1 //===- ASTMatchersInternal.h - Structural query framework -------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Implements the base layer of the matcher framework. 10 // 11 // Matchers are methods that return a Matcher<T> which provides a method 12 // Matches(...) which is a predicate on an AST node. The Matches method's 13 // parameters define the context of the match, which allows matchers to recurse 14 // or store the current node as bound to a specific string, so that it can be 15 // retrieved later. 16 // 17 // In general, matchers have two parts: 18 // 1. A function Matcher<T> MatcherName(<arguments>) which returns a Matcher<T> 19 // based on the arguments and optionally on template type deduction based 20 // on the arguments. Matcher<T>s form an implicit reverse hierarchy 21 // to clang's AST class hierarchy, meaning that you can use a Matcher<Base> 22 // everywhere a Matcher<Derived> is required. 23 // 2. An implementation of a class derived from MatcherInterface<T>. 24 // 25 // The matcher functions are defined in ASTMatchers.h. To make it possible 26 // to implement both the matcher function and the implementation of the matcher 27 // interface in one place, ASTMatcherMacros.h defines macros that allow 28 // implementing a matcher in a single place. 29 // 30 // This file contains the base classes needed to construct the actual matchers. 31 // 32 //===----------------------------------------------------------------------===// 33 34 #ifndef LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H 35 #define LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H 36 37 #include "clang/AST/ASTTypeTraits.h" 38 #include "clang/AST/Decl.h" 39 #include "clang/AST/DeclCXX.h" 40 #include "clang/AST/DeclFriend.h" 41 #include "clang/AST/DeclTemplate.h" 42 #include "clang/AST/Expr.h" 43 #include "clang/AST/ExprCXX.h" 44 #include "clang/AST/ExprObjC.h" 45 #include "clang/AST/NestedNameSpecifier.h" 46 #include "clang/AST/Stmt.h" 47 #include "clang/AST/TemplateName.h" 48 #include "clang/AST/Type.h" 49 #include "clang/AST/TypeLoc.h" 50 #include "clang/Basic/LLVM.h" 51 #include "clang/Basic/OperatorKinds.h" 52 #include "llvm/ADT/APFloat.h" 53 #include "llvm/ADT/ArrayRef.h" 54 #include "llvm/ADT/IntrusiveRefCntPtr.h" 55 #include "llvm/ADT/None.h" 56 #include "llvm/ADT/Optional.h" 57 #include "llvm/ADT/STLExtras.h" 58 #include "llvm/ADT/SmallVector.h" 59 #include "llvm/ADT/StringRef.h" 60 #include "llvm/ADT/iterator.h" 61 #include "llvm/Support/Casting.h" 62 #include "llvm/Support/ManagedStatic.h" 63 #include "llvm/Support/Regex.h" 64 #include <algorithm> 65 #include <cassert> 66 #include <cstddef> 67 #include <cstdint> 68 #include <map> 69 #include <memory> 70 #include <string> 71 #include <tuple> 72 #include <type_traits> 73 #include <utility> 74 #include <vector> 75 76 namespace clang { 77 78 class ASTContext; 79 80 namespace ast_matchers { 81 82 class BoundNodes; 83 84 namespace internal { 85 86 /// A type-list implementation. 87 /// 88 /// A "linked list" of types, accessible by using the ::head and ::tail 89 /// typedefs. 90 template <typename... Ts> struct TypeList {}; // Empty sentinel type list. 91 92 template <typename T1, typename... Ts> struct TypeList<T1, Ts...> { 93 /// The first type on the list. 94 using head = T1; 95 96 /// A sublist with the tail. ie everything but the head. 97 /// 98 /// This type is used to do recursion. TypeList<>/EmptyTypeList indicates the 99 /// end of the list. 100 using tail = TypeList<Ts...>; 101 }; 102 103 /// The empty type list. 104 using EmptyTypeList = TypeList<>; 105 106 /// Helper meta-function to determine if some type \c T is present or 107 /// a parent type in the list. 108 template <typename AnyTypeList, typename T> struct TypeListContainsSuperOf { 109 static const bool value = 110 std::is_base_of<typename AnyTypeList::head, T>::value || 111 TypeListContainsSuperOf<typename AnyTypeList::tail, T>::value; 112 }; 113 template <typename T> struct TypeListContainsSuperOf<EmptyTypeList, T> { 114 static const bool value = false; 115 }; 116 117 /// Variadic function object. 118 /// 119 /// Most of the functions below that use VariadicFunction could be implemented 120 /// using plain C++11 variadic functions, but the function object allows us to 121 /// capture it on the dynamic matcher registry. 122 template <typename ResultT, typename ArgT, 123 ResultT (*Func)(ArrayRef<const ArgT *>)> 124 struct VariadicFunction { 125 ResultT operator()() const { return Func(None); } 126 127 template <typename... ArgsT> 128 ResultT operator()(const ArgT &Arg1, const ArgsT &... Args) const { 129 return Execute(Arg1, static_cast<const ArgT &>(Args)...); 130 } 131 132 // We also allow calls with an already created array, in case the caller 133 // already had it. 134 ResultT operator()(ArrayRef<ArgT> Args) const { 135 SmallVector<const ArgT*, 8> InnerArgs; 136 for (const ArgT &Arg : Args) 137 InnerArgs.push_back(&Arg); 138 return Func(InnerArgs); 139 } 140 141 private: 142 // Trampoline function to allow for implicit conversions to take place 143 // before we make the array. 144 template <typename... ArgsT> ResultT Execute(const ArgsT &... Args) const { 145 const ArgT *const ArgsArray[] = {&Args...}; 146 return Func(ArrayRef<const ArgT *>(ArgsArray, sizeof...(ArgsT))); 147 } 148 }; 149 150 /// Unifies obtaining the underlying type of a regular node through 151 /// `getType` and a TypedefNameDecl node through `getUnderlyingType`. 152 inline QualType getUnderlyingType(const Expr &Node) { return Node.getType(); } 153 154 inline QualType getUnderlyingType(const ValueDecl &Node) { 155 return Node.getType(); 156 } 157 inline QualType getUnderlyingType(const TypedefNameDecl &Node) { 158 return Node.getUnderlyingType(); 159 } 160 inline QualType getUnderlyingType(const FriendDecl &Node) { 161 if (const TypeSourceInfo *TSI = Node.getFriendType()) 162 return TSI->getType(); 163 return QualType(); 164 } 165 inline QualType getUnderlyingType(const CXXBaseSpecifier &Node) { 166 return Node.getType(); 167 } 168 169 /// Unifies obtaining a `TypeSourceInfo` from different node types. 170 template <typename T, 171 std::enable_if_t<TypeListContainsSuperOf< 172 TypeList<CXXBaseSpecifier, CXXCtorInitializer, 173 CXXTemporaryObjectExpr, CXXUnresolvedConstructExpr, 174 CompoundLiteralExpr, DeclaratorDecl, ObjCPropertyDecl, 175 TemplateArgumentLoc, TypedefNameDecl>, 176 T>::value> * = nullptr> 177 inline TypeSourceInfo *GetTypeSourceInfo(const T &Node) { 178 return Node.getTypeSourceInfo(); 179 } 180 template <typename T, 181 std::enable_if_t<TypeListContainsSuperOf< 182 TypeList<CXXFunctionalCastExpr, ExplicitCastExpr>, T>::value> * = 183 nullptr> 184 inline TypeSourceInfo *GetTypeSourceInfo(const T &Node) { 185 return Node.getTypeInfoAsWritten(); 186 } 187 inline TypeSourceInfo *GetTypeSourceInfo(const BlockDecl &Node) { 188 return Node.getSignatureAsWritten(); 189 } 190 inline TypeSourceInfo *GetTypeSourceInfo(const CXXNewExpr &Node) { 191 return Node.getAllocatedTypeSourceInfo(); 192 } 193 inline TypeSourceInfo * 194 GetTypeSourceInfo(const ClassTemplateSpecializationDecl &Node) { 195 return Node.getTypeAsWritten(); 196 } 197 198 /// Unifies obtaining the FunctionProtoType pointer from both 199 /// FunctionProtoType and FunctionDecl nodes.. 200 inline const FunctionProtoType * 201 getFunctionProtoType(const FunctionProtoType &Node) { 202 return &Node; 203 } 204 205 inline const FunctionProtoType *getFunctionProtoType(const FunctionDecl &Node) { 206 return Node.getType()->getAs<FunctionProtoType>(); 207 } 208 209 /// Unifies obtaining the access specifier from Decl and CXXBaseSpecifier nodes. 210 inline clang::AccessSpecifier getAccessSpecifier(const Decl &Node) { 211 return Node.getAccess(); 212 } 213 214 inline clang::AccessSpecifier getAccessSpecifier(const CXXBaseSpecifier &Node) { 215 return Node.getAccessSpecifier(); 216 } 217 218 /// Internal version of BoundNodes. Holds all the bound nodes. 219 class BoundNodesMap { 220 public: 221 /// Adds \c Node to the map with key \c ID. 222 /// 223 /// The node's base type should be in NodeBaseType or it will be unaccessible. 224 void addNode(StringRef ID, const DynTypedNode &DynNode) { 225 NodeMap[std::string(ID)] = DynNode; 226 } 227 228 /// Returns the AST node bound to \c ID. 229 /// 230 /// Returns NULL if there was no node bound to \c ID or if there is a node but 231 /// it cannot be converted to the specified type. 232 template <typename T> 233 const T *getNodeAs(StringRef ID) const { 234 IDToNodeMap::const_iterator It = NodeMap.find(ID); 235 if (It == NodeMap.end()) { 236 return nullptr; 237 } 238 return It->second.get<T>(); 239 } 240 241 DynTypedNode getNode(StringRef ID) const { 242 IDToNodeMap::const_iterator It = NodeMap.find(ID); 243 if (It == NodeMap.end()) { 244 return DynTypedNode(); 245 } 246 return It->second; 247 } 248 249 /// Imposes an order on BoundNodesMaps. 250 bool operator<(const BoundNodesMap &Other) const { 251 return NodeMap < Other.NodeMap; 252 } 253 254 /// A map from IDs to the bound nodes. 255 /// 256 /// Note that we're using std::map here, as for memoization: 257 /// - we need a comparison operator 258 /// - we need an assignment operator 259 using IDToNodeMap = std::map<std::string, DynTypedNode, std::less<>>; 260 261 const IDToNodeMap &getMap() const { 262 return NodeMap; 263 } 264 265 /// Returns \c true if this \c BoundNodesMap can be compared, i.e. all 266 /// stored nodes have memoization data. 267 bool isComparable() const { 268 for (const auto &IDAndNode : NodeMap) { 269 if (!IDAndNode.second.getMemoizationData()) 270 return false; 271 } 272 return true; 273 } 274 275 private: 276 IDToNodeMap NodeMap; 277 }; 278 279 /// Creates BoundNodesTree objects. 280 /// 281 /// The tree builder is used during the matching process to insert the bound 282 /// nodes from the Id matcher. 283 class BoundNodesTreeBuilder { 284 public: 285 /// A visitor interface to visit all BoundNodes results for a 286 /// BoundNodesTree. 287 class Visitor { 288 public: 289 virtual ~Visitor() = default; 290 291 /// Called multiple times during a single call to VisitMatches(...). 292 /// 293 /// 'BoundNodesView' contains the bound nodes for a single match. 294 virtual void visitMatch(const BoundNodes& BoundNodesView) = 0; 295 }; 296 297 /// Add a binding from an id to a node. 298 void setBinding(StringRef Id, const DynTypedNode &DynNode) { 299 if (Bindings.empty()) 300 Bindings.emplace_back(); 301 for (BoundNodesMap &Binding : Bindings) 302 Binding.addNode(Id, DynNode); 303 } 304 305 /// Adds a branch in the tree. 306 void addMatch(const BoundNodesTreeBuilder &Bindings); 307 308 /// Visits all matches that this BoundNodesTree represents. 309 /// 310 /// The ownership of 'ResultVisitor' remains at the caller. 311 void visitMatches(Visitor* ResultVisitor); 312 313 template <typename ExcludePredicate> 314 bool removeBindings(const ExcludePredicate &Predicate) { 315 Bindings.erase(std::remove_if(Bindings.begin(), Bindings.end(), Predicate), 316 Bindings.end()); 317 return !Bindings.empty(); 318 } 319 320 /// Imposes an order on BoundNodesTreeBuilders. 321 bool operator<(const BoundNodesTreeBuilder &Other) const { 322 return Bindings < Other.Bindings; 323 } 324 325 /// Returns \c true if this \c BoundNodesTreeBuilder can be compared, 326 /// i.e. all stored node maps have memoization data. 327 bool isComparable() const { 328 for (const BoundNodesMap &NodesMap : Bindings) { 329 if (!NodesMap.isComparable()) 330 return false; 331 } 332 return true; 333 } 334 335 private: 336 SmallVector<BoundNodesMap, 1> Bindings; 337 }; 338 339 class ASTMatchFinder; 340 341 /// Generic interface for all matchers. 342 /// 343 /// Used by the implementation of Matcher<T> and DynTypedMatcher. 344 /// In general, implement MatcherInterface<T> or SingleNodeMatcherInterface<T> 345 /// instead. 346 class DynMatcherInterface 347 : public llvm::ThreadSafeRefCountedBase<DynMatcherInterface> { 348 public: 349 virtual ~DynMatcherInterface() = default; 350 351 /// Returns true if \p DynNode can be matched. 352 /// 353 /// May bind \p DynNode to an ID via \p Builder, or recurse into 354 /// the AST via \p Finder. 355 virtual bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder, 356 BoundNodesTreeBuilder *Builder) const = 0; 357 358 virtual llvm::Optional<clang::TraversalKind> TraversalKind() const { 359 return llvm::None; 360 } 361 }; 362 363 /// Generic interface for matchers on an AST node of type T. 364 /// 365 /// Implement this if your matcher may need to inspect the children or 366 /// descendants of the node or bind matched nodes to names. If you are 367 /// writing a simple matcher that only inspects properties of the 368 /// current node and doesn't care about its children or descendants, 369 /// implement SingleNodeMatcherInterface instead. 370 template <typename T> 371 class MatcherInterface : public DynMatcherInterface { 372 public: 373 /// Returns true if 'Node' can be matched. 374 /// 375 /// May bind 'Node' to an ID via 'Builder', or recurse into 376 /// the AST via 'Finder'. 377 virtual bool matches(const T &Node, 378 ASTMatchFinder *Finder, 379 BoundNodesTreeBuilder *Builder) const = 0; 380 381 bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder, 382 BoundNodesTreeBuilder *Builder) const override { 383 return matches(DynNode.getUnchecked<T>(), Finder, Builder); 384 } 385 }; 386 387 /// Interface for matchers that only evaluate properties on a single 388 /// node. 389 template <typename T> 390 class SingleNodeMatcherInterface : public MatcherInterface<T> { 391 public: 392 /// Returns true if the matcher matches the provided node. 393 /// 394 /// A subclass must implement this instead of Matches(). 395 virtual bool matchesNode(const T &Node) const = 0; 396 397 private: 398 /// Implements MatcherInterface::Matches. 399 bool matches(const T &Node, 400 ASTMatchFinder * /* Finder */, 401 BoundNodesTreeBuilder * /* Builder */) const override { 402 return matchesNode(Node); 403 } 404 }; 405 406 template <typename> class Matcher; 407 408 /// Matcher that works on a \c DynTypedNode. 409 /// 410 /// It is constructed from a \c Matcher<T> object and redirects most calls to 411 /// underlying matcher. 412 /// It checks whether the \c DynTypedNode is convertible into the type of the 413 /// underlying matcher and then do the actual match on the actual node, or 414 /// return false if it is not convertible. 415 class DynTypedMatcher { 416 public: 417 /// Takes ownership of the provided implementation pointer. 418 template <typename T> 419 DynTypedMatcher(MatcherInterface<T> *Implementation) 420 : SupportedKind(ASTNodeKind::getFromNodeKind<T>()), 421 RestrictKind(SupportedKind), Implementation(Implementation) {} 422 423 /// Construct from a variadic function. 424 enum VariadicOperator { 425 /// Matches nodes for which all provided matchers match. 426 VO_AllOf, 427 428 /// Matches nodes for which at least one of the provided matchers 429 /// matches. 430 VO_AnyOf, 431 432 /// Matches nodes for which at least one of the provided matchers 433 /// matches, but doesn't stop at the first match. 434 VO_EachOf, 435 436 /// Matches any node but executes all inner matchers to find result 437 /// bindings. 438 VO_Optionally, 439 440 /// Matches nodes that do not match the provided matcher. 441 /// 442 /// Uses the variadic matcher interface, but fails if 443 /// InnerMatchers.size() != 1. 444 VO_UnaryNot 445 }; 446 447 static DynTypedMatcher 448 constructVariadic(VariadicOperator Op, ASTNodeKind SupportedKind, 449 std::vector<DynTypedMatcher> InnerMatchers); 450 451 static DynTypedMatcher 452 constructRestrictedWrapper(const DynTypedMatcher &InnerMatcher, 453 ASTNodeKind RestrictKind); 454 455 /// Get a "true" matcher for \p NodeKind. 456 /// 457 /// It only checks that the node is of the right kind. 458 static DynTypedMatcher trueMatcher(ASTNodeKind NodeKind); 459 460 void setAllowBind(bool AB) { AllowBind = AB; } 461 462 /// Check whether this matcher could ever match a node of kind \p Kind. 463 /// \return \c false if this matcher will never match such a node. Otherwise, 464 /// return \c true. 465 bool canMatchNodesOfKind(ASTNodeKind Kind) const; 466 467 /// Return a matcher that points to the same implementation, but 468 /// restricts the node types for \p Kind. 469 DynTypedMatcher dynCastTo(const ASTNodeKind Kind) const; 470 471 /// Return a matcher that that points to the same implementation, but sets the 472 /// traversal kind. 473 /// 474 /// If the traversal kind is already set, then \c TK overrides it. 475 DynTypedMatcher withTraversalKind(TraversalKind TK); 476 477 /// Returns true if the matcher matches the given \c DynNode. 478 bool matches(const DynTypedNode &DynNode, ASTMatchFinder *Finder, 479 BoundNodesTreeBuilder *Builder) const; 480 481 /// Same as matches(), but skips the kind check. 482 /// 483 /// It is faster, but the caller must ensure the node is valid for the 484 /// kind of this matcher. 485 bool matchesNoKindCheck(const DynTypedNode &DynNode, ASTMatchFinder *Finder, 486 BoundNodesTreeBuilder *Builder) const; 487 488 /// Bind the specified \p ID to the matcher. 489 /// \return A new matcher with the \p ID bound to it if this matcher supports 490 /// binding. Otherwise, returns an empty \c Optional<>. 491 llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const; 492 493 /// Returns a unique \p ID for the matcher. 494 /// 495 /// Casting a Matcher<T> to Matcher<U> creates a matcher that has the 496 /// same \c Implementation pointer, but different \c RestrictKind. We need to 497 /// include both in the ID to make it unique. 498 /// 499 /// \c MatcherIDType supports operator< and provides strict weak ordering. 500 using MatcherIDType = std::pair<ASTNodeKind, uint64_t>; 501 MatcherIDType getID() const { 502 /// FIXME: Document the requirements this imposes on matcher 503 /// implementations (no new() implementation_ during a Matches()). 504 return std::make_pair(RestrictKind, 505 reinterpret_cast<uint64_t>(Implementation.get())); 506 } 507 508 /// Returns the type this matcher works on. 509 /// 510 /// \c matches() will always return false unless the node passed is of this 511 /// or a derived type. 512 ASTNodeKind getSupportedKind() const { return SupportedKind; } 513 514 /// Returns \c true if the passed \c DynTypedMatcher can be converted 515 /// to a \c Matcher<T>. 516 /// 517 /// This method verifies that the underlying matcher in \c Other can process 518 /// nodes of types T. 519 template <typename T> bool canConvertTo() const { 520 return canConvertTo(ASTNodeKind::getFromNodeKind<T>()); 521 } 522 bool canConvertTo(ASTNodeKind To) const; 523 524 /// Construct a \c Matcher<T> interface around the dynamic matcher. 525 /// 526 /// This method asserts that \c canConvertTo() is \c true. Callers 527 /// should call \c canConvertTo() first to make sure that \c this is 528 /// compatible with T. 529 template <typename T> Matcher<T> convertTo() const { 530 assert(canConvertTo<T>()); 531 return unconditionalConvertTo<T>(); 532 } 533 534 /// Same as \c convertTo(), but does not check that the underlying 535 /// matcher can handle a value of T. 536 /// 537 /// If it is not compatible, then this matcher will never match anything. 538 template <typename T> Matcher<T> unconditionalConvertTo() const; 539 540 /// Returns the \c TraversalKind respected by calls to `match()`, if any. 541 /// 542 /// Most matchers will not have a traversal kind set, instead relying on the 543 /// surrounding context. For those, \c llvm::None is returned. 544 llvm::Optional<clang::TraversalKind> getTraversalKind() const { 545 return Implementation->TraversalKind(); 546 } 547 548 private: 549 DynTypedMatcher(ASTNodeKind SupportedKind, ASTNodeKind RestrictKind, 550 IntrusiveRefCntPtr<DynMatcherInterface> Implementation) 551 : SupportedKind(SupportedKind), RestrictKind(RestrictKind), 552 Implementation(std::move(Implementation)) {} 553 554 bool AllowBind = false; 555 ASTNodeKind SupportedKind; 556 557 /// A potentially stricter node kind. 558 /// 559 /// It allows to perform implicit and dynamic cast of matchers without 560 /// needing to change \c Implementation. 561 ASTNodeKind RestrictKind; 562 IntrusiveRefCntPtr<DynMatcherInterface> Implementation; 563 }; 564 565 /// Wrapper of a MatcherInterface<T> *that allows copying. 566 /// 567 /// A Matcher<Base> can be used anywhere a Matcher<Derived> is 568 /// required. This establishes an is-a relationship which is reverse 569 /// to the AST hierarchy. In other words, Matcher<T> is contravariant 570 /// with respect to T. The relationship is built via a type conversion 571 /// operator rather than a type hierarchy to be able to templatize the 572 /// type hierarchy instead of spelling it out. 573 template <typename T> 574 class Matcher { 575 public: 576 /// Takes ownership of the provided implementation pointer. 577 explicit Matcher(MatcherInterface<T> *Implementation) 578 : Implementation(Implementation) {} 579 580 /// Implicitly converts \c Other to a Matcher<T>. 581 /// 582 /// Requires \c T to be derived from \c From. 583 template <typename From> 584 Matcher(const Matcher<From> &Other, 585 std::enable_if_t<std::is_base_of<From, T>::value && 586 !std::is_same<From, T>::value> * = nullptr) 587 : Implementation(restrictMatcher(Other.Implementation)) { 588 assert(Implementation.getSupportedKind().isSame( 589 ASTNodeKind::getFromNodeKind<T>())); 590 } 591 592 /// Implicitly converts \c Matcher<Type> to \c Matcher<QualType>. 593 /// 594 /// The resulting matcher is not strict, i.e. ignores qualifiers. 595 template <typename TypeT> 596 Matcher(const Matcher<TypeT> &Other, 597 std::enable_if_t<std::is_same<T, QualType>::value && 598 std::is_same<TypeT, Type>::value> * = nullptr) 599 : Implementation(new TypeToQualType<TypeT>(Other)) {} 600 601 /// Convert \c this into a \c Matcher<T> by applying dyn_cast<> to the 602 /// argument. 603 /// \c To must be a base class of \c T. 604 template <typename To> Matcher<To> dynCastTo() const LLVM_LVALUE_FUNCTION { 605 static_assert(std::is_base_of<To, T>::value, "Invalid dynCast call."); 606 return Matcher<To>(Implementation); 607 } 608 609 #if LLVM_HAS_RVALUE_REFERENCE_THIS 610 template <typename To> Matcher<To> dynCastTo() && { 611 static_assert(std::is_base_of<To, T>::value, "Invalid dynCast call."); 612 return Matcher<To>(std::move(Implementation)); 613 } 614 #endif 615 616 /// Forwards the call to the underlying MatcherInterface<T> pointer. 617 bool matches(const T &Node, 618 ASTMatchFinder *Finder, 619 BoundNodesTreeBuilder *Builder) const { 620 return Implementation.matches(DynTypedNode::create(Node), Finder, Builder); 621 } 622 623 /// Returns an ID that uniquely identifies the matcher. 624 DynTypedMatcher::MatcherIDType getID() const { 625 return Implementation.getID(); 626 } 627 628 /// Extract the dynamic matcher. 629 /// 630 /// The returned matcher keeps the same restrictions as \c this and remembers 631 /// that it is meant to support nodes of type \c T. 632 operator DynTypedMatcher() const LLVM_LVALUE_FUNCTION { 633 return Implementation; 634 } 635 636 #if LLVM_HAS_RVALUE_REFERENCE_THIS 637 operator DynTypedMatcher() && { return std::move(Implementation); } 638 #endif 639 640 /// Allows the conversion of a \c Matcher<Type> to a \c 641 /// Matcher<QualType>. 642 /// 643 /// Depending on the constructor argument, the matcher is either strict, i.e. 644 /// does only matches in the absence of qualifiers, or not, i.e. simply 645 /// ignores any qualifiers. 646 template <typename TypeT> 647 class TypeToQualType : public MatcherInterface<QualType> { 648 const DynTypedMatcher InnerMatcher; 649 650 public: 651 TypeToQualType(const Matcher<TypeT> &InnerMatcher) 652 : InnerMatcher(InnerMatcher) {} 653 654 bool matches(const QualType &Node, ASTMatchFinder *Finder, 655 BoundNodesTreeBuilder *Builder) const override { 656 if (Node.isNull()) 657 return false; 658 return this->InnerMatcher.matches(DynTypedNode::create(*Node), Finder, 659 Builder); 660 } 661 662 llvm::Optional<clang::TraversalKind> TraversalKind() const override { 663 return this->InnerMatcher.getTraversalKind(); 664 } 665 }; 666 667 private: 668 // For Matcher<T> <=> Matcher<U> conversions. 669 template <typename U> friend class Matcher; 670 671 // For DynTypedMatcher::unconditionalConvertTo<T>. 672 friend class DynTypedMatcher; 673 674 static DynTypedMatcher restrictMatcher(const DynTypedMatcher &Other) { 675 return Other.dynCastTo(ASTNodeKind::getFromNodeKind<T>()); 676 } 677 678 explicit Matcher(const DynTypedMatcher &Implementation) 679 : Implementation(restrictMatcher(Implementation)) { 680 assert(this->Implementation.getSupportedKind().isSame( 681 ASTNodeKind::getFromNodeKind<T>())); 682 } 683 684 DynTypedMatcher Implementation; 685 }; // class Matcher 686 687 /// A convenient helper for creating a Matcher<T> without specifying 688 /// the template type argument. 689 template <typename T> 690 inline Matcher<T> makeMatcher(MatcherInterface<T> *Implementation) { 691 return Matcher<T>(Implementation); 692 } 693 694 /// Interface that allows matchers to traverse the AST. 695 /// FIXME: Find a better name. 696 /// 697 /// This provides three entry methods for each base node type in the AST: 698 /// - \c matchesChildOf: 699 /// Matches a matcher on every child node of the given node. Returns true 700 /// if at least one child node could be matched. 701 /// - \c matchesDescendantOf: 702 /// Matches a matcher on all descendant nodes of the given node. Returns true 703 /// if at least one descendant matched. 704 /// - \c matchesAncestorOf: 705 /// Matches a matcher on all ancestors of the given node. Returns true if 706 /// at least one ancestor matched. 707 /// 708 /// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal. 709 /// In the future, we want to implement this for all nodes for which it makes 710 /// sense. In the case of matchesAncestorOf, we'll want to implement it for 711 /// all nodes, as all nodes have ancestors. 712 class ASTMatchFinder { 713 public: 714 /// Defines how bindings are processed on recursive matches. 715 enum BindKind { 716 /// Stop at the first match and only bind the first match. 717 BK_First, 718 719 /// Create results for all combinations of bindings that match. 720 BK_All 721 }; 722 723 /// Defines which ancestors are considered for a match. 724 enum AncestorMatchMode { 725 /// All ancestors. 726 AMM_All, 727 728 /// Direct parent only. 729 AMM_ParentOnly 730 }; 731 732 virtual ~ASTMatchFinder() = default; 733 734 /// Returns true if the given C++ class is directly or indirectly derived 735 /// from a base type matching \c base. 736 /// 737 /// A class is not considered to be derived from itself. 738 virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration, 739 const Matcher<NamedDecl> &Base, 740 BoundNodesTreeBuilder *Builder, 741 bool Directly) = 0; 742 743 /// Returns true if the given Objective-C class is directly or indirectly 744 /// derived from a base class matching \c base. 745 /// 746 /// A class is not considered to be derived from itself. 747 virtual bool objcClassIsDerivedFrom(const ObjCInterfaceDecl *Declaration, 748 const Matcher<NamedDecl> &Base, 749 BoundNodesTreeBuilder *Builder, 750 bool Directly) = 0; 751 752 template <typename T> 753 bool matchesChildOf(const T &Node, const DynTypedMatcher &Matcher, 754 BoundNodesTreeBuilder *Builder, BindKind Bind) { 755 static_assert(std::is_base_of<Decl, T>::value || 756 std::is_base_of<Stmt, T>::value || 757 std::is_base_of<NestedNameSpecifier, T>::value || 758 std::is_base_of<NestedNameSpecifierLoc, T>::value || 759 std::is_base_of<TypeLoc, T>::value || 760 std::is_base_of<QualType, T>::value, 761 "unsupported type for recursive matching"); 762 return matchesChildOf(DynTypedNode::create(Node), getASTContext(), Matcher, 763 Builder, Bind); 764 } 765 766 template <typename T> 767 bool matchesDescendantOf(const T &Node, const DynTypedMatcher &Matcher, 768 BoundNodesTreeBuilder *Builder, BindKind Bind) { 769 static_assert(std::is_base_of<Decl, T>::value || 770 std::is_base_of<Stmt, T>::value || 771 std::is_base_of<NestedNameSpecifier, T>::value || 772 std::is_base_of<NestedNameSpecifierLoc, T>::value || 773 std::is_base_of<TypeLoc, T>::value || 774 std::is_base_of<QualType, T>::value, 775 "unsupported type for recursive matching"); 776 return matchesDescendantOf(DynTypedNode::create(Node), getASTContext(), 777 Matcher, Builder, Bind); 778 } 779 780 // FIXME: Implement support for BindKind. 781 template <typename T> 782 bool matchesAncestorOf(const T &Node, const DynTypedMatcher &Matcher, 783 BoundNodesTreeBuilder *Builder, 784 AncestorMatchMode MatchMode) { 785 static_assert(std::is_base_of<Decl, T>::value || 786 std::is_base_of<NestedNameSpecifierLoc, T>::value || 787 std::is_base_of<Stmt, T>::value || 788 std::is_base_of<TypeLoc, T>::value, 789 "type not allowed for recursive matching"); 790 return matchesAncestorOf(DynTypedNode::create(Node), getASTContext(), 791 Matcher, Builder, MatchMode); 792 } 793 794 virtual ASTContext &getASTContext() const = 0; 795 796 virtual bool IsMatchingInASTNodeNotSpelledInSource() const = 0; 797 798 virtual bool IsMatchingInASTNodeNotAsIs() const = 0; 799 800 bool isTraversalIgnoringImplicitNodes() const; 801 802 protected: 803 virtual bool matchesChildOf(const DynTypedNode &Node, ASTContext &Ctx, 804 const DynTypedMatcher &Matcher, 805 BoundNodesTreeBuilder *Builder, 806 BindKind Bind) = 0; 807 808 virtual bool matchesDescendantOf(const DynTypedNode &Node, ASTContext &Ctx, 809 const DynTypedMatcher &Matcher, 810 BoundNodesTreeBuilder *Builder, 811 BindKind Bind) = 0; 812 813 virtual bool matchesAncestorOf(const DynTypedNode &Node, ASTContext &Ctx, 814 const DynTypedMatcher &Matcher, 815 BoundNodesTreeBuilder *Builder, 816 AncestorMatchMode MatchMode) = 0; 817 private: 818 friend struct ASTChildrenNotSpelledInSourceScope; 819 virtual bool isMatchingChildrenNotSpelledInSource() const = 0; 820 virtual void setMatchingChildrenNotSpelledInSource(bool Set) = 0; 821 }; 822 823 struct ASTChildrenNotSpelledInSourceScope { 824 ASTChildrenNotSpelledInSourceScope(ASTMatchFinder *V, bool B) 825 : MV(V), MB(V->isMatchingChildrenNotSpelledInSource()) { 826 V->setMatchingChildrenNotSpelledInSource(B); 827 } 828 ~ASTChildrenNotSpelledInSourceScope() { 829 MV->setMatchingChildrenNotSpelledInSource(MB); 830 } 831 832 private: 833 ASTMatchFinder *MV; 834 bool MB; 835 }; 836 837 /// Specialization of the conversion functions for QualType. 838 /// 839 /// This specialization provides the Matcher<Type>->Matcher<QualType> 840 /// conversion that the static API does. 841 template <> 842 inline Matcher<QualType> DynTypedMatcher::convertTo<QualType>() const { 843 assert(canConvertTo<QualType>()); 844 const ASTNodeKind SourceKind = getSupportedKind(); 845 if (SourceKind.isSame(ASTNodeKind::getFromNodeKind<Type>())) { 846 // We support implicit conversion from Matcher<Type> to Matcher<QualType> 847 return unconditionalConvertTo<Type>(); 848 } 849 return unconditionalConvertTo<QualType>(); 850 } 851 852 /// Finds the first node in a range that matches the given matcher. 853 template <typename MatcherT, typename IteratorT> 854 IteratorT matchesFirstInRange(const MatcherT &Matcher, IteratorT Start, 855 IteratorT End, ASTMatchFinder *Finder, 856 BoundNodesTreeBuilder *Builder) { 857 for (IteratorT I = Start; I != End; ++I) { 858 BoundNodesTreeBuilder Result(*Builder); 859 if (Matcher.matches(*I, Finder, &Result)) { 860 *Builder = std::move(Result); 861 return I; 862 } 863 } 864 return End; 865 } 866 867 /// Finds the first node in a pointer range that matches the given 868 /// matcher. 869 template <typename MatcherT, typename IteratorT> 870 IteratorT matchesFirstInPointerRange(const MatcherT &Matcher, IteratorT Start, 871 IteratorT End, ASTMatchFinder *Finder, 872 BoundNodesTreeBuilder *Builder) { 873 for (IteratorT I = Start; I != End; ++I) { 874 BoundNodesTreeBuilder Result(*Builder); 875 if (Matcher.matches(**I, Finder, &Result)) { 876 *Builder = std::move(Result); 877 return I; 878 } 879 } 880 return End; 881 } 882 883 template <typename T, std::enable_if_t<!std::is_base_of<FunctionDecl, T>::value> 884 * = nullptr> 885 inline bool isDefaultedHelper(const T *) { 886 return false; 887 } 888 inline bool isDefaultedHelper(const FunctionDecl *FD) { 889 return FD->isDefaulted(); 890 } 891 892 // Metafunction to determine if type T has a member called getDecl. 893 template <typename Ty> 894 class has_getDecl { 895 using yes = char[1]; 896 using no = char[2]; 897 898 template <typename Inner> 899 static yes& test(Inner *I, decltype(I->getDecl()) * = nullptr); 900 901 template <typename> 902 static no& test(...); 903 904 public: 905 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 906 }; 907 908 /// Matches overloaded operators with a specific name. 909 /// 910 /// The type argument ArgT is not used by this matcher but is used by 911 /// PolymorphicMatcher and should be StringRef. 912 template <typename T, typename ArgT> 913 class HasOverloadedOperatorNameMatcher : public SingleNodeMatcherInterface<T> { 914 static_assert(std::is_same<T, CXXOperatorCallExpr>::value || 915 std::is_base_of<FunctionDecl, T>::value, 916 "unsupported class for matcher"); 917 static_assert(std::is_same<ArgT, std::vector<std::string>>::value, 918 "argument type must be std::vector<std::string>"); 919 920 public: 921 explicit HasOverloadedOperatorNameMatcher(std::vector<std::string> Names) 922 : SingleNodeMatcherInterface<T>(), Names(std::move(Names)) {} 923 924 bool matchesNode(const T &Node) const override { 925 return matchesSpecialized(Node); 926 } 927 928 private: 929 930 /// CXXOperatorCallExpr exist only for calls to overloaded operators 931 /// so this function returns true if the call is to an operator of the given 932 /// name. 933 bool matchesSpecialized(const CXXOperatorCallExpr &Node) const { 934 return llvm::is_contained(Names, getOperatorSpelling(Node.getOperator())); 935 } 936 937 /// Returns true only if CXXMethodDecl represents an overloaded 938 /// operator and has the given operator name. 939 bool matchesSpecialized(const FunctionDecl &Node) const { 940 return Node.isOverloadedOperator() && 941 llvm::is_contained( 942 Names, getOperatorSpelling(Node.getOverloadedOperator())); 943 } 944 945 std::vector<std::string> Names; 946 }; 947 948 /// Matches named declarations with a specific name. 949 /// 950 /// See \c hasName() and \c hasAnyName() in ASTMatchers.h for details. 951 class HasNameMatcher : public SingleNodeMatcherInterface<NamedDecl> { 952 public: 953 explicit HasNameMatcher(std::vector<std::string> Names); 954 955 bool matchesNode(const NamedDecl &Node) const override; 956 957 private: 958 /// Unqualified match routine. 959 /// 960 /// It is much faster than the full match, but it only works for unqualified 961 /// matches. 962 bool matchesNodeUnqualified(const NamedDecl &Node) const; 963 964 /// Full match routine 965 /// 966 /// Fast implementation for the simple case of a named declaration at 967 /// namespace or RecordDecl scope. 968 /// It is slower than matchesNodeUnqualified, but faster than 969 /// matchesNodeFullSlow. 970 bool matchesNodeFullFast(const NamedDecl &Node) const; 971 972 /// Full match routine 973 /// 974 /// It generates the fully qualified name of the declaration (which is 975 /// expensive) before trying to match. 976 /// It is slower but simple and works on all cases. 977 bool matchesNodeFullSlow(const NamedDecl &Node) const; 978 979 bool UseUnqualifiedMatch; 980 std::vector<std::string> Names; 981 }; 982 983 /// Trampoline function to use VariadicFunction<> to construct a 984 /// HasNameMatcher. 985 Matcher<NamedDecl> hasAnyNameFunc(ArrayRef<const StringRef *> NameRefs); 986 987 /// Trampoline function to use VariadicFunction<> to construct a 988 /// hasAnySelector matcher. 989 Matcher<ObjCMessageExpr> hasAnySelectorFunc( 990 ArrayRef<const StringRef *> NameRefs); 991 992 /// Matches declarations for QualType and CallExpr. 993 /// 994 /// Type argument DeclMatcherT is required by PolymorphicMatcher but 995 /// not actually used. 996 template <typename T, typename DeclMatcherT> 997 class HasDeclarationMatcher : public MatcherInterface<T> { 998 static_assert(std::is_same<DeclMatcherT, Matcher<Decl>>::value, 999 "instantiated with wrong types"); 1000 1001 DynTypedMatcher InnerMatcher; 1002 1003 public: 1004 explicit HasDeclarationMatcher(const Matcher<Decl> &InnerMatcher) 1005 : InnerMatcher(InnerMatcher) {} 1006 1007 bool matches(const T &Node, ASTMatchFinder *Finder, 1008 BoundNodesTreeBuilder *Builder) const override { 1009 return matchesSpecialized(Node, Finder, Builder); 1010 } 1011 1012 private: 1013 /// Forwards to matching on the underlying type of the QualType. 1014 bool matchesSpecialized(const QualType &Node, ASTMatchFinder *Finder, 1015 BoundNodesTreeBuilder *Builder) const { 1016 if (Node.isNull()) 1017 return false; 1018 1019 return matchesSpecialized(*Node, Finder, Builder); 1020 } 1021 1022 /// Finds the best declaration for a type and returns whether the inner 1023 /// matcher matches on it. 1024 bool matchesSpecialized(const Type &Node, ASTMatchFinder *Finder, 1025 BoundNodesTreeBuilder *Builder) const { 1026 // DeducedType does not have declarations of its own, so 1027 // match the deduced type instead. 1028 const Type *EffectiveType = &Node; 1029 if (const auto *S = dyn_cast<DeducedType>(&Node)) { 1030 EffectiveType = S->getDeducedType().getTypePtrOrNull(); 1031 if (!EffectiveType) 1032 return false; 1033 } 1034 1035 // First, for any types that have a declaration, extract the declaration and 1036 // match on it. 1037 if (const auto *S = dyn_cast<TagType>(EffectiveType)) { 1038 return matchesDecl(S->getDecl(), Finder, Builder); 1039 } 1040 if (const auto *S = dyn_cast<InjectedClassNameType>(EffectiveType)) { 1041 return matchesDecl(S->getDecl(), Finder, Builder); 1042 } 1043 if (const auto *S = dyn_cast<TemplateTypeParmType>(EffectiveType)) { 1044 return matchesDecl(S->getDecl(), Finder, Builder); 1045 } 1046 if (const auto *S = dyn_cast<TypedefType>(EffectiveType)) { 1047 return matchesDecl(S->getDecl(), Finder, Builder); 1048 } 1049 if (const auto *S = dyn_cast<UnresolvedUsingType>(EffectiveType)) { 1050 return matchesDecl(S->getDecl(), Finder, Builder); 1051 } 1052 if (const auto *S = dyn_cast<ObjCObjectType>(EffectiveType)) { 1053 return matchesDecl(S->getInterface(), Finder, Builder); 1054 } 1055 1056 // A SubstTemplateTypeParmType exists solely to mark a type substitution 1057 // on the instantiated template. As users usually want to match the 1058 // template parameter on the uninitialized template, we can always desugar 1059 // one level without loss of expressivness. 1060 // For example, given: 1061 // template<typename T> struct X { T t; } class A {}; X<A> a; 1062 // The following matcher will match, which otherwise would not: 1063 // fieldDecl(hasType(pointerType())). 1064 if (const auto *S = dyn_cast<SubstTemplateTypeParmType>(EffectiveType)) { 1065 return matchesSpecialized(S->getReplacementType(), Finder, Builder); 1066 } 1067 1068 // For template specialization types, we want to match the template 1069 // declaration, as long as the type is still dependent, and otherwise the 1070 // declaration of the instantiated tag type. 1071 if (const auto *S = dyn_cast<TemplateSpecializationType>(EffectiveType)) { 1072 if (!S->isTypeAlias() && S->isSugared()) { 1073 // If the template is non-dependent, we want to match the instantiated 1074 // tag type. 1075 // For example, given: 1076 // template<typename T> struct X {}; X<int> a; 1077 // The following matcher will match, which otherwise would not: 1078 // templateSpecializationType(hasDeclaration(cxxRecordDecl())). 1079 return matchesSpecialized(*S->desugar(), Finder, Builder); 1080 } 1081 // If the template is dependent or an alias, match the template 1082 // declaration. 1083 return matchesDecl(S->getTemplateName().getAsTemplateDecl(), Finder, 1084 Builder); 1085 } 1086 1087 // FIXME: We desugar elaborated types. This makes the assumption that users 1088 // do never want to match on whether a type is elaborated - there are 1089 // arguments for both sides; for now, continue desugaring. 1090 if (const auto *S = dyn_cast<ElaboratedType>(EffectiveType)) { 1091 return matchesSpecialized(S->desugar(), Finder, Builder); 1092 } 1093 return false; 1094 } 1095 1096 /// Extracts the Decl the DeclRefExpr references and returns whether 1097 /// the inner matcher matches on it. 1098 bool matchesSpecialized(const DeclRefExpr &Node, ASTMatchFinder *Finder, 1099 BoundNodesTreeBuilder *Builder) const { 1100 return matchesDecl(Node.getDecl(), Finder, Builder); 1101 } 1102 1103 /// Extracts the Decl of the callee of a CallExpr and returns whether 1104 /// the inner matcher matches on it. 1105 bool matchesSpecialized(const CallExpr &Node, ASTMatchFinder *Finder, 1106 BoundNodesTreeBuilder *Builder) const { 1107 return matchesDecl(Node.getCalleeDecl(), Finder, Builder); 1108 } 1109 1110 /// Extracts the Decl of the constructor call and returns whether the 1111 /// inner matcher matches on it. 1112 bool matchesSpecialized(const CXXConstructExpr &Node, 1113 ASTMatchFinder *Finder, 1114 BoundNodesTreeBuilder *Builder) const { 1115 return matchesDecl(Node.getConstructor(), Finder, Builder); 1116 } 1117 1118 bool matchesSpecialized(const ObjCIvarRefExpr &Node, 1119 ASTMatchFinder *Finder, 1120 BoundNodesTreeBuilder *Builder) const { 1121 return matchesDecl(Node.getDecl(), Finder, Builder); 1122 } 1123 1124 /// Extracts the operator new of the new call and returns whether the 1125 /// inner matcher matches on it. 1126 bool matchesSpecialized(const CXXNewExpr &Node, 1127 ASTMatchFinder *Finder, 1128 BoundNodesTreeBuilder *Builder) const { 1129 return matchesDecl(Node.getOperatorNew(), Finder, Builder); 1130 } 1131 1132 /// Extracts the \c ValueDecl a \c MemberExpr refers to and returns 1133 /// whether the inner matcher matches on it. 1134 bool matchesSpecialized(const MemberExpr &Node, 1135 ASTMatchFinder *Finder, 1136 BoundNodesTreeBuilder *Builder) const { 1137 return matchesDecl(Node.getMemberDecl(), Finder, Builder); 1138 } 1139 1140 /// Extracts the \c LabelDecl a \c AddrLabelExpr refers to and returns 1141 /// whether the inner matcher matches on it. 1142 bool matchesSpecialized(const AddrLabelExpr &Node, 1143 ASTMatchFinder *Finder, 1144 BoundNodesTreeBuilder *Builder) const { 1145 return matchesDecl(Node.getLabel(), Finder, Builder); 1146 } 1147 1148 /// Extracts the declaration of a LabelStmt and returns whether the 1149 /// inner matcher matches on it. 1150 bool matchesSpecialized(const LabelStmt &Node, ASTMatchFinder *Finder, 1151 BoundNodesTreeBuilder *Builder) const { 1152 return matchesDecl(Node.getDecl(), Finder, Builder); 1153 } 1154 1155 /// Returns whether the inner matcher \c Node. Returns false if \c Node 1156 /// is \c NULL. 1157 bool matchesDecl(const Decl *Node, ASTMatchFinder *Finder, 1158 BoundNodesTreeBuilder *Builder) const { 1159 return Node != nullptr && 1160 !(Finder->isTraversalIgnoringImplicitNodes() && 1161 Node->isImplicit()) && 1162 this->InnerMatcher.matches(DynTypedNode::create(*Node), Finder, 1163 Builder); 1164 } 1165 }; 1166 1167 /// IsBaseType<T>::value is true if T is a "base" type in the AST 1168 /// node class hierarchies. 1169 template <typename T> 1170 struct IsBaseType { 1171 static const bool value = 1172 std::is_same<T, Decl>::value || std::is_same<T, Stmt>::value || 1173 std::is_same<T, QualType>::value || std::is_same<T, Type>::value || 1174 std::is_same<T, TypeLoc>::value || 1175 std::is_same<T, NestedNameSpecifier>::value || 1176 std::is_same<T, NestedNameSpecifierLoc>::value || 1177 std::is_same<T, CXXCtorInitializer>::value || 1178 std::is_same<T, TemplateArgumentLoc>::value; 1179 }; 1180 template <typename T> 1181 const bool IsBaseType<T>::value; 1182 1183 /// A "type list" that contains all types. 1184 /// 1185 /// Useful for matchers like \c anything and \c unless. 1186 using AllNodeBaseTypes = 1187 TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc, QualType, 1188 Type, TypeLoc, CXXCtorInitializer>; 1189 1190 /// Helper meta-function to extract the argument out of a function of 1191 /// type void(Arg). 1192 /// 1193 /// See AST_POLYMORPHIC_SUPPORTED_TYPES for details. 1194 template <class T> struct ExtractFunctionArgMeta; 1195 template <class T> struct ExtractFunctionArgMeta<void(T)> { 1196 using type = T; 1197 }; 1198 1199 template <class T, class Tuple, std::size_t... I> 1200 constexpr T *new_from_tuple_impl(Tuple &&t, std::index_sequence<I...>) { 1201 return new T(std::get<I>(std::forward<Tuple>(t))...); 1202 } 1203 1204 template <class T, class Tuple> constexpr T *new_from_tuple(Tuple &&t) { 1205 return new_from_tuple_impl<T>( 1206 std::forward<Tuple>(t), 1207 std::make_index_sequence< 1208 std::tuple_size<std::remove_reference_t<Tuple>>::value>{}); 1209 } 1210 1211 /// Default type lists for ArgumentAdaptingMatcher matchers. 1212 using AdaptativeDefaultFromTypes = AllNodeBaseTypes; 1213 using AdaptativeDefaultToTypes = 1214 TypeList<Decl, Stmt, NestedNameSpecifier, NestedNameSpecifierLoc, TypeLoc, 1215 QualType>; 1216 1217 /// All types that are supported by HasDeclarationMatcher above. 1218 using HasDeclarationSupportedTypes = 1219 TypeList<CallExpr, CXXConstructExpr, CXXNewExpr, DeclRefExpr, EnumType, 1220 ElaboratedType, InjectedClassNameType, LabelStmt, AddrLabelExpr, 1221 MemberExpr, QualType, RecordType, TagType, 1222 TemplateSpecializationType, TemplateTypeParmType, TypedefType, 1223 UnresolvedUsingType, ObjCIvarRefExpr>; 1224 1225 /// A Matcher that allows binding the node it matches to an id. 1226 /// 1227 /// BindableMatcher provides a \a bind() method that allows binding the 1228 /// matched node to an id if the match was successful. 1229 template <typename T> class BindableMatcher : public Matcher<T> { 1230 public: 1231 explicit BindableMatcher(const Matcher<T> &M) : Matcher<T>(M) {} 1232 explicit BindableMatcher(MatcherInterface<T> *Implementation) 1233 : Matcher<T>(Implementation) {} 1234 1235 /// Returns a matcher that will bind the matched node on a match. 1236 /// 1237 /// The returned matcher is equivalent to this matcher, but will 1238 /// bind the matched node on a match. 1239 Matcher<T> bind(StringRef ID) const { 1240 return DynTypedMatcher(*this) 1241 .tryBind(ID) 1242 ->template unconditionalConvertTo<T>(); 1243 } 1244 1245 /// Same as Matcher<T>'s conversion operator, but enables binding on 1246 /// the returned matcher. 1247 operator DynTypedMatcher() const { 1248 DynTypedMatcher Result = static_cast<const Matcher<T> &>(*this); 1249 Result.setAllowBind(true); 1250 return Result; 1251 } 1252 }; 1253 1254 /// Matches any instance of the given NodeType. 1255 /// 1256 /// This is useful when a matcher syntactically requires a child matcher, 1257 /// but the context doesn't care. See for example: anything(). 1258 class TrueMatcher { 1259 public: 1260 using ReturnTypes = AllNodeBaseTypes; 1261 1262 template <typename T> operator Matcher<T>() const { 1263 return DynTypedMatcher::trueMatcher(ASTNodeKind::getFromNodeKind<T>()) 1264 .template unconditionalConvertTo<T>(); 1265 } 1266 }; 1267 1268 /// Creates a Matcher<T> that matches if all inner matchers match. 1269 template <typename T> 1270 BindableMatcher<T> 1271 makeAllOfComposite(ArrayRef<const Matcher<T> *> InnerMatchers) { 1272 // For the size() == 0 case, we return a "true" matcher. 1273 if (InnerMatchers.empty()) { 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 using PI = llvm::pointee_iterator<const Matcher<T> *const *>; 1283 1284 std::vector<DynTypedMatcher> DynMatchers(PI(InnerMatchers.begin()), 1285 PI(InnerMatchers.end())); 1286 return BindableMatcher<T>( 1287 DynTypedMatcher::constructVariadic(DynTypedMatcher::VO_AllOf, 1288 ASTNodeKind::getFromNodeKind<T>(), 1289 std::move(DynMatchers)) 1290 .template unconditionalConvertTo<T>()); 1291 } 1292 1293 /// 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> 1301 makeDynCastAllOfComposite(ArrayRef<const Matcher<InnerT> *> InnerMatchers) { 1302 return BindableMatcher<T>( 1303 makeAllOfComposite(InnerMatchers).template dynCastTo<T>()); 1304 } 1305 1306 /// A VariadicDynCastAllOfMatcher<SourceT, TargetT> object is a 1307 /// variadic functor that takes a number of Matcher<TargetT> and returns a 1308 /// Matcher<SourceT> that matches TargetT nodes that are matched by all of the 1309 /// given matchers, if SourceT can be dynamically casted into TargetT. 1310 /// 1311 /// For example: 1312 /// const VariadicDynCastAllOfMatcher<Decl, CXXRecordDecl> record; 1313 /// Creates a functor record(...) that creates a Matcher<Decl> given 1314 /// a variable number of arguments of type Matcher<CXXRecordDecl>. 1315 /// The returned matcher matches if the given Decl can by dynamically 1316 /// casted to CXXRecordDecl and all given matchers match. 1317 template <typename SourceT, typename TargetT> 1318 class VariadicDynCastAllOfMatcher 1319 : public VariadicFunction<BindableMatcher<SourceT>, Matcher<TargetT>, 1320 makeDynCastAllOfComposite<SourceT, TargetT>> { 1321 public: 1322 VariadicDynCastAllOfMatcher() {} 1323 }; 1324 1325 /// A \c VariadicAllOfMatcher<T> object is a variadic functor that takes 1326 /// a number of \c Matcher<T> and returns a \c Matcher<T> that matches \c T 1327 /// nodes that are matched by all of the given matchers. 1328 /// 1329 /// For example: 1330 /// const VariadicAllOfMatcher<NestedNameSpecifier> nestedNameSpecifier; 1331 /// Creates a functor nestedNameSpecifier(...) that creates a 1332 /// \c Matcher<NestedNameSpecifier> given a variable number of arguments of type 1333 /// \c Matcher<NestedNameSpecifier>. 1334 /// The returned matcher matches if all given matchers match. 1335 template <typename T> 1336 class VariadicAllOfMatcher 1337 : public VariadicFunction<BindableMatcher<T>, Matcher<T>, 1338 makeAllOfComposite<T>> { 1339 public: 1340 VariadicAllOfMatcher() {} 1341 }; 1342 1343 /// VariadicOperatorMatcher related types. 1344 /// @{ 1345 1346 /// Polymorphic matcher object that uses a \c 1347 /// DynTypedMatcher::VariadicOperator operator. 1348 /// 1349 /// Input matchers can have any type (including other polymorphic matcher 1350 /// types), and the actual Matcher<T> is generated on demand with an implicit 1351 /// conversion operator. 1352 template <typename... Ps> class VariadicOperatorMatcher { 1353 public: 1354 VariadicOperatorMatcher(DynTypedMatcher::VariadicOperator Op, Ps &&... Params) 1355 : Op(Op), Params(std::forward<Ps>(Params)...) {} 1356 1357 template <typename T> operator Matcher<T>() const LLVM_LVALUE_FUNCTION { 1358 return DynTypedMatcher::constructVariadic( 1359 Op, ASTNodeKind::getFromNodeKind<T>(), 1360 getMatchers<T>(std::index_sequence_for<Ps...>())) 1361 .template unconditionalConvertTo<T>(); 1362 } 1363 1364 #if LLVM_HAS_RVALUE_REFERENCE_THIS 1365 template <typename T> operator Matcher<T>() && { 1366 return DynTypedMatcher::constructVariadic( 1367 Op, ASTNodeKind::getFromNodeKind<T>(), 1368 getMatchers<T>(std::index_sequence_for<Ps...>())) 1369 .template unconditionalConvertTo<T>(); 1370 } 1371 #endif 1372 private: 1373 // Helper method to unpack the tuple into a vector. 1374 template <typename T, std::size_t... Is> 1375 std::vector<DynTypedMatcher> 1376 getMatchers(std::index_sequence<Is...>) const LLVM_LVALUE_FUNCTION { 1377 return {Matcher<T>(std::get<Is>(Params))...}; 1378 } 1379 1380 #if LLVM_HAS_RVALUE_REFERENCE_THIS 1381 template <typename T, std::size_t... Is> 1382 std::vector<DynTypedMatcher> getMatchers(std::index_sequence<Is...>) && { 1383 return {Matcher<T>(std::get<Is>(std::move(Params)))...}; 1384 } 1385 #endif 1386 1387 const DynTypedMatcher::VariadicOperator Op; 1388 std::tuple<Ps...> Params; 1389 }; 1390 1391 /// Overloaded function object to generate VariadicOperatorMatcher 1392 /// objects from arbitrary matchers. 1393 template <unsigned MinCount, unsigned MaxCount> 1394 struct VariadicOperatorMatcherFunc { 1395 DynTypedMatcher::VariadicOperator Op; 1396 1397 template <typename... Ms> 1398 VariadicOperatorMatcher<Ms...> operator()(Ms &&... Ps) const { 1399 static_assert(MinCount <= sizeof...(Ms) && sizeof...(Ms) <= MaxCount, 1400 "invalid number of parameters for variadic matcher"); 1401 return VariadicOperatorMatcher<Ms...>(Op, std::forward<Ms>(Ps)...); 1402 } 1403 }; 1404 1405 template <typename F, typename Tuple, std::size_t... I> 1406 constexpr auto applyMatcherImpl(F &&f, Tuple &&args, 1407 std::index_sequence<I...>) { 1408 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(args))...); 1409 } 1410 1411 template <typename F, typename Tuple> 1412 constexpr auto applyMatcher(F &&f, Tuple &&args) { 1413 return applyMatcherImpl( 1414 std::forward<F>(f), std::forward<Tuple>(args), 1415 std::make_index_sequence< 1416 std::tuple_size<typename std::decay<Tuple>::type>::value>()); 1417 } 1418 1419 template <typename T, bool IsBaseOf, typename Head, typename Tail> 1420 struct GetCladeImpl { 1421 using Type = Head; 1422 }; 1423 template <typename T, typename Head, typename Tail> 1424 struct GetCladeImpl<T, false, Head, Tail> 1425 : GetCladeImpl<T, std::is_base_of<typename Tail::head, T>::value, 1426 typename Tail::head, typename Tail::tail> {}; 1427 1428 template <typename T, typename... U> 1429 struct GetClade : GetCladeImpl<T, false, T, AllNodeBaseTypes> {}; 1430 1431 template <typename CladeType, typename... MatcherTypes> 1432 struct MapAnyOfMatcherImpl { 1433 1434 template <typename... InnerMatchers> 1435 BindableMatcher<CladeType> 1436 operator()(InnerMatchers &&... InnerMatcher) const { 1437 // TODO: Use std::apply from c++17 1438 return VariadicAllOfMatcher<CladeType>()(applyMatcher( 1439 internal::VariadicOperatorMatcherFunc< 1440 0, std::numeric_limits<unsigned>::max()>{ 1441 internal::DynTypedMatcher::VO_AnyOf}, 1442 applyMatcher( 1443 [&](auto... Matcher) { 1444 return std::make_tuple(Matcher(InnerMatcher...)...); 1445 }, 1446 std::tuple< 1447 VariadicDynCastAllOfMatcher<CladeType, MatcherTypes>...>()))); 1448 } 1449 }; 1450 1451 template <typename... MatcherTypes> 1452 using MapAnyOfMatcher = 1453 MapAnyOfMatcherImpl<typename GetClade<MatcherTypes...>::Type, 1454 MatcherTypes...>; 1455 1456 template <typename... MatcherTypes> struct MapAnyOfHelper { 1457 using CladeType = typename GetClade<MatcherTypes...>::Type; 1458 1459 MapAnyOfMatcher<MatcherTypes...> with; 1460 1461 operator BindableMatcher<CladeType>() const { return with(); } 1462 1463 Matcher<CladeType> bind(StringRef ID) const { return with().bind(ID); } 1464 }; 1465 1466 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT, 1467 typename T, typename ToTypes> 1468 class ArgumentAdaptingMatcherFuncAdaptor { 1469 public: 1470 explicit ArgumentAdaptingMatcherFuncAdaptor(const Matcher<T> &InnerMatcher) 1471 : InnerMatcher(InnerMatcher) {} 1472 1473 using ReturnTypes = ToTypes; 1474 1475 template <typename To> operator Matcher<To>() const LLVM_LVALUE_FUNCTION { 1476 return Matcher<To>(new ArgumentAdapterT<To, T>(InnerMatcher)); 1477 } 1478 1479 #if LLVM_HAS_RVALUE_REFERENCE_THIS 1480 template <typename To> operator Matcher<To>() && { 1481 return Matcher<To>(new ArgumentAdapterT<To, T>(std::move(InnerMatcher))); 1482 } 1483 #endif 1484 1485 private: 1486 Matcher<T> InnerMatcher; 1487 }; 1488 1489 /// Converts a \c Matcher<T> to a matcher of desired type \c To by 1490 /// "adapting" a \c To into a \c T. 1491 /// 1492 /// The \c ArgumentAdapterT argument specifies how the adaptation is done. 1493 /// 1494 /// For example: 1495 /// \c ArgumentAdaptingMatcher<HasMatcher, T>(InnerMatcher); 1496 /// Given that \c InnerMatcher is of type \c Matcher<T>, this returns a matcher 1497 /// that is convertible into any matcher of type \c To by constructing 1498 /// \c HasMatcher<To, T>(InnerMatcher). 1499 /// 1500 /// If a matcher does not need knowledge about the inner type, prefer to use 1501 /// PolymorphicMatcher. 1502 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT, 1503 typename FromTypes = AdaptativeDefaultFromTypes, 1504 typename ToTypes = AdaptativeDefaultToTypes> 1505 struct ArgumentAdaptingMatcherFunc { 1506 template <typename T> 1507 static ArgumentAdaptingMatcherFuncAdaptor<ArgumentAdapterT, T, ToTypes> 1508 create(const Matcher<T> &InnerMatcher) { 1509 return ArgumentAdaptingMatcherFuncAdaptor<ArgumentAdapterT, T, ToTypes>( 1510 InnerMatcher); 1511 } 1512 1513 template <typename T> 1514 ArgumentAdaptingMatcherFuncAdaptor<ArgumentAdapterT, T, ToTypes> 1515 operator()(const Matcher<T> &InnerMatcher) const { 1516 return create(InnerMatcher); 1517 } 1518 1519 template <typename... T> 1520 ArgumentAdaptingMatcherFuncAdaptor<ArgumentAdapterT, 1521 typename GetClade<T...>::Type, ToTypes> 1522 operator()(const MapAnyOfHelper<T...> &InnerMatcher) const { 1523 return create(InnerMatcher.with()); 1524 } 1525 }; 1526 1527 template <typename T> class TraversalMatcher : public MatcherInterface<T> { 1528 DynTypedMatcher InnerMatcher; 1529 clang::TraversalKind Traversal; 1530 1531 public: 1532 explicit TraversalMatcher(clang::TraversalKind TK, 1533 const Matcher<T> &InnerMatcher) 1534 : InnerMatcher(InnerMatcher), Traversal(TK) {} 1535 1536 bool matches(const T &Node, ASTMatchFinder *Finder, 1537 BoundNodesTreeBuilder *Builder) const override { 1538 return this->InnerMatcher.matches(DynTypedNode::create(Node), Finder, 1539 Builder); 1540 } 1541 1542 llvm::Optional<clang::TraversalKind> TraversalKind() const override { 1543 if (auto NestedKind = this->InnerMatcher.getTraversalKind()) 1544 return NestedKind; 1545 return Traversal; 1546 } 1547 }; 1548 1549 template <typename MatcherType> class TraversalWrapper { 1550 public: 1551 TraversalWrapper(TraversalKind TK, const MatcherType &InnerMatcher) 1552 : TK(TK), InnerMatcher(InnerMatcher) {} 1553 1554 template <typename T> operator Matcher<T>() const LLVM_LVALUE_FUNCTION { 1555 return internal::DynTypedMatcher::constructRestrictedWrapper( 1556 new internal::TraversalMatcher<T>(TK, InnerMatcher), 1557 ASTNodeKind::getFromNodeKind<T>()) 1558 .template unconditionalConvertTo<T>(); 1559 } 1560 1561 #if LLVM_HAS_RVALUE_REFERENCE_THIS 1562 template <typename T> operator Matcher<T>() && { 1563 return internal::DynTypedMatcher::constructRestrictedWrapper( 1564 new internal::TraversalMatcher<T>(TK, std::move(InnerMatcher)), 1565 ASTNodeKind::getFromNodeKind<T>()) 1566 .template unconditionalConvertTo<T>(); 1567 } 1568 #endif 1569 1570 private: 1571 TraversalKind TK; 1572 MatcherType InnerMatcher; 1573 }; 1574 1575 /// A PolymorphicMatcher<MatcherT, P1, ..., PN> object can be 1576 /// created from N parameters p1, ..., pN (of type P1, ..., PN) and 1577 /// used as a Matcher<T> where a MatcherT<T, P1, ..., PN>(p1, ..., pN) 1578 /// can be constructed. 1579 /// 1580 /// For example: 1581 /// - PolymorphicMatcher<IsDefinitionMatcher>() 1582 /// creates an object that can be used as a Matcher<T> for any type T 1583 /// where an IsDefinitionMatcher<T>() can be constructed. 1584 /// - PolymorphicMatcher<ValueEqualsMatcher, int>(42) 1585 /// creates an object that can be used as a Matcher<T> for any type T 1586 /// where a ValueEqualsMatcher<T, int>(42) can be constructed. 1587 template <template <typename T, typename... Params> class MatcherT, 1588 typename ReturnTypesF, typename... ParamTypes> 1589 class PolymorphicMatcher { 1590 public: 1591 PolymorphicMatcher(const ParamTypes &... Params) : Params(Params...) {} 1592 1593 using ReturnTypes = typename ExtractFunctionArgMeta<ReturnTypesF>::type; 1594 1595 template <typename T> operator Matcher<T>() const LLVM_LVALUE_FUNCTION { 1596 static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value, 1597 "right polymorphic conversion"); 1598 return Matcher<T>(new_from_tuple<MatcherT<T, ParamTypes...>>(Params)); 1599 } 1600 1601 #if LLVM_HAS_RVALUE_REFERENCE_THIS 1602 template <typename T> operator Matcher<T>() && { 1603 static_assert(TypeListContainsSuperOf<ReturnTypes, T>::value, 1604 "right polymorphic conversion"); 1605 return Matcher<T>( 1606 new_from_tuple<MatcherT<T, ParamTypes...>>(std::move(Params))); 1607 } 1608 #endif 1609 1610 private: 1611 std::tuple<ParamTypes...> Params; 1612 }; 1613 1614 /// Matches nodes of type T that have child nodes of type ChildT for 1615 /// which a specified child matcher matches. 1616 /// 1617 /// ChildT must be an AST base type. 1618 template <typename T, typename ChildT> 1619 class HasMatcher : public MatcherInterface<T> { 1620 DynTypedMatcher InnerMatcher; 1621 1622 public: 1623 explicit HasMatcher(const Matcher<ChildT> &InnerMatcher) 1624 : InnerMatcher(InnerMatcher) {} 1625 1626 bool matches(const T &Node, ASTMatchFinder *Finder, 1627 BoundNodesTreeBuilder *Builder) const override { 1628 return Finder->matchesChildOf(Node, this->InnerMatcher, Builder, 1629 ASTMatchFinder::BK_First); 1630 } 1631 }; 1632 1633 /// Matches nodes of type T that have child nodes of type ChildT for 1634 /// which a specified child matcher matches. ChildT must be an AST base 1635 /// type. 1636 /// As opposed to the HasMatcher, the ForEachMatcher will produce a match 1637 /// for each child that matches. 1638 template <typename T, typename ChildT> 1639 class ForEachMatcher : public MatcherInterface<T> { 1640 static_assert(IsBaseType<ChildT>::value, 1641 "for each only accepts base type matcher"); 1642 1643 DynTypedMatcher InnerMatcher; 1644 1645 public: 1646 explicit ForEachMatcher(const Matcher<ChildT> &InnerMatcher) 1647 : InnerMatcher(InnerMatcher) {} 1648 1649 bool matches(const T &Node, ASTMatchFinder *Finder, 1650 BoundNodesTreeBuilder *Builder) const override { 1651 return Finder->matchesChildOf( 1652 Node, this->InnerMatcher, Builder, 1653 ASTMatchFinder::BK_All); 1654 } 1655 }; 1656 1657 /// @} 1658 1659 template <typename T> 1660 inline Matcher<T> DynTypedMatcher::unconditionalConvertTo() const { 1661 return Matcher<T>(*this); 1662 } 1663 1664 /// Matches nodes of type T that have at least one descendant node of 1665 /// type DescendantT for which the given inner matcher matches. 1666 /// 1667 /// DescendantT must be an AST base type. 1668 template <typename T, typename DescendantT> 1669 class HasDescendantMatcher : public MatcherInterface<T> { 1670 static_assert(IsBaseType<DescendantT>::value, 1671 "has descendant only accepts base type matcher"); 1672 1673 DynTypedMatcher DescendantMatcher; 1674 1675 public: 1676 explicit HasDescendantMatcher(const Matcher<DescendantT> &DescendantMatcher) 1677 : DescendantMatcher(DescendantMatcher) {} 1678 1679 bool matches(const T &Node, ASTMatchFinder *Finder, 1680 BoundNodesTreeBuilder *Builder) const override { 1681 return Finder->matchesDescendantOf(Node, this->DescendantMatcher, Builder, 1682 ASTMatchFinder::BK_First); 1683 } 1684 }; 1685 1686 /// Matches nodes of type \c T that have a parent node of type \c ParentT 1687 /// for which the given inner matcher matches. 1688 /// 1689 /// \c ParentT must be an AST base type. 1690 template <typename T, typename ParentT> 1691 class HasParentMatcher : public MatcherInterface<T> { 1692 static_assert(IsBaseType<ParentT>::value, 1693 "has parent only accepts base type matcher"); 1694 1695 DynTypedMatcher ParentMatcher; 1696 1697 public: 1698 explicit HasParentMatcher(const Matcher<ParentT> &ParentMatcher) 1699 : ParentMatcher(ParentMatcher) {} 1700 1701 bool matches(const T &Node, ASTMatchFinder *Finder, 1702 BoundNodesTreeBuilder *Builder) const override { 1703 return Finder->matchesAncestorOf(Node, this->ParentMatcher, Builder, 1704 ASTMatchFinder::AMM_ParentOnly); 1705 } 1706 }; 1707 1708 /// Matches nodes of type \c T that have at least one ancestor node of 1709 /// type \c AncestorT for which the given inner matcher matches. 1710 /// 1711 /// \c AncestorT must be an AST base type. 1712 template <typename T, typename AncestorT> 1713 class HasAncestorMatcher : public MatcherInterface<T> { 1714 static_assert(IsBaseType<AncestorT>::value, 1715 "has ancestor only accepts base type matcher"); 1716 1717 DynTypedMatcher AncestorMatcher; 1718 1719 public: 1720 explicit HasAncestorMatcher(const Matcher<AncestorT> &AncestorMatcher) 1721 : AncestorMatcher(AncestorMatcher) {} 1722 1723 bool matches(const T &Node, ASTMatchFinder *Finder, 1724 BoundNodesTreeBuilder *Builder) const override { 1725 return Finder->matchesAncestorOf(Node, this->AncestorMatcher, Builder, 1726 ASTMatchFinder::AMM_All); 1727 } 1728 }; 1729 1730 /// Matches nodes of type T that have at least one descendant node of 1731 /// type DescendantT for which the given inner matcher matches. 1732 /// 1733 /// DescendantT must be an AST base type. 1734 /// As opposed to HasDescendantMatcher, ForEachDescendantMatcher will match 1735 /// for each descendant node that matches instead of only for the first. 1736 template <typename T, typename DescendantT> 1737 class ForEachDescendantMatcher : public MatcherInterface<T> { 1738 static_assert(IsBaseType<DescendantT>::value, 1739 "for each descendant only accepts base type matcher"); 1740 1741 DynTypedMatcher DescendantMatcher; 1742 1743 public: 1744 explicit ForEachDescendantMatcher( 1745 const Matcher<DescendantT> &DescendantMatcher) 1746 : DescendantMatcher(DescendantMatcher) {} 1747 1748 bool matches(const T &Node, ASTMatchFinder *Finder, 1749 BoundNodesTreeBuilder *Builder) const override { 1750 return Finder->matchesDescendantOf(Node, this->DescendantMatcher, Builder, 1751 ASTMatchFinder::BK_All); 1752 } 1753 }; 1754 1755 /// Matches on nodes that have a getValue() method if getValue() equals 1756 /// the value the ValueEqualsMatcher was constructed with. 1757 template <typename T, typename ValueT> 1758 class ValueEqualsMatcher : public SingleNodeMatcherInterface<T> { 1759 static_assert(std::is_base_of<CharacterLiteral, T>::value || 1760 std::is_base_of<CXXBoolLiteralExpr, T>::value || 1761 std::is_base_of<FloatingLiteral, T>::value || 1762 std::is_base_of<IntegerLiteral, T>::value, 1763 "the node must have a getValue method"); 1764 1765 public: 1766 explicit ValueEqualsMatcher(const ValueT &ExpectedValue) 1767 : ExpectedValue(ExpectedValue) {} 1768 1769 bool matchesNode(const T &Node) const override { 1770 return Node.getValue() == ExpectedValue; 1771 } 1772 1773 private: 1774 ValueT ExpectedValue; 1775 }; 1776 1777 /// Template specializations to easily write matchers for floating point 1778 /// literals. 1779 template <> 1780 inline bool ValueEqualsMatcher<FloatingLiteral, double>::matchesNode( 1781 const FloatingLiteral &Node) const { 1782 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle()) 1783 return Node.getValue().convertToFloat() == ExpectedValue; 1784 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble()) 1785 return Node.getValue().convertToDouble() == ExpectedValue; 1786 return false; 1787 } 1788 template <> 1789 inline bool ValueEqualsMatcher<FloatingLiteral, float>::matchesNode( 1790 const FloatingLiteral &Node) const { 1791 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEsingle()) 1792 return Node.getValue().convertToFloat() == ExpectedValue; 1793 if ((&Node.getSemantics()) == &llvm::APFloat::IEEEdouble()) 1794 return Node.getValue().convertToDouble() == ExpectedValue; 1795 return false; 1796 } 1797 template <> 1798 inline bool ValueEqualsMatcher<FloatingLiteral, llvm::APFloat>::matchesNode( 1799 const FloatingLiteral &Node) const { 1800 return ExpectedValue.compare(Node.getValue()) == llvm::APFloat::cmpEqual; 1801 } 1802 1803 /// Matches nodes of type \c TLoc for which the inner 1804 /// \c Matcher<T> matches. 1805 template <typename TLoc, typename T> 1806 class LocMatcher : public MatcherInterface<TLoc> { 1807 DynTypedMatcher InnerMatcher; 1808 1809 public: 1810 explicit LocMatcher(const Matcher<T> &InnerMatcher) 1811 : InnerMatcher(InnerMatcher) {} 1812 1813 bool matches(const TLoc &Node, ASTMatchFinder *Finder, 1814 BoundNodesTreeBuilder *Builder) const override { 1815 if (!Node) 1816 return false; 1817 return this->InnerMatcher.matches(extract(Node), Finder, Builder); 1818 } 1819 1820 private: 1821 static DynTypedNode extract(const NestedNameSpecifierLoc &Loc) { 1822 return DynTypedNode::create(*Loc.getNestedNameSpecifier()); 1823 } 1824 }; 1825 1826 /// Matches \c TypeLocs based on an inner matcher matching a certain 1827 /// \c QualType. 1828 /// 1829 /// Used to implement the \c loc() matcher. 1830 class TypeLocTypeMatcher : public MatcherInterface<TypeLoc> { 1831 DynTypedMatcher InnerMatcher; 1832 1833 public: 1834 explicit TypeLocTypeMatcher(const Matcher<QualType> &InnerMatcher) 1835 : InnerMatcher(InnerMatcher) {} 1836 1837 bool matches(const TypeLoc &Node, ASTMatchFinder *Finder, 1838 BoundNodesTreeBuilder *Builder) const override { 1839 if (!Node) 1840 return false; 1841 return this->InnerMatcher.matches(DynTypedNode::create(Node.getType()), 1842 Finder, Builder); 1843 } 1844 }; 1845 1846 /// Matches nodes of type \c T for which the inner matcher matches on a 1847 /// another node of type \c T that can be reached using a given traverse 1848 /// function. 1849 template <typename T> class TypeTraverseMatcher : public MatcherInterface<T> { 1850 DynTypedMatcher InnerMatcher; 1851 1852 public: 1853 explicit TypeTraverseMatcher(const Matcher<QualType> &InnerMatcher, 1854 QualType (T::*TraverseFunction)() const) 1855 : InnerMatcher(InnerMatcher), TraverseFunction(TraverseFunction) {} 1856 1857 bool matches(const T &Node, ASTMatchFinder *Finder, 1858 BoundNodesTreeBuilder *Builder) const override { 1859 QualType NextNode = (Node.*TraverseFunction)(); 1860 if (NextNode.isNull()) 1861 return false; 1862 return this->InnerMatcher.matches(DynTypedNode::create(NextNode), Finder, 1863 Builder); 1864 } 1865 1866 private: 1867 QualType (T::*TraverseFunction)() const; 1868 }; 1869 1870 /// Matches nodes of type \c T in a ..Loc hierarchy, for which the inner 1871 /// matcher matches on a another node of type \c T that can be reached using a 1872 /// given traverse function. 1873 template <typename T> 1874 class TypeLocTraverseMatcher : public MatcherInterface<T> { 1875 DynTypedMatcher InnerMatcher; 1876 1877 public: 1878 explicit TypeLocTraverseMatcher(const Matcher<TypeLoc> &InnerMatcher, 1879 TypeLoc (T::*TraverseFunction)() const) 1880 : InnerMatcher(InnerMatcher), TraverseFunction(TraverseFunction) {} 1881 1882 bool matches(const T &Node, ASTMatchFinder *Finder, 1883 BoundNodesTreeBuilder *Builder) const override { 1884 TypeLoc NextNode = (Node.*TraverseFunction)(); 1885 if (!NextNode) 1886 return false; 1887 return this->InnerMatcher.matches(DynTypedNode::create(NextNode), Finder, 1888 Builder); 1889 } 1890 1891 private: 1892 TypeLoc (T::*TraverseFunction)() const; 1893 }; 1894 1895 /// Converts a \c Matcher<InnerT> to a \c Matcher<OuterT>, where 1896 /// \c OuterT is any type that is supported by \c Getter. 1897 /// 1898 /// \code Getter<OuterT>::value() \endcode returns a 1899 /// \code InnerTBase (OuterT::*)() \endcode, which is used to adapt a \c OuterT 1900 /// object into a \c InnerT 1901 template <typename InnerTBase, 1902 template <typename OuterT> class Getter, 1903 template <typename OuterT> class MatcherImpl, 1904 typename ReturnTypesF> 1905 class TypeTraversePolymorphicMatcher { 1906 private: 1907 using Self = TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, 1908 ReturnTypesF>; 1909 1910 static Self create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers); 1911 1912 public: 1913 using ReturnTypes = typename ExtractFunctionArgMeta<ReturnTypesF>::type; 1914 1915 explicit TypeTraversePolymorphicMatcher( 1916 ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) 1917 : InnerMatcher(makeAllOfComposite(InnerMatchers)) {} 1918 1919 template <typename OuterT> operator Matcher<OuterT>() const { 1920 return Matcher<OuterT>( 1921 new MatcherImpl<OuterT>(InnerMatcher, Getter<OuterT>::value())); 1922 } 1923 1924 struct Func 1925 : public VariadicFunction<Self, Matcher<InnerTBase>, &Self::create> { 1926 Func() {} 1927 }; 1928 1929 private: 1930 Matcher<InnerTBase> InnerMatcher; 1931 }; 1932 1933 /// A simple memoizer of T(*)() functions. 1934 /// 1935 /// It will call the passed 'Func' template parameter at most once. 1936 /// Used to support AST_MATCHER_FUNCTION() macro. 1937 template <typename Matcher, Matcher (*Func)()> class MemoizedMatcher { 1938 struct Wrapper { 1939 Wrapper() : M(Func()) {} 1940 1941 Matcher M; 1942 }; 1943 1944 public: 1945 static const Matcher &getInstance() { 1946 static llvm::ManagedStatic<Wrapper> Instance; 1947 return Instance->M; 1948 } 1949 }; 1950 1951 // Define the create() method out of line to silence a GCC warning about 1952 // the struct "Func" having greater visibility than its base, which comes from 1953 // using the flag -fvisibility-inlines-hidden. 1954 template <typename InnerTBase, template <typename OuterT> class Getter, 1955 template <typename OuterT> class MatcherImpl, typename ReturnTypesF> 1956 TypeTraversePolymorphicMatcher<InnerTBase, Getter, MatcherImpl, ReturnTypesF> 1957 TypeTraversePolymorphicMatcher< 1958 InnerTBase, Getter, MatcherImpl, 1959 ReturnTypesF>::create(ArrayRef<const Matcher<InnerTBase> *> InnerMatchers) { 1960 return Self(InnerMatchers); 1961 } 1962 1963 // FIXME: unify ClassTemplateSpecializationDecl and TemplateSpecializationType's 1964 // APIs for accessing the template argument list. 1965 inline ArrayRef<TemplateArgument> 1966 getTemplateSpecializationArgs(const ClassTemplateSpecializationDecl &D) { 1967 return D.getTemplateArgs().asArray(); 1968 } 1969 1970 inline ArrayRef<TemplateArgument> 1971 getTemplateSpecializationArgs(const TemplateSpecializationType &T) { 1972 return llvm::makeArrayRef(T.getArgs(), T.getNumArgs()); 1973 } 1974 1975 inline ArrayRef<TemplateArgument> 1976 getTemplateSpecializationArgs(const FunctionDecl &FD) { 1977 if (const auto* TemplateArgs = FD.getTemplateSpecializationArgs()) 1978 return TemplateArgs->asArray(); 1979 return ArrayRef<TemplateArgument>(); 1980 } 1981 1982 struct NotEqualsBoundNodePredicate { 1983 bool operator()(const internal::BoundNodesMap &Nodes) const { 1984 return Nodes.getNode(ID) != Node; 1985 } 1986 1987 std::string ID; 1988 DynTypedNode Node; 1989 }; 1990 1991 template <typename Ty, typename Enable = void> struct GetBodyMatcher { 1992 static const Stmt *get(const Ty &Node) { return Node.getBody(); } 1993 }; 1994 1995 template <typename Ty> 1996 struct GetBodyMatcher<Ty, typename std::enable_if< 1997 std::is_base_of<FunctionDecl, Ty>::value>::type> { 1998 static const Stmt *get(const Ty &Node) { 1999 return Node.doesThisDeclarationHaveABody() ? Node.getBody() : nullptr; 2000 } 2001 }; 2002 2003 template <typename NodeType> 2004 inline Optional<BinaryOperatorKind> 2005 equivalentBinaryOperator(const NodeType &Node) { 2006 return Node.getOpcode(); 2007 } 2008 2009 template <> 2010 inline Optional<BinaryOperatorKind> 2011 equivalentBinaryOperator<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) { 2012 if (Node.getNumArgs() != 2) 2013 return None; 2014 switch (Node.getOperator()) { 2015 default: 2016 return None; 2017 case OO_ArrowStar: 2018 return BO_PtrMemI; 2019 case OO_Star: 2020 return BO_Mul; 2021 case OO_Slash: 2022 return BO_Div; 2023 case OO_Percent: 2024 return BO_Rem; 2025 case OO_Plus: 2026 return BO_Add; 2027 case OO_Minus: 2028 return BO_Sub; 2029 case OO_LessLess: 2030 return BO_Shl; 2031 case OO_GreaterGreater: 2032 return BO_Shr; 2033 case OO_Spaceship: 2034 return BO_Cmp; 2035 case OO_Less: 2036 return BO_LT; 2037 case OO_Greater: 2038 return BO_GT; 2039 case OO_LessEqual: 2040 return BO_LE; 2041 case OO_GreaterEqual: 2042 return BO_GE; 2043 case OO_EqualEqual: 2044 return BO_EQ; 2045 case OO_ExclaimEqual: 2046 return BO_NE; 2047 case OO_Amp: 2048 return BO_And; 2049 case OO_Caret: 2050 return BO_Xor; 2051 case OO_Pipe: 2052 return BO_Or; 2053 case OO_AmpAmp: 2054 return BO_LAnd; 2055 case OO_PipePipe: 2056 return BO_LOr; 2057 case OO_Equal: 2058 return BO_Assign; 2059 case OO_StarEqual: 2060 return BO_MulAssign; 2061 case OO_SlashEqual: 2062 return BO_DivAssign; 2063 case OO_PercentEqual: 2064 return BO_RemAssign; 2065 case OO_PlusEqual: 2066 return BO_AddAssign; 2067 case OO_MinusEqual: 2068 return BO_SubAssign; 2069 case OO_LessLessEqual: 2070 return BO_ShlAssign; 2071 case OO_GreaterGreaterEqual: 2072 return BO_ShrAssign; 2073 case OO_AmpEqual: 2074 return BO_AndAssign; 2075 case OO_CaretEqual: 2076 return BO_XorAssign; 2077 case OO_PipeEqual: 2078 return BO_OrAssign; 2079 case OO_Comma: 2080 return BO_Comma; 2081 } 2082 } 2083 2084 template <typename NodeType> 2085 inline Optional<UnaryOperatorKind> 2086 equivalentUnaryOperator(const NodeType &Node) { 2087 return Node.getOpcode(); 2088 } 2089 2090 template <> 2091 inline Optional<UnaryOperatorKind> 2092 equivalentUnaryOperator<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) { 2093 if (Node.getNumArgs() != 1 && Node.getOperator() != OO_PlusPlus && 2094 Node.getOperator() != OO_MinusMinus) 2095 return None; 2096 switch (Node.getOperator()) { 2097 default: 2098 return None; 2099 case OO_Plus: 2100 return UO_Plus; 2101 case OO_Minus: 2102 return UO_Minus; 2103 case OO_Amp: 2104 return UO_AddrOf; 2105 case OO_Star: 2106 return UO_Deref; 2107 case OO_Tilde: 2108 return UO_Not; 2109 case OO_Exclaim: 2110 return UO_LNot; 2111 case OO_PlusPlus: { 2112 const auto *FD = Node.getDirectCallee(); 2113 if (!FD) 2114 return None; 2115 return FD->getNumParams() > 0 ? UO_PostInc : UO_PreInc; 2116 } 2117 case OO_MinusMinus: { 2118 const auto *FD = Node.getDirectCallee(); 2119 if (!FD) 2120 return None; 2121 return FD->getNumParams() > 0 ? UO_PostDec : UO_PreDec; 2122 } 2123 case OO_Coawait: 2124 return UO_Coawait; 2125 } 2126 } 2127 2128 template <typename NodeType> inline const Expr *getLHS(const NodeType &Node) { 2129 return Node.getLHS(); 2130 } 2131 template <> 2132 inline const Expr * 2133 getLHS<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) { 2134 if (!internal::equivalentBinaryOperator(Node)) 2135 return nullptr; 2136 return Node.getArg(0); 2137 } 2138 template <typename NodeType> inline const Expr *getRHS(const NodeType &Node) { 2139 return Node.getRHS(); 2140 } 2141 template <> 2142 inline const Expr * 2143 getRHS<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) { 2144 if (!internal::equivalentBinaryOperator(Node)) 2145 return nullptr; 2146 return Node.getArg(1); 2147 } 2148 template <typename NodeType> 2149 inline const Expr *getSubExpr(const NodeType &Node) { 2150 return Node.getSubExpr(); 2151 } 2152 template <> 2153 inline const Expr * 2154 getSubExpr<CXXOperatorCallExpr>(const CXXOperatorCallExpr &Node) { 2155 if (!internal::equivalentUnaryOperator(Node)) 2156 return nullptr; 2157 return Node.getArg(0); 2158 } 2159 2160 template <typename Ty> 2161 struct HasSizeMatcher { 2162 static bool hasSize(const Ty &Node, unsigned int N) { 2163 return Node.getSize() == N; 2164 } 2165 }; 2166 2167 template <> 2168 inline bool HasSizeMatcher<StringLiteral>::hasSize( 2169 const StringLiteral &Node, unsigned int N) { 2170 return Node.getLength() == N; 2171 } 2172 2173 template <typename Ty> 2174 struct GetSourceExpressionMatcher { 2175 static const Expr *get(const Ty &Node) { 2176 return Node.getSubExpr(); 2177 } 2178 }; 2179 2180 template <> 2181 inline const Expr *GetSourceExpressionMatcher<OpaqueValueExpr>::get( 2182 const OpaqueValueExpr &Node) { 2183 return Node.getSourceExpr(); 2184 } 2185 2186 template <typename Ty> 2187 struct CompoundStmtMatcher { 2188 static const CompoundStmt *get(const Ty &Node) { 2189 return &Node; 2190 } 2191 }; 2192 2193 template <> 2194 inline const CompoundStmt * 2195 CompoundStmtMatcher<StmtExpr>::get(const StmtExpr &Node) { 2196 return Node.getSubStmt(); 2197 } 2198 2199 /// If \p Loc is (transitively) expanded from macro \p MacroName, returns the 2200 /// location (in the chain of expansions) at which \p MacroName was 2201 /// expanded. Since the macro may have been expanded inside a series of 2202 /// expansions, that location may itself be a MacroID. 2203 llvm::Optional<SourceLocation> 2204 getExpansionLocOfMacro(StringRef MacroName, SourceLocation Loc, 2205 const ASTContext &Context); 2206 2207 inline Optional<StringRef> getOpName(const UnaryOperator &Node) { 2208 return Node.getOpcodeStr(Node.getOpcode()); 2209 } 2210 inline Optional<StringRef> getOpName(const BinaryOperator &Node) { 2211 return Node.getOpcodeStr(); 2212 } 2213 inline StringRef getOpName(const CXXRewrittenBinaryOperator &Node) { 2214 return Node.getOpcodeStr(); 2215 } 2216 inline Optional<StringRef> getOpName(const CXXOperatorCallExpr &Node) { 2217 auto optBinaryOpcode = equivalentBinaryOperator(Node); 2218 if (!optBinaryOpcode) { 2219 auto optUnaryOpcode = equivalentUnaryOperator(Node); 2220 if (!optUnaryOpcode) 2221 return None; 2222 return UnaryOperator::getOpcodeStr(*optUnaryOpcode); 2223 } 2224 return BinaryOperator::getOpcodeStr(*optBinaryOpcode); 2225 } 2226 2227 /// Matches overloaded operators with a specific name. 2228 /// 2229 /// The type argument ArgT is not used by this matcher but is used by 2230 /// PolymorphicMatcher and should be std::vector<std::string>>. 2231 template <typename T, typename ArgT = std::vector<std::string>> 2232 class HasAnyOperatorNameMatcher : public SingleNodeMatcherInterface<T> { 2233 static_assert(std::is_same<T, BinaryOperator>::value || 2234 std::is_same<T, CXXOperatorCallExpr>::value || 2235 std::is_same<T, CXXRewrittenBinaryOperator>::value || 2236 std::is_same<T, UnaryOperator>::value, 2237 "Matcher only supports `BinaryOperator`, `UnaryOperator`, " 2238 "`CXXOperatorCallExpr` and `CXXRewrittenBinaryOperator`"); 2239 static_assert(std::is_same<ArgT, std::vector<std::string>>::value, 2240 "Matcher ArgT must be std::vector<std::string>"); 2241 2242 public: 2243 explicit HasAnyOperatorNameMatcher(std::vector<std::string> Names) 2244 : SingleNodeMatcherInterface<T>(), Names(std::move(Names)) {} 2245 2246 bool matchesNode(const T &Node) const override { 2247 Optional<StringRef> OptOpName = getOpName(Node); 2248 if (!OptOpName) 2249 return false; 2250 return llvm::any_of(Names, [OpName = *OptOpName](const std::string &Name) { 2251 return Name == OpName; 2252 }); 2253 } 2254 2255 private: 2256 static Optional<StringRef> getOpName(const UnaryOperator &Node) { 2257 return Node.getOpcodeStr(Node.getOpcode()); 2258 } 2259 static Optional<StringRef> getOpName(const BinaryOperator &Node) { 2260 return Node.getOpcodeStr(); 2261 } 2262 static StringRef getOpName(const CXXRewrittenBinaryOperator &Node) { 2263 return Node.getOpcodeStr(); 2264 } 2265 static Optional<StringRef> getOpName(const CXXOperatorCallExpr &Node) { 2266 auto optBinaryOpcode = equivalentBinaryOperator(Node); 2267 if (!optBinaryOpcode) { 2268 auto optUnaryOpcode = equivalentUnaryOperator(Node); 2269 if (!optUnaryOpcode) 2270 return None; 2271 return UnaryOperator::getOpcodeStr(*optUnaryOpcode); 2272 } 2273 return BinaryOperator::getOpcodeStr(*optBinaryOpcode); 2274 } 2275 2276 std::vector<std::string> Names; 2277 }; 2278 2279 using HasOpNameMatcher = 2280 PolymorphicMatcher<HasAnyOperatorNameMatcher, 2281 void( 2282 TypeList<BinaryOperator, CXXOperatorCallExpr, 2283 CXXRewrittenBinaryOperator, UnaryOperator>), 2284 std::vector<std::string>>; 2285 2286 HasOpNameMatcher hasAnyOperatorNameFunc(ArrayRef<const StringRef *> NameRefs); 2287 2288 using HasOverloadOpNameMatcher = 2289 PolymorphicMatcher<HasOverloadedOperatorNameMatcher, 2290 void(TypeList<CXXOperatorCallExpr, FunctionDecl>), 2291 std::vector<std::string>>; 2292 2293 HasOverloadOpNameMatcher 2294 hasAnyOverloadedOperatorNameFunc(ArrayRef<const StringRef *> NameRefs); 2295 2296 /// Returns true if \p Node has a base specifier matching \p BaseSpec. 2297 /// 2298 /// A class is not considered to be derived from itself. 2299 bool matchesAnyBase(const CXXRecordDecl &Node, 2300 const Matcher<CXXBaseSpecifier> &BaseSpecMatcher, 2301 ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder); 2302 2303 std::shared_ptr<llvm::Regex> createAndVerifyRegex(StringRef Regex, 2304 llvm::Regex::RegexFlags Flags, 2305 StringRef MatcherID); 2306 2307 } // namespace internal 2308 2309 } // namespace ast_matchers 2310 2311 } // namespace clang 2312 2313 #endif // LLVM_CLANG_ASTMATCHERS_ASTMATCHERSINTERNAL_H 2314