[clang-format] Support sorting using declarations

Summary:
This patch adds UsingDeclarationsSorter, a TokenAnalyzer that sorts consecutive
using declarations.

Reviewers: klimek

Reviewed By: klimek

Subscribers: Typz, djasper, cfe-commits, klimek, mgorny

Differential Revision: https://reviews.llvm.org/D33823

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@305901 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 438 insertions, 0 deletions

diff --git a/include/clang/Format/Format.h b/include/clang/Format/Format.h
index 1891c06eba..3d311a0ba8 100644
--- a/include/clang/Format/Format.h
+++ b/include/clang/Format/Format.h
@@ -1641,6 +1641,16 @@ tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
                                               ArrayRef<tooling::Range> Ranges,
                                               StringRef FileName = "<stdin>");
 
+/// \brief Sort consecutive using declarations in the given \p Ranges in
+/// \p Code.
+///
+/// Returns the ``Replacements`` that sort the using declarations in all
+/// \p Ranges in \p Code.
+tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
+                                            StringRef Code,
+                                            ArrayRef<tooling::Range> Ranges,
+                                            StringRef FileName = "<stdin>");
+
 /// \brief Returns the ``LangOpts`` that the formatter expects you to set.
 ///
 /// \param Style determines specific settings for lexing mode.
diff --git a/lib/Format/CMakeLists.txt b/lib/Format/CMakeLists.txt
index 0c7511c1bb..42e6d53d9f 100644
--- a/lib/Format/CMakeLists.txt
+++ b/lib/Format/CMakeLists.txt
@@ -13,6 +13,7 @@ add_clang_library(clangFormat
   TokenAnnotator.cpp
   UnwrappedLineFormatter.cpp
   UnwrappedLineParser.cpp
+  UsingDeclarationsSorter.cpp
   WhitespaceManager.cpp
 
   LINK_LIBS
diff --git a/lib/Format/Format.cpp b/lib/Format/Format.cpp
index 39da87cf99..aebe22c07e 100644
--- a/lib/Format/Format.cpp
+++ b/lib/Format/Format.cpp
@@ -23,6 +23,7 @@
 #include "TokenAnnotator.h"
 #include "UnwrappedLineFormatter.h"
 #include "UnwrappedLineParser.h"
+#include "UsingDeclarationsSorter.h"
 #include "WhitespaceManager.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
@@ -1943,6 +1944,16 @@ tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
   return Fix.process();
 }
 
+tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
+                                            StringRef Code,
+                                            ArrayRef<tooling::Range> Ranges,
+                                            StringRef FileName) {
+  std::unique_ptr<Environment> Env =
+      Environment::CreateVirtualEnvironment(Code, FileName, Ranges);
+  UsingDeclarationsSorter Sorter(*Env, Style);
+  return Sorter.process();
+}
+
 LangOptions getFormattingLangOpts(const FormatStyle &Style) {
   LangOptions LangOpts;
   LangOpts.CPlusPlus = 1;
diff --git a/lib/Format/UsingDeclarationsSorter.cpp b/lib/Format/UsingDeclarationsSorter.cpp
new file mode 100644
index 0000000000..fb4f59fbc9
--- /dev/null
+++ b/lib/Format/UsingDeclarationsSorter.cpp
@@ -0,0 +1,144 @@
+//===--- UsingDeclarationsSorter.cpp ----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This file implements UsingDeclarationsSorter, a TokenAnalyzer that
+/// sorts consecutive using declarations.
+///
+//===----------------------------------------------------------------------===//
+
+#include "UsingDeclarationsSorter.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Regex.h"
+
+#include <algorithm>
+
+#define DEBUG_TYPE "using-declarations-sorter"
+
+namespace clang {
+namespace format {
+
+namespace {
+
+struct UsingDeclaration {
+  const AnnotatedLine *Line;
+  std::string Label;
+
+  UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
+      : Line(Line), Label(Label) {}
+
+  bool operator<(const UsingDeclaration &Other) const {
+    return Label < Other.Label;
+  }
+};
+
+/// 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;
+/// and not type aliases, as in:
+/// using A = B::C;
+/// Type aliases are in general not safe to permute.
+std::string computeUsingDeclarationLabel(const FormatToken *UsingTok) {
+  assert(UsingTok && UsingTok->is(tok::kw_using) && "Expecting a using token");
+  std::string Label;
+  const FormatToken *Tok = UsingTok->Next;
+  if (Tok && Tok->is(tok::kw_typename)) {
+    Label.append("typename ");
+    Tok = Tok->Next;
+  }
+  if (Tok && Tok->is(tok::coloncolon)) {
+    Label.append("::");
+    Tok = Tok->Next;
+  }
+  bool HasIdentifier = false;
+  while (Tok && Tok->is(tok::identifier)) {
+    HasIdentifier = true;
+    Label.append(Tok->TokenText.str());
+    Tok = Tok->Next;
+    if (!Tok || Tok->isNot(tok::coloncolon))
+      break;
+    Label.append("::");
+    Tok = Tok->Next;
+  }
+  if (HasIdentifier && Tok && Tok->isOneOf(tok::semi, tok::comma))
+    return Label;
+  return "";
+}
+
+void endUsingDeclarationBlock(
+    SmallVectorImpl<UsingDeclaration> *UsingDeclarations,
+    const SourceManager &SourceMgr, tooling::Replacements *Fixes) {
+  SmallVector<UsingDeclaration, 4> SortedUsingDeclarations(
+      UsingDeclarations->begin(), UsingDeclarations->end());
+  std::sort(SortedUsingDeclarations.begin(), SortedUsingDeclarations.end());
+  for (size_t I = 0, E = UsingDeclarations->size(); I < E; ++I) {
+    if ((*UsingDeclarations)[I].Line == SortedUsingDeclarations[I].Line)
+      continue;
+    auto Begin = (*UsingDeclarations)[I].Line->First->Tok.getLocation();
+    auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
+    auto SortedBegin =
+        SortedUsingDeclarations[I].Line->First->Tok.getLocation();
+    auto SortedEnd = SortedUsingDeclarations[I].Line->Last->Tok.getEndLoc();
+    StringRef Text(SourceMgr.getCharacterData(SortedBegin),
+                   SourceMgr.getCharacterData(SortedEnd) -
+                       SourceMgr.getCharacterData(SortedBegin));
+    DEBUG({
+      StringRef OldText(SourceMgr.getCharacterData(Begin),
+                        SourceMgr.getCharacterData(End) -
+                            SourceMgr.getCharacterData(Begin));
+      llvm::dbgs() << "Replacing '" << OldText << "' with '" << Text << "'\n";
+    });
+    auto Range = CharSourceRange::getCharRange(Begin, End);
+    auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, Text));
+    if (Err) {
+      llvm::errs() << "Error while sorting using declarations: "
+                   << llvm::toString(std::move(Err)) << "\n";
+    }
+  }
+  UsingDeclarations->clear();
+}
+
+} // namespace
+
+UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
+                                                 const FormatStyle &Style)
+    : TokenAnalyzer(Env, Style) {}
+
+tooling::Replacements UsingDeclarationsSorter::analyze(
+    TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
+    FormatTokenLexer &Tokens) {
+  const SourceManager &SourceMgr = Env.getSourceManager();
+  AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
+                                        AnnotatedLines.end());
+  tooling::Replacements Fixes;
+  SmallVector<UsingDeclaration, 4> UsingDeclarations;
+  for (size_t I = 0, E = AnnotatedLines.size(); I != E; ++I) {
+    if (!AnnotatedLines[I]->Affected || AnnotatedLines[I]->InPPDirective ||
+        !AnnotatedLines[I]->startsWith(tok::kw_using) ||
+        AnnotatedLines[I]->First->Finalized) {
+      endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
+      continue;
+    }
+    if (AnnotatedLines[I]->First->NewlinesBefore > 1)
+      endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
+    std::string Label = computeUsingDeclarationLabel(AnnotatedLines[I]->First);
+    if (Label.empty()) {
+      endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
+      continue;
+    }
+    UsingDeclarations.push_back(UsingDeclaration(AnnotatedLines[I], Label));
+  }
+  endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
+  return Fixes;
+}
+
+} // namespace format
+} // namespace clang
diff --git a/lib/Format/UsingDeclarationsSorter.h b/lib/Format/UsingDeclarationsSorter.h
new file mode 100644
index 0000000000..f7d5f97e3a
--- /dev/null
+++ b/lib/Format/UsingDeclarationsSorter.h
@@ -0,0 +1,37 @@
+//===--- UsingDeclarationsSorter.h ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This file declares UsingDeclarationsSorter, a TokenAnalyzer that
+/// sorts consecutive using declarations.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIB_FORMAT_USINGDECLARATIONSSORTER_H
+#define LLVM_CLANG_LIB_FORMAT_USINGDECLARATIONSSORTER_H
+
+#include "TokenAnalyzer.h"
+
+namespace clang {
+namespace format {
+
+class UsingDeclarationsSorter : public TokenAnalyzer {
+public:
+  UsingDeclarationsSorter(const Environment &Env, const FormatStyle &Style);
+
+  tooling::Replacements
+  analyze(TokenAnnotator &Annotator,
+          SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
+          FormatTokenLexer &Tokens) override;
+};
+
+} // end namespace format
+} // end namespace clang
+
+#endif
diff --git a/unittests/Format/CMakeLists.txt b/unittests/Format/CMakeLists.txt
index 507d643ba1..5c04ba1143 100644
--- a/unittests/Format/CMakeLists.txt
+++ b/unittests/Format/CMakeLists.txt
@@ -14,6 +14,7 @@ add_clang_unittest(FormatTests
   NamespaceEndCommentsFixerTest.cpp
   SortImportsTestJS.cpp
   SortIncludesTest.cpp
+  UsingDeclarationsSorterTest.cpp
   )
 
 target_link_libraries(FormatTests
diff --git a/unittests/Format/UsingDeclarationsSorterTest.cpp b/unittests/Format/UsingDeclarationsSorterTest.cpp
new file mode 100644
index 0000000000..858a62c2d7
--- /dev/null
+++ b/unittests/Format/UsingDeclarationsSorterTest.cpp
@@ -0,0 +1,234 @@
+//===- UsingDeclarationsSorterTest.cpp - Formatting unit tests ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Format/Format.h"
+
+#include "llvm/Support/Debug.h"
+#include "gtest/gtest.h"
+
+#define DEBUG_TYPE "using-declarations-sorter-test"
+
+namespace clang {
+namespace format {
+namespace {
+
+class UsingDeclarationsSorterTest : public ::testing::Test {
+protected:
+  std::string sortUsingDeclarations(llvm::StringRef Code,
+                                    const std::vector<tooling::Range> &Ranges,
+                                    const FormatStyle &Style = getLLVMStyle()) {
+    DEBUG(llvm::errs() << "---\n");
+    DEBUG(llvm::errs() << Code << "\n\n");
+    tooling::Replacements Replaces =
+        clang::format::sortUsingDeclarations(Style, Code, Ranges, "<stdin>");
+    auto Result = applyAllReplacements(Code, Replaces);
+    EXPECT_TRUE(static_cast<bool>(Result));
+    DEBUG(llvm::errs() << "\n" << *Result << "\n\n");
+    return *Result;
+  }
+
+  std::string sortUsingDeclarations(llvm::StringRef Code,
+                                    const FormatStyle &Style = getLLVMStyle()) {
+    return sortUsingDeclarations(Code,
+                                 /*Ranges=*/{1, tooling::Range(0, Code.size())},
+                                 Style);
+  }
+};
+
+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;",
+            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 a;\n"
+            "using a::a;",
+            sortUsingDeclarations("using a::a;\n"
+                                  "using a;"));
+
+  EXPECT_EQ("using a::ba::aa;\n"
+            "using a::bb::ccc;",
+            sortUsingDeclarations("using a::bb::ccc;\n"
+                                  "using a::ba::aa;"));
+
+  EXPECT_EQ("using a;\n"
+            "using typename a;",
+            sortUsingDeclarations("using typename a;\n"
+                                  "using a;"));
+
+  EXPECT_EQ("using typename z;\n"
+            "using typenamea;",
+            sortUsingDeclarations("using typenamea;\n"
+                                  "using typename z;"));
+
+  EXPECT_EQ("using a, b;\n"
+            "using aa;",
+            sortUsingDeclarations("using aa;\n"
+                                  "using a, b;"));
+}
+
+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"
+            "int main();",
+            sortUsingDeclarations("#include <iostream>\n"
+                                  "using std::cout;\n"
+                                  "using std::cin;\n"
+                                  "using ::std::endl;\n"
+                                  "int main();"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, BreaksOnEmptyLines) {
+  EXPECT_EQ("using b;\n"
+            "using c;\n"
+            "\n"
+            "using a;\n"
+            "using d;",
+            sortUsingDeclarations("using c;\n"
+                                  "using b;\n"
+                                  "\n"
+                                  "using d;\n"
+                                  "using a;"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, BreaksOnUsingNamespace) {
+  EXPECT_EQ("using b;\n"
+            "using namespace std;\n"
+            "using a;",
+            sortUsingDeclarations("using b;\n"
+                                  "using namespace std;\n"
+                                  "using a;"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, KeepsUsingDeclarationsInPPDirectives) {
+  EXPECT_EQ("#define A \\\n"
+            "using b;\\\n"
+            "using a;",
+            sortUsingDeclarations("#define A \\\n"
+                                  "using b;\\\n"
+                                  "using a;"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, KeepsTypeAliases) {
+  auto Code = "struct C { struct B { struct A; }; };\n"
+              "using B = C::B;\n"
+              "using A = B::A;";
+  EXPECT_EQ(Code, sortUsingDeclarations(Code));
+}
+
+TEST_F(UsingDeclarationsSorterTest, MovesTrailingCommentsWithDeclarations) {
+  EXPECT_EQ("using a; // line a1\n"
+            "using b; /* line b1\n"
+            "          * line b2\n"
+            "          * line b3 */\n"
+            "using c; // line c1\n"
+            "         // line c2",
+            sortUsingDeclarations("using c; // line c1\n"
+                                  "         // line c2\n"
+                                  "using b; /* line b1\n"
+                                  "          * line b2\n"
+                                  "          * line b3 */\n"
+                                  "using a; // line a1"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, SortsInStructScope) {
+  EXPECT_EQ("struct pt3 : pt2 {\n"
+            "  using pt2::x;\n"
+            "  using pt2::y;\n"
+            "  float z;\n"
+            "};",
+            sortUsingDeclarations("struct pt3 : pt2 {\n"
+                                  "  using pt2::y;\n"
+                                  "  using pt2::x;\n"
+                                  "  float z;\n"
+                                  "};"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, KeepsOperators) {
+  EXPECT_EQ("using a::operator();\n"
+            "using a::operator-;\n"
+            "using a::operator+;",
+            sortUsingDeclarations("using a::operator();\n"
+                                  "using a::operator-;\n"
+                                  "using a::operator+;"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, SortsUsingDeclarationsInsideNamespaces) {
+  EXPECT_EQ("namespace A {\n"
+            "struct B;\n"
+            "struct C;\n"
+            "}\n"
+            "namespace X {\n"
+            "using A::B;\n"
+            "using A::C;\n"
+            "}",
+            sortUsingDeclarations("namespace A {\n"
+                                  "struct B;\n"
+                                  "struct C;\n"
+                                  "}\n"
+                                  "namespace X {\n"
+                                  "using A::C;\n"
+                                  "using A::B;\n"
+                                  "}"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, SupportsClangFormatOff) {
+  EXPECT_EQ("// clang-format off\n"
+            "using b;\n"
+            "using a;\n"
+            "// clang-format on\n"
+            "using c;\n"
+            "using d;",
+            sortUsingDeclarations("// clang-format off\n"
+                                  "using b;\n"
+                                  "using a;\n"
+                                  "// clang-format on\n"
+                                  "using d;\n"
+                                  "using c;"));
+}
+
+TEST_F(UsingDeclarationsSorterTest, SortsPartialRangeOfUsingDeclarations) {
+  EXPECT_EQ("using b;\n"
+            "using a;\n"
+            "using c;",
+            sortUsingDeclarations("using b;\n"
+                                  "using c;\n" // starts at offset 10
+                                  "using a;",
+                                  {tooling::Range(10, 15)}));
+}
+
+} // end namespace
+} // end namespace format
+} // end namespace clang