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