::next_gen
Safe generators on stable Rust.
Examples
Reimplementing a range
iterator
use *;
mk_gen!;
assert_eq!;
Implementing an iterator over prime numbers using the sieve of Eratosthenes
use *;
/// Generator over all the primes less or equal to `up_to`.
mk_gen!;
for prime in primes
Defining an iterator with self-borrowed state
This is surely the most useful feature of a generator.
Consider, for instance, the following problem:
'_ +
Miserable attempts without generators
No matter how hard you try, without using unsafe
, or some other
unsafe
-using self-referential library/tool, you won't be able to feature such
a signature!
-
The following fails:
'_ +
error: cannot return value referencing local variable `locked_elems` -/lib.rs:122:5 | 11 | / from_fn | |______^ returns a value referencing data owned by the current function | = help: use `.collect ` to allocate the iterator
-
as well as this:
'_ +
error: cannot return value referencing local variable `locked_elems` -/lib.rs:144:5 | 11 | / from_fn | |______^ returns a value referencing data owned by the current function | = help: use `.collect ` to allocate the iterator error: cannot move out of `locked_elems` because it is borrowed -/lib.rs:147:9 | 8 | | - let's call the lifetime of this reference `'1` ... 11 | / from_fn | |______- returning this value requires that `locked_elems` is borrowed for `'1` error: aborting due to 2 previous errors
-
Such as when that
Set
would be aVec
instead. In that case, we can use indices as a poorman's self-reference, with no "official" lifetimes and thus Rust not complaining:'_ + let mutexed_elems = new; let mut iter = iter_locked; assert_eq!; assert_eq!; assert_eq!;
But with generators this is easy:
use *;
and voilà!
That #[generator] fn
is the key constructor for our safe self-referential
iterator!
Now, instantiating an iterator off a self-referential generator has a subtle
aspect, muck alike that of polling a self-referential Future
(that's what a
missing Unpin
bound means): we need to get it pinned before it can be polled!
-
Getting a
Future
:let future = async ; // or let future = some_async_fn;
-
Pinning an instantiated
Future
in the heap (Box
ed):// Pinning it in the heap (boxed): let mut pinned_future = Box pin // or, through an extension trait (`::futures::future::FutureExt`): let mut pinned_future = future.boxed // this also incidentally `dyn`-erases the future.
-
Now we can return it, or poll it:
if true // and/or return it: return pinned_future;
-
-
Pinning an instantiated
Future
in the stack (pinned to the local scope):use some_pinning_macro as stack_pinned; // Pinning it in the "stack" stack_pinned!; /* the above shadows `future`, thus acting as: let mut future = magic::Stack::pin(future); // */ // Let's rename it for clarity: let mut pinned_future = future;
-
Now we can poll it / use it within the current stack frame, but we cannot return it.
pinned_future.as_mut.poll
-
Well, it turns out that for generators it's similar:
-
Once you have a
#[generator] fn
"generator constructor"use *;
-
Instantiation requires pinning, and thus:
-
Stack-pinning: cheap,
no_std
compatible, usable within the same scope. But it cannot be returned.mk_gen!; // can be used within the same scope assert_eq!; assert_eq!; // but it can't be returned // return generator; /* Error, can't return borrow to local value */
-
Heap-pinning: a bit more expensive, requires an
::alloc
ator or not beingno_std
, but the so-pinned generator can be returned.mk_gen!; // can be used within the same scope if some_condition // and/or it can be returned return generator; // OK
-
So, back to our example, this is what we need to do:
use *;
/// We already have:
...
/// Now let's wrap-it so that it yields a nice iterator:
'_ +
let mutexed_elems = new;
let mut iter = iter_locked;
assert_eq!;
assert_eq!;
assert_eq!;
-
If the
iter_locked()
function you are trying to implement is part of a trait definition and thus need to name the type, at which point theimpl '_ + Iterator…
existential syntax can be problematic, you can then usedyn
instead ofimpl
, at the cost of having to mention thePin<Box<>>
layer:// instead of '_ + // write:
use *; ; assert_eq!;
Resume arguments
This crate has been updated to support resume arguments: the Generator
trait
is now generic over a ResumeArg
parameter (which defaults to ()
), and its
.resume(…)
method now takes a parameter of that type:
let _: = generator.as_mut.resume;
this makes it so the yield_!(…)
expressions inside the generator evaluate to
ResumeArg
rather than ()
:
let _: ResumeArg = yield_!;
Macro syntax
In order to express this using the #[generator]
attribute, add a
resume(Type)
parameter to it:
use *;
type ShouldContinue = bool;
mk_gen!;
assert!;
assert!;
assert!;
assert!;
assert!;
If you don't want to ignore/disregard the first resume argument (the "start
argument" we could call it), then you can append a as <binding>
after the
resume(ResumeArgTy)
annotation:
use *;
type ShouldContinue = bool;
-
use *; /// A silly recursive function, computing the sum of integers up to `n`. /// /// If you know your math, you know this equals `n * (n + 1) / 2`. /// /// This result is quite "obvious" from the geometric representation: /// /// ```text /// # . . . . . <- Amount of #: 1 /// # # . . . . <- Amount of #: 2 /// # # # . . . <- Amount of #: 3 /// # # # # . . <- Amount of #: 4 /// ⋮ … ⋱ ⋮ /// # # # # # # <- Amount of #: N /// Height = N + 1 Total: 1 + 2 + … + N /// Width = N /// Half the area of the "square": (N + 1) * N / 2 /// ``` /// /// As you can see, computing the sum `1 + 2 + 3 + … + N` is the same as /// counting the number of `#` in that diagram. And those `#` fill half a /// "square". But it's actually not exactly a `N x N` square since we have /// from `1` to `N` rows, that is, `N + 1` rows, and a width of `N`. /// /// This results in `(n + 1) * n` for the area of the "square", followed by /// the `/ 2` halving operation. const N: u64 = 10_000; assert_eq!; // where the `drive_recursion` "runtime" is defined as: /// A recursive computation can be seen as a "suspensible coroutine", /// whereby, when needing to "compute-recurse" into new inputs, /// that current computation just suspends and yields the new input /// for which it requests a computation. /// /// The driver / "executor", thus starts with the initial input, and /// polls the suspensible coroutine until reaching a suspension point. /// /// Such suspension point gives the driver a new computation it needs to /// perform (updates `input`), and a new "customer" waiting for that new /// result: that suspended computation. These stack onto each other as /// we recurse, and when the innermost computation _completes_ / _returns_ /// rather than yield-enqueuing a new one, we can then feed that result to /// the top-most suspended computation, _resuming_ it.
The "stacks" (storage for the local variables captured within non-terminal / non-tail recursive calls) are thus, in practice, state that crosses the
yield_!()
points, resulting in state captured by theGenerator
. And since theGenerator
instance isBox
ed, it means such stack ends up in the heap, behind a pointer. This happens for each and every recursion step.This means that the stack has successfully been segmented (within each
Generator
instance) into the heap; which is otherwise a cumbersome manual process that is nonetheless needed for non-trivial recursive functions.
Features
Performance
The crate enables no-allocation generators, thanks the usage of stack pinning. When used in that fashion, it should thus be close to zero-cost.
Ergonomics / sugar
A lot of effort has been put into macros and an attribute macro providing the most ergonomic experience when dealing with these generators, despite the complex / subtle internals involved, such as stack pinning.
Safe
Almost no unsafe
is used, the exception being:
-
Stack pinning, where it uses the official
::pin_utils::pin_mut
implementation; -
Using the pinning guarantee to extend a lifetime;
no_std
support
This crates supports #![no_std]
. For it, just disable the default "std"
feature:
<!-- AUTOGENERATED FILE -->
```toml
[]
= "..."
= false # <- ADD THIS to disable `std`&`alloc` for `no_std` compat
= [
"alloc", # If your no_std platform has access to allocators.
# "std", # `default-features` bundles this.
]
Idea
Since generators and coroutines rely on the same internals, one can derive a
safe implementation of generators using the async
/ await
machinery, which
is only already in stable Rust.
A similar idea has also been implemented in https://docs.rs/genawaiter.