8
0

transform.js 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698
  1. /**
  2. * @license Copyright (c) 2003-2017, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. /**
  6. * @module engine/model/operation/transform
  7. */
  8. import InsertOperation from './insertoperation';
  9. import AttributeOperation from './attributeoperation';
  10. import RootAttributeOperation from './rootattributeoperation';
  11. import RenameOperation from './renameoperation';
  12. import MarkerOperation from './markeroperation';
  13. import MoveOperation from './moveoperation';
  14. import RemoveOperation from './removeoperation';
  15. import ReinsertOperation from './reinsertoperation';
  16. import NoOperation from './nooperation';
  17. import Range from '../range';
  18. import compareArrays from '@ckeditor/ckeditor5-utils/src/comparearrays';
  19. /**
  20. * Transforms given {@link module:engine/model/operation/operation~Operation operation}
  21. * by another {@link module:engine/model/operation/operation~Operation operation}
  22. * and returns the result of that transformation as an array containing
  23. * one or more {@link module:engine/model/operation/operation~Operation operations}.
  24. *
  25. * Operations work on specified positions, passed to them when they are created.
  26. * Whenever {@link module:engine/model/document~Document document}
  27. * changes, we have to reflect those modifications by updating or "transforming" operations which are not yet applied.
  28. * When an operation is transformed, its parameters may change based on the operation by which it is transformed.
  29. * If the transform-by operation applied any modifications to the Tree Data Model which affect positions or nodes
  30. * connected with transformed operation, those changes will be reflected in the parameters of the returned operation(s).
  31. *
  32. * Whenever the {@link module:engine/model/document~Document document}
  33. * has different {@link module:engine/model/document~Document#version}
  34. * than the operation you want to {@link module:engine/model/document~Document#applyOperation apply}, you need to transform that
  35. * operation by all operations which were already applied to the {@link module:engine/model/document~Document document} and have greater
  36. * {@link module:engine/model/document~Document#version} than the operation being applied. Transform them in the same order as those
  37. * operations which were applied. This way all modifications done to the Tree Data Model will be reflected
  38. * in the operation parameters and the operation will "operate" on "up-to-date" version of the Tree Data Model.
  39. * This is mostly the case with Operational Transformations but it might be needed in particular features as well.
  40. *
  41. * In some cases, when given operation apply changes to the same nodes as this operation, two or more operations need
  42. * to be created as one would not be able to reflect the combination of these operations.
  43. * This is why an array is returned instead of a single object. All returned operations have to be applied
  44. * (or further transformed) to get an effect which was intended in pre-transformed operation.
  45. *
  46. * Sometimes two operations are in conflict. This happens when they modify the same node in a different way, i.e.
  47. * set different value for the same attribute or move the node into different positions. When this happens,
  48. * we need to decide which operation is more important. We can't assume that operation `a` or operation `b` is always
  49. * more important. In Operational Transformations algorithms we often need to get a result of transforming
  50. * `a` by `b` and also `b` by `a`. In both transformations the same operation has to be the important one. If we assume
  51. * that first or the second passed operation is always more important we won't be able to solve this case.
  52. *
  53. * @function module:engine/model/operation/transform~transform
  54. * @param {module:engine/model/operation/operation~Operation} a Operation that will be transformed.
  55. * @param {module:engine/model/operation/operation~Operation} b Operation to transform by.
  56. * @param {module:engine/model/delta/transform~transformationContext} [context] Transformation context.
  57. * @returns {Array.<module:engine/model/operation/operation~Operation>} Result of the transformation.
  58. */
  59. export default transform;
  60. const ot = {
  61. InsertOperation: {
  62. // Transforms InsertOperation `a` by InsertOperation `b`. Accepts a flag stating whether `a` is more important
  63. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  64. InsertOperation( a, b, context ) {
  65. // Transformed operations are always new instances, not references to the original operations.
  66. const transformed = a.clone();
  67. // Check whether there is a forced order of nodes or use `context.isStrong` flag for conflict resolving.
  68. const insertBefore = context.insertBefore === undefined ? !context.isStrong : context.insertBefore;
  69. // Transform insert position by the other operation position.
  70. transformed.position = transformed.position._getTransformedByInsertion( b.position, b.nodes.maxOffset, insertBefore );
  71. return [ transformed ];
  72. },
  73. AttributeOperation: doNotUpdate,
  74. RootAttributeOperation: doNotUpdate,
  75. RenameOperation: doNotUpdate,
  76. MarkerOperation: doNotUpdate,
  77. // Transforms InsertOperation `a` by MoveOperation `b`. Accepts a flag stating whether `a` is more important
  78. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  79. MoveOperation( a, b, context ) {
  80. const transformed = a.clone();
  81. // Check whether there is a forced order of nodes or use `context.isStrong` flag for conflict resolving.
  82. const insertBefore = context.insertBefore === undefined ? !context.isStrong : context.insertBefore;
  83. // Transform insert position by the other operation parameters.
  84. transformed.position = a.position._getTransformedByMove(
  85. b.sourcePosition,
  86. b.targetPosition,
  87. b.howMany,
  88. insertBefore,
  89. b.isSticky && !context.forceNotSticky
  90. );
  91. return [ transformed ];
  92. }
  93. },
  94. AttributeOperation: {
  95. // Transforms AttributeOperation `a` by InsertOperation `b`. Returns results as an array of operations.
  96. InsertOperation( a, b ) {
  97. // Transform this operation's range.
  98. const ranges = a.range._getTransformedByInsertion( b.position, b.nodes.maxOffset, true, false );
  99. // Map transformed range(s) to operations and return them.
  100. return ranges.reverse().map( range => {
  101. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
  102. } );
  103. },
  104. // Transforms AttributeOperation `a` by AttributeOperation `b`. Accepts a flag stating whether `a` is more important
  105. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  106. AttributeOperation( a, b, context ) {
  107. if ( a.key === b.key ) {
  108. // If operations attributes are in conflict, check if their ranges intersect and manage them properly.
  109. // First, we want to apply change to the part of a range that has not been changed by the other operation.
  110. const operations = a.range.getDifference( b.range ).map( range => {
  111. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
  112. } );
  113. // Then we take care of the common part of ranges.
  114. const common = a.range.getIntersection( b.range );
  115. if ( common ) {
  116. // If this operation is more important, we also want to apply change to the part of the
  117. // original range that has already been changed by the other operation. Since that range
  118. // got changed we also have to update `oldValue`.
  119. if ( context.isStrong ) {
  120. operations.push( new AttributeOperation( common, b.key, b.newValue, a.newValue, a.baseVersion ) );
  121. } else if ( operations.length === 0 ) {
  122. operations.push( new NoOperation( 0 ) );
  123. }
  124. }
  125. return operations;
  126. } else {
  127. // If operations don't conflict, simply return an array containing just a clone of this operation.
  128. return [ a.clone() ];
  129. }
  130. },
  131. RootAttributeOperation: doNotUpdate,
  132. RenameOperation: doNotUpdate,
  133. MarkerOperation: doNotUpdate,
  134. // Transforms AttributeOperation `a` by MoveOperation `b`. Returns results as an array of operations.
  135. MoveOperation( a, b ) {
  136. // Convert MoveOperation properties into a range.
  137. const rangeB = Range.createFromPositionAndShift( b.sourcePosition, b.howMany );
  138. // This will aggregate transformed ranges.
  139. let ranges = [];
  140. // Difference is a part of changed range that is modified by AttributeOperation but is not affected
  141. // by MoveOperation. This can be zero, one or two ranges (if moved range is inside changed range).
  142. // Right now we will make a simplification and join difference ranges and transform them as one. We will cover rangeB later.
  143. const difference = joinRanges( a.range.getDifference( rangeB ) );
  144. // Common is a range of nodes that is affected by MoveOperation. So it got moved to other place.
  145. const common = a.range.getIntersection( rangeB );
  146. if ( difference !== null ) {
  147. // MoveOperation removes nodes from their original position. We acknowledge this by proper transformation.
  148. // Take the start and the end of the range and transform them by deletion of moved nodes.
  149. // Note that if rangeB was inside AttributeOperation range, only difference.end will be transformed.
  150. // This nicely covers the joining simplification we did in the previous step.
  151. difference.start = difference.start._getTransformedByDeletion( b.sourcePosition, b.howMany );
  152. difference.end = difference.end._getTransformedByDeletion( b.sourcePosition, b.howMany );
  153. // MoveOperation pastes nodes into target position. We acknowledge this by proper transformation.
  154. // Note that since we operate on transformed difference range, we should transform by
  155. // previously transformed target position.
  156. // Note that we do not use Position._getTransformedByMove on range boundaries because we need to
  157. // transform by insertion a range as a whole, since newTargetPosition might be inside that range.
  158. ranges = difference._getTransformedByInsertion( b.getMovedRangeStart(), b.howMany, true, false ).reverse();
  159. }
  160. if ( common !== null ) {
  161. // Here we do not need to worry that newTargetPosition is inside moved range, because that
  162. // would mean that the MoveOperation targets into itself, and that is incorrect operation.
  163. // Instead, we calculate the new position of that part of original range.
  164. common.start = common.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  165. common.end = common.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  166. ranges.push( common );
  167. }
  168. // Map transformed range(s) to operations and return them.
  169. return ranges.map( range => {
  170. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
  171. } );
  172. }
  173. },
  174. RootAttributeOperation: {
  175. InsertOperation: doNotUpdate,
  176. AttributeOperation: doNotUpdate,
  177. // Transforms RootAttributeOperation `a` by RootAttributeOperation `b`. Accepts a flag stating whether `a` is more important
  178. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  179. RootAttributeOperation( a, b, context ) {
  180. if ( a.root === b.root && a.key === b.key ) {
  181. if ( ( a.newValue !== b.newValue && !context.isStrong ) || a.newValue === b.newValue ) {
  182. return [ new NoOperation( a.baseVersion ) ];
  183. }
  184. }
  185. return [ a.clone() ];
  186. },
  187. RenameOperation: doNotUpdate,
  188. MarkerOperation: doNotUpdate,
  189. MoveOperation: doNotUpdate
  190. },
  191. RenameOperation: {
  192. // Transforms RenameOperation `a` by InsertOperation `b`. Returns results as an array of operations.
  193. InsertOperation( a, b ) {
  194. // Clone the operation, we don't want to alter the original operation.
  195. const clone = a.clone();
  196. // Transform this operation's position.
  197. clone.position = clone.position._getTransformedByInsertion( b.position, b.nodes.maxOffset, true );
  198. return [ clone ];
  199. },
  200. AttributeOperation: doNotUpdate,
  201. RootAttributeOperation: doNotUpdate,
  202. // Transforms RenameOperation `a` by RenameOperation `b`. Accepts a flag stating whether `a` is more important
  203. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  204. RenameOperation( a, b, context ) {
  205. // Clone the operation, we don't want to alter the original operation.
  206. const clone = a.clone();
  207. if ( a.position.isEqual( b.position ) ) {
  208. if ( context.isStrong ) {
  209. clone.oldName = b.newName;
  210. } else {
  211. return [ new NoOperation( a.baseVersion ) ];
  212. }
  213. }
  214. return [ clone ];
  215. },
  216. MarkerOperation: doNotUpdate,
  217. // Transforms RenameOperation `a` by MoveOperation `b`. Returns results as an array of operations.
  218. MoveOperation( a, b ) {
  219. const clone = a.clone();
  220. const isSticky = clone.position.isEqual( b.sourcePosition );
  221. clone.position = clone.position._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany, true, isSticky );
  222. return [ clone ];
  223. }
  224. },
  225. MarkerOperation: {
  226. // Transforms MarkerOperation `a` by InsertOperation `b`. Returns results as an array of operations.
  227. InsertOperation( a, b ) {
  228. // Clone the operation, we don't want to alter the original operation.
  229. const clone = a.clone();
  230. if ( clone.oldRange ) {
  231. clone.oldRange = clone.oldRange._getTransformedByInsertion( b.position, b.nodes.maxOffset, false, false )[ 0 ];
  232. }
  233. if ( clone.newRange ) {
  234. clone.newRange = clone.newRange._getTransformedByInsertion( b.position, b.nodes.maxOffset, false, false )[ 0 ];
  235. }
  236. return [ clone ];
  237. },
  238. AttributeOperation: doNotUpdate,
  239. RootAttributeOperation: doNotUpdate,
  240. RenameOperation: doNotUpdate,
  241. // Transforms MarkerOperation `a` by MarkerOperation `b`. Accepts a flag stating whether `a` is more important
  242. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  243. MarkerOperation( a, b, context ) {
  244. // Clone the operation, we don't want to alter the original operation.
  245. const clone = a.clone();
  246. if ( a.name == b.name ) {
  247. if ( context.isStrong ) {
  248. clone.oldRange = b.newRange;
  249. } else {
  250. return [ new NoOperation( a.baseVersion ) ];
  251. }
  252. }
  253. return [ clone ];
  254. },
  255. // Transforms MarkerOperation `a` by MoveOperation `b`. Returns results as an array of operations.
  256. MoveOperation( a, b ) {
  257. // Clone the operation, we don't want to alter the original operation.
  258. const clone = a.clone();
  259. if ( clone.oldRange ) {
  260. const oldRanges = clone.oldRange._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  261. clone.oldRange = Range.createFromRanges( oldRanges );
  262. }
  263. if ( clone.newRange ) {
  264. const newRanges = clone.newRange._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  265. clone.newRange = Range.createFromRanges( newRanges );
  266. }
  267. return [ clone ];
  268. }
  269. },
  270. MoveOperation: {
  271. // Transforms MoveOperation `a` by InsertOperation `b`. Accepts a flag stating whether `a` is more important
  272. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  273. InsertOperation( a, b, context ) {
  274. // Create range from MoveOperation properties and transform it by insertion.
  275. let range = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  276. const includeB = a.isSticky && !context.forceNotSticky;
  277. range = range._getTransformedByInsertion( b.position, b.nodes.maxOffset, false, includeB )[ 0 ];
  278. // Check whether there is a forced order of nodes or use `context.isStrong` flag for conflict resolving.
  279. const insertBefore = context.insertBefore === undefined ? !context.isStrong : context.insertBefore;
  280. const result = new a.constructor(
  281. range.start,
  282. range.end.offset - range.start.offset,
  283. a.targetPosition._getTransformedByInsertion( b.position, b.nodes.maxOffset, insertBefore ),
  284. a.baseVersion
  285. );
  286. result.isSticky = a.isSticky;
  287. return [ result ];
  288. },
  289. AttributeOperation: doNotUpdate,
  290. RootAttributeOperation: doNotUpdate,
  291. RenameOperation: doNotUpdate,
  292. MarkerOperation: doNotUpdate,
  293. // Transforms MoveOperation `a` by MoveOperation `b`. Accepts a flag stating whether `a` is more important
  294. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  295. MoveOperation( a, b, context ) {
  296. //
  297. // Setting and evaluating some variables that will be used in special cases and default algorithm.
  298. //
  299. // Create ranges from `MoveOperations` properties.
  300. const rangeA = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  301. const rangeB = Range.createFromPositionAndShift( b.sourcePosition, b.howMany );
  302. // Assign `context.isStrong` to a different variable, because the value may change during execution of
  303. // this algorithm and we do not want to override original `context.isStrong` that will be used in later transformations.
  304. let isStrong = context.isStrong;
  305. // Whether range moved by operation `b` is includable in operation `a` move range.
  306. // For this, `a` operation has to be sticky (so `b` sticks to the range) and context has to allow stickiness.
  307. const includeB = a.isSticky && !context.forceNotSticky;
  308. // Evaluate new target position for transformed operation.
  309. // Check whether there is a forced order of nodes or use `isStrong` flag for conflict resolving.
  310. const insertBefore = context.insertBefore === undefined ? !isStrong : context.insertBefore;
  311. // `a.targetPosition` could be affected by the `b` operation. We will transform it.
  312. const newTargetPosition = a.targetPosition._getTransformedByMove(
  313. b.sourcePosition,
  314. b.targetPosition,
  315. b.howMany,
  316. insertBefore,
  317. b.isSticky && !context.forceNotSticky
  318. );
  319. //
  320. // Special case #1 + mirror.
  321. //
  322. // Special case when both move operations' target positions are inside nodes that are
  323. // being moved by the other move operation. So in other words, we move ranges into inside of each other.
  324. // This case can't be solved reasonably (on the other hand, it should not happen often).
  325. if ( moveTargetIntoMovedRange( a, b ) && moveTargetIntoMovedRange( b, a ) ) {
  326. // Instead of transforming operation, we return a reverse of the operation that we transform by.
  327. // So when the results of this "transformation" will be applied, `b` MoveOperation will get reversed.
  328. return [ b.getReversed() ];
  329. }
  330. //
  331. // End of special case #1.
  332. //
  333. //
  334. // Special case #2.
  335. //
  336. // Check if `b` operation targets inside `rangeA`. Use stickiness if possible.
  337. const bTargetsToA = rangeA.containsPosition( b.targetPosition ) ||
  338. ( rangeA.start.isEqual( b.targetPosition ) && includeB ) ||
  339. ( rangeA.end.isEqual( b.targetPosition ) && includeB );
  340. // If `b` targets to `rangeA` and `rangeA` contains `rangeB`, `b` operation has no influence on `a` operation.
  341. // You might say that operation `b` is captured inside operation `a`.
  342. if ( bTargetsToA && rangeA.containsRange( rangeB, true ) ) {
  343. // There is a mini-special case here, where `rangeB` is on other level than `rangeA`. That's why
  344. // we need to transform `a` operation anyway.
  345. rangeA.start = rangeA.start._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany, !includeB );
  346. rangeA.end = rangeA.end._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany, includeB );
  347. return makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition, a );
  348. }
  349. //
  350. // Special case #2 mirror.
  351. //
  352. const aTargetsToB = rangeB.containsPosition( a.targetPosition ) ||
  353. ( rangeB.start.isEqual( a.targetPosition ) && b.isSticky && !context.forceNotSticky ) ||
  354. ( rangeB.end.isEqual( a.targetPosition ) && b.isSticky && !context.forceNotSticky );
  355. if ( aTargetsToB && rangeB.containsRange( rangeA, true ) ) {
  356. // `a` operation is "moved together" with `b` operation.
  357. // Here, just move `rangeA` "inside" `rangeB`.
  358. rangeA.start = rangeA.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  359. rangeA.end = rangeA.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  360. return makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition, a );
  361. }
  362. //
  363. // End of special case #2.
  364. //
  365. //
  366. // Special case #3 + mirror.
  367. //
  368. // `rangeA` has a node which is an ancestor of `rangeB`. In other words, `rangeB` is inside `rangeA`
  369. // but not on the same tree level. In such case ranges have common part but we have to treat it
  370. // differently, because in such case those ranges are not really conflicting and should be treated like
  371. // two separate ranges. Also we have to discard two difference parts.
  372. const aCompB = compareArrays( a.sourcePosition.getParentPath(), b.sourcePosition.getParentPath() );
  373. if ( aCompB == 'prefix' || aCompB == 'extension' ) {
  374. // Transform `rangeA` by `b` operation and make operation out of it, and that's all.
  375. // Note that this is a simplified version of default case, but here we treat the common part (whole `rangeA`)
  376. // like a one difference part.
  377. rangeA.start = rangeA.start._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany, !includeB );
  378. rangeA.end = rangeA.end._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany, includeB );
  379. return makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition, a );
  380. }
  381. //
  382. // End of special case #3.
  383. //
  384. //
  385. // Default case - ranges are on the same level or are not connected with each other.
  386. //
  387. // Modifier for default case.
  388. // Modifies `isStrong` flag in certain conditions.
  389. //
  390. // If only one of operations is a remove operation, we force remove operation to be the "stronger" one
  391. // to provide more expected results. This is done only if `context.forceWeakRemove` is set to `false`.
  392. // `context.forceWeakRemove` is set to `true` in certain conditions when transformation takes place during undo.
  393. if ( !context.forceWeakRemove ) {
  394. if ( a instanceof RemoveOperation && !( b instanceof RemoveOperation ) ) {
  395. isStrong = true;
  396. } else if ( !( a instanceof RemoveOperation ) && b instanceof RemoveOperation ) {
  397. isStrong = false;
  398. }
  399. }
  400. // Handle operation's source ranges - check how `rangeA` is affected by `b` operation.
  401. // This will aggregate transformed ranges.
  402. const ranges = [];
  403. // Get the "difference part" of `a` operation source range.
  404. // This is an array with one or two ranges. Two ranges if `rangeB` is inside `rangeA`.
  405. const difference = rangeA.getDifference( rangeB );
  406. for ( const range of difference ) {
  407. // Transform those ranges by `b` operation. For example if `b` moved range from before those ranges, fix those ranges.
  408. range.start = range.start._getTransformedByDeletion( b.sourcePosition, b.howMany );
  409. range.end = range.end._getTransformedByDeletion( b.sourcePosition, b.howMany );
  410. // If `b` operation targets into `rangeA` on the same level, spread `rangeA` into two ranges.
  411. const shouldSpread = compareArrays( range.start.getParentPath(), b.getMovedRangeStart().getParentPath() ) == 'same';
  412. const newRanges = range._getTransformedByInsertion( b.getMovedRangeStart(), b.howMany, shouldSpread, includeB );
  413. ranges.push( ...newRanges );
  414. }
  415. // Then, we have to manage the "common part" of both move ranges.
  416. const common = rangeA.getIntersection( rangeB );
  417. if ( common !== null && isStrong && !bTargetsToA ) {
  418. // Calculate the new position of that part of original range.
  419. common.start = common.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  420. common.end = common.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  421. // Take care of proper range order.
  422. //
  423. // Put `common` at appropriate place. Keep in mind that we are interested in original order.
  424. // Basically there are only three cases: there is zero, one or two difference ranges.
  425. //
  426. // If there is zero difference ranges, just push `common` in the array.
  427. if ( ranges.length === 0 ) {
  428. ranges.push( common );
  429. }
  430. // If there is one difference range, we need to check whether common part was before it or after it.
  431. else if ( ranges.length == 1 ) {
  432. if ( rangeB.start.isBefore( rangeA.start ) || rangeB.start.isEqual( rangeA.start ) ) {
  433. ranges.unshift( common );
  434. } else {
  435. ranges.push( common );
  436. }
  437. }
  438. // If there are more ranges (which means two), put common part between them. This is the only scenario
  439. // where there could be two difference ranges so we don't have to make any comparisons.
  440. else {
  441. ranges.splice( 1, 0, common );
  442. }
  443. }
  444. if ( ranges.length === 0 ) {
  445. // If there are no "source ranges", nothing should be changed.
  446. // Note that this can happen only if `isStrong == false` and `rangeA.isEqual( rangeB )`.
  447. return [ new NoOperation( a.baseVersion ) ];
  448. }
  449. return makeMoveOperationsFromRanges( ranges, newTargetPosition, a );
  450. }
  451. }
  452. };
  453. function transform( a, b, context = { isStrong: false } ) {
  454. let group, algorithm;
  455. if ( a instanceof InsertOperation ) {
  456. group = ot.InsertOperation;
  457. } else if ( a instanceof AttributeOperation ) {
  458. group = ot.AttributeOperation;
  459. } else if ( a instanceof RootAttributeOperation ) {
  460. group = ot.RootAttributeOperation;
  461. } else if ( a instanceof RenameOperation ) {
  462. group = ot.RenameOperation;
  463. } else if ( a instanceof MarkerOperation ) {
  464. group = ot.MarkerOperation;
  465. } else if ( a instanceof MoveOperation ) {
  466. group = ot.MoveOperation;
  467. } else {
  468. algorithm = doNotUpdate;
  469. }
  470. if ( group ) {
  471. if ( b instanceof InsertOperation ) {
  472. algorithm = group.InsertOperation;
  473. } else if ( b instanceof AttributeOperation ) {
  474. algorithm = group.AttributeOperation;
  475. } else if ( b instanceof RootAttributeOperation ) {
  476. algorithm = group.RootAttributeOperation;
  477. } else if ( b instanceof RenameOperation ) {
  478. algorithm = group.RenameOperation;
  479. } else if ( b instanceof MarkerOperation ) {
  480. algorithm = group.MarkerOperation;
  481. } else if ( b instanceof MoveOperation ) {
  482. algorithm = group.MoveOperation;
  483. } else {
  484. algorithm = doNotUpdate;
  485. }
  486. }
  487. const transformed = algorithm( a, b, context );
  488. return updateBaseVersions( a.baseVersion, transformed );
  489. }
  490. // When we don't want to update an operation, we create and return a clone of it.
  491. // Returns the operation in "unified format" - wrapped in an Array.
  492. function doNotUpdate( operation ) {
  493. return [ operation.clone() ];
  494. }
  495. // Takes an Array of operations and sets consecutive base versions for them, starting from given base version.
  496. // Returns the passed array.
  497. function updateBaseVersions( baseVersion, operations ) {
  498. for ( let i = 0; i < operations.length; i++ ) {
  499. operations[ i ].baseVersion = baseVersion + i + 1;
  500. }
  501. return operations;
  502. }
  503. // Checks whether MoveOperation targetPosition is inside a node from the moved range of the other MoveOperation.
  504. function moveTargetIntoMovedRange( a, b ) {
  505. return a.targetPosition._getTransformedByDeletion( b.sourcePosition, b.howMany ) === null;
  506. }
  507. // Gets an array of Ranges and produces one Range out of it. The root of a new range will be same as
  508. // the root of the first range in the array. If any of given ranges has different root than the first range,
  509. // it will be discarded.
  510. function joinRanges( ranges ) {
  511. if ( ranges.length === 0 ) {
  512. return null;
  513. } else if ( ranges.length == 1 ) {
  514. return ranges[ 0 ];
  515. } else {
  516. ranges[ 0 ].end = ranges[ ranges.length - 1 ].end;
  517. return ranges[ 0 ];
  518. }
  519. }
  520. // Helper function for `MoveOperation` x `MoveOperation` transformation.
  521. // Convert given ranges and target position to move operations and return them.
  522. // Ranges and target position will be transformed on-the-fly when generating operations.
  523. // Given `ranges` should be in the order of how they were in the original transformed operation.
  524. // Given `targetPosition` is the target position of the first range from `ranges`.
  525. function makeMoveOperationsFromRanges( ranges, targetPosition, a ) {
  526. // At this moment we have some ranges and a target position, to which those ranges should be moved.
  527. // Order in `ranges` array is the go-to order of after transformation.
  528. //
  529. // We are almost done. We have `ranges` and `targetPosition` to make operations from.
  530. // Unfortunately, those operations may affect each other. Precisely, first operation after move
  531. // may affect source range and target position of second and third operation. Same with second
  532. // operation affecting third.
  533. //
  534. // We need to fix those source ranges and target positions once again, before converting `ranges` to operations.
  535. const operations = [];
  536. // Keep in mind that nothing will be transformed if there is just one range in `ranges`.
  537. for ( let i = 0; i < ranges.length; i++ ) {
  538. // Create new operation out of a range and target position.
  539. const op = makeMoveOperation( ranges[ i ], targetPosition, a.isSticky );
  540. operations.push( op );
  541. // Transform other ranges by the generated operation.
  542. for ( let j = i + 1; j < ranges.length; j++ ) {
  543. // All ranges in `ranges` array should be:
  544. // * non-intersecting (these are part of original operation source range), and
  545. // * `targetPosition` does not target into them (opposite would mean that transformed operation targets "inside itself").
  546. //
  547. // This means that the transformation will be "clean" and always return one result.
  548. ranges[ j ] = ranges[ j ]._getTransformedByMove( op.sourcePosition, op.targetPosition, op.howMany )[ 0 ];
  549. }
  550. targetPosition = targetPosition._getTransformedByMove( op.sourcePosition, op.targetPosition, op.howMany, true, false );
  551. }
  552. return operations;
  553. }
  554. function makeMoveOperation( range, targetPosition, isSticky ) {
  555. // We want to keep correct operation class.
  556. let OperationClass;
  557. if ( targetPosition.root.rootName == '$graveyard' ) {
  558. OperationClass = RemoveOperation;
  559. } else if ( range.start.root.rootName == '$graveyard' ) {
  560. OperationClass = ReinsertOperation;
  561. } else {
  562. OperationClass = MoveOperation;
  563. }
  564. const result = new OperationClass(
  565. range.start,
  566. range.end.offset - range.start.offset,
  567. targetPosition,
  568. 0 // Is corrected anyway later.
  569. );
  570. result.isSticky = isSticky;
  571. return result;
  572. }