import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Given a graph G with nodes A and B, this algorithm determines if all paths
 * from A to B contain at least one node satisfying a given predicate.
 *
 * Note that nodePredicate is not necessarily called for all nodes in G nor is
 * edgePredicate called for all edges in G.
 *
 * @param graph Graph G to analyze.
 * @param a The node A.
 * @param b The node B.
 * @param nodePredicate Predicate which at least one node on each path from an
 *     A node to B (inclusive) must match.
 * @param edgePredicate Edges to consider as part of the graph. Edges in
 *     graph that don't match edgePredicate will be ignored.
 */
CheckPathsBetweenNodes(DiGraph<N, E> graph, DiGraphNode<N, E> a,
    DiGraphNode<N, E> b, Predicate<N> nodePredicate,
    Predicate<DiGraphEdge<N, E>> edgePredicate) {
  this.nodePredicate = nodePredicate;
  this.edgePredicate = edgePredicate;

  graph.pushNodeAnnotations();
  graph.pushEdgeAnnotations();

  discoverBackEdges(a);
  result = checkAllPathsWithoutBackEdges(a, b);

  graph.popNodeAnnotations();
  graph.popEdgeAnnotations();
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Tests a graph where some paths between the nodes are valid and others
 * are invalid.
 */
public void testSomeValidPaths() {
  DiGraph<String, String> g = new LinkedDirectedGraph<String, String>();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");
  g.createDirectedGraphNode("e");

  g.connect("a", "1", "b");
  g.connect("b", "2", "c");
  g.connect("b", "3", "e");
  g.connect("e", "4", "d");
  g.connect("c", "5", "d");

  assertBad(createTest(g, "a", "d", Predicates.equalTo("c"), ALL_EDGE));
  assertBad(createTest(g, "a", "d", Predicates.equalTo("z"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/** Tests a graph with many valid paths. */
public void testManyValidPaths() {
  DiGraph<String, String> g = new LinkedDirectedGraph<String, String>();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c1");
  g.createDirectedGraphNode("c2");
  g.createDirectedGraphNode("c3");
  DiGraphNode<String, String> d = g.createDirectedGraphNode("d");

  g.connect("a",  "-", "b");
  g.connect("b",  "-", "c1");
  g.connect("b",  "-", "c2");
  g.connect("c2", "-", "d");
  g.connect("c1", "-", "d");
  g.connect("a",  "-", "c3");
  g.connect("c3", "-", "d");

  assertGood(createTest(g, "a", "d", new PrefixPredicate("c"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/** Tests a graph with some cycles. */
public void testCycles1() {
  DiGraph<String, String> g = new LinkedDirectedGraph<String, String>();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");
  g.createDirectedGraphNode("e");
  g.createDirectedGraphNode("f");

  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "d");
  g.connect("d", "-", "e");
  g.connect("e", "-", "f");
  g.connect("f", "-", "b");

  assertGood(createTest(g, "a", "e", Predicates.equalTo("b"), ALL_EDGE));
  assertGood(createTest(g, "a", "e", Predicates.equalTo("c"), ALL_EDGE));
  assertGood(createTest(g, "a", "e", Predicates.equalTo("d"), ALL_EDGE));
  assertGood(createTest(g, "a", "e", Predicates.equalTo("e"), ALL_EDGE));
  assertBad(createTest(g, "a", "e", Predicates.equalTo("f"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Tests another graph with cycles. The topology of this graph was inspired
 * by a control flow graph that was being incorrectly analyzed by an early
 * version of CheckPathsBetweenNodes.
 */
public void testCycles2() {
  DiGraph<String, String> g = new LinkedDirectedGraph<String, String>();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");
  
  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "b");
  g.connect("b", "-", "d");
  
  assertGood(createTest(g, "a", "d", Predicates.equalTo("a"), ALL_EDGE));
  assertBad(createTest(g, "a", "d", Predicates.equalTo("z"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Tests another graph with cycles. The topology of this graph was inspired
 * by a control flow graph that was being incorrectly analyzed by an early
 * version of CheckPathsBetweenNodes.
 */
public void testCycles3() {
  DiGraph<String, String> g = new LinkedDirectedGraph<String, String>();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");
  
  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "b");
  g.connect("b", "-", "d");
  g.connect("c", "-", "d");
  
  assertGood(createTest(g, "a", "d", Predicates.equalTo("a"), ALL_EDGE));
  assertBad(createTest(g, "a", "d", Predicates.equalTo("z"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
public void testDirectedInAndOutEdges() {
  DiGraph<String, String> graph =
      new LinkedDirectedGraph<String, String>();
  graph.createNode("a");
  graph.createNode("b");
  graph.createNode("c");
  graph.createNode("d");
  graph.connect("a", "->", "b");
  graph.connect("a", "-->", "b");
  graph.connect("a", "--->", "b");
  graph.connect("a", "->", "c");
  graph.connect("c", "->", "d");
  assertSetEquals(graph.getDirectedSuccNodes("a"), "b", "c");
  assertSetEquals(graph.getDirectedPredNodes("b"), "a");
  assertSetEquals(graph.getDirectedPredNodes("c"), "a");
  assertListCount(graph.getDirectedSuccNodes("a"), "b", 3);

  // Removal.
  graph.disconnect("a", "b");
  assertFalse(graph.isConnected("a", "b"));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
private static void digraphConnect(DiGraph<Function, Callsite> digraph,
    Function caller,
    Callsite callsite,
    Function callee,
    boolean forward) {
  
  Function source;
  Function destination;

  if (forward) {
    source = caller;
    destination = callee;
  } else {
    source = callee;
    destination = caller;
  }
  
  digraph.connect(source, callsite, destination);
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Tests another graph with cycles. The topology of this graph was inspired
 * by a control flow graph that was being incorrectly analyzed by an early
 * version of CheckPathsBetweenNodes.
 */
public void testCycles2() {
  DiGraph<String, String> g = new LinkedDirectedGraph<String, String>();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");

  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "b");
  g.connect("b", "-", "d");

  assertGood(createTest(g, "a", "d", Predicates.equalTo("a"), ALL_EDGE));
  assertBad(createTest(g, "a", "d", Predicates.equalTo("z"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Tests another graph with cycles. The topology of this graph was inspired
 * by a control flow graph that was being incorrectly analyzed by an early
 * version of CheckPathsBetweenNodes.
 */
public void testCycles3() {
  DiGraph<String, String> g = new LinkedDirectedGraph<String, String>();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");

  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "b");
  g.connect("b", "-", "d");
  g.connect("c", "-", "d");

  assertGood(createTest(g, "a", "d", Predicates.equalTo("a"), ALL_EDGE));
  assertBad(createTest(g, "a", "d", Predicates.equalTo("z"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Much of the tests are done by testing all paths. We quickly verified
 * that some paths are indeed correct for the some path case.
 */
public void testSomePath1() {
  DiGraph<String, String> g = new LinkedDirectedGraph<String, String>();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");

  g.connect("a", "-", "b");
  g.connect("a", "-", "c");
  g.connect("b", "-", "d");
  g.connect("c", "-", "d");

  assertTrue(createTest(g, "a", "d", Predicates.equalTo("b"), ALL_EDGE)
      .somePathsSatisfyPredicate());
  assertTrue(createTest(g, "a", "d", Predicates.equalTo("c"), ALL_EDGE)
      .somePathsSatisfyPredicate());
  assertTrue(createTest(g, "a", "d", Predicates.equalTo("a"), ALL_EDGE)
      .somePathsSatisfyPredicate());
  assertTrue(createTest(g, "a", "d", Predicates.equalTo("d"), ALL_EDGE)
      .somePathsSatisfyPredicate());
  assertFalse(createTest(g, "a", "d", Predicates.equalTo("NONE"), ALL_EDGE)
      .somePathsSatisfyPredicate());
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
private static void digraphConnect(DiGraph<Function, Callsite> digraph,
    Function caller,
    Callsite callsite,
    Function callee,
    boolean forward) {

  Function source;
  Function destination;

  if (forward) {
    source = caller;
    destination = callee;
  } else {
    source = callee;
    destination = caller;
  }

  digraph.connect(source, callsite, destination);
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Tests a graph where some paths between the nodes are valid and others
 * are invalid.
 */
public void testSomeValidPaths() {
  DiGraph<String, String> g = LinkedDirectedGraph.create();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");
  g.createDirectedGraphNode("e");

  g.connect("a", "1", "b");
  g.connect("b", "2", "c");
  g.connect("b", "3", "e");
  g.connect("e", "4", "d");
  g.connect("c", "5", "d");

  assertBad(createTest(g, "a", "d", Predicates.equalTo("c"), ALL_EDGE));
  assertBad(createTest(g, "a", "d", Predicates.equalTo("z"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/** Tests a graph with many valid paths. */
public void testManyValidPaths() {
  DiGraph<String, String> g = LinkedDirectedGraph.create();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c1");
  g.createDirectedGraphNode("c2");
  g.createDirectedGraphNode("c3");
  DiGraphNode<String, String> d = g.createDirectedGraphNode("d");

  g.connect("a",  "-", "b");
  g.connect("b",  "-", "c1");
  g.connect("b",  "-", "c2");
  g.connect("c2", "-", "d");
  g.connect("c1", "-", "d");
  g.connect("a",  "-", "c3");
  g.connect("c3", "-", "d");

  assertGood(createTest(g, "a", "d", new PrefixPredicate("c"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/** Tests a graph with some cycles. */
public void testCycles1() {
  DiGraph<String, String> g = LinkedDirectedGraph.create();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");
  g.createDirectedGraphNode("e");
  g.createDirectedGraphNode("f");

  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "d");
  g.connect("d", "-", "e");
  g.connect("e", "-", "f");
  g.connect("f", "-", "b");

  assertGood(createTest(g, "a", "e", Predicates.equalTo("b"), ALL_EDGE));
  assertGood(createTest(g, "a", "e", Predicates.equalTo("c"), ALL_EDGE));
  assertGood(createTest(g, "a", "e", Predicates.equalTo("d"), ALL_EDGE));
  assertGood(createTest(g, "a", "e", Predicates.equalTo("e"), ALL_EDGE));
  assertBad(createTest(g, "a", "e", Predicates.equalTo("f"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Tests another graph with cycles. The topology of this graph was inspired
 * by a control flow graph that was being incorrectly analyzed by an early
 * version of CheckPathsBetweenNodes.
 */
public void testCycles2() {
  DiGraph<String, String> g = LinkedDirectedGraph.create();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");

  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "b");
  g.connect("b", "-", "d");

  assertGood(createTest(g, "a", "d", Predicates.equalTo("a"), ALL_EDGE));
  assertBad(createTest(g, "a", "d", Predicates.equalTo("z"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Tests another graph with cycles. The topology of this graph was inspired
 * by a control flow graph that was being incorrectly analyzed by an early
 * version of CheckPathsBetweenNodes.
 */
public void testCycles3() {
  DiGraph<String, String> g = LinkedDirectedGraph.create();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");

  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "b");
  g.connect("b", "-", "d");
  g.connect("c", "-", "d");

  assertGood(createTest(g, "a", "d", Predicates.equalTo("a"), ALL_EDGE));
  assertBad(createTest(g, "a", "d", Predicates.equalTo("z"), ALL_EDGE));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/**
 * Much of the tests are done by testing all paths. We quickly verified
 * that some paths are indeed correct for the some path case.
 */
public void testSomePath1() {
  DiGraph<String, String> g = LinkedDirectedGraph.create();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");

  g.connect("a", "-", "b");
  g.connect("a", "-", "c");
  g.connect("b", "-", "d");
  g.connect("c", "-", "d");

  assertTrue(createTest(g, "a", "d", Predicates.equalTo("b"), ALL_EDGE)
      .somePathsSatisfyPredicate());
  assertTrue(createTest(g, "a", "d", Predicates.equalTo("c"), ALL_EDGE)
      .somePathsSatisfyPredicate());
  assertTrue(createTest(g, "a", "d", Predicates.equalTo("a"), ALL_EDGE)
      .somePathsSatisfyPredicate());
  assertTrue(createTest(g, "a", "d", Predicates.equalTo("d"), ALL_EDGE)
      .somePathsSatisfyPredicate());
  assertFalse(createTest(g, "a", "d", Predicates.equalTo("NONE"), ALL_EDGE)
      .somePathsSatisfyPredicate());
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
public void testDirectedInAndOutEdges() {
  DiGraph<String, String> graph =
      LinkedDirectedGraph.create();
  graph.createNode("a");
  graph.createNode("b");
  graph.createNode("c");
  graph.createNode("d");
  graph.connect("a", "->", "b");
  graph.connect("a", "-->", "b");
  graph.connect("a", "--->", "b");
  graph.connect("a", "->", "c");
  graph.connect("c", "->", "d");
  assertSetEquals(graph.getDirectedSuccNodes("a"), "b", "c");
  assertSetEquals(graph.getDirectedPredNodes("b"), "a");
  assertSetEquals(graph.getDirectedPredNodes("c"), "a");
  assertListCount(graph.getDirectedSuccNodes("a"), "b", 3);

  // Removal.
  graph.disconnect("a", "b");
  assertFalse(graph.isConnected("a", "b"));
}
 

import com.google.javascript.jscomp.graph.DiGraph; //导入依赖的package包/类
/** Tests straight-line graphs. */
public void testSimple() {
  DiGraph<String, String> g = LinkedDirectedGraph.create();
  g.createDirectedGraphNode("a");
  g.createDirectedGraphNode("b");
  g.createDirectedGraphNode("c");
  g.createDirectedGraphNode("d");

  g.connect("a", "-", "b");
  g.connect("b", "-", "c");
  g.connect("c", "-", "d");
  g.connect("a", "x", "d");

  // Simple case: the sole path from a to d has a matching node.
  assertGood(createTest(g, "a", "d", Predicates.equalTo("b"), edgeIs("-")));
  //Test two edge cases where satisfying node is the first and last node on
  // the path.
  assertGood(createTest(g, "a", "d", Predicates.equalTo("a"), edgeIs("-")));
  assertGood(createTest(g, "a", "d", Predicates.equalTo("d"), edgeIs("-")));

  // Traverse no edges, so no paths.
  assertGood(createTest(g, "a", "d", FALSE, NO_EDGE));

  // No path with matching edges contains b.
  assertBad(createTest(g, "a", "d", Predicates.equalTo("b"), edgeIs("x")));
}