Skip to main content

dive_api/temporal/
native.rs

1//! Native temporal reports retain selected words and sealed facts, not graphs.
2
3use std::sync::Arc;
4use std::time::Instant;
5
6use dive_config::ModelConfig;
7use dive_ir::Ir;
8use dive_liveness::analyze::periodic::Checks;
9use dive_runtime::{CheckOptions, CheckResult, capture};
10use dive_trace::{
11    Ending, Report as ValidationReport, Trace, TraceDoc, Validation, ValidationRunError,
12};
13
14use super::{
15    Error, Failure, Outcome, Report, Stage, bind_controlled, core_file_configuration, core_report,
16    validate_native_document, validation_binding_failure, validation_checkpoint,
17    validation_control, validation_run_error,
18};
19use dive_liveness::analyze::ExplorationEvidence;
20use dive_liveness::analyze::periodic::external::{NativeAnalysis, NativeFinal, NativeWord};
21
22/// An independently validated native word from complete exploration.
23#[derive(Clone, Debug)]
24pub struct ValidatedNativeCounterexample {
25    word: NativeWord,
26    exploration: capture::CompleteEvidence,
27    document: TraceDoc,
28    validation: ValidationReport,
29}
30
31impl ValidatedNativeCounterexample {
32    /// Selected original states, edges, property names and loop position.
33    #[must_use]
34    pub const fn word(&self) -> &NativeWord {
35        &self.word
36    }
37
38    /// Actual exhausted producer facts, without retained graph rows.
39    #[must_use]
40    pub const fn evidence(&self) -> &capture::CompleteEvidence {
41        &self.exploration
42    }
43
44    /// Independently validated serialized native word.
45    #[must_use]
46    pub const fn document(&self) -> &TraceDoc {
47        &self.document
48    }
49
50    /// Independent serialized replay, always valid.
51    #[must_use]
52    pub const fn validation(&self) -> &ValidationReport {
53        &self.validation
54    }
55}
56
57/// An independently validated native word on a real unfinished prefix.
58#[derive(Clone, Debug)]
59pub struct ValidatedNativePrefix {
60    word: NativeWord,
61    exploration: capture::PrefixEvidence,
62    document: TraceDoc,
63    validation: ValidationReport,
64}
65
66impl ValidatedNativePrefix {
67    /// Selected original states, edges, property names and loop position.
68    #[must_use]
69    pub const fn word(&self) -> &NativeWord {
70        &self.word
71    }
72
73    /// Actual successful prefix facts, which cannot supply completion.
74    #[must_use]
75    pub const fn evidence(&self) -> &capture::PrefixEvidence {
76        &self.exploration
77    }
78
79    /// Independently validated serialized native word.
80    #[must_use]
81    pub const fn document(&self) -> &TraceDoc {
82        &self.document
83    }
84
85    /// Independent serialized replay, always valid.
86    #[must_use]
87    pub const fn validation(&self) -> &ValidationReport {
88        &self.validation
89    }
90}
91
92pub(super) fn facts(result: &CheckResult, stats: dive_runtime::Stats) -> ExplorationEvidence {
93    ExplorationEvidence {
94        stats,
95        workers: result.workers.clone(),
96        collision: result.collision.clone(),
97        output: result.output.clone(),
98        warnings: result.warnings.clone(),
99    }
100}
101
102fn interrupted(
103    control: &dive_runtime::budget::EvaluationControl,
104    error: ValidationRunError,
105) -> Failure {
106    let (error, progress) = validation_run_error(control, error);
107    let mut failure = Failure::before(error, Stage::Validation);
108    failure.validation_progress = progress.map(Box::new);
109    failure
110}
111
112fn rejected(word: &NativeWord, report: ValidationReport) -> Failure {
113    Failure::before(
114        Error::NativeValidation {
115            word: Box::new(word.clone()),
116            report,
117        },
118        Stage::Validation,
119    )
120}
121
122fn validate_word(
123    ir: &Arc<Ir>,
124    config: &ModelConfig,
125    options: &CheckOptions,
126    word: &NativeWord,
127) -> Result<(TraceDoc, ValidationReport), Failure> {
128    let control =
129        validation_control(options).map_err(|error| Failure::before(error, Stage::Validation))?;
130    validation_checkpoint(&control).map_err(|error| interrupted(&control, error))?;
131    // The source-bound model is fresh: retained native handles and its evaluator
132    // are unavailable to this independent typed and serialized replay.
133    let model =
134        bind_controlled(ir, config, options, &control).map_err(validation_binding_failure)?;
135    let trace = Trace {
136        states: word.states.clone(),
137        labels: vec![None; word.states.len()],
138        ending: Ending::Lasso {
139            back_to: word.back_to,
140        },
141        length: Some(word.states.len()),
142        properties: word.properties.clone(),
143    };
144    let report = dive_trace::validate_controlled(&model, &trace, control.clone())
145        .map_err(|error| interrupted(&control, error))?;
146    if report.validation != Validation::Valid {
147        return Err(rejected(word, report));
148    }
149    let document = trace
150        .to_doc(&model)
151        .map_err(|error| Failure::before(Error::Document(error), Stage::Document))?;
152    let report = validate_native_document(&model, &document, &control)
153        .map_err(|error| interrupted(&control, error))?;
154    if report.validation != Validation::Valid {
155        return Err(rejected(word, report));
156    }
157    Ok((document, report))
158}
159
160fn outcome(
161    ir: &Arc<Ir>,
162    config: &ModelConfig,
163    options: &CheckOptions,
164    analysis: NativeAnalysis,
165) -> Result<Outcome, Failure> {
166    match analysis {
167        NativeAnalysis::Final(NativeFinal::Holds(evidence)) => {
168            Ok(Outcome::NativeHolds(Box::new(evidence)))
169        }
170        NativeAnalysis::Final(NativeFinal::Candidate(word, evidence)) => {
171            let (document, validation) =
172                validate_word(ir, config, options, &word).map_err(|mut failure| {
173                    failure.exploration =
174                        Some(Box::new(facts(evidence.safety_result(), evidence.stats())));
175                    failure
176                })?;
177            Ok(Outcome::NativeViolation(Box::new(
178                ValidatedNativeCounterexample {
179                    word,
180                    exploration: evidence,
181                    document,
182                    validation,
183                },
184            )))
185        }
186        NativeAnalysis::Prefix(prefix) => {
187            let (document, validation) =
188                validate_word(ir, config, options, &prefix.word).map_err(|mut failure| {
189                    failure.exploration = Some(Box::new(facts(
190                        prefix.exploration.safety_result(),
191                        prefix.exploration.stats(),
192                    )));
193                    failure.incomplete = true;
194                    failure
195                })?;
196            Ok(Outcome::NativePrefixViolation(Box::new(
197                ValidatedNativePrefix {
198                    word: prefix.word,
199                    exploration: prefix.exploration,
200                    document,
201                    validation,
202                },
203            )))
204        }
205    }
206}
207
208/// Finishes the real native producer through the same independent proof boundary.
209pub(crate) fn core_native_report(
210    ir: &Arc<Ir>,
211    config: &ModelConfig,
212    options: &CheckOptions,
213    result: Result<(NativeAnalysis, Checks), dive_liveness::analyze::periodic::PeriodicFailure>,
214    periodic: bool,
215    symmetry_liveness: dive_model::SymmetryLivenessResolution,
216    started: Instant,
217) -> Result<Report, Failure> {
218    let (analysis, checks) = match result {
219        Ok(value) => value,
220        // Reuse the existing error/Safety transport. This branch constructs no
221        // graph or completed result, and retains the actual failure facts.
222        Err(failure) => {
223            let result = core_report(
224                ir,
225                config,
226                options,
227                failure,
228                periodic,
229                symmetry_liveness,
230                started,
231            );
232            return result
233                .map(|mut report| {
234                    report.configuration = Some(core_file_configuration());
235                    report
236                })
237                .map_err(|mut failure| {
238                    failure.configuration = Some(Box::new(core_file_configuration()));
239                    failure
240                });
241        }
242    };
243    match outcome(ir, config, options, analysis) {
244        Ok(outcome) => Ok(Report {
245            symmetry_liveness: Some(symmetry_liveness),
246            outcome,
247            options: options.clone(),
248            elapsed: started.elapsed(),
249            periodic: periodic.then_some(checks),
250            memory_samples: options.budget.memory_samples(),
251            configuration: Some(core_file_configuration()),
252        }),
253        Err(mut failure) => {
254            failure.elapsed = started.elapsed();
255            failure.periodic = periodic.then(|| Box::new(checks));
256            failure.configuration = Some(Box::new(core_file_configuration()));
257            failure.symmetry_liveness = Some(Box::new(symmetry_liveness));
258            Err(failure)
259        }
260    }
261}
262
263/// Retains the actual producer boundary when a checked capture factory is
264/// interrupted. No completion evidence is manufactured by this failure path.
265pub(crate) fn core_capture_stop(
266    verdict: dive_runtime::Verdict,
267    safety: &CheckResult,
268    completed: bool,
269    started: Instant,
270    checks: Option<Checks>,
271) -> Failure {
272    let error = match verdict {
273        dive_runtime::Verdict::Stopped(stopped) => {
274            dive_liveness::analyze::AnalysisError::Stopped(stopped)
275        }
276        dive_runtime::Verdict::BudgetMeasurement { error } => {
277            dive_liveness::analyze::AnalysisError::BudgetMeasurement(error)
278        }
279        dive_runtime::Verdict::ResourceLimit { .. } => {
280            dive_liveness::analyze::AnalysisError::Limit(
281                "native source-row allocation or evaluation resources",
282            )
283        }
284        dive_runtime::Verdict::Unsupported { feature } => {
285            dive_liveness::analyze::AnalysisError::UnsupportedValue(feature)
286        }
287        _ => dive_liveness::analyze::AnalysisError::Inconsistent("non-budget capture stop"),
288    };
289    let mut failure = Failure::before(
290        Error::Analysis(error),
291        Stage::Analysis(dive_liveness::analyze::Stage::Capture),
292    );
293    failure.exploration = safety.stats.map(|stats| Box::new(facts(safety, stats)));
294    failure.incomplete = !completed;
295    failure.elapsed = started.elapsed();
296    failure.periodic = checks.map(Box::new);
297    failure.configuration = Some(Box::new(core_file_configuration()));
298    failure.symmetry_liveness = safety.symmetry_liveness.clone().map(Box::new);
299    failure
300}
301
302/// A budget stop of Core's start-up work, found before the temporal route
303/// plans or captures: stage and phase `check-startup`, no capture,
304/// and the start-up output printed so far.
305pub(crate) fn core_startup_stop(
306    verdict: dive_runtime::Verdict,
307    started: Instant,
308    checks: Option<Checks>,
309    symmetry_liveness: dive_model::SymmetryLivenessResolution,
310    output: Vec<dive_model::Message>,
311) -> Failure {
312    let error = match verdict {
313        dive_runtime::Verdict::Stopped(stopped) => {
314            dive_liveness::analyze::AnalysisError::Stopped(stopped)
315        }
316        dive_runtime::Verdict::BudgetMeasurement { error } => {
317            dive_liveness::analyze::AnalysisError::BudgetMeasurement(error)
318        }
319        _ => dive_liveness::analyze::AnalysisError::Inconsistent("non-budget start-up stop"),
320    };
321    let mut failure = Failure::before(Error::Analysis(error), Stage::Startup);
322    failure.elapsed = started.elapsed();
323    failure.periodic = checks.map(Box::new);
324    failure.configuration = Some(Box::new(core_file_configuration()));
325    failure.symmetry_liveness = Some(Box::new(symmetry_liveness));
326    failure.binding_output = output;
327    failure
328}
329
330#[allow(
331    clippy::too_many_arguments,
332    reason = "same native producer and source-validation boundary"
333)]
334pub(crate) fn core_source_row_failure(
335    ir: &Arc<Ir>,
336    config: &ModelConfig,
337    options: &CheckOptions,
338    state: dive_liveness::analyze::StateEvaluation,
339    safety: &CheckResult,
340    checks: Option<Checks>,
341    started: Instant,
342) -> Failure {
343    let error = dive_liveness::analyze::AnalysisError::Atom {
344        property: state.property().into(),
345        source: Box::new(state.source().clone()),
346        detail: state.cause().to_string(),
347    };
348    let mut failure = Failure::before(
349        Error::Analysis(error),
350        Stage::Analysis(dive_liveness::analyze::Stage::Capture),
351    );
352    failure.exploration = safety.stats.map(|stats| Box::new(facts(safety, stats)));
353    failure.state_evaluation = Some(Box::new(state));
354    failure.incomplete = true;
355    failure.periodic = checks.map(Box::new);
356    failure.configuration = Some(Box::new(core_file_configuration()));
357    failure.symmetry_liveness = safety.symmetry_liveness.clone().map(Box::new);
358    let mut failure = super::finish_row_failure(ir, config, options, failure);
359    failure.elapsed = started.elapsed();
360    failure
361}
362
363/// Core's own temporal analysis of a model, recovered from its validated
364/// report: the final analysis, or with `prefix` the first due prefix of an
365/// every-level schedule. Test inputs replay the validation boundary on it.
366#[cfg(test)]
367#[allow(clippy::panic, reason = "test fixture producer")]
368pub(crate) fn core_analysis(
369    ir: &Arc<Ir>,
370    config: &ModelConfig,
371    options: &CheckOptions,
372    tlc: bool,
373    prefix: bool,
374) -> NativeAnalysis {
375    use dive_liveness::analyze::periodic::Schedule;
376    use dive_liveness::analyze::periodic::external::NativePrefix;
377    let opts = dive_core::Opts::default();
378    let prepared = crate::core_engine::prepare(ir, config, options, tlc, opts, true)
379        .unwrap_or_else(|r| panic!("core refused: {:?}", r.verdict));
380    let route = prefix.then_some(Schedule {
381        min_states: 2,
382        growth_factor: 1,
383    });
384    let outcome = crate::core_temporal::check(
385        ir,
386        config,
387        options,
388        (tlc, opts),
389        prepared,
390        route,
391        &mut crate::core_engine::CoreRun::default(),
392    );
393    let crate::core_engine::CoreOutcome::Temporal(report) = outcome else {
394        panic!("core temporal report: {outcome:?}")
395    };
396    match report.outcome {
397        Outcome::NativeHolds(evidence) => NativeAnalysis::Final(NativeFinal::Holds(*evidence)),
398        Outcome::NativeViolation(word) => {
399            NativeAnalysis::Final(NativeFinal::Candidate(word.word, word.exploration))
400        }
401        Outcome::NativePrefixViolation(word) => NativeAnalysis::Prefix(NativePrefix {
402            word: word.word,
403            exploration: word.exploration,
404        }),
405        Outcome::Safety(result) => panic!("native outcome: {result:?}"),
406    }
407}
408
409#[cfg(test)]
410#[allow(
411    clippy::expect_used,
412    clippy::panic,
413    reason = "actual finite producer and independent proof controls"
414)]
415mod tests {
416    use super::*;
417    use dive_liveness::analyze::AnalysisError;
418
419    /// Core's own analysis of a two-state model, so the validation boundary
420    /// can be replayed on it (or on a forged copy of it).
421    fn input(
422        tlc: bool,
423        holds: bool,
424        prefix: bool,
425    ) -> (Arc<Ir>, ModelConfig, CheckOptions, NativeAnalysis) {
426        let atom = if holds { "x<=1" } else { "x=2" };
427        let source = format!(
428            "---- MODULE NativeReport ----\nEXTENDS Naturals\nVARIABLE x\nInit == x=0\nNext == x'=1-x\nP == []<>({atom})\n====\n"
429        );
430        let parsed =
431            dive_sema::analyze_source("NativeReport.tla", &source, &dive_sema::Options::default());
432        assert!(parsed.accepted());
433        let ir = Arc::new(dive_ir::lower(&parsed).expect("IR"));
434        let config = dive_config::parse("INIT Init\nNEXT Next\nPROPERTY P\n")
435            .into_config()
436            .expect("config");
437        let mut options = if tlc {
438            CheckOptions::tlc(0, 0)
439        } else {
440            CheckOptions::dive(0)
441        };
442        options.workers = 1;
443        let analysis = core_analysis(&ir, &config, &options, tlc, prefix);
444        (ir, config, options, analysis)
445    }
446
447    #[test]
448    fn actual_final_and_prefix_words_require_fresh_typed_and_serialized_proof() {
449        for tlc in [false, true] {
450            let (ir, config, options, analysis) = input(tlc, true, false);
451            let Outcome::NativeHolds(evidence) =
452                outcome(&ir, &config, &options, analysis).expect("holding")
453            else {
454                panic!("native holds")
455            };
456            assert_eq!(evidence.stats().distinct, 2);
457            assert_eq!(evidence.stats().left_on_queue, 0);
458            for prefix in [false, true] {
459                let (ir, config, options, analysis) = input(tlc, false, prefix);
460                let actual =
461                    outcome(&ir, &config, &options, analysis).expect("validated native word");
462                match actual {
463                    Outcome::NativeViolation(word) => {
464                        assert!(!prefix);
465                        assert_eq!(word.validation().validation, Validation::Valid);
466                        assert_eq!(word.word().target_property, "P");
467                        assert_eq!(word.document().properties, ["P"]);
468                        assert_eq!(word.evidence().stats().left_on_queue, 0);
469                    }
470                    Outcome::NativePrefixViolation(word) => {
471                        assert!(prefix);
472                        assert_eq!(word.validation().validation, Validation::Valid);
473                        assert!(word.evidence().stats().left_on_queue > 0);
474                        assert_eq!(word.word().target_property, "P");
475                    }
476                    _ => panic!("native violation kind"),
477                }
478            }
479        }
480    }
481
482    #[test]
483    fn forged_word_is_not_promoted_and_keeps_actual_complete_or_prefix_facts() {
484        for prefix in [false, true] {
485            let (ir, config, options, mut analysis) = input(true, false, prefix);
486            let word = match &mut analysis {
487                NativeAnalysis::Final(NativeFinal::Candidate(word, _)) => word,
488                NativeAnalysis::Prefix(prefix) => &mut prefix.word,
489                NativeAnalysis::Final(_) => panic!("actual candidate"),
490            };
491            word.states[0] = Arc::from([Some(dive_value::Value::from(999))]);
492            let failure = outcome(&ir, &config, &options, analysis).expect_err("forged Init");
493            assert!(
494                matches!(failure.error(), Error::NativeValidation { report, .. } if matches!(report.validation, Validation::Invalid(_)))
495            );
496            assert_eq!(failure.incomplete, prefix);
497            assert!(failure.exploration.is_some());
498        }
499    }
500
501    #[test]
502    fn expired_validation_cannot_certify_a_native_word() {
503        for prefix in [false, true] {
504            let (ir, config, mut options, analysis) = input(true, false, prefix);
505            let watch = dive_runtime::budget::Budget::new(Some(std::time::Duration::ZERO), None)
506                .start()
507                .expect("watchdog")
508                .expect("armed");
509            options.budget = watch.budget().clone();
510            let failure =
511                outcome(&ir, &config, &options, analysis).expect_err("validation stopped");
512            assert!(matches!(
513                failure.error(),
514                Error::Analysis(AnalysisError::Stopped(_))
515            ));
516            assert_eq!(failure.incomplete, prefix);
517            assert_eq!(
518                failure
519                    .validation_progress
520                    .expect("real progress")
521                    .checks_passed,
522                0
523            );
524            assert!(failure.exploration.is_some());
525        }
526    }
527}