1 //===- ParentMapContext.h - Map of parents using DynTypedNode -------*- 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 // Similar to ParentMap.h, but generalizes to non-Stmt nodes, which can have 10 // multiple parents. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_AST_PARENTMAPCONTEXT_H 15 #define LLVM_CLANG_AST_PARENTMAPCONTEXT_H 16 17 #include "clang/AST/ASTContext.h" 18 #include "clang/AST/ASTTypeTraits.h" 19 20 namespace clang { 21 class DynTypedNodeList; 22 23 class ParentMapContext { 24 public: 25 ParentMapContext(ASTContext &Ctx); 26 27 ~ParentMapContext(); 28 29 /// Returns the parents of the given node (within the traversal scope). 30 /// 31 /// Note that this will lazily compute the parents of all nodes 32 /// and store them for later retrieval. Thus, the first call is O(n) 33 /// in the number of AST nodes. 34 /// 35 /// Caveats and FIXMEs: 36 /// Calculating the parent map over all AST nodes will need to load the 37 /// full AST. This can be undesirable in the case where the full AST is 38 /// expensive to create (for example, when using precompiled header 39 /// preambles). Thus, there are good opportunities for optimization here. 40 /// One idea is to walk the given node downwards, looking for references 41 /// to declaration contexts - once a declaration context is found, compute 42 /// the parent map for the declaration context; if that can satisfy the 43 /// request, loading the whole AST can be avoided. Note that this is made 44 /// more complex by statements in templates having multiple parents - those 45 /// problems can be solved by building closure over the templated parts of 46 /// the AST, which also avoids touching large parts of the AST. 47 /// Additionally, we will want to add an interface to already give a hint 48 /// where to search for the parents, for example when looking at a statement 49 /// inside a certain function. 50 /// 51 /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc, 52 /// NestedNameSpecifier or NestedNameSpecifierLoc. 53 template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node); 54 55 DynTypedNodeList getParents(const DynTypedNode &Node); 56 57 /// Clear parent maps. 58 void clear(); 59 60 TraversalKind getTraversalKind() const { return Traversal; } 61 void setTraversalKind(TraversalKind TK) { Traversal = TK; } 62 63 const Expr *traverseIgnored(const Expr *E) const; 64 Expr *traverseIgnored(Expr *E) const; 65 DynTypedNode traverseIgnored(const DynTypedNode &N) const; 66 67 class ParentMap; 68 69 private: 70 ASTContext &ASTCtx; 71 TraversalKind Traversal = TK_AsIs; 72 std::unique_ptr<ParentMap> Parents; 73 }; 74 75 class TraversalKindScope { 76 ParentMapContext &Ctx; 77 TraversalKind TK = TK_AsIs; 78 79 public: 80 TraversalKindScope(ASTContext &ASTCtx, llvm::Optional<TraversalKind> ScopeTK) 81 : Ctx(ASTCtx.getParentMapContext()) { 82 TK = Ctx.getTraversalKind(); 83 if (ScopeTK) 84 Ctx.setTraversalKind(*ScopeTK); 85 } 86 87 ~TraversalKindScope() { Ctx.setTraversalKind(TK); } 88 }; 89 90 /// Container for either a single DynTypedNode or for an ArrayRef to 91 /// DynTypedNode. For use with ParentMap. 92 class DynTypedNodeList { 93 llvm::AlignedCharArrayUnion<DynTypedNode, ArrayRef<DynTypedNode>> Storage; 94 bool IsSingleNode; 95 96 public: 97 DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) { 98 new (&Storage) DynTypedNode(N); 99 } 100 101 DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) { 102 new (&Storage) ArrayRef<DynTypedNode>(A); 103 } 104 105 const DynTypedNode *begin() const { 106 if (!IsSingleNode) 107 return reinterpret_cast<const ArrayRef<DynTypedNode> *>(&Storage) 108 ->begin(); 109 return reinterpret_cast<const DynTypedNode *>(&Storage); 110 } 111 112 const DynTypedNode *end() const { 113 if (!IsSingleNode) 114 return reinterpret_cast<const ArrayRef<DynTypedNode> *>(&Storage)->end(); 115 return reinterpret_cast<const DynTypedNode *>(&Storage) + 1; 116 } 117 118 size_t size() const { return end() - begin(); } 119 bool empty() const { return begin() == end(); } 120 121 const DynTypedNode &operator[](size_t N) const { 122 assert(N < size() && "Out of bounds!"); 123 return *(begin() + N); 124 } 125 }; 126 127 template <typename NodeT> 128 inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) { 129 return getParents(DynTypedNode::create(Node)); 130 } 131 132 template <typename NodeT> 133 inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) { 134 return getParentMapContext().getParents(Node); 135 } 136 137 template <> 138 inline DynTypedNodeList ASTContext::getParents(const DynTypedNode &Node) { 139 return getParentMapContext().getParents(Node); 140 } 141 142 } // namespace clang 143 144 #endif 145