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 operator new of the new call and returns whether the 791 /// inner matcher matches on it. 792 bool matchesSpecialized(const CXXNewExpr &Node, 793 ASTMatchFinder *Finder, 794 BoundNodesTreeBuilder *Builder) const { 795 return matchesDecl(Node.getOperatorNew(), Finder, Builder); 796 } 797 798 /// \brief Extracts the \c ValueDecl a \c MemberExpr refers to and returns 799 /// whether the inner matcher matches on it. 800 bool matchesSpecialized(const MemberExpr &Node, 801 ASTMatchFinder *Finder, 802 BoundNodesTreeBuilder *Builder) const { 803 return matchesDecl(Node.getMemberDecl(), Finder, Builder); 804 } 805 806 /// \brief Extracts the \c LabelDecl a \c AddrLabelExpr refers to and returns 807 /// whether the inner matcher matches on it. 808 bool matchesSpecialized(const AddrLabelExpr &Node, 809 ASTMatchFinder *Finder, 810 BoundNodesTreeBuilder *Builder) const { 811 return matchesDecl(Node.getLabel(), Finder, Builder); 812 } 813 814 /// \brief Returns whether the inner matcher \c Node. Returns false if \c Node 815 /// is \c NULL. 816 bool matchesDecl(const Decl *Node, ASTMatchFinder *Finder, 817 BoundNodesTreeBuilder *Builder) const { 818 return Node != nullptr && 819 this->InnerMatcher.matches( 820 ast_type_traits::DynTypedNode::create(*Node), Finder, Builder); 821 } 822 }; 823 824 /// \brief IsBaseType<T>::value is true if T is a "base" type in the AST 825 /// node class hierarchies. 826 template <typename T> 827 struct IsBaseType { 828 static const bool value = 829 std::is_same<T, Decl>::value || 830 std::is_same<T, Stmt>::value || 831 std::is_same<T, QualType>::value || 832 std::is_same<T, Type>::value || 833 std::is_same<T, TypeLoc>::value || 834 std::is_same<T, NestedNameSpecifier>::value || 835 std::is_same<T, NestedNameSpecifierLoc>::value || 836 std::is_same<T, CXXCtorInitializer>::value; 837 }; 838 template <typename T> 839 const bool IsBaseType<T>::value; 840 841 /// \brief Interface that allows matchers to traverse the AST. 842 /// FIXME: Find a better name. 843 /// 844 /// This provides three entry methods for each base node type in the AST: 845 /// - \c matchesChildOf: 846 /// Matches a matcher on every child node of the given node. Returns true 847 /// if at least one child node could be matched. 848 /// - \c matchesDescendantOf: 849 /// Matches a matcher on all descendant nodes of the given node. Returns true 850 /// if at least one descendant matched. 851 /// - \c matchesAncestorOf: 852 /// Matches a matcher on all ancestors of the given node. Returns true if 853 /// at least one ancestor matched. 854 /// 855 /// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal. 856 /// In the future, we want to implement this for all nodes for which it makes 857 /// sense. In the case of matchesAncestorOf, we'll want to implement it for 858 /// all nodes, as all nodes have ancestors. 859 class ASTMatchFinder { 860 public: 861 /// \brief Defines how we descend a level in the AST when we pass 862 /// through expressions. 863 enum TraversalKind { 864 /// Will traverse any child nodes. 865 TK_AsIs, 866 /// Will not traverse implicit casts and parentheses. 867 TK_IgnoreImplicitCastsAndParentheses 868 }; 869 870 /// \brief Defines how bindings are processed on recursive matches. 871 enum BindKind { 872 /// Stop at the first match and only bind the first match. 873 BK_First, 874 /// Create results for all combinations of bindings that match. 875 BK_All 876 }; 877 878 /// \brief Defines which ancestors are considered for a match. 879 enum AncestorMatchMode { 880 /// All ancestors. 881 AMM_All, 882 /// Direct parent only. 883 AMM_ParentOnly 884 }; 885 886 virtual ~ASTMatchFinder() {} 887 888 /// \brief Returns true if the given class is directly or indirectly derived 889 /// from a base type matching \c base. 890 /// 891 /// A class is considered to be also derived from itself. 892 virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration, 893 const Matcher<NamedDecl> &Base, 894 BoundNodesTreeBuilder *Builder) = 0; 895 896 template <typename T> 897 bool matchesChildOf(const T &Node, 898 const DynTypedMatcher &Matcher, 899 BoundNodesTreeBuilder *Builder, 900 TraversalKind Traverse, 901 BindKind Bind) { 902 static_assert(std::is_base_of<Decl, T>::value || 903 std::is_base_of<Stmt, T>::value || 904 std::is_base_of<NestedNameSpecifier, T>::value || 905 std::is_base_of<NestedNameSpecifierLoc, T>::value || 906 std::is_base_of<TypeLoc, T>::value || 907 std::is_base_of<QualType, T>::value, 908 "unsupported type for recursive matching"); 909 return matchesChildOf(ast_type_traits::DynTypedNode::create(Node), 910 Matcher, Builder, Traverse, Bind); 911 } 912 913 template <typename T> 914 bool matchesDescendantOf(const T &Node, 915 const DynTypedMatcher &Matcher, 916 BoundNodesTreeBuilder *Builder, 917 BindKind Bind) { 918 static_assert(std::is_base_of<Decl, T>::value || 919 std::is_base_of<Stmt, T>::value || 920 std::is_base_of<NestedNameSpecifier, T>::value || 921 std::is_base_of<NestedNameSpecifierLoc, T>::value || 922 std::is_base_of<TypeLoc, T>::value || 923 std::is_base_of<QualType, T>::value, 924 "unsupported type for recursive matching"); 925 return matchesDescendantOf(ast_type_traits::DynTypedNode::create(Node), 926 Matcher, Builder, Bind); 927 } 928 929 // FIXME: Implement support for BindKind. 930 template <typename T> 931 bool matchesAncestorOf(const T &Node, 932 const DynTypedMatcher &Matcher, 933 BoundNodesTreeBuilder *Builder, 934 AncestorMatchMode MatchMode) { 935 static_assert(std::is_base_of<Decl, T>::value || 936 std::is_base_of<NestedNameSpecifierLoc, T>::value || 937 std::is_base_of<Stmt, T>::value || 938 std::is_base_of<TypeLoc, T>::value, 939 "type not allowed for recursive matching"); 940 return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node), 941 Matcher, Builder, MatchMode); 942 } 943 944 virtual ASTContext &getASTContext() const = 0; 945 946 protected: 947 virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node, 948 const DynTypedMatcher &Matcher, 949 BoundNodesTreeBuilder *Builder, 950 TraversalKind Traverse, 951 BindKind Bind) = 0; 952 953 virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node, 954 const DynTypedMatcher &Matcher, 955 BoundNodesTreeBuilder *Builder, 956 BindKind Bind) = 0; 957 958 virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node, 959 const DynTypedMatcher &Matcher, 960 BoundNodesTreeBuilder *Builder, 961 AncestorMatchMode MatchMode) = 0; 962 }; 963 964 /// \brief A type-list implementation. 965 /// 966 /// A "linked list" of types, accessible by using the ::head and ::tail 967 /// typedefs. 968 template <typename... Ts> struct TypeList {}; // Empty sentinel type list. 969 970 template <typename T1, typename... Ts> struct TypeList<T1, Ts...> { 971 /// \brief The first type on the list. 972 typedef T1 head; 973 974 /// \brief A sublist with the tail. ie everything but the head. 975 /// 976 /// This type is used to do recursion. TypeList<>/EmptyTypeList indicates the 977 /// end of the list. 978 typedef TypeList<Ts...> tail; 979 }; 980 981 /// \brief The empty type list. 982 typedef TypeList<> EmptyTypeList; 983 984 /// \brief Helper meta-function to determine if some type \c T is present or 985 /// a parent type in the list. 986 template <typename AnyTypeList, typename T> 987 struct TypeListContainsSuperOf { 988 static const bool value = 989 std::is_base_of<typename AnyTypeList::head, T>::value || 990 TypeListContainsSuperOf<typename AnyTypeList::tail, T>::value; 991 }; 992 template <typename T> 993 struct TypeListContainsSuperOf<EmptyTypeList, T> { 994 static const bool value = false; 995 }; 996 997 /// \brief A "type list" that contains all types. 998 /// 999 /// Useful for matchers like \c anything and \c unless. 1000 typedef TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc, 1001 QualType, Type, TypeLoc, CXXCtorInitializer> AllNodeBaseTypes; 1002 1003 /// \brief Helper meta-function to extract the argument out of a function of 1004 /// type void(Arg). 1005 /// 1006 /// See AST_POLYMORPHIC_SUPPORTED_TYPES for details. 1007 template <class T> struct ExtractFunctionArgMeta; 1008 template <class T> struct ExtractFunctionArgMeta<void(T)> { 1009 typedef T type; 1010 }; 1011 1012 /// \brief Default type lists for ArgumentAdaptingMatcher matchers. 1013 typedef AllNodeBaseTypes AdaptativeDefaultFromTypes; 1014 typedef TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc, 1015 TypeLoc, QualType> AdaptativeDefaultToTypes; 1016 1017 /// \brief All types that are supported by HasDeclarationMatcher above. 1018 typedef TypeList<CallExpr, CXXConstructExpr, CXXNewExpr, DeclRefExpr, EnumType, 1019 InjectedClassNameType, LabelStmt, AddrLabelExpr, MemberExpr, 1020 QualType, RecordType, TagType, TemplateSpecializationType, 1021 TemplateTypeParmType, TypedefType, UnresolvedUsingType> 1022 HasDeclarationSupportedTypes; 1023 1024 /// \brief Converts a \c Matcher<T> to a matcher of desired type \c To by 1025 /// "adapting" a \c To into a \c T. 1026 /// 1027 /// The \c ArgumentAdapterT argument specifies how the adaptation is done. 1028 /// 1029 /// For example: 1030 /// \c ArgumentAdaptingMatcher<HasMatcher, T>(InnerMatcher); 1031 /// Given that \c InnerMatcher is of type \c Matcher<T>, this returns a matcher 1032 /// that is convertible into any matcher of type \c To by constructing 1033 /// \c HasMatcher<To, T>(InnerMatcher). 1034 /// 1035 /// If a matcher does not need knowledge about the inner type, prefer to use 1036 /// PolymorphicMatcherWithParam1. 1037 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT, 1038 typename FromTypes = AdaptativeDefaultFromTypes, 1039 typename ToTypes = AdaptativeDefaultToTypes> 1040 struct ArgumentAdaptingMatcherFunc { 1041 template <typename T> class Adaptor { 1042 public: 1043 explicit Adaptor(const Matcher<T> &InnerMatcher) 1044 : InnerMatcher(InnerMatcher) {} 1045 1046 typedef ToTypes ReturnTypes; 1047 1048 template <typename To> operator Matcher<To>() const { 1049 return Matcher<To>(new ArgumentAdapterT<To, T>(InnerMatcher)); 1050 } 1051 1052 private: 1053 const Matcher<T> InnerMatcher; 1054 }; 1055 1056 template <typename T> 1057 static Adaptor<T> create(const Matcher<T> &InnerMatcher) { 1058 return Adaptor<T>(InnerMatcher); 1059 } 1060 1061 template <typename T> 1062 Adaptor<T> operator()(const Matcher<T> &InnerMatcher) const { 1063 return create(InnerMatcher); 1064 } 1065 }; 1066 1067 /// \brief A PolymorphicMatcherWithParamN<MatcherT, P1, ..., PN> object can be 1068 /// created from N parameters p1, ..., pN (of type P1, ..., PN) and 1069 /// used as a Matcher<T> where a MatcherT<T, P1, ..., PN>(p1, ..., pN) 1070 /// can be constructed. 1071 /// 1072 /// For example: 1073 /// - PolymorphicMatcherWithParam0<IsDefinitionMatcher>() 1074 /// creates an object that can be used as a Matcher<T> for any type T 1075 /// where an IsDefinitionMatcher<T>() can be constructed. 1076 /// - PolymorphicMatcherWithParam1<ValueEqualsMatcher, int>(42) 1077 /// creates an object that can be used as a Matcher<T> for any type T 1078 /// where a ValueEqualsMatcher<T, int>(42) can be constructed. 1079 template <template <typename T> class MatcherT, 1080 typename ReturnTypesF = void(AllNodeBaseTypes)> 1081 class PolymorphicMatcherWithParam0 { 1082 public: 1083 typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes; 1084 template <typename T> 1085 operator Matcher<T>() const { 1086 static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value, 1087 "right polymorphic conversion"); 1088 return Matcher<T>(new MatcherT<T>()); 1089 } 1090 }; 1091 1092 template <template <typename T, typename P1> class MatcherT, 1093 typename P1, 1094 typename ReturnTypesF = void(AllNodeBaseTypes)> 1095 class PolymorphicMatcherWithParam1 { 1096 public: 1097 explicit PolymorphicMatcherWithParam1(const P1 &Param1) 1098 : Param1(Param1) {} 1099 1100 typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes; 1101 1102 template <typename T> 1103 operator Matcher<T>() const { 1104 static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value, 1105 "right polymorphic conversion"); 1106 return Matcher<T>(new MatcherT<T, P1>(Param1)); 1107 } 1108 1109 private: 1110 const P1 Param1; 1111 }; 1112 1113 template <template <typename T, typename P1, typename P2> class MatcherT, 1114 typename P1, typename P2, 1115 typename ReturnTypesF = void(AllNodeBaseTypes)> 1116 class PolymorphicMatcherWithParam2 { 1117 public: 1118 PolymorphicMatcherWithParam2(const P1 &Param1, const P2 &Param2) 1119 : Param1(Param1), Param2(Param2) {} 1120 1121 typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes; 1122 1123 template <typename T> 1124 operator Matcher<T>() const { 1125 static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value, 1126 "right polymorphic conversion"); 1127 return Matcher<T>(new MatcherT<T, P1, P2>(Param1, Param2)); 1128 } 1129 1130 private: 1131 const P1 Param1; 1132 const P2 Param2; 1133 }; 1134 1135 /// \brief Matches any instance of the given NodeType. 1136 /// 1137 /// This is useful when a matcher syntactically requires a child matcher, 1138 /// but the context doesn't care. See for example: anything(). 1139 class TrueMatcher { 1140 public: 1141 typedef AllNodeBaseTypes ReturnTypes; 1142 1143 template <typename T> 1144 operator Matcher<T>() const { 1145 return DynTypedMatcher::trueMatcher( 1146 ast_type_traits::ASTNodeKind::getFromNodeKind<T>()) 1147 .template unconditionalConvertTo<T>(); 1148 } 1149 }; 1150 1151 /// \brief A Matcher that allows binding the node it matches to an id. 1152 /// 1153 /// BindableMatcher provides a \a bind() method that allows binding the 1154 /// matched node to an id if the match was successful. 1155 template <typename T> 1156 class BindableMatcher : public Matcher<T> { 1157 public: 1158 explicit BindableMatcher(const Matcher<T> &M) : Matcher<T>(M) {} 1159 explicit BindableMatcher(MatcherInterface<T> *Implementation) 1160 : Matcher<T>(Implementation) {} 1161 1162 /// \brief Returns a matcher that will bind the matched node on a match. 1163 /// 1164 /// The returned matcher is equivalent to this matcher, but will 1165 /// bind the matched node on a match. 1166 Matcher<T> bind(StringRef ID) const { 1167 return DynTypedMatcher(*this) 1168 .tryBind(ID) 1169 ->template unconditionalConvertTo<T>(); 1170 } 1171 1172 /// \brief Same as Matcher<T>'s conversion operator, but enables binding on 1173 /// the returned matcher. 1174 operator DynTypedMatcher() const { 1175 DynTypedMatcher Result = static_cast<const Matcher<T>&>(*this); 1176 Result.setAllowBind(true); 1177 return Result; 1178 } 1179 }; 1180 1181 /// \brief Matches nodes of type T that have child nodes of type ChildT for 1182 /// which a specified child matcher matches. 1183 /// 1184 /// ChildT must be an AST base type. 1185 template <typename T, typename ChildT> 1186 class HasMatcher : public WrapperMatcherInterface<T> { 1187 1188 public: 1189 explicit HasMatcher(const Matcher<ChildT> &ChildMatcher) 1190 : HasMatcher::WrapperMatcherInterface(ChildMatcher) {} 1191 1192 bool matches(const T &Node, ASTMatchFinder *Finder, 1193 BoundNodesTreeBuilder *Builder) const override { 1194 return Finder->matchesChildOf(Node, this->InnerMatcher, Builder, 1195 ASTMatchFinder::TK_AsIs, 1196 ASTMatchFinder::BK_First); 1197 } 1198 }; 1199 1200 /// \brief Matches nodes of type T that have child nodes of type ChildT for 1201 /// which a specified child matcher matches. ChildT must be an AST base 1202 /// type. 1203 /// As opposed to the HasMatcher, the ForEachMatcher will produce a match 1204 /// for each child that matches. 1205 template <typename T, typename ChildT> 1206 class ForEachMatcher : public WrapperMatcherInterface<T> { 1207 static_assert(IsBaseType<ChildT>::value, 1208 "for each only accepts base type matcher"); 1209 1210 public: 1211 explicit ForEachMatcher(const Matcher<ChildT> &ChildMatcher) 1212 : ForEachMatcher::WrapperMatcherInterface(ChildMatcher) {} 1213 1214 bool matches(const T& Node, ASTMatchFinder* Finder, 1215 BoundNodesTreeBuilder* Builder) const override { 1216 return Finder->matchesChildOf( 1217 Node, this->InnerMatcher, Builder, 1218 ASTMatchFinder::TK_IgnoreImplicitCastsAndParentheses, 1219 ASTMatchFinder::BK_All); 1220 } 1221 }; 1222 1223 /// \brief VariadicOperatorMatcher related types. 1224 /// @{ 1225 1226 /// \brief Polymorphic matcher object that uses a \c 1227 /// DynTypedMatcher::VariadicOperator operator. 1228 /// 1229 /// Input matchers can have any type (including other polymorphic matcher 1230 /// types), and the actual Matcher<T> is generated on demand with an implicit 1231 /// coversion operator. 1232 template <typename... Ps> class VariadicOperatorMatcher { 1233 public: 1234 VariadicOperatorMatcher(DynTypedMatcher::VariadicOperator Op, Ps &&... Params) 1235 : Op(Op), Params(std::forward<Ps>(Params)...) {} 1236 1237 template <typename T> operator Matcher<T>() const { 1238 return DynTypedMatcher::constructVariadic( 1239 Op, ast_type_traits::ASTNodeKind::getFromNodeKind<T>(), 1240 getMatchers<T>(llvm::index_sequence_for<Ps...>())) 1241 .template unconditionalConvertTo<T>(); 1242 } 1243 1244 private: 1245 // Helper method to unpack the tuple into a vector. 1246 template <typename T, std::size_t... Is> 1247 std::vector<DynTypedMatcher> getMatchers(llvm::index_sequence<Is...>) const { 1248 return {Matcher<T>(std::get<Is>(Params))...}; 1249 } 1250 1251 const DynTypedMatcher::VariadicOperator Op; 1252 std::tuple<Ps...> Params; 1253 }; 1254 1255 /// \brief Overloaded function object to generate VariadicOperatorMatcher 1256 /// objects from arbitrary matchers. 1257 template <unsigned MinCount, unsigned MaxCount> 1258 struct VariadicOperatorMatcherFunc { 1259 DynTypedMatcher::VariadicOperator Op; 1260 1261 template <typename... Ms> 1262 VariadicOperatorMatcher<Ms...> operator()(Ms &&... Ps) const { 1263 static_assert(MinCount <= sizeof...(Ms) && sizeof...(Ms) <= MaxCount, 1264 "invalid number of parameters for variadic matcher"); 1265 return VariadicOperatorMatcher<Ms...>(Op, std::forward<Ms>(Ps)...); 1266 } 1267 }; 1268 1269 /// @} 1270 1271 template <typename T> 1272 inline Matcher<T> DynTypedMatcher::unconditionalConvertTo() const { 1273 return Matcher<T>(*this); 1274 } 1275 1276 /// \brief Creates a Matcher<T> that matches if all inner matchers match. 1277 template<typename T> 1278 BindableMatcher<T> makeAllOfComposite( 1279 ArrayRef<const Matcher<T> *> InnerMatchers) { 1280 // For the size() == 0 case, we return a "true" matcher. 1281 if (InnerMatchers.size() == 0) { 1282 return BindableMatcher<T>(TrueMatcher()); 1283 } 1284 // For the size() == 1 case, we simply return that one matcher. 1285 // No need to wrap it in a variadic operation. 1286 if (InnerMatchers.size() == 1) { 1287 return BindableMatcher<T>(*InnerMatchers[0]); 1288 } 1289 1290 typedef llvm::pointee_iterator<const Matcher<T> *const *> PI; 1291 std::vector<DynTypedMatcher> DynMatchers(PI(InnerMatchers.begin()), 1292 PI(InnerMatchers.end())); 1293 return BindableMatcher<T>( 1294 DynTypedMatcher::constructVariadic( 1295 DynTypedMatcher::VO_AllOf, 1296 ast_type_traits::ASTNodeKind::getFromNodeKind<T>(), 1297 std::move(DynMatchers)) 1298 .template unconditionalConvertTo<T>()); 1299 } 1300 1301 /// \brief Creates a Matcher<T> that matches if 1302 /// T is dyn_cast'able into InnerT and all inner matchers match. 1303 /// 1304 /// Returns BindableMatcher, as matchers that use dyn_cast have 1305 /// the same object both to match on and to run submatchers on, 1306 /// so there is no ambiguity with what gets bound. 1307 template<typename T, typename InnerT> 1308 BindableMatcher<T> makeDynCastAllOfComposite( 1309 ArrayRef<const Matcher<InnerT> *> InnerMatchers) { 1310 return BindableMatcher<T>( 1311 makeAllOfComposite(InnerMatchers).template dynCastTo<T>()); 1312 } 1313 1314 /// \brief Matches nodes of type T that have at least one descendant node of 1315 /// type DescendantT for which the given inner matcher matches. 1316 /// 1317 /// DescendantT must be an AST base type. 1318 template <typename T, typename DescendantT> 1319 class HasDescendantMatcher : public WrapperMatcherInterface<T> { 1320 static_assert(IsBaseType<DescendantT>::value, 1321 "has descendant only accepts base type matcher"); 1322 1323 public: 1324 explicit HasDescendantMatcher(const Matcher<DescendantT> &DescendantMatcher) 1325 : HasDescendantMatcher::WrapperMatcherInterface(DescendantMatcher) {} 1326 1327 bool matches(const T &Node, ASTMatchFinder *Finder, 1328 BoundNodesTreeBuilder *Builder) const override { 1329 return Finder->matchesDescendantOf(Node, this->InnerMatcher, Builder, 1330 ASTMatchFinder::BK_First); 1331 } 1332 }; 1333 1334 /// \brief Matches nodes of type \c T that have a parent node of type \c ParentT 1335 /// for which the given inner matcher matches. 1336 /// 1337 /// \c ParentT must be an AST base type. 1338 template <typename T, typename ParentT> 1339 class HasParentMatcher : public WrapperMatcherInterface<T> { 1340 static_assert(IsBaseType<ParentT>::value, 1341 "has parent only accepts base type matcher"); 1342 1343 public: 1344 explicit HasParentMatcher(const Matcher<ParentT> &ParentMatcher) 1345 : HasParentMatcher::WrapperMatcherInterface(ParentMatcher) {} 1346 1347 bool matches(const T &Node, ASTMatchFinder *Finder, 1348 BoundNodesTreeBuilder *Builder) const override { 1349 return Finder->matchesAncestorOf(Node, this->InnerMatcher, Builder, 1350 ASTMatchFinder::AMM_ParentOnly); 1351 } 1352 }; 1353 1354 /// \brief Matches nodes of type \c T that have at least one ancestor node of 1355 /// type \c AncestorT for which the given inner matcher matches. 1356 /// 1357 /// \c AncestorT must be an AST base type. 1358 template <typename T, typename AncestorT> 1359 class HasAncestorMatcher : public WrapperMatcherInterface<T> { 1360 static_assert(IsBaseType<AncestorT>::value, 1361 "has ancestor only accepts base type matcher"); 1362 1363 public: 1364 explicit HasAncestorMatcher(const Matcher<AncestorT> &AncestorMatcher) 1365 : HasAncestorMatcher::WrapperMatcherInterface(AncestorMatcher) {} 1366 1367 bool matches(const T &Node, ASTMatchFinder *Finder, 1368 BoundNodesTreeBuilder *Builder) const override { 1369 return Finder->matchesAncestorOf(Node, this->InnerMatcher, Builder, 1370 ASTMatchFinder::AMM_All); 1371 } 1372 }; 1373 1374 /// \brief Matches nodes of type T that have at least one descendant node of 1375 /// type DescendantT for which the given inner matcher matches. 1376 /// 1377 /// DescendantT must be an AST base type. 1378 /// As opposed to HasDescendantMatcher, ForEachDescendantMatcher will match 1379 /// for each descendant node that matches instead of only for the first. 1380 template <typename T, typename DescendantT> 1381 class ForEachDescendantMatcher : public WrapperMatcherInterface<T> { 1382 static_assert(IsBaseType<DescendantT>::value, 1383 "for each descendant only accepts base type matcher"); 1384 1385 public: 1386 explicit ForEachDescendantMatcher( 1387 const Matcher<DescendantT> &DescendantMatcher) 1388 : ForEachDescendantMatcher::WrapperMatcherInterface(DescendantMatcher) {} 1389 1390 bool matches(const T &Node, ASTMatchFinder *Finder, 1391 BoundNodesTreeBuilder *Builder) const override { 1392 return Finder->matchesDescendantOf(Node, this->InnerMatcher, Builder, 1393 ASTMatchFinder::BK_All); 1394 } 1395 }; 1396 1397 /// \brief Matches on nodes that have a getValue() method if getValue() equals 1398 /// the value the ValueEqualsMatcher was constructed with. 1399 template <typename T, typename ValueT> 1400 class ValueEqualsMatcher : public SingleNodeMatcherInterface<T> { 1401 static_assert(std::is_base_of<CharacterLiteral, T>::value || 1402 std::is_base_of<CXXBoolLiteralExpr, T>::value || 1403 std::is_base_of<FloatingLiteral, T>::value || 1404 std::is_base_of<IntegerLiteral, T>::value, 1405 "the node must have a getValue method"); 1406 1407 public: 1408 explicit ValueEqualsMatcher(const ValueT &ExpectedValue) 1409 : ExpectedValue(ExpectedValue) {} 1410 1411 bool matchesNode(const T &Node) const override { 1412 return Node.getValue() == ExpectedValue; 1413 } 1414 1415 private: 1416 const ValueT ExpectedValue; 1417 }; 1418 1419 /// \brief Template specializations to easily write matchers for floating point 1420 /// literals. 1421 template <> 1422 inline bool ValueEqualsMatcher<FloatingLiteral, double>::matchesNode( 1423 const FloatingLiteral &Node) const { 1424 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle()) 1425 return Node.getValue().convertToFloat() == ExpectedValue; 1426 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble()) 1427 return Node.getValue().convertToDouble() == ExpectedValue; 1428 return false; 1429 } 1430 template <> 1431 inline bool ValueEqualsMatcher<FloatingLiteral, float>::matchesNode( 1432 const FloatingLiteral &Node) const { 1433 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle()) 1434 return Node.getValue().convertToFloat() == ExpectedValue; 1435 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble()) 1436 return Node.getValue().convertToDouble() == ExpectedValue; 1437 return false; 1438 } 1439 template <> 1440 inline bool ValueEqualsMatcher<FloatingLiteral, llvm::APFloat>::matchesNode( 1441 const FloatingLiteral &Node) const { 1442 return ExpectedValue.compare(Node.getValue()) == llvm::APFloat::cmpEqual; 1443 } 1444 1445 /// \brief A VariadicDynCastAllOfMatcher<SourceT, TargetT> object is a 1446 /// variadic functor that takes a number of Matcher<TargetT> and returns a 1447 /// Matcher<SourceT> that matches TargetT nodes that are matched by all of the 1448 /// given matchers, if SourceT can be dynamically casted into TargetT. 1449 /// 1450 /// For example: 1451 /// const VariadicDynCastAllOfMatcher< 1452 /// Decl, CXXRecordDecl> record; 1453 /// Creates a functor record(...) that creates a Matcher<Decl> given 1454 /// a variable number of arguments of type Matcher<CXXRecordDecl>. 1455 /// The returned matcher matches if the given Decl can by dynamically 1456 /// casted to CXXRecordDecl and all given matchers match. 1457 template <typename SourceT, typename TargetT> 1458 class VariadicDynCastAllOfMatcher 1459 : public VariadicFunction<BindableMatcher<SourceT>, Matcher<TargetT>, 1460 makeDynCastAllOfComposite<SourceT, TargetT>> { 1461 public: 1462 VariadicDynCastAllOfMatcher() {} 1463 }; 1464 1465 /// \brief A \c VariadicAllOfMatcher<T> object is a variadic functor that takes 1466 /// a number of \c Matcher<T> and returns a \c Matcher<T> that matches \c T 1467 /// nodes that are matched by all of the given matchers. 1468 /// 1469 /// For example: 1470 /// const VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier; 1471 /// Creates a functor nestedNameSpecifier(...) that creates a 1472 /// \c Matcher<NestedNameSpecifier> given a variable number of arguments of type 1473 /// \c Matcher<NestedNameSpecifier>. 1474 /// The returned matcher matches if all given matchers match. 1475 template <typename T> 1476 class VariadicAllOfMatcher 1477 : public VariadicFunction<BindableMatcher<T>, Matcher<T>, 1478 makeAllOfComposite<T>> { 1479 public: 1480 VariadicAllOfMatcher() {} 1481 }; 1482 1483 /// \brief Matches nodes of type \c TLoc for which the inner 1484 /// \c Matcher<T> matches. 1485 template <typename TLoc, typename T> 1486 class LocMatcher : public WrapperMatcherInterface<TLoc> { 1487 public: 1488 explicit LocMatcher(const Matcher<T> &InnerMatcher) 1489 : LocMatcher::WrapperMatcherInterface(InnerMatcher) {} 1490 1491 bool matches(const TLoc &Node, ASTMatchFinder *Finder, 1492 BoundNodesTreeBuilder *Builder) const override { 1493 if (!Node) 1494 return false; 1495 return this->InnerMatcher.matches(extract(Node), Finder, Builder); 1496 } 1497 1498 private: 1499 static ast_type_traits::DynTypedNode 1500 extract(const NestedNameSpecifierLoc &Loc) { 1501 return ast_type_traits::DynTypedNode::create(*Loc.getNestedNameSpecifier()); 1502 } 1503 }; 1504 1505 /// \brief Matches \c TypeLocs based on an inner matcher matching a certain 1506 /// \c QualType. 1507 /// 1508 /// Used to implement the \c loc() matcher. 1509 class TypeLocTypeMatcher : public WrapperMatcherInterface<TypeLoc> { 1510 public: 1511 explicit TypeLocTypeMatcher(const Matcher<QualType> &InnerMatcher) 1512 : TypeLocTypeMatcher::WrapperMatcherInterface(InnerMatcher) {} 1513 1514 bool matches(const TypeLoc &Node, ASTMatchFinder *Finder, 1515 BoundNodesTreeBuilder *Builder) const override { 1516 if (!Node) 1517 return false; 1518 return this->InnerMatcher.matches( 1519 ast_type_traits::DynTypedNode::create(Node.getType()), Finder, Builder); 1520 } 1521 }; 1522 1523 /// \brief Matches nodes of type \c T for which the inner matcher matches on a 1524 /// another node of type \c T that can be reached using a given traverse 1525 /// function. 1526 template <typename T> 1527 class TypeTraverseMatcher : public WrapperMatcherInterface<T> { 1528 public: 1529 explicit TypeTraverseMatcher(const Matcher<QualType> &InnerMatcher, 1530 QualType (T::*TraverseFunction)() const) 1531 : TypeTraverseMatcher::WrapperMatcherInterface(InnerMatcher), 1532 TraverseFunction(TraverseFunction) {} 1533 1534 bool matches(const T &Node, ASTMatchFinder *Finder, 1535 BoundNodesTreeBuilder *Builder) const override { 1536 QualType NextNode = (Node.*TraverseFunction)(); 1537 if (NextNode.isNull()) 1538 return false; 1539 return this->InnerMatcher.matches( 1540 ast_type_traits::DynTypedNode::create(NextNode), Finder, Builder); 1541 } 1542 1543 private: 1544 QualType (T::*TraverseFunction)() const; 1545 }; 1546 1547 /// \brief Matches nodes of type \c T in a ..Loc hierarchy, for which the inner 1548 /// matcher matches on a another node of type \c T that can be reached using a 1549 /// given traverse function. 1550 template <typename T> 1551 class TypeLocTraverseMatcher : public WrapperMatcherInterface<T> { 1552 public: 1553 explicit TypeLocTraverseMatcher(const Matcher<TypeLoc> &InnerMatcher, 1554 TypeLoc (T::*TraverseFunction)() const) 1555 : TypeLocTraverseMatcher::WrapperMatcherInterface(InnerMatcher), 1556 TraverseFunction(TraverseFunction) {} 1557 1558 bool matches(const T &Node, ASTMatchFinder *Finder, 1559 BoundNodesTreeBuilder *Builder) const override { 1560 TypeLoc NextNode = (Node.*TraverseFunction)(); 1561 if (!NextNode) 1562 return false; 1563 return this->InnerMatcher.matches( 1564 ast_type_traits::DynTypedNode::create(NextNode), Finder, Builder); 1565 } 1566 1567 private: 1568 TypeLoc (T::*TraverseFunction)() const; 1569 }; 1570 1571 /// \brief Converts a \c Matcher<InnerT> to a \c Matcher<OuterT>, where 1572 /// \c OuterT is any type that is supported by \c Getter. 1573 /// 1574 /// \code Getter<OuterT>::value() \endcode returns a 1575 /// \code InnerTBase (OuterT::*)() \endcode, which is used to adapt a \c OuterT 1576 /// object into a \c InnerT 1577 template <typename InnerTBase, 1578 template <typename OuterT> class Getter, 1579 template <typename OuterT> class MatcherImpl, 1580 typename ReturnTypesF> 1581 class TypeTraversePolymorphicMatcher { 1582 private: 1583 typedef TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, 1584 ReturnTypesF> Self; 1585 static Self create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers); 1586 1587 public: 1588 typedef typename ExtractFunctionArgMeta<ReturnTypesF>::type ReturnTypes; 1589 1590 explicit TypeTraversePolymorphicMatcher( 1591 ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) 1592 : InnerMatcher(makeAllOfComposite(InnerMatchers)) {} 1593 1594 template <typename OuterT> operator Matcher<OuterT>() const { 1595 return Matcher<OuterT>( 1596 new MatcherImpl<OuterT>(InnerMatcher, Getter<OuterT>::value())); 1597 } 1598 1599 struct Func 1600 : public VariadicFunction<Self, Matcher<InnerTBase>, &Self::create> { 1601 Func() {} 1602 }; 1603 1604 private: 1605 const Matcher<InnerTBase> InnerMatcher; 1606 }; 1607 1608 /// \brief A simple memoizer of T(*)() functions. 1609 /// 1610 /// It will call the passed 'Func' template parameter at most once. 1611 /// Used to support AST_MATCHER_FUNCTION() macro. 1612 template <typename Matcher, Matcher (*Func)()> class MemoizedMatcher { 1613 struct Wrapper { 1614 Wrapper() : M(Func()) {} 1615 Matcher M; 1616 }; 1617 1618 public: 1619 static const Matcher &getInstance() { 1620 static llvm::ManagedStatic<Wrapper> Instance; 1621 return Instance->M; 1622 } 1623 }; 1624 1625 // Define the create() method out of line to silence a GCC warning about 1626 // the struct "Func" having greater visibility than its base, which comes from 1627 // using the flag -fvisibility-inlines-hidden. 1628 template <typename InnerTBase, template <typename OuterT> class Getter, 1629 template <typename OuterT> class MatcherImpl, typename ReturnTypesF> 1630 TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, ReturnTypesF> 1631 TypeTraversePolymorphicMatcher< 1632 InnerTBase, Getter, MatcherImpl, 1633 ReturnTypesF>::create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) { 1634 return Self(InnerMatchers); 1635 } 1636 1637 // FIXME: unify ClassTemplateSpecializationDecl and TemplateSpecializationType's 1638 // APIs for accessing the template argument list. 1639 inline ArrayRef<TemplateArgument> 1640 getTemplateSpecializationArgs(const ClassTemplateSpecializationDecl &D) { 1641 return D.getTemplateArgs().asArray(); 1642 } 1643 1644 inline ArrayRef<TemplateArgument> 1645 getTemplateSpecializationArgs(const TemplateSpecializationType &T) { 1646 return llvm::makeArrayRef(T.getArgs(), T.getNumArgs()); 1647 } 1648 1649 inline ArrayRef<TemplateArgument> 1650 getTemplateSpecializationArgs(const FunctionDecl &FD) { 1651 if (const auto* TemplateArgs = FD.getTemplateSpecializationArgs()) 1652 return TemplateArgs->asArray(); 1653 return ArrayRef<TemplateArgument>(); 1654 } 1655 1656 struct NotEqualsBoundNodePredicate { 1657 bool operator()(const internal::BoundNodesMap &Nodes) const { 1658 return Nodes.getNode(ID) != Node; 1659 } 1660 std::string ID; 1661 ast_type_traits::DynTypedNode Node; 1662 }; 1663 1664 template <typename Ty> 1665 struct GetBodyMatcher { 1666 static const Stmt *get(const Ty &Node) { 1667 return Node.getBody(); 1668 } 1669 }; 1670 1671 template <> 1672 inline const Stmt *GetBodyMatcher<FunctionDecl>::get(const FunctionDecl &Node) { 1673 return Node.doesThisDeclarationHaveABody() ? Node.getBody() : nullptr; 1674 } 1675 1676 template <typename Ty> 1677 struct HasSizeMatcher { 1678 static bool hasSize(const Ty &Node, unsigned int N) { 1679 return Node.getSize() == N; 1680 } 1681 }; 1682 1683 template <> 1684 inline bool HasSizeMatcher<StringLiteral>::hasSize( 1685 const StringLiteral &Node, unsigned int N) { 1686 return Node.getLength() == N; 1687 } 1688 1689 template <typename Ty> 1690 struct GetSourceExpressionMatcher { 1691 static const Expr *get(const Ty &Node) { 1692 return Node.getSubExpr(); 1693 } 1694 }; 1695 1696 template <> 1697 inline const Expr *GetSourceExpressionMatcher<OpaqueValueExpr>::get( 1698 const OpaqueValueExpr &Node) { 1699 return Node.getSourceExpr(); 1700 } 1701 1702 template <typename Ty> 1703 struct CompoundStmtMatcher { 1704 static const CompoundStmt *get(const Ty &Node) { 1705 return &Node; 1706 } 1707 }; 1708 1709 template <> 1710 inline const CompoundStmt * 1711 CompoundStmtMatcher<StmtExpr>::get(const StmtExpr &Node) { 1712 return Node.getSubStmt(); 1713 } 1714 1715 1716 } // end namespace internal 1717 } // end namespace ast_matchers 1718 } // end namespace clang 1719 1720 #endif // LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H 1721