minerva 0.2.0

Causal ordering for distributed systems
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

extern crate alloc;

use alloc::vec::Vec;

use crate::metis::dot::Dot;
use crate::metis::dot_set::{
    DotSet, HAVE_SET_STATION_LEN, HAVE_SET_WIRE_HEADER_LEN, HaveSetDecodeBudget, HaveSetDecodeError,
};
use crate::metis::{Cut, VersionVector};

use super::super::gate::EpochAddress;
use super::error::WireCutError;

/// The width of one dot on the wire: a `u32` station and a `u64` index.
pub(super) const WIRE_DOT_LEN: usize = 12;
/// The width of one epoch address: a `u64` generation plus its dot.
pub(super) const WIRE_ADDRESS_LEN: usize = 8 + WIRE_DOT_LEN;

/// The exact wire length of a gap-free cut embedding.
pub(super) fn cut_embedding_len(vector: &VersionVector) -> usize {
    HAVE_SET_WIRE_HEADER_LEN + vector.iter().count() * HAVE_SET_STATION_LEN
}

/// Appends the canonical gap-free have-set embedding of `vector`.
pub(super) fn encode_cut_into(out: &mut Vec<u8>, vector: &VersionVector) {
    out.extend_from_slice(&DotSet::from_cut(vector).to_bytes());
}

/// Decodes and proves one gap-free have-set embedding.
pub(super) fn decode_cut(rest: &[u8]) -> Result<(VersionVector, &[u8]), WireCutError> {
    let (set, tail) =
        DotSet::from_prefix_with_budget(rest, HaveSetDecodeBudget::new(0)).map_err(|error| {
            match error {
                HaveSetDecodeError::RunTooLong { station, start, .. } => {
                    WireCutError::Gapped { station, start }
                }
                other => WireCutError::HaveSet(other),
            }
        })?;
    Ok((Cut::floor_of(&set).as_vector().clone(), tail))
}

/// Reads a big-endian `u32`; the caller owns the typed length refusal.
pub(super) fn read_u32(rest: &[u8]) -> Option<(u32, &[u8])> {
    let word: [u8; 4] = rest.get(..4)?.try_into().ok()?;
    Some((u32::from_be_bytes(word), &rest[4..]))
}

/// Reads a big-endian `u64`.
pub(super) fn read_u64(rest: &[u8]) -> Option<(u64, &[u8])> {
    let word: [u8; 8] = rest.get(..8)?.try_into().ok()?;
    Some((u64::from_be_bytes(word), &rest[8..]))
}

/// Reads one wire dot as raw parts. The frame owns the typed refusal: a
/// counter zero is refused by the frame's own arm before any [`Dot`] is
/// built, so acceptance is byte-identical (ruling R-91).
pub(super) fn read_dot(rest: &[u8]) -> Option<((u32, u64), &[u8])> {
    let (station, rest) = read_u32(rest)?;
    let (index, rest) = read_u64(rest)?;
    Some(((station, index), rest))
}

/// Appends one wire dot.
pub(super) fn encode_dot_into(out: &mut Vec<u8>, dot: Dot) {
    out.extend_from_slice(&dot.station().to_be_bytes());
    out.extend_from_slice(&dot.counter().to_be_bytes());
}

/// Appends one epoch address.
pub(super) fn encode_address_into(out: &mut Vec<u8>, address: EpochAddress) {
    out.extend_from_slice(&address.generation().to_be_bytes());
    encode_dot_into(out, address.declaration());
}

/// One address's raw wire parts beside the unconsumed tail.
pub(super) type AddressParts<'a> = ((u64, (u32, u64)), &'a [u8]);

/// Reads one epoch address's raw parts; the frame owns typed validation.
pub(super) fn read_address_parts(rest: &[u8]) -> Option<AddressParts<'_>> {
    let (generation, rest) = read_u64(rest)?;
    let (dot, rest) = read_dot(rest)?;
    Some(((generation, dot), rest))
}