This crate provides an implementation of first-class stackful asymmetric coroutines.
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. An asymmetric coroutine suspends the
execution of its program by invoking a suspend 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 asymmetric 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, at the expense of some extra memory space. The resulting coroutine implementation is said to be stackful.
The crux of this crate is the Coro type, which implements the
built-in core::ops::Coroutine trait using a stackful approach.
Perhaps its most interesting feature is that it allows a coroutine
to return control without the need to pass a "yielder" object around.
(Instead, a thread-local variable keeps track of the currently active
coroutine.)
The paper "Revisiting Coroutines" by A. L. de Moura and R. Ierusalimschy [ACM TOPLAS 31 (2009), 1–31] formally defines the terms "stackful", "first-class" and "asymmetric" used above.
coro incorporates ideas from two other implementations of stackful
coroutines: corosensei by Amanieu d'Antras, and libfringe by edef.
Preliminary experiments seem to indicate that the three libraries can
transfer control between coroutines with comparable efficiency, but
coro is still inferior with respect to platform support. I mainly
put together this library for my own education, so significant
improvements are likely possible.
As a typical example of the use of coroutines, let us consider
the problem of determining whether two ordered trees are similar.
Formally speaking, a tree is a set of nodes that consists of a
root together with
#![feature(coroutine_trait)]
use core::cell::Cell;
use core::ops::CoroutineState;
use coro::{suspend, Coro};
struct Node(Vec<Node>);
fn similar(t: &Node, tp: &Node) -> bool {
let (m, mp) = (Cell::new(0), Cell::new(0));
fn visit(root: &Node, m: &Cell<usize>) {
m.set(root.0.len());
suspend();
for child in &root.0 {
visit(child, m);
}
}
let mut t_coro = Coro::new(|| visit(t, &m));
let mut tp_coro = Coro::new(|| visit(tp, &mp));
loop {
match (t_coro.resume(), tp_coro.resume()) {
(CoroutineState::Complete(_), CoroutineState::Complete(_)) => return true,
(CoroutineState::Yielded(_), CoroutineState::Yielded(_)) if m == mp => {},
_ => return false,
}
}
}