contrib/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchersInternal.h

   1 //===--- ASTMatchersInternal.h - Structural query framework -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  Implements the base layer of the matcher framework.
  11 //
  12 //  Matchers are methods that return a Matcher<T> which provides a method
  13 //  Matches(...) which is a predicate on an AST node. The Matches method's
  14 //  parameters define the context of the match, which allows matchers to recurse
  15 //  or store the current node as bound to a specific string, so that it can be
  16 //  retrieved later.
  17 //
  18 //  In general, matchers have two parts:
  19 //  1. A function Matcher<T> MatcherName(<arguments>) which returns a Matcher<T>
  20 //     based on the arguments and optionally on template type deduction based
  21 //     on the arguments. Matcher<T>s form an implicit reverse hierarchy
  22 //     to clang's AST class hierarchy, meaning that you can use a Matcher<Base>
  23 //     everywhere a Matcher<Derived> is required.
  24 //  2. An implementation of a class derived from MatcherInterface<T>.
  25 //
  26 //  The matcher functions are defined in ASTMatchers.h. To make it possible
  27 //  to implement both the matcher function and the implementation of the matcher
  28 //  interface in one place, ASTMatcherMacros.h defines macros that allow
  29 //  implementing a matcher in a single place.
  30 //
  31 //  This file contains the base classes needed to construct the actual matchers.
  32 //
  33 //===----------------------------------------------------------------------===//
  34
  35 #ifndef LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_INTERNAL_H
  36 #define LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_INTERNAL_H
  37
  38 #include "clang/AST/Decl.h"
  39 #include "clang/AST/DeclCXX.h"
  40 #include "clang/AST/ExprCXX.h"
  41 #include "clang/AST/Stmt.h"
  42 #include "clang/AST/StmtCXX.h"
  43 #include "clang/AST/Type.h"
  44 #include "clang/ASTMatchers/ASTTypeTraits.h"
  45 #include "llvm/ADT/VariadicFunction.h"
  46 #include "llvm/Support/type_traits.h"
  47 #include <map>
  48 #include <string>
  49 #include <vector>
  50
  51 namespace clang {
  52 namespace ast_matchers {
  53
  54 /// FIXME: Move into the llvm support library.
  55 template <bool> struct CompileAssert {};
  56 #define TOOLING_COMPILE_ASSERT(Expr, Msg) \
  57   typedef CompileAssert<(bool(Expr))> Msg[bool(Expr) ? 1 : -1]
  58
  59 class BoundNodes;
  60
  61 namespace internal {
  62
  63 class BoundNodesTreeBuilder;
  64 /// \brief Internal version of BoundNodes. Holds all the bound nodes.
  65 class BoundNodesMap {
  66 public:
  67   /// \brief Adds \c Node to the map with key \c ID.
  68   ///
  69   /// The node's base type should be in NodeBaseType or it will be unaccessible.
  70   template <typename T>
  71   void addNode(StringRef ID, const T* Node) {
  72     NodeMap[ID] = ast_type_traits::DynTypedNode::create(*Node);
  73   }
  74   void addNode(StringRef ID, ast_type_traits::DynTypedNode Node) {
  75     NodeMap[ID] = Node;
  76   }
  77
  78   /// \brief Returns the AST node bound to \c ID.
  79   ///
  80   /// Returns NULL if there was no node bound to \c ID or if there is a node but
  81   /// it cannot be converted to the specified type.
  82   template <typename T>
  83   const T *getNodeAs(StringRef ID) const {
  84     IDToNodeMap::const_iterator It = NodeMap.find(ID);
  85     if (It == NodeMap.end()) {
  86       return NULL;
  87     }
  88     return It->second.get<T>();
  89   }
  90
  91   /// \brief Copies all ID/Node pairs to BoundNodesTreeBuilder \c Builder.
  92   void copyTo(BoundNodesTreeBuilder *Builder) const;
  93
  94   /// \brief Copies all ID/Node pairs to BoundNodesMap \c Other.
  95   void copyTo(BoundNodesMap *Other) const;
  96
  97 private:
  98   /// \brief A map from IDs to the bound nodes.
  99   typedef std::map<std::string, ast_type_traits::DynTypedNode> IDToNodeMap;
 100
 101   IDToNodeMap NodeMap;
 102 };
 103
 104 /// \brief A tree of bound nodes in match results.
 105 ///
 106 /// If a match can contain multiple matches on the same node with different
 107 /// matching subexpressions, BoundNodesTree contains a branch for each of
 108 /// those matching subexpressions.
 109 ///
 110 /// BoundNodesTree's are created during the matching process; when a match
 111 /// is found, we iterate over the tree and create a BoundNodes object containing
 112 /// the union of all bound nodes on the path from the root to a each leaf.
 113 class BoundNodesTree {
 114 public:
 115   /// \brief A visitor interface to visit all BoundNodes results for a
 116   /// BoundNodesTree.
 117   class Visitor {
 118   public:
 119     virtual ~Visitor() {}
 120
 121     /// \brief Called multiple times during a single call to VisitMatches(...).
 122     ///
 123     /// 'BoundNodesView' contains the bound nodes for a single match.
 124     virtual void visitMatch(const BoundNodes& BoundNodesView) = 0;
 125   };
 126
 127   BoundNodesTree();
 128
 129   /// \brief Create a BoundNodesTree from pre-filled maps of bindings.
 130   BoundNodesTree(const BoundNodesMap& Bindings,
 131                  const std::vector<BoundNodesTree> RecursiveBindings);
 132
 133   /// \brief Adds all bound nodes to \c Builder.
 134   void copyTo(BoundNodesTreeBuilder* Builder) const;
 135
 136   /// \brief Visits all matches that this BoundNodesTree represents.
 137   ///
 138   /// The ownership of 'ResultVisitor' remains at the caller.
 139   void visitMatches(Visitor* ResultVisitor);
 140
 141 private:
 142   void visitMatchesRecursively(
 143       Visitor* ResultVistior,
 144       const BoundNodesMap& AggregatedBindings);
 145
 146   // FIXME: Find out whether we want to use different data structures here -
 147   // first benchmarks indicate that it doesn't matter though.
 148
 149   BoundNodesMap Bindings;
 150
 151   std::vector<BoundNodesTree> RecursiveBindings;
 152 };
 153
 154 /// \brief Creates BoundNodesTree objects.
 155 ///
 156 /// The tree builder is used during the matching process to insert the bound
 157 /// nodes from the Id matcher.
 158 class BoundNodesTreeBuilder {
 159 public:
 160   BoundNodesTreeBuilder();
 161
 162   /// \brief Add a binding from an id to a node.
 163   template <typename T>
 164   void setBinding(const std::string &Id, const T *Node) {
 165     Bindings.addNode(Id, Node);
 166   }
 167   void setBinding(const std::string &Id, ast_type_traits::DynTypedNode Node) {
 168     Bindings.addNode(Id, Node);
 169   }
 170
 171   /// \brief Adds a branch in the tree.
 172   void addMatch(const BoundNodesTree& Bindings);
 173
 174   /// \brief Returns a BoundNodes object containing all current bindings.
 175   BoundNodesTree build() const;
 176
 177 private:
 178   BoundNodesTreeBuilder(const BoundNodesTreeBuilder &) LLVM_DELETED_FUNCTION;
 179   void operator=(const BoundNodesTreeBuilder &) LLVM_DELETED_FUNCTION;
 180
 181   BoundNodesMap Bindings;
 182
 183   std::vector<BoundNodesTree> RecursiveBindings;
 184 };
 185
 186 class ASTMatchFinder;
 187
 188 /// \brief Generic interface for matchers on an AST node of type T.
 189 ///
 190 /// Implement this if your matcher may need to inspect the children or
 191 /// descendants of the node or bind matched nodes to names. If you are
 192 /// writing a simple matcher that only inspects properties of the
 193 /// current node and doesn't care about its children or descendants,
 194 /// implement SingleNodeMatcherInterface instead.
 195 template <typename T>
 196 class MatcherInterface : public llvm::RefCountedBaseVPTR {
 197 public:
 198   virtual ~MatcherInterface() {}
 199
 200   /// \brief Returns true if 'Node' can be matched.
 201   ///
 202   /// May bind 'Node' to an ID via 'Builder', or recurse into
 203   /// the AST via 'Finder'.
 204   virtual bool matches(const T &Node,
 205                        ASTMatchFinder *Finder,
 206                        BoundNodesTreeBuilder *Builder) const = 0;
 207 };
 208
 209 /// \brief Interface for matchers that only evaluate properties on a single
 210 /// node.
 211 template <typename T>
 212 class SingleNodeMatcherInterface : public MatcherInterface<T> {
 213 public:
 214   /// \brief Returns true if the matcher matches the provided node.
 215   ///
 216   /// A subclass must implement this instead of Matches().
 217   virtual bool matchesNode(const T &Node) const = 0;
 218
 219 private:
 220   /// Implements MatcherInterface::Matches.
 221   virtual bool matches(const T &Node,
 222                        ASTMatchFinder * /* Finder */,
 223                        BoundNodesTreeBuilder * /*  Builder */) const {
 224     return matchesNode(Node);
 225   }
 226 };
 227
 228 /// \brief Base class for all matchers that works on a \c DynTypedNode.
 229 ///
 230 /// Matcher implementations will check whether the \c DynTypedNode is
 231 /// convertible into the respecitve types and then do the actual match
 232 /// on the actual node, or return false if it is not convertible.
 233 class DynTypedMatcher {
 234 public:
 235   virtual ~DynTypedMatcher() {}
 236
 237   /// \brief Returns true if the matcher matches the given \c DynNode.
 238   virtual bool matches(const ast_type_traits::DynTypedNode DynNode,
 239                        ASTMatchFinder *Finder,
 240                        BoundNodesTreeBuilder *Builder) const = 0;
 241
 242   /// \brief Returns a unique ID for the matcher.
 243   virtual uint64_t getID() const = 0;
 244 };
 245
 246 /// \brief Wrapper of a MatcherInterface<T> *that allows copying.
 247 ///
 248 /// A Matcher<Base> can be used anywhere a Matcher<Derived> is
 249 /// required. This establishes an is-a relationship which is reverse
 250 /// to the AST hierarchy. In other words, Matcher<T> is contravariant
 251 /// with respect to T. The relationship is built via a type conversion
 252 /// operator rather than a type hierarchy to be able to templatize the
 253 /// type hierarchy instead of spelling it out.
 254 template <typename T>
 255 class Matcher : public DynTypedMatcher {
 256 public:
 257   /// \brief Takes ownership of the provided implementation pointer.
 258   explicit Matcher(MatcherInterface<T> *Implementation)
 259       : Implementation(Implementation) {}
 260
 261   /// \brief Implicitly converts \c Other to a Matcher<T>.
 262   ///
 263   /// Requires \c T to be derived from \c From.
 264   template <typename From>
 265   Matcher(const Matcher<From> &Other,
 266           typename llvm::enable_if_c<
 267             llvm::is_base_of<From, T>::value &&
 268             !llvm::is_same<From, T>::value >::type* = 0)
 269       : Implementation(new ImplicitCastMatcher<From>(Other)) {}
 270
 271   /// \brief Implicitly converts \c Matcher<Type> to \c Matcher<QualType>.
 272   ///
 273   /// The resulting matcher is not strict, i.e. ignores qualifiers.
 274   template <typename TypeT>
 275   Matcher(const Matcher<TypeT> &Other,
 276           typename llvm::enable_if_c<
 277             llvm::is_same<T, QualType>::value &&
 278             llvm::is_same<TypeT, Type>::value >::type* = 0)
 279       : Implementation(new TypeToQualType<TypeT>(Other)) {}
 280
 281   /// \brief Forwards the call to the underlying MatcherInterface<T> pointer.
 282   bool matches(const T &Node,
 283                ASTMatchFinder *Finder,
 284                BoundNodesTreeBuilder *Builder) const {
 285     return Implementation->matches(Node, Finder, Builder);
 286   }
 287
 288   /// \brief Returns an ID that uniquely identifies the matcher.
 289   uint64_t getID() const {
 290     /// FIXME: Document the requirements this imposes on matcher
 291     /// implementations (no new() implementation_ during a Matches()).
 292     return reinterpret_cast<uint64_t>(Implementation.getPtr());
 293   }
 294
 295   /// \brief Returns whether the matcher matches on the given \c DynNode.
 296   virtual bool matches(const ast_type_traits::DynTypedNode DynNode,
 297                        ASTMatchFinder *Finder,
 298                        BoundNodesTreeBuilder *Builder) const {
 299     const T *Node = DynNode.get<T>();
 300     if (!Node) return false;
 301     return matches(*Node, Finder, Builder);
 302   }
 303
 304   /// \brief Allows the conversion of a \c Matcher<Type> to a \c
 305   /// Matcher<QualType>.
 306   ///
 307   /// Depending on the constructor argument, the matcher is either strict, i.e.
 308   /// does only matches in the absence of qualifiers, or not, i.e. simply
 309   /// ignores any qualifiers.
 310   template <typename TypeT>
 311   class TypeToQualType : public MatcherInterface<QualType> {
 312    public:
 313     TypeToQualType(const Matcher<TypeT> &InnerMatcher)
 314         : InnerMatcher(InnerMatcher) {}
 315
 316     virtual bool matches(const QualType &Node,
 317                          ASTMatchFinder *Finder,
 318                          BoundNodesTreeBuilder *Builder) const {
 319       if (Node.isNull())
 320         return false;
 321       return InnerMatcher.matches(*Node, Finder, Builder);
 322     }
 323    private:
 324     const Matcher<TypeT> InnerMatcher;
 325   };
 326
 327 private:
 328   /// \brief Allows conversion from Matcher<Base> to Matcher<T> if T
 329   /// is derived from Base.
 330   template <typename Base>
 331   class ImplicitCastMatcher : public MatcherInterface<T> {
 332   public:
 333     explicit ImplicitCastMatcher(const Matcher<Base> &From)
 334         : From(From) {}
 335
 336     virtual bool matches(const T &Node,
 337                          ASTMatchFinder *Finder,
 338                          BoundNodesTreeBuilder *Builder) const {
 339       return From.matches(Node, Finder, Builder);
 340     }
 341
 342   private:
 343     const Matcher<Base> From;
 344   };
 345
 346   llvm::IntrusiveRefCntPtr< MatcherInterface<T> > Implementation;
 347 };  // class Matcher
 348
 349 /// \brief A convenient helper for creating a Matcher<T> without specifying
 350 /// the template type argument.
 351 template <typename T>
 352 inline Matcher<T> makeMatcher(MatcherInterface<T> *Implementation) {
 353   return Matcher<T>(Implementation);
 354 }
 355
 356 /// \brief Matches declarations for QualType and CallExpr.
 357 ///
 358 /// Type argument DeclMatcherT is required by PolymorphicMatcherWithParam1 but
 359 /// not actually used.
 360 template <typename T, typename DeclMatcherT>
 361 class HasDeclarationMatcher : public MatcherInterface<T> {
 362   TOOLING_COMPILE_ASSERT((llvm::is_same< DeclMatcherT,
 363                                          Matcher<Decl> >::value),
 364                           instantiated_with_wrong_types);
 365 public:
 366   explicit HasDeclarationMatcher(const Matcher<Decl> &InnerMatcher)
 367       : InnerMatcher(InnerMatcher) {}
 368
 369   virtual bool matches(const T &Node,
 370                        ASTMatchFinder *Finder,
 371                        BoundNodesTreeBuilder *Builder) const {
 372     return matchesSpecialized(Node, Finder, Builder);
 373   }
 374
 375 private:
 376   /// \brief Extracts the CXXRecordDecl of a QualType and returns whether the
 377   /// inner matcher matches on it.
 378   bool matchesSpecialized(const QualType &Node, ASTMatchFinder *Finder,
 379                           BoundNodesTreeBuilder *Builder) const {
 380     /// FIXME: Add other ways to convert...
 381     if (Node.isNull())
 382       return false;
 383     return matchesDecl(Node->getAsCXXRecordDecl(), Finder, Builder);
 384   }
 385
 386   /// \brief Extracts the Decl of the callee of a CallExpr and returns whether
 387   /// the inner matcher matches on it.
 388   bool matchesSpecialized(const CallExpr &Node, ASTMatchFinder *Finder,
 389                           BoundNodesTreeBuilder *Builder) const {
 390     return matchesDecl(Node.getCalleeDecl(), Finder, Builder);
 391   }
 392
 393   /// \brief Extracts the Decl of the constructor call and returns whether the
 394   /// inner matcher matches on it.
 395   bool matchesSpecialized(const CXXConstructExpr &Node,
 396                           ASTMatchFinder *Finder,
 397                           BoundNodesTreeBuilder *Builder) const {
 398     return matchesDecl(Node.getConstructor(), Finder, Builder);
 399   }
 400
 401   /// \brief Extracts the \c ValueDecl a \c MemberExpr refers to and returns
 402   /// whether the inner matcher matches on it.
 403   bool matchesSpecialized(const MemberExpr &Node,
 404                           ASTMatchFinder *Finder,
 405                           BoundNodesTreeBuilder *Builder) const {
 406     return matchesDecl(Node.getMemberDecl(), Finder, Builder);
 407   }
 408
 409   /// \brief Returns whether the inner matcher \c Node. Returns false if \c Node
 410   /// is \c NULL.
 411   bool matchesDecl(const Decl *Node,
 412                    ASTMatchFinder *Finder,
 413                    BoundNodesTreeBuilder *Builder) const {
 414     return Node != NULL && InnerMatcher.matches(*Node, Finder, Builder);
 415   }
 416
 417   const Matcher<Decl> InnerMatcher;
 418 };
 419
 420 /// \brief IsBaseType<T>::value is true if T is a "base" type in the AST
 421 /// node class hierarchies.
 422 template <typename T>
 423 struct IsBaseType {
 424   static const bool value =
 425       (llvm::is_same<T, Decl>::value ||
 426        llvm::is_same<T, Stmt>::value ||
 427        llvm::is_same<T, QualType>::value ||
 428        llvm::is_same<T, Type>::value ||
 429        llvm::is_same<T, TypeLoc>::value ||
 430        llvm::is_same<T, NestedNameSpecifier>::value ||
 431        llvm::is_same<T, NestedNameSpecifierLoc>::value ||
 432        llvm::is_same<T, CXXCtorInitializer>::value);
 433 };
 434 template <typename T>
 435 const bool IsBaseType<T>::value;
 436
 437 /// \brief Interface that allows matchers to traverse the AST.
 438 /// FIXME: Find a better name.
 439 ///
 440 /// This provides three entry methods for each base node type in the AST:
 441 /// - \c matchesChildOf:
 442 ///   Matches a matcher on every child node of the given node. Returns true
 443 ///   if at least one child node could be matched.
 444 /// - \c matchesDescendantOf:
 445 ///   Matches a matcher on all descendant nodes of the given node. Returns true
 446 ///   if at least one descendant matched.
 447 /// - \c matchesAncestorOf:
 448 ///   Matches a matcher on all ancestors of the given node. Returns true if
 449 ///   at least one ancestor matched.
 450 ///
 451 /// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal.
 452 /// In the future, we wan to implement this for all nodes for which it makes
 453 /// sense. In the case of matchesAncestorOf, we'll want to implement it for
 454 /// all nodes, as all nodes have ancestors.
 455 class ASTMatchFinder {
 456 public:
 457   /// \brief Defines how we descend a level in the AST when we pass
 458   /// through expressions.
 459   enum TraversalKind {
 460     /// Will traverse any child nodes.
 461     TK_AsIs,
 462     /// Will not traverse implicit casts and parentheses.
 463     TK_IgnoreImplicitCastsAndParentheses
 464   };
 465
 466   /// \brief Defines how bindings are processed on recursive matches.
 467   enum BindKind {
 468     /// Stop at the first match and only bind the first match.
 469     BK_First,
 470     /// Create results for all combinations of bindings that match.
 471     BK_All
 472   };
 473
 474   /// \brief Defines which ancestors are considered for a match.
 475   enum AncestorMatchMode {
 476     /// All ancestors.
 477     AMM_All,
 478     /// Direct parent only.
 479     AMM_ParentOnly
 480   };
 481
 482   virtual ~ASTMatchFinder() {}
 483
 484   /// \brief Returns true if the given class is directly or indirectly derived
 485   /// from a base type matching \c base.
 486   ///
 487   /// A class is considered to be also derived from itself.
 488   virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
 489                                   const Matcher<NamedDecl> &Base,
 490                                   BoundNodesTreeBuilder *Builder) = 0;
 491
 492   template <typename T>
 493   bool matchesChildOf(const T &Node,
 494                       const DynTypedMatcher &Matcher,
 495                       BoundNodesTreeBuilder *Builder,
 496                       TraversalKind Traverse,
 497                       BindKind Bind) {
 498     TOOLING_COMPILE_ASSERT(
 499         (llvm::is_base_of<Decl, T>::value ||
 500          llvm::is_base_of<Stmt, T>::value ||
 501          llvm::is_base_of<NestedNameSpecifier, T>::value ||
 502          llvm::is_base_of<NestedNameSpecifierLoc, T>::value ||
 503          llvm::is_base_of<TypeLoc, T>::value ||
 504          llvm::is_base_of<QualType, T>::value),
 505         unsupported_type_for_recursive_matching);
 506    return matchesChildOf(ast_type_traits::DynTypedNode::create(Node),
 507                           Matcher, Builder, Traverse, Bind);
 508   }
 509
 510   template <typename T>
 511   bool matchesDescendantOf(const T &Node,
 512                            const DynTypedMatcher &Matcher,
 513                            BoundNodesTreeBuilder *Builder,
 514                            BindKind Bind) {
 515     TOOLING_COMPILE_ASSERT(
 516         (llvm::is_base_of<Decl, T>::value ||
 517          llvm::is_base_of<Stmt, T>::value ||
 518          llvm::is_base_of<NestedNameSpecifier, T>::value ||
 519          llvm::is_base_of<NestedNameSpecifierLoc, T>::value ||
 520          llvm::is_base_of<TypeLoc, T>::value ||
 521          llvm::is_base_of<QualType, T>::value),
 522         unsupported_type_for_recursive_matching);
 523     return matchesDescendantOf(ast_type_traits::DynTypedNode::create(Node),
 524                                Matcher, Builder, Bind);
 525   }
 526
 527   // FIXME: Implement support for BindKind.
 528   template <typename T>
 529   bool matchesAncestorOf(const T &Node,
 530                          const DynTypedMatcher &Matcher,
 531                          BoundNodesTreeBuilder *Builder,
 532                          AncestorMatchMode MatchMode) {
 533     TOOLING_COMPILE_ASSERT((llvm::is_base_of<Decl, T>::value ||
 534                             llvm::is_base_of<Stmt, T>::value),
 535                            only_Decl_or_Stmt_allowed_for_recursive_matching);
 536     return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node),
 537                              Matcher, Builder, MatchMode);
 538   }
 539
 540 protected:
 541   virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
 542                               const DynTypedMatcher &Matcher,
 543                               BoundNodesTreeBuilder *Builder,
 544                               TraversalKind Traverse,
 545                               BindKind Bind) = 0;
 546
 547   virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
 548                                    const DynTypedMatcher &Matcher,
 549                                    BoundNodesTreeBuilder *Builder,
 550                                    BindKind Bind) = 0;
 551
 552   virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
 553                                  const DynTypedMatcher &Matcher,
 554                                  BoundNodesTreeBuilder *Builder,
 555                                  AncestorMatchMode MatchMode) = 0;
 556 };
 557
 558 /// \brief Converts a \c Matcher<T> to a matcher of desired type \c To by
 559 /// "adapting" a \c To into a \c T.
 560 ///
 561 /// The \c ArgumentAdapterT argument specifies how the adaptation is done.
 562 ///
 563 /// For example:
 564 ///   \c ArgumentAdaptingMatcher<HasMatcher, T>(InnerMatcher);
 565 /// Given that \c InnerMatcher is of type \c Matcher<T>, this returns a matcher
 566 /// that is convertible into any matcher of type \c To by constructing
 567 /// \c HasMatcher<To, T>(InnerMatcher).
 568 ///
 569 /// If a matcher does not need knowledge about the inner type, prefer to use
 570 /// PolymorphicMatcherWithParam1.
 571 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
 572           typename T>
 573 class ArgumentAdaptingMatcher {
 574 public:
 575   explicit ArgumentAdaptingMatcher(const Matcher<T> &InnerMatcher)
 576       : InnerMatcher(InnerMatcher) {}
 577
 578   template <typename To>
 579   operator Matcher<To>() const {
 580     return Matcher<To>(new ArgumentAdapterT<To, T>(InnerMatcher));
 581   }
 582
 583 private:
 584   const Matcher<T> InnerMatcher;
 585 };
 586
 587 /// \brief A PolymorphicMatcherWithParamN<MatcherT, P1, ..., PN> object can be
 588 /// created from N parameters p1, ..., pN (of type P1, ..., PN) and
 589 /// used as a Matcher<T> where a MatcherT<T, P1, ..., PN>(p1, ..., pN)
 590 /// can be constructed.
 591 ///
 592 /// For example:
 593 /// - PolymorphicMatcherWithParam0<IsDefinitionMatcher>()
 594 ///   creates an object that can be used as a Matcher<T> for any type T
 595 ///   where an IsDefinitionMatcher<T>() can be constructed.
 596 /// - PolymorphicMatcherWithParam1<ValueEqualsMatcher, int>(42)
 597 ///   creates an object that can be used as a Matcher<T> for any type T
 598 ///   where a ValueEqualsMatcher<T, int>(42) can be constructed.
 599 template <template <typename T> class MatcherT>
 600 class PolymorphicMatcherWithParam0 {
 601 public:
 602   template <typename T>
 603   operator Matcher<T>() const {
 604     return Matcher<T>(new MatcherT<T>());
 605   }
 606 };
 607
 608 template <template <typename T, typename P1> class MatcherT,
 609           typename P1>
 610 class PolymorphicMatcherWithParam1 {
 611 public:
 612   explicit PolymorphicMatcherWithParam1(const P1 &Param1)
 613       : Param1(Param1) {}
 614
 615   template <typename T>
 616   operator Matcher<T>() const {
 617     return Matcher<T>(new MatcherT<T, P1>(Param1));
 618   }
 619
 620 private:
 621   const P1 Param1;
 622 };
 623
 624 template <template <typename T, typename P1, typename P2> class MatcherT,
 625           typename P1, typename P2>
 626 class PolymorphicMatcherWithParam2 {
 627 public:
 628   PolymorphicMatcherWithParam2(const P1 &Param1, const P2 &Param2)
 629       : Param1(Param1), Param2(Param2) {}
 630
 631   template <typename T>
 632   operator Matcher<T>() const {
 633     return Matcher<T>(new MatcherT<T, P1, P2>(Param1, Param2));
 634   }
 635
 636 private:
 637   const P1 Param1;
 638   const P2 Param2;
 639 };
 640
 641 /// \brief Matches any instance of the given NodeType.
 642 ///
 643 /// This is useful when a matcher syntactically requires a child matcher,
 644 /// but the context doesn't care. See for example: anything().
 645 ///
 646 /// FIXME: Alternatively we could also create a IsAMatcher or something
 647 /// that checks that a dyn_cast is possible. This is purely needed for the
 648 /// difference between calling for example:
 649 ///   record()
 650 /// and
 651 ///   record(SomeMatcher)
 652 /// In the second case we need the correct type we were dyn_cast'ed to in order
 653 /// to get the right type for the inner matcher. In the first case we don't need
 654 /// that, but we use the type conversion anyway and insert a TrueMatcher.
 655 template <typename T>
 656 class TrueMatcher : public SingleNodeMatcherInterface<T>  {
 657 public:
 658   virtual bool matchesNode(const T &Node) const {
 659     return true;
 660   }
 661 };
 662
 663 /// \brief Provides a MatcherInterface<T> for a Matcher<To> that matches if T is
 664 /// dyn_cast'able into To and the given Matcher<To> matches on the dyn_cast'ed
 665 /// node.
 666 template <typename T, typename To>
 667 class DynCastMatcher : public MatcherInterface<T> {
 668 public:
 669   explicit DynCastMatcher(const Matcher<To> &InnerMatcher)
 670       : InnerMatcher(InnerMatcher) {}
 671
 672   virtual bool matches(const T &Node,
 673                        ASTMatchFinder *Finder,
 674                        BoundNodesTreeBuilder *Builder) const {
 675     const To *InnerMatchValue = llvm::dyn_cast<To>(&Node);
 676     return InnerMatchValue != NULL &&
 677       InnerMatcher.matches(*InnerMatchValue, Finder, Builder);
 678   }
 679
 680 private:
 681   const Matcher<To> InnerMatcher;
 682 };
 683
 684 /// \brief Matcher<T> that wraps an inner Matcher<T> and binds the matched node
 685 /// to an ID if the inner matcher matches on the node.
 686 template <typename T>
 687 class IdMatcher : public MatcherInterface<T> {
 688 public:
 689   /// \brief Creates an IdMatcher that binds to 'ID' if 'InnerMatcher' matches
 690   /// the node.
 691   IdMatcher(StringRef ID, const Matcher<T> &InnerMatcher)
 692       : ID(ID), InnerMatcher(InnerMatcher) {}
 693
 694   virtual bool matches(const T &Node,
 695                        ASTMatchFinder *Finder,
 696                        BoundNodesTreeBuilder *Builder) const {
 697     bool Result = InnerMatcher.matches(Node, Finder, Builder);
 698     if (Result) {
 699       Builder->setBinding(ID, &Node);
 700     }
 701     return Result;
 702   }
 703
 704 private:
 705   const std::string ID;
 706   const Matcher<T> InnerMatcher;
 707 };
 708
 709 /// \brief A Matcher that allows binding the node it matches to an id.
 710 ///
 711 /// BindableMatcher provides a \a bind() method that allows binding the
 712 /// matched node to an id if the match was successful.
 713 template <typename T>
 714 class BindableMatcher : public Matcher<T> {
 715 public:
 716   BindableMatcher(MatcherInterface<T> *Implementation)
 717     : Matcher<T>(Implementation) {}
 718
 719   /// \brief Returns a matcher that will bind the matched node on a match.
 720   ///
 721   /// The returned matcher is equivalent to this matcher, but will
 722   /// bind the matched node on a match.
 723   Matcher<T> bind(StringRef ID) const {
 724     return Matcher<T>(new IdMatcher<T>(ID, *this));
 725   }
 726 };
 727
 728 /// \brief Matches nodes of type T that have child nodes of type ChildT for
 729 /// which a specified child matcher matches.
 730 ///
 731 /// ChildT must be an AST base type.
 732 template <typename T, typename ChildT>
 733 class HasMatcher : public MatcherInterface<T> {
 734   TOOLING_COMPILE_ASSERT(IsBaseType<ChildT>::value,
 735                          has_only_accepts_base_type_matcher);
 736 public:
 737   explicit HasMatcher(const Matcher<ChildT> &ChildMatcher)
 738       : ChildMatcher(ChildMatcher) {}
 739
 740   virtual bool matches(const T &Node,
 741                        ASTMatchFinder *Finder,
 742                        BoundNodesTreeBuilder *Builder) const {
 743     return Finder->matchesChildOf(
 744         Node, ChildMatcher, Builder,
 745         ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses,
 746         ASTMatchFinder::BK_First);
 747   }
 748
 749  private:
 750   const Matcher<ChildT> ChildMatcher;
 751 };
 752
 753 /// \brief Matches nodes of type T that have child nodes of type ChildT for
 754 /// which a specified child matcher matches. ChildT must be an AST base
 755 /// type.
 756 /// As opposed to the HasMatcher, the ForEachMatcher will produce a match
 757 /// for each child that matches.
 758 template <typename T, typename ChildT>
 759 class ForEachMatcher : public MatcherInterface<T> {
 760   TOOLING_COMPILE_ASSERT(IsBaseType<ChildT>::value,
 761                          for_each_only_accepts_base_type_matcher);
 762  public:
 763   explicit ForEachMatcher(const Matcher<ChildT> &ChildMatcher)
 764       : ChildMatcher(ChildMatcher) {}
 765
 766   virtual bool matches(const T& Node,
 767                        ASTMatchFinder* Finder,
 768                        BoundNodesTreeBuilder* Builder) const {
 769     return Finder->matchesChildOf(
 770       Node, ChildMatcher, Builder,
 771       ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses,
 772       ASTMatchFinder::BK_All);
 773   }
 774
 775 private:
 776   const Matcher<ChildT> ChildMatcher;
 777 };
 778
 779 /// \brief Matches nodes of type T if the given Matcher<T> does not match.
 780 ///
 781 /// Type argument MatcherT is required by PolymorphicMatcherWithParam1
 782 /// but not actually used. It will always be instantiated with a type
 783 /// convertible to Matcher<T>.
 784 template <typename T, typename MatcherT>
 785 class NotMatcher : public MatcherInterface<T> {
 786 public:
 787   explicit NotMatcher(const Matcher<T> &InnerMatcher)
 788       : InnerMatcher(InnerMatcher) {}
 789
 790   virtual bool matches(const T &Node,
 791                        ASTMatchFinder *Finder,
 792                        BoundNodesTreeBuilder *Builder) const {
 793     return !InnerMatcher.matches(Node, Finder, Builder);
 794   }
 795
 796 private:
 797   const Matcher<T> InnerMatcher;
 798 };
 799
 800 /// \brief Matches nodes of type T for which both provided matchers match.
 801 ///
 802 /// Type arguments MatcherT1 and MatcherT2 are required by
 803 /// PolymorphicMatcherWithParam2 but not actually used. They will
 804 /// always be instantiated with types convertible to Matcher<T>.
 805 template <typename T, typename MatcherT1, typename MatcherT2>
 806 class AllOfMatcher : public MatcherInterface<T> {
 807 public:
 808   AllOfMatcher(const Matcher<T> &InnerMatcher1, const Matcher<T> &InnerMatcher2)
 809       : InnerMatcher1(InnerMatcher1), InnerMatcher2(InnerMatcher2) {}
 810
 811   virtual bool matches(const T &Node,
 812                        ASTMatchFinder *Finder,
 813                        BoundNodesTreeBuilder *Builder) const {
 814     return InnerMatcher1.matches(Node, Finder, Builder) &&
 815            InnerMatcher2.matches(Node, Finder, Builder);
 816   }
 817
 818 private:
 819   const Matcher<T> InnerMatcher1;
 820   const Matcher<T> InnerMatcher2;
 821 };
 822
 823 /// \brief Matches nodes of type T for which at least one of the two provided
 824 /// matchers matches.
 825 ///
 826 /// Type arguments MatcherT1 and MatcherT2 are
 827 /// required by PolymorphicMatcherWithParam2 but not actually
 828 /// used. They will always be instantiated with types convertible to
 829 /// Matcher<T>.
 830 template <typename T, typename MatcherT1, typename MatcherT2>
 831 class AnyOfMatcher : public MatcherInterface<T> {
 832 public:
 833   AnyOfMatcher(const Matcher<T> &InnerMatcher1, const Matcher<T> &InnerMatcher2)
 834       : InnerMatcher1(InnerMatcher1), InnertMatcher2(InnerMatcher2) {}
 835
 836   virtual bool matches(const T &Node,
 837                        ASTMatchFinder *Finder,
 838                        BoundNodesTreeBuilder *Builder) const {
 839     return InnerMatcher1.matches(Node, Finder, Builder) ||
 840            InnertMatcher2.matches(Node, Finder, Builder);
 841   }
 842
 843 private:
 844   const Matcher<T> InnerMatcher1;
 845   const Matcher<T> InnertMatcher2;
 846 };
 847
 848 /// \brief Creates a Matcher<T> that matches if all inner matchers match.
 849 template<typename T>
 850 BindableMatcher<T> makeAllOfComposite(
 851     ArrayRef<const Matcher<T> *> InnerMatchers) {
 852   if (InnerMatchers.empty())
 853     return BindableMatcher<T>(new TrueMatcher<T>);
 854   MatcherInterface<T> *InnerMatcher = new TrueMatcher<T>;
 855   for (int i = InnerMatchers.size() - 1; i >= 0; --i) {
 856     InnerMatcher = new AllOfMatcher<T, Matcher<T>, Matcher<T> >(
 857       *InnerMatchers[i], makeMatcher(InnerMatcher));
 858   }
 859   return BindableMatcher<T>(InnerMatcher);
 860 }
 861
 862 /// \brief Creates a Matcher<T> that matches if
 863 /// T is dyn_cast'able into InnerT and all inner matchers match.
 864 ///
 865 /// Returns BindableMatcher, as matchers that use dyn_cast have
 866 /// the same object both to match on and to run submatchers on,
 867 /// so there is no ambiguity with what gets bound.
 868 template<typename T, typename InnerT>
 869 BindableMatcher<T> makeDynCastAllOfComposite(
 870     ArrayRef<const Matcher<InnerT> *> InnerMatchers) {
 871   return BindableMatcher<T>(new DynCastMatcher<T, InnerT>(
 872     makeAllOfComposite(InnerMatchers)));
 873 }
 874
 875 /// \brief Matches nodes of type T that have at least one descendant node of
 876 /// type DescendantT for which the given inner matcher matches.
 877 ///
 878 /// DescendantT must be an AST base type.
 879 template <typename T, typename DescendantT>
 880 class HasDescendantMatcher : public MatcherInterface<T> {
 881   TOOLING_COMPILE_ASSERT(IsBaseType<DescendantT>::value,
 882                          has_descendant_only_accepts_base_type_matcher);
 883 public:
 884   explicit HasDescendantMatcher(const Matcher<DescendantT> &DescendantMatcher)
 885       : DescendantMatcher(DescendantMatcher) {}
 886
 887   virtual bool matches(const T &Node,
 888                        ASTMatchFinder *Finder,
 889                        BoundNodesTreeBuilder *Builder) const {
 890     return Finder->matchesDescendantOf(
 891         Node, DescendantMatcher, Builder, ASTMatchFinder::BK_First);
 892   }
 893
 894  private:
 895   const Matcher<DescendantT> DescendantMatcher;
 896 };
 897
 898 /// \brief Matches nodes of type \c T that have a parent node of type \c ParentT
 899 /// for which the given inner matcher matches.
 900 ///
 901 /// \c ParentT must be an AST base type.
 902 template <typename T, typename ParentT>
 903 class HasParentMatcher : public MatcherInterface<T> {
 904   TOOLING_COMPILE_ASSERT(IsBaseType<ParentT>::value,
 905                          has_parent_only_accepts_base_type_matcher);
 906 public:
 907   explicit HasParentMatcher(const Matcher<ParentT> &ParentMatcher)
 908       : ParentMatcher(ParentMatcher) {}
 909
 910   virtual bool matches(const T &Node,
 911                        ASTMatchFinder *Finder,
 912                        BoundNodesTreeBuilder *Builder) const {
 913     return Finder->matchesAncestorOf(
 914         Node, ParentMatcher, Builder, ASTMatchFinder::AMM_ParentOnly);
 915   }
 916
 917  private:
 918   const Matcher<ParentT> ParentMatcher;
 919 };
 920
 921 /// \brief Matches nodes of type \c T that have at least one ancestor node of
 922 /// type \c AncestorT for which the given inner matcher matches.
 923 ///
 924 /// \c AncestorT must be an AST base type.
 925 template <typename T, typename AncestorT>
 926 class HasAncestorMatcher : public MatcherInterface<T> {
 927   TOOLING_COMPILE_ASSERT(IsBaseType<AncestorT>::value,
 928                          has_ancestor_only_accepts_base_type_matcher);
 929 public:
 930   explicit HasAncestorMatcher(const Matcher<AncestorT> &AncestorMatcher)
 931       : AncestorMatcher(AncestorMatcher) {}
 932
 933   virtual bool matches(const T &Node,
 934                        ASTMatchFinder *Finder,
 935                        BoundNodesTreeBuilder *Builder) const {
 936     return Finder->matchesAncestorOf(
 937         Node, AncestorMatcher, Builder, ASTMatchFinder::AMM_All);
 938   }
 939
 940  private:
 941   const Matcher<AncestorT> AncestorMatcher;
 942 };
 943
 944 /// \brief Matches nodes of type T that have at least one descendant node of
 945 /// type DescendantT for which the given inner matcher matches.
 946 ///
 947 /// DescendantT must be an AST base type.
 948 /// As opposed to HasDescendantMatcher, ForEachDescendantMatcher will match
 949 /// for each descendant node that matches instead of only for the first.
 950 template <typename T, typename DescendantT>
 951 class ForEachDescendantMatcher : public MatcherInterface<T> {
 952   TOOLING_COMPILE_ASSERT(IsBaseType<DescendantT>::value,
 953                          for_each_descendant_only_accepts_base_type_matcher);
 954  public:
 955   explicit ForEachDescendantMatcher(
 956       const Matcher<DescendantT>& DescendantMatcher)
 957       : DescendantMatcher(DescendantMatcher) {}
 958
 959   virtual bool matches(const T& Node,
 960                        ASTMatchFinder* Finder,
 961                        BoundNodesTreeBuilder* Builder) const {
 962     return Finder->matchesDescendantOf(Node, DescendantMatcher, Builder,
 963                                        ASTMatchFinder::BK_All);
 964   }
 965
 966 private:
 967   const Matcher<DescendantT> DescendantMatcher;
 968 };
 969
 970 /// \brief Matches on nodes that have a getValue() method if getValue() equals
 971 /// the value the ValueEqualsMatcher was constructed with.
 972 template <typename T, typename ValueT>
 973 class ValueEqualsMatcher : public SingleNodeMatcherInterface<T> {
 974   TOOLING_COMPILE_ASSERT((llvm::is_base_of<CharacterLiteral, T>::value ||
 975                          llvm::is_base_of<CXXBoolLiteralExpr,
 976                                           T>::value ||
 977                          llvm::is_base_of<FloatingLiteral, T>::value ||
 978                          llvm::is_base_of<IntegerLiteral, T>::value),
 979                          the_node_must_have_a_getValue_method);
 980 public:
 981   explicit ValueEqualsMatcher(const ValueT &ExpectedValue)
 982       : ExpectedValue(ExpectedValue) {}
 983
 984   virtual bool matchesNode(const T &Node) const {
 985     return Node.getValue() == ExpectedValue;
 986   }
 987
 988 private:
 989   const ValueT ExpectedValue;
 990 };
 991
 992 template <typename T>
 993 class IsDefinitionMatcher : public SingleNodeMatcherInterface<T> {
 994   TOOLING_COMPILE_ASSERT(
 995     (llvm::is_base_of<TagDecl, T>::value) ||
 996     (llvm::is_base_of<VarDecl, T>::value) ||
 997     (llvm::is_base_of<FunctionDecl, T>::value),
 998     is_definition_requires_isThisDeclarationADefinition_method);
 999 public:
1000   virtual bool matchesNode(const T &Node) const {
1001     return Node.isThisDeclarationADefinition();
1002   }
1003 };
1004
1005 /// \brief Matches on template instantiations for FunctionDecl, VarDecl or
1006 /// CXXRecordDecl nodes.
1007 template <typename T>
1008 class IsTemplateInstantiationMatcher : public MatcherInterface<T> {
1009   TOOLING_COMPILE_ASSERT((llvm::is_base_of<FunctionDecl, T>::value) ||
1010                          (llvm::is_base_of<VarDecl, T>::value) ||
1011                          (llvm::is_base_of<CXXRecordDecl, T>::value),
1012                          requires_getTemplateSpecializationKind_method);
1013  public:
1014   virtual bool matches(const T& Node,
1015                        ASTMatchFinder* Finder,
1016                        BoundNodesTreeBuilder* Builder) const {
1017     return (Node.getTemplateSpecializationKind() ==
1018                 TSK_ImplicitInstantiation ||
1019             Node.getTemplateSpecializationKind() ==
1020                 TSK_ExplicitInstantiationDefinition);
1021   }
1022 };
1023
1024 /// \brief Matches on explicit template specializations for FunctionDecl,
1025 /// VarDecl or CXXRecordDecl nodes.
1026 template <typename T>
1027 class IsExplicitTemplateSpecializationMatcher : public MatcherInterface<T> {
1028   TOOLING_COMPILE_ASSERT((llvm::is_base_of<FunctionDecl, T>::value) ||
1029                          (llvm::is_base_of<VarDecl, T>::value) ||
1030                          (llvm::is_base_of<CXXRecordDecl, T>::value),
1031                          requires_getTemplateSpecializationKind_method);
1032  public:
1033   virtual bool matches(const T& Node,
1034                        ASTMatchFinder* Finder,
1035                        BoundNodesTreeBuilder* Builder) const {
1036     return (Node.getTemplateSpecializationKind() == TSK_ExplicitSpecialization);
1037   }
1038 };
1039
1040 class IsArrowMatcher : public SingleNodeMatcherInterface<MemberExpr> {
1041 public:
1042   virtual bool matchesNode(const MemberExpr &Node) const {
1043     return Node.isArrow();
1044   }
1045 };
1046
1047 class IsConstQualifiedMatcher
1048     : public SingleNodeMatcherInterface<QualType> {
1049  public:
1050   virtual bool matchesNode(const QualType& Node) const {
1051     return Node.isConstQualified();
1052   }
1053 };
1054
1055 /// \brief A VariadicDynCastAllOfMatcher<SourceT, TargetT> object is a
1056 /// variadic functor that takes a number of Matcher<TargetT> and returns a
1057 /// Matcher<SourceT> that matches TargetT nodes that are matched by all of the
1058 /// given matchers, if SourceT can be dynamically casted into TargetT.
1059 ///
1060 /// For example:
1061 ///   const VariadicDynCastAllOfMatcher<
1062 ///       Decl, CXXRecordDecl> record;
1063 /// Creates a functor record(...) that creates a Matcher<Decl> given
1064 /// a variable number of arguments of type Matcher<CXXRecordDecl>.
1065 /// The returned matcher matches if the given Decl can by dynamically
1066 /// casted to CXXRecordDecl and all given matchers match.
1067 template <typename SourceT, typename TargetT>
1068 class VariadicDynCastAllOfMatcher
1069     : public llvm::VariadicFunction<
1070         BindableMatcher<SourceT>, Matcher<TargetT>,
1071         makeDynCastAllOfComposite<SourceT, TargetT> > {
1072 public:
1073   VariadicDynCastAllOfMatcher() {}
1074 };
1075
1076 /// \brief A \c VariadicAllOfMatcher<T> object is a variadic functor that takes
1077 /// a number of \c Matcher<T> and returns a \c Matcher<T> that matches \c T
1078 /// nodes that are matched by all of the given matchers.
1079 ///
1080 /// For example:
1081 ///   const VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier;
1082 /// Creates a functor nestedNameSpecifier(...) that creates a
1083 /// \c Matcher<NestedNameSpecifier> given a variable number of arguments of type
1084 /// \c Matcher<NestedNameSpecifier>.
1085 /// The returned matcher matches if all given matchers match.
1086 template <typename T>
1087 class VariadicAllOfMatcher : public llvm::VariadicFunction<
1088                                BindableMatcher<T>, Matcher<T>,
1089                                makeAllOfComposite<T> > {
1090 public:
1091   VariadicAllOfMatcher() {}
1092 };
1093
1094 /// \brief Matches nodes of type \c TLoc for which the inner
1095 /// \c Matcher<T> matches.
1096 template <typename TLoc, typename T>
1097 class LocMatcher : public MatcherInterface<TLoc> {
1098 public:
1099   explicit LocMatcher(const Matcher<T> &InnerMatcher)
1100     : InnerMatcher(InnerMatcher) {}
1101
1102   virtual bool matches(const TLoc &Node,
1103                        ASTMatchFinder *Finder,
1104                        BoundNodesTreeBuilder *Builder) const {
1105     if (!Node)
1106       return false;
1107     return InnerMatcher.matches(*extract(Node), Finder, Builder);
1108   }
1109
1110 private:
1111   const NestedNameSpecifier *extract(const NestedNameSpecifierLoc &Loc) const {
1112     return Loc.getNestedNameSpecifier();
1113   }
1114
1115   const Matcher<T> InnerMatcher;
1116 };
1117
1118 /// \brief Matches \c NestedNameSpecifiers with a prefix matching another
1119 /// \c Matcher<NestedNameSpecifier>.
1120 class NestedNameSpecifierPrefixMatcher
1121   : public MatcherInterface<NestedNameSpecifier> {
1122 public:
1123   explicit NestedNameSpecifierPrefixMatcher(
1124     const Matcher<NestedNameSpecifier> &InnerMatcher)
1125     : InnerMatcher(InnerMatcher) {}
1126
1127   virtual bool matches(const NestedNameSpecifier &Node,
1128                        ASTMatchFinder *Finder,
1129                        BoundNodesTreeBuilder *Builder) const {
1130     NestedNameSpecifier *NextNode = Node.getPrefix();
1131     if (NextNode == NULL)
1132       return false;
1133     return InnerMatcher.matches(*NextNode, Finder, Builder);
1134   }
1135
1136 private:
1137   const Matcher<NestedNameSpecifier> InnerMatcher;
1138 };
1139
1140 /// \brief Matches \c NestedNameSpecifierLocs with a prefix matching another
1141 /// \c Matcher<NestedNameSpecifierLoc>.
1142 class NestedNameSpecifierLocPrefixMatcher
1143   : public MatcherInterface<NestedNameSpecifierLoc> {
1144 public:
1145   explicit NestedNameSpecifierLocPrefixMatcher(
1146     const Matcher<NestedNameSpecifierLoc> &InnerMatcher)
1147     : InnerMatcher(InnerMatcher) {}
1148
1149   virtual bool matches(const NestedNameSpecifierLoc &Node,
1150                        ASTMatchFinder *Finder,
1151                        BoundNodesTreeBuilder *Builder) const {
1152     NestedNameSpecifierLoc NextNode = Node.getPrefix();
1153     if (!NextNode)
1154       return false;
1155     return InnerMatcher.matches(NextNode, Finder, Builder);
1156   }
1157
1158 private:
1159   const Matcher<NestedNameSpecifierLoc> InnerMatcher;
1160 };
1161
1162 /// \brief Matches \c TypeLocs based on an inner matcher matching a certain
1163 /// \c QualType.
1164 ///
1165 /// Used to implement the \c loc() matcher.
1166 class TypeLocTypeMatcher : public MatcherInterface<TypeLoc> {
1167 public:
1168   explicit TypeLocTypeMatcher(const Matcher<QualType> &InnerMatcher)
1169       : InnerMatcher(InnerMatcher) {}
1170
1171   virtual bool matches(const TypeLoc &Node,
1172                        ASTMatchFinder *Finder,
1173                        BoundNodesTreeBuilder *Builder) const {
1174     if (!Node)
1175       return false;
1176     return InnerMatcher.matches(Node.getType(), Finder, Builder);
1177   }
1178
1179 private:
1180   const Matcher<QualType> InnerMatcher;
1181 };
1182
1183 /// \brief Matches nodes of type \c T for which the inner matcher matches on a
1184 /// another node of type \c T that can be reached using a given traverse
1185 /// function.
1186 template <typename T>
1187 class TypeTraverseMatcher : public MatcherInterface<T> {
1188 public:
1189   explicit TypeTraverseMatcher(const Matcher<QualType> &InnerMatcher,
1190                                QualType (T::*TraverseFunction)() const)
1191       : InnerMatcher(InnerMatcher), TraverseFunction(TraverseFunction) {}
1192
1193   virtual bool matches(const T &Node,
1194                        ASTMatchFinder *Finder,
1195                        BoundNodesTreeBuilder *Builder) const {
1196     QualType NextNode = (Node.*TraverseFunction)();
1197     if (NextNode.isNull())
1198       return false;
1199     return InnerMatcher.matches(NextNode, Finder, Builder);
1200   }
1201
1202 private:
1203   const Matcher<QualType> InnerMatcher;
1204   QualType (T::*TraverseFunction)() const;
1205 };
1206
1207 /// \brief Matches nodes of type \c T in a ..Loc hierarchy, for which the inner
1208 /// matcher matches on a another node of type \c T that can be reached using a
1209 /// given traverse function.
1210 template <typename T>
1211 class TypeLocTraverseMatcher : public MatcherInterface<T> {
1212 public:
1213   explicit TypeLocTraverseMatcher(const Matcher<TypeLoc> &InnerMatcher,
1214                                   TypeLoc (T::*TraverseFunction)() const)
1215       : InnerMatcher(InnerMatcher), TraverseFunction(TraverseFunction) {}
1216
1217   virtual bool matches(const T &Node,
1218                        ASTMatchFinder *Finder,
1219                        BoundNodesTreeBuilder *Builder) const {
1220     TypeLoc NextNode = (Node.*TraverseFunction)();
1221     if (!NextNode)
1222       return false;
1223     return InnerMatcher.matches(NextNode, Finder, Builder);
1224   }
1225
1226 private:
1227   const Matcher<TypeLoc> InnerMatcher;
1228   TypeLoc (T::*TraverseFunction)() const;
1229 };
1230
1231 template <typename T, typename InnerT>
1232 T makeTypeAllOfComposite(ArrayRef<const Matcher<InnerT> *> InnerMatchers) {
1233   return T(makeAllOfComposite<InnerT>(InnerMatchers));
1234 }
1235
1236 } // end namespace internal
1237 } // end namespace ast_matchers
1238 } // end namespace clang
1239
1240 #endif // LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_INTERNAL_H