1/**
2 * Compares values with Effect's structural equality rules.
3 *
4 * `equals` compares primitives, arrays, plain objects, maps, sets, dates,
5 * regular expressions, and values that implement the `Equal` interface. This
6 * module also defines the equality symbol, guards, adapters, map and set
7 * comparison builders, and helpers for marking objects that should compare only
8 * by reference.
9 *
10 * @since 2.0.0
11 */
12import type { Equivalence } from "./Equivalence.ts"
13import * as Hash from "./Hash.ts"
14import { byReferenceInstances, getAllObjectKeys, viewBytes } from "./internal/equal.ts"
15import { hasProperty } from "./Predicate.ts"
16
17/**
18 * Defines the unique string identifier for the `Equal` interface.
19 *
20 * **When to use**
21 *
22 * Use when you implement custom equality and need the computed property key for
23 * the equality method.
24 *
25 * **Details**
26 *
27 * This is a pure constant with no allocation or side effects.
28 *
29 * **Example** (Implementing Equal on a class)
30 *
31 * ```ts import.meta.vitest
32 * import { Equal, Hash } from "effect"
33 *
34 * class UserId implements Equal.Equal {
35 * constructor(readonly id: string) {}
36 *
37 * [Equal.symbol](that: Equal.Equal): boolean {
38 * return that instanceof UserId && this.id === that.id
39 * }
40 *
41 * [Hash.symbol](): number {
42 * return Hash.string(this.id)
43 * }
44 * }
45 *
46 * Equal.equals(new UserId("1"), new UserId("1")) // => true
47 * Equal.equals(new UserId("1"), new UserId("2")) // => false
48 * ```
49 *
50 * @see {@link Equal} — the interface that uses this symbol
51 * @see {@link isEqual} — type guard for `Equal` implementors
52 * @category symbols
53 * @since 2.0.0
54 */
55export const symbol = "~effect/Equal"
56
57/**
58 * The interface for types that define their own equality logic.
59 *
60 * **When to use**
61 *
62 * Use when you need value-based equality for a class (e.g. domain IDs,
63 * coordinates, money values).
64 * - When your type will be stored in `HashMap` or `HashSet`.
65 * - When the default structural comparison is too broad or too narrow for
66 * your type.
67 *
68 * **Details**
69 *
70 * Any object that implements both `[Equal.symbol]` (equality) and
71 * `[Hash.symbol]` (hashing) is recognized by {@link equals} and by hash-based
72 * collections such as `HashMap` and `HashSet`.
73 *
74 * - Extends `Hash.Hash`, so implementors **must** also provide `[Hash.symbol]`.
75 * - The hash contract: if `a[Equal.symbol](b)` returns `true`, then
76 * `Hash.hash(a)` must equal `Hash.hash(b)`.
77 * - {@link equals} delegates to this method when both operands implement it.
78 * If only one operand implements `Equal`, they are considered unequal.
79 *
80 * **Example** (Comparing coordinates by value)
81 *
82 * ```ts import.meta.vitest
83 * import { Equal, Hash } from "effect"
84 *
85 * class Coordinate implements Equal.Equal {
86 * constructor(readonly x: number, readonly y: number) {}
87 *
88 * [Equal.symbol](that: Equal.Equal): boolean {
89 * return that instanceof Coordinate &&
90 * this.x === that.x &&
91 * this.y === that.y
92 * }
93 *
94 * [Hash.symbol](): number {
95 * return Hash.string(`${this.x},${this.y}`)
96 * }
97 * }
98 *
99 * Equal.equals(new Coordinate(1, 2), new Coordinate(1, 2)) // => true
100 * Equal.equals(new Coordinate(1, 2), new Coordinate(3, 4)) // => false
101 * ```
102 *
103 * @see {@link symbol} — the property key used by the equality method
104 * @see {@link equals} — the main comparison function
105 * @see {@link isEqual} — type guard for `Equal` implementors
106 * @category models
107 * @since 2.0.0
108 */
109export interface Equal extends Hash.Hash {
110 [symbol](that: Equal): boolean
111}
112
113/**
114 * Checks whether two values are deeply structurally equal.
115 *
116 * **When to use**
117 *
118 * Use when you need Effect's default structural equality check.
119 *
120 * **Details**
121 *
122 * Returns a `boolean` and never throws. Primitives are compared by value, and
123 * `NaN` equals `NaN`. Objects implementing `Equal` delegate to their
124 * `[Equal.symbol]` method; if only one operand implements `Equal`, the result
125 * is `false`.
126 *
127 * Dates compare by ISO string, RegExps compare by string representation,
128 * arrays compare element-by-element, Maps and Sets compare entries
129 * order-independently, and plain objects compare enumerable keys recursively.
130 * Functions without an `Equal` implementation compare by reference. Circular
131 * structures use coinductive equality.
132 *
133 * Hash values are checked first as a fast-path rejection. The function also
134 * supports dual data-last usage: call it with one argument to get a curried
135 * predicate.
136 *
137 * **Gotchas**
138 *
139 * - Object-pair results are cached in a WeakMap. **Objects must not be
140 * be mutated after their first comparison.**
141 * - Map and Set entries are matched within groups of equal hashes, so they
142 * are O(n) for well-distributed hashes and O(n²) when every hash collides.
143 *
144 * **Example** (Comparing values)
145 *
146 * ```ts import.meta.vitest
147 * import { Equal } from "effect"
148 *
149 * Equal.equals(1, 1) // => true
150 * Equal.equals(NaN, NaN) // => true
151 * Equal.equals("a", "b") // => false
152 *
153 * Equal.equals({ a: 1, b: 2 }, { a: 1, b: 2 }) // => true
154 * Equal.equals([1, [2, 3]], [1, [2, 3]]) // => true
155 *
156 * Equal.equals(new Date("2024-01-01"), new Date("2024-01-01")) // => true
157 *
158 * const m1 = new Map([["a", 1], ["b", 2]])
159 * const m2 = new Map([["b", 2], ["a", 1]])
160 * Equal.equals(m1, m2) // => true
161 *
162 * const is5 = Equal.equals(5)
163 * is5(5) // => true
164 * is5(3) // => false
165 * ```
166 *
167 * @see {@link Equal} — the interface for custom equality
168 * @see {@link isEqual} — check whether a value implements `Equal`
169 * @see {@link asEquivalence} — wrap `equals` as an `Equivalence`
170 * @category equality
171 * @since 2.0.0
172 */
173export function equals<B>(that: B): <A>(self: A) => boolean
174export function equals<A, B>(self: A, that: B): boolean
175export function equals(): any {
176 if (arguments.length === 1) {
177 return (self: unknown) => compareBoth(self, arguments[0])
178 }
179 return compareBoth(arguments[0], arguments[1])
180}
181
182function compareBoth(self: unknown, that: unknown): boolean {
183 if (self === that) return true
184 if (self == null || that == null) return false
185 const selfType = typeof self
186 if (selfType !== typeof that) {
187 return false
188 }
189 // Special case for NaN: NaN should be considered equal to NaN
190 if (selfType === "number" && self !== self && that !== that) {
191 return true
192 }
193 if (selfType !== "object" && selfType !== "function") {
194 return false
195 }
196
197 if (byReferenceInstances.has(self) || byReferenceInstances.has(that)) {
198 return false
199 }
200
201 return compareObjects(self, that)
202}
203
204function compareObjects(self: object, that: object): boolean {
205 const depth = pathLeft.length
206 // A repeated pair closes a cycle under coinductive equality.
207 for (let i = depth; i-- > 0;) {
208 if (pathLeft[i] === self && pathRight[i] === that) return true
209 }
210 if (depth) return compareOnPath(self, that)
211 // Only outermost results are independent of path assumptions.
212 let known = results.get(self)
213 if (!known) results.set(self, known = new WeakMap())
214 let result = known.get(that)
215 if (result === undefined) known.set(that, result = compareOnPath(self, that))
216 return result
217}
218
219function compareOnPath(self: object, that: object): boolean {
220 pathLeft.push(self)
221 pathRight.push(that)
222 try {
223 return compareStructure(self, that)
224 } finally {
225 pathLeft.pop()
226 pathRight.pop()
227 }
228}
229
230// The pairs on the current comparison's path (the coinductive assumptions).
231const pathLeft: Array<object> = []
232const pathRight: Array<object> = []
233const results = new WeakMap<object, WeakMap<object, boolean>>()
234
235function compareStructure(self: object, that: object): boolean {
236 if (Hash.hash(self) !== Hash.hash(that)) {
237 return false
238 } else if (self instanceof Date) {
239 if (!(that instanceof Date)) return false
240 const selfTime = self.getTime()
241 const thatTime = that.getTime()
242 return selfTime === thatTime || (Number.isNaN(selfTime) && Number.isNaN(thatTime))
243 } else if (self instanceof RegExp) {
244 return that instanceof RegExp && self.toString() === that.toString()
245 }
246 const bothEquals = isEqual(self)
247 if (bothEquals !== isEqual(that) || (typeof self === "function" && !bothEquals)) {
248 return false
249 } else if (bothEquals) {
250 return (self as Equal)[symbol](that as Equal)
251 } else if (Array.isArray(self)) {
252 if (!Array.isArray(that) || self.length !== that.length) {
253 return false
254 }
255 return compareArrays(self, that)
256 } else if (ArrayBuffer.isView(self)) {
257 const selfIsDataView = self instanceof DataView
258 if (
259 !ArrayBuffer.isView(that) ||
260 self.byteLength !== that.byteLength ||
261 selfIsDataView !== (that instanceof DataView)
262 ) {
263 return false
264 }
265 if (selfIsDataView) {
266 return compareTypedArrays(viewBytes(self), viewBytes(that as DataView))
267 }
268 return compareTypedArrays(self as Uint8Array, that as Uint8Array)
269 } else if (self instanceof Map) {
270 if (!(that instanceof Map) || self.size !== that.size) {
271 return false
272 }
273 return compareHashed(self, that, entryHash, equalEntries)
274 } else if (self instanceof Set) {
275 if (!(that instanceof Set) || self.size !== that.size) {
276 return false
277 }
278 return compareHashed(self, that, Hash.hash, compareBoth)
279 }
280 return compareRecords(self as any, that as any)
281}
282
283function compareArrays(self: Array<unknown>, that: Array<unknown>): boolean {
284 for (let i = 0; i < self.length; i++) {
285 if (!compareBoth(self[i], that[i])) {
286 return false
287 }
288 }
289
290 return true
291}
292
293function compareTypedArrays(self: Uint8Array, that: Uint8Array): boolean {
294 if (self.length !== that.length) {
295 return false
296 }
297 for (let i = 0; i < self.length; i++) {
298 if (self[i] !== that[i]) {
299 return false
300 }
301 }
302 return true
303}
304
305function compareRecords(
306 self: Record<PropertyKey, unknown>,
307 that: Record<PropertyKey, unknown>
308): boolean {
309 const selfKeys = getAllObjectKeys(self)
310 const thatKeys = getAllObjectKeys(that)
311
312 if (selfKeys.size !== thatKeys.size) {
313 return false
314 }
315
316 for (const key of selfKeys) {
317 if (!(thatKeys.has(key)) || !compareBoth(self[key], that[key])) {
318 return false
319 }
320 }
321
322 return true
323}
324
325// Match items one-to-one within equal-hash groups.
326function compareHashed<A>(
327 self: Iterable<A>,
328 that: Iterable<A>,
329 hashOf: (item: A) => number,
330 equivalent: (self: A, that: A) => boolean
331): boolean {
332 const groups = new Map<number, Array<A>>()
333 for (const item of that) {
334 const h = hashOf(item)
335 const group = groups.get(h)
336 if (group) group.push(item)
337 else groups.set(h, [item])
338 }
339 outer: for (const item of self) {
340 const group = groups.get(hashOf(item))
341 if (group) {
342 for (let i = 0; i < group.length; i++) {
343 if (equivalent(item, group[i])) {
344 group[i] = group[group.length - 1]
345 group.pop()
346 continue outer
347 }
348 }
349 }
350 return false
351 }
352 return true
353}
354
355const entryHash = (entry: readonly [unknown, unknown]): number => Hash.hash(entry[0])
356
357const equalEntries = <K, V>(self: readonly [K, V], that: readonly [K, V]): boolean =>
358 compareBoth(self[0], that[0]) && compareBoth(self[1], that[1])
359
360const sameGroup = (): number => 0
361
362/** @internal */
363export function makeCompareMap<K, V>(keyEquivalence: Equivalence<K>, valueEquivalence: Equivalence<V>) {
364 return makeCompareSet<readonly [K, V]>((self, that) =>
365 keyEquivalence(self[0], that[0]) && valueEquivalence(self[1], that[1])
366 )
367}
368
369/** @internal */
370export function makeCompareSet<A>(equivalence: Equivalence<A>) {
371 return function compareSets(self: Iterable<A>, that: Iterable<A>): boolean {
372 return compareHashed(self, that, sameGroup, equivalence)
373 }
374}
375
376/**
377 * Checks whether a value implements the {@link Equal} interface.
378 *
379 * **When to use**
380 *
381 * Use when you need generic utility code to distinguish `Equal` implementors
382 * from plain values before calling `[Equal.symbol]` directly.
383 *
384 * **Details**
385 *
386 * - Pure function, no side effects.
387 * - Returns `true` if and only if `u` has a property keyed by
388 * {@link symbol}.
389 * - Acts as a TypeScript type guard, narrowing the input to {@link Equal}.
390 *
391 * **Example** (Checking Equal values)
392 *
393 * ```ts import.meta.vitest
394 * import { Equal, Hash } from "effect"
395 *
396 * class Token implements Equal.Equal {
397 * constructor(readonly value: string) {}
398 * [Equal.symbol](that: Equal.Equal): boolean {
399 * return that instanceof Token && this.value === that.value
400 * }
401 * [Hash.symbol](): number {
402 * return Hash.string(this.value)
403 * }
404 * }
405 *
406 * Equal.isEqual(new Token("abc")) // => true
407 * Equal.isEqual({ x: 1 }) // => false
408 * Equal.isEqual(42) // => false
409 * ```
410 *
411 * @see {@link Equal} — the interface being checked
412 * @see {@link symbol} — the property key that signals `Equal` support
413 * @category guards
414 * @since 2.0.0
415 */
416export const isEqual = (u: unknown): u is Equal => hasProperty(u, symbol)
417
418/**
419 * Wraps {@link equals} as an `Equivalence<A>`.
420 *
421 * **When to use**
422 *
423 * Use when you want to pass `Equal.equals` to APIs that require an
424 * `Equivalence`.
425 *
426 * **Details**
427 *
428 * - Returns a function `(a: A, b: A) => boolean` that delegates to
429 * {@link equals}.
430 * - Pure; allocates a thin wrapper on each call.
431 *
432 * **Example** (Deduplicating with Equal semantics)
433 *
434 * ```ts import.meta.vitest
435 * import { Array, Equal } from "effect"
436 *
437 * Array.dedupeWith([1, 2, 2, 3, 1], Equal.asEquivalence<number>()) // => [1, 2, 3]
438 * ```
439 *
440 * @see {@link equals} — the underlying comparison function
441 * @category instances
442 * @since 4.0.0
443 */
444export const asEquivalence: <A>() => Equivalence<A> = () => equals
445
446/**
447 * Creates a proxy that uses reference equality instead of structural equality.
448 *
449 * **When to use**
450 *
451 * Use when you need to compare a plain object or array by identity without
452 * mutating the original value.
453 *
454 * **Details**
455 *
456 * - Returns a `Proxy` wrapping `obj`. The proxy reads through to the
457 * original, so property access is unchanged.
458 * - The proxy is registered in an internal WeakSet; {@link equals} returns
459 * `false` for any pair where at least one operand is in that set (unless
460 * they are the same reference).
461 * - Each call creates a **new** proxy, so `byReference(x) !== byReference(x)`.
462 * - Does **not** mutate the original object (unlike {@link byReferenceUnsafe}).
463 *
464 * **Example** (Opting out of structural equality)
465 *
466 * ```ts import.meta.vitest
467 * import { Equal } from "effect"
468 *
469 * const a = { x: 1 }
470 * const b = { x: 1 }
471 *
472 * Equal.equals(a, b) // => true
473 *
474 * const aRef = Equal.byReference(a)
475 * Equal.equals(aRef, b) // => false
476 * Equal.equals(aRef, aRef) // => true
477 * aRef.x // => 1
478 * ```
479 *
480 * @see {@link byReferenceUnsafe} — same effect without a proxy (mutates the
481 * original)
482 * @see {@link equals} — the comparison function affected by this opt-out
483 * @category equality
484 * @since 4.0.0
485 */
486export const byReference = <T extends object>(obj: T): T => byReferenceUnsafe(new Proxy(obj, {}))
487
488/**
489 * Marks an object permanently to use reference equality, without creating a proxy.
490 *
491 * **When to use**
492 *
493 * Use when you need reference equality without proxy allocation and accept
494 * permanently marking the original object for reference-only equality.
495 *
496 * **Details**
497 *
498 * - Adds `obj` to an internal WeakSet. From that point on, {@link equals}
499 * treats it as reference-only.
500 * - Returns the **same** object (not a copy or proxy), so
501 * `byReferenceUnsafe(x) === x`.
502 * - Does **not** affect the object's prototype, properties, or behavior
503 * beyond equality checks.
504 *
505 * **Gotchas**
506 *
507 * The marking is irreversible for the lifetime of the object.
508 *
509 * **Example** (Marking an object for reference equality)
510 *
511 * ```ts import.meta.vitest
512 * import { Equal } from "effect"
513 *
514 * const obj1 = { a: 1, b: 2 }
515 * const obj2 = { a: 1, b: 2 }
516 *
517 * const marked = Equal.byReferenceUnsafe(obj1)
518 *
519 * Equal.equals(obj1, obj2) // => false
520 * Equal.equals(obj1, obj1) // => true
521 * marked === obj1 // => true
522 * ```
523 *
524 * @see {@link byReference} — safer alternative that creates a proxy
525 * @see {@link equals} — the comparison function affected by this opt-out
526 * @category unsafe
527 * @since 4.0.0
528 */
529export const byReferenceUnsafe = <T extends object>(obj: T): T => {
530 byReferenceInstances.add(obj)
531 return obj
532}