Coverage Report

Created: 2020-03-31 06:27

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Tooling/Syntax/Tree.h
Line
Count
Source (jump to first uncovered line)
1
//===- Tree.h - structure of the syntax tree ------------------*- 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
// Defines the basic structure of the syntax tree. There are two kinds of nodes:
9
//   - leaf nodes correspond to a token in the expanded token stream,
10
//   - tree nodes correspond to language grammar constructs.
11
//
12
// The tree is initially built from an AST. Each node of a newly built tree
13
// covers a continous subrange of expanded tokens (i.e. tokens after
14
// preprocessing), the specific tokens coverered are stored in the leaf nodes of
15
// a tree. A post-order traversal of a tree will visit leaf nodes in an order
16
// corresponding the original order of expanded tokens.
17
//
18
// This is still work in progress and highly experimental, we leave room for
19
// ourselves to completely change the design and/or implementation.
20
//===----------------------------------------------------------------------===//
21
#ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_CASCADE_H
22
#define LLVM_CLANG_TOOLING_SYNTAX_TREE_CASCADE_H
23
24
#include "clang/Basic/LangOptions.h"
25
#include "clang/Basic/SourceLocation.h"
26
#include "clang/Basic/SourceManager.h"
27
#include "clang/Basic/TokenKinds.h"
28
#include "clang/Tooling/Syntax/Tokens.h"
29
#include "llvm/ADT/ArrayRef.h"
30
#include "llvm/ADT/DenseMap.h"
31
#include "llvm/Support/Allocator.h"
32
#include <cstdint>
33
34
namespace clang {
35
namespace syntax {
36
37
/// A memory arena for syntax trees. Also tracks the underlying token buffers,
38
/// source manager, etc.
39
class Arena {
40
public:
41
  Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
42
        TokenBuffer Tokens);
43
44
2.32k
  const SourceManager &sourceManager() const { return SourceMgr; }
45
0
  const LangOptions &langOptions() const { return LangOpts; }
46
47
  const TokenBuffer &tokenBuffer() const;
48
2.36k
  llvm::BumpPtrAllocator &allocator() { return Allocator; }
49
50
  /// Add \p Buffer to the underlying source manager, tokenize it and store the
51
  /// resulting tokens. Useful when there is a need to materialize tokens that
52
  /// were not written in user code.
53
  std::pair<FileID, llvm::ArrayRef<syntax::Token>>
54
  lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Buffer);
55
56
private:
57
  SourceManager &SourceMgr;
58
  const LangOptions &LangOpts;
59
  TokenBuffer Tokens;
60
  /// IDs and storage for additional tokenized files.
61
  llvm::DenseMap<FileID, std::vector<syntax::Token>> ExtraTokens;
62
  /// Keeps all the allocated nodes and their intermediate data structures.
63
  llvm::BumpPtrAllocator Allocator;
64
};
65
66
class Tree;
67
class TreeBuilder;
68
class FactoryImpl;
69
class MutationsImpl;
70
71
enum class NodeKind : uint16_t;
72
enum class NodeRole : uint8_t;
73
74
/// A node in a syntax tree. Each node is either a Leaf (representing tokens) or
75
/// a Tree (representing language constructrs).
76
class Node {
77
public:
78
  /// Newly created nodes are detached from a tree, parent and sibling links are
79
  /// set when the node is added as a child to another one.
80
  Node(NodeKind Kind);
81
82
12.2k
  NodeKind kind() const { return static_cast<NodeKind>(Kind); }
83
12.2k
  NodeRole role() const { return static_cast<NodeRole>(Role); }
84
85
  /// Whether the node is detached from a tree, i.e. does not have a parent.
86
  bool isDetached() const;
87
  /// Whether the node was created from the AST backed by the source code
88
  /// rather than added later through mutation APIs or created with factory
89
  /// functions.
90
  /// When this flag is true, all subtrees are also original.
91
  /// This flag is set to false on any modifications to the node or any of its
92
  /// subtrees, even if this simply involves swapping existing subtrees.
93
6.94k
  bool isOriginal() const { return Original; }
94
  /// If this function return false, the tree cannot be modified because there
95
  /// is no reasonable way to produce the corresponding textual replacements.
96
  /// This can happen when the node crosses macro expansion boundaries.
97
  ///
98
  /// Note that even if the node is not modifiable, its child nodes can be
99
  /// modifiable.
100
2.30k
  bool canModify() const { return CanModify; }
101
102
4.66k
  const Tree *parent() const { return Parent; }
103
12
  Tree *parent() { return Parent; }
104
105
9.07k
  const Node *nextSibling() const { return NextSibling; }
106
127
  Node *nextSibling() { return NextSibling; }
107
108
  /// Dumps the structure of a subtree. For debugging and testing purposes.
109
  std::string dump(const Arena &A) const;
110
  /// Dumps the tokens forming this subtree.
111
  std::string dumpTokens(const Arena &A) const;
112
113
  /// Asserts invariants on this node of the tree and its immediate children.
114
  /// Will not recurse into the subtree. No-op if NDEBUG is set.
115
  void assertInvariants() const;
116
  /// Runs checkInvariants on all nodes in the subtree. No-op if NDEBUG is set.
117
  void assertInvariantsRecursive() const;
118
119
private:
120
  // Tree is allowed to change the Parent link and Role.
121
  friend class Tree;
122
  // TreeBuilder is allowed to set the Original and CanModify flags.
123
  friend class TreeBuilder;
124
  // MutationsImpl sets roles and CanModify flag.
125
  friend class MutationsImpl;
126
  // FactoryImpl sets CanModify flag.
127
  friend class FactoryImpl;
128
129
  void setRole(NodeRole NR);
130
131
  Tree *Parent;
132
  Node *NextSibling;
133
  unsigned Kind : 16;
134
  unsigned Role : 8;
135
  unsigned Original : 1;
136
  unsigned CanModify : 1;
137
};
138
139
/// A leaf node points to a single token inside the expanded token stream.
140
class Leaf final : public Node {
141
public:
142
  Leaf(const syntax::Token *T);
143
  static bool classof(const Node *N);
144
145
1.60k
  const syntax::Token *token() const { return Tok; }
146
147
private:
148
  const syntax::Token *Tok;
149
};
150
151
/// A node that has children and represents a syntactic language construct.
152
class Tree : public Node {
153
public:
154
  using Node::Node;
155
  static bool classof(const Node *N);
156
157
898
  Node *firstChild() { return FirstChild; }
158
2.46k
  const Node *firstChild() const { return FirstChild; }
159
160
  Leaf *firstLeaf();
161
0
  const Leaf *firstLeaf() const {
162
0
    return const_cast<Tree *>(this)->firstLeaf();
163
0
  }
164
165
  Leaf *lastLeaf();
166
0
  const Leaf *lastLeaf() const { return const_cast<Tree *>(this)->lastLeaf(); }
167
168
protected:
169
  /// Find the first node with a corresponding role.
170
  syntax::Node *findChild(NodeRole R);
171
172
private:
173
  /// Prepend \p Child to the list of children and and sets the parent pointer.
174
  /// A very low-level operation that does not check any invariants, only used
175
  /// by TreeBuilder and FactoryImpl.
176
  /// EXPECTS: Role != Detached.
177
  void prependChildLowLevel(Node *Child, NodeRole Role);
178
  /// Like the previous overload, but does not set role for \p Child.
179
  /// EXPECTS: Child->Role != Detached
180
  void prependChildLowLevel(Node *Child);
181
  friend class TreeBuilder;
182
  friend class FactoryImpl;
183
184
  /// Replace a range of children [BeforeBegin->NextSibling, End) with a list of
185
  /// new nodes starting at \p New.
186
  /// Only used by MutationsImpl to implement higher-level mutation operations.
187
  /// (!) \p New can be null to model removal of the child range.
188
  void replaceChildRangeLowLevel(Node *BeforeBegin, Node *End, Node *New);
189
  friend class MutationsImpl;
190
191
  Node *FirstChild = nullptr;
192
};
193
194
} // namespace syntax
195
} // namespace clang
196
197
#endif