lib/preserves/src/containers.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! A hash map and a hash set keyed by the package's values. A lookup has to find a key whenever the
2 //! key it is given is an equal value, including a set or dictionary that stores its items in
3 //! another order. Two equal sets can store their items in different orders, and so can two equal
4 //! dictionaries. A hash over the stored order would put such equal keys in different buckets.
5 //!
6 //! `ValueContext` gives the standard hash map the value's own hash and equality, which ignore the
7 //! order in which a set or dictionary stores its items. `ValueHashMap` and `ValueSet` are the
8 //! standard unmanaged hash map with that context, so every call that allocates takes the allocator
9 //! as an argument. The map stores each key and value as given and frees only its own table, so the
10 //! caller keeps every value's memory alive while it sits in the map.
11 const std = @import("std");
12 const value_mod = @import("value.zig");
13
14 /// Returns the hashing context for `Value(D)` that the standard hash map expects. `ValueHashMap`
15 /// and `ValueSet` pass it to Zig's standard hash map, so the map finds keys by value equality. The
16 /// context holds no state, so every instance behaves the same.
17 pub fn ValueContext(comptime D: type) type {
18 return struct {
19 /// Returns the hash of `v`, the same number `v.hash()` returns. Equal values get equal
20 /// hashes, whatever order a set or dictionary stores its items in.
21 pub fn hash(_: @This(), v: value_mod.Value(D)) u64 {
22 return v.hash();
23 }
24
25 /// Returns true when `a` and `b` are equal values, the same answer `a.eql(b)` gives.
26 pub fn eql(_: @This(), a: value_mod.Value(D), b: value_mod.Value(D)) bool {
27 return a.eql(b);
28 }
29 };
30 }
31
32 /// Returns the standard unmanaged hash map type from `Value(D)` keys to `Value(D)` values, keyed
33 /// through `ValueContext(D)`. Code that maps one Preserves value to another declares one, for
34 /// lookups by value equality. The map grows once it is 80 percent full. A lookup with a set key
35 /// finds an entry stored under an equal set in another order, and the same holds for dictionaries.
36 /// The map copies no value memory, and `deinit` frees only the map's table.
37 pub fn ValueHashMap(comptime D: type) type {
38 return std.HashMapUnmanaged(value_mod.Value(D), value_mod.Value(D), ValueContext(D), 80);
39 }
40
41 /// Returns the standard unmanaged hash map type with `Value(D)` keys and `void` values, keyed
42 /// through `ValueContext(D)`. Code that tracks which values it has seen declares one of these. The
43 /// set grows once it is 80 percent full. Adding an equal value a second time leaves the count
44 /// unchanged. The set copies no value memory, and `deinit` frees only its table.
45 pub fn ValueSet(comptime D: type) type {
46 return std.HashMapUnmanaged(value_mod.Value(D), void, ValueContext(D), 80);
47 }
48
49 /// Returns true when `a` and `b` are equal values, the same answer `a.eql(b)` gives. Generic code
50 /// that passes equality as a function value calls it, for the method's answer in function form. The
51 /// package root's `valueEqual` is a separate function with the same answer for values whose
52 /// embedded values hold any pointer.
53 pub fn valueEqual(comptime D: type, a: value_mod.Value(D), b: value_mod.Value(D)) bool {
54 return a.eql(b);
55 }
56
57 test "ValueHashMap stores and looks up by value" {
58 const NoEmbedded = @import("domain.zig").NoEmbedded;
59 const V = value_mod.Value(NoEmbedded);
60 const Map = ValueHashMap(NoEmbedded);
61
62 const allocator = std.testing.allocator;
63 var map: Map = .{};
64 defer map.deinit(allocator);
65
66 const k1 = V.initI128(1);
67 const k2 = V.initI128(2);
68 const v1 = V.initBoolean(true);
69 const v2 = V.initBoolean(false);
70
71 try map.put(allocator, k1, v1);
72 try map.put(allocator, k2, v2);
73 try std.testing.expectEqual(@as(usize, 2), map.count());
74
75 const got1 = map.get(V.initI128(1)).?;
76 try std.testing.expect(got1.eql(v1));
77 const got2 = map.get(V.initI128(2)).?;
78 try std.testing.expect(got2.eql(v2));
79 try std.testing.expect(map.get(V.initI128(99)) == null);
80 }
81
82 test "ValueHashMap finds permutation-equivalent unordered keys" {
83 const NoEmbedded = @import("domain.zig").NoEmbedded;
84 const V = value_mod.Value(NoEmbedded);
85 const Map = ValueHashMap(NoEmbedded);
86
87 const allocator = std.testing.allocator;
88 var map: Map = .{};
89 defer map.deinit(allocator);
90
91 var set_items_a = [_]V{ V.initI128(1), V.initI128(2) };
92 var set_items_b = [_]V{ V.initI128(2), V.initI128(1) };
93 const set_a = V.initSet(&set_items_a);
94 const set_b = V.initSet(&set_items_b);
95 try std.testing.expect(set_a.eql(set_b));
96 try std.testing.expectEqual(std.math.Order.eq, set_a.compare(set_b));
97 try std.testing.expectEqual(set_a.hash(), set_b.hash());
98 try map.put(allocator, set_a, V.initBoolean(true));
99 try std.testing.expect(map.get(set_b) != null);
100
101 var entries_a = [_]V.DictionaryEntry{
102 .{ .key = V.initI128(1), .value = V.initBoolean(true) },
103 .{ .key = V.initI128(2), .value = V.initBoolean(false) },
104 };
105 var entries_b = [_]V.DictionaryEntry{
106 .{ .key = V.initI128(2), .value = V.initBoolean(false) },
107 .{ .key = V.initI128(1), .value = V.initBoolean(true) },
108 };
109 const dictionary_a = V.initDictionary(&entries_a);
110 const dictionary_b = V.initDictionary(&entries_b);
111 try std.testing.expect(dictionary_a.eql(dictionary_b));
112 try std.testing.expectEqual(std.math.Order.eq, dictionary_a.compare(dictionary_b));
113 try std.testing.expectEqual(dictionary_a.hash(), dictionary_b.hash());
114 try map.put(allocator, dictionary_a, V.initBoolean(false));
115 try std.testing.expect(map.get(dictionary_b) != null);
116 }
117
118 test "ValueSet tracks presence" {
119 const NoEmbedded = @import("domain.zig").NoEmbedded;
120 const V = value_mod.Value(NoEmbedded);
121 const Set = ValueSet(NoEmbedded);
122
123 const allocator = std.testing.allocator;
124 var set: Set = .{};
125 defer set.deinit(allocator);
126
127 try set.put(allocator, V.initI128(1), {});
128 try set.put(allocator, V.initI128(2), {});
129 try set.put(allocator, V.initI128(1), {});
130 try std.testing.expectEqual(@as(usize, 2), set.count());
131 try std.testing.expect(set.contains(V.initI128(1)));
132 try std.testing.expect(!set.contains(V.initI128(7)));
133 }
134
135 test "valueEqual freestanding wrapper matches method form" {
136 const NoEmbedded = @import("domain.zig").NoEmbedded;
137 const V = value_mod.Value(NoEmbedded);
138 try std.testing.expect(valueEqual(NoEmbedded, V.initI128(1), V.initI128(1)));
139 try std.testing.expect(!valueEqual(NoEmbedded, V.initI128(1), V.initI128(2)));
140 }