8
0

transform.js 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550
  1. /**
  2. * @license Copyright (c) 2003-2017, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. import transformations from '../../../../src/model/delta/basic-transformations'; // eslint-disable-line no-unused-vars
  6. import deltaTransform from '../../../../src/model/delta/transform';
  7. const transformDeltaSets = deltaTransform.transformDeltaSets;
  8. import Document from '../../../../src/model/document';
  9. import Element from '../../../../src/model/element';
  10. import Text from '../../../../src/model/text';
  11. import Position from '../../../../src/model/position';
  12. import Delta from '../../../../src/model/delta/delta';
  13. import InsertDelta from '../../../../src/model/delta/insertdelta';
  14. import RemoveDelta from '../../../../src/model/delta/removedelta';
  15. import MoveDelta from '../../../../src/model/delta/movedelta';
  16. import SplitDelta from '../../../../src/model/delta/splitdelta';
  17. import UnwrapDelta from '../../../../src/model/delta/unwrapdelta';
  18. import NoOperation from '../../../../src/model/operation/nooperation';
  19. import MoveOperation from '../../../../src/model/operation/moveoperation';
  20. import RemoveOperation from '../../../../src/model/operation/removeoperation';
  21. import ReinsertOperation from '../../../../src/model/operation/reinsertoperation';
  22. import InsertOperation from '../../../../src/model/operation/insertoperation';
  23. import {
  24. expectDelta,
  25. getInsertDelta,
  26. getSplitDelta,
  27. getRemoveDelta,
  28. getMoveDelta,
  29. getMergeDelta,
  30. getUnwrapDelta
  31. } from '../../../../tests/model/delta/transform/_utils/utils';
  32. describe( 'transform', () => {
  33. let doc, root, baseVersion;
  34. beforeEach( () => {
  35. doc = new Document();
  36. root = doc.createRoot();
  37. root.appendChildren( new Element( 'p', null, new Text( 'foobar' ) ) );
  38. baseVersion = doc.version;
  39. } );
  40. describe( 'transformDeltaSets', () => {
  41. it( 'should use deltaTransform.transform', () => {
  42. sinon.spy( deltaTransform, 'transform' );
  43. const insertDelta = getInsertDelta( new Position( root, [ 0, 4 ] ), new Text( 'xxx' ), baseVersion );
  44. const removeDelta = getRemoveDelta( new Position( root, [ 0, 0 ] ), 2, baseVersion );
  45. transformDeltaSets( [ insertDelta ], [ removeDelta ] );
  46. expect( deltaTransform.transform.called ).to.be.true;
  47. deltaTransform.transform.restore();
  48. } );
  49. it( 'should transform two arrays of deltas', () => {
  50. const splitDelta = getSplitDelta( new Position( root, [ 0, 3 ] ), new Element( 'p' ), 3, baseVersion );
  51. const insertDeltaX = getInsertDelta( new Position( root, [ 0, 3 ] ), new Text( 'xxx' ), baseVersion + 2 );
  52. const removeDelta = getRemoveDelta( new Position( root, [ 0, 2 ] ), 2, baseVersion );
  53. const insertDeltaY = getInsertDelta( new Position( root, [ 0, 4 ] ), new Text( 'yyy' ), baseVersion + 1 );
  54. const { deltasA, deltasB } = transformDeltaSets( [ splitDelta, insertDeltaX ], [ removeDelta, insertDeltaY ] );
  55. expect( deltasA.length ).to.equal( 3 );
  56. expect( deltasB.length ).to.equal( 3 );
  57. expectDelta( deltasA[ 0 ], {
  58. type: SplitDelta,
  59. operations: [
  60. {
  61. type: InsertOperation,
  62. position: new Position( root, [ 1 ] ),
  63. baseVersion: 2
  64. },
  65. {
  66. type: MoveOperation,
  67. sourcePosition: new Position( root, [ 0, 2 ] ),
  68. howMany: 5,
  69. targetPosition: new Position( root, [ 1, 0 ] ),
  70. baseVersion: 3
  71. }
  72. ]
  73. } );
  74. expectDelta( deltasA[ 1 ], {
  75. type: InsertDelta,
  76. operations: [
  77. {
  78. type: InsertOperation,
  79. position: new Position( root, [ 0, 2 ] ),
  80. baseVersion: 4
  81. }
  82. ]
  83. } );
  84. expectDelta( deltasA[ 2 ], {
  85. type: Delta,
  86. operations: [
  87. {
  88. type: NoOperation,
  89. baseVersion: 5
  90. }
  91. ]
  92. } );
  93. expectDelta( deltasB[ 0 ], {
  94. type: RemoveDelta,
  95. operations: [
  96. {
  97. type: RemoveOperation,
  98. sourcePosition: new Position( root, [ 0, 2 ] ),
  99. howMany: 1,
  100. baseVersion: 3
  101. }
  102. ]
  103. } );
  104. expectDelta( deltasB[ 1 ], {
  105. type: RemoveDelta,
  106. operations: [
  107. {
  108. type: RemoveOperation,
  109. sourcePosition: new Position( root, [ 1, 0 ] ),
  110. howMany: 1,
  111. baseVersion: 4
  112. }
  113. ]
  114. } );
  115. expectDelta( deltasB[ 2 ], {
  116. type: InsertDelta,
  117. operations: [
  118. {
  119. type: InsertOperation,
  120. position: new Position( root, [ 1, 2 ] ),
  121. baseVersion: 5
  122. }
  123. ]
  124. } );
  125. } );
  126. it( 'should transform two arrays of deltas - reverse', () => {
  127. const splitDelta = getSplitDelta( new Position( root, [ 0, 3 ] ), new Element( 'p' ), 3, baseVersion );
  128. const insertDeltaX = getInsertDelta( new Position( root, [ 0, 3 ] ), new Text( 'xxx' ), baseVersion + 2 );
  129. const removeDelta = getRemoveDelta( new Position( root, [ 0, 2 ] ), 2, baseVersion );
  130. const insertDeltaY = getInsertDelta( new Position( root, [ 0, 4 ] ), new Text( 'yyy' ), baseVersion + 1 );
  131. const { deltasA, deltasB } = transformDeltaSets( [ removeDelta, insertDeltaY ], [ splitDelta, insertDeltaX ] );
  132. expect( deltasA.length ).to.equal( 3 );
  133. expect( deltasB.length ).to.equal( 3 );
  134. expectDelta( deltasA[ 0 ], {
  135. type: RemoveDelta,
  136. operations: [
  137. {
  138. type: RemoveOperation,
  139. sourcePosition: new Position( root, [ 0, 2 ] ),
  140. howMany: 1,
  141. baseVersion: 3
  142. }
  143. ]
  144. } );
  145. expectDelta( deltasA[ 1 ], {
  146. type: RemoveDelta,
  147. operations: [
  148. {
  149. type: RemoveOperation,
  150. sourcePosition: new Position( root, [ 1, 0 ] ),
  151. howMany: 1,
  152. baseVersion: 4
  153. }
  154. ]
  155. } );
  156. expectDelta( deltasA[ 2 ], {
  157. type: InsertDelta,
  158. operations: [
  159. {
  160. type: InsertOperation,
  161. position: new Position( root, [ 1, 2 ] ),
  162. baseVersion: 5
  163. }
  164. ]
  165. } );
  166. expectDelta( deltasB[ 0 ], {
  167. type: SplitDelta,
  168. operations: [
  169. {
  170. type: InsertOperation,
  171. position: new Position( root, [ 1 ] ),
  172. baseVersion: 2
  173. },
  174. {
  175. type: MoveOperation,
  176. sourcePosition: new Position( root, [ 0, 2 ] ),
  177. howMany: 5,
  178. targetPosition: new Position( root, [ 1, 0 ] ),
  179. baseVersion: 3
  180. }
  181. ]
  182. } );
  183. expectDelta( deltasB[ 1 ], {
  184. type: InsertDelta,
  185. operations: [
  186. {
  187. type: InsertOperation,
  188. position: new Position( root, [ 0, 2 ] ),
  189. baseVersion: 4
  190. }
  191. ]
  192. } );
  193. expectDelta( deltasB[ 2 ], {
  194. type: Delta,
  195. operations: [
  196. {
  197. type: NoOperation,
  198. baseVersion: 5
  199. }
  200. ]
  201. } );
  202. } );
  203. it( 'should not modify original deltas or arrays', () => {
  204. const insertDeltaA = getInsertDelta( new Position( root, [ 0, 0 ] ), new Text( 'x' ), baseVersion );
  205. const insertDeltaB = getInsertDelta( new Position( root, [ 1, 0 ] ), new Text( 'y' ), baseVersion );
  206. const originalDeltasA = [ insertDeltaA ];
  207. const originalDeltasB = [ insertDeltaB ];
  208. const { deltasA, deltasB } = transformDeltaSets( originalDeltasA, originalDeltasB );
  209. expect( deltasA ).to.not.equal( originalDeltasA );
  210. expect( deltasB ).to.not.equal( originalDeltasB );
  211. expect( deltasA[ 0 ] ).to.not.equal( originalDeltasA[ 0 ] );
  212. expect( deltasB[ 0 ] ).to.not.equal( originalDeltasB[ 0 ] );
  213. } );
  214. describe( 'context', () => {
  215. it( 'first set is important', () => {
  216. const insertDeltaA = getInsertDelta( new Position( root, [ 0, 4 ] ), new Text( 'xxx' ), baseVersion );
  217. const insertDeltaB = getInsertDelta( new Position( root, [ 0, 4 ] ), new Text( 'yyy' ), baseVersion );
  218. const { deltasA, deltasB } = transformDeltaSets( [ insertDeltaA ], [ insertDeltaB ] );
  219. expectDelta( deltasA[ 0 ], {
  220. type: InsertDelta,
  221. operations: [
  222. {
  223. type: InsertOperation,
  224. position: new Position( root, [ 0, 4 ] ),
  225. baseVersion: 1
  226. }
  227. ]
  228. } );
  229. expectDelta( deltasB[ 0 ], {
  230. type: InsertDelta,
  231. operations: [
  232. {
  233. type: InsertOperation,
  234. position: new Position( root, [ 0, 7 ] ),
  235. baseVersion: 1
  236. }
  237. ]
  238. } );
  239. } );
  240. it( 'remove delta is more important if additional context is not used', () => {
  241. const moveDelta = getMoveDelta( new Position( root, [ 0, 4 ] ), 3, new Position( root, [ 1, 0 ] ), baseVersion );
  242. const removeDelta = getRemoveDelta( new Position( root, [ 0, 4 ] ), 3, baseVersion );
  243. const { deltasA, deltasB } = transformDeltaSets( [ moveDelta ], [ removeDelta ] );
  244. expectDelta( deltasA[ 0 ], {
  245. type: Delta,
  246. operations: [
  247. {
  248. type: NoOperation,
  249. baseVersion: 1
  250. }
  251. ]
  252. } );
  253. expectDelta( deltasB[ 0 ], {
  254. type: RemoveDelta,
  255. operations: [
  256. {
  257. type: RemoveOperation,
  258. sourcePosition: new Position( root, [ 1, 0 ] ),
  259. howMany: 3,
  260. targetPosition: new Position( doc.graveyard, [ 0 ] ),
  261. baseVersion: 1
  262. }
  263. ]
  264. } );
  265. } );
  266. it( 'remove delta may be less important if additional context is used and the delta was undone', () => {
  267. const moveDelta = getMoveDelta( new Position( root, [ 0, 4 ] ), 3, new Position( root, [ 1, 0 ] ), baseVersion );
  268. const removeDelta = getRemoveDelta( new Position( root, [ 0, 4 ] ), 3, baseVersion );
  269. // "Fake" delta undoing.
  270. doc.history.setDeltaAsUndone( removeDelta, new Delta() );
  271. const { deltasA, deltasB } = transformDeltaSets( [ moveDelta ], [ removeDelta ], doc );
  272. expectDelta( deltasA[ 0 ], {
  273. type: MoveDelta,
  274. operations: [
  275. {
  276. type: MoveOperation,
  277. sourcePosition: new Position( doc.graveyard, [ 0 ] ),
  278. howMany: 3,
  279. targetPosition: new Position( root, [ 1, 0 ] ),
  280. baseVersion: 1
  281. }
  282. ]
  283. } );
  284. expectDelta( deltasB[ 0 ], {
  285. type: Delta,
  286. operations: [
  287. {
  288. type: NoOperation,
  289. baseVersion: 1
  290. }
  291. ]
  292. } );
  293. } );
  294. // #1053.
  295. it( 'remove operation importance should be set correctly also for deltas other than remove delta', () => {
  296. const unwrapDelta = getUnwrapDelta( new Position( root, [ 0 ] ), 2, baseVersion );
  297. const nodeCopy = new Element( 'p' );
  298. const splitDelta = getSplitDelta( new Position( root, [ 0, 0, 1 ] ), nodeCopy, 1, baseVersion );
  299. const mergeDelta = splitDelta.getReversed();
  300. const { deltasA } = transformDeltaSets( [ unwrapDelta ], [ splitDelta, mergeDelta ], doc );
  301. expect( deltasA.length ).to.equal( 2 );
  302. expectDelta( deltasA[ 0 ], {
  303. type: MoveDelta,
  304. operations: [
  305. {
  306. type: MoveOperation,
  307. sourcePosition: new Position( root, [ 0, 0 ] ),
  308. howMany: 1,
  309. targetPosition: new Position( root, [ 0 ] ),
  310. baseVersion: baseVersion + 4
  311. }
  312. ]
  313. } );
  314. expectDelta( deltasA[ 1 ], {
  315. type: UnwrapDelta,
  316. operations: [
  317. {
  318. type: MoveOperation,
  319. sourcePosition: new Position( root, [ 1, 0 ] ),
  320. howMany: 1,
  321. targetPosition: new Position( root, [ 1 ] ),
  322. baseVersion: baseVersion + 5
  323. },
  324. {
  325. type: RemoveOperation,
  326. sourcePosition: new Position( root, [ 2 ] ),
  327. howMany: 1,
  328. baseVersion: baseVersion + 6
  329. }
  330. ]
  331. } );
  332. } );
  333. it( 'should keep correct order of nodes if additional context is used (insert before)', () => {
  334. // Assume document state: 'a^bcd'. User presses 'delete' key twice.
  335. const removeDelta1 = getRemoveDelta( new Position( root, [ 1 ] ), 1, baseVersion ); // 'acd'.
  336. const removeDelta2 = getRemoveDelta( new Position( root, [ 1 ] ), 1, baseVersion + 1 ); // 'ad'.
  337. const reinsertDelta2 = removeDelta2.getReversed(); // 'acd'.
  338. doc.history.addDelta( removeDelta1 );
  339. doc.history.addDelta( removeDelta2 );
  340. doc.history.addDelta( reinsertDelta2 );
  341. doc.history.setDeltaAsUndone( removeDelta2, reinsertDelta2 );
  342. // This should insert 'b' at offset 1.
  343. // However this delta will be transformed by `reinsertDelta2` which also inserts a node at offset 1.
  344. // This leads to a conflict and history needs to be check how deltas relate to each other.
  345. // Compare this scenario to the scenario below.
  346. const reinsertDelta1 = removeDelta1.getReversed();
  347. const { deltasA } = transformDeltaSets( [ reinsertDelta1 ], [ removeDelta2, reinsertDelta2 ], doc );
  348. expectDelta( deltasA[ 0 ], {
  349. type: MoveDelta,
  350. operations: [
  351. {
  352. type: ReinsertOperation,
  353. targetPosition: new Position( root, [ 1 ] ),
  354. howMany: 1,
  355. baseVersion: 3
  356. }
  357. ]
  358. } );
  359. } );
  360. it( 'should keep correct order of nodes if additional context is used (insert after)', () => {
  361. // Assume document state: 'abc^d'. User presses 'backspace' key twice.
  362. const removeDelta1 = getRemoveDelta( new Position( root, [ 2 ] ), 1, baseVersion ); // 'abd'.
  363. const removeDelta2 = getRemoveDelta( new Position( root, [ 1 ] ), 1, baseVersion + 1 ); // 'ad'.
  364. const reinsertDelta2 = removeDelta2.getReversed(); // 'abd'.
  365. doc.history.addDelta( removeDelta1 );
  366. doc.history.addDelta( removeDelta2 );
  367. doc.history.addDelta( reinsertDelta2 );
  368. doc.history.setDeltaAsUndone( removeDelta2, reinsertDelta2 );
  369. // This should insert 'c' at offset 2.
  370. // However this delta will be first transformed by `removeDelta2`. After that transformation
  371. // the delta will try to insert 'c' at offset 1. Then, it will be transformed by `reinsertDelta2`,
  372. // which also tries to insert node at offset 1.
  373. // This leads to a conflict and history needs to be check how deltas relate to each other.
  374. // Compare this scenario to the scenario below.
  375. // In both cases transformed delta was inserting something at the same position. However, in
  376. // both cases the expected outcome is different.
  377. const reinsertDelta1 = removeDelta1.getReversed();
  378. const { deltasA } = transformDeltaSets( [ reinsertDelta1 ], [ removeDelta2, reinsertDelta2 ], doc );
  379. expectDelta( deltasA[ 0 ], {
  380. type: MoveDelta,
  381. operations: [
  382. {
  383. type: ReinsertOperation,
  384. targetPosition: new Position( root, [ 2 ] ),
  385. howMany: 1,
  386. baseVersion: 3
  387. }
  388. ]
  389. } );
  390. } );
  391. it( 'should not throw if delta transformed by undoing delta was not transformed by undone delta', () => {
  392. // This scenario may happen when deltas are undone in different order than usual LIFO order.
  393. const removeDelta1 = getRemoveDelta( new Position( root, [ 0 ] ), 1, baseVersion );
  394. const removeDelta2 = getRemoveDelta( new Position( root, [ 2 ] ), 1, baseVersion + 1 );
  395. const reinsertDelta1 = removeDelta1.getReversed();
  396. reinsertDelta1.baseVersion = 2;
  397. doc.history.addDelta( removeDelta1 );
  398. doc.history.addDelta( removeDelta2 );
  399. doc.history.addDelta( reinsertDelta1 );
  400. doc.history.setDeltaAsUndone( removeDelta1, reinsertDelta1 );
  401. const reinsertDelta2 = removeDelta2.getReversed();
  402. const { deltasA } = transformDeltaSets( [ reinsertDelta2 ], [ reinsertDelta1 ], doc );
  403. expectDelta( deltasA[ 0 ], {
  404. type: MoveDelta,
  405. operations: [
  406. {
  407. type: MoveOperation,
  408. sourcePosition: new Position( root, [ 0 ] ),
  409. targetPosition: new Position( root, [ 3 ] ),
  410. howMany: 1,
  411. baseVersion: 3
  412. }
  413. ]
  414. } );
  415. } );
  416. it( 'should use stickiness if additional context is not used', () => {
  417. const moveDeltaA = getMoveDelta( new Position( root, [ 0, 0 ] ), 1, new Position( root, [ 1, 0 ] ), baseVersion );
  418. const moveDeltaB = getMoveDelta( new Position( root, [ 1, 0 ] ), 3, new Position( root, [ 2, 2 ] ), baseVersion );
  419. moveDeltaB.operations[ 0 ].isSticky = true;
  420. const { deltasA } = transformDeltaSets( [ moveDeltaA ], [ moveDeltaB ], doc );
  421. expectDelta( deltasA[ 0 ], {
  422. type: MoveDelta,
  423. operations: [
  424. {
  425. type: MoveOperation,
  426. targetPosition: new Position( root, [ 2, 2 ] ),
  427. howMany: 1,
  428. baseVersion: 1
  429. }
  430. ]
  431. } );
  432. } );
  433. it( 'should discard stickiness if additional context is used and delta with sticky move operation has been undone', () => {
  434. // Assume following data model: <paragraph>ab</paragraph><paragraph>cd</paragraph>
  435. // Then we remove 'b': <paragraph>a</paragraph><paragraph>cd</paragraph>
  436. const removeDelta = getRemoveDelta( new Position( root, [ 0, 1 ] ), 1, baseVersion );
  437. // Then we merge paragraphs: <paragraph>acd</paragraph>
  438. // Keep in mind that merging has sticky move operation ('cd' is sticky-moved to the first paragraph).
  439. const mergeDelta = getMergeDelta( new Position( root, [ 1 ] ), 2, 1, baseVersion + 1 );
  440. // Then we reverse merging: <paragraph>a</paragraph><paragraph>cd</paragraph>
  441. // Keep in mind that now we have two deltas with sticky moves in a history.
  442. const splitDelta = mergeDelta.getReversed();
  443. doc.history.addDelta( removeDelta );
  444. doc.history.addDelta( mergeDelta );
  445. doc.history.addDelta( splitDelta );
  446. doc.history.setDeltaAsUndone( mergeDelta, splitDelta );
  447. // This delta should insert 'b' at position [ 0, 1 ].
  448. // However, without context data, after transforming `reinsertDelta` by `splitDelta`,
  449. // 'b' would "go away" together with 'cd'.
  450. const reinsertDelta = removeDelta.getReversed();
  451. const { deltasA } = transformDeltaSets( [ reinsertDelta ], [ mergeDelta, splitDelta ], doc );
  452. expectDelta( deltasA[ 0 ], {
  453. type: MoveDelta,
  454. operations: [
  455. {
  456. type: ReinsertOperation,
  457. targetPosition: new Position( root, [ 0, 1 ] ),
  458. howMany: 1,
  459. baseVersion: 5
  460. }
  461. ]
  462. } );
  463. } );
  464. } );
  465. } );
  466. } );