Skip to main content

dive_core/
lib.rs

1//! `dive-core`: Core, dive's compiled execution core for explicit-state
2//! model checking.
3//!
4//! Core turns a bound specification into a [`Plan`] and evaluates it over
5//! compact value handles instead of tree-walking the IR. [`compile()`] takes
6//! `dive_ir` plus the binder's [`Handoff`] (constants, roles and the
7//! definitions left to evaluate) and compiles every value expression and
8//! every action into flat node arrays. A [`Machine`] interprets those nodes
9//! over a [`Heap`]: persistent values live in a hash-consed, sharded
10//! [`Store`] shared by all workers, and each worker builds intermediate
11//! values in its own transient arena, released once a state is accepted.
12//! Successor generation follows TLC's `getNextStates` rules and hands each
13//! initial state and successor to a [`Sink`]; the exploration engine in
14//! `dive-explore` provides that sink and does the searching, storing and
15//! checking.
16//!
17//! Core serves both profiles, dive's default and `--compat=tlc`: it keeps
18//! TLC's evaluation order and error classes, supports either integer mode
19//! and either value order, and implements `SYMMETRY` reduction. Anything it
20//! does not implement exactly is refused before or during the run with an
21//! `unsupported` result naming the construct, never approximated.
22//!
23//! - [`handle`]: 64-bit tagged value words.
24//! - [`store`]: the hash-consed, sharded persistent store.
25//! - [`arena`]: the per-worker transient arena with epochs.
26//! - [`heap`]: hashing, equality, order, builders and interning.
27//! - [`int`]: integers of any size, in both integer modes.
28//! - [`mod@compile`]: the plan compiler from `dive_ir` plus the binder handoff.
29//! - [`eval`]: the interpreter for value nodes.
30//! - [`generate`]: TLC's successor-generation rules.
31//! - [`memo`]: keyed result caches.
32//! - [`opts`]: strategy switches for ablation.
33//!
34//! # Example
35//!
36//! ```
37//! use std::sync::Arc;
38//! use dive_core::{Handle, Heap, Store};
39//!
40//! let store = Arc::new(Store::default());
41//! let mut heap = Heap::new(store, false, false);
42//! let one = Handle::int(1).unwrap();
43//! let two = Handle::int(2).unwrap();
44//! let a = heap.set_from(&mut vec![two, one]);
45//! let b = heap.set_from(&mut vec![one, two, one]);
46//! assert!(heap.eq(a, b));
47//! let (pa, pb) = (heap.intern(a).unwrap(), heap.intern(b).unwrap());
48//! assert_eq!(pa, pb); // hash-consed
49//! ```
50#![forbid(unsafe_code)]
51
52pub mod arena;
53pub mod candidate_codec;
54mod compare;
55pub mod compile;
56pub mod convert;
57pub mod debug;
58pub mod eval;
59pub mod frontier_codec;
60pub mod generate;
61pub mod handle;
62pub mod heap;
63pub mod int;
64pub mod key;
65mod member_index;
66pub mod memo;
67pub mod node;
68pub mod opts;
69pub mod owned_exchange;
70pub mod plan;
71pub mod print;
72pub mod random;
73pub mod stdlib;
74pub mod store;
75pub mod strings;
76pub mod symmetry;
77
78pub use compile::{Handoff, Role, compile};
79pub use eval::Machine;
80pub use generate::Sink;
81pub use handle::Handle;
82pub use heap::Heap;
83pub use opts::Opts;
84pub use plan::Plan;
85pub use store::{Semantics, Store};
86
87/// What kind of failure an [`Error`] is.
88#[derive(Clone, Copy, Debug, PartialEq, Eq)]
89pub enum ErrorKind {
90    /// A construct or size the core does not implement: never a verdict.
91    Unsupported,
92    /// An evaluation error TLC would also raise, with its TLC class
93    /// ([`Error::tlc`]). The engine decides the reported site class.
94    Eval,
95    /// A bug in the core.
96    Internal,
97    /// Not an error: the sink ended the enumeration.
98    Stop,
99}
100
101/// An error of the core. Boxed, so that `Result<Handle, Error>` is two
102/// words and returns in registers on the interpreter's hot path.
103#[derive(Clone, Debug, PartialEq, Eq)]
104pub struct Error(Box<ErrorData>);
105
106/// The contents of an [`Error`].
107#[derive(Clone, Debug, PartialEq, Eq)]
108pub struct ErrorData {
109    /// The kind.
110    pub kind: ErrorKind,
111    /// What happened.
112    pub message: String,
113    /// TLC's class of an [`ErrorKind::Eval`] error, when the core knows it.
114    /// `None` is an unclassified error, which the engine must not report
115    /// as a verdict: it names it as unsupported instead.
116    pub tlc: Option<TlcClass>,
117}
118
119/// How TLC raises an evaluation error: its `EC` code and whether it is an
120/// `EvalException` (which a Java override passes through, and which the
121/// checker reports with its own code) or an `Assert.fail`.
122/// The site rules stay with the engine.
123#[derive(Clone, Copy, Debug, PartialEq, Eq)]
124pub struct TlcClass {
125    /// The `tlc2.output.EC` code: 1000 for `GENERAL`.
126    pub code: u32,
127    /// Whether TLC raises it as an `EvalException`.
128    pub eval_exception: bool,
129}
130
131impl TlcClass {
132    /// `Assert.fail(EC.GENERAL, ...)`, TLC's most common evaluation error.
133    pub const GENERAL: Self = Self {
134        code: 1000,
135        eval_exception: false,
136    };
137
138    /// An `EvalException` with `code`.
139    #[must_use]
140    pub const fn eval_exception(code: u32) -> Self {
141        Self {
142            code,
143            eval_exception: true,
144        }
145    }
146}
147
148impl Error {
149    fn new(kind: ErrorKind, message: String) -> Self {
150        Self(Box::new(ErrorData {
151            kind,
152            message,
153            tlc: None,
154        }))
155    }
156
157    /// An unsupported construct.
158    #[must_use]
159    pub fn unsupported(what: impl Into<String>) -> Self {
160        Self::new(ErrorKind::Unsupported, what.into())
161    }
162
163    /// An unclassified evaluation error: the core has not established that
164    /// TLC raises it, or with which class.
165    #[must_use]
166    pub fn eval(what: impl Into<String>) -> Self {
167        Self::new(ErrorKind::Eval, what.into())
168    }
169
170    /// An evaluation error of TLC class `tlc`.
171    ///
172    /// ```
173    /// use dive_core::{Error, TlcClass};
174    /// let e = Error::eval_class(TlcClass::eval_exception(2179), "The second argument of \\div is 0.");
175    /// assert_eq!(e.tlc(), Some(TlcClass { code: 2179, eval_exception: true }));
176    /// assert_eq!(Error::eval("x").tlc(), None);
177    /// ```
178    #[must_use]
179    pub fn eval_class(tlc: TlcClass, what: impl Into<String>) -> Self {
180        Self(Box::new(ErrorData {
181            kind: ErrorKind::Eval,
182            message: what.into(),
183            tlc: Some(tlc),
184        }))
185    }
186
187    /// TLC's class of an evaluation error the core has classified.
188    #[must_use]
189    pub fn tlc(&self) -> Option<TlcClass> {
190        self.0.tlc
191    }
192
193    /// An internal error.
194    #[must_use]
195    pub fn internal(what: impl Into<String>) -> Self {
196        Self::new(ErrorKind::Internal, what.into())
197    }
198
199    /// The sink's stop.
200    #[must_use]
201    pub fn stop() -> Self {
202        Self::new(ErrorKind::Stop, String::new())
203    }
204
205    /// The kind.
206    #[must_use]
207    pub fn kind(&self) -> ErrorKind {
208        self.0.kind
209    }
210
211    /// The message.
212    #[must_use]
213    pub fn message(&self) -> &str {
214        &self.0.message
215    }
216
217    /// The kind and the message.
218    #[must_use]
219    pub fn into_parts(self) -> (ErrorKind, String) {
220        (self.0.kind, self.0.message)
221    }
222}
223
224impl std::fmt::Display for Error {
225    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
226        f.write_str(&self.0.message)
227    }
228}
229
230impl std::error::Error for Error {}