[SyntaxTree] Add reverse links to syntax Nodes.

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.

Differential Revision: https://reviews.llvm.org/D90240

1 files changed, 3 insertions, 4 deletions

diff --git a/clang/lib/Tooling/Syntax/BuildTree.cpp b/clang/lib/Tooling/Syntax/BuildTree.cpp
index 1975905..6777782 100644
--- a/clang/lib/Tooling/Syntax/BuildTree.cpp
+++ b/clang/lib/Tooling/Syntax/BuildTree.cpp
@@ -636,12 +636,11 @@ private:
           (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.