First step towards adding a parent map to the ASTContext.

This does not yet implement the LimitNode approach discussed.

The impact of this is an O(n) in the number of nodes in the AST
reduction of complexity for certain kinds of matchers (as otherwise the
parent map gets recreated for every new MatchFinder).

See FIXMEs in the comments for the direction of future work.

llvm-svn: 176251

3 files changed, 73 insertions, 1 deletions

diff --git a/clang/unittests/AST/ASTContextParentMapTest.cpp b/clang/unittests/AST/ASTContextParentMapTest.cpp
new file mode 100644
index 00000000000..c1910a82310
--- /dev/null
+++ b/clang/unittests/AST/ASTContextParentMapTest.cpp
@@ -0,0 +1,71 @@
+//===- unittest/AST/ASTContextParentMapTest.cpp - AST parent map test -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Tests for the getParents(...) methods of ASTContext.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+#include "MatchVerifier.h"
+
+namespace clang {
+namespace ast_matchers {
+
+using clang::tooling::newFrontendActionFactory;
+using clang::tooling::runToolOnCodeWithArgs;
+using clang::tooling::FrontendActionFactory;
+
+TEST(GetParents, ReturnsParentForDecl) {
+  MatchVerifier<Decl> Verifier;
+  EXPECT_TRUE(Verifier.match("class C { void f(); };",
+                             methodDecl(hasParent(recordDecl(hasName("C"))))));
+}
+
+TEST(GetParents, ReturnsParentForStmt) {
+  MatchVerifier<Stmt> Verifier;
+  EXPECT_TRUE(Verifier.match("class C { void f() { if (true) {} } };",
+                             ifStmt(hasParent(compoundStmt()))));
+}
+
+TEST(GetParents, ReturnsParentInsideTemplateInstantiations) {
+  MatchVerifier<Decl> DeclVerifier;
+  EXPECT_TRUE(DeclVerifier.match(
+      "template<typename T> struct C { void f() {} };"
+      "void g() { C<int> c; c.f(); }",
+      methodDecl(hasName("f"),
+                 hasParent(recordDecl(isTemplateInstantiation())))));
+  EXPECT_TRUE(DeclVerifier.match(
+      "template<typename T> struct C { void f() {} };"
+      "void g() { C<int> c; c.f(); }",
+      methodDecl(hasName("f"),
+                 hasParent(recordDecl(unless(isTemplateInstantiation()))))));
+  EXPECT_FALSE(DeclVerifier.match(
+      "template<typename T> struct C { void f() {} };"
+      "void g() { C<int> c; c.f(); }",
+      methodDecl(hasName("f"),
+                 allOf(hasParent(recordDecl(unless(isTemplateInstantiation()))),
+                       hasParent(recordDecl(isTemplateInstantiation()))))));
+}
+
+TEST(GetParents, ReturnsMultipleParentsInTemplateInstantiations) {
+  MatchVerifier<Stmt> TemplateVerifier;
+  EXPECT_TRUE(TemplateVerifier.match(
+      "template<typename T> struct C { void f() {} };"
+      "void g() { C<int> c; c.f(); }",
+      compoundStmt(
+          allOf(hasAncestor(recordDecl(isTemplateInstantiation())),
+                hasAncestor(recordDecl(unless(isTemplateInstantiation())))))));
+}
+
+} // end namespace ast_matchers
+} // end namespace clang
diff --git a/clang/unittests/AST/CMakeLists.txt b/clang/unittests/AST/CMakeLists.txt
index 1ea293ee83a..ad29428220b 100644
--- a/clang/unittests/AST/CMakeLists.txt
+++ b/clang/unittests/AST/CMakeLists.txt
@@ -1,4 +1,5 @@
 add_clang_unittest(ASTTests
+  ASTContextParentMapTest.cpp
   CommentLexer.cpp
   CommentParser.cpp
   DeclPrinterTest.cpp
diff --git a/clang/unittests/AST/MatchVerifier.h b/clang/unittests/AST/MatchVerifier.h
index f0a58537048..7aa78860aa9 100644
--- a/clang/unittests/AST/MatchVerifier.h
+++ b/clang/unittests/AST/MatchVerifier.h
@@ -44,7 +44,7 @@ public:
 protected:
   virtual void run(const MatchFinder::MatchResult &Result);
   virtual void verify(const MatchFinder::MatchResult &Result,
-                      const NodeType &Node) = 0;
+                      const NodeType &Node) {}
 
   void setFailure(const Twine &Result) {
     Verified = false;