Skip to main content

rs_singleflight/
lib.rs

1#![doc = include_str!("../README.md")]
2
3use std::{
4    borrow::Borrow,
5    collections::HashMap,
6    fmt,
7    future::Future,
8    hash::Hash,
9    sync::{Arc, Weak},
10    time::{Duration, Instant},
11};
12
13use parking_lot::{Mutex, RwLock};
14use tokio::sync::Notify;
15
16/// A result whose value and error can be shared without implementing [`Clone`].
17pub type SharedResult<V, E> = Result<Arc<V>, Arc<E>>;
18
19/// Controls what a waiting caller does when the leader future is dropped.
20///
21/// A leader can be dropped because its task was cancelled or because it
22/// panicked while polling the operation.
23#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
24pub enum LeaderDropPolicy {
25    /// Re-acquire the key and execute this caller's operation if it becomes the
26    /// next leader.
27    #[default]
28    Retry,
29    /// Return [`CallError::LeaderDropped`] without executing this caller's
30    /// operation.
31    ReturnError,
32}
33
34/// Error returned by policy-aware calls.
35#[derive(Debug, Clone, PartialEq, Eq)]
36pub enum CallError<E> {
37    /// The operation completed with an error.
38    Operation(E),
39    /// The leader future was dropped before publishing a result.
40    LeaderDropped,
41}
42
43impl<E> CallError<E> {
44    /// Returns whether the leader was dropped before publishing a result.
45    #[must_use]
46    pub const fn is_leader_dropped(&self) -> bool {
47        matches!(self, Self::LeaderDropped)
48    }
49
50    /// Returns the operation error, if the operation completed with one.
51    #[must_use]
52    pub const fn operation_error(&self) -> Option<&E> {
53        match self {
54            Self::Operation(error) => Some(error),
55            Self::LeaderDropped => None,
56        }
57    }
58}
59
60impl<E: fmt::Display> fmt::Display for CallError<E> {
61    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
62        match self {
63            Self::Operation(error) => error.fmt(f),
64            Self::LeaderDropped => f.write_str("singleflight leader was dropped"),
65        }
66    }
67}
68
69impl<E> std::error::Error for CallError<E>
70where
71    E: std::error::Error + 'static,
72{
73    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
74        match self {
75            Self::Operation(error) => Some(error),
76            Self::LeaderDropped => None,
77        }
78    }
79}
80
81enum FlightState<V, E> {
82    Running,
83    Complete(SharedResult<V, E>),
84    Aborted,
85}
86
87struct Flight<V, E> {
88    state: Mutex<FlightState<V, E>>,
89    changed: Notify,
90}
91
92type FlightMap<K, V, E> = HashMap<K, Weak<Flight<V, E>>>;
93type Flights<K, V, E> = Arc<Mutex<FlightMap<K, V, E>>>;
94
95impl<V, E> Flight<V, E> {
96    fn new() -> Self {
97        Self {
98            state: Mutex::new(FlightState::Running),
99            changed: Notify::new(),
100        }
101    }
102
103    async fn wait(&self) -> Option<SharedResult<V, E>> {
104        loop {
105            // Register before reading the state so a publication between the
106            // state check and await cannot be lost.
107            let changed = self.changed.notified();
108            tokio::pin!(changed);
109            changed.as_mut().enable();
110
111            {
112                let state = self.state.lock();
113                match &*state {
114                    FlightState::Running => {}
115                    FlightState::Complete(result) => return Some(result.clone()),
116                    FlightState::Aborted => return None,
117                }
118            }
119
120            changed.await;
121        }
122    }
123
124    fn publish(&self, result: SharedResult<V, E>) {
125        let mut state = self.state.lock();
126        debug_assert!(matches!(*state, FlightState::Running));
127        *state = FlightState::Complete(result);
128    }
129
130    fn abort(&self) -> bool {
131        let mut state = self.state.lock();
132        if matches!(*state, FlightState::Running) {
133            *state = FlightState::Aborted;
134            true
135        } else {
136            false
137        }
138    }
139
140    fn wake_waiters(&self) {
141        self.changed.notify_waiters();
142    }
143}
144
145/// Coalesces concurrent asynchronous operations by key.
146///
147/// The registry stores weak references, so dropping or aborting the caller
148/// executing an operation cannot leave a permanently live entry behind.
149/// Internal locks are synchronous and are never held across an `.await`.
150pub struct Group<K, V, E> {
151    flights: Flights<K, V, E>,
152}
153
154impl<K, V, E> Group<K, V, E> {
155    /// Creates an empty group.
156    #[must_use]
157    pub fn new() -> Self {
158        Self {
159            flights: Arc::new(Mutex::new(HashMap::new())),
160        }
161    }
162}
163
164impl<K, V, E> Clone for Group<K, V, E> {
165    fn clone(&self) -> Self {
166        Self {
167            flights: Arc::clone(&self.flights),
168        }
169    }
170}
171
172impl<K, V, E> Group<K, V, E>
173where
174    K: Eq + Hash + Clone,
175{
176    /// Runs `operation` or waits for the operation already running for `key`.
177    ///
178    /// Values and errors are returned in an [`Arc`], so neither needs to
179    /// implement [`Clone`]. If the current leader is dropped, one waiting
180    /// caller retries and executes its own operation. Use
181    /// [`Group::do_call_shared_with_policy`] to opt out of that retry.
182    pub async fn do_call_shared<F, Fut>(&self, key: K, operation: F) -> SharedResult<V, E>
183    where
184        F: FnOnce() -> Fut,
185        Fut: Future<Output = Result<V, E>>,
186    {
187        match self
188            .do_call_shared_with_policy(key, LeaderDropPolicy::Retry, operation)
189            .await
190        {
191            Ok(value) => Ok(value),
192            Err(CallError::Operation(error)) => Err(error),
193            Err(CallError::LeaderDropped) => {
194                unreachable!("retry policy never returns a leader-drop error")
195            }
196        }
197    }
198
199    /// Runs or joins an operation using the requested leader-drop policy.
200    pub async fn do_call_shared_with_policy<F, Fut>(
201        &self,
202        key: K,
203        policy: LeaderDropPolicy,
204        operation: F,
205    ) -> Result<Arc<V>, CallError<Arc<E>>>
206    where
207        F: FnOnce() -> Fut,
208        Fut: Future<Output = Result<V, E>>,
209    {
210        self.coalesce_shared(key, policy, move || async move {
211            operation().await.map(Arc::new).map_err(Arc::new)
212        })
213        .await
214    }
215
216    async fn coalesce_shared<F, Fut>(
217        &self,
218        key: K,
219        policy: LeaderDropPolicy,
220        operation: F,
221    ) -> Result<Arc<V>, CallError<Arc<E>>>
222    where
223        F: FnOnce() -> Fut,
224        Fut: Future<Output = SharedResult<V, E>>,
225    {
226        let mut operation = Some(operation);
227
228        loop {
229            let (flight, is_leader) = self.acquire(&key);
230            if !is_leader {
231                if let Some(result) = flight.wait().await {
232                    return result.map_err(CallError::Operation);
233                }
234                self.remove_if_current(&key, &flight);
235                match policy {
236                    LeaderDropPolicy::Retry => continue,
237                    LeaderDropPolicy::ReturnError => return Err(CallError::LeaderDropped),
238                }
239            }
240
241            let guard = LeaderGuard::new(self, &key, flight);
242            let operation = operation
243                .take()
244                .expect("singleflight operation can only be executed once");
245            let result = operation().await;
246            return guard.complete(result).map_err(CallError::Operation);
247        }
248    }
249
250    /// Runs `operation` or waits for the operation already running for `key`.
251    ///
252    /// Prefer [`Group::do_call_shared`] when cloning a large value is
253    /// undesirable or the value/error is not [`Clone`].
254    pub async fn do_call<F, Fut>(&self, key: K, operation: F) -> Result<V, E>
255    where
256        V: Clone,
257        E: Clone,
258        F: FnOnce() -> Fut,
259        Fut: Future<Output = Result<V, E>>,
260    {
261        let result = self.do_call_shared(key, operation).await;
262        match result {
263            Ok(value) => Ok(value.as_ref().clone()),
264            Err(error) => Err(error.as_ref().clone()),
265        }
266    }
267
268    /// Runs or joins an operation using the requested leader-drop policy.
269    pub async fn do_call_with_policy<F, Fut>(
270        &self,
271        key: K,
272        policy: LeaderDropPolicy,
273        operation: F,
274    ) -> Result<V, CallError<E>>
275    where
276        V: Clone,
277        E: Clone,
278        F: FnOnce() -> Fut,
279        Fut: Future<Output = Result<V, E>>,
280    {
281        match self
282            .do_call_shared_with_policy(key, policy, operation)
283            .await
284        {
285            Ok(value) => Ok(value.as_ref().clone()),
286            Err(CallError::Operation(error)) => Err(CallError::Operation(error.as_ref().clone())),
287            Err(CallError::LeaderDropped) => Err(CallError::LeaderDropped),
288        }
289    }
290
291    /// Detaches the current flight for `key`.
292    ///
293    /// Existing callers keep waiting on the detached flight, while subsequent
294    /// callers create a new flight. Returns whether a live flight was detached.
295    pub fn forget<Q>(&self, key: &Q) -> bool
296    where
297        K: Borrow<Q>,
298        Q: Eq + Hash + ?Sized,
299    {
300        self.flights
301            .lock()
302            .remove(key)
303            .and_then(|flight| flight.upgrade())
304            .is_some()
305    }
306
307    /// Returns the number of currently registered flights.
308    #[must_use]
309    pub fn in_flight(&self) -> usize {
310        self.flights
311            .lock()
312            .values()
313            .filter(|flight| flight.strong_count() > 0)
314            .count()
315    }
316
317    fn acquire(&self, key: &K) -> (Arc<Flight<V, E>>, bool) {
318        let mut flights = self.flights.lock();
319
320        if let Some(flight) = flights.get(key).and_then(Weak::upgrade) {
321            return (flight, false);
322        }
323
324        let flight = Arc::new(Flight::new());
325        flights.insert(key.clone(), Arc::downgrade(&flight));
326        (flight, true)
327    }
328
329    fn remove_if_current(&self, key: &K, flight: &Arc<Flight<V, E>>) {
330        let mut flights = self.flights.lock();
331        let is_current = flights
332            .get(key)
333            .is_some_and(|current| std::ptr::eq(current.as_ptr(), Arc::as_ptr(flight)));
334
335        if is_current {
336            flights.remove(key);
337        }
338    }
339
340    #[cfg(test)]
341    fn in_flight_len(&self) -> usize {
342        self.in_flight()
343    }
344}
345
346impl<K, V, E> Default for Group<K, V, E> {
347    fn default() -> Self {
348        Self::new()
349    }
350}
351
352struct LeaderGuard<'a, K, V, E>
353where
354    K: Eq + Hash + Clone,
355{
356    group: &'a Group<K, V, E>,
357    key: &'a K,
358    flight: Arc<Flight<V, E>>,
359    armed: bool,
360}
361
362impl<'a, K, V, E> LeaderGuard<'a, K, V, E>
363where
364    K: Eq + Hash + Clone,
365{
366    fn new(group: &'a Group<K, V, E>, key: &'a K, flight: Arc<Flight<V, E>>) -> Self {
367        Self {
368            group,
369            key,
370            flight,
371            armed: true,
372        }
373    }
374
375    fn complete(mut self, result: SharedResult<V, E>) -> SharedResult<V, E> {
376        self.flight.publish(result.clone());
377        self.group.remove_if_current(self.key, &self.flight);
378        self.flight.wake_waiters();
379        self.armed = false;
380        result
381    }
382}
383
384impl<K, V, E> Drop for LeaderGuard<'_, K, V, E>
385where
386    K: Eq + Hash + Clone,
387{
388    fn drop(&mut self) {
389        if self.armed && self.flight.abort() {
390            self.group.remove_if_current(self.key, &self.flight);
391            self.flight.wake_waiters();
392        }
393    }
394}
395
396struct CacheEntry<V> {
397    inserted_at: Instant,
398    value: Arc<V>,
399}
400
401struct CacheSlot<V> {
402    revision: u64,
403    entry: Option<CacheEntry<V>>,
404}
405
406struct CacheState<K, V> {
407    clear_revision: u64,
408    slots: HashMap<K, CacheSlot<V>>,
409}
410
411impl<K, V> CacheState<K, V> {
412    fn new() -> Self {
413        Self {
414            clear_revision: 0,
415            slots: HashMap::new(),
416        }
417    }
418}
419
420#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
421struct CacheVersion {
422    clear_revision: u64,
423    key_revision: u64,
424}
425
426#[derive(Clone, PartialEq, Eq, Hash)]
427struct CacheFlightKey<K> {
428    key: K,
429    version: CacheVersion,
430}
431
432fn next_revision(revision: u64) -> u64 {
433    let revision = revision.wrapping_add(1);
434    if revision == 0 { 1 } else { revision }
435}
436
437struct CacheAttempt<'a, K, V>
438where
439    K: Eq + Hash + Clone,
440{
441    cache: &'a RwLock<CacheState<K, V>>,
442    key: &'a K,
443    version: CacheVersion,
444}
445
446impl<'a, K, V> CacheAttempt<'a, K, V>
447where
448    K: Eq + Hash + Clone,
449{
450    fn new(cache: &'a RwLock<CacheState<K, V>>, key: &'a K, version: CacheVersion) -> Self {
451        Self {
452            cache,
453            key,
454            version,
455        }
456    }
457
458    fn cache(self, value: Arc<V>) {
459        let mut cache = self.cache.write();
460        if cache.clear_revision == self.version.clear_revision {
461            match cache.slots.get_mut(self.key) {
462                Some(slot) if slot.revision == self.version.key_revision => {
463                    slot.entry = Some(CacheEntry {
464                        inserted_at: Instant::now(),
465                        value,
466                    });
467                }
468                None if self.version.key_revision == 0 => {
469                    cache.slots.insert(
470                        self.key.clone(),
471                        CacheSlot {
472                            revision: 0,
473                            entry: Some(CacheEntry {
474                                inserted_at: Instant::now(),
475                                value,
476                            }),
477                        },
478                    );
479                }
480                Some(_) | None => {}
481            }
482        }
483    }
484}
485
486/// A [`Group`] layered with a success-only, in-memory TTL cache.
487///
488/// Cache hits use a read lock, allowing unrelated keys to be read
489/// concurrently. Failed operations are not cached. Call
490/// [`CachedGroup::purge_expired`] periodically if the key space is unbounded.
491pub struct CachedGroup<K, V, E> {
492    flight: Group<CacheFlightKey<K>, V, E>,
493    cache: Arc<RwLock<CacheState<K, V>>>,
494    ttl: Duration,
495}
496
497impl<K, V, E> CachedGroup<K, V, E> {
498    /// Creates an empty cached group.
499    #[must_use]
500    pub fn new(ttl: Duration) -> Self {
501        Self {
502            flight: Group::new(),
503            cache: Arc::new(RwLock::new(CacheState::new())),
504            ttl,
505        }
506    }
507
508    /// Returns the configured time to live.
509    #[must_use]
510    pub const fn ttl(&self) -> Duration {
511        self.ttl
512    }
513}
514
515impl<K, V, E> Clone for CachedGroup<K, V, E> {
516    fn clone(&self) -> Self {
517        Self {
518            flight: self.flight.clone(),
519            cache: Arc::clone(&self.cache),
520            ttl: self.ttl,
521        }
522    }
523}
524
525impl<K, V, E> CachedGroup<K, V, E>
526where
527    K: Eq + Hash + Clone,
528{
529    /// Returns a shared fresh value or coalesces a call to `operation`.
530    ///
531    /// The cache is checked again by the winning caller, and a successful
532    /// result is cached before waiting callers are released. This closes the
533    /// miss window between flight completion and cache population.
534    ///
535    /// Invalidating the key while the operation is running prevents that
536    /// operation from repopulating the cache. Calls started after invalidation
537    /// use a new flight generation and never join the invalidated flight.
538    pub async fn get_shared<F, Fut>(&self, key: K, operation: F) -> Result<Arc<V>, Arc<E>>
539    where
540        F: FnOnce() -> Fut,
541        Fut: Future<Output = Result<V, E>>,
542    {
543        match self
544            .get_shared_with_policy(key, LeaderDropPolicy::Retry, operation)
545            .await
546        {
547            Ok(value) => Ok(value),
548            Err(CallError::Operation(error)) => Err(error),
549            Err(CallError::LeaderDropped) => {
550                unreachable!("retry policy never returns a leader-drop error")
551            }
552        }
553    }
554
555    /// Returns a cached value or coalesces an operation using the requested
556    /// leader-drop policy.
557    pub async fn get_shared_with_policy<F, Fut>(
558        &self,
559        key: K,
560        policy: LeaderDropPolicy,
561        operation: F,
562    ) -> Result<Arc<V>, CallError<Arc<E>>>
563    where
564        F: FnOnce() -> Fut,
565        Fut: Future<Output = Result<V, E>>,
566    {
567        let version = {
568            let cache = self.cache.read();
569            if let Some(value) = Self::fresh_value(&cache, &key, self.ttl) {
570                return Ok(value);
571            }
572            CacheVersion {
573                clear_revision: cache.clear_revision,
574                key_revision: cache.slots.get(&key).map_or(0, |slot| slot.revision),
575            }
576        };
577
578        let cache_key = key.clone();
579        let flight_key = CacheFlightKey { key, version };
580        self.flight
581            .coalesce_shared(flight_key, policy, move || async move {
582                if let Some(value) = self.cached(&cache_key) {
583                    return Ok(value);
584                }
585
586                let cache_attempt = CacheAttempt::new(&self.cache, &cache_key, version);
587                match operation().await {
588                    Ok(value) => {
589                        let value = Arc::new(value);
590                        cache_attempt.cache(Arc::clone(&value));
591                        Ok(value)
592                    }
593                    Err(error) => Err(Arc::new(error)),
594                }
595            })
596            .await
597    }
598
599    /// Returns a fresh cached value or coalesces a call to `operation`.
600    ///
601    /// Prefer [`CachedGroup::get_shared`] for large or non-[`Clone`] results.
602    pub async fn get<F, Fut>(&self, key: K, operation: F) -> Result<V, E>
603    where
604        V: Clone,
605        E: Clone,
606        F: FnOnce() -> Fut,
607        Fut: Future<Output = Result<V, E>>,
608    {
609        match self.get_shared(key, operation).await {
610            Ok(value) => Ok(value.as_ref().clone()),
611            Err(error) => Err(error.as_ref().clone()),
612        }
613    }
614
615    /// Returns a cached value or coalesces an operation using the requested
616    /// leader-drop policy.
617    pub async fn get_with_policy<F, Fut>(
618        &self,
619        key: K,
620        policy: LeaderDropPolicy,
621        operation: F,
622    ) -> Result<V, CallError<E>>
623    where
624        V: Clone,
625        E: Clone,
626        F: FnOnce() -> Fut,
627        Fut: Future<Output = Result<V, E>>,
628    {
629        match self.get_shared_with_policy(key, policy, operation).await {
630            Ok(value) => Ok(value.as_ref().clone()),
631            Err(CallError::Operation(error)) => Err(CallError::Operation(error.as_ref().clone())),
632            Err(CallError::LeaderDropped) => Err(CallError::LeaderDropped),
633        }
634    }
635
636    /// Invalidates `key` and prevents an in-flight operation from caching its
637    /// result.
638    ///
639    /// Returns whether a cached value was present. Callers already joined to
640    /// the current flight still receive that flight's result; the next flight
641    /// executes the new operation.
642    pub fn invalidate<Q>(&self, key: &Q) -> bool
643    where
644        K: Borrow<Q>,
645        Q: Eq + Hash + ToOwned<Owned = K> + ?Sized,
646    {
647        let mut cache = self.cache.write();
648        if let Some(slot) = cache.slots.get_mut(key) {
649            slot.revision = next_revision(slot.revision);
650            slot.entry.take().is_some()
651        } else {
652            cache.slots.insert(
653                key.to_owned(),
654                CacheSlot {
655                    revision: 1,
656                    entry: None,
657                },
658            );
659            false
660        }
661    }
662
663    /// Removes all cached values and prevents currently in-flight operations
664    /// from repopulating the cache.
665    pub fn clear(&self) {
666        let mut cache = self.cache.write();
667        cache.clear_revision = next_revision(cache.clear_revision);
668        cache.slots.clear();
669    }
670
671    /// Removes expired cached values and returns the number removed.
672    ///
673    /// Generation metadata for explicitly invalidated keys is retained until
674    /// [`CachedGroup::clear`] so an old flight can never become current again.
675    pub fn purge_expired(&self) -> usize {
676        let mut cache = self.cache.write();
677        let mut expired = 0;
678        cache.slots.retain(|_, slot| {
679            if slot
680                .entry
681                .as_ref()
682                .is_some_and(|entry| entry.inserted_at.elapsed() >= self.ttl)
683            {
684                slot.entry = None;
685                expired += 1;
686            }
687            slot.entry.is_some() || slot.revision != 0
688        });
689        expired
690    }
691
692    /// Returns the number of currently registered flight generations.
693    #[must_use]
694    pub fn in_flight(&self) -> usize {
695        self.flight.in_flight()
696    }
697
698    fn cached(&self, key: &K) -> Option<Arc<V>> {
699        let cache = self.cache.read();
700        Self::fresh_value(&cache, key, self.ttl)
701    }
702
703    fn fresh_value(cache: &CacheState<K, V>, key: &K, ttl: Duration) -> Option<Arc<V>> {
704        cache
705            .slots
706            .get(key)
707            .and_then(|slot| slot.entry.as_ref())
708            .filter(|entry| entry.inserted_at.elapsed() < ttl)
709            .map(|entry| Arc::clone(&entry.value))
710    }
711}
712
713#[cfg(test)]
714mod tests {
715    use super::*;
716    use std::{
717        convert::Infallible,
718        future::pending,
719        sync::atomic::{AtomicUsize, Ordering},
720    };
721    use tokio::{
722        sync::{Barrier, Notify},
723        task::JoinSet,
724        time::{sleep, timeout},
725    };
726
727    #[tokio::test(flavor = "multi_thread", worker_threads = 4)]
728    async fn coalesces_concurrent_calls_for_the_same_key() {
729        const CALLERS: usize = 64;
730
731        let group = Arc::new(Group::<&str, usize, Infallible>::new());
732        let barrier = Arc::new(Barrier::new(CALLERS));
733        let executions = Arc::new(AtomicUsize::new(0));
734        let mut calls = JoinSet::new();
735
736        for _ in 0..CALLERS {
737            let group = Arc::clone(&group);
738            let barrier = Arc::clone(&barrier);
739            let executions = Arc::clone(&executions);
740            calls.spawn(async move {
741                barrier.wait().await;
742                group
743                    .do_call("channel", || async move {
744                        executions.fetch_add(1, Ordering::SeqCst);
745                        sleep(Duration::from_millis(25)).await;
746                        Ok(42)
747                    })
748                    .await
749            });
750        }
751
752        while let Some(result) = calls.join_next().await {
753            assert_eq!(result.unwrap(), Ok(42));
754        }
755        assert_eq!(executions.load(Ordering::SeqCst), 1);
756        assert_eq!(group.in_flight_len(), 0);
757    }
758
759    #[tokio::test]
760    async fn operations_for_different_keys_are_independent() {
761        let group = Arc::new(Group::<&str, usize, Infallible>::new());
762        let first_started = Arc::new(Notify::new());
763        let release_first = Arc::new(Notify::new());
764
765        let first = {
766            let group = Arc::clone(&group);
767            let first_started = Arc::clone(&first_started);
768            let release_first = Arc::clone(&release_first);
769            tokio::spawn(async move {
770                group
771                    .do_call("first", || async move {
772                        first_started.notify_one();
773                        release_first.notified().await;
774                        Ok(1)
775                    })
776                    .await
777            })
778        };
779
780        first_started.notified().await;
781        let second = timeout(
782            Duration::from_millis(100),
783            group.do_call("second", || async { Ok(2) }),
784        )
785        .await
786        .unwrap();
787        assert_eq!(second, Ok(2));
788
789        release_first.notify_one();
790        assert_eq!(first.await.unwrap(), Ok(1));
791    }
792
793    #[test]
794    fn clones_share_the_registry_and_forget_accepts_a_borrowed_key() {
795        let group = Group::<String, usize, Infallible>::new();
796        let cloned = group.clone();
797        let key = "key".to_owned();
798        let (first, is_leader) = group.acquire(&key);
799        assert!(is_leader);
800        assert_eq!(cloned.in_flight(), 1);
801
802        assert!(cloned.forget("key"));
803        assert_eq!(group.in_flight(), 0);
804
805        let (second, is_leader) = cloned.acquire(&key);
806        assert!(is_leader);
807        assert!(!Arc::ptr_eq(&first, &second));
808    }
809
810    #[tokio::test]
811    async fn shares_errors() {
812        let group = Arc::new(Group::<&str, (), &'static str>::new());
813        let started = Arc::new(Barrier::new(2));
814
815        let leader = {
816            let group = Arc::clone(&group);
817            let started = Arc::clone(&started);
818            tokio::spawn(async move {
819                group
820                    .do_call("key", || async move {
821                        started.wait().await;
822                        sleep(Duration::from_millis(10)).await;
823                        Err("failed")
824                    })
825                    .await
826            })
827        };
828
829        started.wait().await;
830        let follower = group.do_call("key", || async { Ok(()) });
831        assert_eq!(follower.await, Err("failed"));
832        assert_eq!(leader.await.unwrap(), Err("failed"));
833    }
834
835    #[tokio::test]
836    async fn shared_api_supports_non_clone_results() {
837        #[derive(Debug, PartialEq)]
838        struct NonClone(usize);
839
840        let group = Arc::new(Group::<&str, NonClone, NonClone>::new());
841        let release = Arc::new(Notify::new());
842        let started = Arc::new(Notify::new());
843
844        let leader = {
845            let group = Arc::clone(&group);
846            let release = Arc::clone(&release);
847            let started = Arc::clone(&started);
848            tokio::spawn(async move {
849                group
850                    .do_call_shared("key", || async move {
851                        started.notify_one();
852                        release.notified().await;
853                        Ok(NonClone(7))
854                    })
855                    .await
856            })
857        };
858
859        started.notified().await;
860        let follower = {
861            let group = Arc::clone(&group);
862            tokio::spawn(async move {
863                group
864                    .do_call_shared("key", || async { Err(NonClone(9)) })
865                    .await
866            })
867        };
868        tokio::task::yield_now().await;
869        release.notify_one();
870
871        let leader_value = leader.await.unwrap().unwrap();
872        let follower_value = follower.await.unwrap().unwrap();
873        assert!(Arc::ptr_eq(&leader_value, &follower_value));
874        assert_eq!(leader_value.as_ref(), &NonClone(7));
875    }
876
877    #[tokio::test]
878    async fn return_error_policy_does_not_retry_a_dropped_leader() {
879        let group = Group::<&str, usize, Infallible>::new();
880        let executions = AtomicUsize::new(0);
881        let (flight, is_leader) = group.acquire(&"key");
882        assert!(is_leader);
883
884        let follower = group.do_call_with_policy("key", LeaderDropPolicy::ReturnError, || async {
885            executions.fetch_add(1, Ordering::SeqCst);
886            Ok(7)
887        });
888        tokio::pin!(follower);
889        assert!(
890            timeout(Duration::from_millis(10), follower.as_mut())
891                .await
892                .is_err()
893        );
894
895        assert!(flight.abort());
896        group.remove_if_current(&"key", &flight);
897        flight.wake_waiters();
898
899        assert_eq!(follower.await, Err(CallError::LeaderDropped));
900        assert_eq!(executions.load(Ordering::SeqCst), 0);
901    }
902
903    #[tokio::test]
904    async fn recovers_when_the_leader_is_cancelled() {
905        let group = Arc::new(Group::<&str, usize, Infallible>::new());
906        let started = Arc::new(Notify::new());
907        let recovery_executions = Arc::new(AtomicUsize::new(0));
908
909        let leader = {
910            let group = Arc::clone(&group);
911            let started = Arc::clone(&started);
912            tokio::spawn(async move {
913                group
914                    .do_call("key", || async move {
915                        started.notify_one();
916                        pending::<Result<usize, Infallible>>().await
917                    })
918                    .await
919            })
920        };
921
922        started.notified().await;
923        let follower = {
924            let group = Arc::clone(&group);
925            let recovery_executions = Arc::clone(&recovery_executions);
926            tokio::spawn(async move {
927                group
928                    .do_call("key", || async move {
929                        recovery_executions.fetch_add(1, Ordering::SeqCst);
930                        Ok(11)
931                    })
932                    .await
933            })
934        };
935
936        tokio::task::yield_now().await;
937        leader.abort();
938        assert!(leader.await.unwrap_err().is_cancelled());
939        assert_eq!(
940            timeout(Duration::from_secs(1), follower)
941                .await
942                .unwrap()
943                .unwrap(),
944            Ok(11)
945        );
946        assert_eq!(recovery_executions.load(Ordering::SeqCst), 1);
947        assert_eq!(group.in_flight_len(), 0);
948    }
949
950    #[tokio::test]
951    async fn cancellation_without_waiters_removes_the_flight() {
952        let group = Arc::new(Group::<&str, usize, Infallible>::new());
953        let started = Arc::new(Notify::new());
954
955        let leader = {
956            let group = Arc::clone(&group);
957            let started = Arc::clone(&started);
958            tokio::spawn(async move {
959                group
960                    .do_call("key", || async move {
961                        started.notify_one();
962                        pending::<Result<usize, Infallible>>().await
963                    })
964                    .await
965            })
966        };
967
968        started.notified().await;
969        leader.abort();
970        assert!(leader.await.unwrap_err().is_cancelled());
971        assert_eq!(group.in_flight_len(), 0);
972        assert_eq!(group.do_call("key", || async { Ok(12) }).await, Ok(12));
973    }
974
975    #[tokio::test]
976    async fn recovers_when_the_leader_panics() {
977        let group = Arc::new(Group::<&str, usize, Infallible>::new());
978        let started = Arc::new(Notify::new());
979
980        let leader = {
981            let group = Arc::clone(&group);
982            let started = Arc::clone(&started);
983            tokio::spawn(async move {
984                group
985                    .do_call("key", || async move {
986                        started.notify_one();
987                        sleep(Duration::from_millis(10)).await;
988                        panic!("leader failed");
989                    })
990                    .await
991            })
992        };
993
994        started.notified().await;
995        let follower = {
996            let group = Arc::clone(&group);
997            tokio::spawn(async move { group.do_call("key", || async { Ok(13) }).await })
998        };
999
1000        assert!(leader.await.unwrap_err().is_panic());
1001        assert_eq!(follower.await.unwrap(), Ok(13));
1002        assert_eq!(group.in_flight_len(), 0);
1003    }
1004
1005    #[tokio::test]
1006    async fn cached_group_coalesces_and_honors_ttl() {
1007        let group = Arc::new(CachedGroup::<&str, usize, Infallible>::new(
1008            Duration::from_millis(250),
1009        ));
1010        let executions = Arc::new(AtomicUsize::new(0));
1011        let barrier = Arc::new(Barrier::new(8));
1012        let mut calls = JoinSet::new();
1013
1014        for _ in 0..8 {
1015            let group = Arc::clone(&group);
1016            let executions = Arc::clone(&executions);
1017            let barrier = Arc::clone(&barrier);
1018            calls.spawn(async move {
1019                barrier.wait().await;
1020                group
1021                    .get("key", || async move {
1022                        executions.fetch_add(1, Ordering::SeqCst);
1023                        sleep(Duration::from_millis(5)).await;
1024                        Ok(17)
1025                    })
1026                    .await
1027            });
1028        }
1029
1030        while let Some(result) = calls.join_next().await {
1031            assert_eq!(result.unwrap(), Ok(17));
1032        }
1033        assert_eq!(executions.load(Ordering::SeqCst), 1);
1034
1035        assert_eq!(group.get("key", || async { Ok(99) }).await, Ok(17));
1036        assert_eq!(executions.load(Ordering::SeqCst), 1);
1037
1038        sleep(Duration::from_millis(275)).await;
1039        assert_eq!(group.purge_expired(), 1);
1040        let executions_for_refresh = Arc::clone(&executions);
1041        assert_eq!(
1042            group
1043                .get("key", || async move {
1044                    executions_for_refresh.fetch_add(1, Ordering::SeqCst);
1045                    Ok(23)
1046                })
1047                .await,
1048            Ok(23)
1049        );
1050        assert_eq!(executions.load(Ordering::SeqCst), 2);
1051    }
1052
1053    #[tokio::test]
1054    async fn cached_shared_api_avoids_cloning_values() {
1055        #[derive(Debug, PartialEq)]
1056        struct NonClone(usize);
1057
1058        let group = CachedGroup::<&str, NonClone, NonClone>::new(Duration::from_secs(60));
1059        let fetched: SharedResult<NonClone, NonClone> =
1060            group.get_shared("key", || async { Ok(NonClone(31)) }).await;
1061        let fetched = fetched.unwrap();
1062        let cached = group
1063            .get_shared("key", || async { Err(NonClone(32)) })
1064            .await
1065            .unwrap();
1066
1067        assert!(Arc::ptr_eq(&fetched, &cached));
1068        assert_eq!(fetched.as_ref(), &NonClone(31));
1069    }
1070
1071    #[tokio::test]
1072    async fn invalidation_wins_against_an_in_flight_result() {
1073        let group = Arc::new(CachedGroup::<&str, usize, Infallible>::new(
1074            Duration::from_secs(60),
1075        ));
1076        let started = Arc::new(Notify::new());
1077        let release = Arc::new(Notify::new());
1078
1079        let first = {
1080            let group = Arc::clone(&group);
1081            let started = Arc::clone(&started);
1082            let release = Arc::clone(&release);
1083            tokio::spawn(async move {
1084                group
1085                    .get("key", || async move {
1086                        started.notify_one();
1087                        release.notified().await;
1088                        Ok(37)
1089                    })
1090                    .await
1091            })
1092        };
1093
1094        started.notified().await;
1095        assert!(!group.invalidate(&"key"));
1096        assert_eq!(
1097            timeout(
1098                Duration::from_millis(100),
1099                group.get("key", || async { Ok(41) })
1100            )
1101            .await
1102            .unwrap(),
1103            Ok(41)
1104        );
1105
1106        release.notify_one();
1107        assert_eq!(first.await.unwrap(), Ok(37));
1108        assert_eq!(group.get("key", || async { Ok(43) }).await, Ok(41));
1109    }
1110
1111    #[tokio::test]
1112    async fn clear_wins_against_in_flight_results() {
1113        let group = Arc::new(CachedGroup::<&str, usize, Infallible>::new(
1114            Duration::from_secs(60),
1115        ));
1116        let started = Arc::new(Notify::new());
1117        let release = Arc::new(Notify::new());
1118
1119        let first = {
1120            let group = Arc::clone(&group);
1121            let started = Arc::clone(&started);
1122            let release = Arc::clone(&release);
1123            tokio::spawn(async move {
1124                group
1125                    .get("key", || async move {
1126                        started.notify_one();
1127                        release.notified().await;
1128                        Ok(47)
1129                    })
1130                    .await
1131            })
1132        };
1133
1134        started.notified().await;
1135        group.clear();
1136        assert_eq!(
1137            timeout(
1138                Duration::from_millis(100),
1139                group.get("key", || async { Ok(53) })
1140            )
1141            .await
1142            .unwrap(),
1143            Ok(53)
1144        );
1145
1146        release.notify_one();
1147        assert_eq!(first.await.unwrap(), Ok(47));
1148        assert_eq!(group.get("key", || async { Ok(59) }).await, Ok(53));
1149    }
1150
1151    #[tokio::test]
1152    async fn invalidate_accepts_a_borrowed_key() {
1153        let group = CachedGroup::<String, usize, Infallible>::new(Duration::from_secs(60));
1154        assert_eq!(
1155            group.get("key".to_owned(), || async { Ok(61) }).await,
1156            Ok(61)
1157        );
1158        assert!(group.invalidate("key"));
1159        assert_eq!(
1160            group.get("key".to_owned(), || async { Ok(67) }).await,
1161            Ok(67)
1162        );
1163    }
1164
1165    #[tokio::test]
1166    async fn cached_group_does_not_cache_errors() {
1167        let group = CachedGroup::<&str, usize, &'static str>::new(Duration::from_secs(60));
1168        assert_eq!(
1169            group.get("key", || async { Err("temporary") }).await,
1170            Err("temporary")
1171        );
1172        assert_eq!(group.get("key", || async { Ok(29) }).await, Ok(29));
1173    }
1174}