1 //=-- ExprEngineC.cpp - ExprEngine support for C expressions ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines ExprEngine's support for C expressions.
12 //===----------------------------------------------------------------------===//
14 #include "clang/AST/ExprCXX.h"
15 #include "clang/AST/DeclCXX.h"
16 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
19 using namespace clang;
23 void ExprEngine::VisitBinaryOperator(const BinaryOperator* B,
25 ExplodedNodeSet &Dst) {
27 Expr *LHS = B->getLHS()->IgnoreParens();
28 Expr *RHS = B->getRHS()->IgnoreParens();
30 // FIXME: Prechecks eventually go in ::Visit().
31 ExplodedNodeSet CheckedSet;
33 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, B, *this);
35 // With both the LHS and RHS evaluated, process the operation itself.
36 for (ExplodedNodeSet::iterator it=CheckedSet.begin(), ei=CheckedSet.end();
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);
44 BinaryOperator::Opcode Op = B->getOpcode();
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,
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),
62 if (!B->isAssignmentOp()) {
63 StmtNodeBuilder Bldr(*it, Tmp2, *currBldrCtx);
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
71 unsigned Count = currBldrCtx->blockCount();
72 if (LeftV.getAs<Loc>() &&
73 RHS->getType()->isIntegralOrEnumerationType() &&
75 RightV = svalBuilder.conjureSymbolVal(RHS, LCtx, RHS->getType(),
78 if (RightV.getAs<Loc>() &&
79 LHS->getType()->isIntegralOrEnumerationType() &&
81 LeftV = svalBuilder.conjureSymbolVal(LHS, LCtx, LHS->getType(),
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
89 if (B->getOpcode() == BO_PtrMemD)
90 state = createTemporaryRegionIfNeeded(state, LCtx, LHS);
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);
100 state = state->BindExpr(B, LCtx, Result);
101 Bldr.generateNode(B, *it, state);
105 assert (B->isCompoundAssignmentOp());
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;
122 // Perform a load (the LHS). This performs the checks for
123 // null dereferences, and so on.
125 SVal location = LeftV;
126 evalLoad(Tmp, B, LHS, *it, state, location);
128 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E;
131 state = (*I)->getState();
132 const LocationContext *LCtx = (*I)->getLocationContext();
133 SVal V = state->getSVal(LHS, LCtx);
135 // Get the computation type.
137 cast<CompoundAssignOperator>(B)->getComputationResultType();
138 CTy = getContext().getCanonicalType(CTy);
141 cast<CompoundAssignOperator>(B)->getComputationLHSType();
142 CLHSTy = getContext().getCanonicalType(CLHSTy);
144 QualType LTy = getContext().getCanonicalType(LHS->getType());
147 V = svalBuilder.evalCast(V, CLHSTy, LTy);
149 // Compute the result of the operation.
150 SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy),
153 // EXPERIMENTAL: "Conjured" symbols.
154 // FIXME: Handle structs.
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);
168 // The left-hand side may bind to a different value then the
170 LHSVal = svalBuilder.evalCast(Result, LTy, CTy);
173 // In C++, assignment and compound assignment operators return an
176 state = state->BindExpr(B, LCtx, location);
178 state = state->BindExpr(B, LCtx, Result);
180 evalStore(Tmp2, B, LHS, *I, state, location, LHSVal);
184 // FIXME: postvisits eventually go in ::Visit()
185 getCheckerManager().runCheckersForPostStmt(Dst, Tmp2, B, *this);
188 void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
189 ExplodedNodeSet &Dst) {
191 CanQualType T = getContext().getCanonicalType(BE->getType());
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());
199 ProgramStateRef State = Pred->getState();
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())) {
206 BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
207 E = BDR->referenced_vars_end();
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();
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;
223 assert(CI->getVariable() == capturedR->getDecl());
224 copyExpr = CI->getCopyExpr();
228 if (capturedR != originalR) {
230 const LocationContext *LCtx = Pred->getLocationContext();
232 originalV = State->getSVal(copyExpr, LCtx);
234 originalV = State->getSVal(loc::MemRegionVal(originalR));
236 State = State->bindLoc(loc::MemRegionVal(capturedR), originalV, LCtx);
242 StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
243 Bldr.generateNode(BE, Pred,
244 State->BindExpr(BE, Pred->getLocationContext(), V),
245 nullptr, ProgramPoint::PostLValueKind);
247 // FIXME: Move all post/pre visits to ::Visit().
248 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this);
251 ProgramStateRef ExprEngine::handleLValueBitCast(
252 ProgramStateRef state, const Expr* Ex, const LocationContext* LCtx,
253 QualType T, QualType ExTy, const CastExpr* CastE, StmtNodeBuilder& Bldr,
254 ExplodedNode* Pred) {
255 // Delegate to SValBuilder to process.
256 SVal V = state->getSVal(Ex, LCtx);
257 V = svalBuilder.evalCast(V, T, ExTy);
258 // Negate the result if we're treating the boolean as a signed i1
259 if (CastE->getCastKind() == CK_BooleanToSignedIntegral)
261 state = state->BindExpr(CastE, LCtx, V);
262 Bldr.generateNode(CastE, Pred, state);
267 ProgramStateRef ExprEngine::handleLVectorSplat(
268 ProgramStateRef state, const LocationContext* LCtx, const CastExpr* CastE,
269 StmtNodeBuilder &Bldr, ExplodedNode* Pred) {
270 // Recover some path sensitivity by conjuring a new value.
271 QualType resultType = CastE->getType();
272 if (CastE->isGLValue())
273 resultType = getContext().getPointerType(resultType);
274 SVal result = svalBuilder.conjureSymbolVal(nullptr, CastE, LCtx,
276 currBldrCtx->blockCount());
277 state = state->BindExpr(CastE, LCtx, result);
278 Bldr.generateNode(CastE, Pred, state);
283 void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,
284 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
286 ExplodedNodeSet dstPreStmt;
287 getCheckerManager().runCheckersForPreStmt(dstPreStmt, Pred, CastE, *this);
289 if (CastE->getCastKind() == CK_LValueToRValue) {
290 for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end();
292 ExplodedNode *subExprNode = *I;
293 ProgramStateRef state = subExprNode->getState();
294 const LocationContext *LCtx = subExprNode->getLocationContext();
295 evalLoad(Dst, CastE, CastE, subExprNode, state, state->getSVal(Ex, LCtx));
301 QualType T = CastE->getType();
302 QualType ExTy = Ex->getType();
304 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE))
305 T = ExCast->getTypeAsWritten();
307 StmtNodeBuilder Bldr(dstPreStmt, Dst, *currBldrCtx);
308 for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end();
312 ProgramStateRef state = Pred->getState();
313 const LocationContext *LCtx = Pred->getLocationContext();
315 switch (CastE->getCastKind()) {
316 case CK_LValueToRValue:
317 llvm_unreachable("LValueToRValue casts handled earlier.");
320 // The analyzer doesn't do anything special with these casts,
321 // since it understands retain/release semantics already.
322 case CK_ARCProduceObject:
323 case CK_ARCConsumeObject:
324 case CK_ARCReclaimReturnedObject:
325 case CK_ARCExtendBlockObject: // Fall-through.
326 case CK_CopyAndAutoreleaseBlockObject:
327 // The analyser can ignore atomic casts for now, although some future
328 // checkers may want to make certain that you're not modifying the same
329 // value through atomic and nonatomic pointers.
330 case CK_AtomicToNonAtomic:
331 case CK_NonAtomicToAtomic:
334 case CK_ConstructorConversion:
335 case CK_UserDefinedConversion:
336 case CK_FunctionToPointerDecay:
337 case CK_BuiltinFnToFnPtr: {
338 // Copy the SVal of Ex to CastE.
339 ProgramStateRef state = Pred->getState();
340 const LocationContext *LCtx = Pred->getLocationContext();
341 SVal V = state->getSVal(Ex, LCtx);
342 state = state->BindExpr(CastE, LCtx, V);
343 Bldr.generateNode(CastE, Pred, state);
346 case CK_MemberPointerToBoolean:
347 case CK_PointerToBoolean: {
348 SVal V = state->getSVal(Ex, LCtx);
349 auto PTMSV = V.getAs<nonloc::PointerToMember>();
351 V = svalBuilder.makeTruthVal(!PTMSV->isNullMemberPointer(), ExTy);
352 if (V.isUndef() || PTMSV) {
353 state = state->BindExpr(CastE, LCtx, V);
354 Bldr.generateNode(CastE, Pred, state);
357 // Explicitly proceed with default handler for this case cascade.
359 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred);
363 case CK_ArrayToPointerDecay:
365 case CK_AddressSpaceConversion:
366 case CK_BooleanToSignedIntegral:
367 case CK_NullToPointer:
368 case CK_IntegralToPointer:
369 case CK_PointerToIntegral: {
370 SVal V = state->getSVal(Ex, LCtx);
371 if (V.getAs<nonloc::PointerToMember>()) {
372 state = state->BindExpr(CastE, LCtx, UnknownVal());
373 Bldr.generateNode(CastE, Pred, state);
376 // Explicitly proceed with default handler for this case cascade.
378 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred);
381 case CK_IntegralToBoolean:
382 case CK_IntegralToFloating:
383 case CK_FloatingToIntegral:
384 case CK_FloatingToBoolean:
385 case CK_FloatingCast:
386 case CK_FloatingRealToComplex:
387 case CK_FloatingComplexToReal:
388 case CK_FloatingComplexToBoolean:
389 case CK_FloatingComplexCast:
390 case CK_FloatingComplexToIntegralComplex:
391 case CK_IntegralRealToComplex:
392 case CK_IntegralComplexToReal:
393 case CK_IntegralComplexToBoolean:
394 case CK_IntegralComplexCast:
395 case CK_IntegralComplexToFloatingComplex:
396 case CK_CPointerToObjCPointerCast:
397 case CK_BlockPointerToObjCPointerCast:
398 case CK_AnyPointerToBlockPointerCast:
399 case CK_ObjCObjectLValueCast:
400 case CK_ZeroToOCLEvent:
401 case CK_ZeroToOCLQueue:
402 case CK_IntToOCLSampler:
403 case CK_LValueBitCast: {
405 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred);
408 case CK_IntegralCast: {
409 // Delegate to SValBuilder to process.
410 SVal V = state->getSVal(Ex, LCtx);
411 V = svalBuilder.evalIntegralCast(state, V, T, ExTy);
412 state = state->BindExpr(CastE, LCtx, V);
413 Bldr.generateNode(CastE, Pred, state);
416 case CK_DerivedToBase:
417 case CK_UncheckedDerivedToBase: {
418 // For DerivedToBase cast, delegate to the store manager.
419 SVal val = state->getSVal(Ex, LCtx);
420 val = getStoreManager().evalDerivedToBase(val, CastE);
421 state = state->BindExpr(CastE, LCtx, val);
422 Bldr.generateNode(CastE, Pred, state);
425 // Handle C++ dyn_cast.
427 SVal val = state->getSVal(Ex, LCtx);
429 // Compute the type of the result.
430 QualType resultType = CastE->getType();
431 if (CastE->isGLValue())
432 resultType = getContext().getPointerType(resultType);
436 // Check if the value being cast evaluates to 0.
437 if (val.isZeroConstant())
439 // Else, evaluate the cast.
441 val = getStoreManager().attemptDownCast(val, T, Failed);
444 if (T->isReferenceType()) {
445 // A bad_cast exception is thrown if input value is a reference.
446 // Currently, we model this, by generating a sink.
447 Bldr.generateSink(CastE, Pred, state);
450 // If the cast fails on a pointer, bind to 0.
451 state = state->BindExpr(CastE, LCtx, svalBuilder.makeNull());
454 // If we don't know if the cast succeeded, conjure a new symbol.
455 if (val.isUnknown()) {
456 DefinedOrUnknownSVal NewSym =
457 svalBuilder.conjureSymbolVal(nullptr, CastE, LCtx, resultType,
458 currBldrCtx->blockCount());
459 state = state->BindExpr(CastE, LCtx, NewSym);
461 // Else, bind to the derived region value.
462 state = state->BindExpr(CastE, LCtx, val);
464 Bldr.generateNode(CastE, Pred, state);
467 case CK_BaseToDerived: {
468 SVal val = state->getSVal(Ex, LCtx);
469 QualType resultType = CastE->getType();
470 if (CastE->isGLValue())
471 resultType = getContext().getPointerType(resultType);
475 if (!val.isConstant()) {
476 val = getStoreManager().attemptDownCast(val, T, Failed);
479 // Failed to cast or the result is unknown, fall back to conservative.
480 if (Failed || val.isUnknown()) {
482 svalBuilder.conjureSymbolVal(nullptr, CastE, LCtx, resultType,
483 currBldrCtx->blockCount());
485 state = state->BindExpr(CastE, LCtx, val);
486 Bldr.generateNode(CastE, Pred, state);
489 case CK_NullToMemberPointer: {
490 SVal V = svalBuilder.getMemberPointer(nullptr);
491 state = state->BindExpr(CastE, LCtx, V);
492 Bldr.generateNode(CastE, Pred, state);
495 case CK_DerivedToBaseMemberPointer:
496 case CK_BaseToDerivedMemberPointer:
497 case CK_ReinterpretMemberPointer: {
498 SVal V = state->getSVal(Ex, LCtx);
499 if (auto PTMSV = V.getAs<nonloc::PointerToMember>()) {
500 SVal CastedPTMSV = svalBuilder.makePointerToMember(
501 getBasicVals().accumCXXBase(
502 llvm::make_range<CastExpr::path_const_iterator>(
503 CastE->path_begin(), CastE->path_end()), *PTMSV));
504 state = state->BindExpr(CastE, LCtx, CastedPTMSV);
505 Bldr.generateNode(CastE, Pred, state);
508 // Explicitly proceed with default handler for this case cascade.
509 state = handleLVectorSplat(state, LCtx, CastE, Bldr, Pred);
512 // Various C++ casts that are not handled yet.
514 case CK_VectorSplat: {
515 state = handleLVectorSplat(state, LCtx, CastE, Bldr, Pred);
522 void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,
524 ExplodedNodeSet &Dst) {
525 StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
527 ProgramStateRef State = Pred->getState();
528 const LocationContext *LCtx = Pred->getLocationContext();
530 const Expr *Init = CL->getInitializer();
531 SVal V = State->getSVal(CL->getInitializer(), LCtx);
533 if (isa<CXXConstructExpr>(Init)) {
534 // No work needed. Just pass the value up to this expression.
536 assert(isa<InitListExpr>(Init));
537 Loc CLLoc = State->getLValue(CL, LCtx);
538 State = State->bindLoc(CLLoc, V, LCtx);
544 B.generateNode(CL, Pred, State->BindExpr(CL, LCtx, V));
547 void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
548 ExplodedNodeSet &Dst) {
549 // Assumption: The CFG has one DeclStmt per Decl.
550 const VarDecl *VD = dyn_cast_or_null<VarDecl>(*DS->decl_begin());
553 //TODO:AZ: remove explicit insertion after refactoring is done.
558 // FIXME: all pre/post visits should eventually be handled by ::Visit().
559 ExplodedNodeSet dstPreVisit;
560 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, DS, *this);
562 ExplodedNodeSet dstEvaluated;
563 StmtNodeBuilder B(dstPreVisit, dstEvaluated, *currBldrCtx);
564 for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
566 ExplodedNode *N = *I;
567 ProgramStateRef state = N->getState();
568 const LocationContext *LC = N->getLocationContext();
570 // Decls without InitExpr are not initialized explicitly.
571 if (const Expr *InitEx = VD->getInit()) {
573 // Note in the state that the initialization has occurred.
574 ExplodedNode *UpdatedN = N;
575 SVal InitVal = state->getSVal(InitEx, LC);
577 assert(DS->isSingleDecl());
578 if (auto *CtorExpr = findDirectConstructorForCurrentCFGElement()) {
579 assert(InitEx->IgnoreImplicit() == CtorExpr);
581 // We constructed the object directly in the variable.
582 // No need to bind anything.
583 B.generateNode(DS, UpdatedN, state);
585 // We bound the temp obj region to the CXXConstructExpr. Now recover
586 // the lazy compound value when the variable is not a reference.
587 if (AMgr.getLangOpts().CPlusPlus && VD->getType()->isRecordType() &&
588 !VD->getType()->isReferenceType()) {
589 if (Optional<loc::MemRegionVal> M =
590 InitVal.getAs<loc::MemRegionVal>()) {
591 InitVal = state->getSVal(M->getRegion());
592 assert(InitVal.getAs<nonloc::LazyCompoundVal>());
596 // Recover some path-sensitivity if a scalar value evaluated to
598 if (InitVal.isUnknown()) {
599 QualType Ty = InitEx->getType();
600 if (InitEx->isGLValue()) {
601 Ty = getContext().getPointerType(Ty);
604 InitVal = svalBuilder.conjureSymbolVal(nullptr, InitEx, LC, Ty,
605 currBldrCtx->blockCount());
609 B.takeNodes(UpdatedN);
610 ExplodedNodeSet Dst2;
611 evalBind(Dst2, DS, UpdatedN, state->getLValue(VD, LC), InitVal, true);
616 B.generateNode(DS, N, state);
620 getCheckerManager().runCheckersForPostStmt(Dst, B.getResults(), DS, *this);
623 void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
624 ExplodedNodeSet &Dst) {
625 assert(B->getOpcode() == BO_LAnd ||
626 B->getOpcode() == BO_LOr);
628 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
629 ProgramStateRef state = Pred->getState();
631 ExplodedNode *N = Pred;
632 while (!N->getLocation().getAs<BlockEntrance>()) {
633 ProgramPoint P = N->getLocation();
634 assert(P.getAs<PreStmt>()|| P.getAs<PreStmtPurgeDeadSymbols>());
636 assert(N->pred_size() == 1);
637 N = *N->pred_begin();
639 assert(N->pred_size() == 1);
640 N = *N->pred_begin();
641 BlockEdge BE = N->getLocation().castAs<BlockEdge>();
644 // Determine the value of the expression by introspecting how we
645 // got this location in the CFG. This requires looking at the previous
646 // block we were in and what kind of control-flow transfer was involved.
647 const CFGBlock *SrcBlock = BE.getSrc();
648 // The only terminator (if there is one) that makes sense is a logical op.
649 CFGTerminator T = SrcBlock->getTerminator();
650 if (const BinaryOperator *Term = cast_or_null<BinaryOperator>(T.getStmt())) {
652 assert(Term->isLogicalOp());
653 assert(SrcBlock->succ_size() == 2);
654 // Did we take the true or false branch?
655 unsigned constant = (*SrcBlock->succ_begin() == BE.getDst()) ? 1 : 0;
656 X = svalBuilder.makeIntVal(constant, B->getType());
659 // If there is no terminator, by construction the last statement
660 // in SrcBlock is the value of the enclosing expression.
661 // However, we still need to constrain that value to be 0 or 1.
662 assert(!SrcBlock->empty());
663 CFGStmt Elem = SrcBlock->rbegin()->castAs<CFGStmt>();
664 const Expr *RHS = cast<Expr>(Elem.getStmt());
665 SVal RHSVal = N->getState()->getSVal(RHS, Pred->getLocationContext());
667 if (RHSVal.isUndef()) {
670 // We evaluate "RHSVal != 0" expression which result in 0 if the value is
671 // known to be false, 1 if the value is known to be true and a new symbol
672 // when the assumption is unknown.
673 nonloc::ConcreteInt Zero(getBasicVals().getValue(0, B->getType()));
674 X = evalBinOp(N->getState(), BO_NE,
675 svalBuilder.evalCast(RHSVal, B->getType(), RHS->getType()),
679 Bldr.generateNode(B, Pred, state->BindExpr(B, Pred->getLocationContext(), X));
682 void ExprEngine::VisitInitListExpr(const InitListExpr *IE,
684 ExplodedNodeSet &Dst) {
685 StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
687 ProgramStateRef state = Pred->getState();
688 const LocationContext *LCtx = Pred->getLocationContext();
689 QualType T = getContext().getCanonicalType(IE->getType());
690 unsigned NumInitElements = IE->getNumInits();
692 if (!IE->isGLValue() &&
693 (T->isArrayType() || T->isRecordType() || T->isVectorType() ||
694 T->isAnyComplexType())) {
695 llvm::ImmutableList<SVal> vals = getBasicVals().getEmptySValList();
697 // Handle base case where the initializer has no elements.
698 // e.g: static int* myArray[] = {};
699 if (NumInitElements == 0) {
700 SVal V = svalBuilder.makeCompoundVal(T, vals);
701 B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V));
705 for (InitListExpr::const_reverse_iterator it = IE->rbegin(),
706 ei = IE->rend(); it != ei; ++it) {
707 SVal V = state->getSVal(cast<Expr>(*it), LCtx);
708 vals = getBasicVals().prependSVal(V, vals);
711 B.generateNode(IE, Pred,
712 state->BindExpr(IE, LCtx,
713 svalBuilder.makeCompoundVal(T, vals)));
717 // Handle scalars: int{5} and int{} and GLvalues.
718 // Note, if the InitListExpr is a GLvalue, it means that there is an address
719 // representing it, so it must have a single init element.
720 assert(NumInitElements <= 1);
723 if (NumInitElements == 0)
724 V = getSValBuilder().makeZeroVal(T);
726 V = state->getSVal(IE->getInit(0), LCtx);
728 B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V));
731 void ExprEngine::VisitGuardedExpr(const Expr *Ex,
735 ExplodedNodeSet &Dst) {
738 StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
739 ProgramStateRef state = Pred->getState();
740 const LocationContext *LCtx = Pred->getLocationContext();
741 const CFGBlock *SrcBlock = nullptr;
743 // Find the predecessor block.
744 ProgramStateRef SrcState = state;
745 for (const ExplodedNode *N = Pred ; N ; N = *N->pred_begin()) {
746 ProgramPoint PP = N->getLocation();
747 if (PP.getAs<PreStmtPurgeDeadSymbols>() || PP.getAs<BlockEntrance>()) {
748 assert(N->pred_size() == 1);
751 SrcBlock = PP.castAs<BlockEdge>().getSrc();
752 SrcState = N->getState();
756 assert(SrcBlock && "missing function entry");
758 // Find the last expression in the predecessor block. That is the
759 // expression that is used for the value of the ternary expression.
760 bool hasValue = false;
763 for (CFGElement CE : llvm::reverse(*SrcBlock)) {
764 if (Optional<CFGStmt> CS = CE.getAs<CFGStmt>()) {
765 const Expr *ValEx = cast<Expr>(CS->getStmt());
766 ValEx = ValEx->IgnoreParens();
768 // For GNU extension '?:' operator, the left hand side will be an
769 // OpaqueValueExpr, so get the underlying expression.
770 if (const OpaqueValueExpr *OpaqueEx = dyn_cast<OpaqueValueExpr>(L))
771 L = OpaqueEx->getSourceExpr();
773 // If the last expression in the predecessor block matches true or false
774 // subexpression, get its the value.
775 if (ValEx == L->IgnoreParens() || ValEx == R->IgnoreParens()) {
777 V = SrcState->getSVal(ValEx, LCtx);
784 V = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx,
785 currBldrCtx->blockCount());
787 // Generate a new node with the binding from the appropriate path.
788 B.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V, true));
792 VisitOffsetOfExpr(const OffsetOfExpr *OOE,
793 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
794 StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
796 if (OOE->EvaluateAsInt(IV, getContext())) {
797 assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType()));
798 assert(OOE->getType()->isBuiltinType());
799 assert(OOE->getType()->getAs<BuiltinType>()->isInteger());
800 assert(IV.isSigned() == OOE->getType()->isSignedIntegerType());
801 SVal X = svalBuilder.makeIntVal(IV);
802 B.generateNode(OOE, Pred,
803 Pred->getState()->BindExpr(OOE, Pred->getLocationContext(),
806 // FIXME: Handle the case where __builtin_offsetof is not a constant.
811 VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
813 ExplodedNodeSet &Dst) {
814 // FIXME: Prechecks eventually go in ::Visit().
815 ExplodedNodeSet CheckedSet;
816 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, Ex, *this);
818 ExplodedNodeSet EvalSet;
819 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
821 QualType T = Ex->getTypeOfArgument();
823 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
825 if (Ex->getKind() == UETT_SizeOf) {
826 if (!T->isIncompleteType() && !T->isConstantSizeType()) {
827 assert(T->isVariableArrayType() && "Unknown non-constant-sized type.");
829 // FIXME: Add support for VLA type arguments and VLA expressions.
830 // When that happens, we should probably refactor VLASizeChecker's code.
832 } else if (T->getAs<ObjCObjectType>()) {
833 // Some code tries to take the sizeof an ObjCObjectType, relying that
834 // the compiler has laid out its representation. Just report Unknown
840 APSInt Value = Ex->EvaluateKnownConstInt(getContext());
841 CharUnits amt = CharUnits::fromQuantity(Value.getZExtValue());
843 ProgramStateRef state = (*I)->getState();
844 state = state->BindExpr(Ex, (*I)->getLocationContext(),
845 svalBuilder.makeIntVal(amt.getQuantity(),
847 Bldr.generateNode(Ex, *I, state);
850 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, Ex, *this);
853 void ExprEngine::handleUOExtension(ExplodedNodeSet::iterator I,
854 const UnaryOperator *U,
855 StmtNodeBuilder &Bldr) {
856 // FIXME: We can probably just have some magic in Environment::getSVal()
857 // that propagates values, instead of creating a new node here.
859 // Unary "+" is a no-op, similar to a parentheses. We still have places
860 // where it may be a block-level expression, so we need to
861 // generate an extra node that just propagates the value of the
863 const Expr *Ex = U->getSubExpr()->IgnoreParens();
864 ProgramStateRef state = (*I)->getState();
865 const LocationContext *LCtx = (*I)->getLocationContext();
866 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx,
867 state->getSVal(Ex, LCtx)));
870 void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, ExplodedNode *Pred,
871 ExplodedNodeSet &Dst) {
872 // FIXME: Prechecks eventually go in ::Visit().
873 ExplodedNodeSet CheckedSet;
874 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, U, *this);
876 ExplodedNodeSet EvalSet;
877 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
879 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
881 switch (U->getOpcode()) {
885 VisitIncrementDecrementOperator(U, *I, Tmp);
890 const Expr *Ex = U->getSubExpr()->IgnoreParens();
892 // FIXME: We don't have complex SValues yet.
893 if (Ex->getType()->isAnyComplexType()) {
894 // Just report "Unknown."
898 // For all other types, UO_Real is an identity operation.
899 assert (U->getType() == Ex->getType());
900 ProgramStateRef state = (*I)->getState();
901 const LocationContext *LCtx = (*I)->getLocationContext();
902 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx,
903 state->getSVal(Ex, LCtx)));
908 const Expr *Ex = U->getSubExpr()->IgnoreParens();
909 // FIXME: We don't have complex SValues yet.
910 if (Ex->getType()->isAnyComplexType()) {
911 // Just report "Unknown."
914 // For all other types, UO_Imag returns 0.
915 ProgramStateRef state = (*I)->getState();
916 const LocationContext *LCtx = (*I)->getLocationContext();
917 SVal X = svalBuilder.makeZeroVal(Ex->getType());
918 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, X));
923 // Process pointer-to-member address operation.
924 const Expr *Ex = U->getSubExpr()->IgnoreParens();
925 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Ex)) {
926 const ValueDecl *VD = DRE->getDecl();
928 if (isa<CXXMethodDecl>(VD) || isa<FieldDecl>(VD)) {
929 ProgramStateRef State = (*I)->getState();
930 const LocationContext *LCtx = (*I)->getLocationContext();
931 SVal SV = svalBuilder.getMemberPointer(cast<DeclaratorDecl>(VD));
932 Bldr.generateNode(U, *I, State->BindExpr(U, LCtx, SV));
936 // Explicitly proceed with default handler for this case cascade.
937 handleUOExtension(I, U, Bldr);
941 assert(!U->isGLValue());
945 handleUOExtension(I, U, Bldr);
952 assert (!U->isGLValue());
953 const Expr *Ex = U->getSubExpr()->IgnoreParens();
954 ProgramStateRef state = (*I)->getState();
955 const LocationContext *LCtx = (*I)->getLocationContext();
957 // Get the value of the subexpression.
958 SVal V = state->getSVal(Ex, LCtx);
960 if (V.isUnknownOrUndef()) {
961 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V));
965 switch (U->getOpcode()) {
967 llvm_unreachable("Invalid Opcode.");
969 // FIXME: Do we need to handle promotions?
970 state = state->BindExpr(U, LCtx, evalComplement(V.castAs<NonLoc>()));
973 // FIXME: Do we need to handle promotions?
974 state = state->BindExpr(U, LCtx, evalMinus(V.castAs<NonLoc>()));
977 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
979 // Note: technically we do "E == 0", but this is the same in the
980 // transfer functions as "0 == E".
982 if (Optional<Loc> LV = V.getAs<Loc>()) {
983 Loc X = svalBuilder.makeNullWithType(Ex->getType());
984 Result = evalBinOp(state, BO_EQ, *LV, X, U->getType());
985 } else if (Ex->getType()->isFloatingType()) {
986 // FIXME: handle floating point types.
987 Result = UnknownVal();
989 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType()));
990 Result = evalBinOp(state, BO_EQ, V.castAs<NonLoc>(), X,
994 state = state->BindExpr(U, LCtx, Result);
997 Bldr.generateNode(U, *I, state);
1003 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, U, *this);
1006 void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U,
1008 ExplodedNodeSet &Dst) {
1009 // Handle ++ and -- (both pre- and post-increment).
1010 assert (U->isIncrementDecrementOp());
1011 const Expr *Ex = U->getSubExpr()->IgnoreParens();
1013 const LocationContext *LCtx = Pred->getLocationContext();
1014 ProgramStateRef state = Pred->getState();
1015 SVal loc = state->getSVal(Ex, LCtx);
1018 ExplodedNodeSet Tmp;
1019 evalLoad(Tmp, U, Ex, Pred, state, loc);
1021 ExplodedNodeSet Dst2;
1022 StmtNodeBuilder Bldr(Tmp, Dst2, *currBldrCtx);
1023 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end();I!=E;++I) {
1025 state = (*I)->getState();
1026 assert(LCtx == (*I)->getLocationContext());
1027 SVal V2_untested = state->getSVal(Ex, LCtx);
1029 // Propagate unknown and undefined values.
1030 if (V2_untested.isUnknownOrUndef()) {
1031 Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V2_untested));
1034 DefinedSVal V2 = V2_untested.castAs<DefinedSVal>();
1036 // Handle all other values.
1037 BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add : BO_Sub;
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.
1044 if (U->getType()->isAnyPointerType())
1045 RHS = svalBuilder.makeArrayIndex(1);
1046 else if (U->getType()->isIntegralOrEnumerationType())
1047 RHS = svalBuilder.makeIntVal(1, U->getType());
1051 SVal Result = evalBinOp(state, Op, V2, RHS, U->getType());
1053 // Conjure a new symbol if necessary to recover precision.
1054 if (Result.isUnknown()){
1055 DefinedOrUnknownSVal SymVal =
1056 svalBuilder.conjureSymbolVal(nullptr, U, LCtx,
1057 currBldrCtx->blockCount());
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()));
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()));
1074 state = state->assume(Constraint, false);
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++).
1083 state = state->BindExpr(U, LCtx, loc);
1085 state = state->BindExpr(U, LCtx, U->isPostfix() ? V2 : Result);
1087 // Perform the store.
1089 ExplodedNodeSet Dst3;
1090 evalStore(Dst3, U, U, *I, state, loc, Result);
1091 Bldr.addNodes(Dst3);