1use 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
20const MIN_GAP_WAIT: Duration = Duration::from_millis(1);
22
23#[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#[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 max_item_age: Option<Duration>,
102 max_frames_behind_gap: Option<usize>,
105 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 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 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 let stream_poll = this.inner.as_mut().poll_next(cx);
173
174 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 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 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 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 tracing::trace!("timer elapsed");
239 *this.state = State::BufferUpdated;
240 }
241 }
242 } else {
243 tracing::warn!("sequencer buffer is full");
245 *this.state = State::BufferUpdated;
246 }
247 }
248 State::BufferUpdated => {
249 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 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 } else if next.buffered_at.elapsed() >= max_wait
281 || this.buffer.len() == this.buffer.capacity()
282 || this.max_frames_behind_gap.is_some_and(|n| {
287 this.buffer.len() >= n
294 || 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 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 *this.state = State::Polling;
324 }
325 State::Done => {
326 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#[derive(Clone, Copy, Debug)]
360pub struct SequencerConfig {
361 pub max_wait: Duration,
363 pub capacity: usize,
365 pub max_item_age: Option<Duration>,
367 pub max_frames_behind_gap: Option<usize>,
378 pub adapt_to_reordering: bool,
387}
388
389pub trait SequencerExt: futures::Stream {
391 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 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 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 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 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 seq_sink.send(2u32).await?;
484
485 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 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 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 #[test_log::test(tokio::test)]
572 async fn sequencer_should_abandon_a_gap_once_enough_later_frames_are_waiting() -> anyhow::Result<()> {
573 let max_wait = Duration::from_secs(5);
576 let (mut seq_sink, seq_stream) = futures::channel::mpsc::unbounded();
577
578 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 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 drop(seq_sink);
610 Ok(())
611 }
612
613 #[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 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 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 #[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 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 #[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 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 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 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 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 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 #[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 #[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 #[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 #[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 let took = time_to_abandon(&mut sink, &mut seq, 3, 4).await?;
1127 assert!(took < Duration::from_secs(1), "{took:?}");
1128 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}