Add clang-format stability check with FormatTests

[vglavnyy]

Summary

Twice running clang-format may give unstable result for some code samples, for example: https://bugs.llvm.org/show_bug.cgi?id=23728
This commit adds stability check to clang-format unit-tests.
After apply this patch 10 tests from the FormatTests will fail.

[==========] 647 tests from 19 test cases ran. (31449 ms total)
[ PASSED ] 637 tests.
[ FAILED ] 10 tests, listed below:
[ FAILED ] FormatTest.OnlyGeneratesNecessaryReplacements
[ FAILED ] FormatTest.BreaksStringLiterals
[ FAILED ] FormatTest.BreaksStringLiteralsWithTabs
[ FAILED ] FormatTest.BreaksWideAndNSStringLiterals
[ FAILED ] FormatTest.BreaksStringLiteralsWithin_TMacro
[ FAILED ] FormatTest.DoNotBreakStringLiteralsInEscapeSequence
[ FAILED ] FormatTest.OptimizeBreakPenaltyVsExcess
[ FAILED ] FormatTest.WorksFor8bitEncodings
[ FAILED ] FormatTest.SplitsUTF8Strings
[ FAILED ] FormatTest.SupportsCRLF

[krasimir]

Sadly I tried this out a year ago and hit the same thing. A root cause is that tabs have variable column length depending on their start column, and in clang-format tokens are modeled as entities having a fixed column width. There are FIXMEs about this in the codebase (https://github.com/llvm-mirror/clang/blob/41e165b659ec7d8262153a6e0ed9130431c886de/lib/Format/FormatTokenLexer.cpp#L641).
A patch that adds stability to tests would have to address the underlying root cause which requires quite a lot of stuff to be threaded over clang-format and for practical purposes folks using clang-format are not complaining about this enough to be worth spending the effort and added complexity fixing this. I know, it sucks, but that's the situation right now.

[vglavnyy]

A twice-format problem: the format of format isn't format.
This commit surface an instability problem in clang-format at unit-tests level.
The patch adds double-checking format method for all test and adds a stub for tests with the detected TF-problem.

[vglavnyy]

@krasimir thank you for review.
The patch code has been updated.
I hope this patch will help to start to fix this issue.
Probably will be helpful to add an optional debug flag will enable a twice-run checking for every run of clang-format.

[krasimir]

The problem with this is that I believe fixing this issue is not worth it, hence this patch is unnecessary. Feel free to reach out to djasper@ for a second opinion. For completeness, was the unstability a problem just in FormatTest.cpp, how about the other FormatTest*.cpp in the same directory?

[aardappel]

@krasimir first you say that fixing it is hard, then when someone wants to attempt, that it is not necessary?

Plenty of people run clang-format in automated fashion as part of some pipeline, seems to me results ping-ponging between two formattings and cluttering commits would be pretty bad.

I just ran into this bug (https://bugs.llvm.org/show_bug.cgi?id=39280) and now instructions to my contributors are going to have to be: please run clang-format twice :)

[MyDeveloperDay]

As @krasimir said we wouldn't normally commit tests which just break as they'd fail on the buildbot and someone would revert your change within 24 hours.. however, what you have here raises an interesting conversation

This bug of instability is often raised, I've even seen it myself with my own code and I normally see new bugs coming in about this on a regular basis

https://bugs.llvm.org/show_bug.cgi?id=43845
https://bugs.llvm.org/show_bug.cgi?id=42509

Firstly those developers who have clang-formated integrated into say vim,emac,vs,vscode with format on save likely never see this because they often format multiple times during their development and its likely those instabilities iron themselves out pretty quickly, but this does show up for those people who perhaps only do a final git clang-format before committing or who are reformatting a largely unformatted code base, then the CI system likely complains on commit if you have a check.

It would be good to investigate the root causes, but my experience seems to be that it often feels related to the alignment rules and the positioning of trailing comments. (at least that my experience)

It would also be good to understand if this is always solved with a second run or does it sometimes require more than two runs, or has anyone seen a case where the format flip-flops between 2 styles.

Ultimately fixing the alignment routines to try and make them completely stable with regard to future downstream rules, I believe would simply make them individually more complex and unstable if new rules were added.

It might be worth simply rerunning the specific alignXXX routine again on the subsequent changes.

I'd also be interested to understand if any real thought was put into the order of these routines? Or if just conceptually if you are trying to align declarations, assignments and trailing comments something has to go first and you don't know where the best place is until someone takes a first stab.

llvm::sort(Changes, Change::IsBeforeInFile(SourceMgr));
calculateLineBreakInformation();
alignConsecutiveMacros();
alignConsecutiveDeclarations();
alignConsecutiveAssignments();
alignTrailingComments();
alignEscapedNewlines();
generateChanges();

I'd would like to think there was a more elegant approach than just running clang-format twice! one solution might be to simply rerun the whole of reformat() function more than once. Of course, we have to keep one eye on performance because for large files clang-format can already be a little slow.

But running reformat() wouldn't be 2x because we definitely don't need to rerun the sort includes twice and we don't need to reannotate the tokens, detemine the spaces between or apply the replacements twice (+ no startup costs, dll loading, code rewriting), so I actually think a second pass of reformat might not be terrible. (maybe undesirable but not terrible)

What if we experiment with a -stable command line switch which simply reruns those parts of reformat that are causing the issues? and then measure the impact to performance?

[aardappel]

@MyDeveloperDay thanks for your thoughts.. while -stable would be helpful once you know you have the issue (or to permanently turn on in a git pre-submit), it does not help developers that don't even know this is a thing, and waste a bunch of time figuring out what is going on. In fact, it took me longer to figure out simply because I assumed it is unlikely that clang-format has such a bug :)

It might almost make sense in reverse: -stable by default, and have a -un-stable for those users where clang-format becomes a performance bottleneck :) But once you admit that, might as well fix the core problem instead.

[MyDeveloperDay]

In D53482#1737203, @aardappel wrote:

@MyDeveloperDay thanks for your thoughts.. while -stable would be helpful once you know you have the issue (or to permanently turn on in a git pre-submit), it does not help developers that don't even know this is a thing, and waste a bunch of time figuring out what is going on. In fact, it took me longer to figure out simply because I assumed it is unlikely that clang-format has such a bug :)

It might almost make sense in reverse: -stable by default, and have a -un-stable for those users where clang-format becomes a performance bottleneck :) But once you admit that, might as well fix the core problem instead.

Sorry I didn't make myself clear,I wasn't thinking of a final customer facing solution, I was only really thinking of adding the -stable purely so we could pass a flag down and try different levels of repeating so we could do some performance tests. I feel it might be related to these 3 below, but was trying to think about how we could easily experiment.. I think ultimately we'd want a stable solution.

alignConsecutiveDeclarations();
alignConsecutiveAssignments();
alignTrailingComments();

unittests/Format/FormatTest.cpp

     SC_DoNotCheck
   };
 
-  std::string format(llvm::StringRef Code,
+  std::string format_weak(llvm::StringRef Code,
                           const FormatStyle &Style = getLLVMStyle(),
                           StatusCheck CheckComplete = SC_ExpectComplete) {
     LLVM_DEBUG(llvm::errs() << "---\n");
     LLVM_DEBUG(llvm::errs() << Code << "\n\n");
     std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));

     return *Result;
   }
 
+  // Format method with invariant check: format(Code)==format(format(Code)).
+  std::string format(llvm::StringRef Code,
+                     const FormatStyle &Style = getLLVMStyle(),
+                     StatusCheck CheckComplete = SC_ExpectComplete) {
+    const auto Formatted = format_weak(Code, Style, CheckComplete);
+    if (CheckComplete != SC_DoNotCheck) {
+      auto SaveReplacementCount = ReplacementCount;
+      EXPECT_EQ(Formatted, format_weak(Formatted, Style, CheckComplete));
+      ReplacementCount = SaveReplacementCount;
+    }
+    return Formatted;
+  }
+
+  // A stub-method for tests with broken invariant: format(Code)!=format(format(Code)).
+  // Will be redundant when all tests become stable.
+  std::string format_unstable(llvm::StringRef Code,
+                     const FormatStyle &Style = getLLVMStyle(),
+                     StatusCheck CheckComplete = SC_ExpectComplete) {
+    const auto Formatted = format_weak(Code, Style, CheckComplete);
+    if (CheckComplete != SC_DoNotCheck) {
+      auto SaveReplacementCount = ReplacementCount;
+      EXPECT_NE(Formatted, format_weak(Formatted, Style, CheckComplete));
+      ReplacementCount = SaveReplacementCount;
+    }
+    return Formatted;
+  }
+
   FormatStyle getStyleWithColumns(FormatStyle Style, unsigned ColumnLimit) {
     Style.ColumnLimit = ColumnLimit;
     return Style;

 
 
 TEST_F(FormatTest, BreaksStringLiterals) {
-  EXPECT_EQ("\"some text \"\n"
-            "\"other\";",
-            format("\"some text other\";", getLLVMStyleWithColumns(12)));
-  EXPECT_EQ("\"some text \"\n"
-            "\"other\";",
-            format("\\\n\"some text other\";", getLLVMStyleWithColumns(12)));
+  EXPECT_EQ(
+      "\"some text \"\n"
+      "\"other\";",
+      format_unstable("\"some text other\";", getLLVMStyleWithColumns(12)));
+  EXPECT_EQ(
+      "\"some text \"\n"
+      "\"other\";",
+      format_unstable("\\\n\"some text other\";", getLLVMStyleWithColumns(12)));
   EXPECT_EQ(
       "#define A  \\\n"
       "  \"some \"  \\\n"

             format("\"some text\"", getLLVMStyleWithColumns(11)));
   EXPECT_EQ("\"some \"\n"
             "\"text\"",
-            format("\"some text\"", getLLVMStyleWithColumns(10)));
+            format_unstable("\"some text\"", getLLVMStyleWithColumns(10)));
   EXPECT_EQ("\"some \"\n"
             "\"text\"",
-            format("\"some text\"", getLLVMStyleWithColumns(7)));
+            format_unstable("\"some text\"", getLLVMStyleWithColumns(7)));
   EXPECT_EQ("\"some\"\n"
             "\" tex\"\n"
             "\"t\"",
-            format("\"some text\"", getLLVMStyleWithColumns(6)));
+            format_unstable("\"some text\"", getLLVMStyleWithColumns(6)));
   EXPECT_EQ("\"some\"\n"
             "\" tex\"\n"
             "\" and\"",
-            format("\"some tex and\"", getLLVMStyleWithColumns(6)));
+            format_unstable("\"some tex and\"", getLLVMStyleWithColumns(6)));
   EXPECT_EQ("\"some\"\n"
             "\"/tex\"\n"
             "\"/and\"",
-            format("\"some/tex/and\"", getLLVMStyleWithColumns(6)));
+            format_unstable("\"some/tex/and\"", getLLVMStyleWithColumns(6)));
 
   EXPECT_EQ("variable =\n"
             "    \"long string \"\n"

       "    aaaaaaaaaaaaaaaaaaaa,\n"
       "    aaaaaa(\"aaa aaaaa aaa aaa aaaaa aaa aaaaa aaa aaa aaaaaa\"));");
 
-  EXPECT_EQ("\"splitmea\"\n"
-            "\"trandomp\"\n"
-            "\"oint\"",
-            format("\"splitmeatrandompoint\"", getLLVMStyleWithColumns(10)));
+  EXPECT_EQ(
+      "\"splitmea\"\n"
+      "\"trandomp\"\n"
+      "\"oint\"",
+      format_unstable("\"splitmeatrandompoint\"", getLLVMStyleWithColumns(10)));
 
-  EXPECT_EQ("\"split/\"\n"
-            "\"pathat/\"\n"
-            "\"slashes\"",
-            format("\"split/pathat/slashes\"", getLLVMStyleWithColumns(10)));
+  EXPECT_EQ(
+      "\"split/\"\n"
+      "\"pathat/\"\n"
+      "\"slashes\"",
+      format_unstable("\"split/pathat/slashes\"", getLLVMStyleWithColumns(10)));
 
-  EXPECT_EQ("\"split/\"\n"
-            "\"pathat/\"\n"
-            "\"slashes\"",
-            format("\"split/pathat/slashes\"", getLLVMStyleWithColumns(10)));
   EXPECT_EQ("\"split at \"\n"
             "\"spaces/at/\"\n"
             "\"slashes.at.any$\"\n"
             "\"non-alphanumeric%\"\n"
             "\"1111111111characte\"\n"
             "\"rs\"",
-            format("\"split at "
+            format_unstable("\"split at "
                             "spaces/at/"
                             "slashes.at."
                             "any$non-"
                             "alphanumeric%"
                             "1111111111characte"
                             "rs\"",
                             getLLVMStyleWithColumns(20)));
 
   // Verify that splitting the strings understands
   // Style::AlwaysBreakBeforeMultilineStrings.

       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
       "(\n"
       "    \"x\t\");",
-      format("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
-             "aaaaaaa("
-             "\"x\t\");"));
+      format_unstable(
+          "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+          "aaaaaaa("
+          "\"x\t\");"));
 }
 
 TEST_F(FormatTest, BreaksWideAndNSStringLiterals) {
-  EXPECT_EQ(
-      "u8\"utf8 string \"\n"
-      "u8\"literal\";",
-      format("u8\"utf8 string literal\";", getGoogleStyleWithColumns(16)));
-  EXPECT_EQ(
-      "u\"utf16 string \"\n"
-      "u\"literal\";",
-      format("u\"utf16 string literal\";", getGoogleStyleWithColumns(16)));
-  EXPECT_EQ(
-      "U\"utf32 string \"\n"
-      "U\"literal\";",
-      format("U\"utf32 string literal\";", getGoogleStyleWithColumns(16)));
+  EXPECT_EQ("u8\"utf8 string \"\n"
+            "u8\"literal\";",
+            format_unstable("u8\"utf8 string literal\";",
+                            getGoogleStyleWithColumns(16)));
+  EXPECT_EQ("u\"utf16 string \"\n"
+            "u\"literal\";",
+            format_unstable("u\"utf16 string literal\";",
+                            getGoogleStyleWithColumns(16)));
+  EXPECT_EQ("U\"utf32 string \"\n"
+            "U\"literal\";",
+            format_unstable("U\"utf32 string literal\";",
+                            getGoogleStyleWithColumns(16)));
   EXPECT_EQ("L\"wide string \"\n"
             "L\"literal\";",
-            format("L\"wide string literal\";", getGoogleStyleWithColumns(16)));
+            format_unstable("L\"wide string literal\";",
+                            getGoogleStyleWithColumns(16)));
   EXPECT_EQ("@\"NSString \"\n"
             "@\"literal\";",
             format("@\"NSString literal\";", getGoogleStyleWithColumns(19)));

 
 TEST_F(FormatTest, BreaksStringLiteralsWithin_TMacro) {
   FormatStyle Style = getLLVMStyleWithColumns(20);
-  EXPECT_EQ(
+  EXPECT_EQ("_T(\"aaaaaaaaaaaaaa\")\n"
             "_T(\"aaaaaaaaaaaaaa\")\n"
-      "_T(\"aaaaaaaaaaaaaa\")\n"
-      "_T(\"aaaaaaaaaaaa\")",
-      format("  _T(\"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\")", Style));
+            "_T(\"aaaaaaaaaaaa\")",
+            format_unstable(
+                "  _T(\"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\")", Style));
   EXPECT_EQ("f(x,\n"
             "  _T(\"aaaaaaaaaaaa\")\n"
             "  _T(\"aaa\"),\n"

   EXPECT_EQ("\"\\\"", format("\"\\\"", getLLVMStyleWithColumns(2)));
   EXPECT_EQ("\"test\"\n"
             "\"\\n\"",
-            format("\"test\\n\"", getLLVMStyleWithColumns(7)));
+            format_unstable("\"test\\n\"", getLLVMStyleWithColumns(7)));
   EXPECT_EQ("\"tes\\\\\"\n"
             "\"n\"",
-            format("\"tes\\\\n\"", getLLVMStyleWithColumns(7)));
+            format_unstable("\"tes\\\\n\"", getLLVMStyleWithColumns(7)));
   EXPECT_EQ("\"\\\\\\\\\"\n"
             "\"\\n\"",
-            format("\"\\\\\\\\\\n\"", getLLVMStyleWithColumns(7)));
+            format_unstable("\"\\\\\\\\\\n\"", getLLVMStyleWithColumns(7)));
   EXPECT_EQ("\"\\uff01\"", format("\"\\uff01\"", getLLVMStyleWithColumns(7)));
   EXPECT_EQ("\"\\uff01\"\n"
             "\"test\"",
-            format("\"\\uff01test\"", getLLVMStyleWithColumns(8)));
+            format_unstable("\"\\uff01test\"", getLLVMStyleWithColumns(8)));
   EXPECT_EQ("\"\\Uff01ff02\"",
             format("\"\\Uff01ff02\"", getLLVMStyleWithColumns(11)));
   EXPECT_EQ("\"\\x000000000001\"\n"
             "\"next\"",
-            format("\"\\x000000000001next\"", getLLVMStyleWithColumns(16)));
+            format_unstable("\"\\x000000000001next\"", getLLVMStyleWithColumns(16)));
   EXPECT_EQ("\"\\x000000000001next\"",
             format("\"\\x000000000001next\"", getLLVMStyleWithColumns(15)));
   EXPECT_EQ("\"\\x000000000001\"",

   EXPECT_EQ("\"test\"\n"
             "\"\\000000\"\n"
             "\"000001\"",
-            format("\"test\\000000000001\"", getLLVMStyleWithColumns(9)));
+            format_unstable("\"test\\000000000001\"", getLLVMStyleWithColumns(9)));
   EXPECT_EQ("\"test\\000\"\n"
             "\"00000000\"\n"
             "\"1\"",
-            format("\"test\\000000000001\"", getLLVMStyleWithColumns(10)));
+            format_unstable("\"test\\000000000001\"", getLLVMStyleWithColumns(10)));
 }
 
 TEST_F(FormatTest, DoNotCreateUnreasonableUnwrappedLines) {

   EXPECT_EQ("// foo bar baz bazfoo\n"
             "// foo bar baz bazfoo\n"
             "// bar foo bar\n",
-            format("// foo bar baz      bazfoo\n"
+            format_unstable("// foo bar baz      bazfoo\n"
                             "// foo bar baz      bazfoo bar\n"
                             "// foo bar\n",
                             Style));
 
   EXPECT_EQ("// foo bar baz bazfoo\n"
             "// foo bar baz bazfoo\n"
             "// bar foo bar\n",
-            format("// foo bar baz      bazfoo\n"
+            format_unstable("// foo bar baz      bazfoo\n"
                             "// foo bar baz      bazfoo bar\n"
                             "// foo           bar\n",
                             Style));
 
   // Make sure we do not keep protruding characters if strict mode reflow is
   // cheaper than keeping protruding characters.

             "\"\xf1\xf2\xf3\xe4\xb8\xed\xf3\xfe \"\n"
             "\"\xe7\xe8\xec\xed\xfe\xfe \"\n"
             "\"\xef\xee\xf0\xf3...\"",
-            format("\"\xce\xe4\xed\xe0\xe6\xe4\xfb \xe2 "
-                   "\xf1\xf2\xf3\xe4\xb8\xed\xf3\xfe \xe7\xe8\xec\xed\xfe\xfe "
-                   "\xef\xee\xf0\xf3...\"",
-                   getLLVMStyleWithColumns(12)));
+            format_unstable(
+                "\"\xce\xe4\xed\xe0\xe6\xe4\xfb \xe2 "
+                "\xf1\xf2\xf3\xe4\xb8\xed\xf3\xfe \xe7\xe8\xec\xed\xfe\xfe "
+                "\xef\xee\xf0\xf3...\"",
+                getLLVMStyleWithColumns(12)));
 }
 
 TEST_F(FormatTest, HandlesUTF8BOM) {

   // (e.g. "<8d>"), so there's no single correct way to handle them.
   EXPECT_EQ("\"aaaaÄ\"\n"
             "\"\xc2\x8d\";",
-            format("\"aaaaÄ\xc2\x8d\";", getLLVMStyleWithColumns(10)));
-  EXPECT_EQ("\"aaaaaaaÄ\"\n"
-            "\"\xc2\x8d\";",
-            format("\"aaaaaaaÄ\xc2\x8d\";", getLLVMStyleWithColumns(10)));
+            format_unstable("\"aaaaÄ\xc2\x8d\";", getLLVMStyleWithColumns(10)));
+  EXPECT_EQ(
+      "\"aaaaaaaÄ\"\n"
+      "\"\xc2\x8d\";",
+      format_unstable("\"aaaaaaaÄ\xc2\x8d\";", getLLVMStyleWithColumns(10)));
   EXPECT_EQ("\"Однажды, в \"\n"
             "\"студёную \"\n"
             "\"зимнюю \"\n"
             "\"пору,\"",
-            format("\"Однажды, в студёную зимнюю пору,\"",
+            format_unstable("\"Однажды, в студёную зимнюю пору,\"",
                             getLLVMStyleWithColumns(13)));
-  EXPECT_EQ(
-      "\"一 二 三 \"\n"
-      "\"四 五六 \"\n"
-      "\"七 八 九 \"\n"
-      "\"十\"",
-      format("\"一 二 三 四 五六 七 八 九 十\"", getLLVMStyleWithColumns(11)));
+  EXPECT_EQ("\"一 二 三 \"\n"
+            "\"四 五六 \"\n"
+            "\"七 八 九 \"\n"
+            "\"十\"",
+            format_unstable("\"一 二 三 四 五六 七 八 九 十\"",
+                            getLLVMStyleWithColumns(11)));
   EXPECT_EQ("\"一\t\"\n"
             "\"二 \t\"\n"
             "\"三 四 \"\n"

             "\"六 \t\"\n"
             "\"七 \"\n"
             "\"八九十\tqq\"",
-            format("\"一\t二 \t三 四 五\t六 \t七 八九十\tqq\"",
+            format_unstable("\"一\t二 \t三 四 五\t六 \t七 八九十\tqq\"",
                             getLLVMStyleWithColumns(11)));
 
   // UTF8 character in an escape sequence.
-  EXPECT_EQ("\"aaaaaa\"\n"
-            "\"\\\xC2\x8D\"",
-            format("\"aaaaaa\\\xC2\x8D\"", getLLVMStyleWithColumns(10)));
+  EXPECT_EQ(
+      "\"aaaaaa\"\n"
+      "\"\\\xC2\x8D\"",
+      format_unstable("\"aaaaaa\\\xC2\x8D\"", getLLVMStyleWithColumns(10)));
 }
 
 TEST_F(FormatTest, HandlesDoubleWidthCharsInMultiLineStrings) {

                    getLLVMStyle()));
   EXPECT_EQ("\"aaaaaaa \"\r\n"
             "\"bbbbbbb\";\r\n",
-            format("\"aaaaaaa bbbbbbb\";\r\n", getLLVMStyleWithColumns(10)));
+            format_unstable("\"aaaaaaa bbbbbbb\";\r\n", getLLVMStyleWithColumns(10)));
   EXPECT_EQ("#define A \\\r\n"
             "  b;      \\\r\n"
             "  c;      \\\r\n"