The Array Family

Goose does not have an array type. It has a family of them, and the members differ in only one thing: what can happen to their size after they are built. Choosing between them is one of the main design decisions in a Goose program, so this chapter goes through each in turn and ends with a guide to picking one.

#The family7.1

The type syntax is postfix: the brackets go after the element type, so a growable array of 16-byte names is u8[..16][>..], read from left to right as "an array of 16-byte names that can grow".

Every one of them has the same representation: some metadata, followed by the elements, inline and packed together. There is never a pointer to a separate block of elements.

Here they all are at once:

fn main() {
    var pen: i32[4] = [3, 1, 4, 1];         // fixed
    let frozen: i64[] = [7, 8, 9];          // sized once
    var nest: i64[..6] = [];                // up to 6, inline
    nest.push(10); nest.push(20);
    var sized: i64[..] = [..10];            // capacity 10, chosen now
    sized.push(42);
    var flock: i64[>..] = [];               // grow-only
    for i in 4 { flock.push(i * i); }
    var stack: i64[>..<] = [];              // grow-shrink
    stack.push(5); stack.push(6); stack.push(7);
    let top = stack.pop();
    print(pen, " ", frozen, " ", nest, " ", nest.len, "/", nest.cap, " ", sized.cap);
    print(flock, " ", stack, " ", top);
}

[3, 1, 4, 1] [7, 8, 9] [10, 20] 2/6 10
[0, 1, 4, 9] [5, 6] 7

#Fixed arrays: T[k]7.2

A fixed array is exactly what it is in C: k elements, no metadata. The size must be a compile-time constant, that is, a literal, a named constant or an expression made of them. A local variable will not do, even a let:

fn main() {
    let n = 5;
    let pens: i64[n] = [0; n];
}

error: array size n names a local variable, not a constant

[v; n] is the fill literal: n copies of v, evaluated once. It is the easy way to initialize a large fixed array, and Goose requires every array to be fully initialized. A fixed array of a fixed element type is fixed-size, so it is copied on assignment like any other fixed value.

#Frozen arrays: T[]7.3

T[] is an array whose length is decided when it is built and never changes afterwards. It stores its length as a u32 in front of the elements. You cannot push to it or pop from it:

fn main() {
    let frozen: i64[] = [7, 8, 9];
    frozen.push(10);
}

error: .push is not available on i64[]

This is the type for finished data: a string inside a record, the list of children of a node, anything that is built once and then only read. Because its size depends on its contents, T[] is a variable-size type, which has consequences you will meet in the next few chapters.

The length can be stored in a narrower type when you know the array is small: T[u8] holds up to 255 elements with a one-byte length, and T[u16] up to 65535. There is also T[varint], whose length takes as few bytes as its value needs. Chapter 10 has more about varint.

#Limited arrays: T[..k] and T[..]7.4

A limited array has a capacity and a length. T[..k] reserves room for k elements inline, wherever the array sits, and its length can go up and down between 0 and k. Because the room is always there, T[..k] is a fixed-size type, so it can be a field of a struct, an element of another array, or a local, exactly like a T[k].

T[..] is the same thing with a capacity chosen when the array is built, written [..capacity]. Since the capacity is not known at compile time, T[..] is a variable-size type.

Pushing past the capacity stops the program:

fn main() {
    var nest: i64[..2] = [];
    nest.push(1);
    nest.push(2);
    nest.push(3);
}

goose runtime error: limited array capacity exceeded

The most common limited array by far is a short string inside a struct: name: u8[..16] stores up to 16 bytes and a one-byte length right inside the struct, so an array of such structs is still one flat block.

#Grow-only arrays: T[>..]7.5

The grow-only array is the workhorse. It is what you use wherever you would use a Vec, a [dynamic]T or a hand-rolled growable buffer: building up results, arenas of nodes, string builders, scratch space.

It lives on top of its own data stack, so it can grow without limit and without ever moving. push(v) builds one element at the end, in place, and returns a reference to it. append(xs) copies in all the elements of another array, a slice or a literal:

fn main() {
    var weights: i64[>..] = [];
    weights.push(4200);
    weights.append([3900, 4600]);
    let frozen: i64[] = [5100, 4400];
    weights.append(frozen);
    let last .= weights.push(4800);
    print(weights, " ", weights.len, " ", weights.index_of(last));
}

[4200, 3900, 4600, 5100, 4400, 4800] 6 5

index_of(r) turns a reference to an element back into its index.

#Grow-only does not mean "never shrinks"7.5.1

The name "grow-only" describes a guarantee, not a restriction on the operations. A T[>..] has pop, pop_n, resize and clear, and you can use them, but only where nothing points into the array. While a reference or slice into the array is still going to be used, shrinking it is an error:

fn main() {
    var eggs: i64[>..] = [61, 72, 58];
    let first .= eggs[0];
    eggs.pop();
    print(first);
}

error: cannot pop eggs while first is still used: it may hold a reference or slice into it (§5.1)

The check is about liveness, not scope. Move the print(first) above the pop and the program compiles, because first is never used after the array shrinks. The compiler does this analysis for you, which is how a grow-only array can be both a structure you hold references into and a scratch buffer you clear on every iteration.

fn main() {
    var eggs: i64[>..] = [61, 72, 58, 66];
    let first .= eggs[0];
    print(first);                // first's last use
    eggs.pop();
    eggs.resize(6, 0);           // grow with copies of 0
    print(eggs);
    eggs.clear();
    print(eggs.len);
}

61
[61, 72, 58, 0, 0, 0]
0

#Grow-shrink arrays: T[>..<]7.6

A grow-shrink array is for data that really does go up and down: a stack, a queue, a priority heap. It shrinks from anywhere, at any time, with no analysis needed. The price is a different restriction: references into a grow-shrink array may only be kept in local variables, never stored in a field, an element or a global. That way the compiler only has to look at the local variables in scope when it checks a pop.

fn main() {
    var todo: i64[>..<] = [];
    for job in [3, 1, 4, 1, 5] { todo.push(job); }
    var done = 0;
    while todo.len > 2 { done += todo.pop(); }
    print(todo, " done: ", done);
}

[3, 1] done: 10

The elements of a grow-shrink array must be fixed-size, because a popped slot may later be reused for a different value.

#What can go inside what7.7

The array kinds can be nested, within limits. The rules follow from the size classes:

• Fixed elements can go in any array.
• Variable elements, such as u8[] strings, can go in a T[] or a T[>..]. Such an array is sequential (see below).
• Resizable values can never be elements. An array of growable arrays would need one data stack per element.

fn main() {
    var groups: i64[>..][>..] = [];
}

error: array elements may not be resizable: i64[>..]

When you want "a list of lists", store finished inner arrays (i64[][>..]), or keep all the inner elements in one array and the boundaries in another. Chapter 14 shows a third way.

#Sequential arrays7.7.1

An array whose elements have different sizes, like an array of strings, cannot be indexed. Where the third element starts depends on the lengths of the first two, so words[2] would have to walk the array. Goose does not hide that cost: you can iterate such an array, but not index it.

fn main() {
    var words: u8[][>..] = [];
    words.push("honk");
    print(words[0]);
}

error: arrays of variable-size elements cannot be indexed, only iterated; for random access, keep your own array of references to them (§3.3)

fn main() {
    var words: u8[][>..] = [];
    for w in ["honk", "hiss", "flap"] { words.push(w); }
    for w, i in words { print(i, ": ", w); }
}

0: honk
1: hiss
2: flap

When you need both a compact layout and random access, keep an index beside the array, as the error message suggests. Chapter 13 shows how to do that with four bytes per entry. When you only need short strings, use a fixed-size element such as u8[..16] instead, and the array becomes indexable again.

#Array literals7.8

An array literal is written in brackets. Its element type comes from where it is going, if that is known: a typed variable, a parameter, a field. Without a destination, [1, 2, 3] is an i64[3]. There are a few special forms:

• [] is an empty array, and needs a destination type.
• [v; n] is n copies of v.
• [..cap] is an empty T[..] with capacity cap.
• var out = []; on its own creates a grow-only array whose element type is decided by the first push or append.

fn main() {
    var readings = [];
    readings.push(36.6);
    readings.push(37.1);
    let tally: i64[4] = [0; 4];
    print(readings, " ", tally, " ", [1, 2, 3].len);
}

[36.6, 37.1] [0, 0, 0, 0] 3

#Members7.9

Every array kind has .len, and the limited ones have .cap. The rest are available where they make sense:

Growing always provides a value for every new element, so there is no operation that exposes uninitialized memory.

Two arrays compare with == element by element, and arrays of different kinds can be compared as long as their element types match:

fn main() {
    let frozen: i64[] = [7, 8, 9];
    var grown: i64[>..] = [];
    for i in 7..10 { grown.push(i); }
    print(frozen == [7, 8, 9], " ", grown == frozen, " ", grown == [7, 8]);
}

true true false

#Choosing an array7.10

• T[>..] is the default. Reach for it first.
• T[>..<] when you need to pop from a stack or a heap in a loop, and only ever hold references into it in local variables.
• T[..k] when an array must live inside something else, like a name inside a struct, and has a sensible upper bound.
• T[] for data that is complete when it is built.
• T[k] for things that really have a fixed shape: a 4 by 4 matrix, a 256-entry lookup table.

#Exercises7.11

1. Build a u8[..8][>..] holding the names "Ada", "Grace" and "Linus", then print the second name. Why can you index this array, when you could not index a u8[][>..]?

2. Write a program that pushes the numbers 1 to 10 onto a i64[>..<] and then pops numbers until the sum of what was popped exceeds 20. Print the popped sum and what is left on the stack.

3. What goes wrong if you change the type of the stack in exercise 2 to i64[..8]? Try it.