includes/clientside/tinymce/plugins/devkit/jscripts/diff.js
changeset 335 67bd3121a12e
parent 334 c72b545f1304
child 336 bfa2e9c23f03
equal deleted inserted replaced
334:c72b545f1304 335:67bd3121a12e
     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;
       
  1136   while (text.length != 0) {
       
  1137     m = text[0].match(/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/);
       
  1138     if (!m)
       
  1139       return alert("Invalid patch string:\n"+text[0]);
       
  1140     patch = new patch_obj();
       
  1141     patches.push(patch);
       
  1142     patch.start1 = parseInt(m[1]);
       
  1143     if (m[2] == '') {
       
  1144       patch.start1--;
       
  1145       patch.length1 = 1;
       
  1146     } else if (m[2] == '0') {
       
  1147       patch.length1 = 0;
       
  1148     } else {
       
  1149       patch.start1--;
       
  1150       patch.length1 = parseInt(m[2]);
       
  1151     }
       
  1152 
       
  1153     patch.start2 = parseInt(m[3]);
       
  1154     if (m[4] == '') {
       
  1155       patch.start2--;
       
  1156       patch.length2 = 1;
       
  1157     } else if (m[4] == '0') {
       
  1158       patch.length2 = 0;
       
  1159     } else {
       
  1160       patch.start2--;
       
  1161       patch.length2 = parseInt(m[4]);
       
  1162     }
       
  1163     text.shift();
       
  1164 
       
  1165     while (text.length != 0) {
       
  1166       sign = text[0].charAt(0);
       
  1167       line = decodeURIComponent(text[0].substring(1));
       
  1168       if (sign == '-') {
       
  1169         // Deletion.
       
  1170         patch.diffs.push([-1, line]);
       
  1171       } else if (sign == '+') {
       
  1172         // Insertion.
       
  1173         patch.diffs.push([1, line]);
       
  1174       } else if (sign == ' ') {
       
  1175         // Minor equality.
       
  1176         patch.diffs.push([0, line]);
       
  1177       } else if (sign == '@') {
       
  1178         // Start of next patch.
       
  1179         break;
       
  1180       } else if (sign == '') {
       
  1181         // Blank line?  Whatever.
       
  1182       } else {
       
  1183         // WTF?
       
  1184         return alert("Invalid patch mode: '"+sign+"'\n"+line);
       
  1185       }
       
  1186       text.shift();
       
  1187     }
       
  1188   }
       
  1189   return patches;
       
  1190 }
       
  1191 
       
  1192 // EOF