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