Skip to main content

dive_explore/
sample.rs

1//! Successor sampling for a differential sample: Core's successors of a
2//! sample of states, for comparison with an independent evaluator.
3//!
4//! A run with [`Config::sample`](crate::Config::sample) keeps a uniform
5//! sample of the states it expanded (reservoir sampling, seeded, so the same
6//! seed picks the same states at any worker count), retaining each source's
7//! actual evaluation level. [`successors`] then
8//! regenerates each sampled state's successors, action by action, for the
9//! caller to compare with the dive-eval evaluator's.
10
11use std::sync::Arc;
12
13use dive_core::memo::Memo;
14use dive_core::plan::Code;
15use dive_core::{Error, Handle, Machine, Opts, Plan, Sink, Store};
16
17/// What to sample.
18#[derive(Clone, Copy, Debug, PartialEq, Eq)]
19pub struct Sample {
20    /// The seed of the selection.
21    pub seed: u64,
22    /// At most this many states.
23    pub states: usize,
24}
25
26/// An expanded state and the evaluation level used for its successors.
27#[derive(Clone, Debug, PartialEq, Eq)]
28pub struct SampledState {
29    /// Persistent state handles, in the plan's variable order.
30    pub values: Vec<Handle>,
31    /// The source state's `TLCGet("level")` (initial states have level 1).
32    pub level: i64,
33}
34
35/// A reservoir of expanded states (Algorithm R).
36#[derive(Debug)]
37pub(crate) struct Reservoir {
38    want: usize,
39    rng: u64,
40    seen: u64,
41    pub(crate) states: Vec<SampledState>,
42}
43
44impl Reservoir {
45    pub(crate) fn new(s: Sample) -> Self {
46        Self {
47            want: s.states,
48            rng: s.seed ^ 0x9e37_79b9_7f4a_7c15,
49            seen: 0,
50            states: Vec::new(),
51        }
52    }
53
54    fn next(&mut self) -> u64 {
55        // SplitMix64.
56        self.rng = self.rng.wrapping_add(0x9e37_79b9_7f4a_7c15);
57        let mut z = self.rng;
58        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
59        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
60        z ^ (z >> 31)
61    }
62
63    /// Offers the state about to be expanded.
64    pub(crate) fn offer(&mut self, state: &[Handle], level: i64) {
65        if self.want == 0 {
66            return;
67        }
68        self.seen += 1;
69        if self.states.len() < self.want {
70            self.states.push(SampledState {
71                values: state.to_vec(),
72                level,
73            });
74            return;
75        }
76        let j = self.next() % self.seen;
77        if let Some(slot) = usize::try_from(j).ok().and_then(|j| self.states.get_mut(j)) {
78            *slot = SampledState {
79                values: state.to_vec(),
80                level,
81            };
82        }
83    }
84}
85
86/// The successors of one state by one action: every emission in order,
87/// as persistent handles (empty handles are unassigned variables), or the
88/// core's message for the evaluation error that ended the action.
89pub type ActionSuccessors = Result<Vec<Vec<Handle>>, String>;
90
91struct Collect {
92    states: Vec<Vec<Handle>>,
93}
94
95impl Sink for Collect {
96    fn emit(&mut self, m: &mut Machine, _code: &Code) -> Result<(), Error> {
97        let mut values = Vec::with_capacity(m.s1.len());
98        for &h in &m.s1.clone() {
99            values.push(if h.is_empty() { h } else { m.heap.intern(h)? });
100        }
101        self.states.push(values);
102        Ok(())
103    }
104}
105
106/// The successors of `s0` under each action of [`Plan::next`], in order,
107/// evaluated at the sampled source state's actual `level`.
108///
109/// # Errors
110/// An error other than an evaluation error (a refusal or a core bug).
111pub fn successors(
112    plan: &Plan,
113    store: &Arc<Store>,
114    opts: Opts,
115    warn: bool,
116    s0: &[Handle],
117    level: i64,
118) -> Result<Vec<ActionSuccessors>, Error> {
119    let keys: Vec<usize> = plan
120        .code
121        .sites
122        .iter()
123        .map(dive_core::plan::MemoSite::key_len)
124        .collect();
125    let mut m = Machine::new(Arc::clone(store), plan.vars.len(), opts, Memo::new(&keys));
126    m.warn = warn;
127    m.level = level;
128    if s0.len() != m.s0.len() {
129        return Err(Error::internal("a sampled state of the wrong width"));
130    }
131    let mut out = Vec::with_capacity(plan.next.len());
132    for a in &plan.next {
133        m.s0.copy_from_slice(s0);
134        let mut sink = Collect { states: Vec::new() };
135        let old = m.enter(a.frame);
136        for &(slot, v) in &a.preset {
137            if let Some(x) = m.frame.get_mut(m.base + slot as usize) {
138                *x = v;
139            }
140        }
141        let r = m.run_action(&plan.code, a.g, &mut sink);
142        m.leave(old);
143        m.heap.reset();
144        out.push(match r {
145            Ok(()) => Ok(sink.states),
146            Err(e) if e.kind() == dive_core::ErrorKind::Eval => Err(e.message().to_owned()),
147            Err(e) => return Err(e),
148        });
149    }
150    Ok(out)
151}
152
153#[cfg(test)]
154mod tests {
155    use super::{Reservoir, Sample, SampledState};
156    use dive_core::Handle;
157
158    fn picks(seed: u64, n: i64) -> Vec<SampledState> {
159        let mut r = Reservoir::new(Sample { seed, states: 4 });
160        for i in 0..n {
161            r.offer(&[Handle::int(i).unwrap_or(Handle::EMPTY)], i + 1);
162        }
163        r.states
164    }
165
166    #[test]
167    fn the_seed_decides_the_sample() {
168        assert_eq!(picks(1, 3).len(), 3);
169        assert_eq!(picks(1, 1000).len(), 4);
170        assert_eq!(picks(1, 1000), picks(1, 1000));
171        assert_ne!(picks(1, 1000), picks(2, 1000));
172        let mut r = Reservoir::new(Sample { seed: 1, states: 0 });
173        r.offer(&[Handle::EMPTY], 1);
174        assert_eq!(r.states.len(), 0);
175    }
176
177    #[test]
178    fn levels_are_retained_without_changing_algorithm_r_selection() {
179        let sample = picks(1, 1000);
180        let selected: Vec<_> = sample.iter().map(|s| s.values[0].as_int()).collect();
181        assert_eq!(selected, vec![Some(669), Some(231), Some(180), Some(745)]);
182        for state in sample {
183            assert_eq!(state.values[0].as_int().map(|n| n + 1), Some(state.level));
184        }
185    }
186}