diff options
Diffstat (limited to 'clang/include/clang/StaticAnalyzer/Core')
20 files changed, 750 insertions, 226 deletions
diff --git a/clang/include/clang/StaticAnalyzer/Core/Analyses.def b/clang/include/clang/StaticAnalyzer/Core/Analyses.def index c4e5f5be6fd7..88c375ce0925 100644 --- a/clang/include/clang/StaticAnalyzer/Core/Analyses.def +++ b/clang/include/clang/StaticAnalyzer/Core/Analyses.def @@ -52,9 +52,14 @@ ANALYSIS_DIAGNOSTICS(PLIST_HTML, "plist-html", "Output analysis results using HTML wrapped with Plists", createPlistHTMLDiagnosticConsumer) -ANALYSIS_DIAGNOSTICS(SARIF, "sarif", "Output analysis results in a SARIF file", +ANALYSIS_DIAGNOSTICS(SARIF, "sarif", "Output analysis results using SARIF", createSarifDiagnosticConsumer) +ANALYSIS_DIAGNOSTICS(SARIF_HTML, "sarif-html", + "Output analysis results using both SARIF and HTML " + "output files", + createSarifHTMLDiagnosticConsumer) + ANALYSIS_DIAGNOSTICS(TEXT, "text", "Text output of analysis results to stderr", createTextPathDiagnosticConsumer) diff --git a/clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h b/clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h index 27bc0dda1f1c..3c93ebeccde8 100644 --- a/clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h +++ b/clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h @@ -432,6 +432,8 @@ public: void markInteresting(SymbolRef sym, bugreporter::TrackingKind TKind = bugreporter::TrackingKind::Thorough); + void markNotInteresting(SymbolRef sym); + /// Marks a region as interesting. Different kinds of interestingness will /// be processed differently by visitors (e.g. if the tracking kind is /// condition, will append "will be used as a condition" to the message). @@ -439,6 +441,8 @@ public: const MemRegion *R, bugreporter::TrackingKind TKind = bugreporter::TrackingKind::Thorough); + void markNotInteresting(const MemRegion *R); + /// Marks a symbolic value as interesting. Different kinds of interestingness /// will be processed differently by visitors (e.g. if the tracking kind is /// condition, will append "will be used as a condition" to the message). @@ -489,11 +493,16 @@ public: /// /// The visitors should be used when the default trace is not sufficient. /// For example, they allow constructing a more elaborate trace. - /// \sa registerConditionVisitor(), registerTrackNullOrUndefValue(), - /// registerFindLastStore(), registerNilReceiverVisitor(), and - /// registerVarDeclsLastStore(). + /// @{ void addVisitor(std::unique_ptr<BugReporterVisitor> visitor); + template <class VisitorType, class... Args> + void addVisitor(Args &&... ConstructorArgs) { + addVisitor( + std::make_unique<VisitorType>(std::forward<Args>(ConstructorArgs)...)); + } + /// @} + /// Remove all visitors attached to this bug report. void clearVisitors(); @@ -720,14 +729,43 @@ public: } }; +/// The tag that carries some information with it. +/// +/// It can be valuable to produce tags with some bits of information and later +/// reuse them for a better diagnostic. +/// +/// Please make sure that derived class' constuctor is private and that the user +/// can only create objects using DataTag::Factory. This also means that +/// DataTag::Factory should be friend for every derived class. +class DataTag : public ProgramPointTag { +public: + StringRef getTagDescription() const override { return "Data Tag"; } + + // Manage memory for DataTag objects. + class Factory { + std::vector<std::unique_ptr<DataTag>> Tags; + + public: + template <class DataTagType, class... Args> + const DataTagType *make(Args &&... ConstructorArgs) { + // We cannot use std::make_unique because we cannot access the private + // constructor from inside it. + Tags.emplace_back( + new DataTagType(std::forward<Args>(ConstructorArgs)...)); + return static_cast<DataTagType *>(Tags.back().get()); + } + }; + +protected: + DataTag(void *TagKind) : ProgramPointTag(TagKind) {} +}; /// The tag upon which the TagVisitor reacts. Add these in order to display /// additional PathDiagnosticEventPieces along the path. -class NoteTag : public ProgramPointTag { +class NoteTag : public DataTag { public: - using Callback = - std::function<std::string(BugReporterContext &, - PathSensitiveBugReport &)>; + using Callback = std::function<std::string(BugReporterContext &, + PathSensitiveBugReport &)>; private: static int Kind; @@ -736,7 +774,7 @@ private: const bool IsPrunable; NoteTag(Callback &&Cb, bool IsPrunable) - : ProgramPointTag(&Kind), Cb(std::move(Cb)), IsPrunable(IsPrunable) {} + : DataTag(&Kind), Cb(std::move(Cb)), IsPrunable(IsPrunable) {} public: static bool classof(const ProgramPointTag *T) { @@ -761,20 +799,7 @@ public: bool isPrunable() const { return IsPrunable; } - // Manage memory for NoteTag objects. - class Factory { - std::vector<std::unique_ptr<NoteTag>> Tags; - - public: - const NoteTag *makeNoteTag(Callback &&Cb, bool IsPrunable = false) { - // We cannot use std::make_unique because we cannot access the private - // constructor from inside it. - std::unique_ptr<NoteTag> T(new NoteTag(std::move(Cb), IsPrunable)); - Tags.push_back(std::move(T)); - return Tags.back().get(); - } - }; - + friend class Factory; friend class TagVisitor; }; diff --git a/clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h b/clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h index 58a88f452ed9..24cae12af24a 100644 --- a/clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h +++ b/clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h @@ -19,9 +19,12 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/IntrusiveRefCntPtr.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/StringRef.h" +#include <list> #include <memory> +#include <utility> namespace clang { @@ -93,74 +96,293 @@ enum class TrackingKind { /// gathered about the tracked expression value as possible. Thorough, /// Specifies that a more moderate tracking should be used for the expression - /// value. This will essentially make sure that functions relevant to the it + /// value. This will essentially make sure that functions relevant to it /// aren't pruned, but otherwise relies on the user reading the code or /// following the arrows. Condition }; -/// Attempts to add visitors to track expression value back to its point of -/// origin. -/// -/// \param N A node "downstream" from the evaluation of the statement. -/// \param E The expression value which we are tracking -/// \param R The bug report to which visitors should be attached. -/// \param EnableNullFPSuppression Whether we should employ false positive -/// suppression (inlined defensive checks, returned null). +/// Defines a set of options altering tracking behavior. +struct TrackingOptions { + /// Specifies the kind of tracking. + TrackingKind Kind = TrackingKind::Thorough; + /// Specifies whether we should employ false positive suppression + /// (inlined defensive checks, returned null). + bool EnableNullFPSuppression = true; +}; + +/// Describes an event when the value got stored into a memory region. /// -/// \return Whether or not the function was able to add visitors for this -/// statement. Note that returning \c true does not actually imply -/// that any visitors were added. -bool trackExpressionValue(const ExplodedNode *N, const Expr *E, - PathSensitiveBugReport &R, - TrackingKind TKind = TrackingKind::Thorough, - bool EnableNullFPSuppression = true); +/// As opposed to checker checkBind API, it reacts also to binds +/// generated by the checker as well. It can be useful when the binding +/// happened as a result of evalCall, for example. +struct StoreInfo { + enum Kind { + /// The value got stored into the region during initialization: + /// int x = 42; + Initialization, + /// The value got stored into the region during assignment: + /// int x; + /// x = 42; + Assignment, + /// The value got stored into the parameter region as the result + /// of a call. + CallArgument, + /// The value got stored into the region as block capture. + /// Block data is modeled as a separate region, thus whenever + /// the analyzer sees a captured variable, its value is copied + /// into a special block region. + BlockCapture + }; + + /// The type of store operation. + Kind StoreKind; + /// The node where the store happened. + const ExplodedNode *StoreSite; + /// The expression where the value comes from. + /// NOTE: might be null. + const Expr *SourceOfTheValue; + /// Symbolic value that is being stored. + SVal Value; + /// Memory regions involved in the store operation. + /// Dest <- Origin + /// NOTE: Origin might be null, when the stored value doesn't come + /// from another region. + const MemRegion *Dest, *Origin; +}; -const Expr *getDerefExpr(const Stmt *S); +class Tracker; +using TrackerRef = llvm::IntrusiveRefCntPtr<Tracker>; -} // namespace bugreporter +class ExpressionHandler; +class StoreHandler; -/// Finds last store into the given region, -/// which is different from a given symbolic value. -class FindLastStoreBRVisitor final : public BugReporterVisitor { - const MemRegion *R; - SVal V; - bool Satisfied = false; +/// A generalized component for tracking expressions, values, and stores. +/// +/// Tracker aimes at providing a sensible set of default behaviors that can be +/// used by any checker, while providing mechanisms to hook into any part of the +/// tracking process and insert checker-specific logic. +class Tracker : public llvm::RefCountedBase<Tracker> { +private: + using ExpressionHandlerPtr = std::unique_ptr<ExpressionHandler>; + using StoreHandlerPtr = std::unique_ptr<StoreHandler>; - /// If the visitor is tracking the value directly responsible for the - /// bug, we are going to employ false positive suppression. - bool EnableNullFPSuppression; + PathSensitiveBugReport &Report; + std::list<ExpressionHandlerPtr> ExpressionHandlers; + std::list<StoreHandlerPtr> StoreHandlers; - using TrackingKind = bugreporter::TrackingKind; - TrackingKind TKind; - const StackFrameContext *OriginSFC; +protected: + /// \param Report The bug report to which visitors should be attached. + Tracker(PathSensitiveBugReport &Report); public: + virtual ~Tracker() = default; + + static TrackerRef create(PathSensitiveBugReport &Report) { + return new Tracker(Report); + } + + PathSensitiveBugReport &getReport() { return Report; } + + /// Describes a tracking result with the most basic information of what was + /// actually done (or not done). + struct Result { + /// Usually it means that the tracker added visitors. + bool FoundSomethingToTrack = false; + /// Signifies that the tracking was interrupted at some point. + /// Usually this information is important only for sub-trackers. + bool WasInterrupted = false; + + /// Combines the current result with the given result. + void combineWith(const Result &Other) { + // If we found something in one of the cases, we can + // say we found something overall. + FoundSomethingToTrack |= Other.FoundSomethingToTrack; + // The same goes to the interruption. + WasInterrupted |= Other.WasInterrupted; + } + }; + + /// Track expression value back to its point of origin. + /// + /// \param E The expression value which we are tracking + /// \param N A node "downstream" from the evaluation of the statement. + /// \param Opts Tracking options specifying how we want to track the value. + virtual Result track(const Expr *E, const ExplodedNode *N, + TrackingOptions Opts = {}); + + /// Track how the value got stored into the given region and where it came + /// from. + /// /// \param V We're searching for the store where \c R received this value. /// \param R The region we're tracking. - /// \param TKind May limit the amount of notes added to the bug report. - /// \param OriginSFC Only adds notes when the last store happened in a + /// \param Opts Tracking options specifying how we want to track the value. + /// \param Origin Only adds notes when the last store happened in a /// different stackframe to this one. Disregarded if the tracking kind /// is thorough. /// This is useful, because for non-tracked regions, notes about /// changes to its value in a nested stackframe could be pruned, and /// this visitor can prevent that without polluting the bugpath too /// much. - FindLastStoreBRVisitor(KnownSVal V, const MemRegion *R, - bool InEnableNullFPSuppression, TrackingKind TKind, - const StackFrameContext *OriginSFC = nullptr) - : R(R), V(V), EnableNullFPSuppression(InEnableNullFPSuppression), - TKind(TKind), OriginSFC(OriginSFC) { - assert(R); + virtual Result track(SVal V, const MemRegion *R, TrackingOptions Opts = {}, + const StackFrameContext *Origin = nullptr); + + /// Handle the store operation and produce the note. + /// + /// \param SI The information fully describing the store. + /// \param Opts Tracking options specifying how we got to it. + /// + /// NOTE: this method is designed for sub-trackers and visitors. + virtual PathDiagnosticPieceRef handle(StoreInfo SI, BugReporterContext &BRC, + TrackingOptions Opts); + + /// Add custom expression handler with the highest priority. + /// + /// It means that it will be asked for handling first, and can prevent + /// other handlers from running if decides to interrupt. + void addHighPriorityHandler(ExpressionHandlerPtr SH) { + ExpressionHandlers.push_front(std::move(SH)); } - void Profile(llvm::FoldingSetNodeID &ID) const override; + /// Add custom expression handler with the lowest priority. + /// + /// It means that it will be asked for handling last, and other handlers can + /// prevent it from running if any of them decides to interrupt. + void addLowPriorityHandler(ExpressionHandlerPtr SH) { + ExpressionHandlers.push_back(std::move(SH)); + } - PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, - BugReporterContext &BRC, - PathSensitiveBugReport &BR) override; + /// Add custom store handler with the highest priority. + /// + /// It means that it will be asked for handling first, and will prevent + /// other handlers from running if it produces non-null note. + void addHighPriorityHandler(StoreHandlerPtr SH) { + StoreHandlers.push_front(std::move(SH)); + } + + /// Add custom store handler with the lowest priority. + /// + /// It means that it will be asked for handling last, only + /// if all other handlers failed to produce the note. + void addLowPriorityHandler(StoreHandlerPtr SH) { + StoreHandlers.push_back(std::move(SH)); + } + + /// Add custom expression/store handler with the highest priority + /// + /// See other overloads for explanation. + template <class HandlerType, class... Args> + void addHighPriorityHandler(Args &&... ConstructorArgs) { + addHighPriorityHandler(std::make_unique<HandlerType>( + *this, std::forward<Args>(ConstructorArgs)...)); + } + + /// Add custom expression/store handler with the lowest priority + /// + /// See other overloads for explanation. + template <class HandlerType, class... Args> + void addLowPriorityHandler(Args &&... ConstructorArgs) { + addLowPriorityHandler(std::make_unique<HandlerType>( + *this, std::forward<Args>(ConstructorArgs)...)); + } +}; + +/// Handles expressions during the tracking. +class ExpressionHandler { +private: + Tracker &ParentTracker; + +public: + ExpressionHandler(Tracker &ParentTracker) : ParentTracker(ParentTracker) {} + virtual ~ExpressionHandler() {} + + /// Handle the given expression from the given node. + /// + /// \param E The expression value which we are tracking + /// \param Original A node "downstream" where the tracking started. + /// \param ExprNode A node where the evaluation of \c E actually happens. + /// \param Opts Tracking options specifying how we are tracking the value. + virtual Tracker::Result handle(const Expr *E, const ExplodedNode *Original, + const ExplodedNode *ExprNode, + TrackingOptions Opts) = 0; + + /// \Return the tracker that initiated the process. + Tracker &getParentTracker() { return ParentTracker; } +}; + +/// Handles stores during the tracking. +class StoreHandler { +private: + Tracker &ParentTracker; + +public: + StoreHandler(Tracker &ParentTracker) : ParentTracker(ParentTracker) {} + virtual ~StoreHandler() {} + + /// Handle the given store and produce the node. + /// + /// \param SI The information fully describing the store. + /// \param Opts Tracking options specifying how we are tracking the value. + /// + /// \return the produced note, null if the handler doesn't support this kind + /// of stores. + virtual PathDiagnosticPieceRef handle(StoreInfo SI, BugReporterContext &BRC, + TrackingOptions Opts) = 0; + + Tracker &getParentTracker() { return ParentTracker; } + +protected: + PathDiagnosticPieceRef constructNote(StoreInfo SI, BugReporterContext &BRC, + StringRef NodeText); }; +/// Visitor that tracks expressions and values. +class TrackingBugReporterVisitor : public BugReporterVisitor { +private: + TrackerRef ParentTracker; + +public: + TrackingBugReporterVisitor(TrackerRef ParentTracker) + : ParentTracker(ParentTracker) {} + + Tracker &getParentTracker() { return *ParentTracker; } +}; + +/// Attempts to add visitors to track expression value back to its point of +/// origin. +/// +/// \param N A node "downstream" from the evaluation of the statement. +/// \param E The expression value which we are tracking +/// \param R The bug report to which visitors should be attached. +/// \param Opts Tracking options specifying how we are tracking the value. +/// +/// \return Whether or not the function was able to add visitors for this +/// statement. Note that returning \c true does not actually imply +/// that any visitors were added. +bool trackExpressionValue(const ExplodedNode *N, const Expr *E, + PathSensitiveBugReport &R, TrackingOptions Opts = {}); + +/// Track how the value got stored into the given region and where it came +/// from. +/// +/// \param V We're searching for the store where \c R received this value. +/// \param R The region we're tracking. +/// \param Opts Tracking options specifying how we want to track the value. +/// \param Origin Only adds notes when the last store happened in a +/// different stackframe to this one. Disregarded if the tracking kind +/// is thorough. +/// This is useful, because for non-tracked regions, notes about +/// changes to its value in a nested stackframe could be pruned, and +/// this visitor can prevent that without polluting the bugpath too +/// much. +void trackStoredValue(KnownSVal V, const MemRegion *R, + PathSensitiveBugReport &Report, TrackingOptions Opts = {}, + const StackFrameContext *Origin = nullptr); + +const Expr *getDerefExpr(const Stmt *S); + +} // namespace bugreporter + class TrackConstraintBRVisitor final : public BugReporterVisitor { DefinedSVal Constraint; bool Assumption; diff --git a/clang/include/clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h b/clang/include/clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h index 637b89fd9036..392bc484bf62 100644 --- a/clang/include/clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h +++ b/clang/include/clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h @@ -19,7 +19,9 @@ extern const char *const MemoryRefCount; extern const char *const MemoryError; extern const char *const UnixAPI; extern const char *const CXXObjectLifecycle; +extern const char *const CXXMoveSemantics; extern const char *const SecurityError; +extern const char *const UnusedCode; } // namespace categories } // namespace ento } // namespace clang diff --git a/clang/include/clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h b/clang/include/clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h index f40f88eb32ff..71a590d9e9a2 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h @@ -21,7 +21,9 @@ namespace clang { class AnalyzerOptions; +class MacroExpansionContext; class Preprocessor; + namespace cross_tu { class CrossTranslationUnitContext; } @@ -35,7 +37,8 @@ typedef std::vector<PathDiagnosticConsumer*> PathDiagnosticConsumers; void CREATEFN(PathDiagnosticConsumerOptions Diagopts, \ PathDiagnosticConsumers &C, const std::string &Prefix, \ const Preprocessor &PP, \ - const cross_tu::CrossTranslationUnitContext &CTU); + const cross_tu::CrossTranslationUnitContext &CTU, \ + const MacroExpansionContext &MacroExpansions); #include "clang/StaticAnalyzer/Core/Analyses.def" } // end 'ento' namespace diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h index 142b1ab11750..bb598af68166 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h @@ -52,6 +52,8 @@ public: iterator begin() const { return L.begin(); } iterator end() const { return L.end(); } + QualType getType() const { return T; } + static void Profile(llvm::FoldingSetNodeID& ID, QualType T, llvm::ImmutableList<SVal> L); @@ -139,6 +141,12 @@ public: /// Returns the type of the APSInt used to store values of the given QualType. APSIntType getAPSIntType(QualType T) const { + // For the purposes of the analysis and constraints, we treat atomics + // as their underlying types. + if (const AtomicType *AT = T->getAs<AtomicType>()) { + T = AT->getValueType(); + } + assert(T->isIntegralOrEnumerationType() || Loc::isLocType(T)); return APSIntType(Ctx.getIntWidth(T), !T->isSignedIntegerOrEnumerationType()); @@ -258,9 +266,9 @@ public: return CXXBaseListFactory.add(CBS, L); } - const PointerToMemberData *accumCXXBase( - llvm::iterator_range<CastExpr::path_const_iterator> PathRange, - const nonloc::PointerToMember &PTM); + const PointerToMemberData * + accumCXXBase(llvm::iterator_range<CastExpr::path_const_iterator> PathRange, + const nonloc::PointerToMember &PTM, const clang::CastKind &kind); const llvm::APSInt* evalAPSInt(BinaryOperator::Opcode Op, const llvm::APSInt& V1, diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h index 54572bd81f20..a383012dc351 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h @@ -255,7 +255,7 @@ public: /// to omit the note from the report if it would make the displayed /// bug path significantly shorter. const NoteTag *getNoteTag(NoteTag::Callback &&Cb, bool IsPrunable = false) { - return Eng.getNoteTags().makeNoteTag(std::move(Cb), IsPrunable); + return Eng.getDataTags().make<NoteTag>(std::move(Cb), IsPrunable); } /// A shorthand version of getNoteTag that doesn't require you to accept diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h index f253c14cc487..a81d67ab3063 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h @@ -13,7 +13,9 @@ #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CHECKERHELPERS_H #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CHECKERHELPERS_H +#include "clang/AST/OperationKinds.h" #include "clang/AST/Stmt.h" +#include "clang/Basic/OperatorKinds.h" #include "llvm/ADT/Optional.h" #include <tuple> @@ -69,6 +71,45 @@ Nullability getNullabilityAnnotation(QualType Type); /// token for an integer. If we cannot parse the value then None is returned. llvm::Optional<int> tryExpandAsInteger(StringRef Macro, const Preprocessor &PP); +class OperatorKind { + union { + BinaryOperatorKind Bin; + UnaryOperatorKind Un; + } Op; + bool IsBinary; + +public: + explicit OperatorKind(BinaryOperatorKind Bin) : Op{Bin}, IsBinary{true} {} + explicit OperatorKind(UnaryOperatorKind Un) : IsBinary{false} { Op.Un = Un; } + bool IsBinaryOp() const { return IsBinary; } + + BinaryOperatorKind GetBinaryOpUnsafe() const { + assert(IsBinary && "cannot get binary operator - we have a unary operator"); + return Op.Bin; + } + + Optional<BinaryOperatorKind> GetBinaryOp() const { + if (IsBinary) + return Op.Bin; + return {}; + } + + UnaryOperatorKind GetUnaryOpUnsafe() const { + assert(!IsBinary && + "cannot get unary operator - we have a binary operator"); + return Op.Un; + } + + Optional<UnaryOperatorKind> GetUnaryOp() const { + if (!IsBinary) + return Op.Un; + return {}; + } +}; + +OperatorKind operationKindFromOverloadedOperator(OverloadedOperatorKind OOK, + bool IsBinary); + } // namespace ento } // namespace clang diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 2aca2c99ef4f..9898b9b42f4b 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -96,9 +96,10 @@ private: /// (This data is owned by AnalysisConsumer.) FunctionSummariesTy *FunctionSummaries; - /// Add path note tags along the path when we see that something interesting - /// is happening. This field is the allocator for such tags. - NoteTag::Factory NoteTags; + /// Add path tags with some useful data along the path when we see that + /// something interesting is happening. This field is the allocator for such + /// tags. + DataTag::Factory DataTags; void generateNode(const ProgramPoint &Loc, ProgramStateRef State, @@ -200,7 +201,7 @@ public: /// Enqueue a single node created as a result of statement processing. void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx); - NoteTag::Factory &getNoteTags() { return NoteTags; } + DataTag::Factory &getDataTags() { return DataTags; } }; // TODO: Turn into a class. diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h new file mode 100644 index 000000000000..cfd7aa9664b6 --- /dev/null +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h @@ -0,0 +1,59 @@ +//===- DynamicExtent.h - Dynamic extent related APIs ------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines APIs that track and query dynamic extent information. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICEXTENT_H +#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICEXTENT_H + +#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" + +namespace clang { +namespace ento { + +/// \returns The stored dynamic extent for the region \p MR. +DefinedOrUnknownSVal getDynamicExtent(ProgramStateRef State, + const MemRegion *MR, SValBuilder &SVB); + +/// \returns The element extent of the type \p Ty. +DefinedOrUnknownSVal getElementExtent(QualType Ty, SValBuilder &SVB); + +/// \returns The stored element count of the region \p MR. +DefinedOrUnknownSVal getDynamicElementCount(ProgramStateRef State, + const MemRegion *MR, + SValBuilder &SVB, QualType Ty); + +/// Set the dynamic extent \p Extent of the region \p MR. +ProgramStateRef setDynamicExtent(ProgramStateRef State, const MemRegion *MR, + DefinedOrUnknownSVal Extent, SValBuilder &SVB); + +/// Get the dynamic extent for a symbolic value that represents a buffer. If +/// there is an offsetting to the underlying buffer we consider that too. +/// Returns with an SVal that represents the extent, this is Unknown if the +/// engine cannot deduce the extent. +/// E.g. +/// char buf[3]; +/// (buf); // extent is 3 +/// (buf + 1); // extent is 2 +/// (buf + 3); // extent is 0 +/// (buf + 4); // extent is -1 +/// +/// char *bufptr; +/// (bufptr) // extent is unknown +SVal getDynamicExtentWithOffset(ProgramStateRef State, SVal BufV); + +} // namespace ento +} // namespace clang + +#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICEXTENT_H diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h deleted file mode 100644 index 398f9b6ac33a..000000000000 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h +++ /dev/null @@ -1,53 +0,0 @@ -//===- DynamicSize.h - Dynamic size related APIs ----------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This file defines APIs that track and query dynamic size information. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICSIZE_H -#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICSIZE_H - -#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" - -namespace clang { -namespace ento { - -/// Get the stored dynamic size for the region \p MR. -DefinedOrUnknownSVal getDynamicSize(ProgramStateRef State, const MemRegion *MR, - SValBuilder &SVB); - -/// Get the stored element count of the region \p MR. -DefinedOrUnknownSVal getDynamicElementCount(ProgramStateRef State, - const MemRegion *MR, - SValBuilder &SVB, - QualType ElementTy); - -/// Get the dynamic size for a symbolic value that represents a buffer. If -/// there is an offsetting to the underlying buffer we consider that too. -/// Returns with an SVal that represents the size, this is Unknown if the -/// engine cannot deduce the size. -/// E.g. -/// char buf[3]; -/// (buf); // size is 3 -/// (buf + 1); // size is 2 -/// (buf + 3); // size is 0 -/// (buf + 4); // size is -1 -/// -/// char *bufptr; -/// (bufptr) // size is unknown -SVal getDynamicSizeWithOffset(ProgramStateRef State, const SVal &BufV); - -} // namespace ento -} // namespace clang - -#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICSIZE_H diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h index 2679339537e8..ffe1fe846be1 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h @@ -24,7 +24,6 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" #include "llvm/ADT/ImmutableMap.h" #include "llvm/ADT/Optional.h" -#include <utility> namespace clang { namespace ento { diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index 582a56cbee1e..cef7dda172f3 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -428,8 +428,7 @@ public: SymbolManager &getSymbolManager() { return SymMgr; } MemRegionManager &getRegionManager() { return MRMgr; } - NoteTag::Factory &getNoteTags() { return Engine.getNoteTags(); } - + DataTag::Factory &getDataTags() { return Engine.getDataTags(); } // Functions for external checking of whether we have unfinished work bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); } diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h index d25d26435454..53b221cb53c9 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h @@ -5,7 +5,7 @@ // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// -/// +/// \file /// This header contains the declarations of functions which are used to decide /// which loops should be completely unrolled and mark their corresponding /// CFGBlocks. It is done by tracking a stack of loops in the ProgramState. This @@ -18,7 +18,6 @@ /// has to be initialized by a literal in the corresponding initStmt. /// - Does not contain goto, switch and returnStmt. /// -/// //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPUNROLLING_H diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h index 7484a51b1eda..e75228f92a8e 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h @@ -5,7 +5,7 @@ // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// -/// +/// \file /// This header contains the declarations of functions which are used to widen /// loops which do not otherwise exit. The widening is done by invalidating /// anything which might be modified by the body of the loop. diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h index bc5d5f57cd68..c67df1e51b4f 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h @@ -16,6 +16,8 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/Support/Allocator.h" namespace clang { @@ -24,21 +26,19 @@ namespace ento { /// A Range represents the closed range [from, to]. The caller must /// guarantee that from <= to. Note that Range is immutable, so as not /// to subvert RangeSet's immutability. -class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> { +class Range { public: - Range(const llvm::APSInt &from, const llvm::APSInt &to) - : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) { - assert(from <= to); + Range(const llvm::APSInt &From, const llvm::APSInt &To) : Impl(&From, &To) { + assert(From <= To); } - Range(const llvm::APSInt &point) - : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&point, &point) {} + Range(const llvm::APSInt &Point) : Range(Point, Point) {} - bool Includes(const llvm::APSInt &v) const { - return *first <= v && v <= *second; + bool Includes(const llvm::APSInt &Point) const { + return From() <= Point && Point <= To(); } - const llvm::APSInt &From() const { return *first; } - const llvm::APSInt &To() const { return *second; } + const llvm::APSInt &From() const { return *Impl.first; } + const llvm::APSInt &To() const { return *Impl.second; } const llvm::APSInt *getConcreteValue() const { return &From() == &To() ? &From() : nullptr; } @@ -47,93 +47,267 @@ public: ID.AddPointer(&From()); ID.AddPointer(&To()); } -}; + void dump(raw_ostream &OS) const; -class RangeTrait : public llvm::ImutContainerInfo<Range> { -public: - // When comparing if one Range is less than another, we should compare - // the actual APSInt values instead of their pointers. This keeps the order - // consistent (instead of comparing by pointer values) and can potentially - // be used to speed up some of the operations in RangeSet. - static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { - return *lhs.first < *rhs.first || - (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); - } + // In order to keep non-overlapping ranges sorted, we can compare only From + // points. + bool operator<(const Range &RHS) const { return From() < RHS.From(); } + + bool operator==(const Range &RHS) const { return Impl == RHS.Impl; } + bool operator!=(const Range &RHS) const { return !operator==(RHS); } + +private: + std::pair<const llvm::APSInt *, const llvm::APSInt *> Impl; }; -/// RangeSet contains a set of ranges. If the set is empty, then -/// there the value of a symbol is overly constrained and there are no -/// possible values for that symbol. +/// @class RangeSet is a persistent set of non-overlapping ranges. +/// +/// New RangeSet objects can be ONLY produced by RangeSet::Factory object, which +/// also supports the most common operations performed on range sets. +/// +/// Empty set corresponds to an overly constrained symbol meaning that there +/// are no possible values for that symbol. class RangeSet { - typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet; - PrimRangeSet ranges; // no need to make const, since it is an - // ImmutableSet - this allows default operator= - // to work. public: - typedef PrimRangeSet::Factory Factory; - typedef PrimRangeSet::iterator iterator; - - RangeSet(PrimRangeSet RS) : ranges(RS) {} - - /// Create a new set with all ranges of this set and RS. - /// Possible intersections are not checked here. - RangeSet addRange(Factory &F, const RangeSet &RS) { - PrimRangeSet Ranges(RS.ranges); - for (const auto &range : ranges) - Ranges = F.add(Ranges, range); - return RangeSet(Ranges); - } - - iterator begin() const { return ranges.begin(); } - iterator end() const { return ranges.end(); } + class Factory; - bool isEmpty() const { return ranges.isEmpty(); } +private: + // We use llvm::SmallVector as the underlying container for the following + // reasons: + // + // * Range sets are usually very simple, 1 or 2 ranges. + // That's why llvm::ImmutableSet is not perfect. + // + // * Ranges in sets are NOT overlapping, so it is natural to keep them + // sorted for efficient operations and queries. For this reason, + // llvm::SmallSet doesn't fit the requirements, it is not sorted when it + // is a vector. + // + // * Range set operations usually a bit harder than add/remove a range. + // Complex operations might do many of those for just one range set. + // Formerly it used to be llvm::ImmutableSet, which is inefficient for our + // purposes as we want to make these operations BOTH immutable AND + // efficient. + // + // * Iteration over ranges is widespread and a more cache-friendly + // structure is preferred. + using ImplType = llvm::SmallVector<Range, 4>; + + struct ContainerType : public ImplType, public llvm::FoldingSetNode { + void Profile(llvm::FoldingSetNodeID &ID) const { + for (const Range &It : *this) { + It.Profile(ID); + } + } + }; + // This is a non-owning pointer to an actual container. + // The memory is fully managed by the factory and is alive as long as the + // factory itself is alive. + // It is a pointer as opposed to a reference, so we can easily reassign + // RangeSet objects. + using UnderlyingType = const ContainerType *; + UnderlyingType Impl; - /// Construct a new RangeSet representing '{ [from, to] }'. - RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to) - : ranges(F.add(F.getEmptySet(), Range(from, to))) {} +public: + using const_iterator = ImplType::const_iterator; + + const_iterator begin() const { return Impl->begin(); } + const_iterator end() const { return Impl->end(); } + size_t size() const { return Impl->size(); } + + bool isEmpty() const { return Impl->empty(); } + + class Factory { + public: + Factory(BasicValueFactory &BV) : ValueFactory(BV) {} + + /// Create a new set with all ranges from both LHS and RHS. + /// Possible intersections are not checked here. + /// + /// Complexity: O(N + M) + /// where N = size(LHS), M = size(RHS) + RangeSet add(RangeSet LHS, RangeSet RHS); + /// Create a new set with all ranges from the original set plus the new one. + /// Possible intersections are not checked here. + /// + /// Complexity: O(N) + /// where N = size(Original) + RangeSet add(RangeSet Original, Range Element); + /// Create a new set with all ranges from the original set plus the point. + /// Possible intersections are not checked here. + /// + /// Complexity: O(N) + /// where N = size(Original) + RangeSet add(RangeSet Original, const llvm::APSInt &Point); + + RangeSet getEmptySet() { return &EmptySet; } + + /// Create a new set with just one range. + /// @{ + RangeSet getRangeSet(Range Origin); + RangeSet getRangeSet(const llvm::APSInt &From, const llvm::APSInt &To) { + return getRangeSet(Range(From, To)); + } + RangeSet getRangeSet(const llvm::APSInt &Origin) { + return getRangeSet(Origin, Origin); + } + /// @} + + /// Intersect the given range sets. + /// + /// Complexity: O(N + M) + /// where N = size(LHS), M = size(RHS) + RangeSet intersect(RangeSet LHS, RangeSet RHS); + /// Intersect the given set with the closed range [Lower, Upper]. + /// + /// Unlike the Range type, this range uses modular arithmetic, corresponding + /// to the common treatment of C integer overflow. Thus, if the Lower bound + /// is greater than the Upper bound, the range is taken to wrap around. This + /// is equivalent to taking the intersection with the two ranges [Min, + /// Upper] and [Lower, Max], or, alternatively, /removing/ all integers + /// between Upper and Lower. + /// + /// Complexity: O(N) + /// where N = size(What) + RangeSet intersect(RangeSet What, llvm::APSInt Lower, llvm::APSInt Upper); + /// Intersect the given range with the given point. + /// + /// The result can be either an empty set or a set containing the given + /// point depending on whether the point is in the range set. + /// + /// Complexity: O(logN) + /// where N = size(What) + RangeSet intersect(RangeSet What, llvm::APSInt Point); + + /// Delete the given point from the range set. + /// + /// Complexity: O(N) + /// where N = size(From) + RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point); + /// Negate the given range set. + /// + /// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus + /// operation under the values of the type. + /// + /// We also handle MIN because applying unary minus to MIN does not change + /// it. + /// Example 1: + /// char x = -128; // -128 is a MIN value in a range of 'char' + /// char y = -x; // y: -128 + /// + /// Example 2: + /// unsigned char x = 0; // 0 is a MIN value in a range of 'unsigned char' + /// unsigned char y = -x; // y: 0 + /// + /// And it makes us to separate the range + /// like [MIN, N] to [MIN, MIN] U [-N, MAX]. + /// For instance, whole range is {-128..127} and subrange is [-128,-126], + /// thus [-128,-127,-126,...] negates to [-128,...,126,127]. + /// + /// Negate restores disrupted ranges on bounds, + /// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B]. + /// + /// Negate is a self-inverse function, i.e. negate(negate(R)) == R. + /// + /// Complexity: O(N) + /// where N = size(What) + RangeSet negate(RangeSet What); + + /// Return associated value factory. + BasicValueFactory &getValueFactory() const { return ValueFactory; } + + private: + /// Return a persistent version of the given container. + RangeSet makePersistent(ContainerType &&From); + /// Construct a new persistent version of the given container. + ContainerType *construct(ContainerType &&From); + + RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS); + + // Many operations include producing new APSInt values and that's why + // we need this factory. + BasicValueFactory &ValueFactory; + // Allocator for all the created containers. + // Containers might own their own memory and that's why it is specific + // for the type, so it calls container destructors upon deletion. + llvm::SpecificBumpPtrAllocator<ContainerType> Arena; + // Usually we deal with the same ranges and range sets over and over. + // Here we track all created containers and try not to repeat ourselves. + llvm::FoldingSet<ContainerType> Cache; + static ContainerType EmptySet; + }; + + RangeSet(const RangeSet &) = default; + RangeSet &operator=(const RangeSet &) = default; + RangeSet(RangeSet &&) = default; + RangeSet &operator=(RangeSet &&) = default; + ~RangeSet() = default; + + /// Construct a new RangeSet representing '{ [From, To] }'. + RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To) + : RangeSet(F.getRangeSet(From, To)) {} /// Construct a new RangeSet representing the given point as a range. - RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {} + RangeSet(Factory &F, const llvm::APSInt &Point) + : RangeSet(F.getRangeSet(Point)) {} + + static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS) { + ID.AddPointer(RS.Impl); + } /// Profile - Generates a hash profile of this RangeSet for use /// by FoldingSet. - void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); } + void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, *this); } - /// getConcreteValue - If a symbol is contrained to equal a specific integer + /// getConcreteValue - If a symbol is constrained to equal a specific integer /// constant then this method returns that value. Otherwise, it returns /// NULL. const llvm::APSInt *getConcreteValue() const { - return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; + return Impl->size() == 1 ? begin()->getConcreteValue() : nullptr; } - /// Get a minimal value covered by the ranges in the set + /// Get the minimal value covered by the ranges in the set. + /// + /// Complexity: O(1) const llvm::APSInt &getMinValue() const; - /// Get a maximal value covered by the ranges in the set + /// Get the maximal value covered by the ranges in the set. + /// + /// Complexity: O(1) const llvm::APSInt &getMaxValue() const; -private: - void IntersectInRange(BasicValueFactory &BV, Factory &F, - const llvm::APSInt &Lower, const llvm::APSInt &Upper, - PrimRangeSet &newRanges, PrimRangeSet::iterator &i, - PrimRangeSet::iterator &e) const; + /// Test whether the given point is contained by any of the ranges. + /// + /// Complexity: O(logN) + /// where N = size(this) + bool contains(llvm::APSInt Point) const { return containsImpl(Point); } + + void dump(raw_ostream &OS) const; + + bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; } + bool operator!=(const RangeSet &Other) const { return !(*this == Other); } +private: + /* implicit */ RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {} + /* implicit */ RangeSet(UnderlyingType Ptr) : Impl(Ptr) {} + + /// Pin given points to the type represented by the current range set. + /// + /// This makes parameter points to be in-out parameters. + /// In order to maintain consistent types across all of the ranges in the set + /// and to keep all the operations to compare ONLY points of the same type, we + /// need to pin every point before any operation. + /// + /// @Returns true if the given points can be converted to the target type + /// without changing the values (i.e. trivially) and false otherwise. + /// @{ bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const; + bool pin(llvm::APSInt &Point) const; + /// @} -public: - RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, - llvm::APSInt Upper) const; - RangeSet Intersect(BasicValueFactory &BV, Factory &F, - const RangeSet &Other) const; - RangeSet Negate(BasicValueFactory &BV, Factory &F) const; - RangeSet Delete(BasicValueFactory &BV, Factory &F, - const llvm::APSInt &Point) const; - - void print(raw_ostream &os) const; - - bool operator==(const RangeSet &other) const { - return ranges == other.ranges; - } + // This version of this function modifies its arguments (pins it). + bool containsImpl(llvm::APSInt &Point) const; + + friend class Factory; }; using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>; @@ -213,6 +387,11 @@ private: static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); }; +/// Try to simplify a given symbolic expression's associated value based on the +/// constraints in State. This is needed because the Environment bindings are +/// not getting updated when a new constraint is added to the State. +SymbolRef simplify(ProgramStateRef State, SymbolRef Sym); + } // namespace ento } // namespace clang diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h index 07fc73a670f3..e4878d4e0156 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h @@ -146,7 +146,7 @@ public: Solver->addConstraint(NotExp); Optional<bool> isNotSat = Solver->check(); - if (!isSat.hasValue() || isNotSat.getValue()) + if (!isNotSat.hasValue() || isNotSat.getValue()) return nullptr; // This is the only solution, store it diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h index 4ea85f9730bb..87a49cf4ffe9 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -72,13 +72,27 @@ 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 dispatchCast(SVal val, QualType castTy) = 0; + SVal evalCastKind(UndefinedVal V, QualType CastTy, QualType OriginalTy); + SVal evalCastKind(UnknownVal V, QualType CastTy, QualType OriginalTy); + SVal evalCastKind(Loc V, QualType CastTy, QualType OriginalTy); + SVal evalCastKind(NonLoc V, QualType CastTy, QualType OriginalTy); + SVal evalCastSubKind(loc::ConcreteInt V, QualType CastTy, + QualType OriginalTy); + SVal evalCastSubKind(loc::GotoLabel V, QualType CastTy, QualType OriginalTy); + SVal evalCastSubKind(loc::MemRegionVal V, QualType CastTy, + QualType OriginalTy); + SVal evalCastSubKind(nonloc::CompoundVal V, QualType CastTy, + QualType OriginalTy); + SVal evalCastSubKind(nonloc::ConcreteInt V, QualType CastTy, + QualType OriginalTy); + SVal evalCastSubKind(nonloc::LazyCompoundVal V, QualType CastTy, + QualType OriginalTy); + SVal evalCastSubKind(nonloc::LocAsInteger V, QualType CastTy, + QualType OriginalTy); + SVal evalCastSubKind(nonloc::SymbolVal V, QualType CastTy, + QualType OriginalTy); + SVal evalCastSubKind(nonloc::PointerToMember V, QualType CastTy, + QualType OriginalTy); public: SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, @@ -102,7 +116,7 @@ public: Ty2->isIntegralOrEnumerationType())); } - SVal evalCast(SVal val, QualType castTy, QualType originalType); + SVal evalCast(SVal V, QualType CastTy, QualType OriginalTy); // Handles casts of type CK_IntegralCast. SVal evalIntegralCast(ProgramStateRef state, SVal val, QualType castTy, @@ -224,6 +238,14 @@ public: const LocationContext *LCtx, unsigned Count); + /// Conjure a symbol representing heap allocated memory region. + /// + /// Note, now, the expression *doesn't* need to represent a location. + /// But the type need to! + DefinedOrUnknownSVal getConjuredHeapSymbolVal(const Expr *E, + const LocationContext *LCtx, + QualType type, unsigned Count); + DefinedOrUnknownSVal getDerivedRegionValueSymbolVal( SymbolRef parentSymbol, const TypedValueRegion *region); @@ -366,6 +388,10 @@ public: return loc::ConcreteInt(BasicVals.getValue(integer)); } + /// Return MemRegionVal on success cast, otherwise return None. + Optional<loc::MemRegionVal> getCastedMemRegionVal(const MemRegion *region, + QualType type); + /// Make an SVal that represents the given symbol. This follows the convention /// of representing Loc-type symbols (symbolic pointers and references) /// as Loc values wrapping the symbol rather than as plain symbol values. diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h index bb295ab591d4..6199c8d8d179 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -201,6 +201,19 @@ public: SymExpr::symbol_iterator symbol_end() const { return SymExpr::symbol_end(); } + + /// Try to get a reasonable type for the given value. + /// + /// \returns The best approximation of the value type or Null. + /// In theory, all symbolic values should be typed, but this function + /// is still a WIP and might have a few blind spots. + /// + /// \note This function should not be used when the user has access to the + /// bound expression AST node as well, since AST always has exact types. + /// + /// \note Loc values are interpreted as pointer rvalues for the purposes of + /// this method. + QualType getType(const ASTContext &) const; }; inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { @@ -511,10 +524,11 @@ private: /// This value is qualified as NonLoc because neither loading nor storing /// operations are applied to it. Instead, the analyzer uses the L-value coming /// from pointer-to-member applied to an object. -/// This SVal is represented by a DeclaratorDecl which can be a member function -/// pointer or a member data pointer and a list of CXXBaseSpecifiers. This list -/// is required to accumulate the pointer-to-member cast history to figure out -/// the correct subobject field. +/// This SVal is represented by a NamedDecl which can be a member function +/// pointer or a member data pointer and an optional list of CXXBaseSpecifiers. +/// This list is required to accumulate the pointer-to-member cast history to +/// figure out the correct subobject field. In particular, implicit casts grow +/// this list and explicit casts like static_cast shrink this list. class PointerToMember : public NonLoc { friend class ento::SValBuilder; diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h index c3b590e4784e..d2461705d128 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h @@ -181,7 +181,8 @@ public: /// castRegion - Used by ExprEngine::VisitCast to handle casts from /// a MemRegion* to a specific location type. 'R' is the region being /// casted and 'CastToTy' the result type of the cast. - const MemRegion *castRegion(const MemRegion *region, QualType CastToTy); + Optional<const MemRegion *> castRegion(const MemRegion *region, + QualType CastToTy); virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, SymbolReaper &SymReaper) = 0; @@ -280,12 +281,6 @@ protected: QualType pointeeTy, uint64_t index = 0); - /// CastRetrievedVal - Used by subclasses of StoreManager to implement - /// implicit casts that arise from loads from regions that are reinterpreted - /// as another region. - SVal CastRetrievedVal(SVal val, const TypedValueRegion *region, - QualType castTy); - private: SVal getLValueFieldOrIvar(const Decl *decl, SVal base); }; |