Move dependency walker logic to front end.

pkg/analyzer/lib/src/summary/link.dart

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 /**
  * This library is capable of producing linked summaries from unlinked
  * ones (or prelinked ones).  It functions by building a miniature
  * element model to represent the contents of the summaries, and then
  * scanning the element model to gather linked information and adding
  * it to the summary data structures.
@@ skipping 54 matching lines @@
 import 'package:analyzer/src/dart/element/element.dart';
 import 'package:analyzer/src/dart/element/type.dart';
 import 'package:analyzer/src/dart/resolver/inheritance_manager.dart';
 import 'package:analyzer/src/generated/engine.dart';
 import 'package:analyzer/src/generated/resolver.dart';
 import 'package:analyzer/src/generated/utilities_dart.dart';
 import 'package:analyzer/src/summary/format.dart';
 import 'package:analyzer/src/summary/idl.dart';
 import 'package:analyzer/src/summary/prelink.dart';
 import 'package:analyzer/src/task/strong_mode.dart';
+import 'package:front_end/src/dependency_walker.dart';
 
 bool isIncrementOrDecrement(UnlinkedExprAssignOperator operator) {
   switch (operator) {
     case UnlinkedExprAssignOperator.prefixDecrement:
     case UnlinkedExprAssignOperator.prefixIncrement:
     case UnlinkedExprAssignOperator.postfixDecrement:
     case UnlinkedExprAssignOperator.postfixIncrement:
       return true;
     default:
       return false;
@@ skipping 1660 matching lines @@
   AnalysisOptionsForLink get analysisOptions => _linker.analysisOptions;
 
   @override
   TypeSystem get typeSystem => _linker.typeSystem;
 
   @override
   noSuchMethod(Invocation invocation) => super.noSuchMethod(invocation);
 }
 
 /**
- * An instance of [DependencyWalker] contains the core algorithms for
- * walking a dependency graph and evaluating nodes in a safe order.
- */
-abstract class DependencyWalker<NodeType extends Node<NodeType>> {
-  /**
-   * Called by [walk] to evaluate a single non-cyclical node, after
-   * all that node's dependencies have been evaluated.
-   */
-  void evaluate(NodeType v);
-
-  /**
-   * Called by [walk] to evaluate a strongly connected component
-   * containing one or more nodes.  All dependencies of the strongly
-   * connected component have been evaluated.
-   */
-  void evaluateScc(List<NodeType> scc);
-
-  /**
-   * Walk the dependency graph starting at [startingPoint], finding
-   * strongly connected components and evaluating them in a safe order
-   * by calling [evaluate] and [evaluateScc].
-   *
-   * This is an implementation of Tarjan's strongly connected
-   * components algorithm
-   * (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm).
-   */
-  void walk(NodeType startingPoint) {
-    // TODO(paulberry): consider rewriting in a non-recursive way so
-    // that long dependency chains don't cause stack overflow.
-
-    // TODO(paulberry): in the event that an exception occurs during
-    // the walk, restore the state of the [Node] data structures so
-    // that further evaluation will be safe.
-
-    // The index which will be assigned to the next node that is
-    // freshly visited.
-    int index = 1;
-
-    // Stack of nodes which have been seen so far and whose strongly
-    // connected component is still being determined.  Nodes are only
-    // popped off the stack when they are evaluated, so sometimes the
-    // stack contains nodes that were visited after the current node.
-    List<NodeType> stack = <NodeType>[];
-
-    void strongConnect(NodeType node) {
-      bool hasTrivialCycle = false;
-
-      // Assign the current node an index and add it to the stack.  We
-      // haven't seen any of its dependencies yet, so set its lowLink
-      // to its index, indicating that so far it is the only node in
-      // its strongly connected component.
-      node.index = node.lowLink = index++;
-      stack.add(node);
-
-      // Consider the node's dependencies one at a time.
-      for (NodeType dependency in node.dependencies) {
-        // If the dependency has already been evaluated, it can't be
-        // part of this node's strongly connected component, so we can
-        // skip it.
-        if (dependency.isEvaluated) {
-          continue;
-        }
-        if (identical(node, dependency)) {
-          // If a node includes itself as a dependency, there is no need to
-          // explore the dependency further.
-          hasTrivialCycle = true;
-        } else if (dependency.index == 0) {
-          // The dependency hasn't been seen yet, so recurse on it.
-          strongConnect(dependency);
-          // If the dependency's lowLink refers to a node that was
-          // visited before the current node, that means that the
-          // current node, the dependency, and the node referred to by
-          // the dependency's lowLink are all part of the same
-          // strongly connected component, so we need to update the
-          // current node's lowLink accordingly.
-          if (dependency.lowLink < node.lowLink) {
-            node.lowLink = dependency.lowLink;
-          }
-        } else {
-          // The dependency has already been seen, so it is part of
-          // the current node's strongly connected component.  If it
-          // was visited earlier than the current node's lowLink, then
-          // it is a new addition to the current node's strongly
-          // connected component, so we need to update the current
-          // node's lowLink accordingly.
-          if (dependency.index < node.lowLink) {
-            node.lowLink = dependency.index;
-          }
-        }
-      }
-
-      // If the current node's lowLink is the same as its index, then
-      // we have finished visiting a strongly connected component, so
-      // pop the stack and evaluate it before moving on.
-      if (node.lowLink == node.index) {
-        // The strongly connected component has only one node.  If there is a
-        // cycle, it's a trivial one.
-        if (identical(stack.last, node)) {
-          stack.removeLast();
-          if (hasTrivialCycle) {
-            evaluateScc(<NodeType>[node]);
-          } else {
-            evaluate(node);
-          }
-        } else {
-          // There are multiple nodes in the strongly connected
-          // component.
-          List<NodeType> scc = <NodeType>[];
-          while (true) {
-            NodeType otherNode = stack.removeLast();
-            scc.add(otherNode);
-            if (identical(otherNode, node)) {
-              break;
-            }
-          }
-          evaluateScc(scc);
-        }
-      }
-    }
-
-    // Kick off the algorithm starting with the starting point.
-    strongConnect(startingPoint);
-  }
-}
-
-/**
  * Base class for executable elements resynthesized from a summary during
  * linking.
  */
 abstract class ExecutableElementForLink extends Object
     with TypeParameterizedElementMixin, ParameterParentElementForLink
     implements ExecutableElementImpl {
   /**
    * The unlinked representation of the method in the summary.
    */
   final UnlinkedExecutable _unlinkedExecutable;
@@ skipping 1958 matching lines @@
   }
 
   @override
   noSuchMethod(Invocation invocation) => super.noSuchMethod(invocation);
 
   @override
   String toString() => '$enclosingElement.$name';
 }
 
 /**
- * Instances of [Node] represent nodes in a dependency graph.  The
- * type parameter, [NodeType], is the derived type (this affords some
- * extra type safety by making it difficult to accidentally construct
- * bridges between unrelated dependency graphs).
- */
-abstract class Node<NodeType> {
-  /**
-   * Index used by Tarjan's strongly connected components algorithm.
-   * Zero means the node has not been visited yet; a nonzero value
-   * counts the order in which the node was visited.
-   */
-  int index = 0;
-
-  /**
-   * Low link used by Tarjan's strongly connected components
-   * algorithm.  This represents the smallest [index] of all the nodes
-   * in the strongly connected component to which this node belongs.
-   */
-  int lowLink = 0;
-
-  List<NodeType> _dependencies;
-
-  /**
-   * Retrieve the dependencies of this node.
-   */
-  List<NodeType> get dependencies => _dependencies ??= computeDependencies();
-
-  /**
-   * Indicates whether this node has been evaluated yet.
-   */
-  bool get isEvaluated;
-
-  /**
-   * Compute the dependencies of this node.
-   */
-  List<NodeType> computeDependencies();
-}
-
-/**
  * Element used for references that result from trying to access a non-static
  * member of an element that is not a container (e.g. accessing the "length"
  * property of a constant).
  *
  * Accesses to a chain of non-static members separated by '.' are andled by
  * creating a [NonstaticMemberElementForLink] that points to another
  * [NonstaticMemberElementForLink], to whatever nesting level is necessary.
  */
 class NonstaticMemberElementForLink extends Object
     with ReferenceableElementForLink {
@@ skipping 1204 matching lines @@
    * there are no type parameters in scope.
    */
   TypeParameterizedElementMixin get _typeParameterContext;
 
   @override
   noSuchMethod(Invocation invocation) => super.noSuchMethod(invocation);
 
   @override
   String toString() => '$enclosingElement.$name';
 }