A Speedy E.Meyers's O(ND) Based Diffing Algorithm

 

This is a re-write of the original Arpad Borsos's diff repository.

As there's no single module in npm that doesn't couple Meyers with strings, and all do more than one thing, I've decided to re-publish it with performance improvements and in a modern ECMAScript fashion. Arpad Borsos agreed so ... here it is.

``js
import {NOOP, REPLACE, INSERT, DELETE, diff} from 'speedy-myers';
// const {NOOP, REPLACE, INSERT, DELETE, diff} = require('speedy-myers');

const changes = diff(
sourceList, // the list you'd like to diff
targetList, // against its updated version
// with an optional callback
// to diff objects by keys too
(a, b) => a.id === b.id
);
`

The resulting Array of changes will contain all the information to _patch_ the sourceList through operations performed via the targetList.

$3

`js
const {NOOP, REPLACE, INSERT, DELETE, diff} = Myers;
const source = [1, 2, 3, 4, 5];
const target = [2, 7, 4, 5, 9, 6];
const changes = diff(source, target);
let sourceIndex = 0;
let targetIndex = 0;
for (let i = 0, {length} = changes; i < length; i++) {
switch (changes[i]) {

// in both REPLACE and NOOP cases
// move forward with both indexes
case REPLACE:
// in replace case, you can safely pass the value
source[sourceIndex] = target[targetIndex];
// se no break here: the fallthrough in meant to increment
case NOOP:
sourceIndex++;
targetIndex++;
break;

case DELETE:
source.splice(sourceIndex, 1);
// Note: in this case don't increment the sourceIndex
// as the length mutated via splice, however,
// you should increment sourceIndex++ if you are dealing
// with a parentNode, as example, and the source is a facade
// never touch the targetIndex during DELETE
break;

case INSERT:
// Note: in this case, as the length is mutated again
// you need to move forward sourceIndex++ too
// but if you appending nodes, or inserting before other nodes,
// you should not move sourceIndex forward
source.splice(sourceIndex++, 0, target[targetIndex]);

// the targetIndex instead should always be incremented on INSERT
targetIndex++;
break;
}
}

// verify everything went fine
console.assert(source.join(',') === target.join(','));
`

#### A DOM Based Example

As this module is general purpose, it is possible to use it to update a tree in the DOM too.

uhtml, lighterhtml, and hyperHTML use a very similar strategy through udomdiff and domdiff.

`js
const {NOOP, REPLACE, INSERT, DELETE, diff} = Myers;
const parentNode = document.body;
const source = [].slice.call(document.body.childNodes);
const target = source.append(document.createElement('myers'));
const changes = diff(source, target);
let sourceIndex = 0;
let targetIndex = 0;
const comments = new Map;
for (let i = 0, {length} = changes; i < length; i++) {
switch (changes[i]) {

case REPLACE:
// as a node cannot exists simultaneously in two parts of the tree
// we cannot append directly the target[targetIndex] unless
// its parentNode is different, or non-existent
if (target[targetIndex].parentNode !== parentNode)
parentNode.replaceChild(
target[targetIndex],
source[sourceIndex]
);
// otherwise we need to use a placeholder to keep the position
// and replace it only once all operations are completed
else {
const comment = document.createComment('');
comments.set(comment, target[targetIndex]);
parentNode.replaceChild(comment, source[sourceIndex]);
}
// remember to move forward both indexes, with NOOP and REPLACE
case NOOP:
sourceIndex++;
targetIndex++;
break;

case DELETE:
// it is always safe to remove a live node from its deleted position
parentNode.removeChild(source[sourceIndex]);
// remember in this case to move the sourceIndex forward
sourceIndex++;
break;

case INSERT:
// similarly with the REPLACE case, we cannot insert the target node
// right away, unless its parent is different
if (target[targetIndex].parentNode !== parentNode)
// INSERT can happen outside the source boundaries
// however, null or undefined, with insertBefore
// means appendChild, so since this is a root container
// it is OK to just use insertBefore
parentNode.insertBefore(
target[targetIndex],
source[sourceIndex]
);
// use the same comment strategy
else {
const comment = document.createComment('');
comments.set(comment, target[targetIndex]);
parentNode.insertBefore(comment, source[sourceIndex]);
}
// always move forward targetIndex++; on INSERT
targetIndex++;
break;
}
}

// once the loop is completed, we can replace all placeholders
comments.forEach((node, comment) => {
parentNode.replaceChild(node, comment);
});
`

$3

This module is compatible with IE11 and every other Mobile or Desktop engine that supports Int8Array`.