Async recursion, async closures, and streams

Repair the recursive async function, then trace the supplied closure and stream helpers. The starter already implements those helpers; its compile error comes from tree_sum awaiting itself without indirection.

pub fn run(tree: Vec<Vec<usize>>, x: u32, factor: u32, fail_first: u32, take: usize)
    -> (u64, u32, Option<u32>, Vec<u64>)

Expected results

The returned tuple contains four results, in this order:

1. Tree sum: add the indices of the nodes reached from root 0. An empty tree has sum 0; a tree containing only root 0 also has sum 0.
2. Apply twice: multiply x by factor, then multiply that result by factor again.
3. Retry: make at most three attempts. Attempts are numbered from 1. The first fail_first attempts return None; the next returns Some(attempt_number * 10). Stop at the first success. If all three fail, return None.
4. Stream: collect take values: 0 * factor, 1 * factor, and so on. With take == 0, return an empty vector without polling the inner stream.

Inputs contain either an empty tree or a valid, shallow tree rooted at 0. Every child index is in bounds, there are no cycles or repeated children, and all nodes belong to that tree. Inputs are small enough to collect in memory; all intermediate arithmetic fits its declared integer type. You do not need to validate malformed graphs or define overflow behavior.

For tree = [[1, 2], [], [3], []], x = 2, factor = 3, fail_first = 1, and take = 4, return (6, 18, Some(20), vec![0, 3, 6, 9]).

Break the recursive future's size dependency

A future must have a finite size. Directly awaiting another call to the same async function would require its future to contain another future of its own type. Rust rejects that recursion with E0733.

One repair is to change tree_sum into an ordinary function returning BoxFut<u64>, and put its body inside Box::pin(async move { ... }). The boxed pointer has a fixed size, so the recursive future no longer has to be stored inline. The existing alias also erases the future's concrete type.

Another valid repair keeps async fn and boxes the recursive call before awaiting it. Both forms are shown in Rust's E0733 explanation.

In the reference's boxed-return form, each visited node creates a boxed future. That is one per node visited, not one per tree depth in total. Only the current recursion path needs to remain active while its descendants are being processed. The cloned child vectors have their own allocation costs. Boxing fixes the type's size; it does not remove recursive polling depth or make arbitrarily deep traversal safe from stack exhaustion.

The reference clones each node's child list for convenient ownership. This is not a rule that all borrows must end before .await: borrowing this immutable, Rc-owned tree across an await can also be valid.

Read the async closure bounds

apply_twice awaits f(x), then awaits f again with the first result. Its AsyncFn(u32) -> u32 bound permits repeated calls through a shared borrow of the callable.

retry uses AsyncFnMut() -> Option<u32> because its callable may mutate captured state. Each call is awaited before the next begins. In the supplied async move closure, the captured attempt counter persists between calls. With zero allowed attempts, the general retry helper returns None without calling the closure; run always gives it three attempts.

Async closures and these callable bounds became stable in Rust 1.85. An async closure can lend access to its captures to the future from a call. In particular, AsyncFnMut can return a future borrowing the callable mutably until that call finishes.

A plain closure returning an async block is still useful when its future owns its data or borrows suitable external data. Its FnMut return type cannot, however, express a future borrowing the closure itself for the lifetime of each mutable call. Avoid treating every borrowing async closure as an error, or assuming older Rust could not express any lifetime-dependent future APIs.

Distinguish an item, a wait, and the end

The exercise defines its own SimpleStream trait using only the standard library. Its method has this shape:

fn poll_next(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<Self::Item>>

Ready(Some(value)) yields one item. Pending means the next result is not ready. Ready(None) signals completion, so the collector stops polling. In a stream that waits for external events, returning Pending also needs a way to wake the task when progress becomes possible. The supplied counter produces items immediately.

Map multiplies each yielded item and forwards Pending or completion. Take decrements its budget only when it receives an item. Once that budget reaches zero, it returns Ready(None) without polling its inner stream. If an inner stream ends earlier, the collector stops on that result too.

The adapters store a Pin<Box<dyn SimpleStream<Item = u64>>>. Moving that pointer does not move the pinned stream it owns. Together with their integer fields, this makes the supplied adapters Unpin, so the next helper can use Pin::new. Boxing is one design choice; an inline adapter can instead use suitable Unpin bounds or pin projection.

A regular for loop uses synchronous IntoIterator. Here, the collector awaits next(&mut stream) in a while let Some(value) loop instead.

Do not assume every stream returns None forever after completion. The futures Stream contract leaves subsequent polls unspecified within Rust's safety rules; a fused stream adds a repeatable completion guarantee. This exercise's Take repeats None after its budget runs out, but does not remember an early completion from an arbitrary inner stream. Its collector needs no further polls after either kind of completion.

Limits of the supplied runner

block_on repeatedly polls with a no-op waker and gives up after 100,000 pending polls. That is enough for these immediately progressing futures. It is a teaching helper, not an executor for timers, network I/O or general asynchronous work. Its poll limit also cannot interrupt recursion that never returns from a single poll.