307 lines
13 KiB
JavaScript
307 lines
13 KiB
JavaScript
/*
|
|
* Copyright (C) 2026 Mateusz Gruszczynski @linuxiarz.pl
|
|
* Source-Available Code / Dual-Licensed.
|
|
*
|
|
* Free for non-commercial and evaluation use under terms of BSL/GPLv3.
|
|
* Commercial or production use requires a valid paid license.
|
|
* See LICENSE file in repository root for details.
|
|
*/
|
|
|
|
import { parseAuthorship, serializeAuthorship } from "@rustpad/authorship";
|
|
|
|
function normalizeOwnerSpans(spans, length) {
|
|
const result = [];
|
|
const sorted = [...(Array.isArray(spans) ? spans : [])].sort((left, right) => (Number(left?.start) || 0) - (Number(right?.start) || 0) || (Number(left?.end) || 0) - (Number(right?.end) || 0));
|
|
for (const source of sorted) {
|
|
const start = Math.max(0, Math.min(length, Number(source?.start) || 0));
|
|
const end = Math.max(start, Math.min(length, Number(source?.end) || 0));
|
|
const owner = String(source?.owner || "");
|
|
if (!owner || end <= start) continue;
|
|
const previous = result.at(-1);
|
|
if (previous && previous.owner === owner && start <= previous.end) {
|
|
previous.end = Math.max(previous.end, end);
|
|
continue;
|
|
}
|
|
const clippedStart = previous && start < previous.end ? previous.end : start;
|
|
if (end > clippedStart) result.push({ start: clippedStart, end, owner });
|
|
}
|
|
return result;
|
|
}
|
|
|
|
function sliceOwnerSpans(spans, start, length) {
|
|
const end = start + length;
|
|
return normalizeOwnerSpans((spans || []).flatMap(span => {
|
|
const overlapStart = Math.max(start, span.start);
|
|
const overlapEnd = Math.min(end, span.end);
|
|
return overlapEnd > overlapStart
|
|
? [{ start: overlapStart - start, end: overlapEnd - start, owner: span.owner }]
|
|
: [];
|
|
}), length);
|
|
}
|
|
|
|
function shiftOwnerSpans(spans, offset) {
|
|
return (spans || []).map(span => ({ start: span.start + offset, end: span.end + offset, owner: span.owner }));
|
|
}
|
|
|
|
function appendComponent(components, component) {
|
|
if (!component) return;
|
|
if (component.kind === "retain" || component.kind === "delete") {
|
|
const count = Number(component.count) || 0;
|
|
if (count <= 0) return;
|
|
const previous = components.at(-1);
|
|
if (previous?.kind === component.kind) previous.count += count;
|
|
else components.push({ kind: component.kind, count });
|
|
return;
|
|
}
|
|
if (component.kind !== "insert") throw new Error("Unknown operation component");
|
|
const text = String(component.text || "");
|
|
if (!text) return;
|
|
const owners = normalizeOwnerSpans(component.owners, text.length);
|
|
const previous = components.at(-1);
|
|
if (previous?.kind === "insert") {
|
|
const offset = previous.text.length;
|
|
previous.text += text;
|
|
previous.owners = normalizeOwnerSpans([
|
|
...(previous.owners || []),
|
|
...shiftOwnerSpans(owners, offset),
|
|
], previous.text.length);
|
|
} else components.push({ kind: "insert", text, owners });
|
|
}
|
|
|
|
export function normalizeOperation(operation) {
|
|
const components = [];
|
|
for (const component of operation?.components || []) appendComponent(components, component);
|
|
return { components };
|
|
}
|
|
|
|
export function operationBaseLength(operation) {
|
|
return normalizeOperation(operation).components.reduce((length, component) =>
|
|
length + (component.kind === "retain" || component.kind === "delete" ? component.count : 0), 0);
|
|
}
|
|
|
|
export function operationTargetLength(operation) {
|
|
return normalizeOperation(operation).components.reduce((length, component) =>
|
|
length + (component.kind === "retain" ? component.count : component.kind === "insert" ? component.text.length : 0), 0);
|
|
}
|
|
|
|
export function identityOperation(length) {
|
|
return normalizeOperation({ components: length > 0 ? [{ kind: "retain", count: length }] : [] });
|
|
}
|
|
|
|
function isUtf16Boundary(value, offset) {
|
|
if (offset <= 0 || offset >= value.length) return true;
|
|
const previous = value.charCodeAt(offset - 1);
|
|
const next = value.charCodeAt(offset);
|
|
return !(previous >= 0xd800 && previous <= 0xdbff && next >= 0xdc00 && next <= 0xdfff);
|
|
}
|
|
|
|
export function operationFromEdit(previousText, nextText, nextAuthorship) {
|
|
previousText = String(previousText || "");
|
|
nextText = String(nextText || "");
|
|
let prefix = 0;
|
|
const shared = Math.min(previousText.length, nextText.length);
|
|
while (prefix < shared && previousText.charCodeAt(prefix) === nextText.charCodeAt(prefix)) prefix++;
|
|
while (prefix > 0 && (!isUtf16Boundary(previousText, prefix) || !isUtf16Boundary(nextText, prefix))) prefix--;
|
|
|
|
let oldSuffix = previousText.length;
|
|
let newSuffix = nextText.length;
|
|
while (oldSuffix > prefix && newSuffix > prefix && previousText.charCodeAt(oldSuffix - 1) === nextText.charCodeAt(newSuffix - 1)) {
|
|
oldSuffix--;
|
|
newSuffix--;
|
|
}
|
|
while (!isUtf16Boundary(previousText, oldSuffix) || !isUtf16Boundary(nextText, newSuffix)) {
|
|
oldSuffix++;
|
|
newSuffix++;
|
|
}
|
|
|
|
const components = [];
|
|
appendComponent(components, { kind: "retain", count: prefix });
|
|
appendComponent(components, { kind: "delete", count: oldSuffix - prefix });
|
|
const insertedText = nextText.slice(prefix, newSuffix);
|
|
appendComponent(components, {
|
|
kind: "insert",
|
|
text: insertedText,
|
|
owners: sliceOwnerSpans(nextAuthorship?.spans || [], prefix, insertedText.length),
|
|
});
|
|
appendComponent(components, { kind: "retain", count: previousText.length - oldSuffix });
|
|
return { components };
|
|
}
|
|
|
|
class OperationCursor {
|
|
constructor(operation) {
|
|
this.components = normalizeOperation(operation).components;
|
|
this.index = 0;
|
|
this.offset = 0;
|
|
}
|
|
|
|
get current() { return this.components[this.index] || null; }
|
|
get kind() { return this.current?.kind || null; }
|
|
get remaining() {
|
|
const component = this.current;
|
|
if (!component) return 0;
|
|
return (component.kind === "insert" ? component.text.length : component.count) - this.offset;
|
|
}
|
|
|
|
take(count = this.remaining) {
|
|
const component = this.current;
|
|
if (!component || count <= 0 || count > this.remaining) throw new Error("Invalid operation cursor read");
|
|
let part;
|
|
if (component.kind === "insert") {
|
|
part = {
|
|
kind: "insert",
|
|
text: component.text.slice(this.offset, this.offset + count),
|
|
owners: sliceOwnerSpans(component.owners, this.offset, count),
|
|
};
|
|
} else part = { kind: component.kind, count };
|
|
this.offset += count;
|
|
if (this.offset === (component.kind === "insert" ? component.text.length : component.count)) {
|
|
this.index++;
|
|
this.offset = 0;
|
|
}
|
|
return part;
|
|
}
|
|
}
|
|
|
|
export function composeOperations(first, second) {
|
|
first = normalizeOperation(first);
|
|
second = normalizeOperation(second);
|
|
if (operationTargetLength(first) !== operationBaseLength(second)) throw new Error("Cannot compose operations with different lengths");
|
|
const left = new OperationCursor(first);
|
|
const right = new OperationCursor(second);
|
|
const components = [];
|
|
|
|
while (left.current || right.current) {
|
|
if (right.kind === "insert") {
|
|
appendComponent(components, right.take());
|
|
continue;
|
|
}
|
|
if (left.kind === "delete") {
|
|
appendComponent(components, left.take());
|
|
continue;
|
|
}
|
|
if (!left.current || !right.current) throw new Error("Incomplete operation composition");
|
|
const count = Math.min(left.remaining, right.remaining);
|
|
const leftKind = left.kind;
|
|
const rightKind = right.kind;
|
|
if (leftKind === "retain" && rightKind === "retain") {
|
|
appendComponent(components, { kind: "retain", count });
|
|
left.take(count);
|
|
right.take(count);
|
|
} else if (leftKind === "retain" && rightKind === "delete") {
|
|
appendComponent(components, { kind: "delete", count });
|
|
left.take(count);
|
|
right.take(count);
|
|
} else if (leftKind === "insert" && rightKind === "retain") {
|
|
appendComponent(components, left.take(count));
|
|
right.take(count);
|
|
} else if (leftKind === "insert" && rightKind === "delete") {
|
|
left.take(count);
|
|
right.take(count);
|
|
} else throw new Error("Unsupported operation composition");
|
|
}
|
|
return { components };
|
|
}
|
|
|
|
export function transformOperations(leftOperation, rightOperation, leftBeforeRight = true) {
|
|
leftOperation = normalizeOperation(leftOperation);
|
|
rightOperation = normalizeOperation(rightOperation);
|
|
if (operationBaseLength(leftOperation) !== operationBaseLength(rightOperation)) throw new Error("Cannot transform operations with different base lengths");
|
|
const left = new OperationCursor(leftOperation);
|
|
const right = new OperationCursor(rightOperation);
|
|
const leftPrime = [];
|
|
const rightPrime = [];
|
|
|
|
while (left.current || right.current) {
|
|
if (left.kind === "insert" && (right.kind !== "insert" || leftBeforeRight)) {
|
|
const part = left.take();
|
|
appendComponent(leftPrime, part);
|
|
appendComponent(rightPrime, { kind: "retain", count: part.text.length });
|
|
continue;
|
|
}
|
|
if (right.kind === "insert") {
|
|
const part = right.take();
|
|
appendComponent(leftPrime, { kind: "retain", count: part.text.length });
|
|
appendComponent(rightPrime, part);
|
|
continue;
|
|
}
|
|
if (!left.current || !right.current) throw new Error("Incomplete operation transform");
|
|
const count = Math.min(left.remaining, right.remaining);
|
|
if (left.kind === "retain" && right.kind === "retain") {
|
|
appendComponent(leftPrime, { kind: "retain", count });
|
|
appendComponent(rightPrime, { kind: "retain", count });
|
|
} else if (left.kind === "delete" && right.kind === "retain") {
|
|
appendComponent(leftPrime, { kind: "delete", count });
|
|
} else if (left.kind === "retain" && right.kind === "delete") {
|
|
appendComponent(rightPrime, { kind: "delete", count });
|
|
} else if (left.kind !== "delete" || right.kind !== "delete") throw new Error("Unsupported operation transform");
|
|
left.take(count);
|
|
right.take(count);
|
|
}
|
|
return [{ components: leftPrime }, { components: rightPrime }];
|
|
}
|
|
|
|
function copyRetainedSpans(target, spans, sourceStart, length, outputStart) {
|
|
const sourceEnd = sourceStart + length;
|
|
for (const span of spans || []) {
|
|
const start = Math.max(sourceStart, span.start);
|
|
const end = Math.min(sourceEnd, span.end);
|
|
if (end > start) target.push({ start: outputStart + start - sourceStart, end: outputStart + end - sourceStart, owner: span.owner });
|
|
}
|
|
}
|
|
|
|
export function applyOperationToDocument(content, ownerMap, operation, ownerReplacements = []) {
|
|
content = String(content || "");
|
|
operation = normalizeOperation(operation);
|
|
if (operationBaseLength(operation) !== content.length) throw new Error("Operation base length does not match document");
|
|
const sourceModel = parseAuthorship(content, ownerMap);
|
|
const outputSpans = [];
|
|
let sourceOffset = 0;
|
|
let outputOffset = 0;
|
|
let nextContent = "";
|
|
for (const component of operation.components) {
|
|
if (component.kind === "retain") {
|
|
nextContent += content.slice(sourceOffset, sourceOffset + component.count);
|
|
copyRetainedSpans(outputSpans, sourceModel.spans, sourceOffset, component.count, outputOffset);
|
|
sourceOffset += component.count;
|
|
outputOffset += component.count;
|
|
} else if (component.kind === "delete") sourceOffset += component.count;
|
|
else {
|
|
nextContent += component.text;
|
|
outputSpans.push(...shiftOwnerSpans(component.owners, outputOffset));
|
|
outputOffset += component.text.length;
|
|
}
|
|
}
|
|
if (sourceOffset !== content.length) throw new Error("Operation did not consume the whole document");
|
|
const replacementMap = new Map((ownerReplacements || []).map(item => [String(item?.owner || ""), String(item?.replacement || "")]));
|
|
const replacedSpans = outputSpans.map(span => {
|
|
const identity = String(span.owner || "").split("\u001f", 1)[0];
|
|
const replacement = replacementMap.get(identity);
|
|
return replacement ? { ...span, owner: replacement } : span;
|
|
});
|
|
const model = { version: 2, spans: normalizeOwnerSpans(replacedSpans, nextContent.length) };
|
|
return { content: nextContent, ownerMap: serializeAuthorship(model, nextContent.length), authorship: model };
|
|
}
|
|
|
|
export function compareOperationKeys(left, right) {
|
|
const leftClient = String(left?.clientId || left?.client_id || "");
|
|
const rightClient = String(right?.clientId || right?.client_id || "");
|
|
if (leftClient !== rightClient) return leftClient < rightClient ? -1 : 1;
|
|
const leftUpdate = Number(left?.updateId ?? left?.update_id ?? 0);
|
|
const rightUpdate = Number(right?.updateId ?? right?.update_id ?? 0);
|
|
return leftUpdate === rightUpdate ? 0 : leftUpdate < rightUpdate ? -1 : 1;
|
|
}
|
|
|
|
export function documentAfterPending(serverContent, serverOwnerMap, outstanding, buffer) {
|
|
let documentState = { content: serverContent, ownerMap: serverOwnerMap };
|
|
for (const pending of [outstanding, buffer]) {
|
|
if (!pending) continue;
|
|
documentState = applyOperationToDocument(
|
|
documentState.content,
|
|
documentState.ownerMap,
|
|
pending.operation,
|
|
pending.ownerReplacements,
|
|
);
|
|
}
|
|
return documentState;
|
|
}
|