//===- CastValueChecker - Model implementation of custom RTTIs --*- 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 defines CastValueChecker which models casts of custom RTTIs.

//

// TODO list:

// - It only allows one succesful cast between two types however in the wild

//   the object could be casted to multiple types.

// - It needs to check the most likely type information from the dynamic type

//   map to increase precision of dynamic casting.

//

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

#include "clang/AST/DeclTemplate.h"

#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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/DynamicType.h"

#include <optional>

#include <utility>

using namespace clang;

using namespace ento;

namespace {

class CastValueChecker : public Checker<check::DeadSymbols, eval::Call> {

  enum class CallKind { Function, Method, InstanceOf };

  using CastCheck =

      std::function<void(const CastValueChecker *, const CallEvent &Call,

                         DefinedOrUnknownSVal, CheckerContext &)>;

public:

  // We have five cases to evaluate a cast:

  // 1) The parameter is non-null, the return value is non-null.

  // 2) The parameter is non-null, the return value is null.

  // 3) The parameter is null, the return value is null.

  // cast: 1;  dyn_cast: 1, 2;  cast_or_null: 1, 3;  dyn_cast_or_null: 1, 2, 3.

  //

  // 4) castAs: Has no parameter, the return value is non-null.

  // 5) getAs:  Has no parameter, the return value is null or non-null.

  //

  // We have two cases to check the parameter is an instance of the given type.

  // 1) isa:             The parameter is non-null, returns boolean.

  // 2) isa_and_nonnull: The parameter is null or non-null, returns boolean.

  bool evalCall(const CallEvent &Call, CheckerContext &C) const;

  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;

private:

  // These are known in the LLVM project. The pairs are in the following form:

  // {{{namespace, call}, argument-count}, {callback, kind}}

  const CallDescriptionMap<std::pair<CastCheck, CallKind>> CDM = {

      {{{"llvm", "cast"}, 1},

       {&CastValueChecker::evalCast, CallKind::Function}},

      {{{"llvm", "dyn_cast"}, 1},

       {&CastValueChecker::evalDynCast, CallKind::Function}},

      {{{"llvm", "cast_or_null"}, 1},

       {&CastValueChecker::evalCastOrNull, CallKind::Function}},

      {{{"llvm", "dyn_cast_or_null"}, 1},

       {&CastValueChecker::evalDynCastOrNull, CallKind::Function}},

      {{{"clang", "castAs"}, 0},

       {&CastValueChecker::evalCastAs, CallKind::Method}},

      {{{"clang", "getAs"}, 0},

       {&CastValueChecker::evalGetAs, CallKind::Method}},

      {{{"llvm", "isa"}, 1},

       {&CastValueChecker::evalIsa, CallKind::InstanceOf}},

      {{{"llvm", "isa_and_nonnull"}, 1},

       {&CastValueChecker::evalIsaAndNonNull, CallKind::InstanceOf}}};

  void evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,

                CheckerContext &C) const;

  void evalDynCast(const CallEvent &Call, DefinedOrUnknownSVal DV,

                   CheckerContext &C) const;

  void evalCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,

                      CheckerContext &C) const;

  void evalDynCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,

                         CheckerContext &C) const;

  void evalCastAs(const CallEvent &Call, DefinedOrUnknownSVal DV,

                  CheckerContext &C) const;

  void evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,

                 CheckerContext &C) const;

  void evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,

               CheckerContext &C) const;

  void evalIsaAndNonNull(const CallEvent &Call, DefinedOrUnknownSVal DV,

                         CheckerContext &C) const;

};

} // namespace

static bool isInfeasibleCast(const DynamicCastInfo *CastInfo,

                             bool CastSucceeds) {

  if (!CastInfo)

    return false;

  return CastSucceeds ? 
CastInfo->fails()18
 : 
CastInfo->succeeds()18
;

}

static const NoteTag *getNoteTag(CheckerContext &C,

                                 const DynamicCastInfo *CastInfo,

                                 QualType CastToTy, const Expr *Object,

                                 bool CastSucceeds, bool IsKnownCast) {

  std::string CastToName =

      CastInfo ? 
CastInfo->to()->getAsCXXRecordDecl()->getNameAsString()36

               : 
CastToTy.getAsString()362
;

  Object = Object->IgnoreParenImpCasts();

  return C.getNoteTag(

      [=]() -> std::string {

        SmallString<128> Msg;

        llvm::raw_svector_ostream Out(Msg);

        if (!IsKnownCast)

          Out << "Assuming ";

        if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {

          Out << '\'' << DRE->getDecl()->getDeclName() << '\'';

        } else 
if (const auto *0
ME0
 = dyn_cast<MemberExpr>(Object)) {

          Out << (IsKnownCast ? "Field '" : "field '")

              << ME->getMemberDecl()->getDeclName() << '\'';

        } else {

          Out << (IsKnownCast ? "The object" : "the object");

        }

        Out << ' ' << (CastSucceeds ? 
"is a"95
 : 
"is not a"89
) << " '" << CastToName

            << '\'';

        return std::string(Out.str());

      },

      /*IsPrunable=*/true);

}

static const NoteTag *getNoteTag(CheckerContext &C,

                                 SmallVector<QualType, 4> CastToTyVec,

                                 const Expr *Object,

                                 bool IsKnownCast) {

  Object = Object->IgnoreParenImpCasts();

  return C.getNoteTag(

      [=]() -> std::string {

        SmallString<128> Msg;

        llvm::raw_svector_ostream Out(Msg);

        if (!IsKnownCast)

          Out << "Assuming ";

        if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {

          Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';

        } else 
if (const auto *0
ME0
 = dyn_cast<MemberExpr>(Object)) {

          Out << (IsKnownCast ? "Field '" : "field '")

              << ME->getMemberDecl()->getNameAsString() << '\'';

        } else {

          Out << (IsKnownCast ? "The object" : "the object");

        }

        Out << " is";

        bool First = true;

        for (QualType CastToTy: CastToTyVec) {

          std::string CastToName =

              CastToTy->getAsCXXRecordDecl()

                  ? CastToTy->getAsCXXRecordDecl()->getNameAsString()

                  : 
CastToTy.getAsString()0
;

          Out << ' ' << ((CastToTyVec.size() == 1) ? 
"not"20
 :

                         
(96
First96
 ? 
"neither"38
 : 
"nor"58
)) << " a '" << CastToName

              << '\'';

          First = false;

        }

        return std::string(Out.str());

      },

      /*IsPrunable=*/true);

}

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

// Main logic to evaluate a cast.

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

static QualType alignReferenceTypes(QualType toAlign, QualType alignTowards,

                                    ASTContext &ACtx) {

  if (alignTowards->isLValueReferenceType() &&

      alignTowards.isConstQualified()) {

    toAlign.addConst();

    return ACtx.getLValueReferenceType(toAlign);

  } else if (alignTowards->isLValueReferenceType())

    return ACtx.getLValueReferenceType(toAlign);

  else if (alignTowards->isRValueReferenceType())

    return ACtx.getRValueReferenceType(toAlign);

  llvm_unreachable("Must align towards a reference type!");

}

static void addCastTransition(const CallEvent &Call, DefinedOrUnknownSVal DV,

                              CheckerContext &C, bool IsNonNullParam,

                              bool IsNonNullReturn,

                              bool IsCheckedCast = false) {

  ProgramStateRef State = C.getState()->assume(DV, IsNonNullParam);

  if (!State)

    return;

  const Expr *Object;

  QualType CastFromTy;

  QualType CastToTy = Call.getResultType();

  if (Call.getNumArgs() > 0) {

    Object = Call.getArgExpr(0);

    CastFromTy = Call.parameters()[0]->getType();

  } else {

    Object = cast<CXXInstanceCall>(&Call)->getCXXThisExpr();

    CastFromTy = Object->getType();

    if (CastToTy->isPointerType()) {

      if (!CastFromTy->isPointerType())

        return;

    } else {

      if (!CastFromTy->isReferenceType())

        return;

      CastFromTy = alignReferenceTypes(CastFromTy, CastToTy, C.getASTContext());

    }

  }

  const MemRegion *MR = DV.getAsRegion();

  const DynamicCastInfo *CastInfo =

      getDynamicCastInfo(State, MR, CastFromTy, CastToTy);

  // We assume that every checked cast succeeds.

  bool CastSucceeds = IsCheckedCast || 
CastFromTy == CastToTy351
;

  if (!CastSucceeds) {

    if (CastInfo)

      CastSucceeds = IsNonNullReturn && 
CastInfo->succeeds()18
;

    else

      CastSucceeds = IsNonNullReturn;

  }

  // Check for infeasible casts.

  if (isInfeasibleCast(CastInfo, CastSucceeds)) {

    C.generateSink(State, C.getPredecessor());

    return;

  }

  // Store the type and the cast information.

  bool IsKnownCast = CastInfo || 
IsCheckedCast336
 || 
CastFromTy == CastToTy315
;

  if (!IsKnownCast || 
IsCheckedCast39
)

    State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,

                                      CastSucceeds);

  SVal V = CastSucceeds ? 
C.getSValBuilder().evalCast(DV, CastToTy, CastFromTy)197

                        : 
C.getSValBuilder().makeNullWithType(CastToTy)157
;

  C.addTransition(

      State->BindExpr(Call.getOriginExpr(), C.getLocationContext(), V, false),

      getNoteTag(C, CastInfo, CastToTy, Object, CastSucceeds, IsKnownCast));

}

static void addInstanceOfTransition(const CallEvent &Call,

                                    DefinedOrUnknownSVal DV,

                                    ProgramStateRef State, CheckerContext &C,

                                    bool IsInstanceOf) {

  const FunctionDecl *FD = Call.getDecl()->getAsFunction();

  QualType CastFromTy = Call.parameters()[0]->getType();

  SmallVector<QualType, 4> CastToTyVec;

  for (unsigned idx = 0; idx < FD->getTemplateSpecializationArgs()->size() - 1;

       ++idx) {

    TemplateArgument CastToTempArg =

      FD->getTemplateSpecializationArgs()->get(idx);

    switch (CastToTempArg.getKind()) {

    default:

      return;

    case TemplateArgument::Type:

      CastToTyVec.push_back(CastToTempArg.getAsType());

      break;

    case TemplateArgument::Pack:

      for (TemplateArgument ArgInPack: CastToTempArg.pack_elements())

        CastToTyVec.push_back(ArgInPack.getAsType());

      break;

    }

  }

  const MemRegion *MR = DV.getAsRegion();

  if (MR && CastFromTy->isReferenceType())

    MR = State->getSVal(DV.castAs<Loc>()).getAsRegion();

  bool Success = false;

  bool IsAnyKnown = false;

  for (QualType CastToTy: CastToTyVec) {

    if (CastFromTy->isPointerType())

      CastToTy = C.getASTContext().getPointerType(CastToTy);

    else if (CastFromTy->isReferenceType())

      CastToTy = alignReferenceTypes(CastToTy, CastFromTy, C.getASTContext());

    else

      return;

    const DynamicCastInfo *CastInfo =

      getDynamicCastInfo(State, MR, CastFromTy, CastToTy);

    bool CastSucceeds;

    if (CastInfo)

      CastSucceeds = IsInstanceOf && 
CastInfo->succeeds()126
;

    else

      CastSucceeds = IsInstanceOf || 
CastFromTy == CastToTy26
;

    // Store the type and the cast information.

    bool IsKnownCast = CastInfo || 
CastFromTy == CastToTy52
;

    IsAnyKnown = IsAnyKnown || 
IsKnownCast196
;

    ProgramStateRef NewState = State;

    if (!IsKnownCast)

      NewState = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,

                                           IsInstanceOf);

    if (CastSucceeds) {

      Success = true;

      C.addTransition(

          NewState->BindExpr(Call.getOriginExpr(), C.getLocationContext(),

                             C.getSValBuilder().makeTruthVal(true)),

          getNoteTag(C, CastInfo, CastToTy, Call.getArgExpr(0), true,

                     IsKnownCast));

      if (IsKnownCast)

        return;

    } else if (CastInfo && 
CastInfo->succeeds()234
) {

      C.generateSink(NewState, C.getPredecessor());

      return;

    }

  }

  if (!Success) {

    C.addTransition(

        State->BindExpr(Call.getOriginExpr(), C.getLocationContext(),

                        C.getSValBuilder().makeTruthVal(false)),

        getNoteTag(C, CastToTyVec, Call.getArgExpr(0), IsAnyKnown));

  }

}

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

// Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.

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

static void evalNonNullParamNonNullReturn(const CallEvent &Call,

                                          DefinedOrUnknownSVal DV,

                                          CheckerContext &C,

                                          bool IsCheckedCast = false) {

  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,

                    /*IsNonNullReturn=*/true, IsCheckedCast);

}

static void evalNonNullParamNullReturn(const CallEvent &Call,

                                       DefinedOrUnknownSVal DV,

                                       CheckerContext &C) {

  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,

                    /*IsNonNullReturn=*/false);

}

static void evalNullParamNullReturn(const CallEvent &Call,

                                    DefinedOrUnknownSVal DV,

                                    CheckerContext &C) {

  if (ProgramStateRef State = C.getState()->assume(DV, false))

    C.addTransition(State->BindExpr(Call.getOriginExpr(),

                                    C.getLocationContext(),

                                    C.getSValBuilder().makeNullWithType(

                                        Call.getOriginExpr()->getType()),

                                    false),

                    C.getNoteTag("Assuming null pointer is passed into cast",

                                 /*IsPrunable=*/true));

}

void CastValueChecker::evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,

                                CheckerContext &C) const {

  evalNonNullParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);

}

void CastValueChecker::evalDynCast(const CallEvent &Call,

                                   DefinedOrUnknownSVal DV,

                                   CheckerContext &C) const {

  evalNonNullParamNonNullReturn(Call, DV, C);

  evalNonNullParamNullReturn(Call, DV, C);

}

void CastValueChecker::evalCastOrNull(const CallEvent &Call,

                                      DefinedOrUnknownSVal DV,

                                      CheckerContext &C) const {

  evalNonNullParamNonNullReturn(Call, DV, C);

  evalNullParamNullReturn(Call, DV, C);

}

void CastValueChecker::evalDynCastOrNull(const CallEvent &Call,

                                         DefinedOrUnknownSVal DV,

                                         CheckerContext &C) const {

  evalNonNullParamNonNullReturn(Call, DV, C);

  evalNonNullParamNullReturn(Call, DV, C);

  evalNullParamNullReturn(Call, DV, C);

}

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

// Evaluating castAs, getAs.

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

static void evalZeroParamNonNullReturn(const CallEvent &Call,

                                       DefinedOrUnknownSVal DV,

                                       CheckerContext &C,

                                       bool IsCheckedCast = false) {

  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,

                    /*IsNonNullReturn=*/true, IsCheckedCast);

}

static void evalZeroParamNullReturn(const CallEvent &Call,

                                    DefinedOrUnknownSVal DV,

                                    CheckerContext &C) {

  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,

                    /*IsNonNullReturn=*/false);

}

void CastValueChecker::evalCastAs(const CallEvent &Call,

                                  DefinedOrUnknownSVal DV,

                                  CheckerContext &C) const {

  evalZeroParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);

}

void CastValueChecker::evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,

                                 CheckerContext &C) const {

  evalZeroParamNonNullReturn(Call, DV, C);

  evalZeroParamNullReturn(Call, DV, C);

}

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

// Evaluating isa, isa_and_nonnull.

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

void CastValueChecker::evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,

                               CheckerContext &C) const {

  ProgramStateRef NonNullState, NullState;

  std::tie(NonNullState, NullState) = C.getState()->assume(DV);

  if (NonNullState) {

    addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/true);

    addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/false);

  }

  if (NullState) {

    C.generateSink(NullState, C.getPredecessor());

  }

}

void CastValueChecker::evalIsaAndNonNull(const CallEvent &Call,

                                         DefinedOrUnknownSVal DV,

                                         CheckerContext &C) const {

  ProgramStateRef NonNullState, NullState;

  std::tie(NonNullState, NullState) = C.getState()->assume(DV);

  if (NonNullState) {

    addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/true);

    addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/false);

  }

  if (NullState) {

    addInstanceOfTransition(Call, DV, NullState, C, /*IsInstanceOf=*/false);

  }

}

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

// Main logic to evaluate a call.

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

bool CastValueChecker::evalCall(const CallEvent &Call,

                                CheckerContext &C) const {

  const auto *Lookup = CDM.lookup(Call);

  if (!Lookup)

    return false;

  const CastCheck &Check = Lookup->first;

  CallKind Kind = Lookup->second;

  std::optional<DefinedOrUnknownSVal> DV;

  switch (Kind) {

  case CallKind::Function: {

    // We only model casts from pointers to pointers or from references

    // to references. Other casts are most likely specialized and we

    // cannot model them.

    QualType ParamT = Call.parameters()[0]->getType();

    QualType ResultT = Call.getResultType();

    if (!(ParamT->isPointerType() && 
ResultT->isPointerType()173
) &&

        
!(25
ParamT->isReferenceType()25
 && 
ResultT->isReferenceType()24
)) {

      return false;

    }

    DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();

    break;

  }

  case CallKind::InstanceOf: {

    // We need to obtain the only template argument to determinte the type.

    const FunctionDecl *FD = Call.getDecl()->getAsFunction();

    if (!FD || !FD->getTemplateSpecializationArgs())

      return false;

    DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();

    break;

  }

  case CallKind::Method:

    const auto *InstanceCall = dyn_cast<CXXInstanceCall>(&Call);

    if (!InstanceCall)

      return false;

    DV = InstanceCall->getCXXThisVal().getAs<DefinedOrUnknownSVal>();

    break;

  }

  if (!DV)

    return false;

  Check(this, Call, *DV, C);

  return true;

}

void CastValueChecker::checkDeadSymbols(SymbolReaper &SR,

                                        CheckerContext &C) const {

  C.addTransition(removeDeadCasts(C.getState(), SR));

}

void ento::registerCastValueChecker(CheckerManager &Mgr) {

  Mgr.registerChecker<CastValueChecker>();

}

bool ento::shouldRegisterCastValueChecker(const CheckerManager &mgr) {

  return true;

}