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