Review

12

com/google/javascript/jscomp/graph/FixedPointGraphTraversal.java

computeFixedPoint(DiGraph, Set)

class FixedPointGraphTraversal {
  /**
   * Compute a fixed point for the given graph, entering from the given nodes.
   * @param graph The graph to traverse.
   * @param entrySet The nodes to begin traversing from.
   */
  public void computeFixedPoint(DiGraph<N, E> graph, Set<N> entrySet) {
    int cycleCount = 0;
    long nodeCount = graph.getNodes().size();

    // Choose a bail-out heuristically in case the computation
    // doesn't converge.
    long maxIterations = Math.max(nodeCount * nodeCount * nodeCount, 100);

    // Use a LinkedHashSet, so that the traversal is deterministic.
    LinkedHashSet<DiGraphNode<N, E>> workSet =
        Sets.newLinkedHashSet();
    for (N n : entrySet) {
      workSet.add(graph.getDirectedGraphNode(n));
    }
    for (; !workSet.isEmpty() && cycleCount < maxIterations; cycleCount++) {
      // For every out edge in the workSet, traverse that edge. If that
      // edge updates the state of the graph, then add the destination
      // node to the resultSet, so that we can update all of its out edges
      // on the next iteration.
      DiGraphNode<N, E> source = workSet.iterator().next();
      N sourceValue = source.getValue();

      workSet.remove(source);

      List<DiGraphEdge<N, E>> outEdges = source.getOutEdges();
      for (DiGraphEdge<N, E> edge : outEdges) {
        N destNode = edge.getDestination().getValue();
        if (callback.traverseEdge(sourceValue, edge.getValue(), destNode)) {
          workSet.add(edge.getDestination());
        }
      }
    }

    Preconditions.checkState(cycleCount != maxIterations,
        NON_HALTING_ERROR_MSG);
  }

}