contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h

   1 //===- SVals.h - Abstract Values for Static Analysis ------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines SVal, Loc, and NonLoc, classes that represent
  10 //  abstract r-values for use with path-sensitive value tracking.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
  15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
  16
  17 #include "clang/AST/Expr.h"
  18 #include "clang/AST/Type.h"
  19 #include "clang/Basic/LLVM.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
  21 #include "llvm/ADT/FoldingSet.h"
  22 #include "llvm/ADT/ImmutableList.h"
  23 #include "llvm/ADT/None.h"
  24 #include "llvm/ADT/Optional.h"
  25 #include "llvm/ADT/PointerUnion.h"
  26 #include "llvm/Support/Casting.h"
  27 #include <cassert>
  28 #include <cstdint>
  29 #include <utility>
  30
  31 //==------------------------------------------------------------------------==//
  32 //  Base SVal types.
  33 //==------------------------------------------------------------------------==//
  34
  35 namespace clang {
  36
  37 class CXXBaseSpecifier;
  38 class DeclaratorDecl;
  39 class FunctionDecl;
  40 class LabelDecl;
  41
  42 namespace ento {
  43
  44 class BasicValueFactory;
  45 class CompoundValData;
  46 class LazyCompoundValData;
  47 class MemRegion;
  48 class PointerToMemberData;
  49 class SValBuilder;
  50 class TypedValueRegion;
  51
  52 namespace nonloc {
  53
  54 /// Sub-kinds for NonLoc values.
  55 enum Kind {
  56 #define NONLOC_SVAL(Id, Parent) Id ## Kind,
  57 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
  58 };
  59
  60 } // namespace nonloc
  61
  62 namespace loc {
  63
  64 /// Sub-kinds for Loc values.
  65 enum Kind {
  66 #define LOC_SVAL(Id, Parent) Id ## Kind,
  67 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
  68 };
  69
  70 } // namespace loc
  71
  72 /// SVal - This represents a symbolic expression, which can be either
  73 ///  an L-value or an R-value.
  74 ///
  75 class SVal {
  76 public:
  77   enum BaseKind {
  78     // The enumerators must be representable using 2 bits.
  79 #define BASIC_SVAL(Id, Parent) Id ## Kind,
  80 #define ABSTRACT_SVAL_WITH_KIND(Id, Parent) Id ## Kind,
  81 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
  82   };
  83   enum { BaseBits = 2, BaseMask = 0x3 };
  84
  85 protected:
  86   const void *Data = nullptr;
  87
  88   /// The lowest 2 bits are a BaseKind (0 -- 3).
  89   ///  The higher bits are an unsigned "kind" value.
  90   unsigned Kind = 0;
  91
  92   explicit SVal(const void *d, bool isLoc, unsigned ValKind)
  93       : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
  94
  95   explicit SVal(BaseKind k, const void *D = nullptr) : Data(D), Kind(k) {}
  96
  97 public:
  98   explicit SVal() = default;
  99
 100   /// Convert to the specified SVal type, asserting that this SVal is of
 101   /// the desired type.
 102   template<typename T>
 103   T castAs() const {
 104     assert(T::isKind(*this));
 105     return *static_cast<const T *>(this);
 106   }
 107
 108   /// Convert to the specified SVal type, returning None if this SVal is
 109   /// not of the desired type.
 110   template<typename T>
 111   Optional<T> getAs() const {
 112     if (!T::isKind(*this))
 113       return None;
 114     return *static_cast<const T *>(this);
 115   }
 116
 117   unsigned getRawKind() const { return Kind; }
 118   BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
 119   unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
 120
 121   // This method is required for using SVal in a FoldingSetNode.  It
 122   // extracts a unique signature for this SVal object.
 123   void Profile(llvm::FoldingSetNodeID &ID) const {
 124     ID.AddInteger((unsigned) getRawKind());
 125     ID.AddPointer(Data);
 126   }
 127
 128   bool operator==(const SVal &R) const {
 129     return getRawKind() == R.getRawKind() && Data == R.Data;
 130   }
 131
 132   bool operator!=(const SVal &R) const {
 133     return !(*this == R);
 134   }
 135
 136   bool isUnknown() const {
 137     return getRawKind() == UnknownValKind;
 138   }
 139
 140   bool isUndef() const {
 141     return getRawKind() == UndefinedValKind;
 142   }
 143
 144   bool isUnknownOrUndef() const {
 145     return getRawKind() <= UnknownValKind;
 146   }
 147
 148   bool isValid() const {
 149     return getRawKind() > UnknownValKind;
 150   }
 151
 152   bool isConstant() const;
 153
 154   bool isConstant(int I) const;
 155
 156   bool isZeroConstant() const;
 157
 158   /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true;
 159   bool hasConjuredSymbol() const;
 160
 161   /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a
 162   /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl.
 163   /// Otherwise return 0.
 164   const FunctionDecl *getAsFunctionDecl() const;
 165
 166   /// If this SVal is a location and wraps a symbol, return that
 167   ///  SymbolRef. 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 getAsLocSymbol(bool IncludeBaseRegions = false) const;
 173
 174   /// Get the symbol in the SVal or its base region.
 175   SymbolRef getLocSymbolInBase() const;
 176
 177   /// If this SVal wraps a symbol return that SymbolRef.
 178   /// Otherwise, return 0.
 179   ///
 180   /// Casts are ignored during lookup.
 181   /// \param IncludeBaseRegions The boolean that controls whether the search
 182   /// should continue to the base regions if the region is not symbolic.
 183   SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const;
 184
 185   /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
 186   ///  return that expression.  Otherwise return NULL.
 187   const SymExpr *getAsSymbolicExpression() const;
 188
 189   const SymExpr *getAsSymExpr() const;
 190
 191   const MemRegion *getAsRegion() const;
 192
 193   /// printJson - Pretty-prints in JSON format.
 194   void printJson(raw_ostream &Out, bool AddQuotes) const;
 195
 196   void dumpToStream(raw_ostream &OS) const;
 197   void dump() const;
 198
 199   SymExpr::symbol_iterator symbol_begin() const {
 200     const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true);
 201     if (SE)
 202       return SE->symbol_begin();
 203     else
 204       return SymExpr::symbol_iterator();
 205   }
 206
 207   SymExpr::symbol_iterator symbol_end() const {
 208     return SymExpr::symbol_end();
 209   }
 210 };
 211
 212 inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) {
 213   V.dumpToStream(os);
 214   return os;
 215 }
 216
 217 class UndefinedVal : public SVal {
 218 public:
 219   UndefinedVal() : SVal(UndefinedValKind) {}
 220
 221 private:
 222   friend class SVal;
 223
 224   static bool isKind(const SVal& V) {
 225     return V.getBaseKind() == UndefinedValKind;
 226   }
 227 };
 228
 229 class DefinedOrUnknownSVal : public SVal {
 230 public:
 231   // We want calling these methods to be a compiler error since they are
 232   // tautologically false.
 233   bool isUndef() const = delete;
 234   bool isValid() const = delete;
 235
 236 protected:
 237   DefinedOrUnknownSVal() = default;
 238   explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
 239       : SVal(d, isLoc, ValKind) {}
 240   explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr) : SVal(k, D) {}
 241
 242 private:
 243   friend class SVal;
 244
 245   static bool isKind(const SVal& V) {
 246     return !V.isUndef();
 247   }
 248 };
 249
 250 class UnknownVal : public DefinedOrUnknownSVal {
 251 public:
 252   explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {}
 253
 254 private:
 255   friend class SVal;
 256
 257   static bool isKind(const SVal &V) {
 258     return V.getBaseKind() == UnknownValKind;
 259   }
 260 };
 261
 262 class DefinedSVal : public DefinedOrUnknownSVal {
 263 public:
 264   // We want calling these methods to be a compiler error since they are
 265   // tautologically true/false.
 266   bool isUnknown() const = delete;
 267   bool isUnknownOrUndef() const = delete;
 268   bool isValid() const = delete;
 269
 270 protected:
 271   DefinedSVal() = default;
 272   explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
 273       : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
 274
 275 private:
 276   friend class SVal;
 277
 278   static bool isKind(const SVal& V) {
 279     return !V.isUnknownOrUndef();
 280   }
 281 };
 282
 283 /// Represents an SVal that is guaranteed to not be UnknownVal.
 284 class KnownSVal : public SVal {
 285   friend class SVal;
 286
 287   KnownSVal() = default;
 288
 289   static bool isKind(const SVal &V) {
 290     return !V.isUnknown();
 291   }
 292
 293 public:
 294   KnownSVal(const DefinedSVal &V) : SVal(V) {}
 295   KnownSVal(const UndefinedVal &V) : SVal(V) {}
 296 };
 297
 298 class NonLoc : public DefinedSVal {
 299 protected:
 300   NonLoc() = default;
 301   explicit NonLoc(unsigned SubKind, const void *d)
 302       : DefinedSVal(d, false, SubKind) {}
 303
 304 public:
 305   void dumpToStream(raw_ostream &Out) const;
 306
 307   static bool isCompoundType(QualType T) {
 308     return T->isArrayType() || T->isRecordType() ||
 309            T->isAnyComplexType() || T->isVectorType();
 310   }
 311
 312 private:
 313   friend class SVal;
 314
 315   static bool isKind(const SVal& V) {
 316     return V.getBaseKind() == NonLocKind;
 317   }
 318 };
 319
 320 class Loc : public DefinedSVal {
 321 protected:
 322   Loc() = default;
 323   explicit Loc(unsigned SubKind, const void *D)
 324       : DefinedSVal(const_cast<void *>(D), true, SubKind) {}
 325
 326 public:
 327   void dumpToStream(raw_ostream &Out) const;
 328
 329   static bool isLocType(QualType T) {
 330     return T->isAnyPointerType() || T->isBlockPointerType() ||
 331            T->isReferenceType() || T->isNullPtrType();
 332   }
 333
 334 private:
 335   friend class SVal;
 336
 337   static bool isKind(const SVal& V) {
 338     return V.getBaseKind() == LocKind;
 339   }
 340 };
 341
 342 //==------------------------------------------------------------------------==//
 343 //  Subclasses of NonLoc.
 344 //==------------------------------------------------------------------------==//
 345
 346 namespace nonloc {
 347
 348 /// Represents symbolic expression that isn't a location.
 349 class SymbolVal : public NonLoc {
 350 public:
 351   SymbolVal() = delete;
 352   SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {
 353     assert(sym);
 354     assert(!Loc::isLocType(sym->getType()));
 355   }
 356
 357   SymbolRef getSymbol() const {
 358     return (const SymExpr *) Data;
 359   }
 360
 361   bool isExpression() const {
 362     return !isa<SymbolData>(getSymbol());
 363   }
 364
 365 private:
 366   friend class SVal;
 367
 368   static bool isKind(const SVal& V) {
 369     return V.getBaseKind() == NonLocKind &&
 370            V.getSubKind() == SymbolValKind;
 371   }
 372
 373   static bool isKind(const NonLoc& V) {
 374     return V.getSubKind() == SymbolValKind;
 375   }
 376 };
 377
 378 /// Value representing integer constant.
 379 class ConcreteInt : public NonLoc {
 380 public:
 381   explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
 382
 383   const llvm::APSInt& getValue() const {
 384     return *static_cast<const llvm::APSInt *>(Data);
 385   }
 386
 387   // Transfer functions for binary/unary operations on ConcreteInts.
 388   SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
 389                  const ConcreteInt& R) const;
 390
 391   ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
 392
 393   ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
 394
 395 private:
 396   friend class SVal;
 397
 398   ConcreteInt() = default;
 399
 400   static bool isKind(const SVal& V) {
 401     return V.getBaseKind() == NonLocKind &&
 402            V.getSubKind() == ConcreteIntKind;
 403   }
 404
 405   static bool isKind(const NonLoc& V) {
 406     return V.getSubKind() == ConcreteIntKind;
 407   }
 408 };
 409
 410 class LocAsInteger : public NonLoc {
 411   friend class ento::SValBuilder;
 412
 413   explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
 414       : NonLoc(LocAsIntegerKind, &data) {
 415     // We do not need to represent loc::ConcreteInt as LocAsInteger,
 416     // as it'd collapse into a nonloc::ConcreteInt instead.
 417     assert(data.first.getBaseKind() == LocKind &&
 418            (data.first.getSubKind() == loc::MemRegionValKind ||
 419             data.first.getSubKind() == loc::GotoLabelKind));
 420   }
 421
 422 public:
 423   Loc getLoc() const {
 424     const std::pair<SVal, uintptr_t> *D =
 425       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 426     return D->first.castAs<Loc>();
 427   }
 428
 429   Loc getPersistentLoc() const {
 430     const std::pair<SVal, uintptr_t> *D =
 431       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 432     const SVal& V = D->first;
 433     return V.castAs<Loc>();
 434   }
 435
 436   unsigned getNumBits() const {
 437     const std::pair<SVal, uintptr_t> *D =
 438       static_cast<const std::pair<SVal, uintptr_t> *>(Data);
 439     return D->second;
 440   }
 441
 442 private:
 443   friend class SVal;
 444
 445   LocAsInteger() = default;
 446
 447   static bool isKind(const SVal& V) {
 448     return V.getBaseKind() == NonLocKind &&
 449            V.getSubKind() == LocAsIntegerKind;
 450   }
 451
 452   static bool isKind(const NonLoc& V) {
 453     return V.getSubKind() == LocAsIntegerKind;
 454   }
 455 };
 456
 457 class CompoundVal : public NonLoc {
 458   friend class ento::SValBuilder;
 459
 460   explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
 461
 462 public:
 463   const CompoundValData* getValue() const {
 464     return static_cast<const CompoundValData *>(Data);
 465   }
 466
 467   using iterator = llvm::ImmutableList<SVal>::iterator;
 468
 469   iterator begin() const;
 470   iterator end() const;
 471
 472 private:
 473   friend class SVal;
 474
 475   CompoundVal() = default;
 476
 477   static bool isKind(const SVal& V) {
 478     return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
 479   }
 480
 481   static bool isKind(const NonLoc& V) {
 482     return V.getSubKind() == CompoundValKind;
 483   }
 484 };
 485
 486 class LazyCompoundVal : public NonLoc {
 487   friend class ento::SValBuilder;
 488
 489   explicit LazyCompoundVal(const LazyCompoundValData *D)
 490       : NonLoc(LazyCompoundValKind, D) {}
 491
 492 public:
 493   const LazyCompoundValData *getCVData() const {
 494     return static_cast<const LazyCompoundValData *>(Data);
 495   }
 496
 497   const void *getStore() const;
 498   const TypedValueRegion *getRegion() const;
 499
 500 private:
 501   friend class SVal;
 502
 503   LazyCompoundVal() = default;
 504
 505   static bool isKind(const SVal& V) {
 506     return V.getBaseKind() == NonLocKind &&
 507            V.getSubKind() == LazyCompoundValKind;
 508   }
 509
 510   static bool isKind(const NonLoc& V) {
 511     return V.getSubKind() == LazyCompoundValKind;
 512   }
 513 };
 514
 515 /// Value representing pointer-to-member.
 516 ///
 517 /// This value is qualified as NonLoc because neither loading nor storing
 518 /// operations are applied to it. Instead, the analyzer uses the L-value coming
 519 /// from pointer-to-member applied to an object.
 520 /// This SVal is represented by a DeclaratorDecl which can be a member function
 521 /// pointer or a member data pointer and a list of CXXBaseSpecifiers. This list
 522 /// is required to accumulate the pointer-to-member cast history to figure out
 523 /// the correct subobject field.
 524 class PointerToMember : public NonLoc {
 525   friend class ento::SValBuilder;
 526
 527 public:
 528   using PTMDataType =
 529       llvm::PointerUnion<const DeclaratorDecl *, const PointerToMemberData *>;
 530
 531   const PTMDataType getPTMData() const {
 532     return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data));
 533   }
 534
 535   bool isNullMemberPointer() const;
 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 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H