yjs-minimal.ts

// This implements the core algorithm of Yjs, but with some tweaks in about 100 lines.
// This is a toy and it probably still has some small bugs.

import assert from 'assert/strict'

type Id = {
  agent: string,
  seq: number,
}

type Item<T> = {
  content: T,
  id: Id,

  // Left and right implicit in document list.
  // null represents document's root / end.
  originLeft: Id | null,
  originRight: Id | null,

  isDeleted: boolean,
}

interface Doc<T = string> {
  content: Item<T>[]
  version: Record<string, number> // agent => last seen seq.
}

const idEq = (a: Id | null, b: Id | null): boolean => (
  a === b || (a != null && b != null && a.agent === b.agent && a.seq === b.seq)
)

const findItem = <T>(doc: Doc<T>, needle: Id | null): number => {
  if (needle == null) return -1
  else {
    const idx = doc.content.findIndex(({id}) => idEq(id, needle))
    if (idx < 0) throw Error('Could not find item') // Could use a ternary if not for this!
    return idx
  }
}

const integrate = <T>(doc: Doc<T>, newItem: Item<T>) => {
  const lastSeen = doc.version[newItem.id.agent] ?? -1
  if (newItem.id.seq !== lastSeen + 1) throw Error('Operations out of order')
  doc.version[newItem.id.agent] = newItem.id.seq

  let left = findItem(doc, newItem.originLeft)
  let destIdx = left + 1
  let right = newItem.originRight == null ? doc.content.length : findItem(doc, newItem.originRight)
  let conflictStart = -1

  const startConflict = (i: number) => conflictStart = i
  const resetConflict = () => conflictStart = -1

  for (let i = destIdx; ; i++) {
    // Inserting at the end of the document. Just insert.
    if (conflictStart === -1) destIdx = i
    if (i === doc.content.length) break
    if (i === right) break // No ambiguity / concurrency. Insert here.

    let o = doc.content[i]

    let oleft = findItem(doc, o.originLeft)
    let oright = o.originRight == null ? doc.content.length : findItem(doc, o.originRight)

    // Ok now we implement the punnet square of behaviour
    if (oleft < left) {
      // Top row. Insert, insert, arbitrary (insert)
      resetConflict()
      break
    } else if (oleft === left) {
      // Middle row.
      if (oright < right) {
        // This is tricky. We're looking at an item we *might* insert after - but we can't tell yet!
        startConflict(i)
        continue
      } else if (oright === right) {
        // Raw conflict. Order based on user agents
        // resetConflict()
        if (newItem.id.agent < o.id.agent) break
        else {
          resetConflict()
          continue
        }
      } else {
        // I'm not sure here - should we reset conflict?
        resetConflict()
        continue
      }
    } else {
      // Bottom row. Arbitrary (skip), skip, skip
      continue
    }
  }

  // We've found the position. Insert here.
  doc.content.splice(destIdx, 0, newItem)
}

const getNextSeq = <T>(doc: Doc<T>, agent: string): number => {
  const last = doc.version[agent]
  return last == null ? 0 : last + 1
}

const makeItemAt = <T>(doc: Doc<T>, pos: number, content: T, agent: string, seq?: number, originLeft?: Id | null, originRight?: Id | null): Item<T> => ({
  content,
  id: {agent, seq: seq ?? getNextSeq(doc, agent)},
  isDeleted: false,
  originLeft: originLeft ?? (pos === 0 ? null : doc.content[pos - 1].id),
  originRight: originRight ?? (pos >= doc.content.length ? null : doc.content[pos].id)
})

const getArray = <T>(doc: Doc<T>): T[] => (
  doc.content.map(i => i.content)
)



/// TESTS

;(() => { // Separate scope for namespace protection.

  const test = (fn: () => void) => {
    process.stdout.write(`running ${fn.name} ...`)
    fn()
    process.stdout.write(`PASS\n`)
  }

  const smoke = () => {
    const doc: Doc = {content: [], version: {}}
    integrate(doc, makeItemAt(doc, 0, 'a', 'A'))
    integrate(doc, makeItemAt(doc, 1, 'b', 'A'))

    // console.log(doc.content.map(x => x.content))
    // console.log(doc.content)
    assert.deepEqual(getArray(doc), ['a', 'b'])
  }

  const concurrentAvsB = () => {
    const doc: Doc = {content: [], version: {}}
    const a = makeItemAt(doc, 0, 'a', 'A', 0)
    const b = makeItemAt(doc, 0, 'b', 'B', 0)

    integrate(doc, a)
    integrate(doc, b)
    assert.deepEqual(getArray(doc), ['a', 'b'])

    const doc2: Doc = {content: [], version: {}}
    integrate(doc2, b)
    integrate(doc2, a)
    assert.deepEqual(getArray(doc2), ['a', 'b'])
  }

  const interleavingForward = () => {
    const doc: Doc = {content: [], version: {}}
    const as = [
      makeItemAt(doc, 0, 'a', 'A', 0),
      makeItemAt(doc, 1, 'a', 'A', 1, {agent: 'A', seq: 0}),
      makeItemAt(doc, 2, 'a', 'A', 2, {agent: 'A', seq: 1}),
    ]
    const bs = [
      makeItemAt(doc, 0, 'b', 'B', 0),
      makeItemAt(doc, 1, 'b', 'B', 1, {agent: 'B', seq: 0}),
      makeItemAt(doc, 2, 'b', 'B', 2, {agent: 'B', seq: 1}),
    ]

    as.forEach(item => integrate(doc, item))
    bs.forEach(item => integrate(doc, item))
    assert.deepEqual(getArray(doc), ['a', 'a', 'a', 'b', 'b', 'b'])

    // And with a different interleaving. It'd be better to play with more variants here.
    const doc2: Doc = {content: [], version: {}}
    bs.forEach(item => integrate(doc2, item))
    as.forEach(item => integrate(doc2, item))
    assert.deepEqual(getArray(doc2), ['a', 'a', 'a', 'b', 'b', 'b'])
  }

  const interleavingBackward = () => {
    const doc: Doc = {content: [], version: {}}
    const as = [
      makeItemAt(doc, 0, 'a', 'A', 0),
      makeItemAt(doc, 0, 'a', 'A', 1, null, {agent: 'A', seq: 0}),
      makeItemAt(doc, 0, 'a', 'A', 2, null, {agent: 'A', seq: 1}),
    ]
    const bs = [
      makeItemAt(doc, 0, 'b', 'B', 0),
      makeItemAt(doc, 0, 'b', 'B', 1, null, {agent: 'B', seq: 0}),
      makeItemAt(doc, 0, 'b', 'B', 2, null, {agent: 'B', seq: 1}),
    ]

    as.forEach(item => integrate(doc, item))
    bs.forEach(item => integrate(doc, item))
    assert.deepEqual(getArray(doc), ['a', 'a', 'a', 'b', 'b', 'b'])

    // And with a different interleaving. It'd be better to play with more variants here.
    const doc2: Doc = {content: [], version: {}}
    bs.forEach(item => integrate(doc2, item))
    as.forEach(item => integrate(doc2, item))
    assert.deepEqual(getArray(doc2), ['a', 'a', 'a', 'b', 'b', 'b'])
  }

  const withTails = () => {
    const doc: Doc = {content: [], version: {}}
    const as = [
      makeItemAt(doc, 0, 'a', 'A', 0),
      makeItemAt(doc, 0, 'a0', 'A', 1, null, {agent: 'A', seq: 0}), // left
      makeItemAt(doc, 2, 'a1', 'A', 2, {agent: 'A', seq: 0}), // right
    ]
    const bs = [
      makeItemAt(doc, 0, 'b', 'B', 0),
      makeItemAt(doc, 0, 'b0', 'B', 1, null, {agent: 'B', seq: 0}), // left
      makeItemAt(doc, 2, 'b1', 'B', 2, {agent: 'B', seq: 0}), // right
    ]

    as.forEach(item => integrate(doc, item))
    bs.forEach(item => integrate(doc, item))
    assert.deepEqual(getArray(doc), ['a0', 'a', 'a1', 'b0', 'b', 'b1'])

    // And with a different interleaving.
    const doc2: Doc = {content: [], version: {}}
    bs.forEach(item => integrate(doc2, item))
    as.forEach(item => integrate(doc2, item))
    assert.deepEqual(getArray(doc2), ['a0', 'a', 'a1', 'b0', 'b', 'b1'])
  }

  const localVsConcurrent = () => {
    // Check what happens when a top level concurrent change interacts
    // with a more localised change. (C vs D)
    const doc: Doc = {content: [], version: {}}
    const a = makeItemAt(doc, 0, 'a', 'A', 0)
    const c = makeItemAt(doc, 0, 'c', 'C', 0)

    // How do these two get ordered?
    const b = makeItemAt(doc, 0, 'b', 'B', 0) // Concurrent with a and c
    const d = makeItemAt(doc, 1, 'd', 'D', 0, {agent: 'A', seq: 0}, {agent: 'C', seq: 0}) // in between a and c

    integrate(doc, a)
    integrate(doc, c)
    integrate(doc, b)
    integrate(doc, d)
    assert.deepEqual(getArray(doc), ['a', 'd', 'b', 'c'])
  }

  const tests = [
    smoke,
    concurrentAvsB,
    interleavingForward,
    interleavingBackward,
    withTails,
    localVsConcurrent,
  ]
  tests.forEach(test)

})()