[roetlich]

This looks somewhat horrifying. How do I safely write a function that takes a linked list as a parameter?

[the_mitsuhiko]

> How do I safely write a function that takes a linked list as a parameter?

Zig does not have a lot of generic code. You would pass the user directly and then walk the list or you use comptime. The real answer is that "you don't write code like that in Zig".

[AndyKelley]

Two points here:

Linked lists are useful in unsafe code. Most recent use case I had for them was in an event loop with coroutines. It's not possible to implement such thing in memory safe languages. For example if you use Rust, you have to use unsafe [1].

@fieldParentPtr does not yet have safety but it is a planned upcoming change to the language, with a fairly straightforward implementation [2].

[1]: https://github.com/search?q=repo%3Atokio-rs%2Ftokio%20unsafe...

[2]: https://github.com/ziglang/zig/issues/2414

[roetlich]

Oh, that makes more sense. Thank you!

Is this linked list type then mostly meant to be used as an internal implementation detail, and not be exposed in a public API? Because if I see a function that takes a non-generic list I won't really know how to call it. :)

[reissbaker]

Assuming you mean "how would I safely write a function that takes a generic linked list and does something with the data," I'm pretty sure you would use comptime: your function would take the concrete type (say, User) as a comptime parameter, and then you would do your list stuff via accessing .node and use the fieldParentPtr to access the underlying data.

Syntactically I don't think it's that weird, TBH. And it's typesafe: if you write invalid code the compiler will give you an error.

[boomlinde]

@fieldParentPtr is not type safe. It assumes that the given pointer is to a field of the given name in the inferred type. Zig can detect at compile time whether the inferred type has a field of that name of the same type as the pointer child. So far, so good: type safe.

The lack of safety stems from the fact it doesn't know that the assumption that the pointer has that parent is true. Here's a very simple illustration. It'll compile.

    const T = struct {
        field: i32 = 0,
    };
    
    pub fn main() void {
        var nonfield: i32 = 0;
    
        _ = @as(*T, @fieldParentPtr("field", &nonfield));
    }

`nonfield` doesn't have a parent T. The use of @fieldParentPtr here causes what the official reference calls "unchecked illegal behavior"; it isn't checked even in the safe build modes.

[roetlich]

Okay, thanks for explaining more.

> And it's typesafe: if you write invalid code the compiler will give you an error.

One more question, if @fieldParentPtr("node", n) is typesafe and can get you a User, the compiler needs to know that the struct has the fields of a User, and that this pointer is indeed pointing at a node field, right? Then why do you need to specify "node" at all?

I think I don't understand Zig at all :)

[fpoling]

But how does the generic code know the name by which the field is known in the struct that contains the field? Is it supposed to be passed as an extra parameter to the generic function?

[GolDDranks]

If you write a function that takes a _generic_ linked list as a parameter, you'd have a function that refers to just the linked list subrecord, and does only linked list operations to that and the linked nodes.

If you want to write a function that takes a linked list of a specific type as a parameter, you just take in a value of that type. The linked list is baked in, so you can get to the other nodes, and because the type is known, you can get back to the parent type from the linked nodes with fieldParentPtr. How to do that _safely_? I don't think that Zig embraces any Rust-like safe/unsafe dichotomy, so you don't.

[flohofwoe]

Since you don't need to care about the 'outer type' in that case you just pass a pointer to the linked list header or a linked list node and that's it.

If you need to access the outer type, just pass a pointer to that type (since your functions need to know the outer type anyway I don't think there's a need to reach for generics).

[skywal_l]

You have to pass the field name too ("node").

[kllrnohj]

You don't & generally shouldn't be in the first place, in any language. Linked lists are a very niche data structure, so generic code should ~never be using them. So it's a moot question. It's kinda like the complaints about how hard a doubly linked list is in Rust - it's just not important because it's not something you should be using 99.999% of the time anyway.

[grayhatter]

A linked list is just a simpler version of both a graph and a tree. What data structure would you suggest to represent both/either of those?

Or are you asserting, because you've never used them they're not common? Because while maybe I agree, and I don't often reach for a linked list, I've built plenty of trees and graphs.

[roetlich]

Well I personally almost never use linked lists, don't like them. But Zig seems to think otherwise, they have two implementations in the standard library.

I don't know much Zig, I just wanted to ask how to use the type that the article talks about?

Let's use the very simple example from the article. Let's say I want to extract this code into a function:

    while (node) |n| {
      const user: *User = @fieldParentPtr("node", n);
      std.debug.print("{any}\n", .{user});
      node = n.next;
    }

1. How does that look, what's the type signature of this function? 2. What happens if I put in a list doesn't contain users? Do I get a simple to understand compile time error, or can I segfault because I'm accessing bad memory?

And I don't think that would need any generics, since the list type isn't generic, right?