Clean up trivial cycle detection logic.

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 939 matching lines @@
     // 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 (dependency.index == 0) {
+        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) {
-        // In the case where the strongly connected component has only
-        // one node, determine whether there is a trivial cycle or
-        // not.
-        //
-        // TODO(paulberry): could we figure this out in the for-loop
-        // above and save some effort?
+        // 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 (_hasTrivialScc(node)) {
+          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);
   }
-
-  /**
-   * The given [node] is in a strongly connected component of size 1.
-   * Determine if it contains a trivial cycle (i.e. depends on
-   * itself).
-   */
-  bool _hasTrivialScc(NodeType node) {
-    for (NodeType dependency in node.dependencies) {
-      if (identical(dependency, node)) {
-        return true;
-      }
-    }
-    return false;
-  }
 }
 
 /**
  * Representation of the dynamic type during linking.
  */
 class DynamicTypeForLink extends DartTypeForLink {
   /**
    * Singleton instance of the dynamic type.
    */
   static const DynamicTypeForLink instance = const DynamicTypeForLink._();
@@ skipping 569 matching lines @@
 
   /**
    * Throw away any information produced by a previous call to [link].
    */
   void unlink() {
     for (LibraryElementInBuildUnit library in _librariesInBuildUnit) {
       library.unlink();
     }
   }
 }