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 // FIXME: Restructure checker registration.
17 #include "ExprEngineInternalChecks.h"
19 #include "clang/StaticAnalyzer/BugReporter/BugType.h"
20 #include "clang/StaticAnalyzer/PathSensitive/AnalysisManager.h"
21 #include "clang/StaticAnalyzer/PathSensitive/ExprEngine.h"
22 #include "clang/StaticAnalyzer/PathSensitive/ExprEngineBuilders.h"
23 #include "clang/StaticAnalyzer/PathSensitive/Checker.h"
24 #include "clang/AST/CharUnits.h"
25 #include "clang/AST/ParentMap.h"
26 #include "clang/AST/StmtObjC.h"
27 #include "clang/AST/DeclCXX.h"
28 #include "clang/Basic/Builtins.h"
29 #include "clang/Basic/SourceManager.h"
30 #include "clang/Basic/SourceManager.h"
31 #include "clang/Basic/PrettyStackTrace.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include "llvm/ADT/ImmutableList.h"
36 #include "llvm/Support/GraphWriter.h"
39 using namespace clang
;
42 using llvm::dyn_cast_or_null
;
47 // Trait class for recording returned expression in the state.
50 typedef const Stmt
*data_type
;
52 int ReturnExpr::TagInt
;
55 //===----------------------------------------------------------------------===//
57 //===----------------------------------------------------------------------===//
59 static inline Selector
GetNullarySelector(const char* name
, ASTContext
& Ctx
) {
60 IdentifierInfo
* II
= &Ctx
.Idents
.get(name
);
61 return Ctx
.Selectors
.getSelector(0, &II
);
64 //===----------------------------------------------------------------------===//
65 // Checker worklist routines.
66 //===----------------------------------------------------------------------===//
68 void ExprEngine::CheckerVisit(const Stmt
*S
, ExplodedNodeSet
&Dst
,
69 ExplodedNodeSet
&Src
, CallbackKind Kind
) {
71 // Determine if we already have a cached 'CheckersOrdered' vector
72 // specifically tailored for the provided <CallbackKind, Stmt kind>. This
73 // can reduce the number of checkers actually called.
74 CheckersOrdered
*CO
= &Checkers
;
75 llvm::OwningPtr
<CheckersOrdered
> NewCO
;
77 // The cache key is made up of the and the callback kind (pre- or post-visit)
78 // and the statement kind.
79 CallbackTag K
= GetCallbackTag(Kind
, S
->getStmtClass());
81 CheckersOrdered
*& CO_Ref
= COCache
[K
];
84 // If we have no previously cached CheckersOrdered vector for this
85 // statement kind, then create one.
86 NewCO
.reset(new CheckersOrdered
);
89 // Use the already cached set.
94 // If there are no checkers, return early without doing any
101 ExplodedNodeSet
*PrevSet
= &Src
;
102 unsigned checkersEvaluated
= 0;
104 for (CheckersOrdered::iterator I
=CO
->begin(), E
=CO
->end(); I
!=E
; ++I
) {
105 // If all nodes are sunk, bail out early.
106 if (PrevSet
->empty())
108 ExplodedNodeSet
*CurrSet
= 0;
112 CurrSet
= (PrevSet
== &Tmp
) ? &Src
: &Tmp
;
115 void *tag
= I
->first
;
116 Checker
*checker
= I
->second
;
117 bool respondsToCallback
= true;
119 for (ExplodedNodeSet::iterator NI
= PrevSet
->begin(), NE
= PrevSet
->end();
122 checker
->GR_Visit(*CurrSet
, *Builder
, *this, S
, *NI
, tag
,
123 Kind
== PreVisitStmtCallback
, respondsToCallback
);
131 if (respondsToCallback
)
132 NewCO
->push_back(*I
);
136 // If we built NewCO, check if we called all the checkers. This is important
137 // so that we know that we accurately determined the entire set of checkers
138 // that responds to this callback. Note that 'checkersEvaluated' might
139 // not be the same as Checkers.size() if one of the Checkers generates
141 if (NewCO
.get() && checkersEvaluated
== Checkers
.size())
142 CO_Ref
= NewCO
.take();
144 // Don't autotransition. The CheckerContext objects should do this
148 void ExprEngine::CheckerVisitObjCMessage(const ObjCMessage
&msg
,
149 ExplodedNodeSet
&Dst
,
150 ExplodedNodeSet
&Src
,
153 if (Checkers
.empty()) {
159 ExplodedNodeSet
*PrevSet
= &Src
;
161 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end(); I
!=E
; ++I
)
163 ExplodedNodeSet
*CurrSet
= 0;
167 CurrSet
= (PrevSet
== &Tmp
) ? &Src
: &Tmp
;
171 void *tag
= I
->first
;
172 Checker
*checker
= I
->second
;
174 for (ExplodedNodeSet::iterator NI
= PrevSet
->begin(), NE
= PrevSet
->end();
176 checker
->GR_visitObjCMessage(*CurrSet
, *Builder
, *this, msg
,
177 *NI
, tag
, isPrevisit
);
179 // Update which NodeSet is the current one.
183 // Don't autotransition. The CheckerContext objects should do this
187 void ExprEngine::CheckerEvalNilReceiver(const ObjCMessage
&msg
,
188 ExplodedNodeSet
&Dst
,
189 const GRState
*state
,
190 ExplodedNode
*Pred
) {
191 bool evaluated
= false;
192 ExplodedNodeSet DstTmp
;
194 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end();I
!=E
;++I
) {
195 void *tag
= I
->first
;
196 Checker
*checker
= I
->second
;
198 if (checker
->GR_evalNilReceiver(DstTmp
, *Builder
, *this, msg
, Pred
, state
,
203 // The checker didn't evaluate the expr. Restore the Dst.
213 // CheckerEvalCall returns true if one of the checkers processed the node.
214 // This may return void when all call evaluation logic goes to some checker
216 bool ExprEngine::CheckerEvalCall(const CallExpr
*CE
,
217 ExplodedNodeSet
&Dst
,
218 ExplodedNode
*Pred
) {
219 bool evaluated
= false;
220 ExplodedNodeSet DstTmp
;
222 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end();I
!=E
;++I
) {
223 void *tag
= I
->first
;
224 Checker
*checker
= I
->second
;
226 if (checker
->GR_evalCallExpr(DstTmp
, *Builder
, *this, CE
, Pred
, tag
)) {
230 // The checker didn't evaluate the expr. Restore the DstTmp set.
242 // FIXME: This is largely copy-paste from CheckerVisit(). Need to
244 void ExprEngine::CheckerVisitBind(const Stmt
*StoreE
, ExplodedNodeSet
&Dst
,
245 ExplodedNodeSet
&Src
, SVal location
,
246 SVal val
, bool isPrevisit
) {
248 if (Checkers
.empty()) {
254 ExplodedNodeSet
*PrevSet
= &Src
;
256 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end(); I
!=E
; ++I
)
258 ExplodedNodeSet
*CurrSet
= 0;
262 CurrSet
= (PrevSet
== &Tmp
) ? &Src
: &Tmp
;
266 void *tag
= I
->first
;
267 Checker
*checker
= I
->second
;
269 for (ExplodedNodeSet::iterator NI
= PrevSet
->begin(), NE
= PrevSet
->end();
271 checker
->GR_VisitBind(*CurrSet
, *Builder
, *this, StoreE
,
272 *NI
, tag
, location
, val
, isPrevisit
);
274 // Update which NodeSet is the current one.
278 // Don't autotransition. The CheckerContext objects should do this
281 //===----------------------------------------------------------------------===//
282 // Engine construction and deletion.
283 //===----------------------------------------------------------------------===//
285 static void RegisterInternalChecks(ExprEngine
&Eng
) {
286 // Register internal "built-in" BugTypes with the BugReporter. These BugTypes
287 // are different than what probably many checks will do since they don't
288 // create BugReports on-the-fly but instead wait until ExprEngine finishes
289 // analyzing a function. Generation of BugReport objects is done via a call
290 // to 'FlushReports' from BugReporter.
291 // The following checks do not need to have their associated BugTypes
292 // explicitly registered with the BugReporter. If they issue any BugReports,
293 // their associated BugType will get registered with the BugReporter
294 // automatically. Note that the check itself is owned by the ExprEngine
296 RegisterAdjustedReturnValueChecker(Eng
);
297 // CallAndMessageChecker should be registered before AttrNonNullChecker,
298 // where we assume arguments are not undefined.
299 RegisterCallAndMessageChecker(Eng
);
300 RegisterAttrNonNullChecker(Eng
);
301 RegisterDereferenceChecker(Eng
);
302 RegisterVLASizeChecker(Eng
);
303 RegisterDivZeroChecker(Eng
);
304 RegisterReturnUndefChecker(Eng
);
305 RegisterUndefinedArraySubscriptChecker(Eng
);
306 RegisterUndefinedAssignmentChecker(Eng
);
307 RegisterUndefBranchChecker(Eng
);
308 RegisterUndefCapturedBlockVarChecker(Eng
);
309 RegisterUndefResultChecker(Eng
);
310 RegisterStackAddrLeakChecker(Eng
);
311 RegisterObjCAtSyncChecker(Eng
);
312 registerObjCSelfInitChecker(Eng
);
314 // This is not a checker yet.
315 RegisterNoReturnFunctionChecker(Eng
);
316 RegisterBuiltinFunctionChecker(Eng
);
317 RegisterOSAtomicChecker(Eng
);
318 RegisterUnixAPIChecker(Eng
);
319 RegisterMacOSXAPIChecker(Eng
);
322 ExprEngine::ExprEngine(AnalysisManager
&mgr
, TransferFuncs
*tf
)
325 G(Engine
.getGraph()),
327 StateMgr(getContext(), mgr
.getStoreManagerCreator(),
328 mgr
.getConstraintManagerCreator(), G
.getAllocator(),
330 SymMgr(StateMgr
.getSymbolManager()),
331 svalBuilder(StateMgr
.getSValBuilder()),
332 EntryNode(NULL
), currentStmt(NULL
),
333 NSExceptionII(NULL
), NSExceptionInstanceRaiseSelectors(NULL
),
334 RaiseSel(GetNullarySelector("raise", getContext())),
335 BR(mgr
, *this), TF(tf
) {
336 // Register internal checks.
337 RegisterInternalChecks(*this);
339 // FIXME: Eventually remove the TF object entirely.
340 TF
->RegisterChecks(*this);
341 TF
->RegisterPrinters(getStateManager().Printers
);
344 ExprEngine::~ExprEngine() {
346 delete [] NSExceptionInstanceRaiseSelectors
;
348 // Delete the set of checkers.
349 for (CheckersOrdered::iterator I
=Checkers
.begin(), E
=Checkers
.end(); I
!=E
;++I
)
352 for (CheckersOrderedCache::iterator I
=COCache
.begin(), E
=COCache
.end();
357 //===----------------------------------------------------------------------===//
359 //===----------------------------------------------------------------------===//
361 const GRState
* ExprEngine::getInitialState(const LocationContext
*InitLoc
) {
362 const GRState
*state
= StateMgr
.getInitialState(InitLoc
);
366 // FIXME: It would be nice if we had a more general mechanism to add
367 // such preconditions. Some day.
369 const Decl
*D
= InitLoc
->getDecl();
370 if (const FunctionDecl
*FD
= dyn_cast
<FunctionDecl
>(D
)) {
371 // Precondition: the first argument of 'main' is an integer guaranteed
373 const IdentifierInfo
*II
= FD
->getIdentifier();
374 if (!II
|| !(II
->getName() == "main" && FD
->getNumParams() > 0))
377 const ParmVarDecl
*PD
= FD
->getParamDecl(0);
378 QualType T
= PD
->getType();
379 if (!T
->isIntegerType())
382 const MemRegion
*R
= state
->getRegion(PD
, InitLoc
);
386 SVal V
= state
->getSVal(loc::MemRegionVal(R
));
387 SVal Constraint_untested
= evalBinOp(state
, BO_GT
, V
,
388 svalBuilder
.makeZeroVal(T
),
391 DefinedOrUnknownSVal
*Constraint
=
392 dyn_cast
<DefinedOrUnknownSVal
>(&Constraint_untested
);
397 if (const GRState
*newState
= state
->assume(*Constraint
, true))
403 if (const ObjCMethodDecl
*MD
= dyn_cast
<ObjCMethodDecl
>(D
)) {
404 // Precondition: 'self' is always non-null upon entry to an Objective-C
406 const ImplicitParamDecl
*SelfD
= MD
->getSelfDecl();
407 const MemRegion
*R
= state
->getRegion(SelfD
, InitLoc
);
408 SVal V
= state
->getSVal(loc::MemRegionVal(R
));
410 if (const Loc
*LV
= dyn_cast
<Loc
>(&V
)) {
411 // Assume that the pointer value in 'self' is non-null.
412 state
= state
->assume(*LV
, true);
413 assert(state
&& "'self' cannot be null");
421 //===----------------------------------------------------------------------===//
422 // Top-level transfer function logic (Dispatcher).
423 //===----------------------------------------------------------------------===//
425 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
426 /// logic for handling assumptions on symbolic values.
427 const GRState
*ExprEngine::processAssume(const GRState
*state
, SVal cond
,
429 // Determine if we already have a cached 'CheckersOrdered' vector
430 // specifically tailored for processing assumptions. This
431 // can reduce the number of checkers actually called.
432 CheckersOrdered
*CO
= &Checkers
;
433 llvm::OwningPtr
<CheckersOrdered
> NewCO
;
435 CallbackTag K
= GetCallbackTag(processAssumeCallback
);
436 CheckersOrdered
*& CO_Ref
= COCache
[K
];
439 // If we have no previously cached CheckersOrdered vector for this
440 // statement kind, then create one.
441 NewCO
.reset(new CheckersOrdered
);
444 // Use the already cached set.
449 // Let the checkers have a crack at the assume before the transfer functions
451 for (CheckersOrdered::iterator I
= CO
->begin(), E
= CO
->end(); I
!=E
; ++I
) {
453 // If any checker declares the state infeasible (or if it starts that
458 Checker
*C
= I
->second
;
459 bool respondsToCallback
= true;
461 state
= C
->evalAssume(state
, cond
, assumption
, &respondsToCallback
);
463 // Check if we're building the cache of checkers that care about
465 if (NewCO
.get() && respondsToCallback
)
466 NewCO
->push_back(*I
);
469 // If we got through all the checkers, and we built a list of those that
470 // care about assumptions, save it.
472 CO_Ref
= NewCO
.take();
475 // If the state is infeasible at this point, bail out.
479 return TF
->evalAssume(state
, cond
, assumption
);
482 bool ExprEngine::wantsRegionChangeUpdate(const GRState
* state
) {
483 CallbackTag K
= GetCallbackTag(EvalRegionChangesCallback
);
484 CheckersOrdered
*CO
= COCache
[K
];
489 for (CheckersOrdered::iterator I
= CO
->begin(), E
= CO
->end(); I
!= E
; ++I
) {
490 Checker
*C
= I
->second
;
491 if (C
->wantsRegionChangeUpdate(state
))
499 ExprEngine::processRegionChanges(const GRState
*state
,
500 const MemRegion
* const *Begin
,
501 const MemRegion
* const *End
) {
502 // FIXME: Most of this method is copy-pasted from processAssume.
504 // Determine if we already have a cached 'CheckersOrdered' vector
505 // specifically tailored for processing region changes. This
506 // can reduce the number of checkers actually called.
507 CheckersOrdered
*CO
= &Checkers
;
508 llvm::OwningPtr
<CheckersOrdered
> NewCO
;
510 CallbackTag K
= GetCallbackTag(EvalRegionChangesCallback
);
511 CheckersOrdered
*& CO_Ref
= COCache
[K
];
514 // If we have no previously cached CheckersOrdered vector for this
515 // callback, then create one.
516 NewCO
.reset(new CheckersOrdered
);
519 // Use the already cached set.
523 // If there are no checkers, just return the state as is.
527 for (CheckersOrdered::iterator I
= CO
->begin(), E
= CO
->end(); I
!= E
; ++I
) {
528 // If any checker declares the state infeasible (or if it starts that way),
533 Checker
*C
= I
->second
;
534 bool respondsToCallback
= true;
536 state
= C
->EvalRegionChanges(state
, Begin
, End
, &respondsToCallback
);
538 // See if we're building a cache of checkers that care about region changes.
539 if (NewCO
.get() && respondsToCallback
)
540 NewCO
->push_back(*I
);
543 // If we got through all the checkers, and we built a list of those that
544 // care about region changes, save it.
546 CO_Ref
= NewCO
.take();
551 void ExprEngine::processEndWorklist(bool hasWorkRemaining
) {
552 for (CheckersOrdered::iterator I
= Checkers
.begin(), E
= Checkers
.end();
554 I
->second
->VisitEndAnalysis(G
, BR
, *this);
558 void ExprEngine::processCFGElement(const CFGElement E
,
559 StmtNodeBuilder
& builder
) {
560 switch (E
.getKind()) {
561 case CFGElement::Statement
:
562 ProcessStmt(E
.getAs
<CFGStmt
>(), builder
);
564 case CFGElement::Initializer
:
565 ProcessInitializer(E
.getAs
<CFGInitializer
>(), builder
);
567 case CFGElement::ImplicitDtor
:
568 ProcessImplicitDtor(E
.getAs
<CFGImplicitDtor
>(), builder
);
571 // Suppress compiler warning.
572 llvm_unreachable("Unexpected CFGElement kind.");
576 void ExprEngine::ProcessStmt(const CFGStmt S
, StmtNodeBuilder
& builder
) {
577 currentStmt
= S
.getStmt();
578 PrettyStackTraceLoc
CrashInfo(getContext().getSourceManager(),
579 currentStmt
->getLocStart(),
580 "Error evaluating statement");
583 EntryNode
= builder
.getPredecessor();
585 // Create the cleaned state.
586 const LocationContext
*LC
= EntryNode
->getLocationContext();
587 SymbolReaper
SymReaper(LC
, currentStmt
, SymMgr
);
589 if (AMgr
.shouldPurgeDead()) {
590 const GRState
*St
= EntryNode
->getState();
592 for (CheckersOrdered::iterator I
= Checkers
.begin(), E
= Checkers
.end();
594 Checker
*checker
= I
->second
;
595 checker
->MarkLiveSymbols(St
, SymReaper
);
598 const StackFrameContext
*SFC
= LC
->getCurrentStackFrame();
599 CleanedState
= StateMgr
.removeDeadBindings(St
, SFC
, SymReaper
);
601 CleanedState
= EntryNode
->getState();
604 // Process any special transfer function for dead symbols.
607 if (!SymReaper
.hasDeadSymbols())
610 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
611 SaveOr
OldHasGen(Builder
->hasGeneratedNode
);
613 SaveAndRestore
<bool> OldPurgeDeadSymbols(Builder
->PurgingDeadSymbols
);
614 Builder
->PurgingDeadSymbols
= true;
616 // FIXME: This should soon be removed.
617 ExplodedNodeSet Tmp2
;
618 getTF().evalDeadSymbols(Tmp2
, *this, *Builder
, EntryNode
,
619 CleanedState
, SymReaper
);
621 if (Checkers
.empty())
624 ExplodedNodeSet Tmp3
;
625 ExplodedNodeSet
*SrcSet
= &Tmp2
;
626 for (CheckersOrdered::iterator I
= Checkers
.begin(), E
= Checkers
.end();
628 ExplodedNodeSet
*DstSet
= 0;
632 DstSet
= (SrcSet
== &Tmp2
) ? &Tmp3
: &Tmp2
;
636 void *tag
= I
->first
;
637 Checker
*checker
= I
->second
;
638 for (ExplodedNodeSet::iterator NI
= SrcSet
->begin(), NE
= SrcSet
->end();
640 checker
->GR_evalDeadSymbols(*DstSet
, *Builder
, *this, currentStmt
,
641 *NI
, SymReaper
, tag
);
646 if (!Builder
->BuildSinks
&& !Builder
->hasGeneratedNode
)
650 bool HasAutoGenerated
= false;
652 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
655 // Set the cleaned state.
656 Builder
->SetCleanedState(*I
== EntryNode
? CleanedState
: GetState(*I
));
658 // Visit the statement.
659 Visit(currentStmt
, *I
, Dst
);
661 // Do we need to auto-generate a node? We only need to do this to generate
662 // a node with a "cleaned" state; CoreEngine will actually handle
663 // auto-transitions for other cases.
664 if (Dst
.size() == 1 && *Dst
.begin() == EntryNode
665 && !Builder
->hasGeneratedNode
&& !HasAutoGenerated
) {
666 HasAutoGenerated
= true;
667 builder
.generateNode(currentStmt
, GetState(EntryNode
), *I
);
671 // NULL out these variables to cleanup.
680 void ExprEngine::ProcessInitializer(const CFGInitializer Init
,
681 StmtNodeBuilder
&builder
) {
682 // We don't set EntryNode and currentStmt. And we don't clean up state.
683 const CXXCtorInitializer
*BMI
= Init
.getInitializer();
685 ExplodedNode
*pred
= builder
.getPredecessor();
687 const StackFrameContext
*stackFrame
= cast
<StackFrameContext
>(pred
->getLocationContext());
688 const CXXConstructorDecl
*decl
= cast
<CXXConstructorDecl
>(stackFrame
->getDecl());
689 const CXXThisRegion
*thisReg
= getCXXThisRegion(decl
, stackFrame
);
691 SVal thisVal
= pred
->getState()->getSVal(thisReg
);
693 if (BMI
->isAnyMemberInitializer()) {
696 // Evaluate the initializer.
697 Visit(BMI
->getInit(), pred
, Dst
);
699 for (ExplodedNodeSet::iterator I
= Dst
.begin(), E
= Dst
.end(); I
!= E
; ++I
){
700 ExplodedNode
*Pred
= *I
;
701 const GRState
*state
= Pred
->getState();
703 const FieldDecl
*FD
= BMI
->getAnyMember();
705 SVal FieldLoc
= state
->getLValue(FD
, thisVal
);
706 SVal InitVal
= state
->getSVal(BMI
->getInit());
707 state
= state
->bindLoc(FieldLoc
, InitVal
);
709 // Use a custom node building process.
710 PostInitializer
PP(BMI
, stackFrame
);
711 // Builder automatically add the generated node to the deferred set,
712 // which are processed in the builder's dtor.
713 builder
.generateNode(PP
, state
, Pred
);
718 assert(BMI
->isBaseInitializer());
720 // Get the base class declaration.
721 const CXXConstructExpr
*ctorExpr
= cast
<CXXConstructExpr
>(BMI
->getInit());
723 // Create the base object region.
725 getStoreManager().evalDerivedToBase(thisVal
, ctorExpr
->getType());
726 const MemRegion
*baseReg
= baseVal
.getAsRegion();
730 VisitCXXConstructExpr(ctorExpr
, baseReg
, pred
, dst
);
733 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D
,
734 StmtNodeBuilder
&builder
) {
737 switch (D
.getDtorKind()) {
738 case CFGElement::AutomaticObjectDtor
:
739 ProcessAutomaticObjDtor(cast
<CFGAutomaticObjDtor
>(D
), builder
);
741 case CFGElement::BaseDtor
:
742 ProcessBaseDtor(cast
<CFGBaseDtor
>(D
), builder
);
744 case CFGElement::MemberDtor
:
745 ProcessMemberDtor(cast
<CFGMemberDtor
>(D
), builder
);
747 case CFGElement::TemporaryDtor
:
748 ProcessTemporaryDtor(cast
<CFGTemporaryDtor
>(D
), builder
);
751 llvm_unreachable("Unexpected dtor kind.");
755 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor dtor
,
756 StmtNodeBuilder
&builder
) {
757 ExplodedNode
*pred
= builder
.getPredecessor();
758 const GRState
*state
= pred
->getState();
759 const VarDecl
*varDecl
= dtor
.getVarDecl();
761 QualType varType
= varDecl
->getType();
763 if (const ReferenceType
*refType
= varType
->getAs
<ReferenceType
>())
764 varType
= refType
->getPointeeType();
766 const CXXRecordDecl
*recordDecl
= varType
->getAsCXXRecordDecl();
767 assert(recordDecl
&& "get CXXRecordDecl fail");
768 const CXXDestructorDecl
*dtorDecl
= recordDecl
->getDestructor();
770 Loc dest
= state
->getLValue(varDecl
, pred
->getLocationContext());
772 ExplodedNodeSet dstSet
;
773 VisitCXXDestructor(dtorDecl
, cast
<loc::MemRegionVal
>(dest
).getRegion(),
774 dtor
.getTriggerStmt(), pred
, dstSet
);
777 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D
,
778 StmtNodeBuilder
&builder
) {
781 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D
,
782 StmtNodeBuilder
&builder
) {
785 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D
,
786 StmtNodeBuilder
&builder
) {
789 void ExprEngine::Visit(const Stmt
* S
, ExplodedNode
* Pred
,
790 ExplodedNodeSet
& Dst
) {
791 PrettyStackTraceLoc
CrashInfo(getContext().getSourceManager(),
793 "Error evaluating statement");
795 // Expressions to ignore.
796 if (const Expr
*Ex
= dyn_cast
<Expr
>(S
))
797 S
= Ex
->IgnoreParens();
799 // FIXME: add metadata to the CFG so that we can disable
800 // this check when we KNOW that there is no block-level subexpression.
801 // The motivation is that this check requires a hashtable lookup.
803 if (S
!= currentStmt
&& Pred
->getLocationContext()->getCFG()->isBlkExpr(S
)) {
808 switch (S
->getStmtClass()) {
809 // C++ stuff we don't support yet.
810 case Stmt::CXXBindTemporaryExprClass
:
811 case Stmt::CXXCatchStmtClass
:
812 case Stmt::CXXDefaultArgExprClass
:
813 case Stmt::CXXDependentScopeMemberExprClass
:
814 case Stmt::ExprWithCleanupsClass
:
815 case Stmt::CXXNullPtrLiteralExprClass
:
816 case Stmt::CXXPseudoDestructorExprClass
:
817 case Stmt::CXXTemporaryObjectExprClass
:
818 case Stmt::CXXThrowExprClass
:
819 case Stmt::CXXTryStmtClass
:
820 case Stmt::CXXTypeidExprClass
:
821 case Stmt::CXXUuidofExprClass
:
822 case Stmt::CXXUnresolvedConstructExprClass
:
823 case Stmt::CXXScalarValueInitExprClass
:
824 case Stmt::DependentScopeDeclRefExprClass
:
825 case Stmt::UnaryTypeTraitExprClass
:
826 case Stmt::BinaryTypeTraitExprClass
:
827 case Stmt::UnresolvedLookupExprClass
:
828 case Stmt::UnresolvedMemberExprClass
:
829 case Stmt::CXXNoexceptExprClass
:
830 case Stmt::PackExpansionExprClass
:
831 case Stmt::SubstNonTypeTemplateParmPackExprClass
:
833 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
834 Builder
->BuildSinks
= true;
835 MakeNode(Dst
, S
, Pred
, GetState(Pred
));
839 case Stmt::ParenExprClass
:
840 llvm_unreachable("ParenExprs already handled.");
841 // Cases that should never be evaluated simply because they shouldn't
842 // appear in the CFG.
843 case Stmt::BreakStmtClass
:
844 case Stmt::CaseStmtClass
:
845 case Stmt::CompoundStmtClass
:
846 case Stmt::ContinueStmtClass
:
847 case Stmt::DefaultStmtClass
:
848 case Stmt::DoStmtClass
:
849 case Stmt::GotoStmtClass
:
850 case Stmt::IndirectGotoStmtClass
:
851 case Stmt::LabelStmtClass
:
852 case Stmt::NoStmtClass
:
853 case Stmt::NullStmtClass
:
854 case Stmt::SwitchCaseClass
:
855 case Stmt::OpaqueValueExprClass
:
856 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
859 case Stmt::GNUNullExprClass
: {
860 MakeNode(Dst
, S
, Pred
, GetState(Pred
)->BindExpr(S
, svalBuilder
.makeNull()));
864 case Stmt::ObjCAtSynchronizedStmtClass
:
865 VisitObjCAtSynchronizedStmt(cast
<ObjCAtSynchronizedStmt
>(S
), Pred
, Dst
);
868 case Stmt::ObjCPropertyRefExprClass
:
869 VisitObjCPropertyRefExpr(cast
<ObjCPropertyRefExpr
>(S
), Pred
, Dst
);
872 // Cases not handled yet; but will handle some day.
873 case Stmt::DesignatedInitExprClass
:
874 case Stmt::ExtVectorElementExprClass
:
875 case Stmt::ImaginaryLiteralClass
:
876 case Stmt::ImplicitValueInitExprClass
:
877 case Stmt::ObjCAtCatchStmtClass
:
878 case Stmt::ObjCAtFinallyStmtClass
:
879 case Stmt::ObjCAtTryStmtClass
:
880 case Stmt::ObjCEncodeExprClass
:
881 case Stmt::ObjCIsaExprClass
:
882 case Stmt::ObjCProtocolExprClass
:
883 case Stmt::ObjCSelectorExprClass
:
884 case Stmt::ObjCStringLiteralClass
:
885 case Stmt::ParenListExprClass
:
886 case Stmt::PredefinedExprClass
:
887 case Stmt::ShuffleVectorExprClass
:
888 case Stmt::VAArgExprClass
:
891 // Cases we intentionally don't evaluate, since they don't need
892 // to be explicitly evaluated.
893 case Stmt::AddrLabelExprClass
:
894 case Stmt::IntegerLiteralClass
:
895 case Stmt::CharacterLiteralClass
:
896 case Stmt::CXXBoolLiteralExprClass
:
897 case Stmt::FloatingLiteralClass
:
898 case Stmt::SizeOfPackExprClass
:
899 Dst
.Add(Pred
); // No-op. Simply propagate the current state unchanged.
902 case Stmt::ArraySubscriptExprClass
:
903 VisitLvalArraySubscriptExpr(cast
<ArraySubscriptExpr
>(S
), Pred
, Dst
);
906 case Stmt::AsmStmtClass
:
907 VisitAsmStmt(cast
<AsmStmt
>(S
), Pred
, Dst
);
910 case Stmt::BlockDeclRefExprClass
: {
911 const BlockDeclRefExpr
*BE
= cast
<BlockDeclRefExpr
>(S
);
912 VisitCommonDeclRefExpr(BE
, BE
->getDecl(), Pred
, Dst
);
916 case Stmt::BlockExprClass
:
917 VisitBlockExpr(cast
<BlockExpr
>(S
), Pred
, Dst
);
920 case Stmt::BinaryOperatorClass
: {
921 const BinaryOperator
* B
= cast
<BinaryOperator
>(S
);
922 if (B
->isLogicalOp()) {
923 VisitLogicalExpr(B
, Pred
, Dst
);
926 else if (B
->getOpcode() == BO_Comma
) {
927 const GRState
* state
= GetState(Pred
);
928 MakeNode(Dst
, B
, Pred
, state
->BindExpr(B
, state
->getSVal(B
->getRHS())));
932 if (AMgr
.shouldEagerlyAssume() &&
933 (B
->isRelationalOp() || B
->isEqualityOp())) {
935 VisitBinaryOperator(cast
<BinaryOperator
>(S
), Pred
, Tmp
);
936 evalEagerlyAssume(Dst
, Tmp
, cast
<Expr
>(S
));
939 VisitBinaryOperator(cast
<BinaryOperator
>(S
), Pred
, Dst
);
944 case Stmt::CallExprClass
: {
945 const CallExpr
* C
= cast
<CallExpr
>(S
);
946 VisitCall(C
, Pred
, C
->arg_begin(), C
->arg_end(), Dst
);
950 case Stmt::CXXConstructExprClass
: {
951 const CXXConstructExpr
*C
= cast
<CXXConstructExpr
>(S
);
952 // For block-level CXXConstructExpr, we don't have a destination region.
953 // Let VisitCXXConstructExpr() create one.
954 VisitCXXConstructExpr(C
, 0, Pred
, Dst
);
958 case Stmt::CXXMemberCallExprClass
: {
959 const CXXMemberCallExpr
*MCE
= cast
<CXXMemberCallExpr
>(S
);
960 VisitCXXMemberCallExpr(MCE
, Pred
, Dst
);
964 case Stmt::CXXOperatorCallExprClass
: {
965 const CXXOperatorCallExpr
*C
= cast
<CXXOperatorCallExpr
>(S
);
966 VisitCXXOperatorCallExpr(C
, Pred
, Dst
);
970 case Stmt::CXXNewExprClass
: {
971 const CXXNewExpr
*NE
= cast
<CXXNewExpr
>(S
);
972 VisitCXXNewExpr(NE
, Pred
, Dst
);
976 case Stmt::CXXDeleteExprClass
: {
977 const CXXDeleteExpr
*CDE
= cast
<CXXDeleteExpr
>(S
);
978 VisitCXXDeleteExpr(CDE
, Pred
, Dst
);
981 // FIXME: ChooseExpr is really a constant. We need to fix
982 // the CFG do not model them as explicit control-flow.
984 case Stmt::ChooseExprClass
: { // __builtin_choose_expr
985 const ChooseExpr
* C
= cast
<ChooseExpr
>(S
);
986 VisitGuardedExpr(C
, C
->getLHS(), C
->getRHS(), Pred
, Dst
);
990 case Stmt::CompoundAssignOperatorClass
:
991 VisitBinaryOperator(cast
<BinaryOperator
>(S
), Pred
, Dst
);
994 case Stmt::CompoundLiteralExprClass
:
995 VisitCompoundLiteralExpr(cast
<CompoundLiteralExpr
>(S
), Pred
, Dst
);
998 case Stmt::ConditionalOperatorClass
: { // '?' operator
999 const ConditionalOperator
* C
= cast
<ConditionalOperator
>(S
);
1000 VisitGuardedExpr(C
, C
->getLHS(), C
->getRHS(), Pred
, Dst
);
1004 case Stmt::CXXThisExprClass
:
1005 VisitCXXThisExpr(cast
<CXXThisExpr
>(S
), Pred
, Dst
);
1008 case Stmt::DeclRefExprClass
: {
1009 const DeclRefExpr
*DE
= cast
<DeclRefExpr
>(S
);
1010 VisitCommonDeclRefExpr(DE
, DE
->getDecl(), Pred
, Dst
);
1014 case Stmt::DeclStmtClass
:
1015 VisitDeclStmt(cast
<DeclStmt
>(S
), Pred
, Dst
);
1018 case Stmt::ForStmtClass
:
1019 // This case isn't for branch processing, but for handling the
1020 // initialization of a condition variable.
1021 VisitCondInit(cast
<ForStmt
>(S
)->getConditionVariable(), S
, Pred
, Dst
);
1024 case Stmt::ImplicitCastExprClass
:
1025 case Stmt::CStyleCastExprClass
:
1026 case Stmt::CXXStaticCastExprClass
:
1027 case Stmt::CXXDynamicCastExprClass
:
1028 case Stmt::CXXReinterpretCastExprClass
:
1029 case Stmt::CXXConstCastExprClass
:
1030 case Stmt::CXXFunctionalCastExprClass
: {
1031 const CastExpr
* C
= cast
<CastExpr
>(S
);
1032 VisitCast(C
, C
->getSubExpr(), Pred
, Dst
);
1036 case Stmt::IfStmtClass
:
1037 // This case isn't for branch processing, but for handling the
1038 // initialization of a condition variable.
1039 VisitCondInit(cast
<IfStmt
>(S
)->getConditionVariable(), S
, Pred
, Dst
);
1042 case Stmt::InitListExprClass
:
1043 VisitInitListExpr(cast
<InitListExpr
>(S
), Pred
, Dst
);
1046 case Stmt::MemberExprClass
:
1047 VisitMemberExpr(cast
<MemberExpr
>(S
), Pred
, Dst
);
1049 case Stmt::ObjCIvarRefExprClass
:
1050 VisitLvalObjCIvarRefExpr(cast
<ObjCIvarRefExpr
>(S
), Pred
, Dst
);
1053 case Stmt::ObjCForCollectionStmtClass
:
1054 VisitObjCForCollectionStmt(cast
<ObjCForCollectionStmt
>(S
), Pred
, Dst
);
1057 case Stmt::ObjCMessageExprClass
:
1058 VisitObjCMessageExpr(cast
<ObjCMessageExpr
>(S
), Pred
, Dst
);
1061 case Stmt::ObjCAtThrowStmtClass
: {
1062 // FIXME: This is not complete. We basically treat @throw as
1064 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
1065 Builder
->BuildSinks
= true;
1066 MakeNode(Dst
, S
, Pred
, GetState(Pred
));
1070 case Stmt::ReturnStmtClass
:
1071 VisitReturnStmt(cast
<ReturnStmt
>(S
), Pred
, Dst
);
1074 case Stmt::OffsetOfExprClass
:
1075 VisitOffsetOfExpr(cast
<OffsetOfExpr
>(S
), Pred
, Dst
);
1078 case Stmt::SizeOfAlignOfExprClass
:
1079 VisitSizeOfAlignOfExpr(cast
<SizeOfAlignOfExpr
>(S
), Pred
, Dst
);
1082 case Stmt::StmtExprClass
: {
1083 const StmtExpr
* SE
= cast
<StmtExpr
>(S
);
1085 if (SE
->getSubStmt()->body_empty()) {
1086 // Empty statement expression.
1087 assert(SE
->getType() == getContext().VoidTy
1088 && "Empty statement expression must have void type.");
1093 if (Expr
* LastExpr
= dyn_cast
<Expr
>(*SE
->getSubStmt()->body_rbegin())) {
1094 const GRState
* state
= GetState(Pred
);
1095 MakeNode(Dst
, SE
, Pred
, state
->BindExpr(SE
, state
->getSVal(LastExpr
)));
1103 case Stmt::StringLiteralClass
: {
1104 const GRState
* state
= GetState(Pred
);
1105 SVal V
= state
->getLValue(cast
<StringLiteral
>(S
));
1106 MakeNode(Dst
, S
, Pred
, state
->BindExpr(S
, V
));
1110 case Stmt::SwitchStmtClass
:
1111 // This case isn't for branch processing, but for handling the
1112 // initialization of a condition variable.
1113 VisitCondInit(cast
<SwitchStmt
>(S
)->getConditionVariable(), S
, Pred
, Dst
);
1116 case Stmt::UnaryOperatorClass
: {
1117 const UnaryOperator
*U
= cast
<UnaryOperator
>(S
);
1118 if (AMgr
.shouldEagerlyAssume()&&(U
->getOpcode() == UO_LNot
)) {
1119 ExplodedNodeSet Tmp
;
1120 VisitUnaryOperator(U
, Pred
, Tmp
);
1121 evalEagerlyAssume(Dst
, Tmp
, U
);
1124 VisitUnaryOperator(U
, Pred
, Dst
);
1128 case Stmt::WhileStmtClass
:
1129 // This case isn't for branch processing, but for handling the
1130 // initialization of a condition variable.
1131 VisitCondInit(cast
<WhileStmt
>(S
)->getConditionVariable(), S
, Pred
, Dst
);
1136 //===----------------------------------------------------------------------===//
1137 // Block entrance. (Update counters).
1138 //===----------------------------------------------------------------------===//
1140 void ExprEngine::processCFGBlockEntrance(ExplodedNodeSet
&dstNodes
,
1141 GenericNodeBuilder
<BlockEntrance
> &nodeBuilder
){
1143 // FIXME: Refactor this into a checker.
1144 const CFGBlock
*block
= nodeBuilder
.getProgramPoint().getBlock();
1145 ExplodedNode
*pred
= nodeBuilder
.getPredecessor();
1147 if (nodeBuilder
.getBlockCounter().getNumVisited(
1148 pred
->getLocationContext()->getCurrentStackFrame(),
1149 block
->getBlockID()) >= AMgr
.getMaxVisit()) {
1152 nodeBuilder
.generateNode(pred
->getState(), pred
, &tag
, true);
1156 //===----------------------------------------------------------------------===//
1157 // Generic node creation.
1158 //===----------------------------------------------------------------------===//
1160 ExplodedNode
* ExprEngine::MakeNode(ExplodedNodeSet
& Dst
, const Stmt
* S
,
1161 ExplodedNode
* Pred
, const GRState
* St
,
1162 ProgramPoint::Kind K
, const void *tag
) {
1163 assert (Builder
&& "StmtNodeBuilder not present.");
1164 SaveAndRestore
<const void*> OldTag(Builder
->Tag
);
1166 return Builder
->MakeNode(Dst
, S
, Pred
, St
, K
);
1169 //===----------------------------------------------------------------------===//
1170 // Branch processing.
1171 //===----------------------------------------------------------------------===//
1173 const GRState
* ExprEngine::MarkBranch(const GRState
* state
,
1174 const Stmt
* Terminator
,
1177 switch (Terminator
->getStmtClass()) {
1181 case Stmt::BinaryOperatorClass
: { // '&&' and '||'
1183 const BinaryOperator
* B
= cast
<BinaryOperator
>(Terminator
);
1184 BinaryOperator::Opcode Op
= B
->getOpcode();
1186 assert (Op
== BO_LAnd
|| Op
== BO_LOr
);
1188 // For &&, if we take the true branch, then the value of the whole
1189 // expression is that of the RHS expression.
1191 // For ||, if we take the false branch, then the value of the whole
1192 // expression is that of the RHS expression.
1194 const Expr
* Ex
= (Op
== BO_LAnd
&& branchTaken
) ||
1195 (Op
== BO_LOr
&& !branchTaken
)
1196 ? B
->getRHS() : B
->getLHS();
1198 return state
->BindExpr(B
, UndefinedVal(Ex
));
1201 case Stmt::ConditionalOperatorClass
: { // ?:
1203 const ConditionalOperator
* C
= cast
<ConditionalOperator
>(Terminator
);
1205 // For ?, if branchTaken == true then the value is either the LHS or
1206 // the condition itself. (GNU extension).
1211 Ex
= C
->getLHS() ? C
->getLHS() : C
->getCond();
1215 return state
->BindExpr(C
, UndefinedVal(Ex
));
1218 case Stmt::ChooseExprClass
: { // ?:
1220 const ChooseExpr
* C
= cast
<ChooseExpr
>(Terminator
);
1222 const Expr
* Ex
= branchTaken
? C
->getLHS() : C
->getRHS();
1223 return state
->BindExpr(C
, UndefinedVal(Ex
));
1228 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1229 /// to try to recover some path-sensitivity for casts of symbolic
1230 /// integers that promote their values (which are currently not tracked well).
1231 /// This function returns the SVal bound to Condition->IgnoreCasts if all the
1232 // cast(s) did was sign-extend the original value.
1233 static SVal
RecoverCastedSymbol(GRStateManager
& StateMgr
, const GRState
* state
,
1234 const Stmt
* Condition
, ASTContext
& Ctx
) {
1236 const Expr
*Ex
= dyn_cast
<Expr
>(Condition
);
1238 return UnknownVal();
1241 bool bitsInit
= false;
1243 while (const CastExpr
*CE
= dyn_cast
<CastExpr
>(Ex
)) {
1244 QualType T
= CE
->getType();
1246 if (!T
->isIntegerType())
1247 return UnknownVal();
1249 uint64_t newBits
= Ctx
.getTypeSize(T
);
1250 if (!bitsInit
|| newBits
< bits
) {
1255 Ex
= CE
->getSubExpr();
1258 // We reached a non-cast. Is it a symbolic value?
1259 QualType T
= Ex
->getType();
1261 if (!bitsInit
|| !T
->isIntegerType() || Ctx
.getTypeSize(T
) > bits
)
1262 return UnknownVal();
1264 return state
->getSVal(Ex
);
1267 void ExprEngine::processBranch(const Stmt
* Condition
, const Stmt
* Term
,
1268 BranchNodeBuilder
& builder
) {
1270 // Check for NULL conditions; e.g. "for(;;)"
1272 builder
.markInfeasible(false);
1276 PrettyStackTraceLoc
CrashInfo(getContext().getSourceManager(),
1277 Condition
->getLocStart(),
1278 "Error evaluating branch");
1280 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end();I
!=E
;++I
) {
1281 void *tag
= I
->first
;
1282 Checker
*checker
= I
->second
;
1283 checker
->VisitBranchCondition(builder
, *this, Condition
, tag
);
1286 // If the branch condition is undefined, return;
1287 if (!builder
.isFeasible(true) && !builder
.isFeasible(false))
1290 const GRState
* PrevState
= builder
.getState();
1291 SVal X
= PrevState
->getSVal(Condition
);
1293 if (X
.isUnknown()) {
1294 // Give it a chance to recover from unknown.
1295 if (const Expr
*Ex
= dyn_cast
<Expr
>(Condition
)) {
1296 if (Ex
->getType()->isIntegerType()) {
1297 // Try to recover some path-sensitivity. Right now casts of symbolic
1298 // integers that promote their values are currently not tracked well.
1299 // If 'Condition' is such an expression, try and recover the
1300 // underlying value and use that instead.
1301 SVal recovered
= RecoverCastedSymbol(getStateManager(),
1302 builder
.getState(), Condition
,
1305 if (!recovered
.isUnknown()) {
1310 // If the condition is still unknown, give up.
1311 if (X
.isUnknown()) {
1312 builder
.generateNode(MarkBranch(PrevState
, Term
, true), true);
1313 builder
.generateNode(MarkBranch(PrevState
, Term
, false), false);
1318 DefinedSVal V
= cast
<DefinedSVal
>(X
);
1320 // Process the true branch.
1321 if (builder
.isFeasible(true)) {
1322 if (const GRState
*state
= PrevState
->assume(V
, true))
1323 builder
.generateNode(MarkBranch(state
, Term
, true), true);
1325 builder
.markInfeasible(true);
1328 // Process the false branch.
1329 if (builder
.isFeasible(false)) {
1330 if (const GRState
*state
= PrevState
->assume(V
, false))
1331 builder
.generateNode(MarkBranch(state
, Term
, false), false);
1333 builder
.markInfeasible(false);
1337 /// processIndirectGoto - Called by CoreEngine. Used to generate successor
1338 /// nodes by processing the 'effects' of a computed goto jump.
1339 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder
& builder
) {
1341 const GRState
*state
= builder
.getState();
1342 SVal V
= state
->getSVal(builder
.getTarget());
1344 // Three possibilities:
1346 // (1) We know the computed label.
1347 // (2) The label is NULL (or some other constant), or Undefined.
1348 // (3) We have no clue about the label. Dispatch to all targets.
1351 typedef IndirectGotoNodeBuilder::iterator iterator
;
1353 if (isa
<loc::GotoLabel
>(V
)) {
1354 const LabelStmt
* L
= cast
<loc::GotoLabel
>(V
).getLabel();
1356 for (iterator I
=builder
.begin(), E
=builder
.end(); I
!= E
; ++I
) {
1357 if (I
.getLabel() == L
) {
1358 builder
.generateNode(I
, state
);
1363 assert (false && "No block with label.");
1367 if (isa
<loc::ConcreteInt
>(V
) || isa
<UndefinedVal
>(V
)) {
1368 // Dispatch to the first target and mark it as a sink.
1369 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1370 // FIXME: add checker visit.
1371 // UndefBranches.insert(N);
1375 // This is really a catch-all. We don't support symbolics yet.
1376 // FIXME: Implement dispatch for symbolic pointers.
1378 for (iterator I
=builder
.begin(), E
=builder
.end(); I
!= E
; ++I
)
1379 builder
.generateNode(I
, state
);
1383 void ExprEngine::VisitGuardedExpr(const Expr
* Ex
, const Expr
* L
,
1385 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
) {
1387 assert(Ex
== currentStmt
&&
1388 Pred
->getLocationContext()->getCFG()->isBlkExpr(Ex
));
1390 const GRState
* state
= GetState(Pred
);
1391 SVal X
= state
->getSVal(Ex
);
1393 assert (X
.isUndef());
1395 const Expr
*SE
= (Expr
*) cast
<UndefinedVal
>(X
).getData();
1397 X
= state
->getSVal(SE
);
1399 // Make sure that we invalidate the previous binding.
1400 MakeNode(Dst
, Ex
, Pred
, state
->BindExpr(Ex
, X
, true));
1403 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
1404 /// nodes when the control reaches the end of a function.
1405 void ExprEngine::processEndOfFunction(EndOfFunctionNodeBuilder
& builder
) {
1406 getTF().evalEndPath(*this, builder
);
1407 StateMgr
.EndPath(builder
.getState());
1408 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end(); I
!=E
;++I
){
1409 void *tag
= I
->first
;
1410 Checker
*checker
= I
->second
;
1411 checker
->evalEndPath(builder
, tag
, *this);
1415 /// ProcessSwitch - Called by CoreEngine. Used to generate successor
1416 /// nodes by processing the 'effects' of a switch statement.
1417 void ExprEngine::processSwitch(SwitchNodeBuilder
& builder
) {
1418 typedef SwitchNodeBuilder::iterator iterator
;
1419 const GRState
* state
= builder
.getState();
1420 const Expr
* CondE
= builder
.getCondition();
1421 SVal CondV_untested
= state
->getSVal(CondE
);
1423 if (CondV_untested
.isUndef()) {
1424 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1425 // FIXME: add checker
1426 //UndefBranches.insert(N);
1430 DefinedOrUnknownSVal CondV
= cast
<DefinedOrUnknownSVal
>(CondV_untested
);
1432 const GRState
*DefaultSt
= state
;
1434 iterator I
= builder
.begin(), EI
= builder
.end();
1435 bool defaultIsFeasible
= I
== EI
;
1437 for ( ; I
!= EI
; ++I
) {
1438 const CaseStmt
* Case
= I
.getCase();
1440 // Evaluate the LHS of the case value.
1441 Expr::EvalResult V1
;
1442 bool b
= Case
->getLHS()->Evaluate(V1
, getContext());
1444 // Sanity checks. These go away in Release builds.
1445 assert(b
&& V1
.Val
.isInt() && !V1
.HasSideEffects
1446 && "Case condition must evaluate to an integer constant.");
1447 (void)b
; // silence unused variable warning
1448 assert(V1
.Val
.getInt().getBitWidth() ==
1449 getContext().getTypeSize(CondE
->getType()));
1451 // Get the RHS of the case, if it exists.
1452 Expr::EvalResult V2
;
1454 if (const Expr
* E
= Case
->getRHS()) {
1455 b
= E
->Evaluate(V2
, getContext());
1456 assert(b
&& V2
.Val
.isInt() && !V2
.HasSideEffects
1457 && "Case condition must evaluate to an integer constant.");
1458 (void)b
; // silence unused variable warning
1463 // FIXME: Eventually we should replace the logic below with a range
1464 // comparison, rather than concretize the values within the range.
1465 // This should be easy once we have "ranges" for NonLVals.
1468 nonloc::ConcreteInt
CaseVal(getBasicVals().getValue(V1
.Val
.getInt()));
1469 DefinedOrUnknownSVal Res
= svalBuilder
.evalEQ(DefaultSt
? DefaultSt
: state
,
1472 // Now "assume" that the case matches.
1473 if (const GRState
* stateNew
= state
->assume(Res
, true)) {
1474 builder
.generateCaseStmtNode(I
, stateNew
);
1476 // If CondV evaluates to a constant, then we know that this
1477 // is the *only* case that we can take, so stop evaluating the
1479 if (isa
<nonloc::ConcreteInt
>(CondV
))
1483 // Now "assume" that the case doesn't match. Add this state
1484 // to the default state (if it is feasible).
1486 if (const GRState
*stateNew
= DefaultSt
->assume(Res
, false)) {
1487 defaultIsFeasible
= true;
1488 DefaultSt
= stateNew
;
1491 defaultIsFeasible
= false;
1496 // Concretize the next value in the range.
1497 if (V1
.Val
.getInt() == V2
.Val
.getInt())
1501 assert (V1
.Val
.getInt() <= V2
.Val
.getInt());
1506 if (!defaultIsFeasible
)
1509 // If we have switch(enum value), the default branch is not
1510 // feasible if all of the enum constants not covered by 'case:' statements
1511 // are not feasible values for the switch condition.
1513 // Note that this isn't as accurate as it could be. Even if there isn't
1514 // a case for a particular enum value as long as that enum value isn't
1515 // feasible then it shouldn't be considered for making 'default:' reachable.
1516 const SwitchStmt
*SS
= builder
.getSwitch();
1517 const Expr
*CondExpr
= SS
->getCond()->IgnoreParenImpCasts();
1518 if (CondExpr
->getType()->getAs
<EnumType
>()) {
1519 if (SS
->isAllEnumCasesCovered())
1523 builder
.generateDefaultCaseNode(DefaultSt
);
1526 void ExprEngine::processCallEnter(CallEnterNodeBuilder
&B
) {
1527 const GRState
*state
= B
.getState()->enterStackFrame(B
.getCalleeContext());
1528 B
.generateNode(state
);
1531 void ExprEngine::processCallExit(CallExitNodeBuilder
&B
) {
1532 const GRState
*state
= B
.getState();
1533 const ExplodedNode
*Pred
= B
.getPredecessor();
1534 const StackFrameContext
*calleeCtx
=
1535 cast
<StackFrameContext
>(Pred
->getLocationContext());
1536 const Stmt
*CE
= calleeCtx
->getCallSite();
1538 // If the callee returns an expression, bind its value to CallExpr.
1539 const Stmt
*ReturnedExpr
= state
->get
<ReturnExpr
>();
1541 SVal RetVal
= state
->getSVal(ReturnedExpr
);
1542 state
= state
->BindExpr(CE
, RetVal
);
1543 // Clear the return expr GDM.
1544 state
= state
->remove
<ReturnExpr
>();
1547 // Bind the constructed object value to CXXConstructExpr.
1548 if (const CXXConstructExpr
*CCE
= dyn_cast
<CXXConstructExpr
>(CE
)) {
1549 const CXXThisRegion
*ThisR
=
1550 getCXXThisRegion(CCE
->getConstructor()->getParent(), calleeCtx
);
1552 SVal ThisV
= state
->getSVal(ThisR
);
1553 // Always bind the region to the CXXConstructExpr.
1554 state
= state
->BindExpr(CCE
, ThisV
);
1557 B
.generateNode(state
);
1560 //===----------------------------------------------------------------------===//
1561 // Transfer functions: logical operations ('&&', '||').
1562 //===----------------------------------------------------------------------===//
1564 void ExprEngine::VisitLogicalExpr(const BinaryOperator
* B
, ExplodedNode
* Pred
,
1565 ExplodedNodeSet
& Dst
) {
1567 assert(B
->getOpcode() == BO_LAnd
||
1568 B
->getOpcode() == BO_LOr
);
1570 assert(B
==currentStmt
&& Pred
->getLocationContext()->getCFG()->isBlkExpr(B
));
1572 const GRState
* state
= GetState(Pred
);
1573 SVal X
= state
->getSVal(B
);
1574 assert(X
.isUndef());
1576 const Expr
*Ex
= (const Expr
*) cast
<UndefinedVal
>(X
).getData();
1579 if (Ex
== B
->getRHS()) {
1580 X
= state
->getSVal(Ex
);
1582 // Handle undefined values.
1584 MakeNode(Dst
, B
, Pred
, state
->BindExpr(B
, X
));
1588 DefinedOrUnknownSVal XD
= cast
<DefinedOrUnknownSVal
>(X
);
1590 // We took the RHS. Because the value of the '&&' or '||' expression must
1591 // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
1592 // or 1. Alternatively, we could take a lazy approach, and calculate this
1593 // value later when necessary. We don't have the machinery in place for
1594 // this right now, and since most logical expressions are used for branches,
1595 // the payoff is not likely to be large. Instead, we do eager evaluation.
1596 if (const GRState
*newState
= state
->assume(XD
, true))
1597 MakeNode(Dst
, B
, Pred
,
1598 newState
->BindExpr(B
, svalBuilder
.makeIntVal(1U, B
->getType())));
1600 if (const GRState
*newState
= state
->assume(XD
, false))
1601 MakeNode(Dst
, B
, Pred
,
1602 newState
->BindExpr(B
, svalBuilder
.makeIntVal(0U, B
->getType())));
1605 // We took the LHS expression. Depending on whether we are '&&' or
1606 // '||' we know what the value of the expression is via properties of
1607 // the short-circuiting.
1608 X
= svalBuilder
.makeIntVal(B
->getOpcode() == BO_LAnd
? 0U : 1U,
1610 MakeNode(Dst
, B
, Pred
, state
->BindExpr(B
, X
));
1614 //===----------------------------------------------------------------------===//
1615 // Transfer functions: Loads and stores.
1616 //===----------------------------------------------------------------------===//
1618 void ExprEngine::VisitBlockExpr(const BlockExpr
*BE
, ExplodedNode
*Pred
,
1619 ExplodedNodeSet
&Dst
) {
1621 ExplodedNodeSet Tmp
;
1623 CanQualType T
= getContext().getCanonicalType(BE
->getType());
1624 SVal V
= svalBuilder
.getBlockPointer(BE
->getBlockDecl(), T
,
1625 Pred
->getLocationContext());
1627 MakeNode(Tmp
, BE
, Pred
, GetState(Pred
)->BindExpr(BE
, V
),
1628 ProgramPoint::PostLValueKind
);
1630 // Post-visit the BlockExpr.
1631 CheckerVisit(BE
, Dst
, Tmp
, PostVisitStmtCallback
);
1634 void ExprEngine::VisitCommonDeclRefExpr(const Expr
*Ex
, const NamedDecl
*D
,
1636 ExplodedNodeSet
&Dst
) {
1637 const GRState
*state
= GetState(Pred
);
1639 if (const VarDecl
* VD
= dyn_cast
<VarDecl
>(D
)) {
1640 assert(Ex
->isLValue());
1641 SVal V
= state
->getLValue(VD
, Pred
->getLocationContext());
1643 // For references, the 'lvalue' is the pointer address stored in the
1644 // reference region.
1645 if (VD
->getType()->isReferenceType()) {
1646 if (const MemRegion
*R
= V
.getAsRegion())
1647 V
= state
->getSVal(R
);
1652 MakeNode(Dst
, Ex
, Pred
, state
->BindExpr(Ex
, V
),
1653 ProgramPoint::PostLValueKind
);
1656 if (const EnumConstantDecl
* ED
= dyn_cast
<EnumConstantDecl
>(D
)) {
1657 assert(!Ex
->isLValue());
1658 SVal V
= svalBuilder
.makeIntVal(ED
->getInitVal());
1659 MakeNode(Dst
, Ex
, Pred
, state
->BindExpr(Ex
, V
));
1662 if (const FunctionDecl
* FD
= dyn_cast
<FunctionDecl
>(D
)) {
1663 SVal V
= svalBuilder
.getFunctionPointer(FD
);
1664 MakeNode(Dst
, Ex
, Pred
, state
->BindExpr(Ex
, V
),
1665 ProgramPoint::PostLValueKind
);
1669 "ValueDecl support for this ValueDecl not implemented.");
1672 /// VisitArraySubscriptExpr - Transfer function for array accesses
1673 void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr
* A
,
1675 ExplodedNodeSet
& Dst
){
1677 const Expr
* Base
= A
->getBase()->IgnoreParens();
1678 const Expr
* Idx
= A
->getIdx()->IgnoreParens();
1680 // Evaluate the base.
1681 ExplodedNodeSet Tmp
;
1682 Visit(Base
, Pred
, Tmp
);
1684 for (ExplodedNodeSet::iterator I1
=Tmp
.begin(), E1
=Tmp
.end(); I1
!=E1
; ++I1
) {
1685 ExplodedNodeSet Tmp2
;
1686 Visit(Idx
, *I1
, Tmp2
); // Evaluate the index.
1687 ExplodedNodeSet Tmp3
;
1688 CheckerVisit(A
, Tmp3
, Tmp2
, PreVisitStmtCallback
);
1690 for (ExplodedNodeSet::iterator I2
=Tmp3
.begin(),E2
=Tmp3
.end();I2
!=E2
; ++I2
) {
1691 const GRState
* state
= GetState(*I2
);
1692 SVal V
= state
->getLValue(A
->getType(), state
->getSVal(Idx
),
1693 state
->getSVal(Base
));
1694 assert(A
->isLValue());
1695 MakeNode(Dst
, A
, *I2
, state
->BindExpr(A
, V
), ProgramPoint::PostLValueKind
);
1700 /// VisitMemberExpr - Transfer function for member expressions.
1701 void ExprEngine::VisitMemberExpr(const MemberExpr
* M
, ExplodedNode
* Pred
,
1702 ExplodedNodeSet
& Dst
) {
1704 Expr
*baseExpr
= M
->getBase()->IgnoreParens();
1705 ExplodedNodeSet dstBase
;
1706 Visit(baseExpr
, Pred
, dstBase
);
1708 FieldDecl
*field
= dyn_cast
<FieldDecl
>(M
->getMemberDecl());
1709 if (!field
) // FIXME: skipping member expressions for non-fields
1712 for (ExplodedNodeSet::iterator I
= dstBase
.begin(), E
= dstBase
.end();
1714 const GRState
* state
= GetState(*I
);
1715 SVal baseExprVal
= state
->getSVal(baseExpr
);
1716 if (isa
<nonloc::LazyCompoundVal
>(baseExprVal
) ||
1717 isa
<nonloc::CompoundVal
>(baseExprVal
)) {
1718 MakeNode(Dst
, M
, *I
, state
->BindExpr(M
, UnknownVal()));
1722 // FIXME: Should we insert some assumption logic in here to determine
1723 // if "Base" is a valid piece of memory? Before we put this assumption
1724 // later when using FieldOffset lvals (which we no longer have).
1726 // For all other cases, compute an lvalue.
1727 SVal L
= state
->getLValue(field
, baseExprVal
);
1729 MakeNode(Dst
, M
, *I
, state
->BindExpr(M
, L
), ProgramPoint::PostLValueKind
);
1731 evalLoad(Dst
, M
, *I
, state
, L
);
1735 /// evalBind - Handle the semantics of binding a value to a specific location.
1736 /// This method is used by evalStore and (soon) VisitDeclStmt, and others.
1737 void ExprEngine::evalBind(ExplodedNodeSet
& Dst
, const Stmt
* StoreE
,
1738 ExplodedNode
* Pred
, const GRState
* state
,
1739 SVal location
, SVal Val
, bool atDeclInit
) {
1742 // Do a previsit of the bind.
1743 ExplodedNodeSet CheckedSet
, Src
;
1745 CheckerVisitBind(StoreE
, CheckedSet
, Src
, location
, Val
, true);
1747 for (ExplodedNodeSet::iterator I
= CheckedSet
.begin(), E
= CheckedSet
.end();
1751 state
= GetState(*I
);
1753 const GRState
* newState
= 0;
1756 const VarRegion
*VR
=
1757 cast
<VarRegion
>(cast
<loc::MemRegionVal
>(location
).getRegion());
1759 newState
= state
->bindDecl(VR
, Val
);
1762 if (location
.isUnknown()) {
1763 // We know that the new state will be the same as the old state since
1764 // the location of the binding is "unknown". Consequently, there
1765 // is no reason to just create a new node.
1769 // We are binding to a value other than 'unknown'. Perform the binding
1770 // using the StoreManager.
1771 newState
= state
->bindLoc(cast
<Loc
>(location
), Val
);
1775 // The next thing to do is check if the TransferFuncs object wants to
1776 // update the state based on the new binding. If the GRTransferFunc object
1777 // doesn't do anything, just auto-propagate the current state.
1779 // NOTE: We use 'AssignE' for the location of the PostStore if 'AssignE'
1780 // is non-NULL. Checkers typically care about
1782 StmtNodeBuilderRef
BuilderRef(Dst
, *Builder
, *this, *I
, newState
, StoreE
,
1785 getTF().evalBind(BuilderRef
, location
, Val
);
1789 /// evalStore - Handle the semantics of a store via an assignment.
1790 /// @param Dst The node set to store generated state nodes
1791 /// @param AssignE The assignment expression if the store happens in an
1793 /// @param LocatioinE The location expression that is stored to.
1794 /// @param state The current simulation state
1795 /// @param location The location to store the value
1796 /// @param Val The value to be stored
1797 void ExprEngine::evalStore(ExplodedNodeSet
& Dst
, const Expr
*AssignE
,
1798 const Expr
* LocationE
,
1800 const GRState
* state
, SVal location
, SVal Val
,
1803 assert(Builder
&& "StmtNodeBuilder must be defined.");
1805 // Proceed with the store. We use AssignE as the anchor for the PostStore
1806 // ProgramPoint if it is non-NULL, and LocationE otherwise.
1807 const Expr
*StoreE
= AssignE
? AssignE
: LocationE
;
1809 if (isa
<loc::ObjCPropRef
>(location
)) {
1810 loc::ObjCPropRef prop
= cast
<loc::ObjCPropRef
>(location
);
1811 ExplodedNodeSet src
= Pred
;
1812 return VisitObjCMessage(ObjCPropertySetter(prop
.getPropRefExpr(),
1813 StoreE
, Val
), src
, Dst
);
1816 // Evaluate the location (checks for bad dereferences).
1817 ExplodedNodeSet Tmp
;
1818 evalLocation(Tmp
, LocationE
, Pred
, state
, location
, tag
, false);
1823 assert(!location
.isUndef());
1825 SaveAndRestore
<ProgramPoint::Kind
> OldSPointKind(Builder
->PointKind
,
1826 ProgramPoint::PostStoreKind
);
1828 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(), NE
=Tmp
.end(); NI
!=NE
; ++NI
)
1829 evalBind(Dst
, StoreE
, *NI
, GetState(*NI
), location
, Val
);
1832 void ExprEngine::evalLoad(ExplodedNodeSet
& Dst
, const Expr
*Ex
,
1834 const GRState
* state
, SVal location
,
1835 const void *tag
, QualType LoadTy
) {
1836 assert(!isa
<NonLoc
>(location
) && "location cannot be a NonLoc.");
1838 if (isa
<loc::ObjCPropRef
>(location
)) {
1839 loc::ObjCPropRef prop
= cast
<loc::ObjCPropRef
>(location
);
1840 ExplodedNodeSet src
= Pred
;
1841 return VisitObjCMessage(ObjCPropertyGetter(prop
.getPropRefExpr(), Ex
),
1845 // Are we loading from a region? This actually results in two loads; one
1846 // to fetch the address of the referenced value and one to fetch the
1847 // referenced value.
1848 if (const TypedRegion
*TR
=
1849 dyn_cast_or_null
<TypedRegion
>(location
.getAsRegion())) {
1851 QualType ValTy
= TR
->getValueType();
1852 if (const ReferenceType
*RT
= ValTy
->getAs
<ReferenceType
>()) {
1853 static int loadReferenceTag
= 0;
1854 ExplodedNodeSet Tmp
;
1855 evalLoadCommon(Tmp
, Ex
, Pred
, state
, location
, &loadReferenceTag
,
1856 getContext().getPointerType(RT
->getPointeeType()));
1858 // Perform the load from the referenced value.
1859 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end() ; I
!=E
; ++I
) {
1860 state
= GetState(*I
);
1861 location
= state
->getSVal(Ex
);
1862 evalLoadCommon(Dst
, Ex
, *I
, state
, location
, tag
, LoadTy
);
1868 evalLoadCommon(Dst
, Ex
, Pred
, state
, location
, tag
, LoadTy
);
1871 void ExprEngine::evalLoadCommon(ExplodedNodeSet
& Dst
, const Expr
*Ex
,
1873 const GRState
* state
, SVal location
,
1874 const void *tag
, QualType LoadTy
) {
1876 // Evaluate the location (checks for bad dereferences).
1877 ExplodedNodeSet Tmp
;
1878 evalLocation(Tmp
, Ex
, Pred
, state
, location
, tag
, true);
1883 assert(!location
.isUndef());
1885 SaveAndRestore
<ProgramPoint::Kind
> OldSPointKind(Builder
->PointKind
);
1887 // Proceed with the load.
1888 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(), NE
=Tmp
.end(); NI
!=NE
; ++NI
) {
1889 state
= GetState(*NI
);
1891 if (location
.isUnknown()) {
1892 // This is important. We must nuke the old binding.
1893 MakeNode(Dst
, Ex
, *NI
, state
->BindExpr(Ex
, UnknownVal()),
1894 ProgramPoint::PostLoadKind
, tag
);
1897 if (LoadTy
.isNull())
1898 LoadTy
= Ex
->getType();
1899 SVal V
= state
->getSVal(cast
<Loc
>(location
), LoadTy
);
1900 MakeNode(Dst
, Ex
, *NI
, state
->bindExprAndLocation(Ex
, location
, V
),
1901 ProgramPoint::PostLoadKind
, tag
);
1906 void ExprEngine::evalLocation(ExplodedNodeSet
&Dst
, const Stmt
*S
,
1908 const GRState
* state
, SVal location
,
1909 const void *tag
, bool isLoad
) {
1910 // Early checks for performance reason.
1911 if (location
.isUnknown() || Checkers
.empty()) {
1916 ExplodedNodeSet Src
, Tmp
;
1918 ExplodedNodeSet
*PrevSet
= &Src
;
1920 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end(); I
!=E
; ++I
)
1922 ExplodedNodeSet
*CurrSet
= 0;
1926 CurrSet
= (PrevSet
== &Tmp
) ? &Src
: &Tmp
;
1930 void *tag
= I
->first
;
1931 Checker
*checker
= I
->second
;
1933 for (ExplodedNodeSet::iterator NI
= PrevSet
->begin(), NE
= PrevSet
->end();
1935 // Use the 'state' argument only when the predecessor node is the
1936 // same as Pred. This allows us to catch updates to the state.
1937 checker
->GR_visitLocation(*CurrSet
, *Builder
, *this, S
, *NI
,
1938 *NI
== Pred
? state
: GetState(*NI
),
1939 location
, tag
, isLoad
);
1942 // Update which NodeSet is the current one.
1947 bool ExprEngine::InlineCall(ExplodedNodeSet
&Dst
, const CallExpr
*CE
,
1948 ExplodedNode
*Pred
) {
1949 const GRState
*state
= GetState(Pred
);
1950 const Expr
*Callee
= CE
->getCallee();
1951 SVal L
= state
->getSVal(Callee
);
1953 const FunctionDecl
*FD
= L
.getAsFunctionDecl();
1957 // Check if the function definition is in the same translation unit.
1958 if (FD
->hasBody(FD
)) {
1959 const StackFrameContext
*stackFrame
=
1960 AMgr
.getStackFrame(AMgr
.getAnalysisContext(FD
),
1961 Pred
->getLocationContext(),
1962 CE
, Builder
->getBlock(), Builder
->getIndex());
1963 // Now we have the definition of the callee, create a CallEnter node.
1964 CallEnter
Loc(CE
, stackFrame
, Pred
->getLocationContext());
1966 ExplodedNode
*N
= Builder
->generateNode(Loc
, state
, Pred
);
1971 // Check if we can find the function definition in other translation units.
1972 if (AMgr
.hasIndexer()) {
1973 AnalysisContext
*C
= AMgr
.getAnalysisContextInAnotherTU(FD
);
1976 const StackFrameContext
*stackFrame
=
1977 AMgr
.getStackFrame(C
, Pred
->getLocationContext(),
1978 CE
, Builder
->getBlock(), Builder
->getIndex());
1979 CallEnter
Loc(CE
, stackFrame
, Pred
->getLocationContext());
1980 ExplodedNode
*N
= Builder
->generateNode(Loc
, state
, Pred
);
1988 void ExprEngine::VisitCall(const CallExpr
* CE
, ExplodedNode
* Pred
,
1989 CallExpr::const_arg_iterator AI
,
1990 CallExpr::const_arg_iterator AE
,
1991 ExplodedNodeSet
& Dst
) {
1993 // Determine the type of function we're calling (if available).
1994 const FunctionProtoType
*Proto
= NULL
;
1995 QualType FnType
= CE
->getCallee()->IgnoreParens()->getType();
1996 if (const PointerType
*FnTypePtr
= FnType
->getAs
<PointerType
>())
1997 Proto
= FnTypePtr
->getPointeeType()->getAs
<FunctionProtoType
>();
1999 // Evaluate the arguments.
2000 ExplodedNodeSet ArgsEvaluated
;
2001 evalArguments(CE
->arg_begin(), CE
->arg_end(), Proto
, Pred
, ArgsEvaluated
);
2003 // Now process the call itself.
2004 ExplodedNodeSet DstTmp
;
2005 const Expr
* Callee
= CE
->getCallee()->IgnoreParens();
2007 for (ExplodedNodeSet::iterator NI
=ArgsEvaluated
.begin(),
2008 NE
=ArgsEvaluated
.end(); NI
!= NE
; ++NI
) {
2009 // Evaluate the callee.
2010 ExplodedNodeSet DstTmp2
;
2011 Visit(Callee
, *NI
, DstTmp2
);
2012 // Perform the previsit of the CallExpr, storing the results in DstTmp.
2013 CheckerVisit(CE
, DstTmp
, DstTmp2
, PreVisitStmtCallback
);
2016 // Finally, evaluate the function call. We try each of the checkers
2017 // to see if the can evaluate the function call.
2018 ExplodedNodeSet DstTmp3
;
2020 for (ExplodedNodeSet::iterator DI
= DstTmp
.begin(), DE
= DstTmp
.end();
2023 const GRState
* state
= GetState(*DI
);
2024 SVal L
= state
->getSVal(Callee
);
2026 // FIXME: Add support for symbolic function calls (calls involving
2027 // function pointer values that are symbolic).
2028 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
2029 ExplodedNodeSet DstChecker
;
2031 // If the callee is processed by a checker, skip the rest logic.
2032 if (CheckerEvalCall(CE
, DstChecker
, *DI
))
2033 DstTmp3
.insert(DstChecker
);
2034 else if (AMgr
.shouldInlineCall() && InlineCall(Dst
, CE
, *DI
)) {
2035 // Callee is inlined. We shouldn't do post call checking.
2039 for (ExplodedNodeSet::iterator DI_Checker
= DstChecker
.begin(),
2040 DE_Checker
= DstChecker
.end();
2041 DI_Checker
!= DE_Checker
; ++DI_Checker
) {
2043 // Dispatch to the plug-in transfer function.
2044 unsigned oldSize
= DstTmp3
.size();
2045 SaveOr
OldHasGen(Builder
->hasGeneratedNode
);
2048 // Dispatch to transfer function logic to handle the call itself.
2049 // FIXME: Allow us to chain together transfer functions.
2050 assert(Builder
&& "StmtNodeBuilder must be defined.");
2051 getTF().evalCall(DstTmp3
, *this, *Builder
, CE
, L
, Pred
);
2053 // Handle the case where no nodes where generated. Auto-generate that
2054 // contains the updated state if we aren't generating sinks.
2055 if (!Builder
->BuildSinks
&& DstTmp3
.size() == oldSize
&&
2056 !Builder
->hasGeneratedNode
)
2057 MakeNode(DstTmp3
, CE
, Pred
, state
);
2062 // Finally, perform the post-condition check of the CallExpr and store
2063 // the created nodes in 'Dst'.
2064 CheckerVisit(CE
, Dst
, DstTmp3
, PostVisitStmtCallback
);
2067 //===----------------------------------------------------------------------===//
2068 // Transfer function: Objective-C dot-syntax to access a property.
2069 //===----------------------------------------------------------------------===//
2071 void ExprEngine::VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr
*Ex
,
2073 ExplodedNodeSet
&Dst
) {
2075 // Visit the base expression, which is needed for computing the lvalue
2077 ExplodedNodeSet dstBase
;
2078 const Expr
*baseExpr
= Ex
->getBase();
2079 Visit(baseExpr
, Pred
, dstBase
);
2081 ExplodedNodeSet dstPropRef
;
2083 // Using the base, compute the lvalue of the instance variable.
2084 for (ExplodedNodeSet::iterator I
= dstBase
.begin(), E
= dstBase
.end();
2086 ExplodedNode
*nodeBase
= *I
;
2087 const GRState
*state
= GetState(nodeBase
);
2088 SVal baseVal
= state
->getSVal(baseExpr
);
2089 MakeNode(dstPropRef
, Ex
, *I
, state
->BindExpr(Ex
, loc::ObjCPropRef(Ex
)));
2092 Dst
.insert(dstPropRef
);
2095 //===----------------------------------------------------------------------===//
2096 // Transfer function: Objective-C ivar references.
2097 //===----------------------------------------------------------------------===//
2099 static std::pair
<const void*,const void*> EagerlyAssumeTag
2100 = std::pair
<const void*,const void*>(&EagerlyAssumeTag
,static_cast<void*>(0));
2102 void ExprEngine::evalEagerlyAssume(ExplodedNodeSet
&Dst
, ExplodedNodeSet
&Src
,
2104 for (ExplodedNodeSet::iterator I
=Src
.begin(), E
=Src
.end(); I
!=E
; ++I
) {
2105 ExplodedNode
*Pred
= *I
;
2107 // Test if the previous node was as the same expression. This can happen
2108 // when the expression fails to evaluate to anything meaningful and
2109 // (as an optimization) we don't generate a node.
2110 ProgramPoint P
= Pred
->getLocation();
2111 if (!isa
<PostStmt
>(P
) || cast
<PostStmt
>(P
).getStmt() != Ex
) {
2116 const GRState
* state
= GetState(Pred
);
2117 SVal V
= state
->getSVal(Ex
);
2118 if (nonloc::SymExprVal
*SEV
= dyn_cast
<nonloc::SymExprVal
>(&V
)) {
2119 // First assume that the condition is true.
2120 if (const GRState
*stateTrue
= state
->assume(*SEV
, true)) {
2121 stateTrue
= stateTrue
->BindExpr(Ex
,
2122 svalBuilder
.makeIntVal(1U, Ex
->getType()));
2123 Dst
.Add(Builder
->generateNode(PostStmtCustom(Ex
,
2124 &EagerlyAssumeTag
, Pred
->getLocationContext()),
2128 // Next, assume that the condition is false.
2129 if (const GRState
*stateFalse
= state
->assume(*SEV
, false)) {
2130 stateFalse
= stateFalse
->BindExpr(Ex
,
2131 svalBuilder
.makeIntVal(0U, Ex
->getType()));
2132 Dst
.Add(Builder
->generateNode(PostStmtCustom(Ex
, &EagerlyAssumeTag
,
2133 Pred
->getLocationContext()),
2142 //===----------------------------------------------------------------------===//
2143 // Transfer function: Objective-C @synchronized.
2144 //===----------------------------------------------------------------------===//
2146 void ExprEngine::VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt
*S
,
2148 ExplodedNodeSet
&Dst
) {
2150 // The mutex expression is a CFGElement, so we don't need to explicitly
2151 // visit it since it will already be processed.
2153 // Pre-visit the ObjCAtSynchronizedStmt.
2154 ExplodedNodeSet Tmp
;
2156 CheckerVisit(S
, Dst
, Tmp
, PreVisitStmtCallback
);
2159 //===----------------------------------------------------------------------===//
2160 // Transfer function: Objective-C ivar references.
2161 //===----------------------------------------------------------------------===//
2163 void ExprEngine::VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr
* Ex
,
2165 ExplodedNodeSet
& Dst
) {
2167 // Visit the base expression, which is needed for computing the lvalue
2169 ExplodedNodeSet dstBase
;
2170 const Expr
*baseExpr
= Ex
->getBase();
2171 Visit(baseExpr
, Pred
, dstBase
);
2173 ExplodedNodeSet dstIvar
;
2175 // Using the base, compute the lvalue of the instance variable.
2176 for (ExplodedNodeSet::iterator I
= dstBase
.begin(), E
= dstBase
.end();
2178 ExplodedNode
*nodeBase
= *I
;
2179 const GRState
*state
= GetState(nodeBase
);
2180 SVal baseVal
= state
->getSVal(baseExpr
);
2181 SVal location
= state
->getLValue(Ex
->getDecl(), baseVal
);
2182 MakeNode(dstIvar
, Ex
, *I
, state
->BindExpr(Ex
, location
));
2185 // Perform the post-condition check of the ObjCIvarRefExpr and store
2186 // the created nodes in 'Dst'.
2187 CheckerVisit(Ex
, Dst
, dstIvar
, PostVisitStmtCallback
);
2190 //===----------------------------------------------------------------------===//
2191 // Transfer function: Objective-C fast enumeration 'for' statements.
2192 //===----------------------------------------------------------------------===//
2194 void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt
* S
,
2195 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
) {
2197 // ObjCForCollectionStmts are processed in two places. This method
2198 // handles the case where an ObjCForCollectionStmt* occurs as one of the
2199 // statements within a basic block. This transfer function does two things:
2201 // (1) binds the next container value to 'element'. This creates a new
2202 // node in the ExplodedGraph.
2204 // (2) binds the value 0/1 to the ObjCForCollectionStmt* itself, indicating
2205 // whether or not the container has any more elements. This value
2206 // will be tested in ProcessBranch. We need to explicitly bind
2207 // this value because a container can contain nil elements.
2209 // FIXME: Eventually this logic should actually do dispatches to
2210 // 'countByEnumeratingWithState:objects:count:' (NSFastEnumeration).
2211 // This will require simulating a temporary NSFastEnumerationState, either
2212 // through an SVal or through the use of MemRegions. This value can
2213 // be affixed to the ObjCForCollectionStmt* instead of 0/1; when the loop
2214 // terminates we reclaim the temporary (it goes out of scope) and we
2215 // we can test if the SVal is 0 or if the MemRegion is null (depending
2216 // on what approach we take).
2218 // For now: simulate (1) by assigning either a symbol or nil if the
2219 // container is empty. Thus this transfer function will by default
2220 // result in state splitting.
2222 const Stmt
* elem
= S
->getElement();
2225 if (const DeclStmt
* DS
= dyn_cast
<DeclStmt
>(elem
)) {
2226 const VarDecl
* ElemD
= cast
<VarDecl
>(DS
->getSingleDecl());
2227 assert (ElemD
->getInit() == 0);
2228 ElementV
= GetState(Pred
)->getLValue(ElemD
, Pred
->getLocationContext());
2229 VisitObjCForCollectionStmtAux(S
, Pred
, Dst
, ElementV
);
2233 ExplodedNodeSet Tmp
;
2234 Visit(cast
<Expr
>(elem
), Pred
, Tmp
);
2235 for (ExplodedNodeSet::iterator I
= Tmp
.begin(), E
= Tmp
.end(); I
!=E
; ++I
) {
2236 const GRState
* state
= GetState(*I
);
2237 VisitObjCForCollectionStmtAux(S
, *I
, Dst
, state
->getSVal(elem
));
2241 void ExprEngine::VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt
* S
,
2242 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
,
2245 // Check if the location we are writing back to is a null pointer.
2246 const Stmt
* elem
= S
->getElement();
2247 ExplodedNodeSet Tmp
;
2248 evalLocation(Tmp
, elem
, Pred
, GetState(Pred
), ElementV
, NULL
, false);
2253 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(), NE
=Tmp
.end(); NI
!=NE
; ++NI
) {
2255 const GRState
*state
= GetState(Pred
);
2257 // Handle the case where the container still has elements.
2258 SVal TrueV
= svalBuilder
.makeTruthVal(1);
2259 const GRState
*hasElems
= state
->BindExpr(S
, TrueV
);
2261 // Handle the case where the container has no elements.
2262 SVal FalseV
= svalBuilder
.makeTruthVal(0);
2263 const GRState
*noElems
= state
->BindExpr(S
, FalseV
);
2265 if (loc::MemRegionVal
* MV
= dyn_cast
<loc::MemRegionVal
>(&ElementV
))
2266 if (const TypedRegion
* R
= dyn_cast
<TypedRegion
>(MV
->getRegion())) {
2267 // FIXME: The proper thing to do is to really iterate over the
2268 // container. We will do this with dispatch logic to the store.
2269 // For now, just 'conjure' up a symbolic value.
2270 QualType T
= R
->getValueType();
2271 assert(Loc::IsLocType(T
));
2272 unsigned Count
= Builder
->getCurrentBlockCount();
2273 SymbolRef Sym
= SymMgr
.getConjuredSymbol(elem
, T
, Count
);
2274 SVal V
= svalBuilder
.makeLoc(Sym
);
2275 hasElems
= hasElems
->bindLoc(ElementV
, V
);
2277 // Bind the location to 'nil' on the false branch.
2278 SVal nilV
= svalBuilder
.makeIntVal(0, T
);
2279 noElems
= noElems
->bindLoc(ElementV
, nilV
);
2282 // Create the new nodes.
2283 MakeNode(Dst
, S
, Pred
, hasElems
);
2284 MakeNode(Dst
, S
, Pred
, noElems
);
2288 //===----------------------------------------------------------------------===//
2289 // Transfer function: Objective-C message expressions.
2290 //===----------------------------------------------------------------------===//
2293 class ObjCMsgWLItem
{
2295 ObjCMessageExpr::const_arg_iterator I
;
2298 ObjCMsgWLItem(const ObjCMessageExpr::const_arg_iterator
&i
, ExplodedNode
*n
)
2301 } // end anonymous namespace
2303 void ExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr
* ME
,
2305 ExplodedNodeSet
& Dst
){
2307 // Create a worklist to process both the arguments.
2308 llvm::SmallVector
<ObjCMsgWLItem
, 20> WL
;
2310 // But first evaluate the receiver (if any).
2311 ObjCMessageExpr::const_arg_iterator AI
= ME
->arg_begin(), AE
= ME
->arg_end();
2312 if (const Expr
*Receiver
= ME
->getInstanceReceiver()) {
2313 ExplodedNodeSet Tmp
;
2314 Visit(Receiver
, Pred
, Tmp
);
2319 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
)
2320 WL
.push_back(ObjCMsgWLItem(AI
, *I
));
2323 WL
.push_back(ObjCMsgWLItem(AI
, Pred
));
2325 // Evaluate the arguments.
2326 ExplodedNodeSet ArgsEvaluated
;
2327 while (!WL
.empty()) {
2328 ObjCMsgWLItem Item
= WL
.back();
2332 ArgsEvaluated
.insert(Item
.N
);
2336 // Evaluate the subexpression.
2337 ExplodedNodeSet Tmp
;
2339 // FIXME: [Objective-C++] handle arguments that are references
2340 Visit(*Item
.I
, Item
.N
, Tmp
);
2342 // Enqueue evaluating the next argument on the worklist.
2344 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(), NE
=Tmp
.end(); NI
!=NE
; ++NI
)
2345 WL
.push_back(ObjCMsgWLItem(Item
.I
, *NI
));
2348 // Now that the arguments are processed, handle the ObjC message.
2349 VisitObjCMessage(ME
, ArgsEvaluated
, Dst
);
2352 void ExprEngine::VisitObjCMessage(const ObjCMessage
&msg
,
2353 ExplodedNodeSet
&Src
, ExplodedNodeSet
& Dst
) {
2355 // Handle the previsits checks.
2356 ExplodedNodeSet DstPrevisit
;
2357 CheckerVisitObjCMessage(msg
, DstPrevisit
, Src
, /*isPreVisit=*/true);
2359 // Proceed with evaluate the message expression.
2360 ExplodedNodeSet dstEval
;
2362 for (ExplodedNodeSet::iterator DI
= DstPrevisit
.begin(),
2363 DE
= DstPrevisit
.end(); DI
!= DE
; ++DI
) {
2365 ExplodedNode
*Pred
= *DI
;
2366 bool RaisesException
= false;
2367 unsigned oldSize
= dstEval
.size();
2368 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
2369 SaveOr
OldHasGen(Builder
->hasGeneratedNode
);
2371 if (const Expr
*Receiver
= msg
.getInstanceReceiver()) {
2372 const GRState
*state
= GetState(Pred
);
2374 // Bifurcate the state into nil and non-nil ones.
2375 DefinedOrUnknownSVal receiverVal
=
2376 cast
<DefinedOrUnknownSVal
>(state
->getSVal(Receiver
));
2378 const GRState
*notNilState
, *nilState
;
2379 llvm::tie(notNilState
, nilState
) = state
->assume(receiverVal
);
2381 // There are three cases: can be nil or non-nil, must be nil, must be
2382 // non-nil. We handle must be nil, and merge the rest two into non-nil.
2383 if (nilState
&& !notNilState
) {
2384 CheckerEvalNilReceiver(msg
, dstEval
, nilState
, Pred
);
2388 // Check if the "raise" message was sent.
2389 assert(notNilState
);
2390 if (msg
.getSelector() == RaiseSel
)
2391 RaisesException
= true;
2393 // Check if we raise an exception. For now treat these as sinks.
2394 // Eventually we will want to handle exceptions properly.
2395 if (RaisesException
)
2396 Builder
->BuildSinks
= true;
2398 // Dispatch to plug-in transfer function.
2399 evalObjCMessage(dstEval
, msg
, Pred
, notNilState
);
2401 else if (const ObjCInterfaceDecl
*Iface
= msg
.getReceiverInterface()) {
2402 IdentifierInfo
* ClsName
= Iface
->getIdentifier();
2403 Selector S
= msg
.getSelector();
2405 // Check for special instance methods.
2406 if (!NSExceptionII
) {
2407 ASTContext
& Ctx
= getContext();
2408 NSExceptionII
= &Ctx
.Idents
.get("NSException");
2411 if (ClsName
== NSExceptionII
) {
2412 enum { NUM_RAISE_SELECTORS
= 2 };
2414 // Lazily create a cache of the selectors.
2415 if (!NSExceptionInstanceRaiseSelectors
) {
2416 ASTContext
& Ctx
= getContext();
2417 NSExceptionInstanceRaiseSelectors
=
2418 new Selector
[NUM_RAISE_SELECTORS
];
2419 llvm::SmallVector
<IdentifierInfo
*, NUM_RAISE_SELECTORS
> II
;
2423 II
.push_back(&Ctx
.Idents
.get("raise"));
2424 II
.push_back(&Ctx
.Idents
.get("format"));
2425 NSExceptionInstanceRaiseSelectors
[idx
++] =
2426 Ctx
.Selectors
.getSelector(II
.size(), &II
[0]);
2428 // raise:format::arguments:
2429 II
.push_back(&Ctx
.Idents
.get("arguments"));
2430 NSExceptionInstanceRaiseSelectors
[idx
++] =
2431 Ctx
.Selectors
.getSelector(II
.size(), &II
[0]);
2434 for (unsigned i
= 0; i
< NUM_RAISE_SELECTORS
; ++i
)
2435 if (S
== NSExceptionInstanceRaiseSelectors
[i
]) {
2436 RaisesException
= true;
2441 // Check if we raise an exception. For now treat these as sinks.
2442 // Eventually we will want to handle exceptions properly.
2443 if (RaisesException
)
2444 Builder
->BuildSinks
= true;
2446 // Dispatch to plug-in transfer function.
2447 evalObjCMessage(dstEval
, msg
, Pred
, Builder
->GetState(Pred
));
2450 // Handle the case where no nodes where generated. Auto-generate that
2451 // contains the updated state if we aren't generating sinks.
2452 if (!Builder
->BuildSinks
&& dstEval
.size() == oldSize
&&
2453 !Builder
->hasGeneratedNode
)
2454 MakeNode(dstEval
, msg
.getOriginExpr(), Pred
, GetState(Pred
));
2457 // Finally, perform the post-condition check of the ObjCMessageExpr and store
2458 // the created nodes in 'Dst'.
2459 CheckerVisitObjCMessage(msg
, Dst
, dstEval
, /*isPreVisit=*/false);
2462 //===----------------------------------------------------------------------===//
2463 // Transfer functions: Miscellaneous statements.
2464 //===----------------------------------------------------------------------===//
2466 void ExprEngine::VisitCast(const CastExpr
*CastE
, const Expr
*Ex
,
2467 ExplodedNode
*Pred
, ExplodedNodeSet
&Dst
) {
2470 Visit(Ex
, Pred
, S1
);
2472 CheckerVisit(CastE
, S2
, S1
, PreVisitStmtCallback
);
2474 if (CastE
->getCastKind() == CK_LValueToRValue
||
2475 CastE
->getCastKind() == CK_GetObjCProperty
) {
2476 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!=E
; ++I
) {
2477 ExplodedNode
*subExprNode
= *I
;
2478 const GRState
*state
= GetState(subExprNode
);
2479 evalLoad(Dst
, CastE
, subExprNode
, state
, state
->getSVal(Ex
));
2485 QualType T
= CastE
->getType();
2486 QualType ExTy
= Ex
->getType();
2488 if (const ExplicitCastExpr
*ExCast
=dyn_cast_or_null
<ExplicitCastExpr
>(CastE
))
2489 T
= ExCast
->getTypeAsWritten();
2492 // If we are evaluating the cast in an lvalue context, we implicitly want
2493 // the cast to evaluate to a location.
2495 ASTContext
&Ctx
= getContext();
2496 T
= Ctx
.getPointerType(Ctx
.getCanonicalType(T
));
2497 ExTy
= Ctx
.getPointerType(Ctx
.getCanonicalType(ExTy
));
2501 switch (CastE
->getCastKind()) {
2503 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!= E
; ++I
)
2507 case CK_LValueToRValue
:
2509 case CK_FunctionToPointerDecay
:
2510 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!= E
; ++I
) {
2511 // Copy the SVal of Ex to CastE.
2512 ExplodedNode
*N
= *I
;
2513 const GRState
*state
= GetState(N
);
2514 SVal V
= state
->getSVal(Ex
);
2515 state
= state
->BindExpr(CastE
, V
);
2516 MakeNode(Dst
, CastE
, N
, state
);
2520 case CK_GetObjCProperty
:
2522 case CK_ArrayToPointerDecay
:
2524 case CK_LValueBitCast
:
2525 case CK_IntegralCast
:
2526 case CK_NullToPointer
:
2527 case CK_IntegralToPointer
:
2528 case CK_PointerToIntegral
:
2529 case CK_PointerToBoolean
:
2530 case CK_IntegralToBoolean
:
2531 case CK_IntegralToFloating
:
2532 case CK_FloatingToIntegral
:
2533 case CK_FloatingToBoolean
:
2534 case CK_FloatingCast
:
2535 case CK_FloatingRealToComplex
:
2536 case CK_FloatingComplexToReal
:
2537 case CK_FloatingComplexToBoolean
:
2538 case CK_FloatingComplexCast
:
2539 case CK_FloatingComplexToIntegralComplex
:
2540 case CK_IntegralRealToComplex
:
2541 case CK_IntegralComplexToReal
:
2542 case CK_IntegralComplexToBoolean
:
2543 case CK_IntegralComplexCast
:
2544 case CK_IntegralComplexToFloatingComplex
:
2545 case CK_AnyPointerToObjCPointerCast
:
2546 case CK_AnyPointerToBlockPointerCast
:
2548 case CK_ObjCObjectLValueCast
: {
2549 // Delegate to SValBuilder to process.
2550 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!= E
; ++I
) {
2551 ExplodedNode
* N
= *I
;
2552 const GRState
* state
= GetState(N
);
2553 SVal V
= state
->getSVal(Ex
);
2554 V
= svalBuilder
.evalCast(V
, T
, ExTy
);
2555 state
= state
->BindExpr(CastE
, V
);
2556 MakeNode(Dst
, CastE
, N
, state
);
2561 case CK_DerivedToBase
:
2562 case CK_UncheckedDerivedToBase
:
2563 // For DerivedToBase cast, delegate to the store manager.
2564 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!= E
; ++I
) {
2565 ExplodedNode
*node
= *I
;
2566 const GRState
*state
= GetState(node
);
2567 SVal val
= state
->getSVal(Ex
);
2568 val
= getStoreManager().evalDerivedToBase(val
, T
);
2569 state
= state
->BindExpr(CastE
, val
);
2570 MakeNode(Dst
, CastE
, node
, state
);
2574 // Various C++ casts that are not handled yet.
2577 case CK_BaseToDerived
:
2578 case CK_NullToMemberPointer
:
2579 case CK_BaseToDerivedMemberPointer
:
2580 case CK_DerivedToBaseMemberPointer
:
2581 case CK_UserDefinedConversion
:
2582 case CK_ConstructorConversion
:
2583 case CK_VectorSplat
:
2584 case CK_MemberPointerToBoolean
: {
2585 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
2586 Builder
->BuildSinks
= true;
2587 MakeNode(Dst
, CastE
, Pred
, GetState(Pred
));
2593 void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr
* CL
,
2595 ExplodedNodeSet
& Dst
) {
2596 const InitListExpr
* ILE
2597 = cast
<InitListExpr
>(CL
->getInitializer()->IgnoreParens());
2598 ExplodedNodeSet Tmp
;
2599 Visit(ILE
, Pred
, Tmp
);
2601 for (ExplodedNodeSet::iterator I
= Tmp
.begin(), EI
= Tmp
.end(); I
!=EI
; ++I
) {
2602 const GRState
* state
= GetState(*I
);
2603 SVal ILV
= state
->getSVal(ILE
);
2604 const LocationContext
*LC
= (*I
)->getLocationContext();
2605 state
= state
->bindCompoundLiteral(CL
, LC
, ILV
);
2607 if (CL
->isLValue()) {
2608 MakeNode(Dst
, CL
, *I
, state
->BindExpr(CL
, state
->getLValue(CL
, LC
)));
2611 MakeNode(Dst
, CL
, *I
, state
->BindExpr(CL
, ILV
));
2615 void ExprEngine::VisitDeclStmt(const DeclStmt
*DS
, ExplodedNode
*Pred
,
2616 ExplodedNodeSet
& Dst
) {
2618 // The CFG has one DeclStmt per Decl.
2619 const Decl
* D
= *DS
->decl_begin();
2621 if (!D
|| !isa
<VarDecl
>(D
))
2624 const VarDecl
* VD
= dyn_cast
<VarDecl
>(D
);
2625 const Expr
* InitEx
= VD
->getInit();
2627 // FIXME: static variables may have an initializer, but the second
2628 // time a function is called those values may not be current.
2629 ExplodedNodeSet Tmp
;
2632 if (VD
->getType()->isReferenceType() && !InitEx
->isLValue()) {
2633 // If the initializer is C++ record type, it should already has a
2635 if (!InitEx
->getType()->isRecordType())
2636 CreateCXXTemporaryObject(InitEx
, Pred
, Tmp
);
2640 Visit(InitEx
, Pred
, Tmp
);
2644 ExplodedNodeSet Tmp2
;
2645 CheckerVisit(DS
, Tmp2
, Tmp
, PreVisitStmtCallback
);
2647 for (ExplodedNodeSet::iterator I
=Tmp2
.begin(), E
=Tmp2
.end(); I
!=E
; ++I
) {
2648 ExplodedNode
*N
= *I
;
2649 const GRState
*state
= GetState(N
);
2651 // Decls without InitExpr are not initialized explicitly.
2652 const LocationContext
*LC
= N
->getLocationContext();
2655 SVal InitVal
= state
->getSVal(InitEx
);
2657 // We bound the temp obj region to the CXXConstructExpr. Now recover
2658 // the lazy compound value when the variable is not a reference.
2659 if (AMgr
.getLangOptions().CPlusPlus
&& VD
->getType()->isRecordType() &&
2660 !VD
->getType()->isReferenceType() && isa
<loc::MemRegionVal
>(InitVal
)){
2661 InitVal
= state
->getSVal(cast
<loc::MemRegionVal
>(InitVal
).getRegion());
2662 assert(isa
<nonloc::LazyCompoundVal
>(InitVal
));
2665 // Recover some path-sensitivity if a scalar value evaluated to
2667 if ((InitVal
.isUnknown() ||
2668 !getConstraintManager().canReasonAbout(InitVal
)) &&
2669 !VD
->getType()->isReferenceType()) {
2670 InitVal
= svalBuilder
.getConjuredSymbolVal(NULL
, InitEx
,
2671 Builder
->getCurrentBlockCount());
2674 evalBind(Dst
, DS
, *I
, state
,
2675 loc::MemRegionVal(state
->getRegion(VD
, LC
)), InitVal
, true);
2678 state
= state
->bindDeclWithNoInit(state
->getRegion(VD
, LC
));
2679 MakeNode(Dst
, DS
, *I
, state
);
2684 void ExprEngine::VisitCondInit(const VarDecl
*VD
, const Stmt
*S
,
2685 ExplodedNode
*Pred
, ExplodedNodeSet
& Dst
) {
2687 const Expr
* InitEx
= VD
->getInit();
2688 ExplodedNodeSet Tmp
;
2689 Visit(InitEx
, Pred
, Tmp
);
2691 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2692 ExplodedNode
*N
= *I
;
2693 const GRState
*state
= GetState(N
);
2695 const LocationContext
*LC
= N
->getLocationContext();
2696 SVal InitVal
= state
->getSVal(InitEx
);
2698 // Recover some path-sensitivity if a scalar value evaluated to
2700 if (InitVal
.isUnknown() ||
2701 !getConstraintManager().canReasonAbout(InitVal
)) {
2702 InitVal
= svalBuilder
.getConjuredSymbolVal(NULL
, InitEx
,
2703 Builder
->getCurrentBlockCount());
2706 evalBind(Dst
, S
, N
, state
,
2707 loc::MemRegionVal(state
->getRegion(VD
, LC
)), InitVal
, true);
2712 // This class is used by VisitInitListExpr as an item in a worklist
2713 // for processing the values contained in an InitListExpr.
2714 class InitListWLItem
{
2716 llvm::ImmutableList
<SVal
> Vals
;
2718 InitListExpr::const_reverse_iterator Itr
;
2720 InitListWLItem(ExplodedNode
* n
, llvm::ImmutableList
<SVal
> vals
,
2721 InitListExpr::const_reverse_iterator itr
)
2722 : Vals(vals
), N(n
), Itr(itr
) {}
2727 void ExprEngine::VisitInitListExpr(const InitListExpr
* E
, ExplodedNode
* Pred
,
2728 ExplodedNodeSet
& Dst
) {
2730 const GRState
* state
= GetState(Pred
);
2731 QualType T
= getContext().getCanonicalType(E
->getType());
2732 unsigned NumInitElements
= E
->getNumInits();
2734 if (T
->isArrayType() || T
->isRecordType() || T
->isVectorType()) {
2735 llvm::ImmutableList
<SVal
> StartVals
= getBasicVals().getEmptySValList();
2737 // Handle base case where the initializer has no elements.
2738 // e.g: static int* myArray[] = {};
2739 if (NumInitElements
== 0) {
2740 SVal V
= svalBuilder
.makeCompoundVal(T
, StartVals
);
2741 MakeNode(Dst
, E
, Pred
, state
->BindExpr(E
, V
));
2745 // Create a worklist to process the initializers.
2746 llvm::SmallVector
<InitListWLItem
, 10> WorkList
;
2747 WorkList
.reserve(NumInitElements
);
2748 WorkList
.push_back(InitListWLItem(Pred
, StartVals
, E
->rbegin()));
2749 InitListExpr::const_reverse_iterator ItrEnd
= E
->rend();
2750 assert(!(E
->rbegin() == E
->rend()));
2752 // Process the worklist until it is empty.
2753 while (!WorkList
.empty()) {
2754 InitListWLItem X
= WorkList
.back();
2755 WorkList
.pop_back();
2757 ExplodedNodeSet Tmp
;
2758 Visit(*X
.Itr
, X
.N
, Tmp
);
2760 InitListExpr::const_reverse_iterator NewItr
= X
.Itr
+ 1;
2762 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(),NE
=Tmp
.end();NI
!=NE
;++NI
) {
2763 // Get the last initializer value.
2764 state
= GetState(*NI
);
2765 SVal InitV
= state
->getSVal(cast
<Expr
>(*X
.Itr
));
2767 // Construct the new list of values by prepending the new value to
2768 // the already constructed list.
2769 llvm::ImmutableList
<SVal
> NewVals
=
2770 getBasicVals().consVals(InitV
, X
.Vals
);
2772 if (NewItr
== ItrEnd
) {
2773 // Now we have a list holding all init values. Make CompoundValData.
2774 SVal V
= svalBuilder
.makeCompoundVal(T
, NewVals
);
2776 // Make final state and node.
2777 MakeNode(Dst
, E
, *NI
, state
->BindExpr(E
, V
));
2780 // Still some initializer values to go. Push them onto the worklist.
2781 WorkList
.push_back(InitListWLItem(*NI
, NewVals
, NewItr
));
2789 if (Loc::IsLocType(T
) || T
->isIntegerType()) {
2790 assert (E
->getNumInits() == 1);
2791 ExplodedNodeSet Tmp
;
2792 const Expr
* Init
= E
->getInit(0);
2793 Visit(Init
, Pred
, Tmp
);
2794 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), EI
=Tmp
.end(); I
!= EI
; ++I
) {
2795 state
= GetState(*I
);
2796 MakeNode(Dst
, E
, *I
, state
->BindExpr(E
, state
->getSVal(Init
)));
2801 assert(0 && "unprocessed InitListExpr type");
2804 /// VisitSizeOfAlignOfExpr - Transfer function for sizeof(type).
2805 void ExprEngine::VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr
* Ex
,
2807 ExplodedNodeSet
& Dst
) {
2808 QualType T
= Ex
->getTypeOfArgument();
2811 if (Ex
->isSizeOf()) {
2812 if (T
== getContext().VoidTy
) {
2813 // sizeof(void) == 1 byte.
2814 amt
= CharUnits::One();
2816 else if (!T
->isConstantSizeType()) {
2817 assert(T
->isVariableArrayType() && "Unknown non-constant-sized type.");
2819 // FIXME: Add support for VLA type arguments, not just VLA expressions.
2820 // When that happens, we should probably refactor VLASizeChecker's code.
2821 if (Ex
->isArgumentType()) {
2826 // Get the size by getting the extent of the sub-expression.
2827 // First, visit the sub-expression to find its region.
2828 const Expr
*Arg
= Ex
->getArgumentExpr();
2829 ExplodedNodeSet Tmp
;
2830 Visit(Arg
, Pred
, Tmp
);
2832 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2833 const GRState
* state
= GetState(*I
);
2834 const MemRegion
*MR
= state
->getSVal(Arg
).getAsRegion();
2836 // If the subexpression can't be resolved to a region, we don't know
2837 // anything about its size. Just leave the state as is and continue.
2843 // The result is the extent of the VLA.
2844 SVal Extent
= cast
<SubRegion
>(MR
)->getExtent(svalBuilder
);
2845 MakeNode(Dst
, Ex
, *I
, state
->BindExpr(Ex
, Extent
));
2850 else if (T
->getAs
<ObjCObjectType
>()) {
2851 // Some code tries to take the sizeof an ObjCObjectType, relying that
2852 // the compiler has laid out its representation. Just report Unknown
2859 amt
= getContext().getTypeSizeInChars(T
);
2862 else // Get alignment of the type.
2863 amt
= getContext().getTypeAlignInChars(T
);
2865 MakeNode(Dst
, Ex
, Pred
,
2866 GetState(Pred
)->BindExpr(Ex
,
2867 svalBuilder
.makeIntVal(amt
.getQuantity(), Ex
->getType())));
2870 void ExprEngine::VisitOffsetOfExpr(const OffsetOfExpr
* OOE
,
2871 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
) {
2872 Expr::EvalResult Res
;
2873 if (OOE
->Evaluate(Res
, getContext()) && Res
.Val
.isInt()) {
2874 const APSInt
&IV
= Res
.Val
.getInt();
2875 assert(IV
.getBitWidth() == getContext().getTypeSize(OOE
->getType()));
2876 assert(OOE
->getType()->isIntegerType());
2877 assert(IV
.isSigned() == OOE
->getType()->isSignedIntegerType());
2878 SVal X
= svalBuilder
.makeIntVal(IV
);
2879 MakeNode(Dst
, OOE
, Pred
, GetState(Pred
)->BindExpr(OOE
, X
));
2882 // FIXME: Handle the case where __builtin_offsetof is not a constant.
2886 void ExprEngine::VisitUnaryOperator(const UnaryOperator
* U
,
2888 ExplodedNodeSet
& Dst
) {
2890 switch (U
->getOpcode()) {
2896 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
2897 ExplodedNodeSet Tmp
;
2898 Visit(Ex
, Pred
, Tmp
);
2900 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2902 // FIXME: We don't have complex SValues yet.
2903 if (Ex
->getType()->isAnyComplexType()) {
2904 // Just report "Unknown."
2909 // For all other types, UO_Real is an identity operation.
2910 assert (U
->getType() == Ex
->getType());
2911 const GRState
* state
= GetState(*I
);
2912 MakeNode(Dst
, U
, *I
, state
->BindExpr(U
, state
->getSVal(Ex
)));
2920 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
2921 ExplodedNodeSet Tmp
;
2922 Visit(Ex
, Pred
, Tmp
);
2924 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2925 // FIXME: We don't have complex SValues yet.
2926 if (Ex
->getType()->isAnyComplexType()) {
2927 // Just report "Unknown."
2932 // For all other types, UO_Imag returns 0.
2933 const GRState
* state
= GetState(*I
);
2934 SVal X
= svalBuilder
.makeZeroVal(Ex
->getType());
2935 MakeNode(Dst
, U
, *I
, state
->BindExpr(U
, X
));
2942 assert(!U
->isLValue());
2946 case UO_Extension
: {
2948 // Unary "+" is a no-op, similar to a parentheses. We still have places
2949 // where it may be a block-level expression, so we need to
2950 // generate an extra node that just propagates the value of the
2953 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
2954 ExplodedNodeSet Tmp
;
2955 Visit(Ex
, Pred
, Tmp
);
2957 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2958 const GRState
* state
= GetState(*I
);
2959 MakeNode(Dst
, U
, *I
, state
->BindExpr(U
, state
->getSVal(Ex
)));
2968 assert (!U
->isLValue());
2969 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
2970 ExplodedNodeSet Tmp
;
2971 Visit(Ex
, Pred
, Tmp
);
2973 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2974 const GRState
* state
= GetState(*I
);
2976 // Get the value of the subexpression.
2977 SVal V
= state
->getSVal(Ex
);
2979 if (V
.isUnknownOrUndef()) {
2980 MakeNode(Dst
, U
, *I
, state
->BindExpr(U
, V
));
2984 // QualType DstT = getContext().getCanonicalType(U->getType());
2985 // QualType SrcT = getContext().getCanonicalType(Ex->getType());
2987 // if (DstT != SrcT) // Perform promotions.
2988 // V = evalCast(V, DstT);
2990 // if (V.isUnknownOrUndef()) {
2991 // MakeNode(Dst, U, *I, BindExpr(St, U, V));
2995 switch (U
->getOpcode()) {
2997 assert(false && "Invalid Opcode.");
3001 // FIXME: Do we need to handle promotions?
3002 state
= state
->BindExpr(U
, evalComplement(cast
<NonLoc
>(V
)));
3006 // FIXME: Do we need to handle promotions?
3007 state
= state
->BindExpr(U
, evalMinus(cast
<NonLoc
>(V
)));
3012 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
3014 // Note: technically we do "E == 0", but this is the same in the
3015 // transfer functions as "0 == E".
3019 Loc X
= svalBuilder
.makeNull();
3020 Result
= evalBinOp(state
, BO_EQ
, cast
<Loc
>(V
), X
,
3024 nonloc::ConcreteInt
X(getBasicVals().getValue(0, Ex
->getType()));
3025 Result
= evalBinOp(state
, BO_EQ
, cast
<NonLoc
>(V
), X
,
3029 state
= state
->BindExpr(U
, Result
);
3034 MakeNode(Dst
, U
, *I
, state
);
3041 // Handle ++ and -- (both pre- and post-increment).
3042 assert (U
->isIncrementDecrementOp());
3043 ExplodedNodeSet Tmp
;
3044 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
3045 Visit(Ex
, Pred
, Tmp
);
3047 for (ExplodedNodeSet::iterator I
= Tmp
.begin(), E
= Tmp
.end(); I
!=E
; ++I
) {
3049 const GRState
* state
= GetState(*I
);
3050 SVal loc
= state
->getSVal(Ex
);
3053 ExplodedNodeSet Tmp2
;
3054 evalLoad(Tmp2
, Ex
, *I
, state
, loc
);
3056 for (ExplodedNodeSet::iterator I2
=Tmp2
.begin(), E2
=Tmp2
.end();I2
!=E2
;++I2
) {
3058 state
= GetState(*I2
);
3059 SVal V2_untested
= state
->getSVal(Ex
);
3061 // Propagate unknown and undefined values.
3062 if (V2_untested
.isUnknownOrUndef()) {
3063 MakeNode(Dst
, U
, *I2
, state
->BindExpr(U
, V2_untested
));
3066 DefinedSVal V2
= cast
<DefinedSVal
>(V2_untested
);
3068 // Handle all other values.
3069 BinaryOperator::Opcode Op
= U
->isIncrementOp() ? BO_Add
3072 // If the UnaryOperator has non-location type, use its type to create the
3073 // constant value. If the UnaryOperator has location type, create the
3074 // constant with int type and pointer width.
3077 if (U
->getType()->isAnyPointerType())
3078 RHS
= svalBuilder
.makeArrayIndex(1);
3080 RHS
= svalBuilder
.makeIntVal(1, U
->getType());
3082 SVal Result
= evalBinOp(state
, Op
, V2
, RHS
, U
->getType());
3084 // Conjure a new symbol if necessary to recover precision.
3085 if (Result
.isUnknown() || !getConstraintManager().canReasonAbout(Result
)){
3086 DefinedOrUnknownSVal SymVal
=
3087 svalBuilder
.getConjuredSymbolVal(NULL
, Ex
,
3088 Builder
->getCurrentBlockCount());
3091 // If the value is a location, ++/-- should always preserve
3092 // non-nullness. Check if the original value was non-null, and if so
3093 // propagate that constraint.
3094 if (Loc::IsLocType(U
->getType())) {
3095 DefinedOrUnknownSVal Constraint
=
3096 svalBuilder
.evalEQ(state
, V2
,svalBuilder
.makeZeroVal(U
->getType()));
3098 if (!state
->assume(Constraint
, true)) {
3099 // It isn't feasible for the original value to be null.
3100 // Propagate this constraint.
3101 Constraint
= svalBuilder
.evalEQ(state
, SymVal
,
3102 svalBuilder
.makeZeroVal(U
->getType()));
3105 state
= state
->assume(Constraint
, false);
3111 // Since the lvalue-to-rvalue conversion is explicit in the AST,
3112 // we bind an l-value if the operator is prefix and an lvalue (in C++).
3114 state
= state
->BindExpr(U
, loc
);
3116 state
= state
->BindExpr(U
, V2
);
3118 // Perform the store.
3119 evalStore(Dst
, NULL
, U
, *I2
, state
, loc
, Result
);
3124 void ExprEngine::VisitAsmStmt(const AsmStmt
* A
, ExplodedNode
* Pred
,
3125 ExplodedNodeSet
& Dst
) {
3126 VisitAsmStmtHelperOutputs(A
, A
->begin_outputs(), A
->end_outputs(), Pred
, Dst
);
3129 void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt
* A
,
3130 AsmStmt::const_outputs_iterator I
,
3131 AsmStmt::const_outputs_iterator E
,
3132 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
) {
3134 VisitAsmStmtHelperInputs(A
, A
->begin_inputs(), A
->end_inputs(), Pred
, Dst
);
3138 ExplodedNodeSet Tmp
;
3139 Visit(*I
, Pred
, Tmp
);
3142 for (ExplodedNodeSet::iterator NI
= Tmp
.begin(), NE
= Tmp
.end();NI
!= NE
;++NI
)
3143 VisitAsmStmtHelperOutputs(A
, I
, E
, *NI
, Dst
);
3146 void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt
* A
,
3147 AsmStmt::const_inputs_iterator I
,
3148 AsmStmt::const_inputs_iterator E
,
3150 ExplodedNodeSet
& Dst
) {
3153 // We have processed both the inputs and the outputs. All of the outputs
3154 // should evaluate to Locs. Nuke all of their values.
3156 // FIXME: Some day in the future it would be nice to allow a "plug-in"
3157 // which interprets the inline asm and stores proper results in the
3160 const GRState
* state
= GetState(Pred
);
3162 for (AsmStmt::const_outputs_iterator OI
= A
->begin_outputs(),
3163 OE
= A
->end_outputs(); OI
!= OE
; ++OI
) {
3165 SVal X
= state
->getSVal(*OI
);
3166 assert (!isa
<NonLoc
>(X
)); // Should be an Lval, or unknown, undef.
3169 state
= state
->bindLoc(cast
<Loc
>(X
), UnknownVal());
3172 MakeNode(Dst
, A
, Pred
, state
);
3176 ExplodedNodeSet Tmp
;
3177 Visit(*I
, Pred
, Tmp
);
3181 for (ExplodedNodeSet::iterator NI
= Tmp
.begin(), NE
= Tmp
.end(); NI
!=NE
; ++NI
)
3182 VisitAsmStmtHelperInputs(A
, I
, E
, *NI
, Dst
);
3185 void ExprEngine::VisitReturnStmt(const ReturnStmt
*RS
, ExplodedNode
*Pred
,
3186 ExplodedNodeSet
&Dst
) {
3187 ExplodedNodeSet Src
;
3188 if (const Expr
*RetE
= RS
->getRetValue()) {
3189 // Record the returned expression in the state. It will be used in
3190 // processCallExit to bind the return value to the call expr.
3193 const GRState
*state
= GetState(Pred
);
3194 state
= state
->set
<ReturnExpr
>(RetE
);
3195 Pred
= Builder
->generateNode(RetE
, state
, Pred
, &tag
);
3197 // We may get a NULL Pred because we generated a cached node.
3199 Visit(RetE
, Pred
, Src
);
3205 ExplodedNodeSet CheckedSet
;
3206 CheckerVisit(RS
, CheckedSet
, Src
, PreVisitStmtCallback
);
3208 for (ExplodedNodeSet::iterator I
= CheckedSet
.begin(), E
= CheckedSet
.end();
3211 assert(Builder
&& "StmtNodeBuilder must be defined.");
3214 unsigned size
= Dst
.size();
3216 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
3217 SaveOr
OldHasGen(Builder
->hasGeneratedNode
);
3219 getTF().evalReturn(Dst
, *this, *Builder
, RS
, Pred
);
3221 // Handle the case where no nodes where generated.
3222 if (!Builder
->BuildSinks
&& Dst
.size() == size
&&
3223 !Builder
->hasGeneratedNode
)
3224 MakeNode(Dst
, RS
, Pred
, GetState(Pred
));
3228 //===----------------------------------------------------------------------===//
3229 // Transfer functions: Binary operators.
3230 //===----------------------------------------------------------------------===//
3232 void ExprEngine::VisitBinaryOperator(const BinaryOperator
* B
,
3234 ExplodedNodeSet
& Dst
) {
3235 ExplodedNodeSet Tmp1
;
3236 Expr
* LHS
= B
->getLHS()->IgnoreParens();
3237 Expr
* RHS
= B
->getRHS()->IgnoreParens();
3239 Visit(LHS
, Pred
, Tmp1
);
3240 ExplodedNodeSet Tmp3
;
3242 for (ExplodedNodeSet::iterator I1
=Tmp1
.begin(), E1
=Tmp1
.end(); I1
!=E1
; ++I1
) {
3243 SVal LeftV
= GetState(*I1
)->getSVal(LHS
);
3244 ExplodedNodeSet Tmp2
;
3245 Visit(RHS
, *I1
, Tmp2
);
3247 ExplodedNodeSet CheckedSet
;
3248 CheckerVisit(B
, CheckedSet
, Tmp2
, PreVisitStmtCallback
);
3250 // With both the LHS and RHS evaluated, process the operation itself.
3252 for (ExplodedNodeSet::iterator I2
=CheckedSet
.begin(), E2
=CheckedSet
.end();
3255 const GRState
*state
= GetState(*I2
);
3256 SVal RightV
= state
->getSVal(RHS
);
3258 BinaryOperator::Opcode Op
= B
->getOpcode();
3260 if (Op
== BO_Assign
) {
3261 // EXPERIMENTAL: "Conjured" symbols.
3262 // FIXME: Handle structs.
3263 if (RightV
.isUnknown() ||!getConstraintManager().canReasonAbout(RightV
))
3265 unsigned Count
= Builder
->getCurrentBlockCount();
3266 RightV
= svalBuilder
.getConjuredSymbolVal(NULL
, B
->getRHS(), Count
);
3269 SVal ExprVal
= B
->isLValue() ? LeftV
: RightV
;
3271 // Simulate the effects of a "store": bind the value of the RHS
3272 // to the L-Value represented by the LHS.
3273 evalStore(Tmp3
, B
, LHS
, *I2
, state
->BindExpr(B
, ExprVal
), LeftV
,RightV
);
3277 if (!B
->isAssignmentOp()) {
3278 // Process non-assignments except commas or short-circuited
3279 // logical expressions (LAnd and LOr).
3280 SVal Result
= evalBinOp(state
, Op
, LeftV
, RightV
, B
->getType());
3282 if (Result
.isUnknown()) {
3283 MakeNode(Tmp3
, B
, *I2
, state
);
3287 state
= state
->BindExpr(B
, Result
);
3289 MakeNode(Tmp3
, B
, *I2
, state
);
3293 assert (B
->isCompoundAssignmentOp());
3297 assert(0 && "Invalid opcode for compound assignment.");
3298 case BO_MulAssign
: Op
= BO_Mul
; break;
3299 case BO_DivAssign
: Op
= BO_Div
; break;
3300 case BO_RemAssign
: Op
= BO_Rem
; break;
3301 case BO_AddAssign
: Op
= BO_Add
; break;
3302 case BO_SubAssign
: Op
= BO_Sub
; break;
3303 case BO_ShlAssign
: Op
= BO_Shl
; break;
3304 case BO_ShrAssign
: Op
= BO_Shr
; break;
3305 case BO_AndAssign
: Op
= BO_And
; break;
3306 case BO_XorAssign
: Op
= BO_Xor
; break;
3307 case BO_OrAssign
: Op
= BO_Or
; break;
3310 // Perform a load (the LHS). This performs the checks for
3311 // null dereferences, and so on.
3312 ExplodedNodeSet Tmp4
;
3313 SVal location
= state
->getSVal(LHS
);
3314 evalLoad(Tmp4
, LHS
, *I2
, state
, location
);
3316 for (ExplodedNodeSet::iterator I4
=Tmp4
.begin(), E4
=Tmp4
.end(); I4
!=E4
;
3318 state
= GetState(*I4
);
3319 SVal V
= state
->getSVal(LHS
);
3321 // Get the computation type.
3323 cast
<CompoundAssignOperator
>(B
)->getComputationResultType();
3324 CTy
= getContext().getCanonicalType(CTy
);
3327 cast
<CompoundAssignOperator
>(B
)->getComputationLHSType();
3328 CLHSTy
= getContext().getCanonicalType(CLHSTy
);
3330 QualType LTy
= getContext().getCanonicalType(LHS
->getType());
3333 V
= svalBuilder
.evalCast(V
, CLHSTy
, LTy
);
3335 // Compute the result of the operation.
3336 SVal Result
= svalBuilder
.evalCast(evalBinOp(state
, Op
, V
, RightV
, CTy
),
3339 // EXPERIMENTAL: "Conjured" symbols.
3340 // FIXME: Handle structs.
3344 if (Result
.isUnknown() ||
3345 !getConstraintManager().canReasonAbout(Result
)) {
3347 unsigned Count
= Builder
->getCurrentBlockCount();
3349 // The symbolic value is actually for the type of the left-hand side
3350 // expression, not the computation type, as this is the value the
3351 // LValue on the LHS will bind to.
3352 LHSVal
= svalBuilder
.getConjuredSymbolVal(NULL
, B
->getRHS(), LTy
, Count
);
3354 // However, we need to convert the symbol to the computation type.
3355 Result
= svalBuilder
.evalCast(LHSVal
, CTy
, LTy
);
3358 // The left-hand side may bind to a different value then the
3359 // computation type.
3360 LHSVal
= svalBuilder
.evalCast(Result
, LTy
, CTy
);
3363 // In C++, assignment and compound assignment operators return an
3366 state
= state
->BindExpr(B
, location
);
3368 state
= state
->BindExpr(B
, Result
);
3370 evalStore(Tmp3
, B
, LHS
, *I4
, state
, location
, LHSVal
);
3375 CheckerVisit(B
, Dst
, Tmp3
, PostVisitStmtCallback
);
3378 //===----------------------------------------------------------------------===//
3379 // Checker registration/lookup.
3380 //===----------------------------------------------------------------------===//
3382 Checker
*ExprEngine::lookupChecker(void *tag
) const {
3383 CheckerMap::const_iterator I
= CheckerM
.find(tag
);
3384 return (I
== CheckerM
.end()) ? NULL
: Checkers
[I
->second
].second
;
3387 //===----------------------------------------------------------------------===//
3389 //===----------------------------------------------------------------------===//
3392 static ExprEngine
* GraphPrintCheckerState
;
3393 static SourceManager
* GraphPrintSourceManager
;
3397 struct DOTGraphTraits
<ExplodedNode
*> :
3398 public DefaultDOTGraphTraits
{
3400 DOTGraphTraits (bool isSimple
=false) : DefaultDOTGraphTraits(isSimple
) {}
3402 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
3404 static std::string
getNodeAttributes(const ExplodedNode
* N
, void*) {
3407 // FIXME: Replace with a general scheme to tell if the node is
3409 if (GraphPrintCheckerState
->isImplicitNullDeref(N
) ||
3410 GraphPrintCheckerState
->isExplicitNullDeref(N
) ||
3411 GraphPrintCheckerState
->isUndefDeref(N
) ||
3412 GraphPrintCheckerState
->isUndefStore(N
) ||
3413 GraphPrintCheckerState
->isUndefControlFlow(N
) ||
3414 GraphPrintCheckerState
->isUndefResult(N
) ||
3415 GraphPrintCheckerState
->isBadCall(N
) ||
3416 GraphPrintCheckerState
->isUndefArg(N
))
3417 return "color=\"red\",style=\"filled\"";
3419 if (GraphPrintCheckerState
->isNoReturnCall(N
))
3420 return "color=\"blue\",style=\"filled\"";
3425 static std::string
getNodeLabel(const ExplodedNode
* N
, void*){
3428 llvm::raw_string_ostream
Out(sbuf
);
3430 // Program Location.
3431 ProgramPoint Loc
= N
->getLocation();
3433 switch (Loc
.getKind()) {
3434 case ProgramPoint::BlockEntranceKind
:
3435 Out
<< "Block Entrance: B"
3436 << cast
<BlockEntrance
>(Loc
).getBlock()->getBlockID();
3439 case ProgramPoint::BlockExitKind
:
3443 case ProgramPoint::CallEnterKind
:
3447 case ProgramPoint::CallExitKind
:
3452 if (StmtPoint
*L
= dyn_cast
<StmtPoint
>(&Loc
)) {
3453 const Stmt
* S
= L
->getStmt();
3454 SourceLocation SLoc
= S
->getLocStart();
3456 Out
<< S
->getStmtClassName() << ' ' << (void*) S
<< ' ';
3457 LangOptions LO
; // FIXME.
3458 S
->printPretty(Out
, 0, PrintingPolicy(LO
));
3460 if (SLoc
.isFileID()) {
3462 << GraphPrintSourceManager
->getInstantiationLineNumber(SLoc
)
3464 << GraphPrintSourceManager
->getInstantiationColumnNumber(SLoc
)
3468 if (isa
<PreStmt
>(Loc
))
3469 Out
<< "\\lPreStmt\\l;";
3470 else if (isa
<PostLoad
>(Loc
))
3471 Out
<< "\\lPostLoad\\l;";
3472 else if (isa
<PostStore
>(Loc
))
3473 Out
<< "\\lPostStore\\l";
3474 else if (isa
<PostLValue
>(Loc
))
3475 Out
<< "\\lPostLValue\\l";
3478 // FIXME: Replace with a general scheme to determine
3479 // the name of the check.
3480 if (GraphPrintCheckerState
->isImplicitNullDeref(N
))
3481 Out
<< "\\|Implicit-Null Dereference.\\l";
3482 else if (GraphPrintCheckerState
->isExplicitNullDeref(N
))
3483 Out
<< "\\|Explicit-Null Dereference.\\l";
3484 else if (GraphPrintCheckerState
->isUndefDeref(N
))
3485 Out
<< "\\|Dereference of undefialied value.\\l";
3486 else if (GraphPrintCheckerState
->isUndefStore(N
))
3487 Out
<< "\\|Store to Undefined Loc.";
3488 else if (GraphPrintCheckerState
->isUndefResult(N
))
3489 Out
<< "\\|Result of operation is undefined.";
3490 else if (GraphPrintCheckerState
->isNoReturnCall(N
))
3491 Out
<< "\\|Call to function marked \"noreturn\".";
3492 else if (GraphPrintCheckerState
->isBadCall(N
))
3493 Out
<< "\\|Call to NULL/Undefined.";
3494 else if (GraphPrintCheckerState
->isUndefArg(N
))
3495 Out
<< "\\|Argument in call is undefined";
3501 const BlockEdge
& E
= cast
<BlockEdge
>(Loc
);
3502 Out
<< "Edge: (B" << E
.getSrc()->getBlockID() << ", B"
3503 << E
.getDst()->getBlockID() << ')';
3505 if (const Stmt
* T
= E
.getSrc()->getTerminator()) {
3507 SourceLocation SLoc
= T
->getLocStart();
3509 Out
<< "\\|Terminator: ";
3510 LangOptions LO
; // FIXME.
3511 E
.getSrc()->printTerminator(Out
, LO
);
3513 if (SLoc
.isFileID()) {
3515 << GraphPrintSourceManager
->getInstantiationLineNumber(SLoc
)
3517 << GraphPrintSourceManager
->getInstantiationColumnNumber(SLoc
);
3520 if (isa
<SwitchStmt
>(T
)) {
3521 const Stmt
* Label
= E
.getDst()->getLabel();
3524 if (const CaseStmt
* C
= dyn_cast
<CaseStmt
>(Label
)) {
3526 LangOptions LO
; // FIXME.
3527 C
->getLHS()->printPretty(Out
, 0, PrintingPolicy(LO
));
3529 if (const Stmt
* RHS
= C
->getRHS()) {
3531 RHS
->printPretty(Out
, 0, PrintingPolicy(LO
));
3537 assert (isa
<DefaultStmt
>(Label
));
3538 Out
<< "\\ldefault:";
3542 Out
<< "\\l(implicit) default:";
3544 else if (isa
<IndirectGotoStmt
>(T
)) {
3548 Out
<< "\\lCondition: ";
3549 if (*E
.getSrc()->succ_begin() == E
.getDst())
3559 // FIXME: Replace with a general scheme to determine
3560 // the name of the check.
3561 if (GraphPrintCheckerState
->isUndefControlFlow(N
)) {
3562 Out
<< "\\|Control-flow based on\\lUndefined value.\\l";
3568 const GRState
*state
= N
->getState();
3569 Out
<< "\\|StateID: " << (void*) state
3570 << " NodeID: " << (void*) N
<< "\\|";
3571 state
->printDOT(Out
, *N
->getLocationContext()->getCFG());
3576 } // end llvm namespace
3580 template <typename ITERATOR
>
3581 ExplodedNode
* GetGraphNode(ITERATOR I
) { return *I
; }
3583 template <> ExplodedNode
*
3584 GetGraphNode
<llvm::DenseMap
<ExplodedNode
*, Expr
*>::iterator
>
3585 (llvm::DenseMap
<ExplodedNode
*, Expr
*>::iterator I
) {
3590 void ExprEngine::ViewGraph(bool trim
) {
3593 std::vector
<ExplodedNode
*> Src
;
3595 // Flush any outstanding reports to make sure we cover all the nodes.
3596 // This does not cause them to get displayed.
3597 for (BugReporter::iterator I
=BR
.begin(), E
=BR
.end(); I
!=E
; ++I
)
3598 const_cast<BugType
*>(*I
)->FlushReports(BR
);
3600 // Iterate through the reports and get their nodes.
3601 for (BugReporter::iterator I
=BR
.begin(), E
=BR
.end(); I
!=E
; ++I
) {
3602 for (BugType::const_iterator I2
=(*I
)->begin(), E2
=(*I
)->end();
3604 const BugReportEquivClass
& EQ
= *I2
;
3605 const BugReport
&R
= **EQ
.begin();
3606 ExplodedNode
*N
= const_cast<ExplodedNode
*>(R
.getErrorNode());
3607 if (N
) Src
.push_back(N
);
3611 ViewGraph(&Src
[0], &Src
[0]+Src
.size());
3614 GraphPrintCheckerState
= this;
3615 GraphPrintSourceManager
= &getContext().getSourceManager();
3617 llvm::ViewGraph(*G
.roots_begin(), "ExprEngine");
3619 GraphPrintCheckerState
= NULL
;
3620 GraphPrintSourceManager
= NULL
;
3625 void ExprEngine::ViewGraph(ExplodedNode
** Beg
, ExplodedNode
** End
) {
3627 GraphPrintCheckerState
= this;
3628 GraphPrintSourceManager
= &getContext().getSourceManager();
3630 std::auto_ptr
<ExplodedGraph
> TrimmedG(G
.Trim(Beg
, End
).first
);
3632 if (!TrimmedG
.get())
3633 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
3635 llvm::ViewGraph(*TrimmedG
->roots_begin(), "TrimmedExprEngine");
3637 GraphPrintCheckerState
= NULL
;
3638 GraphPrintSourceManager
= NULL
;