granicus.if.org Git - clang/blob - 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   /// \brief If this SVal is a MemRegionVal and wraps a VarDecl,
 129   /// return that VarDecl. Otherwise return 0.
 130   const VarDecl* getAsVarDecl() const;
 131
 132   /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and
 133   ///  wraps a symbol, return that SymbolRef.  Otherwise return NULL.
 134   SymbolRef getAsLocSymbol() const;
 135
 136   /// Get the symbol in the SVal or its base region.
 137   SymbolRef getLocSymbolInBase() const;
 138
 139   /// getAsSymbol - If this Sval wraps a symbol return that SymbolRef.
 140   ///  Otherwise return a SymbolRef where 'isValid()' returns false.
 141   SymbolRef getAsSymbol() const;
 142
 143   /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
 144   ///  return that expression.  Otherwise return NULL.
 145   const SymExpr *getAsSymbolicExpression() const;
 146
 147   const MemRegion *getAsRegion() const;
 148
 149   void dumpToStream(llvm::raw_ostream& OS) const;
 150   void dump() const;
 151
 152   // Iterators.
 153   class symbol_iterator {
 154     llvm::SmallVector<const SymExpr*, 5> itr;
 155     void expand();
 156   public:
 157     symbol_iterator() {}
 158     symbol_iterator(const SymExpr* SE);
 159
 160     symbol_iterator& operator++();
 161     SymbolRef operator*();
 162
 163     bool operator==(const symbol_iterator& X) const;
 164     bool operator!=(const symbol_iterator& X) const;
 165   };
 166
 167   symbol_iterator symbol_begin() const {
 168     const SymExpr *SE = getAsSymbolicExpression();
 169     if (SE)
 170       return symbol_iterator(SE);
 171     else
 172       return symbol_iterator();
 173   }
 174
 175   symbol_iterator symbol_end() const { return symbol_iterator(); }
 176
 177   // Implement isa<T> support.
 178   static inline bool classof(const SVal*) { return true; }
 179 };
 180
 181
 182 class UndefinedVal : public SVal {
 183 public:
 184   UndefinedVal() : SVal(UndefinedKind) {}
 185   UndefinedVal(const void* D) : SVal(UndefinedKind, D) {}
 186
 187   static inline bool classof(const SVal* V) {
 188     return V->getBaseKind() == UndefinedKind;
 189   }
 190
 191   const void* getData() const { return Data; }
 192 };
 193
 194 class DefinedOrUnknownSVal : public SVal {
 195 private:
 196   // Do not implement.  We want calling these methods to be a compiler
 197   // error since they are tautologically false.
 198   bool isUndef() const;
 199   bool isValid() const;
 200
 201 protected:
 202   explicit DefinedOrUnknownSVal(const void* d, bool isLoc, unsigned ValKind)
 203     : SVal(d, isLoc, ValKind) {}
 204
 205   explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL)
 206     : SVal(k, D) {}
 207
 208 public:
 209     // Implement isa<T> support.
 210   static inline bool classof(const SVal *V) {
 211     return !V->isUndef();
 212   }
 213 };
 214
 215 class UnknownVal : public DefinedOrUnknownSVal {
 216 public:
 217   explicit UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {}
 218
 219   static inline bool classof(const SVal *V) {
 220     return V->getBaseKind() == UnknownKind;
 221   }
 222 };
 223
 224 class DefinedSVal : public DefinedOrUnknownSVal {
 225 private:
 226   // Do not implement.  We want calling these methods to be a compiler
 227   // error since they are tautologically true/false.
 228   bool isUnknown() const;
 229   bool isUnknownOrUndef() const;
 230   bool isValid() const;
 231 protected:
 232   explicit DefinedSVal(const void* d, bool isLoc, unsigned ValKind)
 233     : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
 234 public:
 235   // Implement isa<T> support.
 236   static inline bool classof(const SVal *V) {
 237     return !V->isUnknownOrUndef();
 238   }
 239 };
 240
 241 class NonLoc : public DefinedSVal {
 242 protected:
 243   explicit NonLoc(unsigned SubKind, const void* d)
 244     : DefinedSVal(d, false, SubKind) {}
 245
 246 public:
 247   void dumpToStream(llvm::raw_ostream& Out) const;
 248
 249   // Implement isa<T> support.
 250   static inline bool classof(const SVal* V) {
 251     return V->getBaseKind() == NonLocKind;
 252   }
 253 };
 254
 255 class Loc : public DefinedSVal {
 256 protected:
 257   explicit Loc(unsigned SubKind, const void* D)
 258   : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
 259
 260 public:
 261   void dumpToStream(llvm::raw_ostream& Out) const;
 262
 263   Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {}
 264
 265   // Implement isa<T> support.
 266   static inline bool classof(const SVal* V) {
 267     return V->getBaseKind() == LocKind;
 268   }
 269
 270   static inline bool isLocType(QualType T) {
 271     return T->isAnyPointerType() || T->isBlockPointerType() ||
 272            T->isReferenceType();
 273   }
 274 };
 275
 276 //==------------------------------------------------------------------------==//
 277 //  Subclasses of NonLoc.
 278 //==------------------------------------------------------------------------==//
 279
 280 namespace nonloc {
 281
 282 enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind,
 283             LocAsIntegerKind, CompoundValKind, LazyCompoundValKind };
 284
 285 class SymbolVal : public NonLoc {
 286 public:
 287   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
 288
 289   SymbolRef getSymbol() const {
 290     return (const SymbolData*) Data;
 291   }
 292
 293   static inline bool classof(const SVal* V) {
 294     return V->getBaseKind() == NonLocKind &&
 295            V->getSubKind() == SymbolValKind;
 296   }
 297
 298   static inline bool classof(const NonLoc* V) {
 299     return V->getSubKind() == SymbolValKind;
 300   }
 301 };
 302
 303 class SymExprVal : public NonLoc {
 304 public:
 305   explicit SymExprVal(const SymExpr *SE)
 306     : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {}
 307
 308   const SymExpr *getSymbolicExpression() const {
 309     return reinterpret_cast<const SymExpr*>(Data);
 310   }
 311
 312   static inline bool classof(const SVal* V) {
 313     return V->getBaseKind() == NonLocKind &&
 314            V->getSubKind() == SymExprValKind;
 315   }
 316
 317   static inline bool classof(const NonLoc* V) {
 318     return V->getSubKind() == SymExprValKind;
 319   }
 320 };
 321
 322 class ConcreteInt : public NonLoc {
 323 public:
 324   explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
 325
 326   const llvm::APSInt& getValue() const {
 327     return *static_cast<const llvm::APSInt*>(Data);
 328   }
 329
 330   // Transfer functions for binary/unary operations on ConcreteInts.
 331   SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
 332                  const ConcreteInt& R) const;
 333
 334   ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
 335
 336   ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
 337
 338   // Implement isa<T> support.
 339   static inline bool classof(const SVal* V) {
 340     return V->getBaseKind() == NonLocKind &&
 341            V->getSubKind() == ConcreteIntKind;
 342   }
 343
 344   static inline bool classof(const NonLoc* V) {
 345     return V->getSubKind() == ConcreteIntKind;
 346   }
 347 };
 348
 349 class LocAsInteger : public NonLoc {
 350   friend class ento::SValBuilder;
 351
 352   explicit LocAsInteger(const std::pair<SVal, uintptr_t>& data) :
 353     NonLoc(LocAsIntegerKind, &data) {
 354       assert (isa<Loc>(data.first));
 355     }
 356
 357 public:
 358
 359   Loc getLoc() const {
 360     return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first);
 361   }
 362
 363   const Loc& getPersistentLoc() const {
 364     const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first;
 365     return cast<Loc>(V);
 366   }
 367
 368   unsigned getNumBits() const {
 369     return ((std::pair<SVal, unsigned>*) Data)->second;
 370   }
 371
 372   // Implement isa<T> support.
 373   static inline bool classof(const SVal* V) {
 374     return V->getBaseKind() == NonLocKind &&
 375            V->getSubKind() == LocAsIntegerKind;
 376   }
 377
 378   static inline bool classof(const NonLoc* V) {
 379     return V->getSubKind() == LocAsIntegerKind;
 380   }
 381 };
 382
 383 class CompoundVal : public NonLoc {
 384   friend class ento::SValBuilder;
 385
 386   explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
 387
 388 public:
 389   const CompoundValData* getValue() const {
 390     return static_cast<const CompoundValData*>(Data);
 391   }
 392
 393   typedef llvm::ImmutableList<SVal>::iterator iterator;
 394   iterator begin() const;
 395   iterator end() const;
 396
 397   static bool classof(const SVal* V) {
 398     return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind;
 399   }
 400
 401   static bool classof(const NonLoc* V) {
 402     return V->getSubKind() == CompoundValKind;
 403   }
 404 };
 405
 406 class LazyCompoundVal : public NonLoc {
 407   friend class ento::SValBuilder;
 408
 409   explicit LazyCompoundVal(const LazyCompoundValData *D)
 410     : NonLoc(LazyCompoundValKind, D) {}
 411 public:
 412   const LazyCompoundValData *getCVData() const {
 413     return static_cast<const LazyCompoundValData*>(Data);
 414   }
 415   const void *getStore() const;
 416   const TypedRegion *getRegion() const;
 417
 418   static bool classof(const SVal *V) {
 419     return V->getBaseKind() == NonLocKind &&
 420            V->getSubKind() == LazyCompoundValKind;
 421   }
 422   static bool classof(const NonLoc *V) {
 423     return V->getSubKind() == LazyCompoundValKind;
 424   }
 425 };
 426
 427 } // end namespace ento::nonloc
 428
 429 //==------------------------------------------------------------------------==//
 430 //  Subclasses of Loc.
 431 //==------------------------------------------------------------------------==//
 432
 433 namespace loc {
 434
 435 enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind, ObjCPropRefKind };
 436
 437 class GotoLabel : public Loc {
 438 public:
 439   explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {}
 440
 441   const LabelDecl *getLabel() const {
 442     return static_cast<const LabelDecl*>(Data);
 443   }
 444
 445   static inline bool classof(const SVal* V) {
 446     return V->getBaseKind() == LocKind && V->getSubKind() == GotoLabelKind;
 447   }
 448
 449   static inline bool classof(const Loc* V) {
 450     return V->getSubKind() == GotoLabelKind;
 451   }
 452 };
 453
 454
 455 class MemRegionVal : public Loc {
 456 public:
 457   explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {}
 458
 459   const MemRegion* getRegion() const {
 460     return static_cast<const MemRegion*>(Data);
 461   }
 462
 463   const MemRegion* stripCasts() const;
 464
 465   template <typename REGION>
 466   const REGION* getRegionAs() const {
 467     return llvm::dyn_cast<REGION>(getRegion());
 468   }
 469
 470   inline bool operator==(const MemRegionVal& R) const {
 471     return getRegion() == R.getRegion();
 472   }
 473
 474   inline bool operator!=(const MemRegionVal& R) const {
 475     return getRegion() != R.getRegion();
 476   }
 477
 478   // Implement isa<T> support.
 479   static inline bool classof(const SVal* V) {
 480     return V->getBaseKind() == LocKind &&
 481            V->getSubKind() == MemRegionKind;
 482   }
 483
 484   static inline bool classof(const Loc* V) {
 485     return V->getSubKind() == MemRegionKind;
 486   }
 487 };
 488
 489 class ConcreteInt : public Loc {
 490 public:
 491   explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
 492
 493   const llvm::APSInt& getValue() const {
 494     return *static_cast<const llvm::APSInt*>(Data);
 495   }
 496
 497   // Transfer functions for binary/unary operations on ConcreteInts.
 498   SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
 499                  const ConcreteInt& R) const;
 500
 501   // Implement isa<T> support.
 502   static inline bool classof(const SVal* V) {
 503     return V->getBaseKind() == LocKind &&
 504            V->getSubKind() == ConcreteIntKind;
 505   }
 506
 507   static inline bool classof(const Loc* V) {
 508     return V->getSubKind() == ConcreteIntKind;
 509   }
 510 };
 511
 512 /// \brief Pseudo-location SVal used by the ExprEngine to simulate a "load" or
 513 /// "store" of an ObjC property for the dot syntax.
 514 class ObjCPropRef : public Loc {
 515 public:
 516   explicit ObjCPropRef(const ObjCPropertyRefExpr *E)
 517     : Loc(ObjCPropRefKind, E) {}
 518
 519   const ObjCPropertyRefExpr *getPropRefExpr() const {
 520     return static_cast<const ObjCPropertyRefExpr *>(Data);
 521   }
 522
 523   // Implement isa<T> support.
 524   static inline bool classof(const SVal* V) {
 525     return V->getBaseKind() == LocKind &&
 526            V->getSubKind() == ObjCPropRefKind;
 527   }
 528
 529   static inline bool classof(const Loc* V) {
 530     return V->getSubKind() == ObjCPropRefKind;
 531   }
 532 };
 533
 534 } // end ento::loc namespace
 535 } // end GR namespace
 536
 537 } // end clang namespace
 538
 539 namespace llvm {
 540 static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os,
 541                                             clang::ento::SVal V) {
 542   V.dumpToStream(os);
 543   return os;
 544 }
 545
 546 } // end llvm namespace
 547
 548 #endif