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