| //== SVals.h - Abstract Values for Static Analysis ---------*- C++ -*--==// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines SVal, Loc, and NonLoc, classes that represent |
| // abstract r-values for use with path-sensitive value tracking. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H |
| #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H |
| |
| #include "clang/AST/Expr.h" |
| #include "clang/Basic/LLVM.h" |
| #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" |
| #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" |
| #include "llvm/ADT/FoldingSet.h" |
| #include "llvm/ADT/ImmutableList.h" |
| |
| //==------------------------------------------------------------------------==// |
| // Base SVal types. |
| //==------------------------------------------------------------------------==// |
| |
| namespace clang { |
| |
| namespace ento { |
| |
| class CompoundValData; |
| class LazyCompoundValData; |
| class PointerToMemberData; |
| class ProgramState; |
| class BasicValueFactory; |
| class MemRegion; |
| class TypedValueRegion; |
| class MemRegionManager; |
| class ProgramStateManager; |
| class SValBuilder; |
| |
| namespace nonloc { |
| /// Sub-kinds for NonLoc values. |
| enum Kind { |
| #define NONLOC_SVAL(Id, Parent) Id ## Kind, |
| #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" |
| }; |
| } |
| |
| namespace loc { |
| /// Sub-kinds for Loc values. |
| enum Kind { |
| #define LOC_SVAL(Id, Parent) Id ## Kind, |
| #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" |
| }; |
| } |
| |
| /// 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, |
| #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" |
| }; |
| enum { BaseBits = 2, BaseMask = 0x3 }; |
| |
| protected: |
| const void *Data; |
| |
| /// The lowest 2 bits are a BaseKind (0 -- 3). |
| /// The higher bits are an unsigned "kind" value. |
| unsigned Kind; |
| |
| explicit SVal(const void *d, bool isLoc, unsigned ValKind) |
| : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} |
| |
| explicit SVal(BaseKind k, const void *D = nullptr) |
| : Data(D), Kind(k) {} |
| |
| public: |
| explicit SVal() : Data(nullptr), Kind(0) {} |
| |
| /// \brief 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); |
| } |
| |
| /// \brief Convert to the specified SVal type, returning None 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); |
| } |
| |
| /// BufferTy - A temporary buffer to hold a set of SVals. |
| typedef SmallVector<SVal,5> BufferTy; |
| |
| inline unsigned getRawKind() const { return Kind; } |
| inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); } |
| inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; } |
| |
| // This method is required for using SVal in a FoldingSetNode. It |
| // extracts a unique signature for this SVal object. |
| inline void Profile(llvm::FoldingSetNodeID& ID) const { |
| ID.AddInteger((unsigned) getRawKind()); |
| ID.AddPointer(Data); |
| } |
| |
| inline bool operator==(const SVal& R) const { |
| return getRawKind() == R.getRawKind() && Data == R.Data; |
| } |
| |
| inline bool operator!=(const SVal& R) const { |
| return !(*this == R); |
| } |
| |
| inline bool isUnknown() const { |
| return getRawKind() == UnknownValKind; |
| } |
| |
| inline bool isUndef() const { |
| return getRawKind() == UndefinedValKind; |
| } |
| |
| inline bool isUnknownOrUndef() const { |
| return getRawKind() <= UnknownValKind; |
| } |
| |
| inline bool isValid() const { |
| return getRawKind() > UnknownValKind; |
| } |
| |
| bool isConstant() const; |
| |
| bool isConstant(int I) const; |
| |
| bool isZeroConstant() const; |
| |
| /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true; |
| bool hasConjuredSymbol() const; |
| |
| /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a |
| /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. |
| /// Otherwise return 0. |
| const FunctionDecl *getAsFunctionDecl() const; |
| |
| /// \brief If this SVal is a location and wraps a symbol, return that |
| /// SymbolRef. Otherwise return 0. |
| /// |
| /// Casts are ignored during lookup. |
| /// \param IncludeBaseRegions The boolean that controls whether the search |
| /// should continue to the base regions if the region is not symbolic. |
| SymbolRef getAsLocSymbol(bool IncludeBaseRegions = false) const; |
| |
| /// Get the symbol in the SVal or its base region. |
| SymbolRef getLocSymbolInBase() const; |
| |
| /// \brief If this SVal wraps a symbol return that SymbolRef. |
| /// Otherwise, return 0. |
| /// |
| /// Casts are ignored during lookup. |
| /// \param IncludeBaseRegions The boolean that controls whether the search |
| /// should continue to the base regions if the region is not symbolic. |
| SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const; |
| |
| /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then |
| /// return that expression. Otherwise return NULL. |
| const SymExpr *getAsSymbolicExpression() const; |
| |
| const SymExpr* getAsSymExpr() const; |
| |
| const MemRegion *getAsRegion() const; |
| |
| void dumpToStream(raw_ostream &OS) const; |
| void dump() const; |
| |
| SymExpr::symbol_iterator symbol_begin() const { |
| const SymExpr *SE = getAsSymbolicExpression(); |
| if (SE) |
| return SE->symbol_begin(); |
| else |
| return SymExpr::symbol_iterator(); |
| } |
| |
| SymExpr::symbol_iterator symbol_end() const { |
| return SymExpr::symbol_end(); |
| } |
| }; |
| |
| |
| class UndefinedVal : public SVal { |
| public: |
| UndefinedVal() : SVal(UndefinedValKind) {} |
| |
| private: |
| friend class SVal; |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == UndefinedValKind; |
| } |
| }; |
| |
| class DefinedOrUnknownSVal : public SVal { |
| private: |
| // We want calling these methods to be a compiler error since they are |
| // tautologically false. |
| bool isUndef() const = delete; |
| bool isValid() const = delete; |
| |
| protected: |
| DefinedOrUnknownSVal() {} |
| 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 isKind(const SVal& V) { |
| return !V.isUndef(); |
| } |
| }; |
| |
| class UnknownVal : public DefinedOrUnknownSVal { |
| public: |
| explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {} |
| |
| private: |
| friend class SVal; |
| static bool isKind(const SVal &V) { |
| return V.getBaseKind() == UnknownValKind; |
| } |
| }; |
| |
| class DefinedSVal : public DefinedOrUnknownSVal { |
| private: |
| // We want calling these methods to be a compiler error since they are |
| // tautologically true/false. |
| bool isUnknown() const = delete; |
| bool isUnknownOrUndef() const = delete; |
| bool isValid() const = delete; |
| protected: |
| DefinedSVal() {} |
| explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) |
| : DefinedOrUnknownSVal(d, isLoc, ValKind) {} |
| private: |
| friend class SVal; |
| static bool isKind(const SVal& V) { |
| return !V.isUnknownOrUndef(); |
| } |
| }; |
| |
| |
| /// \brief Represents an SVal that is guaranteed to not be UnknownVal. |
| class KnownSVal : public SVal { |
| KnownSVal() {} |
| friend class SVal; |
| static bool isKind(const SVal &V) { |
| return !V.isUnknown(); |
| } |
| public: |
| KnownSVal(const DefinedSVal &V) : SVal(V) {} |
| KnownSVal(const UndefinedVal &V) : SVal(V) {} |
| }; |
| |
| class NonLoc : public DefinedSVal { |
| protected: |
| NonLoc() {} |
| explicit NonLoc(unsigned SubKind, const void *d) |
| : DefinedSVal(d, false, SubKind) {} |
| |
| public: |
| void dumpToStream(raw_ostream &Out) const; |
| |
| static inline bool isCompoundType(QualType T) { |
| return T->isArrayType() || T->isRecordType() || |
| T->isComplexType() || T->isVectorType(); |
| } |
| |
| private: |
| friend class SVal; |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == NonLocKind; |
| } |
| }; |
| |
| class Loc : public DefinedSVal { |
| protected: |
| Loc() {} |
| explicit Loc(unsigned SubKind, const void *D) |
| : DefinedSVal(const_cast<void*>(D), true, SubKind) {} |
| |
| public: |
| void dumpToStream(raw_ostream &Out) const; |
| |
| static inline bool isLocType(QualType T) { |
| return T->isAnyPointerType() || T->isBlockPointerType() || |
| T->isReferenceType() || T->isNullPtrType(); |
| } |
| |
| private: |
| friend class SVal; |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == LocKind; |
| } |
| }; |
| |
| //==------------------------------------------------------------------------==// |
| // Subclasses of NonLoc. |
| //==------------------------------------------------------------------------==// |
| |
| namespace nonloc { |
| |
| /// \brief Represents symbolic expression. |
| class SymbolVal : public NonLoc { |
| public: |
| SymbolVal() = delete; |
| SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) { assert(sym); } |
| |
| SymbolRef getSymbol() const { |
| return (const SymExpr*) Data; |
| } |
| |
| bool isExpression() const { |
| 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; |
| } |
| }; |
| |
| /// \brief 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; |
| |
| ConcreteInt evalMinus(SValBuilder &svalBuilder) const; |
| |
| private: |
| friend class SVal; |
| ConcreteInt() {} |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == NonLocKind && |
| V.getSubKind() == ConcreteIntKind; |
| } |
| |
| static bool isKind(const NonLoc& V) { |
| return V.getSubKind() == ConcreteIntKind; |
| } |
| }; |
| |
| class LocAsInteger : public NonLoc { |
| friend class ento::SValBuilder; |
| |
| explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data) |
| : NonLoc(LocAsIntegerKind, &data) { |
| // 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)); |
| } |
| |
| 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>(); |
| } |
| |
| 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() {} |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == NonLocKind && |
| V.getSubKind() == LocAsIntegerKind; |
| } |
| |
| static bool isKind(const NonLoc& V) { |
| return V.getSubKind() == LocAsIntegerKind; |
| } |
| }; |
| |
| class CompoundVal : public NonLoc { |
| friend class ento::SValBuilder; |
| |
| explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} |
| |
| public: |
| const CompoundValData* getValue() const { |
| return static_cast<const CompoundValData*>(Data); |
| } |
| |
| typedef llvm::ImmutableList<SVal>::iterator iterator; |
| iterator begin() const; |
| iterator end() const; |
| |
| private: |
| friend class SVal; |
| CompoundVal() {} |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind; |
| } |
| |
| static bool isKind(const NonLoc& V) { |
| return V.getSubKind() == CompoundValKind; |
| } |
| }; |
| |
| class LazyCompoundVal : public NonLoc { |
| friend class ento::SValBuilder; |
| |
| explicit LazyCompoundVal(const LazyCompoundValData *D) |
| : NonLoc(LazyCompoundValKind, D) {} |
| public: |
| const LazyCompoundValData *getCVData() const { |
| return static_cast<const LazyCompoundValData*>(Data); |
| } |
| const void *getStore() const; |
| const TypedValueRegion *getRegion() const; |
| |
| private: |
| friend class SVal; |
| LazyCompoundVal() {} |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == NonLocKind && |
| V.getSubKind() == LazyCompoundValKind; |
| } |
| static bool isKind(const NonLoc& V) { |
| return V.getSubKind() == LazyCompoundValKind; |
| } |
| }; |
| |
| /// \brief Value representing pointer-to-member. |
| /// |
| /// This value is qualified as NonLoc because neither loading nor storing |
| /// operations are aplied to it. Instead, the analyzer uses the L-value coming |
| /// from pointer-to-member applied to an object. |
| /// This SVal is represented by a DeclaratorDecl which can be a member function |
| /// pointer or a member data pointer and a list of CXXBaseSpecifiers. This list |
| /// is required to accumulate the pointer-to-member cast history to figure out |
| /// the correct subobject field. |
| class PointerToMember : public NonLoc { |
| friend class ento::SValBuilder; |
| |
| public: |
| typedef llvm::PointerUnion<const DeclaratorDecl *, |
| const PointerToMemberData *> PTMDataType; |
| const PTMDataType getPTMData() const { |
| return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data)); |
| } |
| bool isNullMemberPointer() const { |
| return getPTMData().isNull(); |
| } |
| const DeclaratorDecl *getDecl() const; |
| template<typename AdjustedDecl> |
| const AdjustedDecl* getDeclAs() const { |
| return dyn_cast_or_null<AdjustedDecl>(getDecl()); |
| } |
| typedef llvm::ImmutableList<const CXXBaseSpecifier *>::iterator iterator; |
| iterator begin() const; |
| iterator end() const; |
| |
| private: |
| explicit PointerToMember(const PTMDataType D) |
| : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {} |
| friend class SVal; |
| PointerToMember() {} |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == NonLocKind && |
| V.getSubKind() == PointerToMemberKind; |
| } |
| |
| static bool isKind(const NonLoc& V) { |
| return V.getSubKind() == PointerToMemberKind; |
| } |
| }; |
| |
| } // end namespace ento::nonloc |
| |
| //==------------------------------------------------------------------------==// |
| // Subclasses of Loc. |
| //==------------------------------------------------------------------------==// |
| |
| namespace loc { |
| |
| class GotoLabel : public Loc { |
| public: |
| explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) { |
| assert(Label); |
| } |
| |
| const LabelDecl *getLabel() const { |
| return static_cast<const LabelDecl*>(Data); |
| } |
| |
| private: |
| friend class SVal; |
| GotoLabel() {} |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind; |
| } |
| |
| static bool isKind(const Loc& V) { |
| return V.getSubKind() == GotoLabelKind; |
| } |
| }; |
| |
| |
| class MemRegionVal : public Loc { |
| public: |
| explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) { |
| assert(r); |
| } |
| |
| /// \brief Get the underlining region. |
| const MemRegion* getRegion() const { |
| return static_cast<const MemRegion*>(Data); |
| } |
| |
| /// \brief Get the underlining region and strip casts. |
| const MemRegion* stripCasts(bool StripBaseCasts = true) const; |
| |
| template <typename REGION> |
| const REGION* getRegionAs() const { |
| return dyn_cast<REGION>(getRegion()); |
| } |
| |
| inline bool operator==(const MemRegionVal& R) const { |
| return getRegion() == R.getRegion(); |
| } |
| |
| inline bool operator!=(const MemRegionVal& R) const { |
| return getRegion() != R.getRegion(); |
| } |
| |
| private: |
| friend class SVal; |
| MemRegionVal() {} |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == LocKind && |
| V.getSubKind() == MemRegionValKind; |
| } |
| |
| static bool isKind(const Loc& V) { |
| return V.getSubKind() == 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; |
| ConcreteInt() {} |
| static bool isKind(const SVal& V) { |
| return V.getBaseKind() == LocKind && |
| V.getSubKind() == ConcreteIntKind; |
| } |
| |
| static bool isKind(const Loc& V) { |
| return V.getSubKind() == ConcreteIntKind; |
| } |
| }; |
| |
| } // end ento::loc namespace |
| |
| } // end ento namespace |
| |
| } // end clang namespace |
| |
| namespace llvm { |
| static inline raw_ostream &operator<<(raw_ostream &os, |
| clang::ento::SVal V) { |
| V.dumpToStream(os); |
| return os; |
| } |
| |
| template <typename T> struct isPodLike; |
| template <> struct isPodLike<clang::ento::SVal> { |
| static const bool value = true; |
| }; |
| |
| } // end llvm namespace |
| |
| #endif |