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 23namespace clang { 24namespace format { 25 26namespace { 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. 35int 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 67struct 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. 87std::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 114void 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 180UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env, 181 const FormatStyle &Style) 182 : TokenAnalyzer(Env, Style) {} 183 184std::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