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