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