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/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 Optional<T>();
  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 class NonLoc : public DefinedSVal {
 246 protected:
 247   NonLoc() {}
 248   explicit NonLoc(unsigned SubKind, const void *d)
 249     : DefinedSVal(d, false, SubKind) {}
 250
 251 public:
 252   void dumpToStream(raw_ostream &Out) const;
 253
 254 private:
 255   friend class SVal;
 256   static bool isKind(const SVal& V) {
 257     return V.getBaseKind() == NonLocKind;
 258   }
 259 };
 260
 261 class Loc : public DefinedSVal {
 262 protected:
 263   Loc() {}
 264   explicit Loc(unsigned SubKind, const void *D)
 265   : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
 266
 267 public:
 268   void dumpToStream(raw_ostream &Out) const;
 269
 270   static inline bool isLocType(QualType T) {
 271     return T->isAnyPointerType() || T->isBlockPointerType() ||
 272            T->isReferenceType();
 273   }
 274
 275 private:
 276   friend class SVal;
 277   static bool isKind(const SVal& V) {
 278     return V.getBaseKind() == LocKind;
 279   }
 280 };
 281
 282 //==------------------------------------------------------------------------==//
 283 //  Subclasses of NonLoc.
 284 //==------------------------------------------------------------------------==//
 285
 286 namespace nonloc {
 287
 288 enum Kind { ConcreteIntKind, SymbolValKind,
 289             LocAsIntegerKind, CompoundValKind, LazyCompoundValKind };
 290
 291 /// \brief Represents symbolic expression.
 292 class SymbolVal : public NonLoc {
 293 public:
 294   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
 295
 296   SymbolRef getSymbol() const {
 297     return (const SymExpr*) Data;
 298   }
 299
 300   bool isExpression() const {
 301     return !isa<SymbolData>(getSymbol());
 302   }
 303
 304 private:
 305   friend class SVal;
 306   SymbolVal() {}
 307   static bool isKind(const SVal& V) {
 308     return V.getBaseKind() == NonLocKind &&
 309            V.getSubKind() == SymbolValKind;
 310   }
 311
 312   static bool isKind(const NonLoc& V) {
 313     return V.getSubKind() == SymbolValKind;
 314   }
 315 };
 316
 317 /// \brief Value representing integer constant.
 318 class ConcreteInt : public NonLoc {
 319 public:
 320   explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
 321
 322   const llvm::APSInt& getValue() const {
 323     return *static_cast<const llvm::APSInt*>(Data);
 324   }
 325
 326   // Transfer functions for binary/unary operations on ConcreteInts.
 327   SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
 328                  const ConcreteInt& R) const;
 329
 330   ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
 331
 332   ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
 333
 334 private:
 335   friend class SVal;
 336   ConcreteInt() {}
 337   static bool isKind(const SVal& V) {
 338     return V.getBaseKind() == NonLocKind &&
 339            V.getSubKind() == ConcreteIntKind;
 340   }
 341
 342   static bool isKind(const NonLoc& V) {
 343     return V.getSubKind() == ConcreteIntKind;
 344   }
 345 };
 346
 347 class LocAsInteger : public NonLoc {
 348   friend class ento::SValBuilder;
 349
 350   explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
 351       : NonLoc(LocAsIntegerKind, &data) {
 352     assert (data.first.getAs<Loc>());
 353   }
 354
 355 public:
 356
 357   Loc getLoc() const {
 358     const std::pair<SVal, uintptr_t> *D =
 359       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 360     return D->first.castAs<Loc>();
 361   }
 362
 363   Loc getPersistentLoc() const {
 364     const std::pair<SVal, uintptr_t> *D =
 365       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 366     const SVal& V = D->first;
 367     return V.castAs<Loc>();
 368   }
 369
 370   unsigned getNumBits() const {
 371     const std::pair<SVal, uintptr_t> *D =
 372       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 373     return D->second;
 374   }
 375
 376 private:
 377   friend class SVal;
 378   LocAsInteger() {}
 379   static bool isKind(const SVal& V) {
 380     return V.getBaseKind() == NonLocKind &&
 381            V.getSubKind() == LocAsIntegerKind;
 382   }
 383
 384   static bool isKind(const NonLoc& V) {
 385     return V.getSubKind() == LocAsIntegerKind;
 386   }
 387 };
 388
 389 class CompoundVal : public NonLoc {
 390   friend class ento::SValBuilder;
 391
 392   explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
 393
 394 public:
 395   const CompoundValData* getValue() const {
 396     return static_cast<const CompoundValData*>(Data);
 397   }
 398
 399   typedef llvm::ImmutableList<SVal>::iterator iterator;
 400   iterator begin() const;
 401   iterator end() const;
 402
 403 private:
 404   friend class SVal;
 405   CompoundVal() {}
 406   static bool isKind(const SVal& V) {
 407     return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
 408   }
 409
 410   static bool isKind(const NonLoc& V) {
 411     return V.getSubKind() == CompoundValKind;
 412   }
 413 };
 414
 415 class LazyCompoundVal : public NonLoc {
 416   friend class ento::SValBuilder;
 417
 418   explicit LazyCompoundVal(const LazyCompoundValData *D)
 419     : NonLoc(LazyCompoundValKind, D) {}
 420 public:
 421   const LazyCompoundValData *getCVData() const {
 422     return static_cast<const LazyCompoundValData*>(Data);
 423   }
 424   const void *getStore() const;
 425   const TypedValueRegion *getRegion() const;
 426
 427 private:
 428   friend class SVal;
 429   LazyCompoundVal() {}
 430   static bool isKind(const SVal& V) {
 431     return V.getBaseKind() == NonLocKind &&
 432            V.getSubKind() == LazyCompoundValKind;
 433   }
 434   static bool isKind(const NonLoc& V) {
 435     return V.getSubKind() == LazyCompoundValKind;
 436   }
 437 };
 438
 439 } // end namespace ento::nonloc
 440
 441 //==------------------------------------------------------------------------==//
 442 //  Subclasses of Loc.
 443 //==------------------------------------------------------------------------==//
 444
 445 namespace loc {
 446
 447 enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind };
 448
 449 class GotoLabel : public Loc {
 450 public:
 451   explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {}
 452
 453   const LabelDecl *getLabel() const {
 454     return static_cast<const LabelDecl*>(Data);
 455   }
 456
 457 private:
 458   friend class SVal;
 459   GotoLabel() {}
 460   static bool isKind(const SVal& V) {
 461     return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind;
 462   }
 463
 464   static bool isKind(const Loc& V) {
 465     return V.getSubKind() == GotoLabelKind;
 466   }
 467 };
 468
 469
 470 class MemRegionVal : public Loc {
 471 public:
 472   explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {}
 473
 474   /// \brief Get the underlining region.
 475   const MemRegion* getRegion() const {
 476     return static_cast<const MemRegion*>(Data);
 477   }
 478
 479   /// \brief Get the underlining region and strip casts.
 480   const MemRegion* stripCasts(bool StripBaseCasts = true) const;
 481
 482   template <typename REGION>
 483   const REGION* getRegionAs() const {
 484     return dyn_cast<REGION>(getRegion());
 485   }
 486
 487   inline bool operator==(const MemRegionVal& R) const {
 488     return getRegion() == R.getRegion();
 489   }
 490
 491   inline bool operator!=(const MemRegionVal& R) const {
 492     return getRegion() != R.getRegion();
 493   }
 494
 495 private:
 496   friend class SVal;
 497   MemRegionVal() {}
 498   static bool isKind(const SVal& V) {
 499     return V.getBaseKind() == LocKind &&
 500            V.getSubKind() == MemRegionKind;
 501   }
 502
 503   static bool isKind(const Loc& V) {
 504     return V.getSubKind() == MemRegionKind;
 505   }
 506 };
 507
 508 class ConcreteInt : public Loc {
 509 public:
 510   explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
 511
 512   const llvm::APSInt& getValue() const {
 513     return *static_cast<const llvm::APSInt*>(Data);
 514   }
 515
 516   // Transfer functions for binary/unary operations on ConcreteInts.
 517   SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
 518                  const ConcreteInt& R) const;
 519
 520 private:
 521   friend class SVal;
 522   ConcreteInt() {}
 523   static bool isKind(const SVal& V) {
 524     return V.getBaseKind() == LocKind &&
 525            V.getSubKind() == ConcreteIntKind;
 526   }
 527
 528   static bool isKind(const Loc& V) {
 529     return V.getSubKind() == ConcreteIntKind;
 530   }
 531 };
 532
 533 } // end ento::loc namespace
 534 } // end GR namespace
 535
 536 } // end clang namespace
 537
 538 namespace llvm {
 539 static inline raw_ostream &operator<<(raw_ostream &os,
 540                                             clang::ento::SVal V) {
 541   V.dumpToStream(os);
 542   return os;
 543 }
 544
 545 } // end llvm namespace
 546
 547 #endif