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