clang  16.0.0git
Tree.cpp
Go to the documentation of this file.
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 //===----------------------------------------------------------------------===//
11 #include "llvm/ADT/BitVector.h"
12 #include "llvm/Support/raw_ostream.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  llvm::function_ref<void(const syntax::Node *)> Visit) {
21  if (auto *T = dyn_cast<syntax::Tree>(N)) {
22  for (const syntax::Node &C : T->getChildren())
23  traverse(&C, Visit);
24  }
25  Visit(N);
26 }
27 static void traverse(syntax::Node *N,
28  llvm::function_ref<void(syntax::Node *)> Visit) {
29  traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) {
30  Visit(const_cast<syntax::Node *>(N));
31  });
32 }
33 } // namespace
34 
36 
38  : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
39  Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),
40  CanModify(false) {
41  this->setRole(NodeRole::Detached);
42 }
43 
45  return getRole() == NodeRole::Detached;
46 }
47 
48 void syntax::Node::setRole(NodeRole NR) {
49  this->Role = static_cast<unsigned>(NR);
50 }
51 
52 void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) {
53  assert(Child->getRole() == NodeRole::Detached);
54  assert(Role != NodeRole::Detached);
55 
56  Child->setRole(Role);
57  appendChildLowLevel(Child);
58 }
59 
60 void syntax::Tree::appendChildLowLevel(Node *Child) {
61  assert(Child->Parent == nullptr);
62  assert(Child->NextSibling == nullptr);
63  assert(Child->PreviousSibling == nullptr);
64  assert(Child->getRole() != NodeRole::Detached);
65 
66  Child->Parent = this;
67  if (this->LastChild) {
68  Child->PreviousSibling = this->LastChild;
69  this->LastChild->NextSibling = Child;
70  } else
71  this->FirstChild = Child;
72 
73  this->LastChild = Child;
74 }
75 
76 void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
77  assert(Child->getRole() == NodeRole::Detached);
78  assert(Role != NodeRole::Detached);
79 
80  Child->setRole(Role);
81  prependChildLowLevel(Child);
82 }
83 
84 void syntax::Tree::prependChildLowLevel(Node *Child) {
85  assert(Child->Parent == nullptr);
86  assert(Child->NextSibling == nullptr);
87  assert(Child->PreviousSibling == nullptr);
88  assert(Child->getRole() != NodeRole::Detached);
89 
90  Child->Parent = this;
91  if (this->FirstChild) {
92  Child->NextSibling = this->FirstChild;
93  this->FirstChild->PreviousSibling = Child;
94  } else
95  this->LastChild = Child;
96 
97  this->FirstChild = Child;
98 }
99 
100 void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End,
101  Node *New) {
102  assert((!Begin || Begin->Parent == this) &&
103  "`Begin` is not a child of `this`.");
104  assert((!End || End->Parent == this) && "`End` is not a child of `this`.");
105  assert(canModify() && "Cannot modify `this`.");
106 
107 #ifndef NDEBUG
108  for (auto *N = New; N; N = N->NextSibling) {
109  assert(N->Parent == nullptr);
110  assert(N->getRole() != NodeRole::Detached && "Roles must be set");
111  // FIXME: validate the role.
112  }
113 
114  auto Reachable = [](Node *From, Node *N) {
115  if (!N)
116  return true;
117  for (auto *It = From; It; It = It->NextSibling)
118  if (It == N)
119  return true;
120  return false;
121  };
122  assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable.");
123  assert(Reachable(Begin, End) && "`End` is not after `Begin`.");
124 #endif
125 
126  if (!New && Begin == End)
127  return;
128 
129  // Mark modification.
130  for (auto *T = this; T && T->Original; T = T->Parent)
131  T->Original = false;
132 
133  // Save the node before the range to be removed. Later we insert the `New`
134  // range after this node.
135  auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;
136 
137  // Detach old nodes.
138  for (auto *N = Begin; N != End;) {
139  auto *Next = N->NextSibling;
140 
141  N->setRole(NodeRole::Detached);
142  N->Parent = nullptr;
143  N->NextSibling = nullptr;
144  N->PreviousSibling = nullptr;
145  if (N->Original)
146  traverse(N, [](Node *C) { C->Original = false; });
147 
148  N = Next;
149  }
150 
151  // Attach new range.
152  auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
153  auto *&NewLast = End ? End->PreviousSibling : LastChild;
154 
155  if (!New) {
156  NewFirst = End;
157  NewLast = BeforeBegin;
158  return;
159  }
160 
161  New->PreviousSibling = BeforeBegin;
162  NewFirst = New;
163 
164  Node *LastInNew;
165  for (auto *N = New; N != nullptr; N = N->NextSibling) {
166  LastInNew = N;
167  N->Parent = this;
168  }
169  LastInNew->NextSibling = End;
170  NewLast = LastInNew;
171 }
172 
173 namespace {
174 static void dumpNode(raw_ostream &OS, const syntax::Node *N,
175  const syntax::TokenManager &TM, llvm::BitVector IndentMask) {
176  auto DumpExtraInfo = [&OS](const syntax::Node *N) {
178  OS << " " << N->getRole();
179  if (!N->isOriginal())
180  OS << " synthesized";
181  if (!N->canModify())
182  OS << " unmodifiable";
183  };
184 
185  assert(N);
186  if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
187  OS << "'";
188  OS << TM.getText(L->getTokenKey());
189  OS << "'";
190  DumpExtraInfo(N);
191  OS << "\n";
192  return;
193  }
194 
195  const auto *T = cast<syntax::Tree>(N);
196  OS << T->getKind();
197  DumpExtraInfo(N);
198  OS << "\n";
199 
200  for (const syntax::Node &It : T->getChildren()) {
201  for (unsigned Idx = 0; Idx < IndentMask.size(); ++Idx) {
202  if (IndentMask[Idx])
203  OS << "| ";
204  else
205  OS << " ";
206  }
207  if (!It.getNextSibling()) {
208  OS << "`-";
209  IndentMask.push_back(false);
210  } else {
211  OS << "|-";
212  IndentMask.push_back(true);
213  }
214  dumpNode(OS, &It, TM, IndentMask);
215  IndentMask.pop_back();
216  }
217 }
218 } // namespace
219 
221  std::string Str;
222  llvm::raw_string_ostream OS(Str);
223  dumpNode(OS, this, TM, /*IndentMask=*/{});
224  return std::move(OS.str());
225 }
226 
228  std::string Storage;
229  llvm::raw_string_ostream OS(Storage);
230  traverse(this, [&](const syntax::Node *N) {
231  if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
232  OS << TM.getText(L->getTokenKey());
233  OS << " ";
234  }
235  });
236  return Storage;
237 }
238 
240 #ifndef NDEBUG
241  if (isDetached())
242  assert(getParent() == nullptr);
243  else
244  assert(getParent() != nullptr);
245 
246  const auto *T = dyn_cast<Tree>(this);
247  if (!T)
248  return;
249  for (const Node &C : T->getChildren()) {
250  if (T->isOriginal())
251  assert(C.isOriginal());
252  assert(!C.isDetached());
253  assert(C.getParent() == T);
254  const auto *Next = C.getNextSibling();
255  assert(!Next || &C == Next->getPreviousSibling());
256  if (!C.getNextSibling())
257  assert(&C == T->getLastChild() &&
258  "Last child is reachable by advancing from the first child.");
259  }
260 
261  const auto *L = dyn_cast<List>(T);
262  if (!L)
263  return;
264  for (const Node &C : T->getChildren()) {
265  assert(C.getRole() == NodeRole::ListElement ||
266  C.getRole() == NodeRole::ListDelimiter);
267  if (C.getRole() == NodeRole::ListDelimiter) {
268  assert(isa<Leaf>(C));
269  // FIXME: re-enable it when there is way to retrieve token kind in Leaf.
270  // assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind());
271  }
272  }
273 
274 #endif
275 }
276 
278 #ifndef NDEBUG
279  traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
280 #endif
281 }
282 
284  for (const Node &C : getChildren()) {
285  if (const auto *L = dyn_cast<syntax::Leaf>(&C))
286  return L;
287  if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf())
288  return L;
289  }
290  return nullptr;
291 }
292 
294  for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
295  if (const auto *L = dyn_cast<syntax::Leaf>(C))
296  return L;
297  if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf())
298  return L;
299  }
300  return nullptr;
301 }
302 
304  for (const Node &C : getChildren()) {
305  if (C.getRole() == R)
306  return &C;
307  }
308  return nullptr;
309 }
310 
311 std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
313  if (!getFirstChild())
314  return {};
315 
316  std::vector<syntax::List::ElementAndDelimiter<Node>> Children;
317  syntax::Node *ElementWithoutDelimiter = nullptr;
318  for (Node &C : getChildren()) {
319  switch (C.getRole()) {
321  if (ElementWithoutDelimiter) {
322  Children.push_back({ElementWithoutDelimiter, nullptr});
323  }
324  ElementWithoutDelimiter = &C;
325  break;
326  }
328  Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)});
329  ElementWithoutDelimiter = nullptr;
330  break;
331  }
332  default:
333  llvm_unreachable(
334  "A list can have only elements and delimiters as children.");
335  }
336  }
337 
338  switch (getTerminationKind()) {
340  Children.push_back({ElementWithoutDelimiter, nullptr});
341  break;
342  }
345  if (ElementWithoutDelimiter) {
346  Children.push_back({ElementWithoutDelimiter, nullptr});
347  }
348  break;
349  }
350  }
351 
352  return Children;
353 }
354 
355 // Almost the same implementation of `getElementsAsNodesAndDelimiters` but
356 // ignoring delimiters
357 std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
358  if (!getFirstChild())
359  return {};
360 
361  std::vector<syntax::Node *> Children;
362  syntax::Node *ElementWithoutDelimiter = nullptr;
363  for (Node &C : getChildren()) {
364  switch (C.getRole()) {
366  if (ElementWithoutDelimiter) {
367  Children.push_back(ElementWithoutDelimiter);
368  }
369  ElementWithoutDelimiter = &C;
370  break;
371  }
373  Children.push_back(ElementWithoutDelimiter);
374  ElementWithoutDelimiter = nullptr;
375  break;
376  }
377  default:
378  llvm_unreachable("A list has only elements or delimiters.");
379  }
380  }
381 
382  switch (getTerminationKind()) {
384  Children.push_back(ElementWithoutDelimiter);
385  break;
386  }
389  if (ElementWithoutDelimiter) {
390  Children.push_back(ElementWithoutDelimiter);
391  }
392  break;
393  }
394  }
395 
396  return Children;
397 }
398 
400  switch (this->getKind()) {
401  case NodeKind::NestedNameSpecifier:
402  return clang::tok::coloncolon;
403  case NodeKind::CallArguments:
404  case NodeKind::ParameterDeclarationList:
405  case NodeKind::DeclaratorList:
406  return clang::tok::comma;
407  default:
408  llvm_unreachable("This is not a subclass of List, thus "
409  "getDelimiterTokenKind() cannot be called");
410  }
411 }
412 
414  switch (this->getKind()) {
415  case NodeKind::NestedNameSpecifier:
416  return TerminationKind::Terminated;
417  case NodeKind::CallArguments:
418  case NodeKind::ParameterDeclarationList:
419  case NodeKind::DeclaratorList:
420  return TerminationKind::Separated;
421  default:
422  llvm_unreachable("This is not a subclass of List, thus "
423  "getTerminationKind() cannot be called");
424  }
425 }
426 
428  switch (this->getKind()) {
429  case NodeKind::NestedNameSpecifier:
430  return false;
431  case NodeKind::CallArguments:
432  return true;
433  case NodeKind::ParameterDeclarationList:
434  return true;
435  case NodeKind::DeclaratorList:
436  return true;
437  default:
438  llvm_unreachable("This is not a subclass of List, thus canBeEmpty() "
439  "cannot be called");
440  }
441 }
clang::syntax::List::canBeEmpty
bool canBeEmpty() const
Whether this list can be empty in syntactically and semantically correct code.
Definition: Tree.cpp:427
clang::syntax::Node::dump
std::string dump(const TokenManager &SM) const
Dumps the structure of a subtree. For debugging and testing purposes.
Definition: Tree.cpp:220
clang::for
for(unsigned I=0, E=TL.getNumArgs();I !=E;++I)
Definition: RecursiveASTVisitor.h:1384
string
string(SUBSTRING ${CMAKE_CURRENT_BINARY_DIR} 0 ${PATH_LIB_START} PATH_HEAD) string(SUBSTRING $
Definition: CMakeLists.txt:22
clang::syntax::List::getDelimiterTokenKind
clang::tok::TokenKind getDelimiterTokenKind() const
Returns the appropriate delimiter for this list.
Definition: Tree.cpp:399
clang::syntax::Node
A node in a syntax tree.
Definition: Tree.h:54
clang::syntax::List::TerminationKind
TerminationKind
Definition: Tree.h:261
clang::syntax::List::getTerminationKind
TerminationKind getTerminationKind() const
Definition: Tree.cpp:413
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:56
clang::syntax::NodeRole::Detached
@ Detached
A node without a parent.
clang::syntax::Node::dumpTokens
std::string dumpTokens(const TokenManager &SM) const
Dumps the tokens forming this subtree.
Definition: Tree.cpp:227
End
SourceLocation End
Definition: USRLocFinder.cpp:167
clang::syntax::Tree::findFirstLeaf
const Leaf * findFirstLeaf() const
Definition: Tree.cpp:283
clang::ast_matchers::traverse
internal::Matcher< T > traverse(TraversalKind TK, const internal::Matcher< T > &InnerMatcher)
Causes all nested matchers to be matched with the specified traversal kind.
Definition: ASTMatchers.h:815
clang::syntax::Node::canModify
bool canModify() const
If this function return false, the tree cannot be modified because there is no reasonable way to prod...
Definition: Tree.h:88
TokenKinds.h
clang::syntax::List::TerminationKind::MaybeTerminated
@ MaybeTerminated
Node
DynTypedNode Node
Definition: ASTMatchFinder.cpp:68
clang::syntax::Node::Node
Node(NodeKind Kind)
Newly created nodes are detached from a tree, parent and sibling links are set when the node is added...
Definition: Tree.cpp:37
clang::syntax::List::TerminationKind::Separated
@ Separated
clang::syntax::NodeRole::ListElement
@ ListElement
List API roles.
clang::syntax::Node::isDetached
bool isDetached() const
Whether the node is detached from a tree, i.e. does not have a parent.
Definition: Tree.cpp:44
clang::syntax::List::getElementsAsNodes
std::vector< Node * > getElementsAsNodes()
Returns the elements of the list.
Definition: Tree.cpp:357
clang::syntax::List::getElementsAsNodesAndDelimiters
std::vector< ElementAndDelimiter< Node > > getElementsAsNodesAndDelimiters()
Returns the elements and corresponding delimiters.
Definition: Tree.cpp:312
clang::syntax::NodeRole::Unknown
@ Unknown
Children of an unknown semantic nature, e.g. skipped tokens, comments.
clang::syntax::TokenManager::getText
virtual llvm::StringRef getText(Key K) const =0
getKind
static Decl::Kind getKind(const Decl *D)
Definition: DeclBase.cpp:1025
clang::syntax::List::TerminationKind::Terminated
@ Terminated
clang::syntax::TokenManager
Defines interfaces for operating "Token" in the clang syntax-tree.
Definition: TokenManager.h:29
clang::syntax::Node::getRole
NodeRole getRole() const
Definition: Tree.h:71
clang::tok::TokenKind
TokenKind
Provides a simple uniform namespace for tokens from all C languages.
Definition: TokenKinds.h:25
false
#define false
Definition: stdbool.h:22
clang::syntax::NodeRole::ListDelimiter
@ ListDelimiter
clang::syntax::TokenManager::Key
uintptr_t Key
A key to identify a specific token.
Definition: TokenManager.h:40
clang::syntax::Tree::findChild
const Node * findChild(NodeRole R) const
Find the first node with a corresponding role.
Definition: Tree.cpp:303
Begin
SourceLocation Begin
Definition: USRLocFinder.cpp:165
Tree.h
Nodes.h
clang::syntax::Leaf
A leaf node points to a single token.
Definition: Tree.h:132
clang::ObjCPropertyAttribute::Kind
Kind
Definition: DeclObjCCommon.h:22
clang::syntax::NodeRole
NodeRole
A relation between a parent and child node, e.g.
Definition: Nodes.h:54
clang
Definition: CalledOnceCheck.h:17
clang::syntax::NodeKind
NodeKind
A kind of a syntax node, used for implementing casts.
Definition: Nodes.h:32
clang::syntax::Tree::findLastLeaf
const Leaf * findLastLeaf() const
Definition: Tree.cpp:293
clang::syntax::Node::isOriginal
bool isOriginal() const
Whether the node was created from the AST backed by the source code rather than added later through m...
Definition: Tree.h:81
unsigned
clang::syntax::Leaf::Leaf
Leaf(TokenManager::Key K)
Definition: Tree.cpp:35
Parent
NodeId Parent
Definition: ASTDiff.cpp:190
clang::syntax::Node::assertInvariants
void assertInvariants() const
Asserts invariants on this node of the tree and its immediate children.
Definition: Tree.cpp:239
clang::syntax::Node::assertInvariantsRecursive
void assertInvariantsRecursive() const
Runs checkInvariants on all nodes in the subtree. No-op if NDEBUG is set.
Definition: Tree.cpp:277
clang::ento::ObjKind::OS
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...