Fix overlapping replacements in clang-tidy.

[angelgarcia]

Summary

Prevent clang-tidy from applying fixes to errors that overlap with other errors' fixes, with one exception: if one fix is completely contained inside another one, then we can apply the big one.

[klimek]

clang-tidy/ClangTidyDiagnosticConsumer.cpp

417–418

These need to be documented.

420

I'd name this Queue instead (reading later I had no idea what this was).

432–435

Why are you calling this "Sit"?

474

Why do we need to sort?

[angelgarcia]

Fix comments.

[angelgarcia]

These need to be documented.

Done.

I'd name this Queue instead (reading later I had no idea what this was).

Done.

Why are you calling this "Sit"?

I didn't even know how to describe this variable without using examples,
and naming it is harder. More or less, it keeps track of the different
overlapping situations that have been spotted during the process, so "Sit"
stands for that. But I know it is a really poor name and I'd like to change
it, any ideas?

Why do we need to sort?

It's a remnant of a different approach that I tried before. Removed.

[klimek]

clang-tidy/ClangTidyDiagnosticConsumer.cpp

437–439

The description makes it unclear whether the indices stand for the set, or the dimensions stand for the sets (I can see it's the dimensions from where it is set, and that the indices are bools, but that's unclear without that / hard to grasp).
Here's a slightly denormalized way, that uses early-exit and might be easier to understand (more opinions would be nice, though).
(note that I probably messed up the FirstInsideSecond setting somewhere :)

bool Overlaps = false;
bool FirstInsideSecond = false;

// In the loop:
if (Count[0] != 0 && Count[1] != 0) {
  Overlaps = true;
} else if (Overlaps && ((Count[0] != 0 && FirstInsideSecond) ||
                        (Count[1] != 0 && !FirstInsideSecond)) {
  return OK_Overlap;
} else if (Count[0] != 0 || Count[1] != 0) {
  FirstInsideSecond = Count[1] != 0;
}

// After the loop:
if (!Overlaps)
  return OK_Disjoint;
return FirstInsideSecond ? OK_FirstInsideSecond : OK_SecondInsideFirst;

[klimek]

clang-tidy/ClangTidyDiagnosticConsumer.cpp

437–439

Ok, what I proposed doesn't work.

I start to like your solution more. Perhaps we just need to document it better:
a) call it Coverage
b) introduce enum with Covered and Empty (or similar)
c) document:
Coverage[Covered][Covered]: both set 1 and set 2 cover an area;
Coverage[Covered][Empty]: set 1 covers an area set 2 doesn't cover;
Coverage[Empty][Covered]: set 2 covers an area set 1 doesn't cover;

[angelgarcia]

Add an enum and rename "Sit" to "Coverage" to improve readability.

[klimek]

clang-tidy/ClangTidyDiagnosticConsumer.cpp

443–447

I'd just call out the 3 cases, like I suggested in my previous comment ("etc" sounds for me like there's more than 1 case left ;)

460

I'd say:
// If both sets never cover the same range, there is no overlap.

471–474

I'd make that:
return Coverage[Empty][Covered] ? OK_FirstInsideSecond : OK_SecondInsideFirst;
(and adapt the comment)

[angelgarcia]

Done.

[klimek]

clang-tidy/ClangTidyDiagnosticConsumer.cpp

494–495

I'm somewhat concerned about the quadratic runtime here, for cases where somebody messes up a {} pair in a header and we have 1000s of errors.
Can we do a two step algorithm:

• go over all error-lists, compute bounding rectangles for each
• sort errors
• only do the squared algorithm for errors where the bounding rectangles overlap

[angelgarcia]

Use bounding boxes to reduce complexity.

[klimek]

LG in general now, looks to me like we have very few tests though.
My favorite strategy to make sure I have enough tests is to comment out code (or do mutations) as long as the tests still pass. Then write tests that fail with the mutation, then undo the mutation.

clang-tidy/ClangTidyDiagnosticConsumer.cpp

491–492

I think a comment at the top of this function outlining the full algorithm would be nice (without lots of details).

518–520

Document what goes into the pair - I assumed 'first, second' for a moment, and then was confused.

[djasper]

clang-tidy/ClangTidyDiagnosticConsumer.cpp

494–495

From a brief look, it seems like it might be slightly easier, to do what this is currently doing, but skip the bounding-box-calculation step. Simple do the same with each interval of each fix. We are just interested to efficiently calculate, which fixes overlap at all.

Now, I am not sure whether this is going to be more or less efficient:

• It might be hard / not worth it to calculate which fixes have already been compared so we might compare the same two fixes repeatedly (once for each "touching point").
• We might not need to carefully compare fixes at all in spite of their bounding boxes overlapping, e.g. two fixes A and B might have 3 entirely disjoint intervals: A, B, A. Then, we don't need to do the sweep at all.

[angelgarcia]

I've done a couple of runs for each version, and these are the results (I
have clang-tidy compiled with the option "RelWithDebInfo"):

$ time clang-tidy -checks=* test.cpp -- -std=c++11

Without looking for overlaps.

Suppressed 23463 warnings (23463 in non-user code).
Use -header-filter=.* to display errors from all non-system headers.

real 2m14.572s
user 2m13.136s
sys 0m0.483s

real 2m15.103s
user 2m13.361s
sys 0m0.687s

Bounding boxes

Suppressed 23463 warnings (23463 in non-user code).
Use -header-filter=.* to display errors from all non-system headers.

real 2m14.208s
user 2m13.051s
sys 0m0.643s

real 2m16.368s
user 2m14.286s
sys 0m0.986s

Quadratic

Suppressed 23463 warnings (23463 in non-user code).
Use -header-filter=.* to display errors from all non-system headers.

real 2m15.130s
user 2m13.627s
sys 0m0.499s

real 2m15.322s
user 2m13.660s
sys 0m0.683s

The time is about the same for all three versions. Note that the first
version doesn't do any sweep at all, and the last version invariably does
(23463 choose 2) = 275244453 sweeps. The amount of time required to do this
seems to be too low compared to the time that clang-tidy takes to output
these diagnostics.
Also, the fact that all three versions take about the same time is a bit
suspicious, but I double-checked that I was doing it right (I did a small
file with would cause overlapping and I checked if the message "note: this
fix will not be applied because it overlaps with another fix" was there
before each run).

I intended to implement Daniel's idea to check out which one was more
efficient, but with these results in sight I don't think it is worth it.

[djasper]

There might be an even easier algorithm:

What if we put all start and end points into a single sorted list. Identical start points are sorted by decreasing end points and identical end points are sorted by increasing start points. Now do a single sweep and simply count the total number of starts vs. the total number of ends, call this C (if you encounter a start point, ++C, if you encounter an end point, --C). If you encounter a start-point and C != 0, mark the interval and corresponding Fixit as inapplicable. Similarly if you encounter an end point and C != 1, mark the fixit as inapplicable. Basically, this does a single sweep over all fixits and marks the ones as bad that have either their start point or their endpoint within a different interval.

(Take this as an additional idea, if you have an existing algorithm that you like better, I am fine with keeping that. Just wanted to give my additional thoughts).

[angelgarcia]

That works pretty well (well, identical end points have to be sorted
decreasingly, if I understand correctly). I see a couple of problems
though, like equal intervals, or consecutive. But the algorithm is way more
efficient than what we currently have, I will try to make it work.

[angelgarcia]

I did several mutations and the only case were a test didn't break was when I removed the sort, but it turned out that we don't need it. I changed the tests to apply the checks in both orders to ensure that a test will break if the errors are not sorted.

I am still thinking about how to complete Daniel's idea.

[angelgarcia]

I cannot find a way to make Daniel's idea work with equal intervals:

In this case, fix A can be applied because B is completely contained inside
it.
A: [a, b)[c, d)
B: [a, b)

This time, we should not apply anyone:
A: [a, b)
B: [a, b)

And here they both have to be discarded again, but for a different reason:
A: [a, b)[c, d)
B: [e, f)[a, b)

The problem is that we have three completely different situations that are
the same from the point of view of interval "[a, b)". The local situation
of individual intervals doesn't provide enough information.

[angelgarcia]

I implemented this, with the following addition: if several errors share
the same interval, I can still apply the biggest one that was not discarded
during the sweep. This way, the first example would work and in the two
other examples it would just apply a random one, as you suggested. But I
found a different case that also fails:
A: [a, b)[c,d)
B: [e, f) such that e < a, b < f < c.

In this case it just discards A. This is not incorrect (as long as we don't
apply both, everything is OK), but it gets away from the idea of "if two
fixes overlap, discard both", which is what Manuel said when I started
this. I don't think that changing that idea is a problem, but right now the
behavior of the tool is so diffuse that maintaining and testing it would be
a bit painful. Also, if we want to allow applying one of the fixes when
they overlap, we have a different problem, it might be better just to start
from scratch and think about how to solve that problem.

[angelgarcia]

New algorithm :)

[klimek]

lg

clang-tidy/ClangTidyDiagnosticConsumer.cpp

488

Perhaps call this OpenIntervals, or if you like it short, just Open.

492–493

s/have/has/

[angelgarcia]

Remove unused include, fix typo and rename Count to OpenIntervals.

clang-tidy/ClangTidyDiagnosticConsumer.h

public:
 
   /// \brief Clears collected errors.
   void clearErrors() { Errors.clear(); }
 
   /// \brief Set the output struct for profile data.
   ///
   /// Setting a non-null pointer here will enable profile collection in
   /// clang-tidy.
-  void setCheckProfileData(ProfileData* Profile);
-  ProfileData* getCheckProfileData() const { return Profile; }
+  void setCheckProfileData(ProfileData *Profile);
+  ProfileData *getCheckProfileData() const { return Profile; }
 
 private:
   // Calls setDiagnosticsEngine() and storeError().
   friend class ClangTidyDiagnosticConsumer;
 
   /// \brief Sets the \c DiagnosticsEngine so that Diagnostics can be generated
   /// correctly.
   void setDiagnosticsEngine(DiagnosticsEngine *Engine);
void HandleDiagnostic(DiagnosticsEngine::Level DiagLevel,
                         const Diagnostic &Info) override;
 
   /// \brief Flushes the internal diagnostics buffer to the ClangTidyContext.
   void finish() override;
 
 private:
   void finalizeLastError();
 
+  void removeIncompatibleErrors(SmallVectorImpl<ClangTidyError> &Errors) const;
+
   /// \brief Returns the \c HeaderFilter constructed for the options set in the
   /// context.
-  llvm::Regex* getHeaderFilter();
+  llvm::Regex *getHeaderFilter();
 
   /// \brief Updates \c LastErrorRelatesToUserCode and LastErrorPassesLineFilter
   /// according to the diagnostic \p Location.
   void checkFilters(SourceLocation Location);
   bool passesLineFilter(StringRef FileName, unsigned LineNumber) const;
 
   ClangTidyContext &Context;
   std::unique_ptr<DiagnosticsEngine> Diags;

clang-tidy/ClangTidyDiagnosticConsumer.cpp

 //===----------------------------------------------------------------------===//
 
 #include "ClangTidyDiagnosticConsumer.h"
 #include "ClangTidyOptions.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Frontend/DiagnosticRenderer.h"
 #include "llvm/ADT/SmallString.h"
-#include <set>
 #include <tuple>
+#include <vector>
 using namespace clang;
 using namespace tidy;
 
 namespace {
 class ClangTidyDiagnosticRenderer : public DiagnosticRenderer {
 public:
   ClangTidyDiagnosticRenderer(const LangOptions &LangOpts,
                               DiagnosticOptions *DiagOpts,
else if (MetaChars.find(C) != StringRef::npos)
       RegexText.push_back('\\');
     RegexText.push_back(C);
   }
   RegexText.push_back('$');
   return llvm::Regex(RegexText);
 }
 
 GlobList::GlobList(StringRef Globs)
-    : Positive(!ConsumeNegativeIndicator(Globs)),
-      Regex(ConsumeGlob(Globs)),
+    : Positive(!ConsumeNegativeIndicator(Globs)), Regex(ConsumeGlob(Globs)),
       NextGlob(Globs.empty() ? nullptr : new GlobList(Globs)) {}
 
 bool GlobList::contains(StringRef S, bool Contains) {
   if (Regex.match(S))
     Contains = Positive;
 
   if (NextGlob)
     Contains = NextGlob->contains(S, Contains);

 const ClangTidyGlobalOptions &ClangTidyContext::getGlobalOptions() const {
   return OptionsProvider->getGlobalOptions();
 }
 
 const ClangTidyOptions &ClangTidyContext::getOptions() const {
   return CurrentOptions;
 }
 
-void ClangTidyContext::setCheckProfileData(ProfileData *P) {
-  Profile = P;
-}
+void ClangTidyContext::setCheckProfileData(ProfileData *P) { Profile = P; }
 
 GlobList &ClangTidyContext::getChecksFilter() {
   assert(CheckFilter != nullptr);
   return *CheckFilter;
 }
 
 /// \brief Store a \c ClangTidyError.
 void ClangTidyContext::storeError(const ClangTidyError &Error) {
if (DiagLevel == DiagnosticsEngine::Note) {
     std::string CheckName = !WarningOption.empty()
                                 ? ("clang-diagnostic-" + WarningOption).str()
                                 : Context.getCheckName(Info.getID()).str();
 
     if (CheckName.empty()) {
       // This is a compiler diagnostic without a warning option. Assign check
       // name based on its level.
       switch (DiagLevel) {
-        case DiagnosticsEngine::Error:
-        case DiagnosticsEngine::Fatal:
-          CheckName = "clang-diagnostic-error";
-          break;
-        case DiagnosticsEngine::Warning:
-          CheckName = "clang-diagnostic-warning";
-          break;
-        default:
-          CheckName = "clang-diagnostic-unknown";
-          break;
       }
     }
 
     ClangTidyError::Level Level = ClangTidyError::Warning;
     if (DiagLevel == DiagnosticsEngine::Error ||
         DiagLevel == DiagnosticsEngine::Fatal) {
       // Force reporting of Clang errors regardless of filters and non-user
       // code.
void ClangTidyDiagnosticConsumer::HandleDiagnostic(
 
   checkFilters(Info.getLocation());
 }
 
 bool ClangTidyDiagnosticConsumer::passesLineFilter(StringRef FileName,
                                                    unsigned LineNumber) const {
   if (Context.getGlobalOptions().LineFilter.empty())
     return true;
-  for (const FileFilter& Filter : Context.getGlobalOptions().LineFilter) {
+  for (const FileFilter &Filter : Context.getGlobalOptions().LineFilter) {
     if (FileName.endswith(Filter.Name)) {
       if (Filter.LineRanges.empty())
         return true;
       for (const FileFilter::LineRange &Range : Filter.LineRanges) {
         if (Range.first <= LineNumber && LineNumber <= Range.second)
           return true;
       }
       return false;

 
 llvm::Regex *ClangTidyDiagnosticConsumer::getHeaderFilter() {
   if (!HeaderFilter)
     HeaderFilter.reset(
         new llvm::Regex(*Context.getOptions().HeaderFilterRegex));
   return HeaderFilter.get();
 }
 
+void ClangTidyDiagnosticConsumer::removeIncompatibleErrors(
+    SmallVectorImpl<ClangTidyError> &Errors) const {
+  // Each error is modelled as the set of intervals in which it applies
+  // replacements. To detect overlapping replacements, we use a sweep line
+  // algorithm over these sets of intervals.
+  // An event here consists of the opening or closing of an interval. During the
+  // proccess, we maintain a counter with the amount of open intervals. If we
+  // find an endpoint of an interval and this counter is different from 0, it
+  // means that this interval overlaps with another one, so we set it as
+  // inapplicable.
+  struct Event {
+    // An event can be either the begin or the end of an interval.
+    enum EventType {
+      ET_Begin = 1,
+      ET_End = -1,
+    };
+
+    Event(unsigned Begin, unsigned End, EventType Type, unsigned ErrorId,
+          unsigned ErrorSize)
+        : Type(Type), ErrorId(ErrorId) {
+      // The events are going to be sorted by their position. In case of draw:
+      //
+      // * If an interval ends at the same position at which other interval
+      //   begins, this is not an overlapping, so we want to remove the ending
+      //   interval before adding the starting one: end events have higher
+      //   priority than begin events.
+      //
+      // * If we have several begin points at the same position, we will mark as
+      //   inapplicable the ones that we proccess later, so the first one has to
+      //   be the one with the latest end point, because this one will contain
+      //   all the other intervals. For the same reason, if we have several end
+      //   points in the same position, the last one has to be the one with the
+      //   earliest begin point. In both cases, we sort non-increasingly by the
+      //   position of the complementary.
+      //
+      // * In case of two equal intervals, the one whose error is bigger can
+      //   potentially contain the other one, so we want to proccess its begin
+      //   points before and its end points later.
+      //
+      // * Finally, if we have two equal intervals whose errors have the same
+      //   size, none of them will be strictly contained inside the other.
+      //   Sorting by ErrorId will guarantee that the begin point of the first
+      //   one will be proccessed before, disallowing the second one, and the
+      //   end point of the first one will also be proccessed before,
+      //   disallowing the first one.
+      if (Type == ET_Begin)
+        Priority = std::make_tuple(Begin, Type, -End, -ErrorSize, ErrorId);
+      else
+        Priority = std::make_tuple(End, Type, -Begin, ErrorSize, ErrorId);
+    }
+
+    bool operator<(const Event &Other) const {
+      return Priority < Other.Priority;
+    }
+
+    // Determines if this event is the begin or the end of an interval.
+    EventType Type;
+    // The index of the error to which the interval that generated this event
+    // belongs.
+    unsigned ErrorId;
+    // The events will be sorted based on this field.
+    std::tuple<unsigned, EventType, int, int, unsigned> Priority;
+  };
+
+  // Compute error sizes.
+  std::vector<int> Sizes;
+  for (const auto &Error : Errors) {
+    int Size = 0;
+    for (const auto &Replace : Error.Fix)
+      Size += Replace.getLength();
+    Sizes.push_back(Size);
+  }
+
+  // Build events from error intervals.
+  std::vector<Event> Events;
+  for (unsigned I = 0; I < Errors.size(); ++I) {
+    for (const auto &Replace : Errors[I].Fix) {
+      unsigned Begin = Replace.getOffset();
+      unsigned End = Begin + Replace.getLength();
+      // FIXME: Handle empty intervals, such as those from insertions.
+      if (Begin == End)
+        continue;
+      Events.push_back(Event(Begin, End, Event::ET_Begin, I, Sizes[I]));
+      Events.push_back(Event(Begin, End, Event::ET_End, I, Sizes[I]));
+    }
+  }
+  std::sort(Events.begin(), Events.end());
+
+  // Sweep.
+  std::vector<bool> Apply(Errors.size(), true);
+  int OpenIntervals = 0;
+  for (const auto &Event : Events) {
+    if (Event.Type == Event::ET_End)
+      --OpenIntervals;
+    // This has to be checked after removing the interval from the count if it
+    // is an end event, or before adding it if it is a begin event.
+    if (OpenIntervals != 0)
+      Apply[Event.ErrorId] = false;
+    if (Event.Type == Event::ET_Begin)
+      ++OpenIntervals;
+  }
+  assert(OpenIntervals == 0 && "Amount of begin/end points doesn't match");
+
+  for (unsigned I = 0; I < Errors.size(); ++I) {
+    if (!Apply[I]) {
+      Errors[I].Fix.clear();
+      Errors[I].Notes.push_back(
+          ClangTidyMessage("this fix will not be applied because"
+                           " it overlaps with another fix"));
+    }
+  }
+}
+
 namespace {
 struct LessClangTidyError {
-  bool operator()(const ClangTidyError *LHS, const ClangTidyError *RHS) const {
-    const ClangTidyMessage &M1 = LHS->Message;
-    const ClangTidyMessage &M2 = RHS->Message;
+  bool operator()(const ClangTidyError &LHS, const ClangTidyError &RHS) const {
+    const ClangTidyMessage &M1 = LHS.Message;
+    const ClangTidyMessage &M2 = RHS.Message;
 
     return std::tie(M1.FilePath, M1.FileOffset, M1.Message) <
            std::tie(M2.FilePath, M2.FileOffset, M2.Message);
   }
 };
+struct EqualClangTidyError {
+  static LessClangTidyError Less;
+  bool operator()(const ClangTidyError &LHS, const ClangTidyError &RHS) const {
+    return !Less(LHS, RHS) && !Less(RHS, LHS);
+  }
+};
 } // end anonymous namespace
 
 // Flushes the internal diagnostics buffer to the ClangTidyContext.
 void ClangTidyDiagnosticConsumer::finish() {
   finalizeLastError();
-  std::set<const ClangTidyError*, LessClangTidyError> UniqueErrors;
-  for (const ClangTidyError &Error : Errors)
-    UniqueErrors.insert(&Error);
 
-  for (const ClangTidyError *Error : UniqueErrors)
-    Context.storeError(*Error);
+  std::sort(Errors.begin(), Errors.end(), LessClangTidyError());
+  Errors.erase(std::unique(Errors.begin(), Errors.end(), EqualClangTidyError()),
+               Errors.end());
+  removeIncompatibleErrors(Errors);
+
+  for (const ClangTidyError &Error : Errors)
+    Context.storeError(Error);
   Errors.clear();
 }

unittests/clang-tidy/OverlappingReplacementsTest.cpp

void registerMatchers(ast_matchers::MatchFinder *Finder) final {
     using namespace ast_matchers;
     Finder->addMatcher(varDecl(matchesName(NamePattern)).bind(BoundDecl), this);
   }
 
   void check(const ast_matchers::MatchFinder::MatchResult &Result) final {
     auto *VD = Result.Nodes.getNodeAs<VarDecl>(BoundDecl);
     std::string NewName = newName(VD->getName());
 
-    auto Diag = diag(VD->getLocation(), "refactor")
+    auto Diag = diag(VD->getLocation(), "refactor %0 into %1")
+                << VD->getName() << NewName
                 << FixItHint::CreateReplacement(
                        CharSourceRange::getTokenRange(VD->getLocation(),
                                                       VD->getLocation()),
                        NewName);
 
     class UsageVisitor : public RecursiveASTVisitor<UsageVisitor> {
     public:
       UsageVisitor(const ValueDecl *VD, StringRef NewName,
                    DiagnosticBuilder &Diag)
           : VD(VD), NewName(NewName), Diag(Diag) {}
       bool VisitDeclRefExpr(DeclRefExpr *E) {
         if (const ValueDecl *D = E->getDecl()) {
TEST(OverlappingReplacementsTest, ReplacementInsideOtherReplacement) {
   } else if (int a = 0) {
     char potato = 0;
     if (potato) potato;
   }
 })";
 
   // Apply the UseCharCheck together with the IfFalseCheck.
   //
-  // The 'If' fix is bigger, so that is the one that has to be applied.
+  // The 'If' fix contains the other, so that is the one that has to be applied.
   // } else if (int a = 0) {
   //            ^^^ -> char
   //            ~~~~~~~~~ -> false
   const char CharIfFix[] =
       R"(void f() {
   if (false) {
   } else if (false) {
     char potato = 0;
     if (false) potato;
   }
 })";
   Res = runCheckOnCode<UseCharCheck, IfFalseCheck>(Code);
-  // FIXME: EXPECT_EQ(CharIfFix, Res);
+  EXPECT_EQ(CharIfFix, Res);
+  Res = runCheckOnCode<IfFalseCheck, UseCharCheck>(Code);
+  EXPECT_EQ(CharIfFix, Res);
 
   // Apply the IfFalseCheck with the StartsWithPotaCheck.
   //
   // The 'If' replacement is bigger here.
   // if (char potato = 0) {
   //          ^^^^^^ -> tomato
   //     ~~~~~~~~~~~~~~~ -> false
   //
-  // But the refactoring is bigger here:
+  // But the refactoring is the one that contains the other here:
   // char potato = 0;
   //      ^^^^^^ -> tomato
   // if (potato) potato;
   //     ^^^^^^  ^^^^^^ -> tomato, tomato
   //     ~~~~~~ -> false
   const char IfStartsFix[] =
       R"(void f() {
   if (false) {
   } else if (false) {
     char tomato = 0;
     if (tomato) tomato;
   }
 })";
   Res = runCheckOnCode<IfFalseCheck, StartsWithPotaCheck>(Code);
-  // FIXME: EXPECT_EQ(IfStartsFix, Res);
-
-  // Silence warnings.
-  (void)CharIfFix;
-  (void)IfStartsFix;
+  EXPECT_EQ(IfStartsFix, Res);
+  Res = runCheckOnCode<StartsWithPotaCheck, IfFalseCheck>(Code);
+  EXPECT_EQ(IfStartsFix, Res);
 }
 
-TEST(OverlappingReplacementsTest, ApplyFullErrorOrNothingWhenOverlapping) {
+TEST(OverlappingReplacements, TwoReplacementsInsideOne) {
   std::string Res;
   const char Code[] =
       R"(void f() {
-  int potato = 0;
-  potato += potato * potato;
-  if (char this_name_make_this_if_really_long = potato) potato;
+  if (int potato = 0) {
+    int a = 0;
+  }
 })";
 
-  // StartsWithPotaCheck will try to refactor 'potato' into 'tomato',
-  // and EndsWithTatoCheck will try to use 'pomelo'. We have to apply
-  // either all conversions from one check, or all from the other.
-  const char StartsFix[] =
+  // The two smallest replacements should not be applied.
+  // if (int potato = 0) {
+  //         ^^^^^^ -> tomato
+  //     *** -> char
+  //     ~~~~~~~~~~~~~~ -> false
+  // But other errors from the same checks should not be affected.
+  //   int a = 0;
+  //   *** -> char
+  const char Fix[] =
       R"(void f() {
-  int tomato = 0;
-  tomato += tomato * tomato;
-  if (char this_name_make_this_if_really_long = tomato) tomato;
+  if (false) {
+    char a = 0;
+  }
 })";
-  const char EndsFix[] =
+  Res = runCheckOnCode<UseCharCheck, IfFalseCheck, StartsWithPotaCheck>(Code);
+  EXPECT_EQ(Fix, Res);
+  Res = runCheckOnCode<StartsWithPotaCheck, IfFalseCheck, UseCharCheck>(Code);
+  EXPECT_EQ(Fix, Res);
+}
+
+TEST(OverlappingReplacementsTest,
+     ApplyAtMostOneOfTheChangesWhenPartialOverlapping) {
+  std::string Res;
+  const char Code[] =
       R"(void f() {
-  int pomelo = 0;
-  pomelo += pomelo * pomelo;
-  if (char this_name_make_this_if_really_long = pomelo) pomelo;
+  if (int potato = 0) {
+    int a = potato;
+  }
 })";
-  // In case of overlapping, we will prioritize the biggest fix. However, these
-  // two fixes have the same size and position, so we don't know yet which one
-  // will have preference.
-  Res = runCheckOnCode<StartsWithPotaCheck, EndsWithTatoCheck>(Code);
-  // FIXME: EXPECT_TRUE(Res == StartsFix || Res == EndsFix);
 
-  // StartsWithPotaCheck will try to refactor 'potato' into 'tomato', but
-  // replacing the 'if' condition is a bigger change than all the refactoring
-  // changes together (48 vs 36), so this is the one that is going to be
-  // applied.
+  // These two replacements overlap, but none of them is completely contained
+  // inside the other.
+  // if (int potato = 0) {
+  //         ^^^^^^ -> tomato
+  //     ~~~~~~~~~~~~~~ -> false
+  //   int a = potato;
+  //           ^^^^^^ -> tomato
+  //
+  // The 'StartsWithPotaCheck' fix has endpoints inside the 'IfFalseCheck' fix,
+  // so it is going to be set as inapplicable. The 'if' fix will be applied.
   const char IfFix[] =
       R"(void f() {
+  if (false) {
+    int a = potato;
+  }
+})";
+  Res = runCheckOnCode<IfFalseCheck, StartsWithPotaCheck>(Code);
+  EXPECT_EQ(IfFix, Res);
+}
+
+TEST(OverlappingReplacementsTest, TwoErrorsHavePerfectOverlapping) {
+  std::string Res;
+  const char Code[] =
+      R"(void f() {
   int potato = 0;
   potato += potato * potato;
-  if (true) potato;
+  if (char a = potato) potato;
 })";
-  Res = runCheckOnCode<StartsWithPotaCheck, IfFalseCheck>(Code);
-  // FIXME: EXPECT_EQ(IfFix, Res);
 
-  // Silence warnings.
-  (void)StartsFix;
-  (void)EndsFix;
-  (void)IfFix;
+  // StartsWithPotaCheck will try to refactor 'potato' into 'tomato', and
+  // EndsWithTatoCheck will try to use 'pomelo'. Both fixes have the same set of
+  // ranges. This is a corner case of one error completely containing another:
+  // the other completely contains the first one as well. Both errors are
+  // discarded.
+
+  Res = runCheckOnCode<StartsWithPotaCheck, EndsWithTatoCheck>(Code);
+  EXPECT_EQ(Code, Res);
 }
 
 } // namespace test
 } // namespace tidy
 } // namespace clang