1 //===- SVals.h - Abstract Values for Static Analysis ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines SVal, Loc, and NonLoc, classes that represent
11 // abstract r-values for use with path-sensitive value tracking.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/Type.h"
20 #include "clang/Basic/LLVM.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
22 #include "llvm/ADT/FoldingSet.h"
23 #include "llvm/ADT/ImmutableList.h"
24 #include "llvm/ADT/None.h"
25 #include "llvm/ADT/Optional.h"
26 #include "llvm/ADT/PointerUnion.h"
27 #include "llvm/Support/Casting.h"
32 //==------------------------------------------------------------------------==//
34 //==------------------------------------------------------------------------==//
38 class CXXBaseSpecifier;
45 class BasicValueFactory;
46 class CompoundValData;
47 class LazyCompoundValData;
49 class PointerToMemberData;
51 class TypedValueRegion;
55 /// Sub-kinds for NonLoc values.
57 #define NONLOC_SVAL(Id, Parent) Id ## Kind,
58 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
65 /// Sub-kinds for Loc values.
67 #define LOC_SVAL(Id, Parent) Id ## Kind,
68 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
73 /// SVal - This represents a symbolic expression, which can be either
74 /// an L-value or an R-value.
79 // The enumerators must be representable using 2 bits.
80 #define BASIC_SVAL(Id, Parent) Id ## Kind,
81 #define ABSTRACT_SVAL_WITH_KIND(Id, Parent) Id ## Kind,
82 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
84 enum { BaseBits = 2, BaseMask = 0x3 };
87 const void *Data = nullptr;
89 /// The lowest 2 bits are a BaseKind (0 -- 3).
90 /// The higher bits are an unsigned "kind" value.
93 explicit SVal(const void *d, bool isLoc, unsigned ValKind)
94 : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
96 explicit SVal(BaseKind k, const void *D = nullptr) : Data(D), Kind(k) {}
99 explicit SVal() = default;
101 /// Convert to the specified SVal type, asserting that this SVal is of
102 /// the desired type.
105 assert(T::isKind(*this));
106 return *static_cast<const T *>(this);
109 /// Convert to the specified SVal type, returning None if this SVal is
110 /// not of the desired type.
112 Optional<T> getAs() const {
113 if (!T::isKind(*this))
115 return *static_cast<const T *>(this);
118 unsigned getRawKind() const { return Kind; }
119 BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
120 unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
122 // This method is required for using SVal in a FoldingSetNode. It
123 // extracts a unique signature for this SVal object.
124 void Profile(llvm::FoldingSetNodeID &ID) const {
125 ID.AddInteger((unsigned) getRawKind());
129 bool operator==(const SVal &R) const {
130 return getRawKind() == R.getRawKind() && Data == R.Data;
133 bool operator!=(const SVal &R) const {
134 return !(*this == R);
137 bool isUnknown() const {
138 return getRawKind() == UnknownValKind;
141 bool isUndef() const {
142 return getRawKind() == UndefinedValKind;
145 bool isUnknownOrUndef() const {
146 return getRawKind() <= UnknownValKind;
149 bool isValid() const {
150 return getRawKind() > UnknownValKind;
153 bool isConstant() const;
155 bool isConstant(int I) const;
157 bool isZeroConstant() const;
159 /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true;
160 bool hasConjuredSymbol() const;
162 /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a
163 /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl.
164 /// Otherwise return 0.
165 const FunctionDecl *getAsFunctionDecl() const;
167 /// If this SVal is a location and wraps a symbol, return that
168 /// SymbolRef. Otherwise return 0.
170 /// Casts are ignored during lookup.
171 /// \param IncludeBaseRegions The boolean that controls whether the search
172 /// should continue to the base regions if the region is not symbolic.
173 SymbolRef getAsLocSymbol(bool IncludeBaseRegions = false) const;
175 /// Get the symbol in the SVal or its base region.
176 SymbolRef getLocSymbolInBase() const;
178 /// If this SVal wraps a symbol return that SymbolRef.
179 /// Otherwise, return 0.
181 /// Casts are ignored during lookup.
182 /// \param IncludeBaseRegions The boolean that controls whether the search
183 /// should continue to the base regions if the region is not symbolic.
184 SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const;
186 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
187 /// return that expression. Otherwise return NULL.
188 const SymExpr *getAsSymbolicExpression() const;
190 const SymExpr *getAsSymExpr() const;
192 const MemRegion *getAsRegion() const;
194 void dumpToStream(raw_ostream &OS) const;
197 SymExpr::symbol_iterator symbol_begin() const {
198 const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true);
200 return SE->symbol_begin();
202 return SymExpr::symbol_iterator();
205 SymExpr::symbol_iterator symbol_end() const {
206 return SymExpr::symbol_end();
210 inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) {
215 class UndefinedVal : public SVal {
217 UndefinedVal() : SVal(UndefinedValKind) {}
222 static bool isKind(const SVal& V) {
223 return V.getBaseKind() == UndefinedValKind;
227 class DefinedOrUnknownSVal : public SVal {
229 // We want calling these methods to be a compiler error since they are
230 // tautologically false.
231 bool isUndef() const = delete;
232 bool isValid() const = delete;
235 DefinedOrUnknownSVal() = default;
236 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
237 : SVal(d, isLoc, ValKind) {}
238 explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr) : SVal(k, D) {}
243 static bool isKind(const SVal& V) {
248 class UnknownVal : public DefinedOrUnknownSVal {
250 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {}
255 static bool isKind(const SVal &V) {
256 return V.getBaseKind() == UnknownValKind;
260 class DefinedSVal : public DefinedOrUnknownSVal {
262 // We want calling these methods to be a compiler error since they are
263 // tautologically true/false.
264 bool isUnknown() const = delete;
265 bool isUnknownOrUndef() const = delete;
266 bool isValid() const = delete;
269 DefinedSVal() = default;
270 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
271 : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
276 static bool isKind(const SVal& V) {
277 return !V.isUnknownOrUndef();
281 /// Represents an SVal that is guaranteed to not be UnknownVal.
282 class KnownSVal : public SVal {
285 KnownSVal() = default;
287 static bool isKind(const SVal &V) {
288 return !V.isUnknown();
292 KnownSVal(const DefinedSVal &V) : SVal(V) {}
293 KnownSVal(const UndefinedVal &V) : SVal(V) {}
296 class NonLoc : public DefinedSVal {
299 explicit NonLoc(unsigned SubKind, const void *d)
300 : DefinedSVal(d, false, SubKind) {}
303 void dumpToStream(raw_ostream &Out) const;
305 static bool isCompoundType(QualType T) {
306 return T->isArrayType() || T->isRecordType() ||
307 T->isComplexType() || T->isVectorType();
313 static bool isKind(const SVal& V) {
314 return V.getBaseKind() == NonLocKind;
318 class Loc : public DefinedSVal {
321 explicit Loc(unsigned SubKind, const void *D)
322 : DefinedSVal(const_cast<void *>(D), true, SubKind) {}
325 void dumpToStream(raw_ostream &Out) const;
327 static bool isLocType(QualType T) {
328 return T->isAnyPointerType() || T->isBlockPointerType() ||
329 T->isReferenceType() || T->isNullPtrType();
335 static bool isKind(const SVal& V) {
336 return V.getBaseKind() == LocKind;
340 //==------------------------------------------------------------------------==//
341 // Subclasses of NonLoc.
342 //==------------------------------------------------------------------------==//
346 /// Represents symbolic expression that isn't a location.
347 class SymbolVal : public NonLoc {
349 SymbolVal() = delete;
350 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {
352 assert(!Loc::isLocType(sym->getType()));
355 SymbolRef getSymbol() const {
356 return (const SymExpr *) Data;
359 bool isExpression() const {
360 return !isa<SymbolData>(getSymbol());
366 static bool isKind(const SVal& V) {
367 return V.getBaseKind() == NonLocKind &&
368 V.getSubKind() == SymbolValKind;
371 static bool isKind(const NonLoc& V) {
372 return V.getSubKind() == SymbolValKind;
376 /// Value representing integer constant.
377 class ConcreteInt : public NonLoc {
379 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
381 const llvm::APSInt& getValue() const {
382 return *static_cast<const llvm::APSInt *>(Data);
385 // Transfer functions for binary/unary operations on ConcreteInts.
386 SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
387 const ConcreteInt& R) const;
389 ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
391 ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
396 ConcreteInt() = default;
398 static bool isKind(const SVal& V) {
399 return V.getBaseKind() == NonLocKind &&
400 V.getSubKind() == ConcreteIntKind;
403 static bool isKind(const NonLoc& V) {
404 return V.getSubKind() == ConcreteIntKind;
408 class LocAsInteger : public NonLoc {
409 friend class ento::SValBuilder;
411 explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
412 : NonLoc(LocAsIntegerKind, &data) {
413 // We do not need to represent loc::ConcreteInt as LocAsInteger,
414 // as it'd collapse into a nonloc::ConcreteInt instead.
415 assert(data.first.getBaseKind() == LocKind &&
416 (data.first.getSubKind() == loc::MemRegionValKind ||
417 data.first.getSubKind() == loc::GotoLabelKind));
422 const std::pair<SVal, uintptr_t> *D =
423 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
424 return D->first.castAs<Loc>();
427 Loc getPersistentLoc() const {
428 const std::pair<SVal, uintptr_t> *D =
429 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
430 const SVal& V = D->first;
431 return V.castAs<Loc>();
434 unsigned getNumBits() const {
435 const std::pair<SVal, uintptr_t> *D =
436 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
443 LocAsInteger() = default;
445 static bool isKind(const SVal& V) {
446 return V.getBaseKind() == NonLocKind &&
447 V.getSubKind() == LocAsIntegerKind;
450 static bool isKind(const NonLoc& V) {
451 return V.getSubKind() == LocAsIntegerKind;
455 class CompoundVal : public NonLoc {
456 friend class ento::SValBuilder;
458 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
461 const CompoundValData* getValue() const {
462 return static_cast<const CompoundValData *>(Data);
465 using iterator = llvm::ImmutableList<SVal>::iterator;
467 iterator begin() const;
468 iterator end() const;
473 CompoundVal() = default;
475 static bool isKind(const SVal& V) {
476 return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
479 static bool isKind(const NonLoc& V) {
480 return V.getSubKind() == CompoundValKind;
484 class LazyCompoundVal : public NonLoc {
485 friend class ento::SValBuilder;
487 explicit LazyCompoundVal(const LazyCompoundValData *D)
488 : NonLoc(LazyCompoundValKind, D) {}
491 const LazyCompoundValData *getCVData() const {
492 return static_cast<const LazyCompoundValData *>(Data);
495 const void *getStore() const;
496 const TypedValueRegion *getRegion() const;
501 LazyCompoundVal() = default;
503 static bool isKind(const SVal& V) {
504 return V.getBaseKind() == NonLocKind &&
505 V.getSubKind() == LazyCompoundValKind;
508 static bool isKind(const NonLoc& V) {
509 return V.getSubKind() == LazyCompoundValKind;
513 /// Value representing pointer-to-member.
515 /// This value is qualified as NonLoc because neither loading nor storing
516 /// operations are applied to it. Instead, the analyzer uses the L-value coming
517 /// from pointer-to-member applied to an object.
518 /// This SVal is represented by a DeclaratorDecl which can be a member function
519 /// pointer or a member data pointer and a list of CXXBaseSpecifiers. This list
520 /// is required to accumulate the pointer-to-member cast history to figure out
521 /// the correct subobject field.
522 class PointerToMember : public NonLoc {
523 friend class ento::SValBuilder;
527 llvm::PointerUnion<const DeclaratorDecl *, const PointerToMemberData *>;
529 const PTMDataType getPTMData() const {
530 return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data));
533 bool isNullMemberPointer() const {
534 return getPTMData().isNull();
537 const DeclaratorDecl *getDecl() const;
539 template<typename AdjustedDecl>
540 const AdjustedDecl *getDeclAs() const {
541 return dyn_cast_or_null<AdjustedDecl>(getDecl());
544 using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator;
546 iterator begin() const;
547 iterator end() const;
552 PointerToMember() = default;
553 explicit PointerToMember(const PTMDataType D)
554 : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {}
556 static bool isKind(const SVal& V) {
557 return V.getBaseKind() == NonLocKind &&
558 V.getSubKind() == PointerToMemberKind;
561 static bool isKind(const NonLoc& V) {
562 return V.getSubKind() == PointerToMemberKind;
566 } // namespace nonloc
568 //==------------------------------------------------------------------------==//
569 // Subclasses of Loc.
570 //==------------------------------------------------------------------------==//
574 class GotoLabel : public Loc {
576 explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) {
580 const LabelDecl *getLabel() const {
581 return static_cast<const LabelDecl *>(Data);
587 GotoLabel() = default;
589 static bool isKind(const SVal& V) {
590 return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind;
593 static bool isKind(const Loc& V) {
594 return V.getSubKind() == GotoLabelKind;
598 class MemRegionVal : public Loc {
600 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) {
604 /// Get the underlining region.
605 const MemRegion *getRegion() const {
606 return static_cast<const MemRegion *>(Data);
609 /// Get the underlining region and strip casts.
610 const MemRegion* stripCasts(bool StripBaseCasts = true) const;
612 template <typename REGION>
613 const REGION* getRegionAs() const {
614 return dyn_cast<REGION>(getRegion());
617 bool operator==(const MemRegionVal &R) const {
618 return getRegion() == R.getRegion();
621 bool operator!=(const MemRegionVal &R) const {
622 return getRegion() != R.getRegion();
628 MemRegionVal() = default;
630 static bool isKind(const SVal& V) {
631 return V.getBaseKind() == LocKind &&
632 V.getSubKind() == MemRegionValKind;
635 static bool isKind(const Loc& V) {
636 return V.getSubKind() == MemRegionValKind;
640 class ConcreteInt : public Loc {
642 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
644 const llvm::APSInt &getValue() const {
645 return *static_cast<const llvm::APSInt *>(Data);
648 // Transfer functions for binary/unary operations on ConcreteInts.
649 SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
650 const ConcreteInt& R) const;
655 ConcreteInt() = default;
657 static bool isKind(const SVal& V) {
658 return V.getBaseKind() == LocKind &&
659 V.getSubKind() == ConcreteIntKind;
662 static bool isKind(const Loc& V) {
663 return V.getSubKind() == ConcreteIntKind;
675 template <typename T> struct isPodLike;
676 template <> struct isPodLike<clang::ento::SVal> {
677 static const bool value = true;
682 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H