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