ExprEngineC.cpp revision 239462
1226586Sdim//=-- ExprEngineC.cpp - ExprEngine support for C expressions ----*- C++ -*-===// 2226586Sdim// 3226586Sdim// The LLVM Compiler Infrastructure 4226586Sdim// 5226586Sdim// This file is distributed under the University of Illinois Open Source 6226586Sdim// License. See LICENSE.TXT for details. 7226586Sdim// 8226586Sdim//===----------------------------------------------------------------------===// 9226586Sdim// 10226586Sdim// This file defines ExprEngine's support for C expressions. 11226586Sdim// 12226586Sdim//===----------------------------------------------------------------------===// 13226586Sdim 14226586Sdim#include "clang/StaticAnalyzer/Core/CheckerManager.h" 15226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 16226586Sdim 17226586Sdimusing namespace clang; 18226586Sdimusing namespace ento; 19226586Sdimusing llvm::APSInt; 20226586Sdim 21226586Sdimvoid ExprEngine::VisitBinaryOperator(const BinaryOperator* B, 22226586Sdim ExplodedNode *Pred, 23226586Sdim ExplodedNodeSet &Dst) { 24226586Sdim 25226586Sdim Expr *LHS = B->getLHS()->IgnoreParens(); 26226586Sdim Expr *RHS = B->getRHS()->IgnoreParens(); 27226586Sdim 28226586Sdim // FIXME: Prechecks eventually go in ::Visit(). 29226586Sdim ExplodedNodeSet CheckedSet; 30226586Sdim ExplodedNodeSet Tmp2; 31226586Sdim getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, B, *this); 32226586Sdim 33226586Sdim // With both the LHS and RHS evaluated, process the operation itself. 34226586Sdim for (ExplodedNodeSet::iterator it=CheckedSet.begin(), ei=CheckedSet.end(); 35226586Sdim it != ei; ++it) { 36226586Sdim 37234353Sdim ProgramStateRef state = (*it)->getState(); 38234353Sdim const LocationContext *LCtx = (*it)->getLocationContext(); 39234353Sdim SVal LeftV = state->getSVal(LHS, LCtx); 40234353Sdim SVal RightV = state->getSVal(RHS, LCtx); 41226586Sdim 42226586Sdim BinaryOperator::Opcode Op = B->getOpcode(); 43226586Sdim 44226586Sdim if (Op == BO_Assign) { 45226586Sdim // EXPERIMENTAL: "Conjured" symbols. 46226586Sdim // FIXME: Handle structs. 47234353Sdim if (RightV.isUnknown()) { 48234353Sdim unsigned Count = currentBuilderContext->getCurrentBlockCount(); 49234353Sdim RightV = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LCtx, Count); 50226586Sdim } 51226586Sdim // Simulate the effects of a "store": bind the value of the RHS 52226586Sdim // to the L-Value represented by the LHS. 53239462Sdim SVal ExprVal = B->isGLValue() ? LeftV : RightV; 54234353Sdim evalStore(Tmp2, B, LHS, *it, state->BindExpr(B, LCtx, ExprVal), 55234353Sdim LeftV, RightV); 56226586Sdim continue; 57226586Sdim } 58226586Sdim 59226586Sdim if (!B->isAssignmentOp()) { 60234353Sdim StmtNodeBuilder Bldr(*it, Tmp2, *currentBuilderContext); 61239462Sdim 62239462Sdim if (B->isAdditiveOp()) { 63239462Sdim // If one of the operands is a location, conjure a symbol for the other 64239462Sdim // one (offset) if it's unknown so that memory arithmetic always 65239462Sdim // results in an ElementRegion. 66239462Sdim // TODO: This can be removed after we enable history tracking with 67239462Sdim // SymSymExpr. 68239462Sdim unsigned Count = currentBuilderContext->getCurrentBlockCount(); 69239462Sdim if (isa<Loc>(LeftV) && 70239462Sdim RHS->getType()->isIntegerType() && RightV.isUnknown()) { 71239462Sdim RightV = svalBuilder.getConjuredSymbolVal(RHS, LCtx, 72239462Sdim RHS->getType(), Count); 73239462Sdim } 74239462Sdim if (isa<Loc>(RightV) && 75239462Sdim LHS->getType()->isIntegerType() && LeftV.isUnknown()) { 76239462Sdim LeftV = svalBuilder.getConjuredSymbolVal(LHS, LCtx, 77239462Sdim LHS->getType(), Count); 78239462Sdim } 79239462Sdim } 80239462Sdim 81226586Sdim // Process non-assignments except commas or short-circuited 82226586Sdim // logical expressions (LAnd and LOr). 83226586Sdim SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType()); 84226586Sdim if (Result.isUnknown()) { 85234353Sdim Bldr.generateNode(B, *it, state); 86226586Sdim continue; 87226586Sdim } 88226586Sdim 89234353Sdim state = state->BindExpr(B, LCtx, Result); 90234353Sdim Bldr.generateNode(B, *it, state); 91226586Sdim continue; 92226586Sdim } 93226586Sdim 94226586Sdim assert (B->isCompoundAssignmentOp()); 95226586Sdim 96226586Sdim switch (Op) { 97226586Sdim default: 98226586Sdim llvm_unreachable("Invalid opcode for compound assignment."); 99226586Sdim case BO_MulAssign: Op = BO_Mul; break; 100226586Sdim case BO_DivAssign: Op = BO_Div; break; 101226586Sdim case BO_RemAssign: Op = BO_Rem; break; 102226586Sdim case BO_AddAssign: Op = BO_Add; break; 103226586Sdim case BO_SubAssign: Op = BO_Sub; break; 104226586Sdim case BO_ShlAssign: Op = BO_Shl; break; 105226586Sdim case BO_ShrAssign: Op = BO_Shr; break; 106226586Sdim case BO_AndAssign: Op = BO_And; break; 107226586Sdim case BO_XorAssign: Op = BO_Xor; break; 108226586Sdim case BO_OrAssign: Op = BO_Or; break; 109226586Sdim } 110226586Sdim 111226586Sdim // Perform a load (the LHS). This performs the checks for 112226586Sdim // null dereferences, and so on. 113226586Sdim ExplodedNodeSet Tmp; 114226586Sdim SVal location = LeftV; 115234353Sdim evalLoad(Tmp, B, LHS, *it, state, location); 116226586Sdim 117226586Sdim for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; 118226586Sdim ++I) { 119226586Sdim 120226586Sdim state = (*I)->getState(); 121234353Sdim const LocationContext *LCtx = (*I)->getLocationContext(); 122234353Sdim SVal V = state->getSVal(LHS, LCtx); 123226586Sdim 124226586Sdim // Get the computation type. 125226586Sdim QualType CTy = 126226586Sdim cast<CompoundAssignOperator>(B)->getComputationResultType(); 127226586Sdim CTy = getContext().getCanonicalType(CTy); 128226586Sdim 129226586Sdim QualType CLHSTy = 130226586Sdim cast<CompoundAssignOperator>(B)->getComputationLHSType(); 131226586Sdim CLHSTy = getContext().getCanonicalType(CLHSTy); 132226586Sdim 133226586Sdim QualType LTy = getContext().getCanonicalType(LHS->getType()); 134226586Sdim 135226586Sdim // Promote LHS. 136226586Sdim V = svalBuilder.evalCast(V, CLHSTy, LTy); 137226586Sdim 138226586Sdim // Compute the result of the operation. 139226586Sdim SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy), 140226586Sdim B->getType(), CTy); 141226586Sdim 142226586Sdim // EXPERIMENTAL: "Conjured" symbols. 143226586Sdim // FIXME: Handle structs. 144226586Sdim 145226586Sdim SVal LHSVal; 146226586Sdim 147234353Sdim if (Result.isUnknown()) { 148226586Sdim 149234353Sdim unsigned Count = currentBuilderContext->getCurrentBlockCount(); 150226586Sdim 151226586Sdim // The symbolic value is actually for the type of the left-hand side 152226586Sdim // expression, not the computation type, as this is the value the 153226586Sdim // LValue on the LHS will bind to. 154234353Sdim LHSVal = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LCtx, 155234353Sdim LTy, Count); 156226586Sdim 157226586Sdim // However, we need to convert the symbol to the computation type. 158226586Sdim Result = svalBuilder.evalCast(LHSVal, CTy, LTy); 159226586Sdim } 160226586Sdim else { 161226586Sdim // The left-hand side may bind to a different value then the 162226586Sdim // computation type. 163226586Sdim LHSVal = svalBuilder.evalCast(Result, LTy, CTy); 164226586Sdim } 165226586Sdim 166226586Sdim // In C++, assignment and compound assignment operators return an 167226586Sdim // lvalue. 168239462Sdim if (B->isGLValue()) 169234353Sdim state = state->BindExpr(B, LCtx, location); 170226586Sdim else 171234353Sdim state = state->BindExpr(B, LCtx, Result); 172226586Sdim 173226586Sdim evalStore(Tmp2, B, LHS, *I, state, location, LHSVal); 174226586Sdim } 175226586Sdim } 176226586Sdim 177226586Sdim // FIXME: postvisits eventually go in ::Visit() 178226586Sdim getCheckerManager().runCheckersForPostStmt(Dst, Tmp2, B, *this); 179226586Sdim} 180226586Sdim 181226586Sdimvoid ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, 182226586Sdim ExplodedNodeSet &Dst) { 183226586Sdim 184226586Sdim CanQualType T = getContext().getCanonicalType(BE->getType()); 185239462Sdim 186239462Sdim // Get the value of the block itself. 187226586Sdim SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T, 188226586Sdim Pred->getLocationContext()); 189226586Sdim 190239462Sdim ProgramStateRef State = Pred->getState(); 191239462Sdim 192239462Sdim // If we created a new MemRegion for the block, we should explicitly bind 193239462Sdim // the captured variables. 194239462Sdim if (const BlockDataRegion *BDR = 195239462Sdim dyn_cast_or_null<BlockDataRegion>(V.getAsRegion())) { 196239462Sdim 197239462Sdim BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), 198239462Sdim E = BDR->referenced_vars_end(); 199239462Sdim 200239462Sdim for (; I != E; ++I) { 201239462Sdim const MemRegion *capturedR = I.getCapturedRegion(); 202239462Sdim const MemRegion *originalR = I.getOriginalRegion(); 203239462Sdim if (capturedR != originalR) { 204239462Sdim SVal originalV = State->getSVal(loc::MemRegionVal(originalR)); 205239462Sdim State = State->bindLoc(loc::MemRegionVal(capturedR), originalV); 206239462Sdim } 207239462Sdim } 208239462Sdim } 209239462Sdim 210226586Sdim ExplodedNodeSet Tmp; 211234353Sdim StmtNodeBuilder Bldr(Pred, Tmp, *currentBuilderContext); 212234353Sdim Bldr.generateNode(BE, Pred, 213239462Sdim State->BindExpr(BE, Pred->getLocationContext(), V), 214234353Sdim false, 0, 215234353Sdim ProgramPoint::PostLValueKind); 216226586Sdim 217226586Sdim // FIXME: Move all post/pre visits to ::Visit(). 218226586Sdim getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this); 219226586Sdim} 220226586Sdim 221226586Sdimvoid ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, 222226586Sdim ExplodedNode *Pred, ExplodedNodeSet &Dst) { 223226586Sdim 224226586Sdim ExplodedNodeSet dstPreStmt; 225226586Sdim getCheckerManager().runCheckersForPreStmt(dstPreStmt, Pred, CastE, *this); 226226586Sdim 227234353Sdim if (CastE->getCastKind() == CK_LValueToRValue) { 228226586Sdim for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end(); 229226586Sdim I!=E; ++I) { 230226586Sdim ExplodedNode *subExprNode = *I; 231234353Sdim ProgramStateRef state = subExprNode->getState(); 232234353Sdim const LocationContext *LCtx = subExprNode->getLocationContext(); 233234353Sdim evalLoad(Dst, CastE, CastE, subExprNode, state, state->getSVal(Ex, LCtx)); 234226586Sdim } 235226586Sdim return; 236226586Sdim } 237226586Sdim 238226586Sdim // All other casts. 239226586Sdim QualType T = CastE->getType(); 240226586Sdim QualType ExTy = Ex->getType(); 241226586Sdim 242226586Sdim if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE)) 243226586Sdim T = ExCast->getTypeAsWritten(); 244226586Sdim 245234353Sdim StmtNodeBuilder Bldr(dstPreStmt, Dst, *currentBuilderContext); 246226586Sdim for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end(); 247226586Sdim I != E; ++I) { 248226586Sdim 249226586Sdim Pred = *I; 250226586Sdim 251226586Sdim switch (CastE->getCastKind()) { 252226586Sdim case CK_LValueToRValue: 253226586Sdim llvm_unreachable("LValueToRValue casts handled earlier."); 254226586Sdim case CK_ToVoid: 255226586Sdim continue; 256226586Sdim // The analyzer doesn't do anything special with these casts, 257226586Sdim // since it understands retain/release semantics already. 258226586Sdim case CK_ARCProduceObject: 259226586Sdim case CK_ARCConsumeObject: 260226586Sdim case CK_ARCReclaimReturnedObject: 261226586Sdim case CK_ARCExtendBlockObject: // Fall-through. 262234353Sdim case CK_CopyAndAutoreleaseBlockObject: 263234353Sdim // The analyser can ignore atomic casts for now, although some future 264234353Sdim // checkers may want to make certain that you're not modifying the same 265234353Sdim // value through atomic and nonatomic pointers. 266234353Sdim case CK_AtomicToNonAtomic: 267234353Sdim case CK_NonAtomicToAtomic: 268226586Sdim // True no-ops. 269226586Sdim case CK_NoOp: 270226586Sdim case CK_FunctionToPointerDecay: { 271226586Sdim // Copy the SVal of Ex to CastE. 272234353Sdim ProgramStateRef state = Pred->getState(); 273234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 274234353Sdim SVal V = state->getSVal(Ex, LCtx); 275234353Sdim state = state->BindExpr(CastE, LCtx, V); 276234353Sdim Bldr.generateNode(CastE, Pred, state); 277226586Sdim continue; 278226586Sdim } 279226586Sdim case CK_Dependent: 280226586Sdim case CK_ArrayToPointerDecay: 281226586Sdim case CK_BitCast: 282226586Sdim case CK_IntegralCast: 283226586Sdim case CK_NullToPointer: 284226586Sdim case CK_IntegralToPointer: 285226586Sdim case CK_PointerToIntegral: 286226586Sdim case CK_PointerToBoolean: 287226586Sdim case CK_IntegralToBoolean: 288226586Sdim case CK_IntegralToFloating: 289226586Sdim case CK_FloatingToIntegral: 290226586Sdim case CK_FloatingToBoolean: 291226586Sdim case CK_FloatingCast: 292226586Sdim case CK_FloatingRealToComplex: 293226586Sdim case CK_FloatingComplexToReal: 294226586Sdim case CK_FloatingComplexToBoolean: 295226586Sdim case CK_FloatingComplexCast: 296226586Sdim case CK_FloatingComplexToIntegralComplex: 297226586Sdim case CK_IntegralRealToComplex: 298226586Sdim case CK_IntegralComplexToReal: 299226586Sdim case CK_IntegralComplexToBoolean: 300226586Sdim case CK_IntegralComplexCast: 301226586Sdim case CK_IntegralComplexToFloatingComplex: 302226586Sdim case CK_CPointerToObjCPointerCast: 303226586Sdim case CK_BlockPointerToObjCPointerCast: 304226586Sdim case CK_AnyPointerToBlockPointerCast: 305226586Sdim case CK_ObjCObjectLValueCast: { 306226586Sdim // Delegate to SValBuilder to process. 307234353Sdim ProgramStateRef state = Pred->getState(); 308234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 309234353Sdim SVal V = state->getSVal(Ex, LCtx); 310226586Sdim V = svalBuilder.evalCast(V, T, ExTy); 311234353Sdim state = state->BindExpr(CastE, LCtx, V); 312234353Sdim Bldr.generateNode(CastE, Pred, state); 313226586Sdim continue; 314226586Sdim } 315226586Sdim case CK_DerivedToBase: 316226586Sdim case CK_UncheckedDerivedToBase: { 317226586Sdim // For DerivedToBase cast, delegate to the store manager. 318234353Sdim ProgramStateRef state = Pred->getState(); 319234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 320234353Sdim SVal val = state->getSVal(Ex, LCtx); 321239462Sdim val = getStoreManager().evalDerivedToBase(val, CastE); 322234353Sdim state = state->BindExpr(CastE, LCtx, val); 323234353Sdim Bldr.generateNode(CastE, Pred, state); 324226586Sdim continue; 325226586Sdim } 326234353Sdim // Handle C++ dyn_cast. 327234353Sdim case CK_Dynamic: { 328234353Sdim ProgramStateRef state = Pred->getState(); 329234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 330234353Sdim SVal val = state->getSVal(Ex, LCtx); 331234353Sdim 332234353Sdim // Compute the type of the result. 333234353Sdim QualType resultType = CastE->getType(); 334239462Sdim if (CastE->isGLValue()) 335234353Sdim resultType = getContext().getPointerType(resultType); 336234353Sdim 337234353Sdim bool Failed = false; 338234353Sdim 339234353Sdim // Check if the value being cast evaluates to 0. 340234353Sdim if (val.isZeroConstant()) 341234353Sdim Failed = true; 342234353Sdim // Else, evaluate the cast. 343234353Sdim else 344234353Sdim val = getStoreManager().evalDynamicCast(val, T, Failed); 345234353Sdim 346234353Sdim if (Failed) { 347234353Sdim if (T->isReferenceType()) { 348234353Sdim // A bad_cast exception is thrown if input value is a reference. 349234353Sdim // Currently, we model this, by generating a sink. 350234353Sdim Bldr.generateNode(CastE, Pred, state, true); 351234353Sdim continue; 352234353Sdim } else { 353234353Sdim // If the cast fails on a pointer, bind to 0. 354234353Sdim state = state->BindExpr(CastE, LCtx, svalBuilder.makeNull()); 355234353Sdim } 356234353Sdim } else { 357234353Sdim // If we don't know if the cast succeeded, conjure a new symbol. 358234353Sdim if (val.isUnknown()) { 359234353Sdim DefinedOrUnknownSVal NewSym = svalBuilder.getConjuredSymbolVal(NULL, 360234353Sdim CastE, LCtx, resultType, 361234353Sdim currentBuilderContext->getCurrentBlockCount()); 362234353Sdim state = state->BindExpr(CastE, LCtx, NewSym); 363234353Sdim } else 364234353Sdim // Else, bind to the derived region value. 365234353Sdim state = state->BindExpr(CastE, LCtx, val); 366234353Sdim } 367234353Sdim Bldr.generateNode(CastE, Pred, state); 368234353Sdim continue; 369234353Sdim } 370234353Sdim // Various C++ casts that are not handled yet. 371226586Sdim case CK_ToUnion: 372226586Sdim case CK_BaseToDerived: 373226586Sdim case CK_NullToMemberPointer: 374226586Sdim case CK_BaseToDerivedMemberPointer: 375226586Sdim case CK_DerivedToBaseMemberPointer: 376234353Sdim case CK_ReinterpretMemberPointer: 377226586Sdim case CK_UserDefinedConversion: 378226586Sdim case CK_ConstructorConversion: 379226586Sdim case CK_VectorSplat: 380239462Sdim case CK_MemberPointerToBoolean: 381239462Sdim case CK_LValueBitCast: { 382226586Sdim // Recover some path-sensitivty by conjuring a new value. 383226586Sdim QualType resultType = CastE->getType(); 384239462Sdim if (CastE->isGLValue()) 385226586Sdim resultType = getContext().getPointerType(resultType); 386234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 387234353Sdim SVal result = svalBuilder.getConjuredSymbolVal(NULL, CastE, LCtx, 388234353Sdim resultType, currentBuilderContext->getCurrentBlockCount()); 389234353Sdim ProgramStateRef state = Pred->getState()->BindExpr(CastE, LCtx, 390234353Sdim result); 391234353Sdim Bldr.generateNode(CastE, Pred, state); 392226586Sdim continue; 393226586Sdim } 394226586Sdim } 395226586Sdim } 396226586Sdim} 397226586Sdim 398226586Sdimvoid ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL, 399226586Sdim ExplodedNode *Pred, 400226586Sdim ExplodedNodeSet &Dst) { 401234353Sdim StmtNodeBuilder B(Pred, Dst, *currentBuilderContext); 402234353Sdim 403226586Sdim const InitListExpr *ILE 404226586Sdim = cast<InitListExpr>(CL->getInitializer()->IgnoreParens()); 405226586Sdim 406234353Sdim ProgramStateRef state = Pred->getState(); 407234353Sdim SVal ILV = state->getSVal(ILE, Pred->getLocationContext()); 408226586Sdim const LocationContext *LC = Pred->getLocationContext(); 409226586Sdim state = state->bindCompoundLiteral(CL, LC, ILV); 410239462Sdim 411239462Sdim // Compound literal expressions are a GNU extension in C++. 412239462Sdim // Unlike in C, where CLs are lvalues, in C++ CLs are prvalues, 413239462Sdim // and like temporary objects created by the functional notation T() 414239462Sdim // CLs are destroyed at the end of the containing full-expression. 415239462Sdim // HOWEVER, an rvalue of array type is not something the analyzer can 416239462Sdim // reason about, since we expect all regions to be wrapped in Locs. 417239462Sdim // So we treat array CLs as lvalues as well, knowing that they will decay 418239462Sdim // to pointers as soon as they are used. 419239462Sdim if (CL->isGLValue() || CL->getType()->isArrayType()) 420234353Sdim B.generateNode(CL, Pred, state->BindExpr(CL, LC, state->getLValue(CL, LC))); 421226586Sdim else 422234353Sdim B.generateNode(CL, Pred, state->BindExpr(CL, LC, ILV)); 423226586Sdim} 424226586Sdim 425226586Sdimvoid ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, 426226586Sdim ExplodedNodeSet &Dst) { 427226586Sdim 428226586Sdim // FIXME: static variables may have an initializer, but the second 429226586Sdim // time a function is called those values may not be current. 430226586Sdim // This may need to be reflected in the CFG. 431226586Sdim 432226586Sdim // Assumption: The CFG has one DeclStmt per Decl. 433226586Sdim const Decl *D = *DS->decl_begin(); 434226586Sdim 435234353Sdim if (!D || !isa<VarDecl>(D)) { 436234353Sdim //TODO:AZ: remove explicit insertion after refactoring is done. 437234353Sdim Dst.insert(Pred); 438226586Sdim return; 439234353Sdim } 440226586Sdim 441226586Sdim // FIXME: all pre/post visits should eventually be handled by ::Visit(). 442226586Sdim ExplodedNodeSet dstPreVisit; 443226586Sdim getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, DS, *this); 444226586Sdim 445234353Sdim StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); 446226586Sdim const VarDecl *VD = dyn_cast<VarDecl>(D); 447226586Sdim for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end(); 448226586Sdim I!=E; ++I) { 449226586Sdim ExplodedNode *N = *I; 450234353Sdim ProgramStateRef state = N->getState(); 451226586Sdim 452226586Sdim // Decls without InitExpr are not initialized explicitly. 453226586Sdim const LocationContext *LC = N->getLocationContext(); 454226586Sdim 455226586Sdim if (const Expr *InitEx = VD->getInit()) { 456239462Sdim SVal InitVal = state->getSVal(InitEx, LC); 457234353Sdim 458239462Sdim if (InitVal == state->getLValue(VD, LC) || 459239462Sdim (VD->getType()->isArrayType() && 460239462Sdim isa<CXXConstructExpr>(InitEx->IgnoreImplicit()))) { 461239462Sdim // We constructed the object directly in the variable. 462239462Sdim // No need to bind anything. 463239462Sdim B.generateNode(DS, N, state); 464239462Sdim } else { 465239462Sdim // We bound the temp obj region to the CXXConstructExpr. Now recover 466239462Sdim // the lazy compound value when the variable is not a reference. 467239462Sdim if (AMgr.getLangOpts().CPlusPlus && VD->getType()->isRecordType() && 468239462Sdim !VD->getType()->isReferenceType() && isa<loc::MemRegionVal>(InitVal)){ 469239462Sdim InitVal = state->getSVal(cast<loc::MemRegionVal>(InitVal).getRegion()); 470239462Sdim assert(isa<nonloc::LazyCompoundVal>(InitVal)); 471239462Sdim } 472239462Sdim 473239462Sdim // Recover some path-sensitivity if a scalar value evaluated to 474239462Sdim // UnknownVal. 475239462Sdim if (InitVal.isUnknown()) { 476239462Sdim QualType Ty = InitEx->getType(); 477239462Sdim if (InitEx->isGLValue()) { 478239462Sdim Ty = getContext().getPointerType(Ty); 479239462Sdim } 480239462Sdim 481239462Sdim InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx, LC, Ty, 482239462Sdim currentBuilderContext->getCurrentBlockCount()); 483239462Sdim } 484239462Sdim B.takeNodes(N); 485239462Sdim ExplodedNodeSet Dst2; 486239462Sdim evalBind(Dst2, DS, N, state->getLValue(VD, LC), InitVal, true); 487239462Sdim B.addNodes(Dst2); 488226586Sdim } 489226586Sdim } 490226586Sdim else { 491234353Sdim B.generateNode(DS, N,state->bindDeclWithNoInit(state->getRegion(VD, LC))); 492226586Sdim } 493226586Sdim } 494226586Sdim} 495226586Sdim 496226586Sdimvoid ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, 497226586Sdim ExplodedNodeSet &Dst) { 498226586Sdim assert(B->getOpcode() == BO_LAnd || 499226586Sdim B->getOpcode() == BO_LOr); 500234353Sdim 501234353Sdim StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 502234353Sdim ProgramStateRef state = Pred->getState(); 503239462Sdim 504239462Sdim ExplodedNode *N = Pred; 505239462Sdim while (!isa<BlockEntrance>(N->getLocation())) { 506239462Sdim ProgramPoint P = N->getLocation(); 507239462Sdim assert(isa<PreStmt>(P)|| isa<PreStmtPurgeDeadSymbols>(P)); 508239462Sdim (void) P; 509239462Sdim assert(N->pred_size() == 1); 510239462Sdim N = *N->pred_begin(); 511226586Sdim } 512239462Sdim assert(N->pred_size() == 1); 513239462Sdim N = *N->pred_begin(); 514239462Sdim BlockEdge BE = cast<BlockEdge>(N->getLocation()); 515239462Sdim SVal X; 516239462Sdim 517239462Sdim // Determine the value of the expression by introspecting how we 518239462Sdim // got this location in the CFG. This requires looking at the previous 519239462Sdim // block we were in and what kind of control-flow transfer was involved. 520239462Sdim const CFGBlock *SrcBlock = BE.getSrc(); 521239462Sdim // The only terminator (if there is one) that makes sense is a logical op. 522239462Sdim CFGTerminator T = SrcBlock->getTerminator(); 523239462Sdim if (const BinaryOperator *Term = cast_or_null<BinaryOperator>(T.getStmt())) { 524239462Sdim (void) Term; 525239462Sdim assert(Term->isLogicalOp()); 526239462Sdim assert(SrcBlock->succ_size() == 2); 527239462Sdim // Did we take the true or false branch? 528239462Sdim unsigned constant = (*SrcBlock->succ_begin() == BE.getDst()) ? 1 : 0; 529239462Sdim X = svalBuilder.makeIntVal(constant, B->getType()); 530239462Sdim } 531226586Sdim else { 532239462Sdim // If there is no terminator, by construction the last statement 533239462Sdim // in SrcBlock is the value of the enclosing expression. 534239462Sdim assert(!SrcBlock->empty()); 535239462Sdim CFGStmt Elem = cast<CFGStmt>(*SrcBlock->rbegin()); 536239462Sdim const Stmt *S = Elem.getStmt(); 537239462Sdim X = N->getState()->getSVal(S, Pred->getLocationContext()); 538226586Sdim } 539239462Sdim 540239462Sdim Bldr.generateNode(B, Pred, state->BindExpr(B, Pred->getLocationContext(), X)); 541226586Sdim} 542226586Sdim 543226586Sdimvoid ExprEngine::VisitInitListExpr(const InitListExpr *IE, 544226586Sdim ExplodedNode *Pred, 545226586Sdim ExplodedNodeSet &Dst) { 546234353Sdim StmtNodeBuilder B(Pred, Dst, *currentBuilderContext); 547226586Sdim 548234353Sdim ProgramStateRef state = Pred->getState(); 549234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 550226586Sdim QualType T = getContext().getCanonicalType(IE->getType()); 551226586Sdim unsigned NumInitElements = IE->getNumInits(); 552226586Sdim 553226586Sdim if (T->isArrayType() || T->isRecordType() || T->isVectorType()) { 554226586Sdim llvm::ImmutableList<SVal> vals = getBasicVals().getEmptySValList(); 555226586Sdim 556226586Sdim // Handle base case where the initializer has no elements. 557226586Sdim // e.g: static int* myArray[] = {}; 558226586Sdim if (NumInitElements == 0) { 559226586Sdim SVal V = svalBuilder.makeCompoundVal(T, vals); 560234353Sdim B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V)); 561226586Sdim return; 562226586Sdim } 563226586Sdim 564226586Sdim for (InitListExpr::const_reverse_iterator it = IE->rbegin(), 565226586Sdim ei = IE->rend(); it != ei; ++it) { 566234353Sdim vals = getBasicVals().consVals(state->getSVal(cast<Expr>(*it), LCtx), 567234353Sdim vals); 568226586Sdim } 569226586Sdim 570234353Sdim B.generateNode(IE, Pred, 571234353Sdim state->BindExpr(IE, LCtx, 572234353Sdim svalBuilder.makeCompoundVal(T, vals))); 573226586Sdim return; 574226586Sdim } 575239462Sdim 576239462Sdim // Handle scalars: int{5} and int{}. 577239462Sdim assert(NumInitElements <= 1); 578239462Sdim 579239462Sdim SVal V; 580239462Sdim if (NumInitElements == 0) 581239462Sdim V = getSValBuilder().makeZeroVal(T); 582239462Sdim else 583239462Sdim V = state->getSVal(IE->getInit(0), LCtx); 584239462Sdim 585239462Sdim B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V)); 586226586Sdim} 587226586Sdim 588226586Sdimvoid ExprEngine::VisitGuardedExpr(const Expr *Ex, 589226586Sdim const Expr *L, 590226586Sdim const Expr *R, 591226586Sdim ExplodedNode *Pred, 592226586Sdim ExplodedNodeSet &Dst) { 593234353Sdim StmtNodeBuilder B(Pred, Dst, *currentBuilderContext); 594234353Sdim ProgramStateRef state = Pred->getState(); 595234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 596239462Sdim const CFGBlock *SrcBlock = 0; 597239462Sdim 598239462Sdim for (const ExplodedNode *N = Pred ; N ; N = *N->pred_begin()) { 599239462Sdim ProgramPoint PP = N->getLocation(); 600239462Sdim if (isa<PreStmtPurgeDeadSymbols>(PP) || isa<BlockEntrance>(PP)) { 601239462Sdim assert(N->pred_size() == 1); 602239462Sdim continue; 603239462Sdim } 604239462Sdim SrcBlock = cast<BlockEdge>(&PP)->getSrc(); 605239462Sdim break; 606239462Sdim } 607239462Sdim 608239462Sdim // Find the last expression in the predecessor block. That is the 609239462Sdim // expression that is used for the value of the ternary expression. 610239462Sdim bool hasValue = false; 611239462Sdim SVal V; 612239462Sdim 613239462Sdim for (CFGBlock::const_reverse_iterator I = SrcBlock->rbegin(), 614239462Sdim E = SrcBlock->rend(); I != E; ++I) { 615239462Sdim CFGElement CE = *I; 616239462Sdim if (CFGStmt *CS = dyn_cast<CFGStmt>(&CE)) { 617239462Sdim const Expr *ValEx = cast<Expr>(CS->getStmt()); 618239462Sdim hasValue = true; 619239462Sdim V = state->getSVal(ValEx, LCtx); 620239462Sdim break; 621239462Sdim } 622239462Sdim } 623239462Sdim 624239462Sdim assert(hasValue); 625239462Sdim (void) hasValue; 626239462Sdim 627239462Sdim // Generate a new node with the binding from the appropriate path. 628239462Sdim B.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V, true)); 629226586Sdim} 630226586Sdim 631226586Sdimvoid ExprEngine:: 632226586SdimVisitOffsetOfExpr(const OffsetOfExpr *OOE, 633226586Sdim ExplodedNode *Pred, ExplodedNodeSet &Dst) { 634234353Sdim StmtNodeBuilder B(Pred, Dst, *currentBuilderContext); 635234353Sdim APSInt IV; 636234353Sdim if (OOE->EvaluateAsInt(IV, getContext())) { 637226586Sdim assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType())); 638226586Sdim assert(OOE->getType()->isIntegerType()); 639226586Sdim assert(IV.isSigned() == OOE->getType()->isSignedIntegerOrEnumerationType()); 640226586Sdim SVal X = svalBuilder.makeIntVal(IV); 641234353Sdim B.generateNode(OOE, Pred, 642234353Sdim Pred->getState()->BindExpr(OOE, Pred->getLocationContext(), 643234353Sdim X)); 644226586Sdim } 645226586Sdim // FIXME: Handle the case where __builtin_offsetof is not a constant. 646226586Sdim} 647226586Sdim 648226586Sdim 649226586Sdimvoid ExprEngine:: 650226586SdimVisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex, 651226586Sdim ExplodedNode *Pred, 652226586Sdim ExplodedNodeSet &Dst) { 653234353Sdim StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 654226586Sdim 655226586Sdim QualType T = Ex->getTypeOfArgument(); 656226586Sdim 657226586Sdim if (Ex->getKind() == UETT_SizeOf) { 658226586Sdim if (!T->isIncompleteType() && !T->isConstantSizeType()) { 659226586Sdim assert(T->isVariableArrayType() && "Unknown non-constant-sized type."); 660226586Sdim 661226586Sdim // FIXME: Add support for VLA type arguments and VLA expressions. 662226586Sdim // When that happens, we should probably refactor VLASizeChecker's code. 663226586Sdim return; 664226586Sdim } 665226586Sdim else if (T->getAs<ObjCObjectType>()) { 666226586Sdim // Some code tries to take the sizeof an ObjCObjectType, relying that 667226586Sdim // the compiler has laid out its representation. Just report Unknown 668226586Sdim // for these. 669226586Sdim return; 670226586Sdim } 671226586Sdim } 672226586Sdim 673234353Sdim APSInt Value = Ex->EvaluateKnownConstInt(getContext()); 674234353Sdim CharUnits amt = CharUnits::fromQuantity(Value.getZExtValue()); 675226586Sdim 676234353Sdim ProgramStateRef state = Pred->getState(); 677234353Sdim state = state->BindExpr(Ex, Pred->getLocationContext(), 678234353Sdim svalBuilder.makeIntVal(amt.getQuantity(), 679226586Sdim Ex->getType())); 680234353Sdim Bldr.generateNode(Ex, Pred, state); 681226586Sdim} 682226586Sdim 683226586Sdimvoid ExprEngine::VisitUnaryOperator(const UnaryOperator* U, 684226586Sdim ExplodedNode *Pred, 685234353Sdim ExplodedNodeSet &Dst) { 686234353Sdim StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 687226586Sdim switch (U->getOpcode()) { 688234353Sdim default: { 689234353Sdim Bldr.takeNodes(Pred); 690234353Sdim ExplodedNodeSet Tmp; 691234353Sdim VisitIncrementDecrementOperator(U, Pred, Tmp); 692234353Sdim Bldr.addNodes(Tmp); 693234353Sdim } 694226586Sdim break; 695226586Sdim case UO_Real: { 696226586Sdim const Expr *Ex = U->getSubExpr()->IgnoreParens(); 697226586Sdim 698234353Sdim // FIXME: We don't have complex SValues yet. 699234353Sdim if (Ex->getType()->isAnyComplexType()) { 700234353Sdim // Just report "Unknown." 701234353Sdim break; 702234353Sdim } 703226586Sdim 704234353Sdim // For all other types, UO_Real is an identity operation. 705234353Sdim assert (U->getType() == Ex->getType()); 706234353Sdim ProgramStateRef state = Pred->getState(); 707234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 708234353Sdim Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, 709234353Sdim state->getSVal(Ex, LCtx))); 710234353Sdim break; 711226586Sdim } 712226586Sdim 713234353Sdim case UO_Imag: { 714226586Sdim const Expr *Ex = U->getSubExpr()->IgnoreParens(); 715234353Sdim // FIXME: We don't have complex SValues yet. 716234353Sdim if (Ex->getType()->isAnyComplexType()) { 717234353Sdim // Just report "Unknown." 718234353Sdim break; 719226586Sdim } 720234353Sdim // For all other types, UO_Imag returns 0. 721234353Sdim ProgramStateRef state = Pred->getState(); 722234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 723234353Sdim SVal X = svalBuilder.makeZeroVal(Ex->getType()); 724234353Sdim Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, X)); 725234353Sdim break; 726226586Sdim } 727226586Sdim 728226586Sdim case UO_Plus: 729239462Sdim assert(!U->isGLValue()); 730226586Sdim // FALL-THROUGH. 731226586Sdim case UO_Deref: 732226586Sdim case UO_AddrOf: 733226586Sdim case UO_Extension: { 734234353Sdim // FIXME: We can probably just have some magic in Environment::getSVal() 735234353Sdim // that propagates values, instead of creating a new node here. 736234353Sdim // 737226586Sdim // Unary "+" is a no-op, similar to a parentheses. We still have places 738226586Sdim // where it may be a block-level expression, so we need to 739226586Sdim // generate an extra node that just propagates the value of the 740234353Sdim // subexpression. 741226586Sdim const Expr *Ex = U->getSubExpr()->IgnoreParens(); 742234353Sdim ProgramStateRef state = Pred->getState(); 743234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 744234353Sdim Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, 745234353Sdim state->getSVal(Ex, LCtx))); 746234353Sdim break; 747226586Sdim } 748226586Sdim 749226586Sdim case UO_LNot: 750226586Sdim case UO_Minus: 751226586Sdim case UO_Not: { 752239462Sdim assert (!U->isGLValue()); 753226586Sdim const Expr *Ex = U->getSubExpr()->IgnoreParens(); 754234353Sdim ProgramStateRef state = Pred->getState(); 755234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 756226586Sdim 757234353Sdim // Get the value of the subexpression. 758234353Sdim SVal V = state->getSVal(Ex, LCtx); 759226586Sdim 760234353Sdim if (V.isUnknownOrUndef()) { 761234353Sdim Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, V)); 762234353Sdim break; 763234353Sdim } 764226586Sdim 765234353Sdim switch (U->getOpcode()) { 766234353Sdim default: 767234353Sdim llvm_unreachable("Invalid Opcode."); 768234353Sdim case UO_Not: 769234353Sdim // FIXME: Do we need to handle promotions? 770234353Sdim state = state->BindExpr(U, LCtx, evalComplement(cast<NonLoc>(V))); 771234353Sdim break; 772234353Sdim case UO_Minus: 773234353Sdim // FIXME: Do we need to handle promotions? 774234353Sdim state = state->BindExpr(U, LCtx, evalMinus(cast<NonLoc>(V))); 775234353Sdim break; 776234353Sdim case UO_LNot: 777234353Sdim // C99 6.5.3.3: "The expression !E is equivalent to (0==E)." 778234353Sdim // 779234353Sdim // Note: technically we do "E == 0", but this is the same in the 780234353Sdim // transfer functions as "0 == E". 781234353Sdim SVal Result; 782234353Sdim if (isa<Loc>(V)) { 783234353Sdim Loc X = svalBuilder.makeNull(); 784234353Sdim Result = evalBinOp(state, BO_EQ, cast<Loc>(V), X, 785234353Sdim U->getType()); 786234353Sdim } 787234353Sdim else { 788234353Sdim nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType())); 789234353Sdim Result = evalBinOp(state, BO_EQ, cast<NonLoc>(V), X, 790234353Sdim U->getType()); 791234353Sdim } 792234353Sdim 793234353Sdim state = state->BindExpr(U, LCtx, Result); 794234353Sdim break; 795226586Sdim } 796234353Sdim Bldr.generateNode(U, Pred, state); 797234353Sdim break; 798226586Sdim } 799226586Sdim } 800234353Sdim 801234353Sdim} 802234353Sdim 803234353Sdimvoid ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U, 804234353Sdim ExplodedNode *Pred, 805234353Sdim ExplodedNodeSet &Dst) { 806226586Sdim // Handle ++ and -- (both pre- and post-increment). 807226586Sdim assert (U->isIncrementDecrementOp()); 808226586Sdim const Expr *Ex = U->getSubExpr()->IgnoreParens(); 809226586Sdim 810234353Sdim const LocationContext *LCtx = Pred->getLocationContext(); 811234353Sdim ProgramStateRef state = Pred->getState(); 812234353Sdim SVal loc = state->getSVal(Ex, LCtx); 813234353Sdim 814234353Sdim // Perform a load. 815234353Sdim ExplodedNodeSet Tmp; 816234353Sdim evalLoad(Tmp, U, Ex, Pred, state, loc); 817234353Sdim 818234353Sdim ExplodedNodeSet Dst2; 819234353Sdim StmtNodeBuilder Bldr(Tmp, Dst2, *currentBuilderContext); 820234353Sdim for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end();I!=E;++I) { 821226586Sdim 822234353Sdim state = (*I)->getState(); 823234353Sdim assert(LCtx == (*I)->getLocationContext()); 824234353Sdim SVal V2_untested = state->getSVal(Ex, LCtx); 825226586Sdim 826234353Sdim // Propagate unknown and undefined values. 827234353Sdim if (V2_untested.isUnknownOrUndef()) { 828234353Sdim Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V2_untested)); 829234353Sdim continue; 830234353Sdim } 831234353Sdim DefinedSVal V2 = cast<DefinedSVal>(V2_untested); 832226586Sdim 833234353Sdim // Handle all other values. 834234353Sdim BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add : BO_Sub; 835234353Sdim 836234353Sdim // If the UnaryOperator has non-location type, use its type to create the 837234353Sdim // constant value. If the UnaryOperator has location type, create the 838234353Sdim // constant with int type and pointer width. 839234353Sdim SVal RHS; 840234353Sdim 841234353Sdim if (U->getType()->isAnyPointerType()) 842234353Sdim RHS = svalBuilder.makeArrayIndex(1); 843234353Sdim else 844234353Sdim RHS = svalBuilder.makeIntVal(1, U->getType()); 845234353Sdim 846234353Sdim SVal Result = evalBinOp(state, Op, V2, RHS, U->getType()); 847234353Sdim 848234353Sdim // Conjure a new symbol if necessary to recover precision. 849234353Sdim if (Result.isUnknown()){ 850234353Sdim DefinedOrUnknownSVal SymVal = 851234353Sdim svalBuilder.getConjuredSymbolVal(NULL, Ex, LCtx, 852234353Sdim currentBuilderContext->getCurrentBlockCount()); 853234353Sdim Result = SymVal; 854226586Sdim 855234353Sdim // If the value is a location, ++/-- should always preserve 856234353Sdim // non-nullness. Check if the original value was non-null, and if so 857234353Sdim // propagate that constraint. 858234353Sdim if (Loc::isLocType(U->getType())) { 859234353Sdim DefinedOrUnknownSVal Constraint = 860234353Sdim svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType())); 861226586Sdim 862234353Sdim if (!state->assume(Constraint, true)) { 863234353Sdim // It isn't feasible for the original value to be null. 864234353Sdim // Propagate this constraint. 865234353Sdim Constraint = svalBuilder.evalEQ(state, SymVal, 866234353Sdim svalBuilder.makeZeroVal(U->getType())); 867226586Sdim 868234353Sdim 869234353Sdim state = state->assume(Constraint, false); 870234353Sdim assert(state); 871226586Sdim } 872226586Sdim } 873226586Sdim } 874234353Sdim 875234353Sdim // Since the lvalue-to-rvalue conversion is explicit in the AST, 876234353Sdim // we bind an l-value if the operator is prefix and an lvalue (in C++). 877239462Sdim if (U->isGLValue()) 878234353Sdim state = state->BindExpr(U, LCtx, loc); 879234353Sdim else 880234353Sdim state = state->BindExpr(U, LCtx, U->isPostfix() ? V2 : Result); 881234353Sdim 882234353Sdim // Perform the store. 883234353Sdim Bldr.takeNodes(*I); 884234353Sdim ExplodedNodeSet Dst3; 885234353Sdim evalStore(Dst3, U, U, *I, state, loc, Result); 886234353Sdim Bldr.addNodes(Dst3); 887226586Sdim } 888234353Sdim Dst.insert(Dst2); 889226586Sdim} 890