Home | History | Annotate | Line # | Download | only in AST 
      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