diff options
-rw-r--r-- | include/clang/Analysis/PathSensitive/BugReporter.h | 79 | ||||
-rw-r--r-- | include/clang/Analysis/PathSensitive/ExplodedGraph.h | 14 | ||||
-rw-r--r-- | include/clang/Analysis/PathSensitive/GRCoreEngine.h | 68 | ||||
-rw-r--r-- | include/clang/Analysis/PathSensitive/GRExprEngine.h | 74 | ||||
-rw-r--r-- | include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h | 4 | ||||
-rw-r--r-- | include/clang/Analysis/PathSensitive/GRTransferFuncs.h | 2 | ||||
-rw-r--r-- | lib/Analysis/BasicObjCFoundationChecks.cpp | 92 | ||||
-rw-r--r-- | lib/Analysis/BugReporter.cpp | 76 | ||||
-rw-r--r-- | lib/Analysis/CFRefCount.cpp | 12 | ||||
-rw-r--r-- | lib/Analysis/GRExprEngine.cpp | 62 | ||||
-rw-r--r-- | lib/Analysis/GRSimpleVals.cpp | 308 | ||||
-rw-r--r-- | lib/Analysis/GRSimpleVals.h | 2 |
12 files changed, 474 insertions, 319 deletions
diff --git a/include/clang/Analysis/PathSensitive/BugReporter.h b/include/clang/Analysis/PathSensitive/BugReporter.h index 7ff79fc53d..9f8b17ac00 100644 --- a/include/clang/Analysis/PathSensitive/BugReporter.h +++ b/include/clang/Analysis/PathSensitive/BugReporter.h @@ -19,9 +19,6 @@ #include "clang/Analysis/PathSensitive/ExplodedGraph.h" #include "llvm/ADT/SmallPtrSet.h" -// FIXME: ExplodedGraph<> should be templated on state, not the checker engine. -#include "clang/Analysis/PathSensitive/GRExprEngine.h" - namespace clang { class PathDiagnostic; @@ -29,61 +26,79 @@ class PathDiagnosticPiece; class PathDiagnosticClient; class ASTContext; class Diagnostic; - -class BugDescription { +class BugReporter; +class GRExprEngine; +class ValueState; + +class BugType { public: - BugDescription() {} - virtual ~BugDescription() {} + BugType() {} + virtual ~BugType(); virtual const char* getName() const = 0; + virtual const char* getDescription() const { return getName(); } + + virtual void EmitWarnings(BugReporter& BR) {} +}; - virtual const char* getDescription() const = 0; +class BugReport { + const BugType& Desc; + +public: + BugReport(const BugType& D) : Desc(D) {} + virtual ~BugReport(); + + const BugType& getBugType() const { return Desc; } + + const char* getName() const { return getBugType().getName(); } + const char* getDescription() const { return getBugType().getDescription(); } virtual PathDiagnosticPiece* getEndPath(ASTContext& Ctx, ExplodedNode<ValueState> *N) const; virtual void getRanges(const SourceRange*& beg, const SourceRange*& end) const; -}; - -class BugReporterHelper { -public: - virtual ~BugReporterHelper() {} virtual PathDiagnosticPiece* VisitNode(ExplodedNode<ValueState>* N, ExplodedNode<ValueState>* PrevN, - ExplodedGraph<GRExprEngine>& G, - ASTContext& Ctx) = 0; + ExplodedGraph<ValueState>& G, + ASTContext& Ctx); }; class BugReporter { llvm::SmallPtrSet<void*,10> CachedErrors; + Diagnostic& Diag; + PathDiagnosticClient* PD; + ASTContext& Ctx; + GRExprEngine& Eng; public: - BugReporter() {} + BugReporter(Diagnostic& diag, PathDiagnosticClient* pd, + ASTContext& ctx, GRExprEngine& eng) + : Diag(diag), PD(pd), Ctx(ctx), Eng(eng) {} + ~BugReporter(); - void EmitPathWarning(Diagnostic& Diag, PathDiagnosticClient* PDC, - ASTContext& Ctx, const BugDescription& B, - ExplodedGraph<GRExprEngine>& G, - ExplodedNode<ValueState>* N, - BugReporterHelper** BegHelpers = NULL, - BugReporterHelper** EndHelpers = NULL); + Diagnostic& getDiagnostic() { return Diag; } + + PathDiagnosticClient* getDiagnosticClient() { return PD; } - void EmitWarning(Diagnostic& Diag, ASTContext& Ctx, - const BugDescription& B, - ExplodedNode<ValueState>* N); + ASTContext& getContext() { return Ctx; } + ExplodedGraph<ValueState>& getGraph(); -private: + GRExprEngine& getEngine() { return Eng; } + + void EmitPathWarning(BugReport& R, ExplodedNode<ValueState>* N); + + void EmitWarning(BugReport& R, ExplodedNode<ValueState>* N); + + void clearCache() { CachedErrors.clear(); } + bool IsCached(ExplodedNode<ValueState>* N); - void GeneratePathDiagnostic(PathDiagnostic& PD, ASTContext& Ctx, - const BugDescription& B, - ExplodedGraph<GRExprEngine>& G, - ExplodedNode<ValueState>* N, - BugReporterHelper** BegHelpers = NULL, - BugReporterHelper** EndHelpers = NULL); + void GeneratePathDiagnostic(PathDiagnostic& PD, BugReport& R, + ExplodedNode<ValueState>* N); }; } // end clang namespace diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h index 30d95605ea..8db069639b 100644 --- a/include/clang/Analysis/PathSensitive/ExplodedGraph.h +++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h @@ -278,17 +278,14 @@ public: }; -template <typename CHECKER> +template <typename STATE> class ExplodedGraph : public ExplodedGraphImpl { public: - typedef CHECKER CheckerTy; - typedef typename CHECKER::StateTy StateTy; + typedef STATE StateTy; typedef ExplodedNode<StateTy> NodeTy; typedef llvm::FoldingSet<NodeTy> AllNodesTy; protected: - llvm::OwningPtr<CheckerTy> CheckerState; - /// Nodes - The nodes in the graph. AllNodesTy Nodes; @@ -305,12 +302,7 @@ protected: public: ExplodedGraph(CFG& c, Decl& cd, ASTContext& ctx) - : ExplodedGraphImpl(c, cd, ctx), CheckerState(new CheckerTy(*this)) {} - - /// getCheckerState - Returns the internal checker state associated - /// with the exploded graph. Ownership remains with the ExplodedGraph - /// objecct. - CheckerTy* getCheckerState() const { return CheckerState.get(); } + : ExplodedGraphImpl(c, cd, ctx) {} /// getNode - Retrieve the node associated with a (Location,State) pair, /// where the 'Location' is a ProgramPoint in the CFG. If no node for diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h index 35fddadf33..5b7aeb5975 100644 --- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h +++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h @@ -111,7 +111,7 @@ protected: 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(unsigned Steps = 1000000); + bool ExecuteWorkList(unsigned Steps); virtual ~GRCoreEngineImpl() {} @@ -309,11 +309,10 @@ public: } }; -template<typename CHECKER> +template<typename STATE> class GRBranchNodeBuilder { - typedef CHECKER CheckerTy; - typedef typename CheckerTy::StateTy StateTy; - typedef ExplodedGraph<CheckerTy> GraphTy; + typedef STATE StateTy; + typedef ExplodedGraph<StateTy> GraphTy; typedef typename GraphTy::NodeTy NodeTy; GRBranchNodeBuilderImpl& NB; @@ -392,11 +391,10 @@ public: inline void* getState() const { return Pred->State; } }; -template<typename CHECKER> +template<typename STATE> class GRIndirectGotoNodeBuilder { - typedef CHECKER CheckerTy; - typedef typename CheckerTy::StateTy StateTy; - typedef ExplodedGraph<CheckerTy> GraphTy; + typedef STATE StateTy; + typedef ExplodedGraph<StateTy> GraphTy; typedef typename GraphTy::NodeTy NodeTy; GRIndirectGotoNodeBuilderImpl& NB; @@ -459,11 +457,10 @@ public: inline void* getState() const { return Pred->State; } }; -template<typename CHECKER> +template<typename STATE> class GRSwitchNodeBuilder { - typedef CHECKER CheckerTy; - typedef typename CheckerTy::StateTy StateTy; - typedef ExplodedGraph<CheckerTy> GraphTy; + typedef STATE StateTy; + typedef ExplodedGraph<StateTy> GraphTy; typedef typename GraphTy::NodeTy NodeTy; GRSwitchNodeBuilderImpl& NB; @@ -492,21 +489,19 @@ public: }; -template<typename CHECKER> +template<typename SUBENGINE> class GRCoreEngine : public GRCoreEngineImpl { public: - typedef CHECKER CheckerTy; - typedef typename CheckerTy::StateTy StateTy; - typedef ExplodedGraph<CheckerTy> GraphTy; + typedef SUBENGINE SubEngineTy; + typedef typename SubEngineTy::StateTy StateTy; + typedef ExplodedGraph<StateTy> GraphTy; typedef typename GraphTy::NodeTy NodeTy; protected: - // A local reference to the checker that avoids an indirect access - // via the Graph. - CheckerTy* Checker; + SubEngineTy& SubEngine; virtual void* getInitialState() { - return getCheckerState().getInitialState(); + return SubEngine.getInitialState(); } virtual void* ProcessEOP(CFGBlock* Blk, void* State) { @@ -516,44 +511,44 @@ protected: virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilderImpl& BuilderImpl) { GRStmtNodeBuilder<StateTy> Builder(BuilderImpl); - Checker->ProcessStmt(S, Builder); + SubEngine.ProcessStmt(S, Builder); } virtual bool ProcessBlockEntrance(CFGBlock* Blk, void* State, GRBlockCounter BC) { - return Checker->ProcessBlockEntrance(Blk, - static_cast<StateTy*>(State), BC); + return SubEngine.ProcessBlockEntrance(Blk, static_cast<StateTy*>(State),BC); } virtual void ProcessBranch(Expr* Condition, Stmt* Terminator, GRBranchNodeBuilderImpl& BuilderImpl) { - GRBranchNodeBuilder<CHECKER> Builder(BuilderImpl); - Checker->ProcessBranch(Condition, Terminator, Builder); + GRBranchNodeBuilder<StateTy> Builder(BuilderImpl); + SubEngine.ProcessBranch(Condition, Terminator, Builder); } virtual void ProcessIndirectGoto(GRIndirectGotoNodeBuilderImpl& BuilderImpl) { - GRIndirectGotoNodeBuilder<CHECKER> Builder(BuilderImpl); - Checker->ProcessIndirectGoto(Builder); + GRIndirectGotoNodeBuilder<StateTy> Builder(BuilderImpl); + SubEngine.ProcessIndirectGoto(Builder); } virtual void ProcessSwitch(GRSwitchNodeBuilderImpl& BuilderImpl) { - GRSwitchNodeBuilder<CHECKER> Builder(BuilderImpl); - Checker->ProcessSwitch(Builder); + GRSwitchNodeBuilder<StateTy> Builder(BuilderImpl); + SubEngine.ProcessSwitch(Builder); } public: /// Construct a GRCoreEngine object to analyze the provided CFG using /// a DFS exploration of the exploded graph. - GRCoreEngine(CFG& cfg, Decl& cd, ASTContext& ctx) + GRCoreEngine(CFG& cfg, Decl& cd, ASTContext& ctx, SubEngineTy& subengine) : GRCoreEngineImpl(new GraphTy(cfg, cd, ctx), GRWorkList::MakeDFS()), - Checker(static_cast<GraphTy*>(G.get())->getCheckerState()) {} + SubEngine(subengine) {} /// Construct a GRCoreEngine object to analyze the provided CFG and to /// use the provided worklist object to execute the worklist algorithm. /// The GRCoreEngine object assumes ownership of 'wlist'. - GRCoreEngine(CFG& cfg, Decl& cd, ASTContext& ctx, GRWorkList* wlist) + GRCoreEngine(CFG& cfg, Decl& cd, ASTContext& ctx, GRWorkList* wlist, + SubEngineTy& subengine) : GRCoreEngineImpl(new GraphTy(cfg, cd, ctx), wlist), - Checker(static_cast<GraphTy*>(G.get())->getCheckerState()) {} + SubEngine(subengine) {} virtual ~GRCoreEngine() {} @@ -562,11 +557,6 @@ public: return *static_cast<GraphTy*>(G.get()); } - /// getCheckerState - Returns the internal checker state. - CheckerTy& getCheckerState() { - return *Checker; - } - /// takeGraph - Returns the exploded graph. Ownership of the graph is /// transfered to the caller. GraphTy* takeGraph() { diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index e88b377a97..473b658b67 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -21,26 +21,30 @@ #include "clang/Analysis/PathSensitive/GRSimpleAPICheck.h" #include "clang/Analysis/PathSensitive/GRTransferFuncs.h" -namespace clang { +namespace clang { - class StatelessChecks; + class BugType; + class PathDiagnosticClient; + class Diagnostic; class GRExprEngine { public: typedef ValueState StateTy; - typedef ExplodedGraph<GRExprEngine> GraphTy; + typedef ExplodedGraph<StateTy> GraphTy; typedef GraphTy::NodeTy NodeTy; // Builders. - typedef GRStmtNodeBuilder<StateTy> StmtNodeBuilder; - typedef GRBranchNodeBuilder<GRExprEngine> BranchNodeBuilder; - typedef GRIndirectGotoNodeBuilder<GRExprEngine> IndirectGotoNodeBuilder; - typedef GRSwitchNodeBuilder<GRExprEngine> SwitchNodeBuilder; - typedef ExplodedNodeSet<StateTy> NodeSet; + typedef GRStmtNodeBuilder<StateTy> StmtNodeBuilder; + typedef GRBranchNodeBuilder<StateTy> BranchNodeBuilder; + typedef GRIndirectGotoNodeBuilder<StateTy> IndirectGotoNodeBuilder; + typedef GRSwitchNodeBuilder<StateTy> SwitchNodeBuilder; + typedef ExplodedNodeSet<StateTy> NodeSet; protected: + GRCoreEngine<GRExprEngine> CoreEngine; + /// G - the simulation graph. GraphTy& G; @@ -62,6 +66,10 @@ protected: /// for manipulating and creating RVals. GRTransferFuncs* TF; + /// BugTypes - Objects used for reporting bugs. + typedef std::vector<BugType*> BugTypeSet; + BugTypeSet BugTypes; + /// SymMgr - Object that manages the symbol information. SymbolManager& SymMgr; @@ -154,18 +162,11 @@ protected: UndefArgsTy MsgExprUndefArgs; public: - GRExprEngine(GraphTy& g) : - G(g), Liveness(G.getCFG()), - Builder(NULL), - StateMgr(G.getContext(), G.getAllocator()), - BasicVals(StateMgr.getBasicValueFactory()), - TF(NULL), // FIXME. - SymMgr(StateMgr.getSymbolManager()), - StmtEntryNode(NULL), CleanedState(NULL), CurrentStmt(NULL) { - - // Compute liveness information. - Liveness.runOnCFG(G.getCFG()); - Liveness.runOnAllBlocks(G.getCFG(), NULL, true); + GRExprEngine(CFG& cfg, Decl& CD, ASTContext& Ctx); + ~GRExprEngine(); + + void ExecuteWorkList(unsigned Steps = 150000) { + CoreEngine.ExecuteWorkList(Steps); } /// getContext - Return the ASTContext associated with this analysis. @@ -175,8 +176,11 @@ public: CFG& getCFG() { return G.getCFG(); } /// setTransferFunctions - void setTransferFunctions(GRTransferFuncs* tf) { TF = tf; } - void setTransferFunctions(GRTransferFuncs& tf) { TF = &tf; } + void setTransferFunctions(GRTransferFuncs* tf); + + void setTransferFunctions(GRTransferFuncs& tf) { + setTransferFunctions(&tf); + } /// ViewGraph - Visualize the ExplodedGraph created by executing the /// simulation. @@ -188,6 +192,24 @@ public: /// in the ExplodedGraph. ValueState* getInitialState(); + GraphTy& getGraph() { return G; } + const GraphTy& getGraph() const { return G; } + + typedef BugTypeSet::iterator bug_type_iterator; + typedef BugTypeSet::const_iterator const_bug_type_iterator; + + bug_type_iterator bug_types_begin() { return BugTypes.begin(); } + bug_type_iterator bug_types_end() { return BugTypes.end(); } + + const_bug_type_iterator bug_types_begin() const { return BugTypes.begin(); } + const_bug_type_iterator bug_types_end() const { return BugTypes.end(); } + + void Register(BugType* B) { + BugTypes.push_back(B); + } + + void EmitWarnings(Diagnostic& Diag, PathDiagnosticClient* PD); + bool isRetStackAddr(const NodeTy* N) const { return N->isSink() && RetsStackAddr.count(const_cast<NodeTy*>(N)) != 0; } @@ -317,13 +339,9 @@ public: return MsgExprChecks.end(); } - void AddCallCheck(GRSimpleAPICheck* A) { - CallChecks.push_back(A); - } + void AddCallCheck(GRSimpleAPICheck* A); - void AddObjCMessageExprCheck(GRSimpleAPICheck* A) { - MsgExprChecks.push_back(A); - } + void AddObjCMessageExprCheck(GRSimpleAPICheck* A); /// ProcessStmt - Called by GRCoreEngine. Used to generate new successor /// nodes by processing the 'effects' of a block-level statement. diff --git a/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h b/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h index 16b23c558c..782ddcfffe 100644 --- a/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h +++ b/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h @@ -33,9 +33,7 @@ class GRSimpleAPICheck : public GRAuditor<ValueState> { public: GRSimpleAPICheck() {} virtual ~GRSimpleAPICheck() {} - virtual void ReportResults(Diagnostic& Diag, PathDiagnosticClient* PD, - ASTContext& Ctx, BugReporter& BR, - ExplodedGraph<GRExprEngine>& G) = 0; + virtual void EmitWarnings(BugReporter& BR) = 0; }; } // end namespace clang diff --git a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h index 55a0fae273..9c68f20e74 100644 --- a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h +++ b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h @@ -32,6 +32,8 @@ public: return NULL; } + virtual void RegisterChecks(GRExprEngine& Eng) {} + // Casts. virtual RVal EvalCast(GRExprEngine& Engine, NonLVal V, QualType CastT) =0; diff --git a/lib/Analysis/BasicObjCFoundationChecks.cpp b/lib/Analysis/BasicObjCFoundationChecks.cpp index 6149abefa3..154adcaa47 100644 --- a/lib/Analysis/BasicObjCFoundationChecks.cpp +++ b/lib/Analysis/BasicObjCFoundationChecks.cpp @@ -54,51 +54,61 @@ static const char* GetReceiverNameType(ObjCMessageExpr* ME) { namespace { -class VISIBILITY_HIDDEN NilArg : public BugDescription { - std::string Msg; - const char* s; - SourceRange R; +class VISIBILITY_HIDDEN NilArg : public BugType { public: - NilArg(ObjCMessageExpr* ME, unsigned Arg); virtual ~NilArg() {} virtual const char* getName() const { return "nil argument"; } - virtual const char* getDescription() const { - return s; - } - - virtual void getRanges(const SourceRange*& beg, - const SourceRange*& end) const { - beg = &R; - end = beg+1; - } + class Report : public BugReport { + std::string Msg; + const char* s; + SourceRange R; + public: + Report(NilArg& Desc, ObjCMessageExpr* ME, unsigned Arg) : BugReport(Desc) { + + Expr* E = ME->getArg(Arg); + R = E->getSourceRange(); + + std::ostringstream os; + + os << "Argument to '" << GetReceiverNameType(ME) << "' method '" + << ME->getSelector().getName() << "' cannot be nil."; + + Msg = os.str(); + s = Msg.c_str(); + } + + virtual ~Report() {} + + virtual PathDiagnosticPiece* getEndPath(ASTContext& Ctx, + ExplodedNode<ValueState> *N) const { + + Stmt* S = cast<PostStmt>(N->getLocation()).getStmt(); + + if (!S) + return NULL; + + FullSourceLoc L(S->getLocStart(), Ctx.getSourceManager()); + PathDiagnosticPiece* P = new PathDiagnosticPiece(L, s); + + P->addRange(R); + + return P; + } + }; }; - -NilArg::NilArg(ObjCMessageExpr* ME, unsigned Arg) : s(NULL) { - - Expr* E = ME->getArg(Arg); - R = E->getSourceRange(); - - std::ostringstream os; - - os << "Argument to '" << GetReceiverNameType(ME) << "' method '" - << ME->getSelector().getName() << "' cannot be nil."; - - Msg = os.str(); - s = Msg.c_str(); -} - + class VISIBILITY_HIDDEN BasicObjCFoundationChecks : public GRSimpleAPICheck { - + NilArg Desc; ASTContext &Ctx; ValueStateManager* VMgr; - typedef std::vector<std::pair<NodeTy*,BugDescription*> > ErrorsTy; + typedef std::vector<std::pair<NodeTy*,BugReport*> > ErrorsTy; ErrorsTy Errors; RVal GetRVal(ValueState* St, Expr* E) { return VMgr->GetRVal(St, E); } @@ -122,18 +132,16 @@ public: virtual bool Audit(ExplodedNode<ValueState>* N); - virtual void ReportResults(Diagnostic& Diag, PathDiagnosticClient* PD, - ASTContext& Ctx, BugReporter& BR, - ExplodedGraph<GRExprEngine>& G); + virtual void EmitWarnings(BugReporter& BR); private: - void AddError(NodeTy* N, BugDescription* D) { - Errors.push_back(std::make_pair(N, D)); + void AddError(NodeTy* N, BugReport* R) { + Errors.push_back(std::make_pair(N, R)); } void WarnNilArg(NodeTy* N, ObjCMessageExpr* ME, unsigned Arg) { - AddError(N, new NilArg(ME, Arg)); + AddError(N, new NilArg::Report(Desc, ME, Arg)); } }; @@ -186,13 +194,11 @@ static inline bool isNil(RVal X) { //===----------------------------------------------------------------------===// -void BasicObjCFoundationChecks::ReportResults(Diagnostic& Diag, - PathDiagnosticClient* PD, - ASTContext& Ctx, BugReporter& BR, - ExplodedGraph<GRExprEngine>& G) { - +void BasicObjCFoundationChecks::EmitWarnings(BugReporter& BR) { + for (ErrorsTy::iterator I=Errors.begin(), E=Errors.end(); I!=E; ++I) - BR.EmitPathWarning(Diag, PD, Ctx, *I->second, G, I->first); + + BR.EmitPathWarning(*I->second, I->first); } bool BasicObjCFoundationChecks::CheckNilArg(NodeTy* N, unsigned Arg) { diff --git a/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp index 66b1b04c9d..c851696a30 100644 --- a/lib/Analysis/BugReporter.cpp +++ b/lib/Analysis/BugReporter.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "clang/Analysis/PathSensitive/BugReporter.h" +#include "clang/Analysis/PathSensitive/GRExprEngine.h" #include "clang/Basic/SourceManager.h" #include "clang/Basic/SourceLocation.h" #include "clang/AST/ASTContext.h" @@ -25,6 +26,9 @@ using namespace clang; BugReporter::~BugReporter() {} +BugType::~BugType() {} +BugReport::~BugReport() {} +ExplodedGraph<ValueState>& BugReporter::getGraph() { return Eng.getGraph(); } static inline Stmt* GetStmt(const ProgramPoint& P) { if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) { @@ -48,7 +52,7 @@ static inline Stmt* GetStmt(const CFGBlock* B) { PathDiagnosticPiece* -BugDescription::getEndPath(ASTContext& Ctx, ExplodedNode<ValueState> *N) const { +BugReport::getEndPath(ASTContext& Ctx, ExplodedNode<ValueState> *N) const { Stmt* S = GetStmt(N->getLocation()); @@ -56,7 +60,9 @@ BugDescription::getEndPath(ASTContext& Ctx, ExplodedNode<ValueState> *N) const { return NULL; FullSourceLoc L(S->getLocStart(), Ctx.getSourceManager()); - PathDiagnosticPiece* P = new PathDiagnosticPiece(L, getDescription()); + + PathDiagnosticPiece* P = + new PathDiagnosticPiece(L, getDescription()); const SourceRange *Beg, *End; getRanges(Beg, End); @@ -74,34 +80,38 @@ BugDescription::getEndPath(ASTContext& Ctx, ExplodedNode<ValueState> *N) const { return P; } -void BugDescription::getRanges(const SourceRange*& beg, - const SourceRange*& end) const { +void BugReport::getRanges(const SourceRange*& beg, + const SourceRange*& end) const { beg = NULL; end = NULL; } -void BugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, ASTContext& Ctx, - const BugDescription& B, - ExplodedGraph<GRExprEngine>& G, - ExplodedNode<ValueState>* N, - BugReporterHelper** BegHelpers, - BugReporterHelper** EndHelpers) { - - if (PathDiagnosticPiece* Piece = B.getEndPath(Ctx,N)) +PathDiagnosticPiece* BugReport::VisitNode(ExplodedNode<ValueState>* N, + ExplodedNode<ValueState>* PrevN, + ExplodedGraph<ValueState>& G, + ASTContext& Ctx) { + return NULL; +} + +void BugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, + BugReport& R, + ExplodedNode<ValueState>* N) { + + if (PathDiagnosticPiece* Piece = R.getEndPath(Ctx,N)) PD.push_back(Piece); else return; SourceManager& SMgr = Ctx.getSourceManager(); - llvm::OwningPtr<ExplodedGraph<GRExprEngine> > GTrim(G.Trim(&N, &N+1)); + llvm::OwningPtr<ExplodedGraph<ValueState> > GTrim(getGraph().Trim(&N, &N+1)); // Find the sink in the trimmed graph. // FIXME: Should we eventually have a sink iterator? ExplodedNode<ValueState>* NewN = 0; - for (ExplodedGraph<GRExprEngine>::node_iterator + for (ExplodedGraph<ValueState>::node_iterator I = GTrim->nodes_begin(), E = GTrim->nodes_end(); I != E; ++I) { if (I->isSink()) { @@ -292,13 +302,8 @@ void BugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, ASTContext& Ctx, } } else - for (BugReporterHelper** I = BegHelpers; I != EndHelpers; ++I) { - - PathDiagnosticPiece* piece = (*I)->VisitNode(N, NextNode, G, Ctx); - - if (piece) - PD.push_front(piece); - } + if (PathDiagnosticPiece* piece = R.VisitNode(N, NextNode, *GTrim, Ctx)) + PD.push_front(piece); } } @@ -318,39 +323,30 @@ bool BugReporter::IsCached(ExplodedNode<ValueState>* N) { return false; } -void BugReporter::EmitPathWarning(Diagnostic& Diag, - PathDiagnosticClient* PDC, - ASTContext& Ctx, - const BugDescription& B, - ExplodedGraph<GRExprEngine>& G, - ExplodedNode<ValueState>* N, - BugReporterHelper** BegHelpers, - BugReporterHelper** EndHelpers) { +void BugReporter::EmitPathWarning(BugReport& R, ExplodedNode<ValueState>* N) { - if (!PDC) { - EmitWarning(Diag, Ctx, B, N); + if (!PD) { + EmitWarning(R, N); return; } if (IsCached(N)) return; - PathDiagnostic D(B.getName()); - GeneratePathDiagnostic(D, Ctx, B, G, N, BegHelpers, EndHelpers); + PathDiagnostic D(R.getName()); + GeneratePathDiagnostic(D, R, N); if (!D.empty()) - PDC->HandlePathDiagnostic(D); + PD->HandlePathDiagnostic(D); } -void BugReporter::EmitWarning(Diagnostic& Diag, ASTContext& Ctx, - const BugDescription& B, - ExplodedNode<ValueState>* N) { +void BugReporter::EmitWarning(BugReport& R, ExplodedNode<ValueState>* N) { if (IsCached(N)) return; std::ostringstream os; - os << "[CHECKER] " << B.getDescription(); + os << "[CHECKER] " << R.getDescription(); unsigned ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, os.str().c_str()); @@ -362,8 +358,8 @@ void BugReporter::EmitWarning(Diagnostic& Diag, ASTContext& Ctx, if (!S) return; - SourceRange R = S->getSourceRange(); + SourceRange Range = S->getSourceRange(); Diag.Report(FullSourceLoc(S->getLocStart(), Ctx.getSourceManager()), - ErrorDiag, NULL, 0, &R, 1); + ErrorDiag, NULL, 0, &Range, 1); } diff --git a/lib/Analysis/CFRefCount.cpp b/lib/Analysis/CFRefCount.cpp index d73b771b52..501a3f5a05 100644 --- a/lib/Analysis/CFRefCount.cpp +++ b/lib/Analysis/CFRefCount.cpp @@ -792,7 +792,7 @@ CFRefCount::RefBindings CFRefCount::Update(RefBindings B, SymbolID sym, namespace { -class VISIBILITY_HIDDEN UseAfterRelease : public BugDescription { +class VISIBILITY_HIDDEN UseAfterRelease : public BugType { public: virtual const char* getName() const { @@ -804,7 +804,7 @@ public: } }; -class VISIBILITY_HIDDEN BadRelease : public BugDescription { +class VISIBILITY_HIDDEN BadRelease : public BugType { public: virtual const char* getName() const { @@ -831,14 +831,12 @@ void CheckCFRefCount(CFG& cfg, Decl& CD, ASTContext& Ctx, return; // FIXME: Refactor some day so this becomes a single function invocation. - - GRCoreEngine<GRExprEngine> Eng(cfg, CD, Ctx); - GRExprEngine* CS = &Eng.getCheckerState(); + GRExprEngine Eng(cfg, CD, Ctx); CFRefCount TF; - CS->setTransferFunctions(TF); + Eng.setTransferFunctions(TF); Eng.ExecuteWorkList(); - // Emit warnings. + // FIXME: Emit warnings. } diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp index 36bae45cff..6d4217774d 100644 --- a/lib/Analysis/GRExprEngine.cpp +++ b/lib/Analysis/GRExprEngine.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #include "clang/Analysis/PathSensitive/GRExprEngine.h" +#include "clang/Analysis/PathSensitive/BugReporter.h" #include "clang/Basic/SourceManager.h" #include "llvm/Support/Streams.h" @@ -40,6 +41,67 @@ using llvm::cast; using llvm::APSInt; +GRExprEngine::GRExprEngine(CFG& cfg, Decl& CD, ASTContext& Ctx) + : CoreEngine(cfg, CD, Ctx, *this), + G(CoreEngine.getGraph()), + Liveness(G.getCFG()), + Builder(NULL), + StateMgr(G.getContext(), G.getAllocator()), + BasicVals(StateMgr.getBasicValueFactory()), + TF(NULL), // FIXME + SymMgr(StateMgr.getSymbolManager()), + StmtEntryNode(NULL), CleanedState(NULL), CurrentStmt(NULL) { + + // Compute liveness information. + Liveness.runOnCFG(G.getCFG()); + Liveness.runOnAllBlocks(G.getCFG(), NULL, true); +} + +GRExprEngine::~GRExprEngine() { + for (BugTypeSet::iterator I = BugTypes.begin(), E = BugTypes.end(); I!=E; ++I) + delete *I; + + for (SimpleChecksTy::iterator I = CallChecks.begin(), E = CallChecks.end(); + I != E; ++I) + delete *I; + + for (SimpleChecksTy::iterator I=MsgExprChecks.begin(), E=MsgExprChecks.end(); + I != E; ++I) + delete *I; +} + +void GRExprEngine::EmitWarnings(Diagnostic& Diag, PathDiagnosticClient* PD) { + for (bug_type_iterator I = bug_types_begin(), E = bug_types_end(); I!=E; ++I){ + BugReporter BR(Diag, PD, getContext(), *this); + (*I)->EmitWarnings(BR); + } + + for (SimpleChecksTy::iterator I = CallChecks.begin(), E = CallChecks.end(); + I != E; ++I) { + BugReporter BR(Diag, PD, getContext(), *this); + (*I)->EmitWarnings(BR); + } + + for (SimpleChecksTy::iterator I=MsgExprChecks.begin(), E=MsgExprChecks.end(); + I != E; ++I) { + BugReporter BR(Diag, PD, getContext(), *this); + (*I)->EmitWarnings(BR); + } +} + +void GRExprEngine::setTransferFunctions(GRTransferFuncs* tf) { + TF = tf; + TF->RegisterChecks(*this); +} + +void GRExprEngine::AddCallCheck(GRSimpleAPICheck* A) { + CallChecks.push_back(A); +} + +void GRExprEngine::AddObjCMessageExprCheck(GRSimpleAPICheck* A) { + MsgExprChecks.push_back(A); +} + ValueState* GRExprEngine::getInitialState() { // The LiveVariables information already has a compilation of all VarDecls diff --git a/lib/Analysis/GRSimpleVals.cpp b/lib/Analysis/GRSimpleVals.cpp index d7ee5606a8..e7b456ff21 100644 --- a/lib/Analysis/GRSimpleVals.cpp +++ b/lib/Analysis/GRSimpleVals.cpp @@ -25,239 +25,315 @@ using namespace clang; //===----------------------------------------------------------------------===// +// Utility functions. +//===----------------------------------------------------------------------===// + +template <typename ITERATOR> inline +ExplodedNode<ValueState>* GetNode(ITERATOR I) { + return *I; +} + +template <> inline +ExplodedNode<ValueState>* GetNode(GRExprEngine::undef_arg_iterator I) { + return I->first; +} + +template <typename ITER> +void GenericEmitWarnings(BugReporter& BR, const BugType& D, + ITER I, ITER E) { + + for (; I != E; ++I) { + BugReport R(D); + BR.EmitPathWarning(R, GetNode(I)); + } +} + +//===----------------------------------------------------------------------===// // Bug Descriptions. //===----------------------------------------------------------------------===// namespace { -class VISIBILITY_HIDDEN NullDeref : public BugDescription { +class VISIBILITY_HIDDEN NullDeref : public BugType { public: virtual const char* getName() const { return "null dereference"; } + virtual const char* getDescription() const { return "Dereference of null pointer."; } -}; -class VISIBILITY_HIDDEN UndefDeref : public BugDescription { + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + GenericEmitWarnings(BR, *this, Eng.null_derefs_begin(), + Eng.null_derefs_end()); + } +}; + +class VISIBILITY_HIDDEN UndefDeref : public BugType { public: virtual const char* getName() const { return "bad dereference"; } + virtual const char* getDescription() const { return "Dereference of undefined value."; } + + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + GenericEmitWarnings(BR, *this, Eng.undef_derefs_begin(), + Eng.undef_derefs_end()); + } }; -class VISIBILITY_HIDDEN UndefBranch : public BugDescription { +class VISIBILITY_HIDDEN UndefBranch : public BugType { public: virtual const char* getName() const { return "uninitialized value"; } + virtual const char* getDescription() const { return "Branch condition evaluates to an uninitialized value."; } + + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + GenericEmitWarnings(BR, *this, Eng.undef_branches_begin(), + Eng.undef_branches_end()); + } }; - -class VISIBILITY_HIDDEN DivZero : public BugDescription { + +class VISIBILITY_HIDDEN DivZero : public BugType { public: virtual const char* getName() const { return "divide-by-zero"; } + virtual const char* getDescription() const { return "Division by zero/undefined value."; } -}; -class VISIBILITY_HIDDEN UndefResult : public BugDescription { + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + GenericEmitWarnings(BR, *this, Eng.explicit_bad_divides_begin(), + Eng.explicit_bad_divides_end()); + } +}; + +class VISIBILITY_HIDDEN UndefResult : public BugType { public: virtual const char* getName() const { return "undefined result"; } + virtual const char* getDescription() const { return "Result of operation is undefined."; } + + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + GenericEmitWarnings(BR, *this, Eng.undef_results_begin(), + Eng.undef_results_begin()); + } }; -class VISIBILITY_HIDDEN BadCall : public BugDescription { +class VISIBILITY_HIDDEN BadCall : public BugType { public: virtual const char* getName() const { return "invalid function call"; } + virtual const char* getDescription() const { return "Called function is a NULL or undefined function pointer value."; } + + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + GenericEmitWarnings(BR, *this, Eng.bad_calls_begin(), + Eng.bad_calls_begin()); + } }; -class VISIBILITY_HIDDEN BadArg : public BugDescription { - SourceRange R; + +class VISIBILITY_HIDDEN BadArg : public BugType { +protected: + + class Report : public BugReport { + const SourceRange R; + public: + Report(BugType& D, Expr* E) : BugReport(D), R(E->getSourceRange()) {} + virtual ~Report() {} + + virtual void getRanges(const SourceRange*& B, const SourceRange*& E) const { + B = &R; + E = B+1; + } + }; + public: - BadArg(Expr *E) { - R = E->getSourceRange(); - } + + virtual ~BadArg() {} virtual const char* getName() const { return "bad argument"; } + virtual const char* getDescription() const { return "Pass-by-value argument in function is undefined."; - } - - virtual void getRanges(const SourceRange*& B, const SourceRange*& E) const { - B = &R; - E = B+1; + } + + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + + for (GRExprEngine::UndefArgsTy::iterator I = Eng.undef_arg_begin(), + E = Eng.undef_arg_end(); I!=E; ++I) { + + // Generate a report for this bug. + Report report(*this, I->second); + + // Emit the warning. + BR.EmitPathWarning(report, I->first); + } + } }; - + class VISIBILITY_HIDDEN BadMsgExprArg : public BadArg { public: - BadMsgExprArg(Expr *E) : BadArg(E) {} - virtual const char* getName() const { return "bad argument"; } + virtual const char* getDescription() const { return "Pass-by-value argument in message expression is undefined."; } + + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + + for (GRExprEngine::UndefArgsTy::iterator I=Eng.msg_expr_undef_arg_begin(), + E = Eng.msg_expr_undef_arg_begin(); I!=E; ++I) { + + // Generate a report for this bug. + Report report(*this, I->second); + + // Emit the warning. + BR.EmitPathWarning(report, I->first); + } + + } }; -class VISIBILITY_HIDDEN BadReceiver : public BugDescription { - SourceRange R; -public: - BadReceiver(ExplodedNode<ValueState>* N) { - Stmt *S = cast<PostStmt>(N->getLocation()).getStmt(); - Expr* E = cast<ObjCMessageExpr>(S)->getReceiver(); - assert (E && "Receiver cannot be NULL"); - R = E->getSourceRange(); - } +class VISIBILITY_HIDDEN BadReceiver : public BugType { + class Report : public BugReport { + SourceRange R; + public: + Report(BugType& D, ExplodedNode<ValueState> *N) : BugReport(D) { + Stmt *S = cast<PostStmt>(N->getLocation()).getStmt(); + Expr* E = cast<ObjCMessageExpr>(S)->getReceiver(); + assert (E && "Receiver cannot be NULL"); + R = E->getSourceRange(); + } + + virtual ~Report() {} + + virtual void getRanges(const SourceRange*& B, const SourceRange*& E) const { + B = &R; + E = B+1; + } + }; + +public: virtual const char* getName() const { return "bad receiver"; } + virtual const char* getDescription() const { return "Receiver in message expression is an uninitialized value."; } - virtual void getRanges(const SourceRange*& B, const SourceRange*& E) const { - B = &R; - E = B+1; + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + + for (GRExprEngine::UndefReceiversTy::iterator I=Eng.undef_receivers_begin(), + E = Eng.undef_receivers_end(); I!=E; ++I) { + + // Generate a report for this bug. + Report report(*this, *I); + + // Emit the warning. + BR.EmitPathWarning(report, *I); + } } }; -class VISIBILITY_HIDDEN RetStack : public BugDescription { +class VISIBILITY_HIDDEN RetStack : public BugType { public: virtual const char* getName() const { return "return of stack address"; } + virtual const char* getDescription() const { return "Address of stack-allocated variable returned."; } + + virtual void EmitWarnings(BugReporter& BR) { + GRExprEngine& Eng = BR.getEngine(); + GenericEmitWarnings(BR, *this, Eng.ret_stackaddr_begin(), + Eng.ret_stackaddr_begin()); + } }; } // end anonymous namespace + +void GRSimpleVals::RegisterChecks(GRExprEngine& Eng) { + Eng.Register(new NullDeref()); + Eng.Register(new UndefDeref()); + Eng.Register(new UndefBranch()); + Eng.Register(new DivZero()); + Eng.Register(new UndefResult()); + Eng.Register(new BadCall()); + Eng.Register(new RetStack()); + Eng.Register(new BadArg()); + Eng.Register(new BadMsgExprArg()); + Eng.Register(new BadReceiver()); -//===----------------------------------------------------------------------===// -// Utility functions. -//===----------------------------------------------------------------------===// - -template <typename ITERATOR> inline -ExplodedNode<ValueState>* GetNode(ITERATOR I) { - return *I; -} + // Add extra checkers. -template <> inline -ExplodedNode<ValueState>* GetNode(GRExprEngine::undef_arg_iterator I) { - return I->first; + GRSimpleAPICheck* FoundationCheck = + CreateBasicObjCFoundationChecks(Eng.getContext(), &Eng.getStateManager()); + + Eng.AddObjCMessageExprCheck(FoundationCheck); } //===----------------------------------------------------------------------===// // Analysis Driver. //===----------------------------------------------------------------------===// -template <typename ITERATOR> -void EmitWarning(Diagnostic& Diag, PathDiagnosticClient* PD, - ASTContext& Ctx, BugReporter& BR, - const BugDescription& Desc, - ExplodedGraph<GRExprEngine>& G, - ITERATOR I, ITERATOR E) { - - for (; I != E; ++I) - BR.EmitPathWarning(Diag, PD, Ctx, Desc, G, GetNode(I)); -} - namespace clang { unsigned RunGRSimpleVals(CFG& cfg, Decl& CD, ASTContext& Ctx, Diagnostic& Diag, PathDiagnosticClient* PD, bool Visualize, bool TrimGraph) { - - GRCoreEngine<GRExprEngine> Eng(cfg, CD, Ctx); - GRExprEngine* CS = &Eng.getCheckerState(); + + // Construct the analysis engine. + GRExprEngine Eng(cfg, CD, Ctx); // Set base transfer functions. GRSimpleVals GRSV; - CS->setTransferFunctions(GRSV); - - // Add extra checkers. - llvm::OwningPtr<GRSimpleAPICheck> FoundationCheck( - CreateBasicObjCFoundationChecks(Ctx, &CS->getStateManager())); - - CS->AddObjCMessageExprCheck(FoundationCheck.get()); + Eng.setTransferFunctions(GRSV); // Execute the worklist algorithm. - Eng.ExecuteWorkList(120000); - - BugReporter BR; - ExplodedGraph<GRExprEngine>& G = Eng.getGraph(); + Eng.ExecuteWorkList(); - EmitWarning(Diag, PD, Ctx, BR, NullDeref(), G, - CS->null_derefs_begin(), CS->null_derefs_end()); - - - EmitWarning(Diag, PD, Ctx, BR, UndefDeref(), G, - CS->undef_derefs_begin(), CS->undef_derefs_end()); - - EmitWarning(Diag, PD, Ctx, BR, UndefBranch(), G, - CS->undef_branches_begin(), CS->undef_branches_end()); - - EmitWarning(Diag, PD, Ctx, BR, DivZero(), G, - CS->explicit_bad_divides_begin(), CS->explicit_bad_divides_end()); - - EmitWarning(Diag, PD, Ctx, BR, UndefResult(), G, - CS->undef_results_begin(), CS->undef_results_end()); - - EmitWarning(Diag, PD, Ctx, BR, BadCall(), G, - CS->bad_calls_begin(), CS->bad_calls_end()); - - for (GRExprEngine::UndefArgsTy::iterator I = CS->undef_arg_begin(), - E = CS->undef_arg_end(); I!=E; ++I) { - - BadArg Desc(I->second); - BR.EmitPathWarning(Diag, PD, Ctx, Desc, G, I->first); - } - - for (GRExprEngine::UndefArgsTy::iterator I = CS->msg_expr_undef_arg_begin(), - E = CS->msg_expr_undef_arg_end(); I!=E; ++I) { - - BadMsgExprArg Desc(I->second); - BR.EmitPathWarning(Diag, PD, Ctx, Desc, G, I->first); - } - - for (GRExprEngine::UndefReceiversTy::iterator I = CS->undef_receivers_begin(), - E = CS->undef_receivers_end(); I!=E; ++I) { - - BadReceiver Desc(*I); - BR.EmitPathWarning(Diag, PD, Ctx, Desc, G, *I); - } - - EmitWarning(Diag, PD, Ctx, BR, RetStack(), G, - CS->ret_stackaddr_begin(), CS->ret_stackaddr_end()); - + // Display warnings. + Eng.EmitWarnings(Diag, PD); - FoundationCheck.get()->ReportResults(Diag, PD, Ctx, BR, G); #ifndef NDEBUG - if (Visualize) CS->ViewGraph(TrimGraph); + if (Visualize) Eng.ViewGraph(TrimGraph); #endif return Eng.getGraph().size(); diff --git a/lib/Analysis/GRSimpleVals.h b/lib/Analysis/GRSimpleVals.h index 74f7fd81ea..cd6016bba2 100644 --- a/lib/Analysis/GRSimpleVals.h +++ b/lib/Analysis/GRSimpleVals.h @@ -29,6 +29,8 @@ public: GRSimpleVals() {} virtual ~GRSimpleVals() {} + virtual void RegisterChecks(GRExprEngine& Eng); + // Casts. virtual RVal EvalCast(GRExprEngine& Engine, NonLVal V, QualType CastT); |