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
248