11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/BitVector.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/Support/Casting.h"
17 using namespace clang;
22 if (
auto *T = dyn_cast<syntax::Tree>(N)) {
38 : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(Tokens) {}
44 std::pair<FileID, ArrayRef<syntax::Token>>
45 syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
46 auto FID = SourceMgr.createFileID(std::move(Input));
47 auto It = ExtraTokens.try_emplace(FID,
tokenize(FID, SourceMgr, LangOpts));
48 assert(It.second &&
"duplicate FileID");
49 return {FID, It.first->second};
53 assert(Tok !=
nullptr);
57 :
Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
67 void syntax::Node::setRole(
NodeRole NR) {
68 this->Role =
static_cast<unsigned>(NR);
71 void syntax::Tree::appendChildLowLevel(
Node *Child,
NodeRole Role) {
76 appendChildLowLevel(Child);
79 void syntax::Tree::appendChildLowLevel(
Node *Child) {
80 assert(Child->Parent ==
nullptr);
81 assert(Child->NextSibling ==
nullptr);
82 assert(Child->PreviousSibling ==
nullptr);
86 if (this->LastChild) {
87 Child->PreviousSibling = this->LastChild;
88 this->LastChild->NextSibling = Child;
90 this->FirstChild = Child;
92 this->LastChild = Child;
95 void syntax::Tree::prependChildLowLevel(
Node *Child,
NodeRole Role) {
100 prependChildLowLevel(Child);
103 void syntax::Tree::prependChildLowLevel(
Node *Child) {
104 assert(Child->Parent ==
nullptr);
105 assert(Child->NextSibling ==
nullptr);
106 assert(Child->PreviousSibling ==
nullptr);
109 Child->Parent =
this;
110 if (this->FirstChild) {
111 Child->NextSibling = this->FirstChild;
112 this->FirstChild->PreviousSibling = Child;
114 this->LastChild = Child;
116 this->FirstChild = Child;
122 "`Begin` is not a child of `this`.");
123 assert((!
End ||
End->Parent ==
this) &&
"`End` is not a child of `this`.");
124 assert(canModify() &&
"Cannot modify `this`.");
127 for (
auto *N = New; N; N = N->NextSibling) {
128 assert(N->Parent ==
nullptr);
133 auto Reachable = [](
Node *From,
Node *N) {
136 for (
auto *It = From; It; It = It->NextSibling)
141 assert(Reachable(FirstChild,
Begin) &&
"`Begin` is not reachable.");
142 assert(Reachable(
Begin,
End) &&
"`End` is not after `Begin`.");
149 for (
auto *T =
this; T && T->Original; T = T->Parent)
154 auto *BeforeBegin =
Begin ?
Begin->PreviousSibling : LastChild;
158 auto *Next = N->NextSibling;
162 N->NextSibling =
nullptr;
163 N->PreviousSibling =
nullptr;
171 auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
172 auto *&NewLast =
End ?
End->PreviousSibling : LastChild;
176 NewLast = BeforeBegin;
180 New->PreviousSibling = BeforeBegin;
184 for (
auto *N = New; N !=
nullptr; N = N->NextSibling) {
188 LastInNew->NextSibling =
End;
193 static void dumpLeaf(raw_ostream &OS,
const syntax::Leaf *L,
205 static void dumpNode(raw_ostream &OS,
const syntax::Node *N,
211 OS <<
" synthesized";
213 OS <<
" unmodifiable";
217 if (
const auto *L = dyn_cast<syntax::Leaf>(N)) {
226 const auto *T = cast<syntax::Tree>(N);
232 for (
unsigned Idx = 0; Idx < IndentMask.size(); ++Idx) {
238 if (!It.getNextSibling()) {
240 IndentMask.push_back(
false);
243 IndentMask.push_back(
true);
245 dumpNode(OS, &It,
SM, IndentMask);
246 IndentMask.pop_back();
253 llvm::raw_string_ostream OS(Str);
254 dumpNode(OS,
this,
SM, {});
255 return std::move(OS.str());
260 llvm::raw_string_ostream OS(Storage);
262 if (
const auto *L = dyn_cast<syntax::Leaf>(N)) {
273 assert(getParent() ==
nullptr);
275 assert(getParent() !=
nullptr);
277 const auto *T = dyn_cast<Tree>(
this);
280 for (
const Node &C : T->getChildren()) {
282 assert(C.isOriginal());
283 assert(!C.isDetached());
284 assert(C.getParent() == T);
285 const auto *Next = C.getNextSibling();
286 assert(!Next || &C == Next->getPreviousSibling());
287 if (!C.getNextSibling())
288 assert(&C == T->getLastChild() &&
289 "Last child is reachable by advancing from the first child.");
292 const auto *L = dyn_cast<List>(T);
295 for (
const Node &C : T->getChildren()) {
299 assert(isa<Leaf>(C));
300 assert(cast<Leaf>(C).getToken()->
kind() == L->getDelimiterTokenKind());
314 for (
const Node &C : getChildren()) {
315 if (
const auto *L = dyn_cast<syntax::Leaf>(&C))
317 if (
const auto *L = cast<syntax::Tree>(C).findFirstLeaf())
324 for (
const auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
325 if (
const auto *L = dyn_cast<syntax::Leaf>(C))
327 if (
const auto *L = cast<syntax::Tree>(C)->findLastLeaf())
334 for (
const Node &C : getChildren()) {
335 if (C.getRole() == R)
341 std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
343 if (!getFirstChild())
346 std::vector<syntax::List::ElementAndDelimiter<Node>> Children;
348 for (
Node &C : getChildren()) {
349 switch (C.getRole()) {
351 if (ElementWithoutDelimiter) {
352 Children.push_back({ElementWithoutDelimiter,
nullptr});
354 ElementWithoutDelimiter = &C;
358 Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)});
359 ElementWithoutDelimiter =
nullptr;
364 "A list can have only elements and delimiters as children.");
368 switch (getTerminationKind()) {
370 Children.push_back({ElementWithoutDelimiter,
nullptr});
375 if (ElementWithoutDelimiter) {
376 Children.push_back({ElementWithoutDelimiter,
nullptr});
388 if (!getFirstChild())
391 std::vector<syntax::Node *> Children;
393 for (
Node &C : getChildren()) {
394 switch (C.getRole()) {
396 if (ElementWithoutDelimiter) {
397 Children.push_back(ElementWithoutDelimiter);
399 ElementWithoutDelimiter = &C;
403 Children.push_back(ElementWithoutDelimiter);
404 ElementWithoutDelimiter =
nullptr;
408 llvm_unreachable(
"A list has only elements or delimiters.");
412 switch (getTerminationKind()) {
414 Children.push_back(ElementWithoutDelimiter);
419 if (ElementWithoutDelimiter) {
420 Children.push_back(ElementWithoutDelimiter);
431 case NodeKind::NestedNameSpecifier:
432 return clang::tok::coloncolon;
433 case NodeKind::CallArguments:
434 case NodeKind::ParameterDeclarationList:
435 case NodeKind::DeclaratorList:
436 return clang::tok::comma;
438 llvm_unreachable(
"This is not a subclass of List, thus "
439 "getDelimiterTokenKind() cannot be called");
445 case NodeKind::NestedNameSpecifier:
446 return TerminationKind::Terminated;
447 case NodeKind::CallArguments:
448 case NodeKind::ParameterDeclarationList:
449 case NodeKind::DeclaratorList:
450 return TerminationKind::Separated;
452 llvm_unreachable(
"This is not a subclass of List, thus "
453 "getTerminationKind() cannot be called");
459 case NodeKind::NestedNameSpecifier:
461 case NodeKind::CallArguments:
463 case NodeKind::ParameterDeclarationList:
465 case NodeKind::DeclaratorList:
468 llvm_unreachable(
"This is not a subclass of List, thus canBeEmpty() "