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