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::Unknown) { 89 // FIXME: print the symbolic name of a role. 90 if (N->role() == syntax::NodeRole::Detached) 91 OS << "*: "; 92 else 93 OS << static_cast<int>(N->role()) << ": "; 94 } 95 if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) { 96 dumpTokens(OS, *L->token(), A.sourceManager()); 97 OS << "\n"; 98 return; 99 } 100 101 auto *T = llvm::cast<syntax::Tree>(N); 102 OS << T->kind() << "\n"; 103 104 for (auto It = T->firstChild(); It != nullptr; It = It->nextSibling()) { 105 for (bool Filled : IndentMask) { 106 if (Filled) 107 OS << "| "; 108 else 109 OS << " "; 110 } 111 if (!It->nextSibling()) { 112 OS << "`-"; 113 IndentMask.push_back(false); 114 } else { 115 OS << "|-"; 116 IndentMask.push_back(true); 117 } 118 dumpTree(OS, It, A, IndentMask); 119 IndentMask.pop_back(); 120 } 121 } 122 } // namespace 123 124 std::string syntax::Node::dump(const Arena &A) const { 125 std::string Str; 126 llvm::raw_string_ostream OS(Str); 127 dumpTree(OS, this, A, /*IndentMask=*/{}); 128 return std::move(OS.str()); 129 } 130 131 std::string syntax::Node::dumpTokens(const Arena &A) const { 132 std::string Storage; 133 llvm::raw_string_ostream OS(Storage); 134 traverse(this, [&](const syntax::Node *N) { 135 auto *L = llvm::dyn_cast<syntax::Leaf>(N); 136 if (!L) 137 return; 138 ::dumpTokens(OS, *L->token(), A.sourceManager()); 139 }); 140 return OS.str(); 141 } 142 143 syntax::Node *syntax::Tree::findChild(NodeRole R) { 144 for (auto *C = FirstChild; C; C = C->nextSibling()) { 145 if (C->role() == R) 146 return C; 147 } 148 return nullptr; 149 } 150