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 20namespace clang { 21class DynTypedNodeList; 22 23class ParentMapContext { 24public: 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 67private: 68 ASTContext &ASTCtx; 69 class ParentMap; 70 TraversalKind Traversal = TK_AsIs; 71 std::unique_ptr<ParentMap> Parents; 72}; 73 74class TraversalKindScope { 75 ParentMapContext &Ctx; 76 TraversalKind TK = TK_AsIs; 77 78public: 79 TraversalKindScope(ASTContext &ASTCtx, llvm::Optional<TraversalKind> ScopeTK) 80 : Ctx(ASTCtx.getParentMapContext()) { 81 TK = Ctx.getTraversalKind(); 82 if (ScopeTK) 83 Ctx.setTraversalKind(*ScopeTK); 84 } 85 86 ~TraversalKindScope() { Ctx.setTraversalKind(TK); } 87}; 88 89/// Container for either a single DynTypedNode or for an ArrayRef to 90/// DynTypedNode. For use with ParentMap. 91class DynTypedNodeList { 92 llvm::AlignedCharArrayUnion<DynTypedNode, ArrayRef<DynTypedNode>> Storage; 93 bool IsSingleNode; 94 95public: 96 DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) { 97 new (Storage.buffer) DynTypedNode(N); 98 } 99 100 DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) { 101 new (Storage.buffer) ArrayRef<DynTypedNode>(A); 102 } 103 104 const DynTypedNode *begin() const { 105 if (!IsSingleNode) 106 return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer) 107 ->begin(); 108 return reinterpret_cast<const DynTypedNode *>(Storage.buffer); 109 } 110 111 const DynTypedNode *end() const { 112 if (!IsSingleNode) 113 return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer) 114 ->end(); 115 return reinterpret_cast<const DynTypedNode *>(Storage.buffer) + 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 127template <typename NodeT> 128inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) { 129 return getParents(DynTypedNode::create(Node)); 130} 131 132template <typename NodeT> 133inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) { 134 return getParentMapContext().getParents(Node); 135} 136 137template <> 138inline DynTypedNodeList ASTContext::getParents(const DynTypedNode &Node) { 139 return getParentMapContext().getParents(Node); 140} 141 142} // namespace clang 143 144#endif 145