跳转到内容

std.hash.auto_hash

标准库Zig 0.17.0官方原文
源码std/hash/auto_hash.zig

第 1 行

std.hash.auto_hash.assert

别名

第 2 行

别名目标 std.debug.assert

std.hash.auto_hash.autoHash

函数

第 185 行

为所有符合条件的类型提供泛型哈希。 仅对 key 本身计算哈希,不跟随指针。 拒绝切片,以及包含切片的联合体和结构体, 避免对用户意图产生歧义。

pub fn autoHash(hasher: anytype, key: anytype) void

std.hash.auto_hash.hash

函数

第 64 行

为所有符合条件的类型提供泛型哈希。 通过所提供的策略决定是否跟随指针。

pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void

参数

strat: HashStrategy

std.hash.auto_hash.hashArray

函数

第 56 行

用于对数组或切片中一组连续对象进行哈希的辅助函数。

pub fn hashArray(hasher: anytype, key: anytype, comptime strat: HashStrategy) void

参数

strat: HashStrategy

std.hash.auto_hash.hashPointer

函数

第 22 行

用于对指针进行哈希,并按需修改策略的辅助函数。

pub fn hashPointer(hasher: anytype, key: anytype, comptime strat: HashStrategy) void

参数

strat: HashStrategy

std.hash.auto_hash.HashStrategy

容器

第 6 行

描述指针类型的哈希方式。

字段

Shallow

不要跟随指针,只对其值进行哈希。

Deep

跟随指针,对指向内容进行哈希。 仅解引用一级,即遇到指针类型时会转为 .Shallow。

DeepRecursive

沿指针对所指内容进行哈希。 解引用遇到的所有指针。 假定不存在环。

std.hash.auto_hash.init

函数

第 306 行

pub fn init(allocator: mem.Allocator, a_: u32, b_: u16, c_: bool) !Self

参数

allocator: mem.Allocator
a_: u32
b_: u16
c_: bool

std.hash.auto_hash.mem

别名

第 3 行

别名目标 std.mem

std.hash.auto_hash.Self

别名

第 304 行

别名目标 std.hash.auto_hash

std.hash.auto_hash.std

别名

第 1 行

别名目标 std

std.hash.auto_hash.testHash

函数

第 198 行

fn testHash(key: anytype) u64

std.hash.auto_hash.testHashDeep

函数

第 212 行

fn testHashDeep(key: anytype) u64

std.hash.auto_hash.testHashDeepRecursive

函数

第 219 行

fn testHashDeepRecursive(key: anytype) u64

std.hash.auto_hash.testHashShallow

函数

第 205 行

fn testHashShallow(key: anytype) u64

std.hash.auto_hash.testing

别名

第 195 行

别名目标 std.testing

std.hash.auto_hash.typeContainsSlice

函数

第 164 行

inline fn typeContainsSlice(comptime K: type) bool

参数

K: type

std.hash.auto_hash.Wyhash

别名

第 196 行

别名目标 std.hash.Wyhash

源码

std/hash/auto_hash.zig

const std = @import("std");
const assert = std.debug.assert;
const mem = std.mem;

/// 描述指针类型的哈希方式。
pub const HashStrategy = enum {
    /// 不要跟随指针,只对其值进行哈希。
    Shallow,

    /// 跟随指针,对指向内容进行哈希。
    /// 仅解引用一级,即遇到指针类型时会转为 .Shallow。
    ///
    Deep,

    /// 沿指针对所指内容进行哈希。
    /// 解引用遇到的所有指针。
    /// 假定不存在环。
    DeepRecursive,
};

/// 用于对指针进行哈希,并按需修改策略的辅助函数。
pub fn hashPointer(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
    const info = @typeInfo(@TypeOf(key));

    switch (info.pointer.size) {
        .one => switch (strat) {
            .Shallow => hash(hasher, @intFromPtr(key), .Shallow),
            .Deep => hash(hasher, key.*, .Shallow),
            .DeepRecursive => hash(hasher, key.*, .DeepRecursive),
        },

        .slice => {
            switch (strat) {
                .Shallow => {
                    hashPointer(hasher, key.ptr, .Shallow);
                },
                .Deep => hashArray(hasher, key, .Shallow),
                .DeepRecursive => hashArray(hasher, key, .DeepRecursive),
            }
            hash(hasher, key.len, .Shallow);
        },

        .many,
        .c,
        => switch (strat) {
            .Shallow => hash(hasher, @intFromPtr(key), .Shallow),
            else => @compileError(
                \\ unknown-length pointers and C pointers cannot be hashed deeply.
                \\ Consider providing your own hash function.
            ),
        },
    }
}

/// 用于对数组或切片中一组连续对象进行哈希的辅助函数。
pub fn hashArray(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
    for (key) |element| {
        hash(hasher, element, strat);
    }
}

/// 为所有符合条件的类型提供泛型哈希。
/// 通过所提供的策略决定是否跟随指针。
pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
    const Key = @TypeOf(key);
    const Hasher = switch (@typeInfo(@TypeOf(hasher))) {
        .pointer => |ptr| ptr.child,
        else => @TypeOf(hasher),
    };

    if (strat == .Shallow and std.meta.hasUniqueRepresentation(Key)) {
        @call(.always_inline, Hasher.update, .{ hasher, mem.asBytes(&key) });
        return;
    }

    switch (@typeInfo(Key)) {
        .noreturn,
        .@"opaque",
        .spirv,
        .undefined,
        .null,
        .comptime_float,
        .comptime_int,
        .type,
        .enum_literal,
        .frame,
        .float,
        => @compileError("unable to hash type " ++ @typeName(Key)),

        .void => return,

        // 通过内联帮助优化器识别整数哈希很简单。
        // TODO: 检查 #561 解决后情况是否改善。
        .int => |int| switch (int.signedness) {
            .signed => hash(hasher, @as(@Int(.unsigned, int.bits), @bitCast(key)), strat),
            .unsigned => {
                if (std.meta.hasUniqueRepresentation(Key)) {
                    @call(.always_inline, Hasher.update, .{ hasher, std.mem.asBytes(&key) });
                } else {
                    // 仅取包含键值的部分,其余
                    // 字节未定义,绝不可参与哈希!
                    const byte_size = @divCeil(@bitSizeOf(Key), 8);
                    @call(.always_inline, Hasher.update, .{ hasher, std.mem.asBytes(&key)[0..byte_size] });
                }
            },
        },

        .bool => hash(hasher, @intFromBool(key), strat),
        .@"enum" => hash(hasher, @backingInt(key), strat),
        .error_set => hash(hasher, @intFromError(key), strat),
        .@"anyframe", .@"fn" => hash(hasher, @intFromPtr(key), strat),

        .pointer => @call(.always_inline, hashPointer, .{ hasher, key, strat }),

        .optional => if (key) |k| hash(hasher, k, strat),

        .array => hashArray(hasher, key, strat),

        .vector => |info| {
            if (std.meta.hasUniqueRepresentation(Key)) {
                hasher.update(mem.asBytes(&key));
            } else {
                comptime var i = 0;
                inline while (i < info.len) : (i += 1) {
                    hash(hasher, key[i], strat);
                }
            }
        },

        .@"struct" => |info| {
            inline for (info.field_names) |field_name| {
                // 复用前一个字段的哈希作为
                // 下一个字段的种子,使它们相互依赖。
                hash(hasher, @field(key, field_name), strat);
            }
        },

        .@"union" => |info| blk: {
            if (info.tag_type) |tag_type| {
                const tag = std.meta.activeTag(key);
                hash(hasher, tag, strat);
                inline for (info.field_names, info.field_types) |field_name, field_type| {
                    if (@field(tag_type, field_name) == tag) {
                        if (field_type != void) {
                            hash(hasher, @field(key, field_name), strat);
                        }
                        break :blk;
                    }
                }
                unreachable;
            } else @compileError("cannot hash untagged union type: " ++ @typeName(Key) ++ ", provide your own hash function");
        },

        .error_union => blk: {
            const payload = key catch |err| {
                hash(hasher, err, strat);
                break :blk;
            };
            hash(hasher, payload, strat);
        },
    }
}

inline fn typeContainsSlice(comptime K: type) bool {
    return switch (@typeInfo(K)) {
        .pointer => |info| info.size == .slice,

        inline .@"struct", .@"union" => |info| {
            inline for (info.field_types) |field_type| {
                if (typeContainsSlice(field_type)) {
                    return true;
                }
            }
            return false;
        },

        else => false,
    };
}

/// 为所有符合条件的类型提供泛型哈希。
/// 仅对 `key` 本身计算哈希,不跟随指针。
/// 拒绝切片,以及包含切片的联合体和结构体,
/// 避免对用户意图产生歧义。
pub fn autoHash(hasher: anytype, key: anytype) void {
    const Key = @TypeOf(key);
    if (comptime typeContainsSlice(Key)) {
        @compileError("std.hash.autoHash does not allow slices as well as unions and structs containing slices here (" ++ @typeName(Key) ++
            ") because the intent is unclear. Consider using std.hash.autoHashStrat or providing your own hash function instead.");
    }

    hash(hasher, key, .Shallow);
}

const testing = std.testing;
const Wyhash = std.hash.Wyhash;

fn testHash(key: anytype) u64 {
    // 此处可使用任意哈希,以测试 autoHash。
    var hasher = Wyhash.init(0);
    hash(&hasher, key, .Shallow);
    return hasher.final();
}

fn testHashShallow(key: anytype) u64 {
    // 此处可使用任意哈希,以测试 autoHash。
    var hasher = Wyhash.init(0);
    hash(&hasher, key, .Shallow);
    return hasher.final();
}

fn testHashDeep(key: anytype) u64 {
    // 此处可使用任意哈希,以测试 autoHash。
    var hasher = Wyhash.init(0);
    hash(&hasher, key, .Deep);
    return hasher.final();
}

fn testHashDeepRecursive(key: anytype) u64 {
    // 此处可使用任意哈希,以测试 autoHash。
    var hasher = Wyhash.init(0);
    hash(&hasher, key, .DeepRecursive);
    return hasher.final();
}

test "typeContainsSlice" {
    comptime {
        try testing.expect(!typeContainsSlice(std.meta.Tag(std.lang.Type)));

        try testing.expect(typeContainsSlice([]const u8));
        try testing.expect(!typeContainsSlice(u8));
        const A = struct { x: []const u8 };
        const B = struct { a: A };
        const C = struct { b: B };
        const D = struct { x: u8 };
        try testing.expect(typeContainsSlice(A));
        try testing.expect(typeContainsSlice(B));
        try testing.expect(typeContainsSlice(C));
        try testing.expect(!typeContainsSlice(D));
    }
}

test "hash pointer" {
    const array = [_]u32{ 123, 123, 123 };
    const a = &array[0];
    const b = &array[1];
    const c = &array[2];
    const d = a;

    try testing.expect(testHashShallow(a) == testHashShallow(d));
    try testing.expect(testHashShallow(a) != testHashShallow(c));
    try testing.expect(testHashShallow(a) != testHashShallow(b));

    try testing.expect(testHashDeep(a) == testHashDeep(a));
    try testing.expect(testHashDeep(a) == testHashDeep(c));
    try testing.expect(testHashDeep(a) == testHashDeep(b));

    try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(a));
    try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(c));
    try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(b));
}

test "hash slice shallow" {
    // 动态分配其中一个数组,确保优化过程
    // 不会将其与另一个数组合并。
    const array1 = try std.testing.allocator.create([6]u32);
    defer std.testing.allocator.destroy(array1);
    array1.* = [_]u32{ 1, 2, 3, 4, 5, 6 };
    const array2 = [_]u32{ 1, 2, 3, 4, 5, 6 };
    // TODO 审查深层/浅层行为——对数组指针和切片的处理可能不正确
    var runtime_zero: usize = 0;
    _ = &runtime_zero;
    const a = array1[runtime_zero..];
    const b = array2[runtime_zero..];
    const c = array1[runtime_zero..3];
    try testing.expect(testHashShallow(a) == testHashShallow(a));
    try testing.expect(testHashShallow(a) != testHashShallow(array1));
    try testing.expect(testHashShallow(a) != testHashShallow(b));
    try testing.expect(testHashShallow(a) != testHashShallow(c));
}

test "hash slice deep" {
    // 动态分配其中一个数组,确保优化过程
    // 不会将其与另一个数组合并。
    const array1 = try std.testing.allocator.create([6]u32);
    defer std.testing.allocator.destroy(array1);
    array1.* = [_]u32{ 1, 2, 3, 4, 5, 6 };
    const array2 = [_]u32{ 1, 2, 3, 4, 5, 6 };
    const a = array1[0..];
    const b = array2[0..];
    const c = array1[0..3];
    try testing.expect(testHashDeep(a) == testHashDeep(a));
    try testing.expect(testHashDeep(a) == testHashDeep(array1));
    try testing.expect(testHashDeep(a) == testHashDeep(b));
    try testing.expect(testHashDeep(a) != testHashDeep(c));
}

test "hash struct deep" {
    const Foo = struct {
        a: u32,
        b: u16,
        c: *bool,

        const Self = @This();

        pub fn init(allocator: mem.Allocator, a_: u32, b_: u16, c_: bool) !Self {
            const ptr = try allocator.create(bool);
            ptr.* = c_;
            return Self{ .a = a_, .b = b_, .c = ptr };
        }
    };

    const allocator = std.testing.allocator;
    const foo = try Foo.init(allocator, 123, 10, true);
    const bar = try Foo.init(allocator, 123, 10, true);
    const baz = try Foo.init(allocator, 123, 10, false);
    defer allocator.destroy(foo.c);
    defer allocator.destroy(bar.c);
    defer allocator.destroy(baz.c);

    try testing.expect(testHashDeep(foo) == testHashDeep(bar));
    try testing.expect(testHashDeep(foo) != testHashDeep(baz));
    try testing.expect(testHashDeep(bar) != testHashDeep(baz));

    var hasher = Wyhash.init(0);
    const h = testHashDeep(foo);
    autoHash(&hasher, foo.a);
    autoHash(&hasher, foo.b);
    autoHash(&hasher, foo.c.*);
    try testing.expectEqual(h, hasher.final());

    const h2 = testHashDeepRecursive(&foo);
    try testing.expect(h2 != testHashDeep(&foo));
    try testing.expect(h2 == testHashDeep(foo));
}

test "testHash optional" {
    const a: ?u32 = 123;
    const b: ?u32 = null;
    try testing.expectEqual(testHash(a), testHash(@as(u32, 123)));
    try testing.expect(testHash(a) != testHash(b));
    try testing.expectEqual(testHash(b), 0x409638ee2bde459); // wyhash 空输入的哈希
}

test "testHash array" {
    const a = [_]u32{ 1, 2, 3 };
    const h = testHash(a);
    var hasher = Wyhash.init(0);
    autoHash(&hasher, @as(u32, 1));
    autoHash(&hasher, @as(u32, 2));
    autoHash(&hasher, @as(u32, 3));
    try testing.expectEqual(h, hasher.final());
}

test "testHash multi-dimensional array" {
    const a = [_][]const u32{ &.{ 1, 2, 3 }, &.{ 4, 5 } };
    const b = [_][]const u32{ &.{ 1, 2 }, &.{ 3, 4, 5 } };
    try testing.expect(testHash(a) != testHash(b));
}

test "testHash struct" {
    const Foo = struct {
        a: u32 = 1,
        b: u32 = 2,
        c: u32 = 3,
    };
    const f = Foo{};
    const h = testHash(f);
    var hasher = Wyhash.init(0);
    autoHash(&hasher, @as(u32, 1));
    autoHash(&hasher, @as(u32, 2));
    autoHash(&hasher, @as(u32, 3));
    try testing.expectEqual(h, hasher.final());
}

test "testHash union" {
    const Foo = union(enum) {
        A: u32,
        B: bool,
        C: u32,
        D: void,
    };

    const a = Foo{ .A = 18 };
    var b = Foo{ .B = true };
    const c = Foo{ .C = 18 };
    const d: Foo = .D;
    try testing.expect(testHash(a) == testHash(a));
    try testing.expect(testHash(a) != testHash(b));
    try testing.expect(testHash(a) != testHash(c));
    try testing.expect(testHash(a) != testHash(d));

    b = Foo{ .A = 18 };
    try testing.expect(testHash(a) == testHash(b));

    b = .D;
    try testing.expect(testHash(d) == testHash(b));
}

test "testHash vector" {
    const a: @Vector(4, u32) = [_]u32{ 1, 2, 3, 4 };
    const b: @Vector(4, u32) = [_]u32{ 1, 2, 3, 5 };
    try testing.expect(testHash(a) == testHash(a));
    try testing.expect(testHash(a) != testHash(b));

    const c: @Vector(4, u31) = [_]u31{ 1, 2, 3, 4 };
    const d: @Vector(4, u31) = [_]u31{ 1, 2, 3, 5 };
    try testing.expect(testHash(c) == testHash(c));
    try testing.expect(testHash(c) != testHash(d));
}

test "testHash error union" {
    const Errors = error{Test};
    const Foo = struct {
        a: u32 = 1,
        b: u32 = 2,
        c: u32 = 3,
    };
    const f = Foo{};
    const g: Errors!Foo = Errors.Test;
    try testing.expect(testHash(f) != testHash(g));
    try testing.expect(testHash(f) == testHash(Foo{}));
    try testing.expect(testHash(g) == testHash(Errors.Test));
}