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