Object density

density.ts

function density(x: unknown) {
    const paths = new Set<string>();
    const children = Array.from(gChildren(x));
    // discover paths
    for (const [, child] of children) {
        for (const [path] of gPaths(child, 'primitives')) {
            paths.add(JSON.stringify(path));
        }
    }
    // count empty values
    let empties = 0;
    for (const [, child] of children) {
        if (!isBag(child)) continue;
        for (const path of paths) {
            const p = JSON.parse(path);
            let item: any = child;
            for (const key of p) {
                if (!(key in item)) {
                    ++empties;
                    break;
                }
                item = item[key];
                if (!isBag(item)) {
                    break;
                }
            }
        }
    }
    const cells = children.length * paths.size;
    return cells === 0 ? 1 : 1 - empties / cells;
}

function gPaths(x: unknown, to: 'primitives', p?: Path, visited?: Set<unknown>): Generator<[p: Path, v: Primitive]>;
function gPaths(x: unknown, to: 'objects', p?: Path, visited?: Set<unknown>): Generator<[p: Path, v: object]>;
function gPaths(
    x: unknown,
    to: 'primitives' | 'objects',
    p: Path,
    visited?: Set<unknown>
): Generator<[p: Path, v: unknown]>;
function* gPaths(
    x: unknown,
    to: 'primitives' | 'objects',
    p: Path = [],
    visited = new Set<unknown>()
): Generator<[p: Path, v: unknown]> {
    if (isBag(x)) visited.add(x);
    for (const [k, v] of gChildren(x)) {
        if (visited.has(v)) throw new Error(`cycle detected ${k} ${v}`);
        yield* gPaths(v, to, [...p, k], visited);
    }
    if ((to === 'objects') === isBag(x)) {
        yield [p, x];
    }
}

// does this value have properties.
function isBag(x: unknown): x is object | Function {
    return (typeof x === 'object' && x !== null) || typeof x === 'function';
}