lib/ASTMatchers/ASTMatchFinder.cpp - platform/external/clang - Git at Google

 //===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  Implements an algorithm to efficiently search for matches on AST nodes.
 //  Uses memoization to support recursive matches like HasDescendant.
 //
 //  The general idea is to visit all AST nodes with a RecursiveASTVisitor,
 //  calling the Matches(...) method of each matcher we are running on each
 //  AST node. The matcher can recurse via the ASTMatchFinder interface.
 //
 //===----------------------------------------------------------------------===//

 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include <set>

 namespace clang {
 namespace ast_matchers {
 namespace internal {
 namespace {

 // Returns the value that 'AMap' maps 'Key' to, or NULL if 'Key' is
 // not in 'AMap'.
 template <typename Map>
 static const typename Map::mapped_type *
 find(const Map &AMap, const typename Map::key_type &Key) {
   typename Map::const_iterator It = AMap.find(Key);
   return It == AMap.end() ? NULL : &It->second;
 }

 // We use memoization to avoid running the same matcher on the same
 // AST node twice.  This pair is the key for looking up match
 // result.  It consists of an ID of the MatcherInterface (for
 // identifying the matcher) and a pointer to the AST node.
 typedef std::pair<uint64_t, const void*> UntypedMatchInput;

 // Used to store the result of a match and possibly bound nodes.
 struct MemoizedMatchResult {
   bool ResultOfMatch;
   BoundNodesTree Nodes;
 };

 // A RecursiveASTVisitor that traverses all children or all descendants of
 // a node.
 class MatchChildASTVisitor
     : public RecursiveASTVisitor<MatchChildASTVisitor> {
 public:
   typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;

   // Creates an AST visitor that matches 'matcher' on all children or
   // descendants of a traversed node. max_depth is the maximum depth
   // to traverse: use 1 for matching the children and INT_MAX for
   // matching the descendants.
   MatchChildASTVisitor(const UntypedBaseMatcher *BaseMatcher,
                        ASTMatchFinder *Finder,
                        BoundNodesTreeBuilder *Builder,
                        int MaxDepth,
                        ASTMatchFinder::TraversalKind Traversal,
                        ASTMatchFinder::BindKind Bind)
       : BaseMatcher(BaseMatcher),
         Finder(Finder),
         Builder(Builder),
         CurrentDepth(-1),
         MaxDepth(MaxDepth),
         Traversal(Traversal),
         Bind(Bind),
         Matches(false) {}

   // Returns true if a match is found in the subtree rooted at the
   // given AST node. This is done via a set of mutually recursive
   // functions. Here's how the recursion is done (the  *wildcard can
   // actually be Decl, Stmt, or Type):
   //
   //   - Traverse(node) calls BaseTraverse(node) when it needs
   //     to visit the descendants of node.
   //   - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
   //     Traverse*(c) for each child c of 'node'.
   //   - Traverse*(c) in turn calls Traverse(c), completing the
   //     recursion.
   template <typename T>
   bool findMatch(const T &Node) {
     reset();
     traverse(Node);
     return Matches;
   }

   // The following are overriding methods from the base visitor class.
   // They are public only to allow CRTP to work. They are *not *part
   // of the public API of this class.
   bool TraverseDecl(Decl *DeclNode) {
     return (DeclNode == NULL) || traverse(*DeclNode);
   }
   bool TraverseStmt(Stmt *StmtNode) {
     const Stmt *StmtToTraverse = StmtNode;
     if (Traversal ==
         ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
       const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
       if (ExprNode != NULL) {
         StmtToTraverse = ExprNode->IgnoreParenImpCasts();
       }
     }
     return (StmtToTraverse == NULL) || traverse(*StmtToTraverse);
   }
   bool TraverseType(QualType TypeNode) {
     return traverse(TypeNode);
   }

   bool shouldVisitTemplateInstantiations() const { return true; }
   bool shouldVisitImplicitCode() const { return true; }

 private:
   // Used for updating the depth during traversal.
   struct ScopedIncrement {
     explicit ScopedIncrement(int *Depth) : Depth(Depth) { ++(*Depth); }
     ~ScopedIncrement() { --(*Depth); }

    private:
     int *Depth;
   };

   // Resets the state of this object.
   void reset() {
     Matches = false;
     CurrentDepth = -1;
   }

   // Forwards the call to the corresponding Traverse*() method in the
   // base visitor class.
   bool baseTraverse(const Decl &DeclNode) {
     return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
   }
   bool baseTraverse(const Stmt &StmtNode) {
     return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
   }
   bool baseTraverse(QualType TypeNode) {
     return VisitorBase::TraverseType(TypeNode);
   }

   // Traverses the subtree rooted at 'node'; returns true if the
   // traversal should continue after this function returns; also sets
   // matched_ to true if a match is found during the traversal.
   template <typename T>
   bool traverse(const T &Node) {
     TOOLING_COMPILE_ASSERT(IsBaseType<T>::value,
                            traverse_can_only_be_instantiated_with_base_type);
     ScopedIncrement ScopedDepth(&CurrentDepth);
     if (CurrentDepth == 0) {
       // We don't want to match the root node, so just recurse.
       return baseTraverse(Node);
     }
     if (Bind != ASTMatchFinder::BK_All) {
       if (BaseMatcher->matches(Node, Finder, Builder)) {
         Matches = true;
         return false;  // Abort as soon as a match is found.
       }
       if (CurrentDepth < MaxDepth) {
         // The current node doesn't match, and we haven't reached the
         // maximum depth yet, so recurse.
         return baseTraverse(Node);
       }
       // The current node doesn't match, and we have reached the
       // maximum depth, so don't recurse (but continue the traversal
       // such that other nodes at the current level can be visited).
       return true;
     } else {
       BoundNodesTreeBuilder RecursiveBuilder;
       if (BaseMatcher->matches(Node, Finder, &RecursiveBuilder)) {
         // After the first match the matcher succeeds.
         Matches = true;
         Builder->addMatch(RecursiveBuilder.build());
       }
       if (CurrentDepth < MaxDepth) {
         baseTraverse(Node);
       }
       // In kBindAll mode we always search for more matches.
       return true;
     }
   }

   const UntypedBaseMatcher *const BaseMatcher;
   ASTMatchFinder *const Finder;
   BoundNodesTreeBuilder *const Builder;
   int CurrentDepth;
   const int MaxDepth;
   const ASTMatchFinder::TraversalKind Traversal;
   const ASTMatchFinder::BindKind Bind;
   bool Matches;
 };

 // Controls the outermost traversal of the AST and allows to match multiple
 // matchers.
 class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
                         public ASTMatchFinder {
 public:
   MatchASTVisitor(std::vector< std::pair<const UntypedBaseMatcher*,
                                MatchFinder::MatchCallback*> > *Triggers)
      : Triggers(Triggers),
        ActiveASTContext(NULL) {
   }

   void set_active_ast_context(ASTContext *NewActiveASTContext) {
     ActiveASTContext = NewActiveASTContext;
   }

   // The following Visit*() and Traverse*() functions "override"
   // methods in RecursiveASTVisitor.

   bool VisitTypedefDecl(TypedefDecl *DeclNode) {
     // When we see 'typedef A B', we add name 'B' to the set of names
     // A's canonical type maps to.  This is necessary for implementing
     // IsDerivedFrom(x) properly, where x can be the name of the base
     // class or any of its aliases.
     //
     // In general, the is-alias-of (as defined by typedefs) relation
     // is tree-shaped, as you can typedef a type more than once.  For
     // example,
     //
     //   typedef A B;
     //   typedef A C;
     //   typedef C D;
     //   typedef C E;
     //
     // gives you
     //
     //   A
     //   |- B
     //   `- C
     //      |- D
     //      `- E
     //
     // It is wrong to assume that the relation is a chain.  A correct
     // implementation of IsDerivedFrom() needs to recognize that B and
     // E are aliases, even though neither is a typedef of the other.
     // Therefore, we cannot simply walk through one typedef chain to
     // find out whether the type name matches.
     const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
     const Type *CanonicalType =  // root of the typedef tree
         ActiveASTContext->getCanonicalType(TypeNode);
     TypeToUnqualifiedAliases[CanonicalType].insert(
         DeclNode->getName().str());
     return true;
   }

   bool TraverseDecl(Decl *DeclNode);
   bool TraverseStmt(Stmt *StmtNode);
   bool TraverseType(QualType TypeNode);
   bool TraverseTypeLoc(TypeLoc TypeNode);

   // Matches children or descendants of 'Node' with 'BaseMatcher'.
   template <typename T>
   bool memoizedMatchesRecursively(const T &Node,
                                   const UntypedBaseMatcher &BaseMatcher,
                                   BoundNodesTreeBuilder *Builder, int MaxDepth,
                                   TraversalKind Traversal, BindKind Bind) {
     TOOLING_COMPILE_ASSERT((llvm::is_same<T, Decl>::value) ||
                            (llvm::is_same<T, Stmt>::value),
                            type_does_not_support_memoization);
     const UntypedMatchInput input(BaseMatcher.getID(), &Node);
     std::pair<MemoizationMap::iterator, bool> InsertResult
       = ResultCache.insert(std::make_pair(input, MemoizedMatchResult()));
     if (InsertResult.second) {
       BoundNodesTreeBuilder DescendantBoundNodesBuilder;
       InsertResult.first->second.ResultOfMatch =
         matchesRecursively(Node, BaseMatcher, &DescendantBoundNodesBuilder,
                            MaxDepth, Traversal, Bind);
       InsertResult.first->second.Nodes =
         DescendantBoundNodesBuilder.build();
     }
     InsertResult.first->second.Nodes.copyTo(Builder);
     return InsertResult.first->second.ResultOfMatch;
   }

   // Matches children or descendants of 'Node' with 'BaseMatcher'.
   template <typename T>
   bool matchesRecursively(const T &Node, const UntypedBaseMatcher &BaseMatcher,
                           BoundNodesTreeBuilder *Builder, int MaxDepth,
                           TraversalKind Traversal, BindKind Bind) {
     MatchChildASTVisitor Visitor(
       &BaseMatcher, this, Builder, MaxDepth, Traversal, Bind);
     return Visitor.findMatch(Node);
   }

   virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
                                   StringRef BaseName) const;

   // Implements ASTMatchFinder::MatchesChildOf.
   virtual bool matchesChildOf(const Decl &DeclNode,
                               const UntypedBaseMatcher &BaseMatcher,
                               BoundNodesTreeBuilder *Builder,
                               TraversalKind Traversal,
                               BindKind Bind) {
     return matchesRecursively(DeclNode, BaseMatcher, Builder, 1, Traversal,
                               Bind);
   }
   virtual bool matchesChildOf(const Stmt &StmtNode,
                               const UntypedBaseMatcher &BaseMatcher,
                               BoundNodesTreeBuilder *Builder,
                               TraversalKind Traversal,
                               BindKind Bind) {
     return matchesRecursively(StmtNode, BaseMatcher, Builder, 1, Traversal,
                               Bind);
   }

   // Implements ASTMatchFinder::MatchesDescendantOf.
   virtual bool matchesDescendantOf(const Decl &DeclNode,
                                    const UntypedBaseMatcher &BaseMatcher,
                                    BoundNodesTreeBuilder *Builder,
                                    BindKind Bind) {
     return memoizedMatchesRecursively(DeclNode, BaseMatcher, Builder, INT_MAX,
                                       TK_AsIs, Bind);
   }
   virtual bool matchesDescendantOf(const Stmt &StmtNode,
                                    const UntypedBaseMatcher &BaseMatcher,
                                    BoundNodesTreeBuilder *Builder,
                                    BindKind Bind) {
     return memoizedMatchesRecursively(StmtNode, BaseMatcher, Builder, INT_MAX,
                                       TK_AsIs, Bind);
   }

   bool shouldVisitTemplateInstantiations() const { return true; }
   bool shouldVisitImplicitCode() const { return true; }

 private:
   // Implements a BoundNodesTree::Visitor that calls a MatchCallback with
   // the aggregated bound nodes for each match.
   class MatchVisitor : public BoundNodesTree::Visitor {
   public:
     MatchVisitor(ASTContext* Context,
                  MatchFinder::MatchCallback* Callback)
       : Context(Context),
         Callback(Callback) {}

     virtual void visitMatch(const BoundNodes& BoundNodesView) {
       Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
     }

   private:
     ASTContext* Context;
     MatchFinder::MatchCallback* Callback;
   };

   // Returns true if 'TypeNode' is also known by the name 'Name'.  In other
   // words, there is a type (including typedef) with the name 'Name'
   // that is equal to 'TypeNode'.
   bool typeHasAlias(const Type *TypeNode,
                     StringRef Name) const {
     const Type *const CanonicalType =
       ActiveASTContext->getCanonicalType(TypeNode);
     const std::set<std::string> *UnqualifiedAlias =
       find(TypeToUnqualifiedAliases, CanonicalType);
     return UnqualifiedAlias != NULL && UnqualifiedAlias->count(Name) > 0;
   }

   // Matches all registered matchers on the given node and calls the
   // result callback for every node that matches.
   template <typename T>
   void match(const T &node) {
     for (std::vector< std::pair<const UntypedBaseMatcher*,
                       MatchFinder::MatchCallback*> >::const_iterator
              It = Triggers->begin(), End = Triggers->end();
          It != End; ++It) {
       BoundNodesTreeBuilder Builder;
       if (It->first->matches(node, this, &Builder)) {
         BoundNodesTree BoundNodes = Builder.build();
         MatchVisitor Visitor(ActiveASTContext, It->second);
         BoundNodes.visitMatches(&Visitor);
       }
     }
   }

   std::vector< std::pair<const UntypedBaseMatcher*,
                MatchFinder::MatchCallback*> > *const Triggers;
   ASTContext *ActiveASTContext;

   // Maps a canonical type to the names of its typedefs.
   llvm::DenseMap<const Type*, std::set<std::string> >
     TypeToUnqualifiedAliases;

   // Maps (matcher, node) -> the match result for memoization.
   typedef llvm::DenseMap<UntypedMatchInput, MemoizedMatchResult> MemoizationMap;
   MemoizationMap ResultCache;
 };

 // Returns true if the given class is directly or indirectly derived
 // from a base type with the given name.  A class is considered to be
 // also derived from itself.
 bool
 MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
                                     StringRef BaseName) const {
   if (Declaration->getName() == BaseName) {
     return true;
   }
   if (!Declaration->hasDefinition()) {
     return false;
   }
   typedef CXXRecordDecl::base_class_const_iterator BaseIterator;
   for (BaseIterator It = Declaration->bases_begin(),
                     End = Declaration->bases_end(); It != End; ++It) {
     const Type *TypeNode = It->getType().getTypePtr();

     if (typeHasAlias(TypeNode, BaseName))
       return true;

     // Type::getAs<...>() drills through typedefs.
     if (TypeNode->getAs<DependentNameType>() != NULL ||
         TypeNode->getAs<TemplateTypeParmType>() != NULL) {
       // Dependent names and template TypeNode parameters will be matched when
       // the template is instantiated.
       continue;
     }
     CXXRecordDecl *ClassDecl = NULL;
     TemplateSpecializationType const *TemplateType =
       TypeNode->getAs<TemplateSpecializationType>();
     if (TemplateType != NULL) {
       if (TemplateType->getTemplateName().isDependent()) {
         // Dependent template specializations will be matched when the
         // template is instantiated.
         continue;
       }
       // For template specialization types which are specializing a template
       // declaration which is an explicit or partial specialization of another
       // template declaration, getAsCXXRecordDecl() returns the corresponding
       // ClassTemplateSpecializationDecl.
       //
       // For template specialization types which are specializing a template
       // declaration which is neither an explicit nor partial specialization of
       // another template declaration, getAsCXXRecordDecl() returns NULL and
       // we get the CXXRecordDecl of the templated declaration.
       CXXRecordDecl *SpecializationDecl =
         TemplateType->getAsCXXRecordDecl();
       if (SpecializationDecl != NULL) {
         ClassDecl = SpecializationDecl;
       } else {
         ClassDecl = llvm::dyn_cast<CXXRecordDecl>(
             TemplateType->getTemplateName()
                 .getAsTemplateDecl()->getTemplatedDecl());
       }
     } else {
       ClassDecl = TypeNode->getAsCXXRecordDecl();
     }
     assert(ClassDecl != NULL);
     assert(ClassDecl != Declaration);
     if (classIsDerivedFrom(ClassDecl, BaseName)) {
       return true;
     }
   }
   return false;
 }

 bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
   if (DeclNode == NULL) {
     return true;
   }
   match(*DeclNode);
   return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
 }

 bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
   if (StmtNode == NULL) {
     return true;
   }
   match(*StmtNode);
   return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
 }

 bool MatchASTVisitor::TraverseType(QualType TypeNode) {
   match(TypeNode);
   return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
 }

 bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLoc) {
   return RecursiveASTVisitor<MatchASTVisitor>::
       TraverseType(TypeLoc.getType());
 }

 class MatchASTConsumer : public ASTConsumer {
 public:
   MatchASTConsumer(std::vector< std::pair<const UntypedBaseMatcher*,
                                 MatchFinder::MatchCallback*> > *Triggers,
                    MatchFinder::ParsingDoneTestCallback *ParsingDone)
       : Visitor(Triggers),
         ParsingDone(ParsingDone) {}

 private:
   virtual void HandleTranslationUnit(ASTContext &Context) {
     if (ParsingDone != NULL) {
       ParsingDone->run();
     }
     Visitor.set_active_ast_context(&Context);
     Visitor.TraverseDecl(Context.getTranslationUnitDecl());
     Visitor.set_active_ast_context(NULL);
   }

   MatchASTVisitor Visitor;
   MatchFinder::ParsingDoneTestCallback *ParsingDone;
 };

 } // end namespace
 } // end namespace internal

 MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
                                       ASTContext *Context)
   : Nodes(Nodes), Context(Context),
     SourceManager(&Context->getSourceManager()) {}

 MatchFinder::MatchCallback::~MatchCallback() {}
 MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}

 MatchFinder::MatchFinder() : ParsingDone(NULL) {}

 MatchFinder::~MatchFinder() {
   for (std::vector< std::pair<const internal::UntypedBaseMatcher*,
                     MatchFinder::MatchCallback*> >::const_iterator
            It = Triggers.begin(), End = Triggers.end();
        It != End; ++It) {
     delete It->first;
   }
 }

 void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
                              MatchCallback *Action) {
   Triggers.push_back(std::make_pair(
     new internal::TypedBaseMatcher<Decl>(NodeMatch), Action));
 }

 void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
                              MatchCallback *Action) {
   Triggers.push_back(std::make_pair(
     new internal::TypedBaseMatcher<QualType>(NodeMatch), Action));
 }

 void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
                              MatchCallback *Action) {
   Triggers.push_back(std::make_pair(
     new internal::TypedBaseMatcher<Stmt>(NodeMatch), Action));
 }

 ASTConsumer *MatchFinder::newASTConsumer() {
   return new internal::MatchASTConsumer(&Triggers, ParsingDone);
 }

 void MatchFinder::registerTestCallbackAfterParsing(
     MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
   ParsingDone = NewParsingDone;
 }

 } // end namespace ast_matchers
 } // end namespace clang
	//===--- ASTMatchFinder.cpp - Structural query framework ------------------===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// Implements an algorithm to efficiently search for matches on AST nodes.
	// Uses memoization to support recursive matches like HasDescendant.
	//
	// The general idea is to visit all AST nodes with a RecursiveASTVisitor,
	// calling the Matches(...) method of each matcher we are running on each
	// AST node. The matcher can recurse via the ASTMatchFinder interface.
	//
	//===----------------------------------------------------------------------===//

	#include "clang/ASTMatchers/ASTMatchFinder.h"
	#include "clang/AST/ASTConsumer.h"
	#include "clang/AST/ASTContext.h"
	#include "clang/AST/RecursiveASTVisitor.h"
	#include <set>

	namespace clang {
	namespace ast_matchers {
	namespace internal {
	namespace {

	// Returns the value that 'AMap' maps 'Key' to, or NULL if 'Key' is
	// not in 'AMap'.
	template <typename Map>
	static const typename Map::mapped_type *
	find(const Map &AMap, const typename Map::key_type &Key) {
	typename Map::const_iterator It = AMap.find(Key);
	return It == AMap.end() ? NULL : &It->second;
	}

	// We use memoization to avoid running the same matcher on the same
	// AST node twice. This pair is the key for looking up match
	// result. It consists of an ID of the MatcherInterface (for
	// identifying the matcher) and a pointer to the AST node.
	typedef std::pair<uint64_t, const void*> UntypedMatchInput;

	// Used to store the result of a match and possibly bound nodes.
	struct MemoizedMatchResult {
	bool ResultOfMatch;
	BoundNodesTree Nodes;
	};

	// A RecursiveASTVisitor that traverses all children or all descendants of
	// a node.
	class MatchChildASTVisitor
	: public RecursiveASTVisitor<MatchChildASTVisitor> {
	public:
	typedef RecursiveASTVisitor<MatchChildASTVisitor> VisitorBase;

	// Creates an AST visitor that matches 'matcher' on all children or
	// descendants of a traversed node. max_depth is the maximum depth
	// to traverse: use 1 for matching the children and INT_MAX for
	// matching the descendants.
	MatchChildASTVisitor(const UntypedBaseMatcher *BaseMatcher,
	ASTMatchFinder *Finder,
	BoundNodesTreeBuilder *Builder,
	int MaxDepth,
	ASTMatchFinder::TraversalKind Traversal,
	ASTMatchFinder::BindKind Bind)
	: BaseMatcher(BaseMatcher),
	Finder(Finder),
	Builder(Builder),
	CurrentDepth(-1),
	MaxDepth(MaxDepth),
	Traversal(Traversal),
	Bind(Bind),
	Matches(false) {}

	// Returns true if a match is found in the subtree rooted at the
	// given AST node. This is done via a set of mutually recursive
	// functions. Here's how the recursion is done (the *wildcard can
	// actually be Decl, Stmt, or Type):
	//
	// - Traverse(node) calls BaseTraverse(node) when it needs
	// to visit the descendants of node.
	// - BaseTraverse(node) then calls (via VisitorBase::Traverse*(node))
	// Traverse*(c) for each child c of 'node'.
	// - Traverse*(c) in turn calls Traverse(c), completing the
	// recursion.
	template <typename T>
	bool findMatch(const T &Node) {
	reset();
	traverse(Node);
	return Matches;
	}

	// The following are overriding methods from the base visitor class.
	// They are public only to allow CRTP to work. They are not part
	// of the public API of this class.
	bool TraverseDecl(Decl *DeclNode) {
	return (DeclNode == NULL) \|\| traverse(*DeclNode);
	}
	bool TraverseStmt(Stmt *StmtNode) {
	const Stmt *StmtToTraverse = StmtNode;
	if (Traversal ==
	ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses) {
	const Expr *ExprNode = dyn_cast_or_null<Expr>(StmtNode);
	if (ExprNode != NULL) {
	StmtToTraverse = ExprNode->IgnoreParenImpCasts();
	}
	}
	return (StmtToTraverse == NULL) \|\| traverse(*StmtToTraverse);
	}
	bool TraverseType(QualType TypeNode) {
	return traverse(TypeNode);
	}

	bool shouldVisitTemplateInstantiations() const { return true; }
	bool shouldVisitImplicitCode() const { return true; }

	private:
	// Used for updating the depth during traversal.
	struct ScopedIncrement {
	explicit ScopedIncrement(int Depth) : Depth(Depth) { ++(Depth); }
	~ScopedIncrement() { --(*Depth); }

	private:
	int *Depth;
	};

	// Resets the state of this object.
	void reset() {
	Matches = false;
	CurrentDepth = -1;
	}

	// Forwards the call to the corresponding Traverse*() method in the
	// base visitor class.
	bool baseTraverse(const Decl &DeclNode) {
	return VisitorBase::TraverseDecl(const_cast<Decl*>(&DeclNode));
	}
	bool baseTraverse(const Stmt &StmtNode) {
	return VisitorBase::TraverseStmt(const_cast<Stmt*>(&StmtNode));
	}
	bool baseTraverse(QualType TypeNode) {
	return VisitorBase::TraverseType(TypeNode);
	}

	// Traverses the subtree rooted at 'node'; returns true if the
	// traversal should continue after this function returns; also sets
	// matched_ to true if a match is found during the traversal.
	template <typename T>
	bool traverse(const T &Node) {
	TOOLING_COMPILE_ASSERT(IsBaseType<T>::value,
	traverse_can_only_be_instantiated_with_base_type);
	ScopedIncrement ScopedDepth(&CurrentDepth);
	if (CurrentDepth == 0) {
	// We don't want to match the root node, so just recurse.
	return baseTraverse(Node);
	}
	if (Bind != ASTMatchFinder::BK_All) {
	if (BaseMatcher->matches(Node, Finder, Builder)) {
	Matches = true;
	return false; // Abort as soon as a match is found.
	}
	if (CurrentDepth < MaxDepth) {
	// The current node doesn't match, and we haven't reached the
	// maximum depth yet, so recurse.
	return baseTraverse(Node);
	}
	// The current node doesn't match, and we have reached the
	// maximum depth, so don't recurse (but continue the traversal
	// such that other nodes at the current level can be visited).
	return true;
	} else {
	BoundNodesTreeBuilder RecursiveBuilder;
	if (BaseMatcher->matches(Node, Finder, &RecursiveBuilder)) {
	// After the first match the matcher succeeds.
	Matches = true;
	Builder->addMatch(RecursiveBuilder.build());
	}
	if (CurrentDepth < MaxDepth) {
	baseTraverse(Node);
	}
	// In kBindAll mode we always search for more matches.
	return true;
	}
	}

	const UntypedBaseMatcher *const BaseMatcher;
	ASTMatchFinder *const Finder;
	BoundNodesTreeBuilder *const Builder;
	int CurrentDepth;
	const int MaxDepth;
	const ASTMatchFinder::TraversalKind Traversal;
	const ASTMatchFinder::BindKind Bind;
	bool Matches;
	};

	// Controls the outermost traversal of the AST and allows to match multiple
	// matchers.
	class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>,
	public ASTMatchFinder {
	public:
	MatchASTVisitor(std::vector< std::pair<const UntypedBaseMatcher*,
	MatchFinder::MatchCallback> > Triggers)
	: Triggers(Triggers),
	ActiveASTContext(NULL) {
	}

	void set_active_ast_context(ASTContext *NewActiveASTContext) {
	ActiveASTContext = NewActiveASTContext;
	}

	// The following Visit() and Traverse() functions "override"
	// methods in RecursiveASTVisitor.

	bool VisitTypedefDecl(TypedefDecl *DeclNode) {
	// When we see 'typedef A B', we add name 'B' to the set of names
	// A's canonical type maps to. This is necessary for implementing
	// IsDerivedFrom(x) properly, where x can be the name of the base
	// class or any of its aliases.
	//
	// In general, the is-alias-of (as defined by typedefs) relation
	// is tree-shaped, as you can typedef a type more than once. For
	// example,
	//
	// typedef A B;
	// typedef A C;
	// typedef C D;
	// typedef C E;
	//
	// gives you
	//
	// A
	// \|- B
	// `- C
	// \|- D
	// `- E
	//
	// It is wrong to assume that the relation is a chain. A correct
	// implementation of IsDerivedFrom() needs to recognize that B and
	// E are aliases, even though neither is a typedef of the other.
	// Therefore, we cannot simply walk through one typedef chain to
	// find out whether the type name matches.
	const Type *TypeNode = DeclNode->getUnderlyingType().getTypePtr();
	const Type *CanonicalType = // root of the typedef tree
	ActiveASTContext->getCanonicalType(TypeNode);
	TypeToUnqualifiedAliases[CanonicalType].insert(
	DeclNode->getName().str());
	return true;
	}

	bool TraverseDecl(Decl *DeclNode);
	bool TraverseStmt(Stmt *StmtNode);
	bool TraverseType(QualType TypeNode);
	bool TraverseTypeLoc(TypeLoc TypeNode);

	// Matches children or descendants of 'Node' with 'BaseMatcher'.
	template <typename T>
	bool memoizedMatchesRecursively(const T &Node,
	const UntypedBaseMatcher &BaseMatcher,
	BoundNodesTreeBuilder *Builder, int MaxDepth,
	TraversalKind Traversal, BindKind Bind) {
	TOOLING_COMPILE_ASSERT((llvm::is_same<T, Decl>::value) \|\|
	(llvm::is_same<T, Stmt>::value),
	type_does_not_support_memoization);
	const UntypedMatchInput input(BaseMatcher.getID(), &Node);
	std::pair<MemoizationMap::iterator, bool> InsertResult
	= ResultCache.insert(std::make_pair(input, MemoizedMatchResult()));
	if (InsertResult.second) {
	BoundNodesTreeBuilder DescendantBoundNodesBuilder;
	InsertResult.first->second.ResultOfMatch =
	matchesRecursively(Node, BaseMatcher, &DescendantBoundNodesBuilder,
	MaxDepth, Traversal, Bind);
	InsertResult.first->second.Nodes =
	DescendantBoundNodesBuilder.build();
	}
	InsertResult.first->second.Nodes.copyTo(Builder);
	return InsertResult.first->second.ResultOfMatch;
	}

	// Matches children or descendants of 'Node' with 'BaseMatcher'.
	template <typename T>
	bool matchesRecursively(const T &Node, const UntypedBaseMatcher &BaseMatcher,
	BoundNodesTreeBuilder *Builder, int MaxDepth,
	TraversalKind Traversal, BindKind Bind) {
	MatchChildASTVisitor Visitor(
	&BaseMatcher, this, Builder, MaxDepth, Traversal, Bind);
	return Visitor.findMatch(Node);
	}

	virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
	StringRef BaseName) const;

	// Implements ASTMatchFinder::MatchesChildOf.
	virtual bool matchesChildOf(const Decl &DeclNode,
	const UntypedBaseMatcher &BaseMatcher,
	BoundNodesTreeBuilder *Builder,
	TraversalKind Traversal,
	BindKind Bind) {
	return matchesRecursively(DeclNode, BaseMatcher, Builder, 1, Traversal,
	Bind);
	}
	virtual bool matchesChildOf(const Stmt &StmtNode,
	const UntypedBaseMatcher &BaseMatcher,
	BoundNodesTreeBuilder *Builder,
	TraversalKind Traversal,
	BindKind Bind) {
	return matchesRecursively(StmtNode, BaseMatcher, Builder, 1, Traversal,
	Bind);
	}

	// Implements ASTMatchFinder::MatchesDescendantOf.
	virtual bool matchesDescendantOf(const Decl &DeclNode,
	const UntypedBaseMatcher &BaseMatcher,
	BoundNodesTreeBuilder *Builder,
	BindKind Bind) {
	return memoizedMatchesRecursively(DeclNode, BaseMatcher, Builder, INT_MAX,
	TK_AsIs, Bind);
	}
	virtual bool matchesDescendantOf(const Stmt &StmtNode,
	const UntypedBaseMatcher &BaseMatcher,
	BoundNodesTreeBuilder *Builder,
	BindKind Bind) {
	return memoizedMatchesRecursively(StmtNode, BaseMatcher, Builder, INT_MAX,
	TK_AsIs, Bind);
	}

	bool shouldVisitTemplateInstantiations() const { return true; }
	bool shouldVisitImplicitCode() const { return true; }

	private:
	// Implements a BoundNodesTree::Visitor that calls a MatchCallback with
	// the aggregated bound nodes for each match.
	class MatchVisitor : public BoundNodesTree::Visitor {
	public:
	MatchVisitor(ASTContext* Context,
	MatchFinder::MatchCallback* Callback)
	: Context(Context),
	Callback(Callback) {}

	virtual void visitMatch(const BoundNodes& BoundNodesView) {
	Callback->run(MatchFinder::MatchResult(BoundNodesView, Context));
	}

	private:
	ASTContext* Context;
	MatchFinder::MatchCallback* Callback;
	};

	// Returns true if 'TypeNode' is also known by the name 'Name'. In other
	// words, there is a type (including typedef) with the name 'Name'
	// that is equal to 'TypeNode'.
	bool typeHasAlias(const Type *TypeNode,
	StringRef Name) const {
	const Type *const CanonicalType =
	ActiveASTContext->getCanonicalType(TypeNode);
	const std::set<std::string> *UnqualifiedAlias =
	find(TypeToUnqualifiedAliases, CanonicalType);
	return UnqualifiedAlias != NULL && UnqualifiedAlias->count(Name) > 0;
	}

	// Matches all registered matchers on the given node and calls the
	// result callback for every node that matches.
	template <typename T>
	void match(const T &node) {
	for (std::vector< std::pair<const UntypedBaseMatcher*,
	MatchFinder::MatchCallback*> >::const_iterator
	It = Triggers->begin(), End = Triggers->end();
	It != End; ++It) {
	BoundNodesTreeBuilder Builder;
	if (It->first->matches(node, this, &Builder)) {
	BoundNodesTree BoundNodes = Builder.build();
	MatchVisitor Visitor(ActiveASTContext, It->second);
	BoundNodes.visitMatches(&Visitor);
	}
	}
	}

	std::vector< std::pair<const UntypedBaseMatcher*,
	MatchFinder::MatchCallback> > const Triggers;
	ASTContext *ActiveASTContext;

	// Maps a canonical type to the names of its typedefs.
	llvm::DenseMap<const Type*, std::set<std::string> >
	TypeToUnqualifiedAliases;

	// Maps (matcher, node) -> the match result for memoization.
	typedef llvm::DenseMap<UntypedMatchInput, MemoizedMatchResult> MemoizationMap;
	MemoizationMap ResultCache;
	};

	// Returns true if the given class is directly or indirectly derived
	// from a base type with the given name. A class is considered to be
	// also derived from itself.
	bool
	MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
	StringRef BaseName) const {
	if (Declaration->getName() == BaseName) {
	return true;
	}
	if (!Declaration->hasDefinition()) {
	return false;
	}
	typedef CXXRecordDecl::base_class_const_iterator BaseIterator;
	for (BaseIterator It = Declaration->bases_begin(),
	End = Declaration->bases_end(); It != End; ++It) {
	const Type *TypeNode = It->getType().getTypePtr();

	if (typeHasAlias(TypeNode, BaseName))
	return true;

	// Type::getAs<...>() drills through typedefs.
	if (TypeNode->getAs<DependentNameType>() != NULL \|\|
	TypeNode->getAs<TemplateTypeParmType>() != NULL) {
	// Dependent names and template TypeNode parameters will be matched when
	// the template is instantiated.
	continue;
	}
	CXXRecordDecl *ClassDecl = NULL;
	TemplateSpecializationType const *TemplateType =
	TypeNode->getAs<TemplateSpecializationType>();
	if (TemplateType != NULL) {
	if (TemplateType->getTemplateName().isDependent()) {
	// Dependent template specializations will be matched when the
	// template is instantiated.
	continue;
	}
	// For template specialization types which are specializing a template
	// declaration which is an explicit or partial specialization of another
	// template declaration, getAsCXXRecordDecl() returns the corresponding
	// ClassTemplateSpecializationDecl.
	//
	// For template specialization types which are specializing a template
	// declaration which is neither an explicit nor partial specialization of
	// another template declaration, getAsCXXRecordDecl() returns NULL and
	// we get the CXXRecordDecl of the templated declaration.
	CXXRecordDecl *SpecializationDecl =
	TemplateType->getAsCXXRecordDecl();
	if (SpecializationDecl != NULL) {
	ClassDecl = SpecializationDecl;
	} else {
	ClassDecl = llvm::dyn_cast<CXXRecordDecl>(
	TemplateType->getTemplateName()
	.getAsTemplateDecl()->getTemplatedDecl());
	}
	} else {
	ClassDecl = TypeNode->getAsCXXRecordDecl();
	}
	assert(ClassDecl != NULL);
	assert(ClassDecl != Declaration);
	if (classIsDerivedFrom(ClassDecl, BaseName)) {
	return true;
	}
	}
	return false;
	}

	bool MatchASTVisitor::TraverseDecl(Decl *DeclNode) {
	if (DeclNode == NULL) {
	return true;
	}
	match(*DeclNode);
	return RecursiveASTVisitor<MatchASTVisitor>::TraverseDecl(DeclNode);
	}

	bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode) {
	if (StmtNode == NULL) {
	return true;
	}
	match(*StmtNode);
	return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode);
	}

	bool MatchASTVisitor::TraverseType(QualType TypeNode) {
	match(TypeNode);
	return RecursiveASTVisitor<MatchASTVisitor>::TraverseType(TypeNode);
	}

	bool MatchASTVisitor::TraverseTypeLoc(TypeLoc TypeLoc) {
	return RecursiveASTVisitor<MatchASTVisitor>::
	TraverseType(TypeLoc.getType());
	}

	class MatchASTConsumer : public ASTConsumer {
	public:
	MatchASTConsumer(std::vector< std::pair<const UntypedBaseMatcher*,
	MatchFinder::MatchCallback> > Triggers,
	MatchFinder::ParsingDoneTestCallback *ParsingDone)
	: Visitor(Triggers),
	ParsingDone(ParsingDone) {}

	private:
	virtual void HandleTranslationUnit(ASTContext &Context) {
	if (ParsingDone != NULL) {
	ParsingDone->run();
	}
	Visitor.set_active_ast_context(&Context);
	Visitor.TraverseDecl(Context.getTranslationUnitDecl());
	Visitor.set_active_ast_context(NULL);
	}

	MatchASTVisitor Visitor;
	MatchFinder::ParsingDoneTestCallback *ParsingDone;
	};

	} // end namespace
	} // end namespace internal

	MatchFinder::MatchResult::MatchResult(const BoundNodes &Nodes,
	ASTContext *Context)
	: Nodes(Nodes), Context(Context),
	SourceManager(&Context->getSourceManager()) {}

	MatchFinder::MatchCallback::~MatchCallback() {}
	MatchFinder::ParsingDoneTestCallback::~ParsingDoneTestCallback() {}

	MatchFinder::MatchFinder() : ParsingDone(NULL) {}

	MatchFinder::~MatchFinder() {
	for (std::vector< std::pair<const internal::UntypedBaseMatcher*,
	MatchFinder::MatchCallback*> >::const_iterator
	It = Triggers.begin(), End = Triggers.end();
	It != End; ++It) {
	delete It->first;
	}
	}

	void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
	MatchCallback *Action) {
	Triggers.push_back(std::make_pair(
	new internal::TypedBaseMatcher<Decl>(NodeMatch), Action));
	}

	void MatchFinder::addMatcher(const TypeMatcher &NodeMatch,
	MatchCallback *Action) {
	Triggers.push_back(std::make_pair(
	new internal::TypedBaseMatcher<QualType>(NodeMatch), Action));
	}

	void MatchFinder::addMatcher(const StatementMatcher &NodeMatch,
	MatchCallback *Action) {
	Triggers.push_back(std::make_pair(
	new internal::TypedBaseMatcher<Stmt>(NodeMatch), Action));
	}

	ASTConsumer *MatchFinder::newASTConsumer() {
	return new internal::MatchASTConsumer(&Triggers, ParsingDone);
	}

	void MatchFinder::registerTestCallbackAfterParsing(
	MatchFinder::ParsingDoneTestCallback *NewParsingDone) {
	ParsingDone = NewParsingDone;
	}

	} // end namespace ast_matchers
	} // end namespace clang