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(Ptr: V->store); |

176 | V->GDM.Profile(ID); |

177 | ID.AddBoolean(B: 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, V: 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(K: 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(K: 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(K: 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 | SVal wrapSymbolicRegion(SVal Base) const; |

499 | }; |

500 | |

501 | //===----------------------------------------------------------------------===// |

502 | // ProgramStateManager - Factory object for ProgramStates. |

503 | //===----------------------------------------------------------------------===// |

504 | |

505 | class ProgramStateManager { |

506 | friend class ProgramState; |

507 | friend void ProgramStateRelease(const ProgramState *state); |

508 | private: |

509 | /// Eng - The ExprEngine that owns this state manager. |

510 | ExprEngine *Eng; /* Can be null. */ |

511 | |

512 | EnvironmentManager EnvMgr; |

513 | std::unique_ptr<StoreManager> StoreMgr; |

514 | std::unique_ptr<ConstraintManager> ConstraintMgr; |

515 | |

516 | ProgramState::GenericDataMap::Factory GDMFactory; |

517 | |

518 | typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy; |

519 | GDMContextsTy GDMContexts; |

520 | |

521 | /// StateSet - FoldingSet containing all the states created for analyzing |

522 | /// a particular function. This is used to unique states. |

523 | llvm::FoldingSet<ProgramState> StateSet; |

524 | |

525 | /// Object that manages the data for all created SVals. |

526 | std::unique_ptr<SValBuilder> svalBuilder; |

527 | |

528 | /// Manages memory for created CallEvents. |

529 | std::unique_ptr<CallEventManager> CallEventMgr; |

530 | |

531 | /// A BumpPtrAllocator to allocate states. |

532 | llvm::BumpPtrAllocator &Alloc; |

533 | |

534 | /// A vector of ProgramStates that we can reuse. |

535 | std::vector<ProgramState *> freeStates; |

536 | |

537 | public: |

538 | ProgramStateManager(ASTContext &Ctx, |

539 | StoreManagerCreator CreateStoreManager, |

540 | ConstraintManagerCreator CreateConstraintManager, |

541 | llvm::BumpPtrAllocator& alloc, |

542 | ExprEngine *expreng); |

543 | |

544 | ~ProgramStateManager(); |

545 | |

546 | ProgramStateRef getInitialState(const LocationContext *InitLoc); |

547 | |

548 | ASTContext &getContext() { return svalBuilder->getContext(); } |

549 | const ASTContext &getContext() const { return svalBuilder->getContext(); } |

550 | |

551 | BasicValueFactory &getBasicVals() { |

552 | return svalBuilder->getBasicValueFactory(); |

553 | } |

554 | |

555 | SValBuilder &getSValBuilder() { |

556 | return *svalBuilder; |

557 | } |

558 | |

559 | const SValBuilder &getSValBuilder() const { |

560 | return *svalBuilder; |

561 | } |

562 | |

563 | SymbolManager &getSymbolManager() { |

564 | return svalBuilder->getSymbolManager(); |

565 | } |

566 | const SymbolManager &getSymbolManager() const { |

567 | return svalBuilder->getSymbolManager(); |

568 | } |

569 | |

570 | llvm::BumpPtrAllocator& getAllocator() { return Alloc; } |

571 | |

572 | MemRegionManager& getRegionManager() { |

573 | return svalBuilder->getRegionManager(); |

574 | } |

575 | const MemRegionManager &getRegionManager() const { |

576 | return svalBuilder->getRegionManager(); |

577 | } |

578 | |

579 | CallEventManager &getCallEventManager() { return *CallEventMgr; } |

580 | |

581 | StoreManager &getStoreManager() { return *StoreMgr; } |

582 | ConstraintManager &getConstraintManager() { return *ConstraintMgr; } |

583 | ExprEngine &getOwningEngine() { return *Eng; } |

584 | |

585 | ProgramStateRef |

586 | removeDeadBindingsFromEnvironmentAndStore(ProgramStateRef St, |

587 | const StackFrameContext *LCtx, |

588 | SymbolReaper &SymReaper); |

589 | |

590 | public: |

591 | |

592 | SVal ArrayToPointer(Loc Array, QualType ElementTy) { |

593 | return StoreMgr->ArrayToPointer(Array, ElementTy); |

594 | } |

595 | |

596 | // Methods that manipulate the GDM. |

597 | ProgramStateRef addGDM(ProgramStateRef St, void *Key, void *Data); |

598 | ProgramStateRef removeGDM(ProgramStateRef state, void *Key); |

599 | |

600 | // Methods that query & manipulate the Store. |

601 | |

602 | void iterBindings(ProgramStateRef state, StoreManager::BindingsHandler& F) { |

603 | StoreMgr->iterBindings(store: state->getStore(), f&: F); |

604 | } |

605 | |

606 | ProgramStateRef getPersistentState(ProgramState &Impl); |

607 | ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, |

608 | ProgramStateRef GDMState); |

609 | |

610 | bool haveEqualConstraints(ProgramStateRef S1, ProgramStateRef S2) const { |

611 | return ConstraintMgr->haveEqualConstraints(S1, S2); |

612 | } |

613 | |

614 | bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) const { |

615 | return S1->Env == S2->Env; |

616 | } |

617 | |

618 | bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) const { |

619 | return S1->store == S2->store; |

620 | } |

621 | |

622 | //==---------------------------------------------------------------------==// |

623 | // Generic Data Map methods. |

624 | //==---------------------------------------------------------------------==// |

625 | // |

626 | // ProgramStateManager and ProgramState support a "generic data map" that allows |

627 | // different clients of ProgramState objects to embed arbitrary data within a |

628 | // ProgramState object. The generic data map is essentially an immutable map |

629 | // from a "tag" (that acts as the "key" for a client) and opaque values. |

630 | // Tags/keys and values are simply void* values. The typical way that clients |

631 | // generate unique tags are by taking the address of a static variable. |

632 | // Clients are responsible for ensuring that data values referred to by a |

633 | // the data pointer are immutable (and thus are essentially purely functional |

634 | // data). |

635 | // |

636 | // The templated methods below use the ProgramStateTrait<T> class |

637 | // to resolve keys into the GDM and to return data values to clients. |

638 | // |

639 | |

640 | // Trait based GDM dispatch. |

641 | template <typename T> |

642 | ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait<T>::data_type D) { |

643 | return addGDM(St: st, Key: ProgramStateTrait<T>::GDMIndex(), |

644 | Data: ProgramStateTrait<T>::MakeVoidPtr(D)); |

645 | } |

646 | |

647 | template<typename T> |

648 | ProgramStateRef set(ProgramStateRef st, |

649 | typename ProgramStateTrait<T>::key_type K, |

650 | typename ProgramStateTrait<T>::value_type V, |

651 | typename ProgramStateTrait<T>::context_type C) { |

652 | |

653 | return addGDM(St: st, Key: ProgramStateTrait<T>::GDMIndex(), |

654 | Data: ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Set(st->get<T>(), K, V, C))); |

655 | } |

656 | |

657 | template <typename T> |

658 | ProgramStateRef add(ProgramStateRef st, |

659 | typename ProgramStateTrait<T>::key_type K, |

660 | typename ProgramStateTrait<T>::context_type C) { |

661 | return addGDM(St: st, Key: ProgramStateTrait<T>::GDMIndex(), |

662 | Data: ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Add(st->get<T>(), K, C))); |

663 | } |

664 | |

665 | template <typename T> |

666 | ProgramStateRef remove(ProgramStateRef st, |

667 | typename ProgramStateTrait<T>::key_type K, |

668 | typename ProgramStateTrait<T>::context_type C) { |

669 | |

670 | return addGDM(St: st, Key: ProgramStateTrait<T>::GDMIndex(), |

671 | Data: ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Remove(st->get<T>(), K, C))); |

672 | } |

673 | |

674 | template <typename T> |

675 | ProgramStateRef remove(ProgramStateRef st) { |

676 | return removeGDM(state: st, Key: ProgramStateTrait<T>::GDMIndex()); |

677 | } |

678 | |

679 | void *FindGDMContext(void *index, |

680 | void *(*CreateContext)(llvm::BumpPtrAllocator&), |

681 | void (*DeleteContext)(void*)); |

682 | |

683 | template <typename T> |

684 | typename ProgramStateTrait<T>::context_type get_context() { |

685 | void *p = FindGDMContext(index: ProgramStateTrait<T>::GDMIndex(), |

686 | CreateContext: ProgramStateTrait<T>::CreateContext, |

687 | DeleteContext: ProgramStateTrait<T>::DeleteContext); |

688 | |

689 | return ProgramStateTrait<T>::MakeContext(p); |

690 | } |

691 | }; |

692 | |

693 | |

694 | //===----------------------------------------------------------------------===// |

695 | // Out-of-line method definitions for ProgramState. |

696 | //===----------------------------------------------------------------------===// |

697 | |

698 | inline ConstraintManager &ProgramState::getConstraintManager() const { |

699 | return stateMgr->getConstraintManager(); |

700 | } |

701 | |

702 | inline const VarRegion* ProgramState::getRegion(const VarDecl *D, |

703 | const LocationContext *LC) const |

704 | { |

705 | return getStateManager().getRegionManager().getVarRegion(VD: D, LC); |

706 | } |

707 | |

708 | inline ProgramStateRef ProgramState::assume(DefinedOrUnknownSVal Cond, |

709 | bool Assumption) const { |

710 | if (Cond.isUnknown()) |

711 | return this; |

712 | |

713 | return getStateManager().ConstraintMgr |

714 | ->assume(state: this, Cond: Cond.castAs<DefinedSVal>(), Assumption); |

715 | } |

716 | |

717 | inline std::pair<ProgramStateRef , ProgramStateRef > |

718 | ProgramState::assume(DefinedOrUnknownSVal Cond) const { |

719 | if (Cond.isUnknown()) |

720 | return std::make_pair(x: this, y: this); |

721 | |

722 | return getStateManager().ConstraintMgr |

723 | ->assumeDual(State: this, Cond: Cond.castAs<DefinedSVal>()); |

724 | } |

725 | |

726 | inline ProgramStateRef ProgramState::assumeInclusiveRange( |

727 | DefinedOrUnknownSVal Val, const llvm::APSInt &From, const llvm::APSInt &To, |

728 | bool Assumption) const { |

729 | if (Val.isUnknown()) |

730 | return this; |

731 | |

732 | assert(isa<NonLoc>(Val) && "Only NonLocs are supported!"); |

733 | |

734 | return getStateManager().ConstraintMgr->assumeInclusiveRange( |

735 | State: this, Value: Val.castAs<NonLoc>(), From, To, InBound: Assumption); |

736 | } |

737 | |

738 | inline std::pair<ProgramStateRef, ProgramStateRef> |

739 | ProgramState::assumeInclusiveRange(DefinedOrUnknownSVal Val, |

740 | const llvm::APSInt &From, |

741 | const llvm::APSInt &To) const { |

742 | if (Val.isUnknown()) |

743 | return std::make_pair(x: this, y: this); |

744 | |

745 | assert(isa<NonLoc>(Val) && "Only NonLocs are supported!"); |

746 | |

747 | return getStateManager().ConstraintMgr->assumeInclusiveRangeDual( |

748 | State: this, Value: Val.castAs<NonLoc>(), From, To); |

749 | } |

750 | |

751 | inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V, const LocationContext *LCtx) const { |

752 | if (std::optional<Loc> L = LV.getAs<Loc>()) |

753 | return bindLoc(location: *L, V, LCtx); |

754 | return this; |

755 | } |

756 | |

757 | inline Loc ProgramState::getLValue(const CXXBaseSpecifier &BaseSpec, |

758 | const SubRegion *Super) const { |

759 | const auto *Base = BaseSpec.getType()->getAsCXXRecordDecl(); |

760 | return loc::MemRegionVal( |

761 | getStateManager().getRegionManager().getCXXBaseObjectRegion( |

762 | BaseClass: Base, Super, IsVirtual: BaseSpec.isVirtual())); |

763 | } |

764 | |

765 | inline Loc ProgramState::getLValue(const CXXRecordDecl *BaseClass, |

766 | const SubRegion *Super, |

767 | bool IsVirtual) const { |

768 | return loc::MemRegionVal( |

769 | getStateManager().getRegionManager().getCXXBaseObjectRegion( |

770 | BaseClass, Super, IsVirtual)); |

771 | } |

772 | |

773 | inline Loc ProgramState::getLValue(const VarDecl *VD, |

774 | const LocationContext *LC) const { |

775 | return getStateManager().StoreMgr->getLValueVar(VD, LC); |

776 | } |

777 | |

778 | inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal, |

779 | const LocationContext *LC) const { |

780 | return getStateManager().StoreMgr->getLValueCompoundLiteral(CL: literal, LC); |

781 | } |

782 | |

783 | inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const { |

784 | return getStateManager().StoreMgr->getLValueIvar(decl: D, base: Base); |

785 | } |

786 | |

787 | inline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ |

788 | if (std::optional<NonLoc> N = Idx.getAs<NonLoc>()) |

789 | return getStateManager().StoreMgr->getLValueElement(elementType: ElementType, offset: *N, Base); |

790 | return UnknownVal(); |

791 | } |

792 | |

793 | inline SVal ProgramState::getSVal(const Stmt *Ex, |

794 | const LocationContext *LCtx) const{ |

795 | return Env.getSVal(E: EnvironmentEntry(Ex, LCtx), |

796 | svalBuilder&: *getStateManager().svalBuilder); |

797 | } |

798 | |

799 | inline SVal |

800 | ProgramState::getSValAsScalarOrLoc(const Stmt *S, |

801 | const LocationContext *LCtx) const { |

802 | if (const Expr *Ex = dyn_cast<Expr>(Val: S)) { |

803 | QualType T = Ex->getType(); |

804 | if (Ex->isGLValue() || Loc::isLocType(T) || |

805 | T->isIntegralOrEnumerationType()) |

806 | return getSVal(Ex: S, LCtx); |

807 | } |

808 | |

809 | return UnknownVal(); |

810 | } |

811 | |

812 | inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const { |

813 | return getStateManager().StoreMgr->getBinding(store: getStore(), loc: LV, T); |

814 | } |

815 | |

816 | inline SVal ProgramState::getSVal(const MemRegion* R, QualType T) const { |

817 | return getStateManager().StoreMgr->getBinding(store: getStore(), |

818 | loc: loc::MemRegionVal(R), |

819 | T); |

820 | } |

821 | |

822 | inline BasicValueFactory &ProgramState::getBasicVals() const { |

823 | return getStateManager().getBasicVals(); |

824 | } |

825 | |

826 | inline SymbolManager &ProgramState::getSymbolManager() const { |

827 | return getStateManager().getSymbolManager(); |

828 | } |

829 | |

830 | template<typename T> |

831 | ProgramStateRef ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { |

832 | return getStateManager().add<T>(this, K, get_context<T>()); |

833 | } |

834 | |

835 | template <typename T> |

836 | typename ProgramStateTrait<T>::context_type ProgramState::get_context() const { |

837 | return getStateManager().get_context<T>(); |

838 | } |

839 | |

840 | template<typename T> |

841 | ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { |

842 | return getStateManager().remove<T>(this, K, get_context<T>()); |

843 | } |

844 | |

845 | template<typename T> |

846 | ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K, |

847 | typename ProgramStateTrait<T>::context_type C) const { |

848 | return getStateManager().remove<T>(this, K, C); |

849 | } |

850 | |

851 | template <typename T> |

852 | ProgramStateRef ProgramState::remove() const { |

853 | return getStateManager().remove<T>(this); |

854 | } |

855 | |

856 | template<typename T> |

857 | ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { |

858 | return getStateManager().set<T>(this, D); |

859 | } |

860 | |

861 | template<typename T> |

862 | ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, |

863 | typename ProgramStateTrait<T>::value_type E) const { |

864 | return getStateManager().set<T>(this, K, E, get_context<T>()); |

865 | } |

866 | |

867 | template<typename T> |

868 | ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, |

869 | typename ProgramStateTrait<T>::value_type E, |

870 | typename ProgramStateTrait<T>::context_type C) const { |

871 | return getStateManager().set<T>(this, K, E, C); |

872 | } |

873 | |

874 | template <typename CB> |

875 | CB ProgramState::scanReachableSymbols(SVal val) const { |

876 | CB cb(this); |

877 | scanReachableSymbols(val, cb); |

878 | return cb; |

879 | } |

880 | |

881 | template <typename CB> |

882 | CB ProgramState::scanReachableSymbols( |

883 | llvm::iterator_range<region_iterator> Reachable) const { |

884 | CB cb(this); |

885 | scanReachableSymbols(Reachable, cb); |

886 | return cb; |

887 | } |

888 | |

889 | /// \class ScanReachableSymbols |

890 | /// A utility class that visits the reachable symbols using a custom |

891 | /// SymbolVisitor. Terminates recursive traversal when the visitor function |

892 | /// returns false. |

893 | class ScanReachableSymbols { |

894 | typedef llvm::DenseSet<const void*> VisitedItems; |

895 | |

896 | VisitedItems visited; |

897 | ProgramStateRef state; |

898 | SymbolVisitor &visitor; |

899 | public: |

900 | ScanReachableSymbols(ProgramStateRef st, SymbolVisitor &v) |

901 | : state(std::move(st)), visitor(v) {} |

902 | |

903 | bool scan(nonloc::LazyCompoundVal val); |

904 | bool scan(nonloc::CompoundVal val); |

905 | bool scan(SVal val); |

906 | bool scan(const MemRegion *R); |

907 | bool scan(const SymExpr *sym); |

908 | }; |

909 | |

910 | } // end ento namespace |

911 | |

912 | } // end clang namespace |

913 | |

914 | #endif |

915 |