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 29namespace llvm { 30class APSInt; 31} 32 33namespace clang { 34class ASTContext; 35 36namespace ento { 37 38class AnalysisManager; 39class CallEvent; 40class CallEventManager; 41 42typedef std::unique_ptr<ConstraintManager>(*ConstraintManagerCreator)( 43 ProgramStateManager &, ExprEngine *); 44typedef std::unique_ptr<StoreManager>(*StoreManagerCreator)( 45 ProgramStateManager &); 46 47//===----------------------------------------------------------------------===// 48// ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState. 49//===----------------------------------------------------------------------===// 50 51template <typename T> struct ProgramStateTrait { 52 typedef typename T::data_type data_type; 53 static inline void *MakeVoidPtr(data_type D) { return (void*) D; } 54 static inline data_type MakeData(void *const* P) { 55 return P ? (data_type) *P : (data_type) 0; 56 } 57}; 58 59/// \class 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. 71class ProgramState : public llvm::FoldingSetNode { 72public: 73 typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; 74 typedef llvm::ImmutableMap<void*, void*> GenericDataMap; 75 76private: 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 133public: 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 483private: 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 503class ProgramStateManager { 504 friend class ProgramState; 505 friend void ProgramStateRelease(const ProgramState *state); 506private: 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 535public: 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 588public: 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 696inline ConstraintManager &ProgramState::getConstraintManager() const { 697 return stateMgr->getConstraintManager(); 698} 699 700inline const VarRegion* ProgramState::getRegion(const VarDecl *D, 701 const LocationContext *LC) const 702{ 703 return getStateManager().getRegionManager().getVarRegion(D, LC); 704} 705 706inline 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 715inline std::pair<ProgramStateRef , ProgramStateRef > 716ProgramState::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 724inline 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 736inline std::pair<ProgramStateRef, ProgramStateRef> 737ProgramState::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 749inline 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 755inline 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 763inline 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 771inline Loc ProgramState::getLValue(const VarDecl *VD, 772 const LocationContext *LC) const { 773 return getStateManager().StoreMgr->getLValueVar(VD, LC); 774} 775 776inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal, 777 const LocationContext *LC) const { 778 return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); 779} 780 781inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const { 782 return getStateManager().StoreMgr->getLValueIvar(D, Base); 783} 784 785inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const { 786 return getStateManager().StoreMgr->getLValueField(D, Base); 787} 788 789inline 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 799inline 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 805inline SVal ProgramState::getSVal(const Stmt *Ex, 806 const LocationContext *LCtx) const{ 807 return Env.getSVal(EnvironmentEntry(Ex, LCtx), 808 *getStateManager().svalBuilder); 809} 810 811inline SVal 812ProgramState::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 824inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const { 825 return getStateManager().StoreMgr->getBinding(getStore(), LV, T); 826} 827 828inline SVal ProgramState::getSVal(const MemRegion* R, QualType T) const { 829 return getStateManager().StoreMgr->getBinding(getStore(), 830 loc::MemRegionVal(R), 831 T); 832} 833 834inline BasicValueFactory &ProgramState::getBasicVals() const { 835 return getStateManager().getBasicVals(); 836} 837 838inline SymbolManager &ProgramState::getSymbolManager() const { 839 return getStateManager().getSymbolManager(); 840} 841 842template<typename T> 843ProgramStateRef ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { 844 return getStateManager().add<T>(this, K, get_context<T>()); 845} 846 847template <typename T> 848typename ProgramStateTrait<T>::context_type ProgramState::get_context() const { 849 return getStateManager().get_context<T>(); 850} 851 852template<typename T> 853ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { 854 return getStateManager().remove<T>(this, K, get_context<T>()); 855} 856 857template<typename T> 858ProgramStateRef 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 863template <typename T> 864ProgramStateRef ProgramState::remove() const { 865 return getStateManager().remove<T>(this); 866} 867 868template<typename T> 869ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { 870 return getStateManager().set<T>(this, D); 871} 872 873template<typename T> 874ProgramStateRef 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 879template<typename T> 880ProgramStateRef 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 886template <typename CB> 887CB ProgramState::scanReachableSymbols(SVal val) const { 888 CB cb(this); 889 scanReachableSymbols(val, cb); 890 return cb; 891} 892 893template <typename CB> 894CB 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. 905class ScanReachableSymbols { 906 typedef llvm::DenseSet<const void*> VisitedItems; 907 908 VisitedItems visited; 909 ProgramStateRef state; 910 SymbolVisitor &visitor; 911public: 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