Spawning, JoinHandle, and getting values back out

This exercise extends a small single-threaded executor so that a spawned task can hand its result back to whoever awaits it. The executor you are given already has spawn_raw, which accepts a Future<Output = ()> and throws the output away. On top of it sits spawn, which accepts a future with any 'static output type T and returns a JoinHandle<T>: a future that completes with that task's output. The starter already contains a draft of spawn and JoinHandle with one bug in it; your job is to make them correct.

pub struct Shared<T> { value: Option<T>, waker: Option<Waker> }
pub struct JoinHandle<T> { slot: Rc<RefCell<Shared<T>>> }
impl<T> Future for JoinHandle<T> { type Output = T; /* ... */ }

impl Executor {
    pub fn spawn<T: 'static>(&mut self, fut: impl Future<Output = T> + 'static) -> JoinHandle<T>;
}

A waker is the value a future stores so that it can later say "poll this task again". In this executor, waking a task pushes its id onto the ready queue, and run keeps polling tasks from that queue until it is empty.

The exercise contract

fan_in(inputs: Vec<u32>) -> Vec<u32> is given and you should not change it. For an input of length n, it spawns one worker per element. Worker i (counting from 0) yields n - i times and then returns inputs[i] * 2, so earlier workers finish later. It then spawns a collector task that awaits every handle in input order and pushes each result into the output.

• The result must be every input doubled, in input order. [1, 2, 3] gives [2, 4, 6], and an empty input gives an empty output.
• Inputs have at most 400 elements, and each element is at most 2,147,483,647, so doubling never overflows u32. (With this fan_in, lists longer than 445 elements hit the executor's 100,000-poll safety limit, which panics.)
• The starter already compiles and handles the empty input. For any non-empty input it returns an empty list. Your job is to find out why and fix it.

How a join handle works

A spawned task and its handle share one cell, Rc<RefCell<Shared<T>>>:

• spawn creates the cell, wraps the caller's future in an async move block that awaits it and stores the result in the cell, passes that wrapper to spawn_raw, and returns a JoinHandle that holds a second Rc to the same cell.
• JoinHandle::poll looks in the cell. If a value is there, it takes it and returns Poll::Ready(value). If not, it stores the waker from the current Context and returns Poll::Pending.
• When the task completes, the wrapper writes the value, takes the stored waker out of the cell, and calls wake on it.

That last step is one task waking another: the worker task finishes and schedules the collector task that is waiting on its handle. Many runtime features, such as channels, async mutexes and timers, are built from the same ingredients: shared state, a stored waker, and a wake when the state changes.

Which waker to keep

The documentation for Future::poll says that when a future is polled more than once, only the waker passed in the most recent call should be scheduled to receive a wakeup. A future cannot assume that every poll comes with the same waker.

The starter breaks that rule. It saves the first waker it sees and ignores every later one. fan_in exposes this on purpose: before the collector task exists, it polls every handle once using Waker::noop(), a waker that does nothing when woken. A handle that keeps only its first waker keeps that no-op waker. When the worker finishes, it wakes the no-op waker, so the collector is never put back on the ready queue. The queue empties, run returns, and the output is empty.

The early poll is artificial, but the situation it models is real. A future can be polled by one task and later moved into another task, or a combinator such as futures::stream::FuturesUnordered can give each inner future its own waker. In both cases the same future sees a different waker than it saw last time.

The simplest correct policy is to replace the stored waker on every pending poll. Waker::will_wake can be used to skip that clone: if it returns true, the stored waker is guaranteed to wake the same task. It works on a best-effort basis and may return false even for two wakers that would wake the same task, so it can serve only as an optimisation, never as a reason to keep an old waker when it returns false.

Order of operations at completion

Write the value first, then take the waker, then end the borrow, and only then wake:

let waker = {
    let mut shared = cell.borrow_mut();
    shared.value = Some(value);
    shared.waker.take()
};
if let Some(waker) = waker { waker.wake(); }

In this executor, wake only pushes an id onto a queue, so waking inside the borrow would happen to work. But a waker can run any code its implementer chose. If that code reached the same RefCell while the borrow_mut was still active, borrow_mut or borrow would panic because the cell is already mutably borrowed. With a std::sync::Mutex, locking again on the thread that already holds the lock never succeeds; it may deadlock or panic. Updating shared state under the borrow or lock, and acting on it after releasing it, avoids both problems.

Spawned tasks run without being awaited

The collector awaits its handles one at a time, yet the workers still run interleaved. That is because spawning puts a task on the ready queue immediately, and run polls it whether or not anything is awaiting its handle. A plain future that is never spawned does nothing until something polls it.

Real runtimes make different choices about what dropping a handle means. In Tokio, dropping a JoinHandle detaches the task, which keeps running. In the async-task crate (used by smol), dropping a Task cancels it. This exercise never drops a handle early, so it does not need either policy.