How to use diffs method in fast-check-monorepo

Best JavaScript code snippet using fast-check-monorepo

diff_match_patch_uncompressed.js

Source:diff_match_patch_uncompressed.js

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;...

diff_match_patch_uncompressed.js.js

Source:diff_match_patch_uncompressed.js.js

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;...

diff_match_patch_amd.js

Source:diff_match_patch_amd.js

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;...

decisionchunking.ts

Source:decisionchunking.ts

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;...

Using AI Code Generation

1const fc = require('fast-check');2const { diffs } = require('fast-check-monorepo');3const fc = require('fast-check');4const { diffs } = require('fast-check-monorepo');5const fc = require('fast-check');6const { diffs } = require('fast-check-monorepo');7const fc = require('fast-check');8const { diffs } = require('fast-check-monorepo');9const fc = require('fast-check');10const { diffs } = require('fast-check-monorepo');11const fc = require('fast-check');12const { diffs } = require('fast-check-monorepo');13const fc = require('fast-check');14const { diffs } = require('fast-check-monorepo');15const fc = require('fast-check');16const { diffs } = require('fast-check-monorepo');17const fc = require('fast-check');18const { diffs } = require('fast-check-monorepo');19const fc = require('fast-check');20const { diffs } = require('fast-check-monorepo');21const fc = require('fast-check');22const { diffs } = require('fast-check-monorepo');23const fc = require('fast-check');24const { diffs } = require('fast-check-monorepo');25const fc = require('fast-check');26const { diffs } = require('fast-check-monorepo');27const fc = require('fast-check');28const { diffs } = require('fast-check-monorepo');29const fc = require('fast-check');30const { diffs } = require('fast-check-monorepo');

Using AI Code Generation

1const { diffs } = require('fast-check-monorepo')2const { diffs } = require('fast-check')3const { diffs } = require('fast-check-monorepo')4const { diffs } = require('fast-check')5const { diffs } = require('fast-check-monorepo')6const { diffs } = require('fast-check')7const { diffs } = require('fast-check-monorepo')8const { diffs } = require('fast-check')9const { diffs } = require('fast-check-monorepo')10const { diffs } = require('fast-check')11const { diffs } = require('fast-check-monorepo')12const { diffs } = require('fast-check')13const { diffs } = require('fast-check-monorepo')14const { diffs } = require('fast-check')15const { diffs } = require('fast-check-monorepo')16const { diffs } = require('fast-check')17const { diffs } = require('fast-check-monorepo')18const { diffs } = require('fast-check')19const { diffs } = require('fast-check-monorepo')20const { diffs } = require('

Using AI Code Generation

1const { diffs } = require('fast-check-monorepo');2const diff = diffs({3  a: {4  },5  b: {6  }7});8console.log(diff);9const { diff } = require('fast-check-monorepo');10const diff = diff({11  a: {12  },13  b: {14  }15});16console.log(diff);17const { diff } = require('fast-check-monorepo');18const diff = diff({19  a: {20  },21  b: {22  }23}, {24  a: {25  },26  b: {27  }28});29console.log(diff);30const { diff } = require('fast-check-monorepo');31const diff = diff({32  a: {33  },34  b: {35  }36}, {37  a: {38  },39  b: {40  },41});42console.log(diff);

Using AI Code Generation

1const fc = require('fast-check');2const diff = require('fast-check-monorepo/diffs');3const { strictEqual } = require('assert');4fc.assert(5  fc.property(6    fc.array(fc.integer(), 1, 100),7    fc.array(fc.integer(), 1, 100),8    (a, b) => {9      strictEqual(diff(a, b), diff(b, a));10    }11);12{13  "dependencies": {14  }15}

Using AI Code Generation

1const fc = require("fast-check");2const { diffs } = require("fast-check-monorepo");3const { diff } = require("diff");4const diffArb = diffs();5fc.assert(6  fc.property(diffArb, (diffs) => {7    const diffStr = diffs.map((d) => d.value).join("");8    const diffResult = diff.diffLines("Hello World", diffStr);9    return diffResult.length === 1;10  })11);

Using AI Code Generation

1const { diffs } = require('../src/index.js');2const assert = require('assert');3const diff = diffs([1, 2, 3, 4], [1, 2, 4, 5]);4assert.deepEqual(diff, [5  { type: 'equal', value: 1 },6  { type: 'equal', value: 2 },7  { type: 'delete', value: 3 },8  { type: 'equal', value: 4 },9  { type: 'insert', value: 5 }10]);11console.log('Test passed');

Using AI Code Generation

1const fc = require('fast-check');2const diff = require('fast-check-diff');3const { diffs } = diff;4const { int8Array } = fc;5const { equal, notEqual } = diffs;6fc.assert(7  fc.property(int8Array(), (a) => {8    equal(a, a);9  })10);11fc.assert(12  fc.property(int8Array(), int8Array(), (a, b) => {13    notEqual(a, b);14  })15);16const fc = require('fast-check');17const diff = require('fast-check-diff');18const { diffs } = diff;19const { int8Array } = fc;20const { equal, notEqual } = diffs;21fc.assert(22  fc.property(int8Array(), (a) => {23    equal(a, a);24  })25);26fc.assert(27  fc.property(int8Array(), int8Array(), (a, b) => {28    notEqual(a, b);29  })30);31const fc = require('fast-check');32const diff = require('fast-check-diff');33const { diffs } = diff;34const { int8Array } = fc;35const { equal, notEqual } = diffs;36fc.assert(37  fc.property(int8Array(), (a) => {38    equal(a, a);39  })40);41fc.assert(42  fc.property(int8Array(), int8Array(), (a, b) => {43    notEqual(a, b);44  })45);46const fc = require('fast-check');47const diff = require('fast-check-diff');48const { diffs } = diff;49const { int8Array } = fc;50const { equal, notEqual } = diffs;51fc.assert(52  fc.property(int8Array(), (a) => {53    equal(a, a);54  })55);56fc.assert(57  fc.property(int8Array(), int8Array(), (a, b) => {58    notEqual(a, b);59  })60);61const fc = require('fast-check');62const diff = require('fast-check-diff');63const { diffs } = diff;

Using AI Code Generation

1const { diffs } = require('fast-check-monorepo');2const fc = require('fast-check');3const { generate } = require('./index');4fc.assert(5  fc.property(fc.integer(), fc.integer(), fc.integer(), (a, b, c) => {6    const result1 = generate(a, b, c);7    const result2 = generate(a, b, c);8    return diffs(result1, result2).length === 0;9  })10);11fc.assert(12  fc.property(fc.integer(), fc.integer(), fc.integer(), (a, b, c) => {13    const result1 = generate(a, b, c);14    const result2 = generate(a, b, c + 1);15    return diffs(result1, result2).length > 0;16  })17);18fc.assert(19  fc.property(fc.integer(), fc.integer(), fc.integer(), (a, b, c) => {20    const result1 = generate(a, b, c);21    const result2 = generate(a, b + 1, c);22    return diffs(result1, result2).length > 0;23  })24);25fc.assert(26  fc.property(fc.integer(), fc.integer(), fc.integer(), (a, b, c) => {27    const result1 = generate(a, b, c);28    const result2 = generate(a + 1, b, c);29    return diffs(result1, result2).length > 0;30  })31);32fc.assert(33  fc.property(fc.integer(), fc.integer(), fc.integer(), (a, b, c) => {34    const result1 = generate(a, b, c);35    const result2 = generate(a, b, c);36    return diffs(result1, result2).length === 0;37  })38);39fc.assert(40  fc.property(fc.integer(), fc.integer(), fc.integer(), (a, b, c) => {41    const result1 = generate(a,

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.