//===--- UsingDeclarationsSorter.cpp ----------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file implements UsingDeclarationsSorter, a TokenAnalyzer that
/// sorts consecutive using declarations.
///
//===----------------------------------------------------------------------===//

#include "UsingDeclarationsSorter.h"
#include "clang/Format/Format.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Regex.h"

#include <algorithm>

#define DEBUG_TYPE "using-declarations-sorter"

namespace clang {
namespace format {

namespace {

// The order of using declaration is defined as follows:
// Split the strings by "::" and discard any initial empty strings. The last
// element of each list is a non-namespace name; all others are namespace
// names. Sort the lists of names lexicographically, where the sort order of
// individual names is that all non-namespace names come before all namespace
// names, and within those groups, names are in case-insensitive lexicographic
// order.
int compareLabelsLexicographicNumeric(StringRef A, StringRef B) {
  SmallVector<StringRef, 2> NamesA;
  A.split(NamesA, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  SmallVector<StringRef, 2> NamesB;
  B.split(NamesB, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  size_t SizeA = NamesA.size();
  size_t SizeB = NamesB.size();
  for (size_t I = 0, E = std::min(SizeA, SizeB); I < E; ++I) {
    if (I + 1 == SizeA) {
      // I is the last index of NamesA and NamesA[I] is a non-namespace name.

      // Non-namespace names come before all namespace names.
      if (SizeB > SizeA)
        return -1;

      // Two names within a group compare case-insensitively.
      return NamesA[I].compare_insensitive(NamesB[I]);
    }

    // I is the last index of NamesB and NamesB[I] is a non-namespace name.
    // Non-namespace names come before all namespace names.
    if (I + 1 == SizeB)
      return 1;

    // Two namespaces names within a group compare case-insensitively.
    int C = NamesA[I].compare_insensitive(NamesB[I]);
    if (C != 0)
      return C;
  }
  return 0;
}

int compareLabelsLexicographic(StringRef A, StringRef B) {
  SmallVector<StringRef, 2> NamesA;
  A.split(NamesA, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  SmallVector<StringRef, 2> NamesB;
  B.split(NamesB, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  size_t SizeA = NamesA.size();
  size_t SizeB = NamesB.size();
  for (size_t I = 0, E = std::min(SizeA, SizeB); I < E; ++I) {
    // Two namespaces names within a group compare case-insensitively.
    int C = NamesA[I].compare_insensitive(NamesB[I]);
    if (C != 0)
      return C;
  }
  if (SizeA < SizeB)
    return -1;
  return SizeA == SizeB ? 0 : 1;
}

int compareLabels(
    StringRef A, StringRef B,
    FormatStyle::SortUsingDeclarationsOptions SortUsingDeclarations) {
  if (SortUsingDeclarations == FormatStyle::SUD_LexicographicNumeric)
    return compareLabelsLexicographicNumeric(A, B);
  return compareLabelsLexicographic(A, B);
}

struct UsingDeclaration {
  const AnnotatedLine *Line;
  std::string Label;

  UsingDeclaration(const AnnotatedLine *Line, const std::string &Label)
      : Line(Line), Label(Label) {}
};

/// Computes the label of a using declaration starting at tthe using token
/// \p UsingTok.
/// If \p UsingTok doesn't begin a using declaration, returns the empty string.
/// Note that this detects specifically using declarations, as in:
/// using A::B::C;
/// and not type aliases, as in:
/// using A = B::C;
/// Type aliases are in general not safe to permute.
std::string computeUsingDeclarationLabel(const FormatToken *UsingTok) {
  assert(UsingTok && UsingTok->is(tok::kw_using) && "Expecting a using token");
  std::string Label;
  const FormatToken *Tok = UsingTok->Next;
  if (Tok && Tok->is(tok::kw_typename)) {
    Label.append("typename ");
    Tok = Tok->Next;
  }
  if (Tok && Tok->is(tok::coloncolon)) {
    Label.append("::");
    Tok = Tok->Next;
  }
  bool HasIdentifier = false;
  while (Tok && Tok->is(tok::identifier)) {
    HasIdentifier = true;
    Label.append(Tok->TokenText.str());
    Tok = Tok->Next;
    if (!Tok || Tok->isNot(tok::coloncolon))
      break;
    Label.append("::");
    Tok = Tok->Next;
  }
  if (HasIdentifier && Tok && Tok->isOneOf(tok::semi, tok::comma))
    return Label;
  return "";
}

void endUsingDeclarationBlock(
    SmallVectorImpl<UsingDeclaration> *UsingDeclarations,
    const SourceManager &SourceMgr, tooling::Replacements *Fixes,
    FormatStyle::SortUsingDeclarationsOptions SortUsingDeclarations) {
  bool BlockAffected = false;
  for (const UsingDeclaration &Declaration : *UsingDeclarations) {
    if (Declaration.Line->Affected) {
      BlockAffected = true;
      break;
    }
  }
  if (!BlockAffected) {
    UsingDeclarations->clear();
    return;
  }
  SmallVector<UsingDeclaration, 4> SortedUsingDeclarations(
      UsingDeclarations->begin(), UsingDeclarations->end());
  auto Comp = [SortUsingDeclarations](const UsingDeclaration &Lhs,
                                      const UsingDeclaration &Rhs) -> bool {
    return compareLabels(Lhs.Label, Rhs.Label, SortUsingDeclarations) < 0;
  };
  llvm::stable_sort(SortedUsingDeclarations, Comp);
  SortedUsingDeclarations.erase(
      llvm::unique(SortedUsingDeclarations,
                   [](const UsingDeclaration &a, const UsingDeclaration &b) {
                     return a.Label == b.Label;
                   }),
      SortedUsingDeclarations.end());
  for (size_t I = 0, E = UsingDeclarations->size(); I < E; ++I) {
    if (I >= SortedUsingDeclarations.size()) {
      // This using declaration has been deduplicated, delete it.
      auto Begin =
          (*UsingDeclarations)[I].Line->First->WhitespaceRange.getBegin();
      auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
      auto Range = CharSourceRange::getCharRange(Begin, End);
      auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, ""));
      if (Err) {
        llvm::errs() << "Error while sorting using declarations: "
                     << llvm::toString(std::move(Err)) << "\n";
      }
      continue;
    }
    if ((*UsingDeclarations)[I].Line == SortedUsingDeclarations[I].Line)
      continue;
    auto Begin = (*UsingDeclarations)[I].Line->First->Tok.getLocation();
    auto End = (*UsingDeclarations)[I].Line->Last->Tok.getEndLoc();
    auto SortedBegin =
        SortedUsingDeclarations[I].Line->First->Tok.getLocation();
    auto SortedEnd = SortedUsingDeclarations[I].Line->Last->Tok.getEndLoc();
    StringRef Text(SourceMgr.getCharacterData(SortedBegin),
                   SourceMgr.getCharacterData(SortedEnd) -
                       SourceMgr.getCharacterData(SortedBegin));
    LLVM_DEBUG({
      StringRef OldText(SourceMgr.getCharacterData(Begin),
                        SourceMgr.getCharacterData(End) -
                            SourceMgr.getCharacterData(Begin));
      llvm::dbgs() << "Replacing '" << OldText << "' with '" << Text << "'\n";
    });
    auto Range = CharSourceRange::getCharRange(Begin, End);
    auto Err = Fixes->add(tooling::Replacement(SourceMgr, Range, Text));
    if (Err) {
      llvm::errs() << "Error while sorting using declarations: "
                   << llvm::toString(std::move(Err)) << "\n";
    }
  }
  UsingDeclarations->clear();
}

} // namespace

UsingDeclarationsSorter::UsingDeclarationsSorter(const Environment &Env,
                                                 const FormatStyle &Style)
    : TokenAnalyzer(Env, Style) {}

std::pair<tooling::Replacements, unsigned> UsingDeclarationsSorter::analyze(
    TokenAnnotator &Annotator, SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
    FormatTokenLexer &Tokens) {
  const SourceManager &SourceMgr = Env.getSourceManager();
  AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
  tooling::Replacements Fixes;
  SmallVector<UsingDeclaration, 4> UsingDeclarations;
  for (const AnnotatedLine *Line : AnnotatedLines) {
    const auto *FirstTok = Line->First;
    if (Line->InPPDirective || !Line->startsWith(tok::kw_using) ||
        FirstTok->Finalized) {
      endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,
                               Style.SortUsingDeclarations);
      continue;
    }
    if (FirstTok->NewlinesBefore > 1) {
      endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,
                               Style.SortUsingDeclarations);
    }
    const auto *UsingTok =
        FirstTok->is(tok::comment) ? FirstTok->getNextNonComment() : FirstTok;
    std::string Label = computeUsingDeclarationLabel(UsingTok);
    if (Label.empty()) {
      endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,
                               Style.SortUsingDeclarations);
      continue;
    }
    UsingDeclarations.push_back(UsingDeclaration(Line, Label));
  }
  endUsingDeclarationBlock(&UsingDeclarations, SourceMgr, &Fixes,
                           Style.SortUsingDeclarations);
  return {Fixes, 0};
}

} // namespace format
} // namespace clang