Skip to main content

dive_trace/
ordered_prefix.rs

1//! Independent bounded source admission and actual diagnostic execution.
2
3use dive_eval::{EvalError, ExceptionKind, HostControl};
4use dive_model::Model;
5
6use crate::ordered::{Driver, Event, History, Site};
7use crate::validate::TraceHost;
8use crate::{Check, Ending, Failure, State, Trace, Validation, ViewSourceEndpoint};
9
10/// Independently executed successor invariant primary and diagnostic identities.
11/// Only a fresh [`crate::Session::invariant_error_class`] constructs this value;
12/// it is never serialized or accepted as producer evidence.
13#[derive(Clone, Debug, PartialEq, Eq)]
14pub struct InvariantErrorClass {
15    reported: u32,
16    deciding: u32,
17}
18impl InvariantErrorClass {
19    /// The observed primary invariant wrapper.
20    #[must_use]
21    pub fn reported_code(&self) -> u32 {
22        self.reported
23    }
24    /// The deciding identity after actual diagnostic completion or exception.
25    #[must_use]
26    pub fn deciding_code(&self) -> u32 {
27        self.deciding
28    }
29}
30
31pub(crate) fn invariant(
32    model: &Model,
33    trace: &Trace,
34    host: &TraceHost,
35    control: Option<&dyn HostControl>,
36) -> Result<(Validation, Option<InvariantErrorClass>), EvalError> {
37    let Ending::InvariantError { name, ec } = &trace.ending else {
38        return Ok((invalid("expected a named invariant error"), None));
39    };
40    let (validation, observed) = replay(
41        model,
42        trace,
43        host,
44        control,
45        |site, error, role, candidate| {
46            site == Site::Invariant
47                && role == Some(name.as_str())
48                && error.ec().name() == ec
49                && candidate == trace.states.last()
50        },
51    )?;
52    Ok((
53        validation,
54        observed.map(|deciding| InvariantErrorClass {
55            reported: 2111,
56            deciding,
57        }),
58    ))
59}
60
61pub(crate) fn view(
62    model: &Model,
63    trace: &Trace,
64    ec: &str,
65    endpoint: &ViewSourceEndpoint,
66    host: &TraceHost,
67    control: Option<&dyn HostControl>,
68) -> Result<Validation, EvalError> {
69    let (validation, deciding) = replay(model, trace, host, control, |site, error, _, _| {
70        site == Site::View
71            && error.ec().name() == ec
72            && endpoint.matches_error(&model.ir, error)
73            && reported(error, site) == Some(endpoint.reported_code())
74    })?;
75    if validation != Validation::Valid {
76        return Ok(validation);
77    }
78    Ok(if deciding == Some(endpoint.deciding_code()) {
79        Validation::Valid
80    } else {
81        invalid("VIEW diagnostic execution has a different deciding identity")
82    })
83}
84
85fn preflight(model: &Model, invariant: bool) -> Option<String> {
86    if let Some(feature) = model.unsupported.iter().find(|feature| {
87        !(invariant && feature.kind == dive_model::UnsupportedKind::TemporalProperty)
88    }) {
89        return Some(format!(
90            "ordered prefix unsupported model feature: {}",
91            feature.feature
92        ));
93    }
94    if model.symmetry.is_some()
95        || model.alias.is_some()
96        || !model.temporals.is_empty()
97        || !model.implied_temporals.is_empty() && !invariant
98    {
99        return Some(
100            "ordered prefix excludes unsupported roles, symmetry, ALIAS and temporal obligations"
101                .into(),
102        );
103    }
104    let impure = |pred: &dive_model::Pred| {
105        (!invariant
106            && model
107                .ir
108                .node(pred.expr)
109                .effects
110                .intersects(dive_ir::Effects::IMPURE))
111            || model.evaluator.scope_has_effects(&pred.scope)
112    };
113    if model
114        .init_actions
115        .iter()
116        .chain(&model.actions)
117        .any(|action| {
118            (!invariant
119                && model
120                    .ir
121                    .node(action.expr())
122                    .effects
123                    .intersects(dive_ir::Effects::IMPURE))
124                || model.evaluator.action_shares_side_effects(action)
125        })
126        || model
127            .constraints
128            .iter()
129            .chain(&model.action_constraints)
130            .chain(&model.invariants)
131            .chain(&model.implied_inits)
132            .chain(&model.implied_actions)
133            .chain(&model.view)
134            .any(|named| impure(&named.pred))
135    {
136        return Some("ordered prefix excludes effects and dynamically shared scopes".into());
137    }
138    None
139}
140
141fn simple_recurrences(model: &Model, initial: &State) -> bool {
142    model.implied_temporals.iter().all(|property| {
143        let pred = &property.pred;
144        if pred.scope.has_substitutions() {
145            return false;
146        }
147        let mut expression = pred.expr;
148        for _ in 0..16 {
149            let definition = match model.ir.expr(expression) {
150                dive_ir::Expr::Def(definition) => *definition,
151                dive_ir::Expr::Apply {
152                    callee: dive_ir::OpRef::Def(definition),
153                    args,
154                } if args.is_empty() => *definition,
155                _ => break,
156            };
157            if model.evaluator.redirected(definition) != definition
158                || model.evaluator.is_value_override(definition)
159            {
160                return false;
161            }
162            let definition = model.ir.def(definition);
163            if !definition.params.is_empty() || definition.recursive || definition.std.is_some() {
164                return false;
165            }
166            expression = definition.body;
167        }
168        let dive_ir::Expr::Always(eventually) = model.ir.expr(expression) else {
169            return false;
170        };
171        let dive_ir::Expr::Eventually(atom) = model.ir.expr(*eventually) else {
172            return false;
173        };
174        let dive_ir::Expr::Builtin {
175            op: dive_ir::BuiltinOp::Eq,
176            args,
177        } = model.ir.expr(*atom)
178        else {
179            return false;
180        };
181        if args.len() != 2 {
182            return false;
183        }
184        let pair = (model.ir.expr(args[0]), model.ir.expr(args[1]));
185        let (variable, literal) = match pair {
186            (dive_ir::Expr::Var { var, primed: false }, dive_ir::Expr::Num(literal))
187            | (dive_ir::Expr::Num(literal), dive_ir::Expr::Var { var, primed: false }) => {
188                (*var, literal)
189            }
190            _ => return false,
191        };
192        // Planning is a single nonconstant state recurrence. Its only source
193        // atom is total on the initial source, before this source's safety
194        // error prevents any row completion or temporal analysis.
195        literal.parse::<i32>().is_ok()
196            && matches!(
197                initial.get(variable.index()),
198                Some(Some(dive_value::Value::Int(_)))
199            )
200    })
201}
202
203#[allow(
204    clippy::too_many_lines,
205    reason = "one finite replay retains its actual admission and diagnostic history"
206)]
207fn replay(
208    model: &Model,
209    trace: &Trace,
210    host: &TraceHost,
211    control: Option<&dyn HostControl>,
212    matches: impl FnOnce(Site, &EvalError, Option<&str>, Option<&State>) -> bool,
213) -> Result<(Validation, Option<u32>), EvalError> {
214    let refuse = |reason| (Validation::Unsupported(reason), None);
215    let invariant = matches!(trace.ending, Ending::InvariantError { .. });
216    if let Some(reason) = preflight(model, invariant) {
217        return Ok(refuse(reason));
218    }
219    let source_index = trace
220        .states
221        .len()
222        .checked_sub(if invariant { 2 } else { 1 });
223    let Some(source) = source_index.and_then(|index| trace.states.get(index)) else {
224        return Ok(refuse(
225            "ordered replay needs an initial and terminal source".into(),
226        ));
227    };
228    let Some(initial) = trace.states.first() else {
229        return Ok(refuse("ordered replay needs an initial state".into()));
230    };
231    let mut history = History::default();
232    history.invariant = invariant;
233    let init = Driver {
234        initial: true,
235        model,
236        source: initial,
237        level: 0,
238        host,
239        control,
240    };
241    let (event, emitted) = init.primary_history(false, Some(&mut history))?;
242    if !matches!(event, Event::End) {
243        return Ok((event_validation(event), None));
244    }
245    if if invariant {
246        emitted == 0 || !history.admitted.contains(initial)
247    } else {
248        emitted != 1 || history.admitted.first() != Some(initial) || history.admitted.len() != 1
249    } {
250        return Ok(refuse(
251            if invariant {
252                "ordered invariant prefix needs exhausted Init and an admitted initial word state"
253            } else {
254                "ordered prefix needs exactly one exhausted, admitted Init emission"
255            }
256            .into(),
257        ));
258    }
259    if !model.implied_temporals.is_empty()
260        && (history.admitted.first() != Some(source)
261            || source != initial
262            || !simple_recurrences(model, &history.admitted[0]))
263    {
264        return Ok(refuse("invariant temporal configuration requires the first actually admitted initial source before any completed row and pure state recurrences".into()));
265    }
266    // The complete admission ledger is independently reconstructed. Word rows
267    // do not assert global newness or omit off-word siblings from the replay.
268    let mut index = 0;
269    let (terminal_source, terminal_level) = loop {
270        let Some(current) = history.admitted.get(index).cloned() else {
271            return Ok((
272                invalid("terminal source was not independently admitted"),
273                None,
274            ));
275        };
276        let level = history.levels[index];
277        if &current == source {
278            break (current, level);
279        }
280        let driver = Driver {
281            initial: false,
282            model,
283            source: &current,
284            level,
285            host,
286            control,
287        };
288        let (event, emitted) = driver.primary_history(false, Some(&mut history))?;
289        if !matches!(event, Event::End) {
290            return Ok((event_validation(event), None));
291        }
292        if emitted == 0 && model.settings.check_deadlock {
293            return Ok((
294                invalid(
295                    "an earlier independently expanded source deadlocks before the claimed error",
296                ),
297                None,
298            ));
299        }
300        index += 1;
301    };
302    // Equality selects the actual admitted object, never the word decoder's
303    // separately constructed receiver or its normalization lifetime.
304    let terminal = Driver {
305        initial: false,
306        model,
307        source: &terminal_source,
308        level: terminal_level,
309        host,
310        control,
311    };
312    let (event, _) = terminal.primary_history(false, Some(&mut history))?;
313    let Event::Error {
314        site,
315        error,
316        candidate,
317        name,
318    } = event
319    else {
320        return Ok((event_validation(event), None));
321    };
322    if !matches(site, &error, name.as_deref(), candidate.as_ref()) {
323        return Ok((
324            invalid(
325                "the first actual terminal error differs in site, role, cause, source or candidate",
326            ),
327            None,
328        ));
329    }
330    // A primary invariant's value-method receiver does not decide its class:
331    // insertion can make the diagnostic skip it entirely. Only an actually
332    // repeated diagnostic receiver requires its separate lifetime proof.
333    if !invariant && (error.value_method().is_some() || error.exception_kind().is_none()) {
334        return Ok(refuse(
335            "ordered prefix primary receiver/constructor lifetime is unproved".into(),
336        ));
337    }
338    let diagnostic = terminal.diagnostic_history(&mut history)?;
339    let error = match diagnostic {
340        Event::Error { error, .. } => error,
341        // TLC retains the original invariant wrapper when diagnostic execution
342        // completes or quietly stops at a false predicate/incomplete candidate.
343        Event::End
344        | Event::Failed {
345            check: Check::Invariant | Check::ImpliedAction,
346            ..
347        }
348        | Event::Partial { .. }
349            if invariant =>
350        {
351            terminal.poll()?;
352            return Ok((Validation::Valid, Some(2111)));
353        }
354        other => return Ok((event_validation(other), None)),
355    };
356    if error.value_method().is_some() {
357        return Ok(refuse(
358            "ordered prefix diagnostic receiver lifetime is unproved".into(),
359        ));
360    }
361    terminal.poll()?;
362    let deciding = match error.exception_kind() {
363        Some(ExceptionKind::ToolRuntime) => 2103,
364        Some(ExceptionKind::EvalException) => error.ec().code(),
365        None => {
366            return Ok(refuse(
367                "ordered prefix diagnostic constructor is unproved".into(),
368            ));
369        }
370    };
371    Ok((Validation::Valid, Some(deciding)))
372}
373
374fn reported(error: &EvalError, site: Site) -> Option<u32> {
375    if site == Site::Invariant {
376        return Some(2111);
377    }
378    match error.exception_kind()? {
379        ExceptionKind::ToolRuntime => Some(1000),
380        ExceptionKind::EvalException => Some(error.ec().code()),
381    }
382}
383fn event_validation(event: Event) -> Validation {
384    match event {
385        Event::Refused(reason) => Validation::Unsupported(reason),
386        Event::Failed { check, detail } => Validation::Invalid(Failure {
387            state: 1,
388            check,
389            detail,
390        }),
391        _ => invalid(
392            "an earlier error, incomplete candidate or completed expansion contradicts the terminal claim",
393        ),
394    }
395}
396fn invalid(detail: &str) -> Validation {
397    Validation::Invalid(Failure {
398        state: 1,
399        check: Check::Ending,
400        detail: detail.into(),
401    })
402}