1/**
2 * Computes Effect hash values and defines the interface for objects that want
3 * to provide their own hash implementation. Hashes are small numeric
4 * fingerprints used by Effect data structures to bucket values quickly; they
5 * are not cryptographic digests and they are not proof that two values are
6 * equal. The module also includes helpers for primitive, structure, array, and
7 * reference-based hashes, plus functions for combining and optimizing numeric
8 * hash values.
9 *
10 * @since 2.0.0
11 */
12import { dual } from "./Function.ts"
13import { byReferenceInstances, getAllObjectKeys, viewBytes } from "./internal/equal.ts"
14import { addBackEdge, backEdges } from "./internal/hash.ts"
15import { hasProperty } from "./Predicate.ts"
16
17/**
18 * Defines the unique identifier used to identify objects that implement the Hash interface.
19 *
20 * **When to use**
21 *
22 * Use as the computed property key for the method that supplies a custom hash
23 * value on a `Hash` implementor.
24 *
25 * @see {@link Hash} for the interface implemented with this symbol
26 * @see {@link isHash} for checking whether a value implements `Hash`
27 * @see {@link hash} for computing hash values
28 *
29 * @category symbols
30 * @since 2.0.0
31 */
32export const symbol = "~effect/Hash"
33
34/**
35 * A type that represents an object that can be hashed.
36 *
37 * **When to use**
38 *
39 * Use to let a custom type provide its own stable hash value.
40 *
41 * **Details**
42 *
43 * Objects implementing this interface provide a method to compute their hash value,
44 * which is used for efficient comparison and storage operations.
45 *
46 * **Example** (Implementing Hash)
47 *
48 * ```ts import.meta.vitest
49 * import { Hash } from "effect"
50 *
51 * class MyClass implements Hash.Hash {
52 * constructor(private value: number) {}
53 *
54 * [Hash.symbol](): number {
55 * return Hash.hash(this.value)
56 * }
57 * }
58 *
59 * new MyClass(42)[Hash.symbol]() // => 42
60 * ```
61 *
62 * @category models
63 * @since 2.0.0
64 */
65export interface Hash {
66 [symbol](): number
67}
68
69/**
70 * Computes a hash value for any given value.
71 *
72 * **When to use**
73 *
74 * Use to compute an Effect hash for primitives, collections, and hashable
75 * objects.
76 *
77 * **Details**
78 *
79 * This function can hash primitives (numbers, strings, booleans, etc.) as well as
80 * objects, arrays, and other complex data structures. It automatically handles
81 * different types and provides a consistent hash value for equivalent inputs.
82 *
83 * **Gotchas**
84 *
85 * Objects being hashed must be treated as immutable after their first hash
86 * computation. Hash results are cached, so mutating an object after hashing will
87 * lead to stale cached values and broken hash-based operations. For mutable
88 * objects, implement a custom `Hash` interface that hashes the object reference
89 * rather than its content.
90 *
91 * **Example** (Hashing different values)
92 *
93 * ```ts import.meta.vitest
94 * import { Hash } from "effect"
95 *
96 * Hash.hash(42) === Hash.hash(42) // => true
97 * Hash.hash("hello") === Hash.hash("hello") // => true
98 * Hash.hash([1, 2, 3]) === Hash.hash([1, 2, 3]) // => true
99 * ```
100 *
101 * @category hashing
102 * @since 2.0.0
103 */
104export const hash: <A>(self: A) => number = <A>(self: A) => {
105 switch (typeof self) {
106 case "number":
107 return number(self)
108 case "bigint":
109 return string(self.toString(10))
110 case "string":
111 return string(self)
112 case "function":
113 case "object": {
114 if (self === null) {
115 break
116 } else if (self instanceof Date) {
117 if (Number.isNaN(self.getTime())) {
118 return string("Invalid Date")
119 }
120 return string(self.toISOString())
121 } else if (self instanceof RegExp) {
122 return string(self.toString())
123 } else {
124 if (byReferenceInstances.has(self)) {
125 return random(self)
126 }
127 const cached = hashCache.get(self)
128 if (cached !== undefined) {
129 return cached
130 }
131 if (visitedObjects.has(self)) {
132 addBackEdge()
133 return string("[Circular]")
134 }
135 visitedObjects.add(self)
136 const seen = backEdges
137 let h: number
138 try {
139 if (symbol in self) {
140 h = (self as Hash)[symbol]()
141 } else if (typeof self === "function") {
142 h = random(self)
143 } else if (self instanceof DataView) {
144 h = array(viewBytes(self))
145 } else if (Array.isArray(self) || ArrayBuffer.isView(self)) {
146 h = array(self as any)
147 } else if (self instanceof Map) {
148 h = hashMap(self)
149 } else if (self instanceof Set) {
150 h = hashSet(self)
151 } else {
152 h = structure(self)
153 }
154 } finally {
155 visitedObjects.delete(self)
156 }
157 // Hashes containing a back-edge depend on the entry point.
158 if (seen === backEdges) {
159 hashCache.set(self, h)
160 }
161 return h
162 }
163 }
164 }
165 return optimize(mix(string(String(self))))
166}
167
168/**
169 * Generates a random hash value for an object and caches it.
170 *
171 * **When to use**
172 *
173 * Use to hash an object by reference identity instead of structural content.
174 *
175 * **Details**
176 *
177 * This function creates a random hash value for objects that don't have their own
178 * hash implementation. The hash value is cached using a WeakMap, so the same object
179 * will always return the same hash value during its lifetime.
180 *
181 * **Example** (Hashing objects by reference)
182 *
183 * ```ts import.meta.vitest
184 * import { Hash } from "effect"
185 *
186 * const obj1 = { a: 1 }
187 * const obj2 = { a: 1 }
188 *
189 * Hash.random(obj1) === Hash.random(obj1) // => true
190 *
191 * typeof Hash.random(obj2) // => "number"
192 * ```
193 *
194 * @category hashing
195 * @since 2.0.0
196 */
197export const random: <A extends object>(self: A) => number = (self) => {
198 if (!randomHashCache.has(self)) {
199 randomHashCache.set(self, optimize((Math.random() * 0x100000000) | 0))
200 }
201 return randomHashCache.get(self)!
202}
203
204// 32-bit MurmurHash3 finalizer.
205const mix = (h: number): number => {
206 h ^= h >>> 16
207 h = Math.imul(h, 0x85ebca6b)
208 h ^= h >>> 13
209 h = Math.imul(h, 0xc2b2ae35)
210 return h ^ (h >>> 16)
211}
212
213/**
214 * Combines two hash values into a single hash value.
215 *
216 * **When to use**
217 *
218 * Use to build a hash for a composite value by folding together hash values for
219 * its parts.
220 *
221 * **Details**
222 *
223 * Supports direct and pipeable usage. Argument order affects the result.
224 *
225 * **Example** (Combining hash values)
226 *
227 * ```ts import.meta.vitest
228 * import { Hash, pipe } from "effect"
229 *
230 * const hash1 = Hash.hash("hello")
231 * const hash2 = Hash.hash("world")
232 *
233 * const combined = Hash.combine(hash2)(hash1)
234 * combined === pipe(hash1, Hash.combine(hash2)) // => true
235 * ```
236 *
237 * @see {@link hash} for computing hash values from arbitrary inputs
238 * @see {@link structureKeys} for hashing selected object fields without manual combination
239 *
240 * @category hashing
241 * @since 2.0.0
242 */
243export const combine: {
244 (b: number): (self: number) => number
245 (self: number, b: number): number
246} = dual(2, (self: number, b: number): number => mix(Math.imul(self, 0x9e3779b1) + Math.imul(b, 0x85ebca6b)))
247
248/**
249 * Applies bit manipulation techniques to optimize a hash value.
250 *
251 * **When to use**
252 *
253 * Use to improve the bit distribution of a raw numeric hash value.
254 *
255 * **Details**
256 *
257 * This function takes a hash value and applies bitwise operations to improve
258 * the distribution of hash values, reducing the likelihood of collisions.
259 *
260 * **Example** (Optimizing a hash value)
261 *
262 * ```ts import.meta.vitest
263 * import { Hash } from "effect"
264 *
265 * Hash.optimize(1234567890) // => 160826066
266 * ```
267 *
268 * @category hashing
269 * @since 2.0.0
270 */
271export const optimize = (n: number): number => (n & 0xbfffffff) | ((n >>> 1) & 0x40000000)
272
273/**
274 * Checks whether a value implements the Hash interface.
275 *
276 * **When to use**
277 *
278 * Use to detect whether an unknown value provides a custom hash implementation.
279 *
280 * **Details**
281 *
282 * This function determines whether a given value has the Hash symbol property,
283 * indicating that it can provide its own hash value implementation.
284 *
285 * **Example** (Checking for Hash support)
286 *
287 * ```ts import.meta.vitest
288 * import { Hash } from "effect"
289 *
290 * class MyHashable implements Hash.Hash {
291 * [Hash.symbol]() {
292 * return 42
293 * }
294 * }
295 *
296 * Hash.isHash(new MyHashable()) // => true
297 * Hash.isHash({}) // => false
298 * Hash.isHash("string") // => false
299 * ```
300 *
301 * @category guards
302 * @since 2.0.0
303 */
304export const isHash = (u: unknown): u is Hash => hasProperty(u, symbol)
305
306const float64 = new DataView(new ArrayBuffer(8))
307
308/**
309 * Computes a hash value for a number.
310 *
311 * **When to use**
312 *
313 * Use to hash a JavaScript number with Effect's numeric hash semantics.
314 *
315 * **Details**
316 *
317 * Int32 values hash to themselves. Other numbers hash from their IEEE-754 bits,
318 * with a canonical representation for `NaN`.
319 *
320 * **Example** (Hashing numbers)
321 *
322 * ```ts import.meta.vitest
323 * import { Hash } from "effect"
324 *
325 * Number.isInteger(Hash.number(42)) // => true
326 * Number.isInteger(Hash.number(3.14)) // => true
327 * Hash.number(NaN) === Hash.number(NaN) // => true
328 * Hash.number(Infinity) === Hash.number(Infinity) // => true
329 * Hash.number(100) === Hash.number(100) // => true
330 * ```
331 *
332 * @category hashing
333 * @since 2.0.0
334 */
335export const number = (n: number) => {
336 const h = n | 0
337 if (h === n) {
338 return optimize(h)
339 }
340 float64.setFloat64(0, n !== n ? NaN : n)
341 return optimize(combine(float64.getInt32(0), float64.getInt32(4)))
342}
343
344/**
345 * Computes a hash value for a string using the djb2 algorithm.
346 *
347 * **When to use**
348 *
349 * Use when you need a string field to contribute to a custom structural hash
350 * implementation.
351 *
352 * **Details**
353 *
354 * This function implements a variation of the djb2 hash algorithm, which is
355 * known for its good distribution properties and speed. It processes each
356 * character of the string to produce a consistent hash value.
357 *
358 * **Example** (Hashing strings)
359 *
360 * ```ts import.meta.vitest
361 * import { Hash } from "effect"
362 *
363 * Hash.string("hello") // => 181380007
364 * Hash.string("world") // => 164394279
365 * Hash.string("") // => 5381
366 * Hash.string("test") === Hash.string("test") // => true
367 * ```
368 *
369 * @category hashing
370 * @since 2.0.0
371 */
372export const string = (str: string) => {
373 let h = 5381, i = str.length
374 while (i) {
375 h = (h * 33) ^ str.charCodeAt(--i)
376 }
377 return optimize(h)
378}
379
380/**
381 * Computes a hash value for an object using only the specified keys.
382 *
383 * **When to use**
384 *
385 * Use to hash an object by a selected set of property keys.
386 *
387 * **Details**
388 *
389 * This function allows you to hash an object by considering only specific keys,
390 * which is useful when you want to create a hash based on a subset of an object's
391 * properties.
392 *
393 * **Example** (Hashing selected object keys)
394 *
395 * ```ts import.meta.vitest
396 * import { Hash } from "effect"
397 *
398 * const person = { name: "John", age: 30, city: "New York" }
399 *
400 * const hash1 = Hash.structureKeys(person, ["name", "age"])
401 * const hash2 = Hash.structureKeys(person, ["name", "city"])
402 *
403 * hash1 // => -731887653
404 * hash2 // => 148523102
405 *
406 * const person2 = { name: "John", age: 30, city: "Boston" }
407 * const hash3 = Hash.structureKeys(person2, ["name", "age"])
408 * hash1 === hash3 // => true
409 * ```
410 *
411 * @category hashing
412 * @since 2.0.0
413 */
414export const structureKeys = (o: object, keys: Iterable<PropertyKey>) => {
415 let h = 12289
416 for (const key of keys) {
417 h ^= combine(hash(key), hash((o as any)[key]))
418 }
419 return optimize(h)
420}
421
422/**
423 * Computes a structural hash for an object using Effect's object key collection.
424 *
425 * **When to use**
426 *
427 * Use to hash an object from all structural keys collected by Effect.
428 *
429 * **Details**
430 *
431 * The hash is based on the object's structural keys and their values, including
432 * symbol keys and relevant prototype keys for non-plain objects.
433 *
434 * **Example** (Hashing object structures)
435 *
436 * ```ts import.meta.vitest
437 * import { Hash } from "effect"
438 *
439 * const obj1 = { name: "John", age: 30 }
440 * const obj2 = { name: "Jane", age: 25 }
441 * const obj3 = { name: "John", age: 30 }
442 *
443 * Hash.structure(obj1) // => -731887653
444 * Hash.structure(obj2) // => -222100417
445 * Hash.structure(obj3) // => -731887653
446 * Hash.structure(obj1) === Hash.structure(obj3) // => true
447 * ```
448 *
449 * @category hashing
450 * @since 2.0.0
451 */
452export const structure = <A extends object>(o: A) => structureKeys(o, getAllObjectKeys(o))
453
454const unordered = (seed: number, f: (el: any) => number) => (iter: Iterable<any>) => {
455 let h = seed
456 for (const element of iter) {
457 h ^= f(element)
458 }
459 return optimize(h)
460}
461
462/**
463 * Computes a hash value for an iterable by hashing all of its elements.
464 *
465 * **When to use**
466 *
467 * Use to hash the values yielded by an iterable with Effect hash semantics.
468 *
469 * **Details**
470 *
471 * Folds element hashes with {@link combine}, so order and length affect the
472 * result.
473 *
474 * **Gotchas**
475 *
476 * A hash is not an equality proof. Distinct inputs can still share a hash.
477 *
478 * **Example** (Hashing arrays)
479 *
480 * ```ts import.meta.vitest
481 * import { Hash } from "effect"
482 *
483 * const arr1 = [1, 2, 3]
484 * const arr2 = [1, 2, 3]
485 * const arr3 = [3, 2, 1]
486 *
487 * Hash.array(arr1) === Hash.array(arr2) // => true
488 * Hash.array(arr1) === Hash.array(arr3) // => false
489 * ```
490 *
491 * @see {@link hash} for the general-purpose hash dispatcher
492 *
493 * @category hashing
494 * @since 2.0.0
495 */
496export const array = <A>(arr: Iterable<A>): number => {
497 let h = 6151
498 for (const element of arr) {
499 h = combine(h, hash(element))
500 }
501 return optimize(h)
502}
503
504const hashMap: <K, V>(map: Iterable<readonly [K, V]>) => number = unordered(
505 string("Map"),
506 ([k, v]) => combine(hash(k), hash(v))
507)
508const setSeed = string("Set")
509const hashSet: <A>(set: Iterable<A>) => number = unordered(setSeed, (element) => combine(setSeed, hash(element)))
510
511const randomHashCache = new WeakMap<any, number>()
512const hashCache = new WeakMap<object, number>()
513const visitedObjects = new WeakSet<object>()