This looks somewhat horrifying. How do I safely write a function that takes a linked list as a parameter?
> 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".
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...
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. :)
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.
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.
@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));
}
> 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.
> 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.
> 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.
Describe explicitly how your example will trigger illegal behavior? Happy to discuss the behavior of the compiled asm if you'd like to be that pendantic?
Not type safe, and contains an appreciable risk or defect are two distinct concerns. One matters less than the other.
> Because there is no well-defined layout for plain structs in Zig, they satisfy the "ill-defined layout" requirement.
No? Struts have a defined layout, they're not guaranteed between compilations, but they don't change within a compilation unit.
> 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.
And the failure mode is the compiler will decide to delete your OS?
Unchecked illegal behavior isn't magic, doing something similar to illegal behavior doesn't mean the code will or won't do what you intended. uint rollover is unchecked illegal behavior (when not explict, in release fast) but just because the uint might roll over doesn't make that code invalid.
> 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.
I thought you were saying that it's guaranteed to be incorrect. In fact, I think that's what you said in your reply to me. Mostly because you used the word 'mearly'.
The way that I understood what you meant was, the example you provided was guaranteed wrong. In fact it's actually correct. It will have the same semantics and behavior as what I assume was desired.
> Ignoring that you can't seem to get the facts straight [...] and I don't think you can argue for that in good faith.
I'm sorry if I was unclear, I was trying to discuss it in good faith. :(
> Describe explicitly how your example will trigger illegal behavior? Happy to discuss the behavior of the compiled asm if you'd like to be that pendantic?
Through calling @fieldParentPtr with a field_ptr not pointing at a field of the given field name in the result type, when the result type has an ill-defined memory layout. I'm essentially just paraphrasing the documentation, which I've already quoted.
Generated code is irrelevant to this end. Illegal behavior can coincidentally result in code that works as intended in practice as a side effect of the implementation. Similarly you may expect a signed integer to wrap around as it overflows in C because of the implementation of the compiler and the code it generates, but it's still undefined behavior.
> No? Struts have a defined layout, they're not guaranteed between compilations, but they don't change within a compilation unit.
This is not the sense in which the Zig language reference uses the term well-defined memory layout. Bare structs, error unions, slices and optionals don't have a well-defined memory layout in the sense the Zig language reference uses it.
> And the failure mode is the compiler will decide to delete your OS?
The failure mode is irrelevant. Unchecked illegal behavior is unchecked illegal behavior regardless of the failure mode. You are moving goalposts now.
> I thought you were saying that it's guaranteed to be incorrect. In fact, I think that's what you said in your reply to me. Mostly because you used the word 'mearly'.
The example I posted is guaranteed to be incorrect, which demonstrates that the use of @fieldParentPtr can result in unchecked illegal behavior, hence not type safe nor giving you an error when you write invalid code. Regarding the use of "merely", you should adopt the habit of reading complete sentences before you draw conclusions about what they imply.
> The way that I understood what you meant was, the example you provided was guaranteed wrong.
The example is guaranteed to cause unchecked illegal behavior.
> I'm sorry if I was unclear, I was trying to discuss it in good faith. :(
If you want to argue in good faith, you can start with a good faith reading of the language reference.
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 :)
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,
};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?
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.
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!)
These type of features (map, filter, closures, lambdas...) are in languages like Vlang, Dlang, Rust, etc... They aimed to provide more functional programming style features and always were about general-purpose programming.
Zig presented itself as primarily a more explicit low level language, that so happens it can be used for other things too. Presently, Zig looks to be more in a confused state, where it is not sure what features to add or what other purposes it wants to serve. Probably why they still are years away from hitting v1.0, even after 9 years.
> 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.
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.
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
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.
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.
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).
You have to pass the field name too ("node").
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 ;)
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.
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.
Trees and graphs serve useful roles, of course, but calling a linked list just a simpler version is a stretch. It'd be like calling an array a simplified B-tree. The simplification changes not just the implementation but also radically changes the applicability of the result.
except a tree or graph with multiple pointers is similar to linked list with one pointer.
where as a b-tree stored in an array without pointers probably shouldn't be called a b-tree.
or am I missing something?
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;
}
And I don't think that would need any generics, since the list type isn't generic, right?
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.
Is 2 really an issue? Just how often are you going to have multiple Node types going on in your codebase?