lib/Format/QualifierAlignmentFixer.cpp - llvm-project/clang - Git at Google

 //===--- QualifierAlignmentFixer.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 QualifierAlignmentFixer, 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>
 #include <optional>

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

 namespace clang {
 namespace format {

 void addQualifierAlignmentFixerPasses(const FormatStyle &Style,
                                       SmallVectorImpl<AnalyzerPass> &Passes) {
   std::vector<std::string> LeftOrder;
   std::vector<std::string> RightOrder;
   std::vector<tok::TokenKind> ConfiguredQualifierTokens;
   prepareLeftRightOrderingForQualifierAlignmentFixer(
       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();
         });
   }
 }

 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) {
   auto Range = CharSourceRange::getCharRange(First->Tok.getLocation(),
                                              First->Tok.getEndLoc());

   std::string NewText{};
   NewText += First->TokenText;
   NewText += " " + Qualifier;
   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))
       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);
 }

 static bool
 isConfiguredQualifier(const FormatToken *const Tok,
                       const std::vector<tok::TokenKind> &Qualifiers) {
   return Tok && llvm::is_contained(Qualifiers, Tok->Tok.getKind());
 }

 static bool isQualifier(const FormatToken *const Tok) {
   if (!Tok)
     return false;

   switch (Tok->Tok.getKind()) {
   case tok::kw_const:
   case tok::kw_volatile:
   case tok::kw_static:
   case tok::kw_inline:
   case tok::kw_constexpr:
   case tok::kw_restrict:
   case tok::kw_friend:
     return true;
   default:
     return false;
   }
 }

 const FormatToken *LeftRightQualifierAlignmentFixer::analyzeRight(
     const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
     tooling::Replacements &Fixes, const FormatToken *const Tok,
     const std::string &Qualifier, tok::TokenKind QualifierType) {
   // We only need to think about streams that begin with a qualifier.
   if (Tok->isNot(QualifierType))
     return Tok;
   // Don't concern yourself if nothing follows the qualifier.
   if (!Tok->Next)
     return Tok;

   // Skip qualifiers to the left to find what preceeds the qualifiers.
   // Use isQualifier rather than isConfiguredQualifier to cover all qualifiers.
   const FormatToken *PreviousCheck = Tok->getPreviousNonComment();
   while (isQualifier(PreviousCheck))
     PreviousCheck = PreviousCheck->getPreviousNonComment();

   // Examples given in order of ['type', 'const', 'volatile']
   const bool IsRightQualifier = PreviousCheck && [PreviousCheck]() {
     // The cases:
     // `Foo() const` -> `Foo() const`
     // `Foo() const final` -> `Foo() const final`
     // `Foo() const override` -> `Foo() const final`
     // `Foo() const volatile override` -> `Foo() const volatile override`
     // `Foo() volatile const final` -> `Foo() const volatile final`
     if (PreviousCheck->is(tok::r_paren))
       return true;

     // The cases:
     // `struct {} volatile const a;` -> `struct {} const volatile a;`
     // `class {} volatile const a;` -> `class {} const volatile a;`
     if (PreviousCheck->is(tok::r_brace))
       return true;

     // The case:
     // `template <class T> const Bar Foo()` ->
     // `template <class T> Bar const Foo()`
     // The cases:
     // `Foo<int> const foo` -> `Foo<int> const foo`
     // `Foo<int> volatile const` -> `Foo<int> const volatile`
     // The case:
     // ```
     // template <class T>
     //   requires Concept1<T> && requires Concept2<T>
     // const Foo f();
     // ```
     // ->
     // ```
     // template <class T>
     //   requires Concept1<T> && requires Concept2<T>
     // Foo const f();
     // ```
     if (PreviousCheck->is(TT_TemplateCloser)) {
       // If the token closes a template<> or requires clause, then it is a left
       // qualifier and should be moved to the right.
       return !(PreviousCheck->ClosesTemplateDeclaration ||
                PreviousCheck->ClosesRequiresClause);
     }

     // The case  `Foo* const` -> `Foo* const`
     // The case  `Foo* volatile const` -> `Foo* const volatile`
     // The case  `int32_t const` -> `int32_t const`
     // The case  `auto volatile const` -> `auto const volatile`
     if (PreviousCheck->isOneOf(TT_PointerOrReference, tok::identifier,
                                tok::kw_auto)) {
       return true;
     }

     return false;
   }();

   // Find the last qualifier to the right.
   const FormatToken *LastQual = Tok;
   while (isQualifier(LastQual->getNextNonComment()))
     LastQual = LastQual->getNextNonComment();

   // If this qualifier is to the right of a type or pointer do a partial sort
   // and return.
   if (IsRightQualifier) {
     if (LastQual != Tok)
       rotateTokens(SourceMgr, Fixes, Tok, LastQual, /*Left=*/false);
     return Tok;
   }

   const FormatToken *TypeToken = LastQual->getNextNonComment();
   if (!TypeToken)
     return Tok;

   // Stay safe and don't move past macros, also don't bother with sorting.
   if (isPossibleMacro(TypeToken))
     return Tok;

   const bool IsCpp = Style.isCpp();

   // The case `const long long int volatile` -> `long long int const volatile`
   // The case `long const long int volatile` -> `long long int const volatile`
   // The case `long long volatile int const` -> `long long int const volatile`
   // The case `const long long volatile int` -> `long long int const volatile`
   if (TypeToken->isTypeName(IsCpp)) {
     // The case `const decltype(foo)` -> `const decltype(foo)`
     // The case `const typeof(foo)` -> `const typeof(foo)`
     // The case `const _Atomic(foo)` -> `const _Atomic(foo)`
     if (TypeToken->isOneOf(tok::kw_decltype, tok::kw_typeof, tok::kw__Atomic))
       return Tok;

     const FormatToken *LastSimpleTypeSpecifier = TypeToken;
     while (isQualifierOrType(LastSimpleTypeSpecifier->getNextNonComment(),
                              IsCpp)) {
       LastSimpleTypeSpecifier = LastSimpleTypeSpecifier->getNextNonComment();
     }

     rotateTokens(SourceMgr, Fixes, Tok, LastSimpleTypeSpecifier,
                  /*Left=*/false);
     return LastSimpleTypeSpecifier;
   }

   // The case  `unsigned short const` -> `unsigned short const`
   // The case:
   // `unsigned short volatile const` -> `unsigned short const volatile`
   if (PreviousCheck && PreviousCheck->isTypeName(IsCpp)) {
     if (LastQual != Tok)
       rotateTokens(SourceMgr, Fixes, Tok, LastQual, /*Left=*/false);
     return Tok;
   }

   // Skip the typename keyword.
   // The case `const typename C::type` -> `typename C::type const`
   if (TypeToken->is(tok::kw_typename))
     TypeToken = TypeToken->getNextNonComment();

   // Skip the initial :: of a global-namespace type.
   // The case `const ::...` -> `::... const`
   if (TypeToken->is(tok::coloncolon)) {
     // The case `const ::template Foo...` -> `::template Foo... const`
     TypeToken = TypeToken->getNextNonComment();
     if (TypeToken && TypeToken->is(tok::kw_template))
       TypeToken = TypeToken->getNextNonComment();
   }

   // Don't change declarations such as
   // `foo(const struct Foo a);` -> `foo(const struct Foo a);`
   // as they would currently change code such as
   // `const struct my_struct_t {} my_struct;` -> `struct my_struct_t const {}
   // my_struct;`
   if (TypeToken->isOneOf(tok::kw_struct, tok::kw_class))
     return Tok;

   if (TypeToken->isOneOf(tok::kw_auto, tok::identifier)) {
     // The case  `const auto` -> `auto 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 Foo &&` -> `Foo const &&`
     // The case  `const std::Foo &&` -> `std::Foo const &&`
     // The case  `const std::Foo<T> &&` -> `std::Foo<T> const &&`
     // The case  `const ::template Foo` -> `::template Foo const`
     // The case  `const T::template Foo` -> `T::template Foo const`
     const FormatToken *Next = nullptr;
     while ((Next = TypeToken->getNextNonComment()) &&
            (Next->is(TT_TemplateOpener) ||
             Next->startsSequence(tok::coloncolon, tok::identifier) ||
             Next->startsSequence(tok::coloncolon, tok::kw_template,
                                  tok::identifier))) {
       if (Next->is(TT_TemplateOpener)) {
         assert(Next->MatchingParen && "Missing template closer");
         TypeToken = Next->MatchingParen;
       } else if (Next->startsSequence(tok::coloncolon, tok::identifier)) {
         TypeToken = Next->getNextNonComment();
       } else {
         TypeToken = Next->getNextNonComment()->getNextNonComment();
       }
     }

     if (Next->is(tok::kw_auto))
       TypeToken = Next;

     // Place the Qualifier at the end of the list of qualifiers.
     while (isQualifier(TypeToken->getNextNonComment())) {
       // The case `volatile Foo::iter const` -> `Foo::iter const volatile`
       TypeToken = TypeToken->getNextNonComment();
     }

     insertQualifierAfter(SourceMgr, Fixes, TypeToken, Qualifier);
     // Remove token and following whitespace.
     auto Range = CharSourceRange::getCharRange(
         Tok->getStartOfNonWhitespace(), Tok->Next->getStartOfNonWhitespace());
     replaceToken(SourceMgr, Fixes, Range, "");
   }

   return Tok;
 }

 const FormatToken *LeftRightQualifierAlignmentFixer::analyzeLeft(
     const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
     tooling::Replacements &Fixes, const FormatToken *const Tok,
     const std::string &Qualifier, tok::TokenKind QualifierType) {
   // We only need to think about streams that begin with a qualifier.
   if (Tok->isNot(QualifierType))
     return Tok;
   // Don't concern yourself if nothing preceeds the qualifier.
   if (!Tok->getPreviousNonComment())
     return Tok;

   // Skip qualifiers to the left to find what preceeds the qualifiers.
   const FormatToken *TypeToken = Tok->getPreviousNonComment();
   while (isQualifier(TypeToken))
     TypeToken = TypeToken->getPreviousNonComment();

   // For left qualifiers preceeded by nothing, a template declaration, or *,&,&&
   // we only perform sorting.
   if (!TypeToken || TypeToken->isPointerOrReference() ||
       TypeToken->ClosesRequiresClause || TypeToken->ClosesTemplateDeclaration) {

     // Don't sort past a non-configured qualifier token.
     const FormatToken *FirstQual = Tok;
     while (isConfiguredQualifier(FirstQual->getPreviousNonComment(),
                                  ConfiguredQualifierTokens)) {
       FirstQual = FirstQual->getPreviousNonComment();
     }

     if (FirstQual != Tok)
       rotateTokens(SourceMgr, Fixes, FirstQual, Tok, /*Left=*/true);
     return Tok;
   }

   // Stay safe and don't move past macros, also don't bother with sorting.
   if (isPossibleMacro(TypeToken))
     return Tok;

   // Examples given in order of ['const', 'volatile', 'type']

   // The case `volatile long long int const` -> `const volatile long long int`
   // The case `volatile long long const int` -> `const volatile long long int`
   // The case `const long long volatile int` -> `const volatile long long int`
   // The case `long volatile long int const` -> `const volatile long long int`
   if (const bool IsCpp = Style.isCpp(); TypeToken->isTypeName(IsCpp)) {
     const FormatToken *LastSimpleTypeSpecifier = TypeToken;
     while (isConfiguredQualifierOrType(
         LastSimpleTypeSpecifier->getPreviousNonComment(),
         ConfiguredQualifierTokens, IsCpp)) {
       LastSimpleTypeSpecifier =
           LastSimpleTypeSpecifier->getPreviousNonComment();
     }

     rotateTokens(SourceMgr, Fixes, LastSimpleTypeSpecifier, Tok,
                  /*Left=*/true);
     return Tok;
   }

   if (TypeToken->isOneOf(tok::kw_auto, tok::identifier, TT_TemplateCloser)) {
     const auto IsStartOfType = [](const FormatToken *const Tok) -> bool {
       if (!Tok)
         return true;

       // A template closer is not the start of a type.
       // The case `?<> const` -> `const ?<>`
       if (Tok->is(TT_TemplateCloser))
         return false;

       const FormatToken *const Previous = Tok->getPreviousNonComment();
       if (!Previous)
         return true;

       // An identifier preceeded by :: is not the start of a type.
       // The case `?::Foo const` -> `const ?::Foo`
       if (Tok->is(tok::identifier) && Previous->is(tok::coloncolon))
         return false;

       const FormatToken *const PrePrevious = Previous->getPreviousNonComment();
       // An identifier preceeded by ::template is not the start of a type.
       // The case `?::template Foo const` -> `const ?::template Foo`
       if (Tok->is(tok::identifier) && Previous->is(tok::kw_template) &&
           PrePrevious && PrePrevious->is(tok::coloncolon)) {
         return false;
       }

       if (Tok->endsSequence(tok::kw_auto, tok::identifier))
         return false;

       return true;
     };

     while (!IsStartOfType(TypeToken)) {
       // The case `?<>`
       if (TypeToken->is(TT_TemplateCloser)) {
         assert(TypeToken->MatchingParen && "Missing template opener");
         TypeToken = TypeToken->MatchingParen->getPreviousNonComment();
       } else {
         // The cases
         // `::Foo`
         // `?>::Foo`
         // `?Bar::Foo`
         // `::template Foo`
         // `?>::template Foo`
         // `?Bar::template Foo`
         if (TypeToken->getPreviousNonComment()->is(tok::kw_template))
           TypeToken = TypeToken->getPreviousNonComment();

         const FormatToken *const ColonColon =
             TypeToken->getPreviousNonComment();
         const FormatToken *const PreColonColon =
             ColonColon->getPreviousNonComment();
         if (PreColonColon &&
             PreColonColon->isOneOf(TT_TemplateCloser, tok::identifier)) {
           TypeToken = PreColonColon;
         } else {
           TypeToken = ColonColon;
         }
       }
     }

     assert(TypeToken && "Should be auto or identifier");

     // Place the Qualifier at the start of the list of qualifiers.
     const FormatToken *Previous = nullptr;
     while ((Previous = TypeToken->getPreviousNonComment()) &&
            (isConfiguredQualifier(Previous, ConfiguredQualifierTokens) ||
             Previous->is(tok::kw_typename))) {
       // The case `volatile Foo::iter const` -> `const volatile Foo::iter`
       // The case `typename C::type const` -> `const typename C::type`
       TypeToken = Previous;
     }

     // Don't change declarations such as
     // `foo(struct Foo const a);` -> `foo(struct Foo const a);`
     if (!Previous || !Previous->isOneOf(tok::kw_struct, tok::kw_class)) {
       insertQualifierBefore(SourceMgr, Fixes, TypeToken, Qualifier);
       removeToken(SourceMgr, Fixes, Tok);
     }
   }

   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)
       .Case("friend", tok::kw_friend)
       .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;
   AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
   fixQualifierAlignment(AnnotatedLines, Tokens, Fixes);
   return {Fixes, 0};
 }

 void LeftRightQualifierAlignmentFixer::fixQualifierAlignment(
     SmallVectorImpl<AnnotatedLine *> &AnnotatedLines, FormatTokenLexer &Tokens,
     tooling::Replacements &Fixes) {
   const AdditionalKeywords &Keywords = Tokens.getKeywords();
   const SourceManager &SourceMgr = Env.getSourceManager();
   tok::TokenKind QualifierToken = getTokenFromQualifier(Qualifier);
   assert(QualifierToken != tok::identifier && "Unrecognised Qualifier");

   for (AnnotatedLine *Line : AnnotatedLines) {
     fixQualifierAlignment(Line->Children, Tokens, Fixes);
     if (!Line->Affected || 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 != Last && Tok->Next;
          Tok = Tok->Next) {
       if (Tok->MustBreakBefore)
         break;
       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);
       }
     }
   }
 }

 void prepareLeftRightOrderingForQualifierAlignmentFixer(
     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,
                                                          bool IsCpp) {
   return Tok &&
          (Tok->isTypeName(IsCpp) || Tok->is(tok::kw_auto) || isQualifier(Tok));
 }

 bool LeftRightQualifierAlignmentFixer::isConfiguredQualifierOrType(
     const FormatToken *Tok, const std::vector<tok::TokenKind> &Qualifiers,
     bool IsCpp) {
   return Tok && (Tok->isTypeName(IsCpp) || Tok->is(tok::kw_auto) ||
                  isConfiguredQualifier(Tok, Qualifiers));
 }

 // 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->isNot(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
	//===--- QualifierAlignmentFixer.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 QualifierAlignmentFixer, 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>
	#include <optional>

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

	namespace clang {
	namespace format {

	void addQualifierAlignmentFixerPasses(const FormatStyle &Style,
	SmallVectorImpl<AnalyzerPass> &Passes) {
	std::vector<std::string> LeftOrder;
	std::vector<std::string> RightOrder;
	std::vector<tok::TokenKind> ConfiguredQualifierTokens;
	prepareLeftRightOrderingForQualifierAlignmentFixer(
	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();
	});
	}
	}

	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) {
	auto Range = CharSourceRange::getCharRange(First->Tok.getLocation(),
	First->Tok.getEndLoc());

	std::string NewText{};
	NewText += First->TokenText;
	NewText += " " + Qualifier;
	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))
	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);
	}

	static bool
	isConfiguredQualifier(const FormatToken *const Tok,
	const std::vector<tok::TokenKind> &Qualifiers) {
	return Tok && llvm::is_contained(Qualifiers, Tok->Tok.getKind());
	}

	static bool isQualifier(const FormatToken *const Tok) {
	if (!Tok)
	return false;

	switch (Tok->Tok.getKind()) {
	case tok::kw_const:
	case tok::kw_volatile:
	case tok::kw_static:
	case tok::kw_inline:
	case tok::kw_constexpr:
	case tok::kw_restrict:
	case tok::kw_friend:
	return true;
	default:
	return false;
	}
	}

	const FormatToken *LeftRightQualifierAlignmentFixer::analyzeRight(
	const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
	tooling::Replacements &Fixes, const FormatToken *const Tok,
	const std::string &Qualifier, tok::TokenKind QualifierType) {
	// We only need to think about streams that begin with a qualifier.
	if (Tok->isNot(QualifierType))
	return Tok;
	// Don't concern yourself if nothing follows the qualifier.
	if (!Tok->Next)
	return Tok;

	// Skip qualifiers to the left to find what preceeds the qualifiers.
	// Use isQualifier rather than isConfiguredQualifier to cover all qualifiers.
	const FormatToken *PreviousCheck = Tok->getPreviousNonComment();
	while (isQualifier(PreviousCheck))
	PreviousCheck = PreviousCheck->getPreviousNonComment();

	// Examples given in order of ['type', 'const', 'volatile']
	const bool IsRightQualifier = PreviousCheck && [PreviousCheck]() {
	// The cases:
	// `Foo() const` -> `Foo() const`
	// `Foo() const final` -> `Foo() const final`
	// `Foo() const override` -> `Foo() const final`
	// `Foo() const volatile override` -> `Foo() const volatile override`
	// `Foo() volatile const final` -> `Foo() const volatile final`
	if (PreviousCheck->is(tok::r_paren))
	return true;

	// The cases:
	// `struct {} volatile const a;` -> `struct {} const volatile a;`
	// `class {} volatile const a;` -> `class {} const volatile a;`
	if (PreviousCheck->is(tok::r_brace))
	return true;

	// The case:
	// `template <class T> const Bar Foo()` ->
	// `template <class T> Bar const Foo()`
	// The cases:
	// `Foo<int> const foo` -> `Foo<int> const foo`
	// `Foo<int> volatile const` -> `Foo<int> const volatile`
	// The case:
	// ```
	// template <class T>
	// requires Concept1<T> && requires Concept2<T>
	// const Foo f();
	// ```
	// ->
	// ```
	// template <class T>
	// requires Concept1<T> && requires Concept2<T>
	// Foo const f();
	// ```
	if (PreviousCheck->is(TT_TemplateCloser)) {
	// If the token closes a template<> or requires clause, then it is a left
	// qualifier and should be moved to the right.
	return !(PreviousCheck->ClosesTemplateDeclaration \|\|
	PreviousCheck->ClosesRequiresClause);
	}

	// The case `Foo* const` -> `Foo* const`
	// The case `Foo* volatile const` -> `Foo* const volatile`
	// The case `int32_t const` -> `int32_t const`
	// The case `auto volatile const` -> `auto const volatile`
	if (PreviousCheck->isOneOf(TT_PointerOrReference, tok::identifier,
	tok::kw_auto)) {
	return true;
	}

	return false;
	}();

	// Find the last qualifier to the right.
	const FormatToken *LastQual = Tok;
	while (isQualifier(LastQual->getNextNonComment()))
	LastQual = LastQual->getNextNonComment();

	// If this qualifier is to the right of a type or pointer do a partial sort
	// and return.
	if (IsRightQualifier) {
	if (LastQual != Tok)
	rotateTokens(SourceMgr, Fixes, Tok, LastQual, /Left=/false);
	return Tok;
	}

	const FormatToken *TypeToken = LastQual->getNextNonComment();
	if (!TypeToken)
	return Tok;

	// Stay safe and don't move past macros, also don't bother with sorting.
	if (isPossibleMacro(TypeToken))
	return Tok;

	const bool IsCpp = Style.isCpp();

	// The case `const long long int volatile` -> `long long int const volatile`
	// The case `long const long int volatile` -> `long long int const volatile`
	// The case `long long volatile int const` -> `long long int const volatile`
	// The case `const long long volatile int` -> `long long int const volatile`
	if (TypeToken->isTypeName(IsCpp)) {
	// The case `const decltype(foo)` -> `const decltype(foo)`
	// The case `const typeof(foo)` -> `const typeof(foo)`
	// The case `const _Atomic(foo)` -> `const _Atomic(foo)`
	if (TypeToken->isOneOf(tok::kw_decltype, tok::kw_typeof, tok::kw__Atomic))
	return Tok;

	const FormatToken *LastSimpleTypeSpecifier = TypeToken;
	while (isQualifierOrType(LastSimpleTypeSpecifier->getNextNonComment(),
	IsCpp)) {
	LastSimpleTypeSpecifier = LastSimpleTypeSpecifier->getNextNonComment();
	}

	rotateTokens(SourceMgr, Fixes, Tok, LastSimpleTypeSpecifier,
	/Left=/false);
	return LastSimpleTypeSpecifier;
	}

	// The case `unsigned short const` -> `unsigned short const`
	// The case:
	// `unsigned short volatile const` -> `unsigned short const volatile`
	if (PreviousCheck && PreviousCheck->isTypeName(IsCpp)) {
	if (LastQual != Tok)
	rotateTokens(SourceMgr, Fixes, Tok, LastQual, /Left=/false);
	return Tok;
	}

	// Skip the typename keyword.
	// The case `const typename C::type` -> `typename C::type const`
	if (TypeToken->is(tok::kw_typename))
	TypeToken = TypeToken->getNextNonComment();

	// Skip the initial :: of a global-namespace type.
	// The case `const ::...` -> `::... const`
	if (TypeToken->is(tok::coloncolon)) {
	// The case `const ::template Foo...` -> `::template Foo... const`
	TypeToken = TypeToken->getNextNonComment();
	if (TypeToken && TypeToken->is(tok::kw_template))
	TypeToken = TypeToken->getNextNonComment();
	}

	// Don't change declarations such as
	// `foo(const struct Foo a);` -> `foo(const struct Foo a);`
	// as they would currently change code such as
	// `const struct my_struct_t {} my_struct;` -> `struct my_struct_t const {}
	// my_struct;`
	if (TypeToken->isOneOf(tok::kw_struct, tok::kw_class))
	return Tok;

	if (TypeToken->isOneOf(tok::kw_auto, tok::identifier)) {
	// The case `const auto` -> `auto 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 Foo &&` -> `Foo const &&`
	// The case `const std::Foo &&` -> `std::Foo const &&`
	// The case `const std::Foo<T> &&` -> `std::Foo<T> const &&`
	// The case `const ::template Foo` -> `::template Foo const`
	// The case `const T::template Foo` -> `T::template Foo const`
	const FormatToken *Next = nullptr;
	while ((Next = TypeToken->getNextNonComment()) &&
	(Next->is(TT_TemplateOpener) \|\|
	Next->startsSequence(tok::coloncolon, tok::identifier) \|\|
	Next->startsSequence(tok::coloncolon, tok::kw_template,
	tok::identifier))) {
	if (Next->is(TT_TemplateOpener)) {
	assert(Next->MatchingParen && "Missing template closer");
	TypeToken = Next->MatchingParen;
	} else if (Next->startsSequence(tok::coloncolon, tok::identifier)) {
	TypeToken = Next->getNextNonComment();
	} else {
	TypeToken = Next->getNextNonComment()->getNextNonComment();
	}
	}

	if (Next->is(tok::kw_auto))
	TypeToken = Next;

	// Place the Qualifier at the end of the list of qualifiers.
	while (isQualifier(TypeToken->getNextNonComment())) {
	// The case `volatile Foo::iter const` -> `Foo::iter const volatile`
	TypeToken = TypeToken->getNextNonComment();
	}

	insertQualifierAfter(SourceMgr, Fixes, TypeToken, Qualifier);
	// Remove token and following whitespace.
	auto Range = CharSourceRange::getCharRange(
	Tok->getStartOfNonWhitespace(), Tok->Next->getStartOfNonWhitespace());
	replaceToken(SourceMgr, Fixes, Range, "");
	}

	return Tok;
	}

	const FormatToken *LeftRightQualifierAlignmentFixer::analyzeLeft(
	const SourceManager &SourceMgr, const AdditionalKeywords &Keywords,
	tooling::Replacements &Fixes, const FormatToken *const Tok,
	const std::string &Qualifier, tok::TokenKind QualifierType) {
	// We only need to think about streams that begin with a qualifier.
	if (Tok->isNot(QualifierType))
	return Tok;
	// Don't concern yourself if nothing preceeds the qualifier.
	if (!Tok->getPreviousNonComment())
	return Tok;

	// Skip qualifiers to the left to find what preceeds the qualifiers.
	const FormatToken *TypeToken = Tok->getPreviousNonComment();
	while (isQualifier(TypeToken))
	TypeToken = TypeToken->getPreviousNonComment();

	// For left qualifiers preceeded by nothing, a template declaration, or *,&,&&
	// we only perform sorting.
	if (!TypeToken \|\| TypeToken->isPointerOrReference() \|\|
	TypeToken->ClosesRequiresClause \|\| TypeToken->ClosesTemplateDeclaration) {

	// Don't sort past a non-configured qualifier token.
	const FormatToken *FirstQual = Tok;
	while (isConfiguredQualifier(FirstQual->getPreviousNonComment(),
	ConfiguredQualifierTokens)) {
	FirstQual = FirstQual->getPreviousNonComment();
	}

	if (FirstQual != Tok)
	rotateTokens(SourceMgr, Fixes, FirstQual, Tok, /Left=/true);
	return Tok;
	}

	// Stay safe and don't move past macros, also don't bother with sorting.
	if (isPossibleMacro(TypeToken))
	return Tok;

	// Examples given in order of ['const', 'volatile', 'type']

	// The case `volatile long long int const` -> `const volatile long long int`
	// The case `volatile long long const int` -> `const volatile long long int`
	// The case `const long long volatile int` -> `const volatile long long int`
	// The case `long volatile long int const` -> `const volatile long long int`
	if (const bool IsCpp = Style.isCpp(); TypeToken->isTypeName(IsCpp)) {
	const FormatToken *LastSimpleTypeSpecifier = TypeToken;
	while (isConfiguredQualifierOrType(
	LastSimpleTypeSpecifier->getPreviousNonComment(),
	ConfiguredQualifierTokens, IsCpp)) {
	LastSimpleTypeSpecifier =
	LastSimpleTypeSpecifier->getPreviousNonComment();
	}

	rotateTokens(SourceMgr, Fixes, LastSimpleTypeSpecifier, Tok,
	/Left=/true);
	return Tok;
	}

	if (TypeToken->isOneOf(tok::kw_auto, tok::identifier, TT_TemplateCloser)) {
	const auto IsStartOfType = [](const FormatToken *const Tok) -> bool {
	if (!Tok)
	return true;

	// A template closer is not the start of a type.
	// The case `?<> const` -> `const ?<>`
	if (Tok->is(TT_TemplateCloser))
	return false;

	const FormatToken *const Previous = Tok->getPreviousNonComment();
	if (!Previous)
	return true;

	// An identifier preceeded by :: is not the start of a type.
	// The case `?::Foo const` -> `const ?::Foo`
	if (Tok->is(tok::identifier) && Previous->is(tok::coloncolon))
	return false;

	const FormatToken *const PrePrevious = Previous->getPreviousNonComment();
	// An identifier preceeded by ::template is not the start of a type.
	// The case `?::template Foo const` -> `const ?::template Foo`
	if (Tok->is(tok::identifier) && Previous->is(tok::kw_template) &&
	PrePrevious && PrePrevious->is(tok::coloncolon)) {
	return false;
	}

	if (Tok->endsSequence(tok::kw_auto, tok::identifier))
	return false;

	return true;
	};

	while (!IsStartOfType(TypeToken)) {
	// The case `?<>`
	if (TypeToken->is(TT_TemplateCloser)) {
	assert(TypeToken->MatchingParen && "Missing template opener");
	TypeToken = TypeToken->MatchingParen->getPreviousNonComment();
	} else {
	// The cases
	// `::Foo`
	// `?>::Foo`
	// `?Bar::Foo`
	// `::template Foo`
	// `?>::template Foo`
	// `?Bar::template Foo`
	if (TypeToken->getPreviousNonComment()->is(tok::kw_template))
	TypeToken = TypeToken->getPreviousNonComment();

	const FormatToken *const ColonColon =
	TypeToken->getPreviousNonComment();
	const FormatToken *const PreColonColon =
	ColonColon->getPreviousNonComment();
	if (PreColonColon &&
	PreColonColon->isOneOf(TT_TemplateCloser, tok::identifier)) {
	TypeToken = PreColonColon;
	} else {
	TypeToken = ColonColon;
	}
	}
	}

	assert(TypeToken && "Should be auto or identifier");

	// Place the Qualifier at the start of the list of qualifiers.
	const FormatToken *Previous = nullptr;
	while ((Previous = TypeToken->getPreviousNonComment()) &&
	(isConfiguredQualifier(Previous, ConfiguredQualifierTokens) \|\|
	Previous->is(tok::kw_typename))) {
	// The case `volatile Foo::iter const` -> `const volatile Foo::iter`
	// The case `typename C::type const` -> `const typename C::type`
	TypeToken = Previous;
	}

	// Don't change declarations such as
	// `foo(struct Foo const a);` -> `foo(struct Foo const a);`
	if (!Previous \|\| !Previous->isOneOf(tok::kw_struct, tok::kw_class)) {
	insertQualifierBefore(SourceMgr, Fixes, TypeToken, Qualifier);
	removeToken(SourceMgr, Fixes, Tok);
	}
	}

	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)
	.Case("friend", tok::kw_friend)
	.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;
	AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
	fixQualifierAlignment(AnnotatedLines, Tokens, Fixes);
	return {Fixes, 0};
	}

	void LeftRightQualifierAlignmentFixer::fixQualifierAlignment(
	SmallVectorImpl<AnnotatedLine *> &AnnotatedLines, FormatTokenLexer &Tokens,
	tooling::Replacements &Fixes) {
	const AdditionalKeywords &Keywords = Tokens.getKeywords();
	const SourceManager &SourceMgr = Env.getSourceManager();
	tok::TokenKind QualifierToken = getTokenFromQualifier(Qualifier);
	assert(QualifierToken != tok::identifier && "Unrecognised Qualifier");

	for (AnnotatedLine *Line : AnnotatedLines) {
	fixQualifierAlignment(Line->Children, Tokens, Fixes);
	if (!Line->Affected \|\| 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 != Last && Tok->Next;
	Tok = Tok->Next) {
	if (Tok->MustBreakBefore)
	break;
	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);
	}
	}
	}
	}

	void prepareLeftRightOrderingForQualifierAlignmentFixer(
	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,
	bool IsCpp) {
	return Tok &&
	(Tok->isTypeName(IsCpp) \|\| Tok->is(tok::kw_auto) \|\| isQualifier(Tok));
	}

	bool LeftRightQualifierAlignmentFixer::isConfiguredQualifierOrType(
	const FormatToken *Tok, const std::vector<tok::TokenKind> &Qualifiers,
	bool IsCpp) {
	return Tok && (Tok->isTypeName(IsCpp) \|\| Tok->is(tok::kw_auto) \|\|
	isConfiguredQualifier(Tok, Qualifiers));
	}

	// 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->isNot(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