diff options
Diffstat (limited to 'include/clang/StaticAnalyzer/Core/PathSensitive')
22 files changed, 1097 insertions, 1033 deletions
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h index 1ba038e6da2d..6c93f59d2094 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h @@ -16,6 +16,7 @@ #define LLVM_CLANG_GR_ANALYSISMANAGER_H #include "clang/Analysis/AnalysisContext.h" +#include "clang/Frontend/AnalyzerOptions.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" @@ -34,10 +35,10 @@ class AnalysisManager : public BugReporterData { LocationContextManager LocCtxMgr; ASTContext &Ctx; - Diagnostic &Diags; + DiagnosticsEngine &Diags; const LangOptions &LangInfo; - llvm::OwningPtr<PathDiagnosticClient> PD; + llvm::OwningPtr<PathDiagnosticConsumer> PD; // Configurable components creators. StoreManagerCreator CreateStoreMgr; @@ -60,7 +61,7 @@ class AnalysisManager : public BugReporterData { bool VisualizeEGDot; bool VisualizeEGUbi; - bool PurgeDead; + AnalysisPurgeMode PurgeDead; /// EargerlyAssume - A flag indicating how the engine should handle // expressions such as: 'x = (y != 0)'. When this flag is true then @@ -75,27 +76,24 @@ class AnalysisManager : public BugReporterData { bool EagerlyTrimEGraph; public: - AnalysisManager(ASTContext &ctx, Diagnostic &diags, - const LangOptions &lang, PathDiagnosticClient *pd, + AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags, + const LangOptions &lang, PathDiagnosticConsumer *pd, StoreManagerCreator storemgr, ConstraintManagerCreator constraintmgr, CheckerManager *checkerMgr, idx::Indexer *idxer, unsigned maxnodes, unsigned maxvisit, - bool vizdot, bool vizubi, bool purge, bool eager, bool trim, + bool vizdot, bool vizubi, AnalysisPurgeMode purge, + bool eager, bool trim, bool inlinecall, bool useUnoptimizedCFG, bool addImplicitDtors, bool addInitializers, - bool eagerlyTrimEGraph) - - : AnaCtxMgr(useUnoptimizedCFG, addImplicitDtors, addInitializers), - Ctx(ctx), Diags(diags), LangInfo(lang), PD(pd), - CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr), - CheckerMgr(checkerMgr), Idxer(idxer), - AScope(ScopeDecl), MaxNodes(maxnodes), MaxVisit(maxvisit), - VisualizeEGDot(vizdot), VisualizeEGUbi(vizubi), PurgeDead(purge), - EagerlyAssume(eager), TrimGraph(trim), InlineCall(inlinecall), - EagerlyTrimEGraph(eagerlyTrimEGraph) {} - + bool eagerlyTrimEGraph); + + /// Construct a clone of the given AnalysisManager with the given ASTContext + /// and DiagnosticsEngine. + AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags, + AnalysisManager &ParentAM); + ~AnalysisManager() { FlushDiagnostics(); } void ClearContexts() { @@ -127,7 +125,7 @@ public: return getASTContext().getSourceManager(); } - virtual Diagnostic &getDiagnostic() { + virtual DiagnosticsEngine &getDiagnostic() { return Diags; } @@ -135,7 +133,7 @@ public: return LangInfo; } - virtual PathDiagnosticClient *getPathDiagnosticClient() { + virtual PathDiagnosticConsumer *getPathDiagnosticConsumer() { return PD.get(); } @@ -160,7 +158,7 @@ public: bool shouldTrimGraph() const { return TrimGraph; } - bool shouldPurgeDead() const { return PurgeDead; } + AnalysisPurgeMode getPurgeMode() const { return PurgeDead; } bool shouldEagerlyAssume() const { return EagerlyAssume; } @@ -174,8 +172,9 @@ public: return AnaCtxMgr.getContext(D)->getCFG(); } - LiveVariables *getLiveVariables(Decl const *D) { - return AnaCtxMgr.getContext(D)->getLiveVariables(); + template <typename T> + T *getAnalysis(Decl const *D) { + return AnaCtxMgr.getContext(D)->getAnalysis<T>(); } ParentMap &getParentMap(Decl const *D) { diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h b/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h index 69495be400a3..42a15370a427 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h @@ -27,7 +27,7 @@ namespace clang { namespace ento { - class GRState; +class ProgramState; class CompoundValData : public llvm::FoldingSetNode { QualType T; @@ -49,17 +49,17 @@ public: class LazyCompoundValData : public llvm::FoldingSetNode { StoreRef store; - const TypedRegion *region; + const TypedValueRegion *region; public: - LazyCompoundValData(const StoreRef &st, const TypedRegion *r) + LazyCompoundValData(const StoreRef &st, const TypedValueRegion *r) : store(st), region(r) {} const void *getStore() const { return store.getStore(); } - const TypedRegion *getRegion() const { return region; } + const TypedValueRegion *getRegion() const { return region; } static void Profile(llvm::FoldingSetNodeID& ID, const StoreRef &store, - const TypedRegion *region); + const TypedValueRegion *region); void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, store, region); } }; @@ -68,25 +68,25 @@ class BasicValueFactory { typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt> > APSIntSetTy; - ASTContext& Ctx; + ASTContext &Ctx; llvm::BumpPtrAllocator& BPAlloc; APSIntSetTy APSIntSet; - void* PersistentSVals; - void* PersistentSValPairs; + void * PersistentSVals; + void * PersistentSValPairs; llvm::ImmutableList<SVal>::Factory SValListFactory; llvm::FoldingSet<CompoundValData> CompoundValDataSet; llvm::FoldingSet<LazyCompoundValData> LazyCompoundValDataSet; public: - BasicValueFactory(ASTContext& ctx, llvm::BumpPtrAllocator& Alloc) + BasicValueFactory(ASTContext &ctx, llvm::BumpPtrAllocator& Alloc) : Ctx(ctx), BPAlloc(Alloc), PersistentSVals(0), PersistentSValPairs(0), SValListFactory(Alloc) {} ~BasicValueFactory(); - ASTContext& getContext() const { return Ctx; } + ASTContext &getContext() const { return Ctx; } const llvm::APSInt& getValue(const llvm::APSInt& X); const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned); @@ -176,7 +176,7 @@ public: llvm::ImmutableList<SVal> Vals); const LazyCompoundValData *getLazyCompoundValData(const StoreRef &store, - const TypedRegion *region); + const TypedValueRegion *region); llvm::ImmutableList<SVal> getEmptySValList() { return SValListFactory.getEmptyList(); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h b/include/clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h index 7d0fdfb5f11f..2483a79455b2 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h @@ -26,10 +26,13 @@ class StackFrameContext; namespace ento { +/// \class BlockCounter +/// \brief An abstract data type used to count the number of times a given +/// block has been visited along a path analyzed by CoreEngine. class BlockCounter { - void* Data; + void *Data; - BlockCounter(void* D) : Data(D) {} + BlockCounter(void *D) : Data(D) {} public: BlockCounter() : Data(0) {} @@ -38,7 +41,7 @@ public: unsigned BlockID) const; class Factory { - void* F; + void *F; public: Factory(llvm::BumpPtrAllocator& Alloc); ~Factory(); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h index 4429c6b2a7ad..1f1478713260 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h @@ -28,26 +28,29 @@ class CheckerContext { ExprEngine &Eng; ExplodedNode *Pred; SaveAndRestore<bool> OldSink; - const void *checkerTag; - SaveAndRestore<ProgramPoint::Kind> OldPointKind; SaveOr OldHasGen; - const GRState *ST; - const Stmt *statement; + const ProgramPoint Location; + const ProgramState *ST; const unsigned size; public: bool *respondsToCallback; public: - CheckerContext(ExplodedNodeSet &dst, StmtNodeBuilder &builder, - ExprEngine &eng, ExplodedNode *pred, - const void *tag, ProgramPoint::Kind K, + CheckerContext(ExplodedNodeSet &dst, + StmtNodeBuilder &builder, + ExprEngine &eng, + ExplodedNode *pred, + const ProgramPoint &loc, bool *respondsToCB = 0, - const Stmt *stmt = 0, const GRState *st = 0) - : Dst(dst), B(builder), Eng(eng), Pred(pred), + const ProgramState *st = 0) + : Dst(dst), + B(builder), + Eng(eng), + Pred(pred), OldSink(B.BuildSinks), - checkerTag(tag), - OldPointKind(B.PointKind, K), OldHasGen(B.hasGeneratedNode), - ST(st), statement(stmt), size(Dst.size()), + Location(loc), + ST(st), + size(Dst.size()), respondsToCallback(respondsToCB) {} ~CheckerContext(); @@ -69,10 +72,12 @@ public: } ExplodedNodeSet &getNodeSet() { return Dst; } - StmtNodeBuilder &getNodeBuilder() { return B; } ExplodedNode *&getPredecessor() { return Pred; } - const GRState *getState() { return ST ? ST : B.GetState(Pred); } - const Stmt *getStmt() const { return statement; } + const ProgramState *getState() { return ST ? ST : Pred->getState(); } + + /// \brief Returns the number of times the current block has been visited + /// along the analyzed path. + unsigned getCurrentBlockCount() {return B.getCurrentBlockCount();} ASTContext &getASTContext() { return Eng.getContext(); @@ -90,64 +95,58 @@ public: return Eng.getSValBuilder(); } - ExplodedNode *generateNode(bool autoTransition = true) { - assert(statement && "Only transitions with statements currently supported"); - ExplodedNode *N = generateNodeImpl(statement, getState(), false, - checkerTag); - if (N && autoTransition) - Dst.Add(N); - return N; + SymbolManager &getSymbolManager() { + return getSValBuilder().getSymbolManager(); } - - ExplodedNode *generateNode(const Stmt *stmt, const GRState *state, - bool autoTransition = true, const void *tag = 0) { - assert(state); - ExplodedNode *N = generateNodeImpl(stmt, state, false, - tag ? tag : checkerTag); - if (N && autoTransition) - addTransition(N); - return N; + + bool isObjCGCEnabled() { + return Eng.isObjCGCEnabled(); } - ExplodedNode *generateNode(const GRState *state, ExplodedNode *pred, + /// \brief Generate a default checker node (containing checker tag but no + /// checker state changes). + ExplodedNode *generateNode(bool autoTransition = true) { + return generateNode(getState(), autoTransition); + } + + /// \brief Generate a new checker node with the given predecessor. + /// Allows checkers to generate a chain of nodes. + ExplodedNode *generateNode(const ProgramState *state, + ExplodedNode *pred, + const ProgramPointTag *tag = 0, bool autoTransition = true) { - assert(statement && "Only transitions with statements currently supported"); - ExplodedNode *N = generateNodeImpl(statement, state, pred, false); + ExplodedNode *N = generateNodeImpl(state, false, pred, tag); if (N && autoTransition) addTransition(N); return N; } - ExplodedNode *generateNode(const GRState *state, bool autoTransition = true, - const void *tag = 0) { - assert(statement && "Only transitions with statements currently supported"); - ExplodedNode *N = generateNodeImpl(statement, state, false, - tag ? tag : checkerTag); + /// \brief Generate a new checker node. + ExplodedNode *generateNode(const ProgramState *state, + bool autoTransition = true, + const ProgramPointTag *tag = 0) { + ExplodedNode *N = generateNodeImpl(state, false, 0, tag); if (N && autoTransition) addTransition(N); return N; } - ExplodedNode *generateSink(const Stmt *stmt, const GRState *state = 0) { - return generateNodeImpl(stmt, state ? state : getState(), true, - checkerTag); - } - - ExplodedNode *generateSink(const GRState *state = 0) { - assert(statement && "Only transitions with statements currently supported"); - return generateNodeImpl(statement, state ? state : getState(), true, - checkerTag); + /// \brief Generate a sink node. Generating sink stops exploration of the + /// given path. + ExplodedNode *generateSink(const ProgramState *state = 0) { + return generateNodeImpl(state ? state : getState(), true); } void addTransition(ExplodedNode *node) { Dst.Add(node); } - void addTransition(const GRState *state, const void *tag = 0) { + void addTransition(const ProgramState *state, + const ProgramPointTag *tag = 0) { assert(state); // If the 'state' is not new, we need to check if the cached state 'ST' // is new. - if (state != getState() || (ST && ST != B.GetState(Pred))) + if (state != getState() || (ST && ST != Pred->getState())) // state is new or equals to ST. generateNode(state, true, tag); else @@ -163,17 +162,14 @@ public: } private: - ExplodedNode *generateNodeImpl(const Stmt* stmt, const GRState *state, - bool markAsSink, const void *tag) { - ExplodedNode *node = B.generateNode(stmt, state, Pred, tag); - if (markAsSink && node) - node->markAsSink(); - return node; - } - - ExplodedNode *generateNodeImpl(const Stmt* stmt, const GRState *state, - ExplodedNode *pred, bool markAsSink) { - ExplodedNode *node = B.generateNode(stmt, state, pred, checkerTag); + ExplodedNode *generateNodeImpl(const ProgramState *state, + bool markAsSink, + ExplodedNode *pred = 0, + const ProgramPointTag *tag = 0) { + + ExplodedNode *node = B.generateNode(tag ? Location.withTag(tag) : Location, + state, + pred ? pred : Pred); if (markAsSink && node) node->markAsSink(); return node; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h index 199b41afefae..3f6dddead8e9 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h @@ -14,8 +14,8 @@ #ifndef LLVM_CLANG_GR_CONSTRAINT_MANAGER_H #define LLVM_CLANG_GR_CONSTRAINT_MANAGER_H -// FIXME: Typedef LiveSymbolsTy/DeadSymbolsTy at a more appropriate place. -#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" namespace llvm { class APSInt; @@ -25,36 +25,40 @@ namespace clang { namespace ento { -class GRState; -class GRStateManager; +class ProgramState; +class ProgramStateManager; class SubEngine; -class SVal; class ConstraintManager { public: virtual ~ConstraintManager(); - virtual const GRState *assume(const GRState *state, DefinedSVal Cond, - bool Assumption) = 0; + virtual const ProgramState *assume(const ProgramState *state, + DefinedSVal Cond, + bool Assumption) = 0; - std::pair<const GRState*, const GRState*> assumeDual(const GRState *state, - DefinedSVal Cond) { + std::pair<const ProgramState*, const ProgramState*> + assumeDual(const ProgramState *state, DefinedSVal Cond) + { return std::make_pair(assume(state, Cond, true), assume(state, Cond, false)); } - virtual const llvm::APSInt* getSymVal(const GRState *state, + virtual const llvm::APSInt* getSymVal(const ProgramState *state, SymbolRef sym) const = 0; - virtual bool isEqual(const GRState *state, SymbolRef sym, + virtual bool isEqual(const ProgramState *state, + SymbolRef sym, const llvm::APSInt& V) const = 0; - virtual const GRState *removeDeadBindings(const GRState *state, - SymbolReaper& SymReaper) = 0; + virtual const ProgramState *removeDeadBindings(const ProgramState *state, + SymbolReaper& SymReaper) = 0; - virtual void print(const GRState *state, llvm::raw_ostream& Out, - const char* nl, const char *sep) = 0; + virtual void print(const ProgramState *state, + raw_ostream &Out, + const char* nl, + const char *sep) = 0; - virtual void EndPath(const GRState *state) {} + virtual void EndPath(const ProgramState *state) {} /// canReasonAbout - Not all ConstraintManagers can accurately reason about /// all SVal values. This method returns true if the ConstraintManager can @@ -64,9 +68,9 @@ public: virtual bool canReasonAbout(SVal X) const = 0; }; -ConstraintManager* CreateBasicConstraintManager(GRStateManager& statemgr, +ConstraintManager* CreateBasicConstraintManager(ProgramStateManager& statemgr, SubEngine &subengine); -ConstraintManager* CreateRangeConstraintManager(GRStateManager& statemgr, +ConstraintManager* CreateRangeConstraintManager(ProgramStateManager& statemgr, SubEngine &subengine); } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 2c1d07c59b68..131d39e75528 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -19,11 +19,12 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" #include "llvm/ADT/OwningPtr.h" namespace clang { +class ProgramPointTag; + namespace ento { //===----------------------------------------------------------------------===// @@ -77,16 +78,17 @@ private: /// usually because it could not reason about something. BlocksAborted blocksAborted; - void generateNode(const ProgramPoint& Loc, const GRState* State, - ExplodedNode* Pred); + void generateNode(const ProgramPoint &Loc, + const ProgramState *State, + ExplodedNode *Pred); - void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred); - void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred); - void HandleBlockExit(const CFGBlock* B, ExplodedNode* Pred); - void HandlePostStmt(const CFGBlock* B, unsigned StmtIdx, ExplodedNode *Pred); + void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); + void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); + void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); + void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); - void HandleBranch(const Stmt* Cond, const Stmt* Term, const CFGBlock* B, - ExplodedNode* Pred); + 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); void HandleCallExit(const CallExit &L, ExplodedNode *Pred); @@ -124,9 +126,10 @@ 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, - const GRState *InitState); - void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, - const GRState *InitState, + const ProgramState *InitState); + void ExecuteWorkListWithInitialState(const LocationContext *L, + unsigned Steps, + const ProgramState *InitState, ExplodedNodeSet &Dst); // Functions for external checking of whether we have unfinished work @@ -160,41 +163,36 @@ public: class StmtNodeBuilder { CoreEngine& Eng; - const CFGBlock& B; + const CFGBlock &B; const unsigned Idx; - ExplodedNode* Pred; - GRStateManager& Mgr; + ExplodedNode *Pred; + public: bool PurgingDeadSymbols; bool BuildSinks; bool hasGeneratedNode; ProgramPoint::Kind PointKind; - const void *Tag; - - const GRState* CleanedState; - + const ProgramPointTag *Tag; typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; DeferredTy Deferred; - void GenerateAutoTransition(ExplodedNode* N); + void GenerateAutoTransition(ExplodedNode *N); public: - StmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N, - CoreEngine* e, GRStateManager &mgr); + StmtNodeBuilder(const CFGBlock *b, + unsigned idx, + ExplodedNode *N, + CoreEngine* e); ~StmtNodeBuilder(); - ExplodedNode* getPredecessor() const { return Pred; } + ExplodedNode *getPredecessor() const { return Pred; } // FIXME: This should not be exposed. WorkList *getWorkList() { return Eng.WList; } - void SetCleanedState(const GRState* St) { - CleanedState = St; - } - BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} unsigned getCurrentBlockCount() const { @@ -203,14 +201,11 @@ public: B.getBlockID()); } - ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) { - hasGeneratedNode = true; - return generateNodeInternal(PP, St, Pred); - } - - ExplodedNode* generateNode(const Stmt *S, const GRState *St, - ExplodedNode *Pred, ProgramPoint::Kind K, - const void *tag = 0) { + ExplodedNode *generateNode(const Stmt *S, + const ProgramState *St, + ExplodedNode *Pred, + ProgramPoint::Kind K, + const ProgramPointTag *tag = 0) { hasGeneratedNode = true; if (PurgingDeadSymbols) @@ -219,59 +214,65 @@ public: return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); } - ExplodedNode* generateNode(const Stmt *S, const GRState *St, - ExplodedNode *Pred, const void *tag = 0) { + ExplodedNode *generateNode(const Stmt *S, + const ProgramState *St, + ExplodedNode *Pred, + const ProgramPointTag *tag = 0) { return generateNode(S, St, Pred, PointKind, tag); } - ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State, - ExplodedNode* Pred) { + ExplodedNode *generateNode(const ProgramPoint &PP, + const ProgramState *State, + ExplodedNode *Pred) { hasGeneratedNode = true; return generateNodeInternal(PP, State, Pred); } ExplodedNode* - generateNodeInternal(const ProgramPoint &PP, const GRState* State, - ExplodedNode* Pred); + generateNodeInternal(const ProgramPoint &PP, + const ProgramState *State, + ExplodedNode *Pred); ExplodedNode* - generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred, - ProgramPoint::Kind K = ProgramPoint::PostStmtKind, - const void *tag = 0); + generateNodeInternal(const Stmt *S, + const ProgramState *State, + ExplodedNode *Pred, + ProgramPoint::Kind K, + const ProgramPointTag *tag = 0); /// getStmt - Return the current block-level expression associated with /// this builder. - const Stmt* getStmt() const { + const Stmt *getStmt() const { const CFGStmt *CS = B[Idx].getAs<CFGStmt>(); return CS ? CS->getStmt() : 0; } /// getBlock - Return the CFGBlock associated with the block-level expression /// of this builder. - const CFGBlock* getBlock() const { return &B; } + const CFGBlock *getBlock() const { return &B; } unsigned getIndex() const { return Idx; } - const GRState* GetState(ExplodedNode* Pred) const { - if (Pred == getPredecessor()) - return CleanedState; - else - return Pred->getState(); - } - - ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S, - ExplodedNode* Pred, const GRState* St) { + ExplodedNode *MakeNode(ExplodedNodeSet &Dst, + const Stmt *S, + ExplodedNode *Pred, + const ProgramState *St) { return MakeNode(Dst, S, Pred, St, PointKind); } - ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred, - const GRState* St, ProgramPoint::Kind K); + ExplodedNode *MakeNode(ExplodedNodeSet &Dst, + const Stmt *S, + ExplodedNode *Pred, + const ProgramState *St, + ProgramPoint::Kind K); - ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S, - ExplodedNode* Pred, const GRState* St) { + ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, + const Stmt *S, + ExplodedNode *Pred, + const ProgramState *St) { bool Tmp = BuildSinks; BuildSinks = true; - ExplodedNode* N = MakeNode(Dst, S, Pred, St); + ExplodedNode *N = MakeNode(Dst, S, Pred, St); BuildSinks = Tmp; return N; } @@ -279,12 +280,12 @@ public: class BranchNodeBuilder { CoreEngine& Eng; - const CFGBlock* Src; - const CFGBlock* DstT; - const CFGBlock* DstF; - ExplodedNode* Pred; + const CFGBlock *Src; + const CFGBlock *DstT; + const CFGBlock *DstF; + ExplodedNode *Pred; - typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy; + typedef SmallVector<ExplodedNode*,3> DeferredTy; DeferredTy Deferred; bool GeneratedTrue; @@ -293,25 +294,27 @@ class BranchNodeBuilder { bool InFeasibleFalse; public: - BranchNodeBuilder(const CFGBlock* src, const CFGBlock* dstT, - const CFGBlock* dstF, ExplodedNode* pred, CoreEngine* e) + BranchNodeBuilder(const CFGBlock *src, const CFGBlock *dstT, + const CFGBlock *dstF, ExplodedNode *pred, CoreEngine* e) : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), GeneratedTrue(false), GeneratedFalse(false), InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} ~BranchNodeBuilder(); - ExplodedNode* getPredecessor() const { return Pred; } + ExplodedNode *getPredecessor() const { return Pred; } const ExplodedGraph& getGraph() const { return *Eng.G; } BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} - ExplodedNode* generateNode(const Stmt *Condition, const GRState* State); + /// This function generates a new ExplodedNode but not a new + /// branch(block edge). + ExplodedNode *generateNode(const Stmt *Condition, const ProgramState *State); - ExplodedNode* generateNode(const GRState* State, bool branch); + ExplodedNode *generateNode(const ProgramState *State, bool branch); - const CFGBlock* getTargetBlock(bool branch) const { + const CFGBlock *getTargetBlock(bool branch) const { return branch ? DstT : DstF; } @@ -326,21 +329,21 @@ public: return branch ? !InFeasibleTrue : !InFeasibleFalse; } - const GRState* getState() const { + const ProgramState *getState() const { return getPredecessor()->getState(); } }; class IndirectGotoNodeBuilder { CoreEngine& Eng; - const CFGBlock* Src; - const CFGBlock& DispatchBlock; - const Expr* E; - ExplodedNode* Pred; + const CFGBlock *Src; + const CFGBlock &DispatchBlock; + const Expr *E; + ExplodedNode *Pred; public: - IndirectGotoNodeBuilder(ExplodedNode* pred, const CFGBlock* src, - const Expr* e, const CFGBlock* dispatch, CoreEngine* eng) + IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, + const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} class iterator { @@ -350,8 +353,8 @@ public: iterator(CFGBlock::const_succ_iterator i) : I(i) {} public: - iterator& operator++() { ++I; return *this; } - bool operator!=(const iterator& X) const { return I != X.I; } + iterator &operator++() { ++I; return *this; } + bool operator!=(const iterator &X) const { return I != X.I; } const LabelDecl *getLabel() const { return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl(); @@ -365,23 +368,24 @@ public: iterator begin() { return iterator(DispatchBlock.succ_begin()); } iterator end() { return iterator(DispatchBlock.succ_end()); } - ExplodedNode* generateNode(const iterator& I, const GRState* State, + ExplodedNode *generateNode(const iterator &I, + const ProgramState *State, bool isSink = false); - const Expr* getTarget() const { return E; } + const Expr *getTarget() const { return E; } - const GRState* getState() const { return Pred->State; } + const ProgramState *getState() const { return Pred->State; } }; class SwitchNodeBuilder { CoreEngine& Eng; - const CFGBlock* Src; - const Expr* Condition; - ExplodedNode* Pred; + const CFGBlock *Src; + const Expr *Condition; + ExplodedNode *Pred; public: - SwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src, - const Expr* condition, CoreEngine* eng) + SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, + const Expr *condition, CoreEngine* eng) : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} class iterator { @@ -391,15 +395,15 @@ public: iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} public: - iterator& operator++() { ++I; return *this; } + 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; } - const CaseStmt* getCase() const { + const CaseStmt *getCase() const { return llvm::cast<CaseStmt>((*I)->getLabel()); } - const CFGBlock* getBlock() const { + const CFGBlock *getBlock() const { return *I; } }; @@ -411,14 +415,15 @@ public: return llvm::cast<SwitchStmt>(Src->getTerminator()); } - ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State); + ExplodedNode *generateCaseStmtNode(const iterator &I, + const ProgramState *State); - ExplodedNode* generateDefaultCaseNode(const GRState* State, + ExplodedNode *generateDefaultCaseNode(const ProgramState *State, bool isSink = false); - const Expr* getCondition() const { return Condition; } + const Expr *getCondition() const { return Condition; } - const GRState* getState() const { return Pred->State; } + const ProgramState *getState() const { return Pred->State; } }; class GenericNodeBuilderImpl { @@ -426,10 +431,12 @@ protected: CoreEngine &engine; ExplodedNode *pred; ProgramPoint pp; - llvm::SmallVector<ExplodedNode*, 2> sinksGenerated; + SmallVector<ExplodedNode*, 2> sinksGenerated; - ExplodedNode *generateNodeImpl(const GRState *state, ExplodedNode *pred, - ProgramPoint programPoint, bool asSink); + ExplodedNode *generateNodeImpl(const ProgramState *state, + ExplodedNode *pred, + ProgramPoint programPoint, + bool asSink); GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} @@ -439,13 +446,13 @@ public: WorkList &getWorkList() { return *engine.WList; } - ExplodedNode* getPredecessor() const { return pred; } + ExplodedNode *getPredecessor() const { return pred; } BlockCounter getBlockCounter() const { return engine.WList->getBlockCounter(); } - const llvm::SmallVectorImpl<ExplodedNode*> &sinks() const { + const SmallVectorImpl<ExplodedNode*> &sinks() const { return sinksGenerated; } }; @@ -456,8 +463,8 @@ public: GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p) : GenericNodeBuilderImpl(eng, pr, p) {} - ExplodedNode *generateNode(const GRState *state, ExplodedNode *pred, - const void *tag, bool asSink) { + ExplodedNode *generateNode(const ProgramState *state, ExplodedNode *pred, + const ProgramPointTag *tag, bool asSink) { return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), asSink); } @@ -467,27 +474,27 @@ public: class EndOfFunctionNodeBuilder { CoreEngine &Eng; - const CFGBlock& B; - ExplodedNode* Pred; - void *Tag; + const CFGBlock &B; + ExplodedNode *Pred; + const ProgramPointTag *Tag; public: bool hasGeneratedNode; public: - EndOfFunctionNodeBuilder(const CFGBlock* b, ExplodedNode* N, CoreEngine* e, - void *checkerTag = 0) - : Eng(*e), B(*b), Pred(N), Tag(checkerTag), hasGeneratedNode(false) {} + EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, + const ProgramPointTag *tag = 0) + : Eng(*e), B(*b), Pred(N), Tag(tag), hasGeneratedNode(false) {} ~EndOfFunctionNodeBuilder(); - EndOfFunctionNodeBuilder withCheckerTag(void *tag) { + EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); } WorkList &getWorkList() { return *Eng.WList; } - ExplodedNode* getPredecessor() const { return Pred; } + ExplodedNode *getPredecessor() const { return Pred; } BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter(); @@ -499,14 +506,15 @@ public: B.getBlockID()); } - ExplodedNode* generateNode(const GRState* State, ExplodedNode *P = 0, - const void *tag = 0); + ExplodedNode *generateNode(const ProgramState *State, + ExplodedNode *P = 0, + const ProgramPointTag *tag = 0); - void GenerateCallExitNode(const GRState *state); + void GenerateCallExitNode(const ProgramState *state); - const CFGBlock* getBlock() const { return &B; } + const CFGBlock *getBlock() const { return &B; } - const GRState* getState() const { + const ProgramState *getState() const { return getPredecessor()->getState(); } }; @@ -535,7 +543,7 @@ public: const CFGBlock *blk, unsigned idx) : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {} - const GRState *getState() const { return Pred->getState(); } + const ProgramState *getState() const { return Pred->getState(); } const LocationContext *getLocationContext() const { return Pred->getLocationContext(); @@ -549,7 +557,7 @@ public: unsigned getIndex() const { return Index; } - void generateNode(const GRState *state); + void generateNode(const ProgramState *state); }; class CallExitNodeBuilder { @@ -562,9 +570,9 @@ public: const ExplodedNode *getPredecessor() const { return Pred; } - const GRState *getState() const { return Pred->getState(); } + const ProgramState *getState() const { return Pred->getState(); } - void generateNode(const GRState *state); + void generateNode(const ProgramState *state); }; } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h index 193056e6b030..2463e23f5f79 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h @@ -14,7 +14,6 @@ #ifndef LLVM_CLANG_GR_ENVIRONMENT_H #define LLVM_CLANG_GR_ENVIRONMENT_H -#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/ADT/ImmutableMap.h" @@ -43,7 +42,7 @@ private: Environment(BindingsTy eb) : ExprBindings(eb) {} - SVal lookupExpr(const Stmt* E) const; + SVal lookupExpr(const Stmt *E) const; public: typedef BindingsTy::iterator iterator; @@ -53,7 +52,7 @@ public: /// getSVal - Fetches the current binding of the expression in the /// Environment. - SVal getSVal(const Stmt* Ex, SValBuilder& svalBuilder, + SVal getSVal(const Stmt *Ex, SValBuilder& svalBuilder, bool useOnlyDirectBindings = false) const; /// Profile - Profile the contents of an Environment object for use @@ -96,8 +95,7 @@ public: SVal V); Environment removeDeadBindings(Environment Env, - SymbolReaper &SymReaper, const GRState *ST, - llvm::SmallVectorImpl<const MemRegion*>& RegionRoots); + SymbolReaper &SymReaper, const ProgramState *ST); }; } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index e5d6876fa6b2..fdfed3da5403 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -31,7 +31,7 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/Support/Casting.h" #include "clang/Analysis/Support/BumpVector.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" namespace clang { @@ -67,7 +67,7 @@ class ExplodedNode : public llvm::FoldingSetNode { return P & 0x1; } - void* getPtr() const { + void *getPtr() const { assert (!getFlag()); return reinterpret_cast<void*>(P & ~Mask); } @@ -87,7 +87,7 @@ class ExplodedNode : public llvm::FoldingSetNode { bool empty() const { return (P & ~Mask) == 0; } - void addNode(ExplodedNode* N, ExplodedGraph &G); + void addNode(ExplodedNode *N, ExplodedGraph &G); void replaceNode(ExplodedNode *node); @@ -106,7 +106,7 @@ class ExplodedNode : public llvm::FoldingSetNode { const ProgramPoint Location; /// State - The state associated with this node. - const GRState* State; + const ProgramState *State; /// Preds - The predecessors of this node. NodeGroup Preds; @@ -116,13 +116,13 @@ class ExplodedNode : public llvm::FoldingSetNode { public: - explicit ExplodedNode(const ProgramPoint& loc, const GRState* state) + explicit ExplodedNode(const ProgramPoint &loc, const ProgramState *state) : Location(loc), State(state) { - const_cast<GRState*>(State)->incrementReferenceCount(); + const_cast<ProgramState*>(State)->incrementReferenceCount(); } ~ExplodedNode() { - const_cast<GRState*>(State)->decrementReferenceCount(); + const_cast<ProgramState*>(State)->decrementReferenceCount(); } /// getLocation - Returns the edge associated with the given node. @@ -138,17 +138,18 @@ public: ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} - LiveVariables &getLiveVariables() const { - return *getLocationContext()->getLiveVariables(); + template <typename T> + T &getAnalysis() const { + return *getLocationContext()->getAnalysis<T>(); } - const GRState* getState() const { return State; } + const ProgramState *getState() const { return State; } template <typename T> const T* getLocationAs() const { return llvm::dyn_cast<T>(&Location); } static void Profile(llvm::FoldingSetNodeID &ID, - const ProgramPoint& Loc, const GRState* state) { + const ProgramPoint &Loc, const ProgramState *state) { ID.Add(Loc); ID.AddPointer(state); } @@ -159,7 +160,7 @@ public: /// addPredeccessor - Adds a predecessor to the current node, and /// in tandem add this node as a successor of the other node. - void addPredecessor(ExplodedNode* V, ExplodedGraph &G); + void addPredecessor(ExplodedNode *V, ExplodedGraph &G); unsigned succ_size() const { return Succs.size(); } unsigned pred_size() const { return Preds.size(); } @@ -169,11 +170,11 @@ public: bool isSink() const { return Succs.getFlag(); } void markAsSink() { Succs.setFlag(); } - ExplodedNode* getFirstPred() { + ExplodedNode *getFirstPred() { return pred_empty() ? NULL : *(pred_begin()); } - const ExplodedNode* getFirstPred() const { + const ExplodedNode *getFirstPred() const { return const_cast<ExplodedNode*>(this)->getFirstPred(); } @@ -210,7 +211,7 @@ public: class Auditor { public: virtual ~Auditor(); - virtual void AddEdge(ExplodedNode* Src, ExplodedNode* Dst) = 0; + virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; }; static void SetAuditor(Auditor* A); @@ -226,7 +227,7 @@ class InterExplodedGraphMap { friend class ExplodedGraph; public: - ExplodedNode* getMappedNode(const ExplodedNode* N) const; + ExplodedNode *getMappedNode(const ExplodedNode *N) const; InterExplodedGraphMap() {} virtual ~InterExplodedGraphMap() {} @@ -237,8 +238,8 @@ protected: friend class CoreEngine; // Type definitions. - typedef llvm::SmallVector<ExplodedNode*,2> RootsTy; - typedef llvm::SmallVector<ExplodedNode*,10> EndNodesTy; + typedef SmallVector<ExplodedNode*,2> RootsTy; + typedef SmallVector<ExplodedNode*,10> EndNodesTy; /// Roots - The roots of the simulation graph. Usually there will be only /// one, but clients are free to establish multiple subgraphs within a single @@ -275,7 +276,7 @@ public: /// this pair exists, it is created. IsNew is set to true if /// the node was freshly created. - ExplodedNode* getNode(const ProgramPoint& L, const GRState *State, + ExplodedNode *getNode(const ProgramPoint &L, const ProgramState *State, bool* IsNew = 0); ExplodedGraph* MakeEmptyGraph() const { @@ -283,13 +284,13 @@ public: } /// addRoot - Add an untyped node to the set of roots. - ExplodedNode* addRoot(ExplodedNode* V) { + ExplodedNode *addRoot(ExplodedNode *V) { Roots.push_back(V); return V; } /// addEndOfPath - Add an untyped node to the set of EOP nodes. - ExplodedNode* addEndOfPath(ExplodedNode* V) { + ExplodedNode *addEndOfPath(ExplodedNode *V) { EndNodes.push_back(V); return V; } @@ -368,18 +369,18 @@ class ExplodedNodeSet { ImplTy Impl; public: - ExplodedNodeSet(ExplodedNode* N) { + ExplodedNodeSet(ExplodedNode *N) { assert (N && !static_cast<ExplodedNode*>(N)->isSink()); Impl.insert(N); } ExplodedNodeSet() {} - inline void Add(ExplodedNode* N) { + inline void Add(ExplodedNode *N) { if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); } - ExplodedNodeSet& operator=(const ExplodedNodeSet &X) { + ExplodedNodeSet &operator=(const ExplodedNodeSet &X) { Impl = X.Impl; return *this; } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index d24036c0ec28..9bc470fdde60 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -19,9 +19,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/AST/Type.h" #include "clang/AST/ExprObjC.h" @@ -35,6 +33,8 @@ class ObjCForCollectionStmt; namespace ento { class AnalysisManager; +class CallOrObjCMessage; +class ObjCMessage; class ExprEngine : public SubEngine { AnalysisManager &AMgr; @@ -49,7 +49,7 @@ class ExprEngine : public SubEngine { StmtNodeBuilder* Builder; /// StateMgr - Object that manages the data for all created states. - GRStateManager StateMgr; + ProgramStateManager StateMgr; /// SymMgr - Object that manages the symbol information. SymbolManager& SymMgr; @@ -58,31 +58,32 @@ class ExprEngine : public SubEngine { SValBuilder &svalBuilder; /// EntryNode - The immediate predecessor node. - ExplodedNode* EntryNode; + ExplodedNode *EntryNode; /// CleanedState - The state for EntryNode "cleaned" of all dead /// variables and symbols (as determined by a liveness analysis). - const GRState* CleanedState; + const ProgramState *CleanedState; /// currentStmt - The current block-level statement. - const Stmt* currentStmt; + const Stmt *currentStmt; - // Obj-C Class Identifiers. + /// Obj-C Class Identifiers. IdentifierInfo* NSExceptionII; - // Obj-C Selectors. + /// Obj-C Selectors. Selector* NSExceptionInstanceRaiseSelectors; Selector RaiseSel; + + /// Whether or not GC is enabled in this analysis. + bool ObjCGCEnabled; /// The BugReporter associated with this engine. It is important that /// this object be placed at the very end of member variables so that its /// destructor is called before the rest of the ExprEngine is destroyed. GRBugReporter BR; - - llvm::OwningPtr<TransferFuncs> TF; public: - ExprEngine(AnalysisManager &mgr, TransferFuncs *tf); + ExprEngine(AnalysisManager &mgr, bool gcEnabled); ~ExprEngine(); @@ -94,13 +95,13 @@ public: /// 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, + const ProgramState *InitState, ExplodedNodeSet &Dst) { Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst); } /// getContext - Return the ASTContext associated with this analysis. - ASTContext& getContext() const { return AMgr.getASTContext(); } + ASTContext &getContext() const { return AMgr.getASTContext(); } virtual AnalysisManager &getAnalysisManager() { return AMgr; } @@ -110,14 +111,11 @@ public: SValBuilder &getSValBuilder() { return svalBuilder; } - TransferFuncs& getTF() { return *TF; } - BugReporter& getBugReporter() { return BR; } StmtNodeBuilder &getBuilder() { assert(Builder); return *Builder; } - // FIXME: Remove once TransferFuncs is no longer referenced. - void setTransferFunction(TransferFuncs* tf); + bool isObjCGCEnabled() { return ObjCGCEnabled; } /// ViewGraph - Visualize the ExplodedGraph created by executing the /// simulation. @@ -127,7 +125,7 @@ public: /// getInitialState - Return the initial state used for the root vertex /// in the ExplodedGraph. - const GRState* getInitialState(const LocationContext *InitLoc); + const ProgramState *getInitialState(const LocationContext *InitLoc); ExplodedGraph& getGraph() { return G; } const ExplodedGraph& getGraph() const { return G; } @@ -155,7 +153,7 @@ public: /// ProcessBranch - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a branch condition. - void processBranch(const Stmt* Condition, const Stmt* Term, + void processBranch(const Stmt *Condition, const Stmt *Term, BranchNodeBuilder& builder); /// processIndirectGoto - Called by CoreEngine. Used to generate successor @@ -181,21 +179,25 @@ 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 ProgramState *processAssume(const ProgramState *state, SVal cond,bool assumption); - /// wantsRegionChangeUpdate - Called by GRStateManager to determine if a + /// wantsRegionChangeUpdate - Called by ProgramStateManager to determine if a /// region change should trigger a processRegionChanges update. - bool wantsRegionChangeUpdate(const GRState* state); + bool wantsRegionChangeUpdate(const ProgramState *state); - /// processRegionChanges - Called by GRStateManager whenever a change is made + /// processRegionChanges - Called by ProgramStateManager whenever a change is made /// to the store. Used to update checkers that track region values. - const GRState * - processRegionChanges(const GRState *state, + const ProgramState * + processRegionChanges(const ProgramState *state, const StoreManager::InvalidatedSymbols *invalidated, - const MemRegion * const *Begin, - const MemRegion * const *End); + ArrayRef<const MemRegion *> ExplicitRegions, + ArrayRef<const MemRegion *> Regions); - virtual GRStateManager& getStateManager() { return StateMgr; } + /// printState - Called by ProgramStateManager to print checker-specific data. + void printState(raw_ostream &Out, const ProgramState *State, + const char *NL, const char *Sep); + + virtual ProgramStateManager& getStateManager() { return StateMgr; } StoreManager& getStoreManager() { return StateMgr.getStoreManager(); } @@ -222,124 +224,109 @@ public: const CoreEngine &getCoreEngine() const { return Engine; } -protected: - const GRState* GetState(ExplodedNode* N) { - return N == EntryNode ? CleanedState : N->getState(); - } - public: - ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S, - ExplodedNode* Pred, const GRState* St, + ExplodedNode *MakeNode(ExplodedNodeSet &Dst, const Stmt *S, + ExplodedNode *Pred, const ProgramState *St, ProgramPoint::Kind K = ProgramPoint::PostStmtKind, - const void *tag = 0); + const ProgramPointTag *tag = 0); /// Visit - Transfer function logic for all statements. Dispatches to /// other functions that handle specific kinds of statements. - void Visit(const Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst); + void Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst); /// VisitArraySubscriptExpr - Transfer function for array accesses. - void VisitLvalArraySubscriptExpr(const ArraySubscriptExpr* Ex, - ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *Ex, + ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitAsmStmt - Transfer function logic for inline asm. - void VisitAsmStmt(const AsmStmt* A, ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, ExplodedNodeSet &Dst); - void VisitAsmStmtHelperOutputs(const AsmStmt* A, + void VisitAsmStmtHelperOutputs(const AsmStmt *A, AsmStmt::const_outputs_iterator I, AsmStmt::const_outputs_iterator E, - ExplodedNode* Pred, ExplodedNodeSet& Dst); + ExplodedNode *Pred, ExplodedNodeSet &Dst); - void VisitAsmStmtHelperInputs(const AsmStmt* A, + void VisitAsmStmtHelperInputs(const AsmStmt *A, AsmStmt::const_inputs_iterator I, AsmStmt::const_inputs_iterator E, - ExplodedNode* Pred, ExplodedNodeSet& Dst); + ExplodedNode *Pred, ExplodedNodeSet &Dst); /// VisitBlockExpr - Transfer function logic for BlockExprs. void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, ExplodedNodeSet &Dst); /// VisitBinaryOperator - Transfer function logic for binary operators. - void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitCall - Transfer function for function calls. - void VisitCallExpr(const CallExpr* CE, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitCast - Transfer function logic for all casts (implicit and explicit). void VisitCast(const CastExpr *CastE, const Expr *Ex, ExplodedNode *Pred, ExplodedNodeSet &Dst); /// VisitCompoundLiteralExpr - Transfer function logic for compound literals. - void VisitCompoundLiteralExpr(const CompoundLiteralExpr* CL, - ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL, + ExplodedNode *Pred, ExplodedNodeSet &Dst); /// Transfer function logic for DeclRefExprs and BlockDeclRefExprs. - void VisitCommonDeclRefExpr(const Expr* DR, const NamedDecl *D, - ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitCommonDeclRefExpr(const Expr *DR, const NamedDecl *D, + ExplodedNode *Pred, ExplodedNodeSet &Dst); /// VisitDeclStmt - Transfer function logic for DeclStmts. - void VisitDeclStmt(const DeclStmt* DS, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose - void VisitGuardedExpr(const Expr* Ex, const Expr* L, const Expr* R, - ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitGuardedExpr(const Expr *Ex, const Expr *L, const Expr *R, + ExplodedNode *Pred, ExplodedNodeSet &Dst); - void VisitInitListExpr(const InitListExpr* E, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitInitListExpr(const InitListExpr *E, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitLogicalExpr - Transfer function logic for '&&', '||' - void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitMemberExpr - Transfer function for member expressions. - void VisitMemberExpr(const MemberExpr* M, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// Transfer function logic for ObjCAtSynchronizedStmts. void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst); - void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *E, - ExplodedNode *Pred, ExplodedNodeSet &Dst); - /// Transfer function logic for computing the lvalue of an Objective-C ivar. - void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr* DR, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitObjCForCollectionStmt - Transfer function logic for /// ObjCForCollectionStmt. - void VisitObjCForCollectionStmt(const ObjCForCollectionStmt* S, - ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S, + ExplodedNode *Pred, ExplodedNodeSet &Dst); - void VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt* S, - ExplodedNode* Pred, - ExplodedNodeSet& Dst, SVal ElementV); - - /// VisitObjCMessageExpr - Transfer function for ObjC message expressions. - void VisitObjCMessageExpr(const ObjCMessageExpr* ME, ExplodedNode* Pred, - ExplodedNodeSet& Dst); - void VisitObjCMessage(const ObjCMessage &msg, ExplodedNodeSet &Src, - ExplodedNodeSet& Dst); + void VisitObjCMessage(const ObjCMessage &msg, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitReturnStmt - Transfer function logic for return statements. - void VisitReturnStmt(const ReturnStmt* R, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitReturnStmt(const ReturnStmt *R, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitOffsetOfExpr - Transfer function for offsetof. - void VisitOffsetOfExpr(const OffsetOfExpr* Ex, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitOffsetOfExpr(const OffsetOfExpr *Ex, ExplodedNode *Pred, + ExplodedNodeSet &Dst); /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof. - void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr* Ex, - ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex, + ExplodedNode *Pred, ExplodedNodeSet &Dst); /// VisitUnaryOperator - Transfer function logic for unary operators. - void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode* Pred, - ExplodedNodeSet& Dst); + void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred, + ExplodedNodeSet &Dst); void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred, ExplodedNodeSet & Dst); @@ -366,7 +353,8 @@ public: ExplodedNodeSet &Dst); /// Create a C++ temporary object for an rvalue. - void CreateCXXTemporaryObject(const Expr *Ex, ExplodedNode *Pred, + void CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME, + ExplodedNode *Pred, ExplodedNodeSet &Dst); /// Synthesize CXXThisRegion. @@ -389,8 +377,11 @@ public: /// 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, + void evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, const Expr *Ex); + + std::pair<const ProgramPointTag *, const ProgramPointTag*> + getEagerlyAssumeTags(); SVal evalMinus(SVal X) { return X.isValid() ? svalBuilder.evalMinus(cast<NonLoc>(X)) : X; @@ -402,36 +393,36 @@ public: public: - SVal evalBinOp(const GRState *state, BinaryOperator::Opcode op, + SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op, NonLoc L, NonLoc R, QualType T) { return svalBuilder.evalBinOpNN(state, op, L, R, T); } - SVal evalBinOp(const GRState *state, BinaryOperator::Opcode op, + SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op, NonLoc L, SVal R, QualType T) { return R.isValid() ? svalBuilder.evalBinOpNN(state,op,L, cast<NonLoc>(R), T) : R; } - SVal evalBinOp(const GRState *ST, BinaryOperator::Opcode Op, + SVal evalBinOp(const ProgramState *ST, BinaryOperator::Opcode Op, SVal LHS, SVal RHS, QualType T) { return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T); } protected: - void evalObjCMessage(ExplodedNodeSet& Dst, const ObjCMessage &msg, - ExplodedNode* Pred, const GRState *state) { - assert (Builder && "StmtNodeBuilder must be defined."); - getTF().evalObjCMessage(Dst, *this, *Builder, msg, Pred, state); - } + void evalObjCMessage(ExplodedNodeSet &Dst, const ObjCMessage &msg, + ExplodedNode *Pred, const ProgramState *state); + + const ProgramState *invalidateArguments(const ProgramState *State, + const CallOrObjCMessage &Call, + const LocationContext *LC); - const GRState* MarkBranch(const GRState* St, const Stmt* Terminator, + const ProgramState *MarkBranch(const ProgramState *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, const Stmt* StoreE, ExplodedNode* Pred, - const GRState* St, SVal location, SVal Val, - bool atDeclInit = false); + void evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred, + SVal location, SVal Val, bool atDeclInit = false); public: // FIXME: 'tag' should be removed, and a LocationContext should be used @@ -440,25 +431,25 @@ public: // be the same as Pred->state, and when 'location' may not be the // same as state->getLValue(Ex). /// Simulate a read of the result of Ex. - void evalLoad(ExplodedNodeSet& Dst, const Expr* Ex, ExplodedNode* Pred, - const GRState* St, SVal location, const void *tag = 0, + void evalLoad(ExplodedNodeSet &Dst, const Expr *Ex, ExplodedNode *Pred, + const ProgramState *St, SVal location, const ProgramPointTag *tag = 0, QualType LoadTy = QualType()); // FIXME: 'tag' should be removed, and a LocationContext should be used // instead. - void evalStore(ExplodedNodeSet& Dst, const Expr* AssignE, const Expr* StoreE, - ExplodedNode* Pred, const GRState* St, SVal TargetLV, SVal Val, - const void *tag = 0); + void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE, + ExplodedNode *Pred, const ProgramState *St, SVal TargetLV, SVal Val, + const ProgramPointTag *tag = 0); private: - void evalLoadCommon(ExplodedNodeSet& Dst, const Expr* Ex, ExplodedNode* Pred, - const GRState* St, SVal location, const void *tag, + void evalLoadCommon(ExplodedNodeSet &Dst, const Expr *Ex, ExplodedNode *Pred, + const ProgramState *St, SVal location, const ProgramPointTag *tag, QualType LoadTy); // FIXME: 'tag' should be removed, and a LocationContext should be used // instead. - void evalLocation(ExplodedNodeSet &Dst, const Stmt *S, ExplodedNode* Pred, - const GRState* St, SVal location, - const void *tag, bool isLoad); + void evalLocation(ExplodedNodeSet &Dst, const Stmt *S, ExplodedNode *Pred, + const ProgramState *St, SVal location, + const ProgramPointTag *tag, bool isLoad); bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h index 18e39d999bb4..89b47dc6ec26 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h @@ -25,9 +25,9 @@ class StmtNodeBuilderRef { ExplodedNodeSet &Dst; StmtNodeBuilder &B; ExprEngine& Eng; - ExplodedNode* Pred; - const GRState* state; - const Stmt* stmt; + ExplodedNode *Pred; + const ProgramState *state; + const Stmt *stmt; const unsigned OldSize; const bool AutoCreateNode; SaveAndRestore<bool> OldSink; @@ -42,9 +42,9 @@ private: StmtNodeBuilderRef(ExplodedNodeSet &dst, StmtNodeBuilder &builder, ExprEngine& eng, - ExplodedNode* pred, - const GRState *st, - const Stmt* s, bool auto_create_node) + ExplodedNode *pred, + const ProgramState *st, + const Stmt *s, bool auto_create_node) : Dst(dst), B(builder), Eng(eng), Pred(pred), state(st), stmt(s), OldSize(Dst.size()), AutoCreateNode(auto_create_node), OldSink(B.BuildSinks), OldHasGen(B.hasGeneratedNode) {} @@ -62,13 +62,13 @@ public: } } - const GRState *getState() { return state; } + const ProgramState *getState() { return state; } - GRStateManager& getStateManager() { + ProgramStateManager& getStateManager() { return Eng.getStateManager(); } - ExplodedNode* MakeNode(const GRState* state) { + ExplodedNode *MakeNode(const ProgramState *state) { return B.MakeNode(Dst, const_cast<Stmt*>(stmt), Pred, state); } }; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h index db7a930b556e..c9941fe90c24 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h @@ -19,15 +19,14 @@ #include "clang/AST/CharUnits.h" #include "clang/AST/Decl.h" #include "clang/AST/DeclObjC.h" +#include "clang/Basic/LLVM.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" -#include "llvm/Support/Casting.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/ADT/FoldingSet.h" #include <string> namespace llvm { class BumpPtrAllocator; -class raw_ostream; } namespace clang { @@ -83,12 +82,13 @@ public: // Untyped regions. SymbolicRegionKind, AllocaRegionKind, + BlockDataRegionKind, // Typed regions. BEG_TYPED_REGIONS, FunctionTextRegionKind = BEG_TYPED_REGIONS, BlockTextRegionKind, - BlockDataRegionKind, - CompoundLiteralRegionKind, + BEG_TYPED_VALUE_REGIONS, + CompoundLiteralRegionKind = BEG_TYPED_VALUE_REGIONS, CXXThisRegionKind, StringRegionKind, ElementRegionKind, @@ -100,6 +100,7 @@ public: END_DECL_REGIONS = ObjCIvarRegionKind, CXXTempObjectRegionKind, CXXBaseObjectRegionKind, + END_TYPED_VALUE_REGIONS = CXXBaseObjectRegionKind, END_TYPED_REGIONS = CXXBaseObjectRegionKind }; @@ -136,7 +137,7 @@ public: /// Compute the offset within the top level memory object. RegionOffset getAsOffset() const; - virtual void dumpToStream(llvm::raw_ostream& os) const; + virtual void dumpToStream(raw_ostream &os) const; void dump() const; @@ -197,7 +198,7 @@ class StaticGlobalSpaceRegion : public GlobalsSpaceRegion { public: void Profile(llvm::FoldingSetNodeID &ID) const; - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; const CodeTextRegion *getCodeRegion() const { return CR; } @@ -214,7 +215,7 @@ class NonStaticGlobalSpaceRegion : public GlobalsSpaceRegion { public: - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; static bool classof(const MemRegion *R) { return R->getKind() == NonStaticGlobalSpaceRegionKind; @@ -323,14 +324,14 @@ class AllocaRegion : public SubRegion { protected: unsigned Cnt; // Block counter. Used to distinguish different pieces of // memory allocated by alloca at the same call site. - const Expr* Ex; + const Expr *Ex; - AllocaRegion(const Expr* ex, unsigned cnt, const MemRegion *superRegion) + AllocaRegion(const Expr *ex, unsigned cnt, const MemRegion *superRegion) : SubRegion(superRegion, AllocaRegionKind), Cnt(cnt), Ex(ex) {} public: - const Expr* getExpr() const { return Ex; } + const Expr *getExpr() const { return Ex; } bool isBoundable() const { return true; } @@ -338,10 +339,10 @@ public: void Profile(llvm::FoldingSetNodeID& ID) const; - static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr* Ex, + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr *Ex, unsigned Cnt, const MemRegion *superRegion); - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; static bool classof(const MemRegion* R) { return R->getKind() == AllocaRegionKind; @@ -354,6 +355,26 @@ protected: TypedRegion(const MemRegion* sReg, Kind k) : SubRegion(sReg, k) {} public: + virtual QualType getLocationType() const = 0; + + QualType getDesugaredLocationType(ASTContext &Context) const { + return getLocationType().getDesugaredType(Context); + } + + bool isBoundable() const { return true; } + + static bool classof(const MemRegion* R) { + unsigned k = R->getKind(); + return k >= BEG_TYPED_REGIONS && k <= END_TYPED_REGIONS; + } +}; + +/// TypedValueRegion - An abstract class representing regions having a typed value. +class TypedValueRegion : public TypedRegion { +protected: + TypedValueRegion(const MemRegion* sReg, Kind k) : TypedRegion(sReg, k) {} + +public: virtual QualType getValueType() const = 0; virtual QualType getLocationType() const { @@ -370,15 +391,9 @@ public: return T.getTypePtrOrNull() ? T.getDesugaredType(Context) : T; } - QualType getDesugaredLocationType(ASTContext &Context) const { - return getLocationType().getDesugaredType(Context); - } - - bool isBoundable() const { return true; } - static bool classof(const MemRegion* R) { unsigned k = R->getKind(); - return k >= BEG_TYPED_REGIONS && k <= END_TYPED_REGIONS; + return k >= BEG_TYPED_VALUE_REGIONS && k <= END_TYPED_VALUE_REGIONS; } }; @@ -387,11 +402,6 @@ class CodeTextRegion : public TypedRegion { protected: CodeTextRegion(const MemRegion *sreg, Kind k) : TypedRegion(sreg, k) {} public: - QualType getValueType() const { - assert(0 && "Do not get the object type of a CodeTextRegion."); - return QualType(); - } - bool isBoundable() const { return false; } static bool classof(const MemRegion* R) { @@ -404,7 +414,7 @@ public: class FunctionTextRegion : public CodeTextRegion { const FunctionDecl *FD; public: - FunctionTextRegion(const FunctionDecl* fd, const MemRegion* sreg) + FunctionTextRegion(const FunctionDecl *fd, const MemRegion* sreg) : CodeTextRegion(sreg, FunctionTextRegionKind), FD(fd) {} QualType getLocationType() const { @@ -415,7 +425,7 @@ public: return FD; } - virtual void dumpToStream(llvm::raw_ostream& os) const; + virtual void dumpToStream(raw_ostream &os) const; void Profile(llvm::FoldingSetNodeID& ID) const; @@ -456,7 +466,7 @@ public: AnalysisContext *getAnalysisContext() const { return AC; } - virtual void dumpToStream(llvm::raw_ostream& os) const; + virtual void dumpToStream(raw_ostream &os) const; void Profile(llvm::FoldingSetNodeID& ID) const; @@ -509,7 +519,7 @@ public: bool operator!=(const referenced_vars_iterator &I) const { return I.R != R; } - referenced_vars_iterator& operator++() { + referenced_vars_iterator &operator++() { ++R; return *this; } @@ -518,7 +528,7 @@ public: referenced_vars_iterator referenced_vars_begin() const; referenced_vars_iterator referenced_vars_end() const; - virtual void dumpToStream(llvm::raw_ostream& os) const; + virtual void dumpToStream(raw_ostream &os) const; void Profile(llvm::FoldingSetNodeID& ID) const; @@ -559,7 +569,7 @@ public: SymbolRef sym, const MemRegion* superRegion); - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; static bool classof(const MemRegion* R) { return R->getKind() == SymbolicRegionKind; @@ -567,13 +577,13 @@ public: }; /// StringRegion - Region associated with a StringLiteral. -class StringRegion : public TypedRegion { +class StringRegion : public TypedValueRegion { friend class MemRegionManager; const StringLiteral* Str; protected: StringRegion(const StringLiteral* str, const MemRegion* sreg) - : TypedRegion(sreg, StringRegionKind), Str(str) {} + : TypedValueRegion(sreg, StringRegionKind), Str(str) {} static void ProfileRegion(llvm::FoldingSetNodeID& ID, const StringLiteral* Str, @@ -595,7 +605,7 @@ public: ProfileRegion(ID, Str, superRegion); } - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; static bool classof(const MemRegion* R) { return R->getKind() == StringRegionKind; @@ -605,16 +615,16 @@ public: /// CompoundLiteralRegion - A memory region representing a compound literal. /// Compound literals are essentially temporaries that are stack allocated /// or in the global constant pool. -class CompoundLiteralRegion : public TypedRegion { +class CompoundLiteralRegion : public TypedValueRegion { private: friend class MemRegionManager; - const CompoundLiteralExpr* CL; + const CompoundLiteralExpr *CL; - CompoundLiteralRegion(const CompoundLiteralExpr* cl, const MemRegion* sReg) - : TypedRegion(sReg, CompoundLiteralRegionKind), CL(cl) {} + CompoundLiteralRegion(const CompoundLiteralExpr *cl, const MemRegion* sReg) + : TypedValueRegion(sReg, CompoundLiteralRegionKind), CL(cl) {} static void ProfileRegion(llvm::FoldingSetNodeID& ID, - const CompoundLiteralExpr* CL, + const CompoundLiteralExpr *CL, const MemRegion* superRegion); public: QualType getValueType() const { @@ -625,27 +635,27 @@ public: void Profile(llvm::FoldingSetNodeID& ID) const; - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; - const CompoundLiteralExpr* getLiteralExpr() const { return CL; } + const CompoundLiteralExpr *getLiteralExpr() const { return CL; } static bool classof(const MemRegion* R) { return R->getKind() == CompoundLiteralRegionKind; } }; -class DeclRegion : public TypedRegion { +class DeclRegion : public TypedValueRegion { protected: - const Decl* D; + const Decl *D; - DeclRegion(const Decl* d, const MemRegion* sReg, Kind k) - : TypedRegion(sReg, k), D(d) {} + DeclRegion(const Decl *d, const MemRegion* sReg, Kind k) + : TypedValueRegion(sReg, k), D(d) {} - static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D, + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D, const MemRegion* superRegion, Kind k); public: - const Decl* getDecl() const { return D; } + const Decl *getDecl() const { return D; } void Profile(llvm::FoldingSetNodeID& ID) const; DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; @@ -660,10 +670,10 @@ class VarRegion : public DeclRegion { friend class MemRegionManager; // Constructors and private methods. - VarRegion(const VarDecl* vd, const MemRegion* sReg) + VarRegion(const VarDecl *vd, const MemRegion* sReg) : DeclRegion(vd, sReg, VarRegionKind) {} - static void ProfileRegion(llvm::FoldingSetNodeID& ID, const VarDecl* VD, + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const VarDecl *VD, const MemRegion *superRegion) { DeclRegion::ProfileRegion(ID, VD, superRegion, VarRegionKind); } @@ -680,7 +690,7 @@ public: return getDecl()->getType(); } - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; static bool classof(const MemRegion* R) { return R->getKind() == VarRegionKind; @@ -690,11 +700,11 @@ public: /// CXXThisRegion - Represents the region for the implicit 'this' parameter /// in a call to a C++ method. This region doesn't represent the object /// referred to by 'this', but rather 'this' itself. -class CXXThisRegion : public TypedRegion { +class CXXThisRegion : public TypedValueRegion { friend class MemRegionManager; CXXThisRegion(const PointerType *thisPointerTy, const MemRegion *sReg) - : TypedRegion(sReg, CXXThisRegionKind), ThisPointerTy(thisPointerTy) {} + : TypedValueRegion(sReg, CXXThisRegionKind), ThisPointerTy(thisPointerTy) {} static void ProfileRegion(llvm::FoldingSetNodeID &ID, const PointerType *PT, @@ -707,7 +717,7 @@ public: return QualType(ThisPointerTy, 0); } - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; static bool classof(const MemRegion* R) { return R->getKind() == CXXThisRegionKind; @@ -720,14 +730,14 @@ private: class FieldRegion : public DeclRegion { friend class MemRegionManager; - FieldRegion(const FieldDecl* fd, const MemRegion* sReg) + FieldRegion(const FieldDecl *fd, const MemRegion* sReg) : DeclRegion(fd, sReg, FieldRegionKind) {} public: - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; - const FieldDecl* getDecl() const { return cast<FieldDecl>(D); } + const FieldDecl *getDecl() const { return cast<FieldDecl>(D); } QualType getValueType() const { // FIXME: We can cache this if needed. @@ -736,7 +746,7 @@ public: DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; - static void ProfileRegion(llvm::FoldingSetNodeID& ID, const FieldDecl* FD, + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const FieldDecl *FD, const MemRegion* superRegion) { DeclRegion::ProfileRegion(ID, FD, superRegion, FieldRegionKind); } @@ -750,19 +760,19 @@ class ObjCIvarRegion : public DeclRegion { friend class MemRegionManager; - ObjCIvarRegion(const ObjCIvarDecl* ivd, const MemRegion* sReg) + ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg) : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {} - static void ProfileRegion(llvm::FoldingSetNodeID& ID, const ObjCIvarDecl* ivd, + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const ObjCIvarDecl *ivd, const MemRegion* superRegion) { DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind); } public: - const ObjCIvarDecl* getDecl() const { return cast<ObjCIvarDecl>(D); } + const ObjCIvarDecl *getDecl() const { return cast<ObjCIvarDecl>(D); } QualType getValueType() const { return getDecl()->getType(); } - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; static bool classof(const MemRegion* R) { return R->getKind() == ObjCIvarRegionKind; @@ -789,18 +799,18 @@ public: CharUnits getOffset() const { return Offset; } const MemRegion *getRegion() const { return Region; } - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; void dump() const; }; -class ElementRegion : public TypedRegion { +class ElementRegion : public TypedValueRegion { friend class MemRegionManager; QualType ElementType; NonLoc Index; ElementRegion(QualType elementType, NonLoc Idx, const MemRegion* sReg) - : TypedRegion(sReg, ElementRegionKind), + : TypedValueRegion(sReg, ElementRegionKind), ElementType(elementType), Index(Idx) { assert((!isa<nonloc::ConcreteInt>(&Idx) || cast<nonloc::ConcreteInt>(&Idx)->getValue().isSigned()) && @@ -824,7 +834,7 @@ public: /// Compute the offset within the array. The array might also be a subobject. RegionRawOffset getAsArrayOffset() const; - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; void Profile(llvm::FoldingSetNodeID& ID) const; @@ -834,23 +844,25 @@ public: }; // C++ temporary object associated with an expression. -class CXXTempObjectRegion : public TypedRegion { +class CXXTempObjectRegion : public TypedValueRegion { friend class MemRegionManager; Expr const *Ex; CXXTempObjectRegion(Expr const *E, MemRegion const *sReg) - : TypedRegion(sReg, CXXTempObjectRegionKind), Ex(E) {} + : TypedValueRegion(sReg, CXXTempObjectRegionKind), Ex(E) {} static void ProfileRegion(llvm::FoldingSetNodeID &ID, Expr const *E, const MemRegion *sReg); public: + const Expr *getExpr() const { return Ex; } + QualType getValueType() const { return Ex->getType(); } - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; void Profile(llvm::FoldingSetNodeID &ID) const; @@ -861,13 +873,13 @@ public: // CXXBaseObjectRegion represents a base object within a C++ object. It is // identified by the base class declaration and the region of its parent object. -class CXXBaseObjectRegion : public TypedRegion { +class CXXBaseObjectRegion : public TypedValueRegion { friend class MemRegionManager; const CXXRecordDecl *decl; CXXBaseObjectRegion(const CXXRecordDecl *d, const MemRegion *sReg) - : TypedRegion(sReg, CXXBaseObjectRegionKind), decl(d) {} + : TypedValueRegion(sReg, CXXBaseObjectRegionKind), decl(d) {} static void ProfileRegion(llvm::FoldingSetNodeID &ID, const CXXRecordDecl *decl, const MemRegion *sReg); @@ -877,7 +889,7 @@ public: QualType getValueType() const; - void dumpToStream(llvm::raw_ostream& os) const; + void dumpToStream(raw_ostream &os) const; void Profile(llvm::FoldingSetNodeID &ID) const; @@ -951,13 +963,13 @@ public: const MemSpaceRegion *getCodeRegion(); /// getAllocaRegion - Retrieve a region associated with a call to alloca(). - const AllocaRegion *getAllocaRegion(const Expr* Ex, unsigned Cnt, + const AllocaRegion *getAllocaRegion(const Expr *Ex, unsigned Cnt, const LocationContext *LC); /// getCompoundLiteralRegion - Retrieve the region associated with a /// given CompoundLiteral. const CompoundLiteralRegion* - getCompoundLiteralRegion(const CompoundLiteralExpr* CL, + getCompoundLiteralRegion(const CompoundLiteralExpr *CL, const LocationContext *LC); /// getCXXThisRegion - Retrieve the [artificial] region associated with the @@ -994,7 +1006,7 @@ public: /// a specified FieldDecl. 'superRegion' corresponds to the containing /// memory region (which typically represents the memory representing /// a structure or class). - const FieldRegion *getFieldRegion(const FieldDecl* fd, + const FieldRegion *getFieldRegion(const FieldDecl *fd, const MemRegion* superRegion); const FieldRegion *getFieldRegionWithSuper(const FieldRegion *FR, @@ -1006,7 +1018,7 @@ public: /// a specified Objective-c instance variable. 'superRegion' corresponds /// to the containing region (which typically represents the Objective-C /// object). - const ObjCIvarRegion *getObjCIvarRegion(const ObjCIvarDecl* ivd, + const ObjCIvarRegion *getObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* superRegion); const CXXTempObjectRegion *getCXXTempObjectRegion(Expr const *Ex, @@ -1069,7 +1081,7 @@ private: // Out-of-line member definitions. //===----------------------------------------------------------------------===// -inline ASTContext& MemRegion::getContext() const { +inline ASTContext &MemRegion::getContext() const { return getMemRegionManager()->getContext(); } @@ -1082,7 +1094,7 @@ inline ASTContext& MemRegion::getContext() const { //===----------------------------------------------------------------------===// namespace llvm { -static inline raw_ostream& operator<<(raw_ostream& os, +static inline raw_ostream &operator<<(raw_ostream &os, const clang::ento::MemRegion* R) { R->dumpToStream(os); return os; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h index 734024c2cba4..add3479804bd 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h @@ -16,8 +16,10 @@ #define LLVM_CLANG_STATICANALYZER_PATHSENSITIVE_OBJCMESSAGE #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/AST/ExprObjC.h" +#include "clang/AST/ExprCXX.h" +#include "llvm/ADT/PointerUnion.h" namespace clang { namespace ento { @@ -86,6 +88,21 @@ public: return 0; } + SVal getInstanceReceiverSVal(const ProgramState *State, + const LocationContext *LC) const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + if (!isInstanceMessage()) + return UndefinedVal(); + if (const Expr *Ex = getInstanceReceiver()) + return State->getSValAsScalarOrLoc(Ex); + + // An instance message with no expression means we are sending to super. + // In this case the object reference is the same as 'self'. + const ImplicitParamDecl *SelfDecl = LC->getSelfDecl(); + assert(SelfDecl && "No message receiver Expr, but not in an ObjC method"); + return State->getSVal(State->getRegion(SelfDecl, LC)); + } + bool isInstanceMessage() const { assert(isValid() && "This ObjCMessage is uninitialized!"); if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) @@ -96,7 +113,7 @@ public: } const ObjCMethodDecl *getMethodDecl() const; - + const ObjCInterfaceDecl *getReceiverInterface() const; SourceLocation getSuperLoc() const { @@ -106,45 +123,63 @@ public: return cast<ObjCPropertyRefExpr>(MsgOrPropE)->getReceiverLocation(); } - SourceRange getSourceRange() const { - assert(isValid() && "This ObjCMessage is uninitialized!"); + const Expr *getMsgOrPropExpr() const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + return MsgOrPropE; + } + + SourceRange getSourceRange() const { + assert(isValid() && "This ObjCMessage is uninitialized!"); return MsgOrPropE->getSourceRange(); } - unsigned getNumArgs() const { - assert(isValid() && "This ObjCMessage is uninitialized!"); - if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) - return msgE->getNumArgs(); - return isPropertySetter() ? 1 : 0; - } - - SVal getArgSVal(unsigned i, const GRState *state) const { - assert(isValid() && "This ObjCMessage is uninitialized!"); - assert(i < getNumArgs() && "Invalid index for argument"); - if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) - return state->getSVal(msgE->getArg(i)); - assert(isPropertySetter()); - return SetterArgV; - } - - QualType getArgType(unsigned i) const { - assert(isValid() && "This ObjCMessage is uninitialized!"); - assert(i < getNumArgs() && "Invalid index for argument"); - if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) - return msgE->getArg(i)->getType(); - assert(isPropertySetter()); - return cast<ObjCPropertyRefExpr>(MsgOrPropE)->getType(); - } - - const Expr *getArgExpr(unsigned i) const; - - SourceRange getArgSourceRange(unsigned i) const { - assert(isValid() && "This ObjCMessage is uninitialized!"); - assert(i < getNumArgs() && "Invalid index for argument"); - if (const Expr *argE = getArgExpr(i)) - return argE->getSourceRange(); - return OriginE->getSourceRange(); - } + unsigned getNumArgs() const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) + return msgE->getNumArgs(); + return isPropertySetter() ? 1 : 0; + } + + SVal getArgSVal(unsigned i, const ProgramState *state) const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + assert(i < getNumArgs() && "Invalid index for argument"); + if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) + return state->getSVal(msgE->getArg(i)); + assert(isPropertySetter()); + return SetterArgV; + } + + QualType getArgType(unsigned i) const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + assert(i < getNumArgs() && "Invalid index for argument"); + if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) + return msgE->getArg(i)->getType(); + assert(isPropertySetter()); + return cast<ObjCPropertyRefExpr>(MsgOrPropE)->getType(); + } + + const Expr *getArgExpr(unsigned i) const; + + SourceRange getArgSourceRange(unsigned i) const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + assert(i < getNumArgs() && "Invalid index for argument"); + if (const Expr *argE = getArgExpr(i)) + return argE->getSourceRange(); + return OriginE->getSourceRange(); + } + + SourceRange getReceiverSourceRange() const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) + return msgE->getReceiverRange(); + + const ObjCPropertyRefExpr *propE = cast<ObjCPropertyRefExpr>(MsgOrPropE); + if (propE->isObjectReceiver()) + return propE->getBase()->getSourceRange(); + + // FIXME: This isn't a range. + return propE->getReceiverLocation(); + } }; class ObjCPropertyGetter : public ObjCMessage { @@ -165,58 +200,89 @@ public: } }; -/// \brief Common wrapper for a call expression or an ObjC message, mainly to -/// provide a common interface for handling their arguments. +/// \brief Common wrapper for a call expression, ObjC message, or C++ +/// constructor, mainly to provide a common interface for their arguments. class CallOrObjCMessage { - const CallExpr *CallE; + llvm::PointerUnion<const CallExpr *, const CXXConstructExpr *> CallE; ObjCMessage Msg; - const GRState *State; + const ProgramState *State; public: - CallOrObjCMessage(const CallExpr *callE, const GRState *state) + CallOrObjCMessage(const CallExpr *callE, const ProgramState *state) : CallE(callE), State(state) {} - CallOrObjCMessage(const ObjCMessage &msg, const GRState *state) - : CallE(0), Msg(msg), State(state) {} + CallOrObjCMessage(const CXXConstructExpr *consE, const ProgramState *state) + : CallE(consE), State(state) {} + CallOrObjCMessage(const ObjCMessage &msg, const ProgramState *state) + : CallE((CallExpr *)0), Msg(msg), State(state) {} QualType getResultType(ASTContext &ctx) const; bool isFunctionCall() const { - return (bool) CallE; + return CallE && CallE.is<const CallExpr *>(); } - + + bool isCXXConstructExpr() const { + return CallE && CallE.is<const CXXConstructExpr *>(); + } + + bool isObjCMessage() const { + return !CallE; + } + bool isCXXCall() const { - return CallE && isa<CXXMemberCallExpr>(CallE); + const CallExpr *ActualCallE = CallE.dyn_cast<const CallExpr *>(); + return ActualCallE && isa<CXXMemberCallExpr>(ActualCallE); + } + + const Expr *getOriginExpr() const { + if (!CallE) + return Msg.getOriginExpr(); + if (const CXXConstructExpr *Ctor = + CallE.dyn_cast<const CXXConstructExpr *>()) + return Ctor; + return CallE.get<const CallExpr *>(); } SVal getFunctionCallee() const; SVal getCXXCallee() const; + SVal getInstanceMessageReceiver(const LocationContext *LC) const; unsigned getNumArgs() const { - if (CallE) return CallE->getNumArgs(); - return Msg.getNumArgs(); + if (!CallE) + return Msg.getNumArgs(); + if (const CXXConstructExpr *Ctor = + CallE.dyn_cast<const CXXConstructExpr *>()) + return Ctor->getNumArgs(); + return CallE.get<const CallExpr *>()->getNumArgs(); } SVal getArgSVal(unsigned i) const { assert(i < getNumArgs()); - if (CallE) - return State->getSVal(CallE->getArg(i)); - return Msg.getArgSVal(i, State); + if (!CallE) + return Msg.getArgSVal(i, State); + return State->getSVal(getArg(i)); } - SVal getArgSValAsScalarOrLoc(unsigned i) const; - const Expr *getArg(unsigned i) const { assert(i < getNumArgs()); - if (CallE) - return CallE->getArg(i); - return Msg.getArgExpr(i); + if (!CallE) + return Msg.getArgExpr(i); + if (const CXXConstructExpr *Ctor = + CallE.dyn_cast<const CXXConstructExpr *>()) + return Ctor->getArg(i); + return CallE.get<const CallExpr *>()->getArg(i); } SourceRange getArgSourceRange(unsigned i) const { assert(i < getNumArgs()); if (CallE) - return CallE->getArg(i)->getSourceRange(); + return getArg(i)->getSourceRange(); return Msg.getArgSourceRange(i); } + + SourceRange getReceiverSourceRange() const { + assert(isObjCMessage()); + return Msg.getReceiverSourceRange(); + } }; } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/GRState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h index 0d61d0e620eb..edae06e68c34 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/GRState.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -1,4 +1,4 @@ -//== GRState.h - Path-sensitive "State" for tracking values -----*- C++ -*--==// +//== ProgramState.h - Path-sensitive "State" for tracking values -*- C++ -*--=// // // The LLVM Compiler Infrastructure // @@ -7,13 +7,14 @@ // //===----------------------------------------------------------------------===// // -// This file defines SymbolRef, ExprBindKey, and GRState*. +// This file defines SymbolRef, ExprBindKey, and ProgramState*. // //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_GR_VALUESTATE_H #define LLVM_CLANG_GR_VALUESTATE_H +#include "clang/Basic/LLVM.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" @@ -21,12 +22,10 @@ #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableMap.h" -#include "llvm/Support/Casting.h" namespace llvm { class APSInt; class BumpPtrAllocator; -class raw_ostream; } namespace clang { @@ -34,30 +33,31 @@ class ASTContext; namespace ento { -class GRStateManager; +class ProgramStateManager; -typedef ConstraintManager* (*ConstraintManagerCreator)(GRStateManager&, +typedef ConstraintManager* (*ConstraintManagerCreator)(ProgramStateManager&, SubEngine&); -typedef StoreManager* (*StoreManagerCreator)(GRStateManager&); +typedef StoreManager* (*StoreManagerCreator)(ProgramStateManager&); //===----------------------------------------------------------------------===// -// GRStateTrait - Traits used by the Generic Data Map of a GRState. +// ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState. //===----------------------------------------------------------------------===// -template <typename T> struct GRStatePartialTrait; +template <typename T> struct ProgramStatePartialTrait; -template <typename T> struct GRStateTrait { +template <typename T> struct ProgramStateTrait { typedef typename T::data_type data_type; - static inline void* GDMIndex() { return &T::TagInt; } - static inline void* MakeVoidPtr(data_type D) { return (void*) D; } - static inline data_type MakeData(void* const* P) { + static inline void *GDMIndex() { return &T::TagInt; } + static inline void *MakeVoidPtr(data_type D) { return (void*) D; } + static inline data_type MakeData(void *const* P) { return P ? (data_type) *P : (data_type) 0; } }; -class GRStateManager; +class ProgramStateManager; -/// GRState - This class encapsulates: +/// \class ProgramState +/// ProgramState - This class encapsulates: /// /// 1. A mapping from expressions to values (Environment) /// 2. A mapping from locations to values (Store) @@ -65,47 +65,47 @@ class GRStateManager; /// /// Together these represent the "abstract state" of a program. /// -/// GRState is intended to be used as a functional object; that is, +/// ProgramState is intended to be used as a functional object; that is, /// once it is created and made "persistent" in a FoldingSet, its /// values will never change. -class GRState : public llvm::FoldingSetNode { +class ProgramState : public llvm::FoldingSetNode { public: typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; typedef llvm::ImmutableMap<void*, void*> GenericDataMap; private: - void operator=(const GRState& R) const; // Do not implement. + void operator=(const ProgramState& R) const; // Do not implement. - friend class GRStateManager; + friend class ProgramStateManager; friend class ExplodedGraph; friend class ExplodedNode; - GRStateManager *stateMgr; + ProgramStateManager *stateMgr; Environment Env; // Maps a Stmt to its current SVal. Store store; // Maps a location to its current value. GenericDataMap GDM; // Custom data stored by a client of this class. unsigned refCount; - /// makeWithStore - Return a GRState with the same values as the current + /// makeWithStore - Return a ProgramState with the same values as the current /// state with the exception of using the specified Store. - const GRState *makeWithStore(const StoreRef &store) const; + const ProgramState *makeWithStore(const StoreRef &store) const; void setStore(const StoreRef &storeRef); public: - /// This ctor is used when creating the first GRState object. - GRState(GRStateManager *mgr, const Environment& env, + /// This ctor is used when creating the first ProgramState object. + ProgramState(ProgramStateManager *mgr, const Environment& env, StoreRef st, GenericDataMap gdm); /// Copy ctor - We must explicitly define this or else the "Next" ptr /// in FoldingSetNode will also get copied. - GRState(const GRState& RHS); + ProgramState(const ProgramState &RHS); - ~GRState(); + ~ProgramState(); - /// Return the GRStateManager associated with this state. - GRStateManager &getStateManager() const { return *stateMgr; } + /// Return the ProgramStateManager associated with this state. + ProgramStateManager &getStateManager() const { return *stateMgr; } /// Return true if this state is referenced by a persistent ExplodedNode. bool referencedByExplodedNode() const { return refCount > 0; } @@ -124,10 +124,10 @@ public: void setGDM(GenericDataMap gdm) { GDM = gdm; } - /// Profile - Profile the contents of a GRState object for use in a - /// FoldingSet. Two GRState objects are considered equal if they + /// Profile - Profile the contents of a ProgramState object for use in a + /// FoldingSet. Two ProgramState objects are considered equal if they /// have the same Environment, Store, and GenericDataMap. - static void Profile(llvm::FoldingSetNodeID& ID, const GRState* V) { + static void Profile(llvm::FoldingSetNodeID& ID, const ProgramState *V) { V->Env.Profile(ID); ID.AddPointer(V->store); V->GDM.Profile(ID); @@ -146,44 +146,41 @@ public: // Constraints on values. //==---------------------------------------------------------------------==// // - // Each GRState records constraints on symbolic values. These constraints - // are managed using the ConstraintManager associated with a GRStateManager. + // Each ProgramState records constraints on symbolic values. These constraints + // are managed using the ConstraintManager associated with a ProgramStateManager. // As constraints gradually accrue on symbolic values, added constraints // may conflict and indicate that a state is infeasible (as no real values // could satisfy all the constraints). This is the principal mechanism - // for modeling path-sensitivity in ExprEngine/GRState. + // for modeling path-sensitivity in ExprEngine/ProgramState. // // Various "assume" methods form the interface for adding constraints to // symbolic values. A call to 'assume' indicates an assumption being placed // on one or symbolic values. 'assume' methods take the following inputs: // - // (1) A GRState object representing the current state. + // (1) A ProgramState object representing the current state. // // (2) The assumed constraint (which is specific to a given "assume" method). // // (3) A binary value "Assumption" that indicates whether the constraint is // assumed to be true or false. // - // The output of "assume*" is a new GRState object with the added constraints. + // The output of "assume*" is a new ProgramState object with the added constraints. // If no new state is feasible, NULL is returned. // - const GRState *assume(DefinedOrUnknownSVal cond, bool assumption) const; + const ProgramState *assume(DefinedOrUnknownSVal cond, bool assumption) const; /// This method assumes both "true" and "false" for 'cond', and /// returns both corresponding states. It's shorthand for doing /// 'assume' twice. - std::pair<const GRState*, const GRState*> + std::pair<const ProgramState*, const ProgramState*> assume(DefinedOrUnknownSVal cond) const; - const GRState *assumeInBound(DefinedOrUnknownSVal idx, + const ProgramState *assumeInBound(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, bool assumption) const; - //==---------------------------------------------------------------------==// - // Utility methods for getting regions. - //==---------------------------------------------------------------------==// - + /// Utility method for getting regions. const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; //==---------------------------------------------------------------------==// @@ -192,52 +189,42 @@ public: /// BindCompoundLiteral - Return the state that has the bindings currently /// in this state plus the bindings for the CompoundLiteral. - const GRState *bindCompoundLiteral(const CompoundLiteralExpr* CL, + const ProgramState *bindCompoundLiteral(const CompoundLiteralExpr *CL, 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; + const ProgramState *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 ProgramState *bindExprAndLocation(const Stmt *S, SVal location, SVal V) const; - const GRState *bindDecl(const VarRegion *VR, SVal V) const; + const ProgramState *bindDecl(const VarRegion *VR, SVal V) const; - const GRState *bindDeclWithNoInit(const VarRegion *VR) const; + const ProgramState *bindDeclWithNoInit(const VarRegion *VR) const; - const GRState *bindLoc(Loc location, SVal V) const; + const ProgramState *bindLoc(Loc location, SVal V) const; - const GRState *bindLoc(SVal location, SVal V) const; + const ProgramState *bindLoc(SVal location, SVal V) const; - const GRState *bindDefault(SVal loc, SVal V) const; + const ProgramState *bindDefault(SVal loc, SVal V) const; - 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); - } + const ProgramState *unbindLoc(Loc LV) const; /// 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 ProgramState *invalidateRegions(ArrayRef<const MemRegion *> Regions, const Expr *E, unsigned BlockCount, - StoreManager::InvalidatedSymbols *IS, - bool invalidateGlobals) const; + StoreManager::InvalidatedSymbols *IS = 0, + bool invalidateGlobals = false) const; /// enterStackFrame - Returns the state for entry to the given stack frame, /// preserving the current state. - const GRState *enterStackFrame(const StackFrameContext *frame) const; + const ProgramState *enterStackFrame(const StackFrameContext *frame) const; /// Get the lvalue for a variable reference. Loc getLValue(const VarDecl *D, const LocationContext *LC) const; @@ -260,7 +247,7 @@ public: const llvm::APSInt *getSymVal(SymbolRef sym) const; /// Returns the SVal bound to the statement 'S' in the state's environment. - SVal getSVal(const Stmt* S, bool useOnlyDirectBindings = false) const; + SVal getSVal(const Stmt *S, bool useOnlyDirectBindings = false) const; SVal getSValAsScalarOrLoc(const Stmt *Ex) const; @@ -273,11 +260,22 @@ public: SVal getSValAsScalarOrLoc(const MemRegion *R) const; + /// \brief Visits the symbols reachable from the given SVal using the provided + /// SymbolVisitor. + /// + /// This is a convenience API. Consider using ScanReachableSymbols class + /// directly when making multiple scans on the same state with the same + /// visitor to avoid repeated initialization cost. + /// \sa ScanReachableSymbols bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; + /// \brief Visits the symbols reachable from the SVals in the given range + /// using the provided SymbolVisitor. bool scanReachableSymbols(const SVal *I, const SVal *E, SymbolVisitor &visitor) const; + /// \brief Visits the symbols reachable from the regions in the given + /// MemRegions range using the provided SymbolVisitor. bool scanReachableSymbols(const MemRegion * const *I, const MemRegion * const *E, SymbolVisitor &visitor) const; @@ -294,70 +292,62 @@ public: // Accessing the Generic Data Map (GDM). //==---------------------------------------------------------------------==// - void* const* FindGDM(void* K) const; + void *const* FindGDM(void *K) const; template<typename T> - const GRState *add(typename GRStateTrait<T>::key_type K) const; + const ProgramState *add(typename ProgramStateTrait<T>::key_type K) const; template <typename T> - typename GRStateTrait<T>::data_type + typename ProgramStateTrait<T>::data_type get() const { - return GRStateTrait<T>::MakeData(FindGDM(GRStateTrait<T>::GDMIndex())); + return ProgramStateTrait<T>::MakeData(FindGDM(ProgramStateTrait<T>::GDMIndex())); } template<typename T> - typename GRStateTrait<T>::lookup_type - get(typename GRStateTrait<T>::key_type key) const { - void* const* d = FindGDM(GRStateTrait<T>::GDMIndex()); - return GRStateTrait<T>::Lookup(GRStateTrait<T>::MakeData(d), key); + typename ProgramStateTrait<T>::lookup_type + get(typename ProgramStateTrait<T>::key_type key) const { + void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); + return ProgramStateTrait<T>::Lookup(ProgramStateTrait<T>::MakeData(d), key); } template <typename T> - typename GRStateTrait<T>::context_type get_context() const; + typename ProgramStateTrait<T>::context_type get_context() const; template<typename T> - const GRState *remove(typename GRStateTrait<T>::key_type K) const; + const ProgramState *remove(typename ProgramStateTrait<T>::key_type K) const; template<typename T> - const GRState *remove(typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::context_type C) const; + const ProgramState *remove(typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::context_type C) const; template <typename T> - const GRState *remove() const; + const ProgramState *remove() const; template<typename T> - const GRState *set(typename GRStateTrait<T>::data_type D) const; + const ProgramState *set(typename ProgramStateTrait<T>::data_type D) const; template<typename T> - const GRState *set(typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::value_type E) const; + const ProgramState *set(typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::value_type E) const; template<typename T> - const GRState *set(typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::value_type E, - typename GRStateTrait<T>::context_type C) const; + const ProgramState *set(typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::value_type E, + typename ProgramStateTrait<T>::context_type C) const; template<typename T> - bool contains(typename GRStateTrait<T>::key_type key) const { - void* const* d = FindGDM(GRStateTrait<T>::GDMIndex()); - return GRStateTrait<T>::Contains(GRStateTrait<T>::MakeData(d), key); + bool contains(typename ProgramStateTrait<T>::key_type key) const { + void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); + return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key); } - // State pretty-printing. - class Printer { - public: - virtual ~Printer() {} - virtual void Print(llvm::raw_ostream& Out, const GRState* state, - const char* nl, const char* sep) = 0; - }; - // Pretty-printing. - void print(llvm::raw_ostream& Out, CFG &C, const char *nl = "\n", + void print(raw_ostream &Out, CFG &C, const char *nl = "\n", const char *sep = "") const; void printStdErr(CFG &C) const; - void printDOT(llvm::raw_ostream& Out, CFG &C) const; + void printDOT(raw_ostream &Out, CFG &C) const; private: /// Increments the number of times this state is referenced by ExplodeNodes. @@ -369,20 +359,20 @@ private: --refCount; } - const GRState *invalidateRegionsImpl(const MemRegion * const *Begin, - const MemRegion * const *End, - const Expr *E, unsigned BlockCount, - StoreManager::InvalidatedSymbols &IS, - bool invalidateGlobals) const; + const ProgramState * + invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, + const Expr *E, unsigned BlockCount, + StoreManager::InvalidatedSymbols &IS, + bool invalidateGlobals) const; }; -class GRStateSet { - typedef llvm::SmallPtrSet<const GRState*,5> ImplTy; +class ProgramStateSet { + typedef llvm::SmallPtrSet<const ProgramState*,5> ImplTy; ImplTy Impl; public: - GRStateSet() {} + ProgramStateSet() {} - inline void Add(const GRState* St) { + inline void Add(const ProgramState *St) { Impl.insert(St); } @@ -395,11 +385,11 @@ public: inline iterator end() const { return Impl.end(); } class AutoPopulate { - GRStateSet& S; + ProgramStateSet &S; unsigned StartSize; - const GRState* St; + const ProgramState *St; public: - AutoPopulate(GRStateSet& s, const GRState* st) + AutoPopulate(ProgramStateSet &s, const ProgramState *st) : S(s), StartSize(S.size()), St(st) {} ~AutoPopulate() { @@ -410,12 +400,11 @@ public: }; //===----------------------------------------------------------------------===// -// GRStateManager - Factory object for GRStates. +// ProgramStateManager - Factory object for ProgramStates. //===----------------------------------------------------------------------===// -class GRStateManager { - friend class GRState; - friend class ExprEngine; // FIXME: Remove. +class ProgramStateManager { + friend class ProgramState; private: /// Eng - The SubEngine that owns this state manager. SubEngine *Eng; /* Can be null. */ @@ -424,18 +413,14 @@ private: llvm::OwningPtr<StoreManager> StoreMgr; llvm::OwningPtr<ConstraintManager> ConstraintMgr; - GRState::GenericDataMap::Factory GDMFactory; + ProgramState::GenericDataMap::Factory GDMFactory; typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy; GDMContextsTy GDMContexts; - /// Printers - A set of printer objects used for pretty-printing a GRState. - /// GRStateManager owns these objects. - std::vector<GRState::Printer*> Printers; - /// StateSet - FoldingSet containing all the states created for analyzing /// a particular function. This is used to unique states. - llvm::FoldingSet<GRState> StateSet; + llvm::FoldingSet<ProgramState> StateSet; /// Object that manages the data for all created SVals. llvm::OwningPtr<SValBuilder> svalBuilder; @@ -443,15 +428,15 @@ private: /// A BumpPtrAllocator to allocate states. llvm::BumpPtrAllocator &Alloc; - /// A vector of recently allocated GRStates that can potentially be + /// A vector of recently allocated ProgramStates that can potentially be /// reused. - std::vector<GRState *> recentlyAllocatedStates; + std::vector<ProgramState *> recentlyAllocatedStates; - /// A vector of GRStates that we can reuse. - std::vector<GRState *> freeStates; + /// A vector of ProgramStates that we can reuse. + std::vector<ProgramState *> freeStates; public: - GRStateManager(ASTContext& Ctx, + ProgramStateManager(ASTContext &Ctx, StoreManagerCreator CreateStoreManager, ConstraintManagerCreator CreateConstraintManager, llvm::BumpPtrAllocator& alloc, @@ -465,7 +450,7 @@ public: ConstraintMgr.reset((*CreateConstraintManager)(*this, subeng)); } - GRStateManager(ASTContext& Ctx, + ProgramStateManager(ASTContext &Ctx, StoreManagerCreator CreateStoreManager, ConstraintManager* ConstraintManagerPtr, llvm::BumpPtrAllocator& alloc) @@ -478,9 +463,9 @@ public: ConstraintMgr.reset(ConstraintManagerPtr); } - ~GRStateManager(); + ~ProgramStateManager(); - const GRState *getInitialState(const LocationContext *InitLoc); + const ProgramState *getInitialState(const LocationContext *InitLoc); ASTContext &getContext() { return svalBuilder->getContext(); } const ASTContext &getContext() const { return svalBuilder->getContext(); } @@ -516,13 +501,13 @@ public: ConstraintManager& getConstraintManager() { return *ConstraintMgr; } SubEngine* getOwningEngine() { return Eng; } - const GRState* removeDeadBindings(const GRState* St, + const ProgramState *removeDeadBindings(const ProgramState *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); + const ProgramState *MarshalState(const ProgramState *state, const StackFrameContext *L); public: @@ -531,18 +516,28 @@ public: } // Methods that manipulate the GDM. - const GRState* addGDM(const GRState* St, void* Key, void* Data); - const GRState *removeGDM(const GRState *state, void *Key); + const ProgramState *addGDM(const ProgramState *St, void *Key, void *Data); + const ProgramState *removeGDM(const ProgramState *state, void *Key); // Methods that query & manipulate the Store. - void iterBindings(const GRState* state, StoreManager::BindingsHandler& F) { + void iterBindings(const ProgramState *state, StoreManager::BindingsHandler& F) { StoreMgr->iterBindings(state->getStore(), F); } - const GRState* getPersistentState(GRState& Impl); - - /// Periodically called by ExprEngine to recycle GRStates that were + const ProgramState *getPersistentState(ProgramState &Impl); + const ProgramState *getPersistentStateWithGDM(const ProgramState *FromState, + const ProgramState *GDMState); + + bool haveEqualEnvironments(const ProgramState * S1, const ProgramState * S2) { + return S1->Env == S2->Env; + } + + bool haveEqualStores(const ProgramState * S1, const ProgramState * S2) { + return S1->store == S2->store; + } + + /// Periodically called by ExprEngine to recycle ProgramStates that were /// created but never used for creating an ExplodedNode. void recycleUnusedStates(); @@ -550,9 +545,9 @@ public: // Generic Data Map methods. //==---------------------------------------------------------------------==// // - // GRStateManager and GRState support a "generic data map" that allows - // different clients of GRState objects to embed arbitrary data within a - // GRState object. The generic data map is essentially an immutable map + // ProgramStateManager and ProgramState support a "generic data map" that allows + // different clients of ProgramState objects to embed arbitrary data within a + // ProgramState object. The generic data map is essentially an immutable map // from a "tag" (that acts as the "key" for a client) and opaque values. // Tags/keys and values are simply void* values. The typical way that clients // generate unique tags are by taking the address of a static variable. @@ -560,82 +555,82 @@ public: // the data pointer are immutable (and thus are essentially purely functional // data). // - // The templated methods below use the GRStateTrait<T> class + // The templated methods below use the ProgramStateTrait<T> class // to resolve keys into the GDM and to return data values to clients. // // Trait based GDM dispatch. template <typename T> - const GRState* set(const GRState* st, typename GRStateTrait<T>::data_type D) { - return addGDM(st, GRStateTrait<T>::GDMIndex(), - GRStateTrait<T>::MakeVoidPtr(D)); + const ProgramState *set(const ProgramState *st, typename ProgramStateTrait<T>::data_type D) { + return addGDM(st, ProgramStateTrait<T>::GDMIndex(), + ProgramStateTrait<T>::MakeVoidPtr(D)); } template<typename T> - const GRState* set(const GRState* st, - typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::value_type V, - typename GRStateTrait<T>::context_type C) { + const ProgramState *set(const ProgramState *st, + typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::value_type V, + typename ProgramStateTrait<T>::context_type C) { - return addGDM(st, GRStateTrait<T>::GDMIndex(), - GRStateTrait<T>::MakeVoidPtr(GRStateTrait<T>::Set(st->get<T>(), K, V, C))); + return addGDM(st, ProgramStateTrait<T>::GDMIndex(), + ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Set(st->get<T>(), K, V, C))); } template <typename T> - const GRState* add(const GRState* st, - typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::context_type C) { - return addGDM(st, GRStateTrait<T>::GDMIndex(), - GRStateTrait<T>::MakeVoidPtr(GRStateTrait<T>::Add(st->get<T>(), K, C))); + const ProgramState *add(const ProgramState *st, + typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::context_type C) { + return addGDM(st, ProgramStateTrait<T>::GDMIndex(), + ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Add(st->get<T>(), K, C))); } template <typename T> - const GRState* remove(const GRState* st, - typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::context_type C) { + const ProgramState *remove(const ProgramState *st, + typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::context_type C) { - return addGDM(st, GRStateTrait<T>::GDMIndex(), - GRStateTrait<T>::MakeVoidPtr(GRStateTrait<T>::Remove(st->get<T>(), K, C))); + return addGDM(st, ProgramStateTrait<T>::GDMIndex(), + ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Remove(st->get<T>(), K, C))); } template <typename T> - const GRState *remove(const GRState *st) { - return removeGDM(st, GRStateTrait<T>::GDMIndex()); + const ProgramState *remove(const ProgramState *st) { + return removeGDM(st, ProgramStateTrait<T>::GDMIndex()); } - void* FindGDMContext(void* index, - void* (*CreateContext)(llvm::BumpPtrAllocator&), + void *FindGDMContext(void *index, + void *(*CreateContext)(llvm::BumpPtrAllocator&), void (*DeleteContext)(void*)); template <typename T> - typename GRStateTrait<T>::context_type get_context() { - void* p = FindGDMContext(GRStateTrait<T>::GDMIndex(), - GRStateTrait<T>::CreateContext, - GRStateTrait<T>::DeleteContext); + typename ProgramStateTrait<T>::context_type get_context() { + void *p = FindGDMContext(ProgramStateTrait<T>::GDMIndex(), + ProgramStateTrait<T>::CreateContext, + ProgramStateTrait<T>::DeleteContext); - return GRStateTrait<T>::MakeContext(p); + return ProgramStateTrait<T>::MakeContext(p); } - const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) { + const llvm::APSInt* getSymVal(const ProgramState *St, SymbolRef sym) { return ConstraintMgr->getSymVal(St, sym); } - void EndPath(const GRState* St) { + void EndPath(const ProgramState *St) { ConstraintMgr->EndPath(St); } }; //===----------------------------------------------------------------------===// -// Out-of-line method definitions for GRState. +// Out-of-line method definitions for ProgramState. //===----------------------------------------------------------------------===// -inline const VarRegion* GRState::getRegion(const VarDecl *D, +inline const VarRegion* ProgramState::getRegion(const VarDecl *D, const LocationContext *LC) const { return getStateManager().getRegionManager().getVarRegion(D, LC); } -inline const GRState *GRState::assume(DefinedOrUnknownSVal Cond, +inline const ProgramState *ProgramState::assume(DefinedOrUnknownSVal Cond, bool Assumption) const { if (Cond.isUnknown()) return this; @@ -644,8 +639,8 @@ inline const GRState *GRState::assume(DefinedOrUnknownSVal Cond, Assumption); } -inline std::pair<const GRState*, const GRState*> -GRState::assume(DefinedOrUnknownSVal Cond) const { +inline std::pair<const ProgramState*, const ProgramState*> +ProgramState::assume(DefinedOrUnknownSVal Cond) const { if (Cond.isUnknown()) return std::make_pair(this, this); @@ -653,48 +648,48 @@ GRState::assume(DefinedOrUnknownSVal Cond) const { cast<DefinedSVal>(Cond)); } -inline const GRState *GRState::bindLoc(SVal LV, SVal V) const { +inline const ProgramState *ProgramState::bindLoc(SVal LV, SVal V) const { return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V); } -inline Loc GRState::getLValue(const VarDecl* VD, +inline Loc ProgramState::getLValue(const VarDecl *VD, const LocationContext *LC) const { return getStateManager().StoreMgr->getLValueVar(VD, LC); } -inline Loc GRState::getLValue(const StringLiteral *literal) const { +inline Loc ProgramState::getLValue(const StringLiteral *literal) const { return getStateManager().StoreMgr->getLValueString(literal); } -inline Loc GRState::getLValue(const CompoundLiteralExpr *literal, +inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal, const LocationContext *LC) const { return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); } -inline SVal GRState::getLValue(const ObjCIvarDecl *D, SVal Base) const { +inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const { return getStateManager().StoreMgr->getLValueIvar(D, Base); } -inline SVal GRState::getLValue(const FieldDecl* D, SVal Base) const { +inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const { return getStateManager().StoreMgr->getLValueField(D, Base); } -inline SVal GRState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ +inline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ if (NonLoc *N = dyn_cast<NonLoc>(&Idx)) return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base); return UnknownVal(); } -inline const llvm::APSInt *GRState::getSymVal(SymbolRef sym) const { +inline const llvm::APSInt *ProgramState::getSymVal(SymbolRef sym) const { return getStateManager().getSymVal(this, sym); } -inline SVal GRState::getSVal(const Stmt* Ex, bool useOnlyDirectBindings) const{ +inline SVal ProgramState::getSVal(const Stmt *Ex, bool useOnlyDirectBindings) const{ return Env.getSVal(Ex, *getStateManager().svalBuilder, - useOnlyDirectBindings); + useOnlyDirectBindings); } -inline SVal GRState::getSValAsScalarOrLoc(const Stmt *S) const { +inline SVal ProgramState::getSValAsScalarOrLoc(const Stmt *S) const { if (const Expr *Ex = dyn_cast<Expr>(S)) { QualType T = Ex->getType(); if (Ex->isLValue() || Loc::isLocType(T) || T->isIntegerType()) @@ -704,88 +699,114 @@ inline SVal GRState::getSValAsScalarOrLoc(const Stmt *S) const { return UnknownVal(); } -inline SVal GRState::getRawSVal(Loc LV, QualType T) const { +inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const { return getStateManager().StoreMgr->Retrieve(getStore(), LV, T); } -inline SVal GRState::getSVal(const MemRegion* R) const { +inline SVal ProgramState::getSVal(const MemRegion* R) const { return getStateManager().StoreMgr->Retrieve(getStore(), loc::MemRegionVal(R)); } -inline BasicValueFactory &GRState::getBasicVals() const { +inline BasicValueFactory &ProgramState::getBasicVals() const { return getStateManager().getBasicVals(); } -inline SymbolManager &GRState::getSymbolManager() const { +inline SymbolManager &ProgramState::getSymbolManager() const { return getStateManager().getSymbolManager(); } template<typename T> -const GRState *GRState::add(typename GRStateTrait<T>::key_type K) const { +const ProgramState *ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { return getStateManager().add<T>(this, K, get_context<T>()); } template <typename T> -typename GRStateTrait<T>::context_type GRState::get_context() const { +typename ProgramStateTrait<T>::context_type ProgramState::get_context() const { return getStateManager().get_context<T>(); } template<typename T> -const GRState *GRState::remove(typename GRStateTrait<T>::key_type K) const { +const ProgramState *ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { return getStateManager().remove<T>(this, K, get_context<T>()); } template<typename T> -const GRState *GRState::remove(typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::context_type C) const { +const ProgramState *ProgramState::remove(typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::context_type C) const { return getStateManager().remove<T>(this, K, C); } template <typename T> -const GRState *GRState::remove() const { +const ProgramState *ProgramState::remove() const { return getStateManager().remove<T>(this); } template<typename T> -const GRState *GRState::set(typename GRStateTrait<T>::data_type D) const { +const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { return getStateManager().set<T>(this, D); } template<typename T> -const GRState *GRState::set(typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::value_type E) const { +const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::value_type E) const { return getStateManager().set<T>(this, K, E, get_context<T>()); } template<typename T> -const GRState *GRState::set(typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::value_type E, - typename GRStateTrait<T>::context_type C) const { +const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::key_type K, + typename ProgramStateTrait<T>::value_type E, + typename ProgramStateTrait<T>::context_type C) const { return getStateManager().set<T>(this, K, E, C); } template <typename CB> -CB GRState::scanReachableSymbols(SVal val) const { +CB ProgramState::scanReachableSymbols(SVal val) const { CB cb(this); scanReachableSymbols(val, cb); return cb; } template <typename CB> -CB GRState::scanReachableSymbols(const SVal *beg, const SVal *end) const { +CB ProgramState::scanReachableSymbols(const SVal *beg, const SVal *end) const { CB cb(this); scanReachableSymbols(beg, end, cb); return cb; } template <typename CB> -CB GRState::scanReachableSymbols(const MemRegion * const *beg, +CB ProgramState::scanReachableSymbols(const MemRegion * const *beg, const MemRegion * const *end) const { CB cb(this); scanReachableSymbols(beg, end, cb); return cb; } +/// \class ScanReachableSymbols +/// A Utility class that allows to visit the reachable symbols using a custom +/// SymbolVisitor. +class ScanReachableSymbols : public SubRegionMap::Visitor { + typedef llvm::DenseMap<const void*, unsigned> VisitedItems; + + VisitedItems visited; + const ProgramState *state; + SymbolVisitor &visitor; + llvm::OwningPtr<SubRegionMap> SRM; +public: + + ScanReachableSymbols(const ProgramState *st, SymbolVisitor& v) + : state(st), visitor(v) {} + + bool scan(nonloc::CompoundVal val); + bool scan(SVal val); + bool scan(const MemRegion *R); + bool scan(const SymExpr *sym); + + // From SubRegionMap::Visitor. + bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) { + return scan(SubRegion); + } +}; + } // end GR namespace } // end clang namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h index de7b8684066f..b80d494b88cb 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h @@ -1,4 +1,4 @@ -//==- GRStateTrait.h - Partial implementations of GRStateTrait -----*- C++ -*-// +//ProgramStateTrait.h - Partial implementations of ProgramStateTrait -*- C++ -*- // // The LLVM Compiler Infrastructure // @@ -8,14 +8,15 @@ //===----------------------------------------------------------------------===// // // This file defines partial implementations of template specializations of -// the class GRStateTrait<>. GRStateTrait<> is used by GRState to implement -// set/get methods for mapulating a GRState's generic data map. +// the class ProgramStateTrait<>. ProgramStateTrait<> is used by ProgramState +// to implement set/get methods for mapulating a ProgramState's +// generic data map. // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_GR_GRSTATETRAIT_H -#define LLVM_CLANG_GR_GRSTATETRAIT_H +#ifndef LLVM_CLANG_GR_PROGRAMSTATETRAIT_H +#define LLVM_CLANG_GR_PROGRAMSTATETRAIT_H namespace llvm { class BumpPtrAllocator; @@ -28,22 +29,22 @@ namespace llvm { namespace clang { namespace ento { - template <typename T> struct GRStatePartialTrait; + template <typename T> struct ProgramStatePartialTrait; // Partial-specialization for ImmutableMap. template <typename Key, typename Data, typename Info> - struct GRStatePartialTrait< llvm::ImmutableMap<Key,Data,Info> > { + struct ProgramStatePartialTrait< llvm::ImmutableMap<Key,Data,Info> > { typedef llvm::ImmutableMap<Key,Data,Info> data_type; typedef typename data_type::Factory& context_type; typedef Key key_type; typedef Data value_type; typedef const value_type* lookup_type; - static inline data_type MakeData(void* const* p) { + static inline data_type MakeData(void *const* p) { return p ? data_type((typename data_type::TreeTy*) *p) : data_type(0); } - static inline void* MakeVoidPtr(data_type B) { + static inline void *MakeVoidPtr(data_type B) { return B.getRoot(); } static lookup_type Lookup(data_type B, key_type K) { @@ -57,15 +58,15 @@ namespace ento { return F.remove(B, K); } - static inline context_type MakeContext(void* p) { + static inline context_type MakeContext(void *p) { return *((typename data_type::Factory*) p); } - static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + static void *CreateContext(llvm::BumpPtrAllocator& Alloc) { return new typename data_type::Factory(Alloc); } - static void DeleteContext(void* Ctx) { + static void DeleteContext(void *Ctx) { delete (typename data_type::Factory*) Ctx; } }; @@ -74,16 +75,16 @@ namespace ento { // Partial-specialization for ImmutableSet. template <typename Key, typename Info> - struct GRStatePartialTrait< llvm::ImmutableSet<Key,Info> > { + struct ProgramStatePartialTrait< llvm::ImmutableSet<Key,Info> > { typedef llvm::ImmutableSet<Key,Info> data_type; typedef typename data_type::Factory& context_type; typedef Key key_type; - static inline data_type MakeData(void* const* p) { + static inline data_type MakeData(void *const* p) { return p ? data_type((typename data_type::TreeTy*) *p) : data_type(0); } - static inline void* MakeVoidPtr(data_type B) { + static inline void *MakeVoidPtr(data_type B) { return B.getRoot(); } @@ -99,15 +100,15 @@ namespace ento { return B.contains(K); } - static inline context_type MakeContext(void* p) { + static inline context_type MakeContext(void *p) { return *((typename data_type::Factory*) p); } - static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + static void *CreateContext(llvm::BumpPtrAllocator& Alloc) { return new typename data_type::Factory(Alloc); } - static void DeleteContext(void* Ctx) { + static void DeleteContext(void *Ctx) { delete (typename data_type::Factory*) Ctx; } }; @@ -115,7 +116,7 @@ namespace ento { // Partial-specialization for ImmutableList. template <typename T> - struct GRStatePartialTrait< llvm::ImmutableList<T> > { + struct ProgramStatePartialTrait< llvm::ImmutableList<T> > { typedef llvm::ImmutableList<T> data_type; typedef T key_type; typedef typename data_type::Factory& context_type; @@ -128,33 +129,33 @@ namespace ento { return L.contains(K); } - static inline data_type MakeData(void* const* p) { + static inline data_type MakeData(void *const* p) { return p ? data_type((const llvm::ImmutableListImpl<T>*) *p) : data_type(0); } - static inline void* MakeVoidPtr(data_type D) { + static inline void *MakeVoidPtr(data_type D) { return (void*) D.getInternalPointer(); } - static inline context_type MakeContext(void* p) { + static inline context_type MakeContext(void *p) { return *((typename data_type::Factory*) p); } - static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + static void *CreateContext(llvm::BumpPtrAllocator& Alloc) { return new typename data_type::Factory(Alloc); } - static void DeleteContext(void* Ctx) { + static void DeleteContext(void *Ctx) { delete (typename data_type::Factory*) Ctx; } }; // Partial specialization for bool. - template <> struct GRStatePartialTrait<bool> { + template <> struct ProgramStatePartialTrait<bool> { typedef bool data_type; - static inline data_type MakeData(void* const* p) { + static inline data_type MakeData(void *const* p) { return p ? (data_type) (uintptr_t) *p : data_type(); } @@ -164,10 +165,10 @@ namespace ento { }; // Partial specialization for unsigned. - template <> struct GRStatePartialTrait<unsigned> { + template <> struct ProgramStatePartialTrait<unsigned> { typedef unsigned data_type; - static inline data_type MakeData(void* const* p) { + static inline data_type MakeData(void *const* p) { return p ? (data_type) (uintptr_t) *p : data_type(); } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h index 65eabea24077..17233e194e6d 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -25,7 +25,7 @@ namespace clang { namespace ento { -class GRState; +class ProgramState; class SValBuilder { protected: @@ -40,7 +40,7 @@ protected: /// Manages the creation of memory regions. MemRegionManager MemMgr; - GRStateManager &StateMgr; + ProgramStateManager &StateMgr; /// The scalar type to use for array indices. const QualType ArrayIndexTy; @@ -56,7 +56,7 @@ public: public: SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, - GRStateManager &stateMgr) + ProgramStateManager &stateMgr) : Context(context), BasicVals(context, alloc), SymMgr(context, BasicVals, alloc), MemMgr(context, alloc), @@ -72,29 +72,29 @@ public: virtual SVal evalComplement(NonLoc val) = 0; - virtual SVal evalBinOpNN(const GRState *state, BinaryOperator::Opcode op, + virtual SVal evalBinOpNN(const ProgramState *state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy) = 0; - virtual SVal evalBinOpLL(const GRState *state, BinaryOperator::Opcode op, + virtual SVal evalBinOpLL(const ProgramState *state, BinaryOperator::Opcode op, Loc lhs, Loc rhs, QualType resultTy) = 0; - virtual SVal evalBinOpLN(const GRState *state, BinaryOperator::Opcode op, + virtual SVal evalBinOpLN(const ProgramState *state, BinaryOperator::Opcode op, Loc lhs, NonLoc rhs, QualType resultTy) = 0; /// getKnownValue - evaluates a given SVal. If the SVal has only one possible /// (integer) value, that value is returned. Otherwise, returns NULL. - virtual const llvm::APSInt *getKnownValue(const GRState *state, SVal val) = 0; + virtual const llvm::APSInt *getKnownValue(const ProgramState *state, SVal val) = 0; - SVal evalBinOp(const GRState *state, BinaryOperator::Opcode op, + SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type); - DefinedOrUnknownSVal evalEQ(const GRState *state, DefinedOrUnknownSVal lhs, + DefinedOrUnknownSVal evalEQ(const ProgramState *state, DefinedOrUnknownSVal lhs, DefinedOrUnknownSVal rhs); ASTContext &getContext() { return Context; } const ASTContext &getContext() const { return Context; } - GRStateManager &getStateManager() { return StateMgr; } + ProgramStateManager &getStateManager() { return StateMgr; } QualType getConditionType() const { return getContext().IntTy; @@ -115,14 +115,14 @@ public: // Forwarding methods to SymbolManager. - const SymbolConjured* getConjuredSymbol(const Stmt* stmt, QualType type, + const SymbolConjured* getConjuredSymbol(const Stmt *stmt, QualType type, unsigned visitCount, - const void* symbolTag = 0) { + const void *symbolTag = 0) { return SymMgr.getConjuredSymbol(stmt, type, visitCount, symbolTag); } - const SymbolConjured* getConjuredSymbol(const Expr* expr, unsigned visitCount, - const void* symbolTag = 0) { + const SymbolConjured* getConjuredSymbol(const Expr *expr, unsigned visitCount, + const void *symbolTag = 0) { return SymMgr.getConjuredSymbol(expr, visitCount, symbolTag); } @@ -130,7 +130,7 @@ public: DefinedOrUnknownSVal makeZeroVal(QualType type); /// getRegionValueSymbolVal - make a unique symbol for value of region. - DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedRegion *region); + DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedValueRegion *region); DefinedOrUnknownSVal getConjuredSymbolVal(const void *symbolTag, const Expr *expr, unsigned count); @@ -139,7 +139,7 @@ public: unsigned count); DefinedOrUnknownSVal getDerivedRegionValueSymbolVal( - SymbolRef parentSymbol, const TypedRegion *region); + SymbolRef parentSymbol, const TypedValueRegion *region); DefinedSVal getMetadataSymbolVal( const void *symbolTag, const MemRegion *region, @@ -154,7 +154,8 @@ public: return nonloc::CompoundVal(BasicVals.getCompoundValData(type, vals)); } - NonLoc makeLazyCompoundVal(const StoreRef &store, const TypedRegion *region) { + NonLoc makeLazyCompoundVal(const StoreRef &store, + const TypedValueRegion *region) { return nonloc::LazyCompoundVal( BasicVals.getLazyCompoundValData(store, region)); } @@ -254,7 +255,7 @@ public: SValBuilder* createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, - GRStateManager &stateMgr); + ProgramStateManager &stateMgr); } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h index 0d430794e76c..5827b0042a5d 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -15,14 +15,10 @@ #ifndef LLVM_CLANG_GR_RVALUE_H #define LLVM_CLANG_GR_RVALUE_H +#include "clang/Basic/LLVM.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" -#include "llvm/Support/Casting.h" #include "llvm/ADT/ImmutableList.h" -namespace llvm { - class raw_ostream; -} - //==------------------------------------------------------------------------==// // Base SVal types. //==------------------------------------------------------------------------==// @@ -33,12 +29,12 @@ namespace ento { class CompoundValData; class LazyCompoundValData; -class GRState; +class ProgramState; class BasicValueFactory; class MemRegion; class TypedRegion; class MemRegionManager; -class GRStateManager; +class ProgramStateManager; class SValBuilder; /// SVal - This represents a symbolic expression, which can be either @@ -57,16 +53,16 @@ public: enum { BaseBits = 2, BaseMask = 0x3 }; protected: - const void* Data; + const void *Data; /// The lowest 2 bits are a BaseKind (0 -- 3). /// The higher bits are an unsigned "kind" value. unsigned Kind; - explicit SVal(const void* d, bool isLoc, unsigned ValKind) + explicit SVal(const void *d, bool isLoc, unsigned ValKind) : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} - explicit SVal(BaseKind k, const void* D = NULL) + explicit SVal(BaseKind k, const void *D = NULL) : Data(D), Kind(k) {} public: @@ -74,7 +70,7 @@ public: ~SVal() {} /// BufferTy - A temporary buffer to hold a set of SVals. - typedef llvm::SmallVector<SVal,5> BufferTy; + typedef SmallVector<SVal,5> BufferTy; inline unsigned getRawKind() const { return Kind; } inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); } @@ -123,7 +119,7 @@ public: /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. /// Otherwise return 0. - const FunctionDecl* getAsFunctionDecl() const; + const FunctionDecl *getAsFunctionDecl() const; /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and /// wraps a symbol, return that SymbolRef. Otherwise return NULL. @@ -142,22 +138,22 @@ public: const MemRegion *getAsRegion() const; - void dumpToStream(llvm::raw_ostream& OS) const; + void dumpToStream(raw_ostream &OS) const; void dump() const; // Iterators. class symbol_iterator { - llvm::SmallVector<const SymExpr*, 5> itr; + SmallVector<const SymExpr*, 5> itr; void expand(); public: symbol_iterator() {} - symbol_iterator(const SymExpr* SE); + symbol_iterator(const SymExpr *SE); - symbol_iterator& operator++(); + symbol_iterator &operator++(); SymbolRef operator*(); - bool operator==(const symbol_iterator& X) const; - bool operator!=(const symbol_iterator& X) const; + bool operator==(const symbol_iterator &X) const; + bool operator!=(const symbol_iterator &X) const; }; symbol_iterator symbol_begin() const { @@ -178,13 +174,13 @@ public: class UndefinedVal : public SVal { public: UndefinedVal() : SVal(UndefinedKind) {} - UndefinedVal(const void* D) : SVal(UndefinedKind, D) {} + UndefinedVal(const void *D) : SVal(UndefinedKind, D) {} static inline bool classof(const SVal* V) { return V->getBaseKind() == UndefinedKind; } - const void* getData() const { return Data; } + const void *getData() const { return Data; } }; class DefinedOrUnknownSVal : public SVal { @@ -195,7 +191,7 @@ private: bool isValid() const; protected: - explicit DefinedOrUnknownSVal(const void* d, bool isLoc, unsigned ValKind) + explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind) : SVal(d, isLoc, ValKind) {} explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL) @@ -225,7 +221,7 @@ private: bool isUnknownOrUndef() const; bool isValid() const; protected: - explicit DefinedSVal(const void* d, bool isLoc, unsigned ValKind) + explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) : DefinedOrUnknownSVal(d, isLoc, ValKind) {} public: // Implement isa<T> support. @@ -236,11 +232,11 @@ public: class NonLoc : public DefinedSVal { protected: - explicit NonLoc(unsigned SubKind, const void* d) + explicit NonLoc(unsigned SubKind, const void *d) : DefinedSVal(d, false, SubKind) {} public: - void dumpToStream(llvm::raw_ostream& Out) const; + void dumpToStream(raw_ostream &Out) const; // Implement isa<T> support. static inline bool classof(const SVal* V) { @@ -250,11 +246,11 @@ public: class Loc : public DefinedSVal { protected: - explicit Loc(unsigned SubKind, const void* D) + explicit Loc(unsigned SubKind, const void *D) : DefinedSVal(const_cast<void*>(D), true, SubKind) {} public: - void dumpToStream(llvm::raw_ostream& Out) const; + void dumpToStream(raw_ostream &Out) const; Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {} @@ -533,7 +529,7 @@ public: } // end clang namespace namespace llvm { -static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, +static inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { V.dumpToStream(os); return os; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h index cdbdf64515b4..a688d7f21979 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h @@ -29,20 +29,20 @@ class StackFrameContext; namespace ento { -class GRState; -class GRStateManager; +class ProgramState; +class ProgramStateManager; class SubRegionMap; class StoreManager { protected: SValBuilder &svalBuilder; - GRStateManager &StateMgr; + ProgramStateManager &StateMgr; /// MRMgr - Manages region objects associated with this StoreManager. MemRegionManager &MRMgr; ASTContext &Ctx; - StoreManager(GRStateManager &stateMgr); + StoreManager(ProgramStateManager &stateMgr); public: virtual ~StoreManager() {} @@ -60,7 +60,7 @@ public: /// \param[in] state The analysis state. /// \param[in] loc The symbolic memory location. /// \param[in] val The value to bind to location \c loc. - /// \return A pointer to a GRState object that contains the same bindings as + /// \return A pointer to a ProgramState object that contains the same bindings as /// \c state with the addition of having the value specified by \c val bound /// to the location given for \c loc. virtual StoreRef Bind(Store store, Loc loc, SVal val) = 0; @@ -73,7 +73,7 @@ public: /// for the compound literal and 'BegInit' and 'EndInit' represent an /// array of initializer values. virtual StoreRef BindCompoundLiteral(Store store, - const CompoundLiteralExpr* cl, + const CompoundLiteralExpr *cl, const LocationContext *LC, SVal v) = 0; /// getInitialStore - Returns the initial "empty" store representing the @@ -97,16 +97,16 @@ public: return svalBuilder.makeLoc(MRMgr.getStringRegion(S)); } - Loc getLValueCompoundLiteral(const CompoundLiteralExpr* CL, + Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL, const LocationContext *LC) { return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)); } - virtual SVal getLValueIvar(const ObjCIvarDecl* decl, SVal base) { + virtual SVal getLValueIvar(const ObjCIvarDecl *decl, SVal base) { return getLValueFieldOrIvar(decl, base); } - virtual SVal getLValueField(const FieldDecl* D, SVal Base) { + virtual SVal getLValueField(const FieldDecl *D, SVal Base) { return getLValueFieldOrIvar(D, Base); } @@ -114,7 +114,7 @@ public: // FIXME: This should soon be eliminated altogether; clients should deal with // region extents directly. - virtual DefinedOrUnknownSVal getSizeInElements(const GRState *state, + virtual DefinedOrUnknownSVal getSizeInElements(const ProgramState *state, const MemRegion *region, QualType EleTy) { return UnknownVal(); @@ -130,12 +130,12 @@ public: } class CastResult { - const GRState *state; + const ProgramState *state; const MemRegion *region; public: - const GRState *getState() const { return state; } + const ProgramState *getState() const { return state; } const MemRegion* getRegion() const { return region; } - CastResult(const GRState *s, const MemRegion* r = 0) : state(s), region(r){} + CastResult(const ProgramState *s, const MemRegion* r = 0) : state(s), region(r){} }; const ElementRegion *GetElementZeroRegion(const MemRegion *R, QualType T); @@ -146,13 +146,15 @@ public: const MemRegion *castRegion(const MemRegion *region, QualType CastToTy); virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, - SymbolReaper& SymReaper, - llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) = 0; + SymbolReaper& SymReaper) = 0; virtual StoreRef BindDecl(Store store, const VarRegion *VR, SVal initVal) = 0; virtual StoreRef BindDeclWithNoInit(Store store, const VarRegion *VR) = 0; + virtual bool includedInBindings(Store store, + const MemRegion *region) const = 0; + /// If the StoreManager supports it, increment the reference count of /// the specified Store object. virtual void incrementReferenceCount(Store store) {} @@ -163,7 +165,7 @@ public: virtual void decrementReferenceCount(Store store) {} typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols; - typedef llvm::SmallVector<const MemRegion *, 8> InvalidatedRegions; + typedef 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 @@ -185,19 +187,18 @@ public: /// even if they do not currently have bindings. Pass \c NULL if this /// information will not be used. virtual StoreRef invalidateRegions(Store store, - const MemRegion * const *Begin, - const MemRegion * const *End, + ArrayRef<const MemRegion *> Regions, const Expr *E, unsigned Count, InvalidatedSymbols &IS, bool invalidateGlobals, - InvalidatedRegions *Regions) = 0; + InvalidatedRegions *Invalidated) = 0; /// enterStackFrame - Let the StoreManager to do something when execution /// engine is about to execute into a callee. - virtual StoreRef enterStackFrame(const GRState *state, + virtual StoreRef enterStackFrame(const ProgramState *state, const StackFrameContext *frame); - virtual void print(Store store, llvm::raw_ostream& Out, + virtual void print(Store store, raw_ostream &Out, const char* nl, const char *sep) = 0; class BindingsHandler { @@ -217,11 +218,11 @@ protected: /// CastRetrievedVal - Used by subclasses of StoreManager to implement /// implicit casts that arise from loads from regions that are reinterpreted /// as another region. - SVal CastRetrievedVal(SVal val, const TypedRegion *region, QualType castTy, - bool performTestOnly = true); + SVal CastRetrievedVal(SVal val, const TypedValueRegion *region, + QualType castTy, bool performTestOnly = true); private: - SVal getLValueFieldOrIvar(const Decl* decl, SVal base); + SVal getLValueFieldOrIvar(const Decl *decl, SVal base); }; @@ -269,11 +270,9 @@ public: virtual bool iterSubRegions(const MemRegion *region, Visitor& V) const = 0; }; -// FIXME: Do we need to pass GRStateManager anymore? -StoreManager *CreateBasicStoreManager(GRStateManager& StMgr); -StoreManager *CreateRegionStoreManager(GRStateManager& StMgr); -StoreManager *CreateFieldsOnlyRegionStoreManager(GRStateManager& StMgr); -StoreManager *CreateFlatStoreManager(GRStateManager &StMgr); +// FIXME: Do we need to pass ProgramStateManager anymore? +StoreManager *CreateRegionStoreManager(ProgramStateManager& StMgr); +StoreManager *CreateFieldsOnlyRegionStoreManager(ProgramStateManager& StMgr); } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h b/include/clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h index 0662eadc93c3..d5ba003a6915 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h @@ -23,7 +23,7 @@ namespace ento { /// locations to values. At a high-level, it represents the symbolic /// memory model. Different subclasses of StoreManager may choose /// different types to represent the locations and values. -typedef const void* Store; +typedef const void *Store; class StoreManager; @@ -44,6 +44,7 @@ public: ~StoreRef(); Store getStore() const { return store; } + const StoreManager &getStoreManager() const { return mgr; } }; }} diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h index 1f6ea3d8c732..ae212bcf5ddf 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h @@ -30,8 +30,8 @@ template <typename PP> class GenericNodeBuilder; class AnalysisManager; class ExplodedNodeSet; class ExplodedNode; -class GRState; -class GRStateManager; +class ProgramState; +class ProgramStateManager; class BlockCounter; class StmtNodeBuilder; class BranchNodeBuilder; @@ -46,11 +46,11 @@ class SubEngine { public: virtual ~SubEngine() {} - virtual const GRState* getInitialState(const LocationContext *InitLoc) = 0; + virtual const ProgramState *getInitialState(const LocationContext *InitLoc) = 0; virtual AnalysisManager &getAnalysisManager() = 0; - virtual GRStateManager &getStateManager() = 0; + virtual ProgramStateManager &getStateManager() = 0; /// Called by CoreEngine. Used to generate new successor /// nodes by processing the 'effects' of a block-level statement. @@ -64,7 +64,7 @@ public: /// Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a branch condition. - virtual void processBranch(const Stmt* Condition, const Stmt* Term, + virtual void processBranch(const Stmt *Condition, const Stmt *Term, BranchNodeBuilder& builder) = 0; /// Called by CoreEngine. Used to generate successor @@ -87,28 +87,32 @@ public: /// Called by ConstraintManager. Used to call checker-specific /// logic for handling assumptions on symbolic values. - virtual const GRState* processAssume(const GRState *state, + virtual const ProgramState *processAssume(const ProgramState *state, SVal cond, bool assumption) = 0; - /// wantsRegionChangeUpdate - Called by GRStateManager to determine if a + /// wantsRegionChangeUpdate - Called by ProgramStateManager to determine if a /// region change should trigger a processRegionChanges update. - virtual bool wantsRegionChangeUpdate(const GRState* state) = 0; + virtual bool wantsRegionChangeUpdate(const ProgramState *state) = 0; - /// processRegionChanges - Called by GRStateManager whenever a change is made + /// processRegionChanges - Called by ProgramStateManager whenever a change is made /// to the store. Used to update checkers that track region values. - virtual const GRState * - processRegionChanges(const GRState *state, + virtual const ProgramState * + processRegionChanges(const ProgramState *state, const StoreManager::InvalidatedSymbols *invalidated, - const MemRegion* const *Begin, - const MemRegion* const *End) = 0; + ArrayRef<const MemRegion *> ExplicitRegions, + ArrayRef<const MemRegion *> Regions) = 0; - inline const GRState * - processRegionChange(const GRState* state, + inline const ProgramState * + processRegionChange(const ProgramState *state, const MemRegion* MR) { - return processRegionChanges(state, 0, &MR, &MR+1); + return processRegionChanges(state, 0, MR, MR); } + /// printState - Called by ProgramStateManager to print checker-specific data. + virtual void printState(raw_ostream &Out, const ProgramState *State, + const char *NL, const char *Sep) = 0; + /// Called by CoreEngine 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/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h index ad173bb43536..0d6e18eb3cc8 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -18,13 +18,15 @@ #include "clang/AST/Decl.h" #include "clang/AST/Expr.h" #include "clang/Analysis/AnalysisContext.h" +#include "clang/Basic/LLVM.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" #include "llvm/Support/DataTypes.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DenseMap.h" namespace llvm { class BumpPtrAllocator; -class raw_ostream; } namespace clang { @@ -35,15 +37,15 @@ namespace ento { class BasicValueFactory; class MemRegion; class SubRegion; - class TypedRegion; + class TypedValueRegion; class VarRegion; class SymExpr : public llvm::FoldingSetNode { public: - enum Kind { BEGIN_SYMBOLS, - RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, + enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, MetadataKind, - END_SYMBOLS, + BEGIN_SYMBOLS = RegionValueKind, + END_SYMBOLS = MetadataKind, SymIntKind, SymSymKind }; private: Kind K; @@ -58,7 +60,7 @@ public: void dump() const; - virtual void dumpToStream(llvm::raw_ostream &os) const = 0; + virtual void dumpToStream(raw_ostream &os) const = 0; virtual QualType getType(ASTContext&) const = 0; virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; @@ -82,25 +84,26 @@ public: SymbolID getSymbolID() const { return Sym; } // Implement isa<T> support. - static inline bool classof(const SymExpr* SE) { + static inline bool classof(const SymExpr *SE) { Kind k = SE->getKind(); - return k > BEGIN_SYMBOLS && k < END_SYMBOLS; + return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; } }; typedef const SymbolData* SymbolRef; +typedef llvm::SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy; -// A symbol representing the value of a MemRegion. +/// A symbol representing the value of a MemRegion. class SymbolRegionValue : public SymbolData { - const TypedRegion *R; + const TypedValueRegion *R; public: - SymbolRegionValue(SymbolID sym, const TypedRegion *r) + SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) : SymbolData(RegionValueKind, sym), R(r) {} - const TypedRegion* getRegion() const { return R; } + const TypedValueRegion* getRegion() const { return R; } - static void Profile(llvm::FoldingSetNodeID& profile, const TypedRegion* R) { + static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { profile.AddInteger((unsigned) RegionValueKind); profile.AddPointer(R); } @@ -109,39 +112,39 @@ public: Profile(profile, R); } - void dumpToStream(llvm::raw_ostream &os) const; + void dumpToStream(raw_ostream &os) const; QualType getType(ASTContext&) const; // Implement isa<T> support. - static inline bool classof(const SymExpr* SE) { + static inline bool classof(const SymExpr *SE) { return SE->getKind() == RegionValueKind; } }; -// A symbol representing the result of an expression. +/// A symbol representing the result of an expression. class SymbolConjured : public SymbolData { - const Stmt* S; + const Stmt *S; QualType T; unsigned Count; - const void* SymbolTag; + const void *SymbolTag; public: - SymbolConjured(SymbolID sym, const Stmt* s, QualType t, unsigned count, - const void* symbolTag) + SymbolConjured(SymbolID sym, const Stmt *s, QualType t, unsigned count, + const void *symbolTag) : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), SymbolTag(symbolTag) {} - const Stmt* getStmt() const { return S; } + const Stmt *getStmt() const { return S; } unsigned getCount() const { return Count; } - const void* getTag() const { return SymbolTag; } + const void *getTag() const { return SymbolTag; } QualType getType(ASTContext&) const; - void dumpToStream(llvm::raw_ostream &os) const; + void dumpToStream(raw_ostream &os) const; - static void Profile(llvm::FoldingSetNodeID& profile, const Stmt* S, - QualType T, unsigned Count, const void* SymbolTag) { + static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, + QualType T, unsigned Count, const void *SymbolTag) { profile.AddInteger((unsigned) ConjuredKind); profile.AddPointer(S); profile.Add(T); @@ -154,30 +157,30 @@ public: } // Implement isa<T> support. - static inline bool classof(const SymExpr* SE) { + static inline bool classof(const SymExpr *SE) { return SE->getKind() == ConjuredKind; } }; -// A symbol representing the value of a MemRegion whose parent region has -// symbolic value. +/// A symbol representing the value of a MemRegion whose parent region has +/// symbolic value. class SymbolDerived : public SymbolData { SymbolRef parentSymbol; - const TypedRegion *R; + const TypedValueRegion *R; public: - SymbolDerived(SymbolID sym, SymbolRef parent, const TypedRegion *r) + SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} SymbolRef getParentSymbol() const { return parentSymbol; } - const TypedRegion *getRegion() const { return R; } + const TypedValueRegion *getRegion() const { return R; } QualType getType(ASTContext&) const; - void dumpToStream(llvm::raw_ostream &os) const; + void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, - const TypedRegion *r) { + const TypedValueRegion *r) { profile.AddInteger((unsigned) DerivedKind); profile.AddPointer(r); profile.AddPointer(parent); @@ -188,7 +191,7 @@ public: } // Implement isa<T> support. - static inline bool classof(const SymExpr* SE) { + static inline bool classof(const SymExpr *SE) { return SE->getKind() == DerivedKind; } }; @@ -207,7 +210,7 @@ public: QualType getType(ASTContext&) const; - void dumpToStream(llvm::raw_ostream &os) const; + void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { profile.AddInteger((unsigned) ExtentKind); @@ -219,7 +222,7 @@ public: } // Implement isa<T> support. - static inline bool classof(const SymExpr* SE) { + static inline bool classof(const SymExpr *SE) { return SE->getKind() == ExtentKind; } }; @@ -230,23 +233,23 @@ public: /// Intended for use by checkers. class SymbolMetadata : public SymbolData { const MemRegion* R; - const Stmt* S; + const Stmt *S; QualType T; unsigned Count; - const void* Tag; + const void *Tag; public: - SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt* s, QualType t, - unsigned count, const void* tag) + 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; } + const Stmt *getStmt() const { return S; } unsigned getCount() const { return Count; } - const void* getTag() const { return Tag; } + const void *getTag() const { return Tag; } QualType getType(ASTContext&) const; - void dumpToStream(llvm::raw_ostream &os) const; + void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, const Stmt *S, QualType T, unsigned Count, @@ -264,12 +267,12 @@ public: } // Implement isa<T> support. - static inline bool classof(const SymExpr* SE) { + static inline bool classof(const SymExpr *SE) { return SE->getKind() == MetadataKind; } }; -// SymIntExpr - Represents symbolic expression like 'x' + 3. +/// SymIntExpr - Represents symbolic expression like 'x' + 3. class SymIntExpr : public SymExpr { const SymExpr *LHS; BinaryOperator::Opcode Op; @@ -283,11 +286,11 @@ public: // FIXME: We probably need to make this out-of-line to avoid redundant // generation of virtual functions. - QualType getType(ASTContext& C) const { return T; } + QualType getType(ASTContext &C) const { return T; } BinaryOperator::Opcode getOpcode() const { return Op; } - void dumpToStream(llvm::raw_ostream &os) const; + void dumpToStream(raw_ostream &os) const; const SymExpr *getLHS() const { return LHS; } const llvm::APSInt &getRHS() const { return RHS; } @@ -307,12 +310,12 @@ public: } // Implement isa<T> support. - static inline bool classof(const SymExpr* SE) { + static inline bool classof(const SymExpr *SE) { return SE->getKind() == SymIntKind; } }; -// SymSymExpr - Represents symbolic expression like 'x' + 'y'. +/// SymSymExpr - Represents symbolic expression like 'x' + 'y'. class SymSymExpr : public SymExpr { const SymExpr *LHS; BinaryOperator::Opcode Op; @@ -330,9 +333,9 @@ public: // FIXME: We probably need to make this out-of-line to avoid redundant // generation of virtual functions. - QualType getType(ASTContext& C) const { return T; } + QualType getType(ASTContext &C) const { return T; } - void dumpToStream(llvm::raw_ostream &os) const; + void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { @@ -348,48 +351,58 @@ public: } // Implement isa<T> support. - static inline bool classof(const SymExpr* SE) { + static inline bool classof(const SymExpr *SE) { return SE->getKind() == SymSymKind; } }; class SymbolManager { typedef llvm::FoldingSet<SymExpr> DataSetTy; + typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; + DataSetTy DataSet; + /// Stores the extra dependencies between symbols: the data should be kept + /// alive as long as the key is live. + SymbolDependTy SymbolDependencies; unsigned SymbolCounter; llvm::BumpPtrAllocator& BPAlloc; BasicValueFactory &BV; - ASTContext& Ctx; + ASTContext &Ctx; public: - SymbolManager(ASTContext& ctx, BasicValueFactory &bv, + SymbolManager(ASTContext &ctx, BasicValueFactory &bv, llvm::BumpPtrAllocator& bpalloc) - : SymbolCounter(0), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} + : SymbolDependencies(16), SymbolCounter(0), + BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} ~SymbolManager(); static bool canSymbolicate(QualType T); - /// Make a unique symbol for MemRegion R according to its kind. - const SymbolRegionValue* getRegionValueSymbol(const TypedRegion* R); + /// \brief Make a unique symbol for MemRegion R according to its kind. + const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); - const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T, + const SymbolConjured* getConjuredSymbol(const Stmt *E, QualType T, unsigned VisitCount, - const void* SymbolTag = 0); + const void *SymbolTag = 0); - const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount, - const void* SymbolTag = 0) { + const SymbolConjured* getConjuredSymbol(const Expr *E, unsigned VisitCount, + const void *SymbolTag = 0) { return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag); } const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, - const TypedRegion *R); + const TypedValueRegion *R); const SymbolExtent *getExtentSymbol(const SubRegion *R); - const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt* S, + /// \brief Creates a metadata symbol associated with a specific region. + /// + /// VisitCount can be used to differentiate regions corresponding to + /// different loop iterations, thus, making the symbol path-dependent. + const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, unsigned VisitCount, - const void* SymbolTag = 0); + const void *SymbolTag = 0); const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const llvm::APSInt& rhs, QualType t); @@ -406,23 +419,43 @@ public: return SE->getType(Ctx); } + /// \brief Add artificial symbol dependency. + /// + /// The dependent symbol should stay alive as long as the primary is alive. + void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); + + const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); + ASTContext &getContext() { return Ctx; } BasicValueFactory &getBasicVals() { return BV; } }; class SymbolReaper { - typedef llvm::DenseSet<SymbolRef> SetTy; + enum SymbolStatus { + NotProcessed, + HaveMarkedDependents + }; - SetTy TheLiving; - SetTy MetadataInUse; - SetTy TheDead; + typedef llvm::DenseSet<SymbolRef> SymbolSetTy; + typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; + typedef llvm::DenseSet<const MemRegion *> RegionSetTy; + + SymbolMapTy TheLiving; + SymbolSetTy MetadataInUse; + SymbolSetTy TheDead; + + RegionSetTy RegionRoots; + const LocationContext *LCtx; const Stmt *Loc; SymbolManager& SymMgr; + StoreRef reapedStore; + llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; public: - SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr) - : LCtx(ctx), Loc(s), SymMgr(symmgr) {} + SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr, + StoreManager &storeMgr) + : LCtx(ctx), Loc(s), SymMgr(symmgr), reapedStore(0, storeMgr) {} ~SymbolReaper() {} @@ -430,48 +463,71 @@ public: const Stmt *getCurrentStatement() const { return Loc; } bool isLive(SymbolRef sym); + bool isLiveRegion(const MemRegion *region); bool isLive(const Stmt *ExprVal) const; - bool isLive(const VarRegion *VR) const; + bool isLive(const VarRegion *VR, bool includeStoreBindings = false) 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. + /// \brief 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. + /// \brief 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. + /// \brief 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; + typedef SymbolSetTy::const_iterator dead_iterator; dead_iterator dead_begin() const { return TheDead.begin(); } dead_iterator dead_end() const { return TheDead.end(); } 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.) + + typedef RegionSetTy::const_iterator region_iterator; + region_iterator region_begin() const { return RegionRoots.begin(); } + region_iterator region_end() const { return RegionRoots.end(); } + + /// \brief 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); } + + void markLive(const MemRegion *region); + + /// \brief Set to the value of the symbolic store after + /// StoreManager::removeDeadBindings has been called. + void setReapedStore(StoreRef st) { reapedStore = st; } + +private: + /// Mark the symbols dependent on the input symbol as live. + void markDependentsLive(SymbolRef sym); }; class SymbolVisitor { public: - // VisitSymbol - A visitor method invoked by - // GRStateManager::scanReachableSymbols. The method returns \c true if - // symbols should continue be scanned and \c false otherwise. + /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. + /// + /// The method returns \c true if symbols should continue be scanned and \c + /// false otherwise. virtual bool VisitSymbol(SymbolRef sym) = 0; + virtual bool VisitMemRegion(const MemRegion *region) { return true; } virtual ~SymbolVisitor(); }; @@ -480,7 +536,7 @@ public: } // end clang namespace namespace llvm { -static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, +static inline raw_ostream &operator<<(raw_ostream &os, const clang::ento::SymExpr *SE) { SE->dumpToStream(os); return os; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h b/include/clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h deleted file mode 100644 index 23ed2be8c7a4..000000000000 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h +++ /dev/null @@ -1,93 +0,0 @@ -//== TransferFuncs.h - Path-Sens. Transfer Functions Interface ---*- 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 TransferFuncs, which provides a base-class that -// defines an interface for transfer functions used by ExprEngine. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_GR_TRANSFERFUNCS -#define LLVM_CLANG_GR_TRANSFERFUNCS - -#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" -#include <vector> - -namespace clang { -class ObjCMessageExpr; - -namespace ento { -class ExplodedNode; -class ExplodedNodeSet; -class EndOfFunctionNodeBuilder; -class ExprEngine; -class StmtNodeBuilder; -class StmtNodeBuilderRef; - -class TransferFuncs { -public: - TransferFuncs() {} - virtual ~TransferFuncs() {} - - virtual void RegisterPrinters(std::vector<GRState::Printer*>& Printers) {} - virtual void RegisterChecks(ExprEngine& Eng) {} - - - // Calls. - - virtual void evalCall(ExplodedNodeSet& Dst, - ExprEngine& Engine, - StmtNodeBuilder& Builder, - const CallExpr* CE, SVal L, - ExplodedNode* Pred) {} - - virtual void evalObjCMessage(ExplodedNodeSet& Dst, - ExprEngine& Engine, - StmtNodeBuilder& Builder, - ObjCMessage msg, - ExplodedNode* Pred, - const GRState *state) {} - - // Stores. - - virtual void evalBind(StmtNodeBuilderRef& B, SVal location, SVal val) {} - - // End-of-path and dead symbol notification. - - virtual void evalEndPath(ExprEngine& Engine, - EndOfFunctionNodeBuilder& Builder) {} - - - virtual void evalDeadSymbols(ExplodedNodeSet& Dst, - ExprEngine& Engine, - StmtNodeBuilder& Builder, - ExplodedNode* Pred, - const GRState* state, - SymbolReaper& SymReaper) {} - - // Return statements. - virtual void evalReturn(ExplodedNodeSet& Dst, - ExprEngine& Engine, - StmtNodeBuilder& Builder, - const ReturnStmt* S, - ExplodedNode* Pred) {} - - // Assumptions. - virtual const GRState* evalAssume(const GRState *state, - SVal Cond, bool Assumption) { - return state; - } -}; - -} // end GR namespace - -} // end clang namespace - -#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h b/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h index 6bc9fe56f8d6..fa340753e5b7 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h @@ -28,20 +28,20 @@ class ExplodedNode; class ExplodedNodeImpl; class WorkListUnit { - ExplodedNode* node; + ExplodedNode *node; BlockCounter counter; - const CFGBlock* block; + const CFGBlock *block; unsigned blockIdx; // This is the index of the next statement. public: - WorkListUnit(ExplodedNode* N, BlockCounter C, - const CFGBlock* B, unsigned idx) + WorkListUnit(ExplodedNode *N, BlockCounter C, + const CFGBlock *B, unsigned idx) : node(N), counter(C), block(B), blockIdx(idx) {} - explicit WorkListUnit(ExplodedNode* N, BlockCounter C) + explicit WorkListUnit(ExplodedNode *N, BlockCounter C) : node(N), counter(C), block(NULL), |