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.
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 
71   UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
72       : Line(Line), Label(Label) {}
73 
74   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.
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 
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 
180 UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
181                                                  const FormatStyle &Style)
182     : TokenAnalyzer(Env, Style) {}
183 
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