//===--- TooSmallLoopVariableCheck.cpp - clang-tidy -----------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "TooSmallLoopVariableCheck.h"
#include "clang/AST/ASTContext.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"

using namespace clang::ast_matchers;

namespace clang::tidy::bugprone {

static constexpr llvm::StringLiteral LoopName =
    llvm::StringLiteral("forLoopName");
static constexpr llvm::StringLiteral LoopVarName =
    llvm::StringLiteral("loopVar");
static constexpr llvm::StringLiteral LoopVarCastName =
    llvm::StringLiteral("loopVarCast");
static constexpr llvm::StringLiteral LoopUpperBoundName =
    llvm::StringLiteral("loopUpperBound");
static constexpr llvm::StringLiteral LoopIncrementName =
    llvm::StringLiteral("loopIncrement");

namespace {

struct MagnitudeBits {
  unsigned WidthWithoutSignBit = 0U;
  unsigned BitFieldWidth = 0U;

  bool operator<(const MagnitudeBits &Other) const noexcept {
    return WidthWithoutSignBit < Other.WidthWithoutSignBit;
  }

  bool operator!=(const MagnitudeBits &Other) const noexcept {
    return WidthWithoutSignBit != Other.WidthWithoutSignBit ||
           BitFieldWidth != Other.BitFieldWidth;
  }
};

} // namespace

TooSmallLoopVariableCheck::TooSmallLoopVariableCheck(StringRef Name,
                                                     ClangTidyContext *Context)
    : ClangTidyCheck(Name, Context),
      MagnitudeBitsUpperLimit(Options.get("MagnitudeBitsUpperLimit", 16U)) {}

void TooSmallLoopVariableCheck::storeOptions(
    ClangTidyOptions::OptionMap &Opts) {
  Options.store(Opts, "MagnitudeBitsUpperLimit", MagnitudeBitsUpperLimit);
}

/// The matcher for loops with suspicious integer loop variable.
///
/// In this general example, assuming 'j' and 'k' are of integral type:
/// \code
///   for (...; j < 3 + 2; ++k) { ... }
/// \endcode
/// The following string identifiers are bound to these parts of the AST:
///   LoopVarName: 'j' (as a VarDecl)
///   LoopVarCastName: 'j' (after implicit conversion)
///   LoopUpperBoundName: '3 + 2' (as an Expr)
///   LoopIncrementName: 'k' (as an Expr)
///   LoopName: The entire for loop (as a ForStmt)
///
void TooSmallLoopVariableCheck::registerMatchers(MatchFinder *Finder) {
  StatementMatcher LoopVarMatcher =
      expr(ignoringParenImpCasts(
               anyOf(declRefExpr(to(varDecl(hasType(isInteger())))),
                     memberExpr(member(fieldDecl(hasType(isInteger())))))))
          .bind(LoopVarName);

  // We need to catch only those comparisons which contain any integer cast.
  StatementMatcher LoopVarConversionMatcher = traverse(
      TK_AsIs, implicitCastExpr(hasImplicitDestinationType(isInteger()),
                                has(ignoringParenImpCasts(LoopVarMatcher)))
                   .bind(LoopVarCastName));

  // We are interested in only those cases when the loop bound is a variable
  // value (not const, enum, etc.).
  StatementMatcher LoopBoundMatcher =
      expr(ignoringParenImpCasts(allOf(
               hasType(isInteger()), unless(integerLiteral()),
               unless(allOf(
                   hasType(isConstQualified()),
                   declRefExpr(to(varDecl(anyOf(
                       hasInitializer(ignoringParenImpCasts(integerLiteral())),
                       isConstexpr(), isConstinit())))))),
               unless(hasType(enumType())))))
          .bind(LoopUpperBoundName);

  // We use the loop increment expression only to make sure we found the right
  // loop variable.
  StatementMatcher IncrementMatcher =
      expr(ignoringParenImpCasts(hasType(isInteger()))).bind(LoopIncrementName);

  Finder->addMatcher(
      forStmt(
          hasCondition(anyOf(
              binaryOperator(hasOperatorName("<"),
                             hasLHS(LoopVarConversionMatcher),
                             hasRHS(LoopBoundMatcher)),
              binaryOperator(hasOperatorName("<="),
                             hasLHS(LoopVarConversionMatcher),
                             hasRHS(LoopBoundMatcher)),
              binaryOperator(hasOperatorName(">"), hasLHS(LoopBoundMatcher),
                             hasRHS(LoopVarConversionMatcher)),
              binaryOperator(hasOperatorName(">="), hasLHS(LoopBoundMatcher),
                             hasRHS(LoopVarConversionMatcher)))),
          hasIncrement(IncrementMatcher))
          .bind(LoopName),
      this);
}

/// Returns the magnitude bits of an integer type.
static MagnitudeBits calcMagnitudeBits(const ASTContext &Context,
                                       const QualType &IntExprType,
                                       const Expr *IntExpr) {
  assert(IntExprType->isIntegerType());

  unsigned SignedBits = IntExprType->isUnsignedIntegerType() ? 0U : 1U;

  if (const auto *BitField = IntExpr->getSourceBitField()) {
    unsigned BitFieldWidth = BitField->getBitWidthValue(Context);
    return {BitFieldWidth - SignedBits, BitFieldWidth};
  }

  unsigned IntWidth = Context.getIntWidth(IntExprType);
  return {IntWidth - SignedBits, 0U};
}

/// Calculate the upper bound expression's magnitude bits, but ignore
/// constant like values to reduce false positives.
static MagnitudeBits
calcUpperBoundMagnitudeBits(const ASTContext &Context, const Expr *UpperBound,
                            const QualType &UpperBoundType) {
  // Ignore casting caused by constant values inside a binary operator.
  // We are interested in variable values' magnitude bits.
  if (const auto *BinOperator = dyn_cast<BinaryOperator>(UpperBound)) {
    const Expr *RHSE = BinOperator->getRHS()->IgnoreParenImpCasts();
    const Expr *LHSE = BinOperator->getLHS()->IgnoreParenImpCasts();

    QualType RHSEType = RHSE->getType();
    QualType LHSEType = LHSE->getType();

    if (!RHSEType->isIntegerType() || !LHSEType->isIntegerType())
      return {};

    bool RHSEIsConstantValue = RHSEType->isEnumeralType() ||
                               RHSEType.isConstQualified() ||
                               isa<IntegerLiteral>(RHSE);
    bool LHSEIsConstantValue = LHSEType->isEnumeralType() ||
                               LHSEType.isConstQualified() ||
                               isa<IntegerLiteral>(LHSE);

    // Avoid false positives produced by two constant values.
    if (RHSEIsConstantValue && LHSEIsConstantValue)
      return {};
    if (RHSEIsConstantValue)
      return calcMagnitudeBits(Context, LHSEType, LHSE);
    if (LHSEIsConstantValue)
      return calcMagnitudeBits(Context, RHSEType, RHSE);

    return std::max(calcMagnitudeBits(Context, LHSEType, LHSE),
                    calcMagnitudeBits(Context, RHSEType, RHSE));
  }

  return calcMagnitudeBits(Context, UpperBoundType, UpperBound);
}

static std::string formatIntegralType(const QualType &Type,
                                      const MagnitudeBits &Info) {
  std::string Name = Type.getAsString();
  if (!Info.BitFieldWidth)
    return Name;

  Name += ':';
  Name += std::to_string(Info.BitFieldWidth);
  return Name;
}

void TooSmallLoopVariableCheck::check(const MatchFinder::MatchResult &Result) {
  const auto *LoopVar = Result.Nodes.getNodeAs<Expr>(LoopVarName);
  const auto *UpperBound =
      Result.Nodes.getNodeAs<Expr>(LoopUpperBoundName)->IgnoreParenImpCasts();
  const auto *LoopIncrement =
      Result.Nodes.getNodeAs<Expr>(LoopIncrementName)->IgnoreParenImpCasts();

  // We matched the loop variable incorrectly.
  if (LoopVar->getType() != LoopIncrement->getType())
    return;

  ASTContext &Context = *Result.Context;

  const QualType LoopVarType = LoopVar->getType();
  const MagnitudeBits LoopVarMagnitudeBits =
      calcMagnitudeBits(Context, LoopVarType, LoopVar);

  const MagnitudeBits LoopIncrementMagnitudeBits =
      calcMagnitudeBits(Context, LoopIncrement->getType(), LoopIncrement);
  // We matched the loop variable incorrectly.
  if (LoopIncrementMagnitudeBits != LoopVarMagnitudeBits)
    return;

  const QualType UpperBoundType = UpperBound->getType();
  const MagnitudeBits UpperBoundMagnitudeBits =
      calcUpperBoundMagnitudeBits(Context, UpperBound, UpperBoundType);

  if ((0U == UpperBoundMagnitudeBits.WidthWithoutSignBit) ||
      (LoopVarMagnitudeBits.WidthWithoutSignBit > MagnitudeBitsUpperLimit) ||
      (LoopVarMagnitudeBits.WidthWithoutSignBit >=
       UpperBoundMagnitudeBits.WidthWithoutSignBit))
    return;

  diag(LoopVar->getBeginLoc(),
       "loop variable has narrower type '%0' than iteration's upper bound '%1'")
      << formatIntegralType(LoopVarType, LoopVarMagnitudeBits)
      << formatIntegralType(UpperBoundType, UpperBoundMagnitudeBits);
}

} // namespace clang::tidy::bugprone