Meta-proposal: Comptime memory management reform

[ghost]

Reconstructed from the corpses of #5675, #5718, #5873, #5874, #5881. I'm sorry.

Comptime Memory Management Reform

Currently, comptime is automatically memory managed, and relies on closure for persistent mutable state. This is good for flexibility, but has a few problems:

• Common tasks have fundamentally different implementations at comptime vs runtime, hindering code reuse
• Execution order is visible from userspace code, leading to inelegant hacks and counterintuitive behaviour
• Complex lifetime-tracking logic is needed in the compiler for efficiency, but
• Applications are locked in to one memory management strategy, which may not be a good fit

I believe we can solve these problems by unifying some aspects of comptime and runtime semantics.

What Should Not Be Allowed

• Closure over local variables. Consider the following code from Proposal: Way to force a struct/type to be distinct/unique #5578:

const testing = @import("std").testing;

fn GiveTwice(comptime valt: type) type {
    comptime var times: usize = 2;
    return struct {
        val: valt,

        const Self = @This();

        pub fn init(_val: valt) Self {
            return Self{ .val = _val };
        }

        pub fn give(self: *Self) valt {
            comptime if (times == 0)
                @compileError("You can only 'give' 2 times");

            times -= 1;

            return self.val;
        }
    };
}

test "Test 1" {
    var a = GiveTwice(usize).init(1);
    _ = a.give();
    _ = a.give();
    _ = a.give(); // <-- Should Fail

    var b = GiveTwice(usize).init(1);
    _ = b.give();
    _ = b.give();
    _ = b.give(); // <-- Should Fail
}

This is currently the only way of bundling comptime state with runtime data, and is used extensively for such applications. The problem is that GiveTwice is memoised, which is necessary for generics, however it means that every call to give references the same times, and every call after the second fails. The user should not have to think about comptime execution order, and yet this enforces it.

• Returning or otherwise exporting pointers to local variables. This has similar problems to the previous point, as well as necessitating potentially infinite lifetimes for objects.
• Assigning to a slice a value of a different length than the slice, like this. This only makes sense if the slice is the only handle on the data it points to, which is difficult to track, and otherwise may cause references to desynchronise.
• Global variables. These have similar problems to closure over local variables.
• Inline assembly. Note this also covers syscalls.

Comptime "superpowers" shall include operations on types and functions, passing anything between functions by value, anytype variables/fields/variants, anytype arrays (where every element is a different type), operations on comptime_int and comptime_float, concatenation (++), repetition (**), and assigning to slices (as long as length is preserved). I think this covers everything currently possible at comptime -- if I've missed anything, let me know.

Crucially, this does not impose all of runtime's restrictions on comptime. Internals of execution may still depend on implicit dynamic allocation -- the key is that this is not exposed to the user, to encourage performant and time-agnostic code.

Alternative Solutions

Misc.

I propose we rename comptime_int and comptime_float to int and float, so field and parameter decls aren't so long and repetitive. This is not without precedent -- we have unadorned comptime-only types (type, fn types once #1717 comes through) and comptime-only operators (++, **, / and % on unsigned integers), int and float would still mean the same thing everywhere, and a comptime annotation would still be required in those places.

Mutability

It is useful to be able to call out to a function to mutate some state. I propose, that when a function receives a comptime parameter with a pointer or slice (reference) type, it will cause operations on that reference to be executed at comptime, much like the semantics of comptime var. Consider the following code:

const std = @import("std");

// Using #1717 syntax because it has been accepted
// -- this proposal does not depend on #1717
pub const main = fn () void {
    comptime var c: int = 1;
    const p = &c;
    var v: u32 = 3;
    const a = &v;
    hybridIncrement(p, a); // Mutates p.* within this scope
    std.debug.print("{}, {}\n", .{c, v}); // 2, 4
};

const hybridIncrement = fn (comptime p: *int, a: *u32) void {
    // p.* acts like a comptime var
    p.* += 1; // executed at comptime
    a.* += 1; // executed at runtime
};

hybridIncrement executes partially at comptime, partially at runtime. Comptime or hybrid-time function calls that pass mutable references shall not be memoised, for predictability -- all other comptime function calls shall be memoised. The values of immutable comptime references are reified to static constants at runtime, unless the value is or contains int or float. References to these values, or the values of mutable comptime references, are forbidden from being read at runtime, and attempted codegen of these will fail compilation -- if the goal is to initialise data with comptime logic, a statically-typed comptime constant must be created, or the values must be explicitly copied over. (Mutable comptime references may have different values throughout the source, so for consistency would need to be instantiated in the output for every access by runtime -- this is unintuitive and wasteful.)

Bundling Comptime State with Runtime Data

I propose we allow structs to exist in hybrid time, like so:

const Box = fn (comptime T: type) type {
    return struct {
        const Self = @This();

        val: T,
        comptime times: int,

        const init = fn (_val: T, comptime _times: int) Self {
            return Self { .val = _val, .times = _times };
        };

        // `comptime` is not needed in this case -- see below
        const give = fn (self: *Self) T {
            // These are executed at comptime
            if (self.times <= 0) @compileError("Gave too many times");
            self.times -= 1;

            // This is executed at runtime
            return self.val;
        };
    };
};

test "Test 1" {
    var runtime_1: usize = 1;
    var a = Box(usize).init(runtime_1, 2);
    _ = a.give(); // ok
    _ = a.give(); // ok
    _ = a.give(); // error: Gave too many times

    // Different instance, different counter
    var b = Box(usize).init(runtime_1, 2);
    _ = b.give(); // ok
    _ = b.give(); // ok
    _ = b.give(); // error: Gave too many times
}

comptime fields may also be anytype. Such structs may not be packed or extern. A pointer to such a struct has a defined runtime representation, that leaves out some fields -- thus, it does not make sense to reify these references to static constants, and so values of this type need not be annotated with comptime or some hypothetical hytime keyword. (For this to be efficient, we would need to implement generic deduplication.)

Acquiring (and Releasing) Memory

At runtime we would leverage syscalls for this, which of course is not possible -- however, we can take inspiration from them. I propose two new builtins: @alloc(T: type, len: int) *[len]T and @resize(buf: *[_]anytype, len: int) void. These can only be run at comptime, and produce comptime values: @alloc returns a mutable buffer, @release resizes it (resizing it to 0 frees it). The compiler guarantees that no allocations will overlap. T may be anytype, and then every element of the buffer may be a different type -- this of course requires implicit dynamic allocation, but in a controlled, defined way that does not necessitate lifetime tracking. The comptime allocation quota is by default set to some small value, say a few kilobytes, and is increased by a command line option, say -Dalloc-quota=3M or something similar -- this accommodates as yet unforeseen uses of comptime without making it too easy to abuse sneakily. The returned space is always mutable, as immutable state can simply be passed by value; alignment is not considered, as the extra cost of misaligned access can be absorbed at comptime; operations will never fail in a program-visible way, as builds must remain deterministic -- if the compiler cannot perform the operation, compilation will simply fail.

With these, defining and using a simple comptime allocator looks like this:

const std = @import("std");
const Allocator = std.mem.Allocator;

// Slightly adjusted for the things #1717 will allow us to do
// -- some details might be wrong, corrections welcome
const comptime_allocator = Allocator {
    .alloc = fn (self: *Allocator, len: usize, ptr_align: u29, len_align: u29) Error![]u8 {
        // Bare @alloc implies that this can only be called at comptime
        return @alloc(u8, len)[0..];
    };

    .resize = fn (self: *Allocator, buf: []u8, new_len: usize, len_align: u29) Error!usize {
        @resize(buf, new_len);
        return buf;
    };
};

// taken from https://github.com/Vexu/routez/blob/1e87f10d0c0a238ddedca29f38d9fb9e836958e7/src/routez/router.zig
// and edited -- this is not valid Zig code, some liberties were taken, but the point should be clear
pub const Router = fn (comptime handlers: anytype) HandlerFn {
    comptime var routes = std.ArrayList(Route).init(comptime_allocator);
    // We'd also need to be able to do this
    comptime errdefer routes.deinit();
    comptime var err_handlers = std.ArrayList(ErrorHandler).init(comptime_allocator);
    comptime errdefer err_handlers.deinit();

    inline for (handlers) |handler| {
        switch (@TypeOf(handler)) {
            ErrorHandler => {
                err_handlers.append(handler) catch unreachable; // alloc returns no errors
            },
            Route => {
                routes.append(handler) catch unreachable;
            },
            else => |f_type| @compileError("unsupported handler type " ++ @typeName(f_type)),
        }
    }
    // ...
};

With these changes, we'll be able to use the same techniques at comptime that we can at runtime in more places, and the resulting code for applications will be more efficient and easier to manage. Furthermore, the user will have a much easier time reasoning about the semantics of comptime code.

Addendum: The Branch Quota

Currently, there is a single global branch quota that cannot be read. This has two problems.

Firstly, an irresponsible author of a long-running calculation may, instead of reasoning about its behaviour, choose to simply increment the quota in a loop, bypassing the purpose of a quota altogether:

comptime var q = 1001;
inline while (some_condition) : (q += 1) {
    @setEvalBranchQuota(q);
    // As long as no more than 1000 branches have already been taken,
    // whatever follows is guaranteed to never exceed the quota
}

Secondly, a responsible author who wishes to increase the quota must take a blind guess as to how many branches have already been taken:

// Say we expect the loop to take up to 500 iterations
// -- we wish to add 500 to the quota to guarantee success
@setEvalBranchQuota(1500); // No good;
// the quota has already been increased to 2000,
// and 1400 branches have been taken
inline while (some_condition) {
    // After 100 iterations, compilation fails
}

Allowing the quota to be read solves the second problem but worsens the first; restricting @setEvalBranchQuota to global scope solves the first but worsens the second.

I propose that we abolish @setEvalBranchQuota entirely, in favour of a new builtin: @addBranchQuota(comptime q: int) void. This may only be called within linear scope. It imbues the scope with a branch quota of its own initialised to q, counted separately from the global quota, and only valid within that scope. A branch first draws from its own scope's quota, then when that is exhausted (or if it does not exist) it draws from the enclosing linear scope's quota if applicable, then from the calling function's quota, and so on up the call stack until it reaches the global quota. A loop repeat draws from the scope surrounding the loop and not the loop itself, so a loop cannot increment its own quota to infinity; branch debt flows up the dynamic call graph, so the compiler can generate an exact trace of any overdraw. For reproducibility (specifically, order-independence), memoised functions also cache their branch debt, and this is counted for each invocation.

The following actions draw from the quota:

• Repeating a while loop
• Function recursion
• Inline expansion recursion

These are the only actions which could potentially loop infinitely -- note especially that for loops are not included, as they iterate up to a fixed number of times. A function or inline expansion recursion draws from the scope containing the earliest invocation -- otherwise a function could call itself and increment its own quota (other actions still draw from the innermost local quota). If the compiler decides to pre-compute values not explicitly marked as comptime, or inlines non-inline functions or loops, the mechanism for bounding these actions is internal to the compiler and separate from the local quota -- it would be unfair and unpredictable to do otherwise.

Increasing the global quota cannot be done from within the program -- it requires a command line option, say -Dbranch-quota=2000 or something similar, just like the acquire quota. (The added complexity of a local quota system does not make sense for allocations -- the concept of memory footprint is an implementation detail at comptime, and the compiler can benefit from freedom of allocation representation to save space, so debting a specific amount of memory to each scope would be impractical and inefficient.)

[pixelherodev]

I don't have time to read this over properly, the one thing I will say is I think there should be a defined, relatively small limit on how much memory can be acquired at comptime.

[ghost]

Updated the proposal with one possible mechanism for this.

[pixelherodev]

I don't think a builtin to update it helps; there should be a finite limit to how much memory a program is allowed to demand at compile time.

For instance, under no circumstances should a program ever reach the GiB range at comptime. That's very clearly an abuse of the compile time mechanisms, and there's no reason to allow it.

[ghost]

I'm hesitant to include such a restriction, as we may disallow as yet unforeseen legitimate use cases -- however, I do recognise the danger of giving the program too much control. Updated with possibly a better solution.

[ghost]

With #7396, the crux of this proposal (eliminating comptime closure) can be assumed, hence the individual concepts presented make sense on their own. On advice of the committee, selected individual proposals have been reopened/created, and this amalgam is obsolete.