From 8a81daaa8b58aeaa192a47c4ce7f94b4d59ce082 Mon Sep 17 00:00:00 2001 From: Reid Kleckner Date: Mon, 9 Dec 2019 17:03:47 -0800 Subject: [PATCH] [AST] Split parent map traversal logic into ParentMapContext.h The only part of ASTContext.h that requires most AST types to be complete is the parent map. Nothing in Clang proper uses the ParentMap, so split it out into its own class. Make ASTContext own the ParentMapContext so there is still a one-to-one relationship. After this change, 562 fewer files depend on ASTTypeTraits.h, and 66 fewer depend on TypeLoc.h: $ diff -u deps-before.txt deps-after.txt | \ grep '^[-+] ' | sort | uniq -c | sort -nr | less 562 - ../clang/include/clang/AST/ASTTypeTraits.h 340 + ../clang/include/clang/AST/ParentMapContext.h 66 - ../clang/include/clang/AST/TypeLocNodes.def 66 - ../clang/include/clang/AST/TypeLoc.h 15 - ../clang/include/clang/AST/TemplateBase.h ... I computed deps-before.txt and deps-after.txt with `ninja -t deps`. This removes a common and key dependency on TemplateBase.h and TypeLoc.h. This also has the effect of breaking the ParentMap RecursiveASTVisitor instantiation into its own file, which roughly halves the compilation time of ASTContext.cpp (29.75s -> 17.66s). The new file takes 13.8s to compile. I left behind forwarding methods for getParents(), but clients will need to include a new header to make them work: #include "clang/AST/ParentMapContext.h" I noticed that this parent map functionality is unfortunately duplicated in ParentMap.h, which only works for Stmt nodes. Reviewed By: rsmith Differential Revision: https://reviews.llvm.org/D71313 --- .../ProBoundsArrayToPointerDecayCheck.cpp | 4 +- .../readability/MakeMemberFunctionConstCheck.cpp | 3 +- .../clang-tidy/utils/ExprSequence.cpp | 2 +- clang/include/clang/AST/ASTContext.h | 112 +-------- clang/include/clang/AST/ASTNodeTraverser.h | 1 + clang/include/clang/AST/ParentMapContext.h | 150 ++++++++++++ clang/include/clang/ASTMatchers/ASTMatchers.h | 1 + clang/include/clang/Sema/Sema.h | 1 + clang/lib/AST/ASTContext.cpp | 248 +------------------ clang/lib/AST/CMakeLists.txt | 1 + clang/lib/AST/Linkage.h | 1 + clang/lib/AST/ParentMapContext.cpp | 265 +++++++++++++++++++++ clang/lib/ASTMatchers/ASTMatchFinder.cpp | 15 +- clang/lib/ASTMatchers/ASTMatchersInternal.cpp | 7 +- clang/lib/CodeGen/CGCall.h | 1 + clang/lib/Tooling/ASTDiff/ASTDiff.cpp | 1 + .../Tooling/Refactoring/Rename/USRLocFinder.cpp | 1 + lldb/include/lldb/Symbol/TypeSystemClang.h | 1 + 18 files changed, 465 insertions(+), 350 deletions(-) create mode 100644 clang/include/clang/AST/ParentMapContext.h create mode 100644 clang/lib/AST/ParentMapContext.cpp diff --git a/clang-tools-extra/clang-tidy/cppcoreguidelines/ProBoundsArrayToPointerDecayCheck.cpp b/clang-tools-extra/clang-tidy/cppcoreguidelines/ProBoundsArrayToPointerDecayCheck.cpp index 6939ec9b2e0..760073fcaac 100644 --- a/clang-tools-extra/clang-tidy/cppcoreguidelines/ProBoundsArrayToPointerDecayCheck.cpp +++ b/clang-tools-extra/clang-tidy/cppcoreguidelines/ProBoundsArrayToPointerDecayCheck.cpp @@ -8,6 +8,7 @@ #include "ProBoundsArrayToPointerDecayCheck.h" #include "clang/AST/ASTContext.h" +#include "clang/AST/ParentMapContext.h" #include "clang/ASTMatchers/ASTMatchFinder.h" using namespace clang::ast_matchers; @@ -35,8 +36,7 @@ AST_MATCHER_P(Expr, hasParentIgnoringImpCasts, ast_matchers::internal::Matcher, InnerMatcher) { const Expr *E = &Node; do { - ASTContext::DynTypedNodeList Parents = - Finder->getASTContext().getParents(*E); + DynTypedNodeList Parents = Finder->getASTContext().getParents(*E); if (Parents.size() != 1) return false; E = Parents[0].get(); diff --git a/clang-tools-extra/clang-tidy/readability/MakeMemberFunctionConstCheck.cpp b/clang-tools-extra/clang-tidy/readability/MakeMemberFunctionConstCheck.cpp index aca8d0fe89d..3f1dcfe803e 100644 --- a/clang-tools-extra/clang-tidy/readability/MakeMemberFunctionConstCheck.cpp +++ b/clang-tools-extra/clang-tidy/readability/MakeMemberFunctionConstCheck.cpp @@ -8,6 +8,7 @@ #include "MakeMemberFunctionConstCheck.h" #include "clang/AST/ASTContext.h" +#include "clang/AST/ParentMapContext.h" #include "clang/AST/RecursiveASTVisitor.h" #include "clang/ASTMatchers/ASTMatchFinder.h" @@ -57,7 +58,7 @@ public: UsageKind Usage = Unused; template const T *getParent(const Expr *E) { - ASTContext::DynTypedNodeList Parents = Ctxt.getParents(*E); + DynTypedNodeList Parents = Ctxt.getParents(*E); if (Parents.size() != 1) return nullptr; diff --git a/clang-tools-extra/clang-tidy/utils/ExprSequence.cpp b/clang-tools-extra/clang-tidy/utils/ExprSequence.cpp index 6ed595e4a0d..3505f31c92a 100644 --- a/clang-tools-extra/clang-tidy/utils/ExprSequence.cpp +++ b/clang-tools-extra/clang-tidy/utils/ExprSequence.cpp @@ -28,7 +28,7 @@ static SmallVector getParentStmts(const Stmt *S, ASTContext *Context) { SmallVector Result; - ASTContext::DynTypedNodeList Parents = Context->getParents(*S); + DynTypedNodeList Parents = Context->getParents(*S); SmallVector NodesToProcess(Parents.begin(), Parents.end()); diff --git a/clang/include/clang/AST/ASTContext.h b/clang/include/clang/AST/ASTContext.h index f8403cf13c4..e7b0ef1e4fa 100644 --- a/clang/include/clang/AST/ASTContext.h +++ b/clang/include/clang/AST/ASTContext.h @@ -15,7 +15,7 @@ #define LLVM_CLANG_AST_ASTCONTEXT_H #include "clang/AST/ASTContextAllocate.h" -#include "clang/AST/ASTTypeTraits.h" +#include "clang/AST/ASTFwd.h" #include "clang/AST/CanonicalType.h" #include "clang/AST/CommentCommandTraits.h" #include "clang/AST/ComparisonCategories.h" @@ -26,7 +26,6 @@ #include "clang/AST/NestedNameSpecifier.h" #include "clang/AST/PrettyPrinter.h" #include "clang/AST/RawCommentList.h" -#include "clang/AST/TemplateBase.h" #include "clang/AST/TemplateName.h" #include "clang/AST/Type.h" #include "clang/Basic/AddressSpaces.h" @@ -94,6 +93,8 @@ class CXXConstructorDecl; class CXXMethodDecl; class CXXRecordDecl; class DiagnosticsEngine; +class ParentMapContext; +class DynTypedNodeList; class Expr; class FixedPointSemantics; class GlobalDecl; @@ -129,6 +130,10 @@ class VarTemplateDecl; class VTableContextBase; struct BlockVarCopyInit; +namespace ast_type_traits { +class DynTypedNode; +} + namespace Builtin { class Context; @@ -565,18 +570,9 @@ private: const TargetInfo *AuxTarget = nullptr; clang::PrintingPolicy PrintingPolicy; std::unique_ptr InterpContext; - - ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs; + std::unique_ptr ParentMapCtx; public: - ast_type_traits::TraversalKind getTraversalKind() const { return Traversal; } - void setTraversalKind(ast_type_traits::TraversalKind TK) { Traversal = TK; } - - const Expr *traverseIgnored(const Expr *E) const; - Expr *traverseIgnored(Expr *E) const; - ast_type_traits::DynTypedNode - traverseIgnored(const ast_type_traits::DynTypedNode &N) const; - IdentifierTable &Idents; SelectorTable &Selectors; Builtin::Context &BuiltinInfo; @@ -587,46 +583,8 @@ public: /// Returns the clang bytecode interpreter context. interp::Context &getInterpContext(); - /// Container for either a single DynTypedNode or for an ArrayRef to - /// DynTypedNode. For use with ParentMap. - class DynTypedNodeList { - using DynTypedNode = ast_type_traits::DynTypedNode; - - llvm::AlignedCharArrayUnion> Storage; - bool IsSingleNode; - - public: - DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) { - new (Storage.buffer) DynTypedNode(N); - } - - DynTypedNodeList(ArrayRef A) : IsSingleNode(false) { - new (Storage.buffer) ArrayRef(A); - } - - const ast_type_traits::DynTypedNode *begin() const { - if (!IsSingleNode) - return reinterpret_cast *>(Storage.buffer) - ->begin(); - return reinterpret_cast(Storage.buffer); - } - - const ast_type_traits::DynTypedNode *end() const { - if (!IsSingleNode) - return reinterpret_cast *>(Storage.buffer) - ->end(); - return reinterpret_cast(Storage.buffer) + 1; - } - - size_t size() const { return end() - begin(); } - bool empty() const { return begin() == end(); } - - const DynTypedNode &operator[](size_t N) const { - assert(N < size() && "Out of bounds!"); - return *(begin() + N); - } - }; + /// Returns the dynamic AST node parent map context. + ParentMapContext &getParentMapContext(); // A traversal scope limits the parts of the AST visible to certain analyses. // RecursiveASTVisitor::TraverseAST will only visit reachable nodes, and @@ -638,35 +596,9 @@ public: std::vector getTraversalScope() const { return TraversalScope; } void setTraversalScope(const std::vector &); - /// Returns the parents of the given node (within the traversal scope). - /// - /// 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 DynTypedNodeList getParents(const NodeT &Node) { - return getParents(ast_type_traits::DynTypedNode::create(Node)); - } - - DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node); + /// Forwards to get node parents from the ParentMapContext. New callers should + /// use ParentMapContext::getParents() directly. + template DynTypedNodeList getParents(const NodeT &Node); const clang::PrintingPolicy &getPrintingPolicy() const { return PrintingPolicy; @@ -3026,8 +2958,6 @@ private: llvm::PointerIntPair LastSDM; std::vector TraversalScope; - class ParentMap; - std::map> Parents; std::unique_ptr VTContext; @@ -3071,22 +3001,6 @@ inline Selector GetUnarySelector(StringRef name, ASTContext &Ctx) { return Ctx.Selectors.getSelector(1, &II); } -class TraversalKindScope { - ASTContext &Ctx; - ast_type_traits::TraversalKind TK = ast_type_traits::TK_AsIs; - -public: - TraversalKindScope(ASTContext &Ctx, - llvm::Optional ScopeTK) - : Ctx(Ctx) { - TK = Ctx.getTraversalKind(); - if (ScopeTK) - Ctx.setTraversalKind(*ScopeTK); - } - - ~TraversalKindScope() { Ctx.setTraversalKind(TK); } -}; - } // namespace clang // operator new and delete aren't allowed inside namespaces. diff --git a/clang/include/clang/AST/ASTNodeTraverser.h b/clang/include/clang/AST/ASTNodeTraverser.h index 9ebf64a12af..2259d7dc877 100644 --- a/clang/include/clang/AST/ASTNodeTraverser.h +++ b/clang/include/clang/AST/ASTNodeTraverser.h @@ -15,6 +15,7 @@ #ifndef LLVM_CLANG_AST_ASTNODETRAVERSER_H #define LLVM_CLANG_AST_ASTNODETRAVERSER_H +#include "clang/AST/ASTTypeTraits.h" #include "clang/AST/AttrVisitor.h" #include "clang/AST/CommentVisitor.h" #include "clang/AST/DeclVisitor.h" diff --git a/clang/include/clang/AST/ParentMapContext.h b/clang/include/clang/AST/ParentMapContext.h new file mode 100644 index 00000000000..de1f054be16 --- /dev/null +++ b/clang/include/clang/AST/ParentMapContext.h @@ -0,0 +1,150 @@ +//===- ParentMapContext.h - Map of parents using DynTypedNode -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Similar to ParentMap.h, but generalizes to non-Stmt nodes, which can have +// multiple parents. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_PARENTMAPCONTEXT_H +#define LLVM_CLANG_AST_PARENTMAPCONTEXT_H + +#include "clang/AST/ASTContext.h" +#include "clang/AST/ASTTypeTraits.h" + +namespace clang { +class DynTypedNodeList; + +class ParentMapContext { +public: + ParentMapContext(ASTContext &Ctx); + + ~ParentMapContext(); + + /// Returns the parents of the given node (within the traversal scope). + /// + /// 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 DynTypedNodeList getParents(const NodeT &Node); + + DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node); + + /// Clear parent maps. + void clear(); + + ast_type_traits::TraversalKind getTraversalKind() const { return Traversal; } + void setTraversalKind(ast_type_traits::TraversalKind TK) { Traversal = TK; } + + const Expr *traverseIgnored(const Expr *E) const; + Expr *traverseIgnored(Expr *E) const; + ast_type_traits::DynTypedNode + traverseIgnored(const ast_type_traits::DynTypedNode &N) const; + +private: + ASTContext &ASTCtx; + class ParentMap; + ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs; + std::map> Parents; +}; + +class TraversalKindScope { + ParentMapContext &Ctx; + ast_type_traits::TraversalKind TK = ast_type_traits::TK_AsIs; + +public: + TraversalKindScope(ASTContext &ASTCtx, + llvm::Optional ScopeTK) + : Ctx(ASTCtx.getParentMapContext()) { + TK = Ctx.getTraversalKind(); + if (ScopeTK) + Ctx.setTraversalKind(*ScopeTK); + } + + ~TraversalKindScope() { Ctx.setTraversalKind(TK); } +}; + +/// Container for either a single DynTypedNode or for an ArrayRef to +/// DynTypedNode. For use with ParentMap. +class DynTypedNodeList { + using DynTypedNode = ast_type_traits::DynTypedNode; + + llvm::AlignedCharArrayUnion> Storage; + bool IsSingleNode; + +public: + DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) { + new (Storage.buffer) DynTypedNode(N); + } + + DynTypedNodeList(ArrayRef A) : IsSingleNode(false) { + new (Storage.buffer) ArrayRef(A); + } + + const ast_type_traits::DynTypedNode *begin() const { + if (!IsSingleNode) + return reinterpret_cast *>(Storage.buffer) + ->begin(); + return reinterpret_cast(Storage.buffer); + } + + const ast_type_traits::DynTypedNode *end() const { + if (!IsSingleNode) + return reinterpret_cast *>(Storage.buffer) + ->end(); + return reinterpret_cast(Storage.buffer) + 1; + } + + size_t size() const { return end() - begin(); } + bool empty() const { return begin() == end(); } + + const DynTypedNode &operator[](size_t N) const { + assert(N < size() && "Out of bounds!"); + return *(begin() + N); + } +}; + +template +inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) { + return getParents(ast_type_traits::DynTypedNode::create(Node)); +} + +template +inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) { + return getParentMapContext().getParents(Node); +} + +template <> +inline DynTypedNodeList +ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) { + return getParentMapContext().getParents(Node); +} + +} // namespace clang + +#endif diff --git a/clang/include/clang/ASTMatchers/ASTMatchers.h b/clang/include/clang/ASTMatchers/ASTMatchers.h index 9a5888b7572..538babc569e 100644 --- a/clang/include/clang/ASTMatchers/ASTMatchers.h +++ b/clang/include/clang/ASTMatchers/ASTMatchers.h @@ -52,6 +52,7 @@ #include "clang/AST/DeclFriend.h" #include "clang/AST/DeclObjC.h" #include "clang/AST/DeclTemplate.h" +#include "clang/AST/ParentMapContext.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprCXX.h" #include "clang/AST/ExprObjC.h" diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h index 029637563d4..1e9ea0dd9f3 100644 --- a/clang/include/clang/Sema/Sema.h +++ b/clang/include/clang/Sema/Sema.h @@ -15,6 +15,7 @@ #define LLVM_CLANG_SEMA_SEMA_H #include "clang/AST/ASTConcept.h" +#include "clang/AST/ASTFwd.h" #include "clang/AST/Attr.h" #include "clang/AST/Availability.h" #include "clang/AST/ComparisonCategories.h" diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp index 6d1db38e36c..75919566aa8 100644 --- a/clang/lib/AST/ASTContext.cpp +++ b/clang/lib/AST/ASTContext.cpp @@ -31,13 +31,14 @@ #include "clang/AST/DeclarationName.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprCXX.h" +#include "clang/AST/ExprConcepts.h" #include "clang/AST/ExternalASTSource.h" #include "clang/AST/Mangle.h" #include "clang/AST/MangleNumberingContext.h" #include "clang/AST/NestedNameSpecifier.h" +#include "clang/AST/ParentMapContext.h" #include "clang/AST/RawCommentList.h" #include "clang/AST/RecordLayout.h" -#include "clang/AST/RecursiveASTVisitor.h" #include "clang/AST/Stmt.h" #include "clang/AST/TemplateBase.h" #include "clang/AST/TemplateName.h" @@ -99,32 +100,6 @@ using namespace clang; enum FloatingRank { Float16Rank, HalfRank, FloatRank, DoubleRank, LongDoubleRank, Float128Rank }; -const Expr *ASTContext::traverseIgnored(const Expr *E) const { - return traverseIgnored(const_cast(E)); -} - -Expr *ASTContext::traverseIgnored(Expr *E) const { - if (!E) - return nullptr; - - switch (Traversal) { - case ast_type_traits::TK_AsIs: - return E; - case ast_type_traits::TK_IgnoreImplicitCastsAndParentheses: - return E->IgnoreParenImpCasts(); - case ast_type_traits::TK_IgnoreUnlessSpelledInSource: - return E->IgnoreUnlessSpelledInSource(); - } - llvm_unreachable("Invalid Traversal type!"); -} - -ast_type_traits::DynTypedNode -ASTContext::traverseIgnored(const ast_type_traits::DynTypedNode &N) const { - if (const auto *E = N.get()) { - return ast_type_traits::DynTypedNode::create(*traverseIgnored(E)); - } - return N; -} /// \returns location that is relevant when searching for Doc comments related /// to \p D. @@ -917,6 +892,12 @@ interp::Context &ASTContext::getInterpContext() { return *InterpContext.get(); } +ParentMapContext &ASTContext::getParentMapContext() { + if (!ParentMapCtx) + ParentMapCtx.reset(new ParentMapContext(*this)); + return *ParentMapCtx.get(); +} + static const LangASMap *getAddressSpaceMap(const TargetInfo &T, const LangOptions &LOpts) { if (LOpts.FakeAddressSpaceMap) { @@ -1012,80 +993,9 @@ ASTContext::~ASTContext() { Value->~APValue(); } -class ASTContext::ParentMap { - /// Contains parents of a node. - using ParentVector = llvm::SmallVector; - - /// Maps from a node to its parents. This is used for nodes that have - /// pointer identity only, which are more common and we can save space by - /// only storing a unique pointer to them. - using ParentMapPointers = llvm::DenseMap< - const void *, - llvm::PointerUnion>; - - /// Parent map for nodes without pointer identity. We store a full - /// DynTypedNode for all keys. - using ParentMapOtherNodes = llvm::DenseMap< - ast_type_traits::DynTypedNode, - llvm::PointerUnion>; - - ParentMapPointers PointerParents; - ParentMapOtherNodes OtherParents; - class ASTVisitor; - - static ast_type_traits::DynTypedNode - getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) { - if (const auto *D = U.dyn_cast()) - return ast_type_traits::DynTypedNode::create(*D); - if (const auto *S = U.dyn_cast()) - return ast_type_traits::DynTypedNode::create(*S); - return *U.get(); - } - - template - static ASTContext::DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, - const MapTy &Map) { - auto I = Map.find(Node); - if (I == Map.end()) { - return llvm::ArrayRef(); - } - if (const auto *V = I->second.template dyn_cast()) { - return llvm::makeArrayRef(*V); - } - return getSingleDynTypedNodeFromParentMap(I->second); - } - -public: - ParentMap(ASTContext &Ctx); - ~ParentMap() { - for (const auto &Entry : PointerParents) { - if (Entry.second.is()) { - delete Entry.second.get(); - } else if (Entry.second.is()) { - delete Entry.second.get(); - } - } - for (const auto &Entry : OtherParents) { - if (Entry.second.is()) { - delete Entry.second.get(); - } else if (Entry.second.is()) { - delete Entry.second.get(); - } - } - } - - DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node) { - if (Node.getNodeKind().hasPointerIdentity()) - return getDynNodeFromMap(Node.getMemoizationData(), PointerParents); - return getDynNodeFromMap(Node, OtherParents); - } -}; - void ASTContext::setTraversalScope(const std::vector &TopLevelDecls) { TraversalScope = TopLevelDecls; - Parents.clear(); + getParentMapContext().clear(); } void ASTContext::AddDeallocation(void (*Callback)(void *), void *Data) const { @@ -10534,146 +10444,6 @@ bool ASTContext::AtomicUsesUnsupportedLibcall(const AtomicExpr *E) const { return (Size != Align || toBits(sizeChars) > MaxInlineWidthInBits); } -/// Template specializations to abstract away from pointers and TypeLocs. -/// @{ -template -static ast_type_traits::DynTypedNode createDynTypedNode(const T &Node) { - return ast_type_traits::DynTypedNode::create(*Node); -} -template <> -ast_type_traits::DynTypedNode createDynTypedNode(const TypeLoc &Node) { - return ast_type_traits::DynTypedNode::create(Node); -} -template <> -ast_type_traits::DynTypedNode -createDynTypedNode(const NestedNameSpecifierLoc &Node) { - return ast_type_traits::DynTypedNode::create(Node); -} -/// @} - -/// 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 ASTContext::ParentMap::ASTVisitor - : public RecursiveASTVisitor { -public: - ASTVisitor(ParentMap &Map, ASTContext &Context) - : Map(Map), Context(Context) {} - -private: - friend class RecursiveASTVisitor; - - using VisitorBase = RecursiveASTVisitor; - - bool shouldVisitTemplateInstantiations() const { return true; } - - bool shouldVisitImplicitCode() const { return true; } - - template - bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, - MapTy *Parents) { - if (!Node) - return true; - if (ParentStack.size() > 0) { - // FIXME: Currently we add the same parent multiple times, but only - // when no memoization data is available for the type. - // For example when we visit all subexpressions of template - // instantiations; this is suboptimal, but 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. - auto &NodeOrVector = (*Parents)[MapNode]; - if (NodeOrVector.isNull()) { - if (const auto *D = ParentStack.back().get()) - NodeOrVector = D; - else if (const auto *S = ParentStack.back().get()) - NodeOrVector = S; - else - NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back()); - } else { - if (!NodeOrVector.template is()) { - auto *Vector = new ParentVector( - 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); - delete NodeOrVector - .template dyn_cast(); - NodeOrVector = Vector; - } - - auto *Vector = NodeOrVector.template get(); - // Skip duplicates for types that have memoization data. - // We must check that the type has memoization data before calling - // std::find() because DynTypedNode::operator== can't compare all - // types. - bool Found = ParentStack.back().getMemoizationData() && - std::find(Vector->begin(), Vector->end(), - ParentStack.back()) != Vector->end(); - if (!Found) - Vector->push_back(ParentStack.back()); - } - } - ParentStack.push_back(createDynTypedNode(Node)); - bool Result = BaseTraverse(); - ParentStack.pop_back(); - return Result; - } - - bool TraverseDecl(Decl *DeclNode) { - return TraverseNode( - DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); }, - &Map.PointerParents); - } - - bool TraverseStmt(Stmt *StmtNode) { - Stmt *FilteredNode = StmtNode; - if (auto *ExprNode = dyn_cast_or_null(FilteredNode)) - FilteredNode = Context.traverseIgnored(ExprNode); - return TraverseNode(FilteredNode, FilteredNode, - [&] { return VisitorBase::TraverseStmt(FilteredNode); }, - &Map.PointerParents); - } - - bool TraverseTypeLoc(TypeLoc TypeLocNode) { - return TraverseNode( - TypeLocNode, ast_type_traits::DynTypedNode::create(TypeLocNode), - [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); }, - &Map.OtherParents); - } - - bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { - return TraverseNode( - NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode), - [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }, - &Map.OtherParents); - } - - ParentMap ⤅ - ASTContext &Context; - llvm::SmallVector ParentStack; -}; - -ASTContext::ParentMap::ParentMap(ASTContext &Ctx) { - ASTVisitor(*this, Ctx).TraverseAST(Ctx); -} - -ASTContext::DynTypedNodeList -ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) { - std::unique_ptr &P = Parents[Traversal]; - if (!P) - // We build the parent map for the traversal scope (usually whole TU), as - // hasAncestor can escape any subtree. - P = std::make_unique(*this); - return P->getParents(Node); -} - bool ASTContext::ObjCMethodsAreEqual(const ObjCMethodDecl *MethodDecl, const ObjCMethodDecl *MethodImpl) { diff --git a/clang/lib/AST/CMakeLists.txt b/clang/lib/AST/CMakeLists.txt index e79c245d2f8..a741ca5a80e 100644 --- a/clang/lib/AST/CMakeLists.txt +++ b/clang/lib/AST/CMakeLists.txt @@ -44,6 +44,7 @@ add_clang_library(clangAST DeclOpenMP.cpp DeclPrinter.cpp DeclTemplate.cpp + ParentMapContext.cpp Expr.cpp ExprClassification.cpp ExprConcepts.cpp diff --git a/clang/lib/AST/Linkage.h b/clang/lib/AST/Linkage.h index 4e913540de8..5d8acf0016f 100644 --- a/clang/lib/AST/Linkage.h +++ b/clang/lib/AST/Linkage.h @@ -14,6 +14,7 @@ #ifndef LLVM_CLANG_LIB_AST_LINKAGE_H #define LLVM_CLANG_LIB_AST_LINKAGE_H +#include "clang/AST/ASTFwd.h" #include "clang/AST/Decl.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/Type.h" diff --git a/clang/lib/AST/ParentMapContext.cpp b/clang/lib/AST/ParentMapContext.cpp new file mode 100644 index 00000000000..6287bc8c1d7 --- /dev/null +++ b/clang/lib/AST/ParentMapContext.cpp @@ -0,0 +1,265 @@ +//===- ParentMapContext.cpp - Map of parents using DynTypedNode -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Similar to ParentMap.cpp, but generalizes to non-Stmt nodes, which can have +// multiple parents. +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/ParentMapContext.h" +#include "clang/AST/RecursiveASTVisitor.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" +#include "clang/AST/TemplateBase.h" + +using namespace clang; + +ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {} + +ParentMapContext::~ParentMapContext() = default; + +void ParentMapContext::clear() { Parents.clear(); } + +const Expr *ParentMapContext::traverseIgnored(const Expr *E) const { + return traverseIgnored(const_cast(E)); +} + +Expr *ParentMapContext::traverseIgnored(Expr *E) const { + if (!E) + return nullptr; + + switch (Traversal) { + case ast_type_traits::TK_AsIs: + return E; + case ast_type_traits::TK_IgnoreImplicitCastsAndParentheses: + return E->IgnoreParenImpCasts(); + case ast_type_traits::TK_IgnoreUnlessSpelledInSource: + return E->IgnoreUnlessSpelledInSource(); + } + llvm_unreachable("Invalid Traversal type!"); +} + +ast_type_traits::DynTypedNode +ParentMapContext::traverseIgnored(const ast_type_traits::DynTypedNode &N) const { + if (const auto *E = N.get()) { + return ast_type_traits::DynTypedNode::create(*traverseIgnored(E)); + } + return N; +} + +class ParentMapContext::ParentMap { + /// Contains parents of a node. + using ParentVector = llvm::SmallVector; + + /// Maps from a node to its parents. This is used for nodes that have + /// pointer identity only, which are more common and we can save space by + /// only storing a unique pointer to them. + using ParentMapPointers = llvm::DenseMap< + const void *, + llvm::PointerUnion>; + + /// Parent map for nodes without pointer identity. We store a full + /// DynTypedNode for all keys. + using ParentMapOtherNodes = llvm::DenseMap< + ast_type_traits::DynTypedNode, + llvm::PointerUnion>; + + ParentMapPointers PointerParents; + ParentMapOtherNodes OtherParents; + class ASTVisitor; + + static ast_type_traits::DynTypedNode + getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) { + if (const auto *D = U.dyn_cast()) + return ast_type_traits::DynTypedNode::create(*D); + if (const auto *S = U.dyn_cast()) + return ast_type_traits::DynTypedNode::create(*S); + return *U.get(); + } + + template + static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, + const MapTy &Map) { + auto I = Map.find(Node); + if (I == Map.end()) { + return llvm::ArrayRef(); + } + if (const auto *V = I->second.template dyn_cast()) { + return llvm::makeArrayRef(*V); + } + return getSingleDynTypedNodeFromParentMap(I->second); + } + +public: + ParentMap(ASTContext &Ctx); + ~ParentMap() { + for (const auto &Entry : PointerParents) { + if (Entry.second.is()) { + delete Entry.second.get(); + } else if (Entry.second.is()) { + delete Entry.second.get(); + } + } + for (const auto &Entry : OtherParents) { + if (Entry.second.is()) { + delete Entry.second.get(); + } else if (Entry.second.is()) { + delete Entry.second.get(); + } + } + } + + DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node) { + if (Node.getNodeKind().hasPointerIdentity()) + return getDynNodeFromMap(Node.getMemoizationData(), PointerParents); + return getDynNodeFromMap(Node, OtherParents); + } +}; + +/// Template specializations to abstract away from pointers and TypeLocs. +/// @{ +template +static ast_type_traits::DynTypedNode createDynTypedNode(const T &Node) { + return ast_type_traits::DynTypedNode::create(*Node); +} +template <> +ast_type_traits::DynTypedNode createDynTypedNode(const TypeLoc &Node) { + return ast_type_traits::DynTypedNode::create(Node); +} +template <> +ast_type_traits::DynTypedNode +createDynTypedNode(const NestedNameSpecifierLoc &Node) { + return ast_type_traits::DynTypedNode::create(Node); +} +/// @} + +/// 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 ParentMapContext::ParentMap::ASTVisitor + : public RecursiveASTVisitor { +public: + ASTVisitor(ParentMap &Map, ParentMapContext &MapCtx) + : Map(Map), MapCtx(MapCtx) {} + +private: + friend class RecursiveASTVisitor; + + using VisitorBase = RecursiveASTVisitor; + + bool shouldVisitTemplateInstantiations() const { return true; } + + bool shouldVisitImplicitCode() const { return true; } + + template + bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, + MapTy *Parents) { + if (!Node) + return true; + if (ParentStack.size() > 0) { + // FIXME: Currently we add the same parent multiple times, but only + // when no memoization data is available for the type. + // For example when we visit all subexpressions of template + // instantiations; this is suboptimal, but 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. + auto &NodeOrVector = (*Parents)[MapNode]; + if (NodeOrVector.isNull()) { + if (const auto *D = ParentStack.back().get()) + NodeOrVector = D; + else if (const auto *S = ParentStack.back().get()) + NodeOrVector = S; + else + NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back()); + } else { + if (!NodeOrVector.template is()) { + auto *Vector = new ParentVector( + 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); + delete NodeOrVector + .template dyn_cast(); + NodeOrVector = Vector; + } + + auto *Vector = NodeOrVector.template get(); + // Skip duplicates for types that have memoization data. + // We must check that the type has memoization data before calling + // std::find() because DynTypedNode::operator== can't compare all + // types. + bool Found = ParentStack.back().getMemoizationData() && + std::find(Vector->begin(), Vector->end(), + ParentStack.back()) != Vector->end(); + if (!Found) + Vector->push_back(ParentStack.back()); + } + } + ParentStack.push_back(createDynTypedNode(Node)); + bool Result = BaseTraverse(); + ParentStack.pop_back(); + return Result; + } + + bool TraverseDecl(Decl *DeclNode) { + return TraverseNode( + DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); }, + &Map.PointerParents); + } + + bool TraverseStmt(Stmt *StmtNode) { + Stmt *FilteredNode = StmtNode; + if (auto *ExprNode = dyn_cast_or_null(FilteredNode)) + FilteredNode = MapCtx.traverseIgnored(ExprNode); + return TraverseNode(FilteredNode, FilteredNode, + [&] { return VisitorBase::TraverseStmt(FilteredNode); }, + &Map.PointerParents); + } + + bool TraverseTypeLoc(TypeLoc TypeLocNode) { + return TraverseNode( + TypeLocNode, ast_type_traits::DynTypedNode::create(TypeLocNode), + [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); }, + &Map.OtherParents); + } + + bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { + return TraverseNode( + NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode), + [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }, + &Map.OtherParents); + } + + ParentMap ⤅ + ParentMapContext &MapCtx; + llvm::SmallVector ParentStack; +}; + +ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) { + ASTVisitor(*this, Ctx.getParentMapContext()).TraverseAST(Ctx); +} + +DynTypedNodeList +ParentMapContext::getParents(const ast_type_traits::DynTypedNode &Node) { + std::unique_ptr &P = Parents[Traversal]; + if (!P) + // We build the parent map for the traversal scope (usually whole TU), as + // hasAncestor can escape any subtree. + P = std::make_unique(ASTCtx); + return P->getParents(Node); +} + diff --git a/clang/lib/ASTMatchers/ASTMatchFinder.cpp b/clang/lib/ASTMatchers/ASTMatchFinder.cpp index f62c7ab5ed0..a7ff28b17f7 100644 --- a/clang/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/clang/lib/ASTMatchers/ASTMatchFinder.cpp @@ -143,11 +143,14 @@ public: Stmt *StmtToTraverse = StmtNode; if (auto *ExprNode = dyn_cast_or_null(StmtNode)) { auto *LambdaNode = dyn_cast_or_null(StmtNode); - if (LambdaNode && Finder->getASTContext().getTraversalKind() == - ast_type_traits::TK_IgnoreUnlessSpelledInSource) + if (LambdaNode && + Finder->getASTContext().getParentMapContext().getTraversalKind() == + ast_type_traits::TK_IgnoreUnlessSpelledInSource) StmtToTraverse = LambdaNode; else - StmtToTraverse = Finder->getASTContext().traverseIgnored(ExprNode); + StmtToTraverse = + Finder->getASTContext().getParentMapContext().traverseIgnored( + ExprNode); } if (Traversal == ast_type_traits::TraversalKind::TK_IgnoreImplicitCastsAndParentheses) { @@ -216,7 +219,7 @@ public: return traverse(*CtorInit); } bool TraverseLambdaExpr(LambdaExpr *Node) { - if (Finder->getASTContext().getTraversalKind() != + if (Finder->getASTContext().getParentMapContext().getTraversalKind() != ast_type_traits::TK_IgnoreUnlessSpelledInSource) return VisitorBase::TraverseLambdaExpr(Node); if (!Node) @@ -456,7 +459,7 @@ public: Key.Node = Node; // Note that we key on the bindings *before* the match. Key.BoundNodes = *Builder; - Key.Traversal = Ctx.getTraversalKind(); + Key.Traversal = Ctx.getParentMapContext().getTraversalKind(); MemoizationMap::iterator I = ResultCache.find(Key); if (I != ResultCache.end()) { @@ -705,7 +708,7 @@ private: Key.MatcherID = Matcher.getID(); Key.Node = Node; Key.BoundNodes = *Builder; - Key.Traversal = Ctx.getTraversalKind(); + Key.Traversal = Ctx.getParentMapContext().getTraversalKind(); // Note that we cannot use insert and reuse the iterator, as recursive // calls to match might invalidate the result cache iterators. diff --git a/clang/lib/ASTMatchers/ASTMatchersInternal.cpp b/clang/lib/ASTMatchers/ASTMatchersInternal.cpp index 199a6d839e2..e08765b7566 100644 --- a/clang/lib/ASTMatchers/ASTMatchersInternal.cpp +++ b/clang/lib/ASTMatchers/ASTMatchersInternal.cpp @@ -15,6 +15,7 @@ #include "clang/AST/ASTTypeTraits.h" #include "clang/AST/Decl.h" #include "clang/AST/DeclTemplate.h" +#include "clang/AST/ParentMapContext.h" #include "clang/AST/PrettyPrinter.h" #include "clang/ASTMatchers/ASTMatchers.h" #include "clang/Basic/LLVM.h" @@ -237,7 +238,8 @@ bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode, TraversalKindScope RAII(Finder->getASTContext(), Implementation->TraversalKind()); - auto N = Finder->getASTContext().traverseIgnored(DynNode); + auto N = + Finder->getASTContext().getParentMapContext().traverseIgnored(DynNode); if (RestrictKind.isBaseOf(N.getNodeKind()) && Implementation->dynMatches(N, Finder, Builder)) { @@ -256,7 +258,8 @@ bool DynTypedMatcher::matchesNoKindCheck( TraversalKindScope raii(Finder->getASTContext(), Implementation->TraversalKind()); - auto N = Finder->getASTContext().traverseIgnored(DynNode); + auto N = + Finder->getASTContext().getParentMapContext().traverseIgnored(DynNode); assert(RestrictKind.isBaseOf(N.getNodeKind())); if (Implementation->dynMatches(N, Finder, Builder)) { diff --git a/clang/lib/CodeGen/CGCall.h b/clang/lib/CodeGen/CGCall.h index 34558be5adb..28121af946f 100644 --- a/clang/lib/CodeGen/CGCall.h +++ b/clang/lib/CodeGen/CGCall.h @@ -16,6 +16,7 @@ #include "CGValue.h" #include "EHScopeStack.h" +#include "clang/AST/ASTFwd.h" #include "clang/AST/CanonicalType.h" #include "clang/AST/GlobalDecl.h" #include "clang/AST/Type.h" diff --git a/clang/lib/Tooling/ASTDiff/ASTDiff.cpp b/clang/lib/Tooling/ASTDiff/ASTDiff.cpp index 4d495228cb5..34e56f6e665 100644 --- a/clang/lib/Tooling/ASTDiff/ASTDiff.cpp +++ b/clang/lib/Tooling/ASTDiff/ASTDiff.cpp @@ -12,6 +12,7 @@ #include "clang/Tooling/ASTDiff/ASTDiff.h" +#include "clang/AST/ParentMapContext.h" #include "clang/AST/RecursiveASTVisitor.h" #include "clang/Lex/Lexer.h" #include "llvm/ADT/PriorityQueue.h" diff --git a/clang/lib/Tooling/Refactoring/Rename/USRLocFinder.cpp b/clang/lib/Tooling/Refactoring/Rename/USRLocFinder.cpp index 408e184f5bf..97b4d1077fe 100644 --- a/clang/lib/Tooling/Refactoring/Rename/USRLocFinder.cpp +++ b/clang/lib/Tooling/Refactoring/Rename/USRLocFinder.cpp @@ -15,6 +15,7 @@ #include "clang/Tooling/Refactoring/Rename/USRLocFinder.h" #include "clang/AST/ASTContext.h" +#include "clang/AST/ParentMapContext.h" #include "clang/AST/RecursiveASTVisitor.h" #include "clang/Basic/LLVM.h" #include "clang/Basic/SourceLocation.h" diff --git a/lldb/include/lldb/Symbol/TypeSystemClang.h b/lldb/include/lldb/Symbol/TypeSystemClang.h index acd78026161..bb47ca4af09 100644 --- a/lldb/include/lldb/Symbol/TypeSystemClang.h +++ b/lldb/include/lldb/Symbol/TypeSystemClang.h @@ -21,6 +21,7 @@ #include #include "clang/AST/ASTContext.h" +#include "clang/AST/ASTFwd.h" #include "clang/AST/TemplateBase.h" #include "llvm/ADT/APSInt.h" #include "llvm/ADT/SmallVector.h" -- 2.11.0