fastdiff.js 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477
  1. /**
  2. * @license Copyright (c) 2003-2019, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. import fastDiff from '../src/fastdiff';
  6. import diff from '../src/diff';
  7. import diffToChanges from '../src/difftochanges';
  8. describe( 'fastDiff', () => {
  9. describe( 'changes object', () => {
  10. it( 'should diff identical texts', () => {
  11. expectDiff( '123', '123', [] );
  12. } );
  13. it( 'should diff identical arrays', () => {
  14. expectDiff( [ '1', '2', '3' ], [ '1', '2', '3' ], [] );
  15. } );
  16. it( 'should diff arrays with custom comparator', () => {
  17. expectDiff( [ 'a', 'b', 'c' ], [ 'A', 'B', 'C' ], [], true, ( a, b ) => a.toLowerCase() === b.toLowerCase() );
  18. } );
  19. describe( 'insertion', () => {
  20. it( 'should diff if old text is empty', () => {
  21. expectDiff( '', '123', [ { index: 0, type: 'insert', values: [ '1', '2', '3' ] } ] );
  22. } );
  23. it( 'should diff if old array is empty', () => {
  24. expectDiff( [], [ '1', '2', '3' ], [ { index: 0, type: 'insert', values: [ '1', '2', '3' ] } ] );
  25. } );
  26. it( 'should diff insertion on the beginning', () => {
  27. expectDiff( '123', 'abc123', [ { index: 0, type: 'insert', values: [ 'a', 'b', 'c' ] } ] );
  28. } );
  29. it( 'should diff insertion on the beginning (repetitive substring)', () => {
  30. // Do not check compatibility with 'diffToChanges' as it generates:
  31. // [ { index: 0, type: 'insert', values: [ 'a', 'b' ] }, { index: 5, type: 'insert', values: [ 'c', '1', '2', '3' ] } ]
  32. expectDiff( '123', 'ab123c123', [ { index: 0, type: 'insert', values: [ 'a', 'b', '1', '2', '3', 'c' ] } ], false );
  33. } );
  34. it( 'should diff insertion on the end', () => {
  35. expectDiff( '123', '123abc', [ { index: 3, type: 'insert', values: [ 'a', 'b', 'c' ] } ] );
  36. } );
  37. it( 'should diff insertion on the end (repetitive substring)', () => {
  38. expectDiff( '123', '123ab123c', [ { index: 3, type: 'insert', values: [ 'a', 'b', '1', '2', '3', 'c' ] } ] );
  39. } );
  40. it( 'should diff insertion in the middle', () => {
  41. expectDiff( '123', '12abc3', [ { index: 2, type: 'insert', values: [ 'a', 'b', 'c' ] } ] );
  42. } );
  43. it( 'should diff insertion in the middle (repetitive substring)', () => {
  44. // Do not check compatibility with 'diffToChanges' as it generates:
  45. // [ { index: 2, type: 'insert', values: [ 'a', 'b', '1', '2' ] }, { index: 7, type: 'insert', values: [ 'c', '3' ] } ]
  46. expectDiff( '123', '12ab123c3', [ { index: 2, type: 'insert', values: [ 'a', 'b', '1', '2', '3', 'c' ] } ], false );
  47. } );
  48. it( 'should diff insertion of duplicated content', () => {
  49. expectDiff( '123', '123123', [ { index: 3, type: 'insert', values: [ '1', '2', '3' ] } ] );
  50. } );
  51. it( 'should diff insertion of partially duplicated content', () => {
  52. expectDiff( '123', '12323', [ { index: 3, type: 'insert', values: [ '2', '3' ] } ] );
  53. } );
  54. it( 'should diff insertion on both boundaries', () => {
  55. // Do not check compatibility with 'diffToChanges' as it generates:
  56. // [ { index: 2, type: 'insert', values: [ 'a', 'b' ] }, { index: 5, type: 'insert', values: [ 'c' ] } ]
  57. expectDiff( '123', 'ab123c', [
  58. { index: 0, type: 'insert', values: [ 'a', 'b', '1', '2', '3', 'c' ] },
  59. { index: 6, type: 'delete', howMany: 3 }
  60. ], false );
  61. } );
  62. it( 'should diff insertion in array of objects', () => {
  63. const o1 = { foo: 1 };
  64. const o2 = { bar: 2 };
  65. expectDiff( [ o1, o2 ], [ o1, o2, { baz: 3 } ], [
  66. { index: 2, type: 'insert', values: [ { baz: 3 } ] }
  67. ] );
  68. } );
  69. it( 'should diff insertion in array of objects with comparator', () => {
  70. expectDiff( [ { text: 'foo' }, { text: 'bar' } ], [ { text: 'foo' }, { text: 'bar' }, { text: 'baz' } ], [
  71. { index: 2, type: 'insert', values: [ { text: 'baz' } ] }
  72. ], true, ( a, b ) => a.text === b.text );
  73. } );
  74. } );
  75. describe( 'deletion', () => {
  76. it( 'should diff if new text is empty', () => {
  77. expectDiff( '123', '', [ { index: 0, type: 'delete', howMany: 3 } ] );
  78. } );
  79. it( 'should diff if new array is empty', () => {
  80. expectDiff( [ '1', '2', '3' ], [], [ { index: 0, type: 'delete', howMany: 3 } ] );
  81. } );
  82. it( 'should diff deletion on the beginning', () => {
  83. expectDiff( 'abc123', '123', [ { index: 0, type: 'delete', howMany: 3 } ] );
  84. } );
  85. it( 'should diff deletion on the beginning (repetitive substring)', () => {
  86. // Do not check compatibility with 'diffToChanges' as it generates:
  87. // [ { index: 0, type: 'delete', howMany: 2 }, { index: 3, type: 'delete', howMany: 4 } ]
  88. expectDiff( 'ab123c123', '123', [ { index: 0, type: 'delete', howMany: 6 } ], false );
  89. } );
  90. it( 'should diff deletion on the end', () => {
  91. expectDiff( '123abc', '123', [ { index: 3, type: 'delete', howMany: 3 } ] );
  92. } );
  93. it( 'should diff deletion on the end (repetitive substring)', () => {
  94. expectDiff( '123ab123c', '123', [ { index: 3, type: 'delete', howMany: 6 } ] );
  95. } );
  96. it( 'should diff deletion in the middle', () => {
  97. expectDiff( '12abc3', '123', [ { index: 2, type: 'delete', howMany: 3 } ] );
  98. } );
  99. it( 'should diff deletion in the middle (repetitive substring)', () => {
  100. // Do not check compatibility with 'diffToChanges' as it generates:
  101. // [ { index: 2, type: 'delete', howMany: 4 }, { index: 3, type: 'delete', howMany: 2 } ]
  102. expectDiff( '12ab123c3', '123', [ { index: 2, type: 'delete', howMany: 6 } ], false );
  103. } );
  104. it( 'should diff deletion on both boundaries', () => {
  105. // Do not check compatibility with 'diffToChanges' as it generates:
  106. // [ { index: 0, type: 'delete', howMany: 1 }, { index: 3, type: 'delete', howMany: 2 } ]
  107. expectDiff( '12abc3', '2ab', [
  108. { index: 0, type: 'insert', values: [ '2', 'a', 'b' ] },
  109. { index: 3, type: 'delete', howMany: 6 }
  110. ], false );
  111. } );
  112. it( 'should diff deletion of duplicated content', () => {
  113. expectDiff( '123123', '123', [ { index: 3, type: 'delete', howMany: 3 } ] );
  114. } );
  115. it( 'should diff deletion of partially duplicated content', () => {
  116. expectDiff( '12323', '123', [ { index: 3, type: 'delete', howMany: 2 } ] );
  117. } );
  118. it( 'should diff deletion of partially duplicated content 2', () => {
  119. // Do not check compatibility with 'diffToChanges' as it generates:
  120. // [ { index: 1, type: 'delete', howMany: 2 }, { index: 2, type: 'delete', howMany: 1 } ]
  121. expectDiff( '11233', '13', [ { index: 1, type: 'delete', howMany: 3 } ], false );
  122. } );
  123. it( 'should diff deletion in array of objects', () => {
  124. const o1 = { foo: 1 };
  125. const o2 = { bar: 2 };
  126. expectDiff( [ o1, o2 ], [ o2 ], [
  127. { index: 0, type: 'delete', howMany: 1 }
  128. ] );
  129. } );
  130. it( 'should diff insertion in array of objects with comparator', () => {
  131. expectDiff( [ { text: 'foo' }, { text: 'bar' } ], [ { text: 'bar' } ], [
  132. { index: 0, type: 'delete', howMany: 1 }
  133. ], true, ( a, b ) => a.text === b.text );
  134. } );
  135. } );
  136. describe( 'replacement', () => {
  137. it( 'should diff replacement of entire text', () => {
  138. // Do not check compatibility with 'diffToChanges' as it has changes in reveres order ('delete', 'insert') here.
  139. expectDiff( '12345', 'abcd', [
  140. { index: 0, type: 'insert', values: [ 'a', 'b', 'c', 'd' ] },
  141. { index: 4, type: 'delete', howMany: 5 }
  142. ], false );
  143. } );
  144. it( 'should diff replacement on the beginning', () => {
  145. expectDiff( '12345', 'abcd345', [
  146. { index: 0, type: 'insert', values: [ 'a', 'b', 'c', 'd' ] },
  147. { index: 4, type: 'delete', howMany: 2 }
  148. ] );
  149. } );
  150. it( 'should diff replacement on the beginning (repetitive substring)', () => {
  151. // Do not check compatibility with 'diffToChanges' as it has changes in reveres order ('delete', 'insert') here.
  152. expectDiff( '12345', '345345', [
  153. { index: 0, type: 'insert', values: [ '3', '4', '5' ] },
  154. { index: 3, type: 'delete', howMany: 2 }
  155. ], false );
  156. } );
  157. it( 'should diff replacement on the end', () => {
  158. // Do not check compatibility with 'diffToChanges' as it has changes in reveres order ('delete', 'insert') here.
  159. expectDiff( '12345', '12ab', [
  160. { index: 2, type: 'insert', values: [ 'a', 'b' ] },
  161. { index: 4, type: 'delete', howMany: 3 }
  162. ], false );
  163. } );
  164. it( 'should diff replacement on the end (repetitive substring)', () => {
  165. // Do not check compatibility with 'diffToChanges' as it generates:
  166. // [ { index: 3, type: 'insert', values: [ '1', '2', '3' ] }, { index: 7, type: 'delete', howMany: 1 } ]
  167. expectDiff( '12345', '1231234', [
  168. { index: 3, type: 'insert', values: [ '1', '2', '3', '4' ] },
  169. { index: 7, type: 'delete', howMany: 2 }
  170. ], false );
  171. } );
  172. it( 'should diff insertion of duplicated content', () => {
  173. expectDiff( '1234', '123123', [
  174. { index: 3, type: 'insert', values: [ '1', '2', '3' ] },
  175. { index: 6, type: 'delete', howMany: 1 }
  176. ], false );
  177. } );
  178. it( 'should diff insertion of duplicated content', () => {
  179. expectDiff( '1234', '13424', [
  180. { index: 1, type: 'insert', values: [ '3', '4', '2' ] },
  181. { index: 4, type: 'delete', howMany: 2 }
  182. ], false );
  183. } );
  184. it( 'should diff replacement in the middle', () => {
  185. expectDiff( '12345', '12ab5', [
  186. { index: 2, type: 'insert', values: [ 'a', 'b' ] },
  187. { index: 4, type: 'delete', howMany: 2 }
  188. ] );
  189. } );
  190. it( 'should diff replacement in the middle (repetitive substring)', () => {
  191. // Do not check compatibility with 'diffToChanges' as it generates:
  192. // [ { index: 2, type: 'insert', values: [ '1', '2' ] }, { index: 7, type: 'insert', values: [ '5' ] } ]
  193. expectDiff( '12345', '12123455', [
  194. { index: 2, type: 'insert', values: [ '1', '2', '3', '4', '5' ] },
  195. { index: 7, type: 'delete', howMany: 2 }
  196. ], false );
  197. } );
  198. it( 'should diff replacement of duplicated content', () => {
  199. // Do not check compatibility with 'diffToChanges' as it has changes in reveres order ('delete', 'insert') here.
  200. expectDiff( '123123', '123333', [
  201. { index: 3, type: 'insert', values: '33'.split( '' ) },
  202. { index: 5, type: 'delete', howMany: 2 }
  203. ], false );
  204. } );
  205. it( 'should diff replacement in array of objects', () => {
  206. const o1 = { foo: 1 };
  207. const o2 = { bar: 2 };
  208. expectDiff( [ o1, o2 ], [ o1, { baz: 3 } ], [
  209. { index: 1, type: 'insert', values: [ { baz: 3 } ] },
  210. { index: 2, type: 'delete', howMany: 1 }
  211. ] );
  212. } );
  213. it( 'should diff insertion in array of objects with comparator', () => {
  214. expectDiff( [ { text: 'foo' }, { text: 'bar' } ], [ { text: 'foo' }, { text: 'baz' } ], [
  215. { index: 1, type: 'insert', values: [ { text: 'baz' } ] },
  216. { index: 2, type: 'delete', howMany: 1 }
  217. ], true, ( a, b ) => a.text === b.text );
  218. } );
  219. } );
  220. } );
  221. describe( 'changes linear', () => {
  222. it( 'should diff identical texts', () => {
  223. expectDiffLinear( '123', '123', 'eee' );
  224. } );
  225. it( 'should diff identical arrays', () => {
  226. expectDiffLinear( [ '1', '2', '3' ], [ '1', '2', '3' ], 'eee' );
  227. } );
  228. it( 'should diff arrays with custom comparator', () => {
  229. expectDiffLinear( [ 'a', 'b', 'c' ], [ 'A', 'B', 'C' ], 'eee', true, ( a, b ) => a.toLowerCase() === b.toLowerCase() );
  230. } );
  231. describe( 'insertion', () => {
  232. it( 'should diff if old text is empty', () => {
  233. expectDiffLinear( '', '123', 'iii' );
  234. } );
  235. it( 'should diff if old array is empty', () => {
  236. expectDiffLinear( [], [ '1', '2', '3' ], 'iii' );
  237. } );
  238. it( 'should diff insertion on the beginning', () => {
  239. expectDiffLinear( '123', 'abc123', 'iiieee' );
  240. } );
  241. it( 'should diff insertion on the beginning (repetitive substring)', () => {
  242. expectDiffLinear( '123', 'ab123c123', 'iiiiiieee', false );
  243. } );
  244. it( 'should diff insertion on the end', () => {
  245. expectDiffLinear( '123', '123abc', 'eeeiii' );
  246. } );
  247. it( 'should diff insertion on the end (repetitive substring)', () => {
  248. expectDiffLinear( '123', '123ab123c', 'eeeiiiiii' );
  249. } );
  250. it( 'should diff insertion in the middle', () => {
  251. expectDiffLinear( '123', '12abc3', 'eeiiie' );
  252. } );
  253. it( 'should diff insertion in the middle (repetitive substring)', () => {
  254. expectDiffLinear( '123', '12ab123c3', 'eeiiiiiie', false );
  255. } );
  256. it( 'should diff insertion of duplicated content', () => {
  257. expectDiffLinear( '123', '123123', 'eeeiii' );
  258. } );
  259. it( 'should diff insertion of partially duplicated content', () => {
  260. expectDiffLinear( '123', '12323', 'eeeii' );
  261. } );
  262. it( 'should diff insertion on both boundaries', () => {
  263. expectDiffLinear( '123', 'ab123c', 'iiiiiiddd', false );
  264. } );
  265. it( 'should diff insertion in array of objects', () => {
  266. const o1 = { foo: 1 };
  267. const o2 = { bar: 2 };
  268. expectDiffLinear( [ o1, o2 ], [ o1, o2, { baz: 3 } ], 'eei' );
  269. } );
  270. it( 'should diff insertion in array of objects with comparator', () => {
  271. expectDiffLinear( [ { text: 'foo' }, { text: 'bar' } ], [ { text: 'foo' }, { text: 'bar' }, { text: 'baz' } ],
  272. 'eei', true, ( a, b ) => a.text === b.text );
  273. } );
  274. } );
  275. describe( 'deletion', () => {
  276. it( 'should diff if new text is empty', () => {
  277. expectDiffLinear( '123', '', 'ddd' );
  278. } );
  279. it( 'should diff if new array is empty', () => {
  280. expectDiffLinear( [ '1', '2', '3' ], [], 'ddd' );
  281. } );
  282. it( 'should diff deletion on the beginning', () => {
  283. expectDiffLinear( 'abc123', '123', 'dddeee' );
  284. } );
  285. it( 'should diff deletion on the beginning (repetitive substring)', () => {
  286. expectDiffLinear( 'ab123c123', '123', 'ddddddeee', false );
  287. } );
  288. it( 'should diff deletion on the end', () => {
  289. expectDiffLinear( '123abc', '123', 'eeeddd' );
  290. } );
  291. it( 'should diff deletion on the end (repetitive substring)', () => {
  292. expectDiffLinear( '123ab123c', '123', 'eeedddddd' );
  293. } );
  294. it( 'should diff deletion in the middle', () => {
  295. expectDiffLinear( '12abc3', '123', 'eeddde' );
  296. } );
  297. it( 'should diff deletion in the middle (repetitive substring)', () => {
  298. expectDiffLinear( '12ab123c3', '123', 'eedddddde', false );
  299. } );
  300. it( 'should diff deletion on both boundaries', () => {
  301. expectDiffLinear( '12abc3', '2ab', 'iiidddddd', false );
  302. } );
  303. it( 'should diff deletion of duplicated content', () => {
  304. expectDiffLinear( '123123', '123', 'eeeddd' );
  305. } );
  306. it( 'should diff deletion of partially duplicated content', () => {
  307. expectDiffLinear( '12323', '123', 'eeedd' );
  308. } );
  309. it( 'should diff deletion of partially duplicated content 2', () => {
  310. expectDiffLinear( '11233', '13', 'eddde', false );
  311. } );
  312. it( 'should diff deletion in array of objects', () => {
  313. const o1 = { foo: 1 };
  314. const o2 = { bar: 2 };
  315. expectDiffLinear( [ o1, o2 ], [ o2 ], 'de' );
  316. } );
  317. it( 'should diff insertion in array of objects with comparator', () => {
  318. expectDiffLinear( [ { text: 'foo' }, { text: 'bar' } ], [ { text: 'bar' } ], 'de', true, ( a, b ) => a.text === b.text );
  319. } );
  320. } );
  321. describe( 'replacement', () => {
  322. it( 'should diff replacement of entire text', () => {
  323. expectDiffLinear( '12345', 'abcd', 'iiiiddddd', false );
  324. } );
  325. it( 'should diff replacement on the beginning', () => {
  326. expectDiffLinear( '12345', 'abcd345', 'iiiiddeee' );
  327. } );
  328. it( 'should diff replacement on the beginning (repetitive substring)', () => {
  329. expectDiffLinear( '12345', '345345', 'iiiddeee', false );
  330. } );
  331. it( 'should diff replacement on the end', () => {
  332. expectDiffLinear( '12345', '12ab', 'eeiiddd', false );
  333. } );
  334. it( 'should diff replacement on the end (repetitive substring)', () => {
  335. expectDiffLinear( '12345', '1231234', 'eeeiiiidd', false );
  336. } );
  337. it( 'should diff insertion of duplicated content', () => {
  338. expectDiffLinear( '1234', '123123', 'eeeiiid' );
  339. } );
  340. it( 'should diff insertion of duplicated content', () => {
  341. expectDiffLinear( '1234', '13424', 'eiiidde', false );
  342. } );
  343. it( 'should diff replacement in the middle', () => {
  344. expectDiffLinear( '12345', '12ab5', 'eeiidde' );
  345. } );
  346. it( 'should diff replacement in the middle (repetitive substring)', () => {
  347. expectDiffLinear( '12345', '12123455', 'eeiiiiidde', false );
  348. } );
  349. it( 'should diff replacement of duplicated content', () => {
  350. expectDiffLinear( '123123', '123333', 'eeeiidde', false );
  351. } );
  352. it( 'should diff replacement in array of objects', () => {
  353. const o1 = { foo: 1 };
  354. const o2 = { bar: 2 };
  355. expectDiffLinear( [ o1, o2 ], [ o1, { baz: 3 } ], 'eid' );
  356. } );
  357. it( 'should diff insertion in array of objects with comparator', () => {
  358. expectDiffLinear( [ { text: 'foo' }, { text: 'bar' } ], [ { text: 'foo' }, { text: 'baz' } ], 'eid',
  359. true, ( a, b ) => a.text === b.text );
  360. } );
  361. } );
  362. } );
  363. } );
  364. function expectDiff( oldText, newText, expected, checkDiffToChangesCompatibility = true, comparator = null ) {
  365. const result = fastDiff( oldText, newText, comparator );
  366. expect( result ).to.deep.equals( expected, 'fastDiff changes failed' );
  367. if ( checkDiffToChangesCompatibility ) {
  368. expect( result ).to.deep.equals(
  369. diffToChanges( diff( oldText, newText, comparator ), newText ), 'diffToChanges compatibility failed' );
  370. }
  371. }
  372. function expectDiffLinear( oldText, newText, expected, checkDiffCompatibility = true, comparator = null ) {
  373. const actions = { d: 'delete', e: 'equal', i: 'insert' };
  374. const expectedArray = expected.split( '' ).map( item => actions[ item ] );
  375. const result = fastDiff( oldText, newText, comparator, true );
  376. expect( result ).to.deep.equals( expectedArray, 'fastDiff linear result failed' );
  377. if ( checkDiffCompatibility ) {
  378. expect( result ).to.deep.equals( diff( oldText, newText, comparator ), 'diff compatibility failed' );
  379. }
  380. }