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}