[clang-format] Sort using declarations by splitting on '::'

[krasimir]

Summary

This patch improves using declarations sorting.

[krasimir]

• Remove dead code

[bkramer]

lg

docs/ClangFormatStyleOptions.rst

.. code-block:: c++
     int aaa = bbbbbbbbbbbbbbb +
               ccccccccccccccc;
 
 **AlignTrailingComments** (``bool``)
   If ``true``, aligns trailing comments.
 
   .. code-block:: c++
 
-    true:
-    int a;     // My comment a
-    int b = 2; // comment  b
-
-    false:
-    int a; // My comment a
-    int b = 2; // comment about b
+    true:                                   false:
+    int a;     // My comment a      vs.     int a; // My comment a
+    int b = 2; // comment  b                int b = 2; // comment about b
 
 **AllowAllParametersOfDeclarationOnNextLine** (``bool``)
   If the function declaration doesn't fit on a line,
   allow putting all parameters of a function declaration onto
   the next line even if ``BinPackParameters`` is ``false``.
 
   .. code-block:: c++
 
* ``PAS_Middle`` (in configuration: ``Middle``)
     Align pointer in the middle.
 
     .. code-block:: c++
 
       int * a;
 
 
 
+**RawStringFormats** (``std::vector<RawStringFormat>``)
+  Raw string delimiters denoting that the raw string contents are
+  code in a particular language and can be reformatted.
+
+  A raw string with a matching delimiter will be reformatted assuming the
+  specified language based on a predefined style given by 'BasedOnStyle'.
+  If 'BasedOnStyle' is not found, the formatting is based on llvm style.
+
+  To configure this in the .clang-format file, use:
+
+  .. code-block:: yaml
+
+    RawStringFormats:
+      - Delimiter: 'pb'
+        Language:  TextProto
+        BasedOnStyle: llvm
+      - Delimiter: 'proto'
+        Language:  TextProto
+        BasedOnStyle: google
+
 **ReflowComments** (``bool``)
   If ``true``, clang-format will attempt to re-flow comments.
 
   .. code-block:: c++
 
      false:
      // veryVeryVeryVeryVeryVeryVeryVeryVeryVeryVeryLongComment with plenty of information
      /* second veryVeryVeryVeryVeryVeryVeryVeryVeryVeryVeryLongComment with plenty of information */

 **SortUsingDeclarations** (``bool``)
   If ``true``, clang-format will sort using declarations.
 
   .. code-block:: c++
 
      false:                                 true:
      using std::cout;               vs.     using std::cin;
      using std::cin;                        using std::cout;
+  The order of using declarations is defined as follows:
+  Split the strings by "::" and discard any initial empty strings. The last
+  element of each list is a non-namespace name; all others are namespace
+  names. Sort the lists of names lexicographically, where the sort order of
+  individual names is that all non-namespace names come before all namespace
+  names, and within those groups, names are in case-insensitive
+  lexicographic order.
 
 **SpaceAfterCStyleCast** (``bool``)
   If ``true``, a space is inserted after C style casts.
 
   .. code-block:: c++
 
      true:                                  false:
      (int)i;                        vs.     (int) i;

docs/tools/dump_format_style.py

elif state == State.InEnumMemberComment:
         state = State.InEnum
         enum.values.append(EnumValue(line.replace(',', ''), comment))
   if state != State.Finished:
     raise Exception('Not finished by the end of file')
 
   for option in options:
     if not option.type in ['bool', 'unsigned', 'int', 'std::string',
                            'std::vector<std::string>',
-                           'std::vector<IncludeCategory>']:
+                           'std::vector<IncludeCategory>',
+                           'std::vector<RawStringFormat>']:
       if enums.has_key(option.type):
         option.enum = enums[option.type]
       elif nested_structs.has_key(option.type):
         option.nested_struct = nested_structs[option.type]
       else:
         raise Exception('Unknown type: %s' % option.type)
   return options
 

include/clang/Format/Format.h

   bool SortIncludes;
 
   /// \brief If ``true``, clang-format will sort using declarations.
   /// \code
   ///    false:                                 true:
   ///    using std::cout;               vs.     using std::cin;
   ///    using std::cin;                        using std::cout;
   /// \endcode
+  /// The order of using declarations is defined as follows:
+  /// Split the strings by "::" and discard any initial empty strings. The last
+  /// element of each list is a non-namespace name; all others are namespace
+  /// names. Sort the lists of names lexicographically, where the sort order of
+  /// individual names is that all non-namespace names come before all namespace
+  /// names, and within those groups, names are in case-insensitive
+  /// lexicographic order.
   bool SortUsingDeclarations;
 
   /// \brief If ``true``, a space is inserted after C style casts.
   /// \code
   ///    true:                                  false:
   ///    (int)i;                        vs.     (int) i;
   /// \endcode
   bool SpaceAfterCStyleCast;

lib/Format/UsingDeclarationsSorter.cpp

 
 #define DEBUG_TYPE "using-declarations-sorter"
 
 namespace clang {
 namespace format {
 
 namespace {
 
+// The order of using declaration is defined as follows:
+// Split the strings by "::" and discard any initial empty strings. The last
+// element of each list is a non-namespace name; all others are namespace
+// names. Sort the lists of names lexicographically, where the sort order of
+// individual names is that all non-namespace names come before all namespace
+// names, and within those groups, names are in case-insensitive lexicographic
+// order.
+int compareLabels(StringRef A, StringRef B) {
+  SmallVector<StringRef, 2> NamesA;
+  A.split(NamesA, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
+  SmallVector<StringRef, 2> NamesB;
+  B.split(NamesB, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
+  size_t SizeA = NamesA.size();
+  size_t SizeB = NamesB.size();
+  for (size_t I = 0, E = std::min(SizeA, SizeB); I < E; ++I) {
+    if (I + 1 == SizeA) {
+      // I is the last index of NamesA and NamesA[I] is a non-namespace name.
+
+      // Non-namespace names come before all namespace names.
+      if (SizeB > SizeA)
+        return -1;
+
+      // Two names within a group compare case-insensitively.
+      return NamesA[I].compare_lower(NamesB[I]);
+    }
+
+    // I is the last index of NamesB and NamesB[I] is a non-namespace name.
+    // Non-namespace names come before all namespace names.
+    if (I + 1 == SizeB)
+      return 1;
+
+    // Two namespaces names within a group compare case-insensitively.
+    int C = NamesA[I].compare_lower(NamesB[I]);
+    if (C != 0)
+      return C;
+  }
+  return 0;
+}
+
 struct UsingDeclaration {
   const AnnotatedLine *Line;
   std::string Label;
 
   UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
       : Line(Line), Label(Label) {}
 
+  // The order of using declaration is defined as follows:
+  // Split the strings by "::" and discard any initial empty strings. The last
+  // element of each list is a non-namespace name; all others are namespace
+  // names. Sort the lists of names lexicographically, where the sort order of
+  // individual names is that all non-namespace names come before all namespace
+  // names, and within those groups, names are in case-insensitive lexicographic
+  // order.
+
   // Compares lexicographically with the exception that '_' is just before 'A'.
   bool operator<(const UsingDeclaration &Other) const {
-    size_t Size = Label.size();
-    size_t OtherSize = Other.Label.size();
-    for (size_t I = 0, E = std::min(Size, OtherSize); I < E; ++I) {
-      char Rank = rank(Label[I]);
-      char OtherRank = rank(Other.Label[I]);
-      if (Rank != OtherRank)
-        return Rank < OtherRank;
-    }
-    return Size < OtherSize;
+    return compareLabels(Label, Other.Label) < 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 < '_')

unittests/Format/UsingDeclarationsSorterTest.cpp

TEST_F(UsingDeclarationsSorterTest, SwapsTwoConsecutiveUsingDeclarations) {
   EXPECT_EQ("using a;\n"
             "using b;",
             sortUsingDeclarations("using a;\n"
                                   "using b;"));
   EXPECT_EQ("using a;\n"
             "using aa;",
             sortUsingDeclarations("using aa;\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::bcd;\n"
             "using a::cd;",
             sortUsingDeclarations("using a::cd;\n"
                                   "using a::bcd;"));
 
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, SortsCaseSensitively) {
+TEST_F(UsingDeclarationsSorterTest, UsingDeclarationOrder) {
   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 B;\n"
-            "using a;",
+  EXPECT_EQ("using a;\n"
+            "using B;",
             sortUsingDeclarations("using B;\n"
                                   "using a;"));
 
-  // Sorts '_' right before 'A'.
+  // Ignores leading '::'.
+  EXPECT_EQ("using ::a;\n"
+            "using A;",
+            sortUsingDeclarations("using ::a;\n"
+                                  "using A;"));
+
+  EXPECT_EQ("using ::A;\n"
+            "using a;",
+            sortUsingDeclarations("using ::A;\n"
+                                  "using a;"));
+
+  // Sorts '_' before 'a' and '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::_;"));
 
+  // Sorts non-namespace names before namespace names at the same level.
   EXPECT_EQ("using ::testing::_;\n"
             "using ::testing::Aardvark;\n"
+            "using ::testing::kMax;\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::kMax;\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"
                                   "using e;\n"
                                   "using a;\n"
                                   "using c;"));
 
   EXPECT_EQ("#include <iostream>\n"
-            "using ::std::endl;\n"
             "using std::cin;\n"
             "using std::cout;\n"
+            "using ::std::endl;\n"
             "int main();",
             sortUsingDeclarations("#include <iostream>\n"
                                   "using std::cout;\n"
-                                  "using std::cin;\n"
                                   "using ::std::endl;\n"
+                                  "using std::cin;\n"
                                   "int main();"));
 }
 
 TEST_F(UsingDeclarationsSorterTest, BreaksOnEmptyLines) {
   EXPECT_EQ("using b;\n"
             "using c;\n"
             "\n"
             "using a;\n"