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_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
  16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
  17
  18 #include "clang/AST/Expr.h"
  19 #include "clang/Basic/LLVM.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
  22 #include "llvm/ADT/FoldingSet.h"
  23 #include "llvm/ADT/ImmutableList.h"
  24
  25 //==------------------------------------------------------------------------==//
  26 //  Base SVal types.
  27 //==------------------------------------------------------------------------==//
  28
  29 namespace clang {
  30
  31 namespace ento {
  32
  33 class CompoundValData;
  34 class LazyCompoundValData;
  35 class ProgramState;
  36 class BasicValueFactory;
  37 class MemRegion;
  38 class TypedValueRegion;
  39 class MemRegionManager;
  40 class ProgramStateManager;
  41 class SValBuilder;
  42
  43 /// SVal - This represents a symbolic expression, which can be either
  44 ///  an L-value or an R-value.
  45 ///
  46 class SVal {
  47 public:
  48   enum BaseKind {
  49     // The enumerators must be representable using 2 bits.
  50 #define BASIC_SVAL(Id, Parent) Id ## Kind,
  51 #define ABSTRACT_SVAL_WITH_KIND(Id, Parent) Id ## Kind,
  52 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
  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 = nullptr)
  67     : Data(D), Kind(k) {}
  68
  69 public:
  70   explicit SVal() : Data(nullptr), 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() == UnknownValKind;
 119   }
 120
 121   inline bool isUndef() const {
 122     return getRawKind() == UndefinedValKind;
 123   }
 124
 125   inline bool isUnknownOrUndef() const {
 126     return getRawKind() <= UnknownValKind;
 127   }
 128
 129   inline bool isValid() const {
 130     return getRawKind() > UnknownValKind;
 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   /// \brief If this SVal is a location and wraps a symbol, return that
 148   ///  SymbolRef. Otherwise return 0.
 149   ///
 150   /// Casts are ignored during lookup.
 151   /// \param IncludeBaseRegions The boolean that controls whether the search
 152   /// should continue to the base regions if the region is not symbolic.
 153   SymbolRef getAsLocSymbol(bool IncludeBaseRegions = false) const;
 154
 155   /// Get the symbol in the SVal or its base region.
 156   SymbolRef getLocSymbolInBase() const;
 157
 158   /// \brief If this SVal wraps a symbol return that SymbolRef.
 159   /// Otherwise, return 0.
 160   ///
 161   /// Casts are ignored during lookup.
 162   /// \param IncludeBaseRegions The boolean that controls whether the search
 163   /// should continue to the base regions if the region is not symbolic.
 164   SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const;
 165
 166   /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
 167   ///  return that expression.  Otherwise return NULL.
 168   const SymExpr *getAsSymbolicExpression() const;
 169
 170   const SymExpr* getAsSymExpr() const;
 171
 172   const MemRegion *getAsRegion() const;
 173
 174   void dumpToStream(raw_ostream &OS) const;
 175   void dump() const;
 176
 177   SymExpr::symbol_iterator symbol_begin() const {
 178     const SymExpr *SE = getAsSymbolicExpression();
 179     if (SE)
 180       return SE->symbol_begin();
 181     else
 182       return SymExpr::symbol_iterator();
 183   }
 184
 185   SymExpr::symbol_iterator symbol_end() const {
 186     return SymExpr::symbol_end();
 187   }
 188 };
 189
 190
 191 class UndefinedVal : public SVal {
 192 public:
 193   UndefinedVal() : SVal(UndefinedValKind) {}
 194
 195 private:
 196   friend class SVal;
 197   static bool isKind(const SVal& V) {
 198     return V.getBaseKind() == UndefinedValKind;
 199   }
 200 };
 201
 202 class DefinedOrUnknownSVal : public SVal {
 203 private:
 204   // We want calling these methods to be a compiler error since they are
 205   // tautologically false.
 206   bool isUndef() const = delete;
 207   bool isValid() const = delete;
 208
 209 protected:
 210   DefinedOrUnknownSVal() {}
 211   explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
 212     : SVal(d, isLoc, ValKind) {}
 213
 214   explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr)
 215     : SVal(k, D) {}
 216
 217 private:
 218   friend class SVal;
 219   static bool isKind(const SVal& V) {
 220     return !V.isUndef();
 221   }
 222 };
 223
 224 class UnknownVal : public DefinedOrUnknownSVal {
 225 public:
 226   explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {}
 227
 228 private:
 229   friend class SVal;
 230   static bool isKind(const SVal &V) {
 231     return V.getBaseKind() == UnknownValKind;
 232   }
 233 };
 234
 235 class DefinedSVal : public DefinedOrUnknownSVal {
 236 private:
 237   // We want calling these methods to be a compiler error since they are
 238   // tautologically true/false.
 239   bool isUnknown() const = delete;
 240   bool isUnknownOrUndef() const = delete;
 241   bool isValid() const = delete;
 242 protected:
 243   DefinedSVal() {}
 244   explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
 245     : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
 246 private:
 247   friend class SVal;
 248   static bool isKind(const SVal& V) {
 249     return !V.isUnknownOrUndef();
 250   }
 251 };
 252
 253
 254 /// \brief Represents an SVal that is guaranteed to not be UnknownVal.
 255 class KnownSVal : public SVal {
 256   KnownSVal() {}
 257   friend class SVal;
 258   static bool isKind(const SVal &V) {
 259     return !V.isUnknown();
 260   }
 261 public:
 262   KnownSVal(const DefinedSVal &V) : SVal(V) {}
 263   KnownSVal(const UndefinedVal &V) : SVal(V) {}
 264 };
 265
 266 class NonLoc : public DefinedSVal {
 267 protected:
 268   NonLoc() {}
 269   explicit NonLoc(unsigned SubKind, const void *d)
 270     : DefinedSVal(d, false, SubKind) {}
 271
 272 public:
 273   void dumpToStream(raw_ostream &Out) const;
 274
 275 private:
 276   friend class SVal;
 277   static bool isKind(const SVal& V) {
 278     return V.getBaseKind() == NonLocKind;
 279   }
 280 };
 281
 282 class Loc : public DefinedSVal {
 283 protected:
 284   Loc() {}
 285   explicit Loc(unsigned SubKind, const void *D)
 286   : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
 287
 288 public:
 289   void dumpToStream(raw_ostream &Out) const;
 290
 291   static inline bool isLocType(QualType T) {
 292     return T->isAnyPointerType() || T->isBlockPointerType() ||
 293            T->isReferenceType() || T->isNullPtrType();
 294   }
 295
 296 private:
 297   friend class SVal;
 298   static bool isKind(const SVal& V) {
 299     return V.getBaseKind() == LocKind;
 300   }
 301 };
 302
 303 //==------------------------------------------------------------------------==//
 304 //  Subclasses of NonLoc.
 305 //==------------------------------------------------------------------------==//
 306
 307 namespace nonloc {
 308
 309 enum Kind {
 310 #define NONLOC_SVAL(Id, Parent) Id ## Kind,
 311 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
 312 };
 313
 314 /// \brief Represents symbolic expression.
 315 class SymbolVal : public NonLoc {
 316 public:
 317   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
 318
 319   SymbolRef getSymbol() const {
 320     return (const SymExpr*) Data;
 321   }
 322
 323   bool isExpression() const {
 324     return !isa<SymbolData>(getSymbol());
 325   }
 326
 327 private:
 328   friend class SVal;
 329   SymbolVal() {}
 330   static bool isKind(const SVal& V) {
 331     return V.getBaseKind() == NonLocKind &&
 332            V.getSubKind() == SymbolValKind;
 333   }
 334
 335   static bool isKind(const NonLoc& V) {
 336     return V.getSubKind() == SymbolValKind;
 337   }
 338 };
 339
 340 /// \brief Value representing integer constant.
 341 class ConcreteInt : public NonLoc {
 342 public:
 343   explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
 344
 345   const llvm::APSInt& getValue() const {
 346     return *static_cast<const llvm::APSInt*>(Data);
 347   }
 348
 349   // Transfer functions for binary/unary operations on ConcreteInts.
 350   SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
 351                  const ConcreteInt& R) const;
 352
 353   ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
 354
 355   ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
 356
 357 private:
 358   friend class SVal;
 359   ConcreteInt() {}
 360   static bool isKind(const SVal& V) {
 361     return V.getBaseKind() == NonLocKind &&
 362            V.getSubKind() == ConcreteIntKind;
 363   }
 364
 365   static bool isKind(const NonLoc& V) {
 366     return V.getSubKind() == ConcreteIntKind;
 367   }
 368 };
 369
 370 class LocAsInteger : public NonLoc {
 371   friend class ento::SValBuilder;
 372
 373   explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
 374       : NonLoc(LocAsIntegerKind, &data) {
 375     assert (data.first.getAs<Loc>());
 376   }
 377
 378 public:
 379
 380   Loc getLoc() const {
 381     const std::pair<SVal, uintptr_t> *D =
 382       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 383     return D->first.castAs<Loc>();
 384   }
 385
 386   Loc getPersistentLoc() const {
 387     const std::pair<SVal, uintptr_t> *D =
 388       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 389     const SVal& V = D->first;
 390     return V.castAs<Loc>();
 391   }
 392
 393   unsigned getNumBits() const {
 394     const std::pair<SVal, uintptr_t> *D =
 395       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 396     return D->second;
 397   }
 398
 399 private:
 400   friend class SVal;
 401   LocAsInteger() {}
 402   static bool isKind(const SVal& V) {
 403     return V.getBaseKind() == NonLocKind &&
 404            V.getSubKind() == LocAsIntegerKind;
 405   }
 406
 407   static bool isKind(const NonLoc& V) {
 408     return V.getSubKind() == LocAsIntegerKind;
 409   }
 410 };
 411
 412 class CompoundVal : public NonLoc {
 413   friend class ento::SValBuilder;
 414
 415   explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
 416
 417 public:
 418   const CompoundValData* getValue() const {
 419     return static_cast<const CompoundValData*>(Data);
 420   }
 421
 422   typedef llvm::ImmutableList<SVal>::iterator iterator;
 423   iterator begin() const;
 424   iterator end() const;
 425
 426 private:
 427   friend class SVal;
 428   CompoundVal() {}
 429   static bool isKind(const SVal& V) {
 430     return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
 431   }
 432
 433   static bool isKind(const NonLoc& V) {
 434     return V.getSubKind() == CompoundValKind;
 435   }
 436 };
 437
 438 class LazyCompoundVal : public NonLoc {
 439   friend class ento::SValBuilder;
 440
 441   explicit LazyCompoundVal(const LazyCompoundValData *D)
 442     : NonLoc(LazyCompoundValKind, D) {}
 443 public:
 444   const LazyCompoundValData *getCVData() const {
 445     return static_cast<const LazyCompoundValData*>(Data);
 446   }
 447   const void *getStore() const;
 448   const TypedValueRegion *getRegion() const;
 449
 450 private:
 451   friend class SVal;
 452   LazyCompoundVal() {}
 453   static bool isKind(const SVal& V) {
 454     return V.getBaseKind() == NonLocKind &&
 455            V.getSubKind() == LazyCompoundValKind;
 456   }
 457   static bool isKind(const NonLoc& V) {
 458     return V.getSubKind() == LazyCompoundValKind;
 459   }
 460 };
 461
 462 } // end namespace ento::nonloc
 463
 464 //==------------------------------------------------------------------------==//
 465 //  Subclasses of Loc.
 466 //==------------------------------------------------------------------------==//
 467
 468 namespace loc {
 469
 470 enum Kind {
 471 #define LOC_SVAL(Id, Parent) Id ## Kind,
 472 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
 473 };
 474
 475 class GotoLabel : public Loc {
 476 public:
 477   explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {}
 478
 479   const LabelDecl *getLabel() const {
 480     return static_cast<const LabelDecl*>(Data);
 481   }
 482
 483 private:
 484   friend class SVal;
 485   GotoLabel() {}
 486   static bool isKind(const SVal& V) {
 487     return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind;
 488   }
 489
 490   static bool isKind(const Loc& V) {
 491     return V.getSubKind() == GotoLabelKind;
 492   }
 493 };
 494
 495
 496 class MemRegionVal : public Loc {
 497 public:
 498   explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) {}
 499
 500   /// \brief Get the underlining region.
 501   const MemRegion* getRegion() const {
 502     return static_cast<const MemRegion*>(Data);
 503   }
 504
 505   /// \brief Get the underlining region and strip casts.
 506   const MemRegion* stripCasts(bool StripBaseCasts = true) const;
 507
 508   template <typename REGION>
 509   const REGION* getRegionAs() const {
 510     return dyn_cast<REGION>(getRegion());
 511   }
 512
 513   inline bool operator==(const MemRegionVal& R) const {
 514     return getRegion() == R.getRegion();
 515   }
 516
 517   inline bool operator!=(const MemRegionVal& R) const {
 518     return getRegion() != R.getRegion();
 519   }
 520
 521 private:
 522   friend class SVal;
 523   MemRegionVal() {}
 524   static bool isKind(const SVal& V) {
 525     return V.getBaseKind() == LocKind &&
 526            V.getSubKind() == MemRegionValKind;
 527   }
 528
 529   static bool isKind(const Loc& V) {
 530     return V.getSubKind() == MemRegionValKind;
 531   }
 532 };
 533
 534 class ConcreteInt : public Loc {
 535 public:
 536   explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
 537
 538   const llvm::APSInt& getValue() const {
 539     return *static_cast<const llvm::APSInt*>(Data);
 540   }
 541
 542   // Transfer functions for binary/unary operations on ConcreteInts.
 543   SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
 544                  const ConcreteInt& R) const;
 545
 546 private:
 547   friend class SVal;
 548   ConcreteInt() {}
 549   static bool isKind(const SVal& V) {
 550     return V.getBaseKind() == LocKind &&
 551            V.getSubKind() == ConcreteIntKind;
 552   }
 553
 554   static bool isKind(const Loc& V) {
 555     return V.getSubKind() == ConcreteIntKind;
 556   }
 557 };
 558
 559 } // end ento::loc namespace
 560
 561 } // end ento namespace
 562
 563 } // end clang namespace
 564
 565 namespace llvm {
 566 static inline raw_ostream &operator<<(raw_ostream &os,
 567                                             clang::ento::SVal V) {
 568   V.dumpToStream(os);
 569   return os;
 570 }
 571
 572 template <typename T> struct isPodLike;
 573 template <> struct isPodLike<clang::ento::SVal> {
 574   static const bool value = true;
 575 };
 576
 577 } // end llvm namespace
 578
 579 #endif