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