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