use crate::error::StoreError;
pub type StateId = u64;
const ROOT: u64 = u64::MAX;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct TraceStep {
pub id: StateId,
pub parent: Option<StateId>,
pub ordinal: u32,
}
#[derive(Clone, Debug, Default)]
pub(crate) struct TraceLog {
parents: Vec<u64>,
ordinals: Vec<u32>,
}
impl TraceLog {
#[must_use]
pub(crate) fn new() -> Self {
Self::default()
}
pub(crate) fn reserved_bytes_for(&self, records: usize) -> Option<usize> {
self.parents
.capacity()
.max(records)
.checked_mul(8)?
.checked_add(self.ordinals.capacity().max(records).checked_mul(4)?)
}
pub(crate) fn reserve_record(
&mut self,
exact: bool,
) -> Result<(), std::collections::TryReserveError> {
if exact {
self.parents.try_reserve_exact(1)?;
self.ordinals.try_reserve_exact(1)
} else {
self.parents.try_reserve(1)?;
self.ordinals.try_reserve(1)
}
}
pub(crate) fn push_initial(&mut self, ordinal: u32) -> StateId {
let id = self.parents.len() as u64;
self.parents.push(ROOT);
self.ordinals.push(ordinal);
id
}
pub(crate) fn push(&mut self, parent: StateId, ordinal: u32) -> Result<StateId, StoreError> {
let id = self.parents.len() as u64;
if parent >= id {
return Err(StoreError::BadParent { id, parent });
}
self.parents.push(parent);
self.ordinals.push(ordinal);
Ok(id)
}
#[must_use]
pub(crate) fn get(&self, id: StateId) -> Option<TraceStep> {
let i = usize::try_from(id).ok()?;
let parent = *self.parents.get(i)?;
Some(TraceStep {
id,
parent: (parent != ROOT).then_some(parent),
ordinal: *self.ordinals.get(i)?,
})
}
#[cfg(test)]
pub(crate) fn path(&self, id: StateId) -> Result<Vec<TraceStep>, StoreError> {
let mut path = Vec::new();
let mut cur = Some(id);
while let Some(i) = cur {
let step = self.get(i).ok_or(StoreError::UnknownState(i))?;
path.push(step);
cur = step.parent;
}
path.reverse();
Ok(path)
}
#[must_use]
pub(crate) fn memory_bytes(&self) -> usize {
self.parents.capacity() * 8 + self.ordinals.capacity() * 4
}
}
#[cfg(test)]
#[allow(
clippy::expect_used,
reason = "test code: a failed expectation is a test failure"
)]
mod tests {
use proptest::prelude::*;
use super::TraceLog;
proptest! {
#[test]
fn trace_paths_follow_parents(
parents in prop::collection::vec(any::<u16>(), 0..200),
roots in 1usize..5,
) {
let mut log = TraceLog::new();
for r in 0..roots {
log.push_initial(u32::try_from(r).unwrap_or(0));
}
let mut want_depth = vec![1usize; roots];
for (i, p) in parents.iter().enumerate() {
let id = roots + i;
let parent = usize::from(*p) % id;
let got = log.push(parent as u64, u32::from(*p)).expect("earlier parent");
prop_assert_eq!(got, id as u64);
want_depth.push(want_depth[parent] + 1);
}
let len = want_depth.len() as u64;
for (id, d) in want_depth.iter().enumerate() {
let path = log.path(id as u64).expect("recorded");
prop_assert_eq!(path.len(), *d);
prop_assert!(path[0].parent.is_none());
for w in path.windows(2) {
prop_assert_eq!(w[1].parent, Some(w[0].id));
}
}
prop_assert!(log.push(len, 0).is_err());
prop_assert!(log.path(len).is_err());
}
}
}