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 
17 namespace clang {
18 namespace ast_matchers {
19 namespace internal {
20 
21 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
22   if (Bindings.empty())
23     Bindings.push_back(BoundNodesMap());
24   for (unsigned i = 0, e = Bindings.size(); i != e; ++i) {
25     ResultVisitor->visitMatch(BoundNodes(Bindings[i]));
26   }
27 }
28 
29 namespace {
30 
31 class VariadicMatcher : public DynMatcherInterface {
32  public:
33   VariadicMatcher(VariadicOperatorFunction Func,
34                   std::vector<DynTypedMatcher> InnerMatchers)
35       : Func(Func), InnerMatchers(std::move(InnerMatchers)) {}
36 
37   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
38                   ASTMatchFinder *Finder,
39                   BoundNodesTreeBuilder *Builder) const override {
40     return Func(DynNode, Finder, Builder, InnerMatchers);
41   }
42 
43  private:
44   VariadicOperatorFunction Func;
45   std::vector<DynTypedMatcher> InnerMatchers;
46 };
47 
48 class IdDynMatcher : public DynMatcherInterface {
49  public:
50   IdDynMatcher(StringRef ID,
51                const IntrusiveRefCntPtr<DynMatcherInterface> &InnerMatcher)
52       : ID(ID), InnerMatcher(InnerMatcher) {}
53 
54   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
55                   ASTMatchFinder *Finder,
56                   BoundNodesTreeBuilder *Builder) const override {
57     bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder);
58     if (Result) Builder->setBinding(ID, DynNode);
59     return Result;
60   }
61 
62  private:
63   const std::string ID;
64   const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
65 };
66 
67 /// \brief Return the most derived type between \p Kind1 and \p Kind2.
68 ///
69 /// Return the null type if they are not related.
70 ast_type_traits::ASTNodeKind getMostDerivedType(
71     const ast_type_traits::ASTNodeKind Kind1,
72     const ast_type_traits::ASTNodeKind Kind2) {
73   if (Kind1.isBaseOf(Kind2)) return Kind2;
74   if (Kind2.isBaseOf(Kind1)) return Kind1;
75   return ast_type_traits::ASTNodeKind();
76 }
77 
78 /// \brief Return the least derived type between \p Kind1 and \p Kind2.
79 ///
80 /// Return the null type if they are not related.
81 static ast_type_traits::ASTNodeKind getLeastDerivedType(
82     const ast_type_traits::ASTNodeKind Kind1,
83     const ast_type_traits::ASTNodeKind Kind2) {
84   if (Kind1.isBaseOf(Kind2)) return Kind1;
85   if (Kind2.isBaseOf(Kind1)) return Kind2;
86   return ast_type_traits::ASTNodeKind();
87 }
88 
89 }  // namespace
90 
91 DynTypedMatcher DynTypedMatcher::constructVariadic(
92     VariadicOperatorFunction Func, std::vector<DynTypedMatcher> InnerMatchers) {
93   assert(InnerMatchers.size() > 0 && "Array must not be empty.");
94   DynTypedMatcher Result = InnerMatchers[0];
95   // Use the least derived type as the restriction for the wrapper.
96   // This allows mismatches to be resolved on the inner matchers.
97   for (const DynTypedMatcher &M : InnerMatchers) {
98     assert(Result.SupportedKind.isSame(M.SupportedKind) &&
99            "SupportedKind must match!");
100     Result.RestrictKind =
101         getLeastDerivedType(Result.RestrictKind, M.RestrictKind);
102   }
103   Result.Implementation = new VariadicMatcher(Func, std::move(InnerMatchers));
104   return Result;
105 }
106 
107 DynTypedMatcher DynTypedMatcher::dynCastTo(
108     const ast_type_traits::ASTNodeKind Kind) const {
109   auto Copy = *this;
110   Copy.SupportedKind = Kind;
111   Copy.RestrictKind = getMostDerivedType(Kind, RestrictKind);
112   return Copy;
113 }
114 
115 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
116                               ASTMatchFinder *Finder,
117                               BoundNodesTreeBuilder *Builder) const {
118   if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
119       Implementation->dynMatches(DynNode, Finder, Builder)) {
120     return true;
121   }
122   // Delete all bindings when a matcher does not match.
123   // This prevents unexpected exposure of bound nodes in unmatches
124   // branches of the match tree.
125   Builder->removeBindings([](const BoundNodesMap &) { return true; });
126   return false;
127 }
128 
129 llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
130   if (!AllowBind) return llvm::None;
131   auto Result = *this;
132   Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
133   return Result;
134 }
135 
136 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
137   const auto From = getSupportedKind();
138   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
139   auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
140   /// Mimic the implicit conversions of Matcher<>.
141   /// - From Matcher<Type> to Matcher<QualType>
142   if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
143   /// - From Matcher<Base> to Matcher<Derived>
144   return From.isBaseOf(To);
145 }
146 
147 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
148   for (unsigned i = 0, e = Other.Bindings.size(); i != e; ++i) {
149     Bindings.push_back(Other.Bindings[i]);
150   }
151 }
152 
153 bool NotUnaryOperator(const ast_type_traits::DynTypedNode DynNode,
154                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
155                       ArrayRef<DynTypedMatcher> InnerMatchers) {
156   if (InnerMatchers.size() != 1)
157     return false;
158 
159   // The 'unless' matcher will always discard the result:
160   // If the inner matcher doesn't match, unless returns true,
161   // but the inner matcher cannot have bound anything.
162   // If the inner matcher matches, the result is false, and
163   // any possible binding will be discarded.
164   // We still need to hand in all the bound nodes up to this
165   // point so the inner matcher can depend on bound nodes,
166   // and we need to actively discard the bound nodes, otherwise
167   // the inner matcher will reset the bound nodes if it doesn't
168   // match, but this would be inversed by 'unless'.
169   BoundNodesTreeBuilder Discard(*Builder);
170   return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
171 }
172 
173 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
174                            ASTMatchFinder *Finder,
175                            BoundNodesTreeBuilder *Builder,
176                            ArrayRef<DynTypedMatcher> InnerMatchers) {
177   // allOf leads to one matcher for each alternative in the first
178   // matcher combined with each alternative in the second matcher.
179   // Thus, we can reuse the same Builder.
180   for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
181     if (!InnerMatchers[i].matches(DynNode, Finder, Builder))
182       return false;
183   }
184   return true;
185 }
186 
187 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
188                             ASTMatchFinder *Finder,
189                             BoundNodesTreeBuilder *Builder,
190                             ArrayRef<DynTypedMatcher> InnerMatchers) {
191   BoundNodesTreeBuilder Result;
192   bool Matched = false;
193   for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
194     BoundNodesTreeBuilder BuilderInner(*Builder);
195     if (InnerMatchers[i].matches(DynNode, Finder, &BuilderInner)) {
196       Matched = true;
197       Result.addMatch(BuilderInner);
198     }
199   }
200   *Builder = std::move(Result);
201   return Matched;
202 }
203 
204 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
205                            ASTMatchFinder *Finder,
206                            BoundNodesTreeBuilder *Builder,
207                            ArrayRef<DynTypedMatcher> InnerMatchers) {
208   for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
209     BoundNodesTreeBuilder Result = *Builder;
210     if (InnerMatchers[i].matches(DynNode, Finder, &Result)) {
211       *Builder = std::move(Result);
212       return true;
213     }
214   }
215   return false;
216 }
217 
218 } // end namespace internal
219 } // end namespace ast_matchers
220 } // end namespace clang
221