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