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/Support/ManagedStatic.h"
18 
19 namespace clang {
20 namespace ast_matchers {
21 namespace internal {
22 
23 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
24                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
25                       ArrayRef<DynTypedMatcher> InnerMatchers);
26 
27 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
28                            ASTMatchFinder *Finder,
29                            BoundNodesTreeBuilder *Builder,
30                            ArrayRef<DynTypedMatcher> InnerMatchers);
31 
32 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
33                             ASTMatchFinder *Finder,
34                             BoundNodesTreeBuilder *Builder,
35                             ArrayRef<DynTypedMatcher> InnerMatchers);
36 
37 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
38                            ASTMatchFinder *Finder,
39                            BoundNodesTreeBuilder *Builder,
40                            ArrayRef<DynTypedMatcher> InnerMatchers);
41 
42 
visitMatches(Visitor * ResultVisitor)43 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
44   if (Bindings.empty())
45     Bindings.push_back(BoundNodesMap());
46   for (BoundNodesMap &Binding : Bindings) {
47     ResultVisitor->visitMatch(BoundNodes(Binding));
48   }
49 }
50 
51 namespace {
52 
53 typedef bool (*VariadicOperatorFunction)(
54     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
55     BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
56 
57 template <VariadicOperatorFunction Func>
58 class VariadicMatcher : public DynMatcherInterface {
59 public:
VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers)60   VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers)
61       : InnerMatchers(std::move(InnerMatchers)) {}
62 
dynMatches(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder) const63   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
64                   ASTMatchFinder *Finder,
65                   BoundNodesTreeBuilder *Builder) const override {
66     return Func(DynNode, Finder, Builder, InnerMatchers);
67   }
68 
69 private:
70   std::vector<DynTypedMatcher> InnerMatchers;
71 };
72 
73 class IdDynMatcher : public DynMatcherInterface {
74  public:
IdDynMatcher(StringRef ID,const IntrusiveRefCntPtr<DynMatcherInterface> & InnerMatcher)75   IdDynMatcher(StringRef ID,
76                const IntrusiveRefCntPtr<DynMatcherInterface> &InnerMatcher)
77       : ID(ID), InnerMatcher(InnerMatcher) {}
78 
dynMatches(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder) const79   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
80                   ASTMatchFinder *Finder,
81                   BoundNodesTreeBuilder *Builder) const override {
82     bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder);
83     if (Result) Builder->setBinding(ID, DynNode);
84     return Result;
85   }
86 
87  private:
88   const std::string ID;
89   const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
90 };
91 
92 /// \brief A matcher that always returns true.
93 ///
94 /// We only ever need one instance of this matcher, so we create a global one
95 /// and reuse it to reduce the overhead of the matcher and increase the chance
96 /// of cache hits.
97 class TrueMatcherImpl : public DynMatcherInterface {
98 public:
TrueMatcherImpl()99   TrueMatcherImpl() {
100     Retain(); // Reference count will never become zero.
101   }
dynMatches(const ast_type_traits::DynTypedNode &,ASTMatchFinder *,BoundNodesTreeBuilder *) const102   bool dynMatches(const ast_type_traits::DynTypedNode &, ASTMatchFinder *,
103                   BoundNodesTreeBuilder *) const override {
104     return true;
105   }
106 };
107 static llvm::ManagedStatic<TrueMatcherImpl> TrueMatcherInstance;
108 
109 }  // namespace
110 
constructVariadic(DynTypedMatcher::VariadicOperator Op,ast_type_traits::ASTNodeKind SupportedKind,std::vector<DynTypedMatcher> InnerMatchers)111 DynTypedMatcher DynTypedMatcher::constructVariadic(
112     DynTypedMatcher::VariadicOperator Op,
113     ast_type_traits::ASTNodeKind SupportedKind,
114     std::vector<DynTypedMatcher> InnerMatchers) {
115   assert(InnerMatchers.size() > 0 && "Array must not be empty.");
116   assert(std::all_of(InnerMatchers.begin(), InnerMatchers.end(),
117                      [SupportedKind](const DynTypedMatcher &M) {
118                        return M.canConvertTo(SupportedKind);
119                      }) &&
120          "InnerMatchers must be convertible to SupportedKind!");
121 
122   // We must relax the restrict kind here.
123   // The different operators might deal differently with a mismatch.
124   // Make it the same as SupportedKind, since that is the broadest type we are
125   // allowed to accept.
126   auto RestrictKind = SupportedKind;
127 
128   switch (Op) {
129   case VO_AllOf:
130     // In the case of allOf() we must pass all the checks, so making
131     // RestrictKind the most restrictive can save us time. This way we reject
132     // invalid types earlier and we can elide the kind checks inside the
133     // matcher.
134     for (auto &IM : InnerMatchers) {
135       RestrictKind = ast_type_traits::ASTNodeKind::getMostDerivedType(
136           RestrictKind, IM.RestrictKind);
137     }
138     return DynTypedMatcher(
139         SupportedKind, RestrictKind,
140         new VariadicMatcher<AllOfVariadicOperator>(std::move(InnerMatchers)));
141 
142   case VO_AnyOf:
143     return DynTypedMatcher(
144         SupportedKind, RestrictKind,
145         new VariadicMatcher<AnyOfVariadicOperator>(std::move(InnerMatchers)));
146 
147   case VO_EachOf:
148     return DynTypedMatcher(
149         SupportedKind, RestrictKind,
150         new VariadicMatcher<EachOfVariadicOperator>(std::move(InnerMatchers)));
151 
152   case VO_UnaryNot:
153     // FIXME: Implement the Not operator to take a single matcher instead of a
154     // vector.
155     return DynTypedMatcher(
156         SupportedKind, RestrictKind,
157         new VariadicMatcher<NotUnaryOperator>(std::move(InnerMatchers)));
158   }
159   llvm_unreachable("Invalid Op value.");
160 }
161 
trueMatcher(ast_type_traits::ASTNodeKind NodeKind)162 DynTypedMatcher DynTypedMatcher::trueMatcher(
163     ast_type_traits::ASTNodeKind NodeKind) {
164   return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
165 }
166 
canMatchNodesOfKind(ast_type_traits::ASTNodeKind Kind) const167 bool DynTypedMatcher::canMatchNodesOfKind(
168     ast_type_traits::ASTNodeKind Kind) const {
169   return RestrictKind.isBaseOf(Kind);
170 }
171 
dynCastTo(const ast_type_traits::ASTNodeKind Kind) const172 DynTypedMatcher DynTypedMatcher::dynCastTo(
173     const ast_type_traits::ASTNodeKind Kind) const {
174   auto Copy = *this;
175   Copy.SupportedKind = Kind;
176   Copy.RestrictKind =
177       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
178   return Copy;
179 }
180 
matches(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder) const181 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
182                               ASTMatchFinder *Finder,
183                               BoundNodesTreeBuilder *Builder) const {
184   if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
185       Implementation->dynMatches(DynNode, Finder, Builder)) {
186     return true;
187   }
188   // Delete all bindings when a matcher does not match.
189   // This prevents unexpected exposure of bound nodes in unmatches
190   // branches of the match tree.
191   Builder->removeBindings([](const BoundNodesMap &) { return true; });
192   return false;
193 }
194 
matchesNoKindCheck(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder) const195 bool DynTypedMatcher::matchesNoKindCheck(
196     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
197     BoundNodesTreeBuilder *Builder) const {
198   assert(RestrictKind.isBaseOf(DynNode.getNodeKind()));
199   if (Implementation->dynMatches(DynNode, Finder, Builder)) {
200     return true;
201   }
202   // Delete all bindings when a matcher does not match.
203   // This prevents unexpected exposure of bound nodes in unmatches
204   // branches of the match tree.
205   Builder->removeBindings([](const BoundNodesMap &) { return true; });
206   return false;
207 }
208 
tryBind(StringRef ID) const209 llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
210   if (!AllowBind) return llvm::None;
211   auto Result = *this;
212   Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
213   return Result;
214 }
215 
canConvertTo(ast_type_traits::ASTNodeKind To) const216 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
217   const auto From = getSupportedKind();
218   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
219   auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
220   /// Mimic the implicit conversions of Matcher<>.
221   /// - From Matcher<Type> to Matcher<QualType>
222   if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
223   /// - From Matcher<Base> to Matcher<Derived>
224   return From.isBaseOf(To);
225 }
226 
addMatch(const BoundNodesTreeBuilder & Other)227 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
228   Bindings.append(Other.Bindings.begin(), Other.Bindings.end());
229 }
230 
NotUnaryOperator(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,ArrayRef<DynTypedMatcher> InnerMatchers)231 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
232                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
233                       ArrayRef<DynTypedMatcher> InnerMatchers) {
234   if (InnerMatchers.size() != 1)
235     return false;
236 
237   // The 'unless' matcher will always discard the result:
238   // If the inner matcher doesn't match, unless returns true,
239   // but the inner matcher cannot have bound anything.
240   // If the inner matcher matches, the result is false, and
241   // any possible binding will be discarded.
242   // We still need to hand in all the bound nodes up to this
243   // point so the inner matcher can depend on bound nodes,
244   // and we need to actively discard the bound nodes, otherwise
245   // the inner matcher will reset the bound nodes if it doesn't
246   // match, but this would be inversed by 'unless'.
247   BoundNodesTreeBuilder Discard(*Builder);
248   return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
249 }
250 
AllOfVariadicOperator(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,ArrayRef<DynTypedMatcher> InnerMatchers)251 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
252                            ASTMatchFinder *Finder,
253                            BoundNodesTreeBuilder *Builder,
254                            ArrayRef<DynTypedMatcher> InnerMatchers) {
255   // allOf leads to one matcher for each alternative in the first
256   // matcher combined with each alternative in the second matcher.
257   // Thus, we can reuse the same Builder.
258   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
259     if (!InnerMatcher.matchesNoKindCheck(DynNode, Finder, Builder))
260       return false;
261   }
262   return true;
263 }
264 
EachOfVariadicOperator(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,ArrayRef<DynTypedMatcher> InnerMatchers)265 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
266                             ASTMatchFinder *Finder,
267                             BoundNodesTreeBuilder *Builder,
268                             ArrayRef<DynTypedMatcher> InnerMatchers) {
269   BoundNodesTreeBuilder Result;
270   bool Matched = false;
271   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
272     BoundNodesTreeBuilder BuilderInner(*Builder);
273     if (InnerMatcher.matches(DynNode, Finder, &BuilderInner)) {
274       Matched = true;
275       Result.addMatch(BuilderInner);
276     }
277   }
278   *Builder = std::move(Result);
279   return Matched;
280 }
281 
AnyOfVariadicOperator(const ast_type_traits::DynTypedNode & DynNode,ASTMatchFinder * Finder,BoundNodesTreeBuilder * Builder,ArrayRef<DynTypedMatcher> InnerMatchers)282 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
283                            ASTMatchFinder *Finder,
284                            BoundNodesTreeBuilder *Builder,
285                            ArrayRef<DynTypedMatcher> InnerMatchers) {
286   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
287     BoundNodesTreeBuilder Result = *Builder;
288     if (InnerMatcher.matches(DynNode, Finder, &Result)) {
289       *Builder = std::move(Result);
290       return true;
291     }
292   }
293   return false;
294 }
295 
HasNameMatcher(StringRef NameRef)296 HasNameMatcher::HasNameMatcher(StringRef NameRef)
297     : UseUnqualifiedMatch(NameRef.find("::") == NameRef.npos), Name(NameRef) {
298   assert(!Name.empty());
299 }
300 
matchesNodeUnqualified(const NamedDecl & Node) const301 bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
302   assert(UseUnqualifiedMatch);
303   if (Node.getIdentifier()) {
304     // Simple name.
305     return Name == Node.getName();
306   }
307   if (Node.getDeclName()) {
308     // Name needs to be constructed.
309     llvm::SmallString<128> NodeName;
310     llvm::raw_svector_ostream OS(NodeName);
311     Node.printName(OS);
312     return Name == OS.str();
313   }
314   return false;
315 }
316 
matchesNodeFull(const NamedDecl & Node) const317 bool HasNameMatcher::matchesNodeFull(const NamedDecl &Node) const {
318   llvm::SmallString<128> NodeName = StringRef("::");
319   llvm::raw_svector_ostream OS(NodeName);
320   Node.printQualifiedName(OS);
321   const StringRef FullName = OS.str();
322   const StringRef Pattern = Name;
323 
324   if (Pattern.startswith("::"))
325     return FullName == Pattern;
326 
327   return FullName.endswith(Pattern) &&
328          FullName.drop_back(Pattern.size()).endswith("::");
329 }
330 
matchesNode(const NamedDecl & Node) const331 bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
332   // FIXME: There is still room for improvement, but it would require copying a
333   // lot of the logic from NamedDecl::printQualifiedName(). The benchmarks do
334   // not show like that extra complexity is needed right now.
335   if (UseUnqualifiedMatch) {
336     assert(matchesNodeUnqualified(Node) == matchesNodeFull(Node));
337     return matchesNodeUnqualified(Node);
338   }
339   return matchesNodeFull(Node);
340 }
341 
342 } // end namespace internal
343 } // end namespace ast_matchers
344 } // end namespace clang
345