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
24namespace clang {
25namespace format {
26
27namespace {
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.
36int 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
68int 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
86int 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
94struct 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.
110std::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
137void 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
208UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
209                                                 const FormatStyle &Style)
210    : TokenAnalyzer(Env, Style) {}
211
212std::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