Crate unrecurse

Unrecurse

This is in prototype state As far as author knows the general idea is sound and even passes miri. but there are still a lot of rough edges internally and in public api.

Helper to convert recursive approach into iterative.

This crate consists from following main parts.

• RefStack struct for direct and granular access to stack. But only supports references for now.
• run to be able to store a struct that references previous element on stack.
• run_async to rewrite async recursion without recursion/macros/allocating every future
• run_async_backref if you have async recursion where current stack frame contains references to previous one

The most simple method to use is run_async(_backref). You can just convert your current recursive function into async fn. Add Recursion/RecursionContext parameter. Use it to invoke recursion and voila. It still looks like a recursion so it is still easy to reason about it but internally it uses async machinery to execute everything sequentially using a dedicated stack for current state. But currently quite often futures in rust are not very optimized. So if generated future is too big you might want to resort to the run function which allows you to create your own state to store in internal stack.

MSRV: 1.60

Structs

Checked

Marker to indicate that RecursionChecked has been consumed. Created by RecursionChecked::into_return.

Data

Reference to outer data to access from recursive future.

ForceFutureSend

Workaround for a compiler bug

Lifetime

Type that represents associated lifetime in WithLifetime::Lifetime

RecursionContext

Helper struct to invoke async recursion with references to previous state

RecursionFuture

Future returned from RecursionContext::recurse

RefStack

With this struct you can save full state of current iteration including references so that when you pop that state back you now have full context available as if you just returned from the function call. Basically you just push current state into RefStack and then pop back when you need to return to that state. Exactly what compiler does with regular call stack when you do recursive call. And what RefStack does is sound precisely for that reason, it just emulates what compiler already does just in a dedicated structure.

Enums

Action

Indicates what action should be performed on stack afterwards

Traits

AsyncFnMut2

Helper trait to be able to use HRTBs with async closures

AsyncFnMut3

Helper trait to be able to use HRTBs with async closures

WithLifetime

Trait to be able to apply HRTBs to arbitrary types Can be safely implemented by users for their own types. Soundness is ensured by the sealed Check trait which is implemented in a way that allows only correct WithLifetime implementations.

Functions

run

Used to rewrite post order processing of recursive data structures in iterative way. Struct that you want to use as a current state must implement WithLifetime properly.

run_async

Function to invoke async recursion without Boxing every future. Often you can already rewrite your async recursion with futures::stream::unfold. But it has some limitations, run_async on the other hand has exactly same capabilities as a regular async recursion. You can also use it as a simpler version of run.

run_async_backref

Same as run_async but allows to run recursion where current state/future has references into previous one.

run_async_backref_with_data

Version of run_async_backref that supports additional data to pass into

run_async_blocking

Shorthand for futures::executor::block_on(run_async()) if you want to rewrite regular recursion using async one

run_async_with_data

More capable version of run_async.

Type Definitions

Recursion

Helper struct to invoke async recursion