dt-helpers.js

// Helpers for reading a document's history. dt_diff_from is built on top of
// dt.js, and is kept out of that file because it is generated and gets
// replaced wholesale whenever diamond-types is rebuilt.

// What a run of operations did to some text: the text marked up with
// everything the operations inserted and deleted, and who did each of those
// things.
//
// An operation is {kind, agent, start, end, content}. "Ins" puts `content` in
// at `start`, "Del" takes out [start, end). Positions count code points, and
// each operation reads against the text as the ones before it left it.
//
// Returns runs of [what, text, agent], where `what` is 1 for text the
// operations added, -1 for text they removed, and 0 for text they left alone.
// Deleted text is attributed to whoever deleted it, not to whoever originally
// wrote it.
// How many code points a string holds. Counting the surrogates is far cheaper
// than spreading the string out, and most strings have none.
function cp_length(s) {
    return /[\uD800-\uDBFF]/.test(s) ? [...s].length : s.length
}

// How far into the text the operations reach, in code points. Nothing before
// `lo` is ever addressed by any of them, and nothing from `hi` on is ever
// touched, so both of those stretches come out the way they went in.
function touched_range(len, ops) {
    let lo = Infinity, tail = len, shift = 0
    for (let xf of ops) {
        if (xf.kind == "Ins") {
            let n = cp_length(xf.content)
            lo = Math.min(lo, xf.start)
            shift += n
            // What is left beyond this operation, once it has been applied
            tail = Math.min(tail, Math.max(0, len + shift - (xf.start + n)))
        } else if (xf.kind == "Del") {
            lo = Math.min(lo, Math.max(0, xf.start - 1))  // it writes on the cell before it
            shift -= xf.end - xf.start
            tail = Math.min(tail, Math.max(0, len + shift - xf.start))
        }
    }
    return lo === Infinity ? [0, 0] : [lo, Math.max(lo, len - tail)]
}

// What a run of operations did to some text: the text marked up with
// everything the operations inserted and deleted, and who did each of those
// things.
//
// An operation is {kind, agent, start, end, content}. "Ins" puts `content` in
// at `start`, "Del" takes out [start, end). Positions count code points, and
// each operation reads against the text as the ones before it left it.
//
// Returns runs of [what, text, agent], where `what` is 1 for text the
// operations added, -1 for text they removed, and 0 for text they left alone.
// Deleted text is attributed to whoever deleted it, not to whoever originally
// wrote it.
function diff_from_ops(text, ops) {
    return diff_from_runs(text, [{ ops, marked: true }])
}

// The same, for several runs of operations applied one after another, where
// only some of them are the ones being asked about. An unmarked run still
// moves the text -- it happened, and everything after it sits where it left
// things -- but it is not called out, so a document can show what several
// spans of time did to it without showing the document once per span.
function diff_from_runs(text, runs) {
    // Code points and utf-16 units count the same unless a surrogate pair is
    // in the way, and asking costs far less than spreading the string to find
    // out. One version span of a long document usually touches a line of it,
    // so taking the whole thing apart to mark up that line is nearly all waste.
    let paired = /[\uD800-\uDBFF]/.test(text)
    let cps = paired ? [...text] : null
    let len = paired ? cps.length : text.length
    let cut = (from, to) => paired ? cps.slice(from, to).join('')
                                   : text.slice(from, to)

    let all = []
    for (let run of runs) for (let xf of run.ops) all.push(xf)
    let [lo, hi] = touched_range(len, all)

    // Only the stretch the operations reach becomes a cell per character:
    // one recording that it was inserted, and what was deleted just after it.
    //   { c, ins, gone: [[text, agent], ...] }
    // Iterated rather than cut and spread again, and handed the whole string
    // when the window is the whole string, so a span that really does reach
    // everything pays nothing for having been measured.
    let a = []
    for (let c of paired ? cps.slice(lo, hi)
                : lo === 0 && hi === len ? text : text.slice(lo, hi))
        a.push({ c, ins: null, gone: null })
    let far_left = []

    for (let run of runs) for (let xf of run.ops) {
        let start = xf.start - lo
        if (xf.kind == "Ins") {
            // Moved a piece at a time rather than spliced in: handing splice a
            // document's worth of characters as an argument list overflows the
            // stack, and an operation that writes a whole document is exactly
            // what a snapshot of one turns into.
            let tail = a.splice(start, a.length - start)
            // What an unmarked run wrote is simply text that is there: it is
            // in the document, and nobody being asked about put it there.
            for (let c of xf.content)
                a.push({ c, ins: run.marked ? xf.agent : null, gone: null })
            for (let cell of tail) a.push(cell)
        } else if (xf.kind == "Del") {
            let removed = a.splice(start, xf.end - xf.start)
            let landing = []
            if (run.marked) {
                // Whatever those cells held, plus anything already deleted
                // after them, is now deleted by this operation's author.
                let text = removed.map(x => x.c + (x.gone || []).map(y => y[0]).join('')).join('')
                if (text) landing.push([text, xf.agent])
            } else {
                // A deletion nobody asked about is not worth calling out, but
                // it must not carry a selected span's work off the screen with
                // it. What those spans wrote stays, struck through and still in
                // the colour of whoever wrote it, and so does what they struck.
                // Text nobody selected ever touched simply goes.
                for (let x of removed) {
                    if (x.ins) landing.push([x.c, x.ins])
                    for (let y of x.gone || []) landing.push(y)
                }
            }
            if (!landing.length) continue
            // Only a deletion at the very front of the document has no cell to
            // hang itself on, and that one forces the window open to 0
            if (xf.start == 0) far_left.push(...landing)
            else {
                let prev = a[start - 1]
                if (!prev.gone) prev.gone = []
                prev.gone.push(...landing)
            }
        }
    }

    // Runs of the same kind by the same author collapse into one entry, so
    // the reader gets whole words rather than a span per character. The two
    // untouched stretches go through the same merge, so a seam between one of
    // them and the marked-up middle leaves no seam in the output.
    let diff = []
    let push = (what, text, agent) => {
        if (!text) return
        let last = diff[diff.length - 1]
        if (last && last[0] === what && last[2] === agent) last[1] += text
        else diff.push([what, text, agent])
    }
    push(0, cut(0, lo), null)
    for (let [text, agent] of far_left) push(-1, text, agent)
    for (let cell of a) {
        push(cell.ins ? 1 : 0, cell.c, cell.ins)
        for (let [text, agent] of cell.gone || []) push(-1, text, agent)
    }
    push(0, cut(hi, len), null)
    return diff
}

// What changed between two versions: the text as it stood at `from`, marked up
// with everything the operations between them did to it. Leaving `to` out asks
// about the present, which is what a lone version means.
function dt_diff_from(doc, from, to) {
    // The document answers all of this itself; this used to rebuild a second
    // copy to ask it.
    let lv = doc.remoteToLocalVersion(from)
    return diff_from_ops(doc.getStringAt(lv),
        to ? doc.xfBetween(lv, doc.remoteToLocalVersion(to)) : doc.xfSince(lv))
}

// What several spans of history did, all shown in the one document. The
// document starts where the earliest span does and is played forward through
// everything up to the end of the latest, so the changes in between are there
// too -- they are what puts the later spans where they belong -- just not
// called out.
function dt_diff_spans(doc, spans) {
    if (!spans?.length) return null
    let lv = v => doc.remoteToLocalVersion(v)
    let base = lv(spans[0].from_version)
    let text = doc.getStringAt(base)

    let runs = []
    let at = base
    for (let s of spans) {
        let from = lv(s.from_version), to = lv(s.to_version)
        // Two spans can sit on branches that never saw each other, and asking
        // across them lands on the merge rather than on the second one alone.
        // The running point has to take that merge in, or the next stretch
        // hands back work already done.
        let gap = doc.xfBetween(at, from)
        if (gap.length) runs.push({ ops: gap, marked: false })
        at = doc.mergeVersions(at, from)

        runs.push({ ops: doc.xfBetween(at, to), marked: true })
        at = doc.mergeVersions(at, to)
    }
    return diff_from_runs(text, runs)
}

// A code-point offset said as a utf-16 one, for slicing a JS string with
function cp_to_units(s, at) {
    if (!/[\uD800-\uDBFF]/.test(s)) return at
    let i = 0, n = 0
    while (n < at && i < s.length) { i += s.codePointAt(i) > 0xffff ? 2 : 1; n++ }
    return i
}

// Where a place in what the diff view shows sits in the document that diff
// ends at. Text struck through is on the screen but not in that document, so
// it counts towards one of these and not the other. A place inside struck
// text is the place it was taken from.
function shown_to_document(runs, at, show_deletions) {
    let shown = 0, real = 0
    for (let [what, text] of runs) {
        if (!text || (what === -1 && !show_deletions)) continue
        let n = cp_length(text)
        if (what === -1) {
            if (at < shown + n) return real
            shown += n
        } else {
            if (at < shown + n) return real + (at - shown)
            shown += n
            real += n
        }
    }
    return real
}

// Where a place in the document at some version has ended up in the document
// as it stands now. Writing before it pushes it along, deleting before it
// pulls it back, and a deletion that swallowed it leaves it at the near edge
// of the hole it left.
function xf_position(doc, version, at) {
    for (let xf of doc.xfSince(doc.remoteToLocalVersion(version))) {
        if (xf.kind == "Ins") {
            if (xf.start <= at) at += cp_length(xf.content)
        } else if (xf.kind == "Del") {
            if (xf.end <= at) at -= xf.end - xf.start
            else if (xf.start < at) at = xf.start
        }
    }
    return at
}

function encode_version(agent, seq) {
    return agent + "-" + seq
}

function decode_version(v) {
    let m = v.match(/^(.*)-(\d+)$/s)
    if (!m) throw new Error(`invalid actor-seq version: ${v}`)
    return [m[1], parseInt(m[2])]
}