How to use diffs method in argos

Best JavaScript code snippet using argos

diff_match_patch_uncompressed.js

Source:diff_match_patch_uncompressed.js Github

copy

Full Screen

1/**2 * Diff Match and Patch3 *4 * Copyright 2006 Google Inc.5 * http://code.google.com/p/google-diff-match-patch/6 *7 * Licensed under the Apache License, Version 2.0 (the "License");8 * you may not use this file except in compliance with the License.9 * You may obtain a copy of the License at10 *11 * http://www.apache.org/licenses/LICENSE-2.012 *13 * Unless required by applicable law or agreed to in writing, software14 * distributed under the License is distributed on an "AS IS" BASIS,15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.16 * See the License for the specific language governing permissions and17 * limitations under the License.18 */19/**20 * @fileoverview Computes the difference between two texts to create a patch.21 * Applies the patch onto another text, allowing for errors.22 * @author fraser@google.com (Neil Fraser)23 */24/**25 * Class containing the diff, match and patch methods.26 * @constructor27 */28function diff_match_patch() {29 // Defaults.30 // Redefine these in your program to override the defaults.31 // Number of seconds to map a diff before giving up (0 for infinity).32 this.Diff_Timeout = 1.0;33 // Cost of an empty edit operation in terms of edit characters.34 this.Diff_EditCost = 4;35 // At what point is no match declared (0.0 = perfection, 1.0 = very loose).36 this.Match_Threshold = 0.5;37 // How far to search for a match (0 = exact location, 1000+ = broad match).38 // A match this many characters away from the expected location will add39 // 1.0 to the score (0.0 is a perfect match).40 this.Match_Distance = 1000;41 // When deleting a large block of text (over ~64 characters), how close do42 // the contents have to be to match the expected contents. (0.0 = perfection,43 // 1.0 = very loose). Note that Match_Threshold controls how closely the44 // end points of a delete need to match.45 this.Patch_DeleteThreshold = 0.5;46 // Chunk size for context length.47 this.Patch_Margin = 4;48 // The number of bits in an int.49 this.Match_MaxBits = 32;50}51// DIFF FUNCTIONS52/**53 * The data structure representing a diff is an array of tuples:54 * [[DIFF_DELETE, 'Hello'], [DIFF_INSERT, 'Goodbye'], [DIFF_EQUAL, ' world.']]55 * which means: delete 'Hello', add 'Goodbye' and keep ' world.'56 */57var DIFF_DELETE = -1;58var DIFF_INSERT = 1;59var DIFF_EQUAL = 0;60/** @typedef {{0: number, 1: string}} */61diff_match_patch.Diff;62/**63 * Find the differences between two texts. Simplifies the problem by stripping64 * any common prefix or suffix off the texts before diffing.65 * @param {string} text1 Old string to be diffed.66 * @param {string} text2 New string to be diffed.67 * @param {boolean=} opt_checklines Optional speedup flag. If present and false,68 * then don't run a line-level diff first to identify the changed areas.69 * Defaults to true, which does a faster, slightly less optimal diff.70 * @param {number} opt_deadline Optional time when the diff should be complete71 * by. Used internally for recursive calls. Users should set DiffTimeout72 * instead.73 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.74 */75diff_match_patch.prototype.diff_main = function(text1, text2, opt_checklines,76 opt_deadline) {77 // Set a deadline by which time the diff must be complete.78 if (typeof opt_deadline == 'undefined') {79 if (this.Diff_Timeout <= 0) {80 opt_deadline = Number.MAX_VALUE;81 } else {82 opt_deadline = (new Date).getTime() + this.Diff_Timeout * 1000;83 }84 }85 var deadline = opt_deadline;86 // Check for null inputs.87 if (text1 == null || text2 == null) {88 throw new Error('Null input. (diff_main)');89 }90 // Check for equality (speedup).91 if (text1 == text2) {92 if (text1) {93 return [[DIFF_EQUAL, text1]];94 }95 return [];96 }97 if (typeof opt_checklines == 'undefined') {98 opt_checklines = true;99 }100 var checklines = opt_checklines;101 // Trim off common prefix (speedup).102 var commonlength = this.diff_commonPrefix(text1, text2);103 var commonprefix = text1.substring(0, commonlength);104 text1 = text1.substring(commonlength);105 text2 = text2.substring(commonlength);106 // Trim off common suffix (speedup).107 commonlength = this.diff_commonSuffix(text1, text2);108 var commonsuffix = text1.substring(text1.length - commonlength);109 text1 = text1.substring(0, text1.length - commonlength);110 text2 = text2.substring(0, text2.length - commonlength);111 // Compute the diff on the middle block.112 var diffs = this.diff_compute_(text1, text2, checklines, deadline);113 // Restore the prefix and suffix.114 if (commonprefix) {115 diffs.unshift([DIFF_EQUAL, commonprefix]);116 }117 if (commonsuffix) {118 diffs.push([DIFF_EQUAL, commonsuffix]);119 }120 this.diff_cleanupMerge(diffs);121 return diffs;122};123/**124 * Find the differences between two texts. Assumes that the texts do not125 * have any common prefix or suffix.126 * @param {string} text1 Old string to be diffed.127 * @param {string} text2 New string to be diffed.128 * @param {boolean} checklines Speedup flag. If false, then don't run a129 * line-level diff first to identify the changed areas.130 * If true, then run a faster, slightly less optimal diff.131 * @param {number} deadline Time when the diff should be complete by.132 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.133 * @private134 */135diff_match_patch.prototype.diff_compute_ = function(text1, text2, checklines,136 deadline) {137 var diffs;138 if (!text1) {139 // Just add some text (speedup).140 return [[DIFF_INSERT, text2]];141 }142 if (!text2) {143 // Just delete some text (speedup).144 return [[DIFF_DELETE, text1]];145 }146 var longtext = text1.length > text2.length ? text1 : text2;147 var shorttext = text1.length > text2.length ? text2 : text1;148 var i = longtext.indexOf(shorttext);149 if (i != -1) {150 // Shorter text is inside the longer text (speedup).151 diffs = [[DIFF_INSERT, longtext.substring(0, i)],152 [DIFF_EQUAL, shorttext],153 [DIFF_INSERT, longtext.substring(i + shorttext.length)]];154 // Swap insertions for deletions if diff is reversed.155 if (text1.length > text2.length) {156 diffs[0][0] = diffs[2][0] = DIFF_DELETE;157 }158 return diffs;159 }160 if (shorttext.length == 1) {161 // Single character string.162 // After the previous speedup, the character can't be an equality.163 return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];164 }165 // Check to see if the problem can be split in two.166 var hm = this.diff_halfMatch_(text1, text2);167 if (hm) {168 // A half-match was found, sort out the return data.169 var text1_a = hm[0];170 var text1_b = hm[1];171 var text2_a = hm[2];172 var text2_b = hm[3];173 var mid_common = hm[4];174 // Send both pairs off for separate processing.175 var diffs_a = this.diff_main(text1_a, text2_a, checklines, deadline);176 var diffs_b = this.diff_main(text1_b, text2_b, checklines, deadline);177 // Merge the results.178 return diffs_a.concat([[DIFF_EQUAL, mid_common]], diffs_b);179 }180 if (checklines && text1.length > 100 && text2.length > 100) {181 return this.diff_lineMode_(text1, text2, deadline);182 }183 return this.diff_bisect_(text1, text2, deadline);184};185/**186 * Do a quick line-level diff on both strings, then rediff the parts for187 * greater accuracy.188 * This speedup can produce non-minimal diffs.189 * @param {string} text1 Old string to be diffed.190 * @param {string} text2 New string to be diffed.191 * @param {number} deadline Time when the diff should be complete by.192 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.193 * @private194 */195diff_match_patch.prototype.diff_lineMode_ = function(text1, text2, deadline) {196 // Scan the text on a line-by-line basis first.197 var a = this.diff_linesToChars_(text1, text2);198 text1 = a.chars1;199 text2 = a.chars2;200 var linearray = a.lineArray;201 var diffs = this.diff_main(text1, text2, false, deadline);202 // Convert the diff back to original text.203 this.diff_charsToLines_(diffs, linearray);204 // Eliminate freak matches (e.g. blank lines)205 this.diff_cleanupSemantic(diffs);206 // Rediff any replacement blocks, this time character-by-character.207 // Add a dummy entry at the end.208 diffs.push([DIFF_EQUAL, '']);209 var pointer = 0;210 var count_delete = 0;211 var count_insert = 0;212 var text_delete = '';213 var text_insert = '';214 while (pointer < diffs.length) {215 switch (diffs[pointer][0]) {216 case DIFF_INSERT:217 count_insert++;218 text_insert += diffs[pointer][1];219 break;220 case DIFF_DELETE:221 count_delete++;222 text_delete += diffs[pointer][1];223 break;224 case DIFF_EQUAL:225 // Upon reaching an equality, check for prior redundancies.226 if (count_delete >= 1 && count_insert >= 1) {227 // Delete the offending records and add the merged ones.228 diffs.splice(pointer - count_delete - count_insert,229 count_delete + count_insert);230 pointer = pointer - count_delete - count_insert;231 var a = this.diff_main(text_delete, text_insert, false, deadline);232 for (var j = a.length - 1; j >= 0; j--) {233 diffs.splice(pointer, 0, a[j]);234 }235 pointer = pointer + a.length;236 }237 count_insert = 0;238 count_delete = 0;239 text_delete = '';240 text_insert = '';241 break;242 }243 pointer++;244 }245 diffs.pop(); // Remove the dummy entry at the end.246 return diffs;247};248/**249 * Find the 'middle snake' of a diff, split the problem in two250 * and return the recursively constructed diff.251 * See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.252 * @param {string} text1 Old string to be diffed.253 * @param {string} text2 New string to be diffed.254 * @param {number} deadline Time at which to bail if not yet complete.255 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.256 * @private257 */258diff_match_patch.prototype.diff_bisect_ = function(text1, text2, deadline) {259 // Cache the text lengths to prevent multiple calls.260 var text1_length = text1.length;261 var text2_length = text2.length;262 var max_d = Math.ceil((text1_length + text2_length) / 2);263 var v_offset = max_d;264 var v_length = 2 * max_d;265 var v1 = new Array(v_length);266 var v2 = new Array(v_length);267 // Setting all elements to -1 is faster in Chrome & Firefox than mixing268 // integers and undefined.269 for (var x = 0; x < v_length; x++) {270 v1[x] = -1;271 v2[x] = -1;272 }273 v1[v_offset + 1] = 0;274 v2[v_offset + 1] = 0;275 var delta = text1_length - text2_length;276 // If the total number of characters is odd, then the front path will collide277 // with the reverse path.278 var front = (delta % 2 != 0);279 // Offsets for start and end of k loop.280 // Prevents mapping of space beyond the grid.281 var k1start = 0;282 var k1end = 0;283 var k2start = 0;284 var k2end = 0;285 for (var d = 0; d < max_d; d++) {286 // Bail out if deadline is reached.287 if ((new Date()).getTime() > deadline) {288 break;289 }290 // Walk the front path one step.291 for (var k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {292 var k1_offset = v_offset + k1;293 var x1;294 if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {295 x1 = v1[k1_offset + 1];296 } else {297 x1 = v1[k1_offset - 1] + 1;298 }299 var y1 = x1 - k1;300 while (x1 < text1_length && y1 < text2_length &&301 text1.charAt(x1) == text2.charAt(y1)) {302 x1++;303 y1++;304 }305 v1[k1_offset] = x1;306 if (x1 > text1_length) {307 // Ran off the right of the graph.308 k1end += 2;309 } else if (y1 > text2_length) {310 // Ran off the bottom of the graph.311 k1start += 2;312 } else if (front) {313 var k2_offset = v_offset + delta - k1;314 if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {315 // Mirror x2 onto top-left coordinate system.316 var x2 = text1_length - v2[k2_offset];317 if (x1 >= x2) {318 // Overlap detected.319 return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);320 }321 }322 }323 }324 // Walk the reverse path one step.325 for (var k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {326 var k2_offset = v_offset + k2;327 var x2;328 if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {329 x2 = v2[k2_offset + 1];330 } else {331 x2 = v2[k2_offset - 1] + 1;332 }333 var y2 = x2 - k2;334 while (x2 < text1_length && y2 < text2_length &&335 text1.charAt(text1_length - x2 - 1) ==336 text2.charAt(text2_length - y2 - 1)) {337 x2++;338 y2++;339 }340 v2[k2_offset] = x2;341 if (x2 > text1_length) {342 // Ran off the left of the graph.343 k2end += 2;344 } else if (y2 > text2_length) {345 // Ran off the top of the graph.346 k2start += 2;347 } else if (!front) {348 var k1_offset = v_offset + delta - k2;349 if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {350 var x1 = v1[k1_offset];351 var y1 = v_offset + x1 - k1_offset;352 // Mirror x2 onto top-left coordinate system.353 x2 = text1_length - x2;354 if (x1 >= x2) {355 // Overlap detected.356 return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);357 }358 }359 }360 }361 }362 // Diff took too long and hit the deadline or363 // number of diffs equals number of characters, no commonality at all.364 return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];365};366/**367 * Given the location of the 'middle snake', split the diff in two parts368 * and recurse.369 * @param {string} text1 Old string to be diffed.370 * @param {string} text2 New string to be diffed.371 * @param {number} x Index of split point in text1.372 * @param {number} y Index of split point in text2.373 * @param {number} deadline Time at which to bail if not yet complete.374 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.375 * @private376 */377diff_match_patch.prototype.diff_bisectSplit_ = function(text1, text2, x, y,378 deadline) {379 var text1a = text1.substring(0, x);380 var text2a = text2.substring(0, y);381 var text1b = text1.substring(x);382 var text2b = text2.substring(y);383 // Compute both diffs serially.384 var diffs = this.diff_main(text1a, text2a, false, deadline);385 var diffsb = this.diff_main(text1b, text2b, false, deadline);386 return diffs.concat(diffsb);387};388/**389 * Split two texts into an array of strings. Reduce the texts to a string of390 * hashes where each Unicode character represents one line.391 * @param {string} text1 First string.392 * @param {string} text2 Second string.393 * @return {{chars1: string, chars2: string, lineArray: !Array.<string>}}394 * An object containing the encoded text1, the encoded text2 and395 * the array of unique strings.396 * The zeroth element of the array of unique strings is intentionally blank.397 * @private398 */399diff_match_patch.prototype.diff_linesToChars_ = function(text1, text2) {400 var lineArray = []; // e.g. lineArray[4] == 'Hello\n'401 var lineHash = {}; // e.g. lineHash['Hello\n'] == 4402 // '\x00' is a valid character, but various debuggers don't like it.403 // So we'll insert a junk entry to avoid generating a null character.404 lineArray[0] = '';405 /**406 * Split a text into an array of strings. Reduce the texts to a string of407 * hashes where each Unicode character represents one line.408 * Modifies linearray and linehash through being a closure.409 * @param {string} text String to encode.410 * @return {string} Encoded string.411 * @private412 */413 function diff_linesToCharsMunge_(text) {414 var chars = '';415 // Walk the text, pulling out a substring for each line.416 // text.split('\n') would would temporarily double our memory footprint.417 // Modifying text would create many large strings to garbage collect.418 var lineStart = 0;419 var lineEnd = -1;420 // Keeping our own length variable is faster than looking it up.421 var lineArrayLength = lineArray.length;422 while (lineEnd < text.length - 1) {423 lineEnd = text.indexOf('\n', lineStart);424 if (lineEnd == -1) {425 lineEnd = text.length - 1;426 }427 var line = text.substring(lineStart, lineEnd + 1);428 lineStart = lineEnd + 1;429 if (lineHash.hasOwnProperty ? lineHash.hasOwnProperty(line) :430 (lineHash[line] !== undefined)) {431 chars += String.fromCharCode(lineHash[line]);432 } else {433 chars += String.fromCharCode(lineArrayLength);434 lineHash[line] = lineArrayLength;435 lineArray[lineArrayLength++] = line;436 }437 }438 return chars;439 }440 var chars1 = diff_linesToCharsMunge_(text1);441 var chars2 = diff_linesToCharsMunge_(text2);442 return {chars1: chars1, chars2: chars2, lineArray: lineArray};443};444/**445 * Rehydrate the text in a diff from a string of line hashes to real lines of446 * text.447 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.448 * @param {!Array.<string>} lineArray Array of unique strings.449 * @private450 */451diff_match_patch.prototype.diff_charsToLines_ = function(diffs, lineArray) {452 for (var x = 0; x < diffs.length; x++) {453 var chars = diffs[x][1];454 var text = [];455 for (var y = 0; y < chars.length; y++) {456 text[y] = lineArray[chars.charCodeAt(y)];457 }458 diffs[x][1] = text.join('');459 }460};461/**462 * Determine the common prefix of two strings.463 * @param {string} text1 First string.464 * @param {string} text2 Second string.465 * @return {number} The number of characters common to the start of each466 * string.467 */468diff_match_patch.prototype.diff_commonPrefix = function(text1, text2) {469 // Quick check for common null cases.470 if (!text1 || !text2 || text1.charAt(0) != text2.charAt(0)) {471 return 0;472 }473 // Binary search.474 // Performance analysis: http://neil.fraser.name/news/2007/10/09/475 var pointermin = 0;476 var pointermax = Math.min(text1.length, text2.length);477 var pointermid = pointermax;478 var pointerstart = 0;479 while (pointermin < pointermid) {480 if (text1.substring(pointerstart, pointermid) ==481 text2.substring(pointerstart, pointermid)) {482 pointermin = pointermid;483 pointerstart = pointermin;484 } else {485 pointermax = pointermid;486 }487 pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);488 }489 return pointermid;490};491/**492 * Determine the common suffix of two strings.493 * @param {string} text1 First string.494 * @param {string} text2 Second string.495 * @return {number} The number of characters common to the end of each string.496 */497diff_match_patch.prototype.diff_commonSuffix = function(text1, text2) {498 // Quick check for common null cases.499 if (!text1 || !text2 ||500 text1.charAt(text1.length - 1) != text2.charAt(text2.length - 1)) {501 return 0;502 }503 // Binary search.504 // Performance analysis: http://neil.fraser.name/news/2007/10/09/505 var pointermin = 0;506 var pointermax = Math.min(text1.length, text2.length);507 var pointermid = pointermax;508 var pointerend = 0;509 while (pointermin < pointermid) {510 if (text1.substring(text1.length - pointermid, text1.length - pointerend) ==511 text2.substring(text2.length - pointermid, text2.length - pointerend)) {512 pointermin = pointermid;513 pointerend = pointermin;514 } else {515 pointermax = pointermid;516 }517 pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);518 }519 return pointermid;520};521/**522 * Determine if the suffix of one string is the prefix of another.523 * @param {string} text1 First string.524 * @param {string} text2 Second string.525 * @return {number} The number of characters common to the end of the first526 * string and the start of the second string.527 * @private528 */529diff_match_patch.prototype.diff_commonOverlap_ = function(text1, text2) {530 // Cache the text lengths to prevent multiple calls.531 var text1_length = text1.length;532 var text2_length = text2.length;533 // Eliminate the null case.534 if (text1_length == 0 || text2_length == 0) {535 return 0;536 }537 // Truncate the longer string.538 if (text1_length > text2_length) {539 text1 = text1.substring(text1_length - text2_length);540 } else if (text1_length < text2_length) {541 text2 = text2.substring(0, text1_length);542 }543 var text_length = Math.min(text1_length, text2_length);544 // Quick check for the worst case.545 if (text1 == text2) {546 return text_length;547 }548 // Start by looking for a single character match549 // and increase length until no match is found.550 // Performance analysis: http://neil.fraser.name/news/2010/11/04/551 var best = 0;552 var length = 1;553 while (true) {554 var pattern = text1.substring(text_length - length);555 var found = text2.indexOf(pattern);556 if (found == -1) {557 return best;558 }559 length += found;560 if (found == 0 || text1.substring(text_length - length) ==561 text2.substring(0, length)) {562 best = length;563 length++;564 }565 }566};567/**568 * Do the two texts share a substring which is at least half the length of the569 * longer text?570 * This speedup can produce non-minimal diffs.571 * @param {string} text1 First string.572 * @param {string} text2 Second string.573 * @return {Array.<string>} Five element Array, containing the prefix of574 * text1, the suffix of text1, the prefix of text2, the suffix of575 * text2 and the common middle. Or null if there was no match.576 * @private577 */578diff_match_patch.prototype.diff_halfMatch_ = function(text1, text2) {579 if (this.Diff_Timeout <= 0) {580 // Don't risk returning a non-optimal diff if we have unlimited time.581 return null;582 }583 var longtext = text1.length > text2.length ? text1 : text2;584 var shorttext = text1.length > text2.length ? text2 : text1;585 if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {586 return null; // Pointless.587 }588 var dmp = this; // 'this' becomes 'window' in a closure.589 /**590 * Does a substring of shorttext exist within longtext such that the substring591 * is at least half the length of longtext?592 * Closure, but does not reference any external variables.593 * @param {string} longtext Longer string.594 * @param {string} shorttext Shorter string.595 * @param {number} i Start index of quarter length substring within longtext.596 * @return {Array.<string>} Five element Array, containing the prefix of597 * longtext, the suffix of longtext, the prefix of shorttext, the suffix598 * of shorttext and the common middle. Or null if there was no match.599 * @private600 */601 function diff_halfMatchI_(longtext, shorttext, i) {602 // Start with a 1/4 length substring at position i as a seed.603 var seed = longtext.substring(i, i + Math.floor(longtext.length / 4));604 var j = -1;605 var best_common = '';606 var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;607 while ((j = shorttext.indexOf(seed, j + 1)) != -1) {608 var prefixLength = dmp.diff_commonPrefix(longtext.substring(i),609 shorttext.substring(j));610 var suffixLength = dmp.diff_commonSuffix(longtext.substring(0, i),611 shorttext.substring(0, j));612 if (best_common.length < suffixLength + prefixLength) {613 best_common = shorttext.substring(j - suffixLength, j) +614 shorttext.substring(j, j + prefixLength);615 best_longtext_a = longtext.substring(0, i - suffixLength);616 best_longtext_b = longtext.substring(i + prefixLength);617 best_shorttext_a = shorttext.substring(0, j - suffixLength);618 best_shorttext_b = shorttext.substring(j + prefixLength);619 }620 }621 if (best_common.length * 2 >= longtext.length) {622 return [best_longtext_a, best_longtext_b,623 best_shorttext_a, best_shorttext_b, best_common];624 } else {625 return null;626 }627 }628 // First check if the second quarter is the seed for a half-match.629 var hm1 = diff_halfMatchI_(longtext, shorttext,630 Math.ceil(longtext.length / 4));631 // Check again based on the third quarter.632 var hm2 = diff_halfMatchI_(longtext, shorttext,633 Math.ceil(longtext.length / 2));634 var hm;635 if (!hm1 && !hm2) {636 return null;637 } else if (!hm2) {638 hm = hm1;639 } else if (!hm1) {640 hm = hm2;641 } else {642 // Both matched. Select the longest.643 hm = hm1[4].length > hm2[4].length ? hm1 : hm2;644 }645 // A half-match was found, sort out the return data.646 var text1_a, text1_b, text2_a, text2_b;647 if (text1.length > text2.length) {648 text1_a = hm[0];649 text1_b = hm[1];650 text2_a = hm[2];651 text2_b = hm[3];652 } else {653 text2_a = hm[0];654 text2_b = hm[1];655 text1_a = hm[2];656 text1_b = hm[3];657 }658 var mid_common = hm[4];659 return [text1_a, text1_b, text2_a, text2_b, mid_common];660};661/**662 * Reduce the number of edits by eliminating semantically trivial equalities.663 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.664 */665diff_match_patch.prototype.diff_cleanupSemantic = function(diffs) {666 var changes = false;667 var equalities = []; // Stack of indices where equalities are found.668 var equalitiesLength = 0; // Keeping our own length var is faster in JS.669 /** @type {?string} */670 var lastequality = null;671 // Always equal to diffs[equalities[equalitiesLength - 1]][1]672 var pointer = 0; // Index of current position.673 // Number of characters that changed prior to the equality.674 var length_insertions1 = 0;675 var length_deletions1 = 0;676 // Number of characters that changed after the equality.677 var length_insertions2 = 0;678 var length_deletions2 = 0;679 while (pointer < diffs.length) {680 if (diffs[pointer][0] == DIFF_EQUAL) { // Equality found.681 equalities[equalitiesLength++] = pointer;682 length_insertions1 = length_insertions2;683 length_deletions1 = length_deletions2;684 length_insertions2 = 0;685 length_deletions2 = 0;686 lastequality = diffs[pointer][1];687 } else { // An insertion or deletion.688 if (diffs[pointer][0] == DIFF_INSERT) {689 length_insertions2 += diffs[pointer][1].length;690 } else {691 length_deletions2 += diffs[pointer][1].length;692 }693 // Eliminate an equality that is smaller or equal to the edits on both694 // sides of it.695 if (lastequality && (lastequality.length <=696 Math.max(length_insertions1, length_deletions1)) &&697 (lastequality.length <= Math.max(length_insertions2,698 length_deletions2))) {699 // Duplicate record.700 diffs.splice(equalities[equalitiesLength - 1], 0,701 [DIFF_DELETE, lastequality]);702 // Change second copy to insert.703 diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;704 // Throw away the equality we just deleted.705 equalitiesLength--;706 // Throw away the previous equality (it needs to be reevaluated).707 equalitiesLength--;708 pointer = equalitiesLength > 0 ? equalities[equalitiesLength - 1] : -1;709 length_insertions1 = 0; // Reset the counters.710 length_deletions1 = 0;711 length_insertions2 = 0;712 length_deletions2 = 0;713 lastequality = null;714 changes = true;715 }716 }717 pointer++;718 }719 // Normalize the diff.720 if (changes) {721 this.diff_cleanupMerge(diffs);722 }723 this.diff_cleanupSemanticLossless(diffs);724 // Find any overlaps between deletions and insertions.725 // e.g: <del>abcxxx</del><ins>xxxdef</ins>726 // -> <del>abc</del>xxx<ins>def</ins>727 // e.g: <del>xxxabc</del><ins>defxxx</ins>728 // -> <ins>def</ins>xxx<del>abc</del>729 // Only extract an overlap if it is as big as the edit ahead or behind it.730 pointer = 1;731 while (pointer < diffs.length) {732 if (diffs[pointer - 1][0] == DIFF_DELETE &&733 diffs[pointer][0] == DIFF_INSERT) {734 var deletion = diffs[pointer - 1][1];735 var insertion = diffs[pointer][1];736 var overlap_length1 = this.diff_commonOverlap_(deletion, insertion);737 var overlap_length2 = this.diff_commonOverlap_(insertion, deletion);738 if (overlap_length1 >= overlap_length2) {739 if (overlap_length1 >= deletion.length / 2 ||740 overlap_length1 >= insertion.length / 2) {741 // Overlap found. Insert an equality and trim the surrounding edits.742 diffs.splice(pointer, 0,743 [DIFF_EQUAL, insertion.substring(0, overlap_length1)]);744 diffs[pointer - 1][1] =745 deletion.substring(0, deletion.length - overlap_length1);746 diffs[pointer + 1][1] = insertion.substring(overlap_length1);747 pointer++;748 }749 } else {750 if (overlap_length2 >= deletion.length / 2 ||751 overlap_length2 >= insertion.length / 2) {752 // Reverse overlap found.753 // Insert an equality and swap and trim the surrounding edits.754 diffs.splice(pointer, 0,755 [DIFF_EQUAL, deletion.substring(0, overlap_length2)]);756 diffs[pointer - 1][0] = DIFF_INSERT;757 diffs[pointer - 1][1] =758 insertion.substring(0, insertion.length - overlap_length2);759 diffs[pointer + 1][0] = DIFF_DELETE;760 diffs[pointer + 1][1] =761 deletion.substring(overlap_length2);762 pointer++;763 }764 }765 pointer++;766 }767 pointer++;768 }769};770/**771 * Look for single edits surrounded on both sides by equalities772 * which can be shifted sideways to align the edit to a word boundary.773 * e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.774 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.775 */776diff_match_patch.prototype.diff_cleanupSemanticLossless = function(diffs) {777 /**778 * Given two strings, compute a score representing whether the internal779 * boundary falls on logical boundaries.780 * Scores range from 6 (best) to 0 (worst).781 * Closure, but does not reference any external variables.782 * @param {string} one First string.783 * @param {string} two Second string.784 * @return {number} The score.785 * @private786 */787 function diff_cleanupSemanticScore_(one, two) {788 if (!one || !two) {789 // Edges are the best.790 return 6;791 }792 // Each port of this function behaves slightly differently due to793 // subtle differences in each language's definition of things like794 // 'whitespace'. Since this function's purpose is largely cosmetic,795 // the choice has been made to use each language's native features796 // rather than force total conformity.797 var char1 = one.charAt(one.length - 1);798 var char2 = two.charAt(0);799 var nonAlphaNumeric1 = char1.match(diff_match_patch.nonAlphaNumericRegex_);800 var nonAlphaNumeric2 = char2.match(diff_match_patch.nonAlphaNumericRegex_);801 var whitespace1 = nonAlphaNumeric1 &&802 char1.match(diff_match_patch.whitespaceRegex_);803 var whitespace2 = nonAlphaNumeric2 &&804 char2.match(diff_match_patch.whitespaceRegex_);805 var lineBreak1 = whitespace1 &&806 char1.match(diff_match_patch.linebreakRegex_);807 var lineBreak2 = whitespace2 &&808 char2.match(diff_match_patch.linebreakRegex_);809 var blankLine1 = lineBreak1 &&810 one.match(diff_match_patch.blanklineEndRegex_);811 var blankLine2 = lineBreak2 &&812 two.match(diff_match_patch.blanklineStartRegex_);813 if (blankLine1 || blankLine2) {814 // Five points for blank lines.815 return 5;816 } else if (lineBreak1 || lineBreak2) {817 // Four points for line breaks.818 return 4;819 } else if (nonAlphaNumeric1 && !whitespace1 && whitespace2) {820 // Three points for end of sentences.821 return 3;822 } else if (whitespace1 || whitespace2) {823 // Two points for whitespace.824 return 2;825 } else if (nonAlphaNumeric1 || nonAlphaNumeric2) {826 // One point for non-alphanumeric.827 return 1;828 }829 return 0;830 }831 var pointer = 1;832 // Intentionally ignore the first and last element (don't need checking).833 while (pointer < diffs.length - 1) {834 if (diffs[pointer - 1][0] == DIFF_EQUAL &&835 diffs[pointer + 1][0] == DIFF_EQUAL) {836 // This is a single edit surrounded by equalities.837 var equality1 = diffs[pointer - 1][1];838 var edit = diffs[pointer][1];839 var equality2 = diffs[pointer + 1][1];840 // First, shift the edit as far left as possible.841 var commonOffset = this.diff_commonSuffix(equality1, edit);842 if (commonOffset) {843 var commonString = edit.substring(edit.length - commonOffset);844 equality1 = equality1.substring(0, equality1.length - commonOffset);845 edit = commonString + edit.substring(0, edit.length - commonOffset);846 equality2 = commonString + equality2;847 }848 // Second, step character by character right, looking for the best fit.849 var bestEquality1 = equality1;850 var bestEdit = edit;851 var bestEquality2 = equality2;852 var bestScore = diff_cleanupSemanticScore_(equality1, edit) +853 diff_cleanupSemanticScore_(edit, equality2);854 while (edit.charAt(0) === equality2.charAt(0)) {855 equality1 += edit.charAt(0);856 edit = edit.substring(1) + equality2.charAt(0);857 equality2 = equality2.substring(1);858 var score = diff_cleanupSemanticScore_(equality1, edit) +859 diff_cleanupSemanticScore_(edit, equality2);860 // The >= encourages trailing rather than leading whitespace on edits.861 if (score >= bestScore) {862 bestScore = score;863 bestEquality1 = equality1;864 bestEdit = edit;865 bestEquality2 = equality2;866 }867 }868 if (diffs[pointer - 1][1] != bestEquality1) {869 // We have an improvement, save it back to the diff.870 if (bestEquality1) {871 diffs[pointer - 1][1] = bestEquality1;872 } else {873 diffs.splice(pointer - 1, 1);874 pointer--;875 }876 diffs[pointer][1] = bestEdit;877 if (bestEquality2) {878 diffs[pointer + 1][1] = bestEquality2;879 } else {880 diffs.splice(pointer + 1, 1);881 pointer--;882 }883 }884 }885 pointer++;886 }887};888// Define some regex patterns for matching boundaries.889diff_match_patch.nonAlphaNumericRegex_ = /[^a-zA-Z0-9]/;890diff_match_patch.whitespaceRegex_ = /\s/;891diff_match_patch.linebreakRegex_ = /[\r\n]/;892diff_match_patch.blanklineEndRegex_ = /\n\r?\n$/;893diff_match_patch.blanklineStartRegex_ = /^\r?\n\r?\n/;894/**895 * Reduce the number of edits by eliminating operationally trivial equalities.896 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.897 */898diff_match_patch.prototype.diff_cleanupEfficiency = function(diffs) {899 var changes = false;900 var equalities = []; // Stack of indices where equalities are found.901 var equalitiesLength = 0; // Keeping our own length var is faster in JS.902 /** @type {?string} */903 var lastequality = null;904 // Always equal to diffs[equalities[equalitiesLength - 1]][1]905 var pointer = 0; // Index of current position.906 // Is there an insertion operation before the last equality.907 var pre_ins = false;908 // Is there a deletion operation before the last equality.909 var pre_del = false;910 // Is there an insertion operation after the last equality.911 var post_ins = false;912 // Is there a deletion operation after the last equality.913 var post_del = false;914 while (pointer < diffs.length) {915 if (diffs[pointer][0] == DIFF_EQUAL) { // Equality found.916 if (diffs[pointer][1].length < this.Diff_EditCost &&917 (post_ins || post_del)) {918 // Candidate found.919 equalities[equalitiesLength++] = pointer;920 pre_ins = post_ins;921 pre_del = post_del;922 lastequality = diffs[pointer][1];923 } else {924 // Not a candidate, and can never become one.925 equalitiesLength = 0;926 lastequality = null;927 }928 post_ins = post_del = false;929 } else { // An insertion or deletion.930 if (diffs[pointer][0] == DIFF_DELETE) {931 post_del = true;932 } else {933 post_ins = true;934 }935 /*936 * Five types to be split:937 * <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>938 * <ins>A</ins>X<ins>C</ins><del>D</del>939 * <ins>A</ins><del>B</del>X<ins>C</ins>940 * <ins>A</del>X<ins>C</ins><del>D</del>941 * <ins>A</ins><del>B</del>X<del>C</del>942 */943 if (lastequality && ((pre_ins && pre_del && post_ins && post_del) ||944 ((lastequality.length < this.Diff_EditCost / 2) &&945 (pre_ins + pre_del + post_ins + post_del) == 3))) {946 // Duplicate record.947 diffs.splice(equalities[equalitiesLength - 1], 0,948 [DIFF_DELETE, lastequality]);949 // Change second copy to insert.950 diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;951 equalitiesLength--; // Throw away the equality we just deleted;952 lastequality = null;953 if (pre_ins && pre_del) {954 // No changes made which could affect previous entry, keep going.955 post_ins = post_del = true;956 equalitiesLength = 0;957 } else {958 equalitiesLength--; // Throw away the previous equality.959 pointer = equalitiesLength > 0 ?960 equalities[equalitiesLength - 1] : -1;961 post_ins = post_del = false;962 }963 changes = true;964 }965 }966 pointer++;967 }968 if (changes) {969 this.diff_cleanupMerge(diffs);970 }971};972/**973 * Reorder and merge like edit sections. Merge equalities.974 * Any edit section can move as long as it doesn't cross an equality.975 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.976 */977diff_match_patch.prototype.diff_cleanupMerge = function(diffs) {978 diffs.push([DIFF_EQUAL, '']); // Add a dummy entry at the end.979 var pointer = 0;980 var count_delete = 0;981 var count_insert = 0;982 var text_delete = '';983 var text_insert = '';984 var commonlength;985 while (pointer < diffs.length) {986 switch (diffs[pointer][0]) {987 case DIFF_INSERT:988 count_insert++;989 text_insert += diffs[pointer][1];990 pointer++;991 break;992 case DIFF_DELETE:993 count_delete++;994 text_delete += diffs[pointer][1];995 pointer++;996 break;997 case DIFF_EQUAL:998 // Upon reaching an equality, check for prior redundancies.999 if (count_delete + count_insert > 1) {1000 if (count_delete !== 0 && count_insert !== 0) {1001 // Factor out any common prefixies.1002 commonlength = this.diff_commonPrefix(text_insert, text_delete);1003 if (commonlength !== 0) {1004 if ((pointer - count_delete - count_insert) > 0 &&1005 diffs[pointer - count_delete - count_insert - 1][0] ==1006 DIFF_EQUAL) {1007 diffs[pointer - count_delete - count_insert - 1][1] +=1008 text_insert.substring(0, commonlength);1009 } else {1010 diffs.splice(0, 0, [DIFF_EQUAL,1011 text_insert.substring(0, commonlength)]);1012 pointer++;1013 }1014 text_insert = text_insert.substring(commonlength);1015 text_delete = text_delete.substring(commonlength);1016 }1017 // Factor out any common suffixies.1018 commonlength = this.diff_commonSuffix(text_insert, text_delete);1019 if (commonlength !== 0) {1020 diffs[pointer][1] = text_insert.substring(text_insert.length -1021 commonlength) + diffs[pointer][1];1022 text_insert = text_insert.substring(0, text_insert.length -1023 commonlength);1024 text_delete = text_delete.substring(0, text_delete.length -1025 commonlength);1026 }1027 }1028 // Delete the offending records and add the merged ones.1029 if (count_delete === 0) {1030 diffs.splice(pointer - count_insert,1031 count_delete + count_insert, [DIFF_INSERT, text_insert]);1032 } else if (count_insert === 0) {1033 diffs.splice(pointer - count_delete,1034 count_delete + count_insert, [DIFF_DELETE, text_delete]);1035 } else {1036 diffs.splice(pointer - count_delete - count_insert,1037 count_delete + count_insert, [DIFF_DELETE, text_delete],1038 [DIFF_INSERT, text_insert]);1039 }1040 pointer = pointer - count_delete - count_insert +1041 (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;1042 } else if (pointer !== 0 && diffs[pointer - 1][0] == DIFF_EQUAL) {1043 // Merge this equality with the previous one.1044 diffs[pointer - 1][1] += diffs[pointer][1];1045 diffs.splice(pointer, 1);1046 } else {1047 pointer++;1048 }1049 count_insert = 0;1050 count_delete = 0;1051 text_delete = '';1052 text_insert = '';1053 break;1054 }1055 }1056 if (diffs[diffs.length - 1][1] === '') {1057 diffs.pop(); // Remove the dummy entry at the end.1058 }1059 // Second pass: look for single edits surrounded on both sides by equalities1060 // which can be shifted sideways to eliminate an equality.1061 // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC1062 var changes = false;1063 pointer = 1;1064 // Intentionally ignore the first and last element (don't need checking).1065 while (pointer < diffs.length - 1) {1066 if (diffs[pointer - 1][0] == DIFF_EQUAL &&1067 diffs[pointer + 1][0] == DIFF_EQUAL) {1068 // This is a single edit surrounded by equalities.1069 if (diffs[pointer][1].substring(diffs[pointer][1].length -1070 diffs[pointer - 1][1].length) == diffs[pointer - 1][1]) {1071 // Shift the edit over the previous equality.1072 diffs[pointer][1] = diffs[pointer - 1][1] +1073 diffs[pointer][1].substring(0, diffs[pointer][1].length -1074 diffs[pointer - 1][1].length);1075 diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1];1076 diffs.splice(pointer - 1, 1);1077 changes = true;1078 } else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) ==1079 diffs[pointer + 1][1]) {1080 // Shift the edit over the next equality.1081 diffs[pointer - 1][1] += diffs[pointer + 1][1];1082 diffs[pointer][1] =1083 diffs[pointer][1].substring(diffs[pointer + 1][1].length) +1084 diffs[pointer + 1][1];1085 diffs.splice(pointer + 1, 1);1086 changes = true;1087 }1088 }1089 pointer++;1090 }1091 // If shifts were made, the diff needs reordering and another shift sweep.1092 if (changes) {1093 this.diff_cleanupMerge(diffs);1094 }1095};1096/**1097 * loc is a location in text1, compute and return the equivalent location in1098 * text2.1099 * e.g. 'The cat' vs 'The big cat', 1->1, 5->81100 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1101 * @param {number} loc Location within text1.1102 * @return {number} Location within text2.1103 */1104diff_match_patch.prototype.diff_xIndex = function(diffs, loc) {1105 var chars1 = 0;1106 var chars2 = 0;1107 var last_chars1 = 0;1108 var last_chars2 = 0;1109 var x;1110 for (x = 0; x < diffs.length; x++) {1111 if (diffs[x][0] !== DIFF_INSERT) { // Equality or deletion.1112 chars1 += diffs[x][1].length;1113 }1114 if (diffs[x][0] !== DIFF_DELETE) { // Equality or insertion.1115 chars2 += diffs[x][1].length;1116 }1117 if (chars1 > loc) { // Overshot the location.1118 break;1119 }1120 last_chars1 = chars1;1121 last_chars2 = chars2;1122 }1123 // Was the location was deleted?1124 if (diffs.length != x && diffs[x][0] === DIFF_DELETE) {1125 return last_chars2;1126 }1127 // Add the remaining character length.1128 return last_chars2 + (loc - last_chars1);1129};1130/**1131 * Convert a diff array into a pretty HTML report.1132 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1133 * @return {string} HTML representation.1134 */1135diff_match_patch.prototype.diff_prettyHtml = function(diffs) {1136 var html = [];1137 var pattern_amp = /&/g;1138 var pattern_lt = /</g;1139 var pattern_gt = />/g;1140 var pattern_para = /\n/g;1141 for (var x = 0; x < diffs.length; x++) {1142 var op = diffs[x][0]; // Operation (insert, delete, equal)1143 var data = diffs[x][1]; // Text of change.1144 var text = data.replace(pattern_amp, '&amp;').replace(pattern_lt, '&lt;')1145 .replace(pattern_gt, '&gt;').replace(pattern_para, '&para;<br>');1146 switch (op) {1147 case DIFF_INSERT:1148 html[x] = '<ins style="background:#e6ffe6;">' + text + '</ins>';1149 break;1150 case DIFF_DELETE:1151 html[x] = '<del style="background:#ffe6e6;">' + text + '</del>';1152 break;1153 case DIFF_EQUAL:1154 html[x] = '<span>' + text + '</span>';1155 break;1156 }1157 }1158 return html.join('');1159};1160/**1161 * Compute and return the source text (all equalities and deletions).1162 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1163 * @return {string} Source text.1164 */1165diff_match_patch.prototype.diff_text1 = function(diffs) {1166 var text = [];1167 for (var x = 0; x < diffs.length; x++) {1168 if (diffs[x][0] !== DIFF_INSERT) {1169 text[x] = diffs[x][1];1170 }1171 }1172 return text.join('');1173};1174/**1175 * Compute and return the destination text (all equalities and insertions).1176 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1177 * @return {string} Destination text.1178 */1179diff_match_patch.prototype.diff_text2 = function(diffs) {1180 var text = [];1181 for (var x = 0; x < diffs.length; x++) {1182 if (diffs[x][0] !== DIFF_DELETE) {1183 text[x] = diffs[x][1];1184 }1185 }1186 return text.join('');1187};1188/**1189 * Compute the Levenshtein distance; the number of inserted, deleted or1190 * substituted characters.1191 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1192 * @return {number} Number of changes.1193 */1194diff_match_patch.prototype.diff_levenshtein = function(diffs) {1195 var levenshtein = 0;1196 var insertions = 0;1197 var deletions = 0;1198 for (var x = 0; x < diffs.length; x++) {1199 var op = diffs[x][0];1200 var data = diffs[x][1];1201 switch (op) {1202 case DIFF_INSERT:1203 insertions += data.length;1204 break;1205 case DIFF_DELETE:1206 deletions += data.length;1207 break;1208 case DIFF_EQUAL:1209 // A deletion and an insertion is one substitution.1210 levenshtein += Math.max(insertions, deletions);1211 insertions = 0;1212 deletions = 0;1213 break;1214 }1215 }1216 levenshtein += Math.max(insertions, deletions);1217 return levenshtein;1218};1219/**1220 * Crush the diff into an encoded string which describes the operations1221 * required to transform text1 into text2.1222 * E.g. =3\t-2\t+ing -> Keep 3 chars, delete 2 chars, insert 'ing'.1223 * Operations are tab-separated. Inserted text is escaped using %xx notation.1224 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1225 * @return {string} Delta text.1226 */1227diff_match_patch.prototype.diff_toDelta = function(diffs) {1228 var text = [];1229 for (var x = 0; x < diffs.length; x++) {1230 switch (diffs[x][0]) {1231 case DIFF_INSERT:1232 text[x] = '+' + encodeURI(diffs[x][1]);1233 break;1234 case DIFF_DELETE:1235 text[x] = '-' + diffs[x][1].length;1236 break;1237 case DIFF_EQUAL:1238 text[x] = '=' + diffs[x][1].length;1239 break;1240 }1241 }1242 return text.join('\t').replace(/%20/g, ' ');1243};1244/**1245 * Given the original text1, and an encoded string which describes the1246 * operations required to transform text1 into text2, compute the full diff.1247 * @param {string} text1 Source string for the diff.1248 * @param {string} delta Delta text.1249 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.1250 * @throws {!Error} If invalid input.1251 */1252diff_match_patch.prototype.diff_fromDelta = function(text1, delta) {1253 var diffs = [];1254 var diffsLength = 0; // Keeping our own length var is faster in JS.1255 var pointer = 0; // Cursor in text11256 var tokens = delta.split(/\t/g);1257 for (var x = 0; x < tokens.length; x++) {1258 // Each token begins with a one character parameter which specifies the1259 // operation of this token (delete, insert, equality).1260 var param = tokens[x].substring(1);1261 switch (tokens[x].charAt(0)) {1262 case '+':1263 try {1264 diffs[diffsLength++] = [DIFF_INSERT, decodeURI(param)];1265 } catch (ex) {1266 // Malformed URI sequence.1267 throw new Error('Illegal escape in diff_fromDelta: ' + param);1268 }1269 break;1270 case '-':1271 // Fall through.1272 case '=':1273 var n = parseInt(param, 10);1274 if (isNaN(n) || n < 0) {1275 throw new Error('Invalid number in diff_fromDelta: ' + param);1276 }1277 var text = text1.substring(pointer, pointer += n);1278 if (tokens[x].charAt(0) == '=') {1279 diffs[diffsLength++] = [DIFF_EQUAL, text];1280 } else {1281 diffs[diffsLength++] = [DIFF_DELETE, text];1282 }1283 break;1284 default:1285 // Blank tokens are ok (from a trailing \t).1286 // Anything else is an error.1287 if (tokens[x]) {1288 throw new Error('Invalid diff operation in diff_fromDelta: ' +1289 tokens[x]);1290 }1291 }1292 }1293 if (pointer != text1.length) {1294 throw new Error('Delta length (' + pointer +1295 ') does not equal source text length (' + text1.length + ').');1296 }1297 return diffs;1298};1299// MATCH FUNCTIONS1300/**1301 * Locate the best instance of 'pattern' in 'text' near 'loc'.1302 * @param {string} text The text to search.1303 * @param {string} pattern The pattern to search for.1304 * @param {number} loc The location to search around.1305 * @return {number} Best match index or -1.1306 */1307diff_match_patch.prototype.match_main = function(text, pattern, loc) {1308 // Check for null inputs.1309 if (text == null || pattern == null || loc == null) {1310 throw new Error('Null input. (match_main)');1311 }1312 loc = Math.max(0, Math.min(loc, text.length));1313 if (text == pattern) {1314 // Shortcut (potentially not guaranteed by the algorithm)1315 return 0;1316 } else if (!text.length) {1317 // Nothing to match.1318 return -1;1319 } else if (text.substring(loc, loc + pattern.length) == pattern) {1320 // Perfect match at the perfect spot! (Includes case of null pattern)1321 return loc;1322 } else {1323 // Do a fuzzy compare.1324 return this.match_bitap_(text, pattern, loc);1325 }1326};1327/**1328 * Locate the best instance of 'pattern' in 'text' near 'loc' using the1329 * Bitap algorithm.1330 * @param {string} text The text to search.1331 * @param {string} pattern The pattern to search for.1332 * @param {number} loc The location to search around.1333 * @return {number} Best match index or -1.1334 * @private1335 */1336diff_match_patch.prototype.match_bitap_ = function(text, pattern, loc) {1337 if (pattern.length > this.Match_MaxBits) {1338 throw new Error('Pattern too long for this browser.');1339 }1340 // Initialise the alphabet.1341 var s = this.match_alphabet_(pattern);1342 var dmp = this; // 'this' becomes 'window' in a closure.1343 /**1344 * Compute and return the score for a match with e errors and x location.1345 * Accesses loc and pattern through being a closure.1346 * @param {number} e Number of errors in match.1347 * @param {number} x Location of match.1348 * @return {number} Overall score for match (0.0 = good, 1.0 = bad).1349 * @private1350 */1351 function match_bitapScore_(e, x) {1352 var accuracy = e / pattern.length;1353 var proximity = Math.abs(loc - x);1354 if (!dmp.Match_Distance) {1355 // Dodge divide by zero error.1356 return proximity ? 1.0 : accuracy;1357 }1358 return accuracy + (proximity / dmp.Match_Distance);1359 }1360 // Highest score beyond which we give up.1361 var score_threshold = this.Match_Threshold;1362 // Is there a nearby exact match? (speedup)1363 var best_loc = text.indexOf(pattern, loc);1364 if (best_loc != -1) {1365 score_threshold = Math.min(match_bitapScore_(0, best_loc), score_threshold);1366 // What about in the other direction? (speedup)1367 best_loc = text.lastIndexOf(pattern, loc + pattern.length);1368 if (best_loc != -1) {1369 score_threshold =1370 Math.min(match_bitapScore_(0, best_loc), score_threshold);1371 }1372 }1373 // Initialise the bit arrays.1374 var matchmask = 1 << (pattern.length - 1);1375 best_loc = -1;1376 var bin_min, bin_mid;1377 var bin_max = pattern.length + text.length;1378 var last_rd;1379 for (var d = 0; d < pattern.length; d++) {1380 // Scan for the best match; each iteration allows for one more error.1381 // Run a binary search to determine how far from 'loc' we can stray at this1382 // error level.1383 bin_min = 0;1384 bin_mid = bin_max;1385 while (bin_min < bin_mid) {1386 if (match_bitapScore_(d, loc + bin_mid) <= score_threshold) {1387 bin_min = bin_mid;1388 } else {1389 bin_max = bin_mid;1390 }1391 bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min);1392 }1393 // Use the result from this iteration as the maximum for the next.1394 bin_max = bin_mid;1395 var start = Math.max(1, loc - bin_mid + 1);1396 var finish = Math.min(loc + bin_mid, text.length) + pattern.length;1397 var rd = Array(finish + 2);1398 rd[finish + 1] = (1 << d) - 1;1399 for (var j = finish; j >= start; j--) {1400 // The alphabet (s) is a sparse hash, so the following line generates1401 // warnings.1402 var charMatch = s[text.charAt(j - 1)];1403 if (d === 0) { // First pass: exact match.1404 rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;1405 } else { // Subsequent passes: fuzzy match.1406 rd[j] = (((rd[j + 1] << 1) | 1) & charMatch) |1407 (((last_rd[j + 1] | last_rd[j]) << 1) | 1) |1408 last_rd[j + 1];1409 }1410 if (rd[j] & matchmask) {1411 var score = match_bitapScore_(d, j - 1);1412 // This match will almost certainly be better than any existing match.1413 // But check anyway.1414 if (score <= score_threshold) {1415 // Told you so.1416 score_threshold = score;1417 best_loc = j - 1;1418 if (best_loc > loc) {1419 // When passing loc, don't exceed our current distance from loc.1420 start = Math.max(1, 2 * loc - best_loc);1421 } else {1422 // Already passed loc, downhill from here on in.1423 break;1424 }1425 }1426 }1427 }1428 // No hope for a (better) match at greater error levels.1429 if (match_bitapScore_(d + 1, loc) > score_threshold) {1430 break;1431 }1432 last_rd = rd;1433 }1434 return best_loc;1435};1436/**1437 * Initialise the alphabet for the Bitap algorithm.1438 * @param {string} pattern The text to encode.1439 * @return {!Object} Hash of character locations.1440 * @private1441 */1442diff_match_patch.prototype.match_alphabet_ = function(pattern) {1443 var s = {};1444 for (var i = 0; i < pattern.length; i++) {1445 s[pattern.charAt(i)] = 0;1446 }1447 for (var i = 0; i < pattern.length; i++) {1448 s[pattern.charAt(i)] |= 1 << (pattern.length - i - 1);1449 }1450 return s;1451};1452// PATCH FUNCTIONS1453/**1454 * Increase the context until it is unique,1455 * but don't let the pattern expand beyond Match_MaxBits.1456 * @param {!diff_match_patch.patch_obj} patch The patch to grow.1457 * @param {string} text Source text.1458 * @private1459 */1460diff_match_patch.prototype.patch_addContext_ = function(patch, text) {1461 if (text.length == 0) {1462 return;1463 }1464 var pattern = text.substring(patch.start2, patch.start2 + patch.length1);1465 var padding = 0;1466 // Look for the first and last matches of pattern in text. If two different1467 // matches are found, increase the pattern length.1468 while (text.indexOf(pattern) != text.lastIndexOf(pattern) &&1469 pattern.length < this.Match_MaxBits - this.Patch_Margin -1470 this.Patch_Margin) {1471 padding += this.Patch_Margin;1472 pattern = text.substring(patch.start2 - padding,1473 patch.start2 + patch.length1 + padding);1474 }1475 // Add one chunk for good luck.1476 padding += this.Patch_Margin;1477 // Add the prefix.1478 var prefix = text.substring(patch.start2 - padding, patch.start2);1479 if (prefix) {1480 patch.diffs.unshift([DIFF_EQUAL, prefix]);1481 }1482 // Add the suffix.1483 var suffix = text.substring(patch.start2 + patch.length1,1484 patch.start2 + patch.length1 + padding);1485 if (suffix) {1486 patch.diffs.push([DIFF_EQUAL, suffix]);1487 }1488 // Roll back the start points.1489 patch.start1 -= prefix.length;1490 patch.start2 -= prefix.length;1491 // Extend the lengths.1492 patch.length1 += prefix.length + suffix.length;1493 patch.length2 += prefix.length + suffix.length;1494};1495/**1496 * Compute a list of patches to turn text1 into text2.1497 * Use diffs if provided, otherwise compute it ourselves.1498 * There are four ways to call this function, depending on what data is1499 * available to the caller:1500 * Method 1:1501 * a = text1, b = text21502 * Method 2:1503 * a = diffs1504 * Method 3 (optimal):1505 * a = text1, b = diffs1506 * Method 4 (deprecated, use method 3):1507 * a = text1, b = text2, c = diffs1508 *1509 * @param {string|!Array.<!diff_match_patch.Diff>} a text1 (methods 1,3,4) or1510 * Array of diff tuples for text1 to text2 (method 2).1511 * @param {string|!Array.<!diff_match_patch.Diff>} opt_b text2 (methods 1,4) or1512 * Array of diff tuples for text1 to text2 (method 3) or undefined (method 2).1513 * @param {string|!Array.<!diff_match_patch.Diff>} opt_c Array of diff tuples1514 * for text1 to text2 (method 4) or undefined (methods 1,2,3).1515 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1516 */1517diff_match_patch.prototype.patch_make = function(a, opt_b, opt_c) {1518 var text1, diffs;1519 if (typeof a == 'string' && typeof opt_b == 'string' &&1520 typeof opt_c == 'undefined') {1521 // Method 1: text1, text21522 // Compute diffs from text1 and text2.1523 text1 = /** @type {string} */(a);1524 diffs = this.diff_main(text1, /** @type {string} */(opt_b), true);1525 if (diffs.length > 2) {1526 this.diff_cleanupSemantic(diffs);1527 this.diff_cleanupEfficiency(diffs);1528 }1529 } else if (a && typeof a == 'object' && typeof opt_b == 'undefined' &&1530 typeof opt_c == 'undefined') {1531 // Method 2: diffs1532 // Compute text1 from diffs.1533 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(a);1534 text1 = this.diff_text1(diffs);1535 } else if (typeof a == 'string' && opt_b && typeof opt_b == 'object' &&1536 typeof opt_c == 'undefined') {1537 // Method 3: text1, diffs1538 text1 = /** @type {string} */(a);1539 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(opt_b);1540 } else if (typeof a == 'string' && typeof opt_b == 'string' &&1541 opt_c && typeof opt_c == 'object') {1542 // Method 4: text1, text2, diffs1543 // text2 is not used.1544 text1 = /** @type {string} */(a);1545 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(opt_c);1546 } else {1547 throw new Error('Unknown call format to patch_make.');1548 }1549 if (diffs.length === 0) {1550 return []; // Get rid of the null case.1551 }1552 var patches = [];1553 var patch = new diff_match_patch.patch_obj();1554 var patchDiffLength = 0; // Keeping our own length var is faster in JS.1555 var char_count1 = 0; // Number of characters into the text1 string.1556 var char_count2 = 0; // Number of characters into the text2 string.1557 // Start with text1 (prepatch_text) and apply the diffs until we arrive at1558 // text2 (postpatch_text). We recreate the patches one by one to determine1559 // context info.1560 var prepatch_text = text1;1561 var postpatch_text = text1;1562 for (var x = 0; x < diffs.length; x++) {1563 var diff_type = diffs[x][0];1564 var diff_text = diffs[x][1];1565 if (!patchDiffLength && diff_type !== DIFF_EQUAL) {1566 // A new patch starts here.1567 patch.start1 = char_count1;1568 patch.start2 = char_count2;1569 }1570 switch (diff_type) {1571 case DIFF_INSERT:1572 patch.diffs[patchDiffLength++] = diffs[x];1573 patch.length2 += diff_text.length;1574 postpatch_text = postpatch_text.substring(0, char_count2) + diff_text +1575 postpatch_text.substring(char_count2);1576 break;1577 case DIFF_DELETE:1578 patch.length1 += diff_text.length;1579 patch.diffs[patchDiffLength++] = diffs[x];1580 postpatch_text = postpatch_text.substring(0, char_count2) +1581 postpatch_text.substring(char_count2 +1582 diff_text.length);1583 break;1584 case DIFF_EQUAL:1585 if (diff_text.length <= 2 * this.Patch_Margin &&1586 patchDiffLength && diffs.length != x + 1) {1587 // Small equality inside a patch.1588 patch.diffs[patchDiffLength++] = diffs[x];1589 patch.length1 += diff_text.length;1590 patch.length2 += diff_text.length;1591 } else if (diff_text.length >= 2 * this.Patch_Margin) {1592 // Time for a new patch.1593 if (patchDiffLength) {1594 this.patch_addContext_(patch, prepatch_text);1595 patches.push(patch);1596 patch = new diff_match_patch.patch_obj();1597 patchDiffLength = 0;1598 // Unlike Unidiff, our patch lists have a rolling context.1599 // http://code.google.com/p/google-diff-match-patch/wiki/Unidiff1600 // Update prepatch text & pos to reflect the application of the1601 // just completed patch.1602 prepatch_text = postpatch_text;1603 char_count1 = char_count2;1604 }1605 }1606 break;1607 }1608 // Update the current character count.1609 if (diff_type !== DIFF_INSERT) {1610 char_count1 += diff_text.length;1611 }1612 if (diff_type !== DIFF_DELETE) {1613 char_count2 += diff_text.length;1614 }1615 }1616 // Pick up the leftover patch if not empty.1617 if (patchDiffLength) {1618 this.patch_addContext_(patch, prepatch_text);1619 patches.push(patch);1620 }1621 return patches;1622};1623/**1624 * Given an array of patches, return another array that is identical.1625 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1626 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1627 */1628diff_match_patch.prototype.patch_deepCopy = function(patches) {1629 // Making deep copies is hard in JavaScript.1630 var patchesCopy = [];1631 for (var x = 0; x < patches.length; x++) {1632 var patch = patches[x];1633 var patchCopy = new diff_match_patch.patch_obj();1634 patchCopy.diffs = [];1635 for (var y = 0; y < patch.diffs.length; y++) {1636 patchCopy.diffs[y] = patch.diffs[y].slice();1637 }1638 patchCopy.start1 = patch.start1;1639 patchCopy.start2 = patch.start2;1640 patchCopy.length1 = patch.length1;1641 patchCopy.length2 = patch.length2;1642 patchesCopy[x] = patchCopy;1643 }1644 return patchesCopy;1645};1646/**1647 * Merge a set of patches onto the text. Return a patched text, as well1648 * as a list of true/false values indicating which patches were applied.1649 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1650 * @param {string} text Old text.1651 * @return {!Array.<string|!Array.<boolean>>} Two element Array, containing the1652 * new text and an array of boolean values.1653 */1654diff_match_patch.prototype.patch_apply = function(patches, text) {1655 if (patches.length == 0) {1656 return [text, []];1657 }1658 // Deep copy the patches so that no changes are made to originals.1659 patches = this.patch_deepCopy(patches);1660 var nullPadding = this.patch_addPadding(patches);1661 text = nullPadding + text + nullPadding;1662 this.patch_splitMax(patches);1663 // delta keeps track of the offset between the expected and actual location1664 // of the previous patch. If there are patches expected at positions 10 and1665 // 20, but the first patch was found at 12, delta is 2 and the second patch1666 // has an effective expected position of 22.1667 var delta = 0;1668 var results = [];1669 for (var x = 0; x < patches.length; x++) {1670 var expected_loc = patches[x].start2 + delta;1671 var text1 = this.diff_text1(patches[x].diffs);1672 var start_loc;1673 var end_loc = -1;1674 if (text1.length > this.Match_MaxBits) {1675 // patch_splitMax will only provide an oversized pattern in the case of1676 // a monster delete.1677 start_loc = this.match_main(text, text1.substring(0, this.Match_MaxBits),1678 expected_loc);1679 if (start_loc != -1) {1680 end_loc = this.match_main(text,1681 text1.substring(text1.length - this.Match_MaxBits),1682 expected_loc + text1.length - this.Match_MaxBits);1683 if (end_loc == -1 || start_loc >= end_loc) {1684 // Can't find valid trailing context. Drop this patch.1685 start_loc = -1;1686 }1687 }1688 } else {1689 start_loc = this.match_main(text, text1, expected_loc);1690 }1691 if (start_loc == -1) {1692 // No match found. :(1693 results[x] = false;1694 // Subtract the delta for this failed patch from subsequent patches.1695 delta -= patches[x].length2 - patches[x].length1;1696 } else {1697 // Found a match. :)1698 results[x] = true;1699 delta = start_loc - expected_loc;1700 var text2;1701 if (end_loc == -1) {1702 text2 = text.substring(start_loc, start_loc + text1.length);1703 } else {1704 text2 = text.substring(start_loc, end_loc + this.Match_MaxBits);1705 }1706 if (text1 == text2) {1707 // Perfect match, just shove the replacement text in.1708 text = text.substring(0, start_loc) +1709 this.diff_text2(patches[x].diffs) +1710 text.substring(start_loc + text1.length);1711 } else {1712 // Imperfect match. Run a diff to get a framework of equivalent1713 // indices.1714 var diffs = this.diff_main(text1, text2, false);1715 if (text1.length > this.Match_MaxBits &&1716 this.diff_levenshtein(diffs) / text1.length >1717 this.Patch_DeleteThreshold) {1718 // The end points match, but the content is unacceptably bad.1719 results[x] = false;1720 } else {1721 this.diff_cleanupSemanticLossless(diffs);1722 var index1 = 0;1723 var index2;1724 for (var y = 0; y < patches[x].diffs.length; y++) {1725 var mod = patches[x].diffs[y];1726 if (mod[0] !== DIFF_EQUAL) {1727 index2 = this.diff_xIndex(diffs, index1);1728 }1729 if (mod[0] === DIFF_INSERT) { // Insertion1730 text = text.substring(0, start_loc + index2) + mod[1] +1731 text.substring(start_loc + index2);1732 } else if (mod[0] === DIFF_DELETE) { // Deletion1733 text = text.substring(0, start_loc + index2) +1734 text.substring(start_loc + this.diff_xIndex(diffs,1735 index1 + mod[1].length));1736 }1737 if (mod[0] !== DIFF_DELETE) {1738 index1 += mod[1].length;1739 }1740 }1741 }1742 }1743 }1744 }1745 // Strip the padding off.1746 text = text.substring(nullPadding.length, text.length - nullPadding.length);1747 return [text, results];1748};1749/**1750 * Add some padding on text start and end so that edges can match something.1751 * Intended to be called only from within patch_apply.1752 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1753 * @return {string} The padding string added to each side.1754 */1755diff_match_patch.prototype.patch_addPadding = function(patches) {1756 var paddingLength = this.Patch_Margin;1757 var nullPadding = '';1758 for (var x = 1; x <= paddingLength; x++) {1759 nullPadding += String.fromCharCode(x);1760 }1761 // Bump all the patches forward.1762 for (var x = 0; x < patches.length; x++) {1763 patches[x].start1 += paddingLength;1764 patches[x].start2 += paddingLength;1765 }1766 // Add some padding on start of first diff.1767 var patch = patches[0];1768 var diffs = patch.diffs;1769 if (diffs.length == 0 || diffs[0][0] != DIFF_EQUAL) {1770 // Add nullPadding equality.1771 diffs.unshift([DIFF_EQUAL, nullPadding]);1772 patch.start1 -= paddingLength; // Should be 0.1773 patch.start2 -= paddingLength; // Should be 0.1774 patch.length1 += paddingLength;1775 patch.length2 += paddingLength;1776 } else if (paddingLength > diffs[0][1].length) {1777 // Grow first equality.1778 var extraLength = paddingLength - diffs[0][1].length;1779 diffs[0][1] = nullPadding.substring(diffs[0][1].length) + diffs[0][1];1780 patch.start1 -= extraLength;1781 patch.start2 -= extraLength;1782 patch.length1 += extraLength;1783 patch.length2 += extraLength;1784 }1785 // Add some padding on end of last diff.1786 patch = patches[patches.length - 1];1787 diffs = patch.diffs;1788 if (diffs.length == 0 || diffs[diffs.length - 1][0] != DIFF_EQUAL) {1789 // Add nullPadding equality.1790 diffs.push([DIFF_EQUAL, nullPadding]);1791 patch.length1 += paddingLength;1792 patch.length2 += paddingLength;1793 } else if (paddingLength > diffs[diffs.length - 1][1].length) {1794 // Grow last equality.1795 var extraLength = paddingLength - diffs[diffs.length - 1][1].length;1796 diffs[diffs.length - 1][1] += nullPadding.substring(0, extraLength);1797 patch.length1 += extraLength;1798 patch.length2 += extraLength;1799 }1800 return nullPadding;1801};1802/**1803 * Look through the patches and break up any which are longer than the maximum1804 * limit of the match algorithm.1805 * Intended to be called only from within patch_apply.1806 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1807 */1808diff_match_patch.prototype.patch_splitMax = function(patches) {1809 var patch_size = this.Match_MaxBits;1810 for (var x = 0; x < patches.length; x++) {1811 if (patches[x].length1 <= patch_size) {1812 continue;1813 }1814 var bigpatch = patches[x];1815 // Remove the big old patch.1816 patches.splice(x--, 1);1817 var start1 = bigpatch.start1;1818 var start2 = bigpatch.start2;1819 var precontext = '';1820 while (bigpatch.diffs.length !== 0) {1821 // Create one of several smaller patches.1822 var patch = new diff_match_patch.patch_obj();1823 var empty = true;1824 patch.start1 = start1 - precontext.length;1825 patch.start2 = start2 - precontext.length;1826 if (precontext !== '') {1827 patch.length1 = patch.length2 = precontext.length;1828 patch.diffs.push([DIFF_EQUAL, precontext]);1829 }1830 while (bigpatch.diffs.length !== 0 &&1831 patch.length1 < patch_size - this.Patch_Margin) {1832 var diff_type = bigpatch.diffs[0][0];1833 var diff_text = bigpatch.diffs[0][1];1834 if (diff_type === DIFF_INSERT) {1835 // Insertions are harmless.1836 patch.length2 += diff_text.length;1837 start2 += diff_text.length;1838 patch.diffs.push(bigpatch.diffs.shift());1839 empty = false;1840 } else if (diff_type === DIFF_DELETE && patch.diffs.length == 1 &&1841 patch.diffs[0][0] == DIFF_EQUAL &&1842 diff_text.length > 2 * patch_size) {1843 // This is a large deletion. Let it pass in one chunk.1844 patch.length1 += diff_text.length;1845 start1 += diff_text.length;1846 empty = false;1847 patch.diffs.push([diff_type, diff_text]);1848 bigpatch.diffs.shift();1849 } else {1850 // Deletion or equality. Only take as much as we can stomach.1851 diff_text = diff_text.substring(0,1852 patch_size - patch.length1 - this.Patch_Margin);1853 patch.length1 += diff_text.length;1854 start1 += diff_text.length;1855 if (diff_type === DIFF_EQUAL) {1856 patch.length2 += diff_text.length;1857 start2 += diff_text.length;1858 } else {1859 empty = false;1860 }1861 patch.diffs.push([diff_type, diff_text]);1862 if (diff_text == bigpatch.diffs[0][1]) {1863 bigpatch.diffs.shift();1864 } else {1865 bigpatch.diffs[0][1] =1866 bigpatch.diffs[0][1].substring(diff_text.length);1867 }1868 }1869 }1870 // Compute the head context for the next patch.1871 precontext = this.diff_text2(patch.diffs);1872 precontext =1873 precontext.substring(precontext.length - this.Patch_Margin);1874 // Append the end context for this patch.1875 var postcontext = this.diff_text1(bigpatch.diffs)1876 .substring(0, this.Patch_Margin);1877 if (postcontext !== '') {1878 patch.length1 += postcontext.length;1879 patch.length2 += postcontext.length;1880 if (patch.diffs.length !== 0 &&1881 patch.diffs[patch.diffs.length - 1][0] === DIFF_EQUAL) {1882 patch.diffs[patch.diffs.length - 1][1] += postcontext;1883 } else {1884 patch.diffs.push([DIFF_EQUAL, postcontext]);1885 }1886 }1887 if (!empty) {1888 patches.splice(++x, 0, patch);1889 }1890 }1891 }1892};1893/**1894 * Take a list of patches and return a textual representation.1895 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1896 * @return {string} Text representation of patches.1897 */1898diff_match_patch.prototype.patch_toText = function(patches) {1899 var text = [];1900 for (var x = 0; x < patches.length; x++) {1901 text[x] = patches[x];1902 }1903 return text.join('');1904};1905/**1906 * Parse a textual representation of patches and return a list of Patch objects.1907 * @param {string} textline Text representation of patches.1908 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1909 * @throws {!Error} If invalid input.1910 */1911diff_match_patch.prototype.patch_fromText = function(textline) {1912 var patches = [];1913 if (!textline) {1914 return patches;1915 }1916 var text = textline.split('\n');1917 var textPointer = 0;1918 var patchHeader = /^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/;1919 while (textPointer < text.length) {1920 var m = text[textPointer].match(patchHeader);1921 if (!m) {1922 throw new Error('Invalid patch string: ' + text[textPointer]);1923 }1924 var patch = new diff_match_patch.patch_obj();1925 patches.push(patch);1926 patch.start1 = parseInt(m[1], 10);1927 if (m[2] === '') {1928 patch.start1--;1929 patch.length1 = 1;1930 } else if (m[2] == '0') {1931 patch.length1 = 0;1932 } else {1933 patch.start1--;1934 patch.length1 = parseInt(m[2], 10);1935 }1936 patch.start2 = parseInt(m[3], 10);1937 if (m[4] === '') {1938 patch.start2--;1939 patch.length2 = 1;1940 } else if (m[4] == '0') {1941 patch.length2 = 0;1942 } else {1943 patch.start2--;1944 patch.length2 = parseInt(m[4], 10);1945 }1946 textPointer++;1947 while (textPointer < text.length) {1948 var sign = text[textPointer].charAt(0);1949 try {1950 var line = decodeURI(text[textPointer].substring(1));1951 } catch (ex) {1952 // Malformed URI sequence.1953 throw new Error('Illegal escape in patch_fromText: ' + line);1954 }1955 if (sign == '-') {1956 // Deletion.1957 patch.diffs.push([DIFF_DELETE, line]);1958 } else if (sign == '+') {1959 // Insertion.1960 patch.diffs.push([DIFF_INSERT, line]);1961 } else if (sign == ' ') {1962 // Minor equality.1963 patch.diffs.push([DIFF_EQUAL, line]);1964 } else if (sign == '@') {1965 // Start of next patch.1966 break;1967 } else if (sign === '') {1968 // Blank line? Whatever.1969 } else {1970 // WTF?1971 throw new Error('Invalid patch mode "' + sign + '" in: ' + line);1972 }1973 textPointer++;1974 }1975 }1976 return patches;1977};1978/**1979 * Class representing one patch operation.1980 * @constructor1981 */1982diff_match_patch.patch_obj = function() {1983 /** @type {!Array.<!diff_match_patch.Diff>} */1984 this.diffs = [];1985 /** @type {?number} */1986 this.start1 = null;1987 /** @type {?number} */1988 this.start2 = null;1989 /** @type {number} */1990 this.length1 = 0;1991 /** @type {number} */1992 this.length2 = 0;1993};1994/**1995 * Emmulate GNU diff's format.1996 * Header: @@ -382,8 +481,9 @@1997 * Indicies are printed as 1-based, not 0-based.1998 * @return {string} The GNU diff string.1999 */2000diff_match_patch.patch_obj.prototype.toString = function() {2001 var coords1, coords2;2002 if (this.length1 === 0) {2003 coords1 = this.start1 + ',0';2004 } else if (this.length1 == 1) {2005 coords1 = this.start1 + 1;2006 } else {2007 coords1 = (this.start1 + 1) + ',' + this.length1;2008 }2009 if (this.length2 === 0) {2010 coords2 = this.start2 + ',0';2011 } else if (this.length2 == 1) {2012 coords2 = this.start2 + 1;2013 } else {2014 coords2 = (this.start2 + 1) + ',' + this.length2;2015 }2016 var text = ['@@ -' + coords1 + ' +' + coords2 + ' @@\n'];2017 var op;2018 // Escape the body of the patch with %xx notation.2019 for (var x = 0; x < this.diffs.length; x++) {2020 switch (this.diffs[x][0]) {2021 case DIFF_INSERT:2022 op = '+';2023 break;2024 case DIFF_DELETE:2025 op = '-';2026 break;2027 case DIFF_EQUAL:2028 op = ' ';2029 break;2030 }2031 text[x + 1] = op + encodeURI(this.diffs[x][1]) + '\n';2032 }2033 return text.join('').replace(/%20/g, ' ');2034};2035// Export these global variables so that they survive Google's JS compiler.2036// In a browser, 'this' will be 'window'.2037// Users of node.js should 'require' the uncompressed version since Google's2038// JS compiler may break the following exports for non-browser environments.2039this['diff_match_patch'] = diff_match_patch;2040this['DIFF_DELETE'] = DIFF_DELETE;2041this['DIFF_INSERT'] = DIFF_INSERT;...

Full Screen

Full Screen

diff_match_patch_uncompressed.js.js

Source:diff_match_patch_uncompressed.js.js Github

copy

Full Screen

1/**2 * Diff Match and Patch3 *4 * Copyright 2006 Google Inc.5 * http://code.google.com/p/google-diff-match-patch/6 *7 * Licensed under the Apache License, Version 2.0 (the "License");8 * you may not use this file except in compliance with the License.9 * You may obtain a copy of the License at10 *11 * http://www.apache.org/licenses/LICENSE-2.012 *13 * Unless required by applicable law or agreed to in writing, software14 * distributed under the License is distributed on an "AS IS" BASIS,15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.16 * See the License for the specific language governing permissions and17 * limitations under the License.18 */19/**20 * @fileoverview Computes the difference between two texts to create a patch.21 * Applies the patch onto another text, allowing for errors.22 * @author fraser@google.com (Neil Fraser)23 */24/**25 * Class containing the diff, match and patch methods.26 * @constructor27 */28function diff_match_patch() {29 // Defaults.30 // Redefine these in your program to override the defaults.31 // Number of seconds to map a diff before giving up (0 for infinity).32 this.Diff_Timeout = 1.0;33 // Cost of an empty edit operation in terms of edit characters.34 this.Diff_EditCost = 4;35 // At what point is no match declared (0.0 = perfection, 1.0 = very loose).36 this.Match_Threshold = 0.5;37 // How far to search for a match (0 = exact location, 1000+ = broad match).38 // A match this many characters away from the expected location will add39 // 1.0 to the score (0.0 is a perfect match).40 this.Match_Distance = 1000;41 // When deleting a large block of text (over ~64 characters), how close do42 // the contents have to be to match the expected contents. (0.0 = perfection,43 // 1.0 = very loose). Note that Match_Threshold controls how closely the44 // end points of a delete need to match.45 this.Patch_DeleteThreshold = 0.5;46 // Chunk size for context length.47 this.Patch_Margin = 4;48 // The number of bits in an int.49 this.Match_MaxBits = 32;50}51// DIFF FUNCTIONS52/**53 * The data structure representing a diff is an array of tuples:54 * [[DIFF_DELETE, 'Hello'], [DIFF_INSERT, 'Goodbye'], [DIFF_EQUAL, ' world.']]55 * which means: delete 'Hello', add 'Goodbye' and keep ' world.'56 */57var DIFF_DELETE = -1;58var DIFF_INSERT = 1;59var DIFF_EQUAL = 0;60/** @typedef {{0: number, 1: string}} */61diff_match_patch.Diff;62/**63 * Find the differences between two texts. Simplifies the problem by stripping64 * any common prefix or suffix off the texts before diffing.65 * @param {string} text1 Old string to be diffed.66 * @param {string} text2 New string to be diffed.67 * @param {boolean=} opt_checklines Optional speedup flag. If present and false,68 * then don't run a line-level diff first to identify the changed areas.69 * Defaults to true, which does a faster, slightly less optimal diff.70 * @param {number} opt_deadline Optional time when the diff should be complete71 * by. Used internally for recursive calls. Users should set DiffTimeout72 * instead.73 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.74 */75diff_match_patch.prototype.diff_main = function(text1, text2, opt_checklines,76 opt_deadline) {77 // Set a deadline by which time the diff must be complete.78 if (typeof opt_deadline == 'undefined') {79 if (this.Diff_Timeout <= 0) {80 opt_deadline = Number.MAX_VALUE;81 } else {82 opt_deadline = (new Date).getTime() + this.Diff_Timeout * 1000;83 }84 }85 var deadline = opt_deadline;86 // Check for null inputs.87 if (text1 == null || text2 == null) {88 throw new Error('Null input. (diff_main)');89 }90 // Check for equality (speedup).91 if (text1 == text2) {92 if (text1) {93 return [[DIFF_EQUAL, text1]];94 }95 return [];96 }97 if (typeof opt_checklines == 'undefined') {98 opt_checklines = true;99 }100 var checklines = opt_checklines;101 // Trim off common prefix (speedup).102 var commonlength = this.diff_commonPrefix(text1, text2);103 var commonprefix = text1.substring(0, commonlength);104 text1 = text1.substring(commonlength);105 text2 = text2.substring(commonlength);106 // Trim off common suffix (speedup).107 commonlength = this.diff_commonSuffix(text1, text2);108 var commonsuffix = text1.substring(text1.length - commonlength);109 text1 = text1.substring(0, text1.length - commonlength);110 text2 = text2.substring(0, text2.length - commonlength);111 // Compute the diff on the middle block.112 var diffs = this.diff_compute_(text1, text2, checklines, deadline);113 // Restore the prefix and suffix.114 if (commonprefix) {115 diffs.unshift([DIFF_EQUAL, commonprefix]);116 }117 if (commonsuffix) {118 diffs.push([DIFF_EQUAL, commonsuffix]);119 }120 this.diff_cleanupMerge(diffs);121 return diffs;122};123/**124 * Find the differences between two texts. Assumes that the texts do not125 * have any common prefix or suffix.126 * @param {string} text1 Old string to be diffed.127 * @param {string} text2 New string to be diffed.128 * @param {boolean} checklines Speedup flag. If false, then don't run a129 * line-level diff first to identify the changed areas.130 * If true, then run a faster, slightly less optimal diff.131 * @param {number} deadline Time when the diff should be complete by.132 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.133 * @private134 */135diff_match_patch.prototype.diff_compute_ = function(text1, text2, checklines,136 deadline) {137 var diffs;138 if (!text1) {139 // Just add some text (speedup).140 return [[DIFF_INSERT, text2]];141 }142 if (!text2) {143 // Just delete some text (speedup).144 return [[DIFF_DELETE, text1]];145 }146 var longtext = text1.length > text2.length ? text1 : text2;147 var shorttext = text1.length > text2.length ? text2 : text1;148 var i = longtext.indexOf(shorttext);149 if (i != -1) {150 // Shorter text is inside the longer text (speedup).151 diffs = [[DIFF_INSERT, longtext.substring(0, i)],152 [DIFF_EQUAL, shorttext],153 [DIFF_INSERT, longtext.substring(i + shorttext.length)]];154 // Swap insertions for deletions if diff is reversed.155 if (text1.length > text2.length) {156 diffs[0][0] = diffs[2][0] = DIFF_DELETE;157 }158 return diffs;159 }160 if (shorttext.length == 1) {161 // Single character string.162 // After the previous speedup, the character can't be an equality.163 return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];164 }165 // Check to see if the problem can be split in two.166 var hm = this.diff_halfMatch_(text1, text2);167 if (hm) {168 // A half-match was found, sort out the return data.169 var text1_a = hm[0];170 var text1_b = hm[1];171 var text2_a = hm[2];172 var text2_b = hm[3];173 var mid_common = hm[4];174 // Send both pairs off for separate processing.175 var diffs_a = this.diff_main(text1_a, text2_a, checklines, deadline);176 var diffs_b = this.diff_main(text1_b, text2_b, checklines, deadline);177 // Merge the results.178 return diffs_a.concat([[DIFF_EQUAL, mid_common]], diffs_b);179 }180 if (checklines && text1.length > 100 && text2.length > 100) {181 return this.diff_lineMode_(text1, text2, deadline);182 }183 return this.diff_bisect_(text1, text2, deadline);184};185/**186 * Do a quick line-level diff on both strings, then rediff the parts for187 * greater accuracy.188 * This speedup can produce non-minimal diffs.189 * @param {string} text1 Old string to be diffed.190 * @param {string} text2 New string to be diffed.191 * @param {number} deadline Time when the diff should be complete by.192 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.193 * @private194 */195diff_match_patch.prototype.diff_lineMode_ = function(text1, text2, deadline) {196 // Scan the text on a line-by-line basis first.197 var a = this.diff_linesToChars_(text1, text2);198 text1 = a.chars1;199 text2 = a.chars2;200 var linearray = a.lineArray;201 var diffs = this.diff_main(text1, text2, false, deadline);202 // Convert the diff back to original text.203 this.diff_charsToLines_(diffs, linearray);204 // Eliminate freak matches (e.g. blank lines)205 this.diff_cleanupSemantic(diffs);206 // Rediff any replacement blocks, this time character-by-character.207 // Add a dummy entry at the end.208 diffs.push([DIFF_EQUAL, '']);209 var pointer = 0;210 var count_delete = 0;211 var count_insert = 0;212 var text_delete = '';213 var text_insert = '';214 while (pointer < diffs.length) {215 switch (diffs[pointer][0]) {216 case DIFF_INSERT:217 count_insert++;218 text_insert += diffs[pointer][1];219 break;220 case DIFF_DELETE:221 count_delete++;222 text_delete += diffs[pointer][1];223 break;224 case DIFF_EQUAL:225 // Upon reaching an equality, check for prior redundancies.226 if (count_delete >= 1 && count_insert >= 1) {227 // Delete the offending records and add the merged ones.228 diffs.splice(pointer - count_delete - count_insert,229 count_delete + count_insert);230 pointer = pointer - count_delete - count_insert;231 var a = this.diff_main(text_delete, text_insert, false, deadline);232 for (var j = a.length - 1; j >= 0; j--) {233 diffs.splice(pointer, 0, a[j]);234 }235 pointer = pointer + a.length;236 }237 count_insert = 0;238 count_delete = 0;239 text_delete = '';240 text_insert = '';241 break;242 }243 pointer++;244 }245 diffs.pop(); // Remove the dummy entry at the end.246 return diffs;247};248/**249 * Find the 'middle snake' of a diff, split the problem in two250 * and return the recursively constructed diff.251 * See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.252 * @param {string} text1 Old string to be diffed.253 * @param {string} text2 New string to be diffed.254 * @param {number} deadline Time at which to bail if not yet complete.255 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.256 * @private257 */258diff_match_patch.prototype.diff_bisect_ = function(text1, text2, deadline) {259 // Cache the text lengths to prevent multiple calls.260 var text1_length = text1.length;261 var text2_length = text2.length;262 var max_d = Math.ceil((text1_length + text2_length) / 2);263 var v_offset = max_d;264 var v_length = 2 * max_d;265 var v1 = new Array(v_length);266 var v2 = new Array(v_length);267 // Setting all elements to -1 is faster in Chrome & Firefox than mixing268 // integers and undefined.269 for (var x = 0; x < v_length; x++) {270 v1[x] = -1;271 v2[x] = -1;272 }273 v1[v_offset + 1] = 0;274 v2[v_offset + 1] = 0;275 var delta = text1_length - text2_length;276 // If the total number of characters is odd, then the front path will collide277 // with the reverse path.278 var front = (delta % 2 != 0);279 // Offsets for start and end of k loop.280 // Prevents mapping of space beyond the grid.281 var k1start = 0;282 var k1end = 0;283 var k2start = 0;284 var k2end = 0;285 for (var d = 0; d < max_d; d++) {286 // Bail out if deadline is reached.287 if ((new Date()).getTime() > deadline) {288 break;289 }290 // Walk the front path one step.291 for (var k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {292 var k1_offset = v_offset + k1;293 var x1;294 if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {295 x1 = v1[k1_offset + 1];296 } else {297 x1 = v1[k1_offset - 1] + 1;298 }299 var y1 = x1 - k1;300 while (x1 < text1_length && y1 < text2_length &&301 text1.charAt(x1) == text2.charAt(y1)) {302 x1++;303 y1++;304 }305 v1[k1_offset] = x1;306 if (x1 > text1_length) {307 // Ran off the right of the graph.308 k1end += 2;309 } else if (y1 > text2_length) {310 // Ran off the bottom of the graph.311 k1start += 2;312 } else if (front) {313 var k2_offset = v_offset + delta - k1;314 if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {315 // Mirror x2 onto top-left coordinate system.316 var x2 = text1_length - v2[k2_offset];317 if (x1 >= x2) {318 // Overlap detected.319 return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);320 }321 }322 }323 }324 // Walk the reverse path one step.325 for (var k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {326 var k2_offset = v_offset + k2;327 var x2;328 if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {329 x2 = v2[k2_offset + 1];330 } else {331 x2 = v2[k2_offset - 1] + 1;332 }333 var y2 = x2 - k2;334 while (x2 < text1_length && y2 < text2_length &&335 text1.charAt(text1_length - x2 - 1) ==336 text2.charAt(text2_length - y2 - 1)) {337 x2++;338 y2++;339 }340 v2[k2_offset] = x2;341 if (x2 > text1_length) {342 // Ran off the left of the graph.343 k2end += 2;344 } else if (y2 > text2_length) {345 // Ran off the top of the graph.346 k2start += 2;347 } else if (!front) {348 var k1_offset = v_offset + delta - k2;349 if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {350 var x1 = v1[k1_offset];351 var y1 = v_offset + x1 - k1_offset;352 // Mirror x2 onto top-left coordinate system.353 x2 = text1_length - x2;354 if (x1 >= x2) {355 // Overlap detected.356 return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);357 }358 }359 }360 }361 }362 // Diff took too long and hit the deadline or363 // number of diffs equals number of characters, no commonality at all.364 return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];365};366/**367 * Given the location of the 'middle snake', split the diff in two parts368 * and recurse.369 * @param {string} text1 Old string to be diffed.370 * @param {string} text2 New string to be diffed.371 * @param {number} x Index of split point in text1.372 * @param {number} y Index of split point in text2.373 * @param {number} deadline Time at which to bail if not yet complete.374 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.375 * @private376 */377diff_match_patch.prototype.diff_bisectSplit_ = function(text1, text2, x, y,378 deadline) {379 var text1a = text1.substring(0, x);380 var text2a = text2.substring(0, y);381 var text1b = text1.substring(x);382 var text2b = text2.substring(y);383 // Compute both diffs serially.384 var diffs = this.diff_main(text1a, text2a, false, deadline);385 var diffsb = this.diff_main(text1b, text2b, false, deadline);386 return diffs.concat(diffsb);387};388/**389 * Split two texts into an array of strings. Reduce the texts to a string of390 * hashes where each Unicode character represents one line.391 * @param {string} text1 First string.392 * @param {string} text2 Second string.393 * @return {{chars1: string, chars2: string, lineArray: !Array.<string>}}394 * An object containing the encoded text1, the encoded text2 and395 * the array of unique strings.396 * The zeroth element of the array of unique strings is intentionally blank.397 * @private398 */399diff_match_patch.prototype.diff_linesToChars_ = function(text1, text2) {400 var lineArray = []; // e.g. lineArray[4] == 'Hello\n'401 var lineHash = {}; // e.g. lineHash['Hello\n'] == 4402 // '\x00' is a valid character, but various debuggers don't like it.403 // So we'll insert a junk entry to avoid generating a null character.404 lineArray[0] = '';405 /**406 * Split a text into an array of strings. Reduce the texts to a string of407 * hashes where each Unicode character represents one line.408 * Modifies linearray and linehash through being a closure.409 * @param {string} text String to encode.410 * @return {string} Encoded string.411 * @private412 */413 function diff_linesToCharsMunge_(text) {414 var chars = '';415 // Walk the text, pulling out a substring for each line.416 // text.split('\n') would would temporarily double our memory footprint.417 // Modifying text would create many large strings to garbage collect.418 var lineStart = 0;419 var lineEnd = -1;420 // Keeping our own length variable is faster than looking it up.421 var lineArrayLength = lineArray.length;422 while (lineEnd < text.length - 1) {423 lineEnd = text.indexOf('\n', lineStart);424 if (lineEnd == -1) {425 lineEnd = text.length - 1;426 }427 var line = text.substring(lineStart, lineEnd + 1);428 lineStart = lineEnd + 1;429 if (lineHash.hasOwnProperty ? lineHash.hasOwnProperty(line) :430 (lineHash[line] !== undefined)) {431 chars += String.fromCharCode(lineHash[line]);432 } else {433 chars += String.fromCharCode(lineArrayLength);434 lineHash[line] = lineArrayLength;435 lineArray[lineArrayLength++] = line;436 }437 }438 return chars;439 }440 var chars1 = diff_linesToCharsMunge_(text1);441 var chars2 = diff_linesToCharsMunge_(text2);442 return {chars1: chars1, chars2: chars2, lineArray: lineArray};443};444/**445 * Rehydrate the text in a diff from a string of line hashes to real lines of446 * text.447 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.448 * @param {!Array.<string>} lineArray Array of unique strings.449 * @private450 */451diff_match_patch.prototype.diff_charsToLines_ = function(diffs, lineArray) {452 for (var x = 0; x < diffs.length; x++) {453 var chars = diffs[x][1];454 var text = [];455 for (var y = 0; y < chars.length; y++) {456 text[y] = lineArray[chars.charCodeAt(y)];457 }458 diffs[x][1] = text.join('');459 }460};461/**462 * Determine the common prefix of two strings.463 * @param {string} text1 First string.464 * @param {string} text2 Second string.465 * @return {number} The number of characters common to the start of each466 * string.467 */468diff_match_patch.prototype.diff_commonPrefix = function(text1, text2) {469 // Quick check for common null cases.470 if (!text1 || !text2 || text1.charAt(0) != text2.charAt(0)) {471 return 0;472 }473 // Binary search.474 // Performance analysis: http://neil.fraser.name/news/2007/10/09/475 var pointermin = 0;476 var pointermax = Math.min(text1.length, text2.length);477 var pointermid = pointermax;478 var pointerstart = 0;479 while (pointermin < pointermid) {480 if (text1.substring(pointerstart, pointermid) ==481 text2.substring(pointerstart, pointermid)) {482 pointermin = pointermid;483 pointerstart = pointermin;484 } else {485 pointermax = pointermid;486 }487 pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);488 }489 return pointermid;490};491/**492 * Determine the common suffix of two strings.493 * @param {string} text1 First string.494 * @param {string} text2 Second string.495 * @return {number} The number of characters common to the end of each string.496 */497diff_match_patch.prototype.diff_commonSuffix = function(text1, text2) {498 // Quick check for common null cases.499 if (!text1 || !text2 ||500 text1.charAt(text1.length - 1) != text2.charAt(text2.length - 1)) {501 return 0;502 }503 // Binary search.504 // Performance analysis: http://neil.fraser.name/news/2007/10/09/505 var pointermin = 0;506 var pointermax = Math.min(text1.length, text2.length);507 var pointermid = pointermax;508 var pointerend = 0;509 while (pointermin < pointermid) {510 if (text1.substring(text1.length - pointermid, text1.length - pointerend) ==511 text2.substring(text2.length - pointermid, text2.length - pointerend)) {512 pointermin = pointermid;513 pointerend = pointermin;514 } else {515 pointermax = pointermid;516 }517 pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);518 }519 return pointermid;520};521/**522 * Determine if the suffix of one string is the prefix of another.523 * @param {string} text1 First string.524 * @param {string} text2 Second string.525 * @return {number} The number of characters common to the end of the first526 * string and the start of the second string.527 * @private528 */529diff_match_patch.prototype.diff_commonOverlap_ = function(text1, text2) {530 // Cache the text lengths to prevent multiple calls.531 var text1_length = text1.length;532 var text2_length = text2.length;533 // Eliminate the null case.534 if (text1_length == 0 || text2_length == 0) {535 return 0;536 }537 // Truncate the longer string.538 if (text1_length > text2_length) {539 text1 = text1.substring(text1_length - text2_length);540 } else if (text1_length < text2_length) {541 text2 = text2.substring(0, text1_length);542 }543 var text_length = Math.min(text1_length, text2_length);544 // Quick check for the worst case.545 if (text1 == text2) {546 return text_length;547 }548 // Start by looking for a single character match549 // and increase length until no match is found.550 // Performance analysis: http://neil.fraser.name/news/2010/11/04/551 var best = 0;552 var length = 1;553 while (true) {554 var pattern = text1.substring(text_length - length);555 var found = text2.indexOf(pattern);556 if (found == -1) {557 return best;558 }559 length += found;560 if (found == 0 || text1.substring(text_length - length) ==561 text2.substring(0, length)) {562 best = length;563 length++;564 }565 }566};567/**568 * Do the two texts share a substring which is at least half the length of the569 * longer text?570 * This speedup can produce non-minimal diffs.571 * @param {string} text1 First string.572 * @param {string} text2 Second string.573 * @return {Array.<string>} Five element Array, containing the prefix of574 * text1, the suffix of text1, the prefix of text2, the suffix of575 * text2 and the common middle. Or null if there was no match.576 * @private577 */578diff_match_patch.prototype.diff_halfMatch_ = function(text1, text2) {579 if (this.Diff_Timeout <= 0) {580 // Don't risk returning a non-optimal diff if we have unlimited time.581 return null;582 }583 var longtext = text1.length > text2.length ? text1 : text2;584 var shorttext = text1.length > text2.length ? text2 : text1;585 if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {586 return null; // Pointless.587 }588 var dmp = this; // 'this' becomes 'window' in a closure.589 /**590 * Does a substring of shorttext exist within longtext such that the substring591 * is at least half the length of longtext?592 * Closure, but does not reference any external variables.593 * @param {string} longtext Longer string.594 * @param {string} shorttext Shorter string.595 * @param {number} i Start index of quarter length substring within longtext.596 * @return {Array.<string>} Five element Array, containing the prefix of597 * longtext, the suffix of longtext, the prefix of shorttext, the suffix598 * of shorttext and the common middle. Or null if there was no match.599 * @private600 */601 function diff_halfMatchI_(longtext, shorttext, i) {602 // Start with a 1/4 length substring at position i as a seed.603 var seed = longtext.substring(i, i + Math.floor(longtext.length / 4));604 var j = -1;605 var best_common = '';606 var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;607 while ((j = shorttext.indexOf(seed, j + 1)) != -1) {608 var prefixLength = dmp.diff_commonPrefix(longtext.substring(i),609 shorttext.substring(j));610 var suffixLength = dmp.diff_commonSuffix(longtext.substring(0, i),611 shorttext.substring(0, j));612 if (best_common.length < suffixLength + prefixLength) {613 best_common = shorttext.substring(j - suffixLength, j) +614 shorttext.substring(j, j + prefixLength);615 best_longtext_a = longtext.substring(0, i - suffixLength);616 best_longtext_b = longtext.substring(i + prefixLength);617 best_shorttext_a = shorttext.substring(0, j - suffixLength);618 best_shorttext_b = shorttext.substring(j + prefixLength);619 }620 }621 if (best_common.length * 2 >= longtext.length) {622 return [best_longtext_a, best_longtext_b,623 best_shorttext_a, best_shorttext_b, best_common];624 } else {625 return null;626 }627 }628 // First check if the second quarter is the seed for a half-match.629 var hm1 = diff_halfMatchI_(longtext, shorttext,630 Math.ceil(longtext.length / 4));631 // Check again based on the third quarter.632 var hm2 = diff_halfMatchI_(longtext, shorttext,633 Math.ceil(longtext.length / 2));634 var hm;635 if (!hm1 && !hm2) {636 return null;637 } else if (!hm2) {638 hm = hm1;639 } else if (!hm1) {640 hm = hm2;641 } else {642 // Both matched. Select the longest.643 hm = hm1[4].length > hm2[4].length ? hm1 : hm2;644 }645 // A half-match was found, sort out the return data.646 var text1_a, text1_b, text2_a, text2_b;647 if (text1.length > text2.length) {648 text1_a = hm[0];649 text1_b = hm[1];650 text2_a = hm[2];651 text2_b = hm[3];652 } else {653 text2_a = hm[0];654 text2_b = hm[1];655 text1_a = hm[2];656 text1_b = hm[3];657 }658 var mid_common = hm[4];659 return [text1_a, text1_b, text2_a, text2_b, mid_common];660};661/**662 * Reduce the number of edits by eliminating semantically trivial equalities.663 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.664 */665diff_match_patch.prototype.diff_cleanupSemantic = function(diffs) {666 var changes = false;667 var equalities = []; // Stack of indices where equalities are found.668 var equalitiesLength = 0; // Keeping our own length var is faster in JS.669 /** @type {?string} */670 var lastequality = null;671 // Always equal to diffs[equalities[equalitiesLength - 1]][1]672 var pointer = 0; // Index of current position.673 // Number of characters that changed prior to the equality.674 var length_insertions1 = 0;675 var length_deletions1 = 0;676 // Number of characters that changed after the equality.677 var length_insertions2 = 0;678 var length_deletions2 = 0;679 while (pointer < diffs.length) {680 if (diffs[pointer][0] == DIFF_EQUAL) { // Equality found.681 equalities[equalitiesLength++] = pointer;682 length_insertions1 = length_insertions2;683 length_deletions1 = length_deletions2;684 length_insertions2 = 0;685 length_deletions2 = 0;686 lastequality = diffs[pointer][1];687 } else { // An insertion or deletion.688 if (diffs[pointer][0] == DIFF_INSERT) {689 length_insertions2 += diffs[pointer][1].length;690 } else {691 length_deletions2 += diffs[pointer][1].length;692 }693 // Eliminate an equality that is smaller or equal to the edits on both694 // sides of it.695 if (lastequality && (lastequality.length <=696 Math.max(length_insertions1, length_deletions1)) &&697 (lastequality.length <= Math.max(length_insertions2,698 length_deletions2))) {699 // Duplicate record.700 diffs.splice(equalities[equalitiesLength - 1], 0,701 [DIFF_DELETE, lastequality]);702 // Change second copy to insert.703 diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;704 // Throw away the equality we just deleted.705 equalitiesLength--;706 // Throw away the previous equality (it needs to be reevaluated).707 equalitiesLength--;708 pointer = equalitiesLength > 0 ? equalities[equalitiesLength - 1] : -1;709 length_insertions1 = 0; // Reset the counters.710 length_deletions1 = 0;711 length_insertions2 = 0;712 length_deletions2 = 0;713 lastequality = null;714 changes = true;715 }716 }717 pointer++;718 }719 // Normalize the diff.720 if (changes) {721 this.diff_cleanupMerge(diffs);722 }723 this.diff_cleanupSemanticLossless(diffs);724 // Find any overlaps between deletions and insertions.725 // e.g: <del>abcxxx</del><ins>xxxdef</ins>726 // -> <del>abc</del>xxx<ins>def</ins>727 // e.g: <del>xxxabc</del><ins>defxxx</ins>728 // -> <ins>def</ins>xxx<del>abc</del>729 // Only extract an overlap if it is as big as the edit ahead or behind it.730 pointer = 1;731 while (pointer < diffs.length) {732 if (diffs[pointer - 1][0] == DIFF_DELETE &&733 diffs[pointer][0] == DIFF_INSERT) {734 var deletion = diffs[pointer - 1][1];735 var insertion = diffs[pointer][1];736 var overlap_length1 = this.diff_commonOverlap_(deletion, insertion);737 var overlap_length2 = this.diff_commonOverlap_(insertion, deletion);738 if (overlap_length1 >= overlap_length2) {739 if (overlap_length1 >= deletion.length / 2 ||740 overlap_length1 >= insertion.length / 2) {741 // Overlap found. Insert an equality and trim the surrounding edits.742 diffs.splice(pointer, 0,743 [DIFF_EQUAL, insertion.substring(0, overlap_length1)]);744 diffs[pointer - 1][1] =745 deletion.substring(0, deletion.length - overlap_length1);746 diffs[pointer + 1][1] = insertion.substring(overlap_length1);747 pointer++;748 }749 } else {750 if (overlap_length2 >= deletion.length / 2 ||751 overlap_length2 >= insertion.length / 2) {752 // Reverse overlap found.753 // Insert an equality and swap and trim the surrounding edits.754 diffs.splice(pointer, 0,755 [DIFF_EQUAL, deletion.substring(0, overlap_length2)]);756 diffs[pointer - 1][0] = DIFF_INSERT;757 diffs[pointer - 1][1] =758 insertion.substring(0, insertion.length - overlap_length2);759 diffs[pointer + 1][0] = DIFF_DELETE;760 diffs[pointer + 1][1] =761 deletion.substring(overlap_length2);762 pointer++;763 }764 }765 pointer++;766 }767 pointer++;768 }769};770/**771 * Look for single edits surrounded on both sides by equalities772 * which can be shifted sideways to align the edit to a word boundary.773 * e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.774 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.775 */776diff_match_patch.prototype.diff_cleanupSemanticLossless = function(diffs) {777 /**778 * Given two strings, compute a score representing whether the internal779 * boundary falls on logical boundaries.780 * Scores range from 6 (best) to 0 (worst).781 * Closure, but does not reference any external variables.782 * @param {string} one First string.783 * @param {string} two Second string.784 * @return {number} The score.785 * @private786 */787 function diff_cleanupSemanticScore_(one, two) {788 if (!one || !two) {789 // Edges are the best.790 return 6;791 }792 // Each port of this function behaves slightly differently due to793 // subtle differences in each language's definition of things like794 // 'whitespace'. Since this function's purpose is largely cosmetic,795 // the choice has been made to use each language's native features796 // rather than force total conformity.797 var char1 = one.charAt(one.length - 1);798 var char2 = two.charAt(0);799 var nonAlphaNumeric1 = char1.match(diff_match_patch.nonAlphaNumericRegex_);800 var nonAlphaNumeric2 = char2.match(diff_match_patch.nonAlphaNumericRegex_);801 var whitespace1 = nonAlphaNumeric1 &&802 char1.match(diff_match_patch.whitespaceRegex_);803 var whitespace2 = nonAlphaNumeric2 &&804 char2.match(diff_match_patch.whitespaceRegex_);805 var lineBreak1 = whitespace1 &&806 char1.match(diff_match_patch.linebreakRegex_);807 var lineBreak2 = whitespace2 &&808 char2.match(diff_match_patch.linebreakRegex_);809 var blankLine1 = lineBreak1 &&810 one.match(diff_match_patch.blanklineEndRegex_);811 var blankLine2 = lineBreak2 &&812 two.match(diff_match_patch.blanklineStartRegex_);813 if (blankLine1 || blankLine2) {814 // Five points for blank lines.815 return 5;816 } else if (lineBreak1 || lineBreak2) {817 // Four points for line breaks.818 return 4;819 } else if (nonAlphaNumeric1 && !whitespace1 && whitespace2) {820 // Three points for end of sentences.821 return 3;822 } else if (whitespace1 || whitespace2) {823 // Two points for whitespace.824 return 2;825 } else if (nonAlphaNumeric1 || nonAlphaNumeric2) {826 // One point for non-alphanumeric.827 return 1;828 }829 return 0;830 }831 var pointer = 1;832 // Intentionally ignore the first and last element (don't need checking).833 while (pointer < diffs.length - 1) {834 if (diffs[pointer - 1][0] == DIFF_EQUAL &&835 diffs[pointer + 1][0] == DIFF_EQUAL) {836 // This is a single edit surrounded by equalities.837 var equality1 = diffs[pointer - 1][1];838 var edit = diffs[pointer][1];839 var equality2 = diffs[pointer + 1][1];840 // First, shift the edit as far left as possible.841 var commonOffset = this.diff_commonSuffix(equality1, edit);842 if (commonOffset) {843 var commonString = edit.substring(edit.length - commonOffset);844 equality1 = equality1.substring(0, equality1.length - commonOffset);845 edit = commonString + edit.substring(0, edit.length - commonOffset);846 equality2 = commonString + equality2;847 }848 // Second, step character by character right, looking for the best fit.849 var bestEquality1 = equality1;850 var bestEdit = edit;851 var bestEquality2 = equality2;852 var bestScore = diff_cleanupSemanticScore_(equality1, edit) +853 diff_cleanupSemanticScore_(edit, equality2);854 while (edit.charAt(0) === equality2.charAt(0)) {855 equality1 += edit.charAt(0);856 edit = edit.substring(1) + equality2.charAt(0);857 equality2 = equality2.substring(1);858 var score = diff_cleanupSemanticScore_(equality1, edit) +859 diff_cleanupSemanticScore_(edit, equality2);860 // The >= encourages trailing rather than leading whitespace on edits.861 if (score >= bestScore) {862 bestScore = score;863 bestEquality1 = equality1;864 bestEdit = edit;865 bestEquality2 = equality2;866 }867 }868 if (diffs[pointer - 1][1] != bestEquality1) {869 // We have an improvement, save it back to the diff.870 if (bestEquality1) {871 diffs[pointer - 1][1] = bestEquality1;872 } else {873 diffs.splice(pointer - 1, 1);874 pointer--;875 }876 diffs[pointer][1] = bestEdit;877 if (bestEquality2) {878 diffs[pointer + 1][1] = bestEquality2;879 } else {880 diffs.splice(pointer + 1, 1);881 pointer--;882 }883 }884 }885 pointer++;886 }887};888// Define some regex patterns for matching boundaries.889diff_match_patch.nonAlphaNumericRegex_ = /[^a-zA-Z0-9]/;890diff_match_patch.whitespaceRegex_ = /\s/;891diff_match_patch.linebreakRegex_ = /[\r\n]/;892diff_match_patch.blanklineEndRegex_ = /\n\r?\n$/;893diff_match_patch.blanklineStartRegex_ = /^\r?\n\r?\n/;894/**895 * Reduce the number of edits by eliminating operationally trivial equalities.896 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.897 */898diff_match_patch.prototype.diff_cleanupEfficiency = function(diffs) {899 var changes = false;900 var equalities = []; // Stack of indices where equalities are found.901 var equalitiesLength = 0; // Keeping our own length var is faster in JS.902 /** @type {?string} */903 var lastequality = null;904 // Always equal to diffs[equalities[equalitiesLength - 1]][1]905 var pointer = 0; // Index of current position.906 // Is there an insertion operation before the last equality.907 var pre_ins = false;908 // Is there a deletion operation before the last equality.909 var pre_del = false;910 // Is there an insertion operation after the last equality.911 var post_ins = false;912 // Is there a deletion operation after the last equality.913 var post_del = false;914 while (pointer < diffs.length) {915 if (diffs[pointer][0] == DIFF_EQUAL) { // Equality found.916 if (diffs[pointer][1].length < this.Diff_EditCost &&917 (post_ins || post_del)) {918 // Candidate found.919 equalities[equalitiesLength++] = pointer;920 pre_ins = post_ins;921 pre_del = post_del;922 lastequality = diffs[pointer][1];923 } else {924 // Not a candidate, and can never become one.925 equalitiesLength = 0;926 lastequality = null;927 }928 post_ins = post_del = false;929 } else { // An insertion or deletion.930 if (diffs[pointer][0] == DIFF_DELETE) {931 post_del = true;932 } else {933 post_ins = true;934 }935 /*936 * Five types to be split:937 * <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>938 * <ins>A</ins>X<ins>C</ins><del>D</del>939 * <ins>A</ins><del>B</del>X<ins>C</ins>940 * <ins>A</del>X<ins>C</ins><del>D</del>941 * <ins>A</ins><del>B</del>X<del>C</del>942 */943 if (lastequality && ((pre_ins && pre_del && post_ins && post_del) ||944 ((lastequality.length < this.Diff_EditCost / 2) &&945 (pre_ins + pre_del + post_ins + post_del) == 3))) {946 // Duplicate record.947 diffs.splice(equalities[equalitiesLength - 1], 0,948 [DIFF_DELETE, lastequality]);949 // Change second copy to insert.950 diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;951 equalitiesLength--; // Throw away the equality we just deleted;952 lastequality = null;953 if (pre_ins && pre_del) {954 // No changes made which could affect previous entry, keep going.955 post_ins = post_del = true;956 equalitiesLength = 0;957 } else {958 equalitiesLength--; // Throw away the previous equality.959 pointer = equalitiesLength > 0 ?960 equalities[equalitiesLength - 1] : -1;961 post_ins = post_del = false;962 }963 changes = true;964 }965 }966 pointer++;967 }968 if (changes) {969 this.diff_cleanupMerge(diffs);970 }971};972/**973 * Reorder and merge like edit sections. Merge equalities.974 * Any edit section can move as long as it doesn't cross an equality.975 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.976 */977diff_match_patch.prototype.diff_cleanupMerge = function(diffs) {978 diffs.push([DIFF_EQUAL, '']); // Add a dummy entry at the end.979 var pointer = 0;980 var count_delete = 0;981 var count_insert = 0;982 var text_delete = '';983 var text_insert = '';984 var commonlength;985 while (pointer < diffs.length) {986 switch (diffs[pointer][0]) {987 case DIFF_INSERT:988 count_insert++;989 text_insert += diffs[pointer][1];990 pointer++;991 break;992 case DIFF_DELETE:993 count_delete++;994 text_delete += diffs[pointer][1];995 pointer++;996 break;997 case DIFF_EQUAL:998 // Upon reaching an equality, check for prior redundancies.999 if (count_delete + count_insert > 1) {1000 if (count_delete !== 0 && count_insert !== 0) {1001 // Factor out any common prefixies.1002 commonlength = this.diff_commonPrefix(text_insert, text_delete);1003 if (commonlength !== 0) {1004 if ((pointer - count_delete - count_insert) > 0 &&1005 diffs[pointer - count_delete - count_insert - 1][0] ==1006 DIFF_EQUAL) {1007 diffs[pointer - count_delete - count_insert - 1][1] +=1008 text_insert.substring(0, commonlength);1009 } else {1010 diffs.splice(0, 0, [DIFF_EQUAL,1011 text_insert.substring(0, commonlength)]);1012 pointer++;1013 }1014 text_insert = text_insert.substring(commonlength);1015 text_delete = text_delete.substring(commonlength);1016 }1017 // Factor out any common suffixies.1018 commonlength = this.diff_commonSuffix(text_insert, text_delete);1019 if (commonlength !== 0) {1020 diffs[pointer][1] = text_insert.substring(text_insert.length -1021 commonlength) + diffs[pointer][1];1022 text_insert = text_insert.substring(0, text_insert.length -1023 commonlength);1024 text_delete = text_delete.substring(0, text_delete.length -1025 commonlength);1026 }1027 }1028 // Delete the offending records and add the merged ones.1029 if (count_delete === 0) {1030 diffs.splice(pointer - count_insert,1031 count_delete + count_insert, [DIFF_INSERT, text_insert]);1032 } else if (count_insert === 0) {1033 diffs.splice(pointer - count_delete,1034 count_delete + count_insert, [DIFF_DELETE, text_delete]);1035 } else {1036 diffs.splice(pointer - count_delete - count_insert,1037 count_delete + count_insert, [DIFF_DELETE, text_delete],1038 [DIFF_INSERT, text_insert]);1039 }1040 pointer = pointer - count_delete - count_insert +1041 (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;1042 } else if (pointer !== 0 && diffs[pointer - 1][0] == DIFF_EQUAL) {1043 // Merge this equality with the previous one.1044 diffs[pointer - 1][1] += diffs[pointer][1];1045 diffs.splice(pointer, 1);1046 } else {1047 pointer++;1048 }1049 count_insert = 0;1050 count_delete = 0;1051 text_delete = '';1052 text_insert = '';1053 break;1054 }1055 }1056 if (diffs[diffs.length - 1][1] === '') {1057 diffs.pop(); // Remove the dummy entry at the end.1058 }1059 // Second pass: look for single edits surrounded on both sides by equalities1060 // which can be shifted sideways to eliminate an equality.1061 // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC1062 var changes = false;1063 pointer = 1;1064 // Intentionally ignore the first and last element (don't need checking).1065 while (pointer < diffs.length - 1) {1066 if (diffs[pointer - 1][0] == DIFF_EQUAL &&1067 diffs[pointer + 1][0] == DIFF_EQUAL) {1068 // This is a single edit surrounded by equalities.1069 if (diffs[pointer][1].substring(diffs[pointer][1].length -1070 diffs[pointer - 1][1].length) == diffs[pointer - 1][1]) {1071 // Shift the edit over the previous equality.1072 diffs[pointer][1] = diffs[pointer - 1][1] +1073 diffs[pointer][1].substring(0, diffs[pointer][1].length -1074 diffs[pointer - 1][1].length);1075 diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1];1076 diffs.splice(pointer - 1, 1);1077 changes = true;1078 } else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) ==1079 diffs[pointer + 1][1]) {1080 // Shift the edit over the next equality.1081 diffs[pointer - 1][1] += diffs[pointer + 1][1];1082 diffs[pointer][1] =1083 diffs[pointer][1].substring(diffs[pointer + 1][1].length) +1084 diffs[pointer + 1][1];1085 diffs.splice(pointer + 1, 1);1086 changes = true;1087 }1088 }1089 pointer++;1090 }1091 // If shifts were made, the diff needs reordering and another shift sweep.1092 if (changes) {1093 this.diff_cleanupMerge(diffs);1094 }1095};1096/**1097 * loc is a location in text1, compute and return the equivalent location in1098 * text2.1099 * e.g. 'The cat' vs 'The big cat', 1->1, 5->81100 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1101 * @param {number} loc Location within text1.1102 * @return {number} Location within text2.1103 */1104diff_match_patch.prototype.diff_xIndex = function(diffs, loc) {1105 var chars1 = 0;1106 var chars2 = 0;1107 var last_chars1 = 0;1108 var last_chars2 = 0;1109 var x;1110 for (x = 0; x < diffs.length; x++) {1111 if (diffs[x][0] !== DIFF_INSERT) { // Equality or deletion.1112 chars1 += diffs[x][1].length;1113 }1114 if (diffs[x][0] !== DIFF_DELETE) { // Equality or insertion.1115 chars2 += diffs[x][1].length;1116 }1117 if (chars1 > loc) { // Overshot the location.1118 break;1119 }1120 last_chars1 = chars1;1121 last_chars2 = chars2;1122 }1123 // Was the location was deleted?1124 if (diffs.length != x && diffs[x][0] === DIFF_DELETE) {1125 return last_chars2;1126 }1127 // Add the remaining character length.1128 return last_chars2 + (loc - last_chars1);1129};1130/**1131 * Convert a diff array into a pretty HTML report.1132 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1133 * @return {string} HTML representation.1134 */1135diff_match_patch.prototype.diff_prettyHtml = function(diffs) {1136 var html = [];1137 var pattern_amp = /&/g;1138 var pattern_lt = /</g;1139 var pattern_gt = />/g;1140 var pattern_para = /\n/g;1141 for (var x = 0; x < diffs.length; x++) {1142 var op = diffs[x][0]; // Operation (insert, delete, equal)1143 var data = diffs[x][1]; // Text of change.1144 var text = data.replace(pattern_amp, '&amp;').replace(pattern_lt, '&lt;')1145 .replace(pattern_gt, '&gt;').replace(pattern_para, '&para;<br>');1146 switch (op) {1147 case DIFF_INSERT:1148 html[x] = '<ins style="background:#e6ffe6;">' + text + '</ins>';1149 break;1150 case DIFF_DELETE:1151 html[x] = '<del style="background:#ffe6e6;">' + text + '</del>';1152 break;1153 case DIFF_EQUAL:1154 html[x] = '<span>' + text + '</span>';1155 break;1156 }1157 }1158 return html.join('');1159};1160/**1161 * Compute and return the source text (all equalities and deletions).1162 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1163 * @return {string} Source text.1164 */1165diff_match_patch.prototype.diff_text1 = function(diffs) {1166 var text = [];1167 for (var x = 0; x < diffs.length; x++) {1168 if (diffs[x][0] !== DIFF_INSERT) {1169 text[x] = diffs[x][1];1170 }1171 }1172 return text.join('');1173};1174/**1175 * Compute and return the destination text (all equalities and insertions).1176 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1177 * @return {string} Destination text.1178 */1179diff_match_patch.prototype.diff_text2 = function(diffs) {1180 var text = [];1181 for (var x = 0; x < diffs.length; x++) {1182 if (diffs[x][0] !== DIFF_DELETE) {1183 text[x] = diffs[x][1];1184 }1185 }1186 return text.join('');1187};1188/**1189 * Compute the Levenshtein distance; the number of inserted, deleted or1190 * substituted characters.1191 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1192 * @return {number} Number of changes.1193 */1194diff_match_patch.prototype.diff_levenshtein = function(diffs) {1195 var levenshtein = 0;1196 var insertions = 0;1197 var deletions = 0;1198 for (var x = 0; x < diffs.length; x++) {1199 var op = diffs[x][0];1200 var data = diffs[x][1];1201 switch (op) {1202 case DIFF_INSERT:1203 insertions += data.length;1204 break;1205 case DIFF_DELETE:1206 deletions += data.length;1207 break;1208 case DIFF_EQUAL:1209 // A deletion and an insertion is one substitution.1210 levenshtein += Math.max(insertions, deletions);1211 insertions = 0;1212 deletions = 0;1213 break;1214 }1215 }1216 levenshtein += Math.max(insertions, deletions);1217 return levenshtein;1218};1219/**1220 * Crush the diff into an encoded string which describes the operations1221 * required to transform text1 into text2.1222 * E.g. =3\t-2\t+ing -> Keep 3 chars, delete 2 chars, insert 'ing'.1223 * Operations are tab-separated. Inserted text is escaped using %xx notation.1224 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1225 * @return {string} Delta text.1226 */1227diff_match_patch.prototype.diff_toDelta = function(diffs) {1228 var text = [];1229 for (var x = 0; x < diffs.length; x++) {1230 switch (diffs[x][0]) {1231 case DIFF_INSERT:1232 text[x] = '+' + encodeURI(diffs[x][1]);1233 break;1234 case DIFF_DELETE:1235 text[x] = '-' + diffs[x][1].length;1236 break;1237 case DIFF_EQUAL:1238 text[x] = '=' + diffs[x][1].length;1239 break;1240 }1241 }1242 return text.join('\t').replace(/%20/g, ' ');1243};1244/**1245 * Given the original text1, and an encoded string which describes the1246 * operations required to transform text1 into text2, compute the full diff.1247 * @param {string} text1 Source string for the diff.1248 * @param {string} delta Delta text.1249 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.1250 * @throws {!Error} If invalid input.1251 */1252diff_match_patch.prototype.diff_fromDelta = function(text1, delta) {1253 var diffs = [];1254 var diffsLength = 0; // Keeping our own length var is faster in JS.1255 var pointer = 0; // Cursor in text11256 var tokens = delta.split(/\t/g);1257 for (var x = 0; x < tokens.length; x++) {1258 // Each token begins with a one character parameter which specifies the1259 // operation of this token (delete, insert, equality).1260 var param = tokens[x].substring(1);1261 switch (tokens[x].charAt(0)) {1262 case '+':1263 try {1264 diffs[diffsLength++] = [DIFF_INSERT, decodeURI(param)];1265 } catch (ex) {1266 // Malformed URI sequence.1267 throw new Error('Illegal escape in diff_fromDelta: ' + param);1268 }1269 break;1270 case '-':1271 // Fall through.1272 case '=':1273 var n = parseInt(param, 10);1274 if (isNaN(n) || n < 0) {1275 throw new Error('Invalid number in diff_fromDelta: ' + param);1276 }1277 var text = text1.substring(pointer, pointer += n);1278 if (tokens[x].charAt(0) == '=') {1279 diffs[diffsLength++] = [DIFF_EQUAL, text];1280 } else {1281 diffs[diffsLength++] = [DIFF_DELETE, text];1282 }1283 break;1284 default:1285 // Blank tokens are ok (from a trailing \t).1286 // Anything else is an error.1287 if (tokens[x]) {1288 throw new Error('Invalid diff operation in diff_fromDelta: ' +1289 tokens[x]);1290 }1291 }1292 }1293 if (pointer != text1.length) {1294 throw new Error('Delta length (' + pointer +1295 ') does not equal source text length (' + text1.length + ').');1296 }1297 return diffs;1298};1299// MATCH FUNCTIONS1300/**1301 * Locate the best instance of 'pattern' in 'text' near 'loc'.1302 * @param {string} text The text to search.1303 * @param {string} pattern The pattern to search for.1304 * @param {number} loc The location to search around.1305 * @return {number} Best match index or -1.1306 */1307diff_match_patch.prototype.match_main = function(text, pattern, loc) {1308 // Check for null inputs.1309 if (text == null || pattern == null || loc == null) {1310 throw new Error('Null input. (match_main)');1311 }1312 loc = Math.max(0, Math.min(loc, text.length));1313 if (text == pattern) {1314 // Shortcut (potentially not guaranteed by the algorithm)1315 return 0;1316 } else if (!text.length) {1317 // Nothing to match.1318 return -1;1319 } else if (text.substring(loc, loc + pattern.length) == pattern) {1320 // Perfect match at the perfect spot! (Includes case of null pattern)1321 return loc;1322 } else {1323 // Do a fuzzy compare.1324 return this.match_bitap_(text, pattern, loc);1325 }1326};1327/**1328 * Locate the best instance of 'pattern' in 'text' near 'loc' using the1329 * Bitap algorithm.1330 * @param {string} text The text to search.1331 * @param {string} pattern The pattern to search for.1332 * @param {number} loc The location to search around.1333 * @return {number} Best match index or -1.1334 * @private1335 */1336diff_match_patch.prototype.match_bitap_ = function(text, pattern, loc) {1337 if (pattern.length > this.Match_MaxBits) {1338 throw new Error('Pattern too long for this browser.');1339 }1340 // Initialise the alphabet.1341 var s = this.match_alphabet_(pattern);1342 var dmp = this; // 'this' becomes 'window' in a closure.1343 /**1344 * Compute and return the score for a match with e errors and x location.1345 * Accesses loc and pattern through being a closure.1346 * @param {number} e Number of errors in match.1347 * @param {number} x Location of match.1348 * @return {number} Overall score for match (0.0 = good, 1.0 = bad).1349 * @private1350 */1351 function match_bitapScore_(e, x) {1352 var accuracy = e / pattern.length;1353 var proximity = Math.abs(loc - x);1354 if (!dmp.Match_Distance) {1355 // Dodge divide by zero error.1356 return proximity ? 1.0 : accuracy;1357 }1358 return accuracy + (proximity / dmp.Match_Distance);1359 }1360 // Highest score beyond which we give up.1361 var score_threshold = this.Match_Threshold;1362 // Is there a nearby exact match? (speedup)1363 var best_loc = text.indexOf(pattern, loc);1364 if (best_loc != -1) {1365 score_threshold = Math.min(match_bitapScore_(0, best_loc), score_threshold);1366 // What about in the other direction? (speedup)1367 best_loc = text.lastIndexOf(pattern, loc + pattern.length);1368 if (best_loc != -1) {1369 score_threshold =1370 Math.min(match_bitapScore_(0, best_loc), score_threshold);1371 }1372 }1373 // Initialise the bit arrays.1374 var matchmask = 1 << (pattern.length - 1);1375 best_loc = -1;1376 var bin_min, bin_mid;1377 var bin_max = pattern.length + text.length;1378 var last_rd;1379 for (var d = 0; d < pattern.length; d++) {1380 // Scan for the best match; each iteration allows for one more error.1381 // Run a binary search to determine how far from 'loc' we can stray at this1382 // error level.1383 bin_min = 0;1384 bin_mid = bin_max;1385 while (bin_min < bin_mid) {1386 if (match_bitapScore_(d, loc + bin_mid) <= score_threshold) {1387 bin_min = bin_mid;1388 } else {1389 bin_max = bin_mid;1390 }1391 bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min);1392 }1393 // Use the result from this iteration as the maximum for the next.1394 bin_max = bin_mid;1395 var start = Math.max(1, loc - bin_mid + 1);1396 var finish = Math.min(loc + bin_mid, text.length) + pattern.length;1397 var rd = Array(finish + 2);1398 rd[finish + 1] = (1 << d) - 1;1399 for (var j = finish; j >= start; j--) {1400 // The alphabet (s) is a sparse hash, so the following line generates1401 // warnings.1402 var charMatch = s[text.charAt(j - 1)];1403 if (d === 0) { // First pass: exact match.1404 rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;1405 } else { // Subsequent passes: fuzzy match.1406 rd[j] = (((rd[j + 1] << 1) | 1) & charMatch) |1407 (((last_rd[j + 1] | last_rd[j]) << 1) | 1) |1408 last_rd[j + 1];1409 }1410 if (rd[j] & matchmask) {1411 var score = match_bitapScore_(d, j - 1);1412 // This match will almost certainly be better than any existing match.1413 // But check anyway.1414 if (score <= score_threshold) {1415 // Told you so.1416 score_threshold = score;1417 best_loc = j - 1;1418 if (best_loc > loc) {1419 // When passing loc, don't exceed our current distance from loc.1420 start = Math.max(1, 2 * loc - best_loc);1421 } else {1422 // Already passed loc, downhill from here on in.1423 break;1424 }1425 }1426 }1427 }1428 // No hope for a (better) match at greater error levels.1429 if (match_bitapScore_(d + 1, loc) > score_threshold) {1430 break;1431 }1432 last_rd = rd;1433 }1434 return best_loc;1435};1436/**1437 * Initialise the alphabet for the Bitap algorithm.1438 * @param {string} pattern The text to encode.1439 * @return {!Object} Hash of character locations.1440 * @private1441 */1442diff_match_patch.prototype.match_alphabet_ = function(pattern) {1443 var s = {};1444 for (var i = 0; i < pattern.length; i++) {1445 s[pattern.charAt(i)] = 0;1446 }1447 for (var i = 0; i < pattern.length; i++) {1448 s[pattern.charAt(i)] |= 1 << (pattern.length - i - 1);1449 }1450 return s;1451};1452// PATCH FUNCTIONS1453/**1454 * Increase the context until it is unique,1455 * but don't let the pattern expand beyond Match_MaxBits.1456 * @param {!diff_match_patch.patch_obj} patch The patch to grow.1457 * @param {string} text Source text.1458 * @private1459 */1460diff_match_patch.prototype.patch_addContext_ = function(patch, text) {1461 if (text.length == 0) {1462 return;1463 }1464 var pattern = text.substring(patch.start2, patch.start2 + patch.length1);1465 var padding = 0;1466 // Look for the first and last matches of pattern in text. If two different1467 // matches are found, increase the pattern length.1468 while (text.indexOf(pattern) != text.lastIndexOf(pattern) &&1469 pattern.length < this.Match_MaxBits - this.Patch_Margin -1470 this.Patch_Margin) {1471 padding += this.Patch_Margin;1472 pattern = text.substring(patch.start2 - padding,1473 patch.start2 + patch.length1 + padding);1474 }1475 // Add one chunk for good luck.1476 padding += this.Patch_Margin;1477 // Add the prefix.1478 var prefix = text.substring(patch.start2 - padding, patch.start2);1479 if (prefix) {1480 patch.diffs.unshift([DIFF_EQUAL, prefix]);1481 }1482 // Add the suffix.1483 var suffix = text.substring(patch.start2 + patch.length1,1484 patch.start2 + patch.length1 + padding);1485 if (suffix) {1486 patch.diffs.push([DIFF_EQUAL, suffix]);1487 }1488 // Roll back the start points.1489 patch.start1 -= prefix.length;1490 patch.start2 -= prefix.length;1491 // Extend the lengths.1492 patch.length1 += prefix.length + suffix.length;1493 patch.length2 += prefix.length + suffix.length;1494};1495/**1496 * Compute a list of patches to turn text1 into text2.1497 * Use diffs if provided, otherwise compute it ourselves.1498 * There are four ways to call this function, depending on what data is1499 * available to the caller:1500 * Method 1:1501 * a = text1, b = text21502 * Method 2:1503 * a = diffs1504 * Method 3 (optimal):1505 * a = text1, b = diffs1506 * Method 4 (deprecated, use method 3):1507 * a = text1, b = text2, c = diffs1508 *1509 * @param {string|!Array.<!diff_match_patch.Diff>} a text1 (methods 1,3,4) or1510 * Array of diff tuples for text1 to text2 (method 2).1511 * @param {string|!Array.<!diff_match_patch.Diff>} opt_b text2 (methods 1,4) or1512 * Array of diff tuples for text1 to text2 (method 3) or undefined (method 2).1513 * @param {string|!Array.<!diff_match_patch.Diff>} opt_c Array of diff tuples1514 * for text1 to text2 (method 4) or undefined (methods 1,2,3).1515 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1516 */1517diff_match_patch.prototype.patch_make = function(a, opt_b, opt_c) {1518 var text1, diffs;1519 if (typeof a == 'string' && typeof opt_b == 'string' &&1520 typeof opt_c == 'undefined') {1521 // Method 1: text1, text21522 // Compute diffs from text1 and text2.1523 text1 = /** @type {string} */(a);1524 diffs = this.diff_main(text1, /** @type {string} */(opt_b), true);1525 if (diffs.length > 2) {1526 this.diff_cleanupSemantic(diffs);1527 this.diff_cleanupEfficiency(diffs);1528 }1529 } else if (a && typeof a == 'object' && typeof opt_b == 'undefined' &&1530 typeof opt_c == 'undefined') {1531 // Method 2: diffs1532 // Compute text1 from diffs.1533 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(a);1534 text1 = this.diff_text1(diffs);1535 } else if (typeof a == 'string' && opt_b && typeof opt_b == 'object' &&1536 typeof opt_c == 'undefined') {1537 // Method 3: text1, diffs1538 text1 = /** @type {string} */(a);1539 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(opt_b);1540 } else if (typeof a == 'string' && typeof opt_b == 'string' &&1541 opt_c && typeof opt_c == 'object') {1542 // Method 4: text1, text2, diffs1543 // text2 is not used.1544 text1 = /** @type {string} */(a);1545 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(opt_c);1546 } else {1547 throw new Error('Unknown call format to patch_make.');1548 }1549 if (diffs.length === 0) {1550 return []; // Get rid of the null case.1551 }1552 var patches = [];1553 var patch = new diff_match_patch.patch_obj();1554 var patchDiffLength = 0; // Keeping our own length var is faster in JS.1555 var char_count1 = 0; // Number of characters into the text1 string.1556 var char_count2 = 0; // Number of characters into the text2 string.1557 // Start with text1 (prepatch_text) and apply the diffs until we arrive at1558 // text2 (postpatch_text). We recreate the patches one by one to determine1559 // context info.1560 var prepatch_text = text1;1561 var postpatch_text = text1;1562 for (var x = 0; x < diffs.length; x++) {1563 var diff_type = diffs[x][0];1564 var diff_text = diffs[x][1];1565 if (!patchDiffLength && diff_type !== DIFF_EQUAL) {1566 // A new patch starts here.1567 patch.start1 = char_count1;1568 patch.start2 = char_count2;1569 }1570 switch (diff_type) {1571 case DIFF_INSERT:1572 patch.diffs[patchDiffLength++] = diffs[x];1573 patch.length2 += diff_text.length;1574 postpatch_text = postpatch_text.substring(0, char_count2) + diff_text +1575 postpatch_text.substring(char_count2);1576 break;1577 case DIFF_DELETE:1578 patch.length1 += diff_text.length;1579 patch.diffs[patchDiffLength++] = diffs[x];1580 postpatch_text = postpatch_text.substring(0, char_count2) +1581 postpatch_text.substring(char_count2 +1582 diff_text.length);1583 break;1584 case DIFF_EQUAL:1585 if (diff_text.length <= 2 * this.Patch_Margin &&1586 patchDiffLength && diffs.length != x + 1) {1587 // Small equality inside a patch.1588 patch.diffs[patchDiffLength++] = diffs[x];1589 patch.length1 += diff_text.length;1590 patch.length2 += diff_text.length;1591 } else if (diff_text.length >= 2 * this.Patch_Margin) {1592 // Time for a new patch.1593 if (patchDiffLength) {1594 this.patch_addContext_(patch, prepatch_text);1595 patches.push(patch);1596 patch = new diff_match_patch.patch_obj();1597 patchDiffLength = 0;1598 // Unlike Unidiff, our patch lists have a rolling context.1599 // http://code.google.com/p/google-diff-match-patch/wiki/Unidiff1600 // Update prepatch text & pos to reflect the application of the1601 // just completed patch.1602 prepatch_text = postpatch_text;1603 char_count1 = char_count2;1604 }1605 }1606 break;1607 }1608 // Update the current character count.1609 if (diff_type !== DIFF_INSERT) {1610 char_count1 += diff_text.length;1611 }1612 if (diff_type !== DIFF_DELETE) {1613 char_count2 += diff_text.length;1614 }1615 }1616 // Pick up the leftover patch if not empty.1617 if (patchDiffLength) {1618 this.patch_addContext_(patch, prepatch_text);1619 patches.push(patch);1620 }1621 return patches;1622};1623/**1624 * Given an array of patches, return another array that is identical.1625 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1626 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1627 */1628diff_match_patch.prototype.patch_deepCopy = function(patches) {1629 // Making deep copies is hard in JavaScript.1630 var patchesCopy = [];1631 for (var x = 0; x < patches.length; x++) {1632 var patch = patches[x];1633 var patchCopy = new diff_match_patch.patch_obj();1634 patchCopy.diffs = [];1635 for (var y = 0; y < patch.diffs.length; y++) {1636 patchCopy.diffs[y] = patch.diffs[y].slice();1637 }1638 patchCopy.start1 = patch.start1;1639 patchCopy.start2 = patch.start2;1640 patchCopy.length1 = patch.length1;1641 patchCopy.length2 = patch.length2;1642 patchesCopy[x] = patchCopy;1643 }1644 return patchesCopy;1645};1646/**1647 * Merge a set of patches onto the text. Return a patched text, as well1648 * as a list of true/false values indicating which patches were applied.1649 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1650 * @param {string} text Old text.1651 * @return {!Array.<string|!Array.<boolean>>} Two element Array, containing the1652 * new text and an array of boolean values.1653 */1654diff_match_patch.prototype.patch_apply = function(patches, text) {1655 if (patches.length == 0) {1656 return [text, []];1657 }1658 // Deep copy the patches so that no changes are made to originals.1659 patches = this.patch_deepCopy(patches);1660 var nullPadding = this.patch_addPadding(patches);1661 text = nullPadding + text + nullPadding;1662 this.patch_splitMax(patches);1663 // delta keeps track of the offset between the expected and actual location1664 // of the previous patch. If there are patches expected at positions 10 and1665 // 20, but the first patch was found at 12, delta is 2 and the second patch1666 // has an effective expected position of 22.1667 var delta = 0;1668 var results = [];1669 for (var x = 0; x < patches.length; x++) {1670 var expected_loc = patches[x].start2 + delta;1671 var text1 = this.diff_text1(patches[x].diffs);1672 var start_loc;1673 var end_loc = -1;1674 if (text1.length > this.Match_MaxBits) {1675 // patch_splitMax will only provide an oversized pattern in the case of1676 // a monster delete.1677 start_loc = this.match_main(text, text1.substring(0, this.Match_MaxBits),1678 expected_loc);1679 if (start_loc != -1) {1680 end_loc = this.match_main(text,1681 text1.substring(text1.length - this.Match_MaxBits),1682 expected_loc + text1.length - this.Match_MaxBits);1683 if (end_loc == -1 || start_loc >= end_loc) {1684 // Can't find valid trailing context. Drop this patch.1685 start_loc = -1;1686 }1687 }1688 } else {1689 start_loc = this.match_main(text, text1, expected_loc);1690 }1691 if (start_loc == -1) {1692 // No match found. :(1693 results[x] = false;1694 // Subtract the delta for this failed patch from subsequent patches.1695 delta -= patches[x].length2 - patches[x].length1;1696 } else {1697 // Found a match. :)1698 results[x] = true;1699 delta = start_loc - expected_loc;1700 var text2;1701 if (end_loc == -1) {1702 text2 = text.substring(start_loc, start_loc + text1.length);1703 } else {1704 text2 = text.substring(start_loc, end_loc + this.Match_MaxBits);1705 }1706 if (text1 == text2) {1707 // Perfect match, just shove the replacement text in.1708 text = text.substring(0, start_loc) +1709 this.diff_text2(patches[x].diffs) +1710 text.substring(start_loc + text1.length);1711 } else {1712 // Imperfect match. Run a diff to get a framework of equivalent1713 // indices.1714 var diffs = this.diff_main(text1, text2, false);1715 if (text1.length > this.Match_MaxBits &&1716 this.diff_levenshtein(diffs) / text1.length >1717 this.Patch_DeleteThreshold) {1718 // The end points match, but the content is unacceptably bad.1719 results[x] = false;1720 } else {1721 this.diff_cleanupSemanticLossless(diffs);1722 var index1 = 0;1723 var index2;1724 for (var y = 0; y < patches[x].diffs.length; y++) {1725 var mod = patches[x].diffs[y];1726 if (mod[0] !== DIFF_EQUAL) {1727 index2 = this.diff_xIndex(diffs, index1);1728 }1729 if (mod[0] === DIFF_INSERT) { // Insertion1730 text = text.substring(0, start_loc + index2) + mod[1] +1731 text.substring(start_loc + index2);1732 } else if (mod[0] === DIFF_DELETE) { // Deletion1733 text = text.substring(0, start_loc + index2) +1734 text.substring(start_loc + this.diff_xIndex(diffs,1735 index1 + mod[1].length));1736 }1737 if (mod[0] !== DIFF_DELETE) {1738 index1 += mod[1].length;1739 }1740 }1741 }1742 }1743 }1744 }1745 // Strip the padding off.1746 text = text.substring(nullPadding.length, text.length - nullPadding.length);1747 return [text, results];1748};1749/**1750 * Add some padding on text start and end so that edges can match something.1751 * Intended to be called only from within patch_apply.1752 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1753 * @return {string} The padding string added to each side.1754 */1755diff_match_patch.prototype.patch_addPadding = function(patches) {1756 var paddingLength = this.Patch_Margin;1757 var nullPadding = '';1758 for (var x = 1; x <= paddingLength; x++) {1759 nullPadding += String.fromCharCode(x);1760 }1761 // Bump all the patches forward.1762 for (var x = 0; x < patches.length; x++) {1763 patches[x].start1 += paddingLength;1764 patches[x].start2 += paddingLength;1765 }1766 // Add some padding on start of first diff.1767 var patch = patches[0];1768 var diffs = patch.diffs;1769 if (diffs.length == 0 || diffs[0][0] != DIFF_EQUAL) {1770 // Add nullPadding equality.1771 diffs.unshift([DIFF_EQUAL, nullPadding]);1772 patch.start1 -= paddingLength; // Should be 0.1773 patch.start2 -= paddingLength; // Should be 0.1774 patch.length1 += paddingLength;1775 patch.length2 += paddingLength;1776 } else if (paddingLength > diffs[0][1].length) {1777 // Grow first equality.1778 var extraLength = paddingLength - diffs[0][1].length;1779 diffs[0][1] = nullPadding.substring(diffs[0][1].length) + diffs[0][1];1780 patch.start1 -= extraLength;1781 patch.start2 -= extraLength;1782 patch.length1 += extraLength;1783 patch.length2 += extraLength;1784 }1785 // Add some padding on end of last diff.1786 patch = patches[patches.length - 1];1787 diffs = patch.diffs;1788 if (diffs.length == 0 || diffs[diffs.length - 1][0] != DIFF_EQUAL) {1789 // Add nullPadding equality.1790 diffs.push([DIFF_EQUAL, nullPadding]);1791 patch.length1 += paddingLength;1792 patch.length2 += paddingLength;1793 } else if (paddingLength > diffs[diffs.length - 1][1].length) {1794 // Grow last equality.1795 var extraLength = paddingLength - diffs[diffs.length - 1][1].length;1796 diffs[diffs.length - 1][1] += nullPadding.substring(0, extraLength);1797 patch.length1 += extraLength;1798 patch.length2 += extraLength;1799 }1800 return nullPadding;1801};1802/**1803 * Look through the patches and break up any which are longer than the maximum1804 * limit of the match algorithm.1805 * Intended to be called only from within patch_apply.1806 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1807 */1808diff_match_patch.prototype.patch_splitMax = function(patches) {1809 var patch_size = this.Match_MaxBits;1810 for (var x = 0; x < patches.length; x++) {1811 if (patches[x].length1 <= patch_size) {1812 continue;1813 }1814 var bigpatch = patches[x];1815 // Remove the big old patch.1816 patches.splice(x--, 1);1817 var start1 = bigpatch.start1;1818 var start2 = bigpatch.start2;1819 var precontext = '';1820 while (bigpatch.diffs.length !== 0) {1821 // Create one of several smaller patches.1822 var patch = new diff_match_patch.patch_obj();1823 var empty = true;1824 patch.start1 = start1 - precontext.length;1825 patch.start2 = start2 - precontext.length;1826 if (precontext !== '') {1827 patch.length1 = patch.length2 = precontext.length;1828 patch.diffs.push([DIFF_EQUAL, precontext]);1829 }1830 while (bigpatch.diffs.length !== 0 &&1831 patch.length1 < patch_size - this.Patch_Margin) {1832 var diff_type = bigpatch.diffs[0][0];1833 var diff_text = bigpatch.diffs[0][1];1834 if (diff_type === DIFF_INSERT) {1835 // Insertions are harmless.1836 patch.length2 += diff_text.length;1837 start2 += diff_text.length;1838 patch.diffs.push(bigpatch.diffs.shift());1839 empty = false;1840 } else if (diff_type === DIFF_DELETE && patch.diffs.length == 1 &&1841 patch.diffs[0][0] == DIFF_EQUAL &&1842 diff_text.length > 2 * patch_size) {1843 // This is a large deletion. Let it pass in one chunk.1844 patch.length1 += diff_text.length;1845 start1 += diff_text.length;1846 empty = false;1847 patch.diffs.push([diff_type, diff_text]);1848 bigpatch.diffs.shift();1849 } else {1850 // Deletion or equality. Only take as much as we can stomach.1851 diff_text = diff_text.substring(0,1852 patch_size - patch.length1 - this.Patch_Margin);1853 patch.length1 += diff_text.length;1854 start1 += diff_text.length;1855 if (diff_type === DIFF_EQUAL) {1856 patch.length2 += diff_text.length;1857 start2 += diff_text.length;1858 } else {1859 empty = false;1860 }1861 patch.diffs.push([diff_type, diff_text]);1862 if (diff_text == bigpatch.diffs[0][1]) {1863 bigpatch.diffs.shift();1864 } else {1865 bigpatch.diffs[0][1] =1866 bigpatch.diffs[0][1].substring(diff_text.length);1867 }1868 }1869 }1870 // Compute the head context for the next patch.1871 precontext = this.diff_text2(patch.diffs);1872 precontext =1873 precontext.substring(precontext.length - this.Patch_Margin);1874 // Append the end context for this patch.1875 var postcontext = this.diff_text1(bigpatch.diffs)1876 .substring(0, this.Patch_Margin);1877 if (postcontext !== '') {1878 patch.length1 += postcontext.length;1879 patch.length2 += postcontext.length;1880 if (patch.diffs.length !== 0 &&1881 patch.diffs[patch.diffs.length - 1][0] === DIFF_EQUAL) {1882 patch.diffs[patch.diffs.length - 1][1] += postcontext;1883 } else {1884 patch.diffs.push([DIFF_EQUAL, postcontext]);1885 }1886 }1887 if (!empty) {1888 patches.splice(++x, 0, patch);1889 }1890 }1891 }1892};1893/**1894 * Take a list of patches and return a textual representation.1895 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1896 * @return {string} Text representation of patches.1897 */1898diff_match_patch.prototype.patch_toText = function(patches) {1899 var text = [];1900 for (var x = 0; x < patches.length; x++) {1901 text[x] = patches[x];1902 }1903 return text.join('');1904};1905/**1906 * Parse a textual representation of patches and return a list of Patch objects.1907 * @param {string} textline Text representation of patches.1908 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1909 * @throws {!Error} If invalid input.1910 */1911diff_match_patch.prototype.patch_fromText = function(textline) {1912 var patches = [];1913 if (!textline) {1914 return patches;1915 }1916 var text = textline.split('\n');1917 var textPointer = 0;1918 var patchHeader = /^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/;1919 while (textPointer < text.length) {1920 var m = text[textPointer].match(patchHeader);1921 if (!m) {1922 throw new Error('Invalid patch string: ' + text[textPointer]);1923 }1924 var patch = new diff_match_patch.patch_obj();1925 patches.push(patch);1926 patch.start1 = parseInt(m[1], 10);1927 if (m[2] === '') {1928 patch.start1--;1929 patch.length1 = 1;1930 } else if (m[2] == '0') {1931 patch.length1 = 0;1932 } else {1933 patch.start1--;1934 patch.length1 = parseInt(m[2], 10);1935 }1936 patch.start2 = parseInt(m[3], 10);1937 if (m[4] === '') {1938 patch.start2--;1939 patch.length2 = 1;1940 } else if (m[4] == '0') {1941 patch.length2 = 0;1942 } else {1943 patch.start2--;1944 patch.length2 = parseInt(m[4], 10);1945 }1946 textPointer++;1947 while (textPointer < text.length) {1948 var sign = text[textPointer].charAt(0);1949 try {1950 var line = decodeURI(text[textPointer].substring(1));1951 } catch (ex) {1952 // Malformed URI sequence.1953 throw new Error('Illegal escape in patch_fromText: ' + line);1954 }1955 if (sign == '-') {1956 // Deletion.1957 patch.diffs.push([DIFF_DELETE, line]);1958 } else if (sign == '+') {1959 // Insertion.1960 patch.diffs.push([DIFF_INSERT, line]);1961 } else if (sign == ' ') {1962 // Minor equality.1963 patch.diffs.push([DIFF_EQUAL, line]);1964 } else if (sign == '@') {1965 // Start of next patch.1966 break;1967 } else if (sign === '') {1968 // Blank line? Whatever.1969 } else {1970 // WTF?1971 throw new Error('Invalid patch mode "' + sign + '" in: ' + line);1972 }1973 textPointer++;1974 }1975 }1976 return patches;1977};1978/**1979 * Class representing one patch operation.1980 * @constructor1981 */1982diff_match_patch.patch_obj = function() {1983 /** @type {!Array.<!diff_match_patch.Diff>} */1984 this.diffs = [];1985 /** @type {?number} */1986 this.start1 = null;1987 /** @type {?number} */1988 this.start2 = null;1989 /** @type {number} */1990 this.length1 = 0;1991 /** @type {number} */1992 this.length2 = 0;1993};1994/**1995 * Emmulate GNU diff's format.1996 * Header: @@ -382,8 +481,9 @@1997 * Indicies are printed as 1-based, not 0-based.1998 * @return {string} The GNU diff string.1999 */2000diff_match_patch.patch_obj.prototype.toString = function() {2001 var coords1, coords2;2002 if (this.length1 === 0) {2003 coords1 = this.start1 + ',0';2004 } else if (this.length1 == 1) {2005 coords1 = this.start1 + 1;2006 } else {2007 coords1 = (this.start1 + 1) + ',' + this.length1;2008 }2009 if (this.length2 === 0) {2010 coords2 = this.start2 + ',0';2011 } else if (this.length2 == 1) {2012 coords2 = this.start2 + 1;2013 } else {2014 coords2 = (this.start2 + 1) + ',' + this.length2;2015 }2016 var text = ['@@ -' + coords1 + ' +' + coords2 + ' @@\n'];2017 var op;2018 // Escape the body of the patch with %xx notation.2019 for (var x = 0; x < this.diffs.length; x++) {2020 switch (this.diffs[x][0]) {2021 case DIFF_INSERT:2022 op = '+';2023 break;2024 case DIFF_DELETE:2025 op = '-';2026 break;2027 case DIFF_EQUAL:2028 op = ' ';2029 break;2030 }2031 text[x + 1] = op + encodeURI(this.diffs[x][1]) + '\n';2032 }2033 return text.join('').replace(/%20/g, ' ');2034};2035// Export these global variables so that they survive Google's JS compiler.2036// In a browser, 'this' will be 'window'.2037// Users of node.js should 'require' the uncompressed version since Google's2038// JS compiler may break the following exports for non-browser environments.2039this['diff_match_patch'] = diff_match_patch;2040this['DIFF_DELETE'] = DIFF_DELETE;2041this['DIFF_INSERT'] = DIFF_INSERT;...

Full Screen

Full Screen

diff_match_patch_amd.js

Source:diff_match_patch_amd.js Github

copy

Full Screen

1/**2 * Diff Match and Patch3 *4 * Copyright 2006 Google Inc.5 * http://code.google.com/p/google-diff-match-patch/6 *7 * Licensed under the Apache License, Version 2.0 (the "License");8 * you may not use this file except in compliance with the License.9 * You may obtain a copy of the License at10 *11 * http://www.apache.org/licenses/LICENSE-2.012 *13 * Unless required by applicable law or agreed to in writing, software14 * distributed under the License is distributed on an "AS IS" BASIS,15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.16 * See the License for the specific language governing permissions and17 * limitations under the License.18 */19/**20 * @fileoverview Computes the difference between two texts to create a patch.21 * Applies the patch onto another text, allowing for errors.22 * @author fraser@google.com (Neil Fraser)23 */24define(function(require, exports, module) {25/**26 * Class containing the diff, match and patch methods.27 * @constructor28 */29function diff_match_patch() {30 // Defaults.31 // Redefine these in your program to override the defaults.32 // Number of seconds to map a diff before giving up (0 for infinity).33 this.Diff_Timeout = 1.0;34 // Cost of an empty edit operation in terms of edit characters.35 this.Diff_EditCost = 4;36 // At what point is no match declared (0.0 = perfection, 1.0 = very loose).37 this.Match_Threshold = 0.5;38 // How far to search for a match (0 = exact location, 1000+ = broad match).39 // A match this many characters away from the expected location will add40 // 1.0 to the score (0.0 is a perfect match).41 this.Match_Distance = 1000;42 // When deleting a large block of text (over ~64 characters), how close do43 // the contents have to be to match the expected contents. (0.0 = perfection,44 // 1.0 = very loose). Note that Match_Threshold controls how closely the45 // end points of a delete need to match.46 this.Patch_DeleteThreshold = 0.5;47 // Chunk size for context length.48 this.Patch_Margin = 4;49 // The number of bits in an int.50 this.Match_MaxBits = 32;51}52// DIFF FUNCTIONS53/**54 * The data structure representing a diff is an array of tuples:55 * [[DIFF_DELETE, 'Hello'], [DIFF_INSERT, 'Goodbye'], [DIFF_EQUAL, ' world.']]56 * which means: delete 'Hello', add 'Goodbye' and keep ' world.'57 */58var DIFF_DELETE = -1;59var DIFF_INSERT = 1;60var DIFF_EQUAL = 0;61/** @typedef {{0: number, 1: string}} */62diff_match_patch.Diff;63/**64 * Find the differences between two texts. Simplifies the problem by stripping65 * any common prefix or suffix off the texts before diffing.66 * @param {string} text1 Old string to be diffed.67 * @param {string} text2 New string to be diffed.68 * @param {boolean=} opt_checklines Optional speedup flag. If present and false,69 * then don't run a line-level diff first to identify the changed areas.70 * Defaults to true, which does a faster, slightly less optimal diff.71 * @param {number} opt_deadline Optional time when the diff should be complete72 * by. Used internally for recursive calls. Users should set DiffTimeout73 * instead.74 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.75 */76diff_match_patch.prototype.diff_main = function(text1, text2, opt_checklines,77 opt_deadline) {78 // Set a deadline by which time the diff must be complete.79 if (typeof opt_deadline == 'undefined') {80 if (this.Diff_Timeout <= 0) {81 opt_deadline = Number.MAX_VALUE;82 } else {83 opt_deadline = (new Date).getTime() + this.Diff_Timeout * 1000;84 }85 }86 var deadline = opt_deadline;87 // Check for null inputs.88 if (text1 == null || text2 == null) {89 throw new Error('Null input. (diff_main)');90 }91 // Check for equality (speedup).92 if (text1 == text2) {93 if (text1) {94 return [[DIFF_EQUAL, text1]];95 }96 return [];97 }98 if (typeof opt_checklines == 'undefined') {99 opt_checklines = true;100 }101 var checklines = opt_checklines;102 // Trim off common prefix (speedup).103 var commonlength = this.diff_commonPrefix(text1, text2);104 var commonprefix = text1.substring(0, commonlength);105 text1 = text1.substring(commonlength);106 text2 = text2.substring(commonlength);107 // Trim off common suffix (speedup).108 commonlength = this.diff_commonSuffix(text1, text2);109 var commonsuffix = text1.substring(text1.length - commonlength);110 text1 = text1.substring(0, text1.length - commonlength);111 text2 = text2.substring(0, text2.length - commonlength);112 // Compute the diff on the middle block.113 var diffs = this.diff_compute_(text1, text2, checklines, deadline);114 // Restore the prefix and suffix.115 if (commonprefix) {116 diffs.unshift([DIFF_EQUAL, commonprefix]);117 }118 if (commonsuffix) {119 diffs.push([DIFF_EQUAL, commonsuffix]);120 }121 this.diff_cleanupMerge(diffs);122 return diffs;123};124/**125 * Find the differences between two texts. Assumes that the texts do not126 * have any common prefix or suffix.127 * @param {string} text1 Old string to be diffed.128 * @param {string} text2 New string to be diffed.129 * @param {boolean} checklines Speedup flag. If false, then don't run a130 * line-level diff first to identify the changed areas.131 * If true, then run a faster, slightly less optimal diff.132 * @param {number} deadline Time when the diff should be complete by.133 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.134 * @private135 */136diff_match_patch.prototype.diff_compute_ = function(text1, text2, checklines,137 deadline) {138 var diffs;139 if (!text1) {140 // Just add some text (speedup).141 return [[DIFF_INSERT, text2]];142 }143 if (!text2) {144 // Just delete some text (speedup).145 return [[DIFF_DELETE, text1]];146 }147 /** @type {?string} */148 var longtext = text1.length > text2.length ? text1 : text2;149 /** @type {?string} */150 var shorttext = text1.length > text2.length ? text2 : text1;151 var i = longtext.indexOf(shorttext);152 if (i != -1) {153 // Shorter text is inside the longer text (speedup).154 diffs = [[DIFF_INSERT, longtext.substring(0, i)],155 [DIFF_EQUAL, shorttext],156 [DIFF_INSERT, longtext.substring(i + shorttext.length)]];157 // Swap insertions for deletions if diff is reversed.158 if (text1.length > text2.length) {159 diffs[0][0] = diffs[2][0] = DIFF_DELETE;160 }161 return diffs;162 }163 if (shorttext.length == 1) {164 // Single character string.165 // After the previous speedup, the character can't be an equality.166 return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];167 }168 longtext = shorttext = null; // Garbage collect.169 // Check to see if the problem can be split in two.170 var hm = this.diff_halfMatch_(text1, text2);171 if (hm) {172 // A half-match was found, sort out the return data.173 var text1_a = hm[0];174 var text1_b = hm[1];175 var text2_a = hm[2];176 var text2_b = hm[3];177 var mid_common = hm[4];178 // Send both pairs off for separate processing.179 var diffs_a = this.diff_main(text1_a, text2_a, checklines, deadline);180 var diffs_b = this.diff_main(text1_b, text2_b, checklines, deadline);181 // Merge the results.182 return diffs_a.concat([[DIFF_EQUAL, mid_common]], diffs_b);183 }184 if (checklines && text1.length > 100 && text2.length > 100) {185 return this.diff_lineMode_(text1, text2, deadline);186 }187 return this.diff_bisect_(text1, text2, deadline);188};189/**190 * Do a quick line-level diff on both strings, then rediff the parts for191 * greater accuracy.192 * This speedup can produce non-minimal diffs.193 * @param {string} text1 Old string to be diffed.194 * @param {string} text2 New string to be diffed.195 * @param {number} deadline Time when the diff should be complete by.196 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.197 * @private198 */199diff_match_patch.prototype.diff_lineMode_ = function(text1, text2, deadline) {200 // Scan the text on a line-by-line basis first.201 var a = this.diff_linesToChars_(text1, text2);202 text1 = a.chars1;203 text2 = a.chars2;204 var linearray = a.lineArray;205 var diffs = this.diff_main(text1, text2, false, deadline);206 // Convert the diff back to original text.207 this.diff_charsToLines_(diffs, linearray);208 // Eliminate freak matches (e.g. blank lines)209 this.diff_cleanupSemantic(diffs);210 // Rediff any replacement blocks, this time character-by-character.211 // Add a dummy entry at the end.212 diffs.push([DIFF_EQUAL, '']);213 var pointer = 0;214 var count_delete = 0;215 var count_insert = 0;216 var text_delete = '';217 var text_insert = '';218 while (pointer < diffs.length) {219 switch (diffs[pointer][0]) {220 case DIFF_INSERT:221 count_insert++;222 text_insert += diffs[pointer][1];223 break;224 case DIFF_DELETE:225 count_delete++;226 text_delete += diffs[pointer][1];227 break;228 case DIFF_EQUAL:229 // Upon reaching an equality, check for prior redundancies.230 if (count_delete >= 1 && count_insert >= 1) {231 // Delete the offending records and add the merged ones.232 diffs.splice(pointer - count_delete - count_insert,233 count_delete + count_insert);234 pointer = pointer - count_delete - count_insert;235 var a = this.diff_main(text_delete, text_insert, false, deadline);236 for (var j = a.length - 1; j >= 0; j--) {237 diffs.splice(pointer, 0, a[j]);238 }239 pointer = pointer + a.length;240 }241 count_insert = 0;242 count_delete = 0;243 text_delete = '';244 text_insert = '';245 break;246 }247 pointer++;248 }249 diffs.pop(); // Remove the dummy entry at the end.250 return diffs;251};252/**253 * Find the 'middle snake' of a diff, split the problem in two254 * and return the recursively constructed diff.255 * See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.256 * @param {string} text1 Old string to be diffed.257 * @param {string} text2 New string to be diffed.258 * @param {number} deadline Time at which to bail if not yet complete.259 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.260 * @private261 */262diff_match_patch.prototype.diff_bisect_ = function(text1, text2, deadline) {263 // Cache the text lengths to prevent multiple calls.264 var text1_length = text1.length;265 var text2_length = text2.length;266 var max_d = Math.ceil((text1_length + text2_length) / 2);267 var v_offset = max_d;268 var v_length = 2 * max_d;269 var v1 = new Array(v_length);270 var v2 = new Array(v_length);271 // Setting all elements to -1 is faster in Chrome & Firefox than mixing272 // integers and undefined.273 for (var x = 0; x < v_length; x++) {274 v1[x] = -1;275 v2[x] = -1;276 }277 v1[v_offset + 1] = 0;278 v2[v_offset + 1] = 0;279 var delta = text1_length - text2_length;280 // If the total number of characters is odd, then the front path will collide281 // with the reverse path.282 var front = (delta % 2 != 0);283 // Offsets for start and end of k loop.284 // Prevents mapping of space beyond the grid.285 var k1start = 0;286 var k1end = 0;287 var k2start = 0;288 var k2end = 0;289 for (var d = 0; d < max_d; d++) {290 // Bail out if deadline is reached.291 if ((new Date()).getTime() > deadline) {292 break;293 }294 // Walk the front path one step.295 for (var k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {296 var k1_offset = v_offset + k1;297 var x1;298 if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {299 x1 = v1[k1_offset + 1];300 } else {301 x1 = v1[k1_offset - 1] + 1;302 }303 var y1 = x1 - k1;304 while (x1 < text1_length && y1 < text2_length &&305 text1.charAt(x1) == text2.charAt(y1)) {306 x1++;307 y1++;308 }309 v1[k1_offset] = x1;310 if (x1 > text1_length) {311 // Ran off the right of the graph.312 k1end += 2;313 } else if (y1 > text2_length) {314 // Ran off the bottom of the graph.315 k1start += 2;316 } else if (front) {317 var k2_offset = v_offset + delta - k1;318 if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {319 // Mirror x2 onto top-left coordinate system.320 var x2 = text1_length - v2[k2_offset];321 if (x1 >= x2) {322 // Overlap detected.323 return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);324 }325 }326 }327 }328 // Walk the reverse path one step.329 for (var k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {330 var k2_offset = v_offset + k2;331 var x2;332 if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {333 x2 = v2[k2_offset + 1];334 } else {335 x2 = v2[k2_offset - 1] + 1;336 }337 var y2 = x2 - k2;338 while (x2 < text1_length && y2 < text2_length &&339 text1.charAt(text1_length - x2 - 1) ==340 text2.charAt(text2_length - y2 - 1)) {341 x2++;342 y2++;343 }344 v2[k2_offset] = x2;345 if (x2 > text1_length) {346 // Ran off the left of the graph.347 k2end += 2;348 } else if (y2 > text2_length) {349 // Ran off the top of the graph.350 k2start += 2;351 } else if (!front) {352 var k1_offset = v_offset + delta - k2;353 if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {354 var x1 = v1[k1_offset];355 var y1 = v_offset + x1 - k1_offset;356 // Mirror x2 onto top-left coordinate system.357 x2 = text1_length - x2;358 if (x1 >= x2) {359 // Overlap detected.360 return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);361 }362 }363 }364 }365 }366 // Diff took too long and hit the deadline or367 // number of diffs equals number of characters, no commonality at all.368 return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];369};370/**371 * Given the location of the 'middle snake', split the diff in two parts372 * and recurse.373 * @param {string} text1 Old string to be diffed.374 * @param {string} text2 New string to be diffed.375 * @param {number} x Index of split point in text1.376 * @param {number} y Index of split point in text2.377 * @param {number} deadline Time at which to bail if not yet complete.378 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.379 * @private380 */381diff_match_patch.prototype.diff_bisectSplit_ = function(text1, text2, x, y,382 deadline) {383 var text1a = text1.substring(0, x);384 var text2a = text2.substring(0, y);385 var text1b = text1.substring(x);386 var text2b = text2.substring(y);387 // Compute both diffs serially.388 var diffs = this.diff_main(text1a, text2a, false, deadline);389 var diffsb = this.diff_main(text1b, text2b, false, deadline);390 return diffs.concat(diffsb);391};392/**393 * Split two texts into an array of strings. Reduce the texts to a string of394 * hashes where each Unicode character represents one line.395 * @param {string} text1 First string.396 * @param {string} text2 Second string.397 * @return {{chars1: string, chars2: string, lineArray: !Array.<string>}}398 * An object containing the encoded text1, the encoded text2 and399 * the array of unique strings.400 * The zeroth element of the array of unique strings is intentionally blank.401 * @private402 */403diff_match_patch.prototype.diff_linesToChars_ = function(text1, text2) {404 var lineArray = []; // e.g. lineArray[4] == 'Hello\n'405 var lineHash = {}; // e.g. lineHash['Hello\n'] == 4406 // '\x00' is a valid character, but various debuggers don't like it.407 // So we'll insert a junk entry to avoid generating a null character.408 lineArray[0] = '';409 /**410 * Split a text into an array of strings. Reduce the texts to a string of411 * hashes where each Unicode character represents one line.412 * Modifies linearray and linehash through being a closure.413 * @param {string} text String to encode.414 * @return {string} Encoded string.415 * @private416 */417 function diff_linesToCharsMunge_(text) {418 var chars = '';419 // Walk the text, pulling out a substring for each line.420 // text.split('\n') would would temporarily double our memory footprint.421 // Modifying text would create many large strings to garbage collect.422 var lineStart = 0;423 var lineEnd = -1;424 // Keeping our own length variable is faster than looking it up.425 var lineArrayLength = lineArray.length;426 while (lineEnd < text.length - 1) {427 lineEnd = text.indexOf('\n', lineStart);428 if (lineEnd == -1) {429 lineEnd = text.length - 1;430 }431 var line = text.substring(lineStart, lineEnd + 1);432 lineStart = lineEnd + 1;433 if (lineHash.hasOwnProperty ? lineHash.hasOwnProperty(line) :434 (lineHash[line] !== undefined)) {435 chars += String.fromCharCode(lineHash[line]);436 } else {437 chars += String.fromCharCode(lineArrayLength);438 lineHash[line] = lineArrayLength;439 lineArray[lineArrayLength++] = line;440 }441 }442 return chars;443 }444 var chars1 = diff_linesToCharsMunge_(text1);445 var chars2 = diff_linesToCharsMunge_(text2);446 return { chars1: chars1, chars2: chars2, lineArray: lineArray };447};448/**449 * Rehydrate the text in a diff from a string of line hashes to real lines of450 * text.451 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.452 * @param {!Array.<string>} lineArray Array of unique strings.453 * @private454 */455diff_match_patch.prototype.diff_charsToLines_ = function(diffs, lineArray) {456 for (var x = 0; x < diffs.length; x++) {457 var chars = diffs[x][1];458 var text = [];459 for (var y = 0; y < chars.length; y++) {460 text[y] = lineArray[chars.charCodeAt(y)];461 }462 diffs[x][1] = text.join('');463 }464};465/**466 * Determine the common prefix of two strings.467 * @param {string} text1 First string.468 * @param {string} text2 Second string.469 * @return {number} The number of characters common to the start of each470 * string.471 */472diff_match_patch.prototype.diff_commonPrefix = function(text1, text2) {473 // Quick check for common null cases.474 if (!text1 || !text2 || text1.charAt(0) != text2.charAt(0)) {475 return 0;476 }477 // Binary search.478 // Performance analysis: http://neil.fraser.name/news/2007/10/09/479 var pointermin = 0;480 var pointermax = Math.min(text1.length, text2.length);481 var pointermid = pointermax;482 var pointerstart = 0;483 while (pointermin < pointermid) {484 if (text1.substring(pointerstart, pointermid) ==485 text2.substring(pointerstart, pointermid)) {486 pointermin = pointermid;487 pointerstart = pointermin;488 } else {489 pointermax = pointermid;490 }491 pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);492 }493 return pointermid;494};495/**496 * Determine the common suffix of two strings.497 * @param {string} text1 First string.498 * @param {string} text2 Second string.499 * @return {number} The number of characters common to the end of each string.500 */501diff_match_patch.prototype.diff_commonSuffix = function(text1, text2) {502 // Quick check for common null cases.503 if (!text1 || !text2 ||504 text1.charAt(text1.length - 1) != text2.charAt(text2.length - 1)) {505 return 0;506 }507 // Binary search.508 // Performance analysis: http://neil.fraser.name/news/2007/10/09/509 var pointermin = 0;510 var pointermax = Math.min(text1.length, text2.length);511 var pointermid = pointermax;512 var pointerend = 0;513 while (pointermin < pointermid) {514 if (text1.substring(text1.length - pointermid, text1.length - pointerend) ==515 text2.substring(text2.length - pointermid, text2.length - pointerend)) {516 pointermin = pointermid;517 pointerend = pointermin;518 } else {519 pointermax = pointermid;520 }521 pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);522 }523 return pointermid;524};525/**526 * Determine if the suffix of one string is the prefix of another.527 * @param {string} text1 First string.528 * @param {string} text2 Second string.529 * @return {number} The number of characters common to the end of the first530 * string and the start of the second string.531 * @private532 */533diff_match_patch.prototype.diff_commonOverlap_ = function(text1, text2) {534 // Cache the text lengths to prevent multiple calls.535 var text1_length = text1.length;536 var text2_length = text2.length;537 // Eliminate the null case.538 if (text1_length == 0 || text2_length == 0) {539 return 0;540 }541 // Truncate the longer string.542 if (text1_length > text2_length) {543 text1 = text1.substring(text1_length - text2_length);544 } else if (text1_length < text2_length) {545 text2 = text2.substring(0, text1_length);546 }547 var text_length = Math.min(text1_length, text2_length);548 // Quick check for the worst case.549 if (text1 == text2) {550 return text_length;551 }552 // Start by looking for a single character match553 // and increase length until no match is found.554 // Performance analysis: http://neil.fraser.name/news/2010/11/04/555 var best = 0;556 var length = 1;557 while (true) {558 var pattern = text1.substring(text_length - length);559 var found = text2.indexOf(pattern);560 if (found == -1) {561 return best;562 }563 length += found;564 if (found == 0 || text1.substring(text_length - length) ==565 text2.substring(0, length)) {566 best = length;567 length++;568 }569 }570};571/**572 * Do the two texts share a substring which is at least half the length of the573 * longer text?574 * This speedup can produce non-minimal diffs.575 * @param {string} text1 First string.576 * @param {string} text2 Second string.577 * @return {Array.<string>} Five element Array, containing the prefix of578 * text1, the suffix of text1, the prefix of text2, the suffix of579 * text2 and the common middle. Or null if there was no match.580 * @private581 */582diff_match_patch.prototype.diff_halfMatch_ = function(text1, text2) {583 if (this.Diff_Timeout <= 0) {584 // Don't risk returning a non-optimal diff if we have unlimited time.585 return null;586 }587 var longtext = text1.length > text2.length ? text1 : text2;588 var shorttext = text1.length > text2.length ? text2 : text1;589 if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {590 return null; // Pointless.591 }592 var dmp = this; // 'this' becomes 'window' in a closure.593 /**594 * Does a substring of shorttext exist within longtext such that the substring595 * is at least half the length of longtext?596 * Closure, but does not reference any external variables.597 * @param {string} longtext Longer string.598 * @param {string} shorttext Shorter string.599 * @param {number} i Start index of quarter length substring within longtext.600 * @return {Array.<string>} Five element Array, containing the prefix of601 * longtext, the suffix of longtext, the prefix of shorttext, the suffix602 * of shorttext and the common middle. Or null if there was no match.603 * @private604 */605 function diff_halfMatchI_(longtext, shorttext, i) {606 // Start with a 1/4 length substring at position i as a seed.607 var seed = longtext.substring(i, i + Math.floor(longtext.length / 4));608 var j = -1;609 var best_common = '';610 var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;611 while ((j = shorttext.indexOf(seed, j + 1)) != -1) {612 var prefixLength = dmp.diff_commonPrefix(longtext.substring(i),613 shorttext.substring(j));614 var suffixLength = dmp.diff_commonSuffix(longtext.substring(0, i),615 shorttext.substring(0, j));616 if (best_common.length < suffixLength + prefixLength) {617 best_common = shorttext.substring(j - suffixLength, j) +618 shorttext.substring(j, j + prefixLength);619 best_longtext_a = longtext.substring(0, i - suffixLength);620 best_longtext_b = longtext.substring(i + prefixLength);621 best_shorttext_a = shorttext.substring(0, j - suffixLength);622 best_shorttext_b = shorttext.substring(j + prefixLength);623 }624 }625 if (best_common.length * 2 >= longtext.length) {626 return [best_longtext_a, best_longtext_b,627 best_shorttext_a, best_shorttext_b, best_common];628 } else {629 return null;630 }631 }632 // First check if the second quarter is the seed for a half-match.633 var hm1 = diff_halfMatchI_(longtext, shorttext,634 Math.ceil(longtext.length / 4));635 // Check again based on the third quarter.636 var hm2 = diff_halfMatchI_(longtext, shorttext,637 Math.ceil(longtext.length / 2));638 var hm;639 if (!hm1 && !hm2) {640 return null;641 } else if (!hm2) {642 hm = hm1;643 } else if (!hm1) {644 hm = hm2;645 } else {646 // Both matched. Select the longest.647 hm = hm1[4].length > hm2[4].length ? hm1 : hm2;648 }649 // A half-match was found, sort out the return data.650 var text1_a, text1_b, text2_a, text2_b;651 if (text1.length > text2.length) {652 text1_a = hm[0];653 text1_b = hm[1];654 text2_a = hm[2];655 text2_b = hm[3];656 } else {657 text2_a = hm[0];658 text2_b = hm[1];659 text1_a = hm[2];660 text1_b = hm[3];661 }662 var mid_common = hm[4];663 return [text1_a, text1_b, text2_a, text2_b, mid_common];664};665/**666 * Reduce the number of edits by eliminating semantically trivial equalities.667 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.668 */669diff_match_patch.prototype.diff_cleanupSemantic = function(diffs) {670 var changes = false;671 var equalities = []; // Stack of indices where equalities are found.672 var equalitiesLength = 0; // Keeping our own length var is faster in JS.673 /** @type {?string} */674 var lastequality = null;675 // Always equal to diffs[equalities[equalitiesLength - 1]][1]676 var pointer = 0; // Index of current position.677 // Number of characters that changed prior to the equality.678 var length_insertions1 = 0;679 var length_deletions1 = 0;680 // Number of characters that changed after the equality.681 var length_insertions2 = 0;682 var length_deletions2 = 0;683 while (pointer < diffs.length) {684 if (diffs[pointer][0] == DIFF_EQUAL) { // Equality found.685 equalities[equalitiesLength++] = pointer;686 length_insertions1 = length_insertions2;687 length_deletions1 = length_deletions2;688 length_insertions2 = 0;689 length_deletions2 = 0;690 lastequality = diffs[pointer][1];691 } else { // An insertion or deletion.692 if (diffs[pointer][0] == DIFF_INSERT) {693 length_insertions2 += diffs[pointer][1].length;694 } else {695 length_deletions2 += diffs[pointer][1].length;696 }697 // Eliminate an equality that is smaller or equal to the edits on both698 // sides of it.699 if (lastequality && (lastequality.length <=700 Math.max(length_insertions1, length_deletions1)) &&701 (lastequality.length <= Math.max(length_insertions2,702 length_deletions2))) {703 // Duplicate record.704 diffs.splice(equalities[equalitiesLength - 1], 0,705 [DIFF_DELETE, lastequality]);706 // Change second copy to insert.707 diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;708 // Throw away the equality we just deleted.709 equalitiesLength--;710 // Throw away the previous equality (it needs to be reevaluated).711 equalitiesLength--;712 pointer = equalitiesLength > 0 ? equalities[equalitiesLength - 1] : -1;713 length_insertions1 = 0; // Reset the counters.714 length_deletions1 = 0;715 length_insertions2 = 0;716 length_deletions2 = 0;717 lastequality = null;718 changes = true;719 }720 }721 pointer++;722 }723 // Normalize the diff.724 if (changes) {725 this.diff_cleanupMerge(diffs);726 }727 this.diff_cleanupSemanticLossless(diffs);728 // Find any overlaps between deletions and insertions.729 // e.g: <del>abcxxx</del><ins>xxxdef</ins>730 // -> <del>abc</del>xxx<ins>def</ins>731 // e.g: <del>xxxabc</del><ins>defxxx</ins>732 // -> <ins>def</ins>xxx<del>abc</del>733 // Only extract an overlap if it is as big as the edit ahead or behind it.734 pointer = 1;735 while (pointer < diffs.length) {736 if (diffs[pointer - 1][0] == DIFF_DELETE &&737 diffs[pointer][0] == DIFF_INSERT) {738 var deletion = diffs[pointer - 1][1];739 var insertion = diffs[pointer][1];740 var overlap_length1 = this.diff_commonOverlap_(deletion, insertion);741 var overlap_length2 = this.diff_commonOverlap_(insertion, deletion);742 if (overlap_length1 >= overlap_length2) {743 if (overlap_length1 >= deletion.length / 2 ||744 overlap_length1 >= insertion.length / 2) {745 // Overlap found. Insert an equality and trim the surrounding edits.746 diffs.splice(pointer, 0,747 [DIFF_EQUAL, insertion.substring(0, overlap_length1)]);748 diffs[pointer - 1][1] =749 deletion.substring(0, deletion.length - overlap_length1);750 diffs[pointer + 1][1] = insertion.substring(overlap_length1);751 pointer++;752 }753 } else {754 if (overlap_length2 >= deletion.length / 2 ||755 overlap_length2 >= insertion.length / 2) {756 // Reverse overlap found.757 // Insert an equality and swap and trim the surrounding edits.758 diffs.splice(pointer, 0,759 [DIFF_EQUAL, deletion.substring(0, overlap_length2)]);760 diffs[pointer - 1][0] = DIFF_INSERT;761 diffs[pointer - 1][1] =762 insertion.substring(0, insertion.length - overlap_length2);763 diffs[pointer + 1][0] = DIFF_DELETE;764 diffs[pointer + 1][1] =765 deletion.substring(overlap_length2);766 pointer++;767 }768 }769 pointer++;770 }771 pointer++;772 }773};774/**775 * Look for single edits surrounded on both sides by equalities776 * which can be shifted sideways to align the edit to a word boundary.777 * e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.778 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.779 */780diff_match_patch.prototype.diff_cleanupSemanticLossless = function(diffs) {781 /**782 * Given two strings, compute a score representing whether the internal783 * boundary falls on logical boundaries.784 * Scores range from 6 (best) to 0 (worst).785 * Closure, but does not reference any external variables.786 * @param {string} one First string.787 * @param {string} two Second string.788 * @return {number} The score.789 * @private790 */791 function diff_cleanupSemanticScore_(one, two) {792 if (!one || !two) {793 // Edges are the best.794 return 6;795 }796 // Each port of this function behaves slightly differently due to797 // subtle differences in each language's definition of things like798 // 'whitespace'. Since this function's purpose is largely cosmetic,799 // the choice has been made to use each language's native features800 // rather than force total conformity.801 var char1 = one.charAt(one.length - 1);802 var char2 = two.charAt(0);803 var nonAlphaNumeric1 = char1.match(diff_match_patch.nonAlphaNumericRegex_);804 var nonAlphaNumeric2 = char2.match(diff_match_patch.nonAlphaNumericRegex_);805 var whitespace1 = nonAlphaNumeric1 &&806 char1.match(diff_match_patch.whitespaceRegex_);807 var whitespace2 = nonAlphaNumeric2 &&808 char2.match(diff_match_patch.whitespaceRegex_);809 var lineBreak1 = whitespace1 &&810 char1.match(diff_match_patch.linebreakRegex_);811 var lineBreak2 = whitespace2 &&812 char2.match(diff_match_patch.linebreakRegex_);813 var blankLine1 = lineBreak1 &&814 one.match(diff_match_patch.blanklineEndRegex_);815 var blankLine2 = lineBreak2 &&816 two.match(diff_match_patch.blanklineStartRegex_);817 if (blankLine1 || blankLine2) {818 // Five points for blank lines.819 return 5;820 } else if (lineBreak1 || lineBreak2) {821 // Four points for line breaks.822 return 4;823 } else if (nonAlphaNumeric1 && !whitespace1 && whitespace2) {824 // Three points for end of sentences.825 return 3;826 } else if (whitespace1 || whitespace2) {827 // Two points for whitespace.828 return 2;829 } else if (nonAlphaNumeric1 || nonAlphaNumeric2) {830 // One point for non-alphanumeric.831 return 1;832 }833 return 0;834 }835 var pointer = 1;836 // Intentionally ignore the first and last element (don't need checking).837 while (pointer < diffs.length - 1) {838 if (diffs[pointer - 1][0] == DIFF_EQUAL &&839 diffs[pointer + 1][0] == DIFF_EQUAL) {840 // This is a single edit surrounded by equalities.841 var equality1 = diffs[pointer - 1][1];842 var edit = diffs[pointer][1];843 var equality2 = diffs[pointer + 1][1];844 // First, shift the edit as far left as possible.845 var commonOffset = this.diff_commonSuffix(equality1, edit);846 if (commonOffset) {847 var commonString = edit.substring(edit.length - commonOffset);848 equality1 = equality1.substring(0, equality1.length - commonOffset);849 edit = commonString + edit.substring(0, edit.length - commonOffset);850 equality2 = commonString + equality2;851 }852 // Second, step character by character right, looking for the best fit.853 var bestEquality1 = equality1;854 var bestEdit = edit;855 var bestEquality2 = equality2;856 var bestScore = diff_cleanupSemanticScore_(equality1, edit) +857 diff_cleanupSemanticScore_(edit, equality2);858 while (edit.charAt(0) === equality2.charAt(0)) {859 equality1 += edit.charAt(0);860 edit = edit.substring(1) + equality2.charAt(0);861 equality2 = equality2.substring(1);862 var score = diff_cleanupSemanticScore_(equality1, edit) +863 diff_cleanupSemanticScore_(edit, equality2);864 // The >= encourages trailing rather than leading whitespace on edits.865 if (score >= bestScore) {866 bestScore = score;867 bestEquality1 = equality1;868 bestEdit = edit;869 bestEquality2 = equality2;870 }871 }872 if (diffs[pointer - 1][1] != bestEquality1) {873 // We have an improvement, save it back to the diff.874 if (bestEquality1) {875 diffs[pointer - 1][1] = bestEquality1;876 } else {877 diffs.splice(pointer - 1, 1);878 pointer--;879 }880 diffs[pointer][1] = bestEdit;881 if (bestEquality2) {882 diffs[pointer + 1][1] = bestEquality2;883 } else {884 diffs.splice(pointer + 1, 1);885 pointer--;886 }887 }888 }889 pointer++;890 }891};892// Define some regex patterns for matching boundaries.893diff_match_patch.nonAlphaNumericRegex_ = /[^a-zA-Z0-9]/;894diff_match_patch.whitespaceRegex_ = /\s/;895diff_match_patch.linebreakRegex_ = /[\r\n]/;896diff_match_patch.blanklineEndRegex_ = /\n\r?\n$/;897diff_match_patch.blanklineStartRegex_ = /^\r?\n\r?\n/;898/**899 * Reduce the number of edits by eliminating operationally trivial equalities.900 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.901 */902diff_match_patch.prototype.diff_cleanupEfficiency = function(diffs) {903 var changes = false;904 var equalities = []; // Stack of indices where equalities are found.905 var equalitiesLength = 0; // Keeping our own length var is faster in JS.906 /** @type {?string} */907 var lastequality = null;908 // Always equal to diffs[equalities[equalitiesLength - 1]][1]909 var pointer = 0; // Index of current position.910 // Is there an insertion operation before the last equality.911 var pre_ins = false;912 // Is there a deletion operation before the last equality.913 var pre_del = false;914 // Is there an insertion operation after the last equality.915 var post_ins = false;916 // Is there a deletion operation after the last equality.917 var post_del = false;918 while (pointer < diffs.length) {919 if (diffs[pointer][0] == DIFF_EQUAL) { // Equality found.920 if (diffs[pointer][1].length < this.Diff_EditCost &&921 (post_ins || post_del)) {922 // Candidate found.923 equalities[equalitiesLength++] = pointer;924 pre_ins = post_ins;925 pre_del = post_del;926 lastequality = diffs[pointer][1];927 } else {928 // Not a candidate, and can never become one.929 equalitiesLength = 0;930 lastequality = null;931 }932 post_ins = post_del = false;933 } else { // An insertion or deletion.934 if (diffs[pointer][0] == DIFF_DELETE) {935 post_del = true;936 } else {937 post_ins = true;938 }939 /*940 * Five types to be split:941 * <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>942 * <ins>A</ins>X<ins>C</ins><del>D</del>943 * <ins>A</ins><del>B</del>X<ins>C</ins>944 * <ins>A</del>X<ins>C</ins><del>D</del>945 * <ins>A</ins><del>B</del>X<del>C</del>946 */947 if (lastequality && ((pre_ins && pre_del && post_ins && post_del) ||948 ((lastequality.length < this.Diff_EditCost / 2) &&949 (pre_ins + pre_del + post_ins + post_del) == 3))) {950 // Duplicate record.951 diffs.splice(equalities[equalitiesLength - 1], 0,952 [DIFF_DELETE, lastequality]);953 // Change second copy to insert.954 diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;955 equalitiesLength--; // Throw away the equality we just deleted;956 lastequality = null;957 if (pre_ins && pre_del) {958 // No changes made which could affect previous entry, keep going.959 post_ins = post_del = true;960 equalitiesLength = 0;961 } else {962 equalitiesLength--; // Throw away the previous equality.963 pointer = equalitiesLength > 0 ?964 equalities[equalitiesLength - 1] : -1;965 post_ins = post_del = false;966 }967 changes = true;968 }969 }970 pointer++;971 }972 if (changes) {973 this.diff_cleanupMerge(diffs);974 }975};976/**977 * Reorder and merge like edit sections. Merge equalities.978 * Any edit section can move as long as it doesn't cross an equality.979 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.980 */981diff_match_patch.prototype.diff_cleanupMerge = function(diffs) {982 diffs.push([DIFF_EQUAL, '']); // Add a dummy entry at the end.983 var pointer = 0;984 var count_delete = 0;985 var count_insert = 0;986 var text_delete = '';987 var text_insert = '';988 var commonlength;989 while (pointer < diffs.length) {990 switch (diffs[pointer][0]) {991 case DIFF_INSERT:992 count_insert++;993 text_insert += diffs[pointer][1];994 pointer++;995 break;996 case DIFF_DELETE:997 count_delete++;998 text_delete += diffs[pointer][1];999 pointer++;1000 break;1001 case DIFF_EQUAL:1002 // Upon reaching an equality, check for prior redundancies.1003 if (count_delete + count_insert > 1) {1004 if (count_delete !== 0 && count_insert !== 0) {1005 // Factor out any common prefixies.1006 commonlength = this.diff_commonPrefix(text_insert, text_delete);1007 if (commonlength !== 0) {1008 if ((pointer - count_delete - count_insert) > 0 &&1009 diffs[pointer - count_delete - count_insert - 1][0] ==1010 DIFF_EQUAL) {1011 diffs[pointer - count_delete - count_insert - 1][1] +=1012 text_insert.substring(0, commonlength);1013 } else {1014 diffs.splice(0, 0, [DIFF_EQUAL,1015 text_insert.substring(0, commonlength)]);1016 pointer++;1017 }1018 text_insert = text_insert.substring(commonlength);1019 text_delete = text_delete.substring(commonlength);1020 }1021 // Factor out any common suffixies.1022 commonlength = this.diff_commonSuffix(text_insert, text_delete);1023 if (commonlength !== 0) {1024 diffs[pointer][1] = text_insert.substring(text_insert.length -1025 commonlength) + diffs[pointer][1];1026 text_insert = text_insert.substring(0, text_insert.length -1027 commonlength);1028 text_delete = text_delete.substring(0, text_delete.length -1029 commonlength);1030 }1031 }1032 // Delete the offending records and add the merged ones.1033 if (count_delete === 0) {1034 diffs.splice(pointer - count_insert,1035 count_delete + count_insert, [DIFF_INSERT, text_insert]);1036 } else if (count_insert === 0) {1037 diffs.splice(pointer - count_delete,1038 count_delete + count_insert, [DIFF_DELETE, text_delete]);1039 } else {1040 diffs.splice(pointer - count_delete - count_insert,1041 count_delete + count_insert, [DIFF_DELETE, text_delete],1042 [DIFF_INSERT, text_insert]);1043 }1044 pointer = pointer - count_delete - count_insert +1045 (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;1046 } else if (pointer !== 0 && diffs[pointer - 1][0] == DIFF_EQUAL) {1047 // Merge this equality with the previous one.1048 diffs[pointer - 1][1] += diffs[pointer][1];1049 diffs.splice(pointer, 1);1050 } else {1051 pointer++;1052 }1053 count_insert = 0;1054 count_delete = 0;1055 text_delete = '';1056 text_insert = '';1057 break;1058 }1059 }1060 if (diffs[diffs.length - 1][1] === '') {1061 diffs.pop(); // Remove the dummy entry at the end.1062 }1063 // Second pass: look for single edits surrounded on both sides by equalities1064 // which can be shifted sideways to eliminate an equality.1065 // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC1066 var changes = false;1067 pointer = 1;1068 // Intentionally ignore the first and last element (don't need checking).1069 while (pointer < diffs.length - 1) {1070 if (diffs[pointer - 1][0] == DIFF_EQUAL &&1071 diffs[pointer + 1][0] == DIFF_EQUAL) {1072 // This is a single edit surrounded by equalities.1073 if (diffs[pointer][1].substring(diffs[pointer][1].length -1074 diffs[pointer - 1][1].length) == diffs[pointer - 1][1]) {1075 // Shift the edit over the previous equality.1076 diffs[pointer][1] = diffs[pointer - 1][1] +1077 diffs[pointer][1].substring(0, diffs[pointer][1].length -1078 diffs[pointer - 1][1].length);1079 diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1];1080 diffs.splice(pointer - 1, 1);1081 changes = true;1082 } else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) ==1083 diffs[pointer + 1][1]) {1084 // Shift the edit over the next equality.1085 diffs[pointer - 1][1] += diffs[pointer + 1][1];1086 diffs[pointer][1] =1087 diffs[pointer][1].substring(diffs[pointer + 1][1].length) +1088 diffs[pointer + 1][1];1089 diffs.splice(pointer + 1, 1);1090 changes = true;1091 }1092 }1093 pointer++;1094 }1095 // If shifts were made, the diff needs reordering and another shift sweep.1096 if (changes) {1097 this.diff_cleanupMerge(diffs);1098 }1099};1100/**1101 * loc is a location in text1, compute and return the equivalent location in1102 * text2.1103 * e.g. 'The cat' vs 'The big cat', 1->1, 5->81104 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1105 * @param {number} loc Location within text1.1106 * @return {number} Location within text2.1107 */1108diff_match_patch.prototype.diff_xIndex = function(diffs, loc) {1109 var chars1 = 0;1110 var chars2 = 0;1111 var last_chars1 = 0;1112 var last_chars2 = 0;1113 var x;1114 for (x = 0; x < diffs.length; x++) {1115 if (diffs[x][0] !== DIFF_INSERT) { // Equality or deletion.1116 chars1 += diffs[x][1].length;1117 }1118 if (diffs[x][0] !== DIFF_DELETE) { // Equality or insertion.1119 chars2 += diffs[x][1].length;1120 }1121 if (chars1 > loc) { // Overshot the location.1122 break;1123 }1124 last_chars1 = chars1;1125 last_chars2 = chars2;1126 }1127 // Was the location was deleted?1128 if (diffs.length != x && diffs[x][0] === DIFF_DELETE) {1129 return last_chars2;1130 }1131 // Add the remaining character length.1132 return last_chars2 + (loc - last_chars1);1133};1134/**1135 * Convert a diff array into a pretty HTML report.1136 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1137 * @return {string} HTML representation.1138 */1139diff_match_patch.prototype.diff_prettyHtml = function(diffs) {1140 var html = [];1141 var pattern_amp = /&/g;1142 var pattern_lt = /</g;1143 var pattern_gt = />/g;1144 var pattern_para = /\n/g;1145 for (var x = 0; x < diffs.length; x++) {1146 var op = diffs[x][0]; // Operation (insert, delete, equal)1147 var data = diffs[x][1]; // Text of change.1148 var text = data.replace(pattern_amp, '&amp;').replace(pattern_lt, '&lt;')1149 .replace(pattern_gt, '&gt;').replace(pattern_para, '&para;<br>');1150 switch (op) {1151 case DIFF_INSERT:1152 html[x] = '<ins style="background:#e6ffe6;">' + text + '</ins>';1153 break;1154 case DIFF_DELETE:1155 html[x] = '<del style="background:#ffe6e6;">' + text + '</del>';1156 break;1157 case DIFF_EQUAL:1158 html[x] = '<span>' + text + '</span>';1159 break;1160 }1161 }1162 return html.join('');1163};1164/**1165 * Compute and return the source text (all equalities and deletions).1166 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1167 * @return {string} Source text.1168 */1169diff_match_patch.prototype.diff_text1 = function(diffs) {1170 var text = [];1171 for (var x = 0; x < diffs.length; x++) {1172 if (diffs[x][0] !== DIFF_INSERT) {1173 text[x] = diffs[x][1];1174 }1175 }1176 return text.join('');1177};1178/**1179 * Compute and return the destination text (all equalities and insertions).1180 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1181 * @return {string} Destination text.1182 */1183diff_match_patch.prototype.diff_text2 = function(diffs) {1184 var text = [];1185 for (var x = 0; x < diffs.length; x++) {1186 if (diffs[x][0] !== DIFF_DELETE) {1187 text[x] = diffs[x][1];1188 }1189 }1190 return text.join('');1191};1192/**1193 * Compute the Levenshtein distance; the number of inserted, deleted or1194 * substituted characters.1195 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1196 * @return {number} Number of changes.1197 */1198diff_match_patch.prototype.diff_levenshtein = function(diffs) {1199 var levenshtein = 0;1200 var insertions = 0;1201 var deletions = 0;1202 for (var x = 0; x < diffs.length; x++) {1203 var op = diffs[x][0];1204 var data = diffs[x][1];1205 switch (op) {1206 case DIFF_INSERT:1207 insertions += data.length;1208 break;1209 case DIFF_DELETE:1210 deletions += data.length;1211 break;1212 case DIFF_EQUAL:1213 // A deletion and an insertion is one substitution.1214 levenshtein += Math.max(insertions, deletions);1215 insertions = 0;1216 deletions = 0;1217 break;1218 }1219 }1220 levenshtein += Math.max(insertions, deletions);1221 return levenshtein;1222};1223/**1224 * Crush the diff into an encoded string which describes the operations1225 * required to transform text1 into text2.1226 * E.g. =3\t-2\t+ing -> Keep 3 chars, delete 2 chars, insert 'ing'.1227 * Operations are tab-separated. Inserted text is escaped using %xx notation.1228 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.1229 * @return {string} Delta text.1230 */1231diff_match_patch.prototype.diff_toDelta = function(diffs) {1232 var text = [];1233 for (var x = 0; x < diffs.length; x++) {1234 switch (diffs[x][0]) {1235 case DIFF_INSERT:1236 text[x] = '+' + encodeURI(diffs[x][1]);1237 break;1238 case DIFF_DELETE:1239 text[x] = '-' + diffs[x][1].length;1240 break;1241 case DIFF_EQUAL:1242 text[x] = '=' + diffs[x][1].length;1243 break;1244 }1245 }1246 return text.join('\t').replace(/%20/g, ' ');1247};1248/**1249 * Given the original text1, and an encoded string which describes the1250 * operations required to transform text1 into text2, compute the full diff.1251 * @param {string} text1 Source string for the diff.1252 * @param {string} delta Delta text.1253 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.1254 * @throws {!Error} If invalid input.1255 */1256diff_match_patch.prototype.diff_fromDelta = function(text1, delta) {1257 var diffs = [];1258 var diffsLength = 0; // Keeping our own length var is faster in JS.1259 var pointer = 0; // Cursor in text11260 var tokens = delta.split(/\t/g);1261 for (var x = 0; x < tokens.length; x++) {1262 // Each token begins with a one character parameter which specifies the1263 // operation of this token (delete, insert, equality).1264 var param = tokens[x].substring(1);1265 switch (tokens[x].charAt(0)) {1266 case '+':1267 try {1268 diffs[diffsLength++] = [DIFF_INSERT, decodeURI(param)];1269 } catch (ex) {1270 // Malformed URI sequence.1271 throw new Error('Illegal escape in diff_fromDelta: ' + param);1272 }1273 break;1274 case '-':1275 // Fall through.1276 case '=':1277 var n = parseInt(param, 10);1278 if (isNaN(n) || n < 0) {1279 throw new Error('Invalid number in diff_fromDelta: ' + param);1280 }1281 var text = text1.substring(pointer, pointer += n);1282 if (tokens[x].charAt(0) == '=') {1283 diffs[diffsLength++] = [DIFF_EQUAL, text];1284 } else {1285 diffs[diffsLength++] = [DIFF_DELETE, text];1286 }1287 break;1288 default:1289 // Blank tokens are ok (from a trailing \t).1290 // Anything else is an error.1291 if (tokens[x]) {1292 throw new Error('Invalid diff operation in diff_fromDelta: ' +1293 tokens[x]);1294 }1295 }1296 }1297 if (pointer != text1.length) {1298 throw new Error('Delta length (' + pointer +1299 ') does not equal source text length (' + text1.length + ').');1300 }1301 return diffs;1302};1303// MATCH FUNCTIONS1304/**1305 * Locate the best instance of 'pattern' in 'text' near 'loc'.1306 * @param {string} text The text to search.1307 * @param {string} pattern The pattern to search for.1308 * @param {number} loc The location to search around.1309 * @return {number} Best match index or -1.1310 */1311diff_match_patch.prototype.match_main = function(text, pattern, loc) {1312 // Check for null inputs.1313 if (text == null || pattern == null || loc == null) {1314 throw new Error('Null input. (match_main)');1315 }1316 loc = Math.max(0, Math.min(loc, text.length));1317 if (text == pattern) {1318 // Shortcut (potentially not guaranteed by the algorithm)1319 return 0;1320 } else if (!text.length) {1321 // Nothing to match.1322 return -1;1323 } else if (text.substring(loc, loc + pattern.length) == pattern) {1324 // Perfect match at the perfect spot! (Includes case of null pattern)1325 return loc;1326 } else {1327 // Do a fuzzy compare.1328 return this.match_bitap_(text, pattern, loc);1329 }1330};1331/**1332 * Locate the best instance of 'pattern' in 'text' near 'loc' using the1333 * Bitap algorithm.1334 * @param {string} text The text to search.1335 * @param {string} pattern The pattern to search for.1336 * @param {number} loc The location to search around.1337 * @return {number} Best match index or -1.1338 * @private1339 */1340diff_match_patch.prototype.match_bitap_ = function(text, pattern, loc) {1341 if (pattern.length > this.Match_MaxBits) {1342 throw new Error('Pattern too long for this browser.');1343 }1344 // Initialise the alphabet.1345 var s = this.match_alphabet_(pattern);1346 var dmp = this; // 'this' becomes 'window' in a closure.1347 /**1348 * Compute and return the score for a match with e errors and x location.1349 * Accesses loc and pattern through being a closure.1350 * @param {number} e Number of errors in match.1351 * @param {number} x Location of match.1352 * @return {number} Overall score for match (0.0 = good, 1.0 = bad).1353 * @private1354 */1355 function match_bitapScore_(e, x) {1356 var accuracy = e / pattern.length;1357 var proximity = Math.abs(loc - x);1358 if (!dmp.Match_Distance) {1359 // Dodge divide by zero error.1360 return proximity ? 1.0 : accuracy;1361 }1362 return accuracy + (proximity / dmp.Match_Distance);1363 }1364 // Highest score beyond which we give up.1365 var score_threshold = this.Match_Threshold;1366 // Is there a nearby exact match? (speedup)1367 var best_loc = text.indexOf(pattern, loc);1368 if (best_loc != -1) {1369 score_threshold = Math.min(match_bitapScore_(0, best_loc), score_threshold);1370 // What about in the other direction? (speedup)1371 best_loc = text.lastIndexOf(pattern, loc + pattern.length);1372 if (best_loc != -1) {1373 score_threshold =1374 Math.min(match_bitapScore_(0, best_loc), score_threshold);1375 }1376 }1377 // Initialise the bit arrays.1378 var matchmask = 1 << (pattern.length - 1);1379 best_loc = -1;1380 var bin_min, bin_mid;1381 var bin_max = pattern.length + text.length;1382 var last_rd;1383 for (var d = 0; d < pattern.length; d++) {1384 // Scan for the best match; each iteration allows for one more error.1385 // Run a binary search to determine how far from 'loc' we can stray at this1386 // error level.1387 bin_min = 0;1388 bin_mid = bin_max;1389 while (bin_min < bin_mid) {1390 if (match_bitapScore_(d, loc + bin_mid) <= score_threshold) {1391 bin_min = bin_mid;1392 } else {1393 bin_max = bin_mid;1394 }1395 bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min);1396 }1397 // Use the result from this iteration as the maximum for the next.1398 bin_max = bin_mid;1399 var start = Math.max(1, loc - bin_mid + 1);1400 var finish = Math.min(loc + bin_mid, text.length) + pattern.length;1401 var rd = Array(finish + 2);1402 rd[finish + 1] = (1 << d) - 1;1403 for (var j = finish; j >= start; j--) {1404 // The alphabet (s) is a sparse hash, so the following line generates1405 // warnings.1406 var charMatch = s[text.charAt(j - 1)];1407 if (d === 0) { // First pass: exact match.1408 rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;1409 } else { // Subsequent passes: fuzzy match.1410 rd[j] = (((rd[j + 1] << 1) | 1) & charMatch) |1411 (((last_rd[j + 1] | last_rd[j]) << 1) | 1) |1412 last_rd[j + 1];1413 }1414 if (rd[j] & matchmask) {1415 var score = match_bitapScore_(d, j - 1);1416 // This match will almost certainly be better than any existing match.1417 // But check anyway.1418 if (score <= score_threshold) {1419 // Told you so.1420 score_threshold = score;1421 best_loc = j - 1;1422 if (best_loc > loc) {1423 // When passing loc, don't exceed our current distance from loc.1424 start = Math.max(1, 2 * loc - best_loc);1425 } else {1426 // Already passed loc, downhill from here on in.1427 break;1428 }1429 }1430 }1431 }1432 // No hope for a (better) match at greater error levels.1433 if (match_bitapScore_(d + 1, loc) > score_threshold) {1434 break;1435 }1436 last_rd = rd;1437 }1438 return best_loc;1439};1440/**1441 * Initialise the alphabet for the Bitap algorithm.1442 * @param {string} pattern The text to encode.1443 * @return {!Object} Hash of character locations.1444 * @private1445 */1446diff_match_patch.prototype.match_alphabet_ = function(pattern) {1447 var s = {};1448 for (var i = 0; i < pattern.length; i++) {1449 s[pattern.charAt(i)] = 0;1450 }1451 for (var i = 0; i < pattern.length; i++) {1452 s[pattern.charAt(i)] |= 1 << (pattern.length - i - 1);1453 }1454 return s;1455};1456// PATCH FUNCTIONS1457/**1458 * Increase the context until it is unique,1459 * but don't let the pattern expand beyond Match_MaxBits.1460 * @param {!diff_match_patch.patch_obj} patch The patch to grow.1461 * @param {string} text Source text.1462 * @private1463 */1464diff_match_patch.prototype.patch_addContext_ = function(patch, text) {1465 if (text.length == 0) {1466 return;1467 }1468 var pattern = text.substring(patch.start2, patch.start2 + patch.length1);1469 var padding = 0;1470 // Look for the first and last matches of pattern in text. If two different1471 // matches are found, increase the pattern length.1472 while (text.indexOf(pattern) != text.lastIndexOf(pattern) &&1473 pattern.length < this.Match_MaxBits - this.Patch_Margin -1474 this.Patch_Margin) {1475 padding += this.Patch_Margin;1476 pattern = text.substring(patch.start2 - padding,1477 patch.start2 + patch.length1 + padding);1478 }1479 // Add one chunk for good luck.1480 padding += this.Patch_Margin;1481 // Add the prefix.1482 var prefix = text.substring(patch.start2 - padding, patch.start2);1483 if (prefix) {1484 patch.diffs.unshift([DIFF_EQUAL, prefix]);1485 }1486 // Add the suffix.1487 var suffix = text.substring(patch.start2 + patch.length1,1488 patch.start2 + patch.length1 + padding);1489 if (suffix) {1490 patch.diffs.push([DIFF_EQUAL, suffix]);1491 }1492 // Roll back the start points.1493 patch.start1 -= prefix.length;1494 patch.start2 -= prefix.length;1495 // Extend the lengths.1496 patch.length1 += prefix.length + suffix.length;1497 patch.length2 += prefix.length + suffix.length;1498};1499/**1500 * Compute a list of patches to turn text1 into text2.1501 * Use diffs if provided, otherwise compute it ourselves.1502 * There are four ways to call this function, depending on what data is1503 * available to the caller:1504 * Method 1:1505 * a = text1, b = text21506 * Method 2:1507 * a = diffs1508 * Method 3 (optimal):1509 * a = text1, b = diffs1510 * Method 4 (deprecated, use method 3):1511 * a = text1, b = text2, c = diffs1512 *1513 * @param {string|!Array.<!diff_match_patch.Diff>} a text1 (methods 1,3,4) or1514 * Array of diff tuples for text1 to text2 (method 2).1515 * @param {string|!Array.<!diff_match_patch.Diff>} opt_b text2 (methods 1,4) or1516 * Array of diff tuples for text1 to text2 (method 3) or undefined (method 2).1517 * @param {string|!Array.<!diff_match_patch.Diff>} opt_c Array of diff tuples1518 * for text1 to text2 (method 4) or undefined (methods 1,2,3).1519 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1520 */1521diff_match_patch.prototype.patch_make = function(a, opt_b, opt_c) {1522 var text1, diffs;1523 if (typeof a == 'string' && typeof opt_b == 'string' &&1524 typeof opt_c == 'undefined') {1525 // Method 1: text1, text21526 // Compute diffs from text1 and text2.1527 text1 = /** @type {string} */(a);1528 diffs = this.diff_main(text1, /** @type {string} */(opt_b), true);1529 if (diffs.length > 2) {1530 this.diff_cleanupSemantic(diffs);1531 this.diff_cleanupEfficiency(diffs);1532 }1533 } else if (a && typeof a == 'object' && typeof opt_b == 'undefined' &&1534 typeof opt_c == 'undefined') {1535 // Method 2: diffs1536 // Compute text1 from diffs.1537 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(a);1538 text1 = this.diff_text1(diffs);1539 } else if (typeof a == 'string' && opt_b && typeof opt_b == 'object' &&1540 typeof opt_c == 'undefined') {1541 // Method 3: text1, diffs1542 text1 = /** @type {string} */(a);1543 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(opt_b);1544 } else if (typeof a == 'string' && typeof opt_b == 'string' &&1545 opt_c && typeof opt_c == 'object') {1546 // Method 4: text1, text2, diffs1547 // text2 is not used.1548 text1 = /** @type {string} */(a);1549 diffs = /** @type {!Array.<!diff_match_patch.Diff>} */(opt_c);1550 } else {1551 throw new Error('Unknown call format to patch_make.');1552 }1553 if (diffs.length === 0) {1554 return []; // Get rid of the null case.1555 }1556 var patches = [];1557 var patch = new diff_match_patch.patch_obj();1558 var patchDiffLength = 0; // Keeping our own length var is faster in JS.1559 var char_count1 = 0; // Number of characters into the text1 string.1560 var char_count2 = 0; // Number of characters into the text2 string.1561 // Start with text1 (prepatch_text) and apply the diffs until we arrive at1562 // text2 (postpatch_text). We recreate the patches one by one to determine1563 // context info.1564 var prepatch_text = text1;1565 var postpatch_text = text1;1566 for (var x = 0; x < diffs.length; x++) {1567 var diff_type = diffs[x][0];1568 var diff_text = diffs[x][1];1569 if (!patchDiffLength && diff_type !== DIFF_EQUAL) {1570 // A new patch starts here.1571 patch.start1 = char_count1;1572 patch.start2 = char_count2;1573 }1574 switch (diff_type) {1575 case DIFF_INSERT:1576 patch.diffs[patchDiffLength++] = diffs[x];1577 patch.length2 += diff_text.length;1578 postpatch_text = postpatch_text.substring(0, char_count2) + diff_text +1579 postpatch_text.substring(char_count2);1580 break;1581 case DIFF_DELETE:1582 patch.length1 += diff_text.length;1583 patch.diffs[patchDiffLength++] = diffs[x];1584 postpatch_text = postpatch_text.substring(0, char_count2) +1585 postpatch_text.substring(char_count2 +1586 diff_text.length);1587 break;1588 case DIFF_EQUAL:1589 if (diff_text.length <= 2 * this.Patch_Margin &&1590 patchDiffLength && diffs.length != x + 1) {1591 // Small equality inside a patch.1592 patch.diffs[patchDiffLength++] = diffs[x];1593 patch.length1 += diff_text.length;1594 patch.length2 += diff_text.length;1595 } else if (diff_text.length >= 2 * this.Patch_Margin) {1596 // Time for a new patch.1597 if (patchDiffLength) {1598 this.patch_addContext_(patch, prepatch_text);1599 patches.push(patch);1600 patch = new diff_match_patch.patch_obj();1601 patchDiffLength = 0;1602 // Unlike Unidiff, our patch lists have a rolling context.1603 // http://code.google.com/p/google-diff-match-patch/wiki/Unidiff1604 // Update prepatch text & pos to reflect the application of the1605 // just completed patch.1606 prepatch_text = postpatch_text;1607 char_count1 = char_count2;1608 }1609 }1610 break;1611 }1612 // Update the current character count.1613 if (diff_type !== DIFF_INSERT) {1614 char_count1 += diff_text.length;1615 }1616 if (diff_type !== DIFF_DELETE) {1617 char_count2 += diff_text.length;1618 }1619 }1620 // Pick up the leftover patch if not empty.1621 if (patchDiffLength) {1622 this.patch_addContext_(patch, prepatch_text);1623 patches.push(patch);1624 }1625 return patches;1626};1627/**1628 * Given an array of patches, return another array that is identical.1629 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1630 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1631 */1632diff_match_patch.prototype.patch_deepCopy = function(patches) {1633 // Making deep copies is hard in JavaScript.1634 var patchesCopy = [];1635 for (var x = 0; x < patches.length; x++) {1636 var patch = patches[x];1637 var patchCopy = new diff_match_patch.patch_obj();1638 patchCopy.diffs = [];1639 for (var y = 0; y < patch.diffs.length; y++) {1640 patchCopy.diffs[y] = patch.diffs[y].slice();1641 }1642 patchCopy.start1 = patch.start1;1643 patchCopy.start2 = patch.start2;1644 patchCopy.length1 = patch.length1;1645 patchCopy.length2 = patch.length2;1646 patchesCopy[x] = patchCopy;1647 }1648 return patchesCopy;1649};1650/**1651 * Merge a set of patches onto the text. Return a patched text, as well1652 * as a list of true/false values indicating which patches were applied.1653 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1654 * @param {string} text Old text.1655 * @return {!Array.<string|!Array.<boolean>>} Two element Array, containing the1656 * new text and an array of boolean values.1657 */1658diff_match_patch.prototype.patch_apply = function(patches, text) {1659 if (patches.length == 0) {1660 return [text, []];1661 }1662 // Deep copy the patches so that no changes are made to originals.1663 patches = this.patch_deepCopy(patches);1664 var nullPadding = this.patch_addPadding(patches);1665 text = nullPadding + text + nullPadding;1666 this.patch_splitMax(patches);1667 // delta keeps track of the offset between the expected and actual location1668 // of the previous patch. If there are patches expected at positions 10 and1669 // 20, but the first patch was found at 12, delta is 2 and the second patch1670 // has an effective expected position of 22.1671 var delta = 0;1672 var results = [];1673 for (var x = 0; x < patches.length; x++) {1674 var expected_loc = patches[x].start2 + delta;1675 var text1 = this.diff_text1(patches[x].diffs);1676 var start_loc;1677 var end_loc = -1;1678 if (text1.length > this.Match_MaxBits) {1679 // patch_splitMax will only provide an oversized pattern in the case of1680 // a monster delete.1681 start_loc = this.match_main(text, text1.substring(0, this.Match_MaxBits),1682 expected_loc);1683 if (start_loc != -1) {1684 end_loc = this.match_main(text,1685 text1.substring(text1.length - this.Match_MaxBits),1686 expected_loc + text1.length - this.Match_MaxBits);1687 if (end_loc == -1 || start_loc >= end_loc) {1688 // Can't find valid trailing context. Drop this patch.1689 start_loc = -1;1690 }1691 }1692 } else {1693 start_loc = this.match_main(text, text1, expected_loc);1694 }1695 if (start_loc == -1) {1696 // No match found. :(1697 results[x] = false;1698 // Subtract the delta for this failed patch from subsequent patches.1699 delta -= patches[x].length2 - patches[x].length1;1700 } else {1701 // Found a match. :)1702 results[x] = true;1703 delta = start_loc - expected_loc;1704 var text2;1705 if (end_loc == -1) {1706 text2 = text.substring(start_loc, start_loc + text1.length);1707 } else {1708 text2 = text.substring(start_loc, end_loc + this.Match_MaxBits);1709 }1710 if (text1 == text2) {1711 // Perfect match, just shove the replacement text in.1712 text = text.substring(0, start_loc) +1713 this.diff_text2(patches[x].diffs) +1714 text.substring(start_loc + text1.length);1715 } else {1716 // Imperfect match. Run a diff to get a framework of equivalent1717 // indices.1718 var diffs = this.diff_main(text1, text2, false);1719 if (text1.length > this.Match_MaxBits &&1720 this.diff_levenshtein(diffs) / text1.length >1721 this.Patch_DeleteThreshold) {1722 // The end points match, but the content is unacceptably bad.1723 results[x] = false;1724 } else {1725 this.diff_cleanupSemanticLossless(diffs);1726 var index1 = 0;1727 var index2;1728 for (var y = 0; y < patches[x].diffs.length; y++) {1729 var mod = patches[x].diffs[y];1730 if (mod[0] !== DIFF_EQUAL) {1731