New analyzer snapshot (with CaughtException).

pkg/analyzer/lib/src/generated/utilities_collection.dart

 // Copyright (c) 2014, 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 code was auto-generated, is not intended to be edited, and is subject to
 // significant change. Please see the README file for more information.
 
 library engine.utilities.collection;
 
 import 'java_core.dart';
@@ skipping 116 matching lines @@
    * @param node the node to be added
    */
   void addNode(N node) {
     Set<N> tails = _edges[node];
     if (tails == null) {
       _edges[node] = new Set<N>();
     }
   }
 
   /**
-   * Return a list of nodes that form a cycle, or `null` if there are no cycles in this graph.
-   *
-   * @return a list of nodes that form a cycle
+   * Run a topological sort of the graph. Since the graph may contain cycles, this results in a list
+   * of strongly connected components rather than a list of nodes. The nodes in each strongly
+   * connected components only have edges that point to nodes in the same component or earlier
+   * components.
    */
-  List<N> findCycle() => null;
+  List<List<N>> computeTopologicalSort() {
+    DirectedGraph_SccFinder<N> finder = new DirectedGraph_SccFinder<N>(this);
+    return finder.computeTopologicalSort();
+  }
+
+  /**
+   * Return true if the graph contains at least one path from `source` to `destination`.
+   */
+  bool containsPath(N source, N destination) {
+    Set<N> nodesVisited = new Set<N>();
+    return _containsPathInternal(source, destination, nodesVisited);
+  }
 
   /**
    * Return a list of nodes that form a cycle containing the given node. If the node is not part of
    * this graph, then a list containing only the node itself will be returned.
    *
    * @return a list of nodes that form a cycle containing the given node
    */
   List<N> findCycleContaining(N node) {
     if (node == null) {
       throw new IllegalArgumentException();
     }
     DirectedGraph_SccFinder<N> finder = new DirectedGraph_SccFinder<N>(this);
     return finder.componentContaining(node);
   }
 
   /**
    * Return the number of nodes in this graph.
    *
    * @return the number of nodes in this graph
    */
   int get nodeCount => _edges.length;
 
   /**
+   * Return a set of all nodes in the graph.
+   */
+  Set<N> get nodes => _edges.keys.toSet();
+
+  /**
    * Return a set containing the tails of edges that have the given node as their head. The set will
    * be empty if there are no such edges or if the node is not part of the graph. Clients must not
    * modify the returned set.
    *
    * @param head the node at the head of all of the edges whose tails are to be returned
    * @return a set containing the tails of edges that have the given node as their head
    */
   Set<N> getTails(N head) {
     Set<N> tails = _edges[head];
     if (tails == null) {
@@ skipping 61 matching lines @@
    */
   N removeSink() {
     N sink = _findSink();
     if (sink == null) {
       return null;
     }
     removeNode(sink);
     return sink;
   }
 
+  bool _containsPathInternal(N source, N destination, Set<N> nodesVisited) {
+    if (identical(source, destination)) {
+      return true;
+    }
+    Set<N> tails = _edges[source];
+    if (tails != null) {
+      nodesVisited.add(source);
+      for (N tail in tails) {
+        if (!nodesVisited.contains(tail)) {
+          if (_containsPathInternal(tail, destination, nodesVisited)) {
+            return true;
+          }
+        }
+      }
+    }
+    return false;
+  }
+
   /**
    * Return one node that has no outgoing edges (that is, for which there are no edges that have
    * that node as the head of the edge), or `null` if there are no such nodes.
    *
    * @return a sink node
    */
   N _findSink() {
     for (N key in _edges.keys) {
       if (_edges[key].isEmpty) return key;
     }
@@ skipping 60 matching lines @@
    * The stack of nodes that are being visited in order to identify components.
    */
   List<N> _stack = new List<N>();
 
   /**
    * A table mapping nodes to information about the nodes that is used by this algorithm.
    */
   Map<N, DirectedGraph_NodeInfo<N>> _nodeMap = new Map<N, DirectedGraph_NodeInfo<N>>();
 
   /**
+   * A list of all strongly connected components found, in topological sort order (each node in a
+   * strongly connected component only has edges that point to nodes in the same component or
+   * earlier components).
+   */
+  List<List<N>> _allComponents = new List<List<N>>();
+
+  /**
    * Initialize a newly created finder.
    */
   DirectedGraph_SccFinder(this._graph) : super();
 
   /**
    * Return a list containing the nodes that are part of the strongly connected component that
    * contains the given node.
    *
    * @param node the node used to identify the strongly connected component to be returned
    * @return the nodes that are part of the strongly connected component that contains the given
    *         node
    */
   List<N> componentContaining(N node) => _strongConnect(node).component;
 
   /**
+   * Run Tarjan's algorithm and return the resulting list of strongly connected components. The
+   * list is in topological sort order (each node in a strongly connected component only has edges
+   * that point to nodes in the same component or earlier components).
+   */
+  List<List<N>> computeTopologicalSort() {
+    for (N node in _graph._edges.keys.toSet()) {
+      DirectedGraph_NodeInfo<N> nodeInfo = _nodeMap[node];
+      if (nodeInfo == null) {
+        _strongConnect(node);
+      }
+    }
+    return _allComponents;
+  }
+
+  /**
    * Remove and return the top-most element from the stack.
    *
    * @return the element that was removed
    */
   N _pop() {
     N node = _stack.removeAt(_stack.length - 1);
     _nodeMap[node].onStack = false;
     return node;
   }
 
@@ skipping 42 matching lines @@
     // If v is a root node, pop the stack and generate an SCC
     //
     if (vInfo.lowlink == vInfo.index) {
       List<N> component = new List<N>();
       N w;
       do {
         w = _pop();
         component.add(w);
         _nodeMap[w].component = component;
       } while (!identical(w, v));
+      _allComponents.add(component);
     }
     return vInfo;
   }
 }
 
 /**
  * The class `ListUtilities` defines utility methods useful for working with [List
  ].
  */
 class ListUtilities {
@@ skipping 258 matching lines @@
 
   @override
   void set value(V newValue) {
     if (_currentKey == null) {
       throw new NoSuchElementException();
     }
     _currentValue = newValue;
     _map[_currentKey] = newValue;
   }
 }