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