SVals.h revision 1d1d515b2bafb59d624883d8fdda97d4b7dba0cb
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 ProgramState; 33class BasicValueFactory; 34class MemRegion; 35class TypedRegion; 36class MemRegionManager; 37class ProgramStateManager; 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 /// If this SVal is a location (subclasses Loc) and 125 /// wraps a symbol, return that SymbolRef. Otherwise return 0. 126 SymbolRef getAsLocSymbol() const; 127 128 /// Get the symbol in the SVal or its base region. 129 SymbolRef getLocSymbolInBase() const; 130 131 /// If this SVal wraps a symbol return that SymbolRef. 132 /// Otherwise, return 0. 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 SymExpr* getAsSymExpr() const; 140 141 const MemRegion *getAsRegion() const; 142 143 void dumpToStream(raw_ostream &OS) const; 144 void dump() const; 145 146 SymExpr::symbol_iterator symbol_begin() const { 147 const SymExpr *SE = getAsSymbolicExpression(); 148 if (SE) 149 return SE->symbol_begin(); 150 else 151 return SymExpr::symbol_iterator(); 152 } 153 154 SymExpr::symbol_iterator symbol_end() const { 155 return SymExpr::symbol_end(); 156 } 157 158 // Implement isa<T> support. 159 static inline bool classof(const SVal*) { return true; } 160}; 161 162 163class UndefinedVal : public SVal { 164public: 165 UndefinedVal() : SVal(UndefinedKind) {} 166 UndefinedVal(const void *D) : SVal(UndefinedKind, D) {} 167 168 static inline bool classof(const SVal* V) { 169 return V->getBaseKind() == UndefinedKind; 170 } 171 172 const void *getData() const { return Data; } 173}; 174 175class DefinedOrUnknownSVal : public SVal { 176private: 177 // Do not implement. We want calling these methods to be a compiler 178 // error since they are tautologically false. 179 bool isUndef() const; 180 bool isValid() const; 181 182protected: 183 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind) 184 : SVal(d, isLoc, ValKind) {} 185 186 explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL) 187 : SVal(k, D) {} 188 189public: 190 // Implement isa<T> support. 191 static inline bool classof(const SVal *V) { 192 return !V->isUndef(); 193 } 194}; 195 196class UnknownVal : public DefinedOrUnknownSVal { 197public: 198 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {} 199 200 static inline bool classof(const SVal *V) { 201 return V->getBaseKind() == UnknownKind; 202 } 203}; 204 205class DefinedSVal : public DefinedOrUnknownSVal { 206private: 207 // Do not implement. We want calling these methods to be a compiler 208 // error since they are tautologically true/false. 209 bool isUnknown() const; 210 bool isUnknownOrUndef() const; 211 bool isValid() const; 212protected: 213 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) 214 : DefinedOrUnknownSVal(d, isLoc, ValKind) {} 215public: 216 // Implement isa<T> support. 217 static inline bool classof(const SVal *V) { 218 return !V->isUnknownOrUndef(); 219 } 220}; 221 222class NonLoc : public DefinedSVal { 223protected: 224 explicit NonLoc(unsigned SubKind, const void *d) 225 : DefinedSVal(d, false, SubKind) {} 226 227public: 228 void dumpToStream(raw_ostream &Out) const; 229 230 // Implement isa<T> support. 231 static inline bool classof(const SVal* V) { 232 return V->getBaseKind() == NonLocKind; 233 } 234}; 235 236class Loc : public DefinedSVal { 237protected: 238 explicit Loc(unsigned SubKind, const void *D) 239 : DefinedSVal(const_cast<void*>(D), true, SubKind) {} 240 241public: 242 void dumpToStream(raw_ostream &Out) const; 243 244 Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {} 245 246 // Implement isa<T> support. 247 static inline bool classof(const SVal* V) { 248 return V->getBaseKind() == LocKind; 249 } 250 251 static inline bool isLocType(QualType T) { 252 return T->isAnyPointerType() || T->isBlockPointerType() || 253 T->isReferenceType(); 254 } 255}; 256 257//==------------------------------------------------------------------------==// 258// Subclasses of NonLoc. 259//==------------------------------------------------------------------------==// 260 261namespace nonloc { 262 263enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, 264 LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; 265 266/// \brief Represents symbolic expression. 267class SymbolVal : public NonLoc { 268public: 269 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {} 270 271 SymbolRef getSymbol() const { 272 return (const SymExpr*) Data; 273 } 274 275 bool isExpression() { 276 return !isa<SymbolData>(getSymbol()); 277 } 278 279 static inline bool classof(const SVal* V) { 280 return V->getBaseKind() == NonLocKind && 281 V->getSubKind() == SymbolValKind; 282 } 283 284 static inline bool classof(const NonLoc* V) { 285 return V->getSubKind() == SymbolValKind; 286 } 287}; 288 289/// \brief Value representing integer constant. 290class ConcreteInt : public NonLoc { 291public: 292 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} 293 294 const llvm::APSInt& getValue() const { 295 return *static_cast<const llvm::APSInt*>(Data); 296 } 297 298 // Transfer functions for binary/unary operations on ConcreteInts. 299 SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op, 300 const ConcreteInt& R) const; 301 302 ConcreteInt evalComplement(SValBuilder &svalBuilder) const; 303 304 ConcreteInt evalMinus(SValBuilder &svalBuilder) const; 305 306 // Implement isa<T> support. 307 static inline bool classof(const SVal* V) { 308 return V->getBaseKind() == NonLocKind && 309 V->getSubKind() == ConcreteIntKind; 310 } 311 312 static inline bool classof(const NonLoc* V) { 313 return V->getSubKind() == ConcreteIntKind; 314 } 315}; 316 317class LocAsInteger : public NonLoc { 318 friend class ento::SValBuilder; 319 320 explicit LocAsInteger(const std::pair<SVal, uintptr_t>& data) : 321 NonLoc(LocAsIntegerKind, &data) { 322 assert (isa<Loc>(data.first)); 323 } 324 325public: 326 327 Loc getLoc() const { 328 return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first); 329 } 330 331 const Loc& getPersistentLoc() const { 332 const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first; 333 return cast<Loc>(V); 334 } 335 336 unsigned getNumBits() const { 337 return ((std::pair<SVal, unsigned>*) Data)->second; 338 } 339 340 // Implement isa<T> support. 341 static inline bool classof(const SVal* V) { 342 return V->getBaseKind() == NonLocKind && 343 V->getSubKind() == LocAsIntegerKind; 344 } 345 346 static inline bool classof(const NonLoc* V) { 347 return V->getSubKind() == LocAsIntegerKind; 348 } 349}; 350 351class CompoundVal : public NonLoc { 352 friend class ento::SValBuilder; 353 354 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 355 356public: 357 const CompoundValData* getValue() const { 358 return static_cast<const CompoundValData*>(Data); 359 } 360 361 typedef llvm::ImmutableList<SVal>::iterator iterator; 362 iterator begin() const; 363 iterator end() const; 364 365 static bool classof(const SVal* V) { 366 return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind; 367 } 368 369 static bool classof(const NonLoc* V) { 370 return V->getSubKind() == CompoundValKind; 371 } 372}; 373 374class LazyCompoundVal : public NonLoc { 375 friend class ento::SValBuilder; 376 377 explicit LazyCompoundVal(const LazyCompoundValData *D) 378 : NonLoc(LazyCompoundValKind, D) {} 379public: 380 const LazyCompoundValData *getCVData() const { 381 return static_cast<const LazyCompoundValData*>(Data); 382 } 383 const void *getStore() const; 384 const TypedRegion *getRegion() const; 385 386 static bool classof(const SVal *V) { 387 return V->getBaseKind() == NonLocKind && 388 V->getSubKind() == LazyCompoundValKind; 389 } 390 static bool classof(const NonLoc *V) { 391 return V->getSubKind() == LazyCompoundValKind; 392 } 393}; 394 395} // end namespace ento::nonloc 396 397//==------------------------------------------------------------------------==// 398// Subclasses of Loc. 399//==------------------------------------------------------------------------==// 400 401namespace loc { 402 403enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind, ObjCPropRefKind }; 404 405class GotoLabel : public Loc { 406public: 407 explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {} 408 409 const LabelDecl *getLabel() const { 410 return static_cast<const LabelDecl*>(Data); 411 } 412 413 static inline bool classof(const SVal* V) { 414 return V->getBaseKind() == LocKind && V->getSubKind() == GotoLabelKind; 415 } 416 417 static inline bool classof(const Loc* V) { 418 return V->getSubKind() == GotoLabelKind; 419 } 420}; 421 422 423class MemRegionVal : public Loc { 424public: 425 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {} 426 427 const MemRegion* getRegion() const { 428 return static_cast<const MemRegion*>(Data); 429 } 430 431 const MemRegion* stripCasts() const; 432 433 template <typename REGION> 434 const REGION* getRegionAs() const { 435 return llvm::dyn_cast<REGION>(getRegion()); 436 } 437 438 inline bool operator==(const MemRegionVal& R) const { 439 return getRegion() == R.getRegion(); 440 } 441 442 inline bool operator!=(const MemRegionVal& R) const { 443 return getRegion() != R.getRegion(); 444 } 445 446 // Implement isa<T> support. 447 static inline bool classof(const SVal* V) { 448 return V->getBaseKind() == LocKind && 449 V->getSubKind() == MemRegionKind; 450 } 451 452 static inline bool classof(const Loc* V) { 453 return V->getSubKind() == MemRegionKind; 454 } 455}; 456 457class ConcreteInt : public Loc { 458public: 459 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} 460 461 const llvm::APSInt& getValue() const { 462 return *static_cast<const llvm::APSInt*>(Data); 463 } 464 465 // Transfer functions for binary/unary operations on ConcreteInts. 466 SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, 467 const ConcreteInt& R) const; 468 469 // Implement isa<T> support. 470 static inline bool classof(const SVal* V) { 471 return V->getBaseKind() == LocKind && 472 V->getSubKind() == ConcreteIntKind; 473 } 474 475 static inline bool classof(const Loc* V) { 476 return V->getSubKind() == ConcreteIntKind; 477 } 478}; 479 480/// \brief Pseudo-location SVal used by the ExprEngine to simulate a "load" or 481/// "store" of an ObjC property for the dot syntax. 482class ObjCPropRef : public Loc { 483public: 484 explicit ObjCPropRef(const ObjCPropertyRefExpr *E) 485 : Loc(ObjCPropRefKind, E) {} 486 487 const ObjCPropertyRefExpr *getPropRefExpr() const { 488 return static_cast<const ObjCPropertyRefExpr *>(Data); 489 } 490 491 // Implement isa<T> support. 492 static inline bool classof(const SVal* V) { 493 return V->getBaseKind() == LocKind && 494 V->getSubKind() == ObjCPropRefKind; 495 } 496 497 static inline bool classof(const Loc* V) { 498 return V->getSubKind() == ObjCPropRefKind; 499 } 500}; 501 502} // end ento::loc namespace 503} // end GR namespace 504 505} // end clang namespace 506 507namespace llvm { 508static inline raw_ostream &operator<<(raw_ostream &os, 509 clang::ento::SVal V) { 510 V.dumpToStream(os); 511 return os; 512} 513 514} // end llvm namespace 515 516#endif 517