transform.js 91 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299
  1. import InsertOperation from './insertoperation';
  2. import AttributeOperation from './attributeoperation';
  3. import RenameOperation from './renameoperation';
  4. import MarkerOperation from './markeroperation';
  5. import MoveOperation from './moveoperation';
  6. import RootAttributeOperation from './rootattributeoperation';
  7. import MergeOperation from './mergeoperation';
  8. import SplitOperation from './splitoperation';
  9. import NoOperation from './nooperation';
  10. import Range from '../range';
  11. import Position from '../position';
  12. import compareArrays from '@ckeditor/ckeditor5-utils/src/comparearrays';
  13. import log from '@ckeditor/ckeditor5-utils/src/log';
  14. const transformations = new Map();
  15. /**
  16. * @module engine/model/operation/transform
  17. */
  18. /**
  19. * Sets a transformation function to be be used to transform instances of class `OperationA` by instances of class `OperationB`.
  20. *
  21. * The `transformationFunction` is passed three parameters:
  22. *
  23. * * `a` - operation to be transformed, an instance of `OperationA`,
  24. * * `b` - operation to be transformed by, an instance of `OperationB`,
  25. * * {@link module:engine/model/operation/transform~TransformationContext `context`} - object with additional information about
  26. * transformation context.
  27. *
  28. * The `transformationFunction` should return transformation result, which is an array with one or multiple
  29. * {@link module:engine/model/operation/operation~Operation operation} instances.
  30. *
  31. * @protected
  32. * @param {Function} OperationA
  33. * @param {Function} OperationB
  34. * @param {Function} transformationFunction Function to use for transforming.
  35. */
  36. function setTransformation( OperationA, OperationB, transformationFunction ) {
  37. let aGroup = transformations.get( OperationA );
  38. if ( !aGroup ) {
  39. aGroup = new Map();
  40. transformations.set( OperationA, aGroup );
  41. }
  42. aGroup.set( OperationB, transformationFunction );
  43. }
  44. /**
  45. * Returns a previously set transformation function for transforming an instance of `OperationA` by an instance of `OperationB`.
  46. *
  47. * If no transformation was set for given pair of operations, {@link module:engine/model/operation/transform~noUpdateTransformation}
  48. * is returned. This means that if no transformation was set, the `OperationA` instance will not change when transformed
  49. * by the `OperationB` instance.
  50. *
  51. * @private
  52. * @param {Function} OperationA
  53. * @param {Function} OperationB
  54. * @returns {Function} Function set to transform an instance of `OperationA` by an instance of `OperationB`.
  55. */
  56. function getTransformation( OperationA, OperationB ) {
  57. const aGroup = transformations.get( OperationA );
  58. if ( aGroup && aGroup.has( OperationB ) ) {
  59. return aGroup.get( OperationB );
  60. }
  61. return noUpdateTransformation;
  62. }
  63. /**
  64. * A transformation function that only clones operation to transform, without changing it.
  65. *
  66. * @private
  67. * @param {module:engine/model/operation/operation~Operation} a Operation to transform.
  68. * @returns {Array.<module:engine/model/operation/operation~Operation>}
  69. */
  70. function noUpdateTransformation( a ) {
  71. return [ a ];
  72. }
  73. /**
  74. * Transforms operation `a` by operation `b`.
  75. *
  76. * @param {module:engine/model/operation/operation~Operation} a Operation to be transformed.
  77. * @param {module:engine/model/operation/operation~Operation} b Operation to transform by.
  78. * @param {module:engine/model/operation/transform~TransformationContext} context Transformation context for this transformation.
  79. * @returns {Array.<module:engine/model/operation/operation~Operation>} Transformation result.
  80. */
  81. export function transform( a, b, context = {} ) {
  82. const transformationFunction = getTransformation( a.constructor, b.constructor );
  83. try {
  84. a = a.clone();
  85. return transformationFunction( a, b, context );
  86. } catch ( e ) {
  87. log.error( 'Error during operation transformation!', e.message );
  88. log.error( 'Transformed operation', a );
  89. log.error( 'Operation transformed by', b );
  90. log.error( 'context.aIsStrong', context.aIsStrong );
  91. log.error( 'context.aWasUndone', context.aWasUndone );
  92. log.error( 'context.bWasUndone', context.bWasUndone );
  93. log.error( 'context.abRelation', context.abRelation );
  94. log.error( 'context.baRelation', context.baRelation );
  95. throw e;
  96. }
  97. }
  98. /**
  99. * Performs a transformation of two sets of operations - `operationsA` and `operationsB`. The transformation is two-way -
  100. * both transformed `operationsA` and transformed `operationsB` are returned.
  101. *
  102. * Note, that the first operation in each set should base on the same document state (
  103. * {@link module:engine/model/document~Document#version document version}).
  104. *
  105. * It is assumed that `operationsA` are "more important" during conflict resolution between two operations.
  106. *
  107. * New copies of both passed arrays and operations inside them are returned. Passed arguments are not altered.
  108. *
  109. * Base versions of the transformed operations sets are updated accordingly. For example, assume that base versions are `4`
  110. * and there are `3` operations in `operationsA` and `5` operations in `operationsB`. Then:
  111. *
  112. * * transformed `operationsA` will start from base version `9` (`4` base version + `5` operations B),
  113. * * transformed `operationsB` will start from base version `7` (`4` base version + `3` operations A).
  114. *
  115. * If no operation was broken into two during transformation, then both sets will end up with an operation that bases on version `11`:
  116. *
  117. * * transformed `operationsA` start from `9` and there are `3` of them, so the last will have `baseVersion` equal to `11`,
  118. * * transformed `operationsB` start from `7` and there are `5` of them, so the last will have `baseVersion` equal to `11`.
  119. *
  120. * @param {Array.<module:engine/model/operation/operation~Operation>} operationsA
  121. * @param {Array.<module:engine/model/operation/operation~Operation>} operationsB
  122. * @param {Object} options Additional transformation options.
  123. * @param {module:engine/model/document~Document|null} options.document Document which the operations change.
  124. * @param {Boolean} [options.useRelations=false] Whether during transformation relations should be used (used during undo for
  125. * better conflict resolution).
  126. * @param {Boolean} [options.padWithNoOps=false] Whether additional {@link module:engine/model/operation/nooperation~NoOperation}s
  127. * should be added to the transformation results to force the same last base version for both transformed sets (in case
  128. * if some operations got broken into multiple operations during transformation).
  129. * @returns {Object} Transformation result.
  130. * @returns {Array.<module:engine/model/operation/operation~Operation>} return.operationsA Transformed `operationsA`.
  131. * @returns {Array.<module:engine/model/operation/operation~Operation>} return.operationsB Transformed `operationsB`.
  132. */
  133. export function transformSets( operationsA, operationsB, options ) {
  134. // Create new arrays so the originally passed arguments are not changed.
  135. // No need to clone operations, they are cloned as they are transformed.
  136. operationsA = operationsA.slice();
  137. operationsB = operationsB.slice();
  138. // If one of sets is empty there is simply nothing to transform, so return sets as they are.
  139. if ( operationsA.length == 0 || operationsB.length == 0 ) {
  140. return { operationsA, operationsB };
  141. }
  142. //
  143. // Following is a description of transformation process:
  144. //
  145. // There are `operationsA` and `operationsB` to be transformed, both by both.
  146. //
  147. // So, suppose we have sets of two operations each: `operationsA` = `[ a1, a2 ]`, `operationsB` = `[ b1, b2 ]`.
  148. //
  149. // Remember, that we can only transform operations that base on the same context. We assert that `a1` and `b1` base on
  150. // the same context and we transform them. Then, we get `a1'` and `b1'`. `a2` bases on a context with `a1` -- `a2`
  151. // is an operation that followed `a1`. Similarly, `b2` bases on a context with `b1`.
  152. //
  153. // However, since `a1'` is a result of transformation by `b1`, `a1'` now also has a context with `b1`. This means that
  154. // we can safely transform `a1'` by `b2`. As we finish transforming `a1`, we also transformed all `operationsB`.
  155. // All `operationsB` also have context including `a1`. Now, we can properly transform `a2` by those operations.
  156. //
  157. // The transformation process can be visualized on a transformation diagram ("diamond diagram"):
  158. //
  159. // [the initial state]
  160. // [common for a1 and b1]
  161. //
  162. // *
  163. // / \
  164. // / \
  165. // b1 a1
  166. // / \
  167. // / \
  168. // * *
  169. // / \ / \
  170. // / \ / \
  171. // b2 a1' b1' a2
  172. // / \ / \
  173. // / \ / \
  174. // * * *
  175. // \ / \ /
  176. // \ / \ /
  177. // a1'' b2' a2' b1''
  178. // \ / \ /
  179. // \ / \ /
  180. // * *
  181. // \ /
  182. // \ /
  183. // a2'' b2''
  184. // \ /
  185. // \ /
  186. // *
  187. //
  188. // [the final state]
  189. //
  190. // The final state can be reached from the initial state by applying `a1`, `a2`, `b1''` and `b2''`, as well as by
  191. // applying `b1`, `b2`, `a1''`, `a2''`. Note how the operations get to a proper common state before each pair is
  192. // transformed.
  193. //
  194. // Another thing to consider is that an operation during transformation can be broken into multiple operations.
  195. // Suppose that `a1` * `b1` = `[ a11', a12' ]` (instead of `a1'` that we considered previously).
  196. //
  197. // In that case, we leave `a12'` for later and we continue transforming `a11'` until it is transformed by all `operationsB`
  198. // (in our case it is just `b2`). At this point, `b1` is transformed by "whole" `a1`, while `b2` is only transformed
  199. // by `a11'`. Similarly, `a12'` is only transformed by `b1`. This leads to a conclusion that we need to start transforming `a12'`
  200. // from the moment just after it was broken. So, `a12'` is transformed by `b2`. Now, "the whole" `a1` is transformed
  201. // by `operationsB`, while all `operationsB` are transformed by "the whole" `a1`. This means that we can continue with
  202. // following `operationsA` (in our case it is just `a2`).
  203. //
  204. // Of course, also `operationsB` can be broken. However, since we focus on transforming operation `a` to the end,
  205. // the only thing to do is to store both pieces of operation `b`, so that the next transformed operation `a` will
  206. // be transformed by both of them.
  207. //
  208. // *
  209. // / \
  210. // / \
  211. // / \
  212. // b1 a1
  213. // / \
  214. // / \
  215. // / \
  216. // * *
  217. // / \ / \
  218. // / a11' / \
  219. // / \ / \
  220. // b2 * b1' a2
  221. // / / \ / \
  222. // / / a12' / \
  223. // / / \ / \
  224. // * b2' * *
  225. // \ / / \ /
  226. // a11'' / b21'' \ /
  227. // \ / / \ /
  228. // * * a2' b1''
  229. // \ / \ \ /
  230. // a12'' b22''\ \ /
  231. // \ / \ \ /
  232. // * a2'' *
  233. // \ \ /
  234. // \ \ b21'''
  235. // \ \ /
  236. // a2''' *
  237. // \ /
  238. // \ b22'''
  239. // \ /
  240. // *
  241. //
  242. // Note, how `a1` is broken and transformed into `a11'` and `a12'`, while `b2'` got broken and transformed into `b21''` and `b22''`.
  243. //
  244. // Having all that on mind, here is an outline for the transformation process algorithm:
  245. //
  246. // 1. We have `operationsA` and `operationsB` array, which we dynamically update as the transformation process goes.
  247. //
  248. // 2. We take next (or first) operation from `operationsA` and check from which operation `b` we need to start transforming it.
  249. // All original `operationsA` are set to be transformed starting from the first operation `b`.
  250. //
  251. // 3. We take operations from `operationsB`, one by one, starting from the correct one, and transform operation `a`
  252. // by operation `b` (and vice versa). We update `operationsA` and `operationsB` by replacing the original operations
  253. // with the transformation results.
  254. //
  255. // 4. If operation is broken into multiple operations, we save all the new operations in the place of the
  256. // original operation.
  257. //
  258. // 5. Additionally, if operation `a` was broken, for the "new" operation, we remember from which operation `b` it should
  259. // be transformed by.
  260. //
  261. // 6. We continue transforming "current" operation `a` until it is transformed by all `operationsB`. Then, go to 2.
  262. // unless the last operation `a` was transformed.
  263. //
  264. // The actual implementation of the above algorithm is slightly different, as only one loop (while) is used.
  265. // The difference is that we have "current" `a` operation to transform and we store the index of the next `b` operation
  266. // to transform by. Each loop operates on two indexes then: index pointing to currently processed `a` operation and
  267. // index pointing to next `b` operation. Each loop is just one `a * b` + `b * a` transformation. After each loop
  268. // operation `b` index is updated. If all `b` operations were visited for the current `a` operation, we change
  269. // current `a` operation index to the next one.
  270. //
  271. // For each operation `a`, keeps information what is the index in `operationsB` from which the transformation should start.
  272. const nextTransformIndex = new WeakMap();
  273. // For all the original `operationsA`, set that they should be transformed starting from the first of `operationsB`.
  274. for ( const op of operationsA ) {
  275. nextTransformIndex.set( op, 0 );
  276. }
  277. // Additional data that is used for some postprocessing after the main transformation process is done.
  278. const data = {
  279. nextBaseVersionA: operationsA[ operationsA.length - 1 ].baseVersion + 1,
  280. nextBaseVersionB: operationsB[ operationsB.length - 1 ].baseVersion + 1,
  281. originalOperationsACount: operationsA.length,
  282. originalOperationsBCount: operationsB.length
  283. };
  284. const contextFactory = new ContextFactory( options.document, options.useRelations );
  285. contextFactory.setOriginalOperations( operationsA );
  286. contextFactory.setOriginalOperations( operationsB );
  287. // Index of currently transformed operation `a`.
  288. let i = 0;
  289. // While not all `operationsA` are transformed...
  290. while ( i < operationsA.length ) {
  291. // Get "current" operation `a`.
  292. const opA = operationsA[ i ];
  293. // For the "current" operation `a`, get the index of the next operation `b` to transform by.
  294. const indexB = nextTransformIndex.get( opA );
  295. // If operation `a` was already transformed by every operation `b`, change "current" operation `a` to the next one.
  296. if ( indexB == operationsB.length ) {
  297. i++;
  298. continue;
  299. }
  300. const opB = operationsB[ indexB ];
  301. // Transform `a` by `b` and `b` by `a`.
  302. const newOpsA = transform( opA, opB, contextFactory.getContext( opA, opB, true ) );
  303. const newOpsB = transform( opB, opA, contextFactory.getContext( opB, opA, false ) );
  304. // As a result we get one or more `newOpsA` and one or more `newOpsB` operations.
  305. // Update contextual information about operations.
  306. contextFactory.updateRelation( opA, opB );
  307. contextFactory.setOriginalOperations( newOpsA, opA );
  308. contextFactory.setOriginalOperations( newOpsB, opB );
  309. // For new `a` operations, update their index of the next operation `b` to transform them by.
  310. //
  311. // This is needed even if there was only one result (`a` was not broken) because that information is used
  312. // at the beginning of this loop every time.
  313. for ( const newOpA of newOpsA ) {
  314. // Acknowledge, that operation `b` also might be broken into multiple operations.
  315. //
  316. // This is why we raise `indexB` not just by 1. If `newOpsB` are multiple operations, they will be
  317. // spliced in the place of `opB`. So we need to change `transformBy` accordingly, so that an operation won't
  318. // be transformed by the same operation (part of it) again.
  319. nextTransformIndex.set( newOpA, indexB + newOpsB.length );
  320. }
  321. // Update `operationsA` and `operationsB` with the transformed versions.
  322. operationsA.splice( i, 1, ...newOpsA );
  323. operationsB.splice( indexB, 1, ...newOpsB );
  324. }
  325. if ( options.padWithNoOps ) {
  326. // If no-operations padding is enabled, count how many extra `a` and `b` operations were generated.
  327. const brokenOperationsACount = operationsA.length - data.originalOperationsACount;
  328. const brokenOperationsBCount = operationsB.length - data.originalOperationsBCount;
  329. // Then, if that number is not the same, pad `operationsA` or `operationsB` with correct number of no-ops so
  330. // that the base versions are equalled.
  331. //
  332. // Note that only one array will be updated, as only one of those subtractions can be greater than zero.
  333. padWithNoOps( operationsA, brokenOperationsBCount - brokenOperationsACount );
  334. padWithNoOps( operationsB, brokenOperationsACount - brokenOperationsBCount );
  335. }
  336. // Finally, update base versions of transformed operations.
  337. updateBaseVersions( operationsA, data.nextBaseVersionB );
  338. updateBaseVersions( operationsB, data.nextBaseVersionA );
  339. return { operationsA, operationsB };
  340. }
  341. // Gathers additional data about operations processed during transformation. Can be used to obtain contextual information
  342. // about two operations that are about to be transformed. This contextual information can be used for better conflict resolution.
  343. class ContextFactory {
  344. // Creates `ContextFactory` instance.
  345. //
  346. // @param {module:engine/model/document~Document} document Document which the operations change.
  347. // @param {Boolean} useRelations Whether during transformation relations should be used (used during undo for
  348. // better conflict resolution).
  349. constructor( document, useRelations ) {
  350. // `model.History` instance which information about undone operations will be taken from.
  351. this._history = document.history;
  352. // Whether additional context should be used.
  353. this._useRelations = useRelations;
  354. // For each operation that is created during transformation process, we keep a reference to the original operation
  355. // which it comes from. The original operation works as a kind of "identifier". Every contextual information
  356. // gathered during transformation that we want to save for given operation, is actually saved for the original operation.
  357. // This way no matter if operation `a` is cloned, then transformed, even breaks, we still have access to the previously
  358. // gathered data through original operation reference.
  359. this._originalOperations = new Map();
  360. // Relations is a double-map structure (maps in map) where for two operations we store how those operations were related
  361. // to each other. Those relations are evaluated during transformation process. For every transformated pair of operations
  362. // we keep relations between them.
  363. this._relations = new Map();
  364. }
  365. // Sets "original operation" for given operations.
  366. //
  367. // During transformation process, operations are cloned, then changed, then processed again, sometimes broken into two
  368. // or multiple operations. When gathering additional data it is important that all operations can be somehow linked
  369. // so a cloned and transformed "version" still kept track of the data assigned earlier to it.
  370. //
  371. // The original operation object will be used as such an universal linking id. Throughout the transformation process
  372. // all cloned operations will refer to "the original operation" when storing and reading additional data.
  373. //
  374. // If `takeFrom` is not set, each operation from `operations` array will be assigned itself as "the original operation".
  375. // This should be used as an initialization step.
  376. //
  377. // If `takeFrom` is set, each operation from `operations` will be assigned the same original operation as assigned
  378. // for `takeFrom` operation. This should be used to update original operations. It should be used in a way that
  379. // `operations` are the result of `takeFrom` transformation to ensure proper "original operation propagation".
  380. //
  381. // @param {Array.<module:engine/model/operation/operation~Operation>} operations
  382. // @param {module:engine/model/operation/operation~Operation|null} [takeFrom=null]
  383. setOriginalOperations( operations, takeFrom = null ) {
  384. const originalOperation = takeFrom ? this._originalOperations.get( takeFrom ) : null;
  385. for ( const operation of operations ) {
  386. this._originalOperations.set( operation, originalOperation || operation );
  387. }
  388. }
  389. // Saves a relation between operations `opA` and `opB`.
  390. //
  391. // Relations are then later used to help solve conflicts when operations are transformed.
  392. //
  393. // @param {module:engine/model/operation/operation~Operation} opA
  394. // @param {module:engine/model/operation/operation~Operation} opB
  395. updateRelation( opA, opB ) {
  396. // The use of relations is described in a bigger detail in transformation functions.
  397. //
  398. // In brief, this function, for specified pairs of operation types, checks how positions defined in those operations relate.
  399. // Then those relations are saved. For example, for two move operations, it is saved if one of those operations target
  400. // position is before the other operation source position. This kind of information gives contextual information when
  401. // transformation is used during undo. Similar checks are done for other pairs of operations.
  402. //
  403. switch ( opA.constructor ) {
  404. case MoveOperation: {
  405. switch ( opB.constructor ) {
  406. case MergeOperation: {
  407. if ( opA.targetPosition.isEqual( opB.sourcePosition ) || opB.movedRange.containsPosition( opA.targetPosition ) ) {
  408. this._setRelation( opA, opB, 'insertAtSource' );
  409. } else if ( opA.targetPosition.isEqual( opB.deletionPosition ) ) {
  410. this._setRelation( opA, opB, 'insertBetween' );
  411. } else if ( opA.targetPosition.isAfter( opB.sourcePosition ) ) {
  412. this._setRelation( opA, opB, 'moveTargetAfter' );
  413. }
  414. break;
  415. }
  416. case MoveOperation: {
  417. if ( opA.targetPosition.isEqual( opB.sourcePosition ) || opA.targetPosition.isBefore( opB.sourcePosition ) ) {
  418. this._setRelation( opA, opB, 'insertBefore' );
  419. } else {
  420. this._setRelation( opA, opB, 'insertAfter' );
  421. }
  422. break;
  423. }
  424. }
  425. break;
  426. }
  427. case SplitOperation: {
  428. switch ( opB.constructor ) {
  429. case MergeOperation: {
  430. if ( opA.splitPosition.isBefore( opB.sourcePosition ) ) {
  431. this._setRelation( opA, opB, 'splitBefore' );
  432. }
  433. break;
  434. }
  435. case MoveOperation: {
  436. if ( opA.splitPosition.isEqual( opB.sourcePosition ) || opA.splitPosition.isBefore( opB.sourcePosition ) ) {
  437. this._setRelation( opA, opB, 'splitBefore' );
  438. }
  439. break;
  440. }
  441. }
  442. break;
  443. }
  444. case MergeOperation: {
  445. switch ( opB.constructor ) {
  446. case MergeOperation: {
  447. if ( !opA.targetPosition.isEqual( opB.sourcePosition ) ) {
  448. this._setRelation( opA, opB, 'mergeTargetNotMoved' );
  449. }
  450. if ( opA.sourcePosition.isEqual( opB.sourcePosition ) ) {
  451. this._setRelation( opA, opB, 'mergeSameElement' );
  452. }
  453. break;
  454. }
  455. case SplitOperation: {
  456. if ( opA.sourcePosition.isEqual( opB.splitPosition ) ) {
  457. this._setRelation( opA, opB, 'splitAtSource' );
  458. }
  459. }
  460. }
  461. break;
  462. }
  463. case MarkerOperation: {
  464. const markerRange = opA.newRange;
  465. if ( !markerRange ) {
  466. return;
  467. }
  468. switch ( opB.constructor ) {
  469. case MoveOperation: {
  470. const movedRange = Range._createFromPositionAndShift( opB.sourcePosition, opB.howMany );
  471. const affectedLeft = movedRange.containsPosition( markerRange.start ) ||
  472. movedRange.start.isEqual( markerRange.start );
  473. const affectedRight = movedRange.containsPosition( markerRange.end ) ||
  474. movedRange.end.isEqual( markerRange.end );
  475. if ( ( affectedLeft || affectedRight ) && !movedRange.containsRange( markerRange ) ) {
  476. this._setRelation( opA, opB, {
  477. side: affectedLeft ? 'left' : 'right',
  478. offset: affectedLeft ? markerRange.start.offset : markerRange.end.offset
  479. } );
  480. }
  481. break;
  482. }
  483. case MergeOperation: {
  484. const wasInLeftElement = markerRange.start.isEqual( opB.targetPosition );
  485. const wasInRightElement = markerRange.end.isEqual( opB.sourcePosition );
  486. if ( wasInLeftElement || wasInRightElement ) {
  487. this._setRelation( opA, opB, { wasInLeftElement, wasInRightElement } );
  488. }
  489. break;
  490. }
  491. }
  492. break;
  493. }
  494. }
  495. }
  496. // Evaluates and returns contextual information about two given operations `opA` and `opB` which are about to be transformed.
  497. //
  498. // @param {module:engine/model/operation/operation~Operation} opA
  499. // @param {module:engine/model/operation/operation~Operation} opB
  500. // @returns {module:engine/model/operation/transform~TransformationContext}
  501. getContext( opA, opB, aIsStrong ) {
  502. return {
  503. aIsStrong,
  504. aWasUndone: this._wasUndone( opA ),
  505. bWasUndone: this._wasUndone( opB ),
  506. abRelation: this._useRelations ? this._getRelation( opA, opB ) : null,
  507. baRelation: this._useRelations ? this._getRelation( opB, opA ) : null
  508. };
  509. }
  510. // Returns whether given operation `op` has already been undone.
  511. //
  512. // Information whether an operation was undone gives more context when making a decision when two operations are in conflict.
  513. //
  514. // @param {module:engine/model/operation/operation~Operation} op
  515. // @returns {Boolean}
  516. _wasUndone( op ) {
  517. // For `op`, get its original operation. After all, if `op` is a clone (or even transformed clone) of another
  518. // operation, literally `op` couldn't be undone. It was just generated. If anything, it was the operation it origins
  519. // from which was undone. So get that original operation.
  520. const originalOp = this._originalOperations.get( op );
  521. // And check with the document if the original operation was undone.
  522. return originalOp.wasUndone || this._history.isUndoneOperation( originalOp );
  523. }
  524. // Returns a relation between `opA` and an operation which is undone by `opB`. This can be `String` value if a relation
  525. // was set earlier or `null` if there was no relation between those operations.
  526. //
  527. // This is a little tricky to understand, so let's compare it to `ContextFactory#_wasUndone`.
  528. //
  529. // When `wasUndone( opB )` is used, we check if the `opB` has already been undone. It is obvious, that the
  530. // undoing operation must happen after the undone operation. So, essentially, we have `opB`, we take document history,
  531. // we look forward in the future and ask if in that future `opB` was undone.
  532. //
  533. // Relations is a backward process to `wasUndone()`.
  534. //
  535. // Long story short - using relations is asking what happened in the past. Looking back. This time we have an undoing
  536. // operation `opB` which has undone some other operation. When there is a transformation `opA` x `opB` and there is
  537. // a conflict to solve and `opB` is an undoing operation, we can look back in the history and see what was a relation
  538. // between `opA` and the operation which `opB` undone. Basing on that relation from the past, we can now make
  539. // a better decision when resolving a conflict between two operations, because we know more about the context of
  540. // those two operations.
  541. //
  542. // This is why this function does not return a relation directly between `opA` and `opB` because we need to look
  543. // back to search for a meaningful contextual information.
  544. //
  545. // @param {module:engine/model/operation/operation~Operation} opA
  546. // @param {module:engine/model/operation/operation~Operation} opB
  547. // @returns {String|null}
  548. _getRelation( opA, opB ) {
  549. // Get the original operation. Similarly as in `wasUndone()` it is used as an universal identifier for stored data.
  550. const origB = this._originalOperations.get( opB );
  551. const undoneB = this._history.getUndoneOperation( origB );
  552. // If `opB` is not undoing any operation, there is no relation.
  553. if ( !undoneB ) {
  554. return null;
  555. }
  556. const origA = this._originalOperations.get( opA );
  557. const relationsA = this._relations.get( origA );
  558. // Get all relations for `opA`, and check if there is a relation with `opB`-undone-counterpart. If so, return it.
  559. if ( relationsA ) {
  560. return relationsA.get( undoneB ) || null;
  561. }
  562. return null;
  563. }
  564. // Helper function for `ContextFactory#updateRelations`.
  565. //
  566. // @private
  567. // @param {module:engine/model/operation/operation~Operation} opA
  568. // @param {module:engine/model/operation/operation~Operation} opB
  569. // @param {String} relation
  570. _setRelation( opA, opB, relation ) {
  571. // As always, setting is for original operations, not the clones/transformed operations.
  572. const origA = this._originalOperations.get( opA );
  573. const origB = this._originalOperations.get( opB );
  574. let relationsA = this._relations.get( origA );
  575. if ( !relationsA ) {
  576. relationsA = new Map();
  577. this._relations.set( origA, relationsA );
  578. }
  579. relationsA.set( origB, relation );
  580. }
  581. }
  582. /**
  583. * Holds additional contextual information about a transformed pair of operations (`a` and `b`). Those information
  584. * can be used for better conflict resolving.
  585. *
  586. * @typedef {Object} module:engine/model/operation/transform~TransformationContext
  587. *
  588. * @property {Boolean} aIsStrong Whether `a` is strong operation in this transformation, or weak.
  589. * @property {Boolean} aWasUndone Whether `a` operation was undone.
  590. * @property {Boolean} bWasUndone Whether `b` operation was undone.
  591. * @property {String|null} abRelation The relation between `a` operation and an operation undone by `b` operation.
  592. * @property {String|null} baRelation The relation between `b` operation and an operation undone by `a` operation.
  593. */
  594. /**
  595. * An utility function that updates {@link module:engine/model/operation/operation~Operation#baseVersion base versions}
  596. * of passed operations.
  597. *
  598. * The function simply sets `baseVersion` as a base version of the first passed operation and then increments it for
  599. * each following operation in `operations`.
  600. *
  601. * @private
  602. * @param {Array.<module:engine/model/operation/operation~Operation>} operations Operations to update.
  603. * @param {Number} baseVersion Base version to set for the first operation in `operations`.
  604. */
  605. function updateBaseVersions( operations, baseVersion ) {
  606. for ( const operation of operations ) {
  607. operation.baseVersion = baseVersion++;
  608. }
  609. }
  610. /**
  611. * Adds `howMany` instances of {@link module:engine/model/operation/nooperation~NoOperation} to `operations` set.
  612. *
  613. * @private
  614. * @param {Array.<module:engine/model/operation/operation~Operation>} operations
  615. * @param {Number} howMany
  616. */
  617. function padWithNoOps( operations, howMany ) {
  618. for ( let i = 0; i < howMany; i++ ) {
  619. operations.push( new NoOperation( 0 ) );
  620. }
  621. }
  622. // -----------------------
  623. setTransformation( AttributeOperation, AttributeOperation, ( a, b, context ) => {
  624. if ( a.key === b.key ) {
  625. // If operations attributes are in conflict, check if their ranges intersect and manage them properly.
  626. // First, we want to apply change to the part of a range that has not been changed by the other operation.
  627. const operations = a.range.getDifference( b.range ).map( range => {
  628. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, 0 );
  629. } );
  630. // Then we take care of the common part of ranges.
  631. const common = a.range.getIntersection( b.range );
  632. if ( common ) {
  633. // If this operation is more important, we also want to apply change to the part of the
  634. // original range that has already been changed by the other operation. Since that range
  635. // got changed we also have to update `oldValue`.
  636. if ( context.aIsStrong ) {
  637. operations.push( new AttributeOperation( common, b.key, b.newValue, a.newValue, 0 ) );
  638. }
  639. }
  640. if ( operations.length == 0 ) {
  641. return [ new NoOperation( 0 ) ];
  642. }
  643. return operations;
  644. } else {
  645. // If operations don't conflict, simply return an array containing just a clone of this operation.
  646. return [ a ];
  647. }
  648. } );
  649. setTransformation( AttributeOperation, InsertOperation, ( a, b ) => {
  650. // Case 1:
  651. //
  652. // The attribute operation range includes the position where nodes were inserted.
  653. // There are two possible scenarios: the inserted nodes were text and they should receive attributes or
  654. // the inserted nodes were elements and they should not receive attributes.
  655. //
  656. if ( a.range.start.hasSameParentAs( b.position ) && a.range.containsPosition( b.position ) ) {
  657. // If new nodes should not receive attributes, two separated ranges will be returned.
  658. // Otherwise, one expanded range will be returned.
  659. const range = a.range._getTransformedByInsertion( b.position, b.howMany, !b.shouldReceiveAttributes );
  660. const result = range.map( r => {
  661. return new AttributeOperation( r, a.key, a.oldValue, a.newValue, a.baseVersion );
  662. } );
  663. if ( b.shouldReceiveAttributes ) {
  664. // `AttributeOperation#range` includes some newly inserted text.
  665. // The operation should also change the attribute of that text. An example:
  666. //
  667. // Bold should be applied on the following range:
  668. // <p>Fo[zb]ar</p>
  669. //
  670. // In meantime, new text is typed:
  671. // <p>Fozxxbar</p>
  672. //
  673. // Bold should be applied also on the new text:
  674. // <p>Fo[zxxb]ar</p>
  675. // <p>Fo<$text bold="true">zxxb</$text>ar</p>
  676. //
  677. // There is a special case to consider here to consider.
  678. //
  679. // Consider setting an attribute with multiple possible values, for example `highlight`. The inserted text might
  680. // have already an attribute value applied and the `oldValue` property of the attribute operation might be wrong:
  681. //
  682. // Attribute `highlight="yellow"` should be applied on the following range:
  683. // <p>Fo[zb]ar<p>
  684. //
  685. // In meantime, character `x` with `highlight="red"` is typed:
  686. // <p>Fo[z<$text highlight="red">x</$text>b]ar</p>
  687. //
  688. // In this case we cannot simply apply operation changing the attribute value from `null` to `"yellow"` for the whole range
  689. // because that would lead to an exception (`oldValue` is incorrect for `x`).
  690. //
  691. // We also cannot break the original range as this would mess up a scenario when there are multiple following
  692. // insert operations, because then only the first inserted character is included in those ranges:
  693. // <p>Fo[z][x][b]ar</p> --> <p>Fo[z][x]x[b]ar</p> --> <p>Fo[z][x]xx[b]ar</p>
  694. //
  695. // So, the attribute range needs be expanded, no matter what attributes are set on the inserted nodes:
  696. //
  697. // <p>Fo[z<$text highlight="red">x</$text>b]ar</p> <--- Change from `null` to `yellow`, throwing an exception.
  698. //
  699. // But before that operation would be applied, we will add an additional attribute operation that will change
  700. // attributes on the inserted nodes in a way which would make the original operation correct:
  701. //
  702. // <p>Fo[z{<$text highlight="red">}x</$text>b]ar</p> <--- Change range `{}` from `red` to `null`.
  703. // <p>Fo[zxb]ar</p> <--- Now change from `null` to `yellow` is completely fine.
  704. //
  705. // Generate complementary attribute operation. Be sure to add it before the original operation.
  706. const op = _getComplementaryAttributeOperations( b, a.key, a.oldValue );
  707. if ( op ) {
  708. result.unshift( op );
  709. }
  710. }
  711. // If nodes should not receive new attribute, we are done here.
  712. return result;
  713. }
  714. // If insert operation is not expanding the attribute operation range, simply transform the range.
  715. a.range = a.range._getTransformedByInsertion( b.position, b.howMany, false )[ 0 ];
  716. return [ a ];
  717. } );
  718. /**
  719. * Helper function for `AttributeOperation` x `InsertOperation` (and reverse) transformation.
  720. *
  721. * For given `insertOperation` it checks the inserted node if it has an attribute `key` set to a value different
  722. * than `newValue`. If so, it generates an `AttributeOperation` which changes the value of `key` attribute to `newValue`.
  723. *
  724. * @private
  725. * @param {module:engine/model/operation/insertoperation~InsertOperation} insertOperation
  726. * @param {String} key
  727. * @param {*} newValue
  728. * @returns {module:engine/model/operation/attributeoperation~AttributeOperation|null}
  729. */
  730. function _getComplementaryAttributeOperations( insertOperation, key, newValue ) {
  731. const nodes = insertOperation.nodes;
  732. // At the beginning we store the attribute value from the first node.
  733. const insertValue = nodes.getNode( 0 ).getAttribute( key );
  734. if ( insertValue == newValue ) {
  735. return null;
  736. }
  737. const range = new Range( insertOperation.position, insertOperation.position.getShiftedBy( insertOperation.howMany ) );
  738. return new AttributeOperation( range, key, insertValue, newValue, 0 );
  739. }
  740. setTransformation( AttributeOperation, MergeOperation, ( a, b ) => {
  741. const ranges = [];
  742. // Case 1:
  743. //
  744. // Attribute change on the merged element. In this case, the merged element was moved to the graveyard.
  745. // An additional attribute operation that will change the (re)moved element needs to be generated.
  746. //
  747. if ( a.range.start.hasSameParentAs( b.deletionPosition ) ) {
  748. if ( a.range.containsPosition( b.deletionPosition ) || a.range.start.isEqual( b.deletionPosition ) ) {
  749. ranges.push( Range._createFromPositionAndShift( b.graveyardPosition, 1 ) );
  750. }
  751. }
  752. const range = a.range._getTransformedByMergeOperation( b );
  753. // Do not add empty (collapsed) ranges to the result. `range` may be collapsed if it contained only the merged element.
  754. if ( !range.isCollapsed ) {
  755. ranges.push( range );
  756. }
  757. // Create `AttributeOperation`s out of the ranges.
  758. return ranges.map( range => {
  759. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
  760. } );
  761. } );
  762. setTransformation( AttributeOperation, MoveOperation, ( a, b ) => {
  763. const ranges = _breakRangeByMoveOperation( a.range, b );
  764. // Create `AttributeOperation`s out of the ranges.
  765. return ranges.map( range => new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion ) );
  766. } );
  767. // Helper function for `AttributeOperation` x `MoveOperation` transformation.
  768. //
  769. // Takes the passed `range` and transforms it by move operation `moveOp` in a specific way. Only top-level nodes of `range`
  770. // are considered to be in the range. If move operation moves nodes deep from inside of the range, those nodes won't
  771. // be included in the result. In other words, top-level nodes of the ranges from the result are exactly the same as
  772. // top-level nodes of the original `range`.
  773. //
  774. // This is important for `AttributeOperation` because, for its range, it changes only the top-level nodes. So we need to
  775. // track only how those nodes have been affected by `MoveOperation`.
  776. //
  777. // @private
  778. // @param {module:engine/model/range~Range} range
  779. // @param {module:engine/model/operation/moveoperation~MoveOperation} moveOp
  780. // @returns {Array.<module:engine/model/range~Range>}
  781. function _breakRangeByMoveOperation( range, moveOp ) {
  782. const moveRange = Range._createFromPositionAndShift( moveOp.sourcePosition, moveOp.howMany );
  783. // We are transforming `range` (original range) by `moveRange` (range moved by move operation). As usual when it comes to
  784. // transforming a ranges, we may have a common part of the ranges and we may have a difference part (zero to two ranges).
  785. let common = null;
  786. let difference = [];
  787. // Let's compare the ranges.
  788. if ( moveRange.containsRange( range, true ) ) {
  789. // If the whole original range is moved, treat it whole as a common part. There's also no difference part.
  790. common = range;
  791. } else if ( range.start.hasSameParentAs( moveRange.start ) ) {
  792. // If the ranges are "on the same level" (in the same parent) then move operation may move exactly those nodes
  793. // that are changed by the attribute operation. In this case we get common part and difference part in the usual way.
  794. difference = range.getDifference( moveRange );
  795. common = range.getIntersection( moveRange );
  796. } else {
  797. // In any other situation we assume that original range is different than move range, that is that move operation
  798. // moves other nodes that attribute operation change. Even if the moved range is deep inside in the original range.
  799. //
  800. // Note that this is different than in `.getIntersection` (we would get a common part in that case) and different
  801. // than `.getDifference` (we would get two ranges).
  802. difference = [ range ];
  803. }
  804. const result = [];
  805. // The default behaviour of `_getTransformedByMove` might get wrong results for difference part, though, so
  806. // we do it by hand.
  807. for ( let diff of difference ) {
  808. // First, transform the range by removing moved nodes. Since this is a difference, this is safe, `null` won't be returned
  809. // as the range is different than the moved range.
  810. diff = diff._getTransformedByDeletion( moveOp.sourcePosition, moveOp.howMany );
  811. // Transform also `targetPosition`.
  812. const targetPosition = moveOp.getMovedRangeStart();
  813. // Spread the range only if moved nodes are inserted only between the top-level nodes of the `diff` range.
  814. const spread = diff.start.hasSameParentAs( targetPosition );
  815. // Transform by insertion of moved nodes.
  816. diff = diff._getTransformedByInsertion( targetPosition, moveOp.howMany, spread );
  817. result.push( ...diff );
  818. }
  819. // Common part can be simply transformed by the move operation. This is because move operation will not target to
  820. // that common part (the operation would have to target inside its own moved range).
  821. if ( common ) {
  822. result.push(
  823. common._getTransformedByMove( moveOp.sourcePosition, moveOp.targetPosition, moveOp.howMany, false )[ 0 ]
  824. );
  825. }
  826. return result;
  827. }
  828. setTransformation( AttributeOperation, SplitOperation, ( a, b ) => {
  829. // Case 1:
  830. //
  831. // Split node is the last node in `AttributeOperation#range`.
  832. // `AttributeOperation#range` needs to be expanded to include the new (split) node.
  833. //
  834. // Attribute `type` to be changed to `numbered` but the `listItem` is split.
  835. // <listItem type="bulleted">foobar</listItem>
  836. //
  837. // After split:
  838. // <listItem type="bulleted">foo</listItem><listItem type="bulleted">bar</listItem>
  839. //
  840. // After attribute change:
  841. // <listItem type="numbered">foo</listItem><listItem type="numbered">foo</listItem>
  842. //
  843. if ( a.range.end.isEqual( b.insertionPosition ) ) {
  844. if ( !b.graveyardPosition ) {
  845. a.range.end.offset++;
  846. }
  847. return [ a ];
  848. }
  849. // Case 2:
  850. //
  851. // Split position is inside `AttributeOperation#range`, at the same level, so the nodes to change are
  852. // not going to make a flat range.
  853. //
  854. // Content with range-to-change and split position:
  855. // <p>Fo[zb^a]r</p>
  856. //
  857. // After split:
  858. // <p>Fozb</p><p>ar</p>
  859. //
  860. // Make two separate ranges containing all nodes to change:
  861. // <p>Fo[zb]</p><p>[a]r</p>
  862. //
  863. if ( a.range.start.hasSameParentAs( b.splitPosition ) && a.range.containsPosition( b.splitPosition ) ) {
  864. const secondPart = a.clone();
  865. secondPart.range = new Range(
  866. b.moveTargetPosition.clone(),
  867. a.range.end._getCombined( b.splitPosition, b.moveTargetPosition )
  868. );
  869. a.range.end = b.splitPosition.clone();
  870. a.range.end.stickiness = 'toPrevious';
  871. return [ a, secondPart ];
  872. }
  873. // The default case.
  874. //
  875. a.range = a.range._getTransformedBySplitOperation( b );
  876. return [ a ];
  877. } );
  878. setTransformation( InsertOperation, AttributeOperation, ( a, b ) => {
  879. const result = [ a ];
  880. // Case 1:
  881. //
  882. // The attribute operation range includes the position where nodes were inserted.
  883. // There are two possible scenarios: the inserted nodes were text and they should receive attributes or
  884. // the inserted nodes were elements and they should not receive attributes.
  885. //
  886. // This is a mirror scenario to the one described in `AttributeOperation` x `InsertOperation` transformation,
  887. // although this case is a little less complicated. In this case we simply need to change attributes of the
  888. // inserted nodes and that's it.
  889. //
  890. if ( a.shouldReceiveAttributes && a.position.hasSameParentAs( b.range.start ) && b.range.containsPosition( a.position ) ) {
  891. const op = _getComplementaryAttributeOperations( a, b.key, b.newValue );
  892. if ( op ) {
  893. result.push( op );
  894. }
  895. }
  896. // The default case is: do nothing.
  897. // `AttributeOperation` does not change the model tree structure so `InsertOperation` does not need to be changed.
  898. //
  899. return result;
  900. } );
  901. setTransformation( InsertOperation, InsertOperation, ( a, b, context ) => {
  902. // Case 1:
  903. //
  904. // Two insert operations insert nodes at the same position. Since they are the same, it needs to be decided
  905. // what will be the order of inserted nodes. However, there is no additional information to help in that
  906. // decision. Also, when `b` will be transformed by `a`, the same order must be maintained.
  907. //
  908. // To achieve that, we will check if the operation is strong.
  909. // If it is, it won't get transformed. If it is not, it will be moved.
  910. //
  911. if ( a.position.isEqual( b.position ) && context.aIsStrong ) {
  912. return [ a ];
  913. }
  914. // The default case.
  915. //
  916. a.position = a.position._getTransformedByInsertOperation( b );
  917. return [ a ];
  918. } );
  919. setTransformation( InsertOperation, MoveOperation, ( a, b ) => {
  920. // The default case.
  921. //
  922. a.position = a.position._getTransformedByMoveOperation( b );
  923. return [ a ];
  924. } );
  925. setTransformation( InsertOperation, SplitOperation, ( a, b ) => {
  926. // The default case.
  927. //
  928. a.position = a.position._getTransformedBySplitOperation( b );
  929. return [ a ];
  930. } );
  931. setTransformation( InsertOperation, MergeOperation, ( a, b ) => {
  932. a.position = a.position._getTransformedByMergeOperation( b );
  933. return [ a ];
  934. } );
  935. // -----------------------
  936. setTransformation( MarkerOperation, InsertOperation, ( a, b ) => {
  937. if ( a.oldRange ) {
  938. a.oldRange = a.oldRange._getTransformedByInsertOperation( b )[ 0 ];
  939. }
  940. if ( a.newRange ) {
  941. a.newRange = a.newRange._getTransformedByInsertOperation( b )[ 0 ];
  942. }
  943. return [ a ];
  944. } );
  945. setTransformation( MarkerOperation, MarkerOperation, ( a, b, context ) => {
  946. if ( a.name == b.name ) {
  947. if ( context.aIsStrong ) {
  948. a.oldRange = b.newRange ? b.newRange.clone() : null;
  949. } else {
  950. return [ new NoOperation( 0 ) ];
  951. }
  952. }
  953. return [ a ];
  954. } );
  955. setTransformation( MarkerOperation, MergeOperation, ( a, b ) => {
  956. if ( a.oldRange ) {
  957. a.oldRange = a.oldRange._getTransformedByMergeOperation( b );
  958. }
  959. if ( a.newRange ) {
  960. a.newRange = a.newRange._getTransformedByMergeOperation( b );
  961. }
  962. return [ a ];
  963. } );
  964. setTransformation( MarkerOperation, MoveOperation, ( a, b, context ) => {
  965. if ( a.oldRange ) {
  966. a.oldRange = Range._createFromRanges( a.oldRange._getTransformedByMoveOperation( b ) );
  967. }
  968. if ( a.newRange ) {
  969. if ( context.abRelation ) {
  970. if ( context.abRelation.side == 'left' && b.targetPosition.isEqual( a.newRange.start ) ) {
  971. a.newRange.start.offset = context.abRelation.offset;
  972. a.newRange.end.offset += b.howMany;
  973. return [ a ];
  974. } else if ( context.abRelation.side == 'right' && b.targetPosition.isEqual( a.newRange.end ) ) {
  975. a.newRange.end.offset = context.abRelation.offset;
  976. return [ a ];
  977. }
  978. }
  979. a.newRange = Range._createFromRanges( a.newRange._getTransformedByMoveOperation( b ) );
  980. }
  981. return [ a ];
  982. } );
  983. setTransformation( MarkerOperation, SplitOperation, ( a, b, context ) => {
  984. if ( a.oldRange ) {
  985. a.oldRange = a.oldRange._getTransformedBySplitOperation( b );
  986. }
  987. if ( a.newRange ) {
  988. if ( context.abRelation ) {
  989. if ( a.newRange.start.isEqual( b.splitPosition ) && !context.abRelation.wasInLeftElement ) {
  990. a.newRange.start = Position._createAt( b.moveTargetPosition );
  991. }
  992. if ( a.newRange.end.isEqual( b.splitPosition ) && context.abRelation.wasInRightElement ) {
  993. a.newRange.end = Position._createAt( b.moveTargetPosition );
  994. }
  995. return [ a ];
  996. }
  997. a.newRange = a.newRange._getTransformedBySplitOperation( b );
  998. }
  999. return [ a ];
  1000. } );
  1001. // -----------------------
  1002. setTransformation( MergeOperation, InsertOperation, ( a, b ) => {
  1003. if ( a.sourcePosition.hasSameParentAs( b.position ) ) {
  1004. a.howMany += b.howMany;
  1005. }
  1006. a.sourcePosition = a.sourcePosition._getTransformedByInsertOperation( b );
  1007. a.targetPosition = a.targetPosition._getTransformedByInsertOperation( b );
  1008. return [ a ];
  1009. } );
  1010. setTransformation( MergeOperation, MergeOperation, ( a, b, context ) => {
  1011. // Case 1:
  1012. //
  1013. // Same merge operations.
  1014. //
  1015. // Both operations have same source and target positions. So the element already got merged and there is
  1016. // theoretically nothing to do.
  1017. //
  1018. if ( a.sourcePosition.isEqual( b.sourcePosition ) && a.targetPosition.isEqual( b.targetPosition ) ) {
  1019. // There are two ways that we can provide a do-nothing operation.
  1020. //
  1021. // First is simply a NoOperation instance. We will use it if `b` operation was not undone.
  1022. //
  1023. // Second is a merge operation that has the source operation in the merged element - in the graveyard -
  1024. // same target position and `howMany` equal to `0`. So it is basically merging an empty element from graveyard
  1025. // which is almost the same as NoOperation.
  1026. //
  1027. // This way the merge operation can be later transformed by split operation
  1028. // to provide correct undo. This will be used if `b` operation was undone (only then it is correct).
  1029. //
  1030. if ( !context.bWasUndone ) {
  1031. return [ new NoOperation( 0 ) ];
  1032. } else {
  1033. const path = b.graveyardPosition.path.slice();
  1034. path.push( 0 );
  1035. a.sourcePosition = new Position( b.graveyardPosition.root, path );
  1036. a.howMany = 0;
  1037. return [ a ];
  1038. }
  1039. }
  1040. // Case 2:
  1041. //
  1042. // Same merge source position but different target position.
  1043. //
  1044. // This can happen during collaboration. For example, if one client merged a paragraph to the previous paragraph
  1045. // and the other person removed that paragraph and merged the same paragraph to something before:
  1046. //
  1047. // Client A:
  1048. // <p>Foo</p><p>Bar</p><p>[]Xyz</p>
  1049. // <p>Foo</p><p>BarXyz</p>
  1050. //
  1051. // Client B:
  1052. // <p>Foo</p>[<p>Bar</p>]<p>Xyz</p>
  1053. // <p>Foo</p><p>[]Xyz</p>
  1054. // <p>FooXyz</p>
  1055. //
  1056. // In this case we need to decide where finally "Xyz" will land:
  1057. //
  1058. // <p>FooXyz</p> graveyard: <p>Bar</p>
  1059. // <p>Foo</p> graveyard: <p>BarXyz</p>
  1060. //
  1061. // Let's move it in a way so that a merge operation that does not target to graveyard is more important so that
  1062. // nodes does not end up in the graveyard. It makes sense. Both for Client A and for Client B "Xyz" finally did not
  1063. // end up in the graveyard (see above).
  1064. //
  1065. // If neither or both operations point to graveyard, then let `aIsStrong` decide.
  1066. //
  1067. if (
  1068. a.sourcePosition.isEqual( b.sourcePosition ) && !a.targetPosition.isEqual( b.targetPosition ) &&
  1069. !context.bWasUndone && context.abRelation != 'splitAtSource'
  1070. ) {
  1071. const aToGraveyard = a.targetPosition.root.rootName == '$graveyard';
  1072. const bToGraveyard = b.targetPosition.root.rootName == '$graveyard';
  1073. // If `aIsWeak` it means that `a` points to graveyard while `b` doesn't. Don't move nodes then.
  1074. const aIsWeak = aToGraveyard && !bToGraveyard;
  1075. // If `bIsWeak` it means that `b` points to graveyard while `a` doesn't. Force moving nodes then.
  1076. const bIsWeak = bToGraveyard && !aToGraveyard;
  1077. // Force move if `b` is weak or neither operation is weak but `a` is stronger through `context.aIsStrong`.
  1078. const forceMove = bIsWeak || ( !aIsWeak && context.aIsStrong );
  1079. if ( forceMove ) {
  1080. const sourcePosition = b.targetPosition._getTransformedByMergeOperation( b );
  1081. const targetPosition = a.targetPosition._getTransformedByMergeOperation( b );
  1082. return [ new MoveOperation( sourcePosition, a.howMany, targetPosition, 0 ) ];
  1083. } else {
  1084. return [ new NoOperation( 0 ) ];
  1085. }
  1086. }
  1087. // The default case.
  1088. //
  1089. if ( a.sourcePosition.hasSameParentAs( b.targetPosition ) ) {
  1090. a.howMany += b.howMany;
  1091. }
  1092. a.sourcePosition = a.sourcePosition._getTransformedByMergeOperation( b );
  1093. a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );
  1094. // Handle positions in graveyard.
  1095. // If graveyard positions are same and `a` operation is strong - do not transform.
  1096. if ( !a.graveyardPosition.isEqual( b.graveyardPosition ) || !context.aIsStrong ) {
  1097. a.graveyardPosition = a.graveyardPosition._getTransformedByMergeOperation( b );
  1098. }
  1099. return [ a ];
  1100. } );
  1101. setTransformation( MergeOperation, MoveOperation, ( a, b, context ) => {
  1102. // Case 1:
  1103. //
  1104. // The element to merge got removed.
  1105. //
  1106. // Merge operation does support merging elements which are not siblings. So it would not be a problem
  1107. // from technical point of view. However, if the element was removed, the intention of the user deleting it
  1108. // was to have it all deleted, together with its children. From user experience point of view, moving back the
  1109. // removed nodes might be unexpected. This means that in this scenario we will block the merging.
  1110. //
  1111. // The exception of this rule would be if the remove operation was later undone.
  1112. //
  1113. const removedRange = Range._createFromPositionAndShift( b.sourcePosition, b.howMany );
  1114. if ( b.type == 'remove' && !context.bWasUndone ) {
  1115. if ( a.deletionPosition.hasSameParentAs( b.sourcePosition ) && removedRange.containsPosition( a.sourcePosition ) ) {
  1116. return [ new NoOperation( 0 ) ];
  1117. }
  1118. }
  1119. // The default case.
  1120. //
  1121. if ( a.sourcePosition.hasSameParentAs( b.targetPosition ) ) {
  1122. a.howMany += b.howMany;
  1123. }
  1124. if ( a.sourcePosition.hasSameParentAs( b.sourcePosition ) ) {
  1125. a.howMany -= b.howMany;
  1126. }
  1127. a.sourcePosition = a.sourcePosition._getTransformedByMoveOperation( b );
  1128. a.targetPosition = a.targetPosition._getTransformedByMoveOperation( b );
  1129. // `MergeOperation` graveyard position is like `MoveOperation` target position. It is a position where element(s) will
  1130. // be moved. Like in other similar cases, we need to consider the scenario when those positions are same.
  1131. // Here, we will treat `MergeOperation` like it is always strong (see `InsertOperation` x `InsertOperation` for comparison).
  1132. // This means that we won't transform graveyard position if it is equal to move operation target position.
  1133. if ( !a.graveyardPosition.isEqual( b.targetPosition ) ) {
  1134. a.graveyardPosition = a.graveyardPosition._getTransformedByMoveOperation( b );
  1135. }
  1136. return [ a ];
  1137. } );
  1138. setTransformation( MergeOperation, SplitOperation, ( a, b, context ) => {
  1139. if ( b.graveyardPosition ) {
  1140. // If `b` operation defines graveyard position, a node from graveyard will be moved. This means that we need to
  1141. // transform `a.graveyardPosition` accordingly.
  1142. a.graveyardPosition = a.graveyardPosition._getTransformedByDeletion( b.graveyardPosition, 1 );
  1143. // This is a scenario foreseen in `MergeOperation` x `MergeOperation`, with two identical merge operations.
  1144. //
  1145. // So, there was `MergeOperation` x `MergeOperation` transformation earlier. Now, `a` is a merge operation which
  1146. // source position is in graveyard. Interestingly, split operation wants to use the node to be merged by `a`. This
  1147. // means that `b` is undoing that merge operation from earlier, which caused `a` to be in graveyard.
  1148. //
  1149. // If that's the case, at this point, we will only "fix" `a.howMany`. It was earlier set to `0` in
  1150. // `MergeOperation` x `MergeOperation` transformation. Later transformations in this function will change other
  1151. // properties.
  1152. //
  1153. if ( a.deletionPosition.isEqual( b.graveyardPosition ) ) {
  1154. a.howMany = b.howMany;
  1155. }
  1156. }
  1157. // Case 1:
  1158. //
  1159. // Merge operation moves nodes to the place where split happens.
  1160. // This is a classic situation when there are two paragraphs, and there is a split (enter) after the first
  1161. // paragraph and there is a merge (delete) at the beginning of the second paragraph:
  1162. //
  1163. // <p>Foo{}</p><p>[]Bar</p>.
  1164. //
  1165. // Split is after `Foo`, while merge is from `Bar` to the end of `Foo`.
  1166. //
  1167. // State after split:
  1168. // <p>Foo</p><p></p><p>Bar</p>
  1169. //
  1170. // Now, `Bar` should be merged to the new paragraph:
  1171. // <p>Foo</p><p>Bar</p>
  1172. //
  1173. // Instead of merging it to the original paragraph:
  1174. // <p>FooBar</p><p></p>
  1175. //
  1176. // This means that `targetPosition` needs to be transformed. This is the default case though.
  1177. // For example, if the split would be after `F`, `targetPosition` should also be transformed.
  1178. //
  1179. // There are three exceptions, though, when we want to keep `targetPosition` as it was.
  1180. //
  1181. // First exception is when the merge target position is inside an element (not at the end, as usual). This
  1182. // happens when the merge operation earlier was transformed by "the same" merge operation. If merge operation
  1183. // targets inside the element we want to keep the original target position (and not transform it) because
  1184. // we have additional context telling us that we want to merge to the original element. We can check if the
  1185. // merge operation points inside element by checking what is `SplitOperation#howMany`. Since merge target position
  1186. // is same as split position, if `howMany` is non-zero, it means that the merge target position is inside an element.
  1187. //
  1188. // Second exception is when the element to merge is in the graveyard and split operation uses it. In that case
  1189. // if target position would be transformed, the merge operation would target at the source position:
  1190. //
  1191. // root: <p>Foo</p> graveyard: <p></p>
  1192. //
  1193. // SplitOperation: root [ 0, 3 ] using graveyard [ 0 ] (howMany = 0)
  1194. // MergeOperation: graveyard [ 0, 0 ] -> root [ 0, 3 ] (howMany = 0)
  1195. //
  1196. // Since split operation moves the graveyard node back to the root, the merge operation source position changes.
  1197. // We would like to merge from the empty <p> to the "Foo" <p>:
  1198. //
  1199. // root: <p>Foo</p><p></p> graveyard:
  1200. //
  1201. // MergeOperation#sourcePosition = root [ 1, 0 ]
  1202. //
  1203. // If `targetPosition` is transformed, it would become root [ 1, 0 ] as well. It has to be kept as it was.
  1204. //
  1205. // Third exception is connected with relations. If this happens during undo and we have explicit information
  1206. // that target position has not been affected by the operation which is undone by this split then this split should
  1207. // not move the target position either.
  1208. //
  1209. if ( a.targetPosition.isEqual( b.splitPosition ) ) {
  1210. const mergeInside = b.howMany != 0;
  1211. const mergeSplittingElement = b.graveyardPosition && a.deletionPosition.isEqual( b.graveyardPosition );
  1212. if ( mergeInside || mergeSplittingElement || context.abRelation == 'mergeTargetNotMoved' ) {
  1213. a.sourcePosition = a.sourcePosition._getTransformedBySplitOperation( b );
  1214. return [ a ];
  1215. }
  1216. }
  1217. // Case 2:
  1218. //
  1219. // Merge source is at the same position as split position. This sometimes happen during undo. This merge operation
  1220. // might have been earlier transformed by a merge operation which both merged the same element. See case in
  1221. // `MergeOperation` x `MergeOperation` transformation. In that case, if the merge operation has been undone, the special
  1222. // case is not applied.
  1223. //
  1224. // In this scenario the merge operation is now transformed by the split which has undone the previous merge operation.
  1225. // So now we are fixing situation which was skipped in `MergeOperation` x `MergeOperation` case.
  1226. //
  1227. if ( a.sourcePosition.isEqual( b.splitPosition ) && ( context.abRelation == 'mergeSameElement' || a.sourcePosition.offset > 0 ) ) {
  1228. a.sourcePosition = b.moveTargetPosition.clone();
  1229. a.targetPosition = a.targetPosition._getTransformedBySplitOperation( b );
  1230. return [ a ];
  1231. }
  1232. // The default case.
  1233. //
  1234. if ( a.sourcePosition.hasSameParentAs( b.splitPosition ) ) {
  1235. a.howMany = b.splitPosition.offset;
  1236. }
  1237. a.sourcePosition = a.sourcePosition._getTransformedBySplitOperation( b );
  1238. a.targetPosition = a.targetPosition._getTransformedBySplitOperation( b );
  1239. return [ a ];
  1240. } );
  1241. // -----------------------
  1242. setTransformation( MoveOperation, InsertOperation, ( a, b ) => {
  1243. const moveRange = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );
  1244. const transformed = moveRange._getTransformedByInsertOperation( b, false )[ 0 ];
  1245. a.sourcePosition = transformed.start;
  1246. a.howMany = transformed.end.offset - transformed.start.offset;
  1247. // See `InsertOperation` x `MoveOperation` transformation for details on this case.
  1248. //
  1249. // In summary, both operations point to the same place, so the order of nodes needs to be decided.
  1250. // `MoveOperation` is considered weaker, so it is always transformed, unless there was a certain relation
  1251. // between operations.
  1252. //
  1253. if ( !a.targetPosition.isEqual( b.position ) ) {
  1254. a.targetPosition = a.targetPosition._getTransformedByInsertOperation( b );
  1255. }
  1256. return [ a ];
  1257. } );
  1258. setTransformation( MoveOperation, MoveOperation, ( a, b, context ) => {
  1259. //
  1260. // Setting and evaluating some variables that will be used in special cases and default algorithm.
  1261. //
  1262. // Create ranges from `MoveOperations` properties.
  1263. const rangeA = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );
  1264. const rangeB = Range._createFromPositionAndShift( b.sourcePosition, b.howMany );
  1265. // Assign `context.aIsStrong` to a different variable, because the value may change during execution of
  1266. // this algorithm and we do not want to override original `context.aIsStrong` that will be used in later transformations.
  1267. let aIsStrong = context.aIsStrong;
  1268. // This will be used to decide the order of nodes if both operations target at the same position.
  1269. // By default, use strong/weak operation mechanism.
  1270. let insertBefore = !context.aIsStrong;
  1271. // If the relation is set, then use it to decide nodes order.
  1272. if ( context.abRelation == 'insertBefore' || context.baRelation == 'insertAfter' ) {
  1273. insertBefore = true;
  1274. } else if ( context.abRelation == 'insertAfter' || context.baRelation == 'insertBefore' ) {
  1275. insertBefore = false;
  1276. }
  1277. // `a.targetPosition` could be affected by the `b` operation. We will transform it.
  1278. let newTargetPosition;
  1279. if ( a.targetPosition.isEqual( b.targetPosition ) && insertBefore ) {
  1280. newTargetPosition = a.targetPosition._getTransformedByDeletion(
  1281. b.sourcePosition,
  1282. b.howMany
  1283. );
  1284. } else {
  1285. newTargetPosition = a.targetPosition._getTransformedByMove(
  1286. b.sourcePosition,
  1287. b.targetPosition,
  1288. b.howMany
  1289. );
  1290. }
  1291. //
  1292. // Special case #1 + mirror.
  1293. //
  1294. // Special case when both move operations' target positions are inside nodes that are
  1295. // being moved by the other move operation. So in other words, we move ranges into inside of each other.
  1296. // This case can't be solved reasonably (on the other hand, it should not happen often).
  1297. if ( _moveTargetIntoMovedRange( a, b ) && _moveTargetIntoMovedRange( b, a ) ) {
  1298. // Instead of transforming operation, we return a reverse of the operation that we transform by.
  1299. // So when the results of this "transformation" will be applied, `b` MoveOperation will get reversed.
  1300. return [ b.getReversed() ];
  1301. }
  1302. //
  1303. // End of special case #1.
  1304. //
  1305. //
  1306. // Special case #2.
  1307. //
  1308. // Check if `b` operation targets inside `rangeA`.
  1309. const bTargetsToA = rangeA.containsPosition( b.targetPosition );
  1310. // If `b` targets to `rangeA` and `rangeA` contains `rangeB`, `b` operation has no influence on `a` operation.
  1311. // You might say that operation `b` is captured inside operation `a`.
  1312. if ( bTargetsToA && rangeA.containsRange( rangeB, true ) ) {
  1313. // There is a mini-special case here, where `rangeB` is on other level than `rangeA`. That's why
  1314. // we need to transform `a` operation anyway.
  1315. rangeA.start = rangeA.start._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  1316. rangeA.end = rangeA.end._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  1317. return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition );
  1318. }
  1319. //
  1320. // Special case #2 mirror.
  1321. //
  1322. const aTargetsToB = rangeB.containsPosition( a.targetPosition );
  1323. if ( aTargetsToB && rangeB.containsRange( rangeA, true ) ) {
  1324. // `a` operation is "moved together" with `b` operation.
  1325. // Here, just move `rangeA` "inside" `rangeB`.
  1326. rangeA.start = rangeA.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  1327. rangeA.end = rangeA.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  1328. return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition );
  1329. }
  1330. //
  1331. // End of special case #2.
  1332. //
  1333. //
  1334. // Special case #3 + mirror.
  1335. //
  1336. // `rangeA` has a node which is an ancestor of `rangeB`. In other words, `rangeB` is inside `rangeA`
  1337. // but not on the same tree level. In such case ranges have common part but we have to treat it
  1338. // differently, because in such case those ranges are not really conflicting and should be treated like
  1339. // two separate ranges. Also we have to discard two difference parts.
  1340. const aCompB = compareArrays( a.sourcePosition.getParentPath(), b.sourcePosition.getParentPath() );
  1341. if ( aCompB == 'prefix' || aCompB == 'extension' ) {
  1342. // Transform `rangeA` by `b` operation and make operation out of it, and that's all.
  1343. // Note that this is a simplified version of default case, but here we treat the common part (whole `rangeA`)
  1344. // like a one difference part.
  1345. rangeA.start = rangeA.start._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  1346. rangeA.end = rangeA.end._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  1347. return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition );
  1348. }
  1349. //
  1350. // End of special case #3.
  1351. //
  1352. //
  1353. // Default case - ranges are on the same level or are not connected with each other.
  1354. //
  1355. // Modifier for default case.
  1356. // Modifies `aIsStrong` flag in certain conditions.
  1357. //
  1358. // If only one of operations is a remove operation, we force remove operation to be the "stronger" one
  1359. // to provide more expected results.
  1360. if ( a.type == 'remove' && b.type != 'remove' && !context.aWasUndone ) {
  1361. aIsStrong = true;
  1362. } else if ( a.type != 'remove' && b.type == 'remove' && !context.bWasUndone ) {
  1363. aIsStrong = false;
  1364. }
  1365. // Handle operation's source ranges - check how `rangeA` is affected by `b` operation.
  1366. // This will aggregate transformed ranges.
  1367. const ranges = [];
  1368. // Get the "difference part" of `a` operation source range.
  1369. // This is an array with one or two ranges. Two ranges if `rangeB` is inside `rangeA`.
  1370. const difference = rangeA.getDifference( rangeB );
  1371. for ( const range of difference ) {
  1372. // Transform those ranges by `b` operation. For example if `b` moved range from before those ranges, fix those ranges.
  1373. range.start = range.start._getTransformedByDeletion( b.sourcePosition, b.howMany );
  1374. range.end = range.end._getTransformedByDeletion( b.sourcePosition, b.howMany );
  1375. // If `b` operation targets into `rangeA` on the same level, spread `rangeA` into two ranges.
  1376. const shouldSpread = compareArrays( range.start.getParentPath(), b.getMovedRangeStart().getParentPath() ) == 'same';
  1377. const newRanges = range._getTransformedByInsertion( b.getMovedRangeStart(), b.howMany, shouldSpread );
  1378. ranges.push( ...newRanges );
  1379. }
  1380. // Then, we have to manage the "common part" of both move ranges.
  1381. const common = rangeA.getIntersection( rangeB );
  1382. if ( common !== null && aIsStrong ) {
  1383. // Calculate the new position of that part of original range.
  1384. common.start = common.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  1385. common.end = common.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  1386. // Take care of proper range order.
  1387. //
  1388. // Put `common` at appropriate place. Keep in mind that we are interested in original order.
  1389. // Basically there are only three cases: there is zero, one or two difference ranges.
  1390. //
  1391. // If there is zero difference ranges, just push `common` in the array.
  1392. if ( ranges.length === 0 ) {
  1393. ranges.push( common );
  1394. }
  1395. // If there is one difference range, we need to check whether common part was before it or after it.
  1396. else if ( ranges.length == 1 ) {
  1397. if ( rangeB.start.isBefore( rangeA.start ) || rangeB.start.isEqual( rangeA.start ) ) {
  1398. ranges.unshift( common );
  1399. } else {
  1400. ranges.push( common );
  1401. }
  1402. }
  1403. // If there are more ranges (which means two), put common part between them. This is the only scenario
  1404. // where there could be two difference ranges so we don't have to make any comparisons.
  1405. else {
  1406. ranges.splice( 1, 0, common );
  1407. }
  1408. }
  1409. if ( ranges.length === 0 ) {
  1410. // If there are no "source ranges", nothing should be changed.
  1411. // Note that this can happen only if `aIsStrong == false` and `rangeA.isEqual( rangeB )`.
  1412. return [ new NoOperation( a.baseVersion ) ];
  1413. }
  1414. return _makeMoveOperationsFromRanges( ranges, newTargetPosition );
  1415. } );
  1416. setTransformation( MoveOperation, SplitOperation, ( a, b, context ) => {
  1417. let newTargetPosition = a.targetPosition.clone();
  1418. // Do not transform if target position is same as split insertion position and this split comes from undo.
  1419. // This should be done on relations but it is too much work for now as it would require relations working in collaboration.
  1420. // We need to make a decision how we will resolve such conflict and this is less harmful way.
  1421. if ( !a.targetPosition.isEqual( b.insertionPosition ) || !b.graveyardPosition || context.abRelation == 'moveTargetAfter' ) {
  1422. newTargetPosition = a.targetPosition._getTransformedBySplitOperation( b );
  1423. }
  1424. // Case 1:
  1425. //
  1426. // Last element in the moved range got split.
  1427. //
  1428. // In this case the default range transformation will not work correctly as the element created by
  1429. // split operation would be outside the range. The range to move needs to be fixed manually.
  1430. //
  1431. const moveRange = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );
  1432. if ( moveRange.end.isEqual( b.insertionPosition ) ) {
  1433. // Do it only if this is a "natural" split, not a one that comes from undo.
  1434. // If this is undo split, only `targetPosition` needs to be changed (if the move is a remove).
  1435. if ( !b.graveyardPosition ) {
  1436. a.howMany++;
  1437. }
  1438. a.targetPosition = newTargetPosition;
  1439. return [ a ];
  1440. }
  1441. // Case 2:
  1442. //
  1443. // Split happened between the moved nodes. In this case two ranges to move need to be generated.
  1444. //
  1445. // Characters `ozba` are moved to the end of paragraph `Xyz` but split happened.
  1446. // <p>F[oz|ba]r</p><p>Xyz</p>
  1447. //
  1448. // After split:
  1449. // <p>F[oz</p><p>ba]r</p><p>Xyz</p>
  1450. //
  1451. // Correct ranges:
  1452. // <p>F[oz]</p><p>[ba]r</p><p>Xyz</p>
  1453. //
  1454. // After move:
  1455. // <p>F</p><p>r</p><p>Xyzozba</p>
  1456. //
  1457. if ( moveRange.start.hasSameParentAs( b.splitPosition ) && moveRange.containsPosition( b.splitPosition ) ) {
  1458. let rightRange = new Range( b.splitPosition, moveRange.end );
  1459. rightRange = rightRange._getTransformedBySplitOperation( b );
  1460. const ranges = [
  1461. new Range( moveRange.start, b.splitPosition ),
  1462. rightRange
  1463. ];
  1464. return _makeMoveOperationsFromRanges( ranges, newTargetPosition );
  1465. }
  1466. // Case 3:
  1467. //
  1468. // Move operation targets at the split position. We need to decide if the nodes should be inserted
  1469. // at the end of the split element or at the beginning of the new element.
  1470. //
  1471. if ( a.targetPosition.isEqual( b.splitPosition ) && context.abRelation == 'insertAtSource' ) {
  1472. newTargetPosition = b.moveTargetPosition;
  1473. }
  1474. // Case 4:
  1475. //
  1476. // Move operation targets just after the split element. We need to decide if the nodes should be inserted
  1477. // between two parts of split element, or after the new element.
  1478. //
  1479. // Split at `|`, while move operation moves `<p>Xyz</p>` and targets at `^`:
  1480. // <p>Foo|bar</p>^<p>baz</p>
  1481. // <p>Foo</p>^<p>bar</p><p>baz</p> or <p>Foo</p><p>bar</p>^<p>baz</p>?
  1482. //
  1483. // If there is no contextual information between operations (for example, they come from collaborative
  1484. // editing), we don't want to put some unrelated content (move) between parts of related content (split parts).
  1485. // However, if the split is from undo, in the past, the moved content might be targeting between the
  1486. // split parts, meaning that was exactly user's intention:
  1487. //
  1488. // <p>Foo</p>^<p>bar</p> <--- original situation, in "past".
  1489. // <p>Foobar</p>^ <--- after merge target position is transformed.
  1490. // <p>Foo|bar</p>^ <--- then the merge is undone, and split happens, which leads us to current situation.
  1491. //
  1492. // In this case it is pretty clear that the intention was to put new paragraph between those nodes,
  1493. // so we need to transform accordingly. We can detect this scenario thanks to relations.
  1494. //
  1495. if ( a.targetPosition.isEqual( b.insertionPosition ) && context.abRelation == 'insertBetween' ) {
  1496. newTargetPosition = a.targetPosition;
  1497. }
  1498. // The default case.
  1499. //
  1500. const transformed = moveRange._getTransformedBySplitOperation( b );
  1501. const ranges = [ transformed ];
  1502. // Case 5:
  1503. //
  1504. // Moved range contains graveyard element used by split operation. Add extra move operation to the result.
  1505. //
  1506. if ( b.graveyardPosition ) {
  1507. const movesGraveyardElement = moveRange.start.isEqual( b.graveyardPosition ) || moveRange.containsPosition( b.graveyardPosition );
  1508. if ( a.howMany > 1 && movesGraveyardElement ) {
  1509. ranges.push( Range._createFromPositionAndShift( b.insertionPosition, 1 ) );
  1510. }
  1511. }
  1512. return _makeMoveOperationsFromRanges( ranges, newTargetPosition );
  1513. } );
  1514. setTransformation( MoveOperation, MergeOperation, ( a, b, context ) => {
  1515. const movedRange = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );
  1516. if ( b.deletionPosition.hasSameParentAs( a.sourcePosition ) && movedRange.containsPosition( b.sourcePosition ) ) {
  1517. if ( a.type == 'remove' ) {
  1518. // Case 1:
  1519. //
  1520. // The element to remove got merged.
  1521. //
  1522. // Merge operation does support merging elements which are not siblings. So it would not be a problem
  1523. // from technical point of view. However, if the element was removed, the intention of the user
  1524. // deleting it was to have it all deleted. From user experience point of view, moving back the
  1525. // removed nodes might be unexpected. This means that in this scenario we will reverse merging and remove the element.
  1526. //
  1527. if ( !context.aWasUndone ) {
  1528. const results = [];
  1529. let gyMoveSource = b.graveyardPosition.clone();
  1530. let splitNodesMoveSource = b.targetPosition.clone();
  1531. if ( a.howMany > 1 ) {
  1532. results.push( new MoveOperation( a.sourcePosition, a.howMany - 1, a.targetPosition, 0 ) );
  1533. gyMoveSource = gyMoveSource._getTransformedByInsertion( a.targetPosition, a.howMany - 1 );
  1534. splitNodesMoveSource = splitNodesMoveSource._getTransformedByMove( a.sourcePosition, a.targetPosition, a.howMany - 1 );
  1535. }
  1536. const gyMoveTarget = b.deletionPosition._getCombined( a.sourcePosition, a.targetPosition );
  1537. const gyMove = new MoveOperation( gyMoveSource, 1, gyMoveTarget, 0 );
  1538. const targetPositionPath = gyMove.getMovedRangeStart().path.slice();
  1539. targetPositionPath.push( 0 );
  1540. const splitNodesMoveTarget = new Position( gyMove.targetPosition.root, targetPositionPath );
  1541. splitNodesMoveSource = splitNodesMoveSource._getTransformedByMove( gyMoveSource, gyMoveTarget, 1 );
  1542. const splitNodesMove = new MoveOperation( splitNodesMoveSource, b.howMany, splitNodesMoveTarget, 0 );
  1543. results.push( gyMove );
  1544. results.push( splitNodesMove );
  1545. return results;
  1546. }
  1547. } else {
  1548. // Case 2:
  1549. //
  1550. // The element to move got merged and it was the only element to move.
  1551. // In this case just don't do anything, leave the node in the graveyard. Without special case
  1552. // it would be a move operation that moves 0 nodes, so maybe it is better just to return no-op.
  1553. //
  1554. if ( a.howMany == 1 ) {
  1555. if ( !context.bWasUndone ) {
  1556. return [ new NoOperation( 0 ) ];
  1557. } else {
  1558. a.sourcePosition = b.graveyardPosition.clone();
  1559. a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );
  1560. return [ a ];
  1561. }
  1562. }
  1563. }
  1564. }
  1565. // The default case.
  1566. //
  1567. const moveRange = Range._createFromPositionAndShift( a.sourcePosition, a.howMany );
  1568. const transformed = moveRange._getTransformedByMergeOperation( b );
  1569. a.sourcePosition = transformed.start;
  1570. a.howMany = transformed.end.offset - transformed.start.offset;
  1571. a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );
  1572. return [ a ];
  1573. } );
  1574. // -----------------------
  1575. setTransformation( RenameOperation, InsertOperation, ( a, b ) => {
  1576. a.position = a.position._getTransformedByInsertOperation( b );
  1577. return [ a ];
  1578. } );
  1579. setTransformation( RenameOperation, MergeOperation, ( a, b ) => {
  1580. // Case 1:
  1581. //
  1582. // Element to rename got merged, so it was moved to `b.graveyardPosition`.
  1583. //
  1584. if ( a.position.isEqual( b.deletionPosition ) ) {
  1585. a.position = b.graveyardPosition.clone();
  1586. a.position.stickiness = 'toNext';
  1587. return [ a ];
  1588. }
  1589. a.position = a.position._getTransformedByMergeOperation( b );
  1590. return [ a ];
  1591. } );
  1592. setTransformation( RenameOperation, MoveOperation, ( a, b ) => {
  1593. a.position = a.position._getTransformedByMoveOperation( b );
  1594. return [ a ];
  1595. } );
  1596. setTransformation( RenameOperation, RenameOperation, ( a, b, context ) => {
  1597. if ( a.position.isEqual( b.position ) ) {
  1598. if ( context.aIsStrong ) {
  1599. a.oldName = b.newName;
  1600. } else {
  1601. return [ new NoOperation( 0 ) ];
  1602. }
  1603. }
  1604. return [ a ];
  1605. } );
  1606. setTransformation( RenameOperation, SplitOperation, ( a, b ) => {
  1607. // Case 1:
  1608. //
  1609. // The element to rename has been split. In this case, the new element should be also renamed.
  1610. //
  1611. // User decides to change the paragraph to a list item:
  1612. // <paragraph>Foobar</paragraph>
  1613. //
  1614. // However, in meantime, split happens:
  1615. // <paragraph>Foo</paragraph><paragraph>bar</paragraph>
  1616. //
  1617. // As a result, rename both elements:
  1618. // <listItem>Foo</listItem><listItem>bar</listItem>
  1619. //
  1620. const renamePath = a.position.path;
  1621. const splitPath = b.splitPosition.getParentPath();
  1622. if ( compareArrays( renamePath, splitPath ) == 'same' && !b.graveyardPosition ) {
  1623. const extraRename = new RenameOperation( a.position.getShiftedBy( 1 ), a.oldName, a.newName, 0 );
  1624. return [ a, extraRename ];
  1625. }
  1626. // The default case.
  1627. //
  1628. a.position = a.position._getTransformedBySplitOperation( b );
  1629. return [ a ];
  1630. } );
  1631. // -----------------------
  1632. setTransformation( RootAttributeOperation, RootAttributeOperation, ( a, b, context ) => {
  1633. if ( a.root === b.root && a.key === b.key ) {
  1634. if ( !context.aIsStrong || a.newValue === b.newValue ) {
  1635. return [ new NoOperation( 0 ) ];
  1636. } else {
  1637. a.oldValue = b.newValue;
  1638. }
  1639. }
  1640. return [ a ];
  1641. } );
  1642. // -----------------------
  1643. setTransformation( SplitOperation, InsertOperation, ( a, b ) => {
  1644. // The default case.
  1645. //
  1646. if ( a.splitPosition.hasSameParentAs( b.position ) && a.splitPosition.offset < b.position.offset ) {
  1647. a.howMany += b.howMany;
  1648. }
  1649. a.splitPosition = a.splitPosition._getTransformedByInsertOperation( b );
  1650. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1651. return [ a ];
  1652. } );
  1653. setTransformation( SplitOperation, MergeOperation, ( a, b, context ) => {
  1654. // Case 1:
  1655. //
  1656. // Split element got merged. If two different elements were merged, clients will have different content.
  1657. //
  1658. // Example. Merge at `{}`, split at `[]`:
  1659. // <heading>Foo</heading>{}<paragraph>B[]ar</paragraph>
  1660. //
  1661. // On merge side it will look like this:
  1662. // <heading>FooB[]ar</heading>
  1663. // <heading>FooB</heading><heading>ar</heading>
  1664. //
  1665. // On split side it will look like this:
  1666. // <heading>Foo</heading>{}<paragraph>B</paragraph><paragraph>ar</paragraph>
  1667. // <heading>FooB</heading><paragraph>ar</paragraph>
  1668. //
  1669. // Clearly, the second element is different for both clients.
  1670. //
  1671. // We could use the removed merge element from graveyard as a split element but then clients would have a different
  1672. // model state (in graveyard), because the split side client would still have an element in graveyard (removed by merge).
  1673. //
  1674. // To overcome this, in `SplitOperation` x `MergeOperation` transformation we will add additional `SplitOperation`
  1675. // in the graveyard, which will actually clone the merged-and-deleted element. Then, that cloned element will be
  1676. // used for splitting. Example below.
  1677. //
  1678. // Original state:
  1679. // <heading>Foo</heading>{}<paragraph>B[]ar</paragraph>
  1680. //
  1681. // Merge side client:
  1682. //
  1683. // After merge:
  1684. // <heading>FooB[]ar</heading> graveyard: <paragraph></paragraph>
  1685. //
  1686. // Extra split:
  1687. // <heading>FooB[]ar</heading> graveyard: <paragraph></paragraph><paragraph></paragraph>
  1688. //
  1689. // Use the "cloned" element from graveyard:
  1690. // <heading>FooB</heading><paragraph>ar</paragraph> graveyard: <paragraph></paragraph>
  1691. //
  1692. // Split side client:
  1693. //
  1694. // After split:
  1695. // <heading>Foo</heading>{}<paragraph>B</paragraph><paragraph>ar</paragraph>
  1696. //
  1697. // After merge:
  1698. // <heading>FooB</heading><paragraph>ar</paragraph> graveyard: <paragraph></paragraph>
  1699. //
  1700. // This special case scenario only applies if the original split operation clones the split element.
  1701. // If the original split operation has `graveyardPosition` set, it all doesn't have sense because split operation
  1702. // knows exactly which element it should use. So there would be no original problem with different contents.
  1703. //
  1704. // Additionally, the special case applies only if the merge wasn't already undone.
  1705. //
  1706. if ( !a.graveyardPosition && !context.bWasUndone && a.splitPosition.hasSameParentAs( b.sourcePosition ) ) {
  1707. const splitPath = b.graveyardPosition.path.slice();
  1708. splitPath.push( 0 );
  1709. const splitPosition = new Position( b.graveyardPosition.root, splitPath );
  1710. const insertionPosition = SplitOperation.getInsertionPosition( new Position( b.graveyardPosition.root, splitPath ) );
  1711. const additionalSplit = new SplitOperation( splitPosition, 0, null, 0 );
  1712. additionalSplit.insertionPosition = insertionPosition;
  1713. a.splitPosition = a.splitPosition._getTransformedByMergeOperation( b );
  1714. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1715. a.graveyardPosition = additionalSplit.insertionPosition.clone();
  1716. a.graveyardPosition.stickiness = 'toNext';
  1717. return [ additionalSplit, a ];
  1718. }
  1719. // The default case.
  1720. //
  1721. if ( a.splitPosition.hasSameParentAs( b.deletionPosition ) && !a.splitPosition.isAfter( b.deletionPosition ) ) {
  1722. a.howMany--;
  1723. }
  1724. if ( a.splitPosition.hasSameParentAs( b.targetPosition ) ) {
  1725. a.howMany += b.howMany;
  1726. }
  1727. a.splitPosition = a.splitPosition._getTransformedByMergeOperation( b );
  1728. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1729. if ( a.graveyardPosition ) {
  1730. a.graveyardPosition = a.graveyardPosition._getTransformedByMergeOperation( b );
  1731. }
  1732. return [ a ];
  1733. } );
  1734. setTransformation( SplitOperation, MoveOperation, ( a, b, context ) => {
  1735. const rangeToMove = Range._createFromPositionAndShift( b.sourcePosition, b.howMany );
  1736. if ( a.graveyardPosition ) {
  1737. // Case 1:
  1738. //
  1739. // Split operation graveyard node was moved. In this case move operation is stronger. Since graveyard element
  1740. // is already moved to the correct position, we need to only move the nodes after the split position.
  1741. // This will be done by `MoveOperation` instead of `SplitOperation`.
  1742. //
  1743. if ( rangeToMove.start.isEqual( a.graveyardPosition ) || rangeToMove.containsPosition( a.graveyardPosition ) ) {
  1744. const sourcePosition = a.splitPosition._getTransformedByMoveOperation( b );
  1745. const newParentPosition = a.graveyardPosition._getTransformedByMoveOperation( b );
  1746. const newTargetPath = newParentPosition.path.slice();
  1747. newTargetPath.push( 0 );
  1748. const newTargetPosition = new Position( newParentPosition.root, newTargetPath );
  1749. const moveOp = new MoveOperation( sourcePosition, a.howMany, newTargetPosition, 0 );
  1750. return [ moveOp ];
  1751. }
  1752. a.graveyardPosition = a.graveyardPosition._getTransformedByMoveOperation( b );
  1753. }
  1754. // Case 2:
  1755. //
  1756. // If the split position is inside the moved range, we need to shift the split position to a proper place.
  1757. // The position cannot be moved together with moved range because that would result in splitting of an incorrect element.
  1758. //
  1759. // Characters `bc` should be moved to the second paragraph while split position is between them:
  1760. // <paragraph>A[b|c]d</paragraph><paragraph>Xyz</paragraph>
  1761. //
  1762. // After move, new split position is incorrect:
  1763. // <paragraph>Ad</paragraph><paragraph>Xb|cyz</paragraph>
  1764. //
  1765. // Correct split position:
  1766. // <paragraph>A|d</paragraph><paragraph>Xbcyz</paragraph>
  1767. //
  1768. // After split:
  1769. // <paragraph>A</paragraph><paragraph>d</paragraph><paragraph>Xbcyz</paragraph>
  1770. //
  1771. if ( a.splitPosition.hasSameParentAs( b.sourcePosition ) && rangeToMove.containsPosition( a.splitPosition ) ) {
  1772. const howManyRemoved = b.howMany - ( a.splitPosition.offset - b.sourcePosition.offset );
  1773. a.howMany -= howManyRemoved;
  1774. if ( a.splitPosition.hasSameParentAs( b.targetPosition ) && a.splitPosition.offset < b.targetPosition.offset ) {
  1775. a.howMany += b.howMany;
  1776. }
  1777. a.splitPosition = b.sourcePosition.clone();
  1778. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1779. return [ a ];
  1780. }
  1781. // Case 3:
  1782. //
  1783. // Split is at a position where nodes were moved.
  1784. //
  1785. // This is a scenario described in `MoveOperation` x `SplitOperation` transformation but from the
  1786. // "split operation point of view".
  1787. //
  1788. const splitAtTarget = a.splitPosition.isEqual( b.targetPosition );
  1789. if ( splitAtTarget && ( context.baRelation == 'insertAtSource' || context.abRelation == 'splitBefore' ) ) {
  1790. a.howMany += b.howMany;
  1791. a.splitPosition = a.splitPosition._getTransformedByDeletion( b.sourcePosition, b.howMany );
  1792. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1793. return [ a ];
  1794. }
  1795. // The default case.
  1796. // Don't change `howMany` if move operation does not really move anything.
  1797. //
  1798. if ( !b.sourcePosition.isEqual( b.targetPosition ) ) {
  1799. if ( a.splitPosition.hasSameParentAs( b.sourcePosition ) && a.splitPosition.offset <= b.sourcePosition.offset ) {
  1800. a.howMany -= b.howMany;
  1801. }
  1802. if ( a.splitPosition.hasSameParentAs( b.targetPosition ) && a.splitPosition.offset < b.targetPosition.offset ) {
  1803. a.howMany += b.howMany;
  1804. }
  1805. }
  1806. // Change position stickiness to force a correct transformation.
  1807. a.splitPosition.stickiness = 'toNone';
  1808. a.splitPosition = a.splitPosition._getTransformedByMoveOperation( b );
  1809. a.splitPosition.stickiness = 'toNext';
  1810. if ( a.graveyardPosition ) {
  1811. a.insertionPosition = a.insertionPosition._getTransformedByMoveOperation( b );
  1812. } else {
  1813. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1814. }
  1815. return [ a ];
  1816. } );
  1817. setTransformation( SplitOperation, SplitOperation, ( a, b, context ) => {
  1818. // Case 1:
  1819. //
  1820. // Split at the same position.
  1821. //
  1822. // If there already was a split at the same position as in `a` operation, it means that the intention
  1823. // conveyed by `a` operation has already been fulfilled and `a` should not do anything (to avoid double split).
  1824. //
  1825. // However, there is a difference if these are new splits or splits created by undo. These have different
  1826. // intentions. Also splits moving back different elements from graveyard have different intentions. They
  1827. // are just different operations.
  1828. //
  1829. // So we cancel split operation only if it was really identical.
  1830. //
  1831. if ( a.splitPosition.isEqual( b.splitPosition ) ) {
  1832. if ( !a.graveyardPosition && !b.graveyardPosition ) {
  1833. return [ new NoOperation( 0 ) ];
  1834. }
  1835. if ( a.graveyardPosition && b.graveyardPosition && a.graveyardPosition.isEqual( b.graveyardPosition ) ) {
  1836. return [ new NoOperation( 0 ) ];
  1837. }
  1838. }
  1839. // Case 2:
  1840. //
  1841. // Same node is using to split different elements. This happens in undo when previously same element was merged to
  1842. // two different elements. This is described in `MergeOperation` x `MergeOperation` transformation.
  1843. //
  1844. // In this case we will follow the same logic. We will assume that `insertionPosition` is same for both
  1845. // split operations. This might not always be true but in the real cases that were experienced it was. After all,
  1846. // if these splits are reverses of merge operations that were merging the same element, then the `insertionPosition`
  1847. // should be same for both of those splits.
  1848. //
  1849. // Again, we will decide which operation is stronger by checking if split happens in graveyard or in non-graveyard root.
  1850. //
  1851. if ( a.graveyardPosition && b.graveyardPosition && a.graveyardPosition.isEqual( b.graveyardPosition ) ) {
  1852. const aInGraveyard = a.splitPosition.root.rootName == '$graveyard';
  1853. const bInGraveyard = b.splitPosition.root.rootName == '$graveyard';
  1854. // If `aIsWeak` it means that `a` points to graveyard while `b` doesn't. Don't move nodes then.
  1855. const aIsWeak = aInGraveyard && !bInGraveyard;
  1856. // If `bIsWeak` it means that `b` points to graveyard while `a` doesn't. Force moving nodes then.
  1857. const bIsWeak = bInGraveyard && !aInGraveyard;
  1858. // Force move if `b` is weak or neither operation is weak but `a` is stronger through `context.aIsStrong`.
  1859. const forceMove = bIsWeak || ( !aIsWeak && context.aIsStrong );
  1860. if ( forceMove ) {
  1861. const result = [];
  1862. // First we need to move any nodes split by `b` back to where they were.
  1863. // Do it only if `b` actually moved something.
  1864. if ( b.howMany ) {
  1865. result.push( new MoveOperation( b.moveTargetPosition, b.howMany, b.splitPosition, 0 ) );
  1866. }
  1867. // Then we need to move nodes from `a` split position to their new element.
  1868. // Do it only if `a` actually should move something.
  1869. if ( a.howMany ) {
  1870. result.push( new MoveOperation( a.splitPosition, a.howMany, a.moveTargetPosition, 0 ) );
  1871. }
  1872. return result;
  1873. } else {
  1874. return [ new NoOperation( 0 ) ];
  1875. }
  1876. }
  1877. if ( a.graveyardPosition ) {
  1878. a.graveyardPosition = a.graveyardPosition._getTransformedBySplitOperation( b );
  1879. }
  1880. // Case 3:
  1881. //
  1882. // Position where operation `b` inserted a new node after split is the same as the operation `a` split position.
  1883. // As in similar cases, there is ambiguity if the split should be before the new node (created by `b`) or after.
  1884. //
  1885. if ( a.splitPosition.isEqual( b.insertionPosition ) && context.abRelation == 'splitBefore' ) {
  1886. a.howMany++;
  1887. return [ a ];
  1888. }
  1889. // Case 4:
  1890. //
  1891. // This is a mirror to the case 2. above.
  1892. //
  1893. if ( b.splitPosition.isEqual( a.insertionPosition ) && context.baRelation == 'splitBefore' ) {
  1894. const newPositionPath = b.insertionPosition.path.slice();
  1895. newPositionPath.push( 0 );
  1896. const newPosition = new Position( b.insertionPosition.root, newPositionPath );
  1897. const moveOp = new MoveOperation( a.insertionPosition, 1, newPosition, 0 );
  1898. return [ a, moveOp ];
  1899. }
  1900. // The default case.
  1901. //
  1902. if ( a.splitPosition.hasSameParentAs( b.splitPosition ) && a.splitPosition.offset < b.splitPosition.offset ) {
  1903. a.howMany -= b.howMany;
  1904. }
  1905. a.splitPosition = a.splitPosition._getTransformedBySplitOperation( b );
  1906. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1907. return [ a ];
  1908. } );
  1909. // Checks whether `MoveOperation` `targetPosition` is inside a node from the moved range of the other `MoveOperation`.
  1910. //
  1911. // @private
  1912. // @param {module:engine/model/operation/moveoperation~MoveOperation} a
  1913. // @param {module:engine/model/operation/moveoperation~MoveOperation} b
  1914. // @returns {Boolean}
  1915. function _moveTargetIntoMovedRange( a, b ) {
  1916. return a.targetPosition._getTransformedByDeletion( b.sourcePosition, b.howMany ) === null;
  1917. }
  1918. // Helper function for `MoveOperation` x `MoveOperation` transformation. Converts given ranges and target position to
  1919. // move operations and returns them.
  1920. //
  1921. // Ranges and target position will be transformed on-the-fly when generating operations.
  1922. //
  1923. // Given `ranges` should be in the order of how they were in the original transformed operation.
  1924. //
  1925. // Given `targetPosition` is the target position of the first range from `ranges`.
  1926. //
  1927. // @private
  1928. // @param {Array.<module:engine/model/range~Range>} ranges
  1929. // @param {module:engine/model/position~Position} targetPosition
  1930. // @returns {Array.<module:engine/model/operation/moveoperation~MoveOperation>}
  1931. function _makeMoveOperationsFromRanges( ranges, targetPosition ) {
  1932. // At this moment we have some ranges and a target position, to which those ranges should be moved.
  1933. // Order in `ranges` array is the go-to order of after transformation.
  1934. //
  1935. // We are almost done. We have `ranges` and `targetPosition` to make operations from.
  1936. // Unfortunately, those operations may affect each other. Precisely, first operation after move
  1937. // may affect source range and target position of second and third operation. Same with second
  1938. // operation affecting third.
  1939. //
  1940. // We need to fix those source ranges and target positions once again, before converting `ranges` to operations.
  1941. const operations = [];
  1942. // Keep in mind that nothing will be transformed if there is just one range in `ranges`.
  1943. for ( let i = 0; i < ranges.length; i++ ) {
  1944. // Create new operation out of a range and target position.
  1945. const range = ranges[ i ];
  1946. const op = new MoveOperation(
  1947. range.start,
  1948. range.end.offset - range.start.offset,
  1949. // If the target is the end of the move range this operation doesn't really move anything.
  1950. // In this case, it is better for OT to use range start instead of range end.
  1951. targetPosition.isEqual( range.end ) ? range.start : targetPosition,
  1952. 0
  1953. );
  1954. operations.push( op );
  1955. // Transform other ranges by the generated operation.
  1956. for ( let j = i + 1; j < ranges.length; j++ ) {
  1957. // All ranges in `ranges` array should be:
  1958. //
  1959. // * non-intersecting (these are part of original operation source range), and
  1960. // * `targetPosition` does not target into them (opposite would mean that transformed operation targets "inside itself").
  1961. //
  1962. // This means that the transformation will be "clean" and always return one result.
  1963. ranges[ j ] = ranges[ j ]._getTransformedByMove( op.sourcePosition, op.targetPosition, op.howMany )[ 0 ];
  1964. }
  1965. targetPosition = targetPosition._getTransformedByMove( op.sourcePosition, op.targetPosition, op.howMany );
  1966. }
  1967. return operations;
  1968. }