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