Immutable Structual Sharing

console.log

mmis1000@mmis1000-:~/tests$ node StructualSharing.js 
[ 1, 2, 3 ] [ 1, {}, 3 ] [ 1, { a: 1, b: 2 } ] true true true true true true true

StructualSharing.js

/// <reference path="./weak-ref.ts" />

// The finalizationRegistry must be keep alive or nothing will ever works
globalThis.finalizationRefs = globalThis.finalizationRefs || [];

let Tuple, Record;
{
    const valueSymbol = Symbol('value')
    const LinkMap = new Map()

    const TupleToRecordMap = new WeakMap()
    const RecordToTupleMap = new WeakMap()

    const finalizationRegistry = new FinalizationRegistry((path) => {
        const nodes = [LinkMap]
        let cursor = LinkMap

        for (let item of path) {
            cursor = cursor.get(item)
            nodes.push(cursor)
        }

        nodes[nodes.length - 1].delete(valueSymbol)

        for (let i = nodes.length - 1; i >= 1; i--) {
            if (nodes[i].size === 0) {
                nodes[i - 1].delete(path[i - 1])
            }
        }
    })

    globalThis.finalizationRefs.push(finalizationRegistry)

    const t = (...args) => {
        let cursor = LinkMap

        for (let item of args) {
            if (!cursor.has(item)) {
                var newMap = new Map()
                cursor.set(item, newMap)
            }

            cursor = cursor.get(item)
        }

        if (!cursor.get(valueSymbol) || !cursor.get(valueSymbol).deref()) {
            const tuple = [...args]
            const weakValue = new WeakRef(tuple)
            finalizationRegistry.register(tuple, args)
            cursor.set(valueSymbol, weakValue)
        }

        return cursor.get(valueSymbol).deref()
    }

    const r = (obj) => {
        var entries = Object.entries(obj)

        var pairs = entries.map(e => t(...e))

        pairs.sort((x, y) => x[0] > y[0] ? 1 : -1)

        var tuple = t(...pairs)

        if (TupleToRecordMap.has(tuple)) {
            return TupleToRecordMap.get(tuple)
        }

        const newObj = {}

        for (let [k, v] of pairs) {
            newObj[k] = v
        }

        TupleToRecordMap.set(tuple, newObj)
        RecordToTupleMap.set(newObj, tuple)

        return newObj
    }

    var obj = {}

    Tuple = t
    Record = r

    console.log(
        t(1, 2, 3),
        t(1, obj, 3),
        t(1, r({ a: 1, b: 2})),
        t(1, 2, 3)                        === t(1, 2, 3),
        t(1, ...t(2, 3))                  === t(1, 2, 3),
        t(1, t(2, 3))                     === t(1, t(2, 3)),
        r({ a: 1, b: 2})                  === r({ a: 1, b: 2}),
        t(1, r({ a: 1, b: 2}))            === t(1, r({ b: 2, a: 1})),
        t(1, r({ a: 1, b: 2}))[1].a       === 1,
        t(1, obj, 2)                      === t(1, obj, 2)
    )
}