8
0

fastdiff.js 19 KB

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