fastdiff.js 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
  1. /**
  2. * @license Copyright (c) 2003-2018, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. /**
  6. * @module utils/fastdiff
  7. */
  8. /**
  9. * Finds position of the first and last change in the given strings and generates set of changes. Set of changes
  10. * can be applied to the input text in order to transform it into the output text, for example:
  11. *
  12. * fastDiff( '12a', '12xyza' );
  13. * // [ { index: 2, type: 'insert', values: [ 'x', 'y', 'z' ] } ]
  14. *
  15. * fastDiff( '12a', '12aa' );
  16. * // [ { index: 3, type: 'insert', values: [ 'a' ] } ]
  17. *
  18. * fastDiff( '12xyza', '12a' );
  19. * // [ { index: 2, type: 'delete', howMany: 3 } ]
  20. *
  21. * fastDiff( '12aa', '12a' );
  22. * // [ { index: 3, type: 'delete', howMany: 1 } ]
  23. *
  24. * fastDiff( '12abc3', '2ab' );
  25. * // [ { index: 0, type: 'insert', values: [ '2', 'a', 'b' ] }, { index: 3, type: 'delete', howMany: 6 } ]
  26. *
  27. * Using returned results you can modify `oldText` to transform it into `newText`:
  28. *
  29. * let input = '12abc3';
  30. * const output = '2ab';
  31. * const changes = fastDiff( input, output );
  32. *
  33. * changes.forEach( change => {
  34. * if ( change.type == 'insert' ) {
  35. * input = input.substring( 0, change.index ) + change.values.join( '' ) + input.substring( change.index );
  36. * } else if ( change.type == 'delete' ) {
  37. * input = input.substring( 0, change.index ) + input.substring( change.index + change.howMany );
  38. * }
  39. * } );
  40. *
  41. * input === output; // -> true
  42. *
  43. * The output format of this function is compatible with {@link module:utils/difftochanges~diffToChanges} output format.
  44. *
  45. * @param {String} oldText Input string.
  46. * @param {String} newText Input string.
  47. * @returns {Array} Array of changes.
  48. */
  49. export default function fastDiff( oldText, newText ) {
  50. // Check if both texts are equal.
  51. if ( oldText === newText ) {
  52. return [];
  53. }
  54. const changeIndexes = findChangeBoundaryIndexes( oldText, newText );
  55. return changeIndexesToChanges( newText, changeIndexes );
  56. }
  57. // Finds position of the first and last change in the given strings. For example:
  58. //
  59. // const indexes = findChangeBoundaryIndexes( '1234', '13424' );
  60. // console.log( indexes ); // { firstIndex: 1, lastIndexOld: 3, lastIndexNew: 4 }
  61. //
  62. // The above indexes means that in `oldText` modified part is `1[23]4` and in the `newText` it is `1[342]4`.
  63. // Based on such indexes, array with `insert`/`delete` operations which allows transforming
  64. // old text to the new one can be generated.
  65. //
  66. // It is expected that `oldText` and `newText` are different.
  67. //
  68. // @param {String} oldText
  69. // @param {String} newText
  70. // @returns {Object}
  71. // @returns {Number} return.firstIndex Index of the first change in both strings (always the same for both).
  72. // @returns {Number} result.lastIndexOld Index of the last common character in `oldText` string.
  73. // @returns {Number} result.lastIndexNew Index of the last common character in `newText` string.
  74. function findChangeBoundaryIndexes( oldText, newText ) {
  75. // Find the first difference between texts.
  76. const firstIndex = findFirstDifferenceIndex( oldText, newText );
  77. // Remove the common part of texts and reverse them to make it simpler to find the last difference between texts.
  78. const oldTextReversed = cutAndReverse( oldText, firstIndex );
  79. const newTextReversed = cutAndReverse( newText, firstIndex );
  80. // Find the first difference between reversed texts.
  81. // It should be treated as "how many characters from the end the last difference occurred".
  82. //
  83. // For example:
  84. //
  85. // initial -> after cut -> reversed:
  86. // oldText: '321ba' -> '21ba' -> 'ab12'
  87. // newText: '31xba' -> '1xba' -> 'abx1'
  88. // lastIndex: -> 2
  89. //
  90. // So the last change occurred two characters from the end of the texts.
  91. const lastIndex = findFirstDifferenceIndex( oldTextReversed, newTextReversed );
  92. // Use `lastIndex` to calculate proper offset, starting from the beginning (`lastIndex` kind of starts from the end).
  93. const lastIndexOld = oldText.length - lastIndex;
  94. const lastIndexNew = newText.length - lastIndex;
  95. return { firstIndex, lastIndexOld, lastIndexNew };
  96. }
  97. // Returns a first index on which `oldText` and `newText` differ.
  98. //
  99. // @param {String} oldText
  100. // @param {String} newText
  101. // @returns {Number}
  102. function findFirstDifferenceIndex( oldText, newText ) {
  103. for ( let i = 0; i < Math.max( oldText.length, newText.length ); i++ ) {
  104. if ( oldText[ i ] !== newText[ i ] ) {
  105. return i;
  106. }
  107. }
  108. // No "backup" return cause we assume that `oldText` and `newText` differ. This means that they either have a
  109. // difference or they have a different lengths. This means that the `if` condition will always be met eventually.
  110. }
  111. // Removes `howMany` characters from the given `text` string starting from the beginning, then reverses and returns it.
  112. //
  113. // @param {String} text Text to be processed.
  114. // @param {Number} howMany How many characters from text beginning to cut.
  115. // @returns {String} Shortened and reversed text.
  116. function cutAndReverse( text, howMany ) {
  117. return text.substring( howMany ).split( '' ).reverse().join( '' );
  118. }
  119. // Generates changes array based on change indexes from `findChangeBoundaryIndexes` function. This function will
  120. // generate array with 0 (no changes), 1 (deletion or insertion) or 2 records (insertion and deletion).
  121. //
  122. // @param {String} newText New text for which change indexes were calculated.
  123. // @param {Object} changeIndexes Change indexes object from `findChangeBoundaryIndexes` function.
  124. // @returns {Array.<Object>} Array of changes compatible with {@link module:utils/difftochanges~diffToChanges} format.
  125. function changeIndexesToChanges( newText, changeIndexes ) {
  126. const result = [];
  127. const { firstIndex, lastIndexOld, lastIndexNew } = changeIndexes;
  128. // Order operations as 'insert', 'delete' array to keep compatibility with {@link module:utils/difftochanges~diffToChanges}
  129. // in most cases. However, 'diffToChanges' does not stick to any order so in some cases
  130. // (for example replacing '12345' with 'abcd') it will generate 'delete', 'insert' order.
  131. if ( lastIndexNew - firstIndex > 0 ) {
  132. result.push( {
  133. index: firstIndex,
  134. type: 'insert',
  135. values: newText.substring( firstIndex, lastIndexNew ).split( '' )
  136. } );
  137. }
  138. if ( lastIndexOld - firstIndex > 0 ) {
  139. result.push( {
  140. index: firstIndex + ( lastIndexNew - firstIndex ), // Increase index of what was inserted.
  141. type: 'delete',
  142. howMany: lastIndexOld - firstIndex
  143. } );
  144. }
  145. return result;
  146. }