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 {
traverse(const syntax::Node * N,llvm::function_ref<void (const syntax::Node *)> Visit)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 }
traverse(syntax::Node * N,llvm::function_ref<void (syntax::Node *)> Visit)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
Arena(SourceManager & SourceMgr,const LangOptions & LangOpts,TokenBuffer Tokens)35 syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
36 TokenBuffer Tokens)
37 : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {}
38
tokenBuffer() const39 const clang::syntax::TokenBuffer &syntax::Arena::tokenBuffer() const {
40 return Tokens;
41 }
42
43 std::pair<FileID, llvm::ArrayRef<syntax::Token>>
lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input)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
Leaf(const syntax::Token * Tok)51 syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
52 assert(Tok != nullptr);
53 }
54
classof(const Node * N)55 bool syntax::Leaf::classof(const Node *N) {
56 return N->kind() == NodeKind::Leaf;
57 }
58
Node(NodeKind Kind)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
isDetached() const65 bool syntax::Node::isDetached() const { return role() == NodeRole::Detached; }
66
setRole(NodeRole NR)67 void syntax::Node::setRole(NodeRole NR) {
68 this->Role = static_cast<unsigned>(NR);
69 }
70
classof(const Node * N)71 bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
72
prependChildLowLevel(Node * Child,NodeRole Role)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
prependChildLowLevel(Node * Child)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
replaceChildRangeLowLevel(Node * BeforeBegin,Node * End,Node * New)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 {
dumpTokens(llvm::raw_ostream & OS,ArrayRef<syntax::Token> Tokens,const SourceManager & SM)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
dumpTree(llvm::raw_ostream & OS,const syntax::Node * N,const syntax::Arena & A,std::vector<bool> IndentMask)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
dump(const Arena & A) const197 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
dumpTokens(const Arena & A) const204 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
assertInvariants() const217 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
assertInvariantsRecursive() const236 void syntax::Node::assertInvariantsRecursive() const {
237 #ifndef NDEBUG
238 traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
239 #endif
240 }
241
firstLeaf()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
lastLeaf()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
findChild(NodeRole R)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