9 ms·

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

the_mitsuhiko 1y ago
> 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".
reissbaker 1y ago
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.
- fpoling 1y ago
  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?
  - reissbaker 1y ago
    Yup, you could pass it in at comptime as well! And access via @field.
  - spiffyk 1y ago
    I think the more important question here is: What operations would you possibly want to do with a linked list that are generic and at the same time do something with the concrete data in it? To me these complaints sound like hypotheticals with no sound grounding in the real world. If there indeed is data that is common to the various types you would want to operate upon in such linked lists, you would nest. E.g. you would have some common Entity struct containing the common data and the LinkedList.Node; this Entity would then be inside your more concrete structs. The generic function would then take a pointer to Entity.
    - reissbaker 1y ago
      I think a pretty good example would be: how do you write a map function? Or filter, find, etc. (You would do it with more comptime, but the question is legitimate!)
      - spiffyk 1y ago
        > how do you write a map function? Or filter, find, etc. You just don't. Zig does not have lambdas anyway, there's no readability incentive to having such functions there. You do these things with plain old loops built into the language.
        reissbaker 1y ago
        Zig has first-class functions (you can pass functions as parameters); it just doesn't have closures. Map pretty rarely uses closures anyway IME; e.g. converting a list to JSON doesn't need to close over outside variables. And anyway, anything that's: 1. Generic over lists, and 2. Takes a function as a parameter Will want to know what the node field name is. Luckily, comptime provides a solution there. TBH I think "you just don't" is a pretty unsatisfying answer to "how do I use these features that are built into Zig" — especially when you can use them, very easily.
        spiffyk 1y ago
        I mean yes, you can pass functions as parameters in Zig, you can even define them inline if you wrap them in anonymous structs, but my point is that — in a language where this is supported somewhat properly — you would do this to improve readability with some sort of a fluent API. If you attempt to do it in status-quo Zig, readability will only suffer and you are still much better off doing it with for and/or while loops (depending on the data structure), especially when Zig has nice syntax sugar with payloads in both to support these. edit: formatting
        Zambyte 1y ago
        Zig definitely encourages an imperative style by design, but it does support function pointers, which can be used to implement a map function. I do think passing the field name of the node as a comptime []const u8 as an extra argument to map, filter, etc. would be the only way to implement a generic version of these functions. The fact that these functions are already designed to be cumbersome to implement, I think that's fine? I have also yet to use a linked list in Zig anyways. It's probably better to use an array, slice, std.BoundedArray, std.ArrayList, std.SegmentedList, or std.MultiArrayList unless there is a specific reason that a linked list is the best option.
- roetlich 1y ago
  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 :)
  - messe 1y ago
    What if the User is in multiple linked lists? const User = struct { username: []const u8, id: u128, age: u7, sorted_by_age: std.SinglyLinkedList.Node, sorted_by_id: std.SinglyLinkedList.Node, };
- boomlinde 1y ago
  @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.
  - grayhatter 1y ago
    > The use of @fieldParentPtr here [...] the *hypothetical* use here... This simple example as written is actually correct, and not actually unchecked illegal behavior. But this is just a bit of pedantry, because it would be unchecked illegal if you use this in a more complicated example. I mention it because it's important to note, it can be done correctly, as you obviously just did it correctly, by accident. That said, I still agree, there're no guardrails on this pattern.
    - boomlinde 1y ago
      > the hypothetical use here... No, it's not hypothetical. I just did it, which demonstrates that it's not type safe and that the compiler won't give you an error if you write invalid code, which is what the post I responded to claimed. > This simple example as written is actually correct No. The official reference is clear about this: "If field_ptr does not point to the field_name field of an instance of the result type, and the result type has ill-defined layout, invokes unchecked Illegal Behavior." Because there is no well-defined layout for plain structs in Zig, they satisfy the "ill-defined layout" requirement. Merely invoking the @fieldParentPtr on a pointer that doesn't satisfy the other requirement in that case invokes unchecked illegal behavior according to the language reference. > I mention it because it's important to note, it can be done correctly, Ignoring that you can't seem to get the facts straight, the claim I am responding to is that it's "type safe" and that "if you write invalid code the compiler will give you an error". This is not the case, regardless of whether my example invokes unchecked illegal behavior (which it does) or not. I'm very clearly not saying that it can't be done correctly and I don't think you can argue for that in good faith.
GolDDranks 1y ago
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 1y ago
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 1y ago
  You have to pass the field name too ("node").
  - flohofwoe 1y ago
    Not really. If you only want to manipulate the list, you only need a direct pointer to the nested node but don't need to know the 'outer type'. Only if the function takes a pointer to the outer type it needs to know how to get the pointer to the embedded node struct from the item pointer. ...I guess it makes a lot more sense if you ever wrote code for AmigaOS ;)
kllrnohj 1y ago
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.
- roetlich 1y ago
  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?
  - boomlinde 1y ago
    1. If you mean @fieldParentPtr, the first argument is a compile time-known name of a field, the second argument is a pointer to a field of that name in the parent type, which is inferred from the left hand side of the assignment 2. Then you're screwed. In Zig, using @fieldParentPtr on a field that doesn't have the given parent is unchecked illegal behavior, meaning that there are no checks that can catch it at compile time. This change basically guarantees that there will be a pretty serious foot gun every time you iterate over the items of a standard library list.
    - roetlich 1y ago
      Thank you, that answers all my questions.
    - 1y ago
AndyKelley 1y ago
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&type=code https://github.com/search?q=repo%3Atokio-rs%2Ftokio%20unsafe... [2]: https://github.com/ziglang/zig/issues/2414 https://github.com/ziglang/zig/issues/2414
- roetlich 1y ago
  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. :)
  - AndyKelley 1y ago
    Linked lists are sometimes the right tool for the job. They are available in the standard library for such cases. If you are struggling to understand how you would use this API then it probably means you have not yet been exposed to such a use case, and you are being quite intentionally steered away from using them.
    - roetlich 1y ago
      Fair, thanks.

> 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".

reissbaker 1y ago

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.

fpoling 1y ago
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?
- reissbaker 1y ago
  Yup, you could pass it in at comptime as well! And access via @field.
- spiffyk 1y ago
  I think the more important question here is: What operations would you possibly want to do with a linked list that are generic and at the same time do something with the concrete data in it? To me these complaints sound like hypotheticals with no sound grounding in the real world. If there indeed is data that is common to the various types you would want to operate upon in such linked lists, you would nest. E.g. you would have some common Entity struct containing the common data and the LinkedList.Node; this Entity would then be inside your more concrete structs. The generic function would then take a pointer to Entity.
  - reissbaker 1y ago
    I think a pretty good example would be: how do you write a map function? Or filter, find, etc. (You would do it with more comptime, but the question is legitimate!)
    - spiffyk 1y ago
      > how do you write a map function? Or filter, find, etc. You just don't. Zig does not have lambdas anyway, there's no readability incentive to having such functions there. You do these things with plain old loops built into the language.
      - reissbaker 1y ago
        Zig has first-class functions (you can pass functions as parameters); it just doesn't have closures. Map pretty rarely uses closures anyway IME; e.g. converting a list to JSON doesn't need to close over outside variables. And anyway, anything that's: 1. Generic over lists, and 2. Takes a function as a parameter Will want to know what the node field name is. Luckily, comptime provides a solution there. TBH I think "you just don't" is a pretty unsatisfying answer to "how do I use these features that are built into Zig" — especially when you can use them, very easily.
        spiffyk 1y ago
        I mean yes, you can pass functions as parameters in Zig, you can even define them inline if you wrap them in anonymous structs, but my point is that — in a language where this is supported somewhat properly — you would do this to improve readability with some sort of a fluent API. If you attempt to do it in status-quo Zig, readability will only suffer and you are still much better off doing it with for and/or while loops (depending on the data structure), especially when Zig has nice syntax sugar with payloads in both to support these. edit: formatting
      - Zambyte 1y ago
        Zig definitely encourages an imperative style by design, but it does support function pointers, which can be used to implement a map function. I do think passing the field name of the node as a comptime []const u8 as an extra argument to map, filter, etc. would be the only way to implement a generic version of these functions. The fact that these functions are already designed to be cumbersome to implement, I think that's fine? I have also yet to use a linked list in Zig anyways. It's probably better to use an array, slice, std.BoundedArray, std.ArrayList, std.SegmentedList, or std.MultiArrayList unless there is a specific reason that a linked list is the best option.
roetlich 1y ago
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 :)
- messe 1y ago
  What if the User is in multiple linked lists? const User = struct { username: []const u8, id: u128, age: u7, sorted_by_age: std.SinglyLinkedList.Node, sorted_by_id: std.SinglyLinkedList.Node, };
boomlinde 1y ago
@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.
- grayhatter 1y ago
  > The use of @fieldParentPtr here [...] the *hypothetical* use here... This simple example as written is actually correct, and not actually unchecked illegal behavior. But this is just a bit of pedantry, because it would be unchecked illegal if you use this in a more complicated example. I mention it because it's important to note, it can be done correctly, as you obviously just did it correctly, by accident. That said, I still agree, there're no guardrails on this pattern.
  - boomlinde 1y ago
    > the hypothetical use here... No, it's not hypothetical. I just did it, which demonstrates that it's not type safe and that the compiler won't give you an error if you write invalid code, which is what the post I responded to claimed. > This simple example as written is actually correct No. The official reference is clear about this: "If field_ptr does not point to the field_name field of an instance of the result type, and the result type has ill-defined layout, invokes unchecked Illegal Behavior." Because there is no well-defined layout for plain structs in Zig, they satisfy the "ill-defined layout" requirement. Merely invoking the @fieldParentPtr on a pointer that doesn't satisfy the other requirement in that case invokes unchecked illegal behavior according to the language reference. > I mention it because it's important to note, it can be done correctly, Ignoring that you can't seem to get the facts straight, the claim I am responding to is that it's "type safe" and that "if you write invalid code the compiler will give you an error". This is not the case, regardless of whether my example invokes unchecked illegal behavior (which it does) or not. I'm very clearly not saying that it can't be done correctly and I don't think you can argue for that in good faith.

GolDDranks 1y ago

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 1y ago

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 1y ago
You have to pass the field name too ("node").
- flohofwoe 1y ago
  Not really. If you only want to manipulate the list, you only need a direct pointer to the nested node but don't need to know the 'outer type'. Only if the function takes a pointer to the outer type it needs to know how to get the pointer to the embedded node struct from the item pointer. ...I guess it makes a lot more sense if you ever wrote code for AmigaOS ;)

kllrnohj 1y ago

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.

roetlich 1y ago
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?
- boomlinde 1y ago
  1. If you mean @fieldParentPtr, the first argument is a compile time-known name of a field, the second argument is a pointer to a field of that name in the parent type, which is inferred from the left hand side of the assignment 2. Then you're screwed. In Zig, using @fieldParentPtr on a field that doesn't have the given parent is unchecked illegal behavior, meaning that there are no checks that can catch it at compile time. This change basically guarantees that there will be a pretty serious foot gun every time you iterate over the items of a standard library list.
  - roetlich 1y ago
    Thank you, that answers all my questions.
  - 1y ago

AndyKelley 1y ago

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&type=code https://github.com/search?q=repo%3Atokio-rs%2Ftokio%20unsafe... [2]: https://github.com/ziglang/zig/issues/2414 https://github.com/ziglang/zig/issues/2414

roetlich 1y ago
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. :)
- AndyKelley 1y ago
  Linked lists are sometimes the right tool for the job. They are available in the standard library for such cases. If you are struggling to understand how you would use this API then it probably means you have not yet been exposed to such a use case, and you are being quite intentionally steered away from using them.
  - roetlich 1y ago
    Fair, thanks.