clang  12.0.0git
Tree.cpp
Go to the documentation of this file.
1 //===- Tree.cpp -----------------------------------------------*- 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 //===----------------------------------------------------------------------===//
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/Support/Casting.h"
14 #include <cassert>
15 
16 using namespace clang;
17 
18 namespace {
19 static void traverse(const syntax::Node *N,
20  llvm::function_ref<void(const syntax::Node *)> Visit) {
21  if (auto *T = dyn_cast<syntax::Tree>(N)) {
22  for (auto *C = T->firstChild(); C; C = C->nextSibling())
23  traverse(C, Visit);
24  }
25  Visit(N);
26 }
27 static void traverse(syntax::Node *N,
28  llvm::function_ref<void(syntax::Node *)> Visit) {
29  traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) {
30  Visit(const_cast<syntax::Node *>(N));
31  });
32 }
33 } // namespace
34 
35 syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
36  TokenBuffer Tokens)
37  : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {}
38 
40  return Tokens;
41 }
42 
43 std::pair<FileID, llvm::ArrayRef<syntax::Token>>
44 syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
45  auto FID = SourceMgr.createFileID(std::move(Input));
46  auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
47  assert(It.second && "duplicate FileID");
48  return {FID, It.first->second};
49 }
50 
52  assert(Tok != nullptr);
53 }
54 
55 bool syntax::Leaf::classof(const Node *N) {
56  return N->kind() == NodeKind::Leaf;
57 }
58 
60  : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
61  Role(0), Original(false), CanModify(false) {
62  this->setRole(NodeRole::Detached);
63 }
64 
65 bool syntax::Node::isDetached() const { return role() == NodeRole::Detached; }
66 
67 void syntax::Node::setRole(NodeRole NR) {
68  this->Role = static_cast<unsigned>(NR);
69 }
70 
71 bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
72 
73 void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
74  assert(Child->role() == NodeRole::Detached);
75  assert(Role != NodeRole::Detached);
76 
77  Child->setRole(Role);
78  prependChildLowLevel(Child);
79 }
80 
81 void syntax::Tree::prependChildLowLevel(Node *Child) {
82  assert(Child->Parent == nullptr);
83  assert(Child->NextSibling == nullptr);
84  assert(Child->role() != NodeRole::Detached);
85 
86  Child->Parent = this;
87  Child->NextSibling = this->FirstChild;
88  this->FirstChild = Child;
89 }
90 
91 void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
92  Node *New) {
93  assert(!BeforeBegin || BeforeBegin->Parent == this);
94 
95 #ifndef NDEBUG
96  for (auto *N = New; N; N = N->nextSibling()) {
97  assert(N->Parent == nullptr);
98  assert(N->role() != NodeRole::Detached && "Roles must be set");
99  // FIXME: sanity-check the role.
100  }
101 #endif
102 
103  // Detach old nodes.
104  for (auto *N = !BeforeBegin ? FirstChild : BeforeBegin->nextSibling();
105  N != End;) {
106  auto *Next = N->NextSibling;
107 
108  N->setRole(NodeRole::Detached);
109  N->Parent = nullptr;
110  N->NextSibling = nullptr;
111  if (N->Original)
112  traverse(N, [&](Node *C) { C->Original = false; });
113 
114  N = Next;
115  }
116 
117  // Attach new nodes.
118  if (BeforeBegin)
119  BeforeBegin->NextSibling = New ? New : End;
120  else
121  FirstChild = New ? New : End;
122 
123  if (New) {
124  auto *Last = New;
125  for (auto *N = New; N != nullptr; N = N->nextSibling()) {
126  Last = N;
127  N->Parent = this;
128  }
129  Last->NextSibling = End;
130  }
131 
132  // Mark the node as modified.
133  for (auto *T = this; T && T->Original; T = T->Parent)
134  T->Original = false;
135 }
136 
137 namespace {
138 static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens,
139  const SourceManager &SM) {
140  assert(!Tokens.empty());
141  bool First = true;
142  for (const auto &T : Tokens) {
143  if (!First)
144  OS << " ";
145  else
146  First = false;
147  // Handle 'eof' separately, calling text() on it produces an empty string.
148  if (T.kind() == tok::eof) {
149  OS << "<eof>";
150  continue;
151  }
152  OS << T.text(SM);
153  }
154 }
155 
156 static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
157  const syntax::Arena &A, std::vector<bool> IndentMask) {
158  std::string Marks;
159  if (!N->isOriginal())
160  Marks += "M";
161  if (N->role() == syntax::NodeRole::Detached)
162  Marks += "*"; // FIXME: find a nice way to print other roles.
163  if (!N->canModify())
164  Marks += "I";
165  if (!Marks.empty())
166  OS << Marks << ": ";
167 
168  if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
169  dumpTokens(OS, *L->token(), A.sourceManager());
170  OS << "\n";
171  return;
172  }
173 
174  auto *T = llvm::cast<syntax::Tree>(N);
175  OS << T->kind() << "\n";
176 
177  for (auto It = T->firstChild(); It != nullptr; It = It->nextSibling()) {
178  for (bool Filled : IndentMask) {
179  if (Filled)
180  OS << "| ";
181  else
182  OS << " ";
183  }
184  if (!It->nextSibling()) {
185  OS << "`-";
186  IndentMask.push_back(false);
187  } else {
188  OS << "|-";
189  IndentMask.push_back(true);
190  }
191  dumpTree(OS, It, A, IndentMask);
192  IndentMask.pop_back();
193  }
194 }
195 } // namespace
196 
197 std::string syntax::Node::dump(const Arena &A) const {
198  std::string Str;
199  llvm::raw_string_ostream OS(Str);
200  dumpTree(OS, this, A, /*IndentMask=*/{});
201  return std::move(OS.str());
202 }
203 
204 std::string syntax::Node::dumpTokens(const Arena &A) const {
205  std::string Storage;
206  llvm::raw_string_ostream OS(Storage);
207  traverse(this, [&](const syntax::Node *N) {
208  auto *L = llvm::dyn_cast<syntax::Leaf>(N);
209  if (!L)
210  return;
211  ::dumpTokens(OS, *L->token(), A.sourceManager());
212  OS << " ";
213  });
214  return OS.str();
215 }
216 
218 #ifndef NDEBUG
219  if (isDetached())
220  assert(parent() == nullptr);
221  else
222  assert(parent() != nullptr);
223 
224  auto *T = dyn_cast<Tree>(this);
225  if (!T)
226  return;
227  for (auto *C = T->firstChild(); C; C = C->nextSibling()) {
228  if (T->isOriginal())
229  assert(C->isOriginal());
230  assert(!C->isDetached());
231  assert(C->parent() == T);
232  }
233 #endif
234 }
235 
237 #ifndef NDEBUG
238  traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
239 #endif
240 }
241 
243  auto *T = this;
244  while (auto *C = T->firstChild()) {
245  if (auto *L = dyn_cast<syntax::Leaf>(C))
246  return L;
247  T = cast<syntax::Tree>(C);
248  }
249  return nullptr;
250 }
251 
253  auto *T = this;
254  while (auto *C = T->firstChild()) {
255  // Find the last child.
256  while (auto *Next = C->nextSibling())
257  C = Next;
258 
259  if (auto *L = dyn_cast<syntax::Leaf>(C))
260  return L;
261  T = cast<syntax::Tree>(C);
262  }
263  return nullptr;
264 }
265 
267  for (auto *C = FirstChild; C; C = C->nextSibling()) {
268  if (C->role() == R)
269  return C;
270  }
271  return nullptr;
272 }
FileID createFileID(const FileEntry *SourceFile, SourceLocation IncludePos, SrcMgr::CharacteristicKind FileCharacter, int LoadedID=0, unsigned LoadedOffset=0)
Create a new FileID that represents the specified file being #included from the specified IncludePosi...
std::pair< FileID, llvm::ArrayRef< syntax::Token > > lexBuffer(std::unique_ptr< llvm::MemoryBuffer > Buffer)
Add Buffer to the underlying source manager, tokenize it and store the resulting tokens.
Definition: Tree.cpp:44
Leaf * lastLeaf()
Definition: Tree.cpp:252
std::string dump(const Arena &A) const
Dumps the structure of a subtree. For debugging and testing purposes.
Definition: Tree.cpp:197
NodeRole role() const
Definition: Tree.h:83
A node in a syntax tree.
Definition: Tree.h:76
A token coming directly from a file or from a macro invocation.
Definition: Tokens.h:104
static bool classof(const Node *N)
Definition: Tree.cpp:71
static bool classof(const Node *N)
Definition: Tree.cpp:55
Definition: Format.h:2679
Node(NodeKind Kind)
Newly created nodes are detached from a tree, parent and sibling links are set when the node is added...
Definition: Tree.cpp:59
Leaf * firstLeaf()
Definition: Tree.cpp:242
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:54
const FormatToken & Tok
const SourceManager & sourceManager() const
Definition: Tree.h:44
bool isDetached() const
Whether the node is detached from a tree, i.e. does not have a parent.
Definition: Tree.cpp:65
NodeId Parent
Definition: ASTDiff.cpp:192
const TokenBuffer & tokenBuffer() const
Definition: Tree.cpp:39
A memory arena for syntax trees.
Definition: Tree.h:39
bool canModify() const
If this function return false, the tree cannot be modified because there is no reasonable way to prod...
Definition: Tree.h:100
SourceLocation End
const Node * nextSibling() const
Definition: Tree.h:105
#define SM(sm)
Definition: Cuda.cpp:62
A node that has children and represents a syntactic language construct.
Definition: Tree.h:152
NodeKind
A kind of a syntax node, used for implementing casts.
Definition: Nodes.h:37
const Tree * parent() const
Definition: Tree.h:102
#define false
Definition: stdbool.h:17
Kind
A node without a parent.
internal::Matcher< T > traverse(TraversalKind TK, const internal::Matcher< T > &InnerMatcher)
Causes all nested matchers to be matched with the specified traversal kind.
Definition: ASTMatchers.h:753
NodeRole
A relation between a parent and child node, e.g.
Definition: Nodes.h:124
Dataflow Directional Tag Classes.
Arena(SourceManager &SourceMgr, const LangOptions &LangOpts, TokenBuffer Tokens)
Definition: Tree.cpp:35
A leaf node points to a single token inside the expanded token stream.
Definition: Tree.h:140
bool isOriginal() const
Whether the node was created from the AST backed by the source code rather than added later through m...
Definition: Tree.h:93
std::vector< syntax::Token > tokenize(FileID FID, const SourceManager &SM, const LangOptions &LO)
Lex the text buffer, corresponding to FID, in raw mode and record the resulting spelled tokens...
Definition: Tokens.cpp:509
Defines the clang::TokenKind enum and support functions.
void assertInvariants() const
Asserts invariants on this node of the tree and its immediate children.
Definition: Tree.cpp:217
Leaf(const syntax::Token *T)
Definition: Tree.cpp:51
void assertInvariantsRecursive() const
Runs checkInvariants on all nodes in the subtree. No-op if NDEBUG is set.
Definition: Tree.cpp:236
NodeKind kind() const
Definition: Tree.h:82
std::string dumpTokens(const Arena &A) const
Dumps the tokens forming this subtree.
Definition: Tree.cpp:204
A list of tokens obtained by preprocessing a text buffer and operations to map between the expanded a...
Definition: Tokens.h:175
This class handles loading and caching of source files into memory.
syntax::Node * findChild(NodeRole R)
Find the first node with a corresponding role.
Definition: Tree.cpp:266