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)) {}
44 
45 bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
46 
47 void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
48   assert(Child->Parent == nullptr);
49   assert(Child->NextSibling == nullptr);
50   assert(Child->role() == NodeRole::Detached);
51   assert(Role != NodeRole::Detached);
52 
53   Child->Parent = this;
54   Child->NextSibling = this->FirstChild;
55   Child->Role = static_cast<unsigned>(Role);
56   this->FirstChild = Child;
57 }
58 
59 namespace {
60 static void traverse(const syntax::Node *N,
61                      llvm::function_ref<void(const syntax::Node *)> Visit) {
62   if (auto *T = dyn_cast<syntax::Tree>(N)) {
63     for (auto *C = T->firstChild(); C; C = C->nextSibling())
64       traverse(C, Visit);
65   }
66   Visit(N);
67 }
68 static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens,
69                        const SourceManager &SM) {
70   assert(!Tokens.empty());
71   bool First = true;
72   for (const auto &T : Tokens) {
73     if (!First)
74       OS << " ";
75     else
76       First = false;
77     // Handle 'eof' separately, calling text() on it produces an empty string.
78     if (T.kind() == tok::eof) {
79       OS << "<eof>";
80       continue;
81     }
82     OS << T.text(SM);
83   }
84 }
85 
86 static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
87                      const syntax::Arena &A, std::vector<bool> IndentMask) {
88   if (N->role() == syntax::NodeRole::Detached)
89     OS << "*: ";
90   // FIXME: find a nice way to print other roles.
91 
92   if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
93     dumpTokens(OS, *L->token(), A.sourceManager());
94     OS << "\n";
95     return;
96   }
97 
98   auto *T = llvm::cast<syntax::Tree>(N);
99   OS << T->kind() << "\n";
100 
101   for (auto It = T->firstChild(); It != nullptr; It = It->nextSibling()) {
102     for (bool Filled : IndentMask) {
103       if (Filled)
104         OS << "| ";
105       else
106         OS << "  ";
107     }
108     if (!It->nextSibling()) {
109       OS << "`-";
110       IndentMask.push_back(false);
111     } else {
112       OS << "|-";
113       IndentMask.push_back(true);
114     }
115     dumpTree(OS, It, A, IndentMask);
116     IndentMask.pop_back();
117   }
118 }
119 } // namespace
120 
121 std::string syntax::Node::dump(const Arena &A) const {
122   std::string Str;
123   llvm::raw_string_ostream OS(Str);
124   dumpTree(OS, this, A, /*IndentMask=*/{});
125   return std::move(OS.str());
126 }
127 
128 std::string syntax::Node::dumpTokens(const Arena &A) const {
129   std::string Storage;
130   llvm::raw_string_ostream OS(Storage);
131   traverse(this, [&](const syntax::Node *N) {
132     auto *L = llvm::dyn_cast<syntax::Leaf>(N);
133     if (!L)
134       return;
135     ::dumpTokens(OS, *L->token(), A.sourceManager());
136   });
137   return OS.str();
138 }
139 
140 syntax::Node *syntax::Tree::findChild(NodeRole R) {
141   for (auto *C = FirstChild; C; C = C->nextSibling()) {
142     if (C->role() == R)
143       return C;
144   }
145   return nullptr;
146 }
147