Completely revamp node binding for AST matchers.

This is in preparation for the backwards references to bound
nodes, which will expose a lot more about how matches occur.  Main
changes:
- instead of building the tree of bound nodes, we build a "set" of bound
  nodes and explode all possible match combinations while running
  through the matchers; this will allow us to also implement matchers
  that filter down the current set of matches, like "equalsBoundNode"
- take the set of bound nodes at the start of the match into
  consideration when doing memoization; as part of that, reevaluated
  that memoization gives us benefits that are large enough (it still
  does - the effect on common match patterns is up to an order of
  magnitude)
- reset the bound nodes when a node does not match, thus never leaking
  information from partial sub-matcher matches for failing matchers

Effects:
- we can now correctly "explode" combinatorial matches, for example:
  allOf(forEachDescendant(...bind("a")),
  forEachDescendant(...bind("b"))) will now trigger matches for all
  combinations of matching "a" and "b"s.
- we now never expose bound nodes from partial matches in matchers that
  did not match in the end - this fixes a long-standing issue

FIXMEs:
- rename BoundNodesTreeBuilder to BoundNodesBuilder or
  BoundNodesSetBuilder, as we don't build a tree any more; this is out
  of scope for this change, though
- we're seeing some performance regressions (around 10%), but I expect
  some performance tuning will get that back, and it's easily worth
  the increase in expressiveness for now

llvm-svn: 184313

1 files changed, 113 insertions, 6 deletions

diff --git a/clang/unittests/ASTMatchers/ASTMatchersTest.cpp b/clang/unittests/ASTMatchers/ASTMatchersTest.cpp
index 86b54acdebc..9f0d7afb957 100644
--- a/clang/unittests/ASTMatchers/ASTMatchersTest.cpp
+++ b/clang/unittests/ASTMatchers/ASTMatchersTest.cpp
@@ -3009,12 +3009,13 @@ TEST(ForEachDescendant, NestedForEachDescendant) {
     recordDecl(hasName("A"), anyOf(m, forEachDescendant(m))),
     new VerifyIdIsBoundTo<Decl>("x", "C")));
 
-  // FIXME: This is not really a useful matcher, but the result is still
-  // surprising (currently binds "A").
-  //EXPECT_TRUE(matchAndVerifyResultTrue(
-  //  "class A { class B { class C {}; }; };",
-  //  recordDecl(hasName("A"), allOf(hasDescendant(m), anyOf(m, anything()))),
-  //  new VerifyIdIsBoundTo<Decl>("x", "C")));
+  // Check that a partial match of 'm' that binds 'x' in the
+  // first part of anyOf(m, anything()) will not overwrite the
+  // binding created by the earlier binding in the hasDescendant.
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class A { class B { class C {}; }; };",
+      recordDecl(hasName("A"), allOf(hasDescendant(m), anyOf(m, anything()))),
+      new VerifyIdIsBoundTo<Decl>("x", "C")));
 }
 
 TEST(ForEachDescendant, BindsMultipleNodes) {
@@ -3034,6 +3035,112 @@ TEST(ForEachDescendant, BindsRecursiveCombinations) {
       new VerifyIdIsBoundTo<FieldDecl>("f", 8)));
 }
 
+TEST(ForEachDescendant, BindsCombinations) {
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "void f() { if(true) {} if (true) {} while (true) {} if (true) {} while "
+      "(true) {} }",
+      compoundStmt(forEachDescendant(ifStmt().bind("if")),
+                   forEachDescendant(whileStmt().bind("while"))),
+      new VerifyIdIsBoundTo<IfStmt>("if", 6)));
+}
+
+TEST(Has, DoesNotDeleteBindings) {
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class X { int a; };", recordDecl(decl().bind("x"), has(fieldDecl())),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+}
+
+TEST(LoopingMatchers, DoNotOverwritePreviousMatchResultOnFailure) {
+  // Those matchers cover all the cases where an inner matcher is called
+  // and there is not a 1:1 relationship between the match of the outer
+  // matcher and the match of the inner matcher.
+  // The pattern to look for is:
+  //   ... return InnerMatcher.matches(...); ...
+  // In which case no special handling is needed.
+  //
+  // On the other hand, if there are multiple alternative matches
+  // (for example forEach*) or matches might be discarded (for example has*)
+  // the implementation must make sure that the discarded matches do not
+  // affect the bindings.
+  // When new such matchers are added, add a test here that:
+  // - matches a simple node, and binds it as the first thing in the matcher:
+  //     recordDecl(decl().bind("x"), hasName("X")))
+  // - uses the matcher under test afterwards in a way that not the first
+  //   alternative is matched; for anyOf, that means the first branch
+  //   would need to return false; for hasAncestor, it means that not
+  //   the direct parent matches the inner matcher.
+
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class X { int y; };",
+      recordDecl(
+          recordDecl().bind("x"), hasName("::X"),
+          anyOf(forEachDescendant(recordDecl(hasName("Y"))), anything())),
+      new VerifyIdIsBoundTo<CXXRecordDecl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class X {};", recordDecl(recordDecl().bind("x"), hasName("::X"),
+                                anyOf(unless(anything()), anything())),
+      new VerifyIdIsBoundTo<CXXRecordDecl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "template<typename T1, typename T2> class X {}; X<float, int> x;",
+      classTemplateSpecializationDecl(
+          decl().bind("x"),
+          hasAnyTemplateArgument(refersToType(asString("int")))),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class X { void f(); void g(); };",
+      recordDecl(decl().bind("x"), hasMethod(hasName("g"))),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class X { X() : a(1), b(2) {} double a; int b; };",
+      recordDecl(decl().bind("x"),
+                 has(constructorDecl(
+                     hasAnyConstructorInitializer(forField(hasName("b")))))),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "void x(int, int) { x(0, 42); }",
+      callExpr(expr().bind("x"), hasAnyArgument(integerLiteral(equals(42)))),
+      new VerifyIdIsBoundTo<Expr>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "void x(int, int y) {}",
+      functionDecl(decl().bind("x"), hasAnyParameter(hasName("y"))),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "void x() { return; if (true) {} }",
+      functionDecl(decl().bind("x"),
+                   has(compoundStmt(hasAnySubstatement(ifStmt())))),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "namespace X { void b(int); void b(); }"
+      "using X::b;",
+      usingDecl(decl().bind("x"), hasAnyUsingShadowDecl(hasTargetDecl(
+                                      functionDecl(parameterCountIs(1))))),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class A{}; class B{}; class C : B, A {};",
+      recordDecl(decl().bind("x"), isDerivedFrom("::A")),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class A{}; typedef A B; typedef A C; typedef A D;"
+      "class E : A {};",
+      recordDecl(decl().bind("x"), isDerivedFrom("C")),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class A { class B { void f() {} }; };",
+      functionDecl(decl().bind("x"), hasAncestor(recordDecl(hasName("::A")))),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "template <typename T> struct A { struct B {"
+      "  void f() { if(true) {} }"
+      "}; };"
+      "void t() { A<int>::B b; b.f(); }",
+      ifStmt(stmt().bind("x"), hasAncestor(recordDecl(hasName("::A")))),
+      new VerifyIdIsBoundTo<Stmt>("x", 2)));
+  EXPECT_TRUE(matchAndVerifyResultTrue(
+      "class A {};",
+      recordDecl(hasName("::A"), decl().bind("x"), unless(hasName("fooble"))),
+      new VerifyIdIsBoundTo<Decl>("x", 1)));
+}
+
 TEST(ForEachDescendant, BindsCorrectNodes) {
   EXPECT_TRUE(matchAndVerifyResultTrue(
       "class C { void f(); int i; };",