contrib/llvm/tools/clang/lib/Format/UsingDeclarationsSorter.cpp

   1 //===--- UsingDeclarationsSorter.cpp ----------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// This file implements UsingDeclarationsSorter, a TokenAnalyzer that
  12 /// sorts consecutive using declarations.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "UsingDeclarationsSorter.h"
  17 #include "llvm/Support/Debug.h"
  18 #include "llvm/Support/Regex.h"
  19
  20 #include <algorithm>
  21
  22 #define DEBUG_TYPE "using-declarations-sorter"
  23
  24 namespace clang {
  25 namespace format {
  26
  27 namespace {
  28
  29 // The order of using declaration is defined as follows:
  30 // Split the strings by "::" and discard any initial empty strings. The last
  31 // element of each list is a non-namespace name; all others are namespace
  32 // names. Sort the lists of names lexicographically, where the sort order of
  33 // individual names is that all non-namespace names come before all namespace
  34 // names, and within those groups, names are in case-insensitive lexicographic
  35 // order.
  36 int compareLabels(StringRef A, StringRef B) {
  37   SmallVector<StringRef, 2> NamesA;
  38   A.split(NamesA, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  39   SmallVector<StringRef, 2> NamesB;
  40   B.split(NamesB, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  41   size_t SizeA = NamesA.size();
  42   size_t SizeB = NamesB.size();
  43   for (size_t I = 0, E = std::min(SizeA, SizeB); I < E; ++I) {
  44     if (I + 1 == SizeA) {
  45       // I is the last index of NamesA and NamesA[I] is a non-namespace name.
  46
  47       // Non-namespace names come before all namespace names.
  48       if (SizeB > SizeA)
  49         return -1;
  50
  51       // Two names within a group compare case-insensitively.
  52       return NamesA[I].compare_lower(NamesB[I]);
  53     }
  54
  55     // I is the last index of NamesB and NamesB[I] is a non-namespace name.
  56     // Non-namespace names come before all namespace names.
  57     if (I + 1 == SizeB)
  58       return 1;
  59
  60     // Two namespaces names within a group compare case-insensitively.
  61     int C = NamesA[I].compare_lower(NamesB[I]);
  62     if (C != 0)
  63       return C;
  64   }
  65   return 0;
  66 }
  67
  68 struct UsingDeclaration {
  69   const AnnotatedLine *Line;
  70   std::string Label;
  71
  72   UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
  73       : Line(Line), Label(Label) {}
  74
  75   bool operator<(const UsingDeclaration &Other) const {
  76     return compareLabels(Label, Other.Label) < 0;
  77   }
  78 };
  79
  80 /// Computes the label of a using declaration starting at tthe using token
  81 /// \p UsingTok.
  82 /// If \p UsingTok doesn't begin a using declaration, returns the empty string.
  83 /// Note that this detects specifically using declarations, as in:
  84 /// using A::B::C;
  85 /// and not type aliases, as in:
  86 /// using A = B::C;
  87 /// Type aliases are in general not safe to permute.
  88 std::string computeUsingDeclarationLabel(const FormatToken *UsingTok) {
  89   assert(UsingTok && UsingTok->is(tok::kw_using) && "Expecting a using token");
  90   std::string Label;
  91   const FormatToken *Tok = UsingTok->Next;
  92   if (Tok && Tok->is(tok::kw_typename)) {
  93     Label.append("typename ");
  94     Tok = Tok->Next;
  95   }
  96   if (Tok && Tok->is(tok::coloncolon)) {
  97     Label.append("::");
  98     Tok = Tok->Next;
  99   }
 100   bool HasIdentifier = false;
 101   while (Tok && Tok->is(tok::identifier)) {
 102     HasIdentifier = true;
 103     Label.append(Tok->TokenText.str());
 104     Tok = Tok->Next;
 105     if (!Tok || Tok->isNot(tok::coloncolon))
 106       break;
 107     Label.append("::");
 108     Tok = Tok->Next;
 109   }
 110   if (HasIdentifier && Tok && Tok->isOneOf(tok::semi, tok::comma))
 111     return Label;
 112   return "";
 113 }
 114
 115 void endUsingDeclarationBlock(
 116     SmallVectorImpl<UsingDeclaration> *UsingDeclarations,
 117     const SourceManager &SourceMgr, tooling::Replacements *Fixes) {
 118   bool BlockAffected = false;
 119   for (const UsingDeclaration &Declaration : *UsingDeclarations) {
 120     if (Declaration.Line->Affected) {
 121       BlockAffected = true;
 122       break;
 123     }
 124   }
 125   if (!BlockAffected) {
 126     UsingDeclarations->clear();
 127     return;
 128   }
 129   SmallVector<UsingDeclaration, 4> SortedUsingDeclarations(
 130       UsingDeclarations->begin(), UsingDeclarations->end());
 131   std::stable_sort(SortedUsingDeclarations.begin(),
 132                    SortedUsingDeclarations.end());
 133   SortedUsingDeclarations.erase(
 134       std::unique(SortedUsingDeclarations.begin(),
 135                   SortedUsingDeclarations.end(),
 136                   [](const UsingDeclaration &a, const UsingDeclaration &b) {
 137                     return a.Label == b.Label;
 138                   }),
 139       SortedUsingDeclarations.end());
 140   for (size_t I = 0, E = UsingDeclarations->size(); I < E; ++I) {
 141     if (I >= SortedUsingDeclarations.size()) {
 142       // This using declaration has been deduplicated, delete it.
 143       auto Begin =
 144           (*UsingDeclarations)[I].Line->First->WhitespaceRange.getBegin();
 145       auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
 146       auto Range = CharSourceRange::getCharRange(Begin, End);
 147       auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, ""));
 148       if (Err) {
 149         llvm::errs() << "Error while sorting using declarations: "
 150                      << llvm::toString(std::move(Err)) << "\n";
 151       }
 152       continue;
 153     }
 154     if ((*UsingDeclarations)[I].Line == SortedUsingDeclarations[I].Line)
 155       continue;
 156     auto Begin = (*UsingDeclarations)[I].Line->First->Tok.getLocation();
 157     auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
 158     auto SortedBegin =
 159         SortedUsingDeclarations[I].Line->First->Tok.getLocation();
 160     auto SortedEnd = SortedUsingDeclarations[I].Line->Last->Tok.getEndLoc();
 161     StringRef Text(SourceMgr.getCharacterData(SortedBegin),
 162                    SourceMgr.getCharacterData(SortedEnd) -
 163                        SourceMgr.getCharacterData(SortedBegin));
 164     LLVM_DEBUG({
 165       StringRef OldText(SourceMgr.getCharacterData(Begin),
 166                         SourceMgr.getCharacterData(End) -
 167                             SourceMgr.getCharacterData(Begin));
 168       llvm::dbgs() << "Replacing '" << OldText << "' with '" << Text << "'\n";
 169     });
 170     auto Range = CharSourceRange::getCharRange(Begin, End);
 171     auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, Text));
 172     if (Err) {
 173       llvm::errs() << "Error while sorting using declarations: "
 174                    << llvm::toString(std::move(Err)) << "\n";
 175     }
 176   }
 177   UsingDeclarations->clear();
 178 }
 179
 180 } // namespace
 181
 182 UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
 183                                                  const FormatStyle &Style)
 184     : TokenAnalyzer(Env, Style) {}
 185
 186 std::pair<tooling::Replacements, unsigned> UsingDeclarationsSorter::analyze(
 187     TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
 188     FormatTokenLexer &Tokens) {
 189   const SourceManager &SourceMgr = Env.getSourceManager();
 190   AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
 191   tooling::Replacements Fixes;
 192   SmallVector<UsingDeclaration, 4> UsingDeclarations;
 193   for (size_t I = 0, E = AnnotatedLines.size(); I != E; ++I) {
 194     const auto *FirstTok = AnnotatedLines[I]->First;
 195     if (AnnotatedLines[I]->InPPDirective ||
 196         !AnnotatedLines[I]->startsWith(tok::kw_using) || FirstTok->Finalized) {
 197       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
 198       continue;
 199     }
 200     if (FirstTok->NewlinesBefore > 1)
 201       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
 202     const auto *UsingTok =
 203         FirstTok->is(tok::comment) ? FirstTok->getNextNonComment() : FirstTok;
 204     std::string Label = computeUsingDeclarationLabel(UsingTok);
 205     if (Label.empty()) {
 206       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
 207       continue;
 208     }
 209     UsingDeclarations.push_back(UsingDeclaration(AnnotatedLines[I], Label));
 210   }
 211   endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
 212   return {Fixes, 0};
 213 }
 214
 215 } // namespace format
 216 } // namespace clang