Keyed diff

test.js

let { Window } = require('./happy-dom')

let window = new Window()
let document = window.document

test(
  'No change',
  ['A', 'B', 'C', 'D'],
  ['A', 'B', 'C', 'D']
)

test(
  'Mixed',
  ['', '', 'B', 'C', 'D'],
  ['A', '', 'B', '', 'C', 'D']
)

test(
  'Appended',
  ['A', 'B', 'C', 'D'],
  ['A', 'B', 'C', 'D', 'E']
)

test(
  'Appended',
  ['A', 'B', 'C', 'D'],
  ['A', 'B', 'C', 'D', 'E']
)

test(
  'Appended 2',
  ['A', 'B', 'C', 'D'],
  ['A', 'B', 'C', 'D', 'E', 'F']
)

test(
  'Prepended',
  ['A', 'B', 'C', 'D'],
  ['E', 'A', 'B', 'C', 'D']
)

test(
  'Prepended 2',
  ['A', 'B', 'C', 'D'],
  ['E', 'F', 'A', 'B', 'C', 'D']
)

test(
  'Inserted',
  ['A', 'B', 'C', 'D'],
  ['A', 'E', 'B', 'C', 'D']
)

test(
  'Inserted 2',
  ['A', 'B', 'C', 'D'],
  ['A', 'E', 'F', 'B', 'C', 'D']
)

test(
  'Moved I',
  ['A', 'B', 'C', 'D'],
  ['D', 'B', 'C', 'A']
)

test(
  'Moved II',
  ['A', 'B', 'C', 'D'],
  ['A', 'C', 'B', 'D']
)

test(
  'Moved III',
  ['A', 'B', 'C', 'D'],
  ['C', 'B', 'A', 'D']
)

test(
  'Reversed',
  ['A', 'B', 'C', 'D'],
  ['D', 'C', 'B', 'A']
)

test(
  'Shuffled',
  ['A', 'B', 'C', 'D'],
  ['B', 'A', 'D', 'C']
)

test(
  'Shuffled 2',
  ['A', 'B', 'C', 'D'],
  ['C', 'A', 'D', 'B']
)

test(
  'Remove Last',
  ['A', 'B', 'C', 'D'],
  ['A', 'B', 'C']
)

test(
  'Remove Last 2',
  ['A', 'B', 'C', 'D'],
  ['A', 'B']
)

test(
  'Remove First',
  ['A', 'B', 'C', 'D'],
  ['B', 'C', 'D']
)

test(
  'Remove First 2',
  ['A', 'B', 'C', 'D'],
  ['C', 'D']
)

test(
  'Remove I',
  ['A', 'B', 'C', 'D'],
  ['A', 'C', 'D']
)

test(
  'Remove II',
  ['A', 'B', 'C', 'D'],
  ['A', 'B', 'D']
)

test(
  'Remove Middle',
  ['A', 'B', 'C', 'D'],
  ['A', 'D']
)

test(
  'Add All',
  [],
  ['A', 'B', 'C', 'D']
)

test(
  'Remove All',
  ['A', 'B', 'C', 'D'],
  []
)

function div (arr) {
  let d = document.createElement('div')
  d.innerHTML = arr.map(el => el === '' ? `<img src="${Math.random()}">` : `<img key="${el}">`).join('')
  return d
}

function test (title, curr, next) {
  let p = div(curr)
  let c = p.cloneNode(true)
  let n = div(next)
  patch(c, n)
}

function keyOf (element) {
  return element.getAttribute('key')
}

function patch (curr, next) {
  if (curr.nodeName !== next.nodeName) {
    curr.replaceWith(next)
  } else {
    if (curr.nodeType === 1) {
      for (let { name, value } of next.attributes) {
        if (curr.getAttribute(name) !== value) {
          curr.setAttribute(name, value)
        }
      }
      for (let { name } of [...curr.attributes]) {
        if (!next.hasAttribute(name)) {
          curr.removeAttribute(name)
        }
      }
      let currKeys = [...curr.childNodes].map(keyOf)
      let nextKeys = [...next.childNodes].map(keyOf)
      for (let i = 0; i < nextKeys.length; i++) {
        if (i < currKeys.length) {
          if (currKeys[i] !== nextKeys[i]) {
            let index = currKeys.indexOf(nextKeys[i])
            if (index > -1) {
              if (nextKeys.includes(currKeys[i])) {
                currKeys.splice(index, 1)
                currKeys.splice(i, 0, nextKeys[i])
                curr.insertBefore(
                  curr.childNodes[index],
                  curr.childNodes[i]
                )
                patch(curr.childNodes[i], next.childNodes[i])
              } else {
                currKeys.splice(i, 1)
                curr.removeChild(curr.childNodes[i])
                i--
              }
            } else {
              currKeys.splice(i, 0, next[i])
              curr.insertBefore(next.childNodes[i].cloneNode(true), curr.childNodes[i])
            }
          } else if (currKeys[i] === null) {
            patch(curr.childNodes[i], next.childNodes[i])
          }
        } else {
          currKeys.push(nextKeys[i])
          curr.appendChild(next.childNodes[i].cloneNode(true))
        }
      }
      let currLen = curr.childNodes.length
      let nextLen = next.childNodes.length
      for (let i = nextLen; i < currLen; i++) {
        curr.removeChild(curr.childNodes[nextLen])
      }
    } else if (curr.nodeType === 3) {
      if (curr.data !== next.data) {
        curr.data = next.data
      }
    }
  }
}

function patch__ (curr, next) {
  if (curr.nodeName !== next.nodeName) {
    curr.replaceWith(next)
  } else {
    if (curr.nodeType === 1) {
      for (let { name, value } of next.attributes) {
        if (curr.getAttribute(name) !== value) {
          curr.setAttribute(name, value)
        }
      }
      for (let { name } of [...curr.attributes]) {
        if (!next.hasAttribute(name)) {
          curr.removeAttribute(name)
        }
      }
      for (let i = 0; i < next.childNodes.length; i++) {
        if (i < curr.childNodes.length) {
          if (keyOf(curr.childNodes[i]) !== keyOf(next.childNodes[i])) {
            let index = [...curr.childNodes].findIndex(
              childNode =>
                keyOf(childNode) === keyOf(next.childNodes[i])
            )
            if (index > -1) {
              if (
                [...next.childNodes].find(
                  childNode => keyOf(childNode) === keyOf(curr.childNodes[i])
                )
              ) {
                curr.insertBefore(
                  curr.childNodes[index],
                  curr.childNodes[i]
                )
                patch(curr.childNodes[i], next.childNodes[i])
              } else {
                curr.removeChild(curr.childNodes[i])
                i--
              }
            } else {
              curr.insertBefore(next.childNodes[i].cloneNode(true), curr.childNodes[i])
            }
          } else if (keyOf(curr.childNodes[i]) === null) {
            patch(curr.childNodes[i], next.childNodes[i])
          }
        } else {
          curr.appendChild(next.childNodes[i].cloneNode(true))
        }
      }
      let currLen = curr.childNodes.length
      let nextLen = next.childNodes.length
      for (let i = nextLen; i < currLen; i++) {
        curr.removeChild(curr.childNodes[nextLen])
      }
    } else if (curr.nodeType === 3) {
      if (curr.data !== next.data) {
        curr.data = next.data
      }
    }
  }
}

function patch_ (curr, next) {
  let patches = []
  for (let i = 0; i < next.length; i++) {
    if (i < curr.length) {
      if (next[i] !== curr[i]) {
        let index = curr.indexOf(next[i])
        if (index > -1) {
          if (next.includes(curr[i])) {
            patches.push(`insertBefore (old) ${next[i]} [${i}]`)
            curr.splice(index, 1)
            curr.splice(i, 0, next[i]) // next[i] === curr[index]
          } else {
            patches.push(`removeChild ${curr[i]}`)
            curr.splice(i, 1)
            i--
          }
        } else {
          curr.splice(i, 0, next[i])
          patches.push(`insertBefore (new) ${next[i]} [${i}]`)
        }
      }
    } else {
      curr.push(next[i])
      patches.push(`appendChild (new) ${curr[i]} [${i}]`)
    }
  }
  let currLen = curr.length
  let nextLen = next.length
  for (let i = nextLen; i < currLen; i++) {
    patches.push(`removeChild ${curr[nextLen]}`)
    curr.splice(nextLen, 1)
  }
  return patches
}