clang/lib/Format/UsingDeclarationsSorter.cpp

   1 //===--- UsingDeclarationsSorter.cpp ----------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// This file implements UsingDeclarationsSorter, a TokenAnalyzer that
  11 /// sorts consecutive using declarations.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "UsingDeclarationsSorter.h"
  16 #include "clang/Format/Format.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 compareLabelsLexicographicNumeric(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_insensitive(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_insensitive(NamesB[I]);
  62     if (C != 0)
  63       return C;
  64   }
  65   return 0;
  66 }
  67
  68 int compareLabelsLexicographic(StringRef A, StringRef B) {
  69   SmallVector<StringRef, 2> NamesA;
  70   A.split(NamesA, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  71   SmallVector<StringRef, 2> NamesB;
  72   B.split(NamesB, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  73   size_t SizeA = NamesA.size();
  74   size_t SizeB = NamesB.size();
  75   for (size_t I = 0, E = std::min(SizeA, SizeB); I < E; ++I) {
  76     // Two namespaces names within a group compare case-insensitively.
  77     int C = NamesA[I].compare_insensitive(NamesB[I]);
  78     if (C != 0)
  79       return C;
  80   }
  81   if (SizeA < SizeB)
  82     return -1;
  83   return SizeA == SizeB ? 0 : 1;
  84 }
  85
  86 int compareLabels(
  87     StringRef A, StringRef B,
  88     FormatStyle::SortUsingDeclarationsOptions SortUsingDeclarations) {
  89   if (SortUsingDeclarations == FormatStyle::SUD_LexicographicNumeric)
  90     return compareLabelsLexicographicNumeric(A, B);
  91   return compareLabelsLexicographic(A, B);
  92 }
  93
  94 struct UsingDeclaration {
  95   const AnnotatedLine *Line;
  96   std::string Label;
  97
  98   UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
  99       : Line(Line), Label(Label) {}
 100 };
 101
 102 /// Computes the label of a using declaration starting at tthe using token
 103 /// \p UsingTok.
 104 /// If \p UsingTok doesn't begin a using declaration, returns the empty string.
 105 /// Note that this detects specifically using declarations, as in:
 106 /// using A::B::C;
 107 /// and not type aliases, as in:
 108 /// using A = B::C;
 109 /// Type aliases are in general not safe to permute.
 110 std::string computeUsingDeclarationLabel(const FormatToken *UsingTok) {
 111   assert(UsingTok && UsingTok->is(tok::kw_using) && "Expecting a using token");
 112   std::string Label;
 113   const FormatToken *Tok = UsingTok->Next;
 114   if (Tok && Tok->is(tok::kw_typename)) {
 115     Label.append("typename ");
 116     Tok = Tok->Next;
 117   }
 118   if (Tok && Tok->is(tok::coloncolon)) {
 119     Label.append("::");
 120     Tok = Tok->Next;
 121   }
 122   bool HasIdentifier = false;
 123   while (Tok && Tok->is(tok::identifier)) {
 124     HasIdentifier = true;
 125     Label.append(Tok->TokenText.str());
 126     Tok = Tok->Next;
 127     if (!Tok || Tok->isNot(tok::coloncolon))
 128       break;
 129     Label.append("::");
 130     Tok = Tok->Next;
 131   }
 132   if (HasIdentifier && Tok && Tok->isOneOf(tok::semi, tok::comma))
 133     return Label;
 134   return "";
 135 }
 136
 137 void endUsingDeclarationBlock(
 138     SmallVectorImpl<UsingDeclaration> *UsingDeclarations,
 139     const SourceManager &SourceMgr, tooling::Replacements *Fixes,
 140     FormatStyle::SortUsingDeclarationsOptions SortUsingDeclarations) {
 141   bool BlockAffected = false;
 142   for (const UsingDeclaration &Declaration : *UsingDeclarations) {
 143     if (Declaration.Line->Affected) {
 144       BlockAffected = true;
 145       break;
 146     }
 147   }
 148   if (!BlockAffected) {
 149     UsingDeclarations->clear();
 150     return;
 151   }
 152   SmallVector<UsingDeclaration, 4> SortedUsingDeclarations(
 153       UsingDeclarations->begin(), UsingDeclarations->end());
 154   auto Comp = [SortUsingDeclarations](const UsingDeclaration &Lhs,
 155                                       const UsingDeclaration &Rhs) -> bool {
 156     return compareLabels(Lhs.Label, Rhs.Label, SortUsingDeclarations) < 0;
 157   };
 158   llvm::stable_sort(SortedUsingDeclarations, Comp);
 159   SortedUsingDeclarations.erase(
 160       std::unique(SortedUsingDeclarations.begin(),
 161                   SortedUsingDeclarations.end(),
 162                   [](const UsingDeclaration &a, const UsingDeclaration &b) {
 163                     return a.Label == b.Label;
 164                   }),
 165       SortedUsingDeclarations.end());
 166   for (size_t I = 0, E = UsingDeclarations->size(); I < E; ++I) {
 167     if (I >= SortedUsingDeclarations.size()) {
 168       // This using declaration has been deduplicated, delete it.
 169       auto Begin =
 170           (*UsingDeclarations)[I].Line->First->WhitespaceRange.getBegin();
 171       auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
 172       auto Range = CharSourceRange::getCharRange(Begin, End);
 173       auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, ""));
 174       if (Err) {
 175         llvm::errs() << "Error while sorting using declarations: "
 176                      << llvm::toString(std::move(Err)) << "\n";
 177       }
 178       continue;
 179     }
 180     if ((*UsingDeclarations)[I].Line == SortedUsingDeclarations[I].Line)
 181       continue;
 182     auto Begin = (*UsingDeclarations)[I].Line->First->Tok.getLocation();
 183     auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
 184     auto SortedBegin =
 185         SortedUsingDeclarations[I].Line->First->Tok.getLocation();
 186     auto SortedEnd = SortedUsingDeclarations[I].Line->Last->Tok.getEndLoc();
 187     StringRef Text(SourceMgr.getCharacterData(SortedBegin),
 188                    SourceMgr.getCharacterData(SortedEnd) -
 189                        SourceMgr.getCharacterData(SortedBegin));
 190     LLVM_DEBUG({
 191       StringRef OldText(SourceMgr.getCharacterData(Begin),
 192                         SourceMgr.getCharacterData(End) -
 193                             SourceMgr.getCharacterData(Begin));
 194       llvm::dbgs() << "Replacing '" << OldText << "' with '" << Text << "'\n";
 195     });
 196     auto Range = CharSourceRange::getCharRange(Begin, End);
 197     auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, Text));
 198     if (Err) {
 199       llvm::errs() << "Error while sorting using declarations: "
 200                    << llvm::toString(std::move(Err)) << "\n";
 201     }
 202   }
 203   UsingDeclarations->clear();
 204 }
 205
 206 } // namespace
 207
 208 UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
 209                                                  const FormatStyle &Style)
 210     : TokenAnalyzer(Env, Style) {}
 211
 212 std::pair<tooling::Replacements, unsigned> UsingDeclarationsSorter::analyze(
 213     TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
 214     FormatTokenLexer &Tokens) {
 215   const SourceManager &SourceMgr = Env.getSourceManager();
 216   AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
 217   tooling::Replacements Fixes;
 218   SmallVector<UsingDeclaration, 4> UsingDeclarations;
 219   for (const AnnotatedLine *Line : AnnotatedLines) {
 220     const auto *FirstTok = Line->First;
 221     if (Line->InPPDirective || !Line->startsWith(tok::kw_using) ||
 222         FirstTok->Finalized) {
 223       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,
 224                                Style.SortUsingDeclarations);
 225       continue;
 226     }
 227     if (FirstTok->NewlinesBefore > 1) {
 228       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,
 229                                Style.SortUsingDeclarations);
 230     }
 231     const auto *UsingTok =
 232         FirstTok->is(tok::comment) ? FirstTok->getNextNonComment() : FirstTok;
 233     std::string Label = computeUsingDeclarationLabel(UsingTok);
 234     if (Label.empty()) {
 235       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,
 236                                Style.SortUsingDeclarations);
 237       continue;
 238     }
 239     UsingDeclarations.push_back(UsingDeclaration(Line, Label));
 240   }
 241   endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,
 242                            Style.SortUsingDeclarations);
 243   return {Fixes, 0};
 244 }
 245
 246 } // namespace format
 247 } // namespace clang