Skip to main content

dive_explore/
ending.rs

1//! Error endings.
2//!
3//! The explorer records where an evaluation error was raised, with the
4//! states involved, and stops. It does not classify the error: the caller
5//! does, by the site, as TLC does (`dive-runtime`'s `class.rs`).
6//!
7//! An invariant that fails to evaluate on a new successor inside the model
8//! is followed by TLC's call-stack replay (`ModelChecker.modelCheckImpl`,
9//! `keepCallStack`). The
10//! replay expands the parent again, each action in full before its
11//! successors are checked. Past the failing successor, it inserts new states
12//! (counted as distinct, not as generated), checks them and queues them,
13//! until a violation or an incomplete state ends it quietly, or a further
14//! error ends it with that error's site.
15
16use dive_core::plan::Code;
17use dive_core::{Error, ErrorKind, Handle, Machine, Sink};
18
19use crate::{Explorer, state_identity};
20
21/// Where an evaluation error was raised.
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
23pub enum Site {
24    /// While generating the initial states.
25    Init,
26    /// While generating the successors of a state, in the action at this
27    /// index of [`dive_core::Plan::next`].
28    Next(usize),
29    /// In the `CONSTRAINT` at this index, on [`Failure::state`].
30    Constraint(usize),
31    /// In the `ACTION_CONSTRAINT` at this index, on the step to
32    /// [`Failure::state`].
33    ActionConstraint(usize),
34    /// In the invariant at this index, on [`Failure::state`].
35    Invariant(usize),
36    /// In the implied initial predicate at this index, on the initial
37    /// [`Failure::state`].
38    ImpliedInit(usize),
39    /// In the implied action at this index, on the step to
40    /// [`Failure::state`].
41    ImpliedAction(usize),
42    /// [`Failure::state`] leaves variables unassigned (not an evaluation
43    /// error, but an ending with the same shape).
44    Incomplete,
45    /// [`Failure::state`], a new state inside the model, holds a set TLC
46    /// cannot fingerprint, such as `Nat` (TLC's `fingerPrint` error).
47    Fingerprint,
48    /// In the `VIEW`, on [`Failure::state`], a new state inside the model.
49    View,
50}
51
52/// An evaluation error that ended the search, or the search's replay.
53#[derive(Clone, Debug, PartialEq, Eq)]
54pub struct Failure {
55    /// Where.
56    pub site: Site,
57    /// The core's message (not TLC's text; the caller classifies).
58    pub message: String,
59    /// Whether it was raised on, or while generating, the initial states.
60    pub initial: bool,
61    /// The state being expanded (persistent handles), unless initial.
62    pub parent: Option<Vec<Handle>>,
63    /// The state checked (persistent handles; empty handles are unassigned
64    /// variables), for a check or an incomplete state.
65    pub state: Option<Vec<Handle>>,
66    /// The action that emitted [`Failure::state`] (`None`: initial).
67    pub action: Option<usize>,
68    /// Actual compiled Init action index; distinct from a next-state action.
69    pub init_action: Option<usize>,
70    /// Whether [`Failure::state`] passed the constraints (for an invariant).
71    pub in_model: bool,
72    /// For [`Site::Init`] and [`Site::Next`]: the states the failing
73    /// predicate or action emitted before the error.
74    pub emitted: u64,
75}
76
77impl Failure {
78    /// Whether TLC's call-stack replay goes on past the state: an invariant
79    /// that failed to evaluate on a new successor inside the model.
80    #[must_use]
81    pub fn site_resumes(&self) -> bool {
82        matches!(self.site, Site::Invariant(_)) && !self.initial && self.in_model
83    }
84}
85
86/// What TLC's call-stack replay changed.
87#[derive(Clone, Debug, Default, PartialEq, Eq)]
88pub struct Replayed {
89    /// States it inserted.
90    pub distinct: u64,
91    /// States it queued.
92    pub queued: u64,
93    /// A further error it met, which decides TLC's class.
94    pub error: Option<Failure>,
95}
96
97fn persist(m: &mut Machine, hs: &[Handle]) -> Result<Vec<Handle>, Error> {
98    let mut out = Vec::with_capacity(hs.len());
99    for &h in hs {
100        out.push(if h.is_empty() { h } else { m.heap.intern(h)? });
101    }
102    Ok(out)
103}
104
105impl Explorer<'_> {
106    /// Records an evaluation error raised by a check of the state in `m.s1`
107    /// and returns the stop; any other error passes through.
108    pub(crate) fn fail_check(&mut self, m: &mut Machine, site: Site, e: Error) -> Error {
109        if e.kind() != ErrorKind::Eval {
110            return e;
111        }
112        match self.failure_at(m, site, e.message().to_owned()) {
113            Ok(f) => {
114                self.failure = Some(f);
115                Error::stop()
116            }
117            Err(e) => e,
118        }
119    }
120
121    /// The failure at `site` for the state in `m.s1`.
122    pub(crate) fn failure_at(
123        &mut self,
124        m: &mut Machine,
125        site: Site,
126        message: String,
127    ) -> Result<Failure, Error> {
128        let state = Some(persist(m, &m.s1.clone())?);
129        let parent = if self.initial {
130            None
131        } else {
132            Some(m.s0.clone())
133        };
134        Ok(Failure {
135            site,
136            message,
137            initial: self.initial,
138            parent,
139            state,
140            action: self.action,
141            init_action: self.init_action,
142            in_model: self.in_model,
143            emitted: 0,
144        })
145    }
146
147    /// The failure of a generator error at the current action.
148    pub(crate) fn generator_failure(&self, m: &Machine, message: String) -> Failure {
149        Failure {
150            site: self.action.map_or(Site::Init, Site::Next),
151            message,
152            initial: self.initial,
153            parent: (!self.initial).then(|| m.s0.clone()),
154            state: None,
155            action: self.action,
156            init_action: self.init_action,
157            in_model: false,
158            emitted: self.emitted - self.action_start,
159        }
160    }
161}
162
163/// Collects every emission of one action, as persistent handles.
164struct Collect {
165    states: Vec<(Vec<Handle>, bool)>,
166}
167
168impl Sink for Collect {
169    fn emit(&mut self, m: &mut Machine, _code: &Code) -> Result<(), Error> {
170        let complete = m.assigned == m.s1.len();
171        let values = persist(m, &m.s1.clone())?;
172        self.states.push((values, complete));
173        Ok(())
174    }
175}
176
177/// TLC's call-stack replay after the invariant failure at emission
178/// `ordinal` of the expansion of `m.s0` (module documentation).
179///
180/// # Errors
181/// An error the replay cannot attribute to the specification (a refusal or
182/// a core bug).
183pub(crate) fn replay_after(
184    m: &mut Machine,
185    ex: &mut Explorer<'_>,
186    ordinal: u64,
187) -> Result<Replayed, Error> {
188    // This path reuses the primary machine, unlike fresh trace replay. Its
189    // entire action/check traversal is diagnostic, including every early exit.
190    m.without_debugger(|m| replay_after_unobserved(m, ex, ordinal))
191}
192
193fn replay_after_unobserved(
194    m: &mut Machine,
195    ex: &mut Explorer<'_>,
196    ordinal: u64,
197) -> Result<Replayed, Error> {
198    let plan = ex.plan;
199    let code = &plan.code;
200    let s0 = m.s0.clone();
201    let mut out = Replayed::default();
202    let mut added = ex.seen.empty_like();
203    let mut emission = 0u64;
204    for (index, a) in plan.next.iter().enumerate() {
205        ex.action = Some(index);
206        let mut sink = Collect { states: Vec::new() };
207        let old = m.enter(a.frame);
208        for &(slot, v) in &a.preset {
209            if let Some(x) = m.frame.get_mut(m.base + slot as usize) {
210                *x = v;
211            }
212        }
213        let ran = m.run_action(code, a.g, &mut sink);
214        m.leave(old);
215        if let Err(e) = ran {
216            if e.kind() != ErrorKind::Eval {
217                return Err(e);
218            }
219            // The search reached the failing state without this error, so
220            // it lies in that state's action or a later one.
221            out.error = Some(Failure {
222                site: Site::Next(index),
223                message: e.message().to_owned(),
224                initial: false,
225                parent: Some(s0),
226                state: None,
227                action: Some(index),
228                init_action: None,
229                in_model: false,
230                emitted: sink.states.len() as u64,
231            });
232            return Ok(out);
233        }
234        for (values, complete) in sink.states {
235            let o = emission;
236            emission += 1;
237            if o < ordinal {
238                continue;
239            }
240            if !complete {
241                // `doNextSetErr`: an incomplete state ends it quietly.
242                return Ok(out);
243            }
244            m.s0.copy_from_slice(&s0);
245            m.s1.copy_from_slice(&values);
246            if o == ordinal {
247                // The failing state's own step: only its implied actions.
248                if !replay_implied(m, ex, &mut out)? {
249                    return Ok(out);
250                }
251                continue;
252            }
253            ex.changed = crate::changed_vars(m);
254            let inside = match ex.in_model_of(m) {
255                Ok(b) => b,
256                Err((site, e)) => {
257                    if e.kind() != ErrorKind::Eval {
258                        return Err(e);
259                    }
260                    ex.in_model = true;
261                    out.error = Some(ex.failure_at(m, site, e.message().to_owned())?);
262                    return Ok(out);
263                }
264            };
265            let mut new = true;
266            if inside {
267                let mut identity = Vec::new();
268                let key =
269                    match state_identity(m, plan, ex.seen.exact.as_ref().map(|_| &mut identity)) {
270                        Ok(k) => ex.seen.key(k),
271                        Err(e) if e.kind() == ErrorKind::Eval && plan.view.is_some() => {
272                            out.error =
273                                Some(ex.failure_at(m, Site::View, e.message().to_owned())?);
274                            return Ok(out);
275                        }
276                        Err(e) => return Err(e),
277                    };
278                new = !ex.seen_contains(key, &identity, &m.heap, ("ReplayMembership", Some(o)))?
279                    && (ex.disk.is_some()
280                        || !added.contains_row(key, &identity, &m.heap, ex.poll)?);
281                if new {
282                    if ex.disk.is_some() {
283                        ex.seen_insert(key, &identity, &m.heap, ("ReplayInsertion", Some(o)))?;
284                    } else {
285                        // Diagnostic replay never feeds a graph sink, so
286                        // these discoveries need no id.
287                        added.insert_row(key, &identity, &m.heap, u64::MAX, ex.poll)?;
288                    }
289                    out.distinct += 1;
290                }
291            }
292            if new && !replay_invariants(m, ex, inside, &mut out)? {
293                return Ok(out);
294            }
295            if !replay_implied(m, ex, &mut out)? {
296                return Ok(out);
297            }
298            if inside && new {
299                out.queued += 1;
300            }
301        }
302    }
303    Ok(out)
304}
305
306/// The invariants on the replayed state `m.s1`: whether the replay goes
307/// on. A violation ends it quietly; an error ends it with the error
308/// recorded.
309fn replay_invariants(
310    m: &mut Machine,
311    ex: &mut Explorer<'_>,
312    inside: bool,
313    out: &mut Replayed,
314) -> Result<bool, Error> {
315    let plan = ex.plan;
316    for (i, c) in plan.invariants.iter().enumerate() {
317        match ex.check(m, &plan.code, c) {
318            Ok(true) => {}
319            Ok(false) => return Ok(false),
320            Err(e) => {
321                if e.kind() != ErrorKind::Eval {
322                    return Err(e);
323                }
324                ex.in_model = inside;
325                out.error = Some(ex.failure_at(m, Site::Invariant(i), e.message().to_owned())?);
326                return Ok(false);
327            }
328        }
329    }
330    Ok(true)
331}
332
333/// The implied actions on the replayed step from `m.s0` to `m.s1`: whether
334/// the replay goes on. A violation ends it quietly; an error ends it with
335/// the error recorded.
336fn replay_implied(
337    m: &mut Machine,
338    ex: &mut Explorer<'_>,
339    out: &mut Replayed,
340) -> Result<bool, Error> {
341    let plan = ex.plan;
342    for (i, c) in plan.implied_actions.iter().enumerate() {
343        match crate::check_step(m, &plan.code, c) {
344            Ok(true) => {}
345            Ok(false) => return Ok(false),
346            Err(e) => {
347                if e.kind() != ErrorKind::Eval {
348                    return Err(e);
349                }
350                out.error =
351                    Some(ex.failure_at(m, Site::ImpliedAction(i), e.message().to_owned())?);
352                return Ok(false);
353            }
354        }
355    }
356    Ok(true)
357}