clang/AST/ParentMapContext.h

0001 //===- ParentMapContext.h - Map of parents using DynTypedNode ---*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Similar to ParentMap.h, but generalizes to non-Stmt nodes, which can have
0010 // multiple parents.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CLANG_AST_PARENTMAPCONTEXT_H
0015 #define LLVM_CLANG_AST_PARENTMAPCONTEXT_H
0016
0017 #include "clang/AST/ASTContext.h"
0018 #include "clang/AST/ASTTypeTraits.h"
0019
0020 namespace clang {
0021 class DynTypedNodeList;
0022
0023 class ParentMapContext {
0024 public:
0025   ParentMapContext(ASTContext &Ctx);
0026
0027   ~ParentMapContext();
0028
0029   /// Returns the parents of the given node (within the traversal scope).
0030   ///
0031   /// Note that this will lazily compute the parents of all nodes
0032   /// and store them for later retrieval. Thus, the first call is O(n)
0033   /// in the number of AST nodes.
0034   ///
0035   /// Caveats and FIXMEs:
0036   /// Calculating the parent map over all AST nodes will need to load the
0037   /// full AST. This can be undesirable in the case where the full AST is
0038   /// expensive to create (for example, when using precompiled header
0039   /// preambles). Thus, there are good opportunities for optimization here.
0040   /// One idea is to walk the given node downwards, looking for references
0041   /// to declaration contexts - once a declaration context is found, compute
0042   /// the parent map for the declaration context; if that can satisfy the
0043   /// request, loading the whole AST can be avoided. Note that this is made
0044   /// more complex by statements in templates having multiple parents - those
0045   /// problems can be solved by building closure over the templated parts of
0046   /// the AST, which also avoids touching large parts of the AST.
0047   /// Additionally, we will want to add an interface to already give a hint
0048   /// where to search for the parents, for example when looking at a statement
0049   /// inside a certain function.
0050   ///
0051   /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
0052   /// NestedNameSpecifier or NestedNameSpecifierLoc.
0053   template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node);
0054
0055   DynTypedNodeList getParents(const DynTypedNode &Node);
0056
0057   /// Clear parent maps.
0058   void clear();
0059
0060   TraversalKind getTraversalKind() const { return Traversal; }
0061   void setTraversalKind(TraversalKind TK) { Traversal = TK; }
0062
0063   const Expr *traverseIgnored(const Expr *E) const;
0064   Expr *traverseIgnored(Expr *E) const;
0065   DynTypedNode traverseIgnored(const DynTypedNode &N) const;
0066
0067   class ParentMap;
0068
0069 private:
0070   ASTContext &ASTCtx;
0071   TraversalKind Traversal = TK_AsIs;
0072   std::unique_ptr<ParentMap> Parents;
0073 };
0074
0075 class TraversalKindScope {
0076   ParentMapContext &Ctx;
0077   TraversalKind TK = TK_AsIs;
0078
0079 public:
0080   TraversalKindScope(ASTContext &ASTCtx, std::optional<TraversalKind> ScopeTK)
0081       : Ctx(ASTCtx.getParentMapContext()) {
0082     TK = Ctx.getTraversalKind();
0083     if (ScopeTK)
0084       Ctx.setTraversalKind(*ScopeTK);
0085   }
0086
0087   ~TraversalKindScope() { Ctx.setTraversalKind(TK); }
0088 };
0089
0090 /// Container for either a single DynTypedNode or for an ArrayRef to
0091 /// DynTypedNode. For use with ParentMap.
0092 class DynTypedNodeList {
0093   union {
0094     DynTypedNode SingleNode;
0095     ArrayRef<DynTypedNode> Nodes;
0096   };
0097   bool IsSingleNode;
0098
0099 public:
0100   DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) {
0101     new (&SingleNode) DynTypedNode(N);
0102   }
0103
0104   DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) {
0105     new (&Nodes) ArrayRef<DynTypedNode>(A);
0106   }
0107
0108   const DynTypedNode *begin() const {
0109     return !IsSingleNode ? Nodes.begin() : &SingleNode;
0110   }
0111
0112   const DynTypedNode *end() const {
0113     return !IsSingleNode ? Nodes.end() : &SingleNode + 1;
0114   }
0115
0116   size_t size() const { return end() - begin(); }
0117   bool empty() const { return begin() == end(); }
0118
0119   const DynTypedNode &operator[](size_t N) const {
0120     assert(N < size() && "Out of bounds!");
0121     return *(begin() + N);
0122   }
0123 };
0124
0125 template <typename NodeT>
0126 inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) {
0127   return getParents(DynTypedNode::create(Node));
0128 }
0129
0130 template <typename NodeT>
0131 inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) {
0132   return getParentMapContext().getParents(Node);
0133 }
0134
0135 template <>
0136 inline DynTypedNodeList ASTContext::getParents(const DynTypedNode &Node) {
0137   return getParentMapContext().getParents(Node);
0138 }
0139
0140 } // namespace clang
0141
0142 #endif