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 = 0b11 }; 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 SVal(const void * d,bool isLoc,unsigned ValKind)92 explicit SVal(const void *d, bool isLoc, unsigned ValKind) 93 : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} 94 Data(D)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> castAs()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> getAs()111 Optional<T> getAs() const { 112 if (!T::isKind(*this)) 113 return None; 114 return *static_cast<const T *>(this); 115 } 116 getRawKind()117 unsigned getRawKind() const { return Kind; } getBaseKind()118 BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); } getSubKind()119 unsigned getSubKind() const { return Kind >> BaseBits; } 120 121 // This method is required for using SVal in a FoldingSetNode. It 122 // extracts a unique signature for this SVal object. Profile(llvm::FoldingSetNodeID & ID)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 isUnknown()136 bool isUnknown() const { 137 return getRawKind() == UnknownValKind; 138 } 139 isUndef()140 bool isUndef() const { 141 return getRawKind() == UndefinedValKind; 142 } 143 isUnknownOrUndef()144 bool isUnknownOrUndef() const { 145 return getRawKind() <= UnknownValKind; 146 } 147 isValid()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 const MemRegion *getAsRegion() const; 186 187 /// printJson - Pretty-prints in JSON format. 188 void printJson(raw_ostream &Out, bool AddQuotes) const; 189 190 void dumpToStream(raw_ostream &OS) const; 191 void dump() const; 192 symbol_begin()193 SymExpr::symbol_iterator symbol_begin() const { 194 const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true); 195 if (SE) 196 return SE->symbol_begin(); 197 else 198 return SymExpr::symbol_iterator(); 199 } 200 symbol_end()201 SymExpr::symbol_iterator symbol_end() const { 202 return SymExpr::symbol_end(); 203 } 204 205 /// Try to get a reasonable type for the given value. 206 /// 207 /// \returns The best approximation of the value type or Null. 208 /// In theory, all symbolic values should be typed, but this function 209 /// is still a WIP and might have a few blind spots. 210 /// 211 /// \note This function should not be used when the user has access to the 212 /// bound expression AST node as well, since AST always has exact types. 213 /// 214 /// \note Loc values are interpreted as pointer rvalues for the purposes of 215 /// this method. 216 QualType getType(const ASTContext &) const; 217 }; 218 219 inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { 220 V.dumpToStream(os); 221 return os; 222 } 223 224 class UndefinedVal : public SVal { 225 public: UndefinedVal()226 UndefinedVal() : SVal(UndefinedValKind) {} 227 228 private: 229 friend class SVal; 230 isKind(const SVal & V)231 static bool isKind(const SVal& V) { 232 return V.getBaseKind() == UndefinedValKind; 233 } 234 }; 235 236 class DefinedOrUnknownSVal : public SVal { 237 public: 238 // We want calling these methods to be a compiler error since they are 239 // tautologically false. 240 bool isUndef() const = delete; 241 bool isValid() const = delete; 242 243 protected: 244 DefinedOrUnknownSVal() = default; DefinedOrUnknownSVal(const void * d,bool isLoc,unsigned ValKind)245 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind) 246 : SVal(d, isLoc, ValKind) {} SVal(k,D)247 explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr) : SVal(k, D) {} 248 249 private: 250 friend class SVal; 251 isKind(const SVal & V)252 static bool isKind(const SVal& V) { 253 return !V.isUndef(); 254 } 255 }; 256 257 class UnknownVal : public DefinedOrUnknownSVal { 258 public: UnknownVal()259 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {} 260 261 private: 262 friend class SVal; 263 isKind(const SVal & V)264 static bool isKind(const SVal &V) { 265 return V.getBaseKind() == UnknownValKind; 266 } 267 }; 268 269 class DefinedSVal : public DefinedOrUnknownSVal { 270 public: 271 // We want calling these methods to be a compiler error since they are 272 // tautologically true/false. 273 bool isUnknown() const = delete; 274 bool isUnknownOrUndef() const = delete; 275 bool isValid() const = delete; 276 277 protected: 278 DefinedSVal() = default; DefinedSVal(const void * d,bool isLoc,unsigned ValKind)279 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) 280 : DefinedOrUnknownSVal(d, isLoc, ValKind) {} 281 282 private: 283 friend class SVal; 284 isKind(const SVal & V)285 static bool isKind(const SVal& V) { 286 return !V.isUnknownOrUndef(); 287 } 288 }; 289 290 /// Represents an SVal that is guaranteed to not be UnknownVal. 291 class KnownSVal : public SVal { 292 friend class SVal; 293 294 KnownSVal() = default; 295 isKind(const SVal & V)296 static bool isKind(const SVal &V) { 297 return !V.isUnknown(); 298 } 299 300 public: KnownSVal(const DefinedSVal & V)301 KnownSVal(const DefinedSVal &V) : SVal(V) {} KnownSVal(const UndefinedVal & V)302 KnownSVal(const UndefinedVal &V) : SVal(V) {} 303 }; 304 305 class NonLoc : public DefinedSVal { 306 protected: 307 NonLoc() = default; NonLoc(unsigned SubKind,const void * d)308 explicit NonLoc(unsigned SubKind, const void *d) 309 : DefinedSVal(d, false, SubKind) {} 310 311 public: 312 void dumpToStream(raw_ostream &Out) const; 313 isCompoundType(QualType T)314 static bool isCompoundType(QualType T) { 315 return T->isArrayType() || T->isRecordType() || 316 T->isAnyComplexType() || T->isVectorType(); 317 } 318 319 private: 320 friend class SVal; 321 isKind(const SVal & V)322 static bool isKind(const SVal& V) { 323 return V.getBaseKind() == NonLocKind; 324 } 325 }; 326 327 class Loc : public DefinedSVal { 328 protected: 329 Loc() = default; Loc(unsigned SubKind,const void * D)330 explicit Loc(unsigned SubKind, const void *D) 331 : DefinedSVal(const_cast<void *>(D), true, SubKind) {} 332 333 public: 334 void dumpToStream(raw_ostream &Out) const; 335 isLocType(QualType T)336 static bool isLocType(QualType T) { 337 return T->isAnyPointerType() || T->isBlockPointerType() || 338 T->isReferenceType() || T->isNullPtrType(); 339 } 340 341 private: 342 friend class SVal; 343 isKind(const SVal & V)344 static bool isKind(const SVal& V) { 345 return V.getBaseKind() == LocKind; 346 } 347 }; 348 349 //==------------------------------------------------------------------------==// 350 // Subclasses of NonLoc. 351 //==------------------------------------------------------------------------==// 352 353 namespace nonloc { 354 355 /// Represents symbolic expression that isn't a location. 356 class SymbolVal : public NonLoc { 357 public: 358 SymbolVal() = delete; SymbolVal(SymbolRef sym)359 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) { 360 assert(sym); 361 assert(!Loc::isLocType(sym->getType())); 362 } 363 getSymbol()364 SymbolRef getSymbol() const { 365 return (const SymExpr *) Data; 366 } 367 isExpression()368 bool isExpression() const { 369 return !isa<SymbolData>(getSymbol()); 370 } 371 372 private: 373 friend class SVal; 374 isKind(const SVal & V)375 static bool isKind(const SVal& V) { 376 return V.getBaseKind() == NonLocKind && 377 V.getSubKind() == SymbolValKind; 378 } 379 isKind(const NonLoc & V)380 static bool isKind(const NonLoc& V) { 381 return V.getSubKind() == SymbolValKind; 382 } 383 }; 384 385 /// Value representing integer constant. 386 class ConcreteInt : public NonLoc { 387 public: ConcreteInt(const llvm::APSInt & V)388 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} 389 getValue()390 const llvm::APSInt& getValue() const { 391 return *static_cast<const llvm::APSInt *>(Data); 392 } 393 394 // Transfer functions for binary/unary operations on ConcreteInts. 395 SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op, 396 const ConcreteInt& R) const; 397 398 ConcreteInt evalComplement(SValBuilder &svalBuilder) const; 399 400 ConcreteInt evalMinus(SValBuilder &svalBuilder) const; 401 402 private: 403 friend class SVal; 404 405 ConcreteInt() = default; 406 isKind(const SVal & V)407 static bool isKind(const SVal& V) { 408 return V.getBaseKind() == NonLocKind && 409 V.getSubKind() == ConcreteIntKind; 410 } 411 isKind(const NonLoc & V)412 static bool isKind(const NonLoc& V) { 413 return V.getSubKind() == ConcreteIntKind; 414 } 415 }; 416 417 class LocAsInteger : public NonLoc { 418 friend class ento::SValBuilder; 419 LocAsInteger(const std::pair<SVal,uintptr_t> & data)420 explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data) 421 : NonLoc(LocAsIntegerKind, &data) { 422 // We do not need to represent loc::ConcreteInt as LocAsInteger, 423 // as it'd collapse into a nonloc::ConcreteInt instead. 424 assert(data.first.getBaseKind() == LocKind && 425 (data.first.getSubKind() == loc::MemRegionValKind || 426 data.first.getSubKind() == loc::GotoLabelKind)); 427 } 428 429 public: getLoc()430 Loc getLoc() const { 431 const std::pair<SVal, uintptr_t> *D = 432 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 433 return D->first.castAs<Loc>(); 434 } 435 getPersistentLoc()436 Loc getPersistentLoc() const { 437 const std::pair<SVal, uintptr_t> *D = 438 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 439 const SVal& V = D->first; 440 return V.castAs<Loc>(); 441 } 442 getNumBits()443 unsigned getNumBits() const { 444 const std::pair<SVal, uintptr_t> *D = 445 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 446 return D->second; 447 } 448 449 private: 450 friend class SVal; 451 452 LocAsInteger() = default; 453 isKind(const SVal & V)454 static bool isKind(const SVal& V) { 455 return V.getBaseKind() == NonLocKind && 456 V.getSubKind() == LocAsIntegerKind; 457 } 458 isKind(const NonLoc & V)459 static bool isKind(const NonLoc& V) { 460 return V.getSubKind() == LocAsIntegerKind; 461 } 462 }; 463 464 class CompoundVal : public NonLoc { 465 friend class ento::SValBuilder; 466 CompoundVal(const CompoundValData * D)467 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 468 469 public: getValue()470 const CompoundValData* getValue() const { 471 return static_cast<const CompoundValData *>(Data); 472 } 473 474 using iterator = llvm::ImmutableList<SVal>::iterator; 475 476 iterator begin() const; 477 iterator end() const; 478 479 private: 480 friend class SVal; 481 482 CompoundVal() = default; 483 isKind(const SVal & V)484 static bool isKind(const SVal& V) { 485 return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind; 486 } 487 isKind(const NonLoc & V)488 static bool isKind(const NonLoc& V) { 489 return V.getSubKind() == CompoundValKind; 490 } 491 }; 492 493 class LazyCompoundVal : public NonLoc { 494 friend class ento::SValBuilder; 495 LazyCompoundVal(const LazyCompoundValData * D)496 explicit LazyCompoundVal(const LazyCompoundValData *D) 497 : NonLoc(LazyCompoundValKind, D) {} 498 499 public: getCVData()500 const LazyCompoundValData *getCVData() const { 501 return static_cast<const LazyCompoundValData *>(Data); 502 } 503 504 const void *getStore() const; 505 const TypedValueRegion *getRegion() const; 506 507 private: 508 friend class SVal; 509 510 LazyCompoundVal() = default; 511 isKind(const SVal & V)512 static bool isKind(const SVal& V) { 513 return V.getBaseKind() == NonLocKind && 514 V.getSubKind() == LazyCompoundValKind; 515 } 516 isKind(const NonLoc & V)517 static bool isKind(const NonLoc& V) { 518 return V.getSubKind() == LazyCompoundValKind; 519 } 520 }; 521 522 /// Value representing pointer-to-member. 523 /// 524 /// This value is qualified as NonLoc because neither loading nor storing 525 /// operations are applied to it. Instead, the analyzer uses the L-value coming 526 /// from pointer-to-member applied to an object. 527 /// This SVal is represented by a NamedDecl which can be a member function 528 /// pointer or a member data pointer and an optional list of CXXBaseSpecifiers. 529 /// This list is required to accumulate the pointer-to-member cast history to 530 /// figure out the correct subobject field. In particular, implicit casts grow 531 /// this list and explicit casts like static_cast shrink this list. 532 class PointerToMember : public NonLoc { 533 friend class ento::SValBuilder; 534 535 public: 536 using PTMDataType = 537 llvm::PointerUnion<const NamedDecl *, const PointerToMemberData *>; 538 getPTMData()539 const PTMDataType getPTMData() const { 540 return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data)); 541 } 542 543 bool isNullMemberPointer() const; 544 545 const NamedDecl *getDecl() const; 546 547 template<typename AdjustedDecl> getDeclAs()548 const AdjustedDecl *getDeclAs() const { 549 return dyn_cast_or_null<AdjustedDecl>(getDecl()); 550 } 551 552 using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator; 553 554 iterator begin() const; 555 iterator end() const; 556 557 private: 558 friend class SVal; 559 560 PointerToMember() = default; PointerToMember(const PTMDataType D)561 explicit PointerToMember(const PTMDataType D) 562 : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {} 563 isKind(const SVal & V)564 static bool isKind(const SVal& V) { 565 return V.getBaseKind() == NonLocKind && 566 V.getSubKind() == PointerToMemberKind; 567 } 568 isKind(const NonLoc & V)569 static bool isKind(const NonLoc& V) { 570 return V.getSubKind() == PointerToMemberKind; 571 } 572 }; 573 574 } // namespace nonloc 575 576 //==------------------------------------------------------------------------==// 577 // Subclasses of Loc. 578 //==------------------------------------------------------------------------==// 579 580 namespace loc { 581 582 class GotoLabel : public Loc { 583 public: GotoLabel(const LabelDecl * Label)584 explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) { 585 assert(Label); 586 } 587 getLabel()588 const LabelDecl *getLabel() const { 589 return static_cast<const LabelDecl *>(Data); 590 } 591 592 private: 593 friend class SVal; 594 595 GotoLabel() = default; 596 isKind(const SVal & V)597 static bool isKind(const SVal& V) { 598 return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind; 599 } 600 isKind(const Loc & V)601 static bool isKind(const Loc& V) { 602 return V.getSubKind() == GotoLabelKind; 603 } 604 }; 605 606 class MemRegionVal : public Loc { 607 public: MemRegionVal(const MemRegion * r)608 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) { 609 assert(r); 610 } 611 612 /// Get the underlining region. getRegion()613 const MemRegion *getRegion() const { 614 return static_cast<const MemRegion *>(Data); 615 } 616 617 /// Get the underlining region and strip casts. 618 const MemRegion* stripCasts(bool StripBaseCasts = true) const; 619 620 template <typename REGION> getRegionAs()621 const REGION* getRegionAs() const { 622 return dyn_cast<REGION>(getRegion()); 623 } 624 625 bool operator==(const MemRegionVal &R) const { 626 return getRegion() == R.getRegion(); 627 } 628 629 bool operator!=(const MemRegionVal &R) const { 630 return getRegion() != R.getRegion(); 631 } 632 633 private: 634 friend class SVal; 635 636 MemRegionVal() = default; 637 isKind(const SVal & V)638 static bool isKind(const SVal& V) { 639 return V.getBaseKind() == LocKind && 640 V.getSubKind() == MemRegionValKind; 641 } 642 isKind(const Loc & V)643 static bool isKind(const Loc& V) { 644 return V.getSubKind() == MemRegionValKind; 645 } 646 }; 647 648 class ConcreteInt : public Loc { 649 public: ConcreteInt(const llvm::APSInt & V)650 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} 651 getValue()652 const llvm::APSInt &getValue() const { 653 return *static_cast<const llvm::APSInt *>(Data); 654 } 655 656 // Transfer functions for binary/unary operations on ConcreteInts. 657 SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, 658 const ConcreteInt& R) const; 659 660 private: 661 friend class SVal; 662 663 ConcreteInt() = default; 664 isKind(const SVal & V)665 static bool isKind(const SVal& V) { 666 return V.getBaseKind() == LocKind && 667 V.getSubKind() == ConcreteIntKind; 668 } 669 isKind(const Loc & V)670 static bool isKind(const Loc& V) { 671 return V.getSubKind() == ConcreteIntKind; 672 } 673 }; 674 675 } // namespace loc 676 677 } // namespace ento 678 679 } // namespace clang 680 681 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H 682