SVals.h revision 66874fb18afbffb8b2ca05576851a64534be3352
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 245class NonLoc : public DefinedSVal { 246protected: 247 NonLoc() {} 248 explicit NonLoc(unsigned SubKind, const void *d) 249 : DefinedSVal(d, false, SubKind) {} 250 251public: 252 void dumpToStream(raw_ostream &Out) const; 253 254private: 255 friend class SVal; 256 static bool isKind(const SVal& V) { 257 return V.getBaseKind() == NonLocKind; 258 } 259}; 260 261class Loc : public DefinedSVal { 262protected: 263 Loc() {} 264 explicit Loc(unsigned SubKind, const void *D) 265 : DefinedSVal(const_cast<void*>(D), true, SubKind) {} 266 267public: 268 void dumpToStream(raw_ostream &Out) const; 269 270 static inline bool isLocType(QualType T) { 271 return T->isAnyPointerType() || T->isBlockPointerType() || 272 T->isReferenceType(); 273 } 274 275private: 276 friend class SVal; 277 static bool isKind(const SVal& V) { 278 return V.getBaseKind() == LocKind; 279 } 280}; 281 282//==------------------------------------------------------------------------==// 283// Subclasses of NonLoc. 284//==------------------------------------------------------------------------==// 285 286namespace nonloc { 287 288enum Kind { ConcreteIntKind, SymbolValKind, 289 LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; 290 291/// \brief Represents symbolic expression. 292class SymbolVal : public NonLoc { 293public: 294 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {} 295 296 SymbolRef getSymbol() const { 297 return (const SymExpr*) Data; 298 } 299 300 bool isExpression() const { 301 return !isa<SymbolData>(getSymbol()); 302 } 303 304private: 305 friend class SVal; 306 SymbolVal() {} 307 static bool isKind(const SVal& V) { 308 return V.getBaseKind() == NonLocKind && 309 V.getSubKind() == SymbolValKind; 310 } 311 312 static bool isKind(const NonLoc& V) { 313 return V.getSubKind() == SymbolValKind; 314 } 315}; 316 317/// \brief Value representing integer constant. 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 334private: 335 friend class SVal; 336 ConcreteInt() {} 337 static bool isKind(const SVal& V) { 338 return V.getBaseKind() == NonLocKind && 339 V.getSubKind() == ConcreteIntKind; 340 } 341 342 static bool isKind(const NonLoc& V) { 343 return V.getSubKind() == ConcreteIntKind; 344 } 345}; 346 347class LocAsInteger : public NonLoc { 348 friend class ento::SValBuilder; 349 350 explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data) 351 : NonLoc(LocAsIntegerKind, &data) { 352 assert (data.first.getAs<Loc>()); 353 } 354 355public: 356 357 Loc getLoc() const { 358 const std::pair<SVal, uintptr_t> *D = 359 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 360 return D->first.castAs<Loc>(); 361 } 362 363 Loc getPersistentLoc() const { 364 const std::pair<SVal, uintptr_t> *D = 365 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 366 const SVal& V = D->first; 367 return V.castAs<Loc>(); 368 } 369 370 unsigned getNumBits() const { 371 const std::pair<SVal, uintptr_t> *D = 372 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 373 return D->second; 374 } 375 376private: 377 friend class SVal; 378 LocAsInteger() {} 379 static bool isKind(const SVal& V) { 380 return V.getBaseKind() == NonLocKind && 381 V.getSubKind() == LocAsIntegerKind; 382 } 383 384 static bool isKind(const NonLoc& V) { 385 return V.getSubKind() == LocAsIntegerKind; 386 } 387}; 388 389class CompoundVal : public NonLoc { 390 friend class ento::SValBuilder; 391 392 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 393 394public: 395 const CompoundValData* getValue() const { 396 return static_cast<const CompoundValData*>(Data); 397 } 398 399 typedef llvm::ImmutableList<SVal>::iterator iterator; 400 iterator begin() const; 401 iterator end() const; 402 403private: 404 friend class SVal; 405 CompoundVal() {} 406 static bool isKind(const SVal& V) { 407 return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind; 408 } 409 410 static bool isKind(const NonLoc& V) { 411 return V.getSubKind() == CompoundValKind; 412 } 413}; 414 415class LazyCompoundVal : public NonLoc { 416 friend class ento::SValBuilder; 417 418 explicit LazyCompoundVal(const LazyCompoundValData *D) 419 : NonLoc(LazyCompoundValKind, D) {} 420public: 421 const LazyCompoundValData *getCVData() const { 422 return static_cast<const LazyCompoundValData*>(Data); 423 } 424 const void *getStore() const; 425 const TypedValueRegion *getRegion() const; 426 427private: 428 friend class SVal; 429 LazyCompoundVal() {} 430 static bool isKind(const SVal& V) { 431 return V.getBaseKind() == NonLocKind && 432 V.getSubKind() == LazyCompoundValKind; 433 } 434 static bool isKind(const NonLoc& V) { 435 return V.getSubKind() == LazyCompoundValKind; 436 } 437}; 438 439} // end namespace ento::nonloc 440 441//==------------------------------------------------------------------------==// 442// Subclasses of Loc. 443//==------------------------------------------------------------------------==// 444 445namespace loc { 446 447enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind }; 448 449class GotoLabel : public Loc { 450public: 451 explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {} 452 453 const LabelDecl *getLabel() const { 454 return static_cast<const LabelDecl*>(Data); 455 } 456 457private: 458 friend class SVal; 459 GotoLabel() {} 460 static bool isKind(const SVal& V) { 461 return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind; 462 } 463 464 static bool isKind(const Loc& V) { 465 return V.getSubKind() == GotoLabelKind; 466 } 467}; 468 469 470class MemRegionVal : public Loc { 471public: 472 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {} 473 474 /// \brief Get the underlining region. 475 const MemRegion* getRegion() const { 476 return static_cast<const MemRegion*>(Data); 477 } 478 479 /// \brief Get the underlining region and strip casts. 480 const MemRegion* stripCasts(bool StripBaseCasts = true) const; 481 482 template <typename REGION> 483 const REGION* getRegionAs() const { 484 return dyn_cast<REGION>(getRegion()); 485 } 486 487 inline bool operator==(const MemRegionVal& R) const { 488 return getRegion() == R.getRegion(); 489 } 490 491 inline bool operator!=(const MemRegionVal& R) const { 492 return getRegion() != R.getRegion(); 493 } 494 495private: 496 friend class SVal; 497 MemRegionVal() {} 498 static bool isKind(const SVal& V) { 499 return V.getBaseKind() == LocKind && 500 V.getSubKind() == MemRegionKind; 501 } 502 503 static bool isKind(const Loc& V) { 504 return V.getSubKind() == MemRegionKind; 505 } 506}; 507 508class ConcreteInt : public Loc { 509public: 510 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} 511 512 const llvm::APSInt& getValue() const { 513 return *static_cast<const llvm::APSInt*>(Data); 514 } 515 516 // Transfer functions for binary/unary operations on ConcreteInts. 517 SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, 518 const ConcreteInt& R) const; 519 520private: 521 friend class SVal; 522 ConcreteInt() {} 523 static bool isKind(const SVal& V) { 524 return V.getBaseKind() == LocKind && 525 V.getSubKind() == ConcreteIntKind; 526 } 527 528 static bool isKind(const Loc& V) { 529 return V.getSubKind() == ConcreteIntKind; 530 } 531}; 532 533} // end ento::loc namespace 534} // end GR namespace 535 536} // end clang namespace 537 538namespace llvm { 539static inline raw_ostream &operator<<(raw_ostream &os, 540 clang::ento::SVal V) { 541 V.dumpToStream(os); 542 return os; 543} 544 545} // end llvm namespace 546 547#endif 548