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