Skip to main content

dive_trace/
validate.rs

1//! The checks.
2//!
3//! Every check evaluates a predicate of the model over *given* states with
4//! the dive-eval evaluator (`Model::eval`): `Init` as a state predicate on the
5//! first state, the next-state relation as an action predicate on each pair
6//! of states. Private register-dependent Init delegates to an independent
7//! single-candidate operation from empty slots. Whether a state has a
8//! successor (a deadlock ending, `ENABLED`, fairness) is the dive-eval
9//! evaluator's `ENABLED` search ([`crate::enabled`]).
10//!
11//! **Random draws.** Borrowed/warmed-model replay refuses them by name
12//! ([`RANDOM_UNSUPPORTED`]). Fresh native finite sessions can independently
13//! prove bounded `RandomElement` support by rebinding the entire source runtime
14//! per alternative. No producer RNG position or cached answer supplies proof.
15//! Register reads and writes are also refused ([`REGISTERS_UNSUPPORTED`]):
16//! the evaluator may retain values written by off-trace checker evaluations.
17//!
18//! **Runtime names.** Under TLC's value or exploration order, strings and
19//! model values compare by the order in which they were first encountered.
20//! Names interned when the model was bound have the same order as in TLC.
21//! If decoding the trace or any check interned a name after that
22//! ([`Model::has_runtime_names`]), the validator cannot know where TLC
23//! placed it, and the result, valid or invalid, becomes
24//! [`RUNTIME_NAMES_UNSUPPORTED`].
25
26use std::collections::BTreeSet;
27use std::sync::atomic::{AtomicBool, AtomicI64, AtomicU64, Ordering};
28use std::sync::{Arc, Mutex, PoisonError};
29
30use dive_eval::{AssumptionOutcome, ErrorClass, EvalError, Host, HostError, St, StateRef};
31use dive_ir::StdOp;
32use dive_model::{Model, Pred};
33use dive_value::{Ctx, Value};
34
35use crate::format::Ending;
36use crate::trace::Trace;
37
38/// Which check failed.
39#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
40#[non_exhaustive]
41pub enum Check {
42    /// The trace's shape: empty, a variable missing or extra, a value that
43    /// does not read.
44    Shape,
45    /// The claimed length differs from the number of states.
46    Length,
47    /// An `ASSUME` of the specification does not hold.
48    Assumption,
49    /// The first state does not satisfy the initial predicate.
50    Init,
51    /// A step does not satisfy the next-state relation.
52    Next,
53    /// A step's label names an action that does not hold on it.
54    Label,
55    /// A state that must be in the model violates a `CONSTRAINT`.
56    Constraint,
57    /// A step that must be in the model violates an `ACTION_CONSTRAINT`.
58    ActionConstraint,
59    /// An invariant fails before the end, so the search would have stopped
60    /// there (or, at the end, an invariant listed before the claimed one
61    /// fails).
62    Invariant,
63    /// An implied initial predicate fails on the first state.
64    ImpliedInit,
65    /// An action property fails on a step before the end.
66    ImpliedAction,
67    /// The claimed ending does not hold: the invariant or property is not
68    /// violated, or the model has no such invariant or property.
69    Ending,
70    /// A temporal conjunct of the behavior specification is false.
71    Fairness,
72    /// A claimed temporal property holds, or a violated property was omitted.
73    Temporal,
74}
75
76impl Check {
77    /// A stable name for reports.
78    #[must_use]
79    pub fn name(self) -> &'static str {
80        match self {
81            Self::Shape => "shape",
82            Self::Length => "length",
83            Self::Assumption => "assumption",
84            Self::Init => "init",
85            Self::Next => "next",
86            Self::Label => "label",
87            Self::Constraint => "constraint",
88            Self::ActionConstraint => "action-constraint",
89            Self::Invariant => "invariant",
90            Self::ImpliedInit => "implied-init",
91            Self::ImpliedAction => "implied-action",
92            Self::Ending => "ending",
93            Self::Fairness => "fairness",
94            Self::Temporal => "temporal",
95        }
96    }
97}
98
99/// The first check a trace fails.
100#[derive(Clone, Debug, PartialEq, Eq)]
101pub struct Failure {
102    /// The state (0-based) the check is about; for a step, the state it
103    /// leads to.
104    pub state: usize,
105    /// The check.
106    pub check: Check,
107    /// What failed, precisely enough to file as a bug.
108    pub detail: String,
109}
110
111/// The validator's verdict.
112#[derive(Clone, Debug, PartialEq, Eq)]
113#[non_exhaustive]
114pub enum Validation {
115    /// Every check passed: the trace is a behavior of the specification and
116    /// ends as claimed.
117    Valid,
118    /// A check failed.
119    Invalid(Failure),
120    /// Every check that could be made passed, but part of the claim cannot
121    /// be checked independently. The text names it. Never a verdict.
122    Unsupported(String),
123}
124
125impl Validation {
126    /// Whether the trace validated.
127    #[must_use]
128    pub fn is_valid(&self) -> bool {
129        matches!(self, Self::Valid)
130    }
131
132    /// `valid`, `invalid` or `unsupported`.
133    #[must_use]
134    pub fn kind(&self) -> &'static str {
135        match self {
136            Self::Valid => "valid",
137            Self::Invalid(_) => "invalid",
138            Self::Unsupported(_) => "unsupported",
139        }
140    }
141}
142
143/// The verdict with what the validator noticed along the way.
144#[derive(Clone, Debug, PartialEq, Eq)]
145pub struct Report {
146    /// The verdict.
147    pub validation: Validation,
148    /// Remarks: labels that could not be checked, how a TLC document was
149    /// read. They never change the verdict.
150    pub notes: Vec<String>,
151    /// The number of states in the trace.
152    pub length: usize,
153}
154
155/// Actual progress before cooperative validation interruption.
156#[derive(Clone, Debug, PartialEq, Eq)]
157pub struct ValidationProgress {
158    /// Completed checks in this validation invocation, not exploration work.
159    pub checks_passed: u64,
160    /// Zero-based supplied state position, when known.
161    pub state: Option<usize>,
162    /// The check that was interrupted, when known.
163    pub check: Option<Check>,
164}
165
166/// A controlled validation did not produce a validation report.
167///
168/// The driver interprets the opaque evaluator interruption. This crate knows
169/// neither resource budgets nor the authority that requested interruption.
170#[derive(Clone, Debug, PartialEq, Eq)]
171#[non_exhaustive]
172pub enum ValidationRunError {
173    /// A typed host interruption, never an invalid or unsupported trace.
174    Interrupted {
175        /// Original evaluator transport, retaining its opaque owner identity.
176        error: EvalError,
177        /// Actual progress in this invocation.
178        progress: ValidationProgress,
179    },
180    /// Allocation or evaluator resource exhaustion; no validation verdict exists.
181    ResourceLimit {
182        /// Original resource error, not a semantic capability refusal.
183        error: EvalError,
184        /// Actual progress before validation could not complete.
185        progress: ValidationProgress,
186    },
187    /// An internal evaluator failure aborted validation, rather than refuting it.
188    EvaluationFailure {
189        /// Original internal evaluator error.
190        error: EvalError,
191        /// Work completed before the failure.
192        progress: ValidationProgress,
193    },
194    /// The fresh source binder reported an intrinsic internal binding failure.
195    BindingFailure {
196        /// Original typed binding error; never parsed from its display text.
197        error: dive_model::BindError,
198        /// Progress before a private runtime could be constructed.
199        progress: ValidationProgress,
200    },
201    /// The isolated validation thread could not run or did not return.
202    ThreadFailure(String),
203    /// Another thread owns the evaluator's control registration.
204    ControlConflict(dive_eval::HostControlConflict),
205}
206
207impl std::fmt::Display for ValidationRunError {
208    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
209        match self {
210            Self::Interrupted { error, .. }
211            | Self::ResourceLimit { error, .. }
212            | Self::EvaluationFailure { error, .. } => error.fmt(f),
213            Self::BindingFailure { error, .. } => error.fmt(f),
214            Self::ThreadFailure(message) => f.write_str(message),
215            Self::ControlConflict(error) => error.fmt(f),
216        }
217    }
218}
219impl std::error::Error for ValidationRunError {}
220
221/// The reason given for a deadlock ending whose `ENABLED` cannot be decided.
222pub const DEADLOCK_UNSUPPORTED: &str = "deadlock: ENABLED of the next-state relation could not be decided on the last state; every other check passed";
223
224/// The reason given when the trace or a check created a name after the
225/// model was bound, under an order where names compare by encounter.
226pub const RUNTIME_NAMES_UNSUPPORTED: &str = "runtime string encounter order: decoding the trace or checking it created a string or model value that was not interned when the model was bound, and its order relative to other names depends on evaluations outside the trace";
227
228/// The reason given when a check draws a random value.
229pub const RANDOM_UNSUPPORTED: &str = "a random draw: the value depends on the checking run's stream position, which only the successor generator determines, so the independent validator cannot check it";
230
231/// The reason given when a check accesses search-dependent TLC registers.
232pub const REGISTERS_UNSUPPORTED: &str = "TLCGet/TLCSet registers: their contents depend on evaluations outside the trace, so the independent validator cannot read or write them";
233
234/// Composition outside independent replay's pure, complete, deterministic-tail slice.
235pub const COMPOSITION_UNSUPPORTED: &str = "action composition: independent replay requires TLA mode, pure finite complete intermediates and at most one complete tail successor";
236
237/// What stopped a run early.
238pub(crate) enum Stop {
239    Invalid(Failure),
240    Unsupported(String),
241    Interrupted {
242        error: EvalError,
243        state: Option<usize>,
244        check: Option<Check>,
245    },
246    ControlConflict(dive_eval::HostControlConflict),
247}
248
249impl Stop {
250    fn at(self, state: Option<usize>, check: Check) -> Self {
251        match self {
252            Self::Interrupted { error, .. } => Self::Interrupted {
253                error,
254                state,
255                check: Some(check),
256            },
257            other => other,
258        }
259    }
260}
261
262impl From<Stop> for Validation {
263    fn from(s: Stop) -> Self {
264        match s {
265            Stop::Invalid(f) => Self::Invalid(f),
266            Stop::Unsupported(u) => Self::Unsupported(u),
267            Stop::Interrupted { .. } => Self::Unsupported(
268                "the caller interrupted validation; use validate_controlled for typed transport"
269                    .into(),
270            ),
271            Stop::ControlConflict(error) => Self::Unsupported(error.to_string()),
272        }
273    }
274}
275
276/// What the end of the trace must show.
277enum Goal {
278    Invariant(usize),
279    InvariantError(usize, String),
280    ImpliedInit(usize),
281    ImpliedAction(usize),
282    Deadlock,
283    Behavior,
284    Liveness(&'static str),
285    ErrorEnd(&'static str),
286    TemporalStateError,
287    NextStateError,
288}
289
290/// One validation run. `passed` counts the checks passed, in order: the
291/// TLC reader uses it to compare interpretations of a lossy document.
292enum AssumptionControl {
293    Unit,
294    Cooperative,
295}
296
297/// Which finite operation a trusted caller selected; never read from a document.
298#[derive(Clone, Copy, Debug, PartialEq, Eq)]
299pub(crate) enum FiniteScope {
300    /// An ordinary checking word: a deadlock has no successor.
301    Behavior,
302    /// A sampled finite behavior whose every row passed the safety checks.
303    Sample,
304    /// A simulation deadlock: no successor satisfies the model's constraints.
305    SampledDeadlock,
306}
307
308pub(crate) struct Run<'a> {
309    model: &'a Model,
310    host: Arc<TraceHost>,
311    /// The host installed before the run, restored after it.
312    inner: Option<Arc<dyn Host>>,
313    pub(crate) passed: u64,
314    pub(crate) notes: BTreeSet<String>,
315    private_init: bool,
316    pub(crate) init_incomplete: bool,
317    endpoint_prepared: bool,
318    endpoint_exception: Option<(EvalError, Option<usize>, Check)>,
319    control: Option<Arc<dyn dive_eval::HostControl>>,
320    /// Finite-mode replay keeps its existing control during ASSUME checks.
321    assumption_control: AssumptionControl,
322    /// Trusted operation selection, never read from a serialized document.
323    finite_scope: FiniteScope,
324}
325
326impl<'a> Run<'a> {
327    pub(crate) fn new(model: &'a Model) -> Self {
328        let inner = model.evaluator.host();
329        let host = Arc::new(TraceHost {
330            level: AtomicI64::new(0),
331            inner: inner.clone(),
332            drew: Mutex::new(None),
333            any: AtomicBool::new(false),
334            registers: AtomicBool::new(false),
335            composition: AtomicBool::new(false),
336            register_used: AtomicBool::new(false),
337            startup: AtomicBool::new(false),
338            next_error: AtomicBool::new(false),
339            effect: Mutex::new(None),
340            private: false,
341            run_config: Mutex::new(None),
342            cache_domain: next_cache_domain(),
343            choices: None,
344            predicate_init: AtomicBool::new(false),
345            predicate_next: AtomicBool::new(false),
346            inputs: None,
347        });
348        model.evaluator.set_host(host.clone());
349        Self {
350            model,
351            host,
352            inner,
353            passed: 0,
354            notes: BTreeSet::new(),
355            private_init: false,
356            init_incomplete: false,
357            endpoint_prepared: false,
358            endpoint_exception: None,
359            control: None,
360            assumption_control: AssumptionControl::Unit,
361            finite_scope: FiniteScope::Behavior,
362        }
363    }
364
365    pub(crate) fn private(model: &'a Model, host: Arc<TraceHost>, initial: bool) -> Self {
366        let inner = model.evaluator.replace_host(Some(host.clone()));
367        let notes = if host.inputs.is_some() {
368            BTreeSet::from(["External inputs are explicit assumptions. Fresh source replay verifies their ordered use; it does not authenticate past host contents.".into()])
369        } else {
370            BTreeSet::new()
371        };
372        Self {
373            model,
374            host,
375            inner,
376            passed: 0,
377            notes,
378            private_init: initial,
379            init_incomplete: false,
380            endpoint_prepared: false,
381            endpoint_exception: None,
382            control: None,
383            assumption_control: AssumptionControl::Unit,
384            finite_scope: FiniteScope::Behavior,
385        }
386    }
387
388    /// Validates `trace`.
389    // Plain document/session callers have a closed result type. Controlled
390    // callers bypass this conversion through validate_result, including label,
391    // ENABLED/fairness and final refusal handling.
392    pub(crate) fn validate(&mut self, trace: &Trace) -> Validation {
393        self.validate_result(trace).unwrap_or_else(Validation::from)
394    }
395
396    fn validate_result(&mut self, trace: &Trace) -> Result<Validation, Stop> {
397        let v = match self.run(trace) {
398            Ok(None) => Validation::Valid,
399            Ok(Some(why)) => Validation::Unsupported(why),
400            Err(stop @ (Stop::Interrupted { .. } | Stop::ControlConflict(_))) => return Err(stop),
401            Err(stop) => stop.into(),
402        };
403        let v = self.refusal().map_or(v, Validation::Unsupported);
404        if v == Validation::Valid {
405            self.poll(None, None)?;
406        }
407        Ok(v)
408    }
409
410    fn poll(&self, state: Option<usize>, check: Option<Check>) -> Result<(), Stop> {
411        if let Some(control) = &self.control {
412            control.check().map_err(|interrupted| Stop::Interrupted {
413                error: EvalError::interrupted(interrupted),
414                state,
415                check,
416            })?;
417        }
418        Ok(())
419    }
420
421    /// Why the run's verdict cannot stand, whatever it is: a check drew a
422    /// random value, accessed registers, or a name was created after binding.
423    pub(crate) fn refusal(&self) -> Option<String> {
424        if let Some(feature) = self.model.evaluator.external_input_refusal() {
425            return Some(feature);
426        }
427        if self.host.inputs.is_none() && !self.model.evaluator.options().host_access.is_empty() {
428            return Some(
429                "external inputs require a fresh Session with explicit recorded assumptions".into(),
430            );
431        }
432        if let Some(error) = self
433            .host
434            .inputs
435            .as_ref()
436            .and_then(|inputs| inputs.failure())
437        {
438            return Some(error.message);
439        }
440        if let Some(reason) = self
441            .host
442            .choices
443            .as_ref()
444            .and_then(|choices| choices.refusal())
445        {
446            return Some(reason);
447        }
448        if let Some(effect) = self
449            .host
450            .effect
451            .lock()
452            .unwrap_or_else(PoisonError::into_inner)
453            .clone()
454        {
455            return Some(effect);
456        }
457        if self.host.any.load(Ordering::Relaxed) {
458            let op = self
459                .host
460                .drew
461                .lock()
462                .unwrap_or_else(PoisonError::into_inner)
463                .map_or_else(|| "a random operator".to_owned(), StdOp::qualified_name);
464            return Some(format!("{op}: {RANDOM_UNSUPPORTED}"));
465        }
466        if self.host.registers.load(Ordering::Relaxed) {
467            return Some(REGISTERS_UNSUPPORTED.to_owned());
468        }
469        if self.host.composition.load(Ordering::Relaxed) {
470            return Some(COMPOSITION_UNSUPPORTED.to_owned());
471        }
472        self.model
473            .has_runtime_names()
474            .then(|| RUNTIME_NAMES_UNSUPPORTED.to_owned())
475    }
476
477    #[allow(
478        clippy::too_many_lines,
479        reason = "every trace check, in the order the search makes them"
480    )]
481    fn run(&mut self, trace: &Trace) -> Result<Option<String>, Stop> {
482        self.poll(None, None)?;
483        let m = self.model;
484        if matches!(
485            trace.ending,
486            Ending::TemporalStateError { .. }
487                | Ending::TemporalSourceError { .. }
488                | Ending::NextStateError { .. }
489                | Ending::ViewSourceError { .. }
490                | Ending::CandidateStateError { .. }
491                | Ending::PartialNext { .. }
492                | Ending::PartialInit { .. }
493        ) && (!self.host.private || !self.endpoint_prepared)
494        {
495            return Err(Stop::Unsupported(
496                "temporal error endpoint requires a privately reconstructed source session".into(),
497            ));
498        }
499        let n = trace.states.len();
500        if n == 0 {
501            return Err(invalid(0, Check::Shape, "the trace has no states"));
502        }
503        if trace.labels.len() != n {
504            return Err(invalid(
505                0,
506                Check::Shape,
507                "the trace has a label list of the wrong length",
508            ));
509        }
510        if let Some(len) = trace.length
511            && len != n
512        {
513            return Err(invalid(
514                n - 1,
515                Check::Length,
516                format!("the trace claims {len} states but has {n}"),
517            ));
518        }
519        let vars = m.ir.vars().len();
520        for (k, s) in trace.states.iter().enumerate() {
521            if k.is_multiple_of(1024) {
522                self.poll(Some(k), Some(Check::Shape))?;
523            }
524            if s.len() != vars || s.iter().any(Option::is_none) {
525                return Err(invalid(
526                    k,
527                    Check::Shape,
528                    "the state does not assign every variable",
529                ));
530            }
531            crate::trace::validate_state_names(m, s).map_err(Stop::Unsupported)?;
532        }
533        let named_lasso = !trace.properties.is_empty();
534        if named_lasso {
535            self.host.startup.store(false, Ordering::Relaxed);
536            self.prepare_periodic(&trace.ending, &trace.properties)?;
537            self.host
538                .startup
539                .store(self.private_init, Ordering::Relaxed);
540        }
541        self.assumptions()?;
542        if self.private_init {
543            self.host
544                .startup
545                .store(self.private_init, Ordering::Relaxed);
546        }
547        // The candidate endpoint separately regenerates the final row on a
548        // fresh terminal runtime. Ordinary checks apply to its source prefix;
549        // shape/name/length checks above still cover the entire supplied word.
550        let last = if matches!(trace.ending, Ending::CandidateStateError { .. }) {
551            n.checked_sub(2).ok_or_else(|| {
552                invalid(
553                    0,
554                    Check::Shape,
555                    "candidate error requires a complete source prefix and terminal row",
556                )
557            })?
558        } else {
559            n - 1
560        };
561        let goal = self.goal(&trace.ending, last)?;
562        let terminal_before_exclusion = matches!(
563            goal,
564            Goal::Invariant(_)
565                | Goal::InvariantError(..)
566                | Goal::ImpliedInit(_)
567                | Goal::ImpliedAction(_)
568        );
569        let behavior =
570            matches!(goal, Goal::Behavior) && matches!(self.finite_scope, FiniteScope::Behavior);
571        for k in 0..=last {
572            if k.is_multiple_of(1024) {
573                self.poll(Some(k), None)?;
574            }
575            if let Some(choices) = &self.host.choices {
576                choices.prefer(&trace.states[k]);
577            }
578            let here = St::state(trace.states[k].clone());
579            let step =
580                (k > 0).then(|| St::action(trace.states[k - 1].clone(), trace.states[k].clone()));
581            match &step {
582                None => {
583                    // Init uses startup level 0; generated-state predicates
584                    // keep the separate Clear context in `here` (level 1).
585                    if self.private_init {
586                        // Ordered source construction and finite native choices
587                        // cannot share startup register authority. The existing
588                        // direct scalar domain-membership proof remains a fast path.
589                        self.host.startup.store(false, Ordering::Relaxed);
590                        let operation = if self.host.register_used.load(Ordering::Relaxed) {
591                            self.host.startup.store(true, Ordering::Relaxed);
592                            crate::initial::check(m, &trace.states[0], self.control.as_deref())
593                        } else {
594                            match crate::initial::random_check(m, &trace.states[0]) {
595                                Ok(Some(member)) => Ok(Some(member)),
596                                Ok(None) => crate::initial::check(
597                                    m,
598                                    &trace.states[0],
599                                    self.control.as_deref(),
600                                ),
601                                Err(error) => Err(error),
602                            }
603                        };
604                        let member = match operation {
605                            Ok(Some(member)) => member,
606                            Ok(None) => {
607                                self.init_incomplete = !self
608                                    .host
609                                    .choices
610                                    .as_ref()
611                                    .is_some_and(|choices| choices.drew());
612                                let error = EvalError::unsupported(crate::initial::UNSUPPORTED);
613                                return Err(self.evaluation_refusal(&error, Some(0), Check::Init));
614                            }
615                            Err(error) => {
616                                if error.class() == ErrorClass::Eval {
617                                    return Err(Stop::Unsupported(format!(
618                                        "independent Init source evaluation fails: {error}"
619                                    )));
620                                }
621                                return Err(self.evaluation_refusal(&error, Some(0), Check::Init));
622                            }
623                        };
624                        if !member {
625                            return Err(invalid(
626                                0,
627                                Check::Init,
628                                "the first state is outside the independent Init relation",
629                            ));
630                        }
631                        self.passed += 1;
632                    } else {
633                        self.host.predicate_init.store(true, Ordering::Relaxed);
634                        let initial = St::initial(trace.states[0].clone());
635                        for init in &m.init {
636                            self.require(&init.pred, &initial, 0, Check::Init, || {
637                                format!(
638                                    "the initial predicate {} is false in the first state",
639                                    m.location(&init.pred)
640                                )
641                            })?;
642                        }
643                    }
644                    self.host.startup.store(false, Ordering::Relaxed);
645                    self.host.predicate_init.store(false, Ordering::Relaxed);
646                }
647                Some(step) => {
648                    if !(named_lasso && trace.states[k - 1] == trace.states[k]) {
649                        // Otherwise the implicit full-state stuttering closure.
650                        self.next(step, k, "the step into this state")?;
651                    }
652                    if let Some(label) = &trace.labels[k] {
653                        self.label(&label.name, step, k)?;
654                    }
655                }
656            }
657            if behavior {
658                continue;
659            }
660            let is_last = k == last;
661            let constrained_step = step
662                .as_ref()
663                .filter(|_| !(named_lasso && trace.states[k - 1] == trace.states[k]));
664            self.constraints(
665                &here,
666                constrained_step,
667                k,
668                is_last && terminal_before_exclusion,
669            )?;
670            match (&goal, is_last) {
671                (Goal::Invariant(i), true) => {
672                    self.claimed(&m.invariants, *i, &here, k, Check::Invariant, "invariant")?;
673                }
674                (Goal::InvariantError(i, ec), true) => {
675                    self.invariant_error(*i, ec, &here, k)?;
676                    // An invariant evaluation error decides before implied
677                    // properties or later invariants are checked.
678                    return Ok(None);
679                }
680                _ => {
681                    for inv in &m.invariants {
682                        self.require(&inv.pred, &here, k, Check::Invariant, || {
683                            format!("invariant {} is false here, so the search would have stopped at this state", inv.name)
684                        })?;
685                    }
686                }
687            }
688            match (&goal, &step, is_last) {
689                (Goal::Invariant(_), _, true) => {}
690                (Goal::ImpliedInit(i), None, _) => {
691                    self.claimed(
692                        &m.implied_inits,
693                        *i,
694                        &here,
695                        k,
696                        Check::ImpliedInit,
697                        "property",
698                    )?;
699                }
700                (Goal::ImpliedAction(i), Some(step), true) => {
701                    self.claimed(
702                        &m.implied_actions,
703                        *i,
704                        step,
705                        k,
706                        Check::ImpliedAction,
707                        "property",
708                    )?;
709                }
710                (_, None, _) => {
711                    for p in &m.implied_inits {
712                        self.require(&p.pred, &here, k, Check::ImpliedInit, || {
713                            format!("property {} is false in the first state", p.name)
714                        })?;
715                    }
716                }
717                (_, Some(step), _) => {
718                    for p in &m.implied_actions {
719                        self.require(&p.pred, step, k, Check::ImpliedAction, || {
720                            format!("action property {} is false on this step, so the search would have stopped here", p.name)
721                        })?;
722                    }
723                }
724            }
725        }
726        if named_lasso {
727            self.periodic_end(trace)?;
728            return Ok(None);
729        }
730        if let Ending::Lasso { back_to } = trace.ending {
731            if m.view.is_some() {
732                // TLC closes the loop on the VIEW's value, not the state's:
733                // the last state's successor only has the same view as the
734                // state it loops to (Examples' MCDistributedReplicatedLog).
735                self.notes.insert("VIEW: TLC's loop closes on the view, not the state; the loop step is not checked".to_owned());
736            } else {
737                let step = St::action(trace.states[last].clone(), trace.states[back_to].clone());
738                let what = format!(
739                    "the loop from the last state back to state {} (numbered from 1)",
740                    back_to + 1
741                );
742                self.next(&step, last, &what)?;
743            }
744        }
745        Ok(match goal {
746            Goal::Deadlock
747                if self.finite_scope == FiniteScope::SampledDeadlock
748                    && !(m.constraints.is_empty() && m.action_constraints.is_empty()) =>
749            {
750                return self.sampled_deadlock(&trace.states[last], last);
751            }
752            Goal::Deadlock => {
753                if let Some(next) = &m.next {
754                    match crate::enabled::enabled(m, next, None, &trace.states[last]) {
755                        Ok(false) => None,
756                        Ok(true) => {
757                            return Err(invalid(
758                                last,
759                                Check::Ending,
760                                "the claimed deadlock has a successor",
761                            ));
762                        }
763                        Err(e) => {
764                            if let crate::enabled::EnabledError::Interrupted(error) = e {
765                                return Err(refused(&error).at(Some(last), Check::Ending));
766                            }
767                            self.notes.insert(e.to_string());
768                            Some(DEADLOCK_UNSUPPORTED.to_owned())
769                        }
770                    }
771                } else {
772                    Some(DEADLOCK_UNSUPPORTED.to_owned())
773                }
774            }
775            // The fallible entrypoint separately reconstructs the program
776            // before this path validation and replays it afterward.
777            Goal::TemporalStateError
778            | Goal::Invariant(_)
779            | Goal::InvariantError(..)
780            | Goal::ImpliedInit(_)
781            | Goal::ImpliedAction(_)
782            | Goal::Behavior
783            | Goal::NextStateError => None,
784            Goal::Liveness(why) | Goal::ErrorEnd(why) => Some(why.to_owned()),
785        })
786    }
787
788    pub(crate) fn prepare_periodic(
789        &mut self,
790        ending: &Ending,
791        properties: &[String],
792    ) -> Result<(), Stop> {
793        if !matches!(ending, Ending::Lasso { .. } | Ending::Stuttering) {
794            return Err(invalid(
795                0,
796                Check::Ending,
797                "temporal property names require a periodic ending",
798            ));
799        }
800        if self.model.view.is_some()
801            || self.model.symmetry_reduction.is_some()
802            || (self.model.symmetry.is_some() && !self.model.unreduced_symmetry_liveness())
803        {
804            return Err(Stop::Unsupported(
805                "periodic validation under VIEW or SYMMETRY needs concrete closing-state evidence"
806                    .into(),
807            ));
808        }
809        let mut names = BTreeSet::new();
810        let mut declared = BTreeSet::new();
811        if self
812            .model
813            .property_claims()
814            .iter()
815            .any(|p| !declared.insert(&p.name))
816        {
817            return Err(Stop::Unsupported(
818                "split temporal properties with ambiguous repeated names".into(),
819            ));
820        }
821        let mut previous = None;
822        for name in properties {
823            if name.is_empty() || !names.insert(name) {
824                return Err(invalid(
825                    0,
826                    Check::Ending,
827                    "empty or repeated temporal property name",
828                ));
829            }
830            let Some(index) = self
831                .model
832                .property_claims()
833                .iter()
834                .position(|p| p.name == *name)
835            else {
836                return Err(invalid(
837                    0,
838                    Check::Ending,
839                    format!("the model has no temporal property named `{name}`"),
840                ));
841            };
842            if previous.is_some_and(|prior| index <= prior) {
843                return Err(invalid(
844                    0,
845                    Check::Ending,
846                    "temporal property names are not in configured order",
847                ));
848            }
849            previous = Some(index);
850        }
851        let check = |pred: &Pred| {
852            crate::temporal::check_periodic_context(self.model, pred).map_err(|error| match error {
853                crate::temporal::TemporalError::Interrupted(error) => refused(&error),
854                other => Stop::Unsupported(other.to_string()),
855            })
856        };
857        for init in &self.model.init {
858            check(&init.pred)?;
859        }
860        if let Some(next) = &self.model.next {
861            check(next)?;
862        }
863        for p in self
864            .model
865            .constraints
866            .iter()
867            .chain(&self.model.action_constraints)
868            .chain(&self.model.invariants)
869            .chain(&self.model.implied_inits)
870            .chain(&self.model.implied_actions)
871        {
872            check(&p.pred)?;
873        }
874        for &d in &self.model.assumptions {
875            check(&Pred::new(
876                self.model.ir.def(d).body,
877                self.model.evaluator.scope(d).map_err(|error| {
878                    if error.class() == ErrorClass::Interrupted {
879                        refused(&error).at(None, Check::Assumption)
880                    } else {
881                        Stop::Unsupported(error.to_string())
882                    }
883                })?,
884            ))?;
885        }
886        Ok(())
887    }
888
889    fn periodic_end(&mut self, trace: &Trace) -> Result<(), Stop> {
890        let last = trace.states.len() - 1;
891        let back = match trace.ending {
892            Ending::Lasso { back_to } => back_to,
893            Ending::Stuttering => last,
894            _ => return Err(Stop::Unsupported("internal nonperiodic ending".into())),
895        };
896        let stutter = trace.states[last] == trace.states[back];
897        let step = St::action(trace.states[last].clone(), trace.states[back].clone());
898        if !stutter {
899            self.next(&step, last, "the closing step")?;
900            for c in &self.model.action_constraints {
901                self.require(&c.pred, &step, last, Check::ActionConstraint, || {
902                    format!("ACTION_CONSTRAINT {} is false on the closing step", c.name)
903                })?;
904            }
905        }
906        for p in &self.model.implied_actions {
907            self.require(&p.pred, &step, last, Check::ImpliedAction, || {
908                format!("action property {} is false on the closing step", p.name)
909            })?;
910        }
911        for p in &self.model.temporals {
912            if !self.temporal_truth(&p.pred, trace, back)? {
913                return Err(invalid(
914                    0,
915                    Check::Fairness,
916                    format!(
917                        "behavior temporal conjunct {} is false on this word",
918                        p.name
919                    ),
920                ));
921            }
922            self.passed += 1;
923        }
924        for p in self.model.property_claims() {
925            let holds = self.temporal_truth(&p.pred, trace, back)?;
926            let claimed = trace.properties.contains(&p.name);
927            if claimed && holds {
928                return Err(invalid(
929                    0,
930                    Check::Temporal,
931                    format!("temporal property {} holds on this word", p.name),
932                ));
933            }
934            if !claimed && !holds {
935                return Err(invalid(
936                    0,
937                    Check::Temporal,
938                    format!("violated temporal property {} was omitted", p.name),
939                ));
940            }
941            self.passed += 1;
942        }
943        Ok(())
944    }
945
946    fn temporal_truth(&self, pred: &Pred, trace: &Trace, back: usize) -> Result<bool, Stop> {
947        use crate::temporal::TemporalError;
948        match crate::temporal::evaluate_lasso(self.model, pred, &trace.states, back) {
949            Ok(values) => values
950                .first()
951                .copied()
952                .ok_or_else(|| Stop::Unsupported("internal empty temporal truth vector".into())),
953            Err(TemporalError::Invalid(detail)) => Err(invalid(0, Check::Temporal, detail)),
954            Err(TemporalError::Unsupported(detail)) => Err(Stop::Unsupported(detail)),
955            Err(TemporalError::Interrupted(error)) => {
956                Err(refused(&error).at(None, Check::Temporal))
957            }
958        }
959    }
960
961    fn goal(&self, ending: &Ending, last: usize) -> Result<Goal, Stop> {
962        let m = self.model;
963        let find =
964            |list: &[dive_model::Named], name: &str| list.iter().position(|n| n.name == name);
965        Ok(match ending {
966            Ending::Invariant(name) => Goal::Invariant(find(&m.invariants, name).ok_or_else(|| {
967                invalid(last, Check::Ending, format!("the model has no invariant named `{name}`"))
968            })?),
969            Ending::InvariantError { name, ec } => Goal::InvariantError(
970                find(&m.invariants, name).ok_or_else(|| {
971                    invalid(last, Check::Ending, format!("the model has no invariant named `{name}`"))
972                })?,
973                ec.clone(),
974            ),
975            Ending::Property(name) if last == 0 => {
976                Goal::ImpliedInit(find(&m.implied_inits, name).ok_or_else(|| {
977                    invalid(
978                        last,
979                        Check::Ending,
980                        format!("the model has no implied initial predicate named `{name}`, and a one-state trace cannot violate an action property"),
981                    )
982                })?)
983            }
984            Ending::Property(name) => Goal::ImpliedAction(find(&m.implied_actions, name).ok_or_else(|| {
985                invalid(last, Check::Ending, format!("the model has no action property named `{name}`"))
986            })?),
987            Ending::Deadlock => {
988                if !m.settings.check_deadlock {
989                    return Err(invalid(
990                        last,
991                        Check::Ending,
992                        "the model does not check for deadlock (CHECK_DEADLOCK FALSE or -deadlock)",
993                    ));
994                }
995                Goal::Deadlock
996            }
997            Ending::Behavior => Goal::Behavior,
998            Ending::TemporalStateError { .. } => Goal::TemporalStateError,
999            Ending::NextStateError { .. } | Ending::TemporalSourceError { .. }
1000                | Ending::ViewSourceError { .. }
1001                    | Ending::CandidateStateError { .. } | Ending::PartialNext { .. } | Ending::PartialInit { .. } => Goal::NextStateError,
1002            Ending::Lasso { back_to } => {
1003                if *back_to > last {
1004                    return Err(invalid(last, Check::Shape, format!("the lasso loops back to state {back_to}, past the end")));
1005                }
1006                Goal::Liveness("liveness: the steps and the loop back (unless noted) were checked, but named temporal-property claims are missing")
1007            }
1008            Ending::Stuttering => Goal::Liveness("liveness: the steps were checked, but named temporal-property claims are missing"),
1009            Ending::Assertion | Ending::Error { .. } => Goal::ErrorEnd("an error while expanding the last state: the steps were checked, but re-raising the error needs the successor generator, which the independent validator does not have"),
1010        })
1011    }
1012
1013    fn assumptions(&mut self) -> Result<(), Stop> {
1014        // Binding and ASSUME remain explicit uninterruptible units. This
1015        // thread-owned frame restores control on every return/unwind without
1016        // disabling another evaluator or any worker's installed capability.
1017        let _assumptions = if self.control.is_some()
1018            && !self.endpoint_prepared
1019            && matches!(self.assumption_control, AssumptionControl::Unit)
1020        {
1021            Some(
1022                self.model
1023                    .evaluator
1024                    .host_control(None)
1025                    .map_err(Stop::ControlConflict)?,
1026            )
1027        } else {
1028            None
1029        };
1030        match self.model.check_assumptions() {
1031            AssumptionOutcome::AllTrue => {
1032                self.passed += 1;
1033                Ok(())
1034            }
1035            AssumptionOutcome::False { message, .. } => Err(invalid(0, Check::Assumption, message)),
1036            AssumptionOutcome::Error { error, message, .. } => match error.class() {
1037                ErrorClass::Eval => Err(invalid(0, Check::Assumption, message)),
1038                _ => Err(self.evaluation_refusal(&error, None, Check::Assumption)),
1039            },
1040        }
1041    }
1042
1043    fn next(&mut self, step: &St, k: usize, what: &str) -> Result<(), Stop> {
1044        let m = self.model;
1045        let Some(next) = &m.next else {
1046            return Err(invalid(
1047                k,
1048                Check::Next,
1049                "the model has no next-state relation, so a trace has one state",
1050            ));
1051        };
1052        if let Some(choices) = &self.host.choices
1053            && m.ir
1054                .node(next.expr)
1055                .effects
1056                .intersects(dive_ir::Effects::IMPURE.union(dive_ir::Effects::OPEN))
1057        {
1058            let (StateRef::Vals(source), StateRef::Vals(target)) = (&step.s0, &step.s1) else {
1059                return Err(Stop::Unsupported(
1060                    "independent random Next needs complete source/target rows".into(),
1061                ));
1062            };
1063            self.host
1064                .level
1065                .store(i64::try_from(k).unwrap_or(i64::MAX), Ordering::Relaxed);
1066            match crate::initial::next(m, source, target, choices) {
1067                Ok(Some(true)) => {
1068                    self.passed += 1;
1069                    return Ok(());
1070                }
1071                Ok(Some(false)) => {
1072                    return Err(invalid(
1073                        k,
1074                        Check::Next,
1075                        "the step is outside the independent ordered Next relation",
1076                    ));
1077                }
1078                Ok(None) => {}
1079                Err(error) => return Err(self.evaluation_refusal(&error, Some(k), Check::Next)),
1080            }
1081        }
1082        // Structural decline happens before evaluation. This older predicate
1083        // path may retain different action LET/argument caches, so it may not
1084        // grant random support after the independent operation declined.
1085        self.host.predicate_next.store(true, Ordering::Relaxed);
1086        let result = self.require(next, step, k, Check::Next, || {
1087            format!(
1088                "{what} does not satisfy the next-state relation {}",
1089                m.location(next)
1090            )
1091        });
1092        self.host.predicate_next.store(false, Ordering::Relaxed);
1093        result
1094    }
1095
1096    /// The label's definition must hold on the step, if it can be checked.
1097    /// TLC labels a step with the definition its action was split from, and
1098    /// that action implies the definition's body.
1099    fn label(&mut self, name: &str, step: &St, k: usize) -> Result<(), Stop> {
1100        let m = self.model;
1101        let ev = &m.evaluator;
1102        let Some(d) = m.ir.root_def(name) else {
1103            self.notes.insert(format!(
1104                "label `{name}` names no definition of the root module; not checked"
1105            ));
1106            return Ok(());
1107        };
1108        let d = ev.redirected(d);
1109        if !m.ir.def(d).params.is_empty() || ev.is_value_override(d) {
1110            self.notes.insert(format!(
1111                "label `{name}` names an operator with parameters; not checked"
1112            ));
1113            return Ok(());
1114        }
1115        let r = ev.eval_def(d, step);
1116        match r {
1117            Ok(Value::Bool(true)) => {
1118                self.passed += 1;
1119                Ok(())
1120            }
1121            Ok(Value::Bool(false)) => Err(invalid(
1122                k,
1123                Check::Label,
1124                format!("the step is labelled `{name}`, but `{name}` is false on it"),
1125            )),
1126            Err(error)
1127                if matches!(error.class(), ErrorClass::ResourceLimit | ErrorClass::Bug)
1128                    && self.endpoint_prepared =>
1129            {
1130                Err(self.evaluation_refusal(&error, Some(k), Check::Label))
1131            }
1132            Err(error) if error.class() == ErrorClass::Interrupted => {
1133                Err(refused(&error).at(Some(k), Check::Label))
1134            }
1135            _ => {
1136                self.notes.insert(format!(
1137                    "label `{name}` could not be evaluated on its own; not checked"
1138                ));
1139                Ok(())
1140            }
1141        }
1142    }
1143
1144    /// The claimed invariant or property: those listed before it hold, it
1145    /// does not.
1146    fn claimed(
1147        &mut self,
1148        list: &[dive_model::Named],
1149        i: usize,
1150        st: &St,
1151        k: usize,
1152        check: Check,
1153        what: &str,
1154    ) -> Result<(), Stop> {
1155        for earlier in &list[..i] {
1156            self.require(&earlier.pred, st, k, check, || {
1157                format!("{what} {} is also false here and comes first in the configuration, so it would be reported instead of {}", earlier.name, list[i].name)
1158            })?;
1159        }
1160        let p = &list[i];
1161        if self.holds(&p.pred, st, k, check)? {
1162            return Err(invalid(
1163                k,
1164                Check::Ending,
1165                format!(
1166                    "{what} {} holds at the end of the trace, so the trace does not violate it",
1167                    p.name
1168                ),
1169            ));
1170        }
1171        self.passed += 1;
1172        Ok(())
1173    }
1174
1175    fn require(
1176        &mut self,
1177        pred: &Pred,
1178        st: &St,
1179        k: usize,
1180        check: Check,
1181        detail: impl FnOnce() -> String,
1182    ) -> Result<(), Stop> {
1183        if self.holds(pred, st, k, check)? {
1184            self.passed += 1;
1185            Ok(())
1186        } else {
1187            Err(invalid(k, check, detail()))
1188        }
1189    }
1190
1191    /// The named final invariant raises the claimed underlying error. All
1192    /// earlier invariants still have to hold, in configuration order.
1193    fn invariant_error(&mut self, i: usize, ec: &str, st: &St, k: usize) -> Result<(), Stop> {
1194        let m = self.model;
1195        for earlier in &m.invariants[..i] {
1196            self.require(&earlier.pred, st, k, Check::Invariant, || {
1197                format!(
1198                    "invariant {} comes before {}, so it would decide first",
1199                    earlier.name, m.invariants[i].name
1200                )
1201            })?;
1202        }
1203        let named = &m.invariants[i];
1204        self.host
1205            .level
1206            .store(i64::try_from(k + 1).unwrap_or(i64::MAX), Ordering::Relaxed);
1207        let actual = match m.eval(&named.pred, st) {
1208            Err(error) if error.class() == ErrorClass::Eval => error.ec(),
1209            Err(error) => return Err(self.evaluation_refusal(&error, Some(k), Check::Invariant)),
1210            // Checking an invariant requires a boolean, so a non-boolean
1211            // result independently establishes TLC_EXPECTED_VALUE.
1212            Ok(value) if !matches!(value, Value::Bool(_)) => dive_eval::Ec::ExpectedValue,
1213            Ok(_) => {
1214                return Err(invalid(
1215                    k,
1216                    Check::Ending,
1217                    format!(
1218                        "invariant {} does not raise the claimed evaluation error",
1219                        named.name
1220                    ),
1221                ));
1222            }
1223        };
1224        if actual.name() != ec {
1225            return Err(invalid(
1226                k,
1227                Check::Ending,
1228                format!(
1229                    "invariant {} raises {}, not the claimed {ec}",
1230                    named.name,
1231                    actual.name()
1232                ),
1233            ));
1234        }
1235        self.passed += 1;
1236        Ok(())
1237    }
1238
1239    // TLC first evaluates model constraints, stopping at their first false
1240    // result, then still checks invariants and implied properties on an excluded
1241    // candidate. A false constraint is admissible only for the last state of a
1242    // named, independently checked safety ending. An error while evaluating a
1243    // constraint decides earlier and must never be skipped, even for invariants.
1244    fn constraints(
1245        &mut self,
1246        here: &St,
1247        step: Option<&St>,
1248        state: usize,
1249        allow_excluded: bool,
1250    ) -> Result<(), Stop> {
1251        for constraint in &self.model.constraints {
1252            if !self.holds(&constraint.pred, here, state, Check::Constraint)? {
1253                return if allow_excluded {
1254                    Ok(())
1255                } else {
1256                    Err(invalid(
1257                        state,
1258                        Check::Constraint,
1259                        format!(
1260                            "CONSTRAINT {} is false; only a checked terminal invariant or property may lie outside the model",
1261                            constraint.name,
1262                        ),
1263                    ))
1264                };
1265            }
1266        }
1267        if let Some(step) = step {
1268            for constraint in &self.model.action_constraints {
1269                if !self.holds(&constraint.pred, step, state, Check::ActionConstraint)? {
1270                    return if allow_excluded {
1271                        Ok(())
1272                    } else {
1273                        Err(invalid(
1274                            state,
1275                            Check::ActionConstraint,
1276                            format!(
1277                                "ACTION_CONSTRAINT {} is false; only a checked terminal invariant or property may lie outside the model",
1278                                constraint.name,
1279                            ),
1280                        ))
1281                    };
1282                }
1283            }
1284        }
1285        Ok(())
1286    }
1287
1288    /// A simulation deadlock. TLC's simulator keeps only the successors that
1289    /// satisfy every `CONSTRAINT` and then every `ACTION_CONSTRAINT`, stopping
1290    /// at the first false one (`SimulationWorker.addElement`, `isInModel` and
1291    /// `isInActions`), and reports a deadlock when none is kept. Every
1292    /// successor of the last state is regenerated here; the claim stands only
1293    /// if each one falls outside the model. Constraints see the successor's
1294    /// level, action constraints and generation the last state's.
1295    fn sampled_deadlock(
1296        &mut self,
1297        state: &crate::State,
1298        last: usize,
1299    ) -> Result<Option<String>, Stop> {
1300        let m = self.model;
1301        if m.next.is_none() || m.actions.is_empty() {
1302            return Ok(Some(DEADLOCK_UNSUPPORTED.to_owned()));
1303        }
1304        let source_level = last.saturating_add(1);
1305        let mut ordinal = 0u64;
1306        for action in &m.actions {
1307            self.poll(Some(last), Some(Check::Ending))?;
1308            let host = &self.host;
1309            host.set_replay_level(source_level);
1310            let mut found = None;
1311            let mut sink = |candidate: &dive_eval::next::Successor<'_>| {
1312                if !candidate.complete() {
1313                    found = Some(Found::Incomplete);
1314                    return dive_eval::next::Flow::Stop;
1315                }
1316                let successor: crate::State = candidate.state.iter().cloned().collect();
1317                let here = St::state(successor.clone());
1318                let step = St::action(state.clone(), successor);
1319                let decision = in_model(m, host, &here, &step, source_level);
1320                // Generation continues at the last state's level.
1321                host.set_replay_level(source_level);
1322                match decision {
1323                    Ok(false) => dive_eval::next::Flow::Continue,
1324                    Ok(true) => {
1325                        found = Some(Found::Inside);
1326                        dive_eval::next::Flow::Stop
1327                    }
1328                    Err(other) => {
1329                        found = Some(other);
1330                        dive_eval::next::Flow::Stop
1331                    }
1332                }
1333            };
1334            let outcome = m.evaluator.next_states(action, state, ordinal, &mut sink);
1335            match found {
1336                None => {}
1337                Some(Found::Inside) => {
1338                    return Err(invalid(
1339                        last,
1340                        Check::Ending,
1341                        "the claimed deadlock has a successor that satisfies every constraint",
1342                    ));
1343                }
1344                Some(Found::Incomplete) => {
1345                    return Err(invalid(
1346                        last,
1347                        Check::Ending,
1348                        "the claimed deadlock has a successor that does not assign every variable",
1349                    ));
1350                }
1351                Some(Found::NotBoolean(detail)) => {
1352                    return Err(invalid(last, Check::Ending, detail));
1353                }
1354                Some(Found::Error(e)) => {
1355                    return Err(match e.class() {
1356                        ErrorClass::Eval => invalid(
1357                            last,
1358                            Check::Ending,
1359                            format!(
1360                                "evaluating a constraint on a successor of the claimed deadlock fails: {}",
1361                                e.message()
1362                            ),
1363                        ),
1364                        _ => self.evaluation_refusal(&e, Some(last), Check::Ending),
1365                    });
1366                }
1367            }
1368            match outcome {
1369                Ok(o) => ordinal = ordinal.saturating_add(o.emitted),
1370                Err(e) => {
1371                    return Err(match e.error.class() {
1372                        ErrorClass::Eval => invalid(
1373                            last,
1374                            Check::Ending,
1375                            format!(
1376                                "generating a successor of the claimed deadlock fails: {}",
1377                                e.error.message()
1378                            ),
1379                        ),
1380                        _ => self.evaluation_refusal(&e.error, Some(last), Check::Ending),
1381                    });
1382                }
1383            }
1384        }
1385        if m.has_runtime_names() {
1386            return Ok(Some(crate::RUNTIME_NAMES_UNSUPPORTED.to_owned()));
1387        }
1388        self.notes.insert("Simulation deadlock: every successor of the last state lies outside the model's constraints, so TLC's simulator keeps none".to_owned());
1389        Ok(None)
1390    }
1391
1392    fn evaluation_refusal(
1393        &mut self,
1394        error: &EvalError,
1395        state: Option<usize>,
1396        check: Check,
1397    ) -> Stop {
1398        // Plain finite validation keeps its closed report channel. The
1399        // fallible endpoint path retains original resource/bug transport separately
1400        // and intercepts it before constructing any ValidationReport.
1401        if self.endpoint_prepared
1402            && matches!(error.class(), ErrorClass::ResourceLimit | ErrorClass::Bug)
1403        {
1404            self.endpoint_exception = Some((error.clone(), state, check));
1405        }
1406        refused(error).at(state, check)
1407    }
1408
1409    fn holds(&mut self, pred: &Pred, st: &St, k: usize, check: Check) -> Result<bool, Stop> {
1410        let m = self.model;
1411        // TLC's level of `s0`: state k (numbered from 0) is at level k + 1;
1412        // a step into state k is evaluated with the state before it as s0.
1413        let level = if matches!(st.s1, StateRef::Vals(_)) {
1414            k
1415        } else {
1416            k + 1
1417        };
1418        self.host
1419            .level
1420            .store(i64::try_from(level).unwrap_or(i64::MAX), Ordering::Relaxed);
1421        match m.eval(pred, st) {
1422            Ok(Value::Bool(b)) => Ok(b),
1423            Ok(v) => Err(invalid(
1424                k,
1425                check,
1426                format!(
1427                    "{} is not a boolean here: {}",
1428                    m.location(pred),
1429                    v.kind_name()
1430                ),
1431            )),
1432            Err(e) => match e.class() {
1433                ErrorClass::Eval => Err(invalid(
1434                    k,
1435                    check,
1436                    format!("evaluating {} fails: {}", m.location(pred), e.message()),
1437                )),
1438                _ => Err(self.evaluation_refusal(&e, Some(k), check)),
1439            },
1440        }
1441    }
1442}
1443
1444/// What regenerating a claimed simulation deadlock's successors found.
1445enum Found {
1446    Inside,
1447    Incomplete,
1448    NotBoolean(String),
1449    Error(EvalError),
1450}
1451
1452/// Whether a successor satisfies every `CONSTRAINT` and then every
1453/// `ACTION_CONSTRAINT`, stopping at the first false one, as TLC's simulator
1454/// does. `source_level` is the TLC level of the state it succeeds.
1455fn in_model(
1456    m: &Model,
1457    host: &TraceHost,
1458    here: &St,
1459    step: &St,
1460    source_level: usize,
1461) -> Result<bool, Found> {
1462    let truth = |pred: &Pred, st: &St| match m.eval(pred, st) {
1463        Ok(Value::Bool(b)) => Ok(b),
1464        Ok(v) => Err(Found::NotBoolean(format!(
1465            "{} is not a boolean on a successor of the claimed deadlock: {}",
1466            m.location(pred),
1467            v.kind_name()
1468        ))),
1469        Err(e) => Err(Found::Error(e)),
1470    };
1471    host.set_replay_level(source_level.saturating_add(1));
1472    for constraint in &m.constraints {
1473        if !truth(&constraint.pred, here)? {
1474            return Ok(false);
1475        }
1476    }
1477    host.set_replay_level(source_level);
1478    for constraint in &m.action_constraints {
1479        if !truth(&constraint.pred, step)? {
1480            return Ok(false);
1481        }
1482    }
1483    Ok(true)
1484}
1485
1486fn invalid(state: usize, check: Check, detail: impl Into<String>) -> Stop {
1487    Stop::Invalid(Failure {
1488        state,
1489        check,
1490        detail: detail.into(),
1491    })
1492}
1493
1494fn refused(e: &EvalError) -> Stop {
1495    if e.class() == ErrorClass::Interrupted {
1496        return Stop::Interrupted {
1497            error: e.clone(),
1498            state: None,
1499            check: None,
1500        };
1501    }
1502    Stop::Unsupported(match e.class() {
1503        ErrorClass::Unsupported => format!("the evaluator refuses: {}", e.message()),
1504        ErrorClass::ResourceLimit => format!("resource limit: {}", e.message()),
1505        _ => format!("internal evaluator error (a bug): {e}"),
1506    })
1507}
1508
1509impl Drop for Run<'_> {
1510    fn drop(&mut self) {
1511        let _ = self.model.evaluator.replace_host(self.inner.take());
1512    }
1513}
1514
1515/// What the validator provides of a checking run: the level of the state
1516/// being checked (`TLCGet("level")`, refusing it under a prime) and `TLCGet("config")` from the host the
1517/// model was bound with, if any. Registers and live counters depend on
1518/// evaluations outside the trace, so they are refused by name. Register
1519/// access and unproved random draws are remembered so the whole verdict is
1520/// refused, including when an optional label check swallowed an error. Fresh
1521/// finite sessions may instead install a bounded source-choice search.
1522#[derive(Debug)]
1523pub(crate) struct TraceHost {
1524    inputs: Option<Arc<dive_eval::inputs::InputReplay>>,
1525    level: AtomicI64,
1526    inner: Option<Arc<dyn Host>>,
1527    /// The first operator that drew.
1528    drew: Mutex<Option<StdOp>>,
1529    /// Whether any check drew.
1530    any: AtomicBool,
1531    /// Whether any check attempted a register read or write.
1532    pub(crate) registers: AtomicBool,
1533    /// Whether evaluation reached composition outside the bounded slice.
1534    composition: AtomicBool,
1535    pub(crate) register_used: AtomicBool,
1536    pub(crate) startup: AtomicBool,
1537    /// The narrow Next lane refuses output effects even during fresh startup.
1538    pub(crate) next_error: AtomicBool,
1539    effect: Mutex<Option<String>>,
1540    private: bool,
1541    pub(crate) run_config: Mutex<Option<dive_eval::RunConfig>>,
1542    /// This host's own expression cache domain: replay reuses lazy values it
1543    /// computed itself, as TLC's `LazyValue` does, but never values another
1544    /// consumer cached.
1545    cache_domain: u64,
1546    pub(crate) choices: Option<Arc<crate::choices::Search>>,
1547    predicate_init: AtomicBool,
1548    predicate_next: AtomicBool,
1549}
1550
1551/// A cache domain no other replay host has used (0 is ordinary evaluation's).
1552pub(crate) fn next_cache_domain() -> u64 {
1553    static NEXT: AtomicU64 = AtomicU64::new(1);
1554    NEXT.fetch_add(1, Ordering::Relaxed)
1555}
1556
1557impl TraceHost {
1558    #[cfg(test)]
1559    pub(crate) fn startup() -> Arc<Self> {
1560        Self::startup_context(None, None)
1561    }
1562
1563    pub(crate) fn set_replay_level(&self, level: usize) {
1564        self.level
1565            .store(i64::try_from(level).unwrap_or(i64::MAX), Ordering::Relaxed);
1566    }
1567    pub(crate) fn startup_context(
1568        inputs: Option<Arc<dive_eval::inputs::InputReplay>>,
1569        choices: Option<Arc<crate::choices::Search>>,
1570    ) -> Arc<Self> {
1571        Arc::new(Self {
1572            inputs,
1573            level: AtomicI64::new(0),
1574            inner: None,
1575            drew: Mutex::new(None),
1576            any: AtomicBool::new(false),
1577            registers: AtomicBool::new(false),
1578            composition: AtomicBool::new(false),
1579            register_used: AtomicBool::new(false),
1580            startup: AtomicBool::new(true),
1581            next_error: AtomicBool::new(false),
1582            effect: Mutex::new(None),
1583            private: true,
1584            run_config: Mutex::new(None),
1585            cache_domain: next_cache_domain(),
1586            choices,
1587            predicate_init: AtomicBool::new(false),
1588            predicate_next: AtomicBool::new(false),
1589        })
1590    }
1591
1592    pub(crate) fn finish_input_binding(&self, model: &Model) -> Result<(), String> {
1593        if let Some(feature) = model.evaluator.external_input_refusal() {
1594            return Err(feature);
1595        }
1596        self.inputs.as_ref().map_or(Ok(()), |inputs| {
1597            inputs.finish_binding().map_err(|error| error.message)
1598        })
1599    }
1600
1601    fn private_host(&self) -> bool {
1602        self.private
1603    }
1604
1605    fn refuse_effect(&self, feature: String) -> Result<(), HostError> {
1606        let mut effect = self.effect.lock().unwrap_or_else(PoisonError::into_inner);
1607        if effect.is_none() {
1608            *effect = Some(feature.clone());
1609        }
1610        Err(HostError {
1611            code: 0,
1612            message: feature,
1613        })
1614    }
1615}
1616
1617impl Host for TraceHost {
1618    fn input(
1619        &self,
1620        request: &dive_eval::inputs::InputRequest,
1621    ) -> Option<Result<dive_eval::inputs::InputResponse, HostError>> {
1622        self.inputs.as_ref().map(|inputs| inputs.request(request))
1623    }
1624
1625    fn check_random_in_enabled(&self) -> Result<(), HostError> {
1626        self.refuse_effect(
1627            "RandomElement/Randomization inside ENABLED is unsupported in independent replay"
1628                .into(),
1629        )
1630    }
1631
1632    fn check_native_access(&self, op: StdOp) -> Result<(), HostError> {
1633        if self.inputs.is_some() && matches!(op, StdOp::IoUtilsIOEnv | StdOp::IoUtilsDeserialize) {
1634            return Ok(());
1635        }
1636        if op == StdOp::TlcRandomElement
1637            && let Some(choices) = &self.choices
1638        {
1639            if self.register_used.load(Ordering::Relaxed)
1640                || self.predicate_init.load(Ordering::Relaxed)
1641                || self.predicate_next.load(Ordering::Relaxed)
1642            {
1643                return Err(choices.refuse(
1644                    "random choice requires supported ordered Init/Next and a register-free replay prefix",
1645                ));
1646            }
1647
1648            return Ok(());
1649        }
1650        if self.private_host()
1651            && matches!(
1652                op,
1653                StdOp::TlcRandomElement
1654                    | StdOp::RandomizationRandomSubset
1655                    | StdOp::RandomizationRandomSetOfSubsets
1656                    | StdOp::RandomizationRandomSubsetSet
1657            )
1658        {
1659            if !self.any.swap(true, Ordering::Relaxed) {
1660                *self.drew.lock().unwrap_or_else(PoisonError::into_inner) = Some(op);
1661            }
1662            return Err(HostError {
1663                code: 0,
1664                message: format!("{}: {RANDOM_UNSUPPORTED}", op.qualified_name()),
1665            });
1666        }
1667        if self.private_host()
1668            && op.impure()
1669            && !matches!(
1670                op,
1671                StdOp::TlcTLCGet | StdOp::TlcTLCSet | StdOp::TlcPrint | StdOp::TlcPrintT
1672            )
1673        {
1674            return self.refuse_effect(format!(
1675                "{}: private trace startup does not support this host effect",
1676                op.qualified_name()
1677            ));
1678        }
1679        Ok(())
1680    }
1681
1682    fn print_output(&self, _text: &str) -> Result<bool, HostError> {
1683        if self.next_error.load(Ordering::Relaxed) {
1684            self.refuse_effect("Print/PrintT in Next error reconstruction".into())?;
1685        }
1686        // Reconstruct Print's value semantics without invoking any sink or
1687        // counting replay/startup reconstruction as producer output. The
1688        // evaluator still checks arguments and performs normal rendering.
1689        Ok(false)
1690    }
1691
1692    fn check_tlc_access(&self, key: &str, write: bool) -> Result<(), HostError> {
1693        if self.private_host()
1694            && !(key.starts_with("s:")
1695                || !write && matches!(key, "config" | "level" | "all" | "all:named"))
1696        {
1697            return self.refuse_effect(format!(
1698                "TLC{}({key:?}): private trace startup does not support this host effect",
1699                if write { "Set" } else { "Get" }
1700            ));
1701        }
1702        Ok(())
1703    }
1704    fn check_register_access(&self) -> Result<(), HostError> {
1705        if let Some(choices) = &self.choices
1706            && choices.drew()
1707        {
1708            self.registers.store(true, Ordering::Relaxed);
1709            return Err(choices.refuse(REGISTERS_UNSUPPORTED));
1710        }
1711        self.register_used.store(true, Ordering::Relaxed);
1712        if self.startup.load(Ordering::Relaxed) {
1713            return Ok(());
1714        }
1715        self.registers.store(true, Ordering::Relaxed);
1716        Err(HostError {
1717            code: 0,
1718            message: REGISTERS_UNSUPPORTED.to_owned(),
1719        })
1720    }
1721
1722    fn check_action_composition(&self) -> Result<(), HostError> {
1723        self.composition.store(true, Ordering::Relaxed);
1724        Err(HostError {
1725            code: 0,
1726            message: COMPOSITION_UNSUPPORTED.to_owned(),
1727        })
1728    }
1729
1730    fn requires_bounded_action_composition(&self) -> bool {
1731        true
1732    }
1733
1734    fn check_bounded_action_composition(&self) -> Result<(), HostError> {
1735        let result = self
1736            .inner
1737            .as_ref()
1738            .map_or(Ok(()), |host| host.check_bounded_action_composition());
1739        if result.is_err() {
1740            self.composition.store(true, Ordering::Relaxed);
1741        }
1742        result
1743    }
1744
1745    fn expression_cache_domain(&self) -> u64 {
1746        self.cache_domain
1747    }
1748
1749    fn random(&self, op: StdOp, args: &[Value], ctx: Ctx) -> Option<Result<Value, HostError>> {
1750        if let Some(choices) = &self.choices {
1751            return Some(choices.random(op, args, ctx));
1752        }
1753        if !self.any.swap(true, Ordering::Relaxed) {
1754            *self.drew.lock().unwrap_or_else(PoisonError::into_inner) = Some(op);
1755        }
1756        None
1757    }
1758
1759    fn level(&self) -> Option<i64> {
1760        Some(self.level.load(Ordering::Relaxed))
1761    }
1762
1763    /// Replay tracks only the level of the state being checked, so a primed
1764    /// `TLCGet("level")` (the successor's level in TLC) refuses the whole
1765    /// verdict, even where a label check swallowed the error.
1766    fn successor_level(&self) -> Result<i64, HostError> {
1767        self.refuse_effect(dive_eval::PRIMED_LEVEL_UNSUPPORTED.to_owned())
1768            .map(|()| 0)
1769    }
1770
1771    fn config(&self) -> Option<dive_eval::RunConfig> {
1772        self.run_config
1773            .lock()
1774            .unwrap_or_else(PoisonError::into_inner)
1775            .clone()
1776            .or_else(|| self.inner.as_ref().and_then(|h| h.config()))
1777    }
1778}
1779
1780/// Validates a trace already read against `model`. Random draws are refused
1781/// by name ([`RANDOM_UNSUPPORTED`]).
1782#[must_use]
1783pub fn validate(model: &Model, trace: &Trace) -> Report {
1784    let admitted = model.validate_context().and_then(|()| {
1785        for &def in &model.assumptions {
1786            model.evaluator.scope(def)?;
1787        }
1788        Ok(())
1789    });
1790    if let Err(error) = admitted {
1791        return Report {
1792            validation: Validation::Unsupported(error.to_string()),
1793            notes: Vec::new(),
1794            length: trace.logical_length(),
1795        };
1796    }
1797    let mut run = Run::new(model);
1798    let validation = run.validate(trace);
1799    Report {
1800        validation,
1801        notes: std::mem::take(&mut run.notes).into_iter().collect(),
1802        length: trace.logical_length(),
1803    }
1804}
1805
1806/// Validates supplied states with a generic cooperative host capability.
1807///
1808/// Interruption is returned outside [`Validation`]: it is neither an invalid
1809/// trace nor an unsupported feature. Only the owning driver can interpret its
1810/// opaque identity. Binding, `ASSUME`, quiet value units and pure bulk/native
1811/// work retain their interruption limitations. Supplied deferred values may
1812/// retain a different evaluator, whose work this control does not govern.
1813/// This does not control TLC JSON
1814/// interpretation or private [`crate::Session`] reconstruction.
1815///
1816/// ```
1817/// # fn run(model: &dive_model::Model, trace: &dive_trace::Trace,
1818/// #        control: std::sync::Arc<dyn dive_eval::HostControl>)
1819/// #        -> Result<dive_trace::Report, dive_trace::ValidationRunError> {
1820/// dive_trace::validate_controlled(model, trace, control)
1821/// # }
1822/// ```
1823///
1824/// # Errors
1825/// Typed host interruption with actual validation progress, or a conflicting
1826/// control registration owned by another thread. Ordinary invalid/unsupported
1827/// trace reports remain ordinary reports.
1828pub fn validate_controlled(
1829    model: &Model,
1830    trace: &Trace,
1831    control: Arc<dyn dive_eval::HostControl>,
1832) -> Result<Report, ValidationRunError> {
1833    let _scope = model
1834        .evaluator
1835        .host_control(Some(control.clone()))
1836        .map_err(ValidationRunError::ControlConflict)?;
1837    let admitted = model.validate_context().and_then(|()| {
1838        for &def in &model.assumptions {
1839            model.evaluator.scope(def)?;
1840        }
1841        Ok(())
1842    });
1843    if let Err(error) = admitted {
1844        if error.class() == ErrorClass::Interrupted {
1845            return Err(ValidationRunError::Interrupted {
1846                error,
1847                progress: ValidationProgress {
1848                    checks_passed: 0,
1849                    state: None,
1850                    check: None,
1851                },
1852            });
1853        }
1854        return Ok(Report {
1855            validation: Validation::Unsupported(error.to_string()),
1856            notes: Vec::new(),
1857            length: trace.logical_length(),
1858        });
1859    }
1860    let mut run = Run::new(model);
1861    run.control = Some(control);
1862    controlled_report(&mut run, trace)
1863}
1864
1865#[allow(
1866    clippy::too_many_lines,
1867    reason = "finite validation and independent endpoint phases share one fallible report boundary"
1868)]
1869fn controlled_report(run: &mut Run<'_>, trace: &Trace) -> Result<Report, ValidationRunError> {
1870    let endpoint = if matches!(trace.ending, Ending::TemporalStateError { .. }) {
1871        if !run.host.private {
1872            return Ok(Report {
1873                validation: Validation::Unsupported(
1874                    "temporal error endpoint requires a privately reconstructed source session"
1875                        .into(),
1876                ),
1877                notes: Vec::new(),
1878                length: trace.logical_length(),
1879            });
1880        }
1881        if !trace.properties.is_empty() {
1882            return Ok(Report {
1883                validation: Validation::Invalid(Failure {
1884                    state: 0,
1885                    check: Check::Shape,
1886                    detail: "finite error endpoints cannot claim temporal properties".into(),
1887                }),
1888                notes: Vec::new(),
1889                length: trace.logical_length(),
1890            });
1891        }
1892        match crate::row_demand::prepare(run.model, &trace.states, run.control.as_deref()) {
1893            Ok(program) => {
1894                run.endpoint_prepared = true;
1895                Some(program)
1896            }
1897            Err(error) => return endpoint_refusal(run, trace, error, None),
1898        }
1899    } else {
1900        None
1901    };
1902    let result = run.validate_result(trace);
1903    let mut validation = controlled_result(run, result)?;
1904    if validation == Validation::Valid
1905        && let Some(program) = endpoint
1906    {
1907        let Some(last) = trace.states.len().checked_sub(1) else {
1908            return Ok(Report {
1909                validation: Validation::Invalid(Failure {
1910                    state: 0,
1911                    check: Check::Shape,
1912                    detail: "endpoint has no state".into(),
1913                }),
1914                notes: Vec::new(),
1915                length: 0,
1916            });
1917        };
1918        let Ending::TemporalStateError { ec, endpoint } = &trace.ending else {
1919            return Ok(Report {
1920                validation: Validation::Unsupported("missing endpoint ending".into()),
1921                notes: Vec::new(),
1922                length: trace.logical_length(),
1923            });
1924        };
1925        match program.replay(
1926            run.model,
1927            &trace.states[last],
1928            ec,
1929            endpoint,
1930            run.control.as_deref(),
1931        ) {
1932            Ok(Ok(())) => {}
1933            Ok(Err(detail)) => {
1934                validation = Validation::Invalid(Failure {
1935                    state: last,
1936                    check: Check::Ending,
1937                    detail,
1938                });
1939            }
1940            Err(error) => return endpoint_refusal(run, trace, error, Some(last)),
1941        }
1942        if let Some(control) = &run.control {
1943            control
1944                .check()
1945                .map_err(|error| ValidationRunError::Interrupted {
1946                    error: EvalError::interrupted(error),
1947                    progress: progress(run, Some(last)),
1948                })?;
1949        }
1950    }
1951    if let Some(feature) = run.refusal() {
1952        validation = Validation::Unsupported(feature);
1953    }
1954    Ok(Report {
1955        validation,
1956        notes: std::mem::take(&mut run.notes).into_iter().collect(),
1957        length: trace.logical_length(),
1958    })
1959}
1960
1961fn controlled_result(
1962    run: &mut Run<'_>,
1963    result: Result<Validation, Stop>,
1964) -> Result<Validation, ValidationRunError> {
1965    if let Some((error, state, check)) = run.endpoint_exception.take() {
1966        let progress = ValidationProgress {
1967            checks_passed: run.passed,
1968            state,
1969            check: Some(check),
1970        };
1971        return Err(if error.class() == ErrorClass::ResourceLimit {
1972            ValidationRunError::ResourceLimit { error, progress }
1973        } else {
1974            ValidationRunError::EvaluationFailure { error, progress }
1975        });
1976    }
1977    let validation = match result {
1978        Ok(validation) => validation,
1979        Err(Stop::Interrupted {
1980            error,
1981            state,
1982            check,
1983        }) => {
1984            return Err(ValidationRunError::Interrupted {
1985                error,
1986                progress: ValidationProgress {
1987                    checks_passed: run.passed,
1988                    state,
1989                    check,
1990                },
1991            });
1992        }
1993        Err(Stop::ControlConflict(error)) => {
1994            return Err(ValidationRunError::ControlConflict(error));
1995        }
1996        Err(other) => other.into(),
1997    };
1998    Ok(validation)
1999}
2000
2001fn progress(run: &Run<'_>, state: Option<usize>) -> ValidationProgress {
2002    ValidationProgress {
2003        checks_passed: run.passed,
2004        state,
2005        check: Some(Check::Ending),
2006    }
2007}
2008fn endpoint_refusal(
2009    run: &Run<'_>,
2010    trace: &Trace,
2011    error: crate::row_demand::FormulaError,
2012    state: Option<usize>,
2013) -> Result<Report, ValidationRunError> {
2014    let feature = match error {
2015        crate::row_demand::FormulaError::Evaluation(error) => match error.class() {
2016            ErrorClass::Interrupted => {
2017                return Err(ValidationRunError::Interrupted {
2018                    error,
2019                    progress: progress(run, state),
2020                });
2021            }
2022            ErrorClass::ResourceLimit => {
2023                return Err(ValidationRunError::ResourceLimit {
2024                    error,
2025                    progress: progress(run, state),
2026                });
2027            }
2028            ErrorClass::Bug => {
2029                return Err(ValidationRunError::EvaluationFailure {
2030                    error,
2031                    progress: progress(run, state),
2032                });
2033            }
2034            _ => error.to_string(),
2035        },
2036        other => other.to_string(),
2037    };
2038    Ok(Report {
2039        validation: Validation::Unsupported(feature),
2040        notes: Vec::new(),
2041        length: trace.logical_length(),
2042    })
2043}
2044
2045pub(crate) fn validate_private_controlled(
2046    model: &Model,
2047    host: Arc<TraceHost>,
2048    trace: &Trace,
2049    control: Option<Arc<dyn dive_eval::HostControl>>,
2050) -> Result<Report, ValidationRunError> {
2051    let _scope = control
2052        .as_ref()
2053        .map(|control| model.evaluator.host_control(Some(control.clone())))
2054        .transpose()
2055        .map_err(ValidationRunError::ControlConflict)?;
2056    let mut run = Run::private(model, host, false);
2057    run.control = control;
2058    controlled_report(&mut run, trace)
2059}
2060
2061pub(crate) fn validate_finite_private_controlled(
2062    model: &Model,
2063    host: &Arc<TraceHost>,
2064    trace: &Trace,
2065    initial: bool,
2066    control: Option<Arc<dyn dive_eval::HostControl>>,
2067    scope: FiniteScope,
2068) -> Result<(Report, bool), ValidationRunError> {
2069    let _scope = control
2070        .as_ref()
2071        .map(|control| model.evaluator.host_control(Some(control.clone())))
2072        .transpose()
2073        .map_err(ValidationRunError::ControlConflict)?;
2074    let mut run = Run::private(model, host.clone(), initial);
2075    run.control = control;
2076    run.assumption_control = AssumptionControl::Cooperative;
2077    run.finite_scope = scope;
2078    let report = controlled_report(&mut run, trace)?;
2079    let retry = initial && run.init_incomplete && !host.register_used.load(Ordering::Relaxed);
2080    Ok((report, retry))
2081}
2082
2083/// Internal prefix result: Session must separately replay the terminal event
2084/// on another freshly bound runtime before publishing a completed report.
2085pub(crate) fn validate_next_prefix_controlled(
2086    model: &Model,
2087    host: Arc<TraceHost>,
2088    trace: &Trace,
2089    control: Option<Arc<dyn dive_eval::HostControl>>,
2090) -> Result<(Report, u64), ValidationRunError> {
2091    let _scope = control
2092        .as_ref()
2093        .map(|control| model.evaluator.host_control(Some(control.clone())))
2094        .transpose()
2095        .map_err(ValidationRunError::ControlConflict)?;
2096    let mut run = Run::private(model, host, false);
2097    run.control = control;
2098    run.endpoint_prepared = true;
2099    let mut report = controlled_report(&mut run, trace)?;
2100    if report.validation == Validation::Valid
2101        && matches!(trace.ending, Ending::CandidateStateError { .. })
2102    {
2103        let last = trace.states.len() - 1;
2104        if let Some(label) = &trace.labels[last] {
2105            run.host.set_replay_level(last);
2106            let step = St::action(trace.states[last - 1].clone(), trace.states[last].clone());
2107            let result = run
2108                .label(&label.name, &step, last)
2109                .map(|()| Validation::Valid);
2110            report.validation = controlled_result(&mut run, result)?;
2111            report.notes.extend(std::mem::take(&mut run.notes));
2112        }
2113        report.length = trace.logical_length();
2114    }
2115    Ok((report, run.passed))
2116}
2117
2118#[allow(
2119    clippy::too_many_lines,
2120    reason = "one typed control boundary dispatches independently replayed terminal sites"
2121)]
2122pub(crate) fn replay_next_controlled(
2123    model: &Model,
2124    host: Arc<TraceHost>,
2125    trace: &Trace,
2126    state: &crate::State,
2127    checks_passed: u64,
2128    control: Option<Arc<dyn dive_eval::HostControl>>,
2129) -> Result<Report, ValidationRunError> {
2130    let _scope = control
2131        .as_ref()
2132        .map(|control| model.evaluator.host_control(Some(control.clone())))
2133        .transpose()
2134        .map_err(ValidationRunError::ControlConflict)?;
2135    let mut run = Run::private(model, host, false);
2136    run.control = control;
2137    run.passed = checks_passed;
2138    let Some(last) = trace.states.len().checked_sub(1) else {
2139        return Ok(Report {
2140            validation: Validation::Invalid(Failure {
2141                state: 0,
2142                check: Check::Shape,
2143                detail: "Next endpoint has no state".into(),
2144            }),
2145            notes: Vec::new(),
2146            length: 0,
2147        });
2148    };
2149    run.poll(Some(last), Some(Check::Ending))
2150        .map_err(|stop| match stop {
2151            Stop::Interrupted { error, .. } => ValidationRunError::Interrupted {
2152                error,
2153                progress: progress(&run, Some(last)),
2154            },
2155            _ => ValidationRunError::EvaluationFailure {
2156                error: EvalError::bug("unexpected terminal replay poll outcome"),
2157                progress: progress(&run, Some(last)),
2158            },
2159        })?;
2160    run.host.level.store(
2161        i64::try_from(last.saturating_add(1)).unwrap_or(i64::MAX),
2162        Ordering::Relaxed,
2163    );
2164    let replay = match &trace.ending {
2165        Ending::ViewSourceError { ec, endpoint } => crate::ordered_prefix::view(
2166            model,
2167            trace,
2168            ec,
2169            endpoint,
2170            &run.host,
2171            run.control.as_deref(),
2172        ),
2173        Ending::CandidateStateError { ec, endpoint } => {
2174            let Some(source) = last
2175                .checked_sub(1)
2176                .and_then(|index| trace.states.get(index))
2177            else {
2178                return Ok(Report {
2179                    validation: Validation::Invalid(Failure {
2180                        state: last,
2181                        check: Check::Shape,
2182                        detail: "candidate error has no predecessor".into(),
2183                    }),
2184                    notes: Vec::new(),
2185                    length: trace.logical_length(),
2186                });
2187            };
2188            crate::candidate_error::replay(
2189                model,
2190                source,
2191                state,
2192                last,
2193                ec,
2194                endpoint,
2195                &run.host,
2196                run.control.as_deref(),
2197            )
2198        }
2199        Ending::TemporalSourceError { ec, endpoint } => crate::source_row::replay(
2200            model,
2201            state,
2202            last,
2203            ec,
2204            endpoint,
2205            &run.host,
2206            run.control.as_deref(),
2207        ),
2208        Ending::NextStateError { ec, endpoint } => crate::next_error::replay(
2209            model,
2210            state,
2211            last,
2212            ec,
2213            endpoint,
2214            &run.host,
2215            run.control.as_deref(),
2216        ),
2217        _ => Ok(Validation::Unsupported(
2218            "missing source terminal endpoint".into(),
2219        )),
2220    };
2221    let mut validation = replay.map_err(|error| match error.class() {
2222        ErrorClass::Interrupted => ValidationRunError::Interrupted {
2223            error,
2224            progress: progress(&run, Some(last)),
2225        },
2226        ErrorClass::ResourceLimit => ValidationRunError::ResourceLimit {
2227            error,
2228            progress: progress(&run, Some(last)),
2229        },
2230        _ => ValidationRunError::EvaluationFailure {
2231            error,
2232            progress: progress(&run, Some(last)),
2233        },
2234    })?;
2235    if let Some(feature) = run.refusal() {
2236        validation = Validation::Unsupported(feature);
2237    }
2238    Ok(Report {
2239        validation,
2240        notes: Vec::new(),
2241        length: trace.logical_length(),
2242    })
2243}
2244
2245pub(crate) fn replay_partial_controlled(
2246    model: &Model,
2247    host: Arc<TraceHost>,
2248    trace: &Trace,
2249    endpoint: &crate::PartialNextEndpoint,
2250    checks_passed: u64,
2251    control: Option<Arc<dyn dive_eval::HostControl>>,
2252) -> Result<Report, ValidationRunError> {
2253    let _scope = control
2254        .as_ref()
2255        .map(|control| model.evaluator.host_control(Some(control.clone())))
2256        .transpose()
2257        .map_err(ValidationRunError::ControlConflict)?;
2258    let mut run = Run::private(model, host, false);
2259    run.control = control;
2260    run.passed = checks_passed;
2261    let Some(last) = trace.states.len().checked_sub(1) else {
2262        return Ok(Report {
2263            validation: Validation::Invalid(Failure {
2264                state: 0,
2265                check: Check::Shape,
2266                detail: "Next endpoint has no state".into(),
2267            }),
2268            notes: Vec::new(),
2269            length: 0,
2270        });
2271    };
2272    run.poll(Some(last), Some(Check::Ending))
2273        .map_err(|stop| match stop {
2274            Stop::Interrupted { error, .. } => ValidationRunError::Interrupted {
2275                error,
2276                progress: progress(&run, Some(last)),
2277            },
2278            _ => ValidationRunError::EvaluationFailure {
2279                error: EvalError::bug("unexpected terminal replay poll outcome"),
2280                progress: progress(&run, Some(last)),
2281            },
2282        })?;
2283    run.host.level.store(
2284        i64::try_from(last.saturating_add(1)).unwrap_or(i64::MAX),
2285        Ordering::Relaxed,
2286    );
2287    let mut validation = crate::partial::replay(
2288        model,
2289        &trace.states[last],
2290        trace.states.len(),
2291        endpoint,
2292        &run.host,
2293        run.control.as_deref(),
2294    )
2295    .map_err(|error| match error.class() {
2296        ErrorClass::Interrupted => ValidationRunError::Interrupted {
2297            error,
2298            progress: progress(&run, Some(last)),
2299        },
2300        ErrorClass::ResourceLimit => ValidationRunError::ResourceLimit {
2301            error,
2302            progress: progress(&run, Some(last)),
2303        },
2304        _ => ValidationRunError::EvaluationFailure {
2305            error,
2306            progress: progress(&run, Some(last)),
2307        },
2308    })?;
2309    if let Some(feature) = run.refusal() {
2310        validation = Validation::Unsupported(feature);
2311    }
2312    Ok(Report {
2313        validation,
2314        notes: Vec::new(),
2315        length: trace.states.len().saturating_add(1),
2316    })
2317}
2318
2319pub(crate) fn replay_initial_partial_controlled(
2320    model: &Model,
2321    host: Arc<TraceHost>,
2322    endpoint: &crate::PartialStateEndpoint,
2323    control: Option<Arc<dyn dive_eval::HostControl>>,
2324) -> Result<Report, ValidationRunError> {
2325    let _scope = control
2326        .as_ref()
2327        .map(|c| model.evaluator.host_control(Some(c.clone())))
2328        .transpose()
2329        .map_err(ValidationRunError::ControlConflict)?;
2330    let mut run = Run::private(model, host, false);
2331    run.control = control;
2332    run.endpoint_prepared = true;
2333    run.host.set_replay_level(0);
2334    run.poll(None, Some(Check::Assumption))
2335        .map_err(|stop| match stop {
2336            Stop::Interrupted { error, .. } => ValidationRunError::Interrupted {
2337                error,
2338                progress: progress(&run, None),
2339            },
2340            _ => ValidationRunError::EvaluationFailure {
2341                error: EvalError::bug("unexpected Init partial control failure"),
2342                progress: progress(&run, None),
2343            },
2344        })?;
2345    let result = run.assumptions().map(|()| Validation::Valid);
2346    let mut validation = controlled_result(&mut run, result)?;
2347    if validation == Validation::Valid {
2348        let empty = Arc::from([]);
2349        validation = crate::partial::replay(
2350            model,
2351            &empty,
2352            0,
2353            endpoint,
2354            &run.host,
2355            run.control.as_deref(),
2356        )
2357        .map_err(|error| match error.class() {
2358            ErrorClass::Interrupted => ValidationRunError::Interrupted {
2359                error,
2360                progress: progress(&run, None),
2361            },
2362            ErrorClass::ResourceLimit => ValidationRunError::ResourceLimit {
2363                error,
2364                progress: progress(&run, None),
2365            },
2366            _ => ValidationRunError::EvaluationFailure {
2367                error,
2368                progress: progress(&run, None),
2369            },
2370        })?;
2371    }
2372    if let Some(feature) = run.refusal() {
2373        validation = Validation::Unsupported(feature);
2374    }
2375    if let Some(control) = &run.control {
2376        control
2377            .check()
2378            .map_err(|error| ValidationRunError::Interrupted {
2379                error: EvalError::interrupted(error),
2380                progress: progress(&run, None),
2381            })?;
2382    }
2383    Ok(Report {
2384        validation,
2385        notes: Vec::new(),
2386        length: 1,
2387    })
2388}
2389
2390/// `report`, refused if a name was created after the model was bound
2391/// ([`RUNTIME_NAMES_UNSUPPORTED`]).
2392pub(crate) fn guard_runtime_names(model: &Model, mut report: Report) -> Report {
2393    if model.has_runtime_names() {
2394        report.validation = Validation::Unsupported(RUNTIME_NAMES_UNSUPPORTED.to_owned());
2395    }
2396    report
2397}
2398
2399/// Negative controls: by-construction invalid edits of a valid
2400/// breadth-first counterexample must be rejected.
2401#[cfg(test)]
2402mod negative_controls {
2403    #![allow(clippy::expect_used, clippy::panic, reason = "test assertions")]
2404
2405    use std::sync::Arc;
2406
2407    use super::{
2408        Check, ErrorClass, Run, TraceHost, Validation, ValidationRunError, endpoint_refusal,
2409        validate,
2410    };
2411    use crate::{Ending, Trace, TraceDoc};
2412
2413    const SPEC: &str = "---- MODULE Count ----\nEXTENDS Naturals\nVARIABLE x\n\
2414        Init == x = 0\nNext == x' = x + 1\nSmall == x < 3\nTiny == x < 5\n====\n";
2415
2416    fn model() -> dive_model::Model {
2417        let analysis = dive_sema::analyze_source("Count.tla", SPEC, &dive_sema::Options::default());
2418        let ir = Arc::new(dive_ir::lower(&analysis).expect("lower"));
2419        let cfg = dive_config::parse("INIT Init\nNEXT Next\nINVARIANT Tiny Small\n")
2420            .into_config()
2421            .expect("cfg");
2422        dive_model::bind(ir, &cfg, &dive_model::BindOptions::tlc()).expect("bind")
2423    }
2424
2425    fn trace(model: &dive_model::Model, xs: &[i64]) -> Trace {
2426        let states = xs.iter().map(|x| serde_json::json!({ "x": x })).collect();
2427        let doc = TraceDoc::behavior(states)
2428            .expect("states")
2429            .with_ending(Ending::Invariant("Small".to_owned()));
2430        Trace::decode(model, &doc).expect("decode")
2431    }
2432
2433    fn rejected(model: &dive_model::Model, t: &Trace) -> Check {
2434        match validate(model, t).validation {
2435            Validation::Invalid(f) => f.check,
2436            other => panic!("{other:?}"),
2437        }
2438    }
2439
2440    #[test]
2441    fn endpoint_allocation_failure_has_no_completed_validation_report() {
2442        let model = model();
2443        let trace = trace(&model, &[0, 1]);
2444        let host = TraceHost::startup();
2445        let run = Run::private(&model, host, false);
2446        let error = crate::row_demand::reserve(&mut Vec::<u64>::new(), usize::MAX)
2447            .expect_err("actual allocation capacity overflow");
2448        let error =
2449            endpoint_refusal(&run, &trace, error, Some(1)).expect_err("no report on exhaustion");
2450        assert!(
2451            matches!(error,ValidationRunError::ResourceLimit{error,progress} if error.class()==ErrorClass::ResourceLimit&&progress.state==Some(1)&&progress.check==Some(Check::Ending))
2452        );
2453    }
2454
2455    #[test]
2456    fn edits_of_a_valid_counterexample_are_rejected() {
2457        let m = model();
2458        let original = trace(&m, &[0, 1, 2, 3]);
2459        assert_eq!(validate(&m, &original).validation, Validation::Valid);
2460        // A dropped middle state, a dropped initial state, swapped states
2461        // and a changed value are not steps of the specification.
2462        assert_eq!(rejected(&m, &trace(&m, &[0, 1, 3])), Check::Next);
2463        assert_eq!(rejected(&m, &trace(&m, &[1, 2, 3])), Check::Init);
2464        assert_eq!(rejected(&m, &trace(&m, &[0, 2, 1, 3])), Check::Next);
2465        assert_eq!(rejected(&m, &trace(&m, &[0, 1, 7, 3])), Check::Next);
2466        // Cut short, the claimed invariant holds at the end.
2467        assert_eq!(rejected(&m, &trace(&m, &[0, 1, 2])), Check::Ending);
2468        // Another invariant is not violated at the end.
2469        let mut claim = original.clone();
2470        claim.ending = Ending::Invariant("Tiny".to_owned());
2471        assert_eq!(rejected(&m, &claim), Check::Ending);
2472        // An invariant the model does not have.
2473        claim.ending = Ending::Invariant("Missing".to_owned());
2474        assert_eq!(rejected(&m, &claim), Check::Ending);
2475    }
2476}