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/Basic/LLVM.h"
20 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
22 #include "llvm/ADT/FoldingSet.h"
23 #include "llvm/ADT/ImmutableList.h"
25 //==------------------------------------------------------------------------==//
27 //==------------------------------------------------------------------------==//
33 class CompoundValData;
34 class LazyCompoundValData;
36 class BasicValueFactory;
38 class TypedValueRegion;
39 class MemRegionManager;
40 class ProgramStateManager;
43 /// SVal - This represents a symbolic expression, which can be either
44 /// an L-value or an R-value.
49 // The enumerators must be representable using 2 bits.
50 #define BASIC_SVAL(Id, Parent) Id ## Kind,
51 #define ABSTRACT_SVAL_WITH_KIND(Id, Parent) Id ## Kind,
52 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
54 enum { BaseBits = 2, BaseMask = 0x3 };
59 /// The lowest 2 bits are a BaseKind (0 -- 3).
60 /// The higher bits are an unsigned "kind" value.
63 explicit SVal(const void *d, bool isLoc, unsigned ValKind)
64 : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
66 explicit SVal(BaseKind k, const void *D = nullptr)
70 explicit SVal() : Data(nullptr), Kind(0) {}
72 /// \brief Convert to the specified SVal type, asserting that this SVal is of
76 assert(T::isKind(*this));
83 /// \brief Convert to the specified SVal type, returning None if this SVal is
84 /// not of the desired type.
86 Optional<T> getAs() const {
87 if (!T::isKind(*this))
95 /// BufferTy - A temporary buffer to hold a set of SVals.
96 typedef SmallVector<SVal,5> BufferTy;
98 inline unsigned getRawKind() const { return Kind; }
99 inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
100 inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
102 // This method is required for using SVal in a FoldingSetNode. It
103 // extracts a unique signature for this SVal object.
104 inline void Profile(llvm::FoldingSetNodeID& ID) const {
105 ID.AddInteger((unsigned) getRawKind());
109 inline bool operator==(const SVal& R) const {
110 return getRawKind() == R.getRawKind() && Data == R.Data;
113 inline bool operator!=(const SVal& R) const {
114 return !(*this == R);
117 inline bool isUnknown() const {
118 return getRawKind() == UnknownValKind;
121 inline bool isUndef() const {
122 return getRawKind() == UndefinedValKind;
125 inline bool isUnknownOrUndef() const {
126 return getRawKind() <= UnknownValKind;
129 inline bool isValid() const {
130 return getRawKind() > UnknownValKind;
133 bool isConstant() const;
135 bool isConstant(int I) const;
137 bool isZeroConstant() const;
139 /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true;
140 bool hasConjuredSymbol() const;
142 /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a
143 /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl.
144 /// Otherwise return 0.
145 const FunctionDecl *getAsFunctionDecl() const;
147 /// \brief If this SVal is a location and wraps a symbol, return that
148 /// SymbolRef. Otherwise return 0.
150 /// Casts are ignored during lookup.
151 /// \param IncludeBaseRegions The boolean that controls whether the search
152 /// should continue to the base regions if the region is not symbolic.
153 SymbolRef getAsLocSymbol(bool IncludeBaseRegions = false) const;
155 /// Get the symbol in the SVal or its base region.
156 SymbolRef getLocSymbolInBase() const;
158 /// \brief If this SVal wraps a symbol return that SymbolRef.
159 /// Otherwise, return 0.
161 /// Casts are ignored during lookup.
162 /// \param IncludeBaseRegions The boolean that controls whether the search
163 /// should continue to the base regions if the region is not symbolic.
164 SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const;
166 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
167 /// return that expression. Otherwise return NULL.
168 const SymExpr *getAsSymbolicExpression() const;
170 const SymExpr* getAsSymExpr() const;
172 const MemRegion *getAsRegion() const;
174 void dumpToStream(raw_ostream &OS) const;
177 SymExpr::symbol_iterator symbol_begin() const {
178 const SymExpr *SE = getAsSymbolicExpression();
180 return SE->symbol_begin();
182 return SymExpr::symbol_iterator();
185 SymExpr::symbol_iterator symbol_end() const {
186 return SymExpr::symbol_end();
191 class UndefinedVal : public SVal {
193 UndefinedVal() : SVal(UndefinedValKind) {}
197 static bool isKind(const SVal& V) {
198 return V.getBaseKind() == UndefinedValKind;
202 class DefinedOrUnknownSVal : public SVal {
204 // We want calling these methods to be a compiler error since they are
205 // tautologically false.
206 bool isUndef() const = delete;
207 bool isValid() const = delete;
210 DefinedOrUnknownSVal() {}
211 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
212 : SVal(d, isLoc, ValKind) {}
214 explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr)
219 static bool isKind(const SVal& V) {
224 class UnknownVal : public DefinedOrUnknownSVal {
226 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {}
230 static bool isKind(const SVal &V) {
231 return V.getBaseKind() == UnknownValKind;
235 class DefinedSVal : public DefinedOrUnknownSVal {
237 // We want calling these methods to be a compiler error since they are
238 // tautologically true/false.
239 bool isUnknown() const = delete;
240 bool isUnknownOrUndef() const = delete;
241 bool isValid() const = delete;
244 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
245 : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
248 static bool isKind(const SVal& V) {
249 return !V.isUnknownOrUndef();
254 /// \brief Represents an SVal that is guaranteed to not be UnknownVal.
255 class KnownSVal : public SVal {
258 static bool isKind(const SVal &V) {
259 return !V.isUnknown();
262 KnownSVal(const DefinedSVal &V) : SVal(V) {}
263 KnownSVal(const UndefinedVal &V) : SVal(V) {}
266 class NonLoc : public DefinedSVal {
269 explicit NonLoc(unsigned SubKind, const void *d)
270 : DefinedSVal(d, false, SubKind) {}
273 void dumpToStream(raw_ostream &Out) const;
277 static bool isKind(const SVal& V) {
278 return V.getBaseKind() == NonLocKind;
282 class Loc : public DefinedSVal {
285 explicit Loc(unsigned SubKind, const void *D)
286 : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
289 void dumpToStream(raw_ostream &Out) const;
291 static inline bool isLocType(QualType T) {
292 return T->isAnyPointerType() || T->isBlockPointerType() ||
293 T->isReferenceType() || T->isNullPtrType();
298 static bool isKind(const SVal& V) {
299 return V.getBaseKind() == LocKind;
303 //==------------------------------------------------------------------------==//
304 // Subclasses of NonLoc.
305 //==------------------------------------------------------------------------==//
310 #define NONLOC_SVAL(Id, Parent) Id ## Kind,
311 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
314 /// \brief Represents symbolic expression.
315 class SymbolVal : public NonLoc {
317 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
319 SymbolRef getSymbol() const {
320 return (const SymExpr*) Data;
323 bool isExpression() const {
324 return !isa<SymbolData>(getSymbol());
330 static bool isKind(const SVal& V) {
331 return V.getBaseKind() == NonLocKind &&
332 V.getSubKind() == SymbolValKind;
335 static bool isKind(const NonLoc& V) {
336 return V.getSubKind() == SymbolValKind;
340 /// \brief Value representing integer constant.
341 class ConcreteInt : public NonLoc {
343 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
345 const llvm::APSInt& getValue() const {
346 return *static_cast<const llvm::APSInt*>(Data);
349 // Transfer functions for binary/unary operations on ConcreteInts.
350 SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
351 const ConcreteInt& R) const;
353 ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
355 ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
360 static bool isKind(const SVal& V) {
361 return V.getBaseKind() == NonLocKind &&
362 V.getSubKind() == ConcreteIntKind;
365 static bool isKind(const NonLoc& V) {
366 return V.getSubKind() == ConcreteIntKind;
370 class LocAsInteger : public NonLoc {
371 friend class ento::SValBuilder;
373 explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
374 : NonLoc(LocAsIntegerKind, &data) {
375 assert (data.first.getAs<Loc>());
381 const std::pair<SVal, uintptr_t> *D =
382 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
383 return D->first.castAs<Loc>();
386 Loc getPersistentLoc() const {
387 const std::pair<SVal, uintptr_t> *D =
388 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
389 const SVal& V = D->first;
390 return V.castAs<Loc>();
393 unsigned getNumBits() const {
394 const std::pair<SVal, uintptr_t> *D =
395 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
402 static bool isKind(const SVal& V) {
403 return V.getBaseKind() == NonLocKind &&
404 V.getSubKind() == LocAsIntegerKind;
407 static bool isKind(const NonLoc& V) {
408 return V.getSubKind() == LocAsIntegerKind;
412 class CompoundVal : public NonLoc {
413 friend class ento::SValBuilder;
415 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
418 const CompoundValData* getValue() const {
419 return static_cast<const CompoundValData*>(Data);
422 typedef llvm::ImmutableList<SVal>::iterator iterator;
423 iterator begin() const;
424 iterator end() const;
429 static bool isKind(const SVal& V) {
430 return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
433 static bool isKind(const NonLoc& V) {
434 return V.getSubKind() == CompoundValKind;
438 class LazyCompoundVal : public NonLoc {
439 friend class ento::SValBuilder;
441 explicit LazyCompoundVal(const LazyCompoundValData *D)
442 : NonLoc(LazyCompoundValKind, D) {}
444 const LazyCompoundValData *getCVData() const {
445 return static_cast<const LazyCompoundValData*>(Data);
447 const void *getStore() const;
448 const TypedValueRegion *getRegion() const;
453 static bool isKind(const SVal& V) {
454 return V.getBaseKind() == NonLocKind &&
455 V.getSubKind() == LazyCompoundValKind;
457 static bool isKind(const NonLoc& V) {
458 return V.getSubKind() == LazyCompoundValKind;
462 } // end namespace ento::nonloc
464 //==------------------------------------------------------------------------==//
465 // Subclasses of Loc.
466 //==------------------------------------------------------------------------==//
471 #define LOC_SVAL(Id, Parent) Id ## Kind,
472 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
475 class GotoLabel : public Loc {
477 explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {}
479 const LabelDecl *getLabel() const {
480 return static_cast<const LabelDecl*>(Data);
486 static bool isKind(const SVal& V) {
487 return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind;
490 static bool isKind(const Loc& V) {
491 return V.getSubKind() == GotoLabelKind;
496 class MemRegionVal : public Loc {
498 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) {}
500 /// \brief Get the underlining region.
501 const MemRegion* getRegion() const {
502 return static_cast<const MemRegion*>(Data);
505 /// \brief Get the underlining region and strip casts.
506 const MemRegion* stripCasts(bool StripBaseCasts = true) const;
508 template <typename REGION>
509 const REGION* getRegionAs() const {
510 return dyn_cast<REGION>(getRegion());
513 inline bool operator==(const MemRegionVal& R) const {
514 return getRegion() == R.getRegion();
517 inline bool operator!=(const MemRegionVal& R) const {
518 return getRegion() != R.getRegion();
524 static bool isKind(const SVal& V) {
525 return V.getBaseKind() == LocKind &&
526 V.getSubKind() == MemRegionValKind;
529 static bool isKind(const Loc& V) {
530 return V.getSubKind() == MemRegionValKind;
534 class ConcreteInt : public Loc {
536 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
538 const llvm::APSInt& getValue() const {
539 return *static_cast<const llvm::APSInt*>(Data);
542 // Transfer functions for binary/unary operations on ConcreteInts.
543 SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
544 const ConcreteInt& R) const;
549 static bool isKind(const SVal& V) {
550 return V.getBaseKind() == LocKind &&
551 V.getSubKind() == ConcreteIntKind;
554 static bool isKind(const Loc& V) {
555 return V.getSubKind() == ConcreteIntKind;
559 } // end ento::loc namespace
561 } // end ento namespace
563 } // end clang namespace
566 static inline raw_ostream &operator<<(raw_ostream &os,
567 clang::ento::SVal V) {
572 template <typename T> struct isPodLike;
573 template <> struct isPodLike<clang::ento::SVal> {
574 static const bool value = true;
577 } // end llvm namespace