--- /dev/null
+// Diff_Match_Patch v1.3\r
+// Computes the difference between two texts to create a patch.\r
+// Applies the patch onto another text, allowing for errors.\r
+// Copyright (C) 2006 Neil Fraser\r
+// http://neil.fraser.name/software/diff_match_patch/\r
+\r
+// This program is free software; you can redistribute it and/or\r
+// modify it under the terms of the GNU General Public License\r
+// as published by the Free Software Foundation.\r
+\r
+// This program is distributed in the hope that it will be useful,\r
+// but WITHOUT ANY WARRANTY; without even the implied warranty of\r
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
+// GNU General Public License (www.gnu.org) for more details.\r
+\r
+\r
+// Constants.\r
+// Redefine these in your program to override the defaults.\r
+\r
+// Number of seconds to map a diff before giving up. (0 for infinity)\r
+var DIFF_TIMEOUT = 1.0;\r
+// Cost of an empty edit operation in terms of edit characters.\r
+var DIFF_EDIT_COST = 4;\r
+// Tweak the relative importance (0.0 = accuracy, 1.0 = proximity)\r
+var MATCH_BALANCE = 0.5;\r
+// At what point is no match declared (0.0 = perfection, 1.0 = very loose)\r
+var MATCH_THRESHOLD = 0.5;\r
+// The min and max cutoffs used when computing text lengths.\r
+var MATCH_MINLENGTH = 100;\r
+var MATCH_MAXLENGTH = 1000;\r
+// Chunk size for context length.\r
+var PATCH_MARGIN = 4;\r
+\r
+\r
+ //////////////////////////////////////////////////////////////////////\r
+ // Diff //\r
+//////////////////////////////////////////////////////////////////////\r
+\r
+// The data structure representing a diff is an array of tuples:\r
+// [[-1, "Hello"], [1, "Goodbye"], [0, " world."]]\r
+// which means: delete "Hello", add "Goodbye" and keep " world."\r
+\r
+\r
+function diff_main(text1, text2, checklines) {\r
+ // Find the differences between two texts. Return an array of changes.\r
+ // If checklines is present and false, then don't run a line-level diff first to identify the changed areas.\r
+ // Check for equality (speedup)\r
+ if (text1 == text2)\r
+ return [[0, text1]];\r
+\r
+ if (typeof checklines == 'undefined')\r
+ checklines = true;\r
+\r
+ var a;\r
+ // Trim off common prefix (speedup)\r
+ a = diff_prefix(text1, text2);\r
+ text1 = a[0];\r
+ text2 = a[1];\r
+ var commonprefix = a[2];\r
+\r
+ // Trim off common suffix (speedup)\r
+ a = diff_suffix(text1, text2);\r
+ text1 = a[0];\r
+ text2 = a[1];\r
+ var commonsuffix = a[2];\r
+\r
+ var diff, i;\r
+ var longtext = text1.length > text2.length ? text1 : text2;\r
+ var shorttext = text1.length > text2.length ? text2 : text1;\r
+\r
+ if (!text1) { // Just add some text (speedup)\r
+ diff = [[1, text2]];\r
+ } else if (!text2) { // Just delete some text (speedup)\r
+ diff = [[-1, text1]];\r
+ } else if ((i = longtext.indexOf(shorttext)) != -1) {\r
+ // Shorter text is inside the longer text (speedup)\r
+ diff = [[1, longtext.substring(0, i)], [0, shorttext], [1, longtext.substring(i+shorttext.length)]];\r
+ // Swap insertions for deletions if diff is reversed.\r
+ if (text1.length > text2.length)\r
+ diff[0][0] = diff[2][0] = -1;\r
+ } else {\r
+ longtext = shorttext = null; // Garbage collect\r
+ // Check to see if the problem can be split in two.\r
+ var hm = diff_halfmatch(text1, text2);\r
+ if (hm) {\r
+ // A half-match was found, sort out the return data.\r
+ var text1_a = hm[0];\r
+ var text1_b = hm[1];\r
+ var text2_a = hm[2];\r
+ var text2_b = hm[3];\r
+ var mid_common = hm[4];\r
+ // Send both pairs off for separate processing.\r
+ var diff_a = diff_main(text1_a, text2_a, checklines);\r
+ var diff_b = diff_main(text1_b, text2_b, checklines);\r
+ // Merge the results.\r
+ diff = diff_a.concat([[0, mid_common]], diff_b);\r
+ } else {\r
+ // Perform a real diff.\r
+ if (checklines && text1.length + text2.length < 250)\r
+ checklines = false; // Too trivial for the overhead.\r
+ if (checklines) {\r
+ // Scan the text on a line-by-line basis first.\r
+ a = diff_lines2chars(text1, text2);\r
+ text1 = a[0];\r
+ text2 = a[1];\r
+ var linearray = a[2];\r
+ }\r
+ diff = diff_map(text1, text2);\r
+ if (!diff) // No acceptable result.\r
+ diff = [[-1, text1], [1, text2]];\r
+ if (checklines) {\r
+ diff_chars2lines(diff, linearray); // Convert the diff back to original text.\r
+ diff_cleanup_semantic(diff); // Eliminate freak matches (e.g. blank lines)\r
+\r
+ // Rediff any replacement blocks, this time on character-by-character basis.\r
+ diff.push([0, '']); // Add a dummy entry at the end.\r
+ var pointer = 0;\r
+ var count_delete = 0;\r
+ var count_insert = 0;\r
+ var text_delete = '';\r
+ var text_insert = '';\r
+ while(pointer < diff.length) {\r
+ if (diff[pointer][0] == 1) {\r
+ count_insert++;\r
+ text_insert += diff[pointer][1];\r
+ } else if (diff[pointer][0] == -1) {\r
+ count_delete++;\r
+ text_delete += diff[pointer][1];\r
+ } else { // Upon reaching an equality, check for prior redundancies.\r
+ if (count_delete >= 1 && count_insert >= 1) {\r
+ // Delete the offending records and add the merged ones.\r
+ a = diff_main(text_delete, text_insert, false);\r
+ diff.splice(pointer - count_delete - count_insert, count_delete + count_insert);\r
+ pointer = pointer - count_delete - count_insert;\r
+ for (i=a.length-1; i>=0; i--)\r
+ diff.splice(pointer, 0, a[i]);\r
+ pointer = pointer + a.length;\r
+ }\r
+ count_insert = 0;\r
+ count_delete = 0;\r
+ text_delete = '';\r
+ text_insert = '';\r
+ }\r
+ pointer++;\r
+ }\r
+ diff.pop(); // Remove the dummy entry at the end.\r
+\r
+ }\r
+ }\r
+ }\r
+\r
+ if (commonprefix)\r
+ diff.unshift([0, commonprefix]);\r
+ if (commonsuffix)\r
+ diff.push([0, commonsuffix]);\r
+ diff_cleanup_merge(diff);\r
+ return diff;\r
+}\r
+\r
+\r
+function diff_lines2chars(text1, text2) {\r
+ // Split text into an array of strings.\r
+ // Reduce the texts to a string of hashes where each character represents one line.\r
+ var linearray = new Array(); // linearray[4] == "Hello\n"\r
+ var linehash = new Object(); // linehash["Hello\n"] == 4\r
+\r
+ // "\x00" is a valid JavaScript character, but the Venkman debugger doesn't like it (bug 335098)\r
+ // So we'll insert a junk entry to avoid generating a null character.\r
+ linearray.push('');\r
+\r
+ function diff_lines2chars_munge(text) {\r
+ // My first ever closure!\r
+ var i, line;\r
+ var chars = '';\r
+ while (text) {\r
+ i = text.indexOf('\n');\r
+ if (i == -1)\r
+ i = text.length;\r
+ line = text.substring(0, i+1);\r
+ text = text.substring(i+1);\r
+ if (linehash.hasOwnProperty ? linehash.hasOwnProperty(line) : (linehash[line] !== undefined)) {\r
+ chars += String.fromCharCode(linehash[line]);\r
+ } else {\r
+ linearray.push(line);\r
+ linehash[line] = linearray.length - 1;\r
+ chars += String.fromCharCode(linearray.length - 1);\r
+ }\r
+ }\r
+ return chars;\r
+ }\r
+\r
+ var chars1 = diff_lines2chars_munge(text1);\r
+ var chars2 = diff_lines2chars_munge(text2);\r
+ return [chars1, chars2, linearray];\r
+}\r
+\r
+\r
+function diff_chars2lines(diff, linearray) {\r
+ // Rehydrate the text in a diff from a string of line hashes to real lines of text.\r
+ var chars, text;\r
+ for (var x=0; x<diff.length; x++) {\r
+ chars = diff[x][1];\r
+ text = '';\r
+ for (var y=0; y<chars.length; y++)\r
+ text += linearray[chars.charCodeAt(y)];\r
+ diff[x][1] = text;\r
+ }\r
+}\r
+\r
+\r
+function diff_map(text1, text2) {\r
+ // Explore the intersection points between the two texts.\r
+ var now = new Date();\r
+ var ms_end = now.getTime() + DIFF_TIMEOUT * 1000; // Don't run for too long.\r
+ var max = (text1.length + text2.length) / 2;\r
+ var v_map1 = new Array();\r
+ var v_map2 = new Array();\r
+ var v1 = new Object();\r
+ var v2 = new Object();\r
+ v1[1] = 0;\r
+ v2[1] = 0;\r
+ var x, y;\r
+ var footstep; // Used to track overlapping paths.\r
+ var footsteps = new Object();\r
+ var done = false;\r
+ var hasOwnProperty = !!(footsteps.hasOwnProperty);\r
+ // If the total number of characters is odd, then the front path will collide with the reverse path.\r
+ var front = (text1.length + text2.length) % 2;\r
+ for (var d=0; d<max; d++) {\r
+ now = new Date();\r
+ if (DIFF_TIMEOUT > 0 && now.getTime() > ms_end) // Timeout reached\r
+ return null;\r
+\r
+ // Walk the front path one step.\r
+ v_map1[d] = new Object();\r
+ for (var k=-d; k<=d; k+=2) {\r
+ if (k == -d || k != d && v1[k-1] < v1[k+1])\r
+ x = v1[k+1];\r
+ else\r
+ x = v1[k-1]+1;\r
+ y = x - k;\r
+ footstep = x+","+y;\r
+ if (front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))\r
+ done = true;\r
+ if (!front)\r
+ footsteps[footstep] = d;\r
+ while (!done && x < text1.length && y < text2.length && text1.charAt(x) == text2.charAt(y)) {\r
+ x++; y++;\r
+ footstep = x+","+y;\r
+ if (front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))\r
+ done = true;\r
+ if (!front)\r
+ footsteps[footstep] = d;\r
+ }\r
+ v1[k] = x;\r
+ v_map1[d][x+","+y] = true;\r
+ if (done) {\r
+ // Front path ran over reverse path.\r
+ v_map2 = v_map2.slice(0, footsteps[footstep]+1);\r
+ var a = diff_path1(v_map1, text1.substring(0, x), text2.substring(0, y));\r
+ return a.concat(diff_path2(v_map2, text1.substring(x), text2.substring(y)));\r
+ }\r
+ }\r
+\r
+ // Walk the reverse path one step.\r
+ v_map2[d] = new Object();\r
+ for (var k=-d; k<=d; k+=2) {\r
+ if (k == -d || k != d && v2[k-1] < v2[k+1])\r
+ x = v2[k+1];\r
+ else\r
+ x = v2[k-1]+1;\r
+ y = x - k;\r
+ footstep = (text1.length-x)+","+(text2.length-y);\r
+ if (!front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))\r
+ done = true;\r
+ if (front)\r
+ footsteps[footstep] = d;\r
+ while (!done && x < text1.length && y < text2.length && text1.charAt(text1.length-x-1) == text2.charAt(text2.length-y-1)) {\r
+ x++; y++;\r
+ footstep = (text1.length-x)+","+(text2.length-y);\r
+ if (!front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))\r
+ done = true;\r
+ if (front)\r
+ footsteps[footstep] = d;\r
+ }\r
+ v2[k] = x;\r
+ v_map2[d][x+","+y] = true;\r
+ if (done) {\r
+ // Reverse path ran over front path.\r
+ v_map1 = v_map1.slice(0, footsteps[footstep]+1);\r
+ var a = diff_path1(v_map1, text1.substring(0, text1.length-x), text2.substring(0, text2.length-y));\r
+ return a.concat(diff_path2(v_map2, text1.substring(text1.length-x), text2.substring(text2.length-y)));\r
+ }\r
+ }\r
+ }\r
+ // Number of diffs equals number of characters, no commonality at all.\r
+ return null;\r
+}\r
+\r
+\r
+function diff_path1(v_map, text1, text2) {\r
+ // Work from the middle back to the start to determine the path.\r
+ var path = [];\r
+ var x = text1.length;\r
+ var y = text2.length;\r
+ var last_op = null;\r
+ for (var d=v_map.length-2; d>=0; d--) {\r
+ while(1) {\r
+ if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty((x-1)+","+y) : (v_map[d][(x-1)+","+y] !== undefined)) {\r
+ x--;\r
+ if (last_op === -1)\r
+ path[0][1] = text1.charAt(x) + path[0][1];\r
+ else\r
+ path.unshift([-1, text1.charAt(x)]);\r
+ last_op = -1;\r
+ break;\r
+ } else if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty(x+","+(y-1)) : (v_map[d][x+","+(y-1)] !== undefined)) {\r
+ y--;\r
+ if (last_op === 1)\r
+ path[0][1] = text2.charAt(y) + path[0][1];\r
+ else\r
+ path.unshift([1, text2.charAt(y)]);\r
+ last_op = 1;\r
+ break;\r
+ } else {\r
+ x--;\r
+ y--;\r
+ //if (text1.charAt(x) != text2.charAt(y))\r
+ // return alert("No diagonal. Can't happen. (diff_path1)");\r
+ if (last_op === 0)\r
+ path[0][1] = text1.charAt(x) + path[0][1];\r
+ else\r
+ path.unshift([0, text1.charAt(x)]);\r
+ last_op = 0;\r
+ }\r
+ }\r
+ }\r
+ return path;\r
+}\r
+\r
+\r
+function diff_path2(v_map, text1, text2) {\r
+ // Work from the middle back to the end to determine the path.\r
+ var path = [];\r
+ var x = text1.length;\r
+ var y = text2.length;\r
+ var last_op = null;\r
+ for (var d=v_map.length-2; d>=0; d--) {\r
+ while(1) {\r
+ if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty((x-1)+","+y) : (v_map[d][(x-1)+","+y] !== undefined)) {\r
+ x--;\r
+ if (last_op === -1)\r
+ path[path.length-1][1] += text1.charAt(text1.length-x-1);\r
+ else\r
+ path.push([-1, text1.charAt(text1.length-x-1)]);\r
+ last_op = -1;\r
+ break;\r
+ } else if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty(x+","+(y-1)) : (v_map[d][x+","+(y-1)] !== undefined)) {\r
+ y--;\r
+ if (last_op === 1)\r
+ path[path.length-1][1] += text2.charAt(text2.length-y-1);\r
+ else\r
+ path.push([1, text2.charAt(text2.length-y-1)]);\r
+ last_op = 1;\r
+ break;\r
+ } else {\r
+ x--;\r
+ y--;\r
+ //if (text1.charAt(text1.length-x-1) != text2.charAt(text2.length-y-1))\r
+ // return alert("No diagonal. Can't happen. (diff_path2)");\r
+ if (last_op === 0)\r
+ path[path.length-1][1] += text1.charAt(text1.length-x-1);\r
+ else\r
+ path.push([0, text1.charAt(text1.length-x-1)]);\r
+ last_op = 0;\r
+ }\r
+ }\r
+ }\r
+ return path;\r
+}\r
+\r
+\r
+function diff_prefix(text1, text2) {\r
+ // Trim off common prefix\r
+ var pointermin = 0;\r
+ var pointermax = Math.min(text1.length, text2.length);\r
+ var pointermid = pointermax;\r
+ while(pointermin < pointermid) {\r
+ if (text1.substring(0, pointermid) == text2.substring(0, pointermid))\r
+ pointermin = pointermid;\r
+ else\r
+ pointermax = pointermid;\r
+ pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);\r
+ }\r
+ var commonprefix = text1.substring(0, pointermid);\r
+ text1 = text1.substring(pointermid);\r
+ text2 = text2.substring(pointermid);\r
+ return [text1, text2, commonprefix];\r
+}\r
+\r
+\r
+function diff_suffix(text1, text2) {\r
+ // Trim off common suffix\r
+ var pointermin = 0;\r
+ var pointermax = Math.min(text1.length, text2.length);\r
+ var pointermid = pointermax;\r
+ while(pointermin < pointermid) {\r
+ if (text1.substring(text1.length-pointermid) == text2.substring(text2.length-pointermid))\r
+ pointermin = pointermid;\r
+ else\r
+ pointermax = pointermid;\r
+ pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);\r
+ }\r
+ var commonsuffix = text1.substring(text1.length-pointermid);\r
+ text1 = text1.substring(0, text1.length-pointermid);\r
+ text2 = text2.substring(0, text2.length-pointermid);\r
+ return [text1, text2, commonsuffix];\r
+}\r
+\r
+\r
+function diff_halfmatch(text1, text2) {\r
+ // Do the two texts share a substring which is at least half the length of the longer text?\r
+ var longtext = text1.length > text2.length ? text1 : text2;\r
+ var shorttext = text1.length > text2.length ? text2 : text1;\r
+ if (longtext.length < 10 || shorttext.length < 1)\r
+ return null; // Pointless.\r
+\r
+ function diff_halfmatch_i(longtext, shorttext, i) {\r
+ // Start with a 1/4 length substring at position i as a seed.\r
+ var seed = longtext.substring(i, i+Math.floor(longtext.length/4));\r
+ var j = -1;\r
+ var best_common = '';\r
+ var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;\r
+ while ((j = shorttext.indexOf(seed, j+1)) != -1) {\r
+ var my_prefix = diff_prefix(longtext.substring(i), shorttext.substring(j));\r
+ var my_suffix = diff_suffix(longtext.substring(0, i), shorttext.substring(0, j));\r
+ if (best_common.length < (my_suffix[2] + my_prefix[2]).length) {\r
+ best_common = my_suffix[2] + my_prefix[2];\r
+ best_longtext_a = my_suffix[0];\r
+ best_longtext_b = my_prefix[0];\r
+ best_shorttext_a = my_suffix[1];\r
+ best_shorttext_b = my_prefix[1];\r
+ }\r
+ }\r
+ if (best_common.length >= longtext.length/2)\r
+ return [best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common];\r
+ else\r
+ return null;\r
+ }\r
+\r
+ // First check if the second quarter is the seed for a half-match.\r
+ var hm1 = diff_halfmatch_i(longtext, shorttext, Math.ceil(longtext.length/4));\r
+ // Check again based on the third quarter.\r
+ var hm2 = diff_halfmatch_i(longtext, shorttext, Math.ceil(longtext.length/2));\r
+ var hm;\r
+ if (!hm1 && !hm2)\r
+ return null;\r
+ else if (!hm2)\r
+ hm = hm1;\r
+ else if (!hm1)\r
+ hm = hm2;\r
+ else // Both matched. Select the longest.\r
+ hm = hm1[4].length > hm2[4].length ? hm1 : hm2;\r
+\r
+ // A half-match was found, sort out the return data.\r
+ if (text1.length > text2.length) {\r
+ var text1_a = hm[0];\r
+ var text1_b = hm[1];\r
+ var text2_a = hm[2];\r
+ var text2_b = hm[3];\r
+ } else {\r
+ var text2_a = hm[0];\r
+ var text2_b = hm[1];\r
+ var text1_a = hm[2];\r
+ var text1_b = hm[3];\r
+ }\r
+ var mid_common = hm[4];\r
+ return [text1_a, text1_b, text2_a, text2_b, mid_common];\r
+}\r
+\r
+\r
+function diff_cleanup_semantic(diff) {\r
+ // Reduce the number of edits by eliminating semantically trivial equalities.\r
+ var changes = false;\r
+ var equalities = []; // Stack of indices where equalities are found.\r
+ var lastequality = null; // Always equal to equalities[equalities.length-1][1]\r
+ var pointer = 0; // Index of current position.\r
+ var length_changes1 = 0; // Number of characters that changed prior to the equality.\r
+ var length_changes2 = 0; // Number of characters that changed after the equality.\r
+ while (pointer < diff.length) {\r
+ if (diff[pointer][0] == 0) { // equality found\r
+ equalities.push(pointer);\r
+ length_changes1 = length_changes2;\r
+ length_changes2 = 0;\r
+ lastequality = diff[pointer][1];\r
+ } else { // an insertion or deletion\r
+ length_changes2 += diff[pointer][1].length;\r
+ if (lastequality != null && (lastequality.length <= length_changes1) && (lastequality.length <= length_changes2)) {\r
+ //alert("Splitting: '"+lastequality+"'");\r
+ diff.splice(equalities[equalities.length-1], 0, [-1, lastequality]); // Duplicate record\r
+ diff[equalities[equalities.length-1]+1][0] = 1; // Change second copy to insert.\r
+ equalities.pop(); // Throw away the equality we just deleted;\r
+ equalities.pop(); // Throw away the previous equality;\r
+ pointer = equalities.length ? equalities[equalities.length-1] : -1;\r
+ length_changes1 = 0; // Reset the counters.\r
+ length_changes2 = 0;\r
+ lastequality = null;\r
+ changes = true;\r
+ }\r
+ }\r
+ pointer++;\r
+ }\r
+\r
+ if (changes)\r
+ diff_cleanup_merge(diff);\r
+}\r
+\r
+\r
+function diff_cleanup_efficiency(diff) {\r
+ // Reduce the number of edits by eliminating operationally trivial equalities.\r
+ var changes = false;\r
+ var equalities = []; // Stack of indices where equalities are found.\r
+ var lastequality = ''; // Always equal to equalities[equalities.length-1][1]\r
+ var pointer = 0; // Index of current position.\r
+ var pre_ins = false; // Is there an insertion operation before the last equality.\r
+ var pre_del = false; // Is there an deletion operation before the last equality.\r
+ var post_ins = false; // Is there an insertion operation after the last equality.\r
+ var post_del = false; // Is there an deletion operation after the last equality.\r
+ while (pointer < diff.length) {\r
+ if (diff[pointer][0] == 0) { // equality found\r
+ if (diff[pointer][1].length < DIFF_EDIT_COST && (post_ins || post_del)) {\r
+ // Candidate found.\r
+ equalities.push(pointer);\r
+ pre_ins = post_ins;\r
+ pre_del = post_del;\r
+ lastequality = diff[pointer][1];\r
+ } else {\r
+ // Not a candidate, and can never become one.\r
+ equalities = [];\r
+ lastequality = '';\r
+ }\r
+ post_ins = post_del = false;\r
+ } else { // an insertion or deletion\r
+ if (diff[pointer][0] == -1)\r
+ post_del = true;\r
+ else\r
+ post_ins = true;\r
+ // Five types to be split:\r
+ // <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>\r
+ // <ins>A</ins>X<ins>C</ins><del>D</del>\r
+ // <ins>A</ins><del>B</del>X<ins>C</ins>\r
+ // <ins>A</del>X<ins>C</ins><del>D</del>\r
+ // <ins>A</ins><del>B</del>X<del>C</del>\r
+ 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
+ //alert("Splitting: '"+lastequality+"'");\r
+ diff.splice(equalities[equalities.length-1], 0, [-1, lastequality]); // Duplicate record\r
+ diff[equalities[equalities.length-1]+1][0] = 1; // Change second copy to insert.\r
+ equalities.pop(); // Throw away the equality we just deleted;\r
+ lastequality = '';\r
+ if (pre_ins && pre_del) {\r
+ // No changes made which could affect previous entry, keep going.\r
+ post_ins = post_del = true;\r
+ equalities = [];\r
+ } else {\r
+ equalities.pop(); // Throw away the previous equality;\r
+ pointer = equalities.length ? equalities[equalities.length-1] : -1;\r
+ post_ins = post_del = false;\r
+ }\r
+ changes = true;\r
+ }\r
+ }\r
+ pointer++;\r
+ }\r
+\r
+ if (changes)\r
+ diff_cleanup_merge(diff);\r
+}\r
+\r
+\r
+function diff_cleanup_merge(diff) {\r
+ // Reorder and merge like edit sections. Merge equalities.\r
+ // Any edit section can move as long as it doesn't cross an equality.\r
+ diff.push([0, '']); // Add a dummy entry at the end.\r
+ var pointer = 0;\r
+ var count_delete = 0;\r
+ var count_insert = 0;\r
+ var text_delete = '';\r
+ var text_insert = '';\r
+ var record_insert, record_delete;\r
+ var my_xfix;\r
+ while(pointer < diff.length) {\r
+ if (diff[pointer][0] == 1) {\r
+ count_insert++;\r
+ text_insert += diff[pointer][1];\r
+ pointer++;\r
+ } else if (diff[pointer][0] == -1) {\r
+ count_delete++;\r
+ text_delete += diff[pointer][1];\r
+ pointer++;\r
+ } else { // Upon reaching an equality, check for prior redundancies.\r
+ if (count_delete > 1 || count_insert > 1) {\r
+ if (count_delete > 1 && count_insert > 1) {\r
+ // Factor out any common prefixies.\r
+ my_xfix = diff_prefix(text_insert, text_delete);\r
+ if (my_xfix[2] != '') {\r
+ if ((pointer - count_delete - count_insert) > 0 && diff[pointer - count_delete - count_insert - 1][0] == 0) {\r
+ text_insert = my_xfix[0];\r
+ text_delete = my_xfix[1];\r
+ diff[pointer - count_delete - count_insert - 1][1] += my_xfix[2];\r
+ }\r
+ }\r
+ // Factor out any common suffixies.\r
+ my_xfix = diff_suffix(text_insert, text_delete);\r
+ if (my_xfix[2] != '') {\r
+ text_insert = my_xfix[0];\r
+ text_delete = my_xfix[1];\r
+ diff[pointer][1] = my_xfix[2] + diff[pointer][1];\r
+ }\r
+ }\r
+ // Delete the offending records and add the merged ones.\r
+ if (count_delete == 0)\r
+ diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [1, text_insert]);\r
+ else if (count_insert == 0)\r
+ diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [-1, text_delete]);\r
+ else\r
+ diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [-1, text_delete], [1, text_insert]);\r
+ pointer = pointer - count_delete - count_insert + (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;\r
+ } else if (pointer != 0 && diff[pointer-1][0] == 0) {\r
+ // Merge this equality with the previous one.\r
+ diff[pointer-1][1] += diff[pointer][1];\r
+ diff.splice(pointer, 1);\r
+ } else {\r
+ pointer++;\r
+ }\r
+ count_insert = 0;\r
+ count_delete = 0;\r
+ text_delete = '';\r
+ text_insert = '';\r
+ }\r
+ }\r
+ if (diff[diff.length-1][1] == '')\r
+ diff.pop(); // Remove the dummy entry at the end.\r
+}\r
+\r
+\r
+function diff_addindex(diff) {\r
+ // Add an index to each tuple, represents where the tuple is located in text2.\r
+ // e.g. [[-1, 'h', 0], [1, 'c', 0], [0, 'at', 1]]\r
+ var i = 0;\r
+ for (var x=0; x<diff.length; x++) {\r
+ diff[x].push(i);\r
+ if (diff[x][0] != -1)\r
+ i += diff[x][1].length;\r
+ }\r
+}\r
+\r
+\r
+function diff_xindex(diff, loc) {\r
+ // loc is a location in text1, compute and return the equivalent location in text2.\r
+ // e.g. "The cat" vs "The big cat", 1->1, 5->8\r
+ var chars1 = 0;\r
+ var chars2 = 0;\r
+ var last_chars1 = 0;\r
+ var last_chars2 = 0;\r
+ for (var x=0; x<diff.length; x++) {\r
+ if (diff[x][0] != 1) // Equality or deletion.\r
+ chars1 += diff[x][1].length;\r
+ if (diff[x][0] != -1) // Equality or insertion.\r
+ chars2 += diff[x][1].length;\r
+ if (chars1 > loc) // Overshot the location.\r
+ break;\r
+ last_chars1 = chars1;\r
+ last_chars2 = chars2;\r
+ }\r
+ if (diff.length != x && diff[x][0] == -1) // The location was deleted.\r
+ return last_chars2;\r
+ // Add the remaining character length.\r
+ return last_chars2 + (loc - last_chars1);\r
+}\r
+\r
+\r
+function diff_prettyhtml(diff) {\r
+ // Convert a diff array into a pretty HTML report.\r
+ diff_addindex(diff);\r
+ var html = '';\r
+ for (var x=0; x<diff.length; x++) {\r
+ var m = diff[x][0]; // Mode (-1=delete, 0=copy, 1=add)\r
+ var t = diff[x][1]; // Text of change.\r
+ var i = diff[x][2]; // Index of change.\r
+ t = t.replace(/&/g, "&").replace(/</g, "<").replace(/>/g, ">");\r
+ t = t.replace(/\n/g, "¶<BR>");\r
+ if (m == -1)\r
+ html += "<DEL STYLE='background:#FFE6E6;' TITLE='i="+i+"'>"+t+"</DEL>";\r
+ else if (m == 1)\r
+ html += "<INS STYLE='background:#E6FFE6;' TITLE='i="+i+"'>"+t+"</INS>";\r
+ else\r
+ html += "<SPAN TITLE='i="+i+"'>"+t+"</SPAN>";\r
+ }\r
+ return html;\r
+}\r
+\r
+\r
+ //////////////////////////////////////////////////////////////////////\r
+ // Match //\r
+//////////////////////////////////////////////////////////////////////\r
+\r
+\r
+function match_getmaxbits() {\r
+ // Compute the number of bits in an int.\r
+ // The normal answer for JavaScript is 32.\r
+ var maxbits = 0;\r
+ var oldi = 1;\r
+ var newi = 2;\r
+ while (oldi != newi) {\r
+ maxbits++;\r
+ oldi = newi;\r
+ newi = newi << 1;\r
+ }\r
+ return maxbits;\r
+}\r
+var MATCH_MAXBITS = match_getmaxbits();\r
+\r
+\r
+function match_main(text, pattern, loc) {\r
+ // Locate the best instance of 'pattern' in 'text' near 'loc'.\r
+ loc = Math.max(0, Math.min(loc, text.length-pattern.length));\r
+ if (text == pattern) {\r
+ // Shortcut (potentially not guaranteed by the algorithm)\r
+ return 0;\r
+ } else if (text.length == 0) {\r
+ // Nothing to match.\r
+ return null;\r
+ } else if (text.substring(loc, loc + pattern.length) == pattern) {\r
+ // Perfect match at the perfect spot! (Includes case of null pattern)\r
+ return loc;\r
+ } else {\r
+ // Do a fuzzy compare.\r
+ var match = match_bitap(text, pattern, loc);\r
+ return match;\r
+ }\r
+}\r
+\r
+\r
+function match_bitap(text, pattern, loc) {\r
+ // Locate the best instance of 'pattern' in 'text' near 'loc' using the Bitap algorithm.\r
+ if (pattern.length > MATCH_MAXBITS)\r
+ return alert("Pattern too long for this browser.");\r
+\r
+ // Initialise the alphabet.\r
+ var s = match_alphabet(pattern);\r
+\r
+ var score_text_length = text.length;\r
+ // Coerce the text length between reasonable maximums and minimums.\r
+ score_text_length = Math.max(score_text_length, MATCH_MINLENGTH);\r
+ score_text_length = Math.min(score_text_length, MATCH_MAXLENGTH);\r
+\r
+ function match_bitap_score (e, x) {\r
+ // Compute and return the score for a match with e errors and x location.\r
+ var d = Math.abs(loc-x);\r
+ return (e / pattern.length / MATCH_BALANCE) + (d / score_text_length / (1.0 - MATCH_BALANCE));\r
+ }\r
+\r
+ // Highest score beyond which we give up.\r
+ var score_threshold = MATCH_THRESHOLD;\r
+ // Is there a nearby exact match? (speedup)\r
+ var best_loc = text.indexOf(pattern, loc);\r
+ if (best_loc != -1)\r
+ score_threshold = Math.min(match_bitap_score(0, best_loc), score_threshold);\r
+ // What about in the other direction? (speedup)\r
+ best_loc = text.lastIndexOf(pattern, loc+pattern.length);\r
+ if (best_loc != -1)\r
+ score_threshold = Math.min(match_bitap_score(0, best_loc), score_threshold);\r
+\r
+ // Initialise the bit arrays.\r
+ var r = Array();\r
+ var d = -1;\r
+ var matchmask = Math.pow(2, pattern.length-1);\r
+ best_loc = null;\r
+\r
+ var bin_min, bin_mid;\r
+ var bin_max = Math.max(loc+loc, text.length);\r
+ var last_rd;\r
+ for (var d=0; d<pattern.length; d++) {\r
+ // Scan for the best match; each iteration allows for one more error.\r
+ var rd = Array(text.length);\r
+\r
+ // Run a binary search to determine how far from 'loc' we can stray at this error level.\r
+ bin_min = loc;\r
+ bin_mid = bin_max;\r
+ while(bin_min < bin_mid) {\r
+ if (match_bitap_score(d, bin_mid) < score_threshold)\r
+ bin_min = bin_mid;\r
+ else\r
+ bin_max = bin_mid;\r
+ bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min);\r
+ }\r
+ bin_max = bin_mid; // Use the result from this iteration as the maximum for the next.\r
+ var start = Math.max(0, loc - (bin_mid - loc) - 1);\r
+ var finish = Math.min(text.length-1, pattern.length + bin_mid);\r
+\r
+ if (text.charAt(finish) == pattern.charAt(pattern.length-1))\r
+ rd[finish] = Math.pow(2, d+1)-1;\r
+ else\r
+ rd[finish] = Math.pow(2, d)-1;\r
+ for (var j=finish-1; j>=start; j--) {\r
+ // The alphabet (s) is a sparse hash, so the following lines generate warnings.\r
+ if (d == 0) // First pass: exact match.\r
+ rd[j] = ((rd[j+1] << 1) | 1) & s[text.charAt(j)];\r
+ else // Subsequent passes: fuzzy match.\r
+ 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
+ if (rd[j] & matchmask) {\r
+ var score = match_bitap_score(d, j);\r
+ // This match will almost certainly be better than any existing match. But check anyway.\r
+ if (score <= score_threshold) {\r
+ // Told you so.\r
+ score_threshold = score;\r
+ best_loc = j;\r
+ if (j > loc) {\r
+ // When passing loc, don't exceed our current distance from loc.\r
+ start = Math.max(0, loc - (j - loc));\r
+ } else {\r
+ // Already passed loc, downhill from here on in.\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ if (match_bitap_score(d+1, loc) > score_threshold) // No hope for a (better) match at greater error levels.\r
+ break;\r
+ last_rd = rd;\r
+ }\r
+ return best_loc;\r
+}\r
+\r
+\r
+function match_alphabet(pattern) {\r
+ // Initialise the alphabet for the Bitap algorithm.\r
+ var s = Object();\r
+ for (var i=0; i<pattern.length; i++)\r
+ s[pattern.charAt(i)] = 0;\r
+ for (var i=0; i<pattern.length; i++)\r
+ s[pattern.charAt(i)] |= Math.pow(2, pattern.length-i-1);\r
+ return s;\r
+}\r
+\r
+\r
+ //////////////////////////////////////////////////////////////////////\r
+ // Patch //\r
+//////////////////////////////////////////////////////////////////////\r
+\r
+\r
+function patch_obj() {\r
+ // Constructor for a patch object.\r
+ this.diffs = [];\r
+ this.start1 = null;\r
+ this.start2 = null;\r
+ this.length1 = 0;\r
+ this.length2 = 0;\r
+\r
+ this.toString = function() {\r
+ // Emmulate GNU diff's format.\r
+ // Header: @@ -382,8 +481,9 @@\r
+ // Indicies are printed as 1-based, not 0-based.\r
+ var coords1, coords2;\r
+ if (this.length1 == 0)\r
+ coords1 = this.start1+",0";\r
+ else if (this.length1 == 1)\r
+ coords1 = this.start1+1;\r
+ else\r
+ coords1 = (this.start1+1)+","+this.length1;\r
+ if (this.length2 == 0)\r
+ coords2 = this.start2+",0";\r
+ else if (this.length2 == 1)\r
+ coords2 = this.start2+1;\r
+ else\r
+ coords2 = (this.start2+1)+","+this.length2;\r
+ var txt = "@@ -"+coords1+" +"+coords2+" @@\n";\r
+ // Escape the body of the patch with %xx notation.\r
+ for (var x=0; x<this.diffs.length; x++)\r
+ txt += ("- +".charAt(this.diffs[x][0]+1)) + encodeURI(this.diffs[x][1]) + "\n";\r
+ return txt.replace(/%20/g, ' ');\r
+ }\r
+\r
+ this.text1 = function() {\r
+ // Compute and return the source text (all equalities and deletions).\r
+ var txt = '';\r
+ for (var x=0; x<this.diffs.length; x++)\r
+ if (this.diffs[x][0] == 0 || this.diffs[x][0] == -1)\r
+ txt += this.diffs[x][1];\r
+ return txt;\r
+ }\r
+\r
+ this.text2 = function() {\r
+ // Compute and return the destination text (all equalities and insertions).\r
+ var txt = '';\r
+ for (var x=0; x<this.diffs.length; x++)\r
+ if (this.diffs[x][0] == 0 || this.diffs[x][0] == 1)\r
+ txt += this.diffs[x][1];\r
+ return txt;\r
+ }\r
+}\r
+\r
+\r
+function patch_addcontext(patch, text) {\r
+ var pattern = text.substring(patch.start2, patch.start2+patch.length1);\r
+ var padding = 0;\r
+ // Increase the context until we're unique (but don't let the pattern expand beyond MATCH_MAXBITS).\r
+ while (text.indexOf(pattern) != text.lastIndexOf(pattern) && pattern.length < MATCH_MAXBITS-PATCH_MARGIN-PATCH_MARGIN) {\r
+ padding += PATCH_MARGIN;\r
+ pattern = text.substring(patch.start2 - padding, patch.start2+patch.length1 + padding);\r
+ }\r
+ // Add one chunk for good luck.\r
+ padding += PATCH_MARGIN;\r
+ // Add the prefix.\r
+ var prefix = text.substring(patch.start2 - padding, patch.start2);\r
+ if (prefix != '')\r
+ patch.diffs.unshift([0, prefix]);\r
+ // Add the suffix\r
+ var suffix = text.substring(patch.start2+patch.length1, patch.start2+patch.length1 + padding);\r
+ if (suffix != '')\r
+ patch.diffs.push([0, suffix]);\r
+\r
+ // Roll back the start points.\r
+ patch.start1 -= prefix.length;\r
+ patch.start2 -= prefix.length;\r
+ // Extend the lengths.\r
+ patch.length1 += prefix.length + suffix.length;\r
+ patch.length2 += prefix.length + suffix.length;\r
+}\r
+\r
+\r
+function patch_make(text1, text2, diff) {\r
+ // Compute a list of patches to turn text1 into text2.\r
+ // Use diff if provided, otherwise compute it ourselves.\r
+ if (typeof diff == 'undefined') {\r
+ diff = diff_main(text1, text2, true);\r
+ if (diff.length > 2) {\r
+ diff_cleanup_semantic(diff);\r
+ diff_cleanup_efficiency(diff);\r
+ }\r
+ }\r
+ if (diff.length == 0)\r
+ return []; // Get rid of the null case.\r
+ var patches = [];\r
+ var patch = new patch_obj();\r
+ var char_count1 = 0; // Number of characters into the text1 string.\r
+ var char_count2 = 0; // Number of characters into the text2 string.\r
+ var last_type = null;\r
+ var prepatch_text = text1; // Recreate the patches to determine context info.\r
+ var postpatch_text = text1;\r
+ for (var x=0; x<diff.length; x++) {\r
+ var diff_type = diff[x][0];\r
+ var diff_text = diff[x][1];\r
+\r
+ if (patch.diffs.length == 0 && diff_type != 0) {\r
+ // A new patch starts here.\r
+ patch.start1 = char_count1;\r
+ patch.start2 = char_count2;\r
+ }\r
+\r
+ if (diff_type == 1) {\r
+ // Insertion\r
+ patch.diffs.push(diff[x]);\r
+ patch.length2 += diff_text.length;\r
+ postpatch_text = postpatch_text.substring(0, char_count2) + diff_text + postpatch_text.substring(char_count2);\r
+ } else if (diff_type == -1) {\r
+ // Deletion.\r
+ patch.length1 += diff_text.length;\r
+ patch.diffs.push(diff[x]);\r
+ postpatch_text = postpatch_text.substring(0, char_count2) + postpatch_text.substring(char_count2 + diff_text.length);\r
+ } else if (diff_type == 0 && diff_text.length <= 2*PATCH_MARGIN && patch.diffs.length != 0 && diff.length != x+1) {\r
+ // Small equality inside a patch.\r
+ patch.diffs.push(diff[x]);\r
+ patch.length1 += diff_text.length;\r
+ patch.length2 += diff_text.length;\r
+ }\r
+\r
+ last_type = diff_type;\r
+ if (diff_type == 0 && diff_text.length >= 2*PATCH_MARGIN) {\r
+ // Time for a new patch.\r
+ if (patch.diffs.length != 0) {\r
+ patch_addcontext(patch, prepatch_text);\r
+ patches.push(patch);\r
+ var patch = new patch_obj();\r
+ last_type = null;\r
+ prepatch_text = postpatch_text;\r
+ }\r
+ }\r
+\r
+ // Update the current character count.\r
+ if (diff_type != 1)\r
+ char_count1 += diff_text.length;\r
+ if (diff_type != -1)\r
+ char_count2 += diff_text.length;\r
+ }\r
+ // Pick up the leftover patch if not empty.\r
+ if (patch.diffs.length != 0) {\r
+ patch_addcontext(patch, prepatch_text);\r
+ patches.push(patch);\r
+ }\r
+\r
+ return patches;\r
+}\r
+\r
+\r
+function patch_apply(patches, text) {\r
+ // Merge a set of patches onto the text.\r
+ // Return a patched text, as well as a list of true/false values indicating which patches were applied.\r
+ patch_splitmax(patches);\r
+ var results = [];\r
+ var delta = 0;\r
+ var expected_loc, start_loc;\r
+ var text1, text2;\r
+ var diff, mod, index1, index2;\r
+ for (var x=0; x<patches.length; x++) {\r
+ expected_loc = patches[x].start2 + delta;\r
+ text1 = patches[x].text1();\r
+ start_loc = match_main(text, text1, expected_loc);\r
+ if (start_loc == null) {\r
+ // No match found. :(\r
+ results.push(false);\r
+ } else {\r
+ // Found a match. :)\r
+ results.push(true);\r
+ delta = start_loc - expected_loc;\r
+ text2 = text.substring(start_loc, start_loc + text1.length);\r
+ if (text1 == text2) {\r
+ // Perfect match, just shove the replacement text in.\r
+ text = text.substring(0, start_loc) + patches[x].text2() + text.substring(start_loc + text1.length);\r
+ } else {\r
+ // Imperfect match. Run a diff to get a framework of equivalent indicies.\r
+ diff = diff_main(text1, text2, false);\r
+ index1 = 0;\r
+ for (var y=0; y<patches[x].diffs.length; y++) {\r
+ mod = patches[x].diffs[y];\r
+ if (mod[0] != 0)\r
+ index2 = diff_xindex(diff, index1);\r
+ if (mod[0] == 1) // Insertion\r
+ text = text.substring(0, start_loc + index2) + mod[1] + text.substring(start_loc + index2);\r
+ else if (mod[0] == -1) // Deletion\r
+ text = text.substring(0, start_loc + index2) + text.substring(start_loc + diff_xindex(diff, index1 + mod[1].length));\r
+ if (mod[0] != -1)\r
+ index1 += mod[1].length;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ return [text, results];\r
+}\r
+\r
+\r
+function patch_splitmax(patches) {\r
+ // Look through the patches and break up any which are longer than the maximum limit of the match algorithm.\r
+ var bigpatch, patch, patch_size, start1, start2, diff_type, diff_text, precontext, postcontext, empty;\r
+ for (var x=0; x<patches.length; x++) {\r
+ if (patches[x].length1 > MATCH_MAXBITS) {\r
+ bigpatch = patches[x];\r
+ // Remove the big old patch.\r
+ patches.splice(x, 1);\r
+ patch_size = MATCH_MAXBITS;\r
+ start1 = bigpatch.start1;\r
+ start2 = bigpatch.start2;\r
+ precontext = '';\r
+ while (bigpatch.diffs.length != 0) {\r
+ // Create one of several smaller patches.\r
+ patch = new patch_obj();\r
+ empty = true;\r
+ patch.start1 = start1 - precontext.length;\r
+ patch.start2 = start2 - precontext.length;\r
+ if (precontext != '') {\r
+ patch.length1 = patch.length2 = precontext.length;\r
+ patch.diffs.push([0, precontext]);\r
+ }\r
+ while (bigpatch.diffs.length != 0 && patch.length1 < patch_size - PATCH_MARGIN) {\r
+ diff_type = bigpatch.diffs[0][0];\r
+ diff_text = bigpatch.diffs[0][1];\r
+ if (diff_type == 1) {\r
+ // Insertions are harmless.\r
+ patch.length2 += diff_text.length;\r
+ start2 += diff_text.length;\r
+ patch.diffs.push(bigpatch.diffs.shift());\r
+ empty = false;\r
+ } else {\r
+ // Deletion or equality. Only take as much as we can stomach.\r
+ diff_text = diff_text.substring(0, patch_size - patch.length1 - PATCH_MARGIN);\r
+ patch.length1 += diff_text.length;\r
+ start1 += diff_text.length;\r
+ if (diff_type == 0) {\r
+ patch.length2 += diff_text.length;\r
+ start2 += diff_text.length;\r
+ } else {\r
+ empty = false;\r
+ }\r
+ patch.diffs.push([diff_type, diff_text]);\r
+ if (diff_text == bigpatch.diffs[0][1])\r
+ bigpatch.diffs.shift();\r
+ else\r
+ bigpatch.diffs[0][1] = bigpatch.diffs[0][1].substring(diff_text.length);\r
+ }\r
+ }\r
+ // Compute the head context for the next patch.\r
+ precontext = patch.text2();\r
+ precontext = precontext.substring(precontext.length - PATCH_MARGIN);\r
+ // Append the end context for this patch.\r
+ postcontext = bigpatch.text1().substring(0, PATCH_MARGIN);\r
+ if (postcontext != '') {\r
+ patch.length1 += postcontext.length;\r
+ patch.length2 += postcontext.length;\r
+ if (patch.diffs.length > 0 && patch.diffs[patch.diffs.length-1][0] == 0)\r
+ patch.diffs[patch.diffs.length-1][1] += postcontext;\r
+ else\r
+ patch.diffs.push([0, postcontext]);\r
+ }\r
+ if (!empty)\r
+ patches.splice(x++, 0, patch);\r
+ }\r
+ }\r
+ }\r
+}\r
+\r
+\r
+function patch_totext(patches) {\r
+ // Take a list of patches and return a textual representation.\r
+ var text = '';\r
+ for (var x=0; x<patches.length; x++)\r
+ text += patches[x];\r
+ return text;\r
+}\r
+\r
+\r
+function patch_fromtext(text) {\r
+ // Take a textual representation of patches and return a list of patch objects.\r
+ var patches = [];\r
+ text = text.split('\n');\r
+ var patch, m, chars1, chars2, sign, line;\r
+ while (text.length != 0) {\r
+ m = text[0].match(/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/);\r
+ if (!m)\r
+ return alert("Invalid patch string:\n"+text[0]);\r
+ patch = new patch_obj();\r
+ patches.push(patch);\r
+ patch.start1 = parseInt(m[1]);\r
+ if (m[2] == '') {\r
+ patch.start1--;\r
+ patch.length1 = 1;\r
+ } else if (m[2] == '0') {\r
+ patch.length1 = 0;\r
+ } else {\r
+ patch.start1--;\r
+ patch.length1 = parseInt(m[2]);\r
+ }\r
+\r
+ patch.start2 = parseInt(m[3]);\r
+ if (m[4] == '') {\r
+ patch.start2--;\r
+ patch.length2 = 1;\r
+ } else if (m[4] == '0') {\r
+ patch.length2 = 0;\r
+ } else {\r
+ patch.start2--;\r
+ patch.length2 = parseInt(m[4]);\r
+ }\r
+ text.shift();\r
+\r
+ while (text.length != 0) {\r
+ sign = text[0].charAt(0);\r
+ line = decodeURIComponent(text[0].substring(1));\r
+ if (sign == '-') {\r
+ // Deletion.\r
+ patch.diffs.push([-1, line]);\r
+ } else if (sign == '+') {\r
+ // Insertion.\r
+ patch.diffs.push([1, line]);\r
+ } else if (sign == ' ') {\r
+ // Minor equality.\r
+ patch.diffs.push([0, line]);\r
+ } else if (sign == '@') {\r
+ // Start of next patch.\r
+ break;\r
+ } else if (sign == '') {\r
+ // Blank line? Whatever.\r
+ } else {\r
+ // WTF?\r
+ return alert("Invalid patch mode: '"+sign+"'\n"+line);\r
+ }\r
+ text.shift();\r
+ }\r
+ }\r
+ return patches;\r
+}\r
+\r
+// EOF\r