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