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 /// \brief 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.
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 
72   UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
73       : Line(Line), Label(Label) {}
74 
75   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.
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 
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   for (size_t I = 0, E = UsingDeclarations->size(); I < E; ++I) {
134     if ((*UsingDeclarations)[I].Line == SortedUsingDeclarations[I].Line)
135       continue;
136     auto Begin = (*UsingDeclarations)[I].Line->First->Tok.getLocation();
137     auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
138     auto SortedBegin =
139         SortedUsingDeclarations[I].Line->First->Tok.getLocation();
140     auto SortedEnd = SortedUsingDeclarations[I].Line->Last->Tok.getEndLoc();
141     StringRef Text(SourceMgr.getCharacterData(SortedBegin),
142                    SourceMgr.getCharacterData(SortedEnd) -
143                        SourceMgr.getCharacterData(SortedBegin));
144     DEBUG({
145       StringRef OldText(SourceMgr.getCharacterData(Begin),
146                         SourceMgr.getCharacterData(End) -
147                             SourceMgr.getCharacterData(Begin));
148       llvm::dbgs() << "Replacing '" << OldText << "' with '" << Text << "'\n";
149     });
150     auto Range = CharSourceRange::getCharRange(Begin, End);
151     auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, Text));
152     if (Err) {
153       llvm::errs() << "Error while sorting using declarations: "
154                    << llvm::toString(std::move(Err)) << "\n";
155     }
156   }
157   UsingDeclarations->clear();
158 }
159 
160 } // namespace
161 
162 UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
163                                                  const FormatStyle &Style)
164     : TokenAnalyzer(Env, Style) {}
165 
166 std::pair<tooling::Replacements, unsigned> UsingDeclarationsSorter::analyze(
167     TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
168     FormatTokenLexer &Tokens) {
169   const SourceManager &SourceMgr = Env.getSourceManager();
170   AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
171                                         AnnotatedLines.end());
172   tooling::Replacements Fixes;
173   SmallVector<UsingDeclaration, 4> UsingDeclarations;
174   for (size_t I = 0, E = AnnotatedLines.size(); I != E; ++I) {
175     if (AnnotatedLines[I]->InPPDirective ||
176         !AnnotatedLines[I]->startsWith(tok::kw_using) ||
177         AnnotatedLines[I]->First->Finalized) {
178       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
179       continue;
180     }
181     if (AnnotatedLines[I]->First->NewlinesBefore > 1)
182       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
183     std::string Label = computeUsingDeclarationLabel(AnnotatedLines[I]->First);
184     if (Label.empty()) {
185       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
186       continue;
187     }
188     UsingDeclarations.push_back(UsingDeclaration(AnnotatedLines[I], Label));
189   }
190   endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
191   return {Fixes, 0};
192 }
193 
194 } // namespace format
195 } // namespace clang
196