A logical-time reactor: timers without a clock

A real runtime has two halves. The executor polls tasks that are ready. The reactor owns the waiting primitive — epoll, kqueue, IOCP, a timer wheel — and wakes tasks when their resource becomes ready. You have built the first half. This is the second, and it is the item that earns the phrase “zero to hero”.

Instead of a wall clock, use a logical clock: an integer that only moves when nothing else can run. That trick removes every source of flakiness from the test, and it is a technique worth stealing for any time-dependent system you ever need to test.

pub struct Reactor { now: u64, timers: BinaryHeap<Reverse<(u64, usize)>> }
pub struct Sleep { deadline: u64, armed: bool }
pub fn sleep(delay: u64) -> Sleep;             // Future<Output = u64>
pub fn advance(ex: &Executor) -> bool;
pub fn run(ex: &mut Executor);
pub fn simulate(delays: Vec<u64>) -> Vec<(usize, u64)>

simulate spawns one task per delay; task i sleeps d, logs (i, now), sleeps d again, logs again. The answer for [3, 1, 2] is

[(1,1), (1,2), (2,2), (0,3), (2,4), (0,6)]

Trace it by hand before you write anything. Task 1 (delay 1) fires at t=1 and again at t=2; task 2 (delay 2) fires at t=2 and t=4; task 0 (delay 3) fires at t=3 and t=6. At t=2 two tasks are due at once and task 1 goes first.

The rule that is the whole problem

The clock may only move when the ready queue is empty.

loop {
    while ex.step() {}        // drain everything that can run at the current time
    if !advance(ex) { return; }   // only now, move to the earliest deadline
}

Get that order wrong — advance the clock while tasks are still runnable — and time races ahead of work: a task that was about to arm a timer for now + 1 arms it for a now that has already gone past. The two halves of a runtime are not peers; the reactor runs only when the executor has nothing to do. That is true of your version and true of tokio’s.

BinaryHeap is a max-heap

std::collections::BinaryHeap::pop returns the largest element. Timers need the smallest. Wrap the entries in std::cmp::Reverse and the ordering flips. Forget, and you get a program that runs the latest timer first, and whose logical time goes backwards — which is exactly what the starter does, so you can watch it happen.

Key the heap on (deadline, task_id). The task_id costs nothing and buys deterministic tie-breaking: at t=2 in the trace above, tasks 1 and 2 are both due, and including the id is the difference between a stable test and a flaky one.

Sleep must arm exactly once

poll can be called any number of times. If Sleep pushes a timer on every poll you get duplicate entries, spurious wakeups and a heap that never drains. One armed: bool, set the first time, is enough. Compute the deadline at construction (now() + delay), not on first poll — that way sleep(d) means “d from when I asked”, which is what a reader expects.

sleep(0) is worth thinking about: now >= deadline on the very first poll, so it returns Ready immediately and never arms anything. A task built only from zero sleeps runs start to finish in a single poll.

Thread-locals and the RefCell rule

The reactor is a thread_local! { static REACTOR: RefCell<Reactor> }, which is how you get ambient access from inside Sleep::poll without threading a handle through every future. Two consequences:

• Reset it at the start of simulate. A thread-local outlives your simulation, so a second run in the same process starts with the clock where the first left it. The harness runs simulate twice and grades the second, so this is not optional here.
• Never hold a RefCell borrow across an .await. REACTOR.with_borrow_mut(|r| ..) scopes the borrow to the closure, which is exactly what you want. clippy checks this one for you: clippy::await_holding_refcell_ref is on by default and fatal under -D warnings.

Getting the current task’s id inside Sleep::poll needs the executor to publish it; the given Executor::step sets a CURRENT thread-local before polling, and current_task() reads it. Real runtimes do the same thing with a richer task context.

What you will have built

An executor with a ready queue and per-task wakers, a reactor with a timer heap, and a Sleep future that bridges them. Swap the logical clock for Instant, swap the heap for a hierarchical timer wheel, swap the ready queue for a work-stealing multi-queue, and you have tokio’s architecture. Not a simplification of it — the same shape.