Cone Language Reference

Regions and owning references: new and Uni

On this page

A local variable lasts as long as its block, and a borrow no longer than what it borrows. A value that must outlive the function that made it, a node in a tree, a record kept for later, needs memory of its own, and something to decide when to give it back. In Cone that something is a region, and each region is one of the strategies from the opening tour. This page covers what every region shares: allocating with new, the owning reference you get back, and when a value is freed, with the simplest region, the single owner Uni. Afterwards you can build data that lives as long as you need:

mod tree;

import stdio use *;

// Each node owns its children through a single owner, Uni
struct Node {
  pub value i32;
  pub left Option[Uni[Node]];
  pub right Option[Uni[Node]];
  fn final(self &uni) { print <- "free ", value, "\n"; }
}

// new allocates a node that outlives this function: its owner is returned
fn node(v i32, left Option[Uni[Node]], right Option[Uni[Node]]) Uni[Node] {
  new Uni[Node](v, left, right);
}

fn leaf(v i32) Option[Uni[Node]] {
  Some(node(v, None[Uni[Node]], None[Uni[Node]]));
}

// Borrows a node: it works whatever owns it
fn sum(n &Node) i32 {
  var total = n.value;
  if let l Some = &n.left { total += sum(*l); }
  if let r Some = &n.right { total += sum(*r); }
  total;
}

fn main() {
  let root = node(1, leaf(2), leaf(3));
  print <- "sum: ", sum(root), "\n";
}                          // root's owner goes: the whole tree is freed

It prints:

sum: 6
free 1
free 2
free 3

Try this: give two parents the same child: let four = leaf(4); and then node(1, four, four). A single owner moves, so the compiler refuses the second four: This variable's value has been moved out. A child shared by two parents needs a region that allows several owners, reference counting, next.

sum takes a borrowed reference, and with *l each owner lends what it owns. That is the payoff of borrowing first: code that takes a borrow works the same whatever region the value lives in, single owner, counted, collected or in an arena, and pays none of that region's costs inside it. Most of a program's functions can be written that way, and only the code that makes and keeps values needs to know where they live.

What a region is#

Global variables sit at fixed addresses chosen when the program is linked. Local variables come and go on a stack, last in, first out, one stack for each thread. Neither suits a value made at run time that must survive the scope that made it. That needs the heap, the large pool of memory outside the globals, the code and the stacks.

Cone divides the heap into regions. Each region has its own strategy for allocating memory and for taking it back, and every value on the heap lies wholly within one region, which governs it. Because no one strategy is right for every value (The strategies, and what each costs), a program chooses, for each value it allocates, the region whose strategy suits the way the value will be used.

A few words keep the rest of this part precise:

  • A region is the part of memory managed by one region's rules. Every point in memory is managed by exactly one region: the global region is the memory the linker sets up, the local region is a thread's stack, and every other region is memory owned and managed by the region that allocated it.
  • Regions nest. Each piece of memory has exactly one immediate manager, and managers stack: an Rc allocation holds a List's block, and inside that block the List manages its elements.
  • A static region's state and life are global, kept by a module: a tracing collector's heap, say. A dynamic region's state is a value, and the region lives as long as that value does: an arena, a pool, a collection.
  • A region ref is what an owning reference's type names, Rc in Rc[mut, Node]: a struct declaring the built-in trait RegionRef, which is the bookkeeping a region keeps in front of each value it manages, and whose methods the compiler calls at each event in a reference's life (Making your own region). The region itself is the module, or for a dynamic region the value, behind it.
  • Between them, the region decides when a value dies, and the compiler runs the death, since only the compiler knows the value's type: the value's final, then its fields' finalizers, then the owners its fields hold, then the region's free.

A region gives out two kinds of reference:

  • Owning references. Allocating a value in a region gives back an owning reference to it. Some regions allow copies of it, which are owning references too. Whatever the strategy, the region frees the value only when its last owning reference is gone, so an owning reference is always safe to use, and a value is freed exactly once.
  • Weak references, which point at a value that may or may not still exist, and must be checked before use.

Allocating a value: new#

Like every construction, an allocation begins with new. What follows is the type of owning reference wanted back:

let node = new Rc[mut, Node](1);
  • The region ref names the region that allocates the value and manages its life: here Rc, which counts references. It may be Rc or Uni from core; the sync package's Arc, an Rc whose count several threads may change at once; the collector package's garbage-collected Gc (discouraged, single threaded and outside actors only); the rcweak package's Rcw; or any region ref of your own, a struct declaring is RegionRef (Making your own region). The region ref's methods, and whether it declares Move, decide when a value is freed; its finalizer runs just before (finalizers).
  • The permission says what the reference may do. It can be a static permission or a lock permission, and with none written it is uni.
  • The value type is the type of the value allocated: here a Node.

The parentheses hold the arguments of the value's initializer, chosen as for any construction: here Node's implicit initializer, which takes its fields in order. Empty parentheses may be left off. What comes back is an owning reference of the type written, Rc[mut, Node].

A value of no size cannot be allocated: there is no owning reference to a value of an empty struct, new Uni[Empty]() (Error 1013: May not allocate a value of abstract or zero-size type).

Allocating a finished value#

The parentheses may instead hold one finished value of the value type, which is moved into the new allocation, as though every type had an initializer taking a finished value of itself. A value no initializer constructs, a number, an array, a tuple, an enum or its variant, a reference, is always allocated this way, and its allocation takes exactly one value, converted to the value type as a variable's initial value is: a number literal takes on the value type, and an enum's variant becomes its enum:

let count = new Rc[u64](5);                            // the literal is a u64
let grid = new Rc[mut, Array[i32, 3]]([1, 2, 3]);
let pair = new Uni[(i32, f32)]((1, 2.0));
let maybe = new Uni[Option[i32]](Some(3));
let name = new Arc[imm, String](String.from("x"));     // a call's result
let list = new Rc[mut, List[Fin]](items);              // items is moved in

A struct's allocation is told apart by type: when exactly one argument is given and its type is the struct itself (through an alias as well), it is the finished value, moved in, and no initializer runs; otherwise the arguments go to the struct's initializers, as for any construction. A reference to the struct, or a value that would only convert to it, is not the struct itself:

let s = new Seeded(4);                  // Seeded's init runs
let byInit = new Rc[Seeded](5);         // Seeded's init runs again, on 5
let moved = new Rc[Seeded](s);          // s is moved in; no init runs

A value is constructed once: new Point(p), where p is already a Point, is refused (Error 1227: This is already a value of Point, which needs no construction: use it as it is, or allocate it with 'new R[perm, Point](value)').

An alias of an owning reference type allocates the same way, so a program that names its reference type once writes its allocations with that name. And to make a virtual reference, allocate the concrete type and let the reference coerce where the virtual one is wanted:

alias Node = Gc[mut, NodeValue];
let leaf = new Node(1);                             // a Gc[mut, NodeValue]
let shape Rc[mut, Shape] = new Rc[mut, Circle](5);  // Shape a trait, Circle a struct that is one

Allocating with contents#

An allocation takes contents after <-, as a value's construction does (the send operator). An array's contents fill it in the region's memory, an element at a time, each value evaluated as its element is filled: no array is made elsewhere and copied in, so an array of a million elements is allocated and filled with no copy of it anywhere. They are the same contents a value construction of the array takes, the scalars of a multi-dimensional one written in order, and the allocation then takes nothing in parentheses. A collection's contents are appended through the new reference once it is made, as they are appended to a value it constructs:

let zeros = new Rc[mut, Array[i32, 1000, 1000]] <- fill 0;
let grid = new Uni[Array[i32, 2, 3]] <- 1, 2, 3, 4, 5, 6;
let names = new Rc[mut, List[i32]](10) <- 1, 2, 3;

Today a single owner of a collection does not take contents this way: new Uni[List[i32]](10) <- 1, 2, 3 is refused with a misleading Error 1048: This variable's value has been moved out. Allocate it, then push.

Allocating text and other bodies with no fixed size#

Some types have no size of their own: a value of one is never held in a variable, a field or a parameter, only behind a reference, which carries what is missing. A trait's virtual reference carries a table of its methods. The body of text, str, is reached by a reference that carries its byte count: a pointer and a usize, in every region and for a borrow alike (&str, Uni[str], Rc[str], Arc[str], Gc[str]), 16 bytes where a reference to a type with a size is 8. str declares Immutable, so a reference to it written with no permission is imm (&str is &imm str, Rc[str] is Rc[imm, str]) and mut is refused on it. The region's bookkeeping sits before the first byte, as it does for any value, and the owner points at the byte, so one hop reaches the text.

There is no value of such a body to construct or to move in, so its allocation takes a borrow of one in the parentheses and copies the bytes the borrow holds, as many as it has, into the memory the region gives. A borrow of the body is made from a slice of bytes with as, and converts to a slice by itself; both are the same pair, and as checks only that. Not built yet: checking that the bytes are UTF-8, and that nothing still writes them while the text is used:

let bytes &Array[u8] = "hello";
let view = bytes as &str;                    // a borrow of the bytes: 5 of them
let text = new Rc[str](view);                // a copy, in Rc's memory
let same = trynew Uni[str](view);             // an Option, None if memory ran out
printStr(text);                              // lent as a borrow, which is the &str printStr takes

A string literal is a &imm str: a borrow of its text, in read-only memory, that lasts as long as the program, so it may be sent to another thread. The text is followed by a zero byte for C that the count leaves out, and an owner of str keeps one after its bytes too (C strings). Wherever an owner of str is wanted, in any region, a literal (and only a literal) is copied into one without new; any other &str is copied with new as above:

let name Uni[str] = "Padma";                  // new Uni[str]("Padma"), copied from read-only memory
fn greet(who Rc[str]) {..}
greet("Jayne");                              // the same copy, into an Rc

A growable String is a literal's other destination: where one is wanted a literal is copied into it (let s String = "core";), by the static function fromLiteral a type declares to say so. And s.freeze() moves a String's bytes into a Uni[str] without copying them (Handing text on).

Where a read-only borrow of such a type is wanted, &String for one, the literal is borrowed from a temporary made the same way: &String.fromLiteral("core"), written out. The temporary lasts to the end of the statement and is dropped there, like any temporary a borrow points at (a function's parameter and an init's, in new File("x"), are given one alike); a local's initializer keeps it to the end of the block, as let r = &make() does (Borrowing a temporary). It is lent only to a borrow that cannot write (&mut String is refused, since what is written to the temporary is lost with it), and only inside a function's body, where a statement ends it: a global, a constant, a field's default, a returned value or an if arm is not given one. A parameter's default is made at each call that leaves the argument out, as if the caller had written the literal there: fn shout(s &String = "core") called as shout() lends a temporary of its own (and a String by value is made for the call):

fn shout(s &String) {..}
shout("core");                               // a temporary String, lent to the call, dropped at the semicolon
let r &String = "core";                      // the temporary lasts as long as the block

Owning an array#

The other body with no fixed size is Array[T], the array type without a size, whose elements are any type T and whose count is known only at run time. Its borrow is the slice: &Array[T], and &mut Array[T] the slice that changes its elements (the older spelling &[]T is refused, Error 1336). A slice of bytes, &Array[u8], and a borrow of the text body, &str, are the same pair of words and different types, and either converts to the other with as. Every array reference is borrowed: there is no owning array reference, and an owning reference is thin, virtual, or carries the count of a body, str or Array[T]. An array is owned in one of three ways, chosen by how its length is known:

  • A fixed-size array, whose size is part of its type. It may be held in a variable or a field, or allocated in a region and reached by a thin reference whose type carries the size. Its contents follow the allocation after <- and fill it in the region's memory (above); an array already made is moved in from the parentheses. Today that array must be named first: an array construction written inside the parentheses, new Rc[mut, Array[i32, 4]](new Array[i32, 4] <- 1, 2, 3, 4), is refused with a misleading Error 1226. 
    let grid = new Rc[mut, Array[i32, 4]] <- fill 0i32;   // grid's type: Rc[mut, Array[i32, 4]]
let four = new Array[i32, 4] <- 1, 2, 3, 4;
let made = new Rc[mut, Array[i32, 4]](four);          // four is moved in
  • An owner of Array[T], when the number of elements is chosen at run time and never changes: Uni[Array[T]], Rc[Array[T]], Arc[Array[T]] or Gc[Array[T]], each a pointer and a count, one hop to the elements. It is allocated by copying the elements of a slice, as an owner of str is, so only where the elements copy. The owner has len, is indexed (o[i]) and takes a borrowed range (&o[a ..< b]) as a slice does, and is lent as the slice wherever a &Array[T] is wanted, a generic's element type inferred from it. A borrow of a fixed-size array, &Array[T, n], converts to the slice. Its permission says what may change: held writable (Uni[Array[T]], Rc[mut, Array[T]]) its elements change but its length does not; held imm (Rc[imm, Array[T]], Arc[imm, Array[T]]) nothing changes. The owner's death finalizes each element, and a Gc object counts the bytes its elements really take. 
    fn sum(xs &Array[i32]) i32 { var t = 0; each x in xs { t += *x; } t; }

let primes = new Array[i32, 4] <- 2, 3, 5, 7;
let shared = new Rc[imm, Array[i32]](&primes);   // a copy: a pointer and a count, 16 bytes
let total = sum(shared);                         // lent as the &Array[i32] sum takes: 17
let middle = &shared[1usize ..< 3usize];         // a borrowed range of it
  • A collection, when the length is chosen at run time and may grow or shrink, which is exactly what a List is: a pointer to its elements, how many there are, and how many it has room for. A list held in a local is used directly; one that several owners share is a managed reference to it, new Rc[mut, List[i32]](names). The length of a shared list lives once, in the list, where every owner sees the same count; a length carried in each copy of a reference could not stay in step when the list grows. That is why there is no owning reference to a growable array, and writing +[], as a type or an allocation, is an error that says so (Error 1203: There is no owning array reference '+[]').

A list that will not grow again can become an owned array without a copy: list.freeze() consumes the list and moves its block, shrunk to the elements it holds, into a Uni[Array[T]]. The elements are not copied, move types included, and the owner's death finalizes each of them once. A list that holds nothing makes a one-byte block, since the owner of an Array[T] always owns heap bytes:

var list = List[i32].empty();
list.push(4);
let kept = list.freeze();                       // a Uni[Array[i32]] holding the list's elements, moved

An owner of a body is a counted owner or a single one by its region and permission, like any other: copies, parameters and fields are counted (an owner of str, written with no permission, is imm and copies, though a Uni owner still moves), a uni owner moves, and the last to go gives the block back through the region's free. A collector's region marks it through its pointer. Each owner carries its own count, which is right because the body never grows.

Owning reference types#

Wherever a type is written, a variable, a field, a parameter, a return type, an alias, a generic's argument, an allocation, an owning reference type is written the same way: the region, then in square brackets an optional permission and the value type:

alias Link = Rc[mut, Node];    // shared and mutable
fn first(n Rc[Node]) i64 {..}  // no permission written: uni, the only owner
var list = List[Gc[imm, Leaf]].empty();

Left out, the permission is uni, which may become any other (but for a single owner, which takes no mut), so Rc[Node] is Rc[uni, Node]. The region ref is a struct declaring is RegionRef; a permission given to anything else is an error. A generic region ref takes its own brackets first, then the reference's: R[A][mut, Node], allocated as any other, new R[A][mut, Node](1). When the value type is an open trait, the reference is a virtual reference, which carries a table of methods beside its pointer (Rc[mut, Shape]); when it is a body whose length the reference carries, it is a pointer and a count (Uni[str]); for any other value type, an enum included, it is a single pointer.

A match pattern never spells an owning reference type: it names the variant, Circle, and the matched value supplies the region and the permission, so on an Rc[imm, Shape] it binds an Rc[imm, Circle]. On an Rc[mut, Shape] the narrowing is refused, since another owner could change the variant while it is used (An enum's variant). The older plus-sign spelling, +Rc-mut Circle, is refused (Error 1414: A pattern names only the variant).

An enum reached only by reference: @unsized#

An enum's value normally takes the room of its largest variant, so that it can be held anywhere and given any variant in place; because all its variants are one size, memory holding one variant can be given another instead, and a pool can hand out and reclaim the variants of one enum interchangeably. Padding every variant to the largest costs memory, though, and whether to pay it is a choice only the program can make. Writing @unsized declines it:

enum @unsized Shape {
  pub kind i32;

  pub struct Dot;
  pub struct Polygon { pub points Array[Point, 64]; }
}

let someDot = Shape.Dot(1);
let shape &Shape = &someDot;     // a reference to a variant coerces to one to the enum

Each variant then takes only what it needs, and the enum has no single size, so no value of it may be held, not in a variable, a parameter or a field (Error 1069: Variable s cannot be held by value: Shape is an '@unsized' enum, so its variants differ in size. Reach it through a reference.), and it is reached only by reference. Everything else is unchanged: the tag is still in the value, a common field is still readable through the reference, matching still recovers the variant, and dispatch still works. What is given up is the value semantics: holding one in a variable, copying it, passing it by value, and swapping a variant in place. Its references are thin and say nothing of the size. Most types that want this are graphs and trees, and those are usually better served by an open trait and structs that are one: once a type is reached by reference anyway, there is little left for a closed set to buy. So @unsized is for the case that is genuinely closed, wants exhaustive matching, and has variants whose sizes differ enough to matter.

Several owners of one value#

The first owning reference to a value always comes from an allocation. Where the region and permission allow it, more owning references to the same value are made by copying an existing one, by assignment or by passing it to a function:

let node = new Rc[imm, Node](4);
let node2 = node;            // node2 and node point at the same value

When a value is freed#

An owning reference keeps its value alive. While a value has at least one owning reference, its region will not free it; only when all of them have gone may the region reclaim it, though how soon depends on the region. An owning reference goes when what holds it goes or takes a new value. One never stored anywhere is used up by the expression it is part of, almost at once. One stored in a variable goes no later than the end of the variable's scope, and sooner if the variable takes another value. One held inside a value goes when that value does. When a region decides to reclaim a value, it first runs the value's finalizer, if it has one.

When memory runs out: trynew#

An allocation can fail, rarely, when the region cannot get enough memory. How a program finds out depends on how the allocation is written:

  • new: the program panics and shuts down, naming the line of the allocation and the size it asked for: out of memory allocating 24 bytes.
  • trynew: the allocation gives back an Option of the owning reference, Some holding it when the memory was obtained and None when it was not, which the program may handle as any Option. Only an allocation can fail this way, so trynew takes an owning reference type, never a value type. An array's contents after it are filled only when the memory was obtained: on None, none of their values is evaluated. Not built yet: contents after a trynew of anything else, such as a list (Error 1228); allocate it with trynew alone, then append on Some. A trynew in a region value, such as an arena, is refused too: whether an allocation in such a region can fail is not settled.
let maybe = trynew Rc[mut, Node](1);    // an Option[Rc[mut, Node]]
match maybe {
  case let n Some[Rc[mut, Node]] { adopt(n); }
  else { fallBack(); }
}

let names = trynew Rc[mut, List[i32]](10);   // not: trynew ... <- 1, 2, 3
match names {
  case let s Some[Rc[mut, List[i32]]] { s <- 1, 2, 3; }
  else { fallBack(); }
}

Using an owning reference#

An owning reference is used much as a borrowed one is: it is dereferenced, compared and read through the same way, and wherever a borrowed reference is wanted it lends what it owns (Making a borrow), as the tree's owners did for sum. What differs is what copying and dropping it do, which is up to its region. A value owned by a region may not be moved out through a shared owner, though a sole owner may give it up (Moving a value out).

The single owner: Uni#

The single-owner strategy follows from one constraint: a value it allocates has exactly one owning reference. That reference may be passed from function to function, or from thread to thread, but only by moving, so no copy of it is ever made, and when it goes, the value can be finalized and freed at once. Core's Uni is that region's ref. Written as a region ref of your own would be, it is a struct declaring RegionRef and Move, with no fields, one method to get the memory and one to give it back (Making your own region):

struct Solo is RegionRef, Move {    // Move: a copy of the reference is a move, so never two owners
    fn alloc(size usize) *u8 {
        RawBlocks.alloc(size, 16usize);  // any general-purpose allocator will do
    }
    fn free(self &uni Solo) {
        RawBlocks.release(self as *u8);
    }
}

Choose a single owner for a value with one natural owner: the tree above, a record in a list, a resource. It costs nothing while the program runs, frees each value the moment its owner goes, and is the only strategy where the program decides exactly when a value is destroyed. It uses memory tightly and needs almost no runtime. Its limits follow from the constraint: data takes the shape of a tree, so a node with two parents or a cycle needs another region, and getting a value out of a struct or array that owns it takes a swap. Any number of borrows of a singly owned value may still be made for a while, bounded by the scope they were made in.

A single owner is never shared, so it takes no permission that shares. Uni[T] is the normal spelling, with no permission written, and Uni[imm, T] is allowed, for a value that is promised never to change (an owned closure that only reads its state is Uni[imm, fn(sig)]). mut means several owners writing one value, which a single owner has no one to share with, so it is refused wherever a type is written, in a user's region declaring Move as much as in Uni:

fn keep(n Uni[mut, Node]) {..}   // Error 1507: Uni has one owner per value, which nothing else shares:
                                 //   'mut' is shared mutable, so it means nothing on a single owner.
                                 //   Write Uni[T], or Uni[imm, T] to promise the value never changes.

The order of an allocation#

Every allocation runs its steps in the same order. First the initializer's arguments are evaluated, in the order written, or the finished value is. Then the region obtains the memory, and nothing more (its alloc). Then the region's initializer fills its bookkeeping in place, then a lock permission's does the same for its part, and then the value's initializer fills the value in place, where it was allocated, or the finished value is stored there, or an array's contents fill it, each value evaluated then. Last, the owning reference goes where the expression puts it:

let p = new Rc[mut, Pair](make(1), make(2));  // make(1), make(2), then alloc, then Pair's init
let q = new Rc[mut, Pair](makePair());        // makePair(), then alloc, then the store

A construction always fills its value in place, where the value goes, so no copy is made. Declaring a variable with a construction hands the initializer the variable's own memory, and allocating one hands it the memory the region obtained, after the region's own bookkeeping is filled (a finished value given instead is moved in, and no initializer runs: Constructing in a region shows both). A value constructed where it has no place yet, as an argument to a function or a field of another construction, is built in a temporary and copied there.

An initializer, or a value of an array's contents, may itself allocate, even in a garbage-collected region, whose collector may run while it does: such a region's new object is held as a root and its value reads as empty from the moment its memory is obtained, so a collection finds it, and nothing it half holds, until it is filled.

You can now allocate values that outlive their function, give them a single owner, and lend them to code that does not care where they live. The region decides when a value dies; next is exactly when that is, for a value in a region and every other kind, and in what order its finalizers run.