SVals.h revision 48a7345a0bffcb01290447c73c6f17680d80f02f
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 "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.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 TypedRegion; 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 /// 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 159 160class UndefinedVal : public SVal { 161public: 162 UndefinedVal() : SVal(UndefinedKind) {} 163 164 static inline bool classof(const SVal* V) { 165 return V->getBaseKind() == UndefinedKind; 166 } 167}; 168 169class DefinedOrUnknownSVal : public SVal { 170private: 171 // Do not implement. We want calling these methods to be a compiler 172 // error since they are tautologically false. 173 bool isUndef() const; 174 bool isValid() const; 175 176protected: 177 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind) 178 : SVal(d, isLoc, ValKind) {} 179 180 explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL) 181 : SVal(k, D) {} 182 183public: 184 // Implement isa<T> support. 185 static inline bool classof(const SVal *V) { 186 return !V->isUndef(); 187 } 188}; 189 190class UnknownVal : public DefinedOrUnknownSVal { 191public: 192 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {} 193 194 static inline bool classof(const SVal *V) { 195 return V->getBaseKind() == UnknownKind; 196 } 197}; 198 199class DefinedSVal : public DefinedOrUnknownSVal { 200private: 201 // Do not implement. We want calling these methods to be a compiler 202 // error since they are tautologically true/false. 203 bool isUnknown() const; 204 bool isUnknownOrUndef() const; 205 bool isValid() const; 206protected: 207 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind) 208 : DefinedOrUnknownSVal(d, isLoc, ValKind) {} 209public: 210 // Implement isa<T> support. 211 static inline bool classof(const SVal *V) { 212 return !V->isUnknownOrUndef(); 213 } 214}; 215 216class NonLoc : public DefinedSVal { 217protected: 218 explicit NonLoc(unsigned SubKind, const void *d) 219 : DefinedSVal(d, false, SubKind) {} 220 221public: 222 void dumpToStream(raw_ostream &Out) const; 223 224 // Implement isa<T> support. 225 static inline bool classof(const SVal* V) { 226 return V->getBaseKind() == NonLocKind; 227 } 228}; 229 230class Loc : public DefinedSVal { 231protected: 232 explicit Loc(unsigned SubKind, const void *D) 233 : DefinedSVal(const_cast<void*>(D), true, SubKind) {} 234 235public: 236 void dumpToStream(raw_ostream &Out) const; 237 238 // Implement isa<T> support. 239 static inline bool classof(const SVal* V) { 240 return V->getBaseKind() == LocKind; 241 } 242 243 static inline bool isLocType(QualType T) { 244 return T->isAnyPointerType() || T->isBlockPointerType() || 245 T->isReferenceType(); 246 } 247}; 248 249//==------------------------------------------------------------------------==// 250// Subclasses of NonLoc. 251//==------------------------------------------------------------------------==// 252 253namespace nonloc { 254 255enum Kind { ConcreteIntKind, SymbolValKind, 256 LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; 257 258/// \brief Represents symbolic expression. 259class SymbolVal : public NonLoc { 260public: 261 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {} 262 263 SymbolRef getSymbol() const { 264 return (const SymExpr*) Data; 265 } 266 267 bool isExpression() { 268 return !isa<SymbolData>(getSymbol()); 269 } 270 271 static inline bool classof(const SVal* V) { 272 return V->getBaseKind() == NonLocKind && 273 V->getSubKind() == SymbolValKind; 274 } 275 276 static inline bool classof(const NonLoc* V) { 277 return V->getSubKind() == SymbolValKind; 278 } 279}; 280 281/// \brief Value representing integer constant. 282class ConcreteInt : public NonLoc { 283public: 284 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} 285 286 const llvm::APSInt& getValue() const { 287 return *static_cast<const llvm::APSInt*>(Data); 288 } 289 290 // Transfer functions for binary/unary operations on ConcreteInts. 291 SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op, 292 const ConcreteInt& R) const; 293 294 ConcreteInt evalComplement(SValBuilder &svalBuilder) const; 295 296 ConcreteInt evalMinus(SValBuilder &svalBuilder) const; 297 298 // Implement isa<T> support. 299 static inline bool classof(const SVal* V) { 300 return V->getBaseKind() == NonLocKind && 301 V->getSubKind() == ConcreteIntKind; 302 } 303 304 static inline bool classof(const NonLoc* V) { 305 return V->getSubKind() == ConcreteIntKind; 306 } 307}; 308 309class LocAsInteger : public NonLoc { 310 friend class ento::SValBuilder; 311 312 explicit LocAsInteger(const std::pair<SVal, uintptr_t>& data) : 313 NonLoc(LocAsIntegerKind, &data) { 314 assert (isa<Loc>(data.first)); 315 } 316 317public: 318 319 Loc getLoc() const { 320 const std::pair<SVal, uintptr_t> *D = 321 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 322 return cast<Loc>(D->first); 323 } 324 325 const Loc& getPersistentLoc() const { 326 const std::pair<SVal, uintptr_t> *D = 327 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 328 const SVal& V = D->first; 329 return cast<Loc>(V); 330 } 331 332 unsigned getNumBits() const { 333 const std::pair<SVal, uintptr_t> *D = 334 static_cast<const std::pair<SVal, uintptr_t> *>(Data); 335 return D->second; 336 } 337 338 // Implement isa<T> support. 339 static inline bool classof(const SVal* V) { 340 return V->getBaseKind() == NonLocKind && 341 V->getSubKind() == LocAsIntegerKind; 342 } 343 344 static inline bool classof(const NonLoc* V) { 345 return V->getSubKind() == LocAsIntegerKind; 346 } 347}; 348 349class CompoundVal : public NonLoc { 350 friend class ento::SValBuilder; 351 352 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 353 354public: 355 const CompoundValData* getValue() const { 356 return static_cast<const CompoundValData*>(Data); 357 } 358 359 typedef llvm::ImmutableList<SVal>::iterator iterator; 360 iterator begin() const; 361 iterator end() const; 362 363 static bool classof(const SVal* V) { 364 return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind; 365 } 366 367 static bool classof(const NonLoc* V) { 368 return V->getSubKind() == CompoundValKind; 369 } 370}; 371 372class LazyCompoundVal : public NonLoc { 373 friend class ento::SValBuilder; 374 375 explicit LazyCompoundVal(const LazyCompoundValData *D) 376 : NonLoc(LazyCompoundValKind, D) {} 377public: 378 const LazyCompoundValData *getCVData() const { 379 return static_cast<const LazyCompoundValData*>(Data); 380 } 381 const void *getStore() const; 382 const TypedRegion *getRegion() const; 383 384 static bool classof(const SVal *V) { 385 return V->getBaseKind() == NonLocKind && 386 V->getSubKind() == LazyCompoundValKind; 387 } 388 static bool classof(const NonLoc *V) { 389 return V->getSubKind() == LazyCompoundValKind; 390 } 391}; 392 393} // end namespace ento::nonloc 394 395//==------------------------------------------------------------------------==// 396// Subclasses of Loc. 397//==------------------------------------------------------------------------==// 398 399namespace loc { 400 401enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind }; 402 403class GotoLabel : public Loc { 404public: 405 explicit GotoLabel(LabelDecl *Label) : Loc(GotoLabelKind, Label) {} 406 407 const LabelDecl *getLabel() const { 408 return static_cast<const LabelDecl*>(Data); 409 } 410 411 static inline bool classof(const SVal* V) { 412 return V->getBaseKind() == LocKind && V->getSubKind() == GotoLabelKind; 413 } 414 415 static inline bool classof(const Loc* V) { 416 return V->getSubKind() == GotoLabelKind; 417 } 418}; 419 420 421class MemRegionVal : public Loc { 422public: 423 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {} 424 425 /// \brief Get the underlining region. 426 const MemRegion* getRegion() const { 427 return static_cast<const MemRegion*>(Data); 428 } 429 430 /// \brief Get the underlining region and strip casts. 431 const MemRegion* stripCasts(bool StripBaseCasts = true) 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} // end ento::loc namespace 481} // end GR namespace 482 483} // end clang namespace 484 485namespace llvm { 486static inline raw_ostream &operator<<(raw_ostream &os, 487 clang::ento::SVal V) { 488 V.dumpToStream(os); 489 return os; 490} 491 492} // end llvm namespace 493 494#endif 495