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 "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   /// If this SVal is a location (subclasses Loc) and
 125   /// wraps a symbol, return that SymbolRef.  Otherwise return 0.
 126   SymbolRef getAsLocSymbol() const;
 127
 128   /// Get the symbol in the SVal or its base region.
 129   SymbolRef getLocSymbolInBase() const;
 130
 131   /// If this SVal wraps a symbol return that SymbolRef.
 132   /// Otherwise, return 0.
 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 SymExpr* getAsSymExpr() const;
 140
 141   const MemRegion *getAsRegion() const;
 142
 143   void dumpToStream(raw_ostream &OS) const;
 144   void dump() const;
 145
 146   // Iterators.
 147   class symbol_iterator {
 148     SmallVector<const SymExpr*, 5> itr;
 149     void expand();
 150   public:
 151     symbol_iterator() {}
 152     symbol_iterator(const SymExpr *SE);
 153
 154     symbol_iterator &operator++();
 155     SymbolRef operator*();
 156
 157     bool operator==(const symbol_iterator &X) const;
 158     bool operator!=(const symbol_iterator &X) const;
 159   };
 160
 161   symbol_iterator symbol_begin() const {
 162     const SymExpr *SE = getAsSymbolicExpression();
 163     if (SE)
 164       return symbol_iterator(SE);
 165     else
 166       return symbol_iterator();
 167   }
 168
 169   symbol_iterator symbol_end() const { return symbol_iterator(); }
 170
 171   // Implement isa<T> support.
 172   static inline bool classof(const SVal*) { return true; }
 173 };
 174
 175
 176 class UndefinedVal : public SVal {
 177 public:
 178   UndefinedVal() : SVal(UndefinedKind) {}
 179   UndefinedVal(const void *D) : SVal(UndefinedKind, D) {}
 180
 181   static inline bool classof(const SVal* V) {
 182     return V->getBaseKind() == UndefinedKind;
 183   }
 184
 185   const void *getData() const { return Data; }
 186 };
 187
 188 class DefinedOrUnknownSVal : public SVal {
 189 private:
 190   // Do not implement.  We want calling these methods to be a compiler
 191   // error since they are tautologically false.
 192   bool isUndef() const;
 193   bool isValid() const;
 194
 195 protected:
 196   explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
 197     : SVal(d, isLoc, ValKind) {}
 198
 199   explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL)
 200     : SVal(k, D) {}
 201
 202 public:
 203     // Implement isa<T> support.
 204   static inline bool classof(const SVal *V) {
 205     return !V->isUndef();
 206   }
 207 };
 208
 209 class UnknownVal : public DefinedOrUnknownSVal {
 210 public:
 211   explicit UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {}
 212
 213   static inline bool classof(const SVal *V) {
 214     return V->getBaseKind() == UnknownKind;
 215   }
 216 };
 217
 218 class DefinedSVal : public DefinedOrUnknownSVal {
 219 private:
 220   // Do not implement.  We want calling these methods to be a compiler
 221   // error since they are tautologically true/false.
 222   bool isUnknown() const;
 223   bool isUnknownOrUndef() const;
 224   bool isValid() const;
 225 protected:
 226   explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
 227     : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
 228 public:
 229   // Implement isa<T> support.
 230   static inline bool classof(const SVal *V) {
 231     return !V->isUnknownOrUndef();
 232   }
 233 };
 234
 235 class NonLoc : public DefinedSVal {
 236 protected:
 237   explicit NonLoc(unsigned SubKind, const void *d)
 238     : DefinedSVal(d, false, SubKind) {}
 239
 240 public:
 241   void dumpToStream(raw_ostream &Out) const;
 242
 243   // Implement isa<T> support.
 244   static inline bool classof(const SVal* V) {
 245     return V->getBaseKind() == NonLocKind;
 246   }
 247 };
 248
 249 class Loc : public DefinedSVal {
 250 protected:
 251   explicit Loc(unsigned SubKind, const void *D)
 252   : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
 253
 254 public:
 255   void dumpToStream(raw_ostream &Out) const;
 256
 257   Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {}
 258
 259   // Implement isa<T> support.
 260   static inline bool classof(const SVal* V) {
 261     return V->getBaseKind() == LocKind;
 262   }
 263
 264   static inline bool isLocType(QualType T) {
 265     return T->isAnyPointerType() || T->isBlockPointerType() ||
 266            T->isReferenceType();
 267   }
 268 };
 269
 270 //==------------------------------------------------------------------------==//
 271 //  Subclasses of NonLoc.
 272 //==------------------------------------------------------------------------==//
 273
 274 namespace nonloc {
 275
 276 enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind,
 277             LocAsIntegerKind, CompoundValKind, LazyCompoundValKind };
 278
 279 // TODO: Change to contain symbol data.
 280 class SymbolVal : public NonLoc {
 281 public:
 282   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
 283
 284   SymbolRef getSymbol() const {
 285     return (const SymExpr*) 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(LabelDecl *Label) : Loc(GotoLabelKind, Label) {}
 435
 436   const LabelDecl *getLabel() const {
 437     return static_cast<const LabelDecl*>(Data);
 438   }
 439
 440   static inline bool classof(const SVal* V) {
 441     return V->getBaseKind() == LocKind && V->getSubKind() == GotoLabelKind;
 442   }
 443
 444   static inline bool classof(const Loc* V) {
 445     return V->getSubKind() == GotoLabelKind;
 446   }
 447 };
 448
 449
 450 class MemRegionVal : public Loc {
 451 public:
 452   explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {}
 453
 454   const MemRegion* getRegion() const {
 455     return static_cast<const MemRegion*>(Data);
 456   }
 457
 458   const MemRegion* stripCasts() const;
 459
 460   template <typename REGION>
 461   const REGION* getRegionAs() const {
 462     return llvm::dyn_cast<REGION>(getRegion());
 463   }
 464
 465   inline bool operator==(const MemRegionVal& R) const {
 466     return getRegion() == R.getRegion();
 467   }
 468
 469   inline bool operator!=(const MemRegionVal& R) const {
 470     return getRegion() != R.getRegion();
 471   }
 472
 473   // Implement isa<T> support.
 474   static inline bool classof(const SVal* V) {
 475     return V->getBaseKind() == LocKind &&
 476            V->getSubKind() == MemRegionKind;
 477   }
 478
 479   static inline bool classof(const Loc* V) {
 480     return V->getSubKind() == MemRegionKind;
 481   }
 482 };
 483
 484 class ConcreteInt : public Loc {
 485 public:
 486   explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
 487
 488   const llvm::APSInt& getValue() const {
 489     return *static_cast<const llvm::APSInt*>(Data);
 490   }
 491
 492   // Transfer functions for binary/unary operations on ConcreteInts.
 493   SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
 494                  const ConcreteInt& R) const;
 495
 496   // Implement isa<T> support.
 497   static inline bool classof(const SVal* V) {
 498     return V->getBaseKind() == LocKind &&
 499            V->getSubKind() == ConcreteIntKind;
 500   }
 501
 502   static inline bool classof(const Loc* V) {
 503     return V->getSubKind() == ConcreteIntKind;
 504   }
 505 };
 506
 507 /// \brief Pseudo-location SVal used by the ExprEngine to simulate a "load" or
 508 /// "store" of an ObjC property for the dot syntax.
 509 class ObjCPropRef : public Loc {
 510 public:
 511   explicit ObjCPropRef(const ObjCPropertyRefExpr *E)
 512     : Loc(ObjCPropRefKind, E) {}
 513
 514   const ObjCPropertyRefExpr *getPropRefExpr() const {
 515     return static_cast<const ObjCPropertyRefExpr *>(Data);
 516   }
 517
 518   // Implement isa<T> support.
 519   static inline bool classof(const SVal* V) {
 520     return V->getBaseKind() == LocKind &&
 521            V->getSubKind() == ObjCPropRefKind;
 522   }
 523
 524   static inline bool classof(const Loc* V) {
 525     return V->getSubKind() == ObjCPropRefKind;
 526   }
 527 };
 528
 529 } // end ento::loc namespace
 530 } // end GR namespace
 531
 532 } // end clang namespace
 533
 534 namespace llvm {
 535 static inline raw_ostream &operator<<(raw_ostream &os,
 536                                             clang::ento::SVal V) {
 537   V.dumpToStream(os);
 538   return os;
 539 }
 540
 541 } // end llvm namespace
 542
 543 #endif