diff options
Diffstat (limited to 'lib/StaticAnalyzer/Core/ExprEngine.cpp')
| -rw-r--r-- | lib/StaticAnalyzer/Core/ExprEngine.cpp | 3232 |
1 files changed, 3232 insertions, 0 deletions
diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp new file mode 100644 index 0000000000..cb777aec6d --- /dev/null +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -0,0 +1,3232 @@ +//=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-= +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a meta-engine for path-sensitive dataflow analysis that +// is built on GREngine, but provides the boilerplate to execute transfer +// functions and build the ExplodedGraph at the expression level. +// +//===----------------------------------------------------------------------===// + +#include "clang/StaticAnalyzer/Core/CheckerManager.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h" +#include "clang/AST/CharUnits.h" +#include "clang/AST/ParentMap.h" +#include "clang/AST/StmtObjC.h" +#include "clang/AST/DeclCXX.h" +#include "clang/Basic/Builtins.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Basic/PrettyStackTrace.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/ADT/ImmutableList.h" + +#ifndef NDEBUG +#include "llvm/Support/GraphWriter.h" +#endif + +using namespace clang; +using namespace ento; +using llvm::dyn_cast; +using llvm::dyn_cast_or_null; +using llvm::cast; +using llvm::APSInt; + +namespace { + // Trait class for recording returned expression in the state. + struct ReturnExpr { + static int TagInt; + typedef const Stmt *data_type; + }; + int ReturnExpr::TagInt; +} + +//===----------------------------------------------------------------------===// +// Utility functions. +//===----------------------------------------------------------------------===// + +static inline Selector GetNullarySelector(const char* name, ASTContext& Ctx) { + IdentifierInfo* II = &Ctx.Idents.get(name); + return Ctx.Selectors.getSelector(0, &II); +} + +//===----------------------------------------------------------------------===// +// Engine construction and deletion. +//===----------------------------------------------------------------------===// + +ExprEngine::ExprEngine(AnalysisManager &mgr, TransferFuncs *tf) + : AMgr(mgr), + Engine(*this), + G(Engine.getGraph()), + Builder(NULL), + StateMgr(getContext(), mgr.getStoreManagerCreator(), + mgr.getConstraintManagerCreator(), G.getAllocator(), + *this), + SymMgr(StateMgr.getSymbolManager()), + svalBuilder(StateMgr.getSValBuilder()), + EntryNode(NULL), currentStmt(NULL), + NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL), + RaiseSel(GetNullarySelector("raise", getContext())), + BR(mgr, *this), TF(tf) { + + // FIXME: Eventually remove the TF object entirely. + TF->RegisterChecks(*this); + TF->RegisterPrinters(getStateManager().Printers); + + if (mgr.shouldEagerlyTrimExplodedGraph()) { + // Enable eager node reclaimation when constructing the ExplodedGraph. + G.enableNodeReclamation(); + } +} + +ExprEngine::~ExprEngine() { + BR.FlushReports(); + delete [] NSExceptionInstanceRaiseSelectors; +} + +//===----------------------------------------------------------------------===// +// Utility methods. +//===----------------------------------------------------------------------===// + +const GRState* ExprEngine::getInitialState(const LocationContext *InitLoc) { + const GRState *state = StateMgr.getInitialState(InitLoc); + + // Preconditions. + + // FIXME: It would be nice if we had a more general mechanism to add + // such preconditions. Some day. + do { + const Decl *D = InitLoc->getDecl(); + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { + // Precondition: the first argument of 'main' is an integer guaranteed + // to be > 0. + const IdentifierInfo *II = FD->getIdentifier(); + if (!II || !(II->getName() == "main" && FD->getNumParams() > 0)) + break; + + const ParmVarDecl *PD = FD->getParamDecl(0); + QualType T = PD->getType(); + if (!T->isIntegerType()) + break; + + const MemRegion *R = state->getRegion(PD, InitLoc); + if (!R) + break; + + SVal V = state->getSVal(loc::MemRegionVal(R)); + SVal Constraint_untested = evalBinOp(state, BO_GT, V, + svalBuilder.makeZeroVal(T), + getContext().IntTy); + + DefinedOrUnknownSVal *Constraint = + dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested); + + if (!Constraint) + break; + + if (const GRState *newState = state->assume(*Constraint, true)) + state = newState; + + break; + } + + if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { + // Precondition: 'self' is always non-null upon entry to an Objective-C + // method. + const ImplicitParamDecl *SelfD = MD->getSelfDecl(); + const MemRegion *R = state->getRegion(SelfD, InitLoc); + SVal V = state->getSVal(loc::MemRegionVal(R)); + + if (const Loc *LV = dyn_cast<Loc>(&V)) { + // Assume that the pointer value in 'self' is non-null. + state = state->assume(*LV, true); + assert(state && "'self' cannot be null"); + } + } + } while (0); + + return state; +} + +//===----------------------------------------------------------------------===// +// Top-level transfer function logic (Dispatcher). +//===----------------------------------------------------------------------===// + +/// evalAssume - Called by ConstraintManager. Used to call checker-specific +/// logic for handling assumptions on symbolic values. +const GRState *ExprEngine::processAssume(const GRState *state, SVal cond, + bool assumption) { + state = getCheckerManager().runCheckersForEvalAssume(state, cond, assumption); + + // If the state is infeasible at this point, bail out. + if (!state) + return NULL; + + return TF->evalAssume(state, cond, assumption); +} + +bool ExprEngine::wantsRegionChangeUpdate(const GRState* state) { + return getCheckerManager().wantsRegionChangeUpdate(state); +} + +const GRState * +ExprEngine::processRegionChanges(const GRState *state, + const MemRegion * const *Begin, + const MemRegion * const *End) { + return getCheckerManager().runCheckersForRegionChanges(state, Begin, End); +} + +void ExprEngine::processEndWorklist(bool hasWorkRemaining) { + getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); +} + +void ExprEngine::processCFGElement(const CFGElement E, + StmtNodeBuilder& builder) { + switch (E.getKind()) { + case CFGElement::Statement: + ProcessStmt(E.getAs<CFGStmt>(), builder); + break; + case CFGElement::Initializer: + ProcessInitializer(E.getAs<CFGInitializer>(), builder); + break; + case CFGElement::ImplicitDtor: + ProcessImplicitDtor(E.getAs<CFGImplicitDtor>(), builder); + break; + default: + // Suppress compiler warning. + llvm_unreachable("Unexpected CFGElement kind."); + } +} + +void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) { + // Reclaim any unnecessary nodes in the ExplodedGraph. + G.reclaimRecentlyAllocatedNodes(); + // Recycle any unused states in the GRStateManager. + StateMgr.recycleUnusedStates(); + + currentStmt = S.getStmt(); + PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), + currentStmt->getLocStart(), + "Error evaluating statement"); + + Builder = &builder; + EntryNode = builder.getPredecessor(); + + // Create the cleaned state. + const LocationContext *LC = EntryNode->getLocationContext(); + SymbolReaper SymReaper(LC, currentStmt, SymMgr); + + if (AMgr.shouldPurgeDead()) { + const GRState *St = EntryNode->getState(); + getCheckerManager().runCheckersForLiveSymbols(St, SymReaper); + + const StackFrameContext *SFC = LC->getCurrentStackFrame(); + CleanedState = StateMgr.removeDeadBindings(St, SFC, SymReaper); + } else { + CleanedState = EntryNode->getState(); + } + + // Process any special transfer function for dead symbols. + ExplodedNodeSet Tmp; + + if (!SymReaper.hasDeadSymbols()) + Tmp.Add(EntryNode); + else { + SaveAndRestore<bool> OldSink(Builder->BuildSinks); + SaveOr OldHasGen(Builder->hasGeneratedNode); + + SaveAndRestore<bool> OldPurgeDeadSymbols(Builder->PurgingDeadSymbols); + Builder->PurgingDeadSymbols = true; + + // FIXME: This should soon be removed. + ExplodedNodeSet Tmp2; + getTF().evalDeadSymbols(Tmp2, *this, *Builder, EntryNode, + CleanedState, SymReaper); + + getCheckerManager().runCheckersForDeadSymbols(Tmp, Tmp2, + SymReaper, currentStmt, *this); + + if (!Builder->BuildSinks && !Builder->hasGeneratedNode) + Tmp.Add(EntryNode); + } + + bool HasAutoGenerated = false; + + for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { + ExplodedNodeSet Dst; + + // Set the cleaned state. + Builder->SetCleanedState(*I == EntryNode ? CleanedState : GetState(*I)); + + // Visit the statement. + Visit(currentStmt, *I, Dst); + + // Do we need to auto-generate a node? We only need to do this to generate + // a node with a "cleaned" state; CoreEngine will actually handle + // auto-transitions for other cases. + if (Dst.size() == 1 && *Dst.begin() == EntryNode + && !Builder->hasGeneratedNode && !HasAutoGenerated) { + HasAutoGenerated = true; + builder.generateNode(currentStmt, GetState(EntryNode), *I); + } + } + + // NULL out these variables to cleanup. + CleanedState = NULL; + EntryNode = NULL; + + currentStmt = 0; + + Builder = NULL; +} + +void ExprEngine::ProcessInitializer(const CFGInitializer Init, + StmtNodeBuilder &builder) { + // We don't set EntryNode and currentStmt. And we don't clean up state. + const CXXCtorInitializer *BMI = Init.getInitializer(); + + ExplodedNode *pred = builder.getPredecessor(); + + const StackFrameContext *stackFrame = cast<StackFrameContext>(pred->getLocationContext()); + const CXXConstructorDecl *decl = cast<CXXConstructorDecl>(stackFrame->getDecl()); + const CXXThisRegion *thisReg = getCXXThisRegion(decl, stackFrame); + + SVal thisVal = pred->getState()->getSVal(thisReg); + + if (BMI->isAnyMemberInitializer()) { + ExplodedNodeSet Dst; + + // Evaluate the initializer. + Visit(BMI->getInit(), pred, Dst); + + for (ExplodedNodeSet::iterator I = Dst.begin(), E = Dst.end(); I != E; ++I){ + ExplodedNode *Pred = *I; + const GRState *state = Pred->getState(); + + const FieldDecl *FD = BMI->getAnyMember(); + + SVal FieldLoc = state->getLValue(FD, thisVal); + SVal InitVal = state->getSVal(BMI->getInit()); + state = state->bindLoc(FieldLoc, InitVal); + + // Use a custom node building process. + PostInitializer PP(BMI, stackFrame); + // Builder automatically add the generated node to the deferred set, + // which are processed in the builder's dtor. + builder.generateNode(PP, state, Pred); + } + return; + } + + assert(BMI->isBaseInitializer()); + + // Get the base class declaration. + const CXXConstructExpr *ctorExpr = cast<CXXConstructExpr>(BMI->getInit()); + + // Create the base object region. + SVal baseVal = + getStoreManager().evalDerivedToBase(thisVal, ctorExpr->getType()); + const MemRegion *baseReg = baseVal.getAsRegion(); + assert(baseReg); + Builder = &builder; + ExplodedNodeSet dst; + VisitCXXConstructExpr(ctorExpr, baseReg, pred, dst); +} + +void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, + StmtNodeBuilder &builder) { + Builder = &builder; + + switch (D.getDtorKind()) { + case CFGElement::AutomaticObjectDtor: + ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), builder); + break; + case CFGElement::BaseDtor: + ProcessBaseDtor(cast<CFGBaseDtor>(D), builder); + break; + case CFGElement::MemberDtor: + ProcessMemberDtor(cast<CFGMemberDtor>(D), builder); + break; + case CFGElement::TemporaryDtor: + ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), builder); + break; + default: + llvm_unreachable("Unexpected dtor kind."); + } +} + +void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor dtor, + StmtNodeBuilder &builder) { + ExplodedNode *pred = builder.getPredecessor(); + const GRState *state = pred->getState(); + const VarDecl *varDecl = dtor.getVarDecl(); + + QualType varType = varDecl->getType(); + + if (const ReferenceType *refType = varType->getAs<ReferenceType>()) + varType = refType->getPointeeType(); + + const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl(); + assert(recordDecl && "get CXXRecordDecl fail"); + const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor(); + + Loc dest = state->getLValue(varDecl, pred->getLocationContext()); + + ExplodedNodeSet dstSet; + VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(), + dtor.getTriggerStmt(), pred, dstSet); +} + +void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, + StmtNodeBuilder &builder) { +} + +void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, + StmtNodeBuilder &builder) { +} + +void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, + StmtNodeBuilder &builder) { +} + +void ExprEngine::Visit(const Stmt* S, ExplodedNode* Pred, + ExplodedNodeSet& Dst) { + PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), + S->getLocStart(), + "Error evaluating statement"); + + // Expressions to ignore. + if (const Expr *Ex = dyn_cast<Expr>(S)) + S = Ex->IgnoreParens(); + + // FIXME: add metadata to the CFG so that we can disable + // this check when we KNOW that there is no block-level subexpression. + // The motivation is that this check requires a hashtable lookup. + + if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) { + Dst.Add(Pred); + return; + } + + switch (S->getStmtClass()) { + // C++ stuff we don't support yet. + case Stmt::CXXBindTemporaryExprClass: + case Stmt::CXXCatchStmtClass: + case Stmt::CXXDefaultArgExprClass: + case Stmt::CXXDependentScopeMemberExprClass: + case Stmt::ExprWithCleanupsClass: + case Stmt::CXXNullPtrLiteralExprClass: + case Stmt::CXXPseudoDestructorExprClass: + case Stmt::CXXTemporaryObjectExprClass: + case Stmt::CXXThrowExprClass: + case Stmt::CXXTryStmtClass: + case Stmt::CXXTypeidExprClass: + case Stmt::CXXUuidofExprClass: + case Stmt::CXXUnresolvedConstructExprClass: + case Stmt::CXXScalarValueInitExprClass: + case Stmt::DependentScopeDeclRefExprClass: + case Stmt::UnaryTypeTraitExprClass: + case Stmt::BinaryTypeTraitExprClass: + case Stmt::UnresolvedLookupExprClass: + case Stmt::UnresolvedMemberExprClass: + case Stmt::CXXNoexceptExprClass: + case Stmt::PackExpansionExprClass: + case Stmt::SubstNonTypeTemplateParmPackExprClass: + { + SaveAndRestore<bool> OldSink(Builder->BuildSinks); + Builder->BuildSinks = true; + MakeNode(Dst, S, Pred, GetState(Pred)); + break; + } + + case Stmt::ParenExprClass: + llvm_unreachable("ParenExprs already handled."); + // Cases that should never be evaluated simply because they shouldn't + // appear in the CFG. + case Stmt::BreakStmtClass: + case Stmt::CaseStmtClass: + case Stmt::CompoundStmtClass: + case Stmt::ContinueStmtClass: + case Stmt::DefaultStmtClass: + case Stmt::DoStmtClass: + case Stmt::GotoStmtClass: + case Stmt::IndirectGotoStmtClass: + case Stmt::LabelStmtClass: + case Stmt::NoStmtClass: + case Stmt::NullStmtClass: + llvm_unreachable("Stmt should not be in analyzer evaluation loop"); + break; + + case Stmt::GNUNullExprClass: { + MakeNode(Dst, S, Pred, GetState(Pred)->BindExpr(S, svalBuilder.makeNull())); + break; + } + + case Stmt::ObjCAtSynchronizedStmtClass: + VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst); + break; + + case Stmt::ObjCPropertyRefExprClass: + VisitObjCPropertyRefExpr(cast<ObjCPropertyRefExpr>(S), Pred, Dst); + break; + + // Cases not handled yet; but will handle some day. + case Stmt::DesignatedInitExprClass: + case Stmt::ExtVectorElementExprClass: + case Stmt::ImaginaryLiteralClass: + case Stmt::ImplicitValueInitExprClass: + case Stmt::ObjCAtCatchStmtClass: + case Stmt::ObjCAtFinallyStmtClass: + case Stmt::ObjCAtTryStmtClass: + case Stmt::ObjCEncodeExprClass: + case Stmt::ObjCIsaExprClass: + case Stmt::ObjCProtocolExprClass: + case Stmt::ObjCSelectorExprClass: + case Stmt::ObjCStringLiteralClass: + case Stmt::ParenListExprClass: + case Stmt::PredefinedExprClass: + case Stmt::ShuffleVectorExprClass: + case Stmt::VAArgExprClass: + case Stmt::CUDAKernelCallExprClass: + case Stmt::OpaqueValueExprClass: + // Fall through. + + // Cases we intentionally don't evaluate, since they don't need + // to be explicitly evaluated. + case Stmt::AddrLabelExprClass: + case Stmt::IntegerLiteralClass: + case Stmt::CharacterLiteralClass: + case Stmt::CXXBoolLiteralExprClass: + case Stmt::FloatingLiteralClass: + case Stmt::SizeOfPackExprClass: + Dst.Add(Pred); // No-op. Simply propagate the current state unchanged. + break; + + case Stmt::ArraySubscriptExprClass: + VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); + break; + + case Stmt::AsmStmtClass: + VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst); + break; + + case Stmt::BlockDeclRefExprClass: { + const BlockDeclRefExpr *BE = cast<BlockDeclRefExpr>(S); + VisitCommonDeclRefExpr(BE, BE->getDecl(), Pred, Dst); + break; + } + + case Stmt::BlockExprClass: + VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst); + break; + + case Stmt::BinaryOperatorClass: { + const BinaryOperator* B = cast<BinaryOperator>(S); + if (B->isLogicalOp()) { + VisitLogicalExpr(B, Pred, Dst); + break; + } + else if (B->getOpcode() == BO_Comma) { + const GRState* state = GetState(Pred); + MakeNode(Dst, B, Pred, state->BindExpr(B, state->getSVal(B->getRHS()))); + break; + } + + if (AMgr.shouldEagerlyAssume() && + (B->isRelationalOp() || B->isEqualityOp())) { + ExplodedNodeSet Tmp; + VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); + evalEagerlyAssume(Dst, Tmp, cast<Expr>(S)); + } + else + VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); + + break; + } + + case Stmt::CallExprClass: { + const CallExpr* C = cast<CallExpr>(S); + VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst); + break; + } + + case Stmt::CXXConstructExprClass: { + const CXXConstructExpr *C = cast<CXXConstructExpr>(S); + // For block-level CXXConstructExpr, we don't have a destination region. + // Let VisitCXXConstructExpr() create one. + VisitCXXConstructExpr(C, 0, Pred, Dst); + break; + } + + case Stmt::CXXMemberCallExprClass: { + const CXXMemberCallExpr *MCE = cast<CXXMemberCallExpr>(S); + VisitCXXMemberCallExpr(MCE, Pred, Dst); + break; + } + + case Stmt::CXXOperatorCallExprClass: { + const CXXOperatorCallExpr *C = cast<CXXOperatorCallExpr>(S); + VisitCXXOperatorCallExpr(C, Pred, Dst); + break; + } + + case Stmt::CXXNewExprClass: { + const CXXNewExpr *NE = cast<CXXNewExpr>(S); + VisitCXXNewExpr(NE, Pred, Dst); + break; + } + + case Stmt::CXXDeleteExprClass: { + const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S); + VisitCXXDeleteExpr(CDE, Pred, Dst); + break; + } + // FIXME: ChooseExpr is really a constant. We need to fix + // the CFG do not model them as explicit control-flow. + + case Stmt::ChooseExprClass: { // __builtin_choose_expr + const ChooseExpr* C = cast<ChooseExpr>(S); + VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst); + break; + } + + case Stmt::CompoundAssignOperatorClass: + VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); + break; + + case Stmt::CompoundLiteralExprClass: + VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst); + break; + + case Stmt::BinaryConditionalOperatorClass: + case Stmt::ConditionalOperatorClass: { // '?' operator + const AbstractConditionalOperator *C + = cast<AbstractConditionalOperator>(S); + VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst); + break; + } + + case Stmt::CXXThisExprClass: + VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst); + break; + + case Stmt::DeclRefExprClass: { + const DeclRefExpr *DE = cast<DeclRefExpr>(S); + VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst); + break; + } + + case Stmt::DeclStmtClass: + VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst); + break; + + case Stmt::ForStmtClass: + // This case isn't for branch processing, but for handling the + // initialization of a condition variable. + VisitCondInit(cast<ForStmt>(S)->getConditionVariable(), S, Pred, Dst); + break; + + case Stmt::ImplicitCastExprClass: + case Stmt::CStyleCastExprClass: + case Stmt::CXXStaticCastExprClass: + case Stmt::CXXDynamicCastExprClass: + case Stmt::CXXReinterpretCastExprClass: + case Stmt::CXXConstCastExprClass: + case Stmt::CXXFunctionalCastExprClass: { + const CastExpr* C = cast<CastExpr>(S); + VisitCast(C, C->getSubExpr(), Pred, Dst); + break; + } + + case Stmt::IfStmtClass: + // This case isn't for branch processing, but for handling the + // initialization of a condition variable. + VisitCondInit(cast<IfStmt>(S)->getConditionVariable(), S, Pred, Dst); + break; + + case Stmt::InitListExprClass: + VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst); + break; + + case Stmt::MemberExprClass: + VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst); + break; + case Stmt::ObjCIvarRefExprClass: + VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst); + break; + + case Stmt::ObjCForCollectionStmtClass: + VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst); + break; + + case Stmt::ObjCMessageExprClass: + VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), Pred, Dst); + break; + + case Stmt::ObjCAtThrowStmtClass: { + // FIXME: This is not complete. We basically treat @throw as + // an abort. + SaveAndRestore<bool> OldSink(Builder->BuildSinks); + Builder->BuildSinks = true; + MakeNode(Dst, S, Pred, GetState(Pred)); + break; + } + + case Stmt::ReturnStmtClass: + VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst); + break; + + case Stmt::OffsetOfExprClass: + VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst); + break; + + case Stmt::SizeOfAlignOfExprClass: + VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), Pred, Dst); + break; + + case Stmt::StmtExprClass: { + const StmtExpr* SE = cast<StmtExpr>(S); + + if (SE->getSubStmt()->body_empty()) { + // Empty statement expression. + assert(SE->getType() == getContext().VoidTy + && "Empty statement expression must have void type."); + Dst.Add(Pred); + break; + } + + if (Expr* LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) { + const GRState* state = GetState(Pred); + MakeNode(Dst, SE, Pred, state->BindExpr(SE, state->getSVal(LastExpr))); + } + else + Dst.Add(Pred); + + break; + } + + case Stmt::StringLiteralClass: { + const GRState* state = GetState(Pred); + SVal V = state->getLValue(cast<StringLiteral>(S)); + MakeNode(Dst, S, Pred, state->BindExpr(S, V)); + return; + } + + case Stmt::SwitchStmtClass: + // This case isn't for branch processing, but for handling the + // initialization of a condition variable. + VisitCondInit(cast<SwitchStmt>(S)->getConditionVariable(), S, Pred, Dst); + break; + + case Stmt::UnaryOperatorClass: { + const UnaryOperator *U = cast<UnaryOperator>(S); + if (AMgr.shouldEagerlyAssume()&&(U->getOpcode() == UO_LNot)) { + ExplodedNodeSet Tmp; + VisitUnaryOperator(U, Pred, Tmp); + evalEagerlyAssume(Dst, Tmp, U); + } + else + VisitUnaryOperator(U, Pred, Dst); + break; + } + + case Stmt::WhileStmtClass: + // This case isn't for branch processing, but for handling the + // initialization of a condition variable. + VisitCondInit(cast<WhileStmt>(S)->getConditionVariable(), S, Pred, Dst); + break; + } +} + +//===----------------------------------------------------------------------===// +// Block entrance. (Update counters). +//===----------------------------------------------------------------------===// + +void ExprEngine::processCFGBlockEntrance(ExplodedNodeSet &dstNodes, + GenericNodeBuilder<BlockEntrance> &nodeBuilder){ + + // FIXME: Refactor this into a checker. + const CFGBlock *block = nodeBuilder.getProgramPoint().getBlock(); + ExplodedNode *pred = nodeBuilder.getPredecessor(); + + if (nodeBuilder.getBlockCounter().getNumVisited( + pred->getLocationContext()->getCurrentStackFrame(), + block->getBlockID()) >= AMgr.getMaxVisit()) { + + static int tag = 0; + nodeBuilder.generateNode(pred->getState(), pred, &tag, true); + } +} + +//===----------------------------------------------------------------------===// +// Generic node creation. +//===----------------------------------------------------------------------===// + +ExplodedNode* ExprEngine::MakeNode(ExplodedNodeSet& Dst, const Stmt* S, + ExplodedNode* Pred, const GRState* St, + ProgramPoint::Kind K, const void *tag) { + assert (Builder && "StmtNodeBuilder not present."); + SaveAndRestore<const void*> OldTag(Builder->Tag); + Builder->Tag = tag; + return Builder->MakeNode(Dst, S, Pred, St, K); +} + +//===----------------------------------------------------------------------===// +// Branch processing. +//===----------------------------------------------------------------------===// + +const GRState* ExprEngine::MarkBranch(const GRState* state, + const Stmt* Terminator, + bool branchTaken) { + + switch (Terminator->getStmtClass()) { + default: + return state; + + case Stmt::BinaryOperatorClass: { // '&&' and '||' + + const BinaryOperator* B = cast<BinaryOperator>(Terminator); + BinaryOperator::Opcode Op = B->getOpcode(); + + assert (Op == BO_LAnd || Op == BO_LOr); + + // For &&, if we take the true branch, then the value of the whole + // expression is that of the RHS expression. + // + // For ||, if we take the false branch, then the value of the whole + // expression is that of the RHS expression. + + const Expr* Ex = (Op == BO_LAnd && branchTaken) || + (Op == BO_LOr && !branchTaken) + ? B->getRHS() : B->getLHS(); + + return state->BindExpr(B, UndefinedVal(Ex)); + } + + case Stmt::BinaryConditionalOperatorClass: + case Stmt::ConditionalOperatorClass: { // ?: + const AbstractConditionalOperator* C + = cast<AbstractConditionalOperator>(Terminator); + + // For ?, if branchTaken == true then the value is either the LHS or + // the condition itself. (GNU extension). + + const Expr* Ex; + + if (branchTaken) + Ex = C->getTrueExpr(); + else + Ex = C->getFalseExpr(); + + return state->BindExpr(C, UndefinedVal(Ex)); + } + + case Stmt::ChooseExprClass: { // ?: + + const ChooseExpr* C = cast<ChooseExpr>(Terminator); + + const Expr* Ex = branchTaken ? C->getLHS() : C->getRHS(); + return state->BindExpr(C, UndefinedVal(Ex)); + } + } +} + +/// RecoverCastedSymbol - A helper function for ProcessBranch that is used +/// to try to recover some path-sensitivity for casts of symbolic +/// integers that promote their values (which are currently not tracked well). +/// This function returns the SVal bound to Condition->IgnoreCasts if all the +// cast(s) did was sign-extend the original value. +static SVal RecoverCastedSymbol(GRStateManager& StateMgr, const GRState* state, + const Stmt* Condition, ASTContext& Ctx) { + + const Expr *Ex = dyn_cast<Expr>(Condition); + if (!Ex) + return UnknownVal(); + + uint64_t bits = 0; + bool bitsInit = false; + + while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { + QualType T = CE->getType(); + + if (!T->isIntegerType()) + return UnknownVal(); + + uint64_t newBits = Ctx.getTypeSize(T); + if (!bitsInit || newBits < bits) { + bitsInit = true; + bits = newBits; + } + + Ex = CE->getSubExpr(); + } + + // We reached a non-cast. Is it a symbolic value? + QualType T = Ex->getType(); + + if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits) + return UnknownVal(); + + return state->getSVal(Ex); +} + +void ExprEngine::processBranch(const Stmt* Condition, const Stmt* Term, + BranchNodeBuilder& builder) { + + // Check for NULL conditions; e.g. "for(;;)" + if (!Condition) { + builder.markInfeasible(false); + return; + } + + PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), + Condition->getLocStart(), + "Error evaluating branch"); + + getCheckerManager().runCheckersForBranchCondition(Condition, builder, *this); + + // If the branch condition is undefined, return; + if (!builder.isFeasible(true) && !builder.isFeasible(false)) + return; + + const GRState* PrevState = builder.getState(); + SVal X = PrevState->getSVal(Condition); + + if (X.isUnknownOrUndef()) { + // Give it a chance to recover from unknown. + if (const Expr *Ex = dyn_cast<Expr>(Condition)) { + if (Ex->getType()->isIntegerType()) { + // Try to recover some path-sensitivity. Right now casts of symbolic + // integers that promote their values are currently not tracked well. + // If 'Condition' is such an expression, try and recover the + // underlying value and use that instead. + SVal recovered = RecoverCastedSymbol(getStateManager(), + builder.getState(), Condition, + getContext()); + + if (!recovered.isUnknown()) { + X = recovered; + } + } + } + // If the condition is still unknown, give up. + if (X.isUnknownOrUndef()) { + builder.generateNode(MarkBranch(PrevState, Term, true), true); + builder.generateNode(MarkBranch(PrevState, Term, false), false); + return; + } + } + + DefinedSVal V = cast<DefinedSVal>(X); + + // Process the true branch. + if (builder.isFeasible(true)) { + if (const GRState *state = PrevState->assume(V, true)) + builder.generateNode(MarkBranch(state, Term, true), true); + else + builder.markInfeasible(true); + } + + // Process the false branch. + if (builder.isFeasible(false)) { + if (const GRState *state = PrevState->assume(V, false)) + builder.generateNode(MarkBranch(state, Term, false), false); + else + builder.markInfeasible(false); + } +} + +/// processIndirectGoto - Called by CoreEngine. Used to generate successor +/// nodes by processing the 'effects' of a computed goto jump. +void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { + + const GRState *state = builder.getState(); + SVal V = state->getSVal(builder.getTarget()); + + // Three possibilities: + // + // (1) We know the computed label. + // (2) The label is NULL (or some other constant), or Undefined. + // (3) We have no clue about the label. Dispatch to all targets. + // + + typedef IndirectGotoNodeBuilder::iterator iterator; + + if (isa<loc::GotoLabel>(V)) { + const LabelDecl *L = cast<loc::GotoLabel>(V).getLabel(); + + for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) { + if (I.getLabel() == L) { + builder.generateNode(I, state); + return; + } + } + + assert(false && "No block with label."); + return; + } + + if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) { + // Dispatch to the first target and mark it as a sink. + //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); + // FIXME: add checker visit. + // UndefBranches.insert(N); + return; + } + + // This is really a catch-all. We don't support symbolics yet. + // FIXME: Implement dispatch for symbolic pointers. + + for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) + builder.generateNode(I, state); +} + + +void ExprEngine::VisitGuardedExpr(const Expr* Ex, const Expr* L, + const Expr* R, + ExplodedNode* Pred, ExplodedNodeSet& Dst) { + + assert(Ex == currentStmt && + Pred->getLocationContext()->getCFG()->isBlkExpr(Ex)); + + const GRState* state = GetState(Pred); + SVal X = state->getSVal(Ex); + + assert (X.isUndef()); + + const Expr *SE = (Expr*) cast<UndefinedVal>(X).getData(); + assert(SE); + X = state->getSVal(SE); + + // Make sure that we invalidate the previous binding. + MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, X, true)); +} + +/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path +/// nodes when the control reaches the end of a function. +void ExprEngine::processEndOfFunction(EndOfFunctionNodeBuilder& builder) { + getTF().evalEndPath(*this, builder); + StateMgr.EndPath(builder.getState()); + getCheckerManager().runCheckersForEndPath(builder, *this); +} + +/// ProcessSwitch - Called by CoreEngine. Used to generate successor +/// nodes by processing the 'effects' of a switch statement. +void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { + typedef SwitchNodeBuilder::iterator iterator; + const GRState* state = builder.getState(); + const Expr* CondE = builder.getCondition(); + SVal CondV_untested = state->getSVal(CondE); + + if (CondV_untested.isUndef()) { + //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); + // FIXME: add checker + //UndefBranches.insert(N); + + return; + } + DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested); + + const GRState *DefaultSt = state; + |