extern crate alloc;
use alloc::collections::BTreeMap;
use thiserror::Error;
use crate::metis::{Dot, DotSet, DotSetStation, Vouched};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Departure {
station: u32,
proposals: BTreeMap<u32, Option<u64>>,
fence: Option<u64>,
own: u32,
sealed: Option<Departed>,
}
impl Departure {
pub fn opened(
station: u32,
own: u32,
survivors: impl IntoIterator<Item = u32>,
) -> Result<Self, DepartureRefusal> {
let proposals: BTreeMap<u32, Option<u64>> = survivors
.into_iter()
.map(|surviving| (surviving, None))
.collect();
if proposals.contains_key(&station) {
return Err(DepartureRefusal::SelfDeparture { station });
}
if proposals.is_empty() {
return Err(DepartureRefusal::EmptyFamily { station });
}
if !proposals.contains_key(&own) {
return Err(DepartureRefusal::UnknownStation { station: own });
}
Ok(Self {
station,
proposals,
fence: None,
own,
sealed: None,
})
}
pub fn propose(&mut self, held: &DotSet, successor: &DotSet) -> Result<u64, DepartureRefusal> {
if let Some(row) = successor.station(self.station) {
return Err(DepartureRefusal::SuccessorHeld {
station: self.station,
held: row.high_water(),
});
}
let row = held.station(self.station);
let floor = row.map_or(0, DotSetStation::floor);
if let Some(row) = row
&& row.high_water() > floor
{
return Err(DepartureRefusal::Ragged {
station: self.station,
floor,
held: row.high_water(),
});
}
if let Some(promised) = self.fence {
if floor > promised {
return Err(DepartureRefusal::FenceBroken {
station: self.station,
promised,
held: floor,
});
}
return Ok(promised);
}
self.fence = Some(floor);
self.fold_proposal(self.own, floor);
Ok(floor)
}
pub fn reinstate(&mut self, proposal: u64) -> Result<(), DepartureRefusal> {
if let Some(sealed) = &self.sealed {
return if proposal <= sealed.bound() {
Ok(())
} else {
Err(DepartureRefusal::FenceBroken {
station: self.station,
promised: sealed.bound(),
held: proposal,
})
};
}
if let Some(promised) = self.fence
&& promised != proposal
{
return Err(DepartureRefusal::FenceBroken {
station: self.station,
promised,
held: proposal,
});
}
self.fence = Some(proposal);
self.fold_proposal(self.own, proposal);
Ok(())
}
pub fn fold(&mut self, report: &Vouched<u64>) -> Result<(), DepartureRefusal> {
let by = report.by();
if !self.proposals.contains_key(&by) {
return Err(DepartureRefusal::UnknownStation { station: by });
}
if self.own == by {
return Err(DepartureRefusal::Impersonated { station: by });
}
self.fold_proposal(by, *report.claim());
Ok(())
}
fn fold_proposal(&mut self, by: u32, proposal: u64) {
let slot = self
.proposals
.get_mut(&by)
.expect("the caller checked family membership");
*slot = Some(slot.map_or(proposal, |held| held.max(proposal)));
}
pub fn try_seal(&mut self) -> Option<&Departed> {
if self.sealed.is_none() {
let mut join = 0;
for slot in self.proposals.values() {
join = join.max((*slot)?);
}
self.sealed = Some(Departed {
station: self.station,
bound: join,
proposals: self
.proposals
.iter()
.map(|(&station, slot)| (station, slot.unwrap_or_default()))
.collect(),
});
self.fence = Some(join);
}
self.sealed.as_ref()
}
#[must_use]
pub const fn sealed(&self) -> Option<&Departed> {
self.sealed.as_ref()
}
#[must_use]
pub fn refounded(&self, family: impl IntoIterator<Item = u32>, base: &DotSet) -> Option<Self> {
let sealed = self.sealed.as_ref()?.refounded(family, base);
Some(Self {
station: self.station,
proposals: sealed
.family()
.map(|station| (station, sealed.proposal_of(station)))
.collect(),
fence: Some(sealed.bound()),
own: self.own,
sealed: Some(sealed),
})
}
#[must_use]
pub const fn station(&self) -> u32 {
self.station
}
#[must_use]
pub const fn fence(&self) -> Option<u64> {
self.fence
}
#[must_use]
pub fn bound(&self) -> Option<u64> {
self.sealed.as_ref().map(Departed::bound)
}
pub fn proposals(&self) -> impl Iterator<Item = (u32, Option<u64>)> + '_ {
self.proposals
.iter()
.map(|(&station, &proposal)| (station, proposal))
}
pub const fn admits_successor(&self, dot: Dot) -> Result<(), Fenced> {
if dot.station() != self.station {
return Ok(());
}
Err(Fenced {
station: dot.station(),
counter: dot.counter(),
fence: 0,
sealed: self.sealed.is_some(),
})
}
pub const fn admits(&self, dot: Dot) -> Result<(), Fenced> {
if dot.station() != self.station {
return Ok(());
}
match self.fence {
Some(fence) if dot.counter() > fence => Err(Fenced {
station: dot.station(),
counter: dot.counter(),
fence,
sealed: self.sealed.is_some(),
}),
_ => Ok(()),
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Departed {
station: u32,
bound: u64,
proposals: BTreeMap<u32, u64>,
}
impl Departed {
#[must_use]
pub const fn station(&self) -> u32 {
self.station
}
pub fn family(&self) -> impl Iterator<Item = u32> + '_ {
self.proposals.keys().copied()
}
#[must_use]
pub fn proposal_of(&self, station: u32) -> Option<u64> {
self.proposals.get(&station).copied()
}
pub(super) fn binds(&self, family: impl IntoIterator<Item = u32>) -> bool {
let mut join = 0;
for member in family {
let Some(proposal) = self.proposal_of(member) else {
return false;
};
join = join.max(proposal);
}
join == self.bound
}
#[must_use]
pub const fn bound(&self) -> u64 {
self.bound
}
#[must_use]
pub const fn covers(&self, dot: Dot) -> bool {
dot.station() != self.station || dot.counter() <= self.bound
}
#[must_use]
pub fn refounded(&self, family: impl IntoIterator<Item = u32>, base: &DotSet) -> Self {
let held = base.floor().get(self.station);
Self {
station: self.station,
bound: held,
proposals: family
.into_iter()
.filter(|&station| station != self.station)
.map(|station| {
let holds = self.proposals.contains_key(&station);
(station, if holds { held } else { 0 })
})
.collect(),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
pub enum DepartureRefusal {
#[error("station {station} is not in the surviving family")]
UnknownStation {
station: u32,
},
#[error("station {station} cannot survive its own departure")]
SelfDeparture {
station: u32,
},
#[error("station {station} cannot depart an empty family")]
EmptyFamily {
station: u32,
},
#[error(
"cannot propose for station {station}: holding {held} above the gap-free floor {floor}"
)]
Ragged {
station: u32,
floor: u64,
held: u64,
},
#[error("cannot propose for station {station}: already holding {held} in the successor plane")]
SuccessorHeld {
station: u32,
held: u64,
},
#[error("station {station}'s own proposal may not arrive as a report")]
Impersonated {
station: u32,
},
#[error("fence for station {station} promised {promised}, now holding {held}")]
FenceBroken {
station: u32,
promised: u64,
held: u64,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
#[error("dot ({station}, {counter}) lies above the departure fence {fence}")]
pub struct Fenced {
pub station: u32,
pub counter: u64,
pub fence: u64,
pub sealed: bool,
}
impl Fenced {
#[must_use]
pub const fn is_resurgence(&self) -> bool {
self.sealed
}
}