| 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 |