[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

4 files changed, 84 insertions, 46 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.
diff --git a/clang/lib/Tooling/Syntax/Mutations.cpp b/clang/lib/Tooling/Syntax/Mutations.cpp
index 8def1c7..f8a6522 100644
--- 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 @@ public:
     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 @@ public:
     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 @@ public:
     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
index 73452b7..ef64928 100644
--- a/clang/lib/Tooling/Syntax/Synthesis.cpp
+++ b/clang/lib/Tooling/Syntax/Synthesis.cpp
@@ -21,6 +21,10 @@ public:
                                    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,8 @@ syntax::Tree *clang::syntax::createTree(
     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
index 204c83e..fca2be5 100644
--- a/clang/lib/Tooling/Syntax/Tree.cpp
+++ b/clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@ bool syntax::Leaf::classof(const Node *N) {
 }
 
 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 @@ bool syntax::Tree::classof(const Node *N) {
   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, NodeRole Role) {
 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 @@ void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
         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 @@ void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
   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 @@ void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
     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 @@ void syntax::Node::assertInvariants() const {
       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);
@@ -282,14 +328,13 @@ const syntax::Leaf *syntax::Tree::findFirstLeaf() const {
 }
 
 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;
+  for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
+    if (const auto *L = dyn_cast<syntax::Leaf>(C))
+      return L;
+    if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf())
+      return L;
   }
-  return Last;
+  return nullptr;
 }
 
 const syntax::Node *syntax::Tree::findChild(NodeRole R) const {