1 //===--- ASTMatchersInternal.h - Structural query framework -----*- C++ -*-===// 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 // Matchers are methods that return a Matcher<T> which provides a method 13 // Matches(...) which is a predicate on an AST node. The Matches method's 14 // parameters define the context of the match, which allows matchers to recurse 15 // or store the current node as bound to a specific string, so that it can be 16 // retrieved later. 17 // 18 // In general, matchers have two parts: 19 // 1. A function Matcher<T> MatcherName(<arguments>) which returns a Matcher<T> 20 // based on the arguments and optionally on template type deduction based 21 // on the arguments. Matcher<T>s form an implicit reverse hierarchy 22 // to clang's AST class hierarchy, meaning that you can use a Matcher<Base> 23 // everywhere a Matcher<Derived> is required. 24 // 2. An implementation of a class derived from MatcherInterface<T>. 25 // 26 // The matcher functions are defined in ASTMatchers.h. To make it possible 27 // to implement both the matcher function and the implementation of the matcher 28 // interface in one place, ASTMatcherMacros.h defines macros that allow 29 // implementing a matcher in a single place. 30 // 31 // This file contains the base classes needed to construct the actual matchers. 32 // 33 //===----------------------------------------------------------------------===// 34 35 #ifndef LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H 36 #define LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H 37 38 #include "clang/AST/ASTTypeTraits.h" 39 #include "clang/AST/Decl.h" 40 #include "clang/AST/DeclCXX.h" 41 #include "clang/AST/DeclObjC.h" 42 #include "clang/AST/DeclTemplate.h" 43 #include "clang/AST/ExprCXX.h" 44 #include "clang/AST/ExprObjC.h" 45 #include "clang/AST/Stmt.h" 46 #include "clang/AST/StmtCXX.h" 47 #include "clang/AST/StmtObjC.h" 48 #include "clang/AST/Type.h" 49 #include "llvm/ADT/ArrayRef.h" 50 #include "llvm/ADT/Optional.h" 51 #include "llvm/ADT/SmallVector.h" 52 #include "llvm/Support/ManagedStatic.h" 53 #include <map> 54 #include <string> 55 #include <vector> 56 57 namespace clang { 58 namespace ast_matchers { 59 60 class BoundNodes; 61 62 namespace internal { 63 64 /// \brief Variadic function object. 65 /// 66 /// Most of the functions below that use VariadicFunction could be implemented 67 /// using plain C++11 variadic functions, but the function object allows us to 68 /// capture it on the dynamic matcher registry. 69 template <typename ResultT, typename ArgT, 70 ResultT (*Func)(ArrayRef<const ArgT *>)> 71 struct VariadicFunction { 72 ResultT operator()() const { return Func(None); } 73 74 template <typename... ArgsT> 75 ResultT operator()(const ArgT &Arg1, const ArgsT &... Args) const { 76 return Execute(Arg1, static_cast<const ArgT &>(Args)...); 77 } 78 79 // We also allow calls with an already created array, in case the caller 80 // already had it. 81 ResultT operator()(ArrayRef<ArgT> Args) const { 82 SmallVector<const ArgT*, 8> InnerArgs; 83 for (const ArgT &Arg : Args) 84 InnerArgs.push_back(&Arg); 85 return Func(InnerArgs); 86 } 87 88 private: 89 // Trampoline function to allow for implicit conversions to take place 90 // before we make the array. 91 template <typename... ArgsT> ResultT Execute(const ArgsT &... Args) const { 92 const ArgT *const ArgsArray[] = {&Args...}; 93 return Func(ArrayRef<const ArgT *>(ArgsArray, sizeof...(ArgsT))); 94 } 95 }; 96 97 /// \brief Unifies obtaining the underlying type of a regular node through 98 /// `getType` and a TypedefNameDecl node through `getUnderlyingType`. 99 inline QualType getUnderlyingType(const Expr &Node) { return Node.getType(); } 100 101 inline QualType getUnderlyingType(const ValueDecl &Node) { 102 return Node.getType(); 103 } 104 105 inline QualType getUnderlyingType(const TypedefNameDecl &Node) { 106 return Node.getUnderlyingType(); 107 } 108 109 /// \brief Unifies obtaining the FunctionProtoType pointer from both 110 /// FunctionProtoType and FunctionDecl nodes.. 111 inline const FunctionProtoType * 112 getFunctionProtoType(const FunctionProtoType &Node) { 113 return &Node; 114 } 115 116 inline const FunctionProtoType *getFunctionProtoType(const FunctionDecl &Node) { 117 return Node.getType()->getAs<FunctionProtoType>(); 118 } 119 120 /// \brief Internal version of BoundNodes. Holds all the bound nodes. 121 class BoundNodesMap { 122 public: 123 /// \brief Adds \c Node to the map with key \c ID. 124 /// 125 /// The node's base type should be in NodeBaseType or it will be unaccessible. 126 void addNode(StringRef ID, const ast_type_traits::DynTypedNode& DynNode) { 127 NodeMap[ID] = DynNode; 128 } 129 130 /// \brief Returns the AST node bound to \c ID. 131 /// 132 /// Returns NULL if there was no node bound to \c ID or if there is a node but 133 /// it cannot be converted to the specified type. 134 template <typename T> 135 const T *getNodeAs(StringRef ID) const { 136 IDToNodeMap::const_iterator It = NodeMap.find(ID); 137 if (It == NodeMap.end()) { 138 return nullptr; 139 } 140 return It->second.get<T>(); 141 } 142 143 ast_type_traits::DynTypedNode getNode(StringRef ID) const { 144 IDToNodeMap::const_iterator It = NodeMap.find(ID); 145 if (It == NodeMap.end()) { 146 return ast_type_traits::DynTypedNode(); 147 } 148 return It->second; 149 } 150 151 /// \brief Imposes an order on BoundNodesMaps. 152 bool operator<(const BoundNodesMap &Other) const { 153 return NodeMap < Other.NodeMap; 154 } 155 156 /// \brief A map from IDs to the bound nodes. 157 /// 158 /// Note that we're using std::map here, as for memoization: 159 /// - we need a comparison operator 160 /// - we need an assignment operator 161 typedef std::map<std::string, ast_type_traits::DynTypedNode> IDToNodeMap; 162 163 const IDToNodeMap &getMap() const { 164 return NodeMap; 165 } 166 167 /// \brief Returns \c true if this \c BoundNodesMap can be compared, i.e. all 168 /// stored nodes have memoization data. 169 bool isComparable() const { 170 for (const auto &IDAndNode : NodeMap) { 171 if (!IDAndNode.second.getMemoizationData()) 172 return false; 173 } 174 return true; 175 } 176 177 private: 178 IDToNodeMap NodeMap; 179 }; 180 181 /// \brief Creates BoundNodesTree objects. 182 /// 183 /// The tree builder is used during the matching process to insert the bound 184 /// nodes from the Id matcher. 185 class BoundNodesTreeBuilder { 186 public: 187 /// \brief A visitor interface to visit all BoundNodes results for a 188 /// BoundNodesTree. 189 class Visitor { 190 public: 191 virtual ~Visitor() {} 192 193 /// \brief Called multiple times during a single call to VisitMatches(...). 194 /// 195 /// 'BoundNodesView' contains the bound nodes for a single match. 196 virtual void visitMatch(const BoundNodes& BoundNodesView) = 0; 197 }; 198 199 /// \brief Add a binding from an id to a node. 200 void setBinding(StringRef Id, const ast_type_traits::DynTypedNode &DynNode) { 201 if (Bindings.empty()) 202 Bindings.emplace_back(); 203 for (BoundNodesMap &Binding : Bindings) 204 Binding.addNode(Id, DynNode); 205 } 206 207 /// \brief Adds a branch in the tree. 208 void addMatch(const BoundNodesTreeBuilder &Bindings); 209 210 /// \brief Visits all matches that this BoundNodesTree represents. 211 /// 212 /// The ownership of 'ResultVisitor' remains at the caller. 213 void visitMatches(Visitor* ResultVisitor); 214 215 template <typename ExcludePredicate> 216 bool removeBindings(const ExcludePredicate &Predicate) { 217 Bindings.erase(std::remove_if(Bindings.begin(), Bindings.end(), Predicate), 218 Bindings.end()); 219 return !Bindings.empty(); 220 } 221 222 /// \brief Imposes an order on BoundNodesTreeBuilders. 223 bool operator<(const BoundNodesTreeBuilder &Other) const { 224 return Bindings < Other.Bindings; 225 } 226 227 /// \brief Returns \c true if this \c BoundNodesTreeBuilder can be compared, 228 /// i.e. all stored node maps have memoization data. 229 bool isComparable() const { 230 for (const BoundNodesMap &NodesMap : Bindings) { 231 if (!NodesMap.isComparable()) 232 return false; 233 } 234 return true; 235 } 236 237 private: 238 SmallVector<BoundNodesMap, 16> Bindings; 239 }; 240 241 class ASTMatchFinder; 242 243 /// \brief Generic interface for all matchers. 244 /// 245 /// Used by the implementation of Matcher<T> and DynTypedMatcher. 246 /// In general, implement MatcherInterface<T> or SingleNodeMatcherInterface<T> 247 /// instead. 248 class DynMatcherInterface 249 : public llvm::ThreadSafeRefCountedBase<DynMatcherInterface> { 250 public: 251 virtual ~DynMatcherInterface() {} 252 253 /// \brief Returns true if \p DynNode can be matched. 254 /// 255 /// May bind \p DynNode to an ID via \p Builder, or recurse into 256 /// the AST via \p Finder. 257 virtual bool dynMatches(const ast_type_traits::DynTypedNode &DynNode, 258 ASTMatchFinder *Finder, 259 BoundNodesTreeBuilder *Builder) const = 0; 260 }; 261 262 /// \brief Generic interface for matchers on an AST node of type T. 263 /// 264 /// Implement this if your matcher may need to inspect the children or 265 /// descendants of the node or bind matched nodes to names. If you are 266 /// writing a simple matcher that only inspects properties of the 267 /// current node and doesn't care about its children or descendants, 268 /// implement SingleNodeMatcherInterface instead. 269 template <typename T> 270 class MatcherInterface : public DynMatcherInterface { 271 public: 272 /// \brief Returns true if 'Node' can be matched. 273 /// 274 /// May bind 'Node' to an ID via 'Builder', or recurse into 275 /// the AST via 'Finder'. 276 virtual bool matches(const T &Node, 277 ASTMatchFinder *Finder, 278 BoundNodesTreeBuilder *Builder) const = 0; 279 280 bool dynMatches(const ast_type_traits::DynTypedNode &DynNode, 281 ASTMatchFinder *Finder, 282 BoundNodesTreeBuilder *Builder) const override { 283 return matches(DynNode.getUnchecked<T>(), Finder, Builder); 284 } 285 }; 286 287 /// \brief Interface for matchers that only evaluate properties on a single 288 /// node. 289 template <typename T> 290 class SingleNodeMatcherInterface : public MatcherInterface<T> { 291 public: 292 /// \brief Returns true if the matcher matches the provided node. 293 /// 294 /// A subclass must implement this instead of Matches(). 295 virtual bool matchesNode(const T &Node) const = 0; 296 297 private: 298 /// Implements MatcherInterface::Matches. 299 bool matches(const T &Node, 300 ASTMatchFinder * /* Finder */, 301 BoundNodesTreeBuilder * /* Builder */) const override { 302 return matchesNode(Node); 303 } 304 }; 305 306 template <typename> class Matcher; 307 308 /// \brief Matcher that works on a \c DynTypedNode. 309 /// 310 /// It is constructed from a \c Matcher<T> object and redirects most calls to 311 /// underlying matcher. 312 /// It checks whether the \c DynTypedNode is convertible into the type of the 313 /// underlying matcher and then do the actual match on the actual node, or 314 /// return false if it is not convertible. 315 class DynTypedMatcher { 316 public: 317 /// \brief Takes ownership of the provided implementation pointer. 318 template <typename T> 319 DynTypedMatcher(MatcherInterface<T> *Implementation) 320 : AllowBind(false), 321 SupportedKind(ast_type_traits::ASTNodeKind::getFromNodeKind<T>()), 322 RestrictKind(SupportedKind), Implementation(Implementation) {} 323 324 /// \brief Construct from a variadic function. 325 enum VariadicOperator { 326 /// \brief Matches nodes for which all provided matchers match. 327 VO_AllOf, 328 /// \brief Matches nodes for which at least one of the provided matchers 329 /// matches. 330 VO_AnyOf, 331 /// \brief Matches nodes for which at least one of the provided matchers 332 /// matches, but doesn't stop at the first match. 333 VO_EachOf, 334 /// \brief Matches nodes that do not match the provided matcher. 335 /// 336 /// Uses the variadic matcher interface, but fails if 337 /// InnerMatchers.size() != 1. 338 VO_UnaryNot 339 }; 340 static DynTypedMatcher 341 constructVariadic(VariadicOperator Op, 342 ast_type_traits::ASTNodeKind SupportedKind, 343 std::vector<DynTypedMatcher> InnerMatchers); 344 345 /// \brief Get a "true" matcher for \p NodeKind. 346 /// 347 /// It only checks that the node is of the right kind. 348 static DynTypedMatcher trueMatcher(ast_type_traits::ASTNodeKind NodeKind); 349 350 void setAllowBind(bool AB) { AllowBind = AB; } 351 352 /// \brief Check whether this matcher could ever match a node of kind \p Kind. 353 /// \return \c false if this matcher will never match such a node. Otherwise, 354 /// return \c true. 355 bool canMatchNodesOfKind(ast_type_traits::ASTNodeKind Kind) const; 356 357 /// \brief Return a matcher that points to the same implementation, but 358 /// restricts the node types for \p Kind. 359 DynTypedMatcher dynCastTo(const ast_type_traits::ASTNodeKind Kind) const; 360 361 /// \brief Returns true if the matcher matches the given \c DynNode. 362 bool matches(const ast_type_traits::DynTypedNode &DynNode, 363 ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const; 364 365 /// \brief Same as matches(), but skips the kind check. 366 /// 367 /// It is faster, but the caller must ensure the node is valid for the 368 /// kind of this matcher. 369 bool matchesNoKindCheck(const ast_type_traits::DynTypedNode &DynNode, 370 ASTMatchFinder *Finder, 371 BoundNodesTreeBuilder *Builder) const; 372 373 /// \brief Bind the specified \p ID to the matcher. 374 /// \return A new matcher with the \p ID bound to it if this matcher supports 375 /// binding. Otherwise, returns an empty \c Optional<>. 376 llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const; 377 378 /// \brief Returns a unique \p ID for the matcher. 379 /// 380 /// Casting a Matcher<T> to Matcher<U> creates a matcher that has the 381 /// same \c Implementation pointer, but different \c RestrictKind. We need to 382 /// include both in the ID to make it unique. 383 /// 384 /// \c MatcherIDType supports operator< and provides strict weak ordering. 385 typedef std::pair<ast_type_traits::ASTNodeKind, uint64_t> MatcherIDType; 386 MatcherIDType getID() const { 387 /// FIXME: Document the requirements this imposes on matcher 388 /// implementations (no new() implementation_ during a Matches()). 389 return std::make_pair(RestrictKind, 390 reinterpret_cast<uint64_t>(Implementation.get())); 391 } 392 393 /// \brief Returns the type this matcher works on. 394 /// 395 /// \c matches() will always return false unless the node passed is of this 396 /// or a derived type. 397 ast_type_traits::ASTNodeKind getSupportedKind() const { 398 return SupportedKind; 399 } 400 401 /// \brief Returns \c true if the passed \c DynTypedMatcher can be converted 402 /// to a \c Matcher<T>. 403 /// 404 /// This method verifies that the underlying matcher in \c Other can process 405 /// nodes of types T. 406 template <typename T> bool canConvertTo() const { 407 return canConvertTo(ast_type_traits::ASTNodeKind::getFromNodeKind<T>()); 408 } 409 bool canConvertTo(ast_type_traits::ASTNodeKind To) const; 410 411 /// \brief Construct a \c Matcher<T> interface around the dynamic matcher. 412 /// 413 /// This method asserts that \c canConvertTo() is \c true. Callers 414 /// should call \c canConvertTo() first to make sure that \c this is 415 /// compatible with T. 416 template <typename T> Matcher<T> convertTo() const { 417 assert(canConvertTo<T>()); 418 return unconditionalConvertTo<T>(); 419 } 420 421 /// \brief Same as \c convertTo(), but does not check that the underlying 422 /// matcher can handle a value of T. 423 /// 424 /// If it is not compatible, then this matcher will never match anything. 425 template <typename T> Matcher<T> unconditionalConvertTo() const; 426 427 private: 428 DynTypedMatcher(ast_type_traits::ASTNodeKind SupportedKind, 429 ast_type_traits::ASTNodeKind RestrictKind, 430 IntrusiveRefCntPtr<DynMatcherInterface> Implementation) 431 : AllowBind(false), 432 SupportedKind(SupportedKind), 433 RestrictKind(RestrictKind), 434 Implementation(std::move(Implementation)) {} 435 436 bool AllowBind; 437 ast_type_traits::ASTNodeKind SupportedKind; 438 /// \brief A potentially stricter node kind. 439 /// 440 /// It allows to perform implicit and dynamic cast of matchers without 441 /// needing to change \c Implementation. 442 ast_type_traits::ASTNodeKind RestrictKind; 443 IntrusiveRefCntPtr<DynMatcherInterface> Implementation; 444 }; 445 446 /// \brief Wrapper base class for a wrapping matcher. 447 /// 448 /// This is just a container for a DynTypedMatcher that can be used as a base 449 /// class for another matcher. 450 template <typename T> 451 class WrapperMatcherInterface : public MatcherInterface<T> { 452 protected: 453 explicit WrapperMatcherInterface(DynTypedMatcher &&InnerMatcher) 454 : InnerMatcher(std::move(InnerMatcher)) {} 455 456 const DynTypedMatcher InnerMatcher; 457 }; 458 459 /// \brief Wrapper of a MatcherInterface<T> *that allows copying. 460 /// 461 /// A Matcher<Base> can be used anywhere a Matcher<Derived> is 462 /// required. This establishes an is-a relationship which is reverse 463 /// to the AST hierarchy. In other words, Matcher<T> is contravariant 464 /// with respect to T. The relationship is built via a type conversion 465 /// operator rather than a type hierarchy to be able to templatize the 466 /// type hierarchy instead of spelling it out. 467 template <typename T> 468 class Matcher { 469 public: 470 /// \brief Takes ownership of the provided implementation pointer. 471 explicit Matcher(MatcherInterface<T> *Implementation) 472 : Implementation(Implementation) {} 473 474 /// \brief Implicitly converts \c Other to a Matcher<T>. 475 /// 476 /// Requires \c T to be derived from \c From. 477 template <typename From> 478 Matcher(const Matcher<From> &Other, 479 typename std::enable_if<std::is_base_of<From, T>::value && 480 !std::is_same<From, T>::value>::type * = nullptr) 481 : Implementation(restrictMatcher(Other.Implementation)) { 482 assert(Implementation.getSupportedKind().isSame( 483 ast_type_traits::ASTNodeKind::getFromNodeKind<T>())); 484 } 485 486 /// \brief Implicitly converts \c Matcher<Type> to \c Matcher<QualType>. 487 /// 488 /// The resulting matcher is not strict, i.e. ignores qualifiers. 489 template <typename TypeT> 490 Matcher(const Matcher<TypeT> &Other, 491 typename std::enable_if< 492 std::is_same<T, QualType>::value && 493 std::is_same<TypeT, Type>::value>::type* = nullptr) 494 : Implementation(new TypeToQualType<TypeT>(Other)) {} 495 496 /// \brief Convert \c this into a \c Matcher<T> by applying dyn_cast<> to the 497 /// argument. 498 /// \c To must be a base class of \c T. 499 template <typename To> 500 Matcher<To> dynCastTo() const { 501 static_assert(std::is_base_of<To, T>::value, "Invalid dynCast call."); 502 return Matcher<To>(Implementation); 503 } 504 505 /// \brief Forwards the call to the underlying MatcherInterface<T> pointer. 506 bool matches(const T &Node, 507 ASTMatchFinder *Finder, 508 BoundNodesTreeBuilder *Builder) const { 509 return Implementation.matches(ast_type_traits::DynTypedNode::create(Node), 510 Finder, Builder); 511 } 512 513 /// \brief Returns an ID that uniquely identifies the matcher. 514 DynTypedMatcher::MatcherIDType getID() const { 515 return Implementation.getID(); 516 } 517 518 /// \brief Extract the dynamic matcher. 519 /// 520 /// The returned matcher keeps the same restrictions as \c this and remembers 521 /// that it is meant to support nodes of type \c T. 522 operator DynTypedMatcher() const { return Implementation; } 523 524 /// \brief Allows the conversion of a \c Matcher<Type> to a \c 525 /// Matcher<QualType>. 526 /// 527 /// Depending on the constructor argument, the matcher is either strict, i.e. 528 /// does only matches in the absence of qualifiers, or not, i.e. simply 529 /// ignores any qualifiers. 530 template <typename TypeT> 531 class TypeToQualType : public WrapperMatcherInterface<QualType> { 532 public: 533 TypeToQualType(const Matcher<TypeT> &InnerMatcher) 534 : TypeToQualType::WrapperMatcherInterface(InnerMatcher) {} 535 536 bool matches(const QualType &Node, ASTMatchFinder *Finder, 537 BoundNodesTreeBuilder *Builder) const override { 538 if (Node.isNull()) 539 return false; 540 return this->InnerMatcher.matches( 541 ast_type_traits::DynTypedNode::create(*Node), Finder, Builder); 542 } 543 }; 544 545 private: 546 // For Matcher<T> <=> Matcher<U> conversions. 547 template <typename U> friend class Matcher; 548 // For DynTypedMatcher::unconditionalConvertTo<T>. 549 friend class DynTypedMatcher; 550 551 static DynTypedMatcher restrictMatcher(const DynTypedMatcher &Other) { 552 return Other.dynCastTo(ast_type_traits::ASTNodeKind::getFromNodeKind<T>()); 553 } 554 555 explicit Matcher(const DynTypedMatcher &Implementation) 556 : Implementation(restrictMatcher(Implementation)) { 557 assert(this->Implementation.getSupportedKind() 558 .isSame(ast_type_traits::ASTNodeKind::getFromNodeKind<T>())); 559 } 560 561 DynTypedMatcher Implementation; 562 }; // class Matcher 563 564 /// \brief A convenient helper for creating a Matcher<T> without specifying 565 /// the template type argument. 566 template <typename T> 567 inline Matcher<T> makeMatcher(MatcherInterface<T> *Implementation) { 568 return Matcher<T>(Implementation); 569 } 570 571 /// \brief Specialization of the conversion functions for QualType. 572 /// 573 /// This specialization provides the Matcher<Type>->Matcher<QualType> 574 /// conversion that the static API does. 575 template <> 576 inline Matcher<QualType> DynTypedMatcher::convertTo<QualType>() const { 577 assert(canConvertTo<QualType>()); 578 const ast_type_traits::ASTNodeKind SourceKind = getSupportedKind(); 579 if (SourceKind.isSame( 580 ast_type_traits::ASTNodeKind::getFromNodeKind<Type>())) { 581 // We support implicit conversion from Matcher<Type> to Matcher<QualType> 582 return unconditionalConvertTo<Type>(); 583 } 584 return unconditionalConvertTo<QualType>(); 585 } 586 587 /// \brief Finds the first node in a range that matches the given matcher. 588 template <typename MatcherT, typename IteratorT> 589 bool matchesFirstInRange(const MatcherT &Matcher, IteratorT Start, 590 IteratorT End, ASTMatchFinder *Finder, 591 BoundNodesTreeBuilder *Builder) { 592 for (IteratorT I = Start; I != End; ++I) { 593 BoundNodesTreeBuilder Result(*Builder); 594 if (Matcher.matches(*I, Finder, &Result)) { 595 *Builder = std::move(Result); 596 return true; 597 } 598 } 599 return false; 600 } 601 602 /// \brief Finds the first node in a pointer range that matches the given 603 /// matcher. 604 template <typename MatcherT, typename IteratorT> 605 bool matchesFirstInPointerRange(const MatcherT &Matcher, IteratorT Start, 606 IteratorT End, ASTMatchFinder *Finder, 607 BoundNodesTreeBuilder *Builder) { 608 for (IteratorT I = Start; I != End; ++I) { 609 BoundNodesTreeBuilder Result(*Builder); 610 if (Matcher.matches(**I, Finder, &Result)) { 611 *Builder = std::move(Result); 612 return true; 613 } 614 } 615 return false; 616 } 617 618 // Metafunction to determine if type T has a member called getDecl. 619 template <typename Ty> 620 class has_getDecl { 621 typedef char yes[1]; 622 typedef char no[2]; 623 624 template <typename Inner> 625 static yes& test(Inner *I, decltype(I->getDecl()) * = nullptr); 626 627 template <typename> 628 static no& test(...); 629 630 public: 631 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 632 }; 633 634 /// \brief Matches overloaded operators with a specific name. 635 /// 636 /// The type argument ArgT is not used by this matcher but is used by 637 /// PolymorphicMatcherWithParam1 and should be StringRef. 638 template <typename T, typename ArgT> 639 class HasOverloadedOperatorNameMatcher : public SingleNodeMatcherInterface<T> { 640 static_assert(std::is_same<T, CXXOperatorCallExpr>::value || 641 std::is_base_of<FunctionDecl, T>::value, 642 "unsupported class for matcher"); 643 static_assert(std::is_same<ArgT, StringRef>::value, 644 "argument type must be StringRef"); 645 646 public: 647 explicit HasOverloadedOperatorNameMatcher(const StringRef Name) 648 : SingleNodeMatcherInterface<T>(), Name(Name) {} 649 650 bool matchesNode(const T &Node) const override { 651 return matchesSpecialized(Node); 652 } 653 654 private: 655 656 /// \brief CXXOperatorCallExpr exist only for calls to overloaded operators 657 /// so this function returns true if the call is to an operator of the given 658 /// name. 659 bool matchesSpecialized(const CXXOperatorCallExpr &Node) const { 660 return getOperatorSpelling(Node.getOperator()) == Name; 661 } 662 663 /// \brief Returns true only if CXXMethodDecl represents an overloaded 664 /// operator and has the given operator name. 665 bool matchesSpecialized(const FunctionDecl &Node) const { 666 return Node.isOverloadedOperator() && 667 getOperatorSpelling(Node.getOverloadedOperator()) == Name; 668 } 669 670 std::string Name; 671 }; 672 673 /// \brief Matches named declarations with a specific name. 674 /// 675 /// See \c hasName() and \c hasAnyName() in ASTMatchers.h for details. 676 class HasNameMatcher : public SingleNodeMatcherInterface<NamedDecl> { 677 public: 678 explicit HasNameMatcher(std::vector<std::string> Names); 679 680 bool matchesNode(const NamedDecl &Node) const override; 681 682 private: 683 /// \brief Unqualified match routine. 684 /// 685 /// It is much faster than the full match, but it only works for unqualified 686 /// matches. 687 bool matchesNodeUnqualified(const NamedDecl &Node) const; 688 689 /// \brief Full match routine 690 /// 691 /// Fast implementation for the simple case of a named declaration at 692 /// namespace or RecordDecl scope. 693 /// It is slower than matchesNodeUnqualified, but faster than 694 /// matchesNodeFullSlow. 695 bool matchesNodeFullFast(const NamedDecl &Node) const; 696 697 /// \brief Full match routine 698 /// 699 /// It generates the fully qualified name of the declaration (which is 700 /// expensive) before trying to match. 701 /// It is slower but simple and works on all cases. 702 bool matchesNodeFullSlow(const NamedDecl &Node) const; 703 704 const bool UseUnqualifiedMatch; 705 const std::vector<std::string> Names; 706 }; 707 708 /// \brief Trampoline function to use VariadicFunction<> to construct a 709 /// HasNameMatcher. 710 Matcher<NamedDecl> hasAnyNameFunc(ArrayRef<const StringRef *> NameRefs); 711 712 /// \brief Matches declarations for QualType and CallExpr. 713 /// 714 /// Type argument DeclMatcherT is required by PolymorphicMatcherWithParam1 but 715 /// not actually used. 716 template <typename T, typename DeclMatcherT> 717 class HasDeclarationMatcher : public WrapperMatcherInterface<T> { 718 static_assert(std::is_same<DeclMatcherT, Matcher<Decl>>::value, 719 "instantiated with wrong types"); 720 721 public: 722 explicit HasDeclarationMatcher(const Matcher<Decl> &InnerMatcher) 723 : HasDeclarationMatcher::WrapperMatcherInterface(InnerMatcher) {} 724 725 bool matches(const T &Node, ASTMatchFinder *Finder, 726 BoundNodesTreeBuilder *Builder) const override { 727 return matchesSpecialized(Node, Finder, Builder); 728 } 729 730 private: 731 /// \brief If getDecl exists as a member of U, returns whether the inner 732 /// matcher matches Node.getDecl(). 733 template <typename U> 734 bool matchesSpecialized( 735 const U &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder, 736 typename std::enable_if<has_getDecl<U>::value, int>::type = 0) const { 737 return matchesDecl(Node.getDecl(), Finder, Builder); 738 } 739 740 /// \brief Extracts the TagDecl of a QualType and returns whether the inner 741 /// matcher matches on it. 742 bool matchesSpecialized(const QualType &Node, ASTMatchFinder *Finder, 743 BoundNodesTreeBuilder *Builder) const { 744 if (Node.isNull()) 745 return false; 746 747 if (auto *TD = Node->getAsTagDecl()) 748 return matchesDecl(TD, Finder, Builder); 749 else if (auto *TT = Node->getAs<TypedefType>()) 750 return matchesDecl(TT->getDecl(), Finder, Builder); 751 // Do not use getAs<TemplateTypeParmType> instead of the direct dyn_cast. 752 // Calling getAs will return the canonical type, but that type does not 753 // store a TemplateTypeParmDecl. We *need* the uncanonical type, if it is 754 // available, and using dyn_cast ensures that. 755 else if (auto *TTP = dyn_cast<TemplateTypeParmType>(Node.getTypePtr())) 756 return matchesDecl(TTP->getDecl(), Finder, Builder); 757 else if (auto *OCIT = Node->getAs<ObjCInterfaceType>()) 758 return matchesDecl(OCIT->getDecl(), Finder, Builder); 759 else if (auto *UUT = Node->getAs<UnresolvedUsingType>()) 760 return matchesDecl(UUT->getDecl(), Finder, Builder); 761 else if (auto *ICNT = Node->getAs<InjectedClassNameType>()) 762 return matchesDecl(ICNT->getDecl(), Finder, Builder); 763 return false; 764 } 765 766 /// \brief Gets the TemplateDecl from a TemplateSpecializationType 767 /// and returns whether the inner matches on it. 768 bool matchesSpecialized(const TemplateSpecializationType &Node, 769 ASTMatchFinder *Finder, 770 BoundNodesTreeBuilder *Builder) const { 771 return matchesDecl(Node.getTemplateName().getAsTemplateDecl(), 772 Finder, Builder); 773 } 774 775 /// \brief Extracts the Decl of the callee of a CallExpr and returns whether 776 /// the inner matcher matches on it. 777 bool matchesSpecialized(const CallExpr &Node, ASTMatchFinder *Finder, 778 BoundNodesTreeBuilder *Builder) const { 779 return matchesDecl(Node.getCalleeDecl(), Finder, Builder); 780 } 781 782 /// \brief Extracts the Decl of the constructor call and returns whether the 783 /// inner matcher matches on it. 784 bool matchesSpecialized(const CXXConstructExpr &Node, 785 ASTMatchFinder *Finder, 786 BoundNodesTreeBuilder *Builder) const { 787 return matchesDecl(Node.getConstructor(), Finder, Builder); 788 } 789 790 /// \brief Extracts the \c ValueDecl a \c MemberExpr refers to and returns 791 /// whether the inner matcher matches on it. 792 bool matchesSpecialized(const MemberExpr &Node, 793 ASTMatchFinder *Finder, 794 BoundNodesTreeBuilder *Builder) const { 795 return matchesDecl(Node.getMemberDecl(), Finder, Builder); 796 } 797 798 /// \brief Extracts the \c LabelDecl a \c AddrLabelExpr refers to and returns 799 /// whether the inner matcher matches on it. 800 bool matchesSpecialized(const AddrLabelExpr &Node, 801 ASTMatchFinder *Finder, 802 BoundNodesTreeBuilder *Builder) const { 803 return matchesDecl(Node.getLabel(), Finder, Builder); 804 } 805 806 /// \brief Returns whether the inner matcher \c Node. Returns false if \c Node 807 /// is \c NULL. 808 bool matchesDecl(const Decl *Node, ASTMatchFinder *Finder, 809 BoundNodesTreeBuilder *Builder) const { 810 return Node != nullptr && 811 this->InnerMatcher.matches( 812 ast_type_traits::DynTypedNode::create(*Node), Finder, Builder); 813 } 814 }; 815 816 /// \brief IsBaseType<T>::value is true if T is a "base" type in the AST 817 /// node class hierarchies. 818 template <typename T> 819 struct IsBaseType { 820 static const bool value = 821 std::is_same<T, Decl>::value || 822 std::is_same<T, Stmt>::value || 823 std::is_same<T, QualType>::value || 824 std::is_same<T, Type>::value || 825 std::is_same<T, TypeLoc>::value || 826 std::is_same<T, NestedNameSpecifier>::value || 827 std::is_same<T, NestedNameSpecifierLoc>::value || 828 std::is_same<T, CXXCtorInitializer>::value; 829 }; 830 template <typename T> 831 const bool IsBaseType<T>::value; 832 833 /// \brief Interface that allows matchers to traverse the AST. 834 /// FIXME: Find a better name. 835 /// 836 /// This provides three entry methods for each base node type in the AST: 837 /// - \c matchesChildOf: 838 /// Matches a matcher on every child node of the given node. Returns true 839 /// if at least one child node could be matched. 840 /// - \c matchesDescendantOf: 841 /// Matches a matcher on all descendant nodes of the given node. Returns true 842 /// if at least one descendant matched. 843 /// - \c matchesAncestorOf: 844 /// Matches a matcher on all ancestors of the given node. Returns true if 845 /// at least one ancestor matched. 846 /// 847 /// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal. 848 /// In the future, we want to implement this for all nodes for which it makes 849 /// sense. In the case of matchesAncestorOf, we'll want to implement it for 850 /// all nodes, as all nodes have ancestors. 851 class ASTMatchFinder { 852 public: 853 /// \brief Defines how we descend a level in the AST when we pass 854 /// through expressions. 855 enum TraversalKind { 856 /// Will traverse any child nodes. 857 TK_AsIs, 858 /// Will not traverse implicit casts and parentheses. 859 TK_IgnoreImplicitCastsAndParentheses 860 }; 861 862 /// \brief Defines how bindings are processed on recursive matches. 863 enum BindKind { 864 /// Stop at the first match and only bind the first match. 865 BK_First, 866 /// Create results for all combinations of bindings that match. 867 BK_All 868 }; 869 870 /// \brief Defines which ancestors are considered for a match. 871 enum AncestorMatchMode { 872 /// All ancestors. 873 AMM_All, 874 /// Direct parent only. 875 AMM_ParentOnly 876 }; 877 878 virtual ~ASTMatchFinder() {} 879 880 /// \brief Returns true if the given class is directly or indirectly derived 881 /// from a base type matching \c base. 882 /// 883 /// A class is considered to be also derived from itself. 884 virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration, 885 const Matcher<NamedDecl> &Base, 886 BoundNodesTreeBuilder *Builder) = 0; 887 888 template <typename T> 889 bool matchesChildOf(const T &Node, 890 const DynTypedMatcher &Matcher, 891 BoundNodesTreeBuilder *Builder, 892 TraversalKind Traverse, 893 BindKind Bind) { 894 static_assert(std::is_base_of<Decl, T>::value || 895 std::is_base_of<Stmt, T>::value || 896 std::is_base_of<NestedNameSpecifier, T>::value || 897 std::is_base_of<NestedNameSpecifierLoc, T>::value || 898 std::is_base_of<TypeLoc, T>::value || 899 std::is_base_of<QualType, T>::value, 900 "unsupported type for recursive matching"); 901 return matchesChildOf(ast_type_traits::DynTypedNode::create(Node), 902 Matcher, Builder, Traverse, Bind); 903 } 904 905 template <typename T> 906 bool matchesDescendantOf(const T &Node, 907 const DynTypedMatcher &Matcher, 908 BoundNodesTreeBuilder *Builder, 909 BindKind Bind) { 910 static_assert(std::is_base_of<Decl, T>::value || 911 std::is_base_of<Stmt, T>::value || 912 std::is_base_of<NestedNameSpecifier, T>::value || 913 std::is_base_of<NestedNameSpecifierLoc, T>::value || 914 std::is_base_of<TypeLoc, T>::value || 915 std::is_base_of<QualType, T>::value, 916 "unsupported type for recursive matching"); 917 return matchesDescendantOf(ast_type_traits::DynTypedNode::create(Node), 918 Matcher, Builder, Bind); 919 } 920 921 // FIXME: Implement support for BindKind. 922 template <typename T> 923 bool matchesAncestorOf(const T &Node, 924 const DynTypedMatcher &Matcher, 925 BoundNodesTreeBuilder *Builder, 926 AncestorMatchMode MatchMode) { 927 static_assert(std::is_base_of<Decl, T>::value || 928 std::is_base_of<NestedNameSpecifierLoc, T>::value || 929 std::is_base_of<Stmt, T>::value || 930 std::is_base_of<TypeLoc, T>::value, 931 "type not allowed for recursive matching"); 932 return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node), 933 Matcher, Builder, MatchMode); 934 } 935 936 virtual ASTContext &getASTContext() const = 0; 937 938 protected: 939 virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node, 940 const DynTypedMatcher &Matcher, 941 BoundNodesTreeBuilder *Builder, 942 TraversalKind Traverse, 943 BindKind Bind) = 0; 944 945 virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node, 946 const DynTypedMatcher &Matcher, 947 BoundNodesTreeBuilder *Builder, 948 BindKind Bind) = 0; 949 950 virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node, 951 const DynTypedMatcher &Matcher, 952 BoundNodesTreeBuilder *Builder, 953 AncestorMatchMode MatchMode) = 0; 954 }; 955 956 /// \brief A type-list implementation. 957 /// 958 /// A "linked list" of types, accessible by using the ::head and ::tail 959 /// typedefs. 960 template <typename... Ts> struct TypeList {}; // Empty sentinel type list. 961 962 template <typename T1, typename... Ts> struct TypeList<T1, Ts...> { 963 /// \brief The first type on the list. 964 typedef T1 head; 965 966 /// \brief A sublist with the tail. ie everything but the head. 967 /// 968 /// This type is used to do recursion. TypeList<>/EmptyTypeList indicates the 969 /// end of the list. 970 typedef TypeList<Ts...> tail; 971 }; 972 973 /// \brief The empty type list. 974 typedef TypeList<> EmptyTypeList; 975 976 /// \brief Helper meta-function to determine if some type \c T is present or 977 /// a parent type in the list. 978 template <typename AnyTypeList, typename T> 979 struct TypeListContainsSuperOf { 980 static const bool value = 981 std::is_base_of<typename AnyTypeList::head, T>::value || 982 TypeListContainsSuperOf<typename AnyTypeList::tail, T>::value; 983 }; 984 template <typename T> 985 struct TypeListContainsSuperOf<EmptyTypeList, T> { 986 static const bool value = false; 987 }; 988 989 /// \brief A "type list" that contains all types. 990 /// 991 /// Useful for matchers like \c anything and \c unless. 992 typedef TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc, 993 QualType, Type, TypeLoc, CXXCtorInitializer> AllNodeBaseTypes; 994 995 /// \brief Helper meta-function to extract the argument out of a function of 996 /// type void(Arg). 997 /// 998 /// See AST_POLYMORPHIC_SUPPORTED_TYPES for details. 999 template <class T> struct ExtractFunctionArgMeta; 1000 template <class T> struct ExtractFunctionArgMeta<void(T)> { 1001 typedef T type; 1002 }; 1003 1004 /// \brief Default type lists for ArgumentAdaptingMatcher matchers. 1005 typedef AllNodeBaseTypes AdaptativeDefaultFromTypes; 1006 typedef TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc, 1007 TypeLoc, QualType> AdaptativeDefaultToTypes; 1008 1009 /// \brief All types that are supported by HasDeclarationMatcher above. 1010 typedef TypeList<CallExpr, CXXConstructExpr, DeclRefExpr, EnumType, 1011 InjectedClassNameType, LabelStmt, AddrLabelExpr, MemberExpr, 1012 QualType, RecordType, TagType, TemplateSpecializationType, 1013 TemplateTypeParmType, TypedefType, 1014 UnresolvedUsingType> HasDeclarationSupportedTypes; 1015 1016 /// \brief Converts a \c Matcher<T> to a matcher of desired type \c To by 1017 /// "adapting" a \c To into a \c T. 1018 /// 1019 /// The \c ArgumentAdapterT argument specifies how the adaptation is done. 1020 /// 1021 /// For example: 1022 /// \c ArgumentAdaptingMatcher<HasMatcher, T>(InnerMatcher); 1023 /// Given that \c InnerMatcher is of type \c Matcher<T>, this returns a matcher 1024 /// that is convertible into any matcher of type \c To by constructing 1025 /// \c HasMatcher<To, T>(InnerMatcher). 1026 /// 1027 /// If a matcher does not need knowledge about the inner type, prefer to use 1028 /// PolymorphicMatcherWithParam1. 1029 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT, 1030 typename FromTypes = AdaptativeDefaultFromTypes, 1031 typename ToTypes = AdaptativeDefaultToTypes> 1032 struct ArgumentAdaptingMatcherFunc { 1033 template <typename T> class Adaptor { 1034 public: 1035 explicit Adaptor(const Matcher<T> &InnerMatcher) 1036 : InnerMatcher(InnerMatcher) {} 1037 1038 typedef ToTypes ReturnTypes; 1039 1040 template <typename To> operator Matcher<To>() const { 1041 return Matcher<To>(new ArgumentAdapterT<To, T>(InnerMatcher)); 1042 } 1043 1044 private: 1045 const Matcher<T> InnerMatcher; 1046 }; 1047 1048 template <typename T> 1049 static Adaptor<T> create(const Matcher<T> &InnerMatcher) { 1050 return Adaptor<T>(InnerMatcher); 1051 } 1052 1053 template <typename T> 1054 Adaptor<T> operator()(const Matcher<T> &InnerMatcher) const { 1055 return create(InnerMatcher); 1056 } 1057 }; 1058 1059 /// \brief A PolymorphicMatcherWithParamN<MatcherT, P1, ..., PN> object can be 1060 /// created from N parameters p1, ..., pN (of type P1, ..., PN) and 1061 /// used as a Matcher<T> where a MatcherT<T, P1, ..., PN>(p1, ..., pN) 1062 /// can be constructed. 1063 /// 1064 /// For example: 1065 /// - PolymorphicMatcherWithParam0<IsDefinitionMatcher>() 1066 /// creates an object that can be used as a Matcher<T> for any type T 1067 /// where an IsDefinitionMatcher<T>() can be constructed. 1068 /// - PolymorphicMatcherWithParam1<ValueEqualsMatcher, int>(42) 1069 /// creates an object that can be used as a Matcher<T> for any type T 1070 /// where a ValueEqualsMatcher<T, int>(42) can be constructed. 1071 template <template <typename T> class MatcherT, 1072 typename ReturnTypesF = void(AllNodeBaseTypes)> 1073 class PolymorphicMatcherWithParam0 { 1074 public: 1075 typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes; 1076 template <typename T> 1077 operator Matcher<T>() const { 1078 static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value, 1079 "right polymorphic conversion"); 1080 return Matcher<T>(new MatcherT<T>()); 1081 } 1082 }; 1083 1084 template <template <typename T, typename P1> class MatcherT, 1085 typename P1, 1086 typename ReturnTypesF = void(AllNodeBaseTypes)> 1087 class PolymorphicMatcherWithParam1 { 1088 public: 1089 explicit PolymorphicMatcherWithParam1(const P1 &Param1) 1090 : Param1(Param1) {} 1091 1092 typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes; 1093 1094 template <typename T> 1095 operator Matcher<T>() const { 1096 static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value, 1097 "right polymorphic conversion"); 1098 return Matcher<T>(new MatcherT<T, P1>(Param1)); 1099 } 1100 1101 private: 1102 const P1 Param1; 1103 }; 1104 1105 template <template <typename T, typename P1, typename P2> class MatcherT, 1106 typename P1, typename P2, 1107 typename ReturnTypesF = void(AllNodeBaseTypes)> 1108 class PolymorphicMatcherWithParam2 { 1109 public: 1110 PolymorphicMatcherWithParam2(const P1 &Param1, const P2 &Param2) 1111 : Param1(Param1), Param2(Param2) {} 1112 1113 typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes; 1114 1115 template <typename T> 1116 operator Matcher<T>() const { 1117 static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value, 1118 "right polymorphic conversion"); 1119 return Matcher<T>(new MatcherT<T, P1, P2>(Param1, Param2)); 1120 } 1121 1122 private: 1123 const P1 Param1; 1124 const P2 Param2; 1125 }; 1126 1127 /// \brief Matches any instance of the given NodeType. 1128 /// 1129 /// This is useful when a matcher syntactically requires a child matcher, 1130 /// but the context doesn't care. See for example: anything(). 1131 class TrueMatcher { 1132 public: 1133 typedef AllNodeBaseTypes ReturnTypes; 1134 1135 template <typename T> 1136 operator Matcher<T>() const { 1137 return DynTypedMatcher::trueMatcher( 1138 ast_type_traits::ASTNodeKind::getFromNodeKind<T>()) 1139 .template unconditionalConvertTo<T>(); 1140 } 1141 }; 1142 1143 /// \brief A Matcher that allows binding the node it matches to an id. 1144 /// 1145 /// BindableMatcher provides a \a bind() method that allows binding the 1146 /// matched node to an id if the match was successful. 1147 template <typename T> 1148 class BindableMatcher : public Matcher<T> { 1149 public: 1150 explicit BindableMatcher(const Matcher<T> &M) : Matcher<T>(M) {} 1151 explicit BindableMatcher(MatcherInterface<T> *Implementation) 1152 : Matcher<T>(Implementation) {} 1153 1154 /// \brief Returns a matcher that will bind the matched node on a match. 1155 /// 1156 /// The returned matcher is equivalent to this matcher, but will 1157 /// bind the matched node on a match. 1158 Matcher<T> bind(StringRef ID) const { 1159 return DynTypedMatcher(*this) 1160 .tryBind(ID) 1161 ->template unconditionalConvertTo<T>(); 1162 } 1163 1164 /// \brief Same as Matcher<T>'s conversion operator, but enables binding on 1165 /// the returned matcher. 1166 operator DynTypedMatcher() const { 1167 DynTypedMatcher Result = static_cast<const Matcher<T>&>(*this); 1168 Result.setAllowBind(true); 1169 return Result; 1170 } 1171 }; 1172 1173 /// \brief Matches nodes of type T that have child nodes of type ChildT for 1174 /// which a specified child matcher matches. 1175 /// 1176 /// ChildT must be an AST base type. 1177 template <typename T, typename ChildT> 1178 class HasMatcher : public WrapperMatcherInterface<T> { 1179 1180 public: 1181 explicit HasMatcher(const Matcher<ChildT> &ChildMatcher) 1182 : HasMatcher::WrapperMatcherInterface(ChildMatcher) {} 1183 1184 bool matches(const T &Node, ASTMatchFinder *Finder, 1185 BoundNodesTreeBuilder *Builder) const override { 1186 return Finder->matchesChildOf(Node, this->InnerMatcher, Builder, 1187 ASTMatchFinder::TK_AsIs, 1188 ASTMatchFinder::BK_First); 1189 } 1190 }; 1191 1192 /// \brief Matches nodes of type T that have child nodes of type ChildT for 1193 /// which a specified child matcher matches. ChildT must be an AST base 1194 /// type. 1195 /// As opposed to the HasMatcher, the ForEachMatcher will produce a match 1196 /// for each child that matches. 1197 template <typename T, typename ChildT> 1198 class ForEachMatcher : public WrapperMatcherInterface<T> { 1199 static_assert(IsBaseType<ChildT>::value, 1200 "for each only accepts base type matcher"); 1201 1202 public: 1203 explicit ForEachMatcher(const Matcher<ChildT> &ChildMatcher) 1204 : ForEachMatcher::WrapperMatcherInterface(ChildMatcher) {} 1205 1206 bool matches(const T& Node, ASTMatchFinder* Finder, 1207 BoundNodesTreeBuilder* Builder) const override { 1208 return Finder->matchesChildOf( 1209 Node, this->InnerMatcher, Builder, 1210 ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses, 1211 ASTMatchFinder::BK_All); 1212 } 1213 }; 1214 1215 /// \brief VariadicOperatorMatcher related types. 1216 /// @{ 1217 1218 /// \brief Polymorphic matcher object that uses a \c 1219 /// DynTypedMatcher::VariadicOperator operator. 1220 /// 1221 /// Input matchers can have any type (including other polymorphic matcher 1222 /// types), and the actual Matcher<T> is generated on demand with an implicit 1223 /// coversion operator. 1224 template <typename... Ps> class VariadicOperatorMatcher { 1225 public: 1226 VariadicOperatorMatcher(DynTypedMatcher::VariadicOperator Op, Ps &&... Params) 1227 : Op(Op), Params(std::forward<Ps>(Params)...) {} 1228 1229 template <typename T> operator Matcher<T>() const { 1230 return DynTypedMatcher::constructVariadic( 1231 Op, ast_type_traits::ASTNodeKind::getFromNodeKind<T>(), 1232 getMatchers<T>(llvm::index_sequence_for<Ps...>())) 1233 .template unconditionalConvertTo<T>(); 1234 } 1235 1236 private: 1237 // Helper method to unpack the tuple into a vector. 1238 template <typename T, std::size_t... Is> 1239 std::vector<DynTypedMatcher> getMatchers(llvm::index_sequence<Is...>) const { 1240 return {Matcher<T>(std::get<Is>(Params))...}; 1241 } 1242 1243 const DynTypedMatcher::VariadicOperator Op; 1244 std::tuple<Ps...> Params; 1245 }; 1246 1247 /// \brief Overloaded function object to generate VariadicOperatorMatcher 1248 /// objects from arbitrary matchers. 1249 template <unsigned MinCount, unsigned MaxCount> 1250 struct VariadicOperatorMatcherFunc { 1251 DynTypedMatcher::VariadicOperator Op; 1252 1253 template <typename... Ms> 1254 VariadicOperatorMatcher<Ms...> operator()(Ms &&... Ps) const { 1255 static_assert(MinCount <= sizeof...(Ms) && sizeof...(Ms) <= MaxCount, 1256 "invalid number of parameters for variadic matcher"); 1257 return VariadicOperatorMatcher<Ms...>(Op, std::forward<Ms>(Ps)...); 1258 } 1259 }; 1260 1261 /// @} 1262 1263 template <typename T> 1264 inline Matcher<T> DynTypedMatcher::unconditionalConvertTo() const { 1265 return Matcher<T>(*this); 1266 } 1267 1268 /// \brief Creates a Matcher<T> that matches if all inner matchers match. 1269 template<typename T> 1270 BindableMatcher<T> makeAllOfComposite( 1271 ArrayRef<const Matcher<T> *> InnerMatchers) { 1272 // For the size() == 0 case, we return a "true" matcher. 1273 if (InnerMatchers.size() == 0) { 1274 return BindableMatcher<T>(TrueMatcher()); 1275 } 1276 // For the size() == 1 case, we simply return that one matcher. 1277 // No need to wrap it in a variadic operation. 1278 if (InnerMatchers.size() == 1) { 1279 return BindableMatcher<T>(*InnerMatchers[0]); 1280 } 1281 1282 typedef llvm::pointee_iterator<const Matcher<T> *const *> PI; 1283 std::vector<DynTypedMatcher> DynMatchers(PI(InnerMatchers.begin()), 1284 PI(InnerMatchers.end())); 1285 return BindableMatcher<T>( 1286 DynTypedMatcher::constructVariadic( 1287 DynTypedMatcher::VO_AllOf, 1288 ast_type_traits::ASTNodeKind::getFromNodeKind<T>(), 1289 std::move(DynMatchers)) 1290 .template unconditionalConvertTo<T>()); 1291 } 1292 1293 /// \brief Creates a Matcher<T> that matches if 1294 /// T is dyn_cast'able into InnerT and all inner matchers match. 1295 /// 1296 /// Returns BindableMatcher, as matchers that use dyn_cast have 1297 /// the same object both to match on and to run submatchers on, 1298 /// so there is no ambiguity with what gets bound. 1299 template<typename T, typename InnerT> 1300 BindableMatcher<T> makeDynCastAllOfComposite( 1301 ArrayRef<const Matcher<InnerT> *> InnerMatchers) { 1302 return BindableMatcher<T>( 1303 makeAllOfComposite(InnerMatchers).template dynCastTo<T>()); 1304 } 1305 1306 /// \brief Matches nodes of type T that have at least one descendant node of 1307 /// type DescendantT for which the given inner matcher matches. 1308 /// 1309 /// DescendantT must be an AST base type. 1310 template <typename T, typename DescendantT> 1311 class HasDescendantMatcher : public WrapperMatcherInterface<T> { 1312 static_assert(IsBaseType<DescendantT>::value, 1313 "has descendant only accepts base type matcher"); 1314 1315 public: 1316 explicit HasDescendantMatcher(const Matcher<DescendantT> &DescendantMatcher) 1317 : HasDescendantMatcher::WrapperMatcherInterface(DescendantMatcher) {} 1318 1319 bool matches(const T &Node, ASTMatchFinder *Finder, 1320 BoundNodesTreeBuilder *Builder) const override { 1321 return Finder->matchesDescendantOf(Node, this->InnerMatcher, Builder, 1322 ASTMatchFinder::BK_First); 1323 } 1324 }; 1325 1326 /// \brief Matches nodes of type \c T that have a parent node of type \c ParentT 1327 /// for which the given inner matcher matches. 1328 /// 1329 /// \c ParentT must be an AST base type. 1330 template <typename T, typename ParentT> 1331 class HasParentMatcher : public WrapperMatcherInterface<T> { 1332 static_assert(IsBaseType<ParentT>::value, 1333 "has parent only accepts base type matcher"); 1334 1335 public: 1336 explicit HasParentMatcher(const Matcher<ParentT> &ParentMatcher) 1337 : HasParentMatcher::WrapperMatcherInterface(ParentMatcher) {} 1338 1339 bool matches(const T &Node, ASTMatchFinder *Finder, 1340 BoundNodesTreeBuilder *Builder) const override { 1341 return Finder->matchesAncestorOf(Node, this->InnerMatcher, Builder, 1342 ASTMatchFinder::AMM_ParentOnly); 1343 } 1344 }; 1345 1346 /// \brief Matches nodes of type \c T that have at least one ancestor node of 1347 /// type \c AncestorT for which the given inner matcher matches. 1348 /// 1349 /// \c AncestorT must be an AST base type. 1350 template <typename T, typename AncestorT> 1351 class HasAncestorMatcher : public WrapperMatcherInterface<T> { 1352 static_assert(IsBaseType<AncestorT>::value, 1353 "has ancestor only accepts base type matcher"); 1354 1355 public: 1356 explicit HasAncestorMatcher(const Matcher<AncestorT> &AncestorMatcher) 1357 : HasAncestorMatcher::WrapperMatcherInterface(AncestorMatcher) {} 1358 1359 bool matches(const T &Node, ASTMatchFinder *Finder, 1360 BoundNodesTreeBuilder *Builder) const override { 1361 return Finder->matchesAncestorOf(Node, this->InnerMatcher, Builder, 1362 ASTMatchFinder::AMM_All); 1363 } 1364 }; 1365 1366 /// \brief Matches nodes of type T that have at least one descendant node of 1367 /// type DescendantT for which the given inner matcher matches. 1368 /// 1369 /// DescendantT must be an AST base type. 1370 /// As opposed to HasDescendantMatcher, ForEachDescendantMatcher will match 1371 /// for each descendant node that matches instead of only for the first. 1372 template <typename T, typename DescendantT> 1373 class ForEachDescendantMatcher : public WrapperMatcherInterface<T> { 1374 static_assert(IsBaseType<DescendantT>::value, 1375 "for each descendant only accepts base type matcher"); 1376 1377 public: 1378 explicit ForEachDescendantMatcher( 1379 const Matcher<DescendantT> &DescendantMatcher) 1380 : ForEachDescendantMatcher::WrapperMatcherInterface(DescendantMatcher) {} 1381 1382 bool matches(const T &Node, ASTMatchFinder *Finder, 1383 BoundNodesTreeBuilder *Builder) const override { 1384 return Finder->matchesDescendantOf(Node, this->InnerMatcher, Builder, 1385 ASTMatchFinder::BK_All); 1386 } 1387 }; 1388 1389 /// \brief Matches on nodes that have a getValue() method if getValue() equals 1390 /// the value the ValueEqualsMatcher was constructed with. 1391 template <typename T, typename ValueT> 1392 class ValueEqualsMatcher : public SingleNodeMatcherInterface<T> { 1393 static_assert(std::is_base_of<CharacterLiteral, T>::value || 1394 std::is_base_of<CXXBoolLiteralExpr, T>::value || 1395 std::is_base_of<FloatingLiteral, T>::value || 1396 std::is_base_of<IntegerLiteral, T>::value, 1397 "the node must have a getValue method"); 1398 1399 public: 1400 explicit ValueEqualsMatcher(const ValueT &ExpectedValue) 1401 : ExpectedValue(ExpectedValue) {} 1402 1403 bool matchesNode(const T &Node) const override { 1404 return Node.getValue() == ExpectedValue; 1405 } 1406 1407 private: 1408 const ValueT ExpectedValue; 1409 }; 1410 1411 /// \brief Template specializations to easily write matchers for floating point 1412 /// literals. 1413 template <> 1414 inline bool ValueEqualsMatcher<FloatingLiteral, double>::matchesNode( 1415 const FloatingLiteral &Node) const { 1416 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle) 1417 return Node.getValue().convertToFloat() == ExpectedValue; 1418 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble) 1419 return Node.getValue().convertToDouble() == ExpectedValue; 1420 return false; 1421 } 1422 template <> 1423 inline bool ValueEqualsMatcher<FloatingLiteral, float>::matchesNode( 1424 const FloatingLiteral &Node) const { 1425 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle) 1426 return Node.getValue().convertToFloat() == ExpectedValue; 1427 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble) 1428 return Node.getValue().convertToDouble() == ExpectedValue; 1429 return false; 1430 } 1431 template <> 1432 inline bool ValueEqualsMatcher<FloatingLiteral, llvm::APFloat>::matchesNode( 1433 const FloatingLiteral &Node) const { 1434 return ExpectedValue.compare(Node.getValue()) == llvm::APFloat::cmpEqual; 1435 } 1436 1437 /// \brief A VariadicDynCastAllOfMatcher<SourceT, TargetT> object is a 1438 /// variadic functor that takes a number of Matcher<TargetT> and returns a 1439 /// Matcher<SourceT> that matches TargetT nodes that are matched by all of the 1440 /// given matchers, if SourceT can be dynamically casted into TargetT. 1441 /// 1442 /// For example: 1443 /// const VariadicDynCastAllOfMatcher< 1444 /// Decl, CXXRecordDecl> record; 1445 /// Creates a functor record(...) that creates a Matcher<Decl> given 1446 /// a variable number of arguments of type Matcher<CXXRecordDecl>. 1447 /// The returned matcher matches if the given Decl can by dynamically 1448 /// casted to CXXRecordDecl and all given matchers match. 1449 template <typename SourceT, typename TargetT> 1450 class VariadicDynCastAllOfMatcher 1451 : public VariadicFunction<BindableMatcher<SourceT>, Matcher<TargetT>, 1452 makeDynCastAllOfComposite<SourceT, TargetT>> { 1453 public: 1454 VariadicDynCastAllOfMatcher() {} 1455 }; 1456 1457 /// \brief A \c VariadicAllOfMatcher<T> object is a variadic functor that takes 1458 /// a number of \c Matcher<T> and returns a \c Matcher<T> that matches \c T 1459 /// nodes that are matched by all of the given matchers. 1460 /// 1461 /// For example: 1462 /// const VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier; 1463 /// Creates a functor nestedNameSpecifier(...) that creates a 1464 /// \c Matcher<NestedNameSpecifier> given a variable number of arguments of type 1465 /// \c Matcher<NestedNameSpecifier>. 1466 /// The returned matcher matches if all given matchers match. 1467 template <typename T> 1468 class VariadicAllOfMatcher 1469 : public VariadicFunction<BindableMatcher<T>, Matcher<T>, 1470 makeAllOfComposite<T>> { 1471 public: 1472 VariadicAllOfMatcher() {} 1473 }; 1474 1475 /// \brief Matches nodes of type \c TLoc for which the inner 1476 /// \c Matcher<T> matches. 1477 template <typename TLoc, typename T> 1478 class LocMatcher : public WrapperMatcherInterface<TLoc> { 1479 public: 1480 explicit LocMatcher(const Matcher<T> &InnerMatcher) 1481 : LocMatcher::WrapperMatcherInterface(InnerMatcher) {} 1482 1483 bool matches(const TLoc &Node, ASTMatchFinder *Finder, 1484 BoundNodesTreeBuilder *Builder) const override { 1485 if (!Node) 1486 return false; 1487 return this->InnerMatcher.matches(extract(Node), Finder, Builder); 1488 } 1489 1490 private: 1491 static ast_type_traits::DynTypedNode 1492 extract(const NestedNameSpecifierLoc &Loc) { 1493 return ast_type_traits::DynTypedNode::create(*Loc.getNestedNameSpecifier()); 1494 } 1495 }; 1496 1497 /// \brief Matches \c TypeLocs based on an inner matcher matching a certain 1498 /// \c QualType. 1499 /// 1500 /// Used to implement the \c loc() matcher. 1501 class TypeLocTypeMatcher : public WrapperMatcherInterface<TypeLoc> { 1502 public: 1503 explicit TypeLocTypeMatcher(const Matcher<QualType> &InnerMatcher) 1504 : TypeLocTypeMatcher::WrapperMatcherInterface(InnerMatcher) {} 1505 1506 bool matches(const TypeLoc &Node, ASTMatchFinder *Finder, 1507 BoundNodesTreeBuilder *Builder) const override { 1508 if (!Node) 1509 return false; 1510 return this->InnerMatcher.matches( 1511 ast_type_traits::DynTypedNode::create(Node.getType()), Finder, Builder); 1512 } 1513 }; 1514 1515 /// \brief Matches nodes of type \c T for which the inner matcher matches on a 1516 /// another node of type \c T that can be reached using a given traverse 1517 /// function. 1518 template <typename T> 1519 class TypeTraverseMatcher : public WrapperMatcherInterface<T> { 1520 public: 1521 explicit TypeTraverseMatcher(const Matcher<QualType> &InnerMatcher, 1522 QualType (T::*TraverseFunction)() const) 1523 : TypeTraverseMatcher::WrapperMatcherInterface(InnerMatcher), 1524 TraverseFunction(TraverseFunction) {} 1525 1526 bool matches(const T &Node, ASTMatchFinder *Finder, 1527 BoundNodesTreeBuilder *Builder) const override { 1528 QualType NextNode = (Node.*TraverseFunction)(); 1529 if (NextNode.isNull()) 1530 return false; 1531 return this->InnerMatcher.matches( 1532 ast_type_traits::DynTypedNode::create(NextNode), Finder, Builder); 1533 } 1534 1535 private: 1536 QualType (T::*TraverseFunction)() const; 1537 }; 1538 1539 /// \brief Matches nodes of type \c T in a ..Loc hierarchy, for which the inner 1540 /// matcher matches on a another node of type \c T that can be reached using a 1541 /// given traverse function. 1542 template <typename T> 1543 class TypeLocTraverseMatcher : public WrapperMatcherInterface<T> { 1544 public: 1545 explicit TypeLocTraverseMatcher(const Matcher<TypeLoc> &InnerMatcher, 1546 TypeLoc (T::*TraverseFunction)() const) 1547 : TypeLocTraverseMatcher::WrapperMatcherInterface(InnerMatcher), 1548 TraverseFunction(TraverseFunction) {} 1549 1550 bool matches(const T &Node, ASTMatchFinder *Finder, 1551 BoundNodesTreeBuilder *Builder) const override { 1552 TypeLoc NextNode = (Node.*TraverseFunction)(); 1553 if (!NextNode) 1554 return false; 1555 return this->InnerMatcher.matches( 1556 ast_type_traits::DynTypedNode::create(NextNode), Finder, Builder); 1557 } 1558 1559 private: 1560 TypeLoc (T::*TraverseFunction)() const; 1561 }; 1562 1563 /// \brief Converts a \c Matcher<InnerT> to a \c Matcher<OuterT>, where 1564 /// \c OuterT is any type that is supported by \c Getter. 1565 /// 1566 /// \code Getter<OuterT>::value() \endcode returns a 1567 /// \code InnerTBase (OuterT::*)() \endcode, which is used to adapt a \c OuterT 1568 /// object into a \c InnerT 1569 template <typename InnerTBase, 1570 template <typename OuterT> class Getter, 1571 template <typename OuterT> class MatcherImpl, 1572 typename ReturnTypesF> 1573 class TypeTraversePolymorphicMatcher { 1574 private: 1575 typedef TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, 1576 ReturnTypesF> Self; 1577 static Self create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers); 1578 1579 public: 1580 typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes; 1581 1582 explicit TypeTraversePolymorphicMatcher( 1583 ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) 1584 : InnerMatcher(makeAllOfComposite(InnerMatchers)) {} 1585 1586 template <typename OuterT> operator Matcher<OuterT>() const { 1587 return Matcher<OuterT>( 1588 new MatcherImpl<OuterT>(InnerMatcher, Getter<OuterT>::value())); 1589 } 1590 1591 struct Func 1592 : public VariadicFunction<Self, Matcher<InnerTBase>, &Self::create> { 1593 Func() {} 1594 }; 1595 1596 private: 1597 const Matcher<InnerTBase> InnerMatcher; 1598 }; 1599 1600 /// \brief A simple memoizer of T(*)() functions. 1601 /// 1602 /// It will call the passed 'Func' template parameter at most once. 1603 /// Used to support AST_MATCHER_FUNCTION() macro. 1604 template <typename Matcher, Matcher (*Func)()> class MemoizedMatcher { 1605 struct Wrapper { 1606 Wrapper() : M(Func()) {} 1607 Matcher M; 1608 }; 1609 1610 public: 1611 static const Matcher &getInstance() { 1612 static llvm::ManagedStatic<Wrapper> Instance; 1613 return Instance->M; 1614 } 1615 }; 1616 1617 // Define the create() method out of line to silence a GCC warning about 1618 // the struct "Func" having greater visibility than its base, which comes from 1619 // using the flag -fvisibility-inlines-hidden. 1620 template <typename InnerTBase, template <typename OuterT> class Getter, 1621 template <typename OuterT> class MatcherImpl, typename ReturnTypesF> 1622 TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, ReturnTypesF> 1623 TypeTraversePolymorphicMatcher< 1624 InnerTBase, Getter, MatcherImpl, 1625 ReturnTypesF>::create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) { 1626 return Self(InnerMatchers); 1627 } 1628 1629 // FIXME: unify ClassTemplateSpecializationDecl and TemplateSpecializationType's 1630 // APIs for accessing the template argument list. 1631 inline ArrayRef<TemplateArgument> 1632 getTemplateSpecializationArgs(const ClassTemplateSpecializationDecl &D) { 1633 return D.getTemplateArgs().asArray(); 1634 } 1635 1636 inline ArrayRef<TemplateArgument> 1637 getTemplateSpecializationArgs(const TemplateSpecializationType &T) { 1638 return llvm::makeArrayRef(T.getArgs(), T.getNumArgs()); 1639 } 1640 1641 struct NotEqualsBoundNodePredicate { 1642 bool operator()(const internal::BoundNodesMap &Nodes) const { 1643 return Nodes.getNode(ID) != Node; 1644 } 1645 std::string ID; 1646 ast_type_traits::DynTypedNode Node; 1647 }; 1648 1649 template <typename Ty> 1650 struct GetBodyMatcher { 1651 static const Stmt *get(const Ty &Node) { 1652 return Node.getBody(); 1653 } 1654 }; 1655 1656 template <> 1657 inline const Stmt *GetBodyMatcher<FunctionDecl>::get(const FunctionDecl &Node) { 1658 return Node.doesThisDeclarationHaveABody() ? Node.getBody() : nullptr; 1659 } 1660 1661 template <typename Ty> 1662 struct HasSizeMatcher { 1663 static bool hasSize(const Ty &Node, unsigned int N) { 1664 return Node.getSize() == N; 1665 } 1666 }; 1667 1668 template <> 1669 inline bool HasSizeMatcher<StringLiteral>::hasSize( 1670 const StringLiteral &Node, unsigned int N) { 1671 return Node.getLength() == N; 1672 } 1673 1674 template <typename Ty> 1675 struct GetSourceExpressionMatcher { 1676 static const Expr *get(const Ty &Node) { 1677 return Node.getSubExpr(); 1678 } 1679 }; 1680 1681 template <> 1682 inline const Expr *GetSourceExpressionMatcher<OpaqueValueExpr>::get( 1683 const OpaqueValueExpr &Node) { 1684 return Node.getSourceExpr(); 1685 } 1686 1687 template <typename Ty> 1688 struct CompoundStmtMatcher { 1689 static const CompoundStmt *get(const Ty &Node) { 1690 return &Node; 1691 } 1692 }; 1693 1694 template <> 1695 inline const CompoundStmt * 1696 CompoundStmtMatcher<StmtExpr>::get(const StmtExpr &Node) { 1697 return Node.getSubStmt(); 1698 } 1699 1700 1701 } // end namespace internal 1702 } // end namespace ast_matchers 1703 } // end namespace clang 1704 1705 #endif // LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H 1706