1 //=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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"
33 #include "llvm/Support/GraphWriter.h"
36 using namespace clang;
39 using llvm::dyn_cast_or_null;
44 // Trait class for recording returned expression in the state.
47 typedef const Stmt *data_type;
49 int ReturnExpr::TagInt;
52 //===----------------------------------------------------------------------===//
54 //===----------------------------------------------------------------------===//
56 static inline Selector GetNullarySelector(const char* name, ASTContext& Ctx) {
57 IdentifierInfo* II = &Ctx.Idents.get(name);
58 return Ctx.Selectors.getSelector(0, &II);
61 //===----------------------------------------------------------------------===//
62 // Engine construction and deletion.
63 //===----------------------------------------------------------------------===//
65 ExprEngine::ExprEngine(AnalysisManager &mgr, TransferFuncs *tf)
70 StateMgr(getContext(), mgr.getStoreManagerCreator(),
71 mgr.getConstraintManagerCreator(), G.getAllocator(),
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) {
80 // FIXME: Eventually remove the TF object entirely.
81 TF->RegisterChecks(*this);
82 TF->RegisterPrinters(getStateManager().Printers);
84 if (mgr.shouldEagerlyTrimExplodedGraph()) {
85 // Enable eager node reclaimation when constructing the ExplodedGraph.
86 G.enableNodeReclamation();
90 ExprEngine::~ExprEngine() {
92 delete [] NSExceptionInstanceRaiseSelectors;
95 //===----------------------------------------------------------------------===//
97 //===----------------------------------------------------------------------===//
99 const GRState* ExprEngine::getInitialState(const LocationContext *InitLoc) {
100 const GRState *state = StateMgr.getInitialState(InitLoc);
104 // FIXME: It would be nice if we had a more general mechanism to add
105 // such preconditions. Some day.
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
111 const IdentifierInfo *II = FD->getIdentifier();
112 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
115 const ParmVarDecl *PD = FD->getParamDecl(0);
116 QualType T = PD->getType();
117 if (!T->isIntegerType())
120 const MemRegion *R = state->getRegion(PD, InitLoc);
124 SVal V = state->getSVal(loc::MemRegionVal(R));
125 SVal Constraint_untested = evalBinOp(state, BO_GT, V,
126 svalBuilder.makeZeroVal(T),
129 DefinedOrUnknownSVal *Constraint =
130 dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested);
135 if (const GRState *newState = state->assume(*Constraint, true))
141 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
142 // Precondition: 'self' is always non-null upon entry to an Objective-C
144 const ImplicitParamDecl *SelfD = MD->getSelfDecl();
145 const MemRegion *R = state->getRegion(SelfD, InitLoc);
146 SVal V = state->getSVal(loc::MemRegionVal(R));
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");
160 ExprEngine::doesInvalidateGlobals(const CallOrObjCMessage &callOrMessage) const
162 if (callOrMessage.isFunctionCall() && !callOrMessage.isCXXCall()) {
163 SVal calleeV = callOrMessage.getFunctionCallee();
164 if (const FunctionTextRegion *codeR =
165 llvm::dyn_cast_or_null<FunctionTextRegion>(calleeV.getAsRegion())) {
167 const FunctionDecl *fd = codeR->getDecl();
168 if (const IdentifierInfo *ii = fd->getIdentifier()) {
169 llvm::StringRef fname = ii->getName();
170 if (fname == "strlen")
176 // The conservative answer: invalidates globals.
180 //===----------------------------------------------------------------------===//
181 // Top-level transfer function logic (Dispatcher).
182 //===----------------------------------------------------------------------===//
184 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
185 /// logic for handling assumptions on symbolic values.
186 const GRState *ExprEngine::processAssume(const GRState *state, SVal cond,
188 state = getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
190 // If the state is infeasible at this point, bail out.
194 return TF->evalAssume(state, cond, assumption);
197 bool ExprEngine::wantsRegionChangeUpdate(const GRState* state) {
198 return getCheckerManager().wantsRegionChangeUpdate(state);
202 ExprEngine::processRegionChanges(const GRState *state,
203 const StoreManager::InvalidatedSymbols *invalidated,
204 const MemRegion * const *Begin,
205 const MemRegion * const *End) {
206 return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
210 void ExprEngine::processEndWorklist(bool hasWorkRemaining) {
211 getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
214 void ExprEngine::processCFGElement(const CFGElement E,
215 StmtNodeBuilder& builder) {
216 switch (E.getKind()) {
217 case CFGElement::Invalid:
218 llvm_unreachable("Unexpected CFGElement kind.");
219 case CFGElement::Statement:
220 ProcessStmt(E.getAs<CFGStmt>()->getStmt(), builder);
222 case CFGElement::Initializer:
223 ProcessInitializer(E.getAs<CFGInitializer>()->getInitializer(), builder);
225 case CFGElement::AutomaticObjectDtor:
226 case CFGElement::BaseDtor:
227 case CFGElement::MemberDtor:
228 case CFGElement::TemporaryDtor:
229 ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), builder);
234 void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) {
235 // Reclaim any unnecessary nodes in the ExplodedGraph.
236 G.reclaimRecentlyAllocatedNodes();
237 // Recycle any unused states in the GRStateManager.
238 StateMgr.recycleUnusedStates();
240 currentStmt = S.getStmt();
241 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
242 currentStmt->getLocStart(),
243 "Error evaluating statement");
246 EntryNode = builder.getPredecessor();
248 // Create the cleaned state.
249 const LocationContext *LC = EntryNode->getLocationContext();
250 SymbolReaper SymReaper(LC, currentStmt, SymMgr);
252 if (AMgr.shouldPurgeDead()) {
253 const GRState *St = EntryNode->getState();
254 getCheckerManager().runCheckersForLiveSymbols(St, SymReaper);
256 const StackFrameContext *SFC = LC->getCurrentStackFrame();
257 CleanedState = StateMgr.removeDeadBindings(St, SFC, SymReaper);
259 CleanedState = EntryNode->getState();
262 // Process any special transfer function for dead symbols.
265 if (!SymReaper.hasDeadSymbols())
268 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
269 SaveOr OldHasGen(Builder->hasGeneratedNode);
271 SaveAndRestore<bool> OldPurgeDeadSymbols(Builder->PurgingDeadSymbols);
272 Builder->PurgingDeadSymbols = true;
274 // FIXME: This should soon be removed.
275 ExplodedNodeSet Tmp2;
276 getTF().evalDeadSymbols(Tmp2, *this, *Builder, EntryNode,
277 CleanedState, SymReaper);
279 getCheckerManager().runCheckersForDeadSymbols(Tmp, Tmp2,
280 SymReaper, currentStmt, *this);
282 if (!Builder->BuildSinks && !Builder->hasGeneratedNode)
286 bool HasAutoGenerated = false;
288 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
291 // Set the cleaned state.
292 Builder->SetCleanedState(*I == EntryNode ? CleanedState : GetState(*I));
294 // Visit the statement.
295 Visit(currentStmt, *I, Dst);
297 // Do we need to auto-generate a node? We only need to do this to generate
298 // a node with a "cleaned" state; CoreEngine will actually handle
299 // auto-transitions for other cases.
300 if (Dst.size() == 1 && *Dst.begin() == EntryNode
301 && !Builder->hasGeneratedNode && !HasAutoGenerated) {
302 HasAutoGenerated = true;
303 builder.generateNode(currentStmt, GetState(EntryNode), *I);
307 // NULL out these variables to cleanup.
316 void ExprEngine::ProcessInitializer(const CFGInitializer Init,
317 StmtNodeBuilder &builder) {
318 // We don't set EntryNode and currentStmt. And we don't clean up state.
319 const CXXCtorInitializer *BMI = Init.getInitializer();
321 ExplodedNode *pred = builder.getPredecessor();
323 const StackFrameContext *stackFrame = cast<StackFrameContext>(pred->getLocationContext());
324 const CXXConstructorDecl *decl = cast<CXXConstructorDecl>(stackFrame->getDecl());
325 const CXXThisRegion *thisReg = getCXXThisRegion(decl, stackFrame);
327 SVal thisVal = pred->getState()->getSVal(thisReg);
329 if (BMI->isAnyMemberInitializer()) {
332 // Evaluate the initializer.
333 Visit(BMI->getInit(), pred, Dst);
335 for (ExplodedNodeSet::iterator I = Dst.begin(), E = Dst.end(); I != E; ++I){
336 ExplodedNode *Pred = *I;
337 const GRState *state = Pred->getState();
339 const FieldDecl *FD = BMI->getAnyMember();
341 SVal FieldLoc = state->getLValue(FD, thisVal);
342 SVal InitVal = state->getSVal(BMI->getInit());
343 state = state->bindLoc(FieldLoc, InitVal);
345 // Use a custom node building process.
346 PostInitializer PP(BMI, stackFrame);
347 // Builder automatically add the generated node to the deferred set,
348 // which are processed in the builder's dtor.
349 builder.generateNode(PP, state, Pred);
354 assert(BMI->isBaseInitializer());
356 // Get the base class declaration.
357 const CXXConstructExpr *ctorExpr = cast<CXXConstructExpr>(BMI->getInit());
359 // Create the base object region.
361 getStoreManager().evalDerivedToBase(thisVal, ctorExpr->getType());
362 const MemRegion *baseReg = baseVal.getAsRegion();
366 VisitCXXConstructExpr(ctorExpr, baseReg, pred, dst);
369 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
370 StmtNodeBuilder &builder) {
373 switch (D.getKind()) {
374 case CFGElement::AutomaticObjectDtor:
375 ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), builder);
377 case CFGElement::BaseDtor:
378 ProcessBaseDtor(cast<CFGBaseDtor>(D), builder);
380 case CFGElement::MemberDtor:
381 ProcessMemberDtor(cast<CFGMemberDtor>(D), builder);
383 case CFGElement::TemporaryDtor:
384 ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), builder);
387 llvm_unreachable("Unexpected dtor kind.");
391 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor dtor,
392 StmtNodeBuilder &builder) {
393 ExplodedNode *pred = builder.getPredecessor();
394 const GRState *state = pred->getState();
395 const VarDecl *varDecl = dtor.getVarDecl();
397 QualType varType = varDecl->getType();
399 if (const ReferenceType *refType = varType->getAs<ReferenceType>())
400 varType = refType->getPointeeType();
402 const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl();
403 assert(recordDecl && "get CXXRecordDecl fail");
404 const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor();
406 Loc dest = state->getLValue(varDecl, pred->getLocationContext());
408 ExplodedNodeSet dstSet;
409 VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(),
410 dtor.getTriggerStmt(), pred, dstSet);
413 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
414 StmtNodeBuilder &builder) {
417 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
418 StmtNodeBuilder &builder) {
421 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
422 StmtNodeBuilder &builder) {
425 void ExprEngine::Visit(const Stmt* S, ExplodedNode* Pred,
426 ExplodedNodeSet& Dst) {
427 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
429 "Error evaluating statement");
431 // Expressions to ignore.
432 if (const Expr *Ex = dyn_cast<Expr>(S))
433 S = Ex->IgnoreParens();
435 // FIXME: add metadata to the CFG so that we can disable
436 // this check when we KNOW that there is no block-level subexpression.
437 // The motivation is that this check requires a hashtable lookup.
439 if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) {
444 switch (S->getStmtClass()) {
445 // C++ and ARC stuff we don't support yet.
446 case Expr::ObjCIndirectCopyRestoreExprClass:
447 case Stmt::CXXBindTemporaryExprClass:
448 case Stmt::CXXCatchStmtClass:
449 case Stmt::CXXDependentScopeMemberExprClass:
450 case Stmt::CXXForRangeStmtClass:
451 case Stmt::CXXPseudoDestructorExprClass:
452 case Stmt::CXXTemporaryObjectExprClass:
453 case Stmt::CXXThrowExprClass:
454 case Stmt::CXXTryStmtClass:
455 case Stmt::CXXTypeidExprClass:
456 case Stmt::CXXUuidofExprClass:
457 case Stmt::CXXUnresolvedConstructExprClass:
458 case Stmt::CXXScalarValueInitExprClass:
459 case Stmt::DependentScopeDeclRefExprClass:
460 case Stmt::UnaryTypeTraitExprClass:
461 case Stmt::BinaryTypeTraitExprClass:
462 case Stmt::ArrayTypeTraitExprClass:
463 case Stmt::ExpressionTraitExprClass:
464 case Stmt::UnresolvedLookupExprClass:
465 case Stmt::UnresolvedMemberExprClass:
466 case Stmt::CXXNoexceptExprClass:
467 case Stmt::PackExpansionExprClass:
468 case Stmt::SubstNonTypeTemplateParmPackExprClass:
469 case Stmt::SEHTryStmtClass:
470 case Stmt::SEHExceptStmtClass:
471 case Stmt::SEHFinallyStmtClass:
473 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
474 Builder->BuildSinks = true;
475 const ExplodedNode *node = MakeNode(Dst, S, Pred, GetState(Pred));
476 Engine.addAbortedBlock(node, Builder->getBlock());
480 // We don't handle default arguments either yet, but we can fake it
481 // for now by just skipping them.
482 case Stmt::SubstNonTypeTemplateParmExprClass:
483 case Stmt::CXXDefaultArgExprClass: {
488 case Stmt::ParenExprClass:
489 llvm_unreachable("ParenExprs already handled.");
490 case Stmt::GenericSelectionExprClass:
491 llvm_unreachable("GenericSelectionExprs already handled.");
492 // Cases that should never be evaluated simply because they shouldn't
493 // appear in the CFG.
494 case Stmt::BreakStmtClass:
495 case Stmt::CaseStmtClass:
496 case Stmt::CompoundStmtClass:
497 case Stmt::ContinueStmtClass:
498 case Stmt::DefaultStmtClass:
499 case Stmt::DoStmtClass:
500 case Stmt::ForStmtClass:
501 case Stmt::GotoStmtClass:
502 case Stmt::IfStmtClass:
503 case Stmt::IndirectGotoStmtClass:
504 case Stmt::LabelStmtClass:
505 case Stmt::NoStmtClass:
506 case Stmt::NullStmtClass:
507 case Stmt::SwitchStmtClass:
508 case Stmt::WhileStmtClass:
509 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
512 case Stmt::GNUNullExprClass: {
513 // GNU __null is a pointer-width integer, not an actual pointer.
514 const GRState *state = GetState(Pred);
515 state = state->BindExpr(S, svalBuilder.makeIntValWithPtrWidth(0, false));
516 MakeNode(Dst, S, Pred, state);
520 case Stmt::ObjCAtSynchronizedStmtClass:
521 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
524 case Stmt::ObjCPropertyRefExprClass:
525 VisitObjCPropertyRefExpr(cast<ObjCPropertyRefExpr>(S), Pred, Dst);
528 case Stmt::ImplicitValueInitExprClass: {
529 const GRState *state = GetState(Pred);
530 QualType ty = cast<ImplicitValueInitExpr>(S)->getType();
531 SVal val = svalBuilder.makeZeroVal(ty);
532 MakeNode(Dst, S, Pred, state->BindExpr(S, val));
536 case Stmt::ExprWithCleanupsClass: {
537 Visit(cast<ExprWithCleanups>(S)->getSubExpr(), Pred, Dst);
541 // Cases not handled yet; but will handle some day.
542 case Stmt::DesignatedInitExprClass:
543 case Stmt::ExtVectorElementExprClass:
544 case Stmt::ImaginaryLiteralClass:
545 case Stmt::ObjCAtCatchStmtClass:
546 case Stmt::ObjCAtFinallyStmtClass:
547 case Stmt::ObjCAtTryStmtClass:
548 case Stmt::ObjCAutoreleasePoolStmtClass:
549 case Stmt::ObjCEncodeExprClass:
550 case Stmt::ObjCIsaExprClass:
551 case Stmt::ObjCProtocolExprClass:
552 case Stmt::ObjCSelectorExprClass:
553 case Stmt::ObjCStringLiteralClass:
554 case Stmt::ParenListExprClass:
555 case Stmt::PredefinedExprClass:
556 case Stmt::ShuffleVectorExprClass:
557 case Stmt::VAArgExprClass:
558 case Stmt::CUDAKernelCallExprClass:
559 case Stmt::OpaqueValueExprClass:
560 case Stmt::AsTypeExprClass:
563 // Cases we intentionally don't evaluate, since they don't need
564 // to be explicitly evaluated.
565 case Stmt::AddrLabelExprClass:
566 case Stmt::IntegerLiteralClass:
567 case Stmt::CharacterLiteralClass:
568 case Stmt::CXXBoolLiteralExprClass:
569 case Stmt::FloatingLiteralClass:
570 case Stmt::SizeOfPackExprClass:
571 case Stmt::CXXNullPtrLiteralExprClass:
572 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
575 case Stmt::ArraySubscriptExprClass:
576 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
579 case Stmt::AsmStmtClass:
580 VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst);
583 case Stmt::BlockDeclRefExprClass: {
584 const BlockDeclRefExpr *BE = cast<BlockDeclRefExpr>(S);
585 VisitCommonDeclRefExpr(BE, BE->getDecl(), Pred, Dst);
589 case Stmt::BlockExprClass:
590 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
593 case Stmt::BinaryOperatorClass: {
594 const BinaryOperator* B = cast<BinaryOperator>(S);
595 if (B->isLogicalOp()) {
596 VisitLogicalExpr(B, Pred, Dst);
599 else if (B->getOpcode() == BO_Comma) {
600 const GRState* state = GetState(Pred);
601 MakeNode(Dst, B, Pred, state->BindExpr(B, state->getSVal(B->getRHS())));
605 if (AMgr.shouldEagerlyAssume() &&
606 (B->isRelationalOp() || B->isEqualityOp())) {
608 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
609 evalEagerlyAssume(Dst, Tmp, cast<Expr>(S));
612 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
617 case Stmt::CallExprClass:
618 case Stmt::CXXOperatorCallExprClass:
619 case Stmt::CXXMemberCallExprClass: {
620 VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
624 case Stmt::CXXConstructExprClass: {
625 const CXXConstructExpr *C = cast<CXXConstructExpr>(S);
626 // For block-level CXXConstructExpr, we don't have a destination region.
627 // Let VisitCXXConstructExpr() create one.
628 VisitCXXConstructExpr(C, 0, Pred, Dst);
632 case Stmt::CXXNewExprClass: {
633 const CXXNewExpr *NE = cast<CXXNewExpr>(S);
634 VisitCXXNewExpr(NE, Pred, Dst);
638 case Stmt::CXXDeleteExprClass: {
639 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S);
640 VisitCXXDeleteExpr(CDE, Pred, Dst);
643 // FIXME: ChooseExpr is really a constant. We need to fix
644 // the CFG do not model them as explicit control-flow.
646 case Stmt::ChooseExprClass: { // __builtin_choose_expr
647 const ChooseExpr* C = cast<ChooseExpr>(S);
648 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
652 case Stmt::CompoundAssignOperatorClass:
653 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
656 case Stmt::CompoundLiteralExprClass:
657 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
660 case Stmt::BinaryConditionalOperatorClass:
661 case Stmt::ConditionalOperatorClass: { // '?' operator
662 const AbstractConditionalOperator *C
663 = cast<AbstractConditionalOperator>(S);
664 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
668 case Stmt::CXXThisExprClass:
669 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
672 case Stmt::DeclRefExprClass: {
673 const DeclRefExpr *DE = cast<DeclRefExpr>(S);
674 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
678 case Stmt::DeclStmtClass:
679 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
682 case Stmt::ImplicitCastExprClass:
683 case Stmt::CStyleCastExprClass:
684 case Stmt::CXXStaticCastExprClass:
685 case Stmt::CXXDynamicCastExprClass:
686 case Stmt::CXXReinterpretCastExprClass:
687 case Stmt::CXXConstCastExprClass:
688 case Stmt::CXXFunctionalCastExprClass:
689 case Stmt::ObjCBridgedCastExprClass: {
690 const CastExpr* C = cast<CastExpr>(S);
691 // Handle the previsit checks.
692 ExplodedNodeSet dstPrevisit;
693 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this);
695 // Handle the expression itself.
696 ExplodedNodeSet dstExpr;
697 for (ExplodedNodeSet::iterator i = dstPrevisit.begin(),
698 e = dstPrevisit.end(); i != e ; ++i) {
699 VisitCast(C, C->getSubExpr(), *i, dstExpr);
702 // Handle the postvisit checks.
703 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
707 case Expr::MaterializeTemporaryExprClass: {
708 const MaterializeTemporaryExpr *Materialize
709 = cast<MaterializeTemporaryExpr>(S);
710 if (!Materialize->getType()->isRecordType())
711 CreateCXXTemporaryObject(Materialize->GetTemporaryExpr(), Pred, Dst);
713 Visit(Materialize->GetTemporaryExpr(), Pred, Dst);
717 case Stmt::InitListExprClass:
718 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
721 case Stmt::MemberExprClass:
722 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
724 case Stmt::ObjCIvarRefExprClass:
725 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
728 case Stmt::ObjCForCollectionStmtClass:
729 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
732 case Stmt::ObjCMessageExprClass:
733 VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), Pred, Dst);
736 case Stmt::ObjCAtThrowStmtClass: {
737 // FIXME: This is not complete. We basically treat @throw as
739 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
740 Builder->BuildSinks = true;
741 MakeNode(Dst, S, Pred, GetState(Pred));
745 case Stmt::ReturnStmtClass:
746 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
749 case Stmt::OffsetOfExprClass:
750 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst);
753 case Stmt::UnaryExprOrTypeTraitExprClass:
754 VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
758 case Stmt::StmtExprClass: {
759 const StmtExpr* SE = cast<StmtExpr>(S);
761 if (SE->getSubStmt()->body_empty()) {
762 // Empty statement expression.
763 assert(SE->getType() == getContext().VoidTy
764 && "Empty statement expression must have void type.");
769 if (Expr* LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
770 const GRState* state = GetState(Pred);
771 MakeNode(Dst, SE, Pred, state->BindExpr(SE, state->getSVal(LastExpr)));
779 case Stmt::StringLiteralClass: {
780 const GRState* state = GetState(Pred);
781 SVal V = state->getLValue(cast<StringLiteral>(S));
782 MakeNode(Dst, S, Pred, state->BindExpr(S, V));
786 case Stmt::UnaryOperatorClass: {
787 const UnaryOperator *U = cast<UnaryOperator>(S);
788 if (AMgr.shouldEagerlyAssume()&&(U->getOpcode() == UO_LNot)) {
790 VisitUnaryOperator(U, Pred, Tmp);
791 evalEagerlyAssume(Dst, Tmp, U);
794 VisitUnaryOperator(U, Pred, Dst);
800 //===----------------------------------------------------------------------===//
801 // Block entrance. (Update counters).
802 //===----------------------------------------------------------------------===//
804 void ExprEngine::processCFGBlockEntrance(ExplodedNodeSet &dstNodes,
805 GenericNodeBuilder<BlockEntrance> &nodeBuilder){
807 // FIXME: Refactor this into a checker.
808 const CFGBlock *block = nodeBuilder.getProgramPoint().getBlock();
809 ExplodedNode *pred = nodeBuilder.getPredecessor();
811 if (nodeBuilder.getBlockCounter().getNumVisited(
812 pred->getLocationContext()->getCurrentStackFrame(),
813 block->getBlockID()) >= AMgr.getMaxVisit()) {
816 nodeBuilder.generateNode(pred->getState(), pred, &tag, true);
820 //===----------------------------------------------------------------------===//
821 // Generic node creation.
822 //===----------------------------------------------------------------------===//
824 ExplodedNode* ExprEngine::MakeNode(ExplodedNodeSet& Dst, const Stmt* S,
825 ExplodedNode* Pred, const GRState* St,
826 ProgramPoint::Kind K, const void *tag) {
827 assert (Builder && "StmtNodeBuilder not present.");
828 SaveAndRestore<const void*> OldTag(Builder->Tag);
830 return Builder->MakeNode(Dst, S, Pred, St, K);
833 //===----------------------------------------------------------------------===//
834 // Branch processing.
835 //===----------------------------------------------------------------------===//
837 const GRState* ExprEngine::MarkBranch(const GRState* state,
838 const Stmt* Terminator,
841 switch (Terminator->getStmtClass()) {
845 case Stmt::BinaryOperatorClass: { // '&&' and '||'
847 const BinaryOperator* B = cast<BinaryOperator>(Terminator);
848 BinaryOperator::Opcode Op = B->getOpcode();
850 assert (Op == BO_LAnd || Op == BO_LOr);
852 // For &&, if we take the true branch, then the value of the whole
853 // expression is that of the RHS expression.
855 // For ||, if we take the false branch, then the value of the whole
856 // expression is that of the RHS expression.
858 const Expr* Ex = (Op == BO_LAnd && branchTaken) ||
859 (Op == BO_LOr && !branchTaken)
860 ? B->getRHS() : B->getLHS();
862 return state->BindExpr(B, UndefinedVal(Ex));
865 case Stmt::BinaryConditionalOperatorClass:
866 case Stmt::ConditionalOperatorClass: { // ?:
867 const AbstractConditionalOperator* C
868 = cast<AbstractConditionalOperator>(Terminator);
870 // For ?, if branchTaken == true then the value is either the LHS or
871 // the condition itself. (GNU extension).
876 Ex = C->getTrueExpr();
878 Ex = C->getFalseExpr();
880 return state->BindExpr(C, UndefinedVal(Ex));
883 case Stmt::ChooseExprClass: { // ?:
885 const ChooseExpr* C = cast<ChooseExpr>(Terminator);
887 const Expr* Ex = branchTaken ? C->getLHS() : C->getRHS();
888 return state->BindExpr(C, UndefinedVal(Ex));
893 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
894 /// to try to recover some path-sensitivity for casts of symbolic
895 /// integers that promote their values (which are currently not tracked well).
896 /// This function returns the SVal bound to Condition->IgnoreCasts if all the
897 // cast(s) did was sign-extend the original value.
898 static SVal RecoverCastedSymbol(GRStateManager& StateMgr, const GRState* state,
899 const Stmt* Condition, ASTContext& Ctx) {
901 const Expr *Ex = dyn_cast<Expr>(Condition);
906 bool bitsInit = false;
908 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
909 QualType T = CE->getType();
911 if (!T->isIntegerType())
914 uint64_t newBits = Ctx.getTypeSize(T);
915 if (!bitsInit || newBits < bits) {
920 Ex = CE->getSubExpr();
923 // We reached a non-cast. Is it a symbolic value?
924 QualType T = Ex->getType();
926 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits)
929 return state->getSVal(Ex);
932 void ExprEngine::processBranch(const Stmt* Condition, const Stmt* Term,
933 BranchNodeBuilder& builder) {
935 // Check for NULL conditions; e.g. "for(;;)"
937 builder.markInfeasible(false);
941 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
942 Condition->getLocStart(),
943 "Error evaluating branch");
945 getCheckerManager().runCheckersForBranchCondition(Condition, builder, *this);
947 // If the branch condition is undefined, return;
948 if (!builder.isFeasible(true) && !builder.isFeasible(false))
951 const GRState* PrevState = builder.getState();
952 SVal X = PrevState->getSVal(Condition);
954 if (X.isUnknownOrUndef()) {
955 // Give it a chance to recover from unknown.
956 if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
957 if (Ex->getType()->isIntegerType()) {
958 // Try to recover some path-sensitivity. Right now casts of symbolic
959 // integers that promote their values are currently not tracked well.
960 // If 'Condition' is such an expression, try and recover the
961 // underlying value and use that instead.
962 SVal recovered = RecoverCastedSymbol(getStateManager(),
963 builder.getState(), Condition,
966 if (!recovered.isUnknown()) {
971 // If the condition is still unknown, give up.
972 if (X.isUnknownOrUndef()) {
973 builder.generateNode(MarkBranch(PrevState, Term, true), true);
974 builder.generateNode(MarkBranch(PrevState, Term, false), false);
979 DefinedSVal V = cast<DefinedSVal>(X);
981 // Process the true branch.
982 if (builder.isFeasible(true)) {
983 if (const GRState *state = PrevState->assume(V, true))
984 builder.generateNode(MarkBranch(state, Term, true), true);
986 builder.markInfeasible(true);
989 // Process the false branch.
990 if (builder.isFeasible(false)) {
991 if (const GRState *state = PrevState->assume(V, false))
992 builder.generateNode(MarkBranch(state, Term, false), false);
994 builder.markInfeasible(false);
998 /// processIndirectGoto - Called by CoreEngine. Used to generate successor
999 /// nodes by processing the 'effects' of a computed goto jump.
1000 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
1002 const GRState *state = builder.getState();
1003 SVal V = state->getSVal(builder.getTarget());
1005 // Three possibilities:
1007 // (1) We know the computed label.
1008 // (2) The label is NULL (or some other constant), or Undefined.
1009 // (3) We have no clue about the label. Dispatch to all targets.
1012 typedef IndirectGotoNodeBuilder::iterator iterator;
1014 if (isa<loc::GotoLabel>(V)) {
1015 const LabelDecl *L = cast<loc::GotoLabel>(V).getLabel();
1017 for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
1018 if (I.getLabel() == L) {
1019 builder.generateNode(I, state);
1024 assert(false && "No block with label.");
1028 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
1029 // Dispatch to the first target and mark it as a sink.
1030 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1031 // FIXME: add checker visit.
1032 // UndefBranches.insert(N);
1036 // This is really a catch-all. We don't support symbolics yet.
1037 // FIXME: Implement dispatch for symbolic pointers.
1039 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
1040 builder.generateNode(I, state);
1044 void ExprEngine::VisitGuardedExpr(const Expr* Ex, const Expr* L,
1046 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
1048 assert(Ex == currentStmt &&
1049 Pred->getLocationContext()->getCFG()->isBlkExpr(Ex));
1051 const GRState* state = GetState(Pred);
1052 SVal X = state->getSVal(Ex);
1054 assert (X.isUndef());
1056 const Expr *SE = (Expr*) cast<UndefinedVal>(X).getData();
1058 X = state->getSVal(SE);
1060 // Make sure that we invalidate the previous binding.
1061 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, X, true));
1064 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
1065 /// nodes when the control reaches the end of a function.
1066 void ExprEngine::processEndOfFunction(EndOfFunctionNodeBuilder& builder) {
1067 getTF().evalEndPath(*this, builder);
1068 StateMgr.EndPath(builder.getState());
1069 getCheckerManager().runCheckersForEndPath(builder, *this);
1072 /// ProcessSwitch - Called by CoreEngine. Used to generate successor
1073 /// nodes by processing the 'effects' of a switch statement.
1074 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
1075 typedef SwitchNodeBuilder::iterator iterator;
1076 const GRState* state = builder.getState();
1077 const Expr* CondE = builder.getCondition();
1078 SVal CondV_untested = state->getSVal(CondE);
1080 if (CondV_untested.isUndef()) {
1081 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1082 // FIXME: add checker
1083 //UndefBranches.insert(N);
1087 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested);
1089 const GRState *DefaultSt = state;
1091 iterator I = builder.begin(), EI = builder.end();
1092 bool defaultIsFeasible = I == EI;
1094 for ( ; I != EI; ++I) {
1095 // Successor may be pruned out during CFG construction.
1099 const CaseStmt* Case = I.getCase();
1101 // Evaluate the LHS of the case value.
1102 Expr::EvalResult V1;
1103 bool b = Case->getLHS()->Evaluate(V1, getContext());
1105 // Sanity checks. These go away in Release builds.
1106 assert(b && V1.Val.isInt() && !V1.HasSideEffects
1107 && "Case condition must evaluate to an integer constant.");
1108 (void)b; // silence unused variable warning
1109 assert(V1.Val.getInt().getBitWidth() ==
1110 getContext().getTypeSize(CondE->getType()));
1112 // Get the RHS of the case, if it exists.
1113 Expr::EvalResult V2;
1115 if (const Expr* E = Case->getRHS()) {
1116 b = E->Evaluate(V2, getContext());
1117 assert(b && V2.Val.isInt() && !V2.HasSideEffects
1118 && "Case condition must evaluate to an integer constant.");
1119 (void)b; // silence unused variable warning
1124 // FIXME: Eventually we should replace the logic below with a range
1125 // comparison, rather than concretize the values within the range.
1126 // This should be easy once we have "ranges" for NonLVals.
1129 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1.Val.getInt()));
1130 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
1133 // Now "assume" that the case matches.
1134 if (const GRState* stateNew = state->assume(Res, true)) {
1135 builder.generateCaseStmtNode(I, stateNew);
1137 // If CondV evaluates to a constant, then we know that this
1138 // is the *only* case that we can take, so stop evaluating the
1140 if (isa<nonloc::ConcreteInt>(CondV))
1144 // Now "assume" that the case doesn't match. Add this state
1145 // to the default state (if it is feasible).
1147 if (const GRState *stateNew = DefaultSt->assume(Res, false)) {
1148 defaultIsFeasible = true;
1149 DefaultSt = stateNew;
1152 defaultIsFeasible = false;
1157 // Concretize the next value in the range.
1158 if (V1.Val.getInt() == V2.Val.getInt())
1162 assert (V1.Val.getInt() <= V2.Val.getInt());
1167 if (!defaultIsFeasible)
1170 // If we have switch(enum value), the default branch is not
1171 // feasible if all of the enum constants not covered by 'case:' statements
1172 // are not feasible values for the switch condition.
1174 // Note that this isn't as accurate as it could be. Even if there isn't
1175 // a case for a particular enum value as long as that enum value isn't
1176 // feasible then it shouldn't be considered for making 'default:' reachable.
1177 const SwitchStmt *SS = builder.getSwitch();
1178 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1179 if (CondExpr->getType()->getAs<EnumType>()) {
1180 if (SS->isAllEnumCasesCovered())
1184 builder.generateDefaultCaseNode(DefaultSt);
1187 void ExprEngine::processCallEnter(CallEnterNodeBuilder &B) {
1188 const GRState *state = B.getState()->enterStackFrame(B.getCalleeContext());
1189 B.generateNode(state);
1192 void ExprEngine::processCallExit(CallExitNodeBuilder &B) {
1193 const GRState *state = B.getState();
1194 const ExplodedNode *Pred = B.getPredecessor();
1195 const StackFrameContext *calleeCtx =
1196 cast<StackFrameContext>(Pred->getLocationContext());
1197 const Stmt *CE = calleeCtx->getCallSite();
1199 // If the callee returns an expression, bind its value to CallExpr.
1200 const Stmt *ReturnedExpr = state->get<ReturnExpr>();
1202 SVal RetVal = state->getSVal(ReturnedExpr);
1203 state = state->BindExpr(CE, RetVal);
1204 // Clear the return expr GDM.
1205 state = state->remove<ReturnExpr>();
1208 // Bind the constructed object value to CXXConstructExpr.
1209 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
1210 const CXXThisRegion *ThisR =
1211 getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx);
1213 SVal ThisV = state->getSVal(ThisR);
1214 // Always bind the region to the CXXConstructExpr.
1215 state = state->BindExpr(CCE, ThisV);
1218 B.generateNode(state);
1221 //===----------------------------------------------------------------------===//
1222 // Transfer functions: logical operations ('&&', '||').
1223 //===----------------------------------------------------------------------===//
1225 void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode* Pred,
1226 ExplodedNodeSet& Dst) {
1228 assert(B->getOpcode() == BO_LAnd ||
1229 B->getOpcode() == BO_LOr);
1231 assert(B==currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(B));
1233 const GRState* state = GetState(Pred);
1234 SVal X = state->getSVal(B);
1235 assert(X.isUndef());
1237 const Expr *Ex = (const Expr*) cast<UndefinedVal>(X).getData();
1240 if (Ex == B->getRHS()) {
1241 X = state->getSVal(Ex);
1243 // Handle undefined values.
1245 MakeNode(Dst, B, Pred, state->BindExpr(B, X));
1249 DefinedOrUnknownSVal XD = cast<DefinedOrUnknownSVal>(X);
1251 // We took the RHS. Because the value of the '&&' or '||' expression must
1252 // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
1253 // or 1. Alternatively, we could take a lazy approach, and calculate this
1254 // value later when necessary. We don't have the machinery in place for
1255 // this right now, and since most logical expressions are used for branches,
1256 // the payoff is not likely to be large. Instead, we do eager evaluation.
1257 if (const GRState *newState = state->assume(XD, true))
1258 MakeNode(Dst, B, Pred,
1259 newState->BindExpr(B, svalBuilder.makeIntVal(1U, B->getType())));
1261 if (const GRState *newState = state->assume(XD, false))
1262 MakeNode(Dst, B, Pred,
1263 newState->BindExpr(B, svalBuilder.makeIntVal(0U, B->getType())));
1266 // We took the LHS expression. Depending on whether we are '&&' or
1267 // '||' we know what the value of the expression is via properties of
1268 // the short-circuiting.
1269 X = svalBuilder.makeIntVal(B->getOpcode() == BO_LAnd ? 0U : 1U,
1271 MakeNode(Dst, B, Pred, state->BindExpr(B, X));
1275 //===----------------------------------------------------------------------===//
1276 // Transfer functions: Loads and stores.
1277 //===----------------------------------------------------------------------===//
1279 void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
1280 ExplodedNodeSet &Dst) {
1282 ExplodedNodeSet Tmp;
1284 CanQualType T = getContext().getCanonicalType(BE->getType());
1285 SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T,
1286 Pred->getLocationContext());
1288 MakeNode(Tmp, BE, Pred, GetState(Pred)->BindExpr(BE, V),
1289 ProgramPoint::PostLValueKind);
1291 // Post-visit the BlockExpr.
1292 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this);
1295 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
1297 ExplodedNodeSet &Dst) {
1298 const GRState *state = GetState(Pred);
1300 if (const VarDecl* VD = dyn_cast<VarDecl>(D)) {
1301 assert(Ex->isLValue());
1302 SVal V = state->getLValue(VD, Pred->getLocationContext());
1304 // For references, the 'lvalue' is the pointer address stored in the
1305 // reference region.
1306 if (VD->getType()->isReferenceType()) {
1307 if (const MemRegion *R = V.getAsRegion())
1308 V = state->getSVal(R);
1313 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V),
1314 ProgramPoint::PostLValueKind);
1317 if (const EnumConstantDecl* ED = dyn_cast<EnumConstantDecl>(D)) {
1318 assert(!Ex->isLValue());
1319 SVal V = svalBuilder.makeIntVal(ED->getInitVal());
1320 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V));
1323 if (const FunctionDecl* FD = dyn_cast<FunctionDecl>(D)) {
1324 SVal V = svalBuilder.getFunctionPointer(FD);
1325 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V),
1326 ProgramPoint::PostLValueKind);
1330 "ValueDecl support for this ValueDecl not implemented.");
1333 /// VisitArraySubscriptExpr - Transfer function for array accesses
1334 void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr* A,
1336 ExplodedNodeSet& Dst){
1338 const Expr* Base = A->getBase()->IgnoreParens();
1339 const Expr* Idx = A->getIdx()->IgnoreParens();
1341 // Evaluate the base.
1342 ExplodedNodeSet Tmp;
1343 Visit(Base, Pred, Tmp);
1345 for (ExplodedNodeSet::iterator I1=Tmp.begin(), E1=Tmp.end(); I1!=E1; ++I1) {
1346 ExplodedNodeSet Tmp2;
1347 Visit(Idx, *I1, Tmp2); // Evaluate the index.
1348 ExplodedNodeSet Tmp3;
1349 getCheckerManager().runCheckersForPreStmt(Tmp3, Tmp2, A, *this);
1351 for (ExplodedNodeSet::iterator I2=Tmp3.begin(),E2=Tmp3.end();I2!=E2; ++I2) {
1352 const GRState* state = GetState(*I2);
1353 SVal V = state->getLValue(A->getType(), state->getSVal(Idx),
1354 state->getSVal(Base));
1355 assert(A->isLValue());
1356 MakeNode(Dst, A, *I2, state->BindExpr(A, V), ProgramPoint::PostLValueKind);
1361 /// VisitMemberExpr - Transfer function for member expressions.
1362 void ExprEngine::VisitMemberExpr(const MemberExpr* M, ExplodedNode* Pred,
1363 ExplodedNodeSet& Dst) {
1365 Expr *baseExpr = M->getBase()->IgnoreParens();
1366 ExplodedNodeSet dstBase;
1367 Visit(baseExpr, Pred, dstBase);
1369 FieldDecl *field = dyn_cast<FieldDecl>(M->getMemberDecl());
1370 if (!field) // FIXME: skipping member expressions for non-fields
1373 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end();
1375 const GRState* state = GetState(*I);
1376 SVal baseExprVal = state->getSVal(baseExpr);
1377 if (isa<nonloc::LazyCompoundVal>(baseExprVal) ||
1378 isa<nonloc::CompoundVal>(baseExprVal) ||
1379 // FIXME: This can originate by conjuring a symbol for an unknown
1380 // temporary struct object, see test/Analysis/fields.c:
1382 isa<nonloc::SymbolVal>(baseExprVal)) {
1383 MakeNode(Dst, M, *I, state->BindExpr(M, UnknownVal()));
1387 // FIXME: Should we insert some assumption logic in here to determine
1388 // if "Base" is a valid piece of memory? Before we put this assumption
1389 // later when using FieldOffset lvals (which we no longer have).
1391 // For all other cases, compute an lvalue.
1392 SVal L = state->getLValue(field, baseExprVal);
1394 MakeNode(Dst, M, *I, state->BindExpr(M, L), ProgramPoint::PostLValueKind);
1396 evalLoad(Dst, M, *I, state, L);
1400 /// evalBind - Handle the semantics of binding a value to a specific location.
1401 /// This method is used by evalStore and (soon) VisitDeclStmt, and others.
1402 void ExprEngine::evalBind(ExplodedNodeSet& Dst, const Stmt* StoreE,
1403 ExplodedNode* Pred, const GRState* state,
1404 SVal location, SVal Val, bool atDeclInit) {
1407 // Do a previsit of the bind.
1408 ExplodedNodeSet CheckedSet, Src;
1410 getCheckerManager().runCheckersForBind(CheckedSet, Src, location, Val, StoreE,
1413 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1417 state = GetState(*I);
1419 const GRState* newState = 0;
1422 const VarRegion *VR =
1423 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion());
1425 newState = state->bindDecl(VR, Val);
1428 if (location.isUnknown()) {
1429 // We know that the new state will be the same as the old state since
1430 // the location of the binding is "unknown". Consequently, there
1431 // is no reason to just create a new node.
1435 // We are binding to a value other than 'unknown'. Perform the binding
1436 // using the StoreManager.
1437 newState = state->bindLoc(cast<Loc>(location), Val);
1441 // The next thing to do is check if the TransferFuncs object wants to
1442 // update the state based on the new binding. If the GRTransferFunc object
1443 // doesn't do anything, just auto-propagate the current state.
1445 // NOTE: We use 'AssignE' for the location of the PostStore if 'AssignE'
1446 // is non-NULL. Checkers typically care about
1448 StmtNodeBuilderRef BuilderRef(Dst, *Builder, *this, *I, newState, StoreE,
1451 getTF().evalBind(BuilderRef, location, Val);
1455 /// evalStore - Handle the semantics of a store via an assignment.
1456 /// @param Dst The node set to store generated state nodes
1457 /// @param AssignE The assignment expression if the store happens in an
1459 /// @param LocatioinE The location expression that is stored to.
1460 /// @param state The current simulation state
1461 /// @param location The location to store the value
1462 /// @param Val The value to be stored
1463 void ExprEngine::evalStore(ExplodedNodeSet& Dst, const Expr *AssignE,
1464 const Expr* LocationE,
1466 const GRState* state, SVal location, SVal Val,
1469 assert(Builder && "StmtNodeBuilder must be defined.");
1471 // Proceed with the store. We use AssignE as the anchor for the PostStore
1472 // ProgramPoint if it is non-NULL, and LocationE otherwise.
1473 const Expr *StoreE = AssignE ? AssignE : LocationE;
1475 if (isa<loc::ObjCPropRef>(location)) {
1476 loc::ObjCPropRef prop = cast<loc::ObjCPropRef>(location);
1477 ExplodedNodeSet src = Pred;
1478 return VisitObjCMessage(ObjCPropertySetter(prop.getPropRefExpr(),
1479 StoreE, Val), src, Dst);
1482 // Evaluate the location (checks for bad dereferences).
1483 ExplodedNodeSet Tmp;
1484 evalLocation(Tmp, LocationE, Pred, state, location, tag, false);
1489 if (location.isUndef())
1492 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind,
1493 ProgramPoint::PostStoreKind);
1495 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
1496 evalBind(Dst, StoreE, *NI, GetState(*NI), location, Val);
1499 void ExprEngine::evalLoad(ExplodedNodeSet& Dst, const Expr *Ex,
1501 const GRState* state, SVal location,
1502 const void *tag, QualType LoadTy) {
1503 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");
1505 if (isa<loc::ObjCPropRef>(location)) {
1506 loc::ObjCPropRef prop = cast<loc::ObjCPropRef>(location);
1507 ExplodedNodeSet src = Pred;
1508 return VisitObjCMessage(ObjCPropertyGetter(prop.getPropRefExpr(), Ex),
1512 // Are we loading from a region? This actually results in two loads; one
1513 // to fetch the address of the referenced value and one to fetch the
1514 // referenced value.
1515 if (const TypedRegion *TR =
1516 dyn_cast_or_null<TypedRegion>(location.getAsRegion())) {
1518 QualType ValTy = TR->getValueType();
1519 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
1520 static int loadReferenceTag = 0;
1521 ExplodedNodeSet Tmp;
1522 evalLoadCommon(Tmp, Ex, Pred, state, location, &loadReferenceTag,
1523 getContext().getPointerType(RT->getPointeeType()));
1525 // Perform the load from the referenced value.
1526 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
1527 state = GetState(*I);
1528 location = state->getSVal(Ex);
1529 evalLoadCommon(Dst, Ex, *I, state, location, tag, LoadTy);
1535 evalLoadCommon(Dst, Ex, Pred, state, location, tag, LoadTy);
1538 void ExprEngine::evalLoadCommon(ExplodedNodeSet& Dst, const Expr *Ex,
1540 const GRState* state, SVal location,
1541 const void *tag, QualType LoadTy) {
1543 // Evaluate the location (checks for bad dereferences).
1544 ExplodedNodeSet Tmp;
1545 evalLocation(Tmp, Ex, Pred, state, location, tag, true);
1550 if (location.isUndef())
1553 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind);
1555 // Proceed with the load.
1556 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1557 state = GetState(*NI);
1559 if (location.isUnknown()) {
1560 // This is important. We must nuke the old binding.
1561 MakeNode(Dst, Ex, *NI, state->BindExpr(Ex, UnknownVal()),
1562 ProgramPoint::PostLoadKind, tag);
1565 if (LoadTy.isNull())
1566 LoadTy = Ex->getType();
1567 SVal V = state->getSVal(cast<Loc>(location), LoadTy);
1568 MakeNode(Dst, Ex, *NI, state->bindExprAndLocation(Ex, location, V),
1569 ProgramPoint::PostLoadKind, tag);
1574 void ExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *S,
1576 const GRState* state, SVal location,
1577 const void *tag, bool isLoad) {
1578 // Early checks for performance reason.
1579 if (location.isUnknown()) {
1584 ExplodedNodeSet Src;
1585 if (Builder->GetState(Pred) == state) {
1588 // Associate this new state with an ExplodedNode.
1589 // FIXME: If I pass null tag, the graph is incorrect, e.g for
1593 // "p = 0" is not noted as "Null pointer value stored to 'p'" but
1594 // instead "int *p" is noted as
1595 // "Variable 'p' initialized to a null pointer value"
1596 ExplodedNode *N = Builder->generateNode(S, state, Pred, this);
1597 Src.Add(N ? N : Pred);
1599 getCheckerManager().runCheckersForLocation(Dst, Src, location, isLoad, S,
1603 bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE,
1604 ExplodedNode *Pred) {
1607 // Inlining isn't correct right now because we:
1608 // (a) don't generate CallExit nodes.
1609 // (b) we need a way to postpone doing post-visits of CallExprs until
1610 // the CallExit. This means we need CallExits for the non-inline
1614 const GRState *state = GetState(Pred);
1615 const Expr *Callee = CE->getCallee();
1616 SVal L = state->getSVal(Callee);
1618 const FunctionDecl *FD = L.getAsFunctionDecl();
1622 // Specially handle CXXMethods.
1623 const CXXMethodDecl *methodDecl = 0;
1625 switch (CE->getStmtClass()) {
1627 case Stmt::CXXOperatorCallExprClass: {
1628 const CXXOperatorCallExpr *opCall = cast<CXXOperatorCallExpr>(CE);
1630 llvm::dyn_cast_or_null<CXXMethodDecl>(opCall->getCalleeDecl());
1633 case Stmt::CXXMemberCallExprClass: {
1634 const CXXMemberCallExpr *memberCall = cast<CXXMemberCallExpr>(CE);
1635 const MemberExpr *memberExpr =
1636 cast<MemberExpr>(memberCall->getCallee()->IgnoreParens());
1637 methodDecl = cast<CXXMethodDecl>(memberExpr->getMemberDecl());
1645 // Check if the function definition is in the same translation unit.
1646 if (FD->hasBody(FD)) {
1647 const StackFrameContext *stackFrame =
1648 AMgr.getStackFrame(AMgr.getAnalysisContext(FD),
1649 Pred->getLocationContext(),
1650 CE, Builder->getBlock(), Builder->getIndex());
1651 // Now we have the definition of the callee, create a CallEnter node.
1652 CallEnter Loc(CE, stackFrame, Pred->getLocationContext());
1654 ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
1659 // Check if we can find the function definition in other translation units.
1660 if (AMgr.hasIndexer()) {
1661 AnalysisContext *C = AMgr.getAnalysisContextInAnotherTU(FD);
1664 const StackFrameContext *stackFrame =
1665 AMgr.getStackFrame(C, Pred->getLocationContext(),
1666 CE, Builder->getBlock(), Builder->getIndex());
1667 CallEnter Loc(CE, stackFrame, Pred->getLocationContext());
1668 ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
1673 // Generate the CallExit node.
1679 void ExprEngine::VisitCallExpr(const CallExpr* CE, ExplodedNode* Pred,
1680 ExplodedNodeSet& dst) {
1682 // Determine the type of function we're calling (if available).
1683 const FunctionProtoType *Proto = NULL;
1684 QualType FnType = CE->getCallee()->IgnoreParens()->getType();
1685 if (const PointerType *FnTypePtr = FnType->getAs<PointerType>())
1686 Proto = FnTypePtr->getPointeeType()->getAs<FunctionProtoType>();
1688 // Should the first argument be evaluated as an lvalue?
1689 bool firstArgumentAsLvalue = false;
1690 switch (CE->getStmtClass()) {
1691 case Stmt::CXXOperatorCallExprClass:
1692 firstArgumentAsLvalue = true;
1698 // Evaluate the arguments.
1699 ExplodedNodeSet dstArgsEvaluated;
1700 evalArguments(CE->arg_begin(), CE->arg_end(), Proto, Pred, dstArgsEvaluated,
1701 firstArgumentAsLvalue);
1703 // Evaluate the callee.
1704 ExplodedNodeSet dstCalleeEvaluated;
1705 evalCallee(CE, dstArgsEvaluated, dstCalleeEvaluated);
1707 // Perform the previsit of the CallExpr.
1708 ExplodedNodeSet dstPreVisit;
1709 getCheckerManager().runCheckersForPreStmt(dstPreVisit, dstCalleeEvaluated,
1712 // Now evaluate the call itself.
1713 class DefaultEval : public GraphExpander {
1718 DefaultEval(ExprEngine &eng, const CallExpr *ce)
1719 : Eng(eng), CE(ce) {}
1720 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) {
1721 // Should we inline the call?
1722 if (Eng.getAnalysisManager().shouldInlineCall() &&
1723 Eng.InlineCall(Dst, CE, Pred)) {
1727 StmtNodeBuilder &Builder = Eng.getBuilder();
1728 assert(&Builder && "StmtNodeBuilder must be defined.");
1730 // Dispatch to the plug-in transfer function.
1731 unsigned oldSize = Dst.size();
1732 SaveOr OldHasGen(Builder.hasGeneratedNode);
1734 // Dispatch to transfer function logic to handle the call itself.
1735 const Expr* Callee = CE->getCallee()->IgnoreParens();
1736 const GRState* state = Eng.GetState(Pred);
1737 SVal L = state->getSVal(Callee);
1738 Eng.getTF().evalCall(Dst, Eng, Builder, CE, L, Pred);
1740 // Handle the case where no nodes where generated. Auto-generate that
1741 // contains the updated state if we aren't generating sinks.
1742 if (!Builder.BuildSinks && Dst.size() == oldSize &&
1743 !Builder.hasGeneratedNode)
1744 Eng.MakeNode(Dst, CE, Pred, state);
1748 // Finally, evaluate the function call. We try each of the checkers
1749 // to see if the can evaluate the function call.
1750 ExplodedNodeSet dstCallEvaluated;
1751 DefaultEval defEval(*this, CE);
1752 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated,
1754 CE, *this, &defEval);
1756 // Finally, perform the post-condition check of the CallExpr and store
1757 // the created nodes in 'Dst'.
1758 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE,
1762 //===----------------------------------------------------------------------===//
1763 // Transfer function: Objective-C dot-syntax to access a property.
1764 //===----------------------------------------------------------------------===//
1766 void ExprEngine::VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *Ex,
1768 ExplodedNodeSet &Dst) {
1769 ExplodedNodeSet dstBase;
1771 // Visit the receiver (if any).
1772 if (Ex->isObjectReceiver())
1773 Visit(Ex->getBase(), Pred, dstBase);
1777 ExplodedNodeSet dstPropRef;
1779 // Using the base, compute the lvalue of the instance variable.
1780 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end();
1782 ExplodedNode *nodeBase = *I;
1783 const GRState *state = GetState(nodeBase);
1784 MakeNode(dstPropRef, Ex, *I, state->BindExpr(Ex, loc::ObjCPropRef(Ex)));
1787 Dst.insert(dstPropRef);
1790 //===----------------------------------------------------------------------===//
1791 // Transfer function: Objective-C ivar references.
1792 //===----------------------------------------------------------------------===//
1794 static std::pair<const void*,const void*> EagerlyAssumeTag
1795 = std::pair<const void*,const void*>(&EagerlyAssumeTag,static_cast<void*>(0));
1797 void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
1799 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
1800 ExplodedNode *Pred = *I;
1802 // Test if the previous node was as the same expression. This can happen
1803 // when the expression fails to evaluate to anything meaningful and
1804 // (as an optimization) we don't generate a node.
1805 ProgramPoint P = Pred->getLocation();
1806 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) {
1811 const GRState* state = GetState(Pred);
1812 SVal V = state->getSVal(Ex);
1813 if (nonloc::SymExprVal *SEV = dyn_cast<nonloc::SymExprVal>(&V)) {
1814 // First assume that the condition is true.
1815 if (const GRState *stateTrue = state->assume(*SEV, true)) {
1816 stateTrue = stateTrue->BindExpr(Ex,
1817 svalBuilder.makeIntVal(1U, Ex->getType()));
1818 Dst.Add(Builder->generateNode(PostStmtCustom(Ex,
1819 &EagerlyAssumeTag, Pred->getLocationContext()),
1823 // Next, assume that the condition is false.
1824 if (const GRState *stateFalse = state->assume(*SEV, false)) {
1825 stateFalse = stateFalse->BindExpr(Ex,
1826 svalBuilder.makeIntVal(0U, Ex->getType()));
1827 Dst.Add(Builder->generateNode(PostStmtCustom(Ex, &EagerlyAssumeTag,
1828 Pred->getLocationContext()),
1837 //===----------------------------------------------------------------------===//
1838 // Transfer function: Objective-C @synchronized.
1839 //===----------------------------------------------------------------------===//
1841 void ExprEngine::VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
1843 ExplodedNodeSet &Dst) {
1845 // The mutex expression is a CFGElement, so we don't need to explicitly
1846 // visit it since it will already be processed.
1848 // Pre-visit the ObjCAtSynchronizedStmt.
1849 ExplodedNodeSet Tmp;
1851 getCheckerManager().runCheckersForPreStmt(Dst, Tmp, S, *this);
1854 //===----------------------------------------------------------------------===//
1855 // Transfer function: Objective-C ivar references.
1856 //===----------------------------------------------------------------------===//
1858 void ExprEngine::VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr* Ex,
1860 ExplodedNodeSet& Dst) {
1862 // Visit the base expression, which is needed for computing the lvalue
1864 ExplodedNodeSet dstBase;
1865 const Expr *baseExpr = Ex->getBase();
1866 Visit(baseExpr, Pred, dstBase);
1868 ExplodedNodeSet dstIvar;
1870 // Using the base, compute the lvalue of the instance variable.
1871 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end();
1873 ExplodedNode *nodeBase = *I;
1874 const GRState *state = GetState(nodeBase);
1875 SVal baseVal = state->getSVal(baseExpr);
1876 SVal location = state->getLValue(Ex->getDecl(), baseVal);
1877 MakeNode(dstIvar, Ex, *I, state->BindExpr(Ex, location));
1880 // Perform the post-condition check of the ObjCIvarRefExpr and store
1881 // the created nodes in 'Dst'.
1882 getCheckerManager().runCheckersForPostStmt(Dst, dstIvar, Ex, *this);
1885 //===----------------------------------------------------------------------===//
1886 // Transfer function: Objective-C fast enumeration 'for' statements.
1887 //===----------------------------------------------------------------------===//
1889 void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt* S,
1890 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
1892 // ObjCForCollectionStmts are processed in two places. This method
1893 // handles the case where an ObjCForCollectionStmt* occurs as one of the
1894 // statements within a basic block. This transfer function does two things:
1896 // (1) binds the next container value to 'element'. This creates a new
1897 // node in the ExplodedGraph.
1899 // (2) binds the value 0/1 to the ObjCForCollectionStmt* itself, indicating
1900 // whether or not the container has any more elements. This value
1901 // will be tested in ProcessBranch. We need to explicitly bind
1902 // this value because a container can contain nil elements.
1904 // FIXME: Eventually this logic should actually do dispatches to
1905 // 'countByEnumeratingWithState:objects:count:' (NSFastEnumeration).
1906 // This will require simulating a temporary NSFastEnumerationState, either
1907 // through an SVal or through the use of MemRegions. This value can
1908 // be affixed to the ObjCForCollectionStmt* instead of 0/1; when the loop
1909 // terminates we reclaim the temporary (it goes out of scope) and we
1910 // we can test if the SVal is 0 or if the MemRegion is null (depending
1911 // on what approach we take).
1913 // For now: simulate (1) by assigning either a symbol or nil if the
1914 // container is empty. Thus this transfer function will by default
1915 // result in state splitting.
1917 const Stmt* elem = S->getElement();
1920 if (const DeclStmt* DS = dyn_cast<DeclStmt>(elem)) {
1921 const VarDecl* ElemD = cast<VarDecl>(DS->getSingleDecl());
1922 assert (ElemD->getInit() == 0);
1923 ElementV = GetState(Pred)->getLValue(ElemD, Pred->getLocationContext());
1924 VisitObjCForCollectionStmtAux(S, Pred, Dst, ElementV);
1928 ExplodedNodeSet Tmp;
1929 Visit(cast<Expr>(elem), Pred, Tmp);
1930 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) {
1931 const GRState* state = GetState(*I);
1932 VisitObjCForCollectionStmtAux(S, *I, Dst, state->getSVal(elem));
1936 void ExprEngine::VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt* S,
1937 ExplodedNode* Pred, ExplodedNodeSet& Dst,
1940 // Check if the location we are writing back to is a null pointer.
1941 const Stmt* elem = S->getElement();
1942 ExplodedNodeSet Tmp;
1943 evalLocation(Tmp, elem, Pred, GetState(Pred), ElementV, NULL, false);
1948 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1950 const GRState *state = GetState(Pred);
1952 // Handle the case where the container still has elements.
1953 SVal TrueV = svalBuilder.makeTruthVal(1);
1954 const GRState *hasElems = state->BindExpr(S, TrueV);
1956 // Handle the case where the container has no elements.
1957 SVal FalseV = svalBuilder.makeTruthVal(0);
1958 const GRState *noElems = state->BindExpr(S, FalseV);
1960 if (loc::MemRegionVal* MV = dyn_cast<loc::MemRegionVal>(&ElementV))
1961 if (const TypedRegion* R = dyn_cast<TypedRegion>(MV->getRegion())) {
1962 // FIXME: The proper thing to do is to really iterate over the
1963 // container. We will do this with dispatch logic to the store.
1964 // For now, just 'conjure' up a symbolic value.
1965 QualType T = R->getValueType();
1966 assert(Loc::isLocType(T));
1967 unsigned Count = Builder->getCurrentBlockCount();
1968 SymbolRef Sym = SymMgr.getConjuredSymbol(elem, T, Count);
1969 SVal V = svalBuilder.makeLoc(Sym);
1970 hasElems = hasElems->bindLoc(ElementV, V);
1972 // Bind the location to 'nil' on the false branch.
1973 SVal nilV = svalBuilder.makeIntVal(0, T);
1974 noElems = noElems->bindLoc(ElementV, nilV);
1977 // Create the new nodes.
1978 MakeNode(Dst, S, Pred, hasElems);
1979 MakeNode(Dst, S, Pred, noElems);
1983 //===----------------------------------------------------------------------===//
1984 // Transfer function: Objective-C message expressions.
1985 //===----------------------------------------------------------------------===//
1988 class ObjCMsgWLItem {
1990 ObjCMessageExpr::const_arg_iterator I;
1993 ObjCMsgWLItem(const ObjCMessageExpr::const_arg_iterator &i, ExplodedNode *n)
1996 } // end anonymous namespace
1998 void ExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr* ME,
2000 ExplodedNodeSet& Dst){
2002 // Create a worklist to process both the arguments.
2003 llvm::SmallVector<ObjCMsgWLItem, 20> WL;
2005 // But first evaluate the receiver (if any).
2006 ObjCMessageExpr::const_arg_iterator AI = ME->arg_begin(), AE = ME->arg_end();
2007 if (const Expr *Receiver = ME->getInstanceReceiver()) {
2008 ExplodedNodeSet Tmp;
2009 Visit(Receiver, Pred, Tmp);
2014 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I)
2015 WL.push_back(ObjCMsgWLItem(AI, *I));
2018 WL.push_back(ObjCMsgWLItem(AI, Pred));
2020 // Evaluate the arguments.
2021 ExplodedNodeSet ArgsEvaluated;
2022 while (!WL.empty()) {
2023 ObjCMsgWLItem Item = WL.back();
2027 ArgsEvaluated.insert(Item.N);
2031 // Evaluate the subexpression.
2032 ExplodedNodeSet Tmp;
2034 // FIXME: [Objective-C++] handle arguments that are references
2035 Visit(*Item.I, Item.N, Tmp);
2037 // Enqueue evaluating the next argument on the worklist.
2039 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
2040 WL.push_back(ObjCMsgWLItem(Item.I, *NI));
2043 // Now that the arguments are processed, handle the ObjC message.
2044 VisitObjCMessage(ME, ArgsEvaluated, Dst);
2047 void ExprEngine::VisitObjCMessage(const ObjCMessage &msg,
2048 ExplodedNodeSet &Src, ExplodedNodeSet& Dst) {
2050 // Handle the previsits checks.
2051 ExplodedNodeSet DstPrevisit;
2052 getCheckerManager().runCheckersForPreObjCMessage(DstPrevisit, Src, msg,*this);
2054 // Proceed with evaluate the message expression.
2055 ExplodedNodeSet dstEval;
2057 for (ExplodedNodeSet::iterator DI = DstPrevisit.begin(),
2058 DE = DstPrevisit.end(); DI != DE; ++DI) {
2060 ExplodedNode *Pred = *DI;
2061 bool RaisesException = false;
2062 unsigned oldSize = dstEval.size();
2063 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
2064 SaveOr OldHasGen(Builder->hasGeneratedNode);
2066 if (const Expr *Receiver = msg.getInstanceReceiver()) {
2067 const GRState *state = GetState(Pred);
2068 SVal recVal = state->getSVal(Receiver);
2069 if (!recVal.isUndef()) {
2070 // Bifurcate the state into nil and non-nil ones.
2071 DefinedOrUnknownSVal receiverVal = cast<DefinedOrUnknownSVal>(recVal);
2073 const GRState *notNilState, *nilState;
2074 llvm::tie(notNilState, nilState) = state->assume(receiverVal);
2076 // There are three cases: can be nil or non-nil, must be nil, must be
2077 // non-nil. We ignore must be nil, and merge the rest two into non-nil.
2078 if (nilState && !notNilState) {
2079 dstEval.insert(Pred);
2083 // Check if the "raise" message was sent.
2084 assert(notNilState);
2085 if (msg.getSelector() == RaiseSel)
2086 RaisesException = true;
2088 // Check if we raise an exception. For now treat these as sinks.
2089 // Eventually we will want to handle exceptions properly.
2090 if (RaisesException)
2091 Builder->BuildSinks = true;
2093 // Dispatch to plug-in transfer function.
2094 evalObjCMessage(dstEval, msg, Pred, notNilState);
2097 else if (const ObjCInterfaceDecl *Iface = msg.getReceiverInterface()) {
2098 IdentifierInfo* ClsName = Iface->getIdentifier();
2099 Selector S = msg.getSelector();
2101 // Check for special instance methods.
2102 if (!NSExceptionII) {
2103 ASTContext& Ctx = getContext();
2104 NSExceptionII = &Ctx.Idents.get("NSException");
2107 if (ClsName == NSExceptionII) {
2108 enum { NUM_RAISE_SELECTORS = 2 };
2110 // Lazily create a cache of the selectors.
2111 if (!NSExceptionInstanceRaiseSelectors) {
2112 ASTContext& Ctx = getContext();
2113 NSExceptionInstanceRaiseSelectors =
2114 new Selector[NUM_RAISE_SELECTORS];
2115 llvm::SmallVector<IdentifierInfo*, NUM_RAISE_SELECTORS> II;
2119 II.push_back(&Ctx.Idents.get("raise"));
2120 II.push_back(&Ctx.Idents.get("format"));
2121 NSExceptionInstanceRaiseSelectors[idx++] =
2122 Ctx.Selectors.getSelector(II.size(), &II[0]);
2124 // raise:format::arguments:
2125 II.push_back(&Ctx.Idents.get("arguments"));
2126 NSExceptionInstanceRaiseSelectors[idx++] =
2127 Ctx.Selectors.getSelector(II.size(), &II[0]);
2130 for (unsigned i = 0; i < NUM_RAISE_SELECTORS; ++i)
2131 if (S == NSExceptionInstanceRaiseSelectors[i]) {
2132 RaisesException = true;
2137 // Check if we raise an exception. For now treat these as sinks.
2138 // Eventually we will want to handle exceptions properly.
2139 if (RaisesException)
2140 Builder->BuildSinks = true;
2142 // Dispatch to plug-in transfer function.
2143 evalObjCMessage(dstEval, msg, Pred, Builder->GetState(Pred));
2146 // Handle the case where no nodes where generated. Auto-generate that
2147 // contains the updated state if we aren't generating sinks.
2148 if (!Builder->BuildSinks && dstEval.size() == oldSize &&
2149 !Builder->hasGeneratedNode)
2150 MakeNode(dstEval, msg.getOriginExpr(), Pred, GetState(Pred));
2153 // Finally, perform the post-condition check of the ObjCMessageExpr and store
2154 // the created nodes in 'Dst'.
2155 getCheckerManager().runCheckersForPostObjCMessage(Dst, dstEval, msg, *this);
2158 //===----------------------------------------------------------------------===//
2159 // Transfer functions: Miscellaneous statements.
2160 //===----------------------------------------------------------------------===//
2162 void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,
2163 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
2166 Visit(Ex, Pred, S1);
2168 getCheckerManager().runCheckersForPreStmt(S2, S1, CastE, *this);
2170 if (CastE->getCastKind() == CK_LValueToRValue ||
2171 CastE->getCastKind() == CK_GetObjCProperty) {
2172 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I!=E; ++I) {
2173 ExplodedNode *subExprNode = *I;
2174 const GRState *state = GetState(subExprNode);
2175 evalLoad(Dst, CastE, subExprNode, state, state->getSVal(Ex));
2181 QualType T = CastE->getType();
2182 QualType ExTy = Ex->getType();
2184 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE))
2185 T = ExCast->getTypeAsWritten();
2187 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {
2190 switch (CastE->getCastKind()) {
2191 case CK_LValueToRValue:
2192 assert(false && "LValueToRValue casts handled earlier.");
2193 case CK_GetObjCProperty:
2194 assert(false && "GetObjCProperty casts handled earlier.");
2198 // The analyzer doesn't do anything special with these casts,
2199 // since it understands retain/release semantics already.
2200 case CK_ObjCProduceObject:
2201 case CK_ObjCConsumeObject:
2202 case CK_ObjCReclaimReturnedObject: // Fall-through.
2205 case CK_FunctionToPointerDecay: {
2206 // Copy the SVal of Ex to CastE.
2207 const GRState *state = GetState(Pred);
2208 SVal V = state->getSVal(Ex);
2209 state = state->BindExpr(CastE, V);
2210 MakeNode(Dst, CastE, Pred, state);
2214 case CK_ArrayToPointerDecay:
2216 case CK_LValueBitCast:
2217 case CK_IntegralCast:
2218 case CK_NullToPointer:
2219 case CK_IntegralToPointer:
2220 case CK_PointerToIntegral:
2221 case CK_PointerToBoolean:
2222 case CK_IntegralToBoolean:
2223 case CK_IntegralToFloating:
2224 case CK_FloatingToIntegral:
2225 case CK_FloatingToBoolean:
2226 case CK_FloatingCast:
2227 case CK_FloatingRealToComplex:
2228 case CK_FloatingComplexToReal:
2229 case CK_FloatingComplexToBoolean:
2230 case CK_FloatingComplexCast:
2231 case CK_FloatingComplexToIntegralComplex:
2232 case CK_IntegralRealToComplex:
2233 case CK_IntegralComplexToReal:
2234 case CK_IntegralComplexToBoolean:
2235 case CK_IntegralComplexCast:
2236 case CK_IntegralComplexToFloatingComplex:
2237 case CK_AnyPointerToObjCPointerCast:
2238 case CK_AnyPointerToBlockPointerCast:
2239 case CK_ObjCObjectLValueCast: {
2240 // Delegate to SValBuilder to process.
2241 const GRState* state = GetState(Pred);
2242 SVal V = state->getSVal(Ex);
2243 V = svalBuilder.evalCast(V, T, ExTy);
2244 state = state->BindExpr(CastE, V);
2245 MakeNode(Dst, CastE, Pred, state);
2248 case CK_DerivedToBase:
2249 case CK_UncheckedDerivedToBase: {
2250 // For DerivedToBase cast, delegate to the store manager.
2251 const GRState *state = GetState(Pred);
2252 SVal val = state->getSVal(Ex);
2253 val = getStoreManager().evalDerivedToBase(val, T);
2254 state = state->BindExpr(CastE, val);
2255 MakeNode(Dst, CastE, Pred, state);
2258 // Various C++ casts that are not handled yet.
2261 case CK_BaseToDerived:
2262 case CK_NullToMemberPointer:
2263 case CK_BaseToDerivedMemberPointer:
2264 case CK_DerivedToBaseMemberPointer:
2265 case CK_UserDefinedConversion:
2266 case CK_ConstructorConversion:
2267 case CK_VectorSplat:
2268 case CK_MemberPointerToBoolean: {
2269 // Recover some path-sensitivty by conjuring a new value.
2270 QualType resultType = CastE->getType();
2271 if (CastE->isLValue())
2272 resultType = getContext().getPointerType(resultType);
2275 svalBuilder.getConjuredSymbolVal(NULL, CastE, resultType,
2276 Builder->getCurrentBlockCount());
2278 const GRState *state = GetState(Pred)->BindExpr(CastE, result);
2279 MakeNode(Dst, CastE, Pred, state);
2286 void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr* CL,
2288 ExplodedNodeSet& Dst) {
2289 const InitListExpr* ILE
2290 = cast<InitListExpr>(CL->getInitializer()->IgnoreParens());
2291 ExplodedNodeSet Tmp;
2292 Visit(ILE, Pred, Tmp);
2294 for (ExplodedNodeSet::iterator I = Tmp.begin(), EI = Tmp.end(); I!=EI; ++I) {
2295 const GRState* state = GetState(*I);
2296 SVal ILV = state->getSVal(ILE);
2297 const LocationContext *LC = (*I)->getLocationContext();
2298 state = state->bindCompoundLiteral(CL, LC, ILV);
2300 if (CL->isLValue()) {
2301 MakeNode(Dst, CL, *I, state->BindExpr(CL, state->getLValue(CL, LC)));
2304 MakeNode(Dst, CL, *I, state->BindExpr(CL, ILV));
2308 void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
2309 ExplodedNodeSet& Dst) {
2311 // The CFG has one DeclStmt per Decl.
2312 const Decl* D = *DS->decl_begin();
2314 if (!D || !isa<VarDecl>(D))
2317 const VarDecl* VD = dyn_cast<VarDecl>(D);
2318 const Expr* InitEx = VD->getInit();
2320 // FIXME: static variables may have an initializer, but the second
2321 // time a function is called those values may not be current.
2322 ExplodedNodeSet Tmp;
2325 Visit(InitEx, Pred, Tmp);
2329 ExplodedNodeSet Tmp2;
2330 getCheckerManager().runCheckersForPreStmt(Tmp2, Tmp, DS, *this);
2332 for (ExplodedNodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) {
2333 ExplodedNode *N = *I;
2334 const GRState *state = GetState(N);
2336 // Decls without InitExpr are not initialized explicitly.
2337 const LocationContext *LC = N->getLocationContext();
2340 SVal InitVal = state->getSVal(InitEx);
2342 // We bound the temp obj region to the CXXConstructExpr. Now recover
2343 // the lazy compound value when the variable is not a reference.
2344 if (AMgr.getLangOptions().CPlusPlus && VD->getType()->isRecordType() &&
2345 !VD->getType()->isReferenceType() && isa<loc::MemRegionVal>(InitVal)){
2346 InitVal = state->getSVal(cast<loc::MemRegionVal>(InitVal).getRegion());
2347 assert(isa<nonloc::LazyCompoundVal>(InitVal));
2350 // Recover some path-sensitivity if a scalar value evaluated to
2352 if ((InitVal.isUnknown() ||
2353 !getConstraintManager().canReasonAbout(InitVal)) &&
2354 !VD->getType()->isReferenceType()) {
2355 InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx,
2356 Builder->getCurrentBlockCount());
2359 evalBind(Dst, DS, *I, state,
2360 loc::MemRegionVal(state->getRegion(VD, LC)), InitVal, true);
2363 state = state->bindDeclWithNoInit(state->getRegion(VD, LC));
2364 MakeNode(Dst, DS, *I, state);
2370 // This class is used by VisitInitListExpr as an item in a worklist
2371 // for processing the values contained in an InitListExpr.
2372 class InitListWLItem {
2374 llvm::ImmutableList<SVal> Vals;
2376 InitListExpr::const_reverse_iterator Itr;
2378 InitListWLItem(ExplodedNode* n, llvm::ImmutableList<SVal> vals,
2379 InitListExpr::const_reverse_iterator itr)
2380 : Vals(vals), N(n), Itr(itr) {}
2385 void ExprEngine::VisitInitListExpr(const InitListExpr* E, ExplodedNode* Pred,
2386 ExplodedNodeSet& Dst) {
2388 const GRState* state = GetState(Pred);
2389 QualType T = getContext().getCanonicalType(E->getType());
2390 unsigned NumInitElements = E->getNumInits();
2392 if (T->isArrayType() || T->isRecordType() || T->isVectorType()) {
2393 llvm::ImmutableList<SVal> StartVals = getBasicVals().getEmptySValList();
2395 // Handle base case where the initializer has no elements.
2396 // e.g: static int* myArray[] = {};
2397 if (NumInitElements == 0) {
2398 SVal V = svalBuilder.makeCompoundVal(T, StartVals);
2399 MakeNode(Dst, E, Pred, state->BindExpr(E, V));
2403 // Create a worklist to process the initializers.
2404 llvm::SmallVector<InitListWLItem, 10> WorkList;
2405 WorkList.reserve(NumInitElements);
2406 WorkList.push_back(InitListWLItem(Pred, StartVals, E->rbegin()));
2407 InitListExpr::const_reverse_iterator ItrEnd = E->rend();
2408 assert(!(E->rbegin() == E->rend()));
2410 // Process the worklist until it is empty.
2411 while (!WorkList.empty()) {
2412 InitListWLItem X = WorkList.back();
2413 WorkList.pop_back();
2415 ExplodedNodeSet Tmp;
2416 Visit(*X.Itr, X.N, Tmp);
2418 InitListExpr::const_reverse_iterator NewItr = X.Itr + 1;
2420 for (ExplodedNodeSet::iterator NI=Tmp.begin(),NE=Tmp.end();NI!=NE;++NI) {
2421 // Get the last initializer value.
2422 state = GetState(*NI);
2423 SVal InitV = state->getSVal(cast<Expr>(*X.Itr));
2425 // Construct the new list of values by prepending the new value to
2426 // the already constructed list.
2427 llvm::ImmutableList<SVal> NewVals =
2428 getBasicVals().consVals(InitV, X.Vals);
2430 if (NewItr == ItrEnd) {
2431 // Now we have a list holding all init values. Make CompoundValData.
2432 SVal V = svalBuilder.makeCompoundVal(T, NewVals);
2434 // Make final state and node.
2435 MakeNode(Dst, E, *NI, state->BindExpr(E, V));
2438 // Still some initializer values to go. Push them onto the worklist.
2439 WorkList.push_back(InitListWLItem(*NI, NewVals, NewItr));
2447 if (Loc::isLocType(T) || T->isIntegerType()) {
2448 assert (E->getNumInits() == 1);
2449 ExplodedNodeSet Tmp;
2450 const Expr* Init = E->getInit(0);
2451 Visit(Init, Pred, Tmp);
2452 for (ExplodedNodeSet::iterator I=Tmp.begin(), EI=Tmp.end(); I != EI; ++I) {
2453 state = GetState(*I);
2454 MakeNode(Dst, E, *I, state->BindExpr(E, state->getSVal(Init)));
2459 assert(0 && "unprocessed InitListExpr type");
2462 /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof(type).
2463 void ExprEngine::VisitUnaryExprOrTypeTraitExpr(
2464 const UnaryExprOrTypeTraitExpr* Ex,
2466 ExplodedNodeSet& Dst) {
2467 QualType T = Ex->getTypeOfArgument();
2469 if (Ex->getKind() == UETT_SizeOf) {
2470 if (!T->isIncompleteType() && !T->isConstantSizeType()) {
2471 assert(T->isVariableArrayType() && "Unknown non-constant-sized type.");
2473 // FIXME: Add support for VLA type arguments, not just VLA expressions.
2474 // When that happens, we should probably refactor VLASizeChecker's code.
2475 if (Ex->isArgumentType()) {
2480 // Get the size by getting the extent of the sub-expression.
2481 // First, visit the sub-expression to find its region.
2482 const Expr *Arg = Ex->getArgumentExpr();
2483 ExplodedNodeSet Tmp;
2484 Visit(Arg, Pred, Tmp);
2486 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2487 const GRState* state = GetState(*I);
2488 const MemRegion *MR = state->getSVal(Arg).getAsRegion();
2490 // If the subexpression can't be resolved to a region, we don't know
2491 // anything about its size. Just leave the state as is and continue.
2497 // The result is the extent of the VLA.
2498 SVal Extent = cast<SubRegion>(MR)->getExtent(svalBuilder);
2499 MakeNode(Dst, Ex, *I, state->BindExpr(Ex, Extent));
2504 else if (T->getAs<ObjCObjectType>()) {
2505 // Some code tries to take the sizeof an ObjCObjectType, relying that
2506 // the compiler has laid out its representation. Just report Unknown
2513 Expr::EvalResult Result;
2514 Ex->Evaluate(Result, getContext());
2515 CharUnits amt = CharUnits::fromQuantity(Result.Val.getInt().getZExtValue());
2517 MakeNode(Dst, Ex, Pred,
2518 GetState(Pred)->BindExpr(Ex,
2519 svalBuilder.makeIntVal(amt.getQuantity(), Ex->getType())));
2522 void ExprEngine::VisitOffsetOfExpr(const OffsetOfExpr* OOE,
2523 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
2524 Expr::EvalResult Res;
2525 if (OOE->Evaluate(Res, getContext()) && Res.Val.isInt()) {
2526 const APSInt &IV = Res.Val.getInt();
2527 assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType()));
2528 assert(OOE->getType()->isIntegerType());
2529 assert(IV.isSigned() == OOE->getType()->isSignedIntegerOrEnumerationType());
2530 SVal X = svalBuilder.makeIntVal(IV);
2531 MakeNode(Dst, OOE, Pred, GetState(Pred)->BindExpr(OOE, X));
2534 // FIXME: Handle the case where __builtin_offsetof is not a constant.
2538 void ExprEngine::VisitUnaryOperator(const UnaryOperator* U,
2540 ExplodedNodeSet& Dst) {
2542 switch (U->getOpcode()) {
2548 const Expr* Ex = U->getSubExpr()->IgnoreParens();
2549 ExplodedNodeSet Tmp;
2550 Visit(Ex, Pred, Tmp);
2552 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2554 // FIXME: We don't have complex SValues yet.
2555 if (Ex->getType()->isAnyComplexType()) {
2556 // Just report "Unknown."
2561 // For all other types, UO_Real is an identity operation.
2562 assert (U->getType() == Ex->getType());
2563 const GRState* state = GetState(*I);
2564 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex)));
2572 const Expr* Ex = U->getSubExpr()->IgnoreParens();
2573 ExplodedNodeSet Tmp;
2574 Visit(Ex, Pred, Tmp);
2576 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2577 // FIXME: We don't have complex SValues yet.
2578 if (Ex->getType()->isAnyComplexType()) {
2579 // Just report "Unknown."
2584 // For all other types, UO_Imag returns 0.
2585 const GRState* state = GetState(*I);
2586 SVal X = svalBuilder.makeZeroVal(Ex->getType());
2587 MakeNode(Dst, U, *I, state->BindExpr(U, X));
2594 assert(!U->isLValue());
2598 case UO_Extension: {
2600 // Unary "+" is a no-op, similar to a parentheses. We still have places
2601 // where it may be a block-level expression, so we need to
2602 // generate an extra node that just propagates the value of the
2605 const Expr* Ex = U->getSubExpr()->IgnoreParens();
2606 ExplodedNodeSet Tmp;
2607 Visit(Ex, Pred, Tmp);
2609 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2610 const GRState* state = GetState(*I);
2611 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex)));
2620 assert (!U->isLValue());
2621 const Expr* Ex = U->getSubExpr()->IgnoreParens();
2622 ExplodedNodeSet Tmp;
2623 Visit(Ex, Pred, Tmp);
2625 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2626 const GRState* state = GetState(*I);
2628 // Get the value of the subexpression.
2629 SVal V = state->getSVal(Ex);
2631 if (V.isUnknownOrUndef()) {
2632 MakeNode(Dst, U, *I, state->BindExpr(U, V));
2636 // QualType DstT = getContext().getCanonicalType(U->getType());
2637 // QualType SrcT = getContext().getCanonicalType(Ex->getType());
2639 // if (DstT != SrcT) // Perform promotions.
2640 // V = evalCast(V, DstT);
2642 // if (V.isUnknownOrUndef()) {
2643 // MakeNode(Dst, U, *I, BindExpr(St, U, V));
2647 switch (U->getOpcode()) {
2649 assert(false && "Invalid Opcode.");
2653 // FIXME: Do we need to handle promotions?
2654 state = state->BindExpr(U, evalComplement(cast<NonLoc>(V)));
2658 // FIXME: Do we need to handle promotions?
2659 state = state->BindExpr(U, evalMinus(cast<NonLoc>(V)));
2664 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
2666 // Note: technically we do "E == 0", but this is the same in the
2667 // transfer functions as "0 == E".
2671 Loc X = svalBuilder.makeNull();
2672 Result = evalBinOp(state, BO_EQ, cast<Loc>(V), X,
2676 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType()));
2677 Result = evalBinOp(state, BO_EQ, cast<NonLoc>(V), X,
2681 state = state->BindExpr(U, Result);
2686 MakeNode(Dst, U, *I, state);
2693 // Handle ++ and -- (both pre- and post-increment).
2694 assert (U->isIncrementDecrementOp());
2695 ExplodedNodeSet Tmp;
2696 const Expr* Ex = U->getSubExpr()->IgnoreParens();
2697 Visit(Ex, Pred, Tmp);
2699 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) {
2701 const GRState* state = GetState(*I);
2702 SVal loc = state->getSVal(Ex);
2705 ExplodedNodeSet Tmp2;
2706 evalLoad(Tmp2, Ex, *I, state, loc);
2708 for (ExplodedNodeSet::iterator I2=Tmp2.begin(), E2=Tmp2.end();I2!=E2;++I2) {
2710 state = GetState(*I2);
2711 SVal V2_untested = state->getSVal(Ex);
2713 // Propagate unknown and undefined values.
2714 if (V2_untested.isUnknownOrUndef()) {
2715 MakeNode(Dst, U, *I2, state->BindExpr(U, V2_untested));
2718 DefinedSVal V2 = cast<DefinedSVal>(V2_untested);
2720 // Handle all other values.
2721 BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add
2724 // If the UnaryOperator has non-location type, use its type to create the
2725 // constant value. If the UnaryOperator has location type, create the
2726 // constant with int type and pointer width.
2729 if (U->getType()->isAnyPointerType())
2730 RHS = svalBuilder.makeArrayIndex(1);
2732 RHS = svalBuilder.makeIntVal(1, U->getType());
2734 SVal Result = evalBinOp(state, Op, V2, RHS, U->getType());
2736 // Conjure a new symbol if necessary to recover precision.
2737 if (Result.isUnknown() || !getConstraintManager().canReasonAbout(Result)){
2738 DefinedOrUnknownSVal SymVal =
2739 svalBuilder.getConjuredSymbolVal(NULL, Ex,
2740 Builder->getCurrentBlockCount());
2743 // If the value is a location, ++/-- should always preserve
2744 // non-nullness. Check if the original value was non-null, and if so
2745 // propagate that constraint.
2746 if (Loc::isLocType(U->getType())) {
2747 DefinedOrUnknownSVal Constraint =
2748 svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType()));
2750 if (!state->assume(Constraint, true)) {
2751 // It isn't feasible for the original value to be null.
2752 // Propagate this constraint.
2753 Constraint = svalBuilder.evalEQ(state, SymVal,
2754 svalBuilder.makeZeroVal(U->getType()));
2757 state = state->assume(Constraint, false);
2763 // Since the lvalue-to-rvalue conversion is explicit in the AST,
2764 // we bind an l-value if the operator is prefix and an lvalue (in C++).
2766 state = state->BindExpr(U, loc);
2768 state = state->BindExpr(U, U->isPostfix() ? V2 : Result);
2770 // Perform the store.
2771 evalStore(Dst, NULL, U, *I2, state, loc, Result);
2776 void ExprEngine::VisitAsmStmt(const AsmStmt* A, ExplodedNode* Pred,
2777 ExplodedNodeSet& Dst) {
2778 VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst);
2781 void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt* A,
2782 AsmStmt::const_outputs_iterator I,
2783 AsmStmt::const_outputs_iterator E,
2784 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
2786 VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst);
2790 ExplodedNodeSet Tmp;
2791 Visit(*I, Pred, Tmp);
2794 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI)
2795 VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst);
2798 void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt* A,
2799 AsmStmt::const_inputs_iterator I,
2800 AsmStmt::const_inputs_iterator E,
2802 ExplodedNodeSet& Dst) {
2805 // We have processed both the inputs and the outputs. All of the outputs
2806 // should evaluate to Locs. Nuke all of their values.
2808 // FIXME: Some day in the future it would be nice to allow a "plug-in"
2809 // which interprets the inline asm and stores proper results in the
2812 const GRState* state = GetState(Pred);
2814 for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(),
2815 OE = A->end_outputs(); OI != OE; ++OI) {
2817 SVal X = state->getSVal(*OI);
2818 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.
2821 state = state->bindLoc(cast<Loc>(X), UnknownVal());
2824 MakeNode(Dst, A, Pred, state);
2828 ExplodedNodeSet Tmp;
2829 Visit(*I, Pred, Tmp);
2833 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI)
2834 VisitAsmStmtHelperInputs(A, I, E, *NI, Dst);
2837 void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
2838 ExplodedNodeSet &Dst) {
2839 ExplodedNodeSet Src;
2840 if (const Expr *RetE = RS->getRetValue()) {
2841 // Record the returned expression in the state. It will be used in
2842 // processCallExit to bind the return value to the call expr.
2845 const GRState *state = GetState(Pred);
2846 state = state->set<ReturnExpr>(RetE);
2847 Pred = Builder->generateNode(RetE, state, Pred, &tag);
2849 // We may get a NULL Pred because we generated a cached node.
2851 Visit(RetE, Pred, Src);
2857 ExplodedNodeSet CheckedSet;
2858 getCheckerManager().runCheckersForPreStmt(CheckedSet, Src, RS, *this);
2860 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
2863 assert(Builder && "StmtNodeBuilder must be defined.");
2866 unsigned size = Dst.size();
2868 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
2869 SaveOr OldHasGen(Builder->hasGeneratedNode);
2871 getTF().evalReturn(Dst, *this, *Builder, RS, Pred);
2873 // Handle the case where no nodes where generated.
2874 if (!Builder->BuildSinks && Dst.size() == size &&
2875 !Builder->hasGeneratedNode)
2876 MakeNode(Dst, RS, Pred, GetState(Pred));
2880 //===----------------------------------------------------------------------===//
2881 // Transfer functions: Binary operators.
2882 //===----------------------------------------------------------------------===//
2884 void ExprEngine::VisitBinaryOperator(const BinaryOperator* B,
2886 ExplodedNodeSet& Dst) {
2887 ExplodedNodeSet Tmp1;
2888 Expr* LHS = B->getLHS()->IgnoreParens();
2889 Expr* RHS = B->getRHS()->IgnoreParens();
2891 Visit(LHS, Pred, Tmp1);
2892 ExplodedNodeSet Tmp3;
2894 for (ExplodedNodeSet::iterator I1=Tmp1.begin(), E1=Tmp1.end(); I1!=E1; ++I1) {
2895 SVal LeftV = GetState(*I1)->getSVal(LHS);
2896 ExplodedNodeSet Tmp2;
2897 Visit(RHS, *I1, Tmp2);
2899 ExplodedNodeSet CheckedSet;
2900 getCheckerManager().runCheckersForPreStmt(CheckedSet, Tmp2, B, *this);
2902 // With both the LHS and RHS evaluated, process the operation itself.
2904 for (ExplodedNodeSet::iterator I2=CheckedSet.begin(), E2=CheckedSet.end();
2907 const GRState *state = GetState(*I2);
2908 SVal RightV = state->getSVal(RHS);
2910 BinaryOperator::Opcode Op = B->getOpcode();
2912 if (Op == BO_Assign) {
2913 // EXPERIMENTAL: "Conjured" symbols.
2914 // FIXME: Handle structs.
2915 if (RightV.isUnknown() ||!getConstraintManager().canReasonAbout(RightV))
2917 unsigned Count = Builder->getCurrentBlockCount();
2918 RightV = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), Count);
2921 SVal ExprVal = B->isLValue() ? LeftV : RightV;
2923 // Simulate the effects of a "store": bind the value of the RHS
2924 // to the L-Value represented by the LHS.
2925 evalStore(Tmp3, B, LHS, *I2, state->BindExpr(B, ExprVal), LeftV,RightV);
2929 if (!B->isAssignmentOp()) {
2930 // Process non-assignments except commas or short-circuited
2931 // logical expressions (LAnd and LOr).
2932 SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType());
2934 if (Result.isUnknown()) {
2935 MakeNode(Tmp3, B, *I2, state);
2939 state = state->BindExpr(B, Result);
2941 MakeNode(Tmp3, B, *I2, state);
2945 assert (B->isCompoundAssignmentOp());
2949 assert(0 && "Invalid opcode for compound assignment.");
2950 case BO_MulAssign: Op = BO_Mul; break;
2951 case BO_DivAssign: Op = BO_Div; break;
2952 case BO_RemAssign: Op = BO_Rem; break;
2953 case BO_AddAssign: Op = BO_Add; break;
2954 case BO_SubAssign: Op = BO_Sub; break;
2955 case BO_ShlAssign: Op = BO_Shl; break;
2956 case BO_ShrAssign: Op = BO_Shr; break;
2957 case BO_AndAssign: Op = BO_And; break;
2958 case BO_XorAssign: Op = BO_Xor; break;
2959 case BO_OrAssign: Op = BO_Or; break;
2962 // Perform a load (the LHS). This performs the checks for
2963 // null dereferences, and so on.
2964 ExplodedNodeSet Tmp4;
2965 SVal location = state->getSVal(LHS);
2966 evalLoad(Tmp4, LHS, *I2, state, location);
2968 for (ExplodedNodeSet::iterator I4=Tmp4.begin(), E4=Tmp4.end(); I4!=E4;
2970 state = GetState(*I4);
2971 SVal V = state->getSVal(LHS);
2973 // Get the computation type.
2975 cast<CompoundAssignOperator>(B)->getComputationResultType();
2976 CTy = getContext().getCanonicalType(CTy);
2979 cast<CompoundAssignOperator>(B)->getComputationLHSType();
2980 CLHSTy = getContext().getCanonicalType(CLHSTy);
2982 QualType LTy = getContext().getCanonicalType(LHS->getType());
2985 V = svalBuilder.evalCast(V, CLHSTy, LTy);
2987 // Compute the result of the operation.
2988 SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy),
2991 // EXPERIMENTAL: "Conjured" symbols.
2992 // FIXME: Handle structs.
2996 if (Result.isUnknown() ||
2997 !getConstraintManager().canReasonAbout(Result)) {
2999 unsigned Count = Builder->getCurrentBlockCount();
3001 // The symbolic value is actually for the type of the left-hand side
3002 // expression, not the computation type, as this is the value the
3003 // LValue on the LHS will bind to.
3004 LHSVal = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LTy, Count);
3006 // However, we need to convert the symbol to the computation type.
3007 Result = svalBuilder.evalCast(LHSVal, CTy, LTy);
3010 // The left-hand side may bind to a different value then the
3011 // computation type.
3012 LHSVal = svalBuilder.evalCast(Result, LTy, CTy);
3015 // In C++, assignment and compound assignment operators return an
3018 state = state->BindExpr(B, location);
3020 state = state->BindExpr(B, Result);
3022 evalStore(Tmp3, B, LHS, *I4, state, location, LHSVal);
3027 getCheckerManager().runCheckersForPostStmt(Dst, Tmp3, B, *this);
3030 //===----------------------------------------------------------------------===//
3032 //===----------------------------------------------------------------------===//
3035 static ExprEngine* GraphPrintCheckerState;
3036 static SourceManager* GraphPrintSourceManager;
3040 struct DOTGraphTraits<ExplodedNode*> :
3041 public DefaultDOTGraphTraits {
3043 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
3045 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
3047 static std::string getNodeAttributes(const ExplodedNode* N, void*) {
3050 // FIXME: Replace with a general scheme to tell if the node is
3052 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
3053 GraphPrintCheckerState->isExplicitNullDeref(N) ||
3054 GraphPrintCheckerState->isUndefDeref(N) ||
3055 GraphPrintCheckerState->isUndefStore(N) ||
3056 GraphPrintCheckerState->isUndefControlFlow(N) ||
3057 GraphPrintCheckerState->isUndefResult(N) ||
3058 GraphPrintCheckerState->isBadCall(N) ||
3059 GraphPrintCheckerState->isUndefArg(N))
3060 return "color=\"red\",style=\"filled\"";
3062 if (GraphPrintCheckerState->isNoReturnCall(N))
3063 return "color=\"blue\",style=\"filled\"";
3068 static std::string getNodeLabel(const ExplodedNode* N, void*){
3071 llvm::raw_string_ostream Out(sbuf);
3073 // Program Location.
3074 ProgramPoint Loc = N->getLocation();
3076 switch (Loc.getKind()) {
3077 case ProgramPoint::BlockEntranceKind:
3078 Out << "Block Entrance: B"
3079 << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
3082 case ProgramPoint::BlockExitKind:
3086 case ProgramPoint::CallEnterKind:
3090 case ProgramPoint::CallExitKind:
3095 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) {
3096 const Stmt* S = L->getStmt();
3097 SourceLocation SLoc = S->getLocStart();
3099 Out << S->getStmtClassName() << ' ' << (void*) S << ' ';
3100 LangOptions LO; // FIXME.
3101 S->printPretty(Out, 0, PrintingPolicy(LO));
3103 if (SLoc.isFileID()) {
3105 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc)
3107 << GraphPrintSourceManager->getInstantiationColumnNumber(SLoc)
3111 if (isa<PreStmt>(Loc))
3112 Out << "\\lPreStmt\\l;";
3113 else if (isa<PostLoad>(Loc))
3114 Out << "\\lPostLoad\\l;";
3115 else if (isa<PostStore>(Loc))
3116 Out << "\\lPostStore\\l";
3117 else if (isa<PostLValue>(Loc))
3118 Out << "\\lPostLValue\\l";
3121 // FIXME: Replace with a general scheme to determine
3122 // the name of the check.
3123 if (GraphPrintCheckerState->isImplicitNullDeref(N))
3124 Out << "\\|Implicit-Null Dereference.\\l";
3125 else if (GraphPrintCheckerState->isExplicitNullDeref(N))
3126 Out << "\\|Explicit-Null Dereference.\\l";
3127 else if (GraphPrintCheckerState->isUndefDeref(N))
3128 Out << "\\|Dereference of undefialied value.\\l";
3129 else if (GraphPrintCheckerState->isUndefStore(N))
3130 Out << "\\|Store to Undefined Loc.";
3131 else if (GraphPrintCheckerState->isUndefResult(N))
3132 Out << "\\|Result of operation is undefined.";
3133 else if (GraphPrintCheckerState->isNoReturnCall(N))
3134 Out << "\\|Call to function marked \"noreturn\".";
3135 else if (GraphPrintCheckerState->isBadCall(N))
3136 Out << "\\|Call to NULL/Undefined.";
3137 else if (GraphPrintCheckerState->isUndefArg(N))
3138 Out << "\\|Argument in call is undefined";
3144 const BlockEdge& E = cast<BlockEdge>(Loc);
3145 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
3146 << E.getDst()->getBlockID() << ')';
3148 if (const Stmt* T = E.getSrc()->getTerminator()) {
3150 SourceLocation SLoc = T->getLocStart();
3152 Out << "\\|Terminator: ";
3153 LangOptions LO; // FIXME.
3154 E.getSrc()->printTerminator(Out, LO);
3156 if (SLoc.isFileID()) {
3158 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc)
3160 << GraphPrintSourceManager->getInstantiationColumnNumber(SLoc);
3163 if (isa<SwitchStmt>(T)) {
3164 const Stmt* Label = E.getDst()->getLabel();
3167 if (const CaseStmt* C = dyn_cast<CaseStmt>(Label)) {
3169 LangOptions LO; // FIXME.
3170 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
3172 if (const Stmt* RHS = C->getRHS()) {
3174 RHS->printPretty(Out, 0, PrintingPolicy(LO));
3180 assert (isa<DefaultStmt>(Label));
3181 Out << "\\ldefault:";
3185 Out << "\\l(implicit) default:";
3187 else if (isa<IndirectGotoStmt>(T)) {
3191 Out << "\\lCondition: ";
3192 if (*E.getSrc()->succ_begin() == E.getDst())
3202 // FIXME: Replace with a general scheme to determine
3203 // the name of the check.
3204 if (GraphPrintCheckerState->isUndefControlFlow(N)) {
3205 Out << "\\|Control-flow based on\\lUndefined value.\\l";
3211 const GRState *state = N->getState();
3212 Out << "\\|StateID: " << (void*) state
3213 << " NodeID: " << (void*) N << "\\|";
3214 state->printDOT(Out, *N->getLocationContext()->getCFG());
3219 } // end llvm namespace
3223 template <typename ITERATOR>
3224 ExplodedNode* GetGraphNode(ITERATOR I) { return *I; }
3226 template <> ExplodedNode*
3227 GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
3228 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
3233 void ExprEngine::ViewGraph(bool trim) {
3236 std::vector<ExplodedNode*> Src;
3238 // Flush any outstanding reports to make sure we cover all the nodes.
3239 // This does not cause them to get displayed.
3240 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
3241 const_cast<BugType*>(*I)->FlushReports(BR);
3243 // Iterate through the reports and get their nodes.
3244 for (BugReporter::EQClasses_iterator
3245 EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
3246 BugReportEquivClass& EQ = *EI;
3247 const BugReport &R = **EQ.begin();
3248 ExplodedNode *N = const_cast<ExplodedNode*>(R.getErrorNode());
3249 if (N) Src.push_back(N);
3252 ViewGraph(&Src[0], &Src[0]+Src.size());
3255 GraphPrintCheckerState = this;
3256 GraphPrintSourceManager = &getContext().getSourceManager();
3258 llvm::ViewGraph(*G.roots_begin(), "ExprEngine");
3260 GraphPrintCheckerState = NULL;
3261 GraphPrintSourceManager = NULL;
3266 void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) {
3268 GraphPrintCheckerState = this;
3269 GraphPrintSourceManager = &getContext().getSourceManager();
3271 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first);
3273 if (!TrimmedG.get())
3274 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
3276 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine");
3278 GraphPrintCheckerState = NULL;
3279 GraphPrintSourceManager = NULL;