diff.js

/* See LICENSE file for terms of use */

/*
 * Text diff implementation.
 *
 * This library supports the following APIS:
 * JsDiff.diffChars: Character by character diff
 * JsDiff.diffWords: Word (as defined by \b regex) diff which ignores whitespace
 * JsDiff.diffLines: Line based diff
 *
 * JsDiff.diffCss: Diff targeted at CSS content
 *
 * These methods are based on the implementation proposed in
 * "An O(ND) Difference Algorithm and its Variations" (Myers, 1986).
 * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927
 */
(function(global, undefined) {

  var JsDiff = (function() {
    /*jshint maxparams: 5*/
    /*istanbul ignore next*/
    function map(arr, mapper, that) {
      if (Array.prototype.map) {
        return Array.prototype.map.call(arr, mapper, that);
      }

      var other = new Array(arr.length);

      for (var i = 0, n = arr.length; i < n; i++) {
        other[i] = mapper.call(that, arr[i], i, arr);
      }
      return other;
    }
    function clonePath(path) {
      return { newPos: path.newPos, components: path.components.slice(0) };
    }
    function removeEmpty(array) {
      var ret = [];
      for (var i = 0; i < array.length; i++) {
        if (array[i]) {
          ret.push(array[i]);
        }
      }
      return ret;
    }
    function escapeHTML(s) {
      var n = s;
      n = n.replace(/&/g, '&amp;');
      n = n.replace(/</g, '&lt;');
      n = n.replace(/>/g, '&gt;');
      n = n.replace(/"/g, '&quot;');

      return n;
    }

    function buildValues(components, newString, oldString, useLongestToken) {
      var componentPos = 0,
          componentLen = components.length,
          newPos = 0,
          oldPos = 0;

      for (; componentPos < componentLen; componentPos++) {
        var component = components[componentPos];
        if (!component.removed) {
          if (!component.added && useLongestToken) {
            var value = newString.slice(newPos, newPos + component.count);
            value = map(value, function(value, i) {
              var oldValue = oldString[oldPos + i];
              return oldValue.length > value.length ? oldValue : value;
            });

            component.value = value.join('');
          } else {
            component.value = newString.slice(newPos, newPos + component.count).join('');
          }
          newPos += component.count;

          // Common case
          if (!component.added) {
            oldPos += component.count;
          }
        } else {
          component.value = oldString.slice(oldPos, oldPos + component.count).join('');
          oldPos += component.count;
        }
      }

      return components;
    }

    var Diff = function(ignoreWhitespace) {
      this.ignoreWhitespace = ignoreWhitespace;
    };
    Diff.prototype = {
        diff: function(oldString, newString, callback) {
          var self = this;

          function done(value) {
            if (callback) {
              setTimeout(function() { callback(undefined, value); }, 0);
              return true;
            } else {
              return value;
            }
          }

          // Handle the identity case (this is due to unrolling editLength == 0
          if (newString === oldString) {
            return done([{ value: newString }]);
          }
          if (!newString) {
            return done([{ value: oldString, removed: true }]);
          }
          if (!oldString) {
            return done([{ value: newString, added: true }]);
          }

          newString = this.tokenize(newString);
          oldString = this.tokenize(oldString);

          var newLen = newString.length, oldLen = oldString.length;
          var maxEditLength = newLen + oldLen;
          var bestPath = [{ newPos: -1, components: [] }];

          // Seed editLength = 0, i.e. the content starts with the same values
          var oldPos = this.extractCommon(bestPath[0], newString, oldString, 0);
          if (bestPath[0].newPos+1 >= newLen && oldPos+1 >= oldLen) {
            // Identity per the equality and tokenizer
            return done([{value: newString.join('')}]);
          }

          // Main worker method. checks all permutations of a given edit length for acceptance.
          function execEditLength() {
            for (var diagonalPath = -1*editLength; diagonalPath <= editLength; diagonalPath+=2) {
              var basePath;
              var addPath = bestPath[diagonalPath-1],
                  removePath = bestPath[diagonalPath+1];
              oldPos = (removePath ? removePath.newPos : 0) - diagonalPath;
              if (addPath) {
                // No one else is going to attempt to use this value, clear it
                bestPath[diagonalPath-1] = undefined;
              }

              var canAdd = addPath && addPath.newPos+1 < newLen;
              var canRemove = removePath && 0 <= oldPos && oldPos < oldLen;
              if (!canAdd && !canRemove) {
                // If this path is a terminal then prune
                bestPath[diagonalPath] = undefined;
                continue;
              }

              // Select the diagonal that we want to branch from. We select the prior
              // path whose position in the new string is the farthest from the origin
              // and does not pass the bounds of the diff graph
              if (!canAdd || (canRemove && addPath.newPos < removePath.newPos)) {
                basePath = clonePath(removePath);
                self.pushComponent(basePath.components, undefined, true);
              } else {
                basePath = addPath;   // No need to clone, we've pulled it from the list
                basePath.newPos++;
                self.pushComponent(basePath.components, true, undefined);
              }

              var oldPos = self.extractCommon(basePath, newString, oldString, diagonalPath);

              // If we have hit the end of both strings, then we are done
              if (basePath.newPos+1 >= newLen && oldPos+1 >= oldLen) {
                return done(buildValues(basePath.components, newString, oldString, self.useLongestToken));
              } else {
                // Otherwise track this path as a potential candidate and continue.
                bestPath[diagonalPath] = basePath;
              }
            }

            editLength++;
          }

          // Performs the length of edit iteration. Is a bit fugly as this has to support the
          // sync and async mode which is never fun. Loops over execEditLength until a value
          // is produced.
          var editLength = 1;
          if (callback) {
            (function exec() {
              setTimeout(function() {
                // This should not happen, but we want to be safe.
                /*istanbul ignore next */
                if (editLength > maxEditLength) {
                  return callback();
                }

                if (!execEditLength()) {
                  exec();
                }
              }, 0);
            })();
          } else {
            while(editLength <= maxEditLength) {
              var ret = execEditLength();
              if (ret) {
                return ret;
              }
            }
          }
        },

        pushComponent: function(components, added, removed) {
          var last = components[components.length-1];
          if (last && last.added === added && last.removed === removed) {
            // We need to clone here as the component clone operation is just
            // as shallow array clone
            components[components.length-1] = {count: last.count + 1, added: added, removed: removed };
          } else {
            components.push({count: 1, added: added, removed: removed });
          }
        },
        extractCommon: function(basePath, newString, oldString, diagonalPath) {
          var newLen = newString.length,
              oldLen = oldString.length,
              newPos = basePath.newPos,
              oldPos = newPos - diagonalPath,

              commonCount = 0;
          while (newPos+1 < newLen && oldPos+1 < oldLen && this.equals(newString[newPos+1], oldString[oldPos+1])) {
            newPos++;
            oldPos++;
            commonCount++;
          }

          if (commonCount) {
            basePath.components.push({count: commonCount});
          }

          basePath.newPos = newPos;
          return oldPos;
        },

        equals: function(left, right) {
          var reWhitespace = /\S/;
          return left === right || (this.ignoreWhitespace && !reWhitespace.test(left) && !reWhitespace.test(right));
        },
        tokenize: function(value) {
          return value.split('');
        }
    };

    var CharDiff = new Diff();

    var WordDiff = new Diff(true);
    var WordWithSpaceDiff = new Diff();
    WordDiff.tokenize = WordWithSpaceDiff.tokenize = function(value) {
      return removeEmpty(value.split(/(\s+|\b)/));
    };

    var CssDiff = new Diff(true);
    CssDiff.tokenize = function(value) {
      return removeEmpty(value.split(/([{}:;,]|\s+)/));
    };

    var LineDiff = new Diff();

    var TrimmedLineDiff = new Diff();
    TrimmedLineDiff.ignoreTrim = true;

    LineDiff.tokenize = TrimmedLineDiff.tokenize = function(value) {
      var retLines = [],
          lines = value.split(/^/m);
      for(var i = 0; i < lines.length; i++) {
        var line = lines[i],
            lastLine = lines[i - 1],
            lastLineLastChar = lastLine ? lastLine[lastLine.length - 1] : '';

        // Merge lines that may contain windows new lines
        if (line === '\n' && lastLineLastChar === '\r') {
            retLines[retLines.length - 1] = retLines[retLines.length - 1].slice(0,-1) + '\r\n';
        } else if (line) {
          if (this.ignoreTrim) {
            line = line.trim();
            //add a newline unless this is the last line.
            if (i < lines.length - 1) {
              line += '\n';
            }
          }
          retLines.push(line);
        }
      }

      return retLines;
    };


    var SentenceDiff = new Diff();
    SentenceDiff.tokenize = function (value) {
      return removeEmpty(value.split(/(\S.+?[.!?])(?=\s+|$)/));
    };

    var JsonDiff = new Diff();
    // Discriminate between two lines of pretty-printed, serialized JSON where one of them has a
    // dangling comma and the other doesn't. Turns out including the dangling comma yields the nicest output:
    JsonDiff.useLongestToken = true;
    JsonDiff.tokenize = LineDiff.tokenize;
    JsonDiff.equals = function(left, right) {
      return LineDiff.equals(left.replace(/,([\r\n])/g, '$1'), right.replace(/,([\r\n])/g, '$1'));
    };

    var objectPrototypeToString = Object.prototype.toString;

    // This function handles the presence of circular references by bailing out when encountering an
    // object that is already on the "stack" of items being processed.
    function canonicalize(obj, stack, replacementStack) {
      stack = stack || [];
      replacementStack = replacementStack || [];

      var i;

      for (var i = 0 ; i < stack.length ; i += 1) {
        if (stack[i] === obj) {
          return replacementStack[i];
        }
      }

      var canonicalizedObj;

      if ('[object Array]' === objectPrototypeToString.call(obj)) {
        stack.push(obj);
        canonicalizedObj = new Array(obj.length);
        replacementStack.push(canonicalizedObj);
        for (i = 0 ; i < obj.length ; i += 1) {
          canonicalizedObj[i] = canonicalize(obj[i], stack, replacementStack);
        }
        stack.pop();
        replacementStack.pop();
      } else if (typeof obj === 'object' && obj !== null) {
        stack.push(obj);
        canonicalizedObj = {};
        replacementStack.push(canonicalizedObj);
        var sortedKeys = [];
        for (var key in obj) {
          sortedKeys.push(key);
        }
        sortedKeys.sort();
        for (i = 0 ; i < sortedKeys.length ; i += 1) {
          var key = sortedKeys[i];
          canonicalizedObj[key] = canonicalize(obj[key], stack, replacementStack);
        }
        stack.pop();
        replacementStack.pop();
      } else {
        canonicalizedObj = obj;
      }
      return canonicalizedObj;
    }

    return {
      Diff: Diff,

      diffChars: function(oldStr, newStr, callback) { return CharDiff.diff(oldStr, newStr, callback); },
      diffWords: function(oldStr, newStr, callback) { return WordDiff.diff(oldStr, newStr, callback); },
      diffWordsWithSpace: function(oldStr, newStr, callback) { return WordWithSpaceDiff.diff(oldStr, newStr, callback); },
      diffLines: function(oldStr, newStr, callback) { return LineDiff.diff(oldStr, newStr, callback); },
      diffTrimmedLines: function(oldStr, newStr, callback) { return TrimmedLineDiff.diff(oldStr, newStr, callback); },

      diffSentences: function(oldStr, newStr, callback) { return SentenceDiff.diff(oldStr, newStr, callback); },

      diffCss: function(oldStr, newStr, callback) { return CssDiff.diff(oldStr, newStr, callback); },
      diffJson: function(oldObj, newObj, callback) {
        return JsonDiff.diff(
          typeof oldObj === 'string' ? oldObj : JSON.stringify(canonicalize(oldObj), undefined, '  '),
          typeof newObj === 'string' ? newObj : JSON.stringify(canonicalize(newObj), undefined, '  '),
          callback
        );
      },

      createTwoFilesPatch: function(oldFileName, newFileName, oldStr, newStr, oldHeader, newHeader) {
        var ret = [];

        if (oldFileName == newFileName) {
          ret.push('Index: ' + oldFileName);
	}
        ret.push('===================================================================');
        ret.push('--- ' + oldFileName + (typeof oldHeader === 'undefined' ? '' : '\t' + oldHeader));
        ret.push('+++ ' + newFileName + (typeof newHeader === 'undefined' ? '' : '\t' + newHeader));

        var diff = LineDiff.diff(oldStr, newStr);
        if (!diff[diff.length-1].value) {
          diff.pop();   // Remove trailing newline add
        }
        diff.push({value: '', lines: []});   // Append an empty value to make cleanup easier

        function contextLines(lines) {
          return map(lines, function(entry) { return ' ' + entry; });
        }
        function eofNL(curRange, i, current) {
          var last = diff[diff.length-2],
              isLast = i === diff.length-2,
              isLastOfType = i === diff.length-3 && (current.added !== last.added || current.removed !== last.removed);

          // Figure out if this is the last line for the given file and missing NL
          if (!/\n$/.test(current.value) && (isLast || isLastOfType)) {
            curRange.push('\\ No newline at end of file');
          }
        }

        var oldRangeStart = 0, newRangeStart = 0, curRange = [],
            oldLine = 1, newLine = 1;
        for (var i = 0; i < diff.length; i++) {
          var current = diff[i],
              lines = current.lines || current.value.replace(/\n$/, '').split('\n');
          current.lines = lines;

          if (current.added || current.removed) {
            if (!oldRangeStart) {
              var prev = diff[i-1];
              oldRangeStart = oldLine;
              newRangeStart = newLine;

              if (prev) {
                curRange = contextLines(prev.lines.slice(-4));
                oldRangeStart -= curRange.length;
                newRangeStart -= curRange.length;
              }
            }
            curRange.push.apply(curRange, map(lines, function(entry) { return (current.added?'+':'-') + entry; }));
            eofNL(curRange, i, current);

            if (current.added) {
              newLine += lines.length;
            } else {
              oldLine += lines.length;
            }
          } else {
            if (oldRangeStart) {
              // Close out any changes that have been output (or join overlapping)
              if (lines.length <= 8 && i < diff.length-2) {
                // Overlapping
                curRange.push.apply(curRange, contextLines(lines));
              } else {
                // end the range and output
                var contextSize = Math.min(lines.length, 4);
                ret.push(
                    '@@ -' + oldRangeStart + ',' + (oldLine-oldRangeStart+contextSize)
                    + ' +' + newRangeStart + ',' + (newLine-newRangeStart+contextSize)
                    + ' @@');
                ret.push.apply(ret, curRange);
                ret.push.apply(ret, contextLines(lines.slice(0, contextSize)));
                if (lines.length <= 4) {
                  eofNL(ret, i, current);
                }

                oldRangeStart = 0;  newRangeStart = 0; curRange = [];
              }
            }
            oldLine += lines.length;
            newLine += lines.length;
          }
        }

        return ret.join('\n') + '\n';
      },

      createPatch: function(fileName, oldStr, newStr, oldHeader, newHeader) {
        return JsDiff.createTwoFilesPatch(fileName, fileName, oldStr, newStr, oldHeader, newHeader);
      },

      applyPatch: function(oldStr, uniDiff) {
        var diffstr = uniDiff.split('\n');
        var diff = [];
        var i = 0,
            remEOFNL = false,
            addEOFNL = false;

        // Skip to the first change chunk
        while (i < diffstr.length && !/^@@/.test(diffstr[i])) {
          i++;
        }

        for (; i < diffstr.length; i++) {
          if (diffstr[i][0] === '@') {
            var meh = diffstr[i].split(/@@ -(\d+),(\d+) \+(\d+),(\d+) @@/);
            diff.unshift({
              start:meh[3],
              oldlength:meh[2],
              oldlines:[],
              newlength:meh[4],
              newlines:[]
            });
          } else if (diffstr[i][0] === '+') {
            diff[0].newlines.push(diffstr[i].substr(1));
          } else if (diffstr[i][0] === '-') {
            diff[0].oldlines.push(diffstr[i].substr(1));
          } else if (diffstr[i][0] === ' ') {
            diff[0].newlines.push(diffstr[i].substr(1));
            diff[0].oldlines.push(diffstr[i].substr(1));
          } else if (diffstr[i][0] === '\\') {
            if (diffstr[i-1][0] === '+') {
              remEOFNL = true;
            } else if (diffstr[i-1][0] === '-') {
              addEOFNL = true;
            }
          }
        }

        var str = oldStr.split('\n');
        for (var i = diff.length - 1; i >= 0; i--) {
          var d = diff[i];
          for (var j = 0; j < d.oldlength; j++) {
            if (str[d.start-1+j] !== d.oldlines[j]) {
              return false;
            }
          }
          Array.prototype.splice.apply(str,[d.start-1,+d.oldlength].concat(d.newlines));
        }

        if (remEOFNL) {
          while (!str[str.length-1]) {
            str.pop();
          }
        } else if (addEOFNL) {
          str.push('');
        }
        return str.join('\n');
      },

      convertChangesToXML: function(changes){
        var ret = [];
        for ( var i = 0; i < changes.length; i++) {
          var change = changes[i];
          if (change.added) {
            ret.push('<ins>');
          } else if (change.removed) {
            ret.push('<del>');
          }

          ret.push(escapeHTML(change.value));

          if (change.added) {
            ret.push('</ins>');
          } else if (change.removed) {
            ret.push('</del>');
          }
        }
        return ret.join('');
      },

      // See: http://code.google.com/p/google-diff-match-patch/wiki/API
      convertChangesToDMP: function(changes){
        var ret = [], change;
        for ( var i = 0; i < changes.length; i++) {
          change = changes[i];
          ret.push([(change.added ? 1 : change.removed ? -1 : 0), change.value]);
        }
        return ret;
      },

      canonicalize: canonicalize
    };
  })();

  /*istanbul ignore next */
  if (typeof module !== 'undefined' && module.exports) {
    module.exports = JsDiff;
  }
  else if (typeof define === 'function' && define.amd) {
    /*global define */
    define([], function() { return JsDiff; });
  }
  else if (typeof global.JsDiff === 'undefined') {
    global.JsDiff = JsDiff;
  }
})(this);