Coverage Report

Created: 2022-07-16 07:03

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