Coverage Report

Created: 2022-05-14 11:35

/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
}