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