| /* 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 objectPrototypeToString = Object.prototype.toString; |
| |
| /*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, '&'); |
| n = n.replace(/</g, '<'); |
| n = n.replace(/>/g, '>'); |
| n = n.replace(/"/g, '"'); |
| |
| return n; |
| } |
| |
| // 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 (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 = [], |
| key; |
| for (key in obj) { |
| sortedKeys.push(key); |
| } |
| sortedKeys.sort(); |
| for (i = 0; i < sortedKeys.length; i += 1) { |
| key = sortedKeys[i]; |
| canonicalizedObj[key] = canonicalize(obj[key], stack, replacementStack); |
| } |
| stack.pop(); |
| replacementStack.pop(); |
| } else { |
| canonicalizedObj = obj; |
| } |
| return canonicalizedObj; |
| } |
| |
| 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; |
| |
| // Reverse add and remove so removes are output first to match common convention |
| // The diffing algorithm is tied to add then remove output and this is the simplest |
| // route to get the desired output with minimal overhead. |
| if (componentPos && components[componentPos - 1].added) { |
| var tmp = components[componentPos - 1]; |
| components[componentPos - 1] = components[componentPos]; |
| components[componentPos] = tmp; |
| } |
| } |
| } |
| |
| return components; |
| } |
| |
| function Diff(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 editLength = 1; |
| 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, |
| 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); |
| } |
| |
| 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. |
| 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 (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 PatchDiff = new Diff(); |
| PatchDiff.tokenize = function(value) { |
| var ret = [], |
| linesAndNewlines = value.split(/(\n|\r\n)/); |
| |
| // Ignore the final empty token that occurs if the string ends with a new line |
| if (!linesAndNewlines[linesAndNewlines.length - 1]) { |
| linesAndNewlines.pop(); |
| } |
| |
| // Merge the content and line separators into single tokens |
| for (var i = 0; i < linesAndNewlines.length; i++) { |
| var line = linesAndNewlines[i]; |
| |
| if (i % 2) { |
| ret[ret.length - 1] += line; |
| } else { |
| ret.push(line); |
| } |
| } |
| return ret; |
| }; |
| |
| 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 JsDiff = { |
| 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 = PatchDiff.diff(oldStr, newStr); |
| diff.push({value: '', lines: []}); // Append an empty value to make cleanup easier |
| |
| // Formats a given set of lines for printing as context lines in a patch |
| function contextLines(lines) { |
| return map(lines, function(entry) { return ' ' + entry; }); |
| } |
| |
| // Outputs the no newline at end of file warning if needed |
| 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; |
| |
| // 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 we have previous context, start with that |
| 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; |
| } |
| } |
| |
| // Output our changes |
| curRange.push.apply(curRange, map(lines, function(entry) { |
| return (current.added ? '+' : '-') + entry; |
| })); |
| eofNL(curRange, i, current); |
| |
| // Track the updated file position |
| if (current.added) { |
| newLine += lines.length; |
| } else { |
| oldLine += lines.length; |
| } |
| } else { |
| // Identical context lines. Track line changes |
| 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'), |
| hunks = [], |
| i = 0, |
| remEOFNL = false, |
| addEOFNL = false; |
| |
| // Skip to the first change hunk |
| while (i < diffstr.length && !(/^@@/.test(diffstr[i]))) { |
| i++; |
| } |
| |
| // Parse the unified diff |
| for (; i < diffstr.length; i++) { |
| if (diffstr[i][0] === '@') { |
| var chnukHeader = diffstr[i].split(/@@ -(\d+),(\d+) \+(\d+),(\d+) @@/); |
| hunks.unshift({ |
| start: chnukHeader[3], |
| oldlength: +chnukHeader[2], |
| removed: [], |
| newlength: chnukHeader[4], |
| added: [] |
| }); |
| } else if (diffstr[i][0] === '+') { |
| hunks[0].added.push(diffstr[i].substr(1)); |
| } else if (diffstr[i][0] === '-') { |
| hunks[0].removed.push(diffstr[i].substr(1)); |
| } else if (diffstr[i][0] === ' ') { |
| hunks[0].added.push(diffstr[i].substr(1)); |
| hunks[0].removed.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; |
| } |
| } |
| } |
| |
| // Apply the diff to the input |
| var lines = oldStr.split('\n'); |
| for (i = hunks.length - 1; i >= 0; i--) { |
| var hunk = hunks[i]; |
| // Sanity check the input string. Bail if we don't match. |
| for (var j = 0; j < hunk.oldlength; j++) { |
| if (lines[hunk.start - 1 + j] !== hunk.removed[j]) { |
| return false; |
| } |
| } |
| Array.prototype.splice.apply(lines, [hunk.start - 1, hunk.oldlength].concat(hunk.added)); |
| } |
| |
| // Handle EOFNL insertion/removal |
| if (remEOFNL) { |
| while (!lines[lines.length - 1]) { |
| lines.pop(); |
| } |
| } else if (addEOFNL) { |
| lines.push(''); |
| } |
| return lines.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, |
| operation; |
| for (var i = 0; i < changes.length; i++) { |
| change = changes[i]; |
| if (change.added) { |
| operation = 1; |
| } else if (change.removed) { |
| operation = -1; |
| } else { |
| operation = 0; |
| } |
| |
| ret.push([operation, change.value]); |
| } |
| return ret; |
| }, |
| |
| canonicalize: canonicalize |
| }; |
| |
| /*istanbul ignore next */ |
| /*global module */ |
| 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)); |