Change the implementation of tooling::Replacements to std::vector.

[ioeric]

Summary

Change the implementation of tooling::Replacements to std::vector.

Pair programmed with Martin Böhme!

[klimek]

lib/Tooling/Core/Replacement.cpp

141

Why?

211–212

Ah, so, I believe this is exactly what we're trying to get rid of:
Making applyAllReplacements always unique / unstable-sort doesn't help with the underlying problem, which is that we have some edit sequences we cannot express (which I believe this change is all about).
For example:
insert(0, "a"), insert(0, "a") might want to insert "a" 2 times at 0
insert(0, "a"), insert(0, "b"), insert(0, "a") leads to a different end-state depending on the sort order.

[ioeric]

• Remove shiftedCodePositionInternal.

lib/Tooling/Core/Replacement.cpp

141

Previously, there are two implementations of shiftedCodePosition, and both call this template function. Now that there is only one version, we can get rid of the template.

211

This ensures that the behavior is the same as the std::set version of Replacements.

[ioeric]

lib/Tooling/Core/Replacement.cpp

211–212

Ah, I see. So, what we want is actually stable_sort without deduplicating?

[ioeric]

lib/Tooling/Core/Replacement.cpp

211–212

Hmm, we might need more than that. I'm looking into this.

[ioeric]

• Preserve applyAllReplacements' behavior with sorting+deduplicating.

[ioeric]

lib/Tooling/Core/Replacement.cpp

210–211

As per offline discussion with Manuel, we will preserve the behavior of applyAllReplacements as before (std::set version) with sorting and deduplicating for now. For the problems above (i.e. allowing identical replacements), we might want to create a new set of interfaces (possibly) without preprocessing replacements before applying them and let users ensure that replacements are correct by themselves.

[ioeric]

• Make callers responsile for deduplicate replacements before calling applyAllReplacements.

[ioeric]

• Make LessNoPath consistent with operator< for tooling::Replacement.

[mboehme]

include/clang/Format/Format.h

784

Add "///" at beginning of line? (I.e. make this an empty comment line, not a plain empty line.)

lib/Tooling/Core/Replacement.cpp

209

I think "Replaces" can go back to being a const reference. (We originally changed this to pass-by-value because we were sorting the replacements inside the function, but we're no longer doing that.)

223–224

Again, I think "Replaces" can go back to being a const reference here.

[ioeric]

• Make applyAllReplcements take const reference Replaces again.

include/clang/Format/Format.h

784

Thanks for the catches! :)

[ioeric]

Abondan in favor of http://reviews.llvm.org/D21748

include/clang/Format/Format.h

 /// When ``BasedOnStyle`` is not present, options not present in the YAML
 /// document, are retained in \p Style.
 std::error_code parseConfiguration(StringRef Text, FormatStyle *Style);
 
 /// \brief Gets configuration in a YAML string.
 std::string configurationAsText(const FormatStyle &Style);
 
 /// \brief Returns the replacements necessary to sort all ``#include`` blocks
-/// that are affected by ``Ranges``.
+/// that are affected by ``Ranges``. Replacements will be sorted,
+/// non-overlapping, and ready to be applied.
 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
                                    ArrayRef<tooling::Range> Ranges,
                                    StringRef FileName,
                                    unsigned *Cursor = nullptr);
 
 /// \brief Returns the replacements corresponding to applying and formatting
-/// \p Replaces.
+/// \p Replaces. Replacements will be sorted, non-overlapping, and ready to be
+/// applied.
+/// \pre \p Replaces must be ready to be applied.
 tooling::Replacements formatReplacements(StringRef Code,
                                          const tooling::Replacements &Replaces,
                                          const FormatStyle &Style);
 
 /// \brief Returns the replacements corresponding to applying \p Replaces and
-/// cleaning up the code after that.
+/// cleaning up the code after that. Replacements will be sorted,
+/// non-overlapping, and ready to be applied.
+///
 /// This also inserts a C++ #include directive into the correct block if the
 /// replacement corresponding to the header insertion has offset UINT_MAX.
+///
+/// \pre \p Replaces must be ready to be applied.
 tooling::Replacements
 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
                           const FormatStyle &Style);
 
 /// \brief Reformats the given \p Ranges in the file \p ID.
 ///
 /// Each range is extended on either end to its next bigger logic unit, i.e.
 /// everything that might influence its formatting or might be influenced by its
 /// formatting.
 ///
-/// Returns the ``Replacements`` necessary to make all \p Ranges comply with
-/// \p Style.
+/// Returns the ``Replacements`` necessary to make all \p Ranges comply with \p
+/// Style. ``Replacements`` will be sorted, non-overlapping, and ready to be
+/// applied.
 ///
 /// If ``IncompleteFormat`` is non-null, its value will be set to true if any
 /// of the affected ranges were not formatted due to a non-recoverable syntax
 /// error.
 tooling::Replacements reformat(const FormatStyle &Style,
                                SourceManager &SourceMgr, FileID ID,
                                ArrayRef<CharSourceRange> Ranges,
                                bool *IncompleteFormat = nullptr);
 
 /// \brief Reformats the given \p Ranges in \p Code.
 ///
 /// Otherwise identical to the reformat() function using a file ID.
 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
                                ArrayRef<tooling::Range> Ranges,
                                StringRef FileName = "<stdin>",
                                bool *IncompleteFormat = nullptr);
 
 /// \brief Clean up any erroneous/redundant code in the given \p Ranges in the
 /// file \p ID.
 ///
-/// Returns the ``Replacements`` that clean up all \p Ranges in the file \p ID.
+/// Returns the ``Replacements`` (ready to be applied) that clean up all \p
+/// Ranges in the file \p ID. ``Replacements`` will be sorted, non-overlapping,
+/// and ready to be applied.
 tooling::Replacements cleanup(const FormatStyle &Style,
                               SourceManager &SourceMgr, FileID ID,
                               ArrayRef<CharSourceRange> Ranges);
 
 /// \brief Clean up any erroneous/redundant code in the given \p Ranges in \p
 /// Code.
 ///
 /// Otherwise identical to the cleanup() function using a file ID.

include/clang/Tooling/Core/Replacement.h

 };
 
 /// \brief Less-than operator between two Replacements.
 bool operator<(const Replacement &LHS, const Replacement &RHS);
 
 /// \brief Equal-to operator between two Replacements.
 bool operator==(const Replacement &LHS, const Replacement &RHS);
 
-/// \brief A set of Replacements.
-/// FIXME: Change to a vector and deduplicate in the RefactoringTool.
-typedef std::set<Replacement> Replacements;
+/// \brief A vector of Replacements.
+typedef std::vector<Replacement> Replacements;
 
 /// \brief Apply all replacements in \p Replaces to the Rewriter \p Rewrite.
+/// It is callers' responsibility to ensure replacements are good to apply (i.e
+/// deduplicated or sorted). This function simply applies all replacements
+/// without preprocessing them.
 ///
 /// Replacement applications happen independently of the success of
 /// other applications.
 ///
 /// \returns true if all replacements apply. false otherwise.
 bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite);
 
-/// \brief Apply all replacements in \p Replaces to the Rewriter \p Rewrite.
-///
-/// Replacement applications happen independently of the success of
-/// other applications.
-///
-/// \returns true if all replacements apply. false otherwise.
-bool applyAllReplacements(const std::vector<Replacement> &Replaces,
-                          Rewriter &Rewrite);
-
 /// \brief Applies all replacements in \p Replaces to \p Code.
+/// It is callers' responsibility to ensure replacements are good to apply (i.e
+/// deduplicated or sorted). This function simply applies all replacements
+/// without preprocessing them.
 ///
 /// This completely ignores the path stored in each replacement. If one or more
 /// replacements cannot be applied, this returns an empty \c string.
 std::string applyAllReplacements(StringRef Code, const Replacements &Replaces);
 
 /// \brief Calculates how a code \p Position is shifted when \p Replaces are
 /// applied.
-unsigned shiftedCodePosition(const Replacements& Replaces, unsigned Position);
-
-/// \brief Calculates how a code \p Position is shifted when \p Replaces are
-/// applied.
 ///
 /// \pre Replaces[i].getOffset() <= Replaces[i+1].getOffset().
-unsigned shiftedCodePosition(const std::vector<Replacement> &Replaces,
-                             unsigned Position);
+unsigned shiftedCodePosition(const Replacements& Replaces, unsigned Position);
 
 /// \brief Removes duplicate Replacements and reports if Replacements conflict
 /// with one another. All Replacements are assumed to be in the same file.
 ///
 /// \post Replaces[i].getOffset() <= Replaces[i+1].getOffset().
 ///
 /// This function sorts \p Replaces so that conflicts can be reported simply by
 /// offset into \p Replaces and number of elements in the conflict.
-void deduplicate(std::vector<Replacement> &Replaces,
-                 std::vector<Range> &Conflicts);
+void deduplicate(Replacements &Replaces, std::vector<Range> &Conflicts);
 
 /// \brief Collection of Replacements generated from a single translation unit.
 struct TranslationUnitReplacements {
   /// Name of the main source for the translation unit.
   std::string MainSourceFile;
 
   /// A freeform chunk of text to describe the context of the replacements.
   /// Will be printed, for example, when detecting conflicts during replacement
   /// deduplication.
   std::string Context;
 
   std::vector<Replacement> Replacements;
 };
 
-/// \brief Apply all replacements in \p Replaces to the Rewriter \p Rewrite.
-///
-/// Replacement applications happen independently of the success of
-/// other applications.
-///
-/// \returns true if all replacements apply. false otherwise.
-bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite);
-
-/// \brief Apply all replacements in \p Replaces to the Rewriter \p Rewrite.
-///
-/// Replacement applications happen independently of the success of
-/// other applications.
-///
-/// \returns true if all replacements apply. false otherwise.
-bool applyAllReplacements(const std::vector<Replacement> &Replaces,
-                          Rewriter &Rewrite);
-
-/// \brief Applies all replacements in \p Replaces to \p Code.
-///
-/// This completely ignores the path stored in each replacement. If one or more
-/// replacements cannot be applied, this returns an empty \c string.
-std::string applyAllReplacements(StringRef Code, const Replacements &Replaces);
-
 /// \brief Calculates the ranges in a single file that are affected by the
 /// Replacements.
 ///
 /// \pre Replacements must be for the same file.
-std::vector<Range> calculateChangedRanges(const Replacements &Replaces);
+std::vector<Range> calculateChangedRanges(Replacements Replaces);
 
 /// \brief Groups a random set of replacements by file path. Replacements
 /// related to the same file entry are put into the same vector.
 std::map<std::string, Replacements>
 groupReplacementsByFile(const Replacements &Replaces);
 
 /// \brief Merges two sets of replacements with the second set referring to the
-/// code after applying the first set. Within both 'First' and 'Second',
-/// replacements must not overlap.
-Replacements mergeReplacements(const Replacements &First,
-                               const Replacements &Second);
+/// code after applying the first set.
+///
+/// \pre Within both 'First' and 'Second', replacements must not overlap.
+Replacements mergeReplacements(Replacements First, Replacements Second);
 
 template <typename Node>
 Replacement::Replacement(const SourceManager &Sources,
                          const Node &NodeToReplace, StringRef ReplacementText,
                          const LangOptions &LangOpts) {
   const CharSourceRange Range =
       CharSourceRange::getTokenRange(NodeToReplace->getSourceRange());
   setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
 }
 
 } // end namespace tooling
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLING_CORE_REPLACEMENT_H

lib/Format/Format.cpp

for (AnnotatedLine *Line : Lines) {
              !Input.startswith("\'")))
           continue;
 
         // Change start and end quote.
         bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
         SourceLocation Start = FormatTok->Tok.getLocation();
         auto Replace = [&](SourceLocation Start, unsigned Length,
                            StringRef ReplacementText) {
-          Result.insert(tooling::Replacement(Env.getSourceManager(), Start,
+          Result.push_back(tooling::Replacement(Env.getSourceManager(), Start,
                                                 Length, ReplacementText));
         };
         Replace(Start, 1, IsSingle ? "'" : "\"");
         Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
                 IsSingle ? "'" : "\"");
 
         // Escape internal quotes.
         size_t ColumnWidth = FormatTok->TokenText.size();
         bool Escaped = false;
tooling::Replacements generateFixes() {
     while (Idx < Tokens.size()) {
       unsigned St = Idx, End = Idx;
       while ((End + 1) < Tokens.size() &&
              Tokens[End]->Next == Tokens[End + 1]) {
         End++;
       }
       auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
                                               Tokens[End]->Tok.getEndLoc());
-      Fixes.insert(tooling::Replacement(Env.getSourceManager(), SR, ""));
+      Fixes.push_back(tooling::Replacement(Env.getSourceManager(), SR, ""));
       Idx = End + 1;
     }
 
+    std::vector<tooling::Range> Conflicts;
+    deduplicate(Fixes, Conflicts);
+    assert(Conflicts.empty() && "Fixes must be conflict-free!");
+
     return Fixes;
   }
 
   // Class for less-than inequality comparason for the set `RedundantTokens`.
   // We store tokens in the order they appear in the translation unit so that
   // we do not need to sort them in `generateFixes()`.
   struct FormatTokenLess {
     FormatTokenLess(const SourceManager &SM) : SM(SM) {}
static void sortCppIncludes(const FormatStyle &Style,
   }
 
   // Sorting #includes shouldn't change their total number of characters.
   // This would otherwise mess up 'Ranges'.
   assert(result.size() ==
          Includes.back().Offset + Includes.back().Text.size() -
              Includes.front().Offset);
 
-  Replaces.insert(tooling::Replacement(FileName, Includes.front().Offset,
+  Replaces.push_back(tooling::Replacement(FileName, Includes.front().Offset,
                                           result.size(), result));
 }
 
 namespace {
 
 // This class manages priorities of #include categories and calculates
 // priorities for headers.
 class IncludeCategoryManager {
 public:
tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
                                    ArrayRef<tooling::Range> Ranges,
                                    StringRef FileName, unsigned *Cursor) {
   tooling::Replacements Replaces;
   if (!Style.SortIncludes)
     return Replaces;
   if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
     return sortJavaScriptImports(Style, Code, Ranges, FileName);
   sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
+
+  std::vector<tooling::Range> Conflicts;
+  deduplicate(Replaces, Conflicts);
+  assert(Conflicts.empty() && "Fixes must be conflict-free!");
+
   return Replaces;
 }
 
+// \p Replaces must be ready to be applied.
 template <typename T>
 static tooling::Replacements
 processReplacements(T ProcessFunc, StringRef Code,
                     const tooling::Replacements &Replaces,
                     const FormatStyle &Style) {
   if (Replaces.empty())
     return tooling::Replacements();
 

 fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
                         const FormatStyle &Style) {
   if (Style.Language != FormatStyle::LanguageKind::LK_Cpp)
     return Replaces;
 
   tooling::Replacements HeaderInsertions;
   for (const auto &R : Replaces) {
     if (isHeaderInsertion(R))
-      HeaderInsertions.insert(R);
+      HeaderInsertions.push_back(R);
     else if (R.getOffset() == UINT_MAX)
       llvm::errs() << "Insertions other than header #include insertion are "
                       "not supported! "
                    << R.getReplacementText() << "\n";
   }
   if (HeaderInsertions.empty())
     return Replaces;
   tooling::Replacements Result;
if (ExistingIncludes.find(IncludeName) != ExistingIncludes.end()) {
       continue;
     }
     int Category =
         Categories.getIncludePriority(IncludeName, /*CheckMainHeader=*/true);
     Offset = CategoryEndOffsets[Category];
     std::string NewInclude = !IncludeDirective.endswith("\n")
                                  ? (IncludeDirective + "\n").str()
                                  : IncludeDirective.str();
-    Result.insert(tooling::Replacement(FileName, Offset, 0, NewInclude));
+    Result.push_back(tooling::Replacement(FileName, Offset, 0, NewInclude));
   }
+
+  std::vector<tooling::Range> Conflicts;
+  deduplicate(Result, Conflicts);
+  assert(Conflicts.empty() && "Result must be conflict-free!");
+
   return Result;
 }
 
 } // anonymous namespace
 
 tooling::Replacements
 cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
                           const FormatStyle &Style) {

lib/Format/SortJavaScriptImports.cpp

analyze(TokenAnnotator &Annotator,
 
     // Separate references from the main code body of the file.
     if (FirstNonImportLine && FirstNonImportLine->First->NewlinesBefore < 2)
       ReferencesText += "\n";
 
     DEBUG(llvm::dbgs() << "Replacing imports:\n"
                        << getSourceText(InsertionPoint) << "\nwith:\n"
                        << ReferencesText << "\n");
-    Result.insert(tooling::Replacement(
+    Result.push_back(tooling::Replacement(
         Env.getSourceManager(), CharSourceRange::getCharRange(InsertionPoint),
         ReferencesText));
 
     return Result;
   }
 
 private:
   FormatToken *Current;

lib/Format/TokenAnalyzer.cpp

DEBUG({
                                            E = RunResult.end();
            I != E; ++I) {
         llvm::dbgs() << I->toString() << "\n";
       }
     });
     for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
       delete AnnotatedLines[i];
     }
-    Result.insert(RunResult.begin(), RunResult.end());
+    Result.insert(Result.end(), RunResult.begin(), RunResult.end());
   }
+  std::vector<tooling::Range> Conflicts;
+  deduplicate(Result, Conflicts);
+  assert(Conflicts.empty() && "Result must be conflict-free!");
   return Result;
 }
 
 void TokenAnalyzer::consumeUnwrappedLine(const UnwrappedLine &TheLine) {
   assert(!UnwrappedLines.empty());
   UnwrappedLines.back().push_back(TheLine);
 }
 
 void TokenAnalyzer::finishRun() {
   UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
 }
 
 } // end namespace format
 } // end namespace clang

lib/Format/WhitespaceManager.h

public:
   /// used to align backslashes correctly.
   void replaceWhitespaceInToken(const FormatToken &Tok, unsigned Offset,
                                 unsigned ReplaceChars,
                                 StringRef PreviousPostfix,
                                 StringRef CurrentPrefix, bool InPPDirective,
                                 unsigned Newlines, unsigned IndentLevel,
                                 int Spaces);
 
-  /// \brief Returns all the \c Replacements created during formatting.
+  /// \brief Returns all the \c Replacements (sorted and non-overlapping)
+  /// created during formatting.
   const tooling::Replacements &generateReplacements();
 
   /// \brief Represents a change before a token, a break inside a token,
   /// or the layout of an unchanged token (or whitespace within).
   struct Change {
     /// \brief Functor to sort changes in original source order.
     class IsBeforeInFile {
     public:

lib/Format/WhitespaceManager.cpp

const tooling::Replacements &WhitespaceManager::generateReplacements() {
   std::sort(Changes.begin(), Changes.end(), Change::IsBeforeInFile(SourceMgr));
   calculateLineBreakInformation();
   alignConsecutiveDeclarations();
   alignConsecutiveAssignments();
   alignTrailingComments();
   alignEscapedNewlines();
   generateChanges();
 
+  std::vector<tooling::Range> Conflicts;
+  deduplicate(Replaces, Conflicts);
+  assert(Conflicts.empty() && "Replcements must be conflict-free!");
   return Replaces;
 }
 
 void WhitespaceManager::calculateLineBreakInformation() {
   Changes[0].PreviousEndOfTokenColumn = 0;
   Change *LastOutsideTokenChange = &Changes[0];
   for (unsigned i = 1, e = Changes.size(); i != e; ++i) {
     unsigned OriginalWhitespaceStart =

 void WhitespaceManager::storeReplacement(SourceRange Range,
                                          StringRef Text) {
   unsigned WhitespaceLength = SourceMgr.getFileOffset(Range.getEnd()) -
                               SourceMgr.getFileOffset(Range.getBegin());
   // Don't create a replacement, if it does not change anything.
   if (StringRef(SourceMgr.getCharacterData(Range.getBegin()),
                 WhitespaceLength) == Text)
     return;
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       SourceMgr, CharSourceRange::getCharRange(Range), Text));
 }
 
 void WhitespaceManager::appendNewlineText(std::string &Text,
                                           unsigned Newlines) {
   for (unsigned i = 0; i < Newlines; ++i)
     Text.append(UseCRLF ? "\r\n" : "\n");
 }

lib/Tooling/Core/Replacement.cpp

void Replacement::setFromSourceRange(const SourceManager &Sources,
                                      const CharSourceRange &Range,
                                      StringRef ReplacementText,
                                      const LangOptions &LangOpts) {
   setFromSourceLocation(Sources, Sources.getSpellingLoc(Range.getBegin()),
                         getRangeSize(Sources, Range, LangOpts),
                         ReplacementText);
 }
 
-template <typename T>
-unsigned shiftedCodePositionInternal(const T &Replaces, unsigned Position) {
+unsigned shiftedCodePosition(const Replacements &Replaces, unsigned Position) {
   unsigned Offset = 0;
-  for (const auto& R : Replaces) {
+  for (const auto &R : Replaces) {
     if (R.getOffset() + R.getLength() <= Position) {
       Offset += R.getReplacementText().size() - R.getLength();
       continue;
     }
     if (R.getOffset() < Position &&
         R.getOffset() + R.getReplacementText().size() <= Position) {
       Position = R.getOffset() + R.getReplacementText().size() - 1;
     }
     break;
   }
   return Position + Offset;
 }
 
-unsigned shiftedCodePosition(const Replacements &Replaces, unsigned Position) {
-  return shiftedCodePositionInternal(Replaces, Position);
-}
-
-// FIXME: Remove this function when Replacements is implemented as std::vector
-// instead of std::set.
-unsigned shiftedCodePosition(const std::vector<Replacement> &Replaces,
-                             unsigned Position) {
-  return shiftedCodePositionInternal(Replaces, Position);
-}
-
-void deduplicate(std::vector<Replacement> &Replaces,
-                 std::vector<Range> &Conflicts) {
+void deduplicate(Replacements &Replaces, std::vector<Range> &Conflicts) {
   if (Replaces.empty())
     return;
 
+  // This does not compare file path, otherwise it is the same as operator<.
   auto LessNoPath = [](const Replacement &LHS, const Replacement &RHS) {
     if (LHS.getOffset() != RHS.getOffset())
       return LHS.getOffset() < RHS.getOffset();
     if (LHS.getLength() != RHS.getLength())
-      return LHS.getLength() < RHS.getLength();
+      return LHS.getLength() > RHS.getLength();
     return LHS.getReplacementText() < RHS.getReplacementText();
   };
 
   auto EqualNoPath = [](const Replacement &LHS, const Replacement &RHS) {
     return LHS.getOffset() == RHS.getOffset() &&
            LHS.getLength() == RHS.getLength() &&
            LHS.getReplacementText() == RHS.getReplacementText();
   };
 
   // Deduplicate. We don't want to deduplicate based on the path as we assume
   // that all replacements refer to the same file (or are symlinks).
-  std::sort(Replaces.begin(), Replaces.end(), LessNoPath);
+  std::stable_sort(Replaces.begin(), Replaces.end(), LessNoPath);
   Replaces.erase(std::unique(Replaces.begin(), Replaces.end(), EqualNoPath),
                  Replaces.end());
 
   // Detect conflicts
   Range ConflictRange(Replaces.front().getOffset(),
                       Replaces.front().getLength());
   unsigned ConflictStart = 0;
   unsigned ConflictLength = 1;
if (ConflictRange.overlapsWith(Current)) {
       ConflictLength = 1;
     }
   }
 
   if (ConflictLength > 1)
     Conflicts.push_back(Range(ConflictStart, ConflictLength));
 }
 
 bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite) {
   bool Result = true;
-  for (Replacements::const_iterator I = Replaces.begin(),
-                                    E = Replaces.end();
-       I != E; ++I) {
-    if (I->isApplicable()) {
-      Result = I->apply(Rewrite) && Result;
-    } else {
-      Result = false;
-    }
-  }
-  return Result;
-}
-
-// FIXME: Remove this function when Replacements is implemented as std::vector
-// instead of std::set.
-bool applyAllReplacements(const std::vector<Replacement> &Replaces,
-                          Rewriter &Rewrite) {
-  bool Result = true;
-  for (std::vector<Replacement>::const_iterator I = Replaces.begin(),
-                                                E = Replaces.end();
+  for (Replacements::const_iterator I = Replaces.begin(), E = Replaces.end();
        I != E; ++I) {
     if (I->isApplicable()) {
       Result = I->apply(Rewrite) && Result;
     } else {
       Result = false;
     }
   }
   return Result;
 }
 
 std::string applyAllReplacements(StringRef Code, const Replacements &Replaces) {
-  if (Replaces.empty()) return Code;
-
+  if (Replaces.empty())
+    return Code;
   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
       new vfs::InMemoryFileSystem);
   FileManager Files(FileSystemOptions(), InMemoryFileSystem);
   DiagnosticsEngine Diagnostics(
       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
       new DiagnosticOptions);
   SourceManager SourceMgr(Diagnostics, Files);
   Rewriter Rewrite(SourceMgr, LangOptions());
std::string applyAllReplacements(StringRef Code, const Replacements &Replaces) {
   }
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   Rewrite.getEditBuffer(ID).write(OS);
   OS.flush();
   return Result;
 }
 
-std::vector<Range> calculateChangedRanges(const Replacements &Replaces) {
+std::vector<Range> calculateChangedRanges(Replacements Replaces) {
   std::vector<Range> ChangedRanges;
+  std::stable_sort(Replaces.begin(), Replaces.end());
   int Shift = 0;
   for (const Replacement &R : Replaces) {
     unsigned Offset = R.getOffset() + Shift;
     unsigned Length = R.getReplacementText().size();
     Shift += Length - R.getLength();
     ChangedRanges.push_back(Range(Offset, Length));
   }
   return ChangedRanges;
private:
   std::string Text;
 };
 } // namespace
 
 std::map<std::string, Replacements>
 groupReplacementsByFile(const Replacements &Replaces) {
   std::map<std::string, Replacements> FileToReplaces;
   for (const auto &Replace : Replaces) {
-    FileToReplaces[Replace.getFilePath()].insert(Replace);
+    FileToReplaces[Replace.getFilePath()].push_back(Replace);
   }
   return FileToReplaces;
 }
 
-Replacements mergeReplacements(const Replacements &First,
-                               const Replacements &Second) {
+Replacements mergeReplacements(Replacements First, Replacements Second) {
   if (First.empty() || Second.empty())
     return First.empty() ? Second : First;
 
+  std::vector<Range> Conflicts;
+  deduplicate(First, Conflicts);
+  assert(Conflicts.empty() && "First must be conflict-free!");
+  deduplicate(Second, Conflicts);
+  assert(Conflicts.empty() && "Second must be conflict-free!");
+
   // Delta is the amount of characters that replacements from 'Second' need to
   // be shifted so that their offsets refer to the original text.
   int Delta = 0;
   Replacements Result;
 
   // Iterate over both sets and always add the next element (smallest total
   // Offset) from either 'First' or 'Second'. Merge that element with
   // subsequent replacements as long as they overlap. See more details in the
while ((Merged.mergeSecond() && SecondI != Second.end()) ||
            (!Merged.mergeSecond() && FirstI != First.end())) {
       auto &I = Merged.mergeSecond() ? SecondI : FirstI;
       if (Merged.endsBefore(*I))
         break;
       Merged.merge(*I);
       ++I;
     }
     Delta -= Merged.deltaFirst();
-    Result.insert(Merged.asReplacement());
+    Result.push_back(Merged.asReplacement());
   }
   return Result;
 }
 
 } // end namespace tooling
 } // end namespace clang
 

lib/Tooling/RefactoringCallbacks.cpp

 }
 
 ReplaceStmtWithText::ReplaceStmtWithText(StringRef FromId, StringRef ToText)
     : FromId(FromId), ToText(ToText) {}
 
 void ReplaceStmtWithText::run(
     const ast_matchers::MatchFinder::MatchResult &Result) {
   if (const Stmt *FromMatch = Result.Nodes.getStmtAs<Stmt>(FromId)) {
-    Replace.insert(tooling::Replacement(
+    Replace.push_back(tooling::Replacement(
         *Result.SourceManager,
-        CharSourceRange::getTokenRange(FromMatch->getSourceRange()),
-        ToText));
+        CharSourceRange::getTokenRange(FromMatch->getSourceRange()), ToText));
   }
 }
 
 ReplaceStmtWithStmt::ReplaceStmtWithStmt(StringRef FromId, StringRef ToId)
     : FromId(FromId), ToId(ToId) {}
 
 void ReplaceStmtWithStmt::run(
     const ast_matchers::MatchFinder::MatchResult &Result) {
   const Stmt *FromMatch = Result.Nodes.getStmtAs<Stmt>(FromId);
   const Stmt *ToMatch = Result.Nodes.getStmtAs<Stmt>(ToId);
   if (FromMatch && ToMatch)
-    Replace.insert(replaceStmtWithStmt(
-        *Result.SourceManager, *FromMatch, *ToMatch));
+    Replace.push_back(
+        replaceStmtWithStmt(*Result.SourceManager, *FromMatch, *ToMatch));
 }
 
 ReplaceIfStmtWithItsBody::ReplaceIfStmtWithItsBody(StringRef Id,
                                                    bool PickTrueBranch)
     : Id(Id), PickTrueBranch(PickTrueBranch) {}
 
 void ReplaceIfStmtWithItsBody::run(
     const ast_matchers::MatchFinder::MatchResult &Result) {
   if (const IfStmt *Node = Result.Nodes.getStmtAs<IfStmt>(Id)) {
     const Stmt *Body = PickTrueBranch ? Node->getThen() : Node->getElse();
     if (Body) {
-      Replace.insert(replaceStmtWithStmt(*Result.SourceManager, *Node, *Body));
+      Replace.push_back(
+          replaceStmtWithStmt(*Result.SourceManager, *Node, *Body));
     } else if (!PickTrueBranch) {
       // If we want to use the 'else'-branch, but it doesn't exist, delete
       // the whole 'if'.
-      Replace.insert(replaceStmtWithText(*Result.SourceManager, *Node, ""));
+      Replace.push_back(replaceStmtWithText(*Result.SourceManager, *Node, ""));
     }
   }
 }
 
 } // end namespace tooling
 } // end namespace clang

unittests/Format/FormatTest.cpp

TEST_F(ReplacementTest, FormatCodeAfterReplacements) {
   std::string Expected = "auto a = new Type();\n"
                          "g(iiiii, nullptr,\n"
                          "  jjjjj, nullptr,\n"
                          "  kkkkk, nullptr,\n"
                          "  mm);\n"
                          "int  bad     = format   ;";
   FileID ID = Context.createInMemoryFile("format.cpp", Code);
   tooling::Replacements Replaces;
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID, 1, 1), 6, "auto "));
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID, 3, 10), 1, "nullptr"));
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID, 4, 3), 1, "nullptr"));
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID, 4, 13), 1, "nullptr"));
 
   format::FormatStyle Style = format::getLLVMStyle();
   Style.ColumnLimit = 20; // Set column limit to 20 to increase readibility.
   EXPECT_EQ(Expected, applyAllReplacements(
                           Code, formatReplacements(Code, Replaces, Style)));
 }
 
 TEST_F(ReplacementTest, SortIncludesAfterReplacement) {
   std::string Code = "#include \"a.h\"\n"
                      "#include \"c.h\"\n"
                      "\n"
                      "int main() {\n"
                      "  return 0;\n"
                      "}";
   std::string Expected = "#include \"a.h\"\n"
                          "#include \"b.h\"\n"
                          "#include \"c.h\"\n"
                          "\n"
                          "int main() {\n"
                          "  return 0;\n"
                          "}";
   FileID ID = Context.createInMemoryFile("fix.cpp", Code);
   tooling::Replacements Replaces;
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID, 1, 1), 0, "#include \"b.h\"\n"));
 
   format::FormatStyle Style = format::getLLVMStyle();
   Style.SortIncludes = true;
   auto FinalReplaces = formatReplacements(Code, Replaces, Style);
   EXPECT_EQ(Expected, applyAllReplacements(Code, FinalReplaces));
 }
 
 } // end namespace
 } // end namespace format
 } // end namespace clang

unittests/Tooling/RefactoringTest.cpp

 #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, CanAddText) {
   FileID ID = Context.createInMemoryFile("input.cpp", "");
   SourceLocation Location = Context.getLocation(ID, 1, 1);
   Replacement Replace(createReplacement(Location, 0, "result"));
   EXPECT_TRUE(Replace.apply(Context.Rewrite));
   EXPECT_EQ("result", Context.getRewrittenText(ID));
 }
 
 TEST_F(ReplacementTest, CanReplaceTextAtPosition) {
-  FileID ID = Context.createInMemoryFile("input.cpp",
-                                         "line1\nline2\nline3\nline4");
+  FileID ID =
+      Context.createInMemoryFile("input.cpp", "line1\nline2\nline3\nline4");
   SourceLocation Location = Context.getLocation(ID, 2, 3);
   Replacement Replace(createReplacement(Location, 12, "x"));
   EXPECT_TRUE(Replace.apply(Context.Rewrite));
   EXPECT_EQ("line1\nlixne4", Context.getRewrittenText(ID));
 }
 
 TEST_F(ReplacementTest, CanReplaceTextAtPositionMultipleTimes) {
-  FileID ID = Context.createInMemoryFile("input.cpp",
-                                         "line1\nline2\nline3\nline4");
+  FileID ID =
+      Context.createInMemoryFile("input.cpp", "line1\nline2\nline3\nline4");
   SourceLocation Location1 = Context.getLocation(ID, 2, 3);
   Replacement Replace1(createReplacement(Location1, 12, "x\ny\n"));
   EXPECT_TRUE(Replace1.apply(Context.Rewrite));
   EXPECT_EQ("line1\nlix\ny\nne4", Context.getRewrittenText(ID));
 
   // Since the original source has not been modified, the (4, 4) points to the
   // 'e' in the original content.
   SourceLocation Location2 = Context.getLocation(ID, 4, 4);
TEST_F(ReplacementTest, ReturnsInvalidPath) {
   Replacement Replace1(Context.Sources, SourceLocation(), 0, "");
   EXPECT_TRUE(Replace1.getFilePath().empty());
 
   Replacement Replace2;
   EXPECT_TRUE(Replace2.getFilePath().empty());
 }
 
 TEST_F(ReplacementTest, CanApplyReplacements) {
-  FileID ID = Context.createInMemoryFile("input.cpp",
-                                         "line1\nline2\nline3\nline4");
+  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"));
-  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) {
-  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"));
   EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
   EXPECT_EQ("line1\nreplaced\nother\nline4", Context.getRewrittenText(ID));
 }
 
 TEST_F(ReplacementTest, SkipsDuplicateReplacements) {
-  FileID ID = Context.createInMemoryFile("input.cpp",
-                                         "line1\nline2\nline3\nline4");
+  FileID ID =
+      Context.createInMemoryFile("input.cpp", "line1\nline2\nline3\nline4");
   Replacements Replaces;
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
+  Replaces.push_back(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
                                  5, "replaced"));
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
+  Replaces.push_back(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
                                  5, "replaced"));
-  Replaces.insert(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
+  Replaces.push_back(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
                                  5, "replaced"));
+  std::vector<Range> Conflicts;
+  deduplicate(Replaces, Conflicts);
+  EXPECT_TRUE(Conflicts.empty());
   EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
   EXPECT_EQ("line1\nreplaced\nline3\nline4", Context.getRewrittenText(ID));
 }
 
+TEST_F(ReplacementTest, CanApplyDuplicateReplacements) {
+  FileID ID =
+      Context.createInMemoryFile("input.cpp", "line1\nline2\nline3\nline4");
+  Replacements Replaces;
+  Replaces.push_back(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
+                                 0, "insert\n"));
+  Replaces.push_back(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
+                                 0, "insert\n"));
+  Replaces.push_back(Replacement(Context.Sources, Context.getLocation(ID, 2, 1),
+                                 0, "insert\n"));
+  EXPECT_TRUE(applyAllReplacements(Replaces, Context.Rewrite));
+  EXPECT_EQ("line1\ninsert\ninsert\ninsert\nline2\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"));
+  Replaces.push_back(
+      Replacement(Context.Sources, Context.getLocation(IDa, 1, 1), 4, "a"));
+  Replaces.push_back(Replacement(Context.Sources, SourceLocation(), 5, "2"));
+  Replaces.push_back(
+      Replacement(Context.Sources, Context.getLocation(IDz, 1, 1), 4, "z"));
   EXPECT_FALSE(applyAllReplacements(Replaces, Context.Rewrite));
   EXPECT_EQ("a", Context.getRewrittenText(IDa));
   EXPECT_EQ("z", Context.getRewrittenText(IDz));
 }
 
 TEST_F(ReplacementTest, MultipleFilesReplaceAndFormat) {
   // Column limit is 20.
   std::string Code1 = "Long *a =\n"
                       "    new Long();\n"
                       "long x = 1;";
   std::string Expected1 = "auto a = new Long();\n"
                           "long x =\n"
                           "    12345678901;";
   std::string Code2 = "int x = 123;\n"
                       "int y = 0;";
   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);
 
   tooling::Replacements Replaces;
   // Scrambled the order of replacements.
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID2, 1, 12), 0, "4567890123"));
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID1, 1, 1), 6, "auto "));
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID2, 2, 9), 1, "10"));
-  Replaces.insert(tooling::Replacement(
+  Replaces.push_back(tooling::Replacement(
       Context.Sources, Context.getLocation(ID1, 3, 10), 1, "12345678901"));
 
   EXPECT_TRUE(formatAndApplyAllReplacements(
       Replaces, 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, " "));
-  // 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|
 }
 
 TEST(ShiftedCodePositionTest, FindsNewCodePositionWithInserts) {
   Replacements Replaces;
-  Replaces.insert(Replacement("", 4, 0, "\"\n\""));
+  Replaces.push_back(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"
 }
 
 TEST(ShiftedCodePositionTest, FindsNewCodePositionInReplacedText) {
   Replacements Replaces;
   // Replace the first four characters with "abcd".
-  Replaces.insert(Replacement("", 0, 4, "abcd"));
+  Replaces.push_back(Replacement("", 0, 4, "abcd"));
   for (unsigned i = 0; i < 3; ++i)
     EXPECT_EQ(i, shiftedCodePosition(Replaces, i));
 }
 
 class FlushRewrittenFilesTest : public ::testing::Test {
 public:
-   FlushRewrittenFilesTest() {}
 
-   ~FlushRewrittenFilesTest() override {
     for (llvm::StringMap<std::string>::iterator I = TemporaryFiles.begin(),
                                                 E = TemporaryFiles.end();
          I != E; ++I) {
       llvm::StringRef Name = I->second;
       std::error_code EC = llvm::sys::fs::remove(Name);
       (void)EC;
       assert(!EC);
     }
public:
 
   llvm::StringMap<std::string> TemporaryFiles;
   RewriterTestContext Context;
 };
 
 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),
+  Replaces.push_back(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",
             getFileContentFromDisk("input.cpp"));
 }
 
 namespace {
-template <typename T>
-class TestVisitor : public clang::RecursiveASTVisitor<T> {
+template <typename T> class TestVisitor : public clang::RecursiveASTVisitor<T> {
 public:
   bool runOver(StringRef Code) {
     return runToolOnCode(new TestAction(this), Code);
   }
 
 protected:
   clang::SourceManager *SM;
   clang::ASTContext *Context;
public:
     }
 
   private:
     TestVisitor *Visitor;
   };
 };
 } // end namespace
 
-void expectReplacementAt(const Replacement &Replace,
-                         StringRef File, unsigned Offset, unsigned Length) {
+void expectReplacementAt(const Replacement &Replace, StringRef File,
+                         unsigned Offset, unsigned Length) {
   ASSERT_TRUE(Replace.isApplicable());
   EXPECT_EQ(File, Replace.getFilePath());
   EXPECT_EQ(Offset, Replace.getOffset());
   EXPECT_EQ(Length, Replace.getLength());
 }
 
 class ClassDeclXVisitor : public TestVisitor<ClassDeclXVisitor> {
 public:
TEST(Replacement, FunctionCall) {
   CallToFVisitor CallToF;
   EXPECT_TRUE(CallToF.runOver("void F(); void G() { F(); }"));
   expectReplacementAt(CallToF.Replace, "input.cc", 21, 3);
 }
 
 TEST(Replacement, TemplatedFunctionCall) {
   CallToFVisitor CallToF;
   EXPECT_TRUE(CallToF.runOver(
-        "template <typename T> void F(); void G() { F<int>(); }"));
   expectReplacementAt(CallToF.Replace, "input.cc", 43, 8);
 }
 
 class NestedNameSpecifierAVisitor
     : public TestVisitor<NestedNameSpecifierAVisitor> {
 public:
   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLoc) {
     if (NNSLoc.getNestedNameSpecifier()) {
-      if (const NamespaceDecl* NS = NNSLoc.getNestedNameSpecifier()->getAsNamespace()) {
+      if (const NamespaceDecl *NS =
+              NNSLoc.getNestedNameSpecifier()->getAsNamespace()) {
         if (NS->getName() == "a") {
           Replace = Replacement(*SM, &NNSLoc, "", Context->getLangOpts());
         }
       }
     }
-    return TestVisitor<NestedNameSpecifierAVisitor>::TraverseNestedNameSpecifierLoc(
-        NNSLoc);
+    return TestVisitor<
+        NestedNameSpecifierAVisitor>::TraverseNestedNameSpecifierLoc(NNSLoc);
   }
   Replacement Replace;
 };
 
 TEST(Replacement, ColonColon) {
   NestedNameSpecifierAVisitor VisitNNSA;
   EXPECT_TRUE(VisitNNSA.runOver("namespace a { void f() { ::a::f(); } }"));
   expectReplacementAt(VisitNNSA.Replace, "input.cc", 25, 5);
TEST(Range, contains) {
   EXPECT_FALSE(Range(2, 6).contains(Range(0, 10)));
   EXPECT_FALSE(Range(0, 10).contains(Range(0, 11)));
 }
 
 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"));
+  Replaces.push_back(Replacement("foo", 0, 4, ""));
+  Replaces.push_back(Replacement("foo", 10, 1, "zzzzzz"));
+  Replaces.push_back(Replacement("foo", 11, 0, "oooooooooooooooo"));
 
   std::vector<Range> Ranges = calculateChangedRanges(Replaces);
 
   EXPECT_EQ(3ul, Ranges.size());
   EXPECT_TRUE(Ranges[0].getOffset() == 0);
   EXPECT_TRUE(Ranges[0].getLength() == 0);
   EXPECT_TRUE(Ranges[1].getOffset() == 6);
   EXPECT_TRUE(Ranges[1].getLength() == 6);
   EXPECT_TRUE(Ranges[2].getOffset() == 12);
   EXPECT_TRUE(Ranges[2].getLength() == 16);
 }
 
 TEST(DeduplicateTest, removesDuplicates) {
-  std::vector<Replacement> Input;
+  Replacements 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", 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 "));
+  Replacements Expected;
+  Expected.push_back(Replacement("fileA", 9, 3, " bar "));
   Expected.push_back(Replacement("fileA", 10, 3, " bar "));
+  Expected.push_back(Replacement("fileA", 10, 2, " 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 "));
+  Expected.push_back(Replacement("fileB", 60, 1, " 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;
+    Replacements 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;
+    Replacements 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", 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;

unittests/Tooling/RewriterTest.cpp

Context.Rewrite.ReplaceText(Context.getLocation(WorkingID, 2, 1), 5,
                               "replaced");
   EXPECT_TRUE(Context.Rewrite.overwriteChangedFiles());
   EXPECT_EQ("line1\nreplaced\nline3\nline4",
             Context.getFileContentFromDisk("working.cpp")); 
 }
 
 TEST(Rewriter, AdjacentInsertAndDelete) {
   Replacements Replaces;
-  Replaces.insert(Replacement("<file>", 6, 6, ""));
-  Replaces.insert(Replacement("<file>", 6, 0, "replaced\n"));
+  Replaces.push_back(Replacement("<file>", 6, 6, ""));
+  Replaces.push_back(Replacement("<file>", 6, 0, "replaced\n"));
   EXPECT_EQ("line1\nreplaced\nline3\nline4",
             applyAllReplacements("line1\nline2\nline3\nline4", Replaces));
 }
 
 } // end namespace
 } // end namespace tooling
 } // end namespace clang