1 //===- ASTMatchersInternal.cpp - Structural query framework ---------------===//
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 //===----------------------------------------------------------------------===//
12 
13 #include "clang/ASTMatchers/ASTMatchersInternal.h"
14 #include "clang/AST/ASTContext.h"
15 #include "clang/AST/ASTTypeTraits.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/DeclTemplate.h"
18 #include "clang/AST/ParentMapContext.h"
19 #include "clang/AST/PrettyPrinter.h"
20 #include "clang/ASTMatchers/ASTMatchers.h"
21 #include "clang/Basic/LLVM.h"
22 #include "clang/Lex/Lexer.h"
23 #include "llvm/ADT/ArrayRef.h"
24 #include "llvm/ADT/IntrusiveRefCntPtr.h"
25 #include "llvm/ADT/None.h"
26 #include "llvm/ADT/SmallString.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/StringRef.h"
29 #include "llvm/Support/Casting.h"
30 #include "llvm/Support/ErrorHandling.h"
31 #include "llvm/Support/ManagedStatic.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include <algorithm>
34 #include <cassert>
35 #include <cstddef>
36 #include <string>
37 #include <utility>
38 #include <vector>
39 
40 namespace clang {
41 namespace ast_matchers {
42 
43 AST_MATCHER_P(ObjCMessageExpr, hasAnySelectorMatcher, std::vector<std::string>,
44               Matches) {
45   std::string SelString = Node.getSelector().getAsString();
46   for (const std::string &S : Matches)
47     if (S == SelString)
48       return true;
49   return false;
50 }
51 
52 namespace internal {
53 
54 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
55                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
56                       ArrayRef<DynTypedMatcher> InnerMatchers);
57 
58 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
59                            ASTMatchFinder *Finder,
60                            BoundNodesTreeBuilder *Builder,
61                            ArrayRef<DynTypedMatcher> InnerMatchers);
62 
63 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
64                             ASTMatchFinder *Finder,
65                             BoundNodesTreeBuilder *Builder,
66                             ArrayRef<DynTypedMatcher> InnerMatchers);
67 
68 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
69                            ASTMatchFinder *Finder,
70                            BoundNodesTreeBuilder *Builder,
71                            ArrayRef<DynTypedMatcher> InnerMatchers);
72 
73 bool OptionallyVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
74                                 ASTMatchFinder *Finder,
75                                 BoundNodesTreeBuilder *Builder,
76                                 ArrayRef<DynTypedMatcher> InnerMatchers);
77 
78 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
79   if (Bindings.empty())
80     Bindings.push_back(BoundNodesMap());
81   for (BoundNodesMap &Binding : Bindings) {
82     ResultVisitor->visitMatch(BoundNodes(Binding));
83   }
84 }
85 
86 namespace {
87 
88 using VariadicOperatorFunction = bool (*)(
89     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
90     BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
91 
92 template <VariadicOperatorFunction Func>
93 class VariadicMatcher : public DynMatcherInterface {
94 public:
95   VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers)
96       : InnerMatchers(std::move(InnerMatchers)) {}
97 
98   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
99                   ASTMatchFinder *Finder,
100                   BoundNodesTreeBuilder *Builder) const override {
101     return Func(DynNode, Finder, Builder, InnerMatchers);
102   }
103 
104 private:
105   std::vector<DynTypedMatcher> InnerMatchers;
106 };
107 
108 class IdDynMatcher : public DynMatcherInterface {
109 public:
110   IdDynMatcher(StringRef ID,
111                IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher)
112       : ID(ID), InnerMatcher(std::move(InnerMatcher)) {}
113 
114   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
115                   ASTMatchFinder *Finder,
116                   BoundNodesTreeBuilder *Builder) const override {
117     bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder);
118     if (Result) Builder->setBinding(ID, DynNode);
119     return Result;
120   }
121 
122   llvm::Optional<ast_type_traits::TraversalKind>
123   TraversalKind() const override {
124     return InnerMatcher->TraversalKind();
125   }
126 
127 private:
128   const std::string ID;
129   const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
130 };
131 
132 /// A matcher that always returns true.
133 ///
134 /// We only ever need one instance of this matcher, so we create a global one
135 /// and reuse it to reduce the overhead of the matcher and increase the chance
136 /// of cache hits.
137 class TrueMatcherImpl : public DynMatcherInterface {
138 public:
139   TrueMatcherImpl() {
140     Retain(); // Reference count will never become zero.
141   }
142 
143   bool dynMatches(const ast_type_traits::DynTypedNode &, ASTMatchFinder *,
144                   BoundNodesTreeBuilder *) const override {
145     return true;
146   }
147 };
148 
149 } // namespace
150 
151 static llvm::ManagedStatic<TrueMatcherImpl> TrueMatcherInstance;
152 
153 DynTypedMatcher DynTypedMatcher::constructVariadic(
154     DynTypedMatcher::VariadicOperator Op,
155     ast_type_traits::ASTNodeKind SupportedKind,
156     std::vector<DynTypedMatcher> InnerMatchers) {
157   assert(!InnerMatchers.empty() && "Array must not be empty.");
158   assert(llvm::all_of(InnerMatchers,
159                       [SupportedKind](const DynTypedMatcher &M) {
160                         return M.canConvertTo(SupportedKind);
161                       }) &&
162          "InnerMatchers must be convertible to SupportedKind!");
163 
164   // We must relax the restrict kind here.
165   // The different operators might deal differently with a mismatch.
166   // Make it the same as SupportedKind, since that is the broadest type we are
167   // allowed to accept.
168   auto RestrictKind = SupportedKind;
169 
170   switch (Op) {
171   case VO_AllOf:
172     // In the case of allOf() we must pass all the checks, so making
173     // RestrictKind the most restrictive can save us time. This way we reject
174     // invalid types earlier and we can elide the kind checks inside the
175     // matcher.
176     for (auto &IM : InnerMatchers) {
177       RestrictKind = ast_type_traits::ASTNodeKind::getMostDerivedType(
178           RestrictKind, IM.RestrictKind);
179     }
180     return DynTypedMatcher(
181         SupportedKind, RestrictKind,
182         new VariadicMatcher<AllOfVariadicOperator>(std::move(InnerMatchers)));
183 
184   case VO_AnyOf:
185     return DynTypedMatcher(
186         SupportedKind, RestrictKind,
187         new VariadicMatcher<AnyOfVariadicOperator>(std::move(InnerMatchers)));
188 
189   case VO_EachOf:
190     return DynTypedMatcher(
191         SupportedKind, RestrictKind,
192         new VariadicMatcher<EachOfVariadicOperator>(std::move(InnerMatchers)));
193 
194   case VO_Optionally:
195     return DynTypedMatcher(SupportedKind, RestrictKind,
196                            new VariadicMatcher<OptionallyVariadicOperator>(
197                                std::move(InnerMatchers)));
198 
199   case VO_UnaryNot:
200     // FIXME: Implement the Not operator to take a single matcher instead of a
201     // vector.
202     return DynTypedMatcher(
203         SupportedKind, RestrictKind,
204         new VariadicMatcher<NotUnaryOperator>(std::move(InnerMatchers)));
205   }
206   llvm_unreachable("Invalid Op value.");
207 }
208 
209 DynTypedMatcher DynTypedMatcher::constructRestrictedWrapper(
210     const DynTypedMatcher &InnerMatcher,
211     ast_type_traits::ASTNodeKind RestrictKind) {
212   DynTypedMatcher Copy = InnerMatcher;
213   Copy.RestrictKind = RestrictKind;
214   return Copy;
215 }
216 
217 DynTypedMatcher DynTypedMatcher::trueMatcher(
218     ast_type_traits::ASTNodeKind NodeKind) {
219   return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
220 }
221 
222 bool DynTypedMatcher::canMatchNodesOfKind(
223     ast_type_traits::ASTNodeKind Kind) const {
224   return RestrictKind.isBaseOf(Kind);
225 }
226 
227 DynTypedMatcher DynTypedMatcher::dynCastTo(
228     const ast_type_traits::ASTNodeKind Kind) const {
229   auto Copy = *this;
230   Copy.SupportedKind = Kind;
231   Copy.RestrictKind =
232       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
233   return Copy;
234 }
235 
236 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
237                               ASTMatchFinder *Finder,
238                               BoundNodesTreeBuilder *Builder) const {
239   TraversalKindScope RAII(Finder->getASTContext(),
240                           Implementation->TraversalKind());
241 
242   auto N =
243       Finder->getASTContext().getParentMapContext().traverseIgnored(DynNode);
244 
245   if (RestrictKind.isBaseOf(N.getNodeKind()) &&
246       Implementation->dynMatches(N, Finder, Builder)) {
247     return true;
248   }
249   // Delete all bindings when a matcher does not match.
250   // This prevents unexpected exposure of bound nodes in unmatches
251   // branches of the match tree.
252   Builder->removeBindings([](const BoundNodesMap &) { return true; });
253   return false;
254 }
255 
256 bool DynTypedMatcher::matchesNoKindCheck(
257     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
258     BoundNodesTreeBuilder *Builder) const {
259   TraversalKindScope raii(Finder->getASTContext(),
260                           Implementation->TraversalKind());
261 
262   auto N =
263       Finder->getASTContext().getParentMapContext().traverseIgnored(DynNode);
264 
265   assert(RestrictKind.isBaseOf(N.getNodeKind()));
266   if (Implementation->dynMatches(N, Finder, Builder)) {
267     return true;
268   }
269   // Delete all bindings when a matcher does not match.
270   // This prevents unexpected exposure of bound nodes in unmatches
271   // branches of the match tree.
272   Builder->removeBindings([](const BoundNodesMap &) { return true; });
273   return false;
274 }
275 
276 llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
277   if (!AllowBind) return llvm::None;
278   auto Result = *this;
279   Result.Implementation =
280       new IdDynMatcher(ID, std::move(Result.Implementation));
281   return std::move(Result);
282 }
283 
284 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
285   const auto From = getSupportedKind();
286   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
287   auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
288   /// Mimic the implicit conversions of Matcher<>.
289   /// - From Matcher<Type> to Matcher<QualType>
290   if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
291   /// - From Matcher<Base> to Matcher<Derived>
292   return From.isBaseOf(To);
293 }
294 
295 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
296   Bindings.append(Other.Bindings.begin(), Other.Bindings.end());
297 }
298 
299 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
300                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
301                       ArrayRef<DynTypedMatcher> InnerMatchers) {
302   if (InnerMatchers.size() != 1)
303     return false;
304 
305   // The 'unless' matcher will always discard the result:
306   // If the inner matcher doesn't match, unless returns true,
307   // but the inner matcher cannot have bound anything.
308   // If the inner matcher matches, the result is false, and
309   // any possible binding will be discarded.
310   // We still need to hand in all the bound nodes up to this
311   // point so the inner matcher can depend on bound nodes,
312   // and we need to actively discard the bound nodes, otherwise
313   // the inner matcher will reset the bound nodes if it doesn't
314   // match, but this would be inversed by 'unless'.
315   BoundNodesTreeBuilder Discard(*Builder);
316   return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
317 }
318 
319 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
320                            ASTMatchFinder *Finder,
321                            BoundNodesTreeBuilder *Builder,
322                            ArrayRef<DynTypedMatcher> InnerMatchers) {
323   // allOf leads to one matcher for each alternative in the first
324   // matcher combined with each alternative in the second matcher.
325   // Thus, we can reuse the same Builder.
326   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
327     if (!InnerMatcher.matchesNoKindCheck(DynNode, Finder, Builder))
328       return false;
329   }
330   return true;
331 }
332 
333 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
334                             ASTMatchFinder *Finder,
335                             BoundNodesTreeBuilder *Builder,
336                             ArrayRef<DynTypedMatcher> InnerMatchers) {
337   BoundNodesTreeBuilder Result;
338   bool Matched = false;
339   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
340     BoundNodesTreeBuilder BuilderInner(*Builder);
341     if (InnerMatcher.matches(DynNode, Finder, &BuilderInner)) {
342       Matched = true;
343       Result.addMatch(BuilderInner);
344     }
345   }
346   *Builder = std::move(Result);
347   return Matched;
348 }
349 
350 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
351                            ASTMatchFinder *Finder,
352                            BoundNodesTreeBuilder *Builder,
353                            ArrayRef<DynTypedMatcher> InnerMatchers) {
354   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
355     BoundNodesTreeBuilder Result = *Builder;
356     if (InnerMatcher.matches(DynNode, Finder, &Result)) {
357       *Builder = std::move(Result);
358       return true;
359     }
360   }
361   return false;
362 }
363 
364 bool OptionallyVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
365                                 ASTMatchFinder *Finder,
366                                 BoundNodesTreeBuilder *Builder,
367                                 ArrayRef<DynTypedMatcher> InnerMatchers) {
368   BoundNodesTreeBuilder Result;
369   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
370     BoundNodesTreeBuilder BuilderInner(*Builder);
371     if (InnerMatcher.matches(DynNode, Finder, &BuilderInner))
372       Result.addMatch(BuilderInner);
373   }
374   *Builder = std::move(Result);
375   return true;
376 }
377 
378 inline static
379 std::vector<std::string> vectorFromRefs(ArrayRef<const StringRef *> NameRefs) {
380   std::vector<std::string> Names;
381   for (auto *Name : NameRefs)
382     Names.emplace_back(*Name);
383   return Names;
384 }
385 
386 Matcher<NamedDecl> hasAnyNameFunc(ArrayRef<const StringRef *> NameRefs) {
387   std::vector<std::string> Names = vectorFromRefs(NameRefs);
388   return internal::Matcher<NamedDecl>(new internal::HasNameMatcher(Names));
389 }
390 
391 Matcher<ObjCMessageExpr> hasAnySelectorFunc(
392     ArrayRef<const StringRef *> NameRefs) {
393   return hasAnySelectorMatcher(vectorFromRefs(NameRefs));
394 }
395 
396 HasNameMatcher::HasNameMatcher(std::vector<std::string> N)
397     : UseUnqualifiedMatch(std::all_of(
398           N.begin(), N.end(),
399           [](StringRef Name) { return Name.find("::") == Name.npos; })),
400       Names(std::move(N)) {
401 #ifndef NDEBUG
402   for (StringRef Name : Names)
403     assert(!Name.empty());
404 #endif
405 }
406 
407 static bool consumeNameSuffix(StringRef &FullName, StringRef Suffix) {
408   StringRef Name = FullName;
409   if (!Name.endswith(Suffix))
410     return false;
411   Name = Name.drop_back(Suffix.size());
412   if (!Name.empty()) {
413     if (!Name.endswith("::"))
414       return false;
415     Name = Name.drop_back(2);
416   }
417   FullName = Name;
418   return true;
419 }
420 
421 static StringRef getNodeName(const NamedDecl &Node,
422                              llvm::SmallString<128> &Scratch) {
423   // Simple name.
424   if (Node.getIdentifier())
425     return Node.getName();
426 
427   if (Node.getDeclName()) {
428     // Name needs to be constructed.
429     Scratch.clear();
430     llvm::raw_svector_ostream OS(Scratch);
431     Node.printName(OS);
432     return OS.str();
433   }
434 
435   return "(anonymous)";
436 }
437 
438 static StringRef getNodeName(const RecordDecl &Node,
439                              llvm::SmallString<128> &Scratch) {
440   if (Node.getIdentifier()) {
441     return Node.getName();
442   }
443   Scratch.clear();
444   return ("(anonymous " + Node.getKindName() + ")").toStringRef(Scratch);
445 }
446 
447 static StringRef getNodeName(const NamespaceDecl &Node,
448                              llvm::SmallString<128> &Scratch) {
449   return Node.isAnonymousNamespace() ? "(anonymous namespace)" : Node.getName();
450 }
451 
452 namespace {
453 
454 class PatternSet {
455 public:
456   PatternSet(ArrayRef<std::string> Names) {
457     for (StringRef Name : Names)
458       Patterns.push_back({Name, Name.startswith("::")});
459   }
460 
461   /// Consumes the name suffix from each pattern in the set and removes the ones
462   /// that didn't match.
463   /// Return true if there are still any patterns left.
464   bool consumeNameSuffix(StringRef NodeName, bool CanSkip) {
465     for (size_t I = 0; I < Patterns.size();) {
466       if (::clang::ast_matchers::internal::consumeNameSuffix(Patterns[I].P,
467                                                              NodeName) ||
468           CanSkip) {
469         ++I;
470       } else {
471         Patterns.erase(Patterns.begin() + I);
472       }
473     }
474     return !Patterns.empty();
475   }
476 
477   /// Check if any of the patterns are a match.
478   /// A match will be a pattern that was fully consumed, that also matches the
479   /// 'fully qualified' requirement.
480   bool foundMatch(bool AllowFullyQualified) const {
481     for (auto& P: Patterns)
482       if (P.P.empty() && (AllowFullyQualified || !P.IsFullyQualified))
483         return true;
484     return false;
485   }
486 
487 private:
488   struct Pattern {
489     StringRef P;
490     bool IsFullyQualified;
491   };
492 
493   llvm::SmallVector<Pattern, 8> Patterns;
494 };
495 
496 } // namespace
497 
498 bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
499   assert(UseUnqualifiedMatch);
500   llvm::SmallString<128> Scratch;
501   StringRef NodeName = getNodeName(Node, Scratch);
502   return llvm::any_of(Names, [&](StringRef Name) {
503     return consumeNameSuffix(Name, NodeName) && Name.empty();
504   });
505 }
506 
507 bool HasNameMatcher::matchesNodeFullFast(const NamedDecl &Node) const {
508   PatternSet Patterns(Names);
509   llvm::SmallString<128> Scratch;
510 
511   // This function is copied and adapted from NamedDecl::printQualifiedName()
512   // By matching each part individually we optimize in a couple of ways:
513   //  - We can exit early on the first failure.
514   //  - We can skip inline/anonymous namespaces without another pass.
515   //  - We print one name at a time, reducing the chance of overflowing the
516   //    inlined space of the SmallString.
517 
518   // First, match the name.
519   if (!Patterns.consumeNameSuffix(getNodeName(Node, Scratch),
520                                   /*CanSkip=*/false))
521     return false;
522 
523   // Try to match each declaration context.
524   // We are allowed to skip anonymous and inline namespaces if they don't match.
525   const DeclContext *Ctx = Node.getDeclContext();
526 
527   if (Ctx->isFunctionOrMethod())
528     return Patterns.foundMatch(/*AllowFullyQualified=*/false);
529 
530   for (; Ctx && isa<NamedDecl>(Ctx); Ctx = Ctx->getParent()) {
531     if (Patterns.foundMatch(/*AllowFullyQualified=*/false))
532       return true;
533 
534     if (const auto *ND = dyn_cast<NamespaceDecl>(Ctx)) {
535       // If it matches (or we can skip it), continue.
536       if (Patterns.consumeNameSuffix(getNodeName(*ND, Scratch),
537                                      /*CanSkip=*/ND->isAnonymousNamespace() ||
538                                          ND->isInline()))
539         continue;
540       return false;
541     }
542     if (const auto *RD = dyn_cast<RecordDecl>(Ctx)) {
543       if (!isa<ClassTemplateSpecializationDecl>(Ctx)) {
544         if (Patterns.consumeNameSuffix(getNodeName(*RD, Scratch),
545                                        /*CanSkip=*/false))
546           continue;
547 
548         return false;
549       }
550     }
551 
552     // We don't know how to deal with this DeclContext.
553     // Fallback to the slow version of the code.
554     return matchesNodeFullSlow(Node);
555   }
556 
557   return Patterns.foundMatch(/*AllowFullyQualified=*/true);
558 }
559 
560 bool HasNameMatcher::matchesNodeFullSlow(const NamedDecl &Node) const {
561   const bool SkipUnwrittenCases[] = {false, true};
562   for (bool SkipUnwritten : SkipUnwrittenCases) {
563     llvm::SmallString<128> NodeName = StringRef("::");
564     llvm::raw_svector_ostream OS(NodeName);
565 
566     if (SkipUnwritten) {
567       PrintingPolicy Policy = Node.getASTContext().getPrintingPolicy();
568       Policy.SuppressUnwrittenScope = true;
569       Node.printQualifiedName(OS, Policy);
570     } else {
571       Node.printQualifiedName(OS);
572     }
573 
574     const StringRef FullName = OS.str();
575 
576     for (const StringRef Pattern : Names) {
577       if (Pattern.startswith("::")) {
578         if (FullName == Pattern)
579           return true;
580       } else if (FullName.endswith(Pattern) &&
581                  FullName.drop_back(Pattern.size()).endswith("::")) {
582         return true;
583       }
584     }
585   }
586 
587   return false;
588 }
589 
590 bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
591   assert(matchesNodeFullFast(Node) == matchesNodeFullSlow(Node));
592   if (UseUnqualifiedMatch) {
593     assert(matchesNodeUnqualified(Node) == matchesNodeFullFast(Node));
594     return matchesNodeUnqualified(Node);
595   }
596   return matchesNodeFullFast(Node);
597 }
598 
599 // Checks whether \p Loc points to a token with source text of \p TokenText.
600 static bool isTokenAtLoc(const SourceManager &SM, const LangOptions &LangOpts,
601                          StringRef Text, SourceLocation Loc) {
602   llvm::SmallString<16> Buffer;
603   bool Invalid = false;
604   // Since `Loc` may point into an expansion buffer, which has no corresponding
605   // source, we need to look at the spelling location to read the actual source.
606   StringRef TokenText = Lexer::getSpelling(SM.getSpellingLoc(Loc), Buffer, SM,
607                                            LangOpts, &Invalid);
608   return !Invalid && Text == TokenText;
609 }
610 
611 llvm::Optional<SourceLocation>
612 getExpansionLocOfMacro(StringRef MacroName, SourceLocation Loc,
613                        const ASTContext &Context) {
614   auto &SM = Context.getSourceManager();
615   const LangOptions &LangOpts = Context.getLangOpts();
616   while (Loc.isMacroID()) {
617     SrcMgr::ExpansionInfo Expansion =
618         SM.getSLocEntry(SM.getFileID(Loc)).getExpansion();
619     if (Expansion.isMacroArgExpansion())
620       // Check macro argument for an expansion of the given macro. For example,
621       // `F(G(3))`, where `MacroName` is `G`.
622       if (llvm::Optional<SourceLocation> ArgLoc = getExpansionLocOfMacro(
623               MacroName, Expansion.getSpellingLoc(), Context))
624         return ArgLoc;
625     Loc = Expansion.getExpansionLocStart();
626     if (isTokenAtLoc(SM, LangOpts, MacroName, Loc))
627       return Loc;
628   }
629   return llvm::None;
630 }
631 
632 } // end namespace internal
633 
634 const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAutoreleasePoolStmt>
635     autoreleasePoolStmt;
636 const internal::VariadicDynCastAllOfMatcher<Decl, TranslationUnitDecl>
637     translationUnitDecl;
638 const internal::VariadicDynCastAllOfMatcher<Decl, TypedefDecl> typedefDecl;
639 const internal::VariadicDynCastAllOfMatcher<Decl, TypedefNameDecl>
640     typedefNameDecl;
641 const internal::VariadicDynCastAllOfMatcher<Decl, TypeAliasDecl> typeAliasDecl;
642 const internal::VariadicDynCastAllOfMatcher<Decl, TypeAliasTemplateDecl>
643     typeAliasTemplateDecl;
644 const internal::VariadicAllOfMatcher<Decl> decl;
645 const internal::VariadicDynCastAllOfMatcher<Decl, LinkageSpecDecl>
646     linkageSpecDecl;
647 const internal::VariadicDynCastAllOfMatcher<Decl, NamedDecl> namedDecl;
648 const internal::VariadicDynCastAllOfMatcher<Decl, LabelDecl> labelDecl;
649 const internal::VariadicDynCastAllOfMatcher<Decl, NamespaceDecl> namespaceDecl;
650 const internal::VariadicDynCastAllOfMatcher<Decl, NamespaceAliasDecl>
651     namespaceAliasDecl;
652 const internal::VariadicDynCastAllOfMatcher<Decl, RecordDecl> recordDecl;
653 const internal::VariadicDynCastAllOfMatcher<Decl, CXXRecordDecl> cxxRecordDecl;
654 const internal::VariadicDynCastAllOfMatcher<Decl, ClassTemplateDecl>
655     classTemplateDecl;
656 const internal::VariadicDynCastAllOfMatcher<Decl,
657                                             ClassTemplateSpecializationDecl>
658     classTemplateSpecializationDecl;
659 const internal::VariadicDynCastAllOfMatcher<
660     Decl, ClassTemplatePartialSpecializationDecl>
661     classTemplatePartialSpecializationDecl;
662 const internal::VariadicDynCastAllOfMatcher<Decl, DeclaratorDecl>
663     declaratorDecl;
664 const internal::VariadicDynCastAllOfMatcher<Decl, ParmVarDecl> parmVarDecl;
665 const internal::VariadicDynCastAllOfMatcher<Decl, AccessSpecDecl>
666     accessSpecDecl;
667 const internal::VariadicAllOfMatcher<CXXCtorInitializer> cxxCtorInitializer;
668 const internal::VariadicAllOfMatcher<TemplateArgument> templateArgument;
669 const internal::VariadicAllOfMatcher<TemplateName> templateName;
670 const internal::VariadicDynCastAllOfMatcher<Decl, NonTypeTemplateParmDecl>
671     nonTypeTemplateParmDecl;
672 const internal::VariadicDynCastAllOfMatcher<Decl, TemplateTypeParmDecl>
673     templateTypeParmDecl;
674 const internal::VariadicAllOfMatcher<QualType> qualType;
675 const internal::VariadicAllOfMatcher<Type> type;
676 const internal::VariadicAllOfMatcher<TypeLoc> typeLoc;
677 const internal::VariadicDynCastAllOfMatcher<Stmt, UnaryExprOrTypeTraitExpr>
678     unaryExprOrTypeTraitExpr;
679 const internal::VariadicDynCastAllOfMatcher<Decl, ValueDecl> valueDecl;
680 const internal::VariadicDynCastAllOfMatcher<Decl, CXXConstructorDecl>
681     cxxConstructorDecl;
682 const internal::VariadicDynCastAllOfMatcher<Decl, CXXDestructorDecl>
683     cxxDestructorDecl;
684 const internal::VariadicDynCastAllOfMatcher<Decl, EnumDecl> enumDecl;
685 const internal::VariadicDynCastAllOfMatcher<Decl, EnumConstantDecl>
686     enumConstantDecl;
687 const internal::VariadicDynCastAllOfMatcher<Decl, TagDecl> tagDecl;
688 const internal::VariadicDynCastAllOfMatcher<Decl, CXXMethodDecl> cxxMethodDecl;
689 const internal::VariadicDynCastAllOfMatcher<Decl, CXXConversionDecl>
690     cxxConversionDecl;
691 const internal::VariadicDynCastAllOfMatcher<Decl, VarDecl> varDecl;
692 const internal::VariadicDynCastAllOfMatcher<Decl, FieldDecl> fieldDecl;
693 const internal::VariadicDynCastAllOfMatcher<Decl, IndirectFieldDecl>
694     indirectFieldDecl;
695 const internal::VariadicDynCastAllOfMatcher<Decl, FunctionDecl> functionDecl;
696 const internal::VariadicDynCastAllOfMatcher<Decl, FunctionTemplateDecl>
697     functionTemplateDecl;
698 const internal::VariadicDynCastAllOfMatcher<Decl, FriendDecl> friendDecl;
699 const internal::VariadicAllOfMatcher<Stmt> stmt;
700 const internal::VariadicDynCastAllOfMatcher<Stmt, DeclStmt> declStmt;
701 const internal::VariadicDynCastAllOfMatcher<Stmt, MemberExpr> memberExpr;
702 const internal::VariadicDynCastAllOfMatcher<Stmt, UnresolvedMemberExpr>
703     unresolvedMemberExpr;
704 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDependentScopeMemberExpr>
705     cxxDependentScopeMemberExpr;
706 const internal::VariadicDynCastAllOfMatcher<Stmt, CallExpr> callExpr;
707 const internal::VariadicDynCastAllOfMatcher<Stmt, LambdaExpr> lambdaExpr;
708 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXMemberCallExpr>
709     cxxMemberCallExpr;
710 const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCMessageExpr>
711     objcMessageExpr;
712 const internal::VariadicDynCastAllOfMatcher<Decl, ObjCInterfaceDecl>
713     objcInterfaceDecl;
714 const internal::VariadicDynCastAllOfMatcher<Decl, ObjCImplementationDecl>
715     objcImplementationDecl;
716 const internal::VariadicDynCastAllOfMatcher<Decl, ObjCProtocolDecl>
717     objcProtocolDecl;
718 const internal::VariadicDynCastAllOfMatcher<Decl, ObjCCategoryDecl>
719     objcCategoryDecl;
720 const internal::VariadicDynCastAllOfMatcher<Decl, ObjCCategoryImplDecl>
721     objcCategoryImplDecl;
722 const internal::VariadicDynCastAllOfMatcher<Decl, ObjCMethodDecl>
723     objcMethodDecl;
724 const internal::VariadicDynCastAllOfMatcher<Decl, BlockDecl>
725     blockDecl;
726 const internal::VariadicDynCastAllOfMatcher<Decl, ObjCIvarDecl> objcIvarDecl;
727 const internal::VariadicDynCastAllOfMatcher<Decl, ObjCPropertyDecl>
728     objcPropertyDecl;
729 const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAtThrowStmt>
730     objcThrowStmt;
731 const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAtTryStmt> objcTryStmt;
732 const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAtCatchStmt>
733     objcCatchStmt;
734 const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCAtFinallyStmt>
735     objcFinallyStmt;
736 const internal::VariadicDynCastAllOfMatcher<Stmt, ExprWithCleanups>
737     exprWithCleanups;
738 const internal::VariadicDynCastAllOfMatcher<Stmt, InitListExpr> initListExpr;
739 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXStdInitializerListExpr>
740     cxxStdInitializerListExpr;
741 const internal::VariadicDynCastAllOfMatcher<Stmt, ImplicitValueInitExpr>
742     implicitValueInitExpr;
743 const internal::VariadicDynCastAllOfMatcher<Stmt, ParenListExpr> parenListExpr;
744 const internal::VariadicDynCastAllOfMatcher<Stmt, SubstNonTypeTemplateParmExpr>
745     substNonTypeTemplateParmExpr;
746 const internal::VariadicDynCastAllOfMatcher<Decl, UsingDecl> usingDecl;
747 const internal::VariadicDynCastAllOfMatcher<Decl, UsingDirectiveDecl>
748     usingDirectiveDecl;
749 const internal::VariadicDynCastAllOfMatcher<Stmt, UnresolvedLookupExpr>
750     unresolvedLookupExpr;
751 const internal::VariadicDynCastAllOfMatcher<Decl, UnresolvedUsingValueDecl>
752     unresolvedUsingValueDecl;
753 const internal::VariadicDynCastAllOfMatcher<Decl, UnresolvedUsingTypenameDecl>
754     unresolvedUsingTypenameDecl;
755 const internal::VariadicDynCastAllOfMatcher<Stmt, ConstantExpr> constantExpr;
756 const internal::VariadicDynCastAllOfMatcher<Stmt, ParenExpr> parenExpr;
757 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXConstructExpr>
758     cxxConstructExpr;
759 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXUnresolvedConstructExpr>
760     cxxUnresolvedConstructExpr;
761 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXThisExpr> cxxThisExpr;
762 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXBindTemporaryExpr>
763     cxxBindTemporaryExpr;
764 const internal::VariadicDynCastAllOfMatcher<Stmt, MaterializeTemporaryExpr>
765     materializeTemporaryExpr;
766 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNewExpr> cxxNewExpr;
767 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDeleteExpr> cxxDeleteExpr;
768 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNoexceptExpr>
769     cxxNoexceptExpr;
770 const internal::VariadicDynCastAllOfMatcher<Stmt, ArraySubscriptExpr>
771     arraySubscriptExpr;
772 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDefaultArgExpr>
773     cxxDefaultArgExpr;
774 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXOperatorCallExpr>
775     cxxOperatorCallExpr;
776 const internal::VariadicDynCastAllOfMatcher<Stmt, Expr> expr;
777 const internal::VariadicDynCastAllOfMatcher<Stmt, DeclRefExpr> declRefExpr;
778 const internal::VariadicDynCastAllOfMatcher<Stmt, ObjCIvarRefExpr> objcIvarRefExpr;
779 const internal::VariadicDynCastAllOfMatcher<Stmt, BlockExpr> blockExpr;
780 const internal::VariadicDynCastAllOfMatcher<Stmt, IfStmt> ifStmt;
781 const internal::VariadicDynCastAllOfMatcher<Stmt, ForStmt> forStmt;
782 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXForRangeStmt>
783     cxxForRangeStmt;
784 const internal::VariadicDynCastAllOfMatcher<Stmt, WhileStmt> whileStmt;
785 const internal::VariadicDynCastAllOfMatcher<Stmt, DoStmt> doStmt;
786 const internal::VariadicDynCastAllOfMatcher<Stmt, BreakStmt> breakStmt;
787 const internal::VariadicDynCastAllOfMatcher<Stmt, ContinueStmt> continueStmt;
788 const internal::VariadicDynCastAllOfMatcher<Stmt, ReturnStmt> returnStmt;
789 const internal::VariadicDynCastAllOfMatcher<Stmt, GotoStmt> gotoStmt;
790 const internal::VariadicDynCastAllOfMatcher<Stmt, LabelStmt> labelStmt;
791 const internal::VariadicDynCastAllOfMatcher<Stmt, AddrLabelExpr> addrLabelExpr;
792 const internal::VariadicDynCastAllOfMatcher<Stmt, SwitchStmt> switchStmt;
793 const internal::VariadicDynCastAllOfMatcher<Stmt, SwitchCase> switchCase;
794 const internal::VariadicDynCastAllOfMatcher<Stmt, CaseStmt> caseStmt;
795 const internal::VariadicDynCastAllOfMatcher<Stmt, DefaultStmt> defaultStmt;
796 const internal::VariadicDynCastAllOfMatcher<Stmt, CompoundStmt> compoundStmt;
797 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXCatchStmt> cxxCatchStmt;
798 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXTryStmt> cxxTryStmt;
799 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXThrowExpr> cxxThrowExpr;
800 const internal::VariadicDynCastAllOfMatcher<Stmt, NullStmt> nullStmt;
801 const internal::VariadicDynCastAllOfMatcher<Stmt, AsmStmt> asmStmt;
802 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXBoolLiteralExpr>
803     cxxBoolLiteral;
804 const internal::VariadicDynCastAllOfMatcher<Stmt, StringLiteral> stringLiteral;
805 const internal::VariadicDynCastAllOfMatcher<Stmt, CharacterLiteral>
806     characterLiteral;
807 const internal::VariadicDynCastAllOfMatcher<Stmt, IntegerLiteral>
808     integerLiteral;
809 const internal::VariadicDynCastAllOfMatcher<Stmt, FloatingLiteral> floatLiteral;
810 const internal::VariadicDynCastAllOfMatcher<Stmt, ImaginaryLiteral> imaginaryLiteral;
811 const internal::VariadicDynCastAllOfMatcher<Stmt, UserDefinedLiteral>
812     userDefinedLiteral;
813 const internal::VariadicDynCastAllOfMatcher<Stmt, CompoundLiteralExpr>
814     compoundLiteralExpr;
815 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNullPtrLiteralExpr>
816     cxxNullPtrLiteralExpr;
817 const internal::VariadicDynCastAllOfMatcher<Stmt, ChooseExpr> chooseExpr;
818 const internal::VariadicDynCastAllOfMatcher<Stmt, GNUNullExpr> gnuNullExpr;
819 const internal::VariadicDynCastAllOfMatcher<Stmt, AtomicExpr> atomicExpr;
820 const internal::VariadicDynCastAllOfMatcher<Stmt, StmtExpr> stmtExpr;
821 const internal::VariadicDynCastAllOfMatcher<Stmt, BinaryOperator>
822     binaryOperator;
823 const internal::VariadicDynCastAllOfMatcher<Stmt, UnaryOperator> unaryOperator;
824 const internal::VariadicDynCastAllOfMatcher<Stmt, ConditionalOperator>
825     conditionalOperator;
826 const internal::VariadicDynCastAllOfMatcher<Stmt, BinaryConditionalOperator>
827     binaryConditionalOperator;
828 const internal::VariadicDynCastAllOfMatcher<Stmt, OpaqueValueExpr>
829     opaqueValueExpr;
830 const internal::VariadicDynCastAllOfMatcher<Decl, StaticAssertDecl>
831     staticAssertDecl;
832 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXReinterpretCastExpr>
833     cxxReinterpretCastExpr;
834 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXStaticCastExpr>
835     cxxStaticCastExpr;
836 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXDynamicCastExpr>
837     cxxDynamicCastExpr;
838 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXConstCastExpr>
839     cxxConstCastExpr;
840 const internal::VariadicDynCastAllOfMatcher<Stmt, CStyleCastExpr>
841     cStyleCastExpr;
842 const internal::VariadicDynCastAllOfMatcher<Stmt, ExplicitCastExpr>
843     explicitCastExpr;
844 const internal::VariadicDynCastAllOfMatcher<Stmt, ImplicitCastExpr>
845     implicitCastExpr;
846 const internal::VariadicDynCastAllOfMatcher<Stmt, CastExpr> castExpr;
847 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXFunctionalCastExpr>
848     cxxFunctionalCastExpr;
849 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXTemporaryObjectExpr>
850     cxxTemporaryObjectExpr;
851 const internal::VariadicDynCastAllOfMatcher<Stmt, PredefinedExpr>
852     predefinedExpr;
853 const internal::VariadicDynCastAllOfMatcher<Stmt, DesignatedInitExpr>
854     designatedInitExpr;
855 const internal::VariadicOperatorMatcherFunc<
856     2, std::numeric_limits<unsigned>::max()>
857     eachOf = {internal::DynTypedMatcher::VO_EachOf};
858 const internal::VariadicOperatorMatcherFunc<
859     2, std::numeric_limits<unsigned>::max()>
860     anyOf = {internal::DynTypedMatcher::VO_AnyOf};
861 const internal::VariadicOperatorMatcherFunc<
862     2, std::numeric_limits<unsigned>::max()>
863     allOf = {internal::DynTypedMatcher::VO_AllOf};
864 const internal::VariadicOperatorMatcherFunc<
865     1, std::numeric_limits<unsigned>::max()>
866     optionally = {internal::DynTypedMatcher::VO_Optionally};
867 const internal::VariadicFunction<internal::Matcher<NamedDecl>, StringRef,
868                                  internal::hasAnyNameFunc>
869     hasAnyName = {};
870 const internal::VariadicFunction<internal::Matcher<ObjCMessageExpr>, StringRef,
871                                  internal::hasAnySelectorFunc>
872     hasAnySelector = {};
873 const internal::ArgumentAdaptingMatcherFunc<internal::HasMatcher> has = {};
874 const internal::ArgumentAdaptingMatcherFunc<internal::HasDescendantMatcher>
875     hasDescendant = {};
876 const internal::ArgumentAdaptingMatcherFunc<internal::ForEachMatcher> forEach =
877     {};
878 const internal::ArgumentAdaptingMatcherFunc<internal::ForEachDescendantMatcher>
879     forEachDescendant = {};
880 const internal::ArgumentAdaptingMatcherFunc<
881     internal::HasParentMatcher,
882     internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>,
883     internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>>
884     hasParent = {};
885 const internal::ArgumentAdaptingMatcherFunc<
886     internal::HasAncestorMatcher,
887     internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>,
888     internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>>
889     hasAncestor = {};
890 const internal::VariadicOperatorMatcherFunc<1, 1> unless = {
891     internal::DynTypedMatcher::VO_UnaryNot};
892 const internal::VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier;
893 const internal::VariadicAllOfMatcher<NestedNameSpecifierLoc>
894     nestedNameSpecifierLoc;
895 const internal::VariadicDynCastAllOfMatcher<Stmt, CUDAKernelCallExpr>
896     cudaKernelCallExpr;
897 const AstTypeMatcher<BuiltinType> builtinType;
898 const AstTypeMatcher<ArrayType> arrayType;
899 const AstTypeMatcher<ComplexType> complexType;
900 const AstTypeMatcher<ConstantArrayType> constantArrayType;
901 const AstTypeMatcher<DeducedTemplateSpecializationType>
902     deducedTemplateSpecializationType;
903 const AstTypeMatcher<DependentSizedArrayType> dependentSizedArrayType;
904 const AstTypeMatcher<IncompleteArrayType> incompleteArrayType;
905 const AstTypeMatcher<VariableArrayType> variableArrayType;
906 const AstTypeMatcher<AtomicType> atomicType;
907 const AstTypeMatcher<AutoType> autoType;
908 const AstTypeMatcher<DecltypeType> decltypeType;
909 const AstTypeMatcher<FunctionType> functionType;
910 const AstTypeMatcher<FunctionProtoType> functionProtoType;
911 const AstTypeMatcher<ParenType> parenType;
912 const AstTypeMatcher<BlockPointerType> blockPointerType;
913 const AstTypeMatcher<MemberPointerType> memberPointerType;
914 const AstTypeMatcher<PointerType> pointerType;
915 const AstTypeMatcher<ObjCObjectPointerType> objcObjectPointerType;
916 const AstTypeMatcher<ReferenceType> referenceType;
917 const AstTypeMatcher<LValueReferenceType> lValueReferenceType;
918 const AstTypeMatcher<RValueReferenceType> rValueReferenceType;
919 const AstTypeMatcher<TypedefType> typedefType;
920 const AstTypeMatcher<EnumType> enumType;
921 const AstTypeMatcher<TemplateSpecializationType> templateSpecializationType;
922 const AstTypeMatcher<UnaryTransformType> unaryTransformType;
923 const AstTypeMatcher<RecordType> recordType;
924 const AstTypeMatcher<TagType> tagType;
925 const AstTypeMatcher<ElaboratedType> elaboratedType;
926 const AstTypeMatcher<SubstTemplateTypeParmType> substTemplateTypeParmType;
927 const AstTypeMatcher<TemplateTypeParmType> templateTypeParmType;
928 const AstTypeMatcher<InjectedClassNameType> injectedClassNameType;
929 const AstTypeMatcher<DecayedType> decayedType;
930 AST_TYPELOC_TRAVERSE_MATCHER_DEF(hasElementType,
931                                  AST_POLYMORPHIC_SUPPORTED_TYPES(ArrayType,
932                                                                  ComplexType));
933 AST_TYPELOC_TRAVERSE_MATCHER_DEF(hasValueType,
934                                  AST_POLYMORPHIC_SUPPORTED_TYPES(AtomicType));
935 AST_TYPELOC_TRAVERSE_MATCHER_DEF(
936     pointee,
937     AST_POLYMORPHIC_SUPPORTED_TYPES(BlockPointerType, MemberPointerType,
938                                     PointerType, ReferenceType));
939 
940 const internal::VariadicDynCastAllOfMatcher<Stmt, OMPExecutableDirective>
941     ompExecutableDirective;
942 const internal::VariadicDynCastAllOfMatcher<OMPClause, OMPDefaultClause>
943     ompDefaultClause;
944 const internal::VariadicDynCastAllOfMatcher<Decl, CXXDeductionGuideDecl>
945     cxxDeductionGuideDecl;
946 
947 } // end namespace ast_matchers
948 } // end namespace clang
949