1 // Diff_Match_Patch v1.3

     2 // Computes the difference between two texts to create a patch.

     3 // Applies the patch onto another text, allowing for errors.

     4 // Copyright (C) 2006 Neil Fraser

     5 // http://neil.fraser.name/software/diff_match_patch/

     6 

     7 // This program is free software; you can redistribute it and/or

     8 // modify it under the terms of the GNU General Public License

     9 // as published by the Free Software Foundation.

    10 

    11 // This program is distributed in the hope that it will be useful,

    12 // but WITHOUT ANY WARRANTY; without even the implied warranty of

    13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    14 // GNU General Public License (www.gnu.org) for more details.

    15 

    16 

    17 // Constants.

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

    19 

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

    21 var DIFF_TIMEOUT = 1.0;

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

    23 var DIFF_EDIT_COST = 4;

    24 // Tweak the relative importance (0.0 = accuracy, 1.0 = proximity)

    25 var MATCH_BALANCE = 0.5;

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

    27 var MATCH_THRESHOLD = 0.5;

    28 // The min and max cutoffs used when computing text lengths.

    29 var MATCH_MINLENGTH = 100;

    30 var MATCH_MAXLENGTH = 1000;

    31 // Chunk size for context length.

    32 var PATCH_MARGIN = 4;

    33 

    34 

    35   //////////////////////////////////////////////////////////////////////

    36  //  Diff                                                            //

    37 //////////////////////////////////////////////////////////////////////

    38 

    39 // The data structure representing a diff is an array of tuples:

    40 // [[-1, "Hello"], [1, "Goodbye"], [0, " world."]]

    41 // which means: delete "Hello", add "Goodbye" and keep " world."

    42 

    43 

    44 function diff_main(text1, text2, checklines) {

    45   // Find the differences between two texts.  Return an array of changes.

    46   // If checklines is present and false, then don't run a line-level diff first to identify the changed areas.

    47   // Check for equality (speedup)

    48   if (text1 == text2)

    49     return [[0, text1]];

    50 

    51   if (typeof checklines == 'undefined')

    52     checklines = true;

    53 

    54   var a;

    55   // Trim off common prefix (speedup)

    56   a = diff_prefix(text1, text2);

    57   text1 = a[0];

    58   text2 = a[1];

    59   var commonprefix = a[2];

    60 

    61   // Trim off common suffix (speedup)

    62   a = diff_suffix(text1, text2);

    63   text1 = a[0];

    64   text2 = a[1];

    65   var commonsuffix = a[2];

    66 

    67   var diff, i;

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

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

    70 

    71   if (!text1) {  // Just add some text (speedup)

    72     diff = [[1, text2]];

    73   } else if (!text2) { // Just delete some text (speedup)

    74     diff = [[-1, text1]];

    75   } else if ((i = longtext.indexOf(shorttext)) != -1) {

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

    77     diff = [[1, longtext.substring(0, i)], [0, shorttext], [1, longtext.substring(i+shorttext.length)]];

    78     // Swap insertions for deletions if diff is reversed.

    79     if (text1.length > text2.length)

    80       diff[0][0] = diff[2][0] = -1;

    81   } else {

    82     longtext = shorttext = null; // Garbage collect

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

    84     var hm = diff_halfmatch(text1, text2);

    85     if (hm) {

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

    87       var text1_a = hm[0];

    88       var text1_b = hm[1];

    89       var text2_a = hm[2];

    90       var text2_b = hm[3];

    91       var mid_common = hm[4];

    92       // Send both pairs off for separate processing.

    93       var diff_a = diff_main(text1_a, text2_a, checklines);

    94       var diff_b = diff_main(text1_b, text2_b, checklines);

    95       // Merge the results.

    96       diff = diff_a.concat([[0, mid_common]], diff_b);

    97     } else {

    98       // Perform a real diff.

    99       if (checklines && text1.length + text2.length < 250)

   100         checklines = false; // Too trivial for the overhead.

   101       if (checklines) {

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

   103         a = diff_lines2chars(text1, text2);

   104         text1 = a[0];

   105         text2 = a[1];

   106         var linearray = a[2];

   107       }

   108       diff = diff_map(text1, text2);

   109       if (!diff) // No acceptable result.

   110         diff = [[-1, text1], [1, text2]];

   111       if (checklines) {

   112         diff_chars2lines(diff, linearray); // Convert the diff back to original text.

   113         diff_cleanup_semantic(diff); // Eliminate freak matches (e.g. blank lines)

   114 

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

   116         diff.push([0, '']);  // Add a dummy entry at the end.

   117         var pointer = 0;

   118         var count_delete = 0;

   119         var count_insert = 0;

   120         var text_delete = '';

   121         var text_insert = '';

   122         while(pointer < diff.length) {

   123           if (diff[pointer][0] == 1) {

   124             count_insert++;

   125             text_insert += diff[pointer][1];

   126           } else if (diff[pointer][0] == -1) {

   127             count_delete++;

   128             text_delete += diff[pointer][1];

   129           } else {  // Upon reaching an equality, check for prior redundancies.

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

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

   132               a = diff_main(text_delete, text_insert, false);

   133               diff.splice(pointer - count_delete - count_insert, count_delete + count_insert);

   134               pointer = pointer - count_delete - count_insert;

   135               for (i=a.length-1; i>=0; i--)

   136                 diff.splice(pointer, 0, a[i]);

   137               pointer = pointer + a.length;

   138             }

   139             count_insert = 0;

   140             count_delete = 0;

   141             text_delete = '';

   142             text_insert = '';

   143           }

   144           pointer++;

   145         }

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

   147 

   148       }

   149     }

   150   }

   151 

   152   if (commonprefix)

   153     diff.unshift([0, commonprefix]);

   154   if (commonsuffix)

   155     diff.push([0, commonsuffix]);

   156   diff_cleanup_merge(diff);

   157   return diff;

   158 }

   159 

   160 

   161 function diff_lines2chars(text1, text2) {

   162   // Split text into an array of strings.

   163   // Reduce the texts to a string of hashes where each character represents one line.

   164   var linearray = new Array();  // linearray[4] == "Hello\n"

   165   var linehash = new Object();  // linehash["Hello\n"] == 4

   166 

   167   // "\x00" is a valid JavaScript character, but the Venkman debugger doesn't like it (bug 335098)

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

   169   linearray.push('');

   170 

   171   function diff_lines2chars_munge(text) {

   172     // My first ever closure!

   173     var i, line;

   174     var chars = '';

   175     while (text) {

   176       i = text.indexOf('\n');

   177       if (i == -1)

   178         i = text.length;

   179       line = text.substring(0, i+1);

   180       text = text.substring(i+1);

   181       if (linehash.hasOwnProperty ? linehash.hasOwnProperty(line) : (linehash[line] !== undefined)) {

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

   183       } else {

   184         linearray.push(line);

   185         linehash[line] = linearray.length - 1;

   186         chars += String.fromCharCode(linearray.length - 1);

   187       }

   188     }

   189     return chars;

   190   }

   191 

   192   var chars1 = diff_lines2chars_munge(text1);

   193   var chars2 = diff_lines2chars_munge(text2);

   194   return [chars1, chars2, linearray];

   195 }

   196 

   197 

   198 function diff_chars2lines(diff, linearray) {

   199   // Rehydrate the text in a diff from a string of line hashes to real lines of text.

   200   var chars, text;

   201   for (var x=0; x<diff.length; x++) {

   202     chars = diff[x][1];

   203     text = '';

   204     for (var y=0; y<chars.length; y++)

   205       text += linearray[chars.charCodeAt(y)];

   206     diff[x][1] = text;

   207   }

   208 }

   209 

   210 

   211 function diff_map(text1, text2) {

   212   // Explore the intersection points between the two texts.

   213   var now = new Date();

   214   var ms_end = now.getTime() + DIFF_TIMEOUT * 1000; // Don't run for too long.

   215   var max = (text1.length + text2.length) / 2;

   216   var v_map1 = new Array();

   217   var v_map2 = new Array();

   218   var v1 = new Object();

   219   var v2 = new Object();

   220   v1[1] = 0;

   221   v2[1] = 0;

   222   var x, y;

   223   var footstep; // Used to track overlapping paths.

   224   var footsteps = new Object();

   225   var done = false;

   226   var hasOwnProperty = !!(footsteps.hasOwnProperty);

   227   // If the total number of characters is odd, then the front path will collide with the reverse path.

   228   var front = (text1.length + text2.length) % 2;

   229   for (var d=0; d<max; d++) {

   230     now = new Date();

   231     if (DIFF_TIMEOUT > 0 && now.getTime() > ms_end) // Timeout reached

   232       return null;

   233 

   234     // Walk the front path one step.

   235     v_map1[d] = new Object();

   236     for (var k=-d; k<=d; k+=2) {

   237       if (k == -d || k != d && v1[k-1] < v1[k+1])

   238         x = v1[k+1];

   239       else

   240         x = v1[k-1]+1;

   241       y = x - k;

   242       footstep = x+","+y;

   243       if (front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))

   244         done = true;

   245       if (!front)

   246         footsteps[footstep] = d;

   247       while (!done && x < text1.length && y < text2.length && text1.charAt(x) == text2.charAt(y)) {

   248         x++; y++;

   249         footstep = x+","+y;

   250         if (front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))

   251           done = true;

   252         if (!front)

   253           footsteps[footstep] = d;

   254       }

   255       v1[k] = x;

   256       v_map1[d][x+","+y] = true;

   257       if (done) {

   258         // Front path ran over reverse path.

   259         v_map2 = v_map2.slice(0, footsteps[footstep]+1);

   260         var a = diff_path1(v_map1, text1.substring(0, x), text2.substring(0, y));

   261         return a.concat(diff_path2(v_map2, text1.substring(x), text2.substring(y)));

   262       }

   263     }

   264 

   265     // Walk the reverse path one step.

   266     v_map2[d] = new Object();

   267     for (var k=-d; k<=d; k+=2) {

   268       if (k == -d || k != d && v2[k-1] < v2[k+1])

   269         x = v2[k+1];

   270       else

   271         x = v2[k-1]+1;

   272       y = x - k;

   273       footstep = (text1.length-x)+","+(text2.length-y);

   274       if (!front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))

   275         done = true;

   276       if (front)

   277         footsteps[footstep] = d;

   278       while (!done && x < text1.length && y < text2.length && text1.charAt(text1.length-x-1) == text2.charAt(text2.length-y-1)) {

   279         x++; y++;

   280         footstep = (text1.length-x)+","+(text2.length-y);

   281         if (!front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))

   282           done = true;

   283         if (front)

   284           footsteps[footstep] = d;

   285       }

   286       v2[k] = x;

   287       v_map2[d][x+","+y] = true;

   288       if (done) {

   289         // Reverse path ran over front path.

   290         v_map1 = v_map1.slice(0, footsteps[footstep]+1);

   291         var a = diff_path1(v_map1, text1.substring(0, text1.length-x), text2.substring(0, text2.length-y));

   292         return a.concat(diff_path2(v_map2, text1.substring(text1.length-x), text2.substring(text2.length-y)));

   293       }

   294     }

   295   }

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

   297   return null;

   298 }

   299 

   300 

   301 function diff_path1(v_map, text1, text2) {

   302   // Work from the middle back to the start to determine the path.

   303   var path = [];

   304   var x = text1.length;

   305   var y = text2.length;

   306   var last_op = null;

   307   for (var d=v_map.length-2; d>=0; d--) {

   308     while(1) {

   309       if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty((x-1)+","+y) : (v_map[d][(x-1)+","+y] !== undefined)) {

   310         x--;

   311         if (last_op === -1)

   312           path[0][1] = text1.charAt(x) + path[0][1];

   313         else

   314           path.unshift([-1, text1.charAt(x)]);

   315         last_op = -1;

   316         break;

   317       } else if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty(x+","+(y-1)) : (v_map[d][x+","+(y-1)] !== undefined)) {

   318         y--;

   319         if (last_op === 1)

   320           path[0][1] = text2.charAt(y) + path[0][1];

   321         else

   322           path.unshift([1, text2.charAt(y)]);

   323         last_op = 1;

   324         break;

   325       } else {

   326         x--;

   327         y--;

   328         //if (text1.charAt(x) != text2.charAt(y))

   329         //  return alert("No diagonal.  Can't happen. (diff_path1)");

   330         if (last_op === 0)

   331           path[0][1] = text1.charAt(x) + path[0][1];

   332         else

   333           path.unshift([0, text1.charAt(x)]);

   334         last_op = 0;

   335       }

   336     }

   337   }

   338   return path;

   339 }

   340 

   341 

   342 function diff_path2(v_map, text1, text2) {

   343   // Work from the middle back to the end to determine the path.

   344   var path = [];

   345   var x = text1.length;

   346   var y = text2.length;

   347   var last_op = null;

   348   for (var d=v_map.length-2; d>=0; d--) {

   349     while(1) {

   350       if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty((x-1)+","+y) : (v_map[d][(x-1)+","+y] !== undefined)) {

   351         x--;

   352         if (last_op === -1)

   353           path[path.length-1][1] += text1.charAt(text1.length-x-1);

   354         else

   355           path.push([-1, text1.charAt(text1.length-x-1)]);

   356         last_op = -1;

   357         break;

   358       } else if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty(x+","+(y-1)) : (v_map[d][x+","+(y-1)] !== undefined)) {

   359         y--;

   360         if (last_op === 1)

   361           path[path.length-1][1] += text2.charAt(text2.length-y-1);

   362         else

   363           path.push([1, text2.charAt(text2.length-y-1)]);

   364         last_op = 1;

   365         break;

   366       } else {

   367         x--;

   368         y--;

   369         //if (text1.charAt(text1.length-x-1) != text2.charAt(text2.length-y-1))

   370         //  return alert("No diagonal.  Can't happen. (diff_path2)");

   371         if (last_op === 0)

   372           path[path.length-1][1] += text1.charAt(text1.length-x-1);

   373         else

   374           path.push([0, text1.charAt(text1.length-x-1)]);

   375         last_op = 0;

   376       }

   377     }

   378   }

   379   return path;

   380 }

   381 

   382 

   383 function diff_prefix(text1, text2) {

   384   // Trim off common prefix

   385   var pointermin = 0;

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

   387   var pointermid = pointermax;

   388   while(pointermin < pointermid) {

   389     if (text1.substring(0, pointermid) == text2.substring(0, pointermid))

   390       pointermin = pointermid;

   391     else

   392       pointermax = pointermid;

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

   394   }

   395   var commonprefix = text1.substring(0, pointermid);

   396   text1 = text1.substring(pointermid);

   397   text2 = text2.substring(pointermid);

   398   return [text1, text2, commonprefix];

   399 }

   400 

   401 

   402 function diff_suffix(text1, text2) {

   403   // Trim off common suffix

   404   var pointermin = 0;

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

   406   var pointermid = pointermax;

   407   while(pointermin < pointermid) {

   408     if (text1.substring(text1.length-pointermid) == text2.substring(text2.length-pointermid))

   409       pointermin = pointermid;

   410     else

   411       pointermax = pointermid;

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

   413   }

   414   var commonsuffix = text1.substring(text1.length-pointermid);

   415   text1 = text1.substring(0, text1.length-pointermid);

   416   text2 = text2.substring(0, text2.length-pointermid);

   417   return [text1, text2, commonsuffix];

   418 }

   419 

   420 

   421 function diff_halfmatch(text1, text2) {

   422   // Do the two texts share a substring which is at least half the length of the longer text?

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

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

   425   if (longtext.length < 10 || shorttext.length < 1)

   426     return null; // Pointless.

   427 

   428   function diff_halfmatch_i(longtext, shorttext, i) {

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

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

   431     var j = -1;

   432     var best_common = '';

   433     var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;

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

   435       var my_prefix = diff_prefix(longtext.substring(i), shorttext.substring(j));

   436       var my_suffix = diff_suffix(longtext.substring(0, i), shorttext.substring(0, j));

   437       if (best_common.length < (my_suffix[2] + my_prefix[2]).length) {

   438         best_common = my_suffix[2] + my_prefix[2];

   439         best_longtext_a = my_suffix[0];

   440         best_longtext_b = my_prefix[0];

   441         best_shorttext_a = my_suffix[1];

   442         best_shorttext_b = my_prefix[1];

   443       }

   444     }

   445     if (best_common.length >= longtext.length/2)

   446       return [best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common];

   447     else

   448       return null;

   449   }

   450 

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

   452   var hm1 = diff_halfmatch_i(longtext, shorttext, Math.ceil(longtext.length/4));

   453   // Check again based on the third quarter.

   454   var hm2 = diff_halfmatch_i(longtext, shorttext, Math.ceil(longtext.length/2));

   455   var hm;

   456   if (!hm1 && !hm2)

   457     return null;

   458   else if (!hm2)

   459     hm = hm1;

   460   else if (!hm1)

   461     hm = hm2;

   462   else // Both matched.  Select the longest.

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

   464 

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

   466   if (text1.length > text2.length) {

   467     var text1_a = hm[0];

   468     var text1_b = hm[1];

   469     var text2_a = hm[2];

   470     var text2_b = hm[3];

   471   } else {

   472     var text2_a = hm[0];

   473     var text2_b = hm[1];

   474     var text1_a = hm[2];

   475     var text1_b = hm[3];

   476   }

   477   var mid_common = hm[4];

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

   479 }

   480 

   481 

   482 function diff_cleanup_semantic(diff) {

   483   // Reduce the number of edits by eliminating semantically trivial equalities.

   484   var changes = false;

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

   486   var lastequality = null; // Always equal to equalities[equalities.length-1][1]

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

   488   var length_changes1 = 0; // Number of characters that changed prior to the equality.

   489   var length_changes2 = 0; // Number of characters that changed after the equality.

   490   while (pointer < diff.length) {

   491     if (diff[pointer][0] == 0) { // equality found

   492       equalities.push(pointer);

   493       length_changes1 = length_changes2;

   494       length_changes2 = 0;

   495       lastequality = diff[pointer][1];

   496     } else { // an insertion or deletion

   497       length_changes2 += diff[pointer][1].length;

   498       if (lastequality != null && (lastequality.length <= length_changes1) && (lastequality.length <= length_changes2)) {

   499         //alert("Splitting: '"+lastequality+"'");

   500         diff.splice(equalities[equalities.length-1], 0, [-1, lastequality]); // Duplicate record

   501         diff[equalities[equalities.length-1]+1][0] = 1; // Change second copy to insert.

   502         equalities.pop();  // Throw away the equality we just deleted;

   503         equalities.pop();  // Throw away the previous equality;

   504         pointer = equalities.length ? equalities[equalities.length-1] : -1;

   505         length_changes1 = 0; // Reset the counters.

   506         length_changes2 = 0;

   507         lastequality = null;

   508         changes = true;

   509       }

   510     }

   511     pointer++;

   512   }

   513 

   514   if (changes)

   515     diff_cleanup_merge(diff);

   516 }

   517 

   518 

   519 function diff_cleanup_efficiency(diff) {

   520   // Reduce the number of edits by eliminating operationally trivial equalities.

   521   var changes = false;

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

   523   var lastequality = ''; // Always equal to equalities[equalities.length-1][1]

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

   525   var pre_ins = false; // Is there an insertion operation before the last equality.

   526   var pre_del = false; // Is there an deletion operation before the last equality.

   527   var post_ins = false; // Is there an insertion operation after the last equality.

   528   var post_del = false; // Is there an deletion operation after the last equality.

   529   while (pointer < diff.length) {

   530     if (diff[pointer][0] == 0) { // equality found

   531       if (diff[pointer][1].length < DIFF_EDIT_COST && (post_ins || post_del)) {

   532         // Candidate found.

   533         equalities.push(pointer);

   534         pre_ins = post_ins;

   535         pre_del = post_del;

   536         lastequality = diff[pointer][1];

   537       } else {

   538         // Not a candidate, and can never become one.

   539         equalities = [];

   540         lastequality = '';

   541       }

   542       post_ins = post_del = false;

   543     } else { // an insertion or deletion

   544       if (diff[pointer][0] == -1)

   545         post_del = true;

   546       else

   547         post_ins = true;

   548       // Five types to be split:

   549       // <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>

   550       // <ins>A</ins>X<ins>C</ins><del>D</del>

   551       // <ins>A</ins><del>B</del>X<ins>C</ins>

   552       // <ins>A</del>X<ins>C</ins><del>D</del>

   553       // <ins>A</ins><del>B</del>X<del>C</del>

   554       if (lastequality && ((pre_ins && pre_del && post_ins && post_del) || ((lastequality.length < DIFF_EDIT_COST/2) && (pre_ins + pre_del + post_ins + post_del) == 3))) {

   555         //alert("Splitting: '"+lastequality+"'");

   556         diff.splice(equalities[equalities.length-1], 0, [-1, lastequality]); // Duplicate record

   557         diff[equalities[equalities.length-1]+1][0] = 1; // Change second copy to insert.

   558         equalities.pop();  // Throw away the equality we just deleted;

   559         lastequality = '';

   560         if (pre_ins && pre_del) {

   561           // No changes made which could affect previous entry, keep going.

   562           post_ins = post_del = true;

   563           equalities = [];

   564         } else {

   565           equalities.pop();  // Throw away the previous equality;

   566           pointer = equalities.length ? equalities[equalities.length-1] : -1;

   567           post_ins = post_del = false;

   568         }

   569         changes = true;

   570       }

   571     }

   572     pointer++;

   573   }

   574 

   575   if (changes)

   576     diff_cleanup_merge(diff);

   577 }

   578 

   579 

   580 function diff_cleanup_merge(diff) {

   581   // Reorder and merge like edit sections.  Merge equalities.

   582   // Any edit section can move as long as it doesn't cross an equality.

   583   diff.push([0, '']);  // Add a dummy entry at the end.

   584   var pointer = 0;

   585   var count_delete = 0;

   586   var count_insert = 0;

   587   var text_delete = '';

   588   var text_insert = '';

   589   var record_insert, record_delete;

   590   var my_xfix;

   591   while(pointer < diff.length) {

   592     if (diff[pointer][0] == 1) {

   593       count_insert++;

   594       text_insert += diff[pointer][1];

   595       pointer++;

   596     } else if (diff[pointer][0] == -1) {

   597       count_delete++;

   598       text_delete += diff[pointer][1];

   599       pointer++;

   600     } else {  // Upon reaching an equality, check for prior redundancies.

   601       if (count_delete > 1 || count_insert > 1) {

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

   603           // Factor out any common prefixies.

   604           my_xfix = diff_prefix(text_insert, text_delete);

   605           if (my_xfix[2] != '') {

   606             if ((pointer - count_delete - count_insert) > 0 && diff[pointer - count_delete - count_insert - 1][0] == 0) {

   607               text_insert = my_xfix[0];

   608               text_delete = my_xfix[1];

   609               diff[pointer - count_delete - count_insert - 1][1] += my_xfix[2];

   610             }

   611           }

   612           // Factor out any common suffixies.

   613           my_xfix = diff_suffix(text_insert, text_delete);

   614           if (my_xfix[2] != '') {

   615             text_insert = my_xfix[0];

   616             text_delete = my_xfix[1];

   617             diff[pointer][1] = my_xfix[2] + diff[pointer][1];

   618           }

   619         }

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

   621         if (count_delete == 0)

   622           diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [1, text_insert]);

   623         else if (count_insert == 0)

   624           diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [-1, text_delete]);

   625         else

   626           diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [-1, text_delete], [1, text_insert]);

   627         pointer = pointer - count_delete - count_insert + (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;

   628       } else if (pointer != 0 && diff[pointer-1][0] == 0) {

   629         // Merge this equality with the previous one.

   630         diff[pointer-1][1] += diff[pointer][1];

   631         diff.splice(pointer, 1);

   632       } else {

   633         pointer++;

   634       }

   635       count_insert = 0;

   636       count_delete = 0;

   637       text_delete = '';

   638       text_insert = '';

   639     }

   640   }

   641   if (diff[diff.length-1][1] == '')

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

   643 }

   644 

   645 

   646 function diff_addindex(diff) {

   647   // Add an index to each tuple, represents where the tuple is located in text2.

   648   // e.g. [[-1, 'h', 0], [1, 'c', 0], [0, 'at', 1]]

   649   var i = 0;

   650   for (var x=0; x<diff.length; x++) {

   651     diff[x].push(i);

   652     if (diff[x][0] != -1)

   653       i += diff[x][1].length;

   654   }

   655 }

   656 

   657 

   658 function diff_xindex(diff, loc) {

   659   // loc is a location in text1, compute and return the equivalent location in text2.

   660   // e.g. "The cat" vs "The big cat", 1->1, 5->8

   661   var chars1 = 0;

   662   var chars2 = 0;

   663   var last_chars1 = 0;

   664   var last_chars2 = 0;

   665   for (var x=0; x<diff.length; x++) {

   666     if (diff[x][0] != 1) // Equality or deletion.

   667       chars1 += diff[x][1].length;

   668     if (diff[x][0] != -1) // Equality or insertion.

   669       chars2 += diff[x][1].length;

   670     if (chars1 > loc) // Overshot the location.

   671       break;

   672     last_chars1 = chars1;

   673     last_chars2 = chars2;

   674   }

   675   if (diff.length != x && diff[x][0] == -1) // The location was deleted.

   676     return last_chars2;

   677   // Add the remaining character length.

   678   return last_chars2 + (loc - last_chars1);

   679 }

   680 

   681 

   682 function diff_prettyhtml(diff) {

   683   // Convert a diff array into a pretty HTML report.

   684   diff_addindex(diff);

   685   var html = '';

   686   for (var x=0; x<diff.length; x++) {

   687     var m = diff[x][0]; // Mode (-1=delete, 0=copy, 1=add)

   688     var t = diff[x][1]; // Text of change.

   689     var i = diff[x][2]; // Index of change.

   690     t = t.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;");

   691     t = t.replace(/\n/g, "&para;<BR>");

   692     if (m == -1)

   693       html += "<DEL STYLE='background:#FFE6E6;' TITLE='i="+i+"'>"+t+"</DEL>";

   694     else if (m == 1)

   695       html += "<INS STYLE='background:#E6FFE6;' TITLE='i="+i+"'>"+t+"</INS>";

   696     else

   697       html += "<SPAN TITLE='i="+i+"'>"+t+"</SPAN>";

   698   }

   699   return html;

   700 }

   701 

   702 

   703   //////////////////////////////////////////////////////////////////////

   704  //  Match                                                           //

   705 //////////////////////////////////////////////////////////////////////

   706 

   707 

   708 function match_getmaxbits() {

   709   // Compute the number of bits in an int.

   710   // The normal answer for JavaScript is 32.

   711   var maxbits = 0;

   712   var oldi = 1;

   713   var newi = 2;

   714   while (oldi != newi) {

   715     maxbits++;

   716     oldi = newi;

   717     newi = newi << 1;

   718   }

   719   return maxbits;

   720 }

   721 var MATCH_MAXBITS = match_getmaxbits();

   722 

   723 

   724 function match_main(text, pattern, loc) {

   725   // Locate the best instance of 'pattern' in 'text' near 'loc'.

   726   loc = Math.max(0, Math.min(loc, text.length-pattern.length));

   727   if (text == pattern) {

   728     // Shortcut (potentially not guaranteed by the algorithm)

   729     return 0;

   730   } else if (text.length == 0) {

   731     // Nothing to match.

   732     return null;

   733   } else if (text.substring(loc, loc + pattern.length) == pattern) {

   734     // Perfect match at the perfect spot!  (Includes case of null pattern)

   735     return loc;

   736   } else {

   737     // Do a fuzzy compare.

   738     var match = match_bitap(text, pattern, loc);

   739     return match;

   740   }

   741 }

   742 

   743 

   744 function match_bitap(text, pattern, loc) {

   745   // Locate the best instance of 'pattern' in 'text' near 'loc' using the Bitap algorithm.

   746   if (pattern.length > MATCH_MAXBITS)

   747     return alert("Pattern too long for this browser.");

   748 

   749   // Initialise the alphabet.

   750   var s = match_alphabet(pattern);

   751 

   752   var score_text_length = text.length;

   753   // Coerce the text length between reasonable maximums and minimums.

   754   score_text_length = Math.max(score_text_length, MATCH_MINLENGTH);

   755   score_text_length = Math.min(score_text_length, MATCH_MAXLENGTH);

   756 

   757   function match_bitap_score (e, x) {

   758     // Compute and return the score for a match with e errors and x location.

   759     var d = Math.abs(loc-x);

   760     return (e / pattern.length / MATCH_BALANCE) + (d / score_text_length / (1.0 - MATCH_BALANCE));

   761   }

   762 

   763   // Highest score beyond which we give up.

   764   var score_threshold = MATCH_THRESHOLD;

   765   // Is there a nearby exact match? (speedup)

   766   var best_loc = text.indexOf(pattern, loc);

   767   if (best_loc != -1)

   768     score_threshold = Math.min(match_bitap_score(0, best_loc), score_threshold);

   769   // What about in the other direction? (speedup)

   770   best_loc = text.lastIndexOf(pattern, loc+pattern.length);

   771   if (best_loc != -1)

   772     score_threshold = Math.min(match_bitap_score(0, best_loc), score_threshold);

   773 

   774   // Initialise the bit arrays.

   775   var r = Array();

   776   var d = -1;

   777   var matchmask = Math.pow(2, pattern.length-1);

   778   best_loc = null;

   779 

   780   var bin_min, bin_mid;

   781   var bin_max = Math.max(loc+loc, text.length);

   782   var last_rd;

   783   for (var d=0; d<pattern.length; d++) {

   784     // Scan for the best match; each iteration allows for one more error.

   785     var rd = Array(text.length);

   786 

   787     // Run a binary search to determine how far from 'loc' we can stray at this error level.

   788     bin_min = loc;

   789     bin_mid = bin_max;

   790     while(bin_min < bin_mid) {

   791       if (match_bitap_score(d, bin_mid) < score_threshold)

   792         bin_min = bin_mid;

   793       else

   794         bin_max = bin_mid;

   795       bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min);

   796     }

   797     bin_max = bin_mid; // Use the result from this iteration as the maximum for the next.

   798     var start = Math.max(0, loc - (bin_mid - loc) - 1);

   799     var finish = Math.min(text.length-1, pattern.length + bin_mid);

   800 

   801     if (text.charAt(finish) == pattern.charAt(pattern.length-1))

   802       rd[finish] = Math.pow(2, d+1)-1;

   803     else

   804       rd[finish] = Math.pow(2, d)-1;

   805     for (var j=finish-1; j>=start; j--) {

   806       // The alphabet (s) is a sparse hash, so the following lines generate warnings.

   807       if (d == 0) // First pass: exact match.

   808         rd[j] = ((rd[j+1] << 1) | 1) & s[text.charAt(j)];

   809       else // Subsequent passes: fuzzy match.

   810         rd[j] = ((rd[j+1] << 1) | 1) & s[text.charAt(j)] | ((last_rd[j+1] << 1) | 1) | ((last_rd[j] << 1) | 1) | last_rd[j+1];

   811       if (rd[j] & matchmask) {

   812         var score = match_bitap_score(d, j);

   813         // This match will almost certainly be better than any existing match.  But check anyway.

   814         if (score <= score_threshold) {

   815           // Told you so.

   816           score_threshold = score;

   817           best_loc = j;

   818           if (j > loc) {

   819             // When passing loc, don't exceed our current distance from loc.

   820             start = Math.max(0, loc - (j - loc));

   821           } else {

   822             // Already passed loc, downhill from here on in.

   823             break;

   824           }

   825         }

   826       }

   827     }

   828     if (match_bitap_score(d+1, loc) > score_threshold) // No hope for a (better) match at greater error levels.

   829       break;

   830     last_rd = rd;

   831   }

   832   return best_loc;

   833 }

   834 

   835 

   836 function match_alphabet(pattern) {

   837   // Initialise the alphabet for the Bitap algorithm.

   838   var s = Object();

   839   for (var i=0; i<pattern.length; i++)

   840     s[pattern.charAt(i)] = 0;

   841   for (var i=0; i<pattern.length; i++)

   842     s[pattern.charAt(i)] |= Math.pow(2, pattern.length-i-1);

   843   return s;

   844 }

   845 

   846 

   847   //////////////////////////////////////////////////////////////////////

   848  //  Patch                                                           //

   849 //////////////////////////////////////////////////////////////////////

   850 

   851 

   852 function patch_obj() {

   853   // Constructor for a patch object.

   854   this.diffs = [];

   855   this.start1 = null;

   856   this.start2 = null;

   857   this.length1 = 0;

   858   this.length2 = 0;

   859 

   860   this.toString = function() {

   861     // Emmulate GNU diff's format.

   862     // Header: @@ -382,8 +481,9 @@

   863     // Indicies are printed as 1-based, not 0-based.

   864     var coords1, coords2;

   865     if (this.length1 == 0)

   866       coords1 = this.start1+",0";

   867     else if (this.length1 == 1)

   868       coords1 = this.start1+1;

   869     else

   870       coords1 = (this.start1+1)+","+this.length1;

   871     if (this.length2 == 0)

   872       coords2 = this.start2+",0";

   873     else if (this.length2 == 1)

   874       coords2 = this.start2+1;

   875     else

   876       coords2 = (this.start2+1)+","+this.length2;

   877     var txt = "@@ -"+coords1+" +"+coords2+" @@\n";

   878     // Escape the body of the patch with %xx notation.

   879     for (var x=0; x<this.diffs.length; x++)

   880       txt += ("- +".charAt(this.diffs[x][0]+1)) + encodeURI(this.diffs[x][1]) + "\n";

   881     return txt.replace(/%20/g, ' ');

   882   }

   883 

   884   this.text1 = function() {

   885     // Compute and return the source text (all equalities and deletions).

   886     var txt = '';

   887     for (var x=0; x<this.diffs.length; x++)

   888       if (this.diffs[x][0] == 0 || this.diffs[x][0] == -1)

   889         txt += this.diffs[x][1];

   890     return txt;

   891   }

   892 

   893   this.text2 = function() {

   894     // Compute and return the destination text (all equalities and insertions).

   895     var txt = '';

   896     for (var x=0; x<this.diffs.length; x++)

   897       if (this.diffs[x][0] == 0 || this.diffs[x][0] == 1)

   898         txt += this.diffs[x][1];

   899     return txt;

   900   }

   901 }

   902 

   903 

   904 function patch_addcontext(patch, text) {

   905   var pattern = text.substring(patch.start2, patch.start2+patch.length1);

   906   var padding = 0;

   907   // Increase the context until we're unique (but don't let the pattern expand beyond MATCH_MAXBITS).

   908   while (text.indexOf(pattern) != text.lastIndexOf(pattern) && pattern.length < MATCH_MAXBITS-PATCH_MARGIN-PATCH_MARGIN) {

   909     padding += PATCH_MARGIN;

   910     pattern = text.substring(patch.start2 - padding, patch.start2+patch.length1 + padding);

   911   }

   912   // Add one chunk for good luck.

   913   padding += PATCH_MARGIN;

   914   // Add the prefix.

   915   var prefix = text.substring(patch.start2 - padding, patch.start2);

   916   if (prefix != '')

   917     patch.diffs.unshift([0, prefix]);

   918   // Add the suffix

   919   var suffix = text.substring(patch.start2+patch.length1, patch.start2+patch.length1 + padding);

   920   if (suffix != '')

   921     patch.diffs.push([0, suffix]);

   922 

   923   // Roll back the start points.

   924   patch.start1 -= prefix.length;

   925   patch.start2 -= prefix.length;

   926   // Extend the lengths.

   927   patch.length1 += prefix.length + suffix.length;

   928   patch.length2 += prefix.length + suffix.length;

   929 }

   930 

   931 

   932 function patch_make(text1, text2, diff) {

   933   // Compute a list of patches to turn text1 into text2.

   934   // Use diff if provided, otherwise compute it ourselves.

   935   if (typeof diff == 'undefined') {

   936     diff = diff_main(text1, text2, true);

   937     if (diff.length > 2) {

   938       diff_cleanup_semantic(diff);

   939       diff_cleanup_efficiency(diff);

   940     }

   941   }

   942   if (diff.length == 0)

   943     return []; // Get rid of the null case.

   944   var patches = [];

   945   var patch = new patch_obj();

   946   var char_count1 = 0; // Number of characters into the text1 string.

   947   var char_count2 = 0; // Number of characters into the text2 string.

   948   var last_type = null;

   949   var prepatch_text = text1; // Recreate the patches to determine context info.

   950   var postpatch_text = text1;

   951   for (var x=0; x<diff.length; x++) {

   952     var diff_type = diff[x][0];

   953     var diff_text = diff[x][1];

   954 

   955     if (patch.diffs.length == 0 && diff_type != 0) {

   956       // A new patch starts here.

   957       patch.start1 = char_count1;

   958       patch.start2 = char_count2;

   959     }

   960 

   961     if (diff_type == 1) {

   962       // Insertion

   963       patch.diffs.push(diff[x]);

   964       patch.length2 += diff_text.length;

   965       postpatch_text = postpatch_text.substring(0, char_count2) + diff_text + postpatch_text.substring(char_count2);

   966     } else if (diff_type == -1) {

   967       // Deletion.

   968       patch.length1 += diff_text.length;

   969       patch.diffs.push(diff[x]);

   970       postpatch_text = postpatch_text.substring(0, char_count2) + postpatch_text.substring(char_count2 + diff_text.length);

   971     } else if (diff_type == 0 && diff_text.length <= 2*PATCH_MARGIN && patch.diffs.length != 0 && diff.length != x+1) {

   972       // Small equality inside a patch.

   973       patch.diffs.push(diff[x]);

   974       patch.length1 += diff_text.length;

   975       patch.length2 += diff_text.length;

   976     }

   977 

   978     last_type = diff_type;

   979     if (diff_type == 0 && diff_text.length >= 2*PATCH_MARGIN) {

   980       // Time for a new patch.

   981       if (patch.diffs.length != 0) {

   982         patch_addcontext(patch, prepatch_text);

   983         patches.push(patch);

   984         var patch = new patch_obj();

   985         last_type = null;

   986         prepatch_text = postpatch_text;

   987       }

   988     }

   989 

   990     // Update the current character count.

   991     if (diff_type != 1)

   992       char_count1 += diff_text.length;

   993     if (diff_type != -1)

   994       char_count2 += diff_text.length;

   995   }

   996   // Pick up the leftover patch if not empty.

   997   if (patch.diffs.length != 0) {

   998     patch_addcontext(patch, prepatch_text);

   999     patches.push(patch);

  1000   }

  1001 

  1002   return patches;

  1003 }

  1004 

  1005 

  1006 function patch_apply(patches, text) {

  1007   // Merge a set of patches onto the text.

  1008   // Return a patched text, as well as a list of true/false values indicating which patches were applied.

  1009   patch_splitmax(patches);

  1010   var results = [];

  1011   var delta = 0;

  1012   var expected_loc, start_loc;

  1013   var text1, text2;

  1014   var diff, mod, index1, index2;

  1015   for (var x=0; x<patches.length; x++) {

  1016     expected_loc = patches[x].start2 + delta;

  1017     text1 = patches[x].text1();

  1018     start_loc = match_main(text, text1, expected_loc);

  1019     if (start_loc == null) {

  1020       // No match found.  :(

  1021       results.push(false);

  1022     } else {

  1023       // Found a match.  :)

  1024       results.push(true);

  1025       delta = start_loc - expected_loc;

  1026       text2 = text.substring(start_loc, start_loc + text1.length);

  1027       if (text1 == text2) {

  1028         // Perfect match, just shove the replacement text in.

  1029         text = text.substring(0, start_loc) + patches[x].text2() + text.substring(start_loc + text1.length);

  1030       } else {

  1031         // Imperfect match.  Run a diff to get a framework of equivalent indicies.

  1032         diff = diff_main(text1, text2, false);

  1033         index1 = 0;

  1034         for (var y=0; y<patches[x].diffs.length; y++) {

  1035           mod = patches[x].diffs[y];

  1036           if (mod[0] != 0)

  1037             index2 = diff_xindex(diff, index1);

  1038           if (mod[0] == 1) // Insertion

  1039             text = text.substring(0, start_loc + index2) + mod[1] + text.substring(start_loc + index2);

  1040           else if (mod[0] == -1) // Deletion

  1041             text = text.substring(0, start_loc + index2) + text.substring(start_loc + diff_xindex(diff, index1 + mod[1].length));

  1042           if (mod[0] != -1)

  1043             index1 += mod[1].length;

  1044         }

  1045       }

  1046     }

  1047   }

  1048   return [text, results];

  1049 }

  1050 

  1051 

  1052 function patch_splitmax(patches) {

  1053   // Look through the patches and break up any which are longer than the maximum limit of the match algorithm.

  1054   var bigpatch, patch, patch_size, start1, start2, diff_type, diff_text, precontext, postcontext, empty;

  1055   for (var x=0; x<patches.length; x++) {

  1056     if (patches[x].length1 > MATCH_MAXBITS) {

  1057       bigpatch = patches[x];

  1058       // Remove the big old patch.

  1059       patches.splice(x, 1);

  1060       patch_size = MATCH_MAXBITS;

  1061       start1 = bigpatch.start1;

  1062       start2 = bigpatch.start2;

  1063       precontext = '';

  1064       while (bigpatch.diffs.length != 0) {

  1065         // Create one of several smaller patches.

  1066         patch = new patch_obj();

  1067         empty = true;

  1068         patch.start1 = start1 - precontext.length;

  1069         patch.start2 = start2 - precontext.length;

  1070         if (precontext  != '') {

  1071           patch.length1 = patch.length2 = precontext.length;

  1072           patch.diffs.push([0, precontext]);

  1073         }

  1074         while (bigpatch.diffs.length != 0 && patch.length1 < patch_size - PATCH_MARGIN) {

  1075           diff_type = bigpatch.diffs[0][0];

  1076           diff_text = bigpatch.diffs[0][1];

  1077           if (diff_type == 1) {

  1078             // Insertions are harmless.

  1079             patch.length2 += diff_text.length;

  1080             start2 += diff_text.length;

  1081             patch.diffs.push(bigpatch.diffs.shift());

  1082             empty = false;

  1083           } else {

  1084             // Deletion or equality.  Only take as much as we can stomach.

  1085             diff_text = diff_text.substring(0, patch_size - patch.length1 - PATCH_MARGIN);

  1086             patch.length1 += diff_text.length;

  1087             start1 += diff_text.length;

  1088             if (diff_type == 0) {

  1089               patch.length2 += diff_text.length;

  1090               start2 += diff_text.length;

  1091             } else {

  1092               empty = false;

  1093             }

  1094             patch.diffs.push([diff_type, diff_text]);

  1095             if (diff_text == bigpatch.diffs[0][1])

  1096               bigpatch.diffs.shift();

  1097             else

  1098               bigpatch.diffs[0][1] = bigpatch.diffs[0][1].substring(diff_text.length);

  1099           }

  1100         }

  1101         // Compute the head context for the next patch.

  1102         precontext = patch.text2();

  1103         precontext = precontext.substring(precontext.length - PATCH_MARGIN);

  1104         // Append the end context for this patch.

  1105         postcontext = bigpatch.text1().substring(0, PATCH_MARGIN);

  1106         if (postcontext  != '') {

  1107           patch.length1 += postcontext.length;

  1108           patch.length2 += postcontext.length;

  1109           if (patch.diffs.length > 0 && patch.diffs[patch.diffs.length-1][0] == 0)

  1110             patch.diffs[patch.diffs.length-1][1] += postcontext;

  1111           else

  1112             patch.diffs.push([0, postcontext]);

  1113         }

  1114         if (!empty)

  1115           patches.splice(x++, 0, patch);

  1116       }

  1117     }

  1118   }

  1119 }

  1120 

  1121 

  1122 function patch_totext(patches) {

  1123   // Take a list of patches and return a textual representation.

  1124   var text = '';

  1125   for (var x=0; x<patches.length; x++)

  1126     text += patches[x];

  1127   return text;

  1128 }

  1129 

  1130 

  1131 function patch_fromtext(text) {

  1132   // Take a textual representation of patches and return a list of patch objects.

  1133   var patches = [];

  1134   text = text.split('\n');

  1135   var patch, m, chars1, chars2, sign, line;