[SyntaxTree] Improve the signature of `replaceChildRangeLowLevel`.

[eduucaldas]

Summary

Previously replaceChildRangeLowLevel took the new child range as a Node* New. New was expected to have siblings attached already, and thus it was interpreted as a range. Additionally, the role of New and its siblings were expected to be set prior to calling the function. As a result the New argument broke the invariant New->Parent == nullptr <=> New->Role == Detached, at call site. We change the signature of replaceChildRangeLowLevel to take instead an ArrayRef<std::pair<Node*, NodeRole>>, and thus move the burden of setting siblings and roles from the user to the member function.

Moreover, replaceChildRangeLowLevel returns now a vector of the replaced range, following the "law of useful returns". Previously, in
order to reuse the replaced elements the user needed to get pointers to those elements and before calling the function.

We also fixed some minor bugs in addAfter, and added more asserts to the new replaceChildRangeLowLevel.

[eduucaldas]

Add reachability assertions

[eduucaldas]

Add role sanity-check. Introduce GetBegin().

[eduucaldas]

Fix whitespacing

[eduucaldas]

Add asserts to MutationsImpl::remove

clang/include/clang/Tooling/Syntax/Tree.h

private:
   /// EXPECTS: Role != Detached.
   void prependChildLowLevel(Node *Child, NodeRole Role);
   /// Like the previous overload, but does not set role for \p Child.
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
   friend class TreeBuilder;
   friend class FactoryImpl;
 
-  /// Replace a range of children [BeforeBegin->NextSibling, 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);
+  /// Replace a range of children between \p BeforeBegin  and \p End with a list
+  /// of new nodes and their corresponding `NodeRole`s \p NewRange. Only used by
+  /// MutationsImpl to implement higher-level mutation operations.
+  /// (!) `BeforeBegin` == nullptr => Replace everything before `End`.
+  /// (!) `End` == nullptr => Replace everything after `BeforeBegin`.
+  std::vector<std::pair<Node *, NodeRole>> replaceChildRangeLowLevel(
+      Node *BeforeBegin, Node *End,
+      ArrayRef<std::pair<syntax::Node *, NodeRole>> NewRange);
   friend class MutationsImpl;
 
   Node *FirstChild = nullptr;
 };
 
 /// A list of Elements separated or terminated by a fixed token.
 ///
 /// This type models the following grammar construct:

clang/lib/Tooling/Syntax/Mutations.cpp

 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
 #include <string>
 
 using namespace clang;
 
+static syntax::Node *findPrevious(syntax::Node *N) {
+  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 {
 public:
   /// Add a new node with a specified role.
   static void addAfter(syntax::Node *Anchor, syntax::Node *New, NodeRole Role) {
     assert(Anchor != nullptr);
+    assert(Anchor->Parent != nullptr);
     assert(New->Parent == nullptr);
     assert(New->NextSibling == nullptr);
-    assert(!New->isDetached());
+    assert(New->isDetached());
     assert(Role != NodeRole::Detached);
 
-    New->setRole(Role);
     auto *P = Anchor->getParent();
-    P->replaceChildRangeLowLevel(Anchor, Anchor, New);
+    P->replaceChildRangeLowLevel(Anchor, Anchor->getNextSibling(),
+                                 {{New, Role}});
 
     P->assertInvariants();
   }
 
   /// Replace the node, keeping the role.
   static void replace(syntax::Node *Old, syntax::Node *New) {
     assert(Old != nullptr);
     assert(Old->Parent != nullptr);
     assert(Old->canModify());
     assert(New->Parent == nullptr);
     assert(New->NextSibling == nullptr);
     assert(New->isDetached());
 
-    New->Role = Old->Role;
     auto *P = Old->getParent();
-    P->replaceChildRangeLowLevel(findPrevious(Old), Old->getNextSibling(), New);
+    P->replaceChildRangeLowLevel(findPrevious(Old), Old->getNextSibling(),
+                                 {{New, Old->getRole()}});
 
     P->assertInvariants();
   }
 
   /// Completely remove the node from its parent.
   static void remove(syntax::Node *N) {
     auto *P = N->getParent();
     P->replaceChildRangeLowLevel(findPrevious(N), N->getNextSibling(),
-                                 /*New=*/nullptr);
+                                 /*NewRange=*/{});
 
     P->assertInvariants();
     N->assertInvariants();
   }
-
-private:
-  static syntax::Node *findPrevious(syntax::Node *N) {
-    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");
-  }
 };
 
 void syntax::removeStatement(syntax::Arena &A, syntax::Statement *S) {
   assert(S);
   assert(S->canModify());
 
   if (isa<CompoundStatement>(S->getParent())) {
     // A child of CompoundStatement can just be safely removed.

clang/lib/Tooling/Syntax/Tree.cpp

void syntax::Tree::prependChildLowLevel(Node *Child) {
   assert(Child->NextSibling == nullptr);
   assert(Child->getRole() != NodeRole::Detached);
 
   Child->Parent = this;
   Child->NextSibling = this->FirstChild;
   this->FirstChild = Child;
 }
 
-void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
-                                             Node *New) {
-  assert(!BeforeBegin || BeforeBegin->Parent == this);
+std::vector<std::pair<syntax::Node *, syntax::NodeRole>>
+syntax::Tree::replaceChildRangeLowLevel(
+    Node *BeforeBegin, Node *End,
+    ArrayRef<std::pair<syntax::Node *, syntax::NodeRole>> NewRange) {
+  assert(!BeforeBegin || BeforeBegin->Parent == this &&
+                             "`BeforeBegin` is not a child of `this`");
+  assert(!End || End->Parent == this && "`End` is not a child of `this`");
 
 #ifndef NDEBUG
-  for (auto *N = New; N; N = N->getNextSibling()) {
+  for (const auto &NodeAndRole : NewRange) {
+    auto *N = NodeAndRole.first;
     assert(N->Parent == nullptr);
-    assert(N->getRole() != NodeRole::Detached && "Roles must be set");
-    // FIXME: sanity-check the role.
+    assert(N->getRole() == NodeRole::Detached && "Roles must not be set");
   }
+  // TODO: assert that both `BeforeBegin` and `End` are children of parent, and
+  // that `End` is "after" `BeforeBegin`.
+
 #endif
 
-  // Detach old nodes.
-  for (auto *N = !BeforeBegin ? FirstChild : BeforeBegin->getNextSibling();
-       N != End;) {
+  // Extract children to be replaced.
+  std::vector<std::pair<syntax::Node *, syntax::NodeRole>> ExtractedChildren;
+  auto *Begin = BeforeBegin ? BeforeBegin->getNextSibling() : FirstChild;
+  for (auto *N = Begin; N != End;) {
     auto *Next = N->NextSibling;
+    ExtractedChildren.push_back({N, N->getRole()});
 
     N->setRole(NodeRole::Detached);
     N->Parent = nullptr;
     N->NextSibling = nullptr;
+
     if (N->Original)
-      traverse(N, [&](Node *C) { C->Original = false; });
+      traverse(N, [](Node *C) { C->Original = false; });
 
     N = Next;
   }
 
-  // Attach new nodes.
-  if (BeforeBegin)
-    BeforeBegin->NextSibling = New ? New : End;
-  else
-    FirstChild = New ? New : End;
+  // If any modification occurred mark this and its ancestors as modified.
+  if (!ExtractedChildren.empty() || !NewRange.empty())
+    for (auto *T = this; T && T->Original; T = T->Parent)
+      T->Original = false;
+
+  if (NewRange.empty()) {
+    BeforeBegin->NextSibling = End;
+    return ExtractedChildren;
+  }
 
-  if (New) {
-    auto *Last = New;
-    for (auto *N = New; N != nullptr; N = N->getNextSibling()) {
-      Last = N;
-      N->Parent = this;
-    }
-    Last->NextSibling = End;
+  // `NewRange` becomes children of this Tree.
+  for (const auto &NodeAndRole : NewRange) {
+    NodeAndRole.first->setRole(NodeAndRole.second);
+    NodeAndRole.first->Parent = this;
+
+  // `NewRange` nodes are siblings.
+  for (const auto *It = NewRange.begin(); It != std::prev(NewRange.end());
+       ++It) {
+    auto *Node = It->first;
+    auto *Next = std::next(It)->first;
+    Node->NextSibling = Next;
   }
+  // Attach new children to the end of the replaced range.
+  NewRange.back().first->NextSibling = End;
 
-  // Mark the node as modified.
-  for (auto *T = this; T && T->Original; T = T->Parent)
-    T->Original = false;
+  // New children are now the beginning of the replaced range.
+  auto *NewBegin = NewRange.front().first;
+  if (BeforeBegin)
+    BeforeBegin->NextSibling = NewBegin;
+  else
+    FirstChild = NewBegin;
+
+  return ExtractedChildren;
 }
 
 namespace {
 static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L,
                      const SourceManager &SM) {
   assert(L);
   const auto *Token = L->getToken();
   assert(Token);