1 //===--- UsingDeclarationsSorter.cpp ----------------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// This file implements UsingDeclarationsSorter, a TokenAnalyzer that
12 /// sorts consecutive using declarations.
13 ///
14 //===----------------------------------------------------------------------===//
15
16 #include "UsingDeclarationsSorter.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.
compareLabels(StringRef A,StringRef B)36 int compareLabels(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_lower(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_lower(NamesB[I]);
62 if (C != 0)
63 return C;
64 }
65 return 0;
66 }
67
68 struct UsingDeclaration {
69 const AnnotatedLine *Line;
70 std::string Label;
71
UsingDeclarationclang::format::__anone41c55de0111::UsingDeclaration72 UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
73 : Line(Line), Label(Label) {}
74
operator <clang::format::__anone41c55de0111::UsingDeclaration75 bool operator<(const UsingDeclaration &Other) const {
76 return compareLabels(Label, Other.Label) < 0;
77 }
78 };
79
80 /// Computes the label of a using declaration starting at tthe using token
81 /// \p UsingTok.
82 /// If \p UsingTok doesn't begin a using declaration, returns the empty string.
83 /// Note that this detects specifically using declarations, as in:
84 /// using A::B::C;
85 /// and not type aliases, as in:
86 /// using A = B::C;
87 /// Type aliases are in general not safe to permute.
computeUsingDeclarationLabel(const FormatToken * UsingTok)88 std::string computeUsingDeclarationLabel(const FormatToken *UsingTok) {
89 assert(UsingTok && UsingTok->is(tok::kw_using) && "Expecting a using token");
90 std::string Label;
91 const FormatToken *Tok = UsingTok->Next;
92 if (Tok && Tok->is(tok::kw_typename)) {
93 Label.append("typename ");
94 Tok = Tok->Next;
95 }
96 if (Tok && Tok->is(tok::coloncolon)) {
97 Label.append("::");
98 Tok = Tok->Next;
99 }
100 bool HasIdentifier = false;
101 while (Tok && Tok->is(tok::identifier)) {
102 HasIdentifier = true;
103 Label.append(Tok->TokenText.str());
104 Tok = Tok->Next;
105 if (!Tok || Tok->isNot(tok::coloncolon))
106 break;
107 Label.append("::");
108 Tok = Tok->Next;
109 }
110 if (HasIdentifier && Tok && Tok->isOneOf(tok::semi, tok::comma))
111 return Label;
112 return "";
113 }
114
endUsingDeclarationBlock(SmallVectorImpl<UsingDeclaration> * UsingDeclarations,const SourceManager & SourceMgr,tooling::Replacements * Fixes)115 void endUsingDeclarationBlock(
116 SmallVectorImpl<UsingDeclaration> *UsingDeclarations,
117 const SourceManager &SourceMgr, tooling::Replacements *Fixes) {
118 bool BlockAffected = false;
119 for (const UsingDeclaration &Declaration : *UsingDeclarations) {
120 if (Declaration.Line->Affected) {
121 BlockAffected = true;
122 break;
123 }
124 }
125 if (!BlockAffected) {
126 UsingDeclarations->clear();
127 return;
128 }
129 SmallVector<UsingDeclaration, 4> SortedUsingDeclarations(
130 UsingDeclarations->begin(), UsingDeclarations->end());
131 std::stable_sort(SortedUsingDeclarations.begin(),
132 SortedUsingDeclarations.end());
133 SortedUsingDeclarations.erase(
134 std::unique(SortedUsingDeclarations.begin(),
135 SortedUsingDeclarations.end(),
136 [](const UsingDeclaration &a, const UsingDeclaration &b) {
137 return a.Label == b.Label;
138 }),
139 SortedUsingDeclarations.end());
140 for (size_t I = 0, E = UsingDeclarations->size(); I < E; ++I) {
141 if (I >= SortedUsingDeclarations.size()) {
142 // This using declaration has been deduplicated, delete it.
143 auto Begin =
144 (*UsingDeclarations)[I].Line->First->WhitespaceRange.getBegin();
145 auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
146 auto Range = CharSourceRange::getCharRange(Begin, End);
147 auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, ""));
148 if (Err) {
149 llvm::errs() << "Error while sorting using declarations: "
150 << llvm::toString(std::move(Err)) << "\n";
151 }
152 continue;
153 }
154 if ((*UsingDeclarations)[I].Line == SortedUsingDeclarations[I].Line)
155 continue;
156 auto Begin = (*UsingDeclarations)[I].Line->First->Tok.getLocation();
157 auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
158 auto SortedBegin =
159 SortedUsingDeclarations[I].Line->First->Tok.getLocation();
160 auto SortedEnd = SortedUsingDeclarations[I].Line->Last->Tok.getEndLoc();
161 StringRef Text(SourceMgr.getCharacterData(SortedBegin),
162 SourceMgr.getCharacterData(SortedEnd) -
163 SourceMgr.getCharacterData(SortedBegin));
164 LLVM_DEBUG({
165 StringRef OldText(SourceMgr.getCharacterData(Begin),
166 SourceMgr.getCharacterData(End) -
167 SourceMgr.getCharacterData(Begin));
168 llvm::dbgs() << "Replacing '" << OldText << "' with '" << Text << "'\n";
169 });
170 auto Range = CharSourceRange::getCharRange(Begin, End);
171 auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, Text));
172 if (Err) {
173 llvm::errs() << "Error while sorting using declarations: "
174 << llvm::toString(std::move(Err)) << "\n";
175 }
176 }
177 UsingDeclarations->clear();
178 }
179
180 } // namespace
181
UsingDeclarationsSorter(const Environment & Env,const FormatStyle & Style)182 UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
183 const FormatStyle &Style)
184 : TokenAnalyzer(Env, Style) {}
185
analyze(TokenAnnotator & Annotator,SmallVectorImpl<AnnotatedLine * > & AnnotatedLines,FormatTokenLexer & Tokens)186 std::pair<tooling::Replacements, unsigned> UsingDeclarationsSorter::analyze(
187 TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
188 FormatTokenLexer &Tokens) {
189 const SourceManager &SourceMgr = Env.getSourceManager();
190 AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
191 tooling::Replacements Fixes;
192 SmallVector<UsingDeclaration, 4> UsingDeclarations;
193 for (size_t I = 0, E = AnnotatedLines.size(); I != E; ++I) {
194 const auto *FirstTok = AnnotatedLines[I]->First;
195 if (AnnotatedLines[I]->InPPDirective ||
196 !AnnotatedLines[I]->startsWith(tok::kw_using) || FirstTok->Finalized) {
197 endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
198 continue;
199 }
200 if (FirstTok->NewlinesBefore > 1)
201 endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
202 const auto *UsingTok =
203 FirstTok->is(tok::comment) ? FirstTok->getNextNonComment() : FirstTok;
204 std::string Label = computeUsingDeclarationLabel(UsingTok);
205 if (Label.empty()) {
206 endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
207 continue;
208 }
209 UsingDeclarations.push_back(UsingDeclaration(AnnotatedLines[I], Label));
210 }
211 endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
212 return {Fixes, 0};
213 }
214
215 } // namespace format
216 } // namespace clang
217