1use std::sync::Arc;
14
15use dive_core::{Error, Handle, Heap, Store};
16
17use crate::Stats;
18
19pub const MAX_STATES: usize = 65_536;
21pub const MAX_LEVEL: u64 = 65_536;
23pub const MAX_BYTES: usize = 64 << 20;
25const MAGIC: &[u8; 8] = b"DIVEEX01";
26
27#[derive(Clone, Debug)]
28pub(super) struct Discovery {
29 pub(super) key: u64,
30 pub(super) canonical: Vec<Handle>,
31 pub(super) original: Vec<Handle>,
32 pub(super) parent: Option<u64>,
33 pub(super) ordinal: u32,
34}
35
36#[derive(Clone, Debug)]
38pub struct Snapshot {
39 pub(super) store: Arc<Store>,
40 pub(super) variables: usize,
41 pub(super) next_level: u64,
42 pub(super) stats: Stats,
43 pub(super) discoveries: Vec<Discovery>,
44 pub(super) frontier: Vec<u64>,
45 pub(super) warnings: Vec<(u16, u32)>,
46}
47
48fn invalid(message: impl Into<String>) -> Error {
49 Error::unsupported(format!("native search snapshot: {}", message.into()))
50}
51
52impl Snapshot {
53 #[must_use]
55 pub const fn next_level(&self) -> u64 {
56 self.next_level
57 }
58 #[must_use]
60 pub const fn stats(&self) -> Stats {
61 self.stats
62 }
63 #[must_use]
65 pub fn discovered(&self) -> usize {
66 self.discoveries.len()
67 }
68 #[must_use]
70 pub fn queued(&self) -> usize {
71 self.frontier.len()
72 }
73 pub fn warning_sites(&self) -> impl Iterator<Item = u32> + '_ {
75 self.warnings.iter().map(|v| v.1)
76 }
77
78 fn validate(&self) -> Result<(), Error> {
79 let count = self.discoveries.len();
80 if self.variables > 1024
81 || count == 0
82 || count > MAX_STATES
83 || self.next_level == 0
84 || self.next_level > MAX_LEVEL
85 || self.stats.distinct != count as u64
86 || self.stats.generated < self.stats.initial_generated
87 || self.stats.generated < self.stats.distinct
88 || self.stats.generated > i64::MAX as u64
89 || self.stats.depth > MAX_LEVEL
90 || self.frontier.is_empty()
91 || self.stats.left_on_queue != self.frontier.len() as u64
92 {
93 return Err(invalid("count/level/counter bounds"));
94 }
95 let mut depths = Vec::new();
96 depths
97 .try_reserve_exact(count)
98 .map_err(|_| invalid("depth allocation"))?;
99 let mut children = false;
100 let mut max_depth = 0;
101 for (id, d) in self.discoveries.iter().enumerate() {
102 if d.canonical.len() != self.variables || d.original.len() != self.variables {
103 return Err(invalid("discovery row width"));
104 }
105 let depth = match d.parent {
106 None if !children => 1,
107 Some(parent) if parent < (id as u64) => {
108 children = true;
109 depths[usize::try_from(parent).map_err(|_| invalid("parent address space"))?]
110 + 1
111 }
112 _ => return Err(invalid("ordered predecessor forest")),
113 };
114 if depth > MAX_LEVEL {
115 return Err(invalid("predecessor depth bound"));
116 }
117 max_depth = max_depth.max(depth);
118 depths.push(depth);
119 }
120 let first =
121 usize::try_from(self.frontier[0]).map_err(|_| invalid("frontier address space"))?;
122 if first >= count
123 || self.frontier.len() != count - first
124 || self
125 .frontier
126 .iter()
127 .enumerate()
128 .any(|(i, &id)| id != (first + i) as u64 || depths[first + i] != self.next_level)
129 || max_depth != self.stats.depth
130 {
131 return Err(invalid("complete ordered frontier suffix/depth"));
132 }
133 if self
134 .warnings
135 .iter()
136 .any(|(var, _)| usize::from(*var) >= self.variables)
137 {
138 return Err(invalid("warning variable"));
139 }
140 Ok(())
141 }
142
143 pub fn encode(&self, proceed: &(dyn Fn() -> bool + Sync)) -> Result<Vec<u8>, Error> {
148 self.validate()?;
149 let mut out = Output(Vec::new());
150 out.bytes(MAGIC)?;
151 out.word(self.variables as u64)?;
152 out.word(self.next_level)?;
153 for n in [
154 self.stats.generated,
155 self.stats.distinct,
156 self.stats.depth,
157 self.stats.left_on_queue,
158 self.stats.initial_generated,
159 ] {
160 out.word(n)?;
161 }
162 out.word(self.discoveries.len() as u64)?;
163 for (i, d) in self.discoveries.iter().enumerate() {
164 if i.is_multiple_of(128) && !proceed() {
165 return Err(Error::stop());
166 }
167 out.word(d.key)?;
168 out.word(d.parent.unwrap_or(u64::MAX))?;
169 out.word(u64::from(d.ordinal))?;
170 for h in d.canonical.iter().chain(&d.original) {
171 out.word(h.bits())?;
172 }
173 }
174 out.word(self.frontier.len() as u64)?;
175 for &id in &self.frontier {
176 out.word(id)?;
177 }
178 out.word(self.warnings.len() as u64)?;
179 for &(var, site) in &self.warnings {
180 out.word(u64::from(var))?;
181 out.word(u64::from(site))?;
182 }
183 Ok(out.0)
184 }
185
186 pub fn decode(
191 bytes: &[u8],
192 store: Arc<Store>,
193 proceed: &(dyn Fn() -> bool + Sync),
194 ) -> Result<Self, Error> {
195 if bytes.len() > MAX_BYTES {
196 return Err(invalid("image byte bound"));
197 }
198 let mut input = Input { bytes, at: 0 };
199 if input.take(8)? != MAGIC {
200 return Err(invalid("format/version"));
201 }
202 let variables =
203 usize::try_from(input.word()?).map_err(|_| invalid("variable address space"))?;
204 if variables > 1024 {
205 return Err(invalid("variable bound"));
206 }
207 let next_level = input.word()?;
208 let stats = Stats {
209 generated: input.word()?,
210 distinct: input.word()?,
211 depth: input.word()?,
212 left_on_queue: input.word()?,
213 initial_generated: input.word()?,
214 };
215 let count = input.count(24 + variables * 16, MAX_STATES)?;
216 let mut discoveries = Vec::new();
217 discoveries
218 .try_reserve_exact(count)
219 .map_err(|_| invalid("discovery allocation"))?;
220 for i in 0..count {
221 if i.is_multiple_of(128) && !proceed() {
222 return Err(Error::stop());
223 }
224 let key = input.word()?;
225 let parent = input.word()?;
226 let ordinal = u32::try_from(input.word()?).map_err(|_| invalid("successor ordinal"))?;
227 let mut rows = [Vec::new(), Vec::new()];
228 for (phase, row) in rows.iter_mut().enumerate() {
229 let mut words = Vec::new();
230 words
231 .try_reserve_exact(variables)
232 .map_err(|_| invalid("row allocation"))?;
233 for _ in 0..variables {
234 words.push(input.word()?);
235 }
236 *row = dive_core::store::snapshot::row(&store, &words, phase == 0, proceed)?;
237 }
238 let [canonical, original] = rows;
239 discoveries.push(Discovery {
240 key,
241 parent: (parent != u64::MAX).then_some(parent),
242 ordinal,
243 canonical,
244 original,
245 });
246 }
247 let n = input.count(8, MAX_STATES)?;
248 let mut frontier = Vec::new();
249 frontier
250 .try_reserve_exact(n)
251 .map_err(|_| invalid("frontier allocation"))?;
252 for _ in 0..n {
253 frontier.push(input.word()?);
254 }
255 let n = input.count(16, MAX_STATES)?;
256 let mut warnings = Vec::new();
257 warnings
258 .try_reserve_exact(n)
259 .map_err(|_| invalid("warning allocation"))?;
260 for _ in 0..n {
261 warnings.push((
262 u16::try_from(input.word()?).map_err(|_| invalid("warning variable"))?,
263 u32::try_from(input.word()?).map_err(|_| invalid("warning site"))?,
264 ));
265 }
266 if input.at != bytes.len() {
267 return Err(invalid("trailing search image bytes"));
268 }
269 let snapshot = Self {
270 store,
271 variables,
272 next_level,
273 stats,
274 discoveries,
275 frontier,
276 warnings,
277 };
278 snapshot.validate()?;
279 Ok(snapshot)
280 }
281}
282
283struct Output(Vec<u8>);
284impl Output {
285 fn bytes(&mut self, bytes: &[u8]) -> Result<(), Error> {
286 let end = self
287 .0
288 .len()
289 .checked_add(bytes.len())
290 .filter(|&n| n <= MAX_BYTES)
291 .ok_or_else(|| invalid("search image byte limit"))?;
292 if self.0.capacity() < end {
293 let target = end.max(self.0.capacity().saturating_mul(2)).min(MAX_BYTES);
294 self.0
295 .try_reserve_exact(target - self.0.len())
296 .map_err(|_| invalid("search image allocation"))?;
297 }
298 self.0.extend_from_slice(bytes);
299 Ok(())
300 }
301 fn word(&mut self, n: u64) -> Result<(), Error> {
302 self.bytes(&n.to_le_bytes())
303 }
304}
305struct Input<'a> {
306 bytes: &'a [u8],
307 at: usize,
308}
309impl<'a> Input<'a> {
310 fn take(&mut self, n: usize) -> Result<&'a [u8], Error> {
311 let end = self
312 .at
313 .checked_add(n)
314 .filter(|&n| n <= self.bytes.len())
315 .ok_or_else(|| invalid("truncated search image"))?;
316 let out = &self.bytes[self.at..end];
317 self.at = end;
318 Ok(out)
319 }
320 fn word(&mut self) -> Result<u64, Error> {
321 let mut a = [0; 8];
322 a.copy_from_slice(self.take(8)?);
323 Ok(u64::from_le_bytes(a))
324 }
325 fn count(&mut self, unit: usize, max: usize) -> Result<usize, Error> {
326 let n = usize::try_from(self.word()?).map_err(|_| invalid("count address space"))?;
327 if n > max
328 || n.checked_mul(unit)
329 .is_none_or(|n| n > self.bytes.len().saturating_sub(self.at))
330 {
331 return Err(invalid("declared count bound"));
332 }
333 Ok(n)
334 }
335}
336
337#[derive(Debug)]
339pub struct Session {
340 pub(super) pause_after: Option<u64>,
341 pub(super) imported: Option<Snapshot>,
342 pub(super) retain_counters: bool,
343 pub(super) discoveries: Vec<Discovery>,
344 pub(super) paused: Option<Snapshot>,
345 pub(super) retained_bytes: usize,
346 pub(super) owner: Option<Arc<Store>>,
347 pub(super) started: bool,
348 restored: bool,
349}
350impl Session {
351 pub fn pause(levels: u64) -> Result<Self, Error> {
356 if levels >= MAX_LEVEL {
357 return Err(invalid("pause level bound"));
358 }
359 Ok(Self {
360 pause_after: Some(levels),
361 imported: None,
362 retain_counters: true,
363 discoveries: Vec::new(),
364 paused: None,
365 retained_bytes: 0,
366 owner: None,
367 started: false,
368 restored: false,
369 })
370 }
371 #[must_use]
373 pub fn recover(snapshot: Snapshot, retain_counters: bool) -> Self {
374 Self {
375 pause_after: None,
376 imported: Some(snapshot),
377 retain_counters,
378 discoveries: Vec::new(),
379 paused: None,
380 retained_bytes: 0,
381 owner: None,
382 started: false,
383 restored: false,
384 }
385 }
386 #[must_use]
388 pub const fn recovered(&self) -> bool {
389 self.restored
390 }
391
392 #[must_use]
394 pub fn paused(&self) -> Option<&Snapshot> {
395 self.paused.as_ref()
396 }
397
398 pub(super) fn record(
399 &mut self,
400 heap: &mut Heap,
401 values: &[Handle],
402 original: &[Handle],
403 key: u64,
404 parent: Option<u64>,
405 ordinal: u32,
406 ) -> Result<(), Error> {
407 if self.pause_after.is_none() {
408 return Ok(());
409 }
410 let bytes = values
411 .len()
412 .checked_mul(16)
413 .and_then(|n| n.checked_add(48))
414 .ok_or_else(|| invalid("discovery address space"))?;
415 if self.discoveries.len() >= MAX_STATES
416 || self
417 .retained_bytes
418 .checked_add(bytes)
419 .is_none_or(|n| n > MAX_BYTES / 2)
420 {
421 return Err(invalid("checkpoint discovery admission bound"));
422 }
423 let mut canonical = Vec::new();
424 canonical
425 .try_reserve_exact(values.len())
426 .map_err(|_| invalid("canonical row allocation"))?;
427 for &h in values {
428 canonical.push(heap.intern(h)?);
429 }
430 let mut kept = Vec::new();
431 kept.try_reserve_exact(original.len())
432 .map_err(|_| invalid("original row allocation"))?;
433 for &h in original {
434 kept.push(heap.intern_exact(h)?);
435 }
436 self.discoveries
437 .try_reserve(1)
438 .map_err(|_| invalid("discovery index allocation"))?;
439 self.discoveries.push(Discovery {
440 key,
441 canonical,
442 original: kept,
443 parent,
444 ordinal,
445 });
446 self.retained_bytes += bytes;
447 Ok(())
448 }
449}
450
451pub(super) fn restore(
452 ex: &mut super::Explorer<'_>,
453 m: &mut dive_core::Machine,
454) -> Result<bool, Error> {
455 let Some(session) = ex.checkpoint.as_deref_mut() else {
456 return Ok(false);
457 };
458 if session.started {
459 return Err(invalid("checkpoint session reused"));
460 }
461 session.started = true;
462 let owner = Arc::clone(m.heap.store());
463 session.owner = session.pause_after.map(|_| Arc::clone(&owner));
465 let Some(snapshot) = session.imported.take() else {
466 return Ok(false);
467 };
468 let retain = session.retain_counters;
469 if !Arc::ptr_eq(&snapshot.store, &owner) || snapshot.variables != ex.plan.vars.len() {
470 return Err(invalid("restored Store owner/plan width"));
471 }
472 snapshot.validate()?;
473 for (id, d) in snapshot.discoveries.iter().enumerate() {
474 if id.is_multiple_of(128) && (ex.poll)() {
475 return Err(Error::stop());
476 }
477 m.s1.copy_from_slice(&d.original);
478 let mut identity = Vec::new();
479 let key = ex.seen.key(super::state_identity(
480 m,
481 ex.plan,
482 ex.seen.exact.as_ref().map(|_| &mut identity),
483 )?);
484 if key != d.key
485 || d.original
486 .iter()
487 .zip(&d.canonical)
488 .any(|(&a, &b)| !m.heap.eq(a, b))
489 {
490 return Err(invalid("restored discovery identity"));
491 }
492 ex.cur_id = d.parent;
493 if !ex
494 .seen_insert(
495 key,
496 &identity,
497 &m.heap,
498 ("RecoveryInsertion", Some(u64::from(d.ordinal))),
499 )?
500 .is_new()
501 {
502 return Err(invalid("duplicate restored discovery key"));
503 }
504 let stored = match d.parent {
505 None => ex.log.push_initial(d.ordinal),
506 Some(parent) => ex.log.push(parent, d.ordinal),
507 }
508 .map_err(|e| Error::internal(format!("predecessor log: {e}")))?;
509 if stored != id as u64 {
510 return Err(invalid("restored predecessor coordinate"));
511 }
512 ex.confirm_logged(stored)?;
513 m.heap.reset();
516 }
517 for &id in &snapshot.frontier {
518 let d = &snapshot.discoveries
519 [usize::try_from(id).map_err(|_| invalid("frontier address space"))?];
520 if let Some(frontier) = &mut ex.frontier {
521 frontier.push(id, &d.canonical, &d.original)?;
522 } else {
523 super::capture_reserve(&mut ex.next, d.canonical.len())?;
524 ex.next.extend_from_slice(&d.canonical);
525 super::capture_reserve(&mut ex.next_originals, d.original.len())?;
526 ex.next_originals.extend_from_slice(&d.original);
527 super::capture_reserve(&mut ex.next_ids, 1)?;
528 ex.next_ids.push(id);
529 }
530 }
531 ex.stats = snapshot.stats;
532 ex.stats.left_on_queue = 0;
533 if !retain {
534 ex.stats.generated = ex.stats.distinct;
535 ex.stats.initial_generated = ex.stats.distinct;
536 }
537 ex.level = snapshot.next_level;
538 ex.initial = false;
539 ex.cur_id = None;
540 ex.warnings = snapshot.warnings;
541 m.warnings = ex.warnings.clone();
542 m.heap.reset();
543 if let Some(session) = ex.checkpoint.as_deref_mut() {
544 session.restored = true;
545 }
546 Ok(true)
547}
548
549pub(super) fn boundary(ex: &mut super::Explorer<'_>) -> Result<(), Error> {
550 let queued = ex.queued_states();
551 let Some(session) = ex.checkpoint.as_deref_mut() else {
552 return Ok(());
553 };
554 if queued == 0 || session.pause_after.is_none_or(|n| ex.level <= n) {
555 return Ok(());
556 }
557 if session.discoveries.len() as u64 != ex.stats.distinct || ex.log.len() != ex.stats.distinct {
558 return Err(invalid("completed-level discovery/log mismatch"));
559 }
560 let first = session
561 .discoveries
562 .len()
563 .checked_sub(queued)
564 .ok_or_else(|| invalid("completed-level queue count"))?;
565 let mut frontier = Vec::new();
566 frontier
567 .try_reserve_exact(queued)
568 .map_err(|_| invalid("boundary frontier allocation"))?;
569 frontier.extend((first..session.discoveries.len()).map(|id| id as u64));
570 if ex.frontier.is_none() && ex.next_ids != frontier {
571 return Err(invalid("completed-level frontier order"));
572 }
573 ex.stats.left_on_queue = queued as u64;
574 let snapshot = Snapshot {
575 store: Arc::clone(
576 session
577 .owner
578 .as_ref()
579 .ok_or_else(|| invalid("boundary owner missing"))?,
580 ),
581 variables: ex.plan.vars.len(),
582 next_level: ex.level,
583 stats: ex.stats,
584 discoveries: std::mem::take(&mut session.discoveries),
585 frontier,
586 warnings: ex.warnings.clone(),
587 };
588 snapshot.validate()?;
589 session.paused = Some(snapshot);
590 ex.stop = Some(super::Verdict::CheckpointPaused {
591 next_level: ex.level,
592 });
593 Err(Error::stop())
594}