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