Referencing other structs in an array at comptime

Help
,
1

Hey all,

I’m pretty new to zig but I’m absolutely loving it so far. Right now I’m trying to, at comptime, generate a tree where the nodes are all in some shared array and point to each other, but I can’t quite figure out how to do that with the new comtime var changes.

I created a simplified example to test what I’m trying to do:

const BoundedSR10 = std.BoundedArray(SelfRefStruct, 10);
const SelfRefStruct = struct {
    data: u8,
    next: *const @This(),
};

const ArrOfSelfRef = struct {
    list: []const SelfRefStruct,
    first: *const SelfRefStruct,
};

fn generateSelfRefData() ArrOfSelfRef {
    var list: BoundedSR10 = try BoundedSR10.init(0);

    try list.append(.{ .data = 'p', .next = undefined });

    try list.append(.{
        .data = 'a',
        .next = &list.slice()[0],
    });
    list.slice()[0].next = &list.slice()[1];

    const listConst = list.constSlice()[0..].*;
    
    // @compileLog(listConst);
    return .{
        .list = &listConst,
        .first = &listConst[0],
    };
}

test "Self Ref Test" {
    const fakeReffingData = comptime generateSelfRefData();
    // @compileLog(fakeReffingData);
    print("{any}", .{fakeReffingData});
}

When calling print it gives the “runtime value contains reference to comptime var” error. This makes perfect sense considering all of my pointers are pointing into the bounded array which is mutable.
I just can’t quite figure out how to get them to point into the const array, since in order to get that address the array needs to exist, but if it exists then I can’t update its values to make them point into it.
I could change the second field of the struct to store an index into the array instead of a pointer (still might do that), but that’s less fun and and I would love to know if there’s a way to accomplish this with pointers, as I’m sure there’s something I’m overlooking.
Thanks in advance!

P.S. I also think I found a bug. If I uncomment the @compileLog in the test zig crashes with SIGSEGV. Running it with lldb and printing the backtrace shows over 50,000 frames on the call stack. Prolly some recursion thing? Idk but this does not happen with the @compileLog in the function. No clue if this is known, but I figured I’d mention it. I’m on M1 Mac in case that helps.

2

Hi @ParkerHitch welcome to ziggit :slight_smile:

You must not use undefined as null.

const SelfRefStruct = struct {
    data: u8,
    next: ?*const @This(),
};

fn generateSelfRefData() ArrOfSelfRef {
    ...
    try list.append(.{ .data = 'p', .next = null });
    ...

list is a local variable allocated in stack, its life ends when generateSelfRefData function returns.

fn generateSelfRefData() ArrOfSelfRef {
    var list: BoundedSR10 = try BoundedSR10.init(0);
    ...

After generateSelfRefData returns, the pointers in the returned struct point to stack data that are replaced by the next function calls.

One way to solve the problem is to declare the list in a place with bigger lifetime. It can be a global, or passed to the function.

fn generateSelfRefData(list: BoundedSR10) ArrOfSelfRef {
    try list.append(.{ .data = 'p', .next = null });
    ...
}

test "Self Ref Test" {
    const list = try BoundedSR10.init(0);
    const fakeReffingData = comptime generateSelfRefData(list);
    ...
}
1 Like
3

Hi @dimdin!

Thanks for the reply. I will absolutely change the pointer to an optional when needed I just made that quick for the example since it isn’t really nullable, more just waiting to be initialized.

As for making the list available to a greater scope that does kind of help but my main goal here is to have the contents of list be available at runtime.
In order to get it passing to the function I had to change the function a bit and write the test like this:

test "Self Ref Test" {
    comptime var list: BoundedSR10 = try BoundedSR10.init(0);
    const fakeReffingData = comptime generateSelfRefData(&list);
    print("{any}", .{fakeReffingData});
}

But I think this just makes the problem more visible. The items inside of list point to other items in list. List is a comptime var. I want to use the contents of list at runtime. Because of the recent changes we can’t have references to comptime vars at runtime, hence I’m looking for help on how to transfer the contents of list into a constant array once I’m done generating them, and keep their references to each other, just in the context of this new array.

It might not be possible but that’s ok.
Again super apprecieate the help and the tips on scope and optional.

4

I think you would need to know the final address of the array.
I have never used linker scripts or looked into them in detail, but I think they could be used to do things like that? (Place something at a specific location in memory)

If you had the final address you could pre-calculate all the pointers with the fixed address as the base pointer and then copy it over to the const.
I haven’t had a reason to try something like this, so I am not sure if it would work, or whether it would be difficult.

1 Like
5

This is some code that precomputes 10^0 upto 10^32 at compile time using the init_exp10 function.
Function exp10 returns the precomputed value from the array.

const std = @import("std");
const assert = std.debug.assert;

const max_precision = 32;

// returns 10^scale
fn exp10(scale: u8) u128 {
    assert(scale <= max_precision);

    const S = struct {
        fn init_exp10(comptime T: type) T {
            var exps: T = undefined;
            var current: u128 = 1;
            exps[0] = current;
            for (0..max_precision) |i| {
                current *= 10;
                exps[i + 1] = current;
            }
            return exps;
        }

        const exp10 = init_exp10([max_precision + 1]u128);
    };

    return S.exp10[scale];
}

test exp10 {
    const data = [_]u128{ 1, 10, 100, 1000, 10_000, 100_000, 1_000_000 };
    for (data, 0..) |v, i| {
        try std.testing.expectEqual(v, exp10(@intCast(i)));
    }
}

You can do the same with an array instead of the BoundedSR10, and integer indexes instead of pointers.

2 Likes
6

I think avoiding pointers like @dimdin suggests is probably the best solution.
But I had another possible idea, use page mapping techniques to map the data of the array residing in const memory at some specific virtual address, then access that data through that view at the specific address.

I guess one problem would be if that specific virtual address is already used and you may not want to use manual page mapping.

1 Like
7

@Sze both of those solutions sound actually really cool but maybe a tad out of scope for me at the moment lol.
I’m gonna do as @dimdin suggested and stick to ints for indecies instead of pointers.
Thank you both for the ideas and help!

2 Likes
8

Zig would treat a struct as a runtime type when it contains only runtime types. It’ll complain when you stick a pointer to a comptime var into it. The trick is to have a comptime type like type or comptime_int somewhere. The following works, for example:

const std = @import("std");
const print = std.debug.print;

const SelfRefStruct = struct {
    data: u8,
    next: ?*const @This(),
    nothing: @TypeOf(null) = null,
};

const ArrOfSelfRef = struct {
    list: []const SelfRefStruct,
    first: *const SelfRefStruct,
};

fn generateSelfRefData() ArrOfSelfRef {
    comptime var array: [10]SelfRefStruct = undefined;
    array[0] = .{ .data = 'p', .next = &array[1] };
    array[1] = .{ .data = 'a', .next = null };
    return .{
        .list = &array,
        .first = &array[0],
    };
}

test "Self Ref Test" {
    const fakeReffingData = generateSelfRefData();
    print("\n", .{});
    print("{any} {any}\n", .{ fakeReffingData.first.data, fakeReffingData.first.next.?.data });
}

@TypeOf(null) is comptime, that makes SelfRefStruct comptime, which in turn makes ArrOfSelfRef comptime. Pointing to the comptime var array therefore does not cause an error. nothing can be in ArrOfSelfRef too.

2 Likes
9

Interesting trick.
Returning the array also works:

const std = @import("std");
const print = std.debug.print;

const SelfRefStruct = struct {
    data: u8,
    next: ?*const @This(),
};

fn generateSelfRefData() [10]SelfRefStruct {
    comptime var array: [10]SelfRefStruct = undefined;
    array[0] = .{ .data = 'p', .next = &array[1] };
    array[1] = .{ .data = 'a', .next = null };
    return array;
}

test "Self Ref Test" {
    const fakeReffingData = comptime generateSelfRefData();
    print("\n{c} {c}\n", .{ fakeReffingData[0].data, fakeReffingData[0].next.?.data });
}

The question is: Will &array[1] continue to work in future zig versions?

10

Using a pointer here is not the best choice, since that keeps you from reinitializing the struct with a bigger array. An index would make more sense. Maybe make it comptime_int to eliminate the need for the dummy field.

1 Like
11

I just tried compiling a small variation of this example, in which I access the first two elements of array via a loop:

const std = @import("std");
const print = std.debug.print;

const SelfRefStruct = struct {
    data: u8,
    next: ?*const @This(),
};

fn generateSelfRefData() [10]SelfRefStruct {
    comptime var array: [10]SelfRefStruct = undefined;
    array[0] = .{ .data = 'p', .next = &array[1] };
    array[1] = .{ .data = 'a', .next = null };
    return array;
}

pub fn main() void {
    const fakeReffingData = comptime generateSelfRefData();
    for (0..1) |i| {
        print("{c}", .{fakeReffingData[i].data});
    }
}

This code not only fails to compile with this loop, but the error message is basically opaque:

$ zig build run
run
+- run zig-play
   +- zig build-exe zig-play Debug native failure
error: the following command exited with error code 3:
C:\tools\zig-dev\zig.exe build-exe -ODebug -Mroot=C:\Users\biosb\zig\zig-play\src\main.zig --cache-dir C:\Users\biosb\zig\zig-play\zig-cache --global-cache-dir C:\Users\biosb\AppData\Local\zig --name zig-play --listen=-
Build Summary: 2/7 steps succeeded; 1 failed (disable with --summary none)
run transitive failure
+- run zig-play transitive failure
   +- zig build-exe zig-play Debug native failure
   +- install transitive failure
      +- install zig-play transitive failure
         +- zig build-exe zig-play Debug native (reused)
error: the following build command failed with exit code 1:
C:\Users\biosb\zig\zig-play\zig-cache\o\074cf8b1e6d684493d443d6f6d3dbab6\build.exe C:\tools\zig-dev\zig.exe C:\Users\biosb\zig\zig-play C:\Users\biosb\zig\zig-play\zig-cache C:\Users\biosb\AppData\Local\zig --seed 0xe625a989 -Zad55c03e619be54f run

I’m still trying to find a solution to the dependency loop issue described here, and was intrigued by how this array was initialized at comptime.

But correct me if I’m wrong, but I can’t really use this technique to initialize arrays declared at container-scope???

12

Sometimes when zig build run fails like this, you can get the real error by just doing a zig build and then running the executable in zig-out/bin directly.

13

The .exe file was never built; all I have is a .lib file.

It appears that zig build-exe internally returned “error code 3”.