diff options
Diffstat (limited to 'include/clang/StaticAnalyzer')
32 files changed, 2164 insertions, 1406 deletions
diff --git a/include/clang/StaticAnalyzer/Checkers/CommonBugCategories.h b/include/clang/StaticAnalyzer/Checkers/CommonBugCategories.h new file mode 100644 index 0000000..9d4251b --- /dev/null +++ b/include/clang/StaticAnalyzer/Checkers/CommonBugCategories.h @@ -0,0 +1,24 @@ +//=--- CommonBugCategories.h - Provides common issue categories -*- 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_STATIC_ANALYZER_CHECKER_CATEGORIES_H +#define LLVM_CLANG_STATIC_ANALYZER_CHECKER_CATEGORIES_H + +// Common strings used for the "category" of many static analyzer issues. +namespace clang { + namespace ento { + namespace categories { + extern const char *CoreFoundationObjectiveC; + extern const char *MemoryCoreFoundationObjectiveC; + extern const char *UnixAPI; + } + } +} +#endif + diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h index bfb7ef8..2b699a8 100644 --- a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h +++ b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h @@ -20,10 +20,10 @@ #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/ImmutableList.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" #include "llvm/ADT/ImmutableSet.h" -#include "llvm/ADT/SmallSet.h" -#include <list> +#include "llvm/ADT/DenseSet.h" namespace clang { @@ -49,9 +49,10 @@ class BugType; /// This class provides an interface through which checkers can create /// individual bug reports. -class BugReport { -public: +class BugReport : public llvm::ilist_node<BugReport> { +public: class NodeResolver { + virtual void anchor(); public: virtual ~NodeResolver() {} virtual const ExplodedNode* @@ -59,7 +60,8 @@ public: }; typedef const SourceRange *ranges_iterator; - typedef llvm::ImmutableList<BugReporterVisitor*>::iterator visitor_iterator; + typedef SmallVector<BugReporterVisitor *, 8> VisitorList; + typedef VisitorList::iterator visitor_iterator; typedef SmallVector<StringRef, 2> ExtraTextList; protected: @@ -67,32 +69,65 @@ protected: friend class BugReportEquivClass; BugType& BT; + const Decl *DeclWithIssue; std::string ShortDescription; std::string Description; PathDiagnosticLocation Location; + PathDiagnosticLocation UniqueingLocation; const ExplodedNode *ErrorNode; SmallVector<SourceRange, 4> Ranges; ExtraTextList ExtraText; + + typedef llvm::DenseSet<SymbolRef> Symbols; + typedef llvm::DenseSet<const MemRegion *> Regions; + + /// A set of symbols that are registered with this report as being + /// "interesting", and thus used to help decide which diagnostics + /// to include when constructing the final path diagnostic. + Symbols interestingSymbols; + + /// A set of regions that are registered with this report as being + /// "interesting", and thus used to help decide which diagnostics + /// to include when constructing the final path diagnostic. + Regions interestingRegions; - // 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; + /// A set of custom visitors which generate "event" diagnostics at + /// interesting points in the path. + VisitorList Callbacks; + + /// Used for ensuring the visitors are only added once. llvm::FoldingSet<BugReporterVisitor> CallbacksSet; + /// Used for clients to tell if the report's configuration has changed + /// since the last time they checked. + unsigned ConfigurationChangeToken; + public: BugReport(BugType& bt, StringRef desc, const ExplodedNode *errornode) - : BT(bt), Description(desc), ErrorNode(errornode), - Callbacks(F.getEmptyList()) {} + : BT(bt), DeclWithIssue(0), Description(desc), ErrorNode(errornode), + ConfigurationChangeToken(0) {} BugReport(BugType& bt, StringRef shortDesc, StringRef desc, const ExplodedNode *errornode) - : BT(bt), ShortDescription(shortDesc), Description(desc), - ErrorNode(errornode), Callbacks(F.getEmptyList()) {} + : BT(bt), DeclWithIssue(0), ShortDescription(shortDesc), Description(desc), + ErrorNode(errornode), ConfigurationChangeToken(0) {} BugReport(BugType& bt, StringRef desc, PathDiagnosticLocation l) - : BT(bt), Description(desc), Location(l), ErrorNode(0), - Callbacks(F.getEmptyList()) {} + : BT(bt), DeclWithIssue(0), Description(desc), Location(l), ErrorNode(0), + ConfigurationChangeToken(0) {} + + /// \brief Create a BugReport with a custom uniqueing location. + /// + /// The reports that have the same report location, description, bug type, and + /// ranges are uniqued - only one of the equivalent reports will be presented + /// to the user. This method allows to rest the location which should be used + /// for uniquing reports. For example, memory leaks checker, could set this to + /// the allocation site, rather then the location where the bug is reported. + BugReport(BugType& bt, StringRef desc, const ExplodedNode *errornode, + PathDiagnosticLocation LocationToUnique) + : BT(bt), DeclWithIssue(0), Description(desc), + UniqueingLocation(LocationToUnique), + ErrorNode(errornode), ConfigurationChangeToken(0) {} virtual ~BugReport(); @@ -107,6 +142,28 @@ public: return ShortDescription.empty() ? Description : ShortDescription; } + void markInteresting(SymbolRef sym); + void markInteresting(const MemRegion *R); + void markInteresting(SVal V); + + bool isInteresting(SymbolRef sym) const; + bool isInteresting(const MemRegion *R) const; + bool isInteresting(SVal V) const; + + unsigned getConfigurationChangeToken() const { + return ConfigurationChangeToken; + } + + /// Return the canonical declaration, be it a method or class, where + /// this issue semantically occurred. + const Decl *getDeclWithIssue() const; + + /// Specifically set the Decl where an issue occurred. This isn't necessary + /// for BugReports that cover a path as it will be automatically inferred. + void setDeclWithIssue(const Decl *declWithIssue) { + DeclWithIssue = declWithIssue; + } + /// \brief This allows for addition of meta data to the diagnostic. /// /// Currently, only the HTMLDiagnosticClient knows how to display it. @@ -162,13 +219,38 @@ public: virtual void Profile(llvm::FoldingSetNodeID& hash) const; }; +} // end ento namespace +} // end clang namespace + +namespace llvm { + template<> struct ilist_traits<clang::ento::BugReport> + : public ilist_default_traits<clang::ento::BugReport> { + clang::ento::BugReport *createSentinel() const { + return static_cast<clang::ento::BugReport *>(&Sentinel); + } + void destroySentinel(clang::ento::BugReport *) const {} + + clang::ento::BugReport *provideInitialHead() const { + return createSentinel(); + } + clang::ento::BugReport *ensureHead(clang::ento::BugReport *) const { + return createSentinel(); + } + private: + mutable ilist_half_node<clang::ento::BugReport> Sentinel; + }; +} + +namespace clang { +namespace ento { + //===----------------------------------------------------------------------===// // BugTypes (collections of related reports). //===----------------------------------------------------------------------===// class BugReportEquivClass : public llvm::FoldingSetNode { /// List of *owned* BugReport objects. - std::list<BugReport*> Reports; + llvm::ilist<BugReport> Reports; friend class BugReporter; void AddReport(BugReport* R) { Reports.push_back(R); } @@ -178,36 +260,17 @@ public: void Profile(llvm::FoldingSetNodeID& ID) const { assert(!Reports.empty()); - (*Reports.begin())->Profile(ID); + Reports.front().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; } - }; + typedef llvm::ilist<BugReport>::iterator iterator; + typedef llvm::ilist<BugReport>::const_iterator const_iterator; - 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()); } + iterator begin() { return Reports.begin(); } + iterator end() { return Reports.end(); } - const_iterator begin() const { return const_iterator(Reports.begin()); } - const_iterator end() const { return const_iterator(Reports.end()); } + const_iterator begin() const { return Reports.begin(); } + const_iterator end() const { return Reports.end(); } }; //===----------------------------------------------------------------------===// @@ -294,34 +357,22 @@ public: /// reports. void EmitReport(BugReport *R); - void EmitBasicReport(StringRef BugName, StringRef BugStr, - PathDiagnosticLocation Loc, - SourceRange* RangeBeg, unsigned NumRanges); - - void EmitBasicReport(StringRef BugName, StringRef BugCategory, + void EmitBasicReport(const Decl *DeclWithIssue, + StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc, SourceRange* RangeBeg, unsigned NumRanges); - - void EmitBasicReport(StringRef BugName, StringRef BugStr, - PathDiagnosticLocation Loc) { - EmitBasicReport(BugName, BugStr, Loc, 0, 0); - } - - void EmitBasicReport(StringRef BugName, StringRef BugCategory, + void EmitBasicReport(const Decl *DeclWithIssue, + StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc) { - EmitBasicReport(BugName, BugCategory, BugStr, Loc, 0, 0); - } - - void EmitBasicReport(StringRef BugName, StringRef BugStr, - PathDiagnosticLocation Loc, SourceRange R) { - EmitBasicReport(BugName, BugStr, Loc, &R, 1); + EmitBasicReport(DeclWithIssue, BugName, BugCategory, BugStr, Loc, 0, 0); } - void EmitBasicReport(StringRef BugName, StringRef Category, + void EmitBasicReport(const Decl *DeclWithIssue, + StringRef BugName, StringRef Category, StringRef BugStr, PathDiagnosticLocation Loc, SourceRange R) { - EmitBasicReport(BugName, Category, BugStr, Loc, &R, 1); + EmitBasicReport(DeclWithIssue, BugName, Category, BugStr, Loc, &R, 1); } static bool classof(const BugReporter* R) { return true; } @@ -337,7 +388,6 @@ private: // 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) {} @@ -359,14 +409,6 @@ public: virtual void GeneratePathDiagnostic(PathDiagnostic &pathDiagnostic, 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; @@ -374,6 +416,7 @@ public: }; class BugReporterContext { + virtual void anchor(); GRBugReporter &BR; public: BugReporterContext(GRBugReporter& br) : BR(br) {} @@ -384,16 +427,6 @@ public: 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); - } - ProgramStateManager& getStateManager() { return BR.getStateManager(); } diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitor.h b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitor.h index 41c0a3a..7e665ce 100644 --- a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitor.h +++ b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitor.h @@ -28,10 +28,28 @@ class ExplodedNode; class MemRegion; class PathDiagnosticPiece; +/// \brief BugReporterVisitors are used to add custom diagnostics along a path. +/// +/// Custom visitors should subclass the BugReporterVisitorImpl class for a +/// default implementation of the clone() method. +/// (Warning: if you have a deep subclass of BugReporterVisitorImpl, the +/// default implementation of clone() will NOT do the right thing, and you +/// will have to provide your own implementation.) class BugReporterVisitor : public llvm::FoldingSetNode { public: virtual ~BugReporterVisitor(); + /// \brief Returns a copy of this BugReporter. + /// + /// Custom BugReporterVisitors should not override this method directly. + /// Instead, they should inherit from BugReporterVisitorImpl and provide + /// a protected or public copy constructor. + /// + /// (Warning: if you have a deep subclass of BugReporterVisitorImpl, the + /// default implementation of clone() will NOT do the right thing, and you + /// will have to provide your own implementation.) + virtual BugReporterVisitor *clone() const = 0; + /// \brief Return a diagnostic piece which should be associated with the /// given node. /// @@ -61,7 +79,24 @@ public: }; -class FindLastStoreBRVisitor : public BugReporterVisitor { +/// This class provides a convenience implementation for clone() using the +/// Curiously-Recurring Template Pattern. If you are implementing a custom +/// BugReporterVisitor, subclass BugReporterVisitorImpl and provide a public +/// or protected copy constructor. +/// +/// (Warning: if you have a deep subclass of BugReporterVisitorImpl, the +/// default implementation of clone() will NOT do the right thing, and you +/// will have to provide your own implementation.) +template <class DERIVED> +class BugReporterVisitorImpl : public BugReporterVisitor { + virtual BugReporterVisitor *clone() const { + return new DERIVED(*static_cast<const DERIVED *>(this)); + } +}; + +class FindLastStoreBRVisitor + : public BugReporterVisitorImpl<FindLastStoreBRVisitor> +{ const MemRegion *R; SVal V; bool satisfied; @@ -94,7 +129,9 @@ public: BugReport &BR); }; -class TrackConstraintBRVisitor : public BugReporterVisitor { +class TrackConstraintBRVisitor + : public BugReporterVisitorImpl<TrackConstraintBRVisitor> +{ DefinedSVal Constraint; const bool Assumption; bool isSatisfied; @@ -111,7 +148,9 @@ public: BugReport &BR); }; -class NilReceiverBRVisitor : public BugReporterVisitor { +class NilReceiverBRVisitor + : public BugReporterVisitorImpl<NilReceiverBRVisitor> +{ public: void Profile(llvm::FoldingSetNodeID &ID) const { static int x = 0; @@ -125,50 +164,71 @@ public: }; /// Visitor that tries to report interesting diagnostics from conditions. -class ConditionBRVisitor : public BugReporterVisitor { +class ConditionBRVisitor : public BugReporterVisitorImpl<ConditionBRVisitor> { public: void Profile(llvm::FoldingSetNodeID &ID) const { static int x = 0; ID.AddPointer(&x); } + virtual PathDiagnosticPiece *VisitNode(const ExplodedNode *N, const ExplodedNode *Prev, BugReporterContext &BRC, BugReport &BR); + PathDiagnosticPiece *VisitNodeImpl(const ExplodedNode *N, + const ExplodedNode *Prev, + BugReporterContext &BRC, + BugReport &BR); + PathDiagnosticPiece *VisitTerminator(const Stmt *Term, const ExplodedNode *N, const CFGBlock *srcBlk, const CFGBlock *dstBlk, + BugReport &R, BugReporterContext &BRC); PathDiagnosticPiece *VisitTrueTest(const Expr *Cond, bool tookTrue, BugReporterContext &BRC, - const LocationContext *LC); + BugReport &R, + const ExplodedNode *N); PathDiagnosticPiece *VisitTrueTest(const Expr *Cond, const DeclRefExpr *DR, const bool tookTrue, BugReporterContext &BRC, - const LocationContext *LC); + BugReport &R, + const ExplodedNode *N); PathDiagnosticPiece *VisitTrueTest(const Expr *Cond, const BinaryOperator *BExpr, const bool tookTrue, BugReporterContext &BRC, - const LocationContext *LC); + BugReport &R, + const ExplodedNode *N); + + PathDiagnosticPiece *VisitConditionVariable(StringRef LhsString, + const Expr *CondVarExpr, + const bool tookTrue, + BugReporterContext &BRC, + BugReport &R, + const ExplodedNode *N); bool patternMatch(const Expr *Ex, llvm::raw_ostream &Out, - BugReporterContext &BRC); + BugReporterContext &BRC, + BugReport &R, + const ExplodedNode *N, + llvm::Optional<bool> &prunable); }; - + namespace bugreporter { BugReporterVisitor *getTrackNullOrUndefValueVisitor(const ExplodedNode *N, - const Stmt *S); + const Stmt *S, + BugReport *R); const Stmt *GetDerefExpr(const ExplodedNode *N); const Stmt *GetDenomExpr(const ExplodedNode *N); diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h b/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h index 78067cd..cb49122 100644 --- a/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h +++ b/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h @@ -49,6 +49,7 @@ public: }; class BuiltinBug : public BugType { + virtual void anchor(); const std::string desc; public: BuiltinBug(const char *name, const char *description) diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h index 406be3c..5a8a1c7 100644 --- a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h +++ b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h @@ -14,9 +14,12 @@ #ifndef LLVM_CLANG_PATH_DIAGNOSTIC_H #define LLVM_CLANG_PATH_DIAGNOSTIC_H -#include "clang/Basic/Diagnostic.h" +#include "clang/Basic/SourceLocation.h" +#include "clang/Analysis/ProgramPoint.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/IntrusiveRefCntPtr.h" #include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/Optional.h" #include <deque> #include <iterator> #include <string> @@ -24,7 +27,7 @@ namespace clang { -class AnalysisContext; +class AnalysisDeclContext; class BinaryOperator; class CompoundStmt; class Decl; @@ -38,6 +41,8 @@ class Stmt; namespace ento { class ExplodedNode; +class SymExpr; +typedef const SymExpr* SymbolRef; //===----------------------------------------------------------------------===// // High-level interface for handlers of path-sensitive diagnostics. @@ -46,33 +51,34 @@ class ExplodedNode; class PathDiagnostic; class PathDiagnosticConsumer { + virtual void anchor(); public: - PathDiagnosticConsumer() {} + PathDiagnosticConsumer() : flushed(false) {} + virtual ~PathDiagnosticConsumer(); + + void FlushDiagnostics(SmallVectorImpl<std::string> *FilesMade); + + virtual void FlushDiagnosticsImpl(std::vector<const PathDiagnostic *> &Diags, + SmallVectorImpl<std::string> *FilesMade) + = 0; - virtual ~PathDiagnosticConsumer() {} - - virtual void - FlushDiagnostics(SmallVectorImpl<std::string> *FilesMade = 0) = 0; - - void FlushDiagnostics(SmallVectorImpl<std::string> &FilesMade) { - FlushDiagnostics(&FilesMade); - } - virtual StringRef getName() const = 0; - void HandlePathDiagnostic(const PathDiagnostic* D); + void HandlePathDiagnostic(PathDiagnostic *D); 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; } + + /// Return true if the PathDiagnosticConsumer supports individual + /// PathDiagnostics that span multiple files. + virtual bool supportsCrossFileDiagnostics() const { return false; } protected: - /// The actual logic for handling path diagnostics, as implemented - /// by subclasses of PathDiagnosticConsumer. - virtual void HandlePathDiagnosticImpl(const PathDiagnostic* D) = 0; - + bool flushed; + llvm::FoldingSet<PathDiagnostic> Diags; }; //===----------------------------------------------------------------------===// @@ -89,8 +95,8 @@ public: PathDiagnosticRange() : isPoint(false) {} }; -typedef llvm::PointerUnion<const LocationContext*, AnalysisContext*> - LocationOrAnalysisContext; +typedef llvm::PointerUnion<const LocationContext*, AnalysisDeclContext*> + LocationOrAnalysisDeclContext; class PathDiagnosticLocation { private: @@ -111,10 +117,10 @@ private: FullSourceLoc genLocation(SourceLocation L = SourceLocation(), - LocationOrAnalysisContext LAC = (AnalysisContext*)0) const; + LocationOrAnalysisDeclContext LAC = (AnalysisDeclContext*)0) const; PathDiagnosticRange - genRange(LocationOrAnalysisContext LAC = (AnalysisContext*)0) const; + genRange(LocationOrAnalysisDeclContext LAC = (AnalysisDeclContext*)0) const; public: /// Create an invalid location. @@ -124,10 +130,11 @@ public: /// Create a location corresponding to the given statement. PathDiagnosticLocation(const Stmt *s, const SourceManager &sm, - LocationOrAnalysisContext lac) + LocationOrAnalysisDeclContext lac) : K(StmtK), S(s), D(0), SM(&sm), Loc(genLocation(SourceLocation(), lac)), Range(genRange(lac)) { + assert(S); assert(Loc.isValid()); assert(Range.isValid()); } @@ -136,6 +143,7 @@ public: PathDiagnosticLocation(const Decl *d, const SourceManager &sm) : K(DeclK), S(0), D(d), SM(&sm), Loc(genLocation()), Range(genRange()) { + assert(D); assert(Loc.isValid()); assert(Range.isValid()); } @@ -153,7 +161,7 @@ public: /// Create a location for the beginning of the statement. static PathDiagnosticLocation createBegin(const Stmt *S, const SourceManager &SM, - const LocationOrAnalysisContext LAC); + const LocationOrAnalysisDeclContext LAC); /// Create the location for the operator of the binary expression. /// Assumes the statement has a valid location. @@ -260,14 +268,13 @@ public: // Path "pieces" for path-sensitive diagnostics. //===----------------------------------------------------------------------===// -class PathDiagnosticPiece { +class PathDiagnosticPiece : public RefCountedBaseVPTR { public: - enum Kind { ControlFlow, Event, Macro }; + enum Kind { ControlFlow, Event, Macro, Call }; enum DisplayHint { Above, Below }; private: const std::string str; - std::vector<FixItHint> FixItHints; const Kind kind; const DisplayHint Hint; std::vector<SourceRange> ranges; @@ -308,10 +315,6 @@ public: 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 { @@ -322,23 +325,19 @@ public: 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 PathPieces : + public std::deque<IntrusiveRefCntPtr<PathDiagnosticPiece> > { +public: + ~PathPieces(); +}; class PathDiagnosticSpotPiece : public PathDiagnosticPiece { private: @@ -360,20 +359,170 @@ public: virtual void Profile(llvm::FoldingSetNodeID &ID) const; }; +/// \brief Interface for classes constructing Stack hints. +/// +/// If a PathDiagnosticEvent occurs in a different frame than the final +/// diagnostic the hints can be used to summarise the effect of the call. +class StackHintGenerator { +public: + virtual ~StackHintGenerator() = 0; + + /// \brief Construct the Diagnostic message for the given ExplodedNode. + virtual std::string getMessage(const ExplodedNode *N) = 0; +}; + +/// \brief Constructs a Stack hint for the given symbol. +/// +/// The class knows how to construct the stack hint message based on +/// traversing the CallExpr associated with the call and checking if the given +/// symbol is returned or is one of the arguments. +/// The hint can be customized by redefining 'getMessageForX()' methods. +class StackHintGeneratorForSymbol : public StackHintGenerator { +private: + SymbolRef Sym; + std::string Msg; + +public: + StackHintGeneratorForSymbol(SymbolRef S, StringRef M) : Sym(S), Msg(M) {} + virtual ~StackHintGeneratorForSymbol() {} + + /// \brief Search the call expression for the symbol Sym and dispatch the + /// 'getMessageForX()' methods to construct a specific message. + virtual std::string getMessage(const ExplodedNode *N); + + /// Prints the ordinal form of the given integer, + /// only valid for ValNo : ValNo > 0. + void printOrdinal(unsigned ValNo, llvm::raw_svector_ostream &Out); + + /// Produces the message of the following form: + /// 'Msg via Nth parameter' + virtual std::string getMessageForArg(const Expr *ArgE, unsigned ArgIndex); + virtual std::string getMessageForReturn(const CallExpr *CallExpr) { + return Msg; + } + virtual std::string getMessageForSymbolNotFound() { + return Msg; + } +}; + class PathDiagnosticEventPiece : public PathDiagnosticSpotPiece { + llvm::Optional<bool> IsPrunable; + + /// If the event occurs in a different frame than the final diagnostic, + /// supply a message that will be used to construct an extra hint on the + /// returns from all the calls on the stack from this event to the final + /// diagnostic. + llvm::OwningPtr<StackHintGenerator> CallStackHint; public: PathDiagnosticEventPiece(const PathDiagnosticLocation &pos, - StringRef s, bool addPosRange = true) - : PathDiagnosticSpotPiece(pos, s, Event, addPosRange) {} + StringRef s, bool addPosRange = true, + StackHintGenerator *stackHint = 0) + : PathDiagnosticSpotPiece(pos, s, Event, addPosRange), + CallStackHint(stackHint) {} ~PathDiagnosticEventPiece(); + /// Mark the diagnostic piece as being potentially prunable. This + /// flag may have been previously set, at which point it will not + /// be reset unless one specifies to do so. + void setPrunable(bool isPrunable, bool override = false) { + if (IsPrunable.hasValue() && !override) + return; + IsPrunable = isPrunable; + } + + /// Return true if the diagnostic piece is prunable. + bool isPrunable() const { + return IsPrunable.hasValue() ? IsPrunable.getValue() : false; + } + + bool hasCallStackHint() { + return (CallStackHint != 0); + } + + /// Produce the hint for the given node. The node contains + /// information about the call for which the diagnostic can be generated. + std::string getCallStackMessage(const ExplodedNode *N) { + if (CallStackHint) + return CallStackHint->getMessage(N); + return ""; + } + static inline bool classof(const PathDiagnosticPiece *P) { return P->getKind() == Event; } }; +class PathDiagnosticCallPiece : public PathDiagnosticPiece { + PathDiagnosticCallPiece(const Decl *callerD, + const PathDiagnosticLocation &callReturnPos) + : PathDiagnosticPiece(Call), Caller(callerD), Callee(0), + NoExit(false), callReturn(callReturnPos) {} + + PathDiagnosticCallPiece(PathPieces &oldPath, const Decl *caller) + : PathDiagnosticPiece(Call), Caller(caller), Callee(0), + NoExit(true), path(oldPath) {} + + const Decl *Caller; + const Decl *Callee; + + // Flag signifying that this diagnostic has only call enter and no matching + // call exit. + bool NoExit; + + // The custom string, which should appear after the call Return Diagnostic. + // TODO: Should we allow multiple diagnostics? + std::string CallStackMessage; + +public: + PathDiagnosticLocation callEnter; + PathDiagnosticLocation callEnterWithin; + PathDiagnosticLocation callReturn; + PathPieces path; + + virtual ~PathDiagnosticCallPiece(); + + const Decl *getCaller() const { return Caller; } + + const Decl *getCallee() const { return Callee; } + void setCallee(const CallEnter &CE, const SourceManager &SM); + + bool hasCallStackMessage() { return !CallStackMessage.empty(); } + void setCallStackMessage(StringRef st) { + CallStackMessage = st; + } + + virtual PathDiagnosticLocation getLocation() const { + return callEnter; + } + + IntrusiveRefCntPtr<PathDiagnosticEventPiece> getCallEnterEvent() const; + IntrusiveRefCntPtr<PathDiagnosticEventPiece> + getCallEnterWithinCallerEvent() const; + IntrusiveRefCntPtr<PathDiagnosticEventPiece> getCallExitEvent() const; + + virtual void flattenLocations() { + callEnter.flatten(); + callReturn.flatten(); + for (PathPieces::iterator I = path.begin(), + E = path.end(); I != E; ++I) (*I)->flattenLocations(); + } + + static PathDiagnosticCallPiece *construct(const ExplodedNode *N, + const CallExit &CE, + const SourceManager &SM); + + static PathDiagnosticCallPiece *construct(PathPieces &pieces, + const Decl *caller); + + virtual void Profile(llvm::FoldingSetNodeID &ID) const; + + static inline bool classof(const PathDiagnosticPiece *P) { + return P->getKind() == Call; + } +}; + class PathDiagnosticControlFlowPiece : public PathDiagnosticPiece { std::vector<PathDiagnosticLocationPair> LPairs; public: @@ -431,30 +580,22 @@ public: }; class PathDiagnosticMacroPiece : public PathDiagnosticSpotPiece { - std::vector<PathDiagnosticPiece*> SubPieces; public: PathDiagnosticMacroPiece(const PathDiagnosticLocation &pos) : PathDiagnosticSpotPiece(pos, "", Macro) {} ~PathDiagnosticMacroPiece(); + PathPieces subPieces; + 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(); + for (PathPieces::iterator I = subPieces.begin(), + E = subPieces.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; } @@ -466,17 +607,41 @@ public: /// 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; + const Decl *DeclWithIssue; std::string BugType; std::string Desc; std::string Category; std::deque<std::string> OtherDesc; - + PathPieces pathImpl; + llvm::SmallVector<PathPieces *, 3> pathStack; + + PathDiagnostic(); // Do not implement. public: - PathDiagnostic(); + const PathPieces &path; + + /// Return the path currently used by builders for constructing the + /// PathDiagnostic. + PathPieces &getActivePath() { + if (pathStack.empty()) + return pathImpl; + return *pathStack.back(); + } + + /// Return a mutable version of 'path'. + PathPieces &getMutablePieces() { + return pathImpl; + } + + /// Return the unrolled size of the path. + unsigned full_size(); - PathDiagnostic(StringRef bugtype, StringRef desc, + void pushActivePath(PathPieces *p) { pathStack.push_back(p); } + void popActivePath() { if (!pathStack.empty()) pathStack.pop_back(); } + + // PathDiagnostic(); + PathDiagnostic(const Decl *DeclWithIssue, + StringRef bugtype, + StringRef desc, StringRef category); ~PathDiagnostic(); @@ -485,115 +650,26 @@ public: StringRef getBugType() const { return BugType; } StringRef getCategory() const { return Category; } + /// Return the semantic context where an issue occurred. If the + /// issue occurs along a path, this represents the "central" area + /// where the bug manifests. + const Decl *getDeclWithIssue() const { return DeclWithIssue; } + 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(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());} + PathDiagnosticLocation getLocation() const; void flattenLocations() { - for (iterator I = begin(), E = end(); I != E; ++I) I->flattenLocations(); + for (PathPieces::iterator I = pathImpl.begin(), E = pathImpl.end(); + I != E; ++I) (*I)->flattenLocations(); } void Profile(llvm::FoldingSetNodeID &ID) const; + + void FullProfile(llvm::FoldingSetNodeID &ID) const; }; } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/Checker.h b/include/clang/StaticAnalyzer/Core/Checker.h index 1e4edeb..76d8c15 100644 --- a/include/clang/StaticAnalyzer/Core/Checker.h +++ b/include/clang/StaticAnalyzer/Core/Checker.h @@ -199,9 +199,9 @@ public: class EndPath { template <typename CHECKER> - static void _checkEndPath(void *checker, EndOfFunctionNodeBuilder &B, - ExprEngine &Eng) { - ((const CHECKER *)checker)->checkEndPath(B, Eng); + static void _checkEndPath(void *checker, + CheckerContext &C) { + ((const CHECKER *)checker)->checkEndPath(C); } public: @@ -214,9 +214,9 @@ public: class BranchCondition { template <typename CHECKER> - static void _checkBranchCondition(void *checker, const Stmt *condition, - BranchNodeBuilder &B, ExprEngine &Eng) { - ((const CHECKER *)checker)->checkBranchCondition(condition, B, Eng); + static void _checkBranchCondition(void *checker, const Stmt *Condition, + CheckerContext & C) { + ((const CHECKER *)checker)->checkBranchCondition(Condition, C); } public: @@ -230,7 +230,7 @@ public: class LiveSymbols { template <typename CHECKER> - static void _checkLiveSymbols(void *checker, const ProgramState *state, + static void _checkLiveSymbols(void *checker, ProgramStateRef state, SymbolReaper &SR) { ((const CHECKER *)checker)->checkLiveSymbols(state, SR); } @@ -260,18 +260,19 @@ public: class RegionChanges { template <typename CHECKER> - static const ProgramState * + static ProgramStateRef _checkRegionChanges(void *checker, - const ProgramState *state, + ProgramStateRef state, const StoreManager::InvalidatedSymbols *invalidated, ArrayRef<const MemRegion *> Explicits, - ArrayRef<const MemRegion *> Regions) { + ArrayRef<const MemRegion *> Regions, + const CallOrObjCMessage *Call) { return ((const CHECKER *)checker)->checkRegionChanges(state, invalidated, - Explicits, Regions); + Explicits, Regions, Call); } template <typename CHECKER> static bool _wantsRegionChangeUpdate(void *checker, - const ProgramState *state) { + ProgramStateRef state) { return ((const CHECKER *)checker)->wantsRegionChangeUpdate(state); } @@ -306,8 +307,8 @@ namespace eval { class Assume { template <typename CHECKER> - static const ProgramState *_evalAssume(void *checker, - const ProgramState *state, + static ProgramStateRef _evalAssume(void *checker, + ProgramStateRef state, const SVal &cond, bool assumption) { return ((const CHECKER *)checker)->evalAssume(state, cond, assumption); @@ -359,7 +360,7 @@ public: StringRef getTagDescription() const; /// See CheckerManager::runCheckersForPrintState. - virtual void printState(raw_ostream &Out, const ProgramState *State, + virtual void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const { } }; @@ -370,7 +371,8 @@ template <typename CHECK1, typename CHECK2=check::_VoidCheck, typename CHECK9=check::_VoidCheck, typename CHECK10=check::_VoidCheck, typename CHECK11=check::_VoidCheck,typename CHECK12=check::_VoidCheck, typename CHECK13=check::_VoidCheck,typename CHECK14=check::_VoidCheck, - typename CHECK15=check::_VoidCheck,typename CHECK16=check::_VoidCheck> + typename CHECK15=check::_VoidCheck,typename CHECK16=check::_VoidCheck, + typename CHECK17=check::_VoidCheck,typename CHECK18=check::_VoidCheck> class Checker; template <> @@ -379,9 +381,10 @@ class Checker<check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, check::_VoidCheck, - check::_VoidCheck> + check::_VoidCheck, check::_VoidCheck, check::_VoidCheck> : public CheckerBase { + virtual void anchor(); public: static void _register(void *checker, CheckerManager &mgr) { } }; @@ -389,19 +392,20 @@ public: template <typename CHECK1, typename CHECK2, typename CHECK3, typename CHECK4, typename CHECK5, typename CHECK6, typename CHECK7, typename CHECK8, typename CHECK9, typename CHECK10,typename CHECK11,typename CHECK12, - typename CHECK13,typename CHECK14,typename CHECK15,typename CHECK16> + typename CHECK13,typename CHECK14,typename CHECK15,typename CHECK16, + typename CHECK17,typename CHECK18> class Checker : public CHECK1, public Checker<CHECK2, CHECK3, CHECK4, CHECK5, CHECK6, CHECK7, CHECK8, CHECK9, CHECK10,CHECK11,CHECK12,CHECK13,CHECK14,CHECK15, - CHECK16> { + CHECK16,CHECK17,CHECK18> { public: template <typename CHECKER> static void _register(CHECKER *checker, CheckerManager &mgr) { CHECK1::_register(checker, mgr); Checker<CHECK2, CHECK3, CHECK4, CHECK5, CHECK6, CHECK7, CHECK8, CHECK9, CHECK10,CHECK11,CHECK12,CHECK13,CHECK14,CHECK15, - CHECK16>::_register(checker, mgr); + CHECK16,CHECK17,CHECK18>::_register(checker, mgr); } }; diff --git a/include/clang/StaticAnalyzer/Core/CheckerManager.h b/include/clang/StaticAnalyzer/Core/CheckerManager.h index e3e4c49..d215f99 100644 --- a/include/clang/StaticAnalyzer/Core/CheckerManager.h +++ b/include/clang/StaticAnalyzer/Core/CheckerManager.h @@ -19,6 +19,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" +#include "clang/Analysis/ProgramPoint.h" #include <vector> namespace clang { @@ -38,8 +39,8 @@ namespace ento { class ExplodedNodeSet; class ExplodedGraph; class ProgramState; - class EndOfFunctionNodeBuilder; - class BranchNodeBuilder; + class NodeBuilder; + struct NodeBuilderContext; class MemRegion; class SymbolReaper; @@ -51,6 +52,19 @@ public: template <typename T> class CheckerFn; +template <typename RET, typename P1, typename P2, typename P3, typename P4, + typename P5> +class CheckerFn<RET(P1, P2, P3, P4, P5)> { + typedef RET (*Func)(void *, P1, P2, P3, P4, P5); + Func Fn; +public: + CheckerBase *Checker; + CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { } + RET operator()(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) const { + return Fn(Checker, p1, p2, p3, p4, p5); + } +}; + template <typename RET, typename P1, typename P2, typename P3, typename P4> class CheckerFn<RET(P1, P2, P3, P4)> { typedef RET (*Func)(void *, P1, P2, P3, P4); @@ -114,7 +128,7 @@ public: void finishedCheckerRegistration(); - const LangOptions &getLangOptions() const { return LangOpts; } + const LangOptions &getLangOpts() const { return LangOpts; } typedef CheckerBase *CheckerRef; typedef const void *CheckerTag; @@ -179,14 +193,16 @@ public: void runCheckersForPostStmt(ExplodedNodeSet &Dst, const ExplodedNodeSet &Src, const Stmt *S, - ExprEngine &Eng) { - runCheckersForStmt(/*isPreVisit=*/false, Dst, Src, S, Eng); + ExprEngine &Eng, + bool wasInlined = false) { + runCheckersForStmt(/*isPreVisit=*/false, Dst, Src, S, Eng, wasInlined); } /// \brief Run checkers for visiting Stmts. void runCheckersForStmt(bool isPreVisit, ExplodedNodeSet &Dst, const ExplodedNodeSet &Src, - const Stmt *S, ExprEngine &Eng); + const Stmt *S, ExprEngine &Eng, + bool wasInlined = false); /// \brief Run checkers for pre-visiting obj-c messages. void runCheckersForPreObjCMessage(ExplodedNodeSet &Dst, @@ -213,33 +229,39 @@ public: /// \brief Run checkers for load/store of a location. void runCheckersForLocation(ExplodedNodeSet &Dst, const ExplodedNodeSet &Src, - SVal location, bool isLoad, - const Stmt *S, + SVal location, + bool isLoad, + const Stmt *NodeEx, + const Stmt *BoundEx, ExprEngine &Eng); /// \brief Run checkers for binding of a value to a location. void runCheckersForBind(ExplodedNodeSet &Dst, const ExplodedNodeSet &Src, SVal location, SVal val, - const Stmt *S, ExprEngine &Eng); + const Stmt *S, ExprEngine &Eng, + ProgramPoint::Kind PointKind); /// \brief Run checkers for end of analysis. void runCheckersForEndAnalysis(ExplodedGraph &G, BugReporter &BR, ExprEngine &Eng); /// \brief Run checkers for end of path. - void runCheckersForEndPath(EndOfFunctionNodeBuilder &B, ExprEngine &Eng); + void runCheckersForEndPath(NodeBuilderContext &BC, + ExplodedNodeSet &Dst, + ExprEngine &Eng); /// \brief Run checkers for branch condition. void runCheckersForBranchCondition(const Stmt *condition, - BranchNodeBuilder &B, ExprEngine &Eng); + ExplodedNodeSet &Dst, ExplodedNode *Pred, + ExprEngine &Eng); /// \brief Run checkers for live symbols. /// /// Allows modifying SymbolReaper object. For example, checkers can explicitly /// register symbols of interest as live. These symbols will not be marked /// dead and removed. - void runCheckersForLiveSymbols(const ProgramState *state, + void runCheckersForLiveSymbols(ProgramStateRef state, SymbolReaper &SymReaper); /// \brief Run checkers for dead symbols. @@ -253,7 +275,7 @@ public: ExprEngine &Eng); /// \brief True if at least one checker wants to check region changes. - bool wantsRegionChangeUpdate(const ProgramState *state); + bool wantsRegionChangeUpdate(ProgramStateRef state); /// \brief Run checkers for region changes. /// @@ -264,15 +286,18 @@ public: /// For example, in the case of a function call, these would be arguments. /// \param Regions The transitive closure of accessible regions, /// i.e. all regions that may have been touched by this change. - const ProgramState * - runCheckersForRegionChanges(const ProgramState *state, + /// \param The call expression wrapper if the regions are invalidated by a + /// call. + ProgramStateRef + runCheckersForRegionChanges(ProgramStateRef state, const StoreManager::InvalidatedSymbols *invalidated, ArrayRef<const MemRegion *> ExplicitRegions, - ArrayRef<const MemRegion *> Regions); + ArrayRef<const MemRegion *> Regions, + const CallOrObjCMessage *Call); /// \brief Run checkers for handling assumptions on symbolic values. - const ProgramState *runCheckersForEvalAssume(const ProgramState *state, - SVal Cond, bool Assumption); + ProgramStateRef runCheckersForEvalAssume(ProgramStateRef state, + SVal Cond, bool Assumption); /// \brief Run checkers for evaluating a call. void runCheckersForEvalCall(ExplodedNodeSet &Dst, @@ -293,7 +318,7 @@ public: /// \param State The state being printed /// \param NL The preferred representation of a newline. /// \param Sep The preferred separator between different kinds of data. - void runCheckersForPrintState(raw_ostream &Out, const ProgramState *State, + void runCheckersForPrintState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep); //===----------------------------------------------------------------------===// @@ -320,7 +345,8 @@ public: typedef CheckerFn<void (const ObjCMessage &, CheckerContext &)> CheckObjCMessageFunc; - typedef CheckerFn<void (const SVal &location, bool isLoad, const Stmt *S, + typedef CheckerFn<void (const SVal &location, bool isLoad, + const Stmt *S, CheckerContext &)> CheckLocationFunc; @@ -331,26 +357,27 @@ public: typedef CheckerFn<void (ExplodedGraph &, BugReporter &, ExprEngine &)> CheckEndAnalysisFunc; - typedef CheckerFn<void (EndOfFunctionNodeBuilder &, ExprEngine &)> + typedef CheckerFn<void (CheckerContext &)> CheckEndPathFunc; - typedef CheckerFn<void (const Stmt *, BranchNodeBuilder &, ExprEngine &)> + typedef CheckerFn<void (const Stmt *, CheckerContext &)> CheckBranchConditionFunc; typedef CheckerFn<void (SymbolReaper &, CheckerContext &)> CheckDeadSymbolsFunc; - typedef CheckerFn<void (const ProgramState *,SymbolReaper &)> CheckLiveSymbolsFunc; + typedef CheckerFn<void (ProgramStateRef,SymbolReaper &)> CheckLiveSymbolsFunc; - typedef CheckerFn<const ProgramState * (const ProgramState *, + typedef CheckerFn<ProgramStateRef (ProgramStateRef, const StoreManager::InvalidatedSymbols *symbols, - ArrayRef<const MemRegion *> ExplicitRegions, - ArrayRef<const MemRegion *> Regions)> + ArrayRef<const MemRegion *> ExplicitRegions, + ArrayRef<const MemRegion *> Regions, + const CallOrObjCMessage *Call)> CheckRegionChangesFunc; - typedef CheckerFn<bool (const ProgramState *)> WantsRegionChangeUpdateFunc; + typedef CheckerFn<bool (ProgramStateRef)> WantsRegionChangeUpdateFunc; - typedef CheckerFn<const ProgramState * (const ProgramState *, + typedef CheckerFn<ProgramStateRef (ProgramStateRef, const SVal &cond, bool assumption)> EvalAssumeFunc; diff --git a/include/clang/StaticAnalyzer/Core/CheckerRegistry.h b/include/clang/StaticAnalyzer/Core/CheckerRegistry.h index b59c14d..1452d45 100644 --- a/include/clang/StaticAnalyzer/Core/CheckerRegistry.h +++ b/include/clang/StaticAnalyzer/Core/CheckerRegistry.h @@ -107,7 +107,9 @@ public: /// checker does not require any custom initialization. template <class T> void addChecker(StringRef fullName, StringRef desc) { - addChecker(&initializeManager<T>, fullName, desc); + // Avoid MSVC's Compiler Error C2276: + // http://msdn.microsoft.com/en-us/library/850cstw1(v=VS.80).aspx + addChecker(&CheckerRegistry::initializeManager<T>, fullName, desc); } /// Initializes a CheckerManager by calling the initialization functions for diff --git a/include/clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h b/include/clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h index d1f5a7d..65be3a4 100644 --- a/include/clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h +++ b/include/clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h @@ -32,6 +32,10 @@ createPlistDiagnosticConsumer(const std::string& prefix, const Preprocessor &PP, PathDiagnosticConsumer *SubPD = 0); PathDiagnosticConsumer* +createPlistMultiFileDiagnosticConsumer(const std::string& prefix, + const Preprocessor &PP); + +PathDiagnosticConsumer* createTextPathDiagnosticConsumer(const std::string& prefix, const Preprocessor &PP); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h index 6c93f59..3cbecf7 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h @@ -31,14 +31,14 @@ namespace ento { class CheckerManager; class AnalysisManager : public BugReporterData { - AnalysisContextManager AnaCtxMgr; - LocationContextManager LocCtxMgr; + virtual void anchor(); + AnalysisDeclContextManager AnaCtxMgr; ASTContext &Ctx; DiagnosticsEngine &Diags; - const LangOptions &LangInfo; + const LangOptions &LangOpts; - llvm::OwningPtr<PathDiagnosticConsumer> PD; + OwningPtr<PathDiagnosticConsumer> PD; // Configurable components creators. StoreManagerCreator CreateStoreMgr; @@ -53,29 +53,47 @@ class AnalysisManager : public BugReporterData { enum AnalysisScope { ScopeTU, ScopeDecl } AScope; - // The maximum number of exploded nodes the analyzer will generate. + /// \brief The maximum number of exploded nodes the analyzer will generate. unsigned MaxNodes; - // The maximum number of times the analyzer visit a block. + /// \brief The maximum number of times the analyzer visits a block. unsigned MaxVisit; bool VisualizeEGDot; bool VisualizeEGUbi; AnalysisPurgeMode 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. + /// \brief The flag regulates if we should eagerly assume evaluations of + /// conditionals, thus, bifurcating the path. + /// + /// EagerlyAssume - 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: + // \brief inter-procedural analysis mode. + AnalysisIPAMode IPAMode; + + // Settings for inlining tuning. + /// \brief The inlining stack depth limit. + unsigned InlineMaxStackDepth; + /// \brief The max number of basic blocks in a function being inlined. + unsigned InlineMaxFunctionSize; + /// \brief The mode of function selection used during inlining. + AnalysisInliningMode InliningMode; + + /// \brief Do not re-analyze paths leading to exhausted nodes with a different + /// strategy. We get better code coverage when retry is enabled. + bool NoRetryExhausted; + +public: AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags, const LangOptions &lang, PathDiagnosticConsumer *pd, StoreManagerCreator storemgr, @@ -85,9 +103,14 @@ public: unsigned maxnodes, unsigned maxvisit, bool vizdot, bool vizubi, AnalysisPurgeMode purge, bool eager, bool trim, - bool inlinecall, bool useUnoptimizedCFG, + bool useUnoptimizedCFG, bool addImplicitDtors, bool addInitializers, - bool eagerlyTrimEGraph); + bool eagerlyTrimEGraph, + AnalysisIPAMode ipa, + unsigned inlineMaxStack, + unsigned inlineMaxFunctionSize, + AnalysisInliningMode inliningMode, + bool NoRetry); /// Construct a clone of the given AnalysisManager with the given ASTContext /// and DiagnosticsEngine. @@ -97,11 +120,10 @@ public: ~AnalysisManager() { FlushDiagnostics(); } void ClearContexts() { - LocCtxMgr.clear(); AnaCtxMgr.clear(); } - AnalysisContextManager& getAnalysisContextManager() { + AnalysisDeclContextManager& getAnalysisDeclContextManager() { return AnaCtxMgr; } @@ -129,8 +151,8 @@ public: return Diags; } - const LangOptions &getLangOptions() const { - return LangInfo; + const LangOptions &getLangOpts() const { + return LangOpts; } virtual PathDiagnosticConsumer *getPathDiagnosticConsumer() { @@ -139,7 +161,7 @@ public: void FlushDiagnostics() { if (PD.get()) - PD->FlushDiagnostics(); + PD->FlushDiagnostics(0); } unsigned getMaxNodes() const { return MaxNodes; } @@ -162,11 +184,11 @@ public: bool shouldEagerlyAssume() const { return EagerlyAssume; } - bool shouldInlineCall() const { return InlineCall; } + bool shouldInlineCall() const { return (IPAMode == Inlining); } bool hasIndexer() const { return Idxer != 0; } - AnalysisContext *getAnalysisContextInAnotherTU(const Decl *D); + AnalysisDeclContext *getAnalysisDeclContextInAnotherTU(const Decl *D); CFG *getCFG(Decl const *D) { return AnaCtxMgr.getContext(D)->getCFG(); @@ -181,38 +203,17 @@ public: return AnaCtxMgr.getContext(D)->getParentMap(); } - AnalysisContext *getAnalysisContext(const Decl *D) { + AnalysisDeclContext *getAnalysisDeclContext(const Decl *D) { return AnaCtxMgr.getContext(D); } - AnalysisContext *getAnalysisContext(const Decl *D, idx::TranslationUnit *TU) { + AnalysisDeclContext *getAnalysisDeclContext(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 +} // enAnaCtxMgrspace } // end clang namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h b/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h index 42a1537..9a699f9 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h @@ -18,17 +18,10 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.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 ProgramState; - class CompoundValData : public llvm::FoldingSetNode { QualType T; llvm::ImmutableList<SVal> L; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h index 1f14787..b051d33 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h @@ -15,48 +15,41 @@ #ifndef LLVM_CLANG_SA_CORE_PATHSENSITIVE_CHECKERCONTEXT #define LLVM_CLANG_SA_CORE_PATHSENSITIVE_CHECKERCONTEXT -#include "clang/Analysis/Support/SaveAndRestore.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" namespace clang { - namespace ento { class CheckerContext { - ExplodedNodeSet &Dst; - StmtNodeBuilder &B; ExprEngine &Eng; + /// The current exploded(symbolic execution) graph node. ExplodedNode *Pred; - SaveAndRestore<bool> OldSink; - SaveOr OldHasGen; + /// The flag is true if the (state of the execution) has been modified + /// by the checker using this context. For example, a new transition has been + /// added or a bug report issued. + bool Changed; + /// The tagged location, which is used to generate all new nodes. const ProgramPoint Location; - const ProgramState *ST; - const unsigned size; -public: - bool *respondsToCallback; + NodeBuilder &NB; + public: - CheckerContext(ExplodedNodeSet &dst, - StmtNodeBuilder &builder, + /// If we are post visiting a call, this flag will be set if the + /// call was inlined. In all other cases it will be false. + const bool wasInlined; + + CheckerContext(NodeBuilder &builder, ExprEngine &eng, ExplodedNode *pred, const ProgramPoint &loc, - bool *respondsToCB = 0, - const ProgramState *st = 0) - : Dst(dst), - B(builder), - Eng(eng), + bool wasInlined = false) + : Eng(eng), Pred(pred), - OldSink(B.BuildSinks), - OldHasGen(B.hasGeneratedNode), + Changed(false), Location(loc), - ST(st), - size(Dst.size()), - respondsToCallback(respondsToCB) {} - - ~CheckerContext(); - - ExprEngine &getEngine() { - return Eng; + NB(builder), + wasInlined(wasInlined) { + assert(Pred->getState() && + "We should not call the checkers on an empty state."); } AnalysisManager &getAnalysisManager() { @@ -71,18 +64,34 @@ public: return Eng.getStoreManager(); } - ExplodedNodeSet &getNodeSet() { return Dst; } - ExplodedNode *&getPredecessor() { return Pred; } - const ProgramState *getState() { return ST ? ST : Pred->getState(); } + /// \brief Returns the previous node in the exploded graph, which includes + /// the state of the program before the checker ran. Note, checkers should + /// not retain the node in their state since the nodes might get invalidated. + ExplodedNode *getPredecessor() { return Pred; } + ProgramStateRef getState() const { return Pred->getState(); } + + /// \brief Check if the checker changed the state of the execution; ex: added + /// a new transition or a bug report. + bool isDifferent() { return Changed; } /// \brief Returns the number of times the current block has been visited /// along the analyzed path. - unsigned getCurrentBlockCount() {return B.getCurrentBlockCount();} + unsigned getCurrentBlockCount() const { + return NB.getContext().getCurrentBlockCount(); + } ASTContext &getASTContext() { return Eng.getContext(); } - + + const LangOptions &getLangOpts() const { + return Eng.getContext().getLangOpts(); + } + + const LocationContext *getLocationContext() const { + return Pred->getLocationContext(); + } + BugReporter &getBugReporter() { return Eng.getBugReporter(); } @@ -99,83 +108,130 @@ public: return getSValBuilder().getSymbolManager(); } - bool isObjCGCEnabled() { + bool isObjCGCEnabled() const { return Eng.isObjCGCEnabled(); } - /// \brief Generate a default checker node (containing checker tag but no + ProgramStateManager &getStateManager() { + return Eng.getStateManager(); + } + + AnalysisDeclContext *getCurrentAnalysisDeclContext() const { + return Pred->getLocationContext()->getAnalysisDeclContext(); + } + + /// \brief If the given node corresponds to a PostStore program point, retrieve + /// the location region as it was uttered in the code. + /// + /// This utility can be useful for generating extensive diagnostics, for + /// example, for finding variables that the given symbol was assigned to. + static const MemRegion *getLocationRegionIfPostStore(const ExplodedNode *N) { + ProgramPoint L = N->getLocation(); + if (const PostStore *PSL = dyn_cast<PostStore>(&L)) + return reinterpret_cast<const MemRegion*>(PSL->getLocationValue()); + return 0; + } + + /// \brief Generates a new transition in the program state graph + /// (ExplodedGraph). Uses the default CheckerContext predecessor node. + /// + /// @param State The state of the generated node. + /// @param Tag The tag is used to uniquely identify the creation site. If no + /// tag is specified, a default tag, unique to the given checker, + /// will be used. Tags are used to prevent states generated at + /// different sites from caching out. + ExplodedNode *addTransition(ProgramStateRef State, + const ProgramPointTag *Tag = 0) { + return addTransitionImpl(State, false, 0, Tag); + } + + /// \brief Generates a default transition (containing checker tag but no /// checker state changes). - ExplodedNode *generateNode(bool autoTransition = true) { - return generateNode(getState(), autoTransition); + ExplodedNode *addTransition() { + return addTransition(getState()); } - - /// \brief Generate a new checker node with the given predecessor. + + /// \brief Generates a new transition with the given predecessor. /// Allows checkers to generate a chain of nodes. - ExplodedNode *generateNode(const ProgramState *state, - ExplodedNode *pred, - const ProgramPointTag *tag = 0, - bool autoTransition = true) { - ExplodedNode *N = generateNodeImpl(state, false, pred, tag); - if (N && autoTransition) - addTransition(N); - return N; - } - - /// \brief Generate a new checker node. - ExplodedNode *generateNode(const ProgramState *state, - bool autoTransition = true, - const ProgramPointTag *tag = 0) { - ExplodedNode *N = generateNodeImpl(state, false, 0, tag); - if (N && autoTransition) - addTransition(N); - return N; + /// + /// @param State The state of the generated node. + /// @param Pred The transition will be generated from the specified Pred node + /// to the newly generated node. + /// @param Tag The tag to uniquely identify the creation site. + /// @param IsSink Mark the new node as sink, which will stop exploration of + /// the given path. + ExplodedNode *addTransition(ProgramStateRef State, + ExplodedNode *Pred, + const ProgramPointTag *Tag = 0, + bool IsSink = false) { + return addTransitionImpl(State, IsSink, Pred, Tag); } /// \brief Generate a sink node. Generating sink stops exploration of the /// given path. - ExplodedNode *generateSink(const ProgramState *state = 0) { - return generateNodeImpl(state ? state : getState(), true); - } - - void addTransition(ExplodedNode *node) { - Dst.Add(node); - } - - void addTransition(const ProgramState *state, - const ProgramPointTag *tag = 0) { - assert(state); - // If the 'state' is not new, we need to check if the cached state 'ST' - // is new. - if (state != getState() || (ST && ST != Pred->getState())) - // state is new or equals to ST. - generateNode(state, true, tag); - else - Dst.Add(Pred); + ExplodedNode *generateSink(ProgramStateRef state = 0) { + return addTransitionImpl(state ? state : getState(), true); } + /// \brief Emit the diagnostics report. void EmitReport(BugReport *R) { + Changed = true; Eng.getBugReporter().EmitReport(R); } - AnalysisContext *getCurrentAnalysisContext() const { - return Pred->getLocationContext()->getAnalysisContext(); + /// \brief Get the declaration of the called function (path-sensitive). + const FunctionDecl *getCalleeDecl(const CallExpr *CE) const; + + /// \brief Get the name of the called function (path-sensitive). + StringRef getCalleeName(const FunctionDecl *FunDecl) const; + + /// \brief Get the name of the called function (path-sensitive). + StringRef getCalleeName(const CallExpr *CE) const { + const FunctionDecl *FunDecl = getCalleeDecl(CE); + return getCalleeName(FunDecl); } + /// Given a function declaration and a name checks if this is a C lib + /// function with the given name. + bool isCLibraryFunction(const FunctionDecl *FD, StringRef Name); + static bool isCLibraryFunction(const FunctionDecl *FD, StringRef Name, + ASTContext &Context); + + /// \brief Depending on wither the location corresponds to a macro, return + /// either the macro name or the token spelling. + /// + /// This could be useful when checkers' logic depends on whether a function + /// is called with a given macro argument. For example: + /// s = socket(AF_INET,..) + /// If AF_INET is a macro, the result should be treated as a source of taint. + /// + /// \sa clang::Lexer::getSpelling(), clang::Lexer::getImmediateMacroName(). + StringRef getMacroNameOrSpelling(SourceLocation &Loc); + private: - ExplodedNode *generateNodeImpl(const ProgramState *state, - bool markAsSink, - ExplodedNode *pred = 0, - const ProgramPointTag *tag = 0) { - - ExplodedNode *node = B.generateNode(tag ? Location.withTag(tag) : Location, - state, - pred ? pred : Pred); - if (markAsSink && node) - node->markAsSink(); + ExplodedNode *addTransitionImpl(ProgramStateRef State, + bool MarkAsSink, + ExplodedNode *P = 0, + const ProgramPointTag *Tag = 0) { + if (!State || (State == Pred->getState() && !Tag && !MarkAsSink)) + return Pred; + + Changed = true; + ExplodedNode *node = NB.generateNode(Tag ? Location.withTag(Tag) : Location, + State, + P ? P : Pred, MarkAsSink); return node; } }; +/// \brief A helper class which wraps a boolean value set to false by default. +struct DefaultBool { + bool Val; + DefaultBool() : Val(false) {} + operator bool() const { return Val; } + DefaultBool &operator=(bool b) { Val = b; return *this; } +}; + } // end GR namespace } // end clang namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h index 3f6ddde..631858d 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h @@ -22,44 +22,45 @@ class APSInt; } namespace clang { - namespace ento { -class ProgramState; -class ProgramStateManager; class SubEngine; class ConstraintManager { public: virtual ~ConstraintManager(); - virtual const ProgramState *assume(const ProgramState *state, + virtual ProgramStateRef assume(ProgramStateRef state, DefinedSVal Cond, bool Assumption) = 0; - std::pair<const ProgramState*, const ProgramState*> - assumeDual(const ProgramState *state, DefinedSVal Cond) + std::pair<ProgramStateRef, ProgramStateRef > + assumeDual(ProgramStateRef state, DefinedSVal Cond) { - return std::make_pair(assume(state, Cond, true), - assume(state, Cond, false)); + std::pair<ProgramStateRef, ProgramStateRef > res = + std::make_pair(assume(state, Cond, true), assume(state, Cond, false)); + + assert(!(!res.first && !res.second) && "System is over constrained."); + return res; } - virtual const llvm::APSInt* getSymVal(const ProgramState *state, + virtual const llvm::APSInt* getSymVal(ProgramStateRef state, SymbolRef sym) const = 0; - virtual bool isEqual(const ProgramState *state, + virtual bool isEqual(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& V) const = 0; - virtual const ProgramState *removeDeadBindings(const ProgramState *state, + virtual ProgramStateRef removeDeadBindings(ProgramStateRef state, SymbolReaper& SymReaper) = 0; - virtual void print(const ProgramState *state, + virtual void print(ProgramStateRef state, raw_ostream &Out, const char* nl, const char *sep) = 0; - virtual void EndPath(const ProgramState *state) {} + virtual void EndPath(ProgramStateRef state) {} +protected: /// 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 diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 131d39e..59136fc 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -16,7 +16,9 @@ #define LLVM_CLANG_GR_COREENGINE #include "clang/AST/Expr.h" +#include "clang/Analysis/AnalysisContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" #include "llvm/ADT/OwningPtr.h" @@ -27,6 +29,8 @@ class ProgramPointTag; namespace ento { +class NodeBuilder; + //===----------------------------------------------------------------------===// /// CoreEngine - Implements the core logic of the graph-reachability /// analysis. It traverses the CFG and generates the ExplodedGraph. @@ -37,15 +41,13 @@ namespace ento { /// 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 struct NodeBuilderContext; + friend class NodeBuilder; + friend class ExprEngine; + friend class CommonNodeBuilder; friend class IndirectGotoNodeBuilder; friend class SwitchNodeBuilder; friend class EndOfFunctionNodeBuilder; - friend class CallEnterNodeBuilder; - friend class CallExitNodeBuilder; - public: typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > BlocksExhausted; @@ -58,7 +60,7 @@ private: SubEngine& SubEng; /// G - The simulation graph. Each node is a (location,state) pair. - llvm::OwningPtr<ExplodedGraph> G; + 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 @@ -78,8 +80,16 @@ private: /// usually because it could not reason about something. BlocksAborted blocksAborted; + /// The functions which have been analyzed through inlining. This is owned by + /// AnalysisConsumer. It can be null. + SetOfConstDecls *AnalyzedCallees; + + /// The information about functions shared by the whole translation unit. + /// (This data is owned by AnalysisConsumer.) + FunctionSummariesTy *FunctionSummaries; + void generateNode(const ProgramPoint &Loc, - const ProgramState *State, + ProgramStateRef State, ExplodedNode *Pred); void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); @@ -89,28 +99,23 @@ private: 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&); + ExplodedNode *generateCallExitNode(ExplodedNode *N); + public: /// Construct a CoreEngine object to analyze the provided CFG using /// a DFS exploration of the exploded graph. - CoreEngine(SubEngine& subengine) + CoreEngine(SubEngine& subengine, SetOfConstDecls *VisitedCallees, + FunctionSummariesTy *FS) : 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()) {} + BCounterFactory(G->getAllocator()), + AnalyzedCallees(VisitedCallees), + FunctionSummaries(FS){} ~CoreEngine() { delete WList; @@ -126,12 +131,18 @@ public: /// ExecuteWorkList - Run the worklist algorithm for a maximum number of /// steps. Returns true if there is still simulation state on the worklist. bool ExecuteWorkList(const LocationContext *L, unsigned Steps, - const ProgramState *InitState); - void ExecuteWorkListWithInitialState(const LocationContext *L, + ProgramStateRef InitState); + /// Returns true if there is still simulation state on the worklist. + bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, - const ProgramState *InitState, + ProgramStateRef InitState, ExplodedNodeSet &Dst); + /// Dispatch the work list item based on the given location information. + /// Use Pred parameter as the predecessor state. + void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, + const WorkListUnit& WU); + // Functions for external checking of whether we have unfinished work bool wasBlockAborted() const { return !blocksAborted.empty(); } bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } @@ -159,160 +170,254 @@ public: BlocksAborted::const_iterator blocks_aborted_end() const { return blocksAborted.end(); } + + /// \brief Enqueue the given set of nodes onto the work list. + void enqueue(ExplodedNodeSet &Set); + + /// \brief Enqueue nodes that were created as a result of processing + /// a statement onto the work list. + void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx); + + /// \brief enqueue the nodes corresponding to the end of function onto the + /// end of path / work list. + void enqueueEndOfFunction(ExplodedNodeSet &Set); + + /// \brief Enqueue a single node created as a result of statement processing. + void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx); }; -class StmtNodeBuilder { - CoreEngine& Eng; - const CFGBlock &B; - const unsigned Idx; +// TODO: Turn into a calss. +struct NodeBuilderContext { + CoreEngine &Eng; + const CFGBlock *Block; ExplodedNode *Pred; + NodeBuilderContext(CoreEngine &E, const CFGBlock *B, ExplodedNode *N) + : Eng(E), Block(B), Pred(N) { assert(B); assert(!N->isSink()); } + ExplodedNode *getPred() const { return Pred; } -public: - bool PurgingDeadSymbols; - bool BuildSinks; - bool hasGeneratedNode; - ProgramPoint::Kind PointKind; - const ProgramPointTag *Tag; + /// \brief Return the CFGBlock associated with this builder. + const CFGBlock *getBlock() const { return Block; } - typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; - DeferredTy Deferred; + /// \brief Returns the number of times the current basic block has been + /// visited on the exploded graph path. + unsigned getCurrentBlockCount() const { + return Eng.WList->getBlockCounter().getNumVisited( + Pred->getLocationContext()->getCurrentStackFrame(), + Block->getBlockID()); + } +}; - void GenerateAutoTransition(ExplodedNode *N); +/// \class NodeBuilder +/// \brief This is the simplest builder which generates nodes in the +/// ExplodedGraph. +/// +/// The main benefit of the builder is that it automatically tracks the +/// frontier nodes (or destination set). This is the set of nodes which should +/// be propagated to the next step / builder. They are the nodes which have been +/// added to the builder (either as the input node set or as the newly +/// constructed nodes) but did not have any outgoing transitions added. +class NodeBuilder { + virtual void anchor(); +protected: + const NodeBuilderContext &C; + + /// Specifies if the builder results have been finalized. For example, if it + /// is set to false, autotransitions are yet to be generated. + bool Finalized; + bool HasGeneratedNodes; + /// \brief The frontier set - a set of nodes which need to be propagated after + /// the builder dies. + ExplodedNodeSet &Frontier; + + /// Checkes if the results are ready. + virtual bool checkResults() { + if (!Finalized) + return false; + return true; + } -public: - StmtNodeBuilder(const CFGBlock *b, - unsigned idx, - ExplodedNode *N, - CoreEngine* e); + bool hasNoSinksInFrontier() { + for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) { + if ((*I)->isSink()) + return false; + } + return true; + } - ~StmtNodeBuilder(); + /// Allow subclasses to finalize results before result_begin() is executed. + virtual void finalizeResults() {} + + ExplodedNode *generateNodeImpl(const ProgramPoint &PP, + ProgramStateRef State, + ExplodedNode *Pred, + bool MarkAsSink = false); - ExplodedNode *getPredecessor() const { return Pred; } +public: + NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, + const NodeBuilderContext &Ctx, bool F = true) + : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { + Frontier.Add(SrcNode); + } - // FIXME: This should not be exposed. - WorkList *getWorkList() { return Eng.WList; } + NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, + const NodeBuilderContext &Ctx, bool F = true) + : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { + Frontier.insert(SrcSet); + assert(hasNoSinksInFrontier()); + } - BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} + virtual ~NodeBuilder() {} - unsigned getCurrentBlockCount() const { - return getBlockCounter().getNumVisited( - Pred->getLocationContext()->getCurrentStackFrame(), - B.getBlockID()); + /// \brief Generates a node in the ExplodedGraph. + /// + /// When a node is marked as sink, the exploration from the node is stopped - + /// the node becomes the last node on the path. + ExplodedNode *generateNode(const ProgramPoint &PP, + ProgramStateRef State, + ExplodedNode *Pred, + bool MarkAsSink = false) { + return generateNodeImpl(PP, State, Pred, MarkAsSink); } - ExplodedNode *generateNode(const Stmt *S, - const ProgramState *St, - ExplodedNode *Pred, - ProgramPoint::Kind K, - const ProgramPointTag *tag = 0) { - hasGeneratedNode = true; + const ExplodedNodeSet &getResults() { + finalizeResults(); + assert(checkResults()); + return Frontier; + } + + typedef ExplodedNodeSet::iterator iterator; + /// \brief Iterators through the results frontier. + inline iterator begin() { + finalizeResults(); + assert(checkResults()); + return Frontier.begin(); + } + inline iterator end() { + finalizeResults(); + return Frontier.end(); + } - if (PurgingDeadSymbols) - K = ProgramPoint::PostPurgeDeadSymbolsKind; + const NodeBuilderContext &getContext() { return C; } + bool hasGeneratedNodes() { return HasGeneratedNodes; } - return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag); + void takeNodes(const ExplodedNodeSet &S) { + for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I ) + Frontier.erase(*I); } + void takeNodes(ExplodedNode *N) { Frontier.erase(N); } + void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } + void addNodes(ExplodedNode *N) { Frontier.Add(N); } +}; - ExplodedNode *generateNode(const Stmt *S, - const ProgramState *St, +/// \class NodeBuilderWithSinks +/// \brief This node builder keeps track of the generated sink nodes. +class NodeBuilderWithSinks: public NodeBuilder { + virtual void anchor(); +protected: + SmallVector<ExplodedNode*, 2> sinksGenerated; + ProgramPoint &Location; + +public: + NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, + const NodeBuilderContext &Ctx, ProgramPoint &L) + : NodeBuilder(Pred, DstSet, Ctx), Location(L) {} + ExplodedNode *generateNode(ProgramStateRef State, ExplodedNode *Pred, - const ProgramPointTag *tag = 0) { - return generateNode(S, St, Pred, PointKind, tag); - } + const ProgramPointTag *Tag = 0, + bool MarkAsSink = false) { + ProgramPoint LocalLoc = (Tag ? Location.withTag(Tag): Location); - ExplodedNode *generateNode(const ProgramPoint &PP, - const ProgramState *State, - ExplodedNode *Pred) { - hasGeneratedNode = true; - return generateNodeInternal(PP, State, Pred); + ExplodedNode *N = generateNodeImpl(LocalLoc, State, Pred, MarkAsSink); + if (N && N->isSink()) + sinksGenerated.push_back(N); + return N; } - ExplodedNode* - generateNodeInternal(const ProgramPoint &PP, - const ProgramState *State, - ExplodedNode *Pred); - - ExplodedNode* - generateNodeInternal(const Stmt *S, - const ProgramState *State, - ExplodedNode *Pred, - ProgramPoint::Kind K, - const ProgramPointTag *tag = 0); - - /// getStmt - Return the current block-level expression associated with - /// this builder. - const Stmt *getStmt() const { - const CFGStmt *CS = B[Idx].getAs<CFGStmt>(); - return CS ? CS->getStmt() : 0; + const SmallVectorImpl<ExplodedNode*> &getSinks() const { + return sinksGenerated; } +}; - /// getBlock - Return the CFGBlock associated with the block-level expression - /// of this builder. - const CFGBlock *getBlock() const { return &B; } +/// \class StmtNodeBuilder +/// \brief This builder class is useful for generating nodes that resulted from +/// visiting a statement. The main difference from it's parent NodeBuilder is +/// that it creates a statement specific ProgramPoint. +class StmtNodeBuilder: public NodeBuilder { + NodeBuilder *EnclosingBldr; +public: - unsigned getIndex() const { return Idx; } + /// \brief Constructs a StmtNodeBuilder. If the builder is going to process + /// nodes currently owned by another builder(with larger scope), use + /// Enclosing builder to transfer ownership. + StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, + const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) + : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) { + if (EnclosingBldr) + EnclosingBldr->takeNodes(SrcNode); + } - ExplodedNode *MakeNode(ExplodedNodeSet &Dst, - const Stmt *S, - ExplodedNode *Pred, - const ProgramState *St) { - return MakeNode(Dst, S, Pred, St, PointKind); + StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, + const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) + : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) { + if (EnclosingBldr) + for (ExplodedNodeSet::iterator I = SrcSet.begin(), + E = SrcSet.end(); I != E; ++I ) + EnclosingBldr->takeNodes(*I); } - ExplodedNode *MakeNode(ExplodedNodeSet &Dst, - const Stmt *S, - ExplodedNode *Pred, - const ProgramState *St, - ProgramPoint::Kind K); + virtual ~StmtNodeBuilder(); - ExplodedNode *MakeSinkNode(ExplodedNodeSet &Dst, - const Stmt *S, + ExplodedNode *generateNode(const Stmt *S, ExplodedNode *Pred, - const ProgramState *St) { - bool Tmp = BuildSinks; - BuildSinks = true; - ExplodedNode *N = MakeNode(Dst, S, Pred, St); - BuildSinks = Tmp; - return N; + ProgramStateRef St, + bool MarkAsSink = false, + const ProgramPointTag *tag = 0, + ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ + const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, + Pred->getLocationContext(), tag); + return generateNodeImpl(L, St, Pred, MarkAsSink); + } + + ExplodedNode *generateNode(const ProgramPoint &PP, + ExplodedNode *Pred, + ProgramStateRef State, + bool MarkAsSink = false) { + return generateNodeImpl(PP, State, Pred, MarkAsSink); } }; -class BranchNodeBuilder { - CoreEngine& Eng; - const CFGBlock *Src; +/// \brief BranchNodeBuilder is responsible for constructing the nodes +/// corresponding to the two branches of the if statement - true and false. +class BranchNodeBuilder: public NodeBuilder { + virtual void anchor(); const CFGBlock *DstT; const CFGBlock *DstF; - ExplodedNode *Pred; - typedef 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();} + BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, + const NodeBuilderContext &C, + const CFGBlock *dstT, const CFGBlock *dstF) + : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF), + InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { + // The branch node builder does not generate autotransitions. + // If there are no successors it means that both branches are infeasible. + takeNodes(SrcNode); + } - /// This function generates a new ExplodedNode but not a new - /// branch(block edge). - ExplodedNode *generateNode(const Stmt *Condition, const ProgramState *State); + BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, + const NodeBuilderContext &C, + const CFGBlock *dstT, const CFGBlock *dstF) + : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF), + InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { + takeNodes(SrcSet); + } - ExplodedNode *generateNode(const ProgramState *State, bool branch); + ExplodedNode *generateNode(ProgramStateRef State, bool branch, + ExplodedNode *Pred); const CFGBlock *getTargetBlock(bool branch) const { return branch ? DstT : DstF; @@ -320,18 +425,14 @@ public: void markInfeasible(bool branch) { if (branch) - InFeasibleTrue = GeneratedTrue = true; + InFeasibleTrue = true; else - InFeasibleFalse = GeneratedFalse = true; + InFeasibleFalse = true; } bool isFeasible(bool branch) { return branch ? !InFeasibleTrue : !InFeasibleFalse; } - - const ProgramState *getState() const { - return getPredecessor()->getState(); - } }; class IndirectGotoNodeBuilder { @@ -369,12 +470,16 @@ public: iterator end() { return iterator(DispatchBlock.succ_end()); } ExplodedNode *generateNode(const iterator &I, - const ProgramState *State, + ProgramStateRef State, bool isSink = false); const Expr *getTarget() const { return E; } - const ProgramState *getState() const { return Pred->State; } + ProgramStateRef getState() const { return Pred->State; } + + const LocationContext *getLocationContext() const { + return Pred->getLocationContext(); + } }; class SwitchNodeBuilder { @@ -416,167 +521,21 @@ public: } ExplodedNode *generateCaseStmtNode(const iterator &I, - const ProgramState *State); + ProgramStateRef State); - ExplodedNode *generateDefaultCaseNode(const ProgramState *State, + ExplodedNode *generateDefaultCaseNode(ProgramStateRef State, bool isSink = false); const Expr *getCondition() const { return Condition; } - const ProgramState *getState() const { return Pred->State; } -}; - -class GenericNodeBuilderImpl { -protected: - CoreEngine &engine; - ExplodedNode *pred; - ProgramPoint pp; - SmallVector<ExplodedNode*, 2> sinksGenerated; - - ExplodedNode *generateNodeImpl(const ProgramState *state, - ExplodedNode *pred, - ProgramPoint programPoint, - bool asSink); - - GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p) - : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {} - -public: - bool hasGeneratedNode; - - WorkList &getWorkList() { return *engine.WList; } - - ExplodedNode *getPredecessor() const { return pred; } + ProgramStateRef getState() const { return Pred->State; } - BlockCounter getBlockCounter() const { - return engine.WList->getBlockCounter(); - } - - const 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 ProgramState *state, ExplodedNode *pred, - const ProgramPointTag *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; - const ProgramPointTag *Tag; - -public: - bool hasGeneratedNode; - -public: - EndOfFunctionNodeBuilder(const CFGBlock *b, ExplodedNode *N, CoreEngine* e, - const ProgramPointTag *tag = 0) - : Eng(*e), B(*b), Pred(N), Tag(tag), hasGeneratedNode(false) {} - - ~EndOfFunctionNodeBuilder(); - - EndOfFunctionNodeBuilder withCheckerTag(const ProgramPointTag *tag) { - return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag); - } - - 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 ProgramState *State, - ExplodedNode *P = 0, - const ProgramPointTag *tag = 0); - - void GenerateCallExitNode(const ProgramState *state); - - const CFGBlock *getBlock() const { return &B; } - - const ProgramState *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 ProgramState *getState() const { return Pred->getState(); } - - const LocationContext *getLocationContext() const { + 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 ProgramState *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 ProgramState *getState() const { return Pred->getState(); } - - void generateNode(const ProgramState *state); -}; - -} // end GR namespace - +} // end ento namespace } // end clang namespace #endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h index 2463e23..b80213e 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h @@ -14,6 +14,7 @@ #ifndef LLVM_CLANG_GR_ENVIRONMENT_H #define LLVM_CLANG_GR_ENVIRONMENT_H +#include "clang/Analysis/AnalysisContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/ADT/ImmutableMap.h" @@ -26,15 +27,39 @@ namespace ento { class EnvironmentManager; class SValBuilder; -/// Environment - An immutable map from Stmts to their current -/// symbolic values (SVals). -/// +/// An entry in the environment consists of a Stmt and an LocationContext. +/// This allows the environment to manage context-sensitive bindings, +/// which is essentially for modeling recursive function analysis, among +/// other things. +class EnvironmentEntry : public std::pair<const Stmt*, + const StackFrameContext *> { +public: + EnvironmentEntry(const Stmt *s, const LocationContext *L) + : std::pair<const Stmt*, + const StackFrameContext*>(s, L ? L->getCurrentStackFrame():0) {} + + const Stmt *getStmt() const { return first; } + const LocationContext *getLocationContext() const { return second; } + + /// Profile an EnvironmentEntry for inclusion in a FoldingSet. + static void Profile(llvm::FoldingSetNodeID &ID, + const EnvironmentEntry &E) { + ID.AddPointer(E.getStmt()); + ID.AddPointer(E.getLocationContext()); + } + + void Profile(llvm::FoldingSetNodeID &ID) const { + Profile(ID, *this); + } +}; + +/// An immutable map from EnvironemntEntries to SVals. class Environment { private: friend class EnvironmentManager; // Type definitions. - typedef llvm::ImmutableMap<const Stmt*,SVal> BindingsTy; + typedef llvm::ImmutableMap<EnvironmentEntry, SVal> BindingsTy; // Data. BindingsTy ExprBindings; @@ -42,18 +67,18 @@ private: Environment(BindingsTy eb) : ExprBindings(eb) {} - SVal lookupExpr(const Stmt *E) const; + SVal lookupExpr(const EnvironmentEntry &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, - bool useOnlyDirectBindings = false) const; + /// Fetches the current binding of the expression in the + /// Environment. + SVal getSVal(const EnvironmentEntry &E, + SValBuilder &svalBuilder, + bool useOnlyDirectBindings = false) const; /// Profile - Profile the contents of an Environment object for use /// in a FoldingSet. @@ -70,6 +95,12 @@ public: bool operator==(const Environment& RHS) const { return ExprBindings == RHS.ExprBindings; } + + void print(raw_ostream &Out, const char *NL, const char *Sep) const; + +private: + void printAux(raw_ostream &Out, bool printLocations, + const char *NL, const char *Sep) const; }; class EnvironmentManager { @@ -85,17 +116,20 @@ public: return Environment(F.getEmptyMap()); } - /// Bind the value 'V' to the statement 'S'. - Environment bindExpr(Environment Env, const Stmt *S, SVal V, + /// Bind a symbolic value to the given environment entry. + Environment bindExpr(Environment Env, const EnvironmentEntry &E, 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, + /// Bind the location 'location' and value 'V' to the specified + /// environment entry. + Environment bindExprAndLocation(Environment Env, + const EnvironmentEntry &E, + SVal location, SVal V); Environment removeDeadBindings(Environment Env, - SymbolReaper &SymReaper, const ProgramState *ST); + SymbolReaper &SymReaper, + ProgramStateRef state); }; } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index fdfed3d..46fbb88 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -32,6 +32,7 @@ #include "llvm/Support/Casting.h" #include "clang/Analysis/Support/BumpVector.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include <vector> namespace clang { @@ -53,7 +54,7 @@ class ExplodedGraph; class ExplodedNode : public llvm::FoldingSetNode { friend class ExplodedGraph; friend class CoreEngine; - friend class StmtNodeBuilder; + friend class NodeBuilder; friend class BranchNodeBuilder; friend class IndirectGotoNodeBuilder; friend class SwitchNodeBuilder; @@ -106,7 +107,7 @@ class ExplodedNode : public llvm::FoldingSetNode { const ProgramPoint Location; /// State - The state associated with this node. - const ProgramState *State; + ProgramStateRef State; /// Preds - The predecessors of this node. NodeGroup Preds; @@ -116,14 +117,14 @@ class ExplodedNode : public llvm::FoldingSetNode { public: - explicit ExplodedNode(const ProgramPoint &loc, const ProgramState *state) + explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, + bool IsSink) : Location(loc), State(state) { - const_cast<ProgramState*>(State)->incrementReferenceCount(); + if (IsSink) + Succs.setFlag(); } - ~ExplodedNode() { - const_cast<ProgramState*>(State)->decrementReferenceCount(); - } + ~ExplodedNode() {} /// getLocation - Returns the edge associated with the given node. ProgramPoint getLocation() const { return Location; } @@ -143,19 +144,22 @@ public: return *getLocationContext()->getAnalysis<T>(); } - const ProgramState *getState() const { return State; } + ProgramStateRef 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 ProgramState *state) { + const ProgramPoint &Loc, + ProgramStateRef state, + bool IsSink) { ID.Add(Loc); - ID.AddPointer(state); + ID.AddPointer(state.getPtr()); + ID.AddBoolean(IsSink); } void Profile(llvm::FoldingSetNodeID& ID) const { - Profile(ID, getLocation(), getState()); + Profile(ID, getLocation(), getState(), isSink()); } /// addPredeccessor - Adds a predecessor to the current node, and @@ -168,7 +172,10 @@ public: bool pred_empty() const { return Preds.empty(); } bool isSink() const { return Succs.getFlag(); } - void markAsSink() { Succs.setFlag(); } + + bool hasSinglePred() const { + return (pred_size() == 1); + } ExplodedNode *getFirstPred() { return pred_empty() ? NULL : *(pred_begin()); @@ -223,6 +230,7 @@ private: // FIXME: Is this class necessary? class InterExplodedGraphMap { + virtual void anchor(); llvm::DenseMap<const ExplodedNode*, ExplodedNode*> M; friend class ExplodedGraph; @@ -238,18 +246,17 @@ protected: friend class CoreEngine; // Type definitions. - typedef SmallVector<ExplodedNode*,2> RootsTy; - typedef SmallVector<ExplodedNode*,10> EndNodesTy; + typedef std::vector<ExplodedNode *> NodeVector; - /// Roots - The roots of the simulation graph. Usually there will be only + /// 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; + NodeVector Roots; - /// EndNodes - The nodes in the simulation graph which have been - /// specially marked as the endpoint of an abstract simulation path. - EndNodesTy EndNodes; + /// The nodes in the simulation graph which have been + /// specially marked as the endpoint of an abstract simulation path. + NodeVector EndNodes; /// Nodes - The nodes in the graph. llvm::FoldingSet<ExplodedNode> Nodes; @@ -262,21 +269,25 @@ protected: unsigned NumNodes; /// A list of recently allocated nodes that can potentially be recycled. - void *recentlyAllocatedNodes; + NodeVector ChangedNodes; /// A list of nodes that can be reused. - void *freeNodes; + NodeVector FreeNodes; /// A flag that indicates whether nodes should be recycled. bool reclaimNodes; + + /// Counter to determine when to reclaim nodes. + unsigned reclaimCounter; public: - /// getNode - Retrieve the node associated with a (Location,State) pair, + + /// \brief 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 + /// this pair exists, it is created. IsNew is set to true if /// the node was freshly created. - - ExplodedNode *getNode(const ProgramPoint &L, const ProgramState *State, + ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, + bool IsSink = false, bool* IsNew = 0); ExplodedGraph* MakeEmptyGraph() const { @@ -295,9 +306,7 @@ public: return V; } - ExplodedGraph() - : NumNodes(0), recentlyAllocatedNodes(0), - freeNodes(0), reclaimNodes(false) {} + ExplodedGraph(); ~ExplodedGraph(); @@ -310,10 +319,10 @@ public: // 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 NodeVector::iterator roots_iterator; + typedef NodeVector::const_iterator const_roots_iterator; + typedef NodeVector::iterator eop_iterator; + typedef NodeVector::const_iterator const_eop_iterator; typedef AllNodesTy::iterator node_iterator; typedef AllNodesTy::const_iterator const_node_iterator; @@ -362,6 +371,10 @@ public: /// Reclaim "uninteresting" nodes created since the last time this method /// was called. void reclaimRecentlyAllocatedNodes(); + +private: + bool shouldCollect(const ExplodedNode *node); + void collectNode(ExplodedNode *node); }; class ExplodedNodeSet { @@ -380,19 +393,16 @@ public: 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(); } + bool erase(ExplodedNode *N) { return Impl.erase(N); } void clear() { Impl.clear(); } void insert(const ExplodedNodeSet &S) { + assert(&S != this); if (empty()) Impl = S.Impl; else diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index 9bc470f..2a21a03 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -20,16 +20,24 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" +#include "clang/AST/Expr.h" #include "clang/AST/Type.h" -#include "clang/AST/ExprObjC.h" -#include "clang/AST/ExprCXX.h" -#include "clang/AST/StmtObjC.h" namespace clang { +class AnalysisDeclContextManager; +class CXXCatchStmt; +class CXXConstructExpr; +class CXXDeleteExpr; +class CXXNewExpr; +class CXXTemporaryObjectExpr; +class CXXThisExpr; +class MaterializeTemporaryExpr; +class ObjCAtSynchronizedStmt; class ObjCForCollectionStmt; - + namespace ento { class AnalysisManager; @@ -38,16 +46,14 @@ class ObjCMessage; class ExprEngine : public SubEngine { AnalysisManager &AMgr; + + AnalysisDeclContextManager &AnalysisDeclContexts; 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. ProgramStateManager StateMgr; @@ -62,10 +68,12 @@ class ExprEngine : public SubEngine { /// CleanedState - The state for EntryNode "cleaned" of all dead /// variables and symbols (as determined by a liveness analysis). - const ProgramState *CleanedState; + ProgramStateRef CleanedState; /// currentStmt - The current block-level statement. const Stmt *currentStmt; + unsigned int currentStmtIdx; + const NodeBuilderContext *currentBuilderContext; /// Obj-C Class Identifiers. IdentifierInfo* NSExceptionII; @@ -83,21 +91,25 @@ class ExprEngine : public SubEngine { GRBugReporter BR; public: - ExprEngine(AnalysisManager &mgr, bool gcEnabled); + ExprEngine(AnalysisManager &mgr, bool gcEnabled, + SetOfConstDecls *VisitedCallees, + FunctionSummariesTy *FS); ~ExprEngine(); - void ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) { - Engine.ExecuteWorkList(L, Steps, 0); + /// Returns true if there is still simulation state on the worklist. + bool ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) { + return 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 ProgramState *InitState, + /// state of the function call. Returns true if there is still simulation + /// state on the worklist. + bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, + ProgramStateRef InitState, ExplodedNodeSet &Dst) { - Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst); + return Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst); } /// getContext - Return the ASTContext associated with this analysis. @@ -113,10 +125,19 @@ public: BugReporter& getBugReporter() { return BR; } - StmtNodeBuilder &getBuilder() { assert(Builder); return *Builder; } + const NodeBuilderContext &getBuilderContext() { + assert(currentBuilderContext); + return *currentBuilderContext; + } bool isObjCGCEnabled() { return ObjCGCEnabled; } + const Stmt *getStmt() const; + + void GenerateAutoTransition(ExplodedNode *N); + void enqueueEndOfPath(ExplodedNodeSet &S); + void GenerateCallExitNode(ExplodedNode *N); + /// ViewGraph - Visualize the ExplodedGraph created by executing the /// simulation. void ViewGraph(bool trim = false); @@ -125,36 +146,43 @@ public: /// getInitialState - Return the initial state used for the root vertex /// in the ExplodedGraph. - const ProgramState *getInitialState(const LocationContext *InitLoc); + ProgramStateRef getInitialState(const LocationContext *InitLoc); ExplodedGraph& getGraph() { return G; } const ExplodedGraph& getGraph() const { return G; } /// 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 processCFGElement(const CFGElement E, ExplodedNode *Pred, + unsigned StmtIdx, NodeBuilderContext *Ctx); - void ProcessStmt(const CFGStmt S, StmtNodeBuilder &builder); + void ProcessStmt(const CFGStmt S, ExplodedNode *Pred); - void ProcessInitializer(const CFGInitializer I, StmtNodeBuilder &builder); + void ProcessInitializer(const CFGInitializer I, ExplodedNode *Pred); - void ProcessImplicitDtor(const CFGImplicitDtor D, StmtNodeBuilder &builder); + void ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred); void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D, - StmtNodeBuilder &builder); - void ProcessBaseDtor(const CFGBaseDtor D, StmtNodeBuilder &builder); - void ProcessMemberDtor(const CFGMemberDtor D, StmtNodeBuilder &builder); + ExplodedNode *Pred, ExplodedNodeSet &Dst); + void ProcessBaseDtor(const CFGBaseDtor D, + ExplodedNode *Pred, ExplodedNodeSet &Dst); + void ProcessMemberDtor(const CFGMemberDtor D, + ExplodedNode *Pred, ExplodedNodeSet &Dst); void ProcessTemporaryDtor(const CFGTemporaryDtor D, - StmtNodeBuilder &builder); + ExplodedNode *Pred, ExplodedNodeSet &Dst); /// Called by CoreEngine when processing the entrance of a CFGBlock. - virtual void processCFGBlockEntrance(ExplodedNodeSet &dstNodes, - GenericNodeBuilder<BlockEntrance> &nodeBuilder); + virtual void processCFGBlockEntrance(const BlockEdge &L, + NodeBuilderWithSinks &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); + NodeBuilderContext& BuilderCtx, + ExplodedNode *Pred, + ExplodedNodeSet &Dst, + const CFGBlock *DstT, + const CFGBlock *DstF); /// processIndirectGoto - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a computed goto jump. @@ -166,35 +194,36 @@ public: /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path /// nodes when the control reaches the end of a function. - void processEndOfFunction(EndOfFunctionNodeBuilder& builder); + void processEndOfFunction(NodeBuilderContext& BC); /// Generate the entry node of the callee. - void processCallEnter(CallEnterNodeBuilder &builder); + void processCallEnter(CallEnter CE, ExplodedNode *Pred); /// Generate the first post callsite node. - void processCallExit(CallExitNodeBuilder &builder); + void processCallExit(ExplodedNode *Pred); /// 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 ProgramState *processAssume(const ProgramState *state, SVal cond,bool assumption); + ProgramStateRef processAssume(ProgramStateRef state, SVal cond,bool assumption); /// wantsRegionChangeUpdate - Called by ProgramStateManager to determine if a /// region change should trigger a processRegionChanges update. - bool wantsRegionChangeUpdate(const ProgramState *state); + bool wantsRegionChangeUpdate(ProgramStateRef state); /// processRegionChanges - Called by ProgramStateManager whenever a change is made /// to the store. Used to update checkers that track region values. - const ProgramState * - processRegionChanges(const ProgramState *state, + ProgramStateRef + processRegionChanges(ProgramStateRef state, const StoreManager::InvalidatedSymbols *invalidated, ArrayRef<const MemRegion *> ExplicitRegions, - ArrayRef<const MemRegion *> Regions); + ArrayRef<const MemRegion *> Regions, + const CallOrObjCMessage *Call); /// printState - Called by ProgramStateManager to print checker-specific data. - void printState(raw_ostream &Out, const ProgramState *State, + void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep); virtual ProgramStateManager& getStateManager() { return StateMgr; } @@ -225,11 +254,6 @@ public: const CoreEngine &getCoreEngine() const { return Engine; } public: - ExplodedNode *MakeNode(ExplodedNodeSet &Dst, const Stmt *S, - ExplodedNode *Pred, const ProgramState *St, - ProgramPoint::Kind K = ProgramPoint::PostStmtKind, - const ProgramPointTag *tag = 0); - /// Visit - Transfer function logic for all statements. Dispatches to /// other functions that handle specific kinds of statements. void Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst); @@ -241,16 +265,6 @@ public: /// 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, @@ -328,13 +342,19 @@ public: void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred, ExplodedNodeSet &Dst); + /// Handle ++ and -- (both pre- and post-increment). + void VisitIncrementDecrementOperator(const UnaryOperator* U, + ExplodedNode *Pred, + ExplodedNodeSet &Dst); + + void VisitCXXCatchStmt(const CXXCatchStmt *CS, 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); - } + ExplodedNode *Pred, ExplodedNodeSet &Dst); void VisitCXXConstructExpr(const CXXConstructExpr *E, const MemRegion *Dest, ExplodedNode *Pred, ExplodedNodeSet &Dst); @@ -349,9 +369,6 @@ public: 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 MaterializeTemporaryExpr *ME, ExplodedNode *Pred, @@ -363,17 +380,7 @@ public: 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 callee expression (for a function call). - void evalCallee(const CallExpr *callExpr, const ExplodedNodeSet &src, - ExplodedNodeSet &dest); - /// 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. @@ -393,31 +400,34 @@ public: public: - SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op, + SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc L, NonLoc R, QualType T) { return svalBuilder.evalBinOpNN(state, op, L, R, T); } - SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op, + SVal evalBinOp(ProgramStateRef 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 ProgramState *ST, BinaryOperator::Opcode Op, + SVal evalBinOp(ProgramStateRef 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 ProgramState *state); + void evalObjCMessage(StmtNodeBuilder &Bldr, const ObjCMessage &msg, + ExplodedNode *Pred, ProgramStateRef state, + bool GenSink); - const ProgramState *invalidateArguments(const ProgramState *State, + ProgramStateRef invalidateArguments(ProgramStateRef State, const CallOrObjCMessage &Call, const LocationContext *LC); - const ProgramState *MarkBranch(const ProgramState *St, const Stmt *Terminator, - bool branchTaken); + ProgramStateRef MarkBranch(ProgramStateRef state, + const Stmt *Terminator, + const LocationContext *LCtx, + bool branchTaken); /// evalBind - Handle the semantics of binding a value to a specific location. /// This method is used by evalStore, VisitDeclStmt, and others. @@ -431,34 +441,52 @@ public: // be the same as Pred->state, and when 'location' may not be the // same as state->getLValue(Ex). /// Simulate a read of the result of Ex. - void evalLoad(ExplodedNodeSet &Dst, const Expr *Ex, ExplodedNode *Pred, - const ProgramState *St, SVal location, const ProgramPointTag *tag = 0, + void evalLoad(ExplodedNodeSet &Dst, + const Expr *NodeEx, /* Eventually will be a CFGStmt */ + const Expr *BoundExpr, + ExplodedNode *Pred, + ProgramStateRef St, + SVal location, + const ProgramPointTag *tag = 0, QualType LoadTy = QualType()); // FIXME: 'tag' should be removed, and a LocationContext should be used // instead. void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE, - ExplodedNode *Pred, const ProgramState *St, SVal TargetLV, SVal Val, + ExplodedNode *Pred, ProgramStateRef St, SVal TargetLV, SVal Val, const ProgramPointTag *tag = 0); private: - void evalLoadCommon(ExplodedNodeSet &Dst, const Expr *Ex, ExplodedNode *Pred, - const ProgramState *St, SVal location, const ProgramPointTag *tag, + void evalLoadCommon(ExplodedNodeSet &Dst, + const Expr *NodeEx, /* Eventually will be a CFGStmt */ + const Expr *BoundEx, + ExplodedNode *Pred, + ProgramStateRef St, + SVal location, + const ProgramPointTag *tag, QualType LoadTy); // FIXME: 'tag' should be removed, and a LocationContext should be used // instead. - void evalLocation(ExplodedNodeSet &Dst, const Stmt *S, ExplodedNode *Pred, - const ProgramState *St, SVal location, + void evalLocation(ExplodedNodeSet &Dst, + const Stmt *NodeEx, /* This will eventually be a CFGStmt */ + const Stmt *BoundEx, + ExplodedNode *Pred, + ProgramStateRef St, SVal location, const ProgramPointTag *tag, bool isLoad); + bool shouldInlineDecl(const FunctionDecl *FD, ExplodedNode *Pred); bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred); - - -public: - /// Returns true if calling the specific function or method would possibly - /// cause global variables to be invalidated. - bool doesInvalidateGlobals(const CallOrObjCMessage &callOrMessage) const; - + + bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC); +}; + +/// Traits for storing the call processing policy inside GDM. +/// The GDM stores the corresponding CallExpr pointer. +struct ReplayWithoutInlining{}; +template <> +struct ProgramStateTrait<ReplayWithoutInlining> : + public ProgramStatePartialTrait<void*> { + static void *GDMIndex() { static int index = 0; return &index; } }; } // end ento namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h deleted file mode 100644 index 89b47dc..0000000 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngineBuilders.h +++ /dev/null @@ -1,80 +0,0 @@ -//===-- 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 ProgramState *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 ProgramState *st, - const Stmt *s, bool auto_create_node) - : Dst(dst), B(builder), Eng(eng), Pred(pred), - state(st), stmt(s), OldSize(Dst.size()), AutoCreateNode(auto_create_node), - OldSink(B.BuildSinks), OldHasGen(B.hasGeneratedNode) {} - -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 ProgramState *getState() { return state; } - - ProgramStateManager& getStateManager() { - return Eng.getStateManager(); - } - - ExplodedNode *MakeNode(const ProgramState *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/FunctionSummary.h b/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h new file mode 100644 index 0000000..42adff3 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h @@ -0,0 +1,107 @@ +//== FunctionSummary.h - Stores summaries of functions. ------------*- 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 summary of a function gathered/used by static analyzes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_FUNCTIONSUMMARY_H +#define LLVM_CLANG_GR_FUNCTIONSUMMARY_H + +#include "clang/AST/Decl.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/BitVector.h" + +namespace clang { +namespace ento { +typedef llvm::SmallPtrSet<Decl*, 24> SetOfDecls; +typedef llvm::SmallPtrSet<const Decl*, 24> SetOfConstDecls; + +class FunctionSummariesTy { + struct FunctionSummary { + /// True if this function has reached a max block count while inlined from + /// at least one call site. + bool MayReachMaxBlockCount; + + /// Total number of blocks in the function. + unsigned TotalBasicBlocks; + + /// Marks the IDs of the basic blocks visited during the analyzes. + llvm::BitVector VisitedBasicBlocks; + + FunctionSummary() : + MayReachMaxBlockCount(false), + TotalBasicBlocks(0), + VisitedBasicBlocks(0) {} + }; + + typedef llvm::DenseMap<const Decl*, FunctionSummary*> MapTy; + MapTy Map; + +public: + ~FunctionSummariesTy(); + + MapTy::iterator findOrInsertSummary(const Decl *D) { + MapTy::iterator I = Map.find(D); + if (I != Map.end()) + return I; + FunctionSummary *DS = new FunctionSummary(); + I = Map.insert(std::pair<const Decl*, FunctionSummary*>(D, DS)).first; + assert(I != Map.end()); + return I; + } + + void markReachedMaxBlockCount(const Decl* D) { + MapTy::iterator I = findOrInsertSummary(D); + I->second->MayReachMaxBlockCount = true; + } + + bool hasReachedMaxBlockCount(const Decl* D) { + MapTy::const_iterator I = Map.find(D); + if (I != Map.end()) + return I->second->MayReachMaxBlockCount; + return false; + } + + void markVisitedBasicBlock(unsigned ID, const Decl* D, unsigned TotalIDs) { + MapTy::iterator I = findOrInsertSummary(D); + llvm::BitVector &Blocks = I->second->VisitedBasicBlocks; + assert(ID < TotalIDs); + if (TotalIDs > Blocks.size()) { + Blocks.resize(TotalIDs); + I->second->TotalBasicBlocks = TotalIDs; + } + Blocks[ID] = true; + } + + unsigned getNumVisitedBasicBlocks(const Decl* D) { + MapTy::const_iterator I = Map.find(D); + if (I != Map.end()) + return I->second->VisitedBasicBlocks.count(); + return 0; + } + + /// Get the percentage of the reachable blocks. + unsigned getPercentBlocksReachable(const Decl *D) { + MapTy::const_iterator I = Map.find(D); + if (I != Map.end()) + return ((I->second->VisitedBasicBlocks.count() * 100) / + I->second->TotalBasicBlocks); + return 0; + } + + unsigned getTotalNumBasicBlocks(); + unsigned getTotalNumVisitedBasicBlocks(); + +}; + +}} // end clang ento namespaces + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h index c9941fe..87bc0df 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h @@ -18,7 +18,7 @@ #include "clang/AST/CharUnits.h" #include "clang/AST/Decl.h" -#include "clang/AST/DeclObjC.h" +#include "clang/AST/ExprObjC.h" #include "clang/Basic/LLVM.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/Support/ErrorHandling.h" @@ -73,12 +73,16 @@ public: StackArgumentsSpaceRegionKind, HeapSpaceRegionKind, UnknownSpaceRegionKind, - NonStaticGlobalSpaceRegionKind, StaticGlobalSpaceRegionKind, - BEG_GLOBAL_MEMSPACES = NonStaticGlobalSpaceRegionKind, - END_GLOBAL_MEMSPACES = StaticGlobalSpaceRegionKind, + GlobalInternalSpaceRegionKind, + GlobalSystemSpaceRegionKind, + GlobalImmutableSpaceRegionKind, + BEG_NON_STATIC_GLOBAL_MEMSPACES = GlobalInternalSpaceRegionKind, + END_NON_STATIC_GLOBAL_MEMSPACES = GlobalImmutableSpaceRegionKind, + BEG_GLOBAL_MEMSPACES = StaticGlobalSpaceRegionKind, + END_GLOBAL_MEMSPACES = GlobalImmutableSpaceRegionKind, BEG_MEMSPACES = GenericMemSpaceRegionKind, - END_MEMSPACES = StaticGlobalSpaceRegionKind, + END_MEMSPACES = GlobalImmutableSpaceRegionKind, // Untyped regions. SymbolicRegionKind, AllocaRegionKind, @@ -91,6 +95,7 @@ public: CompoundLiteralRegionKind = BEG_TYPED_VALUE_REGIONS, CXXThisRegionKind, StringRegionKind, + ObjCStringRegionKind, ElementRegionKind, // Decl Regions. BEG_DECL_REGIONS, @@ -118,8 +123,6 @@ public: virtual MemRegionManager* getMemRegionManager() const = 0; - std::string getString() const; - const MemSpaceRegion *getMemorySpace() const; const MemRegion *getBaseRegion() const; @@ -137,10 +140,16 @@ public: /// Compute the offset within the top level memory object. RegionOffset getAsOffset() const; + /// \brief Get a string representation of a region for debug use. + std::string getString() const; + virtual void dumpToStream(raw_ostream &os) const; void dump() const; + /// \brief Print the region for use in diagnostics. + virtual void dumpPretty(raw_ostream &os) const; + Kind getKind() const { return kind; } template<typename RegionTy> const RegionTy* getAs() const; @@ -150,7 +159,7 @@ public: static bool classof(const MemRegion*) { return true; } }; -/// MemSpaceRegion - A memory region that represents and "memory space"; +/// MemSpaceRegion - A memory region that represents a "memory space"; /// for example, the set of global variables, the stack frame, etc. class MemSpaceRegion : public MemRegion { protected: @@ -177,6 +186,7 @@ public: }; class GlobalsSpaceRegion : public MemSpaceRegion { + virtual void anchor(); protected: GlobalsSpaceRegion(MemRegionManager *mgr, Kind k) : MemSpaceRegion(mgr, k) {} @@ -186,7 +196,11 @@ public: return k >= BEG_GLOBAL_MEMSPACES && k <= END_GLOBAL_MEMSPACES; } }; - + +/// \class The region of the static variables within the current CodeTextRegion +/// scope. +/// Currently, only the static locals are placed there, so we know that these +/// variables do not get invalidated by calls to other functions. class StaticGlobalSpaceRegion : public GlobalsSpaceRegion { friend class MemRegionManager; @@ -206,23 +220,88 @@ public: return R->getKind() == StaticGlobalSpaceRegionKind; } }; - + +/// \class The region for all the non-static global variables. +/// +/// This class is further split into subclasses for efficient implementation of +/// invalidating a set of related global values as is done in +/// RegionStoreManager::invalidateRegions (instead of finding all the dependent +/// globals, we invalidate the whole parent region). class NonStaticGlobalSpaceRegion : public GlobalsSpaceRegion { friend class MemRegionManager; - NonStaticGlobalSpaceRegion(MemRegionManager *mgr) - : GlobalsSpaceRegion(mgr, NonStaticGlobalSpaceRegionKind) {} +protected: + NonStaticGlobalSpaceRegion(MemRegionManager *mgr, Kind k) + : GlobalsSpaceRegion(mgr, k) {} public: void dumpToStream(raw_ostream &os) const; static bool classof(const MemRegion *R) { - return R->getKind() == NonStaticGlobalSpaceRegionKind; + Kind k = R->getKind(); + return k >= BEG_NON_STATIC_GLOBAL_MEMSPACES && + k <= END_NON_STATIC_GLOBAL_MEMSPACES; } }; - + +/// \class The region containing globals which are defined in system/external +/// headers and are considered modifiable by system calls (ex: errno). +class GlobalSystemSpaceRegion : public NonStaticGlobalSpaceRegion { + friend class MemRegionManager; + + GlobalSystemSpaceRegion(MemRegionManager *mgr) + : NonStaticGlobalSpaceRegion(mgr, GlobalSystemSpaceRegionKind) {} + +public: + + void dumpToStream(raw_ostream &os) const; + + static bool classof(const MemRegion *R) { + return R->getKind() == GlobalSystemSpaceRegionKind; + } +}; + +/// \class The region containing globals which are considered not to be modified +/// or point to data which could be modified as a result of a function call +/// (system or internal). Ex: Const global scalars would be modeled as part of +/// this region. This region also includes most system globals since they have +/// low chance of being modified. +class GlobalImmutableSpaceRegion : public NonStaticGlobalSpaceRegion { + friend class MemRegionManager; + + GlobalImmutableSpaceRegion(MemRegionManager *mgr) + : NonStaticGlobalSpaceRegion(mgr, GlobalImmutableSpaceRegionKind) {} + +public: + + void dumpToStream(raw_ostream &os) const; + + static bool classof(const MemRegion *R) { + return R->getKind() == GlobalImmutableSpaceRegionKind; + } +}; + +/// \class The region containing globals which can be modified by calls to +/// "internally" defined functions - (for now just) functions other then system +/// calls. +class GlobalInternalSpaceRegion : public NonStaticGlobalSpaceRegion { + friend class MemRegionManager; + + GlobalInternalSpaceRegion(MemRegionManager *mgr) + : NonStaticGlobalSpaceRegion(mgr, GlobalInternalSpaceRegionKind) {} + +public: + + void dumpToStream(raw_ostream &os) const; + + static bool classof(const MemRegion *R) { + return R->getKind() == GlobalInternalSpaceRegionKind; + } +}; + class HeapSpaceRegion : public MemSpaceRegion { + virtual void anchor(); friend class MemRegionManager; HeapSpaceRegion(MemRegionManager *mgr) @@ -234,6 +313,7 @@ public: }; class UnknownSpaceRegion : public MemSpaceRegion { + virtual void anchor(); friend class MemRegionManager; UnknownSpaceRegion(MemRegionManager *mgr) : MemSpaceRegion(mgr, UnknownSpaceRegionKind) {} @@ -266,7 +346,7 @@ public: }; class StackLocalsSpaceRegion : public StackSpaceRegion { -private: + virtual void anchor(); friend class MemRegionManager; StackLocalsSpaceRegion(MemRegionManager *mgr, const StackFrameContext *sfc) : StackSpaceRegion(mgr, StackLocalsSpaceRegionKind, sfc) {} @@ -278,6 +358,7 @@ public: class StackArgumentsSpaceRegion : public StackSpaceRegion { private: + virtual void anchor(); friend class MemRegionManager; StackArgumentsSpaceRegion(MemRegionManager *mgr, const StackFrameContext *sfc) : StackSpaceRegion(mgr, StackArgumentsSpaceRegionKind, sfc) {} @@ -291,6 +372,8 @@ public: /// SubRegion - A region that subsets another larger region. Most regions /// are subclasses of SubRegion. class SubRegion : public MemRegion { +private: + virtual void anchor(); protected: const MemRegion* superRegion; SubRegion(const MemRegion* sReg, Kind k) : MemRegion(k), superRegion(sReg) {} @@ -351,6 +434,8 @@ public: /// TypedRegion - An abstract class representing regions that are typed. class TypedRegion : public SubRegion { +public: + virtual void anchor(); protected: TypedRegion(const MemRegion* sReg, Kind k) : SubRegion(sReg, k) {} @@ -371,6 +456,8 @@ public: /// TypedValueRegion - An abstract class representing regions having a typed value. class TypedValueRegion : public TypedRegion { +public: + virtual void anchor(); protected: TypedValueRegion(const MemRegion* sReg, Kind k) : TypedRegion(sReg, k) {} @@ -399,6 +486,8 @@ public: class CodeTextRegion : public TypedRegion { +public: + virtual void anchor(); protected: CodeTextRegion(const MemRegion *sreg, Kind k) : TypedRegion(sreg, k) {} public: @@ -448,11 +537,11 @@ class BlockTextRegion : public CodeTextRegion { friend class MemRegionManager; const BlockDecl *BD; - AnalysisContext *AC; + AnalysisDeclContext *AC; CanQualType locTy; BlockTextRegion(const BlockDecl *bd, CanQualType lTy, - AnalysisContext *ac, const MemRegion* sreg) + AnalysisDeclContext *ac, const MemRegion* sreg) : CodeTextRegion(sreg, BlockTextRegionKind), BD(bd), AC(ac), locTy(lTy) {} public: @@ -464,14 +553,14 @@ public: return BD; } - AnalysisContext *getAnalysisContext() const { return AC; } + AnalysisDeclContext *getAnalysisDeclContext() const { return AC; } virtual void dumpToStream(raw_ostream &os) const; void Profile(llvm::FoldingSetNodeID& ID) const; static void ProfileRegion(llvm::FoldingSetNodeID& ID, const BlockDecl *BD, - CanQualType, const AnalysisContext*, + CanQualType, const AnalysisDeclContext*, const MemRegion*); static bool classof(const MemRegion* R) { @@ -611,6 +700,40 @@ public: return R->getKind() == StringRegionKind; } }; + +/// The region associated with an ObjCStringLiteral. +class ObjCStringRegion : public TypedValueRegion { + friend class MemRegionManager; + const ObjCStringLiteral* Str; +protected: + + ObjCStringRegion(const ObjCStringLiteral* str, const MemRegion* sreg) + : TypedValueRegion(sreg, ObjCStringRegionKind), Str(str) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, + const ObjCStringLiteral* Str, + const MemRegion* superRegion); + +public: + + const ObjCStringLiteral* getObjCStringLiteral() const { return Str; } + + QualType getValueType() const { + return Str->getType(); + } + + bool isBoundable() const { return false; } + + void Profile(llvm::FoldingSetNodeID& ID) const { + ProfileRegion(ID, Str, superRegion); + } + + void dumpToStream(raw_ostream &os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == ObjCStringRegionKind; + } +}; /// CompoundLiteralRegion - A memory region representing a compound literal. /// Compound literals are essentially temporaries that are stack allocated @@ -695,6 +818,8 @@ public: static bool classof(const MemRegion* R) { return R->getKind() == VarRegionKind; } + + void dumpPretty(raw_ostream &os) const; }; /// CXXThisRegion - Represents the region for the implicit 'this' parameter @@ -734,9 +859,6 @@ class FieldRegion : public DeclRegion { : DeclRegion(fd, sReg, FieldRegionKind) {} public: - - void dumpToStream(raw_ostream &os) const; - const FieldDecl *getDecl() const { return cast<FieldDecl>(D); } QualType getValueType() const { @@ -754,23 +876,23 @@ public: static bool classof(const MemRegion* R) { return R->getKind() == FieldRegionKind; } + + void dumpToStream(raw_ostream &os) const; + void dumpPretty(raw_ostream &os) const; }; class ObjCIvarRegion : public DeclRegion { friend class MemRegionManager; - ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg) - : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {} + ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg); static void ProfileRegion(llvm::FoldingSetNodeID& ID, const ObjCIvarDecl *ivd, - const MemRegion* superRegion) { - DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind); - } + const MemRegion* superRegion); public: - const ObjCIvarDecl *getDecl() const { return cast<ObjCIvarDecl>(D); } - QualType getValueType() const { return getDecl()->getType(); } + const ObjCIvarDecl *getDecl() const; + QualType getValueType() const; void dumpToStream(raw_ostream &os) const; @@ -803,6 +925,7 @@ public: void dump() const; }; +/// \brief ElementRegin is used to represent both array elements and casts. class ElementRegion : public TypedValueRegion { friend class MemRegionManager; @@ -915,7 +1038,10 @@ class MemRegionManager { llvm::BumpPtrAllocator& A; llvm::FoldingSet<MemRegion> Regions; - NonStaticGlobalSpaceRegion *globals; + GlobalInternalSpaceRegion *InternalGlobals; + GlobalSystemSpaceRegion *SystemGlobals; + GlobalImmutableSpaceRegion *ImmutableGlobals; + llvm::DenseMap<const StackFrameContext *, StackLocalsSpaceRegion *> StackLocalsSpaceRegions; @@ -930,7 +1056,8 @@ class MemRegionManager { public: MemRegionManager(ASTContext &c, llvm::BumpPtrAllocator& a) - : C(c), A(a), globals(0), heap(0), unknown(0), code(0) {} + : C(c), A(a), InternalGlobals(0), SystemGlobals(0), ImmutableGlobals(0), + heap(0), unknown(0), code(0) {} ~MemRegionManager(); @@ -950,7 +1077,9 @@ public: /// getGlobalsRegion - Retrieve the memory region associated with /// global variables. - const GlobalsSpaceRegion *getGlobalsRegion(const CodeTextRegion *R = 0); + const GlobalsSpaceRegion *getGlobalsRegion( + MemRegion::Kind K = MemRegion::GlobalInternalSpaceRegionKind, + const CodeTextRegion *R = 0); /// getHeapRegion - Retrieve the memory region associated with the /// generic "heap". @@ -980,7 +1109,9 @@ public: /// getSymbolicRegion - Retrieve or create a "symbolic" memory region. const SymbolicRegion* getSymbolicRegion(SymbolRef sym); - const StringRegion* getStringRegion(const StringLiteral* Str); + const StringRegion *getStringRegion(const StringLiteral* Str); + + const ObjCStringRegion *getObjCStringRegion(const ObjCStringLiteral *Str); /// getVarRegion - Retrieve or create the memory region associated with /// a specified VarDecl and LocationContext. @@ -1038,7 +1169,7 @@ public: const FunctionTextRegion *getFunctionTextRegion(const FunctionDecl *FD); const BlockTextRegion *getBlockTextRegion(const BlockDecl *BD, CanQualType locTy, - AnalysisContext *AC); + AnalysisDeclContext *AC); /// getBlockDataRegion - Get the memory region associated with an instance /// of a block. Unlike many other MemRegions, the LocationContext* @@ -1047,11 +1178,6 @@ public: 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); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h index add3479..d8aec09 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h @@ -19,82 +19,72 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/AST/ExprObjC.h" #include "clang/AST/ExprCXX.h" +#include "clang/Basic/SourceManager.h" #include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Support/Compiler.h" namespace clang { namespace ento { +using llvm::StrInStrNoCase; /// \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) { } - + const ObjCMessageExpr *Msg; + const ObjCPropertyRefExpr *PE; + const bool IsPropSetter; public: - ObjCMessage() : MsgOrPropE(0), OriginE(0) { } + ObjCMessage() : Msg(0), PE(0), IsPropSetter(false) {} - ObjCMessage(const ObjCMessageExpr *E) - : MsgOrPropE(E), OriginE(E) { + ObjCMessage(const ObjCMessageExpr *E, const ObjCPropertyRefExpr *pe = 0, + bool isSetter = false) + : Msg(E), PE(pe), IsPropSetter(isSetter) { assert(E && "should not be initialized with null expression"); } - bool isValid() const { return MsgOrPropE != 0; } - bool isInvalid() const { return !isValid(); } + bool isValid() const { return Msg; } + + bool isPureMessageExpr() const { return !PE; } - bool isMessageExpr() const { - return isValid() && isa<ObjCMessageExpr>(MsgOrPropE); - } + bool isPropertyGetter() const { return PE && !IsPropSetter; } - bool isPropertyGetter() const { - return isValid() && - isa<ObjCPropertyRefExpr>(MsgOrPropE) && !IsPropSetter; + bool isPropertySetter() const { + return IsPropSetter; } - bool isPropertySetter() const { - return isValid() && - isa<ObjCPropertyRefExpr>(MsgOrPropE) && IsPropSetter; + const Expr *getMessageExpr() const { + return Msg; } - - const Expr *getOriginExpr() const { return OriginE; } - QualType getType(ASTContext &ctx) const; + QualType getType(ASTContext &ctx) const { + return Msg->getType(); + } 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(); + if (const ObjCMethodDecl *MD = Msg->getMethodDecl()) + return MD->getResultType(); return getType(ctx); } - ObjCMethodFamily getMethodFamily() const; + ObjCMethodFamily getMethodFamily() const { + return Msg->getMethodFamily(); + } - Selector getSelector() const; + Selector getSelector() const { + return Msg->getSelector(); + } 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; + return Msg->getInstanceReceiver(); } - SVal getInstanceReceiverSVal(const ProgramState *State, + SVal getInstanceReceiverSVal(ProgramStateRef State, const LocationContext *LC) const { - assert(isValid() && "This ObjCMessage is uninitialized!"); if (!isInstanceMessage()) return UndefinedVal(); if (const Expr *Ex = getInstanceReceiver()) - return State->getSValAsScalarOrLoc(Ex); + return State->getSValAsScalarOrLoc(Ex, LC); // An instance message with no expression means we are sending to super. // In this case the object reference is the same as 'self'. @@ -104,99 +94,66 @@ public: } 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(); + return Msg->isInstanceMessage(); } - 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(); + const ObjCMethodDecl *getMethodDecl() const { + return Msg->getMethodDecl(); } - const Expr *getMsgOrPropExpr() const { - assert(isValid() && "This ObjCMessage is uninitialized!"); - return MsgOrPropE; + const ObjCInterfaceDecl *getReceiverInterface() const { + return Msg->getReceiverInterface(); } - SourceRange getSourceRange() const { - assert(isValid() && "This ObjCMessage is uninitialized!"); - return MsgOrPropE->getSourceRange(); + SourceLocation getSuperLoc() const { + if (PE) + return PE->getReceiverLocation(); + return Msg->getSuperLoc(); + } + + SourceRange getSourceRange() const LLVM_READONLY { + if (PE) + return PE->getSourceRange(); + return Msg->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; + return Msg->getNumArgs(); } - SVal getArgSVal(unsigned i, const ProgramState *state) const { - assert(isValid() && "This ObjCMessage is uninitialized!"); + SVal getArgSVal(unsigned i, + const LocationContext *LCtx, + ProgramStateRef state) const { 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; + return state->getSVal(Msg->getArg(i), LCtx); } 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(); + return Msg->getArg(i)->getType(); } - const Expr *getArgExpr(unsigned i) const; + const Expr *getArgExpr(unsigned i) const { + assert(i < getNumArgs() && "Invalid index for argument"); + return Msg->getArg(i); + } 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(); + const Expr *argE = getArgExpr(i); + return argE->getSourceRange(); } SourceRange getReceiverSourceRange() const { - assert(isValid() && "This ObjCMessage is uninitialized!"); - if (const ObjCMessageExpr *msgE = dyn_cast<ObjCMessageExpr>(MsgOrPropE)) - return msgE->getReceiverRange(); - - const ObjCPropertyRefExpr *propE = cast<ObjCPropertyRefExpr>(MsgOrPropE); - if (propE->isObjectReceiver()) - return propE->getBase()->getSourceRange(); + if (PE) { + if (PE->isObjectReceiver()) + return PE->getBase()->getSourceRange(); + } + else { + return Msg->getReceiverRange(); + } // FIXME: This isn't a range. - return propE->getReceiverLocation(); - } -}; - -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"); + return PE->getReceiverLocation(); } }; @@ -205,14 +162,18 @@ public: class CallOrObjCMessage { llvm::PointerUnion<const CallExpr *, const CXXConstructExpr *> CallE; ObjCMessage Msg; - const ProgramState *State; + ProgramStateRef State; + const LocationContext *LCtx; public: - CallOrObjCMessage(const CallExpr *callE, const ProgramState *state) - : CallE(callE), State(state) {} - CallOrObjCMessage(const CXXConstructExpr *consE, const ProgramState *state) - : CallE(consE), State(state) {} - CallOrObjCMessage(const ObjCMessage &msg, const ProgramState *state) - : CallE((CallExpr *)0), Msg(msg), State(state) {} + CallOrObjCMessage(const CallExpr *callE, ProgramStateRef state, + const LocationContext *lctx) + : CallE(callE), State(state), LCtx(lctx) {} + CallOrObjCMessage(const CXXConstructExpr *consE, ProgramStateRef state, + const LocationContext *lctx) + : CallE(consE), State(state), LCtx(lctx) {} + CallOrObjCMessage(const ObjCMessage &msg, ProgramStateRef state, + const LocationContext *lctx) + : CallE((CallExpr *)0), Msg(msg), State(state), LCtx(lctx) {} QualType getResultType(ASTContext &ctx) const; @@ -233,9 +194,19 @@ public: return ActualCallE && isa<CXXMemberCallExpr>(ActualCallE); } + /// Check if the callee is declared in the system header. + bool isInSystemHeader() const { + if (const Decl *FD = getDecl()) { + const SourceManager &SM = + State->getStateManager().getContext().getSourceManager(); + return SM.isInSystemHeader(FD->getLocation()); + } + return false; + } + const Expr *getOriginExpr() const { if (!CallE) - return Msg.getOriginExpr(); + return Msg.getMessageExpr(); if (const CXXConstructExpr *Ctor = CallE.dyn_cast<const CXXConstructExpr *>()) return Ctor; @@ -246,6 +217,9 @@ public: SVal getCXXCallee() const; SVal getInstanceMessageReceiver(const LocationContext *LC) const; + /// Get the declaration of the function or method. + const Decl *getDecl() const; + unsigned getNumArgs() const { if (!CallE) return Msg.getNumArgs(); @@ -258,8 +232,8 @@ public: SVal getArgSVal(unsigned i) const { assert(i < getNumArgs()); if (!CallE) - return Msg.getArgSVal(i, State); - return State->getSVal(getArg(i)); + return Msg.getArgSVal(i, LCtx, State); + return State->getSVal(getArg(i), LCtx); } const Expr *getArg(unsigned i) const { @@ -283,6 +257,34 @@ public: assert(isObjCMessage()); return Msg.getReceiverSourceRange(); } + + /// \brief Check if the name corresponds to a CoreFoundation or CoreGraphics + /// function that allows objects to escape. + /// + /// Many methods allow a tracked object to escape. For example: + /// + /// CFMutableDictionaryRef x = CFDictionaryCreateMutable(..., customDeallocator); + /// CFDictionaryAddValue(y, key, x); + /// + /// We handle this and similar cases with the following heuristic. If the + /// function name contains "InsertValue", "SetValue", "AddValue", + /// "AppendValue", or "SetAttribute", then we assume that arguments may + /// escape. + // + // TODO: To reduce false negatives here, we should track the container + // allocation site and check if a proper deallocator was set there. + static bool isCFCGAllowingEscape(StringRef FName) { + if (FName[0] == 'C' && (FName[1] == 'F' || FName[1] == 'G')) + if (StrInStrNoCase(FName, "InsertValue") != StringRef::npos|| + StrInStrNoCase(FName, "AddValue") != StringRef::npos || + StrInStrNoCase(FName, "SetValue") != StringRef::npos || + StrInStrNoCase(FName, "WithData") != StringRef::npos || + StrInStrNoCase(FName, "AppendValue") != StringRef::npos|| + StrInStrNoCase(FName, "SetAttribute") != StringRef::npos) { + return true; + } + return false; + } }; } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h index edae06e..360d648 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -19,6 +19,8 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableMap.h" @@ -33,7 +35,7 @@ class ASTContext; namespace ento { -class ProgramStateManager; +class CallOrObjCMessage; typedef ConstraintManager* (*ConstraintManagerCreator)(ProgramStateManager&, SubEngine&); @@ -54,8 +56,6 @@ template <typename T> struct ProgramStateTrait { } }; -class ProgramStateManager; - /// \class ProgramState /// ProgramState - This class encapsulates: /// @@ -88,12 +88,11 @@ private: /// makeWithStore - Return a ProgramState with the same values as the current /// state with the exception of using the specified Store. - const ProgramState *makeWithStore(const StoreRef &store) const; + ProgramStateRef makeWithStore(const StoreRef &store) const; void setStore(const StoreRef &storeRef); public: - /// This ctor is used when creating the first ProgramState object. ProgramState(ProgramStateManager *mgr, const Environment& env, StoreRef st, GenericDataMap gdm); @@ -107,9 +106,6 @@ public: /// Return the ProgramStateManager associated with this state. ProgramStateManager &getStateManager() const { return *stateMgr; } - /// Return true if this state is referenced by a persistent ExplodedNode. - bool referencedByExplodedNode() const { return refCount > 0; } - /// getEnvironment - Return the environment associated with this state. /// The environment is the mapping from expressions to values. const Environment& getEnvironment() const { return Env; } @@ -168,17 +164,18 @@ public: // If no new state is feasible, NULL is returned. // - const ProgramState *assume(DefinedOrUnknownSVal cond, bool assumption) const; + ProgramStateRef 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 ProgramState*, const ProgramState*> + std::pair<ProgramStateRef , ProgramStateRef > assume(DefinedOrUnknownSVal cond) const; - const ProgramState *assumeInBound(DefinedOrUnknownSVal idx, + ProgramStateRef assumeInBound(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, - bool assumption) const; + bool assumption, + QualType IndexType = QualType()) const; /// Utility method for getting regions. const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; @@ -189,49 +186,50 @@ public: /// BindCompoundLiteral - Return the state that has the bindings currently /// in this state plus the bindings for the CompoundLiteral. - const ProgramState *bindCompoundLiteral(const CompoundLiteralExpr *CL, + ProgramStateRef 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 ProgramState *BindExpr(const Stmt *S, SVal V, bool Invalidate = true) const; + ProgramStateRef BindExpr(const Stmt *S, const LocationContext *LCtx, + 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 ProgramState *bindExprAndLocation(const Stmt *S, SVal location, SVal V) - const; + ProgramStateRef bindExprAndLocation(const Stmt *S, + const LocationContext *LCtx, + SVal location, SVal V) const; - const ProgramState *bindDecl(const VarRegion *VR, SVal V) const; + ProgramStateRef bindDecl(const VarRegion *VR, SVal V) const; - const ProgramState *bindDeclWithNoInit(const VarRegion *VR) const; + ProgramStateRef bindDeclWithNoInit(const VarRegion *VR) const; - const ProgramState *bindLoc(Loc location, SVal V) const; + ProgramStateRef bindLoc(Loc location, SVal V) const; - const ProgramState *bindLoc(SVal location, SVal V) const; + ProgramStateRef bindLoc(SVal location, SVal V) const; - const ProgramState *bindDefault(SVal loc, SVal V) const; + ProgramStateRef bindDefault(SVal loc, SVal V) const; - const ProgramState *unbindLoc(Loc LV) const; + ProgramStateRef unbindLoc(Loc LV) const; /// invalidateRegions - Returns the state with bindings for the given regions /// cleared from the store. The regions are provided as a continuous array /// from Begin to End. Optionally invalidates global regions as well. - const ProgramState *invalidateRegions(ArrayRef<const MemRegion *> Regions, - const Expr *E, unsigned BlockCount, - StoreManager::InvalidatedSymbols *IS = 0, - bool invalidateGlobals = false) const; + ProgramStateRef invalidateRegions(ArrayRef<const MemRegion *> Regions, + const Expr *E, unsigned BlockCount, + const LocationContext *LCtx, + StoreManager::InvalidatedSymbols *IS = 0, + const CallOrObjCMessage *Call = 0) const; /// enterStackFrame - Returns the state for entry to the given stack frame, /// preserving the current state. - const ProgramState *enterStackFrame(const StackFrameContext *frame) const; + ProgramStateRef enterStackFrame(const LocationContext *callerCtx, + const StackFrameContext *calleeCtx) 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; @@ -247,15 +245,20 @@ public: const llvm::APSInt *getSymVal(SymbolRef sym) const; /// Returns the SVal bound to the statement 'S' in the state's environment. - SVal getSVal(const Stmt *S, bool useOnlyDirectBindings = false) const; + SVal getSVal(const Stmt *S, const LocationContext *LCtx, + bool useOnlyDirectBindings = false) const; - SVal getSValAsScalarOrLoc(const Stmt *Ex) const; + SVal getSValAsScalarOrLoc(const Stmt *Ex, const LocationContext *LCtx) const; + /// \brief Return the value bound to the specified location. + /// Returns UnknownVal() if none found. 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; + /// \brief Return the value bound to the specified location. + /// Returns UnknownVal() if none found. SVal getSVal(const MemRegion* R) const; SVal getSValAsScalarOrLoc(const MemRegion *R) const; @@ -288,6 +291,25 @@ public: scanReachableSymbols(const MemRegion * const *beg, const MemRegion * const *end) const; + /// Create a new state in which the statement is marked as tainted. + ProgramStateRef addTaint(const Stmt *S, const LocationContext *LCtx, + TaintTagType Kind = TaintTagGeneric) const; + + /// Create a new state in which the symbol is marked as tainted. + ProgramStateRef addTaint(SymbolRef S, + TaintTagType Kind = TaintTagGeneric) const; + + /// Create a new state in which the region symbol is marked as tainted. + ProgramStateRef addTaint(const MemRegion *R, + TaintTagType Kind = TaintTagGeneric) const; + + /// Check if the statement is tainted in the current state. + bool isTainted(const Stmt *S, const LocationContext *LCtx, + TaintTagType Kind = TaintTagGeneric) const; + bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const; + bool isTainted(SymbolRef Sym, TaintTagType Kind = TaintTagGeneric) const; + bool isTainted(const MemRegion *Reg, TaintTagType Kind=TaintTagGeneric) const; + //==---------------------------------------------------------------------==// // Accessing the Generic Data Map (GDM). //==---------------------------------------------------------------------==// @@ -295,7 +317,7 @@ public: void *const* FindGDM(void *K) const; template<typename T> - const ProgramState *add(typename ProgramStateTrait<T>::key_type K) const; + ProgramStateRef add(typename ProgramStateTrait<T>::key_type K) const; template <typename T> typename ProgramStateTrait<T>::data_type @@ -315,23 +337,23 @@ public: template<typename T> - const ProgramState *remove(typename ProgramStateTrait<T>::key_type K) const; + ProgramStateRef remove(typename ProgramStateTrait<T>::key_type K) const; template<typename T> - const ProgramState *remove(typename ProgramStateTrait<T>::key_type K, + ProgramStateRef remove(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::context_type C) const; template <typename T> - const ProgramState *remove() const; + ProgramStateRef remove() const; template<typename T> - const ProgramState *set(typename ProgramStateTrait<T>::data_type D) const; + ProgramStateRef set(typename ProgramStateTrait<T>::data_type D) const; template<typename T> - const ProgramState *set(typename ProgramStateTrait<T>::key_type K, + ProgramStateRef set(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::value_type E) const; template<typename T> - const ProgramState *set(typename ProgramStateTrait<T>::key_type K, + ProgramStateRef set(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::value_type E, typename ProgramStateTrait<T>::context_type C) const; @@ -342,61 +364,25 @@ public: } // Pretty-printing. - void print(raw_ostream &Out, CFG &C, const char *nl = "\n", + void print(raw_ostream &Out, const char *nl = "\n", const char *sep = "") const; + void printDOT(raw_ostream &Out) const; + void printTaint(raw_ostream &Out, const char *nl = "\n", + const char *sep = "") const; - void printStdErr(CFG &C) const; - - void printDOT(raw_ostream &Out, CFG &C) const; + void dump() const; + void dumpTaint() 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; - } + friend void ProgramStateRetain(const ProgramState *state); + friend void ProgramStateRelease(const ProgramState *state); - const ProgramState * + ProgramStateRef invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, const Expr *E, unsigned BlockCount, + const LocationContext *LCtx, StoreManager::InvalidatedSymbols &IS, - bool invalidateGlobals) const; -}; - -class ProgramStateSet { - typedef llvm::SmallPtrSet<const ProgramState*,5> ImplTy; - ImplTy Impl; -public: - ProgramStateSet() {} - - inline void Add(const ProgramState *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 { - ProgramStateSet &S; - unsigned StartSize; - const ProgramState *St; - public: - AutoPopulate(ProgramStateSet &s, const ProgramState *st) - : S(s), StartSize(S.size()), St(st) {} - - ~AutoPopulate() { - if (StartSize == S.size()) - S.Add(St); - } - }; + const CallOrObjCMessage *Call) const; }; //===----------------------------------------------------------------------===// @@ -405,13 +391,14 @@ public: class ProgramStateManager { friend class ProgramState; + friend void ProgramStateRelease(const ProgramState *state); private: /// Eng - The SubEngine that owns this state manager. SubEngine *Eng; /* Can be null. */ EnvironmentManager EnvMgr; - llvm::OwningPtr<StoreManager> StoreMgr; - llvm::OwningPtr<ConstraintManager> ConstraintMgr; + OwningPtr<StoreManager> StoreMgr; + OwningPtr<ConstraintManager> ConstraintMgr; ProgramState::GenericDataMap::Factory GDMFactory; @@ -423,14 +410,10 @@ private: llvm::FoldingSet<ProgramState> StateSet; /// Object that manages the data for all created SVals. - llvm::OwningPtr<SValBuilder> svalBuilder; + OwningPtr<SValBuilder> svalBuilder; /// A BumpPtrAllocator to allocate states. llvm::BumpPtrAllocator &Alloc; - - /// A vector of recently allocated ProgramStates that can potentially be - /// reused. - std::vector<ProgramState *> recentlyAllocatedStates; /// A vector of ProgramStates that we can reuse. std::vector<ProgramState *> freeStates; @@ -465,7 +448,7 @@ public: ~ProgramStateManager(); - const ProgramState *getInitialState(const LocationContext *InitLoc); + ProgramStateRef getInitialState(const LocationContext *InitLoc); ASTContext &getContext() { return svalBuilder->getContext(); } const ASTContext &getContext() const { return svalBuilder->getContext(); } @@ -501,13 +484,13 @@ public: ConstraintManager& getConstraintManager() { return *ConstraintMgr; } SubEngine* getOwningEngine() { return Eng; } - const ProgramState *removeDeadBindings(const ProgramState *St, + ProgramStateRef removeDeadBindings(ProgramStateRef 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 ProgramState *MarshalState(const ProgramState *state, const StackFrameContext *L); + ProgramStateRef MarshalState(ProgramStateRef state, const StackFrameContext *L); public: @@ -516,31 +499,27 @@ public: } // Methods that manipulate the GDM. - const ProgramState *addGDM(const ProgramState *St, void *Key, void *Data); - const ProgramState *removeGDM(const ProgramState *state, void *Key); + ProgramStateRef addGDM(ProgramStateRef St, void *Key, void *Data); + ProgramStateRef removeGDM(ProgramStateRef state, void *Key); // Methods that query & manipulate the Store. - void iterBindings(const ProgramState *state, StoreManager::BindingsHandler& F) { + void iterBindings(ProgramStateRef state, StoreManager::BindingsHandler& F) { StoreMgr->iterBindings(state->getStore(), F); } - const ProgramState *getPersistentState(ProgramState &Impl); - const ProgramState *getPersistentStateWithGDM(const ProgramState *FromState, - const ProgramState *GDMState); + ProgramStateRef getPersistentState(ProgramState &Impl); + ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, + ProgramStateRef GDMState); - bool haveEqualEnvironments(const ProgramState * S1, const ProgramState * S2) { + bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) { return S1->Env == S2->Env; } - bool haveEqualStores(const ProgramState * S1, const ProgramState * S2) { + bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) { return S1->store == S2->store; } - /// Periodically called by ExprEngine to recycle ProgramStates that were - /// created but never used for creating an ExplodedNode. - void recycleUnusedStates(); - //==---------------------------------------------------------------------==// // Generic Data Map methods. //==---------------------------------------------------------------------==// @@ -561,13 +540,13 @@ public: // Trait based GDM dispatch. template <typename T> - const ProgramState *set(const ProgramState *st, typename ProgramStateTrait<T>::data_type D) { + ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait<T>::data_type D) { return addGDM(st, ProgramStateTrait<T>::GDMIndex(), ProgramStateTrait<T>::MakeVoidPtr(D)); } template<typename T> - const ProgramState *set(const ProgramState *st, + ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::value_type V, typename ProgramStateTrait<T>::context_type C) { @@ -577,7 +556,7 @@ public: } template <typename T> - const ProgramState *add(const ProgramState *st, + ProgramStateRef add(ProgramStateRef st, typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::context_type C) { return addGDM(st, ProgramStateTrait<T>::GDMIndex(), @@ -585,7 +564,7 @@ public: } template <typename T> - const ProgramState *remove(const ProgramState *st, + ProgramStateRef remove(ProgramStateRef st, typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::context_type C) { @@ -594,7 +573,7 @@ public: } template <typename T> - const ProgramState *remove(const ProgramState *st) { + ProgramStateRef remove(ProgramStateRef st) { return removeGDM(st, ProgramStateTrait<T>::GDMIndex()); } @@ -611,11 +590,11 @@ public: return ProgramStateTrait<T>::MakeContext(p); } - const llvm::APSInt* getSymVal(const ProgramState *St, SymbolRef sym) { + const llvm::APSInt* getSymVal(ProgramStateRef St, SymbolRef sym) { return ConstraintMgr->getSymVal(St, sym); } - void EndPath(const ProgramState *St) { + void EndPath(ProgramStateRef St) { ConstraintMgr->EndPath(St); } }; @@ -626,11 +605,12 @@ public: //===----------------------------------------------------------------------===// inline const VarRegion* ProgramState::getRegion(const VarDecl *D, - const LocationContext *LC) const { + const LocationContext *LC) const +{ return getStateManager().getRegionManager().getVarRegion(D, LC); } -inline const ProgramState *ProgramState::assume(DefinedOrUnknownSVal Cond, +inline ProgramStateRef ProgramState::assume(DefinedOrUnknownSVal Cond, bool Assumption) const { if (Cond.isUnknown()) return this; @@ -639,7 +619,7 @@ inline const ProgramState *ProgramState::assume(DefinedOrUnknownSVal Cond, Assumption); } -inline std::pair<const ProgramState*, const ProgramState*> +inline std::pair<ProgramStateRef , ProgramStateRef > ProgramState::assume(DefinedOrUnknownSVal Cond) const { if (Cond.isUnknown()) return std::make_pair(this, this); @@ -648,7 +628,7 @@ ProgramState::assume(DefinedOrUnknownSVal Cond) const { cast<DefinedSVal>(Cond)); } -inline const ProgramState *ProgramState::bindLoc(SVal LV, SVal V) const { +inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V) const { return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V); } @@ -657,10 +637,6 @@ inline Loc ProgramState::getLValue(const VarDecl *VD, return getStateManager().StoreMgr->getLValueVar(VD, LC); } -inline Loc ProgramState::getLValue(const StringLiteral *literal) const { - return getStateManager().StoreMgr->getLValueString(literal); -} - inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal, const LocationContext *LC) const { return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); @@ -684,27 +660,32 @@ inline const llvm::APSInt *ProgramState::getSymVal(SymbolRef sym) const { return getStateManager().getSymVal(this, sym); } -inline SVal ProgramState::getSVal(const Stmt *Ex, bool useOnlyDirectBindings) const{ - return Env.getSVal(Ex, *getStateManager().svalBuilder, +inline SVal ProgramState::getSVal(const Stmt *Ex, const LocationContext *LCtx, + bool useOnlyDirectBindings) const{ + return Env.getSVal(EnvironmentEntry(Ex, LCtx), + *getStateManager().svalBuilder, useOnlyDirectBindings); } -inline SVal ProgramState::getSValAsScalarOrLoc(const Stmt *S) const { +inline SVal +ProgramState::getSValAsScalarOrLoc(const Stmt *S, + const LocationContext *LCtx) const { if (const Expr *Ex = dyn_cast<Expr>(S)) { QualType T = Ex->getType(); if (Ex->isLValue() || Loc::isLocType(T) || T->isIntegerType()) - return getSVal(S); + return getSVal(S, LCtx); } return UnknownVal(); } inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const { - return getStateManager().StoreMgr->Retrieve(getStore(), LV, T); + return getStateManager().StoreMgr->getBinding(getStore(), LV, T); } inline SVal ProgramState::getSVal(const MemRegion* R) const { - return getStateManager().StoreMgr->Retrieve(getStore(), loc::MemRegionVal(R)); + return getStateManager().StoreMgr->getBinding(getStore(), + loc::MemRegionVal(R)); } inline BasicValueFactory &ProgramState::getBasicVals() const { @@ -716,7 +697,7 @@ inline SymbolManager &ProgramState::getSymbolManager() const { } template<typename T> -const ProgramState *ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { +ProgramStateRef ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { return getStateManager().add<T>(this, K, get_context<T>()); } @@ -726,34 +707,34 @@ typename ProgramStateTrait<T>::context_type ProgramState::get_context() const { } template<typename T> -const ProgramState *ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { +ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { return getStateManager().remove<T>(this, K, get_context<T>()); } template<typename T> -const ProgramState *ProgramState::remove(typename ProgramStateTrait<T>::key_type K, +ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::context_type C) const { return getStateManager().remove<T>(this, K, C); } template <typename T> -const ProgramState *ProgramState::remove() const { +ProgramStateRef ProgramState::remove() const { return getStateManager().remove<T>(this); } template<typename T> -const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { +ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { return getStateManager().set<T>(this, D); } template<typename T> -const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::key_type K, +ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::value_type E) const { return getStateManager().set<T>(this, K, E, get_context<T>()); } template<typename T> -const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::key_type K, +ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::value_type E, typename ProgramStateTrait<T>::context_type C) const { return getStateManager().set<T>(this, K, E, C); @@ -785,15 +766,16 @@ CB ProgramState::scanReachableSymbols(const MemRegion * const *beg, /// A Utility class that allows to visit the reachable symbols using a custom /// SymbolVisitor. class ScanReachableSymbols : public SubRegionMap::Visitor { + virtual void anchor(); typedef llvm::DenseMap<const void*, unsigned> VisitedItems; VisitedItems visited; - const ProgramState *state; + ProgramStateRef state; SymbolVisitor &visitor; - llvm::OwningPtr<SubRegionMap> SRM; + OwningPtr<SubRegionMap> SRM; public: - ScanReachableSymbols(const ProgramState *st, SymbolVisitor& v) + ScanReachableSymbols(ProgramStateRef st, SymbolVisitor& v) : state(st), visitor(v) {} bool scan(nonloc::CompoundVal val); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h index b80d494..1c7bedb 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h @@ -9,8 +9,8 @@ // // This file defines partial implementations of template specializations of // the class ProgramStateTrait<>. ProgramStateTrait<> is used by ProgramState -// to implement set/get methods for mapulating a ProgramState's -// generic data map. +// to implement set/get methods for manipulating a ProgramState's +// generic data map. // //===----------------------------------------------------------------------===// @@ -176,7 +176,20 @@ namespace ento { return (void*) (uintptr_t) d; } }; - + + // Partial specialization for void*. + template <> struct ProgramStatePartialTrait<void*> { + typedef void *data_type; + + static inline data_type MakeData(void *const* p) { + return p ? *p + : data_type(); + } + static inline void *MakeVoidPtr(data_type d) { + return d; + } + }; + } // end GR namespace } // end clang namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h new file mode 100644 index 0000000..371f3c5 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h @@ -0,0 +1,43 @@ +//== ProgramState_Fwd.h - Incomplete declarations of ProgramState -*- 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_PROGRAMSTATE_FWD_H +#define LLVM_CLANG_PROGRAMSTATE_FWD_H + +#include "clang/Basic/LLVM.h" +#include "llvm/ADT/IntrusiveRefCntPtr.h" + +namespace clang { +namespace ento { + class ProgramState; + class ProgramStateManager; + void ProgramStateRetain(const ProgramState *state); + void ProgramStateRelease(const ProgramState *state); +} +} + +namespace llvm { + template <> struct IntrusiveRefCntPtrInfo<const clang::ento::ProgramState> { + static void retain(const clang::ento::ProgramState *state) { + clang::ento::ProgramStateRetain(state); + } + static void release(const clang::ento::ProgramState *state) { + clang::ento::ProgramStateRelease(state); + } + }; +} + +namespace clang { +namespace ento { + typedef IntrusiveRefCntPtr<const ProgramState> ProgramStateRef; +} +} + +#endif + diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h index 17233e1..4ad36f9 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -17,17 +17,19 @@ #include "clang/AST/Expr.h" #include "clang/AST/ExprCXX.h" +#include "clang/AST/ExprObjC.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 CXXBoolLiteralExpr; -class ProgramState; +namespace ento { class SValBuilder { + virtual void anchor(); protected: ASTContext &Context; @@ -48,11 +50,13 @@ protected: /// The width of the scalar type used for array indices. const unsigned ArrayIndexWidth; + virtual SVal evalCastFromNonLoc(NonLoc val, QualType castTy) = 0; + virtual SVal evalCastFromLoc(Loc val, QualType castTy) = 0; + public: // FIXME: Make these protected again once RegionStoreManager correctly // handles loads from different bound value types. - virtual SVal evalCastFromNonLoc(NonLoc val, QualType castTy) = 0; - virtual SVal evalCastFromLoc(Loc val, QualType castTy) = 0; + virtual SVal dispatchCast(SVal val, QualType castTy) = 0; public: SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, @@ -66,29 +70,54 @@ public: virtual ~SValBuilder() {} + bool haveSameType(const SymExpr *Sym1, const SymExpr *Sym2) { + return haveSameType(Sym1->getType(Context), Sym2->getType(Context)); + } + + bool haveSameType(QualType Ty1, QualType Ty2) { + // FIXME: Remove the second disjunct when we support symbolic + // truncation/extension. + return (Context.getCanonicalType(Ty1) == Context.getCanonicalType(Ty2) || + (Ty2->isIntegerType() && Ty2->isIntegerType())); + } + SVal evalCast(SVal val, QualType castTy, QualType originalType); virtual SVal evalMinus(NonLoc val) = 0; virtual SVal evalComplement(NonLoc val) = 0; - virtual SVal evalBinOpNN(const ProgramState *state, BinaryOperator::Opcode op, + /// Create a new value which represents a binary expression with two non + /// location operands. + virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy) = 0; - virtual SVal evalBinOpLL(const ProgramState *state, BinaryOperator::Opcode op, + /// Create a new value which represents a binary expression with two memory + /// location operands. + virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, Loc lhs, Loc rhs, QualType resultTy) = 0; - virtual SVal evalBinOpLN(const ProgramState *state, BinaryOperator::Opcode op, + /// Create a new value which represents a binary expression with a memory + /// location and non location operands. For example, this would be used to + /// evaluate a pointer arithmetic operation. + virtual SVal evalBinOpLN(ProgramStateRef 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 ProgramState *state, SVal val) = 0; + /// 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(ProgramStateRef state, SVal val) = 0; - SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op, + /// Handles generation of the value in case the builder is not smart enough to + /// handle the given binary expression. Depending on the state, decides to + /// either keep the expression or forget the history and generate an + /// UnknownVal. + SVal makeGenericVal(ProgramStateRef state, BinaryOperator::Opcode op, + NonLoc lhs, NonLoc rhs, QualType resultTy); + + SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type); - DefinedOrUnknownSVal evalEQ(const ProgramState *state, DefinedOrUnknownSVal lhs, + DefinedOrUnknownSVal evalEQ(ProgramStateRef state, DefinedOrUnknownSVal lhs, DefinedOrUnknownSVal rhs); ASTContext &getContext() { return Context; } @@ -115,28 +144,47 @@ public: // Forwarding methods to SymbolManager. - const SymbolConjured* getConjuredSymbol(const Stmt *stmt, QualType type, + const SymbolConjured* getConjuredSymbol(const Stmt *stmt, + const LocationContext *LCtx, + QualType type, unsigned visitCount, const void *symbolTag = 0) { - return SymMgr.getConjuredSymbol(stmt, type, visitCount, symbolTag); + return SymMgr.getConjuredSymbol(stmt, LCtx, type, visitCount, symbolTag); } - const SymbolConjured* getConjuredSymbol(const Expr *expr, unsigned visitCount, + const SymbolConjured* getConjuredSymbol(const Expr *expr, + const LocationContext *LCtx, + unsigned visitCount, const void *symbolTag = 0) { - return SymMgr.getConjuredSymbol(expr, visitCount, symbolTag); + return SymMgr.getConjuredSymbol(expr, LCtx, visitCount, symbolTag); } - /// makeZeroVal - Construct an SVal representing '0' for the specified type. + /// Construct an SVal representing '0' for the specified type. DefinedOrUnknownSVal makeZeroVal(QualType type); - /// getRegionValueSymbolVal - make a unique symbol for value of region. + /// Make a unique symbol for value of region. DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedValueRegion *region); + /// \brief Create a new symbol with a unique 'name'. + /// + /// We resort to conjured symbols when we cannot construct a derived symbol. + /// The advantage of symbols derived/built from other symbols is that we + /// preserve the relation between related(or even equivalent) expressions, so + /// conjured symbols should be used sparingly. DefinedOrUnknownSVal getConjuredSymbolVal(const void *symbolTag, - const Expr *expr, unsigned count); + const Expr *expr, + const LocationContext *LCtx, + unsigned count); DefinedOrUnknownSVal getConjuredSymbolVal(const void *symbolTag, - const Expr *expr, QualType type, + const Expr *expr, + const LocationContext *LCtx, + QualType type, unsigned count); + + DefinedOrUnknownSVal getConjuredSymbolVal(const Stmt *stmt, + const LocationContext *LCtx, + QualType type, + unsigned visitCount); DefinedOrUnknownSVal getDerivedRegionValueSymbolVal( SymbolRef parentSymbol, const TypedValueRegion *region); @@ -175,11 +223,13 @@ public: BasicVals.getValue(integer->getValue(), integer->getType()->isUnsignedIntegerOrEnumerationType())); } - - nonloc::ConcreteInt makeBoolVal(const CXXBoolLiteralExpr *boolean) { - return makeTruthVal(boolean->getValue()); + + nonloc::ConcreteInt makeBoolVal(const ObjCBoolLiteralExpr *boolean) { + return makeTruthVal(boolean->getValue(), boolean->getType()); } + nonloc::ConcreteInt makeBoolVal(const CXXBoolLiteralExpr *boolean); + nonloc::ConcreteInt makeIntVal(const llvm::APSInt& integer) { return nonloc::ConcreteInt(BasicVals.getValue(integer)); } @@ -220,9 +270,15 @@ public: NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, const llvm::APSInt& rhs, QualType type); + NonLoc makeNonLoc(const llvm::APSInt& rhs, BinaryOperator::Opcode op, + const SymExpr *lhs, QualType type); + NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType type); + /// \brief Create a NonLoc value for cast. + NonLoc makeNonLoc(const SymExpr *operand, QualType fromTy, QualType toTy); + nonloc::ConcreteInt makeTruthVal(bool b, QualType type) { return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type)); } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h index 5827b00..ed01db2 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -17,6 +17,7 @@ #include "clang/Basic/LLVM.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" #include "llvm/ADT/ImmutableList.h" //==------------------------------------------------------------------------==// @@ -121,50 +122,39 @@ public: /// 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. + /// If this SVal is a location (subclasses Loc) and + /// wraps a symbol, return that SymbolRef. Otherwise return 0. 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. + /// If this SVal wraps a symbol return that SymbolRef. + /// Otherwise, return 0. SymbolRef getAsSymbol() const; /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then /// return that expression. Otherwise return NULL. const SymExpr *getAsSymbolicExpression() const; + const SymExpr* getAsSymExpr() const; + const MemRegion *getAsRegion() const; void dumpToStream(raw_ostream &OS) const; void dump() const; - // Iterators. - class symbol_iterator { - 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 { + SymExpr::symbol_iterator symbol_begin() const { const SymExpr *SE = getAsSymbolicExpression(); if (SE) - return symbol_iterator(SE); + return SE->symbol_begin(); else - return symbol_iterator(); + return SymExpr::symbol_iterator(); } - symbol_iterator symbol_end() const { return symbol_iterator(); } + SymExpr::symbol_iterator symbol_end() const { + return SymExpr::symbol_end(); + } // Implement isa<T> support. static inline bool classof(const SVal*) { return true; } @@ -274,43 +264,30 @@ namespace nonloc { enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; +/// \brief Represents symbolic expression. 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; + return (const SymExpr*) Data; } -}; - -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); + bool isExpression() { + return !isa<SymbolData>(getSymbol()); } static inline bool classof(const SVal* V) { return V->getBaseKind() == NonLocKind && - V->getSubKind() == SymExprValKind; + V->getSubKind() == SymbolValKind; } static inline bool classof(const NonLoc* V) { - return V->getSubKind() == SymExprValKind; + return V->getSubKind() == SymbolValKind; } }; +/// \brief Value representing integer constant. class ConcreteInt : public NonLoc { public: explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h index a688d7f..5315f4b 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h @@ -29,6 +29,7 @@ class StackFrameContext; namespace ento { +class CallOrObjCMessage; class ProgramState; class ProgramStateManager; class SubRegionMap; @@ -54,7 +55,7 @@ public: /// 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; + virtual SVal getBinding(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. @@ -93,18 +94,12 @@ public: 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 getLValueIvar(const ObjCIvarDecl *decl, SVal base); virtual SVal getLValueField(const FieldDecl *D, SVal Base) { return getLValueFieldOrIvar(D, Base); @@ -114,7 +109,7 @@ public: // FIXME: This should soon be eliminated altogether; clients should deal with // region extents directly. - virtual DefinedOrUnknownSVal getSizeInElements(const ProgramState *state, + virtual DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, const MemRegion *region, QualType EleTy) { return UnknownVal(); @@ -125,17 +120,26 @@ public: virtual SVal ArrayToPointer(Loc Array) = 0; /// Evaluates DerivedToBase casts. - virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType) { - return UnknownVal(); - } + virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType) = 0; + + /// \brief Evaluates C++ dynamic_cast cast. + /// The callback may result in the following 3 scenarios: + /// - Successful cast (ex: derived is subclass of base). + /// - Failed cast (ex: derived is definitely not a subclass of base). + /// - We don't know (base is a symbolic region and we don't have + /// enough info to determine if the cast will succeed at run time). + /// The function returns an SVal representing the derived class; it's + /// valid only if Failed flag is set to false. + virtual SVal evalDynamicCast(SVal base, QualType derivedPtrType, + bool &Failed) = 0; class CastResult { - const ProgramState *state; + ProgramStateRef state; const MemRegion *region; public: - const ProgramState *getState() const { return state; } + ProgramStateRef getState() const { return state; } const MemRegion* getRegion() const { return region; } - CastResult(const ProgramState *s, const MemRegion* r = 0) : state(s), region(r){} + CastResult(ProgramStateRef s, const MemRegion* r = 0) : state(s), region(r){} }; const ElementRegion *GetElementZeroRegion(const MemRegion *R, QualType T); @@ -180,8 +184,8 @@ public: /// 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] Call The call expression which will be used to determine which + /// globals should get invalidated. /// \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 @@ -189,14 +193,16 @@ public: virtual StoreRef invalidateRegions(Store store, ArrayRef<const MemRegion *> Regions, const Expr *E, unsigned Count, + const LocationContext *LCtx, InvalidatedSymbols &IS, - bool invalidateGlobals, + const CallOrObjCMessage *Call, InvalidatedRegions *Invalidated) = 0; /// enterStackFrame - Let the StoreManager to do something when execution /// engine is about to execute into a callee. - virtual StoreRef enterStackFrame(const ProgramState *state, - const StackFrameContext *frame); + virtual StoreRef enterStackFrame(ProgramStateRef state, + const LocationContext *callerCtx, + const StackFrameContext *calleeCtx); virtual void print(Store store, raw_ostream &Out, const char* nl, const char *sep) = 0; @@ -208,6 +214,21 @@ public: const MemRegion *region, SVal val) = 0; }; + class FindUniqueBinding : + public BindingsHandler { + SymbolRef Sym; + const MemRegion* Binding; + bool First; + + public: + FindUniqueBinding(SymbolRef sym) : Sym(sym), Binding(0), First(true) {} + + bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R, + SVal val); + operator bool() { return First && Binding; } + const MemRegion *getRegion() { return Binding; } + }; + /// iterBindings - Iterate over the bindings in the Store. virtual void iterBindings(Store store, BindingsHandler& f) = 0; @@ -258,10 +279,12 @@ inline StoreRef &StoreRef::operator=(StoreRef const &newStore) { /// SubRegionMap - An abstract interface that represents a queryable map /// between MemRegion objects and their subregions. class SubRegionMap { + virtual void anchor(); public: virtual ~SubRegionMap() {} class Visitor { + virtual void anchor(); public: virtual ~Visitor() {} virtual bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) = 0; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h index ae212bc..baf57d4 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h @@ -26,27 +26,26 @@ class Stmt; namespace ento { -template <typename PP> class GenericNodeBuilder; +struct NodeBuilderContext; class AnalysisManager; class ExplodedNodeSet; class ExplodedNode; class ProgramState; class ProgramStateManager; class BlockCounter; -class StmtNodeBuilder; class BranchNodeBuilder; class IndirectGotoNodeBuilder; class SwitchNodeBuilder; class EndOfFunctionNodeBuilder; -class CallEnterNodeBuilder; -class CallExitNodeBuilder; +class NodeBuilderWithSinks; class MemRegion; class SubEngine { + virtual void anchor(); public: virtual ~SubEngine() {} - virtual const ProgramState *getInitialState(const LocationContext *InitLoc) = 0; + virtual ProgramStateRef getInitialState(const LocationContext *InitLoc) = 0; virtual AnalysisManager &getAnalysisManager() = 0; @@ -54,18 +53,23 @@ public: /// 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; + virtual void processCFGElement(const CFGElement E, ExplodedNode* Pred, + unsigned StmtIdx, NodeBuilderContext *Ctx)=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; + virtual void processCFGBlockEntrance(const BlockEdge &L, + NodeBuilderWithSinks &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; + NodeBuilderContext& BuilderCtx, + ExplodedNode *Pred, + ExplodedNodeSet &Dst, + const CFGBlock *DstT, + const CFGBlock *DstF) = 0; /// Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a computed goto jump. @@ -77,40 +81,41 @@ public: /// 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; + virtual void processEndOfFunction(NodeBuilderContext& BC) = 0; // Generate the entry node of the callee. - virtual void processCallEnter(CallEnterNodeBuilder &builder) = 0; + virtual void processCallEnter(CallEnter CE, ExplodedNode *Pred) = 0; // Generate the first post callsite node. - virtual void processCallExit(CallExitNodeBuilder &builder) = 0; + virtual void processCallExit(ExplodedNode *Pred) = 0; /// Called by ConstraintManager. Used to call checker-specific /// logic for handling assumptions on symbolic values. - virtual const ProgramState *processAssume(const ProgramState *state, + virtual ProgramStateRef processAssume(ProgramStateRef state, SVal cond, bool assumption) = 0; /// wantsRegionChangeUpdate - Called by ProgramStateManager to determine if a /// region change should trigger a processRegionChanges update. - virtual bool wantsRegionChangeUpdate(const ProgramState *state) = 0; + virtual bool wantsRegionChangeUpdate(ProgramStateRef state) = 0; - /// processRegionChanges - Called by ProgramStateManager whenever a change is made - /// to the store. Used to update checkers that track region values. - virtual const ProgramState * - processRegionChanges(const ProgramState *state, + /// processRegionChanges - Called by ProgramStateManager whenever a change is + /// made to the store. Used to update checkers that track region values. + virtual ProgramStateRef + processRegionChanges(ProgramStateRef state, const StoreManager::InvalidatedSymbols *invalidated, ArrayRef<const MemRegion *> ExplicitRegions, - ArrayRef<const MemRegion *> Regions) = 0; + ArrayRef<const MemRegion *> Regions, + const CallOrObjCMessage *Call) = 0; - inline const ProgramState * - processRegionChange(const ProgramState *state, + inline ProgramStateRef + processRegionChange(ProgramStateRef state, const MemRegion* MR) { - return processRegionChanges(state, 0, MR, MR); + return processRegionChanges(state, 0, MR, MR, 0); } /// printState - Called by ProgramStateManager to print checker-specific data. - virtual void printState(raw_ostream &Out, const ProgramState *State, + virtual void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) = 0; /// Called by CoreEngine when the analysis worklist is either empty or the diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h index 0d6e18e..c7de7ef 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -40,13 +40,16 @@ namespace ento { class TypedValueRegion; class VarRegion; +/// \brief Symbolic value. These values used to capture symbolic execution of +/// the program. class SymExpr : public llvm::FoldingSetNode { + virtual void anchor(); public: enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, MetadataKind, BEGIN_SYMBOLS = RegionValueKind, END_SYMBOLS = MetadataKind, - SymIntKind, SymSymKind }; + SymIntKind, IntSymKind, SymSymKind, CastSymbolKind }; private: Kind K; @@ -58,21 +61,49 @@ public: Kind getKind() const { return K; } - void dump() const; + virtual void dump() const; - virtual void dumpToStream(raw_ostream &os) const = 0; + virtual void dumpToStream(raw_ostream &os) const {} 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; } + + /// \brief Iterator over symbols that the current symbol depends on. + /// + /// For SymbolData, it's the symbol itself; for expressions, it's the + /// expression symbol and all the operands in it. Note, SymbolDerived is + /// treated as SymbolData - the iterator will NOT visit the parent region. + class symbol_iterator { + SmallVector<const SymExpr*, 5> itr; + void expand(); + public: + symbol_iterator() {} + symbol_iterator(const SymExpr *SE); + + symbol_iterator &operator++(); + const SymExpr* operator*(); + + bool operator==(const symbol_iterator &X) const; + bool operator!=(const symbol_iterator &X) const; + }; + + symbol_iterator symbol_begin() const { + return symbol_iterator(this); + } + static symbol_iterator symbol_end() { return symbol_iterator(); } }; -typedef unsigned SymbolID; +typedef const SymExpr* SymbolRef; +typedef llvm::SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy; +typedef unsigned SymbolID; +/// \brief A symbol representing data which can be stored in a memory location +/// (region). class SymbolData : public SymExpr { -private: + virtual void anchor(); const SymbolID Sym; protected: @@ -90,10 +121,7 @@ public: } }; -typedef const SymbolData* SymbolRef; -typedef llvm::SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy; - -/// A symbol representing the value of a MemRegion. +///\brief A symbol representing the value stored at a MemRegion. class SymbolRegionValue : public SymbolData { const TypedValueRegion *R; @@ -112,7 +140,7 @@ public: Profile(profile, R); } - void dumpToStream(raw_ostream &os) const; + virtual void dumpToStream(raw_ostream &os) const; QualType getType(ASTContext&) const; @@ -122,17 +150,21 @@ public: } }; -/// A symbol representing the result of an expression. +/// A symbol representing the result of an expression in the case when we do +/// not know anything about what the expression is. class SymbolConjured : public SymbolData { const Stmt *S; QualType T; unsigned Count; + const LocationContext *LCtx; const void *SymbolTag; public: - SymbolConjured(SymbolID sym, const Stmt *s, QualType t, unsigned count, + SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, + QualType t, unsigned count, const void *symbolTag) : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), + LCtx(lctx), SymbolTag(symbolTag) {} const Stmt *getStmt() const { return S; } @@ -141,19 +173,21 @@ public: QualType getType(ASTContext&) const; - void dumpToStream(raw_ostream &os) const; + virtual void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, - QualType T, unsigned Count, const void *SymbolTag) { + QualType T, unsigned Count, const LocationContext *LCtx, + const void *SymbolTag) { profile.AddInteger((unsigned) ConjuredKind); profile.AddPointer(S); + profile.AddPointer(LCtx); profile.Add(T); profile.AddInteger(Count); profile.AddPointer(SymbolTag); } virtual void Profile(llvm::FoldingSetNodeID& profile) { - Profile(profile, S, T, Count, SymbolTag); + Profile(profile, S, T, Count, LCtx, SymbolTag); } // Implement isa<T> support. @@ -177,7 +211,7 @@ public: QualType getType(ASTContext&) const; - void dumpToStream(raw_ostream &os) const; + virtual void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, const TypedValueRegion *r) { @@ -210,7 +244,7 @@ public: QualType getType(ASTContext&) const; - void dumpToStream(raw_ostream &os) const; + virtual void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { profile.AddInteger((unsigned) ExtentKind); @@ -249,7 +283,7 @@ public: QualType getType(ASTContext&) const; - void dumpToStream(raw_ostream &os) const; + virtual void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, const Stmt *S, QualType T, unsigned Count, @@ -272,6 +306,42 @@ public: } }; +/// \brief Represents a cast expression. +class SymbolCast : public SymExpr { + const SymExpr *Operand; + /// Type of the operand. + QualType FromTy; + /// The type of the result. + QualType ToTy; + +public: + SymbolCast(const SymExpr *In, QualType From, QualType To) : + SymExpr(CastSymbolKind), Operand(In), FromTy(From), ToTy(To) { } + + QualType getType(ASTContext &C) const { return ToTy; } + + const SymExpr *getOperand() const { return Operand; } + + virtual void dumpToStream(raw_ostream &os) const; + + static void Profile(llvm::FoldingSetNodeID& ID, + const SymExpr *In, QualType From, QualType To) { + ID.AddInteger((unsigned) CastSymbolKind); + ID.AddPointer(In); + ID.Add(From); + ID.Add(To); + } + + void Profile(llvm::FoldingSetNodeID& ID) { + Profile(ID, Operand, FromTy, ToTy); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr *SE) { + return SE->getKind() == CastSymbolKind; + } +}; + /// SymIntExpr - Represents symbolic expression like 'x' + 3. class SymIntExpr : public SymExpr { const SymExpr *LHS; @@ -290,7 +360,7 @@ public: BinaryOperator::Opcode getOpcode() const { return Op; } - void dumpToStream(raw_ostream &os) const; + virtual void dumpToStream(raw_ostream &os) const; const SymExpr *getLHS() const { return LHS; } const llvm::APSInt &getRHS() const { return RHS; } @@ -315,6 +385,47 @@ public: } }; +/// IntSymExpr - Represents symbolic expression like 3 - 'x'. +class IntSymExpr : public SymExpr { + const llvm::APSInt& LHS; + BinaryOperator::Opcode Op; + const SymExpr *RHS; + QualType T; + +public: + IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, + const SymExpr *rhs, QualType t) + : SymExpr(IntSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} + + QualType getType(ASTContext &C) const { return T; } + + BinaryOperator::Opcode getOpcode() const { return Op; } + + virtual void dumpToStream(raw_ostream &os) const; + + const SymExpr *getRHS() const { return RHS; } + const llvm::APSInt &getLHS() const { return LHS; } + + static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, + BinaryOperator::Opcode op, const SymExpr *rhs, + QualType t) { + ID.AddInteger((unsigned) IntSymKind); + 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() == IntSymKind; + } +}; + /// SymSymExpr - Represents symbolic expression like 'x' + 'y'. class SymSymExpr : public SymExpr { const SymExpr *LHS; @@ -335,7 +446,7 @@ public: // generation of virtual functions. QualType getType(ASTContext &C) const { return T; } - void dumpToStream(raw_ostream &os) const; + virtual void dumpToStream(raw_ostream &os) const; static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { @@ -382,13 +493,18 @@ public: /// \brief Make a unique symbol for MemRegion R according to its kind. const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); - const SymbolConjured* getConjuredSymbol(const Stmt *E, QualType T, + const SymbolConjured* getConjuredSymbol(const Stmt *E, + const LocationContext *LCtx, + QualType T, unsigned VisitCount, const void *SymbolTag = 0); - const SymbolConjured* getConjuredSymbol(const Expr *E, unsigned VisitCount, + const SymbolConjured* getConjuredSymbol(const Expr *E, + const LocationContext *LCtx, + unsigned VisitCount, const void *SymbolTag = 0) { - return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag); + return getConjuredSymbol(E, LCtx, E->getType(), + VisitCount, SymbolTag); } const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, @@ -404,6 +520,9 @@ public: QualType T, unsigned VisitCount, const void *SymbolTag = 0); + const SymbolCast* getCastSymbol(const SymExpr *Operand, + QualType From, QualType To); + const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const llvm::APSInt& rhs, QualType t); @@ -412,6 +531,10 @@ public: return getSymIntExpr(&lhs, op, rhs, t); } + const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, + BinaryOperator::Opcode op, + const SymExpr *rhs, QualType t); + const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType t); @@ -464,7 +587,7 @@ public: bool isLive(SymbolRef sym); bool isLiveRegion(const MemRegion *region); - bool isLive(const Stmt *ExprVal) const; + bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; /// \brief Unconditionally marks a symbol as live. @@ -537,7 +660,7 @@ public: namespace llvm { static inline raw_ostream &operator<<(raw_ostream &os, - const clang::ento::SymExpr *SE) { + const clang::ento::SymExpr *SE) { SE->dumpToStream(os); return os; } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h new file mode 100644 index 0000000..53205d3 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h @@ -0,0 +1,40 @@ +//== TaintManager.h - Managing taint --------------------------- -*- C++ -*--=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides APIs for adding, removing, querying symbol taint. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_TAINTMANAGER_H +#define LLVM_CLANG_TAINTMANAGER_H + +#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h" + +namespace clang { +namespace ento { + +/// The GDM component containing the tainted root symbols. We lazily infer the +/// taint of the dependent symbols. Currently, this is a map from a symbol to +/// tag kind. TODO: Should support multiple tag kinds. +struct TaintMap {}; +typedef llvm::ImmutableMap<SymbolRef, TaintTagType> TaintMapImpl; +template<> struct ProgramStateTrait<TaintMap> + : public ProgramStatePartialTrait<TaintMapImpl> { + static void *GDMIndex() { static int index = 0; return &index; } +}; + +class TaintManager { + + TaintManager() {} +}; + +} +} + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h new file mode 100644 index 0000000..8ddc8b9d --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h @@ -0,0 +1,27 @@ +//== TaintTag.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. +// +//===----------------------------------------------------------------------===// +// +// Defines a set of taint tags. Several tags are used to differentiate kinds +// of taint. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_CLANG_TAINTTAG_H +#define LLVM_CLANG_TAINTTAG_H + +namespace clang { +namespace ento { + +/// The type of taint, which helps to differentiate between different types of +/// taint. +typedef unsigned TaintTagType; +static const TaintTagType TaintTagGeneric = 0; + +}} + +#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h b/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h index fa34075..51aa753 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h @@ -73,6 +73,7 @@ public: } void enqueue(ExplodedNode *N) { + assert(N->getLocation().getKind() != ProgramPoint::PostStmtKind); enqueue(WorkListUnit(N, CurrentCounter)); } |