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.
compareLabels(StringRef A,StringRef B)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
UsingDeclarationclang::format::__anon5475eee00111::UsingDeclaration71 UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
72 : Line(Line), Label(Label) {}
73
operator <clang::format::__anon5475eee00111::UsingDeclaration74 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.
computeUsingDeclarationLabel(const FormatToken * UsingTok)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
endUsingDeclarationBlock(SmallVectorImpl<UsingDeclaration> * UsingDeclarations,const SourceManager & SourceMgr,tooling::Replacements * Fixes)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
UsingDeclarationsSorter(const Environment & Env,const FormatStyle & Style)180 UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
181 const FormatStyle &Style)
182 : TokenAnalyzer(Env, Style) {}
183
analyze(TokenAnnotator & Annotator,SmallVectorImpl<AnnotatedLine * > & AnnotatedLines,FormatTokenLexer & Tokens)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
215