v0.4.0
Collections · Lesson 17.2

Dynamic array

Source
Make a Collections::Array<T> whose length is chosen at run time, and compare it with an inline int32[4].
You'll need: Array, Slice, Move, Catch, Allocator, Vector

An inline array, int32[4], carries its length in its type. The compiler fixes it, and the elements live wherever the array itself lives — inside a local, a struct, another array. That is fast and simple, and it needs the length while compiling.

Sometimes the length is only known once the program runs: a count read from a file, a size passed in by a caller. Collections::Array<T> is for that case. It asks an allocator for a block of the length you choose at run time, and once made, that length never changes. It is not a vector: there is no Push. A fixed run whose size is decided late is the whole idea.

A length chosen at run time

The length arrives as an ordinary parameter:

func Squares(allocator: Allocator, count: uint) -> Array<int32> throws CollectionError {
    var squares = Array::Filled<int32>(allocator, count, 0);
    for i in 0..count {
        try squares.Set(i, (i * i) as int32);
    }
    return move squares;
}

Array::Filled makes count copies of one value — here count zeros — and Set replaces them one by one. Set can fail, for a reason you will see below, so each call is marked with try and Squares declares throws CollectionError. Filled asks for memory, but like every allocation in a collection it stops the program if there is none, so it needs no try.

An inline array could not do this. int32[count] is rejected, because an inline array's length must be a constant.

The array owns its block, so returning it moves the block out to the caller — the move squares of Move. Main receives it, with a try that hands any failure on to its own throws CollectionError, and walks it like any container:

var squares = try Squares(allocator, 6);
for value in squares {
    Print(" {}", value);
}

Copying an inline array onto the heap

Array::FromSlice copies existing values into a new dynamic array:

let primes: int32[4] = [2, 3, 5, 7];
var copy = Array::FromSlice<int32>(allocator, primes);
try copy.Set(0, 99);

The copy is independent: changing it leaves the original alone, so the copy starts with 99 while primes[0] is still 2.

What a wrong index costs

Both kinds of array check every index. They differ in what happens when one is wrong:

Wrong index on…What happens
inline array, constantdoes not build: index 7 is out of range…
inline array, computedthe program stops: Panic: index out of range
dynamic array, Getreturns none
dynamic array, Setthrows IndexOutOfRange

A dynamic array reports the mistake in its types, so the program decides what to do with it:

PrintLine("copy[9]         {}", copy.Get(9) ?? -1);
try copy.Set(9, 1) catch {
    e => { PrintLine("copy.Set(9)     failed: {}", e); }
};

Get(9) is none, and the ?? turns it into -1. Set(9, 1) throws, and the catch arm prints the error: index the collection does not have.

Owned, not copied

One more difference. An inline array is a plain value, copied by =. A dynamic array owns its block, and two arrays must never think they own the same one — so it cannot be copied. You move it with move instead, and the old name can no longer be used. When squares and copy go out of scope, each gives its block back to the allocator.

Inline int32[4]Array<int32>Vector<int32>
Length decidedwhile compilingat run timeat run time
Length changesneverneverwith every push
Elements livein the array itselfin a block from an allocatorin a block from an allocator
=copiesrefused — move itrefused — move it
Wrong indexbuild error or panicnone or a thrown errornone or a thrown error

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

Src/Main.rux
// An inline array, `int32[4]`, carries its length in its type. The compiler fixes it, and the
// elements live wherever the array itself lives — inside a local, a struct, another array.
//
// Sometimes the length is only known once the program runs: a count read from a file, a size
// passed in by a caller. `Collections::Array<T>` is for that case. It asks an allocator for a
// block of the length you choose at run time, and once made, that length never changes. It is
// not a vector: there is no `Push`. A fixed run whose size is decided late is the whole idea.
import Allocator::{ Allocator, SystemAllocator };
import Collections::{ Array, CollectionError };
import Io::{ Print, PrintLine };

// The length arrives as an ordinary parameter. `int32[count]` would be rejected, because an
// inline array's length must be known while compiling; a dynamic array has no such limit.
func Squares(allocator: Allocator, count: uint) -> Array<int32> throws CollectionError {
    // `Filled` makes `count` copies of one value. `Set` can fail, so `Squares` declares `throws`.
    var squares = Array::Filled<int32>(allocator, count, 0);
    for i in 0..count {
        try squares.Set(i, (i * i) as int32);
    }
    // The array owns its block, so returning it moves the block out to the caller.
    return move squares;
}

func Main() throws CollectionError {
    let allocator = SystemAllocator();

    let primes: int32[4] = [2, 3, 5, 7];
    PrintLine("inline length   {}", primes.length);

    var squares = try Squares(allocator, 6);
    Print("squares        ");
    for value in squares {
        Print(" {}", value);
    }
    PrintLine("   (length {})", squares.Length());

    // `FromSlice` copies an inline array onto the heap. The copy is independent: changing it
    // leaves the original alone.
    var copy = Array::FromSlice<int32>(allocator, primes);
    try copy.Set(0, 99);
    PrintLine("copy[0]         {}, primes[0] still {}", copy.Get(0) ?? -1, primes[0]);

    // Both kinds check an index, but they differ in what a wrong one costs. On an inline array,
    // a constant index past the end does not build, `primes[7]` being "index 7 is out of range
    // for an array of 4 elements", and a computed one stops the program with "Panic: index out
    // of range". A dynamic array's `Get` and `Set` report it in their types instead: `Get`
    // returns `none`, and `Set` fails with `IndexOutOfRange`, so the program decides what to do.
    PrintLine("copy[9]         {}", copy.Get(9) ?? -1);
    try copy.Set(9, 1) catch {
        e => { PrintLine("copy.Set(9)     failed: {}", e); }
    };

    // One more difference: an inline array is copied by `=`, but a dynamic array owns its block
    // and cannot be copied. Writing `let other = copy;` is rejected; `let other = move copy;`
    // moves it.
    // When `squares` and `copy` go out of scope, each gives its block back to the allocator.
}

Besides Io, its Rux.toml lists Allocator and Collections under [Dependencies].

Run it

cd Examples/Collections/DynamicArray
rux run
inline length   4
squares         0 1 4 9 16 25   (length 6)
copy[0]         99, primes[0] still 2
copy[9]         -1
copy.Set(9)     failed: index the collection does not have

Common mistakes

Try it yourself

  1. Change Squares to Cubes, returning an Array<int64>.
  2. Make an array of 10 copies of -1 with Filled, and set every third element to its index.
  3. Write let other = copy;, read the error, then fix it with move. What happens if you use copy afterwards?
  4. Push a few values into a Vector<int32>, then freeze them into an Array<int32> with ToArray().

Learn more

  • Array — inline arrays, whose length is part of the type
  • Vector — the growable sequence
  • Move — handing ownership on with move
  • Arrays in the Rux Reference