#recursion #stack #future #helper #iterative #async #reference

unrecurse

Helper crate for rewriting your recursive code in iterative way

1 unstable release

0.1.0 Apr 6, 2022

#2044 in Data structures

MIT license

55KB
664 lines

Unrecurse

Get rid of the recursion in your rust code.

License

MIT


lib.rs:

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

Dependencies

~1MB
~15K SLoC