1use 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#[derive(Clone, Copy, Debug, PartialEq, Eq)]
19pub struct Sample {
20 pub seed: u64,
22 pub states: usize,
24}
25
26#[derive(Clone, Debug, PartialEq, Eq)]
28pub struct SampledState {
29 pub values: Vec<Handle>,
31 pub level: i64,
33}
34
35#[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 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 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
86pub 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
106pub 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}