//===--- LeftRightQualifierAlignmentFixer.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 LeftRightQualifierAlignmentFixer, a TokenAnalyzer that

/// enforces either left or right const depending on the style.

///

//===----------------------------------------------------------------------===//

#include "QualifierAlignmentFixer.h"

#include "FormatToken.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/Regex.h"

#include <algorithm>

#define DEBUG_TYPE "format-qualifier-alignment-fixer"

namespace clang {

namespace format {

QualifierAlignmentFixer::QualifierAlignmentFixer(

    const Environment &Env, const FormatStyle &Style, StringRef &Code,

    ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,

    unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName)

    : TokenAnalyzer(Env, Style), Code(Code), Ranges(Ranges),

      FirstStartColumn(FirstStartColumn), NextStartColumn(NextStartColumn),

      LastStartColumn(LastStartColumn), FileName(FileName) {

  std::vector<std::string> LeftOrder;

  std::vector<std::string> RightOrder;

  std::vector<tok::TokenKind> ConfiguredQualifierTokens;

  PrepareLeftRightOrdering(Style.QualifierOrder, LeftOrder, RightOrder,

                           ConfiguredQualifierTokens);

  // Handle the left and right alignment separately.

  for (const auto &Qualifier : LeftOrder) {

    Passes.emplace_back(

        [&, Qualifier, ConfiguredQualifierTokens](const Environment &Env) {

          return LeftRightQualifierAlignmentFixer(Env, Style, Qualifier,

                                                  ConfiguredQualifierTokens,

                                                  /*RightAlign=*/false)

              .process();

        });

  }

  for (const auto &Qualifier : RightOrder) {

    Passes.emplace_back(

        [&, Qualifier, ConfiguredQualifierTokens](const Environment &Env) {

          return LeftRightQualifierAlignmentFixer(Env, Style, Qualifier,

                                                  ConfiguredQualifierTokens,

                                                  /*RightAlign=*/true)

              .process();

        });

  }

}

std::pair<tooling::Replacements, unsigned> QualifierAlignmentFixer::analyze(

    TokenAnnotator & /*Annotator*/,

    SmallVectorImpl<AnnotatedLine *> & /*AnnotatedLines*/,

    FormatTokenLexer & /*Tokens*/) {

  auto Env = Environment::make(Code, FileName, Ranges, FirstStartColumn,

                               NextStartColumn, LastStartColumn);

  if (!Env)

    return {};

  llvm::Optional<std::string> CurrentCode = None;

  tooling::Replacements Fixes;

  for (size_t I = 0, E = Passes.size(); I < E; 
++I2.31k
) {

    std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);

    auto NewCode = applyAllReplacements(

        CurrentCode ? 
StringRef(*CurrentCode)1.47k
 : 
Code840
, PassFixes.first);

    if (NewCode) {

      Fixes = Fixes.merge(PassFixes.first);

      if (I + 1 < E) {

        CurrentCode = std::move(*NewCode);

        Env = Environment::make(

            *CurrentCode, FileName,

            tooling::calculateRangesAfterReplacements(Fixes, Ranges),

            FirstStartColumn, NextStartColumn, LastStartColumn);

        if (!Env)

          return {};

      }

    }

  }

  // Don't make replacements that replace nothing.

  tooling::Replacements NonNoOpFixes;

  for (const tooling::Replacement &Fix : Fixes) {

    StringRef OriginalCode = Code.substr(Fix.getOffset(), Fix.getLength());

    if (!OriginalCode.equals(Fix.getReplacementText())) {

      auto Err = NonNoOpFixes.add(Fix);

      if (Err) {

        llvm::errs() << "Error adding replacements : "

                     << llvm::toString(std::move(Err)) << "\n";

      }

    }

  }

  return {NonNoOpFixes, 0};

}

static void replaceToken(const SourceManager &SourceMgr,

                         tooling::Replacements &Fixes,

                         const CharSourceRange &Range, std::string NewText) {

  auto Replacement = tooling::Replacement(SourceMgr, Range, NewText);

  auto Err = Fixes.add(Replacement);

  if (Err) {

    llvm::errs() << "Error while rearranging Qualifier : "

                 << llvm::toString(std::move(Err)) << "\n";

  }

}

static void removeToken(const SourceManager &SourceMgr,

                        tooling::Replacements &Fixes,

                        const FormatToken *First) {

  auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),

                                             First->Tok.getEndLoc());

  replaceToken(SourceMgr, Fixes, Range, "");

}

static void insertQualifierAfter(const SourceManager &SourceMgr,

                                 tooling::Replacements &Fixes,

                                 const FormatToken *First,

                                 const std::string &Qualifier) {

  FormatToken *Next = First->Next;

  if (!Next)

    return;

  auto Range = CharSourceRange::getCharRange(Next->getStartOfNonWhitespace(),

                                             Next->Tok.getEndLoc());

  std::string NewText = " " + Qualifier + " ";

  NewText += Next->TokenText;

  replaceToken(SourceMgr, Fixes, Range, NewText);

}

static void insertQualifierBefore(const SourceManager &SourceMgr,

                                  tooling::Replacements &Fixes,

                                  const FormatToken *First,

                                  const std::string &Qualifier) {

  auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),

                                             First->Tok.getEndLoc());

  std::string NewText = " " + Qualifier + " ";

  NewText += First->TokenText;

  replaceToken(SourceMgr, Fixes, Range, NewText);

}

static bool endsWithSpace(const std::string &s) {

  if (s.empty())

    return false;

  return isspace(s.back());

}

static bool startsWithSpace(const std::string &s) {

  if (s.empty())

    return false;

  return isspace(s.front());

}

static void rotateTokens(const SourceManager &SourceMgr,

                         tooling::Replacements &Fixes, const FormatToken *First,

                         const FormatToken *Last, bool Left) {

  auto *End = Last;

  auto *Begin = First;

  if (!Left) {

    End = Last->Next;

    Begin = First->Next;

  }

  std::string NewText;

  // If we are rotating to the left we move the Last token to the front.

  if (Left) {

    NewText += Last->TokenText;

    NewText += " ";

  }

  // Then move through the other tokens.

  auto *Tok = Begin;

  while (Tok != End) {

    if (!NewText.empty() && 
!endsWithSpace(NewText)683
)

      NewText += " ";

    NewText += Tok->TokenText;

    Tok = Tok->Next;

  }

  // If we are rotating to the right we move the first token to the back.

  if (!Left) {

    if (!NewText.empty() && !startsWithSpace(NewText))

      NewText += " ";

    NewText += First->TokenText;

  }

  auto Range = CharSourceRange::getCharRange(First->getStartOfNonWhitespace(),

                                             Last->Tok.getEndLoc());

  replaceToken(SourceMgr, Fixes, Range, NewText);

}

const FormatToken *LeftRightQualifierAlignmentFixer::analyzeRight(

    const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,

    tooling::Replacements &Fixes, const FormatToken *Tok,

    const std::string &Qualifier, tok::TokenKind QualifierType) {

  // We only need to think about streams that begin with a qualifier.

  if (!Tok->is(QualifierType))

    return Tok;

  // Don't concern yourself if nothing follows the qualifier.

  if (!Tok->Next)

    return Tok;

  if (LeftRightQualifierAlignmentFixer::isPossibleMacro(Tok->Next))

    return Tok;

  auto AnalyzeTemplate =

      [&](const FormatToken *Tok,

          const FormatToken *StartTemplate) -> const FormatToken * {

    // Read from the TemplateOpener to TemplateCloser.

    FormatToken *EndTemplate = StartTemplate->MatchingParen;

    if (EndTemplate) {

      // Move to the end of any template class members e.g.

      // `Foo<int>::iterator`.

      if (EndTemplate->startsSequence(TT_TemplateCloser, tok::coloncolon,

                                      tok::identifier)) {

        EndTemplate = EndTemplate->Next->Next;

      }

    }

    if (EndTemplate && EndTemplate->Next &&

        !EndTemplate->Next->isOneOf(tok::equal, tok::l_paren)) {

      insertQualifierAfter(SourceMgr, Fixes, EndTemplate, Qualifier);

      // Remove the qualifier.

      removeToken(SourceMgr, Fixes, Tok);

      return Tok;

    }

    return nullptr;

  };

  FormatToken *Qual = Tok->Next;

  FormatToken *LastQual = Qual;

  while (Qual && isQualifierOrType(Qual, ConfiguredQualifierTokens)) {

    LastQual = Qual;

    Qual = Qual->Next;

  }

  if (LastQual && Qual != LastQual) {

    rotateTokens(SourceMgr, Fixes, Tok, LastQual, /*Left=*/false);

    Tok = LastQual;

  } else if (Tok->startsSequence(QualifierType, tok::identifier,

                                 TT_TemplateCloser)) {

    FormatToken *Closer = Tok->Next->Next;

    rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/false);

    Tok = Closer;

    return Tok;

  } else if (Tok->startsSequence(QualifierType, tok::identifier,

                                 TT_TemplateOpener)) {

    // `const ArrayRef<int> a;`

    // `const ArrayRef<int> &a;`

    const FormatToken *NewTok = AnalyzeTemplate(Tok, Tok->Next->Next);

    if (NewTok)

      return NewTok;

  } else if (Tok->startsSequence(QualifierType, tok::coloncolon,

                                 tok::identifier, TT_TemplateOpener)) {

    // `const ::ArrayRef<int> a;`

    // `const ::ArrayRef<int> &a;`

    const FormatToken *NewTok = AnalyzeTemplate(Tok, Tok->Next->Next->Next);

    if (NewTok)

      return NewTok;

  } else if (Tok->startsSequence(QualifierType, tok::identifier) ||

             Tok->startsSequence(QualifierType, tok::coloncolon,

                                 tok::identifier)) {

    FormatToken *Next = Tok->Next;

    // The case  `const Foo` -> `Foo const`

    // The case  `const ::Foo` -> `::Foo const`

    // The case  `const Foo *` -> `Foo const *`

    // The case  `const Foo &` -> `Foo const &`

    // The case  `const Foo &&` -> `Foo const &&`

    // The case  `const std::Foo &&` -> `std::Foo const &&`

    // The case  `const std::Foo<T> &&` -> `std::Foo<T> const &&`

    while (Next && 
Next->isOneOf(tok::identifier, tok::coloncolon)252
)

      Next = Next->Next;

    if (Next && 
Next->is(TT_TemplateOpener)95
) {

      Next = Next->MatchingParen;

      // Move to the end of any template class members e.g.

      // `Foo<int>::iterator`.

      if (Next && Next->startsSequence(TT_TemplateCloser, tok::coloncolon,

                                       tok::identifier)) {

        return Tok;

      }

      assert(Next && "Missing template opener");

      Next = Next->Next;

    }

    if (Next && 
Next->isOneOf(tok::star, tok::amp, tok::ampamp)95
 &&

        
!Tok->Next->isOneOf(Keywords.kw_override, Keywords.kw_final)28
) {

      if (Next->Previous && !Next->Previous->is(QualifierType)) {

        insertQualifierAfter(SourceMgr, Fixes, Next->Previous, Qualifier);

        removeToken(SourceMgr, Fixes, Tok);

      }

      return Next;

    }

  }

  return Tok;

}

const FormatToken *LeftRightQualifierAlignmentFixer::analyzeLeft(

    const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,

    tooling::Replacements &Fixes, const FormatToken *Tok,

    const std::string &Qualifier, tok::TokenKind QualifierType) {

  // if Tok is an identifier and possibly a macro then don't convert.

  if (LeftRightQualifierAlignmentFixer::isPossibleMacro(Tok))

    return Tok;

  const FormatToken *Qual = Tok;

  const FormatToken *LastQual = Qual;

  while (Qual && isQualifierOrType(Qual, ConfiguredQualifierTokens)) {

    LastQual = Qual;

    Qual = Qual->Next;

    if (Qual && Qual->is(QualifierType))

      break;

  }

  if (!Qual)

    return Tok;

  if (LastQual && Qual != LastQual && 
Qual->is(QualifierType)2.96k
) {

    rotateTokens(SourceMgr, Fixes, Tok, Qual, /*Left=*/true);

    if (!Qual->Next)

      return Tok;

    Tok = Qual->Next;

  } else if (Tok->startsSequence(tok::identifier, QualifierType)) {

    if (Tok->Next->Next && Tok->Next->Next->isOneOf(tok::identifier, tok::star,

                                                    tok::amp, tok::ampamp)) {

      // Don't swap `::iterator const` to `::const iterator`.

      if (!Tok->Previous ||

          (Tok->Previous && !Tok->Previous->is(tok::coloncolon))) {

        rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);

        Tok = Tok->Next;

      }

    } else if (Tok->startsSequence(tok::identifier, QualifierType,

                                   TT_TemplateCloser)) {

      FormatToken *Closer = Tok->Next->Next;

      rotateTokens(SourceMgr, Fixes, Tok, Tok->Next, /*Left=*/true);

      Tok = Closer;

    }

  }

  if (Tok->is(TT_TemplateOpener) && 
Tok->Next690
 &&

      
(690
Tok->Next->is(tok::identifier)690
 || 
Tok->Next->isSimpleTypeSpecifier()376
) &&

      
Tok->Next->Next504
 && 
Tok->Next->Next->is(QualifierType)504
) {

    rotateTokens(SourceMgr, Fixes, Tok->Next, Tok->Next->Next, /*Left=*/true);

  }

  if ((Tok->startsSequence(tok::coloncolon, tok::identifier) ||

       
Tok->is(tok::identifier)9.25k
) &&

      
Tok->Next3.25k
) {

    if (Tok->Previous &&

        
Tok->Previous->isOneOf(tok::star, tok::ampamp, tok::amp)3.09k
) {

      return Tok;

    }

    const FormatToken *Next = Tok->Next;

    // The case  `std::Foo<T> const` -> `const std::Foo<T> &&`

    while (Next && 
Next->isOneOf(tok::identifier, tok::coloncolon)3.56k
)

      Next = Next->Next;

    if (Next && 
Next->Previous2.72k
 &&

        
Next->Previous->startsSequence(tok::identifier, TT_TemplateOpener)2.72k
) {

      // Read from to the end of the TemplateOpener to

      // TemplateCloser const ArrayRef<int> a; const ArrayRef<int> &a;

      if (Next->is(tok::comment) && 
Next->getNextNonComment()36
)

        Next = Next->getNextNonComment();

      assert(Next->MatchingParen && "Missing template closer");

      Next = Next->MatchingParen;

      // If the template closer is closing the requires clause,

      // then stop and go back to the TemplateOpener and do whatever is

      // inside the <>.

      if (Next->ClosesRequiresClause)

        return Next->MatchingParen;

      Next = Next->Next;

      // Move to the end of any template class members e.g.

      // `Foo<int>::iterator`.

      if (Next && 
Next->startsSequence(tok::coloncolon, tok::identifier)729
)

        Next = Next->Next->Next;

      if (Next && 
Next->is(QualifierType)729
) {

        // Move the qualifier.

        insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);

        removeToken(SourceMgr, Fixes, Next);

        return Next;

      }

    }

    if (Next && 
Next->Next2.61k
 &&

        
Next->Next->isOneOf(tok::amp, tok::ampamp, tok::star)1.74k
) {

      if (Next->is(QualifierType)) {

        // Move the qualifier.

        insertQualifierBefore(SourceMgr, Fixes, Tok, Qualifier);

        removeToken(SourceMgr, Fixes, Next);

        return Next;

      }

    }

  }

  return Tok;

}

tok::TokenKind LeftRightQualifierAlignmentFixer::getTokenFromQualifier(

    const std::string &Qualifier) {

  // Don't let 'type' be an identifier, but steal typeof token.

  return llvm::StringSwitch<tok::TokenKind>(Qualifier)

      .Case("type", tok::kw_typeof)

      .Case("const", tok::kw_const)

      .Case("volatile", tok::kw_volatile)

      .Case("static", tok::kw_static)

      .Case("inline", tok::kw_inline)

      .Case("constexpr", tok::kw_constexpr)

      .Case("restrict", tok::kw_restrict)

      .Default(tok::identifier);

}

LeftRightQualifierAlignmentFixer::LeftRightQualifierAlignmentFixer(

    const Environment &Env, const FormatStyle &Style,

    const std::string &Qualifier,

    const std::vector<tok::TokenKind> &QualifierTokens, bool RightAlign)

    : TokenAnalyzer(Env, Style), Qualifier(Qualifier), RightAlign(RightAlign),

      ConfiguredQualifierTokens(QualifierTokens) {}

std::pair<tooling::Replacements, unsigned>

LeftRightQualifierAlignmentFixer::analyze(

    TokenAnnotator & /*Annotator*/,

    SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,

    FormatTokenLexer &Tokens) {

  tooling::Replacements Fixes;

  const AdditionalKeywords &Keywords = Tokens.getKeywords();

  const SourceManager &SourceMgr = Env.getSourceManager();

  AffectedRangeMgr.computeAffectedLines(AnnotatedLines);

  tok::TokenKind QualifierToken = getTokenFromQualifier(Qualifier);

  assert(QualifierToken != tok::identifier && "Unrecognised Qualifier");

  for (AnnotatedLine *Line : AnnotatedLines) {

    if (Line->InPPDirective)

      continue;

    FormatToken *First = Line->First;

    assert(First);

    if (First->Finalized)

      continue;

    const auto *Last = Line->Last;

    for (const auto *Tok = First; Tok && 
Tok != Last20.4k
 && 
Tok->Next15.4k
;

         Tok = Tok->Next) {

      if (Tok->is(tok::comment))

        continue;

      if (RightAlign) {

        Tok = analyzeRight(SourceMgr, Keywords, Fixes, Tok, Qualifier,

                           QualifierToken);

      } else {

        Tok = analyzeLeft(SourceMgr, Keywords, Fixes, Tok, Qualifier,

                          QualifierToken);

      }

    }

  }

  return {Fixes, 0};

}

void QualifierAlignmentFixer::PrepareLeftRightOrdering(

    const std::vector<std::string> &Order, std::vector<std::string> &LeftOrder,

    std::vector<std::string> &RightOrder,

    std::vector<tok::TokenKind> &Qualifiers) {

  // Depending on the position of type in the order you need

  // To iterate forward or backward through the order list as qualifier

  // can push through each other.

  // The Order list must define the position of "type" to signify

  assert(llvm::is_contained(Order, "type") &&

         "QualifierOrder must contain type");

  // Split the Order list by type and reverse the left side.

  bool left = true;

  for (const auto &s : Order) {

    if (s == "type") {

      left = false;

      continue;

    }

    tok::TokenKind QualifierToken =

        LeftRightQualifierAlignmentFixer::getTokenFromQualifier(s);

    if (QualifierToken != tok::kw_typeof && QualifierToken != tok::identifier)

      Qualifiers.push_back(QualifierToken);

    if (left) {

      // Reverse the order for left aligned items.

      LeftOrder.insert(LeftOrder.begin(), s);

    } else {

      RightOrder.push_back(s);

    }

  }

}

bool LeftRightQualifierAlignmentFixer::isQualifierOrType(

    const FormatToken *Tok, const std::vector<tok::TokenKind> &specifiedTypes) {

  return Tok && (Tok->isSimpleTypeSpecifier() || 
Tok->is(tok::kw_auto)12.1k
 ||

                 
llvm::is_contained(specifiedTypes, Tok->Tok.getKind())12.0k
);

}

// If a token is an identifier and it's upper case, it could

// be a macro and hence we need to be able to ignore it.

bool LeftRightQualifierAlignmentFixer::isPossibleMacro(const FormatToken *Tok) {

  if (!Tok)

    return false;

  if (!Tok->is(tok::identifier))

    return false;

  if (Tok->TokenText.upper() == Tok->TokenText.str()) {

    // T,K,U,V likely could be template arguments

    return (Tok->TokenText.size() != 1);

  }

  return false;

}

} // namespace format

} // namespace clang