Agnostic keyed diff

diff-data.mjs

export const tests = [
  // 0
  {
    previous: ['A', 'B'],
    next: ['A', 'B', 'C'],
    expected: [
      { tag: 'skip', index: 0 },
      { tag: 'skip', index: 1 },
      { tag: 'insert', index: 2 },
    ]
  },
  // 1
  {
    previous: ['A', 'B'],
    next: ['C', 'A', 'B'],
    expected: [
      { tag: 'insert', index: 0 },
      { tag: 'skip', index: 1 },
      { tag: 'skip', index: 2 },
    ]
  },
  // 2
  {
    previous: ['A', 'B'],
    next: ['A', 'C', 'B'],
    expected: [
      { tag: 'skip', index: 0 },
      { tag: 'insert', index: 1 },
      { tag: 'skip', index: 2 },
    ]
  },
  // 3
  {
    previous: ['A', 'B', 'C'],
    next: ['A', 'B'],
    expected: [
      { tag: 'skip', index: 0 },
      { tag: 'skip', index: 1 },
      { tag: 'remove', index: 2 },
    ]
  },
  // 4
  {
    previous: ['A', 'B', 'C'],
    next: ['B', 'C'],
    expected: [
      { tag: 'remove', index: 0 },
      { tag: 'skip', index: 0 },
      { tag: 'skip', index: 1 },
    ]
  },
  // 5
  {
    previous: ['A', 'B', 'C'],
    next: ['C', 'A', 'B'],
    expected: [
      { tag: 'move', from: 2, to: 0 },
      { tag: 'skip', index: 1 },
      { tag: 'skip', index: 2 },
    ]
  },
  // 6
  {
    previous: ['A', 'B', 'C'],
    next: ['C', 'B', 'A'],
    expected: [
      { tag: 'move', from: 2, to: 0 },
      { tag: 'move', from: 2, to: 1 },
      { tag: 'skip', index: 2 },
    ]
  },
  // 7
  {
    previous: ['A', 'B', 'C', 'D'],
    next: ['D', 'B', 'C', 'A'],
    expected: [
      { tag: 'move', from: 3, to: 0 },
      { tag: 'move', from: 2, to: 1 },
      { tag: 'move', from: 3, to: 2 },
      { tag: 'skip', index: 3 },
    ]
  },
]

diff-dom.mjs

import { Window } from 'npm:happy-dom'
import { diff } from './diff.mjs'
import { tests } from './diff-data.mjs'
import { identity } from './diff-util.mjs'

const doc = new Window().document

const createList = (array) => {
  const list = doc.createElement('ul')
  for (const value of array) {
    const li = doc.createElement('li')
    li.textContent = value
    list.append(li)
  }
  return list
}

const patchList = (previous, next, key, list) => {
  const changes = diff(previous, next, identity)
  for (const { tag, index, from, to } of changes) {
    switch (tag) {
      case 'insert':
        const li = doc.createElement('li')
        li.textContent = next[index]
        list.insertBefore(li, list.children[index])
        break
      case 'remove':
        list.removeChild(list.children[index])
        break
      case 'move':
        list.insertBefore(
          list.children[from],
          list.children[to]
        )
        break
    }
  }
}

for (const [index, { previous, next }] of tests.entries()) {
  const previousList = createList(previous)
  const nextList = createList(next)
  patchList(previous, next, identity, previousList)
  if (previousList.innerHTML !== nextList.innerHTML) {
    console.log('INDEX', index)
    console.log('previous', previous)
    console.log('next', next)
    console.log('previousList', previousList.innerHTML)
    console.log('nextList', nextList.innerHTML)
    break
  }
}

diff-test.mjs

import { diff } from './diff.mjs'
import { tests } from './diff-data.mjs'
import { identity } from './diff-util.mjs'

for (const [index, { previous, next, expected }] of tests.entries()) {
  const actual = diff(previous, next, identity)
  if (JSON.stringify(actual) !== JSON.stringify(expected)) {
    console.log('INDEX', index)
    console.log('previous', previous)
    console.log('next', next)
    console.log('actual', actual)
    console.log('expected', expected)
    break
  }
}

diff-util.mjs

export const identity = (value) => {
  return value
}

diff.mjs

/**
 * Computes a list of changes needed to transform `previous` into `next`.
 * It generates a sequence of operations: insert, remove, move, or skip.
 *
 * @template T
 * @param {T[]} previous - The original list of items before updates.
 * @param {T[]} next - The new desired list of items after updates.
 * @param {(value: T) => any} key - A function to extract a unique, comparable key from each item.
 * @returns {Array<{tag: 'insert' | 'remove' | 'skip', index: number} | {tag: 'move', from: number, to: number}>}
 */
export const diff = (previous, next, key) => {
  const results = []

  // Create a working copy of the previous list so we can mutate it during diffing
  let current = [...previous]

  // Iterate through each index of the target `next` array
  for (let i = 0; i < next.length; i++) {
    if (i < current.length) {
      // Extract keys for both the current and desired item at this index
      const prevKey = key(current[i])
      const nextKey = key(next[i])

      if (prevKey !== nextKey) {
        // `next[i]` does not match `current[i]`, so we need to investigate

        // Look for the item with `nextKey` somewhere else in the `current` list
        let foundIndex = -1
        for (let j = 0; j < current.length; j++) {
          if (key(current[j]) === nextKey) {
            foundIndex = j
            break
          }
        }

        if (foundIndex !== -1) {
          // If the item exists in `current`, check if the `prevKey` is still needed in `next`
          let foundInNext = false
          for (const item of next) {
            if (key(item) === prevKey) {
              foundInNext = true
              break
            }
          }

          if (foundInNext) {
            // Both items exist, but in wrong positions → perform a move
            results.push({ tag: 'move', from: foundIndex, to: i })

            // Apply the move in the working list to keep it in sync
            current.splice(foundIndex, 1)
            current.splice(i, 0, next[i])
          } else {
            // The old item is no longer needed → remove it
            results.push({ tag: 'remove', index: i })
            current.splice(i, 1)

            // Decrement `i` to retry this index with the new current item
            i--
          }
        } else {
          // The desired item is new → insert it
          results.push({ tag: 'insert', index: i })
          current.splice(i, 0, next[i])
        }
      } else {
        // The current item is already correct → skip
        results.push({ tag: 'skip', index: i })
      }
    } else {
      // We’ve reached the end of the `current` list but still have more items in `next`
      // → insert new items at the end
      results.push({ tag: 'insert', index: i })
      current.push(next[i])
    }
  }

  // After processing all items in `next`, if `current` is longer, remove extras
  for (let i = next.length; i < current.length; i++) {
    results.push({ tag: 'remove', index: i })
  }

  return results
}