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