ProgramState.h revision 56a46b51df691f857f7120aaf2d4deeff0b014de
1//== ProgramState.h - Path-sensitive "State" for tracking values -*- 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 SymbolRef, ExprBindKey, and ProgramState*. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_CLANG_GR_VALUESTATE_H 15#define LLVM_CLANG_GR_VALUESTATE_H 16 17#include "clang/Basic/LLVM.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 22#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 23#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h" 24#include "llvm/ADT/PointerIntPair.h" 25#include "llvm/ADT/FoldingSet.h" 26#include "llvm/ADT/ImmutableMap.h" 27 28namespace llvm { 29class APSInt; 30class BumpPtrAllocator; 31} 32 33namespace clang { 34class ASTContext; 35 36namespace ento { 37 38class CallEvent; 39class CallEventManager; 40 41typedef ConstraintManager* (*ConstraintManagerCreator)(ProgramStateManager&, 42 SubEngine&); 43typedef StoreManager* (*StoreManagerCreator)(ProgramStateManager&); 44 45//===----------------------------------------------------------------------===// 46// ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState. 47//===----------------------------------------------------------------------===// 48 49template <typename T> struct ProgramStatePartialTrait; 50 51template <typename T> struct ProgramStateTrait { 52 typedef typename T::data_type data_type; 53 static inline void *MakeVoidPtr(data_type D) { return (void*) D; } 54 static inline data_type MakeData(void *const* P) { 55 return P ? (data_type) *P : (data_type) 0; 56 } 57}; 58 59/// \class Stores the dynamic type information. 60/// Information about type of an object at runtime. This is used by dynamic 61/// dispatch implementation. 62class DynamicTypeInfo { 63 QualType T; 64 bool CanBeASubClass; 65 66public: 67 DynamicTypeInfo() : T(QualType()) {} 68 DynamicTypeInfo(QualType WithType, bool CanBeSub = true) 69 : T(WithType), CanBeASubClass(CanBeSub) {} 70 71 bool isValid() const { return !T.isNull(); } 72 73 QualType getType() const { return T; } 74 bool canBeASubClass() const { return CanBeASubClass; } 75 76 void Profile(llvm::FoldingSetNodeID &ID) const { 77 T.Profile(ID); 78 ID.AddInteger((unsigned)CanBeASubClass); 79 } 80 bool operator==(const DynamicTypeInfo &X) const { 81 return T == X.T && CanBeASubClass == X.CanBeASubClass; 82 } 83}; 84 85/// \class ProgramState 86/// ProgramState - This class encapsulates: 87/// 88/// 1. A mapping from expressions to values (Environment) 89/// 2. A mapping from locations to values (Store) 90/// 3. Constraints on symbolic values (GenericDataMap) 91/// 92/// Together these represent the "abstract state" of a program. 93/// 94/// ProgramState is intended to be used as a functional object; that is, 95/// once it is created and made "persistent" in a FoldingSet, its 96/// values will never change. 97class ProgramState : public llvm::FoldingSetNode { 98public: 99 typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; 100 typedef llvm::ImmutableMap<void*, void*> GenericDataMap; 101 102private: 103 void operator=(const ProgramState& R) const; // Do not implement. 104 105 friend class ProgramStateManager; 106 friend class ExplodedGraph; 107 friend class ExplodedNode; 108 109 ProgramStateManager *stateMgr; 110 Environment Env; // Maps a Stmt to its current SVal. 111 Store store; // Maps a location to its current value. 112 GenericDataMap GDM; // Custom data stored by a client of this class. 113 unsigned refCount; 114 115 /// makeWithStore - Return a ProgramState with the same values as the current 116 /// state with the exception of using the specified Store. 117 ProgramStateRef makeWithStore(const StoreRef &store) const; 118 119 void setStore(const StoreRef &storeRef); 120 121public: 122 /// This ctor is used when creating the first ProgramState object. 123 ProgramState(ProgramStateManager *mgr, const Environment& env, 124 StoreRef st, GenericDataMap gdm); 125 126 /// Copy ctor - We must explicitly define this or else the "Next" ptr 127 /// in FoldingSetNode will also get copied. 128 ProgramState(const ProgramState &RHS); 129 130 ~ProgramState(); 131 132 /// Return the ProgramStateManager associated with this state. 133 ProgramStateManager &getStateManager() const { return *stateMgr; } 134 135 /// getEnvironment - Return the environment associated with this state. 136 /// The environment is the mapping from expressions to values. 137 const Environment& getEnvironment() const { return Env; } 138 139 /// Return the store associated with this state. The store 140 /// is a mapping from locations to values. 141 Store getStore() const { return store; } 142 143 144 /// getGDM - Return the generic data map associated with this state. 145 GenericDataMap getGDM() const { return GDM; } 146 147 void setGDM(GenericDataMap gdm) { GDM = gdm; } 148 149 /// Profile - Profile the contents of a ProgramState object for use in a 150 /// FoldingSet. Two ProgramState objects are considered equal if they 151 /// have the same Environment, Store, and GenericDataMap. 152 static void Profile(llvm::FoldingSetNodeID& ID, const ProgramState *V) { 153 V->Env.Profile(ID); 154 ID.AddPointer(V->store); 155 V->GDM.Profile(ID); 156 } 157 158 /// Profile - Used to profile the contents of this object for inclusion 159 /// in a FoldingSet. 160 void Profile(llvm::FoldingSetNodeID& ID) const { 161 Profile(ID, this); 162 } 163 164 BasicValueFactory &getBasicVals() const; 165 SymbolManager &getSymbolManager() const; 166 167 //==---------------------------------------------------------------------==// 168 // Constraints on values. 169 //==---------------------------------------------------------------------==// 170 // 171 // Each ProgramState records constraints on symbolic values. These constraints 172 // are managed using the ConstraintManager associated with a ProgramStateManager. 173 // As constraints gradually accrue on symbolic values, added constraints 174 // may conflict and indicate that a state is infeasible (as no real values 175 // could satisfy all the constraints). This is the principal mechanism 176 // for modeling path-sensitivity in ExprEngine/ProgramState. 177 // 178 // Various "assume" methods form the interface for adding constraints to 179 // symbolic values. A call to 'assume' indicates an assumption being placed 180 // on one or symbolic values. 'assume' methods take the following inputs: 181 // 182 // (1) A ProgramState object representing the current state. 183 // 184 // (2) The assumed constraint (which is specific to a given "assume" method). 185 // 186 // (3) A binary value "Assumption" that indicates whether the constraint is 187 // assumed to be true or false. 188 // 189 // The output of "assume*" is a new ProgramState object with the added constraints. 190 // If no new state is feasible, NULL is returned. 191 // 192 193 ProgramStateRef assume(DefinedOrUnknownSVal cond, bool assumption) const; 194 195 /// This method assumes both "true" and "false" for 'cond', and 196 /// returns both corresponding states. It's shorthand for doing 197 /// 'assume' twice. 198 std::pair<ProgramStateRef , ProgramStateRef > 199 assume(DefinedOrUnknownSVal cond) const; 200 201 ProgramStateRef assumeInBound(DefinedOrUnknownSVal idx, 202 DefinedOrUnknownSVal upperBound, 203 bool assumption, 204 QualType IndexType = QualType()) const; 205 206 /// Utility method for getting regions. 207 const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; 208 209 //==---------------------------------------------------------------------==// 210 // Binding and retrieving values to/from the environment and symbolic store. 211 //==---------------------------------------------------------------------==// 212 213 /// \brief Create a new state with the specified CompoundLiteral binding. 214 /// \param CL the compound literal expression (the binding key) 215 /// \param LC the LocationContext of the binding 216 /// \param V the value to bind. 217 ProgramStateRef bindCompoundLiteral(const CompoundLiteralExpr *CL, 218 const LocationContext *LC, 219 SVal V) const; 220 221 /// Create a new state by binding the value 'V' to the statement 'S' in the 222 /// state's environment. 223 ProgramStateRef BindExpr(const Stmt *S, const LocationContext *LCtx, 224 SVal V, bool Invalidate = true) const; 225 226 /// Create a new state by binding the value 'V' and location 'locaton' to the 227 /// statement 'S' in the state's environment. 228 ProgramStateRef bindExprAndLocation(const Stmt *S, 229 const LocationContext *LCtx, 230 SVal location, SVal V) const; 231 232 ProgramStateRef bindLoc(Loc location, 233 SVal V, 234 bool notifyChanges = true) const; 235 236 ProgramStateRef bindLoc(SVal location, SVal V) const; 237 238 ProgramStateRef bindDefault(SVal loc, SVal V) const; 239 240 ProgramStateRef killBinding(Loc LV) const; 241 242 /// invalidateRegions - Returns the state with bindings for the given regions 243 /// cleared from the store. The regions are provided as a continuous array 244 /// from Begin to End. Optionally invalidates global regions as well. 245 ProgramStateRef invalidateRegions(ArrayRef<const MemRegion *> Regions, 246 const Expr *E, unsigned BlockCount, 247 const LocationContext *LCtx, 248 StoreManager::InvalidatedSymbols *IS = 0, 249 const CallEvent *Call = 0) const; 250 251 /// enterStackFrame - Returns the state for entry to the given stack frame, 252 /// preserving the current state. 253 ProgramStateRef enterStackFrame(const CallEvent &Call, 254 const StackFrameContext *CalleeCtx) const; 255 256 /// Get the lvalue for a variable reference. 257 Loc getLValue(const VarDecl *D, const LocationContext *LC) const; 258 259 Loc getLValue(const CompoundLiteralExpr *literal, 260 const LocationContext *LC) const; 261 262 /// Get the lvalue for an ivar reference. 263 SVal getLValue(const ObjCIvarDecl *decl, SVal base) const; 264 265 /// Get the lvalue for a field reference. 266 SVal getLValue(const FieldDecl *decl, SVal Base) const; 267 268 /// Get the lvalue for an indirect field reference. 269 SVal getLValue(const IndirectFieldDecl *decl, SVal Base) const; 270 271 /// Get the lvalue for an array index. 272 SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; 273 274 const llvm::APSInt *getSymVal(SymbolRef sym) const; 275 276 /// Returns the SVal bound to the statement 'S' in the state's environment. 277 SVal getSVal(const Stmt *S, const LocationContext *LCtx, 278 bool useOnlyDirectBindings = false) const; 279 280 SVal getSValAsScalarOrLoc(const Stmt *Ex, const LocationContext *LCtx) const; 281 282 /// \brief Return the value bound to the specified location. 283 /// Returns UnknownVal() if none found. 284 SVal getSVal(Loc LV, QualType T = QualType()) const; 285 286 /// Returns the "raw" SVal bound to LV before any value simplfication. 287 SVal getRawSVal(Loc LV, QualType T= QualType()) const; 288 289 /// \brief Return the value bound to the specified location. 290 /// Returns UnknownVal() if none found. 291 SVal getSVal(const MemRegion* R) const; 292 293 SVal getSValAsScalarOrLoc(const MemRegion *R) const; 294 295 /// \brief Visits the symbols reachable from the given SVal using the provided 296 /// SymbolVisitor. 297 /// 298 /// This is a convenience API. Consider using ScanReachableSymbols class 299 /// directly when making multiple scans on the same state with the same 300 /// visitor to avoid repeated initialization cost. 301 /// \sa ScanReachableSymbols 302 bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; 303 304 /// \brief Visits the symbols reachable from the SVals in the given range 305 /// using the provided SymbolVisitor. 306 bool scanReachableSymbols(const SVal *I, const SVal *E, 307 SymbolVisitor &visitor) const; 308 309 /// \brief Visits the symbols reachable from the regions in the given 310 /// MemRegions range using the provided SymbolVisitor. 311 bool scanReachableSymbols(const MemRegion * const *I, 312 const MemRegion * const *E, 313 SymbolVisitor &visitor) const; 314 315 template <typename CB> CB scanReachableSymbols(SVal val) const; 316 template <typename CB> CB scanReachableSymbols(const SVal *beg, 317 const SVal *end) const; 318 319 template <typename CB> CB 320 scanReachableSymbols(const MemRegion * const *beg, 321 const MemRegion * const *end) const; 322 323 /// Create a new state in which the statement is marked as tainted. 324 ProgramStateRef addTaint(const Stmt *S, const LocationContext *LCtx, 325 TaintTagType Kind = TaintTagGeneric) const; 326 327 /// Create a new state in which the symbol is marked as tainted. 328 ProgramStateRef addTaint(SymbolRef S, 329 TaintTagType Kind = TaintTagGeneric) const; 330 331 /// Create a new state in which the region symbol is marked as tainted. 332 ProgramStateRef addTaint(const MemRegion *R, 333 TaintTagType Kind = TaintTagGeneric) const; 334 335 /// Check if the statement is tainted in the current state. 336 bool isTainted(const Stmt *S, const LocationContext *LCtx, 337 TaintTagType Kind = TaintTagGeneric) const; 338 bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const; 339 bool isTainted(SymbolRef Sym, TaintTagType Kind = TaintTagGeneric) const; 340 bool isTainted(const MemRegion *Reg, TaintTagType Kind=TaintTagGeneric) const; 341 342 /// \brief Get dynamic type information for a region. 343 DynamicTypeInfo getDynamicTypeInfo(const MemRegion *Reg) const; 344 345 /// \brief Set dynamic type information of the region; return the new state. 346 ProgramStateRef setDynamicTypeInfo(const MemRegion *Reg, 347 DynamicTypeInfo NewTy) const; 348 349 /// \brief Set dynamic type information of the region; return the new state. 350 ProgramStateRef setDynamicTypeInfo(const MemRegion *Reg, 351 QualType NewTy, 352 bool CanBeSubClassed = true) const { 353 return setDynamicTypeInfo(Reg, DynamicTypeInfo(NewTy, CanBeSubClassed)); 354 } 355 356 //==---------------------------------------------------------------------==// 357 // Accessing the Generic Data Map (GDM). 358 //==---------------------------------------------------------------------==// 359 360 void *const* FindGDM(void *K) const; 361 362 template<typename T> 363 ProgramStateRef add(typename ProgramStateTrait<T>::key_type K) const; 364 365 template <typename T> 366 typename ProgramStateTrait<T>::data_type 367 get() const { 368 return ProgramStateTrait<T>::MakeData(FindGDM(ProgramStateTrait<T>::GDMIndex())); 369 } 370 371 template<typename T> 372 typename ProgramStateTrait<T>::lookup_type 373 get(typename ProgramStateTrait<T>::key_type key) const { 374 void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); 375 return ProgramStateTrait<T>::Lookup(ProgramStateTrait<T>::MakeData(d), key); 376 } 377 378 template <typename T> 379 typename ProgramStateTrait<T>::context_type get_context() const; 380 381 382 template<typename T> 383 ProgramStateRef remove(typename ProgramStateTrait<T>::key_type K) const; 384 385 template<typename T> 386 ProgramStateRef remove(typename ProgramStateTrait<T>::key_type K, 387 typename ProgramStateTrait<T>::context_type C) const; 388 template <typename T> 389 ProgramStateRef remove() const; 390 391 template<typename T> 392 ProgramStateRef set(typename ProgramStateTrait<T>::data_type D) const; 393 394 template<typename T> 395 ProgramStateRef set(typename ProgramStateTrait<T>::key_type K, 396 typename ProgramStateTrait<T>::value_type E) const; 397 398 template<typename T> 399 ProgramStateRef set(typename ProgramStateTrait<T>::key_type K, 400 typename ProgramStateTrait<T>::value_type E, 401 typename ProgramStateTrait<T>::context_type C) const; 402 403 template<typename T> 404 bool contains(typename ProgramStateTrait<T>::key_type key) const { 405 void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); 406 return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key); 407 } 408 409 // Pretty-printing. 410 void print(raw_ostream &Out, const char *nl = "\n", 411 const char *sep = "") const; 412 void printDOT(raw_ostream &Out) const; 413 void printTaint(raw_ostream &Out, const char *nl = "\n", 414 const char *sep = "") const; 415 416 void dump() const; 417 void dumpTaint() const; 418 419private: 420 friend void ProgramStateRetain(const ProgramState *state); 421 friend void ProgramStateRelease(const ProgramState *state); 422 423 ProgramStateRef 424 invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, 425 const Expr *E, unsigned BlockCount, 426 const LocationContext *LCtx, 427 StoreManager::InvalidatedSymbols &IS, 428 const CallEvent *Call) const; 429}; 430 431//===----------------------------------------------------------------------===// 432// ProgramStateManager - Factory object for ProgramStates. 433//===----------------------------------------------------------------------===// 434 435class ProgramStateManager { 436 friend class ProgramState; 437 friend void ProgramStateRelease(const ProgramState *state); 438private: 439 /// Eng - The SubEngine that owns this state manager. 440 SubEngine *Eng; /* Can be null. */ 441 442 EnvironmentManager EnvMgr; 443 OwningPtr<StoreManager> StoreMgr; 444 OwningPtr<ConstraintManager> ConstraintMgr; 445 446 ProgramState::GenericDataMap::Factory GDMFactory; 447 448 typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy; 449 GDMContextsTy GDMContexts; 450 451 /// StateSet - FoldingSet containing all the states created for analyzing 452 /// a particular function. This is used to unique states. 453 llvm::FoldingSet<ProgramState> StateSet; 454 455 /// Object that manages the data for all created SVals. 456 OwningPtr<SValBuilder> svalBuilder; 457 458 /// Manages memory for created CallEvents. 459 OwningPtr<CallEventManager> CallEventMgr; 460 461 /// A BumpPtrAllocator to allocate states. 462 llvm::BumpPtrAllocator &Alloc; 463 464 /// A vector of ProgramStates that we can reuse. 465 std::vector<ProgramState *> freeStates; 466 467public: 468 ProgramStateManager(ASTContext &Ctx, 469 StoreManagerCreator CreateStoreManager, 470 ConstraintManagerCreator CreateConstraintManager, 471 llvm::BumpPtrAllocator& alloc, 472 SubEngine &subeng); 473 474 ~ProgramStateManager(); 475 476 ProgramStateRef getInitialState(const LocationContext *InitLoc); 477 478 ASTContext &getContext() { return svalBuilder->getContext(); } 479 const ASTContext &getContext() const { return svalBuilder->getContext(); } 480 481 BasicValueFactory &getBasicVals() { 482 return svalBuilder->getBasicValueFactory(); 483 } 484 const BasicValueFactory& getBasicVals() const { 485 return svalBuilder->getBasicValueFactory(); 486 } 487 488 SValBuilder &getSValBuilder() { 489 return *svalBuilder; 490 } 491 492 SymbolManager &getSymbolManager() { 493 return svalBuilder->getSymbolManager(); 494 } 495 const SymbolManager &getSymbolManager() const { 496 return svalBuilder->getSymbolManager(); 497 } 498 499 llvm::BumpPtrAllocator& getAllocator() { return Alloc; } 500 501 MemRegionManager& getRegionManager() { 502 return svalBuilder->getRegionManager(); 503 } 504 const MemRegionManager& getRegionManager() const { 505 return svalBuilder->getRegionManager(); 506 } 507 508 CallEventManager &getCallEventManager() { return *CallEventMgr; } 509 510 StoreManager& getStoreManager() { return *StoreMgr; } 511 ConstraintManager& getConstraintManager() { return *ConstraintMgr; } 512 SubEngine* getOwningEngine() { return Eng; } 513 514 ProgramStateRef removeDeadBindings(ProgramStateRef St, 515 const StackFrameContext *LCtx, 516 SymbolReaper& SymReaper); 517 518 /// Marshal a new state for the callee in another translation unit. 519 /// 'state' is owned by the caller's engine. 520 ProgramStateRef MarshalState(ProgramStateRef state, const StackFrameContext *L); 521 522public: 523 524 SVal ArrayToPointer(Loc Array) { 525 return StoreMgr->ArrayToPointer(Array); 526 } 527 528 // Methods that manipulate the GDM. 529 ProgramStateRef addGDM(ProgramStateRef St, void *Key, void *Data); 530 ProgramStateRef removeGDM(ProgramStateRef state, void *Key); 531 532 // Methods that query & manipulate the Store. 533 534 void iterBindings(ProgramStateRef state, StoreManager::BindingsHandler& F) { 535 StoreMgr->iterBindings(state->getStore(), F); 536 } 537 538 ProgramStateRef getPersistentState(ProgramState &Impl); 539 ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, 540 ProgramStateRef GDMState); 541 542 bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) { 543 return S1->Env == S2->Env; 544 } 545 546 bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) { 547 return S1->store == S2->store; 548 } 549 550 //==---------------------------------------------------------------------==// 551 // Generic Data Map methods. 552 //==---------------------------------------------------------------------==// 553 // 554 // ProgramStateManager and ProgramState support a "generic data map" that allows 555 // different clients of ProgramState objects to embed arbitrary data within a 556 // ProgramState object. The generic data map is essentially an immutable map 557 // from a "tag" (that acts as the "key" for a client) and opaque values. 558 // Tags/keys and values are simply void* values. The typical way that clients 559 // generate unique tags are by taking the address of a static variable. 560 // Clients are responsible for ensuring that data values referred to by a 561 // the data pointer are immutable (and thus are essentially purely functional 562 // data). 563 // 564 // The templated methods below use the ProgramStateTrait<T> class 565 // to resolve keys into the GDM and to return data values to clients. 566 // 567 568 // Trait based GDM dispatch. 569 template <typename T> 570 ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait<T>::data_type D) { 571 return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 572 ProgramStateTrait<T>::MakeVoidPtr(D)); 573 } 574 575 template<typename T> 576 ProgramStateRef set(ProgramStateRef st, 577 typename ProgramStateTrait<T>::key_type K, 578 typename ProgramStateTrait<T>::value_type V, 579 typename ProgramStateTrait<T>::context_type C) { 580 581 return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 582 ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Set(st->get<T>(), K, V, C))); 583 } 584 585 template <typename T> 586 ProgramStateRef add(ProgramStateRef st, 587 typename ProgramStateTrait<T>::key_type K, 588 typename ProgramStateTrait<T>::context_type C) { 589 return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 590 ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Add(st->get<T>(), K, C))); 591 } 592 593 template <typename T> 594 ProgramStateRef remove(ProgramStateRef st, 595 typename ProgramStateTrait<T>::key_type K, 596 typename ProgramStateTrait<T>::context_type C) { 597 598 return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 599 ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Remove(st->get<T>(), K, C))); 600 } 601 602 template <typename T> 603 ProgramStateRef remove(ProgramStateRef st) { 604 return removeGDM(st, ProgramStateTrait<T>::GDMIndex()); 605 } 606 607 void *FindGDMContext(void *index, 608 void *(*CreateContext)(llvm::BumpPtrAllocator&), 609 void (*DeleteContext)(void*)); 610 611 template <typename T> 612 typename ProgramStateTrait<T>::context_type get_context() { 613 void *p = FindGDMContext(ProgramStateTrait<T>::GDMIndex(), 614 ProgramStateTrait<T>::CreateContext, 615 ProgramStateTrait<T>::DeleteContext); 616 617 return ProgramStateTrait<T>::MakeContext(p); 618 } 619 620 const llvm::APSInt* getSymVal(ProgramStateRef St, SymbolRef sym) { 621 return ConstraintMgr->getSymVal(St, sym); 622 } 623 624 void EndPath(ProgramStateRef St) { 625 ConstraintMgr->EndPath(St); 626 } 627}; 628 629 630//===----------------------------------------------------------------------===// 631// Out-of-line method definitions for ProgramState. 632//===----------------------------------------------------------------------===// 633 634inline const VarRegion* ProgramState::getRegion(const VarDecl *D, 635 const LocationContext *LC) const 636{ 637 return getStateManager().getRegionManager().getVarRegion(D, LC); 638} 639 640inline ProgramStateRef ProgramState::assume(DefinedOrUnknownSVal Cond, 641 bool Assumption) const { 642 if (Cond.isUnknown()) 643 return this; 644 645 return getStateManager().ConstraintMgr->assume(this, cast<DefinedSVal>(Cond), 646 Assumption); 647} 648 649inline std::pair<ProgramStateRef , ProgramStateRef > 650ProgramState::assume(DefinedOrUnknownSVal Cond) const { 651 if (Cond.isUnknown()) 652 return std::make_pair(this, this); 653 654 return getStateManager().ConstraintMgr->assumeDual(this, 655 cast<DefinedSVal>(Cond)); 656} 657 658inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V) const { 659 return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V); 660} 661 662inline Loc ProgramState::getLValue(const VarDecl *VD, 663 const LocationContext *LC) const { 664 return getStateManager().StoreMgr->getLValueVar(VD, LC); 665} 666 667inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal, 668 const LocationContext *LC) const { 669 return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); 670} 671 672inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const { 673 return getStateManager().StoreMgr->getLValueIvar(D, Base); 674} 675 676inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const { 677 return getStateManager().StoreMgr->getLValueField(D, Base); 678} 679 680inline SVal ProgramState::getLValue(const IndirectFieldDecl *D, 681 SVal Base) const { 682 StoreManager &SM = *getStateManager().StoreMgr; 683 for (IndirectFieldDecl::chain_iterator I = D->chain_begin(), 684 E = D->chain_end(); 685 I != E; ++I) { 686 Base = SM.getLValueField(cast<FieldDecl>(*I), Base); 687 } 688 689 return Base; 690} 691 692inline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ 693 if (NonLoc *N = dyn_cast<NonLoc>(&Idx)) 694 return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base); 695 return UnknownVal(); 696} 697 698inline const llvm::APSInt *ProgramState::getSymVal(SymbolRef sym) const { 699 return getStateManager().getSymVal(this, sym); 700} 701 702inline SVal ProgramState::getSVal(const Stmt *Ex, const LocationContext *LCtx, 703 bool useOnlyDirectBindings) const{ 704 return Env.getSVal(EnvironmentEntry(Ex, LCtx), 705 *getStateManager().svalBuilder, 706 useOnlyDirectBindings); 707} 708 709inline SVal 710ProgramState::getSValAsScalarOrLoc(const Stmt *S, 711 const LocationContext *LCtx) const { 712 if (const Expr *Ex = dyn_cast<Expr>(S)) { 713 QualType T = Ex->getType(); 714 if (Ex->isGLValue() || Loc::isLocType(T) || T->isIntegerType()) 715 return getSVal(S, LCtx); 716 } 717 718 return UnknownVal(); 719} 720 721inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const { 722 return getStateManager().StoreMgr->getBinding(getStore(), LV, T); 723} 724 725inline SVal ProgramState::getSVal(const MemRegion* R) const { 726 return getStateManager().StoreMgr->getBinding(getStore(), 727 loc::MemRegionVal(R)); 728} 729 730inline BasicValueFactory &ProgramState::getBasicVals() const { 731 return getStateManager().getBasicVals(); 732} 733 734inline SymbolManager &ProgramState::getSymbolManager() const { 735 return getStateManager().getSymbolManager(); 736} 737 738template<typename T> 739ProgramStateRef ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { 740 return getStateManager().add<T>(this, K, get_context<T>()); 741} 742 743template <typename T> 744typename ProgramStateTrait<T>::context_type ProgramState::get_context() const { 745 return getStateManager().get_context<T>(); 746} 747 748template<typename T> 749ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { 750 return getStateManager().remove<T>(this, K, get_context<T>()); 751} 752 753template<typename T> 754ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K, 755 typename ProgramStateTrait<T>::context_type C) const { 756 return getStateManager().remove<T>(this, K, C); 757} 758 759template <typename T> 760ProgramStateRef ProgramState::remove() const { 761 return getStateManager().remove<T>(this); 762} 763 764template<typename T> 765ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { 766 return getStateManager().set<T>(this, D); 767} 768 769template<typename T> 770ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, 771 typename ProgramStateTrait<T>::value_type E) const { 772 return getStateManager().set<T>(this, K, E, get_context<T>()); 773} 774 775template<typename T> 776ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, 777 typename ProgramStateTrait<T>::value_type E, 778 typename ProgramStateTrait<T>::context_type C) const { 779 return getStateManager().set<T>(this, K, E, C); 780} 781 782template <typename CB> 783CB ProgramState::scanReachableSymbols(SVal val) const { 784 CB cb(this); 785 scanReachableSymbols(val, cb); 786 return cb; 787} 788 789template <typename CB> 790CB ProgramState::scanReachableSymbols(const SVal *beg, const SVal *end) const { 791 CB cb(this); 792 scanReachableSymbols(beg, end, cb); 793 return cb; 794} 795 796template <typename CB> 797CB ProgramState::scanReachableSymbols(const MemRegion * const *beg, 798 const MemRegion * const *end) const { 799 CB cb(this); 800 scanReachableSymbols(beg, end, cb); 801 return cb; 802} 803 804/// \class ScanReachableSymbols 805/// A Utility class that allows to visit the reachable symbols using a custom 806/// SymbolVisitor. 807class ScanReachableSymbols { 808 typedef llvm::DenseMap<const void*, unsigned> VisitedItems; 809 810 VisitedItems visited; 811 ProgramStateRef state; 812 SymbolVisitor &visitor; 813public: 814 815 ScanReachableSymbols(ProgramStateRef st, SymbolVisitor& v) 816 : state(st), visitor(v) {} 817 818 bool scan(nonloc::CompoundVal val); 819 bool scan(SVal val); 820 bool scan(const MemRegion *R); 821 bool scan(const SymExpr *sym); 822}; 823 824} // end GR namespace 825 826} // end clang namespace 827 828#endif 829