Coverage Report

Created: 2020-09-15 12:33

/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
        const TokenBuffer &Tokens);
43
44
24.4k
  const SourceManager &getSourceManager() const { return SourceMgr; }
45
0
  const LangOptions &getLangOptions() const { return LangOpts; }
46
47
  const TokenBuffer &getTokenBuffer() const;
48
62.5k
  llvm::BumpPtrAllocator &getAllocator() { return Allocator; }
49
50
private:
51
  /// Add \p Buffer to the underlying source manager, tokenize it and store the
52
  /// resulting tokens. Used exclusively in `FactoryImpl` to materialize tokens
53
  /// that were not written in user code.
54
  std::pair<FileID, ArrayRef<Token>>
55
  lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Buffer);
56
  friend class FactoryImpl;
57
58
private:
59
  SourceManager &SourceMgr;
60
  const LangOptions &LangOpts;
61
  const TokenBuffer &Tokens;
62
  /// IDs and storage for additional tokenized files.
63
  llvm::DenseMap<FileID, std::vector<Token>> ExtraTokens;
64
  /// Keeps all the allocated nodes and their intermediate data structures.
65
  llvm::BumpPtrAllocator Allocator;
66
};
67
68
class Tree;
69
class TreeBuilder;
70
class FactoryImpl;
71
class MutationsImpl;
72
73
enum class NodeKind : uint16_t;
74
enum class NodeRole : uint8_t;
75
76
/// A node in a syntax tree. Each node is either a Leaf (representing tokens) or
77
/// a Tree (representing language constructrs).
78
class Node {
79
public:
80
  /// Newly created nodes are detached from a tree, parent and sibling links are
81
  /// set when the node is added as a child to another one.
82
  Node(NodeKind Kind);
83
84
661k
  NodeKind getKind() const { return static_cast<NodeKind>(Kind); }
85
317k
  NodeRole getRole() const { return static_cast<NodeRole>(Role); }
86
87
  /// Whether the node is detached from a tree, i.e. does not have a parent.
88
  bool isDetached() const;
89
  /// Whether the node was created from the AST backed by the source code
90
  /// rather than added later through mutation APIs or created with factory
91
  /// functions.
92
  /// When this flag is true, all subtrees are also original.
93
  /// This flag is set to false on any modifications to the node or any of its
94
  /// subtrees, even if this simply involves swapping existing subtrees.
95
209k
  bool isOriginal() const { return Original; }
96
  /// If this function return false, the tree cannot be modified because there
97
  /// is no reasonable way to produce the corresponding textual replacements.
98
  /// This can happen when the node crosses macro expansion boundaries.
99
  ///
100
  /// Note that even if the node is not modifiable, its child nodes can be
101
  /// modifiable.
102
29.1k
  bool canModify() const { return CanModify; }
103
104
120k
  const Tree *getParent() const { return Parent; }
105
168
  Tree *getParent() { return Parent; }
106
107
174k
  const Node *getNextSibling() const { return NextSibling; }
108
169k
  Node *getNextSibling() { return NextSibling; }
109
110
  /// Dumps the structure of a subtree. For debugging and testing purposes.
111
  std::string dump(const SourceManager &SM) const;
112
  /// Dumps the tokens forming this subtree.
113
  std::string dumpTokens(const SourceManager &SM) const;
114
115
  /// Asserts invariants on this node of the tree and its immediate children.
116
  /// Will not recurse into the subtree. No-op if NDEBUG is set.
117
  void assertInvariants() const;
118
  /// Runs checkInvariants on all nodes in the subtree. No-op if NDEBUG is set.
119
  void assertInvariantsRecursive() const;
120
121
private:
122
  // Tree is allowed to change the Parent link and Role.
123
  friend class Tree;
124
  // TreeBuilder is allowed to set the Original and CanModify flags.
125
  friend class TreeBuilder;
126
  // MutationsImpl sets roles and CanModify flag.
127
  friend class MutationsImpl;
128
  // FactoryImpl sets CanModify flag.
129
  friend class FactoryImpl;
130
131
  void setRole(NodeRole NR);
132
133
  Tree *Parent;
134
  Node *NextSibling;
135
  unsigned Kind : 16;
136
  unsigned Role : 8;
137
  unsigned Original : 1;
138
  unsigned CanModify : 1;
139
};
140
141
/// A leaf node points to a single token inside the expanded token stream.
142
class Leaf final : public Node {
143
public:
144
  Leaf(const Token *T);
145
  static bool classof(const Node *N);
146
147
108k
  const Token *getToken() const { return Tok; }
148
149
private:
150
  const Token *Tok;
151
};
152
153
/// A node that has children and represents a syntactic language construct.
154
class Tree : public Node {
155
public:
156
  using Node::Node;
157
  static bool classof(const Node *N);
158
159
139k
  Node *getFirstChild() { return FirstChild; }
160
64.2k
  const Node *getFirstChild() const { return FirstChild; }
161
162
  Leaf *findFirstLeaf();
163
0
  const Leaf *findFirstLeaf() const {
164
0
    return const_cast<Tree *>(this)->findFirstLeaf();
165
0
  }
166
167
  Leaf *findLastLeaf();
168
0
  const Leaf *findLastLeaf() const {
169
0
    return const_cast<Tree *>(this)->findLastLeaf();
170
0
  }
171
172
protected:
173
  /// Find the first node with a corresponding role.
174
  Node *findChild(NodeRole R);
175
176
private:
177
  /// Prepend \p Child to the list of children and and sets the parent pointer.
178
  /// A very low-level operation that does not check any invariants, only used
179
  /// by TreeBuilder and FactoryImpl.
180
  /// EXPECTS: Role != Detached.
181
  void prependChildLowLevel(Node *Child, NodeRole Role);
182
  /// Like the previous overload, but does not set role for \p Child.
183
  /// EXPECTS: Child->Role != Detached
184
  void prependChildLowLevel(Node *Child);
185
  friend class TreeBuilder;
186
  friend class FactoryImpl;
187
188
  /// Replace a range of children [BeforeBegin->NextSibling, End) with a list of
189
  /// new nodes starting at \p New.
190
  /// Only used by MutationsImpl to implement higher-level mutation operations.
191
  /// (!) \p New can be null to model removal of the child range.
192
  void replaceChildRangeLowLevel(Node *BeforeBegin, Node *End, Node *New);
193
  friend class MutationsImpl;
194
195
  Node *FirstChild = nullptr;
196
};
197
198
/// A list of Elements separated or terminated by a fixed token.
199
///
200
/// This type models the following grammar construct:
201
/// delimited-list(element, delimiter, termination, canBeEmpty)
202
class List : public Tree {
203
public:
204
  template <typename Element> struct ElementAndDelimiter {
205
    Element *element;
206
    Leaf *delimiter;
207
  };
208
209
  enum class TerminationKind {
210
    Terminated,
211
    MaybeTerminated,
212
    Separated,
213
  };
214
215
  using Tree::Tree;
216
  static bool classof(const Node *N);
217
  /// Returns the elements and corresponding delimiters. Missing elements
218
  /// and delimiters are represented as null pointers.
219
  ///
220
  /// For example, in a separated list:
221
  /// "a, b, c" <=> [("a", ","), ("b", ","), ("c", null)]
222
  /// "a, , c" <=> [("a", ","), (null, ","), ("c", ",)]
223
  /// "a, b," <=> [("a", ","), ("b", ","), (null, null)]
224
  ///
225
  /// In a terminated or maybe-terminated list:
226
  /// "a, b," <=> [("a", ","), ("b", ",")]
227
  std::vector<ElementAndDelimiter<Node>> getElementsAsNodesAndDelimiters();
228
229
  /// Returns the elements of the list. Missing elements are represented
230
  /// as null pointers in the same way as in the return value of
231
  /// `getElementsAsNodesAndDelimiters()`.
232
  std::vector<Node *> getElementsAsNodes();
233
234
  // These can't be implemented with the information we have!
235
236
  /// Returns the appropriate delimiter for this list.
237
  ///
238
  /// Useful for discovering the correct delimiter to use when adding
239
  /// elements to empty or one-element lists.
240
  clang::tok::TokenKind getDelimiterTokenKind() const;
241
242
  TerminationKind getTerminationKind() const;
243
244
  /// Whether this list can be empty in syntactically and semantically correct
245
  /// code.
246
  ///
247
  /// This list may be empty when the source code has errors even if
248
  /// canBeEmpty() returns false.
249
  bool canBeEmpty() const;
250
};
251
252
} // namespace syntax
253
} // namespace clang
254
255
#endif