Zig Version
0.16.0-dev.2296+fd3657bf8
Steps to Reproduce and Observed Behavior
This is the minimal working example I've managed to trim down to. It does rely on my own implementation of a slot map, but I don't think the implementation is the issue.
conststd=@import("std");constSlotMap=@import("SlotMap.zig").SlotMap;constFooMap=SlotMap(Foo);constFoo=struct{bar:usize,baz:?FooMap.Key,};pubfnmain(init:std.process.Init)!void{constarena=init.arena.allocator();varmap:FooMap=try.initCapacity(arena,1);constfoo_in:Foo=.{.bar=69,.baz=null};constkey_in=trymap.insertBounded(foo_in);constfoo_out_ptr_maybe=map.get(key_in);constfoo_out_ptr=foo_out_ptr_maybe.?;std.debug.assert(foo_out_ptr.baz==null);// Assertion succeedsif(foo_out_ptr.baz==null){std.debug.print("1) baz is null.\n",.{});// This prints}if(foo_out_ptr.baz==null){std.debug.print("2) baz is null.\n",.{});// This does not print}std.debug.assert(foo_out_ptr.baz==null);// Assertion fails}//! Slot map implementation (Trimmed down)conststd=@import("std");pubfnSlotMap(comptimeT:type)type{returnstruct{constSelf=@This();/// The underlying data structure for the contiguous block of memory.slots:std.ArrayList(Slot),/// Index of `slots` that will be used on the next call of `insert`./// This will be null when the SlotMap is full.free_head:?usize,/// The number of active slotssize:usize,pubconstKey=struct{index:usize,generation:usize,};constSlot=struct{/// Even = vacant, Odd = occupied. Does not necessarily start at 0.generation:usize,content:union(enum){data:T,next_free:?usize,},};/// Initialises the underlying memory to have capacity equal to exactly num elements.pubfninitCapacity(allocator:std.mem.Allocator,num:usize)!Self{return.{.slots=trystd.ArrayList(Slot).initCapacity(allocator,num),.free_head=0,.size=0,};}/// Deinit the underlying memory.pubfndeinit(slot_map:*Self,allocator:std.mem.Allocator)void{slot_map.slots.deinit(allocator);}/// Attempt to insert a value and return the key for later retrieval.pubfninsertBounded(slot_map:*Self,value:T)!Key{constfree_head=slot_map.free_headorelsereturnerror.OutOfMemory;constslots=&slot_map.slots;varslot:*Slot=undefined;if(free_head>=slots.items.len){slot=tryslots.addOneBounded();// If this activates a previously invalidated slot,// ensure the generation is even to reflect it is free.slot.generation+%=slot.generation%2;// set free_headslot_map.free_head=if(free_head==slots.capacity)nullelsefree_head+1;}else{slot=&slots.items[free_head];// Assert this free slot is free, and that it points to a free slot{std.debug.assert(slot.generation%2==0);std.debug.assert(slot.content==.next_free);std.debug.assert(slots.items[slot.content.next_free.?].generation%2==0);}slot_map.free_head=slot.content.next_free;}slot.content=.{.data=value};slot.generation+%=1;slot_map.size+=1;return.{.index=free_head,.generation=slot.generation,};}/// Returns a reference to the value corresponding to the key if it is valid.pubfnget(slot_map:Self,key:Key)?*T{// Check if the slot is currently invalidatedif(key.index>=slot_map.slots.items.len)returnnull;varslot=slot_map.slots.items[key.index];// Check generationif(slot.generation!=key.generation)returnnull;return&slot.content.data;}};}Output:
zig build run
1) baz is null.
thread 3578515 panic: reached unreachable code
/Users/xiexingwu/.zvm/master/lib/std/debug.zig:419:14: 0x1000756d3 in assert (zig_null)
if (!ok) unreachable; // assertion failure
^
/Users/xiexingwu/src/misc/zig-null/src/main.zig:28:21: 0x10016bb57 in main (zig_null)
std.debug.assert(foo_out_ptr.baz == null); // Assertion fails
...
Expected Behavior
I expect both assertions to succeed, and for the program to print
1) baz is null.
2) baz is null.
### Zig Version
0.16.0-dev.2296+fd3657bf8
### Steps to Reproduce and Observed Behavior
This is the minimal working example I've managed to trim down to. It does rely on my own implementation of a slot map, but I don't think the implementation is the issue.
```zig
const std = @import("std");
const SlotMap = @import("SlotMap.zig").SlotMap;
const FooMap = SlotMap(Foo);
const Foo = struct {
bar: usize,
baz: ?FooMap.Key,
};
pub fn main(init: std.process.Init) !void {
const arena = init.arena.allocator();
var map: FooMap = try .initCapacity(arena, 1);
const foo_in: Foo = .{ .bar = 69, .baz = null };
const key_in = try map.insertBounded(foo_in);
const foo_out_ptr_maybe = map.get(key_in);
const foo_out_ptr = foo_out_ptr_maybe.?;
std.debug.assert(foo_out_ptr.baz == null); // Assertion succeeds
if (foo_out_ptr.baz == null) {
std.debug.print("1) baz is null.\n", .{}); // This prints
}
if (foo_out_ptr.baz == null) {
std.debug.print("2) baz is null.\n", .{}); // This does not print
}
std.debug.assert(foo_out_ptr.baz == null); // Assertion fails
}
```
```zig
//! Slot map implementation (Trimmed down)
const std = @import("std");
pub fn SlotMap(comptime T: type) type {
return struct {
const Self = @This();
/// The underlying data structure for the contiguous block of memory.
slots: std.ArrayList(Slot),
/// Index of `slots` that will be used on the next call of `insert`.
/// This will be null when the SlotMap is full.
free_head: ?usize,
/// The number of active slots
size: usize,
pub const Key = struct {
index: usize,
generation: usize,
};
const Slot = struct {
/// Even = vacant, Odd = occupied. Does not necessarily start at 0.
generation: usize,
content: union(enum) {
data: T,
next_free: ?usize,
},
};
/// Initialises the underlying memory to have capacity equal to exactly num elements.
pub fn initCapacity(allocator: std.mem.Allocator, num: usize) !Self {
return .{
.slots = try std.ArrayList(Slot).initCapacity(allocator, num),
.free_head = 0,
.size = 0,
};
}
/// Deinit the underlying memory.
pub fn deinit(slot_map: *Self, allocator: std.mem.Allocator) void {
slot_map.slots.deinit(allocator);
}
/// Attempt to insert a value and return the key for later retrieval.
pub fn insertBounded(slot_map: *Self, value: T) !Key {
const free_head = slot_map.free_head orelse return error.OutOfMemory;
const slots = &slot_map.slots;
var slot: *Slot = undefined;
if (free_head >= slots.items.len) {
slot = try slots.addOneBounded();
// If this activates a previously invalidated slot,
// ensure the generation is even to reflect it is free.
slot.generation +%= slot.generation % 2;
// set free_head
slot_map.free_head = if (free_head == slots.capacity) null else free_head + 1;
} else {
slot = &slots.items[free_head];
// Assert this free slot is free, and that it points to a free slot
{
std.debug.assert(slot.generation % 2 == 0);
std.debug.assert(slot.content == .next_free);
std.debug.assert(slots.items[slot.content.next_free.?].generation % 2 == 0);
}
slot_map.free_head = slot.content.next_free;
}
slot.content = .{ .data = value };
slot.generation +%= 1;
slot_map.size += 1;
return .{
.index = free_head,
.generation = slot.generation,
};
}
/// Returns a reference to the value corresponding to the key if it is valid.
pub fn get(slot_map: Self, key: Key) ?*T {
// Check if the slot is currently invalidated
if (key.index >= slot_map.slots.items.len) return null;
var slot = slot_map.slots.items[key.index];
// Check generation
if (slot.generation != key.generation) return null;
return &slot.content.data;
}
};
}
```
Output:
```
zig build run
1) baz is null.
thread 3578515 panic: reached unreachable code
/Users/xiexingwu/.zvm/master/lib/std/debug.zig:419:14: 0x1000756d3 in assert (zig_null)
if (!ok) unreachable; // assertion failure
^
/Users/xiexingwu/src/misc/zig-null/src/main.zig:28:21: 0x10016bb57 in main (zig_null)
std.debug.assert(foo_out_ptr.baz == null); // Assertion fails
...
```
### Expected Behavior
I expect both assertions to succeed, and for the program to print
```
1) baz is null.
2) baz is null.
```