nish/json-equal

Whether two JSON values are equal by JSON Schema's rule, a canonical text and a hash that agree with it, and the first repeated element of an array, which is what const, enum and uniqueItems ask.

import {
  jsonEqual,
  jsonEqualCanonical,
  jsonEqualFirstDuplicate,
  jsonEqualHash,
} from "nish/json-equal";
import { jsonEqual, jsonEqualFirstDuplicate } from "nish/json-equal"

const doc = new JsonDocument(new JsonLimits())
const a = doc.parseText('[{"x":1,"y":[true]},{"y":[true],"x":1.0}]')
jsonEqual(doc, doc.at(a, 0), doc, doc.at(a, 1))   // true
jsonEqualFirstDuplicate(doc, a)                    // 1
The rule

Two values are equal when they are the same kind and: two numbers have the same mathematical value (1, 1.0 and 1e0 are equal; nish/json-number decides, never through f64), two strings have the same string, two booleans the same value, two arrays the same length and equal elements in order, and two objects the same keys with equal values, in whatever order the members are written. null equals only null, and true is not 1. A number whose exponent is past JSON_NUMBER_MAX_EXPONENT cannot be read exactly, and equals only a number written with the same text.

No depth limit. Every walk keeps its own stack in an array, so a tree built with push and set deeper than any parser allows compares as well as a flat one, and nothing recurses.

What a call costs

jsonEqual stops at the first difference. Up to there it is linear in the values' size, except that each pair of objects reads every key (one string each) and sorts them, n log n for n members; it also allocates one string per string value, its stack, and whatever jsonNumberCompare allocates per number pair. jsonEqualCanonical builds the canonical text, about the size of the value written as JSON, and sorts keys the same way. jsonEqualHash is FNV-1a of that text's units: its bytes natively, its code units under Node.

Every order and length below is in those units too. jsonEqualFirstDuplicate makes the canonical text of every element up to the first repeat and keeps them in a Map.

The hash is not keyed

FNV-1a (public domain) is the same in every process, so an attacker can make many values that share a hash, and a table keyed by jsonEqualHash alone degrades to a list. It is for a filter or a fingerprint; jsonEqualFirstDuplicate keys its Map by the canonical text, which the Map's own keyed hash spreads.

Functions

jsonEqual

Whether value a of document da equals value b of document db by JSON Schema's rule (the module header): numbers by value, objects whatever their member order. The two may be one document. false when either handle names no value. Iterative, so any depth compares.

const jsonEqual: (
  da: JsonDocument,
  a: i32,
  db: JsonDocument,
  b: i32,
) => boolean
daJsonDocumentrequired

the document that holds a.

ai32required

a value handle from da.

dbJsonDocumentrequired

the document that holds b, which may be da itself.

bi32required

a value handle from db.

returnsboolean

true when the two values are equal as JSON Schema compares them.

jsonEqualCanonical

The canonical text of value v: the same text for exactly the values jsonEqual calls equal, so it is a key for a Map or Set of values. It is not JSON: each value is a tag and what it holds, z, t and f for null, true and false, n and a jsonNumberCanonical text and ; for a number, s, a length, : and the string itself, a and a count and : before an array's elements, and o and a count and : before an object's members in key order, each key a length, : and the key (orders and lengths as the module header says). "" for a handle that names no value.

const jsonEqualCanonical: (
  doc: JsonDocument,
  v: i32,
) => string
docJsonDocumentrequired

the document that holds v.

vi32required

the value to write out.

returnsstring

the canonical text, which two values share exactly when jsonEqual calls them equal.

jsonEqualFirstDuplicate

The position of the first element of array v equal (jsonEqual) to an earlier one, or -1 when every element is distinct or v is not an array: JSON Schema's uniqueItems holds exactly when this is -1. Linear in the elements read, through a Map of their canonical texts.

const jsonEqualFirstDuplicate: (
  doc: JsonDocument,
  v: i32,
) => i32
docJsonDocumentrequired

the document that holds v.

vi32required

the array to search.

returnsi32

the index of the first repeated element, or -1 when there is none.

jsonEqualHash

A 64-bit hash of value v that agrees with jsonEqual: equal values hash the same. FNV-1a of the canonical text's units (its code units under Node, so a string past U+00FF hashes differently there), unkeyed (the module header says what that means for a table). The offset basis for a handle that names no value.

const jsonEqualHash: (doc: JsonDocument, v: i32) => u64
docJsonDocumentrequired

the document that holds v.

vi32required

the value to hash.

returnsu64

the hash, the same for any two values jsonEqual calls equal.