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