1 //===- SVals.h - Abstract Values for Static Analysis ------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines SVal, Loc, and NonLoc, classes that represent 11 // abstract r-values for use with path-sensitive value tracking. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H 16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H 17 18 #include "clang/AST/Expr.h" 19 #include "clang/AST/Type.h" 20 #include "clang/Basic/LLVM.h" 21 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 22 #include "llvm/ADT/FoldingSet.h" 23 #include "llvm/ADT/ImmutableList.h" 24 #include "llvm/ADT/None.h" 25 #include "llvm/ADT/Optional.h" 26 #include "llvm/ADT/PointerUnion.h" 27 #include "llvm/Support/Casting.h" 28 #include <cassert> 29 #include <cstdint> 30 #include <utility> 31 32 //==------------------------------------------------------------------------==// 33 // Base SVal types. 34 //==------------------------------------------------------------------------==// 35 36 namespace clang { 37 38 class CXXBaseSpecifier; 39 class DeclaratorDecl; 40 class FunctionDecl; 41 class LabelDecl; 42 43 namespace ento { 44 45 class BasicValueFactory; 46 class CompoundValData; 47 class LazyCompoundValData; 48 class MemRegion; 49 class PointerToMemberData; 50 class SValBuilder; 51 class TypedValueRegion; 52 53 namespace nonloc { 54 55 /// Sub-kinds for NonLoc values. 56 enum Kind { 57 #define NONLOC_SVAL(Id, Parent) Id ## Kind, 58 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" 59 }; 60 61 } // namespace nonloc 62 63 namespace loc { 64 65 /// Sub-kinds for Loc values. 66 enum Kind { 67 #define LOC_SVAL(Id, Parent) Id ## Kind, 68 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" 69 }; 70 71 } // namespace loc 72 73 /// SVal - This represents a symbolic expression, which can be either 74 /// an L-value or an R-value. 75 /// 76 class SVal { 77 public: 78 enum BaseKind { 79 // The enumerators must be representable using 2 bits. 80 #define BASIC_SVAL(Id, Parent) Id ## Kind, 81 #define ABSTRACT_SVAL_WITH_KIND(Id, Parent) Id ## Kind, 82 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" 83 }; 84 enum { BaseBits = 2, BaseMask = 0x3 }; 85 86 protected: 87 const void *Data = nullptr; 88 89 /// The lowest 2 bits are a BaseKind (0 -- 3). 90 /// The higher bits are an unsigned "kind" value. 91 unsigned Kind = 0; 92 SVal(const void * d,bool isLoc,unsigned ValKind)93 explicit SVal(const void *d, bool isLoc, unsigned ValKind) 94 : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} 95 Data(D)96 explicit SVal(BaseKind k, const void *D = nullptr) : Data(D), Kind(k) {} 97 98 public: 99 explicit SVal() = default; 100 101 /// Convert to the specified SVal type, asserting that this SVal is of 102 /// the desired type. 103 template<typename T> castAs()104 T castAs() const { 105 assert(T::isKind(*this)); 106 return *static_cast<const T *>(this); 107 } 108 109 /// Convert to the specified SVal type, returning None if this SVal is 110 /// not of the desired type. 111 template<typename T> getAs()112 Optional<T> getAs() const { 113 if (!T::isKind(*this)) 114 return None; 115 return *static_cast<const T *>(this); 116 } 117 getRawKind()118 unsigned getRawKind() const { return Kind; } getBaseKind()119 BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); } getSubKind()120 unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; } 121 122 // This method is required for using SVal in a FoldingSetNode. It 123 // extracts a unique signature for this SVal object. Profile(llvm::FoldingSetNodeID & ID)124 void Profile(llvm::FoldingSetNodeID &ID) const { 125 ID.AddInteger((unsigned) getRawKind()); 126 ID.AddPointer(Data); 127 } 128 129 bool operator==(const SVal &R) const { 130 return getRawKind() == R.getRawKind() && Data == R.Data; 131 } 132 133 bool operator!=(const SVal &R) const { 134 return !(*this == R); 135 } 136 isUnknown()137 bool isUnknown() const { 138 return getRawKind() == UnknownValKind; 139 } 140 isUndef()141 bool isUndef() const { 142 return getRawKind() == UndefinedValKind; 143 } 144 isUnknownOrUndef()145 bool isUnknownOrUndef() const { 146 return getRawKind() <= UnknownValKind; 147 } 148 isValid()149 bool isValid() const { 150 return getRawKind() > UnknownValKind; 151 } 152 153 bool isConstant() const; 154 155 bool isConstant(int I) const; 156 157 bool isZeroConstant() const; 158 159 /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true; 160 bool hasConjuredSymbol() const; 161 162 /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a 163 /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. 164 /// Otherwise return 0. 165 const FunctionDecl *getAsFunctionDecl() const; 166 167 /// If this SVal is a location and wraps a symbol, return that 168 /// SymbolRef. Otherwise return 0. 169 /// 170 /// Casts are ignored during lookup. 171 /// \param IncludeBaseRegions The boolean that controls whether the search 172 /// should continue to the base regions if the region is not symbolic. 173 SymbolRef getAsLocSymbol(bool IncludeBaseRegions = false) const; 174 175 /// Get the symbol in the SVal or its base region. 176 SymbolRef getLocSymbolInBase() const; 177 178 /// If this SVal wraps a symbol return that SymbolRef. 179 /// Otherwise, return 0. 180 /// 181 /// Casts are ignored during lookup. 182 /// \param IncludeBaseRegions The boolean that controls whether the search 183 /// should continue to the base regions if the region is not symbolic. 184 SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const; 185 186 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then 187 /// return that expression. Otherwise return NULL. 188 const SymExpr *getAsSymbolicExpression() const; 189 190 const SymExpr *getAsSymExpr() const; 191 192 const MemRegion *getAsRegion() const; 193 194 void dumpToStream(raw_ostream &OS) const; 195 void dump() const; 196 symbol_begin()197 SymExpr::symbol_iterator symbol_begin() const { 198 const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true); 199 if (SE) 200 return SE->symbol_begin(); 201 else 202 return SymExpr::symbol_iterator(); 203 } 204 symbol_end()205 SymExpr::symbol_iterator symbol_end() const { 206 return SymExpr::symbol_end(); 207 } 208 }; 209 210 inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { 211 V.dumpToStream(os); 212 return os; 213 } 214 215 class UndefinedVal : public SVal { 216 public: UndefinedVal()217 UndefinedVal() : SVal(UndefinedValKind) {} 218 219 private: 220 friend class SVal; 221 isKind(const SVal & V)222 static bool isKind(const SVal& V) { 223 return V.getBaseKind() == UndefinedValKind; 224 } 225 }; 226 227 class DefinedOrUnknownSVal : public SVal { 228 public: 229 // We want calling these methods to be a compiler error since they are 230 // tautologically false. 231 bool isUndef() const = delete; 232 bool isValid() const = delete; 233 234 protected: 235 DefinedOrUnknownSVal() = default; DefinedOrUnknownSVal(const void * d,bool isLoc,unsigned ValKind)236 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind) 237 : SVal(d, isLoc, ValKind) {} SVal(k,D)238 explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr) : SVal(k, D) {} 239 240 private: 241 friend class SVal; 242 isKind(const SVal & V)243 static bool isKind(const SVal& V) { 244 return !V.isUndef(); 245 } 246 }; 247 248 class UnknownVal : public DefinedOrUnknownSVal { 249 public: UnknownVal()250 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {} 251 252 private: 253 friend class SVal; 254 isKind(const SVal & V)255 static bool isKind(const SVal &V) { 256 return V.getBaseKind() == UnknownValKind; 257 } 258 }; 259 260 class DefinedSVal : public DefinedOrUnknownSVal { 261 public: 262 // We want calling these methods to be a compiler error since they are 263 // tautologically true/false. 264 bool isUnknown() const = delete; 265 bool isUnknownOrUndef() const = delete; 266 bool isValid() const = delete; 267 268 protected: 269 DefinedSVal() = default; DefinedSVal(const void * d,bool isLoc,unsigned ValKind)270 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) 271 : DefinedOrUnknownSVal(d, isLoc, ValKind) {} 272 273 private: 274 friend class SVal; 275 isKind(const SVal & V)276 static bool isKind(const SVal& V) { 277 return !V.isUnknownOrUndef(); 278 } 279 }; 280 281 /// Represents an SVal that is guaranteed to not be UnknownVal. 282 class KnownSVal : public SVal { 283 friend class SVal; 284 285 KnownSVal() = default; 286 isKind(const SVal & V)287 static bool isKind(const SVal &V) { 288 return !V.isUnknown(); 289 } 290 291 public: KnownSVal(const DefinedSVal & V)292 KnownSVal(const DefinedSVal &V) : SVal(V) {} KnownSVal(const UndefinedVal & V)293 KnownSVal(const UndefinedVal &V) : SVal(V) {} 294 }; 295 296 class NonLoc : public DefinedSVal { 297 protected: 298 NonLoc() = default; NonLoc(unsigned SubKind,const void * d)299 explicit NonLoc(unsigned SubKind, const void *d) 300 : DefinedSVal(d, false, SubKind) {} 301 302 public: 303 void dumpToStream(raw_ostream &Out) const; 304 isCompoundType(QualType T)305 static bool isCompoundType(QualType T) { 306 return T->isArrayType() || T->isRecordType() || 307 T->isComplexType() || T->isVectorType(); 308 } 309 310 private: 311 friend class SVal; 312 isKind(const SVal & V)313 static bool isKind(const SVal& V) { 314 return V.getBaseKind() == NonLocKind; 315 } 316 }; 317 318 class Loc : public DefinedSVal { 319 protected: 320 Loc() = default; Loc(unsigned SubKind,const void * D)321 explicit Loc(unsigned SubKind, const void *D) 322 : DefinedSVal(const_cast<void *>(D), true, SubKind) {} 323 324 public: 325 void dumpToStream(raw_ostream &Out) const; 326 isLocType(QualType T)327 static bool isLocType(QualType T) { 328 return T->isAnyPointerType() || T->isBlockPointerType() || 329 T->isReferenceType() || T->isNullPtrType(); 330 } 331 332 private: 333 friend class SVal; 334 isKind(const SVal & V)335 static bool isKind(const SVal& V) { 336 return V.getBaseKind() == LocKind; 337 } 338 }; 339 340 //==------------------------------------------------------------------------==// 341 // Subclasses of NonLoc. 342 //==------------------------------------------------------------------------==// 343 344 namespace nonloc { 345 346 /// Represents symbolic expression that isn't a location. 347 class SymbolVal : public NonLoc { 348 public: 349 SymbolVal() = delete; SymbolVal(SymbolRef sym)350 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) { 351 assert(sym); 352 assert(!Loc::isLocType(sym->getType())); 353 } 354 getSymbol()355 SymbolRef getSymbol() const { 356 return (const SymExpr *) Data; 357 } 358 isExpression()359 bool isExpression() const { 360 return !isa<SymbolData>(getSymbol()); 361 } 362 363 private: 364 friend class SVal; 365 isKind(const SVal & V)366 static bool isKind(const SVal& V) { 367 return V.getBaseKind() == NonLocKind && 368 V.getSubKind() == SymbolValKind; 369 } 370 isKind(const NonLoc & V)371 static bool isKind(const NonLoc& V) { 372 return V.getSubKind() == SymbolValKind; 373 } 374 }; 375 376 /// Value representing integer constant. 377 class ConcreteInt : public NonLoc { 378 public: ConcreteInt(const llvm::APSInt & V)379 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} 380 getValue()381 const llvm::APSInt& getValue() const { 382 return *static_cast<const llvm::APSInt *>(Data); 383 } 384 385 // Transfer functions for binary/unary operations on ConcreteInts. 386 SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op, 387 const ConcreteInt& R) const; 388 389 ConcreteInt evalComplement(SValBuilder &svalBuilder) const; 390 391 ConcreteInt evalMinus(SValBuilder &svalBuilder) const; 392 393 private: 394 friend class SVal; 395 396 ConcreteInt() = default; 397 isKind(const SVal & V)398 static bool isKind(const SVal& V) { 399 return V.getBaseKind() == NonLocKind && 400 V.getSubKind() == ConcreteIntKind; 401 } 402 isKind(const NonLoc & V)403 static bool isKind(const NonLoc& V) { 404 return V.getSubKind() == ConcreteIntKind; 405 } 406 }; 407 408 class LocAsInteger : public NonLoc { 409 friend class ento::SValBuilder; 410 LocAsInteger(const std::pair<SVal,uintptr_t> & data)411 explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data) 412 : NonLoc(LocAsIntegerKind, &data) { 413 // We do not need to represent loc::ConcreteInt as LocAsInteger, 414 // as it'd collapse into a nonloc::ConcreteInt instead. 415 assert(data.first.getBaseKind() == LocKind && 416 (data.first.getSubKind() == loc::MemRegionValKind || 417 data.first.getSubKind() == loc::GotoLabelKind)); 418 } 419 420 public: getLoc()421 Loc getLoc() const { 422 const std::pair<SVal, uintptr_t> *D = 423 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 424 return D->first.castAs<Loc>(); 425 } 426 getPersistentLoc()427 Loc getPersistentLoc() const { 428 const std::pair<SVal, uintptr_t> *D = 429 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 430 const SVal& V = D->first; 431 return V.castAs<Loc>(); 432 } 433 getNumBits()434 unsigned getNumBits() const { 435 const std::pair<SVal, uintptr_t> *D = 436 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 437 return D->second; 438 } 439 440 private: 441 friend class SVal; 442 443 LocAsInteger() = default; 444 isKind(const SVal & V)445 static bool isKind(const SVal& V) { 446 return V.getBaseKind() == NonLocKind && 447 V.getSubKind() == LocAsIntegerKind; 448 } 449 isKind(const NonLoc & V)450 static bool isKind(const NonLoc& V) { 451 return V.getSubKind() == LocAsIntegerKind; 452 } 453 }; 454 455 class CompoundVal : public NonLoc { 456 friend class ento::SValBuilder; 457 CompoundVal(const CompoundValData * D)458 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 459 460 public: getValue()461 const CompoundValData* getValue() const { 462 return static_cast<const CompoundValData *>(Data); 463 } 464 465 using iterator = llvm::ImmutableList<SVal>::iterator; 466 467 iterator begin() const; 468 iterator end() const; 469 470 private: 471 friend class SVal; 472 473 CompoundVal() = default; 474 isKind(const SVal & V)475 static bool isKind(const SVal& V) { 476 return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind; 477 } 478 isKind(const NonLoc & V)479 static bool isKind(const NonLoc& V) { 480 return V.getSubKind() == CompoundValKind; 481 } 482 }; 483 484 class LazyCompoundVal : public NonLoc { 485 friend class ento::SValBuilder; 486 LazyCompoundVal(const LazyCompoundValData * D)487 explicit LazyCompoundVal(const LazyCompoundValData *D) 488 : NonLoc(LazyCompoundValKind, D) {} 489 490 public: getCVData()491 const LazyCompoundValData *getCVData() const { 492 return static_cast<const LazyCompoundValData *>(Data); 493 } 494 495 const void *getStore() const; 496 const TypedValueRegion *getRegion() const; 497 498 private: 499 friend class SVal; 500 501 LazyCompoundVal() = default; 502 isKind(const SVal & V)503 static bool isKind(const SVal& V) { 504 return V.getBaseKind() == NonLocKind && 505 V.getSubKind() == LazyCompoundValKind; 506 } 507 isKind(const NonLoc & V)508 static bool isKind(const NonLoc& V) { 509 return V.getSubKind() == LazyCompoundValKind; 510 } 511 }; 512 513 /// Value representing pointer-to-member. 514 /// 515 /// This value is qualified as NonLoc because neither loading nor storing 516 /// operations are applied to it. Instead, the analyzer uses the L-value coming 517 /// from pointer-to-member applied to an object. 518 /// This SVal is represented by a DeclaratorDecl which can be a member function 519 /// pointer or a member data pointer and a list of CXXBaseSpecifiers. This list 520 /// is required to accumulate the pointer-to-member cast history to figure out 521 /// the correct subobject field. 522 class PointerToMember : public NonLoc { 523 friend class ento::SValBuilder; 524 525 public: 526 using PTMDataType = 527 llvm::PointerUnion<const DeclaratorDecl *, const PointerToMemberData *>; 528 getPTMData()529 const PTMDataType getPTMData() const { 530 return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data)); 531 } 532 isNullMemberPointer()533 bool isNullMemberPointer() const { 534 return getPTMData().isNull(); 535 } 536 537 const DeclaratorDecl *getDecl() const; 538 539 template<typename AdjustedDecl> getDeclAs()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; PointerToMember(const PTMDataType D)553 explicit PointerToMember(const PTMDataType D) 554 : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {} 555 isKind(const SVal & V)556 static bool isKind(const SVal& V) { 557 return V.getBaseKind() == NonLocKind && 558 V.getSubKind() == PointerToMemberKind; 559 } 560 isKind(const NonLoc & V)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: GotoLabel(const LabelDecl * Label)576 explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) { 577 assert(Label); 578 } 579 getLabel()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 isKind(const SVal & V)589 static bool isKind(const SVal& V) { 590 return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind; 591 } 592 isKind(const Loc & V)593 static bool isKind(const Loc& V) { 594 return V.getSubKind() == GotoLabelKind; 595 } 596 }; 597 598 class MemRegionVal : public Loc { 599 public: MemRegionVal(const MemRegion * r)600 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) { 601 assert(r); 602 } 603 604 /// Get the underlining region. getRegion()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> getRegionAs()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 isKind(const SVal & V)630 static bool isKind(const SVal& V) { 631 return V.getBaseKind() == LocKind && 632 V.getSubKind() == MemRegionValKind; 633 } 634 isKind(const Loc & V)635 static bool isKind(const Loc& V) { 636 return V.getSubKind() == MemRegionValKind; 637 } 638 }; 639 640 class ConcreteInt : public Loc { 641 public: ConcreteInt(const llvm::APSInt & V)642 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} 643 getValue()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 isKind(const SVal & V)657 static bool isKind(const SVal& V) { 658 return V.getBaseKind() == LocKind && 659 V.getSubKind() == ConcreteIntKind; 660 } 661 isKind(const Loc & V)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 namespace llvm { 674 675 template <typename T> struct isPodLike; 676 template <> struct isPodLike<clang::ento::SVal> { 677 static const bool value = true; 678 }; 679 680 } // namespace llvm 681 682 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H 683