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