Collection Types

On this page

List
Freezing a list
A list that a C function fills
Dict
Looking things up
Text keys looked up as &str
Visiting order and seeds
OrderedDict
Set
Deque
String, the growable string
Text and bytes
Building, changing and reading a String
A String for C, and freezing it
Walking a collection
The collection traits
Why a push waits for a borrow of an element
Collections in a region or an arena
The region a collection's block comes from
The heap's region and the raw blocks layer
Giving a collection another region
A type that carries a region
Starting sizes, and what the region word costs
A collection in an arena
A collection in an actor's own region
Collections of garbage-collected references

Note: A Set has no union or intersection yet, and no trait covers a set's insert and remove.

A collection type holds some number of values (elements) that are all the same type. The standard library offers a number of versatile collection types, such as List, Deque, Dict, OrderedDict and Set.

All such collection types are built on top of the array primitive types, whose elements are co-located in memory and are individually accessed using an integer index:

Array types. An array has a statically known size.
Array reference types. An array reference, a slice, is a borrowed view of some runtime-determined number of elements of the same type: all or some of the elements of an array, or of a collection. It owns none of them. An array whose length is chosen at runtime is a collection.

The array primitives are described on the next two pages.

The library collection types are the collections package's List[T], Dict[K, V] (keyed by any type that is Hash), OrderedDict[K, V] (the same, visiting in insertion order), Set[T] and Deque[T], with String beside them (import collections use *;). A list or a dictionary is constructed with new, its first values after <-: new List[i32](100) <- fill 0 (a collection's contents). Each holds its elements in one block it gets from its region (the heap's unless it was made in another; see below) through a raw pointer, not in an array reference.

List#

A List[T] is a growable array: pushing onto it makes room as it needs, doubling its block as it fills. xs <- v is a push. An element is read with xs[i], which is a borrow of the element, so it is dereferenced to get the value, and &mut xs[i] borrows it to change.

import stdio use *;
import collections use *;

fn main() i32 {
  mut xs = List[i32].empty();
  xs.push(3);
  xs <- 4;                       // <- is push
  xs.push(5);
  print <- xs.len();
  print <- "\n";
  print <- *xs[1usize];          // an element is a borrow, so dereference it
  print <- "\n";
  match xs.pop() {
    case imm v Some {print <- v; print <- "\n";}
    case is None {print <- "empty\n";}
  }
  match xs.get(7usize) {         // get does not panic
    case imm v Some {print <- *v; print <- "\n";}
    case is None {print <- "no seventh\n";}
  }
  mut total = 0;
  each x in xs {                 // walks the slice the list lends
    total += *x;
  }
  print <- total;
  print <- "\n";
  imm zeros = new List[i32](5) <- fill 0;
  print <- zeros.len();
  print <- "\n";
  0i32;
}

This prints 3, 4, 5, no seventh, 7 and 5, one to a line. peek() (an Option of a borrow of the last value) and get(i) (the same for position i, None past the end) do not panic.

A list is String's twin for any element. list.view() lends its elements as a &Array[T], the slice, and the list folds the methods of Array[T] in as its own (list.len is Array[T]'s).

Freezing a list#

list.freeze() consumes the list and moves its block, shrunk to the elements it holds, into a So[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 (owned arrays).

A list that a C function fills#

A list that a C function fills (the "ask how many, then fill" shape of Vulkan's queries) needs no unsafe code: list.resize(n, zero) makes it n copies of a value long (or drops the values past n), the C function is handed list.viewMut() (as a pointer, list.viewMut() as *T, and the count), and list.truncate(written) cuts it to the count C wrote, finalizing the values it drops (a no-op when written is not less than its length). resize exists only where T copies; a list of values with finalizers is shortened with truncate. Here a Cone function stands in for the C one:

import stdio use *;
import collections use *;

// Stands in for a C function that fills at most out.len values and says how many it wrote
fn squares(out &mut Array[i32]) usize {
  mut n = 0usize;
  while n < out.len and n < 5usize {
    out[n] = i32.from(n) * i32.from(n);
    n = n + 1usize;
  }
  n;
}

fn main() i32 {
  mut xs = List[i32].empty();
  xs.resize(8usize, 0);                 // room to fill: eight zeros
  imm written = squares(xs.viewMut());
  xs.truncate(written);                 // keep only what was written
  print <- xs.len();
  print <- ": ";
  each x in xs {
    print <- *x;
    print <- " ";
  }
  print <- "\n";
  0i32;
}

This prints 5: 0 1 4 9 16.

Dict#

Dict[K, V] is a SwissTable: an open-addressed table with a control byte for each bucket (empty, removed, or the top 7 bits of the key's hash), read eight at a time as one 64-bit word, so a lookup compares a key only in a bucket whose tag matches; it holds up to 7/8 of its buckets, and doubles when full. Its keys are any type that is Hash: integers and bool, a String, a pool.Ref[T], a struct that declares is Hash (the compiler supplies its hash from its fields, and the struct writes the == that goes with it); a float key is refused. A key moves in and the dictionary owns it.

import stdio use *;
import collections use *;

fn main() i32 {
  mut counts = new Dict[String, i64];
  imm words = ["to", "be", "or", "not", "to", "be"];
  each w in words {
    *counts.getOrInsert(String.from(*w), 0i64) += 1i64;   // one search; the String moves in
  }
  print <- counts.len();
  print <- "\n";
  print <- *counts["be"];                          // a &str looks up a Dict[String, V]
  print <- "\n";
  if counts.contains("not") { print <- "has not\n"; }
  match counts.get("or") {
    case imm n Some {print <- *n; print <- "\n";}
    case is None {print <- "none\n";}
  }
  match counts.remove("to") {                      // the value comes out
    case imm n Some {print <- n; print <- "\n";}
    case is None {print <- "none\n";}
  }
  print <- counts.len();
  print <- "\n";
  0i32;
}

This prints 4, 2, has not, 1, 2 and 3, one to a line.

Looking things up#

Lookups take a &K: get(&k) is an Option of a borrow of the value, getMut a mutable one, getCopy an Option of a copy (only where the value copies, which is the lookup that works through a shared Rc[mut, Dict[K, V]]), contains, remove (the value moved out, the key finalized), d[&k] and &mut d[&k] (a panic for a key it does not hold), insert(k, v) (when it replaced an entry, finalizing the old key, an Option holding the old value moved out to the caller, as Rust's does, and None for a new key; the value dies with the caller's binding, or at the end of a statement that ignores it; d <- k: v ignores it), getOrInsert(k, v) (a mutable borrow of the value held, or else v moved in, with one search: *counts.getOrInsert(word, 0) += 1), clear, len and capacity (the entries it holds before it grows).

Text keys looked up as &str#

A Dict[String, V], a Dict[So[str], V] or a Dict[Rc[str], V] (an owner of text is Hash, an immutable key with no spare capacity; a literal given to insert is copied into the owner) also takes the key as the body it lends or holds, a &str (d.contains("core")), for every one of these lookups: a literal, a view (s.view(), a slice of text), a So[str] and an Rc[str] are each lent as a &str, so none builds a String to ask. They find the key they equal because a str, a String and a literal feed a hasher the same bytes (str has a hash of its own) and == compares the bytes. A d["sdl"] of a key it does not hold is a panic that names the key; one by a &K does not. A &Array[u8] is not text until it says so: bytes as &str.

Visiting order and seeds#

A dictionary is unordered: each dictionary keeps a seed of its own, the process's random one by default, so keys(), values() and entries() (cursors, each next() giving an Option of a borrow, the dictionary loaned while one is used) visit in a different order on every run, and a program sorts, or looks a key up, rather than rely on it. Dict[K, V].deterministic() fixes the seed, and then the same keys inserted in the same order are visited in the same order on every run; Dict[K, V].withSeed(n) takes one of your own. When the order matters to the output, use an OrderedDict.

OrderedDict#

OrderedDict[K, V] is a Dict that visits in the order of insertion, on every run and under every seed, which is what a program wants to print, write out as a file, or replay (a JSON object, a configuration, HTTP headers). It has the same methods under the same names, including the &str lookups of an OrderedDict[String, V] and the cursors keys(), values() and entries(), and the same seeds.

import stdio use *;
import collections use *;

fn main() i32 {
  mut headers = new OrderedDict[String, String];
  headers <- String.from("Host"): String.from("example.org");
  headers <- String.from("Accept"): String.from("text/html");
  headers <- String.from("Host"): String.from("cone.dev");   // replaced where it stands
  each key, value in headers {
    print <- key.view();
    print <- ": ";
    print <- value.view();
    print <- "\n";
  }
  headers.remove("Host");                                    // the later entries move down
  headers <- String.from("Host"): String.from("again");      // a key put back goes last
  each key in headers.keys() {
    print <- key.view();
    print <- "\n";
  }
  0i32;
}

This prints Host: cone.dev, Accept: text/html, then Accept and Host.

Its layout is Python's compact dict and Rust's IndexMap: a dense array of (hash, key, value) in insertion order, which the cursors walk front to back, and beside it an index with the same control bytes and eight-at-a-time probe as Dict's, holding for each bucket a u32 position in the array, so a table holds fewer than 2³² entries. A lookup is one memory access slower than Dict's; iteration is faster, with no empty buckets to skip. Inserting a key it holds replaces that entry where it stands; a key put back after a remove goes to the end. remove keeps the order: every later entry moves down one place, so it costs the entries after the one removed (IndexMap's shift_remove). swapRemove(&k) is O(1) but moves the last entry into the hole, which breaks the order. If you mostly look keys up and rarely iterate, Dict is the faster choice.

Set#

Set[T] is a set of any type that is Hash: a Dict whose values take no bytes, so it has the dictionary's table, seed and unordered visiting. insert(x) answers whether x was new (a held element stays, and the item given dies), contains(&x), remove(&x) (true when it was held), clear, len, isEmpty, capacity, deterministic() and withSeed(n); items() is a cursor over borrows of the elements. A Set[String] takes an element as the &str a String lends (s.contains("core")).

import stdio use *;
import collections use *;

fn main() i32 {
  mut seen = new Set[String];
  imm words = ["to", "be", "or", "not", "to", "be"];
  mut repeats = 0;
  each w in words {
    if not seen.insert(String.from(*w)) {      // insert answers whether the element was new
      repeats += 1;
    }
  }
  print <- seen.len();
  print <- " distinct, ";
  print <- repeats;
  print <- " repeats\n";
  if seen.contains("or") { print <- "or is in\n"; }
  if seen.remove("or") { print <- "or removed\n"; }
  if not seen.contains("or") { print <- "or is out\n"; }
  0i32;
}

This prints 4 distinct, 2 repeats, then or is in, or removed and or is out.

Deque#

Deque[T] is a double-ended queue, a growable ring buffer (Rust's VecDeque): its values are in one block, as a circle, the first at a slot that moves, so push and pop at the back and pushFront and popFront at the front are all O(1), where a List can take a value off its front only by moving every other one. peek() and peekFront() are an Option of a borrow of the last and the first value, get(i) the same of position i counted from the front (None past the end), d[i] and &mut d[i] borrow it (a panic past the end), and items() is a cursor over borrows from the front to the back.

import stdio use *;
import collections use *;

fn main() i32 {
  mut line = Deque[i32].empty();
  line.push(1);
  line.push(2);
  line.push(3);
  line.pushFront(0);                  // O(1) at the front too
  match line.popFront() {
    case imm v Some {print <- v; print <- "\n";}
    case is None {print <- "empty\n";}
  }
  match line.peek() {                 // the last, as a borrow
    case imm v Some {print <- *v; print <- "\n";}
    case is None {print <- "empty\n";}
  }
  print <- *line[1usize];             // counted from the front
  print <- "\n";
  each v in line {
    print <- *v;
    print <- " ";
  }
  print <- "\n";
  0i32;
}

This prints 0, 3, 2 and 1 2 3.

A full block is replaced by one twice the size (4, 8, 16, ...), the values moved in order with the first in slot 0; it never shrinks. reserve(n), capacity, clear (finalizing front to back, keeping the block), len, isEmpty and new Deque[T](n), a block of exactly n slots, are a list's. Its values may wrap round the block's end, so it has no view(): read them by position or with the cursor.

String, the growable string#

String is the growable string: a list of bytes and one spare byte, so its block always has a NUL after the text (which the length leaves out, rewritten by each change) for C, and a String that holds nothing has no block at all. s.view() lends it as a &str (the static empty literal when it holds nothing), and the String folds the methods of str in as its own (trimStart, isCharBoundary, slice and the ranges &s[a..<b], the orderings < ...: The Methods of str), and == and the orderings compare its bytes with any other text, a literal, a &str, a So[str] or another String. A literal is copied into a String wherever one is wanted (imm s String = "core", names.push("core")).

import stdio use *;
import collections use *;

fn main() i32 {
  mut s = String.from("hello");
  s <- ", ";                               // append text
  s <- "world", 33i64;                     // and a number
  s.appendByte('!');
  print <- s.view();
  print <- "\n";
  print <- s.len();
  print <- "\n";
  if s.view().startsWith("hello") { print <- "starts with hello\n"; }
  s.insert(5usize, "!!");
  s.replace("l", "L");
  s.upperAscii();
  print <- s.view();
  print <- "\n";
  imm parts = String.from("a,b,c").split(',');   // copies, which are Strings
  print <- parts.len();
  print <- "\n";
  print <- parts[1usize].view();
  print <- "\n";
  imm frozen = s.freeze();                 // the bytes move into a So[str]
  print <- frozen.len;
  print <- "\n";
  0i32;
}

This prints hello, world33!, 15, starts with hello, HELLO!!, WORLD33!, 3, b and 17, one to a line.

Text and bytes#

Text is a &str throughout: a &Array[u8] is bytes, and is not text until it says so (bytes as &str), though any &str is a &Array[u8] where bytes are wanted.

Building, changing and reading a String#

Building: String.from(text), String.fromBytes(bytes) (a copy of bytes that are text, such as a buffer read from a file or a socket; nothing checks they are UTF-8, as bytes as &str does not), String.withCapacity(n), String.fromCStr(c) (a copy of a cstr's bytes, or of a raw pointer's, which is a panic if null) and String.join(parts, sep); appending: append(text) (also s <- text; Rust's push_str), appendBytes(bytes) (bytes that are text, unchecked like fromBytes), appendByte, appendInt, appendUInt and appendHex; editing: insert(i, text) (i between characters), remove(start, end) (the bytes from start up to end, both between characters), truncate(n), clear, replace(from, to), replaceByte, padStart, padEnd, lowerAscii and upperAscii; reading, in bytes, with &str text: equals, equalsIgnoreAsciiCase, and (folded in from str) compare, startsWith, endsWith, find, findFrom and contains; and copies of parts, which are Strings: sub, trim, lines and split.

A String for C, and freezing it#

s.cstr() is its C string, the NUL already there, so nothing is copied; it is good until the String next changes, and a NUL inside the text is a panic, at the caller's line, since C would stop reading there. s.freeze() consumes the String and moves its block, shrunk to the text and its NUL, into a So[str]: the bytes are not copied.

Walking a collection#

Walking a collection is each. A List is walked as the slice it lends, a counted loop; iter() is its cursor, for code generic over cursors (Iterator), and the methods of Array[T] it folds in come with it: mutItems() lends each element as a &mut to change, indexed() pairs a position (a usize) with a borrow of the element, chunks(n) and mutChunks(n) hand out its values in runs of n (each run a slice, a &mut one from mutChunks, which a list gives itself), asArrays[N]() and mutArrays[N]() see them as rows of N over the same block (Seen as Rows), and drain() leaves the list empty at once (keeping its block) and hands each value over by value, finalizing those a loop left early did not reach.

import stdio use *;
import collections use *;

fn main() i32 {
  mut xs = List[i32].empty();
  xs <- 1, 2, 3, 4, 5;

  each x in xs.mutItems() {              // each element lent as a &mut
    *x = *x * 10;
  }
  each i, x in xs.indexed() {            // a position beside a borrow of the element
    print <- i;
    print <- "=";
    print <- *x;
    print <- " ";
  }
  print <- "\n";
  each run in xs.chunks(2usize) {        // runs of two; each run is a slice
    print <- run.len;
    print <- " ";
  }
  print <- "\n";
  mut ys = List[i32].empty();
  ys <- 7, 8, 9;
  each a, b in zip(&xs, &ys) {           // two collections side by side
    print <- *a + *b;
    print <- " ";
  }
  print <- "\n";
  each x in xs.drain() {                 // leaves the list empty; each value by value
    print <- x;
    print <- " ";
  }
  print <- "\n";
  print <- xs.len();
  print <- "\n";
  0i32;
}

This prints 0=10 1=20 2=30 3=40 4=50, 2 2 1, 17 28 39, 10 20 30 40 50 and 0, each on its own line.

A Deque, a Set, a Dict and an OrderedDict each have an iter() that each calls itself: a deque's and a set's give a borrow of each element (items() is the same cursor), a dictionary's gives its pairs, a borrow of the key and a borrow of the value, which each key, value in dict unpacks. The dictionaries' other views are cursors too: keys(), values() and entries() (a borrow of each entry, with its key and value). zip(&a, &b) walks two lists, arrays, slices, deques, sets or dictionaries side by side. A dictionary or set is not changed while a loop walks it, and a dictionary's order is the one described above. A String's text is walked through chars() and charIndices() (The Methods of str).

The collection traits#

The collections package also declares five small traits, one for each thing a collection can do, so that a function asks for exactly the ability it uses; each is met structurally (Traits), by having the methods, so none of the collections declares one.

Collection (len, isEmpty: List, Deque, String, Dict, OrderedDict, Set);
Indexed[T] (get(i): List, Deque);
Stack[T] (push and pop at the back, peek: List, Deque);
Queue[T] (push at the back, popFront: Deque);
Map[K, V] (get, insert, remove, contains by a &K: Dict, OrderedDict).

A function asks for one as a static bound (A generic trait as a constraint), fn drain[S Stack[i64]](s &mut S), fn drain[T, S Stack[T]](s &mut S) or fn drain[T, S](s &mut S) where S is Stack[T], called with &mut list or &mut deque; the bound is decided where the function is called, so the call is to the type's own methods. A trait is given all its type arguments ([S Stack] is refused), while Collection, which has none, is written alone, fn count[C Collection](c &C). The other form is a virtual reference, fn drain(s &<mut Stack[i64]), which takes the same arguments through one compiled function and a table of methods, for a value whose type is not known where the function is compiled; every trait works either way. Map's insert answers the old value, an Option (None for a new key). A Set's insert answers whether the element was new.

import stdio use *;
import collections use *;

// A function asks for exactly the ability it uses
fn countOf[C Collection](c &C) usize { c.len(); }

fn drainSum[S Stack[i64]](s &mut S) i64 {
  mut total = 0i64;
  while true {
    match s.pop() {
      case imm v Some {total = total + v;}
      case is None {break;}
    }
  }
  total;
}

// The other form: one compiled function, called through a table of methods
fn peekTop(s &<mut Stack[i64]) i64 {
  match s.peek() {
    case imm v Some {*v;}
    case is None {-1i64;}
  }
}

fn main() i32 {
  mut list = List[i64].empty();
  list <- 1i64, 2i64, 3i64;
  mut deque = Deque[i64].empty();
  deque <- 10i64, 20i64;
  imm word = String.from("four");
  print <- countOf(&list);              // a List is a Collection
  print <- " ";
  print <- countOf(&deque);
  print <- " ";
  print <- countOf(&word);
  print <- "\n";
  print <- peekTop(&mut list);
  print <- "\n";
  print <- drainSum(&mut list);         // a List is a Stack
  print <- " ";
  print <- drainSum(&mut deque);        // so is a Deque
  print <- "\n";
  0i32;
}

This prints 3 2 4, 3 and 6 30.

Why a push waits for a borrow of an element#

A collection's elements sit in one block, and a push may move every one of them to a bigger block. So a borrow of an element (list[i], dict[key], s.view()) keeps a local collection loaned while it is used: it may be read, but a push waits for the borrow's last use. The compiler refuses the push that would leave the borrow dangling:

mut list = List[i32].empty();
list.push(10);
list.push(20);
imm first = list[0usize];     // borrows list, read-only
imm n = list.len();           // fine: the list may be read
list.push(30);                // refused: first is used again below
print <- *first;

Copying what is needed out before the push leaves no borrow to wait for (imm firstX = l[0usize].x; l.push(p);). A mutable borrow (&mut list[i], or list.viewMut(), a &mut Array[T] of every element, and a String's s.viewMut() of its bytes) is one more alias of the elements: until its last use the collection may still be read and written in place, but not reshaped, by a push, a clear or a pop.

mut list = List[i32].empty();
list.push(10);
list.push(20);
imm e = &mut list[0usize];
imm n = list.len();           // fine: read while the mutable borrow is live
list.set(1usize, 5);          // fine: written in place
*e = 7;                       // the last use of e

Each collection declares ShapeChanging (a provisional name), as does any type the compiler finds to be one from its methods, a struct wrapping a list included:

struct Pt { pub x i32; pub y i32; }

struct Bag {
  items List[Pt];
  fn first(self &) &Pt { items[0usize]; }
  fn add(self &mut, p Pt) { items.push(p); }
}

fn g(bag &mut Bag) i32 {
  imm e = bag.first();
  bag.add(new Pt(5, 6));      // refused: e is used again below
  e.x;
}

Reached through a shared path, a &mut List parameter say, the same path is frozen the same way, and a push, a clear or a pop through another reference to the same collection, or by a call that might make one, is refused while the borrow is still to be used (fn f(l &mut List[Pt], p Pt) i32 { imm e = l[0usize]; l.push(p); e.x; } is refused at the push, as is a cursor held across a push: mut it = dq.items(); dq.push(9); it.next();). The full rules, for locals, fields, and what a call could do, are those of borrowed references.

Collections in a region or an arena#

Every growable collection (List, String, Deque, Dict, OrderedDict, Set and the pool package's Pool) gets, grows and gives back its block through a *MemRegion it holds as its last field, not through the C library.

The region a collection's block comes from#

A MemRegion (core) is three function references, allocFn, resizeFn and releaseFn, held in a struct's first field and handed that field's address: allocate(bytes, align) gives a block, resize(block, old, new, align) makes it longer, in place or by copying to a new one (a null block of 0 bytes is an allocation), and release(block, bytes) gives it back.

The heap's region and the raw blocks layer#

The heap's region, heapRegion(), is one static object that is never null, whose functions take blocks from the program's heap through core's raw blocks layer (RawBlocks: alloc, resize and release, the one place the heap's bytes come from, which today forwards to the C library's malloc, realloc and free; a block comes back to it, never to the C library directly); a collection made without a region points to it, so new List[i32] and List[i32].empty() take their blocks from the heap.

Giving a collection another region#

Another region is the construction's last argument: new List[i32](100, r), new Dict[String, i64](r), where r is a *MemRegion. Every block of the collection is then the region's, and its death gives each back to it. A collection that cannot hand its block over, because the owner of freeze() gives it back to the heap, moves its values into a heap block first when its region is not the heap's. This region counts what it is asked for:

import stdio use *;
import collections use *;
import libc;

// A region is three function references held in a struct's first field.
// This one counts what it is asked for and takes its memory from the C library.
struct Counting {
  header MemRegion;
  blocks usize;
  bytes usize;
}

fn countAlloc(r *MemRegion, bytes usize, align usize) *u8 {
  imm c = r as *Counting;
  (*c).blocks = (*c).blocks + 1usize;
  (*c).bytes = (*c).bytes + bytes;
  libc.malloc(bytes);
}

fn countResize(r *MemRegion, block *u8, oldBytes usize, newBytes usize, align usize) *u8 {
  imm c = r as *Counting;
  (*c).bytes = (*c).bytes + newBytes - oldBytes;
  libc.realloc(block, newBytes);
}

fn countRelease(r *MemRegion, block *u8, bytes usize) {
  if block as usize == 0usize { return; }
  imm c = r as *Counting;
  (*c).bytes = (*c).bytes - bytes;
  libc.free(block);
}

// A type of your own that carries a region hands it on to what it is made of:
// its last init parameter is the region, and a construction that names none gets the heap's.
struct Mesh is CarriesRegion {
  pub points List[f32];
  pub fn init(self &new, n usize, region *MemRegion) {
    *self = new Mesh(new List[f32](n, region));
  }
}

fn main() i32 {
  mut counting = new Counting(new MemRegion(&countAlloc, &countResize, &countRelease), 0usize, 0usize);
  imm region = (&counting) as *MemRegion;
  {
    mut xs = new List[i64](region);        // asks the region for nothing yet
    mut i = 0i64;
    while i < 100i64 {
      xs.push(i);
      i = i + 1i64;
    }
    print <- "bytes held: ";
    print <- counting.bytes;               // 128 slots of 8 bytes
    print <- "\n";
  }                                        // the list's death gave the block back
  print <- "bytes held after: ";
  print <- counting.bytes;
  print <- "\n";

  imm mesh = new Mesh(50usize, region);    // the mesh's list comes from the same region
  print <- "bytes for the mesh: ";
  print <- counting.bytes;
  print <- "\n";
  imm onHeap = new Mesh(50usize);          // no region named: the heap's
  print <- onHeap.points.capacity();
  print <- "\n";
  0i32;
}

This prints bytes held: 1024, bytes held after: 0, bytes for the mesh: 200 and 50.

A type that carries a region#

A type declares CarriesRegion (a provisional name) to say that it gets its memory this way: it declares an init, and every init it declares ends with the parameter region *MemRegion, which a construction naming none leaves out and the compiler fills in with the heap's. Any type may declare CarriesRegion, not only a collection: a struct that holds lists declares it and passes its own region on to them, init(self &new, n usize, region *MemRegion) { *self = new Mesh(pts: new List[f32](n, region), ...) }, so everything it is made of comes from the one region it was handed (the Mesh above).

Starting sizes, and what the region word costs#

The word costs 8 bytes a collection: a List and a String are 32 bytes, a Deque 40, a Dict and a Set 56, an OrderedDict 64. Every collection takes a starting size as its first argument, new Deque[i32](100), new String(100) (bytes), new Dict[String, i64](100) and likewise OrderedDict and Set (entries, without growing; the table rounds the room up to its size), new Pool[Npc](100) (slots), and a withCapacity(n) function makes one: Dict[String, i64].withCapacity(100).

A collection in an arena#

A collection made in an arena, new arena[List[i32]](16) (the arena's allocation), has its own words in the arena and its block there too: an arena is a region, and the construction hands the list the arena's unless the arguments pass another last. The list grows its block in place while it is the last thing the arena allocated and the room is there, so a list alone in its arena does, as long as the block the arena is bumping through (4096 bytes, or the size of a value that needed more) has the room (made with a starting size, the list is built before it is placed, so its first growth copies once); otherwise the arena bumps a new block, copies the values and abandons the old one, which it holds until it dies (two lists in one arena that grow in turn copy at every growth, and so does a lone list whose block has outgrown the arena's). Giving a block back does nothing. When the arena dies it finalizes the list, which gives its elements' own memory back to wherever it came from (a List[String] whose strings came from the heap frees them then).

import stdio use *;
import collections use *;
import arena use *;

fn main() i32 {
  // The heap's region is what a collection uses unless it is given another
  imm heap = new List[i32](100, heapRegion());
  print <- heap.capacity();
  print <- "\n";

  // A collection made in an arena: its words and its block both live there
  mut a = Arena.empty();
  imm xs = new a[List[i32]](16);
  mut i = 0;
  while i < 40 {
    xs.push(i);                  // the block grows in the arena
    i += 1;
  }
  print <- xs.len();
  print <- "\n";
  print <- *xs[39usize];
  print <- "\n";
  0i32;                          // the arena dies here and takes the list with it
}

This prints 100, 40 and 39.

A collection in an actor's own region#

An actor's own region is one too: new self[List[T]](16) takes the list's block from the region's allocate, resize and release, a block of its own that the region's collector never moves, and the list's final gives it back (Its own region).

import stdio use *;
import actors;
import collections use *;

alias NumsRef = ActorGc[mut, List[i64]];

actor Tally {
  nums Option[NumsRef];

  fn init(self &new) {
    *self = new Self(None[NumsRef]);
  }

  pub async do open(self) {
    nums = Some[NumsRef](new self[List[i64]](16usize));   // in the actor's own region
  }

  pub async do add(self, n i64) {
    match nums {
      case imm l Some[NumsRef] { l.push(n); }
      else { }
    }
  }

  pub async do report(self) {
    mut sum = 0i64;
    match nums {
      case imm l Some[NumsRef] {
        each v in l.iter() { sum = sum + *v; }
      }
      else { }
    }
    print <- sum;
    print <- "\n";
  }
}

fn main() {
  imm t = new Tally();
  t.open();
  t.add(5i64);
  t.add(7i64);
  t.report();
}

This prints 12.

Collections of garbage-collected references#

A collection can hold garbage-collected references (Gc, or in an actor its own ActorGc): a List[Gc[mut, Node]] is traced value by value. A collection, a Pool and an Arena each declare the built-in trait GcTraceElements (a provisional name) and a method fn gcTraceElements(self &mut) I giving a cursor over a writable reference to each value they hold (I declares is Iterator[&mut E], as List's mutItems() cursor does), and a type of your own that holds values behind a raw pointer declares it the same way. The collector traces each reference the cursor gives as it traces a value of its type, and rewrites it where it moves what it points at; a list of numbers holds nothing to trace, and costs nothing. A Dict and an OrderedDict give their values, and refuse a key that holds a traced reference (a collector that moved a key would leave it hashed where it was). An arena holds values of many types, so its cursor gives each value whose type holds a traced reference as an Erased (core's address of a value and the type record of its type), traced by its record's own trace. A type with a raw pointer to a value that holds a traced reference, that does not declare GcTraceElements, cannot be traced, and a variable or a traced allocation of it is refused.