[clang-format] Sort using-declarations case sensitively with a special case for '_'

[krasimir]

Summary

This makes clang-format sort using declarations case-sensitive with the
exception that '_' comes just before 'A'. This is better than the current case
insensitive version, because it groups uppercase names in the same namespace
together.

[bkramer]

Can we just write out the modified string comparison function instead of keeping both versions of the string around in memory? I'd prefer less state.

[krasimir]

• Remove SortLabel

[krasimir]

How about this trade-off? I don't really want to re-implement comparison (it makes the code harder to read), so I replaced the state with an explicit computation.

[krasimir]

• Address review comment

[bkramer]

lg, thanks!

lib/Format/UsingDeclarationsSorter.cpp

 namespace clang {
 namespace format {
 
 namespace {
 
 struct UsingDeclaration {
   const AnnotatedLine *Line;
   std::string Label;
+  std::string SortLabel;
 
   UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
-      : Line(Line), Label(Label) {}
+      : Line(Line), Label(Label), SortLabel(computeSortLabel(Label)) {}
 
+  // Compares lexicographically with the exception that '_' is just before 'A'.
   bool operator<(const UsingDeclaration &Other) const {
-    return StringRef(Label).compare_lower(Other.Label) < 0;
+    return StringRef(SortLabel).compare(Other.SortLabel) < 0;
+  }
+
+  // Returns the position of c in a lexicographic ordering with the exception
+  // that '_' is just before 'A'.
+  static char rank(char c) {
+    if (c == '_')
+      return 'A';
+    if ('A' <= c && c < '_')
+      return c + 1;
+    return c;
+  }
+
+  static std::string computeSortLabel(const std::string &Label) {
+    std::string SortLabel;
+    SortLabel.reserve(Label.size());
+    for (char C : Label)
+      SortLabel += rank(C);
+    return SortLabel;
   }
 };
 
 /// Computes the label of a using declaration starting at tthe using token
 /// \p UsingTok.
 /// If \p UsingTok doesn't begin a using declaration, returns the empty string.
 /// Note that this detects specifically using declarations, as in:
 /// using A::B::C;
if (HasIdentifier && Tok && Tok->isOneOf(tok::semi, tok::comma))
     return Label;
   return "";
 }
 
 void endUsingDeclarationBlock(
     SmallVectorImpl<UsingDeclaration> *UsingDeclarations,
     const SourceManager &SourceMgr, tooling::Replacements *Fixes) {
   bool BlockAffected = false;
-  for (const UsingDeclaration& Declaration : *UsingDeclarations) {
+  for (const UsingDeclaration &Declaration : *UsingDeclarations) {
     if (Declaration.Line->Affected) {
       BlockAffected = true;
       break;
     }
   }
   if (!BlockAffected) {
     UsingDeclarations->clear();
     return;

unittests/Format/UsingDeclarationsSorterTest.cpp

EXPECT_EQ("using typename z;\n"
                                   "using typename z;"));
 
   EXPECT_EQ("using a, b;\n"
             "using aa;",
             sortUsingDeclarations("using aa;\n"
                                   "using a, b;"));
 }
 
-TEST_F(UsingDeclarationsSorterTest, SortsCaseInsensitively) {
+TEST_F(UsingDeclarationsSorterTest, SortsCaseSensitively) {
   EXPECT_EQ("using A;\n"
             "using a;",
             sortUsingDeclarations("using A;\n"
                                   "using a;"));
-  EXPECT_EQ("using a;\n"
-            "using A;",
+  EXPECT_EQ("using A;\n"
+            "using a;",
             sortUsingDeclarations("using a;\n"
                                   "using A;"));
-  EXPECT_EQ("using a;\n"
-            "using B;",
+  EXPECT_EQ("using B;\n"
+            "using a;",
             sortUsingDeclarations("using B;\n"
                                   "using a;"));
+
+  // Sorts '_' right before 'A'.
+  EXPECT_EQ("using _;\n"
+            "using A;",
+            sortUsingDeclarations("using A;\n"
+                                  "using _;"));
   EXPECT_EQ("using _;\n"
             "using a;",
             sortUsingDeclarations("using a;\n"
                                   "using _;"));
   EXPECT_EQ("using a::_;\n"
             "using a::a;",
             sortUsingDeclarations("using a::a;\n"
                                   "using a::_;"));
 
   EXPECT_EQ("using ::testing::_;\n"
             "using ::testing::Aardvark;\n"
-            "using ::testing::apple::Honeycrisp;\n"
             "using ::testing::Xylophone;\n"
+            "using ::testing::apple::Honeycrisp;\n"
             "using ::testing::zebra::Stripes;",
             sortUsingDeclarations("using ::testing::Aardvark;\n"
                                   "using ::testing::Xylophone;\n"
                                   "using ::testing::_;\n"
                                   "using ::testing::apple::Honeycrisp;\n"
                                   "using ::testing::zebra::Stripes;"));
 }
 
-TEST_F(UsingDeclarationsSorterTest, SortsStably) {
-  EXPECT_EQ("using a;\n"
-            "using a;\n"
-            "using A;\n"
-            "using a;\n"
-            "using A;\n"
-            "using a;\n"
-            "using A;\n"
-            "using a;\n"
-            "using B;\n"
-            "using b;\n"
-            "using b;\n"
-            "using B;\n"
-            "using b;\n"
-            "using b;\n"
-            "using b;\n"
-            "using B;\n"
-            "using b;",
-            sortUsingDeclarations("using a;\n"
-                                  "using B;\n"
-                                  "using a;\n"
-                                  "using b;\n"
-                                  "using A;\n"
-                                  "using a;\n"
-                                  "using b;\n"
-                                  "using B;\n"
-                                  "using b;\n"
-                                  "using A;\n"
-                                  "using a;\n"
-                                  "using b;\n"
-                                  "using b;\n"
-                                  "using B;\n"
-                                  "using b;\n"
-                                  "using A;\n"
-                                  "using a;"));
-}
-
 TEST_F(UsingDeclarationsSorterTest, SortsMultipleTopLevelDeclarations) {
   EXPECT_EQ("using a;\n"
             "using b;\n"
             "using c;\n"
             "using d;\n"
             "using e;",
             sortUsingDeclarations("using d;\n"
                                   "using b;\n"