use case: comptime allocator

[andrewrk]

Here's an attempt at implementing the Allocator interface at compile-time:

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

comptime {
    var map = std.AutoArrayHashMap(i32, i32).init(comptime_allocator);
    map.put(12, 34) catch unreachable;
}

pub const comptime_allocator: Allocator = .{
    .ptr = undefined,
    .vtable = &comptime_allocator_vtable,
};

const comptime_allocator_vtable: Allocator.VTable = .{
    .alloc = comptime_alloc,
    .resize = comptime_resize,
    .free = comptime_free,
};

inline fn comptime_alloc(
    context: *anyopaque,
    comptime len: usize,
    comptime log2_align: u8,
    return_address: usize,
) ?[*]u8 {
    _ = context;
    _ = return_address;
    const S = struct {
        var bytes: [len]u8 align(1 << log2_align) = undefined;
    };
    return &S.bytes;
}

fn comptime_resize(
    context: *anyopaque,
    buf: []u8,
    log2_buf_align: u8,
    new_len: usize,
    return_address: usize,
) bool {
    _ = context;
    _ = log2_buf_align;
    _ = return_address;
    // Always returning false here ensures that callsites make new allocations that fit
    // better, avoiding wasted .cdata and .data memory.
    return false;
}

fn comptime_free(
    context: *anyopaque,
    buf: []u8,
    log2_buf_align: u8,
    return_address: usize,
) void {
    _ = context;
    _ = buf;
    _ = log2_buf_align;
    _ = return_address;
}

After #4298 is solved:

--- a/lib/std/mem/Allocator.zig
+++ b/lib/std/mem/Allocator.zig
@@ -223,8 +223,6 @@ fn allocBytesWithAlignment(self: Allocator, comptime alignment: u29, byte_count:
     }
 
     const byte_ptr = self.rawAlloc(byte_count, log2a(alignment), return_address) orelse return Error.OutOfMemory;
-    // TODO: https://github.com/ziglang/zig/issues/4298
-    @memset(byte_ptr[0..byte_count], undefined);
     return @as([*]align(alignment) u8, @alignCast(byte_ptr));
 }
 
@@ -293,8 +291,6 @@ pub fn reallocAdvanced(
         return error.OutOfMemory;
     const copy_len = @min(byte_count, old_byte_slice.len);
     @memcpy(new_mem[0..copy_len], old_byte_slice[0..copy_len]);
-    // TODO https://github.com/ziglang/zig/issues/4298
-    @memset(old_byte_slice, undefined);
     self.rawFree(old_byte_slice, log2a(Slice.alignment), return_address);
 
     const new_bytes: []align(Slice.alignment) u8 = @alignCast(new_mem[0..byte_count]);
@@ -309,8 +305,6 @@ pub fn free(self: Allocator, memory: anytype) void {
     const bytes_len = bytes.len + if (Slice.sentinel != null) @sizeOf(Slice.child) else 0;
     if (bytes_len == 0) return;
     const non_const_ptr = @constCast(bytes.ptr);
-    // TODO: https://github.com/ziglang/zig/issues/4298
-    @memset(non_const_ptr[0..bytes_len], undefined);
     self.rawFree(non_const_ptr[0..bytes_len], log2a(Slice.alignment), @returnAddress());
 }

I believe there is only one problem left:

test.zig:15:6: error: expected type '*const fn (*anyopaque, usize, u8, usize) ?[*]u8', found '*const fn (*anyopaque, comptime usize, comptime u8, usize) callconv(.Inline) ?[*]u8'
    .alloc = comptime_alloc,
    ~^~~~~~~~~~~~~~~~~~~~~~
test.zig:15:6: note: pointer type child 'fn (*anyopaque, comptime usize, comptime u8, usize) callconv(.Inline) ?[*]u8' cannot cast into pointer type child 'fn (*anyopaque, usize, u8, usize) ?[*]u8'
test.zig:15:6: note: generic function cannot cast into a non-generic function
referenced by:
    comptime_allocator: test.zig:11:16
    comptime_0: test.zig:5:51

I think this would have already been working if we hadn't changed the Allocator interface from good ol' @fieldParentPtr to vtables.

But anyway, I think the language rules can be relaxed. This coercion can be allowed as long as it makes the value a comptime-only value. In other words, function pointers are allowed to point to inline functions as long as the function pointer value is comptime-known. Attempt to coerce the function pointer to a runtime-known value would yield a compile error.

And then everything should work fine.

[andrewrk]

Perhaps related to #130

[Hejsil]

We probably don't need @getNextGloballyIncrementingInteger() for uniqueness, as that is what we have @OpaqueType for. We could probably pass @OpaqueType to ComptimeAllocator.init to ensure that all calls are never cashed (index would now be of type type and would be reassigned to a new @OpaqueType in alloc)

[andrewrk]

I had a second pass at this, and it almost all worked, except for:

In std.mem.Allocator, setting the bytes to undefined didn't work at comptime.

Which is a legitimate problem. Because this is trying to, at comptime, do a @memset of a global variable (runtime memory) to undefined. Trying to use this memory at comptime wouldn't work either, again because it is runtime memory.

Related - I had a conversation with @cavedweller about this the other evening, and he pointed out an important use case: freeing the memory. With a pure userland solution to this, as you can see, there is no freeing memory. All comptime-allocated memory escapes, because @ptrToInt or similar could have been using. However if we introduce a compiler builtin which is capable of freeing memory, this allows the following use cases to work:

• comptime code wants to use structures that require heap allocation, but will leave no memory used after it is done. Nothing is actually emitted to the .data section when the build completes.
• comptime code wants to allocate memory, and keep it allocated, initialize some stuff, and then leave it initialized, using standard data structures that expect allocators.
• some mix of both.

My proposal for this builtin would be:

@comptimeRealloc(old_mem: []u8, new_size: usize, new_align: u29) []u8

Notably, comptime allocation doesn't fail - that would be a compile error! To allocate fresh memory, pass a zero-length slice for old_mem.

The returned byte slice would point to memory that is comptime-mutable within the current comptime scope. Outside that scope, the memory would be either runtime-mutable or runtime-const, depending on where the memory escaped to outside the comptime scope.

One problem to solve with this proposal would be the lingering reference to a comptime allocator. As an example:

const std = @import("std");

const foo = comptime blk: {
    var comptime_alloc_state = ComptimeAllocator.init();
    const allocator = &comptime_alloc_state.allocator;

    var list = std.ArrayList(i32).init(allocator);
    list.append(10) catch unreachable;
    list.append(20) catch unreachable;
    break :blk list;
};

pub fn main() void {
    std.debug.warn("list[0]={}\n", foo.at(0));
    std.debug.warn("list[1]={}\n", foo.at(1));
}

const Allocator = std.mem.Allocator;
const assert = std.debug.assert;

const ComptimeAllocator = struct {
    allocator: Allocator,

    fn init() ComptimeAllocator {
        return ComptimeAllocator{
            .allocator = Allocator{
                .reallocFn = realloc,
                .shrinkFn = shrink,
            },
        };
    }

    fn realloc(allocator: *Allocator, old_mem: []u8, old_align: u29, new_size: usize, new_align: u29) Allocator.Error![]u8 {
        return @comptimeRealloc(old_mem, new_size, new_align);
    }

    fn shrink(allocator: *Allocator, old_mem: []u8, old_align: u29, new_size: usize, new_align: u29) []u8 {
        return @comptimeRealloc(old_mem, new_size, new_align);
    }
};

Clearly the example wouldn't work if we made foo a var instead of const and then tried to append. But what about other methods that want to mutate state but don't mess with the comptime allocator reference? Theoretically that should work. I think trying to implement this would make the problems and potential solutions more clear.

[rohlem]

First off, the solution with the smallest-footprint change could look like this:

@comptimeRealloc(old_mem: []u8, new_size: usize, new_align: u29) ?[]u8 //returns null if evaluated at runtime

---

For a more thorough and "optimal" concept, maybe I'm just stating the obvious here, I'll try to keep it short; this is how my mind completes/solves the last comment's perspective:

• Supposing @comptimeRealloc, calling this function only seems sensible in a comptime context/block. In this way, it's in the same "comptime-only" category as ++, or handling instances of type type.
• If our main motivation is to "enable runtime concepts at comptime", we could automatically flag [expressions / blocks / code paths] as "comptime-only" if they unconditionally contain "comptime-only" operations. This would work similarly to the flagging of async functions if they contain suspend/await, but not necessarily bubbling up to function scope, because it doesn't affect calling convention.
• Entering a "comptime-only" block in a runtime context would be equivalent to unreachable - panic in safe builds, UB in unsafe builds.

If this design is accepted, the implementation of comptime variants can use the same interface as a runtime variant - in the case of allocators, the allocate function would unconditionally contain @comptimeRealloc, marking the surrounding block as "comptime-only". Therefore any runtime control flow that ends up there triggers (in safe build modes) a stack trace like f.e.:

comptime_allocator.zig:xx - Error: comptime-only block entered at runtime
comptime_allocator.zig:xy - Note: Block is marked comptime-only because of use of `@comptimeRealloc` here.
std/array_list.zig:zz - called from here ...

For the purpose of code-deduplication, maybe something like #868 could also help in usage:

if(@weAreInComptime())
  return comptime_allocator.allocate(T);
else
  return error.OnlySupportedAtComptime;

[rohlem]

EDIT2: Looks like I commented without doing proper research/testing again. Sorry for the noise.
(After further testing, it appears that comptime-caching with @fieldParentPtr already does what I proposed before this edit, and some forms of fixed-buffer allocators already work during comptime (with certain limitations).)
This discussion is therefore about the semantics behind transferring comptime-initialized memory to runtime-usable (global) memory. Seems I misinterpreted what the actual issue was before.
EDIT3: After a couple more tries, I did get something up and running with status-quo language semantics (only requiring a couple workarounds in std/mem.zig to be more comptime-friendly): see my branch . ( maybe see also irc discussion, if something about my approach still seems unclear )

[ghost]

@rohlem: I don't think we want to draw a hard line between comptime and runtime code here. After all, a key feature of comptime is the ability to integrate with runtime program flow (see: comptime var). A much simpler restriction would be to require the arguments of these builtins to be comptime-known. I'll open a concrete proposal.

Also, #5675 could be helpful here in any case.

[ghost]

I've proposed a reworking of comptime semantics (#5895) to accommodate this use case.

[glyh]

I run into this when trying to port ctregex to zig 0.13, what is the status of this issue? Is this abandoned or implemented?

[andrewrk]

I updated the OP with a fresh writeup. In summary:

• This is definitely within the grasp of the Zig language.
• set memory to undefined in allocator implementations rather than interface #4298 is an easy prerequisite
• Last remaining task is to make a proposal to allow inline functions to coerce to function pointers as long as the value is and remains comptime-known.

[mlugg]

Additionally, one of the biggest thing blocking any Allocator from being useful at comptime (e.g. FBA) is memory reinterpretation rules. Allocating something with a well-defined layout with a comptime FBA probably works today, but allocating something with ill-defined layout (e.g. an auto-layout struct) currently fails because we try to reinterpret the u8 buffer to this different type at comptime, which emits a compile error.

There is a plan for this, discussed in a compiler meeting a while back -- the comptime pointer access rules should be relaxed, so that instead of emitting an error, accessing this kind of reinterpreted pointer works fine, but always spits out undefined when switching from a well-defined to ill-defined layout or vice versa.