Operational Transform (Text)

Operational transformation (OT) keeps people editing the same document in sync by rewriting each incoming edit's positions to account for edits made at the same time, so every copy of the document converges to identical text. When two users edit concurrently, both operations were written against the same starting text — but the moment one is applied, the other's positions are stale. operationalTransformText() builds the two primitives an OT engine needs: apply, which runs one operation, and transform, which rewrites an operation so it still means the right thing after a concurrent operation has already landed.

Signature

type Op =
  | { type: "insert"; pos: number; text: string }
  | { type: "delete"; pos: number; length: number };

// `side` breaks the tie when two inserts target the same position.
function operationalTransformText(): {
  apply(text: string, op: Op): string;
  transform(op1: Op, op2: Op, side: "left" | "right"): Op;
};

Examples

const { apply, transform } = operationalTransformText();

apply('helloworld', { type: 'insert', pos: 5, text: ' ' });
// -> 'hello world'

apply('hello world', { type: 'delete', pos: 5, length: 1 });
// -> 'helloworld'

// Base 'XY'. Two people insert at position 1 at the same time.
const a = { type: 'insert', pos: 1, text: 'A' };
const b = { type: 'insert', pos: 1, text: 'B' };

// Replica 1 applied a, then receives b (transform b past a, side 'right'):
apply(apply('XY', a), transform(b, a, 'right')); // -> 'XABY'

// Replica 2 applied b, then receives a (transform a past b, side 'left'):
apply(apply('XY', b), transform(a, b, 'left'));  // -> 'XABY'  (same result)

Notes

• Two concurrent ops share a base — op1 and op2 were both written against the same text. transform(op1, op2, side) rewrites op1 so it can run correctly after op2 has been applied.
• TP1 is the contract — apply(apply(t, a), transform(b, a, side)) must equal apply(apply(t, b), transform(a, b, otherSide)). Two replicas apply the same pair in opposite orders and still have to match, character for character.
• side is the tiebreak for equal insert positions — pass opposite sides on the two replicas so exactly one of the two colliding inserts shifts. Anywhere else, side is ignored.
• Half-open deletes — a delete at pos of length L removes the characters in the range [pos, pos + L). Positions are zero-based: pos 0 is before the first character, pos === text.length is after the last.
• Don't worry about — validating ops, undo, or transforming one op against a whole sequence of concurrent ops (that needs the harder TP2 property — see Going further). Each transform call rewrites against exactly one concurrent op.