Cone Language Reference

Generators: writing your own

On this page

You want to hand out a sequence whose walk has a shape: a tree in order, a search that recurses, loops inside loops. A cursor written by hand (Being walked: next) keeps its place in its fields, so everything about where the walk has got to must be saved there between calls of next, and a recursive walk needs a stack of its own. A generator lets you write the walk as the loop or the recursion it is: a function declared yields, which hands out each value with yield, and the compiler builds the cursor and its next for you. Functions introduced generators; this recipe has the rest: handing on another generator's values, generator methods, generic generators, generators across packages, what may be borrowed across a yield, and when a generator dies. Here a tree kept in an array is walked in order:

mod treewalk;

import stdio use *;

// A sorted tree kept in an array: each node holds the index
// of its left and right child, or -1 for none
struct Node {
  pub val i64;
  pub left i64;
  pub right i64;
}

// Hands out the nodes in order, smallest first
fn inorder(nodes &Array[Node], at usize) yields &Node {
  let n = &nodes[at];
  if n.left >= 0 { yield each inorder(nodes, usize.from(n.left)); }
  yield n;
  if n.right >= 0 { yield each inorder(nodes, usize.from(n.right)); }
}

fn main() {
  //            50
  //          /    \
  //        30      70
  //       /          \
  //     20            80
  let nodes = [new Node(50, 1, 2), new Node(30, 3, -1), new Node(70, -1, 4),
               new Node(20, -1, -1), new Node(80, -1, -1)];
  each n in inorder(&nodes, 0) {
    print <- n.val, " ";
  }
  print <- "\n";
}

It prints:

20 30 50 70 80

Try this: swap the two yield each lines, and predict the order the nodes come out in.

The walk reads as the definition of "in order": everything on the left, then the node, then everything on the right. yield each hands on every value of the walk of a subtree, and the recursion keeps track of where the walk has got to, as recursion does, with nothing saved by hand. The tree's nodes are handed out as borrowed references, &Node, so none is copied.

What a generator is#

Note: Generators are built: a function declared yields, with yield and yield each, among a module's functions or as a method of a struct, generic or not. A generator may not be inline, have a where clause, or be a method of a trait, an enum, an actor or a type that declares an invariant lifetime. Two-way yield is an idea that is not built.

A generator is a function that hands its caller values one at a time. It runs until it reaches a yield, gives the caller the value written there, and waits. When the caller asks for the next value it goes on from that yield, with its local variables as they were. It is a function whose result is a sequence, written as the loop that makes the sequence, and what it gives back is an Iterator:

fn count(n i64) yields i64 {
  var i = 0i64;
  while i < n {
    yield i;
    i = i + 1i64;
  }
}

After yields comes the type of each value handed out. Calling count(4i64) runs nothing. It gives a value that holds the parameters, and every call of its next runs the body up to the next yield. next gives Some(value) for each value handed out and None once the body ends, by its last statement or by a return, which takes no value:

var g = count(4i64);
while true {
  match g.next() {
    case let v Some { print <- v, " "; }         // 0 1 2 3
    case is None { break; }
  }
}

each x in count(4i64) { print <- x, " "; }        // the same, 0 1 2 3

A loop that leaves early, by break or return, leaves the generator suspended, and it dies there (When a generator dies).

The value a generator gives is a struct made for it, of a type no source names; a message that has to spell it writes count.Gen. Since no source can write that type, a function cannot declare a generator as its result, nor a struct as a field. It is a move type: it is moved, not copied (Moves), so two walks of one generator never run. Having next(self &mut) Option[i64], it complies with core's Iterator[i64] as any cursor does, so it is passed to generic code bounded by that trait, or lent as a virtual reference, and the iterator adapters take it as they take any cursor: count(5).map(x => x * 2).sum() is 20.

fn sum[S Iterator[i64]](s &mut S) i64 {
  var t = 0i64;
  each v in s { t = t + v; }
  t;
}

var g = count(4i64);
sum(&mut g);         // 6

A yield is a statement of its own. It stands in a block, or in the arms of an if or match written as statements, and in a loop, but not inside an expression: f(a(), if c { yield 1; 2; } else { 3; }) would have to keep the value of a() across the wait, and is refused (Error 1350: A 'yield' is a statement of its own, not part of an expression). Compute it into a variable first.

Yielding another generator's values#

yield each hands on every value of another generator, or of anything with a next, in turn, and goes on when they are all handed on. It joins sequences, and it makes a recursive walk as short as the recursion, as inorder showed above:

fn joined(a i64, b i64) yields i64 {
  yield each count(a);
  yield 99;
  yield each count(b);
}
// joined(2i64, 2i64) hands out 0 1 99 0 1

The generator being handed on is kept in the one that hands it on, in its own storage, when its size is known. A generator that hands on one of its own kind, as inorder does, would have to hold itself, so that one is kept on the heap, one for each yield each that needs it, made when the walk begins and freed when the generator dies. A value handed on is the sub-generator's own Some(value): it is moved up, not copied. Each value costs a step through every generator that hands it on.

Generator methods#

A method may be a generator, called as any method is. In its body self is the receiver, exactly as in any method. The generator holds the receiver as it holds a parameter, so what the receiver was lent as stays lent for as long as the generator lives:

struct Tree {
  nodes Array[Node, 3];

  fn walk(self &) yields &Node {            // in order
    yield each self.from(0);
  }

  fn from(self &, at usize) yields &Node {
    let n = &self.nodes[at];
    if n.left >= 0 { yield each self.from(usize.from(n.left)); }
    yield n;
    if n.right >= 0 { yield each self.from(usize.from(n.right)); }
  }
}

each n in tree.walk() { print <- n.val, " "; }
  • A receiver borrowed with self & may be read, not changed, while the generator may still be resumed; one borrowed with self &mut may be neither read nor changed. The generator may change what it was lent, and may hand out borrows of it, yields &mut i64 among them. The borrow lasts until the generator dies, not until it is last called: a block around the generator ends it.
  • A receiver taken by value, fn run(self) yields i64, moves into the generator and dies with it, after its locals. As with any parameter, the body may borrow or copy it (and change it, if declared var self), not move it out.
  • Self in the body is the type the method belongs to.
  • A bare name that is a field of the receiver's type means self.name, as it does in any method, unless a local or a parameter of the generator is named so, which shadows it. A bare name of a method of the type is refused: write self.name().
  • A function of a type with no receiver, fn range(from i64, to i64) yields i64, is a generator too, called as Span.range(3, 7).

The method that makes the generator is the one written; the struct that is the generator is made beside the type and has no name in source (a message spells it Tree.walk.Gen). A method of a trait or of an enum cannot be a generator, since a trait's methods are copied into each type that implements it and an enum's into each of its variants; nor can an actor's, or a method of a type that declares an invariant lifetime (below). Write a function that takes what the method would.

Generic generators#

A generator may be generic, a function over a type or a method of a generic type or both (Generics). The struct that is the generator takes the type parameters, with their bounds as written, so each use is a generator of its own kind, made for the types it was called with, and checked as any generic is, where it is used:

fn items[T](l &List[T]) yields &T {
  each x in l.iter() { yield x; }
}

each x in items(&ints) { print <- *x, " "; }      // a generator over i64s

A generic generator may hand on another, itself included, with yield each, and a recursive one keeps its sub-generator on the heap in each instance as a plain one does. A type parameter of a generator does not name lifetimes ([T + 'a]) yet.

A generator may be a method of a type with lifetimes, such as a View['a] that borrows what it shows, with a receiver of self &, self &mut or by value. The generator takes the type's lifetimes and one of its own, so it may not outlive the receiver or anything it borrows. It holds the receiver, so it holds what the receiver borrows as well as what the receiver was lent: neither may be changed, and neither may die first, while the generator lives.

struct View['a] {
  pub r &'a i64;
  fn twice(self &) yields i64 { yield *r; yield *r; }
}

let x = 4i64;
let v = new View(&x);
each k in v.twice() { print <- k, " "; }   // 4 4

Not built yet: a generator method on a type with an invariant lifetime ('=a), or one that writes a lifetime in its own signature (1352).

Generators across packages#

A pub generator of a package, a function, a method or a method of a generic type, can be walked from another package as it is from its own. The struct that is the generator, and the frame that holds its locals across a yield, are made from its body, so the package's include file carries the generator's declaration whole, as it carries an inline or a generic function, and the importer makes the struct again from it. What the body names in the package, a private type, a private function or another private generator, is declared beside it and exported. A generator that is not pub stays inside the package, unless a body the include file carries names it; neither it nor the private names only it uses are in the file, and no other package can name them.

Borrows across a yield#

A yield leaves the body, and the generator, a value, may be moved by its caller before it is resumed. What the body keeps across a yield is held in the generator's value, so:

  • A borrow of what the generator was lent, a parameter that is a reference, lasts across it. So does a copy of any value.
  • A borrow of one of the body's own local variables, or of a parameter the generator holds by value, does not last: it ends at the yield, and it is an error to use it after. The error names the yield.
  • What a yield hands the caller may borrow only what the generator was lent, as items above hands out borrows of the list. It is a borrow of that, not of the generator, so a caller may keep a value handed out for as long as the generator lives, several of them at once.
  • So the body holds each borrow it has handed out, from the yield to the end of the body, as if a variable of its own held it. It may go on reading what it lent, or change another part of it, but it may not change the thing the borrow points into, or call anything that could change the shape of the collection it points into (a push or a clear on a list). The error is at the change. Copy the value to hand it out, or hand out the borrow once the body has done changing what it borrows.
fn grows(xs &mut List[i64]) yields &i64 {
  yield xs[0usize];
  xs.push(1i64);   // ERROR 1339: the caller may still hold the borrow just yielded,
                   // and the push could move the list's elements
}

fn bad(k i64) yields i64 {
  var x = 5i64;
  let r = &x;
  yield k;         // ERROR 1168: r borrows a local, which cannot last across this yield
  yield *r;
}

The parameters are held in the generator, and the body names them as a method names its fields. It may borrow or copy one, or change one declared var, but it may not move one out. A parameter lives as long as the generator does, not as long as the body, and dies after the locals. A parameter may be called anything but self: its name never clashes with a method the generator has, so a generator may take a parameter called count or map and still be counted and mapped.

When a generator dies#

The locals of the body die as they would in a function, in the order they were declared, last first, where the body ends. A generator that dies while it waits at a yield finalizes the locals it holds there, in the same order, and then its parameters. One never run holds only its parameters. A local moved on some paths only is finalized only if it still holds its value, as anywhere (drop flags).

You can now write a sequence as the loop or the recursion that makes it, hand it out by value or by borrow, and know what it may hold across each yield and when it dies. That ends the recipes. Next comes the standard library, whose collections and cursors are built from the same methods and generators.