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