use std::collections::{HashMap, HashSet, VecDeque};
use super::super::{
Ack, Custody, ItemId, Lifecycle, Lineage, Outbound, Owed, Owing, Station, ack_channel,
};
use crate::{Skip, SkipReason};
fn released(window: &mut Outbound<ItemId>) -> Vec<ItemId> {
window.harvest().released().copied().collect()
}
fn round(window: &mut Outbound<ItemId>, keys: &[u64], released: &[u64]) -> Vec<Station> {
let (ack, answers) = ack_channel::<ItemId>();
window.record(keys.iter().copied().map(ItemId::new), answers);
let set: HashSet<ItemId> = released.iter().copied().map(ItemId::new).collect();
ack.send(Ack::new(set, "consumer", Lifecycle::Persisted(())));
window
.harvest()
.answers()
.iter()
.filter_map(|answer| answer.observation().station())
.collect()
}
#[test]
fn a_fully_released_delivery_moves_the_watermark_to_its_last_key() {
let mut window = Outbound::new();
assert!(window.position().is_none());
assert!(window.is_drained());
let stations = round(&mut window, &[0, 1, 2], &[0, 1, 2]);
assert_eq!(stations, [Station::Persisted]);
assert_eq!(window.position(), Some(&ItemId::new(2)));
assert_eq!(window.outstanding(), 0);
assert!(window.is_drained());
}
#[test]
fn a_gap_stops_the_watermark_at_the_item_before_it() {
let mut window = Outbound::new();
round(&mut window, &[0, 1, 2, 3, 4], &[0, 1, 3, 4]);
assert_eq!(window.position(), Some(&ItemId::new(1)));
assert_eq!(window.outstanding(), 1);
assert!(!window.is_drained());
}
#[test]
fn the_gap_closing_lets_the_watermark_cross_everything_behind_it() {
let mut window = Outbound::new();
round(&mut window, &[0, 1, 2, 3, 4], &[0, 1, 3, 4]);
assert_eq!(window.position(), Some(&ItemId::new(1)));
let (ack, answers) = ack_channel::<ItemId>();
window.record([ItemId::new(5)], answers);
ack.send(Ack::new(
[ItemId::new(2), ItemId::new(5)].into_iter().collect(),
"consumer",
Lifecycle::Persisted(()),
));
window.harvest();
assert_eq!(window.position(), Some(&ItemId::new(5)));
assert!(window.is_drained());
}
#[test]
fn the_watermark_walks_the_send_order_and_not_the_key_order() {
let mut window = Outbound::new();
round(&mut window, &[9, 7, 8], &[9, 7]);
assert_eq!(window.position(), Some(&ItemId::new(7)));
}
#[test]
fn an_unanswered_delivery_holds_the_window_and_a_dropped_one_is_reported_lost() {
let mut window = Outbound::new();
let (ack, answers) = ack_channel::<ItemId>();
window.record([ItemId::new(0), ItemId::new(1)], answers);
let harvest = window.harvest();
assert!(harvest.is_empty());
assert_eq!(harvest.released().count(), 0);
assert_eq!(window.lost(), 0);
assert_eq!(window.outstanding(), 2);
drop(ack);
window.harvest();
assert_eq!(window.lost(), 1, "a dropped oneshot is a lost delivery");
assert!(window.position().is_none(), "nothing was released");
assert_eq!(window.outstanding(), 2);
}
#[test]
fn rewinding_retracts_the_tail_past_the_watermark_and_nothing_before_it() {
let mut window = Outbound::new();
round(&mut window, &[0, 1], &[0, 1]);
assert_eq!(window.position(), Some(&ItemId::new(1)));
round(&mut window, &[2, 3], &[2, 3]);
let (ack, answers) = ack_channel::<ItemId>();
window.record([ItemId::new(4), ItemId::new(5)], answers);
drop(ack);
window.harvest();
assert_eq!(window.lost(), 1);
let retracted = window.rewind();
assert_eq!(retracted, [ItemId::new(4), ItemId::new(5)]);
assert_eq!(window.position(), Some(&ItemId::new(3)));
assert_eq!(window.lost(), 0, "a rewind clears what it acted on");
assert!(window.is_drained());
}
#[test]
fn a_key_crosses_from_held_to_released_exactly_once() {
let mut window = Outbound::new();
let (first, first_answers) = ack_channel::<ItemId>();
window.record([ItemId::new(0), ItemId::new(1)], first_answers);
first.send(Ack::<ItemId, ()>::new(
[ItemId::new(0)].into_iter().collect(),
"consumer",
Lifecycle::Persisted(()),
));
assert_eq!(released(&mut window), [ItemId::new(0)]);
let (second, second_answers) = ack_channel::<ItemId>();
window.record([ItemId::new(2)], second_answers);
second.send(Ack::<ItemId, ()>::new(
[ItemId::new(0), ItemId::new(2)].into_iter().collect(),
"consumer",
Lifecycle::Persisted(()),
));
assert_eq!(released(&mut window), [ItemId::new(2)]);
}
#[test]
fn a_harvest_pairs_every_key_with_the_answer_that_spoke_for_it() {
let mut window = Outbound::new();
let (first, first_answers) = ack_channel::<ItemId>();
window.record([ItemId::new(0), ItemId::new(1)], first_answers);
let (second, second_answers) = ack_channel::<ItemId>();
window.record([ItemId::new(2)], second_answers);
first.send(Ack::<ItemId, ()>::new(
[ItemId::new(0), ItemId::new(1)].into_iter().collect(),
"titles",
Lifecycle::Persisted(()),
));
second.send(Ack::<ItemId, ()>::new(
HashSet::new(),
"captions",
Lifecycle::Skipped(Skip::new(SkipReason::Filtered)),
));
let harvest = window.harvest();
let paired: Vec<(u64, &str, Station)> = harvest
.pairs()
.map(|(key, answer)| {
(
key.seq(),
answer.worker().as_str(),
answer
.observation()
.station()
.expect("an ack carries an arrival"),
)
})
.collect();
assert_eq!(
paired,
[
(0, "titles", Station::Persisted),
(1, "titles", Station::Persisted),
(2, "captions", Station::Skipped),
]
);
}
#[test]
fn a_failed_answer_releases_nothing_and_still_names_every_key_it_covered() {
let mut window = Outbound::new();
let (ack, answers) = ack_channel::<ItemId>();
window.record([ItemId::new(0), ItemId::new(1)], answers);
ack.send(Ack::<ItemId, ()>::holding(
"decode",
Lifecycle::Failed(super::super::Failure::new(std::io::Error::other(
"no codec",
))),
));
let harvest = window.harvest();
assert_eq!(harvest.released().count(), 0, "a failure holds the window");
let [answer] = harvest.answers() else {
panic!("one answer");
};
assert_eq!(answer.worker().as_str(), "decode");
assert_eq!(answer.observation().station(), Some(Station::Failed));
assert_eq!(answer.covered(), [ItemId::new(0), ItemId::new(1)]);
assert_eq!(harvest.pairs().count(), 2);
assert!(window.position().is_none());
}
#[test]
fn an_obligation_settles_once_with_what_it_has() {
let (ack, answers) = ack_channel::<ItemId>();
let mut owed = Owed::open(
[ItemId::new(0), ItemId::new(1), ItemId::new(2)],
Some(Custody::sole(ack)),
);
assert_eq!(owed.held(), 3);
assert!(!owed.is_complete());
assert!(!owed.is_settled());
owed.release(ItemId::new(0));
owed.release(ItemId::new(2));
owed.release(ItemId::new(99));
assert_eq!(owed.held(), 1);
assert!(owed.settle(
"consumer",
Lifecycle::<()>::Skipped(Skip::new(SkipReason::Filtered))
));
assert!(owed.is_settled());
assert!(!owed.settle("consumer", Lifecycle::<()>::Processed(())));
let answer = answers.take();
let super::super::Answer::Settled(settled) = answer else {
panic!("answered once");
};
assert_eq!(settled.released().len(), 2);
assert!(settled.released().contains(&ItemId::new(0)));
assert!(!settled.released().contains(&ItemId::new(1)));
assert_eq!(settled.observation().station(), Some(Station::Skipped));
assert_eq!(settled.worker().as_str(), "consumer");
}
#[test]
fn an_obligation_whose_sender_hung_up_reports_that_it_was_not_heard() {
let (ack, answers) = ack_channel::<ItemId>();
let mut owed = Owed::open([ItemId::new(0)], Some(Custody::sole(ack)));
drop(answers);
owed.release(ItemId::new(0));
assert!(!owed.settle("consumer", Lifecycle::<()>::Processed(())));
}
#[test]
fn an_input_with_no_outputs_is_complete_at_once() {
let mut lineage: Lineage<u8, ItemId> = Lineage::new();
assert!(lineage.is_empty());
assert!(lineage.expect(7, []), "nothing to wait for");
assert!(lineage.is_empty());
assert_eq!(lineage.waiting(), 0);
}
#[test]
fn a_fan_out_joins_on_every_arm_and_not_on_the_first() {
let mut lineage: Lineage<u8, ItemId> = Lineage::new();
let arms = [ItemId::new(10), ItemId::new(11), ItemId::new(12)];
assert!(!lineage.expect(7, arms));
assert_eq!(lineage.waiting(), 1);
assert_eq!(lineage.retire(&arms[0]), None);
assert_eq!(lineage.retire(&arms[2]), None);
assert_eq!(
lineage.retire(&arms[1]),
Some(7),
"the last arm completes it"
);
assert!(lineage.is_empty());
}
#[test]
fn two_inputs_are_counted_apart() {
let mut lineage: Lineage<u8, ItemId> = Lineage::new();
lineage.expect(1, [ItemId::new(10), ItemId::new(11)]);
lineage.expect(2, [ItemId::new(20)]);
assert_eq!(lineage.waiting(), 2);
assert_eq!(lineage.retire(&ItemId::new(20)), Some(2));
assert_eq!(lineage.waiting(), 1);
assert_eq!(lineage.retire(&ItemId::new(10)), None);
assert_eq!(lineage.retire(&ItemId::new(11)), Some(1));
assert!(lineage.is_empty());
}
#[test]
fn an_output_nobody_recorded_retires_nothing() {
let mut lineage: Lineage<u8, ItemId> = Lineage::new();
lineage.expect(1, [ItemId::new(10)]);
assert_eq!(lineage.retire(&ItemId::new(99)), None);
assert_eq!(lineage.retire(&ItemId::new(10)), Some(1));
assert_eq!(lineage.retire(&ItemId::new(10)), None);
}
#[test]
fn retracting_an_arm_never_completes_an_input() {
let mut lineage: Lineage<u8, ItemId> = Lineage::new();
lineage.expect(1, [ItemId::new(10)]);
assert_eq!(lineage.retract(&ItemId::new(10)), Some(1));
assert!(lineage.is_empty(), "the count went with the arm");
assert_eq!(lineage.retire(&ItemId::new(10)), None);
assert!(!lineage.expect(1, [ItemId::new(11)]));
assert_eq!(lineage.retire(&ItemId::new(11)), Some(1));
}
#[test]
fn a_window_reserved_for_its_deliveries_starts_where_an_empty_one_does() {
let mut window = Outbound::<ItemId>::with_capacity(4);
assert!(window.position().is_none());
assert!(window.is_drained());
assert_eq!(window.outstanding(), 0);
assert_eq!(window.lost(), 0);
let stations = round(&mut window, &[0, 1], &[0, 1]);
assert_eq!(stations, [Station::Persisted]);
assert_eq!(window.position(), Some(&ItemId::new(1)));
}
fn growth_steps(reserved: usize, pushes: usize) -> usize {
let mut items: Vec<ItemId> = Vec::with_capacity(reserved);
let mut capacity = items.capacity();
let mut steps = 0;
for seq in 0..pushes as u64 {
items.push(ItemId::new(seq));
if items.capacity() != capacity {
capacity = items.capacity();
steps += 1;
}
}
steps
}
#[test]
fn answer_capacity_is_taken_where_the_size_is_known_and_not_where_it_is_guessed() {
assert_eq!(
growth_steps(256, 256),
0,
"a list reserved for the page it is about never grows again"
);
let grown = growth_steps(0, 256);
assert!(
grown >= 6,
"reaching a page by doubling costs {grown} reallocations and {grown} copies of the prefix"
);
assert_eq!(Vec::<ItemId>::new().capacity(), 0);
assert_eq!(HashMap::<ItemId, usize>::new().capacity(), 0);
assert!(Vec::<ItemId>::with_capacity(8).capacity() >= 8);
}
struct Minter {
next: u64,
freed: Vec<u64>,
reusing: bool,
}
impl Minter {
const fn monotonic() -> Self {
Self {
next: 0,
freed: Vec::new(),
reusing: false,
}
}
const fn reusing() -> Self {
Self {
next: 0,
freed: Vec::new(),
reusing: true,
}
}
fn mint(&mut self) -> ItemId {
if self.reusing
&& let Some(seq) = self.freed.pop()
{
return ItemId::new(seq);
}
let seq = self.next;
self.next += 1;
ItemId::new(seq)
}
fn free(&mut self, id: ItemId) {
self.freed.push(id.seq());
}
}
fn late_answer_for_a_retracted_output(mut minter: Minter) -> Option<(u64, &'static str)> {
let mut lineage: Lineage<(u64, &'static str), ItemId> = Lineage::new();
let first = minter.mint();
lineage.expect((1, "a"), [first]);
assert_eq!(lineage.retract(&first), Some((1, "a")));
minter.free(first);
let second = minter.mint();
lineage.expect((2, "a"), [second]);
lineage.retire(&first)
}
#[test]
fn a_reused_id_settles_the_wrong_input_and_a_monotonic_one_refuses_it() {
assert_eq!(
late_answer_for_a_retracted_output(Minter::reusing()),
Some((2, "a")),
"a reused id let a dead answer release a live input"
);
assert_eq!(
late_answer_for_a_retracted_output(Minter::monotonic()),
None,
"a monotonic id made the dead answer inert"
);
}
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
struct Counted {
probes: usize,
indexes: usize,
released: usize,
}
impl Counted {
const fn operations(&self) -> usize {
self.probes + self.indexes
}
}
const PAGES: usize = 4;
const PAGE: usize = 256;
const HELD: usize = 6;
fn incumbent() -> Counted {
let mut counted = Counted::default();
let mut flights: VecDeque<Vec<(u64, bool)>> = VecDeque::new();
for page in 0..PAGES {
let base = (page * PAGE) as u64;
flights.push_back((0..PAGE as u64).map(|i| (base + i, false)).collect());
let answered: HashSet<u64> = (0..(PAGE - HELD) as u64).map(|i| base + i).collect();
counted.probes += answered.len();
for flight in &mut flights {
for item in flight.iter_mut() {
if item.1 {
continue;
}
counted.probes += 1;
if answered.contains(&item.0) {
item.1 = true;
counted.released += 1;
}
}
}
while let Some(flight) = flights.front_mut() {
let crossed = flight
.iter()
.position(|item| !item.1)
.unwrap_or(flight.len());
flight.drain(..crossed);
if !flight.is_empty() {
break;
}
flights.pop_front();
}
}
counted
}
fn ring() -> Counted {
let mut counted = Counted::default();
let mut slots: VecDeque<bool> = VecDeque::new();
let mut base = 0u64;
for page in 0..PAGES {
let first = (page * PAGE) as u64;
slots.extend(core::iter::repeat_n(false, PAGE));
for i in 0..(PAGE - HELD) as u64 {
counted.indexes += 1;
let at = (first + i - base) as usize;
if !slots[at] {
slots[at] = true;
counted.released += 1;
}
}
while slots.front() == Some(&true) {
slots.pop_front();
base += 1;
}
}
counted
}
fn slot_map() -> Counted {
let mut counted = Counted::default();
let mut translation: HashMap<u64, usize> = HashMap::new();
let mut slots: Vec<bool> = Vec::new();
for page in 0..PAGES {
let base = (page * PAGE) as u64;
for i in 0..PAGE as u64 {
counted.probes += 1;
translation.insert(base + i, slots.len());
slots.push(false);
}
for i in 0..(PAGE - HELD) as u64 {
counted.probes += 1;
let Some(&at) = translation.get(&(base + i)) else {
continue;
};
counted.indexes += 1;
if !slots[at] {
slots[at] = true;
counted.released += 1;
}
}
}
counted
}
#[test]
fn the_outstanding_set_is_counted_against_a_ring_and_a_slot_map() {
let incumbent = incumbent();
let ring = ring();
let slot_map = slot_map();
let crossed = PAGES * (PAGE - HELD);
assert_eq!(incumbent.released, crossed);
assert_eq!(ring.released, crossed);
assert_eq!(slot_map.released, crossed);
let mut window = Outbound::<ItemId>::with_capacity(PAGES);
let mut real = 0usize;
for page in 0..PAGES {
let base = (page * PAGE) as u64;
let (ack, answers) = ack_channel::<ItemId>();
window.record((0..PAGE as u64).map(|i| ItemId::new(base + i)), answers);
let set: HashSet<ItemId> = (0..(PAGE - HELD) as u64)
.map(|i| ItemId::new(base + i))
.collect();
ack.send(Ack::new(set, "consumer", Lifecycle::Persisted(())));
real += window.harvest().released().count();
}
assert_eq!(real, crossed, "the model's traffic is the window's traffic");
assert_eq!(ring.probes, 0, "a ring hashes nothing");
assert!(
ring.operations() < incumbent.operations(),
"ring {} vs incumbent {}",
ring.operations(),
incumbent.operations()
);
assert!(
slot_map.operations() > incumbent.operations(),
"slot map {} vs incumbent {}",
slot_map.operations(),
incumbent.operations()
);
}
fn member(keys: &[u64]) -> (Owing<ItemId>, super::super::AckReceiver<ItemId>) {
let (ack, answers) = ack_channel::<ItemId>();
(
Owing::open(
keys.iter().copied().map(ItemId::new),
Some(Custody::sole(ack)),
),
answers,
)
}
fn answered(answers: &super::super::AckReceiver<ItemId>) -> Option<HashSet<ItemId>> {
match answers.take() {
super::super::Answer::Settled(settled) => Some(settled.into_parts().0),
super::super::Answer::Waiting | super::super::Answer::HungUp => None,
}
}
#[test]
fn a_joined_delivery_answers_every_member_with_its_own_keys() {
let (frames, frame_answers) = member(&[0]);
let (segments, segment_answers) = member(&[0]);
let joined = ItemId::new(1_000);
let custody = Custody::joined(
joined,
vec![frames.share(ItemId::new(0)), segments.share(ItemId::new(0))],
);
let mut owed = Owed::open([joined], Some(custody));
owed.release(joined);
assert!(owed.settle("captioner", Lifecycle::Processed(())));
assert_eq!(
answered(&frame_answers),
Some(HashSet::from([ItemId::new(0)]))
);
assert_eq!(
answered(&segment_answers),
Some(HashSet::from([ItemId::new(0)]))
);
assert!(frames.is_settled() && segments.is_settled());
}
#[test]
fn a_joined_delivery_that_was_not_released_holds_every_member() {
let (frames, frame_answers) = member(&[7]);
let (segments, segment_answers) = member(&[9]);
let joined = ItemId::new(1);
let custody = Custody::joined(
joined,
vec![frames.share(ItemId::new(7)), segments.share(ItemId::new(9))],
);
let mut owed = Owed::open([joined], Some(custody));
assert!(owed.settle(
"captioner",
Lifecycle::<()>::Skipped(Skip::new(SkipReason::Filtered))
));
assert_eq!(answered(&frame_answers), Some(HashSet::new()));
assert_eq!(answered(&segment_answers), Some(HashSet::new()));
}
#[test]
fn a_member_delivery_answers_only_when_its_last_item_has_been_decided() {
let (frames, answers) = member(&[0, 1, 2]);
let mut settled = Vec::new();
for (item, joined, release) in [(0u64, 100u64, true), (1, 101, false), (2, 102, true)] {
let joined = ItemId::new(joined);
let custody = Custody::joined(joined, vec![frames.share(ItemId::new(item))]);
let mut owed = Owed::open([joined], Some(custody));
if release {
owed.release(joined);
}
owed.settle("captioner", Lifecycle::Processed(()));
settled.push(answered(&answers));
}
assert_eq!(settled[0], None, "one of three decided says nothing");
assert_eq!(settled[1], None, "two of three still says nothing");
assert_eq!(
settled[2],
Some(HashSet::from([ItemId::new(0), ItemId::new(2)])),
"the pass that finishes it answers, releasing exactly the pairs that took"
);
assert_eq!(frames.held(), 0, "every item is decided");
}
#[test]
fn a_group_that_never_completes_never_answers_and_the_drop_is_what_holds_it() {
let (frames, answers) = member(&[3]);
let share = frames.share(ItemId::new(3));
assert!(!frames.is_settled());
assert_eq!(frames.held(), 1);
assert!(answered(&answers).is_none(), "nothing has been answered");
drop(share);
drop(frames);
assert!(
matches!(answers.take(), super::super::Answer::HungUp),
"a dropped token is the protocol's own second outcome: held, and re-delivered"
);
}
struct SceneOpen;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SceneId(u64);
impl crate::Receipts for SceneOpen {
type Receipt = SceneId;
}
#[test]
fn a_harvested_answer_reads_its_receipt_at_the_declared_type() {
let mut window = Outbound::new();
let (ack, answers) = ack_channel::<ItemId>();
window.record([ItemId::new(1), ItemId::new(2)], answers);
let released: HashSet<ItemId> = [ItemId::new(1), ItemId::new(2)].into_iter().collect();
ack.send(
Ack::new(released, "seat", Lifecycle::Persisted(()))
.receipting_of::<SceneOpen>(ItemId::new(1), SceneId(4242)),
);
let harvest = window.harvest();
let answered = harvest.answers().first().expect("one answer arrived");
assert_eq!(
answered.receipt_of::<SceneOpen>(&ItemId::new(1)),
Ok(&SceneId(4242)),
"the declared read takes its type off the message's own impl"
);
assert_eq!(
answered.receipt_of::<SceneOpen>(&ItemId::new(2)),
Err(crate::Unreceipted::Silent),
"an item nobody receipted is Silent, not a hang"
);
}