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