Skip to main content

nexus_timer/
timeout_queue.rs

1//! Fixed-duration timeout queue — a sorted front-end over the wheel machinery.
2//!
3//! `TimeoutQueue<T, S>` schedules every timer with the **same** duration, fixed
4//! at construction. Because the duration is constant and the clock is monotone,
5//! deadlines are monotone in insertion order: appending each new entry at the
6//! tail of one intrusive DLL keeps the list sorted with no comparisons. Poll
7//! then walks from the head and stops at the first not-due entry — **O(fired)**,
8//! not O(population) as the wheel's per-entry scan is. `next_deadline()` is the
9//! head's deadline: exact, O(1), no cache.
10//!
11//! # When to use this instead of [`TimerWheel`](crate::TimerWheel)
12//!
13//! A wheel earns its keep when deadlines are *arbitrary* — timers interleaved
14//! among earlier and later expirations. But a large class of callers schedule
15//! **one fixed timeout for everything** (a flat 5 s deadline on every item).
16//! For that workload the wheel buckets by deadline and walks buckets to solve
17//! an ordering problem that does not exist. `TimeoutQueue` exploits the single
18//! duration directly.
19//!
20//! # The invariant is structural, not documented
21//!
22//! There is no per-call `deadline` parameter anywhere in this API. Deadlines
23//! are computed internally as `now + timeout`. Out-of-order insertion is
24//! *unrepresentable*, not merely prohibited — one caller passing a shorter
25//! deadline would break ordering and fire timers late, the worst failure shape
26//! because it is invisible until it matters. A `debug_assert!` on insert is the
27//! backstop for clock weirdness (a `now` that goes backwards).
28//!
29//! # Reuse
30//!
31//! [`WheelEntry`], [`TimerHandle`], the slab
32//! [`store`](crate::store) traits, and the DLL splice logic (`WheelSlot`) are
33//! shared verbatim with the wheel — this front-end is the same machinery with
34//! one head/tail pair in place of `Vec<Level>`, and the whole `min_deadline`
35//! cache removed (the head *is* the min).
36
37use std::marker::PhantomData;
38use std::mem;
39use std::time::{Duration, Instant};
40
41use nexus_slab::{Full, Slot, bounded, unbounded};
42
43use crate::ConfigError;
44use crate::entry::{EntryPtr, WheelEntry, entry_ref};
45use crate::handle::TimerHandle;
46use crate::level::WheelSlot;
47use crate::store::{BoundedStore, SlabStore};
48
49// =============================================================================
50// TimeoutQueueBuilder (typestate)
51// =============================================================================
52
53/// Builder for a [`TimeoutQueue`], mirroring [`WheelBuilder`](crate::WheelBuilder).
54///
55/// The timeout duration is fixed up front in [`new`](Self::new) — that is the
56/// whole point of the type, so it cannot be a per-schedule parameter later.
57///
58/// # Examples
59///
60/// ```
61/// use std::time::{Duration, Instant};
62/// use nexus_timer::{TimeoutQueue, TimeoutQueueBuilder};
63///
64/// let now = Instant::now();
65///
66/// // 5-second timeout, unbounded storage, default 1ms tick.
67/// let list: TimeoutQueue<u64> = TimeoutQueueBuilder::new(Duration::from_secs(5))
68///     .unbounded(4096)
69///     .build(now)
70///     .unwrap();
71///
72/// // Custom tick, bounded storage.
73/// let list: nexus_timer::BoundedTimeoutQueue<u64> =
74///     TimeoutQueueBuilder::new(Duration::from_millis(250))
75///         .tick_duration(Duration::from_micros(100))
76///         .bounded(1024)
77///         .build(now)
78///         .unwrap();
79/// ```
80#[derive(Debug, Clone, Copy)]
81pub struct TimeoutQueueBuilder {
82    timeout: Duration,
83    tick_duration: Duration,
84}
85
86impl TimeoutQueueBuilder {
87    /// Creates a builder with the fixed timeout every timer will use.
88    ///
89    /// Tick duration defaults to 1ms. The timeout must be non-zero — this is not
90    /// checked here but enforced at [`build`](UnboundedTimeoutQueueBuilder::build),
91    /// which returns [`ConfigError`] otherwise.
92    pub fn new(timeout: Duration) -> Self {
93        TimeoutQueueBuilder {
94            timeout,
95            tick_duration: Duration::from_millis(1),
96        }
97    }
98
99    /// Sets the tick duration (internal time quantum). Default: 1ms.
100    pub fn tick_duration(mut self, d: Duration) -> Self {
101        self.tick_duration = d;
102        self
103    }
104
105    /// Transitions to an unbounded (growable) builder.
106    ///
107    /// `chunk_capacity` is the slab chunk size (entries per chunk); the slab
108    /// grows by adding chunks as needed.
109    pub fn unbounded(self, chunk_capacity: usize) -> UnboundedTimeoutQueueBuilder {
110        UnboundedTimeoutQueueBuilder {
111            config: self,
112            chunk_capacity,
113        }
114    }
115
116    /// Transitions to a bounded (fixed-capacity) builder.
117    ///
118    /// `capacity` is the maximum number of concurrent timers.
119    pub fn bounded(self, capacity: usize) -> BoundedTimeoutQueueBuilder {
120        BoundedTimeoutQueueBuilder {
121            config: self,
122            capacity,
123        }
124    }
125
126    fn validate(&self) -> Result<(), ConfigError> {
127        if self.timeout.is_zero() {
128            return Err(ConfigError::Invalid("timeout must be non-zero"));
129        }
130        if self.tick_duration.is_zero() {
131            return Err(ConfigError::Invalid("tick_duration must be non-zero"));
132        }
133        // tick_ns() narrows as_nanos() (u128) to u64; reject a tick that would
134        // not fit so build() cannot produce a zero tick (divide-by-zero). See
135        // WheelBuilder::validate.
136        if self.tick_duration.as_nanos() > u64::MAX as u128 {
137            return Err(ConfigError::Invalid(
138                "tick_duration must fit in u64 nanoseconds",
139            ));
140        }
141        Ok(())
142    }
143
144    #[inline]
145    fn tick_ns(&self) -> u64 {
146        self.tick_duration.as_nanos().min(u64::MAX as u128) as u64
147    }
148
149    /// Fixed timeout expressed in whole ticks (rounded up, minimum 1 tick).
150    ///
151    /// Ceiling division so the effective timeout is never *shorter* than
152    /// requested. Computed once at build time — never on the hot path.
153    #[inline]
154    fn timeout_ticks(&self) -> u64 {
155        let tick_ns = self.tick_ns() as u128;
156        let timeout_ns = self.timeout.as_nanos();
157        let ticks = timeout_ns.div_ceil(tick_ns);
158        ticks.min(u64::MAX as u128).max(1) as u64
159    }
160}
161
162/// Terminal builder for an unbounded [`TimeoutQueue`].
163///
164/// Created via [`TimeoutQueueBuilder::unbounded`]. The only method is `.build()`.
165#[derive(Debug)]
166pub struct UnboundedTimeoutQueueBuilder {
167    config: TimeoutQueueBuilder,
168    chunk_capacity: usize,
169}
170
171impl UnboundedTimeoutQueueBuilder {
172    /// Builds the unbounded timeout queue, validating the configuration.
173    ///
174    /// # Errors
175    ///
176    /// Returns [`ConfigError`] if the configuration is invalid (zero timeout, or a
177    /// tick duration that is zero or exceeds u64 nanoseconds).
178    pub fn build<T: 'static>(self, now: Instant) -> Result<TimeoutQueue<T>, ConfigError> {
179        self.config.validate()?;
180        let tick_ns = self.config.tick_ns();
181        let timeout_ticks = self.config.timeout_ticks();
182        // SAFETY: TimeoutQueue is single-threaded (!Sync). Every slot is freed
183        // via Slot::from_raw() + slab.free() before the list drops. The slab is
184        // never shared across threads.
185        let slab = unsafe { unbounded::Slab::with_chunk_capacity(self.chunk_capacity) };
186        Ok(TimeoutQueue {
187            list: WheelSlot::new(),
188            slab,
189            timeout_ticks,
190            tick_ns,
191            inv_tick_ns: (1u128 << 64) / tick_ns as u128,
192            epoch: now,
193            len: 0,
194            _marker: PhantomData,
195        })
196    }
197}
198
199/// Terminal builder for a bounded [`TimeoutQueue`].
200///
201/// Created via [`TimeoutQueueBuilder::bounded`]. The only method is `.build()`.
202#[derive(Debug)]
203pub struct BoundedTimeoutQueueBuilder {
204    config: TimeoutQueueBuilder,
205    capacity: usize,
206}
207
208impl BoundedTimeoutQueueBuilder {
209    /// Builds the bounded timeout queue, validating the configuration.
210    ///
211    /// # Errors
212    ///
213    /// Returns [`ConfigError`] if the configuration is invalid (zero timeout, or a
214    /// tick duration that is zero or exceeds u64 nanoseconds).
215    pub fn build<T: 'static>(self, now: Instant) -> Result<BoundedTimeoutQueue<T>, ConfigError> {
216        self.config.validate()?;
217        let tick_ns = self.config.tick_ns();
218        let timeout_ticks = self.config.timeout_ticks();
219        // SAFETY: TimeoutQueue is single-threaded (!Sync). Every slot is freed
220        // via Slot::from_raw() + slab.free() before the list drops. The slab is
221        // never shared across threads.
222        let slab = unsafe { bounded::Slab::with_capacity(self.capacity) };
223        Ok(TimeoutQueue {
224            list: WheelSlot::new(),
225            slab,
226            timeout_ticks,
227            tick_ns,
228            inv_tick_ns: (1u128 << 64) / tick_ns as u128,
229            epoch: now,
230            len: 0,
231            _marker: PhantomData,
232        })
233    }
234}
235
236// =============================================================================
237// TimeoutQueue
238// =============================================================================
239
240/// A fixed-duration timeout queue with O(fired) poll and O(1) exact next-deadline.
241///
242/// Generic over:
243/// - `T` — the user payload stored with each timer.
244/// - `S` — the slab storage backend. Defaults to `unbounded::Slab`.
245///
246/// Every timer uses the same duration, fixed at construction. See the
247/// [module docs](crate::timeout_queue) for the invariant this exploits.
248///
249/// # No `reschedule`
250///
251/// Rescheduling *later* is push-to-tail and stays ordered, but rescheduling
252/// *earlier* would break the sort — and the two are indistinguishable in a
253/// single API. So no `reschedule` is offered: callers `cancel` and re-`schedule`,
254/// which is the same two operations without the ordering hazard. (This mirrors
255/// the wheel's `reschedule`, deliberately omitted here.)
256///
257/// # Thread Safety
258///
259/// `Send` but `!Sync`. Can be moved to a thread at setup but must not be
260/// shared. All internal raw pointers point into owned allocations (slab
261/// chunks) — moving the list moves the heap data with it.
262pub struct TimeoutQueue<
263    T: 'static,
264    S: SlabStore<Item = WheelEntry<T>> = unbounded::Slab<WheelEntry<T>>,
265> {
266    /// The whole sorted list: one head/tail intrusive DLL. Reuses the wheel's
267    /// `WheelSlot` splice logic (push at tail, unlink from anywhere).
268    list: WheelSlot<T>,
269    slab: S,
270    /// Fixed timeout in ticks. Added to `now` on every schedule.
271    timeout_ticks: u64,
272    tick_ns: u64,
273    inv_tick_ns: u128,
274    epoch: Instant,
275    len: usize,
276    _marker: PhantomData<*const ()>, // !Send (overridden below), !Sync
277}
278
279// SAFETY: TimeoutQueue<T, S> exclusively owns all memory behind its raw
280// pointers. The slot head/tail and the WheelEntry prev/next links point into
281// slab-owned memory (SlotCell in a slab chunk, a Vec<SlotCell<T>> heap
282// allocation). When the list is moved, those heap allocations stay at their
283// addresses, so the internal pointers remain valid. No thread-local state, no
284// shared ownership.
285//
286// T: Send is required because timer values cross the thread boundary with the
287// list. S is NOT required to be Send: slab types are !Send (raw pointers,
288// Cell), but the list exclusively owns its slab — no shared access, no
289// aliasing. Outstanding TimerHandle<T> values are !Send and cannot follow the
290// list across threads; they become inert (consuming one requires &mut
291// TimeoutQueue, which the original thread no longer has). Worst case is a slot
292// leak (refcount stuck at 1), not unsoundness — the same reasoning as the
293// wheel.
294#[allow(clippy::non_send_fields_in_send_ty)]
295unsafe impl<T: Send + 'static, S: SlabStore<Item = WheelEntry<T>>> Send for TimeoutQueue<T, S> {}
296
297/// A timeout queue backed by a fixed-capacity slab.
298pub type BoundedTimeoutQueue<T> = TimeoutQueue<T, bounded::Slab<WheelEntry<T>>>;
299
300// =============================================================================
301// Construction convenience
302// =============================================================================
303
304impl<T: 'static> TimeoutQueue<T> {
305    /// Creates an unbounded timeout queue with the default 1ms tick.
306    ///
307    /// Every timer fires `timeout` after the `now` passed to `schedule`. The
308    /// `now` here fixes the reference epoch — pass one monotone clock source
309    /// (e.g. `Instant::now()`) here and to every `schedule`/`poll`. For a custom
310    /// tick duration, use [`TimeoutQueueBuilder`].
311    ///
312    /// # Panics
313    ///
314    /// Panics if `timeout` is zero. Use [`TimeoutQueueBuilder::build`] to handle
315    /// a runtime-sourced timeout without panicking.
316    pub fn unbounded(timeout: Duration, chunk_capacity: usize, now: Instant) -> Self {
317        TimeoutQueueBuilder::new(timeout)
318            .unbounded(chunk_capacity)
319            .build(now)
320            .expect("TimeoutQueue requires a non-zero timeout")
321    }
322}
323
324impl<T: 'static> BoundedTimeoutQueue<T> {
325    /// Creates a bounded timeout queue with the default 1ms tick.
326    ///
327    /// Every timer fires `timeout` after the `now` passed to `schedule`. The
328    /// `now` here fixes the reference epoch — pass one monotone clock source
329    /// (e.g. `Instant::now()`) here and to every `schedule`/`poll`. For a custom
330    /// tick duration, use [`TimeoutQueueBuilder`].
331    ///
332    /// # Panics
333    ///
334    /// Panics if `timeout` is zero. Use [`TimeoutQueueBuilder::build`] to handle
335    /// a runtime-sourced timeout without panicking.
336    pub fn bounded(timeout: Duration, capacity: usize, now: Instant) -> Self {
337        TimeoutQueueBuilder::new(timeout)
338            .bounded(capacity)
339            .build(now)
340            .expect("TimeoutQueue requires a non-zero timeout")
341    }
342}
343
344// =============================================================================
345// Schedule
346// =============================================================================
347
348impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
349    /// Schedules a timer for `now + timeout` and returns a handle for cancellation.
350    ///
351    /// The handle must be consumed via [`cancel`](Self::cancel) or
352    /// [`free`](Self::free). Dropping it is a programming error.
353    ///
354    /// `now` must be monotonically non-decreasing across calls (a plain
355    /// `Instant::now()` at each call site satisfies this). A `now` that goes
356    /// backwards trips a `debug_assert!` in debug builds.
357    ///
358    /// # Panics
359    ///
360    /// Panics if the backing slab is at capacity (bounded slabs only). This is
361    /// a capacity planning error — size the list for peak load.
362    pub fn schedule(&mut self, now: Instant, value: T) -> TimerHandle<T> {
363        let deadline_ticks = self.deadline_for(now);
364        let entry = WheelEntry::new(deadline_ticks, value, 2);
365        let ptr = self.slab.alloc(entry).into_raw();
366        self.insert_entry(ptr, deadline_ticks);
367        self.len += 1;
368        TimerHandle::new(ptr)
369    }
370
371    /// Schedules a fire-and-forget timer for `now + timeout` (no handle returned).
372    ///
373    /// The timer fires during poll and its value is collected. It cannot be
374    /// cancelled. See [`schedule`](Self::schedule) for the `now` monotonicity
375    /// requirement.
376    ///
377    /// # Panics
378    ///
379    /// Panics if the backing slab is at capacity (bounded slabs only).
380    pub fn schedule_forget(&mut self, now: Instant, value: T) {
381        let deadline_ticks = self.deadline_for(now);
382        let entry = WheelEntry::new(deadline_ticks, value, 1);
383        let ptr = self.slab.alloc(entry).into_raw();
384        self.insert_entry(ptr, deadline_ticks);
385        self.len += 1;
386    }
387}
388
389// =============================================================================
390// Schedule — fallible (bounded slabs only)
391// =============================================================================
392
393impl<T: 'static, S: BoundedStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
394    /// Attempts to schedule a timer, returning a handle on success.
395    ///
396    /// Returns `Err(Full(value))` — with the caller's `T` recovered, not the
397    /// internal `WheelEntry` — if the slab is at capacity. Use this when
398    /// capacity exhaustion should be handled gracefully; otherwise use
399    /// [`schedule`](Self::schedule).
400    pub fn try_schedule(&mut self, now: Instant, value: T) -> Result<TimerHandle<T>, Full<T>> {
401        let deadline_ticks = self.deadline_for(now);
402        let entry = WheelEntry::new(deadline_ticks, value, 2);
403        match self.slab.try_alloc(entry) {
404            Ok(slot) => {
405                let ptr = slot.into_raw();
406                self.insert_entry(ptr, deadline_ticks);
407                self.len += 1;
408                Ok(TimerHandle::new(ptr))
409            }
410            Err(full) => Err(Full(recover_value(full))),
411        }
412    }
413
414    /// Attempts to schedule a fire-and-forget timer.
415    ///
416    /// Returns `Err(Full(value))` — with the caller's `T` recovered — if the
417    /// slab is at capacity. Otherwise use [`schedule_forget`](Self::schedule_forget).
418    pub fn try_schedule_forget(&mut self, now: Instant, value: T) -> Result<(), Full<T>> {
419        let deadline_ticks = self.deadline_for(now);
420        let entry = WheelEntry::new(deadline_ticks, value, 1);
421        match self.slab.try_alloc(entry) {
422            Ok(slot) => {
423                let ptr = slot.into_raw();
424                self.insert_entry(ptr, deadline_ticks);
425                self.len += 1;
426                Ok(())
427            }
428            Err(full) => Err(Full(recover_value(full))),
429        }
430    }
431}
432
433/// Extracts the user's `T` from a `Full<WheelEntry<T>>` produced by a rejected
434/// `try_alloc`. The entry was just constructed with `Some(value)` and never
435/// inserted, so the value is present.
436#[inline]
437fn recover_value<T>(full: Full<WheelEntry<T>>) -> T {
438    let wheel_entry = full.into_inner();
439    // SAFETY: entry was just constructed with Some(value) and never inserted
440    // into the list — no other code has accessed it. Single-threaded.
441    unsafe { wheel_entry.take_value() }.expect("entry was just constructed with Some(value)")
442}
443
444// =============================================================================
445// Cancel / Free / Poll / Query — generic over any store
446// =============================================================================
447
448impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimeoutQueue<T, S> {
449    /// Cancels a timer and returns its value.
450    ///
451    /// - Still active (refs == 2): unlinks from the list, extracts the value,
452    ///   frees the slab entry. Returns `Some(T)`. O(1) — a mid-list unlink,
453    ///   no residency, no tombstone.
454    /// - Already fired (zombie handle, refs == 1): frees the slab entry.
455    ///   Returns `None`.
456    ///
457    /// Consumes the handle (no Drop runs).
458    pub fn cancel(&mut self, handle: TimerHandle<T>) -> Option<T> {
459        let ptr = handle.ptr;
460        // Consume handle without running Drop.
461        mem::forget(handle);
462
463        // SAFETY: handle guarantees ptr is valid and allocated from our slab.
464        let entry = unsafe { entry_ref(ptr) };
465        let refs = entry.refs();
466
467        if refs == 2 {
468            // Active timer with handle — unlink, extract, free.
469            // SAFETY: single-threaded; entry is still in the list (refs == 2),
470            // so the value has not been taken by fire_entry.
471            let value = unsafe { entry.take_value() };
472            // SAFETY: ptr is in self.list's DLL (invariant from insert_entry).
473            unsafe { self.list.remove_entry(ptr) };
474            self.len -= 1;
475            // SAFETY: ptr was allocated from our slab via into_raw().
476            self.slab.free(unsafe { Slot::from_raw(ptr) });
477            value
478        } else {
479            // refs == 1: the list already fired this (zombie). The fire path
480            // decremented 2 -> 1 and left the entry for us to free.
481            debug_assert_eq!(refs, 1, "unexpected refcount {refs} in cancel");
482            // SAFETY: ptr was allocated from our slab via into_raw().
483            self.slab.free(unsafe { Slot::from_raw(ptr) });
484            None
485        }
486    }
487
488    /// Releases a timer handle without cancelling.
489    ///
490    /// - Still active: converts to fire-and-forget (refs 2 -> 1). The timer
491    ///   stays in the list and fires normally during poll.
492    /// - Already fired (zombie): frees the slab entry (refs 1 -> 0).
493    ///
494    /// Consumes the handle (no Drop runs).
495    pub fn free(&mut self, handle: TimerHandle<T>) {
496        let ptr = handle.ptr;
497        mem::forget(handle);
498
499        // SAFETY: handle guarantees ptr is valid.
500        let entry = unsafe { entry_ref(ptr) };
501        let new_refs = entry.dec_refs();
502
503        if new_refs == 0 {
504            // Was a zombie (fired already, refs was 1) — free the entry.
505            // SAFETY: ptr was allocated from our slab via into_raw().
506            self.slab.free(unsafe { Slot::from_raw(ptr) });
507        }
508        // new_refs == 1: timer is now fire-and-forget, stays in the list.
509    }
510
511    /// Fires all expired timers, collecting their values into `buf`.
512    ///
513    /// Returns the number of timers fired. O(fired): the list is sorted, so
514    /// this walks from the head and stops at the first not-due entry.
515    pub fn poll(&mut self, now: Instant, buf: &mut Vec<T>) -> usize {
516        self.poll_with_limit(now, usize::MAX, buf)
517    }
518
519    /// Fires expired timers up to `limit`, collecting values into `buf`.
520    ///
521    /// Returns the number fired in this call. Truncation is resumable: this
522    /// stops at a head that is either not-due or beyond `limit`, and the next
523    /// call picks up at exactly that head. No bookmark is needed — the sorted
524    /// list *is* the cursor. (The wheel needs a resumption argument because it
525    /// re-derives its scan position each call; here there is nothing to
526    /// re-derive.)
527    pub fn poll_with_limit(&mut self, now: Instant, limit: usize, buf: &mut Vec<T>) -> usize {
528        let now_ticks = self.instant_to_ticks(now);
529        let mut fired = 0;
530
531        while fired < limit {
532            let ptr = self.list.entry_head();
533            if ptr.is_null() {
534                break;
535            }
536            // SAFETY: ptr is the non-null head of self.list's DLL.
537            let entry = unsafe { entry_ref(ptr) };
538
539            #[cfg(test)]
540            {
541                poll_examined_inc();
542            }
543
544            if entry.deadline_ticks() > now_ticks {
545                // Sorted: nothing behind the head is due either.
546                break;
547            }
548
549            // SAFETY: ptr is the current head of self.list's DLL.
550            unsafe { self.list.remove_entry(ptr) };
551            if let Some(value) = self.fire_entry(ptr) {
552                buf.push(value);
553            }
554            fired += 1;
555        }
556
557        fired
558    }
559
560    /// Returns the `Instant` of the next timer that will fire, or `None` if empty.
561    ///
562    /// O(1), exact: the sorted list's head *is* the minimum deadline. No cache.
563    pub fn next_deadline(&self) -> Option<Instant> {
564        let head = self.list.entry_head();
565        if head.is_null() {
566            return None;
567        }
568        // SAFETY: head is non-null and points into self.list's DLL.
569        let ticks = unsafe { entry_ref(head) }.deadline_ticks();
570        Some(self.ticks_to_instant(ticks))
571    }
572
573    /// Returns the number of timers currently in the list.
574    #[inline]
575    pub fn len(&self) -> usize {
576        self.len
577    }
578
579    /// Returns true if the list contains no timers.
580    #[inline]
581    pub fn is_empty(&self) -> bool {
582        self.len == 0
583    }
584
585    // =========================================================================
586    // Internal: tick conversion (replicated from the wheel)
587    // =========================================================================
588
589    #[inline]
590    fn instant_to_ticks(&self, instant: Instant) -> u64 {
591        let dur = instant.saturating_duration_since(self.epoch);
592        let nanos = dur.as_nanos().min(u64::MAX as u128) as u64;
593        ((nanos as u128 * self.inv_tick_ns) >> 64) as u64
594    }
595
596    #[inline]
597    fn ticks_to_instant(&self, ticks: u64) -> Instant {
598        self.epoch + Duration::from_nanos(ticks.saturating_mul(self.tick_ns))
599    }
600
601    /// Deadline in ticks for a timer scheduled at `now`: `now + fixed timeout`.
602    ///
603    /// Saturating add guards the (unrealistic, ~584-year) case where `now` is
604    /// far enough out that the tick count plus the timeout would overflow u64.
605    #[inline]
606    fn deadline_for(&self, now: Instant) -> u64 {
607        self.instant_to_ticks(now)
608            .saturating_add(self.timeout_ticks)
609    }
610
611    // =========================================================================
612    // Internal: insert / fire
613    // =========================================================================
614
615    /// Appends an entry at the tail of the sorted list.
616    ///
617    /// Correctness rests on the caller's `deadline_ticks` being >= the current
618    /// tail's — guaranteed by a monotone `now` and a constant timeout. The
619    /// `debug_assert!` is the backstop for a clock that goes backwards.
620    #[inline]
621    fn insert_entry(&mut self, entry_ptr: EntryPtr<T>, deadline_ticks: u64) {
622        // The entry's `level`/`slot_idx` stay at their `WheelEntry::new` default
623        // of (0, 0): a single sorted list has no slot to record, and the unlink
624        // path (`WheelSlot::remove_entry`) splices via prev/next and never reads
625        // location. So there is no `set_location` write on this hot path.
626        debug_assert!(
627            {
628                let tail = self.list.entry_tail();
629                // SAFETY: tail, when non-null, points into self.list's DLL.
630                tail.is_null() || deadline_ticks >= unsafe { entry_ref(tail) }.deadline_ticks()
631            },
632            "TimeoutQueue: deadline {deadline_ticks} inserted out of order \
633             (did `now` go backwards?)",
634        );
635
636        // SAFETY: entry_ptr is valid (just allocated) and not in any DLL yet.
637        unsafe { self.list.push_entry(entry_ptr) };
638    }
639
640    /// Fires a single entry: extracts value, decrements refcount, possibly frees.
641    ///
642    /// Returns `Some(T)` if the value was still present (not already cancelled).
643    /// The caller has already unlinked `entry_ptr` from the list.
644    #[inline]
645    fn fire_entry(&mut self, entry_ptr: EntryPtr<T>) -> Option<T> {
646        // SAFETY: entry_ptr was the head we just unlinked; still a live slab slot.
647        let entry = unsafe { entry_ref(entry_ptr) };
648
649        // SAFETY: single-threaded.
650        let value = unsafe { entry.take_value() };
651
652        let new_refs = entry.dec_refs();
653        if new_refs == 0 {
654            // Fire-and-forget (was refs == 1) — free the slab entry immediately.
655            // SAFETY: entry_ptr was allocated from our slab via into_raw().
656            self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
657        }
658        // new_refs == 1: handle exists (was refs == 2), entry becomes a zombie.
659        // The handle holder frees it via cancel() or free().
660
661        self.len -= 1;
662        value
663    }
664}
665
666// =============================================================================
667// Drop
668// =============================================================================
669
670impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> Drop for TimeoutQueue<T, S> {
671    fn drop(&mut self) {
672        // Walk the single list, free every remaining entry so nothing leaks.
673        let mut entry_ptr = self.list.entry_head();
674        while !entry_ptr.is_null() {
675            // SAFETY: entry_ptr is in self.list's DLL.
676            let next_entry = unsafe { entry_ref(entry_ptr) }.next();
677            // SAFETY: entry_ptr was allocated from our slab via into_raw().
678            self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
679            entry_ptr = next_entry;
680        }
681    }
682}
683
684// =============================================================================
685// Test-only instrumentation: entries examined during poll
686// =============================================================================
687//
688// A nothing-due poll must be flat across population — it examines only the
689// head (one deadline compare) and fires nothing, never scanning the list the
690// way the wheel does. This counter proves that: tests reset it, poll, and
691// assert the count is 1 (non-empty, nothing due) regardless of population.
692
693#[cfg(test)]
694thread_local! {
695    static POLL_EXAMINED: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
696}
697
698#[cfg(test)]
699fn poll_examined_inc() {
700    POLL_EXAMINED.with(|c| c.set(c.get() + 1));
701}
702
703#[cfg(test)]
704fn poll_examined_reset() {
705    POLL_EXAMINED.with(|c| c.set(0));
706}
707
708#[cfg(test)]
709fn poll_examined_get() -> usize {
710    POLL_EXAMINED.with(std::cell::Cell::get)
711}
712
713// =============================================================================
714// Tests
715// =============================================================================
716
717#[cfg(test)]
718mod tests {
719    use super::*;
720    use std::time::{Duration, Instant};
721
722    fn ms(millis: u64) -> Duration {
723        Duration::from_millis(millis)
724    }
725
726    fn list_50ms(now: Instant) -> TimeoutQueue<u64> {
727        TimeoutQueue::unbounded(ms(50), 1024, now)
728    }
729
730    // -------------------------------------------------------------------------
731    // Thread safety
732    // -------------------------------------------------------------------------
733
734    fn assert_send<T: Send>() {}
735
736    #[test]
737    fn timeout_queue_is_send() {
738        assert_send::<TimeoutQueue<u64>>();
739        assert_send::<BoundedTimeoutQueue<u64>>();
740    }
741
742    // -------------------------------------------------------------------------
743    // Construction
744    // -------------------------------------------------------------------------
745
746    #[test]
747    fn default_construction() {
748        let now = Instant::now();
749        let list = list_50ms(now);
750        assert!(list.is_empty());
751        assert_eq!(list.len(), 0);
752        assert!(list.next_deadline().is_none());
753    }
754
755    #[test]
756    fn bounded_construction() {
757        let now = Instant::now();
758        let list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 128, now);
759        assert!(list.is_empty());
760    }
761
762    /// Asserts `result` is `Err(ConfigError::Invalid(_))` whose message contains
763    /// `expect_substr`. Generic over the Ok type so it needs no `Debug` bound.
764    #[track_caller]
765    fn assert_invalid<T>(result: &Result<T, ConfigError>, expect_substr: &str) {
766        match result {
767            Err(ConfigError::Invalid(msg)) => assert!(
768                msg.contains(expect_substr),
769                "message {msg:?} does not contain {expect_substr:?}"
770            ),
771            Ok(_) => panic!("expected ConfigError::Invalid containing {expect_substr:?}, got Ok"),
772        }
773    }
774
775    #[test]
776    fn invalid_zero_timeout() {
777        let now = Instant::now();
778        let result = TimeoutQueueBuilder::new(Duration::ZERO)
779            .unbounded(64)
780            .build::<u64>(now);
781        assert_invalid(&result, "timeout must be non-zero");
782    }
783
784    #[test]
785    fn invalid_zero_tick() {
786        let now = Instant::now();
787        let result = TimeoutQueueBuilder::new(ms(50))
788            .tick_duration(Duration::ZERO)
789            .unbounded(64)
790            .build::<u64>(now);
791        assert_invalid(&result, "tick_duration must be non-zero");
792    }
793
794    #[test]
795    fn invalid_tick_too_large() {
796        let now = Instant::now();
797        // as_nanos() would exceed u64::MAX and truncate on the cast — reject.
798        let result = TimeoutQueueBuilder::new(ms(50))
799            .tick_duration(Duration::from_secs(20_000_000_000))
800            .unbounded(64)
801            .build::<u64>(now);
802        assert_invalid(&result, "tick_duration must fit in u64 nanoseconds");
803    }
804
805    // -------------------------------------------------------------------------
806    // Lifecycle (ported from wheel.rs)
807    // -------------------------------------------------------------------------
808
809    #[test]
810    fn schedule_and_cancel() {
811        let now = Instant::now();
812        let mut list = list_50ms(now);
813
814        let h = list.schedule(now, 42);
815        assert_eq!(list.len(), 1);
816
817        let val = list.cancel(h);
818        assert_eq!(val, Some(42));
819        assert_eq!(list.len(), 0);
820    }
821
822    #[test]
823    fn schedule_forget_fires() {
824        let now = Instant::now();
825        let mut list = list_50ms(now);
826
827        list.schedule_forget(now, 99);
828        assert_eq!(list.len(), 1);
829
830        let mut buf = Vec::new();
831        let fired = list.poll(now + ms(60), &mut buf);
832        assert_eq!(fired, 1);
833        assert_eq!(buf, vec![99]);
834        assert_eq!(list.len(), 0);
835    }
836
837    #[test]
838    fn cancel_after_fire_returns_none() {
839        let now = Instant::now();
840        let mut list = list_50ms(now);
841
842        let h = list.schedule(now, 42);
843
844        let mut buf = Vec::new();
845        list.poll(now + ms(60), &mut buf);
846        assert_eq!(buf, vec![42]);
847
848        // Handle is now a zombie.
849        let val = list.cancel(h);
850        assert_eq!(val, None);
851    }
852
853    #[test]
854    fn free_active_timer_becomes_fire_and_forget() {
855        let now = Instant::now();
856        let mut list = list_50ms(now);
857
858        let h = list.schedule(now, 42);
859        list.free(h); // releases handle, timer stays
860        assert_eq!(list.len(), 1);
861
862        let mut buf = Vec::new();
863        list.poll(now + ms(60), &mut buf);
864        assert_eq!(buf, vec![42]);
865        assert_eq!(list.len(), 0);
866    }
867
868    #[test]
869    fn free_zombie_handle() {
870        let now = Instant::now();
871        let mut list = list_50ms(now);
872
873        let h = list.schedule(now, 42);
874
875        let mut buf = Vec::new();
876        list.poll(now + ms(60), &mut buf);
877
878        // Handle is a zombie, free cleans up.
879        list.free(h);
880    }
881
882    // -------------------------------------------------------------------------
883    // Bounded full
884    // -------------------------------------------------------------------------
885
886    #[test]
887    fn bounded_full() {
888        let now = Instant::now();
889        let mut list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 2, now);
890
891        let h1 = list.try_schedule(now, 1).unwrap();
892        let h2 = list.try_schedule(now, 2).unwrap();
893
894        let err = list.try_schedule(now, 3);
895        assert!(err.is_err());
896        // The caller's T is recovered, not the WheelEntry wrapper.
897        let recovered = err.unwrap_err().into_inner();
898        assert_eq!(recovered, 3);
899
900        // Cancel one, room again.
901        list.cancel(h1);
902        let h3 = list.try_schedule(now, 3).unwrap();
903
904        list.free(h2);
905        list.free(h3);
906    }
907
908    #[test]
909    fn bounded_schedule_forget_full() {
910        let now = Instant::now();
911        let mut list: BoundedTimeoutQueue<u64> = BoundedTimeoutQueue::bounded(ms(50), 1, now);
912
913        list.try_schedule_forget(now, 1).unwrap();
914        let err = list.try_schedule_forget(now, 2);
915        assert!(err.is_err());
916        assert_eq!(err.unwrap_err().into_inner(), 2);
917    }
918
919    // -------------------------------------------------------------------------
920    // Ordering / FIFO
921    // -------------------------------------------------------------------------
922
923    #[test]
924    fn poll_respects_deadline() {
925        let now = Instant::now();
926        let mut list = list_50ms(now);
927
928        // Fixed 50ms timeout; schedule at staggered `now`s.
929        list.schedule_forget(now, 1); // deadline ~50ms
930        list.schedule_forget(now + ms(40), 2); // deadline ~90ms
931        list.schedule_forget(now + ms(90), 3); // deadline ~140ms
932
933        let mut buf = Vec::new();
934
935        let fired = list.poll(now + ms(60), &mut buf);
936        assert_eq!(fired, 1);
937        assert_eq!(buf, vec![1]);
938        assert_eq!(list.len(), 2);
939
940        buf.clear();
941        let fired = list.poll(now + ms(100), &mut buf);
942        assert_eq!(fired, 1);
943        assert_eq!(buf, vec![2]);
944
945        buf.clear();
946        let fired = list.poll(now + ms(200), &mut buf);
947        assert_eq!(fired, 1);
948        assert_eq!(buf, vec![3]);
949
950        assert!(list.is_empty());
951    }
952
953    #[test]
954    fn mid_list_cancel_preserves_fifo() {
955        let now = Instant::now();
956        let mut list = list_50ms(now);
957
958        // Five timers at strictly increasing `now`s → strictly increasing
959        // deadlines, in insertion order.
960        let mut handles: Vec<_> = (0..5u64).map(|i| list.schedule(now + ms(i), i)).collect();
961        assert_eq!(list.len(), 5);
962
963        // Cancel index 2 (value 2), then index 0 (value 0). Remaining, in
964        // list order: [1, 3, 4].
965        let v2 = list.cancel(handles.remove(2));
966        assert_eq!(v2, Some(2));
967        let v0 = list.cancel(handles.remove(0));
968        assert_eq!(v0, Some(0));
969        assert_eq!(list.len(), 3);
970
971        let mut buf = Vec::new();
972        let fired = list.poll(now + ms(1000), &mut buf);
973        assert_eq!(fired, 3);
974        // Exact Vec equality — FIFO order, not sorted-after-the-fact.
975        assert_eq!(buf, vec![1, 3, 4]);
976
977        // Remaining handles are zombies now.
978        for h in handles {
979            assert_eq!(list.cancel(h), None);
980        }
981    }
982
983    // -------------------------------------------------------------------------
984    // poll_with_limit truncation + resumption
985    // -------------------------------------------------------------------------
986
987    #[test]
988    fn poll_with_limit_truncation_then_resumption() {
989        let now = Instant::now();
990        let mut list = list_50ms(now);
991
992        for i in 0..10u64 {
993            list.schedule_forget(now + ms(i), i);
994        }
995
996        let mut buf = Vec::new();
997        let poll_at = now + ms(1000);
998
999        let fired = list.poll_with_limit(poll_at, 3, &mut buf);
1000        assert_eq!(fired, 3);
1001        assert_eq!(list.len(), 7);
1002
1003        let fired = list.poll_with_limit(poll_at, 3, &mut buf);
1004        assert_eq!(fired, 3);
1005        assert_eq!(list.len(), 4);
1006
1007        let fired = list.poll(poll_at, &mut buf);
1008        assert_eq!(fired, 4);
1009        assert!(list.is_empty());
1010
1011        // Full set, in order, across the truncated calls.
1012        assert_eq!(buf, (0..10u64).collect::<Vec<_>>());
1013    }
1014
1015    #[test]
1016    fn poll_with_limit_mixed_expiry() {
1017        let now = Instant::now();
1018        let mut list = list_50ms(now);
1019
1020        // Three due at poll time, two not.
1021        list.schedule_forget(now, 1);
1022        list.schedule_forget(now, 2);
1023        list.schedule_forget(now, 3);
1024        list.schedule_forget(now + ms(500), 4); // deadline ~550ms
1025        list.schedule_forget(now + ms(500), 5);
1026        assert_eq!(list.len(), 5);
1027
1028        let mut buf = Vec::new();
1029
1030        let fired = list.poll_with_limit(now + ms(60), 2, &mut buf);
1031        assert_eq!(fired, 2);
1032        assert_eq!(list.len(), 3);
1033
1034        let fired = list.poll_with_limit(now + ms(60), 5, &mut buf);
1035        assert_eq!(fired, 1); // only the third due entry; 4 and 5 not due
1036        assert_eq!(list.len(), 2);
1037
1038        assert_eq!(buf, vec![1, 2, 3]);
1039    }
1040
1041    // -------------------------------------------------------------------------
1042    // next_deadline
1043    // -------------------------------------------------------------------------
1044
1045    #[test]
1046    fn next_deadline_is_head_before_and_after_cancel() {
1047        let now = Instant::now();
1048        let mut list = list_50ms(now);
1049
1050        let h0 = list.schedule(now, 0); // deadline ~ now+50
1051        list.schedule_forget(now + ms(30), 1); // deadline ~ now+80
1052        list.schedule_forget(now + ms(60), 2); // deadline ~ now+110
1053
1054        // Head is the first-scheduled: ~ now + 50ms.
1055        let d0 = list.next_deadline().unwrap();
1056        let delta0 = d0.duration_since(now);
1057        assert!(delta0 >= ms(49) && delta0 <= ms(51), "delta0 = {delta0:?}");
1058
1059        // Cancel the head — next deadline becomes the second entry (~now+80ms).
1060        assert_eq!(list.cancel(h0), Some(0));
1061        let d1 = list.next_deadline().unwrap();
1062        let delta1 = d1.duration_since(now);
1063        assert!(delta1 >= ms(79) && delta1 <= ms(81), "delta1 = {delta1:?}");
1064    }
1065
1066    #[test]
1067    fn next_deadline_empty_after_drain() {
1068        let now = Instant::now();
1069        let mut list = list_50ms(now);
1070        list.schedule_forget(now, 1);
1071
1072        let mut buf = Vec::new();
1073        list.poll(now + ms(60), &mut buf);
1074        assert!(list.next_deadline().is_none());
1075    }
1076
1077    // -------------------------------------------------------------------------
1078    // Nothing-due poll touches (examines) only the head — flat across population
1079    // -------------------------------------------------------------------------
1080
1081    #[test]
1082    fn nothing_due_poll_examines_only_head() {
1083        let now = Instant::now();
1084
1085        for &population in &[100usize, 1_000, 10_000, 50_000] {
1086            // Big timeout so nothing is due at poll time.
1087            let mut list: TimeoutQueue<u64> =
1088                TimeoutQueue::unbounded(Duration::from_secs(3600), population + 16, now);
1089            for i in 0..population as u64 {
1090                list.schedule_forget(now, i);
1091            }
1092            assert_eq!(list.len(), population);
1093
1094            let mut buf = Vec::new();
1095            poll_examined_reset();
1096            let fired = list.poll(now + ms(1), &mut buf); // nothing due
1097            assert_eq!(fired, 0);
1098            assert!(buf.is_empty());
1099
1100            // Exactly one entry examined (the head), regardless of population.
1101            // This is the O(1) nothing-due property — no population scan.
1102            assert_eq!(
1103                poll_examined_get(),
1104                1,
1105                "population {population}: nothing-due poll examined more than the head",
1106            );
1107        }
1108    }
1109
1110    #[test]
1111    fn nothing_due_poll_empty_examines_zero() {
1112        let now = Instant::now();
1113        let mut list = list_50ms(now);
1114
1115        let mut buf = Vec::new();
1116        poll_examined_reset();
1117        let fired = list.poll(now + ms(1), &mut buf);
1118        assert_eq!(fired, 0);
1119        // Empty list: literally zero entries touched.
1120        assert_eq!(poll_examined_get(), 0);
1121    }
1122
1123    // -------------------------------------------------------------------------
1124    // Same-deadline entries (all scheduled at the same `now`)
1125    // -------------------------------------------------------------------------
1126
1127    #[test]
1128    fn multiple_entries_same_deadline() {
1129        let now = Instant::now();
1130        let mut list = list_50ms(now);
1131
1132        let mut handles: Vec<_> = (0..5u64).map(|i| list.schedule(now, i)).collect();
1133        assert_eq!(list.len(), 5);
1134
1135        let v2 = list.cancel(handles.remove(2));
1136        assert_eq!(v2, Some(2));
1137        let v0 = list.cancel(handles.remove(0));
1138        assert_eq!(v0, Some(0));
1139        assert_eq!(list.len(), 3);
1140
1141        let mut buf = Vec::new();
1142        let fired = list.poll(now + ms(60), &mut buf);
1143        assert_eq!(fired, 3);
1144        assert_eq!(buf, vec![1, 3, 4]);
1145
1146        for h in handles {
1147            assert_eq!(list.cancel(h), None);
1148        }
1149    }
1150
1151    // -------------------------------------------------------------------------
1152    // Reuse after drain
1153    // -------------------------------------------------------------------------
1154
1155    #[test]
1156    fn reuse_after_full_drain() {
1157        let now = Instant::now();
1158        let mut list = list_50ms(now);
1159
1160        for i in 0..10u64 {
1161            list.schedule_forget(now, i);
1162        }
1163        let mut buf = Vec::new();
1164        list.poll(now + ms(60), &mut buf);
1165        assert_eq!(buf.len(), 10);
1166        assert!(list.is_empty());
1167
1168        buf.clear();
1169        for i in 10..20u64 {
1170            list.schedule_forget(now + ms(100), i);
1171        }
1172        assert_eq!(list.len(), 10);
1173        list.poll(now + ms(200), &mut buf);
1174        assert_eq!(buf.len(), 10);
1175        assert!(list.is_empty());
1176    }
1177
1178    // -------------------------------------------------------------------------
1179    // Drop
1180    // -------------------------------------------------------------------------
1181
1182    #[test]
1183    fn drop_cleans_up_active_entries() {
1184        // Prove the list drops the VALUES of unfired timers on `Drop`, not just
1185        // that it reclaims the slab slots. `unbounded::Slab::free` drops the
1186        // value (store.rs), but nothing else in the suite verifies it — the miri
1187        // run uses `-Zmiri-ignore-leaks`, so a value leak would slip straight
1188        // past. A `Drop`-counting value makes the property observable.
1189        use std::sync::Arc;
1190        use std::sync::atomic::{AtomicUsize, Ordering};
1191
1192        struct DropCounter(Arc<AtomicUsize>);
1193        impl Drop for DropCounter {
1194            fn drop(&mut self) {
1195                self.0.fetch_add(1, Ordering::Relaxed);
1196            }
1197        }
1198
1199        let dropped = Arc::new(AtomicUsize::new(0));
1200        let now = Instant::now();
1201        let mut list: TimeoutQueue<DropCounter> = TimeoutQueue::unbounded(ms(50), 1024, now);
1202        for i in 0..100u64 {
1203            list.schedule_forget(now + ms(i), DropCounter(Arc::clone(&dropped)));
1204        }
1205        assert_eq!(list.len(), 100);
1206
1207        drop(list);
1208        assert_eq!(
1209            dropped.load(Ordering::Relaxed),
1210            100,
1211            "every unfired timer's value must be dropped when the list is dropped",
1212        );
1213    }
1214
1215    #[test]
1216    fn drop_with_outstanding_handles() {
1217        // Dropping the list must free the VALUES of handle-bearing (refs == 2)
1218        // entries too, even when the handles were never consumed — the one Drop
1219        // path `drop_cleans_up_active_entries` (refs == 1) does not cover. The
1220        // handles are `mem::forget`ed to stand in for "still outstanding"
1221        // without tripping `TimerHandle`'s drop debug_assert.
1222        use std::sync::Arc;
1223        use std::sync::atomic::{AtomicUsize, Ordering};
1224
1225        struct DropCounter(Arc<AtomicUsize>);
1226        impl Drop for DropCounter {
1227            fn drop(&mut self) {
1228                self.0.fetch_add(1, Ordering::Relaxed);
1229            }
1230        }
1231
1232        let dropped = Arc::new(AtomicUsize::new(0));
1233        let now = Instant::now();
1234        let mut list: TimeoutQueue<DropCounter> = TimeoutQueue::unbounded(ms(50), 1024, now);
1235        for i in 0..100u64 {
1236            let h = list.schedule(now + ms(i), DropCounter(Arc::clone(&dropped)));
1237            std::mem::forget(h); // outstanding handle — never consumed (refs stays 2)
1238        }
1239        assert_eq!(list.len(), 100);
1240
1241        drop(list);
1242        assert_eq!(
1243            dropped.load(Ordering::Relaxed),
1244            100,
1245            "handle-bearing (refs == 2) timer values must be dropped with the list",
1246        );
1247    }
1248
1249    // -------------------------------------------------------------------------
1250    // Deadline-in-the-past fires immediately
1251    // -------------------------------------------------------------------------
1252
1253    #[test]
1254    fn poll_far_past_deadline_fires() {
1255        let now = Instant::now();
1256        let mut list = list_50ms(now);
1257
1258        list.schedule_forget(now, 42);
1259        let mut buf = Vec::new();
1260        // Way past the 50ms deadline.
1261        let fired = list.poll(now + ms(10_000), &mut buf);
1262        assert_eq!(fired, 1);
1263        assert_eq!(buf, vec![42]);
1264    }
1265
1266    // -------------------------------------------------------------------------
1267    // Miri-compatible tests (raw-pointer paths with a Drop type)
1268    // -------------------------------------------------------------------------
1269
1270    #[test]
1271    fn miri_schedule_cancel_drop_type() {
1272        let now = Instant::now();
1273        let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(50), 64, now);
1274
1275        let h = list.schedule(now, "hello".to_string());
1276        let val = list.cancel(h);
1277        assert_eq!(val, Some("hello".to_string()));
1278        assert!(list.is_empty());
1279    }
1280
1281    #[test]
1282    fn miri_poll_fires_drop_type() {
1283        let now = Instant::now();
1284        let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
1285
1286        list.schedule_forget(now, "a".to_string());
1287        list.schedule_forget(now, "b".to_string());
1288        list.schedule_forget(now, "c".to_string());
1289
1290        let mut buf = Vec::new();
1291        let fired = list.poll(now + ms(20), &mut buf);
1292        assert_eq!(fired, 3);
1293        assert_eq!(buf, vec!["a".to_string(), "b".to_string(), "c".to_string()]);
1294        assert!(list.is_empty());
1295    }
1296
1297    #[test]
1298    fn miri_cancel_zombie_drop_type() {
1299        let now = Instant::now();
1300        let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
1301
1302        let h = list.schedule(now, "zombie".to_string());
1303
1304        let mut buf = Vec::new();
1305        list.poll(now + ms(20), &mut buf);
1306        assert_eq!(buf, vec!["zombie".to_string()]);
1307
1308        let val = list.cancel(h);
1309        assert_eq!(val, None);
1310    }
1311
1312    #[test]
1313    fn miri_free_active_and_zombie() {
1314        let now = Instant::now();
1315        let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(10), 64, now);
1316
1317        // Active → fire-and-forget via free.
1318        let h1 = list.schedule(now, "active".to_string());
1319        list.free(h1);
1320
1321        let mut buf = Vec::new();
1322        list.poll(now + ms(20), &mut buf);
1323        assert_eq!(buf, vec!["active".to_string()]);
1324
1325        // Zombie → free.
1326        let h2 = list.schedule(now, "will-fire".to_string());
1327        buf.clear();
1328        list.poll(now + ms(20), &mut buf);
1329        list.free(h2);
1330    }
1331
1332    #[test]
1333    fn miri_mid_list_unlink_drop_type() {
1334        let now = Instant::now();
1335        let mut list: TimeoutQueue<Vec<u8>> = TimeoutQueue::unbounded(ms(10), 64, now);
1336
1337        let mut handles: Vec<_> = (0..5u8)
1338            .map(|i| list.schedule(now + Duration::from_micros(i as u64), vec![i; 32]))
1339            .collect();
1340
1341        // Cancel middle, then head.
1342        let v2 = list.cancel(handles.remove(2));
1343        assert_eq!(v2.unwrap(), vec![2u8; 32]);
1344        let v0 = list.cancel(handles.remove(0));
1345        assert_eq!(v0.unwrap(), vec![0u8; 32]);
1346
1347        let mut buf = Vec::new();
1348        list.poll(now + ms(20), &mut buf);
1349        assert_eq!(buf.len(), 3);
1350
1351        for h in handles {
1352            assert_eq!(list.cancel(h), None);
1353        }
1354    }
1355
1356    #[test]
1357    fn miri_drop_list_with_entries() {
1358        let now = Instant::now();
1359        let mut list: TimeoutQueue<String> = TimeoutQueue::unbounded(ms(50), 64, now);
1360
1361        for i in 0..20u64 {
1362            list.schedule_forget(now + ms(i), format!("entry-{i}"));
1363        }
1364        assert_eq!(list.len(), 20);
1365        drop(list);
1366    }
1367
1368    #[test]
1369    fn miri_bounded_lifecycle() {
1370        let now = Instant::now();
1371        let mut list: BoundedTimeoutQueue<String> = BoundedTimeoutQueue::bounded(ms(30), 4, now);
1372
1373        let h1 = list.try_schedule(now, "a".to_string()).unwrap();
1374        let h2 = list.try_schedule(now, "b".to_string()).unwrap();
1375        let h3 = list.try_schedule(now, "c".to_string()).unwrap();
1376        let h4 = list.try_schedule(now, "d".to_string()).unwrap();
1377
1378        assert!(list.try_schedule(now, "e".to_string()).is_err());
1379
1380        list.cancel(h1);
1381        let h5 = list.try_schedule(now, "e".to_string()).unwrap();
1382
1383        let mut buf = Vec::new();
1384        list.poll(now + ms(40), &mut buf);
1385
1386        // Everything fired; remaining handles are zombies.
1387        list.free(h2);
1388        list.free(h3);
1389        list.free(h4);
1390        list.free(h5);
1391    }
1392}
1393
1394// =============================================================================
1395// Property tests
1396// =============================================================================
1397
1398#[cfg(test)]
1399mod proptests {
1400    use super::*;
1401    use proptest::prelude::*;
1402    use std::collections::{HashMap, HashSet};
1403    use std::time::{Duration, Instant};
1404
1405    const TIMEOUT_MS: u64 = 100;
1406    // With a 1ms tick and an exact-multiple timeout, the reciprocal tick
1407    // conversion is at most one tick low, so a timer can fire at most 1ms
1408    // before its nominal `schedule_now + TIMEOUT_MS` deadline.
1409    const EARLY_SLOP_MS: u64 = 1;
1410
1411    #[derive(Debug, Clone)]
1412    enum Op {
1413        Schedule,
1414        ScheduleForget,
1415        Cancel { idx: usize },
1416        Poll,
1417        Advance,
1418    }
1419
1420    fn op_strategy() -> impl Strategy<Value = (Op, u64)> {
1421        // Every op carries a non-negative clock advance, keeping `now`
1422        // monotone so the fixed-timeout deadlines stay sorted.
1423        let advance = 0u64..500;
1424        let op = prop_oneof![
1425            Just(Op::Schedule),
1426            Just(Op::ScheduleForget),
1427            any::<usize>().prop_map(|idx| Op::Cancel { idx }),
1428            Just(Op::Poll),
1429            Just(Op::Advance),
1430        ];
1431        (op, advance)
1432    }
1433
1434    proptest! {
1435        #![proptest_config(ProptestConfig::with_cases(400))]
1436
1437        /// Random schedule / schedule_forget / cancel / poll interleaving.
1438        ///
1439        /// Invariants:
1440        /// - `len` always matches the live (scheduled, not cancelled, not
1441        ///   fired) count.
1442        /// - every value fires exactly once.
1443        /// - no value fires before its deadline (within 1ms tick slop).
1444        /// - each poll's output is non-decreasing in deadline.
1445        #[test]
1446        fn fuzz_schedule_cancel_poll(ops in proptest::collection::vec(op_strategy(), 1..300)) {
1447            let now = Instant::now();
1448            let mut list: TimeoutQueue<u64> = TimeoutQueue::unbounded(
1449                Duration::from_millis(TIMEOUT_MS),
1450                4096,
1451                now,
1452            );
1453
1454            // value -> nominal deadline_ms (schedule clock + TIMEOUT_MS)
1455            let mut live: HashMap<u64, u64> = HashMap::new();
1456            // outstanding active handles: (handle, value, deadline_ms)
1457            let mut handles: Vec<(TimerHandle<u64>, u64, u64)> = Vec::new();
1458            let mut fired: HashSet<u64> = HashSet::new();
1459            let mut clock: u64 = 0;
1460            let mut next_id: u64 = 0;
1461
1462            for (op, advance) in &ops {
1463                clock += *advance; // monotone
1464
1465                match op {
1466                    Op::Schedule => {
1467                        let id = next_id;
1468                        next_id += 1;
1469                        let deadline = clock + TIMEOUT_MS;
1470                        let h = list.schedule(now + Duration::from_millis(clock), id);
1471                        handles.push((h, id, deadline));
1472                        live.insert(id, deadline);
1473                    }
1474                    Op::ScheduleForget => {
1475                        let id = next_id;
1476                        next_id += 1;
1477                        let deadline = clock + TIMEOUT_MS;
1478                        list.schedule_forget(now + Duration::from_millis(clock), id);
1479                        live.insert(id, deadline);
1480                    }
1481                    Op::Cancel { idx } => {
1482                        if !handles.is_empty() {
1483                            let i = idx % handles.len();
1484                            let (h, val, _) = handles.swap_remove(i);
1485                            // Handles only ever hold active timers here (zombies
1486                            // are freed right after each poll), so cancel returns
1487                            // Some.
1488                            let r = list.cancel(h);
1489                            prop_assert_eq!(r, Some(val));
1490                            prop_assert!(live.remove(&val).is_some());
1491                            prop_assert!(!fired.contains(&val));
1492                        }
1493                    }
1494                    Op::Poll => {
1495                        let mut buf = Vec::new();
1496                        list.poll(now + Duration::from_millis(clock), &mut buf);
1497
1498                        let mut prev_deadline = 0u64;
1499                        for &v in &buf {
1500                            let deadline = *live.get(&v)
1501                                .expect("fired value must be live");
1502                            // No early fire (within tick slop).
1503                            prop_assert!(
1504                                deadline <= clock + EARLY_SLOP_MS,
1505                                "value {} deadline {}ms fired at {}ms",
1506                                v, deadline, clock,
1507                            );
1508                            // Non-decreasing in deadline within this poll.
1509                            prop_assert!(deadline >= prev_deadline);
1510                            prev_deadline = deadline;
1511                            // Fires exactly once.
1512                            prop_assert!(fired.insert(v));
1513                            live.remove(&v);
1514                        }
1515
1516                        // Free zombie handles whose timers just fired.
1517                        let fired_now: HashSet<u64> = buf.iter().copied().collect();
1518                        let mut i = 0;
1519                        while i < handles.len() {
1520                            if fired_now.contains(&handles[i].1) {
1521                                let (h, _, _) = handles.swap_remove(i);
1522                                list.free(h);
1523                            } else {
1524                                i += 1;
1525                            }
1526                        }
1527                    }
1528                    Op::Advance => {}
1529                }
1530
1531                prop_assert_eq!(list.len(), live.len());
1532            }
1533
1534            // Fire everything remaining.
1535            let mut buf = Vec::new();
1536            list.poll(now + Duration::from_secs(1_000_000), &mut buf);
1537            for &v in &buf {
1538                prop_assert!(fired.insert(v));
1539                prop_assert!(live.remove(&v).is_some());
1540            }
1541            // All remaining handles are zombies now.
1542            for (h, _, _) in handles {
1543                list.free(h);
1544            }
1545
1546            prop_assert!(live.is_empty());
1547            prop_assert!(list.is_empty());
1548        }
1549    }
1550}