extern crate alloc;
use alloc::collections::BTreeMap;
#[cfg(test)]
use alloc::vec::Vec;
use core::num::NonZeroUsize;
#[cfg(test)]
use proptest::prelude::*;
use crate::metis::{EpochAddress, Epochs, SealedEpoch};
use super::fabric::Fabric;
#[cfg(test)]
use super::fabric::Schedule;
use super::replica::Replica;
use super::{act, assert_converged, crash, fleet_of, resync};
const ROSTER: [u32; 3] = [1, 2, 3];
const MAX_OPS: usize = 48;
struct TapeOutcome {
seals: usize,
displaced: usize,
trace: u64,
}
const fn mix(state: u64) -> u64 {
let mut z = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
fn observe_shape(fleet: &BTreeMap<u32, Replica>, trace: u64) -> u64 {
let mut trace = trace;
for (&id, replica) in fleet {
trace = mix(trace ^ u64::from(id));
trace = mix(trace ^ replica.generation());
trace = mix(trace ^ u64::try_from(replica.epochs().candidates().count()).expect("bounded"));
trace = mix(trace ^ u64::try_from(replica.parked_len()).expect("bounded"));
}
trace
}
fn displaced_dots(sealed: &SealedEpoch) -> usize {
let generation = sealed.declaration().generation();
sealed
.declaration_dots()
.filter(|&dot| {
EpochAddress::try_from_parts(generation, dot.into())
.is_ok_and(|address| address != sealed.declaration() && !sealed.contains(address))
})
.count()
}
fn harvest_displacement(epochs: &Epochs, ledger: &mut BTreeMap<u64, usize>) {
for sealed in epochs.sealed() {
let _ = ledger
.entry(sealed.declaration().generation())
.or_insert_with(|| displaced_dots(sealed));
}
}
pub(super) fn assert_quiescent(fleet: &BTreeMap<u32, Replica>) {
for (&id, replica) in fleet {
assert_eq!(
replica.epochs().candidates().count(),
0,
"replica {id}: an epoch window is still open after the closing drain",
);
assert_eq!(
replica.parked_len(),
0,
"replica {id}: parked notes survived the closing drain",
);
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub(super) enum Delivery {
Seeded,
Addressed,
}
pub(super) struct Cursor<'a> {
bytes: &'a [u8],
front: usize,
back: usize,
}
impl<'a> Cursor<'a> {
pub(super) fn new(bytes: &'a [u8]) -> Self {
Self {
bytes,
front: bytes.len().min(8),
back: bytes.len(),
}
}
pub(super) fn op(&mut self) -> Option<(u8, u8)> {
if self.front + 2 > self.back {
return None;
}
let pair = (self.bytes[self.front], self.bytes[self.front + 1]);
self.front += 2;
Some(pair)
}
pub(super) fn address(&mut self) -> Option<u8> {
if self.back <= self.front {
return None;
}
self.back -= 1;
self.bytes.get(self.back).copied()
}
}
fn interpret(tape: &[u8]) -> TapeOutcome {
interpret_with(tape, Delivery::Seeded)
}
fn interpret_with(tape: &[u8], delivery: Delivery) -> TapeOutcome {
let mut seed = [0u8; 8];
for (slot, byte) in seed.iter_mut().zip(tape.iter()) {
*slot = *byte;
}
let mut cursor = Cursor::new(tape);
let mut fleet = fleet_of(&ROSTER, NonZeroUsize::new(2).expect("positive"));
let mut fabric = Fabric::new(u64::from_le_bytes(seed), &ROSTER, 7);
let mut displacement: BTreeMap<u64, usize> = BTreeMap::new();
let mut trace = 0u64;
for _ in 0..MAX_OPS {
let Some((opcode, argument)) = cursor.op() else {
break;
};
let station = ROSTER[usize::from(argument) % ROSTER.len()];
let at = (usize::from(argument) / 3) % 8;
let to = (usize::from(argument) / 24) % 8;
match opcode % 8 {
0 => {
let _ = act(&mut fabric, &mut fleet, station, |replica, out| {
replica.insert_visible(at, out)
});
}
1 => {
let _ = act(&mut fabric, &mut fleet, station, |replica, out| {
replica.delete_visible(at, out)
});
}
2 => {
if fleet[&station].adopted() {
let _ = act(&mut fabric, &mut fleet, station, |replica, out| {
replica.delete_visible(at, out)
});
} else {
let _ = act(&mut fabric, &mut fleet, station, |replica, out| {
replica.move_visible(at, Some(to), out)
});
}
}
3 => {
let _ = act(&mut fabric, &mut fleet, station, |replica, out| {
replica.try_declare(out)
});
}
4 => {
let steps = usize::from(argument) % 32 + 1;
for _ in 0..steps {
let address = match delivery {
Delivery::Seeded => None,
Delivery::Addressed => cursor.address(),
};
let _ = fabric.step_addressed(&mut fleet, address);
}
}
5 => fabric.sever(&[station]),
6 => fabric.heal(),
_ => {
crash(
&mut fleet,
&ROSTER,
NonZeroUsize::new(2).expect("positive"),
station,
);
resync(&mut fabric, &fleet, station);
}
}
for replica in fleet.values() {
harvest_displacement(replica.epochs(), &mut displacement);
}
trace = observe_shape(&fleet, trace);
}
fabric.heal();
fabric.drain(&mut fleet);
assert_converged(&fleet);
assert_quiescent(&fleet);
for replica in fleet.values() {
harvest_displacement(replica.epochs(), &mut displacement);
}
let witness = fleet.get(&ROSTER[0]).expect("roster member");
TapeOutcome {
seals: witness.seals.len(),
displaced: displacement.values().sum(),
trace,
}
}
pub(in crate::metis) fn run_addressed_tape(tape: &[u8]) {
let _ = interpret_with(tape, Delivery::Addressed);
}
#[cfg(test)]
#[test]
fn a_causally_covered_weave_still_crosses_the_boundary() {
let tape = [
69, 55, 93, 189, 113, 147, 226, 26, 99, 45, 28, 220, 157, 10, 195, 4, 204, 50, 21, 213, 13,
222, 227, 181, 6, 194, 199, 216, 149, 176, 247, 213, 20, 98, 17, 155, 143, 97, 213, 13,
136, 248, 255, 139, 116, 225, 11, 200, 41, 212, 207, 208, 212, 150, 102, 243, 251, 198, 85,
250, 84, 14, 38, 34, 150, 177, 27, 203, 27, 141, 212, 58, 123, 232, 48, 2,
];
let _ = interpret(&tape);
}
#[cfg(test)]
proptest! {
#![proptest_config(ProptestConfig::with_cases(64))]
#[test]
fn any_byte_tape_heals_drains_and_converges(
tape in prop::collection::vec(any::<u8>(), 0..104),
) {
let _ = interpret(&tape);
}
#[test]
fn any_addressed_tape_heals_drains_and_converges(
tape in prop::collection::vec(any::<u8>(), 0..104),
) {
run_addressed_tape(&tape);
}
}
#[cfg(test)]
#[test]
fn test_an_address_picks_the_envelope_the_seed_would_not() {
let mut delivered = Vec::new();
for address in [0u8, 1u8] {
let mut fleet = fleet_of(&ROSTER, NonZeroUsize::new(2).expect("positive"));
let mut fabric = Fabric::new(0x5f33_1000, &ROSTER, 0);
let _ = act(&mut fabric, &mut fleet, ROSTER[0], |replica, out| {
replica.insert_visible(0, out)
});
assert!(fabric.step_addressed(&mut fleet, Some(address)));
let heard: Vec<u32> = fleet
.iter()
.filter(|(_, replica)| !replica.effective_order().is_empty())
.map(|(&id, _)| id)
.collect();
assert_eq!(heard.len(), 2, "the weaver plus exactly one receiver");
delivered.push(heard);
}
assert_ne!(
delivered[0], delivered[1],
"two addresses must select two different envelopes",
);
}
#[cfg(test)]
#[test]
fn test_the_addressed_arm_schedules_what_the_seed_would_not() {
let mut bytes = Schedule::new(0x5f33_1a00);
let mut divergences = 0usize;
for _ in 0..32 {
let head: Vec<u8> = (0..8 + 2 * MAX_OPS)
.map(|_| u8::try_from(bytes.below(256)).expect("bounded"))
.collect();
let mut left = head.clone();
let mut right = head;
for _ in 0..(MAX_OPS * 32 + 64) {
left.push(u8::try_from(bytes.below(256)).expect("bounded"));
right.push(u8::try_from(bytes.below(256)).expect("bounded"));
}
if interpret_with(&left, Delivery::Addressed).trace
!= interpret_with(&right, Delivery::Addressed).trace
{
divergences += 1;
}
}
assert!(
divergences > 0,
"thirty-two op programs read the same lifecycle under two address \
regions each; the address is not reaching the fabric",
);
}
#[cfg(test)]
#[test]
fn test_the_detector_reads_the_machine_driven_displaced_window() {
let (epochs, sealed) = super::super::wire::lifecycle::displaced_window();
assert_eq!(displaced_dots(&sealed), 1);
let mut ledger = BTreeMap::new();
harvest_displacement(&epochs, &mut ledger);
harvest_displacement(&epochs, &mut ledger);
assert_eq!(ledger.len(), 1);
assert_eq!(ledger.values().sum::<usize>(), 1);
}
#[cfg(test)]
#[test]
fn test_a_directed_tape_seals_mid_traffic_declarations() {
let mut tape: Vec<u8> = alloc::vec![7, 7, 7, 7, 7, 7, 7, 7];
tape.extend([
0, 0, 0, 1, 0, 2, 4, 31, 1, 3, 5, 1, 0, 4, 7, 1, 3, 0, 4, 63, 6, 0, 4, 63, 3, 2, 2, 5, 5, 0, 0,
0, ]);
let outcome = interpret(&tape);
assert!(
outcome.seals >= 1,
"the drained tape seals at least one generation",
);
assert_eq!(outcome.displaced, 0, "the honest recipe never displaces");
}
#[cfg(test)]
#[test]
fn the_honest_recipe_never_displaces_a_declaration() {
let mut bytes = Schedule::new(0x5f28_9d00);
let mut total_seals = 0usize;
let mut total_displaced = 0usize;
for _ in 0..64 {
let length = bytes.below(96);
let tape: Vec<u8> = (0..length)
.map(|_| u8::try_from(bytes.below(256)).expect("bounded"))
.collect();
for outcome in [
interpret_with(&tape, Delivery::Seeded),
interpret_with(&tape, Delivery::Addressed),
] {
total_seals += outcome.seals;
total_displaced += outcome.displaced;
}
}
assert_eq!(
total_displaced, 0,
"an honest schedule reached the displaced corner; see the module doc",
);
assert!(total_seals > 0, "the corpus exercises real lifecycles");
}
#[cfg(test)]
#[test]
fn test_a_sealed_windows_native_note_redelivers_after_the_next_adoption() {
let tape: alloc::vec::Vec<u8> = alloc::vec![
127, 224, 47, 1, 31, 24, 196, 131, 4, 0, 1, 0, 33, 0, 83, 63, 43, 93, 45, 193, 14, 5, 68,
150, 240, 246, 201, 66, 93, 214, 151, 159, 44, 12, 11, 237, 142, 247, 171, 132, 150, 221,
128, 86, 105, 2, 212, 186, 146, 34, 142, 48, 137, 194, 253, 102, 159, 15, 154, 1, 115, 247,
59, 192, 102,
];
let _ = interpret(&tape);
}