Dependency loop in statically-linked array elements

Help
1

here’s a simple program that initializes an array of elements, where the elements themselves are linked to one another via pointers:

const Elem = struct {
    next: ?*Elem,
    data: u32,
};

var table = [_]Elem{
    Elem{ .data = 10, .next = &table[1] },
    Elem{ .data = 20, .next = &table[2] },
    Elem{ .data = 30, .next = null },
};

var head = &table[0];

pub fn main() void {
    var p = head;
    while (p.next != null) : (p = p.next.?) {
        std.log.debug("{d}", .{p.data});
    }
}

needless to say, the compiler gives me a “dependency loop” error…

for reasons unique to my use-case, i’d prefer to statically allocate all of my Elem objects within a single array… i’ve been stuff like this in C forever – but as i’ve come to appreciate, there is probably a “good reason” why zig doesn’t like this…

what’s the best way to approach this in zig???

2

I built something similar to this a while ago using linked lists as a free-list buffer. I just connect them with an initialization call:

// in struct declaration

    const AnyList = std.SinglyLinkedList(*anyopaque);

    const AnyNode = AnyList.Node;

    // node cache...
    free_nodes: AnyList,

    node_buffer: [MAX_NODES]AnyNode,

    pub fn setup(self: *Self) void {

        // this data structure gets created using an allocator.
        // due to that, we have to set the default field values.

        // n0 -> n1 -> n2 -> ... -> n_i -> null

        for (0..MAX_NODES - 1) |i| {
            self.node_buffer[i].next = &self.node_buffer[i + 1];
            self.node_buffer[i].data = sentinelPtr();
        }
        self.node_buffer[MAX_NODES - 1].next = null;
        self.node_buffer[MAX_NODES - 1].data = sentinelPtr();

        // l.first -> n0...
        self.free_nodes.first = &self.node_buffer[0];

        for (self.scalar_lanes[0..]) |*list| {
            list.first = null;
        }

        self.tensor_stack.len = 0;
    }
3

This dependency loop error is new to me. I guess it’s due to trying to take the address of a variable while defining it? In any case, the following works and still statically allocates the array. It just initializes it at runtime.

const std = @import("std");

const Elem = struct {
    next: ?*Elem,
    data: u32,
};

var table: [3]Elem = undefined;

pub fn main() void {
    table = .{
        Elem{ .data = 10, .next = &table[1] },
        Elem{ .data = 20, .next = &table[2] },
        Elem{ .data = 30, .next = null },
    };

    var head: ?*Elem = &table[0];

    while (head) |elem| : (head = elem.next) {
        std.log.debug("{d}", .{elem.data});
    }
}
2 Likes
4

as @dude_the_builder also mentioned, you can statically allocate the data – if you’re willing to perform the pointer initialization at runtime…

in my world of embedded MCUs with EXTREMELY limited memory, the added code space incurred by the runtime initialization really does matter (to me, anyway)…

i just saw something online with a “workaround” using anyopaque pointers, which i’ll play with…

5

Post your findings here if you can get something that works for you - I’m interested to see it!

6

this appears to work, in that i have a “circular list” with pointers being represented as indicies into my array:

const std = @import("std");

const Elem = struct {
    pub const NIL = ~@as(u16, 0);
    data: u32,
    next: u16 = NIL,
    pub fn getNext(self: @This()) ?*Elem {
        if (self.next == NIL) {
            return null;
        } else {
            return &elem_table[self.next];
        }
    }
};

var elem_table = [_]Elem{
    Elem{ .data = 10, .next = 1 },
    Elem{ .data = 20, .next = 2 },
    Elem{ .data = 30, .next = 0 },
};

var head = &elem_table[0];

pub fn main() void {
    var e = head;
    while (true) {
        std.log.debug("{d}", .{e.data});
        if (e.getNext() == null) break;
        e = e.getNext().?;
        if (e == head) break;
    }
}

the trick, of course, is to ensure getNext incurs little/no overhead… given that initial value of elem_table is known at comptime, you’d think there would be some way to perform another comptime transformation that executes getNext with a known set of .next values on an elem_table that’s known…

in my use-case, i will be GENERATING a file that contains these static initializations; and adding some additional (advanced) comptime initialization is not a problem for me…

the goal remains to minimize memory footprint on my MCU target – pushing as much work as possible to an upstream pass (which actually generates the aforementioned file) as well as any “exotic” initialization idioms…

2 Likes
7

This is #131 (it might look different, but the resolution is the same). It’s on my list, although:

Screenshot_20240515-131936_Discord~2
Screenshot_20240515-131936_Discord~21080×578 73 KB

1 Like
8

i did a little experimentation and found the following pattern which seems to work:

const std = @import("std");

const Elem = struct {
    data: u32,
    next: ?*Elem,
};

var elem_tab: [3]Elem = undefined;
const elem_tab_init = [_]Elem{
    Elem{ .data = 10, .next = &elem_tab[1] },
    Elem{ .data = 20, .next = &elem_tab[2] },
    Elem{ .data = 30, .next = &elem_tab[0] },
};

var head = &elem_tab[0];

pub fn main() void {
    //
    std.mem.copyForwards(Elem, elem_tab[0..], elem_tab_init[0..]);
    //
    var e = head;
    while (true) {
        std.log.debug("{d}", .{e.data});
        if (e.next == null) break;
        e = e.next.?;
        if (e == head) break;
    }
}

needless to say, i verified this works on my memory-constrained MCU :wink:

the net effect in the final image is to add space in the .const section (where elem_tab_init is stored) as well as to allocate an equal amount of uninitialized space in .bss… (this is the moral equivalent of what happens with .data initialization…

in my ongoing quest to reduce memory footprint in embedded systems, i will often “overlay” initialization/startup code with the main (“steady-state”) code anyway…

the std.mem.copyForwards would be present in that initial overlay only – along with similar code found in the equivalent of crt0.c…

while the fix on @mlugg’s work-list would certainly be welcome, i think this approach will hold me for now…

1 Like
9

Rather than copyForwards, just use @memcpy here. std.mem.copy{Forwards,Backwards} need only be used when the ranges to copy overlap.

2 Likes
10

FWIW, std.mem.copyForwards actually yielded a smaller memory footprint than @memcpy…

1 Like
11

I’m curious as to why you want to allocate this space in the .const section in addition to the .bss section? Sounds counterintuitive when dealing in an extemely memory constrained environment.

12

it’s really no different than .data, in that you allocate space in SRAM and will have additional constants as part of the program image… these constants are then copied into SRAM at startup – which is what i’m doing explicitly, in lieu of having the compiler startup do it implicitly …

13

i’d like to revisit this approach, with a slightly more generalized solution:

const std = @import("std");

pub const NIL = ~@as(u16, 0);

const Elem = struct {
    data: u32,
    next: u16 = NIL,
};

pub fn getElem(idx: u16) ?*Elem {
    return if (idx == NIL) null else &elem_tab[idx];
}

var elem_tab = [_]Elem{
    Elem{ .data = 10, .next = 1 },
    Elem{ .data = 20, .next = 2 },
    Elem{ .data = 30, .next = 0 },
};

var head = getElem(0);

pub fn main() void {
    var e = head.?;
    while (true) {
        std.log.debug("data = {d}", .{e.data});
        if (getElem(e.next) == null) break;
        e = getElem(e.next).?;
        if (e == head) break;
    }
}

as before, elem_tab effectively contains cycles… but since the next field is represented as an index into elem_tab, i avoid the compiler dependency loop error…

something else quite remarkable about this approach (which i’ve verified in a more memory-constrained target) is the overhead of getElem is virtually equivalent to using pointers directly… this approach is also smaller than any of the approaches using run-time initialization of elem_tab…

equally remarkable, the compiler in the example above will “downgrade” var elem_tab to constant status – since it sees none of its values being mutated… the space shows up in the image’s .const rather than .data section…

the challenge, of course, is that using getElem with some index value is inherently error-prone and dangerous… unlike a typed pointer, the vanilla u16 used for my indicies don’t say anything about the type of the referenced object let alone the name of the array to be used as a base…

seems simple enough to create some generic types to wrap these relationships… but the problem is (as i’ve discovered after painfully trying) is that any value of a generic type that somehow references elem_tab cannot be placed inside elem_tab itself!!!

even moving the getElem function inside some generic Index type leads to a dependency loop… the compiler has so far seen through all of my attempts to mask what i’m really trying to do here :wink:

any thoughts on how i can improve the safety of my index-based solution, without creating an actually dependency loop within elem_tab ???

14

here’s my latest attempt to generalize the pattern – which unfortunately leads to a dependency loop in ElemDom:

const std = @import("std");

pub fn Domain(T: type) type {
    return struct {
        const Self = @This();
        extent: [*]T,
        pub fn Ref(_: Self) type {
            return struct {
                idx: u16 = NIL,
            };
        }
        pub fn get(self: Self, ref: Ref) ?*T {
            return if (ref.idx == NIL) null else &self.extent[ref.idx];
        }
    };
}

pub const NIL = ~@as(u16, 0);

const ElemDom = Domain(Elem){ .extent = &[_]Elem{
    Elem{ .data = 10, .next = .{ .idx = 1 } },
    Elem{ .data = 20, .next = .{ .idx = 2 } },
    Elem{ .data = 30, .next = .{ .idx = 0 } },
} };

const Elem = struct {
    data: u32,
    next: ElemDom.Ref(),
};

const head = ElemDom.get(.{ .idx = 0 });

pub fn main() void {
    var e = head.?;
    while (true) {
        std.log.debug("data = {d}", .{e.data});
        if (ElemDom.get(e.next) == null) break;
        e = ElemDom.get(e.next).?;
        if (e == head) break;
    }
}

what does work is defining a top-level Ref(T), which truly does create a uniquely-named type… i’m just not sure how to synthesize a fn (ref: Ref(T)) ?*T getter at the top-level for each [*]T extent array which holds the instances…

do i pass the latter array as an anytype??? obviously we’re talking about same T in Ref(T) and the [*]T used in the body of the getter…

15

success!!!

here’s something that works – and i think will generalize nicely…

const std = @import("std");

pub fn Ref(T: type) type {
    return struct {
        const tname = @typeName(T);
        idx: u16,
    };
}

pub fn Domain(T: type) type {
    return struct {
        const Self = @This();
        extent: []T,
        pub fn get(self: Self, ref: Ref(T)) ?*T {
            return if (ref.idx == NIL) null else &self.extent[ref.idx];
        }
    };
}

pub const NIL = ~@as(u16, 0);

const ElemDom = Domain(Elem){ .extent = @constCast(&[_]Elem{
    Elem{ .data = 10, .next = .{ .idx = 1 } },
    Elem{ .data = 20, .next = .{ .idx = 2 } },
    Elem{ .data = 30, .next = .{ .idx = 0 } },
}) };

const Elem = struct {
    data: u32,
    next: Ref(Elem),
};

const head = ElemDom.get(.{ .idx = 0 });

pub fn main() void {
    var e = head.?;
    while (true) {
        std.log.debug("data = {d}", .{e.data});
        if (ElemDom.get(e.next) == null) break;
        e = ElemDom.get(e.next).?;
        if (e == head) break;
    }
}

a few quirks:

  1. the (benign) tname constant inside Ref forced usage of T; using _ instead did really produce a unique type

  2. not sure about the type of the extent field; since i don’t know the actually number of elements in the domain, i figured i needed some sort slice/pointer…

  3. i’m bothered by the @constCast…

16

what’s the best way for me to track progress here??? as soon as this functionality makes it into nightly, i’d like to play with it…