* Copyright 2004 The Closure Compiler Authors.

*

* Licensed under the Apache License, Version 2.0 (the "License");

* you may not use this file except in compliance with the License.

* You may obtain a copy of the License at

*

*     http://www.apache.org/licenses/LICENSE-2.0

*

* Unless required by applicable law or agreed to in writing, software

* distributed under the License is distributed on an "AS IS" BASIS,

* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

* See the License for the specific language governing permissions and

* limitations under the License.

*/

  private static Node parse(String js) {

    Compiler compiler = new Compiler();

    compiler.initCompilerOptionsIfTesting();

    compiler.getOptions().setLanguageIn(LanguageMode.ECMASCRIPT5);

    Node n = compiler.parseTestCode(js);

    assertEquals(0, compiler.getErrorCount());

    return n;

  }

  static Node getNode(String js) {

    Node root = parse("var a=(" + js + ");");

    Node expr = root.getFirstChild();

    Node var = expr.getFirstChild();

    return var.getFirstChild();

  }

  public void testIsLiteralOrConstValue() {

    assertLiteralAndImmutable(getNode("10"));

    assertLiteralAndImmutable(getNode("-10"));

    assertLiteralButNotImmutable(getNode("[10, 20]"));

    assertLiteralButNotImmutable(getNode("{'a': 20}"));

    assertLiteralButNotImmutable(getNode("[10, , 1.0, [undefined], 'a']"));

    assertLiteralButNotImmutable(getNode("/abc/"));

    assertLiteralAndImmutable(getNode("\"string\""));

    assertLiteralAndImmutable(getNode("'aaa'"));

    assertLiteralAndImmutable(getNode("null"));

    assertLiteralAndImmutable(getNode("undefined"));

    assertLiteralAndImmutable(getNode("void 0"));

    assertNotLiteral(getNode("abc"));

    assertNotLiteral(getNode("[10, foo(), 20]"));

    assertNotLiteral(getNode("foo()"));

    assertNotLiteral(getNode("c + d"));

    assertNotLiteral(getNode("{'a': foo()}"));

    assertNotLiteral(getNode("void foo()"));

  }

  public void assertLiteralAndImmutable(Node n) {

    assertTrue(NodeUtil.isLiteralValue(n, true));

    assertTrue(NodeUtil.isLiteralValue(n, false));

    assertTrue(NodeUtil.isImmutableValue(n));

  }

  public void assertLiteralButNotImmutable(Node n) {

    assertTrue(NodeUtil.isLiteralValue(n, true));

    assertTrue(NodeUtil.isLiteralValue(n, false));

    assertFalse(NodeUtil.isImmutableValue(n));

  }

  public void assertNotLiteral(Node n) {

    assertFalse(NodeUtil.isLiteralValue(n, true));

    assertFalse(NodeUtil.isLiteralValue(n, false));

    assertFalse(NodeUtil.isImmutableValue(n));

  }

  public void testGetBooleanValue() {

    assertPureBooleanTrue("true");

    assertPureBooleanTrue("10");

    assertPureBooleanTrue("'0'");

    assertPureBooleanTrue("/a/");

    assertPureBooleanTrue("{}");

    assertPureBooleanTrue("[]");

    assertPureBooleanFalse("false");

    assertPureBooleanFalse("null");

    assertPureBooleanFalse("0");

    assertPureBooleanFalse("''");

    assertPureBooleanFalse("undefined");

    assertPureBooleanFalse("void 0");

    assertPureBooleanUnknown("void foo()");

    assertPureBooleanUnknown("b");

    assertPureBooleanUnknown("-'0.0'");

    // Known but getBooleanValue return false for expressions with side-effects

    assertPureBooleanUnknown("{a:foo()}");

    assertPureBooleanUnknown("[foo()]");

  }

  private void assertPureBooleanTrue(String val) {

    assertEquals(TernaryValue.TRUE, NodeUtil.getPureBooleanValue(getNode(val)));

  }

  private void assertPureBooleanFalse(String val) {

    assertEquals(

        TernaryValue.FALSE, NodeUtil.getPureBooleanValue(getNode(val)));

  }

  private void assertPureBooleanUnknown(String val) {

    assertEquals(

        TernaryValue.UNKNOWN, NodeUtil.getPureBooleanValue(getNode(val)));

  }

  public void testGetExpressionBooleanValue() {

    assertImpureBooleanTrue("a=true");

    assertImpureBooleanFalse("a=false");

    assertImpureBooleanTrue("a=(false,true)");

    assertImpureBooleanFalse("a=(true,false)");

    assertImpureBooleanTrue("a=(false || true)");

    assertImpureBooleanFalse("a=(true && false)");

    assertImpureBooleanTrue("a=!(true && false)");

    assertImpureBooleanTrue("a,true");

    assertImpureBooleanFalse("a,false");

    assertImpureBooleanTrue("true||false");

    assertImpureBooleanFalse("false||false");

    assertImpureBooleanTrue("true&&true");

    assertImpureBooleanFalse("true&&false");

    assertImpureBooleanFalse("!true");

    assertImpureBooleanTrue("!false");

    assertImpureBooleanTrue("!''");

    // Assignment ops other than ASSIGN are unknown.

    assertImpureBooleanUnknown("a *= 2");

    // Complex expressions that contain anything other then "=", ",", or "!" are

    // unknown.

    assertImpureBooleanUnknown("2 + 2");

    assertImpureBooleanTrue("a=1");

    assertImpureBooleanTrue("a=/a/");

    assertImpureBooleanTrue("a={}");

    assertImpureBooleanTrue("true");

    assertImpureBooleanTrue("10");

    assertImpureBooleanTrue("'0'");

    assertImpureBooleanTrue("/a/");

    assertImpureBooleanTrue("{}");

    assertImpureBooleanTrue("[]");

    assertImpureBooleanFalse("false");

    assertImpureBooleanFalse("null");

    assertImpureBooleanFalse("0");

    assertImpureBooleanFalse("''");

    assertImpureBooleanFalse("undefined");

    assertImpureBooleanFalse("void 0");

    assertImpureBooleanFalse("void foo()");

    assertImpureBooleanTrue("a?true:true");

    assertImpureBooleanFalse("a?false:false");

    assertImpureBooleanUnknown("a?true:false");

    assertImpureBooleanUnknown("a?true:foo()");

    assertImpureBooleanUnknown("b");

    assertImpureBooleanUnknown("-'0.0'");

    assertImpureBooleanTrue("{a:foo()}");

    assertImpureBooleanTrue("[foo()]");

  }

  private void assertImpureBooleanTrue(String val) {

    assertEquals(TernaryValue.TRUE,

        NodeUtil.getImpureBooleanValue(getNode(val)));

  }

  private void assertImpureBooleanFalse(String val) {

    assertEquals(TernaryValue.FALSE,

        NodeUtil.getImpureBooleanValue(getNode(val)));

  }

  private void assertImpureBooleanUnknown(String val) {

    assertEquals(TernaryValue.UNKNOWN,

        NodeUtil.getImpureBooleanValue(getNode(val)));

  }

  public void testGetStringValue() {

    assertEquals("true", NodeUtil.getStringValue(getNode("true")));

    assertEquals("10", NodeUtil.getStringValue(getNode("10")));

    assertEquals("1", NodeUtil.getStringValue(getNode("1.0")));

    assertEquals("0", NodeUtil.getStringValue(getNode("'0'")));

    assertEquals(null, NodeUtil.getStringValue(getNode("/a/")));

    assertEquals("[object Object]", NodeUtil.getStringValue(getNode("{}")));

    assertEquals("", NodeUtil.getStringValue(getNode("[]")));

    assertEquals("false", NodeUtil.getStringValue(getNode("false")));

    assertEquals("null", NodeUtil.getStringValue(getNode("null")));

    assertEquals("0", NodeUtil.getStringValue(getNode("0")));

    assertEquals("", NodeUtil.getStringValue(getNode("''")));

    assertEquals("undefined", NodeUtil.getStringValue(getNode("undefined")));

    assertEquals("undefined", NodeUtil.getStringValue(getNode("void 0")));

    assertEquals("undefined", NodeUtil.getStringValue(getNode("void foo()")));

    assertEquals("NaN", NodeUtil.getStringValue(getNode("NaN")));

    assertEquals("Infinity", NodeUtil.getStringValue(getNode("Infinity")));

    assertEquals(null, NodeUtil.getStringValue(getNode("x")));

  }

  public void testGetArrayStringValue() {

    assertEquals("", NodeUtil.getStringValue(getNode("[]")));

    assertEquals("", NodeUtil.getStringValue(getNode("['']")));

    assertEquals("", NodeUtil.getStringValue(getNode("[null]")));

    assertEquals("", NodeUtil.getStringValue(getNode("[undefined]")));

    assertEquals("", NodeUtil.getStringValue(getNode("[void 0]")));

    assertEquals("NaN", NodeUtil.getStringValue(getNode("[NaN]")));

    assertEquals(",", NodeUtil.getStringValue(getNode("[,'']")));

    assertEquals(",,", NodeUtil.getStringValue(getNode("[[''],[''],['']]")));

    assertEquals("1,2", NodeUtil.getStringValue(getNode("[[1.0],[2.0]]")));

    assertEquals(null, NodeUtil.getStringValue(getNode("[a]")));

    assertEquals(null, NodeUtil.getStringValue(getNode("[1,a]")));

  }

  public void testIsObjectLiteralKey1() throws Exception {

    testIsObjectLiteralKey(

      parseExpr("({})"), false);

    testIsObjectLiteralKey(

      parseExpr("a"), false);

    testIsObjectLiteralKey(

      parseExpr("'a'"), false);

    testIsObjectLiteralKey(

      parseExpr("1"), false);

    testIsObjectLiteralKey(

      parseExpr("({a: 1})").getFirstChild(), true);

    testIsObjectLiteralKey(

      parseExpr("({1: 1})").getFirstChild(), true);

    testIsObjectLiteralKey(

      parseExpr("({get a(){}})").getFirstChild(), true);

    testIsObjectLiteralKey(

      parseExpr("({set a(b){}})").getFirstChild(), true);

  }

  private Node parseExpr(String js) {

    Compiler compiler = new Compiler();

    CompilerOptions options = new CompilerOptions();

    options.setLanguageIn(LanguageMode.ECMASCRIPT5);

    compiler.initOptions(options);

    Node root = compiler.parseTestCode(js);

    return root.getFirstChild().getFirstChild();

  }

  private void testIsObjectLiteralKey(Node node, boolean expected) {

    assertEquals(expected, NodeUtil.isObjectLitKey(node, node.getParent()));

  }

  public void testGetFunctionName1() throws Exception {

    Compiler compiler = new Compiler();

    Node parent = compiler.parseTestCode("function name(){}");

    testGetFunctionName(parent.getFirstChild(), "name");

  }

  public void testGetFunctionName2() throws Exception {

    Compiler compiler = new Compiler();

    Node parent = compiler.parseTestCode("var name = function(){}")

        .getFirstChild().getFirstChild();

    testGetFunctionName(parent.getFirstChild(), "name");

  }

  public void testGetFunctionName3() throws Exception {

    Compiler compiler = new Compiler();

    Node parent = compiler.parseTestCode("qualified.name = function(){}")

        .getFirstChild().getFirstChild();

    testGetFunctionName(parent.getLastChild(), "qualified.name");

  }

  public void testGetFunctionName4() throws Exception {

    Compiler compiler = new Compiler();

    Node parent = compiler.parseTestCode("var name2 = function name1(){}")

        .getFirstChild().getFirstChild();

    testGetFunctionName(parent.getFirstChild(), "name2");

  }

  public void testGetFunctionName5() throws Exception {

    Compiler compiler = new Compiler();

    Node n = compiler.parseTestCode("qualified.name2 = function name1(){}");

    Node parent = n.getFirstChild().getFirstChild();

    testGetFunctionName(parent.getLastChild(), "qualified.name2");

  }

  private void testGetFunctionName(Node function, String name) {

    assertEquals(Token.FUNCTION, function.getType());

    assertEquals(name, NodeUtil.getFunctionName(function));

  }

  public void testContainsFunctionDeclaration() {

    assertTrue(NodeUtil.containsFunction(

                   getNode("function foo(){}")));

    assertTrue(NodeUtil.containsFunction(

                   getNode("(b?function(){}:null)")));

    assertFalse(NodeUtil.containsFunction(

                   getNode("(b?foo():null)")));

    assertFalse(NodeUtil.containsFunction(

                    getNode("foo()")));

  }

  private void assertSideEffect(boolean se, String js) {

    Node n = parse(js);

    assertEquals(se, NodeUtil.mayHaveSideEffects(n.getFirstChild()));

  }

  private void assertSideEffect(boolean se, String js, boolean GlobalRegExp) {

    Node n = parse(js);

    Compiler compiler = new Compiler();

    compiler.setHasRegExpGlobalReferences(GlobalRegExp);

    assertEquals(se, NodeUtil.mayHaveSideEffects(n.getFirstChild(), compiler));

  }

  public void testMayHaveSideEffects() {

    assertSideEffect(true, "i++");

    assertSideEffect(true, "[b, [a, i++]]");

    assertSideEffect(true, "i=3");

    assertSideEffect(true, "[0, i=3]");

    assertSideEffect(true, "b()");

    assertSideEffect(true, "[1, b()]");

    assertSideEffect(true, "b.b=4");

    assertSideEffect(true, "b.b--");

    assertSideEffect(true, "i--");

    assertSideEffect(true, "a[0][i=4]");

    assertSideEffect(true, "a += 3");

    assertSideEffect(true, "a, b, z += 4");

    assertSideEffect(true, "a ? c : d++");

    assertSideEffect(true, "a + c++");

    assertSideEffect(true, "a + c - d()");

    assertSideEffect(true, "a + c - d()");

    assertSideEffect(true, "function foo() {}");

    assertSideEffect(true, "while(true);");

    assertSideEffect(true, "if(true){a()}");

    assertSideEffect(false, "if(true){a}");

    assertSideEffect(false, "(function() { })");

    assertSideEffect(false, "(function() { i++ })");

    assertSideEffect(false, "[function a(){}]");

    assertSideEffect(false, "a");

    assertSideEffect(false, "[b, c [d, [e]]]");

    assertSideEffect(false, "({a: x, b: y, c: z})");

    assertSideEffect(false, "/abc/gi");

    assertSideEffect(false, "'a'");

    assertSideEffect(false, "0");

    assertSideEffect(false, "a + c");

    assertSideEffect(false, "'c' + a[0]");

    assertSideEffect(false, "a[0][1]");

    assertSideEffect(false, "'a' + c");

    assertSideEffect(false, "'a' + a.name");

    assertSideEffect(false, "1, 2, 3");

    assertSideEffect(false, "a, b, 3");

    assertSideEffect(false, "(function(a, b) {  })");

    assertSideEffect(false, "a ? c : d");

    assertSideEffect(false, "'1' + navigator.userAgent");

    assertSideEffect(false, "new RegExp('foobar', 'i')");

    assertSideEffect(true, "new RegExp(SomethingWacky(), 'i')");

    assertSideEffect(false, "new Array()");

    assertSideEffect(false, "new Array");

    assertSideEffect(false, "new Array(4)");

    assertSideEffect(false, "new Array('a', 'b', 'c')");

    assertSideEffect(true, "new SomeClassINeverHeardOf()");

    assertSideEffect(true, "new SomeClassINeverHeardOf()");

    assertSideEffect(false, "({}).foo = 4");

    assertSideEffect(false, "([]).foo = 4");

    assertSideEffect(false, "(function() {}).foo = 4");

    assertSideEffect(true, "this.foo = 4");

    assertSideEffect(true, "a.foo = 4");

    assertSideEffect(true, "(function() { return n; })().foo = 4");

    assertSideEffect(true, "([]).foo = bar()");

    assertSideEffect(false, "undefined");

    assertSideEffect(false, "void 0");

    assertSideEffect(true, "void foo()");

    assertSideEffect(false, "-Infinity");

    assertSideEffect(false, "Infinity");

    assertSideEffect(false, "NaN");

    assertSideEffect(false, "({}||[]).foo = 2;");

    assertSideEffect(false, "(true ? {} : []).foo = 2;");

    assertSideEffect(false, "({},[]).foo = 2;");

  }

  public void testObjectMethodSideEffects() {

    // "toString" and "valueOf" are assumed to be side-effect free

    assertSideEffect(false, "o.toString()");

    assertSideEffect(false, "o.valueOf()");

    // other methods depend on the extern definitions

    assertSideEffect(true, "o.watch()");

  }

  public void testRegExpSideEffect() {

    // A RegExp Object by itself doesn't have any side-effects

    assertSideEffect(false, "/abc/gi", true);

    assertSideEffect(false, "/abc/gi", false);

    // RegExp instance methods have global side-effects, so whether they are

    // considered side-effect free depends on whether the global properties

    // are referenced.

    assertSideEffect(true, "(/abc/gi).test('')", true);

    assertSideEffect(false, "(/abc/gi).test('')", false);

    assertSideEffect(true, "(/abc/gi).test(a)", true);

    assertSideEffect(false, "(/abc/gi).test(b)", false);

    assertSideEffect(true, "(/abc/gi).exec('')", true);

    assertSideEffect(false, "(/abc/gi).exec('')", false);

    // Some RegExp object method that may have side-effects.

    assertSideEffect(true, "(/abc/gi).foo('')", true);

    assertSideEffect(true, "(/abc/gi).foo('')", false);

    // Try the string RegExp ops.

    assertSideEffect(true, "''.match('a')", true);

    assertSideEffect(false, "''.match('a')", false);

    assertSideEffect(true, "''.match(/(a)/)", true);

    assertSideEffect(false, "''.match(/(a)/)", false);

    assertSideEffect(true, "''.replace('a')", true);

    assertSideEffect(false, "''.replace('a')", false);

    assertSideEffect(true, "''.search('a')", true);

    assertSideEffect(false, "''.search('a')", false);

    assertSideEffect(true, "''.split('a')", true);

    assertSideEffect(false, "''.split('a')", false);

    // Some non-RegExp string op that may have side-effects.

    assertSideEffect(true, "''.foo('a')", true);

    assertSideEffect(true, "''.foo('a')", false);

    // 'a' might be a RegExp object with the 'g' flag, in which case

    // the state might change by running any of the string ops.

    // Specifically, using these methods resets the "lastIndex" if used

    // in combination with a RegExp instance "exec" method.

    assertSideEffect(true, "''.match(a)", true);

    assertSideEffect(true, "''.match(a)", false);

  }

  private void assertMutableState(boolean se, String js) {

    Node n = parse(js);

    assertEquals(se, NodeUtil.mayEffectMutableState(n.getFirstChild()));

  }

  public void testMayEffectMutableState() {

    assertMutableState(true, "i++");

    assertMutableState(true, "[b, [a, i++]]");

    assertMutableState(true, "i=3");

    assertMutableState(true, "[0, i=3]");

    assertMutableState(true, "b()");

    assertMutableState(true, "void b()");

    assertMutableState(true, "[1, b()]");

    assertMutableState(true, "b.b=4");

    assertMutableState(true, "b.b--");

    assertMutableState(true, "i--");

    assertMutableState(true, "a[0][i=4]");

    assertMutableState(true, "a += 3");

    assertMutableState(true, "a, b, z += 4");

    assertMutableState(true, "a ? c : d++");

    assertMutableState(true, "a + c++");

    assertMutableState(true, "a + c - d()");

    assertMutableState(true, "a + c - d()");

    assertMutableState(true, "function foo() {}");

    assertMutableState(true, "while(true);");

    assertMutableState(true, "if(true){a()}");

    assertMutableState(false, "if(true){a}");

    assertMutableState(true, "(function() { })");

    assertMutableState(true, "(function() { i++ })");

    assertMutableState(true, "[function a(){}]");

    assertMutableState(false, "a");

    assertMutableState(true, "[b, c [d, [e]]]");

    assertMutableState(true, "({a: x, b: y, c: z})");

    // Note: RegEx objects are not immutable,  for instance, the exec

    // method maintains state for "global" searches.

    assertMutableState(true, "/abc/gi");

    assertMutableState(false, "'a'");

    assertMutableState(false, "0");

    assertMutableState(false, "a + c");

    assertMutableState(false, "'c' + a[0]");

    assertMutableState(false, "a[0][1]");

    assertMutableState(false, "'a' + c");

    assertMutableState(false, "'a' + a.name");

    assertMutableState(false, "1, 2, 3");

    assertMutableState(false, "a, b, 3");

    assertMutableState(true, "(function(a, b) {  })");

    assertMutableState(false, "a ? c : d");

    assertMutableState(false, "'1' + navigator.userAgent");

    assertMutableState(true, "new RegExp('foobar', 'i')");

    assertMutableState(true, "new RegExp(SomethingWacky(), 'i')");

    assertMutableState(true, "new Array()");

    assertMutableState(true, "new Array");

    assertMutableState(true, "new Array(4)");

    assertMutableState(true, "new Array('a', 'b', 'c')");

    assertMutableState(true, "new SomeClassINeverHeardOf()");

  }

  public void testIsFunctionExpression() {

    assertContainsAnonFunc(true, "(function(){})");

    assertContainsAnonFunc(true, "[function a(){}]");

    assertContainsAnonFunc(false, "{x: function a(){}}");

    assertContainsAnonFunc(true, "(function a(){})()");

    assertContainsAnonFunc(true, "x = function a(){};");

    assertContainsAnonFunc(true, "var x = function a(){};");

    assertContainsAnonFunc(true, "if (function a(){});");

    assertContainsAnonFunc(true, "while (function a(){});");

    assertContainsAnonFunc(true, "do; while (function a(){});");

    assertContainsAnonFunc(true, "for (function a(){};;);");

    assertContainsAnonFunc(true, "for (;function a(){};);");

    assertContainsAnonFunc(true, "for (;;function a(){});");

    assertContainsAnonFunc(true, "for (p in function a(){});");

    assertContainsAnonFunc(true, "with (function a(){}) {}");

    assertContainsAnonFunc(false, "function a(){}");

    assertContainsAnonFunc(false, "if (x) function a(){};");

    assertContainsAnonFunc(false, "if (x) { function a(){} }");

    assertContainsAnonFunc(false, "if (x); else function a(){};");

    assertContainsAnonFunc(false, "while (x) function a(){};");

    assertContainsAnonFunc(false, "do function a(){} while (0);");

    assertContainsAnonFunc(false, "for (;;) function a(){}");

    assertContainsAnonFunc(false, "for (p in o) function a(){};");

    assertContainsAnonFunc(false, "with (x) function a(){}");

  }

  public void testNewFunctionNode() {

    Node expected = parse("function foo(p1, p2, p3) { throw 2; }");

    Node body = new Node(Token.BLOCK, new Node(Token.THROW, Node.newNumber(2)));

    List<Node> params = Lists.newArrayList(Node.newString(Token.NAME, "p1"),

                                           Node.newString(Token.NAME, "p2"),

                                           Node.newString(Token.NAME, "p3"));

    Node function = NodeUtil.newFunctionNode(

        "foo", params, body, -1, -1);

    Node actual = new Node(Token.SCRIPT);

    actual.setIsSyntheticBlock(true);

    actual.addChildToFront(function);

    String difference = expected.checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  private void assertContainsAnonFunc(boolean expected, String js) {

    Node funcParent = findParentOfFuncDescendant(parse(js));

    assertNotNull("Expected function node in parse tree of: " + js, funcParent);

    Node funcNode = getFuncChild(funcParent);

    assertEquals(expected, NodeUtil.isFunctionExpression(funcNode));

  }

  private Node findParentOfFuncDescendant(Node n) {

    for (Node c = n.getFirstChild(); c != null; c = c.getNext()) {

      if (c.getType() == Token.FUNCTION) {

        return n;

      }

      Node result = findParentOfFuncDescendant(c);

      if (result != null) {

        return result;

      }

    }

    return null;

  }

  private Node getFuncChild(Node n) {

    for (Node c = n.getFirstChild(); c != null; c = c.getNext()) {

      if (c.getType() == Token.FUNCTION) {

        return c;

      }

    }

    return null;

  }

  public void testContainsType() {

    assertTrue(NodeUtil.containsType(

        parse("this"), Token.THIS));

    assertTrue(NodeUtil.containsType(

        parse("function foo(){}(this)"), Token.THIS));

    assertTrue(NodeUtil.containsType(

        parse("b?this:null"), Token.THIS));

    assertFalse(NodeUtil.containsType(

        parse("a"), Token.THIS));

    assertFalse(NodeUtil.containsType(

        parse("function foo(){}"), Token.THIS));

    assertFalse(NodeUtil.containsType(

        parse("(b?foo():null)"), Token.THIS));

  }

  public void testReferencesThis() {

    assertTrue(NodeUtil.referencesThis(

        parse("this")));

    // Don't descend into functions (starts at the script node)

    assertFalse(NodeUtil.referencesThis(

        parse("function foo(){this}")));

    // But starting with a function properly check for 'this'

    Node n = parse("function foo(){this}").getFirstChild();

    assertEquals(n.getType(), Token.FUNCTION);

    assertTrue(NodeUtil.referencesThis(n));

    assertTrue(NodeUtil.referencesThis(

        parse("b?this:null")));

    assertFalse(NodeUtil.referencesThis(

        parse("a")));

    n = parse("function foo(){}").getFirstChild();

    assertEquals(n.getType(), Token.FUNCTION);

    assertFalse(NodeUtil.referencesThis(n));

    assertFalse(NodeUtil.referencesThis(

        parse("(b?foo():null)")));

  }

  public void testGetNodeTypeReferenceCount() {

    assertEquals(0, NodeUtil.getNodeTypeReferenceCount(

        parse("function foo(){}"), Token.THIS,

            Predicates.<Node>alwaysTrue()));

    assertEquals(1, NodeUtil.getNodeTypeReferenceCount(

        parse("this"), Token.THIS,

            Predicates.<Node>alwaysTrue()));

    assertEquals(2, NodeUtil.getNodeTypeReferenceCount(

        parse("this;function foo(){}(this)"), Token.THIS,

            Predicates.<Node>alwaysTrue()));

  }

  public void testIsNameReferenceCount() {

    assertTrue(NodeUtil.isNameReferenced(

        parse("function foo(){}"), "foo"));

    assertTrue(NodeUtil.isNameReferenced(

        parse("var foo = function(){}"), "foo"));

    assertFalse(NodeUtil.isNameReferenced(

        parse("function foo(){}"), "undefined"));

    assertTrue(NodeUtil.isNameReferenced(

        parse("undefined"), "undefined"));

    assertTrue(NodeUtil.isNameReferenced(

        parse("undefined;function foo(){}(undefined)"), "undefined"));

    assertTrue(NodeUtil.isNameReferenced(

        parse("goo.foo"), "goo"));

    assertFalse(NodeUtil.isNameReferenced(

        parse("goo.foo"), "foo"));

  }

  public void testGetNameReferenceCount() {

    assertEquals(0, NodeUtil.getNameReferenceCount(

        parse("function foo(){}"), "undefined"));

    assertEquals(1, NodeUtil.getNameReferenceCount(

        parse("undefined"), "undefined"));

    assertEquals(2, NodeUtil.getNameReferenceCount(

        parse("undefined;function foo(){}(undefined)"), "undefined"));

    assertEquals(1, NodeUtil.getNameReferenceCount(

        parse("goo.foo"), "goo"));

    assertEquals(0, NodeUtil.getNameReferenceCount(

        parse("goo.foo"), "foo"));

    assertEquals(1, NodeUtil.getNameReferenceCount(

        parse("function foo(){}"), "foo"));

    assertEquals(1, NodeUtil.getNameReferenceCount(

        parse("var foo = function(){}"), "foo"));

  }

  public void testGetVarsDeclaredInBranch() {

    Compiler compiler = new Compiler();

    assertNodeNames(Sets.newHashSet("foo"),

        NodeUtil.getVarsDeclaredInBranch(

            parse("var foo;")));

    assertNodeNames(Sets.newHashSet("foo","goo"),

        NodeUtil.getVarsDeclaredInBranch(

            parse("var foo,goo;")));

    assertNodeNames(Sets.<String>newHashSet(),

        NodeUtil.getVarsDeclaredInBranch(

            parse("foo();")));

    assertNodeNames(Sets.<String>newHashSet(),

        NodeUtil.getVarsDeclaredInBranch(

            parse("function f(){var foo;}")));

    assertNodeNames(Sets.newHashSet("goo"),

        NodeUtil.getVarsDeclaredInBranch(

            parse("var goo;function f(){var foo;}")));

  }

  private void assertNodeNames(Set<String> nodeNames, Collection<Node> nodes) {

    Set<String> actualNames = Sets.newHashSet();

    for (Node node : nodes) {

      actualNames.add(node.getString());

    }

    assertEquals(nodeNames, actualNames);

  }

  public void testIsControlStructureCodeBlock() {

    Node root = parse("if (x) foo(); else boo();");

    Node ifNode = root.getFirstChild();

    Node ifCondition = ifNode.getFirstChild();

    Node ifCase = ifNode.getFirstChild().getNext();

    Node elseCase = ifNode.getLastChild();

    assertFalse(NodeUtil.isControlStructureCodeBlock(ifNode, ifCondition));

    assertTrue(NodeUtil.isControlStructureCodeBlock(ifNode, ifCase));

    assertTrue(NodeUtil.isControlStructureCodeBlock(ifNode, elseCase));

  }

  public void testIsFunctionExpression1() {

    Node root = parse("(function foo() {})");

    Node StatementNode = root.getFirstChild();

    assertTrue(NodeUtil.isExpressionNode(StatementNode));

    Node functionNode = StatementNode.getFirstChild();

    assertTrue(NodeUtil.isFunction(functionNode));

    assertTrue(NodeUtil.isFunctionExpression(functionNode));

  }

  public void testIsFunctionExpression2() {

    Node root = parse("function foo() {}");

    Node functionNode = root.getFirstChild();

    assertTrue(NodeUtil.isFunction(functionNode));

    assertFalse(NodeUtil.isFunctionExpression(functionNode));

  }

  public void testRemoveChildBlock() {

    // Test removing the inner block.

    Node actual = parse("{{x()}}");

    Node outerBlockNode = actual.getFirstChild();

    Node innerBlockNode = outerBlockNode.getFirstChild();

    innerBlockNode.setIsSyntheticBlock(true);

    NodeUtil.removeChild(outerBlockNode, innerBlockNode);

    String expected = "{{}}";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveTryChild1() {

    // Test removing the finally clause.

    Node actual = parse("try {foo()} catch(e) {} finally {}");

    Node tryNode = actual.getFirstChild();

    Node tryBlock = tryNode.getFirstChild();

    Node catchBlocks = tryNode.getFirstChild().getNext();

    Node finallyBlock = tryNode.getLastChild();

    NodeUtil.removeChild(tryNode, finallyBlock);

    String expected = "try {foo()} catch(e) {}";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveTryChild2() {

    // Test removing the try clause.

    Node actual = parse("try {foo()} catch(e) {} finally {}");

    Node tryNode = actual.getFirstChild();

    Node tryBlock = tryNode.getFirstChild();

    Node catchBlocks = tryNode.getFirstChild().getNext();

    NodeUtil.removeChild(tryNode, tryBlock);

    String expected = "try {} catch(e) {} finally {}";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveTryChild3() {

    // Test removing the catch clause.

    Node actual = parse("try {foo()} catch(e) {} finally {}");

    Node tryNode = actual.getFirstChild();

    Node tryBlock = tryNode.getFirstChild();

    Node catchBlocks = tryNode.getFirstChild().getNext();

    Node catchBlock = catchBlocks.getFirstChild();

    Node finallyBlock = tryNode.getLastChild();

    NodeUtil.removeChild(catchBlocks, catchBlock);

    String expected = "try {foo()} finally {}";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveTryChild4() {

    // Test removing the catch clause without a finally.

    Node actual = parse("try {foo()} catch(e) {} finally {}");

    Node tryNode = actual.getFirstChild();

    Node tryBlock = tryNode.getFirstChild();

    Node catchBlocks = tryNode.getFirstChild().getNext();

    Node catchBlock = catchBlocks.getFirstChild();

    Node finallyBlock = tryNode.getLastChild();

    NodeUtil.removeChild(tryNode, catchBlocks);

    String expected = "try {foo()} finally {}";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveTryChild5() {

    Node actual = parse("try {foo()} catch(e) {} finally {}");

    Node tryNode = actual.getFirstChild();

    Node tryBlock = tryNode.getFirstChild();

    Node catchBlocks = tryNode.getFirstChild().getNext();

    Node catchBlock = catchBlocks.getFirstChild();

    Node finallyBlock = tryNode.getLastChild();

    NodeUtil.removeChild(catchBlocks, catchBlock);

    String expected = "try {foo()} finally {}";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveVarChild() {

    Compiler compiler = new Compiler();

    // Test removing the first child.

    Node actual = parse("var foo, goo, hoo");

    Node varNode = actual.getFirstChild();

    Node nameNode = varNode.getFirstChild();

    NodeUtil.removeChild(varNode, nameNode);

    String expected = "var goo, hoo";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

    // Test removing the second child.

    actual = parse("var foo, goo, hoo");

    varNode = actual.getFirstChild();

    nameNode = varNode.getFirstChild().getNext();

    NodeUtil.removeChild(varNode, nameNode);

    expected = "var foo, hoo";

    difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

    // Test removing the last child of several children.

    actual = parse("var foo, hoo");

    varNode = actual.getFirstChild();

    nameNode = varNode.getFirstChild().getNext();

    NodeUtil.removeChild(varNode, nameNode);

    expected = "var foo";

    difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

    // Test removing the last.

    actual = parse("var hoo");

    varNode = actual.getFirstChild();

    nameNode = varNode.getFirstChild();

    NodeUtil.removeChild(varNode, nameNode);

    expected = "";

    difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveLabelChild1() {

    Compiler compiler = new Compiler();

    // Test removing the first child.

    Node actual = parse("foo: goo()");

    Node labelNode = actual.getFirstChild();

    Node callExpressNode = labelNode.getLastChild();

    NodeUtil.removeChild(labelNode, callExpressNode);

    String expected = "";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveLabelChild2() {

    // Test removing the first child.

    Node actual = parse("achoo: foo: goo()");

    Node labelNode = actual.getFirstChild();

    Node callExpressNode = labelNode.getLastChild();

    NodeUtil.removeChild(labelNode, callExpressNode);

    String expected = "";

    String difference = parse(expected).checkTreeEquals(actual);

    if (difference != null) {

      assertTrue("Nodes do not match:\n" + difference, false);

    }

  }

  public void testRemoveForChild() {

    Compiler compiler = new Compiler();

    // Test removing the initializer.

    Node actual = parse("for(var a=0;a<0;a++)foo()");

    Node forNode = actual.getFirstChild();

    Node child = forNode.getFirstChild();

    NodeUtil.removeChild(forNode, child);

    String expected = "for(;a<0;a++)foo()";

    String difference = parse(expected).checkTreeEquals(actual);

    assertNull("Nodes do not match:\n" + difference, difference);

    // Test removing the condition.

    actual = parse("for(var a=0;a<0;a++)foo()");

    forNode = actual.getFirstChild();

    child = forNode.getFirstChild().getNext();

    NodeUtil.removeChild(forNode, child);

    expected = "for(var a=0;;a++)foo()";

    difference = parse(expected).checkTreeEquals(actual);

    assertNull("Nodes do not match:\n" + difference, difference);

    // Test removing the increment.

    actual = parse("for(var a=0;a<0;a++)foo()");

    forNode = actual.getFirstChild();

    child = forNode.getFirstChild().getNext().getNext();

    NodeUtil.removeChild(forNode, child);

    expected = "for(var a=0;a<0;)foo()";

    difference = parse(expected).checkTreeEquals(actual);

    assertNull("Nodes do not match:\n" + difference, difference);

    // Test removing the body.

    actual = parse("for(var a=0;a<0;a++)foo()");

    forNode = actual.getFirstChild();

    child = forNode.getLastChild();

    NodeUtil.removeChild(forNode, child);

    expected = "for(var a=0;a<0;a++);";

    difference = parse(expected).checkTreeEquals(actual);

    assertNull("Nodes do not match:\n" + difference, difference);