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