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 struct UsingDeclaration {
30   const AnnotatedLine *Line;
31   std::string Label;
32 
33   UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
34       : Line(Line), Label(Label) {}
35 
36   // Compares lexicographically with the exception that '_' is just before 'A'.
37   bool operator<(const UsingDeclaration &Other) const {
38     size_t Size = Label.size();
39     size_t OtherSize = Other.Label.size();
40     for (size_t I = 0, E = std::min(Size, OtherSize); I < E; ++I) {
41       char Rank = rank(Label[I]);
42       char OtherRank = rank(Other.Label[I]);
43       if (Rank != OtherRank)
44         return Rank < OtherRank;
45     }
46     return Size < OtherSize;
47   }
48 
49   // Returns the position of c in a lexicographic ordering with the exception
50   // that '_' is just before 'A'.
51   static char rank(char c) {
52     if (c == '_')
53       return 'A';
54     if ('A' <= c && c < '_')
55       return c + 1;
56     return c;
57   }
58 };
59 
60 /// Computes the label of a using declaration starting at tthe using token
61 /// \p UsingTok.
62 /// If \p UsingTok doesn't begin a using declaration, returns the empty string.
63 /// Note that this detects specifically using declarations, as in:
64 /// using A::B::C;
65 /// and not type aliases, as in:
66 /// using A = B::C;
67 /// Type aliases are in general not safe to permute.
68 std::string computeUsingDeclarationLabel(const FormatToken *UsingTok) {
69   assert(UsingTok && UsingTok->is(tok::kw_using) && "Expecting a using token");
70   std::string Label;
71   const FormatToken *Tok = UsingTok->Next;
72   if (Tok && Tok->is(tok::kw_typename)) {
73     Label.append("typename ");
74     Tok = Tok->Next;
75   }
76   if (Tok && Tok->is(tok::coloncolon)) {
77     Label.append("::");
78     Tok = Tok->Next;
79   }
80   bool HasIdentifier = false;
81   while (Tok && Tok->is(tok::identifier)) {
82     HasIdentifier = true;
83     Label.append(Tok->TokenText.str());
84     Tok = Tok->Next;
85     if (!Tok || Tok->isNot(tok::coloncolon))
86       break;
87     Label.append("::");
88     Tok = Tok->Next;
89   }
90   if (HasIdentifier && Tok && Tok->isOneOf(tok::semi, tok::comma))
91     return Label;
92   return "";
93 }
94 
95 void endUsingDeclarationBlock(
96     SmallVectorImpl<UsingDeclaration> *UsingDeclarations,
97     const SourceManager &SourceMgr, tooling::Replacements *Fixes) {
98   bool BlockAffected = false;
99   for (const UsingDeclaration &Declaration : *UsingDeclarations) {
100     if (Declaration.Line->Affected) {
101       BlockAffected = true;
102       break;
103     }
104   }
105   if (!BlockAffected) {
106     UsingDeclarations->clear();
107     return;
108   }
109   SmallVector<UsingDeclaration, 4> SortedUsingDeclarations(
110       UsingDeclarations->begin(), UsingDeclarations->end());
111   std::stable_sort(SortedUsingDeclarations.begin(),
112                    SortedUsingDeclarations.end());
113   for (size_t I = 0, E = UsingDeclarations->size(); I < E; ++I) {
114     if ((*UsingDeclarations)[I].Line == SortedUsingDeclarations[I].Line)
115       continue;
116     auto Begin = (*UsingDeclarations)[I].Line->First->Tok.getLocation();
117     auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
118     auto SortedBegin =
119         SortedUsingDeclarations[I].Line->First->Tok.getLocation();
120     auto SortedEnd = SortedUsingDeclarations[I].Line->Last->Tok.getEndLoc();
121     StringRef Text(SourceMgr.getCharacterData(SortedBegin),
122                    SourceMgr.getCharacterData(SortedEnd) -
123                        SourceMgr.getCharacterData(SortedBegin));
124     DEBUG({
125       StringRef OldText(SourceMgr.getCharacterData(Begin),
126                         SourceMgr.getCharacterData(End) -
127                             SourceMgr.getCharacterData(Begin));
128       llvm::dbgs() << "Replacing '" << OldText << "' with '" << Text << "'\n";
129     });
130     auto Range = CharSourceRange::getCharRange(Begin, End);
131     auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, Text));
132     if (Err) {
133       llvm::errs() << "Error while sorting using declarations: "
134                    << llvm::toString(std::move(Err)) << "\n";
135     }
136   }
137   UsingDeclarations->clear();
138 }
139 
140 } // namespace
141 
142 UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
143                                                  const FormatStyle &Style)
144     : TokenAnalyzer(Env, Style) {}
145 
146 std::pair<tooling::Replacements, unsigned> UsingDeclarationsSorter::analyze(
147     TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
148     FormatTokenLexer &Tokens) {
149   const SourceManager &SourceMgr = Env.getSourceManager();
150   AffectedRangeMgr.computeAffectedLines(AnnotatedLines.begin(),
151                                         AnnotatedLines.end());
152   tooling::Replacements Fixes;
153   SmallVector<UsingDeclaration, 4> UsingDeclarations;
154   for (size_t I = 0, E = AnnotatedLines.size(); I != E; ++I) {
155     if (AnnotatedLines[I]->InPPDirective ||
156         !AnnotatedLines[I]->startsWith(tok::kw_using) ||
157         AnnotatedLines[I]->First->Finalized) {
158       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
159       continue;
160     }
161     if (AnnotatedLines[I]->First->NewlinesBefore > 1)
162       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
163     std::string Label = computeUsingDeclarationLabel(AnnotatedLines[I]->First);
164     if (Label.empty()) {
165       endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
166       continue;
167     }
168     UsingDeclarations.push_back(UsingDeclaration(AnnotatedLines[I], Label));
169   }
170   endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes);
171   return {Fixes, 0};
172 }
173 
174 } // namespace format
175 } // namespace clang
176