1 | //== ProgramState.h - Path-sensitive "State" for tracking values -*- C++ -*--=// |
---|---|

2 | // |

3 | // The LLVM Compiler Infrastructure |

4 | // |

5 | // This file is distributed under the University of Illinois Open Source |

6 | // License. See LICENSE.TXT for details. |

7 | // |

8 | //===----------------------------------------------------------------------===// |

9 | // |

10 | // This file defines the state of the program along the analysisa path. |

11 | // |

12 | //===----------------------------------------------------------------------===// |

13 | |

14 | #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H |

15 | #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H |

16 | |

17 | #include "clang/Basic/LLVM.h" |

18 | #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" |

19 | #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h" |

20 | #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" |

21 | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" |

22 | #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" |

23 | #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" |

24 | #include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h" |

25 | #include "llvm/ADT/FoldingSet.h" |

26 | #include "llvm/ADT/ImmutableMap.h" |

27 | #include "llvm/Support/Allocator.h" |

28 | #include <utility> |

29 | |

30 | namespace llvm { |

31 | class APSInt; |

32 | } |

33 | |

34 | namespace clang { |

35 | class ASTContext; |

36 | |

37 | namespace ento { |

38 | |

39 | class AnalysisManager; |

40 | class CallEvent; |

41 | class CallEventManager; |

42 | |

43 | typedef std::unique_ptr<ConstraintManager>(*ConstraintManagerCreator)( |

44 | ProgramStateManager &, SubEngine *); |

45 | typedef std::unique_ptr<StoreManager>(*StoreManagerCreator)( |

46 | ProgramStateManager &); |

47 | typedef llvm::ImmutableMap<const SubRegion*, TaintTagType> TaintedSubRegions; |

48 | |

49 | //===----------------------------------------------------------------------===// |

50 | // ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState. |

51 | //===----------------------------------------------------------------------===// |

52 | |

53 | template <typename T> struct ProgramStatePartialTrait; |

54 | |

55 | template <typename T> struct ProgramStateTrait { |

56 | typedef typename T::data_type data_type; |

57 | static inline void *MakeVoidPtr(data_type D) { return (void*) D; } |

58 | static inline data_type MakeData(void *const* P) { |

59 | return P ? (data_type) *P : (data_type) 0; |

60 | } |

61 | }; |

62 | |

63 | /// \class ProgramState |

64 | /// ProgramState - This class encapsulates: |

65 | /// |

66 | /// 1. A mapping from expressions to values (Environment) |

67 | /// 2. A mapping from locations to values (Store) |

68 | /// 3. Constraints on symbolic values (GenericDataMap) |

69 | /// |

70 | /// Together these represent the "abstract state" of a program. |

71 | /// |

72 | /// ProgramState is intended to be used as a functional object; that is, |

73 | /// once it is created and made "persistent" in a FoldingSet, its |

74 | /// values will never change. |

75 | class ProgramState : public llvm::FoldingSetNode { |

76 | public: |

77 | typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; |

78 | typedef llvm::ImmutableMap<void*, void*> GenericDataMap; |

79 | |

80 | private: |

81 | void operator=(const ProgramState& R) = delete; |

82 | |

83 | friend class ProgramStateManager; |

84 | friend class ExplodedGraph; |

85 | friend class ExplodedNode; |

86 | |

87 | ProgramStateManager *stateMgr; |

88 | Environment Env; // Maps a Stmt to its current SVal. |

89 | Store store; // Maps a location to its current value. |

90 | GenericDataMap GDM; // Custom data stored by a client of this class. |

91 | unsigned refCount; |

92 | |

93 | /// makeWithStore - Return a ProgramState with the same values as the current |

94 | /// state with the exception of using the specified Store. |

95 | ProgramStateRef makeWithStore(const StoreRef &store) const; |

96 | |

97 | void setStore(const StoreRef &storeRef); |

98 | |

99 | public: |

100 | /// This ctor is used when creating the first ProgramState object. |

101 | ProgramState(ProgramStateManager *mgr, const Environment& env, |

102 | StoreRef st, GenericDataMap gdm); |

103 | |

104 | /// Copy ctor - We must explicitly define this or else the "Next" ptr |

105 | /// in FoldingSetNode will also get copied. |

106 | ProgramState(const ProgramState &RHS); |

107 | |

108 | ~ProgramState(); |

109 | |

110 | int64_t getID() const; |

111 | |

112 | /// Return the ProgramStateManager associated with this state. |

113 | ProgramStateManager &getStateManager() const { |

114 | return *stateMgr; |

115 | } |

116 | |

117 | AnalysisManager &getAnalysisManager() const; |

118 | |

119 | /// Return the ConstraintManager. |

120 | ConstraintManager &getConstraintManager() const; |

121 | |

122 | /// getEnvironment - Return the environment associated with this state. |

123 | /// The environment is the mapping from expressions to values. |

124 | const Environment& getEnvironment() const { return Env; } |

125 | |

126 | /// Return the store associated with this state. The store |

127 | /// is a mapping from locations to values. |

128 | Store getStore() const { return store; } |

129 | |

130 | |

131 | /// getGDM - Return the generic data map associated with this state. |

132 | GenericDataMap getGDM() const { return GDM; } |

133 | |

134 | void setGDM(GenericDataMap gdm) { GDM = gdm; } |

135 | |

136 | /// Profile - Profile the contents of a ProgramState object for use in a |

137 | /// FoldingSet. Two ProgramState objects are considered equal if they |

138 | /// have the same Environment, Store, and GenericDataMap. |

139 | static void Profile(llvm::FoldingSetNodeID& ID, const ProgramState *V) { |

140 | V->Env.Profile(ID); |

141 | ID.AddPointer(V->store); |

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

143 | } |

144 | |

145 | /// Profile - Used to profile the contents of this object for inclusion |

146 | /// in a FoldingSet. |

147 | void Profile(llvm::FoldingSetNodeID& ID) const { |

148 | Profile(ID, this); |

149 | } |

150 | |

151 | BasicValueFactory &getBasicVals() const; |

152 | SymbolManager &getSymbolManager() const; |

153 | |

154 | //==---------------------------------------------------------------------==// |

155 | // Constraints on values. |

156 | //==---------------------------------------------------------------------==// |

157 | // |

158 | // Each ProgramState records constraints on symbolic values. These constraints |

159 | // are managed using the ConstraintManager associated with a ProgramStateManager. |

160 | // As constraints gradually accrue on symbolic values, added constraints |

161 | // may conflict and indicate that a state is infeasible (as no real values |

162 | // could satisfy all the constraints). This is the principal mechanism |

163 | // for modeling path-sensitivity in ExprEngine/ProgramState. |

164 | // |

165 | // Various "assume" methods form the interface for adding constraints to |

166 | // symbolic values. A call to 'assume' indicates an assumption being placed |

167 | // on one or symbolic values. 'assume' methods take the following inputs: |

168 | // |

169 | // (1) A ProgramState object representing the current state. |

170 | // |

171 | // (2) The assumed constraint (which is specific to a given "assume" method). |

172 | // |

173 | // (3) A binary value "Assumption" that indicates whether the constraint is |

174 | // assumed to be true or false. |

175 | // |

176 | // The output of "assume*" is a new ProgramState object with the added constraints. |

177 | // If no new state is feasible, NULL is returned. |

178 | // |

179 | |

180 | /// Assumes that the value of \p cond is zero (if \p assumption is "false") |

181 | /// or non-zero (if \p assumption is "true"). |

182 | /// |

183 | /// This returns a new state with the added constraint on \p cond. |

184 | /// If no new state is feasible, NULL is returned. |

185 | LLVM_NODISCARD ProgramStateRef assume(DefinedOrUnknownSVal cond, |

186 | bool assumption) const; |

187 | |

188 | /// Assumes both "true" and "false" for \p cond, and returns both |

189 | /// corresponding states (respectively). |

190 | /// |

191 | /// This is more efficient than calling assume() twice. Note that one (but not |

192 | /// both) of the returned states may be NULL. |

193 | LLVM_NODISCARD std::pair<ProgramStateRef, ProgramStateRef> |

194 | assume(DefinedOrUnknownSVal cond) const; |

195 | |

196 | LLVM_NODISCARD ProgramStateRef |

197 | assumeInBound(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, |

198 | bool assumption, QualType IndexType = QualType()) const; |

199 | |

200 | /// Assumes that the value of \p Val is bounded with [\p From; \p To] |

201 | /// (if \p assumption is "true") or it is fully out of this range |

202 | /// (if \p assumption is "false"). |

203 | /// |

204 | /// This returns a new state with the added constraint on \p cond. |

205 | /// If no new state is feasible, NULL is returned. |

206 | LLVM_NODISCARD ProgramStateRef assumeInclusiveRange(DefinedOrUnknownSVal Val, |

207 | const llvm::APSInt &From, |

208 | const llvm::APSInt &To, |

209 | bool assumption) const; |

210 | |

211 | /// Assumes given range both "true" and "false" for \p Val, and returns both |

212 | /// corresponding states (respectively). |

213 | /// |

214 | /// This is more efficient than calling assume() twice. Note that one (but not |

215 | /// both) of the returned states may be NULL. |

216 | LLVM_NODISCARD std::pair<ProgramStateRef, ProgramStateRef> |

217 | assumeInclusiveRange(DefinedOrUnknownSVal Val, const llvm::APSInt &From, |

218 | const llvm::APSInt &To) const; |

219 | |

220 | /// Check if the given SVal is not constrained to zero and is not |

221 | /// a zero constant. |

222 | ConditionTruthVal isNonNull(SVal V) const; |

223 | |

224 | /// Check if the given SVal is constrained to zero or is a zero |

225 | /// constant. |

226 | ConditionTruthVal isNull(SVal V) const; |

227 | |

228 | /// \return Whether values \p Lhs and \p Rhs are equal. |

229 | ConditionTruthVal areEqual(SVal Lhs, SVal Rhs) const; |

230 | |

231 | /// Utility method for getting regions. |

232 | const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; |

233 | |

234 | //==---------------------------------------------------------------------==// |

235 | // Binding and retrieving values to/from the environment and symbolic store. |

236 | //==---------------------------------------------------------------------==// |

237 | |

238 | /// Create a new state by binding the value 'V' to the statement 'S' in the |

239 | /// state's environment. |

240 | LLVM_NODISCARD ProgramStateRef BindExpr(const Stmt *S, |

241 | const LocationContext *LCtx, SVal V, |

242 | bool Invalidate = true) const; |

243 | |

244 | LLVM_NODISCARD ProgramStateRef bindLoc(Loc location, SVal V, |

245 | const LocationContext *LCtx, |

246 | bool notifyChanges = true) const; |

247 | |

248 | LLVM_NODISCARD ProgramStateRef bindLoc(SVal location, SVal V, |

249 | const LocationContext *LCtx) const; |

250 | |

251 | /// Initializes the region of memory represented by \p loc with an initial |

252 | /// value. Once initialized, all values loaded from any sub-regions of that |

253 | /// region will be equal to \p V, unless overwritten later by the program. |

254 | /// This method should not be used on regions that are already initialized. |

255 | /// If you need to indicate that memory contents have suddenly become unknown |

256 | /// within a certain region of memory, consider invalidateRegions(). |

257 | LLVM_NODISCARD ProgramStateRef |

258 | bindDefaultInitial(SVal loc, SVal V, const LocationContext *LCtx) const; |

259 | |

260 | /// Performs C++ zero-initialization procedure on the region of memory |

261 | /// represented by \p loc. |

262 | LLVM_NODISCARD ProgramStateRef |

263 | bindDefaultZero(SVal loc, const LocationContext *LCtx) const; |

264 | |

265 | LLVM_NODISCARD ProgramStateRef killBinding(Loc LV) const; |

266 | |

267 | /// Returns the state with bindings for the given regions |

268 | /// cleared from the store. |

269 | /// |

270 | /// Optionally invalidates global regions as well. |

271 | /// |

272 | /// \param Regions the set of regions to be invalidated. |

273 | /// \param E the expression that caused the invalidation. |

274 | /// \param BlockCount The number of times the current basic block has been |

275 | // visited. |

276 | /// \param CausesPointerEscape the flag is set to true when |

277 | /// the invalidation entails escape of a symbol (representing a |

278 | /// pointer). For example, due to it being passed as an argument in a |

279 | /// call. |

280 | /// \param IS the set of invalidated symbols. |

281 | /// \param Call if non-null, the invalidated regions represent parameters to |

282 | /// the call and should be considered directly invalidated. |

283 | /// \param ITraits information about special handling for a particular |

284 | /// region/symbol. |

285 | LLVM_NODISCARD ProgramStateRef |

286 | invalidateRegions(ArrayRef<const MemRegion *> Regions, const Expr *E, |

287 | unsigned BlockCount, const LocationContext *LCtx, |

288 | bool CausesPointerEscape, InvalidatedSymbols *IS = nullptr, |

289 | const CallEvent *Call = nullptr, |

290 | RegionAndSymbolInvalidationTraits *ITraits = nullptr) const; |

291 | |

292 | LLVM_NODISCARD ProgramStateRef |

293 | invalidateRegions(ArrayRef<SVal> Regions, const Expr *E, |

294 | unsigned BlockCount, const LocationContext *LCtx, |

295 | bool CausesPointerEscape, InvalidatedSymbols *IS = nullptr, |

296 | const CallEvent *Call = nullptr, |

297 | RegionAndSymbolInvalidationTraits *ITraits = nullptr) const; |

298 | |

299 | /// enterStackFrame - Returns the state for entry to the given stack frame, |

300 | /// preserving the current state. |

301 | LLVM_NODISCARD ProgramStateRef enterStackFrame( |

302 | const CallEvent &Call, const StackFrameContext *CalleeCtx) const; |

303 | |

304 | /// Get the lvalue for a base class object reference. |

305 | Loc getLValue(const CXXBaseSpecifier &BaseSpec, const SubRegion *Super) const; |

306 | |

307 | /// Get the lvalue for a base class object reference. |

308 | Loc getLValue(const CXXRecordDecl *BaseClass, const SubRegion *Super, |

309 | bool IsVirtual) const; |

310 | |

311 | /// Get the lvalue for a variable reference. |

312 | Loc getLValue(const VarDecl *D, const LocationContext *LC) const; |

313 | |

314 | Loc getLValue(const CompoundLiteralExpr *literal, |

315 | const LocationContext *LC) const; |

316 | |

317 | /// Get the lvalue for an ivar reference. |

318 | SVal getLValue(const ObjCIvarDecl *decl, SVal base) const; |

319 | |

320 | /// Get the lvalue for a field reference. |

321 | SVal getLValue(const FieldDecl *decl, SVal Base) const; |

322 | |

323 | /// Get the lvalue for an indirect field reference. |

324 | SVal getLValue(const IndirectFieldDecl *decl, SVal Base) const; |

325 | |

326 | /// Get the lvalue for an array index. |

327 | SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; |

328 | |

329 | /// Returns the SVal bound to the statement 'S' in the state's environment. |

330 | SVal getSVal(const Stmt *S, const LocationContext *LCtx) const; |

331 | |

332 | SVal getSValAsScalarOrLoc(const Stmt *Ex, const LocationContext *LCtx) const; |

333 | |

334 | /// Return the value bound to the specified location. |

335 | /// Returns UnknownVal() if none found. |

336 | SVal getSVal(Loc LV, QualType T = QualType()) const; |

337 | |

338 | /// Returns the "raw" SVal bound to LV before any value simplfication. |

339 | SVal getRawSVal(Loc LV, QualType T= QualType()) const; |

340 | |

341 | /// Return the value bound to the specified location. |

342 | /// Returns UnknownVal() if none found. |

343 | SVal getSVal(const MemRegion* R, QualType T = QualType()) const; |

344 | |

345 | /// Return the value bound to the specified location, assuming |

346 | /// that the value is a scalar integer or an enumeration or a pointer. |

347 | /// Returns UnknownVal() if none found or the region is not known to hold |

348 | /// a value of such type. |

349 | SVal getSValAsScalarOrLoc(const MemRegion *R) const; |

350 | |

351 | using region_iterator = const MemRegion **; |

352 | |

353 | /// Visits the symbols reachable from the given SVal using the provided |

354 | /// SymbolVisitor. |

355 | /// |

356 | /// This is a convenience API. Consider using ScanReachableSymbols class |

357 | /// directly when making multiple scans on the same state with the same |

358 | /// visitor to avoid repeated initialization cost. |

359 | /// \sa ScanReachableSymbols |

360 | bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; |

361 | |

362 | /// Visits the symbols reachable from the regions in the given |

363 | /// MemRegions range using the provided SymbolVisitor. |

364 | bool scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable, |

365 | SymbolVisitor &visitor) const; |

366 | |

367 | template <typename CB> CB scanReachableSymbols(SVal val) const; |

368 | template <typename CB> CB |

369 | scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable) const; |

370 | |

371 | /// Create a new state in which the statement is marked as tainted. |

372 | LLVM_NODISCARD ProgramStateRef |

373 | addTaint(const Stmt *S, const LocationContext *LCtx, |

374 | TaintTagType Kind = TaintTagGeneric) const; |

375 | |

376 | /// Create a new state in which the value is marked as tainted. |

377 | LLVM_NODISCARD ProgramStateRef |

378 | addTaint(SVal V, TaintTagType Kind = TaintTagGeneric) const; |

379 | |

380 | /// Create a new state in which the symbol is marked as tainted. |

381 | LLVM_NODISCARD ProgramStateRef addTaint(SymbolRef S, |

382 | TaintTagType Kind = TaintTagGeneric) const; |

383 | |

384 | /// Create a new state in which the region symbol is marked as tainted. |

385 | LLVM_NODISCARD ProgramStateRef |

386 | addTaint(const MemRegion *R, TaintTagType Kind = TaintTagGeneric) const; |

387 | |

388 | /// Create a new state in a which a sub-region of a given symbol is tainted. |

389 | /// This might be necessary when referring to regions that can not have an |

390 | /// individual symbol, e.g. if they are represented by the default binding of |

391 | /// a LazyCompoundVal. |

392 | LLVM_NODISCARD ProgramStateRef |

393 | addPartialTaint(SymbolRef ParentSym, const SubRegion *SubRegion, |

394 | TaintTagType Kind = TaintTagGeneric) const; |

395 | |

396 | /// Check if the statement is tainted in the current state. |

397 | bool isTainted(const Stmt *S, const LocationContext *LCtx, |

398 | TaintTagType Kind = TaintTagGeneric) const; |

399 | bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const; |

400 | bool isTainted(SymbolRef Sym, TaintTagType Kind = TaintTagGeneric) const; |

401 | bool isTainted(const MemRegion *Reg, TaintTagType Kind=TaintTagGeneric) const; |

402 | |

403 | //==---------------------------------------------------------------------==// |

404 | // Accessing the Generic Data Map (GDM). |

405 | //==---------------------------------------------------------------------==// |

406 | |

407 | void *const* FindGDM(void *K) const; |

408 | |

409 | template <typename T> |

410 | LLVM_NODISCARD ProgramStateRef |

411 | add(typename ProgramStateTrait<T>::key_type K) const; |

412 | |

413 | template <typename T> |

414 | typename ProgramStateTrait<T>::data_type |

415 | get() const { |

416 | return ProgramStateTrait<T>::MakeData(FindGDM(ProgramStateTrait<T>::GDMIndex())); |

417 | } |

418 | |

419 | template<typename T> |

420 | typename ProgramStateTrait<T>::lookup_type |

421 | get(typename ProgramStateTrait<T>::key_type key) const { |

422 | void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); |

423 | return ProgramStateTrait<T>::Lookup(ProgramStateTrait<T>::MakeData(d), key); |

424 | } |

425 | |

426 | template <typename T> |

427 | typename ProgramStateTrait<T>::context_type get_context() const; |

428 | |

429 | template <typename T> |

430 | LLVM_NODISCARD ProgramStateRef |

431 | remove(typename ProgramStateTrait<T>::key_type K) const; |

432 | |

433 | template <typename T> |

434 | LLVM_NODISCARD ProgramStateRef |

435 | remove(typename ProgramStateTrait<T>::key_type K, |

436 | typename ProgramStateTrait<T>::context_type C) const; |

437 | |

438 | template <typename T> LLVM_NODISCARD ProgramStateRef remove() const; |

439 | |

440 | template <typename T> |

441 | LLVM_NODISCARD ProgramStateRef |

442 | set(typename ProgramStateTrait<T>::data_type D) const; |

443 | |

444 | template <typename T> |

445 | LLVM_NODISCARD ProgramStateRef |

446 | set(typename ProgramStateTrait<T>::key_type K, |

447 | typename ProgramStateTrait<T>::value_type E) const; |

448 | |

449 | template <typename T> |

450 | LLVM_NODISCARD ProgramStateRef |

451 | set(typename ProgramStateTrait<T>::key_type K, |

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

453 | typename ProgramStateTrait<T>::context_type C) const; |

454 | |

455 | template<typename T> |

456 | bool contains(typename ProgramStateTrait<T>::key_type key) const { |

457 | void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); |

458 | return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key); |

459 | } |

460 | |

461 | // Pretty-printing. |

462 | void print(raw_ostream &Out, const char *nl = "\n", const char *sep = "", |

463 | const LocationContext *CurrentLC = nullptr) const; |

464 | void printDOT(raw_ostream &Out, |

465 | const LocationContext *CurrentLC = nullptr) const; |

466 | void printTaint(raw_ostream &Out, const char *nl = "\n") const; |

467 | |

468 | void dump() const; |

469 | void dumpTaint() const; |

470 | |

471 | private: |

472 | friend void ProgramStateRetain(const ProgramState *state); |

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

474 | |

475 | /// \sa invalidateValues() |

476 | /// \sa invalidateRegions() |

477 | ProgramStateRef |

478 | invalidateRegionsImpl(ArrayRef<SVal> Values, |

479 | const Expr *E, unsigned BlockCount, |

480 | const LocationContext *LCtx, |

481 | bool ResultsInSymbolEscape, |

482 | InvalidatedSymbols *IS, |

483 | RegionAndSymbolInvalidationTraits *HTraits, |

484 | const CallEvent *Call) const; |

485 | }; |

486 | |

487 | //===----------------------------------------------------------------------===// |

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

489 | //===----------------------------------------------------------------------===// |

490 | |

491 | class ProgramStateManager { |

492 | friend class ProgramState; |

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

494 | private: |

495 | /// Eng - The SubEngine that owns this state manager. |

496 | SubEngine *Eng; /* Can be null. */ |

497 | |

498 | EnvironmentManager EnvMgr; |

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

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

501 | |

502 | ProgramState::GenericDataMap::Factory GDMFactory; |

503 | TaintedSubRegions::Factory TSRFactory; |

504 | |

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

506 | GDMContextsTy GDMContexts; |

507 | |

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

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

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

511 | |

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

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

514 | |

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

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

517 | |

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

519 | llvm::BumpPtrAllocator &Alloc; |

520 | |

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

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

523 | |

524 | public: |

525 | ProgramStateManager(ASTContext &Ctx, |

526 | StoreManagerCreator CreateStoreManager, |

527 | ConstraintManagerCreator CreateConstraintManager, |

528 | llvm::BumpPtrAllocator& alloc, |

529 | SubEngine *subeng); |

530 | |

531 | ~ProgramStateManager(); |

532 | |

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

534 | |

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

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

537 | |

538 | BasicValueFactory &getBasicVals() { |

539 | return svalBuilder->getBasicValueFactory(); |

540 | } |

541 | |

542 | SValBuilder &getSValBuilder() { |

543 | return *svalBuilder; |

544 | } |

545 | |

546 | SymbolManager &getSymbolManager() { |

547 | return svalBuilder->getSymbolManager(); |

548 | } |

549 | const SymbolManager &getSymbolManager() const { |

550 | return svalBuilder->getSymbolManager(); |

551 | } |

552 | |

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

554 | |

555 | MemRegionManager& getRegionManager() { |

556 | return svalBuilder->getRegionManager(); |

557 | } |

558 | const MemRegionManager& getRegionManager() const { |

559 | return svalBuilder->getRegionManager(); |

560 | } |

561 | |

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

563 | |

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

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

566 | SubEngine* getOwningEngine() { return Eng; } |

567 | |

568 | ProgramStateRef removeDeadBindings(ProgramStateRef St, |

569 | const StackFrameContext *LCtx, |

570 | SymbolReaper& SymReaper); |

571 | |

572 | public: |

573 | |

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

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

576 | } |

577 | |

578 | // Methods that manipulate the GDM. |

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

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

581 | |

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

583 | |

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

585 | StoreMgr->iterBindings(state->getStore(), F); |

586 | } |

587 | |

588 | ProgramStateRef getPersistentState(ProgramState &Impl); |

589 | ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, |

590 | ProgramStateRef GDMState); |

591 | |

592 | bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) { |

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

594 | } |

595 | |

596 | bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) { |

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

598 | } |

599 | |

600 | //==---------------------------------------------------------------------==// |

601 | // Generic Data Map methods. |

602 | //==---------------------------------------------------------------------==// |

603 | // |

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

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

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

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

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

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

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

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

612 | // data). |

613 | // |

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

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

616 | // |

617 | |

618 | // Trait based GDM dispatch. |

619 | template <typename T> |

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

621 | return addGDM(st, ProgramStateTrait<T>::GDMIndex(), |

622 | ProgramStateTrait<T>::MakeVoidPtr(D)); |

623 | } |

624 | |

625 | template<typename T> |

626 | ProgramStateRef set(ProgramStateRef st, |

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

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

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

630 | |

631 | return addGDM(st, ProgramStateTrait<T>::GDMIndex(), |

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

633 | } |

634 | |

635 | template <typename T> |

636 | ProgramStateRef add(ProgramStateRef st, |

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

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

639 | return addGDM(st, ProgramStateTrait<T>::GDMIndex(), |

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

641 | } |

642 | |

643 | template <typename T> |

644 | ProgramStateRef remove(ProgramStateRef st, |

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

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

647 | |

648 | return addGDM(st, ProgramStateTrait<T>::GDMIndex(), |

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

650 | } |

651 | |

652 | template <typename T> |

653 | ProgramStateRef remove(ProgramStateRef st) { |

654 | return removeGDM(st, ProgramStateTrait<T>::GDMIndex()); |

655 | } |

656 | |

657 | void *FindGDMContext(void *index, |

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

659 | void (*DeleteContext)(void*)); |

660 | |

661 | template <typename T> |

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

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

664 | ProgramStateTrait<T>::CreateContext, |

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

666 | |

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

668 | } |

669 | |

670 | void EndPath(ProgramStateRef St) { |

671 | ConstraintMgr->EndPath(St); |

672 | } |

673 | }; |

674 | |

675 | |

676 | //===----------------------------------------------------------------------===// |

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

678 | //===----------------------------------------------------------------------===// |

679 | |

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

681 | return stateMgr->getConstraintManager(); |

682 | } |

683 | |

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

685 | const LocationContext *LC) const |

686 | { |

687 | return getStateManager().getRegionManager().getVarRegion(D, LC); |

688 | } |

689 | |

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

691 | bool Assumption) const { |

692 | if (Cond.isUnknown()) |

693 | return this; |

694 | |

695 | return getStateManager().ConstraintMgr |

696 | ->assume(this, Cond.castAs<DefinedSVal>(), Assumption); |

697 | } |

698 | |

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

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

701 | if (Cond.isUnknown()) |

702 | return std::make_pair(this, this); |

703 | |

704 | return getStateManager().ConstraintMgr |

705 | ->assumeDual(this, Cond.castAs<DefinedSVal>()); |

706 | } |

707 | |

708 | inline ProgramStateRef ProgramState::assumeInclusiveRange( |

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

710 | bool Assumption) const { |

711 | if (Val.isUnknown()) |

712 | return this; |

713 | |

714 | assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!"); |

715 | |

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

717 | this, Val.castAs<NonLoc>(), From, To, Assumption); |

718 | } |

719 | |

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

721 | ProgramState::assumeInclusiveRange(DefinedOrUnknownSVal Val, |

722 | const llvm::APSInt &From, |

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

724 | if (Val.isUnknown()) |

725 | return std::make_pair(this, this); |

726 | |

727 | assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!"); |

728 | |

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

730 | this, Val.castAs<NonLoc>(), From, To); |

731 | } |

732 | |

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

734 | if (Optional<Loc> L = LV.getAs<Loc>()) |

735 | return bindLoc(*L, V, LCtx); |

736 | return this; |

737 | } |

738 | |

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

740 | const SubRegion *Super) const { |

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

742 | return loc::MemRegionVal( |

743 | getStateManager().getRegionManager().getCXXBaseObjectRegion( |

744 | Base, Super, BaseSpec.isVirtual())); |

745 | } |

746 | |

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

748 | const SubRegion *Super, |

749 | bool IsVirtual) const { |

750 | return loc::MemRegionVal( |

751 | getStateManager().getRegionManager().getCXXBaseObjectRegion( |

752 | BaseClass, Super, IsVirtual)); |

753 | } |

754 | |

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

756 | const LocationContext *LC) const { |

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

758 | } |

759 | |

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

761 | const LocationContext *LC) const { |

762 | return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); |

763 | } |

764 | |

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

766 | return getStateManager().StoreMgr->getLValueIvar(D, Base); |

767 | } |

768 | |

769 | inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const { |

770 | return getStateManager().StoreMgr->getLValueField(D, Base); |

771 | } |

772 | |

773 | inline SVal ProgramState::getLValue(const IndirectFieldDecl *D, |

774 | SVal Base) const { |

775 | StoreManager &SM = *getStateManager().StoreMgr; |

776 | for (const auto *I : D->chain()) { |

777 | Base = SM.getLValueField(cast<FieldDecl>(I), Base); |

778 | } |

779 | |

780 | return Base; |

781 | } |

782 | |

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

784 | if (Optional<NonLoc> N = Idx.getAs<NonLoc>()) |

785 | return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base); |

786 | return UnknownVal(); |

787 | } |

788 | |

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

790 | const LocationContext *LCtx) const{ |

791 | return Env.getSVal(EnvironmentEntry(Ex, LCtx), |

792 | *getStateManager().svalBuilder); |

793 | } |

794 | |

795 | inline SVal |

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

797 | const LocationContext *LCtx) const { |

798 | if (const Expr *Ex = dyn_cast<Expr>(S)) { |

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

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

801 | T->isIntegralOrEnumerationType()) |

802 | return getSVal(S, LCtx); |

803 | } |

804 | |

805 | return UnknownVal(); |

806 | } |

807 | |

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

809 | return getStateManager().StoreMgr->getBinding(getStore(), LV, T); |

810 | } |

811 | |

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

813 | return getStateManager().StoreMgr->getBinding(getStore(), |

814 | loc::MemRegionVal(R), |

815 | T); |

816 | } |

817 | |

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

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

820 | } |

821 | |

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

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

824 | } |

825 | |

826 | template<typename T> |

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

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

829 | } |

830 | |

831 | template <typename T> |

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

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

834 | } |

835 | |

836 | template<typename T> |

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

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

839 | } |

840 | |

841 | template<typename T> |

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

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

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

845 | } |

846 | |

847 | template <typename T> |

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

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

850 | } |

851 | |

852 | template<typename T> |

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

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

855 | } |

856 | |

857 | template<typename T> |

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

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

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

861 | } |

862 | |

863 | template<typename T> |

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

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

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

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

868 | } |

869 | |

870 | template <typename CB> |

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

872 | CB cb(this); |

873 | scanReachableSymbols(val, cb); |

874 | return cb; |

875 | } |

876 | |

877 | template <typename CB> |

878 | CB ProgramState::scanReachableSymbols( |

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

880 | CB cb(this); |

881 | scanReachableSymbols(Reachable, cb); |

882 | return cb; |

883 | } |

884 | |

885 | /// \class ScanReachableSymbols |

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

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

888 | /// returns false. |

889 | class ScanReachableSymbols { |

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

891 | |

892 | VisitedItems visited; |

893 | ProgramStateRef state; |

894 | SymbolVisitor &visitor; |

895 | public: |

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

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

898 | |

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

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

901 | bool scan(SVal val); |

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

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

904 | }; |

905 | |

906 | } // end ento namespace |

907 | |

908 | } // end clang namespace |

909 | |

910 | #endif |

911 |