8
0

diff.js 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
  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/diff
  7. */
  8. import fastDiff from '../src/fastdiff';
  9. // The following code is based on the "O(NP) Sequence Comparison Algorithm"
  10. // by Sun Wu, Udi Manber, Gene Myers, Webb Miller.
  11. /**
  12. * Calculates the difference between two arrays or strings producing an array containing a list of changes
  13. * necessary to transform input into output.
  14. *
  15. * diff( 'aba', 'acca' ); // [ 'equal', 'insert', 'insert', 'delete', 'equal' ]
  16. *
  17. * This function is based on the "O(NP) Sequence Comparison Algorithm" by Sun Wu, Udi Manber, Gene Myers, Webb Miller.
  18. * Unfortunately, while it gives the most precise results, its to complex for longer strings/arrow (above 200 items).
  19. * Therefore, `diff()` automatically switches to {@link module:utils/fastdiff~fastDiff `fastDiff()`} when detecting
  20. * such a scenario. The return formats of both functions are identical.
  21. *
  22. * @param {Array|String} a Input array or string.
  23. * @param {Array|String} b Output array or string.
  24. * @param {Function} [cmp] Optional function used to compare array values, by default === is used.
  25. * @returns {Array} Array of changes.
  26. */
  27. export default function diff( a, b, cmp ) {
  28. // Set the comparator function.
  29. cmp = cmp || function( a, b ) {
  30. return a === b;
  31. };
  32. const aLength = a.length;
  33. const bLength = b.length;
  34. // Perform `fastDiff` for longer strings/arrays (see #269).
  35. if ( aLength > 200 || bLength > 200 || aLength + bLength > 300 ) {
  36. return diff.fastDiff( a, b, cmp, true );
  37. }
  38. // Temporary action type statics.
  39. let _insert, _delete;
  40. // Swapped the arrays to use the shorter one as the first one.
  41. if ( bLength < aLength ) {
  42. const tmp = a;
  43. a = b;
  44. b = tmp;
  45. // We swap the action types as well.
  46. _insert = 'delete';
  47. _delete = 'insert';
  48. } else {
  49. _insert = 'insert';
  50. _delete = 'delete';
  51. }
  52. const m = a.length;
  53. const n = b.length;
  54. const delta = n - m;
  55. // Edit scripts, for each diagonal.
  56. const es = {};
  57. // Furthest points, the furthest y we can get on each diagonal.
  58. const fp = {};
  59. function snake( k ) {
  60. // We use -1 as an alternative below to handle initial values ( instead of filling the fp with -1 first ).
  61. // Furthest points (y) on the diagonal below k.
  62. const y1 = ( fp[ k - 1 ] !== undefined ? fp[ k - 1 ] : -1 ) + 1;
  63. // Furthest points (y) on the diagonal above k.
  64. const y2 = fp[ k + 1 ] !== undefined ? fp[ k + 1 ] : -1;
  65. // The way we should go to get further.
  66. const dir = y1 > y2 ? -1 : 1;
  67. // Clone previous changes array (if any).
  68. if ( es[ k + dir ] ) {
  69. es[ k ] = es[ k + dir ].slice( 0 );
  70. }
  71. // Create changes array.
  72. if ( !es[ k ] ) {
  73. es[ k ] = [];
  74. }
  75. // Push the action.
  76. es[ k ].push( y1 > y2 ? _insert : _delete );
  77. // Set the beginning coordinates.
  78. let y = Math.max( y1, y2 );
  79. let x = y - k;
  80. // Traverse the diagonal as long as the values match.
  81. while ( x < m && y < n && cmp( a[ x ], b[ y ] ) ) {
  82. x++;
  83. y++;
  84. // Push no change action.
  85. es[ k ].push( 'equal' );
  86. }
  87. return y;
  88. }
  89. let p = 0;
  90. let k;
  91. // Traverse the graph until we reach the end of the longer string.
  92. do {
  93. // Updates furthest points and edit scripts for diagonals below delta.
  94. for ( k = -p; k < delta; k++ ) {
  95. fp[ k ] = snake( k );
  96. }
  97. // Updates furthest points and edit scripts for diagonals above delta.
  98. for ( k = delta + p; k > delta; k-- ) {
  99. fp[ k ] = snake( k );
  100. }
  101. // Updates furthest point and edit script for the delta diagonal.
  102. // note that the delta diagonal is the one which goes through the sink (m, n).
  103. fp[ delta ] = snake( delta );
  104. p++;
  105. } while ( fp[ delta ] !== n );
  106. // Return the final list of edit changes.
  107. // We remove the first item that represents the action for the injected nulls.
  108. return es[ delta ].slice( 1 );
  109. }
  110. // Store the API in static property to easily overwrite it in tests.
  111. // Too bad dependency injection does not work in Webpack + ES 6 (const) + Babel.
  112. diff.fastDiff = fastDiff;