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