[Syntax] Allow to mutate syntax trees

[ilya-biryukov]

Summary

This patch adds facilities to mutate the syntax trees and produce
corresponding text replacements.

The public interface of the syntax library now includes facilities to:

1. perform type-safe modifications of syntax trees,
2. compute textual replacements to apply the modifications,
3. create syntax trees not backed by the source code.

For each of the three, we only add a few example transformations in this
patch to illustrate the idea, support for more kinds of nodes and
transformations will be done in follow-up patches.

The high-level mutation operations are implemented on top of operations
that allow to arbitrarily change the trees. They are considered to be
implementation details and are not available to the users of the
library.

[gribozavr2]

Generally looks good, just nitpicks.

clang/include/clang/Tooling/Syntax/BuildTree.h

24

"Creates syntax trees..."

25

Why a class to contain static functions? Is it like a namespace, or is there some future design intent?..

Or is it for the friendship?

clang/include/clang/Tooling/Syntax/Mutations.h

27

Removes a statement, or replaces it with an empty statement where one is required syntactically.

(provide an explanation why it may sometimes use an empty statement -- I think it is not obvious)

34

Please add the newline.

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

87

Please clarify what happens to mixed content (some subtrees are from the source code, some are synthesized).

90

Please also document what isOriginal means for syntax nodes that were moved within the tree (re-parented). For example, think of a refactoring that swaps "then" and "else" branches of an "if" statement.

126

Is it worth eagerly computing the "can modify" bit? Mapping expanded tokens to spelled is log(n) after all, and doing it for every syntax node can add up to nontrivial costs...

174

s/Before/BeforeBegin/? This way begin/end pairing is more obvious.

clang/lib/Tooling/Syntax/BuildTree.cpp

661

I can imagine that both building the syntax tree from the AST, and synthesizing syntax trees from thin air will eventually grow pretty long. So I'd like to suggest to split synthesis of syntax trees into a separate file, even though it will be pretty short today.

676

Please add the newline below.

clang/lib/Tooling/Syntax/ComputeReplacements.cpp

21

I'd probably change this struct into a function with a local lambda... I feel like it is weird to call a constructor just for the side-effects.

54

BeginOfSpan/EndOfSpan or SpanBegin/SpanEnd sound more natural to me.

80

Why not a reference for the TU?

87

s/RemovedRange/ReplacedRange/ ?

91

Unclear whether this comment is explaining the assumption, or explaining the assert.

"Check that the removed range points..."

93

This assertion duplicates the one in rangeOfExpanded; do we need to duplicate?

The code in this function does not depend on the assumption that tokens are expanded tokens; it is rangeOfExpanded that does.

If you decide to remove the assertion here, please move the comment from here into that function.

125

Please add the newline.

clang/lib/Tooling/Syntax/Tree.cpp

89

Please mention in the doc comment that New can be null.

clang/unittests/Tooling/Syntax/TreeTest.cpp

57

Seems like these first/last helpers should be methods on syntax::Node.

66

The first and the last tokens are not necessarily from the same buffer...

130

"deepest node" (singular)

698

I know this is 100% bikeshedding, but why "X"? I'd suggest "I" for "immutable". Feel free to ignore this comment though...

703

Could you also do something like:

#define OPEN {
#define CLOSE }

void test1() {
  OPEN
    1;
  CLOSE
}
void test1() {
  OPEN
    1;
  }
}

[ilya-biryukov]

• Addressed most comments
• Rebased onto HEAD

[ilya-biryukov]

clang/include/clang/Tooling/Syntax/BuildTree.h

25

Good point, this pattern is terrible.
It is for friendship, but this is supposed to be an implementation detail, therefore shouldn't affect user interface.

I turned these into free-standing functions. Not sure if we should group those into a namespace for simpler discoverability via code completion (although one can just do syntax::create^ to get the same effect now)

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

126

I would expect this bit to be requested quite often, so I think this would actually pay off in the long run. Requesting this bit should be very cheap.

Note that we do quite a bit of O(log N) searches in the same code that sets CanModify bit, so it does not actually make the complexity worse, but definitely makes the constant larger.

If this starts being the bottleneck (I bet this will happen eventually), I believe we can compute it eagerly with O(1) amortized cost. That would involve traversing the AST in the true source code order, which will require tweaking the RecursiveASTVisitor and is much easier done when we have good test coverage with existing implementation.

clang/lib/Tooling/Syntax/BuildTree.cpp

661

Good point.
I've moved only the implementation for now, declaration of synthesis functions are still in BuildTree.h as it seems small enough for now.

I can totally imagine us moving those to a separate file later, though.

clang/lib/Tooling/Syntax/ComputeReplacements.cpp

80

All accessors on syntax tree return pointers (almost everything can be null), so using pointers everywhere just makes the code more uniform.

This one does look a bit different, though, agree that using a reference in this public API is probably more natural.

93

Good point, thanks. Moved the comment to rangeOfExpanded, we don't need to assert in both places.

[merge_guards_bot]

Unit tests: pass. 60958 tests passed, 0 failed and 726 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[ilya-biryukov]

• Fix a header guard
• Make firstLeaf and lastLeaf methods inside Tree
• Mark non-modifiable nodes with I (for immutable)

[ilya-biryukov]

clang/unittests/Tooling/Syntax/TreeTest.cpp

57

Good point. Done.

66

They are for nodes with isOriginal() == true. I've added an assertion.
Exactly the reason why this method is not a good fit for public API, but ok to have in tests.

703

Funnily enough, this causes an assertion failure, because binary-searching with isBeforeInTranslationUnit finds { expanded from OPEN instead of 1 when building a syntax tree.

I'll make use of a hash table for searching tokens by location and add the test in the follow-up patch.

[ilya-biryukov]

clang/unittests/Tooling/Syntax/TreeTest.cpp

703

c1bbefef9d36e84e469513374ef404b9e354b262 adds the corresponding test.

[gribozavr2]

Updated version LGTM, thanks!

[Ka-Ka]

clang/lib/Tooling/Syntax/Mutations.cpp

74

This line introduce a buildbot fail:

/home/buildbots/ppc64be-clang-multistage-test/clang-ppc64be-multistage/llvm/clang/lib/Tooling/Syntax/Mutations.cpp:74:13: warning: unused variable ‘Parent’ [-Wunused-variable]

clang/lib/Tooling/Syntax/Tokens.cpp

70

This line introduce a buildbot failure:

/home/buildbots/ppc64be-clang-multistage-test/clang-ppc64be-multistage/llvm/clang/lib/Tooling/Syntax/Tokens.cpp:70:53: warning: suggest parentheses around ‘&&’ within ‘||’ [-Wparentheses]

[gribozavr2]

@Ka-Ka Thanks for bringing it to our attention! I fixed these warnings in:

https://github.com/llvm/llvm-project/commit/9caf12e8495c1106dd3d1079892ce4f39f91b7d2
https://github.com/llvm/llvm-project/commit/73f423e739bcb9bee7b73f05d4bcd50782013a8c

[ilya-biryukov]

Thanks for the fixes!

clang/include/clang/Tooling/Syntax/BuildTree.h

 //===- BuildTree.h - build syntax trees -----------------------*- C++ -*-=====//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // Functions to construct a syntax tree from an AST.
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_H
 #define LLVM_CLANG_TOOLING_SYNTAX_TREE_H
 
 #include "clang/AST/Decl.h"
+#include "clang/Basic/TokenKinds.h"
 #include "clang/Tooling/Syntax/Nodes.h"
+#include "clang/Tooling/Syntax/Tree.h"
 
 namespace clang {
 namespace syntax {
 
 /// Build a syntax tree for the main file.
 syntax::TranslationUnit *buildSyntaxTree(Arena &A,
                                          const clang::TranslationUnitDecl &TU);
+
+// Create syntax trees from subtrees not backed by the source code.
+
+clang::syntax::Leaf *createPunctuation(clang::syntax::Arena &A,
+                                       clang::tok::TokenKind K);
+clang::syntax::EmptyStatement *createEmptyStatement(clang::syntax::Arena &A);
+
 } // namespace syntax
 } // namespace clang
 #endif

clang/include/clang/Tooling/Syntax/Mutations.h

+//===- Mutations.h - mutate syntax trees --------------------*- C++ ---*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Defines high-level APIs for transforming syntax trees and producing the
+// corresponding textual replacements.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_MUTATIONS_H
+#define LLVM_CLANG_TOOLING_SYNTAX_MUTATIONS_H
+
+#include "clang/Tooling/Core/Replacement.h"
+#include "clang/Tooling/Syntax/Nodes.h"
+#include "clang/Tooling/Syntax/Tree.h"
+
+namespace clang {
+namespace syntax {
+
+/// Computes textual replacements required to mimic the tree modifications made
+/// to the syntax tree.
+tooling::Replacements computeReplacements(const Arena &A,
+                                          const syntax::TranslationUnit &TU);
+
+/// Removes a statement or replaces it with an empty statement where one is
+/// required syntactically. E.g., in the following example:
+///     if (cond) { foo(); } else bar();
+/// One can remove `foo();` completely and to remove `bar();` we would need to
+/// replace it with an empty statement.
+/// EXPECTS: S->canModify() == true
+void removeStatement(syntax::Arena &A, syntax::Statement *S);
+
+} // namespace syntax
+} // namespace clang
+
+#endif

clang/include/clang/Tooling/Syntax/Tokens.h

struct FileRange {
   /// Check \p Offset is inside the range or equal to its endpoint.
   bool touches(unsigned Offset) const {
     return Begin <= Offset && Offset <= End;
   }
 
   /// Gets the substring that this FileRange refers to.
   llvm::StringRef text(const SourceManager &SM) const;
 
+  /// Convert to the clang range. The returned range is always a char range,
+  /// never a token range.
+  CharSourceRange toCharRange(const SourceManager &SM) const;
+
   friend bool operator==(const FileRange &L, const FileRange &R) {
     return std::tie(L.File, L.Begin, L.End) == std::tie(R.File, R.Begin, R.End);
   }
   friend bool operator!=(const FileRange &L, const FileRange &R) {
     return !(L == R);
   }
 
 private:

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

private:
   /// IDs and storage for additional tokenized files.
   llvm::DenseMap<FileID, std::vector<syntax::Token>> ExtraTokens;
   /// Keeps all the allocated nodes and their intermediate data structures.
   llvm::BumpPtrAllocator Allocator;
 };
 
 class Tree;
 class TreeBuilder;
+class FactoryImpl;
+class MutationsImpl;
+
 enum class NodeKind : uint16_t;
 enum class NodeRole : uint8_t;
 
 /// A node in a syntax tree. Each node is either a Leaf (representing tokens) or
 /// a Tree (representing language constructrs).
 class Node {
 public:
   /// Newly created nodes are detached from a tree, parent and sibling links are
   /// set when the node is added as a child to another one.
   Node(NodeKind Kind);
 
   NodeKind kind() const { return static_cast<NodeKind>(Kind); }
   NodeRole role() const { return static_cast<NodeRole>(Role); }
 
+  /// Whether the node is detached from a tree, i.e. does not have a parent.
+  bool isDetached() const;
+  /// Whether the node was created from the AST backed by the source code
+  /// rather than added later through mutation APIs or created with factory
+  /// functions.
+  /// When this flag is true, all subtrees are also original.
+  /// This flag is set to false on any modifications to the node or any of its
+  /// subtrees, even if this simply involves swapping existing subtrees.
+  bool isOriginal() const { return Original; }
+  /// If this function return false, the tree cannot be modified because there
+  /// is no reasonable way to produce the corresponding textual replacements.
+  /// This can happen when the node crosses macro expansion boundaries.
+  ///
+  /// Note that even if the node is not modifiable, its child nodes can be
+  /// modifiable.
+  bool canModify() const { return CanModify; }
+
   const Tree *parent() const { return Parent; }
   Tree *parent() { return Parent; }
 
   const Node *nextSibling() const { return NextSibling; }
   Node *nextSibling() { return NextSibling; }
 
   /// Dumps the structure of a subtree. For debugging and testing purposes.
   std::string dump(const Arena &A) const;
   /// Dumps the tokens forming this subtree.
   std::string dumpTokens(const Arena &A) const;
 
 private:
   // Tree is allowed to change the Parent link and Role.
   friend class Tree;
+  // TreeBuilder is allowed to set the Original and CanModify flags.
+  friend class TreeBuilder;
+  // MutationsImpl sets roles and CanModify flag.
+  friend class MutationsImpl;
 
   Tree *Parent;
   Node *NextSibling;
   unsigned Kind : 16;
   unsigned Role : 8;
+  unsigned Original : 1;
+  unsigned CanModify : 1;
 };
 
 /// A leaf node points to a single token inside the expanded token stream.
 class Leaf final : public Node {
 public:
   Leaf(const syntax::Token *T);
   static bool classof(const Node *N);
 
   const syntax::Token *token() const { return Tok; }
 
 private:
   const syntax::Token *Tok;
 };
 
 /// A node that has children and represents a syntactic language construct.
 class Tree : public Node {
 public:
   using Node::Node;
   static bool classof(const Node *N);
 
   Node *firstChild() { return FirstChild; }
   const Node *firstChild() const { return FirstChild; }
 
+  Leaf *firstLeaf();
+  const Leaf *firstLeaf() const {
+    return const_cast<Tree *>(this)->firstLeaf();
+  }
+
+  Leaf *lastLeaf();
+  const Leaf *lastLeaf() const { return const_cast<Tree *>(this)->lastLeaf(); }
+
 protected:
   /// Find the first node with a corresponding role.
   syntax::Node *findChild(NodeRole R);
 
 private:
   /// Prepend \p Child to the list of children and and sets the parent pointer.
   /// A very low-level operation that does not check any invariants, only used
-  /// by TreeBuilder.
+  /// by TreeBuilder and FactoryImpl.
   /// EXPECTS: Role != NodeRoleDetached.
   void prependChildLowLevel(Node *Child, NodeRole Role);
   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);
+  friend class MutationsImpl;
 
   Node *FirstChild = nullptr;
 };
 
 } // namespace syntax
 } // namespace clang
 
 #endif

clang/lib/Tooling/Syntax/BuildTree.cpp

 #include "clang/Tooling/Syntax/Tree.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
 
 using namespace clang;
 
 LLVM_ATTRIBUTE_UNUSED
 static bool isImplicitExpr(clang::Expr *E) { return E->IgnoreImplicit() != E; }
 
public:
 
   /// Finish building the tree and consume the root node.
   syntax::TranslationUnit *finalize() && {
     auto Tokens = Arena.tokenBuffer().expandedTokens();
     assert(!Tokens.empty());
     assert(Tokens.back().kind() == tok::eof);
 
     // Build the root of the tree, consuming all the children.
-    Pending.foldChildren(Tokens.drop_back(),
+    Pending.foldChildren(Arena, Tokens.drop_back(),
                          new (Arena.allocator()) syntax::TranslationUnit);
 
     return cast<syntax::TranslationUnit>(std::move(Pending).finalize());
   }
 
   /// getRange() finds the syntax tokens corresponding to the passed source
   /// locations.
   /// \p First is the start position of the first token and \p Last is the start
private:
   ///
   /// Ensures that added nodes properly nest and cover the whole token stream.
   struct Forest {
     Forest(syntax::Arena &A) {
       assert(!A.tokenBuffer().expandedTokens().empty());
       assert(A.tokenBuffer().expandedTokens().back().kind() == tok::eof);
       // Create all leaf nodes.
       // Note that we do not have 'eof' in the tree.
-      for (auto &T : A.tokenBuffer().expandedTokens().drop_back())
-        Trees.insert(Trees.end(),
-                     {&T, NodeAndRole{new (A.allocator()) syntax::Leaf(&T)}});
+      for (auto &T : A.tokenBuffer().expandedTokens().drop_back()) {
+        auto *L = new (A.allocator()) syntax::Leaf(&T);
+        L->Original = true;
+        L->CanModify = A.tokenBuffer().spelledForExpanded(T).hasValue();
+        Trees.insert(Trees.end(), {&T, NodeAndRole{L}});
+      }
     }
 
     ~Forest() { assert(DelayedFolds.empty()); }
 
     void assignRole(llvm::ArrayRef<syntax::Token> Range,
                     syntax::NodeRole Role) {
       assert(!Range.empty());
       auto It = Trees.lower_bound(Range.begin());
       assert(It != Trees.end() && "no node found");
       assert(It->first == Range.begin() && "no child with the specified range");
       assert((std::next(It) == Trees.end() ||
               std::next(It)->first == Range.end()) &&
              "no child with the specified range");
       It->second.Role = Role;
     }
 
     /// Add \p Node to the forest and attach child nodes based on \p Tokens.
-    void foldChildren(llvm::ArrayRef<syntax::Token> Tokens,
+    void foldChildren(const syntax::Arena &A,
+                      llvm::ArrayRef<syntax::Token> Tokens,
                       syntax::Tree *Node) {
       // Execute delayed folds inside `Tokens`.
       auto BeginExecuted = DelayedFolds.lower_bound(Tokens.begin());
       auto It = BeginExecuted;
       for (; It != DelayedFolds.end() && It->second.End <= Tokens.end(); ++It)
-        foldChildrenEager(llvm::makeArrayRef(It->first, It->second.End),
+        foldChildrenEager(A, llvm::makeArrayRef(It->first, It->second.End),
                           It->second.Node);
       DelayedFolds.erase(BeginExecuted, It);
 
       // Attach children to `Node`.
-      foldChildrenEager(Tokens, Node);
+      foldChildrenEager(A, Tokens, Node);
     }
 
     /// Schedule a call to `foldChildren` that will only be executed when
     /// containing node is folded. The range of delayed nodes can be extended by
     /// calling `extendDelayedFold`. Only one delayed node for each starting
     /// token is allowed.
     void foldChildrenDelayed(llvm::ArrayRef<syntax::Token> Tokens,
                              syntax::Tree *Node) {
std::string str(const syntax::Arena &A) const {
         R += It->second.Node->dump(A);
       }
       return R;
     }
 
   private:
     /// Implementation detail of `foldChildren`, does acutal folding ignoring
     /// delayed folds.
-    void foldChildrenEager(llvm::ArrayRef<syntax::Token> Tokens,
+    void foldChildrenEager(const syntax::Arena &A,
+                           llvm::ArrayRef<syntax::Token> Tokens,
                            syntax::Tree *Node) {
       assert(Node->firstChild() == nullptr && "node already has children");
 
       auto *FirstToken = Tokens.begin();
       auto BeginChildren = Trees.lower_bound(FirstToken);
       assert((BeginChildren == Trees.end() ||
               BeginChildren->first == FirstToken) &&
              "fold crosses boundaries of existing subtrees");
       auto EndChildren = Trees.lower_bound(Tokens.end());
       assert(
           (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)
         Node->prependChildLowLevel(std::prev(It)->second.Node,
                                    std::prev(It)->second.Role);
 
+      // Mark that this node came from the AST and is backed by the source code.
+      Node->Original = true;
+      Node->CanModify = A.tokenBuffer().spelledForExpanded(Tokens).hasValue();
+
       Trees.erase(BeginChildren, EndChildren);
       Trees.insert({FirstToken, NodeAndRole(Node)});
     }
     /// A with a role that should be assigned to it when adding to a parent.
     struct NodeAndRole {
       explicit NodeAndRole(syntax::Node *Node)
           : Node(Node), Role(NodeRole::Unknown) {}
 
private:
 
   syntax::TreeBuilder &Builder;
   const LangOptions &LangOpts;
 };
 } // namespace
 
 void syntax::TreeBuilder::foldNode(llvm::ArrayRef<syntax::Token> Range,
                                    syntax::Tree *New) {
-  Pending.foldChildren(Range, New);
+  Pending.foldChildren(Arena, Range, New);
 }
 
 void syntax::TreeBuilder::noticeDeclaratorRange(
     llvm::ArrayRef<syntax::Token> Range) {
   if (Pending.extendDelayedFold(Range))
     return;
   Pending.foldChildrenDelayed(Range,
                               new (allocator()) syntax::SimpleDeclaration);
void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
 
   auto Range = getStmtRange(Child);
   // This is an expression in a statement position, consume the trailing
   // semicolon and form an 'ExpressionStatement' node.
   if (auto *E = dyn_cast<Expr>(Child)) {
     Pending.assignRole(getExprRange(E),
                        NodeRole::ExpressionStatement_expression);
     // (!) 'getRange(Stmt)' ensures this already covers a trailing semicolon.
-    Pending.foldChildren(Range, new (allocator()) syntax::ExpressionStatement);
+    Pending.foldChildren(Arena, Range,
+                         new (allocator()) syntax::ExpressionStatement);
   }
   Pending.assignRole(Range, Role);
 }
 
 void syntax::TreeBuilder::markExprChild(Expr *Child, NodeRole Role) {
   if (!Child)
     return;
 
const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {
   return &*It;
 }
 
 syntax::TranslationUnit *
 syntax::buildSyntaxTree(Arena &A, const TranslationUnitDecl &TU) {
   TreeBuilder Builder(A);
   BuildTreeVisitor(TU.getASTContext(), Builder).TraverseAST(TU.getASTContext());
   return std::move(Builder).finalize();
 }

clang/lib/Tooling/Syntax/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangToolingSyntax
   BuildTree.cpp
+  ComputeReplacements.cpp
   Nodes.cpp
+  Mutations.cpp
+  Synthesis.cpp
   Tokens.cpp
   Tree.cpp
 
   LINK_LIBS
   clangAST
   clangBasic
   clangFrontend
   clangLex
   clangToolingCore
   )

clang/lib/Tooling/Syntax/ComputeReplacements.cpp

+//===- ComputeReplacements.cpp --------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Core/Replacement.h"
+#include "clang/Tooling/Syntax/Mutations.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "llvm/Support/Error.h"
+
+using namespace clang;
+
+namespace {
+using ProcessTokensFn = llvm::function_ref<void(llvm::ArrayRef<syntax::Token>,
+                                                bool /*IsOriginal*/)>;
+/// Enumerates spans of tokens from the tree consecutively laid out in memory.
+void enumerateTokenSpans(const syntax::Tree *Root, ProcessTokensFn Callback) {
+  struct Enumerator {
+    Enumerator(ProcessTokensFn Callback)
+        : SpanBegin(nullptr), SpanEnd(nullptr), SpanIsOriginal(false),
+          Callback(Callback) {}
+
+    void run(const syntax::Tree *Root) {
+      process(Root);
+      // Report the last span to the user.
+      if (SpanBegin)
+        Callback(llvm::makeArrayRef(SpanBegin, SpanEnd), SpanIsOriginal);
+    }
+
+  private:
+    void process(const syntax::Node *N) {
+      if (auto *T = dyn_cast<syntax::Tree>(N)) {
+        for (auto *C = T->firstChild(); C != nullptr; C = C->nextSibling())
+          process(C);
+        return;
+      }
+
+      auto *L = cast<syntax::Leaf>(N);
+      if (SpanEnd == L->token() && SpanIsOriginal == L->isOriginal()) {
+        // Extend the current span.
+        ++SpanEnd;
+        return;
+      }
+      // Report the current span to the user.
+      if (SpanBegin)
+        Callback(llvm::makeArrayRef(SpanBegin, SpanEnd), SpanIsOriginal);
+      // Start recording a new span.
+      SpanBegin = L->token();
+      SpanEnd = SpanBegin + 1;
+      SpanIsOriginal = L->isOriginal();
+    }
+
+    const syntax::Token *SpanBegin;
+    const syntax::Token *SpanEnd;
+    bool SpanIsOriginal;
+    ProcessTokensFn Callback;
+  };
+
+  return Enumerator(Callback).run(Root);
+}
+
+syntax::FileRange rangeOfExpanded(const syntax::Arena &A,
+                                  llvm::ArrayRef<syntax::Token> Expanded) {
+  auto &Buffer = A.tokenBuffer();
+  auto &SM = A.sourceManager();
+
+  // Check that \p Expanded actually points into expanded tokens.
+  assert(Buffer.expandedTokens().begin() <= Expanded.begin());
+  assert(Expanded.end() < Buffer.expandedTokens().end());
+
+  if (Expanded.empty())
+    // (!) empty tokens must always point before end().
+    return syntax::FileRange(
+        SM, SM.getExpansionLoc(Expanded.begin()->location()), /*Length=*/0);
+
+  auto Spelled = Buffer.spelledForExpanded(Expanded);
+  assert(Spelled && "could not find spelled tokens for expanded");
+  return syntax::Token::range(SM, Spelled->front(), Spelled->back());
+}
+} // namespace
+
+tooling::Replacements
+syntax::computeReplacements(const syntax::Arena &A,
+                            const syntax::TranslationUnit &TU) {
+  auto &Buffer = A.tokenBuffer();
+  auto &SM = A.sourceManager();
+
+  tooling::Replacements Replacements;
+  // Text inserted by the replacement we are building now.
+  std::string Replacement;
+  auto emitReplacement = [&](llvm::ArrayRef<syntax::Token> ReplacedRange) {
+    if (ReplacedRange.empty() && Replacement.empty())
+      return;
+    llvm::cantFail(Replacements.add(tooling::Replacement(
+        SM, rangeOfExpanded(A, ReplacedRange).toCharRange(SM), Replacement)));
+    Replacement = "";
+  };
+
+  const syntax::Token *NextOriginal = Buffer.expandedTokens().begin();
+  enumerateTokenSpans(
+      &TU, [&](llvm::ArrayRef<syntax::Token> Tokens, bool IsOriginal) {
+        if (!IsOriginal) {
+          Replacement +=
+              syntax::Token::range(SM, Tokens.front(), Tokens.back()).text(SM);
+          return;
+        }
+        assert(NextOriginal <= Tokens.begin());
+        // We are looking at a span of original tokens.
+        if (NextOriginal != Tokens.begin()) {
+          // There is a gap, record a replacement or deletion.
+          emitReplacement(llvm::makeArrayRef(NextOriginal, Tokens.begin()));
+        } else {
+          // No gap, but we may have pending insertions. Emit them now.
+          emitReplacement(llvm::makeArrayRef(NextOriginal, /*Length=*/0));
+        }
+        NextOriginal = Tokens.end();
+      });
+
+  // We might have pending replacements at the end of file. If so, emit them.
+  emitReplacement(llvm::makeArrayRef(
+      NextOriginal, Buffer.expandedTokens().drop_back().end()));
+
+  return Replacements;
+}

clang/lib/Tooling/Syntax/Mutations.cpp

+//===- Mutations.cpp ------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/Mutations.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Lex/Token.h"
+#include "clang/Tooling/Core/Replacement.h"
+#include "clang/Tooling/Syntax/BuildTree.h"
+#include "clang/Tooling/Syntax/Nodes.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "clang/Tooling/Syntax/Tree.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Casting.h"
+#include <cassert>
+#include <string>
+
+using namespace clang;
+
+// 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(New->Parent == nullptr);
+    assert(New->NextSibling == nullptr);
+    assert(!New->isDetached());
+    assert(Role != NodeRole::Detached);
+
+    New->Role = static_cast<unsigned>(Role);
+    Anchor->parent()->replaceChildRangeLowLevel(Anchor, Anchor, New);
+  }
+
+  /// Replace the node, keeping the role.
+  static void replace(syntax::Node *Old, syntax::Node *New) {
+    assert(New->Parent == nullptr);
+    assert(New->NextSibling == nullptr);
+    assert(New->isDetached());
+
+    New->Role = Old->Role;
+    Old->parent()->replaceChildRangeLowLevel(findPrevious(Old),
+                                             Old->nextSibling(), New);
+  }
+
+  /// Completely remove the node from its parent.
+  static void remove(syntax::Node *N) {
+    N->parent()->replaceChildRangeLowLevel(findPrevious(N), N->nextSibling(),
+                                           /*New=*/nullptr);
+  }
+
+private:
+  static syntax::Node *findPrevious(syntax::Node *N) {
+    if (N->parent()->firstChild() == N)
+      return nullptr;
+    for (syntax::Node *C = N->parent()->firstChild(); C != nullptr;
+         C = C->nextSibling()) {
+      if (C->nextSibling() == N)
+        return C;
+    }
+    llvm_unreachable("could not find a child node");
+  }
+};
+
+void syntax::removeStatement(syntax::Arena &A, syntax::Statement *S) {
+  assert(S->canModify());
+
+  if (auto *Parent = llvm::dyn_cast<CompoundStatement>(S->parent())) {
+    // A child of CompoundStatement can just be safely removed.
+    MutationsImpl::remove(S);
+    return;
+  }
+  // For the rest, we have to replace with an empty statement.
+  if (isa<EmptyStatement>(S))
+    return; // already an empty statement, nothing to do.
+
+  MutationsImpl::replace(S, createEmptyStatement(A));
+}

clang/lib/Tooling/Syntax/Synthesis.cpp

+//===- Synthesis.cpp ------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/BuildTree.h"
+
+using namespace clang;
+
+/// Exposes private syntax tree APIs required to implement node synthesis.
+/// Should not be used for anything else.
+class syntax::FactoryImpl {
+public:
+  static void prependChildLowLevel(syntax::Tree *T, syntax::Node *Child,
+                                   syntax::NodeRole R) {
+    T->prependChildLowLevel(Child, R);
+  }
+};
+
+clang::syntax::Leaf *syntax::createPunctuation(clang::syntax::Arena &A,
+                                               clang::tok::TokenKind K) {
+  auto Tokens = A.lexBuffer(llvm::MemoryBuffer::getMemBuffer(
+                                clang::tok::getPunctuatorSpelling(K)))
+                    .second;
+  assert(Tokens.size() == 1);
+  assert(Tokens.front().kind() == K);
+  return new (A.allocator()) clang::syntax::Leaf(Tokens.begin());
+}
+
+clang::syntax::EmptyStatement *
+syntax::createEmptyStatement(clang::syntax::Arena &A) {
+  auto *S = new (A.allocator()) clang::syntax::EmptyStatement;
+  FactoryImpl::prependChildLowLevel(S, createPunctuation(A, clang::tok::semi),
+                                    NodeRole::Unknown);
+  return S;
+}

clang/lib/Tooling/Syntax/Tokens.cpp

 }
 
 FileRange syntax::Token::range(const SourceManager &SM,
                                const syntax::Token &First,
                                const syntax::Token &Last) {
   auto F = First.range(SM);
   auto L = Last.range(SM);
   assert(F.file() == L.file() && "tokens from different files");
-  assert(F.endOffset() <= L.beginOffset() && "wrong order of tokens");
+  assert(F == L || F.endOffset() <= L.beginOffset() && "wrong order of tokens");
   return FileRange(F.file(), F.beginOffset(), L.endOffset());
 }
 
 llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, const Token &T) {
   return OS << T.str();
 }
 
 FileRange::FileRange(FileID File, unsigned BeginOffset, unsigned EndOffset)
const Token *End =
       llvm::partition_point(expandedTokens(), [&](const syntax::Token &T) {
         return !SourceMgr->isBeforeInTranslationUnit(R.getEnd(), T.location());
       });
   if (Begin > End)
     return {};
   return {Begin, End};
 }
 
+CharSourceRange FileRange::toCharRange(const SourceManager &SM) const {
+  return CharSourceRange(
+      SourceRange(SM.getComposedLoc(File, Begin), SM.getComposedLoc(File, End)),
+      /*IsTokenRange=*/false);
+}
+
 std::pair<const syntax::Token *, const TokenBuffer::Mapping *>
 TokenBuffer::spelledForExpandedToken(const syntax::Token *Expanded) const {
   assert(Expanded);
   assert(ExpandedTokens.data() <= Expanded &&
          Expanded < ExpandedTokens.data() + ExpandedTokens.size());
 
   auto FileIt = Files.find(
       SourceMgr->getFileID(SourceMgr->getExpansionLoc(Expanded->location())));

clang/lib/Tooling/Syntax/Tree.cpp

 }
 
 bool syntax::Leaf::classof(const Node *N) {
   return N->kind() == NodeKind::Leaf;
 }
 
 syntax::Node::Node(NodeKind Kind)
     : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
-      Role(static_cast<unsigned>(NodeRole::Detached)) {}
+      Role(static_cast<unsigned>(NodeRole::Detached)), Original(false),
+      CanModify(false) {}
+
+bool syntax::Node::isDetached() const { return role() == NodeRole::Detached; }
 
 bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
 
 void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
   assert(Child->Parent == nullptr);
   assert(Child->NextSibling == nullptr);
   assert(Child->role() == NodeRole::Detached);
   assert(Role != NodeRole::Detached);
 
   Child->Parent = this;
   Child->NextSibling = this->FirstChild;
   Child->Role = static_cast<unsigned>(Role);
   this->FirstChild = Child;
 }
 
+void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
+                                             Node *New) {
+  assert(!BeforeBegin || BeforeBegin->Parent == this);
+
+#ifndef NDEBUG
+  for (auto *N = New; N; N = N->nextSibling()) {
+    assert(N->Parent == nullptr);
+    assert(N->role() != NodeRole::Detached && "Roles must be set");
+    // FIXME: sanity-check the role.
+  }
+#endif
+
+  // Detach old nodes.
+  for (auto *N = !BeforeBegin ? FirstChild : BeforeBegin->nextSibling();
+       N != End;) {
+    auto *Next = N->NextSibling;
+
+    N->Role = static_cast<unsigned>(NodeRole::Detached);
+    N->Parent = nullptr;
+    N->NextSibling = nullptr;
+
+    N = Next;
+  }
+
+  // Attach new nodes.
+  if (BeforeBegin)
+    BeforeBegin->NextSibling = New ? New : End;
+  else
+    FirstChild = New ? New : End;
+
+  if (New) {
+    auto *Last = New;
+    while (auto *Next = Last->nextSibling())
+      Last = Next;
+    Last->NextSibling = End;
+  }
+
+  // Mark the node as modified.
+  for (auto *T = this; T && T->Original; T = T->Parent)
+    T->Original = false;
+}
+
 namespace {
 static void traverse(const syntax::Node *N,
                      llvm::function_ref<void(const syntax::Node *)> Visit) {
   if (auto *T = dyn_cast<syntax::Tree>(N)) {
     for (auto *C = T->firstChild(); C; C = C->nextSibling())
       traverse(C, Visit);
   }
   Visit(N);
if (T.kind() == tok::eof) {
       continue;
     }
     OS << T.text(SM);
   }
 }
 
 static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
                      const syntax::Arena &A, std::vector<bool> IndentMask) {
+  std::string Marks;
+  if (!N->isOriginal())
+    Marks += "M";
   if (N->role() == syntax::NodeRole::Detached)
-    OS << "*: ";
-  // FIXME: find a nice way to print other roles.
+    Marks += "*"; // FIXME: find a nice way to print other roles.
+  if (!N->canModify())
+    Marks += "I";
+  if (!Marks.empty())
+    OS << Marks << ": ";
 
   if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
     dumpTokens(OS, *L->token(), A.sourceManager());
     OS << "\n";
     return;
   }
 
   auto *T = llvm::cast<syntax::Tree>(N);

 std::string syntax::Node::dumpTokens(const Arena &A) const {
   std::string Storage;
   llvm::raw_string_ostream OS(Storage);
   traverse(this, [&](const syntax::Node *N) {
     auto *L = llvm::dyn_cast<syntax::Leaf>(N);
     if (!L)
       return;
     ::dumpTokens(OS, *L->token(), A.sourceManager());
+    OS << " ";
   });
   return OS.str();
 }
 
+syntax::Leaf *syntax::Tree::firstLeaf() {
+  auto *T = this;
+  while (auto *C = T->firstChild()) {
+    if (auto *L = dyn_cast<syntax::Leaf>(C))
+      return L;
+    T = cast<syntax::Tree>(C);
+  }
+  return nullptr;
+}
+
+syntax::Leaf *syntax::Tree::lastLeaf() {
+  auto *T = this;
+  while (auto *C = T->firstChild()) {
+    // Find the last child.
+    while (auto *Next = C->nextSibling())
+      C = Next;
+
+    if (auto *L = dyn_cast<syntax::Leaf>(C))
+      return L;
+    T = cast<syntax::Tree>(C);
+  }
+  return nullptr;
+}
+
 syntax::Node *syntax::Tree::findChild(NodeRole R) {
   for (auto *C = FirstChild; C; C = C->nextSibling()) {
     if (C->role() == R)
       return C;
   }
   return nullptr;
 }

clang/unittests/Tooling/Syntax/CMakeLists.txt

 clang_target_link_libraries(SyntaxTests
   PRIVATE
   clangAST
   clangBasic
   clangFrontend
   clangLex
   clangSerialization
   clangTooling
+  clangToolingCore
   clangToolingSyntax
   )
 
 target_link_libraries(SyntaxTests
   PRIVATE
   LLVMTestingSupport
 )

clang/unittests/Tooling/Syntax/TreeTest.cpp

 //===- TreeTest.cpp -------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/Syntax/Tree.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Basic/LLVM.h"
 #include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendAction.h"
 #include "clang/Lex/PreprocessorOptions.h"
+#include "clang/Tooling/Core/Replacement.h"
 #include "clang/Tooling/Syntax/BuildTree.h"
+#include "clang/Tooling/Syntax/Mutations.h"
 #include "clang/Tooling/Syntax/Nodes.h"
+#include "clang/Tooling/Syntax/Tokens.h"
 #include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Testing/Support/Annotations.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cstdlib>
 
 using namespace clang;
 
 namespace {
+static llvm::ArrayRef<syntax::Token> tokens(syntax::Node *N) {
+  assert(N->isOriginal() && "tokens of modified nodes are not well-defined");
+  if (auto *L = dyn_cast<syntax::Leaf>(N))
+    return llvm::makeArrayRef(L->token(), 1);
+  auto *T = cast<syntax::Tree>(N);
+  return llvm::makeArrayRef(T->firstLeaf()->token(),
+                            T->lastLeaf()->token() + 1);
+}
+
 class SyntaxTreeTest : public ::testing::Test {
 protected:
   // Build a syntax tree for the code.
   syntax::TranslationUnit *buildTree(llvm::StringRef Code) {
     // FIXME: this code is almost the identical to the one in TokensTest. Share
     //        it.
     class BuildSyntaxTree : public ASTConsumer {
     public:
       BuildSyntaxTree(syntax::TranslationUnit *&Root,
                       std::unique_ptr<syntax::Arena> &Arena,
                       std::unique_ptr<syntax::TokenCollector> Tokens)
           : Root(Root), Arena(Arena), Tokens(std::move(Tokens)) {
         assert(this->Tokens);
       }
 
       void HandleTranslationUnit(ASTContext &Ctx) override {
         Arena = std::make_unique<syntax::Arena>(Ctx.getSourceManager(),
                                                 Ctx.getLangOpts(),
                                                 std::move(*Tokens).consume());
         Tokens = nullptr; // make sure we fail if this gets called twice.
         Root = syntax::buildSyntaxTree(*Arena, *Ctx.getTranslationUnitDecl());
       }
 
     private:
       syntax::TranslationUnit *&Root;
       std::unique_ptr<syntax::Arena> &Arena;
       std::unique_ptr<syntax::TokenCollector> Tokens;
     };
 
syntax::TranslationUnit *buildTree(llvm::StringRef Code) {
 
     constexpr const char *FileName = "./input.cpp";
     FS->addFile(FileName, time_t(), llvm::MemoryBuffer::getMemBufferCopy(""));
     if (!Diags->getClient())
       Diags->setClient(new IgnoringDiagConsumer);
     // Prepare to run a compiler.
     std::vector<const char *> Args = {"syntax-test", "-std=c++11",
                                       "-fsyntax-only", FileName};
-    auto CI = createInvocationFromCommandLine(Args, Diags, FS);
-    assert(CI);
-    CI->getFrontendOpts().DisableFree = false;
-    CI->getPreprocessorOpts().addRemappedFile(
+    Invocation = createInvocationFromCommandLine(Args, Diags, FS);
+    assert(Invocation);
+    Invocation->getFrontendOpts().DisableFree = false;
+    Invocation->getPreprocessorOpts().addRemappedFile(
         FileName, llvm::MemoryBuffer::getMemBufferCopy(Code).release());
     CompilerInstance Compiler;
-    Compiler.setInvocation(std::move(CI));
+    Compiler.setInvocation(Invocation);
     Compiler.setDiagnostics(Diags.get());
     Compiler.setFileManager(FileMgr.get());
     Compiler.setSourceManager(SourceMgr.get());
 
     syntax::TranslationUnit *Root = nullptr;
     BuildSyntaxTreeAction Recorder(Root, this->Arena);
     if (!Compiler.ExecuteAction(Recorder)) {
       ADD_FAILURE() << "failed to run the frontend";
       std::abort();
     }
     return Root;
   }
 
   // Adds a file to the test VFS.
   void addFile(llvm::StringRef Path, llvm::StringRef Contents) {
     if (!FS->addFile(Path, time_t(),
                      llvm::MemoryBuffer::getMemBufferCopy(Contents))) {
       ADD_FAILURE() << "could not add a file to VFS: " << Path;
     }
   }
 
+  /// Finds the deepest node in the tree that covers exactly \p R.
+  /// FIXME: implement this efficiently and move to public syntax tree API.
+  syntax::Node *nodeByRange(llvm::Annotations::Range R, syntax::Node *Root) {
+    llvm::ArrayRef<syntax::Token> Toks = tokens(Root);
+
+    if (Toks.front().location().isFileID() &&
+        Toks.back().location().isFileID() &&
+        syntax::Token::range(*SourceMgr, Toks.front(), Toks.back()) ==
+            syntax::FileRange(SourceMgr->getMainFileID(), R.Begin, R.End))
+      return Root;
+
+    auto *T = dyn_cast<syntax::Tree>(Root);
+    if (!T)
+      return nullptr;
+    for (auto *C = T->firstChild(); C != nullptr; C = C->nextSibling()) {
+      if (auto *Result = nodeByRange(R, C))
+        return Result;
+    }
+    return nullptr;
+  }
+
   // Data fields.
   llvm::IntrusiveRefCntPtr<DiagnosticsEngine> Diags =
       new DiagnosticsEngine(new DiagnosticIDs, new DiagnosticOptions);
   IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> FS =
       new llvm::vfs::InMemoryFileSystem;
   llvm::IntrusiveRefCntPtr<FileManager> FileMgr =
       new FileManager(FileSystemOptions(), FS);
   llvm::IntrusiveRefCntPtr<SourceManager> SourceMgr =
       new SourceManager(*Diags, *FileMgr);
+  std::shared_ptr<CompilerInvocation> Invocation;
   // Set after calling buildTree().
   std::unique_ptr<syntax::Arena> Arena;
 };
 
 TEST_F(SyntaxTreeTest, Basic) {
   std::pair</*Input*/ std::string, /*Expected*/ std::string> Cases[] = {
       {
           R"cpp(

 static_assert(true);
     )cpp",
        R"txt(
 *: TranslationUnit
 |-StaticAssertDeclaration
 | |-static_assert
 | |-(
 | |-UnknownExpression
 | | `-true
 | |-,
 | |-UnknownExpression
 | | `-"message"
 | |-)
 | `-;
 `-StaticAssertDeclaration
   |-static_assert
   |-(
   |-UnknownExpression
   | `-true
   |-)
   `-;
        )txt"},
`-LinkageSpecificationDeclaration
   | |-b
   | `-;
   |-SimpleDeclaration
   | |-int
   | |-c
   | `-;
   `-}
        )txt"},
+      // Some nodes are non-modifiable, they are marked with 'I:'.
+      {R"cpp(
+#define HALF_IF if (1+
+#define HALF_IF_2 1) {}
+void test() {
+  HALF_IF HALF_IF_2 else {}
+})cpp",
+       R"txt(
+*: TranslationUnit
+`-SimpleDeclaration
+  |-void
+  |-test
+  |-(
+  |-)
+  `-CompoundStatement
+    |-{
+    |-IfStatement
+    | |-I: if
+    | |-I: (
+    | |-I: UnknownExpression
+    | | |-I: 1
+    | | |-I: +
+    | | `-I: 1
+    | |-I: )
+    | |-I: CompoundStatement
+    | | |-I: {
+    | | `-I: }
+    | |-else
+    | `-CompoundStatement
+    |   |-{
+    |   `-}
+    `-}
+       )txt"},
   };
 
   for (const auto &T : Cases) {
     SCOPED_TRACE(T.first);
 
     auto *Root = buildTree(T.first);
     std::string Expected = llvm::StringRef(T.second).trim().str();
     std::string Actual = llvm::StringRef(Root->dump(*Arena)).trim();
     EXPECT_EQ(Expected, Actual) << "the resulting dump is:\n" << Actual;
   }
 }
+
+TEST_F(SyntaxTreeTest, Mutations) {
+  using Transformation = std::function<void(
+      const llvm::Annotations & /*Input*/, syntax::TranslationUnit * /*Root*/)>;
+  auto CheckTransformation = [this](std::string Input, std::string Expected,
+                                    Transformation Transform) -> void {
+    llvm::Annotations Source(Input);
+    auto *Root = buildTree(Source.code());
+
+    Transform(Source, Root);
+
+    auto Replacements = syntax::computeReplacements(*Arena, *Root);
+    auto Output = tooling::applyAllReplacements(Source.code(), Replacements);
+    if (!Output) {
+      ADD_FAILURE() << "could not apply replacements: "
+                    << llvm::toString(Output.takeError());
+      return;
+    }
+
+    EXPECT_EQ(Expected, *Output) << "input is:\n" << Input;
+  };
+
+  // Removes the selected statement. Input should have exactly one selected
+  // range and it should correspond to a single statement.
+  auto RemoveStatement = [this](const llvm::Annotations &Input,
+                                syntax::TranslationUnit *TU) {
+    auto *S = cast<syntax::Statement>(nodeByRange(Input.range(), TU));
+    ASSERT_TRUE(S->canModify()) << "cannot remove a statement";
+    syntax::removeStatement(*Arena, S);
+  };
+
+  std::vector<std::pair<std::string /*Input*/, std::string /*Expected*/>>
+      Cases = {
+          {"void test() { [[100+100;]] test(); }", "void test() {  test(); }"},
+          {"void test() { if (true) [[{}]] else {} }",
+           "void test() { if (true) ; else {} }"},
+          {"void test() { [[;]] }", "void test() {  }"}};
+  for (const auto &C : Cases)
+    CheckTransformation(C.first, C.second, RemoveStatement);
+}
+
 } // namespace