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 "InternalChecks.h"
19 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
20 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/Checker.h"
25 #include "clang/AST/CharUnits.h"
26 #include "clang/AST/ParentMap.h"
27 #include "clang/AST/StmtObjC.h"
28 #include "clang/AST/DeclCXX.h"
29 #include "clang/Basic/Builtins.h"
30 #include "clang/Basic/SourceManager.h"
31 #include "clang/Basic/SourceManager.h"
32 #include "clang/Basic/PrettyStackTrace.h"
33 #include "llvm/Support/raw_ostream.h"
34 #include "llvm/ADT/ImmutableList.h"
37 #include "llvm/Support/GraphWriter.h"
40 using namespace clang
;
43 using llvm::dyn_cast_or_null
;
48 // Trait class for recording returned expression in the state.
51 typedef const Stmt
*data_type
;
53 int ReturnExpr::TagInt
;
56 //===----------------------------------------------------------------------===//
58 //===----------------------------------------------------------------------===//
60 static inline Selector
GetNullarySelector(const char* name
, ASTContext
& Ctx
) {
61 IdentifierInfo
* II
= &Ctx
.Idents
.get(name
);
62 return Ctx
.Selectors
.getSelector(0, &II
);
65 //===----------------------------------------------------------------------===//
66 // Checker worklist routines.
67 //===----------------------------------------------------------------------===//
69 void ExprEngine::CheckerVisit(const Stmt
*S
, ExplodedNodeSet
&Dst
,
70 ExplodedNodeSet
&Src
, CallbackKind Kind
) {
72 // Determine if we already have a cached 'CheckersOrdered' vector
73 // specifically tailored for the provided <CallbackKind, Stmt kind>. This
74 // can reduce the number of checkers actually called.
75 CheckersOrdered
*CO
= &Checkers
;
76 llvm::OwningPtr
<CheckersOrdered
> NewCO
;
78 // The cache key is made up of the and the callback kind (pre- or post-visit)
79 // and the statement kind.
80 CallbackTag K
= GetCallbackTag(Kind
, S
->getStmtClass());
82 CheckersOrdered
*& CO_Ref
= COCache
[K
];
85 // If we have no previously cached CheckersOrdered vector for this
86 // statement kind, then create one.
87 NewCO
.reset(new CheckersOrdered
);
90 // Use the already cached set.
95 // If there are no checkers, return early without doing any
102 ExplodedNodeSet
*PrevSet
= &Src
;
103 unsigned checkersEvaluated
= 0;
105 for (CheckersOrdered::iterator I
=CO
->begin(), E
=CO
->end(); I
!=E
; ++I
) {
106 // If all nodes are sunk, bail out early.
107 if (PrevSet
->empty())
109 ExplodedNodeSet
*CurrSet
= 0;
113 CurrSet
= (PrevSet
== &Tmp
) ? &Src
: &Tmp
;
116 void *tag
= I
->first
;
117 Checker
*checker
= I
->second
;
118 bool respondsToCallback
= true;
120 for (ExplodedNodeSet::iterator NI
= PrevSet
->begin(), NE
= PrevSet
->end();
123 checker
->GR_Visit(*CurrSet
, *Builder
, *this, S
, *NI
, tag
,
124 Kind
== PreVisitStmtCallback
, respondsToCallback
);
132 if (respondsToCallback
)
133 NewCO
->push_back(*I
);
137 // If we built NewCO, check if we called all the checkers. This is important
138 // so that we know that we accurately determined the entire set of checkers
139 // that responds to this callback. Note that 'checkersEvaluated' might
140 // not be the same as Checkers.size() if one of the Checkers generates
142 if (NewCO
.get() && checkersEvaluated
== Checkers
.size())
143 CO_Ref
= NewCO
.take();
145 // Don't autotransition. The CheckerContext objects should do this
149 void ExprEngine::CheckerVisitObjCMessage(const ObjCMessage
&msg
,
150 ExplodedNodeSet
&Dst
,
151 ExplodedNodeSet
&Src
,
154 if (Checkers
.empty()) {
160 ExplodedNodeSet
*PrevSet
= &Src
;
162 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end(); I
!=E
; ++I
)
164 ExplodedNodeSet
*CurrSet
= 0;
168 CurrSet
= (PrevSet
== &Tmp
) ? &Src
: &Tmp
;
172 void *tag
= I
->first
;
173 Checker
*checker
= I
->second
;
175 for (ExplodedNodeSet::iterator NI
= PrevSet
->begin(), NE
= PrevSet
->end();
177 checker
->GR_visitObjCMessage(*CurrSet
, *Builder
, *this, msg
,
178 *NI
, tag
, isPrevisit
);
180 // Update which NodeSet is the current one.
184 // Don't autotransition. The CheckerContext objects should do this
188 void ExprEngine::CheckerEvalNilReceiver(const ObjCMessage
&msg
,
189 ExplodedNodeSet
&Dst
,
190 const GRState
*state
,
191 ExplodedNode
*Pred
) {
192 bool evaluated
= false;
193 ExplodedNodeSet DstTmp
;
195 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end();I
!=E
;++I
) {
196 void *tag
= I
->first
;
197 Checker
*checker
= I
->second
;
199 if (checker
->GR_evalNilReceiver(DstTmp
, *Builder
, *this, msg
, Pred
, state
,
204 // The checker didn't evaluate the expr. Restore the Dst.
214 // CheckerEvalCall returns true if one of the checkers processed the node.
215 // This may return void when all call evaluation logic goes to some checker
217 bool ExprEngine::CheckerEvalCall(const CallExpr
*CE
,
218 ExplodedNodeSet
&Dst
,
219 ExplodedNode
*Pred
) {
220 bool evaluated
= false;
221 ExplodedNodeSet DstTmp
;
223 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end();I
!=E
;++I
) {
224 void *tag
= I
->first
;
225 Checker
*checker
= I
->second
;
227 if (checker
->GR_evalCallExpr(DstTmp
, *Builder
, *this, CE
, Pred
, tag
)) {
231 // The checker didn't evaluate the expr. Restore the DstTmp set.
243 // FIXME: This is largely copy-paste from CheckerVisit(). Need to
245 void ExprEngine::CheckerVisitBind(const Stmt
*StoreE
, ExplodedNodeSet
&Dst
,
246 ExplodedNodeSet
&Src
, SVal location
,
247 SVal val
, bool isPrevisit
) {
249 if (Checkers
.empty()) {
255 ExplodedNodeSet
*PrevSet
= &Src
;
257 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end(); I
!=E
; ++I
)
259 ExplodedNodeSet
*CurrSet
= 0;
263 CurrSet
= (PrevSet
== &Tmp
) ? &Src
: &Tmp
;
267 void *tag
= I
->first
;
268 Checker
*checker
= I
->second
;
270 for (ExplodedNodeSet::iterator NI
= PrevSet
->begin(), NE
= PrevSet
->end();
272 checker
->GR_VisitBind(*CurrSet
, *Builder
, *this, StoreE
,
273 *NI
, tag
, location
, val
, isPrevisit
);
275 // Update which NodeSet is the current one.
279 // Don't autotransition. The CheckerContext objects should do this
282 //===----------------------------------------------------------------------===//
283 // Engine construction and deletion.
284 //===----------------------------------------------------------------------===//
286 static void RegisterInternalChecks(ExprEngine
&Eng
) {
287 // Register internal "built-in" BugTypes with the BugReporter. These BugTypes
288 // are different than what probably many checks will do since they don't
289 // create BugReports on-the-fly but instead wait until ExprEngine finishes
290 // analyzing a function. Generation of BugReport objects is done via a call
291 // to 'FlushReports' from BugReporter.
292 // The following checks do not need to have their associated BugTypes
293 // explicitly registered with the BugReporter. If they issue any BugReports,
294 // their associated BugType will get registered with the BugReporter
295 // automatically. Note that the check itself is owned by the ExprEngine
297 RegisterAdjustedReturnValueChecker(Eng
);
298 // CallAndMessageChecker should be registered before AttrNonNullChecker,
299 // where we assume arguments are not undefined.
300 RegisterCallAndMessageChecker(Eng
);
301 RegisterAttrNonNullChecker(Eng
);
302 RegisterDereferenceChecker(Eng
);
303 RegisterVLASizeChecker(Eng
);
304 RegisterDivZeroChecker(Eng
);
305 RegisterReturnUndefChecker(Eng
);
306 RegisterUndefinedArraySubscriptChecker(Eng
);
307 RegisterUndefinedAssignmentChecker(Eng
);
308 RegisterUndefBranchChecker(Eng
);
309 RegisterUndefCapturedBlockVarChecker(Eng
);
310 RegisterUndefResultChecker(Eng
);
312 // This is not a checker yet.
313 RegisterNoReturnFunctionChecker(Eng
);
314 RegisterBuiltinFunctionChecker(Eng
);
315 RegisterOSAtomicChecker(Eng
);
318 ExprEngine::ExprEngine(AnalysisManager
&mgr
, TransferFuncs
*tf
)
321 G(Engine
.getGraph()),
323 StateMgr(getContext(), mgr
.getStoreManagerCreator(),
324 mgr
.getConstraintManagerCreator(), G
.getAllocator(),
326 SymMgr(StateMgr
.getSymbolManager()),
327 svalBuilder(StateMgr
.getSValBuilder()),
328 EntryNode(NULL
), currentStmt(NULL
),
329 NSExceptionII(NULL
), NSExceptionInstanceRaiseSelectors(NULL
),
330 RaiseSel(GetNullarySelector("raise", getContext())),
331 BR(mgr
, *this), TF(tf
) {
332 // Register internal checks.
333 RegisterInternalChecks(*this);
335 // FIXME: Eventually remove the TF object entirely.
336 TF
->RegisterChecks(*this);
337 TF
->RegisterPrinters(getStateManager().Printers
);
339 mgr
.getCheckerManager()->registerCheckersToEngine(*this);
341 if (mgr
.shouldEagerlyTrimExplodedGraph()) {
342 // Enable eager node reclaimation when constructing the ExplodedGraph.
343 G
.enableNodeReclamation();
347 ExprEngine::~ExprEngine() {
349 delete [] NSExceptionInstanceRaiseSelectors
;
351 // Delete the set of checkers.
352 for (CheckersOrdered::iterator I
=Checkers
.begin(), E
=Checkers
.end(); I
!=E
;++I
)
355 for (CheckersOrderedCache::iterator I
=COCache
.begin(), E
=COCache
.end();
360 //===----------------------------------------------------------------------===//
362 //===----------------------------------------------------------------------===//
364 const GRState
* ExprEngine::getInitialState(const LocationContext
*InitLoc
) {
365 const GRState
*state
= StateMgr
.getInitialState(InitLoc
);
369 // FIXME: It would be nice if we had a more general mechanism to add
370 // such preconditions. Some day.
372 const Decl
*D
= InitLoc
->getDecl();
373 if (const FunctionDecl
*FD
= dyn_cast
<FunctionDecl
>(D
)) {
374 // Precondition: the first argument of 'main' is an integer guaranteed
376 const IdentifierInfo
*II
= FD
->getIdentifier();
377 if (!II
|| !(II
->getName() == "main" && FD
->getNumParams() > 0))
380 const ParmVarDecl
*PD
= FD
->getParamDecl(0);
381 QualType T
= PD
->getType();
382 if (!T
->isIntegerType())
385 const MemRegion
*R
= state
->getRegion(PD
, InitLoc
);
389 SVal V
= state
->getSVal(loc::MemRegionVal(R
));
390 SVal Constraint_untested
= evalBinOp(state
, BO_GT
, V
,
391 svalBuilder
.makeZeroVal(T
),
394 DefinedOrUnknownSVal
*Constraint
=
395 dyn_cast
<DefinedOrUnknownSVal
>(&Constraint_untested
);
400 if (const GRState
*newState
= state
->assume(*Constraint
, true))
406 if (const ObjCMethodDecl
*MD
= dyn_cast
<ObjCMethodDecl
>(D
)) {
407 // Precondition: 'self' is always non-null upon entry to an Objective-C
409 const ImplicitParamDecl
*SelfD
= MD
->getSelfDecl();
410 const MemRegion
*R
= state
->getRegion(SelfD
, InitLoc
);
411 SVal V
= state
->getSVal(loc::MemRegionVal(R
));
413 if (const Loc
*LV
= dyn_cast
<Loc
>(&V
)) {
414 // Assume that the pointer value in 'self' is non-null.
415 state
= state
->assume(*LV
, true);
416 assert(state
&& "'self' cannot be null");
424 //===----------------------------------------------------------------------===//
425 // Top-level transfer function logic (Dispatcher).
426 //===----------------------------------------------------------------------===//
428 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
429 /// logic for handling assumptions on symbolic values.
430 const GRState
*ExprEngine::processAssume(const GRState
*state
, SVal cond
,
432 // Determine if we already have a cached 'CheckersOrdered' vector
433 // specifically tailored for processing assumptions. This
434 // can reduce the number of checkers actually called.
435 CheckersOrdered
*CO
= &Checkers
;
436 llvm::OwningPtr
<CheckersOrdered
> NewCO
;
438 CallbackTag K
= GetCallbackTag(processAssumeCallback
);
439 CheckersOrdered
*& CO_Ref
= COCache
[K
];
442 // If we have no previously cached CheckersOrdered vector for this
443 // statement kind, then create one.
444 NewCO
.reset(new CheckersOrdered
);
447 // Use the already cached set.
452 // Let the checkers have a crack at the assume before the transfer functions
454 for (CheckersOrdered::iterator I
= CO
->begin(), E
= CO
->end(); I
!=E
; ++I
) {
456 // If any checker declares the state infeasible (or if it starts that
461 Checker
*C
= I
->second
;
462 bool respondsToCallback
= true;
464 state
= C
->evalAssume(state
, cond
, assumption
, &respondsToCallback
);
466 // Check if we're building the cache of checkers that care about
468 if (NewCO
.get() && respondsToCallback
)
469 NewCO
->push_back(*I
);
472 // If we got through all the checkers, and we built a list of those that
473 // care about assumptions, save it.
475 CO_Ref
= NewCO
.take();
478 // If the state is infeasible at this point, bail out.
482 return TF
->evalAssume(state
, cond
, assumption
);
485 bool ExprEngine::wantsRegionChangeUpdate(const GRState
* state
) {
486 CallbackTag K
= GetCallbackTag(EvalRegionChangesCallback
);
487 CheckersOrdered
*CO
= COCache
[K
];
492 for (CheckersOrdered::iterator I
= CO
->begin(), E
= CO
->end(); I
!= E
; ++I
) {
493 Checker
*C
= I
->second
;
494 if (C
->wantsRegionChangeUpdate(state
))
502 ExprEngine::processRegionChanges(const GRState
*state
,
503 const MemRegion
* const *Begin
,
504 const MemRegion
* const *End
) {
505 // FIXME: Most of this method is copy-pasted from processAssume.
507 // Determine if we already have a cached 'CheckersOrdered' vector
508 // specifically tailored for processing region changes. This
509 // can reduce the number of checkers actually called.
510 CheckersOrdered
*CO
= &Checkers
;
511 llvm::OwningPtr
<CheckersOrdered
> NewCO
;
513 CallbackTag K
= GetCallbackTag(EvalRegionChangesCallback
);
514 CheckersOrdered
*& CO_Ref
= COCache
[K
];
517 // If we have no previously cached CheckersOrdered vector for this
518 // callback, then create one.
519 NewCO
.reset(new CheckersOrdered
);
522 // Use the already cached set.
526 // If there are no checkers, just return the state as is.
530 for (CheckersOrdered::iterator I
= CO
->begin(), E
= CO
->end(); I
!= E
; ++I
) {
531 // If any checker declares the state infeasible (or if it starts that way),
536 Checker
*C
= I
->second
;
537 bool respondsToCallback
= true;
539 state
= C
->EvalRegionChanges(state
, Begin
, End
, &respondsToCallback
);
541 // See if we're building a cache of checkers that care about region changes.
542 if (NewCO
.get() && respondsToCallback
)
543 NewCO
->push_back(*I
);
546 // If we got through all the checkers, and we built a list of those that
547 // care about region changes, save it.
549 CO_Ref
= NewCO
.take();
554 void ExprEngine::processEndWorklist(bool hasWorkRemaining
) {
555 for (CheckersOrdered::iterator I
= Checkers
.begin(), E
= Checkers
.end();
557 I
->second
->VisitEndAnalysis(G
, BR
, *this);
561 void ExprEngine::processCFGElement(const CFGElement E
,
562 StmtNodeBuilder
& builder
) {
563 switch (E
.getKind()) {
564 case CFGElement::Statement
:
565 ProcessStmt(E
.getAs
<CFGStmt
>(), builder
);
567 case CFGElement::Initializer
:
568 ProcessInitializer(E
.getAs
<CFGInitializer
>(), builder
);
570 case CFGElement::ImplicitDtor
:
571 ProcessImplicitDtor(E
.getAs
<CFGImplicitDtor
>(), builder
);
574 // Suppress compiler warning.
575 llvm_unreachable("Unexpected CFGElement kind.");
579 void ExprEngine::ProcessStmt(const CFGStmt S
, StmtNodeBuilder
& builder
) {
580 // Reclaim any unnecessary nodes in the ExplodedGraph.
581 G
.reclaimRecentlyAllocatedNodes();
582 // Recycle any unused states in the GRStateManager.
583 StateMgr
.recycleUnusedStates();
585 currentStmt
= S
.getStmt();
586 PrettyStackTraceLoc
CrashInfo(getContext().getSourceManager(),
587 currentStmt
->getLocStart(),
588 "Error evaluating statement");
591 EntryNode
= builder
.getPredecessor();
593 // Create the cleaned state.
594 const LocationContext
*LC
= EntryNode
->getLocationContext();
595 SymbolReaper
SymReaper(LC
, currentStmt
, SymMgr
);
597 if (AMgr
.shouldPurgeDead()) {
598 const GRState
*St
= EntryNode
->getState();
600 for (CheckersOrdered::iterator I
= Checkers
.begin(), E
= Checkers
.end();
602 Checker
*checker
= I
->second
;
603 checker
->MarkLiveSymbols(St
, SymReaper
);
606 const StackFrameContext
*SFC
= LC
->getCurrentStackFrame();
607 CleanedState
= StateMgr
.removeDeadBindings(St
, SFC
, SymReaper
);
609 CleanedState
= EntryNode
->getState();
612 // Process any special transfer function for dead symbols.
615 if (!SymReaper
.hasDeadSymbols())
618 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
619 SaveOr
OldHasGen(Builder
->hasGeneratedNode
);
621 SaveAndRestore
<bool> OldPurgeDeadSymbols(Builder
->PurgingDeadSymbols
);
622 Builder
->PurgingDeadSymbols
= true;
624 // FIXME: This should soon be removed.
625 ExplodedNodeSet Tmp2
;
626 getTF().evalDeadSymbols(Tmp2
, *this, *Builder
, EntryNode
,
627 CleanedState
, SymReaper
);
629 if (Checkers
.empty())
632 ExplodedNodeSet Tmp3
;
633 ExplodedNodeSet
*SrcSet
= &Tmp2
;
634 for (CheckersOrdered::iterator I
= Checkers
.begin(), E
= Checkers
.end();
636 ExplodedNodeSet
*DstSet
= 0;
640 DstSet
= (SrcSet
== &Tmp2
) ? &Tmp3
: &Tmp2
;
644 void *tag
= I
->first
;
645 Checker
*checker
= I
->second
;
646 for (ExplodedNodeSet::iterator NI
= SrcSet
->begin(), NE
= SrcSet
->end();
648 checker
->GR_evalDeadSymbols(*DstSet
, *Builder
, *this, currentStmt
,
649 *NI
, SymReaper
, tag
);
654 if (!Builder
->BuildSinks
&& !Builder
->hasGeneratedNode
)
658 bool HasAutoGenerated
= false;
660 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
663 // Set the cleaned state.
664 Builder
->SetCleanedState(*I
== EntryNode
? CleanedState
: GetState(*I
));
666 // Visit the statement.
667 Visit(currentStmt
, *I
, Dst
);
669 // Do we need to auto-generate a node? We only need to do this to generate
670 // a node with a "cleaned" state; CoreEngine will actually handle
671 // auto-transitions for other cases.
672 if (Dst
.size() == 1 && *Dst
.begin() == EntryNode
673 && !Builder
->hasGeneratedNode
&& !HasAutoGenerated
) {
674 HasAutoGenerated
= true;
675 builder
.generateNode(currentStmt
, GetState(EntryNode
), *I
);
679 // NULL out these variables to cleanup.
688 void ExprEngine::ProcessInitializer(const CFGInitializer Init
,
689 StmtNodeBuilder
&builder
) {
690 // We don't set EntryNode and currentStmt. And we don't clean up state.
691 const CXXCtorInitializer
*BMI
= Init
.getInitializer();
693 ExplodedNode
*pred
= builder
.getPredecessor();
695 const StackFrameContext
*stackFrame
= cast
<StackFrameContext
>(pred
->getLocationContext());
696 const CXXConstructorDecl
*decl
= cast
<CXXConstructorDecl
>(stackFrame
->getDecl());
697 const CXXThisRegion
*thisReg
= getCXXThisRegion(decl
, stackFrame
);
699 SVal thisVal
= pred
->getState()->getSVal(thisReg
);
701 if (BMI
->isAnyMemberInitializer()) {
704 // Evaluate the initializer.
705 Visit(BMI
->getInit(), pred
, Dst
);
707 for (ExplodedNodeSet::iterator I
= Dst
.begin(), E
= Dst
.end(); I
!= E
; ++I
){
708 ExplodedNode
*Pred
= *I
;
709 const GRState
*state
= Pred
->getState();
711 const FieldDecl
*FD
= BMI
->getAnyMember();
713 SVal FieldLoc
= state
->getLValue(FD
, thisVal
);
714 SVal InitVal
= state
->getSVal(BMI
->getInit());
715 state
= state
->bindLoc(FieldLoc
, InitVal
);
717 // Use a custom node building process.
718 PostInitializer
PP(BMI
, stackFrame
);
719 // Builder automatically add the generated node to the deferred set,
720 // which are processed in the builder's dtor.
721 builder
.generateNode(PP
, state
, Pred
);
726 assert(BMI
->isBaseInitializer());
728 // Get the base class declaration.
729 const CXXConstructExpr
*ctorExpr
= cast
<CXXConstructExpr
>(BMI
->getInit());
731 // Create the base object region.
733 getStoreManager().evalDerivedToBase(thisVal
, ctorExpr
->getType());
734 const MemRegion
*baseReg
= baseVal
.getAsRegion();
738 VisitCXXConstructExpr(ctorExpr
, baseReg
, pred
, dst
);
741 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D
,
742 StmtNodeBuilder
&builder
) {
745 switch (D
.getDtorKind()) {
746 case CFGElement::AutomaticObjectDtor
:
747 ProcessAutomaticObjDtor(cast
<CFGAutomaticObjDtor
>(D
), builder
);
749 case CFGElement::BaseDtor
:
750 ProcessBaseDtor(cast
<CFGBaseDtor
>(D
), builder
);
752 case CFGElement::MemberDtor
:
753 ProcessMemberDtor(cast
<CFGMemberDtor
>(D
), builder
);
755 case CFGElement::TemporaryDtor
:
756 ProcessTemporaryDtor(cast
<CFGTemporaryDtor
>(D
), builder
);
759 llvm_unreachable("Unexpected dtor kind.");
763 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor dtor
,
764 StmtNodeBuilder
&builder
) {
765 ExplodedNode
*pred
= builder
.getPredecessor();
766 const GRState
*state
= pred
->getState();
767 const VarDecl
*varDecl
= dtor
.getVarDecl();
769 QualType varType
= varDecl
->getType();
771 if (const ReferenceType
*refType
= varType
->getAs
<ReferenceType
>())
772 varType
= refType
->getPointeeType();
774 const CXXRecordDecl
*recordDecl
= varType
->getAsCXXRecordDecl();
775 assert(recordDecl
&& "get CXXRecordDecl fail");
776 const CXXDestructorDecl
*dtorDecl
= recordDecl
->getDestructor();
778 Loc dest
= state
->getLValue(varDecl
, pred
->getLocationContext());
780 ExplodedNodeSet dstSet
;
781 VisitCXXDestructor(dtorDecl
, cast
<loc::MemRegionVal
>(dest
).getRegion(),
782 dtor
.getTriggerStmt(), pred
, dstSet
);
785 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D
,
786 StmtNodeBuilder
&builder
) {
789 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D
,
790 StmtNodeBuilder
&builder
) {
793 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D
,
794 StmtNodeBuilder
&builder
) {
797 void ExprEngine::Visit(const Stmt
* S
, ExplodedNode
* Pred
,
798 ExplodedNodeSet
& Dst
) {
799 PrettyStackTraceLoc
CrashInfo(getContext().getSourceManager(),
801 "Error evaluating statement");
803 // Expressions to ignore.
804 if (const Expr
*Ex
= dyn_cast
<Expr
>(S
))
805 S
= Ex
->IgnoreParens();
807 // FIXME: add metadata to the CFG so that we can disable
808 // this check when we KNOW that there is no block-level subexpression.
809 // The motivation is that this check requires a hashtable lookup.
811 if (S
!= currentStmt
&& Pred
->getLocationContext()->getCFG()->isBlkExpr(S
)) {
816 switch (S
->getStmtClass()) {
817 // C++ stuff we don't support yet.
818 case Stmt::CXXBindTemporaryExprClass
:
819 case Stmt::CXXCatchStmtClass
:
820 case Stmt::CXXDefaultArgExprClass
:
821 case Stmt::CXXDependentScopeMemberExprClass
:
822 case Stmt::ExprWithCleanupsClass
:
823 case Stmt::CXXNullPtrLiteralExprClass
:
824 case Stmt::CXXPseudoDestructorExprClass
:
825 case Stmt::CXXTemporaryObjectExprClass
:
826 case Stmt::CXXThrowExprClass
:
827 case Stmt::CXXTryStmtClass
:
828 case Stmt::CXXTypeidExprClass
:
829 case Stmt::CXXUuidofExprClass
:
830 case Stmt::CXXUnresolvedConstructExprClass
:
831 case Stmt::CXXScalarValueInitExprClass
:
832 case Stmt::DependentScopeDeclRefExprClass
:
833 case Stmt::UnaryTypeTraitExprClass
:
834 case Stmt::BinaryTypeTraitExprClass
:
835 case Stmt::UnresolvedLookupExprClass
:
836 case Stmt::UnresolvedMemberExprClass
:
837 case Stmt::CXXNoexceptExprClass
:
838 case Stmt::PackExpansionExprClass
:
839 case Stmt::SubstNonTypeTemplateParmPackExprClass
:
841 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
842 Builder
->BuildSinks
= true;
843 MakeNode(Dst
, S
, Pred
, GetState(Pred
));
847 case Stmt::ParenExprClass
:
848 llvm_unreachable("ParenExprs already handled.");
849 // Cases that should never be evaluated simply because they shouldn't
850 // appear in the CFG.
851 case Stmt::BreakStmtClass
:
852 case Stmt::CaseStmtClass
:
853 case Stmt::CompoundStmtClass
:
854 case Stmt::ContinueStmtClass
:
855 case Stmt::DefaultStmtClass
:
856 case Stmt::DoStmtClass
:
857 case Stmt::GotoStmtClass
:
858 case Stmt::IndirectGotoStmtClass
:
859 case Stmt::LabelStmtClass
:
860 case Stmt::NoStmtClass
:
861 case Stmt::NullStmtClass
:
862 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
865 case Stmt::GNUNullExprClass
: {
866 MakeNode(Dst
, S
, Pred
, GetState(Pred
)->BindExpr(S
, svalBuilder
.makeNull()));
870 case Stmt::ObjCAtSynchronizedStmtClass
:
871 VisitObjCAtSynchronizedStmt(cast
<ObjCAtSynchronizedStmt
>(S
), Pred
, Dst
);
874 case Stmt::ObjCPropertyRefExprClass
:
875 VisitObjCPropertyRefExpr(cast
<ObjCPropertyRefExpr
>(S
), Pred
, Dst
);
878 // Cases not handled yet; but will handle some day.
879 case Stmt::DesignatedInitExprClass
:
880 case Stmt::ExtVectorElementExprClass
:
881 case Stmt::ImaginaryLiteralClass
:
882 case Stmt::ImplicitValueInitExprClass
:
883 case Stmt::ObjCAtCatchStmtClass
:
884 case Stmt::ObjCAtFinallyStmtClass
:
885 case Stmt::ObjCAtTryStmtClass
:
886 case Stmt::ObjCEncodeExprClass
:
887 case Stmt::ObjCIsaExprClass
:
888 case Stmt::ObjCProtocolExprClass
:
889 case Stmt::ObjCSelectorExprClass
:
890 case Stmt::ObjCStringLiteralClass
:
891 case Stmt::ParenListExprClass
:
892 case Stmt::PredefinedExprClass
:
893 case Stmt::ShuffleVectorExprClass
:
894 case Stmt::VAArgExprClass
:
895 case Stmt::CUDAKernelCallExprClass
:
896 case Stmt::OpaqueValueExprClass
:
899 // Cases we intentionally don't evaluate, since they don't need
900 // to be explicitly evaluated.
901 case Stmt::AddrLabelExprClass
:
902 case Stmt::IntegerLiteralClass
:
903 case Stmt::CharacterLiteralClass
:
904 case Stmt::CXXBoolLiteralExprClass
:
905 case Stmt::FloatingLiteralClass
:
906 case Stmt::SizeOfPackExprClass
:
907 Dst
.Add(Pred
); // No-op. Simply propagate the current state unchanged.
910 case Stmt::ArraySubscriptExprClass
:
911 VisitLvalArraySubscriptExpr(cast
<ArraySubscriptExpr
>(S
), Pred
, Dst
);
914 case Stmt::AsmStmtClass
:
915 VisitAsmStmt(cast
<AsmStmt
>(S
), Pred
, Dst
);
918 case Stmt::BlockDeclRefExprClass
: {
919 const BlockDeclRefExpr
*BE
= cast
<BlockDeclRefExpr
>(S
);
920 VisitCommonDeclRefExpr(BE
, BE
->getDecl(), Pred
, Dst
);
924 case Stmt::BlockExprClass
:
925 VisitBlockExpr(cast
<BlockExpr
>(S
), Pred
, Dst
);
928 case Stmt::BinaryOperatorClass
: {
929 const BinaryOperator
* B
= cast
<BinaryOperator
>(S
);
930 if (B
->isLogicalOp()) {
931 VisitLogicalExpr(B
, Pred
, Dst
);
934 else if (B
->getOpcode() == BO_Comma
) {
935 const GRState
* state
= GetState(Pred
);
936 MakeNode(Dst
, B
, Pred
, state
->BindExpr(B
, state
->getSVal(B
->getRHS())));
940 if (AMgr
.shouldEagerlyAssume() &&
941 (B
->isRelationalOp() || B
->isEqualityOp())) {
943 VisitBinaryOperator(cast
<BinaryOperator
>(S
), Pred
, Tmp
);
944 evalEagerlyAssume(Dst
, Tmp
, cast
<Expr
>(S
));
947 VisitBinaryOperator(cast
<BinaryOperator
>(S
), Pred
, Dst
);
952 case Stmt::CallExprClass
: {
953 const CallExpr
* C
= cast
<CallExpr
>(S
);
954 VisitCall(C
, Pred
, C
->arg_begin(), C
->arg_end(), Dst
);
958 case Stmt::CXXConstructExprClass
: {
959 const CXXConstructExpr
*C
= cast
<CXXConstructExpr
>(S
);
960 // For block-level CXXConstructExpr, we don't have a destination region.
961 // Let VisitCXXConstructExpr() create one.
962 VisitCXXConstructExpr(C
, 0, Pred
, Dst
);
966 case Stmt::CXXMemberCallExprClass
: {
967 const CXXMemberCallExpr
*MCE
= cast
<CXXMemberCallExpr
>(S
);
968 VisitCXXMemberCallExpr(MCE
, Pred
, Dst
);
972 case Stmt::CXXOperatorCallExprClass
: {
973 const CXXOperatorCallExpr
*C
= cast
<CXXOperatorCallExpr
>(S
);
974 VisitCXXOperatorCallExpr(C
, Pred
, Dst
);
978 case Stmt::CXXNewExprClass
: {
979 const CXXNewExpr
*NE
= cast
<CXXNewExpr
>(S
);
980 VisitCXXNewExpr(NE
, Pred
, Dst
);
984 case Stmt::CXXDeleteExprClass
: {
985 const CXXDeleteExpr
*CDE
= cast
<CXXDeleteExpr
>(S
);
986 VisitCXXDeleteExpr(CDE
, Pred
, Dst
);
989 // FIXME: ChooseExpr is really a constant. We need to fix
990 // the CFG do not model them as explicit control-flow.
992 case Stmt::ChooseExprClass
: { // __builtin_choose_expr
993 const ChooseExpr
* C
= cast
<ChooseExpr
>(S
);
994 VisitGuardedExpr(C
, C
->getLHS(), C
->getRHS(), Pred
, Dst
);
998 case Stmt::CompoundAssignOperatorClass
:
999 VisitBinaryOperator(cast
<BinaryOperator
>(S
), Pred
, Dst
);
1002 case Stmt::CompoundLiteralExprClass
:
1003 VisitCompoundLiteralExpr(cast
<CompoundLiteralExpr
>(S
), Pred
, Dst
);
1006 case Stmt::BinaryConditionalOperatorClass
:
1007 case Stmt::ConditionalOperatorClass
: { // '?' operator
1008 const AbstractConditionalOperator
*C
1009 = cast
<AbstractConditionalOperator
>(S
);
1010 VisitGuardedExpr(C
, C
->getTrueExpr(), C
->getFalseExpr(), Pred
, Dst
);
1014 case Stmt::CXXThisExprClass
:
1015 VisitCXXThisExpr(cast
<CXXThisExpr
>(S
), Pred
, Dst
);
1018 case Stmt::DeclRefExprClass
: {
1019 const DeclRefExpr
*DE
= cast
<DeclRefExpr
>(S
);
1020 VisitCommonDeclRefExpr(DE
, DE
->getDecl(), Pred
, Dst
);
1024 case Stmt::DeclStmtClass
:
1025 VisitDeclStmt(cast
<DeclStmt
>(S
), Pred
, Dst
);
1028 case Stmt::ForStmtClass
:
1029 // This case isn't for branch processing, but for handling the
1030 // initialization of a condition variable.
1031 VisitCondInit(cast
<ForStmt
>(S
)->getConditionVariable(), S
, Pred
, Dst
);
1034 case Stmt::ImplicitCastExprClass
:
1035 case Stmt::CStyleCastExprClass
:
1036 case Stmt::CXXStaticCastExprClass
:
1037 case Stmt::CXXDynamicCastExprClass
:
1038 case Stmt::CXXReinterpretCastExprClass
:
1039 case Stmt::CXXConstCastExprClass
:
1040 case Stmt::CXXFunctionalCastExprClass
: {
1041 const CastExpr
* C
= cast
<CastExpr
>(S
);
1042 VisitCast(C
, C
->getSubExpr(), Pred
, Dst
);
1046 case Stmt::IfStmtClass
:
1047 // This case isn't for branch processing, but for handling the
1048 // initialization of a condition variable.
1049 VisitCondInit(cast
<IfStmt
>(S
)->getConditionVariable(), S
, Pred
, Dst
);
1052 case Stmt::InitListExprClass
:
1053 VisitInitListExpr(cast
<InitListExpr
>(S
), Pred
, Dst
);
1056 case Stmt::MemberExprClass
:
1057 VisitMemberExpr(cast
<MemberExpr
>(S
), Pred
, Dst
);
1059 case Stmt::ObjCIvarRefExprClass
:
1060 VisitLvalObjCIvarRefExpr(cast
<ObjCIvarRefExpr
>(S
), Pred
, Dst
);
1063 case Stmt::ObjCForCollectionStmtClass
:
1064 VisitObjCForCollectionStmt(cast
<ObjCForCollectionStmt
>(S
), Pred
, Dst
);
1067 case Stmt::ObjCMessageExprClass
:
1068 VisitObjCMessageExpr(cast
<ObjCMessageExpr
>(S
), Pred
, Dst
);
1071 case Stmt::ObjCAtThrowStmtClass
: {
1072 // FIXME: This is not complete. We basically treat @throw as
1074 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
1075 Builder
->BuildSinks
= true;
1076 MakeNode(Dst
, S
, Pred
, GetState(Pred
));
1080 case Stmt::ReturnStmtClass
:
1081 VisitReturnStmt(cast
<ReturnStmt
>(S
), Pred
, Dst
);
1084 case Stmt::OffsetOfExprClass
:
1085 VisitOffsetOfExpr(cast
<OffsetOfExpr
>(S
), Pred
, Dst
);
1088 case Stmt::SizeOfAlignOfExprClass
:
1089 VisitSizeOfAlignOfExpr(cast
<SizeOfAlignOfExpr
>(S
), Pred
, Dst
);
1092 case Stmt::StmtExprClass
: {
1093 const StmtExpr
* SE
= cast
<StmtExpr
>(S
);
1095 if (SE
->getSubStmt()->body_empty()) {
1096 // Empty statement expression.
1097 assert(SE
->getType() == getContext().VoidTy
1098 && "Empty statement expression must have void type.");
1103 if (Expr
* LastExpr
= dyn_cast
<Expr
>(*SE
->getSubStmt()->body_rbegin())) {
1104 const GRState
* state
= GetState(Pred
);
1105 MakeNode(Dst
, SE
, Pred
, state
->BindExpr(SE
, state
->getSVal(LastExpr
)));
1113 case Stmt::StringLiteralClass
: {
1114 const GRState
* state
= GetState(Pred
);
1115 SVal V
= state
->getLValue(cast
<StringLiteral
>(S
));
1116 MakeNode(Dst
, S
, Pred
, state
->BindExpr(S
, V
));
1120 case Stmt::SwitchStmtClass
:
1121 // This case isn't for branch processing, but for handling the
1122 // initialization of a condition variable.
1123 VisitCondInit(cast
<SwitchStmt
>(S
)->getConditionVariable(), S
, Pred
, Dst
);
1126 case Stmt::UnaryOperatorClass
: {
1127 const UnaryOperator
*U
= cast
<UnaryOperator
>(S
);
1128 if (AMgr
.shouldEagerlyAssume()&&(U
->getOpcode() == UO_LNot
)) {
1129 ExplodedNodeSet Tmp
;
1130 VisitUnaryOperator(U
, Pred
, Tmp
);
1131 evalEagerlyAssume(Dst
, Tmp
, U
);
1134 VisitUnaryOperator(U
, Pred
, Dst
);
1138 case Stmt::WhileStmtClass
:
1139 // This case isn't for branch processing, but for handling the
1140 // initialization of a condition variable.
1141 VisitCondInit(cast
<WhileStmt
>(S
)->getConditionVariable(), S
, Pred
, Dst
);
1146 //===----------------------------------------------------------------------===//
1147 // Block entrance. (Update counters).
1148 //===----------------------------------------------------------------------===//
1150 void ExprEngine::processCFGBlockEntrance(ExplodedNodeSet
&dstNodes
,
1151 GenericNodeBuilder
<BlockEntrance
> &nodeBuilder
){
1153 // FIXME: Refactor this into a checker.
1154 const CFGBlock
*block
= nodeBuilder
.getProgramPoint().getBlock();
1155 ExplodedNode
*pred
= nodeBuilder
.getPredecessor();
1157 if (nodeBuilder
.getBlockCounter().getNumVisited(
1158 pred
->getLocationContext()->getCurrentStackFrame(),
1159 block
->getBlockID()) >= AMgr
.getMaxVisit()) {
1162 nodeBuilder
.generateNode(pred
->getState(), pred
, &tag
, true);
1166 //===----------------------------------------------------------------------===//
1167 // Generic node creation.
1168 //===----------------------------------------------------------------------===//
1170 ExplodedNode
* ExprEngine::MakeNode(ExplodedNodeSet
& Dst
, const Stmt
* S
,
1171 ExplodedNode
* Pred
, const GRState
* St
,
1172 ProgramPoint::Kind K
, const void *tag
) {
1173 assert (Builder
&& "StmtNodeBuilder not present.");
1174 SaveAndRestore
<const void*> OldTag(Builder
->Tag
);
1176 return Builder
->MakeNode(Dst
, S
, Pred
, St
, K
);
1179 //===----------------------------------------------------------------------===//
1180 // Branch processing.
1181 //===----------------------------------------------------------------------===//
1183 const GRState
* ExprEngine::MarkBranch(const GRState
* state
,
1184 const Stmt
* Terminator
,
1187 switch (Terminator
->getStmtClass()) {
1191 case Stmt::BinaryOperatorClass
: { // '&&' and '||'
1193 const BinaryOperator
* B
= cast
<BinaryOperator
>(Terminator
);
1194 BinaryOperator::Opcode Op
= B
->getOpcode();
1196 assert (Op
== BO_LAnd
|| Op
== BO_LOr
);
1198 // For &&, if we take the true branch, then the value of the whole
1199 // expression is that of the RHS expression.
1201 // For ||, if we take the false branch, then the value of the whole
1202 // expression is that of the RHS expression.
1204 const Expr
* Ex
= (Op
== BO_LAnd
&& branchTaken
) ||
1205 (Op
== BO_LOr
&& !branchTaken
)
1206 ? B
->getRHS() : B
->getLHS();
1208 return state
->BindExpr(B
, UndefinedVal(Ex
));
1211 case Stmt::BinaryConditionalOperatorClass
:
1212 case Stmt::ConditionalOperatorClass
: { // ?:
1213 const AbstractConditionalOperator
* C
1214 = cast
<AbstractConditionalOperator
>(Terminator
);
1216 // For ?, if branchTaken == true then the value is either the LHS or
1217 // the condition itself. (GNU extension).
1222 Ex
= C
->getTrueExpr();
1224 Ex
= C
->getFalseExpr();
1226 return state
->BindExpr(C
, UndefinedVal(Ex
));
1229 case Stmt::ChooseExprClass
: { // ?:
1231 const ChooseExpr
* C
= cast
<ChooseExpr
>(Terminator
);
1233 const Expr
* Ex
= branchTaken
? C
->getLHS() : C
->getRHS();
1234 return state
->BindExpr(C
, UndefinedVal(Ex
));
1239 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1240 /// to try to recover some path-sensitivity for casts of symbolic
1241 /// integers that promote their values (which are currently not tracked well).
1242 /// This function returns the SVal bound to Condition->IgnoreCasts if all the
1243 // cast(s) did was sign-extend the original value.
1244 static SVal
RecoverCastedSymbol(GRStateManager
& StateMgr
, const GRState
* state
,
1245 const Stmt
* Condition
, ASTContext
& Ctx
) {
1247 const Expr
*Ex
= dyn_cast
<Expr
>(Condition
);
1249 return UnknownVal();
1252 bool bitsInit
= false;
1254 while (const CastExpr
*CE
= dyn_cast
<CastExpr
>(Ex
)) {
1255 QualType T
= CE
->getType();
1257 if (!T
->isIntegerType())
1258 return UnknownVal();
1260 uint64_t newBits
= Ctx
.getTypeSize(T
);
1261 if (!bitsInit
|| newBits
< bits
) {
1266 Ex
= CE
->getSubExpr();
1269 // We reached a non-cast. Is it a symbolic value?
1270 QualType T
= Ex
->getType();
1272 if (!bitsInit
|| !T
->isIntegerType() || Ctx
.getTypeSize(T
) > bits
)
1273 return UnknownVal();
1275 return state
->getSVal(Ex
);
1278 void ExprEngine::processBranch(const Stmt
* Condition
, const Stmt
* Term
,
1279 BranchNodeBuilder
& builder
) {
1281 // Check for NULL conditions; e.g. "for(;;)"
1283 builder
.markInfeasible(false);
1287 PrettyStackTraceLoc
CrashInfo(getContext().getSourceManager(),
1288 Condition
->getLocStart(),
1289 "Error evaluating branch");
1291 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end();I
!=E
;++I
) {
1292 void *tag
= I
->first
;
1293 Checker
*checker
= I
->second
;
1294 checker
->VisitBranchCondition(builder
, *this, Condition
, tag
);
1297 // If the branch condition is undefined, return;
1298 if (!builder
.isFeasible(true) && !builder
.isFeasible(false))
1301 const GRState
* PrevState
= builder
.getState();
1302 SVal X
= PrevState
->getSVal(Condition
);
1304 if (X
.isUnknown()) {
1305 // Give it a chance to recover from unknown.
1306 if (const Expr
*Ex
= dyn_cast
<Expr
>(Condition
)) {
1307 if (Ex
->getType()->isIntegerType()) {
1308 // Try to recover some path-sensitivity. Right now casts of symbolic
1309 // integers that promote their values are currently not tracked well.
1310 // If 'Condition' is such an expression, try and recover the
1311 // underlying value and use that instead.
1312 SVal recovered
= RecoverCastedSymbol(getStateManager(),
1313 builder
.getState(), Condition
,
1316 if (!recovered
.isUnknown()) {
1321 // If the condition is still unknown, give up.
1322 if (X
.isUnknown()) {
1323 builder
.generateNode(MarkBranch(PrevState
, Term
, true), true);
1324 builder
.generateNode(MarkBranch(PrevState
, Term
, false), false);
1329 DefinedSVal V
= cast
<DefinedSVal
>(X
);
1331 // Process the true branch.
1332 if (builder
.isFeasible(true)) {
1333 if (const GRState
*state
= PrevState
->assume(V
, true))
1334 builder
.generateNode(MarkBranch(state
, Term
, true), true);
1336 builder
.markInfeasible(true);
1339 // Process the false branch.
1340 if (builder
.isFeasible(false)) {
1341 if (const GRState
*state
= PrevState
->assume(V
, false))
1342 builder
.generateNode(MarkBranch(state
, Term
, false), false);
1344 builder
.markInfeasible(false);
1348 /// processIndirectGoto - Called by CoreEngine. Used to generate successor
1349 /// nodes by processing the 'effects' of a computed goto jump.
1350 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder
&builder
) {
1352 const GRState
*state
= builder
.getState();
1353 SVal V
= state
->getSVal(builder
.getTarget());
1355 // Three possibilities:
1357 // (1) We know the computed label.
1358 // (2) The label is NULL (or some other constant), or Undefined.
1359 // (3) We have no clue about the label. Dispatch to all targets.
1362 typedef IndirectGotoNodeBuilder::iterator iterator
;
1364 if (isa
<loc::GotoLabel
>(V
)) {
1365 const LabelDecl
*L
= cast
<loc::GotoLabel
>(V
).getLabel();
1367 for (iterator I
= builder
.begin(), E
= builder
.end(); I
!= E
; ++I
) {
1368 if (I
.getLabel() == L
) {
1369 builder
.generateNode(I
, state
);
1374 assert(false && "No block with label.");
1378 if (isa
<loc::ConcreteInt
>(V
) || isa
<UndefinedVal
>(V
)) {
1379 // Dispatch to the first target and mark it as a sink.
1380 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1381 // FIXME: add checker visit.
1382 // UndefBranches.insert(N);
1386 // This is really a catch-all. We don't support symbolics yet.
1387 // FIXME: Implement dispatch for symbolic pointers.
1389 for (iterator I
=builder
.begin(), E
=builder
.end(); I
!= E
; ++I
)
1390 builder
.generateNode(I
, state
);
1394 void ExprEngine::VisitGuardedExpr(const Expr
* Ex
, const Expr
* L
,
1396 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
) {
1398 assert(Ex
== currentStmt
&&
1399 Pred
->getLocationContext()->getCFG()->isBlkExpr(Ex
));
1401 const GRState
* state
= GetState(Pred
);
1402 SVal X
= state
->getSVal(Ex
);
1404 assert (X
.isUndef());
1406 const Expr
*SE
= (Expr
*) cast
<UndefinedVal
>(X
).getData();
1408 X
= state
->getSVal(SE
);
1410 // Make sure that we invalidate the previous binding.
1411 MakeNode(Dst
, Ex
, Pred
, state
->BindExpr(Ex
, X
, true));
1414 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
1415 /// nodes when the control reaches the end of a function.
1416 void ExprEngine::processEndOfFunction(EndOfFunctionNodeBuilder
& builder
) {
1417 getTF().evalEndPath(*this, builder
);
1418 StateMgr
.EndPath(builder
.getState());
1419 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end(); I
!=E
;++I
){
1420 void *tag
= I
->first
;
1421 Checker
*checker
= I
->second
;
1422 checker
->evalEndPath(builder
, tag
, *this);
1426 /// ProcessSwitch - Called by CoreEngine. Used to generate successor
1427 /// nodes by processing the 'effects' of a switch statement.
1428 void ExprEngine::processSwitch(SwitchNodeBuilder
& builder
) {
1429 typedef SwitchNodeBuilder::iterator iterator
;
1430 const GRState
* state
= builder
.getState();
1431 const Expr
* CondE
= builder
.getCondition();
1432 SVal CondV_untested
= state
->getSVal(CondE
);
1434 if (CondV_untested
.isUndef()) {
1435 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1436 // FIXME: add checker
1437 //UndefBranches.insert(N);
1441 DefinedOrUnknownSVal CondV
= cast
<DefinedOrUnknownSVal
>(CondV_untested
);
1443 const GRState
*DefaultSt
= state
;
1445 iterator I
= builder
.begin(), EI
= builder
.end();
1446 bool defaultIsFeasible
= I
== EI
;
1448 for ( ; I
!= EI
; ++I
) {
1449 const CaseStmt
* Case
= I
.getCase();
1451 // Evaluate the LHS of the case value.
1452 Expr::EvalResult V1
;
1453 bool b
= Case
->getLHS()->Evaluate(V1
, getContext());
1455 // Sanity checks. These go away in Release builds.
1456 assert(b
&& V1
.Val
.isInt() && !V1
.HasSideEffects
1457 && "Case condition must evaluate to an integer constant.");
1458 (void)b
; // silence unused variable warning
1459 assert(V1
.Val
.getInt().getBitWidth() ==
1460 getContext().getTypeSize(CondE
->getType()));
1462 // Get the RHS of the case, if it exists.
1463 Expr::EvalResult V2
;
1465 if (const Expr
* E
= Case
->getRHS()) {
1466 b
= E
->Evaluate(V2
, getContext());
1467 assert(b
&& V2
.Val
.isInt() && !V2
.HasSideEffects
1468 && "Case condition must evaluate to an integer constant.");
1469 (void)b
; // silence unused variable warning
1474 // FIXME: Eventually we should replace the logic below with a range
1475 // comparison, rather than concretize the values within the range.
1476 // This should be easy once we have "ranges" for NonLVals.
1479 nonloc::ConcreteInt
CaseVal(getBasicVals().getValue(V1
.Val
.getInt()));
1480 DefinedOrUnknownSVal Res
= svalBuilder
.evalEQ(DefaultSt
? DefaultSt
: state
,
1483 // Now "assume" that the case matches.
1484 if (const GRState
* stateNew
= state
->assume(Res
, true)) {
1485 builder
.generateCaseStmtNode(I
, stateNew
);
1487 // If CondV evaluates to a constant, then we know that this
1488 // is the *only* case that we can take, so stop evaluating the
1490 if (isa
<nonloc::ConcreteInt
>(CondV
))
1494 // Now "assume" that the case doesn't match. Add this state
1495 // to the default state (if it is feasible).
1497 if (const GRState
*stateNew
= DefaultSt
->assume(Res
, false)) {
1498 defaultIsFeasible
= true;
1499 DefaultSt
= stateNew
;
1502 defaultIsFeasible
= false;
1507 // Concretize the next value in the range.
1508 if (V1
.Val
.getInt() == V2
.Val
.getInt())
1512 assert (V1
.Val
.getInt() <= V2
.Val
.getInt());
1517 if (!defaultIsFeasible
)
1520 // If we have switch(enum value), the default branch is not
1521 // feasible if all of the enum constants not covered by 'case:' statements
1522 // are not feasible values for the switch condition.
1524 // Note that this isn't as accurate as it could be. Even if there isn't
1525 // a case for a particular enum value as long as that enum value isn't
1526 // feasible then it shouldn't be considered for making 'default:' reachable.
1527 const SwitchStmt
*SS
= builder
.getSwitch();
1528 const Expr
*CondExpr
= SS
->getCond()->IgnoreParenImpCasts();
1529 if (CondExpr
->getType()->getAs
<EnumType
>()) {
1530 if (SS
->isAllEnumCasesCovered())
1534 builder
.generateDefaultCaseNode(DefaultSt
);
1537 void ExprEngine::processCallEnter(CallEnterNodeBuilder
&B
) {
1538 const GRState
*state
= B
.getState()->enterStackFrame(B
.getCalleeContext());
1539 B
.generateNode(state
);
1542 void ExprEngine::processCallExit(CallExitNodeBuilder
&B
) {
1543 const GRState
*state
= B
.getState();
1544 const ExplodedNode
*Pred
= B
.getPredecessor();
1545 const StackFrameContext
*calleeCtx
=
1546 cast
<StackFrameContext
>(Pred
->getLocationContext());
1547 const Stmt
*CE
= calleeCtx
->getCallSite();
1549 // If the callee returns an expression, bind its value to CallExpr.
1550 const Stmt
*ReturnedExpr
= state
->get
<ReturnExpr
>();
1552 SVal RetVal
= state
->getSVal(ReturnedExpr
);
1553 state
= state
->BindExpr(CE
, RetVal
);
1554 // Clear the return expr GDM.
1555 state
= state
->remove
<ReturnExpr
>();
1558 // Bind the constructed object value to CXXConstructExpr.
1559 if (const CXXConstructExpr
*CCE
= dyn_cast
<CXXConstructExpr
>(CE
)) {
1560 const CXXThisRegion
*ThisR
=
1561 getCXXThisRegion(CCE
->getConstructor()->getParent(), calleeCtx
);
1563 SVal ThisV
= state
->getSVal(ThisR
);
1564 // Always bind the region to the CXXConstructExpr.
1565 state
= state
->BindExpr(CCE
, ThisV
);
1568 B
.generateNode(state
);
1571 //===----------------------------------------------------------------------===//
1572 // Transfer functions: logical operations ('&&', '||').
1573 //===----------------------------------------------------------------------===//
1575 void ExprEngine::VisitLogicalExpr(const BinaryOperator
* B
, ExplodedNode
* Pred
,
1576 ExplodedNodeSet
& Dst
) {
1578 assert(B
->getOpcode() == BO_LAnd
||
1579 B
->getOpcode() == BO_LOr
);
1581 assert(B
==currentStmt
&& Pred
->getLocationContext()->getCFG()->isBlkExpr(B
));
1583 const GRState
* state
= GetState(Pred
);
1584 SVal X
= state
->getSVal(B
);
1585 assert(X
.isUndef());
1587 const Expr
*Ex
= (const Expr
*) cast
<UndefinedVal
>(X
).getData();
1590 if (Ex
== B
->getRHS()) {
1591 X
= state
->getSVal(Ex
);
1593 // Handle undefined values.
1595 MakeNode(Dst
, B
, Pred
, state
->BindExpr(B
, X
));
1599 DefinedOrUnknownSVal XD
= cast
<DefinedOrUnknownSVal
>(X
);
1601 // We took the RHS. Because the value of the '&&' or '||' expression must
1602 // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
1603 // or 1. Alternatively, we could take a lazy approach, and calculate this
1604 // value later when necessary. We don't have the machinery in place for
1605 // this right now, and since most logical expressions are used for branches,
1606 // the payoff is not likely to be large. Instead, we do eager evaluation.
1607 if (const GRState
*newState
= state
->assume(XD
, true))
1608 MakeNode(Dst
, B
, Pred
,
1609 newState
->BindExpr(B
, svalBuilder
.makeIntVal(1U, B
->getType())));
1611 if (const GRState
*newState
= state
->assume(XD
, false))
1612 MakeNode(Dst
, B
, Pred
,
1613 newState
->BindExpr(B
, svalBuilder
.makeIntVal(0U, B
->getType())));
1616 // We took the LHS expression. Depending on whether we are '&&' or
1617 // '||' we know what the value of the expression is via properties of
1618 // the short-circuiting.
1619 X
= svalBuilder
.makeIntVal(B
->getOpcode() == BO_LAnd
? 0U : 1U,
1621 MakeNode(Dst
, B
, Pred
, state
->BindExpr(B
, X
));
1625 //===----------------------------------------------------------------------===//
1626 // Transfer functions: Loads and stores.
1627 //===----------------------------------------------------------------------===//
1629 void ExprEngine::VisitBlockExpr(const BlockExpr
*BE
, ExplodedNode
*Pred
,
1630 ExplodedNodeSet
&Dst
) {
1632 ExplodedNodeSet Tmp
;
1634 CanQualType T
= getContext().getCanonicalType(BE
->getType());
1635 SVal V
= svalBuilder
.getBlockPointer(BE
->getBlockDecl(), T
,
1636 Pred
->getLocationContext());
1638 MakeNode(Tmp
, BE
, Pred
, GetState(Pred
)->BindExpr(BE
, V
),
1639 ProgramPoint::PostLValueKind
);
1641 // Post-visit the BlockExpr.
1642 CheckerVisit(BE
, Dst
, Tmp
, PostVisitStmtCallback
);
1645 void ExprEngine::VisitCommonDeclRefExpr(const Expr
*Ex
, const NamedDecl
*D
,
1647 ExplodedNodeSet
&Dst
) {
1648 const GRState
*state
= GetState(Pred
);
1650 if (const VarDecl
* VD
= dyn_cast
<VarDecl
>(D
)) {
1651 assert(Ex
->isLValue());
1652 SVal V
= state
->getLValue(VD
, Pred
->getLocationContext());
1654 // For references, the 'lvalue' is the pointer address stored in the
1655 // reference region.
1656 if (VD
->getType()->isReferenceType()) {
1657 if (const MemRegion
*R
= V
.getAsRegion())
1658 V
= state
->getSVal(R
);
1663 MakeNode(Dst
, Ex
, Pred
, state
->BindExpr(Ex
, V
),
1664 ProgramPoint::PostLValueKind
);
1667 if (const EnumConstantDecl
* ED
= dyn_cast
<EnumConstantDecl
>(D
)) {
1668 assert(!Ex
->isLValue());
1669 SVal V
= svalBuilder
.makeIntVal(ED
->getInitVal());
1670 MakeNode(Dst
, Ex
, Pred
, state
->BindExpr(Ex
, V
));
1673 if (const FunctionDecl
* FD
= dyn_cast
<FunctionDecl
>(D
)) {
1674 SVal V
= svalBuilder
.getFunctionPointer(FD
);
1675 MakeNode(Dst
, Ex
, Pred
, state
->BindExpr(Ex
, V
),
1676 ProgramPoint::PostLValueKind
);
1680 "ValueDecl support for this ValueDecl not implemented.");
1683 /// VisitArraySubscriptExpr - Transfer function for array accesses
1684 void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr
* A
,
1686 ExplodedNodeSet
& Dst
){
1688 const Expr
* Base
= A
->getBase()->IgnoreParens();
1689 const Expr
* Idx
= A
->getIdx()->IgnoreParens();
1691 // Evaluate the base.
1692 ExplodedNodeSet Tmp
;
1693 Visit(Base
, Pred
, Tmp
);
1695 for (ExplodedNodeSet::iterator I1
=Tmp
.begin(), E1
=Tmp
.end(); I1
!=E1
; ++I1
) {
1696 ExplodedNodeSet Tmp2
;
1697 Visit(Idx
, *I1
, Tmp2
); // Evaluate the index.
1698 ExplodedNodeSet Tmp3
;
1699 CheckerVisit(A
, Tmp3
, Tmp2
, PreVisitStmtCallback
);
1701 for (ExplodedNodeSet::iterator I2
=Tmp3
.begin(),E2
=Tmp3
.end();I2
!=E2
; ++I2
) {
1702 const GRState
* state
= GetState(*I2
);
1703 SVal V
= state
->getLValue(A
->getType(), state
->getSVal(Idx
),
1704 state
->getSVal(Base
));
1705 assert(A
->isLValue());
1706 MakeNode(Dst
, A
, *I2
, state
->BindExpr(A
, V
), ProgramPoint::PostLValueKind
);
1711 /// VisitMemberExpr - Transfer function for member expressions.
1712 void ExprEngine::VisitMemberExpr(const MemberExpr
* M
, ExplodedNode
* Pred
,
1713 ExplodedNodeSet
& Dst
) {
1715 Expr
*baseExpr
= M
->getBase()->IgnoreParens();
1716 ExplodedNodeSet dstBase
;
1717 Visit(baseExpr
, Pred
, dstBase
);
1719 FieldDecl
*field
= dyn_cast
<FieldDecl
>(M
->getMemberDecl());
1720 if (!field
) // FIXME: skipping member expressions for non-fields
1723 for (ExplodedNodeSet::iterator I
= dstBase
.begin(), E
= dstBase
.end();
1725 const GRState
* state
= GetState(*I
);
1726 SVal baseExprVal
= state
->getSVal(baseExpr
);
1727 if (isa
<nonloc::LazyCompoundVal
>(baseExprVal
) ||
1728 isa
<nonloc::CompoundVal
>(baseExprVal
) ||
1729 // FIXME: This can originate by conjuring a symbol for an unknown
1730 // temporary struct object, see test/Analysis/fields.c:
1732 isa
<nonloc::SymbolVal
>(baseExprVal
)) {
1733 MakeNode(Dst
, M
, *I
, state
->BindExpr(M
, UnknownVal()));
1737 // FIXME: Should we insert some assumption logic in here to determine
1738 // if "Base" is a valid piece of memory? Before we put this assumption
1739 // later when using FieldOffset lvals (which we no longer have).
1741 // For all other cases, compute an lvalue.
1742 SVal L
= state
->getLValue(field
, baseExprVal
);
1744 MakeNode(Dst
, M
, *I
, state
->BindExpr(M
, L
), ProgramPoint::PostLValueKind
);
1746 evalLoad(Dst
, M
, *I
, state
, L
);
1750 /// evalBind - Handle the semantics of binding a value to a specific location.
1751 /// This method is used by evalStore and (soon) VisitDeclStmt, and others.
1752 void ExprEngine::evalBind(ExplodedNodeSet
& Dst
, const Stmt
* StoreE
,
1753 ExplodedNode
* Pred
, const GRState
* state
,
1754 SVal location
, SVal Val
, bool atDeclInit
) {
1757 // Do a previsit of the bind.
1758 ExplodedNodeSet CheckedSet
, Src
;
1760 CheckerVisitBind(StoreE
, CheckedSet
, Src
, location
, Val
, true);
1762 for (ExplodedNodeSet::iterator I
= CheckedSet
.begin(), E
= CheckedSet
.end();
1766 state
= GetState(*I
);
1768 const GRState
* newState
= 0;
1771 const VarRegion
*VR
=
1772 cast
<VarRegion
>(cast
<loc::MemRegionVal
>(location
).getRegion());
1774 newState
= state
->bindDecl(VR
, Val
);
1777 if (location
.isUnknown()) {
1778 // We know that the new state will be the same as the old state since
1779 // the location of the binding is "unknown". Consequently, there
1780 // is no reason to just create a new node.
1784 // We are binding to a value other than 'unknown'. Perform the binding
1785 // using the StoreManager.
1786 newState
= state
->bindLoc(cast
<Loc
>(location
), Val
);
1790 // The next thing to do is check if the TransferFuncs object wants to
1791 // update the state based on the new binding. If the GRTransferFunc object
1792 // doesn't do anything, just auto-propagate the current state.
1794 // NOTE: We use 'AssignE' for the location of the PostStore if 'AssignE'
1795 // is non-NULL. Checkers typically care about
1797 StmtNodeBuilderRef
BuilderRef(Dst
, *Builder
, *this, *I
, newState
, StoreE
,
1800 getTF().evalBind(BuilderRef
, location
, Val
);
1804 /// evalStore - Handle the semantics of a store via an assignment.
1805 /// @param Dst The node set to store generated state nodes
1806 /// @param AssignE The assignment expression if the store happens in an
1808 /// @param LocatioinE The location expression that is stored to.
1809 /// @param state The current simulation state
1810 /// @param location The location to store the value
1811 /// @param Val The value to be stored
1812 void ExprEngine::evalStore(ExplodedNodeSet
& Dst
, const Expr
*AssignE
,
1813 const Expr
* LocationE
,
1815 const GRState
* state
, SVal location
, SVal Val
,
1818 assert(Builder
&& "StmtNodeBuilder must be defined.");
1820 // Proceed with the store. We use AssignE as the anchor for the PostStore
1821 // ProgramPoint if it is non-NULL, and LocationE otherwise.
1822 const Expr
*StoreE
= AssignE
? AssignE
: LocationE
;
1824 if (isa
<loc::ObjCPropRef
>(location
)) {
1825 loc::ObjCPropRef prop
= cast
<loc::ObjCPropRef
>(location
);
1826 ExplodedNodeSet src
= Pred
;
1827 return VisitObjCMessage(ObjCPropertySetter(prop
.getPropRefExpr(),
1828 StoreE
, Val
), src
, Dst
);
1831 // Evaluate the location (checks for bad dereferences).
1832 ExplodedNodeSet Tmp
;
1833 evalLocation(Tmp
, LocationE
, Pred
, state
, location
, tag
, false);
1838 assert(!location
.isUndef());
1840 SaveAndRestore
<ProgramPoint::Kind
> OldSPointKind(Builder
->PointKind
,
1841 ProgramPoint::PostStoreKind
);
1843 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(), NE
=Tmp
.end(); NI
!=NE
; ++NI
)
1844 evalBind(Dst
, StoreE
, *NI
, GetState(*NI
), location
, Val
);
1847 void ExprEngine::evalLoad(ExplodedNodeSet
& Dst
, const Expr
*Ex
,
1849 const GRState
* state
, SVal location
,
1850 const void *tag
, QualType LoadTy
) {
1851 assert(!isa
<NonLoc
>(location
) && "location cannot be a NonLoc.");
1853 if (isa
<loc::ObjCPropRef
>(location
)) {
1854 loc::ObjCPropRef prop
= cast
<loc::ObjCPropRef
>(location
);
1855 ExplodedNodeSet src
= Pred
;
1856 return VisitObjCMessage(ObjCPropertyGetter(prop
.getPropRefExpr(), Ex
),
1860 // Are we loading from a region? This actually results in two loads; one
1861 // to fetch the address of the referenced value and one to fetch the
1862 // referenced value.
1863 if (const TypedRegion
*TR
=
1864 dyn_cast_or_null
<TypedRegion
>(location
.getAsRegion())) {
1866 QualType ValTy
= TR
->getValueType();
1867 if (const ReferenceType
*RT
= ValTy
->getAs
<ReferenceType
>()) {
1868 static int loadReferenceTag
= 0;
1869 ExplodedNodeSet Tmp
;
1870 evalLoadCommon(Tmp
, Ex
, Pred
, state
, location
, &loadReferenceTag
,
1871 getContext().getPointerType(RT
->getPointeeType()));
1873 // Perform the load from the referenced value.
1874 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end() ; I
!=E
; ++I
) {
1875 state
= GetState(*I
);
1876 location
= state
->getSVal(Ex
);
1877 evalLoadCommon(Dst
, Ex
, *I
, state
, location
, tag
, LoadTy
);
1883 evalLoadCommon(Dst
, Ex
, Pred
, state
, location
, tag
, LoadTy
);
1886 void ExprEngine::evalLoadCommon(ExplodedNodeSet
& Dst
, const Expr
*Ex
,
1888 const GRState
* state
, SVal location
,
1889 const void *tag
, QualType LoadTy
) {
1891 // Evaluate the location (checks for bad dereferences).
1892 ExplodedNodeSet Tmp
;
1893 evalLocation(Tmp
, Ex
, Pred
, state
, location
, tag
, true);
1898 assert(!location
.isUndef());
1900 SaveAndRestore
<ProgramPoint::Kind
> OldSPointKind(Builder
->PointKind
);
1902 // Proceed with the load.
1903 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(), NE
=Tmp
.end(); NI
!=NE
; ++NI
) {
1904 state
= GetState(*NI
);
1906 if (location
.isUnknown()) {
1907 // This is important. We must nuke the old binding.
1908 MakeNode(Dst
, Ex
, *NI
, state
->BindExpr(Ex
, UnknownVal()),
1909 ProgramPoint::PostLoadKind
, tag
);
1912 if (LoadTy
.isNull())
1913 LoadTy
= Ex
->getType();
1914 SVal V
= state
->getSVal(cast
<Loc
>(location
), LoadTy
);
1915 MakeNode(Dst
, Ex
, *NI
, state
->bindExprAndLocation(Ex
, location
, V
),
1916 ProgramPoint::PostLoadKind
, tag
);
1921 void ExprEngine::evalLocation(ExplodedNodeSet
&Dst
, const Stmt
*S
,
1923 const GRState
* state
, SVal location
,
1924 const void *tag
, bool isLoad
) {
1925 // Early checks for performance reason.
1926 if (location
.isUnknown() || Checkers
.empty()) {
1931 ExplodedNodeSet Src
, Tmp
;
1933 ExplodedNodeSet
*PrevSet
= &Src
;
1935 for (CheckersOrdered::iterator I
=Checkers
.begin(),E
=Checkers
.end(); I
!=E
; ++I
)
1937 ExplodedNodeSet
*CurrSet
= 0;
1941 CurrSet
= (PrevSet
== &Tmp
) ? &Src
: &Tmp
;
1945 void *tag
= I
->first
;
1946 Checker
*checker
= I
->second
;
1948 for (ExplodedNodeSet::iterator NI
= PrevSet
->begin(), NE
= PrevSet
->end();
1950 // Use the 'state' argument only when the predecessor node is the
1951 // same as Pred. This allows us to catch updates to the state.
1952 checker
->GR_visitLocation(*CurrSet
, *Builder
, *this, S
, *NI
,
1953 *NI
== Pred
? state
: GetState(*NI
),
1954 location
, tag
, isLoad
);
1957 // Update which NodeSet is the current one.
1962 bool ExprEngine::InlineCall(ExplodedNodeSet
&Dst
, const CallExpr
*CE
,
1963 ExplodedNode
*Pred
) {
1964 const GRState
*state
= GetState(Pred
);
1965 const Expr
*Callee
= CE
->getCallee();
1966 SVal L
= state
->getSVal(Callee
);
1968 const FunctionDecl
*FD
= L
.getAsFunctionDecl();
1972 // Check if the function definition is in the same translation unit.
1973 if (FD
->hasBody(FD
)) {
1974 const StackFrameContext
*stackFrame
=
1975 AMgr
.getStackFrame(AMgr
.getAnalysisContext(FD
),
1976 Pred
->getLocationContext(),
1977 CE
, Builder
->getBlock(), Builder
->getIndex());
1978 // Now we have the definition of the callee, create a CallEnter node.
1979 CallEnter
Loc(CE
, stackFrame
, Pred
->getLocationContext());
1981 ExplodedNode
*N
= Builder
->generateNode(Loc
, state
, Pred
);
1986 // Check if we can find the function definition in other translation units.
1987 if (AMgr
.hasIndexer()) {
1988 AnalysisContext
*C
= AMgr
.getAnalysisContextInAnotherTU(FD
);
1991 const StackFrameContext
*stackFrame
=
1992 AMgr
.getStackFrame(C
, Pred
->getLocationContext(),
1993 CE
, Builder
->getBlock(), Builder
->getIndex());
1994 CallEnter
Loc(CE
, stackFrame
, Pred
->getLocationContext());
1995 ExplodedNode
*N
= Builder
->generateNode(Loc
, state
, Pred
);
2003 void ExprEngine::VisitCall(const CallExpr
* CE
, ExplodedNode
* Pred
,
2004 CallExpr::const_arg_iterator AI
,
2005 CallExpr::const_arg_iterator AE
,
2006 ExplodedNodeSet
& Dst
) {
2008 // Determine the type of function we're calling (if available).
2009 const FunctionProtoType
*Proto
= NULL
;
2010 QualType FnType
= CE
->getCallee()->IgnoreParens()->getType();
2011 if (const PointerType
*FnTypePtr
= FnType
->getAs
<PointerType
>())
2012 Proto
= FnTypePtr
->getPointeeType()->getAs
<FunctionProtoType
>();
2014 // Evaluate the arguments.
2015 ExplodedNodeSet ArgsEvaluated
;
2016 evalArguments(CE
->arg_begin(), CE
->arg_end(), Proto
, Pred
, ArgsEvaluated
);
2018 // Now process the call itself.
2019 ExplodedNodeSet DstTmp
;
2020 const Expr
* Callee
= CE
->getCallee()->IgnoreParens();
2022 for (ExplodedNodeSet::iterator NI
=ArgsEvaluated
.begin(),
2023 NE
=ArgsEvaluated
.end(); NI
!= NE
; ++NI
) {
2024 // Evaluate the callee.
2025 ExplodedNodeSet DstTmp2
;
2026 Visit(Callee
, *NI
, DstTmp2
);
2027 // Perform the previsit of the CallExpr, storing the results in DstTmp.
2028 CheckerVisit(CE
, DstTmp
, DstTmp2
, PreVisitStmtCallback
);
2031 // Finally, evaluate the function call. We try each of the checkers
2032 // to see if the can evaluate the function call.
2033 ExplodedNodeSet DstTmp3
;
2035 for (ExplodedNodeSet::iterator DI
= DstTmp
.begin(), DE
= DstTmp
.end();
2038 const GRState
* state
= GetState(*DI
);
2039 SVal L
= state
->getSVal(Callee
);
2041 // FIXME: Add support for symbolic function calls (calls involving
2042 // function pointer values that are symbolic).
2043 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
2044 ExplodedNodeSet DstChecker
;
2046 // If the callee is processed by a checker, skip the rest logic.
2047 if (CheckerEvalCall(CE
, DstChecker
, *DI
))
2048 DstTmp3
.insert(DstChecker
);
2049 else if (AMgr
.shouldInlineCall() && InlineCall(Dst
, CE
, *DI
)) {
2050 // Callee is inlined. We shouldn't do post call checking.
2054 for (ExplodedNodeSet::iterator DI_Checker
= DstChecker
.begin(),
2055 DE_Checker
= DstChecker
.end();
2056 DI_Checker
!= DE_Checker
; ++DI_Checker
) {
2058 // Dispatch to the plug-in transfer function.
2059 unsigned oldSize
= DstTmp3
.size();
2060 SaveOr
OldHasGen(Builder
->hasGeneratedNode
);
2063 // Dispatch to transfer function logic to handle the call itself.
2064 // FIXME: Allow us to chain together transfer functions.
2065 assert(Builder
&& "StmtNodeBuilder must be defined.");
2066 getTF().evalCall(DstTmp3
, *this, *Builder
, CE
, L
, Pred
);
2068 // Handle the case where no nodes where generated. Auto-generate that
2069 // contains the updated state if we aren't generating sinks.
2070 if (!Builder
->BuildSinks
&& DstTmp3
.size() == oldSize
&&
2071 !Builder
->hasGeneratedNode
)
2072 MakeNode(DstTmp3
, CE
, Pred
, state
);
2077 // Finally, perform the post-condition check of the CallExpr and store
2078 // the created nodes in 'Dst'.
2079 CheckerVisit(CE
, Dst
, DstTmp3
, PostVisitStmtCallback
);
2082 //===----------------------------------------------------------------------===//
2083 // Transfer function: Objective-C dot-syntax to access a property.
2084 //===----------------------------------------------------------------------===//
2086 void ExprEngine::VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr
*Ex
,
2088 ExplodedNodeSet
&Dst
) {
2089 ExplodedNodeSet dstBase
;
2091 // Visit the receiver (if any).
2092 if (Ex
->isObjectReceiver())
2093 Visit(Ex
->getBase(), Pred
, dstBase
);
2097 ExplodedNodeSet dstPropRef
;
2099 // Using the base, compute the lvalue of the instance variable.
2100 for (ExplodedNodeSet::iterator I
= dstBase
.begin(), E
= dstBase
.end();
2102 ExplodedNode
*nodeBase
= *I
;
2103 const GRState
*state
= GetState(nodeBase
);
2104 MakeNode(dstPropRef
, Ex
, *I
, state
->BindExpr(Ex
, loc::ObjCPropRef(Ex
)));
2107 Dst
.insert(dstPropRef
);
2110 //===----------------------------------------------------------------------===//
2111 // Transfer function: Objective-C ivar references.
2112 //===----------------------------------------------------------------------===//
2114 static std::pair
<const void*,const void*> EagerlyAssumeTag
2115 = std::pair
<const void*,const void*>(&EagerlyAssumeTag
,static_cast<void*>(0));
2117 void ExprEngine::evalEagerlyAssume(ExplodedNodeSet
&Dst
, ExplodedNodeSet
&Src
,
2119 for (ExplodedNodeSet::iterator I
=Src
.begin(), E
=Src
.end(); I
!=E
; ++I
) {
2120 ExplodedNode
*Pred
= *I
;
2122 // Test if the previous node was as the same expression. This can happen
2123 // when the expression fails to evaluate to anything meaningful and
2124 // (as an optimization) we don't generate a node.
2125 ProgramPoint P
= Pred
->getLocation();
2126 if (!isa
<PostStmt
>(P
) || cast
<PostStmt
>(P
).getStmt() != Ex
) {
2131 const GRState
* state
= GetState(Pred
);
2132 SVal V
= state
->getSVal(Ex
);
2133 if (nonloc::SymExprVal
*SEV
= dyn_cast
<nonloc::SymExprVal
>(&V
)) {
2134 // First assume that the condition is true.
2135 if (const GRState
*stateTrue
= state
->assume(*SEV
, true)) {
2136 stateTrue
= stateTrue
->BindExpr(Ex
,
2137 svalBuilder
.makeIntVal(1U, Ex
->getType()));
2138 Dst
.Add(Builder
->generateNode(PostStmtCustom(Ex
,
2139 &EagerlyAssumeTag
, Pred
->getLocationContext()),
2143 // Next, assume that the condition is false.
2144 if (const GRState
*stateFalse
= state
->assume(*SEV
, false)) {
2145 stateFalse
= stateFalse
->BindExpr(Ex
,
2146 svalBuilder
.makeIntVal(0U, Ex
->getType()));
2147 Dst
.Add(Builder
->generateNode(PostStmtCustom(Ex
, &EagerlyAssumeTag
,
2148 Pred
->getLocationContext()),
2157 //===----------------------------------------------------------------------===//
2158 // Transfer function: Objective-C @synchronized.
2159 //===----------------------------------------------------------------------===//
2161 void ExprEngine::VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt
*S
,
2163 ExplodedNodeSet
&Dst
) {
2165 // The mutex expression is a CFGElement, so we don't need to explicitly
2166 // visit it since it will already be processed.
2168 // Pre-visit the ObjCAtSynchronizedStmt.
2169 ExplodedNodeSet Tmp
;
2171 CheckerVisit(S
, Dst
, Tmp
, PreVisitStmtCallback
);
2174 //===----------------------------------------------------------------------===//
2175 // Transfer function: Objective-C ivar references.
2176 //===----------------------------------------------------------------------===//
2178 void ExprEngine::VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr
* Ex
,
2180 ExplodedNodeSet
& Dst
) {
2182 // Visit the base expression, which is needed for computing the lvalue
2184 ExplodedNodeSet dstBase
;
2185 const Expr
*baseExpr
= Ex
->getBase();
2186 Visit(baseExpr
, Pred
, dstBase
);
2188 ExplodedNodeSet dstIvar
;
2190 // Using the base, compute the lvalue of the instance variable.
2191 for (ExplodedNodeSet::iterator I
= dstBase
.begin(), E
= dstBase
.end();
2193 ExplodedNode
*nodeBase
= *I
;
2194 const GRState
*state
= GetState(nodeBase
);
2195 SVal baseVal
= state
->getSVal(baseExpr
);
2196 SVal location
= state
->getLValue(Ex
->getDecl(), baseVal
);
2197 MakeNode(dstIvar
, Ex
, *I
, state
->BindExpr(Ex
, location
));
2200 // Perform the post-condition check of the ObjCIvarRefExpr and store
2201 // the created nodes in 'Dst'.
2202 CheckerVisit(Ex
, Dst
, dstIvar
, PostVisitStmtCallback
);
2205 //===----------------------------------------------------------------------===//
2206 // Transfer function: Objective-C fast enumeration 'for' statements.
2207 //===----------------------------------------------------------------------===//
2209 void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt
* S
,
2210 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
) {
2212 // ObjCForCollectionStmts are processed in two places. This method
2213 // handles the case where an ObjCForCollectionStmt* occurs as one of the
2214 // statements within a basic block. This transfer function does two things:
2216 // (1) binds the next container value to 'element'. This creates a new
2217 // node in the ExplodedGraph.
2219 // (2) binds the value 0/1 to the ObjCForCollectionStmt* itself, indicating
2220 // whether or not the container has any more elements. This value
2221 // will be tested in ProcessBranch. We need to explicitly bind
2222 // this value because a container can contain nil elements.
2224 // FIXME: Eventually this logic should actually do dispatches to
2225 // 'countByEnumeratingWithState:objects:count:' (NSFastEnumeration).
2226 // This will require simulating a temporary NSFastEnumerationState, either
2227 // through an SVal or through the use of MemRegions. This value can
2228 // be affixed to the ObjCForCollectionStmt* instead of 0/1; when the loop
2229 // terminates we reclaim the temporary (it goes out of scope) and we
2230 // we can test if the SVal is 0 or if the MemRegion is null (depending
2231 // on what approach we take).
2233 // For now: simulate (1) by assigning either a symbol or nil if the
2234 // container is empty. Thus this transfer function will by default
2235 // result in state splitting.
2237 const Stmt
* elem
= S
->getElement();
2240 if (const DeclStmt
* DS
= dyn_cast
<DeclStmt
>(elem
)) {
2241 const VarDecl
* ElemD
= cast
<VarDecl
>(DS
->getSingleDecl());
2242 assert (ElemD
->getInit() == 0);
2243 ElementV
= GetState(Pred
)->getLValue(ElemD
, Pred
->getLocationContext());
2244 VisitObjCForCollectionStmtAux(S
, Pred
, Dst
, ElementV
);
2248 ExplodedNodeSet Tmp
;
2249 Visit(cast
<Expr
>(elem
), Pred
, Tmp
);
2250 for (ExplodedNodeSet::iterator I
= Tmp
.begin(), E
= Tmp
.end(); I
!=E
; ++I
) {
2251 const GRState
* state
= GetState(*I
);
2252 VisitObjCForCollectionStmtAux(S
, *I
, Dst
, state
->getSVal(elem
));
2256 void ExprEngine::VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt
* S
,
2257 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
,
2260 // Check if the location we are writing back to is a null pointer.
2261 const Stmt
* elem
= S
->getElement();
2262 ExplodedNodeSet Tmp
;
2263 evalLocation(Tmp
, elem
, Pred
, GetState(Pred
), ElementV
, NULL
, false);
2268 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(), NE
=Tmp
.end(); NI
!=NE
; ++NI
) {
2270 const GRState
*state
= GetState(Pred
);
2272 // Handle the case where the container still has elements.
2273 SVal TrueV
= svalBuilder
.makeTruthVal(1);
2274 const GRState
*hasElems
= state
->BindExpr(S
, TrueV
);
2276 // Handle the case where the container has no elements.
2277 SVal FalseV
= svalBuilder
.makeTruthVal(0);
2278 const GRState
*noElems
= state
->BindExpr(S
, FalseV
);
2280 if (loc::MemRegionVal
* MV
= dyn_cast
<loc::MemRegionVal
>(&ElementV
))
2281 if (const TypedRegion
* R
= dyn_cast
<TypedRegion
>(MV
->getRegion())) {
2282 // FIXME: The proper thing to do is to really iterate over the
2283 // container. We will do this with dispatch logic to the store.
2284 // For now, just 'conjure' up a symbolic value.
2285 QualType T
= R
->getValueType();
2286 assert(Loc::isLocType(T
));
2287 unsigned Count
= Builder
->getCurrentBlockCount();
2288 SymbolRef Sym
= SymMgr
.getConjuredSymbol(elem
, T
, Count
);
2289 SVal V
= svalBuilder
.makeLoc(Sym
);
2290 hasElems
= hasElems
->bindLoc(ElementV
, V
);
2292 // Bind the location to 'nil' on the false branch.
2293 SVal nilV
= svalBuilder
.makeIntVal(0, T
);
2294 noElems
= noElems
->bindLoc(ElementV
, nilV
);
2297 // Create the new nodes.
2298 MakeNode(Dst
, S
, Pred
, hasElems
);
2299 MakeNode(Dst
, S
, Pred
, noElems
);
2303 //===----------------------------------------------------------------------===//
2304 // Transfer function: Objective-C message expressions.
2305 //===----------------------------------------------------------------------===//
2308 class ObjCMsgWLItem
{
2310 ObjCMessageExpr::const_arg_iterator I
;
2313 ObjCMsgWLItem(const ObjCMessageExpr::const_arg_iterator
&i
, ExplodedNode
*n
)
2316 } // end anonymous namespace
2318 void ExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr
* ME
,
2320 ExplodedNodeSet
& Dst
){
2322 // Create a worklist to process both the arguments.
2323 llvm::SmallVector
<ObjCMsgWLItem
, 20> WL
;
2325 // But first evaluate the receiver (if any).
2326 ObjCMessageExpr::const_arg_iterator AI
= ME
->arg_begin(), AE
= ME
->arg_end();
2327 if (const Expr
*Receiver
= ME
->getInstanceReceiver()) {
2328 ExplodedNodeSet Tmp
;
2329 Visit(Receiver
, Pred
, Tmp
);
2334 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
)
2335 WL
.push_back(ObjCMsgWLItem(AI
, *I
));
2338 WL
.push_back(ObjCMsgWLItem(AI
, Pred
));
2340 // Evaluate the arguments.
2341 ExplodedNodeSet ArgsEvaluated
;
2342 while (!WL
.empty()) {
2343 ObjCMsgWLItem Item
= WL
.back();
2347 ArgsEvaluated
.insert(Item
.N
);
2351 // Evaluate the subexpression.
2352 ExplodedNodeSet Tmp
;
2354 // FIXME: [Objective-C++] handle arguments that are references
2355 Visit(*Item
.I
, Item
.N
, Tmp
);
2357 // Enqueue evaluating the next argument on the worklist.
2359 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(), NE
=Tmp
.end(); NI
!=NE
; ++NI
)
2360 WL
.push_back(ObjCMsgWLItem(Item
.I
, *NI
));
2363 // Now that the arguments are processed, handle the ObjC message.
2364 VisitObjCMessage(ME
, ArgsEvaluated
, Dst
);
2367 void ExprEngine::VisitObjCMessage(const ObjCMessage
&msg
,
2368 ExplodedNodeSet
&Src
, ExplodedNodeSet
& Dst
) {
2370 // Handle the previsits checks.
2371 ExplodedNodeSet DstPrevisit
;
2372 CheckerVisitObjCMessage(msg
, DstPrevisit
, Src
, /*isPreVisit=*/true);
2374 // Proceed with evaluate the message expression.
2375 ExplodedNodeSet dstEval
;
2377 for (ExplodedNodeSet::iterator DI
= DstPrevisit
.begin(),
2378 DE
= DstPrevisit
.end(); DI
!= DE
; ++DI
) {
2380 ExplodedNode
*Pred
= *DI
;
2381 bool RaisesException
= false;
2382 unsigned oldSize
= dstEval
.size();
2383 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
2384 SaveOr
OldHasGen(Builder
->hasGeneratedNode
);
2386 if (const Expr
*Receiver
= msg
.getInstanceReceiver()) {
2387 const GRState
*state
= GetState(Pred
);
2389 // Bifurcate the state into nil and non-nil ones.
2390 DefinedOrUnknownSVal receiverVal
=
2391 cast
<DefinedOrUnknownSVal
>(state
->getSVal(Receiver
));
2393 const GRState
*notNilState
, *nilState
;
2394 llvm::tie(notNilState
, nilState
) = state
->assume(receiverVal
);
2396 // There are three cases: can be nil or non-nil, must be nil, must be
2397 // non-nil. We handle must be nil, and merge the rest two into non-nil.
2398 if (nilState
&& !notNilState
) {
2399 CheckerEvalNilReceiver(msg
, dstEval
, nilState
, Pred
);
2403 // Check if the "raise" message was sent.
2404 assert(notNilState
);
2405 if (msg
.getSelector() == RaiseSel
)
2406 RaisesException
= true;
2408 // Check if we raise an exception. For now treat these as sinks.
2409 // Eventually we will want to handle exceptions properly.
2410 if (RaisesException
)
2411 Builder
->BuildSinks
= true;
2413 // Dispatch to plug-in transfer function.
2414 evalObjCMessage(dstEval
, msg
, Pred
, notNilState
);
2416 else if (const ObjCInterfaceDecl
*Iface
= msg
.getReceiverInterface()) {
2417 IdentifierInfo
* ClsName
= Iface
->getIdentifier();
2418 Selector S
= msg
.getSelector();
2420 // Check for special instance methods.
2421 if (!NSExceptionII
) {
2422 ASTContext
& Ctx
= getContext();
2423 NSExceptionII
= &Ctx
.Idents
.get("NSException");
2426 if (ClsName
== NSExceptionII
) {
2427 enum { NUM_RAISE_SELECTORS
= 2 };
2429 // Lazily create a cache of the selectors.
2430 if (!NSExceptionInstanceRaiseSelectors
) {
2431 ASTContext
& Ctx
= getContext();
2432 NSExceptionInstanceRaiseSelectors
=
2433 new Selector
[NUM_RAISE_SELECTORS
];
2434 llvm::SmallVector
<IdentifierInfo
*, NUM_RAISE_SELECTORS
> II
;
2438 II
.push_back(&Ctx
.Idents
.get("raise"));
2439 II
.push_back(&Ctx
.Idents
.get("format"));
2440 NSExceptionInstanceRaiseSelectors
[idx
++] =
2441 Ctx
.Selectors
.getSelector(II
.size(), &II
[0]);
2443 // raise:format::arguments:
2444 II
.push_back(&Ctx
.Idents
.get("arguments"));
2445 NSExceptionInstanceRaiseSelectors
[idx
++] =
2446 Ctx
.Selectors
.getSelector(II
.size(), &II
[0]);
2449 for (unsigned i
= 0; i
< NUM_RAISE_SELECTORS
; ++i
)
2450 if (S
== NSExceptionInstanceRaiseSelectors
[i
]) {
2451 RaisesException
= true;
2456 // Check if we raise an exception. For now treat these as sinks.
2457 // Eventually we will want to handle exceptions properly.
2458 if (RaisesException
)
2459 Builder
->BuildSinks
= true;
2461 // Dispatch to plug-in transfer function.
2462 evalObjCMessage(dstEval
, msg
, Pred
, Builder
->GetState(Pred
));
2465 // Handle the case where no nodes where generated. Auto-generate that
2466 // contains the updated state if we aren't generating sinks.
2467 if (!Builder
->BuildSinks
&& dstEval
.size() == oldSize
&&
2468 !Builder
->hasGeneratedNode
)
2469 MakeNode(dstEval
, msg
.getOriginExpr(), Pred
, GetState(Pred
));
2472 // Finally, perform the post-condition check of the ObjCMessageExpr and store
2473 // the created nodes in 'Dst'.
2474 CheckerVisitObjCMessage(msg
, Dst
, dstEval
, /*isPreVisit=*/false);
2477 //===----------------------------------------------------------------------===//
2478 // Transfer functions: Miscellaneous statements.
2479 //===----------------------------------------------------------------------===//
2481 void ExprEngine::VisitCast(const CastExpr
*CastE
, const Expr
*Ex
,
2482 ExplodedNode
*Pred
, ExplodedNodeSet
&Dst
) {
2485 Visit(Ex
, Pred
, S1
);
2487 CheckerVisit(CastE
, S2
, S1
, PreVisitStmtCallback
);
2489 if (CastE
->getCastKind() == CK_LValueToRValue
||
2490 CastE
->getCastKind() == CK_GetObjCProperty
) {
2491 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!=E
; ++I
) {
2492 ExplodedNode
*subExprNode
= *I
;
2493 const GRState
*state
= GetState(subExprNode
);
2494 evalLoad(Dst
, CastE
, subExprNode
, state
, state
->getSVal(Ex
));
2500 QualType T
= CastE
->getType();
2501 QualType ExTy
= Ex
->getType();
2503 if (const ExplicitCastExpr
*ExCast
=dyn_cast_or_null
<ExplicitCastExpr
>(CastE
))
2504 T
= ExCast
->getTypeAsWritten();
2507 // If we are evaluating the cast in an lvalue context, we implicitly want
2508 // the cast to evaluate to a location.
2510 ASTContext
&Ctx
= getContext();
2511 T
= Ctx
.getPointerType(Ctx
.getCanonicalType(T
));
2512 ExTy
= Ctx
.getPointerType(Ctx
.getCanonicalType(ExTy
));
2516 switch (CastE
->getCastKind()) {
2518 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!= E
; ++I
)
2522 case CK_LValueToRValue
:
2524 case CK_FunctionToPointerDecay
:
2525 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!= E
; ++I
) {
2526 // Copy the SVal of Ex to CastE.
2527 ExplodedNode
*N
= *I
;
2528 const GRState
*state
= GetState(N
);
2529 SVal V
= state
->getSVal(Ex
);
2530 state
= state
->BindExpr(CastE
, V
);
2531 MakeNode(Dst
, CastE
, N
, state
);
2535 case CK_GetObjCProperty
:
2537 case CK_ArrayToPointerDecay
:
2539 case CK_LValueBitCast
:
2540 case CK_IntegralCast
:
2541 case CK_NullToPointer
:
2542 case CK_IntegralToPointer
:
2543 case CK_PointerToIntegral
:
2544 case CK_PointerToBoolean
:
2545 case CK_IntegralToBoolean
:
2546 case CK_IntegralToFloating
:
2547 case CK_FloatingToIntegral
:
2548 case CK_FloatingToBoolean
:
2549 case CK_FloatingCast
:
2550 case CK_FloatingRealToComplex
:
2551 case CK_FloatingComplexToReal
:
2552 case CK_FloatingComplexToBoolean
:
2553 case CK_FloatingComplexCast
:
2554 case CK_FloatingComplexToIntegralComplex
:
2555 case CK_IntegralRealToComplex
:
2556 case CK_IntegralComplexToReal
:
2557 case CK_IntegralComplexToBoolean
:
2558 case CK_IntegralComplexCast
:
2559 case CK_IntegralComplexToFloatingComplex
:
2560 case CK_AnyPointerToObjCPointerCast
:
2561 case CK_AnyPointerToBlockPointerCast
:
2563 case CK_ObjCObjectLValueCast
: {
2564 // Delegate to SValBuilder to process.
2565 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!= E
; ++I
) {
2566 ExplodedNode
* N
= *I
;
2567 const GRState
* state
= GetState(N
);
2568 SVal V
= state
->getSVal(Ex
);
2569 V
= svalBuilder
.evalCast(V
, T
, ExTy
);
2570 state
= state
->BindExpr(CastE
, V
);
2571 MakeNode(Dst
, CastE
, N
, state
);
2576 case CK_DerivedToBase
:
2577 case CK_UncheckedDerivedToBase
:
2578 // For DerivedToBase cast, delegate to the store manager.
2579 for (ExplodedNodeSet::iterator I
= S2
.begin(), E
= S2
.end(); I
!= E
; ++I
) {
2580 ExplodedNode
*node
= *I
;
2581 const GRState
*state
= GetState(node
);
2582 SVal val
= state
->getSVal(Ex
);
2583 val
= getStoreManager().evalDerivedToBase(val
, T
);
2584 state
= state
->BindExpr(CastE
, val
);
2585 MakeNode(Dst
, CastE
, node
, state
);
2589 // Various C++ casts that are not handled yet.
2592 case CK_BaseToDerived
:
2593 case CK_NullToMemberPointer
:
2594 case CK_BaseToDerivedMemberPointer
:
2595 case CK_DerivedToBaseMemberPointer
:
2596 case CK_UserDefinedConversion
:
2597 case CK_ConstructorConversion
:
2598 case CK_VectorSplat
:
2599 case CK_MemberPointerToBoolean
: {
2600 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
2601 Builder
->BuildSinks
= true;
2602 MakeNode(Dst
, CastE
, Pred
, GetState(Pred
));
2608 void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr
* CL
,
2610 ExplodedNodeSet
& Dst
) {
2611 const InitListExpr
* ILE
2612 = cast
<InitListExpr
>(CL
->getInitializer()->IgnoreParens());
2613 ExplodedNodeSet Tmp
;
2614 Visit(ILE
, Pred
, Tmp
);
2616 for (ExplodedNodeSet::iterator I
= Tmp
.begin(), EI
= Tmp
.end(); I
!=EI
; ++I
) {
2617 const GRState
* state
= GetState(*I
);
2618 SVal ILV
= state
->getSVal(ILE
);
2619 const LocationContext
*LC
= (*I
)->getLocationContext();
2620 state
= state
->bindCompoundLiteral(CL
, LC
, ILV
);
2622 if (CL
->isLValue()) {
2623 MakeNode(Dst
, CL
, *I
, state
->BindExpr(CL
, state
->getLValue(CL
, LC
)));
2626 MakeNode(Dst
, CL
, *I
, state
->BindExpr(CL
, ILV
));
2630 void ExprEngine::VisitDeclStmt(const DeclStmt
*DS
, ExplodedNode
*Pred
,
2631 ExplodedNodeSet
& Dst
) {
2633 // The CFG has one DeclStmt per Decl.
2634 const Decl
* D
= *DS
->decl_begin();
2636 if (!D
|| !isa
<VarDecl
>(D
))
2639 const VarDecl
* VD
= dyn_cast
<VarDecl
>(D
);
2640 const Expr
* InitEx
= VD
->getInit();
2642 // FIXME: static variables may have an initializer, but the second
2643 // time a function is called those values may not be current.
2644 ExplodedNodeSet Tmp
;
2647 if (VD
->getType()->isReferenceType() && !InitEx
->isLValue()) {
2648 // If the initializer is C++ record type, it should already has a
2650 if (!InitEx
->getType()->isRecordType())
2651 CreateCXXTemporaryObject(InitEx
, Pred
, Tmp
);
2655 Visit(InitEx
, Pred
, Tmp
);
2659 ExplodedNodeSet Tmp2
;
2660 CheckerVisit(DS
, Tmp2
, Tmp
, PreVisitStmtCallback
);
2662 for (ExplodedNodeSet::iterator I
=Tmp2
.begin(), E
=Tmp2
.end(); I
!=E
; ++I
) {
2663 ExplodedNode
*N
= *I
;
2664 const GRState
*state
= GetState(N
);
2666 // Decls without InitExpr are not initialized explicitly.
2667 const LocationContext
*LC
= N
->getLocationContext();
2670 SVal InitVal
= state
->getSVal(InitEx
);
2672 // We bound the temp obj region to the CXXConstructExpr. Now recover
2673 // the lazy compound value when the variable is not a reference.
2674 if (AMgr
.getLangOptions().CPlusPlus
&& VD
->getType()->isRecordType() &&
2675 !VD
->getType()->isReferenceType() && isa
<loc::MemRegionVal
>(InitVal
)){
2676 InitVal
= state
->getSVal(cast
<loc::MemRegionVal
>(InitVal
).getRegion());
2677 assert(isa
<nonloc::LazyCompoundVal
>(InitVal
));
2680 // Recover some path-sensitivity if a scalar value evaluated to
2682 if ((InitVal
.isUnknown() ||
2683 !getConstraintManager().canReasonAbout(InitVal
)) &&
2684 !VD
->getType()->isReferenceType()) {
2685 InitVal
= svalBuilder
.getConjuredSymbolVal(NULL
, InitEx
,
2686 Builder
->getCurrentBlockCount());
2689 evalBind(Dst
, DS
, *I
, state
,
2690 loc::MemRegionVal(state
->getRegion(VD
, LC
)), InitVal
, true);
2693 state
= state
->bindDeclWithNoInit(state
->getRegion(VD
, LC
));
2694 MakeNode(Dst
, DS
, *I
, state
);
2699 void ExprEngine::VisitCondInit(const VarDecl
*VD
, const Stmt
*S
,
2700 ExplodedNode
*Pred
, ExplodedNodeSet
& Dst
) {
2702 const Expr
* InitEx
= VD
->getInit();
2703 ExplodedNodeSet Tmp
;
2704 Visit(InitEx
, Pred
, Tmp
);
2706 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2707 ExplodedNode
*N
= *I
;
2708 const GRState
*state
= GetState(N
);
2710 const LocationContext
*LC
= N
->getLocationContext();
2711 SVal InitVal
= state
->getSVal(InitEx
);
2713 // Recover some path-sensitivity if a scalar value evaluated to
2715 if (InitVal
.isUnknown() ||
2716 !getConstraintManager().canReasonAbout(InitVal
)) {
2717 InitVal
= svalBuilder
.getConjuredSymbolVal(NULL
, InitEx
,
2718 Builder
->getCurrentBlockCount());
2721 evalBind(Dst
, S
, N
, state
,
2722 loc::MemRegionVal(state
->getRegion(VD
, LC
)), InitVal
, true);
2727 // This class is used by VisitInitListExpr as an item in a worklist
2728 // for processing the values contained in an InitListExpr.
2729 class InitListWLItem
{
2731 llvm::ImmutableList
<SVal
> Vals
;
2733 InitListExpr::const_reverse_iterator Itr
;
2735 InitListWLItem(ExplodedNode
* n
, llvm::ImmutableList
<SVal
> vals
,
2736 InitListExpr::const_reverse_iterator itr
)
2737 : Vals(vals
), N(n
), Itr(itr
) {}
2742 void ExprEngine::VisitInitListExpr(const InitListExpr
* E
, ExplodedNode
* Pred
,
2743 ExplodedNodeSet
& Dst
) {
2745 const GRState
* state
= GetState(Pred
);
2746 QualType T
= getContext().getCanonicalType(E
->getType());
2747 unsigned NumInitElements
= E
->getNumInits();
2749 if (T
->isArrayType() || T
->isRecordType() || T
->isVectorType()) {
2750 llvm::ImmutableList
<SVal
> StartVals
= getBasicVals().getEmptySValList();
2752 // Handle base case where the initializer has no elements.
2753 // e.g: static int* myArray[] = {};
2754 if (NumInitElements
== 0) {
2755 SVal V
= svalBuilder
.makeCompoundVal(T
, StartVals
);
2756 MakeNode(Dst
, E
, Pred
, state
->BindExpr(E
, V
));
2760 // Create a worklist to process the initializers.
2761 llvm::SmallVector
<InitListWLItem
, 10> WorkList
;
2762 WorkList
.reserve(NumInitElements
);
2763 WorkList
.push_back(InitListWLItem(Pred
, StartVals
, E
->rbegin()));
2764 InitListExpr::const_reverse_iterator ItrEnd
= E
->rend();
2765 assert(!(E
->rbegin() == E
->rend()));
2767 // Process the worklist until it is empty.
2768 while (!WorkList
.empty()) {
2769 InitListWLItem X
= WorkList
.back();
2770 WorkList
.pop_back();
2772 ExplodedNodeSet Tmp
;
2773 Visit(*X
.Itr
, X
.N
, Tmp
);
2775 InitListExpr::const_reverse_iterator NewItr
= X
.Itr
+ 1;
2777 for (ExplodedNodeSet::iterator NI
=Tmp
.begin(),NE
=Tmp
.end();NI
!=NE
;++NI
) {
2778 // Get the last initializer value.
2779 state
= GetState(*NI
);
2780 SVal InitV
= state
->getSVal(cast
<Expr
>(*X
.Itr
));
2782 // Construct the new list of values by prepending the new value to
2783 // the already constructed list.
2784 llvm::ImmutableList
<SVal
> NewVals
=
2785 getBasicVals().consVals(InitV
, X
.Vals
);
2787 if (NewItr
== ItrEnd
) {
2788 // Now we have a list holding all init values. Make CompoundValData.
2789 SVal V
= svalBuilder
.makeCompoundVal(T
, NewVals
);
2791 // Make final state and node.
2792 MakeNode(Dst
, E
, *NI
, state
->BindExpr(E
, V
));
2795 // Still some initializer values to go. Push them onto the worklist.
2796 WorkList
.push_back(InitListWLItem(*NI
, NewVals
, NewItr
));
2804 if (Loc::isLocType(T
) || T
->isIntegerType()) {
2805 assert (E
->getNumInits() == 1);
2806 ExplodedNodeSet Tmp
;
2807 const Expr
* Init
= E
->getInit(0);
2808 Visit(Init
, Pred
, Tmp
);
2809 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), EI
=Tmp
.end(); I
!= EI
; ++I
) {
2810 state
= GetState(*I
);
2811 MakeNode(Dst
, E
, *I
, state
->BindExpr(E
, state
->getSVal(Init
)));
2816 assert(0 && "unprocessed InitListExpr type");
2819 /// VisitSizeOfAlignOfExpr - Transfer function for sizeof(type).
2820 void ExprEngine::VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr
* Ex
,
2822 ExplodedNodeSet
& Dst
) {
2823 QualType T
= Ex
->getTypeOfArgument();
2826 if (Ex
->isSizeOf()) {
2827 if (T
== getContext().VoidTy
) {
2828 // sizeof(void) == 1 byte.
2829 amt
= CharUnits::One();
2831 else if (!T
->isConstantSizeType()) {
2832 assert(T
->isVariableArrayType() && "Unknown non-constant-sized type.");
2834 // FIXME: Add support for VLA type arguments, not just VLA expressions.
2835 // When that happens, we should probably refactor VLASizeChecker's code.
2836 if (Ex
->isArgumentType()) {
2841 // Get the size by getting the extent of the sub-expression.
2842 // First, visit the sub-expression to find its region.
2843 const Expr
*Arg
= Ex
->getArgumentExpr();
2844 ExplodedNodeSet Tmp
;
2845 Visit(Arg
, Pred
, Tmp
);
2847 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2848 const GRState
* state
= GetState(*I
);
2849 const MemRegion
*MR
= state
->getSVal(Arg
).getAsRegion();
2851 // If the subexpression can't be resolved to a region, we don't know
2852 // anything about its size. Just leave the state as is and continue.
2858 // The result is the extent of the VLA.
2859 SVal Extent
= cast
<SubRegion
>(MR
)->getExtent(svalBuilder
);
2860 MakeNode(Dst
, Ex
, *I
, state
->BindExpr(Ex
, Extent
));
2865 else if (T
->getAs
<ObjCObjectType
>()) {
2866 // Some code tries to take the sizeof an ObjCObjectType, relying that
2867 // the compiler has laid out its representation. Just report Unknown
2874 amt
= getContext().getTypeSizeInChars(T
);
2877 else // Get alignment of the type.
2878 amt
= getContext().getTypeAlignInChars(T
);
2880 MakeNode(Dst
, Ex
, Pred
,
2881 GetState(Pred
)->BindExpr(Ex
,
2882 svalBuilder
.makeIntVal(amt
.getQuantity(), Ex
->getType())));
2885 void ExprEngine::VisitOffsetOfExpr(const OffsetOfExpr
* OOE
,
2886 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
) {
2887 Expr::EvalResult Res
;
2888 if (OOE
->Evaluate(Res
, getContext()) && Res
.Val
.isInt()) {
2889 const APSInt
&IV
= Res
.Val
.getInt();
2890 assert(IV
.getBitWidth() == getContext().getTypeSize(OOE
->getType()));
2891 assert(OOE
->getType()->isIntegerType());
2892 assert(IV
.isSigned() == OOE
->getType()->isSignedIntegerType());
2893 SVal X
= svalBuilder
.makeIntVal(IV
);
2894 MakeNode(Dst
, OOE
, Pred
, GetState(Pred
)->BindExpr(OOE
, X
));
2897 // FIXME: Handle the case where __builtin_offsetof is not a constant.
2901 void ExprEngine::VisitUnaryOperator(const UnaryOperator
* U
,
2903 ExplodedNodeSet
& Dst
) {
2905 switch (U
->getOpcode()) {
2911 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
2912 ExplodedNodeSet Tmp
;
2913 Visit(Ex
, Pred
, Tmp
);
2915 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2917 // FIXME: We don't have complex SValues yet.
2918 if (Ex
->getType()->isAnyComplexType()) {
2919 // Just report "Unknown."
2924 // For all other types, UO_Real is an identity operation.
2925 assert (U
->getType() == Ex
->getType());
2926 const GRState
* state
= GetState(*I
);
2927 MakeNode(Dst
, U
, *I
, state
->BindExpr(U
, state
->getSVal(Ex
)));
2935 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
2936 ExplodedNodeSet Tmp
;
2937 Visit(Ex
, Pred
, Tmp
);
2939 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2940 // FIXME: We don't have complex SValues yet.
2941 if (Ex
->getType()->isAnyComplexType()) {
2942 // Just report "Unknown."
2947 // For all other types, UO_Imag returns 0.
2948 const GRState
* state
= GetState(*I
);
2949 SVal X
= svalBuilder
.makeZeroVal(Ex
->getType());
2950 MakeNode(Dst
, U
, *I
, state
->BindExpr(U
, X
));
2957 assert(!U
->isLValue());
2961 case UO_Extension
: {
2963 // Unary "+" is a no-op, similar to a parentheses. We still have places
2964 // where it may be a block-level expression, so we need to
2965 // generate an extra node that just propagates the value of the
2968 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
2969 ExplodedNodeSet Tmp
;
2970 Visit(Ex
, Pred
, Tmp
);
2972 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2973 const GRState
* state
= GetState(*I
);
2974 MakeNode(Dst
, U
, *I
, state
->BindExpr(U
, state
->getSVal(Ex
)));
2983 assert (!U
->isLValue());
2984 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
2985 ExplodedNodeSet Tmp
;
2986 Visit(Ex
, Pred
, Tmp
);
2988 for (ExplodedNodeSet::iterator I
=Tmp
.begin(), E
=Tmp
.end(); I
!=E
; ++I
) {
2989 const GRState
* state
= GetState(*I
);
2991 // Get the value of the subexpression.
2992 SVal V
= state
->getSVal(Ex
);
2994 if (V
.isUnknownOrUndef()) {
2995 MakeNode(Dst
, U
, *I
, state
->BindExpr(U
, V
));
2999 // QualType DstT = getContext().getCanonicalType(U->getType());
3000 // QualType SrcT = getContext().getCanonicalType(Ex->getType());
3002 // if (DstT != SrcT) // Perform promotions.
3003 // V = evalCast(V, DstT);
3005 // if (V.isUnknownOrUndef()) {
3006 // MakeNode(Dst, U, *I, BindExpr(St, U, V));
3010 switch (U
->getOpcode()) {
3012 assert(false && "Invalid Opcode.");
3016 // FIXME: Do we need to handle promotions?
3017 state
= state
->BindExpr(U
, evalComplement(cast
<NonLoc
>(V
)));
3021 // FIXME: Do we need to handle promotions?
3022 state
= state
->BindExpr(U
, evalMinus(cast
<NonLoc
>(V
)));
3027 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
3029 // Note: technically we do "E == 0", but this is the same in the
3030 // transfer functions as "0 == E".
3034 Loc X
= svalBuilder
.makeNull();
3035 Result
= evalBinOp(state
, BO_EQ
, cast
<Loc
>(V
), X
,
3039 nonloc::ConcreteInt
X(getBasicVals().getValue(0, Ex
->getType()));
3040 Result
= evalBinOp(state
, BO_EQ
, cast
<NonLoc
>(V
), X
,
3044 state
= state
->BindExpr(U
, Result
);
3049 MakeNode(Dst
, U
, *I
, state
);
3056 // Handle ++ and -- (both pre- and post-increment).
3057 assert (U
->isIncrementDecrementOp());
3058 ExplodedNodeSet Tmp
;
3059 const Expr
* Ex
= U
->getSubExpr()->IgnoreParens();
3060 Visit(Ex
, Pred
, Tmp
);
3062 for (ExplodedNodeSet::iterator I
= Tmp
.begin(), E
= Tmp
.end(); I
!=E
; ++I
) {
3064 const GRState
* state
= GetState(*I
);
3065 SVal loc
= state
->getSVal(Ex
);
3068 ExplodedNodeSet Tmp2
;
3069 evalLoad(Tmp2
, Ex
, *I
, state
, loc
);
3071 for (ExplodedNodeSet::iterator I2
=Tmp2
.begin(), E2
=Tmp2
.end();I2
!=E2
;++I2
) {
3073 state
= GetState(*I2
);
3074 SVal V2_untested
= state
->getSVal(Ex
);
3076 // Propagate unknown and undefined values.
3077 if (V2_untested
.isUnknownOrUndef()) {
3078 MakeNode(Dst
, U
, *I2
, state
->BindExpr(U
, V2_untested
));
3081 DefinedSVal V2
= cast
<DefinedSVal
>(V2_untested
);
3083 // Handle all other values.
3084 BinaryOperator::Opcode Op
= U
->isIncrementOp() ? BO_Add
3087 // If the UnaryOperator has non-location type, use its type to create the
3088 // constant value. If the UnaryOperator has location type, create the
3089 // constant with int type and pointer width.
3092 if (U
->getType()->isAnyPointerType())
3093 RHS
= svalBuilder
.makeArrayIndex(1);
3095 RHS
= svalBuilder
.makeIntVal(1, U
->getType());
3097 SVal Result
= evalBinOp(state
, Op
, V2
, RHS
, U
->getType());
3099 // Conjure a new symbol if necessary to recover precision.
3100 if (Result
.isUnknown() || !getConstraintManager().canReasonAbout(Result
)){
3101 DefinedOrUnknownSVal SymVal
=
3102 svalBuilder
.getConjuredSymbolVal(NULL
, Ex
,
3103 Builder
->getCurrentBlockCount());
3106 // If the value is a location, ++/-- should always preserve
3107 // non-nullness. Check if the original value was non-null, and if so
3108 // propagate that constraint.
3109 if (Loc::isLocType(U
->getType())) {
3110 DefinedOrUnknownSVal Constraint
=
3111 svalBuilder
.evalEQ(state
, V2
,svalBuilder
.makeZeroVal(U
->getType()));
3113 if (!state
->assume(Constraint
, true)) {
3114 // It isn't feasible for the original value to be null.
3115 // Propagate this constraint.
3116 Constraint
= svalBuilder
.evalEQ(state
, SymVal
,
3117 svalBuilder
.makeZeroVal(U
->getType()));
3120 state
= state
->assume(Constraint
, false);
3126 // Since the lvalue-to-rvalue conversion is explicit in the AST,
3127 // we bind an l-value if the operator is prefix and an lvalue (in C++).
3129 state
= state
->BindExpr(U
, loc
);
3131 state
= state
->BindExpr(U
, V2
);
3133 // Perform the store.
3134 evalStore(Dst
, NULL
, U
, *I2
, state
, loc
, Result
);
3139 void ExprEngine::VisitAsmStmt(const AsmStmt
* A
, ExplodedNode
* Pred
,
3140 ExplodedNodeSet
& Dst
) {
3141 VisitAsmStmtHelperOutputs(A
, A
->begin_outputs(), A
->end_outputs(), Pred
, Dst
);
3144 void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt
* A
,
3145 AsmStmt::const_outputs_iterator I
,
3146 AsmStmt::const_outputs_iterator E
,
3147 ExplodedNode
* Pred
, ExplodedNodeSet
& Dst
) {
3149 VisitAsmStmtHelperInputs(A
, A
->begin_inputs(), A
->end_inputs(), Pred
, Dst
);
3153 ExplodedNodeSet Tmp
;
3154 Visit(*I
, Pred
, Tmp
);
3157 for (ExplodedNodeSet::iterator NI
= Tmp
.begin(), NE
= Tmp
.end();NI
!= NE
;++NI
)
3158 VisitAsmStmtHelperOutputs(A
, I
, E
, *NI
, Dst
);
3161 void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt
* A
,
3162 AsmStmt::const_inputs_iterator I
,
3163 AsmStmt::const_inputs_iterator E
,
3165 ExplodedNodeSet
& Dst
) {
3168 // We have processed both the inputs and the outputs. All of the outputs
3169 // should evaluate to Locs. Nuke all of their values.
3171 // FIXME: Some day in the future it would be nice to allow a "plug-in"
3172 // which interprets the inline asm and stores proper results in the
3175 const GRState
* state
= GetState(Pred
);
3177 for (AsmStmt::const_outputs_iterator OI
= A
->begin_outputs(),
3178 OE
= A
->end_outputs(); OI
!= OE
; ++OI
) {
3180 SVal X
= state
->getSVal(*OI
);
3181 assert (!isa
<NonLoc
>(X
)); // Should be an Lval, or unknown, undef.
3184 state
= state
->bindLoc(cast
<Loc
>(X
), UnknownVal());
3187 MakeNode(Dst
, A
, Pred
, state
);
3191 ExplodedNodeSet Tmp
;
3192 Visit(*I
, Pred
, Tmp
);
3196 for (ExplodedNodeSet::iterator NI
= Tmp
.begin(), NE
= Tmp
.end(); NI
!=NE
; ++NI
)
3197 VisitAsmStmtHelperInputs(A
, I
, E
, *NI
, Dst
);
3200 void ExprEngine::VisitReturnStmt(const ReturnStmt
*RS
, ExplodedNode
*Pred
,
3201 ExplodedNodeSet
&Dst
) {
3202 ExplodedNodeSet Src
;
3203 if (const Expr
*RetE
= RS
->getRetValue()) {
3204 // Record the returned expression in the state. It will be used in
3205 // processCallExit to bind the return value to the call expr.
3208 const GRState
*state
= GetState(Pred
);
3209 state
= state
->set
<ReturnExpr
>(RetE
);
3210 Pred
= Builder
->generateNode(RetE
, state
, Pred
, &tag
);
3212 // We may get a NULL Pred because we generated a cached node.
3214 Visit(RetE
, Pred
, Src
);
3220 ExplodedNodeSet CheckedSet
;
3221 CheckerVisit(RS
, CheckedSet
, Src
, PreVisitStmtCallback
);
3223 for (ExplodedNodeSet::iterator I
= CheckedSet
.begin(), E
= CheckedSet
.end();
3226 assert(Builder
&& "StmtNodeBuilder must be defined.");
3229 unsigned size
= Dst
.size();
3231 SaveAndRestore
<bool> OldSink(Builder
->BuildSinks
);
3232 SaveOr
OldHasGen(Builder
->hasGeneratedNode
);
3234 getTF().evalReturn(Dst
, *this, *Builder
, RS
, Pred
);
3236 // Handle the case where no nodes where generated.
3237 if (!Builder
->BuildSinks
&& Dst
.size() == size
&&
3238 !Builder
->hasGeneratedNode
)
3239 MakeNode(Dst
, RS
, Pred
, GetState(Pred
));
3243 //===----------------------------------------------------------------------===//
3244 // Transfer functions: Binary operators.
3245 //===----------------------------------------------------------------------===//
3247 void ExprEngine::VisitBinaryOperator(const BinaryOperator
* B
,
3249 ExplodedNodeSet
& Dst
) {
3250 ExplodedNodeSet Tmp1
;
3251 Expr
* LHS
= B
->getLHS()->IgnoreParens();
3252 Expr
* RHS
= B
->getRHS()->IgnoreParens();
3254 Visit(LHS
, Pred
, Tmp1
);
3255 ExplodedNodeSet Tmp3
;
3257 for (ExplodedNodeSet::iterator I1
=Tmp1
.begin(), E1
=Tmp1
.end(); I1
!=E1
; ++I1
) {
3258 SVal LeftV
= GetState(*I1
)->getSVal(LHS
);
3259 ExplodedNodeSet Tmp2
;
3260 Visit(RHS
, *I1
, Tmp2
);
3262 ExplodedNodeSet CheckedSet
;
3263 CheckerVisit(B
, CheckedSet
, Tmp2
, PreVisitStmtCallback
);
3265 // With both the LHS and RHS evaluated, process the operation itself.
3267 for (ExplodedNodeSet::iterator I2
=CheckedSet
.begin(), E2
=CheckedSet
.end();
3270 const GRState
*state
= GetState(*I2
);
3271 SVal RightV
= state
->getSVal(RHS
);
3273 BinaryOperator::Opcode Op
= B
->getOpcode();
3275 if (Op
== BO_Assign
) {
3276 // EXPERIMENTAL: "Conjured" symbols.
3277 // FIXME: Handle structs.
3278 if (RightV
.isUnknown() ||!getConstraintManager().canReasonAbout(RightV
))
3280 unsigned Count
= Builder
->getCurrentBlockCount();
3281 RightV
= svalBuilder
.getConjuredSymbolVal(NULL
, B
->getRHS(), Count
);
3284 SVal ExprVal
= B
->isLValue() ? LeftV
: RightV
;
3286 // Simulate the effects of a "store": bind the value of the RHS
3287 // to the L-Value represented by the LHS.
3288 evalStore(Tmp3
, B
, LHS
, *I2
, state
->BindExpr(B
, ExprVal
), LeftV
,RightV
);
3292 if (!B
->isAssignmentOp()) {
3293 // Process non-assignments except commas or short-circuited
3294 // logical expressions (LAnd and LOr).
3295 SVal Result
= evalBinOp(state
, Op
, LeftV
, RightV
, B
->getType());
3297 if (Result
.isUnknown()) {
3298 MakeNode(Tmp3
, B
, *I2
, state
);
3302 state
= state
->BindExpr(B
, Result
);
3304 MakeNode(Tmp3
, B
, *I2
, state
);
3308 assert (B
->isCompoundAssignmentOp());
3312 assert(0 && "Invalid opcode for compound assignment.");
3313 case BO_MulAssign
: Op
= BO_Mul
; break;
3314 case BO_DivAssign
: Op
= BO_Div
; break;
3315 case BO_RemAssign
: Op
= BO_Rem
; break;
3316 case BO_AddAssign
: Op
= BO_Add
; break;
3317 case BO_SubAssign
: Op
= BO_Sub
; break;
3318 case BO_ShlAssign
: Op
= BO_Shl
; break;
3319 case BO_ShrAssign
: Op
= BO_Shr
; break;
3320 case BO_AndAssign
: Op
= BO_And
; break;
3321 case BO_XorAssign
: Op
= BO_Xor
; break;
3322 case BO_OrAssign
: Op
= BO_Or
; break;
3325 // Perform a load (the LHS). This performs the checks for
3326 // null dereferences, and so on.
3327 ExplodedNodeSet Tmp4
;
3328 SVal location
= state
->getSVal(LHS
);
3329 evalLoad(Tmp4
, LHS
, *I2
, state
, location
);
3331 for (ExplodedNodeSet::iterator I4
=Tmp4
.begin(), E4
=Tmp4
.end(); I4
!=E4
;
3333 state
= GetState(*I4
);
3334 SVal V
= state
->getSVal(LHS
);
3336 // Get the computation type.
3338 cast
<CompoundAssignOperator
>(B
)->getComputationResultType();
3339 CTy
= getContext().getCanonicalType(CTy
);
3342 cast
<CompoundAssignOperator
>(B
)->getComputationLHSType();
3343 CLHSTy
= getContext().getCanonicalType(CLHSTy
);
3345 QualType LTy
= getContext().getCanonicalType(LHS
->getType());
3348 V
= svalBuilder
.evalCast(V
, CLHSTy
, LTy
);
3350 // Compute the result of the operation.
3351 SVal Result
= svalBuilder
.evalCast(evalBinOp(state
, Op
, V
, RightV
, CTy
),
3354 // EXPERIMENTAL: "Conjured" symbols.
3355 // FIXME: Handle structs.
3359 if (Result
.isUnknown() ||
3360 !getConstraintManager().canReasonAbout(Result
)) {
3362 unsigned Count
= Builder
->getCurrentBlockCount();
3364 // The symbolic value is actually for the type of the left-hand side
3365 // expression, not the computation type, as this is the value the
3366 // LValue on the LHS will bind to.
3367 LHSVal
= svalBuilder
.getConjuredSymbolVal(NULL
, B
->getRHS(), LTy
, Count
);
3369 // However, we need to convert the symbol to the computation type.
3370 Result
= svalBuilder
.evalCast(LHSVal
, CTy
, LTy
);
3373 // The left-hand side may bind to a different value then the
3374 // computation type.
3375 LHSVal
= svalBuilder
.evalCast(Result
, LTy
, CTy
);
3378 // In C++, assignment and compound assignment operators return an
3381 state
= state
->BindExpr(B
, location
);
3383 state
= state
->BindExpr(B
, Result
);
3385 evalStore(Tmp3
, B
, LHS
, *I4
, state
, location
, LHSVal
);
3390 CheckerVisit(B
, Dst
, Tmp3
, PostVisitStmtCallback
);
3393 //===----------------------------------------------------------------------===//
3394 // Checker registration/lookup.
3395 //===----------------------------------------------------------------------===//
3397 Checker
*ExprEngine::lookupChecker(void *tag
) const {
3398 CheckerMap::const_iterator I
= CheckerM
.find(tag
);
3399 return (I
== CheckerM
.end()) ? NULL
: Checkers
[I
->second
].second
;
3402 //===----------------------------------------------------------------------===//
3404 //===----------------------------------------------------------------------===//
3407 static ExprEngine
* GraphPrintCheckerState
;
3408 static SourceManager
* GraphPrintSourceManager
;
3412 struct DOTGraphTraits
<ExplodedNode
*> :
3413 public DefaultDOTGraphTraits
{
3415 DOTGraphTraits (bool isSimple
=false) : DefaultDOTGraphTraits(isSimple
) {}
3417 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
3419 static std::string
getNodeAttributes(const ExplodedNode
* N
, void*) {
3422 // FIXME: Replace with a general scheme to tell if the node is
3424 if (GraphPrintCheckerState
->isImplicitNullDeref(N
) ||
3425 GraphPrintCheckerState
->isExplicitNullDeref(N
) ||
3426 GraphPrintCheckerState
->isUndefDeref(N
) ||
3427 GraphPrintCheckerState
->isUndefStore(N
) ||
3428 GraphPrintCheckerState
->isUndefControlFlow(N
) ||
3429 GraphPrintCheckerState
->isUndefResult(N
) ||
3430 GraphPrintCheckerState
->isBadCall(N
) ||
3431 GraphPrintCheckerState
->isUndefArg(N
))
3432 return "color=\"red\",style=\"filled\"";
3434 if (GraphPrintCheckerState
->isNoReturnCall(N
))
3435 return "color=\"blue\",style=\"filled\"";
3440 static std::string
getNodeLabel(const ExplodedNode
* N
, void*){
3443 llvm::raw_string_ostream
Out(sbuf
);
3445 // Program Location.
3446 ProgramPoint Loc
= N
->getLocation();
3448 switch (Loc
.getKind()) {
3449 case ProgramPoint::BlockEntranceKind
:
3450 Out
<< "Block Entrance: B"
3451 << cast
<BlockEntrance
>(Loc
).getBlock()->getBlockID();
3454 case ProgramPoint::BlockExitKind
:
3458 case ProgramPoint::CallEnterKind
:
3462 case ProgramPoint::CallExitKind
:
3467 if (StmtPoint
*L
= dyn_cast
<StmtPoint
>(&Loc
)) {
3468 const Stmt
* S
= L
->getStmt();
3469 SourceLocation SLoc
= S
->getLocStart();
3471 Out
<< S
->getStmtClassName() << ' ' << (void*) S
<< ' ';
3472 LangOptions LO
; // FIXME.
3473 S
->printPretty(Out
, 0, PrintingPolicy(LO
));
3475 if (SLoc
.isFileID()) {
3477 << GraphPrintSourceManager
->getInstantiationLineNumber(SLoc
)
3479 << GraphPrintSourceManager
->getInstantiationColumnNumber(SLoc
)
3483 if (isa
<PreStmt
>(Loc
))
3484 Out
<< "\\lPreStmt\\l;";
3485 else if (isa
<PostLoad
>(Loc
))
3486 Out
<< "\\lPostLoad\\l;";
3487 else if (isa
<PostStore
>(Loc
))
3488 Out
<< "\\lPostStore\\l";
3489 else if (isa
<PostLValue
>(Loc
))
3490 Out
<< "\\lPostLValue\\l";
3493 // FIXME: Replace with a general scheme to determine
3494 // the name of the check.
3495 if (GraphPrintCheckerState
->isImplicitNullDeref(N
))
3496 Out
<< "\\|Implicit-Null Dereference.\\l";
3497 else if (GraphPrintCheckerState
->isExplicitNullDeref(N
))
3498 Out
<< "\\|Explicit-Null Dereference.\\l";
3499 else if (GraphPrintCheckerState
->isUndefDeref(N
))
3500 Out
<< "\\|Dereference of undefialied value.\\l";
3501 else if (GraphPrintCheckerState
->isUndefStore(N
))
3502 Out
<< "\\|Store to Undefined Loc.";
3503 else if (GraphPrintCheckerState
->isUndefResult(N
))
3504 Out
<< "\\|Result of operation is undefined.";
3505 else if (GraphPrintCheckerState
->isNoReturnCall(N
))
3506 Out
<< "\\|Call to function marked \"noreturn\".";
3507 else if (GraphPrintCheckerState
->isBadCall(N
))
3508 Out
<< "\\|Call to NULL/Undefined.";
3509 else if (GraphPrintCheckerState
->isUndefArg(N
))
3510 Out
<< "\\|Argument in call is undefined";
3516 const BlockEdge
& E
= cast
<BlockEdge
>(Loc
);
3517 Out
<< "Edge: (B" << E
.getSrc()->getBlockID() << ", B"
3518 << E
.getDst()->getBlockID() << ')';
3520 if (const Stmt
* T
= E
.getSrc()->getTerminator()) {
3522 SourceLocation SLoc
= T
->getLocStart();
3524 Out
<< "\\|Terminator: ";
3525 LangOptions LO
; // FIXME.
3526 E
.getSrc()->printTerminator(Out
, LO
);
3528 if (SLoc
.isFileID()) {
3530 << GraphPrintSourceManager
->getInstantiationLineNumber(SLoc
)
3532 << GraphPrintSourceManager
->getInstantiationColumnNumber(SLoc
);
3535 if (isa
<SwitchStmt
>(T
)) {
3536 const Stmt
* Label
= E
.getDst()->getLabel();
3539 if (const CaseStmt
* C
= dyn_cast
<CaseStmt
>(Label
)) {
3541 LangOptions LO
; // FIXME.
3542 C
->getLHS()->printPretty(Out
, 0, PrintingPolicy(LO
));
3544 if (const Stmt
* RHS
= C
->getRHS()) {
3546 RHS
->printPretty(Out
, 0, PrintingPolicy(LO
));
3552 assert (isa
<DefaultStmt
>(Label
));
3553 Out
<< "\\ldefault:";
3557 Out
<< "\\l(implicit) default:";
3559 else if (isa
<IndirectGotoStmt
>(T
)) {
3563 Out
<< "\\lCondition: ";
3564 if (*E
.getSrc()->succ_begin() == E
.getDst())
3574 // FIXME: Replace with a general scheme to determine
3575 // the name of the check.
3576 if (GraphPrintCheckerState
->isUndefControlFlow(N
)) {
3577 Out
<< "\\|Control-flow based on\\lUndefined value.\\l";
3583 const GRState
*state
= N
->getState();
3584 Out
<< "\\|StateID: " << (void*) state
3585 << " NodeID: " << (void*) N
<< "\\|";
3586 state
->printDOT(Out
, *N
->getLocationContext()->getCFG());
3591 } // end llvm namespace
3595 template <typename ITERATOR
>
3596 ExplodedNode
* GetGraphNode(ITERATOR I
) { return *I
; }
3598 template <> ExplodedNode
*
3599 GetGraphNode
<llvm::DenseMap
<ExplodedNode
*, Expr
*>::iterator
>
3600 (llvm::DenseMap
<ExplodedNode
*, Expr
*>::iterator I
) {
3605 void ExprEngine::ViewGraph(bool trim
) {
3608 std::vector
<ExplodedNode
*> Src
;
3610 // Flush any outstanding reports to make sure we cover all the nodes.
3611 // This does not cause them to get displayed.
3612 for (BugReporter::iterator I
=BR
.begin(), E
=BR
.end(); I
!=E
; ++I
)
3613 const_cast<BugType
*>(*I
)->FlushReports(BR
);
3615 // Iterate through the reports and get their nodes.
3616 for (BugReporter::iterator I
=BR
.begin(), E
=BR
.end(); I
!=E
; ++I
) {
3617 for (BugType::const_iterator I2
=(*I
)->begin(), E2
=(*I
)->end();
3619 const BugReportEquivClass
& EQ
= *I2
;
3620 const BugReport
&R
= **EQ
.begin();
3621 ExplodedNode
*N
= const_cast<ExplodedNode
*>(R
.getErrorNode());
3622 if (N
) Src
.push_back(N
);
3626 ViewGraph(&Src
[0], &Src
[0]+Src
.size());
3629 GraphPrintCheckerState
= this;
3630 GraphPrintSourceManager
= &getContext().getSourceManager();
3632 llvm::ViewGraph(*G
.roots_begin(), "ExprEngine");
3634 GraphPrintCheckerState
= NULL
;
3635 GraphPrintSourceManager
= NULL
;
3640 void ExprEngine::ViewGraph(ExplodedNode
** Beg
, ExplodedNode
** End
) {
3642 GraphPrintCheckerState
= this;
3643 GraphPrintSourceManager
= &getContext().getSourceManager();
3645 std::auto_ptr
<ExplodedGraph
> TrimmedG(G
.Trim(Beg
, End
).first
);
3647 if (!TrimmedG
.get())
3648 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
3650 llvm::ViewGraph(*TrimmedG
->roots_begin(), "TrimmedExprEngine");
3652 GraphPrintCheckerState
= NULL
;
3653 GraphPrintSourceManager
= NULL
;