contrib/llvm/tools/clang/include/clang/ASTMatchers/ASTMatchersInternal.h

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