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(A&: NamesA, Separator: "::" , /*MaxSplit=*/-1, /*KeepEmpty=*/false); |
39 | SmallVector<StringRef, 2> NamesB; |
40 | B.split(A&: NamesB, Separator: "::" , /*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(a: SizeA, b: 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(RHS: 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(RHS: 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(A&: NamesA, Separator: "::" , /*MaxSplit=*/-1, /*KeepEmpty=*/false); |
71 | SmallVector<StringRef, 2> NamesB; |
72 | B.split(A&: NamesB, Separator: "::" , /*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(a: SizeA, b: SizeB); I < E; ++I) { |
76 | // Two namespaces names within a group compare case-insensitively. |
77 | int C = NamesA[I].compare_insensitive(RHS: 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(Kind: tok::kw_typename)) { |
115 | Label.append(s: "typename " ); |
116 | Tok = Tok->Next; |
117 | } |
118 | if (Tok && Tok->is(Kind: tok::coloncolon)) { |
119 | Label.append(s: "::" ); |
120 | Tok = Tok->Next; |
121 | } |
122 | bool HasIdentifier = false; |
123 | while (Tok && Tok->is(Kind: tok::identifier)) { |
124 | HasIdentifier = true; |
125 | Label.append(str: Tok->TokenText.str()); |
126 | Tok = Tok->Next; |
127 | if (!Tok || Tok->isNot(Kind: tok::coloncolon)) |
128 | break; |
129 | Label.append(s: "::" ); |
130 | Tok = Tok->Next; |
131 | } |
132 | if (HasIdentifier && Tok && Tok->isOneOf(K1: tok::semi, K2: 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(A: Lhs.Label, B: Rhs.Label, SortUsingDeclarations) < 0; |
157 | }; |
158 | llvm::stable_sort(Range&: SortedUsingDeclarations, C: Comp); |
159 | SortedUsingDeclarations.erase( |
160 | CS: llvm::unique(R&: SortedUsingDeclarations, |
161 | P: [](const UsingDeclaration &a, const UsingDeclaration &b) { |
162 | return a.Label == b.Label; |
163 | }), |
164 | CE: 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(B: Begin, E: End); |
172 | auto Err = Fixes->add(R: tooling::Replacement(SourceMgr, Range, "" )); |
173 | if (Err) { |
174 | llvm::errs() << "Error while sorting using declarations: " |
175 | << llvm::toString(E: 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(SL: SortedBegin), |
187 | SourceMgr.getCharacterData(SL: SortedEnd) - |
188 | SourceMgr.getCharacterData(SL: 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(B: Begin, E: End); |
196 | auto Err = Fixes->add(R: tooling::Replacement(SourceMgr, Range, Text)); |
197 | if (Err) { |
198 | llvm::errs() << "Error while sorting using declarations: " |
199 | << llvm::toString(E: std::move(Err)) << "\n" ; |
200 | } |
201 | } |
202 | UsingDeclarations->clear(); |
203 | } |
204 | |
205 | } // namespace |
206 | |
207 | UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env, |
208 | const FormatStyle &Style) |
209 | : TokenAnalyzer(Env, Style) {} |
210 | |
211 | std::pair<tooling::Replacements, unsigned> UsingDeclarationsSorter::analyze( |
212 | TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines, |
213 | FormatTokenLexer &Tokens) { |
214 | const SourceManager &SourceMgr = Env.getSourceManager(); |
215 | AffectedRangeMgr.computeAffectedLines(Lines&: 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(Tokens: tok::kw_using) || |
221 | FirstTok->Finalized) { |
222 | endUsingDeclarationBlock(UsingDeclarations: &UsingDeclarations, SourceMgr, Fixes: &Fixes, |
223 | SortUsingDeclarations: Style.SortUsingDeclarations); |
224 | continue; |
225 | } |
226 | if (FirstTok->NewlinesBefore > 1) { |
227 | endUsingDeclarationBlock(UsingDeclarations: &UsingDeclarations, SourceMgr, Fixes: &Fixes, |
228 | SortUsingDeclarations: Style.SortUsingDeclarations); |
229 | } |
230 | const auto *UsingTok = |
231 | FirstTok->is(Kind: tok::comment) ? FirstTok->getNextNonComment() : FirstTok; |
232 | std::string Label = computeUsingDeclarationLabel(UsingTok); |
233 | if (Label.empty()) { |
234 | endUsingDeclarationBlock(UsingDeclarations: &UsingDeclarations, SourceMgr, Fixes: &Fixes, |
235 | SortUsingDeclarations: Style.SortUsingDeclarations); |
236 | continue; |
237 | } |
238 | UsingDeclarations.push_back(Elt: UsingDeclaration(Line, Label)); |
239 | } |
240 | endUsingDeclarationBlock(UsingDeclarations: &UsingDeclarations, SourceMgr, Fixes: &Fixes, |
241 | SortUsingDeclarations: Style.SortUsingDeclarations); |
242 | return {Fixes, 0}; |
243 | } |
244 | |
245 | } // namespace format |
246 | } // namespace clang |
247 | |