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