vendor/clang/clang-trunk-r290819

13 files changed, 900 insertions, 313 deletions

diff --git a/unittests/Tooling/CMakeLists.txt b/unittests/Tooling/CMakeLists.txt
index b4b3f404e2709..185f43b6a8c54 100644
--- a/unittests/Tooling/CMakeLists.txt
+++ b/unittests/Tooling/CMakeLists.txt
@@ -6,6 +6,7 @@ set(LLVM_LINK_COMPONENTS
 # By default MSVC has a 2^16 limit on the number of sections in an object file,
 # and this needs more than that.
 if (MSVC)
+  set_source_files_properties(RecursiveASTVisitorTest.cpp PROPERTIES COMPILE_FLAGS /bigobj)
   set_source_files_properties(RecursiveASTVisitorTestExprVisitor.cpp PROPERTIES COMPILE_FLAGS /bigobj)
 endif()
 
diff --git a/unittests/Tooling/CompilationDatabaseTest.cpp b/unittests/Tooling/CompilationDatabaseTest.cpp
index 380d86fc5660d..1a6fffec9392a 100644
--- a/unittests/Tooling/CompilationDatabaseTest.cpp
+++ b/unittests/Tooling/CompilationDatabaseTest.cpp
@@ -7,7 +7,6 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "clang/AST/ASTConsumer.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclGroup.h"
 #include "clang/Frontend/FrontendAction.h"
@@ -22,9 +21,10 @@ namespace tooling {
 
 static void expectFailure(StringRef JSONDatabase, StringRef Explanation) {
   std::string ErrorMessage;
-  EXPECT_EQ(nullptr, JSONCompilationDatabase::loadFromBuffer(JSONDatabase,
-                                                             ErrorMessage))
-    << "Expected an error because of: " << Explanation.str();
+  EXPECT_EQ(nullptr,
+            JSONCompilationDatabase::loadFromBuffer(JSONDatabase, ErrorMessage,
+                                                    JSONCommandLineSyntax::Gnu))
+      << "Expected an error because of: " << Explanation.str();
 }
 
 TEST(JSONCompilationDatabase, ErrsOnInvalidFormat) {
@@ -44,12 +44,15 @@ TEST(JSONCompilationDatabase, ErrsOnInvalidFormat) {
   expectFailure("[{\"directory\":\"\",\"command\":[],\"file\":\"\"}]", "Command not string");
   expectFailure("[{\"directory\":\"\",\"arguments\":[[]],\"file\":\"\"}]",
                 "Arguments contain non-string");
+  expectFailure("[{\"output\":[]}]", "Expected strings as value.");
 }
 
 static std::vector<std::string> getAllFiles(StringRef JSONDatabase,
-                                            std::string &ErrorMessage) {
+                                            std::string &ErrorMessage,
+                                            JSONCommandLineSyntax Syntax) {
   std::unique_ptr<CompilationDatabase> Database(
-      JSONCompilationDatabase::loadFromBuffer(JSONDatabase, ErrorMessage));
+      JSONCompilationDatabase::loadFromBuffer(JSONDatabase, ErrorMessage,
+                                              Syntax));
   if (!Database) {
     ADD_FAILURE() << ErrorMessage;
     return std::vector<std::string>();
@@ -57,10 +60,12 @@ static std::vector<std::string> getAllFiles(StringRef JSONDatabase,
   return Database->getAllFiles();
 }
 
-static std::vector<CompileCommand> getAllCompileCommands(StringRef JSONDatabase,
-                                                    std::string &ErrorMessage) {
+static std::vector<CompileCommand>
+getAllCompileCommands(JSONCommandLineSyntax Syntax, StringRef JSONDatabase,
+                      std::string &ErrorMessage) {
   std::unique_ptr<CompilationDatabase> Database(
-      JSONCompilationDatabase::loadFromBuffer(JSONDatabase, ErrorMessage));
+      JSONCompilationDatabase::loadFromBuffer(JSONDatabase, ErrorMessage,
+                                              Syntax));
   if (!Database) {
     ADD_FAILURE() << ErrorMessage;
     return std::vector<CompileCommand>();
@@ -71,7 +76,8 @@ static std::vector<CompileCommand> getAllCompileCommands(StringRef JSONDatabase,
 TEST(JSONCompilationDatabase, GetAllFiles) {
   std::string ErrorMessage;
   EXPECT_EQ(std::vector<std::string>(),
-            getAllFiles("[]", ErrorMessage)) << ErrorMessage;
+            getAllFiles("[]", ErrorMessage, JSONCommandLineSyntax::Gnu))
+      << ErrorMessage;
 
   std::vector<std::string> expected_files;
   SmallString<16> PathStorage;
@@ -79,54 +85,70 @@ TEST(JSONCompilationDatabase, GetAllFiles) {
   expected_files.push_back(PathStorage.str());
   llvm::sys::path::native("//net/dir/file2", PathStorage);
   expected_files.push_back(PathStorage.str());
-  EXPECT_EQ(expected_files, getAllFiles(
-    "[{\"directory\":\"//net/dir\","
-      "\"command\":\"command\","
-      "\"file\":\"file1\"},"
-    " {\"directory\":\"//net/dir\","
-      "\"command\":\"command\","
-      "\"file\":\"file2\"}]",
-    ErrorMessage)) << ErrorMessage;
+  EXPECT_EQ(expected_files,
+            getAllFiles("[{\"directory\":\"//net/dir\","
+                        "\"command\":\"command\","
+                        "\"file\":\"file1\"},"
+                        " {\"directory\":\"//net/dir\","
+                        "\"command\":\"command\","
+                        "\"file\":\"file2\"}]",
+                        ErrorMessage, JSONCommandLineSyntax::Gnu))
+      << ErrorMessage;
 }
 
 TEST(JSONCompilationDatabase, GetAllCompileCommands) {
   std::string ErrorMessage;
-  EXPECT_EQ(0u,
-            getAllCompileCommands("[]", ErrorMessage).size()) << ErrorMessage;
+  EXPECT_EQ(
+      0u, getAllCompileCommands(JSONCommandLineSyntax::Gnu, "[]", ErrorMessage)
+              .size())
+      << ErrorMessage;
 
   StringRef Directory1("//net/dir1");
   StringRef FileName1("file1");
   StringRef Command1("command1");
+  StringRef Output1("file1.o");
   StringRef Directory2("//net/dir2");
   StringRef FileName2("file2");
   StringRef Command2("command2");
+  StringRef Output2("");
 
   std::vector<CompileCommand> Commands = getAllCompileCommands(
-      ("[{\"directory\":\"" + Directory1 + "\"," +
-             "\"command\":\"" + Command1 + "\","
-             "\"file\":\"" + FileName1 + "\"},"
-       " {\"directory\":\"" + Directory2 + "\"," +
-             "\"command\":\"" + Command2 + "\","
-             "\"file\":\"" + FileName2 + "\"}]").str(),
+      JSONCommandLineSyntax::Gnu,
+      ("[{\"directory\":\"" + Directory1 + "\"," + "\"command\":\"" + Command1 +
+       "\","
+       "\"file\":\"" +
+       FileName1 + "\", \"output\":\"" +
+       Output1 + "\"},"
+                   " {\"directory\":\"" +
+       Directory2 + "\"," + "\"command\":\"" + Command2 + "\","
+                                                          "\"file\":\"" +
+       FileName2 + "\"}]")
+          .str(),
       ErrorMessage);
   EXPECT_EQ(2U, Commands.size()) << ErrorMessage;
   EXPECT_EQ(Directory1, Commands[0].Directory) << ErrorMessage;
   EXPECT_EQ(FileName1, Commands[0].Filename) << ErrorMessage;
+  EXPECT_EQ(Output1, Commands[0].Output) << ErrorMessage;
   ASSERT_EQ(1u, Commands[0].CommandLine.size());
   EXPECT_EQ(Command1, Commands[0].CommandLine[0]) << ErrorMessage;
   EXPECT_EQ(Directory2, Commands[1].Directory) << ErrorMessage;
   EXPECT_EQ(FileName2, Commands[1].Filename) << ErrorMessage;
+  EXPECT_EQ(Output2, Commands[1].Output) << ErrorMessage;
   ASSERT_EQ(1u, Commands[1].CommandLine.size());
   EXPECT_EQ(Command2, Commands[1].CommandLine[0]) << ErrorMessage;
 
   // Check that order is preserved.
   Commands = getAllCompileCommands(
-      ("[{\"directory\":\"" + Directory2 + "\"," +
-             "\"command\":\"" + Command2 + "\","
-             "\"file\":\"" + FileName2 + "\"},"
-       " {\"directory\":\"" + Directory1 + "\"," +
-             "\"command\":\"" + Command1 + "\","
-             "\"file\":\"" + FileName1 + "\"}]").str(),
+      JSONCommandLineSyntax::Gnu,
+      ("[{\"directory\":\"" + Directory2 + "\"," + "\"command\":\"" + Command2 +
+       "\","
+       "\"file\":\"" +
+       FileName2 + "\"},"
+                   " {\"directory\":\"" +
+       Directory1 + "\"," + "\"command\":\"" + Command1 + "\","
+                                                          "\"file\":\"" +
+       FileName1 + "\"}]")
+          .str(),
       ErrorMessage);
   EXPECT_EQ(2U, Commands.size()) << ErrorMessage;
   EXPECT_EQ(Directory2, Commands[0].Directory) << ErrorMessage;
@@ -143,7 +165,8 @@ static CompileCommand findCompileArgsInJsonDatabase(StringRef FileName,
                                                     StringRef JSONDatabase,
                                                     std::string &ErrorMessage) {
   std::unique_ptr<CompilationDatabase> Database(
-      JSONCompilationDatabase::loadFromBuffer(JSONDatabase, ErrorMessage));
+      JSONCompilationDatabase::loadFromBuffer(JSONDatabase, ErrorMessage,
+                                              JSONCommandLineSyntax::Gnu));
   if (!Database)
     return CompileCommand();
   std::vector<CompileCommand> Commands = Database->getCompileCommands(FileName);
diff --git a/unittests/Tooling/LookupTest.cpp b/unittests/Tooling/LookupTest.cpp
index d847a298fff23..cc3922d01b51c 100644
--- a/unittests/Tooling/LookupTest.cpp
+++ b/unittests/Tooling/LookupTest.cpp
@@ -14,10 +14,18 @@ using namespace clang;
 namespace {
 struct GetDeclsVisitor : TestVisitor<GetDeclsVisitor> {
   std::function<void(CallExpr *)> OnCall;
+  std::function<void(RecordTypeLoc)> OnRecordTypeLoc;
   SmallVector<Decl *, 4> DeclStack;
 
   bool VisitCallExpr(CallExpr *Expr) {
-    OnCall(Expr);
+    if (OnCall)
+      OnCall(Expr);
+    return true;
+  }
+
+  bool VisitRecordTypeLoc(RecordTypeLoc Loc) {
+    if (OnRecordTypeLoc)
+      OnRecordTypeLoc(Loc);
     return true;
   }
 
@@ -29,7 +37,7 @@ struct GetDeclsVisitor : TestVisitor<GetDeclsVisitor> {
   }
 };
 
-TEST(LookupTest, replaceNestedName) {
+TEST(LookupTest, replaceNestedFunctionName) {
   GetDeclsVisitor Visitor;
 
   auto replaceCallExpr = [&](const CallExpr *Expr,
@@ -103,6 +111,55 @@ TEST(LookupTest, replaceNestedName) {
   };
   Visitor.runOver(
       "namespace a { int foo(); }\nusing a::foo;\nauto f = foo();\n");
+
+  Visitor.OnCall = [&](CallExpr *Expr) {
+    EXPECT_EQ("c::bar", replaceCallExpr(Expr, "::a::c::bar"));
+  };
+  Visitor.runOver("namespace a { namespace b { void foo(); } }\n"
+                  "namespace a { namespace b { namespace {"
+                  "void f() { foo(); }"
+                  "} } }\n");
+
+  Visitor.OnCall = [&](CallExpr *Expr) {
+    EXPECT_EQ("x::bar", replaceCallExpr(Expr, "::a::x::bar"));
+  };
+  Visitor.runOver("namespace a { namespace b { void foo(); } }\n"
+                  "namespace a { namespace b { namespace c {"
+                  "void f() { foo(); }"
+                  "} } }\n");
+}
+
+TEST(LookupTest, replaceNestedClassName) {
+  GetDeclsVisitor Visitor;
+
+  auto replaceRecordTypeLoc = [&](RecordTypeLoc Loc,
+                                  StringRef ReplacementString) {
+    const auto *FD = cast<CXXRecordDecl>(Loc.getDecl());
+    return tooling::replaceNestedName(
+        nullptr, Visitor.DeclStack.back()->getDeclContext(), FD,
+        ReplacementString);
+  };
+
+  Visitor.OnRecordTypeLoc = [&](RecordTypeLoc Type) {
+    // Filter Types by name since there are other `RecordTypeLoc` in the test
+    // file.
+    if (Type.getDecl()->getQualifiedNameAsString() == "a::b::Foo")
+      EXPECT_EQ("x::Bar", replaceRecordTypeLoc(Type, "::a::x::Bar"));
+  };
+  Visitor.runOver("namespace a { namespace b {\n"
+                  "class Foo;\n"
+                  "namespace c { Foo f();; }\n"
+                  "} }\n");
+
+  Visitor.OnRecordTypeLoc = [&](RecordTypeLoc Type) {
+    // Filter Types by name since there are other `RecordTypeLoc` in the test
+    // file.
+    // `a::b::Foo` in using shadow decl is not `TypeLoc`.
+    if (Type.getDecl()->getQualifiedNameAsString() == "a::b::Foo")
+      EXPECT_EQ("Bar", replaceRecordTypeLoc(Type, "::a::x::Bar"));
+  };
+  Visitor.runOver("namespace a { namespace b { class Foo {}; } }\n"
+                  "namespace c { using a::b::Foo; Foo f();; }\n");
 }
 
 } // end anonymous namespace
diff --git a/unittests/Tooling/RecursiveASTVisitorTest.cpp b/unittests/Tooling/RecursiveASTVisitorTest.cpp
index 991ae8bb7f3d2..7e08f9619c1c6 100644
--- a/unittests/Tooling/RecursiveASTVisitorTest.cpp
+++ b/unittests/Tooling/RecursiveASTVisitorTest.cpp
@@ -133,23 +133,21 @@ TEST(RecursiveASTVisitor, AttributesAreVisited) {
     "};\n"));
 }
 
-// Check to ensure that VarDecls are visited.
-class VarDeclVisitor : public ExpectedLocationVisitor<VarDeclVisitor> {
+// Check to ensure that implicit default argument expressions are visited.
+class IntegerLiteralVisitor
+    : public ExpectedLocationVisitor<IntegerLiteralVisitor> {
 public:
-  bool VisitVarDecl(VarDecl *VD) {
-    Match(VD->getNameAsString(), VD->getLocStart());
+  bool VisitIntegerLiteral(const IntegerLiteral *IL) {
+    Match("literal", IL->getLocation());
     return true;
   }
 };
 
-TEST(RecursiveASTVisitor, ArrayInitializersAreVisited) {
-  VarDeclVisitor Visitor;
-  Visitor.ExpectMatch("__i0", 1, 8);
-  EXPECT_TRUE(
-      Visitor.runOver("struct MyClass {\n"
-                      "  int c[1];\n"
-                      "  static MyClass Create() { return MyClass(); }\n"
-                      "};\n"));
+TEST(RecursiveASTVisitor, DefaultArgumentsAreVisited) {
+  IntegerLiteralVisitor Visitor;
+  Visitor.ExpectMatch("literal", 1, 15, 2);
+  EXPECT_TRUE(Visitor.runOver("int f(int i = 1);\n"
+                              "static int k = f();\n"));
 }
 
 } // end anonymous namespace
diff --git a/unittests/Tooling/RecursiveASTVisitorTestCallVisitor.cpp b/unittests/Tooling/RecursiveASTVisitorTestCallVisitor.cpp
index f8ff5bdc7879f..b981585450e10 100644
--- a/unittests/Tooling/RecursiveASTVisitorTestCallVisitor.cpp
+++ b/unittests/Tooling/RecursiveASTVisitorTestCallVisitor.cpp
@@ -8,7 +8,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "TestVisitor.h"
-#include <stack>
 
 using namespace clang;
 
diff --git a/unittests/Tooling/RecursiveASTVisitorTestDeclVisitor.cpp b/unittests/Tooling/RecursiveASTVisitorTestDeclVisitor.cpp
index 02676a737ab1b..63bfb8b2e6c14 100644
--- a/unittests/Tooling/RecursiveASTVisitorTestDeclVisitor.cpp
+++ b/unittests/Tooling/RecursiveASTVisitorTestDeclVisitor.cpp
@@ -8,7 +8,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "TestVisitor.h"
-#include <stack>
 
 using namespace clang;
 
diff --git a/unittests/Tooling/RecursiveASTVisitorTestExprVisitor.cpp b/unittests/Tooling/RecursiveASTVisitorTestExprVisitor.cpp
index 6af5906c3fd40..5f1dd65222ba1 100644
--- a/unittests/Tooling/RecursiveASTVisitorTestExprVisitor.cpp
+++ b/unittests/Tooling/RecursiveASTVisitorTestExprVisitor.cpp
@@ -8,7 +8,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "TestVisitor.h"
-#include <stack>
 
 using namespace clang;
 
@@ -162,10 +161,21 @@ TEST(RecursiveASTVisitor, CanSkipImplicitMemberInitializations) {
 
 class DeclRefExprVisitor : public ExpectedLocationVisitor<DeclRefExprVisitor> {
 public:
+  DeclRefExprVisitor() : ShouldVisitImplicitCode(false) {}
+
+  bool shouldVisitImplicitCode() const { return ShouldVisitImplicitCode; }
+
+  void setShouldVisitImplicitCode(bool NewValue) {
+    ShouldVisitImplicitCode = NewValue;
+  }
+
   bool VisitDeclRefExpr(DeclRefExpr *Reference) {
     Match(Reference->getNameInfo().getAsString(), Reference->getLocation());
     return true;
   }
+
+private:
+  bool ShouldVisitImplicitCode;
 };
 
 TEST(RecursiveASTVisitor, VisitsBaseClassTemplateArguments) {
@@ -192,6 +202,43 @@ TEST(RecursiveASTVisitor, VisitsCallExpr) {
     "void x(); void y() { x(); }"));
 }
 
+TEST(RecursiveASTVisitor, VisitsExplicitLambdaCaptureInit) {
+  DeclRefExprVisitor Visitor;
+  Visitor.ExpectMatch("i", 1, 20);
+  EXPECT_TRUE(Visitor.runOver(
+    "void f() { int i; [i]{}; }",
+    DeclRefExprVisitor::Lang_CXX11));
+}
+
+TEST(RecursiveASTVisitor, VisitsUseOfImplicitLambdaCapture) {
+  DeclRefExprVisitor Visitor;
+  Visitor.ExpectMatch("i", 1, 24);
+  EXPECT_TRUE(Visitor.runOver(
+    "void f() { int i; [=]{ i; }; }",
+    DeclRefExprVisitor::Lang_CXX11));
+}
+
+TEST(RecursiveASTVisitor, VisitsImplicitLambdaCaptureInit) {
+  DeclRefExprVisitor Visitor;
+  Visitor.setShouldVisitImplicitCode(true);
+  // We're expecting the "i" in the lambda to be visited twice:
+  // - Once for the DeclRefExpr in the lambda capture initialization (whose
+  //   source code location is set to the first use of the variable).
+  // - Once for the DeclRefExpr for the use of "i" inside the lambda.
+  Visitor.ExpectMatch("i", 1, 24, /*Times=*/2);
+  EXPECT_TRUE(Visitor.runOver(
+    "void f() { int i; [=]{ i; }; }",
+    DeclRefExprVisitor::Lang_CXX11));
+}
+
+TEST(RecursiveASTVisitor, VisitsLambdaInitCaptureInit) {
+  DeclRefExprVisitor Visitor;
+  Visitor.ExpectMatch("i", 1, 24);
+  EXPECT_TRUE(Visitor.runOver(
+    "void f() { int i; [a = i + 1]{}; }",
+    DeclRefExprVisitor::Lang_CXX14));
+}
+
 /* FIXME: According to Richard Smith this is a bug in the AST.
 TEST(RecursiveASTVisitor, VisitsBaseClassTemplateArgumentsInInstantiation) {
   DeclRefExprVisitor Visitor;
diff --git a/unittests/Tooling/RecursiveASTVisitorTestTypeLocVisitor.cpp b/unittests/Tooling/RecursiveASTVisitorTestTypeLocVisitor.cpp
index 63e2e8b6024c5..dc2adaf4da0c0 100644
--- a/unittests/Tooling/RecursiveASTVisitorTestTypeLocVisitor.cpp
+++ b/unittests/Tooling/RecursiveASTVisitorTestTypeLocVisitor.cpp
@@ -8,7 +8,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "TestVisitor.h"
-#include <stack>
 
 using namespace clang;
 
diff --git a/unittests/Tooling/RefactoringTest.cpp b/unittests/Tooling/RefactoringTest.cpp
index df96bb159dea7..c29f8d7d71230 100644
--- a/unittests/Tooling/RefactoringTest.cpp
+++ b/unittests/Tooling/RefactoringTest.cpp
@@ -7,6 +7,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "ReplacementTest.h"
 #include "RewriterTestContext.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
@@ -18,6 +19,7 @@
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Basic/VirtualFileSystem.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendAction.h"
@@ -26,22 +28,11 @@
 #include "clang/Tooling/Refactoring.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/SmallString.h"
-#include "llvm/Support/Path.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace tooling {
 
-class ReplacementTest : public ::testing::Test {
- protected:
-  Replacement createReplacement(SourceLocation Start, unsigned Length,
-                                llvm::StringRef ReplacementText) {
-    return Replacement(Context.Sources, Start, Length, ReplacementText);
-  }
-
-  RewriterTestContext Context;
-};
-
 TEST_F(ReplacementTest, CanDeleteAllText) {
   FileID ID = Context.createInMemoryFile("input.cpp", "text");
   SourceLocation Location = Context.getLocation(ID, 1, 1);
@@ -109,62 +100,412 @@ TEST_F(ReplacementTest, ReturnsInvalidPath) {
   EXPECT_TRUE(Replace2.getFilePath().empty());
 }
 
+// Checks that an llvm::Error instance contains a ReplacementError with expected
+// error code, expected new replacement, and expected existing replacement.
+static bool checkReplacementError(
+    llvm::Error&& Error, replacement_error ExpectedErr,
+    llvm::Optional<Replacement> ExpectedExisting,
+    llvm::Optional<Replacement> ExpectedNew) {
+  if (!Error) {
+    llvm::errs() << "Error is a success.";
+    return false;
+  }
+  std::string ErrorMessage;
+  llvm::raw_string_ostream OS(ErrorMessage);
+  llvm::handleAllErrors(std::move(Error), [&](const ReplacementError &RE) {
+    llvm::errs() << "Handling error...\n";
+    if (ExpectedErr != RE.get())
+      OS << "Unexpected error code: " << int(RE.get()) << "\n";
+    if (ExpectedExisting != RE.getExistingReplacement()) {
+      OS << "Expected Existing != Actual Existing.\n";
+      if (ExpectedExisting.hasValue())
+        OS << "Expected existing replacement: " << ExpectedExisting->toString()
+           << "\n";
+      if (RE.getExistingReplacement().hasValue())
+        OS << "Actual existing replacement: "
+           << RE.getExistingReplacement()->toString() << "\n";
+    }
+    if (ExpectedNew != RE.getNewReplacement()) {
+      OS << "Expected New != Actual New.\n";
+      if (ExpectedNew.hasValue())
+        OS << "Expected new replacement: " << ExpectedNew->toString() << "\n";
+      if (RE.getNewReplacement().hasValue())
+        OS << "Actual new replacement: " << RE.getNewReplacement()->toString()
+           << "\n";
+    }
+  });
+  OS.flush();
+  if (ErrorMessage.empty()) return true;
+  llvm::errs() << ErrorMessage;
+  return false;
+}
+
+TEST_F(ReplacementTest, FailAddReplacements) {
+  Replacements Replaces;
+  Replacement Deletion("x.cc", 0, 10, "3");
+  auto Err = Replaces.add(Deletion);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Replacement OverlappingReplacement("x.cc", 0, 2, "a");
+  Err = Replaces.add(OverlappingReplacement);
+  EXPECT_TRUE(checkReplacementError(std::move(Err),
+                                    replacement_error::overlap_conflict,
+                                    Deletion, OverlappingReplacement));
+
+  Replacement ContainedReplacement("x.cc", 2, 2, "a");
+  Err = Replaces.add(Replacement(ContainedReplacement));
+  EXPECT_TRUE(checkReplacementError(std::move(Err),
+                                    replacement_error::overlap_conflict,
+                                    Deletion, ContainedReplacement));
+
+  Replacement WrongPathReplacement("y.cc", 20, 2, "");
+  Err = Replaces.add(WrongPathReplacement);
+  EXPECT_TRUE(checkReplacementError(std::move(Err),
+                                    replacement_error::wrong_file_path,
+                                    Deletion, WrongPathReplacement));
+
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(Deletion, *Replaces.begin());
+}
+
+TEST_F(ReplacementTest, DeletionInReplacements) {
+  Replacements Replaces;
+  Replacement R("x.cc", 0, 10, "3");
+  auto Err = Replaces.add(R);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 0, 2, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 2, 2, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(R, *Replaces.begin());
+}
+
+TEST_F(ReplacementTest, OverlappingReplacements) {
+  Replacements Replaces;
+  auto Err = Replaces.add(Replacement("x.cc", 0, 3, "345"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 2, 3, "543"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(Replacement("x.cc", 0, 5, "34543"), *Replaces.begin());
+
+  Err = Replaces.add(Replacement("x.cc", 2, 1, "5"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(Replacement("x.cc", 0, 5, "34543"), *Replaces.begin());
+}
+
+TEST_F(ReplacementTest, AddAdjacentInsertionAndReplacement) {
+  Replacements Replaces;
+  // Test adding an insertion at the offset of an existing replacement.
+  auto Err = Replaces.add(Replacement("x.cc", 10, 3, "replace"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 0, "insert"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(Replaces.size(), 2u);
+
+  Replaces.clear();
+  // Test overlap with an existing insertion.
+  Err = Replaces.add(Replacement("x.cc", 10, 0, "insert"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 3, "replace"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(Replaces.size(), 2u);
+}
+
+TEST_F(ReplacementTest, MergeNewDeletions) {
+  Replacements Replaces;
+  Replacement ContainingReplacement("x.cc", 0, 10, "");
+  auto Err = Replaces.add(ContainingReplacement);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Err = Replaces.add(Replacement("x.cc", 5, 3, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Err = Replaces.add(Replacement("x.cc", 0, 10, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Err = Replaces.add(Replacement("x.cc", 5, 5, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(*Replaces.begin(), ContainingReplacement);
+}
+
+TEST_F(ReplacementTest, MergeOverlappingButNotAdjacentReplacement) {
+  Replacements Replaces;
+  auto Err = Replaces.add(Replacement("x.cc", 0, 2, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Err = Replaces.add(Replacement("x.cc", 5, 5, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Replacement After = Replacement("x.cc", 10, 5, "");
+  Err = Replaces.add(After);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Replacement ContainingReplacement("x.cc", 0, 10, "");
+  Err = Replaces.add(ContainingReplacement);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  EXPECT_EQ(2u, Replaces.size());
+  EXPECT_EQ(*Replaces.begin(), ContainingReplacement);
+  EXPECT_EQ(*(++Replaces.begin()), After);
+}
+
+TEST_F(ReplacementTest, InsertionBeforeMergedDeletions) {
+  Replacements Replaces;
+
+  Replacement Insertion("x.cc", 0, 0, "123");
+  auto Err = Replaces.add(Insertion);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Err = Replaces.add(Replacement("x.cc", 5, 5, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Replacement Deletion("x.cc", 0, 10, "");
+  Err = Replaces.add(Deletion);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  EXPECT_EQ(2u, Replaces.size());
+  EXPECT_EQ(*Replaces.begin(), Insertion);
+  EXPECT_EQ(*(++Replaces.begin()), Deletion);
+}
+
+TEST_F(ReplacementTest, MergeOverlappingDeletions) {
+  Replacements Replaces;
+  auto Err = Replaces.add(Replacement("x.cc", 0, 2, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Err = Replaces.add(Replacement("x.cc", 0, 5, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(Replacement("x.cc", 0, 5, ""), *Replaces.begin());
+
+  Err = Replaces.add(Replacement("x.cc", 1, 5, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(Replacement("x.cc", 0, 6, ""), *Replaces.begin());
+}
+
+TEST_F(ReplacementTest, FailedMergeExistingDeletions) {
+  Replacements Replaces;
+  Replacement First("x.cc", 0, 2, "");
+  auto Err = Replaces.add(First);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Replacement Second("x.cc", 5, 5, "");
+  Err = Replaces.add(Second);
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Err = Replaces.add(Replacement("x.cc", 1, 10, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(Replacement("x.cc", 0, 11, ""), *Replaces.begin());
+}
+
+TEST_F(ReplacementTest, FailAddRegression) {
+  Replacements Replaces;
+  // Create two replacements, where the second one is an insertion of the empty
+  // string exactly at the end of the first one.
+  auto Err = Replaces.add(Replacement("x.cc", 0, 10, "1"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  // Make sure we find the overlap with the first entry when inserting a
+  // replacement that ends exactly at the seam of the existing replacements.
+  Replacement OverlappingReplacement("x.cc", 5, 5, "fail");
+  Err = Replaces.add(OverlappingReplacement);
+  EXPECT_TRUE(checkReplacementError(std::move(Err),
+                                    replacement_error::overlap_conflict,
+                                    *Replaces.begin(), OverlappingReplacement));
+
+  Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+}
+
+TEST_F(ReplacementTest, InsertAtOffsetOfReplacement) {
+  Replacements Replaces;
+  auto Err = Replaces.add(Replacement("x.cc", 10, 2, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(Replaces.size(), 2u);
+
+  Replaces.clear();
+  Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 2, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(Replaces.size(), 2u);
+}
+
+TEST_F(ReplacementTest, AddInsertAtOtherInsertWhenOderIndependent) {
+  Replacements Replaces;
+  auto Err = Replaces.add(Replacement("x.cc", 10, 0, "a"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Replacement ConflictInsertion("x.cc", 10, 0, "b");
+  Err = Replaces.add(ConflictInsertion);
+  EXPECT_TRUE(checkReplacementError(std::move(Err),
+                                    replacement_error::insert_conflict,
+                                    *Replaces.begin(), ConflictInsertion));
+
+  Replaces.clear();
+  Err = Replaces.add(Replacement("x.cc", 10, 0, "a"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 0, "aa"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(1u, Replaces.size());
+  EXPECT_EQ(Replacement("x.cc", 10, 0, "aaa"), *Replaces.begin());
+
+  Replaces.clear();
+  Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 3, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 0, ""));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  EXPECT_EQ(2u, Replaces.size());
+  EXPECT_EQ(Replacement("x.cc", 10, 0, ""), *Replaces.begin());
+  EXPECT_EQ(Replacement("x.cc", 10, 3, ""), *std::next(Replaces.begin()));
+}
+
+TEST_F(ReplacementTest, InsertBetweenAdjacentReplacements) {
+  Replacements Replaces;
+  auto Err = Replaces.add(Replacement("x.cc", 10, 5, "a"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 8, 2, "a"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+  Err = Replaces.add(Replacement("x.cc", 10, 0, "b"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+}
+
 TEST_F(ReplacementTest, CanApplyReplacements) {
   FileID ID = Context.createInMemoryFile("input.cpp",
                                          "line1\nline2\nline3\nline4");
-  Replacements Replaces;
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
-                              5, "replaced"));
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 3, 1),
-                              5, "other"));
+  Replacements Replaces =
+      toReplacements({Replacement(Context.Sources,
+                                  Context.getLocation(ID, 2, 1), 5, "replaced"),
+                      Replacement(Context.Sources,
+                                  Context.getLocation(ID, 3, 1), 5, "other")});
   EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
   EXPECT_EQ("line1\nreplaced\nother\nline4", Context.getRewrittenText(ID));
 }
 
-// FIXME: Remove this test case when Replacements is implemented as std::vector
-// instead of std::set. The other ReplacementTest tests will need to be updated
-// at that point as well.
-TEST_F(ReplacementTest, VectorCanApplyReplacements) {
+// Verifies that replacement/deletion is applied before insertion at the same
+// offset.
+TEST_F(ReplacementTest, InsertAndDelete) {
   FileID ID = Context.createInMemoryFile("input.cpp",
                                          "line1\nline2\nline3\nline4");
-  std::vector<Replacement> Replaces;
-  Replaces.push_back(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
-                                 5, "replaced"));
-  Replaces.push_back(
-      Replacement(Context.Sources, Context.getLocation(ID, 3, 1), 5, "other"));
+  Replacements Replaces = toReplacements(
+      {Replacement(Context.Sources, Context.getLocation(ID, 2, 1), 6, ""),
+       Replacement(Context.Sources, Context.getLocation(ID, 2, 1), 0,
+                   "other\n")});
   EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
-  EXPECT_EQ("line1\nreplaced\nother\nline4", Context.getRewrittenText(ID));
+  EXPECT_EQ("line1\nother\nline3\nline4", Context.getRewrittenText(ID));
+}
+
+TEST_F(ReplacementTest, AdjacentReplacements) {
+  FileID ID = Context.createInMemoryFile("input.cpp",
+                                         "ab");
+  Replacements Replaces = toReplacements(
+      {Replacement(Context.Sources, Context.getLocation(ID, 1, 1), 1, "x"),
+       Replacement(Context.Sources, Context.getLocation(ID, 1, 2), 1, "y")});
+  EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
+  EXPECT_EQ("xy", Context.getRewrittenText(ID));
 }
 
-TEST_F(ReplacementTest, SkipsDuplicateReplacements) {
+TEST_F(ReplacementTest, AddDuplicateReplacements) {
   FileID ID = Context.createInMemoryFile("input.cpp",
                                          "line1\nline2\nline3\nline4");
-  Replacements Replaces;
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
-                              5, "replaced"));
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
-                              5, "replaced"));
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
-                              5, "replaced"));
+  auto Replaces = toReplacements({Replacement(
+      Context.Sources, Context.getLocation(ID, 2, 1), 5, "replaced")});
+
+  auto Err = Replaces.add(Replacement(
+      Context.Sources, Context.getLocation(ID, 2, 1), 5, "replaced"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
+  Err = Replaces.add(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
+                                 5, "replaced"));
+  EXPECT_TRUE(!Err);
+  llvm::consumeError(std::move(Err));
+
   EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
   EXPECT_EQ("line1\nreplaced\nline3\nline4", Context.getRewrittenText(ID));
 }
 
-TEST_F(ReplacementTest, ApplyAllFailsIfOneApplyFails) {
-  // This test depends on the value of the file name of an invalid source
-  // location being in the range ]a, z[.
-  FileID IDa = Context.createInMemoryFile("a.cpp", "text");
-  FileID IDz = Context.createInMemoryFile("z.cpp", "text");
-  Replacements Replaces;
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(IDa, 1, 1),
-                              4, "a"));
-  Replaces.insert(Replacement(Context.Sources, SourceLocation(),
-                              5, "2"));
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(IDz, 1, 1),
-                              4, "z"));
+TEST_F(ReplacementTest, FailOrderDependentReplacements) {
+  FileID ID = Context.createInMemoryFile("input.cpp",
+                                         "line1\nline2\nline3\nline4");
+  auto Replaces = toReplacements({Replacement(
+      Context.Sources, Context.getLocation(ID, 2, 1), 5, "other")});
+
+  Replacement ConflictReplacement(Context.Sources,
+                                  Context.getLocation(ID, 2, 1), 5, "rehto");
+  auto Err = Replaces.add(ConflictReplacement);
+  EXPECT_TRUE(checkReplacementError(std::move(Err),
+                                    replacement_error::overlap_conflict,
+                                    *Replaces.begin(), ConflictReplacement));
+
+  EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
+  EXPECT_EQ("line1\nother\nline3\nline4", Context.getRewrittenText(ID));
+}
+
+TEST_F(ReplacementTest, InvalidSourceLocationFailsApplyAll) {
+  Replacements Replaces =
+      toReplacements({Replacement(Context.Sources, SourceLocation(), 5, "2")});
+
   EXPECT_FALSE(applyAllReplacements(Replaces, Context.Rewrite));
-  EXPECT_EQ("a", Context.getRewrittenText(IDa));
-  EXPECT_EQ("z", Context.getRewrittenText(IDz));
 }
 
 TEST_F(ReplacementTest, MultipleFilesReplaceAndFormat) {
@@ -180,76 +521,66 @@ TEST_F(ReplacementTest, MultipleFilesReplaceAndFormat) {
   std::string Expected2 = "int x =\n"
                           "    1234567890123;\n"
                           "int y = 10;";
-  FileID ID1 = Context.createInMemoryFile("format_1.cpp", Code1);
-  FileID ID2 = Context.createInMemoryFile("format_2.cpp", Code2);
+  StringRef File1 = "format_1.cpp";
+  StringRef File2 = "format_2.cpp";
+  FileID ID1 = Context.createInMemoryFile(File1, Code1);
+  FileID ID2 = Context.createInMemoryFile(File2, Code2);
 
-  tooling::Replacements Replaces;
   // Scrambled the order of replacements.
-  Replaces.insert(tooling::Replacement(
-      Context.Sources, Context.getLocation(ID2, 1, 12), 0, "4567890123"));
-  Replaces.insert(tooling::Replacement(
-      Context.Sources, Context.getLocation(ID1, 1, 1), 6, "auto "));
-  Replaces.insert(tooling::Replacement(
-      Context.Sources, Context.getLocation(ID2, 2, 9), 1, "10"));
-  Replaces.insert(tooling::Replacement(
-      Context.Sources, Context.getLocation(ID1, 3, 10), 1, "12345678901"));
-
-  EXPECT_TRUE(formatAndApplyAllReplacements(
-      Replaces, Context.Rewrite, "{BasedOnStyle: LLVM, ColumnLimit: 20}"));
+  std::map<std::string, Replacements> FileToReplaces;
+  FileToReplaces[File1] = toReplacements(
+      {tooling::Replacement(Context.Sources, Context.getLocation(ID1, 1, 1), 6,
+                            "auto "),
+       tooling::Replacement(Context.Sources, Context.getLocation(ID1, 3, 10), 1,
+                            "12345678901")});
+  FileToReplaces[File2] = toReplacements(
+      {tooling::Replacement(Context.Sources, Context.getLocation(ID2, 1, 12), 0,
+                            "4567890123"),
+       tooling::Replacement(Context.Sources, Context.getLocation(ID2, 2, 9), 1,
+                            "10")});
+  EXPECT_TRUE(
+      formatAndApplyAllReplacements(FileToReplaces, Context.Rewrite,
+                                    "{BasedOnStyle: LLVM, ColumnLimit: 20}"));
   EXPECT_EQ(Expected1, Context.getRewrittenText(ID1));
   EXPECT_EQ(Expected2, Context.getRewrittenText(ID2));
 }
 
 TEST(ShiftedCodePositionTest, FindsNewCodePosition) {
-  Replacements Replaces;
-  Replaces.insert(Replacement("", 0, 1, ""));
-  Replaces.insert(Replacement("", 4, 3, " "));
+  Replacements Replaces =
+      toReplacements({Replacement("", 0, 1, ""), Replacement("", 4, 3, " ")});
   // Assume ' int   i;' is turned into 'int i;' and cursor is located at '|'.
-  EXPECT_EQ(0u, shiftedCodePosition(Replaces, 0)); // |int   i;
-  EXPECT_EQ(0u, shiftedCodePosition(Replaces, 1)); //  |nt   i;
-  EXPECT_EQ(1u, shiftedCodePosition(Replaces, 2)); //  i|t   i;
-  EXPECT_EQ(2u, shiftedCodePosition(Replaces, 3)); //  in|   i;
-  EXPECT_EQ(3u, shiftedCodePosition(Replaces, 4)); //  int|  i;
-  EXPECT_EQ(3u, shiftedCodePosition(Replaces, 5)); //  int | i;
-  EXPECT_EQ(3u, shiftedCodePosition(Replaces, 6)); //  int  |i;
-  EXPECT_EQ(4u, shiftedCodePosition(Replaces, 7)); //  int   |;
-  EXPECT_EQ(5u, shiftedCodePosition(Replaces, 8)); //  int   i|
-}
-
-// FIXME: Remove this test case when Replacements is implemented as std::vector
-// instead of std::set. The other ReplacementTest tests will need to be updated
-// at that point as well.
-TEST(ShiftedCodePositionTest, VectorFindsNewCodePositionWithInserts) {
-  std::vector<Replacement> Replaces;
-  Replaces.push_back(Replacement("", 0, 1, ""));
-  Replaces.push_back(Replacement("", 4, 3, " "));
-  // Assume ' int   i;' is turned into 'int i;' and cursor is located at '|'.
-  EXPECT_EQ(0u, shiftedCodePosition(Replaces, 0)); // |int   i;
-  EXPECT_EQ(0u, shiftedCodePosition(Replaces, 1)); //  |nt   i;
-  EXPECT_EQ(1u, shiftedCodePosition(Replaces, 2)); //  i|t   i;
-  EXPECT_EQ(2u, shiftedCodePosition(Replaces, 3)); //  in|   i;
-  EXPECT_EQ(3u, shiftedCodePosition(Replaces, 4)); //  int|  i;
-  EXPECT_EQ(3u, shiftedCodePosition(Replaces, 5)); //  int | i;
-  EXPECT_EQ(3u, shiftedCodePosition(Replaces, 6)); //  int  |i;
-  EXPECT_EQ(4u, shiftedCodePosition(Replaces, 7)); //  int   |;
-  EXPECT_EQ(5u, shiftedCodePosition(Replaces, 8)); //  int   i|
+  EXPECT_EQ(0u, Replaces.getShiftedCodePosition(0)); // |int   i;
+  EXPECT_EQ(0u, Replaces.getShiftedCodePosition(1)); //  |nt   i;
+  EXPECT_EQ(1u, Replaces.getShiftedCodePosition(2)); //  i|t   i;
+  EXPECT_EQ(2u, Replaces.getShiftedCodePosition(3)); //  in|   i;
+  EXPECT_EQ(3u, Replaces.getShiftedCodePosition(4)); //  int|  i;
+  EXPECT_EQ(3u, Replaces.getShiftedCodePosition(5)); //  int | i;
+  EXPECT_EQ(3u, Replaces.getShiftedCodePosition(6)); //  int  |i;
+  EXPECT_EQ(4u, Replaces.getShiftedCodePosition(7)); //  int   |;
+  EXPECT_EQ(5u, Replaces.getShiftedCodePosition(8)); //  int   i|
 }
 
 TEST(ShiftedCodePositionTest, FindsNewCodePositionWithInserts) {
-  Replacements Replaces;
-  Replaces.insert(Replacement("", 4, 0, "\"\n\""));
+  Replacements Replaces = toReplacements({Replacement("", 4, 0, "\"\n\"")});
   // Assume '"12345678"' is turned into '"1234"\n"5678"'.
-  EXPECT_EQ(3u, shiftedCodePosition(Replaces, 3)); // "123|5678"
-  EXPECT_EQ(7u, shiftedCodePosition(Replaces, 4)); // "1234|678"
-  EXPECT_EQ(8u, shiftedCodePosition(Replaces, 5)); // "12345|78"
+  EXPECT_EQ(3u, Replaces.getShiftedCodePosition(3)); // "123|5678"
+  EXPECT_EQ(7u, Replaces.getShiftedCodePosition(4)); // "1234|678"
+  EXPECT_EQ(8u, Replaces.getShiftedCodePosition(5)); // "12345|78"
 }
 
 TEST(ShiftedCodePositionTest, FindsNewCodePositionInReplacedText) {
-  Replacements Replaces;
   // Replace the first four characters with "abcd".
-  Replaces.insert(Replacement("", 0, 4, "abcd"));
+  auto Replaces = toReplacements({Replacement("", 0, 4, "abcd")});
   for (unsigned i = 0; i < 3; ++i)
-    EXPECT_EQ(i, shiftedCodePosition(Replaces, i));
+    EXPECT_EQ(i, Replaces.getShiftedCodePosition(i));
+}
+
+TEST(ShiftedCodePositionTest, NoReplacementText) {
+  Replacements Replaces = toReplacements({Replacement("", 0, 42, "")});
+  EXPECT_EQ(0u, Replaces.getShiftedCodePosition(0));
+  EXPECT_EQ(0u, Replaces.getShiftedCodePosition(39));
+  EXPECT_EQ(3u, Replaces.getShiftedCodePosition(45));
+  EXPECT_EQ(0u, Replaces.getShiftedCodePosition(42));
 }
 
 class FlushRewrittenFilesTest : public ::testing::Test {
@@ -305,9 +636,8 @@ public:
 
 TEST_F(FlushRewrittenFilesTest, StoresChangesOnDisk) {
   FileID ID = createFile("input.cpp", "line1\nline2\nline3\nline4");
-  Replacements Replaces;
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
-                              5, "replaced"));
+  Replacements Replaces = toReplacements({Replacement(
+      Context.Sources, Context.getLocation(ID, 2, 1), 5, "replaced")});
   EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
   EXPECT_FALSE(Context.Rewrite.overwriteChangedFiles());
   EXPECT_EQ("line1\nreplaced\nline3\nline4",
@@ -455,12 +785,11 @@ TEST(Range, contains) {
 TEST(Range, CalculateRangesOfReplacements) {
   // Before: aaaabbbbbbz
   // After : bbbbbbzzzzzzoooooooooooooooo
-  Replacements Replaces;
-  Replaces.insert(Replacement("foo", 0, 4, ""));
-  Replaces.insert(Replacement("foo", 10, 1, "zzzzzz"));
-  Replaces.insert(Replacement("foo", 11, 0, "oooooooooooooooo"));
+  Replacements Replaces = toReplacements(
+      {Replacement("foo", 0, 4, ""), Replacement("foo", 10, 1, "zzzzzz"),
+       Replacement("foo", 11, 0, "oooooooooooooooo")});
 
-  std::vector<Range> Ranges = calculateChangedRanges(Replaces);
+  std::vector<Range> Ranges = Replaces.getAffectedRanges();
 
   EXPECT_EQ(2ul, Ranges.size());
   EXPECT_TRUE(Ranges[0].getOffset() == 0);
@@ -469,25 +798,43 @@ TEST(Range, CalculateRangesOfReplacements) {
   EXPECT_TRUE(Ranges[1].getLength() == 22);
 }
 
+TEST(Range, CalculateRangesOfInsertionAroundReplacement) {
+  Replacements Replaces = toReplacements(
+      {Replacement("foo", 0, 2, ""), Replacement("foo", 0, 0, "ba")});
+
+  std::vector<Range> Ranges = Replaces.getAffectedRanges();
+
+  EXPECT_EQ(1ul, Ranges.size());
+  EXPECT_EQ(0u, Ranges[0].getOffset());
+  EXPECT_EQ(2u, Ranges[0].getLength());
+}
+
+TEST(Range, RangesAfterEmptyReplacements) {
+  std::vector<Range> Ranges = {Range(5, 6), Range(10, 5)};
+  Replacements Replaces;
+  std::vector<Range> Expected = {Range(5, 10)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
+}
+
 TEST(Range, RangesAfterReplacements) {
   std::vector<Range> Ranges = {Range(5, 2), Range(10, 5)};
-  Replacements Replaces = {Replacement("foo", 0, 2, "1234")};
+  Replacements Replaces = toReplacements({Replacement("foo", 0, 2, "1234")});
   std::vector<Range> Expected = {Range(0, 4), Range(7, 2), Range(12, 5)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 TEST(Range, RangesBeforeReplacements) {
   std::vector<Range> Ranges = {Range(5, 2), Range(10, 5)};
-  Replacements Replaces = {Replacement("foo", 20, 2, "1234")};
+  Replacements Replaces = toReplacements({Replacement("foo", 20, 2, "1234")});
   std::vector<Range> Expected = {Range(5, 2), Range(10, 5), Range(20, 4)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 TEST(Range, NotAffectedByReplacements) {
   std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(10, 5)};
-  Replacements Replaces = {Replacement("foo", 3, 2, "12"),
-                           Replacement("foo", 12, 2, "12"),
-                           Replacement("foo", 20, 5, "")};
+  Replacements Replaces = toReplacements({Replacement("foo", 3, 2, "12"),
+                                          Replacement("foo", 12, 2, "12"),
+                                          Replacement("foo", 20, 5, "")});
   std::vector<Range> Expected = {Range(0, 2), Range(3, 4), Range(10, 5),
                                  Range(20, 0)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
@@ -495,9 +842,9 @@ TEST(Range, NotAffectedByReplacements) {
 
 TEST(Range, RangesWithNonOverlappingReplacements) {
   std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(10, 5)};
-  Replacements Replaces = {Replacement("foo", 3, 1, ""),
-                           Replacement("foo", 6, 1, "123"),
-                           Replacement("foo", 20, 2, "12345")};
+  Replacements Replaces = toReplacements({Replacement("foo", 3, 1, ""),
+                                          Replacement("foo", 6, 1, "123"),
+                                          Replacement("foo", 20, 2, "12345")});
   std::vector<Range> Expected = {Range(0, 2), Range(3, 0), Range(4, 4),
                                  Range(11, 5), Range(21, 5)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
@@ -506,9 +853,9 @@ TEST(Range, RangesWithNonOverlappingReplacements) {
 TEST(Range, RangesWithOverlappingReplacements) {
   std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(15, 5),
                                Range(30, 5)};
-  Replacements Replaces = {
-      Replacement("foo", 1, 3, ""), Replacement("foo", 6, 1, "123"),
-      Replacement("foo", 13, 3, "1"), Replacement("foo", 25, 15, "")};
+  Replacements Replaces = toReplacements(
+      {Replacement("foo", 1, 3, ""), Replacement("foo", 6, 1, "123"),
+       Replacement("foo", 13, 3, "1"), Replacement("foo", 25, 15, "")});
   std::vector<Range> Expected = {Range(0, 1), Range(2, 4), Range(12, 5),
                                  Range(22, 0)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
@@ -516,122 +863,52 @@ TEST(Range, RangesWithOverlappingReplacements) {
 
 TEST(Range, MergeIntoOneRange) {
   std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(15, 5)};
-  Replacements Replaces = {Replacement("foo", 1, 15, "1234567890")};
+  Replacements Replaces =
+      toReplacements({Replacement("foo", 1, 15, "1234567890")});
   std::vector<Range> Expected = {Range(0, 15)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 TEST(Range, ReplacementsStartingAtRangeOffsets) {
   std::vector<Range> Ranges = {Range(0, 2), Range(5, 5), Range(15, 5)};
-  Replacements Replaces = {
-      Replacement("foo", 0, 2, "12"), Replacement("foo", 5, 1, "123"),
-      Replacement("foo", 7, 4, "12345"), Replacement("foo", 15, 10, "12")};
+  Replacements Replaces = toReplacements(
+      {Replacement("foo", 0, 2, "12"), Replacement("foo", 5, 1, "123"),
+       Replacement("foo", 7, 4, "12345"), Replacement("foo", 15, 10, "12")});
   std::vector<Range> Expected = {Range(0, 2), Range(5, 9), Range(18, 2)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 TEST(Range, ReplacementsEndingAtRangeEnds) {
   std::vector<Range> Ranges = {Range(0, 2), Range(5, 2), Range(15, 5)};
-  Replacements Replaces = {Replacement("foo", 6, 1, "123"),
-                           Replacement("foo", 17, 3, "12")};
+  Replacements Replaces = toReplacements(
+      {Replacement("foo", 6, 1, "123"), Replacement("foo", 17, 3, "12")});
   std::vector<Range> Expected = {Range(0, 2), Range(5, 4), Range(17, 4)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 TEST(Range, AjacentReplacements) {
   std::vector<Range> Ranges = {Range(0, 0), Range(15, 5)};
-  Replacements Replaces = {Replacement("foo", 1, 2, "123"),
-                           Replacement("foo", 12, 3, "1234")};
+  Replacements Replaces = toReplacements(
+      {Replacement("foo", 1, 2, "123"), Replacement("foo", 12, 3, "1234")});
   std::vector<Range> Expected = {Range(0, 0), Range(1, 3), Range(13, 9)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 TEST(Range, MergeRangesAfterReplacements) {
   std::vector<Range> Ranges = {Range(8, 0), Range(5, 2), Range(9, 0), Range(0, 1)};
-  Replacements Replaces = {Replacement("foo", 1, 3, ""),
-                           Replacement("foo", 7, 0, "12"), Replacement("foo", 9, 2, "")};
-  std::vector<Range> Expected = {Range(0, 1), Range(2, 4), Range(7, 0), Range(8, 0)};
+  Replacements Replaces = toReplacements({Replacement("foo", 1, 3, ""),
+                                          Replacement("foo", 7, 0, "12"),
+                                          Replacement("foo", 9, 2, "")});
+  std::vector<Range> Expected = {Range(0, 1), Range(2, 4), Range(7, 0),
+                                 Range(8, 0)};
   EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
-TEST(DeduplicateTest, removesDuplicates) {
-  std::vector<Replacement> Input;
-  Input.push_back(Replacement("fileA", 50, 0, " foo "));
-  Input.push_back(Replacement("fileA", 10, 3, " bar "));
-  Input.push_back(Replacement("fileA", 10, 2, " bar ")); // Length differs
-  Input.push_back(Replacement("fileA", 9,  3, " bar ")); // Offset differs
-  Input.push_back(Replacement("fileA", 50, 0, " foo ")); // Duplicate
-  Input.push_back(Replacement("fileA", 51, 3, " bar "));
-  Input.push_back(Replacement("fileB", 51, 3, " bar ")); // Filename differs!
-  Input.push_back(Replacement("fileB", 60, 1, " bar "));
-  Input.push_back(Replacement("fileA", 60, 2, " bar "));
-  Input.push_back(Replacement("fileA", 51, 3, " moo ")); // Replacement text
-                                                         // differs!
-
-  std::vector<Replacement> Expected;
-  Expected.push_back(Replacement("fileA", 9,  3, " bar "));
-  Expected.push_back(Replacement("fileA", 10, 2, " bar "));
-  Expected.push_back(Replacement("fileA", 10, 3, " bar "));
-  Expected.push_back(Replacement("fileA", 50, 0, " foo "));
-  Expected.push_back(Replacement("fileA", 51, 3, " bar "));
-  Expected.push_back(Replacement("fileA", 51, 3, " moo "));
-  Expected.push_back(Replacement("fileB", 60, 1, " bar "));
-  Expected.push_back(Replacement("fileA", 60, 2, " bar "));
-
-  std::vector<Range> Conflicts; // Ignored for this test
-  deduplicate(Input, Conflicts);
-
-  EXPECT_EQ(3U, Conflicts.size());
-  EXPECT_EQ(Expected, Input);
-}
-
-TEST(DeduplicateTest, detectsConflicts) {
-  {
-    std::vector<Replacement> Input;
-    Input.push_back(Replacement("fileA", 0, 5, " foo "));
-    Input.push_back(Replacement("fileA", 0, 5, " foo ")); // Duplicate not a
-                                                          // conflict.
-    Input.push_back(Replacement("fileA", 2, 6, " bar "));
-    Input.push_back(Replacement("fileA", 7, 3, " moo "));
-
-    std::vector<Range> Conflicts;
-    deduplicate(Input, Conflicts);
-
-    // One duplicate is removed and the remaining three items form one
-    // conflicted range.
-    ASSERT_EQ(3u, Input.size());
-    ASSERT_EQ(1u, Conflicts.size());
-    ASSERT_EQ(0u, Conflicts.front().getOffset());
-    ASSERT_EQ(3u, Conflicts.front().getLength());
-  }
-  {
-    std::vector<Replacement> Input;
-
-    // Expected sorted order is shown. It is the sorted order to which the
-    // returned conflict info refers to.
-    Input.push_back(Replacement("fileA", 0,  5, " foo "));  // 0
-    Input.push_back(Replacement("fileA", 5,  5, " bar "));  // 1
-    Input.push_back(Replacement("fileA", 6,  0, " bar "));  // 3
-    Input.push_back(Replacement("fileA", 5,  5, " moo "));  // 2
-    Input.push_back(Replacement("fileA", 7,  2, " bar "));  // 4
-    Input.push_back(Replacement("fileA", 15, 5, " golf ")); // 5
-    Input.push_back(Replacement("fileA", 16, 5, " bag "));  // 6
-    Input.push_back(Replacement("fileA", 10, 3, " club ")); // 7
-
-    // #3 is special in that it is completely contained by another conflicting
-    // Replacement. #4 ensures #3 hasn't messed up the conflicting range size.
-
-    std::vector<Range> Conflicts;
-    deduplicate(Input, Conflicts);
-
-    // No duplicates
-    ASSERT_EQ(8u, Input.size());
-    ASSERT_EQ(2u, Conflicts.size());
-    ASSERT_EQ(1u, Conflicts[0].getOffset());
-    ASSERT_EQ(4u, Conflicts[0].getLength());
-    ASSERT_EQ(6u, Conflicts[1].getOffset());
-    ASSERT_EQ(2u, Conflicts[1].getLength());
-  }
+TEST(Range, ConflictingRangesBeforeReplacements) {
+  std::vector<Range> Ranges = {Range(8, 3), Range(5, 4), Range(9, 1)};
+  Replacements Replaces = toReplacements({Replacement("foo", 1, 3, "")});
+  std::vector<Range> Expected = {Range(1, 0), Range(2, 6)};
+  EXPECT_EQ(Expected, calculateRangesAfterReplacements(Replaces, Ranges));
 }
 
 class MergeReplacementsTest : public ::testing::Test {
@@ -647,7 +924,7 @@ protected:
     EXPECT_EQ(Intermediate, *AfterFirst);
     EXPECT_EQ(Result, *InSequenceRewrite);
 
-    tooling::Replacements Merged = mergeReplacements(First, Second);
+    tooling::Replacements Merged = First.merge(Second);
     auto MergedRewrite = applyAllReplacements(Code, Merged);
     EXPECT_TRUE(static_cast<bool>(MergedRewrite));
     EXPECT_EQ(*InSequenceRewrite, *MergedRewrite);
@@ -661,7 +938,7 @@ protected:
     auto AfterFirst = applyAllReplacements(Code, First);
     EXPECT_TRUE(static_cast<bool>(AfterFirst));
     auto InSequenceRewrite = applyAllReplacements(*AfterFirst, Second);
-    tooling::Replacements Merged = mergeReplacements(First, Second);
+    tooling::Replacements Merged = First.merge(Second);
     auto MergedRewrite = applyAllReplacements(Code, Merged);
     EXPECT_TRUE(static_cast<bool>(MergedRewrite));
     EXPECT_EQ(*InSequenceRewrite, *MergedRewrite);
@@ -674,62 +951,142 @@ protected:
 
 TEST_F(MergeReplacementsTest, Offsets) {
   mergeAndTestRewrite("aaa", "aabab", "cacabab",
-                      {{"", 2, 0, "b"}, {"", 3, 0, "b"}},
-                      {{"", 0, 0, "c"}, {"", 1, 0, "c"}});
+                      toReplacements({{"", 2, 0, "b"}, {"", 3, 0, "b"}}),
+                      toReplacements({{"", 0, 0, "c"}, {"", 1, 0, "c"}}));
   mergeAndTestRewrite("aaa", "babaa", "babacac",
-                      {{"", 0, 0, "b"}, {"", 1, 0, "b"}},
-                      {{"", 4, 0, "c"}, {"", 5, 0, "c"}});
-  mergeAndTestRewrite("aaaa", "aaa", "aac", {{"", 1, 1, ""}},
-                      {{"", 2, 1, "c"}});
+                      toReplacements({{"", 0, 0, "b"}, {"", 1, 0, "b"}}),
+                      toReplacements({{"", 4, 0, "c"}, {"", 5, 0, "c"}}));
+  mergeAndTestRewrite("aaaa", "aaa", "aac", toReplacements({{"", 1, 1, ""}}),
+                      toReplacements({{"", 2, 1, "c"}}));
 
   mergeAndTestRewrite("aa", "bbabba", "bbabcba",
-                      {{"", 0, 0, "bb"}, {"", 1, 0, "bb"}}, {{"", 4, 0, "c"}});
+                      toReplacements({{"", 0, 0, "bb"}, {"", 1, 0, "bb"}}),
+                      toReplacements({{"", 4, 0, "c"}}));
 }
 
 TEST_F(MergeReplacementsTest, Concatenations) {
   // Basic concatenations. It is important to merge these into a single
   // replacement to ensure the correct order.
-  EXPECT_EQ((Replacements{{"", 0, 0, "ab"}}),
-            mergeReplacements({{"", 0, 0, "a"}}, {{"", 1, 0, "b"}}));
-  EXPECT_EQ((Replacements{{"", 0, 0, "ba"}}),
-            mergeReplacements({{"", 0, 0, "a"}}, {{"", 0, 0, "b"}}));
-  mergeAndTestRewrite("", "a", "ab", {{"", 0, 0, "a"}}, {{"", 1, 0, "b"}});
-  mergeAndTestRewrite("", "a", "ba", {{"", 0, 0, "a"}}, {{"", 0, 0, "b"}});
+  {
+    auto First = toReplacements({{"", 0, 0, "a"}});
+    auto Second = toReplacements({{"", 1, 0, "b"}});
+    EXPECT_EQ(toReplacements({{"", 0, 0, "ab"}}), First.merge(Second));
+  }
+  {
+    auto First = toReplacements({{"", 0, 0, "a"}});
+    auto Second = toReplacements({{"", 0, 0, "b"}});
+    EXPECT_EQ(toReplacements({{"", 0, 0, "ba"}}), First.merge(Second));
+  }
+  mergeAndTestRewrite("", "a", "ab", toReplacements({{"", 0, 0, "a"}}),
+                      toReplacements({{"", 1, 0, "b"}}));
+  mergeAndTestRewrite("", "a", "ba", toReplacements({{"", 0, 0, "a"}}),
+                      toReplacements({{"", 0, 0, "b"}}));
 }
 
 TEST_F(MergeReplacementsTest, NotChangingLengths) {
-  mergeAndTestRewrite("aaaa", "abba", "acca", {{"", 1, 2, "bb"}},
-                      {{"", 1, 2, "cc"}});
-  mergeAndTestRewrite("aaaa", "abba", "abcc", {{"", 1, 2, "bb"}},
-                      {{"", 2, 2, "cc"}});
-  mergeAndTestRewrite("aaaa", "abba", "ccba", {{"", 1, 2, "bb"}},
-                      {{"", 0, 2, "cc"}});
+  mergeAndTestRewrite("aaaa", "abba", "acca",
+                      toReplacements({{"", 1, 2, "bb"}}),
+                      toReplacements({{"", 1, 2, "cc"}}));
+  mergeAndTestRewrite("aaaa", "abba", "abcc",
+                      toReplacements({{"", 1, 2, "bb"}}),
+                      toReplacements({{"", 2, 2, "cc"}}));
+  mergeAndTestRewrite("aaaa", "abba", "ccba",
+                      toReplacements({{"", 1, 2, "bb"}}),
+                      toReplacements({{"", 0, 2, "cc"}}));
   mergeAndTestRewrite("aaaaaa", "abbdda", "abccda",
-                      {{"", 1, 2, "bb"}, {"", 3, 2, "dd"}}, {{"", 2, 2, "cc"}});
+                      toReplacements({{"", 1, 2, "bb"}, {"", 3, 2, "dd"}}),
+                      toReplacements({{"", 2, 2, "cc"}}));
 }
 
 TEST_F(MergeReplacementsTest, OverlappingRanges) {
   mergeAndTestRewrite("aaa", "bbd", "bcbcd",
-                      {{"", 0, 1, "bb"}, {"", 1, 2, "d"}},
-                      {{"", 1, 0, "c"}, {"", 2, 0, "c"}});
+                      toReplacements({{"", 0, 1, "bb"}, {"", 1, 2, "d"}}),
+                      toReplacements({{"", 1, 0, "c"}, {"", 2, 0, "c"}}));
 
-  mergeAndTestRewrite("aaaa", "aabbaa", "acccca", {{"", 2, 0, "bb"}},
-                      {{"", 1, 4, "cccc"}});
+  mergeAndTestRewrite("aaaa", "aabbaa", "acccca",
+                      toReplacements({{"", 2, 0, "bb"}}),
+                      toReplacements({{"", 1, 4, "cccc"}}));
   mergeAndTestRewrite("aaaa", "aababa", "acccca",
-                      {{"", 2, 0, "b"}, {"", 3, 0, "b"}}, {{"", 1, 4, "cccc"}});
-  mergeAndTestRewrite("aaaaaa", "abbbba", "abba", {{"", 1, 4, "bbbb"}},
-                      {{"", 2, 2, ""}});
-  mergeAndTestRewrite("aaaa", "aa", "cc", {{"", 1, 1, ""}, {"", 2, 1, ""}},
-                      {{"", 0, 2, "cc"}});
-  mergeAndTestRewrite("aa", "abbba", "abcbcba", {{"", 1, 0, "bbb"}},
-                      {{"", 2, 0, "c"}, {"", 3, 0, "c"}});
-
-  mergeAndTestRewrite("aaa", "abbab", "ccdd",
-                      {{"", 0, 1, ""}, {"", 2, 0, "bb"}, {"", 3, 0, "b"}},
-                      {{"", 0, 2, "cc"}, {"", 2, 3, "dd"}});
-  mergeAndTestRewrite("aa", "babbab", "ccdd",
-                      {{"", 0, 0, "b"}, {"", 1, 0, "bb"}, {"", 2, 0, "b"}},
-                      {{"", 0, 3, "cc"}, {"", 3, 3, "dd"}});
+                      toReplacements({{"", 2, 0, "b"}, {"", 3, 0, "b"}}),
+                      toReplacements({{"", 1, 4, "cccc"}}));
+  mergeAndTestRewrite("aaaaaa", "abbbba", "abba",
+                      toReplacements({{"", 1, 4, "bbbb"}}),
+                      toReplacements({{"", 2, 2, ""}}));
+  mergeAndTestRewrite("aaaa", "aa", "cc",
+                      toReplacements({{"", 1, 1, ""}, {"", 2, 1, ""}}),
+                      toReplacements({{"", 0, 2, "cc"}}));
+  mergeAndTestRewrite("aa", "abbba", "abcbcba",
+                      toReplacements({{"", 1, 0, "bbb"}}),
+                      toReplacements({{"", 2, 0, "c"}, {"", 3, 0, "c"}}));
+
+  mergeAndTestRewrite(
+      "aaa", "abbab", "ccdd",
+      toReplacements({{"", 0, 1, ""}, {"", 2, 0, "bb"}, {"", 3, 0, "b"}}),
+      toReplacements({{"", 0, 2, "cc"}, {"", 2, 3, "dd"}}));
+  mergeAndTestRewrite(
+      "aa", "babbab", "ccdd",
+      toReplacements({{"", 0, 0, "b"}, {"", 1, 0, "bb"}, {"", 2, 0, "b"}}),
+      toReplacements({{"", 0, 3, "cc"}, {"", 3, 3, "dd"}}));
+}
+
+TEST(DeduplicateByFileTest, PathsWithDots) {
+  std::map<std::string, Replacements> FileToReplaces;
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
+      new vfs::InMemoryFileSystem());
+  FileManager FileMgr(FileSystemOptions(), VFS);
+#if !defined(LLVM_ON_WIN32)
+  StringRef Path1 = "a/b/.././c.h";
+  StringRef Path2 = "a/c.h";
+#else
+  StringRef Path1 = "a\\b\\..\\.\\c.h";
+  StringRef Path2 = "a\\c.h";
+#endif
+  EXPECT_TRUE(VFS->addFile(Path1, 0, llvm::MemoryBuffer::getMemBuffer("")));
+  EXPECT_TRUE(VFS->addFile(Path2, 0, llvm::MemoryBuffer::getMemBuffer("")));
+  FileToReplaces[Path1] = Replacements();
+  FileToReplaces[Path2] = Replacements();
+  FileToReplaces = groupReplacementsByFile(FileMgr, FileToReplaces);
+  EXPECT_EQ(1u, FileToReplaces.size());
+  EXPECT_EQ(Path1, FileToReplaces.begin()->first);
+}
+
+TEST(DeduplicateByFileTest, PathWithDotSlash) {
+  std::map<std::string, Replacements> FileToReplaces;
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
+      new vfs::InMemoryFileSystem());
+  FileManager FileMgr(FileSystemOptions(), VFS);
+#if !defined(LLVM_ON_WIN32)
+  StringRef Path1 = "./a/b/c.h";
+  StringRef Path2 = "a/b/c.h";
+#else
+  StringRef Path1 = ".\\a\\b\\c.h";
+  StringRef Path2 = "a\\b\\c.h";
+#endif
+  EXPECT_TRUE(VFS->addFile(Path1, 0, llvm::MemoryBuffer::getMemBuffer("")));
+  EXPECT_TRUE(VFS->addFile(Path2, 0, llvm::MemoryBuffer::getMemBuffer("")));
+  FileToReplaces[Path1] = Replacements();
+  FileToReplaces[Path2] = Replacements();
+  FileToReplaces = groupReplacementsByFile(FileMgr, FileToReplaces);
+  EXPECT_EQ(1u, FileToReplaces.size());
+  EXPECT_EQ(Path1, FileToReplaces.begin()->first);
+}
+
+TEST(DeduplicateByFileTest, NonExistingFilePath) {
+  std::map<std::string, Replacements> FileToReplaces;
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
+      new vfs::InMemoryFileSystem());
+  FileManager FileMgr(FileSystemOptions(), VFS);
+#if !defined(LLVM_ON_WIN32)
+  StringRef Path1 = "./a/b/c.h";
+  StringRef Path2 = "a/b/c.h";
+#else
+  StringRef Path1 = ".\\a\\b\\c.h";
+  StringRef Path2 = "a\\b\\c.h";
+#endif
+  FileToReplaces[Path1] = Replacements();
+  FileToReplaces[Path2] = Replacements();
+  FileToReplaces = groupReplacementsByFile(FileMgr, FileToReplaces);
+  EXPECT_TRUE(FileToReplaces.empty());
 }
 
 } // end namespace tooling
diff --git a/unittests/Tooling/ReplacementTest.h b/unittests/Tooling/ReplacementTest.h
new file mode 100644
index 0000000000000..b6fe5c79b7bef
--- /dev/null
+++ b/unittests/Tooling/ReplacementTest.h
@@ -0,0 +1,56 @@
+//===- unittest/Tooling/ReplacementTest.h - Replacements related test------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines utility class and function for Replacement related tests.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_UNITTESTS_TOOLING_REPLACEMENTTESTBASE_H
+#define LLVM_CLANG_UNITTESTS_TOOLING_REPLACEMENTTESTBASE_H
+
+#include "RewriterTestContext.h"
+#include "clang/Tooling/Core/Replacement.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace tooling {
+
+/// \brief Converts a set of replacements to Replacements class.
+/// \return A Replacements class containing \p Replaces on success; otherwise,
+/// an empty Replacements is returned.
+inline tooling::Replacements
+toReplacements(const std::set<tooling::Replacement> &Replaces) {
+  tooling::Replacements Result;
+  for (const auto &R : Replaces) {
+    auto Err = Result.add(R);
+    EXPECT_TRUE(!Err);
+    if (Err) {
+      llvm::errs() << llvm::toString(std::move(Err)) << "\n";
+      return tooling::Replacements();
+    }
+  }
+  return Result;
+}
+
+/// \brief A utility class for replacement related tests.
+class ReplacementTest : public ::testing::Test {
+protected:
+  tooling::Replacement createReplacement(SourceLocation Start, unsigned Length,
+                                         llvm::StringRef ReplacementText) {
+    return tooling::Replacement(Context.Sources, Start, Length,
+                                ReplacementText);
+  }
+
+  RewriterTestContext Context;
+};
+
+} // namespace tooling
+} // namespace clang
+
+#endif // LLVM_CLANG_UNITTESTS_TOOLING_REPLACEMENTTESTBASE_H
diff --git a/unittests/Tooling/RewriterTest.cpp b/unittests/Tooling/RewriterTest.cpp
index e8afedb01174f..4305d421e1cba 100644
--- a/unittests/Tooling/RewriterTest.cpp
+++ b/unittests/Tooling/RewriterTest.cpp
@@ -39,8 +39,11 @@ TEST(Rewriter, ContinuesOverwritingFilesOnError) {
 
 TEST(Rewriter, AdjacentInsertAndDelete) {
   Replacements Replaces;
-  Replaces.insert(Replacement("<file>", 6, 6, ""));
-  Replaces.insert(Replacement("<file>", 6, 0, "replaced\n"));
+  auto Err = Replaces.add(Replacement("<file>", 6, 6, ""));
+  EXPECT_TRUE(!Err);
+  Replaces =
+      Replaces.merge(Replacements(Replacement("<file>", 6, 0, "replaced\n")));
+
   auto Rewritten = applyAllReplacements("line1\nline2\nline3\nline4", Replaces);
   EXPECT_TRUE(static_cast<bool>(Rewritten));
   EXPECT_EQ("line1\nreplaced\nline3\nline4", *Rewritten);
diff --git a/unittests/Tooling/TestVisitor.h b/unittests/Tooling/TestVisitor.h
index f4a00394487bc..a762ec8b14530 100644
--- a/unittests/Tooling/TestVisitor.h
+++ b/unittests/Tooling/TestVisitor.h
@@ -43,6 +43,7 @@ public:
     Lang_C,
     Lang_CXX98,
     Lang_CXX11,
+    Lang_CXX14,
     Lang_OBJC,
     Lang_OBJCXX11,
     Lang_CXX = Lang_CXX98
@@ -55,6 +56,7 @@ public:
       case Lang_C: Args.push_back("-std=c99"); break;
       case Lang_CXX98: Args.push_back("-std=c++98"); break;
       case Lang_CXX11: Args.push_back("-std=c++11"); break;
+      case Lang_CXX14: Args.push_back("-std=c++14"); break;
       case Lang_OBJC: Args.push_back("-ObjC"); break;
       case Lang_OBJCXX11:
         Args.push_back("-ObjC++");
@@ -127,9 +129,12 @@ public:
   /// \brief Expect 'Match' to occur at the given 'Line' and 'Column'.
   ///
   /// Any number of expected matches can be set by calling this repeatedly.
-  /// Each is expected to be matched exactly once.
-  void ExpectMatch(Twine Match, unsigned Line, unsigned Column) {
-    ExpectedMatches.push_back(ExpectedMatch(Match, Line, Column));
+  /// Each is expected to be matched 'Times' number of times. (This is useful in
+  /// cases in which different AST nodes can match at the same source code
+  /// location.)
+  void ExpectMatch(Twine Match, unsigned Line, unsigned Column,
+                   unsigned Times = 1) {
+    ExpectedMatches.push_back(ExpectedMatch(Match, Line, Column, Times));
   }
 
   /// \brief Checks that all expected matches have been found.
@@ -200,14 +205,17 @@ protected:
   };
 
   struct ExpectedMatch {
-    ExpectedMatch(Twine Name, unsigned LineNumber, unsigned ColumnNumber)
-      : Candidate(Name, LineNumber, ColumnNumber), Found(false) {}
+    ExpectedMatch(Twine Name, unsigned LineNumber, unsigned ColumnNumber,
+                  unsigned Times)
+        : Candidate(Name, LineNumber, ColumnNumber), TimesExpected(Times),
+          TimesSeen(0) {}
 
     void UpdateFor(StringRef Name, FullSourceLoc Location, SourceManager &SM) {
       if (Candidate.Matches(Name, Location)) {
-        EXPECT_TRUE(!Found);
-        Found = true;
-      } else if (!Found && Candidate.PartiallyMatches(Name, Location)) {
+        EXPECT_LT(TimesSeen, TimesExpected);
+        ++TimesSeen;
+      } else if (TimesSeen < TimesExpected &&
+                 Candidate.PartiallyMatches(Name, Location)) {
         llvm::raw_string_ostream Stream(PartialMatches);
         Stream << ", partial match: \"" << Name << "\" at ";
         Location.print(Stream, SM);
@@ -215,7 +223,7 @@ protected:
     }
 
     void ExpectFound() const {
-      EXPECT_TRUE(Found)
+      EXPECT_EQ(TimesExpected, TimesSeen)
           << "Expected \"" << Candidate.ExpectedName
           << "\" at " << Candidate.LineNumber
           << ":" << Candidate.ColumnNumber << PartialMatches;
@@ -223,7 +231,8 @@ protected:
 
     MatchCandidate Candidate;
     std::string PartialMatches;
-    bool Found;
+    unsigned TimesExpected;
+    unsigned TimesSeen;
   };
 
   std::vector<MatchCandidate> DisallowedMatches;
diff --git a/unittests/Tooling/ToolingTest.cpp b/unittests/Tooling/ToolingTest.cpp
index 10ac0c33ed85d..68b5ed21059bc 100644
--- a/unittests/Tooling/ToolingTest.cpp
+++ b/unittests/Tooling/ToolingTest.cpp
@@ -18,8 +18,9 @@
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Config/llvm-config.h"
-#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/Path.h"
 #include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
 #include "gtest/gtest.h"
 #include <algorithm>
 #include <string>
@@ -331,6 +332,44 @@ TEST(runToolOnCodeWithArgs, TestNoDepFile) {
   EXPECT_FALSE(llvm::sys::fs::remove(DepFilePath.str()));
 }
 
+struct CheckColoredDiagnosticsAction : public clang::ASTFrontendAction {
+  CheckColoredDiagnosticsAction(bool ShouldShowColor)
+      : ShouldShowColor(ShouldShowColor) {}
+  std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &Compiler,
+                                                 StringRef) override {
+    if (Compiler.getDiagnosticOpts().ShowColors != ShouldShowColor)
+      Compiler.getDiagnostics().Report(
+          Compiler.getDiagnostics().getCustomDiagID(
+              DiagnosticsEngine::Fatal,
+              "getDiagnosticOpts().ShowColors != ShouldShowColor"));
+    return llvm::make_unique<ASTConsumer>();
+  }
+
+private:
+  bool ShouldShowColor = true;
+};
+
+TEST(runToolOnCodeWithArgs, DiagnosticsColor) {
+
+  EXPECT_TRUE(runToolOnCodeWithArgs(new CheckColoredDiagnosticsAction(true), "",
+                                    {"-fcolor-diagnostics"}));
+  EXPECT_TRUE(runToolOnCodeWithArgs(new CheckColoredDiagnosticsAction(false),
+                                    "", {"-fno-color-diagnostics"}));
+  EXPECT_TRUE(
+      runToolOnCodeWithArgs(new CheckColoredDiagnosticsAction(true), "",
+                            {"-fno-color-diagnostics", "-fcolor-diagnostics"}));
+  EXPECT_TRUE(
+      runToolOnCodeWithArgs(new CheckColoredDiagnosticsAction(false), "",
+                            {"-fcolor-diagnostics", "-fno-color-diagnostics"}));
+  EXPECT_TRUE(runToolOnCodeWithArgs(
+      new CheckColoredDiagnosticsAction(true), "",
+      {"-fno-color-diagnostics", "-fdiagnostics-color=always"}));
+
+  // Check that this test would fail if ShowColors is not what it should.
+  EXPECT_FALSE(runToolOnCodeWithArgs(new CheckColoredDiagnosticsAction(false),
+                                     "", {"-fcolor-diagnostics"}));
+}
+
 TEST(ClangToolTest, ArgumentAdjusters) {
   FixedCompilationDatabase Compilations("/", std::vector<std::string>());