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