//=== BuiltinFunctionChecker.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
//
//===----------------------------------------------------------------------===//
//
// This checker evaluates "standalone" clang builtin functions that are not
// just special-cased variants of well-known non-builtin functions.
// Builtin functions like __builtin_memcpy and __builtin_alloca should be
// evaluated by the same checker that handles their non-builtin variant to
// ensure that the two variants are handled consistently.
//
//===----------------------------------------------------------------------===//

#include "clang/Basic/Builtins.h"
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Checkers/Taint.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"

using namespace clang;
using namespace ento;
using namespace taint;

namespace {

QualType getSufficientTypeForOverflowOp(CheckerContext &C, const QualType &T) {
  // Calling a builtin with a non-integer type result produces compiler error.
  assert(T->isIntegerType());

  ASTContext &ACtx = C.getASTContext();
  unsigned BitWidth = ACtx.getIntWidth(T);
  return ACtx.getBitIntType(T->isUnsignedIntegerType(), BitWidth * 2);
}

QualType getOverflowBuiltinResultType(const CallEvent &Call) {
  // Calling a builtin with an incorrect argument count produces compiler error.
  assert(Call.getNumArgs() == 3);

  return Call.getArgExpr(2)->getType()->getPointeeType();
}

QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
                                      unsigned BI) {
  // Calling a builtin with an incorrect argument count produces compiler error.
  assert(Call.getNumArgs() == 3);

  ASTContext &ACtx = C.getASTContext();

  switch (BI) {
  case Builtin::BI__builtin_smul_overflow:
  case Builtin::BI__builtin_ssub_overflow:
  case Builtin::BI__builtin_sadd_overflow:
    return ACtx.IntTy;
  case Builtin::BI__builtin_smull_overflow:
  case Builtin::BI__builtin_ssubl_overflow:
  case Builtin::BI__builtin_saddl_overflow:
    return ACtx.LongTy;
  case Builtin::BI__builtin_smulll_overflow:
  case Builtin::BI__builtin_ssubll_overflow:
  case Builtin::BI__builtin_saddll_overflow:
    return ACtx.LongLongTy;
  case Builtin::BI__builtin_umul_overflow:
  case Builtin::BI__builtin_usub_overflow:
  case Builtin::BI__builtin_uadd_overflow:
    return ACtx.UnsignedIntTy;
  case Builtin::BI__builtin_umull_overflow:
  case Builtin::BI__builtin_usubl_overflow:
  case Builtin::BI__builtin_uaddl_overflow:
    return ACtx.UnsignedLongTy;
  case Builtin::BI__builtin_umulll_overflow:
  case Builtin::BI__builtin_usubll_overflow:
  case Builtin::BI__builtin_uaddll_overflow:
    return ACtx.UnsignedLongLongTy;
  case Builtin::BI__builtin_mul_overflow:
  case Builtin::BI__builtin_sub_overflow:
  case Builtin::BI__builtin_add_overflow:
    return getOverflowBuiltinResultType(Call);
  default:
    assert(false && "Unknown overflow builtin");
    return ACtx.IntTy;
  }
}

class BuiltinFunctionChecker : public Checker<eval::Call> {
public:
  bool evalCall(const CallEvent &Call, CheckerContext &C) const;
  void handleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
                             BinaryOperator::Opcode Op,
                             QualType ResultType) const;
  const NoteTag *createBuiltinOverflowNoteTag(CheckerContext &C,
                                              bool BothFeasible, SVal Arg1,
                                              SVal Arg2, SVal Result) const;
  ProgramStateRef initStateAftetBuiltinOverflow(CheckerContext &C,
                                                ProgramStateRef State,
                                                const CallEvent &Call,
                                                SVal RetCal,
                                                bool IsOverflow) const;
  std::pair<bool, bool> checkOverflow(CheckerContext &C, SVal RetVal,
                                      QualType Res) const;

private:
  // From: clang/include/clang/Basic/Builtins.def
  // C++ standard library builtins in namespace 'std'.
  const CallDescriptionSet BuiltinLikeStdFunctions{
      {CDM::SimpleFunc, {"std", "addressof"}},        //
      {CDM::SimpleFunc, {"std", "__addressof"}},      //
      {CDM::SimpleFunc, {"std", "as_const"}},         //
      {CDM::SimpleFunc, {"std", "forward"}},          //
      {CDM::SimpleFunc, {"std", "forward_like"}},     //
      {CDM::SimpleFunc, {"std", "move"}},             //
      {CDM::SimpleFunc, {"std", "move_if_noexcept"}}, //
  };

  bool isBuiltinLikeFunction(const CallEvent &Call) const;
};

} // namespace

const NoteTag *BuiltinFunctionChecker::createBuiltinOverflowNoteTag(
    CheckerContext &C, bool overflow, SVal Arg1, SVal Arg2, SVal Result) const {
  return C.getNoteTag([Result, Arg1, Arg2, overflow](PathSensitiveBugReport &BR,
                                                     llvm::raw_ostream &OS) {
    if (!BR.isInteresting(Result))
      return;

    // Propagate interestingness to input arguments if result is interesting.
    BR.markInteresting(Arg1);
    BR.markInteresting(Arg2);

    if (overflow)
      OS << "Assuming overflow";
    else
      OS << "Assuming no overflow";
  });
}

std::pair<bool, bool>
BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
                                      QualType Res) const {
  // Calling a builtin with a non-integer type result produces compiler error.
  assert(Res->isIntegerType());

  unsigned BitWidth = C.getASTContext().getIntWidth(Res);
  bool IsUnsigned = Res->isUnsignedIntegerType();

  SValBuilder &SVB = C.getSValBuilder();
  BasicValueFactory &VF = SVB.getBasicValueFactory();

  auto MinValType = llvm::APSInt::getMinValue(BitWidth, IsUnsigned);
  auto MaxValType = llvm::APSInt::getMaxValue(BitWidth, IsUnsigned);
  nonloc::ConcreteInt MinVal{VF.getValue(MinValType)};
  nonloc::ConcreteInt MaxVal{VF.getValue(MaxValType)};

  ProgramStateRef State = C.getState();
  SVal IsLeMax = SVB.evalBinOp(State, BO_LE, RetVal, MaxVal, Res);
  SVal IsGeMin = SVB.evalBinOp(State, BO_GE, RetVal, MinVal, Res);

  auto [MayNotOverflow, MayOverflow] =
      State->assume(IsLeMax.castAs<DefinedOrUnknownSVal>());
  auto [MayNotUnderflow, MayUnderflow] =
      State->assume(IsGeMin.castAs<DefinedOrUnknownSVal>());

  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
}

ProgramStateRef BuiltinFunctionChecker::initStateAftetBuiltinOverflow(
    CheckerContext &C, ProgramStateRef State, const CallEvent &Call,
    SVal RetVal, bool IsOverflow) const {
  SValBuilder &SVB = C.getSValBuilder();
  SVal Arg1 = Call.getArgSVal(0);
  SVal Arg2 = Call.getArgSVal(1);
  auto BoolTy = C.getASTContext().BoolTy;

  ProgramStateRef NewState =
      State->BindExpr(Call.getOriginExpr(), C.getStackFrame(),
                      SVB.makeTruthVal(IsOverflow, BoolTy));

  if (auto L = Call.getArgSVal(2).getAs<Loc>()) {
    NewState = NewState->bindLoc(*L, RetVal, C.getStackFrame());

    // Propagate taint if any of the arguments were tainted
    if (isTainted(State, Arg1) || isTainted(State, Arg2))
      NewState = addTaint(NewState, *L);
  }

  return NewState;
}

void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
                                                   CheckerContext &C,
                                                   BinaryOperator::Opcode Op,
                                                   QualType ResultType) const {
  // Calling a builtin with an incorrect argument count produces compiler error.
  assert(Call.getNumArgs() == 3);

  ProgramStateRef State = C.getState();
  SValBuilder &SVB = C.getSValBuilder();

  SVal Arg1 = Call.getArgSVal(0);
  SVal Arg2 = Call.getArgSVal(1);

  QualType SufficientlyWideTy = getSufficientTypeForOverflowOp(C, ResultType);
  assert(!SufficientlyWideTy.isNull());

  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2, SufficientlyWideTy);
  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);

  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);

  if (NotOverflow) {
    auto NewState =
        initStateAftetBuiltinOverflow(C, State, Call, RetVal, false);

    C.addTransition(NewState, createBuiltinOverflowNoteTag(
                                  C, /*overflow=*/false, Arg1, Arg2, RetVal));
  }

  if (Overflow) {
    auto NewState = initStateAftetBuiltinOverflow(C, State, Call, RetVal, true);

    C.addTransition(NewState, createBuiltinOverflowNoteTag(C, /*overflow=*/true,
                                                           Arg1, Arg2, RetVal));
  }
}

bool BuiltinFunctionChecker::isBuiltinLikeFunction(
    const CallEvent &Call) const {
  const auto *FD = llvm::dyn_cast_or_null<FunctionDecl>(Call.getDecl());
  if (!FD || FD->getNumParams() != 1)
    return false;

  if (QualType RetTy = FD->getReturnType();
      !RetTy->isPointerType() && !RetTy->isReferenceType())
    return false;

  if (QualType ParmTy = FD->getParamDecl(0)->getType();
      !ParmTy->isPointerType() && !ParmTy->isReferenceType())
    return false;

  return BuiltinLikeStdFunctions.contains(Call);
}

bool BuiltinFunctionChecker::evalCall(const CallEvent &Call,
                                      CheckerContext &C) const {
  ProgramStateRef state = C.getState();
  const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
  if (!FD)
    return false;

  const StackFrame *SF = C.getStackFrame();
  const Expr *CE = Call.getOriginExpr();

  if (isBuiltinLikeFunction(Call)) {
    C.addTransition(state->BindExpr(CE, SF, Call.getArgSVal(0)));
    return true;
  }

  unsigned BI = FD->getBuiltinID();

  switch (BI) {
  default:
    return false;
  case Builtin::BI__builtin_mul_overflow:
  case Builtin::BI__builtin_smul_overflow:
  case Builtin::BI__builtin_smull_overflow:
  case Builtin::BI__builtin_smulll_overflow:
  case Builtin::BI__builtin_umul_overflow:
  case Builtin::BI__builtin_umull_overflow:
  case Builtin::BI__builtin_umulll_overflow:
    handleOverflowBuiltin(Call, C, BO_Mul,
                          getOverflowBuiltinResultType(Call, C, BI));
    return true;
  case Builtin::BI__builtin_sub_overflow:
  case Builtin::BI__builtin_ssub_overflow:
  case Builtin::BI__builtin_ssubl_overflow:
  case Builtin::BI__builtin_ssubll_overflow:
  case Builtin::BI__builtin_usub_overflow:
  case Builtin::BI__builtin_usubl_overflow:
  case Builtin::BI__builtin_usubll_overflow:
    handleOverflowBuiltin(Call, C, BO_Sub,
                          getOverflowBuiltinResultType(Call, C, BI));
    return true;
  case Builtin::BI__builtin_add_overflow:
  case Builtin::BI__builtin_sadd_overflow:
  case Builtin::BI__builtin_saddl_overflow:
  case Builtin::BI__builtin_saddll_overflow:
  case Builtin::BI__builtin_uadd_overflow:
  case Builtin::BI__builtin_uaddl_overflow:
  case Builtin::BI__builtin_uaddll_overflow:
    handleOverflowBuiltin(Call, C, BO_Add,
                          getOverflowBuiltinResultType(Call, C, BI));
    return true;
  case Builtin::BI__builtin_unpredictable:
  case Builtin::BI__builtin_expect:
  case Builtin::BI__builtin_expect_with_probability:
  case Builtin::BI__builtin_assume_aligned:
  case Builtin::BI__builtin_addressof:
  case Builtin::BI__builtin_function_start: {
    // For __builtin_unpredictable, __builtin_expect,
    // __builtin_expect_with_probability and __builtin_assume_aligned,
    // just return the value of the subexpression.
    // __builtin_addressof is going from a reference to a pointer, but those
    // are represented the same way in the analyzer.
    assert (Call.getNumArgs() > 0);
    SVal Arg = Call.getArgSVal(0);
    C.addTransition(state->BindExpr(CE, SF, Arg));
    return true;
  }

  case Builtin::BI__builtin_dynamic_object_size:
  case Builtin::BI__builtin_object_size:
  case Builtin::BI__builtin_constant_p: {
    // This must be resolvable at compile time, so we defer to the constant
    // evaluator for a value.
    SValBuilder &SVB = C.getSValBuilder();
    SVal V = UnknownVal();
    Expr::EvalResult EVResult;
    if (CE->EvaluateAsInt(EVResult, C.getASTContext(), Expr::SE_NoSideEffects)) {
      // Make sure the result has the correct type.
      llvm::APSInt Result = EVResult.Val.getInt();
      BasicValueFactory &BVF = SVB.getBasicValueFactory();
      BVF.getAPSIntType(CE->getType()).apply(Result);
      V = SVB.makeIntVal(Result);
    }

    if (FD->getBuiltinID() == Builtin::BI__builtin_constant_p) {
      // If we didn't manage to figure out if the value is constant or not,
      // it is safe to assume that it's not constant and unsafe to assume
      // that it's constant.
      if (V.isUnknown())
        V = SVB.makeIntVal(0, CE->getType());
    }

    C.addTransition(state->BindExpr(CE, SF, V));
    return true;
  }
  }
}

void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) {
  mgr.registerChecker<BuiltinFunctionChecker>();
}

bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) {
  return true;
}