fastdiff.js 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261
  1. /**
  2. * @license Copyright (c) 2003-2020, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md or https://ckeditor.com/legal/ckeditor-oss-license
  4. */
  5. /**
  6. * @module utils/fastdiff
  7. */
  8. /**
  9. * Finds positions of the first and last change in the given string/array and generates a set of changes:
  10. *
  11. * fastDiff( '12a', '12xyza' );
  12. * // [ { index: 2, type: 'insert', values: [ 'x', 'y', 'z' ] } ]
  13. *
  14. * fastDiff( '12a', '12aa' );
  15. * // [ { index: 3, type: 'insert', values: [ 'a' ] } ]
  16. *
  17. * fastDiff( '12xyza', '12a' );
  18. * // [ { index: 2, type: 'delete', howMany: 3 } ]
  19. *
  20. * fastDiff( [ '1', '2', 'a', 'a' ], [ '1', '2', 'a' ] );
  21. * // [ { index: 3, type: 'delete', howMany: 1 } ]
  22. *
  23. * fastDiff( [ '1', '2', 'a', 'b', 'c', '3' ], [ '2', 'a', 'b' ] );
  24. * // [ { index: 0, type: 'insert', values: [ '2', 'a', 'b' ] }, { index: 3, type: 'delete', howMany: 6 } ]
  25. *
  26. * Passed arrays can contain any type of data, however to compare them correctly custom comparator function
  27. * should be passed as a third parameter:
  28. *
  29. * fastDiff( [ { value: 1 }, { value: 2 } ], [ { value: 1 }, { value: 3 } ], ( a, b ) => {
  30. * return a.value === b.value;
  31. * } );
  32. * // [ { index: 1, type: 'insert', values: [ { value: 3 } ] }, { index: 2, type: 'delete', howMany: 1 } ]
  33. *
  34. * The resulted set of changes can be applied to the input in order to transform it into the output, for example:
  35. *
  36. * let input = '12abc3';
  37. * const output = '2ab';
  38. * const changes = fastDiff( input, output );
  39. *
  40. * changes.forEach( change => {
  41. * if ( change.type == 'insert' ) {
  42. * input = input.substring( 0, change.index ) + change.values.join( '' ) + input.substring( change.index );
  43. * } else if ( change.type == 'delete' ) {
  44. * input = input.substring( 0, change.index ) + input.substring( change.index + change.howMany );
  45. * }
  46. * } );
  47. *
  48. * // input equals output now
  49. *
  50. * or in case of arrays:
  51. *
  52. * let input = [ '1', '2', 'a', 'b', 'c', '3' ];
  53. * const output = [ '2', 'a', 'b' ];
  54. * const changes = fastDiff( input, output );
  55. *
  56. * changes.forEach( change => {
  57. * if ( change.type == 'insert' ) {
  58. * input = input.slice( 0, change.index ).concat( change.values, input.slice( change.index ) );
  59. * } else if ( change.type == 'delete' ) {
  60. * input = input.slice( 0, change.index ).concat( input.slice( change.index + change.howMany ) );
  61. * }
  62. * } );
  63. *
  64. * // input equals output now
  65. *
  66. * By passing `true` as the fourth parameter (`atomicChanges`) the output of this function will become compatible with
  67. * the {@link module:utils/diff~diff `diff()`} function:
  68. *
  69. * fastDiff( '12a', '12xyza' );
  70. * // [ 'equal', 'equal', 'insert', 'insert', 'insert', 'equal' ]
  71. *
  72. * The default output format of this function is compatible with the output format of
  73. * {@link module:utils/difftochanges~diffToChanges `diffToChanges()`}. The `diffToChanges()` input format is, in turn,
  74. * compatible with the output of {@link module:utils/diff~diff `diff()`}:
  75. *
  76. * const a = '1234';
  77. * const b = '12xyz34';
  78. *
  79. * // Both calls will return the same results (grouped changes format).
  80. * fastDiff( a, b );
  81. * diffToChanges( diff( a, b ) );
  82. *
  83. * // Again, both calls will return the same results (atomic changes format).
  84. * fastDiff( a, b, null, true );
  85. * diff( a, b );
  86. *
  87. *
  88. * @param {Array|String} a Input array or string.
  89. * @param {Array|String} b Input array or string.
  90. * @param {Function} [cmp] Optional function used to compare array values, by default `===` (strict equal operator) is used.
  91. * @param {Boolean} [atomicChanges=false] Whether an array of `inset|delete|equal` operations should
  92. * be returned instead of changes set. This makes this function compatible with {@link module:utils/diff~diff `diff()`}.
  93. * @returns {Array} Array of changes.
  94. */
  95. export default function fastDiff( a, b, cmp, atomicChanges = false ) {
  96. // Set the comparator function.
  97. cmp = cmp || function( a, b ) {
  98. return a === b;
  99. };
  100. // Convert the string (or any array-like object - eg. NodeList) to an array by using the slice() method because,
  101. // unlike Array.from(), it returns array of UTF-16 code units instead of the code points of a string.
  102. // One code point might be a surrogate pair of two code units. All text offsets are expected to be in code units.
  103. // See ckeditor/ckeditor5#3147.
  104. //
  105. // We need to make sure here that fastDiff() works identical to diff().
  106. if ( !Array.isArray( a ) ) {
  107. a = Array.prototype.slice.call( a );
  108. }
  109. if ( !Array.isArray( b ) ) {
  110. b = Array.prototype.slice.call( b );
  111. }
  112. // Find first and last change.
  113. const changeIndexes = findChangeBoundaryIndexes( a, b, cmp );
  114. // Transform into changes array.
  115. return atomicChanges ? changeIndexesToAtomicChanges( changeIndexes, b.length ) : changeIndexesToChanges( b, changeIndexes );
  116. }
  117. // Finds position of the first and last change in the given arrays. For example:
  118. //
  119. // const indexes = findChangeBoundaryIndexes( [ '1', '2', '3', '4' ], [ '1', '3', '4', '2', '4' ] );
  120. // console.log( indexes ); // { firstIndex: 1, lastIndexOld: 3, lastIndexNew: 4 }
  121. //
  122. // The above indexes means that in the first array the modified part is `1[23]4` and in the second array it is `1[342]4`.
  123. // Based on such indexes, array with `insert`/`delete` operations which allows transforming first value into the second one
  124. // can be generated.
  125. //
  126. // @param {Array} arr1
  127. // @param {Array} arr2
  128. // @param {Function} cmp Comparator function.
  129. // @returns {Object}
  130. // @returns {Number} return.firstIndex Index of the first change in both values (always the same for both).
  131. // @returns {Number} result.lastIndexOld Index of the last common value in `arr1`.
  132. // @returns {Number} result.lastIndexNew Index of the last common value in `arr2`.
  133. function findChangeBoundaryIndexes( arr1, arr2, cmp ) {
  134. // Find the first difference between passed values.
  135. const firstIndex = findFirstDifferenceIndex( arr1, arr2, cmp );
  136. // If arrays are equal return -1 indexes object.
  137. if ( firstIndex === -1 ) {
  138. return { firstIndex: -1, lastIndexOld: -1, lastIndexNew: -1 };
  139. }
  140. // Remove the common part of each value and reverse them to make it simpler to find the last difference between them.
  141. const oldArrayReversed = cutAndReverse( arr1, firstIndex );
  142. const newArrayReversed = cutAndReverse( arr2, firstIndex );
  143. // Find the first difference between reversed values.
  144. // It should be treated as "how many elements from the end the last difference occurred".
  145. //
  146. // For example:
  147. //
  148. // initial -> after cut -> reversed:
  149. // oldValue: '321ba' -> '21ba' -> 'ab12'
  150. // newValue: '31xba' -> '1xba' -> 'abx1'
  151. // lastIndex: -> 2
  152. //
  153. // So the last change occurred two characters from the end of the arrays.
  154. const lastIndex = findFirstDifferenceIndex( oldArrayReversed, newArrayReversed, cmp );
  155. // Use `lastIndex` to calculate proper offset, starting from the beginning (`lastIndex` kind of starts from the end).
  156. const lastIndexOld = arr1.length - lastIndex;
  157. const lastIndexNew = arr2.length - lastIndex;
  158. return { firstIndex, lastIndexOld, lastIndexNew };
  159. }
  160. // Returns a first index on which given arrays differ. If both arrays are the same, -1 is returned.
  161. //
  162. // @param {Array} arr1
  163. // @param {Array} arr2
  164. // @param {Function} cmp Comparator function.
  165. // @returns {Number}
  166. function findFirstDifferenceIndex( arr1, arr2, cmp ) {
  167. for ( let i = 0; i < Math.max( arr1.length, arr2.length ); i++ ) {
  168. if ( arr1[ i ] === undefined || arr2[ i ] === undefined || !cmp( arr1[ i ], arr2[ i ] ) ) {
  169. return i;
  170. }
  171. }
  172. return -1; // Return -1 if arrays are equal.
  173. }
  174. // Returns a copy of the given array with `howMany` elements removed starting from the beginning and in reversed order.
  175. //
  176. // @param {Array} arr Array to be processed.
  177. // @param {Number} howMany How many elements from array beginning to remove.
  178. // @returns {Array} Shortened and reversed array.
  179. function cutAndReverse( arr, howMany ) {
  180. return arr.slice( howMany ).reverse();
  181. }
  182. // Generates changes array based on change indexes from `findChangeBoundaryIndexes` function. This function will
  183. // generate array with 0 (no changes), 1 (deletion or insertion) or 2 records (insertion and deletion).
  184. //
  185. // @param {Array} newArray New array for which change indexes were calculated.
  186. // @param {Object} changeIndexes Change indexes object from `findChangeBoundaryIndexes` function.
  187. // @returns {Array.<Object>} Array of changes compatible with {@link module:utils/difftochanges~diffToChanges} format.
  188. function changeIndexesToChanges( newArray, changeIndexes ) {
  189. const result = [];
  190. const { firstIndex, lastIndexOld, lastIndexNew } = changeIndexes;
  191. // Order operations as 'insert', 'delete' array to keep compatibility with {@link module:utils/difftochanges~diffToChanges}
  192. // in most cases. However, 'diffToChanges' does not stick to any order so in some cases
  193. // (for example replacing '12345' with 'abcd') it will generate 'delete', 'insert' order.
  194. if ( lastIndexNew - firstIndex > 0 ) {
  195. result.push( {
  196. index: firstIndex,
  197. type: 'insert',
  198. values: newArray.slice( firstIndex, lastIndexNew )
  199. } );
  200. }
  201. if ( lastIndexOld - firstIndex > 0 ) {
  202. result.push( {
  203. index: firstIndex + ( lastIndexNew - firstIndex ), // Increase index of what was inserted.
  204. type: 'delete',
  205. howMany: lastIndexOld - firstIndex
  206. } );
  207. }
  208. return result;
  209. }
  210. // Generates array with set `equal|insert|delete` operations based on change indexes from `findChangeBoundaryIndexes` function.
  211. //
  212. // @param {Object} changeIndexes Change indexes object from `findChangeBoundaryIndexes` function.
  213. // @param {Number} newLength Length of the new array on which `findChangeBoundaryIndexes` calculated change indexes.
  214. // @returns {Array.<String>} Array of changes compatible with {@link module:utils/diff~diff} format.
  215. function changeIndexesToAtomicChanges( changeIndexes, newLength ) {
  216. const { firstIndex, lastIndexOld, lastIndexNew } = changeIndexes;
  217. // No changes.
  218. if ( firstIndex === -1 ) {
  219. return Array( newLength ).fill( 'equal' );
  220. }
  221. let result = [];
  222. if ( firstIndex > 0 ) {
  223. result = result.concat( Array( firstIndex ).fill( 'equal' ) );
  224. }
  225. if ( lastIndexNew - firstIndex > 0 ) {
  226. result = result.concat( Array( lastIndexNew - firstIndex ).fill( 'insert' ) );
  227. }
  228. if ( lastIndexOld - firstIndex > 0 ) {
  229. result = result.concat( Array( lastIndexOld - firstIndex ).fill( 'delete' ) );
  230. }
  231. if ( lastIndexNew < newLength ) {
  232. result = result.concat( Array( newLength - lastIndexNew ).fill( 'equal' ) );
  233. }
  234. return result;
  235. }