diff --git a/clang/include/clang/Tooling/Syntax/Tree.h b/clang/include/clang/Tooling/Syntax/Tree.h --- a/clang/include/clang/Tooling/Syntax/Tree.h +++ b/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 class ChildIteratorBase - : public llvm::iterator_facade_base { + : 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(this); } + DerivedT &operator--() { + N = N->getPreviousSibling(); + return *static_cast(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. diff --git a/clang/lib/Tooling/Syntax/BuildTree.cpp b/clang/lib/Tooling/Syntax/BuildTree.cpp --- a/clang/lib/Tooling/Syntax/BuildTree.cpp +++ b/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. diff --git a/clang/lib/Tooling/Syntax/Mutations.cpp b/clang/lib/Tooling/Syntax/Mutations.cpp --- a/clang/lib/Tooling/Syntax/Mutations.cpp +++ b/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(); diff --git a/clang/lib/Tooling/Syntax/Synthesis.cpp b/clang/lib/Tooling/Syntax/Synthesis.cpp --- a/clang/lib/Tooling/Syntax/Synthesis.cpp +++ b/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> lexBuffer(syntax::Arena &A, std::unique_ptr 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; diff --git a/clang/lib/Tooling/Syntax/Tree.cpp b/clang/lib/Tooling/Syntax/Tree.cpp --- a/clang/lib/Tooling/Syntax/Tree.cpp +++ b/clang/lib/Tooling/Syntax/Tree.cpp @@ -57,8 +57,9 @@ } syntax::Node::Node(NodeKind Kind) - : Parent(nullptr), NextSibling(nullptr), Kind(static_cast(Kind)), - Role(0), Original(false), CanModify(false) { + : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr), + Kind(static_cast(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(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(&C)) - Last = L; - else if (const auto *L = cast(C).findLastLeaf()) - Last = L; +syntax::Leaf *syntax::Tree::findLastLeaf() { + for (auto *C = getLastChild(); C; C = C->getPreviousSibling()) { + if (auto *L = dyn_cast(C)) + return L; + if (auto *L = cast(C)->findLastLeaf()) + return L; } - return Last; + return nullptr; } const syntax::Node *syntax::Tree::findChild(NodeRole R) const {