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 PointerToMemberData;
  36 class ProgramState;
  37 class BasicValueFactory;
  38 class MemRegion;
  39 class TypedValueRegion;
  40 class MemRegionManager;
  41 class ProgramStateManager;
  42 class SValBuilder;
  43
  44 namespace nonloc {
  45 /// Sub-kinds for NonLoc values.
  46 enum Kind {
  47 #define NONLOC_SVAL(Id, Parent) Id ## Kind,
  48 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
  49 };
  50 }
  51
  52 namespace loc {
  53 /// Sub-kinds for Loc values.
  54 enum Kind {
  55 #define LOC_SVAL(Id, Parent) Id ## Kind,
  56 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
  57 };
  58 }
  59
  60 /// SVal - This represents a symbolic expression, which can be either
  61 ///  an L-value or an R-value.
  62 ///
  63 class SVal {
  64 public:
  65   enum BaseKind {
  66     // The enumerators must be representable using 2 bits.
  67 #define BASIC_SVAL(Id, Parent) Id ## Kind,
  68 #define ABSTRACT_SVAL_WITH_KIND(Id, Parent) Id ## Kind,
  69 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
  70   };
  71   enum { BaseBits = 2, BaseMask = 0x3 };
  72
  73 protected:
  74   const void *Data;
  75
  76   /// The lowest 2 bits are a BaseKind (0 -- 3).
  77   ///  The higher bits are an unsigned "kind" value.
  78   unsigned Kind;
  79
  80   explicit SVal(const void *d, bool isLoc, unsigned ValKind)
  81   : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
  82
  83   explicit SVal(BaseKind k, const void *D = nullptr)
  84     : Data(D), Kind(k) {}
  85
  86 public:
  87   explicit SVal() : Data(nullptr), Kind(0) {}
  88
  89   /// \brief Convert to the specified SVal type, asserting that this SVal is of
  90   /// the desired type.
  91   template<typename T>
  92   T castAs() const {
  93     assert(T::isKind(*this));
  94     return *static_cast<const T *>(this);
  95   }
  96
  97   /// \brief Convert to the specified SVal type, returning None if this SVal is
  98   /// not of the desired type.
  99   template<typename T>
 100   Optional<T> getAs() const {
 101     if (!T::isKind(*this))
 102       return None;
 103     return *static_cast<const T *>(this);
 104   }
 105
 106   /// BufferTy - A temporary buffer to hold a set of SVals.
 107   typedef SmallVector<SVal,5> BufferTy;
 108
 109   inline unsigned getRawKind() const { return Kind; }
 110   inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
 111   inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
 112
 113   // This method is required for using SVal in a FoldingSetNode.  It
 114   // extracts a unique signature for this SVal object.
 115   inline void Profile(llvm::FoldingSetNodeID& ID) const {
 116     ID.AddInteger((unsigned) getRawKind());
 117     ID.AddPointer(Data);
 118   }
 119
 120   inline bool operator==(const SVal& R) const {
 121     return getRawKind() == R.getRawKind() && Data == R.Data;
 122   }
 123
 124   inline bool operator!=(const SVal& R) const {
 125     return !(*this == R);
 126   }
 127
 128   inline bool isUnknown() const {
 129     return getRawKind() == UnknownValKind;
 130   }
 131
 132   inline bool isUndef() const {
 133     return getRawKind() == UndefinedValKind;
 134   }
 135
 136   inline bool isUnknownOrUndef() const {
 137     return getRawKind() <= UnknownValKind;
 138   }
 139
 140   inline bool isValid() const {
 141     return getRawKind() > UnknownValKind;
 142   }
 143
 144   bool isConstant() const;
 145
 146   bool isConstant(int I) const;
 147
 148   bool isZeroConstant() const;
 149
 150   /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true;
 151   bool hasConjuredSymbol() const;
 152
 153   /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a
 154   /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl.
 155   /// Otherwise return 0.
 156   const FunctionDecl *getAsFunctionDecl() const;
 157
 158   /// \brief If this SVal is a location and wraps a symbol, return that
 159   ///  SymbolRef. 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 getAsLocSymbol(bool IncludeBaseRegions = false) const;
 165
 166   /// Get the symbol in the SVal or its base region.
 167   SymbolRef getLocSymbolInBase() const;
 168
 169   /// \brief If this SVal wraps a symbol return that SymbolRef.
 170   /// Otherwise, return 0.
 171   ///
 172   /// Casts are ignored during lookup.
 173   /// \param IncludeBaseRegions The boolean that controls whether the search
 174   /// should continue to the base regions if the region is not symbolic.
 175   SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const;
 176
 177   /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
 178   ///  return that expression.  Otherwise return NULL.
 179   const SymExpr *getAsSymbolicExpression() const;
 180
 181   const SymExpr* getAsSymExpr() const;
 182
 183   const MemRegion *getAsRegion() const;
 184
 185   void dumpToStream(raw_ostream &OS) const;
 186   void dump() const;
 187
 188   SymExpr::symbol_iterator symbol_begin() const {
 189     const SymExpr *SE = getAsSymbolicExpression();
 190     if (SE)
 191       return SE->symbol_begin();
 192     else
 193       return SymExpr::symbol_iterator();
 194   }
 195
 196   SymExpr::symbol_iterator symbol_end() const {
 197     return SymExpr::symbol_end();
 198   }
 199 };
 200
 201
 202 class UndefinedVal : public SVal {
 203 public:
 204   UndefinedVal() : SVal(UndefinedValKind) {}
 205
 206 private:
 207   friend class SVal;
 208   static bool isKind(const SVal& V) {
 209     return V.getBaseKind() == UndefinedValKind;
 210   }
 211 };
 212
 213 class DefinedOrUnknownSVal : public SVal {
 214 private:
 215   // We want calling these methods to be a compiler error since they are
 216   // tautologically false.
 217   bool isUndef() const = delete;
 218   bool isValid() const = delete;
 219
 220 protected:
 221   DefinedOrUnknownSVal() {}
 222   explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
 223     : SVal(d, isLoc, ValKind) {}
 224
 225   explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr)
 226     : SVal(k, D) {}
 227
 228 private:
 229   friend class SVal;
 230   static bool isKind(const SVal& V) {
 231     return !V.isUndef();
 232   }
 233 };
 234
 235 class UnknownVal : public DefinedOrUnknownSVal {
 236 public:
 237   explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {}
 238
 239 private:
 240   friend class SVal;
 241   static bool isKind(const SVal &V) {
 242     return V.getBaseKind() == UnknownValKind;
 243   }
 244 };
 245
 246 class DefinedSVal : public DefinedOrUnknownSVal {
 247 private:
 248   // We want calling these methods to be a compiler error since they are
 249   // tautologically true/false.
 250   bool isUnknown() const = delete;
 251   bool isUnknownOrUndef() const = delete;
 252   bool isValid() const = delete;
 253 protected:
 254   DefinedSVal() {}
 255   explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
 256     : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
 257 private:
 258   friend class SVal;
 259   static bool isKind(const SVal& V) {
 260     return !V.isUnknownOrUndef();
 261   }
 262 };
 263
 264
 265 /// \brief Represents an SVal that is guaranteed to not be UnknownVal.
 266 class KnownSVal : public SVal {
 267   KnownSVal() {}
 268   friend class SVal;
 269   static bool isKind(const SVal &V) {
 270     return !V.isUnknown();
 271   }
 272 public:
 273   KnownSVal(const DefinedSVal &V) : SVal(V) {}
 274   KnownSVal(const UndefinedVal &V) : SVal(V) {}
 275 };
 276
 277 class NonLoc : public DefinedSVal {
 278 protected:
 279   NonLoc() {}
 280   explicit NonLoc(unsigned SubKind, const void *d)
 281     : DefinedSVal(d, false, SubKind) {}
 282
 283 public:
 284   void dumpToStream(raw_ostream &Out) const;
 285
 286   static inline bool isCompoundType(QualType T) {
 287     return T->isArrayType() || T->isRecordType() ||
 288            T->isComplexType() || T->isVectorType();
 289   }
 290
 291 private:
 292   friend class SVal;
 293   static bool isKind(const SVal& V) {
 294     return V.getBaseKind() == NonLocKind;
 295   }
 296 };
 297
 298 class Loc : public DefinedSVal {
 299 protected:
 300   Loc() {}
 301   explicit Loc(unsigned SubKind, const void *D)
 302   : DefinedSVal(const_cast<void*>(D), true, SubKind) {}
 303
 304 public:
 305   void dumpToStream(raw_ostream &Out) const;
 306
 307   static inline bool isLocType(QualType T) {
 308     return T->isAnyPointerType() || T->isBlockPointerType() ||
 309            T->isReferenceType() || T->isNullPtrType();
 310   }
 311
 312 private:
 313   friend class SVal;
 314   static bool isKind(const SVal& V) {
 315     return V.getBaseKind() == LocKind;
 316   }
 317 };
 318
 319 //==------------------------------------------------------------------------==//
 320 //  Subclasses of NonLoc.
 321 //==------------------------------------------------------------------------==//
 322
 323 namespace nonloc {
 324
 325 /// \brief Represents symbolic expression.
 326 class SymbolVal : public NonLoc {
 327 public:
 328   SymbolVal() = delete;
 329   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) { assert(sym); }
 330
 331   SymbolRef getSymbol() const {
 332     return (const SymExpr*) Data;
 333   }
 334
 335   bool isExpression() const {
 336     return !isa<SymbolData>(getSymbol());
 337   }
 338
 339 private:
 340   friend class SVal;
 341   static bool isKind(const SVal& V) {
 342     return V.getBaseKind() == NonLocKind &&
 343            V.getSubKind() == SymbolValKind;
 344   }
 345
 346   static bool isKind(const NonLoc& V) {
 347     return V.getSubKind() == SymbolValKind;
 348   }
 349 };
 350
 351 /// \brief Value representing integer constant.
 352 class ConcreteInt : public NonLoc {
 353 public:
 354   explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
 355
 356   const llvm::APSInt& getValue() const {
 357     return *static_cast<const llvm::APSInt*>(Data);
 358   }
 359
 360   // Transfer functions for binary/unary operations on ConcreteInts.
 361   SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
 362                  const ConcreteInt& R) const;
 363
 364   ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
 365
 366   ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
 367
 368 private:
 369   friend class SVal;
 370   ConcreteInt() {}
 371   static bool isKind(const SVal& V) {
 372     return V.getBaseKind() == NonLocKind &&
 373            V.getSubKind() == ConcreteIntKind;
 374   }
 375
 376   static bool isKind(const NonLoc& V) {
 377     return V.getSubKind() == ConcreteIntKind;
 378   }
 379 };
 380
 381 class LocAsInteger : public NonLoc {
 382   friend class ento::SValBuilder;
 383
 384   explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
 385       : NonLoc(LocAsIntegerKind, &data) {
 386     // We do not need to represent loc::ConcreteInt as LocAsInteger,
 387     // as it'd collapse into a nonloc::ConcreteInt instead.
 388     assert(data.first.getBaseKind() == LocKind &&
 389            (data.first.getSubKind() == loc::MemRegionValKind ||
 390             data.first.getSubKind() == loc::GotoLabelKind));
 391   }
 392
 393 public:
 394
 395   Loc getLoc() const {
 396     const std::pair<SVal, uintptr_t> *D =
 397       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 398     return D->first.castAs<Loc>();
 399   }
 400
 401   Loc getPersistentLoc() const {
 402     const std::pair<SVal, uintptr_t> *D =
 403       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 404     const SVal& V = D->first;
 405     return V.castAs<Loc>();
 406   }
 407
 408   unsigned getNumBits() const {
 409     const std::pair<SVal, uintptr_t> *D =
 410       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 411     return D->second;
 412   }
 413
 414 private:
 415   friend class SVal;
 416   LocAsInteger() {}
 417   static bool isKind(const SVal& V) {
 418     return V.getBaseKind() == NonLocKind &&
 419            V.getSubKind() == LocAsIntegerKind;
 420   }
 421
 422   static bool isKind(const NonLoc& V) {
 423     return V.getSubKind() == LocAsIntegerKind;
 424   }
 425 };
 426
 427 class CompoundVal : public NonLoc {
 428   friend class ento::SValBuilder;
 429
 430   explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
 431
 432 public:
 433   const CompoundValData* getValue() const {
 434     return static_cast<const CompoundValData*>(Data);
 435   }
 436
 437   typedef llvm::ImmutableList<SVal>::iterator iterator;
 438   iterator begin() const;
 439   iterator end() const;
 440
 441 private:
 442   friend class SVal;
 443   CompoundVal() {}
 444   static bool isKind(const SVal& V) {
 445     return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
 446   }
 447
 448   static bool isKind(const NonLoc& V) {
 449     return V.getSubKind() == CompoundValKind;
 450   }
 451 };
 452
 453 class LazyCompoundVal : public NonLoc {
 454   friend class ento::SValBuilder;
 455
 456   explicit LazyCompoundVal(const LazyCompoundValData *D)
 457     : NonLoc(LazyCompoundValKind, D) {}
 458 public:
 459   const LazyCompoundValData *getCVData() const {
 460     return static_cast<const LazyCompoundValData*>(Data);
 461   }
 462   const void *getStore() const;
 463   const TypedValueRegion *getRegion() const;
 464
 465 private:
 466   friend class SVal;
 467   LazyCompoundVal() {}
 468   static bool isKind(const SVal& V) {
 469     return V.getBaseKind() == NonLocKind &&
 470            V.getSubKind() == LazyCompoundValKind;
 471   }
 472   static bool isKind(const NonLoc& V) {
 473     return V.getSubKind() == LazyCompoundValKind;
 474   }
 475 };
 476
 477 /// \brief Value representing pointer-to-member.
 478 ///
 479 /// This value is qualified as NonLoc because neither loading nor storing
 480 /// operations are aplied to it. Instead, the analyzer uses the L-value coming
 481 /// from pointer-to-member applied to an object.
 482 /// This SVal is represented by a DeclaratorDecl which can be a member function
 483 /// pointer or a member data pointer and a list of CXXBaseSpecifiers. This list
 484 /// is required to accumulate the pointer-to-member cast history to figure out
 485 /// the correct subobject field.
 486 class PointerToMember : public NonLoc {
 487   friend class ento::SValBuilder;
 488
 489 public:
 490   typedef llvm::PointerUnion<const DeclaratorDecl *,
 491                              const PointerToMemberData *> PTMDataType;
 492   const PTMDataType getPTMData() const {
 493     return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data));
 494   }
 495   bool isNullMemberPointer() const {
 496     return getPTMData().isNull();
 497   }
 498   const DeclaratorDecl *getDecl() const;
 499   template<typename AdjustedDecl>
 500   const AdjustedDecl* getDeclAs() const {
 501     return dyn_cast_or_null<AdjustedDecl>(getDecl());
 502   }
 503   typedef llvm::ImmutableList<const CXXBaseSpecifier *>::iterator iterator;
 504   iterator begin() const;
 505   iterator end() const;
 506
 507 private:
 508   explicit PointerToMember(const PTMDataType D)
 509     : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {}
 510   friend class SVal;
 511   PointerToMember() {}
 512   static bool isKind(const SVal& V) {
 513     return V.getBaseKind() == NonLocKind &&
 514            V.getSubKind() == PointerToMemberKind;
 515   }
 516
 517   static bool isKind(const NonLoc& V) {
 518     return V.getSubKind() == PointerToMemberKind;
 519   }
 520 };
 521
 522 } // end namespace ento::nonloc
 523
 524 //==------------------------------------------------------------------------==//
 525 //  Subclasses of Loc.
 526 //==------------------------------------------------------------------------==//
 527
 528 namespace loc {
 529
 530 class GotoLabel : public Loc {
 531 public:
 532   explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) {
 533     assert(Label);
 534   }
 535
 536   const LabelDecl *getLabel() const {
 537     return static_cast<const LabelDecl*>(Data);
 538   }
 539
 540 private:
 541   friend class SVal;
 542   GotoLabel() {}
 543   static bool isKind(const SVal& V) {
 544     return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind;
 545   }
 546
 547   static bool isKind(const Loc& V) {
 548     return V.getSubKind() == GotoLabelKind;
 549   }
 550 };
 551
 552
 553 class MemRegionVal : public Loc {
 554 public:
 555   explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) {
 556     assert(r);
 557   }
 558
 559   /// \brief Get the underlining region.
 560   const MemRegion* getRegion() const {
 561     return static_cast<const MemRegion*>(Data);
 562   }
 563
 564   /// \brief Get the underlining region and strip casts.
 565   const MemRegion* stripCasts(bool StripBaseCasts = true) const;
 566
 567   template <typename REGION>
 568   const REGION* getRegionAs() const {
 569     return dyn_cast<REGION>(getRegion());
 570   }
 571
 572   inline bool operator==(const MemRegionVal& R) const {
 573     return getRegion() == R.getRegion();
 574   }
 575
 576   inline bool operator!=(const MemRegionVal& R) const {
 577     return getRegion() != R.getRegion();
 578   }
 579
 580 private:
 581   friend class SVal;
 582   MemRegionVal() {}
 583   static bool isKind(const SVal& V) {
 584     return V.getBaseKind() == LocKind &&
 585            V.getSubKind() == MemRegionValKind;
 586   }
 587
 588   static bool isKind(const Loc& V) {
 589     return V.getSubKind() == MemRegionValKind;
 590   }
 591 };
 592
 593 class ConcreteInt : public Loc {
 594 public:
 595   explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
 596
 597   const llvm::APSInt& getValue() const {
 598     return *static_cast<const llvm::APSInt*>(Data);
 599   }
 600
 601   // Transfer functions for binary/unary operations on ConcreteInts.
 602   SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
 603                  const ConcreteInt& R) const;
 604
 605 private:
 606   friend class SVal;
 607   ConcreteInt() {}
 608   static bool isKind(const SVal& V) {
 609     return V.getBaseKind() == LocKind &&
 610            V.getSubKind() == ConcreteIntKind;
 611   }
 612
 613   static bool isKind(const Loc& V) {
 614     return V.getSubKind() == ConcreteIntKind;
 615   }
 616 };
 617
 618 } // end ento::loc namespace
 619
 620 } // end ento namespace
 621
 622 } // end clang namespace
 623
 624 namespace llvm {
 625 static inline raw_ostream &operator<<(raw_ostream &os,
 626                                             clang::ento::SVal V) {
 627   V.dumpToStream(os);
 628   return os;
 629 }
 630
 631 template <typename T> struct isPodLike;
 632 template <> struct isPodLike<clang::ento::SVal> {
 633   static const bool value = true;
 634 };
 635
 636 } // end llvm namespace
 637
 638 #endif