clang/include/clang/ASTMatchers/ASTMatchersInternal.h

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