Project 4: Coroutines

The feature the introduction excluded, and the reason it was excluded: a coroutine turns one call stack into many, which is a change to the machine rather than an addition to the instruction set.

Effort: a week. Value: it is the clearest demonstration in the curriculum that some features are structural.

Why It Was Deferred

Everything else in Section 4 added an opcode or an object. Coroutines add a second VM state:

   BEFORE                              AFTER
   ┌─────────────────────┐             ┌─────────────────────────────────────┐
   │ Vm                  │             │ Vm                                  │
   │   stack:  Vec<Value>│             │   coroutines: Vec<Coroutine>        │
   │   frames: Vec<Frame>│             │   current: usize                    │
   │   heap                            │   heap        ← SHARED              │
   └─────────────────────┘             │   globals     ← SHARED              │
                                       └───────────┬─────────────────────────┘
                                                   │
                                       ┌───────────▼─────────────┐
                                       │ Coroutine               │
                                       │   stack:  Vec<Value>    │  ← its OWN
                                       │   frames: Vec<Frame>    │  ← its OWN
                                       │   open_upvalues         │  ← its OWN
                                       │   status: Suspended|... │
                                       └─────────────────────────┘

Three things become per-coroutine and three stay shared, and getting that split right is the design.

The API

local co = coroutine.create(function(a, b)
  local c = coroutine.yield(a + b)      -- suspends; `c` is what resume() passes back
  return c * 2
end)

print(coroutine.resume(co, 1, 2))       -- true  3
print(coroutine.resume(co, 10))         -- true  20
print(coroutine.resume(co))             -- false  cannot resume dead coroutine
print(coroutine.status(co))             -- dead

Plus coroutine.wrap, coroutine.isyieldable, and coroutine.running.

yield returning a value is the part that makes this hard. It is a suspension point in the middle of an expression, and the VM must be able to stop there and resume with a value on the stack.

What Makes It Hard

1. Yielding across a native boundary

local co = coroutine.create(function()
  table.sort(t, function(a, b) return coroutine.yield(a < b) end)   -- ???
end)

The yield is inside a script comparator, called from a native table.sort, called from the script. To suspend, you would have to unwind and later restore Rust stack frames — which Rust cannot do.

Lua's answer: yielding across a C boundary is an error, unless the C function was written with continuation support (lua_callk/lua_yieldk, added in 5.2). Ember's answer should be the same, plus a clear error message:

error: attempt to yield across a host-function boundary
  in function 'table.sort'
help: `yield` cannot suspend Rust frames. Move the yield outside the sort, or
      use a comparator that does not yield.

That error, with that help line, is worth more than a heroic implementation.

2. Upvalues are per-coroutine

Each coroutine has its own stack, so each has its own open-upvalue list. A closure created in coroutine A capturing A's local has an upvalue pointing into A's stack — and if B resumes and closes upvalues, it must close its own. Mixing the lists is a corruption bug with no error.

3. GC roots multiply

Root set 1 and 2 become "the stack and frames of every coroutine, including suspended ones". A suspended coroutine's stack is fully live. Miss it and resuming reads freed objects.

The root count goes from nine to nine-with-a-loop, and enumerate_roots must iterate coroutines.

4. Limits

Does the instruction budget belong to the engine or the coroutine? Engine — otherwise a script spawns coroutines to multiply its budget. But the call-depth limit is per-coroutine, because each has its own frame stack. Two limits, two scopes, and getting it backwards is a sandbox hole.

What You Build

#![allow(unused)]
fn main() {
pub struct Coroutine {
    stack: Vec<Value>,
    frames: Vec<CallFrame>,
    open_upvalues: Vec<GcRef<Upvalue>>,
    status: CoStatus,          // Suspended | Running | Normal | Dead
    resume_depth: usize,       // for `coroutine.running` and error messages
}

pub enum CoStatus { Suspended, Running, Normal, Dead }
}

The VM loop gains one thing: resume and yield switch which coroutine self.current points at and return control to the outer resume's caller. Because the frames are data rather than Rust stack frames — exactly what Section 3 bought — this is a pointer swap, not a stack unwind.

That is the payoff for making frames data, and it is worth pausing on: coroutines are nearly impossible in the tree walker and straightforward in the VM, for one structural reason.

Deliverables

  • Coroutine with its own stack, frames, and open-upvalue list.
  • create, resume, yield, status, wrap, isyieldable, running.
  • Yielding across a host boundary is a clear error with a help line.
  • enumerate_roots iterates every coroutine; corpus green under --gc-stress.
  • Instruction budget is engine-wide; call depth is per-coroutine. Both tested, including the "spawn coroutines to multiply the budget" attack.
  • Differential tests green — the tree walker cannot do this, so coroutine tests are VM-only and must be marked as such in the harness. That is the first time the corpus splits, and it deserves a comment explaining why.
  • Golden tests: a generator, a producer/consumer pair, and an iterator built on wrap.
  • ADR-018, and a docs/limitations.md update removing "no coroutines".

Where to Read

rg -n 'lua_resume|lua_yieldk|luaB_coresume|lua_State' ldo.c lcorolib.c lstate.h
  • Lua's lcorolib.c and ldo.c — lua_resume and lua_yieldk. Note that in Lua a coroutine is a lua_State: the same structure as the main thread, which is why the split above looks the way it does.
  • Lua 5.4 Reference Manual §2.6 (coroutines) and §4.7 (the C API's continuation functions).
  • PUC-Rio's paper "Coroutines in Lua" (Moura, Rodriguez & Ierusalimschy) — the design rationale, including why asymmetric coroutines.
  • Rust's Generator/Coroutine unstable feature, for the contrast: what the host language's version of this problem looks like.

Validation / Self-check

  1. What becomes per-coroutine and what stays shared? Why that split?
  2. Why can you not yield across a native boundary? What is Lua's answer, and what should the error say?
  3. Why does each coroutine need its own open-upvalue list?
  4. Which limit is per-engine and which is per-coroutine? What attack does getting it backwards enable?
  5. Why are coroutines straightforward in the VM and nearly impossible in the tree walker?
  6. What happens to the differential test suite, and how did you handle it?
  7. In Lua, a coroutine is a lua_State. What does that tell you about Lua's design?

Next: Project 5 — A Source Debugger.