Coverage Report

Created: 2020-02-25 14:32

/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
567
                     llvm::function_ref<void(const syntax::Node *)> Visit) {
21
567
  if (auto *T = dyn_cast<syntax::Tree>(N)) {
22
708
    for (auto *C = T->firstChild(); C; 
C = C->nextSibling()535
)
23
535
      traverse(C, Visit);
24
173
  }
25
567
  Visit(N);
26
567
}
27
static void traverse(syntax::Node *N,
28
3
                     llvm::function_ref<void(syntax::Node *)> Visit) {
29
11
  traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) {
30
11
    Visit(const_cast<syntax::Node *>(N));
31
11
  });
32
3
}
33
} // namespace
34
35
syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
36
                     TokenBuffer Tokens)
37
29
    : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {}
38
39
707
const clang::syntax::TokenBuffer &syntax::Arena::tokenBuffer() const {
40
707
  return Tokens;
41
707
}
42
43
std::pair<FileID, llvm::ArrayRef<syntax::Token>>
44
3
syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
45
3
  auto FID = SourceMgr.createFileID(std::move(Input));
46
3
  auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
47
3
  assert(It.second && "duplicate FileID");
48
3
  return {FID, It.first->second};
49
3
}
50
51
390
syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
52
390
  assert(Tok != nullptr);
53
390
}
54
55
1.00k
bool syntax::Leaf::classof(const Node *N) {
56
1.00k
  return N->kind() == NodeKind::Leaf;
57
1.00k
}
58
59
syntax::Node::Node(NodeKind Kind)
60
    : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
61
      Role(static_cast<unsigned>(NodeRole::Detached)), Original(false),
62
561
      CanModify(false) {}
63
64
1.11k
bool syntax::Node::isDetached() const { return role() == NodeRole::Detached; }
65
66
1.76k
bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
67
68
529
void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
69
529
  assert(Child->Parent == nullptr);
70
529
  assert(Child->NextSibling == nullptr);
71
529
  assert(Child->role() == NodeRole::Detached);
72
529
  assert(Role != NodeRole::Detached);
73
529
74
529
  Child->Parent = this;
75
529
  Child->NextSibling = this->FirstChild;
76
529
  Child->Role = static_cast<unsigned>(Role);
77
529
  this->FirstChild = Child;
78
529
}
79
80
void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
81
3
                                             Node *New) {
82
3
  assert(!BeforeBegin || BeforeBegin->Parent == this);
83
3
84
3
#ifndef NDEBUG
85
4
  for (auto *N = New; N; 
N = N->nextSibling()1
) {
86
1
    assert(N->Parent == nullptr);
87
1
    assert(N->role() != NodeRole::Detached && "Roles must be set");
88
1
    // FIXME: sanity-check the role.
89
1
  }
90
3
#endif
91
3
92
3
  // Detach old nodes.
93
3
  for (auto *N = !BeforeBegin ? 
FirstChild0
: BeforeBegin->nextSibling();
94
6
       N != End;) {
95
3
    auto *Next = N->NextSibling;
96
3
97
3
    N->Role = static_cast<unsigned>(NodeRole::Detached);
98
3
    N->Parent = nullptr;
99
3
    N->NextSibling = nullptr;
100
3
    if (N->Original)
101
11
      
traverse(N, [&](Node *C) 3
{ C->Original = false; });
102
3
103
3
    N = Next;
104
3
  }
105
3
106
3
  // Attach new nodes.
107
3
  if (BeforeBegin)
108
3
    BeforeBegin->NextSibling = New ? 
New1
:
End2
;
109
0
  else
110
0
    FirstChild = New ? New : End;
111
3
112
3
  if (New) {
113
1
    auto *Last = New;
114
2
    for (auto *N = New; N != nullptr; 
N = N->nextSibling()1
) {
115
1
      Last = N;
116
1
      N->Parent = this;
117
1
    }
118
1
    Last->NextSibling = End;
119
1
  }
120
3
121
3
  // Mark the node as modified.
122
13
  for (auto *T = this; T && 
T->Original10
;
T = T->Parent10
)
123
10
    T->Original = false;
124
3
}
125
126
namespace {
127
static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens,
128
351
                       const SourceManager &SM) {
129
351
  assert(!Tokens.empty());
130
351
  bool First = true;
131
351
  for (const auto &T : Tokens) {
132
351
    if (!First)
133
0
      OS << " ";
134
351
    else
135
351
      First = false;
136
351
    // Handle 'eof' separately, calling text() on it produces an empty string.
137
351
    if (T.kind() == tok::eof) {
138
0
      OS << "<eof>";
139
0
      continue;
140
0
    }
141
351
    OS << T.text(SM);
142
351
  }
143
351
}
144
145
static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
146
501
                     const syntax::Arena &A, std::vector<bool> IndentMask) {
147
501
  std::string Marks;
148
501
  if (!N->isOriginal())
149
0
    Marks += "M";
150
501
  if (N->role() == syntax::NodeRole::Detached)
151
25
    Marks += "*"; // FIXME: find a nice way to print other roles.
152
501
  if (!N->canModify())
153
10
    Marks += "I";
154
501
  if (!Marks.empty())
155
35
    OS << Marks << ": ";
156
501
157
501
  if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
158
351
    dumpTokens(OS, *L->token(), A.sourceManager());
159
351
    OS << "\n";
160
351
    return;
161
351
  }
162
150
163
150
  auto *T = llvm::cast<syntax::Tree>(N);
164
150
  OS << T->kind() << "\n";
165
150
166
626
  for (auto It = T->firstChild(); It != nullptr; 
It = It->nextSibling()476
) {
167
1.00k
    for (bool Filled : IndentMask) {
168
1.00k
      if (Filled)
169
347
        OS << "| ";
170
656
      else
171
656
        OS << "  ";
172
1.00k
    }
173
476
    if (!It->nextSibling()) {
174
150
      OS << "`-";
175
150
      IndentMask.push_back(false);
176
326
    } else {
177
326
      OS << "|-";
178
326
      IndentMask.push_back(true);
179
326
    }
180
476
    dumpTree(OS, It, A, IndentMask);
181
476
    IndentMask.pop_back();
182
476
  }
183
150
}
184
} // namespace
185
186
25
std::string syntax::Node::dump(const Arena &A) const {
187
25
  std::string Str;
188
25
  llvm::raw_string_ostream OS(Str);
189
25
  dumpTree(OS, this, A, /*IndentMask=*/{});
190
25
  return std::move(OS.str());
191
25
}
192
193
0
std::string syntax::Node::dumpTokens(const Arena &A) const {
194
0
  std::string Storage;
195
0
  llvm::raw_string_ostream OS(Storage);
196
0
  traverse(this, [&](const syntax::Node *N) {
197
0
    auto *L = llvm::dyn_cast<syntax::Leaf>(N);
198
0
    if (!L)
199
0
      return;
200
0
    ::dumpTokens(OS, *L->token(), A.sourceManager());
201
0
    OS << " ";
202
0
  });
203
0
  return OS.str();
204
0
}
205
206
566
void syntax::Node::assertInvariants() const {
207
566
#ifndef NDEBUG
208
566
  if (isDetached())
209
566
    assert(parent() == nullptr);
210
566
  else
211
566
    assert(parent() != nullptr);
212
566
213
566
  auto *T = dyn_cast<Tree>(this);
214
566
  if (!T)
215
390
    return;
216
720
  
for (auto *C = T->firstChild(); 176
C;
C = C->nextSibling()544
) {
217
544
    if (T->isOriginal())
218
544
      assert(C->isOriginal());
219
544
    assert(!C->isDetached());
220
544
    assert(C->parent() == T);
221
544
  }
222
176
#endif
223
176
}
224
225
29
void syntax::Node::assertInvariantsRecursive() const {
226
29
#ifndef NDEBUG
227
556
  traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
228
29
#endif
229
29
}
230
231
14
syntax::Leaf *syntax::Tree::firstLeaf() {
232
14
  auto *T = this;
233
18
  while (auto *C = T->firstChild()) {
234
18
    if (auto *L = dyn_cast<syntax::Leaf>(C))
235
14
      return L;
236
4
    T = cast<syntax::Tree>(C);
237
4
  }
238
14
  
return nullptr0
;
239
14
}
240
241
14
syntax::Leaf *syntax::Tree::lastLeaf() {
242
14
  auto *T = this;
243
24
  while (auto *C = T->firstChild()) {
244
24
    // Find the last child.
245
78
    while (auto *Next = C->nextSibling())
246
54
      C = Next;
247
24
248
24
    if (auto *L = dyn_cast<syntax::Leaf>(C))
249
14
      return L;
250
10
    T = cast<syntax::Tree>(C);
251
10
  }
252
14
  
return nullptr0
;
253
14
}
254
255
0
syntax::Node *syntax::Tree::findChild(NodeRole R) {
256
0
  for (auto *C = FirstChild; C; C = C->nextSibling()) {
257
0
    if (C->role() == R)
258
0
      return C;
259
0
  }
260
0
  return nullptr;
261
0
}