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 index2 = this.diff_xIndex(diffs, index1);1732 }1733 if (mod[0] === DIFF_INSERT) { // Insertion1734 text = text.substring(0, start_loc + index2) + mod[1] +1735 text.substring(start_loc + index2);1736 } else if (mod[0] === DIFF_DELETE) { // Deletion1737 text = text.substring(0, start_loc + index2) +1738 text.substring(start_loc + this.diff_xIndex(diffs,1739 index1 + mod[1].length));1740 }1741 if (mod[0] !== DIFF_DELETE) {1742 index1 += mod[1].length;1743 }1744 }1745 }1746 }1747 }1748 }1749 // Strip the padding off.1750 text = text.substring(nullPadding.length, text.length - nullPadding.length);1751 return [text, results];1752};1753/**1754 * Add some padding on text start and end so that edges can match something.1755 * Intended to be called only from within patch_apply.1756 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1757 * @return {string} The padding string added to each side.1758 */1759diff_match_patch.prototype.patch_addPadding = function(patches) {1760 var paddingLength = this.Patch_Margin;1761 var nullPadding = '';1762 for (var x = 1; x <= paddingLength; x++) {1763 nullPadding += String.fromCharCode(x);1764 }1765 // Bump all the patches forward.1766 for (var x = 0; x < patches.length; x++) {1767 patches[x].start1 += paddingLength;1768 patches[x].start2 += paddingLength;1769 }1770 // Add some padding on start of first diff.1771 var patch = patches[0];1772 var diffs = patch.diffs;1773 if (diffs.length == 0 || diffs[0][0] != DIFF_EQUAL) {1774 // Add nullPadding equality.1775 diffs.unshift([DIFF_EQUAL, nullPadding]);1776 patch.start1 -= paddingLength; // Should be 0.1777 patch.start2 -= paddingLength; // Should be 0.1778 patch.length1 += paddingLength;1779 patch.length2 += paddingLength;1780 } else if (paddingLength > diffs[0][1].length) {1781 // Grow first equality.1782 var extraLength = paddingLength - diffs[0][1].length;1783 diffs[0][1] = nullPadding.substring(diffs[0][1].length) + diffs[0][1];1784 patch.start1 -= extraLength;1785 patch.start2 -= extraLength;1786 patch.length1 += extraLength;1787 patch.length2 += extraLength;1788 }1789 // Add some padding on end of last diff.1790 patch = patches[patches.length - 1];1791 diffs = patch.diffs;1792 if (diffs.length == 0 || diffs[diffs.length - 1][0] != DIFF_EQUAL) {1793 // Add nullPadding equality.1794 diffs.push([DIFF_EQUAL, nullPadding]);1795 patch.length1 += paddingLength;1796 patch.length2 += paddingLength;1797 } else if (paddingLength > diffs[diffs.length - 1][1].length) {1798 // Grow last equality.1799 var extraLength = paddingLength - diffs[diffs.length - 1][1].length;1800 diffs[diffs.length - 1][1] += nullPadding.substring(0, extraLength);1801 patch.length1 += extraLength;1802 patch.length2 += extraLength;1803 }1804 return nullPadding;1805};1806/**1807 * Look through the patches and break up any which are longer than the maximum1808 * limit of the match algorithm.1809 * Intended to be called only from within patch_apply.1810 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1811 */1812diff_match_patch.prototype.patch_splitMax = function(patches) {1813 var patch_size = this.Match_MaxBits;1814 for (var x = 0; x < patches.length; x++) {1815 if (patches[x].length1 <= patch_size) {1816 continue;1817 }1818 var bigpatch = patches[x];1819 // Remove the big old patch.1820 patches.splice(x--, 1);1821 var start1 = bigpatch.start1;1822 var start2 = bigpatch.start2;1823 var precontext = '';1824 while (bigpatch.diffs.length !== 0) {1825 // Create one of several smaller patches.1826 var patch = new diff_match_patch.patch_obj();1827 var empty = true;1828 patch.start1 = start1 - precontext.length;1829 patch.start2 = start2 - precontext.length;1830 if (precontext !== '') {1831 patch.length1 = patch.length2 = precontext.length;1832 patch.diffs.push([DIFF_EQUAL, precontext]);1833 }1834 while (bigpatch.diffs.length !== 0 &&1835 patch.length1 < patch_size - this.Patch_Margin) {1836 var diff_type = bigpatch.diffs[0][0];1837 var diff_text = bigpatch.diffs[0][1];1838 if (diff_type === DIFF_INSERT) {1839 // Insertions are harmless.1840 patch.length2 += diff_text.length;1841 start2 += diff_text.length;1842 patch.diffs.push(bigpatch.diffs.shift());1843 empty = false;1844 } else if (diff_type === DIFF_DELETE && patch.diffs.length == 1 &&1845 patch.diffs[0][0] == DIFF_EQUAL &&1846 diff_text.length > 2 * patch_size) {1847 // This is a large deletion. Let it pass in one chunk.1848 patch.length1 += diff_text.length;1849 start1 += diff_text.length;1850 empty = false;1851 patch.diffs.push([diff_type, diff_text]);1852 bigpatch.diffs.shift();1853 } else {1854 // Deletion or equality. Only take as much as we can stomach.1855 diff_text = diff_text.substring(0,1856 patch_size - patch.length1 - this.Patch_Margin);1857 patch.length1 += diff_text.length;1858 start1 += diff_text.length;1859 if (diff_type === DIFF_EQUAL) {1860 patch.length2 += diff_text.length;1861 start2 += diff_text.length;1862 } else {1863 empty = false;1864 }1865 patch.diffs.push([diff_type, diff_text]);1866 if (diff_text == bigpatch.diffs[0][1]) {1867 bigpatch.diffs.shift();1868 } else {1869 bigpatch.diffs[0][1] =1870 bigpatch.diffs[0][1].substring(diff_text.length);1871 }1872 }1873 }1874 // Compute the head context for the next patch.1875 precontext = this.diff_text2(patch.diffs);1876 precontext =1877 precontext.substring(precontext.length - this.Patch_Margin);1878 // Append the end context for this patch.1879 var postcontext = this.diff_text1(bigpatch.diffs)1880 .substring(0, this.Patch_Margin);1881 if (postcontext !== '') {1882 patch.length1 += postcontext.length;1883 patch.length2 += postcontext.length;1884 if (patch.diffs.length !== 0 &&1885 patch.diffs[patch.diffs.length - 1][0] === DIFF_EQUAL) {1886 patch.diffs[patch.diffs.length - 1][1] += postcontext;1887 } else {1888 patch.diffs.push([DIFF_EQUAL, postcontext]);1889 }1890 }1891 if (!empty) {1892 patches.splice(++x, 0, patch);1893 }1894 }1895 }1896};1897/**1898 * Take a list of patches and return a textual representation.1899 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.1900 * @return {string} Text representation of patches.1901 */1902diff_match_patch.prototype.patch_toText = function(patches) {1903 var text = [];1904 for (var x = 0; x < patches.length; x++) {1905 text[x] = patches[x];1906 }1907 return text.join('');1908};1909/**1910 * Parse a textual representation of patches and return a list of Patch objects.1911 * @param {string} textline Text representation of patches.1912 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.1913 * @throws {!Error} If invalid input.1914 */1915diff_match_patch.prototype.patch_fromText = function(textline) {1916 var patches = [];1917 if (!textline) {1918 return patches;1919 }1920 var text = textline.split('\n');1921 var textPointer = 0;1922 var patchHeader = /^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/;1923 while (textPointer < text.length) {1924 var m = text[textPointer].match(patchHeader);1925 if (!m) {1926 throw new Error('Invalid patch string: ' + text[textPointer]);1927 }1928 var patch = new diff_match_patch.patch_obj();1929 patches.push(patch);1930 patch.start1 = parseInt(m[1], 10);1931 if (m[2] === '') {1932 patch.start1--;1933 patch.length1 = 1;1934 } else if (m[2] == '0') {1935 patch.length1 = 0;1936 } else {1937 patch.start1--;1938 patch.length1 = parseInt(m[2], 10);1939 }1940 patch.start2 = parseInt(m[3], 10);1941 if (m[4] === '') {1942 patch.start2--;1943 patch.length2 = 1;1944 } else if (m[4] == '0') {1945 patch.length2 = 0;1946 } else {1947 patch.start2--;1948 patch.length2 = parseInt(m[4], 10);1949 }1950 textPointer++;1951 while (textPointer < text.length) {1952 var sign = text[textPointer].charAt(0);1953 try {1954 var line = decodeURI(text[textPointer].substring(1));1955 } catch (ex) {1956 // Malformed URI sequence.1957 throw new Error('Illegal escape in patch_fromText: ' + line);1958 }1959 if (sign == '-') {1960 // Deletion.1961 patch.diffs.push([DIFF_DELETE, line]);1962 } else if (sign == '+') {1963 // Insertion.1964 patch.diffs.push([DIFF_INSERT, line]);1965 } else if (sign == ' ') {1966 // Minor equality.1967 patch.diffs.push([DIFF_EQUAL, line]);1968 } else if (sign == '@') {1969 // Start of next patch.1970 break;1971 } else if (sign === '') {1972 // Blank line? Whatever.1973 } else {1974 // WTF?1975 throw new Error('Invalid patch mode "' + sign + '" in: ' + line);1976 }1977 textPointer++;1978 }1979 }1980 return patches;1981};1982/**1983 * Class representing one patch operation.1984 * @constructor1985 */1986diff_match_patch.patch_obj = function() {1987 /** @type {!Array.<!diff_match_patch.Diff>} */1988 this.diffs = [];1989 /** @type {?number} */1990 this.start1 = null;1991 /** @type {?number} */1992 this.start2 = null;1993 /** @type {number} */1994 this.length1 = 0;1995 /** @type {number} */1996 this.length2 = 0;1997};1998/**1999 * Emmulate GNU diff's format.2000 * Header: @@ -382,8 +481,9 @@2001 * Indicies are printed as 1-based, not 0-based.2002 * @return {string} The GNU diff string.2003 */2004diff_match_patch.patch_obj.prototype.toString = function() {2005 var coords1, coords2;2006 if (this.length1 === 0) {2007 coords1 = this.start1 + ',0';2008 } else if (this.length1 == 1) {2009 coords1 = this.start1 + 1;2010 } else {2011 coords1 = (this.start1 + 1) + ',' + this.length1;2012 }2013 if (this.length2 === 0) {2014 coords2 = this.start2 + ',0';2015 } else if (this.length2 == 1) {2016 coords2 = this.start2 + 1;2017 } else {2018 coords2 = (this.start2 + 1) + ',' + this.length2;2019 }2020 var text = ['@@ -' + coords1 + ' +' + coords2 + ' @@\n'];2021 var op;2022 // Escape the body of the patch with %xx notation.2023 for (var x = 0; x < this.diffs.length; x++) {2024 switch (this.diffs[x][0]) {2025 case DIFF_INSERT:2026 op = '+';2027 break;2028 case DIFF_DELETE:2029 op = '-';2030 break;2031 case DIFF_EQUAL:2032 op = ' ';2033 break;2034 }2035 text[x + 1] = op + encodeURI(this.diffs[x][1]) + '\n';2036 }2037 return text.join('').replace(/%20/g, ' ');2038};2039exports.diff_match_patch = diff_match_patch;2040exports.DIFF_DELETE = DIFF_DELETE;2041exports.DIFF_INSERT = DIFF_INSERT;2042exports.DIFF_EQUAL = DIFF_EQUAL;...

Full Screen

Full Screen

decisionchunking.ts

Source:decisionchunking.ts Github

copy

Full Screen

1import {2 IDiffEntry, DiffCollection, IDiffArrayEntry, opRemoveRange3} from '../diff/diffentries';4import {5 MergeDecision, buildDiffs, pushPath6} from '../merge/decisions';7import {8 hasEntries, valueIn, unique9} from '../common/util';10export11type MergeChunk = {baseStart: number, baseEnd: number, diffs: DiffCollection}12function anyDiffs(diffs: DiffCollection): boolean {13 for (let d of diffs) {14 if (hasEntries(d)) {15 return true;16 }17 }18 return false;19}20function getSectionBoundaries(diffs: IDiffArrayEntry[]) {21 let boundaries: number[] = [];22 for (let e of diffs) {23 let j = e.key;24 let k: number;25 boundaries.push(j);26 if (e.op === 'addrange') {27 // Pass28 } else if (e.op === 'removerange') {29 k = j + e.length;30 boundaries.push(k);31 } else if (e.op === 'patch') {32 k = j + 1;33 boundaries.push(k);34 }35 }36 return boundaries.filter(unique);37}38function splitDiffsOnBoundaries(diffs: IDiffArrayEntry[], boundaries: number[]): IDiffArrayEntry[] {39 let newdiffs: IDiffArrayEntry[] = [];40 if (!Array.isArray(boundaries)) {41 throw new Error();42 }43 // Next relevant boundary index44 let b = 0;45 for (let e of diffs) {46 if (valueIn(e.op, ['addrange', 'patch'])) {47 // Nothing to split48 newdiffs.push(e);49 } else if (e.op === 'removerange') {50 // Skip boundaries smaller than key51 while (boundaries[b] < e.key) {52 b += 1;53 }54 // key should be included in the boundaries55 if (boundaries[b] !== e.key) {56 throw new Error();57 }58 // Add diff entries for each interval between boundaries up to k59 while (b < boundaries.length - 1 && boundaries[b + 1] <= e.key + e.length) {60 newdiffs.push(opRemoveRange(boundaries[b],61 boundaries[b + 1] - boundaries[b]));62 b += 1;63 }64 } else {65 throw new Error('Unhandled diff entry op ' + e.op);66 }67 }68 return newdiffs;69}70/**71 * Make list of chunks on the form (j, k, diffs0, diffs1, ..., diffsN),72 * where `j` and `k` are line numbers in the base, and the `diffsX`73 * entries are subsets from `diffs` that are part of the chunk.74 * Because the diff entries have been split on the union of75 * begin/end boundaries of all diff entries, the keys of76 * diff entries on each side will always match a boundary77 * exactly. The only situation where multiple diff entries78 * on one side matches a boundary is when add/remove or79 * add/patch pairs occur, i.e. when inserting something80 * just before an item that is removed or modified.81 */82function makeChunks(boundaries: number[], diffs: DiffCollection): MergeChunk[] {83 let iDiffs: number[] = Array.apply(null, Array(diffs.length)).map(Number.prototype.valueOf, 0);84 let chunks: MergeChunk[] = [];85 for (let i=0; i < boundaries.length; ++i) {86 // Find span of next chunk87 let j = boundaries[i];88 let k = (i < boundaries.length - 1) ? boundaries[i + 1] : j;89 // Collect diff entries from each side90 // starting at beginning of this chunk91 let subDiffs: DiffCollection = [];92 for (let m=0; m < diffs.length; ++m) {93 let d = diffs[m];94 let dis: IDiffEntry[] = [];95 while (d && iDiffs[m] < d.length && d[iDiffs[m]].key === j) {96 dis.push(d[iDiffs[m]]);97 iDiffs[m] += 1;98 }99 subDiffs.push(dis);100 }101 // Add non-empty chunks102 if (anyDiffs(subDiffs)) {103 let c = {baseStart: j, baseEnd: k, diffs: subDiffs};104 chunks.push(c);105 }106 }107 return chunks;108}109/**110 * Return list of chunks (i, j, d0, d1, ..., dn) where dX are111 * lists of diff entries affecting the range base[i:j].112 *113 * If d0 and d1 are both empty the chunk is not modified.114 *115 * Includes full range 0:len(base).116 *117 * Each diff list contains either 0, 1, or 2 entries,118 * in case of 2 entries the first will be an insert119 * at i (the beginning of the range) and the other a120 * removerange or patch covering the full range i:j.121 */122function makeMergeChunks(base: any[], diffs: DiffCollection): MergeChunk[] {123 // Split diffs on union of diff entry boundaries such that124 // no diff entry overlaps with more than one other entry.125 // Including 0,N makes loop over chunks cleaner.126 let boundaries = [0, base.length];127 for (let d of diffs) {128 if (hasEntries(d)) {129 let newBoundaries = getSectionBoundaries(d as IDiffArrayEntry[]);130 boundaries = boundaries.concat(newBoundaries);131 }132 }133 boundaries = boundaries.filter(unique).sort();134 let splitDiffs: DiffCollection = [];135 for (let d of diffs) {136 if (hasEntries(d)) {137 splitDiffs.push(splitDiffsOnBoundaries(d as IDiffArrayEntry[], boundaries));138 } else {139 splitDiffs.push(d);140 }141 }142 // Make list of chunks on the form (j, k, diffs)143 let chunks = makeChunks(boundaries, splitDiffs);144 return chunks;145}146function splitDecisionByChunks(base: any[], decision: MergeDecision, chunks: MergeChunk[]): MergeDecision[] {147 if (chunks.length < 2) {148 return [decision];149 }150 let out: MergeDecision[] = [];151 for (let c of chunks) {152 let cd = decision.customDiff;153 if (hasEntries(cd)) {154 if (decision.localPath.length > 0) {155 cd = pushPath(cd, decision.localPath);156 }157 // Split custom diff according to chunk lines158 let boundaries =159 [0, base.length, c.baseStart, c.baseEnd].filter(unique).sort();160 cd = splitDiffsOnBoundaries(cd as IDiffArrayEntry[], boundaries);161 }162 out.push(new MergeDecision(163 decision.absolutePath.slice(),164 c.diffs[0],165 c.diffs[1],166 decision.action,167 decision.conflict168 ));169 }170 return out;171}172export173function splitMergeDecisionsOnChunks(base: any[], decisions: MergeDecision[]): MergeDecision[] {174 let out: MergeDecision[] = [];175 for (let md of decisions) {176 let diffs: DiffCollection = [177 buildDiffs(base, [md], 'local'),178 buildDiffs(base, [md], 'remote')179 ];180 let chunks = makeMergeChunks(base, diffs);181 out = out.concat(splitDecisionByChunks(base, md, chunks));182 }183 return out;...

Full Screen

Full Screen

Using AI Code Generation

copy

Full Screen

1var argos = require('argos');2var diffs = argos.diffs;3var obj1 = {4 c: {5 },6 e: {7 }8};9var obj2 = {10 c: {11 },12 e: {13 },14};15var diff = diffs(obj1, obj2);16console.log(diff);17var argos = require('argos');18var patch = argos.patch;19var obj1 = {20 c: {21 },22 e: {23 }24};25var obj2 = {26 c: {27 },28 e: {29 },30};31var diff = diffs(obj1, obj2);32var obj3 = patch(obj1, diff);33console.log(obj3);34var argos = require('argos');35var patch = argos.patch;36var obj1 = {37 c: {38 },39 e: {40 }41};42var obj2 = {43 c: {44 },45 e: {46 },47};48var diff = diffs(obj1, obj2);49var obj3 = patch(obj1, diff);50console.log(obj3);51var argos = require('argos');52var patch = argos.patch;53var obj1 = {54 c: {55 },56 e: {57 }58};59var obj2 = {60 c: {61 },62 e: {

Full Screen

Using AI Code Generation

copy

Full Screen

1const {diffs} = require('argos')2const {expect} = require('chai')3describe('my feature', () => {4 it('should work', () => {5 expect(actual).to.equal(expected)6 })7})

Full Screen

Using AI Code Generation

copy

Full Screen

1var argosy = require('argosy')2var pattern = require('argosy-pattern')3var test = require('tape')4var service = argosy()5service.use(pattern({6 'add': function (a, b) {7 }8}))9test('add', function (t) {10 t.plan(1)11 service.act('add:1,2', function (err, response) {12 t.equal(response, 3)13 })14})15var argosy = require('argosy')16var pattern = require('argosy-pattern')17var test = require('tape')18var service = argosy()19service.use(pattern({20 'add': function (a, b) {21 }22}))23test('add', function (t) {24 t.plan(1)25 service.act('add:1,2', function (err, response) {26 t.equal(response, 3)27 })28})

Full Screen

Using AI Code Generation

copy

Full Screen

1var argos = require('argos');2var diffs = argos.diffs;3var a = diffs('a', 'b');4console.log(a);5var argos = require('argos');6var diffs = argos.diffs;7var a = diffs('a', 'b');8console.log(a);

Full Screen

Using AI Code Generation

copy

Full Screen

1var argos = require('argos');2var diff = argos.diff;3var old = {4 address: {5 }6};7var updated = {8 address: {9 }10};11console.log(diff(old, updated));

Full Screen

Automation Testing Tutorials

Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.

LambdaTest Learning Hubs:

YouTube

You could also refer to video tutorials over LambdaTest YouTube channel to get step by step demonstration from industry experts.

Run argos automation tests on LambdaTest cloud grid

Perform automation testing on 3000+ real desktop and mobile devices online.

Try LambdaTest Now !!

Get 100 minutes of automation test minutes FREE!!

Next-Gen App & Browser Testing Cloud

Was this article helpful?

Helpful

NotHelpful