Skip to main content

dive_store/
lib.rs

1//! `dive-store`: state storage for the model checker. It provides the
2//! state fingerprint and the exact-store key, the disk-backed seen-state set, the
3//! ordered frontier spill and the predecessor log Core's search uses.
4//!
5//! The crate depends on no other dive crate except `dive-value`, and has no
6//! `unsafe` code.
7//!
8//! # Overview
9//!
10//! - [`state`]: the state fingerprint (dive's two-level fingerprint in the default
11//!   profile, cached FP64 value fingerprints combined by a non-linear mixer chain;
12//!   TLC's own, in TLC's variable order, under `--compat=tlc`) and the canonical
13//!   exact-store key.
14//! - [`StoreMode`]: whether two states are the same by fingerprint or by
15//!   canonical key.
16//! - [`seen`]: the disk-backed seen-state set (`--seen disk`).
17//! - [`spill`]: the ordered, disk-spilled frontier.
18//! - [`predecessor`]: parent pointers and successor ordinals for counterexample
19//!   replay, in memory or on disk.
20//! - [`trace`]: the state ids and path steps the predecessor log returns.
21//!
22//! # Fingerprints and keys
23//!
24//! ```
25//! use dive_store::state::{StateFingerprinter, state_key};
26//! use dive_value::{Ctx, Int, Value};
27//!
28//! let ctx = Ctx::tlc();
29//! let fp = StateFingerprinter::new(0).ok_or("polynomial 0")?;
30//! // `1..3` and `{3, 2, 1}` are one state, whatever their representation.
31//! let a = [Value::interval(Int::from(1), Int::from(3), ctx)];
32//! let b = [Value::set(vec![Value::Int(3), Value::Int(2), Value::Int(1)], ctx)?];
33//! assert_eq!(fp.fingerprint(&a, ctx)?, fp.fingerprint(&b, ctx)?);
34//! let (mut ka, mut kb) = (Vec::new(), Vec::new());
35//! state_key(&a, ctx, &mut ka)?;
36//! state_key(&b, ctx, &mut kb)?;
37//! assert_eq!(ka, kb);
38//! # Ok::<(), Box<dyn std::error::Error>>(())
39//! ```
40#![forbid(unsafe_code)]
41
42mod collision;
43mod error;
44pub mod predecessor;
45pub mod seen;
46pub mod spill;
47pub mod state;
48pub mod trace;
49
50pub use error::StoreError;
51
52/// How a store decides that two states are the same.
53#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
54pub enum StoreMode {
55    /// 64-bit fingerprints: two distinct states may collide.
56    Fingerprint,
57    /// Full canonical state encodings: exhaustiveness is unconditional (charter
58    /// soundness rule 4).
59    Exact,
60}
61
62impl StoreMode {
63    /// The name used in output (`store: "fingerprint"` or `store: "exact"`).
64    #[must_use]
65    pub const fn name(self) -> &'static str {
66        match self {
67            Self::Fingerprint => "fingerprint",
68            Self::Exact => "exact",
69        }
70    }
71}