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 674