Coverage Report

Created: 2020-09-19 12:23

/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
60.9k
                     llvm::function_ref<void(const syntax::Node *)> Visit) {
21
60.9k
  if (auto *T = dyn_cast<syntax::Tree>(N)) {
22
84.1k
    for (const auto *C = T->getFirstChild(); C; 
C = C->getNextSibling()59.0k
)
23
59.0k
      traverse(C, Visit);
24
25.1k
  }
25
60.9k
  Visit(N);
26
60.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
syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
36
                     const TokenBuffer &Tokens)
37
1.87k
    : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(Tokens) {}
38
39
70.2k
const syntax::TokenBuffer &syntax::Arena::getTokenBuffer() const {
40
70.2k
  return Tokens;
41
70.2k
}
42
43
std::pair<FileID, ArrayRef<syntax::Token>>
44
154
syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
45
154
  auto FID = SourceMgr.createFileID(std::move(Input));
46
154
  auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
47
154
  assert(It.second && "duplicate FileID");
48
154
  return {FID, It.first->second};
49
154
}
50
51
35.8k
syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
52
35.8k
  assert(Tok != nullptr);
53
35.8k
}
54
55
288k
bool syntax::Leaf::classof(const Node *N) {
56
288k
  return N->getKind() == NodeKind::Leaf;
57
288k
}
58
59
syntax::Node::Node(NodeKind Kind)
60
    : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
61
62.5k
      Role(0), Original(false), CanModify(false) {
62
62.5k
  this->setRole(NodeRole::Detached);
63
62.5k
}
64
65
120k
bool syntax::Node::isDetached() const {
66
120k
  return getRole() == NodeRole::Detached;
67
120k
}
68
69
123k
void syntax::Node::setRole(NodeRole NR) {
70
123k
  this->Role = static_cast<unsigned>(NR);
71
123k
}
72
73
331k
bool syntax::Tree::classof(const Node *N) {
74
331k
  return N->getKind() > NodeKind::Leaf;
75
331k
}
76
77
126
void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
78
126
  assert(Child->getRole() == NodeRole::Detached);
79
126
  assert(Role != NodeRole::Detached);
80
126
81
126
  Child->setRole(Role);
82
126
  prependChildLowLevel(Child);
83
126
}
84
85
59.0k
void syntax::Tree::prependChildLowLevel(Node *Child) {
86
59.0k
  assert(Child->Parent == nullptr);
87
59.0k
  assert(Child->NextSibling == nullptr);
88
59.0k
  assert(Child->getRole() != NodeRole::Detached);
89
59.0k
90
59.0k
  Child->Parent = this;
91
59.0k
  Child->NextSibling = this->FirstChild;
92
59.0k
  this->FirstChild = Child;
93
59.0k
}
94
95
void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
96
42
                                             Node *New) {
97
42
  assert(!BeforeBegin || BeforeBegin->Parent == this);
98
42
99
42
#ifndef NDEBUG
100
56
  for (auto *N = New; N; 
N = N->getNextSibling()14
) {
101
14
    assert(N->Parent == nullptr);
102
14
    assert(N->getRole() != NodeRole::Detached && "Roles must be set");
103
    // FIXME: sanity-check the role.
104
14
  }
105
42
#endif
106
42
107
  // Detach old nodes.
108
42
  for (auto *N = !BeforeBegin ? 
FirstChild0
: BeforeBegin->getNextSibling();
109
84
       N != End;) {
110
42
    auto *Next = N->NextSibling;
111
42
112
42
    N->setRole(NodeRole::Detached);
113
42
    N->Parent = nullptr;
114
42
    N->NextSibling = nullptr;
115
42
    if (N->Original)
116
182
      
traverse(N, [&](Node *C) 42
{ C->Original = false; });
117
42
118
42
    N = Next;
119
42
  }
120
42
121
  // Attach new nodes.
122
42
  if (BeforeBegin)
123
42
    BeforeBegin->NextSibling = New ? 
New14
:
End28
;
124
0
  else
125
0
    FirstChild = New ? New : End;
126
42
127
42
  if (New) {
128
14
    auto *Last = New;
129
28
    for (auto *N = New; N != nullptr; 
N = N->getNextSibling()14
) {
130
14
      Last = N;
131
14
      N->Parent = this;
132
14
    }
133
14
    Last->NextSibling = End;
134
14
  }
135
42
136
  // Mark the node as modified.
137
182
  for (auto *T = this; T && 
T->Original140
;
T = T->Parent140
)
138
140
    T->Original = false;
139
42
}
140
141
namespace {
142
static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L,
143
16.8k
                     const SourceManager &SM) {
144
16.8k
  assert(L);
145
16.8k
  const auto *Token = L->getToken();
146
16.8k
  assert(Token);
147
  // Handle 'eof' separately, calling text() on it produces an empty string.
148
16.8k
  if (Token->kind() == tok::eof)
149
0
    OS << "<eof>";
150
16.8k
  else
151
16.8k
    OS << Token->text(SM);
152
16.8k
}
153
154
static void dumpNode(raw_ostream &OS, const syntax::Node *N,
155
29.0k
                     const SourceManager &SM, std::vector<bool> IndentMask) {
156
29.0k
  auto dumpExtraInfo = [&OS](const syntax::Node *N) {
157
29.0k
    if (N->getRole() != syntax::NodeRole::Unknown)
158
15.7k
      OS << " " << N->getRole();
159
29.0k
    if (!N->isOriginal())
160
224
      OS << " synthesized";
161
29.0k
    if (!N->canModify())
162
168
      OS << " unmodifiable";
163
29.0k
  };
164
29.0k
165
29.0k
  assert(N);
166
29.0k
  if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
167
16.8k
    OS << "'";
168
16.8k
    dumpLeaf(OS, L, SM);
169
16.8k
    OS << "'";
170
16.8k
    dumpExtraInfo(N);
171
16.8k
    OS << "\n";
172
16.8k
    return;
173
16.8k
  }
174
12.2k
175
12.2k
  const auto *T = cast<syntax::Tree>(N);
176
12.2k
  OS << T->getKind();
177
12.2k
  dumpExtraInfo(N);
178
12.2k
  OS << "\n";
179
12.2k
180
38.5k
  for (const auto *It = T->getFirstChild(); It; 
It = It->getNextSibling()26.3k
) {
181
47.9k
    for (bool Filled : IndentMask) {
182
47.9k
      if (Filled)
183
23.7k
        OS << "| ";
184
24.1k
      else
185
24.1k
        OS << "  ";
186
47.9k
    }
187
26.3k
    if (!It->getNextSibling()) {
188
12.2k
      OS << "`-";
189
12.2k
      IndentMask.push_back(false);
190
14.1k
    } else {
191
14.1k
      OS << "|-";
192
14.1k
      IndentMask.push_back(true);
193
14.1k
    }
194
26.3k
    dumpNode(OS, It, SM, IndentMask);
195
26.3k
    IndentMask.pop_back();
196
26.3k
  }
197
12.2k
}
198
} // namespace
199
200
2.70k
std::string syntax::Node::dump(const SourceManager &SM) const {
201
2.70k
  std::string Str;
202
2.70k
  llvm::raw_string_ostream OS(Str);
203
2.70k
  dumpNode(OS, this, SM, /*IndentMask=*/{});
204
2.70k
  return std::move(OS.str());
205
2.70k
}
206
207
0
std::string syntax::Node::dumpTokens(const SourceManager &SM) const {
208
0
  std::string Storage;
209
0
  llvm::raw_string_ostream OS(Storage);
210
0
  traverse(this, [&](const syntax::Node *N) {
211
0
    if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
212
0
      dumpLeaf(OS, L, SM);
213
0
      OS << " ";
214
0
    }
215
0
  });
216
0
  return OS.str();
217
0
}
218
219
61.0k
void syntax::Node::assertInvariants() const {
220
61.0k
#ifndef NDEBUG
221
61.0k
  if (isDetached())
222
61.0k
    assert(getParent() == nullptr);
223
61.0k
  else
224
61.0k
    assert(getParent() != nullptr);
225
61.0k
226
61.0k
  const auto *T = dyn_cast<Tree>(this);
227
61.0k
  if (!T)
228
35.8k
    return;
229
84.4k
  
for (const auto *C = T->getFirstChild(); 25.2k
C;
C = C->getNextSibling()59.2k
) {
230
59.2k
    if (T->isOriginal())
231
59.2k
      assert(C->isOriginal());
232
59.2k
    assert(!C->isDetached());
233
59.2k
    assert(C->getParent() == T);
234
59.2k
  }
235
25.2k
236
25.2k
  const auto *L = dyn_cast<List>(T);
237
25.2k
  if (!L)
238
23.8k
    return;
239
3.84k
  
for (const auto *C = T->getFirstChild(); 1.34k
C;
C = C->getNextSibling()2.49k
) {
240
2.49k
    assert(C->getRole() == NodeRole::ListElement ||
241
2.49k
           C->getRole() == NodeRole::ListDelimiter);
242
2.49k
    if (C->getRole() == NodeRole::ListDelimiter) {
243
703
      assert(isa<Leaf>(C));
244
703
      assert(cast<Leaf>(C)->getToken()->kind() == L->getDelimiterTokenKind());
245
703
    }
246
2.49k
  }
247
1.34k
248
1.34k
#endif
249
1.34k
}
250
251
1.87k
void syntax::Node::assertInvariantsRecursive() const {
252
1.87k
#ifndef NDEBUG
253
60.7k
  traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
254
1.87k
#endif
255
1.87k
}
256
257
29.0k
syntax::Leaf *syntax::Tree::findFirstLeaf() {
258
29.0k
  auto *T = this;
259
42.0k
  while (auto *C = T->getFirstChild()) {
260
42.0k
    if (auto *L = dyn_cast<syntax::Leaf>(C))
261
29.0k
      return L;
262
12.9k
    T = cast<syntax::Tree>(C);
263
12.9k
  }
264
0
  return nullptr;
265
29.0k
}
266
267
29.0k
syntax::Leaf *syntax::Tree::findLastLeaf() {
268
29.0k
  auto *T = this;
269
45.8k
  while (auto *C = T->getFirstChild()) {
270
    // Find the last child.
271
116k
    while (auto *Next = C->getNextSibling())
272
70.4k
      C = Next;
273
45.8k
274
45.8k
    if (auto *L = dyn_cast<syntax::Leaf>(C))
275
29.0k
      return L;
276
16.8k
    T = cast<syntax::Tree>(C);
277
16.8k
  }
278
0
  return nullptr;
279
29.0k
}
280
281
0
syntax::Node *syntax::Tree::findChild(NodeRole R) {
282
0
  for (auto *C = FirstChild; C; C = C->getNextSibling()) {
283
0
    if (C->getRole() == R)
284
0
      return C;
285
0
  }
286
0
  return nullptr;
287
0
}
288
289
26.5k
bool syntax::List::classof(const syntax::Node *N) {
290
26.5k
  switch (N->getKind()) {
291
2.69k
  case syntax::NodeKind::NestedNameSpecifier:
292
2.69k
  case syntax::NodeKind::CallArguments:
293
2.69k
  case syntax::NodeKind::ParameterDeclarationList:
294
2.69k
    return true;
295
23.8k
  default:
296
23.8k
    return false;
297
26.5k
  }
298
26.5k
}
299
300
std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
301
0
syntax::List::getElementsAsNodesAndDelimiters() {
302
0
  if (!getFirstChild())
303
0
    return {};
304
0
305
0
  auto children = std::vector<syntax::List::ElementAndDelimiter<Node>>();
306
0
  syntax::Node *elementWithoutDelimiter = nullptr;
307
0
  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
308
0
    switch (C->getRole()) {
309
0
    case syntax::NodeRole::ListElement: {
310
0
      if (elementWithoutDelimiter) {
311
0
        children.push_back({elementWithoutDelimiter, nullptr});
312
0
      }
313
0
      elementWithoutDelimiter = C;
314
0
      break;
315
0
    }
316
0
    case syntax::NodeRole::ListDelimiter: {
317
0
      children.push_back({elementWithoutDelimiter, cast<syntax::Leaf>(C)});
318
0
      elementWithoutDelimiter = nullptr;
319
0
      break;
320
0
    }
321
0
    default:
322
0
      llvm_unreachable(
323
0
          "A list can have only elements and delimiters as children.");
324
0
    }
325
0
  }
326
0
327
0
  switch (getTerminationKind()) {
328
0
  case syntax::List::TerminationKind::Separated: {
329
0
    children.push_back({elementWithoutDelimiter, nullptr});
330
0
    break;
331
0
  }
332
0
  case syntax::List::TerminationKind::Terminated:
333
0
  case syntax::List::TerminationKind::MaybeTerminated: {
334
0
    if (elementWithoutDelimiter) {
335
0
      children.push_back({elementWithoutDelimiter, nullptr});
336
0
    }
337
0
    break;
338
0
  }
339
0
  }
340
0
341
0
  return children;
342
0
}
343
344
// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
345
// ignoring delimiters
346
0
std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
347
0
  if (!getFirstChild())
348
0
    return {};
349
0
350
0
  auto children = std::vector<syntax::Node *>();
351
0
  syntax::Node *elementWithoutDelimiter = nullptr;
352
0
  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
353
0
    switch (C->getRole()) {
354
0
    case syntax::NodeRole::ListElement: {
355
0
      if (elementWithoutDelimiter) {
356
0
        children.push_back(elementWithoutDelimiter);
357
0
      }
358
0
      elementWithoutDelimiter = C;
359
0
      break;
360
0
    }
361
0
    case syntax::NodeRole::ListDelimiter: {
362
0
      children.push_back(elementWithoutDelimiter);
363
0
      elementWithoutDelimiter = nullptr;
364
0
      break;
365
0
    }
366
0
    default:
367
0
      llvm_unreachable("A list has only elements or delimiters.");
368
0
    }
369
0
  }
370
0
371
0
  switch (getTerminationKind()) {
372
0
  case syntax::List::TerminationKind::Separated: {
373
0
    children.push_back(elementWithoutDelimiter);
374
0
    break;
375
0
  }
376
0
  case syntax::List::TerminationKind::Terminated:
377
0
  case syntax::List::TerminationKind::MaybeTerminated: {
378
0
    if (elementWithoutDelimiter) {
379
0
      children.push_back(elementWithoutDelimiter);
380
0
    }
381
0
    break;
382
0
  }
383
0
  }
384
0
385
0
  return children;
386
0
}
387
388
703
clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const {
389
703
  switch (this->getKind()) {
390
271
  case NodeKind::NestedNameSpecifier:
391
271
    return clang::tok::coloncolon;
392
432
  case NodeKind::CallArguments:
393
432
  case NodeKind::ParameterDeclarationList:
394
432
    return clang::tok::comma;
395
0
  default:
396
0
    llvm_unreachable("This is not a subclass of List, thus "
397
703
                     "getDelimiterTokenKind() cannot be called");
398
703
  }
399
703
}
400
401
0
syntax::List::TerminationKind syntax::List::getTerminationKind() const {
402
0
  switch (this->getKind()) {
403
0
  case NodeKind::NestedNameSpecifier:
404
0
    return TerminationKind::Terminated;
405
0
  case NodeKind::CallArguments:
406
0
  case NodeKind::ParameterDeclarationList:
407
0
    return TerminationKind::Separated;
408
0
  default:
409
0
    llvm_unreachable("This is not a subclass of List, thus "
410
0
                     "getTerminationKind() cannot be called");
411
0
  }
412
0
}
413
414
0
bool syntax::List::canBeEmpty() const {
415
0
  switch (this->getKind()) {
416
0
  case NodeKind::NestedNameSpecifier:
417
0
    return false;
418
0
  case NodeKind::CallArguments:
419
0
    return true;
420
0
  case NodeKind::ParameterDeclarationList:
421
0
    return true;
422
0
  default:
423
0
    llvm_unreachable("This is not a subclass of List, thus canBeEmpty() "
424
0
                     "cannot be called");
425
0
  }
426
0
}