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 union { 94 DynTypedNode SingleNode; 95 ArrayRef<DynTypedNode> Nodes; 96 }; 97 bool IsSingleNode; 98 99 public: 100 DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) { 101 new (&SingleNode) DynTypedNode(N); 102 } 103 104 DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) { 105 new (&Nodes) ArrayRef<DynTypedNode>(A); 106 } 107 108 const DynTypedNode *begin() const { 109 return !IsSingleNode ? Nodes.begin() : &SingleNode; 110 } 111 112 const DynTypedNode *end() const { 113 return !IsSingleNode ? Nodes.end() : &SingleNode + 1; 114 } 115 116 size_t size() const { return end() - begin(); } 117 bool empty() const { return begin() == end(); } 118 119 const DynTypedNode &operator[](size_t N) const { 120 assert(N < size() && "Out of bounds!"); 121 return *(begin() + N); 122 } 123 }; 124 125 template <typename NodeT> 126 inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) { 127 return getParents(DynTypedNode::create(Node)); 128 } 129 130 template <typename NodeT> 131 inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) { 132 return getParentMapContext().getParents(Node); 133 } 134 135 template <> 136 inline DynTypedNodeList ASTContext::getParents(const DynTypedNode &Node) { 137 return getParentMapContext().getParents(Node); 138 } 139 140 } // namespace clang 141 142 #endif 143