247 lines · 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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file implements UsingDeclarationsSorter, a TokenAnalyzer that11/// 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 24namespace clang {25namespace format {26 27namespace {28 29// The order of using declaration is defined as follows:30// Split the strings by "::" and discard any initial empty strings. The last31// element of each list is a non-namespace name; all others are namespace32// names. Sort the lists of names lexicographically, where the sort order of33// individual names is that all non-namespace names come before all namespace34// names, and within those groups, names are in case-insensitive lexicographic35// order.36int 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 68int 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 86int 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 94struct 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 token103/// \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.110std::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 137void 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 llvm::unique(SortedUsingDeclarations,161 [](const UsingDeclaration &a, const UsingDeclaration &b) {162 return a.Label == b.Label;163 }),164 SortedUsingDeclarations.end());165 for (size_t I = 0, E = UsingDeclarations->size(); I < E; ++I) {166 if (I >= SortedUsingDeclarations.size()) {167 // This using declaration has been deduplicated, delete it.168 auto Begin =169 (*UsingDeclarations)[I].Line->First->WhitespaceRange.getBegin();170 auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();171 auto Range = CharSourceRange::getCharRange(Begin, End);172 auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, ""));173 if (Err) {174 llvm::errs() << "Error while sorting using declarations: "175 << llvm::toString(std::move(Err)) << "\n";176 }177 continue;178 }179 if ((*UsingDeclarations)[I].Line == SortedUsingDeclarations[I].Line)180 continue;181 auto Begin = (*UsingDeclarations)[I].Line->First->Tok.getLocation();182 auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();183 auto SortedBegin =184 SortedUsingDeclarations[I].Line->First->Tok.getLocation();185 auto SortedEnd = SortedUsingDeclarations[I].Line->Last->Tok.getEndLoc();186 StringRef Text(SourceMgr.getCharacterData(SortedBegin),187 SourceMgr.getCharacterData(SortedEnd) -188 SourceMgr.getCharacterData(SortedBegin));189 LLVM_DEBUG({190 StringRef OldText(SourceMgr.getCharacterData(Begin),191 SourceMgr.getCharacterData(End) -192 SourceMgr.getCharacterData(Begin));193 llvm::dbgs() << "Replacing '" << OldText << "' with '" << Text << "'\n";194 });195 auto Range = CharSourceRange::getCharRange(Begin, End);196 auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, Text));197 if (Err) {198 llvm::errs() << "Error while sorting using declarations: "199 << llvm::toString(std::move(Err)) << "\n";200 }201 }202 UsingDeclarations->clear();203}204 205} // namespace206 207UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,208 const FormatStyle &Style)209 : TokenAnalyzer(Env, Style) {}210 211std::pair<tooling::Replacements, unsigned> UsingDeclarationsSorter::analyze(212 TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,213 FormatTokenLexer &Tokens) {214 const SourceManager &SourceMgr = Env.getSourceManager();215 AffectedRangeMgr.computeAffectedLines(AnnotatedLines);216 tooling::Replacements Fixes;217 SmallVector<UsingDeclaration, 4> UsingDeclarations;218 for (const AnnotatedLine *Line : AnnotatedLines) {219 const auto *FirstTok = Line->First;220 if (Line->InPPDirective || !Line->startsWith(tok::kw_using) ||221 FirstTok->Finalized) {222 endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,223 Style.SortUsingDeclarations);224 continue;225 }226 if (FirstTok->NewlinesBefore > 1) {227 endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,228 Style.SortUsingDeclarations);229 }230 const auto *UsingTok =231 FirstTok->is(tok::comment) ? FirstTok->getNextNonComment() : FirstTok;232 std::string Label = computeUsingDeclarationLabel(UsingTok);233 if (Label.empty()) {234 endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,235 Style.SortUsingDeclarations);236 continue;237 }238 UsingDeclarations.push_back(UsingDeclaration(Line, Label));239 }240 endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,241 Style.SortUsingDeclarations);242 return {Fixes, 0};243}244 245} // namespace format246} // namespace clang247