Slate operation composition

compose.test.ts

import { Operation } from 'slate'
import { composeOperations } from './compose'

function testComposition(operations: Operation[], expected: Operation[]) {
  expect(composeOperations([], operations)).toEqual(expected)
}

const path = [0, 0]
describe('Inserting text', () => {
  test('Inserting consecutive text composes them to a single operation', () => {
    testComposition(
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jam',
          path,
        },
        {
          type: 'insert_text',
          offset: 3,
          text: 'ie',
          path,
        },
      ],
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jamie',
          path,
        },
      ]
    )
  })

  test('Inserting text after deleting the same text removes the previous operation', () => {
    testComposition(
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jam',
          path,
        },
        {
          type: 'remove_text',
          offset: 2,
          text: 'm',
          path,
        },
        {
          type: 'insert_text',
          offset: 2,
          text: 'mie',
          path,
        },
      ],
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jamie',
          path,
        },
      ]
    )
  })

  test('Removing text then inserting the same text at a later offset should not be composed', () => {
    testComposition(
      [
        // Assuming a base of "Jamei"
        {
          type: 'remove_text',
          offset: 3,
          text: 'e',
          path,
        },
        {
          type: 'insert_text',
          offset: 4,
          text: 'e',
          path,
        },
      ],
      [
        {
          type: 'remove_text',
          offset: 3,
          text: 'e',
          path,
        },
        {
          type: 'insert_text',
          offset: 4,
          text: 'e',
          path,
        },
      ]
    )
  })

  test('Removing text then reinserting the same text plus more text should not crash', () => {
    testComposition(
      [
        // Assuming a base of "Jam"
        {
          type: 'remove_text',
          offset: 2,
          text: 'm',
          path,
        },
        {
          type: 'insert_text',
          offset: 2,
          text: 'm',
          path,
        },
        {
          type: 'insert_text',
          offset: 3,
          text: 'i',
          path,
        },
        {
          type: 'insert_text',
          offset: 4,
          text: 'e',
          path,
        },
      ],
      [
        {
          type: 'insert_text',
          offset: 3,
          text: 'ie',
          path,
        },
      ]
    )
  })

  test('Removing text then inserting the same text at an earlier offset should not be composed', () => {
    testComposition(
      [
        // Assuming a base of "Jamei"
        {
          type: 'remove_text',
          offset: 4,
          text: 'i',
          path,
        },
        {
          type: 'insert_text',
          offset: 3,
          text: 'i',
          path,
        },
      ],
      [
        {
          type: 'remove_text',
          offset: 4,
          text: 'i',
          path,
        },
        {
          type: 'insert_text',
          offset: 3,
          text: 'i',
          path,
        },
      ]
    )
  })

  test('Inserting non-consecutive text at the head then the tail should be composed', () => {
    testComposition(
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Tal',
          path,
        },
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jamie ',
          path,
        },
        {
          type: 'insert_text',
          offset: 9,
          text: 'bot',
          path,
        },
      ],
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jamie Talbot',
          path,
        },
      ]
    )
  })

  test('Inserting text at the tail then the head should be composed', () => {
    testComposition(
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Tal',
          path,
        },
        {
          type: 'insert_text',
          offset: 3,
          text: 'bot',
          path,
        },
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jamie ',
          path,
        },
      ],
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jamie Talbot',
          path,
        },
      ]
    )
  })

  test('Inserting non-consecutive text at different offsets should not be composed', () => {
    testComposition(
      [
        // Assuming a base of "Jmi"
        {
          type: 'insert_text',
          offset: 1,
          text: 'a',
          path,
        },
        {
          type: 'insert_text',
          offset: 4,
          text: 'e',
          path,
        },
      ],
      [
        {
          type: 'insert_text',
          offset: 1,
          text: 'a',
          path,
        },
        {
          type: 'insert_text',
          offset: 4,
          text: 'e',
          path,
        },
      ]
    )
  })

  test('Inserting non-consecutive text at the correct offset but in different paths should not be composed', () => {
    testComposition(
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jam',
          path,
        },
        {
          type: 'insert_text',
          offset: 3,
          text: 'ie',
          path: [1, 0],
        },
      ],
      [
        {
          type: 'insert_text',
          offset: 0,
          text: 'Jam',
          path,
        },
        {
          type: 'insert_text',
          offset: 3,
          text: 'ie',
          path: [1, 0],
        },
      ]
    )
  })

  test('Removing consecutive text composes them to a single operation', () => {
    testComposition(
      [
        // Assuming a base of "Jamie"
        {
          type: 'remove_text',
          offset: 3,
          text: 'ie',
          path,
        },
        {
          type: 'remove_text',
          offset: 2,
          text: 'm',
          path,
        },
      ],
      [
        {
          type: 'remove_text',
          offset: 2,
          text: 'mie',
          path,
        },
      ]
    )
  })

  test('Removing text at non-consecutive offsets should not be composed', () => {
    testComposition(
      [
        // Assuming a base of "Jamie"
        {
          type: 'remove_text',
          offset: 3,
          text: 'ie',
          path,
        },
        {
          type: 'remove_text',
          offset: 1,
          text: 'a',
          path,
        },
      ],
      [
        {
          type: 'remove_text',
          offset: 3,
          text: 'ie',
          path,
        },
        {
          type: 'remove_text',
          offset: 1,
          text: 'a',
          path,
        },
      ]
    )
  })
  test('Removing text at the correct offset but in different paths should not be composed', () => {
    testComposition(
      [
        // Assuming a base of "Jamie"
        {
          type: 'remove_text',
          offset: 3,
          text: 'ie',
          path,
        },
        {
          type: 'remove_text',
          offset: 2,
          text: 'm',
          path: [1, 0],
        },
      ],
      [
        {
          type: 'remove_text',
          offset: 3,
          text: 'ie',
          path,
        },
        {
          type: 'remove_text',
          offset: 2,
          text: 'm',
          path: [1, 0],
        },
      ]
    )
  })
})

compose.ts

import { InsertTextOperation, Operation, Path, RemoveTextOperation } from 'slate'

const isInsertTextOperation = (operation: Operation): operation is InsertTextOperation => {
  return operation.type === 'insert_text'
}

const isRemoveTextOperation = (operation: Operation): operation is RemoveTextOperation => {
  return operation.type === 'remove_text'
}

const composeInsertTextOperation = (
  operations: Operation[],
  operation: InsertTextOperation
): Operation[] => {
  const lastOperation = operations[operations.length - 1]
  if (!Path.equals(lastOperation.path as Path, operation.path)) {
    // Can't merge if the paths differ
    return operations.concat(operation)
  }

  if (isInsertTextOperation(lastOperation)) {
    // Append text from current operation into previous operation.
    if (lastOperation.offset > operation.offset) {
      // For example: "mi" -> "mie" -> "Jamie" should lead to:
      // [{ offset: 2, text: "e" }, { offset: 0, text: "Ja" }]
      // This can't be merged
      return operations.concat(operation)
    }

    if (lastOperation.offset === operation.offset) {
      // For example: "Jae" -> "Jaie" -> "Jamie"
      operations[operations.length - 1].text = `${operation.text}${lastOperation.text}`
      return operations
    }

    if (lastOperation.offset + lastOperation.text.length !== operation.offset) {
      // We can't merge if it doesn't immediately follow the previous insertion.
      return operations.concat(operation)
    }

    const relativeOffset = operation.offset - lastOperation.offset
    const before = lastOperation.text.slice(0, relativeOffset)
    const after = lastOperation.text.slice(relativeOffset)
    operations[operations.length - 1] = {
      ...lastOperation,
      text: `${before}${operation.text}${after}`,
    }
    return operations
  }

  if (isRemoveTextOperation(lastOperation)) {
    if (!lastOperation.text.startsWith(operation.text)) {
      // Can't merge if we're adding different text to that which was previously removed.
      return operations.concat(operation)
    }

    if (lastOperation.offset !== operation.offset) {
      // Can't merge if we're replacing text in a different location.
      return operations.concat(operation)
    }

    if (lastOperation.text.length === operation.text.length) {
      // If the texts are the same length, we just remove the last operation.
      return operations.slice(0, -1)
    }

    // Modify the removal so it doesn't include this inserted text.
    operations[operations.length - 1] = {
      ...lastOperation,
      text: lastOperation.text.substring(operation.text.length),
      offset: lastOperation.offset + operation.text.length,
    }
    return operations
  }
  return operations.concat(operation)
}

function composeRemoveTextOperation(
  operations: Operation[],
  operation: RemoveTextOperation
): Operation[] {
  const lastOperation = operations[operations.length - 1]
  if (!Path.equals(lastOperation.path as Path, operation.path)) {
    // Can't merge if the paths differ
    return operations.concat(operation)
  }

  if (isRemoveTextOperation(lastOperation)) {
    if (operation.offset > lastOperation.offset) {
      // For example: "Jamie" -> "mie" -> "mi" should lead to:
      // [{ offset: 0, text: "Ja" }, { offset: 2, text "e" }]
      // This can't be merged
      return operations.concat(operation)
    }

    if (operation.offset + operation.text.length !== lastOperation.offset) {
      // We can't easily merge an operation where it's non-consecutive.
      // TODO(jamie) We could potentially look further back and merge consecutive
      // removals, if we're removing the part in between. For example:
      // "Jamie" -> "Jmie" -> "Jme" -> "Je".
      // This does not seem like a case to worry about for now though.
      return operations.concat(operation)
    }

    if (operation.offset === lastOperation.offset) {
      // For example: "Jamie" -> "Jmie" -> "Jie" should lead to: [{ offset: 1, text: "am" }]
      operations[operations.length - 1].text = `${lastOperation.text}${operation.text}`
      return operations
    }
    // For example: "Jamie" -> "Jam" -> "J" should lead to: [{ offset: 1, text: "amie" }]
    operations[operations.length - 1] = {
      ...lastOperation,
      offset: lastOperation.offset - operation.text.length,
      text: `${operation.text}${lastOperation.text}`,
    }
    return operations
  }

  if (isInsertTextOperation(lastOperation)) {
    if (!lastOperation.text.endsWith(operation.text)) {
      // It shouldn't technically be possible to remove a character that is different
      // from the last inserted character, but just in case.
      return operations.concat(operation)
    }

    if (lastOperation.text === operation.text) {
      return operations.slice(0, -1)
    }

    operations[operations.length - 1].text = lastOperation.text.substr(
      0,
      lastOperation.text.length - operation.text.length
    )
    return operations
  }

  return operations.concat(operation)
}

/**
 * Merges operations into the buffer as much as possible, returning operations
 * that could not be merged.
 */
function composeOperations(operations: Operation[], newOperations: Operation[]): Operation[] {
  if (!newOperations.length) return operations
  if (!operations.length) {
    // If this is the first set of operations, push the first operation
    // and then iterate the rest so that they get compressed.
    const op = newOperations.shift()
    if (op) {
      operations.push(op)
    }
  }

  newOperations.forEach((operation) => {
    if (!operations.length) {
      // This can happen if we did a removal, followed by an insertion, or vice versa,
      // causing the operation to be removed.
      operations.push(operation)
      return
    }
    if (isInsertTextOperation(operation)) {
      operations = composeInsertTextOperation(operations, operation)
    } else if (isRemoveTextOperation(operation)) {
      operations = composeRemoveTextOperation(operations, operation)
    } else {
      operations.push(operation)
    }
  })

  return operations
}

export { composeOperations }