Skip to main content

dive_explore/
lib.rs

1//! `dive-explore`: breadth-first exploration over a compiled
2//! [`dive_core::Plan`]. With several
3//! workers, each level is expanded in parallel and committed in order
4//! (`parallel.rs`), so every result is the one-worker result.
5//!
6//! The loop follows TLC's `ModelChecker` with one worker:
7//!
8//! - every emitted state counts as generated, before any check;
9//! - an initial state, or a successor, that is not completely specified is
10//!   an error;
11//! - constraints are evaluated before the seen check; a state outside the
12//!   model is not inserted, but its invariants are still checked if it was
13//!   not seen;
14//! - invariants are checked only for new states;
15//! - a state with no successors at all is a deadlock when deadlock is
16//!   checked.
17//!
18//! Successors are probed against the seen set with an incremental hash
19//! computed from the transient buffer, and only new states are interned.
20//! Invariant and constraint conjuncts whose read set does not meet the
21//! variables a step changed are skipped: the parent satisfied them.
22//!
23//! # Example
24//!
25//! The counts of a run are reported in [`Outcome::stats`]; see
26//! `tests/golden.rs` for complete runs from TLA+ sources.
27#![forbid(unsafe_code)]
28
29mod candidate;
30pub mod checkpoint;
31pub mod distributed;
32pub mod ending;
33#[cfg(test)]
34mod exact_identity_tests;
35pub mod graph;
36mod parallel;
37mod reclaim;
38pub mod sample;
39pub mod storage;
40pub mod trace;
41
42use std::sync::Arc;
43use std::time::{Duration, Instant};
44
45use dive_core::handle::{K_STATE, fin, state_term};
46use dive_core::memo::{Memo, SiteStats};
47use dive_core::plan::{Check, Code};
48use dive_core::store::{StoreMemory, StoreStats};
49use dive_core::{Error, ErrorKind, Handle, Machine, Opts, Plan, Sink, Store};
50use dive_store::predecessor::PredecessorLog;
51use dive_store::trace::StateId;
52
53pub use ending::{Failure, Replayed, Site};
54pub use trace::TraceState;
55
56/// How a run ended.
57#[derive(Clone, Debug, PartialEq, Eq)]
58pub enum Verdict {
59    /// The state space was exhausted with no violation.
60    Success,
61    /// An invariant was violated.
62    InvariantViolated {
63        /// The invariant's name.
64        property: String,
65        /// Whether the violating state is initial.
66        initial: bool,
67    },
68    /// A reachable state has no successors.
69    Deadlock,
70    /// Initial states were retained, but no next-state action was defined
71    /// (TLC's `TLC_STATES_AND_NO_NEXT_ACTION`, rather than a deadlock).
72    NoNextAction,
73    /// An implied initial predicate of a `PROPERTY` is false on an initial
74    /// state.
75    PropertyViolatedInitially {
76        /// The property's name.
77        property: String,
78    },
79    /// An implied action `[A]_v` of a `PROPERTY` is false on a step.
80    ActionPropertyViolated {
81        /// The property's name.
82        property: String,
83    },
84    /// An evaluation error, or a state that is not completely specified,
85    /// ended the search: [`Outcome::failure`] says where.
86    Failed,
87    /// A construct, size or error Core does not handle.
88    Unsupported {
89        /// What it was.
90        feature: String,
91    },
92    /// The run's budget (time or memory) ran out: the caller's poll said so.
93    Budget,
94    /// The next new state would exceed a state or depth limit.
95    Admission {
96        /// Which limit.
97        limit: Limit,
98        /// Its value.
99        max: u64,
100        /// The admission that was prevented: the distinct count or the depth
101        /// the state would have had.
102        observed: u64,
103    },
104    /// The graph sink ended the search ([`graph::GraphSink`]); it keeps the
105    /// reason.
106    GraphStop,
107    /// The graph sink stopped the search after a completed level, whose
108    /// frontier is not exhausted.
109    PrefixStop {
110        /// The completed level (the initial states are level 1).
111        level: u64,
112    },
113    /// A requested completed-level pause; never a model verdict.
114    CheckpointPaused {
115        /// Next unexpanded source level.
116        next_level: u64,
117    },
118    /// A checkpoint transaction failed without proving a model result.
119    CheckpointError {
120        /// The explicit structural, ownership or admission failure.
121        message: String,
122    },
123    /// A bug in the core.
124    Internal {
125        /// What happened.
126        message: String,
127    },
128}
129
130/// An admission limit (`--max-states`, `--max-depth`).
131#[derive(Clone, Copy, Debug, PartialEq, Eq)]
132pub enum Limit {
133    /// Distinct states inside the model.
134    States,
135    /// Breadth-first depth (initial states have depth one).
136    Depth,
137}
138
139/// TLC's statistics.
140#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
141pub struct Stats {
142    /// States generated (emitted), initial ones included.
143    pub generated: u64,
144    /// Distinct states found.
145    pub distinct: u64,
146    /// The number of BFS levels reached (initial states are level 1).
147    pub depth: u64,
148    /// States left on the queue when the run ended.
149    pub left_on_queue: u64,
150    /// Initial states generated.
151    pub initial_generated: u64,
152}
153
154/// Strategy metrics.
155#[derive(Clone, Debug, Default)]
156pub struct Metrics {
157    /// Authenticated remote work facts when distributed safety was requested.
158    pub distributed: Option<distributed::Usage>,
159    /// Actual opt-in native safety storage facts, not whole-process memory.
160    pub storage: storage::Usage,
161    /// Successors discarded as seen before any interning.
162    pub discarded_before_intern: u64,
163    /// Successors probed against the seen set.
164    pub probed: u64,
165    /// Invariant and constraint conjunct evaluations needed.
166    pub conjuncts_total: u64,
167    /// Of those, skipped by the parent-delta rule.
168    pub conjuncts_skipped: u64,
169    /// Store intern statistics at the end.
170    pub store: StoreStats,
171    /// Known store storage before explorer workers are dropped; this is a
172    /// lower-bound component snapshot, not process RSS or peak memory.
173    pub store_memory: StoreMemory,
174    /// Memo statistics per site, with the site names.
175    pub memo: Vec<(String, SiteStats)>,
176    /// The largest arena epoch: nodes, pool handles.
177    pub arena_peak: (usize, usize),
178    /// Thunks forced and thunk reads answered from cache.
179    pub thunks: (u64, u64),
180    /// Wall time spent exploring (after compilation).
181    pub explore_time: Duration,
182    /// With several workers: wall time in the parallel expand phase, and in
183    /// the sequential commit phase (`parallel.rs`).
184    pub expand_time: Duration,
185    /// See [`Metrics::expand_time`].
186    pub commit_time: Duration,
187}
188
189/// The result of a run.
190#[derive(Clone, Debug)]
191pub struct Outcome {
192    /// How it ended.
193    pub verdict: Verdict,
194    /// TLC's statistics.
195    pub stats: Stats,
196    /// Strategy metrics.
197    pub metrics: Metrics,
198    /// Warnings 2143 (variable, `UNCHANGED` site as an `ExprId` index), once each, in the
199    /// order raised.
200    pub warnings: Vec<(u16, u32)>,
201    /// The counterexample of a violation, deadlock or failure, initial
202    /// state first, rebuilt by replay; `Err` when the replay failed (a core
203    /// bug). After a failure in a check, the last state is the one checked.
204    pub trace: Option<Result<Vec<TraceState>, String>>,
205    /// Where the search failed ([`Verdict::Failed`]).
206    pub failure: Option<Failure>,
207    /// Whether the run stopped while generating the initial states.
208    pub in_init: bool,
209    /// Whether the run expanded a level after `Init`. `Init` runs on one
210    /// worker; only later levels use the requested width.
211    pub expanded: bool,
212    /// What TLC's call-stack replay changed after an invariant failed to
213    /// evaluate on a new successor.
214    pub replayed: Option<Replayed>,
215    /// The sampled expanded states ([`Config::sample`]), as persistent
216    /// handles and their actual source evaluation levels.
217    pub sampled: Vec<sample::SampledState>,
218    /// What `Print` and `PrintT` printed during the search, in TLC's order
219    /// (a plan that prints runs one worker: [`Plan::effects`]).
220    pub printed: Vec<String>,
221}
222
223/// Run settings.
224#[derive(Clone, Copy, Debug)]
225pub struct Config {
226    /// Strategy switches.
227    pub opts: Opts,
228    /// At most this many distinct states (`--max-states`).
229    pub max_states: Option<u64>,
230    /// At most this depth (`--max-depth`).
231    pub max_depth: Option<u64>,
232    /// Worker threads. Every observable result is the one-worker result.
233    pub workers: usize,
234    /// TLC's warning switch (`-nowarning` turns it off): it also selects
235    /// the all-assigned shortcut for successors (`05` ยง5).
236    pub warn: bool,
237    /// Keep a sample of the expanded states ([`Outcome::sampled`]).
238    pub sample: Option<sample::Sample>,
239}
240
241/// A set of 64-bit state keys (open addressing, linear probing).
242#[derive(Debug)]
243pub struct Seen {
244    table: Vec<u64>,
245    len: usize,
246    exact: Option<storage::Exact>,
247    /// Test-only key override ([`storage::Storage::collide_keys`]).
248    #[cfg(test)]
249    collide_keys: Option<u64>,
250}
251
252impl Default for Seen {
253    fn default() -> Self {
254        Self {
255            table: vec![0; 1 << 16],
256            len: 0,
257            exact: None,
258            #[cfg(test)]
259            collide_keys: None,
260        }
261    }
262}
263
264impl Seen {
265    fn with_detached_exact(exact: bool, detached: bool) -> Self {
266        Self {
267            exact: exact.then(|| {
268                if detached {
269                    storage::Exact::detached()
270                } else {
271                    storage::Exact::default()
272                }
273            }),
274            ..Self::default()
275        }
276    }
277
278    fn empty_like(&self) -> Self {
279        Self {
280            #[cfg(test)]
281            collide_keys: self.collide_keys,
282            ..Self::with_detached_exact(
283                self.exact.is_some(),
284                self.exact.as_ref().is_some_and(storage::Exact::is_detached),
285            )
286        }
287    }
288
289    /// The key a state identity is looked up under. Outside dive-explore's
290    /// own tests this is `key` itself.
291    #[cfg(test)]
292    fn key(&self, key: u64) -> u64 {
293        self.collide_keys.unwrap_or(key)
294    }
295
296    /// The key a state identity is looked up under. Outside dive-explore's
297    /// own tests this is `key` itself.
298    #[cfg(not(test))]
299    #[inline]
300    #[allow(clippy::unused_self, reason = "the test build reads a key override")]
301    const fn key(&self, key: u64) -> u64 {
302        key
303    }
304
305    fn contains_row(
306        &self,
307        key: u64,
308        row: &[Handle],
309        heap: &dive_core::Heap,
310        poll: &(dyn Fn() -> bool + Sync),
311    ) -> Result<bool, Error> {
312        self.exact.as_ref().map_or_else(
313            || Ok(self.contains(key)),
314            |exact| exact.contains_controlled(key, row, heap, poll),
315        )
316    }
317
318    /// Inserts a state; an exact set records `id` as its discovery id.
319    fn insert_row(
320        &mut self,
321        key: u64,
322        row: &[Handle],
323        heap: &dive_core::Heap,
324        id: u64,
325        poll: &(dyn Fn() -> bool + Sync),
326    ) -> Result<storage::Inserted, Error> {
327        if let Some(exact) = &mut self.exact {
328            exact.insert_controlled(key, row, heap, id, poll)
329        } else if self.insert(key) {
330            Ok(storage::Inserted::New)
331        } else {
332            Ok(storage::Inserted::Seen(None))
333        }
334    }
335
336    fn fix(k: u64) -> u64 {
337        if k == 0 { 1 } else { k }
338    }
339
340    fn mask(&self) -> usize {
341        self.table.len() - 1
342    }
343
344    #[allow(clippy::cast_possible_truncation, reason = "masked to the table size")]
345    fn start(&self, k: u64) -> usize {
346        (k as usize) & self.mask()
347    }
348
349    /// Whether `k` is present.
350    #[must_use]
351    pub fn contains(&self, k: u64) -> bool {
352        let k = Self::fix(k);
353        let mut i = self.start(k);
354        loop {
355            match self.table[i] {
356                0 => return false,
357                x if x == k => return true,
358                _ => i = (i + 1) & self.mask(),
359            }
360        }
361    }
362
363    /// Inserts `k`; returns whether it was new.
364    pub fn insert(&mut self, k: u64) -> bool {
365        if (self.len + 1) * 4 > self.table.len() * 3 {
366            self.grow();
367        }
368        let k = Self::fix(k);
369        let mut i = self.start(k);
370        loop {
371            match self.table[i] {
372                0 => {
373                    self.table[i] = k;
374                    self.len += 1;
375                    return true;
376                }
377                x if x == k => return false,
378                _ => i = (i + 1) & self.mask(),
379            }
380        }
381    }
382
383    fn grow(&mut self) {
384        let size = self.table.len() * 2;
385        let old = std::mem::replace(&mut self.table, vec![0; size]);
386        for k in old.into_iter().filter(|&k| k != 0) {
387            let mut i = self.start(k);
388            while self.table[i] != 0 {
389                i = (i + 1) & self.mask();
390            }
391            self.table[i] = k;
392        }
393    }
394
395    /// The number of keys.
396    #[must_use]
397    pub fn len(&self) -> usize {
398        self.len
399    }
400
401    /// Whether no key is present.
402    #[must_use]
403    pub fn is_empty(&self) -> bool {
404        self.len == 0
405    }
406}
407
408/// The state key of `m.s1`: with a `VIEW`, the key of its value; under
409/// `SYMMETRY`, the key of its canonical image (`dive_core::symmetry`).
410///
411/// # Errors
412/// The VIEW's evaluation error (kind `Eval`), or a VIEW value the core
413/// cannot key (unsupported).
414fn state_identity(
415    m: &mut Machine,
416    plan: &Plan,
417    identity: Option<&mut Vec<Handle>>,
418) -> Result<u64, Error> {
419    if let Some(view) = &plan.view {
420        return view_key(m, plan, view, identity);
421    }
422    let image;
423    let state: &[Handle] = match &plan.symmetry {
424        Some(sym) => {
425            let mut out = Vec::with_capacity(m.s1.len());
426            let s1 = m.s1.clone();
427            // The current state is usually the successor's predecessor.
428            sym.canonical_from(&mut m.heap, &s1, &m.s0, &mut out)?;
429            image = out;
430            &image
431        }
432        None => &m.s1,
433    };
434    let mut sum = 0u64;
435    for (i, &h) in state.iter().enumerate() {
436        sum = sum.wrapping_add(state_term(i, m.heap.hash(h)));
437    }
438    if let Some(identity) = identity {
439        capture_reserve(identity, state.len())?;
440        if m.heap.is_speculative() {
441            identity.extend(m.heap.close_identity_row_local(state)?);
442        } else {
443            for &handle in state {
444                identity.push(m.heap.intern(handle)?);
445            }
446        }
447    }
448    Ok(fin(K_STATE, state.len() as u64, sum))
449}
450
451/// The key of the `VIEW`'s value on `m.s1`. TLC normalizes the state's
452/// variables before it evaluates the VIEW (`TLCStateMut.fingerPrint`); the
453/// core interns them, and refuses a state holding an infinite set, whose
454/// normalization it does not reproduce. The value is interned too and must
455/// hold no infinite set, which TLC fails to fingerprint (refused here
456/// rather than reported).
457fn view_key(
458    m: &mut Machine,
459    plan: &Plan,
460    view: &Check,
461    identity: Option<&mut Vec<Handle>>,
462) -> Result<u64, Error> {
463    let Some(conj) = view.conjuncts.first() else {
464        return Err(Error::internal("a VIEW without its expression"));
465    };
466    if !fingerprintable(m, true)? {
467        return Err(Error::unsupported(
468            "a VIEW over a state holding an infinite or lazily represented set (core)",
469        ));
470    }
471    // Under SYMMETRY, TLC evaluates the VIEW on the canonical image
472    // (`TLCStateMut.fingerPrint`).
473    let image = match &plan.symmetry {
474        Some(sym) => {
475            let mut out = Vec::with_capacity(m.s1.len());
476            let s1 = m.s1.clone();
477            // The current state is usually the successor's predecessor.
478            sym.canonical_from(&mut m.heap, &s1, &m.s0, &mut out)?;
479            Some(out)
480        }
481        None => None,
482    };
483    // The VIEW reads the image, or the state itself, as its current state.
484    let saved = if let Some(image) = image {
485        Some(std::mem::replace(&mut m.s0, image))
486    } else {
487        std::mem::swap(&mut m.s0, &mut m.s1);
488        None
489    };
490    let old = m.enter(view.frame);
491    let r = m.eval_norm(&plan.code, conj.p);
492    m.leave(old);
493    if let Some(s0) = saved {
494        m.s0 = s0;
495    } else {
496        std::mem::swap(&mut m.s0, &mut m.s1);
497    }
498    let v = m.heap.state_identity(r?)?;
499    if !closed_fingerprintable(&m.heap, v) {
500        return Err(Error::unsupported(
501            "a VIEW value holding an infinite or lazily represented set (core)",
502        ));
503    }
504    if let Some(identity) = identity {
505        capture_reserve(identity, 1)?;
506        identity.push(v);
507    }
508    Ok(fin(K_STATE, 1, state_term(0, m.heap.hash(v))))
509}
510
511// Capture-only provisional/frontier buffers use checked, fallible growth.
512// The ordinary safety route does not call this helper or retain extra rows.
513pub(crate) fn capture_reserve<T>(values: &mut Vec<T>, additional: usize) -> Result<(), Error> {
514    values
515        .len()
516        .checked_add(additional)
517        .and_then(|n| n.checked_mul(std::mem::size_of::<T>()))
518        .ok_or_else(|| Error::unsupported("capture buffer address space"))?;
519    values
520        .try_reserve(additional)
521        .map_err(|_| Error::unsupported("capture buffer allocation"))
522}
523
524pub(crate) fn capture_copy(values: &[Handle]) -> Result<Vec<Handle>, Error> {
525    let mut copy = Vec::new();
526    capture_reserve(&mut copy, values.len())?;
527    copy.extend_from_slice(values);
528    Ok(copy)
529}
530
531struct Explorer<'p> {
532    plan: &'p Plan,
533    /// The behavior graph's sink, when a temporal check needs it.
534    graph: Option<&'p mut dyn graph::GraphSink>,
535    stats: Stats,
536    metrics: Metrics,
537    seen: Seen,
538    disk: Option<storage::Disk>,
539    checkpoint: Option<&'p mut checkpoint::Session>,
540    distributed: Option<&'p distributed::Coordinator>,
541    next: Vec<Handle>,
542    /// Opt-in encoded current/next queues tied to this live Store.
543    frontier: Option<storage::Frontiers>,
544    candidates: Option<candidate::Account>,
545    candidate_storage: storage::Storage,
546    /// Capture-only first-discovered representations, parallel to `next`.
547    /// Canonical frontier identities remain separate for logs and Step.new.
548    next_originals: Vec<Handle>,
549    emitted: u64,
550    initial: bool,
551    /// Variables the current step changed (bit per variable); all ones for
552    /// initial states.
553    changed: u64,
554    /// The BFS level of the states being emitted (initial states are 1).
555    level: u64,
556    /// Whether this run expanded a level after `Init`, the only phase that
557    /// runs more than one worker.
558    expanded: bool,
559    opts: Opts,
560    stop: Option<Verdict>,
561    /// The index of the action being run (`None` for initial predicates).
562    action: Option<usize>,
563    /// Actual Init action currently generating a candidate.
564    init_action: Option<usize>,
565    /// Parent pointers and ordinals of every enqueued state.
566    log: PredecessorLog,
567    /// The log ids of the states in `next`, in order.
568    next_ids: Vec<StateId>,
569    /// The log id of the state being expanded.
570    cur_id: Option<StateId>,
571    /// The discovery id an in-memory exact seen set recorded for the last
572    /// new state, until the state is logged with exactly that id.
573    predicted: Option<StateId>,
574    /// How the trace of a stop ends: the state to replay up to, and the
575    /// last state when it is not a logged one.
576    end: Option<End>,
577    /// Whether the state being checked passed the constraints.
578    in_model: bool,
579    /// `emitted` when the current action started.
580    action_start: u64,
581    /// The failure that stopped the search.
582    failure: Option<Failure>,
583    /// Whether the budget has run out (polled once per expanded state and
584    /// per initial state).
585    poll: &'p (dyn Fn() -> bool + Sync),
586    max_states: Option<u64>,
587    max_depth: Option<u64>,
588    /// Warnings in the order raised, when levels run in parallel (each
589    /// worker's machine keeps its own).
590    warnings: Vec<(u16, u32)>,
591}
592
593/// How an accepted state inside the model reaches the graph sink.
594#[derive(Clone, Copy, Debug)]
595enum Recorded {
596    /// New: the last state enqueued.
597    New,
598    /// Already seen: its discovery id when the seen set retains ids.
599    Seen(Option<StateId>),
600}
601
602/// The end of a counterexample, recorded at the stop.
603struct End {
604    /// The last logged state of the behavior (`None`: an initial state).
605    upto: Option<StateId>,
606    /// The final state, when it is not logged: the violating successor,
607    /// with the action that emitted it.
608    last: Option<(Option<usize>, Vec<Handle>)>,
609    /// The canonical frontier identities of `upto`, not the original views
610    /// used to evaluate a captured source; replay must reproduce them.
611    expect: Vec<Handle>,
612}
613
614enum Probe {
615    /// Already present: its discovery id when the seen set retains ids.
616    Seen(Option<StateId>),
617    New,
618}
619
620impl Explorer<'_> {
621    fn seen_contains(
622        &mut self,
623        key: u64,
624        row: &[Handle],
625        heap: &dive_core::Heap,
626        phase: (&'static str, Option<u64>),
627    ) -> Result<bool, Error> {
628        let exact = self.seen.exact.is_some();
629        let position = (
630            phase.0,
631            self.stats.generated,
632            self.cur_id,
633            phase.1.unwrap_or_else(|| self.emitted.saturating_sub(1)),
634        );
635        self.disk.as_mut().map_or_else(
636            || self.seen.contains_row(key, row, heap, self.poll),
637            |disk| disk.operation(exact, key, row, heap, false, position, self.poll),
638        )
639    }
640
641    /// Inserts a state. An in-memory exact set records the next discovery id
642    /// (the predecessor log's length), which the state must then be logged
643    /// with ([`Self::confirm_logged`]) before any other state is inserted.
644    fn seen_insert(
645        &mut self,
646        key: u64,
647        row: &[Handle],
648        heap: &dive_core::Heap,
649        phase: (&'static str, Option<u64>),
650    ) -> Result<storage::Inserted, Error> {
651        let exact = self.seen.exact.is_some();
652        let position = (
653            phase.0,
654            self.stats.generated,
655            self.cur_id,
656            phase.1.unwrap_or_else(|| self.emitted.saturating_sub(1)),
657        );
658        if let Some(disk) = &mut self.disk {
659            return disk
660                .operation(exact, key, row, heap, true, position, self.poll)
661                .map(|new| {
662                    if new {
663                        storage::Inserted::New
664                    } else {
665                        storage::Inserted::Seen(None)
666                    }
667                });
668        }
669        if !exact {
670            return self.seen.insert_row(key, row, heap, 0, self.poll);
671        }
672        if self.predicted.is_some() {
673            return Err(Error::internal(
674                "an exact discovery id was recorded for a state that was never logged",
675            ));
676        }
677        let predicted = self.log.len();
678        let inserted = self.seen.insert_row(key, row, heap, predicted, self.poll)?;
679        if inserted.is_new() {
680            self.predicted = Some(predicted);
681        }
682        Ok(inserted)
683    }
684
685    /// Checks that the state just logged as `id` is the one the exact seen
686    /// set recorded with that discovery id.
687    fn confirm_logged(&mut self, id: StateId) -> Result<(), Error> {
688        match self.predicted.take() {
689            Some(predicted) if predicted != id => Err(Error::internal(format!(
690                "the exact seen set recorded discovery id {predicted} for a state logged as {id}"
691            ))),
692            None if self.seen.exact.is_some() && self.disk.is_none() => Err(Error::internal(
693                "a state was logged without its exact discovery id",
694            )),
695            _ => Ok(()),
696        }
697    }
698
699    fn queued_states(&self) -> usize {
700        if self.plan.vars.is_empty() {
701            return 0;
702        }
703        self.frontier.as_ref().map_or_else(
704            || self.next.len() / self.plan.vars.len(),
705            storage::Frontiers::next_len,
706        )
707    }
708
709    fn advance_frontier(&mut self) -> Result<(), Error> {
710        let queued = self.queued_states();
711        if let Some(frontier) = &mut self.frontier {
712            match frontier.advance(self.poll) {
713                Ok(true) => {}
714                Ok(false) => {
715                    self.stats.left_on_queue = queued as u64;
716                    self.stop = Some(Verdict::Budget);
717                    return Err(Error::stop());
718                }
719                Err(error) => {
720                    self.stats.left_on_queue = queued as u64;
721                    return Err(error);
722                }
723            }
724        }
725        Ok(())
726    }
727
728    /// Evaluates a check on the state in `m.s1`.
729    fn check(&mut self, m: &mut Machine, code: &Code, c: &Check) -> Result<bool, Error> {
730        let skip = self.opts.parent_skip && !self.initial;
731        eval_check(m, code, c, skip.then_some(self.changed), &mut self.metrics)
732    }
733
734    /// Whether the state in `m.s1` satisfies the constraints, and the
735    /// action constraints on the step to it; on an error, its site.
736    fn in_model_of(&mut self, m: &mut Machine) -> Result<bool, (Site, Error)> {
737        let skip = self.opts.parent_skip && !self.initial;
738        in_model(
739            m,
740            self.plan,
741            !self.initial,
742            skip.then_some(self.changed),
743            &mut self.metrics,
744        )
745    }
746
747    fn probe(&mut self, m: &mut Machine) -> Result<(Probe, bool, u64), Error> {
748        let in_model = match self.in_model_of(m) {
749            Ok(b) => b,
750            Err((site, e)) => {
751                let e = self.fail_check(m, site, e);
752                if self.failure.is_some() {
753                    self.end_here(m)?;
754                }
755                return Err(e);
756            }
757        };
758        self.in_model = in_model;
759        if !self.opts.early_probe {
760            for i in 0..m.s1.len() {
761                m.s1[i] = m.heap.intern(m.s1[i])?;
762            }
763        }
764        if !in_model && (self.plan.symmetry.is_some() || self.plan.view.is_some()) {
765            // TLC checks a state outside the model without looking it up
766            // (`isSeenState` is for states inside it). Without symmetry or a
767            // VIEW a lookup only skips a state already checked; with them,
768            // a seen image or view value may hide a concrete state that is
769            // not.
770            return Ok((Probe::New, false, 0));
771        }
772        let mut identity = Vec::new();
773        let key = match state_identity(
774            m,
775            self.plan,
776            self.seen.exact.as_ref().map(|_| &mut identity),
777        ) {
778            Ok(k) => self.seen.key(k),
779            Err(e) if e.kind() == ErrorKind::Eval && self.plan.view.is_some() => {
780                self.failure = Some(self.failure_at(m, Site::View, e.message().to_owned())?);
781                self.end_here(m)?;
782                return Err(Error::stop());
783            }
784            Err(e) => return Err(e),
785        };
786        self.metrics.probed += 1;
787        if in_model
788            && (self.max_states.is_some() || self.max_depth.is_some())
789            && !self.seen_contains(key, &identity, &m.heap, ("AdmissionMembership", None))?
790        {
791            self.admit_new()?;
792        }
793        let inserted = if in_model {
794            self.seen_insert(key, &identity, &m.heap, ("Insertion", None))?
795        } else if self.seen_contains(key, &identity, &m.heap, ("AdmissionMembership", None))? {
796            storage::Inserted::Seen(None)
797        } else {
798            storage::Inserted::New
799        };
800        if let storage::Inserted::Seen(id) = inserted {
801            self.metrics.discarded_before_intern +=
802                u64::from(self.opts.early_probe && (!in_model || self.graph.is_none()));
803            return Ok((Probe::Seen(id), in_model, key));
804        }
805        Ok((Probe::New, in_model, key))
806    }
807
808    fn accept(&mut self, m: &mut Machine) -> Result<(), Error> {
809        let plan = self.plan;
810        let code = &plan.code;
811        // The -early-probe control can replace m.s1 with canonical identity
812        // handles. Keep the emitted representation available to capture too.
813        let original = (self.graph.is_some() || self.checkpoint.is_some())
814            .then(|| capture_copy(&m.s1))
815            .transpose()?;
816        if m.assigned != m.s1.len() {
817            let message = incomplete_message(plan, m);
818            self.failure = Some(self.failure_at(m, Site::Incomplete, message)?);
819            self.end_here(m)?;
820            return Err(Error::stop());
821        }
822        if !self.initial {
823            self.changed = changed_vars(m);
824        }
825        let (probe, in_model, key) = self.probe(m)?;
826        if let Probe::Seen(seen) = probe {
827            // TLC checks the implied actions on every step, to a seen state
828            // too (`Search::successor`).
829            if !self.initial {
830                self.implied_actions(m)?;
831            }
832            return if in_model {
833                self.record(m, key, Recorded::Seen(seen), original.as_deref())
834            } else {
835                Ok(())
836            };
837        }
838        // With a VIEW, TLC fingerprints the view's value instead
839        // (`view_key`).
840        if in_model && self.plan.view.is_none() && !fingerprintable(m, self.initial)? {
841            self.failure = Some(self.failure_at(m, Site::Fingerprint, FP_MESSAGE.into())?);
842            self.end_here(m)?;
843            return Err(Error::stop());
844        }
845        // TLC inserts a new state, counting it and its level, before it
846        // checks the invariants.
847        if in_model {
848            self.stats.distinct += 1;
849            self.stats.depth = self.stats.depth.max(self.level);
850        }
851        // TLC enqueues a new initial state before checking its invariants
852        // (`DoInitFunctor.addElement`), and a successor only after
853        // (`Worker.addElement`).
854        let enqueue_first = self.initial && in_model;
855        if enqueue_first {
856            self.enqueue(m, original.as_deref())?;
857        }
858        for (i, c) in plan.invariants.iter().enumerate() {
859            let holds = match self.check(m, code, c) {
860                Ok(b) => b,
861                Err(e) => {
862                    let e = self.fail_check(m, Site::Invariant(i), e);
863                    if self.failure.is_some() {
864                        self.end_here(m)?;
865                    }
866                    return Err(e);
867                }
868            };
869            if !holds {
870                self.stop = Some(Verdict::InvariantViolated {
871                    property: c.name.clone(),
872                    initial: self.initial,
873                });
874                self.end_here(m)?;
875                return Err(Error::stop());
876            }
877        }
878        if self.initial {
879            for (i, c) in plan.implied_inits.iter().enumerate() {
880                let holds = match self.check(m, code, c) {
881                    Ok(b) => b,
882                    Err(e) => {
883                        let e = self.fail_check(m, Site::ImpliedInit(i), e);
884                        if self.failure.is_some() {
885                            self.end_here(m)?;
886                        }
887                        return Err(e);
888                    }
889                };
890                if !holds {
891                    self.stop = Some(Verdict::PropertyViolatedInitially {
892                        property: c.name.clone(),
893                    });
894                    self.end_here(m)?;
895                    return Err(Error::stop());
896                }
897            }
898        } else {
899            self.implied_actions(m)?;
900        }
901        if in_model && !enqueue_first {
902            self.enqueue(m, original.as_deref())?;
903        }
904        if in_model {
905            self.record(m, key, Recorded::New, original.as_deref())?;
906        }
907        Ok(())
908    }
909
910    /// Reports the accepted state inside the model with key `key` to the
911    /// graph sink; a `new` state is the last one enqueued.
912    fn record(
913        &mut self,
914        m: &mut Machine,
915        key: u64,
916        recorded: Recorded,
917        original: Option<&[Handle]>,
918    ) -> Result<(), Error> {
919        let (new, seen) = match recorded {
920            Recorded::New => (true, None),
921            Recorded::Seen(seen) => (false, seen),
922        };
923        if new && let Some(session) = &mut self.checkpoint {
924            let values = m.s1.clone();
925            let original = original.unwrap_or(&values);
926            let ordinal = u32::try_from(self.emitted.saturating_sub(1))
927                .map_err(|_| Error::unsupported("checkpoint successor ordinal bound"))?;
928            if let Err(error) =
929                session.record(&mut m.heap, &values, original, key, self.cur_id, ordinal)
930            {
931                self.stop = Some(Verdict::CheckpointError {
932                    message: error.message().to_owned(),
933                });
934                return Err(Error::stop());
935            }
936        }
937        let Some(sink) = self.graph.as_deref_mut() else {
938            return Ok(());
939        };
940        let nvars = m.s1.len();
941        // Capture preserves the original representation separately from the
942        // canonical identity queued for BFS. No graph means no extra interning
943        // or retained row, including on the duplicate fast path.
944        let kept = if new {
945            Vec::new()
946        } else {
947            let values = original.unwrap_or(&m.s1);
948            let mut kept = Vec::new();
949            capture_reserve(&mut kept, values.len())?;
950            for &handle in values {
951                kept.push(m.heap.intern_exact(handle)?);
952            }
953            kept
954        };
955        let original = if new {
956            self.next_originals
957                .get(self.next_originals.len().saturating_sub(nvars)..)
958                .ok_or_else(|| Error::internal("a new state's original values were not retained"))?
959        } else {
960            &kept
961        };
962        let new = if new {
963            let id = self
964                .next_ids
965                .last()
966                .copied()
967                .ok_or_else(|| Error::internal("a new state was not enqueued"))?;
968            let values = self
969                .next
970                .get(self.next.len().saturating_sub(nvars)..)
971                .ok_or_else(|| Error::internal("a new state's values were not enqueued"))?;
972            Some((id, values))
973        } else {
974            None
975        };
976        let step = graph::Step {
977            key,
978            new,
979            seen,
980            original,
981            parent: self.cur_id,
982            ordinal: self.emitted.saturating_sub(1),
983            action: self.action,
984        };
985        if sink.state(&mut m.heap, step).is_err() {
986            self.stop = Some(Verdict::GraphStop);
987            return Err(Error::stop());
988        }
989        Ok(())
990    }
991
992    /// Reports the `emitted`-th state of its source to the graph sink,
993    /// before its checks.
994    fn report_emitted(&mut self) -> Result<(), Error> {
995        if self.checkpoint.is_some() && self.stats.generated > i64::MAX as u64 {
996            self.stop = Some(Verdict::CheckpointError {
997                message: "native recovery counter bound exceeded".into(),
998            });
999            return Err(Error::stop());
1000        }
1001        let ordinal = (!self.initial).then(|| self.emitted.saturating_sub(1));
1002        let generated = self.stats.generated;
1003        if let Some(sink) = self.graph.as_deref_mut()
1004            && sink.emitted(generated, ordinal).is_err()
1005        {
1006            self.stop = Some(Verdict::GraphStop);
1007            return Err(Error::stop());
1008        }
1009        Ok(())
1010    }
1011
1012    /// The implied actions on the step from `m.s0` to `m.s1`: the first
1013    /// false one stops the search, its trace ending with the successor.
1014    fn implied_actions(&mut self, m: &mut Machine) -> Result<(), Error> {
1015        // An action check reads the expanded state's `TLCGet("level")`.
1016        m.level -= 1;
1017        let r = self.implied_actions_at(m);
1018        m.level += 1;
1019        r
1020    }
1021
1022    fn implied_actions_at(&mut self, m: &mut Machine) -> Result<(), Error> {
1023        let plan = self.plan;
1024        for (i, c) in plan.implied_actions.iter().enumerate() {
1025            let holds = match check_step(m, &plan.code, c) {
1026                Ok(b) => b,
1027                Err(e) => {
1028                    let e = self.fail_check(m, Site::ImpliedAction(i), e);
1029                    if self.failure.is_some() {
1030                        self.end_here(m)?;
1031                    }
1032                    return Err(e);
1033                }
1034            };
1035            if !holds {
1036                self.stop = Some(Verdict::ActionPropertyViolated {
1037                    property: c.name.clone(),
1038                });
1039                self.end_here(m)?;
1040                return Err(Error::stop());
1041            }
1042        }
1043        Ok(())
1044    }
1045
1046    /// Stops before a new state inside the model that would exceed
1047    /// `--max-states` or `--max-depth`; a state already seen is never
1048    /// refused.
1049    fn admit_new(&mut self) -> Result<(), Error> {
1050        let states = self.stats.distinct + 1;
1051        let stop = if let Some(max) = self.max_states
1052            && states > max
1053        {
1054            Some((Limit::States, max, states))
1055        } else if let Some(max) = self.max_depth
1056            && self.level > max
1057        {
1058            Some((Limit::Depth, max, self.level))
1059        } else {
1060            None
1061        };
1062        if let Some((limit, max, observed)) = stop {
1063            self.stop = Some(Verdict::Admission {
1064                limit,
1065                max,
1066                observed,
1067            });
1068            return Err(Error::stop());
1069        }
1070        Ok(())
1071    }
1072
1073    /// Interns the successor in `m.s1`, queues it and logs its parent and
1074    /// ordinal.
1075    fn enqueue(&mut self, m: &mut Machine, original: Option<&[Handle]>) -> Result<(), Error> {
1076        if self.frontier.is_some() {
1077            let mut identity = Vec::new();
1078            let mut retained = Vec::new();
1079            capture_reserve(&mut identity, m.s1.len())?;
1080            capture_reserve(&mut retained, m.s1.len())?;
1081            for &value in &m.s1 {
1082                identity.push(m.heap.intern(value)?);
1083            }
1084            for &value in original.unwrap_or(&m.s1) {
1085                retained.push(m.heap.intern_exact(value)?);
1086            }
1087            let ordinal = u32::try_from(self.emitted.saturating_sub(1))
1088                .map_err(|_| Error::unsupported("more than 2^32 successors of one state"))?;
1089            let id = match self.cur_id {
1090                None => self.log.push_initial(ordinal),
1091                Some(parent) => self.log.push(parent, ordinal),
1092            }
1093            .map_err(|e| Error::internal(format!("predecessor log: {e}")))?;
1094            self.confirm_logged(id)?;
1095            return self
1096                .frontier
1097                .as_mut()
1098                .ok_or_else(|| Error::internal("the spilled frontier disappeared"))?
1099                .push(id, &identity, &retained);
1100        }
1101        if self.graph.is_some() || self.checkpoint.is_some() {
1102            capture_reserve(&mut self.next, m.s1.len())?;
1103            capture_reserve(&mut self.next_originals, m.s1.len())?;
1104            capture_reserve(&mut self.next_ids, 1)?;
1105        }
1106        for i in 0..m.s1.len() {
1107            let h = m.heap.intern(m.s1[i])?;
1108            self.next.push(h);
1109        }
1110        if self.graph.is_some() || self.checkpoint.is_some() {
1111            for &h in original.unwrap_or(&m.s1) {
1112                self.next_originals.push(m.heap.intern_exact(h)?);
1113            }
1114        }
1115        let ordinal = u32::try_from(self.emitted.saturating_sub(1))
1116            .map_err(|_| Error::unsupported("more than 2^32 successors of one state"))?;
1117        let id = match self.cur_id {
1118            None => self.log.push_initial(ordinal),
1119            Some(parent) => self.log.push(parent, ordinal),
1120        }
1121        .map_err(|e| Error::internal(format!("predecessor log: {e}")))?;
1122        self.confirm_logged(id)?;
1123        self.next_ids.push(id);
1124        Ok(())
1125    }
1126
1127    /// Records the successor in `m.s1` as the last state of the trace.
1128    fn end_here(&mut self, m: &mut Machine) -> Result<(), Error> {
1129        let mut values = Vec::with_capacity(m.s1.len());
1130        for &h in &m.s1 {
1131            values.push(if h.is_empty() { h } else { m.heap.intern(h)? });
1132        }
1133        let expect = if self.cur_id.is_some() {
1134            if self.graph.is_some() || self.checkpoint.is_some() || self.distributed.is_some() {
1135                m.s0.iter()
1136                    .map(|&h| m.heap.intern(h))
1137                    .collect::<Result<Vec<_>, _>>()?
1138            } else {
1139                m.s0.clone()
1140            }
1141        } else {
1142            Vec::new()
1143        };
1144        self.end = Some(End {
1145            upto: self.cur_id,
1146            last: Some((self.action, values)),
1147            expect,
1148        });
1149        Ok(())
1150    }
1151}
1152
1153/// Evaluates a check on the state in `m.s1`. With `skip`, the variables the
1154/// step changed: a conjunct that reads none of them is skipped, since the
1155/// parent satisfied it.
1156pub(crate) fn eval_check(
1157    m: &mut Machine,
1158    code: &Code,
1159    c: &Check,
1160    skip: Option<u64>,
1161    metrics: &mut Metrics,
1162) -> Result<bool, Error> {
1163    std::mem::swap(&mut m.s0, &mut m.s1);
1164    let old = m.enter(c.frame);
1165    let mut r = Ok(true);
1166    for conj in &c.conjuncts {
1167        metrics.conjuncts_total += 1;
1168        if let Some(changed) = skip
1169            && conj.skippable
1170            && conj.reads & changed == 0
1171        {
1172            metrics.conjuncts_skipped += 1;
1173            continue;
1174        }
1175        match m.eval_bool(code, conj.p) {
1176            Ok(true) => {}
1177            Ok(false) => {
1178                r = Ok(false);
1179                break;
1180            }
1181            Err(e) => {
1182                r = Err(e);
1183                break;
1184            }
1185        }
1186    }
1187    m.leave(old);
1188    std::mem::swap(&mut m.s0, &mut m.s1);
1189    r
1190}
1191
1192/// Whether the state in `m.s1` satisfies the constraints, and (`step`) the
1193/// action constraints on the step from `m.s0`; on an error, its site.
1194pub(crate) fn in_model(
1195    m: &mut Machine,
1196    plan: &Plan,
1197    step: bool,
1198    skip: Option<u64>,
1199    metrics: &mut Metrics,
1200) -> Result<bool, (Site, Error)> {
1201    let code = &plan.code;
1202    for (i, c) in plan.constraints.iter().enumerate() {
1203        if !eval_check(m, code, c, skip, metrics).map_err(|e| (Site::Constraint(i), e))? {
1204            return Ok(false);
1205        }
1206    }
1207    // `ACTION_CONSTRAINT`s, on the step from the parent (TLC's
1208    // `isInActions`, after `isInModel`); never on initial states.
1209    if step {
1210        // An action check reads the expanded state's `TLCGet("level")`.
1211        m.level -= 1;
1212        let r = (|| {
1213            for (i, c) in plan.action_constraints.iter().enumerate() {
1214                if !check_step(m, code, c).map_err(|e| (Site::ActionConstraint(i), e))? {
1215                    return Ok(false);
1216                }
1217            }
1218            Ok(true)
1219        })();
1220        m.level += 1;
1221        return r;
1222    }
1223    Ok(true)
1224}
1225
1226/// The core's message for a state in `m.s1` that leaves variables
1227/// unassigned.
1228pub(crate) fn incomplete_message(plan: &Plan, m: &Machine) -> String {
1229    let missing: Vec<&str> =
1230        m.s1.iter()
1231            .zip(&plan.vars)
1232            .filter(|(h, _)| h.is_empty())
1233            .map(|(_, n)| n.as_str())
1234            .collect();
1235    format!("not completely specified: {}", missing.join(", "))
1236}
1237
1238/// The variables that differ between `m.s0` and `m.s1` (bit per variable).
1239pub(crate) fn changed_vars(m: &Machine) -> u64 {
1240    let mut changed = 0;
1241    for (i, (a, b)) in m.s0.iter().zip(&m.s1).enumerate() {
1242        if a != b {
1243            changed |= 1u64 << i;
1244        }
1245    }
1246    changed
1247}
1248
1249/// The core's message for [`Site::Fingerprint`]; the caller reports TLC's.
1250const FP_MESSAGE: &str = "a state holds a set that cannot be fingerprinted";
1251
1252/// Whether TLC can fingerprint the new state in `m.s1`, which it does before
1253/// inserting a state inside the model (`ErFpInfinite`). The variables are
1254/// interned in place first, which closes every finite set, so any set kind
1255/// left is an infinite one (`Nat`, `Int`, an infinite `Seq(S)` and the
1256/// like). Only the variables that differ from the parent's are read: the
1257/// parent was fingerprinted. A flagged state the reference fingerprinter
1258/// accepts is refused when the ending is reported, never reported as an
1259/// error.
1260///
1261/// # Errors
1262/// A value too large to intern.
1263pub(crate) fn fingerprintable(m: &mut Machine, initial: bool) -> Result<bool, Error> {
1264    fingerprintable_with_identity(m, initial, None)
1265}
1266
1267/// Reuses only this emission's successful exact identity closure, when it is
1268/// the same unsymmetrized row. No cache survives an emission or Arena rollback.
1269pub(crate) fn fingerprintable_with_identity(
1270    m: &mut Machine,
1271    initial: bool,
1272    identity: Option<&[Handle]>,
1273) -> Result<bool, Error> {
1274    for i in 0..m.s1.len() {
1275        let h = m.s1[i];
1276        if h.is_empty() || !h.is_compound() || (!initial && m.s0.get(i) == Some(&h)) {
1277            continue;
1278        }
1279        let p = if let Some(identity) = identity {
1280            *identity
1281                .get(i)
1282                .ok_or_else(|| Error::internal("candidate identity row width"))?
1283        } else {
1284            m.heap.state_identity(h)?
1285        };
1286        m.s1[i] = p;
1287        if !closed_fingerprintable(&m.heap, p) {
1288            return Ok(false);
1289        }
1290    }
1291    Ok(true)
1292}
1293
1294/// Whether an interned value holds no infinite set.
1295fn closed_fingerprintable(heap: &dive_core::Heap, h: Handle) -> bool {
1296    use dive_core::node::Kind;
1297    if !h.is_compound() {
1298        return true;
1299    }
1300    let v = heap.view(h);
1301    match v.kind {
1302        Kind::Set | Kind::IntFcn | Kind::Fcn => {
1303            v.data.iter().all(|&d| closed_fingerprintable(heap, d))
1304        }
1305        Kind::BigInt | Kind::Interval => true,
1306        _ => false,
1307    }
1308}
1309
1310/// Evaluates a step predicate on `(m.s0, m.s1)`.
1311fn check_step(m: &mut Machine, code: &Code, c: &Check) -> Result<bool, Error> {
1312    let old = m.enter(c.frame);
1313    let mut r = Ok(true);
1314    for conj in &c.conjuncts {
1315        match m.eval_bool(code, conj.p) {
1316            Ok(true) => {}
1317            other => {
1318                r = other;
1319                break;
1320            }
1321        }
1322    }
1323    m.leave(old);
1324    r
1325}
1326
1327impl Sink for Explorer<'_> {
1328    fn emit(&mut self, m: &mut Machine, _code: &Code) -> Result<(), Error> {
1329        // One poll per initial state: the budget can stop a long `Init`
1330        // enumeration between its states.
1331        if self.initial && (self.poll)() {
1332            self.stop = Some(Verdict::Budget);
1333            return Err(Error::stop());
1334        }
1335        if self.graph.is_some() {
1336            self.stats.generated = self
1337                .stats
1338                .generated
1339                .checked_add(1)
1340                .ok_or_else(|| Error::unsupported("capture generated counter overflow"))?;
1341            self.emitted = self
1342                .emitted
1343                .checked_add(1)
1344                .ok_or_else(|| Error::unsupported("capture successor ordinal overflow"))?;
1345            if self.initial {
1346                self.stats.initial_generated = self
1347                    .stats
1348                    .initial_generated
1349                    .checked_add(1)
1350                    .ok_or_else(|| Error::unsupported("capture initial counter overflow"))?;
1351            }
1352        } else {
1353            self.stats.generated += 1;
1354            self.emitted += 1;
1355            if self.initial {
1356                self.stats.initial_generated += 1;
1357            }
1358        }
1359        self.report_emitted()?;
1360        if !self.initial && self.graph.is_some() && (self.poll)() {
1361            self.stop = Some(Verdict::Budget);
1362            return Err(Error::stop());
1363        }
1364        // The checks' transients are freed once the state is accepted:
1365        // an `Init` that enumerates many states, or a state with many
1366        // successors, would otherwise hold them all until the expansion
1367        // ends. Only when no thunk was forced to a transient
1368        // meanwhile, whose slot may hold a value built after the mark.
1369        // The state's own values predate
1370        // the mark, and the frontier holds them interned.
1371        let before = m.heap.mark();
1372        let forced = m.thunk_mark();
1373        let draws = m.draws;
1374        // State checks read the checked state's `TLCGet("level")`.
1375        let level = m.level;
1376        m.level = i64::try_from(self.level).unwrap_or(i64::MAX);
1377        let r = self.accept(m);
1378        m.level = level;
1379        if m.draws != draws {
1380            // TLC's checks draw from the expansion's stream, which the
1381            // trace rebuild replays without them.
1382            return Err(Error::unsupported(
1383                "RandomElement in an invariant, constraint or implied action (M1 core)",
1384            ));
1385        }
1386        if r.is_ok() && m.thunks_released(forced) {
1387            m.heap.rollback(before);
1388        }
1389        if m.heap.poisoned() {
1390            return Err(Error::internal("a stale value handle was read"));
1391        }
1392        r
1393    }
1394}
1395
1396fn run_actions(
1397    m: &mut Machine,
1398    ex: &mut Explorer<'_>,
1399    actions: &[dive_core::plan::Action],
1400    code: &Code,
1401) -> Result<(), Error> {
1402    for (i, a) in actions.iter().enumerate() {
1403        ex.action = (!ex.initial).then_some(i);
1404        ex.init_action = ex.initial.then_some(i);
1405        ex.action_start = ex.emitted;
1406        let old = m.enter(a.frame);
1407        for &(slot, v) in &a.preset {
1408            if let Some(x) = m.frame.get_mut(m.base + slot as usize) {
1409                *x = v;
1410            }
1411        }
1412        let r = m.run_action(code, a.g, ex);
1413        m.leave(old);
1414        r?;
1415    }
1416    Ok(())
1417}
1418
1419/// The workers a run uses: one for a plan with an effect, so that its
1420/// output and draws are in TLC's order ([`Plan::effects`]).
1421fn workers(plan: &Plan, config: &Config) -> usize {
1422    if plan.effects.any {
1423        1
1424    } else {
1425        config.workers.max(1)
1426    }
1427}
1428
1429/// Explores the plan's state space.
1430#[must_use]
1431pub fn explore(
1432    plan: &Plan,
1433    store: &Arc<Store>,
1434    config: Config,
1435    poll: &(dyn Fn() -> bool + Sync),
1436) -> Outcome {
1437    explore_with(plan, store, config, poll, None)
1438}
1439
1440/// Explores the plan's state space, reporting its behavior graph to `graph`
1441/// ([`graph::GraphSink`]) in the one-worker order.
1442#[must_use]
1443#[allow(
1444    clippy::too_many_lines,
1445    reason = "ordered search setup and result assembly stay in one entrypoint"
1446)]
1447pub fn explore_with<'p>(
1448    plan: &'p Plan,
1449    store: &Arc<Store>,
1450    config: Config,
1451    poll: &'p (dyn Fn() -> bool + Sync),
1452    graph: Option<&'p mut dyn graph::GraphSink>,
1453) -> Outcome {
1454    explore_with_control(plan, store, config, poll, graph, None)
1455}
1456
1457/// Explores with the caller's existing owned work checkpoint in addition to
1458/// state-boundary polls. Mathematical identity walks use this same owner.
1459#[must_use]
1460#[allow(
1461    clippy::too_many_lines,
1462    reason = "ordered search setup/result assembly"
1463)]
1464pub fn explore_with_control<'p>(
1465    plan: &'p Plan,
1466    store: &Arc<Store>,
1467    config: Config,
1468    poll: &'p (dyn Fn() -> bool + Sync),
1469    graph: Option<&'p mut dyn graph::GraphSink>,
1470    control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1471) -> Outcome {
1472    explore_with_storage(
1473        plan,
1474        store,
1475        config,
1476        poll,
1477        graph,
1478        control,
1479        &storage::Storage::default(),
1480    )
1481}
1482
1483/// Explores with explicit native safety storage policies. Persistent values stay
1484/// owned by `store`; transient files are not restartable checkpoints.
1485#[must_use]
1486#[allow(
1487    clippy::too_many_arguments,
1488    clippy::too_many_lines,
1489    reason = "search setup and storage policy"
1490)]
1491pub fn explore_with_storage<'p>(
1492    plan: &'p Plan,
1493    store: &Arc<Store>,
1494    config: Config,
1495    poll: &'p (dyn Fn() -> bool + Sync),
1496    graph: Option<&'p mut dyn graph::GraphSink>,
1497    control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1498    storage: &storage::Storage,
1499) -> Outcome {
1500    let mut owner = Arc::clone(store);
1501    explore_inner(
1502        plan, &mut owner, config, poll, graph, control, storage, None, None, false, None,
1503    )
1504}
1505
1506/// Explores pure safety while allowing completed-level replacement of its Store.
1507///
1508/// `store` always names the owner of the returned trace/sample handles. A supplied
1509/// `permanent` must be captured from the same compiled startup before recovery;
1510/// omission captures the current startup. Caller-held clones of replaced Stores
1511/// naturally retain their contents, so callers should transfer their sole owner.
1512/// Checkpoint recovery may continue here; checkpoint pause, graph capture, effects
1513/// and sampling explicitly refuse reclamation. The byte policy is a trigger,
1514/// not a live-root or process-memory limit.
1515#[must_use]
1516#[allow(
1517    clippy::too_many_arguments,
1518    reason = "existing owned search, control and recovery owners"
1519)]
1520pub fn explore_owned<'p>(
1521    plan: &'p Plan,
1522    store: &mut Arc<Store>,
1523    config: Config,
1524    poll: &'p (dyn Fn() -> bool + Sync),
1525    control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1526    storage: &storage::Storage,
1527    session: Option<&'p mut checkpoint::Session>,
1528    permanent: Option<&dive_core::store::compact::Permanent>,
1529) -> Outcome {
1530    explore_inner(
1531        plan, store, config, poll, None, control, storage, session, permanent, true, None,
1532    )
1533}
1534
1535/// Explores pure safety with authenticated remote phase-one evaluation.
1536/// The coordinator retains ordered commit, seen keys and concrete trace replay.
1537#[must_use]
1538#[allow(
1539    clippy::too_many_arguments,
1540    reason = "existing search owners and explicit authenticated coordinator"
1541)]
1542pub fn explore_distributed<'p>(
1543    plan: &'p Plan,
1544    store: &Arc<Store>,
1545    config: Config,
1546    poll: &'p (dyn Fn() -> bool + Sync),
1547    control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1548    storage: &storage::Storage,
1549    coordinator: &'p distributed::Coordinator,
1550) -> Outcome {
1551    let mut owner = Arc::clone(store);
1552    explore_inner(
1553        plan,
1554        &mut owner,
1555        config,
1556        poll,
1557        None,
1558        control,
1559        storage,
1560        None,
1561        None,
1562        false,
1563        Some(coordinator),
1564    )
1565}
1566
1567#[allow(
1568    clippy::too_many_arguments,
1569    clippy::too_many_lines,
1570    reason = "one existing search owner with an optional completed-level transaction"
1571)]
1572fn explore_inner<'p>(
1573    plan: &'p Plan,
1574    store: &mut Arc<Store>,
1575    config: Config,
1576    poll: &'p (dyn Fn() -> bool + Sync),
1577    graph: Option<&'p mut dyn graph::GraphSink>,
1578    control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
1579    storage: &storage::Storage,
1580    checkpoint: Option<&'p mut checkpoint::Session>,
1581    permanent: Option<&dive_core::store::compact::Permanent>,
1582    owned: bool,
1583    distributed: Option<&'p distributed::Coordinator>,
1584) -> Outcome {
1585    let start = Instant::now();
1586    let trigger_bytes = storage.store_compact_bytes;
1587    let mut compact = trigger_bytes.is_some();
1588    let mut reclaim_refusal = if compact && distributed.is_some() {
1589        Some("Store reclamation with distributed workers is not implemented")
1590    } else if compact && !owned {
1591        Some("Store reclamation requires the owned exploration entrypoint")
1592    } else if compact && (graph.is_some() || plan.effects.any || config.sample.is_some()) {
1593        Some("Store reclamation with temporal capture, runtime effects or sampling")
1594    } else if compact && checkpoint.as_ref().is_some_and(|s| s.pause_after.is_some()) {
1595        Some("Store reclamation with checkpoint pause (discovery residency is unsupported)")
1596    } else {
1597        None
1598    };
1599    // A default trigger never turns an admitted search into a refusal: when
1600    // reclamation cannot run, the search keeps its resident Store and says why.
1601    let mut default_skip = None;
1602    if storage.store_compact_default
1603        && let Some(feature) = reclaim_refusal.take()
1604    {
1605        compact = false;
1606        default_skip = Some(feature.to_owned());
1607    }
1608    let captured_permanent = if compact && permanent.is_none() && reclaim_refusal.is_none() {
1609        Some(dive_core::store::compact::Permanent::capture(
1610            store,
1611            &|| !poll(),
1612        ))
1613    } else {
1614        None
1615    };
1616    let (captured_permanent, mut permanent_error) = match captured_permanent.transpose() {
1617        Ok(permanent) => (permanent, None),
1618        Err(error) => (None, Some(error)),
1619    };
1620    if storage.store_compact_default
1621        && let Some(error) = permanent_error.take_if(|error| reclaim::skippable(error))
1622    {
1623        compact = false;
1624        default_skip = Some(error.message().to_owned());
1625    }
1626    let storage_owned;
1627    let storage = if storage.store_compact_default && !compact {
1628        storage_owned = storage::Storage {
1629            store_compact_bytes: None,
1630            ..storage.clone()
1631        };
1632        &storage_owned
1633    } else {
1634        storage
1635    };
1636    let permanent = permanent.or(captured_permanent.as_ref());
1637    let config = if storage.seen_disk.is_some() {
1638        Config {
1639            workers: 1,
1640            ..config
1641        }
1642    } else {
1643        config
1644    };
1645    let unsupported_storage = graph.is_some()
1646        && (storage.seen_disk.is_some()
1647            || storage.predecessor_memory_bytes.is_some()
1648            || storage.predecessor_directory.is_some()
1649            || storage.frontier_memory_bytes.is_some()
1650            || storage.frontier_directory.is_some()
1651            || storage.candidate_memory_bytes.is_some()
1652            || storage.candidate_directory.is_some());
1653    let nvars = plan.vars.len();
1654    let (frontier, storage_setup_error) = match storage
1655        .frontier_memory_bytes
1656        .map(|_| storage::Frontiers::new(store, nvars, storage))
1657        .transpose()
1658    {
1659        Ok(frontier) => (frontier, None),
1660        Err(error) => (None, Some(error)),
1661    };
1662    let mut initial_metrics = Metrics::default();
1663    initial_metrics.storage.reclamation.trigger_bytes = trigger_bytes;
1664    initial_metrics.storage.reclamation.default_trigger = storage.store_compact_default;
1665    initial_metrics.storage.reclamation.skipped = default_skip;
1666    let (disk, disk_setup_error) = match storage
1667        .seen_disk
1668        .as_ref()
1669        .map(|options| storage::Disk::new(storage.exact, options))
1670        .transpose()
1671    {
1672        Ok(disk) => (disk, None),
1673        Err(error) => {
1674            initial_metrics.storage.seen = Some(storage::DiskUsage {
1675                limits: storage
1676                    .seen_disk
1677                    .as_ref()
1678                    .map_or_else(dive_store::seen::Limits::default, |options| options.limits),
1679                admitted_keys: 0,
1680                before_cleanup: None,
1681                after_cleanup: None,
1682                first_failure: Some(storage::DiskFailure {
1683                    phase: "Creation",
1684                    error: error.clone(),
1685                    generated: 0,
1686                    predecessor: None,
1687                    successor_ordinal: 0,
1688                }),
1689                deciding_event_before_failure: None,
1690                audit_completed: false,
1691            });
1692            (None, Some(Error::internal(error.to_string())))
1693        }
1694    };
1695    let mut seen = Seen::with_detached_exact(storage.exact, compact);
1696    #[cfg(test)]
1697    {
1698        seen.collide_keys = storage.collide_keys;
1699    }
1700    if storage.seen_disk.is_some() {
1701        seen.table = Vec::new();
1702    }
1703    let keys: Vec<usize> = plan
1704        .code
1705        .sites
1706        .iter()
1707        .map(dive_core::plan::MemoSite::key_len)
1708        .collect();
1709    let local_workers = if distributed.is_some() {
1710        1
1711    } else {
1712        workers(plan, &config)
1713    };
1714    let mut machines: Vec<Machine> = (0..local_workers)
1715        .map(|_| {
1716            let mut m = Machine::new(Arc::clone(store), nvars, config.opts, Memo::new(&keys));
1717            m.warn = config.warn;
1718            m.set_work_control(control.cloned());
1719            m.set_debugger(plan.code.debugger.clone());
1720            m
1721        })
1722        .collect();
1723    let mut ex = Explorer {
1724        plan,
1725        graph,
1726        stats: Stats::default(),
1727        metrics: initial_metrics,
1728        seen,
1729        disk,
1730        checkpoint,
1731        distributed,
1732        next: Vec::new(),
1733        frontier,
1734        candidates: storage.candidate_memory_bytes.map(|bytes| {
1735            Arc::new(std::sync::Mutex::new(storage::CandidateUsage {
1736                memory_bytes_per_worker: Some(bytes),
1737                ..storage::CandidateUsage::default()
1738            }))
1739        }),
1740        candidate_storage: storage.clone(),
1741        next_originals: Vec::new(),
1742        emitted: 0,
1743        initial: true,
1744        changed: u64::MAX,
1745        level: 1,
1746        expanded: false,
1747        opts: config.opts,
1748        stop: None,
1749        action: None,
1750        init_action: None,
1751        log: PredecessorLog::new(
1752            storage.predecessor_memory_bytes,
1753            storage.predecessor_directory.as_deref(),
1754        ),
1755        next_ids: Vec::new(),
1756        cur_id: None,
1757        predicted: None,
1758        end: None,
1759        in_model: true,
1760        action_start: 0,
1761        failure: None,
1762        poll,
1763        max_states: config.max_states,
1764        max_depth: config.max_depth,
1765        warnings: Vec::new(),
1766    };
1767    let mut replayed = None;
1768    let mut reservoir = config.sample.map(sample::Reservoir::new);
1769    let result = if let Some(feature) = reclaim_refusal {
1770        Err(Error::unsupported(feature))
1771    } else if let Some(error) = permanent_error.or(disk_setup_error).or(storage_setup_error) {
1772        Err(error)
1773    } else if distributed.is_some()
1774        && (ex.graph.is_some()
1775            || config.sample.is_some()
1776            || plan.effects.any
1777            || plan.view.is_some()
1778            || plan.symmetry.is_some()
1779            || storage.seen_disk.is_some()
1780            || storage.candidate_memory_bytes.is_some())
1781    {
1782        Err(Error::unsupported(
1783            "distributed effects, VIEW, symmetry, sampling, disk seen or candidate spill",
1784        ))
1785    } else if unsupported_storage {
1786        Err(Error::unsupported(
1787            "spilled native temporal storage (disk seen set, predecessor, frontier or candidate spill)",
1788        ))
1789    } else if storage.candidate_directory.is_some() && storage.candidate_memory_bytes.is_none() {
1790        Err(Error::unsupported(
1791            "a candidate directory without a candidate memory budget",
1792        ))
1793    } else if storage.candidate_memory_bytes.is_some() && plan.effects.any {
1794        Err(Error::unsupported("candidate spill with runtime effects"))
1795    } else if storage.predecessor_directory.is_some() && storage.predecessor_memory_bytes.is_none()
1796    {
1797        Err(Error::unsupported(
1798            "a predecessor directory without a predecessor memory budget",
1799        ))
1800    } else if storage.frontier_directory.is_some() && storage.frontier_memory_bytes.is_none() {
1801        Err(Error::unsupported(
1802            "a frontier directory without a frontier memory budget",
1803        ))
1804    } else {
1805        run(
1806            &mut machines,
1807            &mut ex,
1808            plan,
1809            &mut replayed,
1810            reservoir.as_mut(),
1811            store,
1812            permanent,
1813            control,
1814        )
1815    };
1816    let parallel = machines.len() > 1 || ex.candidates.is_some() || ex.distributed.is_some();
1817    if let (Some(coordinator), Err(error)) = (distributed, &result) {
1818        coordinator.record_failure(error);
1819    }
1820    let mut m = machines.swap_remove(0);
1821    if let Err(error) = &result
1822        && error.message().starts_with("DIVE-S0203:")
1823    {
1824        ex.metrics
1825            .storage
1826            .reclamation
1827            .failures
1828            .push(error.message().to_owned());
1829    }
1830    let mut trace = ex
1831        .end
1832        .take()
1833        .map(|end| reconstruct(plan, store, &config, &ex.log, end));
1834    let mut verdict = match result {
1835        Ok(()) => Verdict::Success,
1836        Err(e) => match e.into_parts() {
1837            (ErrorKind::Stop, _) if ex.failure.is_some() => Verdict::Failed,
1838            (ErrorKind::Stop, _) => match ex.stop.take() {
1839                Some(stop) => stop,
1840                None if (poll)() || m.heap.work_interrupted() => Verdict::Budget,
1841                None => Verdict::Success,
1842            },
1843            (ErrorKind::Unsupported, message) => Verdict::Unsupported { feature: message },
1844            (ErrorKind::Eval, message) => Verdict::Unsupported {
1845                feature: format!("evaluation error classification (M0 core): {message}"),
1846            },
1847            (ErrorKind::Internal, message) => Verdict::Internal { message },
1848        },
1849    };
1850    if let Some(account) = &ex.candidates {
1851        ex.metrics.storage.candidates = account
1852            .lock()
1853            .unwrap_or_else(std::sync::PoisonError::into_inner)
1854            .clone();
1855        if !ex.metrics.storage.candidates.failures.is_empty() {
1856            ex.metrics.storage.candidates.deciding_event_before_failure =
1857                Some(format!("{verdict:?}"));
1858            verdict = Verdict::Internal {
1859                message: ex.metrics.storage.candidates.failures.join("; "),
1860            };
1861            trace = None;
1862        }
1863    }
1864    ex.metrics.storage.exact_states = ex.seen.exact.as_ref().map_or(0, storage::Exact::len);
1865    if let Some(disk) = &mut ex.disk {
1866        let validate = !matches!(
1867            verdict,
1868            Verdict::Budget
1869                | Verdict::Admission { .. }
1870                | Verdict::Unsupported { .. }
1871                | Verdict::Internal { .. }
1872        );
1873        let complete = disk.finish(validate, poll, verdict.clone());
1874        if storage.exact {
1875            ex.metrics.storage.exact_states =
1876                usize::try_from(disk.usage.admitted_keys).unwrap_or(usize::MAX);
1877        }
1878        ex.metrics.storage.seen = Some(disk.usage.clone());
1879        if let Some(failure) = &disk.usage.first_failure {
1880            verdict = Verdict::Internal {
1881                message: failure.error.to_string(),
1882            };
1883            trace = None;
1884        } else if !complete {
1885            verdict = Verdict::Budget;
1886            trace = None;
1887        }
1888    }
1889    ex.metrics.storage.predecessor = ex.log.usage();
1890    if let Some(error) = ex.log.failure() {
1891        ex.metrics
1892            .storage
1893            .predecessor_failures
1894            .push(error.to_string());
1895    }
1896    match ex.log.close() {
1897        Ok(()) => ex.metrics.storage.predecessor_cleanup_completed = true,
1898        Err(error) => ex
1899            .metrics
1900            .storage
1901            .predecessor_failures
1902            .push(error.to_string()),
1903    }
1904    if !ex.metrics.storage.predecessor_failures.is_empty() {
1905        ex.metrics.storage.predecessor_deciding_event = Some(format!("{verdict:?}"));
1906        verdict = Verdict::Internal {
1907            message: ex.metrics.storage.predecessor_failures.join("; "),
1908        };
1909        trace = None;
1910    }
1911    if let Some(frontier) = &mut ex.frontier {
1912        let validate = !matches!(
1913            verdict,
1914            Verdict::Budget
1915                | Verdict::Admission { .. }
1916                | Verdict::Unsupported { .. }
1917                | Verdict::Internal { .. }
1918        );
1919        let completed = frontier.finish(validate, poll);
1920        ex.metrics.storage.frontier = frontier.usage.clone();
1921        if !ex.metrics.storage.frontier.failures.is_empty() {
1922            ex.metrics.storage.frontier.deciding_event_before_failure =
1923                Some(format!("{verdict:?}"));
1924            verdict = Verdict::Internal {
1925                message: ex.metrics.storage.frontier.failures.join("; "),
1926            };
1927            trace = None;
1928        } else if !completed {
1929            verdict = Verdict::Budget;
1930            trace = None;
1931        }
1932    }
1933    let mut metrics = ex.metrics;
1934    metrics.distributed = distributed.map(distributed::Coordinator::usage);
1935    metrics.store = store.stats();
1936    metrics.store_memory = store.memory_usage();
1937    metrics.memo = plan
1938        .code
1939        .sites
1940        .iter()
1941        .map(|s| s.name.clone())
1942        .zip(m.memo.stats())
1943        .collect();
1944    let (nodes, handles) = m.heap.arena().peak();
1945    metrics.arena_peak.0 = metrics.arena_peak.0.max(nodes);
1946    metrics.arena_peak.1 = metrics.arena_peak.1.max(handles);
1947    for worker in &machines {
1948        let (nodes, handles) = worker.heap.arena().peak();
1949        metrics.arena_peak.0 = metrics.arena_peak.0.max(nodes);
1950        metrics.arena_peak.1 = metrics.arena_peak.1.max(handles);
1951    }
1952    metrics.thunks = (m.stats.forced, m.stats.cached);
1953    metrics.explore_time = start.elapsed();
1954    let warnings = if !config.warn {
1955        Vec::new()
1956    } else if parallel {
1957        std::mem::take(&mut ex.warnings)
1958    } else {
1959        std::mem::take(&mut m.warnings)
1960    };
1961    Outcome {
1962        verdict,
1963        stats: ex.stats,
1964        metrics,
1965        warnings,
1966        trace,
1967        failure: ex.failure,
1968        in_init: ex.initial,
1969        expanded: ex.expanded,
1970        replayed,
1971        sampled: reservoir.map(|r| r.states).unwrap_or_default(),
1972        printed: std::mem::take(&mut m.printed),
1973    }
1974}
1975
1976/// Rebuilds the behavior that ends at `end`.
1977fn reconstruct(
1978    plan: &Plan,
1979    store: &Arc<Store>,
1980    config: &Config,
1981    log: &PredecessorLog,
1982    end: End,
1983) -> Result<Vec<TraceState>, String> {
1984    let mut states = match end.upto {
1985        None => Vec::new(),
1986        Some(id) => {
1987            let path = log.path(id).map_err(|e| format!("predecessor log: {e}"))?;
1988            let states = trace::replay(plan, store, config.opts, config.warn, &path)
1989                .map_err(|e| e.message().to_owned())?;
1990            if !states
1991                .last()
1992                .is_some_and(|s| replay_values_match(store, &s.values, &end.expect))
1993            {
1994                return Err("trace replay produced a different state than the search".into());
1995            }
1996            states
1997        }
1998    };
1999    if let Some((action, values)) = end.last {
2000        states.push(TraceState { action, values });
2001    }
2002    Ok(states)
2003}
2004
2005/// Replay allocates fresh persistent compounds when hash-consing is disabled.
2006/// Their values must still match; unequal handles alone are not a mismatch.
2007fn replay_values_match(store: &Arc<Store>, actual: &[Handle], expected: &[Handle]) -> bool {
2008    if actual == expected {
2009        return true;
2010    }
2011    if store.hashcons() || actual.len() != expected.len() {
2012        return false;
2013    }
2014    let heap = dive_core::Heap::new(Arc::clone(store), false, false);
2015    actual.iter().zip(expected).all(|(&a, &b)| heap.eq(a, b))
2016}
2017
2018/// Turns an evaluation error raised by the generator itself (not by a
2019/// check in the sink, which records its own failure) into a failure.
2020/// `identity` is the canonical frontier row, distinct from capture's original
2021/// source in `m.s0`; the initial generator has no logged parent.
2022fn generator_error(m: &Machine, ex: &mut Explorer<'_>, identity: &[Handle], e: Error) -> Error {
2023    if e.kind() != ErrorKind::Eval || ex.failure.is_some() {
2024        return e;
2025    }
2026    ex.failure = Some(ex.generator_failure(m, e.message().to_owned()));
2027    if let Some(id) = ex.cur_id {
2028        ex.end = Some(End {
2029            upto: Some(id),
2030            last: None,
2031            expect: identity.to_vec(),
2032        });
2033    }
2034    Error::stop()
2035}
2036
2037fn source_row(
2038    machine: &mut Machine,
2039    explorer: &mut Explorer<'_>,
2040    identity: &[Handle],
2041    left: u64,
2042    terminal: bool,
2043) -> Result<(), Error> {
2044    let Some(source) = explorer.cur_id else {
2045        return Ok(());
2046    };
2047    let error = terminal.then_some(explorer.failure.as_ref()).flatten();
2048    let Some(sink) = explorer.graph.as_deref_mut() else {
2049        return Ok(());
2050    };
2051    let row = graph::SourceRow {
2052        source,
2053        original: &machine.s0,
2054        emitted: explorer.emitted,
2055        next_error: error,
2056        stats: Stats {
2057            left_on_queue: left,
2058            ..explorer.stats
2059        },
2060    };
2061    if sink.source_row(&mut machine.heap, row).is_err() {
2062        explorer.stats.left_on_queue = left;
2063        explorer.stop = Some(Verdict::GraphStop);
2064        explorer.end = Some(End {
2065            upto: Some(source),
2066            last: None,
2067            expect: identity.to_vec(),
2068        });
2069        return Err(Error::stop());
2070    }
2071    Ok(())
2072}
2073
2074/// Starts the random stream draws come from: the startup stream for
2075/// `Init`, or the stream of expanding `state`.
2076pub(crate) fn start_stream(
2077    m: &mut Machine,
2078    plan: &Plan,
2079    state: Option<&[Handle]>,
2080) -> Result<(), Error> {
2081    if !plan.effects.draws {
2082        return Ok(());
2083    }
2084    let Some(draws) = m.heap.store().draws().cloned() else {
2085        return Err(Error::unsupported(
2086            "RandomElement without the run's random streams (M1 core)",
2087        ));
2088    };
2089    m.draw = Some(match state {
2090        None => draws.startup(),
2091        Some(vars) => draws.state(&mut m.heap, vars)?,
2092    });
2093    Ok(())
2094}
2095
2096/// Reports the completed level to the graph sink, which may stop the
2097/// search after it.
2098fn level_done(ex: &mut Explorer<'_>, _nvars: usize) -> Result<(), Error> {
2099    let left_on_queue = ex.queued_states() as u64;
2100    let Some(sink) = ex.graph.as_deref_mut() else {
2101        return Ok(());
2102    };
2103    let counts = Stats {
2104        left_on_queue,
2105        ..ex.stats
2106    };
2107    let level = ex.level - 1;
2108    let stop = sink.level_done(level, counts);
2109    if stop == Ok(false) {
2110        return Ok(());
2111    }
2112    ex.stats.left_on_queue = counts.left_on_queue;
2113    ex.stop = Some(match stop {
2114        Ok(_) if counts.left_on_queue > 0 => Verdict::PrefixStop { level },
2115        Ok(_) => Verdict::Internal {
2116            message: "a prefix stop with an exhausted frontier".into(),
2117        },
2118        Err(graph::Stopped) => Verdict::GraphStop,
2119    });
2120    Err(Error::stop())
2121}
2122
2123/// The states of a parallel level each worker expands per chunk.
2124const CHUNK_PER_WORKER: usize = 4096;
2125/// The optional encoded path decodes at most this many state pairs at once.
2126const FRONTIER_CHUNK_STATES: usize = 1024;
2127
2128#[allow(
2129    clippy::too_many_lines,
2130    clippy::too_many_arguments,
2131    reason = "TLC's ordered level loop: expansion, stops, replay and deadlock"
2132)]
2133fn run(
2134    machines: &mut [Machine],
2135    ex: &mut Explorer<'_>,
2136    plan: &Plan,
2137    replayed: &mut Option<Replayed>,
2138    mut reservoir: Option<&mut sample::Reservoir>,
2139    store: &mut Arc<Store>,
2140    permanent: Option<&dive_core::store::compact::Permanent>,
2141    control: Option<&Arc<dyn dive_core::eval::WorkControl>>,
2142) -> Result<(), Error> {
2143    let code = &plan.code;
2144    let nvars = plan.vars.len();
2145    let parallel = machines.len() > 1 || ex.candidates.is_some() || ex.distributed.is_some();
2146    let Some(m) = machines.first_mut() else {
2147        return Err(Error::internal("no core machine"));
2148    };
2149    let recovered = checkpoint::restore(ex, m)?;
2150    if !recovered {
2151        start_stream(m, plan, None)?;
2152        // `TLCGet("level")` is 0 in `Init` (TLC's `INIT_LEVEL - 1`).
2153        m.level = 0;
2154        if let Err(e) = run_actions(m, ex, &plan.init, code) {
2155            ex.stats.left_on_queue = ex.queued_states() as u64;
2156            return Err(generator_error(m, ex, &[], e));
2157        }
2158        // TLC reports depth one after Init emits a state, even when the
2159        // constraints exclude every candidate from the retained graph.
2160        ex.stats.depth = ex
2161            .stats
2162            .depth
2163            .max(u64::from(ex.stats.initial_generated > 0));
2164        // ModelChecker checks this after Init, before starting any workers.
2165        // An empty initial frontier succeeds; defining a disabled action instead
2166        // reaches the ordinary deadlock check, if enabled.
2167        if plan.next.is_empty() && ex.queued_states() > 0 {
2168            ex.stats.left_on_queue = ex.queued_states() as u64;
2169            ex.stop = Some(Verdict::NoNextAction);
2170            return Err(Error::stop());
2171        }
2172        m.heap.reset();
2173        ex.initial = false;
2174        ex.warnings.clone_from(&m.warnings);
2175    }
2176    checkpoint::boundary(ex)?;
2177    reclaim::boundary(machines, ex, store, permanent, control)?;
2178    let mut cur = std::mem::take(&mut ex.next);
2179    let mut cur_originals = std::mem::take(&mut ex.next_originals);
2180    let mut cur_ids = std::mem::take(&mut ex.next_ids);
2181    ex.advance_frontier()?;
2182    let mut generated_before = 0;
2183    loop {
2184        let states = cur.len().checked_div(nvars).map_or(0, |in_memory| {
2185            ex.frontier
2186                .as_ref()
2187                .map_or(in_memory, storage::Frontiers::current_len)
2188        });
2189        if states == 0 {
2190            break;
2191        }
2192        if (ex.graph.is_some() || ex.checkpoint.is_some())
2193            && ex.frontier.is_none()
2194            && cur_originals.len() != cur.len()
2195        {
2196            return Err(Error::internal(
2197                "capture frontier original/identity row mismatch",
2198            ));
2199        }
2200        ex.level += 1;
2201        ex.expanded = true;
2202        // Claims are sized from the previous level's successors.
2203        let estimate = usize::try_from(ex.stats.generated - generated_before).unwrap_or(1 << 20);
2204        generated_before = ex.stats.generated;
2205        let level_started = Instant::now();
2206        let mut expand_time = std::time::Duration::ZERO;
2207        // The parallel level is expanded and committed a chunk of states at
2208        // a time, so that phase 1 buffers one chunk's successors, not the
2209        // level's. A chunk's commit fills the seen set before the
2210        // next chunk is expanded, which reads it as an earlier level's.
2211        let chunk = ex.graph.as_deref().map_or_else(
2212            || (machines.len() * CHUNK_PER_WORKER).max(1),
2213            |sink| sink.max_expansion_units().max(1),
2214        );
2215        let chunk = if ex.candidates.is_some() {
2216            machines.len().max(1)
2217        } else {
2218            chunk
2219        };
2220        let chunk = ex
2221            .distributed
2222            .map_or(chunk, |coordinator| chunk.min(coordinator.width()));
2223        let chunk = if ex.frontier.is_some() {
2224            chunk.min(FRONTIER_CHUNK_STATES)
2225        } else {
2226            chunk
2227        };
2228        let mut expanded: Option<Vec<Option<parallel::Expanded>>> = None;
2229        let mut received: Option<Vec<Option<distributed::Received>>> = None;
2230        let mut decoded = storage::Chunk::default();
2231        let mut base = 0;
2232        for k in 0..states {
2233            if k % chunk == 0 {
2234                let queued = ex.queued_states();
2235                if let Some(frontier) = &mut ex.frontier {
2236                    decoded = match frontier.chunk(k, (k + chunk).min(states), ex.poll) {
2237                        Ok(Some(decoded)) => decoded,
2238                        Ok(None) => {
2239                            ex.stats.left_on_queue = (states - k + queued) as u64;
2240                            ex.stop = Some(Verdict::Budget);
2241                            return Err(Error::stop());
2242                        }
2243                        Err(error) => {
2244                            ex.stats.left_on_queue = (states - k + queued) as u64;
2245                            return Err(error);
2246                        }
2247                    };
2248                }
2249            }
2250            let local = k % chunk;
2251            let state = if ex.frontier.is_some() {
2252                &decoded.identity[local * nvars..(local + 1) * nvars]
2253            } else {
2254                &cur[k * nvars..(k + 1) * nvars]
2255            };
2256            if parallel && k % chunk == 0 {
2257                let started = Instant::now();
2258                let end = (k + chunk).min(states);
2259                let mut metrics = Metrics::default();
2260                let r = if let Some(coordinator) = ex.distributed {
2261                    coordinator
2262                        .expand(
2263                            plan,
2264                            machines[0].heap.store(),
2265                            if ex.frontier.is_some() {
2266                                &decoded.original
2267                            } else {
2268                                &cur[k * nvars..end * nvars]
2269                            },
2270                            &ex.seen,
2271                            ex.level - 1,
2272                            ex.poll,
2273                        )
2274                        .map(|work| {
2275                            received = Some(work);
2276                            Vec::new()
2277                        })
2278                } else {
2279                    parallel::expand_level(
2280                        plan,
2281                        machines,
2282                        if ex.frontier.is_some() {
2283                            &decoded.original
2284                        } else if ex.graph.is_some() || ex.checkpoint.is_some() {
2285                            &cur_originals[k * nvars..end * nvars]
2286                        } else {
2287                            &cur[k * nvars..end * nvars]
2288                        },
2289                        nvars,
2290                        &ex.seen,
2291                        ex.opts,
2292                        ex.checkpoint.is_some(),
2293                        ex.graph
2294                            .as_deref()
2295                            .map(graph::GraphSink::max_successors_per_unit),
2296                        ex.candidates
2297                            .as_ref()
2298                            .map(|account| (&ex.candidate_storage, account)),
2299                        ex.poll,
2300                        estimate.saturating_mul(end - k) / states.max(1),
2301                        &mut metrics,
2302                    )
2303                };
2304                let r = match r {
2305                    Ok(r) => r,
2306                    Err(error) => {
2307                        ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
2308                        return Err(error);
2309                    }
2310                };
2311                ex.metrics.conjuncts_total += metrics.conjuncts_total;
2312                ex.metrics.conjuncts_skipped += metrics.conjuncts_skipped;
2313                ex.metrics.discarded_before_intern += metrics.discarded_before_intern;
2314                expand_time += started.elapsed();
2315                expanded = if received.is_some() { None } else { Some(r) };
2316                base = k;
2317            }
2318            let Some(m) = machines.first_mut() else {
2319                return Err(Error::internal("no core machine"));
2320            };
2321            let have_expansion = expanded.is_some() || received.is_some();
2322            let mut remote_expansion = if let Some(work) = received
2323                .as_mut()
2324                .and_then(|work| work.get_mut(k - base))
2325                .and_then(Option::take)
2326            {
2327                let Some(coordinator) = ex.distributed else {
2328                    return Err(Error::internal("remote result without its coordinator"));
2329                };
2330                let started = Instant::now();
2331                let mut metrics = Metrics::default();
2332                let imported = coordinator.import(work, plan, &mut m.heap, ex.poll, &mut metrics);
2333                let imported = match imported {
2334                    Ok(imported) => imported,
2335                    Err(error) => {
2336                        ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
2337                        return Err(error);
2338                    }
2339                };
2340                ex.metrics.conjuncts_total += metrics.conjuncts_total;
2341                ex.metrics.conjuncts_skipped += metrics.conjuncts_skipped;
2342                ex.metrics.discarded_before_intern += metrics.discarded_before_intern;
2343                expand_time += started.elapsed();
2344                Some(imported)
2345            } else {
2346                None
2347            };
2348            let res = remote_expansion.as_mut().or_else(|| {
2349                expanded
2350                    .as_mut()
2351                    .and_then(|all| all.get_mut(k - base).and_then(Option::as_mut))
2352            });
2353            // Phase 1 polled the budget before each state it expanded, and
2354            // stopped before this one if it ran out.
2355            let exhausted = if have_expansion {
2356                res.is_none()
2357            } else {
2358                (ex.poll)()
2359            };
2360            if exhausted {
2361                ex.stats.left_on_queue = (states - k + ex.queued_states()) as u64;
2362                ex.stop = Some(Verdict::Budget);
2363                return Err(Error::stop());
2364            }
2365            let source = if ex.frontier.is_some() {
2366                &decoded.original[local * nvars..(local + 1) * nvars]
2367            } else if ex.graph.is_some() || ex.checkpoint.is_some() {
2368                cur_originals
2369                    .get(k * nvars..(k + 1) * nvars)
2370                    .ok_or_else(|| Error::internal("capture source original row missing"))?
2371            } else {
2372                state
2373            };
2374            m.s0.copy_from_slice(source);
2375            let level = i64::try_from(ex.level - 1).unwrap_or(i64::MAX);
2376            if res.is_none() {
2377                start_stream(m, plan, Some(source))?;
2378                m.level = level;
2379            }
2380            if let Some(r) = reservoir.as_deref_mut() {
2381                r.offer(source, level);
2382            }
2383            ex.cur_id = if ex.frontier.is_some() {
2384                decoded.ids.get(local).copied()
2385            } else {
2386                cur_ids.get(k).copied()
2387            };
2388            ex.emitted = 0;
2389            let r = match res {
2390                Some(res) => ex.commit(m, res),
2391                None => run_actions(m, ex, &plan.next, code),
2392            }
2393            .map_err(|e| generator_error(m, ex, state, e));
2394            if r.is_err()
2395                && ex
2396                    .failure
2397                    .as_ref()
2398                    .is_some_and(|failure| matches!(failure.site, Site::Next(_)))
2399            {
2400                let row_left = (states - k - 1 + ex.queued_states()) as u64;
2401                source_row(m, ex, state, row_left, true)?;
2402            }
2403            if r.is_err()
2404                && let Some(f) = &ex.failure
2405                && f.site_resumes()
2406            {
2407                // TLC's call-stack replay (`ending.rs`).
2408                if plan.effects.draws {
2409                    return Err(Error::unsupported(
2410                        "TLC's replay after a failing check, in a specification that draws (RandomElement) (M1 core)",
2411                    ));
2412                }
2413                if plan.effects.registers || plan.effects.level {
2414                    return Err(Error::unsupported(
2415                        "TLC's replay after a failing check, in a specification that uses TLCSet or TLCGet (M1 core)",
2416                    ));
2417                }
2418                // The search ends here; the graph has no part in the replay.
2419                ex.graph = None;
2420                let ordinal = ex.emitted - 1;
2421                let saved = std::mem::take(&mut m.warnings);
2422                *replayed = Some(ending::replay_after(m, ex, ordinal)?);
2423                for w in std::mem::replace(&mut m.warnings, saved) {
2424                    if parallel && !ex.warnings.contains(&w) {
2425                        ex.warnings.push(w);
2426                    } else if !parallel && !m.warnings.contains(&w) {
2427                        m.warnings.push(w);
2428                    }
2429                }
2430            }
2431            if let Some(all) = &mut expanded {
2432                all[k - base] = None;
2433            }
2434            m.heap.reset();
2435            let left = (states - k - 1 + ex.queued_states()) as u64;
2436            if let Err(e) = r {
2437                ex.stats.left_on_queue = left;
2438                return Err(e);
2439            }
2440            if ex.emitted == 0 && plan.check_deadlock {
2441                ex.stats.left_on_queue = left;
2442                ex.stop = Some(Verdict::Deadlock);
2443                ex.end = Some(End {
2444                    upto: ex.cur_id,
2445                    last: None,
2446                    expect: state.to_vec(),
2447                });
2448                return Err(Error::stop());
2449            }
2450            if let Some(id) = ex.cur_id
2451                && let Some(sink) = ex.graph.as_deref_mut()
2452                && sink.stutter(id).is_err()
2453            {
2454                ex.stats.left_on_queue = left;
2455                ex.stop = Some(Verdict::GraphStop);
2456                return Err(Error::stop());
2457            }
2458            source_row(m, ex, state, left, false)?;
2459        }
2460        level_done(ex, nvars)?;
2461        if !parallel {
2462            ex.warnings.clone_from(&machines[0].warnings);
2463        }
2464        checkpoint::boundary(ex)?;
2465        if parallel {
2466            ex.metrics.expand_time += expand_time;
2467            ex.metrics.commit_time += level_started.elapsed().saturating_sub(expand_time);
2468        }
2469        cur.clear();
2470        cur_originals.clear();
2471        cur_ids.clear();
2472        // Every source-level owner is now dead. Only the next frontier and
2473        // permanent compiled roots may cross the Store replacement boundary.
2474        drop(expanded);
2475        drop(decoded);
2476        reclaim::boundary(machines, ex, store, permanent, control)?;
2477        std::mem::swap(&mut cur, &mut ex.next);
2478        std::mem::swap(&mut cur_originals, &mut ex.next_originals);
2479        std::mem::swap(&mut cur_ids, &mut ex.next_ids);
2480        ex.advance_frontier()?;
2481    }
2482    Ok(())
2483}
2484
2485#[cfg(test)]
2486mod tests {
2487    use super::*;
2488
2489    pub(super) fn frontier_plan(store: &Arc<Store>, false_invariant: bool) -> Result<Plan, Error> {
2490        use dive_core::plan::{Action, CompileStats, Conjunct, Effects, GNode, Node};
2491
2492        let mut heap = dive_core::Heap::new(Arc::clone(store), true, false);
2493        let domain = heap.interval(0, 127);
2494        let domain = heap.intern_const(domain)?;
2495        let action = |name: &str, g| Action {
2496            name: name.into(),
2497            g,
2498            frame: 0,
2499            preset: Vec::new(),
2500        };
2501        Ok(Plan {
2502            code: Code {
2503                nodes: vec![
2504                    Node::Const(domain),
2505                    Node::Var(0),
2506                    Node::Const(Handle::FALSE),
2507                ],
2508                gnodes: vec![
2509                    GNode::AssignIn { var: 0, set: 0 },
2510                    GNode::Assign { var: 0, rhs: 1 },
2511                ],
2512                ..Code::default()
2513            },
2514            vars: vec!["x".into()],
2515            init: vec![action("Init", 0)],
2516            next: vec![action("Next", 1)],
2517            invariants: if false_invariant {
2518                vec![Check {
2519                    name: "Inv".into(),
2520                    frame: 0,
2521                    conjuncts: vec![Conjunct {
2522                        p: 2,
2523                        reads: 1,
2524                        skippable: false,
2525                        site: None,
2526                    }],
2527                }]
2528            } else {
2529                Vec::new()
2530            },
2531            constraints: Vec::new(),
2532            action_constraints: Vec::new(),
2533            implied_inits: Vec::new(),
2534            implied_actions: Vec::new(),
2535            check_deadlock: true,
2536            symmetry: None,
2537            effects: Effects::default(),
2538            view: None,
2539            stats: CompileStats::default(),
2540            bound_preset: Vec::new(),
2541            startup_assumptions: Vec::new(),
2542            startup_assumption_false: None,
2543        })
2544    }
2545
2546    #[derive(Clone, Copy, Debug)]
2547    enum FrontierFault {
2548        Corrupt,
2549        Missing,
2550        Cleanup,
2551    }
2552
2553    #[allow(
2554        clippy::unwrap_used,
2555        clippy::too_many_lines,
2556        reason = "fault mutation and real explorer outcome remain in one deterministic control"
2557    )]
2558    fn frontier_fault(
2559        tlc: bool,
2560        exact: bool,
2561        workers: usize,
2562        initial_violation: bool,
2563        fault: FrontierFault,
2564    ) {
2565        use std::fs;
2566        use std::io::{Seek, SeekFrom, Write};
2567        use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
2568
2569        static NEXT: AtomicUsize = AtomicUsize::new(0);
2570        let directory = std::env::temp_dir().join(format!(
2571            "dive-frontier-explorer-{}-{}",
2572            std::process::id(),
2573            NEXT.fetch_add(1, Ordering::Relaxed)
2574        ));
2575        fs::create_dir(&directory).unwrap();
2576        let store = Arc::new(Store::with_semantics(
2577            true,
2578            if tlc {
2579                dive_core::Semantics::tlc()
2580            } else {
2581                dive_core::Semantics::default()
2582            },
2583        ));
2584        let plan = frontier_plan(&store, initial_violation).unwrap();
2585        let calls = AtomicUsize::new(0);
2586        let injected = AtomicBool::new(false);
2587        let trigger = if initial_violation { 1 } else { 129 };
2588        let poll = || {
2589            if calls.fetch_add(1, Ordering::Relaxed) == trigger {
2590                let owned = fs::read_dir(&directory)
2591                    .unwrap()
2592                    .next()
2593                    .unwrap()
2594                    .unwrap()
2595                    .path();
2596                match fault {
2597                    FrontierFault::Corrupt => {
2598                        let mut file = fs::OpenOptions::new()
2599                            .write(true)
2600                            .open(owned.join("states"))
2601                            .unwrap();
2602                        file.seek(SeekFrom::End(-1)).unwrap();
2603                        file.write_all(&[255]).unwrap();
2604                    }
2605                    FrontierFault::Missing => fs::remove_file(owned.join("states")).unwrap(),
2606                    FrontierFault::Cleanup => {
2607                        fs::rename(&owned, directory.join("moved")).unwrap();
2608                        fs::write(owned, b"blocks directory cleanup").unwrap();
2609                    }
2610                }
2611                injected.store(true, Ordering::Relaxed);
2612            }
2613            false
2614        };
2615        let out = explore_with_storage(
2616            &plan,
2617            &store,
2618            Config {
2619                opts: Opts::default(),
2620                max_states: None,
2621                max_depth: None,
2622                workers,
2623                warn: true,
2624                sample: None,
2625            },
2626            &poll,
2627            None,
2628            None,
2629            &storage::Storage {
2630                exact,
2631                frontier_memory_bytes: Some(0),
2632                frontier_directory: Some(directory.clone()),
2633                ..storage::Storage::default()
2634            },
2635        );
2636        assert!(injected.load(Ordering::Relaxed), "{fault:?}");
2637        assert!(
2638            matches!(out.verdict, Verdict::Internal { .. }),
2639            "{fault:?}: {:?}",
2640            out.verdict
2641        );
2642        assert!(
2643            out.trace.is_none(),
2644            "corrupt storage must clear a deciding word"
2645        );
2646        let failures = &out.metrics.storage.frontier.failures;
2647        assert_ne!(failures.as_slice(), [] as [String; 0]);
2648        let expected = match fault {
2649            FrontierFault::Corrupt => "checksum",
2650            FrontierFault::Missing => "open record",
2651            FrontierFault::Cleanup => "cleanup",
2652        };
2653        assert!(
2654            failures.iter().any(|message| message.contains(expected)),
2655            "{failures:?}"
2656        );
2657        if initial_violation {
2658            assert!(
2659                out.metrics
2660                    .storage
2661                    .frontier
2662                    .deciding_event_before_failure
2663                    .as_ref()
2664                    .unwrap()
2665                    .contains("InvariantViolated")
2666            );
2667        }
2668        fs::remove_dir_all(directory).unwrap();
2669    }
2670
2671    #[test]
2672    fn corrupt_read_and_cleanup_failures_prevent_success_and_counterexample_certification() {
2673        for tlc in [false, true] {
2674            for exact in [false, true] {
2675                for workers in [1, 4, 8] {
2676                    for initial in [false, true] {
2677                        for fault in [
2678                            FrontierFault::Corrupt,
2679                            FrontierFault::Missing,
2680                            FrontierFault::Cleanup,
2681                        ] {
2682                            frontier_fault(tlc, exact, workers, initial, fault);
2683                        }
2684                    }
2685                }
2686            }
2687        }
2688    }
2689
2690    #[test]
2691    #[allow(
2692        clippy::unwrap_used,
2693        reason = "owned cancellation during final frontier validation"
2694    )]
2695    fn validation_cancellation_is_a_budget_stop_without_storage_failure_or_word() {
2696        use std::sync::atomic::{AtomicUsize, Ordering};
2697
2698        for initial_violation in [false, true] {
2699            for workers in [1, 4, 8] {
2700                let store = Arc::new(Store::new(true));
2701                let plan = frontier_plan(&store, initial_violation).unwrap();
2702                // One Init plus final validation for a deciding initial word;
2703                // otherwise 128 Init + one decoded chunk + 128 expansions.
2704                let trigger = if initial_violation { 1 } else { 257 };
2705                let calls = AtomicUsize::new(0);
2706                let poll = || calls.fetch_add(1, Ordering::Relaxed) >= trigger;
2707                let out = explore_with_storage(
2708                    &plan,
2709                    &store,
2710                    Config {
2711                        opts: Opts::default(),
2712                        max_states: None,
2713                        max_depth: None,
2714                        workers,
2715                        warn: true,
2716                        sample: None,
2717                    },
2718                    &poll,
2719                    None,
2720                    None,
2721                    &storage::Storage {
2722                        frontier_memory_bytes: Some(0),
2723                        ..storage::Storage::default()
2724                    },
2725                );
2726                assert_eq!(out.verdict, Verdict::Budget);
2727                assert!(out.trace.is_none());
2728                assert_eq!(out.metrics.storage.frontier.failures, [] as [String; 0]);
2729                assert_eq!(calls.load(Ordering::Relaxed), trigger + 1);
2730                assert_eq!(out.metrics.storage.frontier.retained_bytes, 0);
2731            }
2732        }
2733    }
2734
2735    #[test]
2736    #[allow(
2737        clippy::unwrap_used,
2738        reason = "deterministic owned budget and spilled-frontier control"
2739    )]
2740    fn budget_stop_closes_an_unread_spilled_frontier_without_validation_polls() {
2741        use std::sync::atomic::{AtomicUsize, Ordering};
2742
2743        for tlc in [false, true] {
2744            for exact in [false, true] {
2745                for workers in [1, 4, 8] {
2746                    let store = Arc::new(Store::with_semantics(
2747                        true,
2748                        if tlc {
2749                            dive_core::Semantics::tlc()
2750                        } else {
2751                            dive_core::Semantics::default()
2752                        },
2753                    ));
2754                    let plan = frontier_plan(&store, false).unwrap();
2755                    let calls = AtomicUsize::new(0);
2756                    let poll = || calls.fetch_add(1, Ordering::Relaxed) >= 128;
2757                    let out = explore_with_storage(
2758                        &plan,
2759                        &store,
2760                        Config {
2761                            opts: Opts::default(),
2762                            max_states: None,
2763                            max_depth: None,
2764                            workers,
2765                            warn: true,
2766                            sample: None,
2767                        },
2768                        &poll,
2769                        None,
2770                        None,
2771                        &storage::Storage {
2772                            exact,
2773                            frontier_memory_bytes: Some(0),
2774                            ..storage::Storage::default()
2775                        },
2776                    );
2777                    assert_eq!(out.verdict, Verdict::Budget);
2778                    assert_eq!(
2779                        out.stats,
2780                        Stats {
2781                            generated: 128,
2782                            distinct: 128,
2783                            depth: 1,
2784                            left_on_queue: 128,
2785                            initial_generated: 128
2786                        }
2787                    );
2788                    assert!(out.trace.is_none());
2789                    assert_eq!(
2790                        calls.load(Ordering::Relaxed),
2791                        129,
2792                        "cleanup must not scan/poll the unread queue"
2793                    );
2794                    assert!(out.metrics.storage.frontier.spilled_bytes > 0);
2795                    assert_eq!(out.metrics.storage.frontier.retained_bytes, 0);
2796                    assert_eq!(out.metrics.storage.frontier.failures, [] as [String; 0]);
2797                }
2798            }
2799        }
2800    }
2801
2802    #[test]
2803    fn impossible_capture_growth_is_fallible_without_modifying_retained_payload() {
2804        let mut values = vec![Handle::EMPTY];
2805        let capacity = values.capacity();
2806        assert!(capture_reserve(&mut values, usize::MAX).is_err());
2807        assert_eq!(values, [Handle::EMPTY]);
2808        assert_eq!(values.capacity(), capacity);
2809    }
2810
2811    /// An invariant whose own frame forces a thunk to a transient (a
2812    /// definition built per checked state, as `Corpus` in
2813    /// `LeastCircularSubstring`) still frees the check's transients once each
2814    /// initial state is accepted: the thunk's slot leaves the frame with the
2815    /// check. Before, every initial state's copy was held until `Init` ended.
2816    #[test]
2817    #[allow(clippy::unwrap_used, reason = "deterministic explorer control")]
2818    fn invariant_frame_thunks_do_not_hold_initial_transients() {
2819        use dive_core::plan::{Action, CompileStats, Conjunct, Effects, GNode, Node};
2820
2821        const WIDTH: usize = 64;
2822        const STATES: u64 = 128;
2823        let store = Arc::new(Store::new(false));
2824        let mut heap = dive_core::Heap::new(Arc::clone(&store), false, false);
2825        let domain = heap.interval(0, 127);
2826        let domain = heap.intern_const(domain).unwrap();
2827        let action = |name: &str, g| Action {
2828            name: name.into(),
2829            g,
2830            // A live action frame below the check's.
2831            frame: 1,
2832            preset: Vec::new(),
2833        };
2834        let plan = Plan {
2835            code: Code {
2836                nodes: vec![
2837                    Node::Const(domain),
2838                    Node::Var(0),
2839                    // A tuple built from the checked state: always transient.
2840                    Node::Tuple(vec![1; WIDTH].into_boxed_slice()),
2841                    Node::Lazy { slot: 0, body: 2 },
2842                    Node::Eq(3, 3),
2843                ],
2844                gnodes: vec![
2845                    GNode::AssignIn { var: 0, set: 0 },
2846                    GNode::Assign { var: 0, rhs: 1 },
2847                ],
2848                ..Code::default()
2849            },
2850            vars: vec!["x".into()],
2851            init: vec![action("Init", 0)],
2852            next: vec![action("Next", 1)],
2853            invariants: vec![Check {
2854                name: "Inv".into(),
2855                frame: 1,
2856                conjuncts: vec![Conjunct {
2857                    p: 4,
2858                    reads: 1,
2859                    skippable: false,
2860                    site: None,
2861                }],
2862            }],
2863            constraints: Vec::new(),
2864            action_constraints: Vec::new(),
2865            implied_inits: Vec::new(),
2866            implied_actions: Vec::new(),
2867            check_deadlock: true,
2868            symmetry: None,
2869            effects: Effects::default(),
2870            view: None,
2871            stats: CompileStats::default(),
2872            bound_preset: Vec::new(),
2873            startup_assumptions: Vec::new(),
2874            startup_assumption_false: None,
2875        };
2876        let out = explore(
2877            &plan,
2878            &store,
2879            Config {
2880                opts: Opts::default(),
2881                max_states: None,
2882                max_depth: None,
2883                workers: 1,
2884                warn: true,
2885                sample: None,
2886            },
2887            &|| false,
2888        );
2889        assert_eq!(out.verdict, Verdict::Success);
2890        assert_eq!(out.stats.distinct, STATES);
2891        assert_eq!(out.metrics.thunks, (STATES, STATES));
2892        // One state's tuple at a time, not one per initial state.
2893        let (_, handles) = out.metrics.arena_peak;
2894        assert!(
2895            handles < 4 * WIDTH,
2896            "arena peak of {handles} handles holds the initial states' check transients"
2897        );
2898    }
2899
2900    #[test]
2901    fn replay_checks_compound_values_without_hashconsing() -> Result<(), Error> {
2902        let store = Arc::new(Store::new(false));
2903        let mut heap = dive_core::Heap::new(Arc::clone(&store), false, false);
2904        let one = heap.int_from_i64(1);
2905        let two = heap.int_from_i64(2);
2906        let a = heap.tuple(&[one]);
2907        let a = heap.intern(a)?;
2908        let equal = heap.tuple(&[one]);
2909        let equal = heap.intern(equal)?;
2910        let different = heap.tuple(&[two]);
2911        let different = heap.intern(different)?;
2912        assert_ne!(a, equal, "the control must allocate distinct handles");
2913        assert!(replay_values_match(&store, &[a], &[equal]));
2914        assert!(!replay_values_match(&store, &[a], &[different]));
2915        assert!(!replay_values_match(&store, &[a], &[equal, equal]));
2916        assert!(!replay_values_match(&store, &[], &[equal]));
2917        let nested_a = heap.tuple(&[a]);
2918        let nested_a = heap.intern(nested_a)?;
2919        let nested_equal = heap.tuple(&[equal]);
2920        let nested_equal = heap.intern(nested_equal)?;
2921        let nested_different = heap.tuple(&[different]);
2922        let nested_different = heap.intern(nested_different)?;
2923        assert!(replay_values_match(&store, &[nested_a], &[nested_equal]));
2924        assert!(!replay_values_match(
2925            &store,
2926            &[nested_a],
2927            &[nested_different]
2928        ));
2929        Ok(())
2930    }
2931
2932    #[test]
2933    fn seen_set_inserts_and_grows() {
2934        let mut s = Seen::default();
2935        for k in 0..200_000u64 {
2936            assert!(s.insert(k.wrapping_mul(0x9e37_79b9_7f4a_7c15)));
2937        }
2938        assert_eq!(s.len(), 200_000);
2939        assert!(!s.insert(0));
2940        assert!(s.contains(5u64.wrapping_mul(0x9e37_79b9_7f4a_7c15)));
2941        assert!(!s.contains(7));
2942    }
2943}