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 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: 61 VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers) 62 : InnerMatchers(std::move(InnerMatchers)) {} 63 64 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: 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 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 163 DynTypedMatcher DynTypedMatcher::trueMatcher( 164 ast_type_traits::ASTNodeKind NodeKind) { 165 return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance); 166 } 167 168 bool DynTypedMatcher::canMatchNodesOfKind( 169 ast_type_traits::ASTNodeKind Kind) const { 170 return RestrictKind.isBaseOf(Kind); 171 } 172 173 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 182 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 196 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 210 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 217 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 228 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) { 229 Bindings.append(Other.Bindings.begin(), Other.Bindings.end()); 230 } 231 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 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 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 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 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 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 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 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 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 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: 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. 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. 387 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 404 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 413 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 466 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 496 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