clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

   1 //===- SValBuilder.cpp - Basic class for all SValBuilder implementations --===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines SValBuilder, the base class for all (complete) SValBuilder
  10 //  implementations.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  15 #include "clang/AST/ASTContext.h"
  16 #include "clang/AST/Decl.h"
  17 #include "clang/AST/DeclCXX.h"
  18 #include "clang/AST/ExprCXX.h"
  19 #include "clang/AST/ExprObjC.h"
  20 #include "clang/AST/Stmt.h"
  21 #include "clang/AST/Type.h"
  22 #include "clang/Analysis/AnalysisDeclContext.h"
  23 #include "clang/Basic/LLVM.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
  27 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  28 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  29 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  30 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
  31 #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
  32 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  33 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  34 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
  35 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
  36 #include "llvm/ADT/APSInt.h"
  37 #include "llvm/Support/Casting.h"
  38 #include "llvm/Support/Compiler.h"
  39 #include <cassert>
  40 #include <optional>
  41 #include <tuple>
  42
  43 using namespace clang;
  44 using namespace ento;
  45
  46 //===----------------------------------------------------------------------===//
  47 // Basic SVal creation.
  48 //===----------------------------------------------------------------------===//
  49
  50 void SValBuilder::anchor() {}
  51
  52 SValBuilder::SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
  53                          ProgramStateManager &stateMgr)
  54     : Context(context), BasicVals(context, alloc),
  55       SymMgr(context, BasicVals, alloc), MemMgr(context, alloc),
  56       StateMgr(stateMgr),
  57       AnOpts(
  58           stateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions()),
  59       ArrayIndexTy(context.LongLongTy),
  60       ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {}
  61
  62 DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) {
  63   if (Loc::isLocType(type))
  64     return makeNullWithType(type);
  65
  66   if (type->isIntegralOrEnumerationType())
  67     return makeIntVal(0, type);
  68
  69   if (type->isArrayType() || type->isRecordType() || type->isVectorType() ||
  70       type->isAnyComplexType())
  71     return makeCompoundVal(type, BasicVals.getEmptySValList());
  72
  73   // FIXME: Handle floats.
  74   return UnknownVal();
  75 }
  76
  77 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs,
  78                                           BinaryOperator::Opcode op,
  79                                           const llvm::APSInt &rhs,
  80                                           QualType type) {
  81   // The Environment ensures we always get a persistent APSInt in
  82   // BasicValueFactory, so we don't need to get the APSInt from
  83   // BasicValueFactory again.
  84   assert(lhs);
  85   assert(!Loc::isLocType(type));
  86   return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type));
  87 }
  88
  89 nonloc::SymbolVal SValBuilder::makeNonLoc(const llvm::APSInt &lhs,
  90                                           BinaryOperator::Opcode op,
  91                                           const SymExpr *rhs, QualType type) {
  92   assert(rhs);
  93   assert(!Loc::isLocType(type));
  94   return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type));
  95 }
  96
  97 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs,
  98                                           BinaryOperator::Opcode op,
  99                                           const SymExpr *rhs, QualType type) {
 100   assert(lhs && rhs);
 101   assert(!Loc::isLocType(type));
 102   return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type));
 103 }
 104
 105 NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op,
 106                                QualType type) {
 107   assert(operand);
 108   assert(!Loc::isLocType(type));
 109   return nonloc::SymbolVal(SymMgr.getUnarySymExpr(operand, op, type));
 110 }
 111
 112 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *operand,
 113                                           QualType fromTy, QualType toTy) {
 114   assert(operand);
 115   assert(!Loc::isLocType(toTy));
 116   if (fromTy == toTy)
 117     return operand;
 118   return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy));
 119 }
 120
 121 SVal SValBuilder::convertToArrayIndex(SVal val) {
 122   if (val.isUnknownOrUndef())
 123     return val;
 124
 125   // Common case: we have an appropriately sized integer.
 126   if (std::optional<nonloc::ConcreteInt> CI =
 127           val.getAs<nonloc::ConcreteInt>()) {
 128     const llvm::APSInt& I = CI->getValue();
 129     if (I.getBitWidth() == ArrayIndexWidth && I.isSigned())
 130       return val;
 131   }
 132
 133   return evalCast(val, ArrayIndexTy, QualType{});
 134 }
 135
 136 nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){
 137   return makeTruthVal(boolean->getValue());
 138 }
 139
 140 DefinedOrUnknownSVal
 141 SValBuilder::getRegionValueSymbolVal(const TypedValueRegion *region) {
 142   QualType T = region->getValueType();
 143
 144   if (T->isNullPtrType())
 145     return makeZeroVal(T);
 146
 147   if (!SymbolManager::canSymbolicate(T))
 148     return UnknownVal();
 149
 150   SymbolRef sym = SymMgr.getRegionValueSymbol(region);
 151
 152   if (Loc::isLocType(T))
 153     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 154
 155   return nonloc::SymbolVal(sym);
 156 }
 157
 158 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *SymbolTag,
 159                                                    const Expr *Ex,
 160                                                    const LocationContext *LCtx,
 161                                                    unsigned Count) {
 162   QualType T = Ex->getType();
 163
 164   if (T->isNullPtrType())
 165     return makeZeroVal(T);
 166
 167   // Compute the type of the result. If the expression is not an R-value, the
 168   // result should be a location.
 169   QualType ExType = Ex->getType();
 170   if (Ex->isGLValue())
 171     T = LCtx->getAnalysisDeclContext()->getASTContext().getPointerType(ExType);
 172
 173   return conjureSymbolVal(SymbolTag, Ex, LCtx, T, Count);
 174 }
 175
 176 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag,
 177                                                    const Expr *expr,
 178                                                    const LocationContext *LCtx,
 179                                                    QualType type,
 180                                                    unsigned count) {
 181   if (type->isNullPtrType())
 182     return makeZeroVal(type);
 183
 184   if (!SymbolManager::canSymbolicate(type))
 185     return UnknownVal();
 186
 187   SymbolRef sym = SymMgr.conjureSymbol(expr, LCtx, type, count, symbolTag);
 188
 189   if (Loc::isLocType(type))
 190     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 191
 192   return nonloc::SymbolVal(sym);
 193 }
 194
 195 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const Stmt *stmt,
 196                                                    const LocationContext *LCtx,
 197                                                    QualType type,
 198                                                    unsigned visitCount) {
 199   if (type->isNullPtrType())
 200     return makeZeroVal(type);
 201
 202   if (!SymbolManager::canSymbolicate(type))
 203     return UnknownVal();
 204
 205   SymbolRef sym = SymMgr.conjureSymbol(stmt, LCtx, type, visitCount);
 206
 207   if (Loc::isLocType(type))
 208     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 209
 210   return nonloc::SymbolVal(sym);
 211 }
 212
 213 DefinedOrUnknownSVal
 214 SValBuilder::getConjuredHeapSymbolVal(const Expr *E,
 215                                       const LocationContext *LCtx,
 216                                       unsigned VisitCount) {
 217   QualType T = E->getType();
 218   return getConjuredHeapSymbolVal(E, LCtx, T, VisitCount);
 219 }
 220
 221 DefinedOrUnknownSVal
 222 SValBuilder::getConjuredHeapSymbolVal(const Expr *E,
 223                                       const LocationContext *LCtx,
 224                                       QualType type, unsigned VisitCount) {
 225   assert(Loc::isLocType(type));
 226   assert(SymbolManager::canSymbolicate(type));
 227   if (type->isNullPtrType())
 228     return makeZeroVal(type);
 229
 230   SymbolRef sym = SymMgr.conjureSymbol(E, LCtx, type, VisitCount);
 231   return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym));
 232 }
 233
 234 DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag,
 235                                               const MemRegion *region,
 236                                               const Expr *expr, QualType type,
 237                                               const LocationContext *LCtx,
 238                                               unsigned count) {
 239   assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type");
 240
 241   SymbolRef sym =
 242       SymMgr.getMetadataSymbol(region, expr, type, LCtx, count, symbolTag);
 243
 244   if (Loc::isLocType(type))
 245     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 246
 247   return nonloc::SymbolVal(sym);
 248 }
 249
 250 DefinedOrUnknownSVal
 251 SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol,
 252                                              const TypedValueRegion *region) {
 253   QualType T = region->getValueType();
 254
 255   if (T->isNullPtrType())
 256     return makeZeroVal(T);
 257
 258   if (!SymbolManager::canSymbolicate(T))
 259     return UnknownVal();
 260
 261   SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region);
 262
 263   if (Loc::isLocType(T))
 264     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 265
 266   return nonloc::SymbolVal(sym);
 267 }
 268
 269 DefinedSVal SValBuilder::getMemberPointer(const NamedDecl *ND) {
 270   assert(!ND || (isa<CXXMethodDecl, FieldDecl, IndirectFieldDecl>(ND)));
 271
 272   if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(ND)) {
 273     // Sema treats pointers to static member functions as have function pointer
 274     // type, so return a function pointer for the method.
 275     // We don't need to play a similar trick for static member fields
 276     // because these are represented as plain VarDecls and not FieldDecls
 277     // in the AST.
 278     if (!MD->isImplicitObjectMemberFunction())
 279       return getFunctionPointer(MD);
 280   }
 281
 282   return nonloc::PointerToMember(ND);
 283 }
 284
 285 DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) {
 286   return loc::MemRegionVal(MemMgr.getFunctionCodeRegion(func));
 287 }
 288
 289 DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block,
 290                                          CanQualType locTy,
 291                                          const LocationContext *locContext,
 292                                          unsigned blockCount) {
 293   const BlockCodeRegion *BC =
 294     MemMgr.getBlockCodeRegion(block, locTy, locContext->getAnalysisDeclContext());
 295   const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext,
 296                                                         blockCount);
 297   return loc::MemRegionVal(BD);
 298 }
 299
 300 std::optional<loc::MemRegionVal>
 301 SValBuilder::getCastedMemRegionVal(const MemRegion *R, QualType Ty) {
 302   if (auto OptR = StateMgr.getStoreManager().castRegion(R, Ty))
 303     return loc::MemRegionVal(*OptR);
 304   return std::nullopt;
 305 }
 306
 307 /// Return a memory region for the 'this' object reference.
 308 loc::MemRegionVal SValBuilder::getCXXThis(const CXXMethodDecl *D,
 309                                           const StackFrameContext *SFC) {
 310   return loc::MemRegionVal(
 311       getRegionManager().getCXXThisRegion(D->getThisType(), SFC));
 312 }
 313
 314 /// Return a memory region for the 'this' object reference.
 315 loc::MemRegionVal SValBuilder::getCXXThis(const CXXRecordDecl *D,
 316                                           const StackFrameContext *SFC) {
 317   const Type *T = D->getTypeForDecl();
 318   QualType PT = getContext().getPointerType(QualType(T, 0));
 319   return loc::MemRegionVal(getRegionManager().getCXXThisRegion(PT, SFC));
 320 }
 321
 322 std::optional<SVal> SValBuilder::getConstantVal(const Expr *E) {
 323   E = E->IgnoreParens();
 324
 325   switch (E->getStmtClass()) {
 326   // Handle expressions that we treat differently from the AST's constant
 327   // evaluator.
 328   case Stmt::AddrLabelExprClass:
 329     return makeLoc(cast<AddrLabelExpr>(E));
 330
 331   case Stmt::CXXScalarValueInitExprClass:
 332   case Stmt::ImplicitValueInitExprClass:
 333     return makeZeroVal(E->getType());
 334
 335   case Stmt::ObjCStringLiteralClass: {
 336     const auto *SL = cast<ObjCStringLiteral>(E);
 337     return makeLoc(getRegionManager().getObjCStringRegion(SL));
 338   }
 339
 340   case Stmt::StringLiteralClass: {
 341     const auto *SL = cast<StringLiteral>(E);
 342     return makeLoc(getRegionManager().getStringRegion(SL));
 343   }
 344
 345   case Stmt::PredefinedExprClass: {
 346     const auto *PE = cast<PredefinedExpr>(E);
 347     assert(PE->getFunctionName() &&
 348            "Since we analyze only instantiated functions, PredefinedExpr "
 349            "should have a function name.");
 350     return makeLoc(getRegionManager().getStringRegion(PE->getFunctionName()));
 351   }
 352
 353   // Fast-path some expressions to avoid the overhead of going through the AST's
 354   // constant evaluator
 355   case Stmt::CharacterLiteralClass: {
 356     const auto *C = cast<CharacterLiteral>(E);
 357     return makeIntVal(C->getValue(), C->getType());
 358   }
 359
 360   case Stmt::CXXBoolLiteralExprClass:
 361     return makeBoolVal(cast<CXXBoolLiteralExpr>(E));
 362
 363   case Stmt::TypeTraitExprClass: {
 364     const auto *TE = cast<TypeTraitExpr>(E);
 365     return makeTruthVal(TE->getValue(), TE->getType());
 366   }
 367
 368   case Stmt::IntegerLiteralClass:
 369     return makeIntVal(cast<IntegerLiteral>(E));
 370
 371   case Stmt::ObjCBoolLiteralExprClass:
 372     return makeBoolVal(cast<ObjCBoolLiteralExpr>(E));
 373
 374   case Stmt::CXXNullPtrLiteralExprClass:
 375     return makeNullWithType(E->getType());
 376
 377   case Stmt::CStyleCastExprClass:
 378   case Stmt::CXXFunctionalCastExprClass:
 379   case Stmt::CXXConstCastExprClass:
 380   case Stmt::CXXReinterpretCastExprClass:
 381   case Stmt::CXXStaticCastExprClass:
 382   case Stmt::ImplicitCastExprClass: {
 383     const auto *CE = cast<CastExpr>(E);
 384     switch (CE->getCastKind()) {
 385     default:
 386       break;
 387     case CK_ArrayToPointerDecay:
 388     case CK_IntegralToPointer:
 389     case CK_NoOp:
 390     case CK_BitCast: {
 391       const Expr *SE = CE->getSubExpr();
 392       std::optional<SVal> Val = getConstantVal(SE);
 393       if (!Val)
 394         return std::nullopt;
 395       return evalCast(*Val, CE->getType(), SE->getType());
 396     }
 397     }
 398     [[fallthrough]];
 399   }
 400
 401   // If we don't have a special case, fall back to the AST's constant evaluator.
 402   default: {
 403     // Don't try to come up with a value for materialized temporaries.
 404     if (E->isGLValue())
 405       return std::nullopt;
 406
 407     ASTContext &Ctx = getContext();
 408     Expr::EvalResult Result;
 409     if (E->EvaluateAsInt(Result, Ctx))
 410       return makeIntVal(Result.Val.getInt());
 411
 412     if (Loc::isLocType(E->getType()))
 413       if (E->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull))
 414         return makeNullWithType(E->getType());
 415
 416     return std::nullopt;
 417   }
 418   }
 419 }
 420
 421 SVal SValBuilder::makeSymExprValNN(BinaryOperator::Opcode Op,
 422                                    NonLoc LHS, NonLoc RHS,
 423                                    QualType ResultTy) {
 424   SymbolRef symLHS = LHS.getAsSymbol();
 425   SymbolRef symRHS = RHS.getAsSymbol();
 426
 427   // TODO: When the Max Complexity is reached, we should conjure a symbol
 428   // instead of generating an Unknown value and propagate the taint info to it.
 429   const unsigned MaxComp = AnOpts.MaxSymbolComplexity;
 430
 431   if (symLHS && symRHS &&
 432       (symLHS->computeComplexity() + symRHS->computeComplexity()) <  MaxComp)
 433     return makeNonLoc(symLHS, Op, symRHS, ResultTy);
 434
 435   if (symLHS && symLHS->computeComplexity() < MaxComp)
 436     if (std::optional<nonloc::ConcreteInt> rInt =
 437             RHS.getAs<nonloc::ConcreteInt>())
 438       return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy);
 439
 440   if (symRHS && symRHS->computeComplexity() < MaxComp)
 441     if (std::optional<nonloc::ConcreteInt> lInt =
 442             LHS.getAs<nonloc::ConcreteInt>())
 443       return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy);
 444
 445   return UnknownVal();
 446 }
 447
 448 SVal SValBuilder::evalMinus(NonLoc X) {
 449   switch (X.getSubKind()) {
 450   case nonloc::ConcreteIntKind:
 451     return makeIntVal(-X.castAs<nonloc::ConcreteInt>().getValue());
 452   case nonloc::SymbolValKind:
 453     return makeNonLoc(X.castAs<nonloc::SymbolVal>().getSymbol(), UO_Minus,
 454                       X.getType(Context));
 455   default:
 456     return UnknownVal();
 457   }
 458 }
 459
 460 SVal SValBuilder::evalComplement(NonLoc X) {
 461   switch (X.getSubKind()) {
 462   case nonloc::ConcreteIntKind:
 463     return makeIntVal(~X.castAs<nonloc::ConcreteInt>().getValue());
 464   case nonloc::SymbolValKind:
 465     return makeNonLoc(X.castAs<nonloc::SymbolVal>().getSymbol(), UO_Not,
 466                       X.getType(Context));
 467   default:
 468     return UnknownVal();
 469   }
 470 }
 471
 472 SVal SValBuilder::evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc,
 473                  SVal operand, QualType type) {
 474   auto OpN = operand.getAs<NonLoc>();
 475   if (!OpN)
 476     return UnknownVal();
 477
 478   if (opc == UO_Minus)
 479     return evalMinus(*OpN);
 480   if (opc == UO_Not)
 481     return evalComplement(*OpN);
 482   llvm_unreachable("Unexpected unary operator");
 483 }
 484
 485 SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
 486                             SVal lhs, SVal rhs, QualType type) {
 487   if (lhs.isUndef() || rhs.isUndef())
 488     return UndefinedVal();
 489
 490   if (lhs.isUnknown() || rhs.isUnknown())
 491     return UnknownVal();
 492
 493   if (isa<nonloc::LazyCompoundVal>(lhs) || isa<nonloc::LazyCompoundVal>(rhs)) {
 494     return UnknownVal();
 495   }
 496
 497   if (op == BinaryOperatorKind::BO_Cmp) {
 498     // We can't reason about C++20 spaceship operator yet.
 499     //
 500     // FIXME: Support C++20 spaceship operator.
 501     //        The main problem here is that the result is not integer.
 502     return UnknownVal();
 503   }
 504
 505   if (std::optional<Loc> LV = lhs.getAs<Loc>()) {
 506     if (std::optional<Loc> RV = rhs.getAs<Loc>())
 507       return evalBinOpLL(state, op, *LV, *RV, type);
 508
 509     return evalBinOpLN(state, op, *LV, rhs.castAs<NonLoc>(), type);
 510   }
 511
 512   if (const std::optional<Loc> RV = rhs.getAs<Loc>()) {
 513     const auto IsCommutative = [](BinaryOperatorKind Op) {
 514       return Op == BO_Mul || Op == BO_Add || Op == BO_And || Op == BO_Xor ||
 515              Op == BO_Or;
 516     };
 517
 518     if (IsCommutative(op)) {
 519       // Swap operands.
 520       return evalBinOpLN(state, op, *RV, lhs.castAs<NonLoc>(), type);
 521     }
 522
 523     // If the right operand is a concrete int location then we have nothing
 524     // better but to treat it as a simple nonloc.
 525     if (auto RV = rhs.getAs<loc::ConcreteInt>()) {
 526       const nonloc::ConcreteInt RhsAsLoc = makeIntVal(RV->getValue());
 527       return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), RhsAsLoc, type);
 528     }
 529   }
 530
 531   return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), rhs.castAs<NonLoc>(),
 532                      type);
 533 }
 534
 535 ConditionTruthVal SValBuilder::areEqual(ProgramStateRef state, SVal lhs,
 536                                         SVal rhs) {
 537   return state->isNonNull(evalEQ(state, lhs, rhs));
 538 }
 539
 540 SVal SValBuilder::evalEQ(ProgramStateRef state, SVal lhs, SVal rhs) {
 541   return evalBinOp(state, BO_EQ, lhs, rhs, getConditionType());
 542 }
 543
 544 DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state,
 545                                          DefinedOrUnknownSVal lhs,
 546                                          DefinedOrUnknownSVal rhs) {
 547   return evalEQ(state, static_cast<SVal>(lhs), static_cast<SVal>(rhs))
 548       .castAs<DefinedOrUnknownSVal>();
 549 }
 550
 551 /// Recursively check if the pointer types are equal modulo const, volatile,
 552 /// and restrict qualifiers. Also, assume that all types are similar to 'void'.
 553 /// Assumes the input types are canonical.
 554 static bool shouldBeModeledWithNoOp(ASTContext &Context, QualType ToTy,
 555                                                          QualType FromTy) {
 556   while (Context.UnwrapSimilarTypes(ToTy, FromTy)) {
 557     Qualifiers Quals1, Quals2;
 558     ToTy = Context.getUnqualifiedArrayType(ToTy, Quals1);
 559     FromTy = Context.getUnqualifiedArrayType(FromTy, Quals2);
 560
 561     // Make sure that non-cvr-qualifiers the other qualifiers (e.g., address
 562     // spaces) are identical.
 563     Quals1.removeCVRQualifiers();
 564     Quals2.removeCVRQualifiers();
 565     if (Quals1 != Quals2)
 566       return false;
 567   }
 568
 569   // If we are casting to void, the 'From' value can be used to represent the
 570   // 'To' value.
 571   //
 572   // FIXME: Doing this after unwrapping the types doesn't make any sense. A
 573   // cast from 'int**' to 'void**' is not special in the way that a cast from
 574   // 'int*' to 'void*' is.
 575   if (ToTy->isVoidType())
 576     return true;
 577
 578   if (ToTy != FromTy)
 579     return false;
 580
 581   return true;
 582 }
 583
 584 // Handles casts of type CK_IntegralCast.
 585 // At the moment, this function will redirect to evalCast, except when the range
 586 // of the original value is known to be greater than the max of the target type.
 587 SVal SValBuilder::evalIntegralCast(ProgramStateRef state, SVal val,
 588                                    QualType castTy, QualType originalTy) {
 589   // No truncations if target type is big enough.
 590   if (getContext().getTypeSize(castTy) >= getContext().getTypeSize(originalTy))
 591     return evalCast(val, castTy, originalTy);
 592
 593   SymbolRef se = val.getAsSymbol();
 594   if (!se) // Let evalCast handle non symbolic expressions.
 595     return evalCast(val, castTy, originalTy);
 596
 597   // Find the maximum value of the target type.
 598   APSIntType ToType(getContext().getTypeSize(castTy),
 599                     castTy->isUnsignedIntegerType());
 600   llvm::APSInt ToTypeMax = ToType.getMaxValue();
 601
 602   NonLoc ToTypeMaxVal = makeIntVal(ToTypeMax);
 603
 604   // Check the range of the symbol being casted against the maximum value of the
 605   // target type.
 606   NonLoc FromVal = val.castAs<NonLoc>();
 607   QualType CmpTy = getConditionType();
 608   NonLoc CompVal =
 609       evalBinOpNN(state, BO_LE, FromVal, ToTypeMaxVal, CmpTy).castAs<NonLoc>();
 610   ProgramStateRef IsNotTruncated, IsTruncated;
 611   std::tie(IsNotTruncated, IsTruncated) = state->assume(CompVal);
 612   if (!IsNotTruncated && IsTruncated) {
 613     // Symbol is truncated so we evaluate it as a cast.
 614     return makeNonLoc(se, originalTy, castTy);
 615   }
 616   return evalCast(val, castTy, originalTy);
 617 }
 618
 619 //===----------------------------------------------------------------------===//
 620 // Cast method.
 621 // `evalCast` and its helper `EvalCastVisitor`
 622 //===----------------------------------------------------------------------===//
 623
 624 namespace {
 625 class EvalCastVisitor : public SValVisitor<EvalCastVisitor, SVal> {
 626 private:
 627   SValBuilder &VB;
 628   ASTContext &Context;
 629   QualType CastTy, OriginalTy;
 630
 631 public:
 632   EvalCastVisitor(SValBuilder &VB, QualType CastTy, QualType OriginalTy)
 633       : VB(VB), Context(VB.getContext()), CastTy(CastTy),
 634         OriginalTy(OriginalTy) {}
 635
 636   SVal Visit(SVal V) {
 637     if (CastTy.isNull())
 638       return V;
 639
 640     CastTy = Context.getCanonicalType(CastTy);
 641
 642     const bool IsUnknownOriginalType = OriginalTy.isNull();
 643     if (!IsUnknownOriginalType) {
 644       OriginalTy = Context.getCanonicalType(OriginalTy);
 645
 646       if (CastTy == OriginalTy)
 647         return V;
 648
 649       // FIXME: Move this check to the most appropriate
 650       // evalCastKind/evalCastSubKind function. For const casts, casts to void,
 651       // just propagate the value.
 652       if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType())
 653         if (shouldBeModeledWithNoOp(Context, Context.getPointerType(CastTy),
 654                                     Context.getPointerType(OriginalTy)))
 655           return V;
 656     }
 657     return SValVisitor::Visit(V);
 658   }
 659   SVal VisitUndefinedVal(UndefinedVal V) { return V; }
 660   SVal VisitUnknownVal(UnknownVal V) { return V; }
 661   SVal VisitLocConcreteInt(loc::ConcreteInt V) {
 662     // Pointer to bool.
 663     if (CastTy->isBooleanType())
 664       return VB.makeTruthVal(V.getValue().getBoolValue(), CastTy);
 665
 666     // Pointer to integer.
 667     if (CastTy->isIntegralOrEnumerationType()) {
 668       llvm::APSInt Value = V.getValue();
 669       VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value);
 670       return VB.makeIntVal(Value);
 671     }
 672
 673     // Pointer to any pointer.
 674     if (Loc::isLocType(CastTy)) {
 675       llvm::APSInt Value = V.getValue();
 676       VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value);
 677       return loc::ConcreteInt(VB.getBasicValueFactory().getValue(Value));
 678     }
 679
 680     // Pointer to whatever else.
 681     return UnknownVal();
 682   }
 683   SVal VisitLocGotoLabel(loc::GotoLabel V) {
 684     // Pointer to bool.
 685     if (CastTy->isBooleanType())
 686       // Labels are always true.
 687       return VB.makeTruthVal(true, CastTy);
 688
 689     // Pointer to integer.
 690     if (CastTy->isIntegralOrEnumerationType()) {
 691       const unsigned BitWidth = Context.getIntWidth(CastTy);
 692       return VB.makeLocAsInteger(V, BitWidth);
 693     }
 694
 695     const bool IsUnknownOriginalType = OriginalTy.isNull();
 696     if (!IsUnknownOriginalType) {
 697       // Array to pointer.
 698       if (isa<ArrayType>(OriginalTy))
 699         if (CastTy->isPointerType() || CastTy->isReferenceType())
 700           return UnknownVal();
 701     }
 702
 703     // Pointer to any pointer.
 704     if (Loc::isLocType(CastTy))
 705       return V;
 706
 707     // Pointer to whatever else.
 708     return UnknownVal();
 709   }
 710   SVal VisitLocMemRegionVal(loc::MemRegionVal V) {
 711     // Pointer to bool.
 712     if (CastTy->isBooleanType()) {
 713       const MemRegion *R = V.getRegion();
 714       if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
 715         if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl()))
 716           if (FD->isWeak())
 717             // FIXME: Currently we are using an extent symbol here,
 718             // because there are no generic region address metadata
 719             // symbols to use, only content metadata.
 720             return nonloc::SymbolVal(
 721                 VB.getSymbolManager().getExtentSymbol(FTR));
 722
 723       if (const SymbolicRegion *SymR = R->getSymbolicBase()) {
 724         SymbolRef Sym = SymR->getSymbol();
 725         QualType Ty = Sym->getType();
 726         // This change is needed for architectures with varying
 727         // pointer widths. See the amdgcn opencl reproducer with
 728         // this change as an example: solver-sym-simplification-ptr-bool.cl
 729         if (!Ty->isReferenceType())
 730           return VB.makeNonLoc(
 731               Sym, BO_NE, VB.getBasicValueFactory().getZeroWithTypeSize(Ty),
 732               CastTy);
 733       }
 734       // Non-symbolic memory regions are always true.
 735       return VB.makeTruthVal(true, CastTy);
 736     }
 737
 738     const bool IsUnknownOriginalType = OriginalTy.isNull();
 739     // Try to cast to array
 740     const auto *ArrayTy =
 741         IsUnknownOriginalType
 742             ? nullptr
 743             : dyn_cast<ArrayType>(OriginalTy.getCanonicalType());
 744
 745     // Pointer to integer.
 746     if (CastTy->isIntegralOrEnumerationType()) {
 747       SVal Val = V;
 748       // Array to integer.
 749       if (ArrayTy) {
 750         // We will always decay to a pointer.
 751         QualType ElemTy = ArrayTy->getElementType();
 752         Val = VB.getStateManager().ArrayToPointer(V, ElemTy);
 753         // FIXME: Keep these here for now in case we decide soon that we
 754         // need the original decayed type.
 755         //    QualType elemTy = cast<ArrayType>(originalTy)->getElementType();
 756         //    QualType pointerTy = C.getPointerType(elemTy);
 757       }
 758       const unsigned BitWidth = Context.getIntWidth(CastTy);
 759       return VB.makeLocAsInteger(Val.castAs<Loc>(), BitWidth);
 760     }
 761
 762     // Pointer to pointer.
 763     if (Loc::isLocType(CastTy)) {
 764
 765       if (IsUnknownOriginalType) {
 766         // When retrieving symbolic pointer and expecting a non-void pointer,
 767         // wrap them into element regions of the expected type if necessary.
 768         // It is necessary to make sure that the retrieved value makes sense,
 769         // because there's no other cast in the AST that would tell us to cast
 770         // it to the correct pointer type. We might need to do that for non-void
 771         // pointers as well.
 772         // FIXME: We really need a single good function to perform casts for us
 773         // correctly every time we need it.
 774         const MemRegion *R = V.getRegion();
 775         if (CastTy->isPointerType() && !CastTy->isVoidPointerType()) {
 776           if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
 777             QualType SRTy = SR->getSymbol()->getType();
 778
 779             auto HasSameUnqualifiedPointeeType = [](QualType ty1,
 780                                                     QualType ty2) {
 781               return ty1->getPointeeType().getCanonicalType().getTypePtr() ==
 782                      ty2->getPointeeType().getCanonicalType().getTypePtr();
 783             };
 784             if (!HasSameUnqualifiedPointeeType(SRTy, CastTy)) {
 785               if (auto OptMemRegV = VB.getCastedMemRegionVal(SR, CastTy))
 786                 return *OptMemRegV;
 787             }
 788           }
 789         }
 790         // Next fixes pointer dereference using type different from its initial
 791         // one. See PR37503 and PR49007 for details.
 792         if (const auto *ER = dyn_cast<ElementRegion>(R)) {
 793           if (auto OptMemRegV = VB.getCastedMemRegionVal(ER, CastTy))
 794             return *OptMemRegV;
 795         }
 796
 797         return V;
 798       }
 799
 800       if (OriginalTy->isIntegralOrEnumerationType() ||
 801           OriginalTy->isBlockPointerType() ||
 802           OriginalTy->isFunctionPointerType())
 803         return V;
 804
 805       // Array to pointer.
 806       if (ArrayTy) {
 807         // Are we casting from an array to a pointer?  If so just pass on
 808         // the decayed value.
 809         if (CastTy->isPointerType() || CastTy->isReferenceType()) {
 810           // We will always decay to a pointer.
 811           QualType ElemTy = ArrayTy->getElementType();
 812           return VB.getStateManager().ArrayToPointer(V, ElemTy);
 813         }
 814         // Are we casting from an array to an integer?  If so, cast the decayed
 815         // pointer value to an integer.
 816         assert(CastTy->isIntegralOrEnumerationType());
 817       }
 818
 819       // Other pointer to pointer.
 820       assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
 821              CastTy->isReferenceType());
 822
 823       // We get a symbolic function pointer for a dereference of a function
 824       // pointer, but it is of function type. Example:
 825
 826       //  struct FPRec {
 827       //    void (*my_func)(int * x);
 828       //  };
 829       //
 830       //  int bar(int x);
 831       //
 832       //  int f1_a(struct FPRec* foo) {
 833       //    int x;
 834       //    (*foo->my_func)(&x);
 835       //    return bar(x)+1; // no-warning
 836       //  }
 837
 838       // Get the result of casting a region to a different type.
 839       const MemRegion *R = V.getRegion();
 840       if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy))
 841         return *OptMemRegV;
 842     }
 843
 844     // Pointer to whatever else.
 845     // FIXME: There can be gross cases where one casts the result of a
 846     // function (that returns a pointer) to some other value that happens to
 847     // fit within that pointer value.  We currently have no good way to model
 848     // such operations.  When this happens, the underlying operation is that
 849     // the caller is reasoning about bits.  Conceptually we are layering a
 850     // "view" of a location on top of those bits.  Perhaps we need to be more
 851     // lazy about mutual possible views, even on an SVal?  This may be
 852     // necessary for bit-level reasoning as well.
 853     return UnknownVal();
 854   }
 855   SVal VisitNonLocCompoundVal(nonloc::CompoundVal V) {
 856     // Compound to whatever.
 857     return UnknownVal();
 858   }
 859   SVal VisitNonLocConcreteInt(nonloc::ConcreteInt V) {
 860     auto CastedValue = [V, this]() {
 861       llvm::APSInt Value = V.getValue();
 862       VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value);
 863       return Value;
 864     };
 865
 866     // Integer to bool.
 867     if (CastTy->isBooleanType())
 868       return VB.makeTruthVal(V.getValue().getBoolValue(), CastTy);
 869
 870     // Integer to pointer.
 871     if (CastTy->isIntegralOrEnumerationType())
 872       return VB.makeIntVal(CastedValue());
 873
 874     // Integer to pointer.
 875     if (Loc::isLocType(CastTy))
 876       return VB.makeIntLocVal(CastedValue());
 877
 878     // Pointer to whatever else.
 879     return UnknownVal();
 880   }
 881   SVal VisitNonLocLazyCompoundVal(nonloc::LazyCompoundVal V) {
 882     // LazyCompound to whatever.
 883     return UnknownVal();
 884   }
 885   SVal VisitNonLocLocAsInteger(nonloc::LocAsInteger V) {
 886     Loc L = V.getLoc();
 887
 888     // Pointer as integer to bool.
 889     if (CastTy->isBooleanType())
 890       // Pass to Loc function.
 891       return Visit(L);
 892
 893     const bool IsUnknownOriginalType = OriginalTy.isNull();
 894     // Pointer as integer to pointer.
 895     if (!IsUnknownOriginalType && Loc::isLocType(CastTy) &&
 896         OriginalTy->isIntegralOrEnumerationType()) {
 897       if (const MemRegion *R = L.getAsRegion())
 898         if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy))
 899           return *OptMemRegV;
 900       return L;
 901     }
 902
 903     // Pointer as integer with region to integer/pointer.
 904     const MemRegion *R = L.getAsRegion();
 905     if (!IsUnknownOriginalType && R) {
 906       if (CastTy->isIntegralOrEnumerationType())
 907         return VisitLocMemRegionVal(loc::MemRegionVal(R));
 908
 909       if (Loc::isLocType(CastTy)) {
 910         assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
 911                CastTy->isReferenceType());
 912         // Delegate to store manager to get the result of casting a region to a
 913         // different type. If the MemRegion* returned is NULL, this expression
 914         // Evaluates to UnknownVal.
 915         if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy))
 916           return *OptMemRegV;
 917       }
 918     } else {
 919       if (Loc::isLocType(CastTy)) {
 920         if (IsUnknownOriginalType)
 921           return VisitLocMemRegionVal(loc::MemRegionVal(R));
 922         return L;
 923       }
 924
 925       SymbolRef SE = nullptr;
 926       if (R) {
 927         if (const SymbolicRegion *SR =
 928                 dyn_cast<SymbolicRegion>(R->StripCasts())) {
 929           SE = SR->getSymbol();
 930         }
 931       }
 932
 933       if (!CastTy->isFloatingType() || !SE || SE->getType()->isFloatingType()) {
 934         // FIXME: Correctly support promotions/truncations.
 935         const unsigned CastSize = Context.getIntWidth(CastTy);
 936         if (CastSize == V.getNumBits())
 937           return V;
 938
 939         return VB.makeLocAsInteger(L, CastSize);
 940       }
 941     }
 942
 943     // Pointer as integer to whatever else.
 944     return UnknownVal();
 945   }
 946   SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) {
 947     SymbolRef SE = V.getSymbol();
 948
 949     const bool IsUnknownOriginalType = OriginalTy.isNull();
 950     // Symbol to bool.
 951     if (!IsUnknownOriginalType && CastTy->isBooleanType()) {
 952       // Non-float to bool.
 953       if (Loc::isLocType(OriginalTy) ||
 954           OriginalTy->isIntegralOrEnumerationType() ||
 955           OriginalTy->isMemberPointerType()) {
 956         BasicValueFactory &BVF = VB.getBasicValueFactory();
 957         return VB.makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy);
 958       }
 959     } else {
 960       // Symbol to integer, float.
 961       QualType T = Context.getCanonicalType(SE->getType());
 962
 963       // Produce SymbolCast if CastTy and T are different integers.
 964       // NOTE: In the end the type of SymbolCast shall be equal to CastTy.
 965       if (T->isIntegralOrUnscopedEnumerationType() &&
 966           CastTy->isIntegralOrUnscopedEnumerationType()) {
 967         AnalyzerOptions &Opts = VB.getStateManager()
 968                                     .getOwningEngine()
 969                                     .getAnalysisManager()
 970                                     .getAnalyzerOptions();
 971         // If appropriate option is disabled, ignore the cast.
 972         // NOTE: ShouldSupportSymbolicIntegerCasts is `false` by default.
 973         if (!Opts.ShouldSupportSymbolicIntegerCasts)
 974           return V;
 975         return simplifySymbolCast(V, CastTy);
 976       }
 977       if (!Loc::isLocType(CastTy))
 978         if (!IsUnknownOriginalType || !CastTy->isFloatingType() ||
 979             T->isFloatingType())
 980           return VB.makeNonLoc(SE, T, CastTy);
 981     }
 982
 983     // Symbol to pointer and whatever else.
 984     return UnknownVal();
 985   }
 986   SVal VisitNonLocPointerToMember(nonloc::PointerToMember V) {
 987     // Member pointer to whatever.
 988     return V;
 989   }
 990
 991   /// Reduce cast expression by removing redundant intermediate casts.
 992   /// E.g.
 993   /// - (char)(short)(int x) -> (char)(int x)
 994   /// - (int)(int x) -> int x
 995   ///
 996   /// \param V -- SymbolVal, which pressumably contains SymbolCast or any symbol
 997   /// that is applicable for cast operation.
 998   /// \param CastTy -- QualType, which `V` shall be cast to.
 999   /// \return SVal with simplified cast expression.
1000   /// \note: Currently only support integral casts.
1001   nonloc::SymbolVal simplifySymbolCast(nonloc::SymbolVal V, QualType CastTy) {
1002     // We use seven conditions to recognize a simplification case.
1003     // For the clarity let `CastTy` be `C`, SE->getType() - `T`, root type -
1004     // `R`, prefix `u` for unsigned, `s` for signed, no prefix - any sign: E.g.
1005     // (char)(short)(uint x)
1006     //      ( sC )( sT  )( uR  x)
1007     //
1008     // C === R (the same type)
1009     //  (char)(char x) -> (char x)
1010     //  (long)(long x) -> (long x)
1011     // Note: Comparisons operators below are for bit width.
1012     // C == T
1013     //  (short)(short)(int x) -> (short)(int x)
1014     //  (int)(long)(char x) -> (int)(char x) (sizeof(long) == sizeof(int))
1015     //  (long)(ullong)(char x) -> (long)(char x) (sizeof(long) ==
1016     //  sizeof(ullong))
1017     // C < T
1018     //  (short)(int)(char x) -> (short)(char x)
1019     //  (char)(int)(short x) -> (char)(short x)
1020     //  (short)(int)(short x) -> (short x)
1021     // C > T > uR
1022     //  (int)(short)(uchar x) -> (int)(uchar x)
1023     //  (uint)(short)(uchar x) -> (uint)(uchar x)
1024     //  (int)(ushort)(uchar x) -> (int)(uchar x)
1025     // C > sT > sR
1026     //  (int)(short)(char x) -> (int)(char x)
1027     //  (uint)(short)(char x) -> (uint)(char x)
1028     // C > sT == sR
1029     //  (int)(char)(char x) -> (int)(char x)
1030     //  (uint)(short)(short x) -> (uint)(short x)
1031     // C > uT == uR
1032     //  (int)(uchar)(uchar x) -> (int)(uchar x)
1033     //  (uint)(ushort)(ushort x) -> (uint)(ushort x)
1034     //  (llong)(ulong)(uint x) -> (llong)(uint x) (sizeof(ulong) ==
1035     //  sizeof(uint))
1036
1037     SymbolRef SE = V.getSymbol();
1038     QualType T = Context.getCanonicalType(SE->getType());
1039
1040     if (T == CastTy)
1041       return V;
1042
1043     if (!isa<SymbolCast>(SE))
1044       return VB.makeNonLoc(SE, T, CastTy);
1045
1046     SymbolRef RootSym = cast<SymbolCast>(SE)->getOperand();
1047     QualType RT = RootSym->getType().getCanonicalType();
1048
1049     // FIXME support simplification from non-integers.
1050     if (!RT->isIntegralOrEnumerationType())
1051       return VB.makeNonLoc(SE, T, CastTy);
1052
1053     BasicValueFactory &BVF = VB.getBasicValueFactory();
1054     APSIntType CTy = BVF.getAPSIntType(CastTy);
1055     APSIntType TTy = BVF.getAPSIntType(T);
1056
1057     const auto WC = CTy.getBitWidth();
1058     const auto WT = TTy.getBitWidth();
1059
1060     if (WC <= WT) {
1061       const bool isSameType = (RT == CastTy);
1062       if (isSameType)
1063         return nonloc::SymbolVal(RootSym);
1064       return VB.makeNonLoc(RootSym, RT, CastTy);
1065     }
1066
1067     APSIntType RTy = BVF.getAPSIntType(RT);
1068     const auto WR = RTy.getBitWidth();
1069     const bool UT = TTy.isUnsigned();
1070     const bool UR = RTy.isUnsigned();
1071
1072     if (((WT > WR) && (UR || !UT)) || ((WT == WR) && (UT == UR)))
1073       return VB.makeNonLoc(RootSym, RT, CastTy);
1074
1075     return VB.makeNonLoc(SE, T, CastTy);
1076   }
1077 };
1078 } // end anonymous namespace
1079
1080 /// Cast a given SVal to another SVal using given QualType's.
1081 /// \param V -- SVal that should be casted.
1082 /// \param CastTy -- QualType that V should be casted according to.
1083 /// \param OriginalTy -- QualType which is associated to V. It provides
1084 /// additional information about what type the cast performs from.
1085 /// \returns the most appropriate casted SVal.
1086 /// Note: Many cases don't use an exact OriginalTy. It can be extracted
1087 /// from SVal or the cast can performs unconditionaly. Always pass OriginalTy!
1088 /// It can be crucial in certain cases and generates different results.
1089 /// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy
1090 /// only. This behavior is uncertain and should be improved.
1091 SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) {
1092   EvalCastVisitor TRV{*this, CastTy, OriginalTy};
1093   return TRV.Visit(V);
1094 }