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/StaticAnalyzer/Core/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   explicit SVal(const void* d, bool isLoc, unsigned ValKind)
  67   : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
  68
  69   explicit SVal(BaseKind k, const void* D = NULL)
  70     : Data(D), Kind(k) {}
  71
  72 public:
  73   explicit SVal() : Data(0), Kind(0) {}
  74   ~SVal() {}
  75
  76   /// BufferTy - A temporary buffer to hold a set of SVals.
  77   typedef llvm::SmallVector<SVal,5> BufferTy;
  78
  79   inline unsigned getRawKind() const { return Kind; }
  80   inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
  81   inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
  82
  83   // This method is required for using SVal in a FoldingSetNode.  It
  84   // extracts a unique signature for this SVal object.
  85   inline void Profile(llvm::FoldingSetNodeID& ID) const {
  86     ID.AddInteger((unsigned) getRawKind());
  87     ID.AddPointer(Data);
  88   }
  89
  90   inline bool operator==(const SVal& R) const {
  91     return getRawKind() == R.getRawKind() && Data == R.Data;
  92   }
  93
  94   inline bool operator!=(const SVal& R) const {
  95     return !(*this == R);
  96   }
  97
  98   inline bool isUnknown() const {
  99     return getRawKind() == UnknownKind;
 100   }
 101
 102   inline bool isUndef() const {
 103     return getRawKind() == UndefinedKind;
 104   }
 105
 106   inline bool isUnknownOrUndef() const {
 107     return getRawKind() <= UnknownKind;
 108   }
 109
 110   inline bool isValid() const {
 111     return getRawKind() > UnknownKind;
 112   }
 113
 114   bool isConstant() const;
 115
 116   bool isConstant(int I) const;
 117
 118   bool isZeroConstant() const;
 119
 120   /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true;
 121   bool hasConjuredSymbol() const;
 122
 123   /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a
 124   /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl.
 125   /// Otherwise return 0.
 126   const FunctionDecl* getAsFunctionDecl() const;
 127
 128   /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and
 129   ///  wraps a symbol, return that SymbolRef.  Otherwise return NULL.
 130   SymbolRef getAsLocSymbol() const;
 131
 132   /// Get the symbol in the SVal or its base region.
 133   SymbolRef getLocSymbolInBase() const;
 134
 135   /// getAsSymbol - If this Sval wraps a symbol return that SymbolRef.
 136   ///  Otherwise return a SymbolRef where 'isValid()' returns false.
 137   SymbolRef getAsSymbol() const;
 138
 139   /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
 140   ///  return that expression.  Otherwise return NULL.
 141   const SymExpr *getAsSymbolicExpression() const;
 142
 143   const MemRegion *getAsRegion() const;
 144
 145   void dumpToStream(llvm::raw_ostream& OS) const;
 146   void dump() const;
 147
 148   // Iterators.
 149   class symbol_iterator {
 150     llvm::SmallVector<const SymExpr*, 5> itr;
 151     void expand();
 152   public:
 153     symbol_iterator() {}
 154     symbol_iterator(const SymExpr* SE);
 155
 156     symbol_iterator& operator++();
 157     SymbolRef operator*();
 158
 159     bool operator==(const symbol_iterator& X) const;
 160     bool operator!=(const symbol_iterator& X) const;
 161   };
 162
 163   symbol_iterator symbol_begin() const {
 164     const SymExpr *SE = getAsSymbolicExpression();
 165     if (SE)
 166       return symbol_iterator(SE);
 167     else
 168       return symbol_iterator();
 169   }
 170
 171   symbol_iterator symbol_end() const { return symbol_iterator(); }
 172
 173   // Implement isa<T> support.
 174   static inline bool classof(const SVal*) { return true; }
 175 };
 176
 177
 178 class UndefinedVal : public SVal {
 179 public:
 180   UndefinedVal() : SVal(UndefinedKind) {}
 181   UndefinedVal(const void* D) : SVal(UndefinedKind, D) {}
 182
 183   static inline bool classof(const SVal* V) {
 184     return V->getBaseKind() == UndefinedKind;
 185   }
 186
 187   const void* getData() const { return Data; }
 188 };
 189
 190 class DefinedOrUnknownSVal : public SVal {
 191 private:
 192   // Do not implement.  We want calling these methods to be a compiler
 193   // error since they are tautologically false.
 194   bool isUndef() const;
 195   bool isValid() const;
 196
 197 protected:
 198   explicit DefinedOrUnknownSVal(const void* d, bool isLoc, unsigned ValKind)
 199     : SVal(d, isLoc, ValKind) {}
 200
 201   explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL)
 202     : SVal(k, D) {}
 203
 204 public:
 205     // Implement isa<T> support.
 206   static inline bool classof(const SVal *V) {
 207     return !V->isUndef();
 208   }
 209 };
 210
 211 class UnknownVal : public DefinedOrUnknownSVal {
 212 public:
 213   explicit UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {}
 214
 215   static inline bool classof(const SVal *V) {
 216     return V->getBaseKind() == UnknownKind;
 217   }
 218 };
 219
 220 class DefinedSVal : public DefinedOrUnknownSVal {
 221 private:
 222   // Do not implement.  We want calling these methods to be a compiler
 223   // error since they are tautologically true/false.
 224   bool isUnknown() const;
 225   bool isUnknownOrUndef() const;
 226   bool isValid() const;
 227 protected:
 228   explicit DefinedSVal(const void* d, bool isLoc, unsigned ValKind)
 229     : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
 230 public:
 231   // Implement isa<T> support.
 232   static inline bool classof(const SVal *V) {
 233     return !V->isUnknownOrUndef();
 234   }
 235 };
 236
 237 class NonLoc : public DefinedSVal {
 238 protected:
 239   explicit NonLoc(unsigned SubKind, const void* d)
 240     : DefinedSVal(d, false, SubKind) {}
 241
 242 public:
 243   void dumpToStream(llvm::raw_ostream& Out) const;
 244
 245   // Implement isa<T> support.
 246   static inline bool classof(const SVal* V) {
 247     return V->getBaseKind() == NonLocKind;
 248   }
 249 };
 250
 251 class Loc : public DefinedSVal {
 252 protected:
 253   explicit Loc(unsigned SubKind, const void* D)
 254   : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
 255
 256 public:
 257   void dumpToStream(llvm::raw_ostream& Out) const;
 258
 259   Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {}
 260
 261   // Implement isa<T> support.
 262   static inline bool classof(const SVal* V) {
 263     return V->getBaseKind() == LocKind;
 264   }
 265
 266   static inline bool isLocType(QualType T) {
 267     return T->isAnyPointerType() || T->isBlockPointerType() ||
 268            T->isReferenceType();
 269   }
 270 };
 271
 272 //==------------------------------------------------------------------------==//
 273 //  Subclasses of NonLoc.
 274 //==------------------------------------------------------------------------==//
 275
 276 namespace nonloc {
 277
 278 enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind,
 279             LocAsIntegerKind, CompoundValKind, LazyCompoundValKind };
 280
 281 class SymbolVal : public NonLoc {
 282 public:
 283   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
 284
 285   SymbolRef getSymbol() const {
 286     return (const SymbolData*) Data;
 287   }
 288
 289   static inline bool classof(const SVal* V) {
 290     return V->getBaseKind() == NonLocKind &&
 291            V->getSubKind() == SymbolValKind;
 292   }
 293
 294   static inline bool classof(const NonLoc* V) {
 295     return V->getSubKind() == SymbolValKind;
 296   }
 297 };
 298
 299 class SymExprVal : public NonLoc {
 300 public:
 301   explicit SymExprVal(const SymExpr *SE)
 302     : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {}
 303
 304   const SymExpr *getSymbolicExpression() const {
 305     return reinterpret_cast<const SymExpr*>(Data);
 306   }
 307
 308   static inline bool classof(const SVal* V) {
 309     return V->getBaseKind() == NonLocKind &&
 310            V->getSubKind() == SymExprValKind;
 311   }
 312
 313   static inline bool classof(const NonLoc* V) {
 314     return V->getSubKind() == SymExprValKind;
 315   }
 316 };
 317
 318 class ConcreteInt : public NonLoc {
 319 public:
 320   explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
 321
 322   const llvm::APSInt& getValue() const {
 323     return *static_cast<const llvm::APSInt*>(Data);
 324   }
 325
 326   // Transfer functions for binary/unary operations on ConcreteInts.
 327   SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
 328                  const ConcreteInt& R) const;
 329
 330   ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
 331
 332   ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
 333
 334   // Implement isa<T> support.
 335   static inline bool classof(const SVal* V) {
 336     return V->getBaseKind() == NonLocKind &&
 337            V->getSubKind() == ConcreteIntKind;
 338   }
 339
 340   static inline bool classof(const NonLoc* V) {
 341     return V->getSubKind() == ConcreteIntKind;
 342   }
 343 };
 344
 345 class LocAsInteger : public NonLoc {
 346   friend class ento::SValBuilder;
 347
 348   explicit LocAsInteger(const std::pair<SVal, uintptr_t>& data) :
 349     NonLoc(LocAsIntegerKind, &data) {
 350       assert (isa<Loc>(data.first));
 351     }
 352
 353 public:
 354
 355   Loc getLoc() const {
 356     return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first);
 357   }
 358
 359   const Loc& getPersistentLoc() const {
 360     const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first;
 361     return cast<Loc>(V);
 362   }
 363
 364   unsigned getNumBits() const {
 365     return ((std::pair<SVal, unsigned>*) Data)->second;
 366   }
 367
 368   // Implement isa<T> support.
 369   static inline bool classof(const SVal* V) {
 370     return V->getBaseKind() == NonLocKind &&
 371            V->getSubKind() == LocAsIntegerKind;
 372   }
 373
 374   static inline bool classof(const NonLoc* V) {
 375     return V->getSubKind() == LocAsIntegerKind;
 376   }
 377 };
 378
 379 class CompoundVal : public NonLoc {
 380   friend class ento::SValBuilder;
 381
 382   explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
 383
 384 public:
 385   const CompoundValData* getValue() const {
 386     return static_cast<const CompoundValData*>(Data);
 387   }
 388
 389   typedef llvm::ImmutableList<SVal>::iterator iterator;
 390   iterator begin() const;
 391   iterator end() const;
 392
 393   static bool classof(const SVal* V) {
 394     return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind;
 395   }
 396
 397   static bool classof(const NonLoc* V) {
 398     return V->getSubKind() == CompoundValKind;
 399   }
 400 };
 401
 402 class LazyCompoundVal : public NonLoc {
 403   friend class ento::SValBuilder;
 404
 405   explicit LazyCompoundVal(const LazyCompoundValData *D)
 406     : NonLoc(LazyCompoundValKind, D) {}
 407 public:
 408   const LazyCompoundValData *getCVData() const {
 409     return static_cast<const LazyCompoundValData*>(Data);
 410   }
 411   const void *getStore() const;
 412   const TypedRegion *getRegion() const;
 413
 414   static bool classof(const SVal *V) {
 415     return V->getBaseKind() == NonLocKind &&
 416            V->getSubKind() == LazyCompoundValKind;
 417   }
 418   static bool classof(const NonLoc *V) {
 419     return V->getSubKind() == LazyCompoundValKind;
 420   }
 421 };
 422
 423 } // end namespace ento::nonloc
 424
 425 //==------------------------------------------------------------------------==//
 426 //  Subclasses of Loc.
 427 //==------------------------------------------------------------------------==//
 428
 429 namespace loc {
 430
 431 enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind, ObjCPropRefKind };
 432
 433 class GotoLabel : public Loc {
 434 public:
 435   explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {}
 436
 437   const LabelDecl *getLabel() const {
 438     return static_cast<const LabelDecl*>(Data);
 439   }
 440
 441   static inline bool classof(const SVal* V) {
 442     return V->getBaseKind() == LocKind && 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