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 \c ValueDecl a \c MemberExpr refers to and returns
 791   /// whether the inner matcher matches on it.
 792   bool matchesSpecialized(const MemberExpr &Node,
 793                           ASTMatchFinder *Finder,
 794                           BoundNodesTreeBuilder *Builder) const {
 795     return matchesDecl(Node.getMemberDecl(), Finder, Builder);
 796   }
 797
 798   /// \brief Extracts the \c LabelDecl a \c AddrLabelExpr refers to and returns
 799   /// whether the inner matcher matches on it.
 800   bool matchesSpecialized(const AddrLabelExpr &Node,
 801                           ASTMatchFinder *Finder,
 802                           BoundNodesTreeBuilder *Builder) const {
 803     return matchesDecl(Node.getLabel(), Finder, Builder);
 804   }
 805
 806   /// \brief Returns whether the inner matcher \c Node. Returns false if \c Node
 807   /// is \c NULL.
 808   bool matchesDecl(const Decl *Node, ASTMatchFinder *Finder,
 809                    BoundNodesTreeBuilder *Builder) const {
 810     return Node != nullptr &&
 811            this->InnerMatcher.matches(
 812                ast_type_traits::DynTypedNode::create(*Node), Finder, Builder);
 813   }
 814 };
 815
 816 /// \brief IsBaseType<T>::value is true if T is a "base" type in the AST
 817 /// node class hierarchies.
 818 template <typename T>
 819 struct IsBaseType {
 820   static const bool value =
 821       std::is_same<T, Decl>::value ||
 822       std::is_same<T, Stmt>::value ||
 823       std::is_same<T, QualType>::value ||
 824       std::is_same<T, Type>::value ||
 825       std::is_same<T, TypeLoc>::value ||
 826       std::is_same<T, NestedNameSpecifier>::value ||
 827       std::is_same<T, NestedNameSpecifierLoc>::value ||
 828       std::is_same<T, CXXCtorInitializer>::value;
 829 };
 830 template <typename T>
 831 const bool IsBaseType<T>::value;
 832
 833 /// \brief Interface that allows matchers to traverse the AST.
 834 /// FIXME: Find a better name.
 835 ///
 836 /// This provides three entry methods for each base node type in the AST:
 837 /// - \c matchesChildOf:
 838 ///   Matches a matcher on every child node of the given node. Returns true
 839 ///   if at least one child node could be matched.
 840 /// - \c matchesDescendantOf:
 841 ///   Matches a matcher on all descendant nodes of the given node. Returns true
 842 ///   if at least one descendant matched.
 843 /// - \c matchesAncestorOf:
 844 ///   Matches a matcher on all ancestors of the given node. Returns true if
 845 ///   at least one ancestor matched.
 846 ///
 847 /// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal.
 848 /// In the future, we want to implement this for all nodes for which it makes
 849 /// sense. In the case of matchesAncestorOf, we'll want to implement it for
 850 /// all nodes, as all nodes have ancestors.
 851 class ASTMatchFinder {
 852 public:
 853   /// \brief Defines how we descend a level in the AST when we pass
 854   /// through expressions.
 855   enum TraversalKind {
 856     /// Will traverse any child nodes.
 857     TK_AsIs,
 858     /// Will not traverse implicit casts and parentheses.
 859     TK_IgnoreImplicitCastsAndParentheses
 860   };
 861
 862   /// \brief Defines how bindings are processed on recursive matches.
 863   enum BindKind {
 864     /// Stop at the first match and only bind the first match.
 865     BK_First,
 866     /// Create results for all combinations of bindings that match.
 867     BK_All
 868   };
 869
 870   /// \brief Defines which ancestors are considered for a match.
 871   enum AncestorMatchMode {
 872     /// All ancestors.
 873     AMM_All,
 874     /// Direct parent only.
 875     AMM_ParentOnly
 876   };
 877
 878   virtual ~ASTMatchFinder() {}
 879
 880   /// \brief Returns true if the given class is directly or indirectly derived
 881   /// from a base type matching \c base.
 882   ///
 883   /// A class is considered to be also derived from itself.
 884   virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
 885                                   const Matcher<NamedDecl> &Base,
 886                                   BoundNodesTreeBuilder *Builder) = 0;
 887
 888   template <typename T>
 889   bool matchesChildOf(const T &Node,
 890                       const DynTypedMatcher &Matcher,
 891                       BoundNodesTreeBuilder *Builder,
 892                       TraversalKind Traverse,
 893                       BindKind Bind) {
 894     static_assert(std::is_base_of<Decl, T>::value ||
 895                   std::is_base_of<Stmt, T>::value ||
 896                   std::is_base_of<NestedNameSpecifier, T>::value ||
 897                   std::is_base_of<NestedNameSpecifierLoc, T>::value ||
 898                   std::is_base_of<TypeLoc, T>::value ||
 899                   std::is_base_of<QualType, T>::value,
 900                   "unsupported type for recursive matching");
 901    return matchesChildOf(ast_type_traits::DynTypedNode::create(Node),
 902                           Matcher, Builder, Traverse, Bind);
 903   }
 904
 905   template <typename T>
 906   bool matchesDescendantOf(const T &Node,
 907                            const DynTypedMatcher &Matcher,
 908                            BoundNodesTreeBuilder *Builder,
 909                            BindKind Bind) {
 910     static_assert(std::is_base_of<Decl, T>::value ||
 911                   std::is_base_of<Stmt, T>::value ||
 912                   std::is_base_of<NestedNameSpecifier, T>::value ||
 913                   std::is_base_of<NestedNameSpecifierLoc, T>::value ||
 914                   std::is_base_of<TypeLoc, T>::value ||
 915                   std::is_base_of<QualType, T>::value,
 916                   "unsupported type for recursive matching");
 917     return matchesDescendantOf(ast_type_traits::DynTypedNode::create(Node),
 918                                Matcher, Builder, Bind);
 919   }
 920
 921   // FIXME: Implement support for BindKind.
 922   template <typename T>
 923   bool matchesAncestorOf(const T &Node,
 924                          const DynTypedMatcher &Matcher,
 925                          BoundNodesTreeBuilder *Builder,
 926                          AncestorMatchMode MatchMode) {
 927     static_assert(std::is_base_of<Decl, T>::value ||
 928                       std::is_base_of<NestedNameSpecifierLoc, T>::value ||
 929                       std::is_base_of<Stmt, T>::value ||
 930                       std::is_base_of<TypeLoc, T>::value,
 931                   "type not allowed for recursive matching");
 932     return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node),
 933                              Matcher, Builder, MatchMode);
 934   }
 935
 936   virtual ASTContext &getASTContext() const = 0;
 937
 938 protected:
 939   virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node,
 940                               const DynTypedMatcher &Matcher,
 941                               BoundNodesTreeBuilder *Builder,
 942                               TraversalKind Traverse,
 943                               BindKind Bind) = 0;
 944
 945   virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node,
 946                                    const DynTypedMatcher &Matcher,
 947                                    BoundNodesTreeBuilder *Builder,
 948                                    BindKind Bind) = 0;
 949
 950   virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
 951                                  const DynTypedMatcher &Matcher,
 952                                  BoundNodesTreeBuilder *Builder,
 953                                  AncestorMatchMode MatchMode) = 0;
 954 };
 955
 956 /// \brief A type-list implementation.
 957 ///
 958 /// A "linked list" of types, accessible by using the ::head and ::tail
 959 /// typedefs.
 960 template <typename... Ts> struct TypeList {}; // Empty sentinel type list.
 961
 962 template <typename T1, typename... Ts> struct TypeList<T1, Ts...> {
 963   /// \brief The first type on the list.
 964   typedef T1 head;
 965
 966   /// \brief A sublist with the tail. ie everything but the head.
 967   ///
 968   /// This type is used to do recursion. TypeList<>/EmptyTypeList indicates the
 969   /// end of the list.
 970   typedef TypeList<Ts...> tail;
 971 };
 972
 973 /// \brief The empty type list.
 974 typedef TypeList<> EmptyTypeList;
 975
 976 /// \brief Helper meta-function to determine if some type \c T is present or
 977 ///   a parent type in the list.
 978 template <typename AnyTypeList, typename T>
 979 struct TypeListContainsSuperOf {
 980   static const bool value =
 981       std::is_base_of<typename AnyTypeList::head, T>::value ||
 982       TypeListContainsSuperOf<typename AnyTypeList::tail, T>::value;
 983 };
 984 template <typename T>
 985 struct TypeListContainsSuperOf<EmptyTypeList, T> {
 986   static const bool value = false;
 987 };
 988
 989 /// \brief A "type list" that contains all types.
 990 ///
 991 /// Useful for matchers like \c anything and \c unless.
 992 typedef TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc,
 993                  QualType, Type, TypeLoc, CXXCtorInitializer> AllNodeBaseTypes;
 994
 995 /// \brief Helper meta-function to extract the argument out of a function of
 996 ///   type void(Arg).
 997 ///
 998 /// See AST_POLYMORPHIC_SUPPORTED_TYPES for details.
 999 template <class T> struct ExtractFunctionArgMeta;
1000 template <class T> struct ExtractFunctionArgMeta<void(T)> {
1001   typedef T type;
1002 };
1003
1004 /// \brief Default type lists for ArgumentAdaptingMatcher matchers.
1005 typedef AllNodeBaseTypes AdaptativeDefaultFromTypes;
1006 typedef TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc,
1007                  TypeLoc, QualType> AdaptativeDefaultToTypes;
1008
1009 /// \brief All types that are supported by HasDeclarationMatcher above.
1010 typedef TypeList<CallExpr, CXXConstructExpr, DeclRefExpr, EnumType,
1011                  InjectedClassNameType, LabelStmt, AddrLabelExpr, MemberExpr,
1012                  QualType, RecordType, TagType, TemplateSpecializationType,
1013                  TemplateTypeParmType, TypedefType,
1014                  UnresolvedUsingType> HasDeclarationSupportedTypes;
1015
1016 /// \brief Converts a \c Matcher<T> to a matcher of desired type \c To by
1017 /// "adapting" a \c To into a \c T.
1018 ///
1019 /// The \c ArgumentAdapterT argument specifies how the adaptation is done.
1020 ///
1021 /// For example:
1022 ///   \c ArgumentAdaptingMatcher<HasMatcher, T>(InnerMatcher);
1023 /// Given that \c InnerMatcher is of type \c Matcher<T>, this returns a matcher
1024 /// that is convertible into any matcher of type \c To by constructing
1025 /// \c HasMatcher<To, T>(InnerMatcher).
1026 ///
1027 /// If a matcher does not need knowledge about the inner type, prefer to use
1028 /// PolymorphicMatcherWithParam1.
1029 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
1030           typename FromTypes = AdaptativeDefaultFromTypes,
1031           typename ToTypes = AdaptativeDefaultToTypes>
1032 struct ArgumentAdaptingMatcherFunc {
1033   template <typename T> class Adaptor {
1034   public:
1035     explicit Adaptor(const Matcher<T> &InnerMatcher)
1036         : InnerMatcher(InnerMatcher) {}
1037
1038     typedef ToTypes ReturnTypes;
1039
1040     template <typename To> operator Matcher<To>() const {
1041       return Matcher<To>(new ArgumentAdapterT<To, T>(InnerMatcher));
1042     }
1043
1044   private:
1045     const Matcher<T> InnerMatcher;
1046   };
1047
1048   template <typename T>
1049   static Adaptor<T> create(const Matcher<T> &InnerMatcher) {
1050     return Adaptor<T>(InnerMatcher);
1051   }
1052
1053   template <typename T>
1054   Adaptor<T> operator()(const Matcher<T> &InnerMatcher) const {
1055     return create(InnerMatcher);
1056   }
1057 };
1058
1059 /// \brief A PolymorphicMatcherWithParamN<MatcherT, P1, ..., PN> object can be
1060 /// created from N parameters p1, ..., pN (of type P1, ..., PN) and
1061 /// used as a Matcher<T> where a MatcherT<T, P1, ..., PN>(p1, ..., pN)
1062 /// can be constructed.
1063 ///
1064 /// For example:
1065 /// - PolymorphicMatcherWithParam0<IsDefinitionMatcher>()
1066 ///   creates an object that can be used as a Matcher<T> for any type T
1067 ///   where an IsDefinitionMatcher<T>() can be constructed.
1068 /// - PolymorphicMatcherWithParam1<ValueEqualsMatcher, int>(42)
1069 ///   creates an object that can be used as a Matcher<T> for any type T
1070 ///   where a ValueEqualsMatcher<T, int>(42) can be constructed.
1071 template <template <typename T> class MatcherT,
1072           typename ReturnTypesF = void(AllNodeBaseTypes)>
1073 class PolymorphicMatcherWithParam0 {
1074 public:
1075   typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes;
1076   template <typename T>
1077   operator Matcher<T>() const {
1078     static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value,
1079                   "right polymorphic conversion");
1080     return Matcher<T>(new MatcherT<T>());
1081   }
1082 };
1083
1084 template <template <typename T, typename P1> class MatcherT,
1085           typename P1,
1086           typename ReturnTypesF = void(AllNodeBaseTypes)>
1087 class PolymorphicMatcherWithParam1 {
1088 public:
1089   explicit PolymorphicMatcherWithParam1(const P1 &Param1)
1090       : Param1(Param1) {}
1091
1092   typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes;
1093
1094   template <typename T>
1095   operator Matcher<T>() const {
1096     static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value,
1097                   "right polymorphic conversion");
1098     return Matcher<T>(new MatcherT<T, P1>(Param1));
1099   }
1100
1101 private:
1102   const P1 Param1;
1103 };
1104
1105 template <template <typename T, typename P1, typename P2> class MatcherT,
1106           typename P1, typename P2,
1107           typename ReturnTypesF = void(AllNodeBaseTypes)>
1108 class PolymorphicMatcherWithParam2 {
1109 public:
1110   PolymorphicMatcherWithParam2(const P1 &Param1, const P2 &Param2)
1111       : Param1(Param1), Param2(Param2) {}
1112
1113   typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes;
1114
1115   template <typename T>
1116   operator Matcher<T>() const {
1117     static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value,
1118                   "right polymorphic conversion");
1119     return Matcher<T>(new MatcherT<T, P1, P2>(Param1, Param2));
1120   }
1121
1122 private:
1123   const P1 Param1;
1124   const P2 Param2;
1125 };
1126
1127 /// \brief Matches any instance of the given NodeType.
1128 ///
1129 /// This is useful when a matcher syntactically requires a child matcher,
1130 /// but the context doesn't care. See for example: anything().
1131 class TrueMatcher {
1132  public:
1133   typedef AllNodeBaseTypes ReturnTypes;
1134
1135   template <typename T>
1136   operator Matcher<T>() const {
1137     return DynTypedMatcher::trueMatcher(
1138                ast_type_traits::ASTNodeKind::getFromNodeKind<T>())
1139         .template unconditionalConvertTo<T>();
1140   }
1141 };
1142
1143 /// \brief A Matcher that allows binding the node it matches to an id.
1144 ///
1145 /// BindableMatcher provides a \a bind() method that allows binding the
1146 /// matched node to an id if the match was successful.
1147 template <typename T>
1148 class BindableMatcher : public Matcher<T> {
1149 public:
1150   explicit BindableMatcher(const Matcher<T> &M) : Matcher<T>(M) {}
1151   explicit BindableMatcher(MatcherInterface<T> *Implementation)
1152     : Matcher<T>(Implementation) {}
1153
1154   /// \brief Returns a matcher that will bind the matched node on a match.
1155   ///
1156   /// The returned matcher is equivalent to this matcher, but will
1157   /// bind the matched node on a match.
1158   Matcher<T> bind(StringRef ID) const {
1159     return DynTypedMatcher(*this)
1160         .tryBind(ID)
1161         ->template unconditionalConvertTo<T>();
1162   }
1163
1164   /// \brief Same as Matcher<T>'s conversion operator, but enables binding on
1165   /// the returned matcher.
1166   operator DynTypedMatcher() const {
1167     DynTypedMatcher Result = static_cast<const Matcher<T>&>(*this);
1168     Result.setAllowBind(true);
1169     return Result;
1170   }
1171 };
1172
1173 /// \brief Matches nodes of type T that have child nodes of type ChildT for
1174 /// which a specified child matcher matches.
1175 ///
1176 /// ChildT must be an AST base type.
1177 template <typename T, typename ChildT>
1178 class HasMatcher : public WrapperMatcherInterface<T> {
1179
1180 public:
1181   explicit HasMatcher(const Matcher<ChildT> &ChildMatcher)
1182       : HasMatcher::WrapperMatcherInterface(ChildMatcher) {}
1183
1184   bool matches(const T &Node, ASTMatchFinder *Finder,
1185                BoundNodesTreeBuilder *Builder) const override {
1186     return Finder->matchesChildOf(Node, this->InnerMatcher, Builder,
1187                                   ASTMatchFinder::TK_AsIs,
1188                                   ASTMatchFinder::BK_First);
1189   }
1190 };
1191
1192 /// \brief Matches nodes of type T that have child nodes of type ChildT for
1193 /// which a specified child matcher matches. ChildT must be an AST base
1194 /// type.
1195 /// As opposed to the HasMatcher, the ForEachMatcher will produce a match
1196 /// for each child that matches.
1197 template <typename T, typename ChildT>
1198 class ForEachMatcher : public WrapperMatcherInterface<T> {
1199   static_assert(IsBaseType<ChildT>::value,
1200                 "for each only accepts base type matcher");
1201
1202  public:
1203    explicit ForEachMatcher(const Matcher<ChildT> &ChildMatcher)
1204        : ForEachMatcher::WrapperMatcherInterface(ChildMatcher) {}
1205
1206   bool matches(const T& Node, ASTMatchFinder* Finder,
1207                BoundNodesTreeBuilder* Builder) const override {
1208     return Finder->matchesChildOf(
1209         Node, this->InnerMatcher, Builder,
1210         ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses,
1211         ASTMatchFinder::BK_All);
1212   }
1213 };
1214
1215 /// \brief VariadicOperatorMatcher related types.
1216 /// @{
1217
1218 /// \brief Polymorphic matcher object that uses a \c
1219 /// DynTypedMatcher::VariadicOperator operator.
1220 ///
1221 /// Input matchers can have any type (including other polymorphic matcher
1222 /// types), and the actual Matcher<T> is generated on demand with an implicit
1223 /// coversion operator.
1224 template <typename... Ps> class VariadicOperatorMatcher {
1225 public:
1226   VariadicOperatorMatcher(DynTypedMatcher::VariadicOperator Op, Ps &&... Params)
1227       : Op(Op), Params(std::forward<Ps>(Params)...) {}
1228
1229   template <typename T> operator Matcher<T>() const {
1230     return DynTypedMatcher::constructVariadic(
1231                Op, ast_type_traits::ASTNodeKind::getFromNodeKind<T>(),
1232                getMatchers<T>(llvm::index_sequence_for<Ps...>()))
1233         .template unconditionalConvertTo<T>();
1234   }
1235
1236 private:
1237   // Helper method to unpack the tuple into a vector.
1238   template <typename T, std::size_t... Is>
1239   std::vector<DynTypedMatcher> getMatchers(llvm::index_sequence<Is...>) const {
1240     return {Matcher<T>(std::get<Is>(Params))...};
1241   }
1242
1243   const DynTypedMatcher::VariadicOperator Op;
1244   std::tuple<Ps...> Params;
1245 };
1246
1247 /// \brief Overloaded function object to generate VariadicOperatorMatcher
1248 ///   objects from arbitrary matchers.
1249 template <unsigned MinCount, unsigned MaxCount>
1250 struct VariadicOperatorMatcherFunc {
1251   DynTypedMatcher::VariadicOperator Op;
1252
1253   template <typename... Ms>
1254   VariadicOperatorMatcher<Ms...> operator()(Ms &&... Ps) const {
1255     static_assert(MinCount <= sizeof...(Ms) && sizeof...(Ms) <= MaxCount,
1256                   "invalid number of parameters for variadic matcher");
1257     return VariadicOperatorMatcher<Ms...>(Op, std::forward<Ms>(Ps)...);
1258   }
1259 };
1260
1261 /// @}
1262
1263 template <typename T>
1264 inline Matcher<T> DynTypedMatcher::unconditionalConvertTo() const {
1265   return Matcher<T>(*this);
1266 }
1267
1268 /// \brief Creates a Matcher<T> that matches if all inner matchers match.
1269 template<typename T>
1270 BindableMatcher<T> makeAllOfComposite(
1271     ArrayRef<const Matcher<T> *> InnerMatchers) {
1272   // For the size() == 0 case, we return a "true" matcher.
1273   if (InnerMatchers.size() == 0) {
1274     return BindableMatcher<T>(TrueMatcher());
1275   }
1276   // For the size() == 1 case, we simply return that one matcher.
1277   // No need to wrap it in a variadic operation.
1278   if (InnerMatchers.size() == 1) {
1279     return BindableMatcher<T>(*InnerMatchers[0]);
1280   }
1281
1282   typedef llvm::pointee_iterator<const Matcher<T> *const *> PI;
1283   std::vector<DynTypedMatcher> DynMatchers(PI(InnerMatchers.begin()),
1284                                            PI(InnerMatchers.end()));
1285   return BindableMatcher<T>(
1286       DynTypedMatcher::constructVariadic(
1287           DynTypedMatcher::VO_AllOf,
1288           ast_type_traits::ASTNodeKind::getFromNodeKind<T>(),
1289           std::move(DynMatchers))
1290           .template unconditionalConvertTo<T>());
1291 }
1292
1293 /// \brief Creates a Matcher<T> that matches if
1294 /// T is dyn_cast'able into InnerT and all inner matchers match.
1295 ///
1296 /// Returns BindableMatcher, as matchers that use dyn_cast have
1297 /// the same object both to match on and to run submatchers on,
1298 /// so there is no ambiguity with what gets bound.
1299 template<typename T, typename InnerT>
1300 BindableMatcher<T> makeDynCastAllOfComposite(
1301     ArrayRef<const Matcher<InnerT> *> InnerMatchers) {
1302   return BindableMatcher<T>(
1303       makeAllOfComposite(InnerMatchers).template dynCastTo<T>());
1304 }
1305
1306 /// \brief Matches nodes of type T that have at least one descendant node of
1307 /// type DescendantT for which the given inner matcher matches.
1308 ///
1309 /// DescendantT must be an AST base type.
1310 template <typename T, typename DescendantT>
1311 class HasDescendantMatcher : public WrapperMatcherInterface<T> {
1312   static_assert(IsBaseType<DescendantT>::value,
1313                 "has descendant only accepts base type matcher");
1314
1315 public:
1316   explicit HasDescendantMatcher(const Matcher<DescendantT> &DescendantMatcher)
1317       : HasDescendantMatcher::WrapperMatcherInterface(DescendantMatcher) {}
1318
1319   bool matches(const T &Node, ASTMatchFinder *Finder,
1320                BoundNodesTreeBuilder *Builder) const override {
1321     return Finder->matchesDescendantOf(Node, this->InnerMatcher, Builder,
1322                                        ASTMatchFinder::BK_First);
1323   }
1324 };
1325
1326 /// \brief Matches nodes of type \c T that have a parent node of type \c ParentT
1327 /// for which the given inner matcher matches.
1328 ///
1329 /// \c ParentT must be an AST base type.
1330 template <typename T, typename ParentT>
1331 class HasParentMatcher : public WrapperMatcherInterface<T> {
1332   static_assert(IsBaseType<ParentT>::value,
1333                 "has parent only accepts base type matcher");
1334
1335 public:
1336   explicit HasParentMatcher(const Matcher<ParentT> &ParentMatcher)
1337       : HasParentMatcher::WrapperMatcherInterface(ParentMatcher) {}
1338
1339   bool matches(const T &Node, ASTMatchFinder *Finder,
1340                BoundNodesTreeBuilder *Builder) const override {
1341     return Finder->matchesAncestorOf(Node, this->InnerMatcher, Builder,
1342                                      ASTMatchFinder::AMM_ParentOnly);
1343   }
1344 };
1345
1346 /// \brief Matches nodes of type \c T that have at least one ancestor node of
1347 /// type \c AncestorT for which the given inner matcher matches.
1348 ///
1349 /// \c AncestorT must be an AST base type.
1350 template <typename T, typename AncestorT>
1351 class HasAncestorMatcher : public WrapperMatcherInterface<T> {
1352   static_assert(IsBaseType<AncestorT>::value,
1353                 "has ancestor only accepts base type matcher");
1354
1355 public:
1356   explicit HasAncestorMatcher(const Matcher<AncestorT> &AncestorMatcher)
1357       : HasAncestorMatcher::WrapperMatcherInterface(AncestorMatcher) {}
1358
1359   bool matches(const T &Node, ASTMatchFinder *Finder,
1360                BoundNodesTreeBuilder *Builder) const override {
1361     return Finder->matchesAncestorOf(Node, this->InnerMatcher, Builder,
1362                                      ASTMatchFinder::AMM_All);
1363   }
1364 };
1365
1366 /// \brief Matches nodes of type T that have at least one descendant node of
1367 /// type DescendantT for which the given inner matcher matches.
1368 ///
1369 /// DescendantT must be an AST base type.
1370 /// As opposed to HasDescendantMatcher, ForEachDescendantMatcher will match
1371 /// for each descendant node that matches instead of only for the first.
1372 template <typename T, typename DescendantT>
1373 class ForEachDescendantMatcher : public WrapperMatcherInterface<T> {
1374   static_assert(IsBaseType<DescendantT>::value,
1375                 "for each descendant only accepts base type matcher");
1376
1377 public:
1378   explicit ForEachDescendantMatcher(
1379       const Matcher<DescendantT> &DescendantMatcher)
1380       : ForEachDescendantMatcher::WrapperMatcherInterface(DescendantMatcher) {}
1381
1382   bool matches(const T &Node, ASTMatchFinder *Finder,
1383                BoundNodesTreeBuilder *Builder) const override {
1384     return Finder->matchesDescendantOf(Node, this->InnerMatcher, Builder,
1385                                        ASTMatchFinder::BK_All);
1386   }
1387 };
1388
1389 /// \brief Matches on nodes that have a getValue() method if getValue() equals
1390 /// the value the ValueEqualsMatcher was constructed with.
1391 template <typename T, typename ValueT>
1392 class ValueEqualsMatcher : public SingleNodeMatcherInterface<T> {
1393   static_assert(std::is_base_of<CharacterLiteral, T>::value ||
1394                 std::is_base_of<CXXBoolLiteralExpr, T>::value ||
1395                 std::is_base_of<FloatingLiteral, T>::value ||
1396                 std::is_base_of<IntegerLiteral, T>::value,
1397                 "the node must have a getValue method");
1398
1399 public:
1400   explicit ValueEqualsMatcher(const ValueT &ExpectedValue)
1401       : ExpectedValue(ExpectedValue) {}
1402
1403   bool matchesNode(const T &Node) const override {
1404     return Node.getValue() == ExpectedValue;
1405   }
1406
1407 private:
1408   const ValueT ExpectedValue;
1409 };
1410
1411 /// \brief Template specializations to easily write matchers for floating point
1412 /// literals.
1413 template <>
1414 inline bool ValueEqualsMatcher<FloatingLiteral, double>::matchesNode(
1415     const FloatingLiteral &Node) const {
1416   if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle)
1417     return Node.getValue().convertToFloat() == ExpectedValue;
1418   if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble)
1419     return Node.getValue().convertToDouble() == ExpectedValue;
1420   return false;
1421 }
1422 template <>
1423 inline bool ValueEqualsMatcher<FloatingLiteral, float>::matchesNode(
1424     const FloatingLiteral &Node) const {
1425   if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle)
1426     return Node.getValue().convertToFloat() == ExpectedValue;
1427   if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble)
1428     return Node.getValue().convertToDouble() == ExpectedValue;
1429   return false;
1430 }
1431 template <>
1432 inline bool ValueEqualsMatcher<FloatingLiteral, llvm::APFloat>::matchesNode(
1433     const FloatingLiteral &Node) const {
1434   return ExpectedValue.compare(Node.getValue()) == llvm::APFloat::cmpEqual;
1435 }
1436
1437 /// \brief A VariadicDynCastAllOfMatcher<SourceT, TargetT> object is a
1438 /// variadic functor that takes a number of Matcher<TargetT> and returns a
1439 /// Matcher<SourceT> that matches TargetT nodes that are matched by all of the
1440 /// given matchers, if SourceT can be dynamically casted into TargetT.
1441 ///
1442 /// For example:
1443 ///   const VariadicDynCastAllOfMatcher<
1444 ///       Decl, CXXRecordDecl> record;
1445 /// Creates a functor record(...) that creates a Matcher<Decl> given
1446 /// a variable number of arguments of type Matcher<CXXRecordDecl>.
1447 /// The returned matcher matches if the given Decl can by dynamically
1448 /// casted to CXXRecordDecl and all given matchers match.
1449 template <typename SourceT, typename TargetT>
1450 class VariadicDynCastAllOfMatcher
1451     : public VariadicFunction<BindableMatcher<SourceT>, Matcher<TargetT>,
1452                               makeDynCastAllOfComposite<SourceT, TargetT>> {
1453 public:
1454   VariadicDynCastAllOfMatcher() {}
1455 };
1456
1457 /// \brief A \c VariadicAllOfMatcher<T> object is a variadic functor that takes
1458 /// a number of \c Matcher<T> and returns a \c Matcher<T> that matches \c T
1459 /// nodes that are matched by all of the given matchers.
1460 ///
1461 /// For example:
1462 ///   const VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier;
1463 /// Creates a functor nestedNameSpecifier(...) that creates a
1464 /// \c Matcher<NestedNameSpecifier> given a variable number of arguments of type
1465 /// \c Matcher<NestedNameSpecifier>.
1466 /// The returned matcher matches if all given matchers match.
1467 template <typename T>
1468 class VariadicAllOfMatcher
1469     : public VariadicFunction<BindableMatcher<T>, Matcher<T>,
1470                               makeAllOfComposite<T>> {
1471 public:
1472   VariadicAllOfMatcher() {}
1473 };
1474
1475 /// \brief Matches nodes of type \c TLoc for which the inner
1476 /// \c Matcher<T> matches.
1477 template <typename TLoc, typename T>
1478 class LocMatcher : public WrapperMatcherInterface<TLoc> {
1479 public:
1480   explicit LocMatcher(const Matcher<T> &InnerMatcher)
1481       : LocMatcher::WrapperMatcherInterface(InnerMatcher) {}
1482
1483   bool matches(const TLoc &Node, ASTMatchFinder *Finder,
1484                BoundNodesTreeBuilder *Builder) const override {
1485     if (!Node)
1486       return false;
1487     return this->InnerMatcher.matches(extract(Node), Finder, Builder);
1488   }
1489
1490 private:
1491   static ast_type_traits::DynTypedNode
1492   extract(const NestedNameSpecifierLoc &Loc) {
1493     return ast_type_traits::DynTypedNode::create(*Loc.getNestedNameSpecifier());
1494   }
1495 };
1496
1497 /// \brief Matches \c TypeLocs based on an inner matcher matching a certain
1498 /// \c QualType.
1499 ///
1500 /// Used to implement the \c loc() matcher.
1501 class TypeLocTypeMatcher : public WrapperMatcherInterface<TypeLoc> {
1502 public:
1503   explicit TypeLocTypeMatcher(const Matcher<QualType> &InnerMatcher)
1504       : TypeLocTypeMatcher::WrapperMatcherInterface(InnerMatcher) {}
1505
1506   bool matches(const TypeLoc &Node, ASTMatchFinder *Finder,
1507                BoundNodesTreeBuilder *Builder) const override {
1508     if (!Node)
1509       return false;
1510     return this->InnerMatcher.matches(
1511         ast_type_traits::DynTypedNode::create(Node.getType()), Finder, Builder);
1512   }
1513 };
1514
1515 /// \brief Matches nodes of type \c T for which the inner matcher matches on a
1516 /// another node of type \c T that can be reached using a given traverse
1517 /// function.
1518 template <typename T>
1519 class TypeTraverseMatcher : public WrapperMatcherInterface<T> {
1520 public:
1521   explicit TypeTraverseMatcher(const Matcher<QualType> &InnerMatcher,
1522                                QualType (T::*TraverseFunction)() const)
1523       : TypeTraverseMatcher::WrapperMatcherInterface(InnerMatcher),
1524         TraverseFunction(TraverseFunction) {}
1525
1526   bool matches(const T &Node, ASTMatchFinder *Finder,
1527                BoundNodesTreeBuilder *Builder) const override {
1528     QualType NextNode = (Node.*TraverseFunction)();
1529     if (NextNode.isNull())
1530       return false;
1531     return this->InnerMatcher.matches(
1532         ast_type_traits::DynTypedNode::create(NextNode), Finder, Builder);
1533   }
1534
1535 private:
1536   QualType (T::*TraverseFunction)() const;
1537 };
1538
1539 /// \brief Matches nodes of type \c T in a ..Loc hierarchy, for which the inner
1540 /// matcher matches on a another node of type \c T that can be reached using a
1541 /// given traverse function.
1542 template <typename T>
1543 class TypeLocTraverseMatcher : public WrapperMatcherInterface<T> {
1544 public:
1545   explicit TypeLocTraverseMatcher(const Matcher<TypeLoc> &InnerMatcher,
1546                                   TypeLoc (T::*TraverseFunction)() const)
1547       : TypeLocTraverseMatcher::WrapperMatcherInterface(InnerMatcher),
1548         TraverseFunction(TraverseFunction) {}
1549
1550   bool matches(const T &Node, ASTMatchFinder *Finder,
1551                BoundNodesTreeBuilder *Builder) const override {
1552     TypeLoc NextNode = (Node.*TraverseFunction)();
1553     if (!NextNode)
1554       return false;
1555     return this->InnerMatcher.matches(
1556         ast_type_traits::DynTypedNode::create(NextNode), Finder, Builder);
1557   }
1558
1559 private:
1560   TypeLoc (T::*TraverseFunction)() const;
1561 };
1562
1563 /// \brief Converts a \c Matcher<InnerT> to a \c Matcher<OuterT>, where
1564 /// \c OuterT is any type that is supported by \c Getter.
1565 ///
1566 /// \code Getter<OuterT>::value() \endcode returns a
1567 /// \code InnerTBase (OuterT::*)() \endcode, which is used to adapt a \c OuterT
1568 /// object into a \c InnerT
1569 template <typename InnerTBase,
1570           template <typename OuterT> class Getter,
1571           template <typename OuterT> class MatcherImpl,
1572           typename ReturnTypesF>
1573 class TypeTraversePolymorphicMatcher {
1574 private:
1575   typedef TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl,
1576                                          ReturnTypesF> Self;
1577   static Self create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers);
1578
1579 public:
1580   typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes;
1581
1582   explicit TypeTraversePolymorphicMatcher(
1583       ArrayRef<const Matcher<InnerTBase> *> InnerMatchers)
1584       : InnerMatcher(makeAllOfComposite(InnerMatchers)) {}
1585
1586   template <typename OuterT> operator Matcher<OuterT>() const {
1587     return Matcher<OuterT>(
1588         new MatcherImpl<OuterT>(InnerMatcher, Getter<OuterT>::value()));
1589   }
1590
1591   struct Func
1592       : public VariadicFunction<Self, Matcher<InnerTBase>, &Self::create> {
1593     Func() {}
1594   };
1595
1596 private:
1597   const Matcher<InnerTBase> InnerMatcher;
1598 };
1599
1600 /// \brief A simple memoizer of T(*)() functions.
1601 ///
1602 /// It will call the passed 'Func' template parameter at most once.
1603 /// Used to support AST_MATCHER_FUNCTION() macro.
1604 template <typename Matcher, Matcher (*Func)()> class MemoizedMatcher {
1605   struct Wrapper {
1606     Wrapper() : M(Func()) {}
1607     Matcher M;
1608   };
1609
1610 public:
1611   static const Matcher &getInstance() {
1612     static llvm::ManagedStatic<Wrapper> Instance;
1613     return Instance->M;
1614   }
1615 };
1616
1617 // Define the create() method out of line to silence a GCC warning about
1618 // the struct "Func" having greater visibility than its base, which comes from
1619 // using the flag -fvisibility-inlines-hidden.
1620 template <typename InnerTBase, template <typename OuterT> class Getter,
1621           template <typename OuterT> class MatcherImpl, typename ReturnTypesF>
1622 TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, ReturnTypesF>
1623 TypeTraversePolymorphicMatcher<
1624     InnerTBase, Getter, MatcherImpl,
1625     ReturnTypesF>::create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) {
1626   return Self(InnerMatchers);
1627 }
1628
1629 // FIXME: unify ClassTemplateSpecializationDecl and TemplateSpecializationType's
1630 // APIs for accessing the template argument list.
1631 inline ArrayRef<TemplateArgument>
1632 getTemplateSpecializationArgs(const ClassTemplateSpecializationDecl &D) {
1633   return D.getTemplateArgs().asArray();
1634 }
1635
1636 inline ArrayRef<TemplateArgument>
1637 getTemplateSpecializationArgs(const TemplateSpecializationType &T) {
1638   return llvm::makeArrayRef(T.getArgs(), T.getNumArgs());
1639 }
1640
1641 struct NotEqualsBoundNodePredicate {
1642   bool operator()(const internal::BoundNodesMap &Nodes) const {
1643     return Nodes.getNode(ID) != Node;
1644   }
1645   std::string ID;
1646   ast_type_traits::DynTypedNode Node;
1647 };
1648
1649 template <typename Ty>
1650 struct GetBodyMatcher {
1651   static const Stmt *get(const Ty &Node) {
1652     return Node.getBody();
1653   }
1654 };
1655
1656 template <>
1657 inline const Stmt *GetBodyMatcher<FunctionDecl>::get(const FunctionDecl &Node) {
1658   return Node.doesThisDeclarationHaveABody() ? Node.getBody() : nullptr;
1659 }
1660
1661 template <typename Ty>
1662 struct HasSizeMatcher {
1663   static bool hasSize(const Ty &Node, unsigned int N) {
1664     return Node.getSize() == N;
1665   }
1666 };
1667
1668 template <>
1669 inline bool HasSizeMatcher<StringLiteral>::hasSize(
1670     const StringLiteral &Node, unsigned int N) {
1671   return Node.getLength() == N;
1672 }
1673
1674 template <typename Ty>
1675 struct GetSourceExpressionMatcher {
1676   static const Expr *get(const Ty &Node) {
1677     return Node.getSubExpr();
1678   }
1679 };
1680
1681 template <>
1682 inline const Expr *GetSourceExpressionMatcher<OpaqueValueExpr>::get(
1683     const OpaqueValueExpr &Node) {
1684   return Node.getSourceExpr();
1685 }
1686
1687 template <typename Ty>
1688 struct CompoundStmtMatcher {
1689   static const CompoundStmt *get(const Ty &Node) {
1690     return &Node;
1691   }
1692 };
1693
1694 template <>
1695 inline const CompoundStmt *
1696 CompoundStmtMatcher<StmtExpr>::get(const StmtExpr &Node) {
1697   return Node.getSubStmt();
1698 }
1699
1700
1701 } // end namespace internal
1702 } // end namespace ast_matchers
1703 } // end namespace clang
1704
1705 #endif // LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H