diff options
Diffstat (limited to 'contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive')
31 files changed, 1527 insertions, 1066 deletions
diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h index 4b7d6054cd87..f1c50e721937 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h @@ -21,8 +21,8 @@ class APSIntType { bool IsUnsigned; public: - APSIntType(uint32_t Width, bool Unsigned) - : BitWidth(Width), IsUnsigned(Unsigned) {} + constexpr APSIntType(uint32_t Width, bool Unsigned) + : BitWidth(Width), IsUnsigned(Unsigned) {} /* implicit */ APSIntType(const llvm::APSInt &Value) : BitWidth(Value.getBitWidth()), IsUnsigned(Value.isUnsigned()) {} diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h index bb598af68166..ec503b41b381 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h @@ -34,7 +34,6 @@ namespace clang { class CXXBaseSpecifier; -class DeclaratorDecl; namespace ento { @@ -67,10 +66,14 @@ class LazyCompoundValData : public llvm::FoldingSetNode { public: LazyCompoundValData(const StoreRef &st, const TypedValueRegion *r) : store(st), region(r) { + assert(r); assert(NonLoc::isCompoundType(r->getValueType())); } + /// It might return null. const void *getStore() const { return store.getStore(); } + + LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion *getRegion() const { return region; } static void Profile(llvm::FoldingSetNodeID& ID, @@ -98,6 +101,8 @@ public: llvm::ImmutableList<const CXXBaseSpecifier *> L); void Profile(llvm::FoldingSetNodeID &ID) { Profile(ID, D, L); } + + /// It might return null. const NamedDecl *getDeclaratorDecl() const { return D; } llvm::ImmutableList<const CXXBaseSpecifier *> getCXXBaseList() const { @@ -147,9 +152,15 @@ public: T = AT->getValueType(); } - assert(T->isIntegralOrEnumerationType() || Loc::isLocType(T)); - return APSIntType(Ctx.getIntWidth(T), - !T->isSignedIntegerOrEnumerationType()); + if (T->isIntegralOrEnumerationType() || Loc::isLocType(T)) { + return APSIntType(Ctx.getIntWidth(T), + !T->isSignedIntegerOrEnumerationType()); + } else { + // implicitly handle case of T->isFixedPointType() + return APSIntType(Ctx.getIntWidth(T), T->isUnsignedFixedPointType()); + } + + llvm_unreachable("Unsupported type in getAPSIntType!"); } /// Convert - Create a new persistent APSInt with the same value as 'From' @@ -221,14 +232,6 @@ public: return getValue(0, Ctx.getTypeSize(T), true); } - const llvm::APSInt &getZeroWithPtrWidth(bool isUnsigned = true) { - return getValue(0, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned); - } - - const llvm::APSInt &getIntWithPtrWidth(uint64_t X, bool isUnsigned) { - return getValue(X, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned); - } - const llvm::APSInt &getTruthValue(bool b, QualType T) { return getValue(b ? 1 : 0, Ctx.getIntWidth(T), T->isUnsignedIntegerOrEnumerationType()); diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h new file mode 100644 index 000000000000..965838a4408c --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h @@ -0,0 +1,257 @@ +//===- CallDescription.h - function/method call matching --*- 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 +// +//===----------------------------------------------------------------------===// +// +/// \file This file defines a generic mechanism for matching for function and +/// method calls of C, C++, and Objective-C languages. Instances of these +/// classes are frequently used together with the CallEvent classes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLDESCRIPTION_H +#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLDESCRIPTION_H + +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/Support/Compiler.h" +#include <optional> +#include <vector> + +namespace clang { +class IdentifierInfo; +} // namespace clang + +namespace clang { +namespace ento { + +enum CallDescriptionFlags : unsigned { + CDF_None = 0, + + /// Describes a C standard function that is sometimes implemented as a macro + /// that expands to a compiler builtin with some __builtin prefix. + /// The builtin may as well have a few extra arguments on top of the requested + /// number of arguments. + CDF_MaybeBuiltin = 1 << 0, +}; + +/// This class represents a description of a function call using the number of +/// arguments and the name of the function. +class CallDescription { + friend class CallEvent; + using MaybeCount = std::optional<unsigned>; + + mutable std::optional<const IdentifierInfo *> II; + // The list of the qualified names used to identify the specified CallEvent, + // e.g. "{a, b}" represent the qualified names, like "a::b". + std::vector<std::string> QualifiedName; + MaybeCount RequiredArgs; + MaybeCount RequiredParams; + int Flags; + +public: + /// Constructs a CallDescription object. + /// + /// @param QualifiedName The list of the name qualifiers of the function that + /// will be matched. The user is allowed to skip any of the qualifiers. + /// For example, {"std", "basic_string", "c_str"} would match both + /// std::basic_string<...>::c_str() and std::__1::basic_string<...>::c_str(). + /// + /// @param RequiredArgs The number of arguments that is expected to match a + /// call. Omit this parameter to match every occurrence of call with a given + /// name regardless the number of arguments. + CallDescription(CallDescriptionFlags Flags, ArrayRef<StringRef> QualifiedName, + MaybeCount RequiredArgs = std::nullopt, + MaybeCount RequiredParams = std::nullopt); + + /// Construct a CallDescription with default flags. + CallDescription(ArrayRef<StringRef> QualifiedName, + MaybeCount RequiredArgs = std::nullopt, + MaybeCount RequiredParams = std::nullopt); + + CallDescription(std::nullptr_t) = delete; + + /// Get the name of the function that this object matches. + StringRef getFunctionName() const { return QualifiedName.back(); } + + /// Get the qualified name parts in reversed order. + /// E.g. { "std", "vector", "data" } -> "vector", "std" + auto begin_qualified_name_parts() const { + return std::next(QualifiedName.rbegin()); + } + auto end_qualified_name_parts() const { return QualifiedName.rend(); } + + /// It's false, if and only if we expect a single identifier, such as + /// `getenv`. It's true for `std::swap`, or `my::detail::container::data`. + bool hasQualifiedNameParts() const { return QualifiedName.size() > 1; } + + /// @name Matching CallDescriptions against a CallEvent + /// @{ + + /// Returns true if the CallEvent is a call to a function that matches + /// the CallDescription. + /// + /// \note This function is not intended to be used to match Obj-C method + /// calls. + bool matches(const CallEvent &Call) const; + + /// Returns true whether the CallEvent matches on any of the CallDescriptions + /// supplied. + /// + /// \note This function is not intended to be used to match Obj-C method + /// calls. + friend bool matchesAny(const CallEvent &Call, const CallDescription &CD1) { + return CD1.matches(Call); + } + + /// \copydoc clang::ento::CallDescription::matchesAny(const CallEvent &, const CallDescription &) + template <typename... Ts> + friend bool matchesAny(const CallEvent &Call, const CallDescription &CD1, + const Ts &...CDs) { + return CD1.matches(Call) || matchesAny(Call, CDs...); + } + /// @} + + /// @name Matching CallDescriptions against a CallExpr + /// @{ + + /// Returns true if the CallExpr is a call to a function that matches the + /// CallDescription. + /// + /// When available, always prefer matching with a CallEvent! This function + /// exists only when that is not available, for example, when _only_ + /// syntactic check is done on a piece of code. + /// + /// Also, StdLibraryFunctionsChecker::Signature is likely a better candicade + /// for syntactic only matching if you are writing a new checker. This is + /// handy if a CallDescriptionMap is already there. + /// + /// The function is imprecise because CallEvent may know path sensitive + /// information, such as the precise argument count (see comments for + /// CallEvent::getNumArgs), the called function if it was called through a + /// function pointer, and other information not available syntactically. + bool matchesAsWritten(const CallExpr &CE) const; + + /// Returns true whether the CallExpr matches on any of the CallDescriptions + /// supplied. + /// + /// \note This function is not intended to be used to match Obj-C method + /// calls. + friend bool matchesAnyAsWritten(const CallExpr &CE, + const CallDescription &CD1) { + return CD1.matchesAsWritten(CE); + } + + /// \copydoc clang::ento::CallDescription::matchesAnyAsWritten(const CallExpr &, const CallDescription &) + template <typename... Ts> + friend bool matchesAnyAsWritten(const CallExpr &CE, + const CallDescription &CD1, + const Ts &...CDs) { + return CD1.matchesAsWritten(CE) || matchesAnyAsWritten(CE, CDs...); + } + /// @} + +private: + bool matchesImpl(const FunctionDecl *Callee, size_t ArgCount, + size_t ParamCount) const; +}; + +/// An immutable map from CallDescriptions to arbitrary data. Provides a unified +/// way for checkers to react on function calls. +template <typename T> class CallDescriptionMap { + friend class CallDescriptionSet; + + // Some call descriptions aren't easily hashable (eg., the ones with qualified + // names in which some sections are omitted), so let's put them + // in a simple vector and use linear lookup. + // TODO: Implement an actual map for fast lookup for "hashable" call + // descriptions (eg., the ones for C functions that just match the name). + std::vector<std::pair<CallDescription, T>> LinearMap; + +public: + CallDescriptionMap( + std::initializer_list<std::pair<CallDescription, T>> &&List) + : LinearMap(List) {} + + template <typename InputIt> + CallDescriptionMap(InputIt First, InputIt Last) : LinearMap(First, Last) {} + + ~CallDescriptionMap() = default; + + // These maps are usually stored once per checker, so let's make sure + // we don't do redundant copies. + CallDescriptionMap(const CallDescriptionMap &) = delete; + CallDescriptionMap &operator=(const CallDescription &) = delete; + + CallDescriptionMap(CallDescriptionMap &&) = default; + CallDescriptionMap &operator=(CallDescriptionMap &&) = default; + + [[nodiscard]] const T *lookup(const CallEvent &Call) const { + // Slow path: linear lookup. + // TODO: Implement some sort of fast path. + for (const std::pair<CallDescription, T> &I : LinearMap) + if (I.first.matches(Call)) + return &I.second; + + return nullptr; + } + + /// When available, always prefer lookup with a CallEvent! This function + /// exists only when that is not available, for example, when _only_ + /// syntactic check is done on a piece of code. + /// + /// Also, StdLibraryFunctionsChecker::Signature is likely a better candicade + /// for syntactic only matching if you are writing a new checker. This is + /// handy if a CallDescriptionMap is already there. + /// + /// The function is imprecise because CallEvent may know path sensitive + /// information, such as the precise argument count (see comments for + /// CallEvent::getNumArgs), the called function if it was called through a + /// function pointer, and other information not available syntactically. + [[nodiscard]] const T *lookupAsWritten(const CallExpr &Call) const { + // Slow path: linear lookup. + // TODO: Implement some sort of fast path. + for (const std::pair<CallDescription, T> &I : LinearMap) + if (I.first.matchesAsWritten(Call)) + return &I.second; + + return nullptr; + } +}; + +/// An immutable set of CallDescriptions. +/// Checkers can efficiently decide if a given CallEvent matches any +/// CallDescription in the set. +class CallDescriptionSet { + CallDescriptionMap<bool /*unused*/> Impl = {}; + +public: + CallDescriptionSet(std::initializer_list<CallDescription> &&List); + + CallDescriptionSet(const CallDescriptionSet &) = delete; + CallDescriptionSet &operator=(const CallDescription &) = delete; + + [[nodiscard]] bool contains(const CallEvent &Call) const; + + /// When available, always prefer lookup with a CallEvent! This function + /// exists only when that is not available, for example, when _only_ + /// syntactic check is done on a piece of code. + /// + /// Also, StdLibraryFunctionsChecker::Signature is likely a better candicade + /// for syntactic only matching if you are writing a new checker. This is + /// handy if a CallDescriptionMap is already there. + /// + /// The function is imprecise because CallEvent may know path sensitive + /// information, such as the precise argument count (see comments for + /// CallEvent::getNumArgs), the called function if it was called through a + /// function pointer, and other information not available syntactically. + [[nodiscard]] bool containsAsWritten(const CallExpr &CE) const; +}; + +} // namespace ento +} // namespace clang + +#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLDESCRIPTION_H diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h index 060fff1a7407..0d36587484bf 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h @@ -45,6 +45,7 @@ #include "llvm/Support/ErrorHandling.h" #include <cassert> #include <limits> +#include <optional> #include <utility> namespace clang { @@ -76,22 +77,24 @@ enum CallEventKind { }; class CallEvent; -class CallDescription; -template<typename T = CallEvent> +template <typename T = CallEvent> class CallEventRef : public IntrusiveRefCntPtr<const T> { public: CallEventRef(const T *Call) : IntrusiveRefCntPtr<const T>(Call) {} CallEventRef(const CallEventRef &Orig) : IntrusiveRefCntPtr<const T>(Orig) {} + // The copy assignment operator is defined as deleted pending further + // motivation. + CallEventRef &operator=(const CallEventRef &) = delete; + CallEventRef<T> cloneWithState(ProgramStateRef State) const { return this->get()->template cloneWithState<T>(State); } // Allow implicit conversions to a superclass type, since CallEventRef // behaves like a pointer-to-const. - template <typename SuperT> - operator CallEventRef<SuperT> () const { + template <typename SuperT> operator CallEventRef<SuperT>() const { return this->get(); } }; @@ -114,12 +117,18 @@ class RuntimeDefinition { /// precise. const MemRegion *R = nullptr; + /// A definition is foreign if it has been imported and newly created by the + /// ASTImporter. This can be true only if CTU is enabled. + const bool Foreign = false; + public: RuntimeDefinition() = default; - RuntimeDefinition(const Decl *InD): D(InD) {} - RuntimeDefinition(const Decl *InD, const MemRegion *InR): D(InD), R(InR) {} + RuntimeDefinition(const Decl *InD) : D(InD) {} + RuntimeDefinition(const Decl *InD, bool Foreign) : D(InD), Foreign(Foreign) {} + RuntimeDefinition(const Decl *InD, const MemRegion *InR) : D(InD), R(InR) {} const Decl *getDecl() { return D; } + bool isForeign() const { return Foreign; } /// Check if the definition we have is precise. /// If not, it is possible that the call dispatches to another definition at @@ -148,6 +157,8 @@ private: ProgramStateRef State; const LocationContext *LCtx; llvm::PointerUnion<const Expr *, const Decl *> Origin; + CFGBlock::ConstCFGElementRef ElemRef = {nullptr, 0}; + mutable std::optional<bool> Foreign; // Set by CTU analysis. protected: // This is user data for subclasses. @@ -169,16 +180,19 @@ private: protected: friend class CallEventManager; - CallEvent(const Expr *E, ProgramStateRef state, const LocationContext *lctx) - : State(std::move(state)), LCtx(lctx), Origin(E) {} + CallEvent(const Expr *E, ProgramStateRef state, const LocationContext *lctx, + CFGBlock::ConstCFGElementRef ElemRef) + : State(std::move(state)), LCtx(lctx), Origin(E), ElemRef(ElemRef) {} - CallEvent(const Decl *D, ProgramStateRef state, const LocationContext *lctx) - : State(std::move(state)), LCtx(lctx), Origin(D) {} + CallEvent(const Decl *D, ProgramStateRef state, const LocationContext *lctx, + CFGBlock::ConstCFGElementRef ElemRef) + : State(std::move(state)), LCtx(lctx), Origin(D), ElemRef(ElemRef) {} // DO NOT MAKE PUBLIC CallEvent(const CallEvent &Original) : State(Original.State), LCtx(Original.LCtx), Origin(Original.Origin), - Data(Original.Data), Location(Original.Location) {} + ElemRef(Original.ElemRef), Data(Original.Data), + Location(Original.Location) {} /// Copies this CallEvent, with vtable intact, into a new block of memory. virtual void cloneTo(void *Dest) const = 0; @@ -192,8 +206,9 @@ protected: /// Used to specify non-argument regions that will be invalidated as a /// result of this call. - virtual void getExtraInvalidatedValues(ValueList &Values, - RegionAndSymbolInvalidationTraits *ETraits) const {} + virtual void + getExtraInvalidatedValues(ValueList &Values, + RegionAndSymbolInvalidationTraits *ETraits) const {} public: CallEvent &operator=(const CallEvent &) = delete; @@ -209,14 +224,20 @@ public: return Origin.dyn_cast<const Decl *>(); } - /// The state in which the call is being evaluated. - const ProgramStateRef &getState() const { - return State; + bool isForeign() const { + assert(Foreign && "Foreign must be set before querying"); + return *Foreign; } + void setForeign(bool B) const { Foreign = B; } + + /// The state in which the call is being evaluated. + const ProgramStateRef &getState() const { return State; } /// The context in which the call is being evaluated. - const LocationContext *getLocationContext() const { - return LCtx; + const LocationContext *getLocationContext() const { return LCtx; } + + const CFGBlock::ConstCFGElementRef &getCFGElementRef() const { + return ElemRef; } /// Returns the definition of the function or method that will be @@ -245,7 +266,7 @@ public: SourceLocation Loc = D->getLocation(); if (Loc.isValid()) { const SourceManager &SM = - getState()->getStateManager().getContext().getSourceManager(); + getState()->getStateManager().getContext().getSourceManager(); return SM.isInSystemHeader(D->getLocation()); } @@ -257,20 +278,6 @@ public: return false; } - /// Returns true if the CallEvent is a call to a function that matches - /// the CallDescription. - /// - /// Note that this function is not intended to be used to match Obj-C method - /// calls. - bool isCalled(const CallDescription &CD) const; - - /// Returns true whether the CallEvent is any of the CallDescriptions supplied - /// as a parameter. - template <typename FirstCallDesc, typename... CallDescs> - bool isCalled(const FirstCallDesc &First, const CallDescs &... Rest) const { - return isCalled(First) || isCalled(Rest...); - } - /// Returns a source range for the entire call, suitable for /// outputting in diagnostics. virtual SourceRange getSourceRange() const { @@ -313,9 +320,7 @@ public: // NOTE: The exact semantics of this are still being defined! // We don't really want a list of hardcoded exceptions in the long run, // but we don't want duplicated lists of known APIs in the short term either. - virtual bool argumentsMayEscape() const { - return hasNonZeroCallbackArg(); - } + virtual bool argumentsMayEscape() const { return hasNonZeroCallbackArg(); } /// Returns true if the callee is an externally-visible function in the /// top-level namespace, such as \c malloc. @@ -416,14 +421,15 @@ public: bool isArgumentConstructedDirectly(unsigned Index) const { // This assumes that the object was not yet removed from the state. return ExprEngine::getObjectUnderConstruction( - getState(), {getOriginExpr(), Index}, getLocationContext()).hasValue(); + getState(), {getOriginExpr(), Index}, getLocationContext()) + .has_value(); } /// Some calls have parameter numbering mismatched from argument numbering. /// This function converts an argument index to the corresponding - /// parameter index. Returns None is the argument doesn't correspond + /// parameter index. Returns std::nullopt is the argument doesn't correspond /// to any parameter variable. - virtual Optional<unsigned> + virtual std::optional<unsigned> getAdjustedParameterIndex(unsigned ASTArgumentIndex) const { return ASTArgumentIndex; } @@ -442,7 +448,15 @@ public: /// If the call returns a C++ record type then the region of its return value /// can be retrieved from its construction context. - Optional<SVal> getReturnValueUnderConstruction() const; + std::optional<SVal> getReturnValueUnderConstruction() const; + + // Returns the CallEvent representing the caller of this function + const CallEventRef<> getCaller() const; + + // Returns true if the function was called from a standard library function. + // If not or could not get the caller (it may be a top level function) + // returns false. + bool isCalledFromSystemHeader() const; // Iterator access to formal parameters and their types. private: @@ -484,11 +498,13 @@ public: class AnyFunctionCall : public CallEvent { protected: AnyFunctionCall(const Expr *E, ProgramStateRef St, - const LocationContext *LCtx) - : CallEvent(E, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : CallEvent(E, St, LCtx, ElemRef) {} AnyFunctionCall(const Decl *D, ProgramStateRef St, - const LocationContext *LCtx) - : CallEvent(D, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : CallEvent(D, St, LCtx, ElemRef) {} AnyFunctionCall(const AnyFunctionCall &Other) = default; public: @@ -521,8 +537,9 @@ class SimpleFunctionCall : public AnyFunctionCall { protected: SimpleFunctionCall(const CallExpr *CE, ProgramStateRef St, - const LocationContext *LCtx) - : AnyFunctionCall(CE, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : AnyFunctionCall(CE, St, LCtx, ElemRef) {} SimpleFunctionCall(const SimpleFunctionCall &Other) = default; void cloneTo(void *Dest) const override { @@ -557,15 +574,16 @@ class BlockCall : public CallEvent { friend class CallEventManager; protected: - BlockCall(const CallExpr *CE, ProgramStateRef St, - const LocationContext *LCtx) - : CallEvent(CE, St, LCtx) {} + BlockCall(const CallExpr *CE, ProgramStateRef St, const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : CallEvent(CE, St, LCtx, ElemRef) {} BlockCall(const BlockCall &Other) = default; void cloneTo(void *Dest) const override { new (Dest) BlockCall(*this); } - void getExtraInvalidatedValues(ValueList &Values, - RegionAndSymbolInvalidationTraits *ETraits) const override; + void getExtraInvalidatedValues( + ValueList &Values, + RegionAndSymbolInvalidationTraits *ETraits) const override; public: const CallExpr *getOriginExpr() const override { @@ -605,10 +623,9 @@ public: const BlockDataRegion *BR = getBlockRegion(); assert(BR && "Block converted from lambda must have a block region"); - auto I = BR->referenced_vars_begin(); - assert(I != BR->referenced_vars_end()); - - return I.getCapturedRegion(); + auto ReferencedVars = BR->referenced_vars(); + assert(!ReferencedVars.empty()); + return ReferencedVars.begin().getCapturedRegion(); } RuntimeDefinition getRuntimeDefinition() const override { @@ -636,14 +653,12 @@ public: // the block body and analyze the operator() method on the captured lambda. const VarDecl *LambdaVD = getRegionStoringCapturedLambda()->getDecl(); const CXXRecordDecl *LambdaDecl = LambdaVD->getType()->getAsCXXRecordDecl(); - CXXMethodDecl* LambdaCallOperator = LambdaDecl->getLambdaCallOperator(); + CXXMethodDecl *LambdaCallOperator = LambdaDecl->getLambdaCallOperator(); return RuntimeDefinition(LambdaCallOperator); } - bool argumentsMayEscape() const override { - return true; - } + bool argumentsMayEscape() const override { return true; } void getInitialStackFrameContents(const StackFrameContext *CalleeCtx, BindingsTy &Bindings) const override; @@ -661,15 +676,18 @@ public: class CXXInstanceCall : public AnyFunctionCall { protected: CXXInstanceCall(const CallExpr *CE, ProgramStateRef St, - const LocationContext *LCtx) - : AnyFunctionCall(CE, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : AnyFunctionCall(CE, St, LCtx, ElemRef) {} CXXInstanceCall(const FunctionDecl *D, ProgramStateRef St, - const LocationContext *LCtx) - : AnyFunctionCall(D, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : AnyFunctionCall(D, St, LCtx, ElemRef) {} CXXInstanceCall(const CXXInstanceCall &Other) = default; - void getExtraInvalidatedValues(ValueList &Values, - RegionAndSymbolInvalidationTraits *ETraits) const override; + void getExtraInvalidatedValues( + ValueList &Values, + RegionAndSymbolInvalidationTraits *ETraits) const override; public: /// Returns the expression representing the implicit 'this' object. @@ -699,8 +717,9 @@ class CXXMemberCall : public CXXInstanceCall { protected: CXXMemberCall(const CXXMemberCallExpr *CE, ProgramStateRef St, - const LocationContext *LCtx) - : CXXInstanceCall(CE, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : CXXInstanceCall(CE, St, LCtx, ElemRef) {} CXXMemberCall(const CXXMemberCall &Other) = default; void cloneTo(void *Dest) const override { new (Dest) CXXMemberCall(*this); } @@ -741,8 +760,9 @@ class CXXMemberOperatorCall : public CXXInstanceCall { protected: CXXMemberOperatorCall(const CXXOperatorCallExpr *CE, ProgramStateRef St, - const LocationContext *LCtx) - : CXXInstanceCall(CE, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : CXXInstanceCall(CE, St, LCtx, ElemRef) {} CXXMemberOperatorCall(const CXXMemberOperatorCall &Other) = default; void cloneTo(void *Dest) const override { @@ -771,12 +791,13 @@ public: return CA->getKind() == CE_CXXMemberOperator; } - Optional<unsigned> + std::optional<unsigned> getAdjustedParameterIndex(unsigned ASTArgumentIndex) const override { // For member operator calls argument 0 on the expression corresponds // to implicit this-parameter on the declaration. - return (ASTArgumentIndex > 0) ? Optional<unsigned>(ASTArgumentIndex - 1) - : None; + return (ASTArgumentIndex > 0) + ? std::optional<unsigned>(ASTArgumentIndex - 1) + : std::nullopt; } unsigned getASTArgumentIndex(unsigned CallArgumentIndex) const override { @@ -807,17 +828,26 @@ protected: /// \param Target The object region to be destructed. /// \param St The path-sensitive state at this point in the program. /// \param LCtx The location context at this point in the program. + /// \param ElemRef The reference to this destructor in the CFG. + /// + /// FIXME: Eventually we want to drop \param Target and deduce it from + /// \param ElemRef. To do that we need to migrate the logic for target + /// region lookup from ExprEngine::ProcessImplicitDtor() and make it + /// independent from ExprEngine. CXXDestructorCall(const CXXDestructorDecl *DD, const Stmt *Trigger, const MemRegion *Target, bool IsBaseDestructor, - ProgramStateRef St, const LocationContext *LCtx) - : CXXInstanceCall(DD, St, LCtx) { + ProgramStateRef St, const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : CXXInstanceCall(DD, St, LCtx, ElemRef) { Data = DtorDataTy(Target, IsBaseDestructor).getOpaqueValue(); Location = Trigger->getEndLoc(); } CXXDestructorCall(const CXXDestructorCall &Other) = default; - void cloneTo(void *Dest) const override {new (Dest) CXXDestructorCall(*this);} + void cloneTo(void *Dest) const override { + new (Dest) CXXDestructorCall(*this); + } public: SourceRange getSourceRange() const override { return Location; } @@ -846,15 +876,17 @@ public: class AnyCXXConstructorCall : public AnyFunctionCall { protected: AnyCXXConstructorCall(const Expr *E, const MemRegion *Target, - ProgramStateRef St, const LocationContext *LCtx) - : AnyFunctionCall(E, St, LCtx) { + ProgramStateRef St, const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : AnyFunctionCall(E, St, LCtx, ElemRef) { assert(E && (isa<CXXConstructExpr>(E) || isa<CXXInheritedCtorInitExpr>(E))); // Target may be null when the region is unknown. Data = Target; } - void getExtraInvalidatedValues(ValueList &Values, - RegionAndSymbolInvalidationTraits *ETraits) const override; + void getExtraInvalidatedValues( + ValueList &Values, + RegionAndSymbolInvalidationTraits *ETraits) const override; void getInitialStackFrameContents(const StackFrameContext *CalleeCtx, BindingsTy &Bindings) const override; @@ -883,13 +915,20 @@ protected: /// a new symbolic region will be used. /// \param St The path-sensitive state at this point in the program. /// \param LCtx The location context at this point in the program. + /// \param ElemRef The reference to this constructor in the CFG. + /// + /// FIXME: Eventually we want to drop \param Target and deduce it from + /// \param ElemRef. CXXConstructorCall(const CXXConstructExpr *CE, const MemRegion *Target, - ProgramStateRef St, const LocationContext *LCtx) - : AnyCXXConstructorCall(CE, Target, St, LCtx) {} + ProgramStateRef St, const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : AnyCXXConstructorCall(CE, Target, St, LCtx, ElemRef) {} CXXConstructorCall(const CXXConstructorCall &Other) = default; - void cloneTo(void *Dest) const override { new (Dest) CXXConstructorCall(*this); } + void cloneTo(void *Dest) const override { + new (Dest) CXXConstructorCall(*this); + } public: const CXXConstructExpr *getOriginExpr() const override { @@ -940,8 +979,9 @@ class CXXInheritedConstructorCall : public AnyCXXConstructorCall { protected: CXXInheritedConstructorCall(const CXXInheritedCtorInitExpr *CE, const MemRegion *Target, ProgramStateRef St, - const LocationContext *LCtx) - : AnyCXXConstructorCall(CE, Target, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : AnyCXXConstructorCall(CE, Target, St, LCtx, ElemRef) {} CXXInheritedConstructorCall(const CXXInheritedConstructorCall &Other) = default; @@ -1002,11 +1042,14 @@ class CXXAllocatorCall : public AnyFunctionCall { protected: CXXAllocatorCall(const CXXNewExpr *E, ProgramStateRef St, - const LocationContext *LCtx) - : AnyFunctionCall(E, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : AnyFunctionCall(E, St, LCtx, ElemRef) {} CXXAllocatorCall(const CXXAllocatorCall &Other) = default; - void cloneTo(void *Dest) const override { new (Dest) CXXAllocatorCall(*this); } + void cloneTo(void *Dest) const override { + new (Dest) CXXAllocatorCall(*this); + } public: const CXXNewExpr *getOriginExpr() const override { @@ -1018,9 +1061,8 @@ public: } SVal getObjectUnderConstruction() const { - return ExprEngine::getObjectUnderConstruction(getState(), getOriginExpr(), - getLocationContext()) - .getValue(); + return *ExprEngine::getObjectUnderConstruction(getState(), getOriginExpr(), + getLocationContext()); } /// Number of non-placement arguments to the call. It is equal to 2 for @@ -1034,6 +1076,18 @@ public: return getOriginExpr()->getNumPlacementArgs() + getNumImplicitArgs(); } + bool isArray() const { return getOriginExpr()->isArray(); } + + std::optional<const clang::Expr *> getArraySizeExpr() const { + return getOriginExpr()->getArraySize(); + } + + SVal getArraySizeVal() const { + assert(isArray() && "The allocator call doesn't allocate and array!"); + + return getState()->getSVal(*getArraySizeExpr(), getLocationContext()); + } + const Expr *getArgExpr(unsigned Index) const override { // The first argument of an allocator call is the size of the allocation. if (Index < getNumImplicitArgs()) @@ -1072,8 +1126,9 @@ class CXXDeallocatorCall : public AnyFunctionCall { protected: CXXDeallocatorCall(const CXXDeleteExpr *E, ProgramStateRef St, - const LocationContext *LCtx) - : AnyFunctionCall(E, St, LCtx) {} + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : AnyFunctionCall(E, St, LCtx, ElemRef) {} CXXDeallocatorCall(const CXXDeallocatorCall &Other) = default; void cloneTo(void *Dest) const override { @@ -1108,11 +1163,7 @@ public: // // Note to maintainers: OCM_Message should always be last, since it does not // need to fit in the Data field's low bits. -enum ObjCMessageKind { - OCM_PropertyAccess, - OCM_Subscript, - OCM_Message -}; +enum ObjCMessageKind { OCM_PropertyAccess, OCM_Subscript, OCM_Message }; /// Represents any expression that calls an Objective-C method. /// @@ -1124,8 +1175,9 @@ class ObjCMethodCall : public CallEvent { protected: ObjCMethodCall(const ObjCMessageExpr *Msg, ProgramStateRef St, - const LocationContext *LCtx) - : CallEvent(Msg, St, LCtx) { + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) + : CallEvent(Msg, St, LCtx, ElemRef) { Data = nullptr; } @@ -1133,8 +1185,9 @@ protected: void cloneTo(void *Dest) const override { new (Dest) ObjCMethodCall(*this); } - void getExtraInvalidatedValues(ValueList &Values, - RegionAndSymbolInvalidationTraits *ETraits) const override; + void getExtraInvalidatedValues( + ValueList &Values, + RegionAndSymbolInvalidationTraits *ETraits) const override; /// Check if the selector may have multiple definitions (may have overrides). virtual bool canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl, @@ -1149,9 +1202,7 @@ public: return getOriginExpr()->getMethodDecl(); } - unsigned getNumArgs() const override { - return getOriginExpr()->getNumArgs(); - } + unsigned getNumArgs() const override { return getOriginExpr()->getNumArgs(); } const Expr *getArgExpr(unsigned Index) const override { return getOriginExpr()->getArg(Index); @@ -1165,9 +1216,7 @@ public: return getOriginExpr()->getMethodFamily(); } - Selector getSelector() const { - return getOriginExpr()->getSelector(); - } + Selector getSelector() const { return getOriginExpr()->getSelector(); } SourceRange getSourceRange() const override; @@ -1215,7 +1264,7 @@ public: void getInitialStackFrameContents(const StackFrameContext *CalleeCtx, BindingsTy &Bindings) const override; - ArrayRef<ParmVarDecl*> parameters() const override; + ArrayRef<ParmVarDecl *> parameters() const override; Kind getKind() const override { return CE_ObjCMessage; } StringRef getKindAsString() const override { return "ObjCMethodCall"; } @@ -1225,99 +1274,6 @@ public: } }; -enum CallDescriptionFlags : int { - /// Describes a C standard function that is sometimes implemented as a macro - /// that expands to a compiler builtin with some __builtin prefix. - /// The builtin may as well have a few extra arguments on top of the requested - /// number of arguments. - CDF_MaybeBuiltin = 1 << 0, -}; - -/// This class represents a description of a function call using the number of -/// arguments and the name of the function. -class CallDescription { - friend CallEvent; - - mutable IdentifierInfo *II = nullptr; - mutable bool IsLookupDone = false; - // The list of the qualified names used to identify the specified CallEvent, - // e.g. "{a, b}" represent the qualified names, like "a::b". - std::vector<const char *> QualifiedName; - Optional<unsigned> RequiredArgs; - Optional<size_t> RequiredParams; - int Flags; - - // A constructor helper. - static Optional<size_t> readRequiredParams(Optional<unsigned> RequiredArgs, - Optional<size_t> RequiredParams) { - if (RequiredParams) - return RequiredParams; - if (RequiredArgs) - return static_cast<size_t>(*RequiredArgs); - return None; - } - -public: - /// Constructs a CallDescription object. - /// - /// @param QualifiedName The list of the name qualifiers of the function that - /// will be matched. The user is allowed to skip any of the qualifiers. - /// For example, {"std", "basic_string", "c_str"} would match both - /// std::basic_string<...>::c_str() and std::__1::basic_string<...>::c_str(). - /// - /// @param RequiredArgs The number of arguments that is expected to match a - /// call. Omit this parameter to match every occurrence of call with a given - /// name regardless the number of arguments. - CallDescription(int Flags, ArrayRef<const char *> QualifiedName, - Optional<unsigned> RequiredArgs = None, - Optional<size_t> RequiredParams = None) - : QualifiedName(QualifiedName), RequiredArgs(RequiredArgs), - RequiredParams(readRequiredParams(RequiredArgs, RequiredParams)), - Flags(Flags) {} - - /// Construct a CallDescription with default flags. - CallDescription(ArrayRef<const char *> QualifiedName, - Optional<unsigned> RequiredArgs = None, - Optional<size_t> RequiredParams = None) - : CallDescription(0, QualifiedName, RequiredArgs, RequiredParams) {} - - /// Get the name of the function that this object matches. - StringRef getFunctionName() const { return QualifiedName.back(); } -}; - -/// An immutable map from CallDescriptions to arbitrary data. Provides a unified -/// way for checkers to react on function calls. -template <typename T> class CallDescriptionMap { - // Some call descriptions aren't easily hashable (eg., the ones with qualified - // names in which some sections are omitted), so let's put them - // in a simple vector and use linear lookup. - // TODO: Implement an actual map for fast lookup for "hashable" call - // descriptions (eg., the ones for C functions that just match the name). - std::vector<std::pair<CallDescription, T>> LinearMap; - -public: - CallDescriptionMap( - std::initializer_list<std::pair<CallDescription, T>> &&List) - : LinearMap(List) {} - - ~CallDescriptionMap() = default; - - // These maps are usually stored once per checker, so let's make sure - // we don't do redundant copies. - CallDescriptionMap(const CallDescriptionMap &) = delete; - CallDescriptionMap &operator=(const CallDescription &) = delete; - - const T *lookup(const CallEvent &Call) const { - // Slow path: linear lookup. - // TODO: Implement some sort of fast path. - for (const std::pair<CallDescription, T> &I : LinearMap) - if (Call.isCalled(I.first)) - return &I.second; - - return nullptr; - } -}; - /// Manages the lifetime of CallEvent objects. /// /// CallEventManager provides a way to create arbitrary CallEvents "on the @@ -1346,89 +1302,98 @@ class CallEventManager { } template <typename T, typename Arg> - T *create(Arg A, ProgramStateRef St, const LocationContext *LCtx) { + T *create(Arg A, ProgramStateRef St, const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) { static_assert(sizeof(T) == sizeof(CallEventTemplateTy), "CallEvent subclasses are not all the same size"); - return new (allocate()) T(A, St, LCtx); + return new (allocate()) T(A, St, LCtx, ElemRef); } template <typename T, typename Arg1, typename Arg2> - T *create(Arg1 A1, Arg2 A2, ProgramStateRef St, const LocationContext *LCtx) { + T *create(Arg1 A1, Arg2 A2, ProgramStateRef St, const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) { static_assert(sizeof(T) == sizeof(CallEventTemplateTy), "CallEvent subclasses are not all the same size"); - return new (allocate()) T(A1, A2, St, LCtx); + return new (allocate()) T(A1, A2, St, LCtx, ElemRef); } template <typename T, typename Arg1, typename Arg2, typename Arg3> T *create(Arg1 A1, Arg2 A2, Arg3 A3, ProgramStateRef St, - const LocationContext *LCtx) { + const LocationContext *LCtx, CFGBlock::ConstCFGElementRef ElemRef) { static_assert(sizeof(T) == sizeof(CallEventTemplateTy), "CallEvent subclasses are not all the same size"); - return new (allocate()) T(A1, A2, A3, St, LCtx); + return new (allocate()) T(A1, A2, A3, St, LCtx, ElemRef); } template <typename T, typename Arg1, typename Arg2, typename Arg3, typename Arg4> T *create(Arg1 A1, Arg2 A2, Arg3 A3, Arg4 A4, ProgramStateRef St, - const LocationContext *LCtx) { + const LocationContext *LCtx, CFGBlock::ConstCFGElementRef ElemRef) { static_assert(sizeof(T) == sizeof(CallEventTemplateTy), "CallEvent subclasses are not all the same size"); - return new (allocate()) T(A1, A2, A3, A4, St, LCtx); + return new (allocate()) T(A1, A2, A3, A4, St, LCtx, ElemRef); } public: CallEventManager(llvm::BumpPtrAllocator &alloc) : Alloc(alloc) {} /// Gets an outside caller given a callee context. - CallEventRef<> - getCaller(const StackFrameContext *CalleeCtx, ProgramStateRef State); + CallEventRef<> getCaller(const StackFrameContext *CalleeCtx, + ProgramStateRef State); /// Gets a call event for a function call, Objective-C method call, - /// or a 'new' call. - CallEventRef<> - getCall(const Stmt *S, ProgramStateRef State, - const LocationContext *LC); + /// a 'new', or a 'delete' call. + CallEventRef<> getCall(const Stmt *S, ProgramStateRef State, + const LocationContext *LC, + CFGBlock::ConstCFGElementRef ElemRef); - CallEventRef<> - getSimpleCall(const CallExpr *E, ProgramStateRef State, - const LocationContext *LCtx); + CallEventRef<> getSimpleCall(const CallExpr *E, ProgramStateRef State, + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef); CallEventRef<ObjCMethodCall> getObjCMethodCall(const ObjCMessageExpr *E, ProgramStateRef State, - const LocationContext *LCtx) { - return create<ObjCMethodCall>(E, State, LCtx); + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) { + return create<ObjCMethodCall>(E, State, LCtx, ElemRef); } CallEventRef<CXXConstructorCall> getCXXConstructorCall(const CXXConstructExpr *E, const MemRegion *Target, - ProgramStateRef State, const LocationContext *LCtx) { - return create<CXXConstructorCall>(E, Target, State, LCtx); + ProgramStateRef State, const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) { + return create<CXXConstructorCall>(E, Target, State, LCtx, ElemRef); } CallEventRef<CXXInheritedConstructorCall> getCXXInheritedConstructorCall(const CXXInheritedCtorInitExpr *E, const MemRegion *Target, ProgramStateRef State, - const LocationContext *LCtx) { - return create<CXXInheritedConstructorCall>(E, Target, State, LCtx); + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) { + return create<CXXInheritedConstructorCall>(E, Target, State, LCtx, ElemRef); } CallEventRef<CXXDestructorCall> getCXXDestructorCall(const CXXDestructorDecl *DD, const Stmt *Trigger, const MemRegion *Target, bool IsBase, - ProgramStateRef State, const LocationContext *LCtx) { - return create<CXXDestructorCall>(DD, Trigger, Target, IsBase, State, LCtx); + ProgramStateRef State, const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) { + return create<CXXDestructorCall>(DD, Trigger, Target, IsBase, State, LCtx, + ElemRef); } CallEventRef<CXXAllocatorCall> getCXXAllocatorCall(const CXXNewExpr *E, ProgramStateRef State, - const LocationContext *LCtx) { - return create<CXXAllocatorCall>(E, State, LCtx); + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) { + return create<CXXAllocatorCall>(E, State, LCtx, ElemRef); } CallEventRef<CXXDeallocatorCall> getCXXDeallocatorCall(const CXXDeleteExpr *E, ProgramStateRef State, - const LocationContext *LCtx) { - return create<CXXDeallocatorCall>(E, State, LCtx); + const LocationContext *LCtx, + CFGBlock::ConstCFGElementRef ElemRef) { + return create<CXXDeallocatorCall>(E, State, LCtx, ElemRef); } }; @@ -1470,11 +1435,10 @@ inline void CallEvent::Release() const { namespace llvm { // Support isa<>, cast<>, and dyn_cast<> for CallEventRef. -template<class T> struct simplify_type< clang::ento::CallEventRef<T>> { +template <class T> struct simplify_type<clang::ento::CallEventRef<T>> { using SimpleType = const T *; - static SimpleType - getSimplifiedValue(clang::ento::CallEventRef<T> Val) { + static SimpleType getSimplifiedValue(clang::ento::CallEventRef<T> Val) { return Val.get(); } }; diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h index a383012dc351..9923c41e6ad2 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h @@ -16,6 +16,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" +#include <optional> namespace clang { namespace ento { @@ -84,6 +85,8 @@ public: return Eng.getContext(); } + const ASTContext &getASTContext() const { return Eng.getContext(); } + const LangOptions &getLangOpts() const { return Eng.getContext().getLangOpts(); } @@ -137,7 +140,7 @@ public: /// example, for finding variables that the given symbol was assigned to. static const MemRegion *getLocationRegionIfPostStore(const ExplodedNode *N) { ProgramPoint L = N->getLocation(); - if (Optional<PostStore> PSL = L.getAs<PostStore>()) + if (std::optional<PostStore> PSL = L.getAs<PostStore>()) return reinterpret_cast<const MemRegion*>(PSL->getLocationValue()); return nullptr; } @@ -210,6 +213,22 @@ public: } /// Generate a transition to a node that will be used to report + /// an error. This node will be a sink. That is, it will stop exploration of + /// the given path. + /// + /// @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. If null, + /// the default tag for the checker will be used. + ExplodedNode *generateErrorNode(ProgramStateRef State, + ExplodedNode *Pred, + const ProgramPointTag *Tag = nullptr) { + return generateSink(State, Pred, + (Tag ? Tag : Location.getTag())); + } + + /// Generate a transition to a node that will be used to report /// an error. This node will not be a sink. That is, exploration will /// continue along this path. /// @@ -254,6 +273,7 @@ public: /// @param IsPrunable Whether the note is prunable. It allows BugReporter /// to omit the note from the report if it would make the displayed /// bug path significantly shorter. + LLVM_ATTRIBUTE_RETURNS_NONNULL const NoteTag *getNoteTag(NoteTag::Callback &&Cb, bool IsPrunable = false) { return Eng.getDataTags().make<NoteTag>(std::move(Cb), IsPrunable); } @@ -296,8 +316,8 @@ public: /// bug path significantly shorter. const NoteTag *getNoteTag(StringRef Note, bool IsPrunable = false) { return getNoteTag( - [Note](BugReporterContext &, - PathSensitiveBugReport &) { return std::string(Note); }, + [Note = std::string(Note)](BugReporterContext &, + PathSensitiveBugReport &) { return Note; }, IsPrunable); } diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h index a81d67ab3063..65982457ad83 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h @@ -16,7 +16,7 @@ #include "clang/AST/OperationKinds.h" #include "clang/AST/Stmt.h" #include "clang/Basic/OperatorKinds.h" -#include "llvm/ADT/Optional.h" +#include <optional> #include <tuple> namespace clang { @@ -24,7 +24,6 @@ namespace clang { class Expr; class VarDecl; class QualType; -class AttributedType; class Preprocessor; namespace ento { @@ -68,8 +67,9 @@ Nullability getNullabilityAnnotation(QualType Type); /// Try to parse the value of a defined preprocessor macro. We can only parse /// simple expressions that consist of an optional minus sign token and then a -/// token for an integer. If we cannot parse the value then None is returned. -llvm::Optional<int> tryExpandAsInteger(StringRef Macro, const Preprocessor &PP); +/// token for an integer. If we cannot parse the value then std::nullopt is +/// returned. +std::optional<int> tryExpandAsInteger(StringRef Macro, const Preprocessor &PP); class OperatorKind { union { @@ -88,7 +88,7 @@ public: return Op.Bin; } - Optional<BinaryOperatorKind> GetBinaryOp() const { + std::optional<BinaryOperatorKind> GetBinaryOp() const { if (IsBinary) return Op.Bin; return {}; @@ -100,7 +100,7 @@ public: return Op.Un; } - Optional<UnaryOperatorKind> GetUnaryOp() const { + std::optional<UnaryOperatorKind> GetUnaryOp() const { if (!IsBinary) return Op.Un; return {}; diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h index 335536b6a310..4de04bc4d397 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h @@ -17,9 +17,9 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" -#include "llvm/ADT/Optional.h" #include "llvm/Support/SaveAndRestore.h" #include <memory> +#include <optional> #include <utility> namespace llvm { @@ -36,7 +36,7 @@ class ExprEngine; class SymbolReaper; class ConditionTruthVal { - Optional<bool> Val; + std::optional<bool> Val; public: /// Construct a ConditionTruthVal indicating the constraint is constrained @@ -53,25 +53,17 @@ public: } /// Return true if the constraint is perfectly constrained to 'true'. - bool isConstrainedTrue() const { - return Val.hasValue() && Val.getValue(); - } + bool isConstrainedTrue() const { return Val && *Val; } /// Return true if the constraint is perfectly constrained to 'false'. - bool isConstrainedFalse() const { - return Val.hasValue() && !Val.getValue(); - } + bool isConstrainedFalse() const { return Val && !*Val; } /// Return true if the constrained is perfectly constrained. - bool isConstrained() const { - return Val.hasValue(); - } + bool isConstrained() const { return Val.has_value(); } /// Return true if the constrained is underconstrained and we do not know /// if the constraint is true of value. - bool isUnderconstrained() const { - return !Val.hasValue(); - } + bool isUnderconstrained() const { return !Val.has_value(); } }; class ConstraintManager { @@ -82,77 +74,58 @@ public: virtual bool haveEqualConstraints(ProgramStateRef S1, ProgramStateRef S2) const = 0; - virtual ProgramStateRef assume(ProgramStateRef state, - DefinedSVal Cond, - bool Assumption) = 0; + ProgramStateRef assume(ProgramStateRef state, DefinedSVal Cond, + bool Assumption); using ProgramStatePair = std::pair<ProgramStateRef, ProgramStateRef>; /// Returns a pair of states (StTrue, StFalse) where the given condition is /// assumed to be true or false, respectively. - ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond) { - ProgramStateRef StTrue = assume(State, Cond, true); - - // If StTrue is infeasible, asserting the falseness of Cond is unnecessary - // because the existing constraints already establish this. - if (!StTrue) { -#ifdef EXPENSIVE_CHECKS - assert(assume(State, Cond, false) && "System is over constrained."); -#endif - return ProgramStatePair((ProgramStateRef)nullptr, State); - } - - ProgramStateRef StFalse = assume(State, Cond, false); - if (!StFalse) { - // We are careful to return the original state, /not/ StTrue, - // because we want to avoid having callers generate a new node - // in the ExplodedGraph. - return ProgramStatePair(State, (ProgramStateRef)nullptr); - } - - return ProgramStatePair(StTrue, StFalse); - } - - virtual ProgramStateRef assumeInclusiveRange(ProgramStateRef State, - NonLoc Value, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool InBound) = 0; - - virtual ProgramStatePair assumeInclusiveRangeDual(ProgramStateRef State, - NonLoc Value, - const llvm::APSInt &From, - const llvm::APSInt &To) { - ProgramStateRef StInRange = - assumeInclusiveRange(State, Value, From, To, true); - - // If StTrue is infeasible, asserting the falseness of Cond is unnecessary - // because the existing constraints already establish this. - if (!StInRange) - return ProgramStatePair((ProgramStateRef)nullptr, State); - - ProgramStateRef StOutOfRange = - assumeInclusiveRange(State, Value, From, To, false); - if (!StOutOfRange) { - // We are careful to return the original state, /not/ StTrue, - // because we want to avoid having callers generate a new node - // in the ExplodedGraph. - return ProgramStatePair(State, (ProgramStateRef)nullptr); - } - - return ProgramStatePair(StInRange, StOutOfRange); - } + /// (Note that these two states might be equal if the parent state turns out + /// to be infeasible. This may happen if the underlying constraint solver is + /// not perfectly precise and this may happen very rarely.) + ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond); + + ProgramStateRef assumeInclusiveRange(ProgramStateRef State, NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To, bool InBound); + + /// Returns a pair of states (StInRange, StOutOfRange) where the given value + /// is assumed to be in the range or out of the range, respectively. + /// (Note that these two states might be equal if the parent state turns out + /// to be infeasible. This may happen if the underlying constraint solver is + /// not perfectly precise and this may happen very rarely.) + ProgramStatePair assumeInclusiveRangeDual(ProgramStateRef State, NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To); /// If a symbol is perfectly constrained to a constant, attempt /// to return the concrete value. /// /// Note that a ConstraintManager is not obligated to return a concretized /// value for a symbol, even if it is perfectly constrained. + /// It might return null. virtual const llvm::APSInt* getSymVal(ProgramStateRef state, SymbolRef sym) const { return nullptr; } + /// Attempt to return the minimal possible value for a given symbol. Note + /// that a ConstraintManager is not obligated to return a lower bound, it may + /// also return nullptr. + virtual const llvm::APSInt *getSymMinVal(ProgramStateRef state, + SymbolRef sym) const { + return nullptr; + } + + /// Attempt to return the minimal possible value for a given symbol. Note + /// that a ConstraintManager is not obligated to return a lower bound, it may + /// also return nullptr. + virtual const llvm::APSInt *getSymMaxVal(ProgramStateRef state, + SymbolRef sym) const { + return nullptr; + } + /// Scan all symbols referenced by the constraints. If the symbol is not /// alive, remove it. virtual ProgramStateRef removeDeadBindings(ProgramStateRef state, @@ -162,22 +135,38 @@ public: const char *NL, unsigned int Space, bool IsDot) const = 0; + virtual void printValue(raw_ostream &Out, ProgramStateRef State, + SymbolRef Sym) {} + /// Convenience method to query the state to see if a symbol is null or /// not null, or if neither assumption can be made. ConditionTruthVal isNull(ProgramStateRef State, SymbolRef Sym) { - SaveAndRestore<bool> DisableNotify(NotifyAssumeClients, false); - return checkNull(State, Sym); } protected: - /// A flag to indicate that clients should be notified of assumptions. - /// By default this is the case, but sometimes this needs to be restricted - /// to avoid infinite recursions within the ConstraintManager. - /// - /// Note that this flag allows the ConstraintManager to be re-entrant, - /// but not thread-safe. - bool NotifyAssumeClients = true; + /// A helper class to simulate the call stack of nested assume calls. + class AssumeStackTy { + public: + void push(const ProgramState *S) { Aux.push_back(S); } + void pop() { Aux.pop_back(); } + bool contains(const ProgramState *S) const { + return llvm::is_contained(Aux, S); + } + + private: + llvm::SmallVector<const ProgramState *, 4> Aux; + }; + AssumeStackTy AssumeStack; + + virtual ProgramStateRef assumeInternal(ProgramStateRef state, + DefinedSVal Cond, bool Assumption) = 0; + + virtual ProgramStateRef assumeInclusiveRangeInternal(ProgramStateRef State, + NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InBound) = 0; /// canReasonAbout - Not all ConstraintManagers can accurately reason about /// all SVal values. This method returns true if the ConstraintManager can @@ -189,6 +178,10 @@ protected: /// Returns whether or not a symbol is known to be null ("true"), known to be /// non-null ("false"), or may be either ("underconstrained"). virtual ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym); + + template <typename AssumeFunction> + ProgramStatePair assumeDualImpl(ProgramStateRef &State, + AssumeFunction &Assume); }; std::unique_ptr<ConstraintManager> diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 9898b9b42f4b..8dbe767cef9d 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -25,6 +25,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Casting.h" #include <cassert> #include <memory> @@ -78,6 +79,7 @@ private: /// worklist algorithm. It is up to the implementation of WList to decide /// the order that nodes are processed. std::unique_ptr<WorkList> WList; + std::unique_ptr<WorkList> CTUWList; /// BCounterFactory - A factory object for created BlockCounter objects. /// These are used to record for key nodes in the ExplodedGraph the @@ -101,6 +103,8 @@ private: /// tags. DataTag::Factory DataTags; + void setBlockCounter(BlockCounter C); + void generateNode(const ProgramPoint &Loc, ProgramStateRef State, ExplodedNode *Pred); @@ -170,22 +174,13 @@ public: } WorkList *getWorkList() const { return WList.get(); } + WorkList *getCTUWorkList() const { return CTUWList.get(); } - BlocksExhausted::const_iterator blocks_exhausted_begin() const { - return blocksExhausted.begin(); + auto exhausted_blocks() const { + return llvm::iterator_range(blocksExhausted); } - BlocksExhausted::const_iterator blocks_exhausted_end() const { - return blocksExhausted.end(); - } - - BlocksAborted::const_iterator blocks_aborted_begin() const { - return blocksAborted.begin(); - } - - BlocksAborted::const_iterator blocks_aborted_end() const { - return blocksAborted.end(); - } + auto aborted_blocks() const { return llvm::iterator_range(blocksAborted); } /// Enqueue the given set of nodes onto the work list. void enqueue(ExplodedNodeSet &Set); @@ -210,8 +205,14 @@ struct NodeBuilderContext { const CFGBlock *Block; const LocationContext *LC; + NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, + const LocationContext *L) + : Eng(E), Block(B), LC(L) { + assert(B); + } + NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N) - : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); } + : NodeBuilderContext(E, B, N->getLocationContext()) {} /// Return the CFGBlock associated with this builder. const CFGBlock *getBlock() const { return Block; } @@ -290,7 +291,9 @@ public: ExplodedNode *generateNode(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred) { - return generateNodeImpl(PP, State, Pred, false); + return generateNodeImpl( + PP, State, Pred, + /*MarkAsSink=*/State->isPosteriorlyOverconstrained()); } /// Generates a sink in the ExplodedGraph. @@ -495,6 +498,11 @@ public: iterator(CFGBlock::const_succ_iterator i) : I(i) {} public: + // This isn't really a conventional iterator. + // We just implement the deref as a no-op for now to make range-based for + // loops work. + const iterator &operator*() const { return *this; } + iterator &operator++() { ++I; return *this; } bool operator!=(const iterator &X) const { return I != X.I; } diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h index cfd7aa9664b6..50d5d254415a 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h @@ -53,6 +53,11 @@ ProgramStateRef setDynamicExtent(ProgramStateRef State, const MemRegion *MR, /// (bufptr) // extent is unknown SVal getDynamicExtentWithOffset(ProgramStateRef State, SVal BufV); +/// \returns The stored element count of the region represented by a symbolic +/// value \p BufV. +DefinedOrUnknownSVal getDynamicElementCountWithOffset(ProgramStateRef State, + SVal BufV, QualType Ty); + } // namespace ento } // namespace clang diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h index ffe1fe846be1..52d1526b1acf 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h @@ -22,8 +22,6 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" -#include "llvm/ADT/ImmutableMap.h" -#include "llvm/ADT/Optional.h" namespace clang { namespace ento { @@ -32,6 +30,7 @@ namespace ento { DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR); /// Get raw dynamic type information for the region \p MR. +/// It might return null. const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR); diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h index 6d2b495dc0f5..3ff453a8de4f 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h @@ -18,7 +18,7 @@ namespace ento { /// of a region in a given state along the analysis path. class DynamicTypeInfo { public: - DynamicTypeInfo() : DynTy(QualType()) {} + DynamicTypeInfo() {} DynamicTypeInfo(QualType Ty, bool CanBeSub = true) : DynTy(Ty), CanBeASubClass(CanBeSub) {} diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index e87772c04b9b..2fb05ac46e8f 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -30,14 +30,15 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Compiler.h" #include <cassert> #include <cstdint> #include <memory> +#include <optional> #include <utility> #include <vector> @@ -161,15 +162,13 @@ public: return getLocationContext()->getParentMap(); } - template <typename T> - T &getAnalysis() const { + template <typename T> T &getAnalysis() const { return *getLocationContext()->getAnalysis<T>(); } const ProgramStateRef &getState() const { return State; } - template <typename T> - Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { + template <typename T> std::optional<T> getLocationAs() const & { return Location.getAs<T>(); } @@ -397,13 +396,9 @@ public: using node_iterator = AllNodesTy::iterator; using const_node_iterator = AllNodesTy::const_iterator; - node_iterator nodes_begin() { return Nodes.begin(); } + llvm::iterator_range<node_iterator> nodes() { return Nodes; } - node_iterator nodes_end() { return Nodes.end(); } - - const_node_iterator nodes_begin() const { return Nodes.begin(); } - - const_node_iterator nodes_end() const { return Nodes.end(); } + llvm::iterator_range<const_node_iterator> nodes() const { return Nodes; } roots_iterator roots_begin() { return Roots.begin(); } diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index cef7dda172f3..ed5c4adb5e3d 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -36,6 +36,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" #include "llvm/ADT/ArrayRef.h" #include <cassert> +#include <optional> #include <utility> namespace clang { @@ -77,13 +78,9 @@ namespace ento { class AnalysisManager; class BasicValueFactory; -class BlockCounter; -class BranchNodeBuilder; class CallEvent; class CheckerManager; class ConstraintManager; -class CXXTempObjectRegion; -class EndOfFunctionNodeBuilder; class ExplodedNodeSet; class ExplodedNode; class IndirectGotoNodeBuilder; @@ -139,6 +136,7 @@ public: private: cross_tu::CrossTranslationUnitContext &CTU; + bool IsCTUEnabled; AnalysisManager &AMgr; @@ -231,10 +229,15 @@ public: const Stmt *getStmt() const; - void GenerateAutoTransition(ExplodedNode *N); - void enqueueEndOfPath(ExplodedNodeSet &S); - void GenerateCallExitNode(ExplodedNode *N); + const LocationContext *getRootLocationContext() const { + assert(G.roots_begin() != G.roots_end()); + return (*G.roots_begin())->getLocation().getLocationContext(); + } + CFGBlock::ConstCFGElementRef getCFGElementRef() const { + const CFGBlock *blockPtr = currBldrCtx ? currBldrCtx->getBlock() : nullptr; + return {blockPtr, currStmtIdx}; + } /// Dump graph to the specified filename. /// If filename is empty, generate a temporary one. @@ -358,13 +361,13 @@ public: void processSwitch(SwitchNodeBuilder& builder); /// Called by CoreEngine. Used to notify checkers that processing a - /// function has begun. Called for both inlined and and top-level functions. + /// function has begun. Called for both inlined and top-level functions. void processBeginOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, ExplodedNodeSet &Dst, const BlockEdge &L); /// Called by CoreEngine. Used to notify checkers that processing a - /// function has ended. Called for both inlined and and top-level functions. + /// function has ended. Called for both inlined and top-level functions. void processEndOfFunction(NodeBuilderContext& BC, ExplodedNode *Pred, const ReturnStmt *RS = nullptr); @@ -442,6 +445,10 @@ public: /// other functions that handle specific kinds of statements. void Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst); + /// VisitArrayInitLoopExpr - Transfer function for array init loop. + void VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex, ExplodedNode *Pred, + ExplodedNodeSet &Dst); + /// VisitArraySubscriptExpr - Transfer function for array accesses. void VisitArraySubscriptExpr(const ArraySubscriptExpr *Ex, ExplodedNode *Pred, @@ -589,51 +596,40 @@ public: static std::pair<const ProgramPointTag *, const ProgramPointTag *> geteagerlyAssumeBinOpBifurcationTags(); - SVal evalMinus(SVal X) { - return X.isValid() ? svalBuilder.evalMinus(X.castAs<NonLoc>()) : X; - } - - SVal evalComplement(SVal X) { - return X.isValid() ? svalBuilder.evalComplement(X.castAs<NonLoc>()) : X; - } - ProgramStateRef handleLValueBitCast(ProgramStateRef state, const Expr *Ex, const LocationContext *LCtx, QualType T, QualType ExTy, const CastExpr *CastE, StmtNodeBuilder &Bldr, ExplodedNode *Pred); - ProgramStateRef handleLVectorSplat(ProgramStateRef state, - const LocationContext *LCtx, - const CastExpr *CastE, - StmtNodeBuilder &Bldr, - ExplodedNode *Pred); - - void handleUOExtension(ExplodedNodeSet::iterator I, - const UnaryOperator* U, + void handleUOExtension(ExplodedNode *N, const UnaryOperator *U, StmtNodeBuilder &Bldr); public: - SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, - NonLoc L, NonLoc R, QualType T) { - return svalBuilder.evalBinOpNN(state, op, L, R, T); - } - - SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, - NonLoc L, SVal R, QualType T) { - return R.isValid() ? svalBuilder.evalBinOpNN(state, op, L, - R.castAs<NonLoc>(), T) : R; - } - SVal evalBinOp(ProgramStateRef ST, BinaryOperator::Opcode Op, SVal LHS, SVal RHS, QualType T) { return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T); } + /// Retreives which element is being constructed in a non-POD type array. + static std::optional<unsigned> + getIndexOfElementToConstruct(ProgramStateRef State, const CXXConstructExpr *E, + const LocationContext *LCtx); + + /// Retreives which element is being destructed in a non-POD type array. + static std::optional<unsigned> + getPendingArrayDestruction(ProgramStateRef State, + const LocationContext *LCtx); + + /// Retreives the size of the array in the pending ArrayInitLoopExpr. + static std::optional<unsigned> + getPendingInitLoop(ProgramStateRef State, const CXXConstructExpr *E, + const LocationContext *LCtx); + /// By looking at a certain item that may be potentially part of an object's /// ConstructionContext, retrieve such object's location. A particular /// statement can be transparently passed as \p Item in most cases. - static Optional<SVal> + static std::optional<SVal> getObjectUnderConstruction(ProgramStateRef State, const ConstructionContextItem &Item, const LocationContext *LC); @@ -721,10 +717,20 @@ public: /// fully implemented it sometimes indicates that it failed via its /// out-parameter CallOpts; in such cases a fake temporary region is /// returned, which is better than nothing but does not represent - /// the actual behavior of the program. - SVal computeObjectUnderConstruction( - const Expr *E, ProgramStateRef State, const LocationContext *LCtx, - const ConstructionContext *CC, EvalCallOptions &CallOpts); + /// the actual behavior of the program. The Idx parameter is used if we + /// construct an array of objects. In that case it points to the index + /// of the continuous memory region. + /// E.g.: + /// For `int arr[4]` this index can be 0,1,2,3. + /// For `int arr2[3][3]` this index can be 0,1,...,7,8. + /// A multi-dimensional array is also a continuous memory location in a + /// row major order, so for arr[0][0] Idx is 0 and for arr[2][2] Idx is 8. + SVal computeObjectUnderConstruction(const Expr *E, ProgramStateRef State, + const NodeBuilderContext *BldrCtx, + const LocationContext *LCtx, + const ConstructionContext *CC, + EvalCallOptions &CallOpts, + unsigned Idx = 0); /// Update the program state with all the path-sensitive information /// that's necessary to perform construction of an object with a given @@ -738,11 +744,15 @@ public: /// A convenient wrapper around computeObjectUnderConstruction /// and updateObjectsUnderConstruction. std::pair<ProgramStateRef, SVal> handleConstructionContext( - const Expr *E, ProgramStateRef State, const LocationContext *LCtx, - const ConstructionContext *CC, EvalCallOptions &CallOpts) { - SVal V = computeObjectUnderConstruction(E, State, LCtx, CC, CallOpts); - return std::make_pair( - updateObjectsUnderConstruction(V, E, State, LCtx, CC, CallOpts), V); + const Expr *E, ProgramStateRef State, const NodeBuilderContext *BldrCtx, + const LocationContext *LCtx, const ConstructionContext *CC, + EvalCallOptions &CallOpts, unsigned Idx = 0) { + + SVal V = computeObjectUnderConstruction(E, State, BldrCtx, LCtx, CC, + CallOpts, Idx); + State = updateObjectsUnderConstruction(V, E, State, LCtx, CC, CallOpts); + + return std::make_pair(State, V); } private: @@ -751,15 +761,6 @@ private: void finishArgumentConstruction(ExplodedNodeSet &Dst, ExplodedNode *Pred, const CallEvent &Call); - 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); - void evalLocation(ExplodedNodeSet &Dst, const Stmt *NodeEx, /* This will eventually be a CFGStmt */ const Stmt *BoundEx, @@ -809,8 +810,46 @@ private: const ExplodedNode *Pred, const EvalCallOptions &CallOpts = {}); - bool inlineCall(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr, - ExplodedNode *Pred, ProgramStateRef State); + /// Checks whether our policies allow us to inline a non-POD type array + /// construction. + bool shouldInlineArrayConstruction(const ProgramStateRef State, + const CXXConstructExpr *CE, + const LocationContext *LCtx); + + /// Checks whether our policies allow us to inline a non-POD type array + /// destruction. + /// \param Size The size of the array. + bool shouldInlineArrayDestruction(uint64_t Size); + + /// Prepares the program state for array destruction. If no error happens + /// the function binds a 'PendingArrayDestruction' entry to the state, which + /// it returns along with the index. If any error happens (we fail to read + /// the size, the index would be -1, etc.) the function will return the + /// original state along with an index of 0. The actual element count of the + /// array can be accessed by the optional 'ElementCountVal' parameter. \param + /// State The program state. \param Region The memory region where the array + /// is stored. \param ElementTy The type an element in the array. \param LCty + /// The location context. \param ElementCountVal A pointer to an optional + /// SVal. If specified, the size of the array will be returned in it. It can + /// be Unknown. + std::pair<ProgramStateRef, uint64_t> prepareStateForArrayDestruction( + const ProgramStateRef State, const MemRegion *Region, + const QualType &ElementTy, const LocationContext *LCtx, + SVal *ElementCountVal = nullptr); + + /// Checks whether we construct an array of non-POD type, and decides if the + /// constructor should be inkoved once again. + bool shouldRepeatCtorCall(ProgramStateRef State, const CXXConstructExpr *E, + const LocationContext *LCtx); + + void inlineCall(WorkList *WList, const CallEvent &Call, const Decl *D, + NodeBuilder &Bldr, ExplodedNode *Pred, ProgramStateRef State); + + void ctuBifurcate(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr, + ExplodedNode *Pred, ProgramStateRef State); + + /// Returns true if the CTU analysis is running its second phase. + bool isSecondPhaseCTU() { return IsCTUEnabled && !Engine.getCTUWorkList(); } /// Conservatively evaluate call by invalidating regions and binding /// a conjured return value. @@ -845,7 +884,7 @@ private: const Expr *InitWithAdjustments, const Expr *Result = nullptr, const SubRegion **OutRegionWithAdjustments = nullptr); - /// Returns a region representing the first element of a (possibly + /// Returns a region representing the `Idx`th element of a (possibly /// multi-dimensional) array, for the purposes of element construction or /// destruction. /// @@ -853,15 +892,8 @@ private: /// /// If the type is not an array type at all, the original value is returned. /// Otherwise the "IsArray" flag is set. - static SVal makeZeroElementRegion(ProgramStateRef State, SVal LValue, - QualType &Ty, bool &IsArray); - - /// For a DeclStmt or CXXInitCtorInitializer, walk backward in the current CFG - /// block to find the constructor expression that directly constructed into - /// the storage for this statement. Returns null if the constructor for this - /// statement created a temporary object region rather than directly - /// constructing into an existing region. - const CXXConstructExpr *findDirectConstructorForCurrentCFGElement(); + static SVal makeElementRegion(ProgramStateRef State, SVal LValue, + QualType &Ty, bool &IsArray, unsigned Idx = 0); /// Common code that handles either a CXXConstructExpr or a /// CXXInheritedCtorInitExpr. @@ -872,19 +904,56 @@ public: /// Note whether this loop has any more iteratios to model. These methods are /// essentially an interface for a GDM trait. Further reading in /// ExprEngine::VisitObjCForCollectionStmt(). - LLVM_NODISCARD static ProgramStateRef + [[nodiscard]] static ProgramStateRef setWhetherHasMoreIteration(ProgramStateRef State, const ObjCForCollectionStmt *O, const LocationContext *LC, bool HasMoreIteraton); - LLVM_NODISCARD static ProgramStateRef + [[nodiscard]] static ProgramStateRef removeIterationState(ProgramStateRef State, const ObjCForCollectionStmt *O, const LocationContext *LC); - LLVM_NODISCARD static bool hasMoreIteration(ProgramStateRef State, - const ObjCForCollectionStmt *O, - const LocationContext *LC); + [[nodiscard]] static bool hasMoreIteration(ProgramStateRef State, + const ObjCForCollectionStmt *O, + const LocationContext *LC); + private: + /// Assuming we construct an array of non-POD types, this method allows us + /// to store which element is to be constructed next. + static ProgramStateRef + setIndexOfElementToConstruct(ProgramStateRef State, const CXXConstructExpr *E, + const LocationContext *LCtx, unsigned Idx); + + static ProgramStateRef + removeIndexOfElementToConstruct(ProgramStateRef State, + const CXXConstructExpr *E, + const LocationContext *LCtx); + + /// Assuming we destruct an array of non-POD types, this method allows us + /// to store which element is to be destructed next. + static ProgramStateRef setPendingArrayDestruction(ProgramStateRef State, + const LocationContext *LCtx, + unsigned Idx); + + static ProgramStateRef + removePendingArrayDestruction(ProgramStateRef State, + const LocationContext *LCtx); + + /// Sets the size of the array in a pending ArrayInitLoopExpr. + static ProgramStateRef setPendingInitLoop(ProgramStateRef State, + const CXXConstructExpr *E, + const LocationContext *LCtx, + unsigned Idx); + + static ProgramStateRef removePendingInitLoop(ProgramStateRef State, + const CXXConstructExpr *E, + const LocationContext *LCtx); + + static ProgramStateRef + removeStateTraitsUsedForArrayEvaluation(ProgramStateRef State, + const CXXConstructExpr *E, + const LocationContext *LCtx); + /// Store the location of a C++ object corresponding to a statement /// until the statement is actually encountered. For example, if a DeclStmt /// has CXXConstructExpr as its initializer, the object would be considered diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h index 53b4bf605871..3ee0d229cfc2 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h @@ -17,11 +17,10 @@ #include "clang/Basic/LLVM.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/None.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallBitVector.h" #include <cassert> #include <deque> +#include <optional> #include <utility> namespace clang { @@ -86,11 +85,11 @@ public: markShouldNotInline(D); } - Optional<bool> mayInline(const Decl *D) { + std::optional<bool> mayInline(const Decl *D) { MapTy::const_iterator I = Map.find(D); if (I != Map.end() && I->second.InlineChecked) return I->second.MayInline; - return None; + return std::nullopt; } void markVisitedBasicBlock(unsigned ID, const Decl* D, unsigned TotalIDs) { diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h index 53b221cb53c9..eb2b0b343428 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h @@ -28,7 +28,6 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" namespace clang { namespace ento { -class AnalysisManager; /// Returns if the given State indicates that is inside a completely unrolled /// loop. diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h index 9f85347db5df..151d3e57c1cb 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h @@ -30,13 +30,14 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Casting.h" #include <cassert> #include <cstdint> #include <limits> +#include <optional> #include <string> #include <utility> @@ -74,6 +75,7 @@ public: RegionOffset() = default; RegionOffset(const MemRegion *r, int64_t off) : R(r), Offset(off) {} + /// It might return null. const MemRegion *getRegion() const { return R; } bool hasSymbolicOffset() const { return Offset == Symbolic; } @@ -101,7 +103,7 @@ public: private: const Kind kind; - mutable Optional<RegionOffset> cachedOffset; + mutable std::optional<RegionOffset> cachedOffset; protected: MemRegion(Kind k) : kind(k) {} @@ -114,26 +116,27 @@ public: virtual MemRegionManager &getMemRegionManager() const = 0; - const MemSpaceRegion *getMemorySpace() const; + LLVM_ATTRIBUTE_RETURNS_NONNULL const MemSpaceRegion *getMemorySpace() const; - const MemRegion *getBaseRegion() const; + LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion *getBaseRegion() const; /// Recursively retrieve the region of the most derived class instance of /// regions of C++ base class instances. + LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion *getMostDerivedObjectRegion() const; /// Check if the region is a subregion of the given region. /// Each region is a subregion of itself. virtual bool isSubRegionOf(const MemRegion *R) const; + LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion *StripCasts(bool StripBaseAndDerivedCasts = true) const; /// If this is a symbolic region, returns the region. Otherwise, /// goes up the base chain looking for the first symbolic base region. + /// It might return null. const SymbolicRegion *getSymbolicBase() const; - bool hasGlobalsOrParametersStorage() const; - bool hasStackStorage() const; bool hasStackNonParametersStorage() const; @@ -169,7 +172,8 @@ public: Kind getKind() const { return kind; } template<typename RegionTy> const RegionTy* getAs() const; - template<typename RegionTy> const RegionTy* castAs() const; + template <typename RegionTy> + LLVM_ATTRIBUTE_RETURNS_NONNULL const RegionTy *castAs() const; virtual bool isBoundable() const { return false; } @@ -268,6 +272,7 @@ public: void dumpToStream(raw_ostream &os) const override; + LLVM_ATTRIBUTE_RETURNS_NONNULL const CodeTextRegion *getCodeRegion() const { return CR; } static bool classof(const MemRegion *R) { @@ -391,6 +396,7 @@ protected: } public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const StackFrameContext *getStackFrame() const { return SFC; } void Profile(llvm::FoldingSetNodeID &ID) const override; @@ -444,6 +450,7 @@ protected: } public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion* getSuperRegion() const { return superRegion; } @@ -481,6 +488,7 @@ class AllocaRegion : public SubRegion { unsigned Cnt, const MemRegion *superRegion); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const Expr *getExpr() const { return Ex; } bool isBoundable() const override { return true; } @@ -639,10 +647,12 @@ public: return locTy; } + LLVM_ATTRIBUTE_RETURNS_NONNULL const BlockDecl *getDecl() const { return BD; } + LLVM_ATTRIBUTE_RETURNS_NONNULL AnalysisDeclContext *getAnalysisDeclContext() const { return AC; } void dumpToStream(raw_ostream &os) const override; @@ -674,6 +684,7 @@ class BlockDataRegion : public TypedRegion { : TypedRegion(sreg, BlockDataRegionKind), BC(bc), LC(lc), BlockCount(count) { assert(bc); + assert(bc->getDecl()); assert(lc); assert(isa<GlobalImmutableSpaceRegion>(sreg) || isa<StackLocalsSpaceRegion>(sreg) || @@ -685,8 +696,10 @@ class BlockDataRegion : public TypedRegion { const MemRegion *); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const BlockCodeRegion *getCodeRegion() const { return BC; } + LLVM_ATTRIBUTE_RETURNS_NONNULL const BlockDecl *getDecl() const { return BC->getDecl(); } QualType getLocationType() const override { return BC->getLocationType(); } @@ -700,10 +713,12 @@ public: const MemRegion * const *originalR) : R(r), OriginalR(originalR) {} + LLVM_ATTRIBUTE_RETURNS_NONNULL const VarRegion *getCapturedRegion() const { return cast<VarRegion>(*R); } + LLVM_ATTRIBUTE_RETURNS_NONNULL const VarRegion *getOriginalRegion() const { return cast<VarRegion>(*OriginalR); } @@ -723,14 +738,20 @@ public: ++OriginalR; return *this; } + + // This isn't really a conventional iterator. + // We just implement the deref as a no-op for now to make range-based for + // loops work. + const referenced_vars_iterator &operator*() const { return *this; } }; /// Return the original region for a captured region, if - /// one exists. + /// one exists. It might return null. const VarRegion *getOriginalRegion(const VarRegion *VR) const; referenced_vars_iterator referenced_vars_begin() const; referenced_vars_iterator referenced_vars_end() const; + llvm::iterator_range<referenced_vars_iterator> referenced_vars() const; void dumpToStream(raw_ostream &os) const override; @@ -764,12 +785,26 @@ class SymbolicRegion : public SubRegion { assert(s->getType()->isAnyPointerType() || s->getType()->isReferenceType() || s->getType()->isBlockPointerType()); - assert(isa<UnknownSpaceRegion>(sreg) || isa<HeapSpaceRegion>(sreg)); + assert(isa<UnknownSpaceRegion>(sreg) || isa<HeapSpaceRegion>(sreg) || + isa<GlobalSystemSpaceRegion>(sreg)); } public: + /// It might return null. SymbolRef getSymbol() const { return sym; } + /// Gets the type of the wrapped symbol. + /// This type might not be accurate at all times - it's just our best guess. + /// Consider these cases: + /// void foo(void *data, char *str, base *obj) {...} + /// The type of the pointee of `data` is of course not `void`, yet that's our + /// best guess. `str` might point to any object and `obj` might point to some + /// derived instance. `TypedRegions` other hand are representing the cases + /// when we actually know their types. + QualType getPointeeStaticType() const { + return sym->getType()->getPointeeType(); + } + bool isBoundable() const override { return true; } void Profile(llvm::FoldingSetNodeID& ID) const override; @@ -801,6 +836,7 @@ class StringRegion : public TypedValueRegion { const MemRegion *superRegion); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const StringLiteral *getStringLiteral() const { return Str; } QualType getValueType() const override { return Str->getType(); } @@ -835,6 +871,7 @@ class ObjCStringRegion : public TypedValueRegion { const MemRegion *superRegion); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const ObjCStringLiteral *getObjCStringLiteral() const { return Str; } QualType getValueType() const override { return Str->getType(); } @@ -881,6 +918,7 @@ public: void dumpToStream(raw_ostream &os) const override; + LLVM_ATTRIBUTE_RETURNS_NONNULL const CompoundLiteralExpr *getLiteralExpr() const { return CL; } static bool classof(const MemRegion* R) { @@ -895,6 +933,7 @@ protected: } public: + // TODO what does this return? virtual const ValueDecl *getDecl() const = 0; static bool classof(const MemRegion* R) { @@ -918,8 +957,10 @@ protected: } public: + // TODO what does this return? const VarDecl *getDecl() const override = 0; + /// It might return null. const StackFrameContext *getStackFrame() const; QualType getValueType() const override { @@ -947,6 +988,7 @@ class NonParamVarRegion : public VarRegion { // which, unlike everything else on this list, are not memory spaces. assert(isa<GlobalsSpaceRegion>(sReg) || isa<StackSpaceRegion>(sReg) || isa<BlockDataRegion>(sReg) || isa<UnknownSpaceRegion>(sReg)); + assert(vd); } static void ProfileRegion(llvm::FoldingSetNodeID &ID, const VarDecl *VD, @@ -955,6 +997,7 @@ class NonParamVarRegion : public VarRegion { public: void Profile(llvm::FoldingSetNodeID &ID) const override; + LLVM_ATTRIBUTE_RETURNS_NONNULL const VarDecl *getDecl() const override { return VD; } QualType getValueType() const override { @@ -992,12 +1035,14 @@ class ParamVarRegion : public VarRegion { ParamVarRegion(const Expr *OE, unsigned Idx, const MemRegion *SReg) : VarRegion(SReg, ParamVarRegionKind), OriginExpr(OE), Index(Idx) { assert(!cast<StackSpaceRegion>(SReg)->getStackFrame()->inTopFrame()); + assert(OriginExpr); } static void ProfileRegion(llvm::FoldingSetNodeID &ID, const Expr *OE, unsigned Idx, const MemRegion *SReg); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const Expr *getOriginExpr() const { return OriginExpr; } unsigned getIndex() const { return Index; } @@ -1006,6 +1051,8 @@ public: void dumpToStream(raw_ostream &os) const override; QualType getValueType() const override; + + /// TODO: What does this return? const ParmVarDecl *getDecl() const override; bool canPrintPrettyAsExpr() const override; @@ -1057,7 +1104,9 @@ class FieldRegion : public DeclRegion { const FieldDecl *FD; FieldRegion(const FieldDecl *fd, const SubRegion *sReg) - : DeclRegion(sReg, FieldRegionKind), FD(fd) {} + : DeclRegion(sReg, FieldRegionKind), FD(fd) { + assert(FD); + } static void ProfileRegion(llvm::FoldingSetNodeID &ID, const FieldDecl *FD, const MemRegion* superRegion) { @@ -1067,6 +1116,7 @@ class FieldRegion : public DeclRegion { } public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const FieldDecl *getDecl() const override { return FD; } void Profile(llvm::FoldingSetNodeID &ID) const override; @@ -1099,6 +1149,7 @@ class ObjCIvarRegion : public DeclRegion { const MemRegion* superRegion); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const ObjCIvarDecl *getDecl() const override; void Profile(llvm::FoldingSetNodeID& ID) const override; @@ -1131,6 +1182,8 @@ class RegionRawOffset { public: // FIXME: Eventually support symbolic offsets. CharUnits getOffset() const { return Offset; } + + // It might return null. const MemRegion *getRegion() const { return Region; } void dumpToStream(raw_ostream &os) const; @@ -1147,7 +1200,7 @@ class ElementRegion : public TypedValueRegion { ElementRegion(QualType elementType, NonLoc Idx, const SubRegion *sReg) : TypedValueRegion(sReg, ElementRegionKind), ElementType(elementType), Index(Idx) { - assert((!Idx.getAs<nonloc::ConcreteInt>() || + assert((!isa<nonloc::ConcreteInt>(Idx) || Idx.castAs<nonloc::ConcreteInt>().getValue().isSigned()) && "The index must be signed"); assert(!elementType.isNull() && !elementType->isVoidType() && @@ -1185,16 +1238,19 @@ class CXXTempObjectRegion : public TypedValueRegion { CXXTempObjectRegion(Expr const *E, MemSpaceRegion const *sReg) : TypedValueRegion(sReg, CXXTempObjectRegionKind), Ex(E) { assert(E); - assert(isa<StackLocalsSpaceRegion>(sReg) || - isa<GlobalInternalSpaceRegion>(sReg)); + assert(isa<StackLocalsSpaceRegion>(sReg)); } static void ProfileRegion(llvm::FoldingSetNodeID &ID, Expr const *E, const MemRegion *sReg); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const Expr *getExpr() const { return Ex; } + LLVM_ATTRIBUTE_RETURNS_NONNULL + const StackFrameContext *getStackFrame() const; + QualType getValueType() const override { return Ex->getType(); } void dumpToStream(raw_ostream &os) const override; @@ -1206,6 +1262,45 @@ public: } }; +// C++ temporary object that have lifetime extended to lifetime of the +// variable. Usually they represent temporary bounds to reference variables. +class CXXLifetimeExtendedObjectRegion : public TypedValueRegion { + friend class MemRegionManager; + + Expr const *Ex; + ValueDecl const *ExD; + + CXXLifetimeExtendedObjectRegion(Expr const *E, ValueDecl const *D, + MemSpaceRegion const *sReg) + : TypedValueRegion(sReg, CXXLifetimeExtendedObjectRegionKind), Ex(E), + ExD(D) { + assert(E); + assert(D); + assert((isa<StackLocalsSpaceRegion, GlobalInternalSpaceRegion>(sReg))); + } + + static void ProfileRegion(llvm::FoldingSetNodeID &ID, Expr const *E, + ValueDecl const *D, const MemRegion *sReg); + +public: + LLVM_ATTRIBUTE_RETURNS_NONNULL + const Expr *getExpr() const { return Ex; } + LLVM_ATTRIBUTE_RETURNS_NONNULL + const ValueDecl *getExtendingDecl() const { return ExD; } + /// It might return null. + const StackFrameContext *getStackFrame() const; + + QualType getValueType() const override { return Ex->getType(); } + + void dumpToStream(raw_ostream &os) const override; + + void Profile(llvm::FoldingSetNodeID &ID) const override; + + static bool classof(const MemRegion *R) { + return R->getKind() == CXXLifetimeExtendedObjectRegionKind; + } +}; + // CXXBaseObjectRegion represents a base object within a C++ object. It is // identified by the base class declaration and the region of its parent object. class CXXBaseObjectRegion : public TypedValueRegion { @@ -1223,6 +1318,7 @@ class CXXBaseObjectRegion : public TypedValueRegion { bool IsVirtual, const MemRegion *SReg); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const CXXRecordDecl *getDecl() const { return Data.getPointer(); } bool isVirtual() const { return Data.getInt(); } @@ -1265,6 +1361,7 @@ class CXXDerivedObjectRegion : public TypedValueRegion { const MemRegion *SReg); public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const CXXRecordDecl *getDecl() const { return DerivedD; } QualType getValueType() const override; @@ -1290,8 +1387,8 @@ const RegionTy* MemRegion::getAs() const { return nullptr; } -template<typename RegionTy> -const RegionTy* MemRegion::castAs() const { +template <typename RegionTy> +LLVM_ATTRIBUTE_RETURNS_NONNULL const RegionTy *MemRegion::castAs() const { return cast<RegionTy>(this); } @@ -1325,6 +1422,7 @@ public: ~MemRegionManager(); ASTContext &getContext() { return Ctx; } + const ASTContext &getContext() const { return Ctx; } llvm::BumpPtrAllocator &getAllocator() { return A; } @@ -1375,7 +1473,9 @@ public: const LocationContext *LC); /// Retrieve or create a "symbolic" memory region. - const SymbolicRegion* getSymbolicRegion(SymbolRef Sym); + /// If no memory space is specified, `UnknownSpaceRegion` will be used. + const SymbolicRegion * + getSymbolicRegion(SymbolRef Sym, const MemSpaceRegion *MemSpace = nullptr); /// Return a unique symbolic region belonging to heap memory space. const SymbolicRegion *getSymbolicHeapRegion(SymbolRef sym); @@ -1433,6 +1533,19 @@ public: const CXXTempObjectRegion *getCXXTempObjectRegion(Expr const *Ex, LocationContext const *LC); + /// Create a CXXLifetimeExtendedObjectRegion for temporaries which are + /// lifetime-extended by local references. + const CXXLifetimeExtendedObjectRegion * + getCXXLifetimeExtendedObjectRegion(Expr const *Ex, ValueDecl const *VD, + LocationContext const *LC); + + /// Create a CXXLifetimeExtendedObjectRegion for temporaries which are + /// lifetime-extended by *static* references. + /// This differs from \ref getCXXLifetimeExtendedObjectRegion(Expr const *, + /// ValueDecl const *, LocationContext const *) in the super-region used. + const CXXLifetimeExtendedObjectRegion * + getCXXStaticLifetimeExtendedObjectRegion(const Expr *Ex, ValueDecl const *VD); + /// Create a CXXBaseObjectRegion with the given base class for region /// \p Super. /// @@ -1471,11 +1584,6 @@ public: const LocationContext *lc, unsigned blockCount); - /// Create a CXXTempObjectRegion for temporaries which are lifetime-extended - /// by static references. This differs from getCXXTempObjectRegion in the - /// super-region used. - const CXXTempObjectRegion *getCXXStaticTempObjectRegion(const Expr *Ex); - private: template <typename RegionTy, typename SuperTy, typename Arg1Ty> diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h index 9a34639e2707..ca75c2a756a4 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -23,6 +23,7 @@ #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableMap.h" #include "llvm/Support/Allocator.h" +#include <optional> #include <utility> namespace llvm { @@ -47,8 +48,6 @@ typedef std::unique_ptr<StoreManager>(*StoreManagerCreator)( // ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState. //===----------------------------------------------------------------------===// -template <typename T> struct ProgramStatePartialTrait; - template <typename T> struct ProgramStateTrait { typedef typename T::data_type data_type; static inline void *MakeVoidPtr(data_type D) { return (void*) D; } @@ -80,11 +79,49 @@ private: friend class ProgramStateManager; friend class ExplodedGraph; friend class ExplodedNode; + friend class NodeBuilder; ProgramStateManager *stateMgr; Environment Env; // Maps a Stmt to its current SVal. Store store; // Maps a location to its current value. GenericDataMap GDM; // Custom data stored by a client of this class. + + // A state is infeasible if there is a contradiction among the constraints. + // An infeasible state is represented by a `nullptr`. + // In the sense of `assumeDual`, a state can have two children by adding a + // new constraint and the negation of that new constraint. A parent state is + // over-constrained if both of its children are infeasible. In the + // mathematical sense, it means that the parent is infeasible and we should + // have realized that at the moment when we have created it. However, we + // could not recognize that because of the imperfection of the underlying + // constraint solver. We say it is posteriorly over-constrained because we + // recognize that a parent is infeasible only *after* a new and more specific + // constraint and its negation are evaluated. + // + // Example: + // + // x * x = 4 and x is in the range [0, 1] + // This is an already infeasible state, but the constraint solver is not + // capable of handling sqrt, thus we don't know it yet. + // + // Then a new constraint `x = 0` is added. At this moment the constraint + // solver re-evaluates the existing constraints and realizes the + // contradiction `0 * 0 = 4`. + // We also evaluate the negated constraint `x != 0`; the constraint solver + // deduces `x = 1` and then realizes the contradiction `1 * 1 = 4`. + // Both children are infeasible, thus the parent state is marked as + // posteriorly over-constrained. These parents are handled with special care: + // we do not allow transitions to exploded nodes with such states. + bool PosteriorlyOverconstrained = false; + // Make internal constraint solver entities friends so they can access the + // overconstrained-related functions. We want to keep this API inaccessible + // for Checkers. + friend class ConstraintManager; + bool isPosteriorlyOverconstrained() const { + return PosteriorlyOverconstrained; + } + ProgramStateRef cloneAsPosteriorlyOverconstrained() const; + unsigned refCount; /// makeWithStore - Return a ProgramState with the same values as the current @@ -137,6 +174,7 @@ public: V->Env.Profile(ID); ID.AddPointer(V->store); V->GDM.Profile(ID); + ID.AddBoolean(V->PosteriorlyOverconstrained); } /// Profile - Used to profile the contents of this object for inclusion @@ -179,18 +217,22 @@ public: /// /// This returns a new state with the added constraint on \p cond. /// If no new state is feasible, NULL is returned. - LLVM_NODISCARD ProgramStateRef assume(DefinedOrUnknownSVal cond, - bool assumption) const; + [[nodiscard]] ProgramStateRef assume(DefinedOrUnknownSVal cond, + bool assumption) const; /// Assumes both "true" and "false" for \p cond, and returns both /// corresponding states (respectively). /// /// This is more efficient than calling assume() twice. Note that one (but not /// both) of the returned states may be NULL. - LLVM_NODISCARD std::pair<ProgramStateRef, ProgramStateRef> + [[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef> assume(DefinedOrUnknownSVal cond) const; - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef> + assumeInBoundDual(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, + QualType IndexType = QualType()) const; + + [[nodiscard]] ProgramStateRef assumeInBound(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, bool assumption, QualType IndexType = QualType()) const; @@ -200,17 +242,17 @@ public: /// /// This returns a new state with the added constraint on \p cond. /// If no new state is feasible, NULL is returned. - LLVM_NODISCARD ProgramStateRef assumeInclusiveRange(DefinedOrUnknownSVal Val, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool assumption) const; + [[nodiscard]] ProgramStateRef assumeInclusiveRange(DefinedOrUnknownSVal Val, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool assumption) const; /// Assumes given range both "true" and "false" for \p Val, and returns both /// corresponding states (respectively). /// /// This is more efficient than calling assume() twice. Note that one (but not /// both) of the returned states may be NULL. - LLVM_NODISCARD std::pair<ProgramStateRef, ProgramStateRef> + [[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef> assumeInclusiveRange(DefinedOrUnknownSVal Val, const llvm::APSInt &From, const llvm::APSInt &To) const; @@ -226,6 +268,7 @@ public: ConditionTruthVal areEqual(SVal Lhs, SVal Rhs) const; /// Utility method for getting regions. + LLVM_ATTRIBUTE_RETURNS_NONNULL const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; //==---------------------------------------------------------------------==// @@ -234,16 +277,16 @@ public: /// Create a new state by binding the value 'V' to the statement 'S' in the /// state's environment. - LLVM_NODISCARD ProgramStateRef BindExpr(const Stmt *S, - const LocationContext *LCtx, SVal V, - bool Invalidate = true) const; + [[nodiscard]] ProgramStateRef BindExpr(const Stmt *S, + const LocationContext *LCtx, SVal V, + bool Invalidate = true) const; - LLVM_NODISCARD ProgramStateRef bindLoc(Loc location, SVal V, - const LocationContext *LCtx, - bool notifyChanges = true) const; + [[nodiscard]] ProgramStateRef bindLoc(Loc location, SVal V, + const LocationContext *LCtx, + bool notifyChanges = true) const; - LLVM_NODISCARD ProgramStateRef bindLoc(SVal location, SVal V, - const LocationContext *LCtx) const; + [[nodiscard]] ProgramStateRef bindLoc(SVal location, SVal V, + const LocationContext *LCtx) const; /// Initializes the region of memory represented by \p loc with an initial /// value. Once initialized, all values loaded from any sub-regions of that @@ -251,15 +294,15 @@ public: /// This method should not be used on regions that are already initialized. /// If you need to indicate that memory contents have suddenly become unknown /// within a certain region of memory, consider invalidateRegions(). - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef bindDefaultInitial(SVal loc, SVal V, const LocationContext *LCtx) const; /// Performs C++ zero-initialization procedure on the region of memory /// represented by \p loc. - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef bindDefaultZero(SVal loc, const LocationContext *LCtx) const; - LLVM_NODISCARD ProgramStateRef killBinding(Loc LV) const; + [[nodiscard]] ProgramStateRef killBinding(Loc LV) const; /// Returns the state with bindings for the given regions /// cleared from the store. @@ -279,24 +322,25 @@ public: /// the call and should be considered directly invalidated. /// \param ITraits information about special handling for a particular /// region/symbol. - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef invalidateRegions(ArrayRef<const MemRegion *> Regions, const Expr *E, unsigned BlockCount, const LocationContext *LCtx, bool CausesPointerEscape, InvalidatedSymbols *IS = nullptr, const CallEvent *Call = nullptr, RegionAndSymbolInvalidationTraits *ITraits = nullptr) const; - LLVM_NODISCARD ProgramStateRef - invalidateRegions(ArrayRef<SVal> Regions, const Expr *E, - unsigned BlockCount, const LocationContext *LCtx, - bool CausesPointerEscape, InvalidatedSymbols *IS = nullptr, + [[nodiscard]] ProgramStateRef + invalidateRegions(ArrayRef<SVal> Regions, const Expr *E, unsigned BlockCount, + const LocationContext *LCtx, bool CausesPointerEscape, + InvalidatedSymbols *IS = nullptr, const CallEvent *Call = nullptr, RegionAndSymbolInvalidationTraits *ITraits = nullptr) const; /// enterStackFrame - Returns the state for entry to the given stack frame, /// preserving the current state. - LLVM_NODISCARD ProgramStateRef enterStackFrame( - const CallEvent &Call, const StackFrameContext *CalleeCtx) const; + [[nodiscard]] ProgramStateRef + enterStackFrame(const CallEvent &Call, + const StackFrameContext *CalleeCtx) const; /// Return the value of 'self' if available in the given context. SVal getSelfSVal(const LocationContext *LC) const; @@ -308,10 +352,6 @@ public: Loc getLValue(const CXXRecordDecl *BaseClass, const SubRegion *Super, bool IsVirtual) const; - /// Get the lvalue for a parameter. - Loc getLValue(const Expr *Call, unsigned Index, - const LocationContext *LC) const; - /// Get the lvalue for a variable reference. Loc getLValue(const VarDecl *D, const LocationContext *LC) const; @@ -379,7 +419,7 @@ public: void *const* FindGDM(void *K) const; template <typename T> - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef add(typename ProgramStateTrait<T>::key_type K) const; template <typename T> @@ -399,27 +439,27 @@ public: typename ProgramStateTrait<T>::context_type get_context() const; template <typename T> - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef remove(typename ProgramStateTrait<T>::key_type K) const; template <typename T> - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef remove(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::context_type C) const; - template <typename T> LLVM_NODISCARD ProgramStateRef remove() const; + template <typename T> [[nodiscard]] ProgramStateRef remove() const; template <typename T> - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef set(typename ProgramStateTrait<T>::data_type D) const; template <typename T> - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef set(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::value_type E) const; template <typename T> - LLVM_NODISCARD ProgramStateRef + [[nodiscard]] ProgramStateRef set(typename ProgramStateTrait<T>::key_type K, typename ProgramStateTrait<T>::value_type E, typename ProgramStateTrait<T>::context_type C) const; @@ -687,7 +727,7 @@ inline ProgramStateRef ProgramState::assumeInclusiveRange( if (Val.isUnknown()) return this; - assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!"); + assert(isa<NonLoc>(Val) && "Only NonLocs are supported!"); return getStateManager().ConstraintMgr->assumeInclusiveRange( this, Val.castAs<NonLoc>(), From, To, Assumption); @@ -700,14 +740,14 @@ ProgramState::assumeInclusiveRange(DefinedOrUnknownSVal Val, if (Val.isUnknown()) return std::make_pair(this, this); - assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!"); + assert(isa<NonLoc>(Val) && "Only NonLocs are supported!"); return getStateManager().ConstraintMgr->assumeInclusiveRangeDual( this, Val.castAs<NonLoc>(), From, To); } inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V, const LocationContext *LCtx) const { - if (Optional<Loc> L = LV.getAs<Loc>()) + if (std::optional<Loc> L = LV.getAs<Loc>()) return bindLoc(*L, V, LCtx); return this; } @@ -757,7 +797,7 @@ inline SVal ProgramState::getLValue(const IndirectFieldDecl *D, } inline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ - if (Optional<NonLoc> N = Idx.getAs<NonLoc>()) + if (std::optional<NonLoc> N = Idx.getAs<NonLoc>()) return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base); return UnknownVal(); } diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h index da82a55e3625..15bec97c5be8 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h @@ -21,29 +21,32 @@ #include "llvm/ADT/ImmutableSet.h" #include "llvm/Support/Allocator.h" #include <cstdint> +#include <type_traits> namespace clang { namespace ento { - template <typename T> struct ProgramStatePartialTrait; - - /// Declares a program state trait for type \p Type called \p Name, and - /// introduce a type named \c NameTy. - /// The macro should not be used inside namespaces. - #define REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, Type) \ - namespace { \ - class Name {}; \ - using Name ## Ty = Type; \ - } \ - namespace clang { \ - namespace ento { \ - template <> \ - struct ProgramStateTrait<Name> \ - : public ProgramStatePartialTrait<Name ## Ty> { \ - static void *GDMIndex() { static int Index; return &Index; } \ - }; \ - } \ - } +template <typename T, typename Enable = void> struct ProgramStatePartialTrait; + +/// Declares a program state trait for type \p Type called \p Name, and +/// introduce a type named \c NameTy. +/// The macro should not be used inside namespaces. +#define REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, Type) \ + namespace { \ + class Name {}; \ + using Name##Ty = Type; \ + } \ + namespace clang { \ + namespace ento { \ + template <> \ + struct ProgramStateTrait<Name> : public ProgramStatePartialTrait<Name##Ty> { \ + static void *GDMIndex() { \ + static int Index; \ + return &Index; \ + } \ + }; \ + } \ + } /// Declares a factory for objects of type \p Type in the program state /// manager. The type must provide a ::Factory sub-class. Commonly used for @@ -267,60 +270,27 @@ namespace ento { } }; - // Partial specialization for bool. - template <> struct ProgramStatePartialTrait<bool> { - using data_type = bool; - - static data_type MakeData(void *const *p) { - return p ? (data_type) (uintptr_t) *p - : data_type(); - } - - static void *MakeVoidPtr(data_type d) { - return (void *) (uintptr_t) d; - } + template <typename T> struct DefaultProgramStatePartialTraitImpl { + using data_type = T; + static T MakeData(void *const *P) { return P ? (T)(uintptr_t)*P : T{}; } + static void *MakeVoidPtr(T D) { return (void *)(uintptr_t)D; } }; - // Partial specialization for unsigned. - template <> struct ProgramStatePartialTrait<unsigned> { - using data_type = unsigned; - - static data_type MakeData(void *const *p) { - return p ? (data_type) (uintptr_t) *p - : data_type(); - } - - static void *MakeVoidPtr(data_type d) { - return (void *) (uintptr_t) d; - } - }; - - // Partial specialization for void*. - template <> struct ProgramStatePartialTrait<void *> { - using data_type = void *; - - static data_type MakeData(void *const *p) { - return p ? *p - : data_type(); - } - - static void *MakeVoidPtr(data_type d) { - return d; - } - }; - - // Partial specialization for const void *. - template <> struct ProgramStatePartialTrait<const void *> { - using data_type = const void *; + // Partial specialization for integral types. + template <typename T> + struct ProgramStatePartialTrait<T, + std::enable_if_t<std::is_integral<T>::value>> + : DefaultProgramStatePartialTraitImpl<T> {}; - static data_type MakeData(void *const *p) { - return p ? *p : data_type(); - } + // Partial specialization for enums. + template <typename T> + struct ProgramStatePartialTrait<T, std::enable_if_t<std::is_enum<T>::value>> + : DefaultProgramStatePartialTraitImpl<T> {}; - static void *MakeVoidPtr(data_type d) { - return const_cast<void *>(d); - } - }; + // Partial specialization for pointers. + template <typename T> + struct ProgramStatePartialTrait<T *, void> + : DefaultProgramStatePartialTraitImpl<T *> {}; } // namespace ento } // namespace clang diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h index c67df1e51b4f..49ea006e27aa 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h @@ -10,8 +10,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H -#define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H +#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_RANGEDCONSTRAINTMANAGER_H +#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_RANGEDCONSTRAINTMANAGER_H #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" @@ -48,6 +48,7 @@ public: ID.AddPointer(&To()); } void dump(raw_ostream &OS) const; + void dump() const; // In order to keep non-overlapping ranges sorted, we can compare only From // points. @@ -139,6 +140,30 @@ public: /// Complexity: O(N) /// where N = size(Original) RangeSet add(RangeSet Original, const llvm::APSInt &Point); + /// Create a new set which is a union of two given ranges. + /// Possible intersections are not checked here. + /// + /// Complexity: O(N + M) + /// where N = size(LHS), M = size(RHS) + RangeSet unite(RangeSet LHS, RangeSet RHS); + /// Create a new set by uniting given range set with the given range. + /// All intersections and adjacent ranges are handled here. + /// + /// Complexity: O(N) + /// where N = size(Original) + RangeSet unite(RangeSet Original, Range Element); + /// Create a new set by uniting given range set with the given point. + /// All intersections and adjacent ranges are handled here. + /// + /// Complexity: O(N) + /// where N = size(Original) + RangeSet unite(RangeSet Original, llvm::APSInt Point); + /// Create a new set by uniting given range set with the given range + /// between points. All intersections and adjacent ranges are handled here. + /// + /// Complexity: O(N) + /// where N = size(Original) + RangeSet unite(RangeSet Original, llvm::APSInt From, llvm::APSInt To); RangeSet getEmptySet() { return &EmptySet; } @@ -212,6 +237,29 @@ public: /// Complexity: O(N) /// where N = size(What) RangeSet negate(RangeSet What); + /// Performs promotions, truncations and conversions of the given set. + /// + /// This function is optimized for each of the six cast cases: + /// - noop + /// - conversion + /// - truncation + /// - truncation-conversion + /// - promotion + /// - promotion-conversion + /// + /// NOTE: This function is NOT self-inverse for truncations, because of + /// the higher bits loss: + /// - castTo(castTo(OrigRangeOfInt, char), int) != OrigRangeOfInt. + /// - castTo(castTo(OrigRangeOfChar, int), char) == OrigRangeOfChar. + /// But it is self-inverse for all the rest casts. + /// + /// Complexity: + /// - Noop O(1); + /// - Truncation O(N^2); + /// - Another case O(N); + /// where N = size(What) + RangeSet castTo(RangeSet What, APSIntType Ty); + RangeSet castTo(RangeSet What, QualType T); /// Return associated value factory. BasicValueFactory &getValueFactory() const { return ValueFactory; } @@ -223,6 +271,25 @@ public: ContainerType *construct(ContainerType &&From); RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS); + /// NOTE: This function relies on the fact that all values in the + /// containers are persistent (created via BasicValueFactory::getValue). + ContainerType unite(const ContainerType &LHS, const ContainerType &RHS); + + /// This is a helper function for `castTo` method. Implies not to be used + /// separately. + /// Performs a truncation case of a cast operation. + ContainerType truncateTo(RangeSet What, APSIntType Ty); + + /// This is a helper function for `castTo` method. Implies not to be used + /// separately. + /// Performs a conversion case and a promotion-conversion case for signeds + /// of a cast operation. + ContainerType convertTo(RangeSet What, APSIntType Ty); + + /// This is a helper function for `castTo` method. Implies not to be used + /// separately. + /// Performs a promotion for unsigneds only. + ContainerType promoteTo(RangeSet What, APSIntType Ty); // Many operations include producing new APSInt values and that's why // we need this factory. @@ -275,13 +342,37 @@ public: /// Complexity: O(1) const llvm::APSInt &getMaxValue() const; + bool isUnsigned() const; + uint32_t getBitWidth() const; + APSIntType getAPSIntType() 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); } + bool containsZero() const { + APSIntType T{getMinValue()}; + return contains(T.getZeroValue()); + } + + /// Test if the range is the [0,0] range. + /// + /// Complexity: O(1) + bool encodesFalseRange() const { + const llvm::APSInt *Constant = getConcreteValue(); + return Constant && Constant->isZero(); + } + + /// Test if the range doesn't contain zero. + /// + /// Complexity: O(logN) + /// where N = size(this) + bool encodesTrueRange() const { return !containsZero(); } + void dump(raw_ostream &OS) const; + void dump() const; bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; } bool operator!=(const RangeSet &Other) const { return !(*this == Other); } @@ -387,11 +478,22 @@ 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. +/// Try to simplify a given symbolic expression 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. If the symbol is +/// simplified to a non-symbol (e.g. to a constant) then the original symbol +/// is returned. We use this function in the family of assumeSymNE/EQ/LT/../GE +/// functions where we can work only with symbols. Use the other function +/// (simplifyToSVal) if you are interested in a simplification that may yield +/// a concrete constant value. SymbolRef simplify(ProgramStateRef State, SymbolRef Sym); +/// Try to simplify a given symbolic expression's associated `SVal` based on the +/// constraints in State. This is very similar to `simplify`, but this function +/// always returns the simplified SVal. The simplified SVal might be a single +/// constant (i.e. `ConcreteInt`). +SVal simplifyToSVal(ProgramStateRef State, SymbolRef Sym); + } // namespace ento } // namespace clang diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def index 44ab31fc9f2e..245828a2fcc0 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def @@ -69,6 +69,7 @@ ABSTRACT_REGION(SubRegion, MemRegion) REGION(CXXBaseObjectRegion, TypedValueRegion) REGION(CXXDerivedObjectRegion, TypedValueRegion) REGION(CXXTempObjectRegion, TypedValueRegion) + REGION(CXXLifetimeExtendedObjectRegion, TypedValueRegion) REGION(CXXThisRegion, TypedValueRegion) ABSTRACT_REGION(DeclRegion, TypedValueRegion) REGION(FieldRegion, DeclRegion) diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h index e4878d4e0156..5116a4c06850 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h @@ -18,6 +18,7 @@ #include "clang/Basic/TargetInfo.h" #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h" +#include <optional> typedef llvm::ImmutableSet< std::pair<clang::ento::SymbolRef, const llvm::SMTExpr *>> @@ -128,8 +129,8 @@ public: addStateConstraints(State); // Constraints are unsatisfiable - Optional<bool> isSat = Solver->check(); - if (!isSat.hasValue() || !isSat.getValue()) + std::optional<bool> isSat = Solver->check(); + if (!isSat || !*isSat) return nullptr; // Model does not assign interpretation @@ -145,8 +146,8 @@ public: Solver->addConstraint(NotExp); - Optional<bool> isNotSat = Solver->check(); - if (!isNotSat.hasValue() || isNotSat.getValue()) + std::optional<bool> isNotSat = Solver->check(); + if (!isNotSat || *isNotSat) return nullptr; // This is the only solution, store it @@ -202,9 +203,9 @@ public: auto CZ = State->get<ConstraintSMT>(); auto &CZFactory = State->get_context<ConstraintSMT>(); - for (auto I = CZ.begin(), E = CZ.end(); I != E; ++I) { - if (SymReaper.isDead(I->first)) - CZ = CZFactory.remove(CZ, *I); + for (const auto &Entry : CZ) { + if (SymReaper.isDead(Entry.first)) + CZ = CZFactory.remove(CZ, Entry); } return State->set<ConstraintSMT>(CZ); @@ -246,7 +247,7 @@ public: bool canReasonAbout(SVal X) const override { const TargetInfo &TI = getBasicVals().getContext().getTargetInfo(); - Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>(); + std::optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>(); if (!SymVal) return true; @@ -340,11 +341,11 @@ protected: Solver->reset(); addStateConstraints(NewState); - Optional<bool> res = Solver->check(); - if (!res.hasValue()) + std::optional<bool> res = Solver->check(); + if (!res) Cached[hash] = ConditionTruthVal(); else - Cached[hash] = ConditionTruthVal(res.getValue()); + Cached[hash] = ConditionTruthVal(*res); return Cached[hash]; } diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h index 2d0f169260a4..fcc9c02999b3 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h @@ -446,6 +446,30 @@ public: return getCastExpr(Solver, Ctx, Exp, FromTy, Sym->getType()); } + if (const UnarySymExpr *USE = dyn_cast<UnarySymExpr>(Sym)) { + if (RetTy) + *RetTy = Sym->getType(); + + QualType OperandTy; + llvm::SMTExprRef OperandExp = + getSymExpr(Solver, Ctx, USE->getOperand(), &OperandTy, hasComparison); + llvm::SMTExprRef UnaryExp = + OperandTy->isRealFloatingType() + ? fromFloatUnOp(Solver, USE->getOpcode(), OperandExp) + : fromUnOp(Solver, USE->getOpcode(), OperandExp); + + // Currently, without the `support-symbolic-integer-casts=true` option, + // we do not emit `SymbolCast`s for implicit casts. + // One such implicit cast is missing if the operand of the unary operator + // has a different type than the unary itself. + if (Ctx.getTypeSize(OperandTy) != Ctx.getTypeSize(Sym->getType())) { + if (hasComparison) + *hasComparison = false; + return getCastExpr(Solver, Ctx, UnaryExp, OperandTy, Sym->getType()); + } + return UnaryExp; + } + if (const BinarySymExpr *BSE = dyn_cast<BinarySymExpr>(Sym)) { llvm::SMTExprRef Exp = getSymBinExpr(Solver, Ctx, BSE, hasComparison, RetTy); @@ -654,14 +678,14 @@ public: assert(!LTy.isNull() && !RTy.isNull() && "Input type is null!"); // Always perform integer promotion before checking type equality. // Otherwise, e.g. (bool) a + (bool) b could trigger a backend assertion - if (LTy->isPromotableIntegerType()) { + if (Ctx.isPromotableIntegerType(LTy)) { QualType NewTy = Ctx.getPromotedIntegerType(LTy); uint64_t NewBitWidth = Ctx.getTypeSize(NewTy); LHS = (*doCast)(Solver, LHS, NewTy, NewBitWidth, LTy, LBitWidth); LTy = NewTy; LBitWidth = NewBitWidth; } - if (RTy->isPromotableIntegerType()) { + if (Ctx.isPromotableIntegerType(RTy)) { QualType NewTy = Ctx.getPromotedIntegerType(RTy); uint64_t NewBitWidth = Ctx.getTypeSize(NewTy); RHS = (*doCast)(Solver, RHS, NewTy, NewBitWidth, RTy, RBitWidth); diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h index 87a49cf4ffe9..d7cff49036cb 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -28,11 +28,12 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" #include "llvm/ADT/ImmutableList.h" -#include "llvm/ADT/Optional.h" #include <cstdint> +#include <optional> namespace clang { +class AnalyzerOptions; class BlockDecl; class CXXBoolLiteralExpr; class CXXMethodDecl; @@ -66,65 +67,28 @@ protected: ProgramStateManager &StateMgr; + const AnalyzerOptions &AnOpts; + /// The scalar type to use for array indices. const QualType ArrayIndexTy; /// The width of the scalar type used for array indices. const unsigned ArrayIndexWidth; - 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, - ProgramStateManager &stateMgr) - : Context(context), BasicVals(context, alloc), - SymMgr(context, BasicVals, alloc), MemMgr(context, alloc), - StateMgr(stateMgr), ArrayIndexTy(context.LongLongTy), - ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {} + ProgramStateManager &stateMgr); virtual ~SValBuilder() = default; - bool haveSameType(const SymExpr *Sym1, const SymExpr *Sym2) { - return haveSameType(Sym1->getType(), Sym2->getType()); - } - - bool haveSameType(QualType Ty1, QualType Ty2) { - // FIXME: Remove the second disjunct when we support symbolic - // truncation/extension. - return (Context.getCanonicalType(Ty1) == Context.getCanonicalType(Ty2) || - (Ty1->isIntegralOrEnumerationType() && - Ty2->isIntegralOrEnumerationType())); - } - SVal evalCast(SVal V, QualType CastTy, QualType OriginalTy); // Handles casts of type CK_IntegralCast. SVal evalIntegralCast(ProgramStateRef state, SVal val, QualType castTy, QualType originalType); - virtual SVal evalMinus(NonLoc val) = 0; - - virtual SVal evalComplement(NonLoc val) = 0; + SVal evalMinus(NonLoc val); + SVal evalComplement(NonLoc val); /// Create a new value which represents a binary expression with two non- /// location operands. @@ -146,6 +110,14 @@ public: /// that value is returned. Otherwise, returns NULL. virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal val) = 0; + /// Tries to get the minimal possible (integer) value of a given SVal. If the + /// constraint manager cannot provide an useful answer, this returns NULL. + virtual const llvm::APSInt *getMinValue(ProgramStateRef state, SVal val) = 0; + + /// Tries to get the maximal possible (integer) value of a given SVal. If the + /// constraint manager cannot provide an useful answer, this returns NULL. + virtual const llvm::APSInt *getMaxValue(ProgramStateRef state, SVal val) = 0; + /// Simplify symbolic expressions within a given SVal. Return an SVal /// that represents the same value, but is hopefully easier to work with /// than the original SVal. @@ -155,6 +127,9 @@ public: SVal makeSymExprValNN(BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy); + SVal evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc, + SVal operand, QualType type); + SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type); @@ -188,6 +163,8 @@ public: MemRegionManager &getRegionManager() { return MemMgr; } const MemRegionManager &getRegionManager() const { return MemMgr; } + const AnalyzerOptions &getAnalyzerOptions() const { return AnOpts; } + // Forwarding methods to SymbolManager. const SymbolConjured* conjureSymbol(const Stmt *stmt, @@ -246,6 +223,15 @@ public: const LocationContext *LCtx, QualType type, unsigned Count); + /// Create an SVal representing the result of an alloca()-like call, that is, + /// an AllocaRegion on the stack. + /// + /// After calling this function, it's a good idea to set the extent of the + /// returned AllocaRegion. + loc::MemRegionVal getAllocaRegionVal(const Expr *E, + const LocationContext *LCtx, + unsigned Count); + DefinedOrUnknownSVal getDerivedRegionValueSymbolVal( SymbolRef parentSymbol, const TypedValueRegion *region); @@ -266,8 +252,8 @@ public: /// Returns the value of \p E, if it can be determined in a non-path-sensitive /// manner. /// - /// If \p E is not a constant or cannot be modeled, returns \c None. - Optional<SVal> getConstantVal(const Expr *E); + /// If \p E is not a constant or cannot be modeled, returns \c std::nullopt. + std::optional<SVal> getConstantVal(const Expr *E); NonLoc makeCompoundVal(QualType type, llvm::ImmutableList<SVal> vals) { return nonloc::CompoundVal(BasicVals.getCompoundValData(type, vals)); @@ -332,26 +318,30 @@ public: return nonloc::ConcreteInt(BasicVals.getIntValue(integer, isUnsigned)); } - NonLoc makeIntValWithPtrWidth(uint64_t integer, bool isUnsigned) { - return nonloc::ConcreteInt( - BasicVals.getIntWithPtrWidth(integer, isUnsigned)); + NonLoc makeIntValWithWidth(QualType ptrType, uint64_t integer) { + return nonloc::ConcreteInt(BasicVals.getValue(integer, ptrType)); } NonLoc makeLocAsInteger(Loc loc, unsigned bits) { return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(loc, bits)); } - NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, - const llvm::APSInt& rhs, QualType type); + nonloc::SymbolVal makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, + const llvm::APSInt &rhs, QualType type); + + nonloc::SymbolVal makeNonLoc(const llvm::APSInt &rhs, + BinaryOperator::Opcode op, const SymExpr *lhs, + QualType type); - NonLoc makeNonLoc(const llvm::APSInt& rhs, BinaryOperator::Opcode op, - const SymExpr *lhs, QualType type); + nonloc::SymbolVal makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, + const SymExpr *rhs, QualType type); - NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, - const SymExpr *rhs, QualType type); + NonLoc makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op, + QualType type); /// Create a NonLoc value for cast. - NonLoc makeNonLoc(const SymExpr *operand, QualType fromTy, QualType toTy); + nonloc::SymbolVal makeNonLoc(const SymExpr *operand, QualType fromTy, + QualType toTy); nonloc::ConcreteInt makeTruthVal(bool b, QualType type) { return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type)); @@ -364,38 +354,46 @@ public: /// Create NULL pointer, with proper pointer bit-width for given address /// space. /// \param type pointer type. - Loc makeNullWithType(QualType type) { + loc::ConcreteInt makeNullWithType(QualType type) { + // We cannot use the `isAnyPointerType()`. + assert((type->isPointerType() || type->isObjCObjectPointerType() || + type->isBlockPointerType() || type->isNullPtrType() || + type->isReferenceType()) && + "makeNullWithType must use pointer type"); + + // The `sizeof(T&)` is `sizeof(T)`, thus we replace the reference with a + // pointer. Here we assume that references are actually implemented by + // pointers under-the-hood. + type = type->isReferenceType() + ? Context.getPointerType(type->getPointeeType()) + : type; return loc::ConcreteInt(BasicVals.getZeroWithTypeSize(type)); } - Loc makeNull() { - return loc::ConcreteInt(BasicVals.getZeroWithPtrWidth()); - } - - Loc makeLoc(SymbolRef sym) { + loc::MemRegionVal makeLoc(SymbolRef sym) { return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); } - Loc makeLoc(const MemRegion* region) { + loc::MemRegionVal makeLoc(const MemRegion *region) { return loc::MemRegionVal(region); } - Loc makeLoc(const AddrLabelExpr *expr) { + loc::GotoLabel makeLoc(const AddrLabelExpr *expr) { return loc::GotoLabel(expr->getLabel()); } - Loc makeLoc(const llvm::APSInt& integer) { + loc::ConcreteInt makeLoc(const llvm::APSInt &integer) { return loc::ConcreteInt(BasicVals.getValue(integer)); } - /// Return MemRegionVal on success cast, otherwise return None. - Optional<loc::MemRegionVal> getCastedMemRegionVal(const MemRegion *region, - QualType type); + /// Return MemRegionVal on success cast, otherwise return std::nullopt. + std::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. - SVal makeSymbolVal(SymbolRef Sym) { + DefinedSVal makeSymbolVal(SymbolRef Sym) { if (Loc::isLocType(Sym->getType())) return makeLoc(Sym); return nonloc::SymbolVal(Sym); diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h index fc83e26183b3..b10f416f4435 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h @@ -14,9 +14,9 @@ #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALVISITOR_H #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALVISITOR_H +#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" namespace clang { @@ -25,49 +25,40 @@ namespace ento { /// SValVisitor - this class implements a simple visitor for SVal /// subclasses. template <typename ImplClass, typename RetTy = void> class SValVisitor { -public: - -#define DISPATCH(NAME, CLASS) \ - return static_cast<ImplClass *>(this)->Visit ## NAME(V.castAs<CLASS>()) + ImplClass &derived() { return *static_cast<ImplClass *>(this); } +public: RetTy Visit(SVal V) { // Dispatch to VisitFooVal for each FooVal. - // Take namespaces (loc:: and nonloc::) into account. - switch (V.getBaseKind()) { -#define BASIC_SVAL(Id, Parent) case SVal::Id ## Kind: DISPATCH(Id, Id); + switch (V.getKind()) { +#define BASIC_SVAL(Id, Parent) \ + case SVal::Id##Kind: \ + return derived().Visit##Id(V.castAs<Id>()); +#define LOC_SVAL(Id, Parent) \ + case SVal::Loc##Id##Kind: \ + return derived().Visit##Id(V.castAs<loc::Id>()); +#define NONLOC_SVAL(Id, Parent) \ + case SVal::NonLoc##Id##Kind: \ + return derived().Visit##Id(V.castAs<nonloc::Id>()); #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" - case SVal::LocKind: - switch (V.getSubKind()) { -#define LOC_SVAL(Id, Parent) \ - case loc::Id ## Kind: DISPATCH(Loc ## Id, loc :: Id); -#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" - } - llvm_unreachable("Unknown Loc sub-kind!"); - case SVal::NonLocKind: - switch (V.getSubKind()) { -#define NONLOC_SVAL(Id, Parent) \ - case nonloc::Id ## Kind: DISPATCH(NonLoc ## Id, nonloc :: Id); -#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" - } - llvm_unreachable("Unknown NonLoc sub-kind!"); } llvm_unreachable("Unknown SVal kind!"); } -#define BASIC_SVAL(Id, Parent) \ - RetTy Visit ## Id(Id V) { DISPATCH(Parent, Id); } -#define ABSTRACT_SVAL(Id, Parent) \ - BASIC_SVAL(Id, Parent) -#define LOC_SVAL(Id, Parent) \ - RetTy VisitLoc ## Id(loc::Id V) { DISPATCH(Parent, Parent); } -#define NONLOC_SVAL(Id, Parent) \ - RetTy VisitNonLoc ## Id(nonloc::Id V) { DISPATCH(Parent, Parent); } + // Dispatch to the more generic handler as a default implementation. +#define BASIC_SVAL(Id, Parent) \ + RetTy Visit##Id(Id V) { return derived().Visit##Parent(V.castAs<Id>()); } +#define ABSTRACT_SVAL(Id, Parent) BASIC_SVAL(Id, Parent) +#define LOC_SVAL(Id, Parent) \ + RetTy Visit##Id(loc::Id V) { return derived().VisitLoc(V.castAs<Loc>()); } +#define NONLOC_SVAL(Id, Parent) \ + RetTy Visit##Id(nonloc::Id V) { \ + return derived().VisitNonLoc(V.castAs<NonLoc>()); \ + } #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" // Base case, ignore it. :) RetTy VisitSVal(SVal V) { return RetTy(); } - -#undef DISPATCH }; /// SymExprVisitor - this class implements a simple visitor for SymExpr diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.def b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.def index eb05de6d9933..36d2425d155a 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.def +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.def @@ -6,28 +6,24 @@ // //===----------------------------------------------------------------------===// // -// The list of symbolic values (SVal kinds and sub-kinds) used in the Static -// Analyzer. The distinction between loc:: and nonloc:: SVal namespaces is +// The list of symbolic values (SVal kinds) used in the Static Analyzer. +// The distinction between `loc::` and `nonloc::` SVal namespaces is // currently hardcoded, because it is too peculiar and explicit to be handled // uniformly. In order to use this information, users of this file must define // one or more of the following macros: // -// BASIC_SVAL(Id, Parent) - for specific SVal sub-kinds, which are -// neither in loc:: nor in nonloc:: namespace; these classes occupy -// their own base kind IdKind. +// BASIC_SVAL(Id, Parent) - for specific SVal kinds, which are +// neither in `loc::` nor in `nonloc::` namespace. // // ABSTRACT_SVAL(Id, Parent) - for abstract SVal classes which are -// neither in loc:: nor in nonloc:: namespace, +// neither in `loc::` nor in `nonloc::` namespace, // -// ABSTRACT_SVAL_WITH_KIND(Id, Parent) - for SVal classes which are also -// neither in loc:: nor in nonloc:: namespace, but occupy a whole base kind -// identifier IdKind, much like BASIC_SVALs. +// LOC_SVAL(Id, Parent) - for values in `loc::` namespace. // -// LOC_SVAL(Id, Parent) - for values in loc:: namespace, which occupy a sub-kind -// loc::IdKind. +// NONLOC_SVAL(Id, Parent) - for values in `nonloc::` namespace. // -// NONLOC_SVAL(Id, Parent) - for values in nonloc:: namespace, which occupy a -// sub-kind nonloc::IdKind. +// SVAL_RANGE(Id, First, Last) - for defining range of subtypes of +// the abstract class `Id`. // //===----------------------------------------------------------------------===// @@ -39,10 +35,6 @@ #define ABSTRACT_SVAL(Id, Parent) #endif -#ifndef ABSTRACT_SVAL_WITH_KIND -#define ABSTRACT_SVAL_WITH_KIND(Id, Parent) ABSTRACT_SVAL(Id, Parent) -#endif - #ifndef LOC_SVAL #define LOC_SVAL(Id, Parent) #endif @@ -51,24 +43,30 @@ #define NONLOC_SVAL(Id, Parent) #endif +#ifndef SVAL_RANGE +#define SVAL_RANGE(Id, First, Last) +#endif + BASIC_SVAL(UndefinedVal, SVal) ABSTRACT_SVAL(DefinedOrUnknownSVal, SVal) BASIC_SVAL(UnknownVal, DefinedOrUnknownSVal) ABSTRACT_SVAL(DefinedSVal, DefinedOrUnknownSVal) - ABSTRACT_SVAL_WITH_KIND(Loc, DefinedSVal) + ABSTRACT_SVAL(Loc, DefinedSVal) LOC_SVAL(ConcreteInt, Loc) LOC_SVAL(GotoLabel, Loc) LOC_SVAL(MemRegionVal, Loc) - ABSTRACT_SVAL_WITH_KIND(NonLoc, DefinedSVal) + SVAL_RANGE(Loc, ConcreteInt, MemRegionVal) + ABSTRACT_SVAL(NonLoc, DefinedSVal) NONLOC_SVAL(CompoundVal, NonLoc) NONLOC_SVAL(ConcreteInt, NonLoc) NONLOC_SVAL(LazyCompoundVal, NonLoc) NONLOC_SVAL(LocAsInteger, NonLoc) NONLOC_SVAL(SymbolVal, NonLoc) NONLOC_SVAL(PointerToMember, NonLoc) + SVAL_RANGE(NonLoc, CompoundVal, PointerToMember) +#undef SVAL_RANGE #undef NONLOC_SVAL #undef LOC_SVAL -#undef ABSTRACT_SVAL_WITH_KIND #undef ABSTRACT_SVAL #undef BASIC_SVAL diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h index 6199c8d8d179..c60528b7685f 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -18,14 +18,16 @@ #include "clang/AST/Type.h" #include "clang/Basic/LLVM.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" +#include "llvm/ADT/APSInt.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableList.h" -#include "llvm/ADT/None.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/STLForwardCompat.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Casting.h" #include <cassert> #include <cstdint> +#include <optional> #include <utility> //==------------------------------------------------------------------------==// @@ -35,13 +37,11 @@ namespace clang { class CXXBaseSpecifier; -class DeclaratorDecl; class FunctionDecl; class LabelDecl; namespace ento { -class BasicValueFactory; class CompoundValData; class LazyCompoundValData; class MemRegion; @@ -49,105 +49,63 @@ class PointerToMemberData; class SValBuilder; class TypedValueRegion; -namespace nonloc { - -/// Sub-kinds for NonLoc values. -enum Kind { -#define NONLOC_SVAL(Id, Parent) Id ## Kind, -#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" -}; - -} // namespace nonloc - -namespace loc { - -/// Sub-kinds for Loc values. -enum Kind { -#define LOC_SVAL(Id, Parent) Id ## Kind, -#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" -}; - -} // namespace loc - /// SVal - This represents a symbolic expression, which can be either /// an L-value or an R-value. /// class SVal { public: - enum BaseKind { - // The enumerators must be representable using 2 bits. -#define BASIC_SVAL(Id, Parent) Id ## Kind, -#define ABSTRACT_SVAL_WITH_KIND(Id, Parent) Id ## Kind, + enum SValKind : unsigned char { +#define BASIC_SVAL(Id, Parent) Id##Kind, +#define LOC_SVAL(Id, Parent) Loc##Id##Kind, +#define NONLOC_SVAL(Id, Parent) NonLoc##Id##Kind, +#define SVAL_RANGE(Id, First, Last) \ + BEGIN_##Id = Id##First##Kind, END_##Id = Id##Last##Kind, #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" }; - enum { BaseBits = 2, BaseMask = 0b11 }; protected: const void *Data = nullptr; + SValKind Kind = UndefinedValKind; - /// The lowest 2 bits are a BaseKind (0 -- 3). - /// The higher bits are an unsigned "kind" value. - unsigned Kind = 0; + explicit SVal(SValKind Kind, const void *Data = nullptr) + : Data(Data), Kind(Kind) {} - explicit SVal(const void *d, bool isLoc, unsigned ValKind) - : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} - - explicit SVal(BaseKind k, const void *D = nullptr) : Data(D), Kind(k) {} + template <typename T> const T *castDataAs() const { + return static_cast<const T *>(Data); + } public: explicit SVal() = default; /// Convert to the specified SVal type, asserting that this SVal is of /// the desired type. - template<typename T> - T castAs() const { - assert(T::isKind(*this)); - return *static_cast<const T *>(this); - } + template <typename T> T castAs() const { return llvm::cast<T>(*this); } - /// Convert to the specified SVal type, returning None if this SVal is + /// Convert to the specified SVal type, returning std::nullopt if this SVal is /// not of the desired type. - template<typename T> - Optional<T> getAs() const { - if (!T::isKind(*this)) - return None; - return *static_cast<const T *>(this); + template <typename T> std::optional<T> getAs() const { + return llvm::dyn_cast<T>(*this); } - unsigned getRawKind() const { return Kind; } - BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); } - unsigned getSubKind() const { return Kind >> BaseBits; } + SValKind getKind() const { return Kind; } // This method is required for using SVal in a FoldingSetNode. It // extracts a unique signature for this SVal object. void Profile(llvm::FoldingSetNodeID &ID) const { - ID.AddInteger((unsigned) getRawKind()); ID.AddPointer(Data); + ID.AddInteger(llvm::to_underlying(getKind())); } - bool operator==(const SVal &R) const { - return getRawKind() == R.getRawKind() && Data == R.Data; - } + bool operator==(SVal R) const { return Kind == R.Kind && Data == R.Data; } + bool operator!=(SVal R) const { return !(*this == R); } - bool operator!=(const SVal &R) const { - return !(*this == R); - } + bool isUnknown() const { return getKind() == UnknownValKind; } - bool isUnknown() const { - return getRawKind() == UnknownValKind; - } + bool isUndef() const { return getKind() == UndefinedValKind; } - bool isUndef() const { - return getRawKind() == UndefinedValKind; - } + bool isUnknownOrUndef() const { return isUnknown() || isUndef(); } - bool isUnknownOrUndef() const { - return getRawKind() <= UnknownValKind; - } - - bool isValid() const { - return getRawKind() > UnknownValKind; - } + bool isValid() const { return !isUnknownOrUndef(); } bool isConstant() const; @@ -155,9 +113,6 @@ public: bool isZeroConstant() const; - /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true; - bool hasConjuredSymbol() const; - /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. /// Otherwise return 0. @@ -182,6 +137,11 @@ public: /// should continue to the base regions if the region is not symbolic. SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const; + /// If this SVal is loc::ConcreteInt or nonloc::ConcreteInt, + /// return a pointer to APSInt which is held in it. + /// Otherwise, return nullptr. + const llvm::APSInt *getAsInteger() const; + const MemRegion *getAsRegion() const; /// printJson - Pretty-prints in JSON format. @@ -190,16 +150,11 @@ public: void dumpToStream(raw_ostream &OS) const; void dump() const; - SymExpr::symbol_iterator symbol_begin() const { - const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true); - if (SE) - return SE->symbol_begin(); - else - return SymExpr::symbol_iterator(); - } - - SymExpr::symbol_iterator symbol_end() const { - return SymExpr::symbol_end(); + llvm::iterator_range<SymExpr::symbol_iterator> symbols() const { + if (const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true)) + return SE->symbols(); + SymExpr::symbol_iterator end{}; + return llvm::make_range(end, end); } /// Try to get a reasonable type for the given value. @@ -221,16 +176,24 @@ inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { return os; } +namespace nonloc { +/// Sub-kinds for NonLoc values. +#define NONLOC_SVAL(Id, Parent) \ + inline constexpr auto Id##Kind = SVal::SValKind::NonLoc##Id##Kind; +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" +} // namespace nonloc + +namespace loc { +/// Sub-kinds for Loc values. +#define LOC_SVAL(Id, Parent) \ + inline constexpr auto Id##Kind = SVal::SValKind::Loc##Id##Kind; +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" +} // namespace loc + class UndefinedVal : public SVal { public: UndefinedVal() : SVal(UndefinedValKind) {} - -private: - friend class SVal; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == UndefinedValKind; - } + static bool classof(SVal V) { return V.getKind() == UndefinedValKind; } }; class DefinedOrUnknownSVal : public SVal { @@ -240,30 +203,18 @@ public: bool isUndef() const = delete; bool isValid() const = delete; -protected: - DefinedOrUnknownSVal() = default; - explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind) - : SVal(d, isLoc, ValKind) {} - explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr) : SVal(k, D) {} - -private: - friend class SVal; + static bool classof(SVal V) { return !V.isUndef(); } - static bool isKind(const SVal& V) { - return !V.isUndef(); - } +protected: + explicit DefinedOrUnknownSVal(SValKind Kind, const void *Data = nullptr) + : SVal(Kind, Data) {} }; class UnknownVal : public DefinedOrUnknownSVal { public: explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {} -private: - friend class SVal; - - static bool isKind(const SVal &V) { - return V.getBaseKind() == UnknownValKind; - } + static bool classof(SVal V) { return V.getKind() == UnknownValKind; } }; class DefinedSVal : public DefinedOrUnknownSVal { @@ -274,39 +225,24 @@ public: bool isUnknownOrUndef() const = delete; bool isValid() const = delete; -protected: - DefinedSVal() = default; - explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) - : DefinedOrUnknownSVal(d, isLoc, ValKind) {} - -private: - friend class SVal; + static bool classof(SVal V) { return !V.isUnknownOrUndef(); } - static bool isKind(const SVal& V) { - return !V.isUnknownOrUndef(); - } +protected: + explicit DefinedSVal(SValKind Kind, const void *Data) + : DefinedOrUnknownSVal(Kind, Data) {} }; /// Represents an SVal that is guaranteed to not be UnknownVal. class KnownSVal : public SVal { - friend class SVal; - - KnownSVal() = default; - - static bool isKind(const SVal &V) { - return !V.isUnknown(); - } - public: - KnownSVal(const DefinedSVal &V) : SVal(V) {} - KnownSVal(const UndefinedVal &V) : SVal(V) {} + /*implicit*/ KnownSVal(DefinedSVal V) : SVal(V) {} + /*implicit*/ KnownSVal(UndefinedVal V) : SVal(V) {} + static bool classof(SVal V) { return !V.isUnknown(); } }; class NonLoc : public DefinedSVal { protected: - NonLoc() = default; - explicit NonLoc(unsigned SubKind, const void *d) - : DefinedSVal(d, false, SubKind) {} + NonLoc(SValKind Kind, const void *Data) : DefinedSVal(Kind, Data) {} public: void dumpToStream(raw_ostream &Out) const; @@ -316,19 +252,14 @@ public: T->isAnyComplexType() || T->isVectorType(); } -private: - friend class SVal; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == NonLocKind; + static bool classof(SVal V) { + return BEGIN_NonLoc <= V.getKind() && V.getKind() <= END_NonLoc; } }; class Loc : public DefinedSVal { protected: - Loc() = default; - explicit Loc(unsigned SubKind, const void *D) - : DefinedSVal(const_cast<void *>(D), true, SubKind) {} + Loc(SValKind Kind, const void *Data) : DefinedSVal(Kind, Data) {} public: void dumpToStream(raw_ostream &Out) const; @@ -338,11 +269,8 @@ public: T->isReferenceType() || T->isNullPtrType(); } -private: - friend class SVal; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == LocKind; + static bool classof(SVal V) { + return BEGIN_Loc <= V.getKind() && V.getKind() <= END_Loc; } }; @@ -356,11 +284,12 @@ namespace nonloc { class SymbolVal : public NonLoc { public: SymbolVal() = delete; - SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) { - assert(sym); - assert(!Loc::isLocType(sym->getType())); + explicit SymbolVal(SymbolRef Sym) : NonLoc(SymbolValKind, Sym) { + assert(Sym); + assert(!Loc::isLocType(Sym->getType())); } + LLVM_ATTRIBUTE_RETURNS_NONNULL SymbolRef getSymbol() const { return (const SymExpr *) Data; } @@ -369,49 +298,17 @@ public: return !isa<SymbolData>(getSymbol()); } -private: - friend class SVal; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == NonLocKind && - V.getSubKind() == SymbolValKind; - } - - static bool isKind(const NonLoc& V) { - return V.getSubKind() == SymbolValKind; - } + static bool classof(SVal V) { return V.getKind() == SymbolValKind; } }; /// Value representing integer constant. class ConcreteInt : public NonLoc { public: - explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} - - const llvm::APSInt& getValue() const { - return *static_cast<const llvm::APSInt *>(Data); - } - - // Transfer functions for binary/unary operations on ConcreteInts. - SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op, - const ConcreteInt& R) const; - - ConcreteInt evalComplement(SValBuilder &svalBuilder) const; + explicit ConcreteInt(const llvm::APSInt &V) : NonLoc(ConcreteIntKind, &V) {} - ConcreteInt evalMinus(SValBuilder &svalBuilder) const; + const llvm::APSInt &getValue() const { return *castDataAs<llvm::APSInt>(); } -private: - friend class SVal; - - ConcreteInt() = default; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == NonLocKind && - V.getSubKind() == ConcreteIntKind; - } - - static bool isKind(const NonLoc& V) { - return V.getSubKind() == ConcreteIntKind; - } + static bool classof(SVal V) { return V.getKind() == ConcreteIntKind; } }; class LocAsInteger : public NonLoc { @@ -421,102 +318,63 @@ class LocAsInteger : public NonLoc { : NonLoc(LocAsIntegerKind, &data) { // We do not need to represent loc::ConcreteInt as LocAsInteger, // as it'd collapse into a nonloc::ConcreteInt instead. - assert(data.first.getBaseKind() == LocKind && - (data.first.getSubKind() == loc::MemRegionValKind || - data.first.getSubKind() == loc::GotoLabelKind)); + [[maybe_unused]] SValKind K = data.first.getKind(); + assert(K == loc::MemRegionValKind || K == loc::GotoLabelKind); } public: Loc getLoc() const { - const std::pair<SVal, uintptr_t> *D = - static_cast<const std::pair<SVal, uintptr_t> *>(Data); - return D->first.castAs<Loc>(); - } - - Loc getPersistentLoc() const { - const std::pair<SVal, uintptr_t> *D = - static_cast<const std::pair<SVal, uintptr_t> *>(Data); - const SVal& V = D->first; - return V.castAs<Loc>(); + return castDataAs<std::pair<SVal, uintptr_t>>()->first.castAs<Loc>(); } unsigned getNumBits() const { - const std::pair<SVal, uintptr_t> *D = - static_cast<const std::pair<SVal, uintptr_t> *>(Data); - return D->second; - } - -private: - friend class SVal; - - LocAsInteger() = default; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == NonLocKind && - V.getSubKind() == LocAsIntegerKind; + return castDataAs<std::pair<SVal, uintptr_t>>()->second; } - static bool isKind(const NonLoc& V) { - return V.getSubKind() == LocAsIntegerKind; - } + static bool classof(SVal V) { return V.getKind() == LocAsIntegerKind; } }; class CompoundVal : public NonLoc { friend class ento::SValBuilder; - explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} + explicit CompoundVal(const CompoundValData *D) : NonLoc(CompoundValKind, D) { + assert(D); + } public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const CompoundValData* getValue() const { - return static_cast<const CompoundValData *>(Data); + return castDataAs<CompoundValData>(); } using iterator = llvm::ImmutableList<SVal>::iterator; - iterator begin() const; iterator end() const; -private: - friend class SVal; - - CompoundVal() = default; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind; - } - - static bool isKind(const NonLoc& V) { - return V.getSubKind() == CompoundValKind; - } + static bool classof(SVal V) { return V.getKind() == CompoundValKind; } }; class LazyCompoundVal : public NonLoc { friend class ento::SValBuilder; explicit LazyCompoundVal(const LazyCompoundValData *D) - : NonLoc(LazyCompoundValKind, D) {} + : NonLoc(LazyCompoundValKind, D) { + assert(D); + } public: + LLVM_ATTRIBUTE_RETURNS_NONNULL const LazyCompoundValData *getCVData() const { - return static_cast<const LazyCompoundValData *>(Data); + return castDataAs<LazyCompoundValData>(); } + /// It might return null. const void *getStore() const; - const TypedValueRegion *getRegion() const; - -private: - friend class SVal; - - LazyCompoundVal() = default; - static bool isKind(const SVal& V) { - return V.getBaseKind() == NonLocKind && - V.getSubKind() == LazyCompoundValKind; - } + LLVM_ATTRIBUTE_RETURNS_NONNULL + const TypedValueRegion *getRegion() const; - static bool isKind(const NonLoc& V) { - return V.getSubKind() == LazyCompoundValKind; - } + static bool classof(SVal V) { return V.getKind() == LazyCompoundValKind; } }; /// Value representing pointer-to-member. @@ -554,21 +412,11 @@ public: iterator begin() const; iterator end() const; -private: - friend class SVal; + static bool classof(SVal V) { return V.getKind() == PointerToMemberKind; } - PointerToMember() = default; +private: explicit PointerToMember(const PTMDataType D) : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {} - - static bool isKind(const SVal& V) { - return V.getBaseKind() == NonLocKind && - V.getSubKind() == PointerToMemberKind; - } - - static bool isKind(const NonLoc& V) { - return V.getSubKind() == PointerToMemberKind; - } }; } // namespace nonloc @@ -585,36 +433,23 @@ public: assert(Label); } - const LabelDecl *getLabel() const { - return static_cast<const LabelDecl *>(Data); - } + const LabelDecl *getLabel() const { return castDataAs<LabelDecl>(); } -private: - friend class SVal; - - GotoLabel() = default; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind; - } - - static bool isKind(const Loc& V) { - return V.getSubKind() == GotoLabelKind; - } + static bool classof(SVal V) { return V.getKind() == GotoLabelKind; } }; class MemRegionVal : public Loc { public: - explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) { + explicit MemRegionVal(const MemRegion *r) : Loc(MemRegionValKind, r) { assert(r); } /// Get the underlining region. - const MemRegion *getRegion() const { - return static_cast<const MemRegion *>(Data); - } + LLVM_ATTRIBUTE_RETURNS_NONNULL + const MemRegion *getRegion() const { return castDataAs<MemRegion>(); } /// Get the underlining region and strip casts. + LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion* stripCasts(bool StripBaseCasts = true) const; template <typename REGION> @@ -630,52 +465,44 @@ public: return getRegion() != R.getRegion(); } -private: - friend class SVal; - - MemRegionVal() = default; - - static bool isKind(const SVal& V) { - return V.getBaseKind() == LocKind && - V.getSubKind() == MemRegionValKind; - } - - static bool isKind(const Loc& V) { - return V.getSubKind() == MemRegionValKind; - } + static bool classof(SVal V) { return V.getKind() == MemRegionValKind; } }; class ConcreteInt : public Loc { public: - explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} - - const llvm::APSInt &getValue() const { - return *static_cast<const llvm::APSInt *>(Data); - } - - // Transfer functions for binary/unary operations on ConcreteInts. - SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, - const ConcreteInt& R) const; - -private: - friend class SVal; + explicit ConcreteInt(const llvm::APSInt &V) : Loc(ConcreteIntKind, &V) {} - ConcreteInt() = default; + const llvm::APSInt &getValue() const { return *castDataAs<llvm::APSInt>(); } - static bool isKind(const SVal& V) { - return V.getBaseKind() == LocKind && - V.getSubKind() == ConcreteIntKind; - } - - static bool isKind(const Loc& V) { - return V.getSubKind() == ConcreteIntKind; - } + static bool classof(SVal V) { return V.getKind() == ConcreteIntKind; } }; } // namespace loc - } // namespace ento - } // namespace clang +namespace llvm { +template <typename To, typename From> +struct CastInfo< + To, From, + std::enable_if_t<std::is_base_of<::clang::ento::SVal, From>::value>> + : public CastIsPossible<To, ::clang::ento::SVal> { + using Self = CastInfo< + To, From, + std::enable_if_t<std::is_base_of<::clang::ento::SVal, From>::value>>; + static bool isPossible(const From &V) { + return To::classof(*static_cast<const ::clang::ento::SVal *>(&V)); + } + static std::optional<To> castFailed() { return std::optional<To>{}; } + static To doCast(const From &f) { + return *static_cast<const To *>(cast<::clang::ento::SVal>(&f)); + } + static std::optional<To> doCastIfPossible(const From &f) { + if (!Self::isPossible(f)) + return Self::castFailed(); + return doCast(f); + } +}; +} // namespace llvm + #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h index 87e927f5b480..725140e073c6 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h @@ -34,16 +34,6 @@ public: // Implementation for interface from ConstraintManager. //===------------------------------------------------------------------===// - /// Ensures that the DefinedSVal conditional is expressed as a NonLoc by - /// creating boolean casts to handle Loc's. - ProgramStateRef assume(ProgramStateRef State, DefinedSVal Cond, - bool Assumption) override; - - ProgramStateRef assumeInclusiveRange(ProgramStateRef State, NonLoc Value, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool InRange) override; - protected: //===------------------------------------------------------------------===// // Interface that subclasses must implement. @@ -74,6 +64,17 @@ protected: // Internal implementation. //===------------------------------------------------------------------===// + /// Ensures that the DefinedSVal conditional is expressed as a NonLoc by + /// creating boolean casts to handle Loc's. + ProgramStateRef assumeInternal(ProgramStateRef State, DefinedSVal Cond, + bool Assumption) override; + + ProgramStateRef assumeInclusiveRangeInternal(ProgramStateRef State, + NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InRange) override; + SValBuilder &getSValBuilder() const { return SVB; } BasicValueFactory &getBasicVals() const { return SVB.getBasicValueFactory(); } SymbolManager &getSymbolManager() const { return SVB.getSymbolManager(); } diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h index d2461705d128..fac0c04ae2ca 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h @@ -23,11 +23,11 @@ #include "clang/Basic/LLVM.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallVector.h" #include <cassert> #include <cstdint> #include <memory> +#include <optional> namespace clang { @@ -83,7 +83,8 @@ public: /// \param[in] R The region to find the default binding for. /// \return The default value bound to the region in the store, if a default /// binding exists. - virtual Optional<SVal> getDefaultBinding(Store store, const MemRegion *R) = 0; + virtual std::optional<SVal> getDefaultBinding(Store store, + const MemRegion *R) = 0; /// Return the default value bound to a LazyCompoundVal. The default binding /// is used to represent the value of any fields or elements within the @@ -93,7 +94,7 @@ public: /// \param[in] lcv The lazy compound value. /// \return The default value bound to the LazyCompoundVal \c lcv, if a /// default binding exists. - Optional<SVal> getDefaultBinding(nonloc::LazyCompoundVal lcv) { + std::optional<SVal> getDefaultBinding(nonloc::LazyCompoundVal lcv) { return getDefaultBinding(lcv.getStore(), lcv.getRegion()); } @@ -172,17 +173,17 @@ public: /// dynamic_cast. /// - 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. - SVal attemptDownCast(SVal Base, QualType DerivedPtrType, bool &Failed); + /// The function returns an optional with SVal representing the derived class + /// in case of a successful cast and `std::nullopt` otherwise. + std::optional<SVal> evalBaseToDerived(SVal Base, QualType DerivedPtrType); const ElementRegion *GetElementZeroRegion(const SubRegion *R, QualType T); /// castRegion - Used by ExprEngine::VisitCast to handle casts from /// a MemRegion* to a specific location type. 'R' is the region being /// casted and 'CastToTy' the result type of the cast. - Optional<const MemRegion *> castRegion(const MemRegion *region, - QualType CastToTy); + std::optional<const MemRegion *> castRegion(const MemRegion *region, + QualType CastToTy); virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, SymbolReaper &SymReaper) = 0; @@ -316,8 +317,6 @@ inline StoreRef &StoreRef::operator=(StoreRef const &newStore) { // FIXME: Do we need to pass ProgramStateManager anymore? std::unique_ptr<StoreManager> CreateRegionStoreManager(ProgramStateManager &StMgr); -std::unique_ptr<StoreManager> -CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr); } // namespace ento diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h index 2f4ac6ba5f97..862a30c0e736 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h @@ -17,6 +17,7 @@ #include "clang/Basic/LLVM.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator_range.h" #include <cassert> namespace clang { @@ -83,8 +84,9 @@ public: bool operator!=(const symbol_iterator &X) const; }; - symbol_iterator symbol_begin() const { return symbol_iterator(this); } - static symbol_iterator symbol_end() { return symbol_iterator(); } + llvm::iterator_range<symbol_iterator> symbols() const { + return llvm::make_range(symbol_iterator(this), symbol_iterator()); + } virtual unsigned computeComplexity() const = 0; @@ -98,6 +100,7 @@ public: /// the beginning of the analysis, and SymbolDerived which denotes the value /// of a certain memory region after its super region (a memory space or /// a larger record region) is default-bound with a certain symbol. + /// It might return null. virtual const MemRegion *getOriginRegion() const { return nullptr; } }; diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h index c71cb88f5574..3b64d38ee2b2 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -24,6 +24,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" #include <cassert> @@ -48,6 +49,7 @@ public: assert(isValidTypeForSymbol(r->getValueType())); } + LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion* getRegion() const { return R; } static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { @@ -95,8 +97,10 @@ public: assert(isValidTypeForSymbol(t)); } + /// It might return null. const Stmt *getStmt() const { return S; } unsigned getCount() const { return Count; } + /// It might return null. const void *getTag() const { return SymbolTag; } QualType getType() const override; @@ -140,7 +144,9 @@ public: assert(isValidTypeForSymbol(r->getValueType())); } + LLVM_ATTRIBUTE_RETURNS_NONNULL SymbolRef getParentSymbol() const { return parentSymbol; } + LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion *getRegion() const { return R; } QualType getType() const override; @@ -179,6 +185,7 @@ public: assert(r); } + LLVM_ATTRIBUTE_RETURNS_NONNULL const SubRegion *getRegion() const { return R; } QualType getType() const override; @@ -226,29 +233,37 @@ public: assert(tag); } - const MemRegion *getRegion() const { return R; } - const Stmt *getStmt() const { return S; } - const LocationContext *getLocationContext() const { return LCtx; } - unsigned getCount() const { return Count; } - const void *getTag() const { return Tag; } + LLVM_ATTRIBUTE_RETURNS_NONNULL + const MemRegion *getRegion() const { return R; } - QualType getType() const override; + LLVM_ATTRIBUTE_RETURNS_NONNULL + const Stmt *getStmt() const { return S; } - StringRef getKindStr() const override; + LLVM_ATTRIBUTE_RETURNS_NONNULL + const LocationContext *getLocationContext() const { return LCtx; } - void dumpToStream(raw_ostream &os) const override; + unsigned getCount() const { return Count; } - static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, - const Stmt *S, QualType T, const LocationContext *LCtx, - unsigned Count, const void *Tag) { - profile.AddInteger((unsigned) SymbolMetadataKind); - profile.AddPointer(R); - profile.AddPointer(S); - profile.Add(T); - profile.AddPointer(LCtx); - profile.AddInteger(Count); - profile.AddPointer(Tag); - } + LLVM_ATTRIBUTE_RETURNS_NONNULL + const void *getTag() const { return Tag; } + + QualType getType() const override; + + StringRef getKindStr() const override; + + void dumpToStream(raw_ostream &os) const override; + + static void Profile(llvm::FoldingSetNodeID &profile, const MemRegion *R, + const Stmt *S, QualType T, const LocationContext *LCtx, + unsigned Count, const void *Tag) { + profile.AddInteger((unsigned)SymbolMetadataKind); + profile.AddPointer(R); + profile.AddPointer(S); + profile.Add(T); + profile.AddPointer(LCtx); + profile.AddInteger(Count); + profile.AddPointer(Tag); + } void Profile(llvm::FoldingSetNodeID& profile) override { Profile(profile, R, S, T, LCtx, Count, Tag); @@ -287,6 +302,7 @@ public: QualType getType() const override { return ToTy; } + LLVM_ATTRIBUTE_RETURNS_NONNULL const SymExpr *getOperand() const { return Operand; } void dumpToStream(raw_ostream &os) const override; @@ -309,6 +325,55 @@ public: } }; +/// Represents a symbolic expression involving a unary operator. +class UnarySymExpr : public SymExpr { + const SymExpr *Operand; + UnaryOperator::Opcode Op; + QualType T; + +public: + UnarySymExpr(const SymExpr *In, UnaryOperator::Opcode Op, QualType T) + : SymExpr(UnarySymExprKind), Operand(In), Op(Op), T(T) { + // Note, some unary operators are modeled as a binary operator. E.g. ++x is + // modeled as x + 1. + assert((Op == UO_Minus || Op == UO_Not) && "non-supported unary expression"); + // Unary expressions are results of arithmetic. Pointer arithmetic is not + // handled by unary expressions, but it is instead handled by applying + // sub-regions to regions. + assert(isValidTypeForSymbol(T) && "non-valid type for unary symbol"); + assert(!Loc::isLocType(T) && "unary symbol should be nonloc"); + } + + unsigned computeComplexity() const override { + if (Complexity == 0) + Complexity = 1 + Operand->computeComplexity(); + return Complexity; + } + + const SymExpr *getOperand() const { return Operand; } + UnaryOperator::Opcode getOpcode() const { return Op; } + QualType getType() const override { return T; } + + void dumpToStream(raw_ostream &os) const override; + + static void Profile(llvm::FoldingSetNodeID &ID, const SymExpr *In, + UnaryOperator::Opcode Op, QualType T) { + ID.AddInteger((unsigned)UnarySymExprKind); + ID.AddPointer(In); + ID.AddInteger(Op); + ID.Add(T); + } + + void Profile(llvm::FoldingSetNodeID &ID) override { + Profile(ID, Operand, Op, T); + } + + // Implement isa<T> support. + static bool classof(const SymExpr *SE) { + return SE->getKind() == UnarySymExprKind; + } +}; + /// Represents a symbolic expression involving a binary operator class BinarySymExpr : public SymExpr { BinaryOperator::Opcode Op; @@ -486,6 +551,9 @@ public: const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType t); + const UnarySymExpr *getUnarySymExpr(const SymExpr *operand, + UnaryOperator::Opcode op, QualType t); + QualType getType(const SymExpr *SE) const { return SE->getType(); } @@ -515,7 +583,12 @@ class SymbolReaper { SymbolMapTy TheLiving; SymbolSetTy MetadataInUse; - RegionSetTy RegionRoots; + RegionSetTy LiveRegionRoots; + // The lazily copied regions are locations for which a program + // can access the value stored at that location, but not its address. + // These regions are constructed as a set of regions referred to by + // lazyCompoundVal. + RegionSetTy LazilyCopiedRegionRoots; const StackFrameContext *LCtx; const Stmt *Loc; @@ -535,6 +608,7 @@ public: SymbolManager &symmgr, StoreManager &storeMgr) : LCtx(Ctx), Loc(s), SymMgr(symmgr), reapedStore(nullptr, storeMgr) {} + /// It might return null. const LocationContext *getLocationContext() const { return LCtx; } bool isLive(SymbolRef sym); @@ -558,10 +632,9 @@ public: /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. void markInUse(SymbolRef sym); - using region_iterator = RegionSetTy::const_iterator; - - region_iterator region_begin() const { return RegionRoots.begin(); } - region_iterator region_end() const { return RegionRoots.end(); } + llvm::iterator_range<RegionSetTy::const_iterator> regions() const { + return LiveRegionRoots; + } /// Returns whether or not a symbol has been confirmed dead. /// @@ -572,6 +645,7 @@ public: } void markLive(const MemRegion *region); + void markLazilyCopied(const MemRegion *region); void markElementIndicesLive(const MemRegion *region); /// Set to the value of the symbolic store after @@ -579,6 +653,12 @@ public: void setReapedStore(StoreRef st) { reapedStore = st; } private: + bool isLazilyCopiedRegion(const MemRegion *region) const; + // A readable region is a region that live or lazily copied. + // Any symbols that refer to values in regions are alive if the region + // is readable. + bool isReadableRegion(const MemRegion *region); + /// Mark the symbols dependent on the input symbol as live. void markDependentsLive(SymbolRef sym); }; @@ -592,6 +672,11 @@ public: SymbolVisitor(const SymbolVisitor &) = default; SymbolVisitor(SymbolVisitor &&) {} + // The copy and move assignment operator is defined as deleted pending further + // motivation. + SymbolVisitor &operator=(const SymbolVisitor &) = delete; + SymbolVisitor &operator=(SymbolVisitor &&) = delete; + /// A visitor method invoked by ProgramStateManager::scanReachableSymbols. /// /// The method returns \c true if symbols should continue be scanned and \c diff --git a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Symbols.def b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Symbols.def index 7163a16263ab..b93f8e250155 100644 --- a/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Symbols.def +++ b/contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Symbols.def @@ -33,6 +33,8 @@ #define SYMBOL_RANGE(Id, First, Last) #endif +SYMBOL(UnarySymExpr, SymExpr) + ABSTRACT_SYMBOL(BinarySymExpr, SymExpr) SYMBOL(IntSymExpr, BinarySymExpr) SYMBOL(SymIntExpr, BinarySymExpr) |