use super::Cuts;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Site {
Choose,
Initial,
Splits,
Answers,
Parts,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Taken {
Open(u32),
Failed,
Settled(u32),
}
#[derive(Clone, Copy, Debug)]
struct Entry {
site: Site,
taken: Taken,
cuts: Cuts,
}
#[derive(Clone, Copy, Debug)]
pub(super) struct Choice {
slot: Option<usize>,
pub(super) start: u32,
pub(super) cuts: Cuts,
pub(super) settled: Option<u32>,
pub(super) resumed: bool,
}
impl Choice {
const FAILED: Self = Self {
slot: None,
start: u32::MAX,
cuts: Cuts::BUDGET,
settled: None,
resumed: false,
};
}
#[derive(Debug, Default)]
pub(super) struct Choices {
log: Vec<Entry>,
script: Vec<Entry>,
cursor: usize,
resume_at: usize,
replaying: bool,
diverged: bool,
open: u32,
}
impl Choices {
pub(super) fn enter(&mut self, site: Site) -> Choice {
if self.diverged {
return Choice::FAILED;
}
if self.replaying {
let Some(&entry) = self.script.get(self.cursor).filter(|e| e.site == site) else {
self.diverge();
return Choice::FAILED;
};
let resumed = self.cursor == self.resume_at;
self.cursor += 1;
self.log.push(entry);
let slot = Some(self.log.len() - 1);
if resumed {
self.replaying = false;
}
let (start, settled) = match entry.taken {
Taken::Open(i) if resumed => (i + 1, None),
Taken::Open(i) => (i, None),
Taken::Failed => (u32::MAX, None),
Taken::Settled(value) => (u32::MAX, Some(value)),
};
return Choice {
slot,
start,
cuts: entry.cuts,
settled,
resumed,
};
}
let slot = (self.open > 0).then(|| {
self.log.push(Entry {
site,
taken: Taken::Open(0),
cuts: Cuts::NONE,
});
self.log.len() - 1
});
Choice {
slot,
start: 0,
cuts: Cuts::NONE,
settled: None,
resumed: false,
}
}
pub(super) fn take(&mut self, choice: &Choice, i: u32, cuts: Cuts) {
let Some(slot) = choice.slot else {
return;
};
if self.replaying && self.log[slot].taken != Taken::Open(i) {
self.diverge();
return;
}
self.log.truncate(slot + 1);
self.log[slot] = Entry {
taken: Taken::Open(i),
cuts,
..self.log[slot]
};
}
pub(super) fn next_round(&mut self, choice: &Choice, i: u32, cuts: Cuts) {
if let Some(slot) = choice.slot {
self.log[slot] = Entry {
taken: Taken::Open(i),
cuts,
..self.log[slot]
};
}
}
pub(super) fn fail(&mut self, choice: &Choice, cuts: Cuts) {
let Some(slot) = choice.slot else {
return;
};
if self.replaying && self.log[slot].taken != Taken::Failed {
self.diverge();
return;
}
self.log.truncate(slot + 1);
self.log[slot] = Entry {
taken: Taken::Failed,
cuts,
..self.log[slot]
};
}
pub(super) fn settle(&mut self, choice: &Choice, value: u32) {
let Some(slot) = choice.slot else {
return;
};
self.log.truncate(slot + 1);
self.log[slot] = Entry {
taken: Taken::Settled(value),
cuts: Cuts::NONE,
..self.log[slot]
};
}
pub(super) fn open(&mut self) {
self.open += 1;
}
pub(super) fn close(&mut self) {
self.open -= 1;
if self.open == 0 {
self.log.clear();
}
}
pub(super) fn len(&self) -> usize {
self.log.len()
}
pub(super) fn truncate(&mut self, at: usize) {
self.log.truncate(at);
}
pub(super) fn resume(&mut self, start: usize, end: usize) -> Result<(), Cuts> {
if self.replaying || self.diverged {
self.diverge();
return Err(Cuts::BUDGET);
}
let entries = &self.log[start..end];
let rest = |entries: &[Entry]| entries.iter().fold(Cuts::NONE, |c, e| c.and(e.cuts));
let Some(at) = entries
.iter()
.rposition(|e| matches!(e.taken, Taken::Open(_)))
else {
let cuts = rest(entries);
self.log.truncate(start);
return Err(cuts);
};
let given_up = rest(&entries[at + 1..]);
self.script.clear();
self.script.extend_from_slice(entries);
self.script[at].cuts = self.script[at].cuts.and(given_up);
self.log.truncate(start);
self.cursor = 0;
self.resume_at = at;
self.replaying = true;
Ok(())
}
pub(super) fn replaying(&self) -> bool {
self.replaying
}
pub(super) fn end_replay(&mut self) -> bool {
let diverged = self.diverged || self.replaying;
self.diverged = false;
self.replaying = false;
self.script.clear();
diverged
}
pub(super) fn bytes(&self) -> usize {
(self.log.capacity() + self.script.capacity()) * size_of::<Entry>()
}
fn diverge(&mut self) {
self.diverged = true;
self.replaying = false;
}
}
#[cfg(test)]
mod tests {
use super::{Choices, Cuts, Site};
#[test]
fn a_resumption_goes_on_at_the_last_open_choice() {
let mut choices = Choices::default();
choices.open();
let stable = choices.enter(Site::Choose);
choices.take(&stable, 0, Cuts::NONE);
choices.take(&stable, 1, Cuts::BUDGET);
let pair = choices.enter(Site::Initial);
choices.take(&pair, 2, Cuts::NONE);
let absorbed = choices.enter(Site::Initial);
choices.fail(&absorbed, Cuts::repeat(3));
let end = choices.len();
assert_eq!(choices.resume(0, end), Ok(()));
let stable = choices.enter(Site::Choose);
assert_eq!(
(stable.start, stable.cuts, stable.resumed),
(1, Cuts::BUDGET, false)
);
choices.take(&stable, 1, stable.cuts);
let pair = choices.enter(Site::Initial);
assert_eq!(
(pair.start, pair.cuts, pair.resumed),
(3, Cuts::repeat(3), true)
);
assert!(!choices.replaying());
assert!(!choices.end_replay());
}
#[test]
fn a_replay_off_its_log_diverges() {
let mut choices = Choices::default();
choices.open();
let stable = choices.enter(Site::Choose);
choices.take(&stable, 0, Cuts::NONE);
let split = choices.enter(Site::Splits);
choices.take(&split, 0, Cuts::NONE);
let end = choices.len();
choices.resume(0, end).unwrap();
let other = choices.enter(Site::Initial);
assert_eq!((other.start, other.cuts), (u32::MAX, Cuts::BUDGET));
assert!(choices.end_replay());
let mut choices = Choices::default();
choices.open();
let stable = choices.enter(Site::Choose);
choices.take(&stable, 0, Cuts::NONE);
let split = choices.enter(Site::Splits);
choices.take(&split, 0, Cuts::NONE);
choices.resume(0, choices.len()).unwrap();
let stable = choices.enter(Site::Choose);
choices.take(&stable, 1, Cuts::NONE);
assert!(choices.end_replay());
}
#[test]
fn no_open_choice_leaves_no_answer() {
let mut choices = Choices::default();
choices.open();
let pair = choices.enter(Site::Initial);
choices.fail(&pair, Cuts::BUDGET);
let parts = choices.enter(Site::Parts);
choices.settle(&parts, 1);
assert_eq!(choices.resume(0, choices.len()), Err(Cuts::BUDGET));
assert!(!choices.replaying());
}
}