Home | History | Annotate | Download | only in ASTMatchers
      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/ASTTypeTraits.h"
     39 #include "clang/AST/DeclCXX.h"
     40 #include "clang/AST/Decl.h"
     41 #include "clang/AST/ExprCXX.h"
     42 #include "clang/AST/StmtCXX.h"
     43 #include "clang/AST/Stmt.h"
     44 #include "clang/AST/Type.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 /// \brief Internal version of BoundNodes. Holds all the bound nodes.
     64 class BoundNodesMap {
     65 public:
     66   /// \brief Adds \c Node to the map with key \c ID.
     67   ///
     68   /// The node's base type should be in NodeBaseType or it will be unaccessible.
     69   template <typename T>
     70   void addNode(StringRef ID, const T* Node) {
     71     NodeMap[ID] = ast_type_traits::DynTypedNode::create(*Node);
     72   }
     73 
     74   /// \brief Returns the AST node bound to \c ID.
     75   ///
     76   /// Returns NULL if there was no node bound to \c ID or if there is a node but
     77   /// it cannot be converted to the specified type.
     78   template <typename T>
     79   const T *getNodeAs(StringRef ID) const {
     80     IDToNodeMap::const_iterator It = NodeMap.find(ID);
     81     if (It == NodeMap.end()) {
     82       return NULL;
     83     }
     84     return It->second.get<T>();
     85   }
     86 
     87   ast_type_traits::DynTypedNode getNode(StringRef ID) const {
     88     IDToNodeMap::const_iterator It = NodeMap.find(ID);
     89     if (It == NodeMap.end()) {
     90       return ast_type_traits::DynTypedNode();
     91     }
     92     return It->second;
     93   }
     94 
     95   /// \brief Imposes an order on BoundNodesMaps.
     96   bool operator<(const BoundNodesMap &Other) const {
     97     return NodeMap < Other.NodeMap;
     98   }
     99 
    100 private:
    101   /// \brief A map from IDs to the bound nodes.
    102   ///
    103   /// Note that we're using std::map here, as for memoization:
    104   /// - we need a comparison operator
    105   /// - we need an assignment operator
    106   typedef std::map<std::string, ast_type_traits::DynTypedNode> IDToNodeMap;
    107 
    108   IDToNodeMap NodeMap;
    109 };
    110 
    111 /// \brief Creates BoundNodesTree objects.
    112 ///
    113 /// The tree builder is used during the matching process to insert the bound
    114 /// nodes from the Id matcher.
    115 class BoundNodesTreeBuilder {
    116 public:
    117   /// \brief A visitor interface to visit all BoundNodes results for a
    118   /// BoundNodesTree.
    119   class Visitor {
    120   public:
    121     virtual ~Visitor() {}
    122 
    123     /// \brief Called multiple times during a single call to VisitMatches(...).
    124     ///
    125     /// 'BoundNodesView' contains the bound nodes for a single match.
    126     virtual void visitMatch(const BoundNodes& BoundNodesView) = 0;
    127   };
    128 
    129   /// \brief Add a binding from an id to a node.
    130   template <typename T> void setBinding(const std::string &Id, const T *Node) {
    131     if (Bindings.empty())
    132       Bindings.push_back(BoundNodesMap());
    133     for (unsigned i = 0, e = Bindings.size(); i != e; ++i)
    134       Bindings[i].addNode(Id, Node);
    135   }
    136 
    137   /// \brief Adds a branch in the tree.
    138   void addMatch(const BoundNodesTreeBuilder &Bindings);
    139 
    140   /// \brief Visits all matches that this BoundNodesTree represents.
    141   ///
    142   /// The ownership of 'ResultVisitor' remains at the caller.
    143   void visitMatches(Visitor* ResultVisitor);
    144 
    145   template <typename ExcludePredicate>
    146   bool removeBindings(const ExcludePredicate &Predicate) {
    147     Bindings.erase(std::remove_if(Bindings.begin(), Bindings.end(), Predicate),
    148                    Bindings.end());
    149     return !Bindings.empty();
    150   }
    151 
    152   /// \brief Imposes an order on BoundNodesTreeBuilders.
    153   bool operator<(const BoundNodesTreeBuilder &Other) const {
    154     return Bindings < Other.Bindings;
    155   }
    156 
    157 private:
    158   SmallVector<BoundNodesMap, 16> Bindings;
    159 };
    160 
    161 class ASTMatchFinder;
    162 
    163 /// \brief Generic interface for matchers on an AST node of type T.
    164 ///
    165 /// Implement this if your matcher may need to inspect the children or
    166 /// descendants of the node or bind matched nodes to names. If you are
    167 /// writing a simple matcher that only inspects properties of the
    168 /// current node and doesn't care about its children or descendants,
    169 /// implement SingleNodeMatcherInterface instead.
    170 template <typename T>
    171 class MatcherInterface : public RefCountedBaseVPTR {
    172 public:
    173   virtual ~MatcherInterface() {}
    174 
    175   /// \brief Returns true if 'Node' can be matched.
    176   ///
    177   /// May bind 'Node' to an ID via 'Builder', or recurse into
    178   /// the AST via 'Finder'.
    179   virtual bool matches(const T &Node,
    180                        ASTMatchFinder *Finder,
    181                        BoundNodesTreeBuilder *Builder) const = 0;
    182 };
    183 
    184 /// \brief Interface for matchers that only evaluate properties on a single
    185 /// node.
    186 template <typename T>
    187 class SingleNodeMatcherInterface : public MatcherInterface<T> {
    188 public:
    189   /// \brief Returns true if the matcher matches the provided node.
    190   ///
    191   /// A subclass must implement this instead of Matches().
    192   virtual bool matchesNode(const T &Node) const = 0;
    193 
    194 private:
    195   /// Implements MatcherInterface::Matches.
    196   virtual bool matches(const T &Node,
    197                        ASTMatchFinder * /* Finder */,
    198                        BoundNodesTreeBuilder * /*  Builder */) const {
    199     return matchesNode(Node);
    200   }
    201 };
    202 
    203 /// \brief Base class for all matchers that works on a \c DynTypedNode.
    204 ///
    205 /// Matcher implementations will check whether the \c DynTypedNode is
    206 /// convertible into the respecitve types and then do the actual match
    207 /// on the actual node, or return false if it is not convertible.
    208 class DynTypedMatcher {
    209 public:
    210   virtual ~DynTypedMatcher();
    211 
    212   /// \brief Returns true if the matcher matches the given \c DynNode.
    213   virtual bool matches(const ast_type_traits::DynTypedNode DynNode,
    214                        ASTMatchFinder *Finder,
    215                        BoundNodesTreeBuilder *Builder) const = 0;
    216 
    217   /// \brief Makes a copy of this matcher object.
    218   virtual DynTypedMatcher *clone() const = 0;
    219 
    220   /// \brief Returns a unique ID for the matcher.
    221   virtual uint64_t getID() const = 0;
    222 
    223   /// \brief Bind the specified \p ID to the matcher.
    224   /// \return A new matcher with the \p ID bound to it if this matcher supports
    225   ///   binding. Otherwise, returns NULL. Returns NULL by default.
    226   virtual DynTypedMatcher* tryBind(StringRef ID) const;
    227 
    228   /// \brief Returns the type this matcher works on.
    229   ///
    230   /// \c matches() will always return false unless the node passed is of this
    231   /// or a derived type.
    232   virtual ast_type_traits::ASTNodeKind getSupportedKind() const = 0;
    233 };
    234 
    235 /// \brief Wrapper of a MatcherInterface<T> *that allows copying.
    236 ///
    237 /// A Matcher<Base> can be used anywhere a Matcher<Derived> is
    238 /// required. This establishes an is-a relationship which is reverse
    239 /// to the AST hierarchy. In other words, Matcher<T> is contravariant
    240 /// with respect to T. The relationship is built via a type conversion
    241 /// operator rather than a type hierarchy to be able to templatize the
    242 /// type hierarchy instead of spelling it out.
    243 template <typename T>
    244 class Matcher : public DynTypedMatcher {
    245 public:
    246   /// \brief Takes ownership of the provided implementation pointer.
    247   explicit Matcher(MatcherInterface<T> *Implementation)
    248       : Implementation(Implementation) {}
    249 
    250   /// \brief Implicitly converts \c Other to a Matcher<T>.
    251   ///
    252   /// Requires \c T to be derived from \c From.
    253   template <typename From>
    254   Matcher(const Matcher<From> &Other,
    255           typename llvm::enable_if_c<
    256             llvm::is_base_of<From, T>::value &&
    257             !llvm::is_same<From, T>::value >::type* = 0)
    258       : Implementation(new ImplicitCastMatcher<From>(Other)) {}
    259 
    260   /// \brief Implicitly converts \c Matcher<Type> to \c Matcher<QualType>.
    261   ///
    262   /// The resulting matcher is not strict, i.e. ignores qualifiers.
    263   template <typename TypeT>
    264   Matcher(const Matcher<TypeT> &Other,
    265           typename llvm::enable_if_c<
    266             llvm::is_same<T, QualType>::value &&
    267             llvm::is_same<TypeT, Type>::value >::type* = 0)
    268       : Implementation(new TypeToQualType<TypeT>(Other)) {}
    269 
    270   /// \brief Returns \c true if the passed DynTypedMatcher can be converted
    271   ///   to a \c Matcher<T>.
    272   ///
    273   /// This method verifies that the underlying matcher in \c Other can process
    274   /// nodes of types T.
    275   static bool canConstructFrom(const DynTypedMatcher &Other) {
    276     return Other.getSupportedKind()
    277         .isBaseOf(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
    278   }
    279 
    280   /// \brief Construct a Matcher<T> interface around the dynamic matcher
    281   ///   \c Other.
    282   ///
    283   /// This method asserts that canConstructFrom(Other) is \c true. Callers
    284   /// should call canConstructFrom(Other) first to make sure that Other is
    285   /// compatible with T.
    286   static Matcher<T> constructFrom(const DynTypedMatcher &Other) {
    287     assert(canConstructFrom(Other));
    288     return Matcher<T>(new WrappedMatcher(Other));
    289   }
    290 
    291   /// \brief Forwards the call to the underlying MatcherInterface<T> pointer.
    292   bool matches(const T &Node,
    293                ASTMatchFinder *Finder,
    294                BoundNodesTreeBuilder *Builder) const {
    295     if (Implementation->matches(Node, Finder, Builder))
    296       return true;
    297     // Delete all bindings when a matcher does not match.
    298     // This prevents unexpected exposure of bound nodes in unmatches
    299     // branches of the match tree.
    300     *Builder = BoundNodesTreeBuilder();
    301     return false;
    302   }
    303 
    304   /// \brief Returns an ID that uniquely identifies the matcher.
    305   uint64_t getID() const {
    306     /// FIXME: Document the requirements this imposes on matcher
    307     /// implementations (no new() implementation_ during a Matches()).
    308     return reinterpret_cast<uint64_t>(Implementation.getPtr());
    309   }
    310 
    311   /// \brief Returns the type this matcher works on.
    312   ast_type_traits::ASTNodeKind getSupportedKind() const {
    313     return ast_type_traits::ASTNodeKind::getFromNodeKind<T>();
    314   }
    315 
    316   /// \brief Returns whether the matcher matches on the given \c DynNode.
    317   virtual bool matches(const ast_type_traits::DynTypedNode DynNode,
    318                        ASTMatchFinder *Finder,
    319                        BoundNodesTreeBuilder *Builder) const {
    320     const T *Node = DynNode.get<T>();
    321     if (!Node) return false;
    322     return matches(*Node, Finder, Builder);
    323   }
    324 
    325   /// \brief Makes a copy of this matcher object.
    326   virtual Matcher<T> *clone() const { return new Matcher<T>(*this); }
    327 
    328   /// \brief Allows the conversion of a \c Matcher<Type> to a \c
    329   /// Matcher<QualType>.
    330   ///
    331   /// Depending on the constructor argument, the matcher is either strict, i.e.
    332   /// does only matches in the absence of qualifiers, or not, i.e. simply
    333   /// ignores any qualifiers.
    334   template <typename TypeT>
    335   class TypeToQualType : public MatcherInterface<QualType> {
    336    public:
    337     TypeToQualType(const Matcher<TypeT> &InnerMatcher)
    338         : InnerMatcher(InnerMatcher) {}
    339 
    340     virtual bool matches(const QualType &Node,
    341                          ASTMatchFinder *Finder,
    342                          BoundNodesTreeBuilder *Builder) const {
    343       if (Node.isNull())
    344         return false;
    345       return InnerMatcher.matches(*Node, Finder, Builder);
    346     }
    347    private:
    348     const Matcher<TypeT> InnerMatcher;
    349   };
    350 
    351 private:
    352   /// \brief Allows conversion from Matcher<Base> to Matcher<T> if T
    353   /// is derived from Base.
    354   template <typename Base>
    355   class ImplicitCastMatcher : public MatcherInterface<T> {
    356   public:
    357     explicit ImplicitCastMatcher(const Matcher<Base> &From)
    358         : From(From) {}
    359 
    360     virtual bool matches(const T &Node,
    361                          ASTMatchFinder *Finder,
    362                          BoundNodesTreeBuilder *Builder) const {
    363       return From.matches(Node, Finder, Builder);
    364     }
    365 
    366   private:
    367     const Matcher<Base> From;
    368   };
    369 
    370   /// \brief Simple MatcherInterface<T> wrapper around a DynTypedMatcher.
    371   class WrappedMatcher : public MatcherInterface<T> {
    372   public:
    373     explicit WrappedMatcher(const DynTypedMatcher &Matcher)
    374         : Inner(Matcher.clone()) {}
    375     virtual ~WrappedMatcher() {}
    376 
    377     bool matches(const T &Node, ASTMatchFinder *Finder,
    378                  BoundNodesTreeBuilder *Builder) const {
    379       return Inner->matches(ast_type_traits::DynTypedNode::create(Node), Finder,
    380                             Builder);
    381     }
    382 
    383   private:
    384     const OwningPtr<DynTypedMatcher> Inner;
    385   };
    386 
    387   IntrusiveRefCntPtr< MatcherInterface<T> > Implementation;
    388 };  // class Matcher
    389 
    390 /// \brief A convenient helper for creating a Matcher<T> without specifying
    391 /// the template type argument.
    392 template <typename T>
    393 inline Matcher<T> makeMatcher(MatcherInterface<T> *Implementation) {
    394   return Matcher<T>(Implementation);
    395 }
    396 
    397 /// \brief Specialization of the conversion functions for QualType.
    398 ///
    399 /// These specializations provide the Matcher<Type>->Matcher<QualType>
    400 /// conversion that the static API does.
    401 template <>
    402 inline bool
    403 Matcher<QualType>::canConstructFrom(const DynTypedMatcher &Other) {
    404   ast_type_traits::ASTNodeKind SourceKind = Other.getSupportedKind();
    405   // We support implicit conversion from Matcher<Type> to Matcher<QualType>
    406   return SourceKind.isSame(
    407              ast_type_traits::ASTNodeKind::getFromNodeKind<Type>()) ||
    408          SourceKind.isSame(
    409              ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>());
    410 }
    411 
    412 template <>
    413 inline Matcher<QualType>
    414 Matcher<QualType>::constructFrom(const DynTypedMatcher &Other) {
    415   assert(canConstructFrom(Other));
    416   ast_type_traits::ASTNodeKind SourceKind = Other.getSupportedKind();
    417   if (SourceKind.isSame(
    418           ast_type_traits::ASTNodeKind::getFromNodeKind<Type>())) {
    419     // We support implicit conversion from Matcher<Type> to Matcher<QualType>
    420     return Matcher<Type>::constructFrom(Other);
    421   }
    422   return makeMatcher(new WrappedMatcher(Other));
    423 }
    424 
    425 /// \brief Finds the first node in a range that matches the given matcher.
    426 template <typename MatcherT, typename IteratorT>
    427 bool matchesFirstInRange(const MatcherT &Matcher, IteratorT Start,
    428                          IteratorT End, ASTMatchFinder *Finder,
    429                          BoundNodesTreeBuilder *Builder) {
    430   for (IteratorT I = Start; I != End; ++I) {
    431     BoundNodesTreeBuilder Result(*Builder);
    432     if (Matcher.matches(*I, Finder, &Result)) {
    433       *Builder = Result;
    434       return true;
    435     }
    436   }
    437   return false;
    438 }
    439 
    440 /// \brief Finds the first node in a pointer range that matches the given
    441 /// matcher.
    442 template <typename MatcherT, typename IteratorT>
    443 bool matchesFirstInPointerRange(const MatcherT &Matcher, IteratorT Start,
    444                                 IteratorT End, ASTMatchFinder *Finder,
    445                                 BoundNodesTreeBuilder *Builder) {
    446   for (IteratorT I = Start; I != End; ++I) {
    447     BoundNodesTreeBuilder Result(*Builder);
    448     if (Matcher.matches(**I, Finder, &Result)) {
    449       *Builder = Result;
    450       return true;
    451     }
    452   }
    453   return false;
    454 }
    455 
    456 /// \brief Metafunction to determine if type T has a member called getDecl.
    457 template <typename T> struct has_getDecl {
    458   struct Default { int getDecl; };
    459   struct Derived : T, Default { };
    460 
    461   template<typename C, C> struct CheckT;
    462 
    463   // If T::getDecl exists, an ambiguity arises and CheckT will
    464   // not be instantiable. This makes f(...) the only available
    465   // overload.
    466   template<typename C>
    467   static char (&f(CheckT<int Default::*, &C::getDecl>*))[1];
    468   template<typename C> static char (&f(...))[2];
    469 
    470   static bool const value = sizeof(f<Derived>(0)) == 2;
    471 };
    472 
    473 /// \brief Matches overloaded operators with a specific name.
    474 ///
    475 /// The type argument ArgT is not used by this matcher but is used by
    476 /// PolymorphicMatcherWithParam1 and should be StringRef.
    477 template <typename T, typename ArgT>
    478 class HasOverloadedOperatorNameMatcher : public SingleNodeMatcherInterface<T> {
    479   TOOLING_COMPILE_ASSERT((llvm::is_same<T, CXXOperatorCallExpr>::value ||
    480                           llvm::is_same<T, CXXMethodDecl>::value),
    481                          unsupported_class_for_matcher);
    482   TOOLING_COMPILE_ASSERT((llvm::is_same<ArgT, StringRef>::value),
    483                          argument_type_must_be_StringRef);
    484 public:
    485   explicit HasOverloadedOperatorNameMatcher(const StringRef Name)
    486       : SingleNodeMatcherInterface<T>(), Name(Name) {}
    487 
    488   virtual bool matchesNode(const T &Node) const LLVM_OVERRIDE {
    489     return matchesSpecialized(Node);
    490   }
    491 
    492 private:
    493 
    494   /// \brief CXXOperatorCallExpr exist only for calls to overloaded operators
    495   /// so this function returns true if the call is to an operator of the given
    496   /// name.
    497   bool matchesSpecialized(const CXXOperatorCallExpr &Node) const {
    498     return getOperatorSpelling(Node.getOperator()) == Name;
    499   }
    500 
    501   /// \brief Returns true only if CXXMethodDecl represents an overloaded
    502   /// operator and has the given operator name.
    503   bool matchesSpecialized(const CXXMethodDecl &Node) const {
    504     return Node.isOverloadedOperator() &&
    505            getOperatorSpelling(Node.getOverloadedOperator()) == Name;
    506   }
    507 
    508   std::string Name;
    509 };
    510 
    511 /// \brief Matches declarations for QualType and CallExpr.
    512 ///
    513 /// Type argument DeclMatcherT is required by PolymorphicMatcherWithParam1 but
    514 /// not actually used.
    515 template <typename T, typename DeclMatcherT>
    516 class HasDeclarationMatcher : public MatcherInterface<T> {
    517   TOOLING_COMPILE_ASSERT((llvm::is_same< DeclMatcherT,
    518                                          Matcher<Decl> >::value),
    519                           instantiated_with_wrong_types);
    520 public:
    521   explicit HasDeclarationMatcher(const Matcher<Decl> &InnerMatcher)
    522       : InnerMatcher(InnerMatcher) {}
    523 
    524   virtual bool matches(const T &Node,
    525                        ASTMatchFinder *Finder,
    526                        BoundNodesTreeBuilder *Builder) const {
    527     return matchesSpecialized(Node, Finder, Builder);
    528   }
    529 
    530 private:
    531   /// \brief If getDecl exists as a member of U, returns whether the inner
    532   /// matcher matches Node.getDecl().
    533   template <typename U>
    534   bool matchesSpecialized(
    535       const U &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
    536       typename llvm::enable_if<has_getDecl<U>, int>::type = 0) const {
    537     return matchesDecl(Node.getDecl(), Finder, Builder);
    538   }
    539 
    540   /// \brief Extracts the CXXRecordDecl or EnumDecl of a QualType and returns
    541   /// whether the inner matcher matches on it.
    542   bool matchesSpecialized(const QualType &Node, ASTMatchFinder *Finder,
    543                           BoundNodesTreeBuilder *Builder) const {
    544     /// FIXME: Add other ways to convert...
    545     if (Node.isNull())
    546       return false;
    547     if (const EnumType *AsEnum = dyn_cast<EnumType>(Node.getTypePtr()))
    548       return matchesDecl(AsEnum->getDecl(), Finder, Builder);
    549     return matchesDecl(Node->getAsCXXRecordDecl(), Finder, Builder);
    550   }
    551 
    552   /// \brief Gets the TemplateDecl from a TemplateSpecializationType
    553   /// and returns whether the inner matches on it.
    554   bool matchesSpecialized(const TemplateSpecializationType &Node,
    555                           ASTMatchFinder *Finder,
    556                           BoundNodesTreeBuilder *Builder) const {
    557     return matchesDecl(Node.getTemplateName().getAsTemplateDecl(),
    558                        Finder, Builder);
    559   }
    560 
    561   /// \brief Extracts the Decl of the callee of a CallExpr and returns whether
    562   /// the inner matcher matches on it.
    563   bool matchesSpecialized(const CallExpr &Node, ASTMatchFinder *Finder,
    564                           BoundNodesTreeBuilder *Builder) const {
    565     return matchesDecl(Node.getCalleeDecl(), Finder, Builder);
    566   }
    567 
    568   /// \brief Extracts the Decl of the constructor call and returns whether the
    569   /// inner matcher matches on it.
    570   bool matchesSpecialized(const CXXConstructExpr &Node,
    571                           ASTMatchFinder *Finder,
    572                           BoundNodesTreeBuilder *Builder) const {
    573     return matchesDecl(Node.getConstructor(), Finder, Builder);
    574   }
    575 
    576   /// \brief Extracts the \c ValueDecl a \c MemberExpr refers to and returns
    577   /// whether the inner matcher matches on it.
    578   bool matchesSpecialized(const MemberExpr &Node,
    579                           ASTMatchFinder *Finder,
    580                           BoundNodesTreeBuilder *Builder) const {
    581     return matchesDecl(Node.getMemberDecl(), Finder, Builder);
    582   }
    583 
    584   /// \brief Returns whether the inner matcher \c Node. Returns false if \c Node
    585   /// is \c NULL.
    586   bool matchesDecl(const Decl *Node,
    587                    ASTMatchFinder *Finder,
    588                    BoundNodesTreeBuilder *Builder) const {
    589     return Node != NULL && InnerMatcher.matches(*Node, Finder, Builder);
    590   }
    591 
    592   const Matcher<Decl> InnerMatcher;
    593 };
    594 
    595 /// \brief IsBaseType<T>::value is true if T is a "base" type in the AST
    596 /// node class hierarchies.
    597 template <typename T>
    598 struct IsBaseType {
    599   static const bool value =
    600       (llvm::is_same<T, Decl>::value ||
    601        llvm::is_same<T, Stmt>::value ||
    602        llvm::is_same<T, QualType>::value ||
    603        llvm::is_same<T, Type>::value ||
    604        llvm::is_same<T, TypeLoc>::value ||
    605        llvm::is_same<T, NestedNameSpecifier>::value ||
    606        llvm::is_same<T, NestedNameSpecifierLoc>::value ||
    607        llvm::is_same<T, CXXCtorInitializer>::value);
    608 };
    609 template <typename T>
    610 const bool IsBaseType<T>::value;
    611 
    612 /// \brief Interface that allows matchers to traverse the AST.
    613 /// FIXME: Find a better name.
    614 ///
    615 /// This provides three entry methods for each base node type in the AST:
    616 /// - \c matchesChildOf:
    617 ///   Matches a matcher on every child node of the given node. Returns true
    618 ///   if at least one child node could be matched.
    619 /// - \c matchesDescendantOf:
    620 ///   Matches a matcher on all descendant nodes of the given node. Returns true
    621 ///   if at least one descendant matched.
    622 /// - \c matchesAncestorOf:
    623 ///   Matches a matcher on all ancestors of the given node. Returns true if
    624 ///   at least one ancestor matched.
    625 ///
    626 /// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal.
    627 /// In the future, we wan to implement this for all nodes for which it makes
    628 /// sense. In the case of matchesAncestorOf, we'll want to implement it for
    629 /// all nodes, as all nodes have ancestors.
    630 class ASTMatchFinder {
    631 public:
    632   /// \brief Defines how we descend a level in the AST when we pass
    633   /// through expressions.
    634   enum TraversalKind {
    635     /// Will traverse any child nodes.
    636     TK_AsIs,
    637     /// Will not traverse implicit casts and parentheses.
    638     TK_IgnoreImplicitCastsAndParentheses
    639   };
    640 
    641   /// \brief Defines how bindings are processed on recursive matches.
    642   enum BindKind {
    643     /// Stop at the first match and only bind the first match.
    644     BK_First,
    645     /// Create results for all combinations of bindings that match.
    646     BK_All
    647   };
    648 
    649   /// \brief Defines which ancestors are considered for a match.
    650   enum AncestorMatchMode {
    651     /// All ancestors.
    652     AMM_All,
    653     /// Direct parent only.
    654     AMM_ParentOnly
    655   };
    656 
    657   virtual ~ASTMatchFinder() {}
    658 
    659   /// \brief Returns true if the given class is directly or indirectly derived
    660   /// from a base type matching \c base.
    661   ///
    662   /// A class is considered to be also derived from itself.
    663   virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
    664                                   const Matcher<NamedDecl> &Base,
    665                                   BoundNodesTreeBuilder *Builder) = 0;
    666 
    667   template <typename T>
    668   bool matchesChildOf(const T &Node,
    669                       const DynTypedMatcher &Matcher,
    670                       BoundNodesTreeBuilder *Builder,
    671                       TraversalKind Traverse,
    672                       BindKind Bind) {
    673     TOOLING_COMPILE_ASSERT(
    674         (llvm::is_base_of<Decl, T>::value ||
    675          llvm::is_base_of<Stmt, T>::value ||
    676          llvm::is_base_of<NestedNameSpecifier, T>::value ||
    677          llvm::is_base_of<NestedNameSpecifierLoc, T>::value ||
    678          llvm::is_base_of<TypeLoc, T>::value ||
    679          llvm::is_base_of<QualType, T>::value),
    680         unsupported_type_for_recursive_matching);
    681    return matchesChildOf(ast_type_traits::DynTypedNode::create(Node),
    682                           Matcher, Builder, Traverse, Bind);
    683   }
    684 
    685   template <typename T>
    686   bool matchesDescendantOf(const T &Node,
    687                            const DynTypedMatcher &Matcher,
    688                            BoundNodesTreeBuilder *Builder,
    689                            BindKind Bind) {
    690     TOOLING_COMPILE_ASSERT(
    691         (llvm::is_base_of<Decl, T>::value ||
    692          llvm::is_base_of<Stmt, T>::value ||
    693          llvm::is_base_of<NestedNameSpecifier, T>::value ||
    694          llvm::is_base_of<NestedNameSpecifierLoc, T>::value ||
    695          llvm::is_base_of<TypeLoc, T>::value ||
    696          llvm::is_base_of<QualType, T>::value),
    697         unsupported_type_for_recursive_matching);
    698     return matchesDescendantOf(ast_type_traits::DynTypedNode::create(Node),
    699                                Matcher, Builder, Bind);
    700   }
    701 
    702   // FIXME: Implement support for BindKind.
    703   template <typename T>
    704   bool matchesAncestorOf(const T &Node,
    705                          const DynTypedMatcher &Matcher,
    706                          BoundNodesTreeBuilder *Builder,
    707                          AncestorMatchMode MatchMode) {
    708     TOOLING_COMPILE_ASSERT((llvm::is_base_of<Decl, T>::value ||
    709                             llvm::is_base_of<Stmt, T>::value),
    710                            only_Decl_or_Stmt_allowed_for_recursive_matching);
    711     return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node),
    712                              Matcher, Builder, MatchMode);
    713   }
    714 
    715   virtual ASTContext &getASTContext() const = 0;
    716 
    717 protected:
    718   virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
    719                               const DynTypedMatcher &Matcher,
    720                               BoundNodesTreeBuilder *Builder,
    721                               TraversalKind Traverse,
    722                               BindKind Bind) = 0;
    723 
    724   virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
    725                                    const DynTypedMatcher &Matcher,
    726                                    BoundNodesTreeBuilder *Builder,
    727                                    BindKind Bind) = 0;
    728 
    729   virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
    730                                  const DynTypedMatcher &Matcher,
    731                                  BoundNodesTreeBuilder *Builder,
    732                                  AncestorMatchMode MatchMode) = 0;
    733 };
    734 
    735 /// \brief A simple type-list implementation.
    736 ///
    737 /// It is implemented as a flat struct with a maximum number of arguments to
    738 /// simplify compiler error messages.
    739 /// However, it is used as a "linked list" of types.
    740 ///
    741 /// Note: If you need to extend for more types, add them as template arguments
    742 ///       and to the "typedef TypeList<...> tail" below. Nothing else is needed.
    743 template <typename T1 = void, typename T2 = void, typename T3 = void,
    744           typename T4 = void, typename T5 = void, typename T6 = void,
    745           typename T7 = void, typename T8 = void>
    746 struct TypeList {
    747   /// \brief The first type on the list.
    748   typedef T1 head;
    749 
    750   /// \brief A sub list with the tail. ie everything but the head.
    751   ///
    752   /// This type is used to do recursion. TypeList<>/EmptyTypeList indicates the
    753   /// end of the list.
    754   typedef TypeList<T2, T3, T4, T5, T6, T7, T8> tail;
    755 
    756   /// \brief Helper meta-function to determine if some type \c T is present or
    757   ///   a parent type in the list.
    758   template <typename T> struct ContainsSuperOf {
    759     static const bool value = llvm::is_base_of<head, T>::value ||
    760                               tail::template ContainsSuperOf<T>::value;
    761   };
    762 };
    763 
    764 /// \brief Specialization of ContainsSuperOf for the empty list.
    765 template <> template <typename T> struct TypeList<>::ContainsSuperOf {
    766   static const bool value = false;
    767 };
    768 
    769 /// \brief The empty type list.
    770 typedef TypeList<> EmptyTypeList;
    771 
    772 /// \brief A "type list" that contains all types.
    773 ///
    774 /// Useful for matchers like \c anything and \c unless.
    775 typedef TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc,
    776         QualType, Type, TypeLoc, CXXCtorInitializer> AllNodeBaseTypes;
    777 
    778 /// \brief Helper meta-function to extract the argument out of a function of
    779 ///   type void(Arg).
    780 ///
    781 /// See AST_POLYMORPHIC_SUPPORTED_TYPES_* for details.
    782 template <class T> struct ExtractFunctionArgMeta;
    783 template <class T> struct ExtractFunctionArgMeta<void(T)> {
    784   typedef T type;
    785 };
    786 
    787 /// \brief Default type lists for ArgumentAdaptingMatcher matchers.
    788 typedef AllNodeBaseTypes AdaptativeDefaultFromTypes;
    789 typedef TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc,
    790                  TypeLoc, QualType> AdaptativeDefaultToTypes;
    791 
    792 /// \brief Converts a \c Matcher<T> to a matcher of desired type \c To by
    793 /// "adapting" a \c To into a \c T.
    794 ///
    795 /// The \c ArgumentAdapterT argument specifies how the adaptation is done.
    796 ///
    797 /// For example:
    798 ///   \c ArgumentAdaptingMatcher<HasMatcher, T>(InnerMatcher);
    799 /// Given that \c InnerMatcher is of type \c Matcher<T>, this returns a matcher
    800 /// that is convertible into any matcher of type \c To by constructing
    801 /// \c HasMatcher<To, T>(InnerMatcher).
    802 ///
    803 /// If a matcher does not need knowledge about the inner type, prefer to use
    804 /// PolymorphicMatcherWithParam1.
    805 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
    806           typename T, typename FromTypes = AdaptativeDefaultFromTypes,
    807           typename ToTypes = AdaptativeDefaultToTypes>
    808 class ArgumentAdaptingMatcher {
    809 public:
    810   explicit ArgumentAdaptingMatcher(const Matcher<T> &InnerMatcher)
    811       : InnerMatcher(InnerMatcher) {}
    812 
    813   typedef ToTypes ReturnTypes;
    814 
    815   template <typename To>
    816   operator Matcher<To>() const {
    817     return Matcher<To>(new ArgumentAdapterT<To, T>(InnerMatcher));
    818   }
    819 
    820 private:
    821   const Matcher<T> InnerMatcher;
    822 };
    823 
    824 /// \brief A PolymorphicMatcherWithParamN<MatcherT, P1, ..., PN> object can be
    825 /// created from N parameters p1, ..., pN (of type P1, ..., PN) and
    826 /// used as a Matcher<T> where a MatcherT<T, P1, ..., PN>(p1, ..., pN)
    827 /// can be constructed.
    828 ///
    829 /// For example:
    830 /// - PolymorphicMatcherWithParam0<IsDefinitionMatcher>()
    831 ///   creates an object that can be used as a Matcher<T> for any type T
    832 ///   where an IsDefinitionMatcher<T>() can be constructed.
    833 /// - PolymorphicMatcherWithParam1<ValueEqualsMatcher, int>(42)
    834 ///   creates an object that can be used as a Matcher<T> for any type T
    835 ///   where a ValueEqualsMatcher<T, int>(42) can be constructed.
    836 template <template <typename T> class MatcherT,
    837           typename ReturnTypesF = void(AllNodeBaseTypes)>
    838 class PolymorphicMatcherWithParam0 {
    839 public:
    840   typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes;
    841   template <typename T>
    842   operator Matcher<T>() const {
    843     TOOLING_COMPILE_ASSERT(ReturnTypes::template ContainsSuperOf<T>::value,
    844                            right_polymorphic_conversion);
    845     return Matcher<T>(new MatcherT<T>());
    846   }
    847 };
    848 
    849 template <template <typename T, typename P1> class MatcherT,
    850           typename P1,
    851           typename ReturnTypesF = void(AllNodeBaseTypes)>
    852 class PolymorphicMatcherWithParam1 {
    853 public:
    854   explicit PolymorphicMatcherWithParam1(const P1 &Param1)
    855       : Param1(Param1) {}
    856 
    857   typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes;
    858 
    859   template <typename T>
    860   operator Matcher<T>() const {
    861     TOOLING_COMPILE_ASSERT(ReturnTypes::template ContainsSuperOf<T>::value,
    862                            right_polymorphic_conversion);
    863     return Matcher<T>(new MatcherT<T, P1>(Param1));
    864   }
    865 
    866 private:
    867   const P1 Param1;
    868 };
    869 
    870 template <template <typename T, typename P1, typename P2> class MatcherT,
    871           typename P1, typename P2,
    872           typename ReturnTypesF = void(AllNodeBaseTypes)>
    873 class PolymorphicMatcherWithParam2 {
    874 public:
    875   PolymorphicMatcherWithParam2(const P1 &Param1, const P2 &Param2)
    876       : Param1(Param1), Param2(Param2) {}
    877 
    878   typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes;
    879 
    880   template <typename T>
    881   operator Matcher<T>() const {
    882     TOOLING_COMPILE_ASSERT(ReturnTypes::template ContainsSuperOf<T>::value,
    883                            right_polymorphic_conversion);
    884     return Matcher<T>(new MatcherT<T, P1, P2>(Param1, Param2));
    885   }
    886 
    887 private:
    888   const P1 Param1;
    889   const P2 Param2;
    890 };
    891 
    892 /// \brief Matches any instance of the given NodeType.
    893 ///
    894 /// This is useful when a matcher syntactically requires a child matcher,
    895 /// but the context doesn't care. See for example: anything().
    896 ///
    897 /// FIXME: Alternatively we could also create a IsAMatcher or something
    898 /// that checks that a dyn_cast is possible. This is purely needed for the
    899 /// difference between calling for example:
    900 ///   record()
    901 /// and
    902 ///   record(SomeMatcher)
    903 /// In the second case we need the correct type we were dyn_cast'ed to in order
    904 /// to get the right type for the inner matcher. In the first case we don't need
    905 /// that, but we use the type conversion anyway and insert a TrueMatcher.
    906 template <typename T>
    907 class TrueMatcher : public SingleNodeMatcherInterface<T>  {
    908 public:
    909   virtual bool matchesNode(const T &Node) const {
    910     return true;
    911   }
    912 };
    913 
    914 /// \brief Provides a MatcherInterface<T> for a Matcher<To> that matches if T is
    915 /// dyn_cast'able into To and the given Matcher<To> matches on the dyn_cast'ed
    916 /// node.
    917 template <typename T, typename To>
    918 class DynCastMatcher : public MatcherInterface<T> {
    919 public:
    920   explicit DynCastMatcher(const Matcher<To> &InnerMatcher)
    921       : InnerMatcher(InnerMatcher) {}
    922 
    923   virtual bool matches(const T &Node,
    924                        ASTMatchFinder *Finder,
    925                        BoundNodesTreeBuilder *Builder) const {
    926     const To *InnerMatchValue = dyn_cast<To>(&Node);
    927     return InnerMatchValue != NULL &&
    928       InnerMatcher.matches(*InnerMatchValue, Finder, Builder);
    929   }
    930 
    931 private:
    932   const Matcher<To> InnerMatcher;
    933 };
    934 
    935 /// \brief Matcher<T> that wraps an inner Matcher<T> and binds the matched node
    936 /// to an ID if the inner matcher matches on the node.
    937 template <typename T>
    938 class IdMatcher : public MatcherInterface<T> {
    939 public:
    940   /// \brief Creates an IdMatcher that binds to 'ID' if 'InnerMatcher' matches
    941   /// the node.
    942   IdMatcher(StringRef ID, const Matcher<T> &InnerMatcher)
    943       : ID(ID), InnerMatcher(InnerMatcher) {}
    944 
    945   virtual bool matches(const T &Node,
    946                        ASTMatchFinder *Finder,
    947                        BoundNodesTreeBuilder *Builder) const {
    948     bool Result = InnerMatcher.matches(Node, Finder, Builder);
    949     if (Result) {
    950       Builder->setBinding(ID, &Node);
    951     }
    952     return Result;
    953   }
    954 
    955 private:
    956   const std::string ID;
    957   const Matcher<T> InnerMatcher;
    958 };
    959 
    960 /// \brief A Matcher that allows binding the node it matches to an id.
    961 ///
    962 /// BindableMatcher provides a \a bind() method that allows binding the
    963 /// matched node to an id if the match was successful.
    964 template <typename T>
    965 class BindableMatcher : public Matcher<T> {
    966 public:
    967   BindableMatcher(MatcherInterface<T> *Implementation)
    968     : Matcher<T>(Implementation) {}
    969 
    970   /// \brief Returns a matcher that will bind the matched node on a match.
    971   ///
    972   /// The returned matcher is equivalent to this matcher, but will
    973   /// bind the matched node on a match.
    974   Matcher<T> bind(StringRef ID) const {
    975     return Matcher<T>(new IdMatcher<T>(ID, *this));
    976   }
    977 
    978   /// \brief Makes a copy of this matcher object.
    979   virtual BindableMatcher<T>* clone() const {
    980     return new BindableMatcher<T>(*this);
    981   }
    982 
    983   /// \brief Bind the specified \c ID to the matcher.
    984   virtual Matcher<T>* tryBind(StringRef ID) const {
    985     return new Matcher<T>(bind(ID));
    986   }
    987 };
    988 
    989 /// \brief Matches nodes of type T that have child nodes of type ChildT for
    990 /// which a specified child matcher matches.
    991 ///
    992 /// ChildT must be an AST base type.
    993 template <typename T, typename ChildT>
    994 class HasMatcher : public MatcherInterface<T> {
    995   TOOLING_COMPILE_ASSERT(IsBaseType<ChildT>::value,
    996                          has_only_accepts_base_type_matcher);
    997 public:
    998   explicit HasMatcher(const Matcher<ChildT> &ChildMatcher)
    999       : ChildMatcher(ChildMatcher) {}
   1000 
   1001   virtual bool matches(const T &Node,
   1002                        ASTMatchFinder *Finder,
   1003                        BoundNodesTreeBuilder *Builder) const {
   1004     return Finder->matchesChildOf(
   1005         Node, ChildMatcher, Builder,
   1006         ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses,
   1007         ASTMatchFinder::BK_First);
   1008   }
   1009 
   1010  private:
   1011   const Matcher<ChildT> ChildMatcher;
   1012 };
   1013 
   1014 /// \brief Matches nodes of type T that have child nodes of type ChildT for
   1015 /// which a specified child matcher matches. ChildT must be an AST base
   1016 /// type.
   1017 /// As opposed to the HasMatcher, the ForEachMatcher will produce a match
   1018 /// for each child that matches.
   1019 template <typename T, typename ChildT>
   1020 class ForEachMatcher : public MatcherInterface<T> {
   1021   TOOLING_COMPILE_ASSERT(IsBaseType<ChildT>::value,
   1022                          for_each_only_accepts_base_type_matcher);
   1023  public:
   1024   explicit ForEachMatcher(const Matcher<ChildT> &ChildMatcher)
   1025       : ChildMatcher(ChildMatcher) {}
   1026 
   1027   virtual bool matches(const T& Node,
   1028                        ASTMatchFinder* Finder,
   1029                        BoundNodesTreeBuilder* Builder) const {
   1030     return Finder->matchesChildOf(
   1031       Node, ChildMatcher, Builder,
   1032       ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses,
   1033       ASTMatchFinder::BK_All);
   1034   }
   1035 
   1036 private:
   1037   const Matcher<ChildT> ChildMatcher;
   1038 };
   1039 
   1040 /// \brief Matches nodes of type T if the given Matcher<T> does not match.
   1041 ///
   1042 /// Type argument MatcherT is required by PolymorphicMatcherWithParam1
   1043 /// but not actually used. It will always be instantiated with a type
   1044 /// convertible to Matcher<T>.
   1045 template <typename T, typename MatcherT>
   1046 class NotMatcher : public MatcherInterface<T> {
   1047 public:
   1048   explicit NotMatcher(const Matcher<T> &InnerMatcher)
   1049       : InnerMatcher(InnerMatcher) {}
   1050 
   1051   virtual bool matches(const T &Node,
   1052                        ASTMatchFinder *Finder,
   1053                        BoundNodesTreeBuilder *Builder) const {
   1054     // The 'unless' matcher will always discard the result:
   1055     // If the inner matcher doesn't match, unless returns true,
   1056     // but the inner matcher cannot have bound anything.
   1057     // If the inner matcher matches, the result is false, and
   1058     // any possible binding will be discarded.
   1059     // We still need to hand in all the bound nodes up to this
   1060     // point so the inner matcher can depend on bound nodes,
   1061     // and we need to actively discard the bound nodes, otherwise
   1062     // the inner matcher will reset the bound nodes if it doesn't
   1063     // match, but this would be inversed by 'unless'.
   1064     BoundNodesTreeBuilder Discard(*Builder);
   1065     return !InnerMatcher.matches(Node, Finder, &Discard);
   1066   }
   1067 
   1068 private:
   1069   const Matcher<T> InnerMatcher;
   1070 };
   1071 
   1072 /// \brief Matches nodes of type T for which both provided matchers match.
   1073 ///
   1074 /// Type arguments MatcherT1 and MatcherT2 are required by
   1075 /// PolymorphicMatcherWithParam2 but not actually used. They will
   1076 /// always be instantiated with types convertible to Matcher<T>.
   1077 template <typename T, typename MatcherT1, typename MatcherT2>
   1078 class AllOfMatcher : public MatcherInterface<T> {
   1079 public:
   1080   AllOfMatcher(const Matcher<T> &InnerMatcher1, const Matcher<T> &InnerMatcher2)
   1081       : InnerMatcher1(InnerMatcher1), InnerMatcher2(InnerMatcher2) {}
   1082 
   1083   virtual bool matches(const T &Node,
   1084                        ASTMatchFinder *Finder,
   1085                        BoundNodesTreeBuilder *Builder) const {
   1086     // allOf leads to one matcher for each alternative in the first
   1087     // matcher combined with each alternative in the second matcher.
   1088     // Thus, we can reuse the same Builder.
   1089     return InnerMatcher1.matches(Node, Finder, Builder) &&
   1090            InnerMatcher2.matches(Node, Finder, Builder);
   1091   }
   1092 
   1093 private:
   1094   const Matcher<T> InnerMatcher1;
   1095   const Matcher<T> InnerMatcher2;
   1096 };
   1097 
   1098 /// \brief Matches nodes of type T for which at least one of the two provided
   1099 /// matchers matches.
   1100 ///
   1101 /// Type arguments MatcherT1 and MatcherT2 are
   1102 /// required by PolymorphicMatcherWithParam2 but not actually
   1103 /// used. They will always be instantiated with types convertible to
   1104 /// Matcher<T>.
   1105 template <typename T, typename MatcherT1, typename MatcherT2>
   1106 class EachOfMatcher : public MatcherInterface<T> {
   1107 public:
   1108   EachOfMatcher(const Matcher<T> &InnerMatcher1,
   1109                 const Matcher<T> &InnerMatcher2)
   1110       : InnerMatcher1(InnerMatcher1), InnerMatcher2(InnerMatcher2) {
   1111   }
   1112 
   1113   virtual bool matches(const T &Node, ASTMatchFinder *Finder,
   1114                        BoundNodesTreeBuilder *Builder) const {
   1115     BoundNodesTreeBuilder Result;
   1116     BoundNodesTreeBuilder Builder1(*Builder);
   1117     bool Matched1 = InnerMatcher1.matches(Node, Finder, &Builder1);
   1118     if (Matched1)
   1119       Result.addMatch(Builder1);
   1120 
   1121     BoundNodesTreeBuilder Builder2(*Builder);
   1122     bool Matched2 = InnerMatcher2.matches(Node, Finder, &Builder2);
   1123     if (Matched2)
   1124       Result.addMatch(Builder2);
   1125 
   1126     *Builder = Result;
   1127     return Matched1 || Matched2;
   1128   }
   1129 
   1130 private:
   1131   const Matcher<T> InnerMatcher1;
   1132   const Matcher<T> InnerMatcher2;
   1133 };
   1134 
   1135 /// \brief Matches nodes of type T for which at least one of the two provided
   1136 /// matchers matches.
   1137 ///
   1138 /// Type arguments MatcherT1 and MatcherT2 are
   1139 /// required by PolymorphicMatcherWithParam2 but not actually
   1140 /// used. They will always be instantiated with types convertible to
   1141 /// Matcher<T>.
   1142 template <typename T, typename MatcherT1, typename MatcherT2>
   1143 class AnyOfMatcher : public MatcherInterface<T> {
   1144 public:
   1145   AnyOfMatcher(const Matcher<T> &InnerMatcher1, const Matcher<T> &InnerMatcher2)
   1146       : InnerMatcher1(InnerMatcher1), InnerMatcher2(InnerMatcher2) {}
   1147 
   1148   virtual bool matches(const T &Node,
   1149                        ASTMatchFinder *Finder,
   1150                        BoundNodesTreeBuilder *Builder) const {
   1151     BoundNodesTreeBuilder Result = *Builder;
   1152     if (InnerMatcher1.matches(Node, Finder, &Result)) {
   1153       *Builder = Result;
   1154       return true;
   1155     }
   1156     Result = *Builder;
   1157     if (InnerMatcher2.matches(Node, Finder, &Result)) {
   1158       *Builder = Result;
   1159       return true;
   1160     }
   1161     return false;
   1162   }
   1163 
   1164 private:
   1165   const Matcher<T> InnerMatcher1;
   1166   const Matcher<T> InnerMatcher2;
   1167 };
   1168 
   1169 /// \brief Creates a Matcher<T> that matches if all inner matchers match.
   1170 template<typename T>
   1171 BindableMatcher<T> makeAllOfComposite(
   1172     ArrayRef<const Matcher<T> *> InnerMatchers) {
   1173   if (InnerMatchers.empty())
   1174     return BindableMatcher<T>(new TrueMatcher<T>);
   1175   MatcherInterface<T> *InnerMatcher = new TrueMatcher<T>;
   1176   for (int i = InnerMatchers.size() - 1; i >= 0; --i) {
   1177     InnerMatcher = new AllOfMatcher<T, Matcher<T>, Matcher<T> >(
   1178       *InnerMatchers[i], makeMatcher(InnerMatcher));
   1179   }
   1180   return BindableMatcher<T>(InnerMatcher);
   1181 }
   1182 
   1183 /// \brief Creates a Matcher<T> that matches if
   1184 /// T is dyn_cast'able into InnerT and all inner matchers match.
   1185 ///
   1186 /// Returns BindableMatcher, as matchers that use dyn_cast have
   1187 /// the same object both to match on and to run submatchers on,
   1188 /// so there is no ambiguity with what gets bound.
   1189 template<typename T, typename InnerT>
   1190 BindableMatcher<T> makeDynCastAllOfComposite(
   1191     ArrayRef<const Matcher<InnerT> *> InnerMatchers) {
   1192   return BindableMatcher<T>(new DynCastMatcher<T, InnerT>(
   1193     makeAllOfComposite(InnerMatchers)));
   1194 }
   1195 
   1196 /// \brief Matches nodes of type T that have at least one descendant node of
   1197 /// type DescendantT for which the given inner matcher matches.
   1198 ///
   1199 /// DescendantT must be an AST base type.
   1200 template <typename T, typename DescendantT>
   1201 class HasDescendantMatcher : public MatcherInterface<T> {
   1202   TOOLING_COMPILE_ASSERT(IsBaseType<DescendantT>::value,
   1203                          has_descendant_only_accepts_base_type_matcher);
   1204 public:
   1205   explicit HasDescendantMatcher(const Matcher<DescendantT> &DescendantMatcher)
   1206       : DescendantMatcher(DescendantMatcher) {}
   1207 
   1208   virtual bool matches(const T &Node,
   1209                        ASTMatchFinder *Finder,
   1210                        BoundNodesTreeBuilder *Builder) const {
   1211     return Finder->matchesDescendantOf(
   1212         Node, DescendantMatcher, Builder, ASTMatchFinder::BK_First);
   1213   }
   1214 
   1215  private:
   1216   const Matcher<DescendantT> DescendantMatcher;
   1217 };
   1218 
   1219 /// \brief Matches nodes of type \c T that have a parent node of type \c ParentT
   1220 /// for which the given inner matcher matches.
   1221 ///
   1222 /// \c ParentT must be an AST base type.
   1223 template <typename T, typename ParentT>
   1224 class HasParentMatcher : public MatcherInterface<T> {
   1225   TOOLING_COMPILE_ASSERT(IsBaseType<ParentT>::value,
   1226                          has_parent_only_accepts_base_type_matcher);
   1227 public:
   1228   explicit HasParentMatcher(const Matcher<ParentT> &ParentMatcher)
   1229       : ParentMatcher(ParentMatcher) {}
   1230 
   1231   virtual bool matches(const T &Node,
   1232                        ASTMatchFinder *Finder,
   1233                        BoundNodesTreeBuilder *Builder) const {
   1234     return Finder->matchesAncestorOf(
   1235         Node, ParentMatcher, Builder, ASTMatchFinder::AMM_ParentOnly);
   1236   }
   1237 
   1238  private:
   1239   const Matcher<ParentT> ParentMatcher;
   1240 };
   1241 
   1242 /// \brief Matches nodes of type \c T that have at least one ancestor node of
   1243 /// type \c AncestorT for which the given inner matcher matches.
   1244 ///
   1245 /// \c AncestorT must be an AST base type.
   1246 template <typename T, typename AncestorT>
   1247 class HasAncestorMatcher : public MatcherInterface<T> {
   1248   TOOLING_COMPILE_ASSERT(IsBaseType<AncestorT>::value,
   1249                          has_ancestor_only_accepts_base_type_matcher);
   1250 public:
   1251   explicit HasAncestorMatcher(const Matcher<AncestorT> &AncestorMatcher)
   1252       : AncestorMatcher(AncestorMatcher) {}
   1253 
   1254   virtual bool matches(const T &Node,
   1255                        ASTMatchFinder *Finder,
   1256                        BoundNodesTreeBuilder *Builder) const {
   1257     return Finder->matchesAncestorOf(
   1258         Node, AncestorMatcher, Builder, ASTMatchFinder::AMM_All);
   1259   }
   1260 
   1261  private:
   1262   const Matcher<AncestorT> AncestorMatcher;
   1263 };
   1264 
   1265 /// \brief Matches nodes of type T that have at least one descendant node of
   1266 /// type DescendantT for which the given inner matcher matches.
   1267 ///
   1268 /// DescendantT must be an AST base type.
   1269 /// As opposed to HasDescendantMatcher, ForEachDescendantMatcher will match
   1270 /// for each descendant node that matches instead of only for the first.
   1271 template <typename T, typename DescendantT>
   1272 class ForEachDescendantMatcher : public MatcherInterface<T> {
   1273   TOOLING_COMPILE_ASSERT(IsBaseType<DescendantT>::value,
   1274                          for_each_descendant_only_accepts_base_type_matcher);
   1275  public:
   1276   explicit ForEachDescendantMatcher(
   1277       const Matcher<DescendantT>& DescendantMatcher)
   1278       : DescendantMatcher(DescendantMatcher) {}
   1279 
   1280   virtual bool matches(const T& Node,
   1281                        ASTMatchFinder* Finder,
   1282                        BoundNodesTreeBuilder* Builder) const {
   1283     return Finder->matchesDescendantOf(Node, DescendantMatcher, Builder,
   1284                                        ASTMatchFinder::BK_All);
   1285   }
   1286 
   1287 private:
   1288   const Matcher<DescendantT> DescendantMatcher;
   1289 };
   1290 
   1291 /// \brief Matches on nodes that have a getValue() method if getValue() equals
   1292 /// the value the ValueEqualsMatcher was constructed with.
   1293 template <typename T, typename ValueT>
   1294 class ValueEqualsMatcher : public SingleNodeMatcherInterface<T> {
   1295   TOOLING_COMPILE_ASSERT((llvm::is_base_of<CharacterLiteral, T>::value ||
   1296                          llvm::is_base_of<CXXBoolLiteralExpr,
   1297                                           T>::value ||
   1298                          llvm::is_base_of<FloatingLiteral, T>::value ||
   1299                          llvm::is_base_of<IntegerLiteral, T>::value),
   1300                          the_node_must_have_a_getValue_method);
   1301 public:
   1302   explicit ValueEqualsMatcher(const ValueT &ExpectedValue)
   1303       : ExpectedValue(ExpectedValue) {}
   1304 
   1305   virtual bool matchesNode(const T &Node) const {
   1306     return Node.getValue() == ExpectedValue;
   1307   }
   1308 
   1309 private:
   1310   const ValueT ExpectedValue;
   1311 };
   1312 
   1313 /// \brief A VariadicDynCastAllOfMatcher<SourceT, TargetT> object is a
   1314 /// variadic functor that takes a number of Matcher<TargetT> and returns a
   1315 /// Matcher<SourceT> that matches TargetT nodes that are matched by all of the
   1316 /// given matchers, if SourceT can be dynamically casted into TargetT.
   1317 ///
   1318 /// For example:
   1319 ///   const VariadicDynCastAllOfMatcher<
   1320 ///       Decl, CXXRecordDecl> record;
   1321 /// Creates a functor record(...) that creates a Matcher<Decl> given
   1322 /// a variable number of arguments of type Matcher<CXXRecordDecl>.
   1323 /// The returned matcher matches if the given Decl can by dynamically
   1324 /// casted to CXXRecordDecl and all given matchers match.
   1325 template <typename SourceT, typename TargetT>
   1326 class VariadicDynCastAllOfMatcher
   1327     : public llvm::VariadicFunction<
   1328         BindableMatcher<SourceT>, Matcher<TargetT>,
   1329         makeDynCastAllOfComposite<SourceT, TargetT> > {
   1330 public:
   1331   VariadicDynCastAllOfMatcher() {}
   1332 };
   1333 
   1334 /// \brief A \c VariadicAllOfMatcher<T> object is a variadic functor that takes
   1335 /// a number of \c Matcher<T> and returns a \c Matcher<T> that matches \c T
   1336 /// nodes that are matched by all of the given matchers.
   1337 ///
   1338 /// For example:
   1339 ///   const VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier;
   1340 /// Creates a functor nestedNameSpecifier(...) that creates a
   1341 /// \c Matcher<NestedNameSpecifier> given a variable number of arguments of type
   1342 /// \c Matcher<NestedNameSpecifier>.
   1343 /// The returned matcher matches if all given matchers match.
   1344 template <typename T>
   1345 class VariadicAllOfMatcher : public llvm::VariadicFunction<
   1346                                BindableMatcher<T>, Matcher<T>,
   1347                                makeAllOfComposite<T> > {
   1348 public:
   1349   VariadicAllOfMatcher() {}
   1350 };
   1351 
   1352 /// \brief Matches nodes of type \c TLoc for which the inner
   1353 /// \c Matcher<T> matches.
   1354 template <typename TLoc, typename T>
   1355 class LocMatcher : public MatcherInterface<TLoc> {
   1356 public:
   1357   explicit LocMatcher(const Matcher<T> &InnerMatcher)
   1358     : InnerMatcher(InnerMatcher) {}
   1359 
   1360   virtual bool matches(const TLoc &Node,
   1361                        ASTMatchFinder *Finder,
   1362                        BoundNodesTreeBuilder *Builder) const {
   1363     if (!Node)
   1364       return false;
   1365     return InnerMatcher.matches(*extract(Node), Finder, Builder);
   1366   }
   1367 
   1368 private:
   1369   const NestedNameSpecifier *extract(const NestedNameSpecifierLoc &Loc) const {
   1370     return Loc.getNestedNameSpecifier();
   1371   }
   1372 
   1373   const Matcher<T> InnerMatcher;
   1374 };
   1375 
   1376 /// \brief Matches \c TypeLocs based on an inner matcher matching a certain
   1377 /// \c QualType.
   1378 ///
   1379 /// Used to implement the \c loc() matcher.
   1380 class TypeLocTypeMatcher : public MatcherInterface<TypeLoc> {
   1381 public:
   1382   explicit TypeLocTypeMatcher(const Matcher<QualType> &InnerMatcher)
   1383       : InnerMatcher(InnerMatcher) {}
   1384 
   1385   virtual bool matches(const TypeLoc &Node,
   1386                        ASTMatchFinder *Finder,
   1387                        BoundNodesTreeBuilder *Builder) const {
   1388     if (!Node)
   1389       return false;
   1390     return InnerMatcher.matches(Node.getType(), Finder, Builder);
   1391   }
   1392 
   1393 private:
   1394   const Matcher<QualType> InnerMatcher;
   1395 };
   1396 
   1397 /// \brief Matches nodes of type \c T for which the inner matcher matches on a
   1398 /// another node of type \c T that can be reached using a given traverse
   1399 /// function.
   1400 template <typename T>
   1401 class TypeTraverseMatcher : public MatcherInterface<T> {
   1402 public:
   1403   explicit TypeTraverseMatcher(const Matcher<QualType> &InnerMatcher,
   1404                                QualType (T::*TraverseFunction)() const)
   1405       : InnerMatcher(InnerMatcher), TraverseFunction(TraverseFunction) {}
   1406 
   1407   virtual bool matches(const T &Node,
   1408                        ASTMatchFinder *Finder,
   1409                        BoundNodesTreeBuilder *Builder) const {
   1410     QualType NextNode = (Node.*TraverseFunction)();
   1411     if (NextNode.isNull())
   1412       return false;
   1413     return InnerMatcher.matches(NextNode, Finder, Builder);
   1414   }
   1415 
   1416 private:
   1417   const Matcher<QualType> InnerMatcher;
   1418   QualType (T::*TraverseFunction)() const;
   1419 };
   1420 
   1421 /// \brief Matches nodes of type \c T in a ..Loc hierarchy, for which the inner
   1422 /// matcher matches on a another node of type \c T that can be reached using a
   1423 /// given traverse function.
   1424 template <typename T>
   1425 class TypeLocTraverseMatcher : public MatcherInterface<T> {
   1426 public:
   1427   explicit TypeLocTraverseMatcher(const Matcher<TypeLoc> &InnerMatcher,
   1428                                   TypeLoc (T::*TraverseFunction)() const)
   1429       : InnerMatcher(InnerMatcher), TraverseFunction(TraverseFunction) {}
   1430 
   1431   virtual bool matches(const T &Node,
   1432                        ASTMatchFinder *Finder,
   1433                        BoundNodesTreeBuilder *Builder) const {
   1434     TypeLoc NextNode = (Node.*TraverseFunction)();
   1435     if (!NextNode)
   1436       return false;
   1437     return InnerMatcher.matches(NextNode, Finder, Builder);
   1438   }
   1439 
   1440 private:
   1441   const Matcher<TypeLoc> InnerMatcher;
   1442   TypeLoc (T::*TraverseFunction)() const;
   1443 };
   1444 
   1445 /// \brief Converts a \c Matcher<InnerT> to a \c Matcher<OuterT>, where
   1446 /// \c OuterT is any type that is supported by \c Getter.
   1447 ///
   1448 /// \code Getter<OuterT>::value() \endcode returns a
   1449 /// \code InnerTBase (OuterT::*)() \endcode, which is used to adapt a \c OuterT
   1450 /// object into a \c InnerT
   1451 template <typename InnerTBase,
   1452           template <typename OuterT> class Getter,
   1453           template <typename OuterT> class MatcherImpl,
   1454           typename ReturnTypesF>
   1455 class TypeTraversePolymorphicMatcher {
   1456 private:
   1457   typedef TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl,
   1458                                          ReturnTypesF> Self;
   1459   static Self create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers);
   1460 
   1461 public:
   1462   typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes;
   1463 
   1464   explicit TypeTraversePolymorphicMatcher(
   1465       ArrayRef<const Matcher<InnerTBase> *> InnerMatchers)
   1466       : InnerMatcher(makeAllOfComposite(InnerMatchers)) {}
   1467 
   1468   template <typename OuterT> operator Matcher<OuterT>() const {
   1469     return Matcher<OuterT>(
   1470         new MatcherImpl<OuterT>(InnerMatcher, Getter<OuterT>::value()));
   1471   }
   1472 
   1473   struct Func : public llvm::VariadicFunction<Self, Matcher<InnerTBase>,
   1474                                               &Self::create> {
   1475     Func() {}
   1476   };
   1477 
   1478 private:
   1479   const Matcher<InnerTBase> InnerMatcher;
   1480 };
   1481 
   1482 // Define the create() method out of line to silence a GCC warning about
   1483 // the struct "Func" having greater visibility than its base, which comes from
   1484 // using the flag -fvisibility-inlines-hidden.
   1485 template <typename InnerTBase, template <typename OuterT> class Getter,
   1486           template <typename OuterT> class MatcherImpl, typename ReturnTypesF>
   1487 TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, ReturnTypesF>
   1488 TypeTraversePolymorphicMatcher<
   1489     InnerTBase, Getter, MatcherImpl,
   1490     ReturnTypesF>::create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) {
   1491   return Self(InnerMatchers);
   1492 }
   1493 
   1494 } // end namespace internal
   1495 } // end namespace ast_matchers
   1496 } // end namespace clang
   1497 
   1498 #endif // LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_INTERNAL_H
   1499