1import { assert, describe, it } from "@effect/vitest"
2import { Chunk, Equal, Graph, Hash, HashMap, HashSet, Trie } from "effect"
3
4const range = (length: number): ReadonlyArray<number> => Array.from({ length }, (_, index) => index)
5
6const grid = <A>(size: number, make: (i: number, j: number) => A): ReadonlyArray<A> => {
7 const values = new Array<A>(size * size)
8 let index = 0
9 for (let i = 0; i < size; i++) {
10 for (let j = 0; j < size; j++) {
11 values[index++] = make(i, j)
12 }
13 }
14 return values
15}
16
17const unorderedPairs = <A>(size: number, make: (i: number, j: number) => A): ReadonlyArray<A> => {
18 const values = new Array<A>((size * (size - 1)) / 2)
19 let index = 0
20 for (let i = 0; i < size; i++) {
21 for (let j = i + 1; j < size; j++) {
22 values[index++] = make(i, j)
23 }
24 }
25 return values
26}
27
28const permutations = <A>(values: ReadonlyArray<A>): ReadonlyArray<ReadonlyArray<A>> => {
29 const output: Array<ReadonlyArray<A>> = []
30 const visit = (prefix: ReadonlyArray<A>, remaining: ReadonlyArray<A>): void => {
31 if (remaining.length === 0) {
32 output.push(prefix)
33 return
34 }
35 for (let i = 0; i < remaining.length; i++) {
36 visit([...prefix, remaining[i]], [...remaining.slice(0, i), ...remaining.slice(i + 1)])
37 }
38 }
39 visit([], values)
40 return output
41}
42
43const assertNoHashCollisions = (values: Iterable<unknown>): void => {
44 const hashes = new Set<number>()
45 let count = 0
46 for (const value of values) {
47 hashes.add(Hash.hash(value))
48 count++
49 }
50 assert.strictEqual(hashes.size, count)
51}
52
53const twoNodeGraph = (type: Graph.Kind, first: number, second: number) =>
54 Graph.make(type)<number, number>((mutable) => {
55 Graph.addNode(mutable, first)
56 Graph.addNode(mutable, second)
57 Graph.addEdge(mutable, 0, 1, 0)
58 })
59
60describe("Hash", () => {
61 describe("collision resistance", () => {
62 it("does not collide for a 100 by 100 grid of arrays", () => {
63 assertNoHashCollisions(grid(100, (i, j) => [i, j]))
64 })
65
66 it("does not collide for a 100 by 100 grid of records", () => {
67 assertNoHashCollisions(grid(100, (i, j) => ({ i, j })))
68 })
69
70 it("does not collide for a 100 by 100 grid of combined hashes", () => {
71 assertNoHashCollisions(grid(100, (i, j) => Hash.combine(Hash.hash(i), Hash.hash(j))))
72 })
73
74 it("does not collide for a 100 by 100 grid of HashMap entries", () => {
75 assertNoHashCollisions(grid(100, (i, j) => HashMap.make([i, j])))
76 })
77
78 it("does not collide for a 100 by 100 grid of Trie entries", () => {
79 assertNoHashCollisions(grid(100, (i, j) => Trie.make([String(i), j])))
80 })
81
82 it("does not collide for a 100 by 100 grid of Chunks", () => {
83 assertNoHashCollisions(grid(100, (i, j) => Chunk.make(i, j)))
84 })
85
86 it("does not collide for native Sets of pairs below 150", () => {
87 assertNoHashCollisions(unorderedPairs(150, (i, j) => new Set([i, j])))
88 })
89
90 it("does not collide for HashSets of pairs below 150", () => {
91 assertNoHashCollisions(unorderedPairs(150, (i, j) => HashSet.make(i, j)))
92 })
93
94 it("does not give distinct HashSets one constant hash", () => {
95 assert.notStrictEqual(Hash.hash(HashSet.make(1)), Hash.hash(HashSet.make(2)))
96 })
97
98 it("does not collide for every permutation of seven integers", () => {
99 assertNoHashCollisions(permutations(range(7)))
100 })
101
102 it("does not collide for nested arrays and records", () => {
103 const values = []
104 for (let i = 0; i < 10; i++) {
105 for (let j = 0; j < 10; j++) {
106 for (let k = 0; k < 10; k++) {
107 values.push({ a: [i, j], b: { c: k } })
108 }
109 }
110 }
111 assertNoHashCollisions(values)
112 })
113
114 it("does not collide for a 100 by 100 grid of directed two-node graphs", () => {
115 assertNoHashCollisions(grid(100, (i, j) => twoNodeGraph("directed", i, j)))
116 })
117
118 it("does not collide for a 100 by 100 grid of undirected two-node graphs", () => {
119 assertNoHashCollisions(grid(100, (i, j) => twoNodeGraph("undirected", i, j)))
120 })
121
122 it("keeps array order and length in the hash", () => {
123 assert.notStrictEqual(Hash.hash([1, 2]), Hash.hash([2, 1]))
124 assert.notStrictEqual(Hash.hash([1, 2, 3]), Hash.hash([]))
125 })
126
127 it("does not hash null, undefined, booleans and symbols like their names", () => {
128 for (const value of [null, undefined, true, false, Symbol.for("a")]) {
129 assert.notStrictEqual(Hash.hash(value), Hash.hash(String(value)))
130 }
131 })
132
133 it("does not collide for 10k multiples of 0.1", () => {
134 assertNoHashCollisions(range(10_000).map((i) => i * 0.1))
135 })
136
137 it("does not collide for 10k multiples of 0.001", () => {
138 assertNoHashCollisions(range(10_000).map((i) => i * 0.001))
139 })
140 })
141
142 describe("floats", () => {
143 it("hashes 0 and -0 the same", () => {
144 assert.strictEqual(Hash.hash(0), Hash.hash(-0))
145 })
146
147 it("hashes every NaN the same", () => {
148 const bytes = new Uint32Array(2)
149 const view = new Float64Array(bytes.buffer)
150 bytes[0] = 1
151 bytes[1] = 0x7ff80000
152 const quietPayload = view[0]
153 bytes[0] = 0
154 bytes[1] = 0xfff00001
155 const signalingNegative = view[0]
156 assert.isNaN(quietPayload)
157 assert.isNaN(signalingNegative)
158 assert.strictEqual(Hash.hash(NaN), Hash.hash(0 / 0))
159 assert.strictEqual(Hash.hash(NaN), Hash.hash(quietPayload))
160 assert.strictEqual(Hash.hash(NaN), Hash.hash(signalingNegative))
161 assert.notStrictEqual(Hash.hash(Infinity), Hash.hash(-Infinity))
162 })
163 })
164
165 describe("hash law", () => {
166 let seed = 1
167 const random = (n: number): number => {
168 seed = (Math.imul(seed, 1103515245) + 12345) >>> 0
169 return (seed >>> 16) % n
170 }
171 const randomKey = (): unknown => [random(60), `k${random(60)}`, [random(4), random(4)]][random(3)]
172 const shuffle = <A>(values: ReadonlyArray<A>): Array<A> => {
173 const output = [...values]
174 for (let i = output.length - 1; i > 0; i--) {
175 const j = random(i + 1)
176 ;[output[i], output[j]] = [output[j], output[i]]
177 }
178 return output
179 }
180
181 it("hashes HashMaps and HashSets independently of insertion order", () => {
182 for (let run = 0; run < 200; run++) {
183 const keys = Array.from(new Set(range(1 + random(80)).map(() => random(1000))))
184 const entries = keys.map((key) => [key, random(3)] as const)
185 const reordered = shuffle(entries)
186 assert.strictEqual(Hash.hash(HashMap.fromIterable(entries)), Hash.hash(HashMap.fromIterable(reordered)))
187 assert.strictEqual(Hash.hash(HashSet.fromIterable(keys)), Hash.hash(HashSet.fromIterable(shuffle(keys))))
188 }
189 })
190
191 it("hashes a HashMap like a fresh build after persistent and in-place edits", () => {
192 for (let run = 0; run < 100; run++) {
193 let map = HashMap.empty<unknown, number>()
194 for (let step = 0; step < 40; step++) {
195 const operation = random(3)
196 if (operation === 0) {
197 map = HashMap.mutate(map, (mutable) => {
198 for (let i = random(20); i >= 0; i--) {
199 if (random(3) === 0) HashMap.remove(mutable, randomKey())
200 else HashMap.set(mutable, randomKey(), random(3))
201 if (random(4) === 0) mutable[Hash.symbol]()
202 }
203 })
204 } else if (operation === 1) {
205 map = HashMap.remove(map, randomKey())
206 } else {
207 map = HashMap.set(map, randomKey(), random(3))
208 }
209 const rebuilt = HashMap.fromIterable(shuffle(Array.from(map)))
210 assert.isTrue(Equal.equals(map, rebuilt))
211 assert.strictEqual(Hash.hash(map), Hash.hash(rebuilt))
212 }
213 }
214 })
215
216 it("invalidates CollisionNode hashes after in-place edits", () => {
217 const key = (id: number) => ({
218 id,
219 [Hash.symbol](): number {
220 return 0
221 }
222 })
223 const first = key(1)
224 const second = key(2)
225 const third = key(3)
226
227 HashMap.mutate(HashMap.empty<typeof first, number>(), (mutable) => {
228 HashMap.set(mutable, first, 1)
229 HashMap.set(mutable, second, 2)
230 mutable[Hash.symbol]()
231
232 HashMap.set(mutable, third, 3)
233 assert.strictEqual(mutable[Hash.symbol](), Hash.hash(HashMap.fromIterable(mutable)))
234
235 mutable[Hash.symbol]()
236 HashMap.set(mutable, second, 20)
237 assert.strictEqual(mutable[Hash.symbol](), Hash.hash(HashMap.fromIterable(mutable)))
238
239 mutable[Hash.symbol]()
240 HashMap.remove(mutable, first)
241 assert.strictEqual(mutable[Hash.symbol](), Hash.hash(HashMap.fromIterable(mutable)))
242 })
243 })
244 })
245
246 describe("cyclic values", () => {
247 it("does not cache a hash computed from a circular sentinel", () => {
248 interface Node {
249 next?: Node
250 }
251 const a1: Node = {}
252 const b1: Node = {}
253 a1.next = b1
254 b1.next = a1
255
256 const a2: Node = {}
257 const b2: Node = {}
258 a2.next = b2
259 b2.next = a2
260
261 Hash.hash(b2)
262 assert.strictEqual(Hash.hash(a1), Hash.hash(a2))
263 })
264
265 it("does not cache a HashMap subtree hash computed from a circular sentinel", () => {
266 const make = () => {
267 const holder: { map?: unknown; tag: number } = { tag: 1 }
268 const map = HashMap.make(["inner", { holder }])
269 holder.map = map
270 return { holder, map }
271 }
272 const first = make()
273 const second = make()
274 Hash.hash(first.map)
275 assert.strictEqual(Hash.hash(first.holder), Hash.hash(second.holder))
276 })
277
278 it("clears visited state when a custom hasher throws", () => {
279 const value = {
280 [Hash.symbol](): number {
281 throw new Error("boom")
282 }
283 }
284
285 assert.throws(() => Hash.hash(value), /boom/)
286 assert.throws(() => Hash.hash(value), /boom/)
287 })
288 })
289})