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