ExprEngine.cpp revision ae2dc146c936244f3cd72efa24085259452a861c
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, getStoreManager()); 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, 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 1339 ExplodedNodeSet checkerPreStmt; 1340 getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this); 1341 1342 for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(), 1343 ei = checkerPreStmt.end(); it != ei; ++it) { 1344 const GRState* state = GetState(*it); 1345 SVal V = state->getLValue(A->getType(), state->getSVal(Idx), 1346 state->getSVal(Base)); 1347 assert(A->isLValue()); 1348 MakeNode(Dst, A, *it, state->BindExpr(A, V), ProgramPoint::PostLValueKind); 1349 } 1350} 1351 1352/// VisitMemberExpr - Transfer function for member expressions. 1353void ExprEngine::VisitMemberExpr(const MemberExpr* M, ExplodedNode *Pred, 1354 ExplodedNodeSet& Dst) { 1355 1356 FieldDecl *field = dyn_cast<FieldDecl>(M->getMemberDecl()); 1357 if (!field) // FIXME: skipping member expressions for non-fields 1358 return; 1359 1360 Expr *baseExpr = M->getBase()->IgnoreParens(); 1361 const GRState* state = GetState(Pred); 1362 SVal baseExprVal = state->getSVal(baseExpr); 1363 if (isa<nonloc::LazyCompoundVal>(baseExprVal) || 1364 isa<nonloc::CompoundVal>(baseExprVal) || 1365 // FIXME: This can originate by conjuring a symbol for an unknown 1366 // temporary struct object, see test/Analysis/fields.c: 1367 // (p = getit()).x 1368 isa<nonloc::SymbolVal>(baseExprVal)) { 1369 MakeNode(Dst, M, Pred, state->BindExpr(M, UnknownVal())); 1370 return; 1371 } 1372 1373 // FIXME: Should we insert some assumption logic in here to determine 1374 // if "Base" is a valid piece of memory? Before we put this assumption 1375 // later when using FieldOffset lvals (which we no longer have). 1376 1377 // For all other cases, compute an lvalue. 1378 SVal L = state->getLValue(field, baseExprVal); 1379 if (M->isLValue()) 1380 MakeNode(Dst, M, Pred, state->BindExpr(M, L), ProgramPoint::PostLValueKind); 1381 else 1382 evalLoad(Dst, M, Pred, state, L); 1383} 1384 1385/// evalBind - Handle the semantics of binding a value to a specific location. 1386/// This method is used by evalStore and (soon) VisitDeclStmt, and others. 1387void ExprEngine::evalBind(ExplodedNodeSet& Dst, const Stmt* StoreE, 1388 ExplodedNode* Pred, const GRState* state, 1389 SVal location, SVal Val, bool atDeclInit) { 1390 1391 1392 // Do a previsit of the bind. 1393 ExplodedNodeSet CheckedSet, Src; 1394 Src.Add(Pred); 1395 getCheckerManager().runCheckersForBind(CheckedSet, Src, location, Val, StoreE, 1396 *this); 1397 1398 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 1399 I!=E; ++I) { 1400 1401 if (Pred != *I) 1402 state = GetState(*I); 1403 1404 const GRState* newState = 0; 1405 1406 if (atDeclInit) { 1407 const VarRegion *VR = 1408 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion()); 1409 1410 newState = state->bindDecl(VR, Val); 1411 } 1412 else { 1413 if (location.isUnknown()) { 1414 // We know that the new state will be the same as the old state since 1415 // the location of the binding is "unknown". Consequently, there 1416 // is no reason to just create a new node. 1417 newState = state; 1418 } 1419 else { 1420 // We are binding to a value other than 'unknown'. Perform the binding 1421 // using the StoreManager. 1422 newState = state->bindLoc(cast<Loc>(location), Val); 1423 } 1424 } 1425 1426 // The next thing to do is check if the TransferFuncs object wants to 1427 // update the state based on the new binding. If the GRTransferFunc object 1428 // doesn't do anything, just auto-propagate the current state. 1429 1430 // NOTE: We use 'AssignE' for the location of the PostStore if 'AssignE' 1431 // is non-NULL. Checkers typically care about 1432 1433 StmtNodeBuilderRef BuilderRef(Dst, *Builder, *this, *I, newState, StoreE, 1434 true); 1435 1436 getTF().evalBind(BuilderRef, location, Val); 1437 } 1438} 1439 1440/// evalStore - Handle the semantics of a store via an assignment. 1441/// @param Dst The node set to store generated state nodes 1442/// @param AssignE The assignment expression if the store happens in an 1443/// assignment. 1444/// @param LocatioinE The location expression that is stored to. 1445/// @param state The current simulation state 1446/// @param location The location to store the value 1447/// @param Val The value to be stored 1448void ExprEngine::evalStore(ExplodedNodeSet& Dst, const Expr *AssignE, 1449 const Expr* LocationE, 1450 ExplodedNode* Pred, 1451 const GRState* state, SVal location, SVal Val, 1452 const void *tag) { 1453 1454 assert(Builder && "StmtNodeBuilder must be defined."); 1455 1456 // Proceed with the store. We use AssignE as the anchor for the PostStore 1457 // ProgramPoint if it is non-NULL, and LocationE otherwise. 1458 const Expr *StoreE = AssignE ? AssignE : LocationE; 1459 1460 if (isa<loc::ObjCPropRef>(location)) { 1461 loc::ObjCPropRef prop = cast<loc::ObjCPropRef>(location); 1462 ExplodedNodeSet src = Pred; 1463 return VisitObjCMessage(ObjCPropertySetter(prop.getPropRefExpr(), 1464 StoreE, Val), src, Dst); 1465 } 1466 1467 // Evaluate the location (checks for bad dereferences). 1468 ExplodedNodeSet Tmp; 1469 evalLocation(Tmp, LocationE, Pred, state, location, tag, false); 1470 1471 if (Tmp.empty()) 1472 return; 1473 1474 if (location.isUndef()) 1475 return; 1476 1477 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind, 1478 ProgramPoint::PostStoreKind); 1479 1480 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 1481 evalBind(Dst, StoreE, *NI, GetState(*NI), location, Val); 1482} 1483 1484void ExprEngine::evalLoad(ExplodedNodeSet& Dst, const Expr *Ex, 1485 ExplodedNode* Pred, 1486 const GRState* state, SVal location, 1487 const void *tag, QualType LoadTy) { 1488 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc."); 1489 1490 if (isa<loc::ObjCPropRef>(location)) { 1491 loc::ObjCPropRef prop = cast<loc::ObjCPropRef>(location); 1492 ExplodedNodeSet src = Pred; 1493 return VisitObjCMessage(ObjCPropertyGetter(prop.getPropRefExpr(), Ex), 1494 src, Dst); 1495 } 1496 1497 // Are we loading from a region? This actually results in two loads; one 1498 // to fetch the address of the referenced value and one to fetch the 1499 // referenced value. 1500 if (const TypedRegion *TR = 1501 dyn_cast_or_null<TypedRegion>(location.getAsRegion())) { 1502 1503 QualType ValTy = TR->getValueType(); 1504 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) { 1505 static int loadReferenceTag = 0; 1506 ExplodedNodeSet Tmp; 1507 evalLoadCommon(Tmp, Ex, Pred, state, location, &loadReferenceTag, 1508 getContext().getPointerType(RT->getPointeeType())); 1509 1510 // Perform the load from the referenced value. 1511 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) { 1512 state = GetState(*I); 1513 location = state->getSVal(Ex); 1514 evalLoadCommon(Dst, Ex, *I, state, location, tag, LoadTy); 1515 } 1516 return; 1517 } 1518 } 1519 1520 evalLoadCommon(Dst, Ex, Pred, state, location, tag, LoadTy); 1521} 1522 1523void ExprEngine::evalLoadCommon(ExplodedNodeSet& Dst, const Expr *Ex, 1524 ExplodedNode* Pred, 1525 const GRState* state, SVal location, 1526 const void *tag, QualType LoadTy) { 1527 1528 // Evaluate the location (checks for bad dereferences). 1529 ExplodedNodeSet Tmp; 1530 evalLocation(Tmp, Ex, Pred, state, location, tag, true); 1531 1532 if (Tmp.empty()) 1533 return; 1534 1535 if (location.isUndef()) 1536 return; 1537 1538 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind); 1539 1540 // Proceed with the load. 1541 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 1542 state = GetState(*NI); 1543 1544 if (location.isUnknown()) { 1545 // This is important. We must nuke the old binding. 1546 MakeNode(Dst, Ex, *NI, state->BindExpr(Ex, UnknownVal()), 1547 ProgramPoint::PostLoadKind, tag); 1548 } 1549 else { 1550 if (LoadTy.isNull()) 1551 LoadTy = Ex->getType(); 1552 SVal V = state->getSVal(cast<Loc>(location), LoadTy); 1553 MakeNode(Dst, Ex, *NI, state->bindExprAndLocation(Ex, location, V), 1554 ProgramPoint::PostLoadKind, tag); 1555 } 1556 } 1557} 1558 1559void ExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *S, 1560 ExplodedNode* Pred, 1561 const GRState* state, SVal location, 1562 const void *tag, bool isLoad) { 1563 // Early checks for performance reason. 1564 if (location.isUnknown()) { 1565 Dst.Add(Pred); 1566 return; 1567 } 1568 1569 ExplodedNodeSet Src; 1570 if (Builder->GetState(Pred) == state) { 1571 Src.Add(Pred); 1572 } else { 1573 // Associate this new state with an ExplodedNode. 1574 // FIXME: If I pass null tag, the graph is incorrect, e.g for 1575 // int *p; 1576 // p = 0; 1577 // *p = 0xDEADBEEF; 1578 // "p = 0" is not noted as "Null pointer value stored to 'p'" but 1579 // instead "int *p" is noted as 1580 // "Variable 'p' initialized to a null pointer value" 1581 ExplodedNode *N = Builder->generateNode(S, state, Pred, this); 1582 Src.Add(N ? N : Pred); 1583 } 1584 getCheckerManager().runCheckersForLocation(Dst, Src, location, isLoad, S, 1585 *this); 1586} 1587 1588bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, 1589 ExplodedNode *Pred) { 1590 return false; 1591 1592 // Inlining isn't correct right now because we: 1593 // (a) don't generate CallExit nodes. 1594 // (b) we need a way to postpone doing post-visits of CallExprs until 1595 // the CallExit. This means we need CallExits for the non-inline 1596 // cases as well. 1597 1598#if 0 1599 const GRState *state = GetState(Pred); 1600 const Expr *Callee = CE->getCallee(); 1601 SVal L = state->getSVal(Callee); 1602 1603 const FunctionDecl *FD = L.getAsFunctionDecl(); 1604 if (!FD) 1605 return false; 1606 1607 // Specially handle CXXMethods. 1608 const CXXMethodDecl *methodDecl = 0; 1609 1610 switch (CE->getStmtClass()) { 1611 default: break; 1612 case Stmt::CXXOperatorCallExprClass: { 1613 const CXXOperatorCallExpr *opCall = cast<CXXOperatorCallExpr>(CE); 1614 methodDecl = 1615 dyn_cast_or_null<CXXMethodDecl>(opCall->getCalleeDecl()); 1616 break; 1617 } 1618 case Stmt::CXXMemberCallExprClass: { 1619 const CXXMemberCallExpr *memberCall = cast<CXXMemberCallExpr>(CE); 1620 const MemberExpr *memberExpr = 1621 cast<MemberExpr>(memberCall->getCallee()->IgnoreParens()); 1622 methodDecl = cast<CXXMethodDecl>(memberExpr->getMemberDecl()); 1623 break; 1624 } 1625 } 1626 1627 1628 1629 1630 // Check if the function definition is in the same translation unit. 1631 if (FD->hasBody(FD)) { 1632 const StackFrameContext *stackFrame = 1633 AMgr.getStackFrame(AMgr.getAnalysisContext(FD), 1634 Pred->getLocationContext(), 1635 CE, Builder->getBlock(), Builder->getIndex()); 1636 // Now we have the definition of the callee, create a CallEnter node. 1637 CallEnter Loc(CE, stackFrame, Pred->getLocationContext()); 1638 1639 ExplodedNode *N = Builder->generateNode(Loc, state, Pred); 1640 Dst.Add(N); 1641 return true; 1642 } 1643 1644 // Check if we can find the function definition in other translation units. 1645 if (AMgr.hasIndexer()) { 1646 AnalysisContext *C = AMgr.getAnalysisContextInAnotherTU(FD); 1647 if (C == 0) 1648 return false; 1649 const StackFrameContext *stackFrame = 1650 AMgr.getStackFrame(C, Pred->getLocationContext(), 1651 CE, Builder->getBlock(), Builder->getIndex()); 1652 CallEnter Loc(CE, stackFrame, Pred->getLocationContext()); 1653 ExplodedNode *N = Builder->generateNode(Loc, state, Pred); 1654 Dst.Add(N); 1655 return true; 1656 } 1657 1658 // Generate the CallExit node. 1659 1660 return false; 1661#endif 1662} 1663 1664void ExprEngine::VisitCallExpr(const CallExpr* CE, ExplodedNode* Pred, 1665 ExplodedNodeSet& dst) { 1666 1667 // Determine the type of function we're calling (if available). 1668 const FunctionProtoType *Proto = NULL; 1669 QualType FnType = CE->getCallee()->IgnoreParens()->getType(); 1670 if (const PointerType *FnTypePtr = FnType->getAs<PointerType>()) 1671 Proto = FnTypePtr->getPointeeType()->getAs<FunctionProtoType>(); 1672 1673 // Perform the previsit of the CallExpr. 1674 ExplodedNodeSet dstPreVisit; 1675 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this); 1676 1677 // Now evaluate the call itself. 1678 class DefaultEval : public GraphExpander { 1679 ExprEngine &Eng; 1680 const CallExpr *CE; 1681 public: 1682 1683 DefaultEval(ExprEngine &eng, const CallExpr *ce) 1684 : Eng(eng), CE(ce) {} 1685 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) { 1686 // Should we inline the call? 1687 if (Eng.getAnalysisManager().shouldInlineCall() && 1688 Eng.InlineCall(Dst, CE, Pred)) { 1689 return; 1690 } 1691 1692 StmtNodeBuilder &Builder = Eng.getBuilder(); 1693 assert(&Builder && "StmtNodeBuilder must be defined."); 1694 1695 // Dispatch to the plug-in transfer function. 1696 unsigned oldSize = Dst.size(); 1697 SaveOr OldHasGen(Builder.hasGeneratedNode); 1698 1699 // Dispatch to transfer function logic to handle the call itself. 1700 const Expr* Callee = CE->getCallee()->IgnoreParens(); 1701 const GRState* state = Eng.GetState(Pred); 1702 SVal L = state->getSVal(Callee); 1703 Eng.getTF().evalCall(Dst, Eng, Builder, CE, L, Pred); 1704 1705 // Handle the case where no nodes where generated. Auto-generate that 1706 // contains the updated state if we aren't generating sinks. 1707 if (!Builder.BuildSinks && Dst.size() == oldSize && 1708 !Builder.hasGeneratedNode) 1709 Eng.MakeNode(Dst, CE, Pred, state); 1710 } 1711 }; 1712 1713 // Finally, evaluate the function call. We try each of the checkers 1714 // to see if the can evaluate the function call. 1715 ExplodedNodeSet dstCallEvaluated; 1716 DefaultEval defEval(*this, CE); 1717 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, 1718 dstPreVisit, 1719 CE, *this, &defEval); 1720 1721 // Finally, perform the post-condition check of the CallExpr and store 1722 // the created nodes in 'Dst'. 1723 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 1724 *this); 1725} 1726 1727//===----------------------------------------------------------------------===// 1728// Transfer function: Objective-C dot-syntax to access a property. 1729//===----------------------------------------------------------------------===// 1730 1731void ExprEngine::VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *Ex, 1732 ExplodedNode *Pred, 1733 ExplodedNodeSet &Dst) { 1734 MakeNode(Dst, Ex, Pred, GetState(Pred)->BindExpr(Ex, loc::ObjCPropRef(Ex))); 1735} 1736 1737//===----------------------------------------------------------------------===// 1738// Transfer function: Objective-C ivar references. 1739//===----------------------------------------------------------------------===// 1740 1741static std::pair<const void*,const void*> EagerlyAssumeTag 1742 = std::pair<const void*,const void*>(&EagerlyAssumeTag,static_cast<void*>(0)); 1743 1744void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, 1745 const Expr *Ex) { 1746 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) { 1747 ExplodedNode *Pred = *I; 1748 1749 // Test if the previous node was as the same expression. This can happen 1750 // when the expression fails to evaluate to anything meaningful and 1751 // (as an optimization) we don't generate a node. 1752 ProgramPoint P = Pred->getLocation(); 1753 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) { 1754 Dst.Add(Pred); 1755 continue; 1756 } 1757 1758 const GRState* state = GetState(Pred); 1759 SVal V = state->getSVal(Ex); 1760 if (nonloc::SymExprVal *SEV = dyn_cast<nonloc::SymExprVal>(&V)) { 1761 // First assume that the condition is true. 1762 if (const GRState *stateTrue = state->assume(*SEV, true)) { 1763 stateTrue = stateTrue->BindExpr(Ex, 1764 svalBuilder.makeIntVal(1U, Ex->getType())); 1765 Dst.Add(Builder->generateNode(PostStmtCustom(Ex, 1766 &EagerlyAssumeTag, Pred->getLocationContext()), 1767 stateTrue, Pred)); 1768 } 1769 1770 // Next, assume that the condition is false. 1771 if (const GRState *stateFalse = state->assume(*SEV, false)) { 1772 stateFalse = stateFalse->BindExpr(Ex, 1773 svalBuilder.makeIntVal(0U, Ex->getType())); 1774 Dst.Add(Builder->generateNode(PostStmtCustom(Ex, &EagerlyAssumeTag, 1775 Pred->getLocationContext()), 1776 stateFalse, Pred)); 1777 } 1778 } 1779 else 1780 Dst.Add(Pred); 1781 } 1782} 1783 1784//===----------------------------------------------------------------------===// 1785// Transfer function: Objective-C @synchronized. 1786//===----------------------------------------------------------------------===// 1787 1788void ExprEngine::VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S, 1789 ExplodedNode *Pred, 1790 ExplodedNodeSet &Dst) { 1791 1792 // The mutex expression is a CFGElement, so we don't need to explicitly 1793 // visit it since it will already be processed. 1794 1795 // Pre-visit the ObjCAtSynchronizedStmt. 1796 ExplodedNodeSet Tmp; 1797 Tmp.Add(Pred); 1798 getCheckerManager().runCheckersForPreStmt(Dst, Tmp, S, *this); 1799} 1800 1801//===----------------------------------------------------------------------===// 1802// Transfer function: Objective-C ivar references. 1803//===----------------------------------------------------------------------===// 1804 1805void ExprEngine::VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr* Ex, 1806 ExplodedNode* Pred, 1807 ExplodedNodeSet& Dst) { 1808 1809 // Visit the base expression, which is needed for computing the lvalue 1810 // of the ivar. 1811 ExplodedNodeSet dstBase; 1812 const Expr *baseExpr = Ex->getBase(); 1813 Visit(baseExpr, Pred, dstBase); 1814 1815 ExplodedNodeSet dstIvar; 1816 1817 // Using the base, compute the lvalue of the instance variable. 1818 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end(); 1819 I!=E; ++I) { 1820 ExplodedNode *nodeBase = *I; 1821 const GRState *state = GetState(nodeBase); 1822 SVal baseVal = state->getSVal(baseExpr); 1823 SVal location = state->getLValue(Ex->getDecl(), baseVal); 1824 MakeNode(dstIvar, Ex, *I, state->BindExpr(Ex, location)); 1825 } 1826 1827 // Perform the post-condition check of the ObjCIvarRefExpr and store 1828 // the created nodes in 'Dst'. 1829 getCheckerManager().runCheckersForPostStmt(Dst, dstIvar, Ex, *this); 1830} 1831 1832//===----------------------------------------------------------------------===// 1833// Transfer function: Objective-C fast enumeration 'for' statements. 1834//===----------------------------------------------------------------------===// 1835 1836void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt* S, 1837 ExplodedNode* Pred, ExplodedNodeSet& Dst) { 1838 1839 // ObjCForCollectionStmts are processed in two places. This method 1840 // handles the case where an ObjCForCollectionStmt* occurs as one of the 1841 // statements within a basic block. This transfer function does two things: 1842 // 1843 // (1) binds the next container value to 'element'. This creates a new 1844 // node in the ExplodedGraph. 1845 // 1846 // (2) binds the value 0/1 to the ObjCForCollectionStmt* itself, indicating 1847 // whether or not the container has any more elements. This value 1848 // will be tested in ProcessBranch. We need to explicitly bind 1849 // this value because a container can contain nil elements. 1850 // 1851 // FIXME: Eventually this logic should actually do dispatches to 1852 // 'countByEnumeratingWithState:objects:count:' (NSFastEnumeration). 1853 // This will require simulating a temporary NSFastEnumerationState, either 1854 // through an SVal or through the use of MemRegions. This value can 1855 // be affixed to the ObjCForCollectionStmt* instead of 0/1; when the loop 1856 // terminates we reclaim the temporary (it goes out of scope) and we 1857 // we can test if the SVal is 0 or if the MemRegion is null (depending 1858 // on what approach we take). 1859 // 1860 // For now: simulate (1) by assigning either a symbol or nil if the 1861 // container is empty. Thus this transfer function will by default 1862 // result in state splitting. 1863 1864 const Stmt* elem = S->getElement(); 1865 SVal ElementV; 1866 1867 if (const DeclStmt* DS = dyn_cast<DeclStmt>(elem)) { 1868 const VarDecl* ElemD = cast<VarDecl>(DS->getSingleDecl()); 1869 assert (ElemD->getInit() == 0); 1870 ElementV = GetState(Pred)->getLValue(ElemD, Pred->getLocationContext()); 1871 VisitObjCForCollectionStmtAux(S, Pred, Dst, ElementV); 1872 return; 1873 } 1874 1875 ExplodedNodeSet Tmp; 1876 Visit(cast<Expr>(elem), Pred, Tmp); 1877 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) { 1878 const GRState* state = GetState(*I); 1879 VisitObjCForCollectionStmtAux(S, *I, Dst, state->getSVal(elem)); 1880 } 1881} 1882 1883void ExprEngine::VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt* S, 1884 ExplodedNode* Pred, ExplodedNodeSet& Dst, 1885 SVal ElementV) { 1886 1887 // Check if the location we are writing back to is a null pointer. 1888 const Stmt* elem = S->getElement(); 1889 ExplodedNodeSet Tmp; 1890 evalLocation(Tmp, elem, Pred, GetState(Pred), ElementV, NULL, false); 1891 1892 if (Tmp.empty()) 1893 return; 1894 1895 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) { 1896 Pred = *NI; 1897 const GRState *state = GetState(Pred); 1898 1899 // Handle the case where the container still has elements. 1900 SVal TrueV = svalBuilder.makeTruthVal(1); 1901 const GRState *hasElems = state->BindExpr(S, TrueV); 1902 1903 // Handle the case where the container has no elements. 1904 SVal FalseV = svalBuilder.makeTruthVal(0); 1905 const GRState *noElems = state->BindExpr(S, FalseV); 1906 1907 if (loc::MemRegionVal* MV = dyn_cast<loc::MemRegionVal>(&ElementV)) 1908 if (const TypedRegion* R = dyn_cast<TypedRegion>(MV->getRegion())) { 1909 // FIXME: The proper thing to do is to really iterate over the 1910 // container. We will do this with dispatch logic to the store. 1911 // For now, just 'conjure' up a symbolic value. 1912 QualType T = R->getValueType(); 1913 assert(Loc::isLocType(T)); 1914 unsigned Count = Builder->getCurrentBlockCount(); 1915 SymbolRef Sym = SymMgr.getConjuredSymbol(elem, T, Count); 1916 SVal V = svalBuilder.makeLoc(Sym); 1917 hasElems = hasElems->bindLoc(ElementV, V); 1918 1919 // Bind the location to 'nil' on the false branch. 1920 SVal nilV = svalBuilder.makeIntVal(0, T); 1921 noElems = noElems->bindLoc(ElementV, nilV); 1922 } 1923 1924 // Create the new nodes. 1925 MakeNode(Dst, S, Pred, hasElems); 1926 MakeNode(Dst, S, Pred, noElems); 1927 } 1928} 1929 1930//===----------------------------------------------------------------------===// 1931// Transfer function: Objective-C message expressions. 1932//===----------------------------------------------------------------------===// 1933 1934namespace { 1935class ObjCMsgWLItem { 1936public: 1937 ObjCMessageExpr::const_arg_iterator I; 1938 ExplodedNode *N; 1939 1940 ObjCMsgWLItem(const ObjCMessageExpr::const_arg_iterator &i, ExplodedNode *n) 1941 : I(i), N(n) {} 1942}; 1943} // end anonymous namespace 1944 1945void ExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr* ME, 1946 ExplodedNode* Pred, 1947 ExplodedNodeSet& Dst){ 1948 1949 // Create a worklist to process both the arguments. 1950 SmallVector<ObjCMsgWLItem, 20> WL; 1951 1952 // But first evaluate the receiver (if any). 1953 ObjCMessageExpr::const_arg_iterator AI = ME->arg_begin(), AE = ME->arg_end(); 1954 if (const Expr *Receiver = ME->getInstanceReceiver()) { 1955 ExplodedNodeSet Tmp; 1956 Visit(Receiver, Pred, Tmp); 1957 1958 if (Tmp.empty()) 1959 return; 1960 1961 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) 1962 WL.push_back(ObjCMsgWLItem(AI, *I)); 1963 } 1964 else 1965 WL.push_back(ObjCMsgWLItem(AI, Pred)); 1966 1967 // Evaluate the arguments. 1968 ExplodedNodeSet ArgsEvaluated; 1969 while (!WL.empty()) { 1970 ObjCMsgWLItem Item = WL.back(); 1971 WL.pop_back(); 1972 1973 if (Item.I == AE) { 1974 ArgsEvaluated.insert(Item.N); 1975 continue; 1976 } 1977 1978 // Evaluate the subexpression. 1979 ExplodedNodeSet Tmp; 1980 1981 // FIXME: [Objective-C++] handle arguments that are references 1982 Visit(*Item.I, Item.N, Tmp); 1983 1984 // Enqueue evaluating the next argument on the worklist. 1985 ++(Item.I); 1986 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) 1987 WL.push_back(ObjCMsgWLItem(Item.I, *NI)); 1988 } 1989 1990 // Now that the arguments are processed, handle the ObjC message. 1991 VisitObjCMessage(ME, ArgsEvaluated, Dst); 1992} 1993 1994void ExprEngine::VisitObjCMessage(const ObjCMessage &msg, 1995 ExplodedNodeSet &Src, ExplodedNodeSet& Dst) { 1996 1997 // Handle the previsits checks. 1998 ExplodedNodeSet DstPrevisit; 1999 getCheckerManager().runCheckersForPreObjCMessage(DstPrevisit, Src, msg,*this); 2000 2001 // Proceed with evaluate the message expression. 2002 ExplodedNodeSet dstEval; 2003 2004 for (ExplodedNodeSet::iterator DI = DstPrevisit.begin(), 2005 DE = DstPrevisit.end(); DI != DE; ++DI) { 2006 2007 ExplodedNode *Pred = *DI; 2008 bool RaisesException = false; 2009 unsigned oldSize = dstEval.size(); 2010 SaveAndRestore<bool> OldSink(Builder->BuildSinks); 2011 SaveOr OldHasGen(Builder->hasGeneratedNode); 2012 2013 if (const Expr *Receiver = msg.getInstanceReceiver()) { 2014 const GRState *state = GetState(Pred); 2015 SVal recVal = state->getSVal(Receiver); 2016 if (!recVal.isUndef()) { 2017 // Bifurcate the state into nil and non-nil ones. 2018 DefinedOrUnknownSVal receiverVal = cast<DefinedOrUnknownSVal>(recVal); 2019 2020 const GRState *notNilState, *nilState; 2021 llvm::tie(notNilState, nilState) = state->assume(receiverVal); 2022 2023 // There are three cases: can be nil or non-nil, must be nil, must be 2024 // non-nil. We ignore must be nil, and merge the rest two into non-nil. 2025 if (nilState && !notNilState) { 2026 dstEval.insert(Pred); 2027 continue; 2028 } 2029 2030 // Check if the "raise" message was sent. 2031 assert(notNilState); 2032 if (msg.getSelector() == RaiseSel) 2033 RaisesException = true; 2034 2035 // Check if we raise an exception. For now treat these as sinks. 2036 // Eventually we will want to handle exceptions properly. 2037 if (RaisesException) 2038 Builder->BuildSinks = true; 2039 2040 // Dispatch to plug-in transfer function. 2041 evalObjCMessage(dstEval, msg, Pred, notNilState); 2042 } 2043 } 2044 else if (const ObjCInterfaceDecl *Iface = msg.getReceiverInterface()) { 2045 IdentifierInfo* ClsName = Iface->getIdentifier(); 2046 Selector S = msg.getSelector(); 2047 2048 // Check for special instance methods. 2049 if (!NSExceptionII) { 2050 ASTContext& Ctx = getContext(); 2051 NSExceptionII = &Ctx.Idents.get("NSException"); 2052 } 2053 2054 if (ClsName == NSExceptionII) { 2055 enum { NUM_RAISE_SELECTORS = 2 }; 2056 2057 // Lazily create a cache of the selectors. 2058 if (!NSExceptionInstanceRaiseSelectors) { 2059 ASTContext& Ctx = getContext(); 2060 NSExceptionInstanceRaiseSelectors = 2061 new Selector[NUM_RAISE_SELECTORS]; 2062 SmallVector<IdentifierInfo*, NUM_RAISE_SELECTORS> II; 2063 unsigned idx = 0; 2064 2065 // raise:format: 2066 II.push_back(&Ctx.Idents.get("raise")); 2067 II.push_back(&Ctx.Idents.get("format")); 2068 NSExceptionInstanceRaiseSelectors[idx++] = 2069 Ctx.Selectors.getSelector(II.size(), &II[0]); 2070 2071 // raise:format::arguments: 2072 II.push_back(&Ctx.Idents.get("arguments")); 2073 NSExceptionInstanceRaiseSelectors[idx++] = 2074 Ctx.Selectors.getSelector(II.size(), &II[0]); 2075 } 2076 2077 for (unsigned i = 0; i < NUM_RAISE_SELECTORS; ++i) 2078 if (S == NSExceptionInstanceRaiseSelectors[i]) { 2079 RaisesException = true; 2080 break; 2081 } 2082 } 2083 2084 // Check if we raise an exception. For now treat these as sinks. 2085 // Eventually we will want to handle exceptions properly. 2086 if (RaisesException) 2087 Builder->BuildSinks = true; 2088 2089 // Dispatch to plug-in transfer function. 2090 evalObjCMessage(dstEval, msg, Pred, Builder->GetState(Pred)); 2091 } 2092 2093 // Handle the case where no nodes where generated. Auto-generate that 2094 // contains the updated state if we aren't generating sinks. 2095 if (!Builder->BuildSinks && dstEval.size() == oldSize && 2096 !Builder->hasGeneratedNode) 2097 MakeNode(dstEval, msg.getOriginExpr(), Pred, GetState(Pred)); 2098 } 2099 2100 // Finally, perform the post-condition check of the ObjCMessageExpr and store 2101 // the created nodes in 'Dst'. 2102 getCheckerManager().runCheckersForPostObjCMessage(Dst, dstEval, msg, *this); 2103} 2104 2105//===----------------------------------------------------------------------===// 2106// Transfer functions: Miscellaneous statements. 2107//===----------------------------------------------------------------------===// 2108 2109void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, 2110 ExplodedNode *Pred, ExplodedNodeSet &Dst) { 2111 2112 ExplodedNodeSet S1; 2113 Visit(Ex, Pred, S1); 2114 ExplodedNodeSet S2; 2115 getCheckerManager().runCheckersForPreStmt(S2, S1, CastE, *this); 2116 2117 if (CastE->getCastKind() == CK_LValueToRValue || 2118 CastE->getCastKind() == CK_GetObjCProperty) { 2119 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I!=E; ++I) { 2120 ExplodedNode *subExprNode = *I; 2121 const GRState *state = GetState(subExprNode); 2122 evalLoad(Dst, CastE, subExprNode, state, state->getSVal(Ex)); 2123 } 2124 return; 2125 } 2126 2127 // All other casts. 2128 QualType T = CastE->getType(); 2129 QualType ExTy = Ex->getType(); 2130 2131 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE)) 2132 T = ExCast->getTypeAsWritten(); 2133 2134 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) { 2135 Pred = *I; 2136 2137 switch (CastE->getCastKind()) { 2138 case CK_LValueToRValue: 2139 assert(false && "LValueToRValue casts handled earlier."); 2140 case CK_GetObjCProperty: 2141 assert(false && "GetObjCProperty casts handled earlier."); 2142 case CK_ToVoid: 2143 Dst.Add(Pred); 2144 continue; 2145 // The analyzer doesn't do anything special with these casts, 2146 // since it understands retain/release semantics already. 2147 case CK_ObjCProduceObject: 2148 case CK_ObjCConsumeObject: 2149 case CK_ObjCReclaimReturnedObject: // Fall-through. 2150 // True no-ops. 2151 case CK_NoOp: 2152 case CK_FunctionToPointerDecay: { 2153 // Copy the SVal of Ex to CastE. 2154 const GRState *state = GetState(Pred); 2155 SVal V = state->getSVal(Ex); 2156 state = state->BindExpr(CastE, V); 2157 MakeNode(Dst, CastE, Pred, state); 2158 continue; 2159 } 2160 case CK_Dependent: 2161 case CK_ArrayToPointerDecay: 2162 case CK_BitCast: 2163 case CK_LValueBitCast: 2164 case CK_IntegralCast: 2165 case CK_NullToPointer: 2166 case CK_IntegralToPointer: 2167 case CK_PointerToIntegral: 2168 case CK_PointerToBoolean: 2169 case CK_IntegralToBoolean: 2170 case CK_IntegralToFloating: 2171 case CK_FloatingToIntegral: 2172 case CK_FloatingToBoolean: 2173 case CK_FloatingCast: 2174 case CK_FloatingRealToComplex: 2175 case CK_FloatingComplexToReal: 2176 case CK_FloatingComplexToBoolean: 2177 case CK_FloatingComplexCast: 2178 case CK_FloatingComplexToIntegralComplex: 2179 case CK_IntegralRealToComplex: 2180 case CK_IntegralComplexToReal: 2181 case CK_IntegralComplexToBoolean: 2182 case CK_IntegralComplexCast: 2183 case CK_IntegralComplexToFloatingComplex: 2184 case CK_AnyPointerToObjCPointerCast: 2185 case CK_AnyPointerToBlockPointerCast: 2186 case CK_ObjCObjectLValueCast: { 2187 // Delegate to SValBuilder to process. 2188 const GRState* state = GetState(Pred); 2189 SVal V = state->getSVal(Ex); 2190 V = svalBuilder.evalCast(V, T, ExTy); 2191 state = state->BindExpr(CastE, V); 2192 MakeNode(Dst, CastE, Pred, state); 2193 continue; 2194 } 2195 case CK_DerivedToBase: 2196 case CK_UncheckedDerivedToBase: { 2197 // For DerivedToBase cast, delegate to the store manager. 2198 const GRState *state = GetState(Pred); 2199 SVal val = state->getSVal(Ex); 2200 val = getStoreManager().evalDerivedToBase(val, T); 2201 state = state->BindExpr(CastE, val); 2202 MakeNode(Dst, CastE, Pred, state); 2203 continue; 2204 } 2205 // Various C++ casts that are not handled yet. 2206 case CK_Dynamic: 2207 case CK_ToUnion: 2208 case CK_BaseToDerived: 2209 case CK_NullToMemberPointer: 2210 case CK_BaseToDerivedMemberPointer: 2211 case CK_DerivedToBaseMemberPointer: 2212 case CK_UserDefinedConversion: 2213 case CK_ConstructorConversion: 2214 case CK_VectorSplat: 2215 case CK_MemberPointerToBoolean: { 2216 // Recover some path-sensitivty by conjuring a new value. 2217 QualType resultType = CastE->getType(); 2218 if (CastE->isLValue()) 2219 resultType = getContext().getPointerType(resultType); 2220 2221 SVal result = 2222 svalBuilder.getConjuredSymbolVal(NULL, CastE, resultType, 2223 Builder->getCurrentBlockCount()); 2224 2225 const GRState *state = GetState(Pred)->BindExpr(CastE, result); 2226 MakeNode(Dst, CastE, Pred, state); 2227 continue; 2228 } 2229 } 2230 } 2231} 2232 2233void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr* CL, 2234 ExplodedNode* Pred, 2235 ExplodedNodeSet& Dst) { 2236 const InitListExpr* ILE 2237 = cast<InitListExpr>(CL->getInitializer()->IgnoreParens()); 2238 ExplodedNodeSet Tmp; 2239 Visit(ILE, Pred, Tmp); 2240 2241 for (ExplodedNodeSet::iterator I = Tmp.begin(), EI = Tmp.end(); I!=EI; ++I) { 2242 const GRState* state = GetState(*I); 2243 SVal ILV = state->getSVal(ILE); 2244 const LocationContext *LC = (*I)->getLocationContext(); 2245 state = state->bindCompoundLiteral(CL, LC, ILV); 2246 2247 if (CL->isLValue()) { 2248 MakeNode(Dst, CL, *I, state->BindExpr(CL, state->getLValue(CL, LC))); 2249 } 2250 else 2251 MakeNode(Dst, CL, *I, state->BindExpr(CL, ILV)); 2252 } 2253} 2254 2255void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, 2256 ExplodedNodeSet& Dst) { 2257 2258 // The CFG has one DeclStmt per Decl. 2259 const Decl* D = *DS->decl_begin(); 2260 2261 if (!D || !isa<VarDecl>(D)) 2262 return; 2263 2264 const VarDecl* VD = dyn_cast<VarDecl>(D); 2265 const Expr* InitEx = VD->getInit(); 2266 2267 // FIXME: static variables may have an initializer, but the second 2268 // time a function is called those values may not be current. 2269 ExplodedNodeSet Tmp; 2270 2271 if (InitEx) 2272 Visit(InitEx, Pred, Tmp); 2273 else 2274 Tmp.Add(Pred); 2275 2276 ExplodedNodeSet Tmp2; 2277 getCheckerManager().runCheckersForPreStmt(Tmp2, Tmp, DS, *this); 2278 2279 for (ExplodedNodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) { 2280 ExplodedNode *N = *I; 2281 const GRState *state = GetState(N); 2282 2283 // Decls without InitExpr are not initialized explicitly. 2284 const LocationContext *LC = N->getLocationContext(); 2285 2286 if (InitEx) { 2287 SVal InitVal = state->getSVal(InitEx); 2288 2289 // We bound the temp obj region to the CXXConstructExpr. Now recover 2290 // the lazy compound value when the variable is not a reference. 2291 if (AMgr.getLangOptions().CPlusPlus && VD->getType()->isRecordType() && 2292 !VD->getType()->isReferenceType() && isa<loc::MemRegionVal>(InitVal)){ 2293 InitVal = state->getSVal(cast<loc::MemRegionVal>(InitVal).getRegion()); 2294 assert(isa<nonloc::LazyCompoundVal>(InitVal)); 2295 } 2296 2297 // Recover some path-sensitivity if a scalar value evaluated to 2298 // UnknownVal. 2299 if ((InitVal.isUnknown() || 2300 !getConstraintManager().canReasonAbout(InitVal)) && 2301 !VD->getType()->isReferenceType()) { 2302 InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx, 2303 Builder->getCurrentBlockCount()); 2304 } 2305 2306 evalBind(Dst, DS, *I, state, 2307 loc::MemRegionVal(state->getRegion(VD, LC)), InitVal, true); 2308 } 2309 else { 2310 state = state->bindDeclWithNoInit(state->getRegion(VD, LC)); 2311 MakeNode(Dst, DS, *I, state); 2312 } 2313 } 2314} 2315 2316namespace { 2317 // This class is used by VisitInitListExpr as an item in a worklist 2318 // for processing the values contained in an InitListExpr. 2319class InitListWLItem { 2320public: 2321 llvm::ImmutableList<SVal> Vals; 2322 ExplodedNode* N; 2323 InitListExpr::const_reverse_iterator Itr; 2324 2325 InitListWLItem(ExplodedNode* n, llvm::ImmutableList<SVal> vals, 2326 InitListExpr::const_reverse_iterator itr) 2327 : Vals(vals), N(n), Itr(itr) {} 2328}; 2329} 2330 2331 2332void ExprEngine::VisitInitListExpr(const InitListExpr* E, ExplodedNode* Pred, 2333 ExplodedNodeSet& Dst) { 2334 2335 const GRState* state = GetState(Pred); 2336 QualType T = getContext().getCanonicalType(E->getType()); 2337 unsigned NumInitElements = E->getNumInits(); 2338 2339 if (T->isArrayType() || T->isRecordType() || T->isVectorType()) { 2340 llvm::ImmutableList<SVal> StartVals = getBasicVals().getEmptySValList(); 2341 2342 // Handle base case where the initializer has no elements. 2343 // e.g: static int* myArray[] = {}; 2344 if (NumInitElements == 0) { 2345 SVal V = svalBuilder.makeCompoundVal(T, StartVals); 2346 MakeNode(Dst, E, Pred, state->BindExpr(E, V)); 2347 return; 2348 } 2349 2350 // Create a worklist to process the initializers. 2351 SmallVector<InitListWLItem, 10> WorkList; 2352 WorkList.reserve(NumInitElements); 2353 WorkList.push_back(InitListWLItem(Pred, StartVals, E->rbegin())); 2354 InitListExpr::const_reverse_iterator ItrEnd = E->rend(); 2355 assert(!(E->rbegin() == E->rend())); 2356 2357 // Process the worklist until it is empty. 2358 while (!WorkList.empty()) { 2359 InitListWLItem X = WorkList.back(); 2360 WorkList.pop_back(); 2361 2362 ExplodedNodeSet Tmp; 2363 Visit(*X.Itr, X.N, Tmp); 2364 2365 InitListExpr::const_reverse_iterator NewItr = X.Itr + 1; 2366 2367 for (ExplodedNodeSet::iterator NI=Tmp.begin(),NE=Tmp.end();NI!=NE;++NI) { 2368 // Get the last initializer value. 2369 state = GetState(*NI); 2370 SVal InitV = state->getSVal(cast<Expr>(*X.Itr)); 2371 2372 // Construct the new list of values by prepending the new value to 2373 // the already constructed list. 2374 llvm::ImmutableList<SVal> NewVals = 2375 getBasicVals().consVals(InitV, X.Vals); 2376 2377 if (NewItr == ItrEnd) { 2378 // Now we have a list holding all init values. Make CompoundValData. 2379 SVal V = svalBuilder.makeCompoundVal(T, NewVals); 2380 2381 // Make final state and node. 2382 MakeNode(Dst, E, *NI, state->BindExpr(E, V)); 2383 } 2384 else { 2385 // Still some initializer values to go. Push them onto the worklist. 2386 WorkList.push_back(InitListWLItem(*NI, NewVals, NewItr)); 2387 } 2388 } 2389 } 2390 2391 return; 2392 } 2393 2394 if (Loc::isLocType(T) || T->isIntegerType()) { 2395 assert (E->getNumInits() == 1); 2396 ExplodedNodeSet Tmp; 2397 const Expr* Init = E->getInit(0); 2398 Visit(Init, Pred, Tmp); 2399 for (ExplodedNodeSet::iterator I=Tmp.begin(), EI=Tmp.end(); I != EI; ++I) { 2400 state = GetState(*I); 2401 MakeNode(Dst, E, *I, state->BindExpr(E, state->getSVal(Init))); 2402 } 2403 return; 2404 } 2405 2406 assert(0 && "unprocessed InitListExpr type"); 2407} 2408 2409/// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof(type). 2410void ExprEngine::VisitUnaryExprOrTypeTraitExpr( 2411 const UnaryExprOrTypeTraitExpr* Ex, 2412 ExplodedNode* Pred, 2413 ExplodedNodeSet& Dst) { 2414 QualType T = Ex->getTypeOfArgument(); 2415 2416 if (Ex->getKind() == UETT_SizeOf) { 2417 if (!T->isIncompleteType() && !T->isConstantSizeType()) { 2418 assert(T->isVariableArrayType() && "Unknown non-constant-sized type."); 2419 2420 // FIXME: Add support for VLA type arguments, not just VLA expressions. 2421 // When that happens, we should probably refactor VLASizeChecker's code. 2422 if (Ex->isArgumentType()) { 2423 Dst.Add(Pred); 2424 return; 2425 } 2426 2427 // Get the size by getting the extent of the sub-expression. 2428 // First, visit the sub-expression to find its region. 2429 const Expr *Arg = Ex->getArgumentExpr(); 2430 ExplodedNodeSet Tmp; 2431 Visit(Arg, Pred, Tmp); 2432 2433 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2434 const GRState* state = GetState(*I); 2435 const MemRegion *MR = state->getSVal(Arg).getAsRegion(); 2436 2437 // If the subexpression can't be resolved to a region, we don't know 2438 // anything about its size. Just leave the state as is and continue. 2439 if (!MR) { 2440 Dst.Add(*I); 2441 continue; 2442 } 2443 2444 // The result is the extent of the VLA. 2445 SVal Extent = cast<SubRegion>(MR)->getExtent(svalBuilder); 2446 MakeNode(Dst, Ex, *I, state->BindExpr(Ex, Extent)); 2447 } 2448 2449 return; 2450 } 2451 else if (T->getAs<ObjCObjectType>()) { 2452 // Some code tries to take the sizeof an ObjCObjectType, relying that 2453 // the compiler has laid out its representation. Just report Unknown 2454 // for these. 2455 Dst.Add(Pred); 2456 return; 2457 } 2458 } 2459 2460 Expr::EvalResult Result; 2461 Ex->Evaluate(Result, getContext()); 2462 CharUnits amt = CharUnits::fromQuantity(Result.Val.getInt().getZExtValue()); 2463 2464 MakeNode(Dst, Ex, Pred, 2465 GetState(Pred)->BindExpr(Ex, 2466 svalBuilder.makeIntVal(amt.getQuantity(), Ex->getType()))); 2467} 2468 2469void ExprEngine::VisitOffsetOfExpr(const OffsetOfExpr* OOE, 2470 ExplodedNode* Pred, ExplodedNodeSet& Dst) { 2471 Expr::EvalResult Res; 2472 if (OOE->Evaluate(Res, getContext()) && Res.Val.isInt()) { 2473 const APSInt &IV = Res.Val.getInt(); 2474 assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType())); 2475 assert(OOE->getType()->isIntegerType()); 2476 assert(IV.isSigned() == OOE->getType()->isSignedIntegerOrEnumerationType()); 2477 SVal X = svalBuilder.makeIntVal(IV); 2478 MakeNode(Dst, OOE, Pred, GetState(Pred)->BindExpr(OOE, X)); 2479 return; 2480 } 2481 // FIXME: Handle the case where __builtin_offsetof is not a constant. 2482 Dst.Add(Pred); 2483} 2484 2485void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, 2486 ExplodedNode* Pred, 2487 ExplodedNodeSet& Dst) { 2488 2489 switch (U->getOpcode()) { 2490 2491 default: 2492 break; 2493 2494 case UO_Real: { 2495 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2496 ExplodedNodeSet Tmp; 2497 Visit(Ex, Pred, Tmp); 2498 2499 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2500 2501 // FIXME: We don't have complex SValues yet. 2502 if (Ex->getType()->isAnyComplexType()) { 2503 // Just report "Unknown." 2504 Dst.Add(*I); 2505 continue; 2506 } 2507 2508 // For all other types, UO_Real is an identity operation. 2509 assert (U->getType() == Ex->getType()); 2510 const GRState* state = GetState(*I); 2511 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex))); 2512 } 2513 2514 return; 2515 } 2516 2517 case UO_Imag: { 2518 2519 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2520 ExplodedNodeSet Tmp; 2521 Visit(Ex, Pred, Tmp); 2522 2523 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2524 // FIXME: We don't have complex SValues yet. 2525 if (Ex->getType()->isAnyComplexType()) { 2526 // Just report "Unknown." 2527 Dst.Add(*I); 2528 continue; 2529 } 2530 2531 // For all other types, UO_Imag returns 0. 2532 const GRState* state = GetState(*I); 2533 SVal X = svalBuilder.makeZeroVal(Ex->getType()); 2534 MakeNode(Dst, U, *I, state->BindExpr(U, X)); 2535 } 2536 2537 return; 2538 } 2539 2540 case UO_Plus: 2541 assert(!U->isLValue()); 2542 // FALL-THROUGH. 2543 case UO_Deref: 2544 case UO_AddrOf: 2545 case UO_Extension: { 2546 2547 // Unary "+" is a no-op, similar to a parentheses. We still have places 2548 // where it may be a block-level expression, so we need to 2549 // generate an extra node that just propagates the value of the 2550 // subexpression. 2551 2552 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2553 ExplodedNodeSet Tmp; 2554 Visit(Ex, Pred, Tmp); 2555 2556 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2557 const GRState* state = GetState(*I); 2558 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex))); 2559 } 2560 2561 return; 2562 } 2563 2564 case UO_LNot: 2565 case UO_Minus: 2566 case UO_Not: { 2567 assert (!U->isLValue()); 2568 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2569 ExplodedNodeSet Tmp; 2570 Visit(Ex, Pred, Tmp); 2571 2572 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { 2573 const GRState* state = GetState(*I); 2574 2575 // Get the value of the subexpression. 2576 SVal V = state->getSVal(Ex); 2577 2578 if (V.isUnknownOrUndef()) { 2579 MakeNode(Dst, U, *I, state->BindExpr(U, V)); 2580 continue; 2581 } 2582 2583// QualType DstT = getContext().getCanonicalType(U->getType()); 2584// QualType SrcT = getContext().getCanonicalType(Ex->getType()); 2585// 2586// if (DstT != SrcT) // Perform promotions. 2587// V = evalCast(V, DstT); 2588// 2589// if (V.isUnknownOrUndef()) { 2590// MakeNode(Dst, U, *I, BindExpr(St, U, V)); 2591// continue; 2592// } 2593 2594 switch (U->getOpcode()) { 2595 default: 2596 assert(false && "Invalid Opcode."); 2597 break; 2598 2599 case UO_Not: 2600 // FIXME: Do we need to handle promotions? 2601 state = state->BindExpr(U, evalComplement(cast<NonLoc>(V))); 2602 break; 2603 2604 case UO_Minus: 2605 // FIXME: Do we need to handle promotions? 2606 state = state->BindExpr(U, evalMinus(cast<NonLoc>(V))); 2607 break; 2608 2609 case UO_LNot: 2610 2611 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)." 2612 // 2613 // Note: technically we do "E == 0", but this is the same in the 2614 // transfer functions as "0 == E". 2615 SVal Result; 2616 2617 if (isa<Loc>(V)) { 2618 Loc X = svalBuilder.makeNull(); 2619 Result = evalBinOp(state, BO_EQ, cast<Loc>(V), X, 2620 U->getType()); 2621 } 2622 else { 2623 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType())); 2624 Result = evalBinOp(state, BO_EQ, cast<NonLoc>(V), X, 2625 U->getType()); 2626 } 2627 2628 state = state->BindExpr(U, Result); 2629 2630 break; 2631 } 2632 2633 MakeNode(Dst, U, *I, state); 2634 } 2635 2636 return; 2637 } 2638 } 2639 2640 // Handle ++ and -- (both pre- and post-increment). 2641 assert (U->isIncrementDecrementOp()); 2642 ExplodedNodeSet Tmp; 2643 const Expr* Ex = U->getSubExpr()->IgnoreParens(); 2644 Visit(Ex, Pred, Tmp); 2645 2646 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) { 2647 2648 const GRState* state = GetState(*I); 2649 SVal loc = state->getSVal(Ex); 2650 2651 // Perform a load. 2652 ExplodedNodeSet Tmp2; 2653 evalLoad(Tmp2, Ex, *I, state, loc); 2654 2655 for (ExplodedNodeSet::iterator I2=Tmp2.begin(), E2=Tmp2.end();I2!=E2;++I2) { 2656 2657 state = GetState(*I2); 2658 SVal V2_untested = state->getSVal(Ex); 2659 2660 // Propagate unknown and undefined values. 2661 if (V2_untested.isUnknownOrUndef()) { 2662 MakeNode(Dst, U, *I2, state->BindExpr(U, V2_untested)); 2663 continue; 2664 } 2665 DefinedSVal V2 = cast<DefinedSVal>(V2_untested); 2666 2667 // Handle all other values. 2668 BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add 2669 : BO_Sub; 2670 2671 // If the UnaryOperator has non-location type, use its type to create the 2672 // constant value. If the UnaryOperator has location type, create the 2673 // constant with int type and pointer width. 2674 SVal RHS; 2675 2676 if (U->getType()->isAnyPointerType()) 2677 RHS = svalBuilder.makeArrayIndex(1); 2678 else 2679 RHS = svalBuilder.makeIntVal(1, U->getType()); 2680 2681 SVal Result = evalBinOp(state, Op, V2, RHS, U->getType()); 2682 2683 // Conjure a new symbol if necessary to recover precision. 2684 if (Result.isUnknown() || !getConstraintManager().canReasonAbout(Result)){ 2685 DefinedOrUnknownSVal SymVal = 2686 svalBuilder.getConjuredSymbolVal(NULL, Ex, 2687 Builder->getCurrentBlockCount()); 2688 Result = SymVal; 2689 2690 // If the value is a location, ++/-- should always preserve 2691 // non-nullness. Check if the original value was non-null, and if so 2692 // propagate that constraint. 2693 if (Loc::isLocType(U->getType())) { 2694 DefinedOrUnknownSVal Constraint = 2695 svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType())); 2696 2697 if (!state->assume(Constraint, true)) { 2698 // It isn't feasible for the original value to be null. 2699 // Propagate this constraint. 2700 Constraint = svalBuilder.evalEQ(state, SymVal, 2701 svalBuilder.makeZeroVal(U->getType())); 2702 2703 2704 state = state->assume(Constraint, false); 2705 assert(state); 2706 } 2707 } 2708 } 2709 2710 // Since the lvalue-to-rvalue conversion is explicit in the AST, 2711 // we bind an l-value if the operator is prefix and an lvalue (in C++). 2712 if (U->isLValue()) 2713 state = state->BindExpr(U, loc); 2714 else 2715 state = state->BindExpr(U, U->isPostfix() ? V2 : Result); 2716 2717 // Perform the store. 2718 evalStore(Dst, NULL, U, *I2, state, loc, Result); 2719 } 2720 } 2721} 2722 2723void ExprEngine::VisitAsmStmt(const AsmStmt* A, ExplodedNode* Pred, 2724 ExplodedNodeSet& Dst) { 2725 VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst); 2726} 2727 2728void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt* A, 2729 AsmStmt::const_outputs_iterator I, 2730 AsmStmt::const_outputs_iterator E, 2731 ExplodedNode* Pred, ExplodedNodeSet& Dst) { 2732 if (I == E) { 2733 VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst); 2734 return; 2735 } 2736 2737 ExplodedNodeSet Tmp; 2738 Visit(*I, Pred, Tmp); 2739 ++I; 2740 2741 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI) 2742 VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst); 2743} 2744 2745void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt* A, 2746 AsmStmt::const_inputs_iterator I, 2747 AsmStmt::const_inputs_iterator E, 2748 ExplodedNode* Pred, 2749 ExplodedNodeSet& Dst) { 2750 if (I == E) { 2751 2752 // We have processed both the inputs and the outputs. All of the outputs 2753 // should evaluate to Locs. Nuke all of their values. 2754 2755 // FIXME: Some day in the future it would be nice to allow a "plug-in" 2756 // which interprets the inline asm and stores proper results in the 2757 // outputs. 2758 2759 const GRState* state = GetState(Pred); 2760 2761 for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(), 2762 OE = A->end_outputs(); OI != OE; ++OI) { 2763 2764 SVal X = state->getSVal(*OI); 2765 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef. 2766 2767 if (isa<Loc>(X)) 2768 state = state->bindLoc(cast<Loc>(X), UnknownVal()); 2769 } 2770 2771 MakeNode(Dst, A, Pred, state); 2772 return; 2773 } 2774 2775 ExplodedNodeSet Tmp; 2776 Visit(*I, Pred, Tmp); 2777 2778 ++I; 2779 2780 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI) 2781 VisitAsmStmtHelperInputs(A, I, E, *NI, Dst); 2782} 2783 2784void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 2785 ExplodedNodeSet &Dst) { 2786 ExplodedNodeSet Src; 2787 if (const Expr *RetE = RS->getRetValue()) { 2788 // Record the returned expression in the state. It will be used in 2789 // processCallExit to bind the return value to the call expr. 2790 { 2791 static int tag = 0; 2792 const GRState *state = GetState(Pred); 2793 state = state->set<ReturnExpr>(RetE); 2794 Pred = Builder->generateNode(RetE, state, Pred, &tag); 2795 } 2796 // We may get a NULL Pred because we generated a cached node. 2797 if (Pred) 2798 Visit(RetE, Pred, Src); 2799 } 2800 else { 2801 Src.Add(Pred); 2802 } 2803 2804 ExplodedNodeSet CheckedSet; 2805 getCheckerManager().runCheckersForPreStmt(CheckedSet, Src, RS, *this); 2806 2807 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); 2808 I != E; ++I) { 2809 2810 assert(Builder && "StmtNodeBuilder must be defined."); 2811 2812 Pred = *I; 2813 unsigned size = Dst.size(); 2814 2815 SaveAndRestore<bool> OldSink(Builder->BuildSinks); 2816 SaveOr OldHasGen(Builder->hasGeneratedNode); 2817 2818 getTF().evalReturn(Dst, *this, *Builder, RS, Pred); 2819 2820 // Handle the case where no nodes where generated. 2821 if (!Builder->BuildSinks && Dst.size() == size && 2822 !Builder->hasGeneratedNode) 2823 MakeNode(Dst, RS, Pred, GetState(Pred)); 2824 } 2825} 2826 2827//===----------------------------------------------------------------------===// 2828// Transfer functions: Binary operators. 2829//===----------------------------------------------------------------------===// 2830 2831void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, 2832 ExplodedNode* Pred, 2833 ExplodedNodeSet& Dst) { 2834 ExplodedNodeSet Tmp1; 2835 Expr* LHS = B->getLHS()->IgnoreParens(); 2836 Expr* RHS = B->getRHS()->IgnoreParens(); 2837 2838 Visit(LHS, Pred, Tmp1); 2839 ExplodedNodeSet Tmp3; 2840 2841 for (ExplodedNodeSet::iterator I1=Tmp1.begin(), E1=Tmp1.end(); I1!=E1; ++I1) { 2842 SVal LeftV = GetState(*I1)->getSVal(LHS); 2843 ExplodedNodeSet Tmp2; 2844 Visit(RHS, *I1, Tmp2); 2845 2846 ExplodedNodeSet CheckedSet; 2847 getCheckerManager().runCheckersForPreStmt(CheckedSet, Tmp2, B, *this); 2848 2849 // With both the LHS and RHS evaluated, process the operation itself. 2850 2851 for (ExplodedNodeSet::iterator I2=CheckedSet.begin(), E2=CheckedSet.end(); 2852 I2 != E2; ++I2) { 2853 2854 const GRState *state = GetState(*I2); 2855 SVal RightV = state->getSVal(RHS); 2856 2857 BinaryOperator::Opcode Op = B->getOpcode(); 2858 2859 if (Op == BO_Assign) { 2860 // EXPERIMENTAL: "Conjured" symbols. 2861 // FIXME: Handle structs. 2862 if (RightV.isUnknown() ||!getConstraintManager().canReasonAbout(RightV)) 2863 { 2864 unsigned Count = Builder->getCurrentBlockCount(); 2865 RightV = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), Count); 2866 } 2867 2868 SVal ExprVal = B->isLValue() ? LeftV : RightV; 2869 2870 // Simulate the effects of a "store": bind the value of the RHS 2871 // to the L-Value represented by the LHS. 2872 evalStore(Tmp3, B, LHS, *I2, state->BindExpr(B, ExprVal), LeftV,RightV); 2873 continue; 2874 } 2875 2876 if (!B->isAssignmentOp()) { 2877 // Process non-assignments except commas or short-circuited 2878 // logical expressions (LAnd and LOr). 2879 SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType()); 2880 2881 if (Result.isUnknown()) { 2882 MakeNode(Tmp3, B, *I2, state); 2883 continue; 2884 } 2885 2886 state = state->BindExpr(B, Result); 2887 2888 MakeNode(Tmp3, B, *I2, state); 2889 continue; 2890 } 2891 2892 assert (B->isCompoundAssignmentOp()); 2893 2894 switch (Op) { 2895 default: 2896 assert(0 && "Invalid opcode for compound assignment."); 2897 case BO_MulAssign: Op = BO_Mul; break; 2898 case BO_DivAssign: Op = BO_Div; break; 2899 case BO_RemAssign: Op = BO_Rem; break; 2900 case BO_AddAssign: Op = BO_Add; break; 2901 case BO_SubAssign: Op = BO_Sub; break; 2902 case BO_ShlAssign: Op = BO_Shl; break; 2903 case BO_ShrAssign: Op = BO_Shr; break; 2904 case BO_AndAssign: Op = BO_And; break; 2905 case BO_XorAssign: Op = BO_Xor; break; 2906 case BO_OrAssign: Op = BO_Or; break; 2907 } 2908 2909 // Perform a load (the LHS). This performs the checks for 2910 // null dereferences, and so on. 2911 ExplodedNodeSet Tmp4; 2912 SVal location = state->getSVal(LHS); 2913 evalLoad(Tmp4, LHS, *I2, state, location); 2914 2915 for (ExplodedNodeSet::iterator I4=Tmp4.begin(), E4=Tmp4.end(); I4!=E4; 2916 ++I4) { 2917 state = GetState(*I4); 2918 SVal V = state->getSVal(LHS); 2919 2920 // Get the computation type. 2921 QualType CTy = 2922 cast<CompoundAssignOperator>(B)->getComputationResultType(); 2923 CTy = getContext().getCanonicalType(CTy); 2924 2925 QualType CLHSTy = 2926 cast<CompoundAssignOperator>(B)->getComputationLHSType(); 2927 CLHSTy = getContext().getCanonicalType(CLHSTy); 2928 2929 QualType LTy = getContext().getCanonicalType(LHS->getType()); 2930 2931 // Promote LHS. 2932 V = svalBuilder.evalCast(V, CLHSTy, LTy); 2933 2934 // Compute the result of the operation. 2935 SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy), 2936 B->getType(), CTy); 2937 2938 // EXPERIMENTAL: "Conjured" symbols. 2939 // FIXME: Handle structs. 2940 2941 SVal LHSVal; 2942 2943 if (Result.isUnknown() || 2944 !getConstraintManager().canReasonAbout(Result)) { 2945 2946 unsigned Count = Builder->getCurrentBlockCount(); 2947 2948 // The symbolic value is actually for the type of the left-hand side 2949 // expression, not the computation type, as this is the value the 2950 // LValue on the LHS will bind to. 2951 LHSVal = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LTy, Count); 2952 2953 // However, we need to convert the symbol to the computation type. 2954 Result = svalBuilder.evalCast(LHSVal, CTy, LTy); 2955 } 2956 else { 2957 // The left-hand side may bind to a different value then the 2958 // computation type. 2959 LHSVal = svalBuilder.evalCast(Result, LTy, CTy); 2960 } 2961 2962 // In C++, assignment and compound assignment operators return an 2963 // lvalue. 2964 if (B->isLValue()) 2965 state = state->BindExpr(B, location); 2966 else 2967 state = state->BindExpr(B, Result); 2968 2969 evalStore(Tmp3, B, LHS, *I4, state, location, LHSVal); 2970 } 2971 } 2972 } 2973 2974 getCheckerManager().runCheckersForPostStmt(Dst, Tmp3, B, *this); 2975} 2976 2977//===----------------------------------------------------------------------===// 2978// Visualization. 2979//===----------------------------------------------------------------------===// 2980 2981#ifndef NDEBUG 2982static ExprEngine* GraphPrintCheckerState; 2983static SourceManager* GraphPrintSourceManager; 2984 2985namespace llvm { 2986template<> 2987struct DOTGraphTraits<ExplodedNode*> : 2988 public DefaultDOTGraphTraits { 2989 2990 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2991 2992 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not 2993 // work. 2994 static std::string getNodeAttributes(const ExplodedNode* N, void*) { 2995 2996#if 0 2997 // FIXME: Replace with a general scheme to tell if the node is 2998 // an error node. 2999 if (GraphPrintCheckerState->isImplicitNullDeref(N) || 3000 GraphPrintCheckerState->isExplicitNullDeref(N) || 3001 GraphPrintCheckerState->isUndefDeref(N) || 3002 GraphPrintCheckerState->isUndefStore(N) || 3003 GraphPrintCheckerState->isUndefControlFlow(N) || 3004 GraphPrintCheckerState->isUndefResult(N) || 3005 GraphPrintCheckerState->isBadCall(N) || 3006 GraphPrintCheckerState->isUndefArg(N)) 3007 return "color=\"red\",style=\"filled\""; 3008 3009 if (GraphPrintCheckerState->isNoReturnCall(N)) 3010 return "color=\"blue\",style=\"filled\""; 3011#endif 3012 return ""; 3013 } 3014 3015 static std::string getNodeLabel(const ExplodedNode* N, void*){ 3016 3017 std::string sbuf; 3018 llvm::raw_string_ostream Out(sbuf); 3019 3020 // Program Location. 3021 ProgramPoint Loc = N->getLocation(); 3022 3023 switch (Loc.getKind()) { 3024 case ProgramPoint::BlockEntranceKind: 3025 Out << "Block Entrance: B" 3026 << cast<BlockEntrance>(Loc).getBlock()->getBlockID(); 3027 break; 3028 3029 case ProgramPoint::BlockExitKind: 3030 assert (false); 3031 break; 3032 3033 case ProgramPoint::CallEnterKind: 3034 Out << "CallEnter"; 3035 break; 3036 3037 case ProgramPoint::CallExitKind: 3038 Out << "CallExit"; 3039 break; 3040 3041 default: { 3042 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) { 3043 const Stmt* S = L->getStmt(); 3044 SourceLocation SLoc = S->getLocStart(); 3045 3046 Out << S->getStmtClassName() << ' ' << (void*) S << ' '; 3047 LangOptions LO; // FIXME. 3048 S->printPretty(Out, 0, PrintingPolicy(LO)); 3049 3050 if (SLoc.isFileID()) { 3051 Out << "\\lline=" 3052 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 3053 << " col=" 3054 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc) 3055 << "\\l"; 3056 } 3057 3058 if (isa<PreStmt>(Loc)) 3059 Out << "\\lPreStmt\\l;"; 3060 else if (isa<PostLoad>(Loc)) 3061 Out << "\\lPostLoad\\l;"; 3062 else if (isa<PostStore>(Loc)) 3063 Out << "\\lPostStore\\l"; 3064 else if (isa<PostLValue>(Loc)) 3065 Out << "\\lPostLValue\\l"; 3066 3067#if 0 3068 // FIXME: Replace with a general scheme to determine 3069 // the name of the check. 3070 if (GraphPrintCheckerState->isImplicitNullDeref(N)) 3071 Out << "\\|Implicit-Null Dereference.\\l"; 3072 else if (GraphPrintCheckerState->isExplicitNullDeref(N)) 3073 Out << "\\|Explicit-Null Dereference.\\l"; 3074 else if (GraphPrintCheckerState->isUndefDeref(N)) 3075 Out << "\\|Dereference of undefialied value.\\l"; 3076 else if (GraphPrintCheckerState->isUndefStore(N)) 3077 Out << "\\|Store to Undefined Loc."; 3078 else if (GraphPrintCheckerState->isUndefResult(N)) 3079 Out << "\\|Result of operation is undefined."; 3080 else if (GraphPrintCheckerState->isNoReturnCall(N)) 3081 Out << "\\|Call to function marked \"noreturn\"."; 3082 else if (GraphPrintCheckerState->isBadCall(N)) 3083 Out << "\\|Call to NULL/Undefined."; 3084 else if (GraphPrintCheckerState->isUndefArg(N)) 3085 Out << "\\|Argument in call is undefined"; 3086#endif 3087 3088 break; 3089 } 3090 3091 const BlockEdge& E = cast<BlockEdge>(Loc); 3092 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B" 3093 << E.getDst()->getBlockID() << ')'; 3094 3095 if (const Stmt* T = E.getSrc()->getTerminator()) { 3096 3097 SourceLocation SLoc = T->getLocStart(); 3098 3099 Out << "\\|Terminator: "; 3100 LangOptions LO; // FIXME. 3101 E.getSrc()->printTerminator(Out, LO); 3102 3103 if (SLoc.isFileID()) { 3104 Out << "\\lline=" 3105 << GraphPrintSourceManager->getExpansionLineNumber(SLoc) 3106 << " col=" 3107 << GraphPrintSourceManager->getExpansionColumnNumber(SLoc); 3108 } 3109 3110 if (isa<SwitchStmt>(T)) { 3111 const Stmt* Label = E.getDst()->getLabel(); 3112 3113 if (Label) { 3114 if (const CaseStmt* C = dyn_cast<CaseStmt>(Label)) { 3115 Out << "\\lcase "; 3116 LangOptions LO; // FIXME. 3117 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO)); 3118 3119 if (const Stmt* RHS = C->getRHS()) { 3120 Out << " .. "; 3121 RHS->printPretty(Out, 0, PrintingPolicy(LO)); 3122 } 3123 3124 Out << ":"; 3125 } 3126 else { 3127 assert (isa<DefaultStmt>(Label)); 3128 Out << "\\ldefault:"; 3129 } 3130 } 3131 else 3132 Out << "\\l(implicit) default:"; 3133 } 3134 else if (isa<IndirectGotoStmt>(T)) { 3135 // FIXME 3136 } 3137 else { 3138 Out << "\\lCondition: "; 3139 if (*E.getSrc()->succ_begin() == E.getDst()) 3140 Out << "true"; 3141 else 3142 Out << "false"; 3143 } 3144 3145 Out << "\\l"; 3146 } 3147 3148#if 0 3149 // FIXME: Replace with a general scheme to determine 3150 // the name of the check. 3151 if (GraphPrintCheckerState->isUndefControlFlow(N)) { 3152 Out << "\\|Control-flow based on\\lUndefined value.\\l"; 3153 } 3154#endif 3155 } 3156 } 3157 3158 const GRState *state = N->getState(); 3159 Out << "\\|StateID: " << (void*) state 3160 << " NodeID: " << (void*) N << "\\|"; 3161 state->printDOT(Out, *N->getLocationContext()->getCFG()); 3162 Out << "\\l"; 3163 return Out.str(); 3164 } 3165}; 3166} // end llvm namespace 3167#endif 3168 3169#ifndef NDEBUG 3170template <typename ITERATOR> 3171ExplodedNode* GetGraphNode(ITERATOR I) { return *I; } 3172 3173template <> ExplodedNode* 3174GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator> 3175 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) { 3176 return I->first; 3177} 3178#endif 3179 3180void ExprEngine::ViewGraph(bool trim) { 3181#ifndef NDEBUG 3182 if (trim) { 3183 std::vector<ExplodedNode*> Src; 3184 3185 // Flush any outstanding reports to make sure we cover all the nodes. 3186 // This does not cause them to get displayed. 3187 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) 3188 const_cast<BugType*>(*I)->FlushReports(BR); 3189 3190 // Iterate through the reports and get their nodes. 3191 for (BugReporter::EQClasses_iterator 3192 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) { 3193 BugReportEquivClass& EQ = *EI; 3194 const BugReport &R = **EQ.begin(); 3195 ExplodedNode *N = const_cast<ExplodedNode*>(R.getErrorNode()); 3196 if (N) Src.push_back(N); 3197 } 3198 3199 ViewGraph(&Src[0], &Src[0]+Src.size()); 3200 } 3201 else { 3202 GraphPrintCheckerState = this; 3203 GraphPrintSourceManager = &getContext().getSourceManager(); 3204 3205 llvm::ViewGraph(*G.roots_begin(), "ExprEngine"); 3206 3207 GraphPrintCheckerState = NULL; 3208 GraphPrintSourceManager = NULL; 3209 } 3210#endif 3211} 3212 3213void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) { 3214#ifndef NDEBUG 3215 GraphPrintCheckerState = this; 3216 GraphPrintSourceManager = &getContext().getSourceManager(); 3217 3218 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first); 3219 3220 if (!TrimmedG.get()) 3221 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; 3222 else 3223 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine"); 3224 3225 GraphPrintCheckerState = NULL; 3226 GraphPrintSourceManager = NULL; 3227#endif 3228} 3229