441 lines · cpp
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-exception6//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/BitVector.h"12#include "llvm/Support/raw_ostream.h"13#include <cassert>14 15using namespace clang;16 17namespace {18static void traverse(const syntax::Node *N,19 llvm::function_ref<void(const syntax::Node *)> Visit) {20 if (auto *T = dyn_cast<syntax::Tree>(N)) {21 for (const syntax::Node &C : T->getChildren())22 traverse(&C, Visit);23 }24 Visit(N);25}26static void traverse(syntax::Node *N,27 llvm::function_ref<void(syntax::Node *)> Visit) {28 traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) {29 Visit(const_cast<syntax::Node *>(N));30 });31}32} // namespace33 34syntax::Leaf::Leaf(syntax::TokenManager::Key K) : Node(NodeKind::Leaf), K(K) {}35 36syntax::Node::Node(NodeKind Kind)37 : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),38 Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),39 CanModify(false) {40 this->setRole(NodeRole::Detached);41}42 43bool syntax::Node::isDetached() const {44 return getRole() == NodeRole::Detached;45}46 47void syntax::Node::setRole(NodeRole NR) {48 this->Role = static_cast<unsigned>(NR);49}50 51void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) {52 assert(Child->getRole() == NodeRole::Detached);53 assert(Role != NodeRole::Detached);54 55 Child->setRole(Role);56 appendChildLowLevel(Child);57}58 59void syntax::Tree::appendChildLowLevel(Node *Child) {60 assert(Child->Parent == nullptr);61 assert(Child->NextSibling == nullptr);62 assert(Child->PreviousSibling == nullptr);63 assert(Child->getRole() != NodeRole::Detached);64 65 Child->Parent = this;66 if (this->LastChild) {67 Child->PreviousSibling = this->LastChild;68 this->LastChild->NextSibling = Child;69 } else70 this->FirstChild = Child;71 72 this->LastChild = Child;73}74 75void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {76 assert(Child->getRole() == NodeRole::Detached);77 assert(Role != NodeRole::Detached);78 79 Child->setRole(Role);80 prependChildLowLevel(Child);81}82 83void syntax::Tree::prependChildLowLevel(Node *Child) {84 assert(Child->Parent == nullptr);85 assert(Child->NextSibling == nullptr);86 assert(Child->PreviousSibling == nullptr);87 assert(Child->getRole() != NodeRole::Detached);88 89 Child->Parent = this;90 if (this->FirstChild) {91 Child->NextSibling = this->FirstChild;92 this->FirstChild->PreviousSibling = Child;93 } else94 this->LastChild = Child;95 96 this->FirstChild = Child;97}98 99void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End,100 Node *New) {101 assert((!Begin || Begin->Parent == this) &&102 "`Begin` is not a child of `this`.");103 assert((!End || End->Parent == this) && "`End` is not a child of `this`.");104 assert(canModify() && "Cannot modify `this`.");105 106#ifndef NDEBUG107 for (auto *N = New; N; N = N->NextSibling) {108 assert(N->Parent == nullptr);109 assert(N->getRole() != NodeRole::Detached && "Roles must be set");110 // FIXME: validate the role.111 }112 113 auto Reachable = [](Node *From, Node *N) {114 if (!N)115 return true;116 for (auto *It = From; It; It = It->NextSibling)117 if (It == N)118 return true;119 return false;120 };121 assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable.");122 assert(Reachable(Begin, End) && "`End` is not after `Begin`.");123#endif124 125 if (!New && Begin == End)126 return;127 128 // Mark modification.129 for (auto *T = this; T && T->Original; T = T->Parent)130 T->Original = false;131 132 // Save the node before the range to be removed. Later we insert the `New`133 // range after this node.134 auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;135 136 // Detach old nodes.137 for (auto *N = Begin; N != End;) {138 auto *Next = N->NextSibling;139 140 N->setRole(NodeRole::Detached);141 N->Parent = nullptr;142 N->NextSibling = nullptr;143 N->PreviousSibling = nullptr;144 if (N->Original)145 traverse(N, [](Node *C) { C->Original = false; });146 147 N = Next;148 }149 150 // Attach new range.151 auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;152 auto *&NewLast = End ? End->PreviousSibling : LastChild;153 154 if (!New) {155 NewFirst = End;156 NewLast = BeforeBegin;157 return;158 }159 160 New->PreviousSibling = BeforeBegin;161 NewFirst = New;162 163 Node *LastInNew;164 for (auto *N = New; N != nullptr; N = N->NextSibling) {165 LastInNew = N;166 N->Parent = this;167 }168 LastInNew->NextSibling = End;169 NewLast = LastInNew;170}171 172namespace {173static void dumpNode(raw_ostream &OS, const syntax::Node *N,174 const syntax::TokenManager &TM, llvm::BitVector IndentMask) {175 auto DumpExtraInfo = [&OS](const syntax::Node *N) {176 if (N->getRole() != syntax::NodeRole::Unknown)177 OS << " " << N->getRole();178 if (!N->isOriginal())179 OS << " synthesized";180 if (!N->canModify())181 OS << " unmodifiable";182 };183 184 assert(N);185 if (const auto *L = dyn_cast<syntax::Leaf>(N)) {186 OS << "'";187 OS << TM.getText(L->getTokenKey());188 OS << "'";189 DumpExtraInfo(N);190 OS << "\n";191 return;192 }193 194 const auto *T = cast<syntax::Tree>(N);195 OS << T->getKind();196 DumpExtraInfo(N);197 OS << "\n";198 199 for (const syntax::Node &It : T->getChildren()) {200 for (unsigned Idx = 0; Idx < IndentMask.size(); ++Idx) {201 if (IndentMask[Idx])202 OS << "| ";203 else204 OS << " ";205 }206 if (!It.getNextSibling()) {207 OS << "`-";208 IndentMask.push_back(false);209 } else {210 OS << "|-";211 IndentMask.push_back(true);212 }213 dumpNode(OS, &It, TM, IndentMask);214 IndentMask.pop_back();215 }216}217} // namespace218 219std::string syntax::Node::dump(const TokenManager &TM) const {220 std::string Str;221 llvm::raw_string_ostream OS(Str);222 dumpNode(OS, this, TM, /*IndentMask=*/{});223 return std::move(OS.str());224}225 226std::string syntax::Node::dumpTokens(const TokenManager &TM) const {227 std::string Storage;228 llvm::raw_string_ostream OS(Storage);229 traverse(this, [&](const syntax::Node *N) {230 if (const auto *L = dyn_cast<syntax::Leaf>(N)) {231 OS << TM.getText(L->getTokenKey());232 OS << " ";233 }234 });235 return Storage;236}237 238void syntax::Node::assertInvariants() const {239#ifndef NDEBUG240 if (isDetached())241 assert(getParent() == nullptr);242 else243 assert(getParent() != nullptr);244 245 const auto *T = dyn_cast<Tree>(this);246 if (!T)247 return;248 for (const Node &C : T->getChildren()) {249 if (T->isOriginal())250 assert(C.isOriginal());251 assert(!C.isDetached());252 assert(C.getParent() == T);253 const auto *Next = C.getNextSibling();254 assert(!Next || &C == Next->getPreviousSibling());255 if (!C.getNextSibling())256 assert(&C == T->getLastChild() &&257 "Last child is reachable by advancing from the first child.");258 }259 260 const auto *L = dyn_cast<List>(T);261 if (!L)262 return;263 for (const Node &C : T->getChildren()) {264 assert(C.getRole() == NodeRole::ListElement ||265 C.getRole() == NodeRole::ListDelimiter);266 if (C.getRole() == NodeRole::ListDelimiter) {267 assert(isa<Leaf>(C));268 // FIXME: re-enable it when there is way to retrieve token kind in Leaf.269 // assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind());270 }271 }272 273#endif274}275 276void syntax::Node::assertInvariantsRecursive() const {277#ifndef NDEBUG278 traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });279#endif280}281 282const syntax::Leaf *syntax::Tree::findFirstLeaf() const {283 for (const Node &C : getChildren()) {284 if (const auto *L = dyn_cast<syntax::Leaf>(&C))285 return L;286 if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf())287 return L;288 }289 return nullptr;290}291 292const syntax::Leaf *syntax::Tree::findLastLeaf() const {293 for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) {294 if (const auto *L = dyn_cast<syntax::Leaf>(C))295 return L;296 if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf())297 return L;298 }299 return nullptr;300}301 302const syntax::Node *syntax::Tree::findChild(NodeRole R) const {303 for (const Node &C : getChildren()) {304 if (C.getRole() == R)305 return &C;306 }307 return nullptr;308}309 310std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>311syntax::List::getElementsAsNodesAndDelimiters() {312 if (!getFirstChild())313 return {};314 315 std::vector<syntax::List::ElementAndDelimiter<Node>> Children;316 syntax::Node *ElementWithoutDelimiter = nullptr;317 for (Node &C : getChildren()) {318 switch (C.getRole()) {319 case syntax::NodeRole::ListElement: {320 if (ElementWithoutDelimiter) {321 Children.push_back({ElementWithoutDelimiter, nullptr});322 }323 ElementWithoutDelimiter = &C;324 break;325 }326 case syntax::NodeRole::ListDelimiter: {327 Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)});328 ElementWithoutDelimiter = nullptr;329 break;330 }331 default:332 llvm_unreachable(333 "A list can have only elements and delimiters as children.");334 }335 }336 337 switch (getTerminationKind()) {338 case syntax::List::TerminationKind::Separated: {339 Children.push_back({ElementWithoutDelimiter, nullptr});340 break;341 }342 case syntax::List::TerminationKind::Terminated:343 case syntax::List::TerminationKind::MaybeTerminated: {344 if (ElementWithoutDelimiter) {345 Children.push_back({ElementWithoutDelimiter, nullptr});346 }347 break;348 }349 }350 351 return Children;352}353 354// Almost the same implementation of `getElementsAsNodesAndDelimiters` but355// ignoring delimiters356std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {357 if (!getFirstChild())358 return {};359 360 std::vector<syntax::Node *> Children;361 syntax::Node *ElementWithoutDelimiter = nullptr;362 for (Node &C : getChildren()) {363 switch (C.getRole()) {364 case syntax::NodeRole::ListElement: {365 if (ElementWithoutDelimiter) {366 Children.push_back(ElementWithoutDelimiter);367 }368 ElementWithoutDelimiter = &C;369 break;370 }371 case syntax::NodeRole::ListDelimiter: {372 Children.push_back(ElementWithoutDelimiter);373 ElementWithoutDelimiter = nullptr;374 break;375 }376 default:377 llvm_unreachable("A list has only elements or delimiters.");378 }379 }380 381 switch (getTerminationKind()) {382 case syntax::List::TerminationKind::Separated: {383 Children.push_back(ElementWithoutDelimiter);384 break;385 }386 case syntax::List::TerminationKind::Terminated:387 case syntax::List::TerminationKind::MaybeTerminated: {388 if (ElementWithoutDelimiter) {389 Children.push_back(ElementWithoutDelimiter);390 }391 break;392 }393 }394 395 return Children;396}397 398clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const {399 switch (this->getKind()) {400 case NodeKind::NestedNameSpecifier:401 return clang::tok::coloncolon;402 case NodeKind::CallArguments:403 case NodeKind::ParameterDeclarationList:404 case NodeKind::DeclaratorList:405 return clang::tok::comma;406 default:407 llvm_unreachable("This is not a subclass of List, thus "408 "getDelimiterTokenKind() cannot be called");409 }410}411 412syntax::List::TerminationKind syntax::List::getTerminationKind() const {413 switch (this->getKind()) {414 case NodeKind::NestedNameSpecifier:415 return TerminationKind::Terminated;416 case NodeKind::CallArguments:417 case NodeKind::ParameterDeclarationList:418 case NodeKind::DeclaratorList:419 return TerminationKind::Separated;420 default:421 llvm_unreachable("This is not a subclass of List, thus "422 "getTerminationKind() cannot be called");423 }424}425 426bool syntax::List::canBeEmpty() const {427 switch (this->getKind()) {428 case NodeKind::NestedNameSpecifier:429 return false;430 case NodeKind::CallArguments:431 return true;432 case NodeKind::ParameterDeclarationList:433 return true;434 case NodeKind::DeclaratorList:435 return true;436 default:437 llvm_unreachable("This is not a subclass of List, thus canBeEmpty() "438 "cannot be called");439 }440}441