eduucaldas created this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
eduucaldas requested review of this revision.
Rationale:
Children of a syntax tree had forward links only, because there was no
need for reverse links.
This need appeared when we started mutating the syntax tree.
On a forward list, to remove a target node in O(1) we need a pointer to the
node before the target. If we don't have this "before" pointer, we have to find
it, and that requires O(n).
So in order to remove a syntax node from a tree, we would similarly need to
find the node before to then remove. This is both not ergonomic nor does it
have a good complexity.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D90240
Files:
clang/include/clang/Tooling/Syntax/Tree.h
clang/lib/Tooling/Syntax/Mutations.cpp
clang/lib/Tooling/Syntax/Tree.cpp
Index: clang/lib/Tooling/Syntax/Tree.cpp
===================================================================
--- clang/lib/Tooling/Syntax/Tree.cpp
+++ clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
}
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);
}
@@ -85,10 +86,16 @@
void syntax::Tree::prependChildLowLevel(Node *Child) {
assert(Child->Parent == nullptr);
assert(Child->NextSibling == nullptr);
+ 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;
}
@@ -100,6 +107,7 @@
assert(canModify() && "Cannot modify `this`.");
Node *&Begin = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+ Node *&Last = End ? End->PreviousSibling : LastChild;
#ifndef NDEBUG
for (auto *N = New; N; N = N->NextSibling) {
@@ -135,6 +143,7 @@
N->setRole(NodeRole::Detached);
N->Parent = nullptr;
N->NextSibling = nullptr;
+ N->PreviousSibling = nullptr;
if (N->Original)
traverse(N, [](Node *C) { C->Original = false; });
@@ -143,16 +152,19 @@
if (!New) {
Begin = End;
+ Last = BeforeBegin;
return;
}
// Attach new nodes.
Begin = New;
- auto *Last = New;
+ New->PreviousSibling = BeforeBegin;
+ auto *LastInNew = New;
for (auto *N = New; N != nullptr; N = N->NextSibling) {
- Last = N;
+ LastInNew = N;
N->Parent = this;
}
- Last->NextSibling = End;
+ LastInNew->NextSibling = End;
+ Last = LastInNew;
}
namespace {
@@ -243,11 +255,20 @@
const auto *T = dyn_cast<Tree>(this);
if (!T)
return;
+
+ const auto *Last = T->getFirstChild();
+ for (; Last && Last->getNextSibling(); Last = Last->getNextSibling())
+ ;
+ assert(Last == T->getLastChild() &&
+ "Last child is reachable by advancing from the first child.");
+
for (const auto *C = T->getFirstChild(); C; C = C->getNextSibling()) {
if (T->isOriginal())
assert(C->isOriginal());
assert(!C->isDetached());
assert(C->getParent() == T);
+ const auto *Next = C->getNextSibling();
+ assert(!Next || C == Next->getPreviousSibling());
}
const auto *L = dyn_cast<List>(T);
@@ -282,14 +303,13 @@
}
syntax::Leaf *syntax::Tree::findLastLeaf() {
- syntax::Leaf *Last = nullptr;
- for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
+ for (auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
if (auto *L = dyn_cast<syntax::Leaf>(C))
- Last = L;
- else if (auto *L = cast<syntax::Tree>(C)->findLastLeaf())
- Last = L;
+ return L;
+ if (auto *L = cast<syntax::Tree>(C)->findLastLeaf())
+ return L;
}
- return Last;
+ return nullptr;
}
syntax::Node *syntax::Tree::findChild(NodeRole R) {
Index: clang/lib/Tooling/Syntax/Mutations.cpp
===================================================================
--- clang/lib/Tooling/Syntax/Mutations.cpp
+++ clang/lib/Tooling/Syntax/Mutations.cpp
@@ -23,19 +23,6 @@
using namespace clang;
-static syntax::Node *findPrevious(syntax::Node *N) {
- assert(N);
- assert(N->getParent());
- if (N->getParent()->getFirstChild() == N)
- return nullptr;
- for (syntax::Node *C = N->getParent()->getFirstChild(); C != nullptr;
- C = C->getNextSibling()) {
- if (C->getNextSibling() == N)
- return C;
- }
- llvm_unreachable("could not find a child node");
-}
-
// This class has access to the internals of tree nodes. Its sole purpose is to
// define helpers that allow implementing the high-level mutation operations.
class syntax::MutationsImpl {
@@ -46,6 +33,7 @@
assert(Anchor->Parent != nullptr);
assert(New->Parent == nullptr);
assert(New->NextSibling == nullptr);
+ assert(New->PreviousSibling == nullptr);
assert(New->isDetached());
assert(Role != NodeRole::Detached);
@@ -63,11 +51,13 @@
assert(Old->canModify());
assert(New->Parent == nullptr);
assert(New->NextSibling == nullptr);
+ assert(New->PreviousSibling == nullptr);
assert(New->isDetached());
New->Role = Old->Role;
auto *P = Old->getParent();
- P->replaceChildRangeLowLevel(findPrevious(Old), Old->getNextSibling(), New);
+ P->replaceChildRangeLowLevel(Old->getPreviousSibling(),
+ Old->getNextSibling(), New);
P->assertInvariants();
}
@@ -79,7 +69,7 @@
assert(N->canModify());
auto *P = N->getParent();
- P->replaceChildRangeLowLevel(findPrevious(N), N->getNextSibling(),
+ P->replaceChildRangeLowLevel(N->getPreviousSibling(), N->getNextSibling(),
/*New=*/nullptr);
P->assertInvariants();
Index: clang/include/clang/Tooling/Syntax/Tree.h
===================================================================
--- clang/include/clang/Tooling/Syntax/Tree.h
+++ clang/include/clang/Tooling/Syntax/Tree.h
@@ -106,6 +106,8 @@
const Node *getNextSibling() const { return NextSibling; }
Node *getNextSibling() { return NextSibling; }
+ const Node *getPreviousSibling() const { return PreviousSibling; }
+ Node *getPreviousSibling() { return PreviousSibling; }
/// Dumps the structure of a subtree. For debugging and testing purposes.
std::string dump(const SourceManager &SM) const;
@@ -132,6 +134,7 @@
Tree *Parent;
Node *NextSibling;
+ Node *PreviousSibling;
unsigned Kind : 16;
unsigned Role : 8;
unsigned Original : 1;
@@ -158,6 +161,8 @@
Node *getFirstChild() { return FirstChild; }
const Node *getFirstChild() const { return FirstChild; }
+ Node *getLastChild() { return LastChild; }
+ const Node *getLastChild() const { return LastChild; }
Leaf *findFirstLeaf();
const Leaf *findFirstLeaf() const {
@@ -193,6 +198,7 @@
friend class MutationsImpl;
Node *FirstChild = nullptr;
+ Node *LastChild = nullptr;
};
/// A list of Elements separated or terminated by a fixed token.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
