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