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