// Defaults.

// Redefine these in your program to override the defaults.

// Number of seconds to map a diff before giving up (0 for infinity).

this.Diff_Timeout = 1.0;

// Cost of an empty edit operation in terms of edit characters.

this.Diff_EditCost = 4;

// At what point is no match declared (0.0 = perfection, 1.0 = very loose).

this.Match_Threshold = 0.5;

// How far to search for a match (0 = exact location, 1000+ = broad match).

// A match this many characters away from the expected location will add

// 1.0 to the score (0.0 is a perfect match).

this.Match_Distance = 1000;

// When deleting a large block of text (over ~64 characters), how close do

// the contents have to be to match the expected contents. (0.0 = perfection,

// 1.0 = very loose). Note that Match_Threshold controls how closely the

// end points of a delete need to match.

this.Patch_DeleteThreshold = 0.5;

// Chunk size for context length.

this.Patch_Margin = 4;

// The number of bits in an int.

this.Match_MaxBits = 32;

opt_deadline) {

// Set a deadline by which time the diff must be complete.

if (typeof opt_deadline == 'undefined') {

if (this.Diff_Timeout <= 0) {

opt_deadline = Number.MAX_VALUE;

} else {

opt_deadline = (new Date).getTime() + this.Diff_Timeout * 1000;

}

}

var deadline = opt_deadline;

// Check for null inputs.

if (text1 == null || text2 == null) {

throw new Error('Null input. (diff_main)');

}

// Check for equality (speedup).

if (text1 == text2) {

if (text1) {

return [new diff_match_patch.Diff(DIFF_EQUAL, text1)];

}

return [];

}

if (typeof opt_checklines == 'undefined') {

opt_checklines = true;

}

var checklines = opt_checklines;

// Trim off common prefix (speedup).

var commonlength = this.diff_commonPrefix(text1, text2);

var commonprefix = text1.substring(0, commonlength);

text1 = text1.substring(commonlength);

text2 = text2.substring(commonlength);

// Trim off common suffix (speedup).

commonlength = this.diff_commonSuffix(text1, text2);

var commonsuffix = text1.substring(text1.length - commonlength);

text1 = text1.substring(0, text1.length - commonlength);

text2 = text2.substring(0, text2.length - commonlength);

// Compute the diff on the middle block.

var diffs = this.diff_compute_(text1, text2, checklines, deadline);

// Restore the prefix and suffix.

if (commonprefix) {

diffs.unshift(new diff_match_patch.Diff(DIFF_EQUAL, commonprefix));

}

if (commonsuffix) {

diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, commonsuffix));

}

this.diff_cleanupMerge(diffs);

return diffs;

deadline) {

var diffs;

if (!text1) {

// Just add some text (speedup).

return [new diff_match_patch.Diff(DIFF_INSERT, text2)];

}

if (!text2) {

// Just delete some text (speedup).

return [new diff_match_patch.Diff(DIFF_DELETE, text1)];

}

var longtext = text1.length > text2.length ? text1 : text2;

var shorttext = text1.length > text2.length ? text2 : text1;

var i = longtext.indexOf(shorttext);

if (i != -1) {

// Shorter text is inside the longer text (speedup).

diffs = [new diff_match_patch.Diff(DIFF_INSERT, longtext.substring(0, i)),

new diff_match_patch.Diff(DIFF_EQUAL, shorttext),

new diff_match_patch.Diff(DIFF_INSERT,

longtext.substring(i + shorttext.length))];

// Swap insertions for deletions if diff is reversed.

if (text1.length > text2.length) {

diffs[0][0] = diffs[2][0] = DIFF_DELETE;

}

return diffs;

}

if (shorttext.length == 1) {

// Single character string.

// After the previous speedup, the character can't be an equality.

return [new diff_match_patch.Diff(DIFF_DELETE, text1),

new diff_match_patch.Diff(DIFF_INSERT, text2)];

}

// Check to see if the problem can be split in two.

var hm = this.diff_halfMatch_(text1, text2);

if (hm) {

// A half-match was found, sort out the return data.

var text1_a = hm[0];

var text1_b = hm[1];

var text2_a = hm[2];

var text2_b = hm[3];

var mid_common = hm[4];

// Send both pairs off for separate processing.

var diffs_a = this.diff_main(text1_a, text2_a, checklines, deadline);

var diffs_b = this.diff_main(text1_b, text2_b, checklines, deadline);

// Merge the results.

return diffs_a.concat([new diff_match_patch.Diff(DIFF_EQUAL, mid_common)],

diffs_b);

}

if (checklines && text1.length > 100 && text2.length > 100) {

return this.diff_lineMode_(text1, text2, deadline);

}

return this.diff_bisect_(text1, text2, deadline);

// Scan the text on a line-by-line basis first.

var a = this.diff_linesToChars_(text1, text2);

text1 = a.chars1;

text2 = a.chars2;

var linearray = a.lineArray;

var diffs = this.diff_main(text1, text2, false, deadline);

// Convert the diff back to original text.

this.diff_charsToLines_(diffs, linearray);

// Eliminate freak matches (e.g. blank lines)

this.diff_cleanupSemantic(diffs);

// Rediff any replacement blocks, this time character-by-character.

// Add a dummy entry at the end.

diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, ''));

var pointer = 0;

var count_delete = 0;

var count_insert = 0;

var text_delete = '';

var text_insert = '';

while (pointer < diffs.length) {

switch (diffs[pointer][0]) {

case DIFF_INSERT:

count_insert++;

text_insert += diffs[pointer][1];

break;

case DIFF_DELETE:

count_delete++;

text_delete += diffs[pointer][1];

break;

case DIFF_EQUAL:

// Upon reaching an equality, check for prior redundancies.

if (count_delete >= 1 && count_insert >= 1) {

// Delete the offending records and add the merged ones.

diffs.splice(pointer - count_delete - count_insert,

count_delete + count_insert);

pointer = pointer - count_delete - count_insert;

var subDiff =

this.diff_main(text_delete, text_insert, false, deadline);

for (var j = subDiff.length - 1; j >= 0; j--) {

diffs.splice(pointer, 0, subDiff[j]);

}

pointer = pointer + subDiff.length;

}

count_insert = 0;

count_delete = 0;

text_delete = '';

text_insert = '';

break;

}

pointer++;

}

diffs.pop(); // Remove the dummy entry at the end.

return diffs;

// Cache the text lengths to prevent multiple calls.

var text1_length = text1.length;

var text2_length = text2.length;

var max_d = Math.ceil((text1_length + text2_length) / 2);

var v_offset = max_d;

var v_length = 2 * max_d;

var v1 = new Array(v_length);

var v2 = new Array(v_length);

// Setting all elements to -1 is faster in Chrome & Firefox than mixing

// integers and undefined.

for (var x = 0; x < v_length; x++) {

v1[x] = -1;

v2[x] = -1;

}

v1[v_offset + 1] = 0;

v2[v_offset + 1] = 0;

var delta = text1_length - text2_length;

// If the total number of characters is odd, then the front path will collide

// with the reverse path.

var front = (delta % 2 != 0);

// Offsets for start and end of k loop.

// Prevents mapping of space beyond the grid.

var k1start = 0;

var k1end = 0;

var k2start = 0;

var k2end = 0;

for (var d = 0; d < max_d; d++) {

// Bail out if deadline is reached.

if ((new Date()).getTime() > deadline) {

break;

}

// Walk the front path one step.

for (var k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {

var k1_offset = v_offset + k1;

var x1;

if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {

x1 = v1[k1_offset + 1];

} else {

x1 = v1[k1_offset - 1] + 1;

}

var y1 = x1 - k1;

while (x1 < text1_length && y1 < text2_length &&

text1.charAt(x1) == text2.charAt(y1)) {

x1++;

y1++;

}

v1[k1_offset] = x1;

if (x1 > text1_length) {

// Ran off the right of the graph.

k1end += 2;

} else if (y1 > text2_length) {

// Ran off the bottom of the graph.

k1start += 2;

} else if (front) {

var k2_offset = v_offset + delta - k1;

if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {

// Mirror x2 onto top-left coordinate system.

var x2 = text1_length - v2[k2_offset];

if (x1 >= x2) {

// Overlap detected.

return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);

}

}

}

}

// Walk the reverse path one step.

for (var k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {

var k2_offset = v_offset + k2;

var x2;

if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {

x2 = v2[k2_offset + 1];

} else {

x2 = v2[k2_offset - 1] + 1;

}

var y2 = x2 - k2;

while (x2 < text1_length && y2 < text2_length &&

text1.charAt(text1_length - x2 - 1) ==

text2.charAt(text2_length - y2 - 1)) {

x2++;

y2++;

}

v2[k2_offset] = x2;

if (x2 > text1_length) {

// Ran off the left of the graph.

k2end += 2;

} else if (y2 > text2_length) {

// Ran off the top of the graph.

k2start += 2;

} else if (!front) {

var k1_offset = v_offset + delta - k2;

if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {

var x1 = v1[k1_offset];

var y1 = v_offset + x1 - k1_offset;

// Mirror x2 onto top-left coordinate system.

x2 = text1_length - x2;

if (x1 >= x2) {

// Overlap detected.

return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);

}

}

}

}

}

// Diff took too long and hit the deadline or

// number of diffs equals number of characters, no commonality at all.

return [new diff_match_patch.Diff(DIFF_DELETE, text1),

new diff_match_patch.Diff(DIFF_INSERT, text2)];

deadline) {

var text1a = text1.substring(0, x);

var text2a = text2.substring(0, y);

var text1b = text1.substring(x);

var text2b = text2.substring(y);

// Compute both diffs serially.

var diffs = this.diff_main(text1a, text2a, false, deadline);

var diffsb = this.diff_main(text1b, text2b, false, deadline);

return diffs.concat(diffsb);

var lineArray = []; // e.g. lineArray[4] == 'Hello\n'

var lineHash = {}; // e.g. lineHash['Hello\n'] == 4

// '\x00' is a valid character, but various debuggers don't like it.

// So we'll insert a junk entry to avoid generating a null character.

lineArray[0] = '';

/**

function diff_linesToCharsMunge_(text) {

var chars = '';

// Walk the text, pulling out a substring for each line.

// text.split('\n') would would temporarily double our memory footprint.

// Modifying text would create many large strings to garbage collect.

var lineStart = 0;

var lineEnd = -1;

// Keeping our own length variable is faster than looking it up.

var lineArrayLength = lineArray.length;

while (lineEnd < text.length - 1) {

lineEnd = text.indexOf('\n', lineStart);

if (lineEnd == -1) {

lineEnd = text.length - 1;

}

var line = text.substring(lineStart, lineEnd + 1);

if (lineHash.hasOwnProperty ? lineHash.hasOwnProperty(line) :

(lineHash[line] !== undefined)) {

chars += String.fromCharCode(lineHash[line]);

} else {

if (lineArrayLength == maxLines) {

// Bail out at 65535 because

// String.fromCharCode(65536) == String.fromCharCode(0)

line = text.substring(lineStart);

lineEnd = text.length;

}

chars += String.fromCharCode(lineArrayLength);

lineHash[line] = lineArrayLength;

lineArray[lineArrayLength++] = line;

}

lineStart = lineEnd + 1;

}

return chars;

}

// Allocate 2/3rds of the space for text1, the rest for text2.

var maxLines = 40000;

var chars1 = diff_linesToCharsMunge_(text1);

maxLines = 65535;

var chars2 = diff_linesToCharsMunge_(text2);

return {chars1: chars1, chars2: chars2, lineArray: lineArray};

for (var i = 0; i < diffs.length; i++) {

var chars = diffs[i][1];

var text = [];

for (var j = 0; j < chars.length; j++) {

text[j] = lineArray[chars.charCodeAt(j)];

}

diffs[i][1] = text.join('');

}

// Quick check for common null cases.

if (!text1 || !text2 || text1.charAt(0) != text2.charAt(0)) {

return 0;

}

// Binary search.

// Performance analysis: https://neil.fraser.name/news/2007/10/09/

var pointermin = 0;

var pointermax = Math.min(text1.length, text2.length);

var pointermid = pointermax;

var pointerstart = 0;

while (pointermin < pointermid) {

if (text1.substring(pointerstart, pointermid) ==

text2.substring(pointerstart, pointermid)) {

pointermin = pointermid;

pointerstart = pointermin;

} else {

pointermax = pointermid;

}

pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);

}

return pointermid;

// Quick check for common null cases.

if (!text1 || !text2 ||

text1.charAt(text1.length - 1) != text2.charAt(text2.length - 1)) {

return 0;

}

// Binary search.

// Performance analysis: https://neil.fraser.name/news/2007/10/09/

var pointermin = 0;

var pointermax = Math.min(text1.length, text2.length);

var pointermid = pointermax;

var pointerend = 0;

while (pointermin < pointermid) {

if (text1.substring(text1.length - pointermid, text1.length - pointerend) ==

text2.substring(text2.length - pointermid, text2.length - pointerend)) {

pointermin = pointermid;

pointerend = pointermin;

} else {

pointermax = pointermid;

}

pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);

}

return pointermid;

// Cache the text lengths to prevent multiple calls.

var text1_length = text1.length;

var text2_length = text2.length;

// Eliminate the null case.

if (text1_length == 0 || text2_length == 0) {

return 0;

}

// Truncate the longer string.

if (text1_length > text2_length) {

text1 = text1.substring(text1_length - text2_length);

} else if (text1_length < text2_length) {

text2 = text2.substring(0, text1_length);

}

var text_length = Math.min(text1_length, text2_length);

// Quick check for the worst case.

if (text1 == text2) {

return text_length;

}

// Start by looking for a single character match

// and increase length until no match is found.

// Performance analysis: https://neil.fraser.name/news/2010/11/04/

var best = 0;

var length = 1;

while (true) {

var pattern = text1.substring(text_length - length);

var found = text2.indexOf(pattern);

if (found == -1) {

return best;

}

length += found;

if (found == 0 || text1.substring(text_length - length) ==

text2.substring(0, length)) {

best = length;

length++;

}

}

if (this.Diff_Timeout <= 0) {

// Don't risk returning a non-optimal diff if we have unlimited time.

return null;

}

var longtext = text1.length > text2.length ? text1 : text2;

var shorttext = text1.length > text2.length ? text2 : text1;

if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {

return null; // Pointless.

}

var dmp = this; // 'this' becomes 'window' in a closure.

/**

function diff_halfMatchI_(longtext, shorttext, i) {

// Start with a 1/4 length substring at position i as a seed.

var seed = longtext.substring(i, i + Math.floor(longtext.length / 4));

var j = -1;

var best_common = '';

var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;

while ((j = shorttext.indexOf(seed, j + 1)) != -1) {

var prefixLength = dmp.diff_commonPrefix(longtext.substring(i),

shorttext.substring(j));

var suffixLength = dmp.diff_commonSuffix(longtext.substring(0, i),

shorttext.substring(0, j));

if (best_common.length < suffixLength + prefixLength) {

best_common = shorttext.substring(j - suffixLength, j) +

shorttext.substring(j, j + prefixLength);

best_longtext_a = longtext.substring(0, i - suffixLength);

best_longtext_b = longtext.substring(i + prefixLength);

best_shorttext_a = shorttext.substring(0, j - suffixLength);

best_shorttext_b = shorttext.substring(j + prefixLength);

}

}

if (best_common.length * 2 >= longtext.length) {

return [best_longtext_a, best_longtext_b,

best_shorttext_a, best_shorttext_b, best_common];

} else {

return null;

}

}

// First check if the second quarter is the seed for a half-match.

var hm1 = diff_halfMatchI_(longtext, shorttext,

Math.ceil(longtext.length / 4));

// Check again based on the third quarter.

var hm2 = diff_halfMatchI_(longtext, shorttext,

Math.ceil(longtext.length / 2));

var hm;

if (!hm1 && !hm2) {

return null;

} else if (!hm2) {

hm = hm1;

} else if (!hm1) {

hm = hm2;

} else {

// Both matched. Select the longest.

hm = hm1[4].length > hm2[4].length ? hm1 : hm2;

}

// A half-match was found, sort out the return data.

var text1_a, text1_b, text2_a, text2_b;

if (text1.length > text2.length) {

text1_a = hm[0];

text1_b = hm[1];

text2_a = hm[2];

text2_b = hm[3];

} else {

text2_a = hm[0];

text2_b = hm[1];

text1_a = hm[2];

text1_b = hm[3];

}

var mid_common = hm[4];

return [text1_a, text1_b, text2_a, text2_b, mid_common];

var changes = false;

var equalities = []; // Stack of indices where equalities are found.

var equalitiesLength = 0; // Keeping our own length var is faster in JS.

/** @type {?string} */

var lastEquality = null;

// Always equal to diffs[equalities[equalitiesLength - 1]][1]

var pointer = 0; // Index of current position.

// Number of characters that changed prior to the equality.

var length_insertions1 = 0;

var length_deletions1 = 0;

// Number of characters that changed after the equality.

var length_insertions2 = 0;

var length_deletions2 = 0;

while (pointer < diffs.length) {

if (diffs[pointer][0] == DIFF_EQUAL) { // Equality found.

equalities[equalitiesLength++] = pointer;

length_insertions1 = length_insertions2;

length_deletions1 = length_deletions2;

length_insertions2 = 0;

length_deletions2 = 0;

lastEquality = diffs[pointer][1];

} else { // An insertion or deletion.

if (diffs[pointer][0] == DIFF_INSERT) {

length_insertions2 += diffs[pointer][1].length;

} else {

length_deletions2 += diffs[pointer][1].length;

}

// Eliminate an equality that is smaller or equal to the edits on both

// sides of it.

if (lastEquality && (lastEquality.length <=

Math.max(length_insertions1, length_deletions1)) &&

(lastEquality.length <= Math.max(length_insertions2,

length_deletions2))) {

// Duplicate record.

diffs.splice(equalities[equalitiesLength - 1], 0,

new diff_match_patch.Diff(DIFF_DELETE, lastEquality));

// Change second copy to insert.

diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;

// Throw away the equality we just deleted.

equalitiesLength--;

// Throw away the previous equality (it needs to be reevaluated).

equalitiesLength--;

pointer = equalitiesLength > 0 ? equalities[equalitiesLength - 1] : -1;

length_insertions1 = 0; // Reset the counters.

length_deletions1 = 0;

length_insertions2 = 0;

length_deletions2 = 0;

lastEquality = null;

changes = true;

}

}

pointer++;

}

// Normalize the diff.

if (changes) {

this.diff_cleanupMerge(diffs);

}

this.diff_cleanupSemanticLossless(diffs);

// Find any overlaps between deletions and insertions.

// e.g: <del>abcxxx</del><ins>xxxdef</ins>

// -> <del>abc</del>xxx<ins>def</ins>

// e.g: <del>xxxabc</del><ins>defxxx</ins>

// -> <ins>def</ins>xxx<del>abc</del>

// Only extract an overlap if it is as big as the edit ahead or behind it.

pointer = 1;

while (pointer < diffs.length) {

if (diffs[pointer - 1][0] == DIFF_DELETE &&

diffs[pointer][0] == DIFF_INSERT) {

var deletion = diffs[pointer - 1][1];

var insertion = diffs[pointer][1];

var overlap_length1 = this.diff_commonOverlap_(deletion, insertion);

var overlap_length2 = this.diff_commonOverlap_(insertion, deletion);

if (overlap_length1 >= overlap_length2) {

if (overlap_length1 >= deletion.length / 2 ||

overlap_length1 >= insertion.length / 2) {

// Overlap found. Insert an equality and trim the surrounding edits.

diffs.splice(pointer, 0, new diff_match_patch.Diff(DIFF_EQUAL,

insertion.substring(0, overlap_length1)));

diffs[pointer - 1][1] =

deletion.substring(0, deletion.length - overlap_length1);