☰

diff_match_patch-for-require

Diff Match and Patch

Dette scriptet burde ikke installeres direkte. Det er et bibliotek for andre script å inkludere med det nye metadirektivet // @require https://update.greatest.deepsurf.us/scripts/9547/48896/diff_match_patch-for-require.js 

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