Skip to main content

hopr_protocol_session/processing/
sequencer.rs

1//! This module defines the [`Sequencer`] stream adaptor.
2
3use std::{
4    collections::BinaryHeap,
5    future::Future,
6    pin::Pin,
7    task::{Context, Poll},
8    time::{Duration, Instant},
9};
10
11use futures_time::future::Timer;
12use tracing::instrument;
13
14use crate::{
15    errors::SessionError,
16    processing::reorder::{ABANDONED_MEMORY, SharedReorder},
17    protocol::FrameId,
18};
19
20/// Floor on a gap timer, so a gap already past its wait still yields to the runtime once.
21const MIN_GAP_WAIT: Duration = Duration::from_millis(1);
22
23/// Buffer entry pairing an item with when it entered the buffer.
24///
25/// Ordering delegates entirely to `item`, so the heap behaves exactly as before; `buffered_at`
26/// exists only to age the entry out.
27#[derive(Clone, Copy, Debug)]
28struct Buffered<T> {
29    item: T,
30    buffered_at: Instant,
31}
32
33impl<T: PartialEq> PartialEq for Buffered<T> {
34    fn eq(&self, other: &Self) -> bool {
35        self.item.eq(&other.item)
36    }
37}
38
39impl<T: Eq> Eq for Buffered<T> {}
40
41impl<T: PartialOrd> PartialOrd for Buffered<T> {
42    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
43        self.item.partial_cmp(&other.item)
44    }
45}
46
47impl<T: Ord> Ord for Buffered<T> {
48    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
49        self.item.cmp(&other.item)
50    }
51}
52
53impl<T: PartialOrd<FrameId>> PartialEq<FrameId> for Buffered<T> {
54    fn eq(&self, other: &FrameId) -> bool {
55        self.item.partial_cmp(other) == Some(std::cmp::Ordering::Equal)
56    }
57}
58
59impl<T: PartialOrd<FrameId>> PartialOrd<FrameId> for Buffered<T> {
60    fn partial_cmp(&self, other: &FrameId) -> Option<std::cmp::Ordering> {
61        self.item.partial_cmp(other)
62    }
63}
64
65/// Sequencer is an adaptor for streams, that yield elements that have a natural ordering and
66/// can be compared with [`FrameId`] and puts them in the correct sequence starting with
67/// `FrameId` equal to 1.
68///
69/// Sequencer internally maintains a `FrameId` to be yielded next, polls the underlying stream
70/// and yields elements only when they match the next `FrameId` to be yielded, incrementing the
71/// value on each yield.
72///
73/// The Sequencer takes to arguments: `max_wait` and `capacity`:
74///
75/// The `max_wait` indicates the maximum amount of time to wait for a certain `FrameId` to
76/// be yielded from the underlying stream. Each gap is timed from when the frame behind it was
77/// buffered, so gaps queued behind one another drain together rather than one `max_wait` each.
78/// If this does not happen, the Segmenter yields an error,
79/// indicating that the given frame was discarded.
80///
81/// The `capacity` parameter sets the maximum number of buffered elements inside the Sequencer.
82/// If this value is reached, the Sequencer will stop polling the underlying stream, waiting for the
83/// next element to expire.
84///
85/// By definition, Sequencer is a fallible stream, yielding either `Ok(Item)`, `Err(`[`SessionError::FrameDiscarded`]`)`
86/// or `Ok(None)` when the underlying stream is closed and no more elements can be yielded.
87///
88/// Use [`SequencerExt`] methods to turn a stream into a sequenced stream.
89#[must_use = "streams do nothing unless polled"]
90#[pin_project::pin_project]
91pub struct Sequencer<S: futures::Stream> {
92    #[pin]
93    inner: S,
94    #[pin]
95    timer: futures_time::task::Sleep,
96    buffer: BinaryHeap<std::cmp::Reverse<Buffered<S::Item>>>,
97    next_id: FrameId,
98    max_wait: Duration,
99    /// Anti-bufferbloat bound: items buffered longer than this are dropped, not emitted, so a
100    /// stall shows up as loss rather than a latency tail. `None` disables it.
101    max_item_age: Option<Duration>,
102    /// Head-of-line bound: abandon the frame due next once the sequence has advanced this far
103    /// past it, rather than holding everything for `max_wait`. `None` disables it.
104    max_frames_behind_gap: Option<usize>,
105    /// Waits on a gap only as long as the reordering seen supports, when set.
106    reorder: Option<SharedReorder>,
107    state: State,
108}
109
110impl<S> Sequencer<S>
111where
112    S: futures::Stream,
113    S::Item: Ord + PartialOrd<FrameId>,
114{
115    /// Creates a new instance, wrapping the given `inner` Segment sink.
116    ///
117    /// The `frame_size` value will be clamped into the `[C, (C - SessionMessage::SEGMENT_OVERHEAD) * SeqIndicator::MAX
118    /// + 1]` interval.
119    fn new(
120        inner: S,
121        max_wait: Duration,
122        capacity: usize,
123        max_item_age: Option<Duration>,
124        max_frames_behind_gap: Option<usize>,
125        reorder: Option<SharedReorder>,
126    ) -> Self {
127        assert!(capacity > 0, "capacity should be positive");
128        Self {
129            inner,
130            buffer: BinaryHeap::with_capacity(capacity),
131            timer: futures_time::task::sleep(max_wait.max(MIN_GAP_WAIT).into()),
132            next_id: 1,
133            max_wait,
134            max_item_age: max_item_age.filter(|age| !age.is_zero()),
135            // Zero would abandon the frame due next before anything had arrived to justify it,
136            // turning every momentary gap into loss. One later frame is the strictest evidence
137            // that still *is* evidence.
138            max_frames_behind_gap: max_frames_behind_gap.map(|n| n.max(1)),
139            reorder,
140            state: State::Polling,
141        }
142    }
143}
144
145#[derive(Clone, Copy, Debug, PartialEq, Eq)]
146enum State {
147    Polling,
148    BufferUpdated,
149    Done,
150}
151
152impl<S> futures::Stream for Sequencer<S>
153where
154    S: futures::Stream,
155    S::Item: Ord + PartialOrd<FrameId>,
156{
157    type Item = Result<S::Item, SessionError>;
158
159    #[instrument(name = "Sequencer::poll_next", level = "trace", skip(self, cx), fields(next_frame_id = self.next_id, state = ?self.state))]
160    fn poll_next(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<Self::Item>> {
161        let mut this = self.project();
162        if *this.next_id == 0 {
163            tracing::debug!("end of frame sequence reached");
164            return Poll::Ready(None);
165        }
166
167        loop {
168            match *this.state {
169                State::Polling => {
170                    if this.buffer.len() < this.buffer.capacity() {
171                        // We still have capacity available, poll the underlying stream
172                        let stream_poll = this.inner.as_mut().poll_next(cx);
173
174                        // Only poll timer if there's something in the buffer
175                        let timer_poll = if !this.buffer.is_empty() {
176                            let poll = this.timer.as_mut().poll(cx);
177                            if poll.is_ready() {
178                                this.timer.as_mut().reset_timer();
179                            }
180                            poll
181                        } else {
182                            Poll::Pending
183                        };
184
185                        match (stream_poll, timer_poll) {
186                            (Poll::Pending, Poll::Pending) => {
187                                tracing::trace!("pending");
188                                *this.state = State::Polling;
189                                return Poll::Pending;
190                            }
191                            (Poll::Ready(Some(item)), _) => {
192                                if item.lt(this.next_id) {
193                                    // Do not accept older frame ids. A frame whose gap was given up
194                                    // is reordering the wait did not cover, and lengthens it.
195                                    let now = Instant::now();
196                                    match this.reorder.as_ref().and_then(|reorder| {
197                                        (1..=ABANDONED_MEMORY as FrameId)
198                                            .map(|back| this.next_id.wrapping_sub(back))
199                                            .find(|id| item.eq(id))
200                                            .and_then(|id| reorder.late(id, now))
201                                            .map(|late| (reorder, late))
202                                    }) {
203                                        Some((reorder, late)) => {
204                                            tracing::debug!(
205                                                late_ms = late.as_millis() as u64,
206                                                "frame came after its gap was given up"
207                                            );
208                                            reorder.record(now, late);
209                                        }
210                                        None => tracing::error!("old item"),
211                                    }
212                                    *this.state = State::Polling;
213                                } else {
214                                    // The frame due next closes its gap: how long it came after the
215                                    // earliest frame waiting behind it is the reordering it took.
216                                    if let Some(reorder) = this.reorder.as_ref()
217                                        && item.eq(this.next_id)
218                                        && let Some(behind_since) = this.buffer.iter().map(|b| b.0.buffered_at).min()
219                                    {
220                                        let now = Instant::now();
221                                        reorder.record(now, now.duration_since(behind_since));
222                                    }
223                                    // Push new item to the buffer
224                                    tracing::trace!("new item");
225                                    this.buffer.push(std::cmp::Reverse(Buffered {
226                                        item,
227                                        buffered_at: Instant::now(),
228                                    }));
229                                    *this.state = State::BufferUpdated;
230                                }
231                            }
232                            (Poll::Ready(None), _) => {
233                                tracing::trace!(len = this.buffer.len(), "stream is done");
234                                *this.state = State::Done
235                            }
236                            (_, Poll::Ready(_)) => {
237                                // Simulate buffer update when the timer elapses
238                                tracing::trace!("timer elapsed");
239                                *this.state = State::BufferUpdated;
240                            }
241                        }
242                    } else {
243                        // Simulate buffer update when at capacity
244                        tracing::warn!("sequencer buffer is full");
245                        *this.state = State::BufferUpdated;
246                    }
247                }
248                State::BufferUpdated => {
249                    // The buffer has been updated, check if we can yield something
250                    if let Some(next) = this.buffer.peek().map(|item| &item.0) {
251                        let max_wait = this
252                            .reorder
253                            .as_ref()
254                            .map_or(*this.max_wait, |reorder| reorder.wait(Instant::now(), *this.max_wait));
255                        if next.eq(this.next_id) {
256                            let stale = this
257                                .max_item_age
258                                .is_some_and(|max_age| next.buffered_at.elapsed() >= max_age);
259
260                            *this.next_id = this.next_id.wrapping_add(1);
261                            *this.state = State::BufferUpdated;
262
263                            // Anti-bufferbloat: the frame is the one due next, but it has been held
264                            // so long that delivering it would only add latency. Report it as
265                            // discarded — the same signal the consumer already handles for a lost
266                            // frame — instead of emitting it late.
267                            if stale {
268                                let discarded = this.next_id.wrapping_sub(1);
269                                this.buffer.pop();
270                                tracing::trace!(discarded, "discard frame that exceeded max age");
271                                return Poll::Ready(Some(Err(SessionError::FrameDiscarded(discarded))));
272                            }
273
274                            tracing::trace!("emit next frame");
275
276                            return Poll::Ready(this.buffer.pop().map(|item| Ok(item.0.item)));
277                        // Each gap waits `max_wait` from the arrival of the frame right behind it, so
278                        // emissions in between don't push it back: K gaps left by one outage drain
279                        // together instead of one per `max_wait`.
280                        } else if next.buffered_at.elapsed() >= max_wait
281                            || this.buffer.len() == this.buffer.capacity()
282                            // The sequence has moved far enough past the gap to conclude the
283                            // missing frame was lost rather than reordered. Waiting out `max_wait`
284                            // cannot change that verdict, and on a session with no retransmission
285                            // nothing else can either.
286                            || this.max_frames_behind_gap.is_some_and(|n| {
287                                // Two readings of the same evidence, because each is blind where
288                                // the other sees. The count catches a run of frames arriving
289                                // behind the gap. The distance catches the case that actually
290                                // dominates under loss: the frames in between never completed, so
291                                // they never reach the sequencer and the buffer stays nearly
292                                // empty however far the sender has moved on.
293                                this.buffer.len() >= n
294                                    // Saturating, not `as`: the bound is configuration, and a value past `FrameId`'s
295                                // range would wrap into a small threshold rather than a large one.
296                                || next.gt(&this.next_id.saturating_add(
297                                    FrameId::try_from(n).unwrap_or(FrameId::MAX).saturating_sub(1),
298                                ))
299                            })
300                        {
301                            let discarded = *this.next_id;
302                            *this.next_id = this.next_id.wrapping_add(1);
303                            *this.state = State::BufferUpdated;
304
305                            tracing::trace!(discarded, "discard frame");
306                            let behind_since = next.buffered_at;
307                            if let Some(reorder) = this.reorder.as_ref() {
308                                reorder.note_abandoned(discarded, behind_since);
309                            }
310
311                            return Poll::Ready(Some(Err(SessionError::FrameDiscarded(discarded))));
312                        }
313                        let remaining = max_wait.saturating_sub(next.buffered_at.elapsed());
314                        // The floor only stands in for a deadline already past, so a sub-millisecond
315                        // `max_wait` is kept as configured.
316                        let wait = if remaining.is_zero() { MIN_GAP_WAIT } else { remaining };
317                        this.timer.set(futures_time::task::sleep(wait.into()));
318                    } else {
319                        tracing::trace!("buffer is empty");
320                    }
321
322                    // Nothing to yield, keep on polling
323                    *this.state = State::Polling;
324                }
325                State::Done => {
326                    // The underlying stream is done, drain what we have in the internal buffer
327                    return if let Some(next) = this.buffer.peek().map(|item| &item.0) {
328                        if next.lt(this.next_id) {
329                            tracing::error!("old item");
330                            this.buffer.pop();
331                            continue;
332                        } else if next.eq(this.next_id) {
333                            *this.next_id = this.next_id.wrapping_add(1);
334                            tracing::trace!("emit next frame when done");
335
336                            Poll::Ready(this.buffer.pop().map(|item| Ok(item.0.item)))
337                        } else {
338                            let discarded = *this.next_id;
339                            *this.next_id = this.next_id.wrapping_add(1);
340                            tracing::trace!(discarded, "discard frame when done");
341
342                            Poll::Ready(Some(Err(SessionError::FrameDiscarded(discarded))))
343                        }
344                    } else {
345                        tracing::trace!("buffer is empty and done");
346                        Poll::Ready(None)
347                    };
348                }
349            }
350        }
351    }
352}
353
354/// How a [`Sequencer`] decides to stop waiting for a frame that has not arrived.
355///
356/// Grouped rather than passed positionally: the two stopping rules below answer different
357/// questions, and a bare list of `Duration`/`Option<usize>` arguments at the call site gives no
358/// hint which is which.
359#[derive(Clone, Copy, Debug)]
360pub struct SequencerConfig {
361    /// Longest the frame due next is waited for before it is abandoned.
362    pub max_wait: Duration,
363    /// Maximum number of buffered items.
364    pub capacity: usize,
365    /// Discards items buffered longer than this instead of emitting them late; `None` disables.
366    pub max_item_age: Option<Duration>,
367    /// Abandons the frame due next once this many later frames are already waiting behind it.
368    ///
369    /// `None` waits out [`Self::max_wait`] regardless of how much has piled up, which is correct
370    /// only when the missing frame can still be recovered. On a session without retransmission it
371    /// cannot: the wait is for something that is never coming, and everything already received is
372    /// held behind it for the full duration.
373    ///
374    /// Counting later frames rather than watching a clock makes the decision on evidence. One or
375    /// two frames arriving ahead is ordinary reordering across paths of differing latency; a queue
376    /// building up behind a gap is a frame that was lost.
377    pub max_frames_behind_gap: Option<usize>,
378    /// Waits on a gap only as long as the reordering this sequence has shown supports: twice the
379    /// deepest of the last minute, at least 250 ms, at most [`Self::max_wait`], and all of
380    /// [`Self::max_wait`] before any reordering is seen.
381    ///
382    /// For a sequence that is not retransmitted. `max_wait` is sized for the worst a deployment
383    /// may see, so a frame lost on a sequence whose frames arrive within a few hundred
384    /// milliseconds of each other holds everything behind it for seconds, waiting for something
385    /// that is never coming. A frame that comes after its gap was given up lengthens the wait.
386    pub adapt_to_reordering: bool,
387}
388
389/// Stream extensions methods for item sequencing.
390pub trait SequencerExt: futures::Stream {
391    /// Attaches a [`Sequencer`] to the underlying stream, given the item `timeout` and `capacity`
392    /// of items.
393    fn sequencer(self, timeout: Duration, capacity: usize) -> Sequencer<Self>
394    where
395        Self::Item: Ord + PartialOrd<FrameId>,
396        Self: Sized,
397    {
398        Sequencer::new(self, timeout, capacity, None, None, None)
399    }
400
401    /// As [`SequencerExt::sequencer`], but discards items buffered longer than `max_item_age`
402    /// instead of emitting them late.
403    fn sequencer_with_max_age(
404        self,
405        timeout: Duration,
406        capacity: usize,
407        max_item_age: Option<Duration>,
408    ) -> Sequencer<Self>
409    where
410        Self::Item: Ord + PartialOrd<FrameId>,
411        Self: Sized,
412    {
413        Sequencer::new(self, timeout, capacity, max_item_age, None, None)
414    }
415
416    /// As [`SequencerExt::sequencer`], with every stopping rule stated explicitly.
417    fn sequencer_with(self, cfg: SequencerConfig) -> Sequencer<Self>
418    where
419        Self::Item: Ord + PartialOrd<FrameId>,
420        Self: Sized,
421    {
422        self.sequencer_sharing(cfg, None)
423    }
424
425    /// As [`SequencerExt::sequencer_with`], adapting the gap wait to a window of reordering that
426    /// others record into as well (the Session's reassembler) when
427    /// [`SequencerConfig::adapt_to_reordering`] is set; with `reorder` `None`, the window holds this
428    /// sequencer's own samples alone.
429    fn sequencer_sharing(self, cfg: SequencerConfig, reorder: Option<SharedReorder>) -> Sequencer<Self>
430    where
431        Self::Item: Ord + PartialOrd<FrameId>,
432        Self: Sized,
433    {
434        Sequencer::new(
435            self,
436            cfg.max_wait,
437            cfg.capacity,
438            cfg.max_item_age,
439            cfg.max_frames_behind_gap,
440            cfg.adapt_to_reordering.then(|| reorder.unwrap_or_default()),
441        )
442    }
443}
444
445impl<T: ?Sized> SequencerExt for T where T: futures::Stream {}
446
447#[cfg(test)]
448mod tests {
449    use futures::{SinkExt, StreamExt, TryStreamExt, pin_mut};
450    use futures_time::future::FutureExt;
451
452    use super::*;
453    use crate::processing::reorder::REORDER_FLOOR;
454
455    #[test_log::test(tokio::test)]
456    async fn sequencer_should_return_entries_in_order() -> anyhow::Result<()> {
457        let mut expected = vec![4u32, 1, 5, 7, 8, 6, 2, 3];
458
459        let actual: Vec<u32> = futures::stream::iter(expected.clone())
460            .sequencer(Duration::from_secs(5), 4096)
461            .try_collect()
462            .timeout(futures_time::time::Duration::from_secs(5))
463            .await??;
464
465        expected.sort();
466        assert_eq!(expected, actual);
467
468        Ok(())
469    }
470
471    #[test_log::test(tokio::test)]
472    async fn sequencer_should_discard_entries_that_exceeded_the_max_age() -> anyhow::Result<()> {
473        let (seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
474
475        // `max_wait` is long, so nothing here is discarded for being *missing* — only for being stale.
476        let seq_stream =
477            seq_stream.sequencer_with_max_age(Duration::from_secs(30), 4096, Some(Duration::from_millis(100)));
478
479        pin_mut!(seq_sink);
480        pin_mut!(seq_stream);
481
482        // Frame 2 arrives first and waits in the buffer for the missing frame 1 — a transport stall.
483        seq_sink.send(2u32).await?;
484
485        // Drive the sequencer so frame 2 actually lands in its buffer; until it is polled the item
486        // only sits in the channel and its buffered-at clock has not started.
487        assert!(
488            seq_stream
489                .try_next()
490                .timeout(futures_time::time::Duration::from_millis(50))
491                .await
492                .is_err(),
493            "nothing is emitted while frame 1 is missing"
494        );
495
496        tokio::time::sleep(std::time::Duration::from_millis(250)).await;
497
498        // Frame 1 arrives fresh and is delivered; frame 2 is now 250 ms stale and must be
499        // reported as discarded rather than handed over a quarter of a second late.
500        seq_sink.send(1u32).await?;
501
502        assert_eq!(Some(1), seq_stream.try_next().await?, "the fresh frame is delivered");
503        assert!(
504            matches!(seq_stream.try_next().await, Err(SessionError::FrameDiscarded(2))),
505            "the stale frame must be discarded, not delivered late"
506        );
507
508        Ok(())
509    }
510
511    #[test_log::test(tokio::test)]
512    async fn sequencer_should_deliver_entries_within_the_max_age() -> anyhow::Result<()> {
513        let (seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
514
515        let seq_stream =
516            seq_stream.sequencer_with_max_age(Duration::from_secs(30), 4096, Some(Duration::from_secs(30)));
517
518        pin_mut!(seq_sink);
519        pin_mut!(seq_stream);
520
521        // Same out-of-order arrival and the same buffering delay, but comfortably inside the
522        // bound: nothing is dropped.
523        seq_sink.send(2u32).await?;
524        assert!(
525            seq_stream
526                .try_next()
527                .timeout(futures_time::time::Duration::from_millis(50))
528                .await
529                .is_err()
530        );
531        tokio::time::sleep(std::time::Duration::from_millis(250)).await;
532        seq_sink.send(1u32).await?;
533
534        assert_eq!(Some(1), seq_stream.try_next().await?);
535        assert_eq!(Some(2), seq_stream.try_next().await?);
536
537        Ok(())
538    }
539
540    #[test_log::test(tokio::test)]
541    async fn sequencer_should_not_allow_emitted_entries() -> anyhow::Result<()> {
542        let (seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
543
544        let seq_stream = seq_stream.sequencer(Duration::from_secs(1), 4096);
545
546        pin_mut!(seq_sink);
547        pin_mut!(seq_stream);
548
549        seq_sink.send(1u32).await?;
550        assert_eq!(Some(1), seq_stream.try_next().await?);
551
552        seq_sink.send(2u32).await?;
553        assert_eq!(Some(2), seq_stream.try_next().await?);
554
555        seq_sink.send(2u32).await?;
556        seq_sink.send(1u32).await?;
557
558        seq_sink.send(3u32).await?;
559        assert_eq!(Some(3), seq_stream.try_next().await?);
560
561        Ok(())
562    }
563
564    /// Frames waiting behind a gap must not be held for `max_wait`.
565    ///
566    /// This is the head-of-line stall, measured on a live cluster: with `max_wait` at 3 s a
567    /// session returning 98.5 % of its bytes over the wire delivered 0.60 % of them to the
568    /// application, and the application-side inter-arrival median sat exactly on the timeout. On a
569    /// session with no retransmission the missing frame is never coming, so every second of that
570    /// wait is spent on an outcome that cannot change while the frames already received are held.
571    #[test_log::test(tokio::test)]
572    async fn sequencer_should_abandon_a_gap_once_enough_later_frames_are_waiting() -> anyhow::Result<()> {
573        // Far longer than the test should take, so any reliance on the timer trips the bound below
574        // rather than becoming a matter of tuning margins.
575        let max_wait = Duration::from_secs(5);
576        let (mut seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
577
578        // Frame 1 never arrives.
579        for v in [2u32, 3, 4] {
580            seq_sink.feed(v).await?;
581        }
582        seq_sink.flush().await?;
583
584        let seq_stream = seq_stream.sequencer_with(SequencerConfig {
585            max_wait,
586            capacity: 4096,
587            max_item_age: None,
588            max_frames_behind_gap: Some(2),
589            adapt_to_reordering: false,
590        });
591        pin_mut!(seq_stream);
592
593        // The bound is the assertion: without the rule the sequencer holds everything for the full
594        // `max_wait`, so a regression trips the timeout instead of blocking the suite for 5 s.
595        let released: Vec<u32> = tokio::time::timeout(max_wait / 2, async {
596            assert!(
597                matches!(seq_stream.try_next().await, Err(SessionError::FrameDiscarded(1))),
598                "the gap must be reported as loss, the signal the consumer already handles"
599            );
600            seq_stream.by_ref().take(3).try_collect().await
601        })
602        .await
603        .map_err(|_| anyhow::anyhow!("frames already received waited on a frame that is never coming"))??;
604
605        assert_eq!(vec![2, 3, 4], released, "everything behind the gap must follow it out");
606
607        // Held open deliberately: closing the sink would drain the buffer through `State::Done`,
608        // which has its own emit path and would pass this test without the rule under test.
609        drop(seq_sink);
610        Ok(())
611    }
612
613    /// Under real loss the frames between the gap and the newest arrival mostly never complete, so
614    /// they never reach the sequencer at all and the buffer stays nearly empty. A rule counting
615    /// buffered frames then never fires and the timeout takes over — which is exactly what a
616    /// cluster showed: at an identical setting the scenario delivered 95–97 % on some runs and
617    /// 0.5 % on others, the failing ones with an application-side inter-arrival median sitting
618    /// back on the 3 s timeout.
619    ///
620    /// What is available regardless is how far the sequence has advanced past the gap. One frame
621    /// arriving at id 40 says as much about frame 1 as forty buffered frames would.
622    #[test_log::test(tokio::test)]
623    async fn sequencer_should_abandon_a_gap_when_the_sequence_has_advanced_past_it() -> anyhow::Result<()> {
624        let max_wait = Duration::from_secs(5);
625        let (mut seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
626
627        // Frame 1 is missing and frames 2..=39 never completed, so only one frame is buffered --
628        // far below any count-based threshold, yet the sequence has clearly moved on.
629        seq_sink.feed(40u32).await?;
630        seq_sink.flush().await?;
631
632        let seq_stream = seq_stream.sequencer_with(SequencerConfig {
633            max_wait,
634            capacity: 4096,
635            max_item_age: None,
636            max_frames_behind_gap: Some(4),
637            adapt_to_reordering: false,
638        });
639        pin_mut!(seq_stream);
640
641        // Only the frames that the sequence has genuinely left behind. The last `n - 1` before the
642        // newest arrival are still inside the reordering window -- the sequence has not advanced
643        // far enough past *them* to call them lost -- so they keep the timeout, which is the
644        // conservative half of the same rule.
645        let now = Instant::now();
646        for expected_gap in 1..=36u32 {
647            assert!(
648                matches!(
649                    seq_stream.try_next().await,
650                    Err(SessionError::FrameDiscarded(id)) if id == expected_gap
651                ),
652                "frame {expected_gap} is behind the advanced sequence and must be given up on"
653            );
654        }
655        assert!(
656            now.elapsed() < max_wait / 2,
657            "a single frame far ahead is evidence enough, with no frames buffered behind the gap to count; took {:?}",
658            now.elapsed()
659        );
660
661        drop(seq_sink);
662        Ok(())
663    }
664
665    /// The inverse, so the rule cannot become "never wait". Below the threshold the sequencer must
666    /// still hold the gap open — one frame arriving ahead is ordinary reordering across paths of
667    /// differing latency, not a loss.
668    #[test_log::test(tokio::test)]
669    async fn sequencer_should_keep_waiting_while_fewer_frames_are_behind_the_gap() -> anyhow::Result<()> {
670        let max_wait = Duration::from_millis(300);
671        let (mut seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
672
673        // Frame 1 is missing and only one frame is waiting behind it, under the threshold of 3.
674        seq_sink.feed(2u32).await?;
675        seq_sink.flush().await?;
676
677        let seq_stream = seq_stream.sequencer_with(SequencerConfig {
678            max_wait,
679            capacity: 4096,
680            max_item_age: None,
681            max_frames_behind_gap: Some(3),
682            adapt_to_reordering: false,
683        });
684        pin_mut!(seq_stream);
685
686        let now = Instant::now();
687        assert!(matches!(
688            seq_stream.try_next().await,
689            Err(SessionError::FrameDiscarded(1))
690        ));
691        assert!(
692            now.elapsed() >= max_wait,
693            "under the threshold the timeout still governs; took {:?}",
694            now.elapsed()
695        );
696
697        drop(seq_sink);
698        Ok(())
699    }
700
701    /// A session that *can* recover a missing frame must be unaffected: `None` keeps the timeout
702    /// as the only rule, however much piles up behind the gap.
703    #[test_log::test(tokio::test)]
704    async fn sequencer_without_the_gap_bound_should_still_wait_for_the_timeout() -> anyhow::Result<()> {
705        let max_wait = Duration::from_millis(300);
706        let (mut seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
707
708        for v in [2u32, 3, 4, 5, 6] {
709            seq_sink.feed(v).await?;
710        }
711        seq_sink.flush().await?;
712
713        let seq_stream = seq_stream.sequencer_with(SequencerConfig {
714            max_wait,
715            capacity: 4096,
716            max_item_age: None,
717            max_frames_behind_gap: None,
718            adapt_to_reordering: false,
719        });
720        pin_mut!(seq_stream);
721
722        let now = Instant::now();
723        assert!(matches!(
724            seq_stream.try_next().await,
725            Err(SessionError::FrameDiscarded(1))
726        ));
727        assert!(
728            now.elapsed() >= max_wait,
729            "with no gap bound the timeout is the only rule; took {:?}",
730            now.elapsed()
731        );
732
733        drop(seq_sink);
734        Ok(())
735    }
736
737    #[test_log::test(tokio::test)]
738    async fn sequencer_should_discard_entry_on_timeout() -> anyhow::Result<()> {
739        let timeout = Duration::from_millis(25);
740        let (mut seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
741
742        let input = vec![2u32, 1, 4, 5, 8, 7, 9, 11, 10];
743
744        let input_clone = input.clone();
745        let jh = hopr_utils::runtime::prelude::spawn(async move {
746            for v in input_clone {
747                seq_sink
748                    .feed(v)
749                    .delay(futures_time::time::Duration::from_millis(5))
750                    .await?;
751            }
752            seq_sink.flush().await?;
753            seq_sink.close().await
754        });
755
756        let seq_stream = seq_stream.sequencer(timeout, 4096);
757
758        pin_mut!(seq_stream);
759
760        assert_eq!(Some(1), seq_stream.try_next().await?);
761        assert_eq!(Some(2), seq_stream.try_next().await?);
762
763        let now = Instant::now();
764        assert!(matches!(
765            seq_stream.try_next().await,
766            Err(SessionError::FrameDiscarded(3))
767        ));
768        assert!(now.elapsed() >= timeout);
769
770        assert_eq!(Some(4), seq_stream.try_next().await?);
771        assert_eq!(Some(5), seq_stream.try_next().await?);
772
773        assert!(matches!(
774            seq_stream.try_next().await,
775            Err(SessionError::FrameDiscarded(6))
776        ));
777
778        assert_eq!(Some(7), seq_stream.try_next().await?);
779        assert_eq!(Some(8), seq_stream.try_next().await?);
780        assert_eq!(Some(9), seq_stream.try_next().await?);
781        assert_eq!(Some(10), seq_stream.try_next().await?);
782        assert_eq!(Some(11), seq_stream.try_next().await?);
783
784        assert_eq!(None, seq_stream.try_next().await?);
785
786        let _ = jh.await?;
787        Ok(())
788    }
789
790    #[test_log::test(tokio::test)]
791    async fn sequencer_should_discard_entry_close() -> anyhow::Result<()> {
792        let (seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
793
794        let input = vec![2u32, 1, 3, 5, 4, 8, 11];
795
796        hopr_utils::runtime::prelude::spawn(futures::stream::iter(input.clone()).map(Ok).forward(seq_sink)).await??;
797
798        let seq_stream = seq_stream.sequencer(Duration::from_millis(25), 4096);
799
800        pin_mut!(seq_stream);
801
802        assert_eq!(Some(1), seq_stream.try_next().await?);
803        assert_eq!(Some(2), seq_stream.try_next().await?);
804        assert_eq!(Some(3), seq_stream.try_next().await?);
805        assert_eq!(Some(4), seq_stream.try_next().await?);
806        assert_eq!(Some(5), seq_stream.try_next().await?);
807        assert!(matches!(
808            seq_stream.try_next().await,
809            Err(SessionError::FrameDiscarded(6))
810        ));
811        assert!(matches!(
812            seq_stream.try_next().await,
813            Err(SessionError::FrameDiscarded(7))
814        ));
815        assert_eq!(Some(8), seq_stream.try_next().await?);
816        assert!(matches!(
817            seq_stream.try_next().await,
818            Err(SessionError::FrameDiscarded(9))
819        ));
820        assert!(matches!(
821            seq_stream.try_next().await,
822            Err(SessionError::FrameDiscarded(10))
823        ));
824        assert_eq!(Some(11), seq_stream.try_next().await?);
825        assert_eq!(None, seq_stream.try_next().await?);
826
827        Ok(())
828    }
829
830    #[test_log::test(tokio::test)]
831    async fn sequencer_should_discard_entry_when_inner_stream_pending() -> anyhow::Result<()> {
832        let sent = vec![4u32, 1, 7, 8, 6, 2, 3];
833        let (tx, rx) = futures::channel::mpsc::unbounded();
834
835        pin_mut!(tx);
836        tx.send_all(&mut futures::stream::iter(sent.clone()).map(Ok)).await?;
837
838        let rx = rx.sequencer(Duration::from_millis(10), 4096);
839        pin_mut!(rx);
840
841        assert!(matches!(rx.next().await, Some(Ok(1))));
842        assert!(matches!(rx.next().await, Some(Ok(2))));
843        assert!(matches!(rx.next().await, Some(Ok(3))));
844        assert!(matches!(rx.next().await, Some(Ok(4))));
845        assert!(matches!(rx.next().await, Some(Err(SessionError::FrameDiscarded(5)))));
846        assert!(matches!(rx.next().await, Some(Ok(6))));
847        assert!(matches!(rx.next().await, Some(Ok(7))));
848        assert!(matches!(rx.next().await, Some(Ok(8))));
849
850        Ok(())
851    }
852
853    #[test_log::test(tokio::test)]
854    async fn sequencer_should_discard_entry_when_capacity_is_reached() -> anyhow::Result<()> {
855        let sent = vec![4u32, 5, 7, 8, 2, 6, 3];
856        let (tx, rx) = futures::channel::mpsc::unbounded();
857
858        pin_mut!(tx);
859        tx.send_all(&mut futures::stream::iter(sent.clone()).map(Ok)).await?;
860
861        let rx = rx.sequencer(Duration::from_millis(10), 4);
862        pin_mut!(rx);
863
864        assert!(matches!(rx.next().await, Some(Err(SessionError::FrameDiscarded(1)))));
865        assert!(matches!(rx.next().await, Some(Err(SessionError::FrameDiscarded(2)))));
866        assert!(matches!(rx.next().await, Some(Err(SessionError::FrameDiscarded(3)))));
867        assert!(matches!(rx.next().await, Some(Ok(4))));
868        assert!(matches!(rx.next().await, Some(Ok(5))));
869        assert!(matches!(rx.next().await, Some(Ok(6))));
870        assert!(matches!(rx.next().await, Some(Ok(7))));
871        assert!(matches!(rx.next().await, Some(Ok(8))));
872
873        Ok(())
874    }
875
876    #[test_log::test(tokio::test)]
877    async fn sequencer_should_drain_contiguous_gap_within_single_timeout_window() -> anyhow::Result<()> {
878        let timeout = Duration::from_millis(50);
879        let (tx, rx) = futures::channel::mpsc::unbounded();
880
881        pin_mut!(tx);
882        tx.send_all(&mut futures::stream::iter([1u32, 2, 10, 11, 12]).map(Ok))
883            .await?;
884
885        let rx = rx.sequencer(timeout, 4096);
886        pin_mut!(rx);
887
888        assert_eq!(Some(1), rx.try_next().await?);
889        assert_eq!(Some(2), rx.try_next().await?);
890
891        let now = Instant::now();
892        for expected in 3u32..=9 {
893            assert!(matches!(
894                rx.next().await,
895                Some(Err(SessionError::FrameDiscarded(id))) if id == expected
896            ));
897        }
898        assert_eq!(Some(10), rx.try_next().await?);
899        assert_eq!(Some(11), rx.try_next().await?);
900        assert_eq!(Some(12), rx.try_next().await?);
901
902        // The 7-frame gap must be flushed after one timeout window,
903        // not at a rate of one frame per window.
904        assert!(
905            now.elapsed() < 3 * timeout,
906            "gap drain took {:?}, expected well under {:?}",
907            now.elapsed(),
908            7 * timeout
909        );
910
911        Ok(())
912    }
913
914    #[test_log::test(tokio::test)]
915    async fn sequencer_should_drain_interleaved_gaps_within_single_timeout_window() -> anyhow::Result<()> {
916        let timeout = Duration::from_millis(50);
917        let (tx, rx) = futures::channel::mpsc::unbounded();
918
919        pin_mut!(tx);
920        tx.send_all(&mut futures::stream::iter([1u32, 3, 5, 7, 9, 11]).map(Ok))
921            .await?;
922
923        let rx = rx.sequencer(timeout, 4096);
924        pin_mut!(rx);
925
926        assert_eq!(Some(1), rx.try_next().await?);
927
928        let now = Instant::now();
929        for frame in [3u32, 5, 7, 9, 11] {
930            assert!(matches!(
931                rx.next().await,
932                Some(Err(SessionError::FrameDiscarded(id))) if id == frame - 1
933            ));
934            assert_eq!(Some(frame), rx.try_next().await?);
935        }
936
937        assert!(
938            now.elapsed() < 2 * timeout,
939            "interleaved gaps took {:?} to drain, expected about one {:?} window",
940            now.elapsed(),
941            timeout
942        );
943
944        Ok(())
945    }
946
947    #[test_log::test(tokio::test)]
948    async fn sequencer_should_not_discard_gap_filled_within_timeout() -> anyhow::Result<()> {
949        let timeout = Duration::from_millis(100);
950        let (tx, rx) = futures::channel::mpsc::unbounded();
951
952        let rx = rx.sequencer(timeout, 4096);
953        pin_mut!(tx);
954        pin_mut!(rx);
955
956        tx.send(1u32).await?;
957        tx.send(3u32).await?;
958        assert_eq!(Some(1), rx.try_next().await?);
959        // Frame 3 is only buffered, and its wait started, once the sequencer is polled again.
960        assert!(futures::poll!(rx.next()).is_pending());
961
962        tokio::time::sleep(timeout / 2).await;
963        tx.send(2u32).await?;
964        assert_eq!(Some(2), rx.try_next().await?);
965        assert_eq!(Some(3), rx.try_next().await?);
966
967        Ok(())
968    }
969
970    #[test_log::test(tokio::test)]
971    async fn sequencer_must_terminate_on_last_frame_id() -> anyhow::Result<()> {
972        let (tx, rx) = futures::channel::mpsc::unbounded();
973
974        pin_mut!(tx);
975        tx.send_all(&mut futures::stream::iter([FrameId::MAX - 1, FrameId::MAX, 1, 2]).map(Ok))
976            .await?;
977
978        let mut rx = rx.sequencer(Duration::from_millis(10), 1024);
979        rx.next_id = FrameId::MAX - 1;
980        pin_mut!(rx);
981
982        const LAST_ID: FrameId = FrameId::MAX - 1;
983        assert!(matches!(rx.next().await, Some(Ok(LAST_ID))));
984        assert!(matches!(rx.next().await, Some(Ok(FrameId::MAX))));
985        assert!(rx.next().await.is_none());
986
987        Ok(())
988    }
989
990    #[test_log::test(tokio::test(flavor = "multi_thread"))]
991    async fn sequencer_must_not_discard_frames_when_buffer_was_empty_after_timeout() -> anyhow::Result<()> {
992        let (tx, rx) = futures::channel::mpsc::unbounded();
993
994        let jh = tokio::task::spawn(async move {
995            tokio::time::sleep(Duration::from_millis(2)).await;
996            pin_mut!(tx);
997            tx.send_all(&mut futures::stream::iter([3, 1, 2, 4]).map(Ok)).await?;
998
999            tokio::time::sleep(Duration::from_millis(150)).await;
1000
1001            tx.send_all(&mut futures::stream::iter([6, 5, 7]).map(Ok)).await?;
1002
1003            anyhow::Ok(())
1004        });
1005
1006        let chunks = rx
1007            .sequencer(Duration::from_millis(50), 1024)
1008            .try_ready_chunks(10)
1009            .try_collect::<Vec<Vec<_>>>()
1010            .await?;
1011
1012        assert_eq!(chunks, vec![vec![1, 2, 3, 4], vec![5, 6, 7]]);
1013        jh.await??;
1014
1015        Ok(())
1016    }
1017
1018    fn adaptive(max_wait: Duration) -> SequencerConfig {
1019        SequencerConfig {
1020            max_wait,
1021            capacity: 4096,
1022            max_item_age: None,
1023            max_frames_behind_gap: None,
1024            adapt_to_reordering: true,
1025        }
1026    }
1027
1028    /// Feeds `late` after `early`, `apart` apart, as two frames that swapped places on the way.
1029    async fn reorder<S>(
1030        sink: &mut futures::channel::mpsc::UnboundedSender<u32>,
1031        seq: &mut std::pin::Pin<&mut S>,
1032        early: u32,
1033        late: u32,
1034        apart: Duration,
1035    ) -> anyhow::Result<()>
1036    where
1037        S: futures::Stream<Item = Result<u32, SessionError>>,
1038    {
1039        sink.unbounded_send(early)?;
1040        // The sequencer buffers `early` here and holds it behind the gap.
1041        assert!(
1042            tokio::time::timeout(apart, seq.next()).await.is_err(),
1043            "{early} must wait for {late}"
1044        );
1045        sink.unbounded_send(late)?;
1046        assert_eq!(Some(late), seq.next().await.transpose()?);
1047        assert_eq!(Some(early), seq.next().await.transpose()?);
1048        Ok(())
1049    }
1050
1051    /// How long the sequencer takes to give up on `missing` once `behind` is waiting.
1052    async fn time_to_abandon<S>(
1053        sink: &mut futures::channel::mpsc::UnboundedSender<u32>,
1054        seq: &mut std::pin::Pin<&mut S>,
1055        missing: u32,
1056        behind: u32,
1057    ) -> anyhow::Result<Duration>
1058    where
1059        S: futures::Stream<Item = Result<u32, SessionError>>,
1060    {
1061        sink.unbounded_send(behind)?;
1062        let start = Instant::now();
1063        assert!(matches!(seq.next().await, Some(Err(SessionError::FrameDiscarded(id))) if id == missing));
1064        let took = start.elapsed();
1065        assert_eq!(Some(behind), seq.next().await.transpose()?);
1066        Ok(took)
1067    }
1068
1069    /// Before any reordering is seen there is nothing to size the wait by, so a gap waits all of
1070    /// `max_wait`, as without the adaptation.
1071    #[test_log::test(tokio::test)]
1072    async fn an_adaptive_gap_wait_should_be_max_wait_before_any_reordering() -> anyhow::Result<()> {
1073        let max_wait = Duration::from_millis(600);
1074        let (mut sink, stream) = futures::channel::mpsc::unbounded();
1075        let seq = stream.sequencer_with(adaptive(max_wait));
1076        pin_mut!(seq);
1077
1078        let took = time_to_abandon(&mut sink, &mut seq, 1, 2).await?;
1079        assert!(took >= max_wait - Duration::from_millis(20), "{took:?}");
1080        Ok(())
1081    }
1082
1083    /// Frames that came 100 ms out of order: the next gap is given up after the 250 ms floor
1084    /// rather than the 5 s `max_wait`.
1085    #[test_log::test(tokio::test)]
1086    async fn an_adaptive_gap_wait_should_follow_the_reordering_seen() -> anyhow::Result<()> {
1087        let max_wait = Duration::from_secs(5);
1088        let (mut sink, stream) = futures::channel::mpsc::unbounded();
1089        let seq = stream.sequencer_sharing(adaptive(max_wait), Some(SharedReorder::warmed()));
1090        pin_mut!(seq);
1091
1092        reorder(&mut sink, &mut seq, 2, 1, Duration::from_millis(100)).await?;
1093        let took = time_to_abandon(&mut sink, &mut seq, 3, 4).await?;
1094        assert!(took >= REORDER_FLOOR - Duration::from_millis(20), "{took:?}");
1095        assert!(took < Duration::from_secs(1), "{took:?}");
1096        Ok(())
1097    }
1098
1099    /// Twice the deepest reordering, above the floor: 400 ms apart, an 800 ms wait.
1100    #[test_log::test(tokio::test)]
1101    async fn an_adaptive_gap_wait_should_be_twice_the_deepest_reordering() -> anyhow::Result<()> {
1102        let max_wait = Duration::from_secs(5);
1103        let (mut sink, stream) = futures::channel::mpsc::unbounded();
1104        let window = SharedReorder::warmed();
1105        window.record(Instant::now(), Duration::from_millis(400));
1106        let seq = stream.sequencer_sharing(adaptive(max_wait), Some(window));
1107        pin_mut!(seq);
1108
1109        let took = time_to_abandon(&mut sink, &mut seq, 1, 2).await?;
1110        assert!(took >= Duration::from_millis(780), "{took:?}");
1111        assert!(took < Duration::from_millis(1500), "{took:?}");
1112        Ok(())
1113    }
1114
1115    /// A frame that comes after its gap was given up is reordering the wait did not cover: it is
1116    /// dropped as before, and the wait grows to cover it.
1117    #[test_log::test(tokio::test)]
1118    async fn a_frame_after_its_abandoned_gap_should_lengthen_the_wait() -> anyhow::Result<()> {
1119        let max_wait = Duration::from_secs(5);
1120        let (mut sink, stream) = futures::channel::mpsc::unbounded();
1121        let seq = stream.sequencer_sharing(adaptive(max_wait), Some(SharedReorder::warmed()));
1122        pin_mut!(seq);
1123
1124        reorder(&mut sink, &mut seq, 2, 1, Duration::from_millis(100)).await?;
1125        // Frame 3 is given up after the floor ...
1126        let took = time_to_abandon(&mut sink, &mut seq, 3, 4).await?;
1127        assert!(took < Duration::from_secs(1), "{took:?}");
1128        // ... and turns up 600 ms after frame 4 began waiting: dropped, but remembered.
1129        tokio::time::sleep(Duration::from_millis(600).saturating_sub(took)).await;
1130        sink.unbounded_send(3)?;
1131        assert!(
1132            tokio::time::timeout(Duration::from_millis(50), seq.next())
1133                .await
1134                .is_err(),
1135            "a late frame is not emitted"
1136        );
1137
1138        let took = time_to_abandon(&mut sink, &mut seq, 5, 6).await?;
1139        assert!(took >= Duration::from_millis(1150), "{took:?}");
1140        assert!(took < Duration::from_secs(3), "{took:?}");
1141        Ok(())
1142    }
1143}