| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161 |
- /**
- * @license Copyright (c) 2003-2018, CKSource - Frederico Knabben. All rights reserved.
- * For licensing, see LICENSE.md.
- */
- /**
- * @module utils/fastdiff
- */
- /**
- * Finds position of the first and last change in the given strings and generates set of changes. Set of changes
- * can be applied to the input text in order to transform it into the output text, for example:
- *
- * fastDiff( '12a', '12xyza' );
- * // [ { index: 2, type: 'insert', values: [ 'x', 'y', 'z' ] } ]
- *
- * fastDiff( '12a', '12aa' );
- * // [ { index: 3, type: 'insert', values: [ 'a' ] } ]
- *
- * fastDiff( '12xyza', '12a' );
- * // [ { index: 2, type: 'delete', howMany: 3 } ]
- *
- * fastDiff( '12aa', '12a' );
- * // [ { index: 3, type: 'delete', howMany: 1 } ]
- *
- * fastDiff( '12abc3', '2ab' );
- * // [ { index: 0, type: 'insert', values: [ '2', 'a', 'b' ] }, { index: 3, type: 'delete', howMany: 6 } ]
- *
- * Using returned results you can modify `oldText` to transform it into `newText`:
- *
- * let input = '12abc3';
- * const output = '2ab';
- * const changes = fastDiff( input, output );
- *
- * changes.forEach( change => {
- * if ( change.type == 'insert' ) {
- * input = input.substring( 0, change.index ) + change.values.join( '' ) + input.substring( change.index );
- * } else if ( change.type == 'delete' ) {
- * input = input.substring( 0, change.index ) + input.substring( change.index + change.howMany );
- * }
- * } );
- *
- * input === output; // -> true
- *
- * The output format of this function is compatible with {@link module:utils/difftochanges~diffToChanges} output format.
- *
- * @param {String} oldText Input string.
- * @param {String} newText Input string.
- * @returns {Array} Array of changes.
- */
- export default function fastDiff( oldText, newText ) {
- // Check if both texts are equal.
- if ( oldText === newText ) {
- return [];
- }
- const changeIndexes = findChangeBoundaryIndexes( oldText, newText );
- return changeIndexesToChanges( newText, changeIndexes );
- }
- // Finds position of the first and last change in the given strings. For example:
- //
- // const indexes = findChangeBoundaryIndexes( '1234', '13424' );
- // console.log( indexes ); // { firstIndex: 1, lastIndexOld: 3, lastIndexNew: 4 }
- //
- // The above indexes means that in `oldText` modified part is `1[23]4` and in the `newText` it is `1[342]4`.
- // Based on such indexes, array with `insert`/`delete` operations which allows transforming
- // old text to the new one can be generated.
- //
- // It is expected that `oldText` and `newText` are different.
- //
- // @param {String} oldText
- // @param {String} newText
- // @returns {Object}
- // @returns {Number} return.firstIndex Index of the first change in both strings (always the same for both).
- // @returns {Number} result.lastIndexOld Index of the last common character in `oldText` string.
- // @returns {Number} result.lastIndexNew Index of the last common character in `newText` string.
- function findChangeBoundaryIndexes( oldText, newText ) {
- // Find the first difference between texts.
- const firstIndex = findFirstDifferenceIndex( oldText, newText );
- // Remove the common part of texts and reverse them to make it simpler to find the last difference between texts.
- const oldTextReversed = cutAndReverse( oldText, firstIndex );
- const newTextReversed = cutAndReverse( newText, firstIndex );
- // Find the first difference between reversed texts.
- // It should be treated as "how many characters from the end the last difference occurred".
- //
- // For example:
- //
- // initial -> after cut -> reversed:
- // oldText: '321ba' -> '21ba' -> 'ab12'
- // newText: '31xba' -> '1xba' -> 'abx1'
- // lastIndex: -> 2
- //
- // So the last change occurred two characters from the end of the texts.
- const lastIndex = findFirstDifferenceIndex( oldTextReversed, newTextReversed );
- // Use `lastIndex` to calculate proper offset, starting from the beginning (`lastIndex` kind of starts from the end).
- const lastIndexOld = oldText.length - lastIndex;
- const lastIndexNew = newText.length - lastIndex;
- return { firstIndex, lastIndexOld, lastIndexNew };
- }
- // Returns a first index on which `oldText` and `newText` differ.
- //
- // @param {String} oldText
- // @param {String} newText
- // @returns {Number}
- function findFirstDifferenceIndex( oldText, newText ) {
- for ( let i = 0; i < Math.max( oldText.length, newText.length ); i++ ) {
- if ( oldText[ i ] !== newText[ i ] ) {
- return i;
- }
- }
- // No "backup" return cause we assume that `oldText` and `newText` differ. This means that they either have a
- // difference or they have a different lengths. This means that the `if` condition will always be met eventually.
- }
- // Removes `howMany` characters from the given `text` string starting from the beginning, then reverses and returns it.
- //
- // @param {String} text Text to be processed.
- // @param {Number} howMany How many characters from text beginning to cut.
- // @returns {String} Shortened and reversed text.
- function cutAndReverse( text, howMany ) {
- return text.substring( howMany ).split( '' ).reverse().join( '' );
- }
- // Generates changes array based on change indexes from `findChangeBoundaryIndexes` function. This function will
- // generate array with 0 (no changes), 1 (deletion or insertion) or 2 records (insertion and deletion).
- //
- // @param {String} newText New text for which change indexes were calculated.
- // @param {Object} changeIndexes Change indexes object from `findChangeBoundaryIndexes` function.
- // @returns {Array.<Object>} Array of changes compatible with {@link module:utils/difftochanges~diffToChanges} format.
- function changeIndexesToChanges( newText, changeIndexes ) {
- const result = [];
- const { firstIndex, lastIndexOld, lastIndexNew } = changeIndexes;
- // Order operations as 'insert', 'delete' array to keep compatibility with {@link module:utils/difftochanges~diffToChanges}
- // in most cases. However, 'diffToChanges' does not stick to any order so in some cases
- // (for example replacing '12345' with 'abcd') it will generate 'delete', 'insert' order.
- if ( lastIndexNew - firstIndex > 0 ) {
- result.push( {
- index: firstIndex,
- type: 'insert',
- values: newText.substring( firstIndex, lastIndexNew ).split( '' )
- } );
- }
- if ( lastIndexOld - firstIndex > 0 ) {
- result.push( {
- index: firstIndex + ( lastIndexNew - firstIndex ), // Increase index of what was inserted.
- type: 'delete',
- howMany: lastIndexOld - firstIndex
- } );
- }
- return result;
- }
|