//===--- ASTMatchersInternal.h - Structural query framework -----*- C++ -*-===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // Implements the base layer of the matcher framework. // // Matchers are methods that return a Matcher which provides a method // Matches(...) which is a predicate on an AST node. The Matches method's // parameters define the context of the match, which allows matchers to recurse // or store the current node as bound to a specific string, so that it can be // retrieved later. // // In general, matchers have two parts: // 1. A function Matcher MatcherName() which returns a Matcher // based on the arguments and optionally on template type deduction based // on the arguments. Matchers form an implicit reverse hierarchy // to clang's AST class hierarchy, meaning that you can use a Matcher // everywhere a Matcher is required. // 2. An implementation of a class derived from MatcherInterface. // // The matcher functions are defined in ASTMatchers.h. To make it possible // to implement both the matcher function and the implementation of the matcher // interface in one place, ASTMatcherMacros.h defines macros that allow // implementing a matcher in a single place. // // This file contains the base classes needed to construct the actual matchers. // //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_INTERNAL_H #define LLVM_CLANG_AST_MATCHERS_AST_MATCHERS_INTERNAL_H #include "clang/AST/ASTTypeTraits.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/Decl.h" #include "clang/AST/ExprCXX.h" #include "clang/AST/StmtCXX.h" #include "clang/AST/Stmt.h" #include "clang/AST/Type.h" #include "llvm/ADT/VariadicFunction.h" #include "llvm/Support/type_traits.h" #include #include #include namespace clang { namespace ast_matchers { /// FIXME: Move into the llvm support library. template struct CompileAssert {}; #define TOOLING_COMPILE_ASSERT(Expr, Msg) \ typedef CompileAssert<(bool(Expr))> Msg[bool(Expr) ? 1 : -1] class BoundNodes; namespace internal { class BoundNodesTreeBuilder; /// \brief Internal version of BoundNodes. Holds all the bound nodes. class BoundNodesMap { public: /// \brief Adds \c Node to the map with key \c ID. /// /// The node's base type should be in NodeBaseType or it will be unaccessible. template void addNode(StringRef ID, const T* Node) { NodeMap[ID] = ast_type_traits::DynTypedNode::create(*Node); } void addNode(StringRef ID, ast_type_traits::DynTypedNode Node) { NodeMap[ID] = Node; } /// \brief Returns the AST node bound to \c ID. /// /// Returns NULL if there was no node bound to \c ID or if there is a node but /// it cannot be converted to the specified type. template const T *getNodeAs(StringRef ID) const { IDToNodeMap::const_iterator It = NodeMap.find(ID); if (It == NodeMap.end()) { return NULL; } return It->second.get(); } /// \brief Copies all ID/Node pairs to BoundNodesTreeBuilder \c Builder. void copyTo(BoundNodesTreeBuilder *Builder) const; /// \brief Copies all ID/Node pairs to BoundNodesMap \c Other. void copyTo(BoundNodesMap *Other) const; private: /// \brief A map from IDs to the bound nodes. typedef std::map IDToNodeMap; IDToNodeMap NodeMap; }; /// \brief A tree of bound nodes in match results. /// /// If a match can contain multiple matches on the same node with different /// matching subexpressions, BoundNodesTree contains a branch for each of /// those matching subexpressions. /// /// BoundNodesTree's are created during the matching process; when a match /// is found, we iterate over the tree and create a BoundNodes object containing /// the union of all bound nodes on the path from the root to a each leaf. class BoundNodesTree { public: /// \brief A visitor interface to visit all BoundNodes results for a /// BoundNodesTree. class Visitor { public: virtual ~Visitor() {} /// \brief Called multiple times during a single call to VisitMatches(...). /// /// 'BoundNodesView' contains the bound nodes for a single match. virtual void visitMatch(const BoundNodes& BoundNodesView) = 0; }; BoundNodesTree(); /// \brief Create a BoundNodesTree from pre-filled maps of bindings. BoundNodesTree(const BoundNodesMap& Bindings, const std::vector RecursiveBindings); /// \brief Adds all bound nodes to \c Builder. void copyTo(BoundNodesTreeBuilder* Builder) const; /// \brief Visits all matches that this BoundNodesTree represents. /// /// The ownership of 'ResultVisitor' remains at the caller. void visitMatches(Visitor* ResultVisitor); private: void visitMatchesRecursively( Visitor* ResultVistior, const BoundNodesMap& AggregatedBindings); // FIXME: Find out whether we want to use different data structures here - // first benchmarks indicate that it doesn't matter though. BoundNodesMap Bindings; std::vector RecursiveBindings; }; /// \brief Creates BoundNodesTree objects. /// /// The tree builder is used during the matching process to insert the bound /// nodes from the Id matcher. class BoundNodesTreeBuilder { public: BoundNodesTreeBuilder(); /// \brief Add a binding from an id to a node. template void setBinding(const std::string &Id, const T *Node) { Bindings.addNode(Id, Node); } void setBinding(const std::string &Id, ast_type_traits::DynTypedNode Node) { Bindings.addNode(Id, Node); } /// \brief Adds a branch in the tree. void addMatch(const BoundNodesTree& Bindings); /// \brief Returns a BoundNodes object containing all current bindings. BoundNodesTree build() const; private: BoundNodesTreeBuilder(const BoundNodesTreeBuilder &) LLVM_DELETED_FUNCTION; void operator=(const BoundNodesTreeBuilder &) LLVM_DELETED_FUNCTION; BoundNodesMap Bindings; std::vector RecursiveBindings; }; class ASTMatchFinder; /// \brief Generic interface for matchers on an AST node of type T. /// /// Implement this if your matcher may need to inspect the children or /// descendants of the node or bind matched nodes to names. If you are /// writing a simple matcher that only inspects properties of the /// current node and doesn't care about its children or descendants, /// implement SingleNodeMatcherInterface instead. template class MatcherInterface : public RefCountedBaseVPTR { public: virtual ~MatcherInterface() {} /// \brief Returns true if 'Node' can be matched. /// /// May bind 'Node' to an ID via 'Builder', or recurse into /// the AST via 'Finder'. virtual bool matches(const T &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const = 0; }; /// \brief Interface for matchers that only evaluate properties on a single /// node. template class SingleNodeMatcherInterface : public MatcherInterface { public: /// \brief Returns true if the matcher matches the provided node. /// /// A subclass must implement this instead of Matches(). virtual bool matchesNode(const T &Node) const = 0; private: /// Implements MatcherInterface::Matches. virtual bool matches(const T &Node, ASTMatchFinder * /* Finder */, BoundNodesTreeBuilder * /* Builder */) const { return matchesNode(Node); } }; /// \brief Base class for all matchers that works on a \c DynTypedNode. /// /// Matcher implementations will check whether the \c DynTypedNode is /// convertible into the respecitve types and then do the actual match /// on the actual node, or return false if it is not convertible. class DynTypedMatcher { public: virtual ~DynTypedMatcher() {} /// \brief Returns true if the matcher matches the given \c DynNode. virtual bool matches(const ast_type_traits::DynTypedNode DynNode, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const = 0; /// \brief Returns a unique ID for the matcher. virtual uint64_t getID() const = 0; }; /// \brief Wrapper of a MatcherInterface *that allows copying. /// /// A Matcher can be used anywhere a Matcher is /// required. This establishes an is-a relationship which is reverse /// to the AST hierarchy. In other words, Matcher is contravariant /// with respect to T. The relationship is built via a type conversion /// operator rather than a type hierarchy to be able to templatize the /// type hierarchy instead of spelling it out. template class Matcher : public DynTypedMatcher { public: /// \brief Takes ownership of the provided implementation pointer. explicit Matcher(MatcherInterface *Implementation) : Implementation(Implementation) {} /// \brief Implicitly converts \c Other to a Matcher. /// /// Requires \c T to be derived from \c From. template Matcher(const Matcher &Other, typename llvm::enable_if_c< llvm::is_base_of::value && !llvm::is_same::value >::type* = 0) : Implementation(new ImplicitCastMatcher(Other)) {} /// \brief Implicitly converts \c Matcher to \c Matcher. /// /// The resulting matcher is not strict, i.e. ignores qualifiers. template Matcher(const Matcher &Other, typename llvm::enable_if_c< llvm::is_same::value && llvm::is_same::value >::type* = 0) : Implementation(new TypeToQualType(Other)) {} /// \brief Forwards the call to the underlying MatcherInterface pointer. bool matches(const T &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { return Implementation->matches(Node, Finder, Builder); } /// \brief Returns an ID that uniquely identifies the matcher. uint64_t getID() const { /// FIXME: Document the requirements this imposes on matcher /// implementations (no new() implementation_ during a Matches()). return reinterpret_cast(Implementation.getPtr()); } /// \brief Returns whether the matcher matches on the given \c DynNode. virtual bool matches(const ast_type_traits::DynTypedNode DynNode, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { const T *Node = DynNode.get(); if (!Node) return false; return matches(*Node, Finder, Builder); } /// \brief Allows the conversion of a \c Matcher to a \c /// Matcher. /// /// Depending on the constructor argument, the matcher is either strict, i.e. /// does only matches in the absence of qualifiers, or not, i.e. simply /// ignores any qualifiers. template class TypeToQualType : public MatcherInterface { public: TypeToQualType(const Matcher &InnerMatcher) : InnerMatcher(InnerMatcher) {} virtual bool matches(const QualType &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { if (Node.isNull()) return false; return InnerMatcher.matches(*Node, Finder, Builder); } private: const Matcher InnerMatcher; }; private: /// \brief Allows conversion from Matcher to Matcher if T /// is derived from Base. template class ImplicitCastMatcher : public MatcherInterface { public: explicit ImplicitCastMatcher(const Matcher &From) : From(From) {} virtual bool matches(const T &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { return From.matches(Node, Finder, Builder); } private: const Matcher From; }; IntrusiveRefCntPtr< MatcherInterface > Implementation; }; // class Matcher /// \brief A convenient helper for creating a Matcher without specifying /// the template type argument. template inline Matcher makeMatcher(MatcherInterface *Implementation) { return Matcher(Implementation); } /// \brief Metafunction to determine if type T has a member called getDecl. template struct has_getDecl { struct Default { int getDecl; }; struct Derived : T, Default { }; template struct CheckT; // If T::getDecl exists, an ambiguity arises and CheckT will // not be instantiable. This makes f(...) the only available // overload. template static char (&f(CheckT*))[1]; template static char (&f(...))[2]; static bool const value = sizeof(f(0)) == 2; }; /// \brief Matches overloaded operators with a specific name. /// /// The type argument ArgT is not used by this matcher but is used by /// PolymorphicMatcherWithParam1 and should be StringRef. template class HasOverloadedOperatorNameMatcher : public SingleNodeMatcherInterface { TOOLING_COMPILE_ASSERT((llvm::is_same::value || llvm::is_same::value), unsupported_class_for_matcher); TOOLING_COMPILE_ASSERT((llvm::is_same::value), argument_type_must_be_StringRef); public: explicit HasOverloadedOperatorNameMatcher(const StringRef Name) : SingleNodeMatcherInterface(), Name(Name) {} virtual bool matchesNode(const T &Node) const LLVM_OVERRIDE { return matchesSpecialized(Node); } private: /// \brief CXXOperatorCallExpr exist only for calls to overloaded operators /// so this function returns true if the call is to an operator of the given /// name. bool matchesSpecialized(const CXXOperatorCallExpr &Node) const { return getOperatorSpelling(Node.getOperator()) == Name; } /// \brief Returns true only if CXXMethodDecl represents an overloaded /// operator and has the given operator name. bool matchesSpecialized(const CXXMethodDecl &Node) const { return Node.isOverloadedOperator() && getOperatorSpelling(Node.getOverloadedOperator()) == Name; } std::string Name; }; /// \brief Matches declarations for QualType and CallExpr. /// /// Type argument DeclMatcherT is required by PolymorphicMatcherWithParam1 but /// not actually used. template class HasDeclarationMatcher : public MatcherInterface { TOOLING_COMPILE_ASSERT((llvm::is_same< DeclMatcherT, Matcher >::value), instantiated_with_wrong_types); public: explicit HasDeclarationMatcher(const Matcher &InnerMatcher) : InnerMatcher(InnerMatcher) {} virtual bool matches(const T &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { return matchesSpecialized(Node, Finder, Builder); } private: /// \brief If getDecl exists as a member of U, returns whether the inner /// matcher matches Node.getDecl(). template bool matchesSpecialized( const U &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder, typename llvm::enable_if, int>::type = 0) const { return matchesDecl(Node.getDecl(), Finder, Builder); } /// \brief Extracts the CXXRecordDecl or EnumDecl of a QualType and returns /// whether the inner matcher matches on it. bool matchesSpecialized(const QualType &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { /// FIXME: Add other ways to convert... if (Node.isNull()) return false; if (const EnumType *AsEnum = dyn_cast(Node.getTypePtr())) return matchesDecl(AsEnum->getDecl(), Finder, Builder); return matchesDecl(Node->getAsCXXRecordDecl(), Finder, Builder); } /// \brief Gets the TemplateDecl from a TemplateSpecializationType /// and returns whether the inner matches on it. bool matchesSpecialized(const TemplateSpecializationType &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { return matchesDecl(Node.getTemplateName().getAsTemplateDecl(), Finder, Builder); } /// \brief Extracts the Decl of the callee of a CallExpr and returns whether /// the inner matcher matches on it. bool matchesSpecialized(const CallExpr &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { return matchesDecl(Node.getCalleeDecl(), Finder, Builder); } /// \brief Extracts the Decl of the constructor call and returns whether the /// inner matcher matches on it. bool matchesSpecialized(const CXXConstructExpr &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { return matchesDecl(Node.getConstructor(), Finder, Builder); } /// \brief Extracts the \c ValueDecl a \c MemberExpr refers to and returns /// whether the inner matcher matches on it. bool matchesSpecialized(const MemberExpr &Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { return matchesDecl(Node.getMemberDecl(), Finder, Builder); } /// \brief Returns whether the inner matcher \c Node. Returns false if \c Node /// is \c NULL. bool matchesDecl(const Decl *Node, ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const { return Node != NULL && InnerMatcher.matches(*Node, Finder, Builder); } const Matcher InnerMatcher; }; /// \brief IsBaseType::value is true if T is a "base" type in the AST /// node class hierarchies. template struct IsBaseType { static const bool value = (llvm::is_same::value || llvm::is_same::value || llvm::is_same::value || llvm::is_same::value || llvm::is_same::value || llvm::is_same::value || llvm::is_same::value || llvm::is_same::value); }; template const bool IsBaseType::value; /// \brief Interface that allows matchers to traverse the AST. /// FIXME: Find a better name. /// /// This provides three entry methods for each base node type in the AST: /// - \c matchesChildOf: /// Matches a matcher on every child node of the given node. Returns true /// if at least one child node could be matched. /// - \c matchesDescendantOf: /// Matches a matcher on all descendant nodes of the given node. Returns true /// if at least one descendant matched. /// - \c matchesAncestorOf: /// Matches a matcher on all ancestors of the given node. Returns true if /// at least one ancestor matched. /// /// FIXME: Currently we only allow Stmt and Decl nodes to start a traversal. /// In the future, we wan to implement this for all nodes for which it makes /// sense. In the case of matchesAncestorOf, we'll want to implement it for /// all nodes, as all nodes have ancestors. class ASTMatchFinder { public: /// \brief Defines how we descend a level in the AST when we pass /// through expressions. enum TraversalKind { /// Will traverse any child nodes. TK_AsIs, /// Will not traverse implicit casts and parentheses. TK_IgnoreImplicitCastsAndParentheses }; /// \brief Defines how bindings are processed on recursive matches. enum BindKind { /// Stop at the first match and only bind the first match. BK_First, /// Create results for all combinations of bindings that match. BK_All }; /// \brief Defines which ancestors are considered for a match. enum AncestorMatchMode { /// All ancestors. AMM_All, /// Direct parent only. AMM_ParentOnly }; virtual ~ASTMatchFinder() {} /// \brief Returns true if the given class is directly or indirectly derived /// from a base type matching \c base. /// /// A class is considered to be also derived from itself. virtual bool classIsDerivedFrom(const CXXRecordDecl *Declaration, const Matcher &Base, BoundNodesTreeBuilder *Builder) = 0; template bool matchesChildOf(const T &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, TraversalKind Traverse, BindKind Bind) { TOOLING_COMPILE_ASSERT( (llvm::is_base_of::value || llvm::is_base_of::value || llvm::is_base_of::value || llvm::is_base_of::value || llvm::is_base_of::value || llvm::is_base_of::value), unsupported_type_for_recursive_matching); return matchesChildOf(ast_type_traits::DynTypedNode::create(Node), Matcher, Builder, Traverse, Bind); } template bool matchesDescendantOf(const T &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, BindKind Bind) { TOOLING_COMPILE_ASSERT( (llvm::is_base_of::value || llvm::is_base_of::value || llvm::is_base_of::value || llvm::is_base_of::value || llvm::is_base_of::value || llvm::is_base_of::value), unsupported_type_for_recursive_matching); return matchesDescendantOf(ast_type_traits::DynTypedNode::create(Node), Matcher, Builder, Bind); } // FIXME: Implement support for BindKind. template bool matchesAncestorOf(const T &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) { TOOLING_COMPILE_ASSERT((llvm::is_base_of::value || llvm::is_base_of::value), only_Decl_or_Stmt_allowed_for_recursive_matching); return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node), Matcher, Builder, MatchMode); } virtual ASTContext &getASTContext() const = 0; protected: virtual bool matchesChildOf(const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, TraversalKind Traverse, BindKind Bind) = 0; virtual bool matchesDescendantOf(const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, BindKind Bind) = 0; virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node, const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) = 0; }; /// \brief Converts a \c Matcher to a matcher of desired type \c To by /// "adapting" a \c To into a \c T. /// /// The \c ArgumentAdapterT argument specifies how the adaptation is done. /// /// For example: /// \c ArgumentAdaptingMatcher(InnerMatcher); /// Given that \c InnerMatcher is of type \c Matcher, this returns a matcher /// that is convertible into any matcher of type \c To by constructing /// \c HasMatcher(InnerMatcher). /// /// If a matcher does not need knowledge about the inner type, prefer to use /// PolymorphicMatcherWithParam1. template