• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- ASTMatchersInternal.cpp - Structural query framework -------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  Implements the base layer of the matcher framework.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/ASTMatchers/ASTMatchers.h"
15 #include "clang/ASTMatchers/ASTMatchersInternal.h"
16 #include "llvm/ADT/SmallString.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Support/ManagedStatic.h"
19 
20 namespace clang {
21 namespace ast_matchers {
22 namespace internal {
23 
24 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
25                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
26                       ArrayRef<DynTypedMatcher> InnerMatchers);
27 
28 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
29                            ASTMatchFinder *Finder,
30                            BoundNodesTreeBuilder *Builder,
31                            ArrayRef<DynTypedMatcher> InnerMatchers);
32 
33 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
34                             ASTMatchFinder *Finder,
35                             BoundNodesTreeBuilder *Builder,
36                             ArrayRef<DynTypedMatcher> InnerMatchers);
37 
38 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
39                            ASTMatchFinder *Finder,
40                            BoundNodesTreeBuilder *Builder,
41                            ArrayRef<DynTypedMatcher> InnerMatchers);
42 
43 
visitMatches(Visitor * ResultVisitor)44 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
45   if (Bindings.empty())
46     Bindings.push_back(BoundNodesMap());
47   for (BoundNodesMap &Binding : Bindings) {
48     ResultVisitor->visitMatch(BoundNodes(Binding));
49   }
50 }
51 
52 namespace {
53 
54 typedef bool (*VariadicOperatorFunction)(
55     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
56     BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
57 
58 template <VariadicOperatorFunction Func>
59 class VariadicMatcher : public DynMatcherInterface {
60 public:
VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers)61   VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers)
62       : InnerMatchers(std::move(InnerMatchers)) {}
63 
dynMatches(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder) const64   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
65                   ASTMatchFinder *Finder,
66                   BoundNodesTreeBuilder *Builder) const override {
67     return Func(DynNode, Finder, Builder, InnerMatchers);
68   }
69 
70 private:
71   std::vector<DynTypedMatcher> InnerMatchers;
72 };
73 
74 class IdDynMatcher : public DynMatcherInterface {
75  public:
IdDynMatcher(StringRef ID,const IntrusiveRefCntPtr<DynMatcherInterface> & InnerMatcher)76   IdDynMatcher(StringRef ID,
77                const IntrusiveRefCntPtr<DynMatcherInterface> &InnerMatcher)
78       : ID(ID), InnerMatcher(InnerMatcher) {}
79 
dynMatches(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder) const80   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
81                   ASTMatchFinder *Finder,
82                   BoundNodesTreeBuilder *Builder) const override {
83     bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder);
84     if (Result) Builder->setBinding(ID, DynNode);
85     return Result;
86   }
87 
88  private:
89   const std::string ID;
90   const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
91 };
92 
93 /// \brief A matcher that always returns true.
94 ///
95 /// We only ever need one instance of this matcher, so we create a global one
96 /// and reuse it to reduce the overhead of the matcher and increase the chance
97 /// of cache hits.
98 class TrueMatcherImpl : public DynMatcherInterface {
99 public:
TrueMatcherImpl()100   TrueMatcherImpl() {
101     Retain(); // Reference count will never become zero.
102   }
dynMatches(const ast_type_traits::DynTypedNode &,ASTMatchFinder *,BoundNodesTreeBuilder *) const103   bool dynMatches(const ast_type_traits::DynTypedNode &, ASTMatchFinder *,
104                   BoundNodesTreeBuilder *) const override {
105     return true;
106   }
107 };
108 static llvm::ManagedStatic<TrueMatcherImpl> TrueMatcherInstance;
109 
110 }  // namespace
111 
constructVariadic(DynTypedMatcher::VariadicOperator Op,ast_type_traits::ASTNodeKind SupportedKind,std::vector<DynTypedMatcher> InnerMatchers)112 DynTypedMatcher DynTypedMatcher::constructVariadic(
113     DynTypedMatcher::VariadicOperator Op,
114     ast_type_traits::ASTNodeKind SupportedKind,
115     std::vector<DynTypedMatcher> InnerMatchers) {
116   assert(InnerMatchers.size() > 0 && "Array must not be empty.");
117   assert(std::all_of(InnerMatchers.begin(), InnerMatchers.end(),
118                      [SupportedKind](const DynTypedMatcher &M) {
119                        return M.canConvertTo(SupportedKind);
120                      }) &&
121          "InnerMatchers must be convertible to SupportedKind!");
122 
123   // We must relax the restrict kind here.
124   // The different operators might deal differently with a mismatch.
125   // Make it the same as SupportedKind, since that is the broadest type we are
126   // allowed to accept.
127   auto RestrictKind = SupportedKind;
128 
129   switch (Op) {
130   case VO_AllOf:
131     // In the case of allOf() we must pass all the checks, so making
132     // RestrictKind the most restrictive can save us time. This way we reject
133     // invalid types earlier and we can elide the kind checks inside the
134     // matcher.
135     for (auto &IM : InnerMatchers) {
136       RestrictKind = ast_type_traits::ASTNodeKind::getMostDerivedType(
137           RestrictKind, IM.RestrictKind);
138     }
139     return DynTypedMatcher(
140         SupportedKind, RestrictKind,
141         new VariadicMatcher<AllOfVariadicOperator>(std::move(InnerMatchers)));
142 
143   case VO_AnyOf:
144     return DynTypedMatcher(
145         SupportedKind, RestrictKind,
146         new VariadicMatcher<AnyOfVariadicOperator>(std::move(InnerMatchers)));
147 
148   case VO_EachOf:
149     return DynTypedMatcher(
150         SupportedKind, RestrictKind,
151         new VariadicMatcher<EachOfVariadicOperator>(std::move(InnerMatchers)));
152 
153   case VO_UnaryNot:
154     // FIXME: Implement the Not operator to take a single matcher instead of a
155     // vector.
156     return DynTypedMatcher(
157         SupportedKind, RestrictKind,
158         new VariadicMatcher<NotUnaryOperator>(std::move(InnerMatchers)));
159   }
160   llvm_unreachable("Invalid Op value.");
161 }
162 
trueMatcher(ast_type_traits::ASTNodeKind NodeKind)163 DynTypedMatcher DynTypedMatcher::trueMatcher(
164     ast_type_traits::ASTNodeKind NodeKind) {
165   return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
166 }
167 
canMatchNodesOfKind(ast_type_traits::ASTNodeKind Kind) const168 bool DynTypedMatcher::canMatchNodesOfKind(
169     ast_type_traits::ASTNodeKind Kind) const {
170   return RestrictKind.isBaseOf(Kind);
171 }
172 
dynCastTo(const ast_type_traits::ASTNodeKind Kind) const173 DynTypedMatcher DynTypedMatcher::dynCastTo(
174     const ast_type_traits::ASTNodeKind Kind) const {
175   auto Copy = *this;
176   Copy.SupportedKind = Kind;
177   Copy.RestrictKind =
178       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
179   return Copy;
180 }
181 
matches(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder) const182 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
183                               ASTMatchFinder *Finder,
184                               BoundNodesTreeBuilder *Builder) const {
185   if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
186       Implementation->dynMatches(DynNode, Finder, Builder)) {
187     return true;
188   }
189   // Delete all bindings when a matcher does not match.
190   // This prevents unexpected exposure of bound nodes in unmatches
191   // branches of the match tree.
192   Builder->removeBindings([](const BoundNodesMap &) { return true; });
193   return false;
194 }
195 
matchesNoKindCheck(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder) const196 bool DynTypedMatcher::matchesNoKindCheck(
197     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
198     BoundNodesTreeBuilder *Builder) const {
199   assert(RestrictKind.isBaseOf(DynNode.getNodeKind()));
200   if (Implementation->dynMatches(DynNode, Finder, Builder)) {
201     return true;
202   }
203   // Delete all bindings when a matcher does not match.
204   // This prevents unexpected exposure of bound nodes in unmatches
205   // branches of the match tree.
206   Builder->removeBindings([](const BoundNodesMap &) { return true; });
207   return false;
208 }
209 
tryBind(StringRef ID) const210 llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
211   if (!AllowBind) return llvm::None;
212   auto Result = *this;
213   Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
214   return Result;
215 }
216 
canConvertTo(ast_type_traits::ASTNodeKind To) const217 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
218   const auto From = getSupportedKind();
219   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
220   auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
221   /// Mimic the implicit conversions of Matcher<>.
222   /// - From Matcher<Type> to Matcher<QualType>
223   if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
224   /// - From Matcher<Base> to Matcher<Derived>
225   return From.isBaseOf(To);
226 }
227 
addMatch(const BoundNodesTreeBuilder & Other)228 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
229   Bindings.append(Other.Bindings.begin(), Other.Bindings.end());
230 }
231 
NotUnaryOperator(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,ArrayRef<DynTypedMatcher> InnerMatchers)232 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
233                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
234                       ArrayRef<DynTypedMatcher> InnerMatchers) {
235   if (InnerMatchers.size() != 1)
236     return false;
237 
238   // The 'unless' matcher will always discard the result:
239   // If the inner matcher doesn't match, unless returns true,
240   // but the inner matcher cannot have bound anything.
241   // If the inner matcher matches, the result is false, and
242   // any possible binding will be discarded.
243   // We still need to hand in all the bound nodes up to this
244   // point so the inner matcher can depend on bound nodes,
245   // and we need to actively discard the bound nodes, otherwise
246   // the inner matcher will reset the bound nodes if it doesn't
247   // match, but this would be inversed by 'unless'.
248   BoundNodesTreeBuilder Discard(*Builder);
249   return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
250 }
251 
AllOfVariadicOperator(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,ArrayRef<DynTypedMatcher> InnerMatchers)252 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
253                            ASTMatchFinder *Finder,
254                            BoundNodesTreeBuilder *Builder,
255                            ArrayRef<DynTypedMatcher> InnerMatchers) {
256   // allOf leads to one matcher for each alternative in the first
257   // matcher combined with each alternative in the second matcher.
258   // Thus, we can reuse the same Builder.
259   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
260     if (!InnerMatcher.matchesNoKindCheck(DynNode, Finder, Builder))
261       return false;
262   }
263   return true;
264 }
265 
EachOfVariadicOperator(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,ArrayRef<DynTypedMatcher> InnerMatchers)266 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
267                             ASTMatchFinder *Finder,
268                             BoundNodesTreeBuilder *Builder,
269                             ArrayRef<DynTypedMatcher> InnerMatchers) {
270   BoundNodesTreeBuilder Result;
271   bool Matched = false;
272   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
273     BoundNodesTreeBuilder BuilderInner(*Builder);
274     if (InnerMatcher.matches(DynNode, Finder, &BuilderInner)) {
275       Matched = true;
276       Result.addMatch(BuilderInner);
277     }
278   }
279   *Builder = std::move(Result);
280   return Matched;
281 }
282 
AnyOfVariadicOperator(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,ArrayRef<DynTypedMatcher> InnerMatchers)283 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
284                            ASTMatchFinder *Finder,
285                            BoundNodesTreeBuilder *Builder,
286                            ArrayRef<DynTypedMatcher> InnerMatchers) {
287   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
288     BoundNodesTreeBuilder Result = *Builder;
289     if (InnerMatcher.matches(DynNode, Finder, &Result)) {
290       *Builder = std::move(Result);
291       return true;
292     }
293   }
294   return false;
295 }
296 
hasAnyNameFunc(ArrayRef<const StringRef * > NameRefs)297 Matcher<NamedDecl> hasAnyNameFunc(ArrayRef<const StringRef *> NameRefs) {
298   std::vector<std::string> Names;
299   for (auto *Name : NameRefs)
300     Names.emplace_back(*Name);
301   return internal::Matcher<NamedDecl>(
302       new internal::HasNameMatcher(std::move(Names)));
303 }
304 
HasNameMatcher(std::vector<std::string> N)305 HasNameMatcher::HasNameMatcher(std::vector<std::string> N)
306     : UseUnqualifiedMatch(std::all_of(
307           N.begin(), N.end(),
308           [](StringRef Name) { return Name.find("::") == Name.npos; })),
309       Names(std::move(N)) {
310 #ifndef NDEBUG
311   for (StringRef Name : Names)
312     assert(!Name.empty());
313 #endif
314 }
315 
316 namespace {
317 
consumeNameSuffix(StringRef & FullName,StringRef Suffix)318 bool consumeNameSuffix(StringRef &FullName, StringRef Suffix) {
319   StringRef Name = FullName;
320   if (!Name.endswith(Suffix))
321     return false;
322   Name = Name.drop_back(Suffix.size());
323   if (!Name.empty()) {
324     if (!Name.endswith("::"))
325       return false;
326     Name = Name.drop_back(2);
327   }
328   FullName = Name;
329   return true;
330 }
331 
getNodeName(const NamedDecl & Node,llvm::SmallString<128> & Scratch)332 StringRef getNodeName(const NamedDecl &Node, llvm::SmallString<128> &Scratch) {
333   // Simple name.
334   if (Node.getIdentifier())
335     return Node.getName();
336 
337   if (Node.getDeclName()) {
338     // Name needs to be constructed.
339     Scratch.clear();
340     llvm::raw_svector_ostream OS(Scratch);
341     Node.printName(OS);
342     return OS.str();
343   }
344 
345   return "(anonymous)";
346 }
347 
getNodeName(const RecordDecl & Node,llvm::SmallString<128> & Scratch)348 StringRef getNodeName(const RecordDecl &Node, llvm::SmallString<128> &Scratch) {
349   if (Node.getIdentifier()) {
350     return Node.getName();
351   }
352   Scratch.clear();
353   return ("(anonymous " + Node.getKindName() + ")").toStringRef(Scratch);
354 }
355 
getNodeName(const NamespaceDecl & Node,llvm::SmallString<128> & Scratch)356 StringRef getNodeName(const NamespaceDecl &Node,
357                       llvm::SmallString<128> &Scratch) {
358   return Node.isAnonymousNamespace() ? "(anonymous namespace)" : Node.getName();
359 }
360 
361 
362 class PatternSet {
363 public:
PatternSet(ArrayRef<std::string> Names)364   PatternSet(ArrayRef<std::string> Names) {
365     for (StringRef Name : Names)
366       Patterns.push_back({Name, Name.startswith("::")});
367   }
368 
369   /// Consumes the name suffix from each pattern in the set and removes the ones
370   /// that didn't match.
371   /// Return true if there are still any patterns left.
consumeNameSuffix(StringRef NodeName,bool CanSkip)372   bool consumeNameSuffix(StringRef NodeName, bool CanSkip) {
373     for (size_t I = 0; I < Patterns.size();) {
374       if (internal::consumeNameSuffix(Patterns[I].P, NodeName) ||
375           CanSkip) {
376         ++I;
377       } else {
378         Patterns.erase(Patterns.begin() + I);
379       }
380     }
381     return !Patterns.empty();
382   }
383 
384   /// Check if any of the patterns are a match.
385   /// A match will be a pattern that was fully consumed, that also matches the
386   /// 'fully qualified' requirement.
foundMatch(bool AllowFullyQualified) const387   bool foundMatch(bool AllowFullyQualified) const {
388     for (auto& P: Patterns)
389       if (P.P.empty() && (AllowFullyQualified || !P.IsFullyQualified))
390         return true;
391     return false;
392   }
393 
394 private:
395   struct Pattern {
396     StringRef P;
397     bool IsFullyQualified;
398   };
399   llvm::SmallVector<Pattern, 8> Patterns;
400 };
401 
402 }  // namespace
403 
matchesNodeUnqualified(const NamedDecl & Node) const404 bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
405   assert(UseUnqualifiedMatch);
406   llvm::SmallString<128> Scratch;
407   StringRef NodeName = getNodeName(Node, Scratch);
408   return std::any_of(Names.begin(), Names.end(), [&](StringRef Name) {
409     return consumeNameSuffix(Name, NodeName) && Name.empty();
410   });
411 }
412 
matchesNodeFullFast(const NamedDecl & Node) const413 bool HasNameMatcher::matchesNodeFullFast(const NamedDecl &Node) const {
414   PatternSet Patterns(Names);
415   llvm::SmallString<128> Scratch;
416 
417   // This function is copied and adapted from NamedDecl::printQualifiedName()
418   // By matching each part individually we optimize in a couple of ways:
419   //  - We can exit early on the first failure.
420   //  - We can skip inline/anonymous namespaces without another pass.
421   //  - We print one name at a time, reducing the chance of overflowing the
422   //    inlined space of the SmallString.
423 
424   // First, match the name.
425   if (!Patterns.consumeNameSuffix(getNodeName(Node, Scratch),
426                                   /*CanSkip=*/false))
427     return false;
428 
429   // Try to match each declaration context.
430   // We are allowed to skip anonymous and inline namespaces if they don't match.
431   const DeclContext *Ctx = Node.getDeclContext();
432 
433   if (Ctx->isFunctionOrMethod())
434     return Patterns.foundMatch(/*AllowFullyQualified=*/false);
435 
436   for (; Ctx && isa<NamedDecl>(Ctx); Ctx = Ctx->getParent()) {
437     if (Patterns.foundMatch(/*AllowFullyQualified=*/false))
438       return true;
439 
440     if (const auto *ND = dyn_cast<NamespaceDecl>(Ctx)) {
441       // If it matches (or we can skip it), continue.
442       if (Patterns.consumeNameSuffix(getNodeName(*ND, Scratch),
443                                      /*CanSkip=*/ND->isAnonymousNamespace() ||
444                                          ND->isInline()))
445         continue;
446       return false;
447     }
448     if (const auto *RD = dyn_cast<RecordDecl>(Ctx)) {
449       if (!isa<ClassTemplateSpecializationDecl>(Ctx)) {
450         if (Patterns.consumeNameSuffix(getNodeName(*RD, Scratch),
451                                        /*CanSkip=*/false))
452           continue;
453 
454         return false;
455       }
456     }
457 
458     // We don't know how to deal with this DeclContext.
459     // Fallback to the slow version of the code.
460     return matchesNodeFullSlow(Node);
461   }
462 
463   return Patterns.foundMatch(/*AllowFullyQualified=*/true);
464 }
465 
matchesNodeFullSlow(const NamedDecl & Node) const466 bool HasNameMatcher::matchesNodeFullSlow(const NamedDecl &Node) const {
467   const bool SkipUnwrittenCases[] = {false, true};
468   for (bool SkipUnwritten : SkipUnwrittenCases) {
469     llvm::SmallString<128> NodeName = StringRef("::");
470     llvm::raw_svector_ostream OS(NodeName);
471 
472     if (SkipUnwritten) {
473       PrintingPolicy Policy = Node.getASTContext().getPrintingPolicy();
474       Policy.SuppressUnwrittenScope = true;
475       Node.printQualifiedName(OS, Policy);
476     } else {
477       Node.printQualifiedName(OS);
478     }
479 
480     const StringRef FullName = OS.str();
481 
482     for (const StringRef Pattern : Names) {
483       if (Pattern.startswith("::")) {
484         if (FullName == Pattern)
485           return true;
486       } else if (FullName.endswith(Pattern) &&
487                  FullName.drop_back(Pattern.size()).endswith("::")) {
488         return true;
489       }
490     }
491   }
492 
493   return false;
494 }
495 
matchesNode(const NamedDecl & Node) const496 bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
497   assert(matchesNodeFullFast(Node) == matchesNodeFullSlow(Node));
498   if (UseUnqualifiedMatch) {
499     assert(matchesNodeUnqualified(Node) == matchesNodeFullFast(Node));
500     return matchesNodeUnqualified(Node);
501   }
502   return matchesNodeFullFast(Node);
503 }
504 
505 } // end namespace internal
506 } // end namespace ast_matchers
507 } // end namespace clang
508