diff options
Diffstat (limited to 'include/clang/Checker')
17 files changed, 620 insertions, 306 deletions
diff --git a/include/clang/Checker/BugReporter/BugReporter.h b/include/clang/Checker/BugReporter/BugReporter.h index 3749b43..370d965 100644 --- a/include/clang/Checker/BugReporter/BugReporter.h +++ b/include/clang/Checker/BugReporter/BugReporter.h @@ -471,6 +471,9 @@ void registerFindLastStore(BugReporterContext& BRC, const void *memregion, void registerNilReceiverVisitor(BugReporterContext &BRC); +void registerVarDeclsLastStore(BugReporterContext &BRC, const void *stmt, + const ExplodedNode *N); + } // end namespace clang::bugreporter //===----------------------------------------------------------------------===// diff --git a/include/clang/Checker/PathSensitive/AnalysisManager.h b/include/clang/Checker/PathSensitive/AnalysisManager.h index 3c7cb68..3855079 100644 --- a/include/clang/Checker/PathSensitive/AnalysisManager.h +++ b/include/clang/Checker/PathSensitive/AnalysisManager.h @@ -21,6 +21,11 @@ namespace clang { +namespace idx { + class Indexer; + class TranslationUnit; +} + class AnalysisManager : public BugReporterData { AnalysisContextManager AnaCtxMgr; LocationContextManager LocCtxMgr; @@ -35,6 +40,11 @@ class AnalysisManager : public BugReporterData { StoreManagerCreator CreateStoreMgr; ConstraintManagerCreator CreateConstraintMgr; + /// \brief Provide function definitions in other translation units. This is + /// NULL if we don't have multiple translation units. AnalysisManager does + /// not own the Indexer. + idx::Indexer *Idxer; + enum AnalysisScope { ScopeTU, ScopeDecl } AScope; // The maximum number of exploded nodes the analyzer will generate. @@ -62,13 +72,15 @@ public: AnalysisManager(ASTContext &ctx, Diagnostic &diags, const LangOptions &lang, PathDiagnosticClient *pd, StoreManagerCreator storemgr, - ConstraintManagerCreator constraintmgr, unsigned maxnodes, - unsigned maxloop, + ConstraintManagerCreator constraintmgr, + idx::Indexer *idxer, + unsigned maxnodes, unsigned maxloop, bool vizdot, bool vizubi, bool purge, bool eager, bool trim, - bool inlinecall) + bool inlinecall, bool useUnoptimizedCFG) - : Ctx(ctx), Diags(diags), LangInfo(lang), PD(pd), - CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr), + : AnaCtxMgr(useUnoptimizedCFG), Ctx(ctx), Diags(diags), LangInfo(lang), + PD(pd), + CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr),Idxer(idxer), AScope(ScopeDecl), MaxNodes(maxnodes), MaxLoop(maxloop), VisualizeEGDot(vizdot), VisualizeEGUbi(vizubi), PurgeDead(purge), EagerlyAssume(eager), TrimGraph(trim), InlineCall(inlinecall) {} @@ -79,6 +91,10 @@ public: LocCtxMgr.clear(); AnaCtxMgr.clear(); } + + AnalysisContextManager& getAnalysisContextManager() { + return AnaCtxMgr; + } StoreManagerCreator getStoreManagerCreator() { return CreateStoreMgr; @@ -88,6 +104,8 @@ public: return CreateConstraintMgr; } + idx::Indexer *getIndexer() const { return Idxer; } + virtual ASTContext &getASTContext() { return Ctx; } @@ -133,6 +151,10 @@ public: bool shouldInlineCall() const { return InlineCall; } + bool hasIndexer() const { return Idxer != 0; } + + const AnalysisContext *getAnalysisContextInAnotherTU(const Decl *D); + CFG *getCFG(Decl const *D) { return AnaCtxMgr.getContext(D)->getCFG(); } @@ -145,9 +167,25 @@ public: return AnaCtxMgr.getContext(D)->getParentMap(); } + AnalysisContext *getAnalysisContext(const Decl *D) { + return AnaCtxMgr.getContext(D); + } + + AnalysisContext *getAnalysisContext(const Decl *D, idx::TranslationUnit *TU) { + return AnaCtxMgr.getContext(D, TU); + } + + const StackFrameContext *getStackFrame(AnalysisContext *Ctx, + LocationContext const *Parent, + Stmt const *S, const CFGBlock *Blk, + unsigned Idx) { + return LocCtxMgr.getStackFrame(Ctx, Parent, S, Blk, Idx); + } + // Get the top level stack frame. - const StackFrameContext *getStackFrame(Decl const *D) { - return LocCtxMgr.getStackFrame(AnaCtxMgr.getContext(D), 0, 0, 0, 0); + const StackFrameContext *getStackFrame(Decl const *D, + idx::TranslationUnit *TU) { + return LocCtxMgr.getStackFrame(AnaCtxMgr.getContext(D, TU), 0, 0, 0, 0); } // Get a stack frame with parent. diff --git a/include/clang/Checker/PathSensitive/Checker.h b/include/clang/Checker/PathSensitive/Checker.h index 49dc3fa..136a29d 100644 --- a/include/clang/Checker/PathSensitive/Checker.h +++ b/include/clang/Checker/PathSensitive/Checker.h @@ -36,7 +36,6 @@ class CheckerContext { const GRState *ST; const Stmt *statement; const unsigned size; - bool DoneEvaluating; // FIXME: This is not a permanent API change. public: bool *respondsToCallback; public: @@ -166,6 +165,10 @@ public: Eng.getBugReporter().EmitReport(R); } + AnalysisContext *getCurrentAnalysisContext() const { + return Pred->getLocationContext()->getAnalysisContext(); + } + private: ExplodedNode *GenerateNodeImpl(const Stmt* stmt, const GRState *state, bool markAsSink) { @@ -223,7 +226,6 @@ private: // FIXME: Remove the 'tag' option. void GR_VisitBind(ExplodedNodeSet &Dst, GRStmtNodeBuilder &Builder, GRExprEngine &Eng, - const Stmt *AssignE, const Stmt *StoreE, ExplodedNode *Pred, void *tag, SVal location, SVal val, bool isPrevisit) { @@ -231,7 +233,7 @@ private: isPrevisit ? ProgramPoint::PreStmtKind : ProgramPoint::PostStmtKind, 0, StoreE); assert(isPrevisit && "Only previsit supported for now."); - PreVisitBind(C, AssignE, StoreE, location, val); + PreVisitBind(C, StoreE, location, val); } // FIXME: Remove the 'tag' option. @@ -261,15 +263,17 @@ public: virtual void _PreVisit(CheckerContext &C, const Stmt *S) {} virtual void _PostVisit(CheckerContext &C, const Stmt *S) {} virtual void VisitLocation(CheckerContext &C, const Stmt *S, SVal location) {} - virtual void PreVisitBind(CheckerContext &C, const Stmt *AssignE, - const Stmt *StoreE, SVal location, SVal val) {} + virtual void PreVisitBind(CheckerContext &C, const Stmt *StoreE, + SVal location, SVal val) {} virtual void EvalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper) {} virtual void EvalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng) {} + virtual void MarkLiveSymbols(const GRState *state, SymbolReaper &SymReaper) {} + virtual void VisitBranchCondition(GRBranchNodeBuilder &Builder, GRExprEngine &Eng, - Stmt *Condition, void *tag) {} + const Stmt *Condition, void *tag) {} virtual bool EvalNilReceiver(CheckerContext &C, const ObjCMessageExpr *ME) { return false; @@ -280,12 +284,23 @@ public: } virtual const GRState *EvalAssume(const GRState *state, SVal Cond, - bool Assumption) { + bool Assumption, bool *respondsToCallback) { + *respondsToCallback = false; + return state; + } + + virtual bool WantsRegionChangeUpdate(const GRState *state) { return false; } + + virtual const GRState *EvalRegionChanges(const GRState *state, + const MemRegion * const *Begin, + const MemRegion * const *End, + bool *respondsToCallback) { + *respondsToCallback = false; return state; } virtual void VisitEndAnalysis(ExplodedGraph &G, BugReporter &B, - bool hasWorkRemaining) {} + GRExprEngine &Eng) {} }; } // end clang namespace diff --git a/include/clang/Checker/PathSensitive/CheckerHelpers.h b/include/clang/Checker/PathSensitive/CheckerHelpers.h new file mode 100644 index 0000000..ea3c842 --- /dev/null +++ b/include/clang/Checker/PathSensitive/CheckerHelpers.h @@ -0,0 +1,40 @@ +//== CheckerHelpers.h - Helper functions for checkers ------------*- 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 CheckerVisitor. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_CHECKER_PATHSENSITIVE_CHECKERHELPERS +#define LLVM_CLANG_CHECKER_PATHSENSITIVE_CHECKERHELPERS + +#include "clang/AST/Stmt.h" + +namespace clang { + +bool containsMacro(const Stmt *S); +bool containsEnum(const Stmt *S); +bool containsStaticLocal(const Stmt *S); +bool containsBuiltinOffsetOf(const Stmt *S); +template <class T> bool containsStmt(const Stmt *S) { + if (isa<T>(S)) + return true; + + for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); + ++I) + if (const Stmt *child = *I) + if (containsStmt<T>(child)) + return true; + + return false; +} + +} + +#endif diff --git a/include/clang/Checker/PathSensitive/ConstraintManager.h b/include/clang/Checker/PathSensitive/ConstraintManager.h index ce7d1b3..97535f5 100644 --- a/include/clang/Checker/PathSensitive/ConstraintManager.h +++ b/include/clang/Checker/PathSensitive/ConstraintManager.h @@ -34,9 +34,6 @@ public: virtual const GRState *Assume(const GRState *state, DefinedSVal Cond, bool Assumption) = 0; - virtual const GRState *AssumeInBound(const GRState *state, DefinedSVal Idx, - DefinedSVal UpperBound, bool Assumption) = 0; - std::pair<const GRState*, const GRState*> AssumeDual(const GRState *state, DefinedSVal Cond) { return std::make_pair(Assume(state, Cond, true), diff --git a/include/clang/Checker/PathSensitive/Environment.h b/include/clang/Checker/PathSensitive/Environment.h index 2981731..611f507 100644 --- a/include/clang/Checker/PathSensitive/Environment.h +++ b/include/clang/Checker/PathSensitive/Environment.h @@ -83,8 +83,14 @@ public: return Environment(F.GetEmptyMap()); } - Environment BindExpr(Environment Env, const Stmt *S, SVal V, + /// Bind the value 'V' to the statement 'S'. + Environment bindExpr(Environment Env, const Stmt *S, SVal V, bool Invalidate); + + /// Bind the location 'location' and value 'V' to the statement 'S'. This + /// is used when simulating loads/stores. + Environment bindExprAndLocation(Environment Env, const Stmt *S, SVal location, + SVal V); Environment RemoveDeadBindings(Environment Env, SymbolReaper &SymReaper, const GRState *ST, diff --git a/include/clang/Checker/PathSensitive/GRCoreEngine.h b/include/clang/Checker/PathSensitive/GRCoreEngine.h index 7f101dc..216ecac 100644 --- a/include/clang/Checker/PathSensitive/GRCoreEngine.h +++ b/include/clang/Checker/PathSensitive/GRCoreEngine.h @@ -43,6 +43,11 @@ class GRCoreEngine { friend class GRCallEnterNodeBuilder; friend class GRCallExitNodeBuilder; +public: + typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > + BlocksAborted; +private: + GRSubEngine& SubEngine; /// G - The simulation graph. Each node is a (location,state) pair. @@ -57,21 +62,21 @@ class GRCoreEngine { /// These are used to record for key nodes in the ExplodedGraph the /// number of times different CFGBlocks have been visited along a path. GRBlockCounter::Factory BCounterFactory; - - /// A flag that indicates whether paths were halted because - /// ProcessBlockEntrace returned false. - bool BlockAborted; + + /// The locations where we stopped doing work because we visited a location + /// too many times. + BlocksAborted blocksAborted; void GenerateNode(const ProgramPoint& Loc, const GRState* State, ExplodedNode* Pred); void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred); void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred); - void HandleBlockExit(CFGBlock* B, ExplodedNode* Pred); - void HandlePostStmt(const PostStmt& S, CFGBlock* B, + void HandleBlockExit(const CFGBlock* B, ExplodedNode* Pred); + void HandlePostStmt(const PostStmt& S, const CFGBlock* B, unsigned StmtIdx, ExplodedNode *Pred); - void HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock* B, + void HandleBranch(const Stmt* Cond, const Stmt* Term, const CFGBlock* B, ExplodedNode* Pred); void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, unsigned Index, ExplodedNode *Pred); @@ -82,25 +87,42 @@ class GRCoreEngine { return SubEngine.getInitialState(InitLoc); } - void ProcessEndPath(GREndPathNodeBuilder& Builder); + void ProcessEndPath(GREndPathNodeBuilder& Builder) { + SubEngine.ProcessEndPath(Builder); + } - void ProcessStmt(CFGElement E, GRStmtNodeBuilder& Builder); + void ProcessStmt(const CFGElement E, GRStmtNodeBuilder& Builder) { + SubEngine.ProcessStmt(E, Builder); + } - bool ProcessBlockEntrance(CFGBlock* Blk, const ExplodedNode *Pred, - GRBlockCounter BC); + bool ProcessBlockEntrance(const CFGBlock* Blk, const ExplodedNode *Pred, + GRBlockCounter BC) { + return SubEngine.ProcessBlockEntrance(Blk, Pred, BC); + } - void ProcessBranch(Stmt* Condition, Stmt* Terminator, - GRBranchNodeBuilder& Builder); + void ProcessBranch(const Stmt* Condition, const Stmt* Terminator, + GRBranchNodeBuilder& Builder) { + SubEngine.ProcessBranch(Condition, Terminator, Builder); + } - void ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder); + void ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder) { + SubEngine.ProcessIndirectGoto(Builder); + } - void ProcessSwitch(GRSwitchNodeBuilder& Builder); + void ProcessSwitch(GRSwitchNodeBuilder& Builder) { + SubEngine.ProcessSwitch(Builder); + } - void ProcessCallEnter(GRCallEnterNodeBuilder &Builder); - void ProcessCallExit(GRCallExitNodeBuilder &Builder); + void ProcessCallEnter(GRCallEnterNodeBuilder &Builder) { + SubEngine.ProcessCallEnter(Builder); + } + + void ProcessCallExit(GRCallExitNodeBuilder &Builder) { + SubEngine.ProcessCallExit(Builder); + } private: GRCoreEngine(const GRCoreEngine&); // Do not implement. @@ -112,16 +134,14 @@ public: GRCoreEngine(GRSubEngine& subengine) : SubEngine(subengine), G(new ExplodedGraph()), WList(GRWorkList::MakeBFS()), - BCounterFactory(G->getAllocator()), - BlockAborted(false) {} + BCounterFactory(G->getAllocator()) {} /// Construct a GRCoreEngine object to analyze the provided CFG and to /// use the provided worklist object to execute the worklist algorithm. /// The GRCoreEngine object assumes ownership of 'wlist'. GRCoreEngine(GRWorkList* wlist, GRSubEngine& subengine) : SubEngine(subengine), G(new ExplodedGraph()), WList(wlist), - BCounterFactory(G->getAllocator()), - BlockAborted(false) {} + BCounterFactory(G->getAllocator()) {} ~GRCoreEngine() { delete WList; @@ -136,12 +156,29 @@ public: /// ExecuteWorkList - Run the worklist algorithm for a maximum number of /// steps. Returns true if there is still simulation state on the worklist. - bool ExecuteWorkList(const LocationContext *L, unsigned Steps); + bool ExecuteWorkList(const LocationContext *L, unsigned Steps, + const GRState *InitState); + void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, + const GRState *InitState, + ExplodedNodeSet &Dst); + + // Functions for external checking of whether we have unfinished work + bool wasBlockAborted() const { return !blocksAborted.empty(); } + bool hasWorkRemaining() const { return wasBlockAborted() || WList->hasWork(); } + + GRWorkList *getWorkList() const { return WList; } + + BlocksAborted::const_iterator blocks_aborted_begin() const { + return blocksAborted.begin(); + } + BlocksAborted::const_iterator blocks_aborted_end() const { + return blocksAborted.end(); + } }; class GRStmtNodeBuilder { GRCoreEngine& Eng; - CFGBlock& B; + const CFGBlock& B; const unsigned Idx; ExplodedNode* Pred; GRStateManager& Mgr; @@ -163,7 +200,7 @@ public: void GenerateAutoTransition(ExplodedNode* N); public: - GRStmtNodeBuilder(CFGBlock* b, unsigned idx, ExplodedNode* N, + GRStmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N, GRCoreEngine* e, GRStateManager &mgr); ~GRStmtNodeBuilder(); @@ -222,11 +259,11 @@ public: /// getStmt - Return the current block-level expression associated with /// this builder. - Stmt* getStmt() const { return B[Idx]; } + const Stmt* getStmt() const { return B[Idx]; } /// getBlock - Return the CFGBlock associated with the block-level expression /// of this builder. - CFGBlock* getBlock() const { return &B; } + const CFGBlock* getBlock() const { return &B; } unsigned getIndex() const { return Idx; } @@ -239,15 +276,15 @@ public: return Pred->getState(); } - ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, - const GRState* St) { + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S, + ExplodedNode* Pred, const GRState* St) { return MakeNode(Dst, S, Pred, St, PointKind); } - ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred, const GRState* St, ProgramPoint::Kind K); - ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, Stmt* S, + ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S, ExplodedNode* Pred, const GRState* St) { bool Tmp = BuildSinks; BuildSinks = true; @@ -259,9 +296,9 @@ public: class GRBranchNodeBuilder { GRCoreEngine& Eng; - CFGBlock* Src; - CFGBlock* DstT; - CFGBlock* DstF; + const CFGBlock* Src; + const CFGBlock* DstT; + const CFGBlock* DstF; ExplodedNode* Pred; typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy; @@ -273,8 +310,8 @@ class GRBranchNodeBuilder { bool InFeasibleFalse; public: - GRBranchNodeBuilder(CFGBlock* src, CFGBlock* dstT, CFGBlock* dstF, - ExplodedNode* pred, GRCoreEngine* e) + GRBranchNodeBuilder(const CFGBlock* src, const CFGBlock* dstT, + const CFGBlock* dstF, ExplodedNode* pred, GRCoreEngine* e) : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), GeneratedTrue(false), GeneratedFalse(false), InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} @@ -289,7 +326,7 @@ public: ExplodedNode* generateNode(const GRState* State, bool branch); - CFGBlock* getTargetBlock(bool branch) const { + const CFGBlock* getTargetBlock(bool branch) const { return branch ? DstT : DstF; } @@ -311,31 +348,31 @@ public: class GRIndirectGotoNodeBuilder { GRCoreEngine& Eng; - CFGBlock* Src; - CFGBlock& DispatchBlock; - Expr* E; + const CFGBlock* Src; + const CFGBlock& DispatchBlock; + const Expr* E; ExplodedNode* Pred; public: - GRIndirectGotoNodeBuilder(ExplodedNode* pred, CFGBlock* src, Expr* e, - CFGBlock* dispatch, GRCoreEngine* eng) - : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} + GRIndirectGotoNodeBuilder(ExplodedNode* pred, const CFGBlock* src, + const Expr* e, const CFGBlock* dispatch, GRCoreEngine* eng) + : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} class iterator { - CFGBlock::succ_iterator I; + CFGBlock::const_succ_iterator I; friend class GRIndirectGotoNodeBuilder; - iterator(CFGBlock::succ_iterator i) : I(i) {} + iterator(CFGBlock::const_succ_iterator i) : I(i) {} public: iterator& operator++() { ++I; return *this; } bool operator!=(const iterator& X) const { return I != X.I; } - LabelStmt* getLabel() const { + const LabelStmt* getLabel() const { return llvm::cast<LabelStmt>((*I)->getLabel()); } - CFGBlock* getBlock() const { + const CFGBlock* getBlock() const { return *I; } }; @@ -346,37 +383,38 @@ public: ExplodedNode* generateNode(const iterator& I, const GRState* State, bool isSink = false); - Expr* getTarget() const { return E; } + const Expr* getTarget() const { return E; } const GRState* getState() const { return Pred->State; } }; class GRSwitchNodeBuilder { GRCoreEngine& Eng; - CFGBlock* Src; - Expr* Condition; + const CFGBlock* Src; + const Expr* Condition; ExplodedNode* Pred; public: - GRSwitchNodeBuilder(ExplodedNode* pred, CFGBlock* src, - Expr* condition, GRCoreEngine* eng) + GRSwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src, + const Expr* condition, GRCoreEngine* eng) : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} class iterator { - CFGBlock::succ_reverse_iterator I; + CFGBlock::const_succ_reverse_iterator I; friend class GRSwitchNodeBuilder; - iterator(CFGBlock::succ_reverse_iterator i) : I(i) {} + iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} public: iterator& operator++() { ++I; return *this; } - bool operator!=(const iterator& X) const { return I != X.I; } + bool operator!=(const iterator &X) const { return I != X.I; } + bool operator==(const iterator &X) const { return I == X.I; } - CaseStmt* getCase() const { + const CaseStmt* getCase() const { return llvm::cast<CaseStmt>((*I)->getLabel()); } - CFGBlock* getBlock() const { + const CFGBlock* getBlock() const { return *I; } }; @@ -389,21 +427,21 @@ public: ExplodedNode* generateDefaultCaseNode(const GRState* State, bool isSink = false); - Expr* getCondition() const { return Condition; } + const Expr* getCondition() const { return Condition; } const GRState* getState() const { return Pred->State; } }; class GREndPathNodeBuilder { GRCoreEngine &Eng; - CFGBlock& B; + const CFGBlock& B; ExplodedNode* Pred; public: bool HasGeneratedNode; public: - GREndPathNodeBuilder(CFGBlock* b, ExplodedNode* N, GRCoreEngine* e) + GREndPathNodeBuilder(const CFGBlock* b, ExplodedNode* N, GRCoreEngine* e) : Eng(*e), B(*b), Pred(N), HasGeneratedNode(false) {} ~GREndPathNodeBuilder(); @@ -427,7 +465,7 @@ public: void GenerateCallExitNode(const GRState *state); - CFGBlock* getBlock() const { return &B; } + const CFGBlock* getBlock() const { return &B; } const GRState* getState() const { return getPredecessor()->getState(); @@ -442,8 +480,8 @@ class GRCallEnterNodeBuilder { // The call site. const Stmt *CE; - // The definition of callee. - const FunctionDecl *FD; + // The AnalysisContext of the callee. + AnalysisContext *CalleeCtx; // The parent block of the CallExpr. const CFGBlock *Block; @@ -453,9 +491,9 @@ class GRCallEnterNodeBuilder { public: GRCallEnterNodeBuilder(GRCoreEngine &eng, const ExplodedNode *pred, - const Stmt *s, const FunctionDecl *fd, + const Stmt *s, AnalysisContext *callee, const CFGBlock *blk, unsigned idx) - : Eng(eng), Pred(pred), CE(s), FD(fd), Block(blk), Index(idx) {} + : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} const GRState *getState() const { return Pred->getState(); } @@ -465,7 +503,7 @@ public: const Stmt *getCallExpr() const { return CE; } - const FunctionDecl *getCallee() const { return FD; } + AnalysisContext *getCalleeContext() const { return CalleeCtx; } const CFGBlock *getBlock() const { return Block; } diff --git a/include/clang/Checker/PathSensitive/GRExprEngine.h b/include/clang/Checker/PathSensitive/GRExprEngine.h index 8eaf3f4..5ba0b36 100644 --- a/include/clang/Checker/PathSensitive/GRExprEngine.h +++ b/include/clang/Checker/PathSensitive/GRExprEngine.h @@ -64,7 +64,7 @@ class GRExprEngine : public GRSubEngine { const GRState* CleanedState; /// CurrentStmt - The current block-level statement. - Stmt* CurrentStmt; + const Stmt* CurrentStmt; // Obj-C Class Identifiers. IdentifierInfo* NSExceptionII; @@ -75,10 +75,26 @@ class GRExprEngine : public GRSubEngine { llvm::OwningPtr<GRSimpleAPICheck> BatchAuditor; + enum CallbackKind { + PreVisitStmtCallback, + PostVisitStmtCallback, + ProcessAssumeCallback, + EvalRegionChangesCallback + }; + + typedef uint32_t CallbackTag; + + /// GetCallbackTag - Create a tag for a certain kind of callback. The 'Sub' + /// argument can be used to differentiate callbacks that depend on another + /// value from a small set of possibilities, such as statement classes. + static inline CallbackTag GetCallbackTag(CallbackKind K, uint32_t Sub = 0) { + assert(Sub == ((Sub << 8) >> 8) && "Tag sub-kind must fit into 24 bits"); + return K | (Sub << 8); + } + typedef llvm::DenseMap<void *, unsigned> CheckerMap; typedef std::vector<std::pair<void *, Checker*> > CheckersOrdered; - typedef llvm::DenseMap<std::pair<unsigned, unsigned>, CheckersOrdered *> - CheckersOrderedCache; + typedef llvm::DenseMap<CallbackTag, CheckersOrdered *> CheckersOrderedCache; /// A registration map from checker tag to the index into the /// ordered checkers vector. @@ -89,7 +105,7 @@ class GRExprEngine : public GRSubEngine { CheckersOrdered Checkers; /// A map used for caching the checkers that respond to the callback for - /// a particular statement and visitation order. + /// a particular callback tag. CheckersOrderedCache COCache; /// The BugReporter associated with this engine. It is important that @@ -101,10 +117,10 @@ class GRExprEngine : public GRSubEngine { class CallExprWLItem { public: - CallExpr::arg_iterator I; + CallExpr::const_arg_iterator I; ExplodedNode *N; - CallExprWLItem(const CallExpr::arg_iterator &i, ExplodedNode *n) + CallExprWLItem(const CallExpr::const_arg_iterator &i, ExplodedNode *n) : I(i), N(n) {} }; @@ -114,13 +130,22 @@ public: ~GRExprEngine(); void ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) { - CoreEngine.ExecuteWorkList(L, Steps); + CoreEngine.ExecuteWorkList(L, Steps, 0); + } + + /// Execute the work list with an initial state. Nodes that reaches the exit + /// of the function are added into the Dst set, which represent the exit + /// state of the function call. + void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, + const GRState *InitState, + ExplodedNodeSet &Dst) { + CoreEngine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst); } /// getContext - Return the ASTContext associated with this analysis. ASTContext& getContext() const { return AMgr.getASTContext(); } - AnalysisManager &getAnalysisManager() const { return AMgr; } + virtual AnalysisManager &getAnalysisManager() { return AMgr; } SValuator &getSValuator() { return SVator; } @@ -166,17 +191,18 @@ public: /// ProcessStmt - Called by GRCoreEngine. Used to generate new successor /// nodes by processing the 'effects' of a block-level statement. - void ProcessStmt(CFGElement E, GRStmtNodeBuilder& builder); + void ProcessStmt(const CFGElement E, GRStmtNodeBuilder& builder); /// ProcessBlockEntrance - Called by GRCoreEngine when start processing /// a CFGBlock. This method returns true if the analysis should continue /// exploring the given path, and false otherwise. - bool ProcessBlockEntrance(CFGBlock* B, const ExplodedNode *Pred, + bool ProcessBlockEntrance(const CFGBlock* B, const ExplodedNode *Pred, GRBlockCounter BC); /// ProcessBranch - Called by GRCoreEngine. Used to generate successor /// nodes by processing the 'effects' of a branch condition. - void ProcessBranch(Stmt* Condition, Stmt* Term, GRBranchNodeBuilder& builder); + void ProcessBranch(const Stmt* Condition, const Stmt* Term, + GRBranchNodeBuilder& builder); /// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor /// nodes by processing the 'effects' of a computed goto jump. @@ -201,10 +227,19 @@ public: /// EvalAssume - Callback function invoked by the ConstraintManager when /// making assumptions about state values. - const GRState *ProcessAssume(const GRState *state, SVal cond, bool assumption); + const GRState *ProcessAssume(const GRState *state, SVal cond,bool assumption); + + /// WantsRegionChangeUpdate - Called by GRStateManager to determine if a + /// region change should trigger a ProcessRegionChanges update. + bool WantsRegionChangeUpdate(const GRState* state); - GRStateManager& getStateManager() { return StateMgr; } - const GRStateManager& getStateManager() const { return StateMgr; } + /// ProcessRegionChanges - Called by GRStateManager whenever a change is made + /// to the store. Used to update checkers that track region values. + const GRState* ProcessRegionChanges(const GRState *state, + const MemRegion * const *Begin, + const MemRegion * const *End); + + virtual GRStateManager& getStateManager() { return StateMgr; } StoreManager& getStoreManager() { return StateMgr.getStoreManager(); } @@ -227,21 +262,29 @@ public: SymbolManager& getSymbolManager() { return SymMgr; } const SymbolManager& getSymbolManager() const { return SymMgr; } + // Functions for external checking of whether we have unfinished work + bool wasBlockAborted() const { return CoreEngine.wasBlockAborted(); } + bool hasWorkRemaining() const { + return wasBlockAborted() || CoreEngine.getWorkList()->hasWork(); + } + + const GRCoreEngine &getCoreEngine() const { return CoreEngine; } + protected: const GRState* GetState(ExplodedNode* N) { return N == EntryNode ? CleanedState : N->getState(); } public: - ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, - const GRState* St, + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S, + ExplodedNode* Pred, const GRState* St, ProgramPoint::Kind K = ProgramPoint::PostStmtKind, const void *tag = 0); /// CheckerVisit - Dispatcher for performing checker-specific logic /// at specific statements. - void CheckerVisit(Stmt *S, ExplodedNodeSet &Dst, ExplodedNodeSet &Src, - bool isPrevisit); + void CheckerVisit(const Stmt *S, ExplodedNodeSet &Dst, ExplodedNodeSet &Src, + CallbackKind Kind); bool CheckerEvalCall(const CallExpr *CE, ExplodedNodeSet &Dst, @@ -252,125 +295,130 @@ public: const GRState *state, ExplodedNode *Pred); - void CheckerVisitBind(const Stmt *AssignE, const Stmt *StoreE, - ExplodedNodeSet &Dst, ExplodedNodeSet &Src, - SVal location, SVal val, bool isPrevisit); - + void CheckerVisitBind(const Stmt *StoreE, ExplodedNodeSet &Dst, + ExplodedNodeSet &Src, SVal location, SVal val, + bool isPrevisit); /// Visit - Transfer function logic for all statements. Dispatches to /// other functions that handle specific kinds of statements. - void Visit(Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst); + void Visit(const Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitLValue - Evaluate the lvalue of the expression. For example, if Ex is /// a DeclRefExpr, it evaluates to the MemRegionVal which represents its /// storage location. Note that not all kinds of expressions has lvalue. - void VisitLValue(Expr* Ex, ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitLValue(const Expr* Ex, ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitArraySubscriptExpr - Transfer function for array accesses. - void VisitArraySubscriptExpr(ArraySubscriptExpr* Ex, ExplodedNode* Pred, + void VisitArraySubscriptExpr(const ArraySubscriptExpr* Ex, ExplodedNode* Pred, ExplodedNodeSet& Dst, bool asLValue); /// VisitAsmStmt - Transfer function logic for inline asm. - void VisitAsmStmt(AsmStmt* A, ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitAsmStmt(const AsmStmt* A, ExplodedNode* Pred, ExplodedNodeSet& Dst); - void VisitAsmStmtHelperOutputs(AsmStmt* A, - AsmStmt::outputs_iterator I, - AsmStmt::outputs_iterator E, + void VisitAsmStmtHelperOutputs(const AsmStmt* A, + AsmStmt::const_outputs_iterator I, + AsmStmt::const_outputs_iterator E, ExplodedNode* Pred, ExplodedNodeSet& Dst); - void VisitAsmStmtHelperInputs(AsmStmt* A, - AsmStmt::inputs_iterator I, - AsmStmt::inputs_iterator E, + void VisitAsmStmtHelperInputs(const AsmStmt* A, + AsmStmt::const_inputs_iterator I, + AsmStmt::const_inputs_iterator E, ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitBlockExpr - Transfer function logic for BlockExprs. - void VisitBlockExpr(BlockExpr *BE, ExplodedNode *Pred, ExplodedNodeSet &Dst); + void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitBinaryOperator - Transfer function logic for binary operators. - void VisitBinaryOperator(BinaryOperator* B, ExplodedNode* Pred, + void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode* Pred, ExplodedNodeSet& Dst, bool asLValue); /// VisitCall - Transfer function for function calls. - void VisitCall(CallExpr* CE, ExplodedNode* Pred, - CallExpr::arg_iterator AI, CallExpr::arg_iterator AE, + void VisitCall(const CallExpr* CE, ExplodedNode* Pred, + CallExpr::const_arg_iterator AI, + CallExpr::const_arg_iterator AE, ExplodedNodeSet& Dst, bool asLValue); /// VisitCast - Transfer function logic for all casts (implicit and explicit). - void VisitCast(CastExpr *CastE, Expr *Ex, ExplodedNode *Pred, + void VisitCast(const CastExpr *CastE, const Expr *Ex, ExplodedNode *Pred, ExplodedNodeSet &Dst, bool asLValue); /// VisitCompoundLiteralExpr - Transfer function logic for compound literals. - void VisitCompoundLiteralExpr(CompoundLiteralExpr* CL, ExplodedNode* Pred, - ExplodedNodeSet& Dst, bool asLValue); + void VisitCompoundLiteralExpr(const CompoundLiteralExpr* CL, + ExplodedNode* Pred, ExplodedNodeSet& Dst, + bool asLValue); /// VisitDeclRefExpr - Transfer function logic for DeclRefExprs. - void VisitDeclRefExpr(DeclRefExpr* DR, ExplodedNode* Pred, + void VisitDeclRefExpr(const DeclRefExpr* DR, ExplodedNode* Pred, ExplodedNodeSet& Dst, bool asLValue); /// VisitBlockDeclRefExpr - Transfer function logic for BlockDeclRefExprs. - void VisitBlockDeclRefExpr(BlockDeclRefExpr* DR, ExplodedNode* Pred, + void VisitBlockDeclRefExpr(const BlockDeclRefExpr* DR, ExplodedNode* Pred, ExplodedNodeSet& Dst, bool asLValue); - void VisitCommonDeclRefExpr(Expr* DR, const NamedDecl *D,ExplodedNode* Pred, - ExplodedNodeSet& Dst, bool asLValue); + void VisitCommonDeclRefExpr(const Expr* DR, const NamedDecl *D, + ExplodedNode* Pred, ExplodedNodeSet& Dst, + bool asLValue); /// VisitDeclStmt - Transfer function logic for DeclStmts. - void VisitDeclStmt(DeclStmt* DS, ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitDeclStmt(const DeclStmt* DS, ExplodedNode* Pred, + ExplodedNodeSet& Dst); /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose - void VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitGuardedExpr(const Expr* Ex, const Expr* L, const Expr* R, + ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitCondInit - Transfer function for handling the initialization /// of a condition variable in an IfStmt, SwitchStmt, etc. - void VisitCondInit(VarDecl *VD, Stmt *S, ExplodedNode *Pred, + void VisitCondInit(const VarDecl *VD, const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet& Dst); - void VisitInitListExpr(InitListExpr* E, ExplodedNode* Pred, + void VisitInitListExpr(const InitListExpr* E, ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitLogicalExpr - Transfer function logic for '&&', '||' - void VisitLogicalExpr(BinaryOperator* B, ExplodedNode* Pred, + void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitMemberExpr - Transfer function for member expressions. - void VisitMemberExpr(MemberExpr* M, ExplodedNode* Pred, ExplodedNodeSet& Dst, - bool asLValue); + void VisitMemberExpr(const MemberExpr* M, ExplodedNode* Pred, + ExplodedNodeSet& Dst, bool asLValue); /// VisitObjCIvarRefExpr - Transfer function logic for ObjCIvarRefExprs. - void VisitObjCIvarRefExpr(ObjCIvarRefExpr* DR, ExplodedNode* Pred, + void VisitObjCIvarRefExpr(const ObjCIvarRefExpr* DR, ExplodedNode* Pred, ExplodedNodeSet& Dst, bool asLValue); /// VisitObjCForCollectionStmt - Transfer function logic for /// ObjCForCollectionStmt. - void VisitObjCForCollectionStmt(ObjCForCollectionStmt* S, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitObjCForCollectionStmt(const ObjCForCollectionStmt* S, + ExplodedNode* Pred, ExplodedNodeSet& Dst); - void VisitObjCForCollectionStmtAux(ObjCForCollectionStmt* S, + void VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst, SVal ElementV); /// VisitObjCMessageExpr - Transfer function for ObjC message expressions. - void VisitObjCMessageExpr(ObjCMessageExpr* ME, ExplodedNode* Pred, + void VisitObjCMessageExpr(const ObjCMessageExpr* ME, ExplodedNode* Pred, ExplodedNodeSet& Dst, bool asLValue); /// VisitReturnStmt - Transfer function logic for return statements. - void VisitReturnStmt(ReturnStmt* R, ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitReturnStmt(const ReturnStmt* R, ExplodedNode* Pred, + ExplodedNodeSet& Dst); /// VisitOffsetOfExpr - Transfer function for offsetof. - void VisitOffsetOfExpr(OffsetOfExpr* Ex, ExplodedNode* Pred, + void VisitOffsetOfExpr(const OffsetOfExpr* Ex, ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitSizeOfAlignOfExpr - Transfer function for sizeof. - void VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr* Ex, ExplodedNode* Pred, + void VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr* Ex, ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitUnaryOperator - Transfer function logic for unary operators. - void VisitUnaryOperator(UnaryOperator* B, ExplodedNode* Pred, + void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode* Pred, ExplodedNodeSet& Dst, bool asLValue); - void VisitCXXThisExpr(CXXThisExpr *TE, ExplodedNode *Pred, + void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred, ExplodedNodeSet & Dst); void VisitCXXConstructExpr(const CXXConstructExpr *E, SVal Dest, @@ -380,17 +428,17 @@ public: void VisitCXXMemberCallExpr(const CXXMemberCallExpr *MCE, ExplodedNode *Pred, ExplodedNodeSet &Dst); - void VisitCXXNewExpr(CXXNewExpr *CNE, ExplodedNode *Pred, + void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, ExplodedNodeSet &Dst); - void VisitCXXDeleteExpr(CXXDeleteExpr *CDE, ExplodedNode *Pred, + void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred, ExplodedNodeSet &Dst); void VisitAggExpr(const Expr *E, SVal Dest, ExplodedNode *Pred, ExplodedNodeSet &Dst); /// Create a C++ temporary object for an rvalue. - void CreateCXXTemporaryObject(Expr *Ex, ExplodedNode *Pred, + void CreateCXXTemporaryObject(const Expr *Ex, ExplodedNode *Pred, ExplodedNodeSet &Dst); /// Synthesize CXXThisRegion. @@ -398,14 +446,15 @@ public: const StackFrameContext *SFC); /// Evaluate arguments with a work list algorithm. - void EvalArguments(ExprIterator AI, ExprIterator AE, + void EvalArguments(ConstExprIterator AI, ConstExprIterator AE, const FunctionProtoType *FnType, ExplodedNode *Pred, ExplodedNodeSet &Dst); /// EvalEagerlyAssume - Given the nodes in 'Src', eagerly assume symbolic /// expressions of the form 'x != 0' and generate new nodes (stored in Dst) /// with those assumptions. - void EvalEagerlyAssume(ExplodedNodeSet& Dst, ExplodedNodeSet& Src, Expr *Ex); + void EvalEagerlyAssume(ExplodedNodeSet& Dst, ExplodedNodeSet& Src, + const Expr *Ex); SVal EvalMinus(SVal X) { return X.isValid() ? SVator.EvalMinus(cast<NonLoc>(X)) : X; @@ -433,42 +482,41 @@ public: } protected: - void EvalObjCMessageExpr(ExplodedNodeSet& Dst, ObjCMessageExpr* ME, + void EvalObjCMessageExpr(ExplodedNodeSet& Dst, const ObjCMessageExpr* ME, ExplodedNode* Pred, const GRState *state) { assert (Builder && "GRStmtNodeBuilder must be defined."); getTF().EvalObjCMessageExpr(Dst, *this, *Builder, ME, Pred, state); } - const GRState* MarkBranch(const GRState* St, Stmt* Terminator, + const GRState* MarkBranch(const GRState* St, const Stmt* Terminator, bool branchTaken); /// EvalBind - Handle the semantics of binding a value to a specific location. /// This method is used by EvalStore, VisitDeclStmt, and others. - void EvalBind(ExplodedNodeSet& Dst, Stmt *AssignE, - Stmt* StoreE, ExplodedNode* Pred, + void EvalBind(ExplodedNodeSet& Dst, const Stmt* StoreE, ExplodedNode* Pred, const GRState* St, SVal location, SVal Val, bool atDeclInit = false); public: // FIXME: 'tag' should be removed, and a LocationContext should be used // instead. - void EvalLoad(ExplodedNodeSet& Dst, Expr* Ex, ExplodedNode* Pred, + void EvalLoad(ExplodedNodeSet& Dst, const Expr* Ex, ExplodedNode* Pred, const GRState* St, SVal location, const void *tag = 0, QualType LoadTy = QualType()); // FIXME: 'tag' should be removed, and a LocationContext should be used // instead. - void EvalStore(ExplodedNodeSet& Dst, Expr* AssignE, Expr* StoreE, + void EvalStore(ExplodedNodeSet& Dst, const Expr* AssignE, const Expr* StoreE, ExplodedNode* Pred, const GRState* St, SVal TargetLV, SVal Val, const void *tag = 0); private: - void EvalLoadCommon(ExplodedNodeSet& Dst, Expr* Ex, ExplodedNode* Pred, + void EvalLoadCommon(ExplodedNodeSet& Dst, const Expr* Ex, ExplodedNode* Pred, const GRState* St, SVal location, const void *tag, QualType LoadTy); // FIXME: 'tag' should be removed, and a LocationContext should be used // instead. - void EvalLocation(ExplodedNodeSet &Dst, Stmt *S, ExplodedNode* Pred, + void EvalLocation(ExplodedNodeSet &Dst, const Stmt *S, ExplodedNode* Pred, const GRState* St, SVal location, const void *tag, bool isLoad); diff --git a/include/clang/Checker/PathSensitive/GRState.h b/include/clang/Checker/PathSensitive/GRState.h index 67a2caf..d72d63a 100644 --- a/include/clang/Checker/PathSensitive/GRState.h +++ b/include/clang/Checker/PathSensitive/GRState.h @@ -77,6 +77,10 @@ private: Store St; GenericDataMap GDM; + /// makeWithStore - Return a GRState with the same values as the current + /// state with the exception of using the specified Store. + const GRState *makeWithStore(Store store) const; + public: /// This ctor is used when creating the first GRState object. @@ -134,10 +138,6 @@ public: return Env.LookupExpr(E); } - /// makeWithStore - Return a GRState with the same values as the current - /// state with the exception of using the specified Store. - const GRState *makeWithStore(Store store) const; - BasicValueFactory &getBasicVals() const; SymbolManager &getSymbolManager() const; @@ -201,8 +201,15 @@ public: const LocationContext *LC, SVal V) const; + /// Create a new state by binding the value 'V' to the statement 'S' in the + /// state's environment. const GRState *BindExpr(const Stmt *S, SVal V, bool Invalidate = true) const; + /// Create a new state by binding the value 'V' and location 'locaton' to the + /// statement 'S' in the state's environment. + const GRState *bindExprAndLocation(const Stmt *S, SVal location, SVal V) + const; + const GRState *bindDecl(const VarRegion *VR, SVal V) const; const GRState *bindDeclWithNoInit(const VarRegion *VR) const; @@ -215,6 +222,28 @@ public: const GRState *unbindLoc(Loc LV) const; + /// InvalidateRegion - Returns the state with bindings for the given region + /// cleared from the store. See InvalidateRegions. + const GRState *InvalidateRegion(const MemRegion *R, + const Expr *E, unsigned BlockCount, + StoreManager::InvalidatedSymbols *IS = NULL) + const { + return InvalidateRegions(&R, &R+1, E, BlockCount, IS, false); + } + + /// InvalidateRegions - Returns the state with bindings for the given regions + /// cleared from the store. The regions are provided as a continuous array + /// from Begin to End. Optionally invalidates global regions as well. + const GRState *InvalidateRegions(const MemRegion * const *Begin, + const MemRegion * const *End, + const Expr *E, unsigned BlockCount, + StoreManager::InvalidatedSymbols *IS, + bool invalidateGlobals) const; + + /// EnterStackFrame - Returns the state for entry to the given stack frame, + /// preserving the current state. + const GRState *EnterStackFrame(const StackFrameContext *frame) const; + /// Get the lvalue for a variable reference. Loc getLValue(const VarDecl *D, const LocationContext *LC) const; @@ -235,11 +264,18 @@ public: const llvm::APSInt *getSymVal(SymbolRef sym) const; - SVal getSVal(const Stmt* Ex) const; - + /// Returns the SVal bound to the statement 'S' in the state's environment. + SVal getSVal(const Stmt* S) const; + SVal getSValAsScalarOrLoc(const Stmt *Ex) const; SVal getSVal(Loc LV, QualType T = QualType()) const; + + /// Returns a "simplified" SVal bound to the location 'LV' in the state's + /// store. A simplified SVal will include optimizations such as + /// if the SVal is a symbol whose value is perfectly constrained then that + /// constant value is returned instead. + SVal getSimplifiedSVal(Loc LV, QualType T= QualType()) const; SVal getSVal(const MemRegion* R) const; @@ -375,6 +411,9 @@ class GRStateManager { friend class GRState; friend class GRExprEngine; // FIXME: Remove. private: + /// Eng - The GRSubEngine that owns this state manager. + GRSubEngine &Eng; + EnvironmentManager EnvMgr; llvm::OwningPtr<StoreManager> StoreMgr; llvm::OwningPtr<ConstraintManager> ConstraintMgr; @@ -404,7 +443,8 @@ public: ConstraintManagerCreator CreateConstraintManager, llvm::BumpPtrAllocator& alloc, GRSubEngine &subeng) - : EnvMgr(alloc), + : Eng(subeng), + EnvMgr(alloc), GDMFactory(alloc), ValueMgr(alloc, Ctx, *this), Alloc(alloc) { @@ -447,11 +487,16 @@ public: StoreManager& getStoreManager() { return *StoreMgr; } ConstraintManager& getConstraintManager() { return *ConstraintMgr; } + GRSubEngine& getOwningEngine() { return Eng; } const GRState* RemoveDeadBindings(const GRState* St, const StackFrameContext *LCtx, SymbolReaper& SymReaper); + /// Marshal a new state for the callee in another translation unit. + /// 'state' is owned by the caller's engine. + const GRState *MarshalState(const GRState *state, const StackFrameContext *L); + public: SVal ArrayToPointer(Loc Array) { @@ -581,50 +626,10 @@ GRState::Assume(DefinedOrUnknownSVal Cond) const { cast<DefinedSVal>(Cond)); } -inline const GRState *GRState::AssumeInBound(DefinedOrUnknownSVal Idx, - DefinedOrUnknownSVal UpperBound, - bool Assumption) const { - if (Idx.isUnknown() || UpperBound.isUnknown()) - return this; - - ConstraintManager &CM = *getStateManager().ConstraintMgr; - return CM.AssumeInBound(this, cast<DefinedSVal>(Idx), - cast<DefinedSVal>(UpperBound), Assumption); -} - -inline const GRState * -GRState::bindCompoundLiteral(const CompoundLiteralExpr* CL, - const LocationContext *LC, SVal V) const { - Store new_store = - getStateManager().StoreMgr->BindCompoundLiteral(St, CL, LC, V); - return makeWithStore(new_store); -} - -inline const GRState *GRState::bindDecl(const VarRegion* VR, SVal IVal) const { - Store new_store = getStateManager().StoreMgr->BindDecl(St, VR, IVal); - return makeWithStore(new_store); -} - -inline const GRState *GRState::bindDeclWithNoInit(const VarRegion* VR) const { - Store new_store = getStateManager().StoreMgr->BindDeclWithNoInit(St, VR); - return makeWithStore(new_store); -} - -inline const GRState *GRState::bindLoc(Loc LV, SVal V) const { - Store new_store = getStateManager().StoreMgr->Bind(St, LV, V); - return makeWithStore(new_store); -} - inline const GRState *GRState::bindLoc(SVal LV, SVal V) const { return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V); } -inline const GRState *GRState::bindDefault(SVal loc, SVal V) const { - const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion(); - Store new_store = getStateManager().StoreMgr->BindDefault(St, R, V); - return makeWithStore(new_store); -} - inline Loc GRState::getLValue(const VarDecl* VD, const LocationContext *LC) const { return getStateManager().StoreMgr->getLValueVar(VD, LC); diff --git a/include/clang/Checker/PathSensitive/GRSubEngine.h b/include/clang/Checker/PathSensitive/GRSubEngine.h index 90a41d7..1904835 100644 --- a/include/clang/Checker/PathSensitive/GRSubEngine.h +++ b/include/clang/Checker/PathSensitive/GRSubEngine.h @@ -17,7 +17,7 @@ namespace clang { -class Stmt; +class AnalysisManager; class CFGBlock; class CFGElement; class ExplodedNode; @@ -32,6 +32,8 @@ class GREndPathNodeBuilder; class GRCallEnterNodeBuilder; class GRCallExitNodeBuilder; class LocationContext; +class MemRegion; +class Stmt; class GRSubEngine { public: @@ -39,21 +41,23 @@ public: virtual const GRState* getInitialState(const LocationContext *InitLoc) = 0; - virtual GRStateManager& getStateManager() = 0; + virtual AnalysisManager &getAnalysisManager() = 0; + + virtual GRStateManager &getStateManager() = 0; /// Called by GRCoreEngine. Used to generate new successor /// nodes by processing the 'effects' of a block-level statement. - virtual void ProcessStmt(CFGElement E, GRStmtNodeBuilder& builder) = 0; + virtual void ProcessStmt(const CFGElement E, GRStmtNodeBuilder& builder) = 0; /// Called by GRCoreEngine when start processing /// a CFGBlock. This method returns true if the analysis should continue /// exploring the given path, and false otherwise. - virtual bool ProcessBlockEntrance(CFGBlock* B, const ExplodedNode *Pred, + virtual bool ProcessBlockEntrance(const CFGBlock* B, const ExplodedNode *Pred, GRBlockCounter BC) = 0; /// Called by GRCoreEngine. Used to generate successor /// nodes by processing the 'effects' of a branch condition. - virtual void ProcessBranch(Stmt* Condition, Stmt* Term, + virtual void ProcessBranch(const Stmt* Condition, const Stmt* Term, GRBranchNodeBuilder& builder) = 0; /// Called by GRCoreEngine. Used to generate successor @@ -73,12 +77,27 @@ public: // Generate the first post callsite node. virtual void ProcessCallExit(GRCallExitNodeBuilder &builder) = 0; - + /// Called by ConstraintManager. Used to call checker-specific /// logic for handling assumptions on symbolic values. virtual const GRState* ProcessAssume(const GRState *state, SVal cond, bool assumption) = 0; - + + /// WantsRegionChangeUpdate - Called by GRStateManager to determine if a + /// region change should trigger a ProcessRegionChanges update. + virtual bool WantsRegionChangeUpdate(const GRState* state) = 0; + + /// ProcessRegionChanges - Called by GRStateManager whenever a change is made + /// to the store. Used to update checkers that track region values. + virtual const GRState* ProcessRegionChanges(const GRState* state, + const MemRegion* const *Begin, + const MemRegion* const *End) = 0; + + inline const GRState* ProcessRegionChange(const GRState* state, + const MemRegion* MR) { + return ProcessRegionChanges(state, &MR, &MR+1); + } + /// Called by GRCoreEngine when the analysis worklist is either empty or the // maximum number of analysis steps have been reached. virtual void ProcessEndWorklist(bool hasWorkRemaining) = 0; diff --git a/include/clang/Checker/PathSensitive/GRTransferFuncs.h b/include/clang/Checker/PathSensitive/GRTransferFuncs.h index 374f998..320b7f7 100644 --- a/include/clang/Checker/PathSensitive/GRTransferFuncs.h +++ b/include/clang/Checker/PathSensitive/GRTransferFuncs.h @@ -42,13 +42,13 @@ public: virtual void EvalCall(ExplodedNodeSet& Dst, GRExprEngine& Engine, GRStmtNodeBuilder& Builder, - CallExpr* CE, SVal L, + const CallExpr* CE, SVal L, ExplodedNode* Pred) {} virtual void EvalObjCMessageExpr(ExplodedNodeSet& Dst, GRExprEngine& Engine, GRStmtNodeBuilder& Builder, - ObjCMessageExpr* ME, + const ObjCMessageExpr* ME, ExplodedNode* Pred, const GRState *state) {} @@ -73,7 +73,7 @@ public: virtual void EvalReturn(ExplodedNodeSet& Dst, GRExprEngine& Engine, GRStmtNodeBuilder& Builder, - ReturnStmt* S, + const ReturnStmt* S, ExplodedNode* Pred) {} // Assumptions. diff --git a/include/clang/Checker/PathSensitive/GRWorkList.h b/include/clang/Checker/PathSensitive/GRWorkList.h index b8f90fa..315b614 100644 --- a/include/clang/Checker/PathSensitive/GRWorkList.h +++ b/include/clang/Checker/PathSensitive/GRWorkList.h @@ -27,12 +27,12 @@ class ExplodedNodeImpl; class GRWorkListUnit { ExplodedNode* Node; GRBlockCounter Counter; - CFGBlock* Block; + const CFGBlock* Block; unsigned BlockIdx; // This is the index of the next statement. public: GRWorkListUnit(ExplodedNode* N, GRBlockCounter C, - CFGBlock* B, unsigned idx) + const CFGBlock* B, unsigned idx) : Node(N), Counter(C), Block(B), @@ -46,7 +46,7 @@ public: ExplodedNode* getNode() const { return Node; } GRBlockCounter getBlockCounter() const { return Counter; } - CFGBlock* getBlock() const { return Block; } + const CFGBlock* getBlock() const { return Block; } unsigned getIndex() const { return BlockIdx; } }; @@ -58,8 +58,8 @@ public: virtual void Enqueue(const GRWorkListUnit& U) = 0; - void Enqueue(ExplodedNode* N, CFGBlock& B, unsigned idx) { - Enqueue(GRWorkListUnit(N, CurrentCounter, &B, idx)); + void Enqueue(ExplodedNode* N, const CFGBlock* B, unsigned idx) { + Enqueue(GRWorkListUnit(N, CurrentCounter, B, idx)); } void Enqueue(ExplodedNode* N) { diff --git a/include/clang/Checker/PathSensitive/MemRegion.h b/include/clang/Checker/PathSensitive/MemRegion.h index feb4b72..96f906a 100644 --- a/include/clang/Checker/PathSensitive/MemRegion.h +++ b/include/clang/Checker/PathSensitive/MemRegion.h @@ -20,6 +20,7 @@ #include "clang/AST/DeclObjC.h" #include "clang/Checker/PathSensitive/SVals.h" #include "llvm/Support/Casting.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/ADT/FoldingSet.h" #include <string> @@ -38,6 +39,22 @@ class ValueManager; class VarRegion; class CodeTextRegion; +/// Represent a region's offset within the top level base region. +class RegionOffset { + /// The base region. + const MemRegion *R; + + /// The bit offset within the base region. It shouldn't be negative. + int64_t Offset; + +public: + RegionOffset(const MemRegion *r) : R(r), Offset(0) {} + RegionOffset(const MemRegion *r, int64_t off) : R(r), Offset(off) {} + + const MemRegion *getRegion() const { return R; } + int64_t getOffset() const { return Offset; } +}; + //===----------------------------------------------------------------------===// // Base region classes. //===----------------------------------------------------------------------===// @@ -111,6 +128,9 @@ public: bool hasStackParametersStorage() const; + /// Compute the offset within the top level memory object. + RegionOffset getAsOffset() const; + virtual void dumpToStream(llvm::raw_ostream& os) const; void dump() const; @@ -261,6 +281,7 @@ public: } }; + /// SubRegion - A region that subsets another larger region. Most regions /// are subclasses of SubRegion. class SubRegion : public MemRegion { @@ -287,31 +308,6 @@ public: }; //===----------------------------------------------------------------------===// -// Auxillary data classes for use with MemRegions. -//===----------------------------------------------------------------------===// - -class ElementRegion; - -class RegionRawOffset { -private: - friend class ElementRegion; - - const MemRegion *Region; - int64_t Offset; - - RegionRawOffset(const MemRegion* reg, int64_t offset = 0) - : Region(reg), Offset(offset) {} - -public: - // FIXME: Eventually support symbolic offsets. - int64_t getByteOffset() const { return Offset; } - const MemRegion *getRegion() const { return Region; } - - void dumpToStream(llvm::raw_ostream& os) const; - void dump() const; -}; - -//===----------------------------------------------------------------------===// // MemRegion subclasses. //===----------------------------------------------------------------------===// @@ -353,25 +349,23 @@ protected: TypedRegion(const MemRegion* sReg, Kind k) : SubRegion(sReg, k) {} public: - virtual QualType getValueType(ASTContext &C) const = 0; + virtual QualType getValueType() const = 0; - virtual QualType getLocationType(ASTContext& C) const { + virtual QualType getLocationType() const { // FIXME: We can possibly optimize this later to cache this value. - return C.getPointerType(getValueType(C)); + return getContext().getPointerType(getValueType()); } - QualType getDesugaredValueType(ASTContext& C) const { - QualType T = getValueType(C); + QualType getDesugaredValueType() const { + QualType T = getValueType(); return T.getTypePtr() ? T.getDesugaredType() : T; } - QualType getDesugaredLocationType(ASTContext& C) const { - return getLocationType(C).getDesugaredType(); + QualType getDesugaredLocationType() const { + return getLocationType().getDesugaredType(); } - bool isBoundable() const { - return !getValueType(getContext()).isNull(); - } + bool isBoundable() const { return true; } static bool classof(const MemRegion* R) { unsigned k = R->getKind(); @@ -384,9 +378,8 @@ class CodeTextRegion : public TypedRegion { protected: CodeTextRegion(const MemRegion *sreg, Kind k) : TypedRegion(sreg, k) {} public: - QualType getValueType(ASTContext &C) const { - // Do not get the object type of a CodeTextRegion. - assert(0); + QualType getValueType() const { + assert(0 && "Do not get the object type of a CodeTextRegion."); return QualType(); } @@ -405,8 +398,8 @@ public: FunctionTextRegion(const FunctionDecl* fd, const MemRegion* sreg) : CodeTextRegion(sreg, FunctionTextRegionKind), FD(fd) {} - QualType getLocationType(ASTContext &C) const { - return C.getPointerType(FD->getType()); + QualType getLocationType() const { + return getContext().getPointerType(FD->getType()); } const FunctionDecl *getDecl() const { @@ -444,7 +437,7 @@ class BlockTextRegion : public CodeTextRegion { : CodeTextRegion(sreg, BlockTextRegionKind), BD(bd), AC(ac), locTy(lTy) {} public: - QualType getLocationType(ASTContext &C) const { + QualType getLocationType() const { return locTy; } @@ -581,7 +574,7 @@ public: const StringLiteral* getStringLiteral() const { return Str; } - QualType getValueType(ASTContext& C) const { + QualType getValueType() const { return Str->getType(); } @@ -615,8 +608,8 @@ private: const CompoundLiteralExpr* CL, const MemRegion* superRegion); public: - QualType getValueType(ASTContext& C) const { - return C.getCanonicalType(CL->getType()); + QualType getValueType() const { + return CL->getType(); } bool isBoundable() const { return !CL->isFileScope(); } @@ -673,9 +666,9 @@ public: const StackFrameContext *getStackFrame() const; - QualType getValueType(ASTContext& C) const { + QualType getValueType() const { // FIXME: We can cache this if needed. - return C.getCanonicalType(getDecl()->getType()); + return getDecl()->getType(); } void dumpToStream(llvm::raw_ostream& os) const; @@ -701,10 +694,10 @@ class CXXThisRegion : public TypedRegion { void Profile(llvm::FoldingSetNodeID &ID) const; public: - QualType getValueType(ASTContext &C) const { + QualType getValueType() const { return QualType(ThisPointerTy, 0); } - + void dumpToStream(llvm::raw_ostream& os) const; static bool classof(const MemRegion* R) { @@ -727,9 +720,9 @@ public: const FieldDecl* getDecl() const { return cast<FieldDecl>(D); } - QualType getValueType(ASTContext& C) const { + QualType getValueType() const { // FIXME: We can cache this if needed. - return C.getCanonicalType(getDecl()->getType()); + return getDecl()->getType(); } DefinedOrUnknownSVal getExtent(ValueManager& ValMgr) const; @@ -758,7 +751,7 @@ class ObjCIvarRegion : public DeclRegion { public: const ObjCIvarDecl* getDecl() const { return cast<ObjCIvarDecl>(D); } - QualType getValueType(ASTContext&) const { return getDecl()->getType(); } + QualType getValueType() const { return getDecl()->getType(); } void dumpToStream(llvm::raw_ostream& os) const; @@ -766,6 +759,30 @@ public: return R->getKind() == ObjCIvarRegionKind; } }; +//===----------------------------------------------------------------------===// +// Auxillary data classes for use with MemRegions. +//===----------------------------------------------------------------------===// + +class ElementRegion; + +class RegionRawOffset { +private: + friend class ElementRegion; + + const MemRegion *Region; + int64_t Offset; + + RegionRawOffset(const MemRegion* reg, int64_t offset = 0) + : Region(reg), Offset(offset) {} + +public: + // FIXME: Eventually support symbolic offsets. + int64_t getByteOffset() const { return Offset; } + const MemRegion *getRegion() const { return Region; } + + void dumpToStream(llvm::raw_ostream& os) const; + void dump() const; +}; class ElementRegion : public TypedRegion { friend class MemRegionManager; @@ -788,15 +805,15 @@ public: SVal getIndex() const { return Index; } - QualType getValueType(ASTContext&) const { + QualType getValueType() const { return ElementType; } QualType getElementType() const { return ElementType; } - - RegionRawOffset getAsRawOffset() const; + /// Compute the offset within the array. The array might also be a subobject. + RegionRawOffset getAsArrayOffset() const; void dumpToStream(llvm::raw_ostream& os) const; @@ -820,7 +837,7 @@ class CXXObjectRegion : public TypedRegion { Expr const *E, const MemRegion *sReg); public: - QualType getValueType(ASTContext& C) const { + QualType getValueType() const { return Ex->getType(); } diff --git a/include/clang/Checker/PathSensitive/SVals.h b/include/clang/Checker/PathSensitive/SVals.h index 55fd3ea..cdb338a 100644 --- a/include/clang/Checker/PathSensitive/SVals.h +++ b/include/clang/Checker/PathSensitive/SVals.h @@ -45,15 +45,14 @@ public: enum { BaseBits = 2, BaseMask = 0x3 }; protected: - void* Data; + const void* Data; unsigned Kind; protected: SVal(const void* d, bool isLoc, unsigned ValKind) - : Data(const_cast<void*>(d)), - Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} + : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} - explicit SVal(BaseKind k, void* D = NULL) + explicit SVal(BaseKind k, const void* D = NULL) : Data(D), Kind(k) {} public: @@ -69,7 +68,7 @@ public: inline void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddInteger((unsigned) getRawKind()); - ID.AddPointer(reinterpret_cast<void*>(Data)); + ID.AddPointer(Data); } inline bool operator==(const SVal& R) const { @@ -163,13 +162,13 @@ public: class UndefinedVal : public SVal { public: UndefinedVal() : SVal(UndefinedKind) {} - UndefinedVal(void* D) : SVal(UndefinedKind, D) {} + UndefinedVal(const void* D) : SVal(UndefinedKind, D) {} static inline bool classof(const SVal* V) { return V->getBaseKind() == UndefinedKind; } - void* getData() const { return Data; } + const void* getData() const { return Data; } }; class DefinedOrUnknownSVal : public SVal { @@ -287,7 +286,7 @@ public: : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {} const SymExpr *getSymbolicExpression() const { - return reinterpret_cast<SymExpr*>(Data); + return reinterpret_cast<const SymExpr*>(Data); } static inline bool classof(const SVal* V) { @@ -305,7 +304,7 @@ public: ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} const llvm::APSInt& getValue() const { - return *static_cast<llvm::APSInt*>(Data); + return *static_cast<const llvm::APSInt*>(Data); } // Transfer functions for binary/unary operations on ConcreteInts. @@ -368,7 +367,7 @@ class CompoundVal : public NonLoc { public: const CompoundValData* getValue() const { - return static_cast<CompoundValData*>(Data); + return static_cast<const CompoundValData*>(Data); } typedef llvm::ImmutableList<SVal>::iterator iterator; @@ -419,8 +418,8 @@ class GotoLabel : public Loc { public: GotoLabel(LabelStmt* Label) : Loc(GotoLabelKind, Label) {} - LabelStmt* getLabel() const { - return static_cast<LabelStmt*>(Data); + const LabelStmt* getLabel() const { + return static_cast<const LabelStmt*>(Data); } static inline bool classof(const SVal* V) { @@ -439,7 +438,7 @@ public: MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {} const MemRegion* getRegion() const { - return static_cast<MemRegion*>(Data); + return static_cast<const MemRegion*>(Data); } const MemRegion* StripCasts() const; @@ -473,7 +472,7 @@ public: ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} const llvm::APSInt& getValue() const { - return *static_cast<llvm::APSInt*>(Data); + return *static_cast<const llvm::APSInt*>(Data); } // Transfer functions for binary/unary operations on ConcreteInts. diff --git a/include/clang/Checker/PathSensitive/Store.h b/include/clang/Checker/PathSensitive/Store.h index 7a60ebb..a1a4184 100644 --- a/include/clang/Checker/PathSensitive/Store.h +++ b/include/clang/Checker/PathSensitive/Store.h @@ -149,9 +149,8 @@ public: return UnknownVal(); } - virtual const GRState *RemoveDeadBindings(GRState &state, - const StackFrameContext *LCtx, - SymbolReaper& SymReaper, + virtual Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx, + SymbolReaper& SymReaper, llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) = 0; virtual Store BindDecl(Store store, const VarRegion *VR, SVal initVal) = 0; @@ -159,25 +158,39 @@ public: virtual Store BindDeclWithNoInit(Store store, const VarRegion *VR) = 0; typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols; - - virtual Store InvalidateRegion(Store store, - const MemRegion *R, - const Expr *E, unsigned Count, - InvalidatedSymbols *IS) = 0; - + typedef llvm::SmallVector<const MemRegion *, 8> InvalidatedRegions; + + /// InvalidateRegions - Clears out the specified regions from the store, + /// marking their values as unknown. Depending on the store, this may also + /// invalidate additional regions that may have changed based on accessing + /// the given regions. Optionally, invalidates non-static globals as well. + /// \param[in] store The initial store + /// \param[in] Begin A pointer to the first region to invalidate. + /// \param[in] End A pointer just past the last region to invalidate. + /// \param[in] E The current statement being evaluated. Used to conjure + /// symbols to mark the values of invalidated regions. + /// \param[in] Count The current block count. Used to conjure + /// symbols to mark the values of invalidated regions. + /// \param[in,out] IS A set to fill with any symbols that are no longer + /// accessible. Pass \c NULL if this information will not be used. + /// \param[in] invalidateGlobals If \c true, any non-static global regions + /// are invalidated as well. + /// \param[in,out] Regions A vector to fill with any regions being + /// invalidated. This should include any regions explicitly invalidated + /// even if they do not currently have bindings. Pass \c NULL if this + /// information will not be used. virtual Store InvalidateRegions(Store store, const MemRegion * const *Begin, const MemRegion * const *End, const Expr *E, unsigned Count, InvalidatedSymbols *IS, - bool invalidateGlobals) = 0; + bool invalidateGlobals, + InvalidatedRegions *Regions) = 0; /// EnterStackFrame - Let the StoreManager to do something when execution /// engine is about to execute into a callee. - virtual const GRState *EnterStackFrame(const GRState *state, - const StackFrameContext *frame) { - return state; - } + virtual Store EnterStackFrame(const GRState *state, + const StackFrameContext *frame); virtual void print(Store store, llvm::raw_ostream& Out, const char* nl, const char *sep) = 0; diff --git a/include/clang/Checker/PathSensitive/SymbolManager.h b/include/clang/Checker/PathSensitive/SymbolManager.h index ffbd289..26ed0c1 100644 --- a/include/clang/Checker/PathSensitive/SymbolManager.h +++ b/include/clang/Checker/PathSensitive/SymbolManager.h @@ -40,6 +40,7 @@ class SymExpr : public llvm::FoldingSetNode { public: enum Kind { BEGIN_SYMBOLS, RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, + MetadataKind, END_SYMBOLS, SymIntKind, SymSymKind }; private: @@ -190,6 +191,9 @@ public: } }; +/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. +/// Clients should not ask the SymbolManager for a region's extent. Always use +/// SubRegion::getExtent instead -- the value returned may not be a symbol. class SymbolExtent : public SymbolData { const SubRegion *R; @@ -218,6 +222,51 @@ public: } }; +/// SymbolMetadata - Represents path-dependent metadata about a specific region. +/// Metadata symbols remain live as long as they are marked as in use before +/// dead-symbol sweeping AND their associated regions are still alive. +/// Intended for use by checkers. +class SymbolMetadata : public SymbolData { + const MemRegion* R; + const Stmt* S; + QualType T; + unsigned Count; + const void* Tag; +public: + SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt* s, QualType t, + unsigned count, const void* tag) + : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} + + const MemRegion *getRegion() const { return R; } + const Stmt* getStmt() const { return S; } + unsigned getCount() const { return Count; } + const void* getTag() const { return Tag; } + + QualType getType(ASTContext&) const; + + void dumpToStream(llvm::raw_ostream &os) const; + + static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, + const Stmt *S, QualType T, unsigned Count, + const void *Tag) { + profile.AddInteger((unsigned) MetadataKind); + profile.AddPointer(R); + profile.AddPointer(S); + profile.Add(T); + profile.AddInteger(Count); + profile.AddPointer(Tag); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, R, S, T, Count, Tag); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == MetadataKind; + } +}; + // SymIntExpr - Represents symbolic expression like 'x' + 3. class SymIntExpr : public SymExpr { const SymExpr *LHS; @@ -336,6 +385,10 @@ public: const SymbolExtent *getExtentSymbol(const SubRegion *R); + const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt* S, + QualType T, unsigned VisitCount, + const void* SymbolTag = 0); + const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const llvm::APSInt& rhs, QualType t); @@ -359,6 +412,7 @@ class SymbolReaper { typedef llvm::DenseSet<SymbolRef> SetTy; SetTy TheLiving; + SetTy MetadataInUse; SetTy TheDead; const LocationContext *LCtx; const Stmt *Loc; @@ -374,12 +428,24 @@ public: const Stmt *getCurrentStatement() const { return Loc; } bool isLive(SymbolRef sym); - bool isLive(const Stmt *ExprVal) const; - bool isLive(const VarRegion *VR) const; - + + // markLive - Unconditionally marks a symbol as live. This should never be + // used by checkers, only by the state infrastructure such as the store and + // environment. Checkers should instead use metadata symbols and markInUse. void markLive(SymbolRef sym); + + // markInUse - Marks a symbol as important to a checker. For metadata symbols, + // this will keep the symbol alive as long as its associated region is also + // live. For other symbols, this has no effect; checkers are not permitted + // to influence the life of other symbols. This should be used before any + // symbol marking has occurred, i.e. in the MarkLiveSymbols callback. + void markInUse(SymbolRef sym); + + // maybeDead - If a symbol is known to be live, marks the symbol as live. + // Otherwise, if the symbol cannot be proven live, it is marked as dead. + // Returns true if the symbol is dead, false if live. bool maybeDead(SymbolRef sym); typedef SetTy::const_iterator dead_iterator; @@ -389,6 +455,13 @@ public: bool hasDeadSymbols() const { return !TheDead.empty(); } + + /// isDead - Returns whether or not a symbol has been confirmed dead. This + /// should only be called once all marking of dead symbols has completed. + /// (For checkers, this means only in the EvalDeadSymbols callback.) + bool isDead(SymbolRef sym) const { + return TheDead.count(sym); + } }; class SymbolVisitor { diff --git a/include/clang/Checker/PathSensitive/ValueManager.h b/include/clang/Checker/PathSensitive/ValueManager.h index 5a9d54d..b81e9c1 100644 --- a/include/clang/Checker/PathSensitive/ValueManager.h +++ b/include/clang/Checker/PathSensitive/ValueManager.h @@ -106,6 +106,9 @@ public: DefinedOrUnknownSVal getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, const TypedRegion *R); + DefinedSVal getMetadataSymbolVal(const void *SymbolTag, const MemRegion *MR, + const Expr *E, QualType T, unsigned Count); + DefinedSVal getFunctionPointer(const FunctionDecl *FD); DefinedSVal getBlockPointer(const BlockDecl *BD, CanQualType locTy, |
