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