1 | use alloc::{collections::BTreeMap, vec::Vec}; |
---|---|

2 | |

3 | use crate::{ |

4 | dfa::{ |

5 | dense::{self, BuildError}, |

6 | DEAD, |

7 | }, |

8 | nfa::thompson, |

9 | util::{ |

10 | self, |

11 | alphabet::{self, ByteSet}, |

12 | determinize::{State, StateBuilderEmpty, StateBuilderNFA}, |

13 | primitives::{PatternID, StateID}, |

14 | search::{Anchored, MatchKind}, |

15 | sparse_set::SparseSets, |

16 | start::Start, |

17 | }, |

18 | }; |

19 | |

20 | /// A builder for configuring and running a DFA determinizer. |

21 | #[derive(Clone, Debug)] |

22 | pub(crate) struct Config { |

23 | match_kind: MatchKind, |

24 | quit: ByteSet, |

25 | dfa_size_limit: Option<usize>, |

26 | determinize_size_limit: Option<usize>, |

27 | } |

28 | |

29 | impl Config { |

30 | /// Create a new default config for a determinizer. The determinizer may be |

31 | /// configured before calling `run`. |

32 | pub fn new() -> Config { |

33 | Config { |

34 | match_kind: MatchKind::LeftmostFirst, |

35 | quit: ByteSet::empty(), |

36 | dfa_size_limit: None, |

37 | determinize_size_limit: None, |

38 | } |

39 | } |

40 | |

41 | /// Run determinization on the given NFA and write the resulting DFA into |

42 | /// the one given. The DFA given should be initialized but otherwise empty. |

43 | /// "Initialized" means that it is setup to handle the NFA's byte classes, |

44 | /// number of patterns and whether to build start states for each pattern. |

45 | pub fn run( |

46 | &self, |

47 | nfa: &thompson::NFA, |

48 | dfa: &mut dense::OwnedDFA, |

49 | ) -> Result<(), BuildError> { |

50 | let dead = State::dead(); |

51 | let quit = State::dead(); |

52 | let mut cache = StateMap::default(); |

53 | // We only insert the dead state here since its representation is |

54 | // identical to the quit state. And we never want anything pointing |

55 | // to the quit state other than specific transitions derived from the |

56 | // determinizer's configured "quit" bytes. |

57 | // |

58 | // We do put the quit state into 'builder_states' below. This ensures |

59 | // that a proper DFA state ID is allocated for it, and that no other |

60 | // DFA state uses the "location after the DEAD state." That is, it |

61 | // is assumed that the quit state is always the state immediately |

62 | // following the DEAD state. |

63 | cache.insert(dead.clone(), DEAD); |

64 | |

65 | let runner = Runner { |

66 | config: self.clone(), |

67 | nfa, |

68 | dfa, |

69 | builder_states: alloc::vec![dead, quit], |

70 | cache, |

71 | memory_usage_state: 0, |

72 | sparses: SparseSets::new(nfa.states().len()), |

73 | stack: alloc::vec![], |

74 | scratch_state_builder: StateBuilderEmpty::new(), |

75 | }; |

76 | runner.run() |

77 | } |

78 | |

79 | /// The match semantics to use for determinization. |

80 | /// |

81 | /// MatchKind::All corresponds to the standard textbook construction. |

82 | /// All possible match states are represented in the DFA. |

83 | /// MatchKind::LeftmostFirst permits greediness and otherwise tries to |

84 | /// simulate the match semantics of backtracking regex engines. Namely, |

85 | /// only a subset of match states are built, and dead states are used to |

86 | /// stop searches with an unanchored prefix. |

87 | /// |

88 | /// The default is MatchKind::LeftmostFirst. |

89 | pub fn match_kind(&mut self, kind: MatchKind) -> &mut Config { |

90 | self.match_kind = kind; |

91 | self |

92 | } |

93 | |

94 | /// The set of bytes to use that will cause the DFA to enter a quit state, |

95 | /// stop searching and return an error. By default, this is empty. |

96 | pub fn quit(&mut self, set: ByteSet) -> &mut Config { |

97 | self.quit = set; |

98 | self |

99 | } |

100 | |

101 | /// The limit, in bytes of the heap, that the DFA is permitted to use. This |

102 | /// does not include the auxiliary heap storage used by determinization. |

103 | pub fn dfa_size_limit(&mut self, bytes: Option<usize>) -> &mut Config { |

104 | self.dfa_size_limit = bytes; |

105 | self |

106 | } |

107 | |

108 | /// The limit, in bytes of the heap, that determinization itself is allowed |

109 | /// to use. This does not include the size of the DFA being built. |

110 | pub fn determinize_size_limit( |

111 | &mut self, |

112 | bytes: Option<usize>, |

113 | ) -> &mut Config { |

114 | self.determinize_size_limit = bytes; |

115 | self |

116 | } |

117 | } |

118 | |

119 | /// The actual implementation of determinization that converts an NFA to a DFA |

120 | /// through powerset construction. |

121 | /// |

122 | /// This determinizer roughly follows the typical powerset construction, where |

123 | /// each DFA state is comprised of one or more NFA states. In the worst case, |

124 | /// there is one DFA state for every possible combination of NFA states. In |

125 | /// practice, this only happens in certain conditions, typically when there are |

126 | /// bounded repetitions. |

127 | /// |

128 | /// The main differences between this implementation and typical deteminization |

129 | /// are that this implementation delays matches by one state and hackily makes |

130 | /// look-around work. Comments below attempt to explain this. |

131 | /// |

132 | /// The lifetime variable `'a` refers to the lifetime of the NFA or DFA, |

133 | /// whichever is shorter. |

134 | #[derive(Debug)] |

135 | struct Runner<'a> { |

136 | /// The configuration used to initialize determinization. |

137 | config: Config, |

138 | /// The NFA we're converting into a DFA. |

139 | nfa: &'a thompson::NFA, |

140 | /// The DFA we're building. |

141 | dfa: &'a mut dense::OwnedDFA, |

142 | /// Each DFA state being built is defined as an *ordered* set of NFA |

143 | /// states, along with some meta facts about the ordered set of NFA states. |

144 | /// |

145 | /// This is never empty. The first state is always a dummy state such that |

146 | /// a state id == 0 corresponds to a dead state. The second state is always |

147 | /// the quit state. |

148 | /// |

149 | /// Why do we have states in both a `Vec` and in a cache map below? |

150 | /// Well, they serve two different roles based on access patterns. |

151 | /// `builder_states` is the canonical home of each state, and provides |

152 | /// constant random access by a DFA state's ID. The cache map below, on |

153 | /// the other hand, provides a quick way of searching for identical DFA |

154 | /// states by using the DFA state as a key in the map. Of course, we use |

155 | /// reference counting to avoid actually duplicating the state's data |

156 | /// itself. (Although this has never been benchmarked.) Note that the cache |

157 | /// map does not give us full minimization; it just lets us avoid some very |

158 | /// obvious redundant states. |

159 | /// |

160 | /// Note that the index into this Vec isn't quite the DFA's state ID. |

161 | /// Rather, it's just an index. To get the state ID, you have to multiply |

162 | /// it by the DFA's stride. That's done by self.dfa.from_index. And the |

163 | /// inverse is self.dfa.to_index. |

164 | /// |

165 | /// Moreover, DFA states don't usually retain the IDs assigned to them |

166 | /// by their position in this Vec. After determinization completes, |

167 | /// states are shuffled around to support other optimizations. See the |

168 | /// sibling 'special' module for more details on that. (The reason for |

169 | /// mentioning this is that if you print out the DFA for debugging during |

170 | /// determinization, and then print out the final DFA after it is fully |

171 | /// built, then the state IDs likely won't match up.) |

172 | builder_states: Vec<State>, |

173 | /// A cache of DFA states that already exist and can be easily looked up |

174 | /// via ordered sets of NFA states. |

175 | /// |

176 | /// See `builder_states` docs for why we store states in two different |

177 | /// ways. |

178 | cache: StateMap, |

179 | /// The memory usage, in bytes, used by builder_states and cache. We track |

180 | /// this as new states are added since states use a variable amount of |

181 | /// heap. Tracking this as we add states makes it possible to compute the |

182 | /// total amount of memory used by the determinizer in constant time. |

183 | memory_usage_state: usize, |

184 | /// A pair of sparse sets for tracking ordered sets of NFA state IDs. |

185 | /// These are reused throughout determinization. A bounded sparse set |

186 | /// gives us constant time insertion, membership testing and clearing. |

187 | sparses: SparseSets, |

188 | /// Scratch space for a stack of NFA states to visit, for depth first |

189 | /// visiting without recursion. |

190 | stack: Vec<StateID>, |

191 | /// Scratch space for storing an ordered sequence of NFA states, for |

192 | /// amortizing allocation. This is principally useful for when we avoid |

193 | /// adding a new DFA state since it already exists. In order to detect this |

194 | /// case though, we still need an ordered set of NFA state IDs. So we use |

195 | /// this space to stage that ordered set before we know whether we need to |

196 | /// create a new DFA state or not. |

197 | scratch_state_builder: StateBuilderEmpty, |

198 | } |

199 | |

200 | /// A map from states to state identifiers. When using std, we use a standard |

201 | /// hashmap, since it's a bit faster for this use case. (Other maps, like |

202 | /// one's based on FNV, have not yet been benchmarked.) |

203 | /// |

204 | /// The main purpose of this map is to reuse states where possible. This won't |

205 | /// fully minimize the DFA, but it works well in a lot of cases. |

206 | #[cfg(feature = "std")] |

207 | type StateMap = std::collections::HashMap<State, StateID>; |

208 | #[cfg(not(feature = "std"))] |

209 | type StateMap = BTreeMap<State, StateID>; |

210 | |

211 | impl<'a> Runner<'a> { |

212 | /// Build the DFA. If there was a problem constructing the DFA (e.g., if |

213 | /// the chosen state identifier representation is too small), then an error |

214 | /// is returned. |

215 | fn run(mut self) -> Result<(), BuildError> { |

216 | if self.nfa.look_set_any().contains_word_unicode() |

217 | && !self.config.quit.contains_range(0x80, 0xFF) |

218 | { |

219 | return Err(BuildError::unsupported_dfa_word_boundary_unicode()); |

220 | } |

221 | |

222 | // A sequence of "representative" bytes drawn from each equivalence |

223 | // class. These representative bytes are fed to the NFA to compute |

224 | // state transitions. This allows us to avoid re-computing state |

225 | // transitions for bytes that are guaranteed to produce identical |

226 | // results. Since computing the representatives needs to do a little |

227 | // work, we do it once here because we'll be iterating over them a lot. |

228 | let representatives: Vec<alphabet::Unit> = |

229 | self.dfa.byte_classes().representatives(..).collect(); |

230 | // The set of all DFA state IDs that still need to have their |

231 | // transitions set. We start by seeding this with all starting states. |

232 | let mut uncompiled = alloc::vec![]; |

233 | self.add_all_starts(&mut uncompiled)?; |

234 | while let Some(dfa_id) = uncompiled.pop() { |

235 | for &unit in &representatives { |

236 | if unit.as_u8().map_or(false, |b| self.config.quit.contains(b)) |

237 | { |

238 | continue; |

239 | } |

240 | // In many cases, the state we transition to has already been |

241 | // computed. 'cached_state' will do the minimal amount of work |

242 | // to check this, and if it exists, immediately return an |

243 | // already existing state ID. |

244 | let (next_dfa_id, is_new) = self.cached_state(dfa_id, unit)?; |

245 | self.dfa.set_transition(dfa_id, unit, next_dfa_id); |

246 | // If the state ID we got back is newly created, then we need |

247 | // to compile it, so add it to our uncompiled frontier. |

248 | if is_new { |

249 | uncompiled.push(next_dfa_id); |

250 | } |

251 | } |

252 | } |

253 | debug!( |

254 | "determinization complete, memory usage: {}, \ |

255 | dense DFA size: {}, \ |

256 | is reverse? {}", |

257 | self.memory_usage(), |

258 | self.dfa.memory_usage(), |

259 | self.nfa.is_reverse(), |

260 | ); |

261 | |

262 | // A map from DFA state ID to one or more NFA match IDs. Each NFA match |

263 | // ID corresponds to a distinct regex pattern that matches in the state |

264 | // corresponding to the key. |

265 | let mut matches: BTreeMap<StateID, Vec<PatternID>> = BTreeMap::new(); |

266 | self.cache.clear(); |

267 | #[cfg(feature = "logging")] |

268 | let mut total_pat_len = 0; |

269 | for (i, state) in self.builder_states.into_iter().enumerate() { |

270 | if let Some(pat_ids) = state.match_pattern_ids() { |

271 | let id = self.dfa.to_state_id(i); |

272 | log! { |

273 | total_pat_len += pat_ids.len(); |

274 | } |

275 | matches.insert(id, pat_ids); |

276 | } |

277 | } |

278 | log! { |

279 | use core::mem::size_of; |

280 | let per_elem = size_of::<StateID>() + size_of::<Vec<PatternID>>(); |

281 | let pats = total_pat_len * size_of::<PatternID>(); |

282 | let mem = (matches.len() * per_elem) + pats; |

283 | log::debug!("matches map built, memory usage: {}", mem); |

284 | } |

285 | // At this point, we shuffle the "special" states in the final DFA. |

286 | // This permits a DFA's match loop to detect a match condition (among |

287 | // other things) by merely inspecting the current state's identifier, |

288 | // and avoids the need for any additional auxiliary storage. |

289 | self.dfa.shuffle(matches)?; |

290 | Ok(()) |

291 | } |

292 | |

293 | /// Return the identifier for the next DFA state given an existing DFA |

294 | /// state and an input byte. If the next DFA state already exists, then |

295 | /// return its identifier from the cache. Otherwise, build the state, cache |

296 | /// it and return its identifier. |

297 | /// |

298 | /// This routine returns a boolean indicating whether a new state was |

299 | /// built. If a new state is built, then the caller needs to add it to its |

300 | /// frontier of uncompiled DFA states to compute transitions for. |

301 | fn cached_state( |

302 | &mut self, |

303 | dfa_id: StateID, |

304 | unit: alphabet::Unit, |

305 | ) -> Result<(StateID, bool), BuildError> { |

306 | // Compute the set of all reachable NFA states, including epsilons. |

307 | let empty_builder = self.get_state_builder(); |

308 | let builder = util::determinize::next( |

309 | self.nfa, |

310 | self.config.match_kind, |

311 | &mut self.sparses, |

312 | &mut self.stack, |

313 | &self.builder_states[self.dfa.to_index(dfa_id)], |

314 | unit, |

315 | empty_builder, |

316 | ); |

317 | self.maybe_add_state(builder) |

318 | } |

319 | |

320 | /// Compute the set of DFA start states and add their identifiers in |

321 | /// 'dfa_state_ids' (no duplicates are added). |

322 | fn add_all_starts( |

323 | &mut self, |

324 | dfa_state_ids: &mut Vec<StateID>, |

325 | ) -> Result<(), BuildError> { |

326 | // These should be the first states added. |

327 | assert!(dfa_state_ids.is_empty()); |

328 | // We only want to add (un)anchored starting states that is consistent |

329 | // with our DFA's configuration. Unconditionally adding both (although |

330 | // it is the default) can make DFAs quite a bit bigger. |

331 | if self.dfa.start_kind().has_unanchored() { |

332 | self.add_start_group(Anchored::No, dfa_state_ids)?; |

333 | } |

334 | if self.dfa.start_kind().has_anchored() { |

335 | self.add_start_group(Anchored::Yes, dfa_state_ids)?; |

336 | } |

337 | // I previously has an 'assert' here checking that either |

338 | // 'dfa_state_ids' was non-empty, or the NFA had zero patterns. But it |

339 | // turns out this isn't always true. For example, the NFA might have |

340 | // one or more patterns but where all such patterns are just 'fail' |

341 | // states. These will ultimately just compile down to DFA dead states, |

342 | // and since the dead state was added earlier, no new DFA states are |

343 | // added. And thus, it is valid and okay for 'dfa_state_ids' to be |

344 | // empty even if there are a non-zero number of patterns in the NFA. |

345 | |

346 | // We only need to compute anchored start states for each pattern if it |

347 | // was requested to do so. |

348 | if self.dfa.starts_for_each_pattern() { |

349 | for pid in self.nfa.patterns() { |

350 | self.add_start_group(Anchored::Pattern(pid), dfa_state_ids)?; |

351 | } |

352 | } |

353 | Ok(()) |

354 | } |

355 | |

356 | /// Add a group of start states for the given match pattern ID. Any new |

357 | /// DFA states added are pushed on to 'dfa_state_ids'. (No duplicates are |

358 | /// pushed.) |

359 | /// |

360 | /// When pattern_id is None, then this will compile a group of unanchored |

361 | /// start states (if the DFA is unanchored). When the pattern_id is |

362 | /// present, then this will compile a group of anchored start states that |

363 | /// only match the given pattern. |

364 | /// |

365 | /// This panics if `anchored` corresponds to an invalid pattern ID. |

366 | fn add_start_group( |

367 | &mut self, |

368 | anchored: Anchored, |

369 | dfa_state_ids: &mut Vec<StateID>, |

370 | ) -> Result<(), BuildError> { |

371 | let nfa_start = match anchored { |

372 | Anchored::No => self.nfa.start_unanchored(), |

373 | Anchored::Yes => self.nfa.start_anchored(), |

374 | Anchored::Pattern(pid) => { |

375 | self.nfa.start_pattern(pid).expect("valid pattern ID") |

376 | } |

377 | }; |

378 | |

379 | // When compiling start states, we're careful not to build additional |

380 | // states that aren't necessary. For example, if the NFA has no word |

381 | // boundary assertion, then there's no reason to have distinct start |

382 | // states for 'NonWordByte' and 'WordByte' starting configurations. |

383 | // Instead, the 'WordByte' starting configuration can just point |

384 | // directly to the start state for the 'NonWordByte' config. |

385 | // |

386 | // Note though that we only need to care about assertions in the prefix |

387 | // of an NFA since this only concerns the starting states. (Actually, |

388 | // the most precisely thing we could do it is look at the prefix |

389 | // assertions of each pattern when 'anchored == Anchored::Pattern', |

390 | // and then only compile extra states if the prefix is non-empty.) But |

391 | // we settle for simplicity here instead of absolute minimalism. It is |

392 | // somewhat rare, after all, for multiple patterns in the same regex to |

393 | // have different prefix look-arounds. |

394 | |

395 | let (id, is_new) = |

396 | self.add_one_start(nfa_start, Start::NonWordByte)?; |

397 | self.dfa.set_start_state(anchored, Start::NonWordByte, id); |

398 | if is_new { |

399 | dfa_state_ids.push(id); |

400 | } |

401 | |

402 | if !self.nfa.look_set_prefix_any().contains_word() { |

403 | self.dfa.set_start_state(anchored, Start::WordByte, id); |

404 | } else { |

405 | let (id, is_new) = |

406 | self.add_one_start(nfa_start, Start::WordByte)?; |

407 | self.dfa.set_start_state(anchored, Start::WordByte, id); |

408 | if is_new { |

409 | dfa_state_ids.push(id); |

410 | } |

411 | } |

412 | if !self.nfa.look_set_prefix_any().contains_anchor() { |

413 | self.dfa.set_start_state(anchored, Start::Text, id); |

414 | self.dfa.set_start_state(anchored, Start::LineLF, id); |

415 | self.dfa.set_start_state(anchored, Start::LineCR, id); |

416 | self.dfa.set_start_state( |

417 | anchored, |

418 | Start::CustomLineTerminator, |

419 | id, |

420 | ); |

421 | } else { |

422 | let (id, is_new) = self.add_one_start(nfa_start, Start::Text)?; |

423 | self.dfa.set_start_state(anchored, Start::Text, id); |

424 | if is_new { |

425 | dfa_state_ids.push(id); |

426 | } |

427 | |

428 | let (id, is_new) = self.add_one_start(nfa_start, Start::LineLF)?; |

429 | self.dfa.set_start_state(anchored, Start::LineLF, id); |

430 | if is_new { |

431 | dfa_state_ids.push(id); |

432 | } |

433 | |

434 | let (id, is_new) = self.add_one_start(nfa_start, Start::LineCR)?; |

435 | self.dfa.set_start_state(anchored, Start::LineCR, id); |

436 | if is_new { |

437 | dfa_state_ids.push(id); |

438 | } |

439 | |

440 | let (id, is_new) = |

441 | self.add_one_start(nfa_start, Start::CustomLineTerminator)?; |

442 | self.dfa.set_start_state( |

443 | anchored, |

444 | Start::CustomLineTerminator, |

445 | id, |

446 | ); |

447 | if is_new { |

448 | dfa_state_ids.push(id); |

449 | } |

450 | } |

451 | |

452 | Ok(()) |

453 | } |

454 | |

455 | /// Add a new DFA start state corresponding to the given starting NFA |

456 | /// state, and the starting search configuration. (The starting search |

457 | /// configuration essentially tells us which look-behind assertions are |

458 | /// true for this particular state.) |

459 | /// |

460 | /// The boolean returned indicates whether the state ID returned is a newly |

461 | /// created state, or a previously cached state. |

462 | fn add_one_start( |

463 | &mut self, |

464 | nfa_start: StateID, |

465 | start: Start, |

466 | ) -> Result<(StateID, bool), BuildError> { |

467 | // Compute the look-behind assertions that are true in this starting |

468 | // configuration, and the determine the epsilon closure. While |

469 | // computing the epsilon closure, we only follow condiional epsilon |

470 | // transitions that satisfy the look-behind assertions in 'look_have'. |

471 | let mut builder_matches = self.get_state_builder().into_matches(); |

472 | util::determinize::set_lookbehind_from_start( |

473 | self.nfa, |

474 | &start, |

475 | &mut builder_matches, |

476 | ); |

477 | self.sparses.set1.clear(); |

478 | util::determinize::epsilon_closure( |

479 | self.nfa, |

480 | nfa_start, |

481 | builder_matches.look_have(), |

482 | &mut self.stack, |

483 | &mut self.sparses.set1, |

484 | ); |

485 | let mut builder = builder_matches.into_nfa(); |

486 | util::determinize::add_nfa_states( |

487 | &self.nfa, |

488 | &self.sparses.set1, |

489 | &mut builder, |

490 | ); |

491 | self.maybe_add_state(builder) |

492 | } |

493 | |

494 | /// Adds the given state to the DFA being built depending on whether it |

495 | /// already exists in this determinizer's cache. |

496 | /// |

497 | /// If it does exist, then the memory used by 'state' is put back into the |

498 | /// determinizer and the previously created state's ID is returned. (Along |

499 | /// with 'false', indicating that no new state was added.) |

500 | /// |

501 | /// If it does not exist, then the state is added to the DFA being built |

502 | /// and a fresh ID is allocated (if ID allocation fails, then an error is |

503 | /// returned) and returned. (Along with 'true', indicating that a new state |

504 | /// was added.) |

505 | fn maybe_add_state( |

506 | &mut self, |

507 | builder: StateBuilderNFA, |

508 | ) -> Result<(StateID, bool), BuildError> { |

509 | if let Some(&cached_id) = self.cache.get(builder.as_bytes()) { |

510 | // Since we have a cached state, put the constructed state's |

511 | // memory back into our scratch space, so that it can be reused. |

512 | self.put_state_builder(builder); |

513 | return Ok((cached_id, false)); |

514 | } |

515 | self.add_state(builder).map(|sid| (sid, true)) |

516 | } |

517 | |

518 | /// Add the given state to the DFA and make it available in the cache. |

519 | /// |

520 | /// The state initially has no transitions. That is, it transitions to the |

521 | /// dead state for all possible inputs, and transitions to the quit state |

522 | /// for all quit bytes. |

523 | /// |

524 | /// If adding the state would exceed the maximum value for StateID, then an |

525 | /// error is returned. |

526 | fn add_state( |

527 | &mut self, |

528 | builder: StateBuilderNFA, |

529 | ) -> Result<StateID, BuildError> { |

530 | let id = self.dfa.add_empty_state()?; |

531 | if !self.config.quit.is_empty() { |

532 | for b in self.config.quit.iter() { |

533 | self.dfa.set_transition( |

534 | id, |

535 | alphabet::Unit::u8(b), |

536 | self.dfa.quit_id(), |

537 | ); |

538 | } |

539 | } |

540 | let state = builder.to_state(); |

541 | // States use reference counting internally, so we only need to count |

542 | // their memory usage once. |

543 | self.memory_usage_state += state.memory_usage(); |

544 | self.builder_states.push(state.clone()); |

545 | self.cache.insert(state, id); |

546 | self.put_state_builder(builder); |

547 | if let Some(limit) = self.config.dfa_size_limit { |

548 | if self.dfa.memory_usage() > limit { |

549 | return Err(BuildError::dfa_exceeded_size_limit(limit)); |

550 | } |

551 | } |

552 | if let Some(limit) = self.config.determinize_size_limit { |

553 | if self.memory_usage() > limit { |

554 | return Err(BuildError::determinize_exceeded_size_limit( |

555 | limit, |

556 | )); |

557 | } |

558 | } |

559 | Ok(id) |

560 | } |

561 | |

562 | /// Returns a state builder from this determinizer that might have existing |

563 | /// capacity. This helps avoid allocs in cases where a state is built that |

564 | /// turns out to already be cached. |

565 | /// |

566 | /// Callers must put the state builder back with 'put_state_builder', |

567 | /// otherwise the allocation reuse won't work. |

568 | fn get_state_builder(&mut self) -> StateBuilderEmpty { |

569 | core::mem::replace( |

570 | &mut self.scratch_state_builder, |

571 | StateBuilderEmpty::new(), |

572 | ) |

573 | } |

574 | |

575 | /// Puts the given state builder back into this determinizer for reuse. |

576 | /// |

577 | /// Note that building a 'State' from a builder always creates a new |

578 | /// alloc, so callers should always put the builder back. |

579 | fn put_state_builder(&mut self, builder: StateBuilderNFA) { |

580 | let _ = core::mem::replace( |

581 | &mut self.scratch_state_builder, |

582 | builder.clear(), |

583 | ); |

584 | } |

585 | |

586 | /// Return the memory usage, in bytes, of this determinizer at the current |

587 | /// point in time. This does not include memory used by the NFA or the |

588 | /// dense DFA itself. |

589 | fn memory_usage(&self) -> usize { |

590 | use core::mem::size_of; |

591 | |

592 | self.builder_states.len() * size_of::<State>() |

593 | // Maps likely use more memory than this, but it's probably close. |

594 | + self.cache.len() * (size_of::<State>() + size_of::<StateID>()) |

595 | + self.memory_usage_state |

596 | + self.stack.capacity() * size_of::<StateID>() |

597 | + self.scratch_state_builder.capacity() |

598 | } |

599 | } |

600 |