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