Skip to main content

dive_trace/
enabled.rs

1//! `ENABLED` and successor existence on a given state, decided by the
2//! dive-eval evaluator's `ENABLED`. The validator replays and checks the
3//! counterexample's states and steps itself; whether an action has some
4//! successor is decided with the shared evaluator, with a pure bounded TLA
5//! composition path and independent cache ownership.
6
7use std::sync::Arc;
8use std::sync::atomic::{AtomicBool, Ordering};
9
10use dive_eval::{Counter, Host, HostError, RunConfig};
11use dive_ir::StdOp;
12use dive_model::{Model, Pred};
13use dive_value::{Ctx, Value};
14
15use crate::State;
16
17/// Why `ENABLED` could not be decided. A refusal is never a decision.
18#[derive(Clone, Debug, PartialEq, Eq)]
19#[non_exhaustive]
20pub enum EnabledError {
21    /// A cooperative caller interruption, whose authority belongs to the driver.
22    Interrupted(dive_eval::EvalError),
23    /// A named feature or context the validator does not decide.
24    Unsupported(String),
25    /// A malformed state, or a TLC evaluation error raised by the search.
26    Invalid(String),
27}
28
29impl EnabledError {
30    /// Stable diagnostic code.
31    #[must_use]
32    pub fn code(&self) -> &'static str {
33        match self {
34            Self::Unsupported(_) => "DIVE-T0020",
35            Self::Invalid(_) => "DIVE-T0021",
36            Self::Interrupted(_) => "DIVE-T0022",
37        }
38    }
39}
40
41impl std::fmt::Display for EnabledError {
42    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
43        write!(f, "{}: ENABLED: ", self.code())?;
44        match self {
45            Self::Unsupported(s) => write!(f, "unsupported {s}"),
46            Self::Invalid(s) => write!(f, "invalid {s}"),
47            Self::Interrupted(error) => error.fmt(f),
48        }
49    }
50}
51
52impl std::error::Error for EnabledError {}
53
54/// Whether `action` has a successor from `state`: `ENABLED action`, or with
55/// `nonstuttering`, `ENABLED <<action>>_nonstuttering`, which is the
56/// enabledness that `WF`/`SF` refer to. `nonstuttering` is an expression in
57/// `action`'s scope.
58///
59/// ```
60/// use std::sync::Arc;
61/// use dive_model::Pred;
62/// use dive_value::Value;
63/// let src = "---- MODULE M ----\nEXTENDS Naturals\nVARIABLE x\nInit == x = 0\nNext == x < 2 /\\ x' = x + 1\n====\n";
64/// let analysis = dive_sema::analyze_source("M.tla", src, &Default::default());
65/// let ir = Arc::new(dive_ir::lower(&analysis)?);
66/// let cfg = dive_config::parse("INIT Init\nNEXT Next\n").into_config().unwrap();
67/// let model = dive_model::bind(ir, &cfg, &dive_model::BindOptions::tlc())?;
68/// let next = model.next.clone().unwrap();
69/// assert!(dive_trace::enabled::enabled(&model, &next, None, &Arc::from([Some(Value::from(1))]))?);
70/// assert!(!dive_trace::enabled::enabled(&model, &next, None, &Arc::from([Some(Value::from(2))]))?);
71/// # Ok::<(), Box<dyn std::error::Error>>(())
72/// ```
73///
74/// # Errors
75/// A foreign or malformed model context, state or predicate; an evaluation
76/// error or refusal during the search, including composition outside the pure
77/// bounded TLA slice ([`crate::COMPOSITION_UNSUPPORTED`]); and a
78/// string or model value created
79/// after binding ([`crate::RUNTIME_NAMES_UNSUPPORTED`]), whatever the result.
80pub fn enabled(
81    model: &Model,
82    action: &Pred,
83    nonstuttering: Option<dive_ir::ExprId>,
84    state: &State,
85) -> Result<bool, EnabledError> {
86    let unsupported = |e: dive_eval::EvalError| {
87        if e.class() == dive_eval::ErrorClass::Interrupted {
88            EnabledError::Interrupted(e)
89        } else {
90            EnabledError::Unsupported(e.to_string())
91        }
92    };
93    model.validate_context().map_err(unsupported)?;
94    model
95        .evaluator
96        .validate_predicate(&action.scope, action.expr)
97        .map_err(unsupported)?;
98    if let Some(sub) = nonstuttering {
99        model
100            .evaluator
101            .validate_predicate(&action.scope, sub)
102            .map_err(unsupported)?;
103    }
104    if state.len() != model.ir.vars().len() || state.iter().any(Option::is_none) {
105        return Err(EnabledError::Invalid(
106            "state does not assign every variable".into(),
107        ));
108    }
109    crate::trace::validate_state_names(model, state).map_err(EnabledError::Unsupported)?;
110    // A search that prints, reads checker state or shares lazy side effects
111    // with other evaluations is not a function of the given state.
112    let impure = |e: dive_ir::ExprId| {
113        model
114            .ir
115            .node(e)
116            .effects
117            .intersects(dive_ir::Effects::IMPURE)
118    };
119    if impure(action.expr)
120        || nonstuttering.is_some_and(impure)
121        || model.evaluator.scope_shares_side_effects(&action.scope)
122    {
123        return Err(EnabledError::Unsupported(
124            "side effects or dynamically bound constants in ENABLED".into(),
125        ));
126    }
127    let guard = ComposeGuard::install(model);
128    let result =
129        model
130            .evaluator
131            .enabled_scoped(&action.scope, action.expr, nonstuttering, state.clone());
132    let composed = guard.composed();
133    drop(guard);
134    if let Err(error) = &result
135        && error.class() == dive_eval::ErrorClass::Interrupted
136    {
137        return Err(EnabledError::Interrupted(error.clone()));
138    }
139    // A declined composition remains refused even if an inner query or label
140    // swallowed its error; accepted bounded composition never sets this flag.
141    if composed {
142        return Err(EnabledError::Unsupported(
143            crate::COMPOSITION_UNSUPPORTED.to_owned(),
144        ));
145    }
146    if model.has_runtime_names() {
147        return Err(EnabledError::Unsupported(
148            crate::RUNTIME_NAMES_UNSUPPORTED.to_owned(),
149        ));
150    }
151    result.map_err(|e| {
152        if e.class() == dive_eval::ErrorClass::Eval {
153            EnabledError::Invalid(e.to_string())
154        } else {
155            EnabledError::Unsupported(e.to_string())
156        }
157    })
158}
159
160/// Typed source-row query after independent canonical/context admission.
161pub(crate) fn source_enabled(
162    model: &Model,
163    action: &Pred,
164    nonstuttering: Option<dive_ir::ExprId>,
165    state: &State,
166) -> Result<bool, dive_eval::EvalError> {
167    model
168        .evaluator
169        .validate_predicate(&action.scope, action.expr)?;
170    if let Some(sub) = nonstuttering {
171        model.evaluator.validate_predicate(&action.scope, sub)?;
172    }
173    let guard = ComposeGuard::install(model);
174    let result =
175        model
176            .evaluator
177            .enabled_scoped(&action.scope, action.expr, nonstuttering, state.clone());
178    let composed = guard.composed();
179    drop(guard);
180    if let Err(error) = &result
181        && matches!(
182            error.class(),
183            dive_eval::ErrorClass::Interrupted
184                | dive_eval::ErrorClass::ResourceLimit
185                | dive_eval::ErrorClass::Bug
186        )
187    {
188        return Err(error.clone());
189    }
190    if composed {
191        return Err(dive_eval::EvalError::unsupported(
192            crate::COMPOSITION_UNSUPPORTED,
193        ));
194    }
195    if model.has_runtime_names() {
196        return Err(dive_eval::EvalError::unsupported(
197            crate::RUNTIME_NAMES_UNSUPPORTED,
198        ));
199    }
200    result
201}
202
203/// A private cache domain and bounded composition policy for an ENABLED or
204/// lasso evaluation. Existing host grants are forwarded; every declined
205/// composition is remembered, including errors swallowed by optional checks.
206/// A prior consumer's cached value never substitutes for this replay.
207#[derive(Debug)]
208struct ComposeGuardHost {
209    inner: Option<Arc<dyn Host>>,
210    composition: AtomicBool,
211    cache_domain: u64,
212}
213
214impl Host for ComposeGuardHost {
215    fn check_native_access(&self, op: StdOp) -> Result<(), HostError> {
216        self.inner
217            .as_ref()
218            .map_or(Ok(()), |h| h.check_native_access(op))
219    }
220
221    fn print_output(&self, text: &str) -> Result<bool, HostError> {
222        self.inner
223            .as_ref()
224            .map_or(Ok(true), |h| h.print_output(text))
225    }
226
227    fn check_tlc_access(&self, key: &str, write: bool) -> Result<(), HostError> {
228        self.inner
229            .as_ref()
230            .map_or(Ok(()), |h| h.check_tlc_access(key, write))
231    }
232
233    fn random(&self, op: StdOp, args: &[Value], ctx: Ctx) -> Option<Result<Value, HostError>> {
234        self.inner.as_ref().and_then(|h| h.random(op, args, ctx))
235    }
236
237    fn check_register_access(&self) -> Result<(), HostError> {
238        self.inner
239            .as_ref()
240            .map_or(Ok(()), |h| h.check_register_access())
241    }
242
243    fn check_action_composition(&self) -> Result<(), HostError> {
244        self.composition.store(true, Ordering::Relaxed);
245        Err(HostError {
246            code: 0,
247            message: crate::COMPOSITION_UNSUPPORTED.to_owned(),
248        })
249    }
250
251    fn requires_bounded_action_composition(&self) -> bool {
252        true
253    }
254
255    fn check_bounded_action_composition(&self) -> Result<(), HostError> {
256        let result = self
257            .inner
258            .as_ref()
259            .map_or(Ok(()), |host| host.check_bounded_action_composition());
260        if result.is_err() {
261            self.composition.store(true, Ordering::Relaxed);
262        }
263        result
264    }
265
266    fn expression_cache_domain(&self) -> u64 {
267        self.cache_domain
268    }
269
270    fn level(&self) -> Option<i64> {
271        self.inner.as_ref().and_then(|h| h.level())
272    }
273
274    fn successor_level(&self) -> Result<i64, HostError> {
275        self.inner.as_ref().map_or_else(
276            || {
277                Err(HostError {
278                    code: 0,
279                    message: dive_eval::PRIMED_LEVEL_UNSUPPORTED.to_owned(),
280                })
281            },
282            |h| h.successor_level(),
283        )
284    }
285
286    fn counter(&self, counter: Counter) -> Option<i64> {
287        self.inner.as_ref().and_then(|h| h.counter(counter))
288    }
289
290    fn config(&self) -> Option<RunConfig> {
291        self.inner.as_ref().and_then(|h| h.config())
292    }
293
294    fn request_exit(&self) -> bool {
295        // A side condition of a search is never a checker's exit request.
296        false
297    }
298}
299
300/// Installs a [`ComposeGuardHost`] for one search and restores the host
301/// installed before it when dropped.
302pub(crate) struct ComposeGuard<'a> {
303    model: &'a Model,
304    host: Arc<ComposeGuardHost>,
305    inner: Option<Arc<dyn Host>>,
306}
307
308impl<'a> ComposeGuard<'a> {
309    pub(crate) fn install(model: &'a Model) -> Self {
310        let inner = model.evaluator.host();
311        let cache_domain = inner
312            .as_ref()
313            .map(|h| h.expression_cache_domain())
314            .filter(|domain| *domain != 0)
315            .unwrap_or_else(crate::validate::next_cache_domain);
316        let host = Arc::new(ComposeGuardHost {
317            inner: inner.clone(),
318            composition: AtomicBool::new(false),
319            cache_domain,
320        });
321        let _installed_before = model.evaluator.replace_host(Some(host.clone()));
322        Self { model, host, inner }
323    }
324
325    pub(crate) fn composed(&self) -> bool {
326        self.host.composition.load(Ordering::Relaxed)
327    }
328}
329
330impl Drop for ComposeGuard<'_> {
331    fn drop(&mut self) {
332        let _ = self.model.evaluator.replace_host(self.inner.take());
333    }
334}