use web_time::Instant;
use crate::message::Position;
pub(crate) const MAX_STREAMS: usize = 32;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Verdict {
Deliver,
Duplicate,
Gap,
}
#[derive(Clone, Copy, Debug)]
struct Stream {
at: Position,
seen: Instant,
}
#[derive(Debug, Default)]
pub(crate) struct Streams {
streams: Vec<Stream>,
position: Option<Position>,
}
impl Streams {
#[inline]
pub(crate) fn check(&mut self, at: Position, now: Instant) -> Verdict {
match self.streams.iter().rposition(|s| s.at.epoch == at.epoch) {
None => {
self.advance(at, now);
Verdict::Deliver
}
Some(i) => {
let last = self.streams[i].at.offset;
if at.offset <= last {
Verdict::Duplicate
} else if at.offset == last + 1 {
self.advance_at(i, at, now);
Verdict::Deliver
} else {
Verdict::Gap
}
}
}
}
pub(crate) fn advance(&mut self, at: Position, now: Instant) {
match self.streams.iter().rposition(|s| s.at.epoch == at.epoch) {
Some(i) => self.advance_at(i, at, now),
None => {
if self.streams.len() == MAX_STREAMS {
self.streams.remove(0);
}
self.streams.push(Stream { at, seen: now });
self.position = Some(at);
}
}
}
#[inline]
fn advance_at(&mut self, i: usize, at: Position, now: Instant) {
let last = self.streams.len() - 1;
if i != last {
self.streams[i..].rotate_left(1);
}
self.streams[last] = Stream { at, seen: now };
self.position = Some(at);
}
pub(crate) fn raise(&mut self, at: Position, now: Instant) {
match self.streams.iter_mut().find(|s| s.at.epoch == at.epoch) {
Some(stream) => {
if at.offset > stream.at.offset {
*stream = Stream { at, seen: now };
}
}
None => {
if self.streams.len() == MAX_STREAMS {
return;
}
self.streams.insert(0, Stream { at, seen: now });
self.position.get_or_insert(at);
}
}
}
pub(crate) fn forget(&mut self, epoch: u32) {
self.streams.retain(|s| s.at.epoch != epoch);
if self.position.is_some_and(|p| p.epoch == epoch) {
self.position = self.streams.last().map(|s| s.at);
}
}
pub(crate) fn forget_quiet(&mut self, before: Instant, keep: impl Fn(u32) -> bool) {
let quiet: Vec<u32> = self
.streams
.iter()
.filter(|s| s.seen < before && !keep(s.at.epoch))
.map(|s| s.at.epoch)
.collect();
for epoch in quiet {
self.forget(epoch);
}
}
pub(crate) fn position(&self) -> Option<Position> {
self.position
}
pub(crate) fn stream(&self, epoch: u32) -> Option<Position> {
self.streams
.iter()
.rev()
.find(|s| s.at.epoch == epoch)
.map(|s| s.at)
}
pub(crate) fn positions(&self) -> impl Iterator<Item = Position> + '_ {
self.streams.iter().map(|s| s.at)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn at(epoch: u32, offset: u64) -> Position {
Position { epoch, offset }
}
fn now() -> Instant {
Instant::now()
}
#[test]
fn in_order_duplicates_and_gaps() {
let mut s = Streams::default();
assert_eq!(s.check(at(1, 10), now()), Verdict::Deliver);
assert_eq!(s.check(at(1, 11), now()), Verdict::Deliver);
assert_eq!(s.check(at(1, 11), now()), Verdict::Duplicate);
assert_eq!(s.check(at(1, 5), now()), Verdict::Duplicate);
assert_eq!(s.check(at(1, 13), now()), Verdict::Gap);
assert_eq!(s.position(), Some(at(1, 11)));
assert_eq!(s.check(at(1, 12), now()), Verdict::Deliver);
assert_eq!(s.check(at(1, 13), now()), Verdict::Deliver);
}
#[test]
fn streams_of_a_topic_are_in_order_each_on_its_own() {
let mut s = Streams::default();
assert_eq!(s.check(at(1, 10), now()), Verdict::Deliver);
assert_eq!(s.check(at(2, 500), now()), Verdict::Deliver);
assert_eq!(s.check(at(1, 11), now()), Verdict::Deliver);
assert_eq!(s.position(), Some(at(1, 11)));
assert_eq!(s.check(at(2, 501), now()), Verdict::Deliver);
assert_eq!(s.check(at(2, 500), now()), Verdict::Duplicate);
assert_eq!(s.stream(1), Some(at(1, 11)));
assert_eq!(s.stream(3), None);
}
#[test]
fn the_oldest_stream_goes_first() {
let mut s = Streams::default();
for epoch in 0..MAX_STREAMS as u32 {
s.check(at(epoch, 1), now());
}
assert_eq!(s.check(at(0, 2), now()), Verdict::Deliver);
assert_eq!(s.check(at(1000, 1), now()), Verdict::Deliver);
assert_eq!(s.stream(1), None);
assert_eq!(s.stream(0), Some(at(0, 2)));
assert_eq!(s.check(at(1, 1), now()), Verdict::Deliver);
}
#[test]
fn a_stream_raised_starts_or_moves_without_taking_the_position() {
let mut s = Streams::default();
s.raise(at(7, 4), now());
assert_eq!(s.stream(7), Some(at(7, 4)));
assert_eq!(s.check(at(7, 4), now()), Verdict::Duplicate);
assert_eq!(s.check(at(1, 10), now()), Verdict::Deliver);
s.raise(at(1, 12), now());
s.raise(at(7, 2), now());
assert_eq!(s.stream(1), Some(at(1, 12)));
assert_eq!(s.stream(7), Some(at(7, 4)));
assert_eq!(s.position(), Some(at(1, 10)));
let mut positions: Vec<_> = s.positions().collect();
positions.sort_unstable_by_key(|p| p.epoch);
assert_eq!(positions, [at(1, 12), at(7, 4)]);
}
#[test]
fn a_stream_forgotten_takes_the_position_with_it() {
let mut s = Streams::default();
let start = now();
s.check(at(1, 1), start);
s.check(at(2, 1), start + std::time::Duration::from_secs(10));
s.forget(2);
assert_eq!(s.position(), Some(at(1, 1)));
assert_eq!(s.stream(2), None);
s.check(at(2, 5), start + std::time::Duration::from_secs(10));
s.forget_quiet(start + std::time::Duration::from_secs(5), |epoch| {
epoch == 3
});
assert_eq!(s.stream(1), None);
assert_eq!(s.stream(2), Some(at(2, 5)));
}
}