1use 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#[derive(Clone, Debug)]
24pub struct ValidatedNativeCounterexample {
25 word: NativeWord,
26 exploration: capture::CompleteEvidence,
27 document: TraceDoc,
28 validation: ValidationReport,
29}
30
31impl ValidatedNativeCounterexample {
32 #[must_use]
34 pub const fn word(&self) -> &NativeWord {
35 &self.word
36 }
37
38 #[must_use]
40 pub const fn evidence(&self) -> &capture::CompleteEvidence {
41 &self.exploration
42 }
43
44 #[must_use]
46 pub const fn document(&self) -> &TraceDoc {
47 &self.document
48 }
49
50 #[must_use]
52 pub const fn validation(&self) -> &ValidationReport {
53 &self.validation
54 }
55}
56
57#[derive(Clone, Debug)]
59pub struct ValidatedNativePrefix {
60 word: NativeWord,
61 exploration: capture::PrefixEvidence,
62 document: TraceDoc,
63 validation: ValidationReport,
64}
65
66impl ValidatedNativePrefix {
67 #[must_use]
69 pub const fn word(&self) -> &NativeWord {
70 &self.word
71 }
72
73 #[must_use]
75 pub const fn evidence(&self) -> &capture::PrefixEvidence {
76 &self.exploration
77 }
78
79 #[must_use]
81 pub const fn document(&self) -> &TraceDoc {
82 &self.document
83 }
84
85 #[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 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
208pub(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 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
263pub(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
302pub(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#[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 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}