• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //== SVals.h - Abstract Values for Static Analysis ---------*- C++ -*--==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines SVal, Loc, and NonLoc, classes that represent
11 //  abstract r-values for use with path-sensitive value tracking.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
17 
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"
24 
25 //==------------------------------------------------------------------------==//
26 //  Base SVal types.
27 //==------------------------------------------------------------------------==//
28 
29 namespace clang {
30 
31 namespace ento {
32 
33 class CompoundValData;
34 class LazyCompoundValData;
35 class ProgramState;
36 class BasicValueFactory;
37 class MemRegion;
38 class TypedValueRegion;
39 class MemRegionManager;
40 class ProgramStateManager;
41 class SValBuilder;
42 
43 /// SVal - This represents a symbolic expression, which can be either
44 ///  an L-value or an R-value.
45 ///
46 class SVal {
47 public:
48   enum BaseKind {
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"
53   };
54   enum { BaseBits = 2, BaseMask = 0x3 };
55 
56 protected:
57   const void *Data;
58 
59   /// The lowest 2 bits are a BaseKind (0 -- 3).
60   ///  The higher bits are an unsigned "kind" value.
61   unsigned Kind;
62 
SVal(const void * d,bool isLoc,unsigned ValKind)63   explicit SVal(const void *d, bool isLoc, unsigned ValKind)
64   : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
65 
66   explicit SVal(BaseKind k, const void *D = nullptr)
Data(D)67     : Data(D), Kind(k) {}
68 
69 public:
SVal()70   explicit SVal() : Data(nullptr), Kind(0) {}
71 
72   /// \brief Convert to the specified SVal type, asserting that this SVal is of
73   /// the desired type.
74   template<typename T>
castAs()75   T castAs() const {
76     assert(T::isKind(*this));
77     T t;
78     SVal& sv = t;
79     sv = *this;
80     return t;
81   }
82 
83   /// \brief Convert to the specified SVal type, returning None if this SVal is
84   /// not of the desired type.
85   template<typename T>
getAs()86   Optional<T> getAs() const {
87     if (!T::isKind(*this))
88       return None;
89     T t;
90     SVal& sv = t;
91     sv = *this;
92     return t;
93   }
94 
95   /// BufferTy - A temporary buffer to hold a set of SVals.
96   typedef SmallVector<SVal,5> BufferTy;
97 
getRawKind()98   inline unsigned getRawKind() const { return Kind; }
getBaseKind()99   inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
getSubKind()100   inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
101 
102   // This method is required for using SVal in a FoldingSetNode.  It
103   // extracts a unique signature for this SVal object.
Profile(llvm::FoldingSetNodeID & ID)104   inline void Profile(llvm::FoldingSetNodeID& ID) const {
105     ID.AddInteger((unsigned) getRawKind());
106     ID.AddPointer(Data);
107   }
108 
109   inline bool operator==(const SVal& R) const {
110     return getRawKind() == R.getRawKind() && Data == R.Data;
111   }
112 
113   inline bool operator!=(const SVal& R) const {
114     return !(*this == R);
115   }
116 
isUnknown()117   inline bool isUnknown() const {
118     return getRawKind() == UnknownValKind;
119   }
120 
isUndef()121   inline bool isUndef() const {
122     return getRawKind() == UndefinedValKind;
123   }
124 
isUnknownOrUndef()125   inline bool isUnknownOrUndef() const {
126     return getRawKind() <= UnknownValKind;
127   }
128 
isValid()129   inline bool isValid() const {
130     return getRawKind() > UnknownValKind;
131   }
132 
133   bool isConstant() const;
134 
135   bool isConstant(int I) const;
136 
137   bool isZeroConstant() const;
138 
139   /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true;
140   bool hasConjuredSymbol() const;
141 
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;
146 
147   /// \brief If this SVal is a location and wraps a symbol, return that
148   ///  SymbolRef. Otherwise return 0.
149   ///
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;
154 
155   /// Get the symbol in the SVal or its base region.
156   SymbolRef getLocSymbolInBase() const;
157 
158   /// \brief If this SVal wraps a symbol return that SymbolRef.
159   /// Otherwise, return 0.
160   ///
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;
165 
166   /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
167   ///  return that expression.  Otherwise return NULL.
168   const SymExpr *getAsSymbolicExpression() const;
169 
170   const SymExpr* getAsSymExpr() const;
171 
172   const MemRegion *getAsRegion() const;
173 
174   void dumpToStream(raw_ostream &OS) const;
175   void dump() const;
176 
symbol_begin()177   SymExpr::symbol_iterator symbol_begin() const {
178     const SymExpr *SE = getAsSymbolicExpression();
179     if (SE)
180       return SE->symbol_begin();
181     else
182       return SymExpr::symbol_iterator();
183   }
184 
symbol_end()185   SymExpr::symbol_iterator symbol_end() const {
186     return SymExpr::symbol_end();
187   }
188 };
189 
190 
191 class UndefinedVal : public SVal {
192 public:
UndefinedVal()193   UndefinedVal() : SVal(UndefinedValKind) {}
194 
195 private:
196   friend class SVal;
isKind(const SVal & V)197   static bool isKind(const SVal& V) {
198     return V.getBaseKind() == UndefinedValKind;
199   }
200 };
201 
202 class DefinedOrUnknownSVal : public SVal {
203 private:
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;
208 
209 protected:
DefinedOrUnknownSVal()210   DefinedOrUnknownSVal() {}
DefinedOrUnknownSVal(const void * d,bool isLoc,unsigned ValKind)211   explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
212     : SVal(d, isLoc, ValKind) {}
213 
214   explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr)
SVal(k,D)215     : SVal(k, D) {}
216 
217 private:
218   friend class SVal;
isKind(const SVal & V)219   static bool isKind(const SVal& V) {
220     return !V.isUndef();
221   }
222 };
223 
224 class UnknownVal : public DefinedOrUnknownSVal {
225 public:
UnknownVal()226   explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {}
227 
228 private:
229   friend class SVal;
isKind(const SVal & V)230   static bool isKind(const SVal &V) {
231     return V.getBaseKind() == UnknownValKind;
232   }
233 };
234 
235 class DefinedSVal : public DefinedOrUnknownSVal {
236 private:
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;
242 protected:
DefinedSVal()243   DefinedSVal() {}
DefinedSVal(const void * d,bool isLoc,unsigned ValKind)244   explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
245     : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
246 private:
247   friend class SVal;
isKind(const SVal & V)248   static bool isKind(const SVal& V) {
249     return !V.isUnknownOrUndef();
250   }
251 };
252 
253 
254 /// \brief Represents an SVal that is guaranteed to not be UnknownVal.
255 class KnownSVal : public SVal {
KnownSVal()256   KnownSVal() {}
257   friend class SVal;
isKind(const SVal & V)258   static bool isKind(const SVal &V) {
259     return !V.isUnknown();
260   }
261 public:
KnownSVal(const DefinedSVal & V)262   KnownSVal(const DefinedSVal &V) : SVal(V) {}
KnownSVal(const UndefinedVal & V)263   KnownSVal(const UndefinedVal &V) : SVal(V) {}
264 };
265 
266 class NonLoc : public DefinedSVal {
267 protected:
NonLoc()268   NonLoc() {}
NonLoc(unsigned SubKind,const void * d)269   explicit NonLoc(unsigned SubKind, const void *d)
270     : DefinedSVal(d, false, SubKind) {}
271 
272 public:
273   void dumpToStream(raw_ostream &Out) const;
274 
275 private:
276   friend class SVal;
isKind(const SVal & V)277   static bool isKind(const SVal& V) {
278     return V.getBaseKind() == NonLocKind;
279   }
280 };
281 
282 class Loc : public DefinedSVal {
283 protected:
Loc()284   Loc() {}
Loc(unsigned SubKind,const void * D)285   explicit Loc(unsigned SubKind, const void *D)
286   : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
287 
288 public:
289   void dumpToStream(raw_ostream &Out) const;
290 
isLocType(QualType T)291   static inline bool isLocType(QualType T) {
292     return T->isAnyPointerType() || T->isBlockPointerType() ||
293            T->isReferenceType() || T->isNullPtrType();
294   }
295 
296 private:
297   friend class SVal;
isKind(const SVal & V)298   static bool isKind(const SVal& V) {
299     return V.getBaseKind() == LocKind;
300   }
301 };
302 
303 //==------------------------------------------------------------------------==//
304 //  Subclasses of NonLoc.
305 //==------------------------------------------------------------------------==//
306 
307 namespace nonloc {
308 
309 enum Kind {
310 #define NONLOC_SVAL(Id, Parent) Id ## Kind,
311 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
312 };
313 
314 /// \brief Represents symbolic expression.
315 class SymbolVal : public NonLoc {
316 public:
SymbolVal(SymbolRef sym)317   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
318 
getSymbol()319   SymbolRef getSymbol() const {
320     return (const SymExpr*) Data;
321   }
322 
isExpression()323   bool isExpression() const {
324     return !isa<SymbolData>(getSymbol());
325   }
326 
327 private:
328   friend class SVal;
SymbolVal()329   SymbolVal() {}
isKind(const SVal & V)330   static bool isKind(const SVal& V) {
331     return V.getBaseKind() == NonLocKind &&
332            V.getSubKind() == SymbolValKind;
333   }
334 
isKind(const NonLoc & V)335   static bool isKind(const NonLoc& V) {
336     return V.getSubKind() == SymbolValKind;
337   }
338 };
339 
340 /// \brief Value representing integer constant.
341 class ConcreteInt : public NonLoc {
342 public:
ConcreteInt(const llvm::APSInt & V)343   explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
344 
getValue()345   const llvm::APSInt& getValue() const {
346     return *static_cast<const llvm::APSInt*>(Data);
347   }
348 
349   // Transfer functions for binary/unary operations on ConcreteInts.
350   SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
351                  const ConcreteInt& R) const;
352 
353   ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
354 
355   ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
356 
357 private:
358   friend class SVal;
ConcreteInt()359   ConcreteInt() {}
isKind(const SVal & V)360   static bool isKind(const SVal& V) {
361     return V.getBaseKind() == NonLocKind &&
362            V.getSubKind() == ConcreteIntKind;
363   }
364 
isKind(const NonLoc & V)365   static bool isKind(const NonLoc& V) {
366     return V.getSubKind() == ConcreteIntKind;
367   }
368 };
369 
370 class LocAsInteger : public NonLoc {
371   friend class ento::SValBuilder;
372 
LocAsInteger(const std::pair<SVal,uintptr_t> & data)373   explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
374       : NonLoc(LocAsIntegerKind, &data) {
375     assert (data.first.getAs<Loc>());
376   }
377 
378 public:
379 
getLoc()380   Loc getLoc() const {
381     const std::pair<SVal, uintptr_t> *D =
382       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
383     return D->first.castAs<Loc>();
384   }
385 
getPersistentLoc()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>();
391   }
392 
getNumBits()393   unsigned getNumBits() const {
394     const std::pair<SVal, uintptr_t> *D =
395       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
396     return D->second;
397   }
398 
399 private:
400   friend class SVal;
LocAsInteger()401   LocAsInteger() {}
isKind(const SVal & V)402   static bool isKind(const SVal& V) {
403     return V.getBaseKind() == NonLocKind &&
404            V.getSubKind() == LocAsIntegerKind;
405   }
406 
isKind(const NonLoc & V)407   static bool isKind(const NonLoc& V) {
408     return V.getSubKind() == LocAsIntegerKind;
409   }
410 };
411 
412 class CompoundVal : public NonLoc {
413   friend class ento::SValBuilder;
414 
CompoundVal(const CompoundValData * D)415   explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
416 
417 public:
getValue()418   const CompoundValData* getValue() const {
419     return static_cast<const CompoundValData*>(Data);
420   }
421 
422   typedef llvm::ImmutableList<SVal>::iterator iterator;
423   iterator begin() const;
424   iterator end() const;
425 
426 private:
427   friend class SVal;
CompoundVal()428   CompoundVal() {}
isKind(const SVal & V)429   static bool isKind(const SVal& V) {
430     return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
431   }
432 
isKind(const NonLoc & V)433   static bool isKind(const NonLoc& V) {
434     return V.getSubKind() == CompoundValKind;
435   }
436 };
437 
438 class LazyCompoundVal : public NonLoc {
439   friend class ento::SValBuilder;
440 
LazyCompoundVal(const LazyCompoundValData * D)441   explicit LazyCompoundVal(const LazyCompoundValData *D)
442     : NonLoc(LazyCompoundValKind, D) {}
443 public:
getCVData()444   const LazyCompoundValData *getCVData() const {
445     return static_cast<const LazyCompoundValData*>(Data);
446   }
447   const void *getStore() const;
448   const TypedValueRegion *getRegion() const;
449 
450 private:
451   friend class SVal;
LazyCompoundVal()452   LazyCompoundVal() {}
isKind(const SVal & V)453   static bool isKind(const SVal& V) {
454     return V.getBaseKind() == NonLocKind &&
455            V.getSubKind() == LazyCompoundValKind;
456   }
isKind(const NonLoc & V)457   static bool isKind(const NonLoc& V) {
458     return V.getSubKind() == LazyCompoundValKind;
459   }
460 };
461 
462 } // end namespace ento::nonloc
463 
464 //==------------------------------------------------------------------------==//
465 //  Subclasses of Loc.
466 //==------------------------------------------------------------------------==//
467 
468 namespace loc {
469 
470 enum Kind {
471 #define LOC_SVAL(Id, Parent) Id ## Kind,
472 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
473 };
474 
475 class GotoLabel : public Loc {
476 public:
GotoLabel(LabelDecl * Label)477   explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {}
478 
getLabel()479   const LabelDecl *getLabel() const {
480     return static_cast<const LabelDecl*>(Data);
481   }
482 
483 private:
484   friend class SVal;
GotoLabel()485   GotoLabel() {}
isKind(const SVal & V)486   static bool isKind(const SVal& V) {
487     return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind;
488   }
489 
isKind(const Loc & V)490   static bool isKind(const Loc& V) {
491     return V.getSubKind() == GotoLabelKind;
492   }
493 };
494 
495 
496 class MemRegionVal : public Loc {
497 public:
MemRegionVal(const MemRegion * r)498   explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) {}
499 
500   /// \brief Get the underlining region.
getRegion()501   const MemRegion* getRegion() const {
502     return static_cast<const MemRegion*>(Data);
503   }
504 
505   /// \brief Get the underlining region and strip casts.
506   const MemRegion* stripCasts(bool StripBaseCasts = true) const;
507 
508   template <typename REGION>
getRegionAs()509   const REGION* getRegionAs() const {
510     return dyn_cast<REGION>(getRegion());
511   }
512 
513   inline bool operator==(const MemRegionVal& R) const {
514     return getRegion() == R.getRegion();
515   }
516 
517   inline bool operator!=(const MemRegionVal& R) const {
518     return getRegion() != R.getRegion();
519   }
520 
521 private:
522   friend class SVal;
MemRegionVal()523   MemRegionVal() {}
isKind(const SVal & V)524   static bool isKind(const SVal& V) {
525     return V.getBaseKind() == LocKind &&
526            V.getSubKind() == MemRegionValKind;
527   }
528 
isKind(const Loc & V)529   static bool isKind(const Loc& V) {
530     return V.getSubKind() == MemRegionValKind;
531   }
532 };
533 
534 class ConcreteInt : public Loc {
535 public:
ConcreteInt(const llvm::APSInt & V)536   explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
537 
getValue()538   const llvm::APSInt& getValue() const {
539     return *static_cast<const llvm::APSInt*>(Data);
540   }
541 
542   // Transfer functions for binary/unary operations on ConcreteInts.
543   SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
544                  const ConcreteInt& R) const;
545 
546 private:
547   friend class SVal;
ConcreteInt()548   ConcreteInt() {}
isKind(const SVal & V)549   static bool isKind(const SVal& V) {
550     return V.getBaseKind() == LocKind &&
551            V.getSubKind() == ConcreteIntKind;
552   }
553 
isKind(const Loc & V)554   static bool isKind(const Loc& V) {
555     return V.getSubKind() == ConcreteIntKind;
556   }
557 };
558 
559 } // end ento::loc namespace
560 
561 } // end ento namespace
562 
563 } // end clang namespace
564 
565 namespace llvm {
566 static inline raw_ostream &operator<<(raw_ostream &os,
567                                             clang::ento::SVal V) {
568   V.dumpToStream(os);
569   return os;
570 }
571 
572 template <typename T> struct isPodLike;
573 template <> struct isPodLike<clang::ento::SVal> {
574   static const bool value = true;
575 };
576 
577 } // end llvm namespace
578 
579 #endif
580