This crate provides an implementation of stackful, first-class asymmetric coroutines in the Rust language.
The general notion of coroutines, first discussed in the published
literature by M. E. Conway [CACM 6 (1963), 396–408], extends the
concept of subroutines by allowing them to share and pass data and control
back and forth. A coroutine suspends execution of its program by invoking
the yield function, which returns control to the caller. Invoking the
resume method on a coroutine resumes execution of its program
immediately after the point where it was last suspended.
The Rust language has built-in support for coroutines, but one cannot easily suspend their execution from within a nested function call. One way to solve this issue is to maintain a separate program stack for each coroutine. This approach takes more memory space, but one can employ pooling techniques to diminish the need for large allocations and liberations.
The crux of this crate is the Coro type, which implements the built-in
core::ops::Coroutine trait. The most noteworthy feature of this library
is that it allows a coroutine to return control without the need to pass
a "yielder" object around. (It's easy to achieve this by carefully aligning
the program stack of a coroutine, so that we can deduce the location of a
control record from the current stack pointer value alone.) This approach
has the following disadvantage: the compiler can no longer prove that
yield is always called from a coroutine. Nevertheless, the function
will trigger a panic in the rare event that this invariant does not hold.
It may be of interest to note that this faulty-call detection mechanism can
slow down the action, because it needs to update a thread-local variable
during each transfer of control. Experienced programmers can disable the
safe_yield feature to skip the check, but we should mention that this
can lead to undefined behavior in purely safe code. Another potential
disadvantage of our implementation is that the program stacks of all
coroutines must have the same size.
See the paper "Revisiting Coroutines" by A. L. de Moura and R. Ierusalimschy [ACM TOPLAS 31 (2009), 1–31] for the definitions of "stackful", "first-class" and "asymmetric" used above.
This library incorporates ideas from two other implementations of stackful
coroutines: corosensei by A. d'Antras, and libfringe by edef1c.
Preliminary experiments seem to indicate that the three approaches can
transfer control between coroutines with comparable efficiency, but coro
is inferior with respect to platform support and stack unwinding. I put
together this library for my own education, so significant improvements
are possible.
As a typical example where coroutines are useful, we will write a program
that tests the similarity of two ordered trees. Formally speaking, a tree
is a finite set of nodes that consists of a root together with
use core::cell::Cell;
use core::ops::{Coroutine, CoroutineState};
use core::pin::Pin;
use coro::{Coro, yield_};
#[derive(Clone)]
struct Node {
children: Vec<Node>,
}
fn visit(root: &Node, m: &Cell<usize>) {
m.set(root.children.len());
yield_();
for ch in &root.children {
visit(ch, m);
}
}
fn similar(first: &Node, second: &Node) -> bool {
let m = Cell::new(0);
let m_prime = Cell::new(0);
let mut first_coro = Coro::new(|| visit(first, &m));
let mut second_coro = Coro::new(|| visit(second, &m_prime));
loop {
match (
Pin::new(&mut first_coro).resume(()),
Pin::new(&mut second_coro).resume(()),
) {
(CoroutineState::Complete(_), CoroutineState::Complete(_)) => return true,
(CoroutineState::Yielded(_), CoroutineState::Yielded(_)) if m == m_prime => {}
_ => return false,
};
}
}