Coverage Report

Created: 2021-01-23 06:44

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