eduucaldas updated this revision to Diff 301255.
eduucaldas added a comment.
Rebase to include ChildIterator patch.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D90240/new/
https://reviews.llvm.org/D90240
Files:
clang/include/clang/Tooling/Syntax/Tree.h
clang/lib/Tooling/Syntax/BuildTree.cpp
clang/lib/Tooling/Syntax/Mutations.cpp
clang/lib/Tooling/Syntax/Synthesis.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);
}
@@ -74,6 +75,30 @@
return N->getKind() > 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->getRole() == NodeRole::Detached);
assert(Role != NodeRole::Detached);
@@ -85,22 +110,26 @@
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;
}
-void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
+void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End,
Node *New) {
- assert((!BeforeBegin || BeforeBegin->Parent == this) &&
- "`BeforeBegin` is not a child of `this`.");
+ assert(((!Begin && !FirstChild) || 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`.");
- Node *&Begin = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
-
#ifndef NDEBUG
for (auto *N = New; N; N = N->NextSibling) {
assert(N->Parent == nullptr);
@@ -116,18 +145,21 @@
return true;
return false;
};
- assert(Reachable(FirstChild, BeforeBegin) &&
- "`BeforeBegin` is not reachable.");
- assert(Reachable(Begin, End) && "`End` is not after `BeforeBegin`.");
+ assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable.");
+ assert(Reachable(Begin, End) && "`End` is not after `Begin`.");
#endif
- if (!New && Begin == End)
+ if (!New && (!Begin || Begin == End))
return;
// Mark modification.
for (auto *T = this; T && T->Original; T = T->Parent)
T->Original = false;
+ // Point to node before the range to be removed, to later insert the `New`
+ // range after it.
+ auto *BeforeBegin = Begin ? Begin->PreviousSibling : nullptr;
+
// Detach old nodes.
for (auto *N = Begin; N != End;) {
auto *Next = N->NextSibling;
@@ -135,24 +167,33 @@
N->setRole(NodeRole::Detached);
N->Parent = nullptr;
N->NextSibling = nullptr;
+ N->PreviousSibling = nullptr;
if (N->Original)
traverse(N, [](Node *C) { C->Original = false; });
N = Next;
}
+ // Attach new range.
+ auto *&NewBegin = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+ auto *&NewLast = End ? End->PreviousSibling : LastChild;
+
if (!New) {
- Begin = End;
+ NewBegin = End;
+ NewLast = BeforeBegin;
return;
}
- // Attach new nodes.
- Begin = New;
- auto *Last = New;
+
+ New->PreviousSibling = BeforeBegin;
+ NewBegin = New;
+
+ Node *LastInNew;
for (auto *N = New; N != nullptr; N = N->NextSibling) {
- Last = N;
+ LastInNew = N;
N->Parent = this;
}
- Last->NextSibling = End;
+ LastInNew->NextSibling = End;
+ NewLast = LastInNew;
}
namespace {
@@ -245,9 +286,14 @@
return;
for (const Node &C : T->getChildren()) {
if (T->isOriginal())
- assert(C.isOriginal());
- assert(!C.isDetached());
- assert(C.getParent() == 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);
@@ -281,15 +327,14 @@
return nullptr;
}
-const syntax::Leaf *syntax::Tree::findLastLeaf() const {
- const syntax::Leaf *Last = nullptr;
- for (const Node &C : getChildren()) {
- if (const auto *L = dyn_cast<syntax::Leaf>(&C))
- Last = L;
- else if (const auto *L = cast<syntax::Tree>(C).findLastLeaf())
- Last = L;
+syntax::Leaf *syntax::Tree::findLastLeaf() {
+ for (auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
+ if (auto *L = dyn_cast<syntax::Leaf>(C))
+ return L;
+ if (auto *L = cast<syntax::Tree>(C)->findLastLeaf())
+ return L;
}
- return Last;
+ return nullptr;
}
const syntax::Node *syntax::Tree::findChild(NodeRole R) const {
Index: clang/lib/Tooling/Syntax/Synthesis.cpp
===================================================================
--- clang/lib/Tooling/Syntax/Synthesis.cpp
+++ clang/lib/Tooling/Syntax/Synthesis.cpp
@@ -21,6 +21,10 @@
syntax::NodeRole R) {
T->prependChildLowLevel(Child, R);
}
+ static void appendChildLowLevel(syntax::Tree *T, syntax::Node *Child,
+ syntax::NodeRole R) {
+ T->appendChildLowLevel(Child, R);
+ }
static std::pair<FileID, ArrayRef<Token>>
lexBuffer(syntax::Arena &A, std::unique_ptr<llvm::MemoryBuffer> Buffer) {
@@ -196,8 +200,9 @@
syntax::NodeKind K) {
auto *T = allocateTree(A, K);
FactoryImpl::setCanModify(T);
- for (auto ChildIt = Children.rbegin(); ChildIt != Children.rend(); ++ChildIt)
- FactoryImpl::prependChildLowLevel(T, ChildIt->first, ChildIt->second);
+ for (const auto *ChildIt = Children.begin(); ChildIt != Children.end();
+ ++ChildIt)
+ FactoryImpl::appendChildLowLevel(T, ChildIt->first, ChildIt->second);
T->assertInvariants();
return T;
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,12 +33,14 @@
assert(Anchor->Parent != nullptr);
assert(New->Parent == nullptr);
assert(New->NextSibling == nullptr);
+ assert(New->PreviousSibling == nullptr);
assert(New->isDetached());
assert(Role != NodeRole::Detached);
New->setRole(Role);
auto *P = Anchor->getParent();
- P->replaceChildRangeLowLevel(Anchor, Anchor->getNextSibling(), New);
+ P->replaceChildRangeLowLevel(Anchor->getNextSibling(),
+ Anchor->getNextSibling(), New);
P->assertInvariants();
}
@@ -63,11 +52,12 @@
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, 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, N->getNextSibling(),
/*New=*/nullptr);
P->assertInvariants();
Index: clang/lib/Tooling/Syntax/BuildTree.cpp
===================================================================
--- clang/lib/Tooling/Syntax/BuildTree.cpp
+++ clang/lib/Tooling/Syntax/BuildTree.cpp
@@ -637,11 +637,11 @@
"fold crosses boundaries of existing subtrees");
// We need to go in reverse order, because we can only prepend.
- for (auto It = EndChildren; It != BeginChildren; --It) {
- auto *C = std::prev(It)->second;
+ for (auto It = BeginChildren; It != EndChildren; ++It) {
+ auto *C = It->second;
if (C->getRole() == NodeRole::Detached)
C->setRole(NodeRole::Unknown);
- Node->prependChildLowLevel(C);
+ Node->appendChildLowLevel(C);
}
// Mark that this node came from the AST and is backed by the source code.
Index: clang/include/clang/Tooling/Syntax/Tree.h
===================================================================
--- clang/include/clang/Tooling/Syntax/Tree.h
+++ clang/include/clang/Tooling/Syntax/Tree.h
@@ -118,6 +118,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;
@@ -144,6 +146,7 @@
Tree *Parent;
Node *NextSibling;
+ Node *PreviousSibling;
unsigned Kind : 16;
unsigned Role : 8;
unsigned Original : 1;
@@ -168,8 +171,8 @@
/// Not invalidated by tree mutations (holds a stable node pointer).
template <typename DerivedT, typename NodeT>
class ChildIteratorBase
- : public llvm::iterator_facade_base<DerivedT, std::forward_iterator_tag,
- NodeT> {
+ : public llvm::iterator_facade_base<
+ DerivedT, std::bidirectional_iterator_tag, NodeT> {
protected:
NodeT *N = nullptr;
using Base = ChildIteratorBase;
@@ -184,6 +187,10 @@
N = N->getNextSibling();
return *static_cast<DerivedT *>(this);
}
+ DerivedT &operator--() {
+ N = N->getPreviousSibling();
+ return *static_cast<DerivedT *>(this);
+ }
/// Truthy if valid (not past-the-end).
/// This allows: if (auto It = find_if(N.children(), ...) )
@@ -197,6 +204,8 @@
Node *getFirstChild() { return FirstChild; }
const Node *getFirstChild() const { return FirstChild; }
+ Node *getLastChild() { return LastChild; }
+ const Node *getLastChild() const { return LastChild; }
const Leaf *findFirstLeaf() const;
Leaf *findFirstLeaf() {
@@ -235,25 +244,30 @@
using Node::Node;
private:
- /// Prepend \p Child to the list of children and and sets the parent pointer.
+ /// Prepend \p Child to the list of children and sets the parent pointer.
/// A very low-level operation that does not check any invariants, only used
/// by TreeBuilder and FactoryImpl.
/// EXPECTS: Role != Detached.
void prependChildLowLevel(Node *Child, NodeRole Role);
- /// Like the previous overload, but does not set role for \p Child.
+ /// Similar but appends.
+ void appendChildLowLevel(Node *Child, NodeRole Role);
+
+ /// Like the previous overloads, but does not set role for \p Child.
/// EXPECTS: Child->Role != Detached
void prependChildLowLevel(Node *Child);
+ void appendChildLowLevel(Node *Child);
friend class TreeBuilder;
friend class FactoryImpl;
- /// Replace a range of children [BeforeBegin->NextSibling, End) with a list of
+ /// Replace a range of children [Begin, End) with a list of
/// new nodes starting at \p New.
/// Only used by MutationsImpl to implement higher-level mutation operations.
/// (!) \p New can be null to model removal of the child range.
- void replaceChildRangeLowLevel(Node *BeforeBegin, Node *End, Node *New);
+ void replaceChildRangeLowLevel(Node *Begin, Node *End, Node *New);
friend class MutationsImpl;
Node *FirstChild = nullptr;
+ Node *LastChild = nullptr;
};
// Provide missing non_const == const overload.
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
