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; @@ -197,6 +200,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() { @@ -236,25 +241,32 @@ using Node::Node; private: - /// Prepend \p Child to the list of children and and sets the parent pointer. + /// Append \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 appendChildLowLevel(Node *Child, NodeRole Role); + /// Similar but prepends. void prependChildLowLevel(Node *Child, NodeRole Role); - /// Like the previous overload, but does not set role for \p Child. + + /// Like the previous overloads, but does not set role for \p Child. /// EXPECTS: Child->Role != Detached + void appendChildLowLevel(Node *Child); void prependChildLowLevel(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); + /// (!) \p End can be null to model one past the end. + /// (!) \p Begin can be null to model an append. + 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 @@ -636,12 +636,11 @@ (EndChildren == Trees.end() || EndChildren->first == Tokens.end()) && "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,8 @@ 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 &Child : Children) + FactoryImpl::appendChildLowLevel(T, Child.first, Child.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 || 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,9 +145,8 @@ 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) @@ -128,6 +156,10 @@ 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 = 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 *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild; + auto *&NewLast = End ? End->PreviousSibling : LastChild; + if (!New) { - Begin = End; + NewFirst = End; + NewLast = BeforeBegin; return; } - // Attach new nodes. - Begin = New; - auto *Last = New; + + New->PreviousSibling = BeforeBegin; + NewFirst = 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 { @@ -248,6 +289,11 @@ 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); @@ -282,14 +328,13 @@ } 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; + for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) { + if (const auto *L = dyn_cast(C)) + return L; + if (const auto *L = cast(C)->findLastLeaf()) + return L; } - return Last; + return nullptr; } const syntax::Node *syntax::Tree::findChild(NodeRole R) const {