[clang-format] Ensure Sort include is stable with negative Priority

[jeanphilippeD]

Summary

The new sort include with negative priority was not stable when running it again over the updated includes.

Extend the test NegativePriorities to have an extra header. Test pas still passing
Add a new assertion to test that the sorting is stable. This new assertion failed.

From this:
#include "important_os_header.h"
#include "c_main_header.h"
#include "a_other_header.h"

Before fix:
#include "important_os_header.h"
#include "a_other_header.h"
#include "c_main_header.h"

After fix:
#include "important_os_header.h"
#include "c_main_header.h"
#include "a_other_header.h"

[jeanphilippeD]

This was fixed by other patch.

lib/Format/Format.cpp

for (;;) {
     if (Trimmed == "// clang-format off")
       FormattingOff = true;
     else if (Trimmed == "// clang-format on")
       FormattingOff = false;
 
     if (!FormattingOff && !Line.endswith("\\")) {
       if (IncludeRegex.match(Line, &Matches)) {
         StringRef IncludeName = Matches[2];
-        int Category;
-        if (LookForMainHeader && !IncludeName.startswith("<")) {
-          Category = 0;
-        } else {
-          Category = INT_MAX;
-          for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) {
+        int Category = INT_MAX;
             if (CategoryRegexs[i].match(IncludeName)) {
                 Category = Style.IncludeCategories[i].Priority;
                 break;
             }
-          }
+
+        if (Category >= 0 ) {
+            if (LookForMainHeader && !IncludeName.startswith("<")) {
+                Category = 0;
             }
             LookForMainHeader = false;
+        }
+
         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
       } else if (!IncludesInBlock.empty()) {
         sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
                      Cursor);
         IncludesInBlock.clear();
       }
       Prev = Pos + 1;
     }

unittests/Format/SortIncludesTest.cpp

EXPECT_EQ("#include \"b.h\"\n"
                  "#include \"c.h\"\n"
                  "#include \"b.h\"\n",
                  "some_header.h"));
 }
 
 TEST_F(SortIncludesTest, NegativePriorities) {
   Style.IncludeCategories = {{".*important_os_header.*", -1}, {".*", 1}};
   EXPECT_EQ("#include \"important_os_header.h\"\n"
-            "#include \"a.h\"\n",
-            sort("#include \"a.h\"\n"
+            "#include \"c_main_header.h\"\n"
+            "#include \"a_other_header.h\"\n",
+            sort("#include \"c_main_header.h\"\n"
+                 "#include \"a_other_header.h\"\n"
                  "#include \"important_os_header.h\"\n"));
+
+  // check stable when re-run
+  EXPECT_EQ("#include \"important_os_header.h\"\n"
+            "#include \"c_main_header.h\"\n"
+            "#include \"a_other_header.h\"\n",
+            sort("#include \"important_os_header.h\"\n"
+                 "#include \"c_main_header.h\"\n"
+                 "#include \"a_other_header.h\"\n"));
 }
 
 TEST_F(SortIncludesTest, CalculatesCorrectCursorPosition) {
   std::string Code = "#include <ccc>\n"    // Start of line: 0
                      "#include <bbbbbb>\n" // Start of line: 15
                      "#include <a>\n";     // Start of line: 33
   EXPECT_EQ(31u, newCursor(Code, 0));
   EXPECT_EQ(13u, newCursor(Code, 15));