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 26 namespace clang { 27 28 namespace ento { 29 30 class CompoundValData; 31 class LazyCompoundValData; 32 class ProgramState; 33 class BasicValueFactory; 34 class MemRegion; 35 class TypedRegion; 36 class MemRegionManager; 37 class ProgramStateManager; 38 class SValBuilder; 39 40 /// SVal - This represents a symbolic expression, which can be either 41 /// an L-value or an R-value. 42 /// 43 class SVal { 44 public: 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 55 protected: 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 68 public: 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 174 class UndefinedVal : public SVal { 175 public: 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 186 class DefinedOrUnknownSVal : public SVal { 187 private: 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 193 protected: 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 200 public: 201 // Implement isa<T> support. 202 static inline bool classof(const SVal *V) { 203 return !V->isUndef(); 204 } 205 }; 206 207 class UnknownVal : public DefinedOrUnknownSVal { 208 public: 209 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {} 210 211 static inline bool classof(const SVal *V) { 212 return V->getBaseKind() == UnknownKind; 213 } 214 }; 215 216 class DefinedSVal : public DefinedOrUnknownSVal { 217 private: 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; 223 protected: 224 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) 225 : DefinedOrUnknownSVal(d, isLoc, ValKind) {} 226 public: 227 // Implement isa<T> support. 228 static inline bool classof(const SVal *V) { 229 return !V->isUnknownOrUndef(); 230 } 231 }; 232 233 class NonLoc : public DefinedSVal { 234 protected: 235 explicit NonLoc(unsigned SubKind, const void *d) 236 : DefinedSVal(d, false, SubKind) {} 237 238 public: 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 247 class Loc : public DefinedSVal { 248 protected: 249 explicit Loc(unsigned SubKind, const void *D) 250 : DefinedSVal(const_cast<void*>(D), true, SubKind) {} 251 252 public: 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 272 namespace nonloc { 273 274 enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, 275 LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; 276 277 class SymbolVal : public NonLoc { 278 public: 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 295 class SymExprVal : public NonLoc { 296 public: 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 314 class ConcreteInt : public NonLoc { 315 public: 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 341 class 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 349 public: 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 375 class CompoundVal : public NonLoc { 376 friend class ento::SValBuilder; 377 378 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 379 380 public: 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 398 class LazyCompoundVal : public NonLoc { 399 friend class ento::SValBuilder; 400 401 explicit LazyCompoundVal(const LazyCompoundValData *D) 402 : NonLoc(LazyCompoundValKind, D) {} 403 public: 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 425 namespace loc { 426 427 enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind, ObjCPropRefKind }; 428 429 class GotoLabel : public Loc { 430 public: 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 447 class MemRegionVal : public Loc { 448 public: 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 481 class ConcreteInt : public Loc { 482 public: 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. 506 class ObjCPropRef : public Loc { 507 public: 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 531 namespace llvm { 532 static 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