clang 19.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/BitVector.h"
12#include "llvm/Support/raw_ostream.h"
13#include "llvm/Support/Casting.h"
14#include <cassert>
15
16using namespace clang;
17
18namespace {
19static 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 (const syntax::Node &C : T->getChildren())
23 traverse(&C, Visit);
24 }
25 Visit(N);
26}
27static 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
36
38 : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
39 Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),
40 CanModify(false) {
41 this->setRole(NodeRole::Detached);
42}
43
45 return getRole() == NodeRole::Detached;
46}
47
48void syntax::Node::setRole(NodeRole NR) {
49 this->Role = static_cast<unsigned>(NR);
50}
51
52void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) {
53 assert(Child->getRole() == NodeRole::Detached);
54 assert(Role != NodeRole::Detached);
55
56 Child->setRole(Role);
57 appendChildLowLevel(Child);
59
60void syntax::Tree::appendChildLowLevel(Node *Child) {
61 assert(Child->Parent == nullptr);
62 assert(Child->NextSibling == nullptr);
63 assert(Child->PreviousSibling == nullptr);
64 assert(Child->getRole() != NodeRole::Detached);
65
66 Child->Parent = this;
67 if (this->LastChild) {
68 Child->PreviousSibling = this->LastChild;
69 this->LastChild->NextSibling = Child;
70 } else
71 this->FirstChild = Child;
72
73 this->LastChild = Child;
74}
75
76void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
77 assert(Child->getRole() == NodeRole::Detached);
78 assert(Role != NodeRole::Detached);
79
80 Child->setRole(Role);
81 prependChildLowLevel(Child);
82}
83
84void syntax::Tree::prependChildLowLevel(Node *Child) {
85 assert(Child->Parent == nullptr);
86 assert(Child->NextSibling == nullptr);
87 assert(Child->PreviousSibling == nullptr);
88 assert(Child->getRole() != NodeRole::Detached);
89
90 Child->Parent = this;
91 if (this->FirstChild) {
92 Child->NextSibling = this->FirstChild;
93 this->FirstChild->PreviousSibling = Child;
94 } else
95 this->LastChild = Child;
96
97 this->FirstChild = Child;
98}
99
100void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End,
101 Node *New) {
102 assert((!Begin || Begin->Parent == this) &&
103 "`Begin` is not a child of `this`.");
104 assert((!End || End->Parent == this) && "`End` is not a child of `this`.");
105 assert(canModify() && "Cannot modify `this`.");
106
107#ifndef NDEBUG
108 for (auto *N = New; N; N = N->NextSibling) {
109 assert(N->Parent == nullptr);
110 assert(N->getRole() != NodeRole::Detached && "Roles must be set");
111 // FIXME: validate the role.
112 }
113
114 auto Reachable = [](Node *From, Node *N) {
115 if (!N)
116 return true;
117 for (auto *It = From; It; It = It->NextSibling)
118 if (It == N)
119 return true;
120 return false;
121 };
122 assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable.");
123 assert(Reachable(Begin, End) && "`End` is not after `Begin`.");
124#endif
125
126 if (!New && Begin == End)
127 return;
128
129 // Mark modification.
130 for (auto *T = this; T && T->Original; T = T->Parent)
131 T->Original = false;
132
133 // Save the node before the range to be removed. Later we insert the `New`
134 // range after this node.
135 auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;
136
137 // Detach old nodes.
138 for (auto *N = Begin; N != End;) {
139 auto *Next = N->NextSibling;
140
141 N->setRole(NodeRole::Detached);
142 N->Parent = nullptr;
143 N->NextSibling = nullptr;
144 N->PreviousSibling = nullptr;
145 if (N->Original)
146 traverse(N, [](Node *C) { C->Original = false; });
147
148 N = Next;
149 }
150
151 // Attach new range.
152 auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
153 auto *&NewLast = End ? End->PreviousSibling : LastChild;
154
155 if (!New) {
156 NewFirst = End;
157 NewLast = BeforeBegin;
158 return;
159 }
160
161 New->PreviousSibling = BeforeBegin;
162 NewFirst = New;
163
164 Node *LastInNew;
165 for (auto *N = New; N != nullptr; N = N->NextSibling) {
166 LastInNew = N;
167 N->Parent = this;
168 }
169 LastInNew->NextSibling = End;
170 NewLast = LastInNew;
171}
172
173namespace {
174static void dumpNode(raw_ostream &OS, const syntax::Node *N,
175 const syntax::TokenManager &TM, llvm::BitVector IndentMask) {
176 auto DumpExtraInfo = [&OS](const syntax::Node *N) {
178 OS << " " << N->getRole();
179 if (!N->isOriginal())
180 OS << " synthesized";
181 if (!N->canModify())
182 OS << " unmodifiable";
183 };
184
185 assert(N);
186 if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
187 OS << "'";
188 OS << TM.getText(L->getTokenKey());
189 OS << "'";
190 DumpExtraInfo(N);
191 OS << "\n";
192 return;
193 }
194
195 const auto *T = cast<syntax::Tree>(N);
196 OS << T->getKind();
197 DumpExtraInfo(N);
198 OS << "\n";
199
200 for (const syntax::Node &It : T->getChildren()) {
201 for (unsigned Idx = 0; Idx < IndentMask.size(); ++Idx) {
202 if (IndentMask[Idx])
203 OS << "| ";
204 else
205 OS << " ";
206 }
207 if (!It.getNextSibling()) {
208 OS << "`-";
209 IndentMask.push_back(false);
210 } else {
211 OS << "|-";
212 IndentMask.push_back(true);
213 }
214 dumpNode(OS, &It, TM, IndentMask);
215 IndentMask.pop_back();
216 }
217}
218} // namespace
219
220std::string syntax::Node::dump(const TokenManager &TM) const {
221 std::string Str;
222 llvm::raw_string_ostream OS(Str);
223 dumpNode(OS, this, TM, /*IndentMask=*/{});
224 return std::move(OS.str());
225}
226
227std::string syntax::Node::dumpTokens(const TokenManager &TM) const {
228 std::string Storage;
229 llvm::raw_string_ostream OS(Storage);
230 traverse(this, [&](const syntax::Node *N) {
231 if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
232 OS << TM.getText(L->getTokenKey());
233 OS << " ";
234 }
235 });
236 return Storage;
237}
238
240#ifndef NDEBUG
241 if (isDetached())
242 assert(getParent() == nullptr);
243 else
244 assert(getParent() != nullptr);
245
246 const auto *T = dyn_cast<Tree>(this);
247 if (!T)
248 return;
249 for (const Node &C : T->getChildren()) {
250 if (T->isOriginal())
251 assert(C.isOriginal());
252 assert(!C.isDetached());
253 assert(C.getParent() == T);
254 const auto *Next = C.getNextSibling();
255 assert(!Next || &C == Next->getPreviousSibling());
256 if (!C.getNextSibling())
257 assert(&C == T->getLastChild() &&
258 "Last child is reachable by advancing from the first child.");
259 }
260
261 const auto *L = dyn_cast<List>(T);
262 if (!L)
263 return;
264 for (const Node &C : T->getChildren()) {
265 assert(C.getRole() == NodeRole::ListElement ||
266 C.getRole() == NodeRole::ListDelimiter);
267 if (C.getRole() == NodeRole::ListDelimiter) {
268 assert(isa<Leaf>(C));
269 // FIXME: re-enable it when there is way to retrieve token kind in Leaf.
270 // assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind());
271 }
272 }
273
274#endif
275}
276
278#ifndef NDEBUG
279 traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
280#endif
281}
282
284 for (const Node &C : getChildren()) {
285 if (const auto *L = dyn_cast<syntax::Leaf>(&C))
286 return L;
287 if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf())
288 return L;
289 }
290 return nullptr;
291}
292
294 for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
295 if (const auto *L = dyn_cast<syntax::Leaf>(C))
296 return L;
297 if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf())
298 return L;
299 }
300 return nullptr;
301}
302
304 for (const Node &C : getChildren()) {
305 if (C.getRole() == R)
306 return &C;
307 }
308 return nullptr;
309}
310
311std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
313 if (!getFirstChild())
314 return {};
315
316 std::vector<syntax::List::ElementAndDelimiter<Node>> Children;
317 syntax::Node *ElementWithoutDelimiter = nullptr;
318 for (Node &C : getChildren()) {
319 switch (C.getRole()) {
321 if (ElementWithoutDelimiter) {
322 Children.push_back({ElementWithoutDelimiter, nullptr});
323 }
324 ElementWithoutDelimiter = &C;
325 break;
326 }
328 Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)});
329 ElementWithoutDelimiter = nullptr;
330 break;
331 }
332 default:
333 llvm_unreachable(
334 "A list can have only elements and delimiters as children.");
335 }
336 }
337
338 switch (getTerminationKind()) {
340 Children.push_back({ElementWithoutDelimiter, nullptr});
341 break;
342 }
345 if (ElementWithoutDelimiter) {
346 Children.push_back({ElementWithoutDelimiter, nullptr});
347 }
348 break;
349 }
350 }
351
352 return Children;
353}
354
355// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
356// ignoring delimiters
357std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
358 if (!getFirstChild())
359 return {};
360
361 std::vector<syntax::Node *> Children;
362 syntax::Node *ElementWithoutDelimiter = nullptr;
363 for (Node &C : getChildren()) {
364 switch (C.getRole()) {
366 if (ElementWithoutDelimiter) {
367 Children.push_back(ElementWithoutDelimiter);
368 }
369 ElementWithoutDelimiter = &C;
370 break;
371 }
373 Children.push_back(ElementWithoutDelimiter);
374 ElementWithoutDelimiter = nullptr;
375 break;
376 }
377 default:
378 llvm_unreachable("A list has only elements or delimiters.");
379 }
380 }
381
382 switch (getTerminationKind()) {
384 Children.push_back(ElementWithoutDelimiter);
385 break;
386 }
389 if (ElementWithoutDelimiter) {
390 Children.push_back(ElementWithoutDelimiter);
391 }
392 break;
393 }
394 }
395
396 return Children;
397}
398
400 switch (this->getKind()) {
401 case NodeKind::NestedNameSpecifier:
402 return clang::tok::coloncolon;
403 case NodeKind::CallArguments:
404 case NodeKind::ParameterDeclarationList:
405 case NodeKind::DeclaratorList:
406 return clang::tok::comma;
407 default:
408 llvm_unreachable("This is not a subclass of List, thus "
409 "getDelimiterTokenKind() cannot be called");
410 }
411}
412
414 switch (this->getKind()) {
415 case NodeKind::NestedNameSpecifier:
416 return TerminationKind::Terminated;
417 case NodeKind::CallArguments:
418 case NodeKind::ParameterDeclarationList:
419 case NodeKind::DeclaratorList:
420 return TerminationKind::Separated;
421 default:
422 llvm_unreachable("This is not a subclass of List, thus "
423 "getTerminationKind() cannot be called");
424 }
425}
426
428 switch (this->getKind()) {
429 case NodeKind::NestedNameSpecifier:
430 return false;
431 case NodeKind::CallArguments:
432 return true;
433 case NodeKind::ParameterDeclarationList:
434 return true;
435 case NodeKind::DeclaratorList:
436 return true;
437 default:
438 llvm_unreachable("This is not a subclass of List, thus canBeEmpty() "
439 "cannot be called");
440 }
441}
NodeId Parent
Definition: ASTDiff.cpp:191
DynTypedNode Node
static Decl::Kind getKind(const Decl *D)
Definition: DeclBase.cpp:1110
Defines the clang::TokenKind enum and support functions.
SourceLocation Begin
A leaf node points to a single token.
Definition: Tree.h:132
Leaf(TokenManager::Key K)
Definition: Tree.cpp:35
bool canBeEmpty() const
Whether this list can be empty in syntactically and semantically correct code.
Definition: Tree.cpp:427
std::vector< Node * > getElementsAsNodes()
Returns the elements of the list.
Definition: Tree.cpp:357
std::vector< ElementAndDelimiter< Node > > getElementsAsNodesAndDelimiters()
Returns the elements and corresponding delimiters.
Definition: Tree.cpp:312
TerminationKind getTerminationKind() const
Definition: Tree.cpp:413
clang::tok::TokenKind getDelimiterTokenKind() const
Returns the appropriate delimiter for this list.
Definition: Tree.cpp:399
A node in a syntax tree.
Definition: Tree.h:54
void assertInvariants() const
Asserts invariants on this node of the tree and its immediate children.
Definition: Tree.cpp:239
bool canModify() const
If this function return false, the tree cannot be modified because there is no reasonable way to prod...
Definition: Tree.h:88
void assertInvariantsRecursive() const
Runs checkInvariants on all nodes in the subtree. No-op if NDEBUG is set.
Definition: Tree.cpp:277
NodeRole getRole() const
Definition: Tree.h:71
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:37
std::string dump(const TokenManager &SM) const
Dumps the structure of a subtree. For debugging and testing purposes.
Definition: Tree.cpp:220
std::string dumpTokens(const TokenManager &SM) const
Dumps the tokens forming this subtree.
Definition: Tree.cpp:227
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:81
bool isDetached() const
Whether the node is detached from a tree, i.e. does not have a parent.
Definition: Tree.cpp:44
Defines interfaces for operating "Token" in the clang syntax-tree.
Definition: TokenManager.h:29
uintptr_t Key
A key to identify a specific token.
Definition: TokenManager.h:40
virtual llvm::StringRef getText(Key K) const =0
const Leaf * findLastLeaf() const
Definition: Tree.cpp:293
const Leaf * findFirstLeaf() const
Definition: Tree.cpp:283
const Node * findChild(NodeRole R) const
Find the first node with a corresponding role.
Definition: Tree.cpp:303
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:817
NodeRole
A relation between a parent and child node, e.g.
Definition: Nodes.h:54
@ ListElement
List API roles.
@ Detached
A node without a parent.
@ Unknown
Children of an unknown semantic nature, e.g. skipped tokens, comments.
NodeKind
A kind of a syntax node, used for implementing casts.
Definition: Nodes.h:32
TokenKind
Provides a simple uniform namespace for tokens from all C languages.
Definition: TokenKinds.h:25
The JSON file list parser is used to communicate input to InstallAPI.
for(unsigned i=0, n=TL.getNumTypeArgs();i !=n;++i) TRY_TO(TraverseTypeLoc(TL.getTypeArgTInfo(i) -> getTypeLoc()))
#define false
Definition: stdbool.h:22