[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

4 files changed, 193 insertions, 0 deletions

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