import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testUndirectedSimple() {
  UndiGraph<String, String> graph =
      new LinkedUndirectedGraph<String, String>();
  graph.createNode("a");
  graph.createNode("b");
  graph.createNode("c");
  graph.connect("a", "--", "b");
  assertTrue(graph.hasNode("a"));
  assertTrue(graph.hasNode("b"));
  assertTrue(graph.hasNode("c"));
  assertFalse(graph.hasNode("d"));
  assertTrue(graph.isConnected("a", "b"));
  assertTrue(graph.isConnected("b", "a"));
  assertFalse(graph.isConnected("a", "c"));
  assertFalse(graph.isConnected("b", "c"));
  assertFalse(graph.isConnected("c", "a"));
  assertFalse(graph.isConnected("c", "b"));
  assertFalse(graph.isConnected("a", "a"));
  assertFalse(graph.isConnected("b", "b"));
  assertFalse(graph.isConnected("b", "c"));

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

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testUndirectedNeighbors() {
  UndiGraph<String, String> graph =
      new LinkedUndirectedGraph<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.getNeighborNodes("a"), "b", "c");
  assertSetEquals(graph.getNeighborNodes("b"), "a");
  assertSetEquals(graph.getNeighborNodes("c"), "a", "d");
  assertListCount(graph.getNeighborNodes("a"), "b", 3);

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

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testSimpleSubGraph() {
  UndiGraph<String, String> graph =
      new LinkedUndirectedGraph<String, String>();
  graph.createNode("a");
  graph.createNode("b");
  graph.createNode("c");
  graph.connect("a", "--", "b");

  SubGraph<String, String> subGraph = graph.newSubGraph();
  subGraph.addNode("a");
  subGraph.addNode("b");

  try {
    subGraph.addNode("d");
    fail("SubGraph should not allow add for node that is not in graph.");
  } catch (IllegalArgumentException e) {
    // exception expected
  }

  assertFalse(subGraph.isIndependentOf("a"));
  assertFalse(subGraph.isIndependentOf("b"));
  assertTrue(subGraph.isIndependentOf("c"));
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testUndirectedSimple() {
  UndiGraph<String, String> graph =
      LinkedUndirectedGraph.create();
  graph.createNode("a");
  graph.createNode("b");
  graph.createNode("c");
  graph.connect("a", "--", "b");
  assertTrue(graph.hasNode("a"));
  assertTrue(graph.hasNode("b"));
  assertTrue(graph.hasNode("c"));
  assertFalse(graph.hasNode("d"));
  assertTrue(graph.isConnected("a", "b"));
  assertTrue(graph.isConnected("b", "a"));
  assertFalse(graph.isConnected("a", "c"));
  assertFalse(graph.isConnected("b", "c"));
  assertFalse(graph.isConnected("c", "a"));
  assertFalse(graph.isConnected("c", "b"));
  assertFalse(graph.isConnected("a", "a"));
  assertFalse(graph.isConnected("b", "b"));
  assertFalse(graph.isConnected("b", "c"));

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

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testUndirectedNeighbors() {
  UndiGraph<String, String> graph =
      LinkedUndirectedGraph.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.getNeighborNodes("a"), "b", "c");
  assertSetEquals(graph.getNeighborNodes("b"), "a");
  assertSetEquals(graph.getNeighborNodes("c"), "a", "d");
  assertListCount(graph.getNeighborNodes("a"), "b", 3);

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

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testSimpleSubGraph() {
  UndiGraph<String, String> graph =
      LinkedUndirectedGraph.create();
  graph.createNode("a");
  graph.createNode("b");
  graph.createNode("c");
  graph.connect("a", "--", "b");

  SubGraph<String, String> subGraph = graph.newSubGraph();
  subGraph.addNode("a");
  subGraph.addNode("b");

  try {
    subGraph.addNode("d");
    fail("SubGraph should not allow add for node that is not in graph.");
  } catch (IllegalArgumentException e) {
    // exception expected
  }

  assertFalse(subGraph.isIndependentOf("a"));
  assertFalse(subGraph.isIndependentOf("b"));
  assertTrue(subGraph.isIndependentOf("c"));
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
@Override
public void enterScope(NodeTraversal t) {
  // TODO(user): We CAN do this in the global scope, just need to be
  // careful when something is exported. Liveness uses bit-vector for live
  // sets so I don't see compilation time will be a problem for running this
  // pass in the global scope.
  Scope scope = t.getScope();
  if (scope.isGlobal()) {
    return;
  }
  ControlFlowGraph<Node> cfg = t.getControlFlowGraph();

  LiveVariablesAnalysis liveness =
      new LiveVariablesAnalysis(cfg, scope, compiler);
  liveness.analyze();

  UndiGraph<Var, Void> interferenceGraph =
      computeVariableNamesInterferenceGraph(
          t, cfg, liveness.getEscapedLocals());

  GraphColoring<Var, Void> coloring =
      new GreedyGraphColoring<Var, Void>(interferenceGraph,
          coloringTieBreaker);

  coloring.color();
  colorings.push(coloring);
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
void connectIfCrossed(UndiGraph<Var, Void> interferenceGraph) {
  if (callback1.crossed || callback2.crossed) {
    Var v1 = callback1.getDef();
    Var v2 = callback2.getDef();
    interferenceGraph.connectIfNotFound(v1, null, v2);
  }
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testUndirectedSelfLoop() {
  UndiGraph<String, String> graph =
      new LinkedUndirectedGraph<String, String>();
  graph.createNode("a");
  graph.createNode("b");
  graph.connect("a", "--", "a");
  assertTrue(graph.isConnected("a", "a"));
  assertFalse(graph.isConnected("a", "b"));
  assertFalse(graph.isConnected("b", "a"));

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

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
@Override
public void enterScope(NodeTraversal t) {
  // TODO(user): We CAN do this in the global scope, just need to be
  // careful when something is exported. Liveness uses bit-vector for live
  // sets so I don't see compilation time will be a problem for running this
  // pass in the global scope.
  if (t.inGlobalScope()) {
    return;
  }
  Scope scope = t.getScope();
  ControlFlowGraph<Node> cfg = t.getControlFlowGraph();

  LiveVariablesAnalysis liveness =
      new LiveVariablesAnalysis(cfg, scope, compiler);
  // If the function has exactly 2 params, mark them as escaped. This is
  // a work-around for an IE bug where it throws an exception if you
  // write to the parameters of the callback in a sort(). See:
  // http://code.google.com/p/closure-compiler/issues/detail?id=58
  if (scope.getRootNode().getFirstChild().getNext().getChildCount() == 2) {
    liveness.markAllParametersEscaped();
  }
  liveness.analyze();

  UndiGraph<Var, Void> interferenceGraph =
      computeVariableNamesInterferenceGraph(
          t, cfg, liveness.getEscapedLocals());

  GraphColoring<Var, Void> coloring =
      new GreedyGraphColoring<Var, Void>(interferenceGraph,
          coloringTieBreaker);

  coloring.color();
  colorings.push(coloring);
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
@Override
public void enterScope(NodeTraversal t) {
  Scope scope = t.getScope();
  if (!shouldOptimizeScope(scope)) {
    return;
  }

  ControlFlowGraph<Node> cfg = t.getControlFlowGraph();
  LiveVariablesAnalysis liveness =
      new LiveVariablesAnalysis(cfg, scope, compiler);
  // If the function has exactly 2 params, mark them as escaped. This is
  // a work-around for an IE bug where it throws an exception if you
  // write to the parameters of the callback in a sort(). See:
  // http://code.google.com/p/closure-compiler/issues/detail?id=58
  if (scope.getRootNode().getFirstChild().getNext().getChildCount() == 2) {
    liveness.markAllParametersEscaped();
  }
  liveness.analyze();

  UndiGraph<Var, Void> interferenceGraph =
      computeVariableNamesInterferenceGraph(
          t, cfg, liveness.getEscapedLocals());

  GraphColoring<Var, Void> coloring =
      new GreedyGraphColoring<Var, Void>(interferenceGraph,
          coloringTieBreaker);

  coloring.color();
  colorings.push(coloring);
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
boolean connectIfCrossed(UndiGraph<Var, Void> interferenceGraph) {
  if (callback1.crossed || callback2.crossed) {
    Var v1 = callback1.getDef();
    Var v2 = callback2.getDef();
    interferenceGraph.connectIfNotFound(v1, null, v2);
    return true;
  }
  return false;
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testUndirectedSelfLoop() {
  UndiGraph<String, String> graph =
      LinkedUndirectedGraph.create();
  graph.createNode("a");
  graph.createNode("b");
  graph.connect("a", "--", "a");
  assertTrue(graph.isConnected("a", "a"));
  assertFalse(graph.isConnected("a", "b"));
  assertFalse(graph.isConnected("b", "a"));

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

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
public void testUndirectedGetFirstEdge() {
  UndiGraph<String, String> graph =
    LinkedUndirectedGraph.create();
  graph.createNode("a");
  graph.createNode("b");
  graph.createNode("c");
  graph.connect("a", "-", "b");
  assertEquals(graph.getFirstEdge("a", "b").getValue(), "-");
  assertEquals(graph.getFirstEdge("b", "a").getValue(), "-");
  assertNull(graph.getFirstEdge("a", "c"));
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
boolean connectIfCrossed(UndiGraph<Var, Void> interferenceGraph) {
  if (callback1.crossed || callback2.crossed) {
    Var v1 = callback1.def;
    Var v2 = callback2.def;
    interferenceGraph.connectIfNotFound(v1, null, v2);
    return true;
  }
  return false;
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
@Override
public void enterScope(NodeTraversal t) {
  Scope scope = t.getScope();
  if (!shouldOptimizeScope(scope)) {
    return;
  }

  ControlFlowGraph<Node> cfg = t.getControlFlowGraph();
  LiveVariablesAnalysis liveness =
      new LiveVariablesAnalysis(cfg, scope, compiler);
  // If the function has exactly 2 params, mark them as escaped. This is
  // a work-around for an IE bug where it throws an exception if you
  // write to the parameters of the callback in a sort(). See:
  // http://code.google.com/p/closure-compiler/issues/detail?id=58
  if (scope.getRootNode().getFirstChild().getNext().getChildCount() == 2) {
    liveness.markAllParametersEscaped();
  }
  liveness.analyze();

  UndiGraph<Var, Void> interferenceGraph =
      computeVariableNamesInterferenceGraph(
          t, cfg, liveness.getEscapedLocals());

  GraphColoring<Var, Void> coloring =
      new GreedyGraphColoring<>(interferenceGraph,
          coloringTieBreaker);

  coloring.color();
  colorings.push(coloring);
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
private UndiGraph<Var, Void> computeVariableNamesInterferenceGraph(
    NodeTraversal t, ControlFlowGraph<Node> cfg, Set<Var> escaped) {
  UndiGraph<Var, Void> interferenceGraph =
      new LinkedUndirectedGraph<Var, Void>();
  Scope scope = t.getScope();

  // First create a node for each non-escaped variable.
  for (Iterator<Var> i = scope.getVars(); i.hasNext();) {
    Var v = i.next();
    if (!escaped.contains(v)) {
      
      // TODO(user): In theory, we CAN coalesce function names just like
      // any variables. Our Liveness analysis captures this just like it as
      // described in the specification. However, we saw some zipped and
      // and unzipped size increase after this. We are not totally sure why
      // that is but, for now, we will respect the dead functions and not play
      // around with it.
      if (!NodeUtil.isFunction(v.getParentNode())) {
        interferenceGraph.createNode(v);
      }
    }
  }

  // Go through every single point of the program and look at each variable
  // pairs. If they are both live at the same time, at an edge between them.
  for (DiGraphNode<Node, Branch> cfgNode : cfg.getDirectedGraphNodes()) {
    FlowState<LiveVariableLattice> state = cfgNode.getAnnotation();
    if (cfg.isImplicitReturn(cfgNode)) {
      continue;
    }

    int varsInScope = scope.getVarCount();
    ArrayList<CombinedLiveRangeChecker> rangesToCheck =
        new ArrayList<CombinedLiveRangeChecker>(
            varsInScope * varsInScope);

    for (Iterator<Var> i1 = scope.getVars(); i1.hasNext();) {
      Var v1 = i1.next();
      for (Iterator<Var> i2 = scope.getVars(); i2.hasNext();) {
        Var v2 = i2.next();

        if (v1 == v2 || !interferenceGraph.hasNode(v1) ||
            !interferenceGraph.hasNode(v2)) {
          // Skip nodes that were not added. They are globals and escaped
          // locals. Also avoid merging a variable with itself.
          continue;
        }

        boolean v1OutLive = state.getOut().isLive(v1);
        boolean v2OutLive = state.getOut().isLive(v2);
        // Finally, check the live states and add edge when possible.
        if (v1.getParentNode().getType() == Token.LP &&
            v2.getParentNode().getType() == Token.LP) {
          interferenceGraph.connectIfNotFound(v1, null, v2);
        } else if ((state.getIn().isLive(v1) && state.getIn().isLive(v2)) ||
            (v1OutLive && v2OutLive)) {
          interferenceGraph.connectIfNotFound(v1, null, v2);
        } else {
          LiveRangeChecker checker1 =
              new LiveRangeChecker(v1, v2OutLive ? null : v2);
          LiveRangeChecker checker2 =
              new LiveRangeChecker(v2, v1OutLive ? null : v1);
          rangesToCheck.add(new CombinedLiveRangeChecker(checker1, checker2));
        }
      }
    }

    // Do the collected live range checks.
    checkRanges(rangesToCheck, cfgNode.getValue());
    for (CombinedLiveRangeChecker range : rangesToCheck) {
      range.connectIfCrossed(interferenceGraph);
    }
  }
  return interferenceGraph;
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
private UndiGraph<Var, Void> computeVariableNamesInterferenceGraph(
    NodeTraversal t, ControlFlowGraph<Node> cfg, Set<Var> escaped) {
  UndiGraph<Var, Void> interferenceGraph =
      new LinkedUndirectedGraph<Var, Void>();
  Scope scope = t.getScope();

  // First create a node for each non-escaped variable.
  for (Iterator<Var> i = scope.getVars(); i.hasNext();) {
    Var v = i.next();
    if (!escaped.contains(v)) {

      // TODO(user): In theory, we CAN coalesce function names just like
      // any variables. Our Liveness analysis captures this just like it as
      // described in the specification. However, we saw some zipped and
      // and unzipped size increase after this. We are not totally sure why
      // that is but, for now, we will respect the dead functions and not play
      // around with it.
      if (!NodeUtil.isFunction(v.getParentNode())) {
        interferenceGraph.createNode(v);
      }
    }
  }

  // Go through every single point of the program and look at each variable
  // pairs. If they are both live at the same time, at an edge between them.
  for (DiGraphNode<Node, Branch> cfgNode : cfg.getDirectedGraphNodes()) {
    FlowState<LiveVariableLattice> state = cfgNode.getAnnotation();
    if (cfg.isImplicitReturn(cfgNode)) {
      continue;
    }

    int varsInScope = scope.getVarCount();
    ArrayList<CombinedLiveRangeChecker> rangesToCheck =
        new ArrayList<CombinedLiveRangeChecker>(
            varsInScope * varsInScope);

    for (Iterator<Var> i1 = scope.getVars(); i1.hasNext();) {
      Var v1 = i1.next();
      for (Iterator<Var> i2 = scope.getVars(); i2.hasNext();) {
        Var v2 = i2.next();

        if (v1 == v2 || !interferenceGraph.hasNode(v1) ||
            !interferenceGraph.hasNode(v2)) {
          // Skip nodes that were not added. They are globals and escaped
          // locals. Also avoid merging a variable with itself.
          continue;
        }

        boolean v1OutLive = state.getOut().isLive(v1);
        boolean v2OutLive = state.getOut().isLive(v2);
        // Finally, check the live states and add edge when possible.
        if (v1.getParentNode().getType() == Token.LP &&
            v2.getParentNode().getType() == Token.LP) {
          interferenceGraph.connectIfNotFound(v1, null, v2);
        } else if ((state.getIn().isLive(v1) && state.getIn().isLive(v2)) ||
            (v1OutLive && v2OutLive)) {
          interferenceGraph.connectIfNotFound(v1, null, v2);
        } else {
          LiveRangeChecker checker1 =
              new LiveRangeChecker(v1, v2OutLive ? null : v2);
          LiveRangeChecker checker2 =
              new LiveRangeChecker(v2, v1OutLive ? null : v1);
          rangesToCheck.add(new CombinedLiveRangeChecker(checker1, checker2));
        }
      }
    }

    // Do the collected live range checks.
    checkRanges(rangesToCheck, cfgNode.getValue());
    for (CombinedLiveRangeChecker range : rangesToCheck) {
      range.connectIfCrossed(interferenceGraph);
    }
  }
  return interferenceGraph;
}
 

import com.google.javascript.jscomp.graph.UndiGraph; //导入依赖的package包/类
@Override
public void enterScope(NodeTraversal t) {
  Scope scope = t.getScope();
  if (!shouldOptimizeScope(t)) {
    return;
  }

  checkState(scope.isFunctionScope(), scope);

  // live variables analysis is based off of the control flow graph
  ControlFlowGraph<Node> cfg = t.getControlFlowGraph();

  liveness =
      new LiveVariablesAnalysis(
          cfg, scope, null, compiler, new Es6SyntacticScopeCreator(compiler));

  if (compiler.getOptions().getLanguageOut() == CompilerOptions.LanguageMode.ECMASCRIPT3) {
    // If the function has exactly 2 params, mark them as escaped. This is a work-around for a
    // bug in IE 8 and below, where it throws an exception if you write to the parameters of the
    // callback in a sort(). See http://blickly.github.io/closure-compiler-issues/#58 and
    // https://www.zachleat.com/web/array-sort/
    Node enclosingFunction = scope.getRootNode();
    if (NodeUtil.getFunctionParameters(enclosingFunction).hasTwoChildren()) {
      liveness.markAllParametersEscaped();
    }
  }

  liveness.analyze();
  liveAnalyses.push(liveness);

  // The interference graph has the function's variables as its nodes and any interference
  // between the variables as the edges. Interference between two variables means that they are
  // alive at overlapping times, which means that their variable names cannot be coalesced.
  UndiGraph<Var, Void> interferenceGraph =
      computeVariableNamesInterferenceGraph(cfg, liveness.getEscapedLocals());

  // Color any interfering variables with different colors and any variables that can be safely
  // coalesced wih the same color.
  GraphColoring<Var, Void> coloring =
      new GreedyGraphColoring<>(interferenceGraph, coloringTieBreaker);
  coloring.color();
  colorings.push(coloring);
}