[clang-format] [PR43372] - clang-format shows replacements in DOS files when no replacement is needed

[MyDeveloperDay]

Summary

This is a patch to fix PR43372 (https://bugs.llvm.org/show_bug.cgi?id=43372) - clang-format can't format file with includes, ( which really keep providing replacements for already sorted headers.)

A similar issue was addressed by @krasimir in D60199: [clang-format] Do not emit replacements while regrouping if Cpp includes are OK, however, this seemingly only prevented the issue when the files being formatted did not contain windows line endings (\r\n)

It's possible this is related to https://twitter.com/StephanTLavavej/status/1176722938243895296 given who @STL_MSFT works for!

As people often used the existence of replacements to determine if a file needs clang-formatting, this is probably pretty important for windows users

There may be a better way of comparing 2 strings and ignoring \r (which appear in both Results and Code), I couldn't choose between this idiom or the copy_if approach, but I'm happy to change it to whatever people consider more performant.

[krasimir]

clang/lib/Format/Format.cpp

1891 ↗

(On Diff #222431)

Here compartIgnoringCarriageReturns is a bit imprecise: there could be \r-s not followed by \n-s in the source code.
Since we have constructed result with newlines as \n-s in this code, I'd suggest to instead implement a function that replaces all occurrences of \r\n with \n in a string (something like "stripNewlineCRs") and have a comparison like result == stripNewlineCRs(...) here. That shouldn't be much harder than this approach and will be a bit more precise.
I've looked around the Format code for preexisting functionality we can reuse, but it seems most of the \r\n handling is concerned with outputting the right newline encoding and not with reading it.

[MyDeveloperDay]

Through experiments, I notice that both result and the Code contains "\r\n", because although we construct the results with "\n" the actual text of the include has I believe trailing "\r" or "\r\n", I notice this when I thought one fix I tried was to trim the include text.

`result += Imports[Index].Text.trim()``

However, this had the effect of dos2unixing the `result``` and the include section of a windows file

but I take your point about the "\r" without the "\r\n"

I'll change the code but I believe it will need to be

if (stripNewlineCRs(result) == stripNewlineCRs(...))

I'll send an updated review

[MyDeveloperDay]

Being specific about replacing "\r\n"'s with "\n"'s rather than removing just \r's

[krasimir]

clang/lib/Format/Format.cpp

1828 ↗

(On Diff #222498)

nit: missing trailing fullstop.

1832 ↗

(On Diff #222498)

The worst-case complexity of this code is quadratic, since std::string::replace is linear in the size of the resulting string.
If we have an include block of a few hundred lines, each a hundred or so characters, I could imagine that could easily add up.
I'd suggest constructing the result by appending to a fresh string to keep the overall complexity linear.
You can then take the argument by const reference.

1838 ↗

(On Diff #222498)

Maybe refine this comment: ignoring any \r, followed by \n in either strings.
Alternatively, since this function is just performing a comparison, consider directly inlining it in the if statements below (not too strong opinion).

[krasimir]

Thank you!

cfe/trunk/lib/Format/Format.cpp

for (int i = 0, e = Includes.size(); i != e; ++i) {
     // #includes.
     while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
       CursorIndex = i;
     break;
   }
   return std::make_pair(CursorIndex, OffsetToEOL);
 }
 
+// Replace all "\r\n" with "\n".
+std::string replaceCRLF(const std::string &Code) {
+  std::string NewCode;
+  size_t Pos = 0, LastPos = 0;
+
+  do {
+    Pos = Code.find("\r\n", LastPos);
+    if (Pos == LastPos) {
+      LastPos++;
+      continue;
+    }
+    if (Pos == std::string::npos) {
+      NewCode += Code.substr(LastPos);
+      break;
+    }
+    NewCode += Code.substr(LastPos, Pos - LastPos) + "\n";
+    LastPos = Pos + 2;
+  } while (Pos != std::string::npos);
+
+  return NewCode;
+}
+
 // Sorts and deduplicate a block of includes given by 'Includes' alphabetically
 // adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
 // source order.
 // #include directives with the same text will be deduplicated, and only the
 // first #include in the duplicate #includes remains. If the `Cursor` is
 // provided and put on a deleted #include, it will be moved to the remaining
 // #include in the duplicate #includes.
 static void sortCppIncludes(const FormatStyle &Style,
for (unsigned Index : Indices) {
     result += Includes[Index].Text;
     if (Cursor && CursorIndex == Index)
       *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
     CurrentCategory = Includes[Index].Category;
   }
 
   // If the #includes are out of order, we generate a single replacement fixing
   // the entire range of blocks. Otherwise, no replacement is generated.
-  if (result == Code.substr(IncludesBeginOffset, IncludesBlockSize))
+  if (replaceCRLF(result) ==
+      replaceCRLF(Code.substr(IncludesBeginOffset, IncludesBlockSize)))
     return;
 
   auto Err = Replaces.add(tooling::Replacement(
       FileName, Includes.front().Offset, IncludesBlockSize, result));
   // FIXME: better error handling. For now, just skip the replacement for the
   // release version.
   if (Err) {
     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
for (unsigned Index : Indices) {
     }
     result += Imports[Index].Text;
     CurrentIsStatic = Imports[Index].IsStatic;
     CurrentImportGroup = JavaImportGroups[Index];
   }
 
   // If the imports are out of order, we generate a single replacement fixing
   // the entire block. Otherwise, no replacement is generated.
-  if (result == Code.substr(Imports.front().Offset, ImportsBlockSize))
+  if (replaceCRLF(result) ==
+      replaceCRLF(Code.substr(Imports.front().Offset, ImportsBlockSize)))
     return;
 
   auto Err = Replaces.add(tooling::Replacement(FileName, Imports.front().Offset,
                                                ImportsBlockSize, result));
   // FIXME: better error handling. For now, just skip the replacement for the
   // release version.
   if (Err) {
     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
if (Style.Language == FormatStyle::LK_JavaScript &&
     });
 
   Passes.emplace_back([&](const Environment &Env) {
     return Formatter(Env, Expanded, Status).process();
   });
 
   auto Env =
       std::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
-                                     NextStartColumn, LastStartColumn);
   llvm::Optional<std::string> CurrentCode = None;
   tooling::Replacements Fixes;
   unsigned Penalty = 0;
   for (size_t I = 0, E = Passes.size(); I < E; ++I) {
     std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
     auto NewCode = applyAllReplacements(
         CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
     if (NewCode) {

cfe/trunk/unittests/Format/SortImportsTestJava.cpp

 TEST_F(SortImportsTestJava, NoReplacementsForValidImports) {
   // Identical #includes have led to a failure with an unstable sort.
   std::string Code = "import org.a;\n"
                      "import org.b;\n";
   EXPECT_TRUE(
       sortIncludes(FmtStyle, Code, GetCodeRange(Code), "input.java").empty());
 }
 
+TEST_F(SortImportsTestJava, NoReplacementsForValidImportsWindows) {
+  std::string Code = "import org.a;\r\n"
+                     "import org.b;\r\n";
+  EXPECT_TRUE(
+      sortIncludes(FmtStyle, Code, GetCodeRange(Code), "input.java").empty());
+}
+
 } // end namespace
 } // end namespace format
 } // end namespace clang

cfe/trunk/unittests/Format/SortIncludesTest.cpp

TEST_F(SortIncludesTest, DoNotOutputReplacementsForSortedBlocksWithRegrouping) {
   std::string Code = R"(
 #include "b.h"
 
 #include <a.h>
 )";
   EXPECT_EQ(Code, sort(Code, "input.h", 0));
 }
 
+TEST_F(SortIncludesTest,
+       DoNotOutputReplacementsForSortedBlocksWithRegroupingWindows) {
+  Style.IncludeBlocks = Style.IBS_Regroup;
+  std::string Code = "#include \"b.h\"\r\n"
+                     "\r\n"
+                     "#include <a.h>\r\n";
+  EXPECT_EQ(Code, sort(Code, "input.h", 0));
+}
 
 TEST_F(SortIncludesTest, DoNotRegroupGroupsInGoogleObjCStyle) {
   FmtStyle = getGoogleStyle(FormatStyle::LK_ObjC);
 
   EXPECT_EQ("#include <a.h>\n"
             "#include <b.h>\n"
             "#include \"a.h\"",
             sort("#include <b.h>\n"
                  "#include <a.h>\n"
                  "#include \"a.h\""));
 }
 
 } // end namespace
 } // end namespace format
 } // end namespace clang