1use futures_core::Stream;
25use std::collections::VecDeque;
26use std::pin::Pin;
27use std::sync::{Arc, Mutex};
28use std::task::{Context, Poll, Waker};
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum Overflow {
33 KeepNewest,
39 KeepOldest,
45}
46
47pub const DEFAULT_CAPACITY: usize = 1024;
54
55struct Shared<T> {
56 queue: VecDeque<T>,
57 capacity: usize,
58 overflow: Overflow,
59 lost: u64,
63 waker: Option<Waker>,
64 closed: bool,
66 finished: bool,
72 senders: usize,
79}
80
81pub struct Sender<T>(Arc<Mutex<Shared<T>>>);
83
84pub struct Receiver<T>(Arc<Mutex<Shared<T>>>);
86
87pub fn bounded<T>(capacity: usize, overflow: Overflow) -> (Sender<T>, Receiver<T>) {
89 let capacity = capacity.max(1);
92 let shared = Arc::new(Mutex::new(Shared {
93 queue: VecDeque::new(),
94 capacity,
95 overflow,
96 lost: 0,
97 waker: None,
98 closed: false,
99 finished: false,
100 senders: 1,
101 }));
102 (Sender(shared.clone()), Receiver(shared))
103}
104
105pub fn channel<T>() -> (Sender<T>, Receiver<T>) {
107 bounded(DEFAULT_CAPACITY, Overflow::KeepNewest)
108}
109
110impl<T> Sender<T> {
111 pub fn send(&self, value: T) -> Result<(), Closed> {
119 let waker = {
120 let mut shared = self.0.lock().unwrap();
121 if shared.closed || shared.finished {
122 return Err(Closed);
123 }
124 if shared.queue.len() >= shared.capacity {
125 shared.lost += 1;
126 match shared.overflow {
127 Overflow::KeepNewest => {
128 shared.queue.pop_front();
129 }
130 Overflow::KeepOldest => return Ok(()),
131 }
132 }
133 shared.queue.push_back(value);
134 shared.waker.take()
135 };
136 if let Some(waker) = waker {
138 waker.wake();
139 }
140 Ok(())
141 }
142
143 pub fn is_open(&self) -> bool {
145 let shared = self.0.lock().unwrap();
146 !shared.closed && !shared.finished
147 }
148
149 pub fn close(&self) {
155 let waker = {
156 let mut shared = self.0.lock().unwrap();
157 shared.finished = true;
158 shared.waker.take()
159 };
160 if let Some(waker) = waker {
161 waker.wake();
162 }
163 }
164}
165
166impl<T> Clone for Sender<T> {
171 fn clone(&self) -> Self {
172 self.0.lock().unwrap().senders += 1;
173 Self(self.0.clone())
174 }
175}
176
177impl<T> Drop for Sender<T> {
178 fn drop(&mut self) {
179 let waker = {
180 let mut shared = self.0.lock().unwrap();
181 shared.senders -= 1;
182 if shared.senders > 0 {
183 return;
184 }
185 shared.waker.take()
188 };
189 if let Some(waker) = waker {
190 waker.wake();
191 }
192 }
193}
194
195#[derive(Debug, Clone, Copy, PartialEq, Eq)]
197pub struct Closed;
198
199impl<T> Receiver<T> {
200 pub fn lost(&self) -> u64 {
206 self.0.lock().unwrap().lost
207 }
208
209 pub fn try_recv(&mut self) -> Option<T> {
215 self.0.lock().unwrap().queue.pop_front()
216 }
217
218 pub fn depth(&self) -> usize {
224 self.0.lock().unwrap().queue.len()
225 }
226}
227
228impl<T> Stream for Receiver<T> {
229 type Item = T;
230
231 fn poll_next(self: Pin<&mut Self>, context: &mut Context<'_>) -> Poll<Option<T>> {
232 let mut shared = self.0.lock().unwrap();
233 if let Some(value) = shared.queue.pop_front() {
234 return Poll::Ready(Some(value));
235 }
236 if shared.senders == 0 || shared.finished {
239 return Poll::Ready(None);
240 }
241 shared.waker = Some(context.waker().clone());
244 Poll::Pending
245 }
246}
247
248impl<T> Drop for Receiver<T> {
249 fn drop(&mut self) {
250 let mut shared = self.0.lock().unwrap();
251 shared.closed = true;
252 shared.queue.clear();
254 }
255}
256
257#[cfg(test)]
258mod tests {
259 use super::*;
260 use std::task::{RawWaker, RawWakerVTable};
261
262 fn noop_waker() -> Waker {
263 fn clone(_: *const ()) -> RawWaker {
264 RawWaker::new(std::ptr::null(), &VTABLE)
265 }
266 fn noop(_: *const ()) {}
267 static VTABLE: RawWakerVTable = RawWakerVTable::new(clone, noop, noop, noop);
268 unsafe { Waker::from_raw(RawWaker::new(std::ptr::null(), &VTABLE)) }
269 }
270
271 fn drain<T>(rx: &mut Receiver<T>) -> Vec<T> {
272 let waker = noop_waker();
273 let mut context = Context::from_waker(&waker);
274 let mut out = Vec::new();
275 while let Poll::Ready(Some(v)) = Pin::new(&mut *rx).poll_next(&mut context) {
276 out.push(v);
277 }
278 out
279 }
280
281 #[test]
282 fn values_come_out_in_the_order_they_went_in() {
283 let (tx, mut rx) = channel();
284 for i in 0..5 {
285 tx.send(i).unwrap();
286 }
287 assert_eq!(drain(&mut rx), vec![0, 1, 2, 3, 4]);
288 assert_eq!(rx.lost(), 0);
289 }
290
291 #[test]
294 fn keeping_the_newest_drops_from_the_front() {
295 let (tx, mut rx) = bounded(3, Overflow::KeepNewest);
296 for i in 0..5 {
297 tx.send(i).expect("a full queue is not an error");
298 }
299 assert_eq!(drain(&mut rx), vec![2, 3, 4], "the newest three survive");
300 assert_eq!(rx.lost(), 2, "and the two it dropped are counted");
301 }
302
303 #[test]
307 fn keeping_the_oldest_drops_what_just_arrived() {
308 let (tx, mut rx) = bounded(3, Overflow::KeepOldest);
309 for i in 0..5 {
310 tx.send(i).unwrap();
311 }
312 assert_eq!(drain(&mut rx), vec![0, 1, 2], "the first three survive");
313 assert_eq!(rx.lost(), 2);
314 }
315
316 #[test]
320 fn a_gap_is_measurable_between_two_reads() {
321 let (tx, mut rx) = bounded(2, Overflow::KeepNewest);
322 tx.send(1).unwrap();
323
324 let waker = noop_waker();
325 let mut context = Context::from_waker(&waker);
326 let before = rx.lost();
327 assert_eq!(
328 Pin::new(&mut rx).poll_next(&mut context),
329 Poll::Ready(Some(1))
330 );
331
332 for i in 2..9 {
334 tx.send(i).unwrap();
335 }
336 let next = match Pin::new(&mut rx).poll_next(&mut context) {
337 Poll::Ready(Some(v)) => v,
338 other => panic!("expected a value, got {other:?}"),
339 };
340 let gap = rx.lost() - before;
341
342 assert_eq!(gap, 5, "five values went missing");
343 assert_eq!(next, 7, "and the stream resumes after them");
344 }
345
346 #[test]
350 fn overflow_is_not_a_send_failure() {
351 let (tx, _rx) = bounded(1, Overflow::KeepNewest);
352 assert!(tx.send(1).is_ok());
353 assert!(tx.send(2).is_ok());
354 assert!(tx.send(3).is_ok());
355 }
356
357 #[test]
360 fn a_dropped_receiver_closes_the_sender() {
361 let (tx, rx) = channel();
362 assert!(tx.is_open());
363 assert!(tx.send(1).is_ok());
364 drop(rx);
365 assert!(!tx.is_open());
366 assert_eq!(tx.send(2), Err(Closed));
367 }
368
369 #[test]
372 fn a_dropped_receiver_releases_what_was_queued() {
373 let held = Arc::new(());
374 let (tx, rx) = channel();
375 for _ in 0..10 {
376 tx.send(held.clone()).unwrap();
377 }
378 assert_eq!(Arc::strong_count(&held), 11);
379 drop(rx);
380 assert_eq!(Arc::strong_count(&held), 1, "the queue was released");
381 }
382
383 #[test]
385 fn a_waiting_consumer_is_woken() {
386 let (tx, mut rx) = channel::<u32>();
387 let woken = Arc::new(Mutex::new(false));
388
389 struct Flag(Arc<Mutex<bool>>);
390 impl std::task::Wake for Flag {
391 fn wake(self: Arc<Self>) {
392 *self.0.lock().unwrap() = true;
393 }
394 }
395 let waker: Waker = Arc::new(Flag(woken.clone())).into();
396 let mut context = Context::from_waker(&waker);
397
398 assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
399 assert!(!*woken.lock().unwrap());
400
401 tx.send(7).unwrap();
402 assert!(*woken.lock().unwrap(), "sending should wake the consumer");
403 assert_eq!(
404 Pin::new(&mut rx).poll_next(&mut context),
405 Poll::Ready(Some(7))
406 );
407 }
408
409 #[test]
416 fn silence_is_pending_but_a_dropped_sender_is_the_end() {
417 let (tx, mut rx) = channel::<u32>();
418 let waker = noop_waker();
419 let mut context = Context::from_waker(&waker);
420
421 assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
423
424 tx.send(7).unwrap();
425 drop(tx);
426
427 assert_eq!(
429 Pin::new(&mut rx).poll_next(&mut context),
430 Poll::Ready(Some(7)),
431 "a value sent before the sender went must not be lost"
432 );
433 assert_eq!(
434 Pin::new(&mut rx).poll_next(&mut context),
435 Poll::Ready(None),
436 "and then the stream is over"
437 );
438 }
439
440 #[test]
442 fn the_stream_ends_only_when_every_sender_is_gone() {
443 let (tx, mut rx) = channel::<u32>();
444 let second = tx.clone();
445 let waker = noop_waker();
446 let mut context = Context::from_waker(&waker);
447
448 drop(second);
449 assert_eq!(
450 Pin::new(&mut rx).poll_next(&mut context),
451 Poll::Pending,
452 "one sender remains, so the stream is merely quiet"
453 );
454
455 drop(tx);
456 assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Ready(None));
457 }
458
459 #[test]
462 fn closing_ends_the_stream_after_draining() {
463 let (tx, mut rx) = channel::<u32>();
464 let waker = noop_waker();
465 let mut context = Context::from_waker(&waker);
466
467 tx.send(1).unwrap();
468 tx.send(2).unwrap();
469 tx.close();
470
471 assert!(!tx.is_open(), "a closed sender reports itself closed");
472 assert_eq!(tx.send(3), Err(Closed), "and takes nothing further");
473
474 assert_eq!(
475 Pin::new(&mut rx).poll_next(&mut context),
476 Poll::Ready(Some(1)),
477 "what was queued before the close is still delivered"
478 );
479 assert_eq!(
480 Pin::new(&mut rx).poll_next(&mut context),
481 Poll::Ready(Some(2))
482 );
483 assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Ready(None));
484 }
485
486 #[test]
488 fn a_zero_capacity_still_carries_a_value() {
489 let (tx, mut rx) = bounded(0, Overflow::KeepNewest);
490 tx.send(9).unwrap();
491 assert_eq!(drain(&mut rx), vec![9]);
492 }
493
494 #[test]
497 fn an_empty_queue_is_pending_rather_than_finished() {
498 let (tx, mut rx) = channel::<u32>();
499 let waker = noop_waker();
500 let mut context = Context::from_waker(&waker);
501 assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
502 tx.send(1).unwrap();
503 assert_eq!(
504 Pin::new(&mut rx).poll_next(&mut context),
505 Poll::Ready(Some(1))
506 );
507 assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
508 }
509
510 #[test]
513 fn nothing_vanishes_unaccounted_under_concurrent_senders() {
514 const THREADS: usize = 8;
515 const EACH: usize = 500;
516
517 let (tx, mut rx) = bounded::<usize>(16, Overflow::KeepNewest);
518 let tx = Arc::new(tx);
519 let threads: Vec<_> = (0..THREADS)
520 .map(|_| {
521 let tx = tx.clone();
522 std::thread::spawn(move || {
523 for i in 0..EACH {
524 tx.send(i).unwrap();
525 }
526 })
527 })
528 .collect();
529 for t in threads {
530 t.join().expect("no sender should have panicked");
531 }
532
533 let received = drain(&mut rx).len() as u64;
534 assert_eq!(
535 received + rx.lost(),
536 (THREADS * EACH) as u64,
537 "every value is either delivered or counted"
538 );
539 }
540
541 #[test]
544 fn senders_clone_and_share_one_queue() {
545 struct NotClone(u32);
546
547 let (tx, mut rx) = bounded::<NotClone>(8, Overflow::KeepNewest);
548 let second = tx.clone();
549 tx.send(NotClone(1)).unwrap();
550 second.send(NotClone(2)).unwrap();
551
552 let got: Vec<u32> = drain(&mut rx).into_iter().map(|v| v.0).collect();
553 assert_eq!(got, vec![1, 2], "both feed the same queue, in order");
554
555 drop(second);
557 assert!(tx.is_open());
558 assert!(tx.send(NotClone(3)).is_ok());
559 }
560
561 #[test]
563 fn try_recv_drains_without_waiting() {
564 let (tx, mut rx) = channel();
565 assert_eq!(rx.try_recv(), None, "nothing queued yet");
566
567 tx.send(1).unwrap();
568 tx.send(2).unwrap();
569 assert_eq!(rx.try_recv(), Some(1));
570 assert_eq!(rx.try_recv(), Some(2));
571 assert_eq!(rx.try_recv(), None, "and it stops rather than blocking");
572 }
573
574 #[test]
575 fn depth_reports_what_is_waiting() {
576 let (tx, mut rx) = bounded(4, Overflow::KeepNewest);
577 assert_eq!(rx.depth(), 0);
578 tx.send(1).unwrap();
579 tx.send(2).unwrap();
580 assert_eq!(rx.depth(), 2);
581 drain(&mut rx);
582 assert_eq!(rx.depth(), 0);
583 }
584
585 #[test]
588 fn the_default_is_the_documented_one() {
589 assert_eq!(DEFAULT_CAPACITY, 1024);
590 let (tx, rx) = channel::<u8>();
591 for i in 0..(DEFAULT_CAPACITY + 10) {
592 tx.send(i as u8).unwrap();
593 }
594 assert_eq!(rx.depth(), DEFAULT_CAPACITY);
595 assert_eq!(rx.lost(), 10);
596 }
597}