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