use std::fmt;
use crate::book::checksum::{ChecksumResult, KRAKEN_CHECKSUM_DEPTH};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SeqVerdict {
InOrder,
Duplicate { seq: u128 },
Stale { seq: u128, floor: u128 },
Gap(GapEvidence),
Divergence { expected: u32, computed: u32 },
Reset { previous: u128, observed: u128 },
OutOfOrder { previous: i64, observed: i64 },
Unverifiable(Unverifiable),
}
impl SeqVerdict {
pub fn requires_resnapshot(&self) -> bool {
matches!(
self,
SeqVerdict::Gap(_)
| SeqVerdict::Divergence { .. }
| SeqVerdict::Reset { .. }
| SeqVerdict::OutOfOrder { .. }
)
}
pub fn should_apply(&self) -> bool {
matches!(self, SeqVerdict::InOrder | SeqVerdict::Unverifiable(_))
}
pub fn is_loss(&self) -> bool {
matches!(
self,
SeqVerdict::Gap(_) | SeqVerdict::Divergence { .. } | SeqVerdict::OutOfOrder { .. }
)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub enum LossSize {
Messages(u64),
Updates(u64),
Unknown,
}
impl LossSize {
pub fn messages(self) -> u64 {
match self {
LossSize::Messages(n) => n,
_ => 0,
}
}
pub fn updates(self) -> u64 {
match self {
LossSize::Updates(n) => n,
_ => 0,
}
}
pub fn is_unknown(self) -> bool {
matches!(self, LossSize::Unknown)
}
}
impl fmt::Display for LossSize {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
LossSize::Messages(n) => write!(f, "{n} message(s)"),
LossSize::Updates(n) => write!(f, "{n} update id(s)"),
LossSize::Unknown => write!(f, "an unknown amount"),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct GapEvidence {
pub expected: u128,
pub observed: u128,
pub size: LossSize,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Unverifiable {
AwaitingSnapshot,
VenuePublishesNoSequence,
BookShallowerThanChecksum { have: usize, need: usize },
RenderingWasLossy { levels: usize },
MissingInstrumentMetadata,
MessageCarriedNoCheck,
}
impl fmt::Display for Unverifiable {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Unverifiable::AwaitingSnapshot => write!(f, "no snapshot yet"),
Unverifiable::VenuePublishesNoSequence => {
write!(f, "venue publishes neither sequence nor checksum")
}
Unverifiable::BookShallowerThanChecksum { have, need } => {
write!(f, "book has {have} levels, checksum covers {need}")
}
Unverifiable::RenderingWasLossy { levels } => {
write!(f, "{levels} level(s) lost digits in our own rendering")
}
Unverifiable::MissingInstrumentMetadata => {
write!(f, "instrument precision unknown")
}
Unverifiable::MessageCarriedNoCheck => {
write!(f, "message carried no sequence or checksum")
}
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CounterState {
last: Option<u64>,
step: u64,
restart_floor: u64,
seen: u64,
}
impl CounterState {
pub fn new(step: u64, restart_floor: u64) -> Self {
assert!(step > 0, "a counter that never advances cannot detect loss");
CounterState {
last: None,
step,
restart_floor,
seen: 0,
}
}
pub fn last(&self) -> Option<u64> {
self.last
}
pub fn anchor(&mut self, seq: u64) {
self.last = Some(seq);
}
pub fn reset(&mut self) {
self.last = None;
}
pub fn observe(&mut self, seq: u64) -> SeqVerdict {
self.seen += 1;
let Some(last) = self.last else {
self.last = Some(seq);
return SeqVerdict::InOrder;
};
if seq == last {
return SeqVerdict::Duplicate { seq: seq as u128 };
}
if seq < last {
return if seq <= self.restart_floor {
self.last = Some(seq);
SeqVerdict::Reset {
previous: last as u128,
observed: seq as u128,
}
} else {
SeqVerdict::Stale {
seq: seq as u128,
floor: last as u128,
}
};
}
let expected = last + self.step;
self.last = Some(seq);
if seq == expected {
SeqVerdict::InOrder
} else {
SeqVerdict::Gap(GapEvidence {
expected: expected as u128,
observed: seq as u128,
size: LossSize::Messages((seq - expected) / self.step),
})
}
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct ChecksumState {
last_matched: Option<u32>,
verified: u64,
unverifiable: u64,
}
impl ChecksumState {
pub fn new() -> Self {
Self::default()
}
pub fn verified(&self) -> u64 {
self.verified
}
pub fn unverifiable(&self) -> u64 {
self.unverifiable
}
pub fn reset(&mut self) {
self.last_matched = None;
}
pub fn observe(&mut self, expected: u32, computed: ChecksumResult) -> SeqVerdict {
if computed.lossy_levels > 0 {
self.unverifiable += 1;
return SeqVerdict::Unverifiable(Unverifiable::RenderingWasLossy {
levels: computed.lossy_levels,
});
}
let shallow = computed.bid_levels.min(computed.ask_levels);
if shallow < KRAKEN_CHECKSUM_DEPTH && computed.value != expected {
self.unverifiable += 1;
return SeqVerdict::Unverifiable(Unverifiable::BookShallowerThanChecksum {
have: shallow,
need: KRAKEN_CHECKSUM_DEPTH,
});
}
if computed.value == expected {
self.last_matched = Some(expected);
self.verified += 1;
SeqVerdict::InOrder
} else {
SeqVerdict::Divergence {
expected,
computed: computed.value,
}
}
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct ChainState {
last: Option<u128>,
}
impl ChainState {
pub fn new() -> Self {
Self::default()
}
pub fn last(&self) -> Option<u128> {
self.last
}
pub fn reset(&mut self) {
self.last = None;
}
pub fn observe(&mut self, seq: u128, prev: Option<u128>) -> SeqVerdict {
let Some(last) = self.last else {
self.last = Some(seq);
return SeqVerdict::InOrder;
};
let Some(prev) = prev else {
self.last = Some(seq);
return SeqVerdict::Reset {
previous: last,
observed: seq,
};
};
if prev == last {
self.last = Some(seq);
return SeqVerdict::InOrder;
}
if seq == last {
return SeqVerdict::Duplicate { seq };
}
if seq < last {
return SeqVerdict::Stale { seq, floor: last };
}
self.last = Some(seq);
SeqVerdict::Gap(GapEvidence {
expected: last,
observed: prev,
size: LossSize::Unknown,
})
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct RangeState {
snapshot_id: Option<u64>,
last_id: Option<u64>,
synced: bool,
}
impl RangeState {
pub fn new() -> Self {
Self::default()
}
pub fn is_synced(&self) -> bool {
self.synced
}
pub fn last_id(&self) -> Option<u64> {
self.last_id
}
pub fn reset(&mut self) {
*self = Self::default();
}
pub fn anchor_snapshot(&mut self, last_update_id: u64) {
self.snapshot_id = Some(last_update_id);
self.last_id = None;
self.synced = false;
}
pub fn observe(&mut self, first: u64, last: u64) -> SeqVerdict {
if !self.synced {
let Some(snapshot_id) = self.snapshot_id else {
return SeqVerdict::Unverifiable(Unverifiable::AwaitingSnapshot);
};
if last <= snapshot_id {
return SeqVerdict::Stale {
seq: last as u128,
floor: snapshot_id as u128,
};
}
#[allow(clippy::int_plus_one)]
let straddles = first <= snapshot_id + 1 && snapshot_id + 1 <= last;
if straddles {
self.synced = true;
self.last_id = Some(last);
return SeqVerdict::InOrder;
}
self.last_id = Some(last);
self.synced = true;
return SeqVerdict::Gap(GapEvidence {
expected: (snapshot_id + 1) as u128,
observed: first as u128,
size: LossSize::Updates(first.saturating_sub(snapshot_id + 1)),
});
}
let last_id = self.last_id.expect("synced implies an anchor");
if last <= last_id {
return SeqVerdict::Duplicate { seq: last as u128 };
}
let expected = last_id + 1;
self.last_id = Some(last);
if first == expected {
SeqVerdict::InOrder
} else if first < expected {
SeqVerdict::InOrder
} else {
SeqVerdict::Gap(GapEvidence {
expected: expected as u128,
observed: first as u128,
size: LossSize::Updates(first - expected),
})
}
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct TimestampState {
last: Option<i64>,
floor: Option<i64>,
}
impl TimestampState {
pub fn new() -> Self {
Self::default()
}
pub fn last(&self) -> Option<i64> {
self.last
}
pub fn reset(&mut self) {
*self = Self::default();
}
pub fn anchor_snapshot(&mut self, nanos: i64) {
self.floor = Some(nanos);
self.last = Some(nanos);
}
pub fn observe(&mut self, stamp: i64) -> SeqVerdict {
if let Some(floor) = self.floor
&& stamp <= floor
{
return SeqVerdict::Stale {
seq: stamp.max(0) as u128,
floor: floor.max(0) as u128,
};
}
match self.last {
Some(last) if stamp == last => SeqVerdict::Duplicate {
seq: stamp.max(0) as u128,
},
Some(last) if stamp < last => SeqVerdict::OutOfOrder {
previous: last,
observed: stamp,
},
_ => {
self.last = Some(stamp);
SeqVerdict::Unverifiable(Unverifiable::VenuePublishesNoSequence)
}
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SeqState {
Counter(CounterState),
Checksum(ChecksumState),
Chain(ChainState),
Range(RangeState),
Timestamp(TimestampState),
Unverifiable,
}
impl SeqState {
pub fn counter(step: u64, restart_floor: u64) -> Self {
SeqState::Counter(CounterState::new(step, restart_floor))
}
pub fn checksum() -> Self {
SeqState::Checksum(ChecksumState::new())
}
pub fn chain() -> Self {
SeqState::Chain(ChainState::new())
}
pub fn range() -> Self {
SeqState::Range(RangeState::new())
}
pub fn timestamp() -> Self {
SeqState::Timestamp(TimestampState::new())
}
pub fn reset(&mut self) {
match self {
SeqState::Counter(c) => c.reset(),
SeqState::Checksum(c) => c.reset(),
SeqState::Chain(c) => c.reset(),
SeqState::Range(c) => c.reset(),
SeqState::Timestamp(c) => c.reset(),
SeqState::Unverifiable => {}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn counter() -> CounterState {
CounterState::new(1, 0)
}
#[test]
fn a_continuous_run_is_all_in_order() {
let mut c = counter();
for seq in 100..110 {
assert_eq!(c.observe(seq), SeqVerdict::InOrder, "at {seq}");
}
}
#[test]
fn a_single_missing_message_is_detected_and_counted() {
let mut c = counter();
c.observe(100);
assert_eq!(
c.observe(102),
SeqVerdict::Gap(GapEvidence {
expected: 101,
observed: 102,
size: LossSize::Messages(1)
})
);
}
#[test]
fn a_burst_of_missing_messages_reports_the_exact_count() {
let mut c = counter();
c.observe(5);
let SeqVerdict::Gap(evidence) = c.observe(1_005) else {
panic!("expected a gap")
};
assert_eq!(evidence.size, LossSize::Messages(999));
assert_eq!(evidence.expected, 6);
}
#[test]
fn after_a_gap_the_stream_resynchronises_rather_than_gapping_forever() {
let mut c = counter();
c.observe(1);
assert!(matches!(c.observe(4), SeqVerdict::Gap(_)));
assert_eq!(c.observe(5), SeqVerdict::InOrder);
}
#[test]
fn duplicates_and_stale_messages_are_distinguished_from_loss() {
let mut c = counter();
c.observe(10);
assert_eq!(c.observe(10), SeqVerdict::Duplicate { seq: 10 });
assert_eq!(c.observe(7), SeqVerdict::Stale { seq: 7, floor: 10 });
assert!(!SeqVerdict::Duplicate { seq: 10 }.is_loss());
assert!(!SeqVerdict::Duplicate { seq: 10 }.should_apply());
}
#[test]
fn a_restart_at_the_floor_is_a_reset_not_a_stale_message() {
let mut c = counter();
c.observe(900);
assert_eq!(
c.observe(0),
SeqVerdict::Reset {
previous: 900,
observed: 0
}
);
assert_eq!(c.observe(1), SeqVerdict::InOrder);
}
#[test]
fn the_first_message_can_never_be_a_gap() {
let mut c = counter();
assert_eq!(c.observe(999_999), SeqVerdict::InOrder);
}
#[test]
fn anchoring_to_a_snapshot_makes_the_next_message_checkable() {
let mut c = counter();
c.anchor(500);
assert_eq!(c.observe(501), SeqVerdict::InOrder);
let mut d = counter();
d.anchor(500);
assert!(matches!(d.observe(503), SeqVerdict::Gap(_)));
}
fn result(value: u32, bids: usize, asks: usize, lossy: usize) -> ChecksumResult {
ChecksumResult {
value,
lossy_levels: lossy,
bid_levels: bids,
ask_levels: asks,
}
}
#[test]
fn a_matching_checksum_is_in_order() {
let mut s = ChecksumState::new();
assert_eq!(s.observe(42, result(42, 10, 10, 0)), SeqVerdict::InOrder);
assert_eq!(s.verified(), 1);
}
#[test]
fn a_mismatch_on_a_full_book_is_divergence() {
let mut s = ChecksumState::new();
assert_eq!(
s.observe(42, result(43, 10, 10, 0)),
SeqVerdict::Divergence {
expected: 42,
computed: 43
}
);
assert!(
SeqVerdict::Divergence {
expected: 42,
computed: 43
}
.requires_resnapshot()
);
}
#[test]
fn our_own_lossy_rendering_is_never_reported_as_the_venue_losing_data() {
let mut s = ChecksumState::new();
assert_eq!(
s.observe(42, result(43, 10, 10, 2)),
SeqVerdict::Unverifiable(Unverifiable::RenderingWasLossy { levels: 2 })
);
assert!(!s.observe(42, result(43, 10, 10, 2)).is_loss());
}
#[test]
fn a_shallow_book_yields_unverifiable_rather_than_a_false_gap() {
let mut s = ChecksumState::new();
assert_eq!(
s.observe(42, result(43, 3, 10, 0)),
SeqVerdict::Unverifiable(Unverifiable::BookShallowerThanChecksum { have: 3, need: 10 })
);
assert_eq!(s.unverifiable(), 1);
}
#[test]
fn a_shallow_book_that_still_matches_is_accepted() {
let mut s = ChecksumState::new();
assert_eq!(s.observe(42, result(42, 3, 3, 0)), SeqVerdict::InOrder);
}
#[test]
fn unverifiable_messages_are_still_applied() {
assert!(SeqVerdict::Unverifiable(Unverifiable::AwaitingSnapshot).should_apply());
assert!(!SeqVerdict::Unverifiable(Unverifiable::AwaitingSnapshot).is_loss());
}
#[test]
fn a_chain_holds_when_each_message_names_its_predecessor() {
let mut c = ChainState::new();
assert_eq!(c.observe(80_274_832_416, None), SeqVerdict::InOrder);
assert_eq!(
c.observe(80_274_832_423, Some(80_274_832_416)),
SeqVerdict::InOrder
);
assert_eq!(
c.observe(80_274_832_435, Some(80_274_832_423)),
SeqVerdict::InOrder
);
}
#[test]
fn a_broken_chain_is_a_gap_of_unknowable_size() {
let mut c = ChainState::new();
c.observe(100, None);
let SeqVerdict::Gap(evidence) = c.observe(160, Some(150)) else {
panic!("expected a gap")
};
assert_eq!(evidence.size, LossSize::Unknown);
assert_eq!(evidence.size.messages(), 0);
assert!(evidence.size.is_unknown());
}
#[test]
fn a_chain_resynchronises_after_a_break() {
let mut c = ChainState::new();
c.observe(10, None);
assert!(matches!(c.observe(30, Some(25)), SeqVerdict::Gap(_)));
assert_eq!(c.observe(40, Some(30)), SeqVerdict::InOrder);
}
#[test]
fn a_chain_start_marker_mid_stream_is_a_reset_not_a_gap() {
let mut c = ChainState::new();
c.observe(500, None);
assert_eq!(
c.observe(900, None),
SeqVerdict::Reset {
previous: 500,
observed: 900
}
);
assert_eq!(c.observe(905, Some(900)), SeqVerdict::InOrder);
}
#[test]
fn a_repeated_chain_message_is_a_duplicate() {
let mut c = ChainState::new();
c.observe(10, None);
c.observe(20, Some(10));
assert_eq!(c.observe(20, Some(10)), SeqVerdict::Duplicate { seq: 20 });
}
#[test]
fn a_range_feed_syncs_to_a_snapshot_that_straddles_it() {
let mut r = RangeState::new();
r.anchor_snapshot(3_297_892_542);
assert!(matches!(
r.observe(3_297_892_529, 3_297_892_535),
SeqVerdict::Stale { .. }
));
assert!(!r.is_synced());
assert_eq!(r.observe(3_297_892_543, 3_297_892_543), SeqVerdict::InOrder);
assert!(r.is_synced());
}
#[test]
fn a_range_feed_counts_missing_update_ids_not_missing_messages() {
let mut r = RangeState::new();
r.anchor_snapshot(100);
assert_eq!(r.observe(101, 105), SeqVerdict::InOrder);
let SeqVerdict::Gap(evidence) = r.observe(110, 112) else {
panic!("expected a gap")
};
assert_eq!(evidence.size, LossSize::Updates(4));
assert_eq!(evidence.size.messages(), 0, "these are not messages");
}
#[test]
fn a_snapshot_the_stream_has_already_passed_is_a_gap_not_a_clean_start() {
let mut r = RangeState::new();
r.anchor_snapshot(100);
let SeqVerdict::Gap(evidence) = r.observe(200, 210) else {
panic!("expected a gap")
};
assert_eq!(evidence.size, LossSize::Updates(99));
assert!(
r.is_synced(),
"we are now tracking, just with a hole behind us"
);
}
#[test]
fn a_range_feed_without_a_snapshot_cannot_judge_anything() {
let mut r = RangeState::new();
assert_eq!(
r.observe(1, 2),
SeqVerdict::Unverifiable(Unverifiable::AwaitingSnapshot)
);
}
#[test]
fn an_overlapping_range_is_applied_rather_than_flagged() {
let mut r = RangeState::new();
r.anchor_snapshot(100);
r.observe(101, 110);
assert_eq!(r.observe(108, 115), SeqVerdict::InOrder);
assert!(matches!(r.observe(109, 112), SeqVerdict::Duplicate { .. }));
}
#[test]
fn a_timestamp_feed_never_claims_a_message_was_verified() {
let mut t = TimestampState::new();
for stamp in [1_000i64, 1_001, 5_000, 9_999] {
assert_eq!(
t.observe(stamp),
SeqVerdict::Unverifiable(Unverifiable::VenuePublishesNoSequence),
"stamp {stamp}"
);
}
assert!(!t.observe(10_000).is_loss());
}
#[test]
fn a_timestamp_feed_does_detect_reordering() {
let mut t = TimestampState::new();
t.observe(5_000);
assert_eq!(
t.observe(4_000),
SeqVerdict::OutOfOrder {
previous: 5_000,
observed: 4_000
}
);
assert!(
SeqVerdict::OutOfOrder {
previous: 5_000,
observed: 4_000
}
.requires_resnapshot()
);
}
#[test]
fn a_repeated_timestamp_is_a_duplicate_not_a_reorder() {
let mut t = TimestampState::new();
t.observe(7_000);
assert_eq!(t.observe(7_000), SeqVerdict::Duplicate { seq: 7_000 });
}
#[test]
fn diffs_predating_a_snapshot_are_discarded_rather_than_called_reordered() {
let mut t = TimestampState::new();
t.anchor_snapshot(1_000);
assert!(matches!(t.observe(900), SeqVerdict::Stale { .. }));
assert!(matches!(t.observe(1_000), SeqVerdict::Stale { .. }));
assert!(!t.observe(900).requires_resnapshot());
assert_eq!(
t.observe(2_000),
SeqVerdict::Unverifiable(Unverifiable::VenuePublishesNoSequence)
);
assert_eq!(
t.observe(1_500),
SeqVerdict::OutOfOrder {
previous: 2_000,
observed: 1_500
}
);
}
#[test]
fn out_of_order_does_not_advance_the_timestamp_baseline() {
let mut t = TimestampState::new();
t.observe(5_000);
t.observe(4_000);
assert_eq!(t.last(), Some(5_000));
assert!(!t.observe(6_000).is_loss());
}
}