Proposal: Comptime allocator builtins

[ghost]

Inspired by #1291.

The current mechanism to obtain persistent mutable state at comptime is closure. I hate comptime closure with a passion that burns with the strength of a thousand white suns. Not only does it violate language principles, it's inefficient for applications that do heavy computations at comptime (regex, interfaces, perfect hash etc.). I sincerely hope #5718 will make it die. In that case, though, we'll need a new way to get mutable state, that doesn't rely on system memory or syscalls at a program level. (Moot with #7396, but maybe there's still some value here.)

I propose two new builtins: @alloc(T: type, len: usize) *[len]T and @resize(buf: *[_]anytype) void. These can only be run at comptime, and produce comptime values. They work as if invoked from a single, global, comptime allocator. One could then implement an analogue of std.heap.page_allocator on top of these, and we're off to the races.

Musings:

• I initially thought of copying the standard allocator interface, however this would have required a choice of either the allocator itself or the allocation functions as the primitive, as well as a lot of implementational complexity either way. Also considered was a monomorphic whole page allocator, but this would have been inefficient and difficult for the compiler to manage. (I am now a wiser woman, and feel that Zig rules, POSIX drools.)
• Acquisition cannot fail in a program-visible way -- a failure to allocate is simply a compile error. I don't see a use case for continuing compilation if the system doesn't have memory for it.
• The global memory quota, being not necessarily equal to the data used and easy to abuse sneakily, should be set outside the program with a command line option; say Dmem-quota=3M or something similar. By default it's something small but not useless, say a few kilobytes.
• This creates pointers to comptime data, potentially where runtime code can see it. For safety, we should either null these pointers in codegen or detect erroneous use at comptime (Compiler intelligence: Pointers to comptime data should not be accessible at runtime #5874). (make closure over comptime var a compile error; comptime vars become immutable when they go out of scope #7396 saves the day again.)
• This presents a use case for comptime defer and comptime errdefer, for code that runs on exit from analysis. I feel we should add this, if we go the comptime allocator route.

[ghost]

#5895 encompasses this. Closing.

[ghost]

#7396 being accepted, the components of #5895 are now cohesive on their own, and can be split out.

[ghost]

I know I reopened this, but honestly, it's an awful idea. At comptime you can just declare whatever data you want. If you need an allocator for something that works with the allocator interface, just declare an array and make an FBA. You can always choose the scope that needs the data, since comptime is deterministic. God damn Zig is awesome.

[adlerd]

This issue seems to be the last word on comptime allocation.

I'm not sure that all use-cases are covered by the suggestion to just use a FixedBufferAllocator. One of the purposes of the Allocator API is so that types can calculate how big an allocation needs to be, and go out and do it without having to, say, return the length to a calling function and wait to be called with a bigger buffer. But the proposed solution requires that the caller know exactly how many bytes will be allocated. That information should be encapsulated in the code doing the allocation. And even the code doing the allocation may not be able to predict all at the first call how much will ultimately be allocated; that's why realloc exists.

If it were an acceptable solution to just use an FBA, then this argument would go through equally well at runtime; there's no need for an allocator API in zig at all?

[iagocq]

I know I reopened this, but honestly, it's an awful idea. At comptime you can just declare whatever data you want. If you need an allocator for something that works with the allocator interface, just declare an array and make an FBA. You can always choose the scope that needs the data, since comptime is deterministic. God damn Zig is awesome.

I've been searching for a while on how to do allocations at comptime (I wanted to parse a JSON at comptime that has arrays and strings as values) and found this issue, but this doesn't look like it works.

Using an FBA at comptime seems to fail because std.mem.Allocator.alloc uses @returnAddress().

An example:

fba.zig:

const std = @import("std");

comptime {
    var buf = [_]u8{0} ** 1000;
    var fba = std.heap.FixedBufferAllocator.init(&buf);
    _ = fba.allocator().alloc(u8, 1);
}

pub fn main() void {}

$ zig build-exe fba.zig
/nix/store/vwx73n3xjz83wy7zj98baax3f06zyj6g-zig-0.9.0/lib/zig/std/mem/Allocator.zig:194:62: error: unable to evaluate constant expression
    return self.allocAdvancedWithRetAddr(T, null, n, .exact, @returnAddress());
                                                             ^
./fba.zig:6:30: note: called from here
    _ = fba.allocator().alloc(u8, 1);
                             ^
./fba.zig:3:10: note: called from here
comptime {
         ^
/nix/store/vwx73n3xjz83wy7zj98baax3f06zyj6g-zig-0.9.0/lib/zig/std/mem/Allocator.zig:194:41: note: referenced here
    return self.allocAdvancedWithRetAddr(T, null, n, .exact, @returnAddress());
                                        ^
./fba.zig:6:30: note: referenced here
    _ = fba.allocator().alloc(u8, 1);
                             ^

Any idea on how to proceed?

[rsepassi]

Hitting this snag in comptime. I'm trying to call some functions that expect an Allocator at comptime. I'm fine pre-declaring the memory and using a FixedBufferAllocator. Unfortunately as @iagocq points out, it breaks because of the use of @returnAddress() in Allocator.zig. Judging from @EleanorNB's comment, it seems that using an FBA at comptime worked at some point, but broke since then. Any plans to (re)enable comptime use of the Allocator interface?

[mlugg]

I believe @returnAddress is permitted to return 0 on platforms which don't support it, and I see no reason it couldn't also do that when evaluated at comptime. I'll bring it up in tomorrow's compiler meeting, since I would also like for this use case to work.

[rsepassi]

That'd be awesome, thank you.

[ghost]

Ok fine, since there's still discussion happening here I guess I'll reopen this. But I'm unsubscribing from updates.

[Cloudef]

It would be nice if fixed buffer allocators could be used comptime to increase code reuse.

[nektro]

that's tracked in #14931