Canonicalization

The fingerprint function relies on a canonicalization step to ensure deterministic hashing. This page describes the algorithm in detail.

The `canonicalize` Function


function canonicalize(value: unknown): unknown {
  if (value === null || value === undefined) return value;
 
  if (Array.isArray(value)) {
    const allStrings = value.every((v) => typeof v === "string");
    const items = allStrings ? (value as string[]).slice().sort() : value;
    return items.map(canonicalize);
  }
 
  if (typeof value === "object") {
    const sorted: Record<string, unknown> = {};
    for (const key of Object.keys(value as Record<string, unknown>).sort()) {
      sorted[key] = canonicalize((value as Record<string, unknown>)[key]);
    }
    return sorted;
  }
 
  return value;
}

Rules

1. Null and undefined pass through


canonicalize(null)      // → null
canonicalize(undefined) // → undefined

2. Object keys are sorted


canonicalize({ z: 1, a: 2, m: 3 })
// → { a: 2, m: 3, z: 1 }

This is recursive — nested objects are also sorted:


canonicalize({ outer: { z: 1, a: 2 } })
// → { outer: { a: 2, z: 1 } }

3. All-string arrays are sorted


canonicalize(["charlie", "alpha", "bravo"])
// → ["alpha", "bravo", "charlie"]

4. Mixed arrays preserve order


canonicalize([3, 1, 2])
// → [3, 1, 2] (not all strings, order preserved)
 
canonicalize(["a", 1, "b"])
// → ["a", 1, "b"] (not all strings)

5. Primitives pass through


canonicalize(42)     // → 42
canonicalize("hello") // → "hello"
canonicalize(true)   // → true

Why Deep Clone First?

The fingerprint function calls structuredClone(obj) before canonicalization to avoid mutating the caller’s object. canonicalize sorts arrays in-place via .sort(), which would modify the original without cloning.

Why Sort String Arrays?

In distributed systems, the same set of items may arrive in different orders depending on which node responded first. Sorting ensures that ["a", "b"] and ["b", "a"] produce the same fingerprint — they represent the same logical set.

Non-string arrays are not sorted because their order may be semantically meaningful (e.g., processing steps, priority lists).