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