transform.js 16 KB

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