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/STLExtras.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 auto *C = T->getFirstChild(); C; C = C->getNextSibling())
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::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
36                      const TokenBuffer &Tokens)
37     : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(Tokens) {}
38 
39 const syntax::TokenBuffer &syntax::Arena::getTokenBuffer() const {
40   return Tokens;
41 }
42 
43 std::pair<FileID, ArrayRef<syntax::Token>>
44 syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
45   auto FID = SourceMgr.createFileID(std::move(Input));
46   auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
47   assert(It.second && "duplicate FileID");
48   return {FID, It.first->second};
49 }
50 
51 syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
52   assert(Tok != nullptr);
53 }
54 
55 bool syntax::Leaf::classof(const Node *N) {
56   return N->getKind() == NodeKind::Leaf;
57 }
58 
59 syntax::Node::Node(NodeKind Kind)
60     : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
61       Role(0), Original(false), CanModify(false) {
62   this->setRole(NodeRole::Detached);
63 }
64 
65 bool syntax::Node::isDetached() const {
66   return getRole() == NodeRole::Detached;
67 }
68 
69 void syntax::Node::setRole(NodeRole NR) {
70   this->Role = static_cast<unsigned>(NR);
71 }
72 
73 bool syntax::Tree::classof(const Node *N) {
74   return N->getKind() > NodeKind::Leaf;
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->getRole() != NodeRole::Detached);
89 
90   Child->Parent = this;
91   Child->NextSibling = this->FirstChild;
92   this->FirstChild = Child;
93 }
94 
95 void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
96                                              Node *New) {
97   assert(!BeforeBegin || BeforeBegin->Parent == this);
98 
99 #ifndef NDEBUG
100   for (auto *N = New; N; N = N->getNextSibling()) {
101     assert(N->Parent == nullptr);
102     assert(N->getRole() != NodeRole::Detached && "Roles must be set");
103     // FIXME: sanity-check the role.
104   }
105 #endif
106 
107   // Detach old nodes.
108   for (auto *N = !BeforeBegin ? FirstChild : BeforeBegin->getNextSibling();
109        N != End;) {
110     auto *Next = N->NextSibling;
111 
112     N->setRole(NodeRole::Detached);
113     N->Parent = nullptr;
114     N->NextSibling = nullptr;
115     if (N->Original)
116       traverse(N, [&](Node *C) { C->Original = false; });
117 
118     N = Next;
119   }
120 
121   // Attach new nodes.
122   if (BeforeBegin)
123     BeforeBegin->NextSibling = New ? New : End;
124   else
125     FirstChild = New ? New : End;
126 
127   if (New) {
128     auto *Last = New;
129     for (auto *N = New; N != nullptr; N = N->getNextSibling()) {
130       Last = N;
131       N->Parent = this;
132     }
133     Last->NextSibling = End;
134   }
135 
136   // Mark the node as modified.
137   for (auto *T = this; T && T->Original; T = T->Parent)
138     T->Original = false;
139 }
140 
141 namespace {
142 static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L,
143                      const SourceManager &SM) {
144   assert(L);
145   const auto *Token = L->getToken();
146   assert(Token);
147   // Handle 'eof' separately, calling text() on it produces an empty string.
148   if (Token->kind() == tok::eof)
149     OS << "<eof>";
150   else
151     OS << Token->text(SM);
152 }
153 
154 static void dumpNode(raw_ostream &OS, const syntax::Node *N,
155                      const SourceManager &SM, std::vector<bool> IndentMask) {
156   auto dumpExtraInfo = [&OS](const syntax::Node *N) {
157     if (N->getRole() != syntax::NodeRole::Unknown)
158       OS << " " << N->getRole();
159     if (!N->isOriginal())
160       OS << " synthesized";
161     if (!N->canModify())
162       OS << " unmodifiable";
163   };
164 
165   assert(N);
166   if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
167     OS << "'";
168     dumpLeaf(OS, L, SM);
169     OS << "'";
170     dumpExtraInfo(N);
171     OS << "\n";
172     return;
173   }
174 
175   const auto *T = cast<syntax::Tree>(N);
176   OS << T->getKind();
177   dumpExtraInfo(N);
178   OS << "\n";
179 
180   for (const auto *It = T->getFirstChild(); It; It = It->getNextSibling()) {
181     for (bool Filled : IndentMask) {
182       if (Filled)
183         OS << "| ";
184       else
185         OS << "  ";
186     }
187     if (!It->getNextSibling()) {
188       OS << "`-";
189       IndentMask.push_back(false);
190     } else {
191       OS << "|-";
192       IndentMask.push_back(true);
193     }
194     dumpNode(OS, It, SM, IndentMask);
195     IndentMask.pop_back();
196   }
197 }
198 } // namespace
199 
200 std::string syntax::Node::dump(const SourceManager &SM) const {
201   std::string Str;
202   llvm::raw_string_ostream OS(Str);
203   dumpNode(OS, this, SM, /*IndentMask=*/{});
204   return std::move(OS.str());
205 }
206 
207 std::string syntax::Node::dumpTokens(const SourceManager &SM) const {
208   std::string Storage;
209   llvm::raw_string_ostream OS(Storage);
210   traverse(this, [&](const syntax::Node *N) {
211     if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
212       dumpLeaf(OS, L, SM);
213       OS << " ";
214     }
215   });
216   return OS.str();
217 }
218 
219 void syntax::Node::assertInvariants() const {
220 #ifndef NDEBUG
221   if (isDetached())
222     assert(getParent() == nullptr);
223   else
224     assert(getParent() != nullptr);
225 
226   auto *T = dyn_cast<Tree>(this);
227   if (!T)
228     return;
229   for (const auto *C = T->getFirstChild(); C; C = C->getNextSibling()) {
230     if (T->isOriginal())
231       assert(C->isOriginal());
232     assert(!C->isDetached());
233     assert(C->getParent() == T);
234   }
235 #endif
236 }
237 
238 void syntax::Node::assertInvariantsRecursive() const {
239 #ifndef NDEBUG
240   traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
241 #endif
242 }
243 
244 syntax::Leaf *syntax::Tree::findFirstLeaf() {
245   auto *T = this;
246   while (auto *C = T->getFirstChild()) {
247     if (auto *L = dyn_cast<syntax::Leaf>(C))
248       return L;
249     T = cast<syntax::Tree>(C);
250   }
251   return nullptr;
252 }
253 
254 syntax::Leaf *syntax::Tree::findLastLeaf() {
255   auto *T = this;
256   while (auto *C = T->getFirstChild()) {
257     // Find the last child.
258     while (auto *Next = C->getNextSibling())
259       C = Next;
260 
261     if (auto *L = dyn_cast<syntax::Leaf>(C))
262       return L;
263     T = cast<syntax::Tree>(C);
264   }
265   return nullptr;
266 }
267 
268 syntax::Node *syntax::Tree::findChild(NodeRole R) {
269   for (auto *C = FirstChild; C; C = C->getNextSibling()) {
270     if (C->getRole() == R)
271       return C;
272   }
273   return nullptr;
274 }
275 
276 std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
277 syntax::List::getElementsAsNodesAndDelimiters() {
278   if (!getFirstChild())
279     return {};
280 
281   auto children = std::vector<syntax::List::ElementAndDelimiter<Node>>();
282   syntax::Node *elementWithoutDelimiter = nullptr;
283   for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
284     switch (C->getRole()) {
285     case syntax::NodeRole::ListElement: {
286       if (elementWithoutDelimiter) {
287         children.push_back({elementWithoutDelimiter, nullptr});
288       }
289       elementWithoutDelimiter = C;
290       break;
291     }
292     case syntax::NodeRole::ListDelimiter: {
293       children.push_back({elementWithoutDelimiter, cast<syntax::Leaf>(C)});
294       elementWithoutDelimiter = nullptr;
295       break;
296     }
297     default:
298       llvm_unreachable(
299           "A list can have only elements and delimiters as children.");
300     }
301   }
302 
303   switch (getTerminationKind()) {
304   case syntax::List::TerminationKind::Separated: {
305     children.push_back({elementWithoutDelimiter, nullptr});
306     break;
307   }
308   case syntax::List::TerminationKind::Terminated:
309   case syntax::List::TerminationKind::MaybeTerminated: {
310     if (elementWithoutDelimiter) {
311       children.push_back({elementWithoutDelimiter, nullptr});
312     }
313     break;
314   }
315   }
316 
317   return children;
318 }
319 
320 // Almost the same implementation of `getElementsAsNodesAndDelimiters` but
321 // ignoring delimiters
322 std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
323   if (!getFirstChild())
324     return {};
325 
326   auto children = std::vector<syntax::Node *>();
327   syntax::Node *elementWithoutDelimiter = nullptr;
328   for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
329     switch (C->getRole()) {
330     case syntax::NodeRole::ListElement: {
331       if (elementWithoutDelimiter) {
332         children.push_back(elementWithoutDelimiter);
333       }
334       elementWithoutDelimiter = C;
335       break;
336     }
337     case syntax::NodeRole::ListDelimiter: {
338       children.push_back(elementWithoutDelimiter);
339       elementWithoutDelimiter = nullptr;
340       break;
341     }
342     default:
343       llvm_unreachable("A list has only elements or delimiters.");
344     }
345   }
346 
347   switch (getTerminationKind()) {
348   case syntax::List::TerminationKind::Separated: {
349     children.push_back(elementWithoutDelimiter);
350     break;
351   }
352   case syntax::List::TerminationKind::Terminated:
353   case syntax::List::TerminationKind::MaybeTerminated: {
354     if (elementWithoutDelimiter) {
355       children.push_back(elementWithoutDelimiter);
356     }
357     break;
358   }
359   }
360 
361   return children;
362 }
363 
364 clang::tok::TokenKind syntax::List::getDelimiterTokenKind() {
365   switch (this->getKind()) {
366   case NodeKind::NestedNameSpecifier:
367     return clang::tok::coloncolon;
368   case NodeKind::CallArguments:
369   case NodeKind::ParameterDeclarationList:
370     return clang::tok::comma;
371   default:
372     llvm_unreachable("This is not a subclass of List, thus "
373                      "getDelimiterTokenKind() cannot be called");
374   }
375 }
376 
377 syntax::List::TerminationKind syntax::List::getTerminationKind() {
378   switch (this->getKind()) {
379   case NodeKind::NestedNameSpecifier:
380     return TerminationKind::Terminated;
381   case NodeKind::CallArguments:
382   case NodeKind::ParameterDeclarationList:
383     return TerminationKind::Separated;
384   default:
385     llvm_unreachable("This is not a subclass of List, thus "
386                      "getTerminationKind() cannot be called");
387   }
388 }
389 
390 bool syntax::List::canBeEmpty() {
391   switch (this->getKind()) {
392   case NodeKind::NestedNameSpecifier:
393     return false;
394   case NodeKind::CallArguments:
395     return true;
396   case NodeKind::ParameterDeclarationList:
397     return true;
398   default:
399     llvm_unreachable("This is not a subclass of List, thus canBeEmpty() "
400                      "cannot be called");
401   }
402 }
403