1const std = @import("std");
2const assert = std.debug.assert;
3const mem = std.mem;
4
5/// Describes how pointer types should be hashed.
6pub const HashStrategy = enum {
7 /// Do not follow pointers, only hash their value.
8 Shallow,
9
10 /// Follow pointers, hash the pointee content.
11 /// Only dereferences one level, ie. it is changed into .Shallow when a
12 /// pointer type is encountered.
13 Deep,
14
15 /// Follow pointers, hash the pointee content.
16 /// Dereferences all pointers encountered.
17 /// Assumes no cycle.
18 DeepRecursive,
19};
20
21/// Helper function to hash a pointer and mutate the strategy if needed.
22pub fn hashPointer(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
23 const info = @typeInfo(@TypeOf(key));
24
25 switch (info.pointer.size) {
26 .one => switch (strat) {
27 .Shallow => hash(hasher, @intFromPtr(key), .Shallow),
28 .Deep => hash(hasher, key.*, .Shallow),
29 .DeepRecursive => hash(hasher, key.*, .DeepRecursive),
30 },
31
32 .slice => {
33 switch (strat) {
34 .Shallow => {
35 hashPointer(hasher, key.ptr, .Shallow);
36 },
37 .Deep => hashArray(hasher, key, .Shallow),
38 .DeepRecursive => hashArray(hasher, key, .DeepRecursive),
39 }
40 hash(hasher, key.len, .Shallow);
41 },
42
43 .many,
44 .c,
45 => switch (strat) {
46 .Shallow => hash(hasher, @intFromPtr(key), .Shallow),
47 else => @compileError(
48 \\ unknown-length pointers and C pointers cannot be hashed deeply.
49 \\ Consider providing your own hash function.
50 ),
51 },
52 }
53}
54
55/// Helper function to hash a set of contiguous objects, from an array or slice.
56pub fn hashArray(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
57 for (key) |element| {
58 hash(hasher, element, strat);
59 }
60}
61
62/// Provides generic hashing for any eligible type.
63/// Strategy is provided to determine if pointers should be followed or not.
64pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
65 const Key = @TypeOf(key);
66 const Hasher = switch (@typeInfo(@TypeOf(hasher))) {
67 .pointer => |ptr| ptr.child,
68 else => @TypeOf(hasher),
69 };
70
71 if (strat == .Shallow and std.meta.hasUniqueRepresentation(Key)) {
72 @call(.always_inline, Hasher.update, .{ hasher, mem.asBytes(&key) });
73 return;
74 }
75
76 switch (@typeInfo(Key)) {
77 .noreturn,
78 .@"opaque",
79 .spirv,
80 .undefined,
81 .null,
82 .comptime_float,
83 .comptime_int,
84 .type,
85 .enum_literal,
86 .frame,
87 .float,
88 => @compileError("unable to hash type " ++ @typeName(Key)),
89
90 .void => return,
91
92 // Help the optimizer see that hashing an int is easy by inlining!
93 // TODO Check if the situation is better after #561 is resolved.
94 .int => |int| switch (int.signedness) {
95 .signed => hash(hasher, @as(@Int(.unsigned, int.bits), @bitCast(key)), strat),
96 .unsigned => {
97 if (std.meta.hasUniqueRepresentation(Key)) {
98 @call(.always_inline, Hasher.update, .{ hasher, std.mem.asBytes(&key) });
99 } else {
100 // Take only the part containing the key value, the remaining
101 // bytes are undefined and must not be hashed!
102 const byte_size = @divCeil(@bitSizeOf(Key), 8);
103 @call(.always_inline, Hasher.update, .{ hasher, std.mem.asBytes(&key)[0..byte_size] });
104 }
105 },
106 },
107
108 .bool => hash(hasher, @intFromBool(key), strat),
109 .@"enum" => hash(hasher, @backingInt(key), strat),
110 .error_set => hash(hasher, @intFromError(key), strat),
111 .@"anyframe", .@"fn" => hash(hasher, @intFromPtr(key), strat),
112
113 .pointer => @call(.always_inline, hashPointer, .{ hasher, key, strat }),
114
115 .optional => if (key) |k| hash(hasher, k, strat),
116
117 .array => hashArray(hasher, key, strat),
118
119 .vector => |info| {
120 if (std.meta.hasUniqueRepresentation(Key)) {
121 hasher.update(mem.asBytes(&key));
122 } else {
123 comptime var i = 0;
124 inline while (i < info.len) : (i += 1) {
125 hash(hasher, key[i], strat);
126 }
127 }
128 },
129
130 .@"struct" => |info| {
131 inline for (info.field_names) |field_name| {
132 // We reuse the hash of the previous field as the seed for the
133 // next one so that they're dependant.
134 hash(hasher, @field(key, field_name), strat);
135 }
136 },
137
138 .@"union" => |info| blk: {
139 if (info.tag_type) |tag_type| {
140 const tag = std.meta.activeTag(key);
141 hash(hasher, tag, strat);
142 inline for (info.field_names, info.field_types) |field_name, field_type| {
143 if (@field(tag_type, field_name) == tag) {
144 if (field_type != void) {
145 hash(hasher, @field(key, field_name), strat);
146 }
147 break :blk;
148 }
149 }
150 unreachable;
151 } else @compileError("cannot hash untagged union type: " ++ @typeName(Key) ++ ", provide your own hash function");
152 },
153
154 .error_union => blk: {
155 const payload = key catch |err| {
156 hash(hasher, err, strat);
157 break :blk;
158 };
159 hash(hasher, payload, strat);
160 },
161 }
162}
163
164inline fn typeContainsSlice(comptime K: type) bool {
165 return switch (@typeInfo(K)) {
166 .pointer => |info| info.size == .slice,
167
168 inline .@"struct", .@"union" => |info| {
169 inline for (info.field_types) |field_type| {
170 if (typeContainsSlice(field_type)) {
171 return true;
172 }
173 }
174 return false;
175 },
176
177 else => false,
178 };
179}
180
181/// Provides generic hashing for any eligible type.
182/// Only hashes `key` itself, pointers are not followed.
183/// Slices as well as unions and structs containing slices are rejected to avoid
184/// ambiguity on the user's intention.
185pub fn autoHash(hasher: anytype, key: anytype) void {
186 const Key = @TypeOf(key);
187 if (comptime typeContainsSlice(Key)) {
188 @compileError("std.hash.autoHash does not allow slices as well as unions and structs containing slices here (" ++ @typeName(Key) ++
189 ") because the intent is unclear. Consider using std.hash.autoHashStrat or providing your own hash function instead.");
190 }
191
192 hash(hasher, key, .Shallow);
193}
194
195const testing = std.testing;
196const Wyhash = std.hash.Wyhash;
197
198fn testHash(key: anytype) u64 {
199 // Any hash could be used here, for testing autoHash.
200 var hasher = Wyhash.init(0);
201 hash(&hasher, key, .Shallow);
202 return hasher.final();
203}
204
205fn testHashShallow(key: anytype) u64 {
206 // Any hash could be used here, for testing autoHash.
207 var hasher = Wyhash.init(0);
208 hash(&hasher, key, .Shallow);
209 return hasher.final();
210}
211
212fn testHashDeep(key: anytype) u64 {
213 // Any hash could be used here, for testing autoHash.
214 var hasher = Wyhash.init(0);
215 hash(&hasher, key, .Deep);
216 return hasher.final();
217}
218
219fn testHashDeepRecursive(key: anytype) u64 {
220 // Any hash could be used here, for testing autoHash.
221 var hasher = Wyhash.init(0);
222 hash(&hasher, key, .DeepRecursive);
223 return hasher.final();
224}
225
226test "typeContainsSlice" {
227 comptime {
228 try testing.expect(!typeContainsSlice(std.meta.Tag(std.lang.Type)));
229
230 try testing.expect(typeContainsSlice([]const u8));
231 try testing.expect(!typeContainsSlice(u8));
232 const A = struct { x: []const u8 };
233 const B = struct { a: A };
234 const C = struct { b: B };
235 const D = struct { x: u8 };
236 try testing.expect(typeContainsSlice(A));
237 try testing.expect(typeContainsSlice(B));
238 try testing.expect(typeContainsSlice(C));
239 try testing.expect(!typeContainsSlice(D));
240 }
241}
242
243test "hash pointer" {
244 const array = [_]u32{ 123, 123, 123 };
245 const a = &array[0];
246 const b = &array[1];
247 const c = &array[2];
248 const d = a;
249
250 try testing.expect(testHashShallow(a) == testHashShallow(d));
251 try testing.expect(testHashShallow(a) != testHashShallow(c));
252 try testing.expect(testHashShallow(a) != testHashShallow(b));
253
254 try testing.expect(testHashDeep(a) == testHashDeep(a));
255 try testing.expect(testHashDeep(a) == testHashDeep(c));
256 try testing.expect(testHashDeep(a) == testHashDeep(b));
257
258 try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(a));
259 try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(c));
260 try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(b));
261}
262
263test "hash slice shallow" {
264 // Allocate one array dynamically so that we're assured it is not merged
265 // with the other by the optimization passes.
266 const array1 = try std.testing.allocator.create([6]u32);
267 defer std.testing.allocator.destroy(array1);
268 array1.* = [_]u32{ 1, 2, 3, 4, 5, 6 };
269 const array2 = [_]u32{ 1, 2, 3, 4, 5, 6 };
270 // TODO audit deep/shallow - maybe it has the wrong behavior with respect to array pointers and slices
271 var runtime_zero: usize = 0;
272 _ = &runtime_zero;
273 const a = array1[runtime_zero..];
274 const b = array2[runtime_zero..];
275 const c = array1[runtime_zero..3];
276 try testing.expect(testHashShallow(a) == testHashShallow(a));
277 try testing.expect(testHashShallow(a) != testHashShallow(array1));
278 try testing.expect(testHashShallow(a) != testHashShallow(b));
279 try testing.expect(testHashShallow(a) != testHashShallow(c));
280}
281
282test "hash slice deep" {
283 // Allocate one array dynamically so that we're assured it is not merged
284 // with the other by the optimization passes.
285 const array1 = try std.testing.allocator.create([6]u32);
286 defer std.testing.allocator.destroy(array1);
287 array1.* = [_]u32{ 1, 2, 3, 4, 5, 6 };
288 const array2 = [_]u32{ 1, 2, 3, 4, 5, 6 };
289 const a = array1[0..];
290 const b = array2[0..];
291 const c = array1[0..3];
292 try testing.expect(testHashDeep(a) == testHashDeep(a));
293 try testing.expect(testHashDeep(a) == testHashDeep(array1));
294 try testing.expect(testHashDeep(a) == testHashDeep(b));
295 try testing.expect(testHashDeep(a) != testHashDeep(c));
296}
297
298test "hash struct deep" {
299 const Foo = struct {
300 a: u32,
301 b: u16,
302 c: *bool,
303
304 const Self = @This();
305
306 pub fn init(allocator: mem.Allocator, a_: u32, b_: u16, c_: bool) !Self {
307 const ptr = try allocator.create(bool);
308 ptr.* = c_;
309 return Self{ .a = a_, .b = b_, .c = ptr };
310 }
311 };
312
313 const allocator = std.testing.allocator;
314 const foo = try Foo.init(allocator, 123, 10, true);
315 const bar = try Foo.init(allocator, 123, 10, true);
316 const baz = try Foo.init(allocator, 123, 10, false);
317 defer allocator.destroy(foo.c);
318 defer allocator.destroy(bar.c);
319 defer allocator.destroy(baz.c);
320
321 try testing.expect(testHashDeep(foo) == testHashDeep(bar));
322 try testing.expect(testHashDeep(foo) != testHashDeep(baz));
323 try testing.expect(testHashDeep(bar) != testHashDeep(baz));
324
325 var hasher = Wyhash.init(0);
326 const h = testHashDeep(foo);
327 autoHash(&hasher, foo.a);
328 autoHash(&hasher, foo.b);
329 autoHash(&hasher, foo.c.*);
330 try testing.expectEqual(h, hasher.final());
331
332 const h2 = testHashDeepRecursive(&foo);
333 try testing.expect(h2 != testHashDeep(&foo));
334 try testing.expect(h2 == testHashDeep(foo));
335}
336
337test "testHash optional" {
338 const a: ?u32 = 123;
339 const b: ?u32 = null;
340 try testing.expectEqual(testHash(a), testHash(@as(u32, 123)));
341 try testing.expect(testHash(a) != testHash(b));
342 try testing.expectEqual(testHash(b), 0x409638ee2bde459); // wyhash empty input hash
343}
344
345test "testHash array" {
346 const a = [_]u32{ 1, 2, 3 };
347 const h = testHash(a);
348 var hasher = Wyhash.init(0);
349 autoHash(&hasher, @as(u32, 1));
350 autoHash(&hasher, @as(u32, 2));
351 autoHash(&hasher, @as(u32, 3));
352 try testing.expectEqual(h, hasher.final());
353}
354
355test "testHash multi-dimensional array" {
356 const a = [_][]const u32{ &.{ 1, 2, 3 }, &.{ 4, 5 } };
357 const b = [_][]const u32{ &.{ 1, 2 }, &.{ 3, 4, 5 } };
358 try testing.expect(testHash(a) != testHash(b));
359}
360
361test "testHash struct" {
362 const Foo = struct {
363 a: u32 = 1,
364 b: u32 = 2,
365 c: u32 = 3,
366 };
367 const f = Foo{};
368 const h = testHash(f);
369 var hasher = Wyhash.init(0);
370 autoHash(&hasher, @as(u32, 1));
371 autoHash(&hasher, @as(u32, 2));
372 autoHash(&hasher, @as(u32, 3));
373 try testing.expectEqual(h, hasher.final());
374}
375
376test "testHash union" {
377 const Foo = union(enum) {
378 A: u32,
379 B: bool,
380 C: u32,
381 D: void,
382 };
383
384 const a = Foo{ .A = 18 };
385 var b = Foo{ .B = true };
386 const c = Foo{ .C = 18 };
387 const d: Foo = .D;
388 try testing.expect(testHash(a) == testHash(a));
389 try testing.expect(testHash(a) != testHash(b));
390 try testing.expect(testHash(a) != testHash(c));
391 try testing.expect(testHash(a) != testHash(d));
392
393 b = Foo{ .A = 18 };
394 try testing.expect(testHash(a) == testHash(b));
395
396 b = .D;
397 try testing.expect(testHash(d) == testHash(b));
398}
399
400test "testHash vector" {
401 const a: @Vector(4, u32) = [_]u32{ 1, 2, 3, 4 };
402 const b: @Vector(4, u32) = [_]u32{ 1, 2, 3, 5 };
403 try testing.expect(testHash(a) == testHash(a));
404 try testing.expect(testHash(a) != testHash(b));
405
406 const c: @Vector(4, u31) = [_]u31{ 1, 2, 3, 4 };
407 const d: @Vector(4, u31) = [_]u31{ 1, 2, 3, 5 };
408 try testing.expect(testHash(c) == testHash(c));
409 try testing.expect(testHash(c) != testHash(d));
410}
411
412test "testHash error union" {
413 const Errors = error{Test};
414 const Foo = struct {
415 a: u32 = 1,
416 b: u32 = 2,
417 c: u32 = 3,
418 };
419 const f = Foo{};
420 const g: Errors!Foo = Errors.Test;
421 try testing.expect(testHash(f) != testHash(g));
422 try testing.expect(testHash(f) == testHash(Foo{}));
423 try testing.expect(testHash(g) == testHash(Errors.Test));
424}