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