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                      TokenBuffer Tokens)
37     : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {}
38 
39 const clang::syntax::TokenBuffer &syntax::Arena::tokenBuffer() const {
40   return Tokens;
41 }
42 
43 std::pair<FileID, llvm::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->kind() == 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 { return role() == NodeRole::Detached; }
66 
67 void syntax::Node::setRole(NodeRole NR) {
68   this->Role = static_cast<unsigned>(NR);
69 }
70 
71 bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
72 
73 void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
74   assert(Child->role() == NodeRole::Detached);
75   assert(Role != NodeRole::Detached);
76 
77   Child->setRole(Role);
78   prependChildLowLevel(Child);
79 }
80 
81 void syntax::Tree::prependChildLowLevel(Node *Child) {
82   assert(Child->Parent == nullptr);
83   assert(Child->NextSibling == nullptr);
84   assert(Child->role() != NodeRole::Detached);
85 
86   Child->Parent = this;
87   Child->NextSibling = this->FirstChild;
88   this->FirstChild = Child;
89 }
90 
91 void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
92                                              Node *New) {
93   assert(!BeforeBegin || BeforeBegin->Parent == this);
94 
95 #ifndef NDEBUG
96   for (auto *N = New; N; N = N->nextSibling()) {
97     assert(N->Parent == nullptr);
98     assert(N->role() != NodeRole::Detached && "Roles must be set");
99     // FIXME: sanity-check the role.
100   }
101 #endif
102 
103   // Detach old nodes.
104   for (auto *N = !BeforeBegin ? FirstChild : BeforeBegin->nextSibling();
105        N != End;) {
106     auto *Next = N->NextSibling;
107 
108     N->setRole(NodeRole::Detached);
109     N->Parent = nullptr;
110     N->NextSibling = nullptr;
111     if (N->Original)
112       traverse(N, [&](Node *C) { C->Original = false; });
113 
114     N = Next;
115   }
116 
117   // Attach new nodes.
118   if (BeforeBegin)
119     BeforeBegin->NextSibling = New ? New : End;
120   else
121     FirstChild = New ? New : End;
122 
123   if (New) {
124     auto *Last = New;
125     for (auto *N = New; N != nullptr; N = N->nextSibling()) {
126       Last = N;
127       N->Parent = this;
128     }
129     Last->NextSibling = End;
130   }
131 
132   // Mark the node as modified.
133   for (auto *T = this; T && T->Original; T = T->Parent)
134     T->Original = false;
135 }
136 
137 namespace {
138 static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens,
139                        const SourceManager &SM) {
140   assert(!Tokens.empty());
141   bool First = true;
142   for (const auto &T : Tokens) {
143     if (!First)
144       OS << " ";
145     else
146       First = false;
147     // Handle 'eof' separately, calling text() on it produces an empty string.
148     if (T.kind() == tok::eof) {
149       OS << "<eof>";
150       continue;
151     }
152     OS << T.text(SM);
153   }
154 }
155 
156 static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
157                      const syntax::Arena &A, std::vector<bool> IndentMask) {
158   std::string Marks;
159   if (!N->isOriginal())
160     Marks += "M";
161   if (N->role() == syntax::NodeRole::Detached)
162     Marks += "*"; // FIXME: find a nice way to print other roles.
163   if (!N->canModify())
164     Marks += "I";
165   if (!Marks.empty())
166     OS << Marks << ": ";
167 
168   if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
169     dumpTokens(OS, *L->token(), A.sourceManager());
170     OS << "\n";
171     return;
172   }
173 
174   auto *T = llvm::cast<syntax::Tree>(N);
175   OS << T->kind() << "\n";
176 
177   for (auto It = T->firstChild(); It != nullptr; It = It->nextSibling()) {
178     for (bool Filled : IndentMask) {
179       if (Filled)
180         OS << "| ";
181       else
182         OS << "  ";
183     }
184     if (!It->nextSibling()) {
185       OS << "`-";
186       IndentMask.push_back(false);
187     } else {
188       OS << "|-";
189       IndentMask.push_back(true);
190     }
191     dumpTree(OS, It, A, IndentMask);
192     IndentMask.pop_back();
193   }
194 }
195 } // namespace
196 
197 std::string syntax::Node::dump(const Arena &A) const {
198   std::string Str;
199   llvm::raw_string_ostream OS(Str);
200   dumpTree(OS, this, A, /*IndentMask=*/{});
201   return std::move(OS.str());
202 }
203 
204 std::string syntax::Node::dumpTokens(const Arena &A) const {
205   std::string Storage;
206   llvm::raw_string_ostream OS(Storage);
207   traverse(this, [&](const syntax::Node *N) {
208     auto *L = llvm::dyn_cast<syntax::Leaf>(N);
209     if (!L)
210       return;
211     ::dumpTokens(OS, *L->token(), A.sourceManager());
212     OS << " ";
213   });
214   return OS.str();
215 }
216 
217 void syntax::Node::assertInvariants() const {
218 #ifndef NDEBUG
219   if (isDetached())
220     assert(parent() == nullptr);
221   else
222     assert(parent() != nullptr);
223 
224   auto *T = dyn_cast<Tree>(this);
225   if (!T)
226     return;
227   for (auto *C = T->firstChild(); C; C = C->nextSibling()) {
228     if (T->isOriginal())
229       assert(C->isOriginal());
230     assert(!C->isDetached());
231     assert(C->parent() == T);
232   }
233 #endif
234 }
235 
236 void syntax::Node::assertInvariantsRecursive() const {
237 #ifndef NDEBUG
238   traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
239 #endif
240 }
241 
242 syntax::Leaf *syntax::Tree::firstLeaf() {
243   auto *T = this;
244   while (auto *C = T->firstChild()) {
245     if (auto *L = dyn_cast<syntax::Leaf>(C))
246       return L;
247     T = cast<syntax::Tree>(C);
248   }
249   return nullptr;
250 }
251 
252 syntax::Leaf *syntax::Tree::lastLeaf() {
253   auto *T = this;
254   while (auto *C = T->firstChild()) {
255     // Find the last child.
256     while (auto *Next = C->nextSibling())
257       C = Next;
258 
259     if (auto *L = dyn_cast<syntax::Leaf>(C))
260       return L;
261     T = cast<syntax::Tree>(C);
262   }
263   return nullptr;
264 }
265 
266 syntax::Node *syntax::Tree::findChild(NodeRole R) {
267   for (auto *C = FirstChild; C; C = C->nextSibling()) {
268     if (C->role() == R)
269       return C;
270   }
271   return nullptr;
272 }
273