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