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