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 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: UndefinedVal()213 UndefinedVal() : SVal(UndefinedValKind) {} 214 215 private: 216 friend class SVal; 217 isKind(const SVal & V)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; DefinedOrUnknownSVal(const void * d,bool isLoc,unsigned ValKind)232 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind) 233 : SVal(d, isLoc, ValKind) {} SVal(k,D)234 explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr) : SVal(k, D) {} 235 236 private: 237 friend class SVal; 238 isKind(const SVal & V)239 static bool isKind(const SVal& V) { 240 return !V.isUndef(); 241 } 242 }; 243 244 class UnknownVal : public DefinedOrUnknownSVal { 245 public: UnknownVal()246 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {} 247 248 private: 249 friend class SVal; 250 isKind(const SVal & V)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; DefinedSVal(const void * d,bool isLoc,unsigned ValKind)266 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) 267 : DefinedOrUnknownSVal(d, isLoc, ValKind) {} 268 269 private: 270 friend class SVal; 271 isKind(const SVal & V)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 isKind(const SVal & V)283 static bool isKind(const SVal &V) { 284 return !V.isUnknown(); 285 } 286 287 public: KnownSVal(const DefinedSVal & V)288 KnownSVal(const DefinedSVal &V) : SVal(V) {} KnownSVal(const UndefinedVal & V)289 KnownSVal(const UndefinedVal &V) : SVal(V) {} 290 }; 291 292 class NonLoc : public DefinedSVal { 293 protected: 294 NonLoc() = default; NonLoc(unsigned SubKind,const void * d)295 explicit NonLoc(unsigned SubKind, const void *d) 296 : DefinedSVal(d, false, SubKind) {} 297 298 public: 299 void dumpToStream(raw_ostream &Out) const; 300 isCompoundType(QualType T)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 isKind(const SVal & V)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; Loc(unsigned SubKind,const void * D)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 isLocType(QualType T)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 isKind(const SVal & V)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; SymbolVal(SymbolRef sym)346 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) { 347 assert(sym); 348 assert(!Loc::isLocType(sym->getType())); 349 } 350 getSymbol()351 SymbolRef getSymbol() const { 352 return (const SymExpr *) Data; 353 } 354 isExpression()355 bool isExpression() const { 356 return !isa<SymbolData>(getSymbol()); 357 } 358 359 private: 360 friend class SVal; 361 isKind(const SVal & V)362 static bool isKind(const SVal& V) { 363 return V.getBaseKind() == NonLocKind && 364 V.getSubKind() == SymbolValKind; 365 } 366 isKind(const NonLoc & V)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: ConcreteInt(const llvm::APSInt & V)375 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} 376 getValue()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 isKind(const SVal & V)394 static bool isKind(const SVal& V) { 395 return V.getBaseKind() == NonLocKind && 396 V.getSubKind() == ConcreteIntKind; 397 } 398 isKind(const NonLoc & V)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 LocAsInteger(const std::pair<SVal,uintptr_t> & data)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: getLoc()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 getPersistentLoc()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 getNumBits()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 isKind(const SVal & V)441 static bool isKind(const SVal& V) { 442 return V.getBaseKind() == NonLocKind && 443 V.getSubKind() == LocAsIntegerKind; 444 } 445 isKind(const NonLoc & V)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 CompoundVal(const CompoundValData * D)454 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 455 456 public: getValue()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 isKind(const SVal & V)471 static bool isKind(const SVal& V) { 472 return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind; 473 } 474 isKind(const NonLoc & V)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 LazyCompoundVal(const LazyCompoundValData * D)483 explicit LazyCompoundVal(const LazyCompoundValData *D) 484 : NonLoc(LazyCompoundValKind, D) {} 485 486 public: getCVData()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 isKind(const SVal & V)499 static bool isKind(const SVal& V) { 500 return V.getBaseKind() == NonLocKind && 501 V.getSubKind() == LazyCompoundValKind; 502 } 503 isKind(const NonLoc & V)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 NamedDecl which can be a member function 515 /// pointer or a member data pointer and an optional list of CXXBaseSpecifiers. 516 /// This list is required to accumulate the pointer-to-member cast history to 517 /// figure out the correct subobject field. In particular, implicit casts grow 518 /// this list and explicit casts like static_cast shrink this list. 519 class PointerToMember : public NonLoc { 520 friend class ento::SValBuilder; 521 522 public: 523 using PTMDataType = 524 llvm::PointerUnion<const NamedDecl *, const PointerToMemberData *>; 525 getPTMData()526 const PTMDataType getPTMData() const { 527 return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data)); 528 } 529 530 bool isNullMemberPointer() const; 531 532 const NamedDecl *getDecl() const; 533 534 template<typename AdjustedDecl> getDeclAs()535 const AdjustedDecl *getDeclAs() const { 536 return dyn_cast_or_null<AdjustedDecl>(getDecl()); 537 } 538 539 using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator; 540 541 iterator begin() const; 542 iterator end() const; 543 544 private: 545 friend class SVal; 546 547 PointerToMember() = default; PointerToMember(const PTMDataType D)548 explicit PointerToMember(const PTMDataType D) 549 : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {} 550 isKind(const SVal & V)551 static bool isKind(const SVal& V) { 552 return V.getBaseKind() == NonLocKind && 553 V.getSubKind() == PointerToMemberKind; 554 } 555 isKind(const NonLoc & V)556 static bool isKind(const NonLoc& V) { 557 return V.getSubKind() == PointerToMemberKind; 558 } 559 }; 560 561 } // namespace nonloc 562 563 //==------------------------------------------------------------------------==// 564 // Subclasses of Loc. 565 //==------------------------------------------------------------------------==// 566 567 namespace loc { 568 569 class GotoLabel : public Loc { 570 public: GotoLabel(const LabelDecl * Label)571 explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) { 572 assert(Label); 573 } 574 getLabel()575 const LabelDecl *getLabel() const { 576 return static_cast<const LabelDecl *>(Data); 577 } 578 579 private: 580 friend class SVal; 581 582 GotoLabel() = default; 583 isKind(const SVal & V)584 static bool isKind(const SVal& V) { 585 return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind; 586 } 587 isKind(const Loc & V)588 static bool isKind(const Loc& V) { 589 return V.getSubKind() == GotoLabelKind; 590 } 591 }; 592 593 class MemRegionVal : public Loc { 594 public: MemRegionVal(const MemRegion * r)595 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) { 596 assert(r); 597 } 598 599 /// Get the underlining region. getRegion()600 const MemRegion *getRegion() const { 601 return static_cast<const MemRegion *>(Data); 602 } 603 604 /// Get the underlining region and strip casts. 605 const MemRegion* stripCasts(bool StripBaseCasts = true) const; 606 607 template <typename REGION> getRegionAs()608 const REGION* getRegionAs() const { 609 return dyn_cast<REGION>(getRegion()); 610 } 611 612 bool operator==(const MemRegionVal &R) const { 613 return getRegion() == R.getRegion(); 614 } 615 616 bool operator!=(const MemRegionVal &R) const { 617 return getRegion() != R.getRegion(); 618 } 619 620 private: 621 friend class SVal; 622 623 MemRegionVal() = default; 624 isKind(const SVal & V)625 static bool isKind(const SVal& V) { 626 return V.getBaseKind() == LocKind && 627 V.getSubKind() == MemRegionValKind; 628 } 629 isKind(const Loc & V)630 static bool isKind(const Loc& V) { 631 return V.getSubKind() == MemRegionValKind; 632 } 633 }; 634 635 class ConcreteInt : public Loc { 636 public: ConcreteInt(const llvm::APSInt & V)637 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} 638 getValue()639 const llvm::APSInt &getValue() const { 640 return *static_cast<const llvm::APSInt *>(Data); 641 } 642 643 // Transfer functions for binary/unary operations on ConcreteInts. 644 SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, 645 const ConcreteInt& R) const; 646 647 private: 648 friend class SVal; 649 650 ConcreteInt() = default; 651 isKind(const SVal & V)652 static bool isKind(const SVal& V) { 653 return V.getBaseKind() == LocKind && 654 V.getSubKind() == ConcreteIntKind; 655 } 656 isKind(const Loc & V)657 static bool isKind(const Loc& V) { 658 return V.getSubKind() == ConcreteIntKind; 659 } 660 }; 661 662 } // namespace loc 663 664 } // namespace ento 665 666 } // namespace clang 667 668 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H 669