diff options
author | Florian Dold <florian.dold@gmail.com> | 2017-08-14 05:01:11 +0200 |
---|---|---|
committer | Florian Dold <florian.dold@gmail.com> | 2017-08-14 05:02:09 +0200 |
commit | 363723fc84f7b8477592e0105aeb331ec9a017af (patch) | |
tree | 29f92724f34131bac64d6a318dd7e30612e631c7 /node_modules/fast-diff | |
parent | 5634e77ad96bfe1818f6b6ee70b7379652e5487f (diff) | |
download | wallet-core-363723fc84f7b8477592e0105aeb331ec9a017af.tar.xz |
node_modules
Diffstat (limited to 'node_modules/fast-diff')
-rw-r--r-- | node_modules/fast-diff/.npmignore | 1 | ||||
-rw-r--r-- | node_modules/fast-diff/.travis.yml | 2 | ||||
-rw-r--r-- | node_modules/fast-diff/README.md | 24 | ||||
-rw-r--r-- | node_modules/fast-diff/diff.js | 698 | ||||
-rw-r--r-- | node_modules/fast-diff/package.json | 24 | ||||
-rw-r--r-- | node_modules/fast-diff/test.js | 52 |
6 files changed, 801 insertions, 0 deletions
diff --git a/node_modules/fast-diff/.npmignore b/node_modules/fast-diff/.npmignore new file mode 100644 index 000000000..3c3629e64 --- /dev/null +++ b/node_modules/fast-diff/.npmignore @@ -0,0 +1 @@ +node_modules diff --git a/node_modules/fast-diff/.travis.yml b/node_modules/fast-diff/.travis.yml new file mode 100644 index 000000000..ffb9f710a --- /dev/null +++ b/node_modules/fast-diff/.travis.yml @@ -0,0 +1,2 @@ +language: node_js +node_js: '0.10' diff --git a/node_modules/fast-diff/README.md b/node_modules/fast-diff/README.md new file mode 100644 index 000000000..e786a3a60 --- /dev/null +++ b/node_modules/fast-diff/README.md @@ -0,0 +1,24 @@ +# Fast Diff [![Build Status](https://travis-ci.org/jhchen/fast-diff.svg)](https://travis-ci.org/jhchen/fast-diff) + +This is a simplified import of the excellent [diff-match-patch](https://code.google.com/p/google-diff-match-patch/) library by [Neil Fraser](https://neil.fraser.name/) into the Node.js environment. The match and patch parts are removed, as well as all the extra diff options. What remains is incredibly fast diffing between two strings. + + The diff function is an implementation of ["An O(ND) Difference Algorithm and its Variations" (Myers, 1986)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.6927&rep=rep1&type=pdf) with the suggested divide and conquer strategy along with several [optimizations](http://neil.fraser.name/news/2007/10/09/) Neil added. + +```js +var diff = require('fast-diff'); + +var good = 'Good dog'; +var bad = 'Bad dog'; + +var result = diff(good, bad); +// [[-1, "Goo"], [1, "Ba"], [0, "d dog"]] + +// Respect suggested edit location (cursor position), added in v1.1 +diff('aaa', 'aaaa', 1) +// [[0, "a"], [1, "a"], [0, "aa"]] + +// For convenience +diff.INSERT === 1; +diff.EQUAL === 0; +diff.DELETE === -1; +``` diff --git a/node_modules/fast-diff/diff.js b/node_modules/fast-diff/diff.js new file mode 100644 index 000000000..c6e3f3ddd --- /dev/null +++ b/node_modules/fast-diff/diff.js @@ -0,0 +1,698 @@ +/** + * This library modifies the diff-patch-match library by Neil Fraser + * by removing the patch and match functionality and certain advanced + * options in the diff function. The original license is as follows: + * + * === + * + * Diff Match and Patch + * + * Copyright 2006 Google Inc. + * http://code.google.com/p/google-diff-match-patch/ + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + + +/** + * The data structure representing a diff is an array of tuples: + * [[DIFF_DELETE, 'Hello'], [DIFF_INSERT, 'Goodbye'], [DIFF_EQUAL, ' world.']] + * which means: delete 'Hello', add 'Goodbye' and keep ' world.' + */ +var DIFF_DELETE = -1; +var DIFF_INSERT = 1; +var DIFF_EQUAL = 0; + + +/** + * Find the differences between two texts. Simplifies the problem by stripping + * any common prefix or suffix off the texts before diffing. + * @param {string} text1 Old string to be diffed. + * @param {string} text2 New string to be diffed. + * @param {Int} cursor_pos Expected edit position in text1 (optional) + * @return {Array} Array of diff tuples. + */ +function diff_main(text1, text2, cursor_pos) { + // Check for equality (speedup). + if (text1 == text2) { + if (text1) { + return [[DIFF_EQUAL, text1]]; + } + return []; + } + + // Check cursor_pos within bounds + if (cursor_pos < 0 || text1.length < cursor_pos) { + cursor_pos = null; + } + + // Trim off common prefix (speedup). + var commonlength = diff_commonPrefix(text1, text2); + var commonprefix = text1.substring(0, commonlength); + text1 = text1.substring(commonlength); + text2 = text2.substring(commonlength); + + // Trim off common suffix (speedup). + commonlength = diff_commonSuffix(text1, text2); + var commonsuffix = text1.substring(text1.length - commonlength); + text1 = text1.substring(0, text1.length - commonlength); + text2 = text2.substring(0, text2.length - commonlength); + + // Compute the diff on the middle block. + var diffs = diff_compute_(text1, text2); + + // Restore the prefix and suffix. + if (commonprefix) { + diffs.unshift([DIFF_EQUAL, commonprefix]); + } + if (commonsuffix) { + diffs.push([DIFF_EQUAL, commonsuffix]); + } + diff_cleanupMerge(diffs); + if (cursor_pos != null) { + diffs = fix_cursor(diffs, cursor_pos); + } + return diffs; +}; + + +/** + * Find the differences between two texts. Assumes that the texts do not + * have any common prefix or suffix. + * @param {string} text1 Old string to be diffed. + * @param {string} text2 New string to be diffed. + * @return {Array} Array of diff tuples. + */ +function diff_compute_(text1, text2) { + var diffs; + + if (!text1) { + // Just add some text (speedup). + return [[DIFF_INSERT, text2]]; + } + + if (!text2) { + // Just delete some text (speedup). + return [[DIFF_DELETE, text1]]; + } + + var longtext = text1.length > text2.length ? text1 : text2; + var shorttext = text1.length > text2.length ? text2 : text1; + var i = longtext.indexOf(shorttext); + if (i != -1) { + // Shorter text is inside the longer text (speedup). + diffs = [[DIFF_INSERT, longtext.substring(0, i)], + [DIFF_EQUAL, shorttext], + [DIFF_INSERT, longtext.substring(i + shorttext.length)]]; + // Swap insertions for deletions if diff is reversed. + if (text1.length > text2.length) { + diffs[0][0] = diffs[2][0] = DIFF_DELETE; + } + return diffs; + } + + if (shorttext.length == 1) { + // Single character string. + // After the previous speedup, the character can't be an equality. + return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]]; + } + + // Check to see if the problem can be split in two. + var hm = diff_halfMatch_(text1, text2); + if (hm) { + // A half-match was found, sort out the return data. + var text1_a = hm[0]; + var text1_b = hm[1]; + var text2_a = hm[2]; + var text2_b = hm[3]; + var mid_common = hm[4]; + // Send both pairs off for separate processing. + var diffs_a = diff_main(text1_a, text2_a); + var diffs_b = diff_main(text1_b, text2_b); + // Merge the results. + return diffs_a.concat([[DIFF_EQUAL, mid_common]], diffs_b); + } + + return diff_bisect_(text1, text2); +}; + + +/** + * Find the 'middle snake' of a diff, split the problem in two + * and return the recursively constructed diff. + * See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations. + * @param {string} text1 Old string to be diffed. + * @param {string} text2 New string to be diffed. + * @return {Array} Array of diff tuples. + * @private + */ +function diff_bisect_(text1, text2) { + // Cache the text lengths to prevent multiple calls. + var text1_length = text1.length; + var text2_length = text2.length; + var max_d = Math.ceil((text1_length + text2_length) / 2); + var v_offset = max_d; + var v_length = 2 * max_d; + var v1 = new Array(v_length); + var v2 = new Array(v_length); + // Setting all elements to -1 is faster in Chrome & Firefox than mixing + // integers and undefined. + for (var x = 0; x < v_length; x++) { + v1[x] = -1; + v2[x] = -1; + } + v1[v_offset + 1] = 0; + v2[v_offset + 1] = 0; + var delta = text1_length - text2_length; + // If the total number of characters is odd, then the front path will collide + // with the reverse path. + var front = (delta % 2 != 0); + // Offsets for start and end of k loop. + // Prevents mapping of space beyond the grid. + var k1start = 0; + var k1end = 0; + var k2start = 0; + var k2end = 0; + for (var d = 0; d < max_d; d++) { + // Walk the front path one step. + for (var k1 = -d + k1start; k1 <= d - k1end; k1 += 2) { + var k1_offset = v_offset + k1; + var x1; + if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) { + x1 = v1[k1_offset + 1]; + } else { + x1 = v1[k1_offset - 1] + 1; + } + var y1 = x1 - k1; + while (x1 < text1_length && y1 < text2_length && + text1.charAt(x1) == text2.charAt(y1)) { + x1++; + y1++; + } + v1[k1_offset] = x1; + if (x1 > text1_length) { + // Ran off the right of the graph. + k1end += 2; + } else if (y1 > text2_length) { + // Ran off the bottom of the graph. + k1start += 2; + } else if (front) { + var k2_offset = v_offset + delta - k1; + if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) { + // Mirror x2 onto top-left coordinate system. + var x2 = text1_length - v2[k2_offset]; + if (x1 >= x2) { + // Overlap detected. + return diff_bisectSplit_(text1, text2, x1, y1); + } + } + } + } + + // Walk the reverse path one step. + for (var k2 = -d + k2start; k2 <= d - k2end; k2 += 2) { + var k2_offset = v_offset + k2; + var x2; + if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) { + x2 = v2[k2_offset + 1]; + } else { + x2 = v2[k2_offset - 1] + 1; + } + var y2 = x2 - k2; + while (x2 < text1_length && y2 < text2_length && + text1.charAt(text1_length - x2 - 1) == + text2.charAt(text2_length - y2 - 1)) { + x2++; + y2++; + } + v2[k2_offset] = x2; + if (x2 > text1_length) { + // Ran off the left of the graph. + k2end += 2; + } else if (y2 > text2_length) { + // Ran off the top of the graph. + k2start += 2; + } else if (!front) { + var k1_offset = v_offset + delta - k2; + if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) { + var x1 = v1[k1_offset]; + var y1 = v_offset + x1 - k1_offset; + // Mirror x2 onto top-left coordinate system. + x2 = text1_length - x2; + if (x1 >= x2) { + // Overlap detected. + return diff_bisectSplit_(text1, text2, x1, y1); + } + } + } + } + } + // Diff took too long and hit the deadline or + // number of diffs equals number of characters, no commonality at all. + return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]]; +}; + + +/** + * Given the location of the 'middle snake', split the diff in two parts + * and recurse. + * @param {string} text1 Old string to be diffed. + * @param {string} text2 New string to be diffed. + * @param {number} x Index of split point in text1. + * @param {number} y Index of split point in text2. + * @return {Array} Array of diff tuples. + */ +function diff_bisectSplit_(text1, text2, x, y) { + var text1a = text1.substring(0, x); + var text2a = text2.substring(0, y); + var text1b = text1.substring(x); + var text2b = text2.substring(y); + + // Compute both diffs serially. + var diffs = diff_main(text1a, text2a); + var diffsb = diff_main(text1b, text2b); + + return diffs.concat(diffsb); +}; + + +/** + * Determine the common prefix of two strings. + * @param {string} text1 First string. + * @param {string} text2 Second string. + * @return {number} The number of characters common to the start of each + * string. + */ +function diff_commonPrefix(text1, text2) { + // Quick check for common null cases. + if (!text1 || !text2 || text1.charAt(0) != text2.charAt(0)) { + return 0; + } + // Binary search. + // Performance analysis: http://neil.fraser.name/news/2007/10/09/ + var pointermin = 0; + var pointermax = Math.min(text1.length, text2.length); + var pointermid = pointermax; + var pointerstart = 0; + while (pointermin < pointermid) { + if (text1.substring(pointerstart, pointermid) == + text2.substring(pointerstart, pointermid)) { + pointermin = pointermid; + pointerstart = pointermin; + } else { + pointermax = pointermid; + } + pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin); + } + return pointermid; +}; + + +/** + * Determine the common suffix of two strings. + * @param {string} text1 First string. + * @param {string} text2 Second string. + * @return {number} The number of characters common to the end of each string. + */ +function diff_commonSuffix(text1, text2) { + // Quick check for common null cases. + if (!text1 || !text2 || + text1.charAt(text1.length - 1) != text2.charAt(text2.length - 1)) { + return 0; + } + // Binary search. + // Performance analysis: http://neil.fraser.name/news/2007/10/09/ + var pointermin = 0; + var pointermax = Math.min(text1.length, text2.length); + var pointermid = pointermax; + var pointerend = 0; + while (pointermin < pointermid) { + if (text1.substring(text1.length - pointermid, text1.length - pointerend) == + text2.substring(text2.length - pointermid, text2.length - pointerend)) { + pointermin = pointermid; + pointerend = pointermin; + } else { + pointermax = pointermid; + } + pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin); + } + return pointermid; +}; + + +/** + * Do the two texts share a substring which is at least half the length of the + * longer text? + * This speedup can produce non-minimal diffs. + * @param {string} text1 First string. + * @param {string} text2 Second string. + * @return {Array.<string>} Five element Array, containing the prefix of + * text1, the suffix of text1, the prefix of text2, the suffix of + * text2 and the common middle. Or null if there was no match. + */ +function diff_halfMatch_(text1, text2) { + var longtext = text1.length > text2.length ? text1 : text2; + var shorttext = text1.length > text2.length ? text2 : text1; + if (longtext.length < 4 || shorttext.length * 2 < longtext.length) { + return null; // Pointless. + } + + /** + * Does a substring of shorttext exist within longtext such that the substring + * is at least half the length of longtext? + * Closure, but does not reference any external variables. + * @param {string} longtext Longer string. + * @param {string} shorttext Shorter string. + * @param {number} i Start index of quarter length substring within longtext. + * @return {Array.<string>} Five element Array, containing the prefix of + * longtext, the suffix of longtext, the prefix of shorttext, the suffix + * of shorttext and the common middle. Or null if there was no match. + * @private + */ + function diff_halfMatchI_(longtext, shorttext, i) { + // Start with a 1/4 length substring at position i as a seed. + var seed = longtext.substring(i, i + Math.floor(longtext.length / 4)); + var j = -1; + var best_common = ''; + var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b; + while ((j = shorttext.indexOf(seed, j + 1)) != -1) { + var prefixLength = diff_commonPrefix(longtext.substring(i), + shorttext.substring(j)); + var suffixLength = diff_commonSuffix(longtext.substring(0, i), + shorttext.substring(0, j)); + if (best_common.length < suffixLength + prefixLength) { + best_common = shorttext.substring(j - suffixLength, j) + + shorttext.substring(j, j + prefixLength); + best_longtext_a = longtext.substring(0, i - suffixLength); + best_longtext_b = longtext.substring(i + prefixLength); + best_shorttext_a = shorttext.substring(0, j - suffixLength); + best_shorttext_b = shorttext.substring(j + prefixLength); + } + } + if (best_common.length * 2 >= longtext.length) { + return [best_longtext_a, best_longtext_b, + best_shorttext_a, best_shorttext_b, best_common]; + } else { + return null; + } + } + + // First check if the second quarter is the seed for a half-match. + var hm1 = diff_halfMatchI_(longtext, shorttext, + Math.ceil(longtext.length / 4)); + // Check again based on the third quarter. + var hm2 = diff_halfMatchI_(longtext, shorttext, + Math.ceil(longtext.length / 2)); + var hm; + if (!hm1 && !hm2) { + return null; + } else if (!hm2) { + hm = hm1; + } else if (!hm1) { + hm = hm2; + } else { + // Both matched. Select the longest. + hm = hm1[4].length > hm2[4].length ? hm1 : hm2; + } + + // A half-match was found, sort out the return data. + var text1_a, text1_b, text2_a, text2_b; + if (text1.length > text2.length) { + text1_a = hm[0]; + text1_b = hm[1]; + text2_a = hm[2]; + text2_b = hm[3]; + } else { + text2_a = hm[0]; + text2_b = hm[1]; + text1_a = hm[2]; + text1_b = hm[3]; + } + var mid_common = hm[4]; + return [text1_a, text1_b, text2_a, text2_b, mid_common]; +}; + + +/** + * Reorder and merge like edit sections. Merge equalities. + * Any edit section can move as long as it doesn't cross an equality. + * @param {Array} diffs Array of diff tuples. + */ +function diff_cleanupMerge(diffs) { + diffs.push([DIFF_EQUAL, '']); // Add a dummy entry at the end. + var pointer = 0; + var count_delete = 0; + var count_insert = 0; + var text_delete = ''; + var text_insert = ''; + var commonlength; + while (pointer < diffs.length) { + switch (diffs[pointer][0]) { + case DIFF_INSERT: + count_insert++; + text_insert += diffs[pointer][1]; + pointer++; + break; + case DIFF_DELETE: + count_delete++; + text_delete += diffs[pointer][1]; + pointer++; + break; + case DIFF_EQUAL: + // Upon reaching an equality, check for prior redundancies. + if (count_delete + count_insert > 1) { + if (count_delete !== 0 && count_insert !== 0) { + // Factor out any common prefixies. + commonlength = diff_commonPrefix(text_insert, text_delete); + if (commonlength !== 0) { + if ((pointer - count_delete - count_insert) > 0 && + diffs[pointer - count_delete - count_insert - 1][0] == + DIFF_EQUAL) { + diffs[pointer - count_delete - count_insert - 1][1] += + text_insert.substring(0, commonlength); + } else { + diffs.splice(0, 0, [DIFF_EQUAL, + text_insert.substring(0, commonlength)]); + pointer++; + } + text_insert = text_insert.substring(commonlength); + text_delete = text_delete.substring(commonlength); + } + // Factor out any common suffixies. + commonlength = diff_commonSuffix(text_insert, text_delete); + if (commonlength !== 0) { + diffs[pointer][1] = text_insert.substring(text_insert.length - + commonlength) + diffs[pointer][1]; + text_insert = text_insert.substring(0, text_insert.length - + commonlength); + text_delete = text_delete.substring(0, text_delete.length - + commonlength); + } + } + // Delete the offending records and add the merged ones. + if (count_delete === 0) { + diffs.splice(pointer - count_insert, + count_delete + count_insert, [DIFF_INSERT, text_insert]); + } else if (count_insert === 0) { + diffs.splice(pointer - count_delete, + count_delete + count_insert, [DIFF_DELETE, text_delete]); + } else { + diffs.splice(pointer - count_delete - count_insert, + count_delete + count_insert, [DIFF_DELETE, text_delete], + [DIFF_INSERT, text_insert]); + } + pointer = pointer - count_delete - count_insert + + (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1; + } else if (pointer !== 0 && diffs[pointer - 1][0] == DIFF_EQUAL) { + // Merge this equality with the previous one. + diffs[pointer - 1][1] += diffs[pointer][1]; + diffs.splice(pointer, 1); + } else { + pointer++; + } + count_insert = 0; + count_delete = 0; + text_delete = ''; + text_insert = ''; + break; + } + } + if (diffs[diffs.length - 1][1] === '') { + diffs.pop(); // Remove the dummy entry at the end. + } + + // Second pass: look for single edits surrounded on both sides by equalities + // which can be shifted sideways to eliminate an equality. + // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC + var changes = false; + pointer = 1; + // Intentionally ignore the first and last element (don't need checking). + while (pointer < diffs.length - 1) { + if (diffs[pointer - 1][0] == DIFF_EQUAL && + diffs[pointer + 1][0] == DIFF_EQUAL) { + // This is a single edit surrounded by equalities. + if (diffs[pointer][1].substring(diffs[pointer][1].length - + diffs[pointer - 1][1].length) == diffs[pointer - 1][1]) { + // Shift the edit over the previous equality. + diffs[pointer][1] = diffs[pointer - 1][1] + + diffs[pointer][1].substring(0, diffs[pointer][1].length - + diffs[pointer - 1][1].length); + diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1]; + diffs.splice(pointer - 1, 1); + changes = true; + } else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) == + diffs[pointer + 1][1]) { + // Shift the edit over the next equality. + diffs[pointer - 1][1] += diffs[pointer + 1][1]; + diffs[pointer][1] = + diffs[pointer][1].substring(diffs[pointer + 1][1].length) + + diffs[pointer + 1][1]; + diffs.splice(pointer + 1, 1); + changes = true; + } + } + pointer++; + } + // If shifts were made, the diff needs reordering and another shift sweep. + if (changes) { + diff_cleanupMerge(diffs); + } +}; + + +var diff = diff_main; +diff.INSERT = DIFF_INSERT; +diff.DELETE = DIFF_DELETE; +diff.EQUAL = DIFF_EQUAL; + +module.exports = diff; + +/* + * Modify a diff such that the cursor position points to the start of a change: + * E.g. + * cursor_normalize_diff([[DIFF_EQUAL, 'abc']], 1) + * => [1, [[DIFF_EQUAL, 'a'], [DIFF_EQUAL, 'bc']]] + * cursor_normalize_diff([[DIFF_INSERT, 'new'], [DIFF_DELETE, 'xyz']], 2) + * => [2, [[DIFF_INSERT, 'new'], [DIFF_DELETE, 'xy'], [DIFF_DELETE, 'z']]] + * + * @param {Array} diffs Array of diff tuples + * @param {Int} cursor_pos Suggested edit position. Must not be out of bounds! + * @return {Array} A tuple [cursor location in the modified diff, modified diff] + */ +function cursor_normalize_diff (diffs, cursor_pos) { + if (cursor_pos === 0) { + return [DIFF_EQUAL, diffs]; + } + for (var current_pos = 0, i = 0; i < diffs.length; i++) { + var d = diffs[i]; + if (d[0] === DIFF_DELETE || d[0] === DIFF_EQUAL) { + var next_pos = current_pos + d[1].length; + if (cursor_pos === next_pos) { + return [i + 1, diffs]; + } else if (cursor_pos < next_pos) { + // copy to prevent side effects + diffs = diffs.slice(); + // split d into two diff changes + var split_pos = cursor_pos - current_pos; + var d_left = [d[0], d[1].slice(0, split_pos)]; + var d_right = [d[0], d[1].slice(split_pos)]; + diffs.splice(i, 1, d_left, d_right); + return [i + 1, diffs]; + } else { + current_pos = next_pos; + } + } + } + throw new Error('cursor_pos is out of bounds!') +} + +/* + * Modify a diff such that the edit position is "shifted" to the proposed edit location (cursor_position). + * + * Case 1) + * Check if a naive shift is possible: + * [0, X], [ 1, Y] -> [ 1, Y], [0, X] (if X + Y === Y + X) + * [0, X], [-1, Y] -> [-1, Y], [0, X] (if X + Y === Y + X) - holds same result + * Case 2) + * Check if the following shifts are possible: + * [0, 'pre'], [ 1, 'prefix'] -> [ 1, 'pre'], [0, 'pre'], [ 1, 'fix'] + * [0, 'pre'], [-1, 'prefix'] -> [-1, 'pre'], [0, 'pre'], [-1, 'fix'] + * ^ ^ + * d d_next + * + * @param {Array} diffs Array of diff tuples + * @param {Int} cursor_pos Suggested edit position. Must not be out of bounds! + * @return {Array} Array of diff tuples + */ +function fix_cursor (diffs, cursor_pos) { + var norm = cursor_normalize_diff(diffs, cursor_pos); + var ndiffs = norm[1]; + var cursor_pointer = norm[0]; + var d = ndiffs[cursor_pointer]; + var d_next = ndiffs[cursor_pointer + 1]; + + if (d == null) { + // Text was deleted from end of original string, + // cursor is now out of bounds in new string + return diffs; + } else if (d[0] !== DIFF_EQUAL) { + // A modification happened at the cursor location. + // This is the expected outcome, so we can return the original diff. + return diffs; + } else { + if (d_next != null && d[1] + d_next[1] === d_next[1] + d[1]) { + // Case 1) + // It is possible to perform a naive shift + ndiffs.splice(cursor_pointer, 2, d_next, d) + return merge_tuples(ndiffs, cursor_pointer, 2) + } else if (d_next != null && d_next[1].indexOf(d[1]) === 0) { + // Case 2) + // d[1] is a prefix of d_next[1] + // We can assume that d_next[0] !== 0, since d[0] === 0 + // Shift edit locations.. + ndiffs.splice(cursor_pointer, 2, [d_next[0], d[1]], [0, d[1]]); + var suffix = d_next[1].slice(d[1].length); + if (suffix.length > 0) { + ndiffs.splice(cursor_pointer + 2, 0, [d_next[0], suffix]); + } + return merge_tuples(ndiffs, cursor_pointer, 3) + } else { + // Not possible to perform any modification + return diffs; + } + } + +} + +/* + * Try to merge tuples with their neigbors in a given range. + * E.g. [0, 'a'], [0, 'b'] -> [0, 'ab'] + * + * @param {Array} diffs Array of diff tuples. + * @param {Int} start Position of the first element to merge (diffs[start] is also merged with diffs[start - 1]). + * @param {Int} length Number of consecutive elements to check. + * @return {Array} Array of merged diff tuples. + */ +function merge_tuples (diffs, start, length) { + // Check from (start-1) to (start+length). + for (var i = start + length - 1; i >= 0 && i >= start - 1; i--) { + if (i + 1 < diffs.length) { + var left_d = diffs[i]; + var right_d = diffs[i+1]; + if (left_d[0] === right_d[1]) { + diffs.splice(i, 2, [left_d[0], left_d[1] + right_d[1]]); + } + } + } + return diffs; +} diff --git a/node_modules/fast-diff/package.json b/node_modules/fast-diff/package.json new file mode 100644 index 000000000..054ea84a2 --- /dev/null +++ b/node_modules/fast-diff/package.json @@ -0,0 +1,24 @@ +{ + "name": "fast-diff", + "version": "1.1.1", + "description": "Fast Javascript text diff", + "author": "Jason Chen <jhchen7@gmail.com>", + "main": "diff.js", + "devDependencies": { + "googlediff": "~0.1.0", + "lodash": "~3.9.3", + "seedrandom": "~2.4.0" + }, + "repository": { + "type": "git", + "url": "https://github.com/jhchen/fast-diff" + }, + "bugs": { + "url": "https://github.com/jhchen/fast-diff/issues" + }, + "scripts": { + "test": "node test.js" + }, + "license": "Apache-2.0", + "keywords": ["diff"] +} diff --git a/node_modules/fast-diff/test.js b/node_modules/fast-diff/test.js new file mode 100644 index 000000000..5a33eed74 --- /dev/null +++ b/node_modules/fast-diff/test.js @@ -0,0 +1,52 @@ +var _ = require('lodash'); +var googlediff = require('googlediff'); +var seedrandom = require('seedrandom'); +var diff = require('./diff.js'); + +googlediff = new googlediff(); + +var ITERATIONS = 10000; +var ALPHABET = 'GATTACA'; +var LENGTH = 100; + +var seed = Math.floor(Math.random() * 10000); +var random = seedrandom(seed); + +console.log('Running computing ' + ITERATIONS + ' diffs with seed ' + seed + '...'); + +console.log('Generating strings...'); +var strings = []; +for(var i = 0; i <= ITERATIONS; ++i) { + var chars = []; + for(var l = 0; l < LENGTH; ++l) { + var letter = ALPHABET.substr(Math.floor(random() * ALPHABET.length), 1); + chars.push(letter); + } + strings.push(chars.join('')); +} + +console.log('Running tests *without* cursor information...'); +for(var i = 0; i < ITERATIONS; ++i) { + var result = diff(strings[i], strings[i+1]); + var expected = googlediff.diff_main(strings[i], strings[i+1]); + if (!_.isEqual(result, expected)) { + console.log('Expected', expected); + console.log('Result', result); + throw new Error('Diff produced difference results.'); + } +} + +console.log('Running tests *with* cursor information'); +for(var i = 0; i < ITERATIONS; ++i) { + var cursor_pos = Math.floor(random() * strings[i].length + 1); + var diffs = diff(strings[i], strings[i+1], cursor_pos); + var patch = googlediff.patch_make(strings[i], strings[i+1], diffs); + var expected = googlediff.patch_apply(patch, strings[i])[0]; + if (expected !== strings[i+1]) { + console.log('Expected', expected); + console.log('Result', strings[i+1]); + throw new Error('Diff produced difference results.'); + } +} + +console.log("Success!"); |