media/tiny_mce/plugins/devkit/jscripts/diff.js

   1 // Diff_Match_Patch v1.3\r
   2 // Computes the difference between two texts to create a patch.\r
   3 // Applies the patch onto another text, allowing for errors.\r
   4 // Copyright (C) 2006 Neil Fraser\r
   5 // http://neil.fraser.name/software/diff_match_patch/\r
   6 \r
   7 // This program is free software; you can redistribute it and/or\r
   8 // modify it under the terms of the GNU General Public License\r
   9 // as published by the Free Software Foundation.\r
  10 \r
  11 // This program is distributed in the hope that it will be useful,\r
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  14 // GNU General Public License (www.gnu.org) for more details.\r
  15 \r
  16 \r
  17 // Constants.\r
  18 // Redefine these in your program to override the defaults.\r
  19 \r
  20 // Number of seconds to map a diff before giving up.  (0 for infinity)\r
  21 var DIFF_TIMEOUT = 1.0;\r
  22 // Cost of an empty edit operation in terms of edit characters.\r
  23 var DIFF_EDIT_COST = 4;\r
  24 // Tweak the relative importance (0.0 = accuracy, 1.0 = proximity)\r
  25 var MATCH_BALANCE = 0.5;\r
  26 // At what point is no match declared (0.0 = perfection, 1.0 = very loose)\r
  27 var MATCH_THRESHOLD = 0.5;\r
  28 // The min and max cutoffs used when computing text lengths.\r
  29 var MATCH_MINLENGTH = 100;\r
  30 var MATCH_MAXLENGTH = 1000;\r
  31 // Chunk size for context length.\r
  32 var PATCH_MARGIN = 4;\r
  33 \r
  34 \r
  35   //////////////////////////////////////////////////////////////////////\r
  36  //  Diff                                                            //\r
  37 //////////////////////////////////////////////////////////////////////\r
  38 \r
  39 // The data structure representing a diff is an array of tuples:\r
  40 // [[-1, "Hello"], [1, "Goodbye"], [0, " world."]]\r
  41 // which means: delete "Hello", add "Goodbye" and keep " world."\r
  42 \r
  43 \r
  44 function diff_main(text1, text2, checklines) {\r
  45   // Find the differences between two texts.  Return an array of changes.\r
  46   // If checklines is present and false, then don't run a line-level diff first to identify the changed areas.\r
  47   // Check for equality (speedup)\r
  48   if (text1 == text2)\r
  49     return [[0, text1]];\r
  50 \r
  51   if (typeof checklines == 'undefined')\r
  52     checklines = true;\r
  53 \r
  54   var a;\r
  55   // Trim off common prefix (speedup)\r
  56   a = diff_prefix(text1, text2);\r
  57   text1 = a[0];\r
  58   text2 = a[1];\r
  59   var commonprefix = a[2];\r
  60 \r
  61   // Trim off common suffix (speedup)\r
  62   a = diff_suffix(text1, text2);\r
  63   text1 = a[0];\r
  64   text2 = a[1];\r
  65   var commonsuffix = a[2];\r
  66 \r
  67   var diff, i;\r
  68   var longtext = text1.length > text2.length ? text1 : text2;\r
  69   var shorttext = text1.length > text2.length ? text2 : text1;\r
  70 \r
  71   if (!text1) {  // Just add some text (speedup)\r
  72     diff = [[1, text2]];\r
  73   } else if (!text2) { // Just delete some text (speedup)\r
  74     diff = [[-1, text1]];\r
  75   } else if ((i = longtext.indexOf(shorttext)) != -1) {\r
  76     // Shorter text is inside the longer text (speedup)\r
  77     diff = [[1, longtext.substring(0, i)], [0, shorttext], [1, longtext.substring(i+shorttext.length)]];\r
  78     // Swap insertions for deletions if diff is reversed.\r
  79     if (text1.length > text2.length)\r
  80       diff[0][0] = diff[2][0] = -1;\r
  81   } else {\r
  82     longtext = shorttext = null; // Garbage collect\r
  83     // Check to see if the problem can be split in two.\r
  84     var hm = diff_halfmatch(text1, text2);\r
  85     if (hm) {\r
  86       // A half-match was found, sort out the return data.\r
  87       var text1_a = hm[0];\r
  88       var text1_b = hm[1];\r
  89       var text2_a = hm[2];\r
  90       var text2_b = hm[3];\r
  91       var mid_common = hm[4];\r
  92       // Send both pairs off for separate processing.\r
  93       var diff_a = diff_main(text1_a, text2_a, checklines);\r
  94       var diff_b = diff_main(text1_b, text2_b, checklines);\r
  95       // Merge the results.\r
  96       diff = diff_a.concat([[0, mid_common]], diff_b);\r
  97     } else {\r
  98       // Perform a real diff.\r
  99       if (checklines && text1.length + text2.length < 250)\r
 100         checklines = false; // Too trivial for the overhead.\r
 101       if (checklines) {\r
 102         // Scan the text on a line-by-line basis first.\r
 103         a = diff_lines2chars(text1, text2);\r
 104         text1 = a[0];\r
 105         text2 = a[1];\r
 106         var linearray = a[2];\r
 107       }\r
 108       diff = diff_map(text1, text2);\r
 109       if (!diff) // No acceptable result.\r
 110         diff = [[-1, text1], [1, text2]];\r
 111       if (checklines) {\r
 112         diff_chars2lines(diff, linearray); // Convert the diff back to original text.\r
 113         diff_cleanup_semantic(diff); // Eliminate freak matches (e.g. blank lines)\r
 114 \r
 115         // Rediff any replacement blocks, this time on character-by-character basis.\r
 116         diff.push([0, '']);  // Add a dummy entry at the end.\r
 117         var pointer = 0;\r
 118         var count_delete = 0;\r
 119         var count_insert = 0;\r
 120         var text_delete = '';\r
 121         var text_insert = '';\r
 122         while(pointer < diff.length) {\r
 123           if (diff[pointer][0] == 1) {\r
 124             count_insert++;\r
 125             text_insert += diff[pointer][1];\r
 126           } else if (diff[pointer][0] == -1) {\r
 127             count_delete++;\r
 128             text_delete += diff[pointer][1];\r
 129           } else {  // Upon reaching an equality, check for prior redundancies.\r
 130             if (count_delete >= 1 && count_insert >= 1) {\r
 131               // Delete the offending records and add the merged ones.\r
 132               a = diff_main(text_delete, text_insert, false);\r
 133               diff.splice(pointer - count_delete - count_insert, count_delete + count_insert);\r
 134               pointer = pointer - count_delete - count_insert;\r
 135               for (i=a.length-1; i>=0; i--)\r
 136                 diff.splice(pointer, 0, a[i]);\r
 137               pointer = pointer + a.length;\r
 138             }\r
 139             count_insert = 0;\r
 140             count_delete = 0;\r
 141             text_delete = '';\r
 142             text_insert = '';\r
 143           }\r
 144           pointer++;\r
 145         }\r
 146         diff.pop();  // Remove the dummy entry at the end.\r
 147 \r
 148       }\r
 149     }\r
 150   }\r
 151 \r
 152   if (commonprefix)\r
 153     diff.unshift([0, commonprefix]);\r
 154   if (commonsuffix)\r
 155     diff.push([0, commonsuffix]);\r
 156   diff_cleanup_merge(diff);\r
 157   return diff;\r
 158 }\r
 159 \r
 160 \r
 161 function diff_lines2chars(text1, text2) {\r
 162   // Split text into an array of strings.\r
 163   // Reduce the texts to a string of hashes where each character represents one line.\r
 164   var linearray = new Array();  // linearray[4] == "Hello\n"\r
 165   var linehash = new Object();  // linehash["Hello\n"] == 4\r
 166 \r
 167   // "\x00" is a valid JavaScript character, but the Venkman debugger doesn't like it (bug 335098)\r
 168   // So we'll insert a junk entry to avoid generating a null character.\r
 169   linearray.push('');\r
 170 \r
 171   function diff_lines2chars_munge(text) {\r
 172     // My first ever closure!\r
 173     var i, line;\r
 174     var chars = '';\r
 175     while (text) {\r
 176       i = text.indexOf('\n');\r
 177       if (i == -1)\r
 178         i = text.length;\r
 179       line = text.substring(0, i+1);\r
 180       text = text.substring(i+1);\r
 181       if (linehash.hasOwnProperty ? linehash.hasOwnProperty(line) : (linehash[line] !== undefined)) {\r
 182         chars += String.fromCharCode(linehash[line]);\r
 183       } else {\r
 184         linearray.push(line);\r
 185         linehash[line] = linearray.length - 1;\r
 186         chars += String.fromCharCode(linearray.length - 1);\r
 187       }\r
 188     }\r
 189     return chars;\r
 190   }\r
 191 \r
 192   var chars1 = diff_lines2chars_munge(text1);\r
 193   var chars2 = diff_lines2chars_munge(text2);\r
 194   return [chars1, chars2, linearray];\r
 195 }\r
 196 \r
 197 \r
 198 function diff_chars2lines(diff, linearray) {\r
 199   // Rehydrate the text in a diff from a string of line hashes to real lines of text.\r
 200   var chars, text;\r
 201   for (var x=0; x<diff.length; x++) {\r
 202     chars = diff[x][1];\r
 203     text = '';\r
 204     for (var y=0; y<chars.length; y++)\r
 205       text += linearray[chars.charCodeAt(y)];\r
 206     diff[x][1] = text;\r
 207   }\r
 208 }\r
 209 \r
 210 \r
 211 function diff_map(text1, text2) {\r
 212   // Explore the intersection points between the two texts.\r
 213   var now = new Date();\r
 214   var ms_end = now.getTime() + DIFF_TIMEOUT * 1000; // Don't run for too long.\r
 215   var max = (text1.length + text2.length) / 2;\r
 216   var v_map1 = new Array();\r
 217   var v_map2 = new Array();\r
 218   var v1 = new Object();\r
 219   var v2 = new Object();\r
 220   v1[1] = 0;\r
 221   v2[1] = 0;\r
 222   var x, y;\r
 223   var footstep; // Used to track overlapping paths.\r
 224   var footsteps = new Object();\r
 225   var done = false;\r
 226   var hasOwnProperty = !!(footsteps.hasOwnProperty);\r
 227   // If the total number of characters is odd, then the front path will collide with the reverse path.\r
 228   var front = (text1.length + text2.length) % 2;\r
 229   for (var d=0; d<max; d++) {\r
 230     now = new Date();\r
 231     if (DIFF_TIMEOUT > 0 && now.getTime() > ms_end) // Timeout reached\r
 232       return null;\r
 233 \r
 234     // Walk the front path one step.\r
 235     v_map1[d] = new Object();\r
 236     for (var k=-d; k<=d; k+=2) {\r
 237       if (k == -d || k != d && v1[k-1] < v1[k+1])\r
 238         x = v1[k+1];\r
 239       else\r
 240         x = v1[k-1]+1;\r
 241       y = x - k;\r
 242       footstep = x+","+y;\r
 243       if (front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))\r
 244         done = true;\r
 245       if (!front)\r
 246         footsteps[footstep] = d;\r
 247       while (!done && x < text1.length && y < text2.length && text1.charAt(x) == text2.charAt(y)) {\r
 248         x++; y++;\r
 249         footstep = x+","+y;\r
 250         if (front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))\r
 251           done = true;\r
 252         if (!front)\r
 253           footsteps[footstep] = d;\r
 254       }\r
 255       v1[k] = x;\r
 256       v_map1[d][x+","+y] = true;\r
 257       if (done) {\r
 258         // Front path ran over reverse path.\r
 259         v_map2 = v_map2.slice(0, footsteps[footstep]+1);\r
 260         var a = diff_path1(v_map1, text1.substring(0, x), text2.substring(0, y));\r
 261         return a.concat(diff_path2(v_map2, text1.substring(x), text2.substring(y)));\r
 262       }\r
 263     }\r
 264 \r
 265     // Walk the reverse path one step.\r
 266     v_map2[d] = new Object();\r
 267     for (var k=-d; k<=d; k+=2) {\r
 268       if (k == -d || k != d && v2[k-1] < v2[k+1])\r
 269         x = v2[k+1];\r
 270       else\r
 271         x = v2[k-1]+1;\r
 272       y = x - k;\r
 273       footstep = (text1.length-x)+","+(text2.length-y);\r
 274       if (!front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))\r
 275         done = true;\r
 276       if (front)\r
 277         footsteps[footstep] = d;\r
 278       while (!done && x < text1.length && y < text2.length && text1.charAt(text1.length-x-1) == text2.charAt(text2.length-y-1)) {\r
 279         x++; y++;\r
 280         footstep = (text1.length-x)+","+(text2.length-y);\r
 281         if (!front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))\r
 282           done = true;\r
 283         if (front)\r
 284           footsteps[footstep] = d;\r
 285       }\r
 286       v2[k] = x;\r
 287       v_map2[d][x+","+y] = true;\r
 288       if (done) {\r
 289         // Reverse path ran over front path.\r
 290         v_map1 = v_map1.slice(0, footsteps[footstep]+1);\r
 291         var a = diff_path1(v_map1, text1.substring(0, text1.length-x), text2.substring(0, text2.length-y));\r
 292         return a.concat(diff_path2(v_map2, text1.substring(text1.length-x), text2.substring(text2.length-y)));\r
 293       }\r
 294     }\r
 295   }\r
 296   // Number of diffs equals number of characters, no commonality at all.\r
 297   return null;\r
 298 }\r
 299 \r
 300 \r
 301 function diff_path1(v_map, text1, text2) {\r
 302   // Work from the middle back to the start to determine the path.\r
 303   var path = [];\r
 304   var x = text1.length;\r
 305   var y = text2.length;\r
 306   var last_op = null;\r
 307   for (var d=v_map.length-2; d>=0; d--) {\r
 308     while(1) {\r
 309       if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty((x-1)+","+y) : (v_map[d][(x-1)+","+y] !== undefined)) {\r
 310         x--;\r
 311         if (last_op === -1)\r
 312           path[0][1] = text1.charAt(x) + path[0][1];\r
 313         else\r
 314           path.unshift([-1, text1.charAt(x)]);\r
 315         last_op = -1;\r
 316         break;\r
 317       } else if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty(x+","+(y-1)) : (v_map[d][x+","+(y-1)] !== undefined)) {\r
 318         y--;\r
 319         if (last_op === 1)\r
 320           path[0][1] = text2.charAt(y) + path[0][1];\r
 321         else\r
 322           path.unshift([1, text2.charAt(y)]);\r
 323         last_op = 1;\r
 324         break;\r
 325       } else {\r
 326         x--;\r
 327         y--;\r
 328         //if (text1.charAt(x) != text2.charAt(y))\r
 329         //  return alert("No diagonal.  Can't happen. (diff_path1)");\r
 330         if (last_op === 0)\r
 331           path[0][1] = text1.charAt(x) + path[0][1];\r
 332         else\r
 333           path.unshift([0, text1.charAt(x)]);\r
 334         last_op = 0;\r
 335       }\r
 336     }\r
 337   }\r
 338   return path;\r
 339 }\r
 340 \r
 341 \r
 342 function diff_path2(v_map, text1, text2) {\r
 343   // Work from the middle back to the end to determine the path.\r
 344   var path = [];\r
 345   var x = text1.length;\r
 346   var y = text2.length;\r
 347   var last_op = null;\r
 348   for (var d=v_map.length-2; d>=0; d--) {\r
 349     while(1) {\r
 350       if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty((x-1)+","+y) : (v_map[d][(x-1)+","+y] !== undefined)) {\r
 351         x--;\r
 352         if (last_op === -1)\r
 353           path[path.length-1][1] += text1.charAt(text1.length-x-1);\r
 354         else\r
 355           path.push([-1, text1.charAt(text1.length-x-1)]);\r
 356         last_op = -1;\r
 357         break;\r
 358       } else if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty(x+","+(y-1)) : (v_map[d][x+","+(y-1)] !== undefined)) {\r
 359         y--;\r
 360         if (last_op === 1)\r
 361           path[path.length-1][1] += text2.charAt(text2.length-y-1);\r
 362         else\r
 363           path.push([1, text2.charAt(text2.length-y-1)]);\r
 364         last_op = 1;\r
 365         break;\r
 366       } else {\r
 367         x--;\r
 368         y--;\r
 369         //if (text1.charAt(text1.length-x-1) != text2.charAt(text2.length-y-1))\r
 370         //  return alert("No diagonal.  Can't happen. (diff_path2)");\r
 371         if (last_op === 0)\r
 372           path[path.length-1][1] += text1.charAt(text1.length-x-1);\r
 373         else\r
 374           path.push([0, text1.charAt(text1.length-x-1)]);\r
 375         last_op = 0;\r
 376       }\r
 377     }\r
 378   }\r
 379   return path;\r
 380 }\r
 381 \r
 382 \r
 383 function diff_prefix(text1, text2) {\r
 384   // Trim off common prefix\r
 385   var pointermin = 0;\r
 386   var pointermax = Math.min(text1.length, text2.length);\r
 387   var pointermid = pointermax;\r
 388   while(pointermin < pointermid) {\r
 389     if (text1.substring(0, pointermid) == text2.substring(0, pointermid))\r
 390       pointermin = pointermid;\r
 391     else\r
 392       pointermax = pointermid;\r
 393     pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);\r
 394   }\r
 395   var commonprefix = text1.substring(0, pointermid);\r
 396   text1 = text1.substring(pointermid);\r
 397   text2 = text2.substring(pointermid);\r
 398   return [text1, text2, commonprefix];\r
 399 }\r
 400 \r
 401 \r
 402 function diff_suffix(text1, text2) {\r
 403   // Trim off common suffix\r
 404   var pointermin = 0;\r
 405   var pointermax = Math.min(text1.length, text2.length);\r
 406   var pointermid = pointermax;\r
 407   while(pointermin < pointermid) {\r
 408     if (text1.substring(text1.length-pointermid) == text2.substring(text2.length-pointermid))\r
 409       pointermin = pointermid;\r
 410     else\r
 411       pointermax = pointermid;\r
 412     pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);\r
 413   }\r
 414   var commonsuffix = text1.substring(text1.length-pointermid);\r
 415   text1 = text1.substring(0, text1.length-pointermid);\r
 416   text2 = text2.substring(0, text2.length-pointermid);\r
 417   return [text1, text2, commonsuffix];\r
 418 }\r
 419 \r
 420 \r
 421 function diff_halfmatch(text1, text2) {\r
 422   // Do the two texts share a substring which is at least half the length of the longer text?\r
 423   var longtext = text1.length > text2.length ? text1 : text2;\r
 424   var shorttext = text1.length > text2.length ? text2 : text1;\r
 425   if (longtext.length < 10 || shorttext.length < 1)\r
 426     return null; // Pointless.\r
 427 \r
 428   function diff_halfmatch_i(longtext, shorttext, i) {\r
 429     // Start with a 1/4 length substring at position i as a seed.\r
 430     var seed = longtext.substring(i, i+Math.floor(longtext.length/4));\r
 431     var j = -1;\r
 432     var best_common = '';\r
 433     var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;\r
 434     while ((j = shorttext.indexOf(seed, j+1)) != -1) {\r
 435       var my_prefix = diff_prefix(longtext.substring(i), shorttext.substring(j));\r
 436       var my_suffix = diff_suffix(longtext.substring(0, i), shorttext.substring(0, j));\r
 437       if (best_common.length < (my_suffix[2] + my_prefix[2]).length) {\r
 438         best_common = my_suffix[2] + my_prefix[2];\r
 439         best_longtext_a = my_suffix[0];\r
 440         best_longtext_b = my_prefix[0];\r
 441         best_shorttext_a = my_suffix[1];\r
 442         best_shorttext_b = my_prefix[1];\r
 443       }\r
 444     }\r
 445     if (best_common.length >= longtext.length/2)\r
 446       return [best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common];\r
 447     else\r
 448       return null;\r
 449   }\r
 450 \r
 451   // First check if the second quarter is the seed for a half-match.\r
 452   var hm1 = diff_halfmatch_i(longtext, shorttext, Math.ceil(longtext.length/4));\r
 453   // Check again based on the third quarter.\r
 454   var hm2 = diff_halfmatch_i(longtext, shorttext, Math.ceil(longtext.length/2));\r
 455   var hm;\r
 456   if (!hm1 && !hm2)\r
 457     return null;\r
 458   else if (!hm2)\r
 459     hm = hm1;\r
 460   else if (!hm1)\r
 461     hm = hm2;\r
 462   else // Both matched.  Select the longest.\r
 463     hm = hm1[4].length > hm2[4].length ? hm1 : hm2;\r
 464 \r
 465   // A half-match was found, sort out the return data.\r
 466   if (text1.length > text2.length) {\r
 467     var text1_a = hm[0];\r
 468     var text1_b = hm[1];\r
 469     var text2_a = hm[2];\r
 470     var text2_b = hm[3];\r
 471   } else {\r
 472     var text2_a = hm[0];\r
 473     var text2_b = hm[1];\r
 474     var text1_a = hm[2];\r
 475     var text1_b = hm[3];\r
 476   }\r
 477   var mid_common = hm[4];\r
 478   return [text1_a, text1_b, text2_a, text2_b, mid_common];\r
 479 }\r
 480 \r
 481 \r
 482 function diff_cleanup_semantic(diff) {\r
 483   // Reduce the number of edits by eliminating semantically trivial equalities.\r
 484   var changes = false;\r
 485   var equalities = []; // Stack of indices where equalities are found.\r
 486   var lastequality = null; // Always equal to equalities[equalities.length-1][1]\r
 487   var pointer = 0; // Index of current position.\r
 488   var length_changes1 = 0; // Number of characters that changed prior to the equality.\r
 489   var length_changes2 = 0; // Number of characters that changed after the equality.\r
 490   while (pointer < diff.length) {\r
 491     if (diff[pointer][0] == 0) { // equality found\r
 492       equalities.push(pointer);\r
 493       length_changes1 = length_changes2;\r
 494       length_changes2 = 0;\r
 495       lastequality = diff[pointer][1];\r
 496     } else { // an insertion or deletion\r
 497       length_changes2 += diff[pointer][1].length;\r
 498       if (lastequality != null && (lastequality.length <= length_changes1) && (lastequality.length <= length_changes2)) {\r
 499         //alert("Splitting: '"+lastequality+"'");\r
 500         diff.splice(equalities[equalities.length-1], 0, [-1, lastequality]); // Duplicate record\r
 501         diff[equalities[equalities.length-1]+1][0] = 1; // Change second copy to insert.\r
 502         equalities.pop();  // Throw away the equality we just deleted;\r
 503         equalities.pop();  // Throw away the previous equality;\r
 504         pointer = equalities.length ? equalities[equalities.length-1] : -1;\r
 505         length_changes1 = 0; // Reset the counters.\r
 506         length_changes2 = 0;\r
 507         lastequality = null;\r
 508         changes = true;\r
 509       }\r
 510     }\r
 511     pointer++;\r
 512   }\r
 513 \r
 514   if (changes)\r
 515     diff_cleanup_merge(diff);\r
 516 }\r
 517 \r
 518 \r
 519 function diff_cleanup_efficiency(diff) {\r
 520   // Reduce the number of edits by eliminating operationally trivial equalities.\r
 521   var changes = false;\r
 522   var equalities = []; // Stack of indices where equalities are found.\r
 523   var lastequality = ''; // Always equal to equalities[equalities.length-1][1]\r
 524   var pointer = 0; // Index of current position.\r
 525   var pre_ins = false; // Is there an insertion operation before the last equality.\r
 526   var pre_del = false; // Is there an deletion operation before the last equality.\r
 527   var post_ins = false; // Is there an insertion operation after the last equality.\r
 528   var post_del = false; // Is there an deletion operation after the last equality.\r
 529   while (pointer < diff.length) {\r
 530     if (diff[pointer][0] == 0) { // equality found\r
 531       if (diff[pointer][1].length < DIFF_EDIT_COST && (post_ins || post_del)) {\r
 532         // Candidate found.\r
 533         equalities.push(pointer);\r
 534         pre_ins = post_ins;\r
 535         pre_del = post_del;\r
 536         lastequality = diff[pointer][1];\r
 537       } else {\r
 538         // Not a candidate, and can never become one.\r
 539         equalities = [];\r
 540         lastequality = '';\r
 541       }\r
 542       post_ins = post_del = false;\r
 543     } else { // an insertion or deletion\r
 544       if (diff[pointer][0] == -1)\r
 545         post_del = true;\r
 546       else\r
 547         post_ins = true;\r
 548       // Five types to be split:\r
 549       // <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>\r
 550       // <ins>A</ins>X<ins>C</ins><del>D</del>\r
 551       // <ins>A</ins><del>B</del>X<ins>C</ins>\r
 552       // <ins>A</del>X<ins>C</ins><del>D</del>\r
 553       // <ins>A</ins><del>B</del>X<del>C</del>\r
 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))) {\r
 555         //alert("Splitting: '"+lastequality+"'");\r
 556         diff.splice(equalities[equalities.length-1], 0, [-1, lastequality]); // Duplicate record\r
 557         diff[equalities[equalities.length-1]+1][0] = 1; // Change second copy to insert.\r
 558         equalities.pop();  // Throw away the equality we just deleted;\r
 559         lastequality = '';\r
 560         if (pre_ins && pre_del) {\r
 561           // No changes made which could affect previous entry, keep going.\r
 562           post_ins = post_del = true;\r
 563           equalities = [];\r
 564         } else {\r
 565           equalities.pop();  // Throw away the previous equality;\r
 566           pointer = equalities.length ? equalities[equalities.length-1] : -1;\r
 567           post_ins = post_del = false;\r
 568         }\r
 569         changes = true;\r
 570       }\r
 571     }\r
 572     pointer++;\r
 573   }\r
 574 \r
 575   if (changes)\r
 576     diff_cleanup_merge(diff);\r
 577 }\r
 578 \r
 579 \r
 580 function diff_cleanup_merge(diff) {\r
 581   // Reorder and merge like edit sections.  Merge equalities.\r
 582   // Any edit section can move as long as it doesn't cross an equality.\r
 583   diff.push([0, '']);  // Add a dummy entry at the end.\r
 584   var pointer = 0;\r
 585   var count_delete = 0;\r
 586   var count_insert = 0;\r
 587   var text_delete = '';\r
 588   var text_insert = '';\r
 589   var record_insert, record_delete;\r
 590   var my_xfix;\r
 591   while(pointer < diff.length) {\r
 592     if (diff[pointer][0] == 1) {\r
 593       count_insert++;\r
 594       text_insert += diff[pointer][1];\r
 595       pointer++;\r
 596     } else if (diff[pointer][0] == -1) {\r
 597       count_delete++;\r
 598       text_delete += diff[pointer][1];\r
 599       pointer++;\r
 600     } else {  // Upon reaching an equality, check for prior redundancies.\r
 601       if (count_delete > 1 || count_insert > 1) {\r
 602         if (count_delete > 1 && count_insert > 1) {\r
 603           // Factor out any common prefixies.\r
 604           my_xfix = diff_prefix(text_insert, text_delete);\r
 605           if (my_xfix[2] != '') {\r
 606             if ((pointer - count_delete - count_insert) > 0 && diff[pointer - count_delete - count_insert - 1][0] == 0) {\r
 607               text_insert = my_xfix[0];\r
 608               text_delete = my_xfix[1];\r
 609               diff[pointer - count_delete - count_insert - 1][1] += my_xfix[2];\r
 610             }\r
 611           }\r
 612           // Factor out any common suffixies.\r
 613           my_xfix = diff_suffix(text_insert, text_delete);\r
 614           if (my_xfix[2] != '') {\r
 615             text_insert = my_xfix[0];\r
 616             text_delete = my_xfix[1];\r
 617             diff[pointer][1] = my_xfix[2] + diff[pointer][1];\r
 618           }\r
 619         }\r
 620         // Delete the offending records and add the merged ones.\r
 621         if (count_delete == 0)\r
 622           diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [1, text_insert]);\r
 623         else if (count_insert == 0)\r
 624           diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [-1, text_delete]);\r
 625         else\r
 626           diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [-1, text_delete], [1, text_insert]);\r
 627         pointer = pointer - count_delete - count_insert + (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;\r
 628       } else if (pointer != 0 && diff[pointer-1][0] == 0) {\r
 629         // Merge this equality with the previous one.\r
 630         diff[pointer-1][1] += diff[pointer][1];\r
 631         diff.splice(pointer, 1);\r
 632       } else {\r
 633         pointer++;\r
 634       }\r
 635       count_insert = 0;\r
 636       count_delete = 0;\r
 637       text_delete = '';\r
 638       text_insert = '';\r
 639     }\r
 640   }\r
 641   if (diff[diff.length-1][1] == '')\r
 642     diff.pop();  // Remove the dummy entry at the end.\r
 643 }\r
 644 \r
 645 \r
 646 function diff_addindex(diff) {\r
 647   // Add an index to each tuple, represents where the tuple is located in text2.\r
 648   // e.g. [[-1, 'h', 0], [1, 'c', 0], [0, 'at', 1]]\r
 649   var i = 0;\r
 650   for (var x=0; x<diff.length; x++) {\r
 651     diff[x].push(i);\r
 652     if (diff[x][0] != -1)\r
 653       i += diff[x][1].length;\r
 654   }\r
 655 }\r
 656 \r
 657 \r
 658 function diff_xindex(diff, loc) {\r
 659   // loc is a location in text1, compute and return the equivalent location in text2.\r
 660   // e.g. "The cat" vs "The big cat", 1->1, 5->8\r
 661   var chars1 = 0;\r
 662   var chars2 = 0;\r
 663   var last_chars1 = 0;\r
 664   var last_chars2 = 0;\r
 665   for (var x=0; x<diff.length; x++) {\r
 666     if (diff[x][0] != 1) // Equality or deletion.\r
 667       chars1 += diff[x][1].length;\r
 668     if (diff[x][0] != -1) // Equality or insertion.\r
 669       chars2 += diff[x][1].length;\r
 670     if (chars1 > loc) // Overshot the location.\r
 671       break;\r
 672     last_chars1 = chars1;\r
 673     last_chars2 = chars2;\r
 674   }\r
 675   if (diff.length != x && diff[x][0] == -1) // The location was deleted.\r
 676     return last_chars2;\r
 677   // Add the remaining character length.\r
 678   return last_chars2 + (loc - last_chars1);\r
 679 }\r
 680 \r
 681 \r
 682 function diff_prettyhtml(diff) {\r
 683   // Convert a diff array into a pretty HTML report.\r
 684   diff_addindex(diff);\r
 685   var html = '';\r
 686   for (var x=0; x<diff.length; x++) {\r
 687     var m = diff[x][0]; // Mode (-1=delete, 0=copy, 1=add)\r
 688     var t = diff[x][1]; // Text of change.\r
 689     var i = diff[x][2]; // Index of change.\r
 690     t = t.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;");\r
 691     t = t.replace(/\n/g, "&para;<BR>");\r
 692     if (m == -1)\r
 693       html += "<DEL STYLE='background:#FFE6E6;' TITLE='i="+i+"'>"+t+"</DEL>";\r
 694     else if (m == 1)\r
 695       html += "<INS STYLE='background:#E6FFE6;' TITLE='i="+i+"'>"+t+"</INS>";\r
 696     else\r
 697       html += "<SPAN TITLE='i="+i+"'>"+t+"</SPAN>";\r
 698   }\r
 699   return html;\r
 700 }\r
 701 \r
 702 \r
 703   //////////////////////////////////////////////////////////////////////\r
 704  //  Match                                                           //\r
 705 //////////////////////////////////////////////////////////////////////\r
 706 \r
 707 \r
 708 function match_getmaxbits() {\r
 709   // Compute the number of bits in an int.\r
 710   // The normal answer for JavaScript is 32.\r
 711   var maxbits = 0;\r
 712   var oldi = 1;\r
 713   var newi = 2;\r
 714   while (oldi != newi) {\r
 715     maxbits++;\r
 716     oldi = newi;\r
 717     newi = newi << 1;\r
 718   }\r
 719   return maxbits;\r
 720 }\r
 721 var MATCH_MAXBITS = match_getmaxbits();\r
 722 \r
 723 \r
 724 function match_main(text, pattern, loc) {\r
 725   // Locate the best instance of 'pattern' in 'text' near 'loc'.\r
 726   loc = Math.max(0, Math.min(loc, text.length-pattern.length));\r
 727   if (text == pattern) {\r
 728     // Shortcut (potentially not guaranteed by the algorithm)\r
 729     return 0;\r
 730   } else if (text.length == 0) {\r
 731     // Nothing to match.\r
 732     return null;\r
 733   } else if (text.substring(loc, loc + pattern.length) == pattern) {\r
 734     // Perfect match at the perfect spot!  (Includes case of null pattern)\r
 735     return loc;\r
 736   } else {\r
 737     // Do a fuzzy compare.\r
 738     var match = match_bitap(text, pattern, loc);\r
 739     return match;\r
 740   }\r
 741 }\r
 742 \r
 743 \r
 744 function match_bitap(text, pattern, loc) {\r
 745   // Locate the best instance of 'pattern' in 'text' near 'loc' using the Bitap algorithm.\r
 746   if (pattern.length > MATCH_MAXBITS)\r
 747     return alert("Pattern too long for this browser.");\r
 748 \r
 749   // Initialise the alphabet.\r
 750   var s = match_alphabet(pattern);\r
 751 \r
 752   var score_text_length = text.length;\r
 753   // Coerce the text length between reasonable maximums and minimums.\r
 754   score_text_length = Math.max(score_text_length, MATCH_MINLENGTH);\r
 755   score_text_length = Math.min(score_text_length, MATCH_MAXLENGTH);\r
 756 \r
 757   function match_bitap_score (e, x) {\r
 758     // Compute and return the score for a match with e errors and x location.\r
 759     var d = Math.abs(loc-x);\r
 760     return (e / pattern.length / MATCH_BALANCE) + (d / score_text_length / (1.0 - MATCH_BALANCE));\r
 761   }\r
 762 \r
 763   // Highest score beyond which we give up.\r
 764   var score_threshold = MATCH_THRESHOLD;\r
 765   // Is there a nearby exact match? (speedup)\r
 766   var best_loc = text.indexOf(pattern, loc);\r
 767   if (best_loc != -1)\r
 768     score_threshold = Math.min(match_bitap_score(0, best_loc), score_threshold);\r
 769   // What about in the other direction? (speedup)\r
 770   best_loc = text.lastIndexOf(pattern, loc+pattern.length);\r
 771   if (best_loc != -1)\r
 772     score_threshold = Math.min(match_bitap_score(0, best_loc), score_threshold);\r
 773 \r
 774   // Initialise the bit arrays.\r
 775   var r = Array();\r
 776   var d = -1;\r
 777   var matchmask = Math.pow(2, pattern.length-1);\r
 778   best_loc = null;\r
 779 \r
 780   var bin_min, bin_mid;\r
 781   var bin_max = Math.max(loc+loc, text.length);\r
 782   var last_rd;\r
 783   for (var d=0; d<pattern.length; d++) {\r
 784     // Scan for the best match; each iteration allows for one more error.\r
 785     var rd = Array(text.length);\r
 786 \r
 787     // Run a binary search to determine how far from 'loc' we can stray at this error level.\r
 788     bin_min = loc;\r
 789     bin_mid = bin_max;\r
 790     while(bin_min < bin_mid) {\r
 791       if (match_bitap_score(d, bin_mid) < score_threshold)\r
 792         bin_min = bin_mid;\r
 793       else\r
 794         bin_max = bin_mid;\r
 795       bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min);\r
 796     }\r
 797     bin_max = bin_mid; // Use the result from this iteration as the maximum for the next.\r
 798     var start = Math.max(0, loc - (bin_mid - loc) - 1);\r
 799     var finish = Math.min(text.length-1, pattern.length + bin_mid);\r
 800 \r
 801     if (text.charAt(finish) == pattern.charAt(pattern.length-1))\r
 802       rd[finish] = Math.pow(2, d+1)-1;\r
 803     else\r
 804       rd[finish] = Math.pow(2, d)-1;\r
 805     for (var j=finish-1; j>=start; j--) {\r
 806       // The alphabet (s) is a sparse hash, so the following lines generate warnings.\r
 807       if (d == 0) // First pass: exact match.\r
 808         rd[j] = ((rd[j+1] << 1) | 1) & s[text.charAt(j)];\r
 809       else // Subsequent passes: fuzzy match.\r
 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];\r
 811       if (rd[j] & matchmask) {\r
 812         var score = match_bitap_score(d, j);\r
 813         // This match will almost certainly be better than any existing match.  But check anyway.\r
 814         if (score <= score_threshold) {\r
 815           // Told you so.\r
 816           score_threshold = score;\r
 817           best_loc = j;\r
 818           if (j > loc) {\r
 819             // When passing loc, don't exceed our current distance from loc.\r
 820             start = Math.max(0, loc - (j - loc));\r
 821           } else {\r
 822             // Already passed loc, downhill from here on in.\r
 823             break;\r
 824           }\r
 825         }\r
 826       }\r
 827     }\r
 828     if (match_bitap_score(d+1, loc) > score_threshold) // No hope for a (better) match at greater error levels.\r
 829       break;\r
 830     last_rd = rd;\r
 831   }\r
 832   return best_loc;\r
 833 }\r
 834 \r
 835 \r
 836 function match_alphabet(pattern) {\r
 837   // Initialise the alphabet for the Bitap algorithm.\r
 838   var s = Object();\r
 839   for (var i=0; i<pattern.length; i++)\r
 840     s[pattern.charAt(i)] = 0;\r
 841   for (var i=0; i<pattern.length; i++)\r
 842     s[pattern.charAt(i)] |= Math.pow(2, pattern.length-i-1);\r
 843   return s;\r
 844 }\r
 845 \r
 846 \r
 847   //////////////////////////////////////////////////////////////////////\r
 848  //  Patch                                                           //\r
 849 //////////////////////////////////////////////////////////////////////\r
 850 \r
 851 \r
 852 function patch_obj() {\r
 853   // Constructor for a patch object.\r
 854   this.diffs = [];\r
 855   this.start1 = null;\r
 856   this.start2 = null;\r
 857   this.length1 = 0;\r
 858   this.length2 = 0;\r
 859 \r
 860   this.toString = function() {\r
 861     // Emmulate GNU diff's format.\r
 862     // Header: @@ -382,8 +481,9 @@\r
 863     // Indicies are printed as 1-based, not 0-based.\r
 864     var coords1, coords2;\r
 865     if (this.length1 == 0)\r
 866       coords1 = this.start1+",0";\r
 867     else if (this.length1 == 1)\r
 868       coords1 = this.start1+1;\r
 869     else\r
 870       coords1 = (this.start1+1)+","+this.length1;\r
 871     if (this.length2 == 0)\r
 872       coords2 = this.start2+",0";\r
 873     else if (this.length2 == 1)\r
 874       coords2 = this.start2+1;\r
 875     else\r
 876       coords2 = (this.start2+1)+","+this.length2;\r
 877     var txt = "@@ -"+coords1+" +"+coords2+" @@\n";\r
 878     // Escape the body of the patch with %xx notation.\r
 879     for (var x=0; x<this.diffs.length; x++)\r
 880       txt += ("- +".charAt(this.diffs[x][0]+1)) + encodeURI(this.diffs[x][1]) + "\n";\r
 881     return txt.replace(/%20/g, ' ');\r
 882   }\r
 883 \r
 884   this.text1 = function() {\r
 885     // Compute and return the source text (all equalities and deletions).\r
 886     var txt = '';\r
 887     for (var x=0; x<this.diffs.length; x++)\r
 888       if (this.diffs[x][0] == 0 || this.diffs[x][0] == -1)\r
 889         txt += this.diffs[x][1];\r
 890     return txt;\r
 891   }\r
 892 \r
 893   this.text2 = function() {\r
 894     // Compute and return the destination text (all equalities and insertions).\r
 895     var txt = '';\r
 896     for (var x=0; x<this.diffs.length; x++)\r
 897       if (this.diffs[x][0] == 0 || this.diffs[x][0] == 1)\r
 898         txt += this.diffs[x][1];\r
 899     return txt;\r
 900   }\r
 901 }\r
 902 \r
 903 \r
 904 function patch_addcontext(patch, text) {\r
 905   var pattern = text.substring(patch.start2, patch.start2+patch.length1);\r
 906   var padding = 0;\r
 907   // Increase the context until we're unique (but don't let the pattern expand beyond MATCH_MAXBITS).\r
 908   while (text.indexOf(pattern) != text.lastIndexOf(pattern) && pattern.length < MATCH_MAXBITS-PATCH_MARGIN-PATCH_MARGIN) {\r
 909     padding += PATCH_MARGIN;\r
 910     pattern = text.substring(patch.start2 - padding, patch.start2+patch.length1 + padding);\r
 911   }\r
 912   // Add one chunk for good luck.\r
 913   padding += PATCH_MARGIN;\r
 914   // Add the prefix.\r
 915   var prefix = text.substring(patch.start2 - padding, patch.start2);\r
 916   if (prefix != '')\r
 917     patch.diffs.unshift([0, prefix]);\r
 918   // Add the suffix\r
 919   var suffix = text.substring(patch.start2+patch.length1, patch.start2+patch.length1 + padding);\r
 920   if (suffix != '')\r
 921     patch.diffs.push([0, suffix]);\r
 922 \r
 923   // Roll back the start points.\r
 924   patch.start1 -= prefix.length;\r
 925   patch.start2 -= prefix.length;\r
 926   // Extend the lengths.\r
 927   patch.length1 += prefix.length + suffix.length;\r
 928   patch.length2 += prefix.length + suffix.length;\r
 929 }\r
 930 \r
 931 \r
 932 function patch_make(text1, text2, diff) {\r
 933   // Compute a list of patches to turn text1 into text2.\r
 934   // Use diff if provided, otherwise compute it ourselves.\r
 935   if (typeof diff == 'undefined') {\r
 936     diff = diff_main(text1, text2, true);\r
 937     if (diff.length > 2) {\r
 938       diff_cleanup_semantic(diff);\r
 939       diff_cleanup_efficiency(diff);\r
 940     }\r
 941   }\r
 942   if (diff.length == 0)\r
 943     return []; // Get rid of the null case.\r
 944   var patches = [];\r
 945   var patch = new patch_obj();\r
 946   var char_count1 = 0; // Number of characters into the text1 string.\r
 947   var char_count2 = 0; // Number of characters into the text2 string.\r
 948   var last_type = null;\r
 949   var prepatch_text = text1; // Recreate the patches to determine context info.\r
 950   var postpatch_text = text1;\r
 951   for (var x=0; x<diff.length; x++) {\r
 952     var diff_type = diff[x][0];\r
 953     var diff_text = diff[x][1];\r
 954 \r
 955     if (patch.diffs.length == 0 && diff_type != 0) {\r
 956       // A new patch starts here.\r
 957       patch.start1 = char_count1;\r
 958       patch.start2 = char_count2;\r
 959     }\r
 960 \r
 961     if (diff_type == 1) {\r
 962       // Insertion\r
 963       patch.diffs.push(diff[x]);\r
 964       patch.length2 += diff_text.length;\r
 965       postpatch_text = postpatch_text.substring(0, char_count2) + diff_text + postpatch_text.substring(char_count2);\r
 966     } else if (diff_type == -1) {\r
 967       // Deletion.\r
 968       patch.length1 += diff_text.length;\r
 969       patch.diffs.push(diff[x]);\r
 970       postpatch_text = postpatch_text.substring(0, char_count2) + postpatch_text.substring(char_count2 + diff_text.length);\r
 971     } else if (diff_type == 0 && diff_text.length <= 2*PATCH_MARGIN && patch.diffs.length != 0 && diff.length != x+1) {\r
 972       // Small equality inside a patch.\r
 973       patch.diffs.push(diff[x]);\r
 974       patch.length1 += diff_text.length;\r
 975       patch.length2 += diff_text.length;\r
 976     }\r
 977 \r
 978     last_type = diff_type;\r
 979     if (diff_type == 0 && diff_text.length >= 2*PATCH_MARGIN) {\r
 980       // Time for a new patch.\r
 981       if (patch.diffs.length != 0) {\r
 982         patch_addcontext(patch, prepatch_text);\r
 983         patches.push(patch);\r
 984         var patch = new patch_obj();\r
 985         last_type = null;\r
 986         prepatch_text = postpatch_text;\r
 987       }\r
 988     }\r
 989 \r
 990     // Update the current character count.\r
 991     if (diff_type != 1)\r
 992       char_count1 += diff_text.length;\r
 993     if (diff_type != -1)\r
 994       char_count2 += diff_text.length;\r
 995   }\r
 996   // Pick up the leftover patch if not empty.\r
 997   if (patch.diffs.length != 0) {\r
 998     patch_addcontext(patch, prepatch_text);\r
 999     patches.push(patch);\r
1000   }\r
1001 \r
1002   return patches;\r
1003 }\r
1004 \r
1005 \r
1006 function patch_apply(patches, text) {\r
1007   // Merge a set of patches onto the text.\r
1008   // Return a patched text, as well as a list of true/false values indicating which patches were applied.\r
1009   patch_splitmax(patches);\r
1010   var results = [];\r
1011   var delta = 0;\r
1012   var expected_loc, start_loc;\r
1013   var text1, text2;\r
1014   var diff, mod, index1, index2;\r
1015   for (var x=0; x<patches.length; x++) {\r
1016     expected_loc = patches[x].start2 + delta;\r
1017     text1 = patches[x].text1();\r
1018     start_loc = match_main(text, text1, expected_loc);\r
1019     if (start_loc == null) {\r
1020       // No match found.  :(\r
1021       results.push(false);\r
1022     } else {\r
1023       // Found a match.  :)\r
1024       results.push(true);\r
1025       delta = start_loc - expected_loc;\r
1026       text2 = text.substring(start_loc, start_loc + text1.length);\r
1027       if (text1 == text2) {\r
1028         // Perfect match, just shove the replacement text in.\r
1029         text = text.substring(0, start_loc) + patches[x].text2() + text.substring(start_loc + text1.length);\r
1030       } else {\r
1031         // Imperfect match.  Run a diff to get a framework of equivalent indicies.\r
1032         diff = diff_main(text1, text2, false);\r
1033         index1 = 0;\r
1034         for (var y=0; y<patches[x].diffs.length; y++) {\r
1035           mod = patches[x].diffs[y];\r
1036           if (mod[0] != 0)\r
1037             index2 = diff_xindex(diff, index1);\r
1038           if (mod[0] == 1) // Insertion\r
1039             text = text.substring(0, start_loc + index2) + mod[1] + text.substring(start_loc + index2);\r
1040           else if (mod[0] == -1) // Deletion\r
1041             text = text.substring(0, start_loc + index2) + text.substring(start_loc + diff_xindex(diff, index1 + mod[1].length));\r
1042           if (mod[0] != -1)\r
1043             index1 += mod[1].length;\r
1044         }\r
1045       }\r
1046     }\r
1047   }\r
1048   return [text, results];\r
1049 }\r
1050 \r
1051 \r
1052 function patch_splitmax(patches) {\r
1053   // Look through the patches and break up any which are longer than the maximum limit of the match algorithm.\r
1054   var bigpatch, patch, patch_size, start1, start2, diff_type, diff_text, precontext, postcontext, empty;\r
1055   for (var x=0; x<patches.length; x++) {\r
1056     if (patches[x].length1 > MATCH_MAXBITS) {\r
1057       bigpatch = patches[x];\r
1058       // Remove the big old patch.\r
1059       patches.splice(x, 1);\r
1060       patch_size = MATCH_MAXBITS;\r
1061       start1 = bigpatch.start1;\r
1062       start2 = bigpatch.start2;\r
1063       precontext = '';\r
1064       while (bigpatch.diffs.length != 0) {\r
1065         // Create one of several smaller patches.\r
1066         patch = new patch_obj();\r
1067         empty = true;\r
1068         patch.start1 = start1 - precontext.length;\r
1069         patch.start2 = start2 - precontext.length;\r
1070         if (precontext  != '') {\r
1071           patch.length1 = patch.length2 = precontext.length;\r
1072           patch.diffs.push([0, precontext]);\r
1073         }\r
1074         while (bigpatch.diffs.length != 0 && patch.length1 < patch_size - PATCH_MARGIN) {\r
1075           diff_type = bigpatch.diffs[0][0];\r
1076           diff_text = bigpatch.diffs[0][1];\r
1077           if (diff_type == 1) {\r
1078             // Insertions are harmless.\r
1079             patch.length2 += diff_text.length;\r
1080             start2 += diff_text.length;\r
1081             patch.diffs.push(bigpatch.diffs.shift());\r
1082             empty = false;\r
1083           } else {\r
1084             // Deletion or equality.  Only take as much as we can stomach.\r
1085             diff_text = diff_text.substring(0, patch_size - patch.length1 - PATCH_MARGIN);\r
1086             patch.length1 += diff_text.length;\r
1087             start1 += diff_text.length;\r
1088             if (diff_type == 0) {\r
1089               patch.length2 += diff_text.length;\r
1090               start2 += diff_text.length;\r
1091             } else {\r
1092               empty = false;\r
1093             }\r
1094             patch.diffs.push([diff_type, diff_text]);\r
1095             if (diff_text == bigpatch.diffs[0][1])\r
1096               bigpatch.diffs.shift();\r
1097             else\r
1098               bigpatch.diffs[0][1] = bigpatch.diffs[0][1].substring(diff_text.length);\r
1099           }\r
1100         }\r
1101         // Compute the head context for the next patch.\r
1102         precontext = patch.text2();\r
1103         precontext = precontext.substring(precontext.length - PATCH_MARGIN);\r
1104         // Append the end context for this patch.\r
1105         postcontext = bigpatch.text1().substring(0, PATCH_MARGIN);\r
1106         if (postcontext  != '') {\r
1107           patch.length1 += postcontext.length;\r
1108           patch.length2 += postcontext.length;\r
1109           if (patch.diffs.length > 0 && patch.diffs[patch.diffs.length-1][0] == 0)\r
1110             patch.diffs[patch.diffs.length-1][1] += postcontext;\r
1111           else\r
1112             patch.diffs.push([0, postcontext]);\r
1113         }\r
1114         if (!empty)\r
1115           patches.splice(x++, 0, patch);\r
1116       }\r
1117     }\r
1118   }\r
1119 }\r
1120 \r
1121 \r
1122 function patch_totext(patches) {\r
1123   // Take a list of patches and return a textual representation.\r
1124   var text = '';\r
1125   for (var x=0; x<patches.length; x++)\r
1126     text += patches[x];\r
1127   return text;\r
1128 }\r
1129 \r
1130 \r
1131 function patch_fromtext(text) {\r
1132   // Take a textual representation of patches and return a list of patch objects.\r
1133   var patches = [];\r
1134   text = text.split('\n');\r
1135   var patch, m, chars1, chars2, sign, line;\r
1136   while (text.length != 0) {\r
1137     m = text[0].match(/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/);\r
1138     if (!m)\r
1139       return alert("Invalid patch string:\n"+text[0]);\r
1140     patch = new patch_obj();\r
1141     patches.push(patch);\r
1142     patch.start1 = parseInt(m[1]);\r
1143     if (m[2] == '') {\r
1144       patch.start1--;\r
1145       patch.length1 = 1;\r
1146     } else if (m[2] == '0') {\r
1147       patch.length1 = 0;\r
1148     } else {\r
1149       patch.start1--;\r
1150       patch.length1 = parseInt(m[2]);\r
1151     }\r
1152 \r
1153     patch.start2 = parseInt(m[3]);\r
1154     if (m[4] == '') {\r
1155       patch.start2--;\r
1156       patch.length2 = 1;\r
1157     } else if (m[4] == '0') {\r
1158       patch.length2 = 0;\r
1159     } else {\r
1160       patch.start2--;\r
1161       patch.length2 = parseInt(m[4]);\r
1162     }\r
1163     text.shift();\r
1164 \r
1165     while (text.length != 0) {\r
1166       sign = text[0].charAt(0);\r
1167       line = decodeURIComponent(text[0].substring(1));\r
1168       if (sign == '-') {\r
1169         // Deletion.\r
1170         patch.diffs.push([-1, line]);\r
1171       } else if (sign == '+') {\r
1172         // Insertion.\r
1173         patch.diffs.push([1, line]);\r
1174       } else if (sign == ' ') {\r
1175         // Minor equality.\r
1176         patch.diffs.push([0, line]);\r
1177       } else if (sign == '@') {\r
1178         // Start of next patch.\r
1179         break;\r
1180       } else if (sign == '') {\r
1181         // Blank line?  Whatever.\r
1182       } else {\r
1183         // WTF?\r
1184         return alert("Invalid patch mode: '"+sign+"'\n"+line);\r
1185       }\r
1186       text.shift();\r
1187     }\r
1188   }\r
1189   return patches;\r
1190 }\r
1191 \r
1192 // EOF\r