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