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 "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 (const syntax::Node &C : T->getChildren())
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::Leaf::Leaf(syntax::TokenManager::Key K) : Node(NodeKind::Leaf), K(K) {}
36 
37 syntax::Node::Node(NodeKind Kind)
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 
44 bool syntax::Node::isDetached() const {
45   return getRole() == NodeRole::Detached;
46 }
47 
48 void syntax::Node::setRole(NodeRole NR) {
49   this->Role = static_cast<unsigned>(NR);
50 }
51 
52 void 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);
58 }
59 
60 void 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 
76 void 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 
84 void 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 
100 void 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 
173 namespace {
174 static 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) {
177     if (N->getRole() != syntax::NodeRole::Unknown)
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 
220 std::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 
227 std::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 
239 void syntax::Node::assertInvariants() const {
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 
277 void syntax::Node::assertInvariantsRecursive() const {
278 #ifndef NDEBUG
279   traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
280 #endif
281 }
282 
283 const syntax::Leaf *syntax::Tree::findFirstLeaf() const {
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 
293 const syntax::Leaf *syntax::Tree::findLastLeaf() const {
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 
303 const syntax::Node *syntax::Tree::findChild(NodeRole R) const {
304   for (const Node &C : getChildren()) {
305     if (C.getRole() == R)
306       return &C;
307   }
308   return nullptr;
309 }
310 
311 std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
312 syntax::List::getElementsAsNodesAndDelimiters() {
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()) {
320     case syntax::NodeRole::ListElement: {
321       if (ElementWithoutDelimiter) {
322         Children.push_back({ElementWithoutDelimiter, nullptr});
323       }
324       ElementWithoutDelimiter = &C;
325       break;
326     }
327     case syntax::NodeRole::ListDelimiter: {
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()) {
339   case syntax::List::TerminationKind::Separated: {
340     Children.push_back({ElementWithoutDelimiter, nullptr});
341     break;
342   }
343   case syntax::List::TerminationKind::Terminated:
344   case syntax::List::TerminationKind::MaybeTerminated: {
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
357 std::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()) {
365     case syntax::NodeRole::ListElement: {
366       if (ElementWithoutDelimiter) {
367         Children.push_back(ElementWithoutDelimiter);
368       }
369       ElementWithoutDelimiter = &C;
370       break;
371     }
372     case syntax::NodeRole::ListDelimiter: {
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()) {
383   case syntax::List::TerminationKind::Separated: {
384     Children.push_back(ElementWithoutDelimiter);
385     break;
386   }
387   case syntax::List::TerminationKind::Terminated:
388   case syntax::List::TerminationKind::MaybeTerminated: {
389     if (ElementWithoutDelimiter) {
390       Children.push_back(ElementWithoutDelimiter);
391     }
392     break;
393   }
394   }
395 
396   return Children;
397 }
398 
399 clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const {
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 
413 syntax::List::TerminationKind syntax::List::getTerminationKind() const {
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 
427 bool syntax::List::canBeEmpty() const {
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 }
442