use futures_core::Stream;
use std::collections::VecDeque;
use std::pin::Pin;
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Waker};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Overflow {
KeepNewest,
KeepOldest,
}
pub const DEFAULT_CAPACITY: usize = 1024;
struct Shared<T> {
queue: VecDeque<T>,
capacity: usize,
overflow: Overflow,
lost: u64,
waker: Option<Waker>,
closed: bool,
finished: bool,
senders: usize,
}
pub struct Sender<T>(Arc<Mutex<Shared<T>>>);
pub struct Receiver<T>(Arc<Mutex<Shared<T>>>);
pub fn bounded<T>(capacity: usize, overflow: Overflow) -> (Sender<T>, Receiver<T>) {
let capacity = capacity.max(1);
let shared = Arc::new(Mutex::new(Shared {
queue: VecDeque::new(),
capacity,
overflow,
lost: 0,
waker: None,
closed: false,
finished: false,
senders: 1,
}));
(Sender(shared.clone()), Receiver(shared))
}
pub fn channel<T>() -> (Sender<T>, Receiver<T>) {
bounded(DEFAULT_CAPACITY, Overflow::KeepNewest)
}
impl<T> Sender<T> {
pub fn send(&self, value: T) -> Result<(), Closed> {
let waker = {
let mut shared = self.0.lock().unwrap();
if shared.closed || shared.finished {
return Err(Closed);
}
if shared.queue.len() >= shared.capacity {
shared.lost += 1;
match shared.overflow {
Overflow::KeepNewest => {
shared.queue.pop_front();
}
Overflow::KeepOldest => return Ok(()),
}
}
shared.queue.push_back(value);
shared.waker.take()
};
if let Some(waker) = waker {
waker.wake();
}
Ok(())
}
pub fn is_open(&self) -> bool {
let shared = self.0.lock().unwrap();
!shared.closed && !shared.finished
}
pub fn close(&self) {
let waker = {
let mut shared = self.0.lock().unwrap();
shared.finished = true;
shared.waker.take()
};
if let Some(waker) = waker {
waker.wake();
}
}
}
impl<T> Clone for Sender<T> {
fn clone(&self) -> Self {
self.0.lock().unwrap().senders += 1;
Self(self.0.clone())
}
}
impl<T> Drop for Sender<T> {
fn drop(&mut self) {
let waker = {
let mut shared = self.0.lock().unwrap();
shared.senders -= 1;
if shared.senders > 0 {
return;
}
shared.waker.take()
};
if let Some(waker) = waker {
waker.wake();
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Closed;
impl<T> Receiver<T> {
pub fn lost(&self) -> u64 {
self.0.lock().unwrap().lost
}
pub fn try_recv(&mut self) -> Option<T> {
self.0.lock().unwrap().queue.pop_front()
}
pub fn depth(&self) -> usize {
self.0.lock().unwrap().queue.len()
}
}
impl<T> Stream for Receiver<T> {
type Item = T;
fn poll_next(self: Pin<&mut Self>, context: &mut Context<'_>) -> Poll<Option<T>> {
let mut shared = self.0.lock().unwrap();
if let Some(value) = shared.queue.pop_front() {
return Poll::Ready(Some(value));
}
if shared.senders == 0 || shared.finished {
return Poll::Ready(None);
}
shared.waker = Some(context.waker().clone());
Poll::Pending
}
}
impl<T> Drop for Receiver<T> {
fn drop(&mut self) {
let mut shared = self.0.lock().unwrap();
shared.closed = true;
shared.queue.clear();
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::task::{RawWaker, RawWakerVTable};
fn noop_waker() -> Waker {
fn clone(_: *const ()) -> RawWaker {
RawWaker::new(std::ptr::null(), &VTABLE)
}
fn noop(_: *const ()) {}
static VTABLE: RawWakerVTable = RawWakerVTable::new(clone, noop, noop, noop);
unsafe { Waker::from_raw(RawWaker::new(std::ptr::null(), &VTABLE)) }
}
fn drain<T>(rx: &mut Receiver<T>) -> Vec<T> {
let waker = noop_waker();
let mut context = Context::from_waker(&waker);
let mut out = Vec::new();
while let Poll::Ready(Some(v)) = Pin::new(&mut *rx).poll_next(&mut context) {
out.push(v);
}
out
}
#[test]
fn values_come_out_in_the_order_they_went_in() {
let (tx, mut rx) = channel();
for i in 0..5 {
tx.send(i).unwrap();
}
assert_eq!(drain(&mut rx), vec![0, 1, 2, 3, 4]);
assert_eq!(rx.lost(), 0);
}
#[test]
fn keeping_the_newest_drops_from_the_front() {
let (tx, mut rx) = bounded(3, Overflow::KeepNewest);
for i in 0..5 {
tx.send(i).expect("a full queue is not an error");
}
assert_eq!(drain(&mut rx), vec![2, 3, 4], "the newest three survive");
assert_eq!(rx.lost(), 2, "and the two it dropped are counted");
}
#[test]
fn keeping_the_oldest_drops_what_just_arrived() {
let (tx, mut rx) = bounded(3, Overflow::KeepOldest);
for i in 0..5 {
tx.send(i).unwrap();
}
assert_eq!(drain(&mut rx), vec![0, 1, 2], "the first three survive");
assert_eq!(rx.lost(), 2);
}
#[test]
fn a_gap_is_measurable_between_two_reads() {
let (tx, mut rx) = bounded(2, Overflow::KeepNewest);
tx.send(1).unwrap();
let waker = noop_waker();
let mut context = Context::from_waker(&waker);
let before = rx.lost();
assert_eq!(
Pin::new(&mut rx).poll_next(&mut context),
Poll::Ready(Some(1))
);
for i in 2..9 {
tx.send(i).unwrap();
}
let next = match Pin::new(&mut rx).poll_next(&mut context) {
Poll::Ready(Some(v)) => v,
other => panic!("expected a value, got {other:?}"),
};
let gap = rx.lost() - before;
assert_eq!(gap, 5, "five values went missing");
assert_eq!(next, 7, "and the stream resumes after them");
}
#[test]
fn overflow_is_not_a_send_failure() {
let (tx, _rx) = bounded(1, Overflow::KeepNewest);
assert!(tx.send(1).is_ok());
assert!(tx.send(2).is_ok());
assert!(tx.send(3).is_ok());
}
#[test]
fn a_dropped_receiver_closes_the_sender() {
let (tx, rx) = channel();
assert!(tx.is_open());
assert!(tx.send(1).is_ok());
drop(rx);
assert!(!tx.is_open());
assert_eq!(tx.send(2), Err(Closed));
}
#[test]
fn a_dropped_receiver_releases_what_was_queued() {
let held = Arc::new(());
let (tx, rx) = channel();
for _ in 0..10 {
tx.send(held.clone()).unwrap();
}
assert_eq!(Arc::strong_count(&held), 11);
drop(rx);
assert_eq!(Arc::strong_count(&held), 1, "the queue was released");
}
#[test]
fn a_waiting_consumer_is_woken() {
let (tx, mut rx) = channel::<u32>();
let woken = Arc::new(Mutex::new(false));
struct Flag(Arc<Mutex<bool>>);
impl std::task::Wake for Flag {
fn wake(self: Arc<Self>) {
*self.0.lock().unwrap() = true;
}
}
let waker: Waker = Arc::new(Flag(woken.clone())).into();
let mut context = Context::from_waker(&waker);
assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
assert!(!*woken.lock().unwrap());
tx.send(7).unwrap();
assert!(*woken.lock().unwrap(), "sending should wake the consumer");
assert_eq!(
Pin::new(&mut rx).poll_next(&mut context),
Poll::Ready(Some(7))
);
}
#[test]
fn silence_is_pending_but_a_dropped_sender_is_the_end() {
let (tx, mut rx) = channel::<u32>();
let waker = noop_waker();
let mut context = Context::from_waker(&waker);
assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
tx.send(7).unwrap();
drop(tx);
assert_eq!(
Pin::new(&mut rx).poll_next(&mut context),
Poll::Ready(Some(7)),
"a value sent before the sender went must not be lost"
);
assert_eq!(
Pin::new(&mut rx).poll_next(&mut context),
Poll::Ready(None),
"and then the stream is over"
);
}
#[test]
fn the_stream_ends_only_when_every_sender_is_gone() {
let (tx, mut rx) = channel::<u32>();
let second = tx.clone();
let waker = noop_waker();
let mut context = Context::from_waker(&waker);
drop(second);
assert_eq!(
Pin::new(&mut rx).poll_next(&mut context),
Poll::Pending,
"one sender remains, so the stream is merely quiet"
);
drop(tx);
assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Ready(None));
}
#[test]
fn closing_ends_the_stream_after_draining() {
let (tx, mut rx) = channel::<u32>();
let waker = noop_waker();
let mut context = Context::from_waker(&waker);
tx.send(1).unwrap();
tx.send(2).unwrap();
tx.close();
assert!(!tx.is_open(), "a closed sender reports itself closed");
assert_eq!(tx.send(3), Err(Closed), "and takes nothing further");
assert_eq!(
Pin::new(&mut rx).poll_next(&mut context),
Poll::Ready(Some(1)),
"what was queued before the close is still delivered"
);
assert_eq!(
Pin::new(&mut rx).poll_next(&mut context),
Poll::Ready(Some(2))
);
assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Ready(None));
}
#[test]
fn a_zero_capacity_still_carries_a_value() {
let (tx, mut rx) = bounded(0, Overflow::KeepNewest);
tx.send(9).unwrap();
assert_eq!(drain(&mut rx), vec![9]);
}
#[test]
fn an_empty_queue_is_pending_rather_than_finished() {
let (tx, mut rx) = channel::<u32>();
let waker = noop_waker();
let mut context = Context::from_waker(&waker);
assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
tx.send(1).unwrap();
assert_eq!(
Pin::new(&mut rx).poll_next(&mut context),
Poll::Ready(Some(1))
);
assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
}
#[test]
fn nothing_vanishes_unaccounted_under_concurrent_senders() {
const THREADS: usize = 8;
const EACH: usize = 500;
let (tx, mut rx) = bounded::<usize>(16, Overflow::KeepNewest);
let tx = Arc::new(tx);
let threads: Vec<_> = (0..THREADS)
.map(|_| {
let tx = tx.clone();
std::thread::spawn(move || {
for i in 0..EACH {
tx.send(i).unwrap();
}
})
})
.collect();
for t in threads {
t.join().expect("no sender should have panicked");
}
let received = drain(&mut rx).len() as u64;
assert_eq!(
received + rx.lost(),
(THREADS * EACH) as u64,
"every value is either delivered or counted"
);
}
#[test]
fn senders_clone_and_share_one_queue() {
struct NotClone(u32);
let (tx, mut rx) = bounded::<NotClone>(8, Overflow::KeepNewest);
let second = tx.clone();
tx.send(NotClone(1)).unwrap();
second.send(NotClone(2)).unwrap();
let got: Vec<u32> = drain(&mut rx).into_iter().map(|v| v.0).collect();
assert_eq!(got, vec![1, 2], "both feed the same queue, in order");
drop(second);
assert!(tx.is_open());
assert!(tx.send(NotClone(3)).is_ok());
}
#[test]
fn try_recv_drains_without_waiting() {
let (tx, mut rx) = channel();
assert_eq!(rx.try_recv(), None, "nothing queued yet");
tx.send(1).unwrap();
tx.send(2).unwrap();
assert_eq!(rx.try_recv(), Some(1));
assert_eq!(rx.try_recv(), Some(2));
assert_eq!(rx.try_recv(), None, "and it stops rather than blocking");
}
#[test]
fn depth_reports_what_is_waiting() {
let (tx, mut rx) = bounded(4, Overflow::KeepNewest);
assert_eq!(rx.depth(), 0);
tx.send(1).unwrap();
tx.send(2).unwrap();
assert_eq!(rx.depth(), 2);
drain(&mut rx);
assert_eq!(rx.depth(), 0);
}
#[test]
fn the_default_is_the_documented_one() {
assert_eq!(DEFAULT_CAPACITY, 1024);
let (tx, rx) = channel::<u8>();
for i in 0..(DEFAULT_CAPACITY + 10) {
tx.send(i as u8).unwrap();
}
assert_eq!(rx.depth(), DEFAULT_CAPACITY);
assert_eq!(rx.lost(), 10);
}
}