diff options
Diffstat (limited to 'clang/lib/Tooling/Syntax/Tree.cpp')
-rw-r--r-- | clang/lib/Tooling/Syntax/Tree.cpp | 412 |
1 files changed, 305 insertions, 107 deletions
diff --git a/clang/lib/Tooling/Syntax/Tree.cpp b/clang/lib/Tooling/Syntax/Tree.cpp index 37579e6145b6..07ee13e313f5 100644 --- a/clang/lib/Tooling/Syntax/Tree.cpp +++ b/clang/lib/Tooling/Syntax/Tree.cpp @@ -19,8 +19,8 @@ namespace { static void traverse(const syntax::Node *N, llvm::function_ref<void(const syntax::Node *)> Visit) { if (auto *T = dyn_cast<syntax::Tree>(N)) { - for (auto *C = T->firstChild(); C; C = C->nextSibling()) - traverse(C, Visit); + for (const syntax::Node &C : T->getChildren()) + traverse(&C, Visit); } Visit(N); } @@ -33,14 +33,14 @@ static void traverse(syntax::Node *N, } // namespace syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts, - TokenBuffer Tokens) - : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {} + const TokenBuffer &Tokens) + : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(Tokens) {} -const clang::syntax::TokenBuffer &syntax::Arena::tokenBuffer() const { +const syntax::TokenBuffer &syntax::Arena::getTokenBuffer() const { return Tokens; } -std::pair<FileID, llvm::ArrayRef<syntax::Token>> +std::pair<FileID, ArrayRef<syntax::Token>> syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) { auto FID = SourceMgr.createFileID(std::move(Input)); auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts)); @@ -52,26 +52,47 @@ syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) { assert(Tok != nullptr); } -bool syntax::Leaf::classof(const Node *N) { - return N->kind() == NodeKind::Leaf; -} - syntax::Node::Node(NodeKind Kind) - : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)), - Role(0), Original(false), CanModify(false) { + : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr), + Kind(static_cast<unsigned>(Kind)), Role(0), Original(false), + CanModify(false) { this->setRole(NodeRole::Detached); } -bool syntax::Node::isDetached() const { return role() == NodeRole::Detached; } +bool syntax::Node::isDetached() const { + return getRole() == NodeRole::Detached; +} void syntax::Node::setRole(NodeRole NR) { this->Role = static_cast<unsigned>(NR); } -bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; } +void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) { + assert(Child->getRole() == NodeRole::Detached); + assert(Role != NodeRole::Detached); + + Child->setRole(Role); + appendChildLowLevel(Child); +} + +void syntax::Tree::appendChildLowLevel(Node *Child) { + assert(Child->Parent == nullptr); + assert(Child->NextSibling == nullptr); + assert(Child->PreviousSibling == nullptr); + assert(Child->getRole() != NodeRole::Detached); + + Child->Parent = this; + if (this->LastChild) { + Child->PreviousSibling = this->LastChild; + this->LastChild->NextSibling = Child; + } else + this->FirstChild = Child; + + this->LastChild = Child; +} void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) { - assert(Child->role() == NodeRole::Detached); + assert(Child->getRole() == NodeRole::Detached); assert(Role != NodeRole::Detached); Child->setRole(Role); @@ -81,135 +102,166 @@ void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) { void syntax::Tree::prependChildLowLevel(Node *Child) { assert(Child->Parent == nullptr); assert(Child->NextSibling == nullptr); - assert(Child->role() != NodeRole::Detached); + assert(Child->PreviousSibling == nullptr); + assert(Child->getRole() != NodeRole::Detached); Child->Parent = this; - Child->NextSibling = this->FirstChild; + if (this->FirstChild) { + Child->NextSibling = this->FirstChild; + this->FirstChild->PreviousSibling = Child; + } else + this->LastChild = Child; + this->FirstChild = Child; } -void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End, +void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End, Node *New) { - assert(!BeforeBegin || BeforeBegin->Parent == this); + assert((!Begin || Begin->Parent == this) && + "`Begin` is not a child of `this`."); + assert((!End || End->Parent == this) && "`End` is not a child of `this`."); + assert(canModify() && "Cannot modify `this`."); #ifndef NDEBUG - for (auto *N = New; N; N = N->nextSibling()) { + for (auto *N = New; N; N = N->NextSibling) { assert(N->Parent == nullptr); - assert(N->role() != NodeRole::Detached && "Roles must be set"); + assert(N->getRole() != NodeRole::Detached && "Roles must be set"); // FIXME: sanity-check the role. } + + auto Reachable = [](Node *From, Node *N) { + if (!N) + return true; + for (auto *It = From; It; It = It->NextSibling) + if (It == N) + return true; + return false; + }; + assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable."); + assert(Reachable(Begin, End) && "`End` is not after `Begin`."); #endif + if (!New && Begin == End) + return; + + // Mark modification. + for (auto *T = this; T && T->Original; T = T->Parent) + T->Original = false; + + // Save the node before the range to be removed. Later we insert the `New` + // range after this node. + auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild; + // Detach old nodes. - for (auto *N = !BeforeBegin ? FirstChild : BeforeBegin->nextSibling(); - N != End;) { + for (auto *N = Begin; N != End;) { auto *Next = N->NextSibling; N->setRole(NodeRole::Detached); N->Parent = nullptr; N->NextSibling = nullptr; + N->PreviousSibling = nullptr; if (N->Original) - traverse(N, [&](Node *C) { C->Original = false; }); + traverse(N, [](Node *C) { C->Original = false; }); N = Next; } - // Attach new nodes. - if (BeforeBegin) - BeforeBegin->NextSibling = New ? New : End; - else - FirstChild = New ? New : End; + // Attach new range. + auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild; + auto *&NewLast = End ? End->PreviousSibling : LastChild; - if (New) { - auto *Last = New; - for (auto *N = New; N != nullptr; N = N->nextSibling()) { - Last = N; - N->Parent = this; - } - Last->NextSibling = End; + if (!New) { + NewFirst = End; + NewLast = BeforeBegin; + return; } - // Mark the node as modified. - for (auto *T = this; T && T->Original; T = T->Parent) - T->Original = false; + New->PreviousSibling = BeforeBegin; + NewFirst = New; + + Node *LastInNew; + for (auto *N = New; N != nullptr; N = N->NextSibling) { + LastInNew = N; + N->Parent = this; + } + LastInNew->NextSibling = End; + NewLast = LastInNew; } namespace { -static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens, - const SourceManager &SM) { - assert(!Tokens.empty()); - bool First = true; - for (const auto &T : Tokens) { - if (!First) - OS << " "; - else - First = false; - // Handle 'eof' separately, calling text() on it produces an empty string. - if (T.kind() == tok::eof) { - OS << "<eof>"; - continue; - } - OS << T.text(SM); - } +static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L, + const SourceManager &SM) { + assert(L); + const auto *Token = L->getToken(); + assert(Token); + // Handle 'eof' separately, calling text() on it produces an empty string. + if (Token->kind() == tok::eof) + OS << "<eof>"; + else + OS << Token->text(SM); } -static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N, - const syntax::Arena &A, std::vector<bool> IndentMask) { - std::string Marks; - if (!N->isOriginal()) - Marks += "M"; - if (N->role() == syntax::NodeRole::Detached) - Marks += "*"; // FIXME: find a nice way to print other roles. - if (!N->canModify()) - Marks += "I"; - if (!Marks.empty()) - OS << Marks << ": "; - - if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) { - dumpTokens(OS, *L->token(), A.sourceManager()); +static void dumpNode(raw_ostream &OS, const syntax::Node *N, + const SourceManager &SM, std::vector<bool> IndentMask) { + auto DumpExtraInfo = [&OS](const syntax::Node *N) { + if (N->getRole() != syntax::NodeRole::Unknown) + OS << " " << N->getRole(); + if (!N->isOriginal()) + OS << " synthesized"; + if (!N->canModify()) + OS << " unmodifiable"; + }; + + assert(N); + if (const auto *L = dyn_cast<syntax::Leaf>(N)) { + OS << "'"; + dumpLeaf(OS, L, SM); + OS << "'"; + DumpExtraInfo(N); OS << "\n"; return; } - auto *T = llvm::cast<syntax::Tree>(N); - OS << T->kind() << "\n"; + const auto *T = cast<syntax::Tree>(N); + OS << T->getKind(); + DumpExtraInfo(N); + OS << "\n"; - for (auto It = T->firstChild(); It != nullptr; It = It->nextSibling()) { + for (const syntax::Node &It : T->getChildren()) { for (bool Filled : IndentMask) { if (Filled) OS << "| "; else OS << " "; } - if (!It->nextSibling()) { + if (!It.getNextSibling()) { OS << "`-"; IndentMask.push_back(false); } else { OS << "|-"; IndentMask.push_back(true); } - dumpTree(OS, It, A, IndentMask); + dumpNode(OS, &It, SM, IndentMask); IndentMask.pop_back(); } } } // namespace -std::string syntax::Node::dump(const Arena &A) const { +std::string syntax::Node::dump(const SourceManager &SM) const { std::string Str; llvm::raw_string_ostream OS(Str); - dumpTree(OS, this, A, /*IndentMask=*/{}); + dumpNode(OS, this, SM, /*IndentMask=*/{}); return std::move(OS.str()); } -std::string syntax::Node::dumpTokens(const Arena &A) const { +std::string syntax::Node::dumpTokens(const SourceManager &SM) const { std::string Storage; llvm::raw_string_ostream OS(Storage); traverse(this, [&](const syntax::Node *N) { - auto *L = llvm::dyn_cast<syntax::Leaf>(N); - if (!L) - return; - ::dumpTokens(OS, *L->token(), A.sourceManager()); - OS << " "; + if (const auto *L = dyn_cast<syntax::Leaf>(N)) { + dumpLeaf(OS, L, SM); + OS << " "; + } }); return OS.str(); } @@ -217,19 +269,37 @@ std::string syntax::Node::dumpTokens(const Arena &A) const { void syntax::Node::assertInvariants() const { #ifndef NDEBUG if (isDetached()) - assert(parent() == nullptr); + assert(getParent() == nullptr); else - assert(parent() != nullptr); + assert(getParent() != nullptr); - auto *T = dyn_cast<Tree>(this); + const auto *T = dyn_cast<Tree>(this); if (!T) return; - for (auto *C = T->firstChild(); C; C = C->nextSibling()) { + for (const Node &C : T->getChildren()) { if (T->isOriginal()) - assert(C->isOriginal()); - assert(!C->isDetached()); - assert(C->parent() == T); + assert(C.isOriginal()); + assert(!C.isDetached()); + assert(C.getParent() == T); + const auto *Next = C.getNextSibling(); + assert(!Next || &C == Next->getPreviousSibling()); + if (!C.getNextSibling()) + assert(&C == T->getLastChild() && + "Last child is reachable by advancing from the first child."); + } + + const auto *L = dyn_cast<List>(T); + if (!L) + return; + for (const Node &C : T->getChildren()) { + assert(C.getRole() == NodeRole::ListElement || + C.getRole() == NodeRole::ListDelimiter); + if (C.getRole() == NodeRole::ListDelimiter) { + assert(isa<Leaf>(C)); + assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind()); + } } + #endif } @@ -239,34 +309,162 @@ void syntax::Node::assertInvariantsRecursive() const { #endif } -syntax::Leaf *syntax::Tree::firstLeaf() { - auto *T = this; - while (auto *C = T->firstChild()) { - if (auto *L = dyn_cast<syntax::Leaf>(C)) +const syntax::Leaf *syntax::Tree::findFirstLeaf() const { + for (const Node &C : getChildren()) { + if (const auto *L = dyn_cast<syntax::Leaf>(&C)) + return L; + if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf()) return L; - T = cast<syntax::Tree>(C); } return nullptr; } -syntax::Leaf *syntax::Tree::lastLeaf() { - auto *T = this; - while (auto *C = T->firstChild()) { - // Find the last child. - while (auto *Next = C->nextSibling()) - C = Next; - - if (auto *L = dyn_cast<syntax::Leaf>(C)) +const syntax::Leaf *syntax::Tree::findLastLeaf() const { + for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) { + if (const auto *L = dyn_cast<syntax::Leaf>(C)) + return L; + if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf()) return L; - T = cast<syntax::Tree>(C); } return nullptr; } -syntax::Node *syntax::Tree::findChild(NodeRole R) { - for (auto *C = FirstChild; C; C = C->nextSibling()) { - if (C->role() == R) - return C; +const syntax::Node *syntax::Tree::findChild(NodeRole R) const { + for (const Node &C : getChildren()) { + if (C.getRole() == R) + return &C; } return nullptr; } + +std::vector<syntax::List::ElementAndDelimiter<syntax::Node>> +syntax::List::getElementsAsNodesAndDelimiters() { + if (!getFirstChild()) + return {}; + + std::vector<syntax::List::ElementAndDelimiter<Node>> Children; + syntax::Node *ElementWithoutDelimiter = nullptr; + for (Node &C : getChildren()) { + switch (C.getRole()) { + case syntax::NodeRole::ListElement: { + if (ElementWithoutDelimiter) { + Children.push_back({ElementWithoutDelimiter, nullptr}); + } + ElementWithoutDelimiter = &C; + break; + } + case syntax::NodeRole::ListDelimiter: { + Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)}); + ElementWithoutDelimiter = nullptr; + break; + } + default: + llvm_unreachable( + "A list can have only elements and delimiters as children."); + } + } + + switch (getTerminationKind()) { + case syntax::List::TerminationKind::Separated: { + Children.push_back({ElementWithoutDelimiter, nullptr}); + break; + } + case syntax::List::TerminationKind::Terminated: + case syntax::List::TerminationKind::MaybeTerminated: { + if (ElementWithoutDelimiter) { + Children.push_back({ElementWithoutDelimiter, nullptr}); + } + break; + } + } + + return Children; +} + +// Almost the same implementation of `getElementsAsNodesAndDelimiters` but +// ignoring delimiters +std::vector<syntax::Node *> syntax::List::getElementsAsNodes() { + if (!getFirstChild()) + return {}; + + std::vector<syntax::Node *> Children; + syntax::Node *ElementWithoutDelimiter = nullptr; + for (Node &C : getChildren()) { + switch (C.getRole()) { + case syntax::NodeRole::ListElement: { + if (ElementWithoutDelimiter) { + Children.push_back(ElementWithoutDelimiter); + } + ElementWithoutDelimiter = &C; + break; + } + case syntax::NodeRole::ListDelimiter: { + Children.push_back(ElementWithoutDelimiter); + ElementWithoutDelimiter = nullptr; + break; + } + default: + llvm_unreachable("A list has only elements or delimiters."); + } + } + + switch (getTerminationKind()) { + case syntax::List::TerminationKind::Separated: { + Children.push_back(ElementWithoutDelimiter); + break; + } + case syntax::List::TerminationKind::Terminated: + case syntax::List::TerminationKind::MaybeTerminated: { + if (ElementWithoutDelimiter) { + Children.push_back(ElementWithoutDelimiter); + } + break; + } + } + + return Children; +} + +clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const { + switch (this->getKind()) { + case NodeKind::NestedNameSpecifier: + return clang::tok::coloncolon; + case NodeKind::CallArguments: + case NodeKind::ParameterDeclarationList: + case NodeKind::DeclaratorList: + return clang::tok::comma; + default: + llvm_unreachable("This is not a subclass of List, thus " + "getDelimiterTokenKind() cannot be called"); + } +} + +syntax::List::TerminationKind syntax::List::getTerminationKind() const { + switch (this->getKind()) { + case NodeKind::NestedNameSpecifier: + return TerminationKind::Terminated; + case NodeKind::CallArguments: + case NodeKind::ParameterDeclarationList: + case NodeKind::DeclaratorList: + return TerminationKind::Separated; + default: + llvm_unreachable("This is not a subclass of List, thus " + "getTerminationKind() cannot be called"); + } +} + +bool syntax::List::canBeEmpty() const { + switch (this->getKind()) { + case NodeKind::NestedNameSpecifier: + return false; + case NodeKind::CallArguments: + return true; + case NodeKind::ParameterDeclarationList: + return true; + case NodeKind::DeclaratorList: + return true; + default: + llvm_unreachable("This is not a subclass of List, thus canBeEmpty() " + "cannot be called"); + } +} |