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