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