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