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