include/clang/StaticAnalyzer/PathSensitive/SVals.h

   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_GR_RVALUE_H
  16 #define LLVM_CLANG_GR_RVALUE_H
  17
  18 #include "clang/StaticAnalyzer/PathSensitive/SymbolManager.h"
  19 #include "llvm/Support/Casting.h"
  20 #include "llvm/ADT/ImmutableList.h"
  21
  22 namespace llvm {
  23   class raw_ostream;
  24 }
  25
  26 //==------------------------------------------------------------------------==//
  27 //  Base SVal types.
  28 //==------------------------------------------------------------------------==//
  29
  30 namespace clang {
  31
  32 namespace ento {
  33
  34 class CompoundValData;
  35 class LazyCompoundValData;
  36 class GRState;
  37 class BasicValueFactory;
  38 class MemRegion;
  39 class TypedRegion;
  40 class MemRegionManager;
  41 class GRStateManager;
  42 class SValBuilder;
  43
  44 /// SVal - This represents a symbolic expression, which can be either
  45 ///  an L-value or an R-value.
  46 ///
  47 class SVal {
  48 public:
  49   enum BaseKind {
  50     // The enumerators must be representable using 2 bits.
  51     UndefinedKind = 0,  // for subclass UndefinedVal (an uninitialized value)
  52     UnknownKind = 1,    // for subclass UnknownVal (a void value)
  53     LocKind = 2,        // for subclass Loc (an L-value)
  54     NonLocKind = 3      // for subclass NonLoc (an R-value that's not
  55                         //   an L-value)
  56   };
  57   enum { BaseBits = 2, BaseMask = 0x3 };
  58
  59 protected:
  60   const void* Data;
  61
  62   /// The lowest 2 bits are a BaseKind (0 -- 3).
  63   ///  The higher bits are an unsigned "kind" value.
  64   unsigned Kind;
  65
  66 protected:
  67   explicit SVal(const void* d, bool isLoc, unsigned ValKind)
  68   : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
  69
  70   explicit SVal(BaseKind k, const void* D = NULL)
  71     : Data(D), Kind(k) {}
  72
  73 public:
  74   explicit SVal() : Data(0), Kind(0) {}
  75   ~SVal() {}
  76
  77   /// BufferTy - A temporary buffer to hold a set of SVals.
  78   typedef llvm::SmallVector<SVal,5> BufferTy;
  79
  80   inline unsigned getRawKind() const { return Kind; }
  81   inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
  82   inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
  83
  84   inline void Profile(llvm::FoldingSetNodeID& ID) const {
  85     ID.AddInteger((unsigned) getRawKind());
  86     ID.AddPointer(Data);
  87   }
  88
  89   inline bool operator==(const SVal& R) const {
  90     return getRawKind() == R.getRawKind() && Data == R.Data;
  91   }
  92
  93   inline bool operator!=(const SVal& R) const {
  94     return !(*this == R);
  95   }
  96
  97   inline bool isUnknown() const {
  98     return getRawKind() == UnknownKind;
  99   }
 100
 101   inline bool isUndef() const {
 102     return getRawKind() == UndefinedKind;
 103   }
 104
 105   inline bool isUnknownOrUndef() const {
 106     return getRawKind() <= UnknownKind;
 107   }
 108
 109   inline bool isValid() const {
 110     return getRawKind() > UnknownKind;
 111   }
 112
 113   bool isConstant() const;
 114
 115   bool isConstant(int I) const;
 116
 117   bool isZeroConstant() const;
 118
 119   /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true;
 120   bool hasConjuredSymbol() const;
 121
 122   /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a
 123   /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl.
 124   /// Otherwise return 0.
 125   const FunctionDecl* getAsFunctionDecl() const;
 126
 127   /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and
 128   ///  wraps a symbol, return that SymbolRef.  Otherwise return NULL.
 129   SymbolRef getAsLocSymbol() const;
 130
 131   /// Get the symbol in the SVal or its base region.
 132   SymbolRef getLocSymbolInBase() const;
 133
 134   /// getAsSymbol - If this Sval wraps a symbol return that SymbolRef.
 135   ///  Otherwise return a SymbolRef where 'isValid()' returns false.
 136   SymbolRef getAsSymbol() const;
 137
 138   /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
 139   ///  return that expression.  Otherwise return NULL.
 140   const SymExpr *getAsSymbolicExpression() const;
 141
 142   const MemRegion *getAsRegion() const;
 143
 144   void dumpToStream(llvm::raw_ostream& OS) const;
 145   void dump() const;
 146
 147   // Iterators.
 148   class symbol_iterator {
 149     llvm::SmallVector<const SymExpr*, 5> itr;
 150     void expand();
 151   public:
 152     symbol_iterator() {}
 153     symbol_iterator(const SymExpr* SE);
 154
 155     symbol_iterator& operator++();
 156     SymbolRef operator*();
 157
 158     bool operator==(const symbol_iterator& X) const;
 159     bool operator!=(const symbol_iterator& X) const;
 160   };
 161
 162   symbol_iterator symbol_begin() const {
 163     const SymExpr *SE = getAsSymbolicExpression();
 164     if (SE)
 165       return symbol_iterator(SE);
 166     else
 167       return symbol_iterator();
 168   }
 169
 170   symbol_iterator symbol_end() const { return symbol_iterator(); }
 171
 172   // Implement isa<T> support.
 173   static inline bool classof(const SVal*) { return true; }
 174 };
 175
 176
 177 class UndefinedVal : public SVal {
 178 public:
 179   UndefinedVal() : SVal(UndefinedKind) {}
 180   UndefinedVal(const void* D) : SVal(UndefinedKind, D) {}
 181
 182   static inline bool classof(const SVal* V) {
 183     return V->getBaseKind() == UndefinedKind;
 184   }
 185
 186   const void* getData() const { return Data; }
 187 };
 188
 189 class DefinedOrUnknownSVal : public SVal {
 190 private:
 191   // Do not implement.  We want calling these methods to be a compiler
 192   // error since they are tautologically false.
 193   bool isUndef() const;
 194   bool isValid() const;
 195
 196 protected:
 197   explicit DefinedOrUnknownSVal(const void* d, bool isLoc, unsigned ValKind)
 198     : SVal(d, isLoc, ValKind) {}
 199
 200   explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL)
 201     : SVal(k, D) {}
 202
 203 public:
 204     // Implement isa<T> support.
 205   static inline bool classof(const SVal *V) {
 206     return !V->isUndef();
 207   }
 208 };
 209
 210 class UnknownVal : public DefinedOrUnknownSVal {
 211 public:
 212   explicit UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {}
 213
 214   static inline bool classof(const SVal *V) {
 215     return V->getBaseKind() == UnknownKind;
 216   }
 217 };
 218
 219 class DefinedSVal : public DefinedOrUnknownSVal {
 220 private:
 221   // Do not implement.  We want calling these methods to be a compiler
 222   // error since they are tautologically true/false.
 223   bool isUnknown() const;
 224   bool isUnknownOrUndef() const;
 225   bool isValid() const;
 226 protected:
 227   explicit DefinedSVal(const void* d, bool isLoc, unsigned ValKind)
 228     : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
 229 public:
 230   // Implement isa<T> support.
 231   static inline bool classof(const SVal *V) {
 232     return !V->isUnknownOrUndef();
 233   }
 234 };
 235
 236 class NonLoc : public DefinedSVal {
 237 protected:
 238   explicit NonLoc(unsigned SubKind, const void* d)
 239     : DefinedSVal(d, false, SubKind) {}
 240
 241 public:
 242   void dumpToStream(llvm::raw_ostream& Out) const;
 243
 244   // Implement isa<T> support.
 245   static inline bool classof(const SVal* V) {
 246     return V->getBaseKind() == NonLocKind;
 247   }
 248 };
 249
 250 class Loc : public DefinedSVal {
 251 protected:
 252   explicit Loc(unsigned SubKind, const void* D)
 253   : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
 254
 255 public:
 256   void dumpToStream(llvm::raw_ostream& Out) const;
 257
 258   Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {}
 259
 260   // Implement isa<T> support.
 261   static inline bool classof(const SVal* V) {
 262     return V->getBaseKind() == LocKind;
 263   }
 264
 265   static inline bool IsLocType(QualType T) {
 266     return T->isAnyPointerType() || T->isBlockPointerType() ||
 267            T->isReferenceType();
 268   }
 269 };
 270
 271 //==------------------------------------------------------------------------==//
 272 //  Subclasses of NonLoc.
 273 //==------------------------------------------------------------------------==//
 274
 275 namespace nonloc {
 276
 277 enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind,
 278             LocAsIntegerKind, CompoundValKind, LazyCompoundValKind };
 279
 280 class SymbolVal : public NonLoc {
 281 public:
 282   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
 283
 284   SymbolRef getSymbol() const {
 285     return (const SymbolData*) Data;
 286   }
 287
 288   static inline bool classof(const SVal* V) {
 289     return V->getBaseKind() == NonLocKind &&
 290            V->getSubKind() == SymbolValKind;
 291   }
 292
 293   static inline bool classof(const NonLoc* V) {
 294     return V->getSubKind() == SymbolValKind;
 295   }
 296 };
 297
 298 class SymExprVal : public NonLoc {
 299 public:
 300   explicit SymExprVal(const SymExpr *SE)
 301     : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {}
 302
 303   const SymExpr *getSymbolicExpression() const {
 304     return reinterpret_cast<const SymExpr*>(Data);
 305   }
 306
 307   static inline bool classof(const SVal* V) {
 308     return V->getBaseKind() == NonLocKind &&
 309            V->getSubKind() == SymExprValKind;
 310   }
 311
 312   static inline bool classof(const NonLoc* V) {
 313     return V->getSubKind() == SymExprValKind;
 314   }
 315 };
 316
 317 class ConcreteInt : public NonLoc {
 318 public:
 319   explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
 320
 321   const llvm::APSInt& getValue() const {
 322     return *static_cast<const llvm::APSInt*>(Data);
 323   }
 324
 325   // Transfer functions for binary/unary operations on ConcreteInts.
 326   SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
 327                  const ConcreteInt& R) const;
 328
 329   ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
 330
 331   ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
 332
 333   // Implement isa<T> support.
 334   static inline bool classof(const SVal* V) {
 335     return V->getBaseKind() == NonLocKind &&
 336            V->getSubKind() == ConcreteIntKind;
 337   }
 338
 339   static inline bool classof(const NonLoc* V) {
 340     return V->getSubKind() == ConcreteIntKind;
 341   }
 342 };
 343
 344 class LocAsInteger : public NonLoc {
 345   friend class ento::SValBuilder;
 346
 347   explicit LocAsInteger(const std::pair<SVal, uintptr_t>& data) :
 348     NonLoc(LocAsIntegerKind, &data) {
 349       assert (isa<Loc>(data.first));
 350     }
 351
 352 public:
 353
 354   Loc getLoc() const {
 355     return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first);
 356   }
 357
 358   const Loc& getPersistentLoc() const {
 359     const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first;
 360     return cast<Loc>(V);
 361   }
 362
 363   unsigned getNumBits() const {
 364     return ((std::pair<SVal, unsigned>*) Data)->second;
 365   }
 366
 367   // Implement isa<T> support.
 368   static inline bool classof(const SVal* V) {
 369     return V->getBaseKind() == NonLocKind &&
 370            V->getSubKind() == LocAsIntegerKind;
 371   }
 372
 373   static inline bool classof(const NonLoc* V) {
 374     return V->getSubKind() == LocAsIntegerKind;
 375   }
 376 };
 377
 378 class CompoundVal : public NonLoc {
 379   friend class ento::SValBuilder;
 380
 381   explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
 382
 383 public:
 384   const CompoundValData* getValue() const {
 385     return static_cast<const CompoundValData*>(Data);
 386   }
 387
 388   typedef llvm::ImmutableList<SVal>::iterator iterator;
 389   iterator begin() const;
 390   iterator end() const;
 391
 392   static bool classof(const SVal* V) {
 393     return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind;
 394   }
 395
 396   static bool classof(const NonLoc* V) {
 397     return V->getSubKind() == CompoundValKind;
 398   }
 399 };
 400
 401 class LazyCompoundVal : public NonLoc {
 402   friend class ento::SValBuilder;
 403
 404   explicit LazyCompoundVal(const LazyCompoundValData *D)
 405     : NonLoc(LazyCompoundValKind, D) {}
 406 public:
 407   const LazyCompoundValData *getCVData() const {
 408     return static_cast<const LazyCompoundValData*>(Data);
 409   }
 410   const void *getStore() const;
 411   const TypedRegion *getRegion() const;
 412
 413   static bool classof(const SVal *V) {
 414     return V->getBaseKind() == NonLocKind &&
 415            V->getSubKind() == LazyCompoundValKind;
 416   }
 417   static bool classof(const NonLoc *V) {
 418     return V->getSubKind() == LazyCompoundValKind;
 419   }
 420 };
 421
 422 } // end namespace ento::nonloc
 423
 424 //==------------------------------------------------------------------------==//
 425 //  Subclasses of Loc.
 426 //==------------------------------------------------------------------------==//
 427
 428 namespace loc {
 429
 430 enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind, ObjCPropRefKind };
 431
 432 class GotoLabel : public Loc {
 433 public:
 434   explicit GotoLabel(LabelStmt* Label) : Loc(GotoLabelKind, Label) {}
 435
 436   const LabelStmt* getLabel() const {
 437     return static_cast<const LabelStmt*>(Data);
 438   }
 439
 440   static inline bool classof(const SVal* V) {
 441     return V->getBaseKind() == LocKind &&
 442            V->getSubKind() == GotoLabelKind;
 443   }
 444
 445   static inline bool classof(const Loc* V) {
 446     return V->getSubKind() == GotoLabelKind;
 447   }
 448 };
 449
 450
 451 class MemRegionVal : public Loc {
 452 public:
 453   explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {}
 454
 455   const MemRegion* getRegion() const {
 456     return static_cast<const MemRegion*>(Data);
 457   }
 458
 459   const MemRegion* StripCasts() const;
 460
 461   template <typename REGION>
 462   const REGION* getRegionAs() const {
 463     return llvm::dyn_cast<REGION>(getRegion());
 464   }
 465
 466   inline bool operator==(const MemRegionVal& R) const {
 467     return getRegion() == R.getRegion();
 468   }
 469
 470   inline bool operator!=(const MemRegionVal& R) const {
 471     return getRegion() != R.getRegion();
 472   }
 473
 474   // Implement isa<T> support.
 475   static inline bool classof(const SVal* V) {
 476     return V->getBaseKind() == LocKind &&
 477            V->getSubKind() == MemRegionKind;
 478   }
 479
 480   static inline bool classof(const Loc* V) {
 481     return V->getSubKind() == MemRegionKind;
 482   }
 483 };
 484
 485 class ConcreteInt : public Loc {
 486 public:
 487   explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
 488
 489   const llvm::APSInt& getValue() const {
 490     return *static_cast<const llvm::APSInt*>(Data);
 491   }
 492
 493   // Transfer functions for binary/unary operations on ConcreteInts.
 494   SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
 495                  const ConcreteInt& R) const;
 496
 497   // Implement isa<T> support.
 498   static inline bool classof(const SVal* V) {
 499     return V->getBaseKind() == LocKind &&
 500            V->getSubKind() == ConcreteIntKind;
 501   }
 502
 503   static inline bool classof(const Loc* V) {
 504     return V->getSubKind() == ConcreteIntKind;
 505   }
 506 };
 507
 508 /// \brief Pseudo-location SVal used by the ExprEngine to simulate a "load" or
 509 /// "store" of an ObjC property for the dot syntax.
 510 class ObjCPropRef : public Loc {
 511 public:
 512   explicit ObjCPropRef(const ObjCPropertyRefExpr *E)
 513     : Loc(ObjCPropRefKind, E) {}
 514
 515   const ObjCPropertyRefExpr *getPropRefExpr() const {
 516     return static_cast<const ObjCPropertyRefExpr *>(Data);
 517   }
 518
 519   // Implement isa<T> support.
 520   static inline bool classof(const SVal* V) {
 521     return V->getBaseKind() == LocKind &&
 522            V->getSubKind() == ObjCPropRefKind;
 523   }
 524
 525   static inline bool classof(const Loc* V) {
 526     return V->getSubKind() == ObjCPropRefKind;
 527   }
 528 };
 529
 530 } // end ento::loc namespace
 531 } // end GR namespace
 532
 533 } // end clang namespace
 534
 535 namespace llvm {
 536 static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os,
 537                                             clang::ento::SVal V) {
 538   V.dumpToStream(os);
 539   return os;
 540 }
 541
 542 } // end llvm namespace
 543
 544 #endif