ExprEngine.cpp revision a77c031cb66f75d22672070052cc6e0205289ff8
1//=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-= 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines a meta-engine for path-sensitive dataflow analysis that 11// is built on GREngine, but provides the boilerplate to execute transfer 12// functions and build the ExplodedGraph at the expression level. 13// 14//===----------------------------------------------------------------------===// 15 16#include "clang/StaticAnalyzer/Core/CheckerManager.h" 17#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h" 21#include "clang/AST/CharUnits.h" 22#include "clang/AST/ParentMap.h" 23#include "clang/AST/StmtObjC.h" 24#include "clang/AST/DeclCXX.h" 25#include "clang/Basic/Builtins.h" 26#include "clang/Basic/SourceManager.h" 27#include "clang/Basic/SourceManager.h" 28#include "clang/Basic/PrettyStackTrace.h" 29#include "llvm/Support/raw_ostream.h" 30#include "llvm/ADT/ImmutableList.h" 31 32#ifndef NDEBUG 33#include "llvm/Support/GraphWriter.h" 34#endif 35 36using namespace clang; 37using namespace ento; 38using llvm::APSInt; 39 40namespace { 41 // Trait class for recording returned expression in the state. 42 struct ReturnExpr { 43 static int TagInt; 44 typedef const Stmt *data_type; 45 }; 46 int ReturnExpr::TagInt; 47} 48 49//===----------------------------------------------------------------------===// 50// Utility functions. 51//===----------------------------------------------------------------------===// 52 53static inline Selector GetNullarySelector(const char* name, ASTContext& Ctx) { 54 IdentifierInfo* II = &Ctx.Idents.get(name); 55 return Ctx.Selectors.getSelector(0, &II); 56} 57 58//===----------------------------------------------------------------------===// 59// Engine construction and deletion. 60//===----------------------------------------------------------------------===// 61 62ExprEngine::ExprEngine(AnalysisManager &mgr, TransferFuncs *tf) 63 : AMgr(mgr), 64 Engine(*this), 65 G(Engine.getGraph()), 66 Builder(NULL), 67 StateMgr(getContext(), mgr.getStoreManagerCreator(), 68 mgr.getConstraintManagerCreator(), G.getAllocator(), 69 *this), 70 SymMgr(StateMgr.getSymbolManager()), 71 svalBuilder(StateMgr.getSValBuilder()), 72 EntryNode(NULL), currentStmt(NULL), 73 NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL), 74 RaiseSel(GetNullarySelector("raise", getContext())), 75 BR(mgr, *this), TF(tf) { 76 77 // FIXME: Eventually remove the TF object entirely. 78 TF->RegisterChecks(*this); 79 TF->RegisterPrinters(getStateManager().Printers); 80 81 if (mgr.shouldEagerlyTrimExplodedGraph()) { 82 // Enable eager node reclaimation when constructing the ExplodedGraph. 83 G.enableNodeReclamation(); 84 } 85} 86 87ExprEngine::~ExprEngine() { 88 BR.FlushReports(); 89 delete [] NSExceptionInstanceRaiseSelectors; 90} 91 92//===----------------------------------------------------------------------===// 93// Utility methods. 94//===----------------------------------------------------------------------===// 95 96const GRState* ExprEngine::getInitialState(const LocationContext *InitLoc) { 97 const GRState *state = StateMgr.getInitialState(InitLoc); 98 99 // Preconditions. 100 101 // FIXME: It would be nice if we had a more general mechanism to add 102 // such preconditions. Some day. 103 do { 104 const Decl *D = InitLoc->getDecl(); 105 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 106 // Precondition: the first argument of 'main' is an integer guaranteed 107 // to be > 0. 108 const IdentifierInfo *II = FD->getIdentifier(); 109 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) 110 break; 111 112 const ParmVarDecl *PD = FD->getParamDecl(0); 113 QualType T = PD->getType(); 114 if (!T->isIntegerType()) 115 break; 116 117 const MemRegion *R = state->getRegion(PD, InitLoc); 118 if (!R) 119 break; 120 121 SVal V = state->getSVal(loc::MemRegionVal(R)); 122 SVal Constraint_untested = evalBinOp(state, BO_GT, V, 123 svalBuilder.makeZeroVal(T), 124 getContext().IntTy); 125 126 DefinedOrUnknownSVal *Constraint = 127 dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested); 128 129 if (!Constraint) 130 break; 131 132 if (const GRState *newState = state->assume(*Constraint, true)) 133 state = newState; 134 135 break; 136 } 137 138 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { 139 // Precondition: 'self' is always non-null upon entry to an Objective-C 140 // method. 141 const ImplicitParamDecl *SelfD = MD->getSelfDecl(); 142 const MemRegion *R = state->getRegion(SelfD, InitLoc); 143 SVal V = state->getSVal(loc::MemRegionVal(R)); 144 145 if (const Loc *LV = dyn_cast<Loc>(&V)) { 146 // Assume that the pointer value in 'self' is non-null. 147 state = state->assume(*LV, true); 148 assert(state && "'self' cannot be null"); 149 } 150 } 151 } while (0); 152 153 return state; 154} 155 156bool 157ExprEngine::doesInvalidateGlobals(const CallOrObjCMessage &callOrMessage) const 158{ 159 if (callOrMessage.isFunctionCall() && !callOrMessage.isCXXCall()) { 160 SVal calleeV = callOrMessage.getFunctionCallee(); 161 if (const FunctionTextRegion *codeR = 162 dyn_cast_or_null<FunctionTextRegion>(calleeV.getAsRegion())) { 163 164 const FunctionDecl *fd = codeR->getDecl(); 165 if (const IdentifierInfo *ii = fd->getIdentifier()) { 166 StringRef fname = ii->getName(); 167 if (fname == "strlen") 168 return false; 169 } 170 } 171 } 172 173 // The conservative answer: invalidates globals. 174 return true; 175} 176 177//===----------------------------------------------------------------------===// 178// Top-level transfer function logic (Dispatcher). 179//===----------------------------------------------------------------------===// 180 181/// evalAssume - Called by ConstraintManager. Used to call checker-specific 182/// logic for handling assumptions on symbolic values. 183const GRState *ExprEngine::processAssume(const GRState *state, SVal cond, 184 bool assumption) { 185 state = getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); 186 187 // If the state is infeasible at this point, bail out. 188 if (!state) 189 return NULL; 190 191 return TF->evalAssume(state, cond, assumption); 192} 193 194bool ExprEngine::wantsRegionChangeUpdate(const GRState* state) { 195 return getCheckerManager().wantsRegionChangeUpdate(state); 196} 197 198const GRState * 199ExprEngine::processRegionChanges(const GRState *state, 200 const StoreManager::InvalidatedSymbols *invalidated, 201 const MemRegion * const *Begin, 202 const MemRegion * const *End) { 203 return getCheckerManager().runCheckersForRegionChanges(state, invalidated, 204 Begin, End); 205} 206 207void ExprEngine::processEndWorklist(bool hasWorkRemaining) { 208 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); 209} 210 211void ExprEngine::processCFGElement(const CFGElement E, 212 StmtNodeBuilder& builder) { 213 switch (E.getKind()) { 214 case CFGElement::Invalid: 215 llvm_unreachable("Unexpected CFGElement kind."); 216 case CFGElement::Statement: 217 ProcessStmt(E.getAs<CFGStmt>()->getStmt(), builder); 218 return; 219 case CFGElement::Initializer: 220 ProcessInitializer(E.getAs<CFGInitializer>()->getInitializer(), builder); 221 return; 222 case CFGElement::AutomaticObjectDtor: 223 case CFGElement::BaseDtor: 224 case CFGElement::MemberDtor: 225 case CFGElement::TemporaryDtor: 226 ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), builder); 227 return; 228 } 229} 230 231void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) { 232 // Reclaim any unnecessary nodes in the ExplodedGraph. 233 G.reclaimRecentlyAllocatedNodes(); 234 // Recycle any unused states in the GRStateManager. 235 StateMgr.recycleUnusedStates(); 236 237 currentStmt = S.getStmt(); 238 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 239 currentStmt->getLocStart(), 240 "Error evaluating statement"); 241 242 Builder = &builder; 243 EntryNode = builder.getPredecessor(); 244 245 // Create the cleaned state. 246 const LocationContext *LC = EntryNode->getLocationContext(); 247 SymbolReaper SymReaper(LC, currentStmt, SymMgr); 248 249 if (AMgr.shouldPurgeDead()) { 250 const GRState *St = EntryNode->getState(); 251 getCheckerManager().runCheckersForLiveSymbols(St, SymReaper); 252 253 const StackFrameContext *SFC = LC->getCurrentStackFrame(); 254 CleanedState = StateMgr.removeDeadBindings(St, SFC, SymReaper); 255 } else { 256 CleanedState = EntryNode->getState(); 257 } 258 259 // Process any special transfer function for dead symbols. 260 ExplodedNodeSet Tmp; 261 262 if (!SymReaper.hasDeadSymbols()) 263 Tmp.Add(EntryNode); 264 else { 265 SaveAndRestore<bool> OldSink(Builder->BuildSinks); 266 SaveOr OldHasGen(Builder->hasGeneratedNode); 267 268 SaveAndRestore<bool> OldPurgeDeadSymbols(Builder->PurgingDeadSymbols); 269 Builder->PurgingDeadSymbols = true; 270 271 // FIXME: This should soon be removed. 272 ExplodedNodeSet Tmp2; 273 getTF().evalDeadSymbols(Tmp2, *this, *Builder, EntryNode, 274 CleanedState, SymReaper); 275 276 getCheckerManager().runCheckersForDeadSymbols(Tmp, Tmp2, 277 SymReaper, currentStmt, *this); 278 279 if (!Builder->BuildSinks && !Builder->hasGeneratedNode) 280 Tmp.Add(EntryNode); 281 } 282 283 bool HasAutoGenerated = false; 284 285 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 286 ExplodedNodeSet Dst; 287 288 // Set the cleaned state. 289 Builder->SetCleanedState(*I == EntryNode ? CleanedState : GetState(*I)); 290 291 // Visit the statement. 292 Visit(currentStmt, *I, Dst); 293 294 // Do we need to auto-generate a node? We only need to do this to generate 295 // a node with a "cleaned" state; CoreEngine will actually handle 296 // auto-transitions for other cases. 297 if (Dst.size() == 1 && *Dst.begin() == EntryNode 298 && !Builder->hasGeneratedNode && !HasAutoGenerated) { 299 HasAutoGenerated = true; 300 builder.generateNode(currentStmt, GetState(EntryNode), *I); 301 } 302 } 303 304 // NULL out these variables to cleanup. 305 CleanedState = NULL; 306 EntryNode = NULL; 307 308 currentStmt = 0; 309 310 Builder = NULL; 311} 312 313void ExprEngine::ProcessInitializer(const CFGInitializer Init, 314 StmtNodeBuilder &builder) { 315 // We don't set EntryNode and currentStmt. And we don't clean up state. 316 const CXXCtorInitializer *BMI = Init.getInitializer(); 317 318 ExplodedNode *pred = builder.getPredecessor(); 319 320 const StackFrameContext *stackFrame = cast<StackFrameContext>(pred->getLocationContext()); 321 const CXXConstructorDecl *decl = cast<CXXConstructorDecl>(stackFrame->getDecl()); 322 const CXXThisRegion *thisReg = getCXXThisRegion(decl, stackFrame); 323 324 SVal thisVal = pred->getState()->getSVal(thisReg); 325 326 if (BMI->isAnyMemberInitializer()) { 327 ExplodedNodeSet Dst; 328 329 // Evaluate the initializer. 330 Visit(BMI->getInit(), pred, Dst); 331 332 for (ExplodedNodeSet::iterator I = Dst.begin(), E = Dst.end(); I != E; ++I){ 333 ExplodedNode *Pred = *I; 334 const GRState *state = Pred->getState(); 335 336 const FieldDecl *FD = BMI->getAnyMember(); 337 338 SVal FieldLoc = state->getLValue(FD, thisVal); 339 SVal InitVal = state->getSVal(BMI->getInit()); 340 state = state->bindLoc(FieldLoc, InitVal); 341 342 // Use a custom node building process. 343 PostInitializer PP(BMI, stackFrame); 344 // Builder automatically add the generated node to the deferred set, 345 // which are processed in the builder's dtor. 346 builder.generateNode(PP, state, Pred); 347 } 348 return; 349 } 350 351 assert(BMI->isBaseInitializer()); 352 353 // Get the base class declaration. 354 const CXXConstructExpr *ctorExpr = cast<CXXConstructExpr>(BMI->getInit()); 355 356 // Create the base object region. 357 SVal baseVal = 358 getStoreManager().evalDerivedToBase(thisVal, ctorExpr->getType()); 359 const MemRegion *baseReg = baseVal.getAsRegion(); 360 assert(baseReg); 361 Builder = &builder; 362 ExplodedNodeSet dst; 363 VisitCXXConstructExpr(ctorExpr, baseReg, pred, dst); 364} 365 366void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, 367 StmtNodeBuilder &builder) { 368 Builder = &builder; 369 370 switch (D.getKind()) { 371 case CFGElement::AutomaticObjectDtor: 372 ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), builder); 373 break; 374 case CFGElement::BaseDtor: 375 ProcessBaseDtor(cast<CFGBaseDtor>(D), builder); 376 break; 377 case CFGElement::MemberDtor: 378 ProcessMemberDtor(cast<CFGMemberDtor>(D), builder); 379 break; 380 case CFGElement::TemporaryDtor: 381 ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), builder); 382 break; 383 default: 384 llvm_unreachable("Unexpected dtor kind."); 385 } 386} 387 388void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor dtor, 389 StmtNodeBuilder &builder) { 390 ExplodedNode *pred = builder.getPredecessor(); 391 const GRState *state = pred->getState(); 392 const VarDecl *varDecl = dtor.getVarDecl(); 393 394 QualType varType = varDecl->getType(); 395 396 if (const ReferenceType *refType = varType->getAs<ReferenceType>()) 397 varType = refType->getPointeeType(); 398 399 const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl(); 400 assert(recordDecl && "get CXXRecordDecl fail"); 401 const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor(); 402 403 Loc dest = state->getLValue(varDecl, pred->getLocationContext()); 404 405 ExplodedNodeSet dstSet; 406 VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(), 407 dtor.getTriggerStmt(), pred, dstSet); 408} 409 410void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, 411 StmtNodeBuilder &builder) { 412} 413 414void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, 415 StmtNodeBuilder &builder) { 416} 417 418void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, 419 StmtNodeBuilder &builder) { 420} 421 422void ExprEngine::Visit(const Stmt* S, ExplodedNode* Pred, 423 ExplodedNodeSet& Dst) { 424 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 425 S->getLocStart(), 426 "Error evaluating statement"); 427 428 // Expressions to ignore. 429 if (const Expr *Ex = dyn_cast<Expr>(S)) 430 S = Ex->IgnoreParens(); 431 432 // FIXME: add metadata to the CFG so that we can disable 433 // this check when we KNOW that there is no block-level subexpression. 434 // The motivation is that this check requires a hashtable lookup. 435 436 if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) { 437 Dst.Add(Pred); 438 return; 439 } 440 441 switch (S->getStmtClass()) { 442 // C++ and ARC stuff we don't support yet. 443 case Expr::ObjCIndirectCopyRestoreExprClass: 444 case Stmt::CXXBindTemporaryExprClass: 445 case Stmt::CXXCatchStmtClass: 446 case Stmt::CXXDependentScopeMemberExprClass: 447 case Stmt::CXXForRangeStmtClass: 448 case Stmt::CXXPseudoDestructorExprClass: 449 case Stmt::CXXTemporaryObjectExprClass: 450 case Stmt::CXXThrowExprClass: 451 case Stmt::CXXTryStmtClass: 452 case Stmt::CXXTypeidExprClass: 453 case Stmt::CXXUuidofExprClass: 454 case Stmt::CXXUnresolvedConstructExprClass: 455 case Stmt::CXXScalarValueInitExprClass: 456 case Stmt::DependentScopeDeclRefExprClass: 457 case Stmt::UnaryTypeTraitExprClass: 458 case Stmt::BinaryTypeTraitExprClass: 459 case Stmt::ArrayTypeTraitExprClass: 460 case Stmt::ExpressionTraitExprClass: 461 case Stmt::UnresolvedLookupExprClass: 462 case Stmt::UnresolvedMemberExprClass: 463 case Stmt::CXXNoexceptExprClass: 464 case Stmt::PackExpansionExprClass: 465 case Stmt::SubstNonTypeTemplateParmPackExprClass: 466 case Stmt::SEHTryStmtClass: 467 case Stmt::SEHExceptStmtClass: 468 case Stmt::SEHFinallyStmtClass: 469 { 470 SaveAndRestore<bool> OldSink(Builder->BuildSinks); 471 Builder->BuildSinks = true; 472 const ExplodedNode *node = MakeNode(Dst, S, Pred, GetState(Pred)); 473 Engine.addAbortedBlock(node, Builder->getBlock()); 474 break; 475 } 476 477 // We don't handle default arguments either yet, but we can fake it 478 // for now by just skipping them. 479 case Stmt::SubstNonTypeTemplateParmExprClass: 480 case Stmt::CXXDefaultArgExprClass: { 481 Dst.Add(Pred); 482 break; 483 } 484 485 case Stmt::ParenExprClass: 486 llvm_unreachable("ParenExprs already handled."); 487 case Stmt::GenericSelectionExprClass: 488 llvm_unreachable("GenericSelectionExprs already handled."); 489 // Cases that should never be evaluated simply because they shouldn't 490 // appear in the CFG. 491 case Stmt::BreakStmtClass: 492 case Stmt::CaseStmtClass: 493 case Stmt::CompoundStmtClass: 494 case Stmt::ContinueStmtClass: 495 case Stmt::DefaultStmtClass: 496 case Stmt::DoStmtClass: 497 case Stmt::ForStmtClass: 498 case Stmt::GotoStmtClass: 499 case Stmt::IfStmtClass: 500 case Stmt::IndirectGotoStmtClass: 501 case Stmt::LabelStmtClass: 502 case Stmt::NoStmtClass: 503 case Stmt::NullStmtClass: 504 case Stmt::SwitchStmtClass: 505 case Stmt::WhileStmtClass: 506 llvm_unreachable("Stmt should not be in analyzer evaluation loop"); 507 break; 508 509 case Stmt::GNUNullExprClass: { 510 // GNU __null is a pointer-width integer, not an actual pointer. 511 const GRState *state = GetState(Pred); 512 state = state->BindExpr(S, svalBuilder.makeIntValWithPtrWidth(0, false)); 513 MakeNode(Dst, S, Pred, state); 514 break; 515 } 516 517 case Stmt::ObjCAtSynchronizedStmtClass: 518 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); 519 break; 520 521 case Stmt::ObjCPropertyRefExprClass: 522 VisitObjCPropertyRefExpr(cast<ObjCPropertyRefExpr>(S), Pred, Dst); 523 break; 524 525 case Stmt::ImplicitValueInitExprClass: { 526 const GRState *state = GetState(Pred); 527 QualType ty = cast<ImplicitValueInitExpr>(S)->getType(); 528 SVal val = svalBuilder.makeZeroVal(ty); 529 MakeNode(Dst, S, Pred, state->BindExpr(S, val)); 530 break; 531 } 532 533 case Stmt::ExprWithCleanupsClass: { 534 Visit(cast<ExprWithCleanups>(S)->getSubExpr(), Pred, Dst); 535 break; 536 } 537 538 // Cases not handled yet; but will handle some day. 539 case Stmt::DesignatedInitExprClass: 540 case Stmt::ExtVectorElementExprClass: 541 case Stmt::ImaginaryLiteralClass: 542 case Stmt::ObjCAtCatchStmtClass: 543 case Stmt::ObjCAtFinallyStmtClass: 544 case Stmt::ObjCAtTryStmtClass: 545 case Stmt::ObjCAutoreleasePoolStmtClass: 546 case Stmt::ObjCEncodeExprClass: 547 case Stmt::ObjCIsaExprClass: 548 case Stmt::ObjCProtocolExprClass: 549 case Stmt::ObjCSelectorExprClass: 550 case Stmt::ObjCStringLiteralClass: 551 case Stmt::ParenListExprClass: 552 case Stmt::PredefinedExprClass: 553 case Stmt::ShuffleVectorExprClass: 554 case Stmt::VAArgExprClass: 555 case Stmt::CUDAKernelCallExprClass: 556 case Stmt::OpaqueValueExprClass: 557 case Stmt::AsTypeExprClass: 558 // Fall through. 559 560 // Cases we intentionally don't evaluate, since they don't need 561 // to be explicitly evaluated. 562 case Stmt::AddrLabelExprClass: 563 case Stmt::IntegerLiteralClass: 564 case Stmt::CharacterLiteralClass: 565 case Stmt::CXXBoolLiteralExprClass: 566 case Stmt::FloatingLiteralClass: 567 case Stmt::SizeOfPackExprClass: 568 case Stmt::CXXNullPtrLiteralExprClass: 569 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged. 570 break; 571 572 case Stmt::ArraySubscriptExprClass: 573 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); 574 break; 575 576 case Stmt::AsmStmtClass: 577 VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst); 578 break; 579 580 case Stmt::BlockDeclRefExprClass: { 581 const BlockDeclRefExpr *BE = cast<BlockDeclRefExpr>(S); 582 VisitCommonDeclRefExpr(BE, BE->getDecl(), Pred, Dst); 583 break; 584 } 585 586 case Stmt::BlockExprClass: 587 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); 588 break; 589 590 case Stmt::BinaryOperatorClass: { 591 const BinaryOperator* B = cast<BinaryOperator>(S); 592 if (B->isLogicalOp()) { 593 VisitLogicalExpr(B, Pred, Dst); 594 break; 595 } 596 else if (B->getOpcode() == BO_Comma) { 597 const GRState* state = GetState(Pred); 598 MakeNode(Dst, B, Pred, state->BindExpr(B, state->getSVal(B->getRHS()))); 599 break; 600 } 601 602 if (AMgr.shouldEagerlyAssume() && 603 (B->isRelationalOp() || B->isEqualityOp())) { 604 ExplodedNodeSet Tmp; 605 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); 606 evalEagerlyAssume(Dst, Tmp, cast<Expr>(S)); 607 } 608 else 609 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 610 611 break; 612 } 613 614 case Stmt::CallExprClass: 615 case Stmt::CXXOperatorCallExprClass: 616 case Stmt::CXXMemberCallExprClass: { 617 VisitCallExpr(cast<CallExpr>(S), Pred, Dst); 618 break; 619 } 620 621 case Stmt::CXXConstructExprClass: { 622 const CXXConstructExpr *C = cast<CXXConstructExpr>(S); 623 // For block-level CXXConstructExpr, we don't have a destination region. 624 // Let VisitCXXConstructExpr() create one. 625 VisitCXXConstructExpr(C, 0, Pred, Dst); 626 break; 627 } 628 629 case Stmt::CXXNewExprClass: { 630 const CXXNewExpr *NE = cast<CXXNewExpr>(S); 631 VisitCXXNewExpr(NE, Pred, Dst); 632 break; 633 } 634 635 case Stmt::CXXDeleteExprClass: { 636 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S); 637 VisitCXXDeleteExpr(CDE, Pred, Dst); 638 break; 639 } 640 // FIXME: ChooseExpr is really a constant. We need to fix 641 // the CFG do not model them as explicit control-flow. 642 643 case Stmt::ChooseExprClass: { // __builtin_choose_expr 644 const ChooseExpr* C = cast<ChooseExpr>(S); 645 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); 646 break; 647 } 648 649 case Stmt::CompoundAssignOperatorClass: 650 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); 651 break; 652 653 case Stmt::CompoundLiteralExprClass: 654 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); 655 break; 656 657 case Stmt::BinaryConditionalOperatorClass: 658 case Stmt::ConditionalOperatorClass: { // '?' operator 659 const AbstractConditionalOperator *C 660 = cast<AbstractConditionalOperator>(S); 661 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); 662 break; 663 } 664 665 case Stmt::CXXThisExprClass: 666 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); 667 break; 668 669 case Stmt::DeclRefExprClass: { 670 const DeclRefExpr *DE = cast<DeclRefExpr>(S); 671 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); 672 break; 673 } 674 675 case Stmt::DeclStmtClass: 676 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); 677 break; 678 679 case Stmt::ImplicitCastExprClass: 680 case Stmt::CStyleCastExprClass: 681 case Stmt::CXXStaticCastExprClass: 682 case Stmt::CXXDynamicCastExprClass: 683 case Stmt::CXXReinterpretCastExprClass: 684 case Stmt::CXXConstCastExprClass: 685 case Stmt::CXXFunctionalCastExprClass: 686 case Stmt::ObjCBridgedCastExprClass: { 687 const CastExpr* C = cast<CastExpr>(S); 688 // Handle the previsit checks. 689 ExplodedNodeSet dstPrevisit; 690 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this); 691 692 // Handle the expression itself. 693 ExplodedNodeSet dstExpr; 694 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(), 695 e = dstPrevisit.end(); i != e ; ++i) { 696 VisitCast(C, C->getSubExpr(), *i, dstExpr); 697 } 698 699 // Handle the postvisit checks. 700 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this); 701 break; 702 } 703 704 case Expr::MaterializeTemporaryExprClass: { 705 const MaterializeTemporaryExpr *Materialize 706 = cast<MaterializeTemporaryExpr>(S); 707 if (!Materialize->getType()->isRecordType()) 708 CreateCXXTemporaryObject(Materialize->GetTemporaryExpr(), Pred, Dst); 709 else 710 Visit(Materialize->GetTemporaryExpr(), Pred, Dst); 711 break; 712 } 713 714 case Stmt::InitListExprClass: 715 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); 716 break; 717 718 case Stmt::MemberExprClass: 719 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); 720 break; 721 case Stmt::ObjCIvarRefExprClass: 722 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); 723 break; 724 725 case Stmt::ObjCForCollectionStmtClass: 726 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); 727 break; 728 729 case Stmt::ObjCMessageExprClass: 730 VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), Pred, Dst); 731 break; 732 733 case Stmt::ObjCAtThrowStmtClass: { 734 // FIXME: This is not complete. We basically treat @throw as 735 // an abort. 736 SaveAndRestore<bool> OldSink(Builder->BuildSinks); 737 Builder->BuildSinks = true; 738 MakeNode(Dst, S, Pred, GetState(Pred)); 739 break; 740 } 741 742 case Stmt::ReturnStmtClass: 743 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); 744 break; 745 746 case Stmt::OffsetOfExprClass: 747 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst); 748 break; 749 750 case Stmt::UnaryExprOrTypeTraitExprClass: 751 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 752 Pred, Dst); 753 break; 754 755 case Stmt::StmtExprClass: { 756 const StmtExpr* SE = cast<StmtExpr>(S); 757 758 if (SE->getSubStmt()->body_empty()) { 759 // Empty statement expression. 760 assert(SE->getType() == getContext().VoidTy 761 && "Empty statement expression must have void type."); 762 Dst.Add(Pred); 763 break; 764 } 765 766 if (Expr* LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { 767 const GRState* state = GetState(Pred); 768 MakeNode(Dst, SE, Pred, state->BindExpr(SE, state->getSVal(LastExpr))); 769 } 770 else 771 Dst.Add(Pred); 772 773 break; 774 } 775 776 case Stmt::StringLiteralClass: { 777 const GRState* state = GetState(Pred); 778 SVal V = state->getLValue(cast<StringLiteral>(S)); 779 MakeNode(Dst, S, Pred, state->BindExpr(S, V)); 780 return; 781 } 782 783 case Stmt::UnaryOperatorClass: { 784 const UnaryOperator *U = cast<UnaryOperator>(S); 785 if (AMgr.shouldEagerlyAssume()&&(U->getOpcode() == UO_LNot)) { 786 ExplodedNodeSet Tmp; 787 VisitUnaryOperator(U, Pred, Tmp); 788 evalEagerlyAssume(Dst, Tmp, U); 789 } 790 else 791 VisitUnaryOperator(U, Pred, Dst); 792 break; 793 } 794 } 795} 796 797//===----------------------------------------------------------------------===// 798// Block entrance. (Update counters). 799//===----------------------------------------------------------------------===// 800 801void ExprEngine::processCFGBlockEntrance(ExplodedNodeSet &dstNodes, 802 GenericNodeBuilder<BlockEntrance> &nodeBuilder){ 803 804 // FIXME: Refactor this into a checker. 805 const CFGBlock *block = nodeBuilder.getProgramPoint().getBlock(); 806 ExplodedNode *pred = nodeBuilder.getPredecessor(); 807 808 if (nodeBuilder.getBlockCounter().getNumVisited( 809 pred->getLocationContext()->getCurrentStackFrame(), 810 block->getBlockID()) >= AMgr.getMaxVisit()) { 811 812 static int tag = 0; 813 nodeBuilder.generateNode(pred->getState(), pred, &tag, true); 814 } 815} 816 817//===----------------------------------------------------------------------===// 818// Generic node creation. 819//===----------------------------------------------------------------------===// 820 821ExplodedNode* ExprEngine::MakeNode(ExplodedNodeSet& Dst, const Stmt* S, 822 ExplodedNode* Pred, const GRState* St, 823 ProgramPoint::Kind K, const void *tag) { 824 assert (Builder && "StmtNodeBuilder not present."); 825 SaveAndRestore<const void*> OldTag(Builder->Tag); 826 Builder->Tag = tag; 827 return Builder->MakeNode(Dst, S, Pred, St, K); 828} 829 830//===----------------------------------------------------------------------===// 831// Branch processing. 832//===----------------------------------------------------------------------===// 833 834const GRState* ExprEngine::MarkBranch(const GRState* state, 835 const Stmt* Terminator, 836 bool branchTaken) { 837 838 switch (Terminator->getStmtClass()) { 839 default: 840 return state; 841 842 case Stmt::BinaryOperatorClass: { // '&&' and '||' 843 844 const BinaryOperator* B = cast<BinaryOperator>(Terminator); 845 BinaryOperator::Opcode Op = B->getOpcode(); 846 847 assert (Op == BO_LAnd || Op == BO_LOr); 848 849 // For &&, if we take the true branch, then the value of the whole 850 // expression is that of the RHS expression. 851 // 852 // For ||, if we take the false branch, then the value of the whole 853 // expression is that of the RHS expression. 854 855 const Expr* Ex = (Op == BO_LAnd && branchTaken) || 856 (Op == BO_LOr && !branchTaken) 857 ? B->getRHS() : B->getLHS(); 858 859 return state->BindExpr(B, UndefinedVal(Ex)); 860 } 861 862 case Stmt::BinaryConditionalOperatorClass: 863 case Stmt::ConditionalOperatorClass: { // ?: 864 const AbstractConditionalOperator* C 865 = cast<AbstractConditionalOperator>(Terminator); 866 867 // For ?, if branchTaken == true then the value is either the LHS or 868 // the condition itself. (GNU extension). 869 870 const Expr* Ex; 871 872 if (branchTaken) 873 Ex = C->getTrueExpr(); 874 else 875 Ex = C->getFalseExpr(); 876 877 return state->BindExpr(C, UndefinedVal(Ex)); 878 } 879 880 case Stmt::ChooseExprClass: { // ?: 881 882 const ChooseExpr* C = cast<ChooseExpr>(Terminator); 883 884 const Expr* Ex = branchTaken ? C->getLHS() : C->getRHS(); 885 return state->BindExpr(C, UndefinedVal(Ex)); 886 } 887 } 888} 889 890/// RecoverCastedSymbol - A helper function for ProcessBranch that is used 891/// to try to recover some path-sensitivity for casts of symbolic 892/// integers that promote their values (which are currently not tracked well). 893/// This function returns the SVal bound to Condition->IgnoreCasts if all the 894// cast(s) did was sign-extend the original value. 895static SVal RecoverCastedSymbol(GRStateManager& StateMgr, const GRState* state, 896 const Stmt* Condition, ASTContext& Ctx) { 897 898 const Expr *Ex = dyn_cast<Expr>(Condition); 899 if (!Ex) 900 return UnknownVal(); 901 902 uint64_t bits = 0; 903 bool bitsInit = false; 904 905 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 906 QualType T = CE->getType(); 907 908 if (!T->isIntegerType()) 909 return UnknownVal(); 910 911 uint64_t newBits = Ctx.getTypeSize(T); 912 if (!bitsInit || newBits < bits) { 913 bitsInit = true; 914 bits = newBits; 915 } 916 917 Ex = CE->getSubExpr(); 918 } 919 920 // We reached a non-cast. Is it a symbolic value? 921 QualType T = Ex->getType(); 922 923 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits) 924 return UnknownVal(); 925 926 return state->getSVal(Ex); 927} 928 929void ExprEngine::processBranch(const Stmt* Condition, const Stmt* Term, 930 BranchNodeBuilder& builder) { 931 932 // Check for NULL conditions; e.g. "for(;;)" 933 if (!Condition) { 934 builder.markInfeasible(false); 935 return; 936 } 937 938 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), 939 Condition->getLocStart(), 940 "Error evaluating branch"); 941 942 getCheckerManager().runCheckersForBranchCondition(Condition, builder, *this); 943 944 // If the branch condition is undefined, return; 945 if (!builder.isFeasible(true) && !builder.isFeasible(false)) 946 return; 947 948 const GRState* PrevState = builder.getState(); 949 SVal X = PrevState->getSVal(Condition); 950 951 if (X.isUnknownOrUndef()) { 952 // Give it a chance to recover from unknown. 953 if (const Expr *Ex = dyn_cast<Expr>(Condition)) { 954 if (Ex->getType()->isIntegerType()) { 955 // Try to recover some path-sensitivity. Right now casts of symbolic 956 // integers that promote their values are currently not tracked well. 957 // If 'Condition' is such an expression, try and recover the 958 // underlying value and use that instead. 959 SVal recovered = RecoverCastedSymbol(getStateManager(), 960 builder.getState(), Condition, 961 getContext()); 962 963 if (!recovered.isUnknown()) { 964 X = recovered; 965 } 966 } 967 } 968 // If the condition is still unknown, give up. 969 if (X.isUnknownOrUndef()) { 970 builder.generateNode(MarkBranch(PrevState, Term, true), true); 971 builder.generateNode(MarkBranch(PrevState, Term, false), false); 972 return; 973 } 974 } 975 976 DefinedSVal V = cast<DefinedSVal>(X); 977 978 // Process the true branch. 979 if (builder.isFeasible(true)) { 980 if (const GRState *state = PrevState->assume(V, true)) 981 builder.generateNode(MarkBranch(state, Term, true), true); 982 else 983 builder.markInfeasible(true); 984 } 985 986 // Process the false branch. 987 if (builder.isFeasible(false)) { 988 if (const GRState *state = PrevState->assume(V, false)) 989 builder.generateNode(MarkBranch(state, Term, false), false); 990 else 991 builder.markInfeasible(false); 992 } 993} 994 995/// processIndirectGoto - Called by CoreEngine. Used to generate successor 996/// nodes by processing the 'effects' of a computed goto jump. 997void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { 998 999 const GRState *state = builder.getState(); 1000 SVal V = state->getSVal(builder.getTarget()); 1001 1002 // Three possibilities: 1003 // 1004 // (1) We know the computed label. 1005 // (2) The label is NULL (or some other constant), or Undefined. 1006 // (3) We have no clue about the label. Dispatch to all targets. 1007 // 1008 1009 typedef IndirectGotoNodeBuilder::iterator iterator; 1010 1011 if (isa<loc::GotoLabel>(V)) { 1012 const LabelDecl *L = cast<loc::GotoLabel>(V).getLabel(); 1013 1014 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { 1015 if (I.getLabel() == L) { 1016 builder.generateNode(I, state); 1017 return; 1018 } 1019 } 1020 1021 assert(false && "No block with label."); 1022 return; 1023 } 1024 1025 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) { 1026 // Dispatch to the first target and mark it as a sink. 1027 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); 1028 // FIXME: add checker visit. 1029 // UndefBranches.insert(N); 1030 return; 1031 } 1032 1033 // This is really a catch-all. We don't support symbolics yet. 1034 // FIXME: Implement dispatch for symbolic pointers. 1035 1036 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) 1037 builder.generateNode(I, state); 1038} 1039 1040 1041void ExprEngine::VisitGuardedExpr(const Expr* Ex, const Expr* L, 1042 const Expr* R, 1043 ExplodedNode* Pred, ExplodedNodeSet& Dst) { 1044 1045 assert(Ex == currentStmt && 1046 Pred->getLocationContext()->getCFG()->isBlkExpr(Ex)); 1047 1048 const GRState* state = GetState(Pred); 1049 SVal X = state->getSVal(Ex); 1050 1051 assert (X.isUndef()); 1052 1053 const Expr *SE = (Expr*) cast<UndefinedVal>(X).getData(); 1054 assert(SE); 1055 X = state->getSVal(SE); 1056 1057 // Make sure that we invalidate the previous binding. 1058 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, X, true)); 1059} 1060 1061/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path 1062/// nodes when the control reaches the end of a function. 1063void ExprEngine::processEndOfFunction(EndOfFunctionNodeBuilder& builder) { 1064 getTF().evalEndPath(*this, builder); 1065 StateMgr.EndPath(builder.getState()); 1066 getCheckerManager().runCheckersForEndPath(builder, *this); 1067} 1068 1069/// ProcessSwitch - Called by CoreEngine. Used to generate successor 1070/// nodes by processing the 'effects' of a switch statement. 1071void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { 1072 typedef SwitchNodeBuilder::iterator iterator; 1073 const GRState* state = builder.getState(); 1074 const Expr* CondE = builder.getCondition(); 1075 SVal CondV_untested = state->getSVal(CondE); 1076 1077 if (CondV_untested.isUndef()) { 1078 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); 1079 // FIXME: add checker 1080 //UndefBranches.insert(N); 1081 1082 return; 1083 } 1084 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested); 1085 1086 const GRState *DefaultSt = state; 1087 1088 iterator I = builder.begin(), EI = builder.end(); 1089 bool defaultIsFeasible = I == EI; 1090 1091 for ( ; I != EI; ++I) { 1092 // Successor may be pruned out during CFG construction. 1093 if (!I.getBlock()) 1094 continue; 1095 1096 const CaseStmt* Case = I.getCase(); 1097 1098 // Evaluate the LHS of the case value. 1099 Expr::EvalResult V1; 1100 bool b = Case->getLHS()->Evaluate(V1, getContext()); 1101 1102 // Sanity checks. These go away in Release builds. 1103 assert(b && V1.Val.isInt() && !V1.HasSideEffects 1104 && "Case condition must evaluate to an integer constant."); 1105 (void)b; // silence unused variable warning 1106 assert(V1.Val.getInt().getBitWidth() == 1107 getContext().getTypeSize(CondE->getType())); 1108 1109 // Get the RHS of the case, if it exists. 1110 Expr::EvalResult V2; 1111 1112 if (const Expr* E = Case->getRHS()) { 1113 b = E->Evaluate(V2, getContext()); 1114 assert(b && V2.Val.isInt() && !V2.HasSideEffects 1115 && "Case condition must evaluate to an integer constant."); 1116 (void)b; // silence unused variable warning 1117 } 1118 else 1119 V2 = V1; 1120 1121 // FIXME: Eventually we should replace the logic below with a range 1122 // comparison, rather than concretize the values within the range. 1123 // This should be easy once we have "ranges" for NonLVals. 1124 1125 do { 1126 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1.Val.getInt())); 1127 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state, 1128 CondV, CaseVal); 1129 1130 // Now "assume" that the case matches. 1131 if (const GRState* stateNew = state->assume(Res, true)) { 1132 builder.generateCaseStmtNode(I, stateNew); 1133 1134 // If CondV evaluates to a constant, then we know that this 1135 // is the *only* case that we can take, so stop evaluating the 1136 // others. 1137 if (isa<nonloc::ConcreteInt>(CondV)) 1138 return; 1139 } 1140 1141 // Now "assume" that the case doesn't match. Add this state 1142 // to the default state (if it is feasible). 1143 if (DefaultSt) { 1144 if (const GRState *stateNew = DefaultSt->assume(Res, false)) { 1145 defaultIsFeasible = true; 1146 DefaultSt = stateNew; 1147 } 1148 else { 1149 defaultIsFeasible = false; 1150 DefaultSt = NULL; 1151 } 1152 } 1153 1154 // Concretize the next value in the range. 1155 if (V1.Val.getInt() == V2.Val.getInt()) 1156 break; 1157 1158 ++V1.Val.getInt(); 1159 assert (V1.Val.getInt() <= V2.Val.getInt()); 1160 1161 } while (true); 1162 } 1163 1164 if (!defaultIsFeasible) 1165 return; 1166 1167 // If we have switch(enum value), the default branch is not 1168 // feasible if all of the enum constants not covered by 'case:' statements 1169 // are not feasible values for the switch condition. 1170 // 1171 // Note that this isn't as accurate as it could be. Even if there isn't 1172 // a case for a particular enum value as long as that enum value isn't 1173 // feasible then it shouldn't be considered for making 'default:' reachable. 1174 const SwitchStmt *SS = builder.getSwitch(); 1175 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); 1176 if (CondExpr->getType()->getAs<EnumType>()) { 1177 if (SS->isAllEnumCasesCovered()) 1178 return; 1179 } 1180 1181 builder.generateDefaultCaseNode(DefaultSt); 1182} 1183 1184void ExprEngine::processCallEnter(CallEnterNodeBuilder &B) { 1185 const GRState *state = B.getState()->enterStackFrame(B.getCalleeContext()); 1186 B.generateNode(state); 1187} 1188 1189void ExprEngine::processCallExit(CallExitNodeBuilder &B) { 1190 const GRState *state = B.getState(); 1191 const ExplodedNode *Pred = B.getPredecessor(); 1192 const StackFrameContext *calleeCtx = 1193 cast<StackFrameContext>(Pred->getLocationContext()); 1194 const Stmt *CE = calleeCtx->getCallSite(); 1195 1196 // If the callee returns an expression, bind its value to CallExpr. 1197 const Stmt *ReturnedExpr = state->get<ReturnExpr>(); 1198 if (ReturnedExpr) { 1199 SVal RetVal = state->getSVal(ReturnedExpr); 1200 state = state->BindExpr(CE, RetVal); 1201 // Clear the return expr GDM. 1202 state = state->remove<ReturnExpr>(); 1203 } 1204 1205 // Bind the constructed object value to CXXConstructExpr. 1206 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) { 1207 const CXXThisRegion *ThisR = 1208 getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx); 1209 1210 SVal ThisV = state->getSVal(ThisR); 1211 // Always bind the region to the CXXConstructExpr. 1212 state = state->BindExpr(CCE, ThisV); 1213 } 1214 1215 B.generateNode(state); 1216} 1217 1218//===----------------------------------------------------------------------===// 1219// Transfer functions: logical operations ('&&', '||'). 1220//===----------------------------------------------------------------------===// 1221 1222void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode* Pred, 1223 ExplodedNodeSet& Dst) { 1224 1225 assert(B->getOpcode() == BO_LAnd || 1226 B->getOpcode() == BO_LOr); 1227 1228 assert(B==currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(B)); 1229 1230 const GRState* state = GetState(Pred); 1231 SVal X = state->getSVal(B); 1232 assert(X.isUndef()); 1233 1234 const Expr *Ex = (const Expr*) cast<UndefinedVal>(X).getData(); 1235 assert(Ex); 1236 1237 if (Ex == B->getRHS()) { 1238 X = state->getSVal(Ex); 1239 1240 // Handle undefined values. 1241 if (X.isUndef()) { 1242 MakeNode(Dst, B, Pred, state->BindExpr(B, X)); 1243 return; 1244 } 1245 1246 DefinedOrUnknownSVal XD = cast<DefinedOrUnknownSVal>(X); 1247 1248 // We took the RHS. Because the value of the '&&' or '||' expression must 1249 // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0 1250 // or 1. Alternatively, we could take a lazy approach, and calculate this 1251 // value later when necessary. We don't have the machinery in place for 1252 // this right now, and since most logical expressions are used for branches, 1253 // the payoff is not likely to be large. Instead, we do eager evaluation. 1254 if (const GRState *newState = state->assume(XD, true)) 1255 MakeNode(Dst, B, Pred, 1256 newState->BindExpr(B, svalBuilder.makeIntVal(1U, B->getType()))); 1257 1258 if (const GRState *newState = state->assume(XD, false)) 1259 MakeNode(Dst, B, Pred, 1260 newState->BindExpr(B, svalBuilder.makeIntVal(0U, B->getType()))); 1261 } 1262 else { 1263 // We took the LHS expression. Depending on whether we are '&&' or 1264 // '||' we know what the value of the expression is via properties of 1265 // the short-circuiting. 1266 X = svalBuilder.makeIntVal(B->getOpcode() == BO_LAnd ? 0U : 1U, 1267 B->getType()); 1268 MakeNode(Dst, B, Pred, state->BindExpr(B, X)); 1269 } 1270} 1271 1272//===----------------------------------------------------------------------===// 1273// Transfer functions: Loads and stores. 1274//===----------------------------------------------------------------------===// 1275 1276void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, 1277 ExplodedNodeSet &Dst) { 1278 1279 ExplodedNodeSet Tmp; 1280 1281 CanQualType T = getContext().getCanonicalType(BE->getType()); 1282 SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T, 1283 Pred->getLocationContext()); 1284 1285 MakeNode(Tmp, BE, Pred, GetState(Pred)->BindExpr(BE, V), 1286 ProgramPoint::PostLValueKind); 1287 1288 // Post-visit the BlockExpr. 1289 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this); 1290} 1291 1292void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, 1293 ExplodedNode *Pred, 1294 ExplodedNodeSet &Dst) { 1295 const GRState *state = GetState(Pred); 1296 1297 if (const VarDecl* VD = dyn_cast<VarDecl>(D)) { 1298 assert(Ex->isLValue()); 1299 SVal V = state->getLValue(VD, Pred->getLocationContext()); 1300 1301 // For references, the 'lvalue' is the pointer address stored in the 1302 // reference region. 1303 if (VD->getType()->isReferenceType()) { 1304 if (const MemRegion *R = V.getAsRegion()) 1305 V = state->getSVal(R); 1306 else 1307 V = UnknownVal(); 1308 } 1309 1310 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V), 1311 ProgramPoint::PostLValueKind); 1312 return; 1313 } 1314 if (const EnumConstantDecl* ED = dyn_cast<EnumConstantDecl>(D)) { 1315 assert(!Ex->isLValue()); 1316 SVal V = svalBuilder.makeIntVal(ED->getInitVal()); 1317 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V)); 1318 return; 1319 } 1320 if (const FunctionDecl* FD = dyn_cast<FunctionDecl>(D)) { 1321 SVal V = svalBuilder.getFunctionPointer(FD); 1322 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V), 1323 ProgramPoint::PostLValueKind); 1324 return; 1325 } 1326 assert (false && 1327 "ValueDecl support for this ValueDecl not implemented."); 1328} 1329 1330/// VisitArraySubscriptExpr - Transfer function for array accesses 1331void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr* A, 1332 ExplodedNode* Pred, 1333 ExplodedNodeSet& Dst){ 1334 1335 const Expr* Base = A->getBase()->IgnoreParens(); 1336 const Expr* Idx = A->getIdx()->IgnoreParens(); 1337 1338 // Evaluate the base. 1339 ExplodedNodeSet Tmp; 1340 Visit(Base, Pred, Tmp); 1341 1342 for (ExplodedNodeSet::iterator I1=Tmp.begin(), E1=Tmp.end(); I1!=E1; ++I1) { 1343 ExplodedNodeSet Tmp2; 1344 Visit(Idx, *I1, Tmp2); // Evaluate the index. 1345 ExplodedNodeSet Tmp3; 1346 getCheckerManager().runCheckersForPreStmt(Tmp3, Tmp2, A, *this); 1347 1348 for (ExplodedNodeSet::iterator I2=Tmp3.begin(),E2=Tmp3.end();I2!=E2; ++I2) { 1349 const GRState* state = GetState(*I2); 1350 SVal V = state->getLValue(A->getType(), state->getSVal(Idx), 1351 state->getSVal(Base)); 1352 assert(A->isLValue()); 1353 MakeNode(Dst, A, *I2, state->BindExpr(A, V), ProgramPoint::PostLValueKind); 1354 } 1355 } 1356} 1357 1358/// VisitMemberExpr - Transfer function for member expressions. 1359void ExprEngine::VisitMemberExpr(const MemberExpr* M, ExplodedNode* Pred, 1360 ExplodedNodeSet& Dst) { 1361 1362 Expr *baseExpr = M->getBase()->IgnoreParens(); 1363 ExplodedNodeSet dstBase; 1364 Visit(baseExpr, Pred, dstBase); 1365 1366 FieldDecl *field = dyn_cast<FieldDecl>(M->getMemberDecl()); 1367 if (!field) // FIXME: skipping member expressions for non-fields 1368 return; 1369 1370 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end(); 1371 I != E; ++I) { 1372 const GRState* state = GetState(*I); 1373 SVal baseExprVal = state->getSVal(baseExpr); 1374 if (isa<nonloc::LazyCompoundVal>(baseExprVal) || 1375 isa<nonloc::CompoundVal>(baseExprVal) || 1376 // FIXME: This can originate by conjuring a symbol for an unknown 1377 // temporary struct object, see test/Analysis/fields.c: 1378 // (p = getit()).x 1379 isa<nonloc::SymbolVal>(baseExprVal)) { 1380 MakeNode(Dst, M, *I, state->BindExpr(M, UnknownVal())); 1381 continue; 1382 } 1383 1384 // FIXME: Should we insert some assumption logic in here to determine 1385 // if "Base" is a valid piece of memory? Before we put this assumption 1386 // later when using FieldOffset lvals (which we no longer have). 1387 1388 // For all other cases, compute an lvalue. 1389 SVal L = state->getLValue(field, baseExprVal); 1390 if (M->isLValue()) 1391 MakeNode(Dst, M, *I, state->BindExpr(M, L), ProgramPoint::PostLValueKind); 1392 else 1393 evalLoad(Dst, M, *I, state, L); 1394 } 1395} 1396 1397/// evalBind - Handle the semantics of binding a value to a specific location. 1398/// This method is used by evalStore and (soon) VisitDeclStmt, and others. 1399void ExprEngine::evalBind(ExplodedNodeSet& Dst, const Stmt* StoreE, 1400 ExplodedNode* Pred, const GRState* state, 1401 SVal location, SVal Val, bool atDeclInit) { 1402 1403 1404 // Do a previsit of the bind. 1405 ExplodedNodeSet CheckedSet, Src; 1406 Src.Add(Pred); 1407 getCheckerManager().runCheckersForBind(CheckedSet, Src, location, Val, StoreE, 1408 *this); 1409 1410 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 1411 I!=E; ++I) { 1412 1413 if (Pred != *I) 1414 state = GetState(*I); 1415 1416 const GRState* newState = 0; 1417 1418 if (atDeclInit) { 1419 const VarRegion *VR = 1420 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion()); 1421 1422 newState = state->bindDecl(VR, Val); 1423 } 1424 else { 1425 if (location.isUnknown()) { 1426 // We know that the new state will be the same as the old state since 1427 // the location of the binding is "unknown". Consequently, there 1428 // is no reason to just create a new node. 1429 newState = state; 1430 } 1431 else { 1432 // We are binding to a value other than 'unknown'. Perform the binding 1433 // using the StoreManager. 1434 newState = state->bindLoc(cast<Loc>(location), Val); 1435 } 1436 } 1437 1438 // The next thing to do is check if the TransferFuncs object wants to 1439 // update the state based on the new binding. If the GRTransferFunc object 1440 // doesn't do anything, just auto-propagate the current state. 1441 1442 // NOTE: We use 'AssignE' for the location of the PostStore if 'AssignE' 1443 // is non-NULL. Checkers typically care about 1444 1445 StmtNodeBuilderRef BuilderRef(Dst, *Builder, *this, *I, newState, StoreE, 1446 true); 1447 1448 getTF().evalBind(BuilderRef, location, Val); 1449 } 1450} 1451 1452/// evalStore - Handle the semantics of a store via an assignment. 1453/// @param Dst The node set to store generated state nodes 1454/// @param AssignE The assignment expression if the store happens in an 1455/// assignment. 1456/// @param LocatioinE The location expression that is stored to. 1457/// @param state The current simulation state 1458/// @param location The location to store the value 1459/// @param Val The value to be stored 1460void ExprEngine::evalStore(ExplodedNodeSet& Dst, const Expr *AssignE, 1461 const Expr* LocationE, 1462 ExplodedNode* Pred, 1463 const GRState* state, SVal location, SVal Val, 1464 const void *tag) { 1465 1466 assert(Builder && "StmtNodeBuilder must be defined."); 1467 1468 // Proceed with the store. We use AssignE as the anchor for the PostStore 1469 // ProgramPoint if it is non-NULL, and LocationE otherwise. 1470 const Expr *StoreE = AssignE ? AssignE : LocationE; 1471 1472 if (isa<loc::ObjCPropRef>(location)) { 1473 loc::ObjCPropRef prop = cast<loc::ObjCPropRef>(location); 1474 ExplodedNodeSet src = Pred; 1475 return VisitObjCMessage(ObjCPropertySetter(prop.getPropRefExpr(), 1476 StoreE, Val), src, Dst); 1477 } 1478 1479 // Evaluate the location (checks for bad dereferences). 1480 ExplodedNodeSet Tmp; 1481 evalLocation(Tmp, LocationE, Pred, state, location, tag, false); 1482 1483 if (Tmp.empty()) 1484 return; 1485 1486 if (location.isUndef()) 1487 return; 1488 1489 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind, 1490 ProgramPoint::PostStoreKind); 1491 1492 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 1493 evalBind(Dst, StoreE, *NI, GetState(*NI), location, Val); 1494} 1495 1496void ExprEngine::evalLoad(ExplodedNodeSet& Dst, const Expr *Ex, 1497 ExplodedNode* Pred, 1498 const GRState* state, SVal location, 1499 const void *tag, QualType LoadTy) { 1500 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc."); 1501 1502 if (isa<loc::ObjCPropRef>(location)) { 1503 loc::ObjCPropRef prop = cast<loc::ObjCPropRef>(location); 1504 ExplodedNodeSet src = Pred; 1505 return VisitObjCMessage(ObjCPropertyGetter(prop.getPropRefExpr(), Ex), 1506 src, Dst); 1507 } 1508 1509 // Are we loading from a region? This actually results in two loads; one 1510 // to fetch the address of the referenced value and one to fetch the 1511 // referenced value. 1512 if (const TypedRegion *TR = 1513 dyn_cast_or_null<TypedRegion>(location.getAsRegion())) { 1514 1515 QualType ValTy = TR->getValueType(); 1516 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) { 1517 static int loadReferenceTag = 0; 1518 ExplodedNodeSet Tmp; 1519 evalLoadCommon(Tmp, Ex, Pred, state, location, &loadReferenceTag, 1520 getContext().getPointerType(RT->getPointeeType())); 1521 1522 // Perform the load from the referenced value. 1523 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) { 1524 state = GetState(*I); 1525 location = state->getSVal(Ex); 1526 evalLoadCommon(Dst, Ex, *I, state, location, tag, LoadTy); 1527 } 1528 return; 1529 } 1530 } 1531 1532 evalLoadCommon(Dst, Ex, Pred, state, location, tag, LoadTy); 1533} 1534 1535void ExprEngine::evalLoadCommon(ExplodedNodeSet& Dst, const Expr *Ex, 1536 ExplodedNode* Pred, 1537 const GRState* state, SVal location, 1538 const void *tag, QualType LoadTy) { 1539 1540 // Evaluate the location (checks for bad dereferences). 1541 ExplodedNodeSet Tmp; 1542 evalLocation(Tmp, Ex, Pred, state, location, tag, true); 1543 1544 if (Tmp.empty()) 1545 return; 1546 1547 if (location.isUndef()) 1548 return; 1549 1550 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind); 1551 1552 // Proceed with the load. 1553 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 1554 state = GetState(*NI); 1555 1556 if (location.isUnknown()) { 1557 // This is important. We must nuke the old binding. 1558 MakeNode(Dst, Ex, *NI, state->BindExpr(Ex, UnknownVal()), 1559 ProgramPoint::PostLoadKind, tag); 1560 } 1561 else { 1562 if (LoadTy.isNull()) 1563 LoadTy = Ex->getType(); 1564 SVal V = state->getSVal(cast<Loc>(location), LoadTy); 1565 MakeNode(Dst, Ex, *NI, state->bindExprAndLocation(Ex, location, V), 1566 ProgramPoint::PostLoadKind, tag); 1567 } 1568 } 1569} 1570 1571void ExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *S, 1572 ExplodedNode* Pred, 1573 const GRState* state, SVal location, 1574 const void *tag, bool isLoad) { 1575 // Early checks for performance reason. 1576 if (location.isUnknown()) { 1577 Dst.Add(Pred); 1578 return; 1579 } 1580 1581 ExplodedNodeSet Src; 1582 if (Builder->GetState(Pred) == state) { 1583 Src.Add(Pred); 1584 } else { 1585 // Associate this new state with an ExplodedNode. 1586 // FIXME: If I pass null tag, the graph is incorrect, e.g for 1587 // int *p; 1588 // p = 0; 1589 // *p = 0xDEADBEEF; 1590 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 1591 // instead "int *p" is noted as 1592 // "Variable 'p' initialized to a null pointer value" 1593 ExplodedNode *N = Builder->generateNode(S, state, Pred, this); 1594 Src.Add(N ? N : Pred); 1595 } 1596 getCheckerManager().runCheckersForLocation(Dst, Src, location, isLoad, S, 1597 *this); 1598} 1599 1600bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, 1601 ExplodedNode *Pred) { 1602 return false; 1603 1604 // Inlining isn't correct right now because we: 1605 // (a) don't generate CallExit nodes. 1606 // (b) we need a way to postpone doing post-visits of CallExprs until 1607 // the CallExit. This means we need CallExits for the non-inline 1608 // cases as well. 1609 1610#if 0 1611 const GRState *state = GetState(Pred); 1612 const Expr *Callee = CE->getCallee(); 1613 SVal L = state->getSVal(Callee); 1614 1615 const FunctionDecl *FD = L.getAsFunctionDecl(); 1616 if (!FD) 1617 return false; 1618 1619 // Specially handle CXXMethods. 1620 const CXXMethodDecl *methodDecl = 0; 1621 1622 switch (CE->getStmtClass()) { 1623 default: break; 1624 case Stmt::CXXOperatorCallExprClass: { 1625 const CXXOperatorCallExpr *opCall = cast<CXXOperatorCallExpr>(CE); 1626 methodDecl = 1627 dyn_cast_or_null<CXXMethodDecl>(opCall->getCalleeDecl()); 1628 break; 1629 } 1630 case Stmt::CXXMemberCallExprClass: { 1631 const CXXMemberCallExpr *memberCall = cast<CXXMemberCallExpr>(CE); 1632 const MemberExpr *memberExpr = 1633 cast<MemberExpr>(memberCall->getCallee()->IgnoreParens()); 1634 methodDecl = cast<CXXMethodDecl>(memberExpr->getMemberDecl()); 1635 break; 1636 } 1637 } 1638 1639 1640 1641 1642 // Check if the function definition is in the same translation unit. 1643 if (FD->hasBody(FD)) { 1644 const StackFrameContext *stackFrame = 1645 AMgr.getStackFrame(AMgr.getAnalysisContext(FD), 1646 Pred->getLocationContext(), 1647 CE, Builder->getBlock(), Builder->getIndex()); 1648 // Now we have the definition of the callee, create a CallEnter node. 1649 CallEnter Loc(CE, stackFrame, Pred->getLocationContext()); 1650 1651 ExplodedNode *N = Builder->generateNode(Loc, state, Pred); 1652 Dst.Add(N); 1653 return true; 1654 } 1655 1656 // Check if we can find the function definition in other translation units. 1657 if (AMgr.hasIndexer()) { 1658 AnalysisContext *C = AMgr.getAnalysisContextInAnotherTU(FD); 1659 if (C == 0) 1660 return false; 1661 const StackFrameContext *stackFrame = 1662 AMgr.getStackFrame(C, Pred->getLocationContext(), 1663 CE, Builder->getBlock(), Builder->getIndex()); 1664 CallEnter Loc(CE, stackFrame, Pred->getLocationContext()); 1665 ExplodedNode *N = Builder->generateNode(Loc, state, Pred); 1666 Dst.Add(N); 1667 return true; 1668 } 1669 1670 // Generate the CallExit node. 1671 1672 return false; 1673#endif 1674} 1675 1676void ExprEngine::VisitCallExpr(const CallExpr* CE, ExplodedNode* Pred, 1677 ExplodedNodeSet& dst) { 1678 1679 // Determine the type of function we're calling (if available). 1680 const FunctionProtoType *Proto = NULL; 1681 QualType FnType = CE->getCallee()->IgnoreParens()->getType(); 1682 if (const PointerType *FnTypePtr = FnType->getAs<PointerType>()) 1683 Proto = FnTypePtr->getPointeeType()->getAs<FunctionProtoType>(); 1684 1685 // Should the first argument be evaluated as an lvalue? 1686 bool firstArgumentAsLvalue = false; 1687 switch (CE->getStmtClass()) { 1688 case Stmt::CXXOperatorCallExprClass: 1689 firstArgumentAsLvalue = true; 1690 break; 1691 default: 1692 break; 1693 } 1694 1695 // Evaluate the arguments. 1696 ExplodedNodeSet dstArgsEvaluated; 1697 evalArguments(CE->arg_begin(), CE->arg_end(), Proto, Pred, dstArgsEvaluated, 1698 firstArgumentAsLvalue); 1699 1700 // Evaluate the callee. 1701 ExplodedNodeSet dstCalleeEvaluated; 1702 evalCallee(CE, dstArgsEvaluated, dstCalleeEvaluated); 1703 1704 // Perform the previsit of the CallExpr. 1705 ExplodedNodeSet dstPreVisit; 1706 getCheckerManager().runCheckersForPreStmt(dstPreVisit, dstCalleeEvaluated, 1707 CE, *this); 1708 1709 // Now evaluate the call itself. 1710 class DefaultEval : public GraphExpander { 1711 ExprEngine &Eng; 1712 const CallExpr *CE; 1713 public: 1714 1715 DefaultEval(ExprEngine &eng, const CallExpr *ce) 1716 : Eng(eng), CE(ce) {} 1717 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) { 1718 // Should we inline the call? 1719 if (Eng.getAnalysisManager().shouldInlineCall() && 1720 Eng.InlineCall(Dst, CE, Pred)) { 1721 return; 1722 } 1723 1724 StmtNodeBuilder &Builder = Eng.getBuilder(); 1725 assert(&Builder && "StmtNodeBuilder must be defined."); 1726 1727 // Dispatch to the plug-in transfer function. 1728 unsigned oldSize = Dst.size(); 1729 SaveOr OldHasGen(Builder.hasGeneratedNode); 1730 1731 // Dispatch to transfer function logic to handle the call itself. 1732 const Expr* Callee = CE->getCallee()->IgnoreParens(); 1733 const GRState* state = Eng.GetState(Pred); 1734 SVal L = state->getSVal(Callee); 1735 Eng.getTF().evalCall(Dst, Eng, Builder, CE, L, Pred); 1736 1737 // Handle the case where no nodes where generated. Auto-generate that 1738 // contains the updated state if we aren't generating sinks. 1739 if (!Builder.BuildSinks && Dst.size() == oldSize && 1740 !Builder.hasGeneratedNode) 1741 Eng.MakeNode(Dst, CE, Pred, state); 1742 } 1743 }; 1744 1745 // Finally, evaluate the function call. We try each of the checkers 1746 // to see if the can evaluate the function call. 1747 ExplodedNodeSet dstCallEvaluated; 1748 DefaultEval defEval(*this, CE); 1749 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, 1750 dstPreVisit, 1751 CE, *this, &defEval); 1752 1753 // Finally, perform the post-condition check of the CallExpr and store 1754 // the created nodes in 'Dst'. 1755 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 1756 *this); 1757} 1758 1759//===----------------------------------------------------------------------===// 1760// Transfer function: Objective-C dot-syntax to access a property. 1761//===----------------------------------------------------------------------===// 1762 1763void ExprEngine::VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *Ex, 1764 ExplodedNode *Pred, 1765 ExplodedNodeSet &Dst) { 1766 ExplodedNodeSet dstBase; 1767 1768 // Visit the receiver (if any). 1769 if (Ex->isObjectReceiver()) 1770 Visit(Ex->getBase(), Pred, dstBase); 1771 else 1772 dstBase = Pred; 1773 1774 ExplodedNodeSet dstPropRef; 1775 1776 // Using the base, compute the lvalue of the instance variable. 1777 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end(); 1778 I!=E; ++I) { 1779 ExplodedNode *nodeBase = *I; 1780 const GRState *state = GetState(nodeBase); 1781 MakeNode(dstPropRef, Ex, *I, state->BindExpr(Ex, loc::ObjCPropRef(Ex))); 1782 } 1783 1784 Dst.insert(dstPropRef); 1785} 1786 1787//===----------------------------------------------------------------------===// 1788// Transfer function: Objective-C ivar references. 1789//===----------------------------------------------------------------------===// 1790 1791static std::pair<const void*,const void*> EagerlyAssumeTag 1792 = std::pair<const void*,const void*>(&EagerlyAssumeTag,static_cast<void*>(0)); 1793 1794void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, 1795 const Expr *Ex) { 1796 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) { 1797 ExplodedNode *Pred = *I; 1798 1799 // Test if the previous node was as the same expression. This can happen 1800 // when the expression fails to evaluate to anything meaningful and 1801 // (as an optimization) we don't generate a node. 1802 ProgramPoint P = Pred->getLocation(); 1803 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) { 1804 Dst.Add(Pred); 1805 continue; 1806 } 1807 1808 const GRState* state = GetState(Pred); 1809 SVal V = state->getSVal(Ex); 1810 if (nonloc::SymExprVal *SEV = dyn_cast<nonloc::SymExprVal>(&V)) { 1811 // First assume that the condition is true. 1812 if (const GRState *stateTrue = state->assume(*SEV, true)) { 1813 stateTrue = stateTrue->BindExpr(Ex, 1814 svalBuilder.makeIntVal(1U, Ex->getType())); 1815 Dst.Add(Builder->generateNode(PostStmtCustom(Ex, 1816 &EagerlyAssumeTag, Pred->getLocationContext()), 1817 stateTrue, Pred)); 1818 } 1819 1820 // Next, assume that the condition is false. 1821 if (const GRState *stateFalse = state->assume(*SEV, false)) { 1822 stateFalse = stateFalse->BindExpr(Ex, 1823 svalBuilder.makeIntVal(0U, Ex->getType())); 1824 Dst.Add(Builder->generateNode(PostStmtCustom(Ex, &EagerlyAssumeTag, 1825 Pred->getLocationContext()), 1826 stateFalse, Pred)); 1827 } 1828 } 1829 else 1830 Dst.Add(Pred); 1831 } 1832} 1833 1834//===----------------------------------------------------------------------===// 1835// Transfer function: Objective-C @synchronized. 1836//===----------------------------------------------------------------------===// 1837 1838void ExprEngine::VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S, 1839 ExplodedNode *Pred, 1840 ExplodedNodeSet &Dst) { 1841 1842 // The mutex expression is a CFGElement, so we don't need to explicitly 1843 // visit it since it will already be processed. 1844 1845 // Pre-visit the ObjCAtSynchronizedStmt. 1846 ExplodedNodeSet Tmp; 1847 Tmp.Add(Pred); 1848 getCheckerManager().runCheckersForPreStmt(Dst, Tmp, S, *this); 1849} 1850 1851//===----------------------------------------------------------------------===// 1852// Transfer function: Objective-C ivar references. 1853//===----------------------------------------------------------------------===// 1854 1855void ExprEngine::VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr* Ex, 1856 ExplodedNode* Pred, 1857 ExplodedNodeSet& Dst) { 1858 1859 // Visit the base expression, which is needed for computing the lvalue 1860 // of the ivar. 1861 ExplodedNodeSet dstBase; 1862 const Expr *baseExpr = Ex->getBase(); 1863 Visit(baseExpr, Pred, dstBase); 1864 1865 ExplodedNodeSet dstIvar; 1866 1867 // Using the base, compute the lvalue of the instance variable. 1868 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end(); 1869 I!=E; ++I) { 1870 ExplodedNode *nodeBase = *I; 1871 const GRState *state = GetState(nodeBase); 1872 SVal baseVal = state->getSVal(baseExpr); 1873 SVal location = state->getLValue(Ex->getDecl(), baseVal); 1874 MakeNode(dstIvar, Ex, *I, state->BindExpr(Ex, location)); 1875 } 1876 1877 // Perform the post-condition check of the ObjCIvarRefExpr and store 1878 // the created nodes in 'Dst'. 1879 getCheckerManager().runCheckersForPostStmt(Dst, dstIvar, Ex, *this); 1880} 1881 1882//===----------------------------------------------------------------------===// 1883// Transfer function: Objective-C fast enumeration 'for' statements. 1884//===----------------------------------------------------------------------===// 1885 1886void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt* S, 1887 ExplodedNode* Pred, ExplodedNodeSet& Dst) { 1888 1889 // ObjCForCollectionStmts are processed in two places. This method 1890 // handles the case where an ObjCForCollectionStmt* occurs as one of the 1891 // statements within a basic block. This transfer function does two things: 1892 // 1893 // (1) binds the next container value to 'element'. This creates a new 1894 // node in the ExplodedGraph. 1895 // 1896 // (2) binds the value 0/1 to the ObjCForCollectionStmt* itself, indicating 1897 // whether or not the container has any more elements. This value 1898 // will be tested in ProcessBranch. We need to explicitly bind 1899 // this value because a container can contain nil elements. 1900 // 1901 // FIXME: Eventually this logic should actually do dispatches to 1902 // 'countByEnumeratingWithState:objects:count:' (NSFastEnumeration). 1903 // This will require simulating a temporary NSFastEnumerationState, either 1904 // through an SVal or through the use of MemRegions. This value can 1905 // be affixed to the ObjCForCollectionStmt* instead of 0/1; when the loop 1906 // terminates we reclaim the temporary (it goes out of scope) and we 1907 // we can test if the SVal is 0 or if the MemRegion is null (depending 1908 // on what approach we take). 1909 // 1910 // For now: simulate (1) by assigning either a symbol or nil if the 1911 // container is empty. Thus this transfer function will by default 1912 // result in state splitting. 1913 1914 const Stmt* elem = S->getElement(); 1915 SVal ElementV; 1916 1917 if (const DeclStmt* DS = dyn_cast<DeclStmt>(elem)) { 1918 const VarDecl* ElemD = cast<VarDecl>(DS->getSingleDecl()); 1919 assert (ElemD->getInit() == 0); 1920 ElementV = GetState(Pred)->getLValue(ElemD, Pred->getLocationContext()); 1921 VisitObjCForCollectionStmtAux(S, Pred, Dst, ElementV); 1922 return; 1923 } 1924 1925 ExplodedNodeSet Tmp; 1926 Visit(cast<Expr>(elem), Pred, Tmp); 1927 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) { 1928 const GRState* state = GetState(*I); 1929 VisitObjCForCollectionStmtAux(S, *I, Dst, state->getSVal(elem)); 1930 } 1931} 1932 1933void ExprEngine::VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt* S, 1934 ExplodedNode* Pred, ExplodedNodeSet& Dst, 1935 SVal ElementV) { 1936 1937 // Check if the location we are writing back to is a null pointer. 1938 const Stmt* elem = S->getElement(); 1939 ExplodedNodeSet Tmp; 1940 evalLocation(Tmp, elem, Pred, GetState(Pred), ElementV, NULL, false); 1941 1942 if (Tmp.empty()) 1943 return; 1944 1945 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 1946 Pred = *NI; 1947 const GRState *state = GetState(Pred); 1948 1949 // Handle the case where the container still has elements. 1950 SVal TrueV = svalBuilder.makeTruthVal(1); 1951 const GRState *hasElems = state->BindExpr(S, TrueV); 1952 1953 // Handle the case where the container has no elements. 1954 SVal FalseV = svalBuilder.makeTruthVal(0); 1955 const GRState *noElems = state->BindExpr(S, FalseV); 1956 1957 if (loc::MemRegionVal* MV = dyn_cast<loc::MemRegionVal>(&ElementV)) 1958 if (const TypedRegion* R = dyn_cast<TypedRegion>(MV->getRegion())) { 1959 // FIXME: The proper thing to do is to really iterate over the 1960 // container. We will do this with dispatch logic to the store. 1961 // For now, just 'conjure' up a symbolic value. 1962 QualType T = R->getValueType(); 1963 assert(Loc::isLocType(T)); 1964 unsigned Count = Builder->getCurrentBlockCount(); 1965 SymbolRef Sym = SymMgr.getConjuredSymbol(elem, T, Count); 1966 SVal V = svalBuilder.makeLoc(Sym); 1967 hasElems = hasElems->bindLoc(ElementV, V); 1968 1969 // Bind the location to 'nil' on the false branch. 1970 SVal nilV = svalBuilder.makeIntVal(0, T); 1971 noElems = noElems->bindLoc(ElementV, nilV); 1972 } 1973 1974 // Create the new nodes. 1975 MakeNode(Dst, S, Pred, hasElems); 1976 MakeNode(Dst, S, Pred, noElems); 1977 } 1978} 1979 1980//===----------------------------------------------------------------------===// 1981// Transfer function: Objective-C message expressions. 1982//===----------------------------------------------------------------------===// 1983 1984namespace { 1985class ObjCMsgWLItem { 1986public: 1987 ObjCMessageExpr::const_arg_iterator I; 1988 ExplodedNode *N; 1989 1990 ObjCMsgWLItem(const ObjCMessageExpr::const_arg_iterator &i, ExplodedNode *n) 1991 : I(i), N(n) {} 1992}; 1993} // end anonymous namespace 1994 1995void ExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr* ME, 1996 ExplodedNode* Pred, 1997 ExplodedNodeSet& Dst){ 1998 1999 // Create a worklist to process both the arguments. 2000 SmallVector<ObjCMsgWLItem, 20> WL; 2001 2002 // But first evaluate the receiver (if any). 2003 ObjCMessageExpr::const_arg_iterator AI = ME->arg_begin(), AE = ME->arg_end(); 2004 if (const Expr *Receiver = ME->getInstanceReceiver()) { 2005 ExplodedNodeSet Tmp; 2006 Visit(Receiver, Pred, Tmp); 2007 2008 if (Tmp.empty()) 2009 return; 2010 2011 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) 2012 WL.push_back(ObjCMsgWLItem(AI, *I)); 2013 } 2014 else 2015 WL.push_back(ObjCMsgWLItem(AI, Pred)); 2016 2017 // Evaluate the arguments. 2018 ExplodedNodeSet ArgsEvaluated; 2019 while (!WL.empty()) { 2020 ObjCMsgWLItem Item = WL.back(); 2021 WL.pop_back(); 2022 2023 if (Item.I == AE) { 2024 ArgsEvaluated.insert(Item.N); 2025 continue; 2026 } 2027 2028 // Evaluate the subexpression. 2029 ExplodedNodeSet Tmp; 2030 2031 // FIXME: [Objective-C++] handle arguments that are references 2032 Visit(*Item.I, Item.N, Tmp); 2033 2034 // Enqueue evaluating the next argument on the worklist. 2035 ++(Item.I); 2036 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 2037 WL.push_back(ObjCMsgWLItem(Item.I, *NI)); 2038 } 2039 2040 // Now that the arguments are processed, handle the ObjC message. 2041 VisitObjCMessage(ME, ArgsEvaluated, Dst); 2042} 2043 2044void ExprEngine::VisitObjCMessage(const ObjCMessage &msg, 2045 ExplodedNodeSet &Src, ExplodedNodeSet& Dst) { 2046 2047 // Handle the previsits checks. 2048 ExplodedNodeSet DstPrevisit; 2049 getCheckerManager().runCheckersForPreObjCMessage(DstPrevisit, Src, msg,*this); 2050 2051 // Proceed with evaluate the message expression. 2052 ExplodedNodeSet dstEval; 2053 2054 for (ExplodedNodeSet::iterator DI = DstPrevisit.begin(), 2055 DE = DstPrevisit.end(); DI != DE; ++DI) { 2056 2057 ExplodedNode *Pred = *DI; 2058 bool RaisesException = false; 2059 unsigned oldSize = dstEval.size(); 2060 SaveAndRestore<bool> OldSink(Builder->BuildSinks); 2061 SaveOr OldHasGen(Builder->hasGeneratedNode); 2062 2063 if (const Expr *Receiver = msg.getInstanceReceiver()) { 2064 const GRState *state = GetState(Pred); 2065 SVal recVal = state->getSVal(Receiver); 2066 if (!recVal.isUndef()) { 2067 // Bifurcate the state into nil and non-nil ones. 2068 DefinedOrUnknownSVal receiverVal = cast<DefinedOrUnknownSVal>(recVal); 2069 2070 const GRState *notNilState, *nilState; 2071 llvm::tie(notNilState, nilState) = state->assume(receiverVal); 2072 2073 // There are three cases: can be nil or non-nil, must be nil, must be 2074 // non-nil. We ignore must be nil, and merge the rest two into non-nil. 2075 if (nilState && !notNilState) { 2076 dstEval.insert(Pred); 2077 continue; 2078 } 2079 2080 // Check if the "raise" message was sent. 2081 assert(notNilState); 2082 if (msg.getSelector() == RaiseSel) 2083 RaisesException = true; 2084 2085 // Check if we raise an exception. For now treat these as sinks. 2086 // Eventually we will want to handle exceptions properly. 2087 if (RaisesException) 2088 Builder->BuildSinks = true; 2089 2090 // Dispatch to plug-in transfer function. 2091 evalObjCMessage(dstEval, msg, Pred, notNilState); 2092 } 2093 } 2094 else if (const ObjCInterfaceDecl *Iface = msg.getReceiverInterface()) { 2095 IdentifierInfo* ClsName = Iface->getIdentifier(); 2096 Selector S = msg.getSelector(); 2097 2098 // Check for special instance methods. 2099 if (!NSExceptionII) { 2100 ASTContext& Ctx = getContext(); 2101 NSExceptionII = &Ctx.Idents.get("NSException"); 2102 } 2103 2104 if (ClsName == NSExceptionII) { 2105 enum { NUM_RAISE_SELECTORS = 2 }; 2106 2107 // Lazily create a cache of the selectors. 2108 if (!NSExceptionInstanceRaiseSelectors) { 2109 ASTContext& Ctx = getContext(); 2110 NSExceptionInstanceRaiseSelectors = 2111 new Selector[NUM_RAISE_SELECTORS]; 2112 SmallVector<IdentifierInfo*, NUM_RAISE_SELECTORS> II; 2113 unsigned idx = 0; 2114 2115 // raise:format: 2116 II.push_back(&Ctx.Idents.get("raise")); 2117 II.push_back(&Ctx.Idents.get("format")); 2118 NSExceptionInstanceRaiseSelectors[idx++] = 2119 Ctx.Selectors.getSelector(II.size(), &II[0]); 2120 2121 // raise:format::arguments: 2122 II.push_back(&Ctx.Idents.get("arguments")); 2123 NSExceptionInstanceRaiseSelectors[idx++] = 2124 Ctx.Selectors.getSelector(II.size(), &II[0]); 2125 } 2126 2127 for (unsigned i = 0; i < NUM_RAISE_SELECTORS; ++i) 2128 if (S == NSExceptionInstanceRaiseSelectors[i]) { 2129 RaisesException = true; 2130 break; 2131 } 2132 } 2133 2134 // Check if we raise an exception. For now treat these as sinks. 2135 // Eventually we will want to handle exceptions properly. 2136 if (RaisesException) 2137 Builder->BuildSinks = true; 2138 2139 // Dispatch to plug-in transfer function. 2140 evalObjCMessage(dstEval, msg, Pred, Builder->GetState(Pred)); 2141 } 2142 2143 // Handle the case where no nodes where generated. Auto-generate that 2144 // contains the updated state if we aren't generating sinks. 2145 if (!Builder->BuildSinks && dstEval.size() == oldSize && 2146 !Builder->hasGeneratedNode) 2147 MakeNode(dstEval, msg.getOriginExpr(), Pred, GetState(Pred)); 2148 } 2149 2150 // Finally, perform the post-condition check of the ObjCMessageExpr and store 2151 // the created nodes in 'Dst'. 2152 getCheckerManager().runCheckersForPostObjCMessage(Dst, dstEval, msg, *this); 2153} 2154 2155//===----------------------------------------------------------------------===// 2156// Transfer functions: Miscellaneous statements. 2157//===----------------------------------------------------------------------===// 2158 2159void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, 2160 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 2161 2162 ExplodedNodeSet S1; 2163 Visit(Ex, Pred, S1); 2164 ExplodedNodeSet S2; 2165 getCheckerManager().runCheckersForPreStmt(S2, S1, CastE, *this); 2166 2167 if (CastE->getCastKind() == CK_LValueToRValue || 2168 CastE->getCastKind() == CK_GetObjCProperty) { 2169 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I!=E; ++I) { 2170 ExplodedNode *subExprNode = *I; 2171 const GRState *state = GetState(subExprNode); 2172 evalLoad(Dst, CastE, subExprNode, state, state->getSVal(Ex)); 2173 } 2174 return; 2175 } 2176 2177 // All other casts. 2178 QualType T = CastE->getType(); 2179 QualType ExTy = Ex->getType(); 2180 2181 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE)) 2182 T = ExCast->getTypeAsWritten(); 2183 2184 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) { 2185 Pred = *I; 2186 2187 switch (CastE->getCastKind()) { 2188 case CK_LValueToRValue: 2189 assert(false && "LValueToRValue casts handled earlier."); 2190 case CK_GetObjCProperty: 2191 assert(false && "GetObjCProperty casts handled earlier."); 2192 case CK_ToVoid: 2193 Dst.Add(Pred); 2194 continue; 2195 // The analyzer doesn't do anything special with these casts, 2196 // since it understands retain/release semantics already. 2197 case CK_ObjCProduceObject: 2198 case CK_ObjCConsumeObject: 2199 case CK_ObjCReclaimReturnedObject: // Fall-through. 2200 // True no-ops. 2201 case CK_NoOp: 2202 case CK_FunctionToPointerDecay: { 2203 // Copy the SVal of Ex to CastE. 2204 const GRState *state = GetState(Pred); 2205 SVal V = state->getSVal(Ex); 2206 state = state->BindExpr(CastE, V); 2207 MakeNode(Dst, CastE, Pred, state); 2208 continue; 2209 } 2210 case CK_Dependent: 2211 case CK_ArrayToPointerDecay: 2212 case CK_BitCast: 2213 case CK_LValueBitCast: 2214 case CK_IntegralCast: 2215 case CK_NullToPointer: 2216 case CK_IntegralToPointer: 2217 case CK_PointerToIntegral: 2218 case CK_PointerToBoolean: 2219 case CK_IntegralToBoolean: 2220 case CK_IntegralToFloating: 2221 case CK_FloatingToIntegral: 2222 case CK_FloatingToBoolean: 2223 case CK_FloatingCast: 2224 case CK_FloatingRealToComplex: 2225 case CK_FloatingComplexToReal: 2226 case CK_FloatingComplexToBoolean: 2227 case CK_FloatingComplexCast: 2228 case CK_FloatingComplexToIntegralComplex: 2229 case CK_IntegralRealToComplex: 2230 case CK_IntegralComplexToReal: 2231 case CK_IntegralComplexToBoolean: 2232 case CK_IntegralComplexCast: 2233 case CK_IntegralComplexToFloatingComplex: 2234 case CK_AnyPointerToObjCPointerCast: 2235 case CK_AnyPointerToBlockPointerCast: 2236 case CK_ObjCObjectLValueCast: { 2237 // Delegate to SValBuilder to process. 2238 const GRState* state = GetState(Pred); 2239 SVal V = state->getSVal(Ex); 2240 V = svalBuilder.evalCast(V, T, ExTy); 2241 state = state->BindExpr(CastE, V); 2242 MakeNode(Dst, CastE, Pred, state); 2243 continue; 2244 } 2245 case CK_DerivedToBase: 2246 case CK_UncheckedDerivedToBase: { 2247 // For DerivedToBase cast, delegate to the store manager. 2248 const GRState *state = GetState(Pred); 2249 SVal val = state->getSVal(Ex); 2250 val = getStoreManager().evalDerivedToBase(val, T); 2251 state = state->BindExpr(CastE, val); 2252 MakeNode(Dst, CastE, Pred, state); 2253 continue; 2254 } 2255 // Various C++ casts that are not handled yet. 2256 case CK_Dynamic: 2257 case CK_ToUnion: 2258 case CK_BaseToDerived: 2259 case CK_NullToMemberPointer: 2260 case CK_BaseToDerivedMemberPointer: 2261 case CK_DerivedToBaseMemberPointer: 2262 case CK_UserDefinedConversion: 2263 case CK_ConstructorConversion: 2264 case CK_VectorSplat: 2265 case CK_MemberPointerToBoolean: { 2266 // Recover some path-sensitivty by conjuring a new value. 2267 QualType resultType = CastE->getType(); 2268 if (CastE->isLValue()) 2269 resultType = getContext().getPointerType(resultType); 2270 2271 SVal result = 2272 svalBuilder.getConjuredSymbolVal(NULL, CastE, resultType, 2273 Builder->getCurrentBlockCount()); 2274 2275 const GRState *state = GetState(Pred)->BindExpr(CastE, result); 2276 MakeNode(Dst, CastE, Pred, state); 2277 continue; 2278 } 2279 } 2280 } 2281} 2282 2283void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr* CL, 2284 ExplodedNode* Pred, 2285 ExplodedNodeSet& Dst) { 2286 const InitListExpr* ILE 2287 = cast<InitListExpr>(CL->getInitializer()->IgnoreParens()); 2288 ExplodedNodeSet Tmp; 2289 Visit(ILE, Pred, Tmp); 2290 2291 for (ExplodedNodeSet::iterator I = Tmp.begin(), EI = Tmp.end(); I!=EI; ++I) { 2292 const GRState* state = GetState(*I); 2293 SVal ILV = state->getSVal(ILE); 2294 const LocationContext *LC = (*I)->getLocationContext(); 2295 state = state->bindCompoundLiteral(CL, LC, ILV); 2296 2297 if (CL->isLValue()) { 2298 MakeNode(Dst, CL, *I, state->BindExpr(CL, state->getLValue(CL, LC))); 2299 } 2300 else 2301 MakeNode(Dst, CL, *I, state->BindExpr(CL, ILV)); 2302 } 2303} 2304 2305void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, 2306 ExplodedNodeSet& Dst) { 2307 2308 // The CFG has one DeclStmt per Decl. 2309 const Decl* D = *DS->decl_begin(); 2310 2311 if (!D || !isa<VarDecl>(D)) 2312 return; 2313 2314 const VarDecl* VD = dyn_cast<VarDecl>(D); 2315 const Expr* InitEx = VD->getInit(); 2316 2317 // FIXME: static variables may have an initializer, but the second 2318 // time a function is called those values may not be current. 2319 ExplodedNodeSet Tmp; 2320 2321 if (InitEx) 2322 Visit(InitEx, Pred, Tmp); 2323 else 2324 Tmp.Add(Pred); 2325 2326 ExplodedNodeSet Tmp2; 2327 getCheckerManager().runCheckersForPreStmt(Tmp2, Tmp, DS, *this); 2328 2329 for (ExplodedNodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) { 2330 ExplodedNode *N = *I; 2331 const GRState *state = GetState(N); 2332 2333 // Decls without InitExpr are not initialized explicitly. 2334 const LocationContext *LC = N->getLocationContext(); 2335 2336 if (InitEx) { 2337 SVal InitVal = state->getSVal(InitEx); 2338 2339 // We bound the temp obj region to the CXXConstructExpr. Now recover 2340 // the lazy compound value when the variable is not a reference. 2341 if (AMgr.getLangOptions().CPlusPlus && VD->getType()->isRecordType() && 2342 !VD->getType()->isReferenceType() && isa<loc::MemRegionVal>(InitVal)){ 2343 InitVal = state->getSVal(cast<loc::MemRegionVal>(InitVal).getRegion()); 2344 assert(isa<nonloc::LazyCompoundVal>(InitVal)); 2345 } 2346 2347 // Recover some path-sensitivity if a scalar value evaluated to 2348 // UnknownVal. 2349 if ((InitVal.isUnknown() || 2350 !getConstraintManager().canReasonAbout(InitVal)) && 2351 !VD->getType()->isReferenceType()) { 2352 InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx, 2353 Builder->getCurrentBlockCount()); 2354 } 2355 2356 evalBind(Dst, DS, *I, state, 2357 loc::MemRegionVal(state->getRegion(VD, LC)), InitVal, true); 2358 } 2359 else { 2360 state = state->bindDeclWithNoInit(state->getRegion(VD, LC)); 2361 MakeNode(Dst, DS, *I, state); 2362 } 2363 } 2364} 2365 2366namespace { 2367 // This class is used by VisitInitListExpr as an item in a worklist 2368 // for processing the values contained in an InitListExpr. 2369class InitListWLItem { 2370public: 2371 llvm::ImmutableList<SVal> Vals; 2372 ExplodedNode* N; 2373 InitListExpr::const_reverse_iterator Itr; 2374 2375 InitListWLItem(ExplodedNode* n, llvm::ImmutableList<SVal> vals, 2376 InitListExpr::const_reverse_iterator itr) 2377 : Vals(vals), N(n), Itr(itr) {} 2378}; 2379} 2380 2381 2382void ExprEngine::VisitInitListExpr(const InitListExpr* E, ExplodedNode* Pred, 2383 ExplodedNodeSet& Dst) { 2384 2385 const GRState* state = GetState(Pred); 2386 QualType T = getContext().getCanonicalType(E->getType()); 2387 unsigned NumInitElements = E->getNumInits(); 2388 2389 if (T->isArrayType() || T->isRecordType() || T->isVectorType()) { 2390 llvm::ImmutableList<SVal> StartVals = getBasicVals().getEmptySValList(); 2391 2392 // Handle base case where the initializer has no elements. 2393 // e.g: static int* myArray[] = {}; 2394 if (NumInitElements == 0) { 2395 SVal V = svalBuilder.makeCompoundVal(T, StartVals); 2396 MakeNode(Dst, E, Pred, state->BindExpr(E, V)); 2397 return; 2398 } 2399 2400 // Create a worklist to process the initializers. 2401 SmallVector<InitListWLItem, 10> WorkList; 2402 WorkList.reserve(NumInitElements); 2403 WorkList.push_back(InitListWLItem(Pred, StartVals, E->rbegin())); 2404 InitListExpr::const_reverse_iterator ItrEnd = E->rend(); 2405 assert(!(E->rbegin() == E->rend())); 2406 2407 // Process the worklist until it is empty. 2408 while (!WorkList.empty()) { 2409 InitListWLItem X = WorkList.back(); 2410 WorkList.pop_back(); 2411 2412 ExplodedNodeSet Tmp; 2413 Visit(*X.Itr, X.N, Tmp); 2414 2415 InitListExpr::const_reverse_iterator NewItr = X.Itr + 1; 2416 2417 for (ExplodedNodeSet::iterator NI=Tmp.begin(),NE=Tmp.end();NI!=NE;++NI) { 2418 // Get the last initializer value. 2419 state = GetState(*NI); 2420 SVal InitV = state->getSVal(cast<Expr>(*X.Itr)); 2421 2422 // Construct the new list of values by prepending the new value to 2423 // the already constructed list. 2424 llvm::ImmutableList<SVal> NewVals = 2425 getBasicVals().consVals(InitV, X.Vals); 2426 2427 if (NewItr == ItrEnd) { 2428 // Now we have a list holding all init values. Make CompoundValData. 2429 SVal V = svalBuilder.makeCompoundVal(T, NewVals); 2430 2431 // Make final state and node. 2432 MakeNode(Dst, E, *NI, state->BindExpr(E, V)); 2433 } 2434 else { 2435 // Still some initializer values to go. Push them onto the worklist. 2436 WorkList.push_back(InitListWLItem(*NI, NewVals, NewItr)); 2437 } 2438 } 2439 } 2440 2441 return; 2442 } 2443 2444 if (Loc::isLocType(T) || T->isIntegerType()) { 2445 assert (E->getNumInits() == 1); 2446 ExplodedNodeSet Tmp; 2447 const Expr* Init = E->getInit(0); 2448 Visit(Init, Pred, Tmp); 2449 for (ExplodedNodeSet::iterator I=Tmp.begin(), EI=Tmp.end(); I != EI; ++I) { 2450 state = GetState(*I); 2451 MakeNode(Dst, E, *I, state->BindExpr(E, state->getSVal(Init))); 2452 } 2453 return; 2454 } 2455 2456 assert(0 && "unprocessed InitListExpr type"); 2457} 2458 2459/// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof(type). 2460void ExprEngine::VisitUnaryExprOrTypeTraitExpr( 2461 const UnaryExprOrTypeTraitExpr* Ex, 2462 ExplodedNode* Pred, 2463 ExplodedNodeSet& Dst) { 2464 QualType T = Ex->getTypeOfArgument(); 2465 2466 if (Ex->getKind() == UETT_SizeOf) { 2467 if (!T->isIncompleteType() && !T->isConstantSizeType()) { 2468 assert(T->isVariableArrayType() && "Unknown non-constant-sized type."); 2469 2470 // FIXME: Add support for VLA type arguments, not just VLA expressions. 2471 // When that happens, we should probably refactor VLASizeChecker's code. 2472 if (Ex->isArgumentType()) { 2473 Dst.Add(Pred); 2474 return; 2475 } 2476 2477 // Get the size by getting the extent of the sub-expression. 2478 // First, visit the sub-expression to find its region. 2479 const Expr *Arg = Ex->getArgumentExpr(); 2480 ExplodedNodeSet Tmp; 2481 Visit(Arg, Pred, Tmp); 2482 2483 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2484 const GRState* state = GetState(*I); 2485 const MemRegion *MR = state->getSVal(Arg).getAsRegion(); 2486 2487 // If the subexpression can't be resolved to a region, we don't know 2488 // anything about its size. Just leave the state as is and continue. 2489 if (!MR) { 2490 Dst.Add(*I); 2491 continue; 2492 } 2493 2494 // The result is the extent of the VLA. 2495 SVal Extent = cast<SubRegion>(MR)->getExtent(svalBuilder); 2496 MakeNode(Dst, Ex, *I, state->BindExpr(Ex, Extent)); 2497 } 2498 2499 return; 2500 } 2501 else if (T->getAs<ObjCObjectType>()) { 2502 // Some code tries to take the sizeof an ObjCObjectType, relying that 2503 // the compiler has laid out its representation. Just report Unknown 2504 // for these. 2505 Dst.Add(Pred); 2506 return; 2507 } 2508 } 2509 2510 Expr::EvalResult Result; 2511 Ex->Evaluate(Result, getContext()); 2512 CharUnits amt = CharUnits::fromQuantity(Result.Val.getInt().getZExtValue()); 2513 2514 MakeNode(Dst, Ex, Pred, 2515 GetState(Pred)->BindExpr(Ex, 2516 svalBuilder.makeIntVal(amt.getQuantity(), Ex->getType()))); 2517} 2518 2519void ExprEngine::VisitOffsetOfExpr(const OffsetOfExpr* OOE, 2520 ExplodedNode* Pred, ExplodedNodeSet& Dst) { 2521 Expr::EvalResult Res; 2522 if (OOE->Evaluate(Res, getContext()) && Res.Val.isInt()) { 2523 const APSInt &IV = Res.Val.getInt(); 2524 assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType())); 2525 assert(OOE->getType()->isIntegerType()); 2526 assert(IV.isSigned() == OOE->getType()->isSignedIntegerOrEnumerationType()); 2527 SVal X = svalBuilder.makeIntVal(IV); 2528 MakeNode(Dst, OOE, Pred, GetState(Pred)->BindExpr(OOE, X)); 2529 return; 2530 } 2531 // FIXME: Handle the case where __builtin_offsetof is not a constant. 2532 Dst.Add(Pred); 2533} 2534 2535void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, 2536 ExplodedNode* Pred, 2537 ExplodedNodeSet& Dst) { 2538 2539 switch (U->getOpcode()) { 2540 2541 default: 2542 break; 2543 2544 case UO_Real: { 2545 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2546 ExplodedNodeSet Tmp; 2547 Visit(Ex, Pred, Tmp); 2548 2549 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2550 2551 // FIXME: We don't have complex SValues yet. 2552 if (Ex->getType()->isAnyComplexType()) { 2553 // Just report "Unknown." 2554 Dst.Add(*I); 2555 continue; 2556 } 2557 2558 // For all other types, UO_Real is an identity operation. 2559 assert (U->getType() == Ex->getType()); 2560 const GRState* state = GetState(*I); 2561 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex))); 2562 } 2563 2564 return; 2565 } 2566 2567 case UO_Imag: { 2568 2569 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2570 ExplodedNodeSet Tmp; 2571 Visit(Ex, Pred, Tmp); 2572 2573 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2574 // FIXME: We don't have complex SValues yet. 2575 if (Ex->getType()->isAnyComplexType()) { 2576 // Just report "Unknown." 2577 Dst.Add(*I); 2578 continue; 2579 } 2580 2581 // For all other types, UO_Imag returns 0. 2582 const GRState* state = GetState(*I); 2583 SVal X = svalBuilder.makeZeroVal(Ex->getType()); 2584 MakeNode(Dst, U, *I, state->BindExpr(U, X)); 2585 } 2586 2587 return; 2588 } 2589 2590 case UO_Plus: 2591 assert(!U->isLValue()); 2592 // FALL-THROUGH. 2593 case UO_Deref: 2594 case UO_AddrOf: 2595 case UO_Extension: { 2596 2597 // Unary "+" is a no-op, similar to a parentheses. We still have places 2598 // where it may be a block-level expression, so we need to 2599 // generate an extra node that just propagates the value of the 2600 // subexpression. 2601 2602 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2603 ExplodedNodeSet Tmp; 2604 Visit(Ex, Pred, Tmp); 2605 2606 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2607 const GRState* state = GetState(*I); 2608 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex))); 2609 } 2610 2611 return; 2612 } 2613 2614 case UO_LNot: 2615 case UO_Minus: 2616 case UO_Not: { 2617 assert (!U->isLValue()); 2618 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2619 ExplodedNodeSet Tmp; 2620 Visit(Ex, Pred, Tmp); 2621 2622 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2623 const GRState* state = GetState(*I); 2624 2625 // Get the value of the subexpression. 2626 SVal V = state->getSVal(Ex); 2627 2628 if (V.isUnknownOrUndef()) { 2629 MakeNode(Dst, U, *I, state->BindExpr(U, V)); 2630 continue; 2631 } 2632 2633// QualType DstT = getContext().getCanonicalType(U->getType()); 2634// QualType SrcT = getContext().getCanonicalType(Ex->getType()); 2635// 2636// if (DstT != SrcT) // Perform promotions. 2637// V = evalCast(V, DstT); 2638// 2639// if (V.isUnknownOrUndef()) { 2640// MakeNode(Dst, U, *I, BindExpr(St, U, V)); 2641// continue; 2642// } 2643 2644 switch (U->getOpcode()) { 2645 default: 2646 assert(false && "Invalid Opcode."); 2647 break; 2648 2649 case UO_Not: 2650 // FIXME: Do we need to handle promotions? 2651 state = state->BindExpr(U, evalComplement(cast<NonLoc>(V))); 2652 break; 2653 2654 case UO_Minus: 2655 // FIXME: Do we need to handle promotions? 2656 state = state->BindExpr(U, evalMinus(cast<NonLoc>(V))); 2657 break; 2658 2659 case UO_LNot: 2660 2661 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)." 2662 // 2663 // Note: technically we do "E == 0", but this is the same in the 2664 // transfer functions as "0 == E". 2665 SVal Result; 2666 2667 if (isa<Loc>(V)) { 2668 Loc X = svalBuilder.makeNull(); 2669 Result = evalBinOp(state, BO_EQ, cast<Loc>(V), X, 2670 U->getType()); 2671 } 2672 else { 2673 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType())); 2674 Result = evalBinOp(state, BO_EQ, cast<NonLoc>(V), X, 2675 U->getType()); 2676 } 2677 2678 state = state->BindExpr(U, Result); 2679 2680 break; 2681 } 2682 2683 MakeNode(Dst, U, *I, state); 2684 } 2685 2686 return; 2687 } 2688 } 2689 2690 // Handle ++ and -- (both pre- and post-increment). 2691 assert (U->isIncrementDecrementOp()); 2692 ExplodedNodeSet Tmp; 2693 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2694 Visit(Ex, Pred, Tmp); 2695 2696 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) { 2697 2698 const GRState* state = GetState(*I); 2699 SVal loc = state->getSVal(Ex); 2700 2701 // Perform a load. 2702 ExplodedNodeSet Tmp2; 2703 evalLoad(Tmp2, Ex, *I, state, loc); 2704 2705 for (ExplodedNodeSet::iterator I2=Tmp2.begin(), E2=Tmp2.end();I2!=E2;++I2) { 2706 2707 state = GetState(*I2); 2708 SVal V2_untested = state->getSVal(Ex); 2709 2710 // Propagate unknown and undefined values. 2711 if (V2_untested.isUnknownOrUndef()) { 2712 MakeNode(Dst, U, *I2, state->BindExpr(U, V2_untested)); 2713 continue; 2714 } 2715 DefinedSVal V2 = cast<DefinedSVal>(V2_untested); 2716 2717 // Handle all other values. 2718 BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add 2719 : BO_Sub; 2720 2721 // If the UnaryOperator has non-location type, use its type to create the 2722 // constant value. If the UnaryOperator has location type, create the 2723 // constant with int type and pointer width. 2724 SVal RHS; 2725 2726 if (U->getType()->isAnyPointerType()) 2727 RHS = svalBuilder.makeArrayIndex(1); 2728 else 2729 RHS = svalBuilder.makeIntVal(1, U->getType()); 2730 2731 SVal Result = evalBinOp(state, Op, V2, RHS, U->getType()); 2732 2733 // Conjure a new symbol if necessary to recover precision. 2734 if (Result.isUnknown() || !getConstraintManager().canReasonAbout(Result)){ 2735 DefinedOrUnknownSVal SymVal = 2736 svalBuilder.getConjuredSymbolVal(NULL, Ex, 2737 Builder->getCurrentBlockCount()); 2738 Result = SymVal; 2739 2740 // If the value is a location, ++/-- should always preserve 2741 // non-nullness. Check if the original value was non-null, and if so 2742 // propagate that constraint. 2743 if (Loc::isLocType(U->getType())) { 2744 DefinedOrUnknownSVal Constraint = 2745 svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType())); 2746 2747 if (!state->assume(Constraint, true)) { 2748 // It isn't feasible for the original value to be null. 2749 // Propagate this constraint. 2750 Constraint = svalBuilder.evalEQ(state, SymVal, 2751 svalBuilder.makeZeroVal(U->getType())); 2752 2753 2754 state = state->assume(Constraint, false); 2755 assert(state); 2756 } 2757 } 2758 } 2759 2760 // Since the lvalue-to-rvalue conversion is explicit in the AST, 2761 // we bind an l-value if the operator is prefix and an lvalue (in C++). 2762 if (U->isLValue()) 2763 state = state->BindExpr(U, loc); 2764 else 2765 state = state->BindExpr(U, U->isPostfix() ? V2 : Result); 2766 2767 // Perform the store. 2768 evalStore(Dst, NULL, U, *I2, state, loc, Result); 2769 } 2770 } 2771} 2772 2773void ExprEngine::VisitAsmStmt(const AsmStmt* A, ExplodedNode* Pred, 2774 ExplodedNodeSet& Dst) { 2775 VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst); 2776} 2777 2778void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt* A, 2779 AsmStmt::const_outputs_iterator I, 2780 AsmStmt::const_outputs_iterator E, 2781 ExplodedNode* Pred, ExplodedNodeSet& Dst) { 2782 if (I == E) { 2783 VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst); 2784 return; 2785 } 2786 2787 ExplodedNodeSet Tmp; 2788 Visit(*I, Pred, Tmp); 2789 ++I; 2790 2791 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI) 2792 VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst); 2793} 2794 2795void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt* A, 2796 AsmStmt::const_inputs_iterator I, 2797 AsmStmt::const_inputs_iterator E, 2798 ExplodedNode* Pred, 2799 ExplodedNodeSet& Dst) { 2800 if (I == E) { 2801 2802 // We have processed both the inputs and the outputs. All of the outputs 2803 // should evaluate to Locs. Nuke all of their values. 2804 2805 // FIXME: Some day in the future it would be nice to allow a "plug-in" 2806 // which interprets the inline asm and stores proper results in the 2807 // outputs. 2808 2809 const GRState* state = GetState(Pred); 2810 2811 for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(), 2812 OE = A->end_outputs(); OI != OE; ++OI) { 2813 2814 SVal X = state->getSVal(*OI); 2815 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef. 2816 2817 if (isa<Loc>(X)) 2818 state = state->bindLoc(cast<Loc>(X), UnknownVal()); 2819 } 2820 2821 MakeNode(Dst, A, Pred, state); 2822 return; 2823 } 2824 2825 ExplodedNodeSet Tmp; 2826 Visit(*I, Pred, Tmp); 2827 2828 ++I; 2829 2830 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI) 2831 VisitAsmStmtHelperInputs(A, I, E, *NI, Dst); 2832} 2833 2834void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 2835 ExplodedNodeSet &Dst) { 2836 ExplodedNodeSet Src; 2837 if (const Expr *RetE = RS->getRetValue()) { 2838 // Record the returned expression in the state. It will be used in 2839 // processCallExit to bind the return value to the call expr. 2840 { 2841 static int tag = 0; 2842 const GRState *state = GetState(Pred); 2843 state = state->set<ReturnExpr>(RetE); 2844 Pred = Builder->generateNode(RetE, state, Pred, &tag); 2845 } 2846 // We may get a NULL Pred because we generated a cached node. 2847 if (Pred) 2848 Visit(RetE, Pred, Src); 2849 } 2850 else { 2851 Src.Add(Pred); 2852 } 2853 2854 ExplodedNodeSet CheckedSet; 2855 getCheckerManager().runCheckersForPreStmt(CheckedSet, Src, RS, *this); 2856 2857 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 2858 I != E; ++I) { 2859 2860 assert(Builder && "StmtNodeBuilder must be defined."); 2861 2862 Pred = *I; 2863 unsigned size = Dst.size(); 2864 2865 SaveAndRestore<bool> OldSink(Builder->BuildSinks); 2866 SaveOr OldHasGen(Builder->hasGeneratedNode); 2867 2868 getTF().evalReturn(Dst, *this, *Builder, RS, Pred); 2869 2870 // Handle the case where no nodes where generated. 2871 if (!Builder->BuildSinks && Dst.size() == size && 2872 !Builder->hasGeneratedNode) 2873 MakeNode(Dst, RS, Pred, GetState(Pred)); 2874 } 2875} 2876 2877//===----------------------------------------------------------------------===// 2878// Transfer functions: Binary operators. 2879//===----------------------------------------------------------------------===// 2880 2881void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, 2882 ExplodedNode* Pred, 2883 ExplodedNodeSet& Dst) { 2884 ExplodedNodeSet Tmp1; 2885 Expr* LHS = B->getLHS()->IgnoreParens(); 2886 Expr* RHS = B->getRHS()->IgnoreParens(); 2887 2888 Visit(LHS, Pred, Tmp1); 2889 ExplodedNodeSet Tmp3; 2890 2891 for (ExplodedNodeSet::iterator I1=Tmp1.begin(), E1=Tmp1.end(); I1!=E1; ++I1) { 2892 SVal LeftV = GetState(*I1)->getSVal(LHS); 2893 ExplodedNodeSet Tmp2; 2894 Visit(RHS, *I1, Tmp2); 2895 2896 ExplodedNodeSet CheckedSet; 2897 getCheckerManager().runCheckersForPreStmt(CheckedSet, Tmp2, B, *this); 2898 2899 // With both the LHS and RHS evaluated, process the operation itself. 2900 2901 for (ExplodedNodeSet::iterator I2=CheckedSet.begin(), E2=CheckedSet.end(); 2902 I2 != E2; ++I2) { 2903 2904 const GRState *state = GetState(*I2); 2905 SVal RightV = state->getSVal(RHS); 2906 2907 BinaryOperator::Opcode Op = B->getOpcode(); 2908 2909 if (Op == BO_Assign) { 2910 // EXPERIMENTAL: "Conjured" symbols. 2911 // FIXME: Handle structs. 2912 if (RightV.isUnknown() ||!getConstraintManager().canReasonAbout(RightV)) 2913 { 2914 unsigned Count = Builder->getCurrentBlockCount(); 2915 RightV = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), Count); 2916 } 2917 2918 SVal ExprVal = B->isLValue() ? LeftV : RightV; 2919 2920 // Simulate the effects of a "store": bind the value of the RHS 2921 // to the L-Value represented by the LHS. 2922 evalStore(Tmp3, B, LHS, *I2, state->BindExpr(B, ExprVal), LeftV,RightV); 2923 continue; 2924 } 2925 2926 if (!B->isAssignmentOp()) { 2927 // Process non-assignments except commas or short-circuited 2928 // logical expressions (LAnd and LOr). 2929 SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType()); 2930 2931 if (Result.isUnknown()) { 2932 MakeNode(Tmp3, B, *I2, state); 2933 continue; 2934 } 2935 2936 state = state->BindExpr(B, Result); 2937 2938 MakeNode(Tmp3, B, *I2, state); 2939 continue; 2940 } 2941 2942 assert (B->isCompoundAssignmentOp()); 2943 2944 switch (Op) { 2945 default: 2946 assert(0 && "Invalid opcode for compound assignment."); 2947 case BO_MulAssign: Op = BO_Mul; break; 2948 case BO_DivAssign: Op = BO_Div; break; 2949 case BO_RemAssign: Op = BO_Rem; break; 2950 case BO_AddAssign: Op = BO_Add; break; 2951 case BO_SubAssign: Op = BO_Sub; break; 2952 case BO_ShlAssign: Op = BO_Shl; break; 2953 case BO_ShrAssign: Op = BO_Shr; break; 2954 case BO_AndAssign: Op = BO_And; break; 2955 case BO_XorAssign: Op = BO_Xor; break; 2956 case BO_OrAssign: Op = BO_Or; break; 2957 } 2958 2959 // Perform a load (the LHS). This performs the checks for 2960 // null dereferences, and so on. 2961 ExplodedNodeSet Tmp4; 2962 SVal location = state->getSVal(LHS); 2963 evalLoad(Tmp4, LHS, *I2, state, location); 2964 2965 for (ExplodedNodeSet::iterator I4=Tmp4.begin(), E4=Tmp4.end(); I4!=E4; 2966 ++I4) { 2967 state = GetState(*I4); 2968 SVal V = state->getSVal(LHS); 2969 2970 // Get the computation type. 2971 QualType CTy = 2972 cast<CompoundAssignOperator>(B)->getComputationResultType(); 2973 CTy = getContext().getCanonicalType(CTy); 2974 2975 QualType CLHSTy = 2976 cast<CompoundAssignOperator>(B)->getComputationLHSType(); 2977 CLHSTy = getContext().getCanonicalType(CLHSTy); 2978 2979 QualType LTy = getContext().getCanonicalType(LHS->getType()); 2980 2981 // Promote LHS. 2982 V = svalBuilder.evalCast(V, CLHSTy, LTy); 2983 2984 // Compute the result of the operation. 2985 SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy), 2986 B->getType(), CTy); 2987 2988 // EXPERIMENTAL: "Conjured" symbols. 2989 // FIXME: Handle structs. 2990 2991 SVal LHSVal; 2992 2993 if (Result.isUnknown() || 2994 !getConstraintManager().canReasonAbout(Result)) { 2995 2996 unsigned Count = Builder->getCurrentBlockCount(); 2997 2998 // The symbolic value is actually for the type of the left-hand side 2999 // expression, not the computation type, as this is the value the 3000 // LValue on the LHS will bind to. 3001 LHSVal = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LTy, Count); 3002 3003 // However, we need to convert the symbol to the computation type. 3004 Result = svalBuilder.evalCast(LHSVal, CTy, LTy); 3005 } 3006 else { 3007 // The left-hand side may bind to a different value then the 3008 // computation type. 3009 LHSVal = svalBuilder.evalCast(Result, LTy, CTy); 3010 } 3011 3012 // In C++, assignment and compound assignment operators return an 3013 // lvalue. 3014 if (B->isLValue()) 3015 state = state->BindExpr(B, location); 3016 else 3017 state = state->BindExpr(B, Result); 3018 3019 evalStore(Tmp3, B, LHS, *I4, state, location, LHSVal); 3020 } 3021 } 3022 } 3023 3024 getCheckerManager().runCheckersForPostStmt(Dst, Tmp3, B, *this); 3025} 3026 3027//===----------------------------------------------------------------------===// 3028// Visualization. 3029//===----------------------------------------------------------------------===// 3030 3031#ifndef NDEBUG 3032static ExprEngine* GraphPrintCheckerState; 3033static SourceManager* GraphPrintSourceManager; 3034 3035namespace llvm { 3036template<> 3037struct DOTGraphTraits<ExplodedNode*> : 3038 public DefaultDOTGraphTraits { 3039 3040 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 3041 3042 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not 3043 // work. 3044 static std::string getNodeAttributes(const ExplodedNode* N, void*) { 3045 3046#if 0 3047 // FIXME: Replace with a general scheme to tell if the node is 3048 // an error node. 3049 if (GraphPrintCheckerState->isImplicitNullDeref(N) || 3050 GraphPrintCheckerState->isExplicitNullDeref(N) || 3051 GraphPrintCheckerState->isUndefDeref(N) || 3052 GraphPrintCheckerState->isUndefStore(N) || 3053 GraphPrintCheckerState->isUndefControlFlow(N) || 3054 GraphPrintCheckerState->isUndefResult(N) || 3055 GraphPrintCheckerState->isBadCall(N) || 3056 GraphPrintCheckerState->isUndefArg(N)) 3057 return "color=\"red\",style=\"filled\""; 3058 3059 if (GraphPrintCheckerState->isNoReturnCall(N)) 3060 return "color=\"blue\",style=\"filled\""; 3061#endif 3062 return ""; 3063 } 3064 3065 static std::string getNodeLabel(const ExplodedNode* N, void*){ 3066 3067 std::string sbuf; 3068 llvm::raw_string_ostream Out(sbuf); 3069 3070 // Program Location. 3071 ProgramPoint Loc = N->getLocation(); 3072 3073 switch (Loc.getKind()) { 3074 case ProgramPoint::BlockEntranceKind: 3075 Out << "Block Entrance: B" 3076 << cast<BlockEntrance>(Loc).getBlock()->getBlockID(); 3077 break; 3078 3079 case ProgramPoint::BlockExitKind: 3080 assert (false); 3081 break; 3082 3083 case ProgramPoint::CallEnterKind: 3084 Out << "CallEnter"; 3085 break; 3086 3087 case ProgramPoint::CallExitKind: 3088 Out << "CallExit"; 3089 break; 3090 3091 default: { 3092 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) { 3093 const Stmt* S = L->getStmt(); 3094 SourceLocation SLoc = S->getLocStart(); 3095 3096 Out << S->getStmtClassName() << ' ' << (void*) S << ' '; 3097 LangOptions LO; // FIXME. 3098 S->printPretty(Out, 0, PrintingPolicy(LO)); 3099 3100 if (SLoc.isFileID()) { 3101 Out << "\\lline=" 3102 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc) 3103 << " col=" 3104 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc) 3105 << "\\l"; 3106 } 3107 3108 if (isa<PreStmt>(Loc)) 3109 Out << "\\lPreStmt\\l;"; 3110 else if (isa<PostLoad>(Loc)) 3111 Out << "\\lPostLoad\\l;"; 3112 else if (isa<PostStore>(Loc)) 3113 Out << "\\lPostStore\\l"; 3114 else if (isa<PostLValue>(Loc)) 3115 Out << "\\lPostLValue\\l"; 3116 3117#if 0 3118 // FIXME: Replace with a general scheme to determine 3119 // the name of the check. 3120 if (GraphPrintCheckerState->isImplicitNullDeref(N)) 3121 Out << "\\|Implicit-Null Dereference.\\l"; 3122 else if (GraphPrintCheckerState->isExplicitNullDeref(N)) 3123 Out << "\\|Explicit-Null Dereference.\\l"; 3124 else if (GraphPrintCheckerState->isUndefDeref(N)) 3125 Out << "\\|Dereference of undefialied value.\\l"; 3126 else if (GraphPrintCheckerState->isUndefStore(N)) 3127 Out << "\\|Store to Undefined Loc."; 3128 else if (GraphPrintCheckerState->isUndefResult(N)) 3129 Out << "\\|Result of operation is undefined."; 3130 else if (GraphPrintCheckerState->isNoReturnCall(N)) 3131 Out << "\\|Call to function marked \"noreturn\"."; 3132 else if (GraphPrintCheckerState->isBadCall(N)) 3133 Out << "\\|Call to NULL/Undefined."; 3134 else if (GraphPrintCheckerState->isUndefArg(N)) 3135 Out << "\\|Argument in call is undefined"; 3136#endif 3137 3138 break; 3139 } 3140 3141 const BlockEdge& E = cast<BlockEdge>(Loc); 3142 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B" 3143 << E.getDst()->getBlockID() << ')'; 3144 3145 if (const Stmt* T = E.getSrc()->getTerminator()) { 3146 3147 SourceLocation SLoc = T->getLocStart(); 3148 3149 Out << "\\|Terminator: "; 3150 LangOptions LO; // FIXME. 3151 E.getSrc()->printTerminator(Out, LO); 3152 3153 if (SLoc.isFileID()) { 3154 Out << "\\lline=" 3155 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc) 3156 << " col=" 3157 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc); 3158 } 3159 3160 if (isa<SwitchStmt>(T)) { 3161 const Stmt* Label = E.getDst()->getLabel(); 3162 3163 if (Label) { 3164 if (const CaseStmt* C = dyn_cast<CaseStmt>(Label)) { 3165 Out << "\\lcase "; 3166 LangOptions LO; // FIXME. 3167 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO)); 3168 3169 if (const Stmt* RHS = C->getRHS()) { 3170 Out << " .. "; 3171 RHS->printPretty(Out, 0, PrintingPolicy(LO)); 3172 } 3173 3174 Out << ":"; 3175 } 3176 else { 3177 assert (isa<DefaultStmt>(Label)); 3178 Out << "\\ldefault:"; 3179 } 3180 } 3181 else 3182 Out << "\\l(implicit) default:"; 3183 } 3184 else if (isa<IndirectGotoStmt>(T)) { 3185 // FIXME 3186 } 3187 else { 3188 Out << "\\lCondition: "; 3189 if (*E.getSrc()->succ_begin() == E.getDst()) 3190 Out << "true"; 3191 else 3192 Out << "false"; 3193 } 3194 3195 Out << "\\l"; 3196 } 3197 3198#if 0 3199 // FIXME: Replace with a general scheme to determine 3200 // the name of the check. 3201 if (GraphPrintCheckerState->isUndefControlFlow(N)) { 3202 Out << "\\|Control-flow based on\\lUndefined value.\\l"; 3203 } 3204#endif 3205 } 3206 } 3207 3208 const GRState *state = N->getState(); 3209 Out << "\\|StateID: " << (void*) state 3210 << " NodeID: " << (void*) N << "\\|"; 3211 state->printDOT(Out, *N->getLocationContext()->getCFG()); 3212 Out << "\\l"; 3213 return Out.str(); 3214 } 3215}; 3216} // end llvm namespace 3217#endif 3218 3219#ifndef NDEBUG 3220template <typename ITERATOR> 3221ExplodedNode* GetGraphNode(ITERATOR I) { return *I; } 3222 3223template <> ExplodedNode* 3224GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator> 3225 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) { 3226 return I->first; 3227} 3228#endif 3229 3230void ExprEngine::ViewGraph(bool trim) { 3231#ifndef NDEBUG 3232 if (trim) { 3233 std::vector<ExplodedNode*> Src; 3234 3235 // Flush any outstanding reports to make sure we cover all the nodes. 3236 // This does not cause them to get displayed. 3237 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) 3238 const_cast<BugType*>(*I)->FlushReports(BR); 3239 3240 // Iterate through the reports and get their nodes. 3241 for (BugReporter::EQClasses_iterator 3242 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 3243 BugReportEquivClass& EQ = *EI; 3244 const BugReport &R = **EQ.begin(); 3245 ExplodedNode *N = const_cast<ExplodedNode*>(R.getErrorNode()); 3246 if (N) Src.push_back(N); 3247 } 3248 3249 ViewGraph(&Src[0], &Src[0]+Src.size()); 3250 } 3251 else { 3252 GraphPrintCheckerState = this; 3253 GraphPrintSourceManager = &getContext().getSourceManager(); 3254 3255 llvm::ViewGraph(*G.roots_begin(), "ExprEngine"); 3256 3257 GraphPrintCheckerState = NULL; 3258 GraphPrintSourceManager = NULL; 3259 } 3260#endif 3261} 3262 3263void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) { 3264#ifndef NDEBUG 3265 GraphPrintCheckerState = this; 3266 GraphPrintSourceManager = &getContext().getSourceManager(); 3267 3268 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first); 3269 3270 if (!TrimmedG.get()) 3271 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 3272 else 3273 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine"); 3274 3275 GraphPrintCheckerState = NULL; 3276 GraphPrintSourceManager = NULL; 3277#endif 3278} 3279