diff options
Diffstat (limited to 'include/clang/AST')
| -rw-r--r-- | include/clang/AST/ASTContext.h | 129 | ||||
| -rw-r--r-- | include/clang/AST/ASTTypeTraits.h | 211 |
2 files changed, 339 insertions, 1 deletions
diff --git a/include/clang/AST/ASTContext.h b/include/clang/AST/ASTContext.h index 7c02699ee4..d12d0545c5 100644 --- a/include/clang/AST/ASTContext.h +++ b/include/clang/AST/ASTContext.h @@ -15,6 +15,7 @@ #ifndef LLVM_CLANG_AST_ASTCONTEXT_H #define LLVM_CLANG_AST_ASTCONTEXT_H +#include "clang/AST/ASTTypeTraits.h" #include "clang/AST/CanonicalType.h" #include "clang/AST/CommentCommandTraits.h" #include "clang/AST/Decl.h" @@ -22,6 +23,7 @@ #include "clang/AST/NestedNameSpecifier.h" #include "clang/AST/PrettyPrinter.h" #include "clang/AST/RawCommentList.h" +#include "clang/AST/RecursiveASTVisitor.h" #include "clang/AST/TemplateName.h" #include "clang/AST/Type.h" #include "clang/Basic/AddressSpaces.h" @@ -382,6 +384,58 @@ public: OwningPtr<ExternalASTSource> ExternalSource; ASTMutationListener *Listener; + /// \brief Contains parents of a node. + typedef llvm::SmallVector<ast_type_traits::DynTypedNode, 1> ParentVector; + + /// \brief Maps from a node to its parents. + typedef llvm::DenseMap<const void *, ParentVector> ParentMap; + + /// \brief Returns the parents of the given node. + /// + /// Note that this will lazily compute the parents of all nodes + /// and store them for later retrieval. Thus, the first call is O(n) + /// in the number of AST nodes. + /// + /// Caveats and FIXMEs: + /// Calculating the parent map over all AST nodes will need to load the + /// full AST. This can be undesirable in the case where the full AST is + /// expensive to create (for example, when using precompiled header + /// preambles). Thus, there are good opportunities for optimization here. + /// One idea is to walk the given node downwards, looking for references + /// to declaration contexts - once a declaration context is found, compute + /// the parent map for the declaration context; if that can satisfy the + /// request, loading the whole AST can be avoided. Note that this is made + /// more complex by statements in templates having multiple parents - those + /// problems can be solved by building closure over the templated parts of + /// the AST, which also avoids touching large parts of the AST. + /// Additionally, we will want to add an interface to already give a hint + /// where to search for the parents, for example when looking at a statement + /// inside a certain function. + /// + /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc, + /// NestedNameSpecifier or NestedNameSpecifierLoc. + template <typename NodeT> + ParentVector getParents(const NodeT &Node) { + return getParents(ast_type_traits::DynTypedNode::create(Node)); + } + + ParentVector getParents(const ast_type_traits::DynTypedNode &Node) { + assert(Node.getMemoizationData() && + "Invariant broken: only nodes that support memoization may be " + "used in the parent map."); + if (!AllParents) { + // We always need to run over the whole translation unit, as + // hasAncestor can escape any subtree. + AllParents.reset( + ParentMapASTVisitor::buildMap(*getTranslationUnitDecl())); + } + ParentMap::const_iterator I = AllParents->find(Node.getMemoizationData()); + if (I == AllParents->end()) { + return ParentVector(); + } + return I->second; + } + const clang::PrintingPolicy &getPrintingPolicy() const { return PrintingPolicy; } @@ -2136,8 +2190,81 @@ private: friend class DeclContext; friend class DeclarationNameTable; void ReleaseDeclContextMaps(); + + /// \brief A \c RecursiveASTVisitor that builds a map from nodes to their + /// parents as defined by the \c RecursiveASTVisitor. + /// + /// Note that the relationship described here is purely in terms of AST + /// traversal - there are other relationships (for example declaration context) + /// in the AST that are better modeled by special matchers. + /// + /// FIXME: Currently only builds up the map using \c Stmt and \c Decl nodes. + class ParentMapASTVisitor : public RecursiveASTVisitor<ParentMapASTVisitor> { + public: + /// \brief Builds and returns the translation unit's parent map. + /// + /// The caller takes ownership of the returned \c ParentMap. + static ParentMap *buildMap(TranslationUnitDecl &TU) { + ParentMapASTVisitor Visitor(new ParentMap); + Visitor.TraverseDecl(&TU); + return Visitor.Parents; + } + + private: + typedef RecursiveASTVisitor<ParentMapASTVisitor> VisitorBase; + + ParentMapASTVisitor(ParentMap *Parents) : Parents(Parents) { + } + + bool shouldVisitTemplateInstantiations() const { + return true; + } + bool shouldVisitImplicitCode() const { + return true; + } + // Disables data recursion. We intercept Traverse* methods in the RAV, which + // are not triggered during data recursion. + bool shouldUseDataRecursionFor(clang::Stmt *S) const { + return false; + } + + template <typename T> + bool TraverseNode(T *Node, bool(VisitorBase:: *traverse) (T *)) { + if (Node == NULL) + return true; + if (ParentStack.size() > 0) + // FIXME: Currently we add the same parent multiple times, for example + // when we visit all subexpressions of template instantiations; this is + // suboptimal, bug benign: the only way to visit those is with + // hasAncestor / hasParent, and those do not create new matches. + // The plan is to enable DynTypedNode to be storable in a map or hash + // map. The main problem there is to implement hash functions / + // comparison operators for all types that DynTypedNode supports that + // do not have pointer identity. + (*Parents)[Node].push_back(ParentStack.back()); + ParentStack.push_back(ast_type_traits::DynTypedNode::create(*Node)); + bool Result = (this ->* traverse) (Node); + ParentStack.pop_back(); + return Result; + } + + bool TraverseDecl(Decl *DeclNode) { + return TraverseNode(DeclNode, &VisitorBase::TraverseDecl); + } + + bool TraverseStmt(Stmt *StmtNode) { + return TraverseNode(StmtNode, &VisitorBase::TraverseStmt); + } + + ParentMap *Parents; + llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack; + + friend class RecursiveASTVisitor<ParentMapASTVisitor>; + }; + + llvm::OwningPtr<ParentMap> AllParents; }; - + /// \brief Utility function for constructing a nullary selector. static inline Selector GetNullarySelector(StringRef name, ASTContext& Ctx) { IdentifierInfo* II = &Ctx.Idents.get(name); diff --git a/include/clang/AST/ASTTypeTraits.h b/include/clang/AST/ASTTypeTraits.h new file mode 100644 index 0000000000..4688b12de7 --- /dev/null +++ b/include/clang/AST/ASTTypeTraits.h @@ -0,0 +1,211 @@ +//===--- ASTTypeTraits.h ----------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Provides a dynamically typed node container that can be used to store +// an AST base node at runtime in the same storage in a type safe way. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_AST_TYPE_TRAITS_H +#define LLVM_CLANG_AST_AST_TYPE_TRAITS_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/TypeLoc.h" +#include "llvm/Support/AlignOf.h" + +namespace clang { +namespace ast_type_traits { + +/// \brief A dynamically typed AST node container. +/// +/// Stores an AST node in a type safe way. This allows writing code that +/// works with different kinds of AST nodes, despite the fact that they don't +/// have a common base class. +/// +/// Use \c create(Node) to create a \c DynTypedNode from an AST node, +/// and \c get<T>() to retrieve the node as type T if the types match. +/// +/// See \c NodeTypeTag for which node base types are currently supported; +/// You can create DynTypedNodes for all nodes in the inheritance hierarchy of +/// the supported base types. +class DynTypedNode { +public: + /// \brief Creates a \c DynTypedNode from \c Node. + template <typename T> + static DynTypedNode create(const T &Node) { + return BaseConverter<T>::create(Node); + } + + /// \brief Retrieve the stored node as type \c T. + /// + /// Returns NULL if the stored node does not have a type that is + /// convertible to \c T. + /// + /// For types that have identity via their pointer in the AST + /// (like \c Stmt and \c Decl) the returned pointer points to the + /// referenced AST node. + /// For other types (like \c QualType) the value is stored directly + /// in the \c DynTypedNode, and the returned pointer points at + /// the storage inside DynTypedNode. For those nodes, do not + /// use the pointer outside the scope of the DynTypedNode. + template <typename T> + const T *get() const { + return BaseConverter<T>::get(Tag, Storage.buffer); + } + + /// \brief Returns a pointer that identifies the stored AST node. + /// + /// Note that this is not supported by all AST nodes. For AST nodes + /// that don't have a pointer-defined identity inside the AST, this + /// method returns NULL. + const void *getMemoizationData() const; + +private: + /// \brief Takes care of converting from and to \c T. + template <typename T, typename EnablerT = void> struct BaseConverter; + + /// \brief Supported base node types. + enum NodeTypeTag { + NT_Decl, + NT_Stmt, + NT_NestedNameSpecifier, + NT_NestedNameSpecifierLoc, + NT_QualType, + NT_Type, + NT_TypeLoc + } Tag; + + /// \brief Stores the data of the node. + /// + /// Note that we can store \c Decls and \c Stmts by pointer as they are + /// guaranteed to be unique pointers pointing to dedicated storage in the + /// AST. \c QualTypes on the other hand do not have storage or unique + /// pointers and thus need to be stored by value. + llvm::AlignedCharArrayUnion<Decl *, Stmt *, NestedNameSpecifier, + NestedNameSpecifierLoc, QualType, Type, + TypeLoc> Storage; +}; + +// FIXME: Pull out abstraction for the following. +template<typename T> struct DynTypedNode::BaseConverter<T, + typename llvm::enable_if<llvm::is_base_of<Decl, T> >::type> { + static const T *get(NodeTypeTag Tag, const char Storage[]) { + if (Tag == NT_Decl) + return dyn_cast<T>(*reinterpret_cast<Decl*const*>(Storage)); + return NULL; + } + static DynTypedNode create(const Decl &Node) { + DynTypedNode Result; + Result.Tag = NT_Decl; + new (Result.Storage.buffer) const Decl*(&Node); + return Result; + } +}; +template<typename T> struct DynTypedNode::BaseConverter<T, + typename llvm::enable_if<llvm::is_base_of<Stmt, T> >::type> { + static const T *get(NodeTypeTag Tag, const char Storage[]) { + if (Tag == NT_Stmt) + return dyn_cast<T>(*reinterpret_cast<Stmt*const*>(Storage)); + return NULL; + } + static DynTypedNode create(const Stmt &Node) { + DynTypedNode Result; + Result.Tag = NT_Stmt; + new (Result.Storage.buffer) const Stmt*(&Node); + return Result; + } +}; +template<typename T> struct DynTypedNode::BaseConverter<T, + typename llvm::enable_if<llvm::is_base_of<Type, T> >::type> { + static const T *get(NodeTypeTag Tag, const char Storage[]) { + if (Tag == NT_Type) + return dyn_cast<T>(*reinterpret_cast<Type*const*>(Storage)); + return NULL; + } + static DynTypedNode create(const Type &Node) { + DynTypedNode Result; + Result.Tag = NT_Type; + new (Result.Storage.buffer) const Type*(&Node); + return Result; + } +}; +template<> struct DynTypedNode::BaseConverter<NestedNameSpecifier, void> { + static const NestedNameSpecifier *get(NodeTypeTag Tag, const char Storage[]) { + if (Tag == NT_NestedNameSpecifier) + return *reinterpret_cast<NestedNameSpecifier*const*>(Storage); + return NULL; + } + static DynTypedNode create(const NestedNameSpecifier &Node) { + DynTypedNode Result; + Result.Tag = NT_NestedNameSpecifier; + new (Result.Storage.buffer) const NestedNameSpecifier*(&Node); + return Result; + } +}; +template<> struct DynTypedNode::BaseConverter<NestedNameSpecifierLoc, void> { + static const NestedNameSpecifierLoc *get(NodeTypeTag Tag, + const char Storage[]) { + if (Tag == NT_NestedNameSpecifierLoc) + return reinterpret_cast<const NestedNameSpecifierLoc*>(Storage); + return NULL; + } + static DynTypedNode create(const NestedNameSpecifierLoc &Node) { + DynTypedNode Result; + Result.Tag = NT_NestedNameSpecifierLoc; + new (Result.Storage.buffer) NestedNameSpecifierLoc(Node); + return Result; + } +}; +template<> struct DynTypedNode::BaseConverter<QualType, void> { + static const QualType *get(NodeTypeTag Tag, const char Storage[]) { + if (Tag == NT_QualType) + return reinterpret_cast<const QualType*>(Storage); + return NULL; + } + static DynTypedNode create(const QualType &Node) { + DynTypedNode Result; + Result.Tag = NT_QualType; + new (Result.Storage.buffer) QualType(Node); + return Result; + } +}; +template<> struct DynTypedNode::BaseConverter<TypeLoc, void> { + static const TypeLoc *get(NodeTypeTag Tag, const char Storage[]) { + if (Tag == NT_TypeLoc) + return reinterpret_cast<const TypeLoc*>(Storage); + return NULL; + } + static DynTypedNode create(const TypeLoc &Node) { + DynTypedNode Result; + Result.Tag = NT_TypeLoc; + new (Result.Storage.buffer) TypeLoc(Node); + return Result; + } +}; +// The only operation we allow on unsupported types is \c get. +// This allows to conveniently use \c DynTypedNode when having an arbitrary +// AST node that is not supported, but prevents misuse - a user cannot create +// a DynTypedNode from arbitrary types. +template <typename T, typename EnablerT> struct DynTypedNode::BaseConverter { + static const T *get(NodeTypeTag Tag, const char Storage[]) { return NULL; } +}; + +inline const void *DynTypedNode::getMemoizationData() const { + switch (Tag) { + case NT_Decl: return BaseConverter<Decl>::get(Tag, Storage.buffer); + case NT_Stmt: return BaseConverter<Stmt>::get(Tag, Storage.buffer); + default: return NULL; + }; +} + +} // end namespace ast_type_traits +} // end namespace clang + +#endif // LLVM_CLANG_AST_AST_TYPE_TRAITS_H |