# Dependency loop in statically-linked array elements

**URL:** <https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323>\
**Category:** Help\
**Tags:** language\
**Created:** [May 15, 2024, 12:10am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323 "2024-05-15T00:10:47Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 15, 2024, 12:10am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/1 "2024-05-15T00:10:47Z")

</div>

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

```zig
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???

---

<div class="post-metadata">

**Author:** ![AndrewCodeDev](https://ziggit.dev/letter_avatar_proxy/v4/letter/a/278dde/32.png) [@AndrewCodeDev](https://ziggit.dev/u/AndrewCodeDev)\
**Post date:** [May 15, 2024, 12:23am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/2 "2024-05-15T00:23:11Z")

</div>

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:

```zig
// 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;
    }

```

---

<div class="post-metadata">

**Author:** ![dude\_the\_builder](https://ziggit.dev/user_avatar/ziggit.dev/dude_the_builder/32/557_2.png) [@dude\_the\_builder](https://ziggit.dev/u/dude_the_builder)\
**Post date:** [May 15, 2024, 12:45am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/3 "2024-05-15T00:45:19Z")

</div>

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.

```zig
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});
    }
}

```

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 15, 2024, 12:53am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/4 "2024-05-15T00:53:33Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![AndrewCodeDev](https://ziggit.dev/letter_avatar_proxy/v4/letter/a/278dde/32.png) [@AndrewCodeDev](https://ziggit.dev/u/AndrewCodeDev)\
**Post date:** [May 15, 2024, 12:54am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/5 "2024-05-15T00:54:31Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 15, 2024, 1:41am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/6 "2024-05-15T01:41:44Z")

</div>

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

```zig
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…

---

<div class="post-metadata">

**Author:** ![mlugg](https://ziggit.dev/user_avatar/ziggit.dev/mlugg/32/437_2.png) [@mlugg](https://ziggit.dev/u/mlugg)\
**Post date:** [May 15, 2024, 11:21am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/7 "2024-05-15T11:21:39Z")

</div>

This is [#131](https://github.com/ziglang/zig/issues/131) (it might look different, but the resolution is the same). It’s on my list, although:

 ![Screenshot_20240515-131936_Discord~2](https://ziggit.dev/uploads/default/original/2X/b/bae72698a04e695a1a13b4a11c257928db6d7056.png)

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 15, 2024, 12:19pm UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/8 "2024-05-15T12:19:59Z")

</div>

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

```zig
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 😉

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…

---

<div class="post-metadata">

**Author:** ![mlugg](https://ziggit.dev/user_avatar/ziggit.dev/mlugg/32/437_2.png) [@mlugg](https://ziggit.dev/u/mlugg)\
**Post date:** [May 15, 2024, 12:28pm UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/9 "2024-05-15T12:28:42Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 15, 2024, 12:46pm UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/10 "2024-05-15T12:46:26Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![dude\_the\_builder](https://ziggit.dev/user_avatar/ziggit.dev/dude_the_builder/32/557_2.png) [@dude\_the\_builder](https://ziggit.dev/u/dude_the_builder)\
**Post date:** [May 15, 2024, 1:38pm UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/11 "2024-05-15T13:38:06Z")

</div>

> [@biosbob](#):
>
> 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`

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.

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 15, 2024, 2:13pm UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/12 "2024-05-15T14:13:53Z")

</div>

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 …

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 17, 2024, 12:03am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/13 "2024-05-17T00:03:15Z")

</div>

i’d like to revisit [this](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/6) approach, with a slightly more generalized solution:

```zig
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 😉

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

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 17, 2024, 2:21am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/14 "2024-05-17T02:21:41Z")

</div>

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

```zig
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…

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 17, 2024, 2:37am UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/15 "2024-05-17T02:37:28Z")

</div>

success!!!

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

```zig
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`…

---

<div class="post-metadata">

**Author:** ![biosbob](https://ziggit.dev/user_avatar/ziggit.dev/biosbob/32/1987_2.png) [@biosbob](https://ziggit.dev/u/biosbob)\
**Post date:** [May 21, 2024, 3:26pm UTC](https://ziggit.dev/t/dependency-loop-in-statically-linked-array-elements/4323/16 "2024-05-21T15:26:18Z")

</div>

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…