Simple List Change Detection (Diffing)

differ.js

function diff(source, target) {
  source = JSON.parse(JSON.stringify(source)).map(JSON.stringify);
  target = JSON.parse(JSON.stringify(target)).map(JSON.stringify);

  var changes = [];

  while (source.length && target.length) {
    var oldVal = source.shift();
    var newVal = target.shift();

    var added   = target.indexOf(oldVal);
    var removed = source.indexOf(newVal);

    if (JSON.stringify(oldVal) == JSON.stringify(newVal)) {
      // If the values are the same, there was no change.
      changes.push({ action: 'keep', value: JSON.parse(newVal) });

    } else if (~added || ~removed) {
      // If the current value appears later in either array, we've something
      // has been changed between here and there.
      var inserting = ! ~removed || (~added && source.length < target.length);

      var row    = inserting ? target : source;
      var action = inserting ? 'insert' : 'delete';
      var value  = inserting ? newVal : oldVal;

      row.unshift(value);
      for (var i = 0; i <= (inserting ? added : removed); i++) {
        changes.push({ action: action, value: JSON.parse(row.shift()) });
      }
      changes.push({ action: 'keep', value: JSON.parse(row.shift()) });
    } else {
      // Otherwise, we should replace the old value with the new one.
      changes.push({ action: 'change', value: JSON.parse(newVal), previous: JSON.parse(oldVal) });
    }
  }

  // Add changes for anything remaining at the end of the list.
  source.forEach(function(val) {
    changes.push({ action: 'delete', value: JSON.parse(val) });
  });

  target.forEach(function(val) {
    changes.push({ action: 'insert', value: JSON.parse(val) });
  });

  return changes;
}

examples.js

diff( [1, 2, 3, 4], [2, 3, 4, 5] );
// => [ { action: 'delete', value: 1 },
//      { action: 'keep', value: 2 },
//      { action: 'keep', value: 3 },
//      { action: 'keep', value: 4 },
//      { action: 'insert', value: 5 } ]

diff( [1, 2, 3], [1, 5, 3] );
// => [ { action: 'keep', value: 1 },
//      { action: 'change', value: 5, previous: 2 },
//      { action: 'keep', value: 3 } ]