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