You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 

334 lines
10 KiB

var _ = require('lodash');
var seedrandom = require('seedrandom');
var diff = require('./diff.js');
var ITERATIONS = 10000;
var ALPHABET = 'GATTACA';
var LENGTH = 100;
var EMOJI_MAX_LENGTH = 50;
var seed = Math.floor(Math.random() * 10000);
var random = seedrandom(seed);
console.log('Running regression tests...');
[
['GAATAAAAAAAGATTAACAT', 'AAAAACTTGTAATTAACAAC'],
['๐Ÿ”˜๐Ÿค˜๐Ÿ”—๐Ÿ”—', '๐Ÿ”—๐Ÿค—๐Ÿค—__๐Ÿค—๐Ÿค˜๐Ÿค˜๐Ÿค—๐Ÿ”—๐Ÿค˜๐Ÿ”—'],
['๐Ÿ”—๐Ÿค—๐Ÿค—__๐Ÿค—๐Ÿค˜๐Ÿค˜๐Ÿค—๐Ÿ”—๐Ÿค˜๐Ÿ”—', '๐Ÿค—๐Ÿค˜๐Ÿ”˜'],
['๐Ÿค˜๐Ÿค˜๐Ÿ”˜๐Ÿ”˜_๐Ÿ”˜๐Ÿ”—๐Ÿค˜๐Ÿค—๐Ÿค—__๐Ÿ”—๐Ÿค˜', '๐Ÿค˜๐Ÿ”˜๐Ÿค˜๐Ÿ”—๐Ÿค˜๐Ÿค˜๐Ÿ”—๐Ÿค—๐Ÿค˜๐Ÿ”˜๐Ÿ”˜'],
['๐Ÿค—๐Ÿค˜๐Ÿค—๐Ÿ”˜๐Ÿค˜๐Ÿ”˜๐Ÿค—_๐Ÿค—๐Ÿ”—๐Ÿค˜๐Ÿค—_๐Ÿค˜๐Ÿ”—๐Ÿค—๐Ÿค˜๐Ÿ”—๐Ÿค˜๐Ÿค˜๐Ÿค˜๐Ÿ”—๐Ÿค—๐Ÿ”—๐Ÿ”—๐Ÿ”—๐Ÿค—_๐Ÿค˜๐Ÿ”—๐Ÿค—๐Ÿค—๐Ÿ”˜๐Ÿค—๐Ÿค—๐Ÿค˜๐Ÿค—',
'_๐Ÿค—๐Ÿค˜_๐Ÿค˜๐Ÿค˜๐Ÿ”˜๐Ÿค—๐Ÿ”˜๐Ÿค˜_๐Ÿ”˜๐Ÿค—๐Ÿ”—๐Ÿ”˜๐Ÿ”—๐Ÿค˜๐Ÿ”—๐Ÿค˜๐Ÿค—๐Ÿ”—๐Ÿ”—๐Ÿ”—๐Ÿค˜๐Ÿ”˜_๐Ÿค—๐Ÿค˜๐Ÿค˜๐Ÿค˜__๐Ÿค˜_๐Ÿ”˜๐Ÿค˜๐Ÿค˜_๐Ÿ”—๐Ÿค˜๐Ÿ”˜'],
['๐Ÿ”—๐Ÿค˜๐Ÿค—๐Ÿ”˜๐Ÿ”˜๐Ÿค—', '๐Ÿค˜๐Ÿค˜๐Ÿค˜๐Ÿค—๐Ÿ”˜๐Ÿ”—๐Ÿ”—'],
['๐Ÿ”˜_๐Ÿ”—๐Ÿ”—๐Ÿ”—๐Ÿค—๐Ÿ”—', '๐Ÿค˜๐Ÿค—๐Ÿ”—๐Ÿค—_๐Ÿค˜๐Ÿ”˜_'],
].forEach(function (data) {
var result = diff(data[0], data[1]);
applyDiff(result, data[0], data[1]);
});
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 fuzz tests *without* cursor information...');
for (var i = 0; i < ITERATIONS; ++i) {
var result = diff(strings[i], strings[i + 1]);
applyDiff(result, strings[i], strings[i + 1]);
}
console.log('Running fuzz 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);
applyDiff(diffs, strings[i], strings[i + 1]);
}
function parseDiff(str) {
if (!str) {
return [];
}
return str.split(/(?=[+\-=])/).map(function (piece) {
var symbol = piece.charAt(0);
var text = piece.slice(1);
return [
symbol === '+' ? diff.INSERT : symbol === '-' ? diff.DELETE : diff.EQUAL,
text
]
});
}
console.log('Running cursor tests');
[
['', 0, '', null, ''],
['', 0, 'a', null, '+a'],
['a', 0, 'aa', null, '+a=a'],
['a', 1, 'aa', null, '=a+a'],
['aa', 0, 'aaa', null, '+a=aa'],
['aa', 1, 'aaa', null, '=a+a=a'],
['aa', 2, 'aaa', null, '=aa+a'],
['aaa', 0, 'aaaa', null, '+a=aaa'],
['aaa', 1, 'aaaa', null, '=a+a=aa'],
['aaa', 2, 'aaaa', null, '=aa+a=a'],
['aaa', 3, 'aaaa', null, '=aaa+a'],
['a', 0, '', null, '-a'],
['a', 1, '', null, '-a'],
['aa', 0, 'a', null, '-a=a'],
['aa', 1, 'a', null, '-a=a'],
['aa', 2, 'a', null, '=a-a'],
['aaa', 0, 'aa', null, '-a=aa'],
['aaa', 1, 'aa', null, '-a=aa'],
['aaa', 2, 'aa', null, '=a-a=a'],
['aaa', 3, 'aa', null, '=aa-a'],
['', 0, '', 0, ''],
['', 0, 'a', 1, '+a'],
['a', 0, 'aa', 1, '+a=a'],
['a', 1, 'aa', 2, '=a+a'],
['aa', 0, 'aaa', 1, '+a=aa'],
['aa', 1, 'aaa', 2, '=a+a=a'],
['aa', 2, 'aaa', 3, '=aa+a'],
['aaa', 0, 'aaaa', 1, '+a=aaa'],
['aaa', 1, 'aaaa', 2, '=a+a=aa'],
['aaa', 2, 'aaaa', 3, '=aa+a=a'],
['aaa', 3, 'aaaa', 4, '=aaa+a'],
['a', 1, '', 0, '-a'],
['aa', 1, 'a', 0, '-a=a'],
['aa', 2, 'a', 1, '=a-a'],
['aaa', 1, 'aa', 0, '-a=aa'],
['aaa', 2, 'aa', 1, '=a-a=a'],
['aaa', 3, 'aa', 2, '=aa-a'],
['a', 1, '', 0, '-a'],
['aa', 1, 'a', 0, '-a=a'],
['aa', 2, 'a', 1, '=a-a'],
['aaa', 1, 'aa', 0, '-a=aa'],
['aaa', 2, 'aa', 1, '=a-a=a'],
['aaa', 3, 'aa', 2, '=aa-a'],
// forward-delete
['a', 0, '', 0, '-a'],
['aa', 0, 'a', 0, '-a=a'],
['aa', 1, 'a', 1, '=a-a'],
['aaa', 0, 'aa', 0, '-a=aa'],
['aaa', 1, 'aa', 1, '=a-a=a'],
['aaa', 2, 'aa', 2, '=aa-a'],
['bob', 0, 'bobob', null, '+bo=bob'],
['bob', 1, 'bobob', null, '=b+ob=ob'],
['bob', 2, 'bobob', null, '=bo+bo=b'],
['bob', 3, 'bobob', null, '=bob+ob'],
['bob', 0, 'bobob', 2, '+bo=bob'],
['bob', 1, 'bobob', 3, '=b+ob=ob'],
['bob', 2, 'bobob', 4, '=bo+bo=b'],
['bob', 3, 'bobob', 5, '=bob+ob'],
['bobob', 2, 'bob', null, '-bo=bob'],
['bobob', 3, 'bob', null, '=b-ob=ob'],
['bobob', 4, 'bob', null, '=bo-bo=b'],
['bobob', 5, 'bob', null, '=bob-ob'],
['bobob', 2, 'bob', 0, '-bo=bob'],
['bobob', 3, 'bob', 1, '=b-ob=ob'],
['bobob', 4, 'bob', 2, '=bo-bo=b'],
['bobob', 5, 'bob', 3, '=bob-ob'],
['bob', 1, 'b', null, '=b-ob'],
['hello', [0, 5], 'h', 1, '-hello+h'],
['yay', [0, 3], 'y', 1, '-yay+y'],
['bobob', [1, 4], 'bob', 2, '=b-obo+o=b'],
].forEach(function (data) {
var oldText = data[0];
var newText = data[2];
var oldRange = typeof data[1] === 'number' ?
{ index: data[1], length: 0 } :
{ index: data[1][0], length: data[1][1] - data[1][0] };
var newRange = typeof data[3] === 'number' ?
{ index: data[3], length: 0 } :
data[3] === null ? null : { index: data[3][0], length: data[3][1] - data[3][0] };
var expected = parseDiff(data[4]);
if (newRange === null && typeof data[1] !== 'number') {
throw new Error('invalid test case');
}
var cursorInfo = newRange === null ? data[1] : {
oldRange: oldRange,
newRange: newRange,
};
doCursorTest(oldText, newText, cursorInfo, expected);
doCursorTest('x' + oldText, 'x' + newText, shiftCursorInfo(cursorInfo, 1), diffPrepend(expected, 'x'));
doCursorTest(oldText + 'x', newText + 'x', cursorInfo, diffAppend(expected, 'x'));
});
function diffPrepend(tuples, text) {
if (tuples.length > 0 && tuples[0][0] === diff.EQUAL) {
return [[diff.EQUAL, text + tuples[0][1]]].concat(tuples.slice(1));
} else {
return [[diff.EQUAL, text]].concat(tuples);
}
}
function diffAppend(tuples, text) {
var lastTuple = tuples[tuples.length - 1];
if (lastTuple && lastTuple[0] === diff.EQUAL) {
return tuples.slice(0, -1).concat([[diff.EQUAL, lastTuple[1] + text]]);
} else {
return tuples.concat([[diff.EQUAL, text]]);
}
}
function shiftCursorInfo(cursorInfo, amount) {
if (typeof cursorInfo === 'number') {
return cursorInfo + amount;
} else {
return {
oldRange: {
index: cursorInfo.oldRange.index + amount,
length: cursorInfo.oldRange.length,
},
newRange: {
index: cursorInfo.newRange.index + amount,
length: cursorInfo.newRange.length,
},
}
}
}
function doCursorTest(oldText, newText, cursorInfo, expected) {
var result = diff(oldText, newText, cursorInfo);
if (!_.isEqual(result, expected)) {
console.log([oldText, newText, cursorInfo]);
console.log(result, '!==', expected);
throw new Error('cursor test failed');
}
}
console.log('Running emoji tests');
[
['๐Ÿถ', '๐Ÿฏ', '-๐Ÿถ+๐Ÿฏ'],
['๐Ÿ‘จ๐Ÿฝ', '๐Ÿ‘ฉ๐Ÿฝ', '-๐Ÿ‘จ+๐Ÿ‘ฉ=๐Ÿฝ'],
['๐Ÿ‘ฉ๐Ÿผ', '๐Ÿ‘ฉ๐Ÿฝ', '=๐Ÿ‘ฉ-๐Ÿผ+๐Ÿฝ'],
['๐Ÿ๐ŸŽ', '๐ŸŽ', '-๐Ÿ=๐ŸŽ'],
['๐ŸŽ', '๐Ÿ๐ŸŽ', '+๐Ÿ=๐ŸŽ'],
].forEach(function (data) {
var oldText = data[0];
var newText = data[1];
var expected = parseDiff(data[2]);
doEmojiTest(oldText, newText, expected);
doEmojiTest('x' + oldText, 'x' + newText, diffPrepend(expected, 'x'));
doEmojiTest(oldText + 'x', newText + 'x', diffAppend(expected, 'x'));
});
function doEmojiTest(oldText, newText, expected) {
var result = diff(oldText, newText);
if (!_.isEqual(result, expected)) {
console.log(oldText, newText, expected);
console.log(result, '!==', expected);
throw new Error('Emoji simple test case failed');
}
}
// emojis chosen to share high and low surrogates!
var EMOJI_ALPHABET = ['_', '๐Ÿค—', '๐Ÿ”—', '๐Ÿค˜', '๐Ÿ”˜'];
console.log('Generating emoji strings...');
var emoji_strings = [];
for (var i = 0; i <= ITERATIONS; ++i) {
var letters = [];
var len = Math.floor(random() * EMOJI_MAX_LENGTH);
for (var l = 0; l < len; ++l) {
var letter = EMOJI_ALPHABET[Math.floor(random() * EMOJI_ALPHABET.length)];
letters.push(letter);
}
emoji_strings.push(letters.join(''));
}
console.log('Running emoji fuzz tests...');
for (var i = 0; i < ITERATIONS; ++i) {
var oldText = emoji_strings[i];
var newText = emoji_strings[i + 1];
var result = diff(oldText, newText);
applyDiff(result, oldText, newText);
}
// Applies a diff to text, throwing an error if diff is invalid or incorrect
function applyDiff(diffs, text, expectedResult) {
var pos = 0;
function throwError(message) {
console.log(diffs, text, expectedResult);
throw new Error(message);
}
function expect(expected) {
var found = text.substr(pos, expected.length);
if (found !== expected) {
throwError('Expected "' + expected + '", found "' + found + '"');
}
}
var result = '';
var inserts_since_last_equality = 0;
var deletes_since_last_equality = 0;
for (var i = 0; i < diffs.length; i++) {
var d = diffs[i];
if (!d[1]) {
throwError('Empty tuple in diff')
}
var firstCharCode = d[1].charCodeAt(0);
var lastCharCode = d[1].slice(-1).charCodeAt(0);
if (firstCharCode >= 0xDC00 && firstCharCode <= 0xDFFF ||
lastCharCode >= 0xD800 && lastCharCode <= 0xDBFF) {
throwError('Bad unicode diff tuple')
}
switch (d[0]) {
case diff.EQUAL:
if (i !== 0 && !inserts_since_last_equality && !deletes_since_last_equality) {
throwError('two consecutive equalities in diff');
}
inserts_since_last_equality = 0;
deletes_since_last_equality = 0;
expect(d[1]);
result += d[1];
pos += d[1].length;
break;
case diff.DELETE:
if (deletes_since_last_equality) {
throwError('multiple deletes between equalities')
}
if (inserts_since_last_equality) {
throwError('delete following insert in diff')
}
deletes_since_last_equality++;
expect(d[1]);
pos += d[1].length;
break
case diff.INSERT:
if (inserts_since_last_equality) {
throwError('multiple inserts between equalities')
}
inserts_since_last_equality++;
result += d[1];
break;
}
}
if (pos !== text.length) {
throwError('Diff did not consume entire input text');
}
if (result !== expectedResult) {
console.log(diffs, text, expectedResult, result);
throw new Error('Diff not correct')
}
return result;
}
console.log("Success!");