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