Skip to main content

dive_explore/
checkpoint.rs

1//! Completed-level native safety search images, owned by their checked Store.
2//!
3//! Only checkpoint-enabled runs retain discovery rows. Images are trusted local
4//! continuation data, not independent reachability or property certificates.
5
6//! ```
7//! use dive_explore::checkpoint::Session;
8//! let transaction = Session::pause(2)?;
9//! assert!(transaction.paused().is_none());
10//! assert!(!transaction.recovered());
11//! # Ok::<(), dive_core::Error>(())
12//! ```
13use std::sync::Arc;
14
15use dive_core::{Error, Handle, Heap, Store};
16
17use crate::Stats;
18
19/// Existing bounded native archive discovery limit.
20pub const MAX_STATES: usize = 65_536;
21/// Existing bounded native archive depth limit.
22pub const MAX_LEVEL: u64 = 65_536;
23/// Maximum encoded search image, independently of retained Store memory.
24pub 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/// A validated, Store-owned ordered search image. It is not a model certificate.
37#[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    /// Next source level; no saved source has yet been expanded at this boundary.
54    #[must_use]
55    pub const fn next_level(&self) -> u64 {
56        self.next_level
57    }
58    /// Saved model counters before the selected recovery reset policy.
59    #[must_use]
60    pub const fn stats(&self) -> Stats {
61        self.stats
62    }
63    /// Number of saved concrete discoveries, including all expanded states.
64    #[must_use]
65    pub fn discovered(&self) -> usize {
66        self.discoveries.len()
67    }
68    /// Number of actual ordered unexpanded states.
69    #[must_use]
70    pub fn queued(&self) -> usize {
71        self.frontier.len()
72    }
73    /// Saved warning expression ids, to validate against the actual source IR.
74    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    /// Encodes owned rows and ordered search facts, without reference values.
144    ///
145    /// # Errors
146    /// Structural bounds, allocation, or the actual owner's cancellation.
147    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    /// Decodes rows only through this fresh validated Store owner.
187    ///
188    /// # Errors
189    /// Invalid framing, source-independent structure, ownership, bounds or cancellation.
190    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/// Optional native checkpoint transaction. Ordinary exploration does not create it.
338#[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    /// Pauses after `levels` complete source levels; zero pauses after Init.
352    ///
353    /// # Errors
354    /// A level beyond the existing bounded native archive policy.
355    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    /// Continues an actual saved frontier; `retain_counters=false` uses TLC's reset.
372    #[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    /// Whether all imported membership, predecessors and frontier were installed.
387    #[must_use]
388    pub const fn recovered(&self) -> bool {
389        self.restored
390    }
391
392    /// The actual committed-level pause, never a property verdict.
393    #[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    // Recovery-only sessions retain no expanded payload owner after installation.
464    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        // Imported identities and rows are persistent. Do not retain VIEW or
514        // symmetry evaluation scratch across the full discovery stream.
515        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}