ExprEngineC.cpp revision 314564
13229Spst//=-- ExprEngineC.cpp - ExprEngine support for C expressions ----*- C++ -*-===// 250476Speter// 33229Spst// The LLVM Compiler Infrastructure 43229Spst// 59720Swpaul// This file is distributed under the University of Illinois Open Source 63229Spst// License. See LICENSE.TXT for details. 73229Spst// 8201380Sed//===----------------------------------------------------------------------===// 9201380Sed// 1013575Spst// This file defines ExprEngine's support for C expressions. 113229Spst// 123229Spst//===----------------------------------------------------------------------===// 133229Spst 143229Spst#include "clang/AST/ExprCXX.h" 1574814Sru#include "clang/AST/DeclCXX.h" 1613849Smpp#include "clang/StaticAnalyzer/Core/CheckerManager.h" 173229Spst#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 183229Spst 19using namespace clang; 20using namespace ento; 21using llvm::APSInt; 22 23void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, 24 ExplodedNode *Pred, 25 ExplodedNodeSet &Dst) { 26 27 Expr *LHS = B->getLHS()->IgnoreParens(); 28 Expr *RHS = B->getRHS()->IgnoreParens(); 29 30 // FIXME: Prechecks eventually go in ::Visit(). 31 ExplodedNodeSet CheckedSet; 32 ExplodedNodeSet Tmp2; 33 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, B, *this); 34 35 // With both the LHS and RHS evaluated, process the operation itself. 36 for (ExplodedNodeSet::iterator it=CheckedSet.begin(), ei=CheckedSet.end(); 37 it != ei; ++it) { 38 39 ProgramStateRef state = (*it)->getState(); 40 const LocationContext *LCtx = (*it)->getLocationContext(); 41 SVal LeftV = state->getSVal(LHS, LCtx); 42 SVal RightV = state->getSVal(RHS, LCtx); 43 44 BinaryOperator::Opcode Op = B->getOpcode(); 45 46 if (Op == BO_Assign) { 47 // EXPERIMENTAL: "Conjured" symbols. 48 // FIXME: Handle structs. 49 if (RightV.isUnknown()) { 50 unsigned Count = currBldrCtx->blockCount(); 51 RightV = svalBuilder.conjureSymbolVal(nullptr, B->getRHS(), LCtx, 52 Count); 53 } 54 // Simulate the effects of a "store": bind the value of the RHS 55 // to the L-Value represented by the LHS. 56 SVal ExprVal = B->isGLValue() ? LeftV : RightV; 57 evalStore(Tmp2, B, LHS, *it, state->BindExpr(B, LCtx, ExprVal), 58 LeftV, RightV); 59 continue; 60 } 61 62 if (!B->isAssignmentOp()) { 63 StmtNodeBuilder Bldr(*it, Tmp2, *currBldrCtx); 64 65 if (B->isAdditiveOp()) { 66 // If one of the operands is a location, conjure a symbol for the other 67 // one (offset) if it's unknown so that memory arithmetic always 68 // results in an ElementRegion. 69 // TODO: This can be removed after we enable history tracking with 70 // SymSymExpr. 71 unsigned Count = currBldrCtx->blockCount(); 72 if (LeftV.getAs<Loc>() && 73 RHS->getType()->isIntegralOrEnumerationType() && 74 RightV.isUnknown()) { 75 RightV = svalBuilder.conjureSymbolVal(RHS, LCtx, RHS->getType(), 76 Count); 77 } 78 if (RightV.getAs<Loc>() && 79 LHS->getType()->isIntegralOrEnumerationType() && 80 LeftV.isUnknown()) { 81 LeftV = svalBuilder.conjureSymbolVal(LHS, LCtx, LHS->getType(), 82 Count); 83 } 84 } 85 86 // Although we don't yet model pointers-to-members, we do need to make 87 // sure that the members of temporaries have a valid 'this' pointer for 88 // other checks. 89 if (B->getOpcode() == BO_PtrMemD) 90 state = createTemporaryRegionIfNeeded(state, LCtx, LHS); 91 92 // Process non-assignments except commas or short-circuited 93 // logical expressions (LAnd and LOr). 94 SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType()); 95 if (Result.isUnknown()) { 96 Bldr.generateNode(B, *it, state); 97 continue; 98 } 99 100 state = state->BindExpr(B, LCtx, Result); 101 Bldr.generateNode(B, *it, state); 102 continue; 103 } 104 105 assert (B->isCompoundAssignmentOp()); 106 107 switch (Op) { 108 default: 109 llvm_unreachable("Invalid opcode for compound assignment."); 110 case BO_MulAssign: Op = BO_Mul; break; 111 case BO_DivAssign: Op = BO_Div; break; 112 case BO_RemAssign: Op = BO_Rem; break; 113 case BO_AddAssign: Op = BO_Add; break; 114 case BO_SubAssign: Op = BO_Sub; break; 115 case BO_ShlAssign: Op = BO_Shl; break; 116 case BO_ShrAssign: Op = BO_Shr; break; 117 case BO_AndAssign: Op = BO_And; break; 118 case BO_XorAssign: Op = BO_Xor; break; 119 case BO_OrAssign: Op = BO_Or; break; 120 } 121 122 // Perform a load (the LHS). This performs the checks for 123 // null dereferences, and so on. 124 ExplodedNodeSet Tmp; 125 SVal location = LeftV; 126 evalLoad(Tmp, B, LHS, *it, state, location); 127 128 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; 129 ++I) { 130 131 state = (*I)->getState(); 132 const LocationContext *LCtx = (*I)->getLocationContext(); 133 SVal V = state->getSVal(LHS, LCtx); 134 135 // Get the computation type. 136 QualType CTy = 137 cast<CompoundAssignOperator>(B)->getComputationResultType(); 138 CTy = getContext().getCanonicalType(CTy); 139 140 QualType CLHSTy = 141 cast<CompoundAssignOperator>(B)->getComputationLHSType(); 142 CLHSTy = getContext().getCanonicalType(CLHSTy); 143 144 QualType LTy = getContext().getCanonicalType(LHS->getType()); 145 146 // Promote LHS. 147 V = svalBuilder.evalCast(V, CLHSTy, LTy); 148 149 // Compute the result of the operation. 150 SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy), 151 B->getType(), CTy); 152 153 // EXPERIMENTAL: "Conjured" symbols. 154 // FIXME: Handle structs. 155 156 SVal LHSVal; 157 158 if (Result.isUnknown()) { 159 // The symbolic value is actually for the type of the left-hand side 160 // expression, not the computation type, as this is the value the 161 // LValue on the LHS will bind to. 162 LHSVal = svalBuilder.conjureSymbolVal(nullptr, B->getRHS(), LCtx, LTy, 163 currBldrCtx->blockCount()); 164 // However, we need to convert the symbol to the computation type. 165 Result = svalBuilder.evalCast(LHSVal, CTy, LTy); 166 } 167 else { 168 // The left-hand side may bind to a different value then the 169 // computation type. 170 LHSVal = svalBuilder.evalCast(Result, LTy, CTy); 171 } 172 173 // In C++, assignment and compound assignment operators return an 174 // lvalue. 175 if (B->isGLValue()) 176 state = state->BindExpr(B, LCtx, location); 177 else 178 state = state->BindExpr(B, LCtx, Result); 179 180 evalStore(Tmp2, B, LHS, *I, state, location, LHSVal); 181 } 182 } 183 184 // FIXME: postvisits eventually go in ::Visit() 185 getCheckerManager().runCheckersForPostStmt(Dst, Tmp2, B, *this); 186} 187 188void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, 189 ExplodedNodeSet &Dst) { 190 191 CanQualType T = getContext().getCanonicalType(BE->getType()); 192 193 const BlockDecl *BD = BE->getBlockDecl(); 194 // Get the value of the block itself. 195 SVal V = svalBuilder.getBlockPointer(BD, T, 196 Pred->getLocationContext(), 197 currBldrCtx->blockCount()); 198 199 ProgramStateRef State = Pred->getState(); 200 201 // If we created a new MemRegion for the block, we should explicitly bind 202 // the captured variables. 203 if (const BlockDataRegion *BDR = 204 dyn_cast_or_null<BlockDataRegion>(V.getAsRegion())) { 205 206 BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), 207 E = BDR->referenced_vars_end(); 208 209 auto CI = BD->capture_begin(); 210 auto CE = BD->capture_end(); 211 for (; I != E; ++I) { 212 const VarRegion *capturedR = I.getCapturedRegion(); 213 const VarRegion *originalR = I.getOriginalRegion(); 214 215 // If the capture had a copy expression, use the result of evaluating 216 // that expression, otherwise use the original value. 217 // We rely on the invariant that the block declaration's capture variables 218 // are a prefix of the BlockDataRegion's referenced vars (which may include 219 // referenced globals, etc.) to enable fast lookup of the capture for a 220 // given referenced var. 221 const Expr *copyExpr = nullptr; 222 if (CI != CE) { 223 assert(CI->getVariable() == capturedR->getDecl()); 224 copyExpr = CI->getCopyExpr(); 225 CI++; 226 } 227 228 if (capturedR != originalR) { 229 SVal originalV; 230 if (copyExpr) { 231 originalV = State->getSVal(copyExpr, Pred->getLocationContext()); 232 } else { 233 originalV = State->getSVal(loc::MemRegionVal(originalR)); 234 } 235 State = State->bindLoc(loc::MemRegionVal(capturedR), originalV); 236 } 237 } 238 } 239 240 ExplodedNodeSet Tmp; 241 StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx); 242 Bldr.generateNode(BE, Pred, 243 State->BindExpr(BE, Pred->getLocationContext(), V), 244 nullptr, ProgramPoint::PostLValueKind); 245 246 // FIXME: Move all post/pre visits to ::Visit(). 247 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this); 248} 249 250ProgramStateRef ExprEngine::handleLValueBitCast( 251 ProgramStateRef state, const Expr* Ex, const LocationContext* LCtx, 252 QualType T, QualType ExTy, const CastExpr* CastE, StmtNodeBuilder& Bldr, 253 ExplodedNode* Pred) { 254 // Delegate to SValBuilder to process. 255 SVal V = state->getSVal(Ex, LCtx); 256 V = svalBuilder.evalCast(V, T, ExTy); 257 // Negate the result if we're treating the boolean as a signed i1 258 if (CastE->getCastKind() == CK_BooleanToSignedIntegral) 259 V = evalMinus(V); 260 state = state->BindExpr(CastE, LCtx, V); 261 Bldr.generateNode(CastE, Pred, state); 262 263 return state; 264} 265 266ProgramStateRef ExprEngine::handleLVectorSplat( 267 ProgramStateRef state, const LocationContext* LCtx, const CastExpr* CastE, 268 StmtNodeBuilder &Bldr, ExplodedNode* Pred) { 269 // Recover some path sensitivity by conjuring a new value. 270 QualType resultType = CastE->getType(); 271 if (CastE->isGLValue()) 272 resultType = getContext().getPointerType(resultType); 273 SVal result = svalBuilder.conjureSymbolVal(nullptr, CastE, LCtx, 274 resultType, 275 currBldrCtx->blockCount()); 276 state = state->BindExpr(CastE, LCtx, result); 277 Bldr.generateNode(CastE, Pred, state); 278 279 return state; 280} 281 282void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, 283 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 284 285 ExplodedNodeSet dstPreStmt; 286 getCheckerManager().runCheckersForPreStmt(dstPreStmt, Pred, CastE, *this); 287 288 if (CastE->getCastKind() == CK_LValueToRValue) { 289 for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end(); 290 I!=E; ++I) { 291 ExplodedNode *subExprNode = *I; 292 ProgramStateRef state = subExprNode->getState(); 293 const LocationContext *LCtx = subExprNode->getLocationContext(); 294 evalLoad(Dst, CastE, CastE, subExprNode, state, state->getSVal(Ex, LCtx)); 295 } 296 return; 297 } 298 299 // All other casts. 300 QualType T = CastE->getType(); 301 QualType ExTy = Ex->getType(); 302 303 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE)) 304 T = ExCast->getTypeAsWritten(); 305 306 StmtNodeBuilder Bldr(dstPreStmt, Dst, *currBldrCtx); 307 for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end(); 308 I != E; ++I) { 309 310 Pred = *I; 311 ProgramStateRef state = Pred->getState(); 312 const LocationContext *LCtx = Pred->getLocationContext(); 313 314 switch (CastE->getCastKind()) { 315 case CK_LValueToRValue: 316 llvm_unreachable("LValueToRValue casts handled earlier."); 317 case CK_ToVoid: 318 continue; 319 // The analyzer doesn't do anything special with these casts, 320 // since it understands retain/release semantics already. 321 case CK_ARCProduceObject: 322 case CK_ARCConsumeObject: 323 case CK_ARCReclaimReturnedObject: 324 case CK_ARCExtendBlockObject: // Fall-through. 325 case CK_CopyAndAutoreleaseBlockObject: 326 // The analyser can ignore atomic casts for now, although some future 327 // checkers may want to make certain that you're not modifying the same 328 // value through atomic and nonatomic pointers. 329 case CK_AtomicToNonAtomic: 330 case CK_NonAtomicToAtomic: 331 // True no-ops. 332 case CK_NoOp: 333 case CK_ConstructorConversion: 334 case CK_UserDefinedConversion: 335 case CK_FunctionToPointerDecay: 336 case CK_BuiltinFnToFnPtr: { 337 // Copy the SVal of Ex to CastE. 338 ProgramStateRef state = Pred->getState(); 339 const LocationContext *LCtx = Pred->getLocationContext(); 340 SVal V = state->getSVal(Ex, LCtx); 341 state = state->BindExpr(CastE, LCtx, V); 342 Bldr.generateNode(CastE, Pred, state); 343 continue; 344 } 345 case CK_MemberPointerToBoolean: 346 case CK_PointerToBoolean: { 347 SVal V = state->getSVal(Ex, LCtx); 348 auto PTMSV = V.getAs<nonloc::PointerToMember>(); 349 if (PTMSV) 350 V = svalBuilder.makeTruthVal(!PTMSV->isNullMemberPointer(), ExTy); 351 if (V.isUndef() || PTMSV) { 352 state = state->BindExpr(CastE, LCtx, V); 353 Bldr.generateNode(CastE, Pred, state); 354 continue; 355 } 356 // Explicitly proceed with default handler for this case cascade. 357 state = 358 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred); 359 continue; 360 } 361 case CK_Dependent: 362 case CK_ArrayToPointerDecay: 363 case CK_BitCast: 364 case CK_AddressSpaceConversion: 365 case CK_BooleanToSignedIntegral: 366 case CK_NullToPointer: 367 case CK_IntegralToPointer: 368 case CK_PointerToIntegral: { 369 SVal V = state->getSVal(Ex, LCtx); 370 if (V.getAs<nonloc::PointerToMember>()) { 371 state = state->BindExpr(CastE, LCtx, UnknownVal()); 372 Bldr.generateNode(CastE, Pred, state); 373 continue; 374 } 375 // Explicitly proceed with default handler for this case cascade. 376 state = 377 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred); 378 continue; 379 } 380 case CK_IntegralToBoolean: 381 case CK_IntegralToFloating: 382 case CK_FloatingToIntegral: 383 case CK_FloatingToBoolean: 384 case CK_FloatingCast: 385 case CK_FloatingRealToComplex: 386 case CK_FloatingComplexToReal: 387 case CK_FloatingComplexToBoolean: 388 case CK_FloatingComplexCast: 389 case CK_FloatingComplexToIntegralComplex: 390 case CK_IntegralRealToComplex: 391 case CK_IntegralComplexToReal: 392 case CK_IntegralComplexToBoolean: 393 case CK_IntegralComplexCast: 394 case CK_IntegralComplexToFloatingComplex: 395 case CK_CPointerToObjCPointerCast: 396 case CK_BlockPointerToObjCPointerCast: 397 case CK_AnyPointerToBlockPointerCast: 398 case CK_ObjCObjectLValueCast: 399 case CK_ZeroToOCLEvent: 400 case CK_ZeroToOCLQueue: 401 case CK_IntToOCLSampler: 402 case CK_LValueBitCast: { 403 state = 404 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred); 405 continue; 406 } 407 case CK_IntegralCast: { 408 // Delegate to SValBuilder to process. 409 SVal V = state->getSVal(Ex, LCtx); 410 V = svalBuilder.evalIntegralCast(state, V, T, ExTy); 411 state = state->BindExpr(CastE, LCtx, V); 412 Bldr.generateNode(CastE, Pred, state); 413 continue; 414 } 415 case CK_DerivedToBase: 416 case CK_UncheckedDerivedToBase: { 417 // For DerivedToBase cast, delegate to the store manager. 418 SVal val = state->getSVal(Ex, LCtx); 419 val = getStoreManager().evalDerivedToBase(val, CastE); 420 state = state->BindExpr(CastE, LCtx, val); 421 Bldr.generateNode(CastE, Pred, state); 422 continue; 423 } 424 // Handle C++ dyn_cast. 425 case CK_Dynamic: { 426 SVal val = state->getSVal(Ex, LCtx); 427 428 // Compute the type of the result. 429 QualType resultType = CastE->getType(); 430 if (CastE->isGLValue()) 431 resultType = getContext().getPointerType(resultType); 432 433 bool Failed = false; 434 435 // Check if the value being cast evaluates to 0. 436 if (val.isZeroConstant()) 437 Failed = true; 438 // Else, evaluate the cast. 439 else 440 val = getStoreManager().attemptDownCast(val, T, Failed); 441 442 if (Failed) { 443 if (T->isReferenceType()) { 444 // A bad_cast exception is thrown if input value is a reference. 445 // Currently, we model this, by generating a sink. 446 Bldr.generateSink(CastE, Pred, state); 447 continue; 448 } else { 449 // If the cast fails on a pointer, bind to 0. 450 state = state->BindExpr(CastE, LCtx, svalBuilder.makeNull()); 451 } 452 } else { 453 // If we don't know if the cast succeeded, conjure a new symbol. 454 if (val.isUnknown()) { 455 DefinedOrUnknownSVal NewSym = 456 svalBuilder.conjureSymbolVal(nullptr, CastE, LCtx, resultType, 457 currBldrCtx->blockCount()); 458 state = state->BindExpr(CastE, LCtx, NewSym); 459 } else 460 // Else, bind to the derived region value. 461 state = state->BindExpr(CastE, LCtx, val); 462 } 463 Bldr.generateNode(CastE, Pred, state); 464 continue; 465 } 466 case CK_BaseToDerived: { 467 SVal val = state->getSVal(Ex, LCtx); 468 QualType resultType = CastE->getType(); 469 if (CastE->isGLValue()) 470 resultType = getContext().getPointerType(resultType); 471 472 bool Failed = false; 473 474 if (!val.isConstant()) { 475 val = getStoreManager().attemptDownCast(val, T, Failed); 476 } 477 478 // Failed to cast or the result is unknown, fall back to conservative. 479 if (Failed || val.isUnknown()) { 480 val = 481 svalBuilder.conjureSymbolVal(nullptr, CastE, LCtx, resultType, 482 currBldrCtx->blockCount()); 483 } 484 state = state->BindExpr(CastE, LCtx, val); 485 Bldr.generateNode(CastE, Pred, state); 486 continue; 487 } 488 case CK_NullToMemberPointer: { 489 SVal V = svalBuilder.getMemberPointer(nullptr); 490 state = state->BindExpr(CastE, LCtx, V); 491 Bldr.generateNode(CastE, Pred, state); 492 continue; 493 } 494 case CK_DerivedToBaseMemberPointer: 495 case CK_BaseToDerivedMemberPointer: 496 case CK_ReinterpretMemberPointer: { 497 SVal V = state->getSVal(Ex, LCtx); 498 if (auto PTMSV = V.getAs<nonloc::PointerToMember>()) { 499 SVal CastedPTMSV = svalBuilder.makePointerToMember( 500 getBasicVals().accumCXXBase( 501 llvm::make_range<CastExpr::path_const_iterator>( 502 CastE->path_begin(), CastE->path_end()), *PTMSV)); 503 state = state->BindExpr(CastE, LCtx, CastedPTMSV); 504 Bldr.generateNode(CastE, Pred, state); 505 continue; 506 } 507 // Explicitly proceed with default handler for this case cascade. 508 state = handleLVectorSplat(state, LCtx, CastE, Bldr, Pred); 509 continue; 510 } 511 // Various C++ casts that are not handled yet. 512 case CK_ToUnion: 513 case CK_VectorSplat: { 514 state = handleLVectorSplat(state, LCtx, CastE, Bldr, Pred); 515 continue; 516 } 517 } 518 } 519} 520 521void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL, 522 ExplodedNode *Pred, 523 ExplodedNodeSet &Dst) { 524 StmtNodeBuilder B(Pred, Dst, *currBldrCtx); 525 526 ProgramStateRef State = Pred->getState(); 527 const LocationContext *LCtx = Pred->getLocationContext(); 528 529 const Expr *Init = CL->getInitializer(); 530 SVal V = State->getSVal(CL->getInitializer(), LCtx); 531 532 if (isa<CXXConstructExpr>(Init)) { 533 // No work needed. Just pass the value up to this expression. 534 } else { 535 assert(isa<InitListExpr>(Init)); 536 Loc CLLoc = State->getLValue(CL, LCtx); 537 State = State->bindLoc(CLLoc, V); 538 539 if (CL->isGLValue()) 540 V = CLLoc; 541 } 542 543 B.generateNode(CL, Pred, State->BindExpr(CL, LCtx, V)); 544} 545 546void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, 547 ExplodedNodeSet &Dst) { 548 // Assumption: The CFG has one DeclStmt per Decl. 549 const VarDecl *VD = dyn_cast_or_null<VarDecl>(*DS->decl_begin()); 550 551 if (!VD) { 552 //TODO:AZ: remove explicit insertion after refactoring is done. 553 Dst.insert(Pred); 554 return; 555 } 556 557 // FIXME: all pre/post visits should eventually be handled by ::Visit(). 558 ExplodedNodeSet dstPreVisit; 559 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, DS, *this); 560 561 ExplodedNodeSet dstEvaluated; 562 StmtNodeBuilder B(dstPreVisit, dstEvaluated, *currBldrCtx); 563 for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end(); 564 I!=E; ++I) { 565 ExplodedNode *N = *I; 566 ProgramStateRef state = N->getState(); 567 const LocationContext *LC = N->getLocationContext(); 568 569 // Decls without InitExpr are not initialized explicitly. 570 if (const Expr *InitEx = VD->getInit()) { 571 572 // Note in the state that the initialization has occurred. 573 ExplodedNode *UpdatedN = N; 574 SVal InitVal = state->getSVal(InitEx, LC); 575 576 assert(DS->isSingleDecl()); 577 if (auto *CtorExpr = findDirectConstructorForCurrentCFGElement()) { 578 assert(InitEx->IgnoreImplicit() == CtorExpr); 579 (void)CtorExpr; 580 // We constructed the object directly in the variable. 581 // No need to bind anything. 582 B.generateNode(DS, UpdatedN, state); 583 } else { 584 // We bound the temp obj region to the CXXConstructExpr. Now recover 585 // the lazy compound value when the variable is not a reference. 586 if (AMgr.getLangOpts().CPlusPlus && VD->getType()->isRecordType() && 587 !VD->getType()->isReferenceType()) { 588 if (Optional<loc::MemRegionVal> M = 589 InitVal.getAs<loc::MemRegionVal>()) { 590 InitVal = state->getSVal(M->getRegion()); 591 assert(InitVal.getAs<nonloc::LazyCompoundVal>()); 592 } 593 } 594 595 // Recover some path-sensitivity if a scalar value evaluated to 596 // UnknownVal. 597 if (InitVal.isUnknown()) { 598 QualType Ty = InitEx->getType(); 599 if (InitEx->isGLValue()) { 600 Ty = getContext().getPointerType(Ty); 601 } 602 603 InitVal = svalBuilder.conjureSymbolVal(nullptr, InitEx, LC, Ty, 604 currBldrCtx->blockCount()); 605 } 606 607 608 B.takeNodes(UpdatedN); 609 ExplodedNodeSet Dst2; 610 evalBind(Dst2, DS, UpdatedN, state->getLValue(VD, LC), InitVal, true); 611 B.addNodes(Dst2); 612 } 613 } 614 else { 615 B.generateNode(DS, N, state); 616 } 617 } 618 619 getCheckerManager().runCheckersForPostStmt(Dst, B.getResults(), DS, *this); 620} 621 622void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, 623 ExplodedNodeSet &Dst) { 624 assert(B->getOpcode() == BO_LAnd || 625 B->getOpcode() == BO_LOr); 626 627 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); 628 ProgramStateRef state = Pred->getState(); 629 630 ExplodedNode *N = Pred; 631 while (!N->getLocation().getAs<BlockEntrance>()) { 632 ProgramPoint P = N->getLocation(); 633 assert(P.getAs<PreStmt>()|| P.getAs<PreStmtPurgeDeadSymbols>()); 634 (void) P; 635 assert(N->pred_size() == 1); 636 N = *N->pred_begin(); 637 } 638 assert(N->pred_size() == 1); 639 N = *N->pred_begin(); 640 BlockEdge BE = N->getLocation().castAs<BlockEdge>(); 641 SVal X; 642 643 // Determine the value of the expression by introspecting how we 644 // got this location in the CFG. This requires looking at the previous 645 // block we were in and what kind of control-flow transfer was involved. 646 const CFGBlock *SrcBlock = BE.getSrc(); 647 // The only terminator (if there is one) that makes sense is a logical op. 648 CFGTerminator T = SrcBlock->getTerminator(); 649 if (const BinaryOperator *Term = cast_or_null<BinaryOperator>(T.getStmt())) { 650 (void) Term; 651 assert(Term->isLogicalOp()); 652 assert(SrcBlock->succ_size() == 2); 653 // Did we take the true or false branch? 654 unsigned constant = (*SrcBlock->succ_begin() == BE.getDst()) ? 1 : 0; 655 X = svalBuilder.makeIntVal(constant, B->getType()); 656 } 657 else { 658 // If there is no terminator, by construction the last statement 659 // in SrcBlock is the value of the enclosing expression. 660 // However, we still need to constrain that value to be 0 or 1. 661 assert(!SrcBlock->empty()); 662 CFGStmt Elem = SrcBlock->rbegin()->castAs<CFGStmt>(); 663 const Expr *RHS = cast<Expr>(Elem.getStmt()); 664 SVal RHSVal = N->getState()->getSVal(RHS, Pred->getLocationContext()); 665 666 if (RHSVal.isUndef()) { 667 X = RHSVal; 668 } else { 669 // We evaluate "RHSVal != 0" expression which result in 0 if the value is 670 // known to be false, 1 if the value is known to be true and a new symbol 671 // when the assumption is unknown. 672 nonloc::ConcreteInt Zero(getBasicVals().getValue(0, B->getType())); 673 X = evalBinOp(N->getState(), BO_NE, 674 svalBuilder.evalCast(RHSVal, B->getType(), RHS->getType()), 675 Zero, B->getType()); 676 } 677 } 678 Bldr.generateNode(B, Pred, state->BindExpr(B, Pred->getLocationContext(), X)); 679} 680 681void ExprEngine::VisitInitListExpr(const InitListExpr *IE, 682 ExplodedNode *Pred, 683 ExplodedNodeSet &Dst) { 684 StmtNodeBuilder B(Pred, Dst, *currBldrCtx); 685 686 ProgramStateRef state = Pred->getState(); 687 const LocationContext *LCtx = Pred->getLocationContext(); 688 QualType T = getContext().getCanonicalType(IE->getType()); 689 unsigned NumInitElements = IE->getNumInits(); 690 691 if (!IE->isGLValue() && 692 (T->isArrayType() || T->isRecordType() || T->isVectorType() || 693 T->isAnyComplexType())) { 694 llvm::ImmutableList<SVal> vals = getBasicVals().getEmptySValList(); 695 696 // Handle base case where the initializer has no elements. 697 // e.g: static int* myArray[] = {}; 698 if (NumInitElements == 0) { 699 SVal V = svalBuilder.makeCompoundVal(T, vals); 700 B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V)); 701 return; 702 } 703 704 for (InitListExpr::const_reverse_iterator it = IE->rbegin(), 705 ei = IE->rend(); it != ei; ++it) { 706 SVal V = state->getSVal(cast<Expr>(*it), LCtx); 707 vals = getBasicVals().prependSVal(V, vals); 708 } 709 710 B.generateNode(IE, Pred, 711 state->BindExpr(IE, LCtx, 712 svalBuilder.makeCompoundVal(T, vals))); 713 return; 714 } 715 716 // Handle scalars: int{5} and int{} and GLvalues. 717 // Note, if the InitListExpr is a GLvalue, it means that there is an address 718 // representing it, so it must have a single init element. 719 assert(NumInitElements <= 1); 720 721 SVal V; 722 if (NumInitElements == 0) 723 V = getSValBuilder().makeZeroVal(T); 724 else 725 V = state->getSVal(IE->getInit(0), LCtx); 726 727 B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V)); 728} 729 730void ExprEngine::VisitGuardedExpr(const Expr *Ex, 731 const Expr *L, 732 const Expr *R, 733 ExplodedNode *Pred, 734 ExplodedNodeSet &Dst) { 735 assert(L && R); 736 737 StmtNodeBuilder B(Pred, Dst, *currBldrCtx); 738 ProgramStateRef state = Pred->getState(); 739 const LocationContext *LCtx = Pred->getLocationContext(); 740 const CFGBlock *SrcBlock = nullptr; 741 742 // Find the predecessor block. 743 ProgramStateRef SrcState = state; 744 for (const ExplodedNode *N = Pred ; N ; N = *N->pred_begin()) { 745 ProgramPoint PP = N->getLocation(); 746 if (PP.getAs<PreStmtPurgeDeadSymbols>() || PP.getAs<BlockEntrance>()) { 747 assert(N->pred_size() == 1); 748 continue; 749 } 750 SrcBlock = PP.castAs<BlockEdge>().getSrc(); 751 SrcState = N->getState(); 752 break; 753 } 754 755 assert(SrcBlock && "missing function entry"); 756 757 // Find the last expression in the predecessor block. That is the 758 // expression that is used for the value of the ternary expression. 759 bool hasValue = false; 760 SVal V; 761 762 for (CFGElement CE : llvm::reverse(*SrcBlock)) { 763 if (Optional<CFGStmt> CS = CE.getAs<CFGStmt>()) { 764 const Expr *ValEx = cast<Expr>(CS->getStmt()); 765 ValEx = ValEx->IgnoreParens(); 766 767 // For GNU extension '?:' operator, the left hand side will be an 768 // OpaqueValueExpr, so get the underlying expression. 769 if (const OpaqueValueExpr *OpaqueEx = dyn_cast<OpaqueValueExpr>(L)) 770 L = OpaqueEx->getSourceExpr(); 771 772 // If the last expression in the predecessor block matches true or false 773 // subexpression, get its the value. 774 if (ValEx == L->IgnoreParens() || ValEx == R->IgnoreParens()) { 775 hasValue = true; 776 V = SrcState->getSVal(ValEx, LCtx); 777 } 778 break; 779 } 780 } 781 782 if (!hasValue) 783 V = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx, 784 currBldrCtx->blockCount()); 785 786 // Generate a new node with the binding from the appropriate path. 787 B.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V, true)); 788} 789 790void ExprEngine:: 791VisitOffsetOfExpr(const OffsetOfExpr *OOE, 792 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 793 StmtNodeBuilder B(Pred, Dst, *currBldrCtx); 794 APSInt IV; 795 if (OOE->EvaluateAsInt(IV, getContext())) { 796 assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType())); 797 assert(OOE->getType()->isBuiltinType()); 798 assert(OOE->getType()->getAs<BuiltinType>()->isInteger()); 799 assert(IV.isSigned() == OOE->getType()->isSignedIntegerType()); 800 SVal X = svalBuilder.makeIntVal(IV); 801 B.generateNode(OOE, Pred, 802 Pred->getState()->BindExpr(OOE, Pred->getLocationContext(), 803 X)); 804 } 805 // FIXME: Handle the case where __builtin_offsetof is not a constant. 806} 807 808 809void ExprEngine:: 810VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex, 811 ExplodedNode *Pred, 812 ExplodedNodeSet &Dst) { 813 // FIXME: Prechecks eventually go in ::Visit(). 814 ExplodedNodeSet CheckedSet; 815 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, Ex, *this); 816 817 ExplodedNodeSet EvalSet; 818 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx); 819 820 QualType T = Ex->getTypeOfArgument(); 821 822 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 823 I != E; ++I) { 824 if (Ex->getKind() == UETT_SizeOf) { 825 if (!T->isIncompleteType() && !T->isConstantSizeType()) { 826 assert(T->isVariableArrayType() && "Unknown non-constant-sized type."); 827 828 // FIXME: Add support for VLA type arguments and VLA expressions. 829 // When that happens, we should probably refactor VLASizeChecker's code. 830 continue; 831 } else if (T->getAs<ObjCObjectType>()) { 832 // Some code tries to take the sizeof an ObjCObjectType, relying that 833 // the compiler has laid out its representation. Just report Unknown 834 // for these. 835 continue; 836 } 837 } 838 839 APSInt Value = Ex->EvaluateKnownConstInt(getContext()); 840 CharUnits amt = CharUnits::fromQuantity(Value.getZExtValue()); 841 842 ProgramStateRef state = (*I)->getState(); 843 state = state->BindExpr(Ex, (*I)->getLocationContext(), 844 svalBuilder.makeIntVal(amt.getQuantity(), 845 Ex->getType())); 846 Bldr.generateNode(Ex, *I, state); 847 } 848 849 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, Ex, *this); 850} 851 852void ExprEngine::handleUOExtension(ExplodedNodeSet::iterator I, 853 const UnaryOperator *U, 854 StmtNodeBuilder &Bldr) { 855 // FIXME: We can probably just have some magic in Environment::getSVal() 856 // that propagates values, instead of creating a new node here. 857 // 858 // Unary "+" is a no-op, similar to a parentheses. We still have places 859 // where it may be a block-level expression, so we need to 860 // generate an extra node that just propagates the value of the 861 // subexpression. 862 const Expr *Ex = U->getSubExpr()->IgnoreParens(); 863 ProgramStateRef state = (*I)->getState(); 864 const LocationContext *LCtx = (*I)->getLocationContext(); 865 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, 866 state->getSVal(Ex, LCtx))); 867} 868 869void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, ExplodedNode *Pred, 870 ExplodedNodeSet &Dst) { 871 // FIXME: Prechecks eventually go in ::Visit(). 872 ExplodedNodeSet CheckedSet; 873 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, U, *this); 874 875 ExplodedNodeSet EvalSet; 876 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx); 877 878 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 879 I != E; ++I) { 880 switch (U->getOpcode()) { 881 default: { 882 Bldr.takeNodes(*I); 883 ExplodedNodeSet Tmp; 884 VisitIncrementDecrementOperator(U, *I, Tmp); 885 Bldr.addNodes(Tmp); 886 break; 887 } 888 case UO_Real: { 889 const Expr *Ex = U->getSubExpr()->IgnoreParens(); 890 891 // FIXME: We don't have complex SValues yet. 892 if (Ex->getType()->isAnyComplexType()) { 893 // Just report "Unknown." 894 break; 895 } 896 897 // For all other types, UO_Real is an identity operation. 898 assert (U->getType() == Ex->getType()); 899 ProgramStateRef state = (*I)->getState(); 900 const LocationContext *LCtx = (*I)->getLocationContext(); 901 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, 902 state->getSVal(Ex, LCtx))); 903 break; 904 } 905 906 case UO_Imag: { 907 const Expr *Ex = U->getSubExpr()->IgnoreParens(); 908 // FIXME: We don't have complex SValues yet. 909 if (Ex->getType()->isAnyComplexType()) { 910 // Just report "Unknown." 911 break; 912 } 913 // For all other types, UO_Imag returns 0. 914 ProgramStateRef state = (*I)->getState(); 915 const LocationContext *LCtx = (*I)->getLocationContext(); 916 SVal X = svalBuilder.makeZeroVal(Ex->getType()); 917 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, X)); 918 break; 919 } 920 921 case UO_AddrOf: { 922 // Process pointer-to-member address operation. 923 const Expr *Ex = U->getSubExpr()->IgnoreParens(); 924 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Ex)) { 925 const ValueDecl *VD = DRE->getDecl(); 926 927 if (isa<CXXMethodDecl>(VD) || isa<FieldDecl>(VD)) { 928 ProgramStateRef State = (*I)->getState(); 929 const LocationContext *LCtx = (*I)->getLocationContext(); 930 SVal SV = svalBuilder.getMemberPointer(cast<DeclaratorDecl>(VD)); 931 Bldr.generateNode(U, *I, State->BindExpr(U, LCtx, SV)); 932 break; 933 } 934 } 935 // Explicitly proceed with default handler for this case cascade. 936 handleUOExtension(I, U, Bldr); 937 break; 938 } 939 case UO_Plus: 940 assert(!U->isGLValue()); 941 // FALL-THROUGH. 942 case UO_Deref: 943 case UO_Extension: { 944 handleUOExtension(I, U, Bldr); 945 break; 946 } 947 948 case UO_LNot: 949 case UO_Minus: 950 case UO_Not: { 951 assert (!U->isGLValue()); 952 const Expr *Ex = U->getSubExpr()->IgnoreParens(); 953 ProgramStateRef state = (*I)->getState(); 954 const LocationContext *LCtx = (*I)->getLocationContext(); 955 956 // Get the value of the subexpression. 957 SVal V = state->getSVal(Ex, LCtx); 958 959 if (V.isUnknownOrUndef()) { 960 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V)); 961 break; 962 } 963 964 switch (U->getOpcode()) { 965 default: 966 llvm_unreachable("Invalid Opcode."); 967 case UO_Not: 968 // FIXME: Do we need to handle promotions? 969 state = state->BindExpr(U, LCtx, evalComplement(V.castAs<NonLoc>())); 970 break; 971 case UO_Minus: 972 // FIXME: Do we need to handle promotions? 973 state = state->BindExpr(U, LCtx, evalMinus(V.castAs<NonLoc>())); 974 break; 975 case UO_LNot: 976 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)." 977 // 978 // Note: technically we do "E == 0", but this is the same in the 979 // transfer functions as "0 == E". 980 SVal Result; 981 if (Optional<Loc> LV = V.getAs<Loc>()) { 982 Loc X = svalBuilder.makeNull(); 983 Result = evalBinOp(state, BO_EQ, *LV, X, U->getType()); 984 } 985 else if (Ex->getType()->isFloatingType()) { 986 // FIXME: handle floating point types. 987 Result = UnknownVal(); 988 } else { 989 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType())); 990 Result = evalBinOp(state, BO_EQ, V.castAs<NonLoc>(), X, 991 U->getType()); 992 } 993 994 state = state->BindExpr(U, LCtx, Result); 995 break; 996 } 997 Bldr.generateNode(U, *I, state); 998 break; 999 } 1000 } 1001 } 1002 1003 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, U, *this); 1004} 1005 1006void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U, 1007 ExplodedNode *Pred, 1008 ExplodedNodeSet &Dst) { 1009 // Handle ++ and -- (both pre- and post-increment). 1010 assert (U->isIncrementDecrementOp()); 1011 const Expr *Ex = U->getSubExpr()->IgnoreParens(); 1012 1013 const LocationContext *LCtx = Pred->getLocationContext(); 1014 ProgramStateRef state = Pred->getState(); 1015 SVal loc = state->getSVal(Ex, LCtx); 1016 1017 // Perform a load. 1018 ExplodedNodeSet Tmp; 1019 evalLoad(Tmp, U, Ex, Pred, state, loc); 1020 1021 ExplodedNodeSet Dst2; 1022 StmtNodeBuilder Bldr(Tmp, Dst2, *currBldrCtx); 1023 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end();I!=E;++I) { 1024 1025 state = (*I)->getState(); 1026 assert(LCtx == (*I)->getLocationContext()); 1027 SVal V2_untested = state->getSVal(Ex, LCtx); 1028 1029 // Propagate unknown and undefined values. 1030 if (V2_untested.isUnknownOrUndef()) { 1031 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V2_untested)); 1032 continue; 1033 } 1034 DefinedSVal V2 = V2_untested.castAs<DefinedSVal>(); 1035 1036 // Handle all other values. 1037 BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add : BO_Sub; 1038 1039 // If the UnaryOperator has non-location type, use its type to create the 1040 // constant value. If the UnaryOperator has location type, create the 1041 // constant with int type and pointer width. 1042 SVal RHS; 1043 1044 if (U->getType()->isAnyPointerType()) 1045 RHS = svalBuilder.makeArrayIndex(1); 1046 else if (U->getType()->isIntegralOrEnumerationType()) 1047 RHS = svalBuilder.makeIntVal(1, U->getType()); 1048 else 1049 RHS = UnknownVal(); 1050 1051 SVal Result = evalBinOp(state, Op, V2, RHS, U->getType()); 1052 1053 // Conjure a new symbol if necessary to recover precision. 1054 if (Result.isUnknown()){ 1055 DefinedOrUnknownSVal SymVal = 1056 svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx, 1057 currBldrCtx->blockCount()); 1058 Result = SymVal; 1059 1060 // If the value is a location, ++/-- should always preserve 1061 // non-nullness. Check if the original value was non-null, and if so 1062 // propagate that constraint. 1063 if (Loc::isLocType(U->getType())) { 1064 DefinedOrUnknownSVal Constraint = 1065 svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType())); 1066 1067 if (!state->assume(Constraint, true)) { 1068 // It isn't feasible for the original value to be null. 1069 // Propagate this constraint. 1070 Constraint = svalBuilder.evalEQ(state, SymVal, 1071 svalBuilder.makeZeroVal(U->getType())); 1072 1073 1074 state = state->assume(Constraint, false); 1075 assert(state); 1076 } 1077 } 1078 } 1079 1080 // Since the lvalue-to-rvalue conversion is explicit in the AST, 1081 // we bind an l-value if the operator is prefix and an lvalue (in C++). 1082 if (U->isGLValue()) 1083 state = state->BindExpr(U, LCtx, loc); 1084 else 1085 state = state->BindExpr(U, LCtx, U->isPostfix() ? V2 : Result); 1086 1087 // Perform the store. 1088 Bldr.takeNodes(*I); 1089 ExplodedNodeSet Dst3; 1090 evalStore(Dst3, U, U, *I, state, loc, Result); 1091 Bldr.addNodes(Dst3); 1092 } 1093 Dst.insert(Dst2); 1094} 1095