diff options
Diffstat (limited to 'include/clang/StaticAnalyzer')
37 files changed, 8597 insertions, 0 deletions
diff --git a/include/clang/StaticAnalyzer/Checkers/CheckerBase.td b/include/clang/StaticAnalyzer/Checkers/CheckerBase.td new file mode 100644 index 0000000..e452ccf --- /dev/null +++ b/include/clang/StaticAnalyzer/Checkers/CheckerBase.td @@ -0,0 +1,38 @@ +//===--- CheckerBase.td - Checker TableGen classes ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the TableGen core definitions for checkers +// +//===----------------------------------------------------------------------===// + +class Package<string name> { + string PackageName = name; + bit Hidden = 0; + Package ParentPackage; +} +class InPackage<Package P> { Package ParentPackage = P; } + +class CheckerGroup<string name> { + string GroupName = name; +} +class InGroup<CheckerGroup G> { CheckerGroup Group = G; } + +// All checkers are an indirect subclass of this. +class Checker<string name = ""> { + string CheckerName = name; + string DescFile; + string HelpText; + bit Hidden = 0; + Package ParentPackage; + CheckerGroup Group; +} + +class DescFile<string filename> { string DescFile = filename; } +class HelpText<string text> { string HelpText = text; } +class Hidden { bit Hidden = 1; } diff --git a/include/clang/StaticAnalyzer/Checkers/DereferenceChecker.h b/include/clang/StaticAnalyzer/Checkers/DereferenceChecker.h new file mode 100644 index 0000000..f9cce9c --- /dev/null +++ b/include/clang/StaticAnalyzer/Checkers/DereferenceChecker.h @@ -0,0 +1,35 @@ +//== NullDerefChecker.h - Null dereference checker --------------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This defines NullDerefChecker and UndefDerefChecker, two builtin checks +// in ExprEngine that check for null and undefined pointers at loads +// and stores. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_DEREFCHECKER +#define LLVM_CLANG_GR_DEREFCHECKER + +#include <utility> + +namespace clang { + +namespace ento { + +class ExprEngine; +class ExplodedNode; + +std::pair<ExplodedNode * const *, ExplodedNode * const *> +GetImplicitNullDereferences(ExprEngine &Eng); + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Checkers/LocalCheckers.h b/include/clang/StaticAnalyzer/Checkers/LocalCheckers.h new file mode 100644 index 0000000..42feb78 --- /dev/null +++ b/include/clang/StaticAnalyzer/Checkers/LocalCheckers.h @@ -0,0 +1,51 @@ +//==- LocalCheckers.h - Intra-Procedural+Flow-Sensitive Checkers -*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the interface to call a set of intra-procedural (local) +// checkers that use flow/path-sensitive analyses to find bugs. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_LOCALCHECKERS_H +#define LLVM_CLANG_GR_LOCALCHECKERS_H + +namespace clang { + +class CFG; +class Decl; +class Diagnostic; +class ASTContext; +class LangOptions; +class ParentMap; +class LiveVariables; +class ObjCImplementationDecl; +class LangOptions; +class TranslationUnitDecl; + +namespace ento { + +class PathDiagnosticClient; +class TransferFuncs; +class BugType; +class BugReporter; +class ExprEngine; + +TransferFuncs* MakeCFRefCountTF(ASTContext& Ctx, bool GCEnabled, + const LangOptions& lopts); + +void RegisterExperimentalChecks(ExprEngine &Eng); +void RegisterExperimentalInternalChecks(ExprEngine &Eng); + +void RegisterCallInliner(ExprEngine &Eng); + +} // end GR namespace + +} // end namespace clang + +#endif diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h new file mode 100644 index 0000000..1786fe6 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h @@ -0,0 +1,486 @@ +//===--- BugReporter.h - Generate PathDiagnostics --------------*- 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 BugReporter, a utility class for generating +// PathDiagnostics for analyses based on GRState. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_BUGREPORTER +#define LLVM_CLANG_GR_BUGREPORTER + +#include "clang/Basic/SourceLocation.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/ImmutableList.h" +#include "llvm/ADT/ImmutableSet.h" +#include "llvm/ADT/SmallSet.h" +#include <list> + +namespace clang { + +class ASTContext; +class Diagnostic; +class Stmt; +class ParentMap; + +namespace ento { + +class PathDiagnostic; +class PathDiagnosticPiece; +class PathDiagnosticClient; +class ExplodedNode; +class ExplodedGraph; +class BugReporter; +class BugReporterContext; +class ExprEngine; +class GRState; +class BugType; + +//===----------------------------------------------------------------------===// +// Interface for individual bug reports. +//===----------------------------------------------------------------------===// + +class BugReporterVisitor : public llvm::FoldingSetNode { +public: + virtual ~BugReporterVisitor(); + virtual PathDiagnosticPiece* VisitNode(const ExplodedNode* N, + const ExplodedNode* PrevN, + BugReporterContext& BRC) = 0; + + virtual bool isOwnedByReporterContext() { return true; } + virtual void Profile(llvm::FoldingSetNodeID &ID) const = 0; +}; + +// FIXME: Combine this with RangedBugReport and remove RangedBugReport. +class BugReport : public BugReporterVisitor { +protected: + BugType& BT; + std::string ShortDescription; + std::string Description; + const ExplodedNode *ErrorNode; + mutable SourceRange R; + +protected: + friend class BugReporter; + friend class BugReportEquivClass; + + virtual void Profile(llvm::FoldingSetNodeID& hash) const { + hash.AddInteger(getLocation().getRawEncoding()); + hash.AddString(Description); + } + +public: + class NodeResolver { + public: + virtual ~NodeResolver() {} + virtual const ExplodedNode* + getOriginalNode(const ExplodedNode* N) = 0; + }; + + BugReport(BugType& bt, llvm::StringRef desc, const ExplodedNode *errornode) + : BT(bt), Description(desc), ErrorNode(errornode) {} + + BugReport(BugType& bt, llvm::StringRef shortDesc, llvm::StringRef desc, + const ExplodedNode *errornode) + : BT(bt), ShortDescription(shortDesc), Description(desc), + ErrorNode(errornode) {} + + virtual ~BugReport(); + + virtual bool isOwnedByReporterContext() { return false; } + + const BugType& getBugType() const { return BT; } + BugType& getBugType() { return BT; } + + // FIXME: Perhaps this should be moved into a subclass? + const ExplodedNode* getErrorNode() const { return ErrorNode; } + + // FIXME: Do we need this? Maybe getLocation() should return a ProgramPoint + // object. + // FIXME: If we do need it, we can probably just make it private to + // BugReporter. + const Stmt* getStmt() const; + + const llvm::StringRef getDescription() const { return Description; } + + const llvm::StringRef getShortDescription() const { + return ShortDescription.empty() ? Description : ShortDescription; + } + + // FIXME: Is this needed? + virtual std::pair<const char**,const char**> getExtraDescriptiveText() { + return std::make_pair((const char**)0,(const char**)0); + } + + // FIXME: Perhaps move this into a subclass. + virtual PathDiagnosticPiece* getEndPath(BugReporterContext& BRC, + const ExplodedNode* N); + + /// getLocation - Return the "definitive" location of the reported bug. + /// While a bug can span an entire path, usually there is a specific + /// location that can be used to identify where the key issue occured. + /// This location is used by clients rendering diagnostics. + virtual SourceLocation getLocation() const; + + typedef const SourceRange *ranges_iterator; + + /// getRanges - Returns the source ranges associated with this bug. + virtual std::pair<ranges_iterator, ranges_iterator> getRanges() const; + + virtual PathDiagnosticPiece* VisitNode(const ExplodedNode* N, + const ExplodedNode* PrevN, + BugReporterContext& BR); + + virtual void registerInitialVisitors(BugReporterContext& BRC, + const ExplodedNode* N) {} +}; + +//===----------------------------------------------------------------------===// +// BugTypes (collections of related reports). +//===----------------------------------------------------------------------===// + +class BugReportEquivClass : public llvm::FoldingSetNode { + // List of *owned* BugReport objects. + std::list<BugReport*> Reports; + + friend class BugReporter; + void AddReport(BugReport* R) { Reports.push_back(R); } +public: + BugReportEquivClass(BugReport* R) { Reports.push_back(R); } + ~BugReportEquivClass(); + + void Profile(llvm::FoldingSetNodeID& ID) const { + assert(!Reports.empty()); + (*Reports.begin())->Profile(ID); + } + + class iterator { + std::list<BugReport*>::iterator impl; + public: + iterator(std::list<BugReport*>::iterator i) : impl(i) {} + iterator& operator++() { ++impl; return *this; } + bool operator==(const iterator& I) const { return I.impl == impl; } + bool operator!=(const iterator& I) const { return I.impl != impl; } + BugReport* operator*() const { return *impl; } + BugReport* operator->() const { return *impl; } + }; + + class const_iterator { + std::list<BugReport*>::const_iterator impl; + public: + const_iterator(std::list<BugReport*>::const_iterator i) : impl(i) {} + const_iterator& operator++() { ++impl; return *this; } + bool operator==(const const_iterator& I) const { return I.impl == impl; } + bool operator!=(const const_iterator& I) const { return I.impl != impl; } + const BugReport* operator*() const { return *impl; } + const BugReport* operator->() const { return *impl; } + }; + + iterator begin() { return iterator(Reports.begin()); } + iterator end() { return iterator(Reports.end()); } + + const_iterator begin() const { return const_iterator(Reports.begin()); } + const_iterator end() const { return const_iterator(Reports.end()); } +}; + + +//===----------------------------------------------------------------------===// +// Specialized subclasses of BugReport. +//===----------------------------------------------------------------------===// + +// FIXME: Collapse this with the default BugReport class. +class RangedBugReport : public BugReport { + llvm::SmallVector<SourceRange, 4> Ranges; +public: + RangedBugReport(BugType& D, llvm::StringRef description, + ExplodedNode *errornode) + : BugReport(D, description, errornode) {} + + RangedBugReport(BugType& D, llvm::StringRef shortDescription, + llvm::StringRef description, ExplodedNode *errornode) + : BugReport(D, shortDescription, description, errornode) {} + + ~RangedBugReport(); + + // FIXME: Move this out of line. + void addRange(SourceRange R) { + assert(R.isValid()); + Ranges.push_back(R); + } + + virtual std::pair<ranges_iterator, ranges_iterator> getRanges() const { + return std::make_pair(Ranges.begin(), Ranges.end()); + } +}; + +class EnhancedBugReport : public RangedBugReport { +public: + typedef void (*VisitorCreator)(BugReporterContext &BRcC, const void *data, + const ExplodedNode *N); + +private: + typedef std::vector<std::pair<VisitorCreator, const void*> > Creators; + Creators creators; + +public: + EnhancedBugReport(BugType& D, llvm::StringRef description, + ExplodedNode *errornode) + : RangedBugReport(D, description, errornode) {} + + EnhancedBugReport(BugType& D, llvm::StringRef shortDescription, + llvm::StringRef description, ExplodedNode *errornode) + : RangedBugReport(D, shortDescription, description, errornode) {} + + ~EnhancedBugReport() {} + + void registerInitialVisitors(BugReporterContext& BRC, const ExplodedNode* N) { + for (Creators::iterator I = creators.begin(), E = creators.end(); I!=E; ++I) + I->first(BRC, I->second, N); + } + + void addVisitorCreator(VisitorCreator creator, const void *data) { + creators.push_back(std::make_pair(creator, data)); + } +}; + +//===----------------------------------------------------------------------===// +// BugReporter and friends. +//===----------------------------------------------------------------------===// + +class BugReporterData { +public: + virtual ~BugReporterData(); + virtual Diagnostic& getDiagnostic() = 0; + virtual PathDiagnosticClient* getPathDiagnosticClient() = 0; + virtual ASTContext& getASTContext() = 0; + virtual SourceManager& getSourceManager() = 0; +}; + +class BugReporter { +public: + enum Kind { BaseBRKind, GRBugReporterKind }; + +private: + typedef llvm::ImmutableSet<BugType*> BugTypesTy; + BugTypesTy::Factory F; + BugTypesTy BugTypes; + + const Kind kind; + BugReporterData& D; + + void FlushReport(BugReportEquivClass& EQ); + +protected: + BugReporter(BugReporterData& d, Kind k) : BugTypes(F.getEmptySet()), kind(k), + D(d) {} + +public: + BugReporter(BugReporterData& d) : BugTypes(F.getEmptySet()), kind(BaseBRKind), + D(d) {} + virtual ~BugReporter(); + + void FlushReports(); + + Kind getKind() const { return kind; } + + Diagnostic& getDiagnostic() { + return D.getDiagnostic(); + } + + PathDiagnosticClient* getPathDiagnosticClient() { + return D.getPathDiagnosticClient(); + } + + typedef BugTypesTy::iterator iterator; + iterator begin() { return BugTypes.begin(); } + iterator end() { return BugTypes.end(); } + + ASTContext& getContext() { return D.getASTContext(); } + + SourceManager& getSourceManager() { return D.getSourceManager(); } + + virtual void GeneratePathDiagnostic(PathDiagnostic& pathDiagnostic, + llvm::SmallVectorImpl<BugReport *> &bugReports) {} + + void Register(BugType *BT); + + void EmitReport(BugReport *R); + + void EmitBasicReport(llvm::StringRef BugName, llvm::StringRef BugStr, + SourceLocation Loc, + SourceRange* RangeBeg, unsigned NumRanges); + + void EmitBasicReport(llvm::StringRef BugName, llvm::StringRef BugCategory, + llvm::StringRef BugStr, SourceLocation Loc, + SourceRange* RangeBeg, unsigned NumRanges); + + + void EmitBasicReport(llvm::StringRef BugName, llvm::StringRef BugStr, + SourceLocation Loc) { + EmitBasicReport(BugName, BugStr, Loc, 0, 0); + } + + void EmitBasicReport(llvm::StringRef BugName, llvm::StringRef BugCategory, + llvm::StringRef BugStr, SourceLocation Loc) { + EmitBasicReport(BugName, BugCategory, BugStr, Loc, 0, 0); + } + + void EmitBasicReport(llvm::StringRef BugName, llvm::StringRef BugStr, + SourceLocation Loc, SourceRange R) { + EmitBasicReport(BugName, BugStr, Loc, &R, 1); + } + + void EmitBasicReport(llvm::StringRef BugName, llvm::StringRef Category, + llvm::StringRef BugStr, SourceLocation Loc, + SourceRange R) { + EmitBasicReport(BugName, Category, BugStr, Loc, &R, 1); + } + + static bool classof(const BugReporter* R) { return true; } +}; + +// FIXME: Get rid of GRBugReporter. It's the wrong abstraction. +class GRBugReporter : public BugReporter { + ExprEngine& Eng; + llvm::SmallSet<SymbolRef, 10> NotableSymbols; +public: + GRBugReporter(BugReporterData& d, ExprEngine& eng) + : BugReporter(d, GRBugReporterKind), Eng(eng) {} + + virtual ~GRBugReporter(); + + /// getEngine - Return the analysis engine used to analyze a given + /// function or method. + ExprEngine &getEngine() { return Eng; } + + /// getGraph - Get the exploded graph created by the analysis engine + /// for the analyzed method or function. + ExplodedGraph &getGraph(); + + /// getStateManager - Return the state manager used by the analysis + /// engine. + GRStateManager &getStateManager(); + + virtual void GeneratePathDiagnostic(PathDiagnostic &pathDiagnostic, + llvm::SmallVectorImpl<BugReport*> &bugReports); + + void addNotableSymbol(SymbolRef Sym) { + NotableSymbols.insert(Sym); + } + + bool isNotable(SymbolRef Sym) const { + return (bool) NotableSymbols.count(Sym); + } + + /// classof - Used by isa<>, cast<>, and dyn_cast<>. + static bool classof(const BugReporter* R) { + return R->getKind() == GRBugReporterKind; + } +}; + +class BugReporterContext { + GRBugReporter &BR; + // Not the most efficient data structure, but we use an ImmutableList for the + // Callbacks because it is safe to make additions to list during iteration. + llvm::ImmutableList<BugReporterVisitor*>::Factory F; + llvm::ImmutableList<BugReporterVisitor*> Callbacks; + llvm::FoldingSet<BugReporterVisitor> CallbacksSet; +public: + BugReporterContext(GRBugReporter& br) : BR(br), Callbacks(F.getEmptyList()) {} + virtual ~BugReporterContext(); + + void addVisitor(BugReporterVisitor* visitor); + + typedef llvm::ImmutableList<BugReporterVisitor*>::iterator visitor_iterator; + visitor_iterator visitor_begin() { return Callbacks.begin(); } + visitor_iterator visitor_end() { return Callbacks.end(); } + + GRBugReporter& getBugReporter() { return BR; } + + ExplodedGraph &getGraph() { return BR.getGraph(); } + + void addNotableSymbol(SymbolRef Sym) { + // FIXME: For now forward to GRBugReporter. + BR.addNotableSymbol(Sym); + } + + bool isNotable(SymbolRef Sym) const { + // FIXME: For now forward to GRBugReporter. + return BR.isNotable(Sym); + } + + GRStateManager& getStateManager() { + return BR.getStateManager(); + } + + SValBuilder& getSValBuilder() { + return getStateManager().getSValBuilder(); + } + + ASTContext& getASTContext() { + return BR.getContext(); + } + + SourceManager& getSourceManager() { + return BR.getSourceManager(); + } + + virtual BugReport::NodeResolver& getNodeResolver() = 0; +}; + +class DiagBugReport : public RangedBugReport { + std::list<std::string> Strs; + FullSourceLoc L; +public: + DiagBugReport(BugType& D, llvm::StringRef desc, FullSourceLoc l) : + RangedBugReport(D, desc, 0), L(l) {} + + virtual ~DiagBugReport() {} + + // FIXME: Move out-of-line (virtual function). + SourceLocation getLocation() const { return L; } + + void addString(llvm::StringRef s) { Strs.push_back(s); } + + typedef std::list<std::string>::const_iterator str_iterator; + str_iterator str_begin() const { return Strs.begin(); } + str_iterator str_end() const { return Strs.end(); } +}; + +//===----------------------------------------------------------------------===// +//===----------------------------------------------------------------------===// + +namespace bugreporter { + +const Stmt *GetDerefExpr(const ExplodedNode *N); +const Stmt *GetDenomExpr(const ExplodedNode *N); +const Stmt *GetCalleeExpr(const ExplodedNode *N); +const Stmt *GetRetValExpr(const ExplodedNode *N); + +void registerTrackNullOrUndefValue(BugReporterContext& BRC, const void *stmt, + const ExplodedNode* N); + +void registerFindLastStore(BugReporterContext& BRC, const void *memregion, + const ExplodedNode *N); + +void registerNilReceiverVisitor(BugReporterContext &BRC); + +void registerVarDeclsLastStore(BugReporterContext &BRC, const void *stmt, + const ExplodedNode *N); + +} // end namespace clang::bugreporter + +//===----------------------------------------------------------------------===// + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h b/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h new file mode 100644 index 0000000..2793284 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h @@ -0,0 +1,76 @@ +//===--- BugType.h - Bug Information Desciption ----------------*- 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 BugType, a class representing a bug type. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_BUGTYPE +#define LLVM_CLANG_ANALYSIS_BUGTYPE + +#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" +#include "llvm/ADT/FoldingSet.h" +#include <string> + +namespace clang { + +namespace ento { + +class ExplodedNode; +class ExprEngine; + +class BugType { +private: + const std::string Name; + const std::string Category; + llvm::FoldingSet<BugReportEquivClass> EQClasses; + friend class BugReporter; + bool SuppressonSink; +public: + BugType(llvm::StringRef name, llvm::StringRef cat) + : Name(name), Category(cat), SuppressonSink(false) {} + virtual ~BugType(); + + // FIXME: Should these be made strings as well? + llvm::StringRef getName() const { return Name; } + llvm::StringRef getCategory() const { return Category; } + + /// isSuppressOnSink - Returns true if bug reports associated with this bug + /// type should be suppressed if the end node of the report is post-dominated + /// by a sink node. + bool isSuppressOnSink() const { return SuppressonSink; } + void setSuppressOnSink(bool x) { SuppressonSink = x; } + + virtual void FlushReports(BugReporter& BR); + + typedef llvm::FoldingSet<BugReportEquivClass>::iterator iterator; + iterator begin() { return EQClasses.begin(); } + iterator end() { return EQClasses.end(); } + + typedef llvm::FoldingSet<BugReportEquivClass>::const_iterator const_iterator; + const_iterator begin() const { return EQClasses.begin(); } + const_iterator end() const { return EQClasses.end(); } +}; + +class BuiltinBug : public BugType { + const std::string desc; +public: + BuiltinBug(const char *name, const char *description) + : BugType(name, "Logic error"), desc(description) {} + + BuiltinBug(const char *name) + : BugType(name, "Logic error"), desc(name) {} + + llvm::StringRef getDescription() const { return desc; } +}; + +} // end GR namespace + +} // end clang namespace +#endif diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h new file mode 100644 index 0000000..6d53c09 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h @@ -0,0 +1,500 @@ +//===--- PathDiagnostic.h - Path-Specific Diagnostic Handling ---*- 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 the PathDiagnostic-related interfaces. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_PATH_DIAGNOSTIC_H +#define LLVM_CLANG_PATH_DIAGNOSTIC_H + +#include "clang/Basic/Diagnostic.h" +#include "llvm/ADT/FoldingSet.h" +#include <deque> +#include <iterator> +#include <string> +#include <vector> + +namespace clang { + +class Decl; +class SourceManager; +class Stmt; + +namespace ento { + +//===----------------------------------------------------------------------===// +// High-level interface for handlers of path-sensitive diagnostics. +//===----------------------------------------------------------------------===// + +class PathDiagnostic; + +class PathDiagnosticClient : public DiagnosticClient { +public: + PathDiagnosticClient() {} + + virtual ~PathDiagnosticClient() {} + + virtual void + FlushDiagnostics(llvm::SmallVectorImpl<std::string> *FilesMade = 0) = 0; + + void FlushDiagnostics(llvm::SmallVectorImpl<std::string> &FilesMade) { + FlushDiagnostics(&FilesMade); + } + + virtual llvm::StringRef getName() const = 0; + + virtual void HandleDiagnostic(Diagnostic::Level DiagLevel, + const DiagnosticInfo &Info); + virtual void HandlePathDiagnostic(const PathDiagnostic* D) = 0; + + enum PathGenerationScheme { Minimal, Extensive }; + virtual PathGenerationScheme getGenerationScheme() const { return Minimal; } + virtual bool supportsLogicalOpControlFlow() const { return false; } + virtual bool supportsAllBlockEdges() const { return false; } + virtual bool useVerboseDescription() const { return true; } +}; + +//===----------------------------------------------------------------------===// +// Path-sensitive diagnostics. +//===----------------------------------------------------------------------===// + +class PathDiagnosticRange : public SourceRange { +public: + const bool isPoint; + + PathDiagnosticRange(const SourceRange &R, bool isP = false) + : SourceRange(R), isPoint(isP) {} +}; + +class PathDiagnosticLocation { +private: + enum Kind { RangeK, SingleLocK, StmtK, DeclK } K; + SourceRange R; + const Stmt *S; + const Decl *D; + const SourceManager *SM; +public: + PathDiagnosticLocation() + : K(SingleLocK), S(0), D(0), SM(0) {} + + PathDiagnosticLocation(FullSourceLoc L) + : K(SingleLocK), R(L, L), S(0), D(0), SM(&L.getManager()) {} + + PathDiagnosticLocation(const Stmt *s, const SourceManager &sm) + : K(StmtK), S(s), D(0), SM(&sm) {} + + PathDiagnosticLocation(SourceRange r, const SourceManager &sm) + : K(RangeK), R(r), S(0), D(0), SM(&sm) {} + + PathDiagnosticLocation(const Decl *d, const SourceManager &sm) + : K(DeclK), S(0), D(d), SM(&sm) {} + + bool operator==(const PathDiagnosticLocation &X) const { + return K == X.K && R == X.R && S == X.S && D == X.D; + } + + bool operator!=(const PathDiagnosticLocation &X) const { + return K != X.K || R != X.R || S != X.S || D != X.D;; + } + + PathDiagnosticLocation& operator=(const PathDiagnosticLocation &X) { + K = X.K; + R = X.R; + S = X.S; + D = X.D; + SM = X.SM; + return *this; + } + + bool isValid() const { + return SM != 0; + } + + const SourceManager& getSourceManager() const { assert(isValid());return *SM;} + + FullSourceLoc asLocation() const; + PathDiagnosticRange asRange() const; + const Stmt *asStmt() const { assert(isValid()); return S; } + const Decl *asDecl() const { assert(isValid()); return D; } + + bool hasRange() const { return K == StmtK || K == RangeK || K == DeclK; } + + void invalidate() { + *this = PathDiagnosticLocation(); + } + + void flatten(); + + const SourceManager& getManager() const { assert(isValid()); return *SM; } + + void Profile(llvm::FoldingSetNodeID &ID) const; +}; + +class PathDiagnosticLocationPair { +private: + PathDiagnosticLocation Start, End; +public: + PathDiagnosticLocationPair(const PathDiagnosticLocation &start, + const PathDiagnosticLocation &end) + : Start(start), End(end) {} + + const PathDiagnosticLocation &getStart() const { return Start; } + const PathDiagnosticLocation &getEnd() const { return End; } + + void flatten() { + Start.flatten(); + End.flatten(); + } + + void Profile(llvm::FoldingSetNodeID &ID) const { + Start.Profile(ID); + End.Profile(ID); + } +}; + +//===----------------------------------------------------------------------===// +// Path "pieces" for path-sensitive diagnostics. +//===----------------------------------------------------------------------===// + +class PathDiagnosticPiece { +public: + enum Kind { ControlFlow, Event, Macro }; + enum DisplayHint { Above, Below }; + +private: + const std::string str; + std::vector<FixItHint> FixItHints; + const Kind kind; + const DisplayHint Hint; + std::vector<SourceRange> ranges; + + // Do not implement: + PathDiagnosticPiece(); + PathDiagnosticPiece(const PathDiagnosticPiece &P); + PathDiagnosticPiece& operator=(const PathDiagnosticPiece &P); + +protected: + PathDiagnosticPiece(llvm::StringRef s, Kind k, DisplayHint hint = Below); + + PathDiagnosticPiece(Kind k, DisplayHint hint = Below); + +public: + virtual ~PathDiagnosticPiece(); + + const std::string& getString() const { return str; } + + /// getDisplayHint - Return a hint indicating where the diagnostic should + /// be displayed by the PathDiagnosticClient. + DisplayHint getDisplayHint() const { return Hint; } + + virtual PathDiagnosticLocation getLocation() const = 0; + virtual void flattenLocations() = 0; + + Kind getKind() const { return kind; } + + void addRange(SourceRange R) { ranges.push_back(R); } + + void addRange(SourceLocation B, SourceLocation E) { + ranges.push_back(SourceRange(B,E)); + } + + void addFixItHint(const FixItHint& Hint) { + FixItHints.push_back(Hint); + } + + typedef const SourceRange* range_iterator; + + range_iterator ranges_begin() const { + return ranges.empty() ? NULL : &ranges[0]; + } + + range_iterator ranges_end() const { + return ranges_begin() + ranges.size(); + } + + typedef const FixItHint *fixit_iterator; + + fixit_iterator fixit_begin() const { + return FixItHints.empty()? 0 : &FixItHints[0]; + } + + fixit_iterator fixit_end() const { + return FixItHints.empty()? 0 + : &FixItHints[0] + FixItHints.size(); + } + + static inline bool classof(const PathDiagnosticPiece* P) { + return true; + } + + virtual void Profile(llvm::FoldingSetNodeID &ID) const; +}; + +class PathDiagnosticSpotPiece : public PathDiagnosticPiece { +private: + PathDiagnosticLocation Pos; +public: + PathDiagnosticSpotPiece(const PathDiagnosticLocation &pos, + llvm::StringRef s, + PathDiagnosticPiece::Kind k, + bool addPosRange = true) + : PathDiagnosticPiece(s, k), Pos(pos) { + assert(Pos.asLocation().isValid() && + "PathDiagnosticSpotPiece's must have a valid location."); + if (addPosRange && Pos.hasRange()) addRange(Pos.asRange()); + } + + PathDiagnosticLocation getLocation() const { return Pos; } + virtual void flattenLocations() { Pos.flatten(); } + + virtual void Profile(llvm::FoldingSetNodeID &ID) const; +}; + +class PathDiagnosticEventPiece : public PathDiagnosticSpotPiece { + +public: + PathDiagnosticEventPiece(const PathDiagnosticLocation &pos, + llvm::StringRef s, bool addPosRange = true) + : PathDiagnosticSpotPiece(pos, s, Event, addPosRange) {} + + ~PathDiagnosticEventPiece(); + + static inline bool classof(const PathDiagnosticPiece* P) { + return P->getKind() == Event; + } +}; + +class PathDiagnosticControlFlowPiece : public PathDiagnosticPiece { + std::vector<PathDiagnosticLocationPair> LPairs; +public: + PathDiagnosticControlFlowPiece(const PathDiagnosticLocation &startPos, + const PathDiagnosticLocation &endPos, + llvm::StringRef s) + : PathDiagnosticPiece(s, ControlFlow) { + LPairs.push_back(PathDiagnosticLocationPair(startPos, endPos)); + } + + PathDiagnosticControlFlowPiece(const PathDiagnosticLocation &startPos, + const PathDiagnosticLocation &endPos) + : PathDiagnosticPiece(ControlFlow) { + LPairs.push_back(PathDiagnosticLocationPair(startPos, endPos)); + } + + ~PathDiagnosticControlFlowPiece(); + + PathDiagnosticLocation getStartLocation() const { + assert(!LPairs.empty() && + "PathDiagnosticControlFlowPiece needs at least one location."); + return LPairs[0].getStart(); + } + + PathDiagnosticLocation getEndLocation() const { + assert(!LPairs.empty() && + "PathDiagnosticControlFlowPiece needs at least one location."); + return LPairs[0].getEnd(); + } + + void push_back(const PathDiagnosticLocationPair &X) { LPairs.push_back(X); } + + virtual PathDiagnosticLocation getLocation() const { + return getStartLocation(); + } + + typedef std::vector<PathDiagnosticLocationPair>::iterator iterator; + iterator begin() { return LPairs.begin(); } + iterator end() { return LPairs.end(); } + + virtual void flattenLocations() { + for (iterator I=begin(), E=end(); I!=E; ++I) I->flatten(); + } + + typedef std::vector<PathDiagnosticLocationPair>::const_iterator + const_iterator; + const_iterator begin() const { return LPairs.begin(); } + const_iterator end() const { return LPairs.end(); } + + static inline bool classof(const PathDiagnosticPiece* P) { + return P->getKind() == ControlFlow; + } + + virtual void Profile(llvm::FoldingSetNodeID &ID) const; +}; + +class PathDiagnosticMacroPiece : public PathDiagnosticSpotPiece { + std::vector<PathDiagnosticPiece*> SubPieces; +public: + PathDiagnosticMacroPiece(const PathDiagnosticLocation &pos) + : PathDiagnosticSpotPiece(pos, "", Macro) {} + + ~PathDiagnosticMacroPiece(); + + bool containsEvent() const; + + void push_back(PathDiagnosticPiece* P) { SubPieces.push_back(P); } + + typedef std::vector<PathDiagnosticPiece*>::iterator iterator; + iterator begin() { return SubPieces.begin(); } + iterator end() { return SubPieces.end(); } + + virtual void flattenLocations() { + PathDiagnosticSpotPiece::flattenLocations(); + for (iterator I=begin(), E=end(); I!=E; ++I) (*I)->flattenLocations(); + } + + typedef std::vector<PathDiagnosticPiece*>::const_iterator const_iterator; + const_iterator begin() const { return SubPieces.begin(); } + const_iterator end() const { return SubPieces.end(); } + + static inline bool classof(const PathDiagnosticPiece* P) { + return P->getKind() == Macro; + } + + virtual void Profile(llvm::FoldingSetNodeID &ID) const; +}; + +/// PathDiagnostic - PathDiagnostic objects represent a single path-sensitive +/// diagnostic. It represents an ordered-collection of PathDiagnosticPieces, +/// each which represent the pieces of the path. +class PathDiagnostic : public llvm::FoldingSetNode { + std::deque<PathDiagnosticPiece*> path; + unsigned Size; + std::string BugType; + std::string Desc; + std::string Category; + std::deque<std::string> OtherDesc; + +public: + PathDiagnostic(); + + PathDiagnostic(llvm::StringRef bugtype, llvm::StringRef desc, + llvm::StringRef category); + + ~PathDiagnostic(); + + llvm::StringRef getDescription() const { return Desc; } + llvm::StringRef getBugType() const { return BugType; } + llvm::StringRef getCategory() const { return Category; } + + typedef std::deque<std::string>::const_iterator meta_iterator; + meta_iterator meta_begin() const { return OtherDesc.begin(); } + meta_iterator meta_end() const { return OtherDesc.end(); } + void addMeta(llvm::StringRef s) { OtherDesc.push_back(s); } + + PathDiagnosticLocation getLocation() const { + assert(Size > 0 && "getLocation() requires a non-empty PathDiagnostic."); + return rbegin()->getLocation(); + } + + void push_front(PathDiagnosticPiece* piece) { + assert(piece); + path.push_front(piece); + ++Size; + } + + void push_back(PathDiagnosticPiece* piece) { + assert(piece); + path.push_back(piece); + ++Size; + } + + PathDiagnosticPiece* back() { + return path.back(); + } + + const PathDiagnosticPiece* back() const { + return path.back(); + } + + unsigned size() const { return Size; } + bool empty() const { return Size == 0; } + + void resetPath(bool deletePieces = true); + + class iterator { + public: + typedef std::deque<PathDiagnosticPiece*>::iterator ImplTy; + + typedef PathDiagnosticPiece value_type; + typedef value_type& reference; + typedef value_type* pointer; + typedef ptrdiff_t difference_type; + typedef std::bidirectional_iterator_tag iterator_category; + + private: + ImplTy I; + + public: + iterator(const ImplTy& i) : I(i) {} + + bool operator==(const iterator& X) const { return I == X.I; } + bool operator!=(const iterator& X) const { return I != X.I; } + + PathDiagnosticPiece& operator*() const { return **I; } + PathDiagnosticPiece* operator->() const { return *I; } + + iterator& operator++() { ++I; return *this; } + iterator& operator--() { --I; return *this; } + }; + + class const_iterator { + public: + typedef std::deque<PathDiagnosticPiece*>::const_iterator ImplTy; + + typedef const PathDiagnosticPiece value_type; + typedef value_type& reference; + typedef value_type* pointer; + typedef ptrdiff_t difference_type; + typedef std::bidirectional_iterator_tag iterator_category; + + private: + ImplTy I; + + public: + const_iterator(const ImplTy& i) : I(i) {} + + bool operator==(const const_iterator& X) const { return I == X.I; } + bool operator!=(const const_iterator& X) const { return I != X.I; } + + reference operator*() const { return **I; } + pointer operator->() const { return *I; } + + const_iterator& operator++() { ++I; return *this; } + const_iterator& operator--() { --I; return *this; } + }; + + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + + // forward iterator creation methods. + + iterator begin() { return path.begin(); } + iterator end() { return path.end(); } + + const_iterator begin() const { return path.begin(); } + const_iterator end() const { return path.end(); } + + // reverse iterator creation methods. + reverse_iterator rbegin() { return reverse_iterator(end()); } + const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rend() const { return const_reverse_iterator(begin());} + + void flattenLocations() { + for (iterator I = begin(), E = end(); I != E; ++I) I->flattenLocations(); + } + + void Profile(llvm::FoldingSetNodeID &ID) const; +}; + +} // end GR namespace + +} //end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/CheckerManager.h b/include/clang/StaticAnalyzer/Core/CheckerManager.h new file mode 100644 index 0000000..65c8b80 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/CheckerManager.h @@ -0,0 +1,109 @@ +//===--- CheckerManager.h - Static Analyzer Checker Manager -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Defines the Static Analyzer Checker Manager. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SA_CORE_CHECKERMANAGER_H +#define LLVM_CLANG_SA_CORE_CHECKERMANAGER_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/DenseMap.h" +#include <vector> + +namespace clang { + class Decl; + +namespace ento { + class ExprEngine; + class AnalysisManager; + class BugReporter; + +class CheckerManager { +public: + ~CheckerManager(); + + typedef void *CheckerRef; + +//===----------------------------------------------------------------------===// +// registerChecker +//===----------------------------------------------------------------------===// + + /// \brief Used to register checkers. + template <typename CHECKER> + void registerChecker() { + CHECKER *checker = new CHECKER(); + Checkers.push_back(std::pair<CheckerRef, Dtor>(checker, destruct<CHECKER>)); + CHECKER::_register(checker, *this); + } + + typedef void (*RegisterToEngFunc)(ExprEngine &Eng); + void addCheckerRegisterFunction(RegisterToEngFunc fn) { + Funcs.push_back(fn); + } + +//===----------------------------------------------------------------------===// +// Functions for running checkers. +//===----------------------------------------------------------------------===// + + /// \brief Run checkers handling Decls. + void runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr, + BugReporter &BR); + + /// \brief Run checkers handling Decls containing a Stmt body. + void runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr, + BugReporter &BR); + +//===----------------------------------------------------------------------===// +// Internal registration functions. +//===----------------------------------------------------------------------===// + + // Functions used by the registration mechanism, checkers should not touch + // these directly. + + typedef void (*CheckDeclFunc)(CheckerRef checker, const Decl *D, + AnalysisManager& mgr, BugReporter &BR); + typedef bool (*HandlesDeclFunc)(const Decl *D); + void _registerForDecl(CheckerRef checker, CheckDeclFunc checkfn, + HandlesDeclFunc isForDeclFn); + + void _registerForBody(CheckerRef checker, CheckDeclFunc checkfn); + + void registerCheckersToEngine(ExprEngine &eng); + +private: + template <typename CHECKER> + static void destruct(void *obj) { delete static_cast<CHECKER *>(obj); } + + std::vector<RegisterToEngFunc> Funcs; + + struct DeclCheckerInfo { + CheckerRef Checker; + CheckDeclFunc CheckFn; + HandlesDeclFunc IsForDeclFn; + }; + std::vector<DeclCheckerInfo> DeclCheckers; + + std::vector<std::pair<CheckerRef, CheckDeclFunc> > BodyCheckers; + + typedef void (*Dtor)(void *); + std::vector<std::pair<CheckerRef, Dtor> > Checkers; + + typedef llvm::SmallVector<std::pair<CheckerRef, CheckDeclFunc>, 4> + CachedDeclCheckers; + typedef llvm::DenseMap<unsigned, CachedDeclCheckers> CachedDeclCheckersMapTy; + CachedDeclCheckersMapTy CachedDeclCheckersMap; +}; + +} // end ento namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/CheckerProvider.h b/include/clang/StaticAnalyzer/Core/CheckerProvider.h new file mode 100644 index 0000000..414ad92 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/CheckerProvider.h @@ -0,0 +1,54 @@ +//===--- CheckerProvider.h - Static Analyzer Checkers Provider --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Defines the Static Analyzer Checker Provider. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SA_CORE_CHECKERPROVIDER_H +#define LLVM_CLANG_SA_CORE_CHECKERPROVIDER_H + +#include "llvm/ADT/StringRef.h" +#include <vector> + +namespace clang { + +namespace ento { + class CheckerManager; + +class CheckerOptInfo { + const char *Name; + bool Enable; + bool Claimed; + +public: + CheckerOptInfo(const char *name, bool enable) + : Name(name), Enable(enable), Claimed(false) { } + + const char *getName() const { return Name; } + bool isEnabled() const { return Enable; } + bool isDisabled() const { return !isEnabled(); } + + bool isClaimed() const { return Claimed; } + bool isUnclaimed() const { return !isClaimed(); } + void claim() { Claimed = true; } +}; + +class CheckerProvider { +public: + virtual ~CheckerProvider(); + virtual void registerCheckers(CheckerManager &checkerMgr, + CheckerOptInfo *checkOpts, unsigned numCheckOpts) = 0; +}; + +} // end ento namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/CheckerV2.h b/include/clang/StaticAnalyzer/Core/CheckerV2.h new file mode 100644 index 0000000..8c96866 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/CheckerV2.h @@ -0,0 +1,93 @@ +//== CheckerV2.h - Registration mechanism for checkers -----------*- C++ -*--=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines CheckerV2, used to create and register checkers. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SA_CORE_CHECKERV2 +#define LLVM_CLANG_SA_CORE_CHECKERV2 + +#include "clang/StaticAnalyzer/Core/CheckerManager.h" +#include "llvm/Support/Casting.h" + +namespace clang { +namespace ento { + class BugReporter; + +namespace check { + +struct _VoidCheck { + static void _register(void *checker, CheckerManager &mgr) { } +}; + +template <typename DECL> +class ASTDecl { + template <typename CHECKER> + static void _checkDecl(void *checker, const Decl *D, AnalysisManager& mgr, + BugReporter &BR) { + ((const CHECKER *)checker)->checkASTDecl(llvm::cast<DECL>(D), mgr, BR); + } + + static bool _handlesDecl(const Decl *D) { + return llvm::isa<DECL>(D); + } +public: + template <typename CHECKER> + static void _register(CHECKER *checker, CheckerManager &mgr) { + mgr._registerForDecl(checker, _checkDecl<CHECKER>, _handlesDecl); + } +}; + +class ASTCodeBody { + template <typename CHECKER> + static void _checkBody(void *checker, const Decl *D, AnalysisManager& mgr, + BugReporter &BR) { + ((const CHECKER *)checker)->checkASTCodeBody(D, mgr, BR); + } + +public: + template <typename CHECKER> + static void _register(CHECKER *checker, CheckerManager &mgr) { + mgr._registerForBody(checker, _checkBody<CHECKER>); + } +}; + +} // end check namespace + +template <typename CHECK1, typename CHECK2=check::_VoidCheck, + typename CHECK3=check::_VoidCheck, typename CHECK4=check::_VoidCheck, + typename CHECK5=check::_VoidCheck, typename CHECK6=check::_VoidCheck, + typename CHECK7=check::_VoidCheck, typename CHECK8=check::_VoidCheck, + typename CHECK9=check::_VoidCheck, typename CHECK10=check::_VoidCheck, + typename CHECK11=check::_VoidCheck,typename CHECK12=check::_VoidCheck> +class CheckerV2 { +public: + template <typename CHECKER> + static void _register(CHECKER *checker, CheckerManager &mgr) { + CHECK1::_register(checker, mgr); + CHECK2::_register(checker, mgr); + CHECK3::_register(checker, mgr); + CHECK4::_register(checker, mgr); + CHECK5::_register(checker, mgr); + CHECK6::_register(checker, mgr); + CHECK7::_register(checker, mgr); + CHECK8::_register(checker, mgr); + CHECK9::_register(checker, mgr); + CHECK10::_register(checker, mgr); + CHECK11::_register(checker, mgr); + CHECK12::_register(checker, mgr); + } +}; + +} // end ento namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathDiagnosticClients.h b/include/clang/StaticAnalyzer/Core/PathDiagnosticClients.h new file mode 100644 index 0000000..2713e31 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathDiagnosticClients.h @@ -0,0 +1,42 @@ +//===--- PathDiagnosticClients.h - Path Diagnostic Clients ------*- 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 the interface to create different path diagostic clients. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_PATH_DIAGNOSTIC_CLIENTS_H +#define LLVM_CLANG_GR_PATH_DIAGNOSTIC_CLiENTS_H + +#include <string> + +namespace clang { + +class Preprocessor; + +namespace ento { + +class PathDiagnosticClient; + +PathDiagnosticClient* +createHTMLDiagnosticClient(const std::string& prefix, const Preprocessor &PP); + +PathDiagnosticClient* +createPlistDiagnosticClient(const std::string& prefix, const Preprocessor &PP, + PathDiagnosticClient *SubPD = 0); + +PathDiagnosticClient* +createTextPathDiagnosticClient(const std::string& prefix, + const Preprocessor &PP); + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h new file mode 100644 index 0000000..1ba038e --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h @@ -0,0 +1,220 @@ +//== AnalysisManager.h - Path sensitive analysis data manager ------*- 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 the AnalysisManager class that manages the data and policy +// for path sensitive analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_ANALYSISMANAGER_H +#define LLVM_CLANG_GR_ANALYSISMANAGER_H + +#include "clang/Analysis/AnalysisContext.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" +#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" + +namespace clang { + +namespace idx { + class Indexer; + class TranslationUnit; +} + +namespace ento { + class CheckerManager; + +class AnalysisManager : public BugReporterData { + AnalysisContextManager AnaCtxMgr; + LocationContextManager LocCtxMgr; + + ASTContext &Ctx; + Diagnostic &Diags; + const LangOptions &LangInfo; + + llvm::OwningPtr<PathDiagnosticClient> PD; + + // Configurable components creators. + StoreManagerCreator CreateStoreMgr; + ConstraintManagerCreator CreateConstraintMgr; + + CheckerManager *CheckerMgr; + + /// \brief Provide function definitions in other translation units. This is + /// NULL if we don't have multiple translation units. AnalysisManager does + /// not own the Indexer. + idx::Indexer *Idxer; + + enum AnalysisScope { ScopeTU, ScopeDecl } AScope; + + // The maximum number of exploded nodes the analyzer will generate. + unsigned MaxNodes; + + // The maximum number of times the analyzer visit a block. + unsigned MaxVisit; + + bool VisualizeEGDot; + bool VisualizeEGUbi; + bool PurgeDead; + + /// EargerlyAssume - A flag indicating how the engine should handle + // expressions such as: 'x = (y != 0)'. When this flag is true then + // the subexpression 'y != 0' will be eagerly assumed to be true or false, + // thus evaluating it to the integers 0 or 1 respectively. The upside + // is that this can increase analysis precision until we have a better way + // to lazily evaluate such logic. The downside is that it eagerly + // bifurcates paths. + bool EagerlyAssume; + bool TrimGraph; + bool InlineCall; + bool EagerlyTrimEGraph; + +public: + AnalysisManager(ASTContext &ctx, Diagnostic &diags, + const LangOptions &lang, PathDiagnosticClient *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 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) {} + + ~AnalysisManager() { FlushDiagnostics(); } + + void ClearContexts() { + LocCtxMgr.clear(); + AnaCtxMgr.clear(); + } + + AnalysisContextManager& getAnalysisContextManager() { + return AnaCtxMgr; + } + + StoreManagerCreator getStoreManagerCreator() { + return CreateStoreMgr; + } + + ConstraintManagerCreator getConstraintManagerCreator() { + return CreateConstraintMgr; + } + + CheckerManager *getCheckerManager() const { return CheckerMgr; } + + idx::Indexer *getIndexer() const { return Idxer; } + + virtual ASTContext &getASTContext() { + return Ctx; + } + + virtual SourceManager &getSourceManager() { + return getASTContext().getSourceManager(); + } + + virtual Diagnostic &getDiagnostic() { + return Diags; + } + + const LangOptions &getLangOptions() const { + return LangInfo; + } + + virtual PathDiagnosticClient *getPathDiagnosticClient() { + return PD.get(); + } + + void FlushDiagnostics() { + if (PD.get()) + PD->FlushDiagnostics(); + } + + unsigned getMaxNodes() const { return MaxNodes; } + + unsigned getMaxVisit() const { return MaxVisit; } + + bool shouldVisualizeGraphviz() const { return VisualizeEGDot; } + + bool shouldVisualizeUbigraph() const { return VisualizeEGUbi; } + + bool shouldVisualize() const { + return VisualizeEGDot || VisualizeEGUbi; + } + + bool shouldEagerlyTrimExplodedGraph() const { return EagerlyTrimEGraph; } + + bool shouldTrimGraph() const { return TrimGraph; } + + bool shouldPurgeDead() const { return PurgeDead; } + + bool shouldEagerlyAssume() const { return EagerlyAssume; } + + bool shouldInlineCall() const { return InlineCall; } + + bool hasIndexer() const { return Idxer != 0; } + + AnalysisContext *getAnalysisContextInAnotherTU(const Decl *D); + + CFG *getCFG(Decl const *D) { + return AnaCtxMgr.getContext(D)->getCFG(); + } + + LiveVariables *getLiveVariables(Decl const *D) { + return AnaCtxMgr.getContext(D)->getLiveVariables(); + } + + ParentMap &getParentMap(Decl const *D) { + return AnaCtxMgr.getContext(D)->getParentMap(); + } + + AnalysisContext *getAnalysisContext(const Decl *D) { + return AnaCtxMgr.getContext(D); + } + + AnalysisContext *getAnalysisContext(const Decl *D, idx::TranslationUnit *TU) { + return AnaCtxMgr.getContext(D, TU); + } + + const StackFrameContext *getStackFrame(AnalysisContext *Ctx, + LocationContext const *Parent, + const Stmt *S, + const CFGBlock *Blk, unsigned Idx) { + return LocCtxMgr.getStackFrame(Ctx, Parent, S, Blk, Idx); + } + + // Get the top level stack frame. + const StackFrameContext *getStackFrame(Decl const *D, + idx::TranslationUnit *TU) { + return LocCtxMgr.getStackFrame(AnaCtxMgr.getContext(D, TU), 0, 0, 0, 0); + } + + // Get a stack frame with parent. + StackFrameContext const *getStackFrame(const Decl *D, + LocationContext const *Parent, + const Stmt *S, + const CFGBlock *Blk, unsigned Idx) { + return LocCtxMgr.getStackFrame(AnaCtxMgr.getContext(D), Parent, S, + Blk,Idx); + } +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h b/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h new file mode 100644 index 0000000..a4327e1 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h @@ -0,0 +1,201 @@ +//=== BasicValueFactory.h - Basic values for Path Sens analysis --*- 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 BasicValueFactory, a class that manages the lifetime +// of APSInt objects and symbolic constraints used by ExprEngine +// and related classes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_BASICVALUEFACTORY_H +#define LLVM_CLANG_GR_BASICVALUEFACTORY_H + +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "clang/AST/ASTContext.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/ADT/ImmutableList.h" + +namespace clang { + +namespace ento { + + class GRState; + +class CompoundValData : public llvm::FoldingSetNode { + QualType T; + llvm::ImmutableList<SVal> L; + +public: + CompoundValData(QualType t, llvm::ImmutableList<SVal> l) + : T(t), L(l) {} + + typedef llvm::ImmutableList<SVal>::iterator iterator; + iterator begin() const { return L.begin(); } + iterator end() const { return L.end(); } + + static void Profile(llvm::FoldingSetNodeID& ID, QualType T, + llvm::ImmutableList<SVal> L); + + void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); } +}; + +class LazyCompoundValData : public llvm::FoldingSetNode { + const void *store; + const TypedRegion *region; +public: + LazyCompoundValData(const void *st, const TypedRegion *r) + : store(st), region(r) {} + + const void *getStore() const { return store; } + const TypedRegion *getRegion() const { return region; } + + static void Profile(llvm::FoldingSetNodeID& ID, const void *store, + const TypedRegion *region); + + void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, store, region); } +}; + +class BasicValueFactory { + typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt> > + APSIntSetTy; + + ASTContext& Ctx; + llvm::BumpPtrAllocator& BPAlloc; + + APSIntSetTy APSIntSet; + void* PersistentSVals; + void* PersistentSValPairs; + + llvm::ImmutableList<SVal>::Factory SValListFactory; + llvm::FoldingSet<CompoundValData> CompoundValDataSet; + llvm::FoldingSet<LazyCompoundValData> LazyCompoundValDataSet; + +public: + BasicValueFactory(ASTContext& ctx, llvm::BumpPtrAllocator& Alloc) + : Ctx(ctx), BPAlloc(Alloc), PersistentSVals(0), PersistentSValPairs(0), + SValListFactory(Alloc) {} + + ~BasicValueFactory(); + + ASTContext& getContext() const { return Ctx; } + + const llvm::APSInt& getValue(const llvm::APSInt& X); + const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned); + const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned); + const llvm::APSInt& getValue(uint64_t X, QualType T); + + /// Convert - Create a new persistent APSInt with the same value as 'From' + /// but with the bitwidth and signedness of 'To'. + const llvm::APSInt &Convert(const llvm::APSInt& To, + const llvm::APSInt& From) { + + if (To.isUnsigned() == From.isUnsigned() && + To.getBitWidth() == From.getBitWidth()) + return From; + + return getValue(From.getSExtValue(), To.getBitWidth(), To.isUnsigned()); + } + + const llvm::APSInt &Convert(QualType T, const llvm::APSInt &From) { + assert(T->isIntegerType() || Loc::isLocType(T)); + unsigned bitwidth = Ctx.getTypeSize(T); + bool isUnsigned = T->isUnsignedIntegerType() || Loc::isLocType(T); + + if (isUnsigned == From.isUnsigned() && bitwidth == From.getBitWidth()) + return From; + + return getValue(From.getSExtValue(), bitwidth, isUnsigned); + } + + const llvm::APSInt& getIntValue(uint64_t X, bool isUnsigned) { + QualType T = isUnsigned ? Ctx.UnsignedIntTy : Ctx.IntTy; + return getValue(X, T); + } + + inline const llvm::APSInt& getMaxValue(const llvm::APSInt &v) { + return getValue(llvm::APSInt::getMaxValue(v.getBitWidth(), v.isUnsigned())); + } + + inline const llvm::APSInt& getMinValue(const llvm::APSInt &v) { + return getValue(llvm::APSInt::getMinValue(v.getBitWidth(), v.isUnsigned())); + } + + inline const llvm::APSInt& getMaxValue(QualType T) { + assert(T->isIntegerType() || Loc::isLocType(T)); + bool isUnsigned = T->isUnsignedIntegerType() || Loc::isLocType(T); + return getValue(llvm::APSInt::getMaxValue(Ctx.getTypeSize(T), isUnsigned)); + } + + inline const llvm::APSInt& getMinValue(QualType T) { + assert(T->isIntegerType() || Loc::isLocType(T)); + bool isUnsigned = T->isUnsignedIntegerType() || Loc::isLocType(T); + return getValue(llvm::APSInt::getMinValue(Ctx.getTypeSize(T), isUnsigned)); + } + + inline const llvm::APSInt& Add1(const llvm::APSInt& V) { + llvm::APSInt X = V; + ++X; + return getValue(X); + } + + inline const llvm::APSInt& Sub1(const llvm::APSInt& V) { + llvm::APSInt X = V; + --X; + return getValue(X); + } + + inline const llvm::APSInt& getZeroWithPtrWidth(bool isUnsigned = true) { + return getValue(0, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned); + } + + inline const llvm::APSInt &getIntWithPtrWidth(uint64_t X, bool isUnsigned) { + return getValue(X, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned); + } + + inline const llvm::APSInt& getTruthValue(bool b, QualType T) { + return getValue(b ? 1 : 0, Ctx.getTypeSize(T), false); + } + + inline const llvm::APSInt& getTruthValue(bool b) { + return getTruthValue(b, Ctx.getLogicalOperationType()); + } + + const CompoundValData *getCompoundValData(QualType T, + llvm::ImmutableList<SVal> Vals); + + const LazyCompoundValData *getLazyCompoundValData(const void *store, + const TypedRegion *region); + + llvm::ImmutableList<SVal> getEmptySValList() { + return SValListFactory.getEmptyList(); + } + + llvm::ImmutableList<SVal> consVals(SVal X, llvm::ImmutableList<SVal> L) { + return SValListFactory.add(X, L); + } + + const llvm::APSInt* evalAPSInt(BinaryOperator::Opcode Op, + const llvm::APSInt& V1, + const llvm::APSInt& V2); + + const std::pair<SVal, uintptr_t>& + getPersistentSValWithData(const SVal& V, uintptr_t Data); + + const std::pair<SVal, SVal>& + getPersistentSValPair(const SVal& V1, const SVal& V2); + + const SVal* getPersistentSVal(SVal X); +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h b/include/clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h new file mode 100644 index 0000000..7d0fdfb --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h @@ -0,0 +1,59 @@ +//==- BlockCounter.h - ADT for counting block visits ---------------*- 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 BlockCounter, an abstract data type used to count +// the number of times a given block has been visited along a path +// analyzed by CoreEngine. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_BLOCKCOUNTER +#define LLVM_CLANG_GR_BLOCKCOUNTER + +namespace llvm { + class BumpPtrAllocator; +} + +namespace clang { + +class StackFrameContext; + +namespace ento { + +class BlockCounter { + void* Data; + + BlockCounter(void* D) : Data(D) {} + +public: + BlockCounter() : Data(0) {} + + unsigned getNumVisited(const StackFrameContext *CallSite, + unsigned BlockID) const; + + class Factory { + void* F; + public: + Factory(llvm::BumpPtrAllocator& Alloc); + ~Factory(); + + BlockCounter GetEmptyCounter(); + BlockCounter IncrementCount(BlockCounter BC, + const StackFrameContext *CallSite, + unsigned BlockID); + }; + + friend class Factory; +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Checker.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Checker.h new file mode 100644 index 0000000..22c2027 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Checker.h @@ -0,0 +1,324 @@ +//== Checker.h - Abstract interface for checkers -----------------*- C++ -*--=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines Checker and CheckerVisitor, classes used for creating +// domain-specific checks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_CHECKER +#define LLVM_CLANG_GR_CHECKER + +#include "clang/Analysis/Support/SaveAndRestore.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" + +//===----------------------------------------------------------------------===// +// Checker interface. +//===----------------------------------------------------------------------===// + +namespace clang { + +namespace ento { + +class CheckerContext { + ExplodedNodeSet &Dst; + StmtNodeBuilder &B; + ExprEngine &Eng; + ExplodedNode *Pred; + SaveAndRestore<bool> OldSink; + const void *checkerTag; + SaveAndRestore<ProgramPoint::Kind> OldPointKind; + SaveOr OldHasGen; + const GRState *ST; + const Stmt *statement; + const unsigned size; +public: + bool *respondsToCallback; +public: + CheckerContext(ExplodedNodeSet &dst, StmtNodeBuilder &builder, + ExprEngine &eng, ExplodedNode *pred, + const void *tag, ProgramPoint::Kind K, + bool *respondsToCB = 0, + const Stmt *stmt = 0, const GRState *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()), + respondsToCallback(respondsToCB) {} + + ~CheckerContext(); + + ExprEngine &getEngine() { + return Eng; + } + + AnalysisManager &getAnalysisManager() { + return Eng.getAnalysisManager(); + } + + ConstraintManager &getConstraintManager() { + return Eng.getConstraintManager(); + } + + StoreManager &getStoreManager() { + return Eng.getStoreManager(); + } + + ExplodedNodeSet &getNodeSet() { return Dst; } + StmtNodeBuilder &getNodeBuilder() { return B; } + ExplodedNode *&getPredecessor() { return Pred; } + const GRState *getState() { return ST ? ST : B.GetState(Pred); } + + ASTContext &getASTContext() { + return Eng.getContext(); + } + + BugReporter &getBugReporter() { + return Eng.getBugReporter(); + } + + SourceManager &getSourceManager() { + return getBugReporter().getSourceManager(); + } + + SValBuilder &getSValBuilder() { + 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; + } + + 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; + } + + ExplodedNode *generateNode(const GRState *state, ExplodedNode *pred, + bool autoTransition = true) { + assert(statement && "Only transitions with statements currently supported"); + ExplodedNode *N = generateNodeImpl(statement, state, pred, false); + 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); + 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); + } + + void addTransition(ExplodedNode *node) { + Dst.Add(node); + } + + void addTransition(const GRState *state, const void *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))) + // state is new or equals to ST. + generateNode(state, true, tag); + else + Dst.Add(Pred); + } + + void EmitReport(BugReport *R) { + Eng.getBugReporter().EmitReport(R); + } + + AnalysisContext *getCurrentAnalysisContext() const { + return Pred->getLocationContext()->getAnalysisContext(); + } + +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); + if (markAsSink && node) + node->markAsSink(); + return node; + } +}; + +class Checker { +private: + friend class ExprEngine; + + // FIXME: Remove the 'tag' option. + void GR_Visit(ExplodedNodeSet &Dst, + StmtNodeBuilder &Builder, + ExprEngine &Eng, + const Stmt *S, + ExplodedNode *Pred, void *tag, bool isPrevisit, + bool& respondsToCallback) { + CheckerContext C(Dst, Builder, Eng, Pred, tag, + isPrevisit ? ProgramPoint::PreStmtKind : + ProgramPoint::PostStmtKind, &respondsToCallback, S); + if (isPrevisit) + _PreVisit(C, S); + else + _PostVisit(C, S); + } + + void GR_visitObjCMessage(ExplodedNodeSet &Dst, + StmtNodeBuilder &Builder, + ExprEngine &Eng, + const ObjCMessage &msg, + ExplodedNode *Pred, void *tag, bool isPrevisit) { + CheckerContext C(Dst, Builder, Eng, Pred, tag, + isPrevisit ? ProgramPoint::PreStmtKind : + ProgramPoint::PostStmtKind, 0, msg.getOriginExpr()); + if (isPrevisit) + preVisitObjCMessage(C, msg); + else + postVisitObjCMessage(C, msg); + } + + bool GR_evalNilReceiver(ExplodedNodeSet &Dst, StmtNodeBuilder &Builder, + ExprEngine &Eng, const ObjCMessage &msg, + ExplodedNode *Pred, const GRState *state, void *tag) { + CheckerContext C(Dst, Builder, Eng, Pred, tag, ProgramPoint::PostStmtKind, + 0, msg.getOriginExpr(), state); + return evalNilReceiver(C, msg); + } + + bool GR_evalCallExpr(ExplodedNodeSet &Dst, StmtNodeBuilder &Builder, + ExprEngine &Eng, const CallExpr *CE, + ExplodedNode *Pred, void *tag) { + CheckerContext C(Dst, Builder, Eng, Pred, tag, ProgramPoint::PostStmtKind, + 0, CE); + return evalCallExpr(C, CE); + } + + // FIXME: Remove the 'tag' option. + void GR_VisitBind(ExplodedNodeSet &Dst, + StmtNodeBuilder &Builder, ExprEngine &Eng, + const Stmt *StoreE, ExplodedNode *Pred, void *tag, + SVal location, SVal val, + bool isPrevisit) { + CheckerContext C(Dst, Builder, Eng, Pred, tag, + isPrevisit ? ProgramPoint::PreStmtKind : + ProgramPoint::PostStmtKind, 0, StoreE); + assert(isPrevisit && "Only previsit supported for now."); + PreVisitBind(C, StoreE, location, val); + } + + // FIXME: Remove the 'tag' option. + void GR_visitLocation(ExplodedNodeSet &Dst, + StmtNodeBuilder &Builder, + ExprEngine &Eng, + const Stmt *S, + ExplodedNode *Pred, const GRState *state, + SVal location, + void *tag, bool isLoad) { + CheckerContext C(Dst, Builder, Eng, Pred, tag, + isLoad ? ProgramPoint::PreLoadKind : + ProgramPoint::PreStoreKind, 0, S, state); + visitLocation(C, S, location, isLoad); + } + + void GR_evalDeadSymbols(ExplodedNodeSet &Dst, StmtNodeBuilder &Builder, + ExprEngine &Eng, const Stmt *S, ExplodedNode *Pred, + SymbolReaper &SymReaper, void *tag) { + CheckerContext C(Dst, Builder, Eng, Pred, tag, + ProgramPoint::PostPurgeDeadSymbolsKind, 0, S); + evalDeadSymbols(C, SymReaper); + } + +public: + virtual ~Checker(); + virtual void _PreVisit(CheckerContext &C, const Stmt *S) {} + virtual void _PostVisit(CheckerContext &C, const Stmt *S) {} + virtual void preVisitObjCMessage(CheckerContext &C, ObjCMessage msg) {} + virtual void postVisitObjCMessage(CheckerContext &C, ObjCMessage msg) {} + virtual void visitLocation(CheckerContext &C, const Stmt *S, SVal location, + bool isLoad) {} + virtual void PreVisitBind(CheckerContext &C, const Stmt *StoreE, + SVal location, SVal val) {} + virtual void evalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper) {} + virtual void evalEndPath(EndOfFunctionNodeBuilder &B, void *tag, + ExprEngine &Eng) {} + + virtual void MarkLiveSymbols(const GRState *state, SymbolReaper &SymReaper) {} + + virtual void VisitBranchCondition(BranchNodeBuilder &Builder, + ExprEngine &Eng, + const Stmt *Condition, void *tag) {} + + virtual bool evalNilReceiver(CheckerContext &C, ObjCMessage msg) { + return false; + } + + virtual bool evalCallExpr(CheckerContext &C, const CallExpr *CE) { + return false; + } + + virtual const GRState *evalAssume(const GRState *state, SVal Cond, + bool Assumption, bool *respondsToCallback) { + *respondsToCallback = false; + return state; + } + + virtual bool wantsRegionChangeUpdate(const GRState *state) { return false; } + + virtual const GRState *EvalRegionChanges(const GRState *state, + const MemRegion * const *Begin, + const MemRegion * const *End, + bool *respondsToCallback) { + *respondsToCallback = false; + return state; + } + + virtual void VisitEndAnalysis(ExplodedGraph &G, BugReporter &B, + ExprEngine &Eng) {} +}; + +} // end GR namespace + +} // end clang namespace + +#endif + diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h new file mode 100644 index 0000000..12547e0 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h @@ -0,0 +1,43 @@ +//== CheckerHelpers.h - Helper functions for checkers ------------*- C++ -*--=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines CheckerVisitor. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_PATHSENSITIVE_CHECKERHELPERS +#define LLVM_CLANG_GR_PATHSENSITIVE_CHECKERHELPERS + +#include "clang/AST/Stmt.h" + +namespace clang { + +namespace ento { + +bool containsMacro(const Stmt *S); +bool containsEnum(const Stmt *S); +bool containsStaticLocal(const Stmt *S); +bool containsBuiltinOffsetOf(const Stmt *S); +template <class T> bool containsStmt(const Stmt *S) { + if (isa<T>(S)) + return true; + + for (Stmt::const_child_range I = S->children(); I; ++I) + if (const Stmt *child = *I) + if (containsStmt<T>(child)) + return true; + + return false; +} + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.def b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.def new file mode 100644 index 0000000..9b3c263 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.def @@ -0,0 +1,48 @@ +//===-- CheckerVisitor.def - Metadata for CheckerVisitor ----------------*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the AST nodes accepted by the CheckerVisitor class. +// +//===---------------------------------------------------------------------===// + +#ifndef PREVISIT +#define PREVISIT(NODE, FALLBACK) +#endif + +#ifndef POSTVISIT +#define POSTVISIT(NODE, FALLBACK) +#endif + +PREVISIT(ArraySubscriptExpr, Stmt) +PREVISIT(BinaryOperator, Stmt) +PREVISIT(CallExpr, GenericCall) +PREVISIT(CompoundAssignOperator, BinaryOperator) +PREVISIT(CStyleCastExpr, CastExpr) +PREVISIT(CXXConstCastExpr, CastExpr) +PREVISIT(CXXDynamicCastExpr, CastExpr) +PREVISIT(CXXFunctionalCastExpr, CastExpr) +PREVISIT(CXXOperatorCallExpr, GenericCall) +PREVISIT(CXXMemberCallExpr, GenericCall) +PREVISIT(CXXReinterpretCastExpr, CastExpr) +PREVISIT(CXXStaticCastExpr, CastExpr) +PREVISIT(DeclStmt, Stmt) +PREVISIT(ImplicitCastExpr, CastExpr) +PREVISIT(ObjCAtSynchronizedStmt, Stmt) +PREVISIT(ReturnStmt, Stmt) + +POSTVISIT(BlockExpr, Stmt) +POSTVISIT(BinaryOperator, Stmt) +POSTVISIT(CallExpr, GenericCall) +POSTVISIT(CompoundAssignOperator, BinaryOperator) +POSTVISIT(CXXOperatorCallExpr, GenericCall) +POSTVISIT(CXXMemberCallExpr, GenericCall) +POSTVISIT(ObjCIvarRefExpr, Stmt) + +#undef PREVISIT +#undef POSTVISIT diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.h new file mode 100644 index 0000000..dc76c96 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.h @@ -0,0 +1,103 @@ +//== CheckerVisitor.h - Abstract visitor for checkers ------------*- C++ -*--=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines CheckerVisitor. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_CHECKERVISITOR +#define LLVM_CLANG_GR_CHECKERVISITOR +#include "clang/StaticAnalyzer/Core/PathSensitive/Checker.h" + +namespace clang { + +namespace ento { + +//===----------------------------------------------------------------------===// +// Checker visitor interface. Used by subclasses of Checker to specify their +// own checker visitor logic. +//===----------------------------------------------------------------------===// + +/// CheckerVisitor - This class implements a simple visitor for Stmt subclasses. +/// Since Expr derives from Stmt, this also includes support for visiting Exprs. +template<typename ImplClass> +class CheckerVisitor : public Checker { +public: + virtual void _PreVisit(CheckerContext &C, const Stmt *S) { + PreVisit(C, S); + } + + virtual void _PostVisit(CheckerContext &C, const Stmt *S) { + PostVisit(C, S); + } + + void PreVisit(CheckerContext &C, const Stmt *S) { + switch (S->getStmtClass()) { + default: + assert(false && "Unsupport statement."); + return; + +#define PREVISIT(NAME, FALLBACK) \ +case Stmt::NAME ## Class:\ +static_cast<ImplClass*>(this)->PreVisit ## NAME(C,static_cast<const NAME*>(S));\ +break; +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.def" + } + } + + void PostVisit(CheckerContext &C, const Stmt *S) { + switch (S->getStmtClass()) { + default: + assert(false && "Unsupport statement."); + return; + +#define POSTVISIT(NAME, FALLBACK) \ +case Stmt::NAME ## Class:\ +static_cast<ImplClass*>(this)->\ +PostVisit ## NAME(C,static_cast<const NAME*>(S));\ +break; +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.def" + } + } + + void PreVisitGenericCall(CheckerContext &C, const CallExpr *CE) { + static_cast<ImplClass*>(this)->PreVisitStmt(C, CE); + } + void PostVisitGenericCall(CheckerContext &C, const CallExpr *CE) { + static_cast<ImplClass*>(this)->PostVisitStmt(C, CE); + } + + void PreVisitStmt(CheckerContext &C, const Stmt *S) { + *C.respondsToCallback = false; + } + + void PostVisitStmt(CheckerContext &C, const Stmt *S) { + *C.respondsToCallback = false; + } + + void PreVisitCastExpr(CheckerContext &C, const CastExpr *E) { + static_cast<ImplClass*>(this)->PreVisitStmt(C, E); + } + +#define PREVISIT(NAME, FALLBACK) \ +void PreVisit ## NAME(CheckerContext &C, const NAME* S) {\ + static_cast<ImplClass*>(this)->PreVisit ## FALLBACK(C, S);\ +} +#define POSTVISIT(NAME, FALLBACK) \ +void PostVisit ## NAME(CheckerContext &C, const NAME* S) {\ + static_cast<ImplClass*>(this)->PostVisit ## FALLBACK(C, S);\ +} +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerVisitor.def" +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h new file mode 100644 index 0000000..199b41a --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h @@ -0,0 +1,76 @@ +//== ConstraintManager.h - Constraints on symbolic values.-------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the interface to manage constraints on symbolic values. +// +//===----------------------------------------------------------------------===// + +#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" + +namespace llvm { +class APSInt; +} + +namespace clang { + +namespace ento { + +class GRState; +class GRStateManager; +class SubEngine; +class SVal; + +class ConstraintManager { +public: + virtual ~ConstraintManager(); + virtual const GRState *assume(const GRState *state, DefinedSVal Cond, + bool Assumption) = 0; + + std::pair<const GRState*, const GRState*> assumeDual(const GRState *state, + DefinedSVal Cond) { + return std::make_pair(assume(state, Cond, true), + assume(state, Cond, false)); + } + + virtual const llvm::APSInt* getSymVal(const GRState *state, + SymbolRef sym) const = 0; + + virtual bool isEqual(const GRState *state, SymbolRef sym, + const llvm::APSInt& V) const = 0; + + virtual const GRState *removeDeadBindings(const GRState *state, + SymbolReaper& SymReaper) = 0; + + virtual void print(const GRState *state, llvm::raw_ostream& Out, + const char* nl, const char *sep) = 0; + + virtual void EndPath(const GRState *state) {} + + /// canReasonAbout - Not all ConstraintManagers can accurately reason about + /// all SVal values. This method returns true if the ConstraintManager can + /// reasonably handle a given SVal value. This is typically queried by + /// ExprEngine to determine if the value should be replaced with a + /// conjured symbolic value in order to recover some precision. + virtual bool canReasonAbout(SVal X) const = 0; +}; + +ConstraintManager* CreateBasicConstraintManager(GRStateManager& statemgr, + SubEngine &subengine); +ConstraintManager* CreateRangeConstraintManager(GRStateManager& statemgr, + SubEngine &subengine); + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h new file mode 100644 index 0000000..800e63a --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -0,0 +1,546 @@ +//==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- C++ -*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a generic engine for intraprocedural, path-sensitive, +// dataflow analysis via graph reachability. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_COREENGINE +#define LLVM_CLANG_GR_COREENGINE + +#include "clang/AST/Expr.h" +#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 { + +namespace ento { + +//===----------------------------------------------------------------------===// +/// CoreEngine - Implements the core logic of the graph-reachability +/// analysis. It traverses the CFG and generates the ExplodedGraph. +/// Program "states" are treated as opaque void pointers. +/// The template class CoreEngine (which subclasses CoreEngine) +/// provides the matching component to the engine that knows the actual types +/// for states. Note that this engine only dispatches to transfer functions +/// at the statement and block-level. The analyses themselves must implement +/// any transfer function logic and the sub-expression level (if any). +class CoreEngine { + friend class StmtNodeBuilder; + friend class GenericNodeBuilderImpl; + friend class BranchNodeBuilder; + friend class IndirectGotoNodeBuilder; + friend class SwitchNodeBuilder; + friend class EndOfFunctionNodeBuilder; + friend class CallEnterNodeBuilder; + friend class CallExitNodeBuilder; + +public: + typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > + BlocksAborted; +private: + + SubEngine& SubEng; + + /// G - The simulation graph. Each node is a (location,state) pair. + llvm::OwningPtr<ExplodedGraph> G; + + /// WList - A set of queued nodes that need to be processed by the + /// worklist algorithm. It is up to the implementation of WList to decide + /// the order that nodes are processed. + WorkList* WList; + + /// BCounterFactory - A factory object for created BlockCounter objects. + /// These are used to record for key nodes in the ExplodedGraph the + /// number of times different CFGBlocks have been visited along a path. + BlockCounter::Factory BCounterFactory; + + /// The locations where we stopped doing work because we visited a location + /// too many times. + BlocksAborted blocksAborted; + + void generateNode(const ProgramPoint& Loc, const GRState* State, + ExplodedNode* Pred); + + void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred); + void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred); + void HandleBlockExit(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 HandleCallEnter(const CallEnter &L, const CFGBlock *Block, + unsigned Index, ExplodedNode *Pred); + void HandleCallExit(const CallExit &L, ExplodedNode *Pred); + +private: + CoreEngine(const CoreEngine&); // Do not implement. + CoreEngine& operator=(const CoreEngine&); + +public: + /// Construct a CoreEngine object to analyze the provided CFG using + /// a DFS exploration of the exploded graph. + CoreEngine(SubEngine& subengine) + : SubEng(subengine), G(new ExplodedGraph()), + WList(WorkList::makeBFS()), + BCounterFactory(G->getAllocator()) {} + + /// Construct a CoreEngine object to analyze the provided CFG and to + /// use the provided worklist object to execute the worklist algorithm. + /// The CoreEngine object assumes ownership of 'wlist'. + CoreEngine(WorkList* wlist, SubEngine& subengine) + : SubEng(subengine), G(new ExplodedGraph()), WList(wlist), + BCounterFactory(G->getAllocator()) {} + + ~CoreEngine() { + delete WList; + } + + /// getGraph - Returns the exploded graph. + ExplodedGraph& getGraph() { return *G.get(); } + + /// takeGraph - Returns the exploded graph. Ownership of the graph is + /// transfered to the caller. + ExplodedGraph* takeGraph() { return G.take(); } + + /// 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, + ExplodedNodeSet &Dst); + + // Functions for external checking of whether we have unfinished work + bool wasBlockAborted() const { return !blocksAborted.empty(); } + bool hasWorkRemaining() const { return wasBlockAborted() || WList->hasWork(); } + + WorkList *getWorkList() const { return WList; } + + BlocksAborted::const_iterator blocks_aborted_begin() const { + return blocksAborted.begin(); + } + BlocksAborted::const_iterator blocks_aborted_end() const { + return blocksAborted.end(); + } +}; + +class StmtNodeBuilder { + CoreEngine& Eng; + const CFGBlock& B; + const unsigned Idx; + ExplodedNode* Pred; + GRStateManager& Mgr; + +public: + bool PurgingDeadSymbols; + bool BuildSinks; + bool hasGeneratedNode; + ProgramPoint::Kind PointKind; + const void *Tag; + + const GRState* CleanedState; + + + typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; + DeferredTy Deferred; + + void GenerateAutoTransition(ExplodedNode* N); + +public: + StmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N, + CoreEngine* e, GRStateManager &mgr); + + ~StmtNodeBuilder(); + + 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 { + return getBlockCounter().getNumVisited( + Pred->getLocationContext()->getCurrentStackFrame(), + 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) { + hasGeneratedNode = true; + + if (PurgingDeadSymbols) + K = ProgramPoint::PostPurgeDeadSymbolsKind; + + return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); + } + + ExplodedNode* generateNode(const Stmt *S, const GRState *St, + ExplodedNode *Pred, const void *tag = 0) { + return generateNode(S, St, Pred, PointKind, tag); + } + + ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State, + ExplodedNode* Pred) { + hasGeneratedNode = true; + return generateNodeInternal(PP, State, Pred); + } + + ExplodedNode* + generateNodeInternal(const ProgramPoint &PP, const GRState* State, + ExplodedNode* Pred); + + ExplodedNode* + generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred, + ProgramPoint::Kind K = ProgramPoint::PostStmtKind, + const void *tag = 0); + + /// getStmt - Return the current block-level expression associated with + /// this builder. + const Stmt* getStmt() const { + CFGStmt CS = B[Idx].getAs<CFGStmt>(); + if (CS) + return CS.getStmt(); + else + return 0; + } + + /// getBlock - Return the CFGBlock associated with the block-level expression + /// of this builder. + 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) { + return MakeNode(Dst, S, Pred, St, PointKind); + } + + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred, + const GRState* St, ProgramPoint::Kind K); + + ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S, + ExplodedNode* Pred, const GRState* St) { + bool Tmp = BuildSinks; + BuildSinks = true; + ExplodedNode* N = MakeNode(Dst, S, Pred, St); + BuildSinks = Tmp; + return N; + } +}; + +class BranchNodeBuilder { + CoreEngine& Eng; + const CFGBlock* Src; + const CFGBlock* DstT; + const CFGBlock* DstF; + ExplodedNode* Pred; + + typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy; + DeferredTy Deferred; + + bool GeneratedTrue; + bool GeneratedFalse; + bool InFeasibleTrue; + bool InFeasibleFalse; + +public: + 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; } + + const ExplodedGraph& getGraph() const { return *Eng.G; } + + BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} + + ExplodedNode* generateNode(const GRState* State, bool branch); + + const CFGBlock* getTargetBlock(bool branch) const { + return branch ? DstT : DstF; + } + + void markInfeasible(bool branch) { + if (branch) + InFeasibleTrue = GeneratedTrue = true; + else + InFeasibleFalse = GeneratedFalse = true; + } + + bool isFeasible(bool branch) { + return branch ? !InFeasibleTrue : !InFeasibleFalse; + } + + const GRState* getState() const { + return getPredecessor()->getState(); + } +}; + +class IndirectGotoNodeBuilder { + CoreEngine& Eng; + 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) + : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} + + class iterator { + CFGBlock::const_succ_iterator I; + + friend class IndirectGotoNodeBuilder; + iterator(CFGBlock::const_succ_iterator i) : I(i) {} + public: + + 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(); + } + + const CFGBlock *getBlock() const { + return *I; + } + }; + + iterator begin() { return iterator(DispatchBlock.succ_begin()); } + iterator end() { return iterator(DispatchBlock.succ_end()); } + + ExplodedNode* generateNode(const iterator& I, const GRState* State, + bool isSink = false); + + const Expr* getTarget() const { return E; } + + const GRState* getState() const { return Pred->State; } +}; + +class SwitchNodeBuilder { + CoreEngine& Eng; + const CFGBlock* Src; + const Expr* Condition; + ExplodedNode* Pred; + +public: + SwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src, + const Expr* condition, CoreEngine* eng) + : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} + + class iterator { + CFGBlock::const_succ_reverse_iterator I; + + friend class SwitchNodeBuilder; + iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} + + public: + iterator& operator++() { ++I; return *this; } + bool operator!=(const iterator &X) const { return I != X.I; } + bool operator==(const iterator &X) const { return I == X.I; } + + const CaseStmt* getCase() const { + return llvm::cast<CaseStmt>((*I)->getLabel()); + } + + const CFGBlock* getBlock() const { + return *I; + } + }; + + iterator begin() { return iterator(Src->succ_rbegin()+1); } + iterator end() { return iterator(Src->succ_rend()); } + + const SwitchStmt *getSwitch() const { + return llvm::cast<SwitchStmt>(Src->getTerminator()); + } + + ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State); + + ExplodedNode* generateDefaultCaseNode(const GRState* State, + bool isSink = false); + + const Expr* getCondition() const { return Condition; } + + const GRState* getState() const { return Pred->State; } +}; + +class GenericNodeBuilderImpl { +protected: + CoreEngine &engine; + ExplodedNode *pred; + ProgramPoint pp; + llvm::SmallVector<ExplodedNode*, 2> sinksGenerated; + + ExplodedNode *generateNodeImpl(const GRState *state, ExplodedNode *pred, + ProgramPoint programPoint, bool asSink); + + GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) + : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} + +public: + bool hasGeneratedNode; + + WorkList &getWorkList() { return *engine.WList; } + + ExplodedNode* getPredecessor() const { return pred; } + + BlockCounter getBlockCounter() const { + return engine.WList->getBlockCounter(); + } + + const llvm::SmallVectorImpl<ExplodedNode*> &sinks() const { + return sinksGenerated; + } +}; + +template <typename PP_T> +class GenericNodeBuilder : public GenericNodeBuilderImpl { +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) { + return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag), + asSink); + } + + const PP_T &getProgramPoint() const { return cast<PP_T>(pp); } +}; + +class EndOfFunctionNodeBuilder { + CoreEngine &Eng; + const CFGBlock& B; + ExplodedNode* Pred; + +public: + bool hasGeneratedNode; + +public: + EndOfFunctionNodeBuilder(const CFGBlock* b, ExplodedNode* N, CoreEngine* e) + : Eng(*e), B(*b), Pred(N), hasGeneratedNode(false) {} + + ~EndOfFunctionNodeBuilder(); + + WorkList &getWorkList() { return *Eng.WList; } + + ExplodedNode* getPredecessor() const { return Pred; } + + BlockCounter getBlockCounter() const { + return Eng.WList->getBlockCounter(); + } + + unsigned getCurrentBlockCount() const { + return getBlockCounter().getNumVisited( + Pred->getLocationContext()->getCurrentStackFrame(), + B.getBlockID()); + } + + ExplodedNode* generateNode(const GRState* State, const void *tag = 0, + ExplodedNode *P = 0); + + void GenerateCallExitNode(const GRState *state); + + const CFGBlock* getBlock() const { return &B; } + + const GRState* getState() const { + return getPredecessor()->getState(); + } +}; + +class CallEnterNodeBuilder { + CoreEngine &Eng; + + const ExplodedNode *Pred; + + // The call site. For implicit automatic object dtor, this is the trigger + // statement. + const Stmt *CE; + + // The context of the callee. + const StackFrameContext *CalleeCtx; + + // The parent block of the CallExpr. + const CFGBlock *Block; + + // The CFGBlock index of the CallExpr. + unsigned Index; + +public: + CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred, + const Stmt *s, const StackFrameContext *callee, + 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 LocationContext *getLocationContext() const { + return Pred->getLocationContext(); + } + + const Stmt *getCallExpr() const { return CE; } + + const StackFrameContext *getCalleeContext() const { return CalleeCtx; } + + const CFGBlock *getBlock() const { return Block; } + + unsigned getIndex() const { return Index; } + + void generateNode(const GRState *state); +}; + +class CallExitNodeBuilder { + CoreEngine &Eng; + const ExplodedNode *Pred; + +public: + CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred) + : Eng(eng), Pred(pred) {} + + const ExplodedNode *getPredecessor() const { return Pred; } + + const GRState *getState() const { return Pred->getState(); } + + void generateNode(const GRState *state); +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h new file mode 100644 index 0000000..732a40cb --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h @@ -0,0 +1,106 @@ +//== Environment.h - Map from Stmt* to Locations/Values ---------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the Environment and EnvironmentManager classes. +// +//===----------------------------------------------------------------------===// + +#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" + +namespace clang { + +class LiveVariables; + +namespace ento { + +class EnvironmentManager; +class SValBuilder; + +/// Environment - An immutable map from Stmts to their current +/// symbolic values (SVals). +/// +class Environment { +private: + friend class EnvironmentManager; + + // Type definitions. + typedef llvm::ImmutableMap<const Stmt*,SVal> BindingsTy; + + // Data. + BindingsTy ExprBindings; + + Environment(BindingsTy eb) + : ExprBindings(eb) {} + + SVal lookupExpr(const Stmt* E) const; + +public: + typedef BindingsTy::iterator iterator; + iterator begin() const { return ExprBindings.begin(); } + iterator end() const { return ExprBindings.end(); } + + + /// GetSVal - Fetches the current binding of the expression in the + /// Environment. + SVal getSVal(const Stmt* Ex, SValBuilder& svalBuilder) const; + + /// Profile - Profile the contents of an Environment object for use + /// in a FoldingSet. + static void Profile(llvm::FoldingSetNodeID& ID, const Environment* env) { + env->ExprBindings.Profile(ID); + } + + /// Profile - Used to profile the contents of this object for inclusion + /// in a FoldingSet. + void Profile(llvm::FoldingSetNodeID& ID) const { + Profile(ID, this); + } + + bool operator==(const Environment& RHS) const { + return ExprBindings == RHS.ExprBindings; + } +}; + +class EnvironmentManager { +private: + typedef Environment::BindingsTy::Factory FactoryTy; + FactoryTy F; + +public: + EnvironmentManager(llvm::BumpPtrAllocator& Allocator) : F(Allocator) {} + ~EnvironmentManager() {} + + Environment getInitialEnvironment() { + return Environment(F.getEmptyMap()); + } + + /// Bind the value 'V' to the statement 'S'. + Environment bindExpr(Environment Env, const Stmt *S, SVal V, + bool Invalidate); + + /// Bind the location 'location' and value 'V' to the statement 'S'. This + /// is used when simulating loads/stores. + Environment bindExprAndLocation(Environment Env, const Stmt *S, SVal location, + SVal V); + + Environment removeDeadBindings(Environment Env, + SymbolReaper &SymReaper, const GRState *ST, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots); +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h new file mode 100644 index 0000000..e5d6876 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -0,0 +1,469 @@ +//=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- 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 the template classes ExplodedNode and ExplodedGraph, +// which represent a path-sensitive, intra-procedural "exploded graph." +// See "Precise interprocedural dataflow analysis via graph reachability" +// by Reps, Horwitz, and Sagiv +// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an +// exploded graph. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_EXPLODEDGRAPH +#define LLVM_CLANG_GR_EXPLODEDGRAPH + +#include "clang/Analysis/ProgramPoint.h" +#include "clang/Analysis/AnalysisContext.h" +#include "clang/AST/Decl.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Support/Allocator.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/Support/Casting.h" +#include "clang/Analysis/Support/BumpVector.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h" + +namespace clang { + +class CFG; + +namespace ento { + +class ExplodedGraph; + +//===----------------------------------------------------------------------===// +// ExplodedGraph "implementation" classes. These classes are not typed to +// contain a specific kind of state. Typed-specialized versions are defined +// on top of these classes. +//===----------------------------------------------------------------------===// + +// ExplodedNode is not constified all over the engine because we need to add +// successors to it at any time after creating it. + +class ExplodedNode : public llvm::FoldingSetNode { + friend class ExplodedGraph; + friend class CoreEngine; + friend class StmtNodeBuilder; + friend class BranchNodeBuilder; + friend class IndirectGotoNodeBuilder; + friend class SwitchNodeBuilder; + friend class EndOfFunctionNodeBuilder; + + class NodeGroup { + enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 }; + uintptr_t P; + + unsigned getKind() const { + return P & 0x1; + } + + void* getPtr() const { + assert (!getFlag()); + return reinterpret_cast<void*>(P & ~Mask); + } + + ExplodedNode *getNode() const { + return reinterpret_cast<ExplodedNode*>(getPtr()); + } + + public: + NodeGroup() : P(0) {} + + ExplodedNode **begin() const; + + ExplodedNode **end() const; + + unsigned size() const; + + bool empty() const { return (P & ~Mask) == 0; } + + void addNode(ExplodedNode* N, ExplodedGraph &G); + + void replaceNode(ExplodedNode *node); + + void setFlag() { + assert(P == 0); + P = AuxFlag; + } + + bool getFlag() const { + return P & AuxFlag ? true : false; + } + }; + + /// Location - The program location (within a function body) associated + /// with this node. + const ProgramPoint Location; + + /// State - The state associated with this node. + const GRState* State; + + /// Preds - The predecessors of this node. + NodeGroup Preds; + + /// Succs - The successors of this node. + NodeGroup Succs; + +public: + + explicit ExplodedNode(const ProgramPoint& loc, const GRState* state) + : Location(loc), State(state) { + const_cast<GRState*>(State)->incrementReferenceCount(); + } + + ~ExplodedNode() { + const_cast<GRState*>(State)->decrementReferenceCount(); + } + + /// getLocation - Returns the edge associated with the given node. + ProgramPoint getLocation() const { return Location; } + + const LocationContext *getLocationContext() const { + return getLocation().getLocationContext(); + } + + const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } + + CFG &getCFG() const { return *getLocationContext()->getCFG(); } + + ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} + + LiveVariables &getLiveVariables() const { + return *getLocationContext()->getLiveVariables(); + } + + const GRState* 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) { + ID.Add(Loc); + ID.AddPointer(state); + } + + void Profile(llvm::FoldingSetNodeID& ID) const { + Profile(ID, getLocation(), getState()); + } + + /// 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); + + unsigned succ_size() const { return Succs.size(); } + unsigned pred_size() const { return Preds.size(); } + bool succ_empty() const { return Succs.empty(); } + bool pred_empty() const { return Preds.empty(); } + + bool isSink() const { return Succs.getFlag(); } + void markAsSink() { Succs.setFlag(); } + + ExplodedNode* getFirstPred() { + return pred_empty() ? NULL : *(pred_begin()); + } + + const ExplodedNode* getFirstPred() const { + return const_cast<ExplodedNode*>(this)->getFirstPred(); + } + + // Iterators over successor and predecessor vertices. + typedef ExplodedNode** succ_iterator; + typedef const ExplodedNode* const * const_succ_iterator; + typedef ExplodedNode** pred_iterator; + typedef const ExplodedNode* const * const_pred_iterator; + + pred_iterator pred_begin() { return Preds.begin(); } + pred_iterator pred_end() { return Preds.end(); } + + const_pred_iterator pred_begin() const { + return const_cast<ExplodedNode*>(this)->pred_begin(); + } + const_pred_iterator pred_end() const { + return const_cast<ExplodedNode*>(this)->pred_end(); + } + + succ_iterator succ_begin() { return Succs.begin(); } + succ_iterator succ_end() { return Succs.end(); } + + const_succ_iterator succ_begin() const { + return const_cast<ExplodedNode*>(this)->succ_begin(); + } + const_succ_iterator succ_end() const { + return const_cast<ExplodedNode*>(this)->succ_end(); + } + + // For debugging. + +public: + + class Auditor { + public: + virtual ~Auditor(); + virtual void AddEdge(ExplodedNode* Src, ExplodedNode* Dst) = 0; + }; + + static void SetAuditor(Auditor* A); + +private: + void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } + void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } +}; + +// FIXME: Is this class necessary? +class InterExplodedGraphMap { + llvm::DenseMap<const ExplodedNode*, ExplodedNode*> M; + friend class ExplodedGraph; + +public: + ExplodedNode* getMappedNode(const ExplodedNode* N) const; + + InterExplodedGraphMap() {} + virtual ~InterExplodedGraphMap() {} +}; + +class ExplodedGraph { +protected: + friend class CoreEngine; + + // Type definitions. + typedef llvm::SmallVector<ExplodedNode*,2> RootsTy; + typedef llvm::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 + /// SimulGraph. Moreover, these subgraphs can often merge when paths from + /// different roots reach the same state at the same program location. + RootsTy Roots; + + /// EndNodes - The nodes in the simulation graph which have been + /// specially marked as the endpoint of an abstract simulation path. + EndNodesTy EndNodes; + + /// Nodes - The nodes in the graph. + llvm::FoldingSet<ExplodedNode> Nodes; + + /// BVC - Allocator and context for allocating nodes and their predecessor + /// and successor groups. + BumpVectorContext BVC; + + /// NumNodes - The number of nodes in the graph. + unsigned NumNodes; + + /// A list of recently allocated nodes that can potentially be recycled. + void *recentlyAllocatedNodes; + + /// A list of nodes that can be reused. + void *freeNodes; + + /// A flag that indicates whether nodes should be recycled. + bool reclaimNodes; + +public: + /// getNode - Retrieve the node associated with a (Location,State) pair, + /// where the 'Location' is a ProgramPoint in the CFG. If no node for + /// 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, + bool* IsNew = 0); + + ExplodedGraph* MakeEmptyGraph() const { + return new ExplodedGraph(); + } + + /// addRoot - Add an untyped node to the set of roots. + 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) { + EndNodes.push_back(V); + return V; + } + + ExplodedGraph() + : NumNodes(0), recentlyAllocatedNodes(0), + freeNodes(0), reclaimNodes(false) {} + + ~ExplodedGraph(); + + unsigned num_roots() const { return Roots.size(); } + unsigned num_eops() const { return EndNodes.size(); } + + bool empty() const { return NumNodes == 0; } + unsigned size() const { return NumNodes; } + + // Iterators. + typedef ExplodedNode NodeTy; + typedef llvm::FoldingSet<ExplodedNode> AllNodesTy; + typedef NodeTy** roots_iterator; + typedef NodeTy* const * const_roots_iterator; + typedef NodeTy** eop_iterator; + typedef NodeTy* const * const_eop_iterator; + typedef AllNodesTy::iterator node_iterator; + typedef AllNodesTy::const_iterator const_node_iterator; + + node_iterator nodes_begin() { return Nodes.begin(); } + + node_iterator nodes_end() { return Nodes.end(); } + + const_node_iterator nodes_begin() const { return Nodes.begin(); } + + const_node_iterator nodes_end() const { return Nodes.end(); } + + roots_iterator roots_begin() { return Roots.begin(); } + + roots_iterator roots_end() { return Roots.end(); } + + const_roots_iterator roots_begin() const { return Roots.begin(); } + + const_roots_iterator roots_end() const { return Roots.end(); } + + eop_iterator eop_begin() { return EndNodes.begin(); } + + eop_iterator eop_end() { return EndNodes.end(); } + + const_eop_iterator eop_begin() const { return EndNodes.begin(); } + + const_eop_iterator eop_end() const { return EndNodes.end(); } + + llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } + BumpVectorContext &getNodeAllocator() { return BVC; } + + typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap; + + std::pair<ExplodedGraph*, InterExplodedGraphMap*> + Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd, + llvm::DenseMap<const void*, const void*> *InverseMap = 0) const; + + ExplodedGraph* TrimInternal(const ExplodedNode* const * NBeg, + const ExplodedNode* const * NEnd, + InterExplodedGraphMap *M, + llvm::DenseMap<const void*, const void*> *InverseMap) const; + + /// Enable tracking of recently allocated nodes for potential reclamation + /// when calling reclaimRecentlyAllocatedNodes(). + void enableNodeReclamation() { reclaimNodes = true; } + + /// Reclaim "uninteresting" nodes created since the last time this method + /// was called. + void reclaimRecentlyAllocatedNodes(); +}; + +class ExplodedNodeSet { + typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy; + ImplTy Impl; + +public: + ExplodedNodeSet(ExplodedNode* N) { + assert (N && !static_cast<ExplodedNode*>(N)->isSink()); + Impl.insert(N); + } + + ExplodedNodeSet() {} + + inline void Add(ExplodedNode* N) { + if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); + } + + ExplodedNodeSet& operator=(const ExplodedNodeSet &X) { + Impl = X.Impl; + return *this; + } + + typedef ImplTy::iterator iterator; + typedef ImplTy::const_iterator const_iterator; + + unsigned size() const { return Impl.size(); } + bool empty() const { return Impl.empty(); } + + void clear() { Impl.clear(); } + void insert(const ExplodedNodeSet &S) { + if (empty()) + Impl = S.Impl; + else + Impl.insert(S.begin(), S.end()); + } + + inline iterator begin() { return Impl.begin(); } + inline iterator end() { return Impl.end(); } + + inline const_iterator begin() const { return Impl.begin(); } + inline const_iterator end() const { return Impl.end(); } +}; + +} // end GR namespace + +} // end clang namespace + +// GraphTraits + +namespace llvm { + template<> struct GraphTraits<clang::ento::ExplodedNode*> { + typedef clang::ento::ExplodedNode NodeType; + typedef NodeType::succ_iterator ChildIteratorType; + typedef llvm::df_iterator<NodeType*> nodes_iterator; + + static inline NodeType* getEntryNode(NodeType* N) { + return N; + } + + static inline ChildIteratorType child_begin(NodeType* N) { + return N->succ_begin(); + } + + static inline ChildIteratorType child_end(NodeType* N) { + return N->succ_end(); + } + + static inline nodes_iterator nodes_begin(NodeType* N) { + return df_begin(N); + } + + static inline nodes_iterator nodes_end(NodeType* N) { + return df_end(N); + } + }; + + template<> struct GraphTraits<const clang::ento::ExplodedNode*> { + typedef const clang::ento::ExplodedNode NodeType; + typedef NodeType::const_succ_iterator ChildIteratorType; + typedef llvm::df_iterator<NodeType*> nodes_iterator; + + static inline NodeType* getEntryNode(NodeType* N) { + return N; + } + + static inline ChildIteratorType child_begin(NodeType* N) { + return N->succ_begin(); + } + + static inline ChildIteratorType child_end(NodeType* N) { + return N->succ_end(); + } + + static inline nodes_iterator nodes_begin(NodeType* N) { + return df_begin(N); + } + + static inline nodes_iterator nodes_end(NodeType* N) { + return df_end(N); + } + }; + +} // end llvm namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h new file mode 100644 index 0000000..767644a --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -0,0 +1,550 @@ +//===-- ExprEngine.h - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a meta-engine for path-sensitive dataflow analysis that +// is built on CoreEngine, but provides the boilerplate to execute transfer +// functions and build the ExplodedGraph at the expression level. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_EXPRENGINE +#define LLVM_CLANG_GR_EXPRENGINE + +#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/BugReporter/BugReporter.h" +#include "clang/AST/Type.h" +#include "clang/AST/ExprObjC.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/StmtObjC.h" + +namespace clang { + +class ObjCForCollectionStmt; + +namespace ento { + +class AnalysisManager; +class Checker; + +class ExprEngine : public SubEngine { + AnalysisManager &AMgr; + + CoreEngine Engine; + + /// G - the simulation graph. + ExplodedGraph& G; + + /// Builder - The current StmtNodeBuilder which is used when building the + /// nodes for a given statement. + StmtNodeBuilder* Builder; + + /// StateMgr - Object that manages the data for all created states. + GRStateManager StateMgr; + + /// SymMgr - Object that manages the symbol information. + SymbolManager& SymMgr; + + /// svalBuilder - SValBuilder object that creates SVals from expressions. + SValBuilder &svalBuilder; + + /// EntryNode - The immediate predecessor node. + ExplodedNode* EntryNode; + + /// CleanedState - The state for EntryNode "cleaned" of all dead + /// variables and symbols (as determined by a liveness analysis). + const GRState* CleanedState; + + /// currentStmt - The current block-level statement. + const Stmt* currentStmt; + + // Obj-C Class Identifiers. + IdentifierInfo* NSExceptionII; + + // Obj-C Selectors. + Selector* NSExceptionInstanceRaiseSelectors; + Selector RaiseSel; + + enum CallbackKind { + PreVisitStmtCallback, + PostVisitStmtCallback, + processAssumeCallback, + EvalRegionChangesCallback + }; + + typedef uint32_t CallbackTag; + + /// GetCallbackTag - Create a tag for a certain kind of callback. The 'Sub' + /// argument can be used to differentiate callbacks that depend on another + /// value from a small set of possibilities, such as statement classes. + static inline CallbackTag GetCallbackTag(CallbackKind K, uint32_t Sub = 0) { + assert(Sub == ((Sub << 8) >> 8) && "Tag sub-kind must fit into 24 bits"); + return K | (Sub << 8); + } + + typedef llvm::DenseMap<void *, unsigned> CheckerMap; + typedef std::vector<std::pair<void *, Checker*> > CheckersOrdered; + typedef llvm::DenseMap<CallbackTag, CheckersOrdered *> CheckersOrderedCache; + + /// A registration map from checker tag to the index into the + /// ordered checkers vector. + CheckerMap CheckerM; + + /// An ordered vector of checkers that are called when evaluating + /// various expressions and statements. + CheckersOrdered Checkers; + + /// A map used for caching the checkers that respond to the callback for + /// a particular callback tag. + CheckersOrderedCache COCache; + + /// 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(); + + void ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) { + Engine.ExecuteWorkList(L, Steps, 0); + } + + /// Execute the work list with an initial state. Nodes that reaches the exit + /// of the function are added into the Dst set, which represent the exit + /// state of the function call. + void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, + const GRState *InitState, + ExplodedNodeSet &Dst) { + Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst); + } + + /// getContext - Return the ASTContext associated with this analysis. + ASTContext& getContext() const { return AMgr.getASTContext(); } + + virtual AnalysisManager &getAnalysisManager() { return AMgr; } + + 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); + + /// ViewGraph - Visualize the ExplodedGraph created by executing the + /// simulation. + void ViewGraph(bool trim = false); + + void ViewGraph(ExplodedNode** Beg, ExplodedNode** End); + + /// getInitialState - Return the initial state used for the root vertex + /// in the ExplodedGraph. + const GRState* getInitialState(const LocationContext *InitLoc); + + ExplodedGraph& getGraph() { return G; } + const ExplodedGraph& getGraph() const { return G; } + + template <typename CHECKER> + void registerCheck(CHECKER *check) { + unsigned entry = Checkers.size(); + void *tag = CHECKER::getTag(); + Checkers.push_back(std::make_pair(tag, check)); + CheckerM[tag] = entry; + } + + Checker *lookupChecker(void *tag) const; + + template <typename CHECKER> + CHECKER *getChecker() const { + return static_cast<CHECKER*>(lookupChecker(CHECKER::getTag())); + } + + /// processCFGElement - Called by CoreEngine. Used to generate new successor + /// nodes by processing the 'effects' of a CFG element. + void processCFGElement(const CFGElement E, StmtNodeBuilder& builder); + + void ProcessStmt(const CFGStmt S, StmtNodeBuilder &builder); + + void ProcessInitializer(const CFGInitializer I, StmtNodeBuilder &builder); + + void ProcessImplicitDtor(const CFGImplicitDtor D, StmtNodeBuilder &builder); + + void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D, + StmtNodeBuilder &builder); + void ProcessBaseDtor(const CFGBaseDtor D, StmtNodeBuilder &builder); + void ProcessMemberDtor(const CFGMemberDtor D, StmtNodeBuilder &builder); + void ProcessTemporaryDtor(const CFGTemporaryDtor D, + StmtNodeBuilder &builder); + + /// Called by CoreEngine when processing the entrance of a CFGBlock. + virtual void processCFGBlockEntrance(ExplodedNodeSet &dstNodes, + GenericNodeBuilder<BlockEntrance> &nodeBuilder); + + /// 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, + BranchNodeBuilder& builder); + + /// processIndirectGoto - Called by CoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a computed goto jump. + void processIndirectGoto(IndirectGotoNodeBuilder& builder); + + /// ProcessSwitch - Called by CoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a switch statement. + void processSwitch(SwitchNodeBuilder& builder); + + /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path + /// nodes when the control reaches the end of a function. + void processEndOfFunction(EndOfFunctionNodeBuilder& builder); + + /// Generate the entry node of the callee. + void processCallEnter(CallEnterNodeBuilder &builder); + + /// Generate the first post callsite node. + void processCallExit(CallExitNodeBuilder &builder); + + /// Called by CoreEngine when the analysis worklist has terminated. + void processEndWorklist(bool hasWorkRemaining); + + /// evalAssume - Callback function invoked by the ConstraintManager when + /// making assumptions about state values. + const GRState *processAssume(const GRState *state, SVal cond,bool assumption); + + /// wantsRegionChangeUpdate - Called by GRStateManager to determine if a + /// region change should trigger a processRegionChanges update. + bool wantsRegionChangeUpdate(const GRState* state); + + /// processRegionChanges - Called by GRStateManager whenever a change is made + /// to the store. Used to update checkers that track region values. + const GRState* processRegionChanges(const GRState *state, + const MemRegion * const *Begin, + const MemRegion * const *End); + + virtual GRStateManager& getStateManager() { return StateMgr; } + + StoreManager& getStoreManager() { return StateMgr.getStoreManager(); } + + ConstraintManager& getConstraintManager() { + return StateMgr.getConstraintManager(); + } + + // FIXME: Remove when we migrate over to just using SValBuilder. + BasicValueFactory& getBasicVals() { + return StateMgr.getBasicVals(); + } + const BasicValueFactory& getBasicVals() const { + return StateMgr.getBasicVals(); + } + + // FIXME: Remove when we migrate over to just using ValueManager. + SymbolManager& getSymbolManager() { return SymMgr; } + const SymbolManager& getSymbolManager() const { return SymMgr; } + + // Functions for external checking of whether we have unfinished work + bool wasBlockAborted() const { return Engine.wasBlockAborted(); } + bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); } + bool hasWorkRemaining() const { + return wasBlockAborted() || Engine.getWorkList()->hasWork(); + } + + 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, + ProgramPoint::Kind K = ProgramPoint::PostStmtKind, + const void *tag = 0); + + /// CheckerVisit - Dispatcher for performing checker-specific logic + /// at specific statements. + void CheckerVisit(const Stmt *S, ExplodedNodeSet &Dst, ExplodedNodeSet &Src, + CallbackKind Kind); + + void CheckerVisitObjCMessage(const ObjCMessage &msg, ExplodedNodeSet &Dst, + ExplodedNodeSet &Src, bool isPrevisit); + + bool CheckerEvalCall(const CallExpr *CE, + ExplodedNodeSet &Dst, + ExplodedNode *Pred); + + void CheckerEvalNilReceiver(const ObjCMessage &msg, + ExplodedNodeSet &Dst, + const GRState *state, + ExplodedNode *Pred); + + void CheckerVisitBind(const Stmt *StoreE, ExplodedNodeSet &Dst, + ExplodedNodeSet &Src, SVal location, SVal val, + bool isPrevisit); + + /// Visit - Transfer function logic for all statements. Dispatches to + /// other functions that handle specific kinds of statements. + void Visit(const Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst); + + /// VisitArraySubscriptExpr - Transfer function for array accesses. + 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 VisitAsmStmtHelperOutputs(const AsmStmt* A, + AsmStmt::const_outputs_iterator I, + AsmStmt::const_outputs_iterator E, + ExplodedNode* Pred, ExplodedNodeSet& Dst); + + void VisitAsmStmtHelperInputs(const AsmStmt* A, + AsmStmt::const_inputs_iterator I, + AsmStmt::const_inputs_iterator E, + ExplodedNode* Pred, ExplodedNodeSet& Dst); + + /// VisitBlockExpr - Transfer function logic for BlockExprs. + void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, + ExplodedNodeSet &Dst); + + /// VisitBinaryOperator - Transfer function logic for binary operators. + void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode* Pred, + ExplodedNodeSet& Dst); + + + /// VisitCall - Transfer function for function calls. + void VisitCall(const CallExpr* CE, ExplodedNode* Pred, + CallExpr::const_arg_iterator AI, + CallExpr::const_arg_iterator AE, + 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); + + /// Transfer function logic for DeclRefExprs and BlockDeclRefExprs. + 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); + + /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose + void VisitGuardedExpr(const Expr* Ex, const Expr* L, const Expr* R, + ExplodedNode* Pred, ExplodedNodeSet& Dst); + + /// VisitCondInit - Transfer function for handling the initialization + /// of a condition variable in an IfStmt, SwitchStmt, etc. + void VisitCondInit(const VarDecl *VD, const Stmt *S, 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); + + /// VisitMemberExpr - Transfer function for member expressions. + 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); + + /// VisitObjCForCollectionStmt - Transfer function logic for + /// ObjCForCollectionStmt. + 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); + + /// VisitReturnStmt - Transfer function logic for return statements. + void VisitReturnStmt(const ReturnStmt* R, ExplodedNode* Pred, + ExplodedNodeSet& Dst); + + /// VisitOffsetOfExpr - Transfer function for offsetof. + void VisitOffsetOfExpr(const OffsetOfExpr* Ex, ExplodedNode* Pred, + ExplodedNodeSet& Dst); + + /// VisitSizeOfAlignOfExpr - Transfer function for sizeof. + void VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr* Ex, ExplodedNode* Pred, + ExplodedNodeSet& Dst); + + /// VisitUnaryOperator - Transfer function logic for unary operators. + void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode* Pred, + ExplodedNodeSet& Dst); + + void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred, + ExplodedNodeSet & Dst); + + void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *expr, + ExplodedNode *Pred, ExplodedNodeSet &Dst) { + VisitCXXConstructExpr(expr, 0, Pred, Dst); + } + + void VisitCXXConstructExpr(const CXXConstructExpr *E, const MemRegion *Dest, + ExplodedNode *Pred, ExplodedNodeSet &Dst); + + void VisitCXXDestructor(const CXXDestructorDecl *DD, + const MemRegion *Dest, const Stmt *S, + ExplodedNode *Pred, ExplodedNodeSet &Dst); + + void VisitCXXMemberCallExpr(const CXXMemberCallExpr *MCE, ExplodedNode *Pred, + ExplodedNodeSet &Dst); + + void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *C, + ExplodedNode *Pred, ExplodedNodeSet &Dst); + + void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, + ExplodedNodeSet &Dst); + + void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred, + ExplodedNodeSet &Dst); + + void VisitAggExpr(const Expr *E, const MemRegion *Dest, ExplodedNode *Pred, + ExplodedNodeSet &Dst); + + /// Create a C++ temporary object for an rvalue. + void CreateCXXTemporaryObject(const Expr *Ex, ExplodedNode *Pred, + ExplodedNodeSet &Dst); + + /// Synthesize CXXThisRegion. + const CXXThisRegion *getCXXThisRegion(const CXXRecordDecl *RD, + const StackFrameContext *SFC); + + const CXXThisRegion *getCXXThisRegion(const CXXMethodDecl *decl, + const StackFrameContext *frameCtx); + + /// Evaluate arguments with a work list algorithm. + void evalArguments(ConstExprIterator AI, ConstExprIterator AE, + const FunctionProtoType *FnType, + ExplodedNode *Pred, ExplodedNodeSet &Dst, + bool FstArgAsLValue = false); + + /// Evaluate method call itself. Used for CXXMethodCallExpr and + /// CXXOperatorCallExpr. + void evalMethodCall(const CallExpr *MCE, const CXXMethodDecl *MD, + const Expr *ThisExpr, ExplodedNode *Pred, + ExplodedNodeSet &Src, ExplodedNodeSet &Dst); + + /// evalEagerlyAssume - Given the nodes in 'Src', eagerly assume symbolic + /// expressions of the form 'x != 0' and generate new nodes (stored in Dst) + /// with those assumptions. + void evalEagerlyAssume(ExplodedNodeSet& Dst, ExplodedNodeSet& Src, + const Expr *Ex); + + SVal evalMinus(SVal X) { + return X.isValid() ? svalBuilder.evalMinus(cast<NonLoc>(X)) : X; + } + + SVal evalComplement(SVal X) { + return X.isValid() ? svalBuilder.evalComplement(cast<NonLoc>(X)) : X; + } + +public: + + SVal evalBinOp(const GRState *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, + 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 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); + } + + const GRState* MarkBranch(const GRState* St, const Stmt* Terminator, + bool branchTaken); + + /// evalBind - Handle the semantics of binding a value to a specific location. + /// This method is used by evalStore, VisitDeclStmt, and others. + void evalBind(ExplodedNodeSet& Dst, const Stmt* StoreE, ExplodedNode* Pred, + const GRState* St, SVal location, SVal Val, + bool atDeclInit = false); + +public: + // FIXME: 'tag' should be removed, and a LocationContext should be used + // instead. + // FIXME: Comment on the meaning of the arguments, when 'St' may not + // 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, + 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); +private: + void evalLoadCommon(ExplodedNodeSet& Dst, const Expr* Ex, ExplodedNode* Pred, + const GRState* St, SVal location, const void *tag, + QualType LoadTy); + + // FIXME: 'tag' should be removed, and a LocationContext should be used + // instead. + void evalLocation(ExplodedNodeSet &Dst, const Stmt *S, ExplodedNode* Pred, + const GRState* St, SVal location, + const void *tag, bool isLoad); + + bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred); +}; + +} // end ento namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h new file mode 100644 index 0000000..18e39d9 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h @@ -0,0 +1,80 @@ +//===-- ExprEngineBuilders.h - "Builder" classes for ExprEngine ---*- 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 smart builder "references" which are used to marshal +// builders between ExprEngine objects and their related components. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_EXPRENGINE_BUILDERS +#define LLVM_CLANG_GR_EXPRENGINE_BUILDERS +#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" +#include "clang/Analysis/Support/SaveAndRestore.h" + +namespace clang { + +namespace ento { + +class StmtNodeBuilderRef { + ExplodedNodeSet &Dst; + StmtNodeBuilder &B; + ExprEngine& Eng; + ExplodedNode* Pred; + const GRState* state; + const Stmt* stmt; + const unsigned OldSize; + const bool AutoCreateNode; + SaveAndRestore<bool> OldSink; + SaveOr OldHasGen; + +private: + friend class ExprEngine; + + StmtNodeBuilderRef(); // do not implement + void operator=(const StmtNodeBuilderRef&); // do not implement + + StmtNodeBuilderRef(ExplodedNodeSet &dst, + StmtNodeBuilder &builder, + ExprEngine& eng, + ExplodedNode* pred, + const GRState *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) {} + +public: + + ~StmtNodeBuilderRef() { + // Handle the case where no nodes where generated. Auto-generate that + // contains the updated state if we aren't generating sinks. + if (!B.BuildSinks && Dst.size() == OldSize && !B.hasGeneratedNode) { + if (AutoCreateNode) + B.MakeNode(Dst, const_cast<Stmt*>(stmt), Pred, state); + else + Dst.Add(Pred); + } + } + + const GRState *getState() { return state; } + + GRStateManager& getStateManager() { + return Eng.getStateManager(); + } + + ExplodedNode* MakeNode(const GRState* state) { + return B.MakeNode(Dst, const_cast<Stmt*>(stmt), Pred, state); + } +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/GRState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/GRState.h new file mode 100644 index 0000000..37694da --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/GRState.h @@ -0,0 +1,793 @@ +//== GRState.h - Path-sensitive "State" for tracking values -----*- 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 SymbolRef, ExprBindKey, and GRState*. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_VALUESTATE_H +#define LLVM_CLANG_GR_VALUESTATE_H + +#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" +#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 { +class ASTContext; + +namespace ento { + +class GRStateManager; +class Checker; + +typedef ConstraintManager* (*ConstraintManagerCreator)(GRStateManager&, + SubEngine&); +typedef StoreManager* (*StoreManagerCreator)(GRStateManager&); + +//===----------------------------------------------------------------------===// +// GRStateTrait - Traits used by the Generic Data Map of a GRState. +//===----------------------------------------------------------------------===// + +template <typename T> struct GRStatePartialTrait; + +template <typename T> struct GRStateTrait { + 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) { + return P ? (data_type) *P : (data_type) 0; + } +}; + +class GRStateManager; + +/// GRState - This class encapsulates: +/// +/// 1. A mapping from expressions to values (Environment) +/// 2. A mapping from locations to values (Store) +/// 3. Constraints on symbolic values (GenericDataMap) +/// +/// Together these represent the "abstract state" of a program. +/// +/// GRState 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 { +public: + typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; + typedef llvm::ImmutableMap<void*, void*> GenericDataMap; + +private: + void operator=(const GRState& R) const; // Do not implement. + + friend class GRStateManager; + friend class ExplodedGraph; + friend class ExplodedNode; + + GRStateManager *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 + /// state with the exception of using the specified Store. + const GRState *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, + 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); + + ~GRState(); + + /// Return the GRStateManager associated with this state. + GRStateManager &getStateManager() const { return *stateMgr; } + + /// Return true if this state is referenced by a persistent ExplodedNode. + bool referencedByExplodedNode() const { return refCount > 0; } + + /// getEnvironment - Return the environment associated with this state. + /// The environment is the mapping from expressions to values. + const Environment& getEnvironment() const { return Env; } + + /// Return the store associated with this state. The store + /// is a mapping from locations to values. + Store getStore() const { return store; } + + + /// getGDM - Return the generic data map associated with this state. + GenericDataMap getGDM() const { return GDM; } + + 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 + /// have the same Environment, Store, and GenericDataMap. + static void Profile(llvm::FoldingSetNodeID& ID, const GRState* V) { + V->Env.Profile(ID); + ID.AddPointer(V->store); + V->GDM.Profile(ID); + } + + /// Profile - Used to profile the contents of this object for inclusion + /// in a FoldingSet. + void Profile(llvm::FoldingSetNodeID& ID) const { + Profile(ID, this); + } + + BasicValueFactory &getBasicVals() const; + SymbolManager &getSymbolManager() const; + + //==---------------------------------------------------------------------==// + // Constraints on values. + //==---------------------------------------------------------------------==// + // + // Each GRState records constraints on symbolic values. These constraints + // are managed using the ConstraintManager associated with a GRStateManager. + // 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. + // + // 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. + // + // (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. + // If no new state is feasible, NULL is returned. + // + + const GRState *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*> + assume(DefinedOrUnknownSVal cond) const; + + const GRState *assumeInBound(DefinedOrUnknownSVal idx, + DefinedOrUnknownSVal upperBound, + bool assumption) const; + + //==---------------------------------------------------------------------==// + // Utility methods for getting regions. + //==---------------------------------------------------------------------==// + + const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; + + //==---------------------------------------------------------------------==// + // Binding and retrieving values to/from the environment and symbolic store. + //==---------------------------------------------------------------------==// + + /// 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 LocationContext *LC, + SVal V) const; + + /// Create a new state by binding the value 'V' to the statement 'S' in the + /// state's environment. + const GRState *BindExpr(const Stmt *S, SVal V, bool Invalidate = true) const; + + /// Create a new state by binding the value 'V' and location 'locaton' to the + /// statement 'S' in the state's environment. + const GRState *bindExprAndLocation(const Stmt *S, SVal location, SVal V) + const; + + const GRState *bindDecl(const VarRegion *VR, SVal V) const; + + const GRState *bindDeclWithNoInit(const VarRegion *VR) const; + + const GRState *bindLoc(Loc location, SVal V) const; + + const GRState *bindLoc(SVal location, SVal V) const; + + const GRState *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); + } + + /// invalidateRegions - Returns the state with bindings for the given regions + /// cleared from the store. The regions are provided as a continuous array + /// from Begin to End. Optionally invalidates global regions as well. + const GRState *invalidateRegions(const MemRegion * const *Begin, + const MemRegion * const *End, + const Expr *E, unsigned BlockCount, + StoreManager::InvalidatedSymbols *IS, + bool invalidateGlobals) const; + + /// enterStackFrame - Returns the state for entry to the given stack frame, + /// preserving the current state. + const GRState *enterStackFrame(const StackFrameContext *frame) const; + + /// Get the lvalue for a variable reference. + Loc getLValue(const VarDecl *D, const LocationContext *LC) const; + + /// Get the lvalue for a StringLiteral. + Loc getLValue(const StringLiteral *literal) const; + + Loc getLValue(const CompoundLiteralExpr *literal, + const LocationContext *LC) const; + + /// Get the lvalue for an ivar reference. + SVal getLValue(const ObjCIvarDecl *decl, SVal base) const; + + /// Get the lvalue for a field reference. + SVal getLValue(const FieldDecl *decl, SVal Base) const; + + /// Get the lvalue for an array index. + SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; + + 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) const; + + SVal getSValAsScalarOrLoc(const Stmt *Ex) const; + + SVal getSVal(Loc LV, QualType T = QualType()) const; + + /// Returns the "raw" SVal bound to LV before any value simplfication. + SVal getRawSVal(Loc LV, QualType T= QualType()) const; + + SVal getSVal(const MemRegion* R) const; + + SVal getSValAsScalarOrLoc(const MemRegion *R) const; + + const llvm::APSInt *getSymVal(SymbolRef sym); + + bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; + + bool scanReachableSymbols(const SVal *I, const SVal *E, + SymbolVisitor &visitor) const; + + bool scanReachableSymbols(const MemRegion * const *I, + const MemRegion * const *E, + SymbolVisitor &visitor) const; + + template <typename CB> CB scanReachableSymbols(SVal val) const; + template <typename CB> CB scanReachableSymbols(const SVal *beg, + const SVal *end) const; + + template <typename CB> CB + scanReachableSymbols(const MemRegion * const *beg, + const MemRegion * const *end) const; + + //==---------------------------------------------------------------------==// + // Accessing the Generic Data Map (GDM). + //==---------------------------------------------------------------------==// + + void* const* FindGDM(void* K) const; + + template<typename T> + const GRState *add(typename GRStateTrait<T>::key_type K) const; + + template <typename T> + typename GRStateTrait<T>::data_type + get() const { + return GRStateTrait<T>::MakeData(FindGDM(GRStateTrait<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); + } + + template <typename T> + typename GRStateTrait<T>::context_type get_context() const; + + + template<typename T> + const GRState *remove(typename GRStateTrait<T>::key_type K) const; + + template<typename T> + const GRState *remove(typename GRStateTrait<T>::key_type K, + typename GRStateTrait<T>::context_type C) const; + template <typename T> + const GRState *remove() const; + + template<typename T> + const GRState *set(typename GRStateTrait<T>::data_type D) const; + + template<typename T> + const GRState *set(typename GRStateTrait<T>::key_type K, + typename GRStateTrait<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; + + 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); + } + + // 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", + const char *sep = "") const; + + void printStdErr(CFG &C) const; + + void printDOT(llvm::raw_ostream& Out, CFG &C) const; + +private: + /// Increments the number of times this state is referenced by ExplodeNodes. + void incrementReferenceCount() { ++refCount; } + + /// Decrement the number of times this state is referenced by ExplodeNodes. + void decrementReferenceCount() { + assert(refCount > 0); + --refCount; + } +}; + +class GRStateSet { + typedef llvm::SmallPtrSet<const GRState*,5> ImplTy; + ImplTy Impl; +public: + GRStateSet() {} + + inline void Add(const GRState* St) { + Impl.insert(St); + } + + typedef ImplTy::const_iterator iterator; + + inline unsigned size() const { return Impl.size(); } + inline bool empty() const { return Impl.empty(); } + + inline iterator begin() const { return Impl.begin(); } + inline iterator end() const { return Impl.end(); } + + class AutoPopulate { + GRStateSet& S; + unsigned StartSize; + const GRState* St; + public: + AutoPopulate(GRStateSet& s, const GRState* st) + : S(s), StartSize(S.size()), St(st) {} + + ~AutoPopulate() { + if (StartSize == S.size()) + S.Add(St); + } + }; +}; + +//===----------------------------------------------------------------------===// +// GRStateManager - Factory object for GRStates. +//===----------------------------------------------------------------------===// + +class GRStateManager { + friend class GRState; + friend class ExprEngine; // FIXME: Remove. +private: + /// Eng - The SubEngine that owns this state manager. + SubEngine *Eng; /* Can be null. */ + + EnvironmentManager EnvMgr; + llvm::OwningPtr<StoreManager> StoreMgr; + llvm::OwningPtr<ConstraintManager> ConstraintMgr; + + GRState::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; + + /// Object that manages the data for all created SVals. + llvm::OwningPtr<SValBuilder> svalBuilder; + + /// A BumpPtrAllocator to allocate states. + llvm::BumpPtrAllocator &Alloc; + + /// A vector of recently allocated GRStates that can potentially be + /// reused. + std::vector<GRState *> recentlyAllocatedStates; + + /// A vector of GRStates that we can reuse. + std::vector<GRState *> freeStates; + +public: + GRStateManager(ASTContext& Ctx, + StoreManagerCreator CreateStoreManager, + ConstraintManagerCreator CreateConstraintManager, + llvm::BumpPtrAllocator& alloc, + SubEngine &subeng) + : Eng(&subeng), + EnvMgr(alloc), + GDMFactory(alloc), + svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), + Alloc(alloc) { + StoreMgr.reset((*CreateStoreManager)(*this)); + ConstraintMgr.reset((*CreateConstraintManager)(*this, subeng)); + } + + GRStateManager(ASTContext& Ctx, + StoreManagerCreator CreateStoreManager, + ConstraintManager* ConstraintManagerPtr, + llvm::BumpPtrAllocator& alloc) + : Eng(0), + EnvMgr(alloc), + GDMFactory(alloc), + svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), + Alloc(alloc) { + StoreMgr.reset((*CreateStoreManager)(*this)); + ConstraintMgr.reset(ConstraintManagerPtr); + } + + ~GRStateManager(); + + const GRState *getInitialState(const LocationContext *InitLoc); + + ASTContext &getContext() { return svalBuilder->getContext(); } + const ASTContext &getContext() const { return svalBuilder->getContext(); } + + BasicValueFactory &getBasicVals() { + return svalBuilder->getBasicValueFactory(); + } + const BasicValueFactory& getBasicVals() const { + return svalBuilder->getBasicValueFactory(); + } + + SValBuilder &getSValBuilder() { + return *svalBuilder; + } + + SymbolManager &getSymbolManager() { + return svalBuilder->getSymbolManager(); + } + const SymbolManager &getSymbolManager() const { + return svalBuilder->getSymbolManager(); + } + + llvm::BumpPtrAllocator& getAllocator() { return Alloc; } + + MemRegionManager& getRegionManager() { + return svalBuilder->getRegionManager(); + } + const MemRegionManager& getRegionManager() const { + return svalBuilder->getRegionManager(); + } + + StoreManager& getStoreManager() { return *StoreMgr; } + ConstraintManager& getConstraintManager() { return *ConstraintMgr; } + SubEngine* getOwningEngine() { return Eng; } + + const GRState* removeDeadBindings(const GRState* St, + const StackFrameContext *LCtx, + SymbolReaper& SymReaper); + + /// Marshal a new state for the callee in another translation unit. + /// 'state' is owned by the caller's engine. + const GRState *MarshalState(const GRState *state, const StackFrameContext *L); + +public: + + SVal ArrayToPointer(Loc Array) { + return StoreMgr->ArrayToPointer(Array); + } + + // Methods that manipulate the GDM. + const GRState* addGDM(const GRState* St, void* Key, void* Data); + const GRState *removeGDM(const GRState *state, void *Key); + + // Methods that query & manipulate the Store. + + void iterBindings(const GRState* state, StoreManager::BindingsHandler& F) { + StoreMgr->iterBindings(state->getStore(), F); + } + + const GRState* getPersistentState(GRState& Impl); + + /// Periodically called by ExprEngine to recycle GRStates that were + /// created but never used for creating an ExplodedNode. + void recycleUnusedStates(); + + //==---------------------------------------------------------------------==// + // 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 + // 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. + // Clients are responsible for ensuring that data values referred to by a + // the data pointer are immutable (and thus are essentially purely functional + // data). + // + // The templated methods below use the GRStateTrait<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)); + } + + 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) { + + return addGDM(st, GRStateTrait<T>::GDMIndex(), + GRStateTrait<T>::MakeVoidPtr(GRStateTrait<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))); + } + + template <typename T> + const GRState* remove(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>::Remove(st->get<T>(), K, C))); + } + + template <typename T> + const GRState *remove(const GRState *st) { + return removeGDM(st, GRStateTrait<T>::GDMIndex()); + } + + 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); + + return GRStateTrait<T>::MakeContext(p); + } + + const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) { + return ConstraintMgr->getSymVal(St, sym); + } + + void EndPath(const GRState* St) { + ConstraintMgr->EndPath(St); + } +}; + + +//===----------------------------------------------------------------------===// +// Out-of-line method definitions for GRState. +//===----------------------------------------------------------------------===// + +inline const llvm::APSInt *GRState::getSymVal(SymbolRef sym) { + return getStateManager().getSymVal(this, sym); +} + +inline const VarRegion* GRState::getRegion(const VarDecl *D, + const LocationContext *LC) const { + return getStateManager().getRegionManager().getVarRegion(D, LC); +} + +inline const GRState *GRState::assume(DefinedOrUnknownSVal Cond, + bool Assumption) const { + if (Cond.isUnknown()) + return this; + + return getStateManager().ConstraintMgr->assume(this, cast<DefinedSVal>(Cond), + Assumption); +} + +inline std::pair<const GRState*, const GRState*> +GRState::assume(DefinedOrUnknownSVal Cond) const { + if (Cond.isUnknown()) + return std::make_pair(this, this); + + return getStateManager().ConstraintMgr->assumeDual(this, + cast<DefinedSVal>(Cond)); +} + +inline const GRState *GRState::bindLoc(SVal LV, SVal V) const { + return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V); +} + +inline Loc GRState::getLValue(const VarDecl* VD, + const LocationContext *LC) const { + return getStateManager().StoreMgr->getLValueVar(VD, LC); +} + +inline Loc GRState::getLValue(const StringLiteral *literal) const { + return getStateManager().StoreMgr->getLValueString(literal); +} + +inline Loc GRState::getLValue(const CompoundLiteralExpr *literal, + const LocationContext *LC) const { + return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); +} + +inline SVal GRState::getLValue(const ObjCIvarDecl *D, SVal Base) const { + return getStateManager().StoreMgr->getLValueIvar(D, Base); +} + +inline SVal GRState::getLValue(const FieldDecl* D, SVal Base) const { + return getStateManager().StoreMgr->getLValueField(D, Base); +} + +inline SVal GRState::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 { + return getStateManager().getSymVal(this, sym); +} + +inline SVal GRState::getSVal(const Stmt* Ex) const { + return Env.getSVal(Ex, *getStateManager().svalBuilder); +} + +inline SVal GRState::getSValAsScalarOrLoc(const Stmt *S) const { + if (const Expr *Ex = dyn_cast<Expr>(S)) { + QualType T = Ex->getType(); + if (Loc::isLocType(T) || T->isIntegerType()) + return getSVal(S); + } + + return UnknownVal(); +} + +inline SVal GRState::getRawSVal(Loc LV, QualType T) const { + return getStateManager().StoreMgr->Retrieve(getStore(), LV, T); +} + +inline SVal GRState::getSVal(const MemRegion* R) const { + return getStateManager().StoreMgr->Retrieve(getStore(), loc::MemRegionVal(R)); +} + +inline BasicValueFactory &GRState::getBasicVals() const { + return getStateManager().getBasicVals(); +} + +inline SymbolManager &GRState::getSymbolManager() const { + return getStateManager().getSymbolManager(); +} + +template<typename T> +const GRState *GRState::add(typename GRStateTrait<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 { + return getStateManager().get_context<T>(); +} + +template<typename T> +const GRState *GRState::remove(typename GRStateTrait<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 { + return getStateManager().remove<T>(this, K, C); +} + +template <typename T> +const GRState *GRState::remove() const { + return getStateManager().remove<T>(this); +} + +template<typename T> +const GRState *GRState::set(typename GRStateTrait<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 { + 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 { + return getStateManager().set<T>(this, K, E, C); +} + +template <typename CB> +CB GRState::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 cb(this); + scanReachableSymbols(beg, end, cb); + return cb; +} + +template <typename CB> +CB GRState::scanReachableSymbols(const MemRegion * const *beg, + const MemRegion * const *end) const { + CB cb(this); + scanReachableSymbols(beg, end, cb); + return cb; +} + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h b/include/clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h new file mode 100644 index 0000000..411441f --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h @@ -0,0 +1,165 @@ +//==- GRStateTrait.h - Partial implementations of GRStateTrait -----*- 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 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. +// +//===----------------------------------------------------------------------===// + + +#ifndef LLVM_CLANG_GR_GRSTATETRAIT_H +#define LLVM_CLANG_GR_GRSTATETRAIT_H + +namespace llvm { + class BumpPtrAllocator; + template <typename K, typename D, typename I> class ImmutableMap; + template <typename K, typename I> class ImmutableSet; + template <typename T> class ImmutableList; + template <typename T> class ImmutableListImpl; +} + +namespace clang { + +namespace ento { + template <typename T> struct GRStatePartialTrait; + + // Partial-specialization for ImmutableMap. + + template <typename Key, typename Data, typename Info> + struct GRStatePartialTrait< 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) { + return p ? data_type((typename data_type::TreeTy*) *p) : data_type(0); + } + static inline void* MakeVoidPtr(data_type B) { + return B.getRoot(); + } + static lookup_type Lookup(data_type B, key_type K) { + return B.lookup(K); + } + static data_type Set(data_type B, key_type K, value_type E,context_type F){ + return F.add(B, K, E); + } + + static data_type Remove(data_type B, key_type K, context_type F) { + return F.remove(B, K); + } + + static inline context_type MakeContext(void* p) { + return *((typename data_type::Factory*) p); + } + + static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + return new typename data_type::Factory(Alloc); + } + + static void DeleteContext(void* Ctx) { + delete (typename data_type::Factory*) Ctx; + } + }; + + + // Partial-specialization for ImmutableSet. + + template <typename Key, typename Info> + struct GRStatePartialTrait< 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) { + return p ? data_type((typename data_type::TreeTy*) *p) : data_type(0); + } + + static inline void* MakeVoidPtr(data_type B) { + return B.getRoot(); + } + + static data_type Add(data_type B, key_type K, context_type F) { + return F.add(B, K); + } + + static data_type Remove(data_type B, key_type K, context_type F) { + return F.remove(B, K); + } + + static bool Contains(data_type B, key_type K) { + return B.contains(K); + } + + static inline context_type MakeContext(void* p) { + return *((typename data_type::Factory*) p); + } + + static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + return new typename data_type::Factory(Alloc); + } + + static void DeleteContext(void* Ctx) { + delete (typename data_type::Factory*) Ctx; + } + }; + + // Partial-specialization for ImmutableList. + + template <typename T> + struct GRStatePartialTrait< llvm::ImmutableList<T> > { + typedef llvm::ImmutableList<T> data_type; + typedef T key_type; + typedef typename data_type::Factory& context_type; + + static data_type Add(data_type L, key_type K, context_type F) { + return F.add(K, L); + } + + 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) { + return (void*) D.getInternalPointer(); + } + + static inline context_type MakeContext(void* p) { + return *((typename data_type::Factory*) p); + } + + static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + return new typename data_type::Factory(Alloc); + } + + static void DeleteContext(void* Ctx) { + delete (typename data_type::Factory*) Ctx; + } + }; + + // Partial specialization for bool. + template <> struct GRStatePartialTrait<bool> { + typedef bool data_type; + + static inline data_type MakeData(void* const* p) { + return (bool) (uintptr_t) p; + } + static inline void *MakeVoidPtr(data_type d) { + return (void*) (uintptr_t) d; + } + }; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h new file mode 100644 index 0000000..8d19b51 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h @@ -0,0 +1,1092 @@ +//== MemRegion.h - Abstract memory regions for static analysis --*- 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 MemRegion and its subclasses. MemRegion defines a +// partially-typed abstraction of memory useful for path-sensitive dataflow +// analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_MEMREGION_H +#define LLVM_CLANG_GR_MEMREGION_H + +#include "clang/AST/CharUnits.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclObjC.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 { + +class LocationContext; +class StackFrameContext; + +namespace ento { + +class MemRegionManager; +class MemSpaceRegion; +class SValBuilder; +class VarRegion; +class CodeTextRegion; + +/// Represent a region's offset within the top level base region. +class RegionOffset { + /// The base region. + const MemRegion *R; + + /// The bit offset within the base region. It shouldn't be negative. + int64_t Offset; + +public: + RegionOffset(const MemRegion *r) : R(r), Offset(0) {} + RegionOffset(const MemRegion *r, int64_t off) : R(r), Offset(off) {} + + const MemRegion *getRegion() const { return R; } + int64_t getOffset() const { return Offset; } +}; + +//===----------------------------------------------------------------------===// +// Base region classes. +//===----------------------------------------------------------------------===// + +/// MemRegion - The root abstract class for all memory regions. +class MemRegion : public llvm::FoldingSetNode { + friend class MemRegionManager; +public: + enum Kind { + // Memory spaces. + GenericMemSpaceRegionKind, + StackLocalsSpaceRegionKind, + StackArgumentsSpaceRegionKind, + HeapSpaceRegionKind, + UnknownSpaceRegionKind, + NonStaticGlobalSpaceRegionKind, + StaticGlobalSpaceRegionKind, + BEG_GLOBAL_MEMSPACES = NonStaticGlobalSpaceRegionKind, + END_GLOBAL_MEMSPACES = StaticGlobalSpaceRegionKind, + BEG_MEMSPACES = GenericMemSpaceRegionKind, + END_MEMSPACES = StaticGlobalSpaceRegionKind, + // Untyped regions. + SymbolicRegionKind, + AllocaRegionKind, + // Typed regions. + BEG_TYPED_REGIONS, + FunctionTextRegionKind = BEG_TYPED_REGIONS, + BlockTextRegionKind, + BlockDataRegionKind, + CompoundLiteralRegionKind, + CXXThisRegionKind, + StringRegionKind, + ElementRegionKind, + // Decl Regions. + BEG_DECL_REGIONS, + VarRegionKind = BEG_DECL_REGIONS, + FieldRegionKind, + ObjCIvarRegionKind, + END_DECL_REGIONS = ObjCIvarRegionKind, + CXXTempObjectRegionKind, + CXXBaseObjectRegionKind, + END_TYPED_REGIONS = CXXBaseObjectRegionKind + }; + +private: + const Kind kind; + +protected: + MemRegion(Kind k) : kind(k) {} + virtual ~MemRegion(); + +public: + ASTContext &getContext() const; + + virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0; + + virtual MemRegionManager* getMemRegionManager() const = 0; + + std::string getString() const; + + const MemSpaceRegion *getMemorySpace() const; + + const MemRegion *getBaseRegion() const; + + const MemRegion *StripCasts() const; + + bool hasGlobalsOrParametersStorage() const; + + bool hasStackStorage() const; + + bool hasStackNonParametersStorage() const; + + bool hasStackParametersStorage() const; + + /// Compute the offset within the top level memory object. + RegionOffset getAsOffset() const; + + virtual void dumpToStream(llvm::raw_ostream& os) const; + + void dump() const; + + Kind getKind() const { return kind; } + + template<typename RegionTy> const RegionTy* getAs() const; + + virtual bool isBoundable() const { return false; } + + static bool classof(const MemRegion*) { return true; } +}; + +/// MemSpaceRegion - A memory region that represents and "memory space"; +/// for example, the set of global variables, the stack frame, etc. +class MemSpaceRegion : public MemRegion { +protected: + friend class MemRegionManager; + + MemRegionManager *Mgr; + + MemSpaceRegion(MemRegionManager *mgr, Kind k = GenericMemSpaceRegionKind) + : MemRegion(k), Mgr(mgr) { + assert(classof(this)); + } + + MemRegionManager* getMemRegionManager() const { return Mgr; } + +public: + bool isBoundable() const { return false; } + + void Profile(llvm::FoldingSetNodeID &ID) const; + + static bool classof(const MemRegion *R) { + Kind k = R->getKind(); + return k >= BEG_MEMSPACES && k <= END_MEMSPACES; + } +}; + +class GlobalsSpaceRegion : public MemSpaceRegion { +protected: + GlobalsSpaceRegion(MemRegionManager *mgr, Kind k) + : MemSpaceRegion(mgr, k) {} +public: + static bool classof(const MemRegion *R) { + Kind k = R->getKind(); + return k >= BEG_GLOBAL_MEMSPACES && k <= END_GLOBAL_MEMSPACES; + } +}; + +class StaticGlobalSpaceRegion : public GlobalsSpaceRegion { + friend class MemRegionManager; + + const CodeTextRegion *CR; + + StaticGlobalSpaceRegion(MemRegionManager *mgr, const CodeTextRegion *cr) + : GlobalsSpaceRegion(mgr, StaticGlobalSpaceRegionKind), CR(cr) {} + +public: + void Profile(llvm::FoldingSetNodeID &ID) const; + + void dumpToStream(llvm::raw_ostream& os) const; + + const CodeTextRegion *getCodeRegion() const { return CR; } + + static bool classof(const MemRegion *R) { + return R->getKind() == StaticGlobalSpaceRegionKind; + } +}; + +class NonStaticGlobalSpaceRegion : public GlobalsSpaceRegion { + friend class MemRegionManager; + + NonStaticGlobalSpaceRegion(MemRegionManager *mgr) + : GlobalsSpaceRegion(mgr, NonStaticGlobalSpaceRegionKind) {} + +public: + + void dumpToStream(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion *R) { + return R->getKind() == NonStaticGlobalSpaceRegionKind; + } +}; + +class HeapSpaceRegion : public MemSpaceRegion { + friend class MemRegionManager; + + HeapSpaceRegion(MemRegionManager *mgr) + : MemSpaceRegion(mgr, HeapSpaceRegionKind) {} +public: + static bool classof(const MemRegion *R) { + return R->getKind() == HeapSpaceRegionKind; + } +}; + +class UnknownSpaceRegion : public MemSpaceRegion { + friend class MemRegionManager; + UnknownSpaceRegion(MemRegionManager *mgr) + : MemSpaceRegion(mgr, UnknownSpaceRegionKind) {} +public: + static bool classof(const MemRegion *R) { + return R->getKind() == UnknownSpaceRegionKind; + } +}; + +class StackSpaceRegion : public MemSpaceRegion { +private: + const StackFrameContext *SFC; + +protected: + StackSpaceRegion(MemRegionManager *mgr, Kind k, const StackFrameContext *sfc) + : MemSpaceRegion(mgr, k), SFC(sfc) { + assert(classof(this)); + } + +public: + const StackFrameContext *getStackFrame() const { return SFC; } + + void Profile(llvm::FoldingSetNodeID &ID) const; + + static bool classof(const MemRegion *R) { + Kind k = R->getKind(); + return k >= StackLocalsSpaceRegionKind && + k <= StackArgumentsSpaceRegionKind; + } +}; + +class StackLocalsSpaceRegion : public StackSpaceRegion { +private: + friend class MemRegionManager; + StackLocalsSpaceRegion(MemRegionManager *mgr, const StackFrameContext *sfc) + : StackSpaceRegion(mgr, StackLocalsSpaceRegionKind, sfc) {} +public: + static bool classof(const MemRegion *R) { + return R->getKind() == StackLocalsSpaceRegionKind; + } +}; + +class StackArgumentsSpaceRegion : public StackSpaceRegion { +private: + friend class MemRegionManager; + StackArgumentsSpaceRegion(MemRegionManager *mgr, const StackFrameContext *sfc) + : StackSpaceRegion(mgr, StackArgumentsSpaceRegionKind, sfc) {} +public: + static bool classof(const MemRegion *R) { + return R->getKind() == StackArgumentsSpaceRegionKind; + } +}; + + +/// SubRegion - A region that subsets another larger region. Most regions +/// are subclasses of SubRegion. +class SubRegion : public MemRegion { +protected: + const MemRegion* superRegion; + SubRegion(const MemRegion* sReg, Kind k) : MemRegion(k), superRegion(sReg) {} +public: + const MemRegion* getSuperRegion() const { + return superRegion; + } + + /// getExtent - Returns the size of the region in bytes. + virtual DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const { + return UnknownVal(); + } + + MemRegionManager* getMemRegionManager() const; + + bool isSubRegionOf(const MemRegion* R) const; + + static bool classof(const MemRegion* R) { + return R->getKind() > END_MEMSPACES; + } +}; + +//===----------------------------------------------------------------------===// +// MemRegion subclasses. +//===----------------------------------------------------------------------===// + +/// AllocaRegion - A region that represents an untyped blob of bytes created +/// by a call to 'alloca'. +class AllocaRegion : public SubRegion { + friend class MemRegionManager; +protected: + unsigned Cnt; // Block counter. Used to distinguish different pieces of + // memory allocated by alloca at the same call site. + const Expr* Ex; + + AllocaRegion(const Expr* ex, unsigned cnt, const MemRegion *superRegion) + : SubRegion(superRegion, AllocaRegionKind), Cnt(cnt), Ex(ex) {} + +public: + + const Expr* getExpr() const { return Ex; } + + bool isBoundable() const { return true; } + + DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr* Ex, + unsigned Cnt, const MemRegion *superRegion); + + void dumpToStream(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == AllocaRegionKind; + } +}; + +/// TypedRegion - An abstract class representing regions that are typed. +class TypedRegion : public SubRegion { +protected: + TypedRegion(const MemRegion* sReg, Kind k) : SubRegion(sReg, k) {} + +public: + virtual QualType getValueType() const = 0; + + virtual QualType getLocationType() const { + // FIXME: We can possibly optimize this later to cache this value. + QualType T = getValueType(); + ASTContext &ctx = getContext(); + if (T->getAs<ObjCObjectType>()) + return ctx.getObjCObjectPointerType(T); + return ctx.getPointerType(getValueType()); + } + + QualType getDesugaredValueType(ASTContext &Context) const { + QualType T = getValueType(); + 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; + } +}; + + +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) { + Kind k = R->getKind(); + return k >= FunctionTextRegionKind && k <= BlockTextRegionKind; + } +}; + +/// FunctionTextRegion - A region that represents code texts of function. +class FunctionTextRegion : public CodeTextRegion { + const FunctionDecl *FD; +public: + FunctionTextRegion(const FunctionDecl* fd, const MemRegion* sreg) + : CodeTextRegion(sreg, FunctionTextRegionKind), FD(fd) {} + + QualType getLocationType() const { + return getContext().getPointerType(FD->getType()); + } + + const FunctionDecl *getDecl() const { + return FD; + } + + virtual void dumpToStream(llvm::raw_ostream& os) const; + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const FunctionDecl *FD, + const MemRegion*); + + static bool classof(const MemRegion* R) { + return R->getKind() == FunctionTextRegionKind; + } +}; + + +/// BlockTextRegion - A region that represents code texts of blocks (closures). +/// Blocks are represented with two kinds of regions. BlockTextRegions +/// represent the "code", while BlockDataRegions represent instances of blocks, +/// which correspond to "code+data". The distinction is important, because +/// like a closure a block captures the values of externally referenced +/// variables. +class BlockTextRegion : public CodeTextRegion { + friend class MemRegionManager; + + const BlockDecl *BD; + AnalysisContext *AC; + CanQualType locTy; + + BlockTextRegion(const BlockDecl *bd, CanQualType lTy, + AnalysisContext *ac, const MemRegion* sreg) + : CodeTextRegion(sreg, BlockTextRegionKind), BD(bd), AC(ac), locTy(lTy) {} + +public: + QualType getLocationType() const { + return locTy; + } + + const BlockDecl *getDecl() const { + return BD; + } + + AnalysisContext *getAnalysisContext() const { return AC; } + + virtual void dumpToStream(llvm::raw_ostream& os) const; + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const BlockDecl *BD, + CanQualType, const AnalysisContext*, + const MemRegion*); + + static bool classof(const MemRegion* R) { + return R->getKind() == BlockTextRegionKind; + } +}; + +/// BlockDataRegion - A region that represents a block instance. +/// Blocks are represented with two kinds of regions. BlockTextRegions +/// represent the "code", while BlockDataRegions represent instances of blocks, +/// which correspond to "code+data". The distinction is important, because +/// like a closure a block captures the values of externally referenced +/// variables. +class BlockDataRegion : public SubRegion { + friend class MemRegionManager; + const BlockTextRegion *BC; + const LocationContext *LC; // Can be null */ + void *ReferencedVars; + + BlockDataRegion(const BlockTextRegion *bc, const LocationContext *lc, + const MemRegion *sreg) + : SubRegion(sreg, BlockDataRegionKind), BC(bc), LC(lc), ReferencedVars(0) {} + +public: + const BlockTextRegion *getCodeRegion() const { return BC; } + + const BlockDecl *getDecl() const { return BC->getDecl(); } + + class referenced_vars_iterator { + const MemRegion * const *R; + public: + explicit referenced_vars_iterator(const MemRegion * const *r) : R(r) {} + + operator const MemRegion * const *() const { + return R; + } + + const VarRegion* operator*() const { + return cast<VarRegion>(*R); + } + + bool operator==(const referenced_vars_iterator &I) const { + return I.R == R; + } + bool operator!=(const referenced_vars_iterator &I) const { + return I.R != R; + } + referenced_vars_iterator& operator++() { + ++R; + return *this; + } + }; + + referenced_vars_iterator referenced_vars_begin() const; + referenced_vars_iterator referenced_vars_end() const; + + virtual void dumpToStream(llvm::raw_ostream& os) const; + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static void ProfileRegion(llvm::FoldingSetNodeID&, const BlockTextRegion *, + const LocationContext *, const MemRegion *); + + static bool classof(const MemRegion* R) { + return R->getKind() == BlockDataRegionKind; + } +private: + void LazyInitializeReferencedVars(); +}; + +/// SymbolicRegion - A special, "non-concrete" region. Unlike other region +/// clases, SymbolicRegion represents a region that serves as an alias for +/// either a real region, a NULL pointer, etc. It essentially is used to +/// map the concept of symbolic values into the domain of regions. Symbolic +/// regions do not need to be typed. +class SymbolicRegion : public SubRegion { +protected: + const SymbolRef sym; + +public: + SymbolicRegion(const SymbolRef s, const MemRegion* sreg) + : SubRegion(sreg, SymbolicRegionKind), sym(s) {} + + SymbolRef getSymbol() const { + return sym; + } + + bool isBoundable() const { return true; } + + DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, + SymbolRef sym, + const MemRegion* superRegion); + + void dumpToStream(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == SymbolicRegionKind; + } +}; + +/// StringRegion - Region associated with a StringLiteral. +class StringRegion : public TypedRegion { + friend class MemRegionManager; + const StringLiteral* Str; +protected: + + StringRegion(const StringLiteral* str, const MemRegion* sreg) + : TypedRegion(sreg, StringRegionKind), Str(str) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, + const StringLiteral* Str, + const MemRegion* superRegion); + +public: + + const StringLiteral* getStringLiteral() const { return Str; } + + QualType getValueType() const { + return Str->getType(); + } + + DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; + + bool isBoundable() const { return false; } + + void Profile(llvm::FoldingSetNodeID& ID) const { + ProfileRegion(ID, Str, superRegion); + } + + void dumpToStream(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == StringRegionKind; + } +}; + +/// 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 { +private: + friend class MemRegionManager; + const CompoundLiteralExpr* CL; + + CompoundLiteralRegion(const CompoundLiteralExpr* cl, const MemRegion* sReg) + : TypedRegion(sReg, CompoundLiteralRegionKind), CL(cl) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, + const CompoundLiteralExpr* CL, + const MemRegion* superRegion); +public: + QualType getValueType() const { + return CL->getType(); + } + + bool isBoundable() const { return !CL->isFileScope(); } + + void Profile(llvm::FoldingSetNodeID& ID) const; + + void dumpToStream(llvm::raw_ostream& os) const; + + const CompoundLiteralExpr* getLiteralExpr() const { return CL; } + + static bool classof(const MemRegion* R) { + return R->getKind() == CompoundLiteralRegionKind; + } +}; + +class DeclRegion : public TypedRegion { +protected: + const Decl* D; + + DeclRegion(const Decl* d, const MemRegion* sReg, Kind k) + : TypedRegion(sReg, k), D(d) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D, + const MemRegion* superRegion, Kind k); + +public: + const Decl* getDecl() const { return D; } + void Profile(llvm::FoldingSetNodeID& ID) const; + + DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; + + static bool classof(const MemRegion* R) { + unsigned k = R->getKind(); + return k >= BEG_DECL_REGIONS && k <= END_DECL_REGIONS; + } +}; + +class VarRegion : public DeclRegion { + friend class MemRegionManager; + + // Constructors and private methods. + VarRegion(const VarDecl* vd, const MemRegion* sReg) + : DeclRegion(vd, sReg, VarRegionKind) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const VarDecl* VD, + const MemRegion *superRegion) { + DeclRegion::ProfileRegion(ID, VD, superRegion, VarRegionKind); + } + + void Profile(llvm::FoldingSetNodeID& ID) const; + +public: + const VarDecl *getDecl() const { return cast<VarDecl>(D); } + + const StackFrameContext *getStackFrame() const; + + QualType getValueType() const { + // FIXME: We can cache this if needed. + return getDecl()->getType(); + } + + void dumpToStream(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == VarRegionKind; + } +}; + +/// 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 { + friend class MemRegionManager; + CXXThisRegion(const PointerType *thisPointerTy, + const MemRegion *sReg) + : TypedRegion(sReg, CXXThisRegionKind), ThisPointerTy(thisPointerTy) {} + + static void ProfileRegion(llvm::FoldingSetNodeID &ID, + const PointerType *PT, + const MemRegion *sReg); + + void Profile(llvm::FoldingSetNodeID &ID) const; + +public: + QualType getValueType() const { + return QualType(ThisPointerTy, 0); + } + + void dumpToStream(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == CXXThisRegionKind; + } + +private: + const PointerType *ThisPointerTy; +}; + +class FieldRegion : public DeclRegion { + friend class MemRegionManager; + + FieldRegion(const FieldDecl* fd, const MemRegion* sReg) + : DeclRegion(fd, sReg, FieldRegionKind) {} + +public: + + void dumpToStream(llvm::raw_ostream& os) const; + + const FieldDecl* getDecl() const { return cast<FieldDecl>(D); } + + QualType getValueType() const { + // FIXME: We can cache this if needed. + return getDecl()->getType(); + } + + DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const; + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const FieldDecl* FD, + const MemRegion* superRegion) { + DeclRegion::ProfileRegion(ID, FD, superRegion, FieldRegionKind); + } + + static bool classof(const MemRegion* R) { + return R->getKind() == FieldRegionKind; + } +}; + +class ObjCIvarRegion : public DeclRegion { + + friend class MemRegionManager; + + ObjCIvarRegion(const ObjCIvarDecl* ivd, const MemRegion* sReg) + : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {} + + 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); } + QualType getValueType() const { return getDecl()->getType(); } + + void dumpToStream(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == ObjCIvarRegionKind; + } +}; +//===----------------------------------------------------------------------===// +// Auxillary data classes for use with MemRegions. +//===----------------------------------------------------------------------===// + +class ElementRegion; + +class RegionRawOffset { +private: + friend class ElementRegion; + + const MemRegion *Region; + CharUnits Offset; + + RegionRawOffset(const MemRegion* reg, CharUnits offset = CharUnits::Zero()) + : Region(reg), Offset(offset) {} + +public: + // FIXME: Eventually support symbolic offsets. + CharUnits getOffset() const { return Offset; } + const MemRegion *getRegion() const { return Region; } + + void dumpToStream(llvm::raw_ostream& os) const; + void dump() const; +}; + +class ElementRegion : public TypedRegion { + friend class MemRegionManager; + + QualType ElementType; + NonLoc Index; + + ElementRegion(QualType elementType, NonLoc Idx, const MemRegion* sReg) + : TypedRegion(sReg, ElementRegionKind), + ElementType(elementType), Index(Idx) { + assert((!isa<nonloc::ConcreteInt>(&Idx) || + cast<nonloc::ConcreteInt>(&Idx)->getValue().isSigned()) && + "The index must be signed"); + } + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType elementType, + SVal Idx, const MemRegion* superRegion); + +public: + + NonLoc getIndex() const { return Index; } + + QualType getValueType() const { + return ElementType; + } + + QualType getElementType() const { + return ElementType; + } + /// Compute the offset within the array. The array might also be a subobject. + RegionRawOffset getAsArrayOffset() const; + + void dumpToStream(llvm::raw_ostream& os) const; + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == ElementRegionKind; + } +}; + +// C++ temporary object associated with an expression. +class CXXTempObjectRegion : public TypedRegion { + friend class MemRegionManager; + + Expr const *Ex; + + CXXTempObjectRegion(Expr const *E, MemRegion const *sReg) + : TypedRegion(sReg, CXXTempObjectRegionKind), Ex(E) {} + + static void ProfileRegion(llvm::FoldingSetNodeID &ID, + Expr const *E, const MemRegion *sReg); + +public: + QualType getValueType() const { + return Ex->getType(); + } + + void dumpToStream(llvm::raw_ostream& os) const; + + void Profile(llvm::FoldingSetNodeID &ID) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == CXXTempObjectRegionKind; + } +}; + +// 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 { + friend class MemRegionManager; + + const CXXRecordDecl *decl; + + CXXBaseObjectRegion(const CXXRecordDecl *d, const MemRegion *sReg) + : TypedRegion(sReg, CXXBaseObjectRegionKind), decl(d) {} + + static void ProfileRegion(llvm::FoldingSetNodeID &ID, + const CXXRecordDecl *decl, const MemRegion *sReg); + +public: + const CXXRecordDecl *getDecl() const { return decl; } + + QualType getValueType() const; + + void dumpToStream(llvm::raw_ostream& os) const; + + void Profile(llvm::FoldingSetNodeID &ID) const; + + static bool classof(const MemRegion *region) { + return region->getKind() == CXXBaseObjectRegionKind; + } +}; + +template<typename RegionTy> +const RegionTy* MemRegion::getAs() const { + if (const RegionTy* RT = dyn_cast<RegionTy>(this)) + return RT; + + return NULL; +} + +//===----------------------------------------------------------------------===// +// MemRegionManager - Factory object for creating regions. +//===----------------------------------------------------------------------===// + +class MemRegionManager { + ASTContext &C; + llvm::BumpPtrAllocator& A; + llvm::FoldingSet<MemRegion> Regions; + + NonStaticGlobalSpaceRegion *globals; + + llvm::DenseMap<const StackFrameContext *, StackLocalsSpaceRegion *> + StackLocalsSpaceRegions; + llvm::DenseMap<const StackFrameContext *, StackArgumentsSpaceRegion *> + StackArgumentsSpaceRegions; + llvm::DenseMap<const CodeTextRegion *, StaticGlobalSpaceRegion *> + StaticsGlobalSpaceRegions; + + HeapSpaceRegion *heap; + UnknownSpaceRegion *unknown; + MemSpaceRegion *code; + +public: + MemRegionManager(ASTContext &c, llvm::BumpPtrAllocator& a) + : C(c), A(a), globals(0), heap(0), unknown(0), code(0) {} + + ~MemRegionManager(); + + ASTContext &getContext() { return C; } + + llvm::BumpPtrAllocator &getAllocator() { return A; } + + /// getStackLocalsRegion - Retrieve the memory region associated with the + /// specified stack frame. + const StackLocalsSpaceRegion * + getStackLocalsRegion(const StackFrameContext *STC); + + /// getStackArgumentsRegion - Retrieve the memory region associated with + /// function/method arguments of the specified stack frame. + const StackArgumentsSpaceRegion * + getStackArgumentsRegion(const StackFrameContext *STC); + + /// getGlobalsRegion - Retrieve the memory region associated with + /// global variables. + const GlobalsSpaceRegion *getGlobalsRegion(const CodeTextRegion *R = 0); + + /// getHeapRegion - Retrieve the memory region associated with the + /// generic "heap". + const HeapSpaceRegion *getHeapRegion(); + + /// getUnknownRegion - Retrieve the memory region associated with unknown + /// memory space. + const MemSpaceRegion *getUnknownRegion(); + + const MemSpaceRegion *getCodeRegion(); + + /// getAllocaRegion - Retrieve a region associated with a call to alloca(). + 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, + const LocationContext *LC); + + /// getCXXThisRegion - Retrieve the [artifical] region associated with the + /// parameter 'this'. + const CXXThisRegion *getCXXThisRegion(QualType thisPointerTy, + const LocationContext *LC); + + /// getSymbolicRegion - Retrieve or create a "symbolic" memory region. + const SymbolicRegion* getSymbolicRegion(SymbolRef sym); + + const StringRegion* getStringRegion(const StringLiteral* Str); + + /// getVarRegion - Retrieve or create the memory region associated with + /// a specified VarDecl and LocationContext. + const VarRegion* getVarRegion(const VarDecl *D, const LocationContext *LC); + + /// getVarRegion - Retrieve or create the memory region associated with + /// a specified VarDecl and super region. + const VarRegion* getVarRegion(const VarDecl *D, const MemRegion *superR); + + /// getElementRegion - Retrieve the memory region associated with the + /// associated element type, index, and super region. + const ElementRegion *getElementRegion(QualType elementType, NonLoc Idx, + const MemRegion *superRegion, + ASTContext &Ctx); + + const ElementRegion *getElementRegionWithSuper(const ElementRegion *ER, + const MemRegion *superRegion) { + return getElementRegion(ER->getElementType(), ER->getIndex(), + superRegion, ER->getContext()); + } + + /// getFieldRegion - Retrieve or create the memory region associated with + /// 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 MemRegion* superRegion); + + const FieldRegion *getFieldRegionWithSuper(const FieldRegion *FR, + const MemRegion *superRegion) { + return getFieldRegion(FR->getDecl(), superRegion); + } + + /// getObjCIvarRegion - Retrieve or create the memory region associated with + /// 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 MemRegion* superRegion); + + const CXXTempObjectRegion *getCXXTempObjectRegion(Expr const *Ex, + LocationContext const *LC); + + const CXXBaseObjectRegion *getCXXBaseObjectRegion(const CXXRecordDecl *decl, + const MemRegion *superRegion); + + /// Create a CXXBaseObjectRegion with the same CXXRecordDecl but a different + /// super region. + const CXXBaseObjectRegion * + getCXXBaseObjectRegionWithSuper(const CXXBaseObjectRegion *baseReg, + const MemRegion *superRegion) { + return getCXXBaseObjectRegion(baseReg->getDecl(), superRegion); + } + + const FunctionTextRegion *getFunctionTextRegion(const FunctionDecl *FD); + const BlockTextRegion *getBlockTextRegion(const BlockDecl *BD, + CanQualType locTy, + AnalysisContext *AC); + + /// getBlockDataRegion - Get the memory region associated with an instance + /// of a block. Unlike many other MemRegions, the LocationContext* + /// argument is allowed to be NULL for cases where we have no known + /// context. + const BlockDataRegion *getBlockDataRegion(const BlockTextRegion *bc, + const LocationContext *lc = NULL); + + bool isGlobalsRegion(const MemRegion* R) { + assert(R); + return R == globals; + } + +private: + template <typename RegionTy, typename A1> + RegionTy* getRegion(const A1 a1); + + template <typename RegionTy, typename A1> + RegionTy* getSubRegion(const A1 a1, const MemRegion* superRegion); + + template <typename RegionTy, typename A1, typename A2> + RegionTy* getRegion(const A1 a1, const A2 a2); + + template <typename RegionTy, typename A1, typename A2> + RegionTy* getSubRegion(const A1 a1, const A2 a2, + const MemRegion* superRegion); + + template <typename RegionTy, typename A1, typename A2, typename A3> + RegionTy* getSubRegion(const A1 a1, const A2 a2, const A3 a3, + const MemRegion* superRegion); + + template <typename REG> + const REG* LazyAllocate(REG*& region); + + template <typename REG, typename ARG> + const REG* LazyAllocate(REG*& region, ARG a); +}; + +//===----------------------------------------------------------------------===// +// Out-of-line member definitions. +//===----------------------------------------------------------------------===// + +inline ASTContext& MemRegion::getContext() const { + return getMemRegionManager()->getContext(); +} + +} // end GR namespace + +} // end clang namespace + +//===----------------------------------------------------------------------===// +// Pretty-printing regions. +//===----------------------------------------------------------------------===// + +namespace llvm { +static inline raw_ostream& operator<<(raw_ostream& os, + const clang::ento::MemRegion* R) { + R->dumpToStream(os); + return os; +} +} // end llvm namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h new file mode 100644 index 0000000..710fc6b --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h @@ -0,0 +1,210 @@ +//===- ObjCMessage.h - Wrapper for ObjC messages and dot syntax ---*- 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 ObjCMessage which serves as a common wrapper for ObjC +// message expressions or implicit messages for loading/storing ObjC properties. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_PATHSENSITIVE_OBJCMESSAGE +#define LLVM_CLANG_STATICANALYZER_PATHSENSITIVE_OBJCMESSAGE + +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h" +#include "clang/AST/ExprObjC.h" + +namespace clang { +namespace ento { + +/// \brief Represents both explicit ObjC message expressions and implicit +/// messages that are sent for handling properties in dot syntax. +class ObjCMessage { + const Expr *MsgOrPropE; + const Expr *OriginE; + bool IsPropSetter; + SVal SetterArgV; + +protected: + ObjCMessage(const Expr *E, const Expr *origE, bool isSetter, SVal setArgV) + : MsgOrPropE(E), OriginE(origE), + IsPropSetter(isSetter), SetterArgV(setArgV) { } + +public: + ObjCMessage() : MsgOrPropE(0), OriginE(0) { } + + ObjCMessage(const ObjCMessageExpr *E) + : MsgOrPropE(E), OriginE(E) { + assert(E && "should not be initialized with null expression"); + } + + bool isValid() const { return MsgOrPropE != 0; } + bool isInvalid() const { return !isValid(); } + + bool isMessageExpr() const { + return isValid() && isa<ObjCMessageExpr>(MsgOrPropE); + } + + bool isPropertyGetter() const { + return isValid() && + isa<ObjCPropertyRefExpr>(MsgOrPropE) && !IsPropSetter; + } + + bool isPropertySetter() const { + return isValid() && + isa<ObjCPropertyRefExpr>(MsgOrPropE) && IsPropSetter; + } + + const Expr *getOriginExpr() const { return OriginE; } + + QualType getType(ASTContext &ctx) const; + + QualType getResultType(ASTContext &ctx) const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) + if (const ObjCMethodDecl *MD = msgE->getMethodDecl()) + return MD->getResultType(); + return getType(ctx); + } + + Selector getSelector() const; + + const Expr *getInstanceReceiver() const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) + return msgE->getInstanceReceiver(); + const ObjCPropertyRefExpr *propE = cast<ObjCPropertyRefExpr>(MsgOrPropE); + if (propE->isObjectReceiver()) + return propE->getBase(); + return 0; + } + + bool isInstanceMessage() const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) + return msgE->isInstanceMessage(); + const ObjCPropertyRefExpr *propE = cast<ObjCPropertyRefExpr>(MsgOrPropE); + // FIXME: 'super' may be super class. + return propE->isObjectReceiver() || propE->isSuperReceiver(); + } + + const ObjCMethodDecl *getMethodDecl() const; + + const ObjCInterfaceDecl *getReceiverInterface() const; + + SourceLocation getSuperLoc() const { + assert(isValid() && "This ObjCMessage is uninitialized!"); + if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) + return msgE->getSuperLoc(); + return cast<ObjCPropertyRefExpr>(MsgOrPropE)->getReceiverLocation(); + } + + 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(); + } +}; + +class ObjCPropertyGetter : public ObjCMessage { +public: + ObjCPropertyGetter(const ObjCPropertyRefExpr *propE, const Expr *originE) + : ObjCMessage(propE, originE, false, SVal()) { + assert(propE && originE && + "should not be initialized with null expressions"); + } +}; + +class ObjCPropertySetter : public ObjCMessage { +public: + ObjCPropertySetter(const ObjCPropertyRefExpr *propE, const Expr *storeE, + SVal argV) + : ObjCMessage(propE, storeE, true, argV) { + assert(propE && storeE &&"should not be initialized with null expressions"); + } +}; + +/// \brief Common wrapper for a call expression or an ObjC message, mainly to +/// provide a common interface for handling their arguments. +class CallOrObjCMessage { + const CallExpr *CallE; + ObjCMessage Msg; + const GRState *State; + +public: + CallOrObjCMessage(const CallExpr *callE, const GRState *state) + : CallE(callE), State(state) { } + CallOrObjCMessage(const ObjCMessage &msg, const GRState *state) + : CallE(0), Msg(msg), State(state) { } + + QualType getResultType(ASTContext &ctx) const; + + unsigned getNumArgs() const { + if (CallE) return CallE->getNumArgs(); + return Msg.getNumArgs(); + } + + SVal getArgSVal(unsigned i) const { + assert(i < getNumArgs()); + if (CallE) return State->getSVal(CallE->getArg(i)); + return Msg.getArgSVal(i, State); + } + + SVal getArgSValAsScalarOrLoc(unsigned i) const; + + const Expr *getArg(unsigned i) const { + assert(i < getNumArgs()); + if (CallE) return CallE->getArg(i); + return Msg.getArgExpr(i); + } + + SourceRange getArgSourceRange(unsigned i) const { + assert(i < getNumArgs()); + if (CallE) return CallE->getArg(i)->getSourceRange(); + return Msg.getArgSourceRange(i); + } +}; + +} +} + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h new file mode 100644 index 0000000..fc2b76e --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -0,0 +1,258 @@ +// SValBuilder.h - Construction of SVals from evaluating expressions -*- 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 SValBuilder, a class that defines the interface for +// "symbolical evaluators" which construct an SVal from an expression. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_SVALBUILDER +#define LLVM_CLANG_GR_SVALBUILDER + +#include "clang/AST/Expr.h" +#include "clang/AST/ExprCXX.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" + +namespace clang { + +namespace ento { + +class GRState; + +class SValBuilder { +protected: + ASTContext &Context; + + /// Manager of APSInt values. + BasicValueFactory BasicVals; + + /// Manages the creation of symbols. + SymbolManager SymMgr; + + /// Manages the creation of memory regions. + MemRegionManager MemMgr; + + GRStateManager &StateMgr; + + /// The scalar type to use for array indices. + const QualType ArrayIndexTy; + + /// The width of the scalar type used for array indices. + const unsigned ArrayIndexWidth; + +public: + // FIXME: Make these protected again one RegionStoreManager correctly + // handles loads from differening bound value types. + virtual SVal evalCastNL(NonLoc val, QualType castTy) = 0; + virtual SVal evalCastL(Loc val, QualType castTy) = 0; + +public: + SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, + GRStateManager &stateMgr) + : Context(context), BasicVals(context, alloc), + SymMgr(context, BasicVals, alloc), + MemMgr(context, alloc), + StateMgr(stateMgr), + ArrayIndexTy(context.IntTy), + ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {} + + virtual ~SValBuilder() {} + + SVal evalCast(SVal V, QualType castTy, QualType originalType); + + virtual SVal evalMinus(NonLoc val) = 0; + + virtual SVal evalComplement(NonLoc val) = 0; + + virtual SVal evalBinOpNN(const GRState *state, BinaryOperator::Opcode Op, + NonLoc lhs, NonLoc rhs, QualType resultTy) = 0; + + virtual SVal evalBinOpLL(const GRState *state, BinaryOperator::Opcode Op, + Loc lhs, Loc rhs, QualType resultTy) = 0; + + virtual SVal evalBinOpLN(const GRState *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 V) = 0; + + SVal evalBinOp(const GRState *ST, BinaryOperator::Opcode Op, + SVal L, SVal R, QualType T); + + DefinedOrUnknownSVal evalEQ(const GRState *ST, DefinedOrUnknownSVal L, + DefinedOrUnknownSVal R); + + ASTContext &getContext() { return Context; } + const ASTContext &getContext() const { return Context; } + + GRStateManager &getStateManager() { return StateMgr; } + + QualType getConditionType() const { + return getContext().IntTy; + } + + QualType getArrayIndexType() const { + return ArrayIndexTy; + } + + BasicValueFactory &getBasicValueFactory() { return BasicVals; } + const BasicValueFactory &getBasicValueFactory() const { return BasicVals; } + + SymbolManager &getSymbolManager() { return SymMgr; } + const SymbolManager &getSymbolManager() const { return SymMgr; } + + MemRegionManager &getRegionManager() { return MemMgr; } + const MemRegionManager &getRegionManager() const { return MemMgr; } + + // Forwarding methods to SymbolManager. + + const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T, + unsigned VisitCount, + const void* SymbolTag = 0) { + return SymMgr.getConjuredSymbol(E, T, VisitCount, SymbolTag); + } + + const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount, + const void* SymbolTag = 0) { + return SymMgr.getConjuredSymbol(E, VisitCount, SymbolTag); + } + + /// makeZeroVal - Construct an SVal representing '0' for the specified type. + DefinedOrUnknownSVal makeZeroVal(QualType T); + + /// getRegionValueSymbolVal - make a unique symbol for value of R. + DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedRegion *R); + + DefinedOrUnknownSVal getConjuredSymbolVal(const void *SymbolTag, + const Expr *E, unsigned Count); + DefinedOrUnknownSVal getConjuredSymbolVal(const void *SymbolTag, + const Expr *E, QualType T, + unsigned Count); + + DefinedOrUnknownSVal getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, + const TypedRegion *R); + + DefinedSVal getMetadataSymbolVal(const void *SymbolTag, const MemRegion *MR, + const Expr *E, QualType T, unsigned Count); + + DefinedSVal getFunctionPointer(const FunctionDecl *FD); + + DefinedSVal getBlockPointer(const BlockDecl *BD, CanQualType locTy, + const LocationContext *LC); + + NonLoc makeCompoundVal(QualType T, llvm::ImmutableList<SVal> Vals) { + return nonloc::CompoundVal(BasicVals.getCompoundValData(T, Vals)); + } + + NonLoc makeLazyCompoundVal(const void *store, const TypedRegion *R) { + return nonloc::LazyCompoundVal(BasicVals.getLazyCompoundValData(store, R)); + } + + NonLoc makeZeroArrayIndex() { + return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy)); + } + + NonLoc makeArrayIndex(uint64_t idx) { + return nonloc::ConcreteInt(BasicVals.getValue(idx, ArrayIndexTy)); + } + + SVal convertToArrayIndex(SVal V); + + nonloc::ConcreteInt makeIntVal(const IntegerLiteral* I) { + return nonloc::ConcreteInt(BasicVals.getValue(I->getValue(), + I->getType()->isUnsignedIntegerType())); + } + + nonloc::ConcreteInt makeBoolVal(const CXXBoolLiteralExpr *E) { + return makeTruthVal(E->getValue()); + } + + nonloc::ConcreteInt makeIntVal(const llvm::APSInt& V) { + return nonloc::ConcreteInt(BasicVals.getValue(V)); + } + + loc::ConcreteInt makeIntLocVal(const llvm::APSInt &v) { + return loc::ConcreteInt(BasicVals.getValue(v)); + } + + NonLoc makeIntVal(const llvm::APInt& V, bool isUnsigned) { + return nonloc::ConcreteInt(BasicVals.getValue(V, isUnsigned)); + } + + DefinedSVal makeIntVal(uint64_t X, QualType T) { + if (Loc::isLocType(T)) + return loc::ConcreteInt(BasicVals.getValue(X, T)); + + return nonloc::ConcreteInt(BasicVals.getValue(X, T)); + } + + NonLoc makeIntVal(uint64_t X, bool isUnsigned) { + return nonloc::ConcreteInt(BasicVals.getIntValue(X, isUnsigned)); + } + + NonLoc makeIntValWithPtrWidth(uint64_t X, bool isUnsigned) { + return nonloc::ConcreteInt(BasicVals.getIntWithPtrWidth(X, isUnsigned)); + } + + NonLoc makeIntVal(uint64_t X, unsigned BitWidth, bool isUnsigned) { + return nonloc::ConcreteInt(BasicVals.getValue(X, BitWidth, isUnsigned)); + } + + NonLoc makeLocAsInteger(Loc V, unsigned Bits) { + return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(V, Bits)); + } + + NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, + const llvm::APSInt& rhs, QualType T); + + NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, + const SymExpr *rhs, QualType T); + + nonloc::ConcreteInt makeTruthVal(bool b, QualType T) { + return nonloc::ConcreteInt(BasicVals.getTruthValue(b, T)); + } + + nonloc::ConcreteInt makeTruthVal(bool b) { + return nonloc::ConcreteInt(BasicVals.getTruthValue(b)); + } + + Loc makeNull() { + return loc::ConcreteInt(BasicVals.getZeroWithPtrWidth()); + } + + Loc makeLoc(SymbolRef Sym) { + return loc::MemRegionVal(MemMgr.getSymbolicRegion(Sym)); + } + + Loc makeLoc(const MemRegion* R) { + return loc::MemRegionVal(R); + } + + Loc makeLoc(const AddrLabelExpr *E) { + return loc::GotoLabel(E->getLabel()); + } + + Loc makeLoc(const llvm::APSInt& V) { + return loc::ConcreteInt(BasicVals.getValue(V)); + } + +}; + +SValBuilder* createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, + ASTContext &context, + GRStateManager &stateMgr); + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h new file mode 100644 index 0000000..0d43079 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -0,0 +1,544 @@ +//== SVals.h - Abstract Values for Static Analysis ---------*- 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 SVal, Loc, and NonLoc, classes that represent +// abstract r-values for use with path-sensitive value tracking. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_RVALUE_H +#define LLVM_CLANG_GR_RVALUE_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. +//==------------------------------------------------------------------------==// + +namespace clang { + +namespace ento { + +class CompoundValData; +class LazyCompoundValData; +class GRState; +class BasicValueFactory; +class MemRegion; +class TypedRegion; +class MemRegionManager; +class GRStateManager; +class SValBuilder; + +/// SVal - This represents a symbolic expression, which can be either +/// an L-value or an R-value. +/// +class SVal { +public: + enum BaseKind { + // The enumerators must be representable using 2 bits. + UndefinedKind = 0, // for subclass UndefinedVal (an uninitialized value) + UnknownKind = 1, // for subclass UnknownVal (a void value) + LocKind = 2, // for subclass Loc (an L-value) + NonLocKind = 3 // for subclass NonLoc (an R-value that's not + // an L-value) + }; + enum { BaseBits = 2, BaseMask = 0x3 }; + +protected: + 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) + : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} + + explicit SVal(BaseKind k, const void* D = NULL) + : Data(D), Kind(k) {} + +public: + explicit SVal() : Data(0), Kind(0) {} + ~SVal() {} + + /// BufferTy - A temporary buffer to hold a set of SVals. + typedef llvm::SmallVector<SVal,5> BufferTy; + + inline unsigned getRawKind() const { return Kind; } + inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); } + inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; } + + // This method is required for using SVal in a FoldingSetNode. It + // extracts a unique signature for this SVal object. + inline void Profile(llvm::FoldingSetNodeID& ID) const { + ID.AddInteger((unsigned) getRawKind()); + ID.AddPointer(Data); + } + + inline bool operator==(const SVal& R) const { + return getRawKind() == R.getRawKind() && Data == R.Data; + } + + inline bool operator!=(const SVal& R) const { + return !(*this == R); + } + + inline bool isUnknown() const { + return getRawKind() == UnknownKind; + } + + inline bool isUndef() const { + return getRawKind() == UndefinedKind; + } + + inline bool isUnknownOrUndef() const { + return getRawKind() <= UnknownKind; + } + + inline bool isValid() const { + return getRawKind() > UnknownKind; + } + + bool isConstant() const; + + bool isConstant(int I) const; + + bool isZeroConstant() const; + + /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true; + bool hasConjuredSymbol() const; + + /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a + /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. + /// Otherwise return 0. + const FunctionDecl* getAsFunctionDecl() const; + + /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and + /// wraps a symbol, return that SymbolRef. Otherwise return NULL. + SymbolRef getAsLocSymbol() const; + + /// Get the symbol in the SVal or its base region. + SymbolRef getLocSymbolInBase() const; + + /// getAsSymbol - If this Sval wraps a symbol return that SymbolRef. + /// Otherwise return a SymbolRef where 'isValid()' returns false. + SymbolRef getAsSymbol() const; + + /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then + /// return that expression. Otherwise return NULL. + const SymExpr *getAsSymbolicExpression() const; + + const MemRegion *getAsRegion() const; + + void dumpToStream(llvm::raw_ostream& OS) const; + void dump() const; + + // Iterators. + class symbol_iterator { + llvm::SmallVector<const SymExpr*, 5> itr; + void expand(); + public: + symbol_iterator() {} + symbol_iterator(const SymExpr* SE); + + symbol_iterator& operator++(); + SymbolRef operator*(); + + bool operator==(const symbol_iterator& X) const; + bool operator!=(const symbol_iterator& X) const; + }; + + symbol_iterator symbol_begin() const { + const SymExpr *SE = getAsSymbolicExpression(); + if (SE) + return symbol_iterator(SE); + else + return symbol_iterator(); + } + + symbol_iterator symbol_end() const { return symbol_iterator(); } + + // Implement isa<T> support. + static inline bool classof(const SVal*) { return true; } +}; + + +class UndefinedVal : public SVal { +public: + UndefinedVal() : SVal(UndefinedKind) {} + UndefinedVal(const void* D) : SVal(UndefinedKind, D) {} + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == UndefinedKind; + } + + const void* getData() const { return Data; } +}; + +class DefinedOrUnknownSVal : public SVal { +private: + // Do not implement. We want calling these methods to be a compiler + // error since they are tautologically false. + bool isUndef() const; + bool isValid() const; + +protected: + explicit DefinedOrUnknownSVal(const void* d, bool isLoc, unsigned ValKind) + : SVal(d, isLoc, ValKind) {} + + explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL) + : SVal(k, D) {} + +public: + // Implement isa<T> support. + static inline bool classof(const SVal *V) { + return !V->isUndef(); + } +}; + +class UnknownVal : public DefinedOrUnknownSVal { +public: + explicit UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {} + + static inline bool classof(const SVal *V) { + return V->getBaseKind() == UnknownKind; + } +}; + +class DefinedSVal : public DefinedOrUnknownSVal { +private: + // Do not implement. We want calling these methods to be a compiler + // error since they are tautologically true/false. + bool isUnknown() const; + bool isUnknownOrUndef() const; + bool isValid() const; +protected: + explicit DefinedSVal(const void* d, bool isLoc, unsigned ValKind) + : DefinedOrUnknownSVal(d, isLoc, ValKind) {} +public: + // Implement isa<T> support. + static inline bool classof(const SVal *V) { + return !V->isUnknownOrUndef(); + } +}; + +class NonLoc : public DefinedSVal { +protected: + explicit NonLoc(unsigned SubKind, const void* d) + : DefinedSVal(d, false, SubKind) {} + +public: + void dumpToStream(llvm::raw_ostream& Out) const; + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind; + } +}; + +class Loc : public DefinedSVal { +protected: + explicit Loc(unsigned SubKind, const void* D) + : DefinedSVal(const_cast<void*>(D), true, SubKind) {} + +public: + void dumpToStream(llvm::raw_ostream& Out) const; + + Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {} + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind; + } + + static inline bool isLocType(QualType T) { + return T->isAnyPointerType() || T->isBlockPointerType() || + T->isReferenceType(); + } +}; + +//==------------------------------------------------------------------------==// +// Subclasses of NonLoc. +//==------------------------------------------------------------------------==// + +namespace nonloc { + +enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, + LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; + +class SymbolVal : public NonLoc { +public: + SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {} + + SymbolRef getSymbol() const { + return (const SymbolData*) Data; + } + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == SymbolValKind; + } + + static inline bool classof(const NonLoc* V) { + return V->getSubKind() == SymbolValKind; + } +}; + +class SymExprVal : public NonLoc { +public: + explicit SymExprVal(const SymExpr *SE) + : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {} + + const SymExpr *getSymbolicExpression() const { + return reinterpret_cast<const SymExpr*>(Data); + } + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == SymExprValKind; + } + + static inline bool classof(const NonLoc* V) { + return V->getSubKind() == SymExprValKind; + } +}; + +class ConcreteInt : public NonLoc { +public: + explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} + + const llvm::APSInt& getValue() const { + return *static_cast<const llvm::APSInt*>(Data); + } + + // Transfer functions for binary/unary operations on ConcreteInts. + SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op, + const ConcreteInt& R) const; + + ConcreteInt evalComplement(SValBuilder &svalBuilder) const; + + ConcreteInt evalMinus(SValBuilder &svalBuilder) const; + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == ConcreteIntKind; + } + + static inline bool classof(const NonLoc* V) { + return V->getSubKind() == ConcreteIntKind; + } +}; + +class LocAsInteger : public NonLoc { + friend class ento::SValBuilder; + + explicit LocAsInteger(const std::pair<SVal, uintptr_t>& data) : + NonLoc(LocAsIntegerKind, &data) { + assert (isa<Loc>(data.first)); + } + +public: + + Loc getLoc() const { + return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first); + } + + const Loc& getPersistentLoc() const { + const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first; + return cast<Loc>(V); + } + + unsigned getNumBits() const { + return ((std::pair<SVal, unsigned>*) Data)->second; + } + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == LocAsIntegerKind; + } + + static inline bool classof(const NonLoc* V) { + return V->getSubKind() == LocAsIntegerKind; + } +}; + +class CompoundVal : public NonLoc { + friend class ento::SValBuilder; + + explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} + +public: + const CompoundValData* getValue() const { + return static_cast<const CompoundValData*>(Data); + } + + typedef llvm::ImmutableList<SVal>::iterator iterator; + iterator begin() const; + iterator end() const; + + static bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind; + } + + static bool classof(const NonLoc* V) { + return V->getSubKind() == CompoundValKind; + } +}; + +class LazyCompoundVal : public NonLoc { + friend class ento::SValBuilder; + + explicit LazyCompoundVal(const LazyCompoundValData *D) + : NonLoc(LazyCompoundValKind, D) {} +public: + const LazyCompoundValData *getCVData() const { + return static_cast<const LazyCompoundValData*>(Data); + } + const void *getStore() const; + const TypedRegion *getRegion() const; + + static bool classof(const SVal *V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == LazyCompoundValKind; + } + static bool classof(const NonLoc *V) { + return V->getSubKind() == LazyCompoundValKind; + } +}; + +} // end namespace ento::nonloc + +//==------------------------------------------------------------------------==// +// Subclasses of Loc. +//==------------------------------------------------------------------------==// + +namespace loc { + +enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind, ObjCPropRefKind }; + +class GotoLabel : public Loc { +public: + explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {} + + const LabelDecl *getLabel() const { + return static_cast<const LabelDecl*>(Data); + } + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind && V->getSubKind() == GotoLabelKind; + } + + static inline bool classof(const Loc* V) { + return V->getSubKind() == GotoLabelKind; + } +}; + + +class MemRegionVal : public Loc { +public: + explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {} + + const MemRegion* getRegion() const { + return static_cast<const MemRegion*>(Data); + } + + const MemRegion* stripCasts() const; + + template <typename REGION> + const REGION* getRegionAs() const { + return llvm::dyn_cast<REGION>(getRegion()); + } + + inline bool operator==(const MemRegionVal& R) const { + return getRegion() == R.getRegion(); + } + + inline bool operator!=(const MemRegionVal& R) const { + return getRegion() != R.getRegion(); + } + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind && + V->getSubKind() == MemRegionKind; + } + + static inline bool classof(const Loc* V) { + return V->getSubKind() == MemRegionKind; + } +}; + +class ConcreteInt : public Loc { +public: + explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} + + const llvm::APSInt& getValue() const { + return *static_cast<const llvm::APSInt*>(Data); + } + + // Transfer functions for binary/unary operations on ConcreteInts. + SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, + const ConcreteInt& R) const; + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind && + V->getSubKind() == ConcreteIntKind; + } + + static inline bool classof(const Loc* V) { + return V->getSubKind() == ConcreteIntKind; + } +}; + +/// \brief Pseudo-location SVal used by the ExprEngine to simulate a "load" or +/// "store" of an ObjC property for the dot syntax. +class ObjCPropRef : public Loc { +public: + explicit ObjCPropRef(const ObjCPropertyRefExpr *E) + : Loc(ObjCPropRefKind, E) {} + + const ObjCPropertyRefExpr *getPropRefExpr() const { + return static_cast<const ObjCPropertyRefExpr *>(Data); + } + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind && + V->getSubKind() == ObjCPropRefKind; + } + + static inline bool classof(const Loc* V) { + return V->getSubKind() == ObjCPropRefKind; + } +}; + +} // end ento::loc namespace +} // end GR namespace + +} // end clang namespace + +namespace llvm { +static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, + clang::ento::SVal V) { + V.dumpToStream(os); + return os; +} + +} // end llvm namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h new file mode 100644 index 0000000..0251311 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h @@ -0,0 +1,307 @@ +//== Store.h - Interface for maps from Locations to Values ------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the types Store and StoreManager. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_STORE_H +#define LLVM_CLANG_GR_STORE_H + +#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/Optional.h" + +namespace clang { + +class Stmt; +class Expr; +class ObjCIvarDecl; +class StackFrameContext; + +namespace ento { + +/// Store - This opaque type encapsulates an immutable mapping from +/// 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; + +class GRState; +class GRStateManager; +class SubRegionMap; +class StoreManager; + +class StoreRef { + Store store; + StoreManager &mgr; +public: + StoreRef(Store, StoreManager &); + StoreRef(const StoreRef &); + StoreRef &operator=(StoreRef const &); + + bool operator==(const StoreRef &x) const { + assert(&mgr == &x.mgr); + return x.store == store; + } + bool operator!=(const StoreRef &x) const { return !operator==(x); } + + ~StoreRef(); + + Store getStore() const { return store; } +}; + +class StoreManager { +protected: + SValBuilder &svalBuilder; + GRStateManager &StateMgr; + + /// MRMgr - Manages region objects associated with this StoreManager. + MemRegionManager &MRMgr; + ASTContext &Ctx; + + StoreManager(GRStateManager &stateMgr); + +public: + virtual ~StoreManager() {} + + /// Return the value bound to specified location in a given state. + /// \param[in] state The analysis state. + /// \param[in] loc The symbolic memory location. + /// \param[in] T An optional type that provides a hint indicating the + /// expected type of the returned value. This is used if the value is + /// lazily computed. + /// \return The value bound to the location \c loc. + virtual SVal Retrieve(Store store, Loc loc, QualType T = QualType()) = 0; + + /// Return a state with the specified value bound to the given location. + /// \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 + /// \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; + + virtual StoreRef BindDefault(Store store, const MemRegion *R, SVal V); + virtual StoreRef Remove(Store St, Loc L) = 0; + + /// BindCompoundLiteral - Return the store that has the bindings currently + /// in 'store' plus the bindings for the CompoundLiteral. 'R' is the region + /// for the compound literal and 'BegInit' and 'EndInit' represent an + /// array of initializer values. + virtual StoreRef BindCompoundLiteral(Store store, + const CompoundLiteralExpr* cl, + const LocationContext *LC, SVal v) = 0; + + /// getInitialStore - Returns the initial "empty" store representing the + /// value bindings upon entry to an analyzed function. + virtual StoreRef getInitialStore(const LocationContext *InitLoc) = 0; + + /// getRegionManager - Returns the internal RegionManager object that is + /// used to query and manipulate MemRegion objects. + MemRegionManager& getRegionManager() { return MRMgr; } + + /// getSubRegionMap - Returns an opaque map object that clients can query + /// to get the subregions of a given MemRegion object. It is the + // caller's responsibility to 'delete' the returned map. + virtual SubRegionMap *getSubRegionMap(Store store) = 0; + + virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) { + return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC)); + } + + virtual Loc getLValueString(const StringLiteral* S) { + return svalBuilder.makeLoc(MRMgr.getStringRegion(S)); + } + + Loc getLValueCompoundLiteral(const CompoundLiteralExpr* CL, + const LocationContext *LC) { + return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)); + } + + virtual SVal getLValueIvar(const ObjCIvarDecl* decl, SVal base) { + return getLValueFieldOrIvar(decl, base); + } + + virtual SVal getLValueField(const FieldDecl* D, SVal Base) { + return getLValueFieldOrIvar(D, Base); + } + + virtual SVal getLValueElement(QualType elementType, NonLoc offset, SVal Base); + + // FIXME: This should soon be eliminated altogether; clients should deal with + // region extents directly. + virtual DefinedOrUnknownSVal getSizeInElements(const GRState *state, + const MemRegion *region, + QualType EleTy) { + return UnknownVal(); + } + + /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit + /// conversions between arrays and pointers. + virtual SVal ArrayToPointer(Loc Array) = 0; + + /// Evaluates DerivedToBase casts. + virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType) { + return UnknownVal(); + } + + class CastResult { + const GRState *state; + const MemRegion *region; + public: + const GRState *getState() const { return state; } + const MemRegion* getRegion() const { return region; } + CastResult(const GRState *s, const MemRegion* r = 0) : state(s), region(r){} + }; + + const ElementRegion *GetElementZeroRegion(const MemRegion *R, QualType T); + + /// castRegion - Used by ExprEngine::VisitCast to handle casts from + /// a MemRegion* to a specific location type. 'R' is the region being + /// casted and 'CastToTy' the result type of the cast. + const MemRegion *castRegion(const MemRegion *region, QualType CastToTy); + + virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, + SymbolReaper& SymReaper, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) = 0; + + virtual StoreRef BindDecl(Store store, const VarRegion *VR, SVal initVal) = 0; + + virtual StoreRef BindDeclWithNoInit(Store store, const VarRegion *VR) = 0; + + /// If the StoreManager supports it, increment the reference count of + /// the specified Store object. + virtual void incrementReferenceCount(Store store) {} + + /// If the StoreManager supports it, decrement the reference count of + /// the specified Store object. If the reference count hits 0, the memory + /// associated with the object is recycled. + virtual void decrementReferenceCount(Store store) {} + + typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols; + typedef llvm::SmallVector<const MemRegion *, 8> InvalidatedRegions; + + /// invalidateRegions - Clears out the specified regions from the store, + /// marking their values as unknown. Depending on the store, this may also + /// invalidate additional regions that may have changed based on accessing + /// the given regions. Optionally, invalidates non-static globals as well. + /// \param[in] store The initial store + /// \param[in] Begin A pointer to the first region to invalidate. + /// \param[in] End A pointer just past the last region to invalidate. + /// \param[in] E The current statement being evaluated. Used to conjure + /// symbols to mark the values of invalidated regions. + /// \param[in] Count The current block count. Used to conjure + /// symbols to mark the values of invalidated regions. + /// \param[in,out] IS A set to fill with any symbols that are no longer + /// accessible. Pass \c NULL if this information will not be used. + /// \param[in] invalidateGlobals If \c true, any non-static global regions + /// are invalidated as well. + /// \param[in,out] Regions A vector to fill with any regions being + /// invalidated. This should include any regions explicitly invalidated + /// even if they do not currently have bindings. Pass \c NULL if this + /// information will not be used. + virtual StoreRef invalidateRegions(Store store, + const MemRegion * const *Begin, + const MemRegion * const *End, + const Expr *E, unsigned Count, + InvalidatedSymbols *IS, + bool invalidateGlobals, + InvalidatedRegions *Regions) = 0; + + /// enterStackFrame - Let the StoreManager to do something when execution + /// engine is about to execute into a callee. + virtual StoreRef enterStackFrame(const GRState *state, + const StackFrameContext *frame); + + virtual void print(Store store, llvm::raw_ostream& Out, + const char* nl, const char *sep) = 0; + + class BindingsHandler { + public: + virtual ~BindingsHandler(); + virtual bool HandleBinding(StoreManager& SMgr, Store store, + const MemRegion *region, SVal val) = 0; + }; + + /// iterBindings - Iterate over the bindings in the Store. + virtual void iterBindings(Store store, BindingsHandler& f) = 0; + +protected: + const MemRegion *MakeElementRegion(const MemRegion *baseRegion, + QualType pointeeTy, uint64_t index = 0); + + /// 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); + +private: + SVal getLValueFieldOrIvar(const Decl* decl, SVal base); +}; + + +inline StoreRef::StoreRef(Store store, StoreManager & smgr) + : store(store), mgr(smgr) { + if (store) + mgr.incrementReferenceCount(store); +} + +inline StoreRef::StoreRef(const StoreRef &sr) + : store(sr.store), mgr(sr.mgr) +{ + if (store) + mgr.incrementReferenceCount(store); +} + +inline StoreRef::~StoreRef() { + if (store) + mgr.decrementReferenceCount(store); +} + +inline StoreRef &StoreRef::operator=(StoreRef const &newStore) { + assert(&newStore.mgr == &mgr); + if (store != newStore.store) { + mgr.incrementReferenceCount(newStore.store); + mgr.decrementReferenceCount(store); + store = newStore.getStore(); + } + return *this; +} + +// FIXME: Do we still need this? +/// SubRegionMap - An abstract interface that represents a queryable map +/// between MemRegion objects and their subregions. +class SubRegionMap { +public: + virtual ~SubRegionMap() {} + + class Visitor { + public: + virtual ~Visitor() {} + virtual bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) = 0; + }; + + 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); + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h new file mode 100644 index 0000000..3d6f9fa --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h @@ -0,0 +1,116 @@ +//== SubEngine.h - Interface of the subengine of CoreEngine --------*- 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 the interface of a subengine of the CoreEngine. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_CLANG_GR_SUBENGINE_H +#define LLVM_CLANG_GR_SUBENGINE_H + +#include "clang/Analysis/ProgramPoint.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" + +namespace clang { + +class CFGBlock; +class CFGElement; +class LocationContext; +class Stmt; + +namespace ento { + +template <typename PP> class GenericNodeBuilder; +class AnalysisManager; +class ExplodedNodeSet; +class ExplodedNode; +class GRState; +class GRStateManager; +class BlockCounter; +class StmtNodeBuilder; +class BranchNodeBuilder; +class IndirectGotoNodeBuilder; +class SwitchNodeBuilder; +class EndOfFunctionNodeBuilder; +class CallEnterNodeBuilder; +class CallExitNodeBuilder; +class MemRegion; + +class SubEngine { +public: + virtual ~SubEngine() {} + + virtual const GRState* getInitialState(const LocationContext *InitLoc) = 0; + + virtual AnalysisManager &getAnalysisManager() = 0; + + virtual GRStateManager &getStateManager() = 0; + + /// Called by CoreEngine. Used to generate new successor + /// nodes by processing the 'effects' of a block-level statement. + virtual void processCFGElement(const CFGElement E, StmtNodeBuilder& builder)=0; + + /// Called by CoreEngine when it starts processing a CFGBlock. The + /// SubEngine is expected to populate dstNodes with new nodes representing + /// updated analysis state, or generate no nodes at all if it doesn't. + virtual void processCFGBlockEntrance(ExplodedNodeSet &dstNodes, + GenericNodeBuilder<BlockEntrance> &nodeBuilder) = 0; + + /// 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, + BranchNodeBuilder& builder) = 0; + + /// Called by CoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a computed goto jump. + virtual void processIndirectGoto(IndirectGotoNodeBuilder& builder) = 0; + + /// Called by CoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a switch statement. + virtual void processSwitch(SwitchNodeBuilder& builder) = 0; + + /// Called by CoreEngine. Used to generate end-of-path + /// nodes when the control reaches the end of a function. + virtual void processEndOfFunction(EndOfFunctionNodeBuilder& builder) = 0; + + // Generate the entry node of the callee. + virtual void processCallEnter(CallEnterNodeBuilder &builder) = 0; + + // Generate the first post callsite node. + virtual void processCallExit(CallExitNodeBuilder &builder) = 0; + + /// Called by ConstraintManager. Used to call checker-specific + /// logic for handling assumptions on symbolic values. + virtual const GRState* processAssume(const GRState *state, + SVal cond, bool assumption) = 0; + + /// wantsRegionChangeUpdate - Called by GRStateManager to determine if a + /// region change should trigger a processRegionChanges update. + virtual bool wantsRegionChangeUpdate(const GRState* state) = 0; + + /// processRegionChanges - Called by GRStateManager whenever a change is made + /// to the store. Used to update checkers that track region values. + virtual const GRState* processRegionChanges(const GRState* state, + const MemRegion* const *Begin, + const MemRegion* const *End) = 0; + + inline const GRState* processRegionChange(const GRState* state, + const MemRegion* MR) { + return processRegionChanges(state, &MR, &MR+1); + } + + /// Called by CoreEngine when the analysis worklist is either empty or the + // maximum number of analysis steps have been reached. + virtual void processEndWorklist(bool hasWorkRemaining) = 0; +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SummaryManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SummaryManager.h new file mode 100644 index 0000000..ed87851 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SummaryManager.h @@ -0,0 +1,61 @@ +//== SummaryManager.h - Generic handling of function summaries --*- 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 SummaryManager and related classes, which provides +// a generic mechanism for managing function summaries. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_SUMMARY +#define LLVM_CLANG_GR_SUMMARY + +#include "llvm/ADT/FoldingSet.h" +#include "llvm/Support/Allocator.h" + +namespace clang { + +namespace ento { + +namespace summMgr { + + +/* Key kinds: + + - C functions + - C++ functions (name + parameter types) + - ObjC methods: + - Class, selector (class method) + - Class, selector (instance method) + - Category, selector (instance method) + - Protocol, selector (instance method) + - C++ methods + - Class, function name + parameter types + const + */ + +class SummaryKey { + +}; + +} // end namespace clang::summMgr + +class SummaryManagerImpl { + +}; + + +template <typename T> +class SummaryManager : SummaryManagerImpl { + +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h new file mode 100644 index 0000000..ad173bb --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -0,0 +1,489 @@ +//== SymbolManager.h - Management of Symbolic Values ------------*- 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 SymbolManager, a class that manages symbolic values +// created for use by ExprEngine and related classes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_SYMMGR_H +#define LLVM_CLANG_GR_SYMMGR_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" +#include "clang/Analysis/AnalysisContext.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/DenseSet.h" + +namespace llvm { +class BumpPtrAllocator; +class raw_ostream; +} + +namespace clang { + class ASTContext; + class StackFrameContext; + +namespace ento { + class BasicValueFactory; + class MemRegion; + class SubRegion; + class TypedRegion; + class VarRegion; + +class SymExpr : public llvm::FoldingSetNode { +public: + enum Kind { BEGIN_SYMBOLS, + RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, + MetadataKind, + END_SYMBOLS, + SymIntKind, SymSymKind }; +private: + Kind K; + +protected: + SymExpr(Kind k) : K(k) {} + +public: + virtual ~SymExpr() {} + + Kind getKind() const { return K; } + + void dump() const; + + virtual void dumpToStream(llvm::raw_ostream &os) const = 0; + + virtual QualType getType(ASTContext&) const = 0; + virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; + + // Implement isa<T> support. + static inline bool classof(const SymExpr*) { return true; } +}; + +typedef unsigned SymbolID; + +class SymbolData : public SymExpr { +private: + const SymbolID Sym; + +protected: + SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {} + +public: + virtual ~SymbolData() {} + + SymbolID getSymbolID() const { return Sym; } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + Kind k = SE->getKind(); + return k > BEGIN_SYMBOLS && k < END_SYMBOLS; + } +}; + +typedef const SymbolData* SymbolRef; + +// A symbol representing the value of a MemRegion. +class SymbolRegionValue : public SymbolData { + const TypedRegion *R; + +public: + SymbolRegionValue(SymbolID sym, const TypedRegion *r) + : SymbolData(RegionValueKind, sym), R(r) {} + + const TypedRegion* getRegion() const { return R; } + + static void Profile(llvm::FoldingSetNodeID& profile, const TypedRegion* R) { + profile.AddInteger((unsigned) RegionValueKind); + profile.AddPointer(R); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, R); + } + + void dumpToStream(llvm::raw_ostream &os) const; + + QualType getType(ASTContext&) const; + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == RegionValueKind; + } +}; + +// A symbol representing the result of an expression. +class SymbolConjured : public SymbolData { + const Stmt* S; + QualType T; + unsigned Count; + const void* SymbolTag; + +public: + 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; } + unsigned getCount() const { return Count; } + const void* getTag() const { return SymbolTag; } + + QualType getType(ASTContext&) const; + + void dumpToStream(llvm::raw_ostream &os) const; + + 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); + profile.AddInteger(Count); + profile.AddPointer(SymbolTag); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, S, T, Count, SymbolTag); + } + + // Implement isa<T> support. + 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. +class SymbolDerived : public SymbolData { + SymbolRef parentSymbol; + const TypedRegion *R; + +public: + SymbolDerived(SymbolID sym, SymbolRef parent, const TypedRegion *r) + : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} + + SymbolRef getParentSymbol() const { return parentSymbol; } + const TypedRegion *getRegion() const { return R; } + + QualType getType(ASTContext&) const; + + void dumpToStream(llvm::raw_ostream &os) const; + + static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, + const TypedRegion *r) { + profile.AddInteger((unsigned) DerivedKind); + profile.AddPointer(r); + profile.AddPointer(parent); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, parentSymbol, R); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == DerivedKind; + } +}; + +/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. +/// Clients should not ask the SymbolManager for a region's extent. Always use +/// SubRegion::getExtent instead -- the value returned may not be a symbol. +class SymbolExtent : public SymbolData { + const SubRegion *R; + +public: + SymbolExtent(SymbolID sym, const SubRegion *r) + : SymbolData(ExtentKind, sym), R(r) {} + + const SubRegion *getRegion() const { return R; } + + QualType getType(ASTContext&) const; + + void dumpToStream(llvm::raw_ostream &os) const; + + static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { + profile.AddInteger((unsigned) ExtentKind); + profile.AddPointer(R); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, R); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == ExtentKind; + } +}; + +/// SymbolMetadata - Represents path-dependent metadata about a specific region. +/// Metadata symbols remain live as long as they are marked as in use before +/// dead-symbol sweeping AND their associated regions are still alive. +/// Intended for use by checkers. +class SymbolMetadata : public SymbolData { + const MemRegion* R; + const Stmt* S; + QualType T; + unsigned Count; + const void* Tag; +public: + SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt* s, QualType t, + unsigned count, const void* tag) + : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} + + const MemRegion *getRegion() const { return R; } + const Stmt* getStmt() const { return S; } + unsigned getCount() const { return Count; } + const void* getTag() const { return Tag; } + + QualType getType(ASTContext&) const; + + void dumpToStream(llvm::raw_ostream &os) const; + + static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, + const Stmt *S, QualType T, unsigned Count, + const void *Tag) { + profile.AddInteger((unsigned) MetadataKind); + profile.AddPointer(R); + profile.AddPointer(S); + profile.Add(T); + profile.AddInteger(Count); + profile.AddPointer(Tag); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, R, S, T, Count, Tag); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == MetadataKind; + } +}; + +// SymIntExpr - Represents symbolic expression like 'x' + 3. +class SymIntExpr : public SymExpr { + const SymExpr *LHS; + BinaryOperator::Opcode Op; + const llvm::APSInt& RHS; + QualType T; + +public: + SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, + const llvm::APSInt& rhs, QualType t) + : SymExpr(SymIntKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} + + // FIXME: We probably need to make this out-of-line to avoid redundant + // generation of virtual functions. + QualType getType(ASTContext& C) const { return T; } + + BinaryOperator::Opcode getOpcode() const { return Op; } + + void dumpToStream(llvm::raw_ostream &os) const; + + const SymExpr *getLHS() const { return LHS; } + const llvm::APSInt &getRHS() const { return RHS; } + + static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, + BinaryOperator::Opcode op, const llvm::APSInt& rhs, + QualType t) { + ID.AddInteger((unsigned) SymIntKind); + ID.AddPointer(lhs); + ID.AddInteger(op); + ID.AddPointer(&rhs); + ID.Add(t); + } + + void Profile(llvm::FoldingSetNodeID& ID) { + Profile(ID, LHS, Op, RHS, T); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == SymIntKind; + } +}; + +// SymSymExpr - Represents symbolic expression like 'x' + 'y'. +class SymSymExpr : public SymExpr { + const SymExpr *LHS; + BinaryOperator::Opcode Op; + const SymExpr *RHS; + QualType T; + +public: + SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, + QualType t) + : SymExpr(SymSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} + + BinaryOperator::Opcode getOpcode() const { return Op; } + const SymExpr *getLHS() const { return LHS; } + const SymExpr *getRHS() const { return RHS; } + + // FIXME: We probably need to make this out-of-line to avoid redundant + // generation of virtual functions. + QualType getType(ASTContext& C) const { return T; } + + void dumpToStream(llvm::raw_ostream &os) const; + + static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, + BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { + ID.AddInteger((unsigned) SymSymKind); + ID.AddPointer(lhs); + ID.AddInteger(op); + ID.AddPointer(rhs); + ID.Add(t); + } + + void Profile(llvm::FoldingSetNodeID& ID) { + Profile(ID, LHS, Op, RHS, T); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == SymSymKind; + } +}; + +class SymbolManager { + typedef llvm::FoldingSet<SymExpr> DataSetTy; + DataSetTy DataSet; + unsigned SymbolCounter; + llvm::BumpPtrAllocator& BPAlloc; + BasicValueFactory &BV; + ASTContext& Ctx; + +public: + SymbolManager(ASTContext& ctx, BasicValueFactory &bv, + llvm::BumpPtrAllocator& bpalloc) + : 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); + + const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T, + 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 SymbolExtent *getExtentSymbol(const SubRegion *R); + + const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt* S, + QualType T, unsigned VisitCount, + const void* SymbolTag = 0); + + const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, + const llvm::APSInt& rhs, QualType t); + + const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, + const llvm::APSInt& rhs, QualType t) { + return getSymIntExpr(&lhs, op, rhs, t); + } + + const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, + const SymExpr *rhs, QualType t); + + QualType getType(const SymExpr *SE) const { + return SE->getType(Ctx); + } + + ASTContext &getContext() { return Ctx; } + BasicValueFactory &getBasicVals() { return BV; } +}; + +class SymbolReaper { + typedef llvm::DenseSet<SymbolRef> SetTy; + + SetTy TheLiving; + SetTy MetadataInUse; + SetTy TheDead; + const LocationContext *LCtx; + const Stmt *Loc; + SymbolManager& SymMgr; + +public: + SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr) + : LCtx(ctx), Loc(s), SymMgr(symmgr) {} + + ~SymbolReaper() {} + + const LocationContext *getLocationContext() const { return LCtx; } + const Stmt *getCurrentStatement() const { return Loc; } + + bool isLive(SymbolRef sym); + bool isLive(const Stmt *ExprVal) const; + bool isLive(const VarRegion *VR) const; + + // markLive - Unconditionally marks a symbol as live. This should never be + // used by checkers, only by the state infrastructure such as the store and + // environment. Checkers should instead use metadata symbols and markInUse. + void markLive(SymbolRef sym); + + // markInUse - Marks a symbol as important to a checker. For metadata symbols, + // this will keep the symbol alive as long as its associated region is also + // live. For other symbols, this has no effect; checkers are not permitted + // to influence the life of other symbols. This should be used before any + // symbol marking has occurred, i.e. in the MarkLiveSymbols callback. + void markInUse(SymbolRef sym); + + // maybeDead - If a symbol is known to be live, marks the symbol as live. + // Otherwise, if the symbol cannot be proven live, it is marked as dead. + // Returns true if the symbol is dead, false if live. + bool maybeDead(SymbolRef sym); + + typedef SetTy::const_iterator dead_iterator; + 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.) + bool isDead(SymbolRef sym) const { + return TheDead.count(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. + virtual bool VisitSymbol(SymbolRef sym) = 0; + virtual ~SymbolVisitor(); +}; + +} // end GR namespace + +} // end clang namespace + +namespace llvm { +static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, + const clang::ento::SymExpr *SE) { + SE->dumpToStream(os); + return os; +} +} // end llvm namespace +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h b/include/clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h new file mode 100644 index 0000000..23ed2be --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h @@ -0,0 +1,93 @@ +//== 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 new file mode 100644 index 0000000..6bc9fe5 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h @@ -0,0 +1,101 @@ +//==- WorkList.h - Worklist class used by CoreEngine ---------------*- 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 WorkList, a pure virtual class that represents an opaque +// worklist used by CoreEngine to explore the reachability state space. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_WORKLIST +#define LLVM_CLANG_GR_WORKLIST + +#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" +#include <cstddef> + +namespace clang { + +class CFGBlock; + +namespace ento { + +class ExplodedNode; +class ExplodedNodeImpl; + +class WorkListUnit { + ExplodedNode* node; + BlockCounter counter; + const CFGBlock* block; + unsigned blockIdx; // This is the index of the next statement. + +public: + WorkListUnit(ExplodedNode* N, BlockCounter C, + const CFGBlock* B, unsigned idx) + : node(N), + counter(C), + block(B), + blockIdx(idx) {} + + explicit WorkListUnit(ExplodedNode* N, BlockCounter C) + : node(N), + counter(C), + block(NULL), + blockIdx(0) {} + + /// Returns the node associated with the worklist unit. + ExplodedNode *getNode() const { return node; } + + /// Returns the block counter map associated with the worklist unit. + BlockCounter getBlockCounter() const { return counter; } + + /// Returns the CFGblock associated with the worklist unit. + const CFGBlock *getBlock() const { return block; } + + /// Return the index within the CFGBlock for the worklist unit. + unsigned getIndex() const { return blockIdx; } +}; + +class WorkList { + BlockCounter CurrentCounter; +public: + virtual ~WorkList(); + virtual bool hasWork() const = 0; + + virtual void enqueue(const WorkListUnit& U) = 0; + + void enqueue(ExplodedNode *N, const CFGBlock *B, unsigned idx) { + enqueue(WorkListUnit(N, CurrentCounter, B, idx)); + } + + void enqueue(ExplodedNode *N) { + enqueue(WorkListUnit(N, CurrentCounter)); + } + + virtual WorkListUnit dequeue() = 0; + + void setBlockCounter(BlockCounter C) { CurrentCounter = C; } + BlockCounter getBlockCounter() const { return CurrentCounter; } + + class Visitor { + public: + Visitor() {} + virtual ~Visitor(); + virtual bool visit(const WorkListUnit &U) = 0; + }; + virtual bool visitItemsInWorkList(Visitor &V) = 0; + + static WorkList *makeDFS(); + static WorkList *makeBFS(); + static WorkList *makeBFSBlockDFSContents(); +}; + +} // end GR namespace + +} // end clang namespace + +#endif diff --git a/include/clang/StaticAnalyzer/Frontend/CheckerRegistration.h b/include/clang/StaticAnalyzer/Frontend/CheckerRegistration.h new file mode 100644 index 0000000..4c3e379 --- /dev/null +++ b/include/clang/StaticAnalyzer/Frontend/CheckerRegistration.h @@ -0,0 +1,26 @@ +//===-- CheckerRegistration.h - Checker Registration Function-------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_SA_FRONTEND_CHECKERREGISTRATION_H +#define LLVM_CLANG_SA_FRONTEND_CHECKERREGISTRATION_H + +namespace clang { + class AnalyzerOptions; + class Diagnostic; + +namespace ento { + class CheckerManager; + +CheckerManager *registerCheckers(const AnalyzerOptions &opts,Diagnostic &diags); + +} // end ento namespace + +} // end namespace clang + +#endif diff --git a/include/clang/StaticAnalyzer/Frontend/FrontendActions.h b/include/clang/StaticAnalyzer/Frontend/FrontendActions.h new file mode 100644 index 0000000..e3867a2 --- /dev/null +++ b/include/clang/StaticAnalyzer/Frontend/FrontendActions.h @@ -0,0 +1,33 @@ +//===-- FrontendActions.h - Useful Frontend Actions -------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_FRONTENDACTIONS_H +#define LLVM_CLANG_GR_FRONTENDACTIONS_H + +#include "clang/Frontend/FrontendAction.h" + +namespace clang { + +namespace ento { + +//===----------------------------------------------------------------------===// +// AST Consumer Actions +//===----------------------------------------------------------------------===// + +class AnalysisAction : public ASTFrontendAction { +protected: + virtual ASTConsumer *CreateASTConsumer(CompilerInstance &CI, + llvm::StringRef InFile); +}; + +} // end GR namespace + +} // end namespace clang + +#endif |
