Skip to main content

dive_model/
lib.rs

1//! `dive-model`: binding a specification to its TLC model configuration.
2//!
3//! This is a port of TLC's `tlc2.tool.impl.SpecProcessor` (tlaplus
4//! `94d0c50`), with the parts of `Spec` and `Tool` that finish setting up a
5//! model. [`bind`] takes the lowered specification and the parsed
6//! configuration and does what TLC does before it checks the assumptions, in
7//! TLC's order:
8//!
9//! 1. **Literals** (`processConstants`): a numeral too big for `--int=tlc` or
10//!    a decimal stops TLC first.
11//! 2. **Names** ([`mod@intern`]): the run's name table is filled in TLC's
12//!    encounter order, so that strings and model values order and
13//!    fingerprint as in TLC.
14//! 3. **Constants and overrides** (`processSpec`): every root constant must be
15//!    assigned (`C = v`) or substituted (`C <- D`); `Op = v` and `Op <- D`
16//!    replace definitions; `[M]` entries replace definitions of module `M`.
17//!    Errors carry TLC's codes ([`Ec`]).
18//! 4. **Constant definitions** (`processConstantDefns`): every zero-arity
19//!    definition TLC's level bound ([`mod@level`]) finds constant is
20//!    evaluated at start-up, module by module, and its value is used from
21//!    then on. `Print` output appears here, as in TLC.
22//! 5. **Roles** (`processConfig`): invariants, the behavior specification
23//!    (`INIT`/`NEXT` or `SPECIFICATION`, split into initial predicates, the
24//!    next-state relation and temporal formulas), properties (split into
25//!    invariants, implied initial predicates, implied actions and temporal
26//!    properties), constraints, `VIEW`.
27//! 6. **Actions** (`Tool.getActions`): the next-state relation split into
28//!    TLC's actions, with their labels, as `dive_eval::next` actions.
29//!
30//! The result is a [`Model`]: an [`dive_eval::Evaluator`] with everything
31//! bound, and every role as a [`Pred`] (an expression and the scope TLC
32//! evaluates it in). Features dive does not check yet (liveness, `SYMMETRY`,
33//! operators it does not implement) are listed in [`Model::unsupported`];
34//! the checker refuses such a model by name. Anything this stage cannot do
35//! exactly is an [`ErrorKind::Unsupported`] error.
36//!
37//! # Java overrides and loaded modules
38//!
39//! Which Java implementation TLC uses for a standard operator depends on the
40//! modules loaded: `Integers`' methods replace `Naturals`' when both are
41//! loaded. The IR records the active override of every definition, computed
42//! from the loaded modules (`dive_ir::std_op`). TLC's `-dumpTrace json`
43//! loads `_JsonTrace`, and with it `Integers`, without extending the root
44//! module; `dive_sema::Options::extra_root_extendees` reproduces that for
45//! oracle comparison (see [`DUMP_TRACE_JSON_MODULES`]).
46//!
47//! # Example
48//!
49//! ```
50//! use std::sync::Arc;
51//! use dive_model::{bind, BindOptions};
52//!
53//! let src = "---- MODULE M ----\nEXTENDS Naturals, TLC\nCONSTANT N\nVARIABLE x\n\
54//!            Max == Print(N, N * 2)\nInit == x = 0\nNext == x < Max /\\ x' = x + 1\n\
55//!            Inv == x <= Max\n====\n";
56//! let analysis = dive_sema::analyze_source("M.tla", src, &dive_sema::Options::default());
57//! let ir = Arc::new(dive_ir::lower(&analysis).unwrap());
58//! let cfg = dive_config::parse("CONSTANT N = 3\nINIT Init\nNEXT Next\nINVARIANT Inv\n")
59//!     .into_config()
60//!     .unwrap();
61//! let model = bind(ir, &cfg, &BindOptions::tlc()).unwrap();
62//! // `Max` is evaluated once, at start-up, as TLC does.
63//! assert_eq!(model.output, [dive_model::Message::Print("3  6".to_owned())]);
64//! assert_eq!(model.invariants[0].name, "Inv");
65//! assert_eq!(model.actions.len(), 1);
66//! assert!(model.actions[0].label().starts_with("<Next line 7, col 9 to line 7, col"));
67//! ```
68#![forbid(unsafe_code)]
69
70mod actions;
71mod bind;
72mod control;
73mod defer;
74mod error;
75pub mod intern;
76pub mod level;
77mod model;
78mod periodic;
79mod randomness;
80mod reach;
81mod spec;
82pub mod symmetry;
83mod tables;
84mod tlc_names;
85mod walk;
86
87use std::sync::Arc;
88
89use dive_config::ModelConfig;
90use dive_ir::Ir;
91
92pub use bind::{BindOptions, HANOI_BITS_CLASS_SHA256, local_java_class_digests};
93pub use control::ControlledBindError;
94pub use error::{BindError, Ec, ErrorKind, Failure, Message};
95pub use model::{Init, Model, Named, Pred, Settings, Unsupported, UnsupportedKind};
96pub use randomness::transformed_randomness;
97pub use reach::TLC_CDOT;
98pub use symmetry::{SymmetryLiveness, SymmetryLivenessResolution};
99
100/// Immutable inputs for reconstructing a model's startup runtime.
101///
102/// Rebinding creates a fresh interner, evaluator Core, registers and caches;
103/// no values or scopes from an already bound model are retained.
104#[derive(Clone, Debug)]
105pub struct Recipe {
106    ir: Arc<Ir>,
107    config: ModelConfig,
108    options: dive_eval::Options,
109    no_deadlock: bool,
110    symmetry_liveness: SymmetryLiveness,
111}
112
113impl Recipe {
114    /// Retains the original lowered source, configuration and value semantics.
115    #[must_use]
116    pub fn new(
117        ir: Arc<Ir>,
118        config: ModelConfig,
119        options: dive_eval::Options,
120        no_deadlock: bool,
121    ) -> Self {
122        Self {
123            ir,
124            config,
125            options,
126            no_deadlock,
127            symmetry_liveness: SymmetryLiveness::Refuse,
128        }
129    }
130
131    /// Whether the source/config inventory may invoke a native random operator.
132    /// This conservative query evaluates nothing and grants no runtime or proof
133    /// authority. Fresh finite replay uses it to preserve actual source-bound
134    /// action captures without constructing actions for ordinary pure words.
135    ///
136    /// ```
137    /// # fn inspect(recipe: &dive_model::Recipe) {
138    /// let _may_draw = recipe.has_randomness();
139    /// # }
140    /// ```
141    #[must_use]
142    pub fn has_randomness(&self) -> bool {
143        randomness::source_randomness(&self.ir, &self.config)
144    }
145
146    /// Retains an explicit independent binding policy for temporal symmetry.
147    /// The plain constructor refuses periodic symmetry unless this is selected.
148    ///
149    /// ```
150    /// # fn example(recipe: dive_model::Recipe) {
151    /// let recipe = recipe.with_symmetry_liveness(dive_model::SymmetryLiveness::Unreduced);
152    /// # let _ = recipe;
153    /// # }
154    /// ```
155    #[must_use]
156    pub fn with_symmetry_liveness(mut self, policy: SymmetryLiveness) -> Self {
157        self.symmetry_liveness = policy;
158        self
159    }
160
161    /// Repeats the real binder's complete startup operation with a new runtime.
162    /// The host is installed before any constant definition is evaluated.
163    /// Checker action construction is omitted; the result carries source
164    /// predicates only.
165    ///
166    /// # Errors
167    /// The ordinary binding errors. Randomness combined with VIEW or SYMMETRY
168    /// refuses after structural checks and before any startup evaluation, using
169    /// the shared [`transformed_randomness`] policy.
170    pub fn bind(&self, host: Arc<dyn dive_eval::Host>) -> Result<Model, Box<Failure>> {
171        bind_in(
172            self.ir.clone(),
173            &self.config,
174            &BindOptions {
175                eval: self.options,
176                symmetry_liveness: self.symmetry_liveness,
177                no_deadlock: self.no_deadlock,
178                host: Some(host),
179            },
180            true,
181            None,
182            false,
183        )
184        .map_err(ControlledBindError::into_uncontrolled)
185    }
186
187    /// Repeats startup with a separate typed evaluator control capability.
188    ///
189    /// Structural preprocessing and evaluator construction remain uninterruptible.
190    /// The capability covers evaluator loop checkpoints during constant evaluation
191    /// and role binding; it is removed before the fresh model is returned.
192    ///
193    /// # Errors
194    /// Ordinary binding failures, typed interruption, or control registration failure.
195    pub fn bind_controlled(
196        &self,
197        host: Arc<dyn dive_eval::Host>,
198        control: Arc<dyn dive_eval::HostControl>,
199    ) -> Result<Model, ControlledBindError> {
200        bind_in(
201            self.ir.clone(),
202            &self.config,
203            &BindOptions {
204                eval: self.options,
205                symmetry_liveness: self.symmetry_liveness,
206                no_deadlock: self.no_deadlock,
207                host: Some(host),
208            },
209            true,
210            Some(control),
211            false,
212        )
213    }
214
215    /// Configuration model values, as text rather than interner atoms.
216    #[must_use]
217    pub fn model_values(&self) -> &[String] {
218        &self.config.model_values
219    }
220
221    /// Reconstructs a fresh predicate-only model with fallible error transport.
222    /// Intrinsic evaluator resource/internal errors retain their original type
223    /// and startup output. No synthetic control or resource policy is installed
224    /// when `control` is absent; the plain binding methods remain unchanged.
225    ///
226    /// # Errors
227    /// Ordinary binding failures, original evaluator failures/interruption, or
228    /// conflicting control ownership. No model exists on failure.
229    pub fn bind_fallible(
230        &self,
231        host: Arc<dyn dive_eval::Host>,
232        control: Option<Arc<dyn dive_eval::HostControl>>,
233    ) -> Result<Model, ControlledBindError> {
234        self.bind_replay(host, control, true)
235    }
236
237    /// Reconstructs a fresh runtime including the real ordered Next actions.
238    /// This carries no checker state, counters, store or execution evidence.
239    ///
240    /// ```no_run
241    /// # fn reconstruct(recipe: &dive_model::Recipe, host: std::sync::Arc<dyn dive_eval::Host>) {
242    /// let fresh = recipe.bind_next_fallible(host, None);
243    /// # let _ = fresh;
244    /// # }
245    /// ```
246    ///
247    /// # Errors
248    /// As [`Self::bind_fallible`], including action construction failures and
249    /// the same pre-startup refusal of randomness under VIEW or SYMMETRY.
250    pub fn bind_next_fallible(
251        &self,
252        host: Arc<dyn dive_eval::Host>,
253        control: Option<Arc<dyn dive_eval::HostControl>>,
254    ) -> Result<Model, ControlledBindError> {
255        self.bind_replay(host, control, false)
256    }
257
258    fn bind_replay(
259        &self,
260        host: Arc<dyn dive_eval::Host>,
261        control: Option<Arc<dyn dive_eval::HostControl>>,
262        predicate_only: bool,
263    ) -> Result<Model, ControlledBindError> {
264        bind_in(
265            self.ir.clone(),
266            &self.config,
267            &BindOptions {
268                eval: self.options,
269                symmetry_liveness: self.symmetry_liveness,
270                no_deadlock: self.no_deadlock,
271                host: Some(host),
272            },
273            predicate_only,
274            control,
275            true,
276        )
277    }
278}
279
280/// The modules TLC's `-dumpTrace json <file>` loads in addition to the
281/// specification's own (`TLC.java` adds the `_JsonTrace` post-condition, and
282/// `ParameterizedSpecObj` makes SANY load `_JsonTrace` as if the root module
283/// extended it). Pass it as `dive_sema::Options::extra_root_extendees` to
284/// reproduce the conformance harness's TLC runs, which use `-dumpTrace json`:
285/// it changes which Java overrides are active (`Integers` replaces
286/// `Naturals`' arithmetic) and the encounter order of names. TLC as users
287/// run it, and so `--compat=tlc`, does not load them. Oracle reproduction
288/// only, until the goldens are regenerated without `-dumpTrace` (issue #35).
289pub const DUMP_TRACE_JSON_MODULES: &[&str] = &["_JsonTrace"];
290
291/// Binds `ir` to `cfg` as TLC does (see the crate documentation).
292///
293/// # Errors
294/// TLC's error for the model, with what TLC printed before it; or an
295/// unsupported feature or an internal error, which are never verdicts.
296pub fn bind(ir: Arc<Ir>, cfg: &ModelConfig, opts: &BindOptions) -> Result<Model, Box<Failure>> {
297    bind_in(ir, cfg, opts, false, None, false).map_err(ControlledBindError::into_uncontrolled)
298}
299
300/// Binds `ir` to `cfg` for Core: as [`bind`], except that the pure
301/// constant-level definitions used only as values by the roles the core
302/// compiles are not evaluated at start-up. They are listed in
303/// [`Model::deferred_constants`], for the core to evaluate when it compiles
304/// its plan; the model's own evaluator evaluates them lazily wherever it
305/// needs them, with the same values. The root module's pure `ASSUME`s are
306/// listed in [`Model::deferred_assumptions`]: the core evaluates them when
307/// it compiles its plan, and [`Model::check_assumptions_except`] checks the
308/// others. With genuine temporal properties, the definitions those
309/// properties, the specification's fairness and the configured properties
310/// reach are evaluated at start-up as [`bind`] evaluates them, for the
311/// dive-eval evaluator that checks them; the core keeps the others.
312///
313/// # Errors
314/// As [`bind`].
315pub fn bind_deferring_constants(
316    ir: Arc<Ir>,
317    cfg: &ModelConfig,
318    opts: &BindOptions,
319) -> Result<Model, Box<Failure>> {
320    bind_in_deferring(ir, cfg, opts, false, None, false, true)
321        .map_err(ControlledBindError::into_uncontrolled)
322}
323
324/// Binds a fresh model with typed cooperative evaluator control.
325///
326/// The capability is installed after structural configuration validation and
327/// real evaluator construction. It covers existing evaluator loop checkpoints,
328/// not every structural, quiet-value or bulk startup operation.
329///
330/// ```
331/// use std::sync::Arc;
332/// use dive_eval::{HostControl, Interrupted};
333/// #[derive(Debug)]
334/// struct Continue;
335/// impl HostControl for Continue {
336///     fn check(&self) -> Result<(), Interrupted> { Ok(()) }
337/// }
338/// # fn example(ir: Arc<dive_ir::Ir>, cfg: &dive_config::ModelConfig) {
339/// let result = dive_model::bind_controlled(ir, cfg,
340///     &dive_model::BindOptions::tlc(), Arc::new(Continue));
341/// # let _ = result;
342/// # }
343/// ```
344///
345/// # Errors
346/// Ordinary binding failures, original typed interruption with startup output,
347/// an intrinsic resource/internal failure of optional proof planning, or a
348/// control registration conflict. The caller classifies run exhaustion.
349pub fn bind_controlled(
350    ir: Arc<Ir>,
351    cfg: &ModelConfig,
352    opts: &BindOptions,
353    control: Arc<dyn dive_eval::HostControl>,
354) -> Result<Model, ControlledBindError> {
355    bind_in(ir, cfg, opts, false, Some(control), false)
356}
357
358fn bind_in(
359    ir: Arc<Ir>,
360    cfg: &ModelConfig,
361    opts: &BindOptions,
362    predicates_only: bool,
363    control: Option<Arc<dyn dive_eval::HostControl>>,
364    fallible_errors: bool,
365) -> Result<Model, ControlledBindError> {
366    bind_in_deferring(
367        ir,
368        cfg,
369        opts,
370        predicates_only,
371        control,
372        fallible_errors,
373        false,
374    )
375}
376
377#[allow(
378    clippy::too_many_arguments,
379    reason = "existing binder ownership inputs plus the core route's deferral switch"
380)]
381fn bind_in_deferring(
382    ir: Arc<Ir>,
383    cfg: &ModelConfig,
384    opts: &BindOptions,
385    predicates_only: bool,
386    control: Option<Arc<dyn dive_eval::HostControl>>,
387    fallible_errors: bool,
388    defer: bool,
389) -> Result<Model, ControlledBindError> {
390    dive_eval::validate_ir(&ir).map_err(|error| {
391        Box::new(Failure {
392            error: BindError::unsupported(error.to_string()),
393            output: Vec::new(),
394        })
395    })?;
396    // Fallible binding is Recipe replay, including its ordered-action form.
397    // Reconstructing actions does not waive independent replay's pre-startup
398    // admission policy, even when a random reference is unused.
399    if (predicates_only || fallible_errors)
400        && let Some(feature) = transformed_randomness(&ir, cfg)
401    {
402        return Err(Box::new(Failure {
403            error: BindError::unsupported(feature),
404            output: Vec::new(),
405        })
406        .into());
407    }
408    let walk = {
409        let t = tables::Tables::new(ir.clone()).map_err(|error| {
410            Box::new(Failure {
411                error,
412                output: Vec::new(),
413            })
414        })?;
415        walk::process_constants(&t, opts.eval.ctx.int_mode)
416    };
417    let ir: Arc<Ir> = ir;
418    if let Some(error) = walk.error {
419        return Err(Box::new(Failure {
420            error,
421            output: Vec::new(),
422        })
423        .into());
424    }
425    let feed = intern::feed(&ir, cfg);
426    let names = Arc::new(feed);
427    let mut b = bind::Binder::new(ir, cfg, opts, names, control, fallible_errors)
428        .map_err(|error| error.with_output(Vec::new()))?;
429    if defer && !predicates_only {
430        b.defer = Some(defer::Deferral {
431            skip: std::collections::HashSet::new(),
432            evaluate: std::collections::HashSet::new(),
433            assumptions: Vec::new(),
434        });
435    }
436    let result = run(&mut b, predicates_only);
437    b.drain_prints();
438    match result {
439        Ok(model) => Ok(model),
440        Err(error) => Err(error.with_output(std::mem::take(&mut b.output))),
441    }
442}
443
444#[allow(clippy::too_many_lines, reason = "ordered binding phases")]
445fn run(b: &mut bind::Binder<'_>, predicates_only: bool) -> bind::R<Model> {
446    b.process_spec()?;
447    // SpecProcessor snapshots defns immediately after processSpec, before
448    // constant definitions replace their entries with values.
449    let periodic_definition = b
450        .cfg
451        .periodic
452        .as_ref()
453        .and_then(|n| b.defns.get(&n.text).cloned());
454    // Tool.getSymmetryPerms uses the definition table before constant
455    // definitions become values (SpecProcessor.snapshot).
456    let symmetry_definition = b
457        .cfg
458        .symmetry
459        .as_ref()
460        .and_then(|n| b.defns.get(&n.text).cloned());
461    b.build_evaluator()?;
462    // Evaluator construction completes configuration-arity validation without
463    // executing predicates. Refuse unknown classes before constant definitions,
464    // ASSUMEs or configured roles can run their unlike TLA fallback.
465    if let Some(feature) = b.unsupported.first() {
466        return Err(BindError::unsupported(feature.clone()).into());
467    }
468    // Own this fresh evaluator's capability only through binding. The guard
469    // drops before a caller registers search, ASSUME, or validation control.
470    let _control = b
471        .control
472        .as_ref()
473        .map(|control| b.ev().host_control(Some(control.clone())))
474        .transpose()?;
475    if let Some(control) = &b.control {
476        control.check().map_err(|interruption| {
477            control::StepError::Interrupted(dive_eval::EvalError::interrupted(interruption))
478        })?;
479    }
480    b.process_constant_defns()?;
481    b.process_config()?;
482    if let Some(name) = &b.cfg.periodic {
483        // Bound with TLC's errors, then refused: dive does not run the hook.
484        periodic::resolve(b, &name.text, periodic_definition.as_ref())?;
485        return Err(BindError::unsupported("_PERIODIC").into());
486    }
487    let view = b.process_view()?;
488    let (init_actions, actions) = if predicates_only {
489        (Vec::new(), Vec::new())
490    } else {
491        (b.init_actions()?, b.expand_actions()?)
492    };
493    b.drain_prints();
494    let ir = b.t.ir.clone();
495    let assumptions = non_axiom_assumptions(&ir);
496    let alias = b
497        .process_alias()
498        .map(|result| match result {
499            Ok(alias) => Ok(Ok(alias)),
500            Err(error) => error.ordinary().map(Err),
501        })
502        .transpose()?;
503    let postconditions = match b.process_postconditions() {
504        Ok(predicates) => Ok(predicates),
505        Err(error) => Err(error.ordinary()?),
506    };
507    let symmetry_liveness = SymmetryLivenessResolution::new(
508        b.opts.symmetry_liveness,
509        b.cfg.symmetry.as_ref().map(|name| name.text.clone()),
510        !b.implied_temporals.is_empty(),
511    );
512    let mut model = Model {
513        ir: ir.clone(),
514        evaluator: b.ev().clone(),
515        names: b.names.clone(),
516        // Keep startup output with the error owner until optional proof
517        // classification succeeds. A late intrinsic failure still needs it.
518        output: Vec::new(),
519        init: std::mem::take(&mut b.init),
520        next: b.next.clone(),
521        init_actions,
522        actions,
523        invariants: std::mem::take(&mut b.invariants),
524        implied_inits: std::mem::take(&mut b.implied_inits),
525        implied_actions: std::mem::take(&mut b.implied_actions),
526        temporals: std::mem::take(&mut b.temporals),
527        implied_temporals: std::mem::take(&mut b.implied_temporals),
528        implied_temporal_action_names: std::mem::take(&mut b.implied_temporal_action_names),
529        configured_properties: std::mem::take(&mut b.configured_properties),
530        constraints: std::mem::take(&mut b.constraints),
531        action_constraints: std::mem::take(&mut b.action_constraints),
532        view,
533        alias,
534        postconditions,
535        symmetry: b.cfg.symmetry.as_ref().map(|n| n.text.clone()),
536        symmetry_definition,
537        symmetry_liveness,
538        symmetry_reduction: None,
539        settings: model::Settings {
540            check_deadlock: b.cfg.checks_deadlock() && !b.opts.no_deadlock,
541        },
542        assumptions,
543        unsupported: Vec::new(),
544        sequential: Vec::new(),
545        sequential_names_only: false,
546        runtime_name_order: false,
547        stateful_checking: None,
548        deferred_constants: std::mem::take(&mut b.deferred),
549        deferred_assumptions: b
550            .defer
551            .as_ref()
552            .map(|d| d.assumptions.clone())
553            .unwrap_or_default(),
554    };
555    // The temporal route's reference evaluation needs the start-up values
556    // of what it reaches: the binder evaluates those, as TLC does, and the
557    // core keeps the rest.
558    for d in b.keep_temporal_startup_values(&model)? {
559        model.deferred_constants.remove(&d);
560    }
561    model.unsupported = reach::unsupported(b, &model);
562    let sequential = reach::sequential(b, &model)?;
563    model.sequential = sequential.reasons;
564    model.sequential_names_only = sequential.names_only;
565    model.runtime_name_order = sequential.runtime_names;
566    model.stateful_checking = sequential.stateful_checking;
567    model.output = std::mem::take(&mut b.output);
568    model.seal_startup_names();
569    Ok(model)
570}
571
572fn non_axiom_assumptions(ir: &Ir) -> Vec<dive_ir::DefId> {
573    let root = ir.module(ir.root());
574    root.assumptions
575        .iter()
576        .zip(root.axioms.iter().chain(std::iter::repeat(&false)))
577        .filter(|(_, ax)| !**ax)
578        .map(|(d, _)| *d)
579        .collect()
580}