DoubleSyncDiff.js

import { equalBytes } from './internal.js';

/**
 * Pure diff algorithm: given two parsed bundles (V_prev and V_new), produce an
 * ordered list of operations that turn V_prev into V_new.
 *
 * Op set:
 *   `replace_file(path, manifest, fingerprint)` — file content changed
 *   `add_file(path, manifest, fingerprint)`     — new file (intermediate folders implicit)
 *   `add_empty_folder(path)`                    — empty folder (non-empty are implied by add_file)
 *   `remove(path)`                              — file or folder removed (recursive for folders)
 *
 * Identity check: folders whose 32-byte fingerprint matches are skipped entirely
 * (zero ops emitted for the whole subtree). That's where the size win comes from.
 *
 * @typedef {Object} DiffOp
 * @property {'replace_file' | 'add_file' | 'add_empty_folder' | 'remove'} kind
 * @property {string[]} path - segments from root, exclusive of root
 * @property {Uint8Array} [manifest]   - raw CDCManifest bytes (for *_file ops)
 * @property {Uint8Array} [fingerprint] - 32 bytes (for *_file ops)
 */

/**
 * Compare two parsed bundles and return the ops that take prev → next.
 *
 * Children at every level are matched by `name` (not by index), so a file added
 * before another file in the same folder produces just an `add_file` op rather
 * than churning the second file.
 *
 * @param {import('./DoubleSyncSnapshot.js').default} prevSnapshot
 * @param {import('./DoubleSyncSnapshot.js').default} nextSnapshot
 * @returns {DiffOp[]}
 */
export function diffSnapshots(prevSnapshot, nextSnapshot) {
    return diffChildren(prevSnapshot.rootChildren, nextSnapshot.rootChildren, []);
}

/**
 * Recurse into two ordered arrays of snapshot entries.
 *
 * @param {Array<Object>} prevEntries
 * @param {Array<Object>} nextEntries
 * @param {string[]} prefix - path from root to the folder these entries belong to
 * @returns {DiffOp[]}
 */
function diffChildren(prevEntries, nextEntries, prefix) {
    /** @type {DiffOp[]} */
    const ops = [];

    const prevByName = new Map(prevEntries.map(e => [e.name, e]));
    const nextByName = new Map(nextEntries.map(e => [e.name, e]));

    // Removes first — apply them in stable name order for determinism.
    const removedNames = [...prevByName.keys()].filter(n => !nextByName.has(n)).sort();
    for (const name of removedNames) {
        ops.push({ kind: 'remove', path: [...prefix, name] });
    }

    // Then process the next-side children, in stable order.
    const nextNames = [...nextByName.keys()].sort();
    for (const name of nextNames) {
        const next = nextByName.get(name);
        const prev = prevByName.get(name);
        const here = [...prefix, name];

        if (!prev) {
            // brand new entry
            emitAdds(next, here, ops);
            continue;
        }

        if (prev.kind !== next.kind) {
            // type change at same path — remove old, add new
            ops.push({ kind: 'remove', path: here });
            emitAdds(next, here, ops);
            continue;
        }

        if (equalBytes(prev.fingerprint, next.fingerprint)) {
            // identical subtree (folder) or identical content (file) — no ops
            continue;
        }

        if (next.kind === 'file') {
            ops.push({
                kind: 'replace_file',
                path: here,
                manifest: next.manifestBytes,
                fingerprint: next.fingerprint,
            });
        } else {
            // folder with same name but different fingerprint → recurse
            ops.push(...diffChildren(prev.children, next.children, here));
        }
    }

    return ops;
}

/**
 * Emit add ops for an entry that wasn't present on the prev side.
 *
 * @param {Object} entry - snapshot entry (file or folder)
 * @param {string[]} path
 * @param {DiffOp[]} sink - ops accumulator
 */
function emitAdds(entry, path, sink) {
    if (entry.kind === 'file') {
        sink.push({
            kind: 'add_file',
            path,
            manifest: entry.manifestBytes,
            fingerprint: entry.fingerprint,
        });
        return;
    }
    // folder
    if (entry.children.length === 0) {
        sink.push({ kind: 'add_empty_folder', path });
        return;
    }
    // non-empty folder: recurse — children's adds implicitly create this folder
    for (const child of entry.children) {
        emitAdds(child, [...path, child.name], sink);
    }
}