My tests have been failing. I deduced it to one line by some miracle. It’s due to a slice element being set to undefined (0xaa). In #1, direct assignment sets an undefined value to items[idx] in some cases. In #2, assigning to a variable beforehand fixes it.
Just based on the syntax alone, should there be any meaningful differences here? If none, then I’ll investigate further-especially on master.
To be clear, the tests fail not because of incorrect logic in my algorithm but due to the undefined value in items[idx].
// #1.a Sets an undefined value
self.list.items[idx] = try self.parse(bp);
// #1.b Sets an undefined value
self.list.items[idx] = self.parse(bp) catch unreachable;
// #2 Completely fine.
const foo = try self.parse(bp);
self.list.items[idx] = foo;
#1.b doesn’t fail with unreachable. It fails the test due to setting an undefined value that is to be used later on, just like with #1.a. This is to see if the miscompilation is related to error unions which it isn’t. I’ll update the post to be clearer.
My guess is that self.parse is resizing self.list which means that
self.list.items[idx] = try self.parse(bp);
is setting [idx] of the old items slice. See here for another example of this same sort of bug, and here for Andrew saying this is working as intended.
This one makes sense (I also got bit by this mistake), to expand on what’s going on here: ArrayLists have a capacity, which is how much memory they are allowed to write to, and a slice (.items) which is how much they actually have. So when you try to write to the slice directly by indexing, the memory is legal, it’s been allocated, but the slice doesn’t know that: the bounds check fails.
You want to be careful about writing directly to a slice that’s part of an allocating data structure, or taking pointers to it. Resizing can move your data, so whenever you can do things through the structure’s interface, you should.
It’s not totally clear that this exact thing is the problem you’re experiencing, but it’s a likely guess. Zig has result location semantics, and that implies that the address of an lvalue is determined before the rvalue expression executes (so that the function knows where to put the result), so if you get unlucky and the parse allocation moves the slice, then the value you expect won’t be there, and if you get really unlucky and the allocator moved the slice and returned the memory to the system, it could segfault as well.
Seems to be the exact issue. Although, you were just appending to the end of the slice and so Andrew’s recommendation doesn’t apply to what im trying to do.
I’m assigning something to the start/middle of the slice. If I were to adhere to the interface, I’d use insert() instead which is O(N). I’m directly assigning to avoid this. Here is the logic:
// This is just an overview of the algorithm logic.
// It does not reproduce the undefined assignment.
pub fn main() !void {
var list = std.ArrayList(u8).init(std.heap.page_allocator);
const idx = try reserve(&list);
list.items[idx] = try parse(&list);
std.debug.print("{any}", .{list.items});
// Output: {1, 2}
// In my original program, it would be: {2863311530, 2}
}
fn reserve(list: *std.ArrayList(u8)) !usize {
try list.resize(list.items.len + 1);
return list.items.len - 1;
}
fn parse(list: *std.ArrayList(u8)) !u8 {
try list.append(2);
return 1;
}
I was referring to your semi-minimal example which is essentially just appending. That’s why Andrew recommended:
The intended usage is unusedCapacitySlice() or addOne().
I was mistaken and thought that the example was the same logic behind your PR. But yes, the final/accepted fix is the same as the fix that passed my tests which is to assign to a variable first.
I’ve reread the RLS section of the langref. Would this be an accurate layman’s description of the fix?
Assigning const index = ... ; before list.items[index] = ... ; asserts to the compiler that it should evaluate index before accessing the possibly resized slice.
Someone else will likely have a better answer, but the way I think about it is:
// With `list.items[index] = ... ;`, the compiler
// is generating code that would be the
// equivalent of something like this:
var result_ptr = &list.items[index];
const value = ... ;
result_ptr.* = value;
// By separating it into two lines, it forces the compiler
// to do something like this instead:
const value = ... ;
var result_ptr = &list.items[index];
result_ptr.* = value;
Seems unintuitive for Zig to evaluate the result location first though? I expect that swapping the prioritization to not matter. Maybe for discarding values with _ = expr so expr evaluation can be forgone.
It is, and it’s an important wrinkle of the language to get out there, because it’s pretty unusual. RLS is great for efficiency, we know it can cause some aliasing problems, but many languages evaluate the right side, then the left side, then perform assignment.
Zig is different in one way: the left side location is determined first, then the right side is evaluated, and assignment happens. This works mostly as expected because Zig, like most systems languages, doesn’t allow a function as an lvalue, so the “evaluation” on the LHS is fairly limited.
It’s kind of interesting that because of RLS, Zig could allow functions as lvalues, if they return addresses:
That doesn’t compile, but it could, uncheckedAt returns, in this case, a * usize.
We probably don’t want this to work, for several reasons, but my point is that this would have to evaluate the left side first, because RLS makes that a requirement.
Yes, and that’s reasonable, but I hope this illustrates why doing so takes a fuller understanding of how Zig and its data structures work. When you borrow a slice from a data structure, you really should do nothing with that data structure until it gets the slice back, and although it’s unintuitive, the line you wrote first borrows and then uses.
When compiling the simple assignment expression x = e, many languages would create the temporary value e on the stack, and then assign it to x, potentially performing a type coercion in the process. Zig approaches this differently. The expression e is given a result type matching the type of x, and a result location of &x
It would be great to add the explanations here in our topic to the langref. It’s beginner-friendly.
That’s a crazy fun fact lol.
It does. The fix felt like a hack but I realize that it’s just me being used to how most programming languages do it. Thank you!
For the record, this issue is completely unrelated to RLS: it’s literally just that Zig uses left-to-right evaluation (which, like, is kind of the least insane way to specify this). Equivalent code in C for example would have unspecified behavior, because C does not define whether &a or b is evaluated first in a = b (in the C spec lingo, the expressions a and b have unsequenced evaluation).
We definitely don’t want unsequenced evaluation of assignments, it’s one of a great many boneheaded decisions which C is stuck with. And if you say that left-to-right, including lvalue before rvalue, predates RLS in Zig, I believe you.
But I will claim that RLS means Zig has little choice in the matter. If “first right then left” had been picked, it would have had to switch. Because you can’t have RLS without a result location, and to get that, you need to evaluate the assigning side to get that location, before passing it to the rvalue expression.
I question “least insane”, in Lua you can do this:
x, y = y, x
But don’t try it in Zig:
test "bad swap" {
var i: usize = 12;
var j: usize = 45;
i, j = .{ j, i };
std.debug.print("i: {d}, j: {d}\n", .{ i, j });
}
But it allows for efficiency gains, and it’s a clear rule, not hard to understand, and the right choice for Zig.
I don’t think the two can be completely unrelated when one is necessary to have the other.
it’s one of a great many boneheaded decisions which C is stuck with
This perspective is lacking some important nuance. C’s sequencing rules may be a useful piece of unspecified behavior for less intelligent optimizing compilers. Given the time in which C was proliferating, it was reasonable – and even necessary – to make small sacrifices at the language level with the goal of improving code generation.
But I will claim that RLS means Zig has little choice in the matter.
Sure; but we’d make the same decision either way. The reverse is much less intuitive (essentially everything evals LTR; why suddenly do the reverse here?), unless you flip the syntax to be 123 -> x or something.
It’d be pretty wild if the LHS of this assignment referred to other_ptr, which is not only “more to the right”, but is actually on the next line in canonical format. There are probably better examples, this was just the first thing that came to mind.
I question “least insane”, in Lua you can do this:
This difference is triggered by RLS. RLS is not relevant to this discussion. I am talking solely about the evaluation order. If you do something to drop the result location, such as writing i, j = @as([2]usize, .{ i, j }), the snippet works as you’d expect.
Throwaway sentences tangential to the main point frequently do!
C is stuck with a lot of things which no one would add to a new language. The PDP-11 had special opcodes for dealing with zero-terminated sequences, and now we’re stuck with it forever.
But the under-specification of execution order wasn’t a design choice, it was a consequence: C spread well before any attempt to standardize it. Programmers in the Modula and Ada camps were sharply critical of this specific thing way back then.
So sure, calling it a decision is not even accurate, it’s just a thing which happened. Technical debt, really. But it wasn’t a deliberate decision to give freedom to optimize, it was the opposite: folks were just out there writing C compilers based on some heavily-photocopied research papers, and maybe some existing source code, and picked different directions to go in, so the standardization effort had to make sense of that in some way which didn’t break a bunch of compilers.
This was an important ingredient in C’s success however, no question about that. An acquaintance of mine, Evan Buswell, has an excellent paper on this subject which I’m always looking for a chance to recommend.
I don’t see how you can square a difference of evaluation caused by RLS with the claim that RLS isn’t relevant here.
I think we’re mostly talking past each other, despite my best attempts to prevent that. You’re saying that left-before-right doesn’t imply RLS, and I’m saying that RLS implies left-before-right! These are logically compatible.
Here:
This explicitly refers to implication. I also said this:
Which is accurate: and doesn’t say anything about RLS. There’s a reference to it in the preceding paragraph:
And perhaps you’re connecting those things in a way which wasn’t intended.
It’s also not a great description of the alternative model, which is basically that variables (but not the contents of objects) are not updated until an expression is completely evaluated, so they take their original value when appearing on the LHS, after the RHS is evaluated. Here’s how Lua explains it (since that was my example):
If a variable is both assigned and read inside a multiple assignment, Lua ensures that all reads get the value of the variable before the assignment.
Which is also valuable because it’s simple, Python’s explanation of the execution semantics is not, and Go’s is positively gnarly (and closer to Zig, or C for that matter).
So this:
Would use the cached value of ptr to assign to, in some completely different language which even has things like identity semantics for objects, and block statements. A lot of people are coming to Zig from languages which do have an evaluation semantics which works that way, and it can have surprising consequences.
In context, I was explaining one of those surprising consequences: that it’s possible to resolve the LHS of an expression to a slice which is then invalidated by doing things with the data structure holding the slice. This is a thing which never happens in languages with object identity semantics, and it involves understanding a bunch of things about Zig, not just the one point you decided to focus on.
I don’t disagree at all that Zig made the right choice here, even the obvious one. But when you just illustrated that you need to grasp RLS semantics to understand why one version of a swap works and the other doesn’t, I don’t see how that fits with the claim that it’s irrelevant to understanding Zig’s execution semantics. It’s essential.
I’d like to give my 2 cents on your conversation with @mnemnion and add clarity in the spirit of pedantics.
I agree that knowing Zig’s universal left-to-right evaluation suffices in debugging this specific issue as it’s a basic result location scenario. If I were given this information alone, I could figure the rest out on my own without consulting the langref.
I wouldn’t say that RLS is irrelevant though as it is the implementation details of how Zig makes LTR work. Rather, the mention of RLS here is unnecessary. Understanding T{ .a = x } however, requires its mention.
I’d say that universal LTR is consistent, not intuitive. For human readability, the reverse (RTL) here is intuitive as that’s how we read mathematical equations. For programming, it’s undecided. Most people’s intuition from math carryover as most languages adopted that. It’s definitely the nice default for low-level languages. I expect the arguments for LTR to hold nicer with regards to consistency rather than intuitiveness such as compiler complexity and whatnot.
Considering all this, an explicit note in the langref of universal LTR seems beneficial. It sets up the motivation for RLS in the same vibe of how Rust differentiates its String types.
Even if i agreed that RLS is unnecessary in this discussion, The initial help I got is still helpful as I didn’t understand RLS anyway. Thanks again to those people.
EDIT: Technically, we do parse mathematical equations left to right. x = 1 + 2. We take a mental note of the variable and then parse rhs. This happens quickly enough that we perceive it as evaluation of the right side first. Also, we’re not robots that have to consciously think about pointers to our mental notes and so that analogy is hard to internalize on your own.
Math equations aren’t mutable assignments, I think dragging math into this conversation doesn’t make sense, because it operates on different rules than most programming languages, the cases where an equal sign is treated like a real math equation within programming is quite rare.
In math there may be convention to use a certain direction, but it isn’t relevant whether you write a = 3 or 3 = a, so I think lets not complicate things by adding another field of study to the discussion.