DoubleSyncDiffPatch.js

/**
 * Stateful diff patch — takes a receiver from V_prev to V_new by carrying ops and
 * only the chunks the receiver doesn't already have.
 *
 * To apply, the receiver MUST hold the previous snapshot bytes. The patch carries
 * a SHA-256 of those previous bytes so the receiver can detect a mismatched base
 * before any destructive changes happen.
 *
 * Wire format (little-endian):
 *
 *   52B header:
 *      4B  magic         = 0xCDCB0102
 *      1B  version       = 1
 *      3B  reserved      = 0
 *     32B  prevSnapshotHash
 *      4B  opsLen        (u32) — size of the ops section in bytes
 *      8B  chunksLen     (u64) — size of the chunks section in bytes
 *
 *   ops section (opsLen bytes), one record per op:
 *      u8 kind
 *           0 = replace_file
 *           1 = add_file
 *           2 = add_empty_folder
 *           3 = remove
 *      u8 pathDepth
 *      for each segment: u16 nameLen + utf-8 bytes
 *      if kind == 0 or 1:  32B fingerprint + u32 manifestLen + manifestBytes
 *
 *   chunks section (chunksLen bytes), identical layout to DoubleSyncPatch:
 *      4B chunkCount
 *      per chunk: 32B hash + 4B length + length bytes
 */

import { MAGICS } from './DoubleSyncFormat.js';
import {
    parseChunksSection,
    iterateChunks,
    measureChunksSection,
    writeChunksSection,
} from './chunksSection.js';

const MAGIC = MAGICS['diff-patch'];
const VERSION = 1;
const HEADER_SIZE = 52;

const KIND_REPLACE_FILE = 0;
const KIND_ADD_FILE = 1;
const KIND_ADD_EMPTY_FOLDER = 2;
const KIND_REMOVE = 3;

const KIND_NAME = ['replace_file', 'add_file', 'add_empty_folder', 'remove'];
const NAME_KIND = new Map(KIND_NAME.map((n, i) => [n, i]));

const ENC = new TextEncoder();
const DEC = new TextDecoder();

export default class DoubleSyncDiffPatch {
    /**
     * Parse a binary diff patch.
     *
     * @param {Uint8Array} doc
     * @throws {Error} on bad magic / version / truncation
     */
    constructor(doc) {
        if (!(doc instanceof Uint8Array)) throw new Error('DoubleSyncDiffPatch: doc must be Uint8Array');
        if (doc.length < HEADER_SIZE) throw new Error(`DoubleSyncDiffPatch: doc too short (${doc.length} < ${HEADER_SIZE})`);

        const dv = new DataView(doc.buffer, doc.byteOffset, doc.byteLength);

        const magic = dv.getUint32(0, true);
        if (magic !== MAGIC) throw new Error(`DoubleSyncDiffPatch: bad magic 0x${magic.toString(16)}`);

        const version = doc[4];
        if (version !== VERSION) throw new Error(`DoubleSyncDiffPatch: unsupported version ${version}`);

        /** @type {Uint8Array} - 32 bytes */
        this.prevSnapshotHash = doc.subarray(8, 40);

        const opsLen = dv.getUint32(40, true);
        const chunksLen = Number(dv.getBigUint64(44, true));

        if (HEADER_SIZE + opsLen + chunksLen !== doc.length) {
            throw new Error(
                `DoubleSyncDiffPatch: size mismatch (header=${HEADER_SIZE} ops=${opsLen} chunks=${chunksLen}, doc=${doc.length})`,
            );
        }

        /** @type {Uint8Array} */
        this._doc = doc;
        /** @type {Uint8Array} */
        this._opsSection = doc.subarray(HEADER_SIZE, HEADER_SIZE + opsLen);
        /** @type {Uint8Array} */
        this._chunksSection = doc.subarray(HEADER_SIZE + opsLen, HEADER_SIZE + opsLen + chunksLen);

        // Pre-index ops so iteration is O(N) and validation happens once.
        /** @type {Array<{kindByte: number, off: number, end: number}>} */
        this._opIndex = [];
        const opsDV = new DataView(this._opsSection.buffer, this._opsSection.byteOffset, this._opsSection.byteLength);
        let cur = 0;
        let opsCount = 0;
        while (cur < this._opsSection.length) {
            const start = cur;
            const kindByte = this._opsSection[cur]; cur += 1;
            if (cur >= this._opsSection.length) throw new Error(`DoubleSyncDiffPatch: truncated op at ${start}`);
            const depth = this._opsSection[cur]; cur += 1;
            for (let s = 0; s < depth; s++) {
                if (cur + 2 > this._opsSection.length) throw new Error(`DoubleSyncDiffPatch: truncated path-segment-len in op ${opsCount}`);
                const nameLen = opsDV.getUint16(cur, true); cur += 2;
                if (cur + nameLen > this._opsSection.length) throw new Error(`DoubleSyncDiffPatch: truncated path-segment in op ${opsCount}`);
                cur += nameLen;
            }
            if (kindByte === KIND_REPLACE_FILE || kindByte === KIND_ADD_FILE) {
                if (cur + 32 + 4 > this._opsSection.length) throw new Error(`DoubleSyncDiffPatch: truncated file-op payload in op ${opsCount}`);
                cur += 32;
                const manifestLen = opsDV.getUint32(cur, true); cur += 4;
                if (cur + manifestLen > this._opsSection.length) throw new Error(`DoubleSyncDiffPatch: truncated manifest in op ${opsCount}`);
                cur += manifestLen;
            } else if (kindByte !== KIND_ADD_EMPTY_FOLDER && kindByte !== KIND_REMOVE) {
                throw new Error(`DoubleSyncDiffPatch: unknown op kind ${kindByte} at ${start}`);
            }
            this._opIndex.push({ kindByte, off: start, end: cur });
            opsCount += 1;
        }

        /** @type {number} */
        this.opCount = opsCount;

        const parsedChunks = parseChunksSection(this._chunksSection, 'DoubleSyncDiffPatch');
        /** @type {number} */
        this.chunkCount = parsedChunks.chunkCount;
        /** @type {Array<{hashOff: number, dataOff: number, length: number}>} */
        this._chunkIndex = parsedChunks.index;
    }

    /**
     * Iterate ops in encoding order.
     * @yields {{kind: string, path: string[], manifest?: Uint8Array, fingerprint?: Uint8Array}}
     */
    *ops() {
        const opsDV = new DataView(this._opsSection.buffer, this._opsSection.byteOffset, this._opsSection.byteLength);
        for (const rec of this._opIndex) {
            let cur = rec.off;
            const kindByte = this._opsSection[cur]; cur += 1;
            const depth = this._opsSection[cur]; cur += 1;
            const path = [];
            for (let s = 0; s < depth; s++) {
                const nameLen = opsDV.getUint16(cur, true); cur += 2;
                path.push(DEC.decode(this._opsSection.subarray(cur, cur + nameLen)));
                cur += nameLen;
            }
            /** @type {Object} */
            const out = { kind: KIND_NAME[kindByte], path };
            if (kindByte === KIND_REPLACE_FILE || kindByte === KIND_ADD_FILE) {
                out.fingerprint = this._opsSection.subarray(cur, cur + 32);
                cur += 32;
                const manifestLen = opsDV.getUint32(cur, true); cur += 4;
                out.manifest = this._opsSection.subarray(cur, cur + manifestLen);
            }
            yield out;
        }
    }

    /**
     * Iterate embedded chunks.
     * @yields {{hash: Uint8Array, bytes: Uint8Array}}
     */
    *chunks() {
        yield* iterateChunks(this._chunksSection, this._chunkIndex);
    }

    /**
     * Build a binary diff-patch document.
     *
     * @param {Object} params
     * @param {Uint8Array} params.prevSnapshotHash - 32 bytes
     * @param {Iterable<{kind: string, path: string[], manifest?: Uint8Array, fingerprint?: Uint8Array}>} params.ops
     * @param {Iterable<{hash: Uint8Array, bytes: Uint8Array}>} params.chunks
     * @returns {Uint8Array}
     */
    static encode({ prevSnapshotHash, ops, chunks }) {
        if (!(prevSnapshotHash instanceof Uint8Array) || prevSnapshotHash.length !== 32) {
            throw new Error('DoubleSyncDiffPatch.encode: prevSnapshotHash must be a 32-byte Uint8Array');
        }

        // Pass 1: serialize ops into a temp byte list to compute opsLen.
        /** @type {Uint8Array[]} */
        const opParts = [];
        let opsLen = 0;
        for (const op of ops) {
            const kindByte = NAME_KIND.get(op.kind);
            if (kindByte === undefined) throw new Error(`DoubleSyncDiffPatch.encode: unknown op kind ${op.kind}`);
            if (!Array.isArray(op.path) || op.path.length > 255) {
                throw new Error(`DoubleSyncDiffPatch.encode: path must be string[] of length <= 255`);
            }

            // Header byte + depth byte
            const head = new Uint8Array(2);
            head[0] = kindByte;
            head[1] = op.path.length;
            opParts.push(head);
            opsLen += head.length;

            for (const seg of op.path) {
                const segBytes = ENC.encode(seg);
                if (segBytes.length > 0xFFFF) {
                    throw new Error(`DoubleSyncDiffPatch.encode: path segment too long (${segBytes.length})`);
                }
                const lenBuf = new Uint8Array(2);
                new DataView(lenBuf.buffer).setUint16(0, segBytes.length, true);
                opParts.push(lenBuf, segBytes);
                opsLen += lenBuf.length + segBytes.length;
            }

            if (kindByte === KIND_REPLACE_FILE || kindByte === KIND_ADD_FILE) {
                if (!(op.fingerprint instanceof Uint8Array) || op.fingerprint.length !== 32) {
                    throw new Error(`DoubleSyncDiffPatch.encode: file op missing 32-byte fingerprint`);
                }
                if (!(op.manifest instanceof Uint8Array)) {
                    throw new Error(`DoubleSyncDiffPatch.encode: file op missing manifest`);
                }
                const mLen = new Uint8Array(4);
                new DataView(mLen.buffer).setUint32(0, op.manifest.length, true);
                opParts.push(op.fingerprint, mLen, op.manifest);
                opsLen += 32 + 4 + op.manifest.length;
            }
        }

        // Pass 2: serialize chunks section.
        const chunksList = [...chunks];
        const chunksLen = measureChunksSection(chunksList, 'DoubleSyncDiffPatch.encode');

        const out = new Uint8Array(HEADER_SIZE + opsLen + chunksLen);
        const dv = new DataView(out.buffer, out.byteOffset, out.byteLength);

        dv.setUint32(0, MAGIC, true);
        out[4] = VERSION;
        // bytes 5..7 reserved
        out.set(prevSnapshotHash, 8);
        dv.setUint32(40, opsLen, true);
        dv.setBigUint64(44, BigInt(chunksLen), true);

        let cur = HEADER_SIZE;
        for (const part of opParts) {
            out.set(part, cur);
            cur += part.length;
        }

        writeChunksSection(out, dv, cur, chunksList);

        return out;
    }

    /**
     * Peek a buffer's first 4 bytes as a u32 little-endian magic number.
     * Useful to dispatch between DoubleSyncPatch / DoubleSyncDiffPatch by header.
     * @param {Uint8Array} doc
     * @returns {number}
     */
    static peekMagic(doc) {
        if (!(doc instanceof Uint8Array) || doc.length < 4) return 0;
        return new DataView(doc.buffer, doc.byteOffset, doc.byteLength).getUint32(0, true);
    }

    /** @internal */
    static _MAGIC() { return MAGIC; }
}