use crate::proposal::Proposal;
use crate::types::Step;
#[derive(Clone, Debug, Default, PartialEq, Eq)]
#[cfg_attr(feature = "model", derive(Hash))]
pub(crate) struct Register {
pub step: Step,
pub first: Option<Proposal>,
pub agg: Option<Proposal>,
pub prev_agg: Option<Proposal>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Summary {
pub step: Step,
pub first: Option<Proposal>,
pub prev_agg: Option<Proposal>,
}
impl Register {
pub fn record(&mut self, s: Step, v: Proposal) -> bool {
if s == self.step {
if self.agg.as_ref().is_some_and(|a| *a >= v) {
return false;
}
self.agg = Some(v);
true
} else if s > self.step {
self.prev_agg = if self.step.checked_add(1) == Some(s) { self.agg.take() } else { None };
self.step = s;
self.first = Some(v.clone());
self.agg = Some(v);
true
} else {
false
}
}
pub fn summary(&self) -> Summary {
Summary { step: self.step, first: self.first.clone(), prev_agg: self.prev_agg.clone() }
}
}
#[cfg(kani)]
mod proofs {
use super::*;
use crate::proposal::ValueKey;
use crate::types::NodeId;
fn any_proposal() -> Proposal {
let key = ValueKey { origin: NodeId(kani::any()), incarnation: kani::any(), seq: kani::any() };
let value: &'static [u8] = match kani::any::<u8>() % 3 {
0 => b"",
1 => b"a",
_ => b"b",
};
Proposal { priority: kani::any(), key, value: bytes::Bytes::from_static(value) }
}
fn any_option() -> Option<Proposal> {
if kani::any() { Some(any_proposal()) } else { None }
}
fn same(a: &Option<Proposal>, b: &Option<Proposal>) -> bool {
match (a, b) {
(Some(a), Some(b)) => {
a == b && a.value.as_ptr() == b.value.as_ptr() && a.value.len() == b.value.len()
}
(None, None) => true,
_ => false,
}
}
#[kani::proof]
fn record_upholds_recorder_invariants() {
let mut r =
Register { step: kani::any(), first: any_option(), agg: any_option(), prev_agg: any_option() };
let before = r.clone();
let (s, v): (Step, Proposal) = (kani::any(), any_proposal());
let changed = r.record(s, v.clone());
let new = Some(v.clone());
assert!(r.step >= before.step, "R1 step monotonic");
assert!(
changed
== !(r.step == before.step
&& same(&r.first, &before.first)
&& same(&r.agg, &before.agg)
&& same(&r.prev_agg, &before.prev_agg)),
"changed exactly when it must be persisted"
);
if s < before.step {
assert!(
same(&r.first, &before.first)
&& same(&r.agg, &before.agg)
&& same(&r.prev_agg, &before.prev_agg),
"R5 stale discard"
);
} else if s == before.step {
assert!(same(&r.first, &before.first), "R2 first write-once");
let raised = before.agg.as_ref().is_none_or(|a| v > *a);
assert!(same(&r.agg, if raised { &new } else { &before.agg }), "R3 aggregate is the maximum");
assert!(same(&r.prev_agg, &before.prev_agg));
} else {
let expect = if before.step.checked_add(1) == Some(s) { before.agg.clone() } else { None };
assert!(same(&r.prev_agg, &expect), "R4 prior aggregate");
assert!(r.step == s && same(&r.first, &new) && same(&r.agg, &new), "new step");
}
let sum = r.summary();
assert!(sum.step == r.step && same(&sum.first, &r.first) && same(&sum.prev_agg, &r.prev_agg), "R6");
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::proposal::tests::prop;
use proptest::prelude::*;
fn summary(step: Step, first: Option<Proposal>, prev_agg: Option<Proposal>) -> Summary {
Summary { step, first, prev_agg }
}
#[test]
fn first_record_sets_step_and_first_value_with_nil_prior() {
let mut r = Register::default();
assert!(r.record(4, prop(3, 1, 0)));
assert_eq!(r.summary(), summary(4, Some(prop(3, 1, 0)), None));
}
#[test]
fn same_step_higher_value_raises_aggregate_but_keeps_first() {
let mut r = Register::default();
r.record(4, prop(3, 1, 0));
assert!(r.record(4, prop(7, 2, 0)));
assert_eq!(r.agg, Some(prop(7, 2, 0)));
assert_eq!(r.first, Some(prop(3, 1, 0)));
}
#[test]
fn same_step_lower_or_equal_value_changes_nothing() {
let mut r = Register::default();
r.record(4, prop(7, 2, 0));
let before = r.clone();
assert!(!r.record(4, prop(3, 1, 0)));
assert!(!r.record(4, prop(7, 2, 0)));
assert_eq!(r, before);
}
#[test]
fn next_step_moves_aggregate_to_prior() {
let mut r = Register::default();
r.record(4, prop(3, 1, 0));
r.record(4, prop(7, 2, 0));
r.record(5, prop(1, 3, 0));
assert_eq!(r.summary(), summary(5, Some(prop(1, 3, 0)), Some(prop(7, 2, 0))));
}
#[test]
fn skipping_a_step_clears_prior_aggregate() {
let mut r = Register::default();
r.record(4, prop(7, 2, 0));
r.record(6, prop(1, 3, 0));
assert_eq!(r.summary(), summary(6, Some(prop(1, 3, 0)), None));
}
#[test]
fn stale_step_is_discarded_and_reports_current_state() {
let mut r = Register::default();
r.record(4, prop(7, 2, 0));
r.record(5, prop(1, 3, 0));
let before = r.clone();
assert!(!r.record(4, prop(9, 9, 0)));
assert_eq!(r, before);
assert_eq!(r.summary(), summary(5, Some(prop(1, 3, 0)), Some(prop(7, 2, 0))));
}
fn arb_input() -> impl Strategy<Value = (Step, Proposal)> {
(4u32..12, 0u64..6, 0u32..3).prop_map(|(s, p, o)| (s, prop(p, o, 0)))
}
proptest! {
#[test]
fn register_upholds_recorder_invariants(inputs in proptest::collection::vec(arb_input(), 1..40)) {
let mut r = Register::default();
for (s, v) in inputs {
let before = r.clone();
let changed = r.record(s, v.clone());
prop_assert!(r.step >= before.step, "R1 step monotonic");
prop_assert_eq!(changed, r != before);
if s < before.step {
prop_assert_eq!(&r, &before, "R5 stale discard");
} else if s == before.step {
prop_assert_eq!(&r.first, &before.first, "R2 first write-once");
prop_assert_eq!(&r.agg, &core::cmp::max(before.agg.clone(), Some(v)), "R3");
} else {
let expect = if s == before.step + 1 { before.agg.clone() } else { None };
prop_assert_eq!(&r.prev_agg, &expect, "R4 prior aggregate");
prop_assert_eq!(&r.first, &Some(v), "first value of new step");
}
prop_assert_eq!(r.summary(), Summary { step: r.step, first: r.first.clone(), prev_agg: r.prev_agg.clone() }, "R6");
}
}
}
}