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
15 using namespace clang;
16
17 namespace {
traverse(const syntax::Node * N,llvm::function_ref<void (const syntax::Node *)> Visit)18 static void traverse(const syntax::Node *N,
19 llvm::function_ref<void(const syntax::Node *)> Visit) {
20 if (auto *T = dyn_cast<syntax::Tree>(N)) {
21 for (const syntax::Node &C : T->getChildren())
22 traverse(&C, Visit);
23 }
24 Visit(N);
25 }
traverse(syntax::Node * N,llvm::function_ref<void (syntax::Node *)> Visit)26 static void traverse(syntax::Node *N,
27 llvm::function_ref<void(syntax::Node *)> Visit) {
28 traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) {
29 Visit(const_cast<syntax::Node *>(N));
30 });
31 }
32 } // namespace
33
Leaf(syntax::TokenManager::Key K)34 syntax::Leaf::Leaf(syntax::TokenManager::Key K) : Node(NodeKind::Leaf), K(K) {}
35
Node(NodeKind Kind)36 syntax::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
isDetached() const43 bool syntax::Node::isDetached() const {
44 return getRole() == NodeRole::Detached;
45 }
46
setRole(NodeRole NR)47 void syntax::Node::setRole(NodeRole NR) {
48 this->Role = static_cast<unsigned>(NR);
49 }
50
appendChildLowLevel(Node * Child,NodeRole Role)51 void 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
appendChildLowLevel(Node * Child)59 void 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
prependChildLowLevel(Node * Child,NodeRole Role)75 void 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
prependChildLowLevel(Node * Child)83 void 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
replaceChildRangeLowLevel(Node * Begin,Node * End,Node * New)99 void 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, [](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
172 namespace {
dumpNode(raw_ostream & OS,const syntax::Node * N,const syntax::TokenManager & TM,llvm::BitVector IndentMask)173 static 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>(N)) {
186 OS << "'";
187 OS << TM.getText(L->getTokenKey());
188 OS << "'";
189 DumpExtraInfo(N);
190 OS << "\n";
191 return;
192 }
193
194 const auto *T = cast<syntax::Tree>(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(false);
209 } else {
210 OS << "|-";
211 IndentMask.push_back(true);
212 }
213 dumpNode(OS, &It, TM, IndentMask);
214 IndentMask.pop_back();
215 }
216 }
217 } // namespace
218
dump(const TokenManager & TM) const219 std::string syntax::Node::dump(const TokenManager &TM) const {
220 std::string Str;
221 llvm::raw_string_ostream OS(Str);
222 dumpNode(OS, this, TM, /*IndentMask=*/{});
223 return std::move(OS.str());
224 }
225
dumpTokens(const TokenManager & TM) const226 std::string syntax::Node::dumpTokens(const TokenManager &TM) const {
227 std::string Storage;
228 llvm::raw_string_ostream OS(Storage);
229 traverse(this, [&](const syntax::Node *N) {
230 if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
231 OS << TM.getText(L->getTokenKey());
232 OS << " ";
233 }
234 });
235 return Storage;
236 }
237
assertInvariants() const238 void 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
assertInvariantsRecursive() const276 void syntax::Node::assertInvariantsRecursive() const {
277 #ifndef NDEBUG
278 traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
279 #endif
280 }
281
findFirstLeaf() const282 const syntax::Leaf *syntax::Tree::findFirstLeaf() const {
283 for (const Node &C : getChildren()) {
284 if (const auto *L = dyn_cast<syntax::Leaf>(&C))
285 return L;
286 if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf())
287 return L;
288 }
289 return nullptr;
290 }
291
findLastLeaf() const292 const 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>(C))
295 return L;
296 if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf())
297 return L;
298 }
299 return nullptr;
300 }
301
findChild(NodeRole R) const302 const 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
310 std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
getElementsAsNodesAndDelimiters()311 syntax::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({ElementWithoutDelimiter, nullptr});
322 }
323 ElementWithoutDelimiter = &C;
324 break;
325 }
326 case syntax::NodeRole::ListDelimiter: {
327 Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&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({ElementWithoutDelimiter, nullptr});
340 break;
341 }
342 case syntax::List::TerminationKind::Terminated:
343 case syntax::List::TerminationKind::MaybeTerminated: {
344 if (ElementWithoutDelimiter) {
345 Children.push_back({ElementWithoutDelimiter, nullptr});
346 }
347 break;
348 }
349 }
350
351 return Children;
352 }
353
354 // Almost the same implementation of `getElementsAsNodesAndDelimiters` but
355 // ignoring delimiters
getElementsAsNodes()356 std::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(ElementWithoutDelimiter);
367 }
368 ElementWithoutDelimiter = &C;
369 break;
370 }
371 case syntax::NodeRole::ListDelimiter: {
372 Children.push_back(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(ElementWithoutDelimiter);
384 break;
385 }
386 case syntax::List::TerminationKind::Terminated:
387 case syntax::List::TerminationKind::MaybeTerminated: {
388 if (ElementWithoutDelimiter) {
389 Children.push_back(ElementWithoutDelimiter);
390 }
391 break;
392 }
393 }
394
395 return Children;
396 }
397
getDelimiterTokenKind() const398 clang::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
getTerminationKind() const412 syntax::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
canBeEmpty() const426 bool 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