clang/include/clang/AST/ParentMapContext.h

   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 private:
  68   ASTContext &ASTCtx;
  69   class ParentMap;
  70   TraversalKind Traversal = TK_AsIs;
  71   std::unique_ptr<ParentMap> Parents;
  72 };
  73
  74 class TraversalKindScope {
  75   ParentMapContext &Ctx;
  76   TraversalKind TK = TK_AsIs;
  77
  78 public:
  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.
  91 class DynTypedNodeList {
  92   llvm::AlignedCharArrayUnion<DynTypedNode, ArrayRef<DynTypedNode>> Storage;
  93   bool IsSingleNode;
  94
  95 public:
  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
 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