/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Tooling/Syntax/Tree.cpp
Line | Count | Source (jump to first uncovered line) |
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/BitVector.h" |
13 | | #include "llvm/ADT/STLExtras.h" |
14 | | #include "llvm/Support/Casting.h" |
15 | | #include <cassert> |
16 | | |
17 | | using namespace clang; |
18 | | |
19 | | namespace { |
20 | | static void traverse(const syntax::Node *N, |
21 | 68.9k | llvm::function_ref<void(const syntax::Node *)> Visit) { |
22 | 68.9k | if (auto *T = dyn_cast<syntax::Tree>(N)) { |
23 | 30.8k | for (const syntax::Node &C : T->getChildren()) |
24 | 66.0k | traverse(&C, Visit); |
25 | 30.8k | } |
26 | 68.9k | Visit(N); |
27 | 68.9k | } |
28 | | static void traverse(syntax::Node *N, |
29 | 42 | llvm::function_ref<void(syntax::Node *)> Visit) { |
30 | 182 | traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) { |
31 | 182 | Visit(const_cast<syntax::Node *>(N)); |
32 | 182 | }); |
33 | 42 | } |
34 | | } // namespace |
35 | | |
36 | | syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts, |
37 | | const TokenBuffer &Tokens) |
38 | 2.16k | : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(Tokens) {} |
39 | | |
40 | 79.0k | const syntax::TokenBuffer &syntax::Arena::getTokenBuffer() const { |
41 | 79.0k | return Tokens; |
42 | 79.0k | } |
43 | | |
44 | | std::pair<FileID, ArrayRef<syntax::Token>> |
45 | 1.70k | syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) { |
46 | 1.70k | auto FID = SourceMgr.createFileID(std::move(Input)); |
47 | 1.70k | auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts)); |
48 | 1.70k | assert(It.second && "duplicate FileID"); |
49 | 0 | return {FID, It.first->second}; |
50 | 1.70k | } |
51 | | |
52 | 39.0k | syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) { |
53 | 39.0k | assert(Tok != nullptr); |
54 | 39.0k | } |
55 | | |
56 | | syntax::Node::Node(NodeKind Kind) |
57 | | : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr), |
58 | | Kind(static_cast<unsigned>(Kind)), Role(0), Original(false), |
59 | 73.5k | CanModify(false) { |
60 | 73.5k | this->setRole(NodeRole::Detached); |
61 | 73.5k | } |
62 | | |
63 | 140k | bool syntax::Node::isDetached() const { |
64 | 140k | return getRole() == NodeRole::Detached; |
65 | 140k | } |
66 | | |
67 | 144k | void syntax::Node::setRole(NodeRole NR) { |
68 | 144k | this->Role = static_cast<unsigned>(NR); |
69 | 144k | } |
70 | | |
71 | 2.34k | void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) { |
72 | 2.34k | assert(Child->getRole() == NodeRole::Detached); |
73 | 0 | assert(Role != NodeRole::Detached); |
74 | | |
75 | 0 | Child->setRole(Role); |
76 | 2.34k | appendChildLowLevel(Child); |
77 | 2.34k | } |
78 | | |
79 | 68.2k | void syntax::Tree::appendChildLowLevel(Node *Child) { |
80 | 68.2k | assert(Child->Parent == nullptr); |
81 | 0 | assert(Child->NextSibling == nullptr); |
82 | 0 | assert(Child->PreviousSibling == nullptr); |
83 | 0 | assert(Child->getRole() != NodeRole::Detached); |
84 | | |
85 | 0 | Child->Parent = this; |
86 | 68.2k | if (this->LastChild) { |
87 | 36.6k | Child->PreviousSibling = this->LastChild; |
88 | 36.6k | this->LastChild->NextSibling = Child; |
89 | 36.6k | } else |
90 | 31.5k | this->FirstChild = Child; |
91 | | |
92 | 68.2k | this->LastChild = Child; |
93 | 68.2k | } |
94 | | |
95 | 0 | void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) { |
96 | 0 | assert(Child->getRole() == NodeRole::Detached); |
97 | 0 | assert(Role != NodeRole::Detached); |
98 | | |
99 | 0 | Child->setRole(Role); |
100 | 0 | prependChildLowLevel(Child); |
101 | 0 | } |
102 | | |
103 | 0 | void syntax::Tree::prependChildLowLevel(Node *Child) { |
104 | 0 | assert(Child->Parent == nullptr); |
105 | 0 | assert(Child->NextSibling == nullptr); |
106 | 0 | assert(Child->PreviousSibling == nullptr); |
107 | 0 | assert(Child->getRole() != NodeRole::Detached); |
108 | | |
109 | 0 | Child->Parent = this; |
110 | 0 | if (this->FirstChild) { |
111 | 0 | Child->NextSibling = this->FirstChild; |
112 | 0 | this->FirstChild->PreviousSibling = Child; |
113 | 0 | } else |
114 | 0 | this->LastChild = Child; |
115 | |
|
116 | 0 | this->FirstChild = Child; |
117 | 0 | } |
118 | | |
119 | | void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End, |
120 | 42 | Node *New) { |
121 | 42 | assert((!Begin || Begin->Parent == this) && |
122 | 42 | "`Begin` is not a child of `this`."); |
123 | 0 | assert((!End || End->Parent == this) && "`End` is not a child of `this`."); |
124 | 0 | assert(canModify() && "Cannot modify `this`."); |
125 | | |
126 | 0 | #ifndef NDEBUG |
127 | 56 | for (auto *N = New; N; N = N->NextSibling14 ) { |
128 | 14 | assert(N->Parent == nullptr); |
129 | 0 | assert(N->getRole() != NodeRole::Detached && "Roles must be set"); |
130 | | // FIXME: validate the role. |
131 | 14 | } |
132 | | |
133 | 84 | auto Reachable = [](Node *From, Node *N) { |
134 | 84 | if (!N) |
135 | 0 | return true; |
136 | 210 | for (auto *It = From; 84 It; It = It->NextSibling126 ) |
137 | 210 | if (It == N) |
138 | 84 | return true; |
139 | 0 | return false; |
140 | 84 | }; |
141 | 42 | assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable."); |
142 | 0 | assert(Reachable(Begin, End) && "`End` is not after `Begin`."); |
143 | 0 | #endif |
144 | | |
145 | 42 | if (!New && Begin == End28 ) |
146 | 0 | return; |
147 | | |
148 | | // Mark modification. |
149 | 182 | for (auto *T = this; 42 T && T->Original140 ; T = T->Parent140 ) |
150 | 140 | T->Original = false; |
151 | | |
152 | | // Save the node before the range to be removed. Later we insert the `New` |
153 | | // range after this node. |
154 | 42 | auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild0 ; |
155 | | |
156 | | // Detach old nodes. |
157 | 84 | for (auto *N = Begin; N != End;) { |
158 | 42 | auto *Next = N->NextSibling; |
159 | | |
160 | 42 | N->setRole(NodeRole::Detached); |
161 | 42 | N->Parent = nullptr; |
162 | 42 | N->NextSibling = nullptr; |
163 | 42 | N->PreviousSibling = nullptr; |
164 | 42 | if (N->Original) |
165 | 182 | traverse(N, [](Node *C) 42 { C->Original = false; }); |
166 | | |
167 | 42 | N = Next; |
168 | 42 | } |
169 | | |
170 | | // Attach new range. |
171 | 42 | auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild0 ; |
172 | 42 | auto *&NewLast = End ? End->PreviousSibling : LastChild0 ; |
173 | | |
174 | 42 | if (!New) { |
175 | 28 | NewFirst = End; |
176 | 28 | NewLast = BeforeBegin; |
177 | 28 | return; |
178 | 28 | } |
179 | | |
180 | 14 | New->PreviousSibling = BeforeBegin; |
181 | 14 | NewFirst = New; |
182 | | |
183 | 14 | Node *LastInNew; |
184 | 28 | for (auto *N = New; N != nullptr; N = N->NextSibling14 ) { |
185 | 14 | LastInNew = N; |
186 | 14 | N->Parent = this; |
187 | 14 | } |
188 | 14 | LastInNew->NextSibling = End; |
189 | 14 | NewLast = LastInNew; |
190 | 14 | } |
191 | | |
192 | | namespace { |
193 | | static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L, |
194 | 18.6k | const SourceManager &SM) { |
195 | 18.6k | assert(L); |
196 | 0 | const auto *Token = L->getToken(); |
197 | 18.6k | assert(Token); |
198 | | // Handle 'eof' separately, calling text() on it produces an empty string. |
199 | 18.6k | if (Token->kind() == tok::eof) |
200 | 0 | OS << "<eof>"; |
201 | 18.6k | else |
202 | 18.6k | OS << Token->text(SM); |
203 | 18.6k | } |
204 | | |
205 | | static void dumpNode(raw_ostream &OS, const syntax::Node *N, |
206 | 32.5k | const SourceManager &SM, llvm::BitVector IndentMask) { |
207 | 32.5k | auto DumpExtraInfo = [&OS](const syntax::Node *N) { |
208 | 32.5k | if (N->getRole() != syntax::NodeRole::Unknown) |
209 | 18.8k | OS << " " << N->getRole(); |
210 | 32.5k | if (!N->isOriginal()) |
211 | 928 | OS << " synthesized"; |
212 | 32.5k | if (!N->canModify()) |
213 | 448 | OS << " unmodifiable"; |
214 | 32.5k | }; |
215 | | |
216 | 32.5k | assert(N); |
217 | 32.5k | if (const auto *L = dyn_cast<syntax::Leaf>(N)) { |
218 | 17.9k | OS << "'"; |
219 | 17.9k | dumpLeaf(OS, L, SM); |
220 | 17.9k | OS << "'"; |
221 | 17.9k | DumpExtraInfo(N); |
222 | 17.9k | OS << "\n"; |
223 | 17.9k | return; |
224 | 17.9k | } |
225 | | |
226 | 14.6k | const auto *T = cast<syntax::Tree>(N); |
227 | 14.6k | OS << T->getKind(); |
228 | 14.6k | DumpExtraInfo(N); |
229 | 14.6k | OS << "\n"; |
230 | | |
231 | 29.6k | for (const syntax::Node &It : T->getChildren()) { |
232 | 93.4k | for (unsigned Idx = 0; Idx < IndentMask.size(); ++Idx63.7k ) { |
233 | 63.7k | if (IndentMask[Idx]) |
234 | 27.1k | OS << "| "; |
235 | 36.6k | else |
236 | 36.6k | OS << " "; |
237 | 63.7k | } |
238 | 29.6k | if (!It.getNextSibling()) { |
239 | 14.6k | OS << "`-"; |
240 | 14.6k | IndentMask.push_back(false); |
241 | 15.0k | } else { |
242 | 15.0k | OS << "|-"; |
243 | 15.0k | IndentMask.push_back(true); |
244 | 15.0k | } |
245 | 29.6k | dumpNode(OS, &It, SM, IndentMask); |
246 | 29.6k | IndentMask.pop_back(); |
247 | 29.6k | } |
248 | 14.6k | } |
249 | | } // namespace |
250 | | |
251 | 2.92k | std::string syntax::Node::dump(const SourceManager &SM) const { |
252 | 2.92k | std::string Str; |
253 | 2.92k | llvm::raw_string_ostream OS(Str); |
254 | 2.92k | dumpNode(OS, this, SM, /*IndentMask=*/{}); |
255 | 2.92k | return std::move(OS.str()); |
256 | 2.92k | } |
257 | | |
258 | 698 | std::string syntax::Node::dumpTokens(const SourceManager &SM) const { |
259 | 698 | std::string Storage; |
260 | 698 | llvm::raw_string_ostream OS(Storage); |
261 | 698 | traverse(this, [&](const syntax::Node *N) { |
262 | 698 | if (const auto *L = dyn_cast<syntax::Leaf>(N)) { |
263 | 698 | dumpLeaf(OS, L, SM); |
264 | 698 | OS << " "; |
265 | 698 | } |
266 | 698 | }); |
267 | 698 | return Storage; |
268 | 698 | } |
269 | | |
270 | 71.4k | void syntax::Node::assertInvariants() const { |
271 | 71.4k | #ifndef NDEBUG |
272 | 71.4k | if (isDetached()) |
273 | 5.49k | assert(getParent() == nullptr); |
274 | 65.9k | else |
275 | 65.9k | assert(getParent() != nullptr); |
276 | | |
277 | 0 | const auto *T = dyn_cast<Tree>(this); |
278 | 71.4k | if (!T) |
279 | 39.0k | return; |
280 | 68.4k | for (const Node &C : T->getChildren())32.3k { |
281 | 68.4k | if (T->isOriginal()) |
282 | 65.9k | assert(C.isOriginal()); |
283 | 0 | assert(!C.isDetached()); |
284 | 0 | assert(C.getParent() == T); |
285 | 0 | const auto *Next = C.getNextSibling(); |
286 | 68.4k | assert(!Next || &C == Next->getPreviousSibling()); |
287 | 68.4k | if (!C.getNextSibling()) |
288 | 31.6k | assert(&C == T->getLastChild() && |
289 | 68.4k | "Last child is reachable by advancing from the first child."); |
290 | 68.4k | } |
291 | | |
292 | 32.3k | const auto *L = dyn_cast<List>(T); |
293 | 32.3k | if (!L) |
294 | 26.8k | return; |
295 | 7.24k | for (const Node &C : T->getChildren())5.55k { |
296 | 7.24k | assert(C.getRole() == NodeRole::ListElement || |
297 | 7.24k | C.getRole() == NodeRole::ListDelimiter); |
298 | 7.24k | if (C.getRole() == NodeRole::ListDelimiter) { |
299 | 999 | assert(isa<Leaf>(C)); |
300 | 0 | assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind()); |
301 | 999 | } |
302 | 7.24k | } |
303 | | |
304 | 5.55k | #endif |
305 | 5.55k | } |
306 | | |
307 | 2.16k | void syntax::Node::assertInvariantsRecursive() const { |
308 | 2.16k | #ifndef NDEBUG |
309 | 68.1k | traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); }); |
310 | 2.16k | #endif |
311 | 2.16k | } |
312 | | |
313 | 53.7k | const syntax::Leaf *syntax::Tree::findFirstLeaf() const { |
314 | 53.7k | for (const Node &C : getChildren()) { |
315 | 53.7k | if (const auto *L = dyn_cast<syntax::Leaf>(&C)) |
316 | 35.0k | return L; |
317 | 18.6k | if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf()) |
318 | 18.5k | return L; |
319 | 18.6k | } |
320 | 112 | return nullptr; |
321 | 53.7k | } |
322 | | |
323 | 63.5k | const syntax::Leaf *syntax::Tree::findLastLeaf() const { |
324 | 63.6k | for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()112 ) { |
325 | 63.5k | if (const auto *L = dyn_cast<syntax::Leaf>(C)) |
326 | 35.0k | return L; |
327 | 28.5k | if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf()) |
328 | 28.3k | return L; |
329 | 28.5k | } |
330 | 112 | return nullptr; |
331 | 63.5k | } |
332 | | |
333 | 0 | const syntax::Node *syntax::Tree::findChild(NodeRole R) const { |
334 | 0 | for (const Node &C : getChildren()) { |
335 | 0 | if (C.getRole() == R) |
336 | 0 | return &C; |
337 | 0 | } |
338 | 0 | return nullptr; |
339 | 0 | } |
340 | | |
341 | | std::vector<syntax::List::ElementAndDelimiter<syntax::Node>> |
342 | 96 | syntax::List::getElementsAsNodesAndDelimiters() { |
343 | 96 | if (!getFirstChild()) |
344 | 0 | return {}; |
345 | | |
346 | 96 | std::vector<syntax::List::ElementAndDelimiter<Node>> Children; |
347 | 96 | syntax::Node *ElementWithoutDelimiter = nullptr; |
348 | 448 | for (Node &C : getChildren()) { |
349 | 448 | switch (C.getRole()) { |
350 | 250 | case syntax::NodeRole::ListElement: { |
351 | 250 | if (ElementWithoutDelimiter) { |
352 | 24 | Children.push_back({ElementWithoutDelimiter, nullptr}); |
353 | 24 | } |
354 | 250 | ElementWithoutDelimiter = &C; |
355 | 250 | break; |
356 | 0 | } |
357 | 198 | case syntax::NodeRole::ListDelimiter: { |
358 | 198 | Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)}); |
359 | 198 | ElementWithoutDelimiter = nullptr; |
360 | 198 | break; |
361 | 0 | } |
362 | 0 | default: |
363 | 0 | llvm_unreachable( |
364 | 448 | "A list can have only elements and delimiters as children."); |
365 | 448 | } |
366 | 448 | } |
367 | | |
368 | 96 | switch (getTerminationKind()) { |
369 | 56 | case syntax::List::TerminationKind::Separated: { |
370 | 56 | Children.push_back({ElementWithoutDelimiter, nullptr}); |
371 | 56 | break; |
372 | 0 | } |
373 | 40 | case syntax::List::TerminationKind::Terminated: |
374 | 40 | case syntax::List::TerminationKind::MaybeTerminated: { |
375 | 40 | if (ElementWithoutDelimiter) { |
376 | 10 | Children.push_back({ElementWithoutDelimiter, nullptr}); |
377 | 10 | } |
378 | 40 | break; |
379 | 40 | } |
380 | 96 | } |
381 | | |
382 | 96 | return Children; |
383 | 96 | } |
384 | | |
385 | | // Almost the same implementation of `getElementsAsNodesAndDelimiters` but |
386 | | // ignoring delimiters |
387 | 96 | std::vector<syntax::Node *> syntax::List::getElementsAsNodes() { |
388 | 96 | if (!getFirstChild()) |
389 | 0 | return {}; |
390 | | |
391 | 96 | std::vector<syntax::Node *> Children; |
392 | 96 | syntax::Node *ElementWithoutDelimiter = nullptr; |
393 | 448 | for (Node &C : getChildren()) { |
394 | 448 | switch (C.getRole()) { |
395 | 250 | case syntax::NodeRole::ListElement: { |
396 | 250 | if (ElementWithoutDelimiter) { |
397 | 24 | Children.push_back(ElementWithoutDelimiter); |
398 | 24 | } |
399 | 250 | ElementWithoutDelimiter = &C; |
400 | 250 | break; |
401 | 0 | } |
402 | 198 | case syntax::NodeRole::ListDelimiter: { |
403 | 198 | Children.push_back(ElementWithoutDelimiter); |
404 | 198 | ElementWithoutDelimiter = nullptr; |
405 | 198 | break; |
406 | 0 | } |
407 | 0 | default: |
408 | 0 | llvm_unreachable("A list has only elements or delimiters."); |
409 | 448 | } |
410 | 448 | } |
411 | | |
412 | 96 | switch (getTerminationKind()) { |
413 | 56 | case syntax::List::TerminationKind::Separated: { |
414 | 56 | Children.push_back(ElementWithoutDelimiter); |
415 | 56 | break; |
416 | 0 | } |
417 | 40 | case syntax::List::TerminationKind::Terminated: |
418 | 40 | case syntax::List::TerminationKind::MaybeTerminated: { |
419 | 40 | if (ElementWithoutDelimiter) { |
420 | 10 | Children.push_back(ElementWithoutDelimiter); |
421 | 10 | } |
422 | 40 | break; |
423 | 40 | } |
424 | 96 | } |
425 | | |
426 | 96 | return Children; |
427 | 96 | } |
428 | | |
429 | 999 | clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const { |
430 | 999 | switch (this->getKind()) { |
431 | 371 | case NodeKind::NestedNameSpecifier: |
432 | 371 | return clang::tok::coloncolon; |
433 | 150 | case NodeKind::CallArguments: |
434 | 558 | case NodeKind::ParameterDeclarationList: |
435 | 628 | case NodeKind::DeclaratorList: |
436 | 628 | return clang::tok::comma; |
437 | 0 | default: |
438 | 0 | llvm_unreachable("This is not a subclass of List, thus " |
439 | 999 | "getDelimiterTokenKind() cannot be called"); |
440 | 999 | } |
441 | 999 | } |
442 | | |
443 | 192 | syntax::List::TerminationKind syntax::List::getTerminationKind() const { |
444 | 192 | switch (this->getKind()) { |
445 | 80 | case NodeKind::NestedNameSpecifier: |
446 | 80 | return TerminationKind::Terminated; |
447 | 112 | case NodeKind::CallArguments: |
448 | 112 | case NodeKind::ParameterDeclarationList: |
449 | 112 | case NodeKind::DeclaratorList: |
450 | 112 | return TerminationKind::Separated; |
451 | 0 | default: |
452 | 0 | llvm_unreachable("This is not a subclass of List, thus " |
453 | 192 | "getTerminationKind() cannot be called"); |
454 | 192 | } |
455 | 192 | } |
456 | | |
457 | 0 | bool syntax::List::canBeEmpty() const { |
458 | 0 | switch (this->getKind()) { |
459 | 0 | case NodeKind::NestedNameSpecifier: |
460 | 0 | return false; |
461 | 0 | case NodeKind::CallArguments: |
462 | 0 | return true; |
463 | 0 | case NodeKind::ParameterDeclarationList: |
464 | 0 | return true; |
465 | 0 | case NodeKind::DeclaratorList: |
466 | 0 | return true; |
467 | 0 | default: |
468 | 0 | llvm_unreachable("This is not a subclass of List, thus canBeEmpty() " |
469 | 0 | "cannot be called"); |
470 | 0 | } |
471 | 0 | } |