Checking at compile time that arena memory can't escape its block

Fels is a small systems language I've been building since June. It has no garbage collector. Memory lives in zones: arenas that are freed when their block ends. This post shows how the compiler makes sure nothing you allocate in a zone is used after the zone is gone, and where that check still has holes.

Why arenas need a check

An arena is the simplest allocator there is. It hands out memory from a big block by moving a pointer forward, and it frees everything at once at the end. There is no free per allocation, and allocating costs a few instructions.

The catch is the end. Once the arena is gone, every pointer into it dangles. In C or Zig nothing stops you from keeping one: you can return it, store it in a struct that lives longer, or hand it to a function that saves it. The program may even keep working until the memory is reused, and then it breaks somewhere else.

I wanted arenas without that catch, and without the weight of a full borrow checker.

Zones

A zone is an arena with a name and a block. Whatever you allocate in it lives until the block ends, and then all of it goes away in one step. You never call free, and nothing runs in the background.

#import std.io.{ println };

// The upper-case letters of `buf`, counted. It borrows `buf`: it may read and change it,
// but it cannot keep it.
count_upper :: fn(buf: borrow []u8) -> i32 {
    n: i32 = 0;
    for i in 0..buf.len {
        if buf[i] >= 'A' && buf[i] <= 'Z' { n += 1; }
    }
    return n;
}

main :: fn() -> i32 {
    total: i32 = 0;
    zone scratch: Arena {
        line := scratch.dupe(u8, "Fels Zones Are Arenas");
        total = count_upper(line);    // a borrow: fine
        first := line[0];             // a byte read out of the zone: a plain value
        total += first as i32 - 'F' as i32;
    }                                 // `line` is freed here
    println("{total} capitals");
    return total;
}

This prints 4 capitals. The copy of the text lives in scratch. count_upper may use it because its parameter says borrow. The count and the byte read out of the zone are plain numbers, so they are free to leave the block.

What the compiler refuses

There are three ways for zone memory to outlive its zone. Each one is a compile error.

Returning it.

// Copies `text` and makes its letters upper case.
shout :: fn(text: []const u8) -> []u8 {
    zone scratch: Arena {
        loud := scratch.dupe(u8, text);
        for i in 0..loud.len {
            if loud[i] >= 'a' && loud[i] <= 'z' { loud[i] -= 32; }
        }
        return loud;
    }
}

error: zone-owned value from `scratch` cannot be returned
  --> ret.fels:8:9
  │
8 │         return loud;
  │         ^^^^^^^^^^^^

Storing it in something that lives longer.

main :: fn() -> i32 {
    keep: []u8 = .{};
    zone scratch: Arena {
        buf := scratch.new_slice(u8, 16);
        keep = buf;
    }
    return keep.len as i32;
}

error: zone-owned value from `scratch` cannot escape its zone
  --> outer.fels:5:9
  │
5 │         keep = buf;
  │         ^^^^^^^^^^^

Passing it to a function that could keep it. println takes a plain slice, so nothing stops it from saving one. Only a borrow parameter promises not to.

#import std.io.{ println };

main :: fn() -> i32 {
    zone scratch: Arena {
        greeting := scratch.dupe(u8, "hello");
        println(greeting);
    }
    return 0;
}

error: zone-owned value from `scratch` can only be passed to a `borrow` parameter
  --> pass.fels:6:17
  │
6 │         println(greeting);
  │                 ^^^^^^^^

Ownership follows the value. A slice of zone memory, a field of it, and a struct built from it all belong to the zone too:

Line :: struct { text: []u8, number: i32 }

numbered :: fn(n: i32) -> Line {
    zone scratch: Arena {
        text := scratch.dupe(u8, "line");
        line: Line = .{ text, n };
        return line;    // error: zone-owned value from `scratch` cannot be returned
    }
}

The same goes for a borrow parameter itself. A function may read and change what it borrows, and pass it on to other borrow parameters, but it cannot return it:

first_word :: fn(text: borrow []u8) -> []u8 {
    i: usize = 0;
    while i < text.len && text[i] != ' ' { i += 1; }
    return text[0..i];    // error: borrowed value from `text` cannot be returned
}

How the check works

There are no lifetime annotations. The only word you ever write is borrow, on a parameter, never at a call. The check runs inside the type checker, one function at a time, with no extra pass.

For every value that holds zone memory, the checker keeps a small record: the zone that owns it, and how deeply nested the zone's block is. Everything else follows from a few rules:

1. Allocating gives a value its owner. A call like scratch.dupe(...), scratch.new_slice(...) or scratch.alloc(...) on a zone handle returns memory owned by that zone.
2. What you make from an owned value is owned too. A slice of it, a field of it, an element, a cast, an address taken from it, an if or match that may give it, a closure that captures it, and a struct or array literal that holds it all have the same owner. Only types that can carry a pointer carry an owner. A byte or a length read out of zone memory is a plain number, so it may go anywhere.
3. An assignment passes the owner on. The variable the value lands in becomes owned by the zone as well. If that variable was declared outside the zone's block, it would outlive the memory, and that is the escape error.
4. Returning an owned value is an error, and so is passing it to any parameter that is not borrow.
5. A borrow parameter is an owner of its own kind. Inside the function the borrowed value can be read, changed and passed to other borrow parameters. It cannot be returned, stored through a pointer, or put into a global.

That is the whole idea: ownership belongs to names and scopes, not to types, so it costs almost nothing to check. The same machinery keeps a function from returning the address of one of its own locals, or storing it in a global.

What it does not catch

The check follows values through names, expressions and closures, but not through everything. Two roads stay open:

unsafe { addr = p as usize; }                     // a pointer turned into a number
register(fn() -> usize { return buf.len; });     // a closure handed to a function that keeps it

The first is what unsafe is for: a pointer turned into a number is just a number. The second is a trade-off. A function value cannot be a borrow parameter, so refusing every closure over zone memory as an argument would forbid comparators and callbacks too. A function that saves a closure it was given can carry zone memory past the zone.

Two more roads were open until this week: a value passed through an if or match expression, and a closure stored in a variable outside the zone. Writing this post turned them up, and both are compile errors now.

Try it

Fels is on GitHub at github.com/fels-lang/fels. The release download is for Windows; on Linux you build the compiler from source. The full rules for zones and borrow are in Memory and zones.

If you try it, I would love to hear where the check gets in your way, and where it lets something through that it should not.