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->isStatic())
 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   NonLoc ToTypeMaxVal =
 602       makeIntVal(ToTypeMax.isUnsigned() ? ToTypeMax.getZExtValue()
 603                                         : ToTypeMax.getSExtValue(),
 604                  castTy)
 605           .castAs<NonLoc>();
 606   // Check the range of the symbol being casted against the maximum value of the
 607   // target type.
 608   NonLoc FromVal = val.castAs<NonLoc>();
 609   QualType CmpTy = getConditionType();
 610   NonLoc CompVal =
 611       evalBinOpNN(state, BO_LE, FromVal, ToTypeMaxVal, CmpTy).castAs<NonLoc>();
 612   ProgramStateRef IsNotTruncated, IsTruncated;
 613   std::tie(IsNotTruncated, IsTruncated) = state->assume(CompVal);
 614   if (!IsNotTruncated && IsTruncated) {
 615     // Symbol is truncated so we evaluate it as a cast.
 616     return makeNonLoc(se, originalTy, castTy);
 617   }
 618   return evalCast(val, castTy, originalTy);
 619 }
 620
 621 //===----------------------------------------------------------------------===//
 622 // Cast method.
 623 // `evalCast` and its helper `EvalCastVisitor`
 624 //===----------------------------------------------------------------------===//
 625
 626 namespace {
 627 class EvalCastVisitor : public SValVisitor<EvalCastVisitor, SVal> {
 628 private:
 629   SValBuilder &VB;
 630   ASTContext &Context;
 631   QualType CastTy, OriginalTy;
 632
 633 public:
 634   EvalCastVisitor(SValBuilder &VB, QualType CastTy, QualType OriginalTy)
 635       : VB(VB), Context(VB.getContext()), CastTy(CastTy),
 636         OriginalTy(OriginalTy) {}
 637
 638   SVal Visit(SVal V) {
 639     if (CastTy.isNull())
 640       return V;
 641
 642     CastTy = Context.getCanonicalType(CastTy);
 643
 644     const bool IsUnknownOriginalType = OriginalTy.isNull();
 645     if (!IsUnknownOriginalType) {
 646       OriginalTy = Context.getCanonicalType(OriginalTy);
 647
 648       if (CastTy == OriginalTy)
 649         return V;
 650
 651       // FIXME: Move this check to the most appropriate
 652       // evalCastKind/evalCastSubKind function. For const casts, casts to void,
 653       // just propagate the value.
 654       if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType())
 655         if (shouldBeModeledWithNoOp(Context, Context.getPointerType(CastTy),
 656                                     Context.getPointerType(OriginalTy)))
 657           return V;
 658     }
 659     return SValVisitor::Visit(V);
 660   }
 661   SVal VisitUndefinedVal(UndefinedVal V) { return V; }
 662   SVal VisitUnknownVal(UnknownVal V) { return V; }
 663   SVal VisitLocConcreteInt(loc::ConcreteInt V) {
 664     // Pointer to bool.
 665     if (CastTy->isBooleanType())
 666       return VB.makeTruthVal(V.getValue().getBoolValue(), CastTy);
 667
 668     // Pointer to integer.
 669     if (CastTy->isIntegralOrEnumerationType()) {
 670       llvm::APSInt Value = V.getValue();
 671       VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value);
 672       return VB.makeIntVal(Value);
 673     }
 674
 675     // Pointer to any pointer.
 676     if (Loc::isLocType(CastTy)) {
 677       llvm::APSInt Value = V.getValue();
 678       VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value);
 679       return loc::ConcreteInt(VB.getBasicValueFactory().getValue(Value));
 680     }
 681
 682     // Pointer to whatever else.
 683     return UnknownVal();
 684   }
 685   SVal VisitLocGotoLabel(loc::GotoLabel V) {
 686     // Pointer to bool.
 687     if (CastTy->isBooleanType())
 688       // Labels are always true.
 689       return VB.makeTruthVal(true, CastTy);
 690
 691     // Pointer to integer.
 692     if (CastTy->isIntegralOrEnumerationType()) {
 693       const unsigned BitWidth = Context.getIntWidth(CastTy);
 694       return VB.makeLocAsInteger(V, BitWidth);
 695     }
 696
 697     const bool IsUnknownOriginalType = OriginalTy.isNull();
 698     if (!IsUnknownOriginalType) {
 699       // Array to pointer.
 700       if (isa<ArrayType>(OriginalTy))
 701         if (CastTy->isPointerType() || CastTy->isReferenceType())
 702           return UnknownVal();
 703     }
 704
 705     // Pointer to any pointer.
 706     if (Loc::isLocType(CastTy))
 707       return V;
 708
 709     // Pointer to whatever else.
 710     return UnknownVal();
 711   }
 712   SVal VisitLocMemRegionVal(loc::MemRegionVal V) {
 713     // Pointer to bool.
 714     if (CastTy->isBooleanType()) {
 715       const MemRegion *R = V.getRegion();
 716       if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
 717         if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl()))
 718           if (FD->isWeak())
 719             // FIXME: Currently we are using an extent symbol here,
 720             // because there are no generic region address metadata
 721             // symbols to use, only content metadata.
 722             return nonloc::SymbolVal(
 723                 VB.getSymbolManager().getExtentSymbol(FTR));
 724
 725       if (const SymbolicRegion *SymR = R->getSymbolicBase()) {
 726         SymbolRef Sym = SymR->getSymbol();
 727         QualType Ty = Sym->getType();
 728         // This change is needed for architectures with varying
 729         // pointer widths. See the amdgcn opencl reproducer with
 730         // this change as an example: solver-sym-simplification-ptr-bool.cl
 731         if (!Ty->isReferenceType())
 732           return VB.makeNonLoc(
 733               Sym, BO_NE, VB.getBasicValueFactory().getZeroWithTypeSize(Ty),
 734               CastTy);
 735       }
 736       // Non-symbolic memory regions are always true.
 737       return VB.makeTruthVal(true, CastTy);
 738     }
 739
 740     const bool IsUnknownOriginalType = OriginalTy.isNull();
 741     // Try to cast to array
 742     const auto *ArrayTy =
 743         IsUnknownOriginalType
 744             ? nullptr
 745             : dyn_cast<ArrayType>(OriginalTy.getCanonicalType());
 746
 747     // Pointer to integer.
 748     if (CastTy->isIntegralOrEnumerationType()) {
 749       SVal Val = V;
 750       // Array to integer.
 751       if (ArrayTy) {
 752         // We will always decay to a pointer.
 753         QualType ElemTy = ArrayTy->getElementType();
 754         Val = VB.getStateManager().ArrayToPointer(V, ElemTy);
 755         // FIXME: Keep these here for now in case we decide soon that we
 756         // need the original decayed type.
 757         //    QualType elemTy = cast<ArrayType>(originalTy)->getElementType();
 758         //    QualType pointerTy = C.getPointerType(elemTy);
 759       }
 760       const unsigned BitWidth = Context.getIntWidth(CastTy);
 761       return VB.makeLocAsInteger(Val.castAs<Loc>(), BitWidth);
 762     }
 763
 764     // Pointer to pointer.
 765     if (Loc::isLocType(CastTy)) {
 766
 767       if (IsUnknownOriginalType) {
 768         // When retrieving symbolic pointer and expecting a non-void pointer,
 769         // wrap them into element regions of the expected type if necessary.
 770         // It is necessary to make sure that the retrieved value makes sense,
 771         // because there's no other cast in the AST that would tell us to cast
 772         // it to the correct pointer type. We might need to do that for non-void
 773         // pointers as well.
 774         // FIXME: We really need a single good function to perform casts for us
 775         // correctly every time we need it.
 776         const MemRegion *R = V.getRegion();
 777         if (CastTy->isPointerType() && !CastTy->isVoidPointerType()) {
 778           if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
 779             QualType SRTy = SR->getSymbol()->getType();
 780
 781             auto HasSameUnqualifiedPointeeType = [](QualType ty1,
 782                                                     QualType ty2) {
 783               return ty1->getPointeeType().getCanonicalType().getTypePtr() ==
 784                      ty2->getPointeeType().getCanonicalType().getTypePtr();
 785             };
 786             if (!HasSameUnqualifiedPointeeType(SRTy, CastTy)) {
 787               if (auto OptMemRegV = VB.getCastedMemRegionVal(SR, CastTy))
 788                 return *OptMemRegV;
 789             }
 790           }
 791         }
 792         // Next fixes pointer dereference using type different from its initial
 793         // one. See PR37503 and PR49007 for details.
 794         if (const auto *ER = dyn_cast<ElementRegion>(R)) {
 795           if (auto OptMemRegV = VB.getCastedMemRegionVal(ER, CastTy))
 796             return *OptMemRegV;
 797         }
 798
 799         return V;
 800       }
 801
 802       if (OriginalTy->isIntegralOrEnumerationType() ||
 803           OriginalTy->isBlockPointerType() ||
 804           OriginalTy->isFunctionPointerType())
 805         return V;
 806
 807       // Array to pointer.
 808       if (ArrayTy) {
 809         // Are we casting from an array to a pointer?  If so just pass on
 810         // the decayed value.
 811         if (CastTy->isPointerType() || CastTy->isReferenceType()) {
 812           // We will always decay to a pointer.
 813           QualType ElemTy = ArrayTy->getElementType();
 814           return VB.getStateManager().ArrayToPointer(V, ElemTy);
 815         }
 816         // Are we casting from an array to an integer?  If so, cast the decayed
 817         // pointer value to an integer.
 818         assert(CastTy->isIntegralOrEnumerationType());
 819       }
 820
 821       // Other pointer to pointer.
 822       assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
 823              CastTy->isReferenceType());
 824
 825       // We get a symbolic function pointer for a dereference of a function
 826       // pointer, but it is of function type. Example:
 827
 828       //  struct FPRec {
 829       //    void (*my_func)(int * x);
 830       //  };
 831       //
 832       //  int bar(int x);
 833       //
 834       //  int f1_a(struct FPRec* foo) {
 835       //    int x;
 836       //    (*foo->my_func)(&x);
 837       //    return bar(x)+1; // no-warning
 838       //  }
 839
 840       // Get the result of casting a region to a different type.
 841       const MemRegion *R = V.getRegion();
 842       if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy))
 843         return *OptMemRegV;
 844     }
 845
 846     // Pointer to whatever else.
 847     // FIXME: There can be gross cases where one casts the result of a
 848     // function (that returns a pointer) to some other value that happens to
 849     // fit within that pointer value.  We currently have no good way to model
 850     // such operations.  When this happens, the underlying operation is that
 851     // the caller is reasoning about bits.  Conceptually we are layering a
 852     // "view" of a location on top of those bits.  Perhaps we need to be more
 853     // lazy about mutual possible views, even on an SVal?  This may be
 854     // necessary for bit-level reasoning as well.
 855     return UnknownVal();
 856   }
 857   SVal VisitNonLocCompoundVal(nonloc::CompoundVal V) {
 858     // Compound to whatever.
 859     return UnknownVal();
 860   }
 861   SVal VisitNonLocConcreteInt(nonloc::ConcreteInt V) {
 862     auto CastedValue = [V, this]() {
 863       llvm::APSInt Value = V.getValue();
 864       VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value);
 865       return Value;
 866     };
 867
 868     // Integer to bool.
 869     if (CastTy->isBooleanType())
 870       return VB.makeTruthVal(V.getValue().getBoolValue(), CastTy);
 871
 872     // Integer to pointer.
 873     if (CastTy->isIntegralOrEnumerationType())
 874       return VB.makeIntVal(CastedValue());
 875
 876     // Integer to pointer.
 877     if (Loc::isLocType(CastTy))
 878       return VB.makeIntLocVal(CastedValue());
 879
 880     // Pointer to whatever else.
 881     return UnknownVal();
 882   }
 883   SVal VisitNonLocLazyCompoundVal(nonloc::LazyCompoundVal V) {
 884     // LazyCompound to whatever.
 885     return UnknownVal();
 886   }
 887   SVal VisitNonLocLocAsInteger(nonloc::LocAsInteger V) {
 888     Loc L = V.getLoc();
 889
 890     // Pointer as integer to bool.
 891     if (CastTy->isBooleanType())
 892       // Pass to Loc function.
 893       return Visit(L);
 894
 895     const bool IsUnknownOriginalType = OriginalTy.isNull();
 896     // Pointer as integer to pointer.
 897     if (!IsUnknownOriginalType && Loc::isLocType(CastTy) &&
 898         OriginalTy->isIntegralOrEnumerationType()) {
 899       if (const MemRegion *R = L.getAsRegion())
 900         if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy))
 901           return *OptMemRegV;
 902       return L;
 903     }
 904
 905     // Pointer as integer with region to integer/pointer.
 906     const MemRegion *R = L.getAsRegion();
 907     if (!IsUnknownOriginalType && R) {
 908       if (CastTy->isIntegralOrEnumerationType())
 909         return VisitLocMemRegionVal(loc::MemRegionVal(R));
 910
 911       if (Loc::isLocType(CastTy)) {
 912         assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
 913                CastTy->isReferenceType());
 914         // Delegate to store manager to get the result of casting a region to a
 915         // different type. If the MemRegion* returned is NULL, this expression
 916         // Evaluates to UnknownVal.
 917         if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy))
 918           return *OptMemRegV;
 919       }
 920     } else {
 921       if (Loc::isLocType(CastTy)) {
 922         if (IsUnknownOriginalType)
 923           return VisitLocMemRegionVal(loc::MemRegionVal(R));
 924         return L;
 925       }
 926
 927       SymbolRef SE = nullptr;
 928       if (R) {
 929         if (const SymbolicRegion *SR =
 930                 dyn_cast<SymbolicRegion>(R->StripCasts())) {
 931           SE = SR->getSymbol();
 932         }
 933       }
 934
 935       if (!CastTy->isFloatingType() || !SE || SE->getType()->isFloatingType()) {
 936         // FIXME: Correctly support promotions/truncations.
 937         const unsigned CastSize = Context.getIntWidth(CastTy);
 938         if (CastSize == V.getNumBits())
 939           return V;
 940
 941         return VB.makeLocAsInteger(L, CastSize);
 942       }
 943     }
 944
 945     // Pointer as integer to whatever else.
 946     return UnknownVal();
 947   }
 948   SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) {
 949     SymbolRef SE = V.getSymbol();
 950
 951     const bool IsUnknownOriginalType = OriginalTy.isNull();
 952     // Symbol to bool.
 953     if (!IsUnknownOriginalType && CastTy->isBooleanType()) {
 954       // Non-float to bool.
 955       if (Loc::isLocType(OriginalTy) ||
 956           OriginalTy->isIntegralOrEnumerationType() ||
 957           OriginalTy->isMemberPointerType()) {
 958         BasicValueFactory &BVF = VB.getBasicValueFactory();
 959         return VB.makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy);
 960       }
 961     } else {
 962       // Symbol to integer, float.
 963       QualType T = Context.getCanonicalType(SE->getType());
 964
 965       // Produce SymbolCast if CastTy and T are different integers.
 966       // NOTE: In the end the type of SymbolCast shall be equal to CastTy.
 967       if (T->isIntegralOrUnscopedEnumerationType() &&
 968           CastTy->isIntegralOrUnscopedEnumerationType()) {
 969         AnalyzerOptions &Opts = VB.getStateManager()
 970                                     .getOwningEngine()
 971                                     .getAnalysisManager()
 972                                     .getAnalyzerOptions();
 973         // If appropriate option is disabled, ignore the cast.
 974         // NOTE: ShouldSupportSymbolicIntegerCasts is `false` by default.
 975         if (!Opts.ShouldSupportSymbolicIntegerCasts)
 976           return V;
 977         return simplifySymbolCast(V, CastTy);
 978       }
 979       if (!Loc::isLocType(CastTy))
 980         if (!IsUnknownOriginalType || !CastTy->isFloatingType() ||
 981             T->isFloatingType())
 982           return VB.makeNonLoc(SE, T, CastTy);
 983     }
 984
 985     // Symbol to pointer and whatever else.
 986     return UnknownVal();
 987   }
 988   SVal VisitNonLocPointerToMember(nonloc::PointerToMember V) {
 989     // Member pointer to whatever.
 990     return V;
 991   }
 992
 993   /// Reduce cast expression by removing redundant intermediate casts.
 994   /// E.g.
 995   /// - (char)(short)(int x) -> (char)(int x)
 996   /// - (int)(int x) -> int x
 997   ///
 998   /// \param V -- SymbolVal, which pressumably contains SymbolCast or any symbol
 999   /// that is applicable for cast operation.
1000   /// \param CastTy -- QualType, which `V` shall be cast to.
1001   /// \return SVal with simplified cast expression.
1002   /// \note: Currently only support integral casts.
1003   nonloc::SymbolVal simplifySymbolCast(nonloc::SymbolVal V, QualType CastTy) {
1004     // We use seven conditions to recognize a simplification case.
1005     // For the clarity let `CastTy` be `C`, SE->getType() - `T`, root type -
1006     // `R`, prefix `u` for unsigned, `s` for signed, no prefix - any sign: E.g.
1007     // (char)(short)(uint x)
1008     //      ( sC )( sT  )( uR  x)
1009     //
1010     // C === R (the same type)
1011     //  (char)(char x) -> (char x)
1012     //  (long)(long x) -> (long x)
1013     // Note: Comparisons operators below are for bit width.
1014     // C == T
1015     //  (short)(short)(int x) -> (short)(int x)
1016     //  (int)(long)(char x) -> (int)(char x) (sizeof(long) == sizeof(int))
1017     //  (long)(ullong)(char x) -> (long)(char x) (sizeof(long) ==
1018     //  sizeof(ullong))
1019     // C < T
1020     //  (short)(int)(char x) -> (short)(char x)
1021     //  (char)(int)(short x) -> (char)(short x)
1022     //  (short)(int)(short x) -> (short x)
1023     // C > T > uR
1024     //  (int)(short)(uchar x) -> (int)(uchar x)
1025     //  (uint)(short)(uchar x) -> (uint)(uchar x)
1026     //  (int)(ushort)(uchar x) -> (int)(uchar x)
1027     // C > sT > sR
1028     //  (int)(short)(char x) -> (int)(char x)
1029     //  (uint)(short)(char x) -> (uint)(char x)
1030     // C > sT == sR
1031     //  (int)(char)(char x) -> (int)(char x)
1032     //  (uint)(short)(short x) -> (uint)(short x)
1033     // C > uT == uR
1034     //  (int)(uchar)(uchar x) -> (int)(uchar x)
1035     //  (uint)(ushort)(ushort x) -> (uint)(ushort x)
1036     //  (llong)(ulong)(uint x) -> (llong)(uint x) (sizeof(ulong) ==
1037     //  sizeof(uint))
1038
1039     SymbolRef SE = V.getSymbol();
1040     QualType T = Context.getCanonicalType(SE->getType());
1041
1042     if (T == CastTy)
1043       return V;
1044
1045     if (!isa<SymbolCast>(SE))
1046       return VB.makeNonLoc(SE, T, CastTy);
1047
1048     SymbolRef RootSym = cast<SymbolCast>(SE)->getOperand();
1049     QualType RT = RootSym->getType().getCanonicalType();
1050
1051     // FIXME support simplification from non-integers.
1052     if (!RT->isIntegralOrEnumerationType())
1053       return VB.makeNonLoc(SE, T, CastTy);
1054
1055     BasicValueFactory &BVF = VB.getBasicValueFactory();
1056     APSIntType CTy = BVF.getAPSIntType(CastTy);
1057     APSIntType TTy = BVF.getAPSIntType(T);
1058
1059     const auto WC = CTy.getBitWidth();
1060     const auto WT = TTy.getBitWidth();
1061
1062     if (WC <= WT) {
1063       const bool isSameType = (RT == CastTy);
1064       if (isSameType)
1065         return nonloc::SymbolVal(RootSym);
1066       return VB.makeNonLoc(RootSym, RT, CastTy);
1067     }
1068
1069     APSIntType RTy = BVF.getAPSIntType(RT);
1070     const auto WR = RTy.getBitWidth();
1071     const bool UT = TTy.isUnsigned();
1072     const bool UR = RTy.isUnsigned();
1073
1074     if (((WT > WR) && (UR || !UT)) || ((WT == WR) && (UT == UR)))
1075       return VB.makeNonLoc(RootSym, RT, CastTy);
1076
1077     return VB.makeNonLoc(SE, T, CastTy);
1078   }
1079 };
1080 } // end anonymous namespace
1081
1082 /// Cast a given SVal to another SVal using given QualType's.
1083 /// \param V -- SVal that should be casted.
1084 /// \param CastTy -- QualType that V should be casted according to.
1085 /// \param OriginalTy -- QualType which is associated to V. It provides
1086 /// additional information about what type the cast performs from.
1087 /// \returns the most appropriate casted SVal.
1088 /// Note: Many cases don't use an exact OriginalTy. It can be extracted
1089 /// from SVal or the cast can performs unconditionaly. Always pass OriginalTy!
1090 /// It can be crucial in certain cases and generates different results.
1091 /// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy
1092 /// only. This behavior is uncertain and should be improved.
1093 SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) {
1094   EvalCastVisitor TRV{*this, CastTy, OriginalTy};
1095   return TRV.Visit(V);
1096 }