Skip to main content

dive_explore/
trace.rs

1//! Counterexample reconstruction.
2//!
3//! The search logs only `(parent, ordinal)` for each new state, in a
4//! [`dive_store::predecessor::PredecessorLog`]. A trace is rebuilt by
5//! replaying the recorded ordinals with the same generator: the initial
6//! predicates are enumerated and the state at the root's ordinal is kept,
7//! then each parent's actions are enumerated in order and the successor at
8//! the recorded ordinal is kept, with the action that emitted it. The
9//! replay runs with memoization off. A replayed state that differs from the
10//! state the search expanded is an internal error, never a trace.
11
12use std::sync::Arc;
13
14use dive_core::memo::Memo;
15use dive_core::plan::{Action, Code};
16use dive_core::{Error, Handle, Machine, Opts, Plan, Sink, Store};
17use dive_store::trace::TraceStep;
18
19/// One state of a reconstructed behavior.
20#[derive(Clone, Debug, PartialEq, Eq)]
21pub struct TraceState {
22    /// The index of the next-state action (in [`Plan::next`]) that
23    /// produced it; `None` for an initial state.
24    pub action: Option<usize>,
25    /// The state's values, as persistent handles of the run's store; empty
26    /// handles are unassigned variables.
27    pub values: Vec<Handle>,
28}
29
30// Action, canonical reported row, and optional actual construction-view row.
31type Captured = (usize, Vec<Handle>, Vec<Handle>);
32
33/// Captures the emission at one ordinal.
34struct Capture {
35    want: u32,
36    seen: u32,
37    action: usize,
38    got: Option<Captured>,
39}
40
41impl Sink for Capture {
42    fn emit(&mut self, m: &mut Machine, _code: &Code) -> Result<(), Error> {
43        if self.seen == self.want {
44            let views = Vec::new();
45            let mut values = Vec::with_capacity(m.s1.len());
46            for &h in &m.s1 {
47                values.push(if h.is_empty() { h } else { m.heap.intern(h)? });
48            }
49            self.got = Some((self.action, values, views));
50            return Err(Error::stop());
51        }
52        self.seen += 1;
53        Ok(())
54    }
55}
56
57fn run(
58    m: &mut Machine,
59    code: &Code,
60    actions: &[Action],
61    want: u32,
62) -> Result<Option<Captured>, Error> {
63    let mut sink = Capture {
64        want,
65        seen: 0,
66        action: 0,
67        got: None,
68    };
69    for (i, a) in actions.iter().enumerate() {
70        sink.action = i;
71        let old = m.enter(a.frame);
72        for &(slot, v) in &a.preset {
73            if let Some(x) = m.frame.get_mut(m.base + slot as usize) {
74                *x = v;
75            }
76        }
77        let r = m.run_action(code, a.g, &mut sink);
78        m.leave(old);
79        match r {
80            Ok(()) => {}
81            Err(e) if e.kind() == dive_core::ErrorKind::Stop => break,
82            Err(e) => return Err(e),
83        }
84    }
85    m.heap.reset();
86    Ok(sink.got)
87}
88
89/// Replays `path` (root first) and returns its states.
90///
91/// # Errors
92/// An internal error when the replay does not reach a recorded ordinal, or
93/// an evaluation error the replay raised.
94pub fn replay(
95    plan: &Plan,
96    store: &Arc<Store>,
97    opts: Opts,
98    warn: bool,
99    path: &[TraceStep],
100) -> Result<Vec<TraceState>, Error> {
101    let keys: Vec<usize> = plan
102        .code
103        .sites
104        .iter()
105        .map(dive_core::plan::MemoSite::key_len)
106        .collect();
107    let opts = Opts {
108        memo: false,
109        ..opts
110    };
111    let mut m = Machine::new(Arc::clone(store), plan.vars.len(), opts, Memo::new(&keys));
112    m.warn = warn;
113    let mut out: Vec<TraceState> = Vec::with_capacity(path.len());
114    let mut source_views = Vec::new();
115    for step in path {
116        let got = if let Some(prev) = out.last() {
117            m.s0.copy_from_slice(if source_views.is_empty() {
118                &prev.values
119            } else {
120                &source_views
121            });
122            crate::start_stream(&mut m, plan, Some(&prev.values))?;
123            // The predecessor's level (initial states are level 1).
124            m.level = i64::try_from(out.len()).unwrap_or(i64::MAX);
125            run(&mut m, &plan.code, &plan.next, step.ordinal)?
126                .map(|(a, v, views)| (Some(a), v, views))
127        } else {
128            crate::start_stream(&mut m, plan, None)?;
129            m.level = 0;
130            run(&mut m, &plan.code, &plan.init, step.ordinal)?.map(|(_, v, views)| (None, v, views))
131        };
132        let Some((action, values, views)) = got else {
133            return Err(Error::internal(format!(
134                "trace replay did not reach ordinal {} of state {}",
135                step.ordinal, step.id
136            )));
137        };
138        source_views = views;
139        out.push(TraceState { action, values });
140    }
141    Ok(out)
142}