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
@@ -185,11 +185,14 @@
   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;
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,6 +23,17 @@
 
 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 {
@@ -30,14 +41,15 @@
   /// 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();
   }
@@ -51,34 +63,26 @@
     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) {
+    assert(N != nullptr);
+    assert(N->Parent != nullptr);
+    assert(N->canModify());
+
     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) {
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
@@ -92,50 +92,84 @@
   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");
+
+    auto Role = NodeAndRole.second;
+    assert(Role != NodeRole::Detached);
   }
+
+  auto Reachable = [](Node *From, Node *N) {
+    if (!N)
+      return true;
+    for (auto *It = From; It; It = It->NextSibling)
+      if (It == N)
+        return true;
+    return false;
+  };
+  assert(Reachable(FirstChild, BeforeBegin) &&
+         "`BeforeBegin` is not reachable");
+  assert(Reachable(BeforeBegin ? BeforeBegin->NextSibling : FirstChild, End) &&
+         "`End` is not after `BeforeBegin`");
 #endif
 
-  // Detach old nodes.
-  for (auto *N = !BeforeBegin ? FirstChild : BeforeBegin->getNextSibling();
-       N != End;) {
+  auto GetBegin = [&BeforeBegin, &FirstChild = this->FirstChild]() -> Node *& {
+    return BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  };
+
+  // Extract old nodes.
+  std::vector<std::pair<syntax::Node *, syntax::NodeRole>> ExtractedChildren;
+  for (auto *N = GetBegin(); 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 them.
+  if (!ExtractedChildren.empty() || !NewRange.empty())
+    for (auto *T = this; T && T->Original; T = T->Parent)
+      T->Original = false;
 
-  if (New) {
-    auto *Last = New;
-    for (auto *N = New; N != nullptr; N = N->getNextSibling()) {
-      Last = N;
-      N->Parent = this;
-    }
-    Last->NextSibling = End;
+  // Attach new children to the replaced range.
+
+  if (NewRange.empty()) {
+    GetBegin() = End;
+    return ExtractedChildren;
+  }
+  GetBegin() = NewRange.front().first;
+  NewRange.back().first->NextSibling = End;
+
+  for (const auto &NodeAndRole : NewRange) {
+    NodeAndRole.first->setRole(NodeAndRole.second);
+    NodeAndRole.first->Parent = this;
+  }
+
+  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;
   }
 
-  // Mark the node as modified.
-  for (auto *T = this; T && T->Original; T = T->Parent)
-    T->Original = false;
+  return ExtractedChildren;
 }
 
 namespace {