Coverage Report

Created: 2020-02-15 09:57

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Tooling/Syntax/BuildTree.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- BuildTree.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/BuildTree.h"
9
#include "clang/AST/Decl.h"
10
#include "clang/AST/DeclBase.h"
11
#include "clang/AST/RecursiveASTVisitor.h"
12
#include "clang/AST/Stmt.h"
13
#include "clang/Basic/LLVM.h"
14
#include "clang/Basic/SourceLocation.h"
15
#include "clang/Basic/SourceManager.h"
16
#include "clang/Basic/TokenKinds.h"
17
#include "clang/Lex/Lexer.h"
18
#include "clang/Tooling/Syntax/Nodes.h"
19
#include "clang/Tooling/Syntax/Tokens.h"
20
#include "clang/Tooling/Syntax/Tree.h"
21
#include "llvm/ADT/ArrayRef.h"
22
#include "llvm/ADT/STLExtras.h"
23
#include "llvm/ADT/SmallVector.h"
24
#include "llvm/Support/Allocator.h"
25
#include "llvm/Support/Casting.h"
26
#include "llvm/Support/Compiler.h"
27
#include "llvm/Support/FormatVariadic.h"
28
#include "llvm/Support/MemoryBuffer.h"
29
#include "llvm/Support/raw_ostream.h"
30
#include <map>
31
32
using namespace clang;
33
34
LLVM_ATTRIBUTE_UNUSED
35
24
static bool isImplicitExpr(clang::Expr *E) { return E->IgnoreImplicit() != E; }
36
37
/// A helper class for constructing the syntax tree while traversing a clang
38
/// AST.
39
///
40
/// At each point of the traversal we maintain a list of pending nodes.
41
/// Initially all tokens are added as pending nodes. When processing a clang AST
42
/// node, the clients need to:
43
///   - create a corresponding syntax node,
44
///   - assign roles to all pending child nodes with 'markChild' and
45
///     'markChildToken',
46
///   - replace the child nodes with the new syntax node in the pending list
47
///     with 'foldNode'.
48
///
49
/// Note that all children are expected to be processed when building a node.
50
///
51
/// Call finalize() to finish building the tree and consume the root node.
52
class syntax::TreeBuilder {
53
public:
54
29
  TreeBuilder(syntax::Arena &Arena) : Arena(Arena), Pending(Arena) {
55
29
    for (const auto &T : Arena.tokenBuffer().expandedTokens())
56
416
      LocationToToken.insert({T.location().getRawEncoding(), &T});
57
29
  }
58
59
140
  llvm::BumpPtrAllocator &allocator() { return Arena.allocator(); }
60
61
  /// Populate children for \p New node, assuming it covers tokens from \p
62
  /// Range.
63
  void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New);
64
65
  /// Must be called with the range of each `DeclaratorDecl`. Ensures the
66
  /// corresponding declarator nodes are covered by `SimpleDeclaration`.
67
  void noticeDeclaratorRange(llvm::ArrayRef<syntax::Token> Range);
68
69
  /// Notifies that we should not consume trailing semicolon when computing
70
  /// token range of \p D.
71
  void noticeDeclaratorWithoutSemicolon(Decl *D);
72
73
  /// Mark the \p Child node with a corresponding \p Role. All marked children
74
  /// should be consumed by foldNode.
75
  /// (!) when called on expressions (clang::Expr is derived from clang::Stmt),
76
  ///     wraps expressions into expression statement.
77
  void markStmtChild(Stmt *Child, NodeRole Role);
78
  /// Should be called for expressions in non-statement position to avoid
79
  /// wrapping into expression statement.
80
  void markExprChild(Expr *Child, NodeRole Role);
81
82
  /// Set role for a token starting at \p Loc.
83
  void markChildToken(SourceLocation Loc, NodeRole R);
84
85
  /// Finish building the tree and consume the root node.
86
29
  syntax::TranslationUnit *finalize() && {
87
29
    auto Tokens = Arena.tokenBuffer().expandedTokens();
88
29
    assert(!Tokens.empty());
89
29
    assert(Tokens.back().kind() == tok::eof);
90
29
91
29
    // Build the root of the tree, consuming all the children.
92
29
    Pending.foldChildren(Arena, Tokens.drop_back(),
93
29
                         new (Arena.allocator()) syntax::TranslationUnit);
94
29
95
29
    auto *TU = cast<syntax::TranslationUnit>(std::move(Pending).finalize());
96
29
    TU->assertInvariantsRecursive();
97
29
    return TU;
98
29
  }
99
100
  /// getRange() finds the syntax tokens corresponding to the passed source
101
  /// locations.
102
  /// \p First is the start position of the first token and \p Last is the start
103
  /// position of the last token.
104
  llvm::ArrayRef<syntax::Token> getRange(SourceLocation First,
105
194
                                         SourceLocation Last) const {
106
194
    assert(First.isValid());
107
194
    assert(Last.isValid());
108
194
    assert(First == Last ||
109
194
           Arena.sourceManager().isBeforeInTranslationUnit(First, Last));
110
194
    return llvm::makeArrayRef(findToken(First), std::next(findToken(Last)));
111
194
  }
112
59
  llvm::ArrayRef<syntax::Token> getRange(const Decl *D) const {
113
59
    auto Tokens = getRange(D->getBeginLoc(), D->getEndLoc());
114
59
    if (llvm::isa<NamespaceDecl>(D))
115
7
      return Tokens;
116
52
    if (DeclsWithoutSemicolons.count(D))
117
6
      return Tokens;
118
46
    // FIXME: do not consume trailing semicolon on function definitions.
119
46
    // Most declarations own a semicolon in syntax trees, but not in clang AST.
120
46
    return withTrailingSemicolon(Tokens);
121
46
  }
122
37
  llvm::ArrayRef<syntax::Token> getExprRange(const Expr *E) const {
123
37
    return getRange(E->getBeginLoc(), E->getEndLoc());
124
37
  }
125
  /// Find the adjusted range for the statement, consuming the trailing
126
  /// semicolon when needed.
127
98
  llvm::ArrayRef<syntax::Token> getStmtRange(const Stmt *S) const {
128
98
    auto Tokens = getRange(S->getBeginLoc(), S->getEndLoc());
129
98
    if (isa<CompoundStmt>(S))
130
42
      return Tokens;
131
56
132
56
    // Some statements miss a trailing semicolon, e.g. 'return', 'continue' and
133
56
    // all statements that end with those. Consume this semicolon here.
134
56
    if (Tokens.back().kind() == tok::semi)
135
22
      return Tokens;
136
34
    return withTrailingSemicolon(Tokens);
137
34
  }
138
139
private:
140
  llvm::ArrayRef<syntax::Token>
141
80
  withTrailingSemicolon(llvm::ArrayRef<syntax::Token> Tokens) const {
142
80
    assert(!Tokens.empty());
143
80
    assert(Tokens.back().kind() != tok::eof);
144
80
    // (!) we never consume 'eof', so looking at the next token is ok.
145
80
    if (Tokens.back().kind() != tok::semi && 
Tokens.end()->kind() == tok::semi79
)
146
40
      return llvm::makeArrayRef(Tokens.begin(), Tokens.end() + 1);
147
40
    return Tokens;
148
40
  }
149
150
  /// Finds a token starting at \p L. The token must exist.
151
  const syntax::Token *findToken(SourceLocation L) const;
152
153
  /// A collection of trees covering the input tokens.
154
  /// When created, each tree corresponds to a single token in the file.
155
  /// Clients call 'foldChildren' to attach one or more subtrees to a parent
156
  /// node and update the list of trees accordingly.
157
  ///
158
  /// Ensures that added nodes properly nest and cover the whole token stream.
159
  struct Forest {
160
29
    Forest(syntax::Arena &A) {
161
29
      assert(!A.tokenBuffer().expandedTokens().empty());
162
29
      assert(A.tokenBuffer().expandedTokens().back().kind() == tok::eof);
163
29
      // Create all leaf nodes.
164
29
      // Note that we do not have 'eof' in the tree.
165
387
      for (auto &T : A.tokenBuffer().expandedTokens().drop_back()) {
166
387
        auto *L = new (A.allocator()) syntax::Leaf(&T);
167
387
        L->Original = true;
168
387
        L->CanModify = A.tokenBuffer().spelledForExpanded(T).hasValue();
169
387
        Trees.insert(Trees.end(), {&T, NodeAndRole{L}});
170
387
      }
171
29
    }
172
173
29
    ~Forest() { assert(DelayedFolds.empty()); }
174
175
    void assignRole(llvm::ArrayRef<syntax::Token> Range,
176
136
                    syntax::NodeRole Role) {
177
136
      assert(!Range.empty());
178
136
      auto It = Trees.lower_bound(Range.begin());
179
136
      assert(It != Trees.end() && "no node found");
180
136
      assert(It->first == Range.begin() && "no child with the specified range");
181
136
      assert((std::next(It) == Trees.end() ||
182
136
              std::next(It)->first == Range.end()) &&
183
136
             "no child with the specified range");
184
136
      It->second.Role = Role;
185
136
    }
186
187
    /// Add \p Node to the forest and attach child nodes based on \p Tokens.
188
    void foldChildren(const syntax::Arena &A,
189
                      llvm::ArrayRef<syntax::Token> Tokens,
190
137
                      syntax::Tree *Node) {
191
137
      // Execute delayed folds inside `Tokens`.
192
137
      auto BeginExecuted = DelayedFolds.lower_bound(Tokens.begin());
193
137
      auto It = BeginExecuted;
194
169
      for (; It != DelayedFolds.end() && 
It->second.End <= Tokens.end()32
;
++It32
)
195
32
        foldChildrenEager(A, llvm::makeArrayRef(It->first, It->second.End),
196
32
                          It->second.Node);
197
137
      DelayedFolds.erase(BeginExecuted, It);
198
137
199
137
      // Attach children to `Node`.
200
137
      foldChildrenEager(A, Tokens, Node);
201
137
    }
202
203
    /// Schedule a call to `foldChildren` that will only be executed when
204
    /// containing node is folded. The range of delayed nodes can be extended by
205
    /// calling `extendDelayedFold`. Only one delayed node for each starting
206
    /// token is allowed.
207
    void foldChildrenDelayed(llvm::ArrayRef<syntax::Token> Tokens,
208
32
                             syntax::Tree *Node) {
209
32
      assert(!Tokens.empty());
210
32
      bool Inserted =
211
32
          DelayedFolds.insert({Tokens.begin(), DelayedFold{Tokens.end(), Node}})
212
32
              .second;
213
32
      (void)Inserted;
214
32
      assert(Inserted && "Multiple delayed folds start at the same token");
215
32
    }
216
217
    /// If there a delayed fold, starting at `ExtendedRange.begin()`, extends
218
    /// its endpoint to `ExtendedRange.end()` and returns true.
219
    /// Otherwise, returns false.
220
36
    bool extendDelayedFold(llvm::ArrayRef<syntax::Token> ExtendedRange) {
221
36
      assert(!ExtendedRange.empty());
222
36
      auto It = DelayedFolds.find(ExtendedRange.data());
223
36
      if (It == DelayedFolds.end())
224
32
        return false;
225
4
      assert(It->second.End <= ExtendedRange.end());
226
4
      It->second.End = ExtendedRange.end();
227
4
      return true;
228
4
    }
229
230
    // EXPECTS: all tokens were consumed and are owned by a single root node.
231
29
    syntax::Node *finalize() && {
232
29
      assert(Trees.size() == 1);
233
29
      auto *Root = Trees.begin()->second.Node;
234
29
      Trees = {};
235
29
      return Root;
236
29
    }
237
238
0
    std::string str(const syntax::Arena &A) const {
239
0
      std::string R;
240
0
      for (auto It = Trees.begin(); It != Trees.end(); ++It) {
241
0
        unsigned CoveredTokens =
242
0
            It != Trees.end()
243
0
                ? (std::next(It)->first - It->first)
244
0
                : A.tokenBuffer().expandedTokens().end() - It->first;
245
0
246
0
        R += std::string(llvm::formatv(
247
0
            "- '{0}' covers '{1}'+{2} tokens\n", It->second.Node->kind(),
248
0
            It->first->text(A.sourceManager()), CoveredTokens));
249
0
        R += It->second.Node->dump(A);
250
0
      }
251
0
      return R;
252
0
    }
253
254
  private:
255
    /// Implementation detail of `foldChildren`, does acutal folding ignoring
256
    /// delayed folds.
257
    void foldChildrenEager(const syntax::Arena &A,
258
                           llvm::ArrayRef<syntax::Token> Tokens,
259
169
                           syntax::Tree *Node) {
260
169
      assert(Node->firstChild() == nullptr && "node already has children");
261
169
262
169
      auto *FirstToken = Tokens.begin();
263
169
      auto BeginChildren = Trees.lower_bound(FirstToken);
264
169
      assert((BeginChildren == Trees.end() ||
265
169
              BeginChildren->first == FirstToken) &&
266
169
             "fold crosses boundaries of existing subtrees");
267
169
      auto EndChildren = Trees.lower_bound(Tokens.end());
268
169
      assert(
269
169
          (EndChildren == Trees.end() || EndChildren->first == Tokens.end()) &&
270
169
          "fold crosses boundaries of existing subtrees");
271
169
272
169
      // (!) we need to go in reverse order, because we can only prepend.
273
696
      for (auto It = EndChildren; It != BeginChildren; 
--It527
)
274
527
        Node->prependChildLowLevel(std::prev(It)->second.Node,
275
527
                                   std::prev(It)->second.Role);
276
169
277
169
      // Mark that this node came from the AST and is backed by the source code.
278
169
      Node->Original = true;
279
169
      Node->CanModify = A.tokenBuffer().spelledForExpanded(Tokens).hasValue();
280
169
281
169
      Trees.erase(BeginChildren, EndChildren);
282
169
      Trees.insert({FirstToken, NodeAndRole(Node)});
283
169
    }
284
    /// A with a role that should be assigned to it when adding to a parent.
285
    struct NodeAndRole {
286
      explicit NodeAndRole(syntax::Node *Node)
287
556
          : Node(Node), Role(NodeRole::Unknown) {}
288
289
      syntax::Node *Node;
290
      NodeRole Role;
291
    };
292
293
    /// Maps from the start token to a subtree starting at that token.
294
    /// Keys in the map are pointers into the array of expanded tokens, so
295
    /// pointer order corresponds to the order of preprocessor tokens.
296
    /// FIXME: storing the end tokens is redundant.
297
    /// FIXME: the key of a map is redundant, it is also stored in NodeForRange.
298
    std::map<const syntax::Token *, NodeAndRole> Trees;
299
300
    /// See documentation of `foldChildrenDelayed` for details.
301
    struct DelayedFold {
302
      const syntax::Token *End = nullptr;
303
      syntax::Tree *Node = nullptr;
304
    };
305
    std::map<const syntax::Token *, DelayedFold> DelayedFolds;
306
  };
307
308
  /// For debugging purposes.
309
0
  std::string str() { return Pending.str(Arena); }
310
311
  syntax::Arena &Arena;
312
  /// To quickly find tokens by their start location.
313
  llvm::DenseMap</*SourceLocation*/ unsigned, const syntax::Token *>
314
      LocationToToken;
315
  Forest Pending;
316
  llvm::DenseSet<Decl *> DeclsWithoutSemicolons;
317
};
318
319
namespace {
320
class BuildTreeVisitor : public RecursiveASTVisitor<BuildTreeVisitor> {
321
public:
322
  explicit BuildTreeVisitor(ASTContext &Ctx, syntax::TreeBuilder &Builder)
323
29
      : Builder(Builder), LangOpts(Ctx.getLangOpts()) {}
324
325
293
  bool shouldTraversePostOrder() const { return true; }
326
327
32
  bool WalkUpFromDeclaratorDecl(DeclaratorDecl *D) {
328
32
    // Ensure declarators are covered by SimpleDeclaration.
329
32
    Builder.noticeDeclaratorRange(Builder.getRange(D));
330
32
    // FIXME: build nodes for the declarator too.
331
32
    return true;
332
32
  }
333
4
  bool WalkUpFromTypedefNameDecl(TypedefNameDecl *D) {
334
4
    // Also a declarator.
335
4
    Builder.noticeDeclaratorRange(Builder.getRange(D));
336
4
    // FIXME: build nodes for the declarator too.
337
4
    return true;
338
4
  }
339
340
2
  bool VisitDecl(Decl *D) {
341
2
    assert(!D->isImplicit());
342
2
    Builder.foldNode(Builder.getRange(D),
343
2
                     new (allocator()) syntax::UnknownDeclaration());
344
2
    return true;
345
2
  }
346
347
6
  bool WalkUpFromTagDecl(TagDecl *C) {
348
6
    // FIXME: build the ClassSpecifier node.
349
6
    if (C->isFreeStanding()) {
350
3
      // Class is a declaration specifier and needs a spanning declaration node.
351
3
      Builder.foldNode(Builder.getRange(C),
352
3
                       new (allocator()) syntax::SimpleDeclaration);
353
3
      return true;
354
3
    }
355
3
    return true;
356
3
  }
357
358
29
  bool WalkUpFromTranslationUnitDecl(TranslationUnitDecl *TU) {
359
29
    // (!) we do not want to call VisitDecl(), the declaration for translation
360
29
    // unit is built by finalize().
361
29
    return true;
362
29
  }
363
364
30
  bool WalkUpFromCompoundStmt(CompoundStmt *S) {
365
30
    using NodeRole = syntax::NodeRole;
366
30
367
30
    Builder.markChildToken(S->getLBracLoc(), NodeRole::OpenParen);
368
30
    for (auto *Child : S->body())
369
27
      Builder.markStmtChild(Child, NodeRole::CompoundStatement_statement);
370
30
    Builder.markChildToken(S->getRBracLoc(), NodeRole::CloseParen);
371
30
372
30
    Builder.foldNode(Builder.getStmtRange(S),
373
30
                     new (allocator()) syntax::CompoundStatement);
374
30
    return true;
375
30
  }
376
377
  // Some statements are not yet handled by syntax trees.
378
1
  bool WalkUpFromStmt(Stmt *S) {
379
1
    Builder.foldNode(Builder.getStmtRange(S),
380
1
                     new (allocator()) syntax::UnknownStatement);
381
1
    return true;
382
1
  }
383
384
1
  bool TraverseCXXForRangeStmt(CXXForRangeStmt *S) {
385
1
    // We override to traverse range initializer as VarDecl.
386
1
    // RAV traverses it as a statement, we produce invalid node kinds in that
387
1
    // case.
388
1
    // FIXME: should do this in RAV instead?
389
1
    if (S->getInit() && 
!TraverseStmt(S->getInit())0
)
390
0
      return false;
391
1
    if (S->getLoopVariable() && !TraverseDecl(S->getLoopVariable()))
392
0
      return false;
393
1
    if (S->getRangeInit() && !TraverseStmt(S->getRangeInit()))
394
0
      return false;
395
1
    if (S->getBody() && !TraverseStmt(S->getBody()))
396
0
      return false;
397
1
    return true;
398
1
  }
399
400
96
  bool TraverseStmt(Stmt *S) {
401
96
    if (auto *DS = llvm::dyn_cast_or_null<DeclStmt>(S)) {
402
4
      // We want to consume the semicolon, make sure SimpleDeclaration does not.
403
4
      for (auto *D : DS->decls())
404
6
        Builder.noticeDeclaratorWithoutSemicolon(D);
405
92
    } else if (auto *E = llvm::dyn_cast_or_null<Expr>(S)) {
406
24
      // (!) do not recurse into subexpressions.
407
24
      // we do not have syntax trees for expressions yet, so we only want to see
408
24
      // the first top-level expression.
409
24
      return WalkUpFromExpr(E->IgnoreImplicit());
410
24
    }
411
72
    return RecursiveASTVisitor::TraverseStmt(S);
412
72
  }
413
414
  // Some expressions are not yet handled by syntax trees.
415
24
  bool WalkUpFromExpr(Expr *E) {
416
24
    assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");
417
24
    Builder.foldNode(Builder.getExprRange(E),
418
24
                     new (allocator()) syntax::UnknownExpression);
419
24
    return true;
420
24
  }
421
422
7
  bool WalkUpFromNamespaceDecl(NamespaceDecl *S) {
423
7
    auto Tokens = Builder.getRange(S);
424
7
    if (Tokens.front().kind() == tok::coloncolon) {
425
1
      // Handle nested namespace definitions. Those start at '::' token, e.g.
426
1
      // namespace a^::b {}
427
1
      // FIXME: build corresponding nodes for the name of this namespace.
428
1
      return true;
429
1
    }
430
6
    Builder.foldNode(Tokens, new (allocator()) syntax::NamespaceDefinition);
431
6
    return true;
432
6
  }
433
434
  // The code below is very regular, it could even be generated with some
435
  // preprocessor magic. We merely assign roles to the corresponding children
436
  // and fold resulting nodes.
437
4
  bool WalkUpFromDeclStmt(DeclStmt *S) {
438
4
    Builder.foldNode(Builder.getStmtRange(S),
439
4
                     new (allocator()) syntax::DeclarationStatement);
440
4
    return true;
441
4
  }
442
443
4
  bool WalkUpFromNullStmt(NullStmt *S) {
444
4
    Builder.foldNode(Builder.getStmtRange(S),
445
4
                     new (allocator()) syntax::EmptyStatement);
446
4
    return true;
447
4
  }
448
449
1
  bool WalkUpFromSwitchStmt(SwitchStmt *S) {
450
1
    Builder.markChildToken(S->getSwitchLoc(),
451
1
                           syntax::NodeRole::IntroducerKeyword);
452
1
    Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
453
1
    Builder.foldNode(Builder.getStmtRange(S),
454
1
                     new (allocator()) syntax::SwitchStatement);
455
1
    return true;
456
1
  }
457
458
1
  bool WalkUpFromCaseStmt(CaseStmt *S) {
459
1
    Builder.markChildToken(S->getKeywordLoc(),
460
1
                           syntax::NodeRole::IntroducerKeyword);
461
1
    Builder.markExprChild(S->getLHS(), syntax::NodeRole::CaseStatement_value);
462
1
    Builder.markStmtChild(S->getSubStmt(), syntax::NodeRole::BodyStatement);
463
1
    Builder.foldNode(Builder.getStmtRange(S),
464
1
                     new (allocator()) syntax::CaseStatement);
465
1
    return true;
466
1
  }
467
468
1
  bool WalkUpFromDefaultStmt(DefaultStmt *S) {
469
1
    Builder.markChildToken(S->getKeywordLoc(),
470
1
                           syntax::NodeRole::IntroducerKeyword);
471
1
    Builder.markStmtChild(S->getSubStmt(), syntax::NodeRole::BodyStatement);
472
1
    Builder.foldNode(Builder.getStmtRange(S),
473
1
                     new (allocator()) syntax::DefaultStatement);
474
1
    return true;
475
1
  }
476
477
6
  bool WalkUpFromIfStmt(IfStmt *S) {
478
6
    Builder.markChildToken(S->getIfLoc(), syntax::NodeRole::IntroducerKeyword);
479
6
    Builder.markStmtChild(S->getThen(),
480
6
                          syntax::NodeRole::IfStatement_thenStatement);
481
6
    Builder.markChildToken(S->getElseLoc(),
482
6
                           syntax::NodeRole::IfStatement_elseKeyword);
483
6
    Builder.markStmtChild(S->getElse(),
484
6
                          syntax::NodeRole::IfStatement_elseStatement);
485
6
    Builder.foldNode(Builder.getStmtRange(S),
486
6
                     new (allocator()) syntax::IfStatement);
487
6
    return true;
488
6
  }
489
490
1
  bool WalkUpFromForStmt(ForStmt *S) {
491
1
    Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);
492
1
    Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
493
1
    Builder.foldNode(Builder.getStmtRange(S),
494
1
                     new (allocator()) syntax::ForStatement);
495
1
    return true;
496
1
  }
497
498
1
  bool WalkUpFromWhileStmt(WhileStmt *S) {
499
1
    Builder.markChildToken(S->getWhileLoc(),
500
1
                           syntax::NodeRole::IntroducerKeyword);
501
1
    Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
502
1
    Builder.foldNode(Builder.getStmtRange(S),
503
1
                     new (allocator()) syntax::WhileStatement);
504
1
    return true;
505
1
  }
506
507
1
  bool WalkUpFromContinueStmt(ContinueStmt *S) {
508
1
    Builder.markChildToken(S->getContinueLoc(),
509
1
                           syntax::NodeRole::IntroducerKeyword);
510
1
    Builder.foldNode(Builder.getStmtRange(S),
511
1
                     new (allocator()) syntax::ContinueStatement);
512
1
    return true;
513
1
  }
514
515
1
  bool WalkUpFromBreakStmt(BreakStmt *S) {
516
1
    Builder.markChildToken(S->getBreakLoc(),
517
1
                           syntax::NodeRole::IntroducerKeyword);
518
1
    Builder.foldNode(Builder.getStmtRange(S),
519
1
                     new (allocator()) syntax::BreakStatement);
520
1
    return true;
521
1
  }
522
523
2
  bool WalkUpFromReturnStmt(ReturnStmt *S) {
524
2
    Builder.markChildToken(S->getReturnLoc(),
525
2
                           syntax::NodeRole::IntroducerKeyword);
526
2
    Builder.markExprChild(S->getRetValue(),
527
2
                          syntax::NodeRole::ReturnStatement_value);
528
2
    Builder.foldNode(Builder.getStmtRange(S),
529
2
                     new (allocator()) syntax::ReturnStatement);
530
2
    return true;
531
2
  }
532
533
1
  bool WalkUpFromCXXForRangeStmt(CXXForRangeStmt *S) {
534
1
    Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);
535
1
    Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
536
1
    Builder.foldNode(Builder.getStmtRange(S),
537
1
                     new (allocator()) syntax::RangeBasedForStatement);
538
1
    return true;
539
1
  }
540
541
1
  bool WalkUpFromEmptyDecl(EmptyDecl *S) {
542
1
    Builder.foldNode(Builder.getRange(S),
543
1
                     new (allocator()) syntax::EmptyDeclaration);
544
1
    return true;
545
1
  }
546
547
2
  bool WalkUpFromStaticAssertDecl(StaticAssertDecl *S) {
548
2
    Builder.markExprChild(S->getAssertExpr(),
549
2
                          syntax::NodeRole::StaticAssertDeclaration_condition);
550
2
    Builder.markExprChild(S->getMessage(),
551
2
                          syntax::NodeRole::StaticAssertDeclaration_message);
552
2
    Builder.foldNode(Builder.getRange(S),
553
2
                     new (allocator()) syntax::StaticAssertDeclaration);
554
2
    return true;
555
2
  }
556
557
2
  bool WalkUpFromLinkageSpecDecl(LinkageSpecDecl *S) {
558
2
    Builder.foldNode(Builder.getRange(S),
559
2
                     new (allocator()) syntax::LinkageSpecificationDeclaration);
560
2
    return true;
561
2
  }
562
563
1
  bool WalkUpFromNamespaceAliasDecl(NamespaceAliasDecl *S) {
564
1
    Builder.foldNode(Builder.getRange(S),
565
1
                     new (allocator()) syntax::NamespaceAliasDefinition);
566
1
    return true;
567
1
  }
568
569
1
  bool WalkUpFromUsingDirectiveDecl(UsingDirectiveDecl *S) {
570
1
    Builder.foldNode(Builder.getRange(S),
571
1
                     new (allocator()) syntax::UsingNamespaceDirective);
572
1
    return true;
573
1
  }
574
575
1
  bool WalkUpFromUsingDecl(UsingDecl *S) {
576
1
    Builder.foldNode(Builder.getRange(S),
577
1
                     new (allocator()) syntax::UsingDeclaration);
578
1
    return true;
579
1
  }
580
581
1
  bool WalkUpFromUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *S) {
582
1
    Builder.foldNode(Builder.getRange(S),
583
1
                     new (allocator()) syntax::UsingDeclaration);
584
1
    return true;
585
1
  }
586
587
1
  bool WalkUpFromUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *S) {
588
1
    Builder.foldNode(Builder.getRange(S),
589
1
                     new (allocator()) syntax::UsingDeclaration);
590
1
    return true;
591
1
  }
592
593
1
  bool WalkUpFromTypeAliasDecl(TypeAliasDecl *S) {
594
1
    Builder.foldNode(Builder.getRange(S),
595
1
                     new (allocator()) syntax::TypeAliasDeclaration);
596
1
    return true;
597
1
  }
598
599
private:
600
  /// A small helper to save some typing.
601
101
  llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }
602
603
  syntax::TreeBuilder &Builder;
604
  const LangOptions &LangOpts;
605
};
606
} // namespace
607
608
void syntax::TreeBuilder::foldNode(llvm::ArrayRef<syntax::Token> Range,
609
101
                                   syntax::Tree *New) {
610
101
  Pending.foldChildren(Arena, Range, New);
611
101
}
612
613
void syntax::TreeBuilder::noticeDeclaratorRange(
614
36
    llvm::ArrayRef<syntax::Token> Range) {
615
36
  if (Pending.extendDelayedFold(Range))
616
4
    return;
617
32
  Pending.foldChildrenDelayed(Range,
618
32
                              new (allocator()) syntax::SimpleDeclaration);
619
32
}
620
621
6
void syntax::TreeBuilder::noticeDeclaratorWithoutSemicolon(Decl *D) {
622
6
  DeclsWithoutSemicolons.insert(D);
623
6
}
624
625
82
void syntax::TreeBuilder::markChildToken(SourceLocation Loc, NodeRole Role) {
626
82
  if (Loc.isInvalid())
627
2
    return;
628
80
  Pending.assignRole(*findToken(Loc), Role);
629
80
}
630
631
45
void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
632
45
  if (!Child)
633
2
    return;
634
43
635
43
  auto Range = getStmtRange(Child);
636
43
  // This is an expression in a statement position, consume the trailing
637
43
  // semicolon and form an 'ExpressionStatement' node.
638
43
  if (auto *E = dyn_cast<Expr>(Child)) {
639
7
    Pending.assignRole(getExprRange(E),
640
7
                       NodeRole::ExpressionStatement_expression);
641
7
    // (!) 'getRange(Stmt)' ensures this already covers a trailing semicolon.
642
7
    Pending.foldChildren(Arena, Range,
643
7
                         new (allocator()) syntax::ExpressionStatement);
644
7
  }
645
43
  Pending.assignRole(Range, Role);
646
43
}
647
648
7
void syntax::TreeBuilder::markExprChild(Expr *Child, NodeRole Role) {
649
7
  if (!Child)
650
1
    return;
651
6
652
6
  Pending.assignRole(getExprRange(Child), Role);
653
6
}
654
655
468
const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {
656
468
  auto It = LocationToToken.find(L.getRawEncoding());
657
468
  assert(It != LocationToToken.end());
658
468
  return It->second;
659
468
}
660
661
syntax::TranslationUnit *
662
29
syntax::buildSyntaxTree(Arena &A, const TranslationUnitDecl &TU) {
663
29
  TreeBuilder Builder(A);
664
29
  BuildTreeVisitor(TU.getASTContext(), Builder).TraverseAST(TU.getASTContext());
665
29
  return std::move(Builder).finalize();
666
29
}