Add std.BoundedArray(u5, 32) to hashmap

ericlang · February 15, 2025, 5:57pm

I construct a lot of “strings” with a std.BoundedArray(u5, 32)
and want to store the unique ones in a hashmap.
AutoHashMap does not work property in this case.
Anyone knows how to do this?

n0s4 · February 15, 2025, 6:08pm

You need to use std.HashMap, and explicitly provide hashing and equality functions through the Context type parameter. The docs for HashMap explains this in more detail.

How you choose to hash your strings depends on your use case, but there are many existing methods in std.hash.

ericlang · February 15, 2025, 6:30pm

Ok. I get an enormous list of compiler errors when using HashMap.
I’ll have to think of something easier first…

n0s4 · February 15, 2025, 7:09pm

I think I misunderstood your question. When you said “AutoHashMap” does not work properly in this case" I thought you meant that it couldn’t generate an autoHash function for your BoundedArray type, but it can, so that’s not the issue.

Would you mind explaining why std.AutoHashMap(std.BoundedArray(u5, 32), void) doesn’t work for you?

ericlang · February 15, 2025, 8:10pm

Adding 16 items of which 8 are unique gives 13 hash keys.
I will have to make a separate program to see what is going on

vulpesx · February 15, 2025, 10:26pm

define unique, do you mean half of them are duplicates?
if so getting 13 hashes is concerning

ericlang · February 15, 2025, 11:48pm

True
I will get back here with proof or maybe proof that I am an idiot.

squeek502 · February 16, 2025, 12:24am

AutoContext will give you hash and eql functions that act on all elements of the array, regardless of the current len. Instead, you want hash and eql functions that work on the return of slice()/constSlice().

Here’s a test showing the problem (the test will fail):

test "bounded array hash map" {
    var map: std.AutoHashMap(std.BoundedArray(u5, 32), void) = .init(std.testing.allocator);
    defer map.deinit();

    var arr = try std.BoundedArray(u5, 32).fromSlice(&[_]u5{ 1, 2, 3, 4 });

    // Intentionally set some element outside of the populated slice
    arr.buffer[arr.buffer.len - 1] = 1;
    try map.putNoClobber(arr, {});

    // Now change the element that should be irrelevant for hash/eql
    arr.buffer[arr.buffer.len - 1] = 2;
    const gop_result = try map.getOrPut(arr);

    // Should still find the previously added BoundedArray key
    try std.testing.expect(gop_result.found_existing);
}

Something like this would work:

fn BoundedArrayContext(comptime T: type, comptime buffer_capacity: usize) type {
    return struct {
        pub fn hash(self: @This(), key: std.BoundedArray(T, buffer_capacity)) u64 {
            _ = self;
            const slice = key.constSlice();
            if (std.meta.hasUniqueRepresentation(T)) {
                return std.hash.Wyhash.hash(0, std.mem.asBytes(&key));
            } else {
                var hasher = std.hash.Wyhash.init(0);
                for (slice) |v| {
                    std.hash.autoHash(&hasher, v);
                }
                return hasher.final();
            }
        }

        pub fn eql(self: @This(), a: std.BoundedArray(T, buffer_capacity), b: std.BoundedArray(T, buffer_capacity)) bool {
            _ = self;
            return std.mem.eql(T, a.constSlice(), b.constSlice());
        }
    };
}

Changing the map initialization in the test code above to this would get it to pass:

    var map: std.HashMap(
        std.BoundedArray(u5, 32),
        void,
        BoundedArrayContext(u5, 32),
        std.hash_map.default_max_load_percentage,
    ) = .init(std.testing.allocator);

geemili · February 16, 2025, 12:25am

BoundedArrays are just a buffer with a comptime known capacity plus a runtime known length. The buffer is initialized to undefined:

github.com

ziglang/zig/blob/9ad57515b2af63a573da9a08fa60c3817ddc1a7d/lib/std/bounded_array.zig#L35-L43


      
          pub fn BoundedArrayAligned(
              comptime T: type,
              comptime alignment: u29,
              comptime buffer_capacity: usize,
          ) type {
              return struct {
                  const Self = @This();
                  buffer: [buffer_capacity]T align(alignment) = undefined,
                  len: usize = 0,

Let’s peek at the AutoContext function (which powers the AutoArrayHashMap function).

github.com

ziglang/zig/blob/d7f9b5a6618eebf6f2c7c205ebdad47a7959ecc1/lib/std/array_hash_map.zig#L2587-L2607


      
          pub fn AutoContext(comptime K: type) type {
              return struct {
                  pub const hash = getAutoHashFn(K, @This());
                  pub const eql = getAutoEqlFn(K, @This());
              };
          }
          
          pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u32) {
              return struct {
                  fn hash(ctx: Context, key: K) u32 {
                      _ = ctx;
                      if (std.meta.hasUniqueRepresentation(K)) {
                          return @truncate(Wyhash.hash(0, std.mem.asBytes(&key)));
                      } else {
                          var hasher = Wyhash.init(0);
                          autoHash(&hasher, key);
                          return @truncate(hasher.final());
                      }
                  }
              }.hash;
          }

You probably aren’t getting the first branch of getAutoHashFn, since u5 will be stored in a u8 by default:

github.com

ziglang/zig/blob/9ad57515b2af63a573da9a08fa60c3817ddc1a7d/lib/std/meta.zig#L1188


      
          else => false, // TODO can we know if it's true for some of these types ?
          
          .@"anyframe",
          .@"enum",
          .error_set,
          .@"fn",
          => true,
          
          .bool => false,
          
          .int => |info| @sizeOf(T) * 8 == info.bits,
          
          .pointer => |info| info.size != .slice,
          
          .optional => |info| switch (@typeInfo(info.child)) {
              .pointer => |ptr| !ptr.is_allowzero and switch (ptr.size) {
                  .slice, .c => false,
                  .one, .many => true,
              },
              else => false,
          },

So we must now look at autoHash.

std.hash.autoHash will start wit the std.BoundedArray struct and hash the buffer field, and then the len field:

github.com

ziglang/zig/blob/master/lib/std/hash/auto_hash.zig#L132-L138


      
          .@"struct" => |info| {
              inline for (info.fields) |field| {
                  // We reuse the hash of the previous field as the seed for the
                  // next one so that they're dependant.
                  hash(hasher, @field(key, field.name), strat);
              }
          },

The buffer field will be hashed by the hashArray function:

github.com

ziglang/zig/blob/9ad57515b2af63a573da9a08fa60c3817ddc1a7d/lib/std/hash/auto_hash.zig#L55-L60


      
          /// Helper function to hash a set of contiguous objects, from an array or slice.
          pub fn hashArray(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
              for (key) |element| {
                  hash(hasher, element, strat);
              }
          }

And this is where the disconnect happens. std.hash.autoHash is hashing the entirety of the buffer field, where you are only expecting it to hash the portion of the buffer that is specified by the len field.

Theoretically, std could support this use case by having some kind of hash function, similar to the current format function. However it is probably better to just implement your own hashmap context that will make sure to only use the values specified by len.

vulpesx · February 16, 2025, 1:17am

AutoContext should be changed to use hash and eql methods that have the correct signature on the given type.
And types like BoundedArray should use that, It’s reasonable to expect types in std to behave with each other.

geemili · February 16, 2025, 2:12am

My main hesitation would be the amount of duck typing this would introduce. What is the correct signature for hash? What is the correct signature for eql? Depending on how the std library handles it, this would also result in the names hash and eql being off limits unless they exactly match what std expects. All of these concerns can be answered, but they would have to be answered.

Other than that, I agree that this would be nice to have in std.

In any case current code will have to work around the current limitations.

vulpesx · February 16, 2025, 2:41am

On second thought a HashMapContext fn would be better

ericlang · February 16, 2025, 8:06am

Thank you both!
I was suspecting the autohash system would include the unused data beyond “len” in the hash.
BTW: I learned another thing from your code. We can use .init()

squeek502 · February 16, 2025, 8:30am

github.com/ziglang/zig

compiler: implement decl literals

ziglang:master ← mlugg:decl-literals

opened 01:53AM - 31 Aug 24 UTC

mlugg

+336 -15

Pretty straightforward -- see commit messages. I also added "default initializat…ion" decls to `ArrayListUnmanaged`, `HashMapUnmanaged`, `ArrayHashMapUnmanaged`, and `GeneralPurposeAllocator`. I am not yet using these in the compiler or standard library to avoid a need for a zig1.wasm update. ## Release Notes Zig 0.14.0 extends the "enum literal" syntax (`.foo`) to provide a new feature, known as "decl literals". Now, an enum literal `.foo` doesn't necessarily refer to an enum variant, but, using \[Result Location Semantics\]\(langref link\), can also refer to any declaration on the target type. For instance, consider the following example: ```zig const S = struct { x: u32, const default: S = .{ .x = 123 }; }; test "decl literal" { const val: S = .default; try std.testing.expectEqual(123, val.x); } const std = @import("std"); ``` Since the initialization expression of `val` has a result type of `S`, the initialization is effectively equivalent to `S.default`. This can be particularly useful when initializing struct fields to avoid having to specify the type again: ```zig const S = struct { x: u32, y: u32, const default: S = .{ .x = 1, .y = 2 }; const other: S = .{ .x = 3, .y = 4 }; }; const Wrapper = struct { val: S = .default, }; test "decl literal initializing struct field" { const a: Wrapper = .{}; try std.testing.expectEqual(1, a.val.x); try std.testing.expectEqual(2, a.val.y); const b: Wrapper = .{ .val = .other }; try std.testing.expectEqual(3, b.val.x); try std.testing.expectEqual(4, b.val.y); } const std = @import("std"); ``` It can also help in avoiding \[Faulty Default Field Values\]\(langref link\), like in the following example: ```zig /// `ptr` points to a `[len]u32`. pub const BufferA = extern struct { ptr: ?[*]u32 = null, len: usize = 0 }; // The default values given above are trying to make the buffer default to "empty". var empty_buf_a: BufferA = .{}; // However, they violate the guidance given in the language reference, because you can write this: var bad_buf_a: BufferA = .{ .len = 10 }; // That's not safe, because the `null` and `0` defaults are "tied together". Decl literals make it // convenient to represent this case correctly: /// `ptr` points to a `[len]u32`. pub const BufferB = extern struct { ptr: ?[*]u32, len: usize, pub const empty: BufferB = .{ .ptr = null, .len = 0 }; }; // We can still easily create an empty buffer: var empty_buf_b: BufferB = .empty; // ...but the language no longer hides incorrect field overrides from us! // If we want to override a field, we'd have to specify both, making the error obvious: var bad_buf_b: BufferB = .{ .ptr = null, .len = 10 }; // clearly wrong! ``` Many existing uses of field default values may be more appropriately handled by a declaration named `default` or `empty` or similar, to ensure data invariants are not violated by overriding single fields. Decl literals also support function calls, like this: ```zig const S = struct { x: u32, y: u32, fn init(val: u32) S { return .{ .x = val + 1, .y = val + 2 }; } }; test "call decl literal" { const a: S = .init(100); try std.testing.expectEqual(101, a.val.x); try std.testing.expectEqual(102, a.val.y); } const std = @import("std"); ``` As before, this syntax can be particularly useful when initializing struct fields. It also supports calling functions which return error unions via `try`. The following example uses these in combination to initialize a thin wrapper around an `ArrayListUnmanaged`: ```zig const Buffer = struct { data: std.ArrayListUnmanaged(u32), fn initCapacity(allocator: std.mem.Allocator, capacity: usize) !Buffer { return .{ .data = try .initCapacity(allocator, capacity) }; } }; test "initialize Buffer with decl literal" { var b: Buffer = try .initCapacity(std.testing.allocator, 5); defer b.data.deinit(std.testing.allocator); b.data.appendAssumeCapacity(123); try std.testing.expectEqual(1, b.data.items.len); try std.testing.expectEqual(123, b.data.items[0]); } ``` The introduction of decl literals comes with some standard library changes. In particular, unmanaged containers, including `ArrayListUnmanaged` and `HashMapUnmanaged`, should no longer be default-initialized with `.{}`, because the default field values here violate the guidance discussed above. Instead, they should be initialized using their `empty` declaration, which can be conveniently accessed via decl literals: ```zig const Buffer = struct { foo: std.ArrayListUnmanaged(u32) = .empty, }; test "default initialize Buffer" { var b: Buffer = .{}; defer b.data.deinit(std.testing.allocator); b.data.appendAssumeCapacity(123); try std.testing.expectEqual(1, b.data.items.len); try std.testing.expectEqual(123, b.data.items[0]); } ``` Similarly, `std.heap.GeneralPurposeAllocator` should now be initialized with its `.init` declaration. The deprecated default field values for these data structures will be removed in the next release cycle.

ericlang · February 16, 2025, 8:51am

Interesting…
Indeed I notitced when initializing to:
var suffix : std.BoundedArray(u5, 32) = .{};
(it is a local var anyway)
the autohash seems to work correctly.

squeek502 · February 16, 2025, 9:19am

Not sure I quite understand what you mean, but note that autoHash seeming to ‘work’ could be a coincidence due to undefined being set to 0xaa in debug mode (or some unknown value in other modes), so the unused bytes of buffer may just so happen to compare equal.

The test case I posted above is a more reliable indicator of whether or not a hash/eql actually works correctly.

ericlang · February 16, 2025, 9:22am

True, I was wondering if
std.BoundedArray(u5, 32) = .{};
initializes to 32 zero’s… (with len = 0)
if not how?

squeek502 · February 16, 2025, 9:24am

buffer has a default value of undefined:

github.com

ziglang/zig/blob/ddff1fa4c6cb80363a2c2a34fd5eace95be585d4/lib/std/bounded_array.zig#L42


      
          //  const b = @ptrCast(*const [1]u16, a.constSlice().ptr);
          //  try testing.expectEqual(@as(u16, 65535), b[0]);
          /// ```
          pub fn BoundedArrayAligned(
              comptime T: type,
              comptime alignment: u29,
              comptime buffer_capacity: usize,
          ) type {
              return struct {
                  const Self = @This();
                  buffer: [buffer_capacity]T align(alignment) = undefined,
                  len: usize = 0,
          
                  /// Set the actual length of the slice.
                  /// Returns error.Overflow if it exceeds the length of the backing array.
                  pub fn init(len: usize) error{Overflow}!Self {
                      if (len > buffer_capacity) return error.Overflow;
                      return Self{ .len = len };
                  }
          
                  /// View the internal array as a slice whose size was previously set.

See the undefined docs:

https://ziglang.org/documentation/master/#undefined

ericlang · February 16, 2025, 9:25am

Yes I saw the undefined in the code…

squeek502 · February 16, 2025, 9:29am

So it initializes the bytes of buffer to whatever memory was there before, i.e. it doesn’t initialize it to any particular value at all. In the future, usage of autoHash with BoundedArray may trigger a panic since it could (incorrectly) be using the parts of buffer that are still undefined:

github.com/ziglang/zig

debug safety feature: runtime undefined value detection

opened 07:52PM - 08 Nov 16 UTC

andrewrk

proposal accepted frontend

If the programmer initializes a variable to undefined or otherwise sets the valu…e to undefined anywhere, we can secretly make the type of the variable a maybe type and have a bit to keep track of whether it is undefined at any given point in time. Then if the programmer tries to use a value which is undefined, we detect it with a runtime check, and crash with a stack trace.