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