Merge pull request #10742 from ziglang/ArrayHashMapEql

std: make ArrayHashMap eql function accept an additional param

4 files changed, 42 insertions, 25 deletions

diff --git a/lib/std/array_hash_map.zig b/lib/std/array_hash_map.zig
index 7ebafc0a1b..4359c30083 100644
--- a/lib/std/array_hash_map.zig
+++ b/lib/std/array_hash_map.zig
@@ -37,8 +37,9 @@ pub const StringContext = struct {
         _ = self;
         return hashString(s);
     }
-    pub fn eql(self: @This(), a: []const u8, b: []const u8) bool {
+    pub fn eql(self: @This(), a: []const u8, b: []const u8, b_index: usize) bool {
         _ = self;
+        _ = b_index;
         return eqlString(a, b);
     }
 };
@@ -76,7 +77,7 @@ pub fn ArrayHashMap(
     comptime Context: type,
     comptime store_hash: bool,
 ) type {
-    comptime std.hash_map.verifyContext(Context, K, K, u32);
+    comptime std.hash_map.verifyContext(Context, K, K, u32, true);
     return struct {
         unmanaged: Unmanaged,
         allocator: Allocator,
@@ -462,7 +463,7 @@ pub fn ArrayHashMapUnmanaged(
     comptime Context: type,
     comptime store_hash: bool,
 ) type {
-    comptime std.hash_map.verifyContext(Context, K, K, u32);
+    comptime std.hash_map.verifyContext(Context, K, K, u32, true);
     return struct {
         /// It is permitted to access this field directly.
         entries: DataList = .{},
@@ -700,7 +701,7 @@ pub fn ArrayHashMapUnmanaged(
                 const hashes_array = slice.items(.hash);
                 const keys_array = slice.items(.key);
                 for (keys_array) |*item_key, i| {
-                    if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*)) {
+                    if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*, i)) {
                         return GetOrPutResult{
                             .key_ptr = item_key,
                             // workaround for #6974
@@ -933,7 +934,7 @@ pub fn ArrayHashMapUnmanaged(
                 const hashes_array = slice.items(.hash);
                 const keys_array = slice.items(.key);
                 for (keys_array) |*item_key, i| {
-                    if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*)) {
+                    if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*, i)) {
                         return i;
                     }
                 }
@@ -1245,7 +1246,7 @@ pub fn ArrayHashMapUnmanaged(
                 const keys_array = slice.items(.key);
                 for (keys_array) |*item_key, i| {
                     const hash_match = if (store_hash) hashes_array[i] == key_hash else true;
-                    if (hash_match and key_ctx.eql(key, item_key.*)) {
+                    if (hash_match and key_ctx.eql(key, item_key.*, i)) {
                         const removed_entry: KV = .{
                             .key = keys_array[i],
                             .value = slice.items(.value)[i],
@@ -1286,7 +1287,7 @@ pub fn ArrayHashMapUnmanaged(
                 const keys_array = slice.items(.key);
                 for (keys_array) |*item_key, i| {
                     const hash_match = if (store_hash) hashes_array[i] == key_hash else true;
-                    if (hash_match and key_ctx.eql(key, item_key.*)) {
+                    if (hash_match and key_ctx.eql(key, item_key.*, i)) {
                         switch (removal_type) {
                             .swap => self.entries.swapRemove(i),
                             .ordered => self.entries.orderedRemove(i),
@@ -1483,8 +1484,9 @@ pub fn ArrayHashMapUnmanaged(
 
                 // This pointer survives the following append because we call
                 // entries.ensureTotalCapacity before getOrPutInternal.
-                const hash_match = if (store_hash) h == hashes_array[slot_data.entry_index] else true;
-                if (hash_match and checkedEql(ctx, key, keys_array[slot_data.entry_index])) {
+                const i = slot_data.entry_index;
+                const hash_match = if (store_hash) h == hashes_array[i] else true;
+                if (hash_match and checkedEql(ctx, key, keys_array[i], i)) {
                     return .{
                         .found_existing = true,
                         .key_ptr = &keys_array[slot_data.entry_index],
@@ -1571,8 +1573,9 @@ pub fn ArrayHashMapUnmanaged(
                 if (slot_data.isEmpty() or slot_data.distance_from_start_index < distance_from_start_index)
                     return null;
 
-                const hash_match = if (store_hash) h == hashes_array[slot_data.entry_index] else true;
-                if (hash_match and checkedEql(ctx, key, keys_array[slot_data.entry_index]))
+                const i = slot_data.entry_index;
+                const hash_match = if (store_hash) h == hashes_array[i] else true;
+                if (hash_match and checkedEql(ctx, key, keys_array[i], i))
                     return slot;
             }
             unreachable;
@@ -1624,7 +1627,7 @@ pub fn ArrayHashMapUnmanaged(
         }
 
         inline fn checkedHash(ctx: anytype, key: anytype) u32 {
-            comptime std.hash_map.verifyContext(@TypeOf(ctx), @TypeOf(key), K, u32);
+            comptime std.hash_map.verifyContext(@TypeOf(ctx), @TypeOf(key), K, u32, true);
             // If you get a compile error on the next line, it means that
             const hash = ctx.hash(key); // your generic hash function doesn't accept your key
             if (@TypeOf(hash) != u32) {
@@ -1633,10 +1636,10 @@ pub fn ArrayHashMapUnmanaged(
             }
             return hash;
         }
-        inline fn checkedEql(ctx: anytype, a: anytype, b: K) bool {
-            comptime std.hash_map.verifyContext(@TypeOf(ctx), @TypeOf(a), K, u32);
+        inline fn checkedEql(ctx: anytype, a: anytype, b: K, b_index: usize) bool {
+            comptime std.hash_map.verifyContext(@TypeOf(ctx), @TypeOf(a), K, u32, true);
             // If you get a compile error on the next line, it means that
-            const eql = ctx.eql(a, b); // your generic eql function doesn't accept (self, adapt key, K)
+            const eql = ctx.eql(a, b, b_index); // your generic eql function doesn't accept (self, adapt key, K, index)
             if (@TypeOf(eql) != bool) {
                 @compileError("Context " ++ @typeName(@TypeOf(ctx)) ++ " has a generic eql function that returns the wrong type!\n" ++
                     @typeName(bool) ++ " was expected, but found " ++ @typeName(@TypeOf(eql)));
@@ -2255,9 +2258,10 @@ pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K)
     }.hash;
 }
 
-pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) {
+pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K, usize) bool) {
     return struct {
-        fn eql(ctx: Context, a: K, b: K) bool {
+        fn eql(ctx: Context, a: K, b: K, b_index: usize) bool {
+            _ = b_index;
             _ = ctx;
             return meta.eql(a, b);
         }
diff --git a/lib/std/builtin.zig b/lib/std/builtin.zig
index e4ab6d7e8f..7c37fa7616 100644
--- a/lib/std/builtin.zig
+++ b/lib/std/builtin.zig
@@ -203,12 +203,14 @@ pub const TypeInfo = union(enum) {
     /// therefore must be kept in sync with the compiler implementation.
     pub const Int = struct {
         signedness: Signedness,
+        /// TODO make this u16 instead of comptime_int
         bits: comptime_int,
     };
 
     /// This data structure is used by the Zig language code generation and
     /// therefore must be kept in sync with the compiler implementation.
     pub const Float = struct {
+        /// TODO make this u16 instead of comptime_int
         bits: comptime_int,
     };
 
@@ -218,6 +220,7 @@ pub const TypeInfo = union(enum) {
         size: Size,
         is_const: bool,
         is_volatile: bool,
+        /// TODO make this u16 instead of comptime_int
         alignment: comptime_int,
         address_space: AddressSpace,
         child: type,
diff --git a/lib/std/hash/auto_hash.zig b/lib/std/hash/auto_hash.zig
index 22fd6526f4..089d8f4df2 100644
--- a/lib/std/hash/auto_hash.zig
+++ b/lib/std/hash/auto_hash.zig
@@ -81,7 +81,6 @@ pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
         .NoReturn,
         .Opaque,
         .Undefined,
-        .Void,
         .Null,
         .ComptimeFloat,
         .ComptimeInt,
@@ -91,6 +90,8 @@ pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
         .Float,
         => @compileError("unable to hash type " ++ @typeName(Key)),
 
+        .Void => return,
+
         // Help the optimizer see that hashing an int is easy by inlining!
         // TODO Check if the situation is better after #561 is resolved.
         .Int => {
diff --git a/lib/std/hash_map.zig b/lib/std/hash_map.zig
index 2c0010211a..53d3f7004d 100644
--- a/lib/std/hash_map.zig
+++ b/lib/std/hash_map.zig
@@ -131,7 +131,13 @@ pub const default_max_load_percentage = 80;
 /// If you are passing a context to a *Adapted function, PseudoKey is the type
 /// of the key parameter.  Otherwise, when creating a HashMap or HashMapUnmanaged
 /// type, PseudoKey = Key = K.
-pub fn verifyContext(comptime RawContext: type, comptime PseudoKey: type, comptime Key: type, comptime Hash: type) void {
+pub fn verifyContext(
+    comptime RawContext: type,
+    comptime PseudoKey: type,
+    comptime Key: type,
+    comptime Hash: type,
+    comptime is_array: bool,
+) void {
     comptime {
         var allow_const_ptr = false;
         var allow_mutable_ptr = false;
@@ -166,7 +172,9 @@ pub fn verifyContext(comptime RawContext: type, comptime PseudoKey: type, compti
             const prefix = "\n  ";
             const deep_prefix = prefix ++ "  ";
             const hash_signature = "fn (self, " ++ @typeName(PseudoKey) ++ ") " ++ @typeName(Hash);
-            const eql_signature = "fn (self, " ++ @typeName(PseudoKey) ++ ", " ++ @typeName(Key) ++ ") bool";
+            const index_param = if (is_array) ", b_index: usize" else "";
+            const eql_signature = "fn (self, " ++ @typeName(PseudoKey) ++ ", " ++
+                @typeName(Key) ++ index_param ++ ") bool";
             const err_invalid_hash_signature = prefix ++ @typeName(Context) ++ ".hash must be " ++ hash_signature ++
                 deep_prefix ++ "but is actually " ++ @typeName(@TypeOf(Context.hash));
             const err_invalid_eql_signature = prefix ++ @typeName(Context) ++ ".eql must be " ++ eql_signature ++
@@ -255,7 +263,8 @@ pub fn verifyContext(comptime RawContext: type, comptime PseudoKey: type, compti
             const info = @typeInfo(@TypeOf(eql));
             if (info == .Fn) {
                 const func = info.Fn;
-                if (func.args.len != 3) {
+                const args_len = if (is_array) 4 else 3;
+                if (func.args.len != args_len) {
                     errors = errors ++ lazy.err_invalid_eql_signature;
                 } else {
                     var emitted_signature = false;
@@ -360,7 +369,7 @@ pub fn HashMap(
     comptime Context: type,
     comptime max_load_percentage: u64,
 ) type {
-    comptime verifyContext(Context, K, K, u64);
+    comptime verifyContext(Context, K, K, u64, false);
     return struct {
         unmanaged: Unmanaged,
         allocator: Allocator,
@@ -683,7 +692,7 @@ pub fn HashMapUnmanaged(
 ) type {
     if (max_load_percentage <= 0 or max_load_percentage >= 100)
         @compileError("max_load_percentage must be between 0 and 100.");
-    comptime verifyContext(Context, K, K, u64);
+    comptime verifyContext(Context, K, K, u64, false);
 
     return struct {
         const Self = @This();
@@ -1108,7 +1117,7 @@ pub fn HashMapUnmanaged(
         /// from this function.  To encourage that, this function is
         /// marked as inline.
         inline fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize {
-            comptime verifyContext(@TypeOf(ctx), @TypeOf(key), K, Hash);
+            comptime verifyContext(@TypeOf(ctx), @TypeOf(key), K, Hash, false);
 
             if (self.size == 0) {
                 return null;
@@ -1291,7 +1300,7 @@ pub fn HashMapUnmanaged(
             return result;
         }
         pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
-            comptime verifyContext(@TypeOf(ctx), @TypeOf(key), K, Hash);
+            comptime verifyContext(@TypeOf(ctx), @TypeOf(key), K, Hash, false);
 
             // If you get a compile error on this line, it means that your generic hash
             // function is invalid for these parameters.