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 
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 class VariadicMatcher : public DynMatcherInterface {
54 public:
55   typedef bool (*VariadicOperatorFunction)(
56       const ast_type_traits::DynTypedNode DynNode, ASTMatchFinder *Finder,
57       BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
58 
59   VariadicMatcher(VariadicOperatorFunction Func,
60                   std::vector<DynTypedMatcher> InnerMatchers)
61       : Func(Func), InnerMatchers(std::move(InnerMatchers)) {}
62 
63   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   VariadicOperatorFunction Func;
71   std::vector<DynTypedMatcher> InnerMatchers;
72 };
73 
74 class IdDynMatcher : public DynMatcherInterface {
75  public:
76   IdDynMatcher(StringRef ID,
77                const IntrusiveRefCntPtr<DynMatcherInterface> &InnerMatcher)
78       : ID(ID), InnerMatcher(InnerMatcher) {}
79 
80   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:
100   TrueMatcherImpl() {
101     Retain(); // Reference count will never become zero.
102   }
103   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 
112 DynTypedMatcher DynTypedMatcher::constructVariadic(
113     DynTypedMatcher::VariadicOperator Op,
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                      [&InnerMatchers](const DynTypedMatcher &M) {
118            return InnerMatchers[0].SupportedKind.isSame(M.SupportedKind);
119          }) &&
120          "SupportedKind must match!");
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 SupportedKind = InnerMatchers[0].SupportedKind;
127   VariadicMatcher::VariadicOperatorFunction Func;
128   switch (Op) {
129   case VO_AllOf:
130     Func = AllOfVariadicOperator;
131     break;
132   case VO_AnyOf:
133     Func = AnyOfVariadicOperator;
134     break;
135   case VO_EachOf:
136     Func = EachOfVariadicOperator;
137     break;
138   case VO_UnaryNot:
139     Func = NotUnaryOperator;
140     break;
141   }
142 
143   return DynTypedMatcher(SupportedKind, SupportedKind,
144                          new VariadicMatcher(Func, std::move(InnerMatchers)));
145 }
146 
147 DynTypedMatcher DynTypedMatcher::trueMatcher(
148     ast_type_traits::ASTNodeKind NodeKind) {
149   return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
150 }
151 
152 DynTypedMatcher DynTypedMatcher::dynCastTo(
153     const ast_type_traits::ASTNodeKind Kind) const {
154   auto Copy = *this;
155   Copy.SupportedKind = Kind;
156   Copy.RestrictKind =
157       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
158   return Copy;
159 }
160 
161 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
162                               ASTMatchFinder *Finder,
163                               BoundNodesTreeBuilder *Builder) const {
164   if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
165       Implementation->dynMatches(DynNode, Finder, Builder)) {
166     return true;
167   }
168   // Delete all bindings when a matcher does not match.
169   // This prevents unexpected exposure of bound nodes in unmatches
170   // branches of the match tree.
171   Builder->removeBindings([](const BoundNodesMap &) { return true; });
172   return false;
173 }
174 
175 llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
176   if (!AllowBind) return llvm::None;
177   auto Result = *this;
178   Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
179   return Result;
180 }
181 
182 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
183   const auto From = getSupportedKind();
184   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
185   auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
186   /// Mimic the implicit conversions of Matcher<>.
187   /// - From Matcher<Type> to Matcher<QualType>
188   if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
189   /// - From Matcher<Base> to Matcher<Derived>
190   return From.isBaseOf(To);
191 }
192 
193 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
194   Bindings.append(Other.Bindings.begin(), Other.Bindings.end());
195 }
196 
197 bool NotUnaryOperator(const ast_type_traits::DynTypedNode DynNode,
198                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
199                       ArrayRef<DynTypedMatcher> InnerMatchers) {
200   if (InnerMatchers.size() != 1)
201     return false;
202 
203   // The 'unless' matcher will always discard the result:
204   // If the inner matcher doesn't match, unless returns true,
205   // but the inner matcher cannot have bound anything.
206   // If the inner matcher matches, the result is false, and
207   // any possible binding will be discarded.
208   // We still need to hand in all the bound nodes up to this
209   // point so the inner matcher can depend on bound nodes,
210   // and we need to actively discard the bound nodes, otherwise
211   // the inner matcher will reset the bound nodes if it doesn't
212   // match, but this would be inversed by 'unless'.
213   BoundNodesTreeBuilder Discard(*Builder);
214   return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
215 }
216 
217 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
218                            ASTMatchFinder *Finder,
219                            BoundNodesTreeBuilder *Builder,
220                            ArrayRef<DynTypedMatcher> InnerMatchers) {
221   // allOf leads to one matcher for each alternative in the first
222   // matcher combined with each alternative in the second matcher.
223   // Thus, we can reuse the same Builder.
224   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
225     if (!InnerMatcher.matches(DynNode, Finder, Builder))
226       return false;
227   }
228   return true;
229 }
230 
231 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
232                             ASTMatchFinder *Finder,
233                             BoundNodesTreeBuilder *Builder,
234                             ArrayRef<DynTypedMatcher> InnerMatchers) {
235   BoundNodesTreeBuilder Result;
236   bool Matched = false;
237   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
238     BoundNodesTreeBuilder BuilderInner(*Builder);
239     if (InnerMatcher.matches(DynNode, Finder, &BuilderInner)) {
240       Matched = true;
241       Result.addMatch(BuilderInner);
242     }
243   }
244   *Builder = std::move(Result);
245   return Matched;
246 }
247 
248 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
249                            ASTMatchFinder *Finder,
250                            BoundNodesTreeBuilder *Builder,
251                            ArrayRef<DynTypedMatcher> InnerMatchers) {
252   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
253     BoundNodesTreeBuilder Result = *Builder;
254     if (InnerMatcher.matches(DynNode, Finder, &Result)) {
255       *Builder = std::move(Result);
256       return true;
257     }
258   }
259   return false;
260 }
261 
262 HasNameMatcher::HasNameMatcher(StringRef NameRef)
263     : UseUnqualifiedMatch(NameRef.find("::") == NameRef.npos), Name(NameRef) {
264   assert(!Name.empty());
265 }
266 
267 bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
268   assert(UseUnqualifiedMatch);
269   if (Node.getIdentifier()) {
270     // Simple name.
271     return Name == Node.getName();
272   }
273   if (Node.getDeclName()) {
274     // Name needs to be constructed.
275     llvm::SmallString<128> NodeName;
276     llvm::raw_svector_ostream OS(NodeName);
277     Node.printName(OS);
278     return Name == OS.str();
279   }
280   return false;
281 }
282 
283 bool HasNameMatcher::matchesNodeFull(const NamedDecl &Node) const {
284   llvm::SmallString<128> NodeName = StringRef("::");
285   llvm::raw_svector_ostream OS(NodeName);
286   Node.printQualifiedName(OS);
287   const StringRef FullName = OS.str();
288   const StringRef Pattern = Name;
289 
290   if (Pattern.startswith("::"))
291     return FullName == Pattern;
292 
293   return FullName.endswith(Pattern) &&
294          FullName.drop_back(Pattern.size()).endswith("::");
295 }
296 
297 bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
298   // FIXME: There is still room for improvement, but it would require copying a
299   // lot of the logic from NamedDecl::printQualifiedName(). The benchmarks do
300   // not show like that extra complexity is needed right now.
301   if (UseUnqualifiedMatch) {
302     assert(matchesNodeUnqualified(Node) == matchesNodeFull(Node));
303     return matchesNodeUnqualified(Node);
304   }
305   return matchesNodeFull(Node);
306 }
307 
308 } // end namespace internal
309 } // end namespace ast_matchers
310 } // end namespace clang
311