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