transform.js 85 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132
  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. }
  412. break;
  413. }
  414. case MoveOperation: {
  415. if ( opA.targetPosition.isEqual( opB.sourcePosition ) || opA.targetPosition.isBefore( opB.sourcePosition ) ) {
  416. this._setRelation( opA, opB, 'insertBefore' );
  417. } else {
  418. this._setRelation( opA, opB, 'insertAfter' );
  419. }
  420. break;
  421. }
  422. }
  423. break;
  424. }
  425. case SplitOperation: {
  426. switch ( opB.constructor ) {
  427. case MergeOperation: {
  428. if ( opA.splitPosition.isBefore( opB.sourcePosition ) ) {
  429. this._setRelation( opA, opB, 'splitBefore' );
  430. }
  431. break;
  432. }
  433. case MoveOperation: {
  434. if ( opA.splitPosition.isEqual( opB.sourcePosition ) || opA.splitPosition.isBefore( opB.sourcePosition ) ) {
  435. this._setRelation( opA, opB, 'splitBefore' );
  436. }
  437. break;
  438. }
  439. }
  440. break;
  441. }
  442. case MergeOperation: {
  443. switch ( opB.constructor ) {
  444. case MergeOperation: {
  445. if ( !opA.targetPosition.isEqual( opB.sourcePosition ) ) {
  446. this._setRelation( opA, opB, 'mergeTargetNotMoved' );
  447. }
  448. break;
  449. }
  450. }
  451. break;
  452. }
  453. }
  454. }
  455. // Evaluates and returns contextual information about two given operations `opA` and `opB` which are about to be transformed.
  456. //
  457. // @param {module:engine/model/operation/operation~Operation} opA
  458. // @param {module:engine/model/operation/operation~Operation} opB
  459. // @returns {module:engine/model/operation/transform~TransformationContext}
  460. getContext( opA, opB, aIsStrong ) {
  461. return {
  462. aIsStrong,
  463. aWasUndone: this._wasUndone( opA ),
  464. bWasUndone: this._wasUndone( opB ),
  465. abRelation: this._useRelations ? this._getRelation( opA, opB ) : null,
  466. baRelation: this._useRelations ? this._getRelation( opB, opA ) : null
  467. };
  468. }
  469. // Returns whether given operation `op` has already been undone.
  470. //
  471. // Information whether an operation was undone gives more context when making a decision when two operations are in conflict.
  472. //
  473. // @param {module:engine/model/operation/operation~Operation} op
  474. // @returns {Boolean}
  475. _wasUndone( op ) {
  476. // For `op`, get its original operation. After all, if `op` is a clone (or even transformed clone) of another
  477. // operation, literally `op` couldn't be undone. It was just generated. If anything, it was the operation it origins
  478. // from which was undone. So get that original operation.
  479. const originalOp = this._originalOperations.get( op );
  480. // And check with the document if the original operation was undone.
  481. return originalOp.wasUndone || this._history.isUndoneOperation( originalOp );
  482. }
  483. // Returns a relation between `opA` and an operation which is undone by `opB`. This can be `String` value if a relation
  484. // was set earlier or `null` if there was no relation between those operations.
  485. //
  486. // This is a little tricky to understand, so let's compare it to `ContextFactory#_wasUndone`.
  487. //
  488. // When `wasUndone( opB )` is used, we check if the `opB` has already been undone. It is obvious, that the
  489. // undoing operation must happen after the undone operation. So, essentially, we have `opB`, we take document history,
  490. // we look forward in the future and ask if in that future `opB` was undone.
  491. //
  492. // Relations is a backward process to `wasUndone()`.
  493. //
  494. // Long story short - using relations is asking what happened in the past. Looking back. This time we have an undoing
  495. // operation `opB` which has undone some other operation. When there is a transformation `opA` x `opB` and there is
  496. // a conflict to solve and `opB` is an undoing operation, we can look back in the history and see what was a relation
  497. // between `opA` and the operation which `opB` undone. Basing on that relation from the past, we can now make
  498. // a better decision when resolving a conflict between two operations, because we know more about the context of
  499. // those two operations.
  500. //
  501. // This is why this function does not return a relation directly between `opA` and `opB` because we need to look
  502. // back to search for a meaningful contextual information.
  503. //
  504. // @param {module:engine/model/operation/operation~Operation} opA
  505. // @param {module:engine/model/operation/operation~Operation} opB
  506. // @returns {String|null}
  507. _getRelation( opA, opB ) {
  508. // Get the original operation. Similarly as in `wasUndone()` it is used as an universal identifier for stored data.
  509. const origB = this._originalOperations.get( opB );
  510. const undoneB = this._history.getUndoneOperation( origB );
  511. // If `opB` is not undoing any operation, there is no relation.
  512. if ( !undoneB ) {
  513. return null;
  514. }
  515. const origA = this._originalOperations.get( opA );
  516. const relationsA = this._relations.get( origA );
  517. // Get all relations for `opA`, and check if there is a relation with `opB`-undone-counterpart. If so, return it.
  518. if ( relationsA ) {
  519. return relationsA.get( undoneB ) || null;
  520. }
  521. return null;
  522. }
  523. // Helper function for `ContextFactory#updateRelations`.
  524. //
  525. // @private
  526. // @param {module:engine/model/operation/operation~Operation} opA
  527. // @param {module:engine/model/operation/operation~Operation} opB
  528. // @param {String} relation
  529. _setRelation( opA, opB, relation ) {
  530. // As always, setting is for original operations, not the clones/transformed operations.
  531. const origA = this._originalOperations.get( opA );
  532. const origB = this._originalOperations.get( opB );
  533. let relationsA = this._relations.get( origA );
  534. if ( !relationsA ) {
  535. relationsA = new Map();
  536. this._relations.set( origA, relationsA );
  537. }
  538. relationsA.set( origB, relation );
  539. }
  540. }
  541. /**
  542. * Holds additional contextual information about a transformed pair of operations (`a` and `b`). Those information
  543. * can be used for better conflict resolving.
  544. *
  545. * @typedef {Object} module:engine/model/operation/transform~TransformationContext
  546. *
  547. * @property {Boolean} aIsStrong Whether `a` is strong operation in this transformation, or weak.
  548. * @property {Boolean} aWasUndone Whether `a` operation was undone.
  549. * @property {Boolean} bWasUndone Whether `b` operation was undone.
  550. * @property {String|null} abRelation The relation between `a` operation and an operation undone by `b` operation.
  551. * @property {String|null} baRelation The relation between `b` operation and an operation undone by `a` operation.
  552. */
  553. /**
  554. * An utility function that updates {@link module:engine/model/operation/operation~Operation#baseVersion base versions}
  555. * of passed operations.
  556. *
  557. * The function simply sets `baseVersion` as a base version of the first passed operation and then increments it for
  558. * each following operation in `operations`.
  559. *
  560. * @private
  561. * @param {Array.<module:engine/model/operation/operation~Operation>} operations Operations to update.
  562. * @param {Number} baseVersion Base version to set for the first operation in `operations`.
  563. */
  564. function updateBaseVersions( operations, baseVersion ) {
  565. for ( const operation of operations ) {
  566. operation.baseVersion = baseVersion++;
  567. }
  568. }
  569. /**
  570. * Adds `howMany` instances of {@link module:engine/model/operation/nooperation~NoOperation} to `operations` set.
  571. *
  572. * @private
  573. * @param {Array.<module:engine/model/operation/operation~Operation>} operations
  574. * @param {Number} howMany
  575. */
  576. function padWithNoOps( operations, howMany ) {
  577. for ( let i = 0; i < howMany; i++ ) {
  578. operations.push( new NoOperation( 0 ) );
  579. }
  580. }
  581. // -----------------------
  582. setTransformation( AttributeOperation, AttributeOperation, ( a, b, context ) => {
  583. if ( a.key === b.key ) {
  584. // If operations attributes are in conflict, check if their ranges intersect and manage them properly.
  585. // First, we want to apply change to the part of a range that has not been changed by the other operation.
  586. const operations = a.range.getDifference( b.range ).map( range => {
  587. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, 0 );
  588. } );
  589. // Then we take care of the common part of ranges.
  590. const common = a.range.getIntersection( b.range );
  591. if ( common ) {
  592. // If this operation is more important, we also want to apply change to the part of the
  593. // original range that has already been changed by the other operation. Since that range
  594. // got changed we also have to update `oldValue`.
  595. if ( context.aIsStrong ) {
  596. operations.push( new AttributeOperation( common, b.key, b.newValue, a.newValue, 0 ) );
  597. }
  598. }
  599. if ( operations.length == 0 ) {
  600. return [ new NoOperation( 0 ) ];
  601. }
  602. return operations;
  603. } else {
  604. // If operations don't conflict, simply return an array containing just a clone of this operation.
  605. return [ a ];
  606. }
  607. } );
  608. setTransformation( AttributeOperation, InsertOperation, ( a, b ) => {
  609. // Case 1:
  610. //
  611. // The attribute operation range includes the position where nodes were inserted.
  612. // There are two possible scenarios: the inserted nodes were text and they should receive attributes or
  613. // the inserted nodes were elements and they should not receive attributes.
  614. //
  615. if ( a.range.start.hasSameParentAs( b.position ) && a.range.containsPosition( b.position ) ) {
  616. // If new nodes should not receive attributes, two separated ranges will be returned.
  617. // Otherwise, one expanded range will be returned.
  618. const range = a.range._getTransformedByInsertion( b.position, b.howMany, !b.shouldReceiveAttributes );
  619. const result = range.map( r => {
  620. return new AttributeOperation( r, a.key, a.oldValue, a.newValue, a.baseVersion );
  621. } );
  622. if ( b.shouldReceiveAttributes ) {
  623. // `AttributeOperation#range` includes some newly inserted text.
  624. // The operation should also change the attribute of that text. An example:
  625. //
  626. // Bold should be applied on the following range:
  627. // <p>Fo[zb]ar</p>
  628. //
  629. // In meantime, new text is typed:
  630. // <p>Fozxxbar</p>
  631. //
  632. // Bold should be applied also on the new text:
  633. // <p>Fo[zxxb]ar</p>
  634. // <p>Fo<$text bold="true">zxxb</$text>ar</p>
  635. //
  636. // There is a special case to consider here to consider.
  637. //
  638. // Consider setting an attribute with multiple possible values, for example `highlight`. The inserted text might
  639. // have already an attribute value applied and the `oldValue` property of the attribute operation might be wrong:
  640. //
  641. // Attribute `highlight="yellow"` should be applied on the following range:
  642. // <p>Fo[zb]ar<p>
  643. //
  644. // In meantime, character `x` with `highlight="red"` is typed:
  645. // <p>Fo[z<$text highlight="red">x</$text>b]ar</p>
  646. //
  647. // In this case we cannot simply apply operation changing the attribute value from `null` to `"yellow"` for the whole range
  648. // because that would lead to an exception (`oldValue` is incorrect for `x`).
  649. //
  650. // We also cannot break the original range as this would mess up a scenario when there are multiple following
  651. // insert operations, because then only the first inserted character is included in those ranges:
  652. // <p>Fo[z][x][b]ar</p> --> <p>Fo[z][x]x[b]ar</p> --> <p>Fo[z][x]xx[b]ar</p>
  653. //
  654. // So, the attribute range needs be expanded, no matter what attributes are set on the inserted nodes:
  655. //
  656. // <p>Fo[z<$text highlight="red">x</$text>b]ar</p> <--- Change from `null` to `yellow`, throwing an exception.
  657. //
  658. // But before that operation would be applied, we will add an additional attribute operation that will change
  659. // attributes on the inserted nodes in a way which would make the original operation correct:
  660. //
  661. // <p>Fo[z{<$text highlight="red">}x</$text>b]ar</p> <--- Change range `{}` from `red` to `null`.
  662. // <p>Fo[zxb]ar</p> <--- Now change from `null` to `yellow` is completely fine.
  663. //
  664. // Generate complementary attribute operation. Be sure to add it before the original operation.
  665. const op = _getComplementaryAttributeOperations( b, a.key, a.oldValue );
  666. if ( op ) {
  667. result.unshift( op );
  668. }
  669. }
  670. // If nodes should not receive new attribute, we are done here.
  671. return result;
  672. }
  673. // If insert operation is not expanding the attribute operation range, simply transform the range.
  674. a.range = a.range._getTransformedByInsertion( b.position, b.howMany, false )[ 0 ];
  675. return [ a ];
  676. } );
  677. /**
  678. * Helper function for `AttributeOperation` x `InsertOperation` (and reverse) transformation.
  679. *
  680. * For given `insertOperation` it checks the inserted node if it has an attribute `key` set to a value different
  681. * than `newValue`. If so, it generates an `AttributeOperation` which changes the value of `key` attribute to `newValue`.
  682. *
  683. * @private
  684. * @param {module:engine/model/operation/insertoperation~InsertOperation} insertOperation
  685. * @param {String} key
  686. * @param {*} newValue
  687. * @returns {module:engine/model/operation/attributeoperation~AttributeOperation|null}
  688. */
  689. function _getComplementaryAttributeOperations( insertOperation, key, newValue ) {
  690. const nodes = insertOperation.nodes;
  691. // At the beginning we store the attribute value from the first node.
  692. const insertValue = nodes.getNode( 0 ).getAttribute( key );
  693. if ( insertValue == newValue ) {
  694. return null;
  695. }
  696. const range = new Range( insertOperation.position, insertOperation.position.getShiftedBy( insertOperation.howMany ) );
  697. return new AttributeOperation( range, key, insertValue, newValue, 0 );
  698. }
  699. setTransformation( AttributeOperation, MergeOperation, ( a, b ) => {
  700. const ranges = [];
  701. // Case 1:
  702. //
  703. // Attribute change on the merged element. In this case, the merged element was moved to the graveyard.
  704. // An additional attribute operation that will change the (re)moved element needs to be generated.
  705. //
  706. if ( a.range.start.hasSameParentAs( b.deletionPosition ) ) {
  707. if ( a.range.containsPosition( b.deletionPosition ) || a.range.start.isEqual( b.deletionPosition ) ) {
  708. ranges.push( Range.createFromPositionAndShift( b.graveyardPosition, 1 ) );
  709. }
  710. }
  711. const range = a.range._getTransformedByMergeOperation( b );
  712. // Do not add empty (collapsed) ranges to the result. `range` may be collapsed if it contained only the merged element.
  713. if ( !range.isCollapsed ) {
  714. ranges.push( range );
  715. }
  716. // Create `AttributeOperation`s out of the ranges.
  717. return ranges.map( range => {
  718. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
  719. } );
  720. } );
  721. setTransformation( AttributeOperation, MoveOperation, ( a, b ) => {
  722. const ranges = _breakRangeByMoveOperation( a.range, b );
  723. // Create `AttributeOperation`s out of the ranges.
  724. return ranges.map( range => new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion ) );
  725. } );
  726. // Helper function for `AttributeOperation` x `MoveOperation` transformation.
  727. //
  728. // Takes the passed `range` and transforms it by move operation `moveOp` in a specific way. Only top-level nodes of `range`
  729. // are considered to be in the range. If move operation moves nodes deep from inside of the range, those nodes won't
  730. // be included in the result. In other words, top-level nodes of the ranges from the result are exactly the same as
  731. // top-level nodes of the original `range`.
  732. //
  733. // This is important for `AttributeOperation` because, for its range, it changes only the top-level nodes. So we need to
  734. // track only how those nodes have been affected by `MoveOperation`.
  735. //
  736. // @private
  737. // @param {module:engine/model/range~Range} range
  738. // @param {module:engine/model/operation/moveoperation~MoveOperation} moveOp
  739. // @returns {Array.<module:engine/model/range~Range>}
  740. function _breakRangeByMoveOperation( range, moveOp ) {
  741. const moveRange = Range.createFromPositionAndShift( moveOp.sourcePosition, moveOp.howMany );
  742. // We are transforming `range` (original range) by `moveRange` (range moved by move operation). As usual when it comes to
  743. // transforming a ranges, we may have a common part of the ranges and we may have a difference part (zero to two ranges).
  744. let common = null;
  745. let difference = [];
  746. // Let's compare the ranges.
  747. if ( moveRange.containsRange( range, true ) ) {
  748. // If the whole original range is moved, treat it whole as a common part. There's also no difference part.
  749. common = range;
  750. } else if ( range.start.hasSameParentAs( moveRange.start ) ) {
  751. // If the ranges are "on the same level" (in the same parent) then move operation may move exactly those nodes
  752. // that are changed by the attribute operation. In this case we get common part and difference part in the usual way.
  753. difference = range.getDifference( moveRange );
  754. common = range.getIntersection( moveRange );
  755. } else {
  756. // In any other situation we assume that original range is different than move range, that is that move operation
  757. // moves other nodes that attribute operation change. Even if the moved range is deep inside in the original range.
  758. //
  759. // Note that this is different than in `.getIntersection` (we would get a common part in that case) and different
  760. // than `.getDifference` (we would get two ranges).
  761. difference = [ range ];
  762. }
  763. const result = [];
  764. // The default behaviour of `_getTransformedByMove` might get wrong results for difference part, though, so
  765. // we do it by hand.
  766. for ( let diff of difference ) {
  767. // First, transform the range by removing moved nodes. Since this is a difference, this is safe, `null` won't be returned
  768. // as the range is different than the moved range.
  769. diff = diff._getTransformedByDeletion( moveOp.sourcePosition, moveOp.howMany );
  770. // Transform also `targetPosition`.
  771. const targetPosition = moveOp.getMovedRangeStart();
  772. // Spread the range only if moved nodes are inserted only between the top-level nodes of the `diff` range.
  773. const spread = diff.start.hasSameParentAs( targetPosition );
  774. // Transform by insertion of moved nodes.
  775. diff = diff._getTransformedByInsertion( targetPosition, moveOp.howMany, spread );
  776. result.push( ...diff );
  777. }
  778. // Common part can be simply transformed by the move operation. This is because move operation will not target to
  779. // that common part (the operation would have to target inside its own moved range).
  780. if ( common ) {
  781. result.push(
  782. common._getTransformedByMove( moveOp.sourcePosition, moveOp.targetPosition, moveOp.howMany, false )[ 0 ]
  783. );
  784. }
  785. return result;
  786. }
  787. setTransformation( AttributeOperation, SplitOperation, ( a, b ) => {
  788. // Case 1:
  789. //
  790. // Split node is the last node in `AttributeOperation#range`.
  791. // `AttributeOperation#range` needs to be expanded to include the new (split) node.
  792. //
  793. // Attribute `type` to be changed to `numbered` but the `listItem` is split.
  794. // <listItem type="bulleted">foobar</listItem>
  795. //
  796. // After split:
  797. // <listItem type="bulleted">foo</listItem><listItem type="bulleted">bar</listItem>
  798. //
  799. // After attribute change:
  800. // <listItem type="numbered">foo</listItem><listItem type="numbered">foo</listItem>
  801. //
  802. if ( a.range.end.isEqual( b.insertionPosition ) && !b.graveyardPosition ) {
  803. a.range.end.offset++;
  804. return [ a ];
  805. }
  806. // Case 2:
  807. //
  808. // Split position is inside `AttributeOperation#range`, at the same level, so the nodes to change are
  809. // not going to make a flat range.
  810. //
  811. // Content with range-to-change and split position:
  812. // <p>Fo[zb^a]r</p>
  813. //
  814. // After split:
  815. // <p>Fozb</p><p>ar</p>
  816. //
  817. // Make two separate ranges containing all nodes to change:
  818. // <p>Fo[zb]</p><p>[a]r</p>
  819. //
  820. if ( a.range.start.hasSameParentAs( b.splitPosition ) && a.range.containsPosition( b.splitPosition ) ) {
  821. const secondPart = a.clone();
  822. secondPart.range = new Range(
  823. Position.createFromPosition( b.moveTargetPosition ),
  824. a.range.end._getCombined( b.splitPosition, b.moveTargetPosition )
  825. );
  826. a.range.end = Position.createFromPosition( b.splitPosition );
  827. a.range.end.stickiness = 'toPrevious';
  828. return [ a, secondPart ];
  829. }
  830. // The default case.
  831. //
  832. a.range = a.range._getTransformedBySplitOperation( b );
  833. return [ a ];
  834. } );
  835. setTransformation( InsertOperation, AttributeOperation, ( a, b ) => {
  836. const result = [ a ];
  837. // Case 1:
  838. //
  839. // The attribute operation range includes the position where nodes were inserted.
  840. // There are two possible scenarios: the inserted nodes were text and they should receive attributes or
  841. // the inserted nodes were elements and they should not receive attributes.
  842. //
  843. // This is a mirror scenario to the one described in `AttributeOperation` x `InsertOperation` transformation,
  844. // although this case is a little less complicated. In this case we simply need to change attributes of the
  845. // inserted nodes and that's it.
  846. //
  847. if ( a.shouldReceiveAttributes && a.position.hasSameParentAs( b.range.start ) && b.range.containsPosition( a.position ) ) {
  848. const op = _getComplementaryAttributeOperations( a, b.key, b.newValue );
  849. if ( op ) {
  850. result.push( op );
  851. }
  852. }
  853. // The default case is: do nothing.
  854. // `AttributeOperation` does not change the model tree structure so `InsertOperation` does not need to be changed.
  855. //
  856. return result;
  857. } );
  858. setTransformation( InsertOperation, InsertOperation, ( a, b, context ) => {
  859. // Case 1:
  860. //
  861. // Two insert operations insert nodes at the same position. Since they are the same, it needs to be decided
  862. // what will be the order of inserted nodes. However, there is no additional information to help in that
  863. // decision. Also, when `b` will be transformed by `a`, the same order must be maintained.
  864. //
  865. // To achieve that, we will check if the operation is strong.
  866. // If it is, it won't get transformed. If it is not, it will be moved.
  867. //
  868. if ( a.position.isEqual( b.position ) && context.aIsStrong ) {
  869. return [ a ];
  870. }
  871. // The default case.
  872. //
  873. a.position = a.position._getTransformedByInsertOperation( b );
  874. return [ a ];
  875. } );
  876. setTransformation( InsertOperation, MoveOperation, ( a, b ) => {
  877. // The default case.
  878. //
  879. a.position = a.position._getTransformedByMoveOperation( b );
  880. return [ a ];
  881. } );
  882. setTransformation( InsertOperation, SplitOperation, ( a, b ) => {
  883. // The default case.
  884. //
  885. a.position = a.position._getTransformedBySplitOperation( b );
  886. return [ a ];
  887. } );
  888. setTransformation( InsertOperation, MergeOperation, ( a, b ) => {
  889. a.position = a.position._getTransformedByMergeOperation( b );
  890. return [ a ];
  891. } );
  892. // -----------------------
  893. setTransformation( MarkerOperation, InsertOperation, ( a, b ) => {
  894. if ( a.oldRange ) {
  895. a.oldRange = a.oldRange._getTransformedByInsertOperation( b )[ 0 ];
  896. }
  897. if ( a.newRange ) {
  898. a.newRange = a.newRange._getTransformedByInsertOperation( b )[ 0 ];
  899. }
  900. return [ a ];
  901. } );
  902. setTransformation( MarkerOperation, MarkerOperation, ( a, b, context ) => {
  903. if ( a.name == b.name ) {
  904. if ( context.aIsStrong ) {
  905. a.oldRange = b.newRange ? Range.createFromRange( b.newRange ) : null;
  906. } else {
  907. return [ new NoOperation( 0 ) ];
  908. }
  909. }
  910. return [ a ];
  911. } );
  912. setTransformation( MarkerOperation, MergeOperation, ( a, b ) => {
  913. if ( a.oldRange ) {
  914. a.oldRange = a.oldRange._getTransformedByMergeOperation( b );
  915. }
  916. if ( a.newRange ) {
  917. a.newRange = a.newRange._getTransformedByMergeOperation( b );
  918. }
  919. return [ a ];
  920. } );
  921. setTransformation( MarkerOperation, MoveOperation, ( a, b ) => {
  922. if ( a.oldRange ) {
  923. a.oldRange = Range.createFromRanges( a.oldRange._getTransformedByMoveOperation( b ) );
  924. }
  925. if ( a.newRange ) {
  926. a.newRange = Range.createFromRanges( a.newRange._getTransformedByMoveOperation( b ) );
  927. }
  928. return [ a ];
  929. } );
  930. setTransformation( MarkerOperation, SplitOperation, ( a, b ) => {
  931. if ( a.oldRange ) {
  932. a.oldRange = a.oldRange._getTransformedBySplitOperation( b );
  933. }
  934. if ( a.newRange ) {
  935. a.newRange = a.newRange._getTransformedBySplitOperation( b );
  936. }
  937. return [ a ];
  938. } );
  939. // -----------------------
  940. setTransformation( MergeOperation, InsertOperation, ( a, b ) => {
  941. if ( a.sourcePosition.hasSameParentAs( b.position ) ) {
  942. a.howMany += b.howMany;
  943. }
  944. a.sourcePosition = a.sourcePosition._getTransformedByInsertOperation( b );
  945. a.targetPosition = a.targetPosition._getTransformedByInsertOperation( b );
  946. return [ a ];
  947. } );
  948. setTransformation( MergeOperation, MergeOperation, ( a, b, context ) => {
  949. // Case 1:
  950. //
  951. // Same merge operations.
  952. //
  953. // Both operations have same source and target positions. So the element already got merged and there is
  954. // theoretically nothing to do.
  955. //
  956. if ( a.sourcePosition.isEqual( b.sourcePosition ) && a.targetPosition.isEqual( b.targetPosition ) ) {
  957. // There are two ways that we can provide a do-nothing operation.
  958. //
  959. // First is simply a NoOperation instance. We will use it if `b` operation was not undone.
  960. //
  961. // Second is a merge operation that has the source operation in the merged element - in the graveyard -
  962. // same target position and `howMany` equal to `0`. So it is basically merging an empty element from graveyard
  963. // which is almost the same as NoOperation.
  964. //
  965. // This way the merge operation can be later transformed by split operation
  966. // to provide correct undo. This will be used if `b` operation was undone (only then it is correct).
  967. //
  968. if ( !context.bWasUndone ) {
  969. return [ new NoOperation( 0 ) ];
  970. } else {
  971. const path = b.graveyardPosition.path.slice();
  972. path.push( 0 );
  973. a.sourcePosition = new Position( b.graveyardPosition.root, path );
  974. a.howMany = 0;
  975. return [ a ];
  976. }
  977. }
  978. // Case 2:
  979. //
  980. // Same merge source position but different target position.
  981. //
  982. // This can happen during collaboration. For example, if one client merged a paragraph to the previous paragraph
  983. // and the other person removed that paragraph and merged the same paragraph to something before:
  984. //
  985. // Client A:
  986. // <p>Foo</p><p>Bar</p><p>[]Xyz</p>
  987. // <p>Foo</p><p>BarXyz</p>
  988. //
  989. // Client B:
  990. // <p>Foo</p>[<p>Bar</p>]<p>Xyz</p>
  991. // <p>Foo</p><p>[]Xyz</p>
  992. // <p>FooXyz</p>
  993. //
  994. // In this case we need to decide where finally "Xyz" will land:
  995. //
  996. // <p>FooXyz</p> graveyard: <p>Bar</p>
  997. // <p>Foo</p> graveyard: <p>BarXyz</p>
  998. //
  999. // Let's move it in a way so that a merge operation that does not target to graveyard is more important so that
  1000. // nodes does not end up in the graveyard. It makes sense. Both for Client A and for Client B "Xyz" finally did not
  1001. // end up in the graveyard (see above).
  1002. //
  1003. // If neither or both operations point to graveyard, then let `aIsStrong` decide.
  1004. //
  1005. if ( a.sourcePosition.isEqual( b.sourcePosition ) && !a.targetPosition.isEqual( b.targetPosition ) && !context.bWasUndone ) {
  1006. const aToGraveyard = a.targetPosition.root.rootName == '$graveyard';
  1007. const bToGraveyard = b.targetPosition.root.rootName == '$graveyard';
  1008. // If `aIsWeak` it means that `a` points to graveyard while `b` doesn't. Don't move nodes then.
  1009. const aIsWeak = aToGraveyard && !bToGraveyard;
  1010. // If `bIsWeak` it means that `b` points to graveyard while `a` doesn't. Force moving nodes then.
  1011. const bIsWeak = bToGraveyard && !aToGraveyard;
  1012. // Force move if `b` is weak or neither operation is weak but `a` is stronger through `context.aIsStrong`.
  1013. const forceMove = bIsWeak || ( !aIsWeak && context.aIsStrong );
  1014. if ( forceMove ) {
  1015. const sourcePosition = b.targetPosition._getTransformedByMergeOperation( b );
  1016. const targetPosition = a.targetPosition._getTransformedByMergeOperation( b );
  1017. return [ new MoveOperation( sourcePosition, a.howMany, targetPosition, 0 ) ];
  1018. } else {
  1019. return [ new NoOperation( 0 ) ];
  1020. }
  1021. }
  1022. // The default case.
  1023. //
  1024. if ( a.sourcePosition.hasSameParentAs( b.targetPosition ) ) {
  1025. a.howMany += b.howMany;
  1026. }
  1027. a.sourcePosition = a.sourcePosition._getTransformedByMergeOperation( b );
  1028. a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );
  1029. // Handle positions in graveyard.
  1030. // If graveyard positions are same and `a` operation is strong - do not transform.
  1031. if ( !a.graveyardPosition.isEqual( b.graveyardPosition ) || !context.aIsStrong ) {
  1032. a.graveyardPosition = a.graveyardPosition._getTransformedByMergeOperation( b );
  1033. }
  1034. return [ a ];
  1035. } );
  1036. setTransformation( MergeOperation, MoveOperation, ( a, b, context ) => {
  1037. // Case 1:
  1038. //
  1039. // The element to merge got removed.
  1040. //
  1041. // Merge operation does support merging elements which are not siblings. So it would not be a problem
  1042. // from technical point of view. However, if the element was removed, the intention of the user deleting it
  1043. // was to have it all deleted, together with its children. From user experience point of view, moving back the
  1044. // removed nodes might be unexpected. This means that in this scenario we will block the merging.
  1045. //
  1046. // The exception of this rule would be if the remove operation was later undone.
  1047. //
  1048. const removedRange = Range.createFromPositionAndShift( b.sourcePosition, b.howMany );
  1049. if ( b.type == 'remove' && !context.bWasUndone ) {
  1050. if ( a.deletionPosition.hasSameParentAs( b.sourcePosition ) && removedRange.containsPosition( a.sourcePosition ) ) {
  1051. return [ new NoOperation( 0 ) ];
  1052. }
  1053. }
  1054. // The default case.
  1055. //
  1056. if ( a.sourcePosition.hasSameParentAs( b.targetPosition ) ) {
  1057. a.howMany += b.howMany;
  1058. }
  1059. if ( a.sourcePosition.hasSameParentAs( b.sourcePosition ) ) {
  1060. a.howMany -= b.howMany;
  1061. }
  1062. a.sourcePosition = a.sourcePosition._getTransformedByMoveOperation( b );
  1063. a.targetPosition = a.targetPosition._getTransformedByMoveOperation( b );
  1064. // `MergeOperation` graveyard position is like `MoveOperation` target position. It is a position where element(s) will
  1065. // be moved. Like in other similar cases, we need to consider the scenario when those positions are same.
  1066. // Here, we will treat `MergeOperation` like it is always strong (see `InsertOperation` x `InsertOperation` for comparison).
  1067. // This means that we won't transform graveyard position if it is equal to move operation target position.
  1068. if ( !a.graveyardPosition.isEqual( b.targetPosition ) ) {
  1069. a.graveyardPosition = a.graveyardPosition._getTransformedByMoveOperation( b );
  1070. }
  1071. return [ a ];
  1072. } );
  1073. setTransformation( MergeOperation, SplitOperation, ( a, b, context ) => {
  1074. if ( b.graveyardPosition ) {
  1075. // If `b` operation defines graveyard position, a node from graveyard will be moved. This means that we need to
  1076. // transform `a.graveyardPosition` accordingly.
  1077. a.graveyardPosition = a.graveyardPosition._getTransformedByDeletion( b.graveyardPosition, 1 );
  1078. // This is a scenario foreseen in `MergeOperation` x `MergeOperation`, with two identical merge operations.
  1079. //
  1080. // So, there was `MergeOperation` x `MergeOperation` transformation earlier. Now, `a` is a merge operation which
  1081. // source position is in graveyard. Interestingly, split operation wants to use the node to be merged by `a`. This
  1082. // means that `b` is undoing that merge operation from earlier, which caused `a` to be in graveyard.
  1083. //
  1084. // If that's the case, at this point, we will only "fix" `a.howMany`. It was earlier set to `0` in
  1085. // `MergeOperation` x `MergeOperation` transformation. Later transformations in this function will change other
  1086. // properties.
  1087. //
  1088. if ( a.deletionPosition.isEqual( b.graveyardPosition ) ) {
  1089. a.howMany = b.howMany;
  1090. }
  1091. }
  1092. // Case 1:
  1093. //
  1094. // Merge operation moves nodes to the place where split happens.
  1095. // This is a classic situation when there are two paragraphs, and there is a split (enter) after the first
  1096. // paragraph and there is a merge (delete) at the beginning of the second paragraph:
  1097. //
  1098. // <p>Foo{}</p><p>[]Bar</p>.
  1099. //
  1100. // Split is after `Foo`, while merge is from `Bar` to the end of `Foo`.
  1101. //
  1102. // State after split:
  1103. // <p>Foo</p><p></p><p>Bar</p>
  1104. //
  1105. // Now, `Bar` should be merged to the new paragraph:
  1106. // <p>Foo</p><p>Bar</p>
  1107. //
  1108. // Instead of merging it to the original paragraph:
  1109. // <p>FooBar</p><p></p>
  1110. //
  1111. // This means that `targetPosition` needs to be transformed. This is the default case though.
  1112. // For example, if the split would be after `F`, `targetPosition` should also be transformed.
  1113. //
  1114. // There are three exceptions, though, when we want to keep `targetPosition` as it was.
  1115. //
  1116. // First exception is when the merge target position is inside an element (not at the end, as usual). This
  1117. // happens when the merge operation earlier was transformed by "the same" merge operation. If merge operation
  1118. // targets inside the element we want to keep the original target position (and not transform it) because
  1119. // we have additional context telling us that we want to merge to the original element. We can check if the
  1120. // merge operation points inside element by checking what is `SplitOperation#howMany`. Since merge target position
  1121. // is same as split position, if `howMany` is non-zero, it means that the merge target position is inside an element.
  1122. //
  1123. // Second exception is when the element to merge is in the graveyard and split operation uses it. In that case
  1124. // if target position would be transformed, the merge operation would target at the source position:
  1125. //
  1126. // root: <p>Foo</p> graveyard: <p></p>
  1127. //
  1128. // SplitOperation: root [ 0, 3 ] using graveyard [ 0 ] (howMany = 0)
  1129. // MergeOperation: graveyard [ 0, 0 ] -> root [ 0, 3 ] (howMany = 0)
  1130. //
  1131. // Since split operation moves the graveyard node back to the root, the merge operation source position changes.
  1132. // We would like to merge from the empty <p> to the "Foo" <p>:
  1133. //
  1134. // root: <p>Foo</p><p></p> graveyard:
  1135. //
  1136. // MergeOperation#sourcePosition = root [ 1, 0 ]
  1137. //
  1138. // If `targetPosition` is transformed, it would become root [ 1, 0 ] as well. It has to be kept as it was.
  1139. //
  1140. // Third exception is connected with relations. If this happens during undo and we have explicit information
  1141. // that target position has not been affected by the operation which is undone by this split then this split should
  1142. // not move the target position either.
  1143. //
  1144. if ( a.targetPosition.isEqual( b.splitPosition ) ) {
  1145. const mergeInside = b.howMany != 0;
  1146. const mergeSplittingElement = b.graveyardPosition && a.deletionPosition.isEqual( b.graveyardPosition );
  1147. if ( mergeInside || mergeSplittingElement || context.abRelation == 'mergeTargetNotMoved' ) {
  1148. a.sourcePosition = a.sourcePosition._getTransformedBySplitOperation( b );
  1149. return [ a ];
  1150. }
  1151. }
  1152. // The default case.
  1153. //
  1154. if ( a.sourcePosition.hasSameParentAs( b.splitPosition ) ) {
  1155. a.howMany = b.splitPosition.offset;
  1156. }
  1157. a.sourcePosition = a.sourcePosition._getTransformedBySplitOperation( b );
  1158. a.targetPosition = a.targetPosition._getTransformedBySplitOperation( b );
  1159. return [ a ];
  1160. } );
  1161. // -----------------------
  1162. setTransformation( MoveOperation, InsertOperation, ( a, b ) => {
  1163. const moveRange = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  1164. const transformed = moveRange._getTransformedByInsertOperation( b, false )[ 0 ];
  1165. a.sourcePosition = transformed.start;
  1166. a.howMany = transformed.end.offset - transformed.start.offset;
  1167. // See `InsertOperation` x `MoveOperation` transformation for details on this case.
  1168. //
  1169. // In summary, both operations point to the same place, so the order of nodes needs to be decided.
  1170. // `MoveOperation` is considered weaker, so it is always transformed, unless there was a certain relation
  1171. // between operations.
  1172. //
  1173. if ( !a.targetPosition.isEqual( b.position ) ) {
  1174. a.targetPosition = a.targetPosition._getTransformedByInsertOperation( b );
  1175. }
  1176. return [ a ];
  1177. } );
  1178. setTransformation( MoveOperation, MoveOperation, ( a, b, context ) => {
  1179. //
  1180. // Setting and evaluating some variables that will be used in special cases and default algorithm.
  1181. //
  1182. // Create ranges from `MoveOperations` properties.
  1183. const rangeA = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  1184. const rangeB = Range.createFromPositionAndShift( b.sourcePosition, b.howMany );
  1185. // Assign `context.aIsStrong` to a different variable, because the value may change during execution of
  1186. // this algorithm and we do not want to override original `context.aIsStrong` that will be used in later transformations.
  1187. let aIsStrong = context.aIsStrong;
  1188. // This will be used to decide the order of nodes if both operations target at the same position.
  1189. // By default, use strong/weak operation mechanism.
  1190. let insertBefore = !context.aIsStrong;
  1191. // If the relation is set, then use it to decide nodes order.
  1192. if ( context.abRelation == 'insertBefore' ) {
  1193. insertBefore = true;
  1194. } else if ( context.abRelation == 'insertAfter' ) {
  1195. insertBefore = false;
  1196. }
  1197. // `a.targetPosition` could be affected by the `b` operation. We will transform it.
  1198. let newTargetPosition;
  1199. if ( a.targetPosition.isEqual( b.targetPosition ) && insertBefore ) {
  1200. newTargetPosition = a.targetPosition._getTransformedByDeletion(
  1201. b.sourcePosition,
  1202. b.howMany
  1203. );
  1204. } else {
  1205. newTargetPosition = a.targetPosition._getTransformedByMove(
  1206. b.sourcePosition,
  1207. b.targetPosition,
  1208. b.howMany
  1209. );
  1210. }
  1211. //
  1212. // Special case #1 + mirror.
  1213. //
  1214. // Special case when both move operations' target positions are inside nodes that are
  1215. // being moved by the other move operation. So in other words, we move ranges into inside of each other.
  1216. // This case can't be solved reasonably (on the other hand, it should not happen often).
  1217. if ( _moveTargetIntoMovedRange( a, b ) && _moveTargetIntoMovedRange( b, a ) ) {
  1218. // Instead of transforming operation, we return a reverse of the operation that we transform by.
  1219. // So when the results of this "transformation" will be applied, `b` MoveOperation will get reversed.
  1220. return [ b.getReversed() ];
  1221. }
  1222. //
  1223. // End of special case #1.
  1224. //
  1225. //
  1226. // Special case #2.
  1227. //
  1228. // Check if `b` operation targets inside `rangeA`.
  1229. const bTargetsToA = rangeA.containsPosition( b.targetPosition );
  1230. // If `b` targets to `rangeA` and `rangeA` contains `rangeB`, `b` operation has no influence on `a` operation.
  1231. // You might say that operation `b` is captured inside operation `a`.
  1232. if ( bTargetsToA && rangeA.containsRange( rangeB, true ) ) {
  1233. // There is a mini-special case here, where `rangeB` is on other level than `rangeA`. That's why
  1234. // we need to transform `a` operation anyway.
  1235. rangeA.start = rangeA.start._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  1236. rangeA.end = rangeA.end._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  1237. return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition );
  1238. }
  1239. //
  1240. // Special case #2 mirror.
  1241. //
  1242. const aTargetsToB = rangeB.containsPosition( a.targetPosition );
  1243. if ( aTargetsToB && rangeB.containsRange( rangeA, true ) ) {
  1244. // `a` operation is "moved together" with `b` operation.
  1245. // Here, just move `rangeA` "inside" `rangeB`.
  1246. rangeA.start = rangeA.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  1247. rangeA.end = rangeA.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  1248. return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition );
  1249. }
  1250. //
  1251. // End of special case #2.
  1252. //
  1253. //
  1254. // Special case #3 + mirror.
  1255. //
  1256. // `rangeA` has a node which is an ancestor of `rangeB`. In other words, `rangeB` is inside `rangeA`
  1257. // but not on the same tree level. In such case ranges have common part but we have to treat it
  1258. // differently, because in such case those ranges are not really conflicting and should be treated like
  1259. // two separate ranges. Also we have to discard two difference parts.
  1260. const aCompB = compareArrays( a.sourcePosition.getParentPath(), b.sourcePosition.getParentPath() );
  1261. if ( aCompB == 'prefix' || aCompB == 'extension' ) {
  1262. // Transform `rangeA` by `b` operation and make operation out of it, and that's all.
  1263. // Note that this is a simplified version of default case, but here we treat the common part (whole `rangeA`)
  1264. // like a one difference part.
  1265. rangeA.start = rangeA.start._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  1266. rangeA.end = rangeA.end._getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany );
  1267. return _makeMoveOperationsFromRanges( [ rangeA ], newTargetPosition );
  1268. }
  1269. //
  1270. // End of special case #3.
  1271. //
  1272. //
  1273. // Default case - ranges are on the same level or are not connected with each other.
  1274. //
  1275. // Modifier for default case.
  1276. // Modifies `aIsStrong` flag in certain conditions.
  1277. //
  1278. // If only one of operations is a remove operation, we force remove operation to be the "stronger" one
  1279. // to provide more expected results.
  1280. if ( a.type == 'remove' && b.type != 'remove' && !context.aWasUndone ) {
  1281. aIsStrong = true;
  1282. } else if ( a.type != 'remove' && b.type == 'remove' && !context.bWasUndone ) {
  1283. aIsStrong = false;
  1284. }
  1285. // Handle operation's source ranges - check how `rangeA` is affected by `b` operation.
  1286. // This will aggregate transformed ranges.
  1287. const ranges = [];
  1288. // Get the "difference part" of `a` operation source range.
  1289. // This is an array with one or two ranges. Two ranges if `rangeB` is inside `rangeA`.
  1290. const difference = rangeA.getDifference( rangeB );
  1291. for ( const range of difference ) {
  1292. // Transform those ranges by `b` operation. For example if `b` moved range from before those ranges, fix those ranges.
  1293. range.start = range.start._getTransformedByDeletion( b.sourcePosition, b.howMany );
  1294. range.end = range.end._getTransformedByDeletion( b.sourcePosition, b.howMany );
  1295. // If `b` operation targets into `rangeA` on the same level, spread `rangeA` into two ranges.
  1296. const shouldSpread = compareArrays( range.start.getParentPath(), b.getMovedRangeStart().getParentPath() ) == 'same';
  1297. const newRanges = range._getTransformedByInsertion( b.getMovedRangeStart(), b.howMany, shouldSpread );
  1298. ranges.push( ...newRanges );
  1299. }
  1300. // Then, we have to manage the "common part" of both move ranges.
  1301. const common = rangeA.getIntersection( rangeB );
  1302. if ( common !== null && aIsStrong ) {
  1303. // Calculate the new position of that part of original range.
  1304. common.start = common.start._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  1305. common.end = common.end._getCombined( b.sourcePosition, b.getMovedRangeStart() );
  1306. // Take care of proper range order.
  1307. //
  1308. // Put `common` at appropriate place. Keep in mind that we are interested in original order.
  1309. // Basically there are only three cases: there is zero, one or two difference ranges.
  1310. //
  1311. // If there is zero difference ranges, just push `common` in the array.
  1312. if ( ranges.length === 0 ) {
  1313. ranges.push( common );
  1314. }
  1315. // If there is one difference range, we need to check whether common part was before it or after it.
  1316. else if ( ranges.length == 1 ) {
  1317. if ( rangeB.start.isBefore( rangeA.start ) || rangeB.start.isEqual( rangeA.start ) ) {
  1318. ranges.unshift( common );
  1319. } else {
  1320. ranges.push( common );
  1321. }
  1322. }
  1323. // If there are more ranges (which means two), put common part between them. This is the only scenario
  1324. // where there could be two difference ranges so we don't have to make any comparisons.
  1325. else {
  1326. ranges.splice( 1, 0, common );
  1327. }
  1328. }
  1329. if ( ranges.length === 0 ) {
  1330. // If there are no "source ranges", nothing should be changed.
  1331. // Note that this can happen only if `aIsStrong == false` and `rangeA.isEqual( rangeB )`.
  1332. return [ new NoOperation( a.baseVersion ) ];
  1333. }
  1334. return _makeMoveOperationsFromRanges( ranges, newTargetPosition );
  1335. } );
  1336. setTransformation( MoveOperation, SplitOperation, ( a, b, context ) => {
  1337. let newTargetPosition = Position.createFromPosition( a.targetPosition );
  1338. // Do not transform if target position is same as split insertion position and this split comes from undo.
  1339. // This should be done on relations but it is too much work for now as it would require relations working in collaboration.
  1340. // We need to make a decision how we will resolve such conflict and this is less harmful way.
  1341. if ( !a.targetPosition.isEqual( b.insertionPosition ) || !b.graveyardPosition ) {
  1342. newTargetPosition = a.targetPosition._getTransformedBySplitOperation( b );
  1343. }
  1344. // Case 1:
  1345. //
  1346. // Last element in the moved range got split.
  1347. //
  1348. // In this case the default range transformation will not work correctly as the element created by
  1349. // split operation would be outside the range. The range to move needs to be fixed manually.
  1350. // Do it only if this is a "natural" split, not a one that comes from undo.
  1351. // TODO: this should be done on relations
  1352. //
  1353. const moveRange = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  1354. if ( moveRange.end.isEqual( b.insertionPosition ) && !b.graveyardPosition ) {
  1355. a.howMany++;
  1356. a.targetPosition = newTargetPosition;
  1357. return [ a ];
  1358. }
  1359. // Case 2:
  1360. //
  1361. // Split happened between the moved nodes. In this case two ranges to move need to be generated.
  1362. //
  1363. // Characters `ozba` are moved to the end of paragraph `Xyz` but split happened.
  1364. // <p>F[oz|ba]r</p><p>Xyz</p>
  1365. //
  1366. // After split:
  1367. // <p>F[oz</p><p>ba]r</p><p>Xyz</p>
  1368. //
  1369. // Correct ranges:
  1370. // <p>F[oz]</p><p>[ba]r</p><p>Xyz</p>
  1371. //
  1372. // After move:
  1373. // <p>F</p><p>r</p><p>Xyzozba</p>
  1374. //
  1375. if ( moveRange.start.hasSameParentAs( b.splitPosition ) && moveRange.containsPosition( b.splitPosition ) ) {
  1376. let rightRange = new Range( b.splitPosition, moveRange.end );
  1377. rightRange = rightRange._getTransformedBySplitOperation( b );
  1378. const ranges = [
  1379. new Range( moveRange.start, b.splitPosition ),
  1380. rightRange
  1381. ];
  1382. return _makeMoveOperationsFromRanges( ranges, newTargetPosition );
  1383. }
  1384. // Case 3:
  1385. //
  1386. // Move operation targets at the split position. We need to decide if the nodes should be inserted
  1387. // at the end of the split element or at the beginning of the new element.
  1388. //
  1389. if ( a.targetPosition.isEqual( b.splitPosition ) && context.abRelation == 'insertAtSource' ) {
  1390. newTargetPosition = b.moveTargetPosition;
  1391. }
  1392. // Case 4:
  1393. //
  1394. // Move operation targets just after the split element. We need to decide if the nodes should be inserted
  1395. // between two parts of split element, or after the new element.
  1396. //
  1397. // Split at `|`, while move operation moves `<p>Xyz</p>` and targets at `^`:
  1398. // <p>Foo|bar</p>^<p>baz</p>
  1399. // <p>Foo</p>^<p>bar</p><p>baz</p> or <p>Foo</p><p>bar</p>^<p>baz</p>?
  1400. //
  1401. // If there is no contextual information between operations (for example, they come from collaborative
  1402. // editing), we don't want to put some unrelated content (move) between parts of related content (split parts).
  1403. // However, if the split is from undo, in the past, the moved content might be targeting between the
  1404. // split parts, meaning that was exactly user's intention:
  1405. //
  1406. // <p>Foo</p>^<p>bar</p> <--- original situation, in "past".
  1407. // <p>Foobar</p>^ <--- after merge target position is transformed.
  1408. // <p>Foo|bar</p>^ <--- then the merge is undone, and split happens, which leads us to current situation.
  1409. //
  1410. // In this case it is pretty clear that the intention was to put new paragraph between those nodes,
  1411. // so we need to transform accordingly. We can detect this scenario thanks to relations.
  1412. //
  1413. if ( a.targetPosition.isEqual( b.insertionPosition ) && context.abRelation == 'insertBetween' ) {
  1414. newTargetPosition = a.targetPosition;
  1415. }
  1416. // The default case.
  1417. //
  1418. const transformed = moveRange._getTransformedBySplitOperation( b );
  1419. a.sourcePosition = transformed.start;
  1420. a.howMany = transformed.end.offset - transformed.start.offset;
  1421. a.targetPosition = newTargetPosition;
  1422. return [ a ];
  1423. } );
  1424. setTransformation( MoveOperation, MergeOperation, ( a, b, context ) => {
  1425. const movedRange = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  1426. if ( b.deletionPosition.hasSameParentAs( a.sourcePosition ) && movedRange.containsPosition( b.sourcePosition ) ) {
  1427. if ( a.type == 'remove' ) {
  1428. // Case 1:
  1429. //
  1430. // The element to remove got merged.
  1431. //
  1432. // Merge operation does support merging elements which are not siblings. So it would not be a problem
  1433. // from technical point of view. However, if the element was removed, the intention of the user
  1434. // deleting it was to have it all deleted. From user experience point of view, moving back the
  1435. // removed nodes might be unexpected. This means that in this scenario we will reverse merging and remove the element.
  1436. //
  1437. if ( !context.aWasUndone ) {
  1438. return [ b.getReversed(), a ];
  1439. }
  1440. } else {
  1441. // Case 2:
  1442. //
  1443. // The element to move got merged and it was the only element to move.
  1444. // In this case just don't do anything, leave the node in the graveyard. Without special case
  1445. // it would be a move operation that moves 0 nodes, so maybe it is better just to return no-op.
  1446. //
  1447. if ( a.howMany == 1 ) {
  1448. if ( !context.bWasUndone ) {
  1449. return [ new NoOperation( 0 ) ];
  1450. } else {
  1451. a.sourcePosition = Position.createFromPosition( b.graveyardPosition );
  1452. a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );
  1453. return [ a ];
  1454. }
  1455. }
  1456. }
  1457. }
  1458. // The default case.
  1459. //
  1460. const moveRange = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  1461. const transformed = moveRange._getTransformedByMergeOperation( b );
  1462. a.sourcePosition = transformed.start;
  1463. a.howMany = transformed.end.offset - transformed.start.offset;
  1464. a.targetPosition = a.targetPosition._getTransformedByMergeOperation( b );
  1465. return [ a ];
  1466. } );
  1467. // -----------------------
  1468. setTransformation( RenameOperation, InsertOperation, ( a, b ) => {
  1469. a.position = a.position._getTransformedByInsertOperation( b );
  1470. return [ a ];
  1471. } );
  1472. setTransformation( RenameOperation, MergeOperation, ( a, b ) => {
  1473. // Case 1:
  1474. //
  1475. // Element to rename got merged, so it was moved to `b.graveyardPosition`.
  1476. //
  1477. if ( a.position.isEqual( b.deletionPosition ) ) {
  1478. a.position = Position.createFromPosition( b.graveyardPosition );
  1479. a.position.stickiness = 'toNext';
  1480. return [ a ];
  1481. }
  1482. a.position = a.position._getTransformedByMergeOperation( b );
  1483. return [ a ];
  1484. } );
  1485. setTransformation( RenameOperation, MoveOperation, ( a, b ) => {
  1486. a.position = a.position._getTransformedByMoveOperation( b );
  1487. return [ a ];
  1488. } );
  1489. setTransformation( RenameOperation, RenameOperation, ( a, b, context ) => {
  1490. if ( a.position.isEqual( b.position ) ) {
  1491. if ( context.aIsStrong ) {
  1492. a.oldName = b.newName;
  1493. } else {
  1494. return [ new NoOperation( 0 ) ];
  1495. }
  1496. }
  1497. return [ a ];
  1498. } );
  1499. setTransformation( RenameOperation, SplitOperation, ( a, b ) => {
  1500. // Case 1:
  1501. //
  1502. // The element to rename has been split. In this case, the new element should be also renamed.
  1503. //
  1504. // User decides to change the paragraph to a list item:
  1505. // <paragraph>Foobar</paragraph>
  1506. //
  1507. // However, in meantime, split happens:
  1508. // <paragraph>Foo</paragraph><paragraph>bar</paragraph>
  1509. //
  1510. // As a result, rename both elements:
  1511. // <listItem>Foo</listItem><listItem>bar</listItem>
  1512. //
  1513. const renamePath = a.position.path;
  1514. const splitPath = b.splitPosition.getParentPath();
  1515. if ( compareArrays( renamePath, splitPath ) == 'same' && !b.graveyardPosition ) {
  1516. const extraRename = new RenameOperation( a.position.getShiftedBy( 1 ), a.oldName, a.newName, 0 );
  1517. return [ a, extraRename ];
  1518. }
  1519. // The default case.
  1520. //
  1521. a.position = a.position._getTransformedBySplitOperation( b );
  1522. return [ a ];
  1523. } );
  1524. // -----------------------
  1525. setTransformation( RootAttributeOperation, RootAttributeOperation, ( a, b, context ) => {
  1526. if ( a.root === b.root && a.key === b.key ) {
  1527. if ( !context.aIsStrong || a.newValue === b.newValue ) {
  1528. return [ new NoOperation( 0 ) ];
  1529. } else {
  1530. a.oldValue = b.newValue;
  1531. }
  1532. }
  1533. return [ a ];
  1534. } );
  1535. // -----------------------
  1536. setTransformation( SplitOperation, InsertOperation, ( a, b ) => {
  1537. // The default case.
  1538. //
  1539. if ( a.splitPosition.hasSameParentAs( b.position ) && a.splitPosition.offset < b.position.offset ) {
  1540. a.howMany += b.howMany;
  1541. }
  1542. a.splitPosition = a.splitPosition._getTransformedByInsertOperation( b );
  1543. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1544. return [ a ];
  1545. } );
  1546. setTransformation( SplitOperation, MergeOperation, ( a, b, context ) => {
  1547. // Case 1:
  1548. //
  1549. // Split element got merged. If two different elements were merged, clients will have different content.
  1550. //
  1551. // Example. Merge at `{}`, split at `[]`:
  1552. // <heading>Foo</heading>{}<paragraph>B[]ar</paragraph>
  1553. //
  1554. // On merge side it will look like this:
  1555. // <heading>FooB[]ar</heading>
  1556. // <heading>FooB</heading><heading>ar</heading>
  1557. //
  1558. // On split side it will look like this:
  1559. // <heading>Foo</heading>{}<paragraph>B</paragraph><paragraph>ar</paragraph>
  1560. // <heading>FooB</heading><paragraph>ar</paragraph>
  1561. //
  1562. // Clearly, the second element is different for both clients.
  1563. //
  1564. // We could use the removed merge element from graveyard as a split element but then clients would have a different
  1565. // model state (in graveyard), because the split side client would still have an element in graveyard (removed by merge).
  1566. //
  1567. // To overcome this, in `SplitOperation` x `MergeOperation` transformation we will add additional `SplitOperation`
  1568. // in the graveyard, which will actually clone the merged-and-deleted element. Then, that cloned element will be
  1569. // used for splitting. Example below.
  1570. //
  1571. // Original state:
  1572. // <heading>Foo</heading>{}<paragraph>B[]ar</paragraph>
  1573. //
  1574. // Merge side client:
  1575. //
  1576. // After merge:
  1577. // <heading>FooB[]ar</heading> graveyard: <paragraph></paragraph>
  1578. //
  1579. // Extra split:
  1580. // <heading>FooB[]ar</heading> graveyard: <paragraph></paragraph><paragraph></paragraph>
  1581. //
  1582. // Use the "cloned" element from graveyard:
  1583. // <heading>FooB</heading><paragraph>ar</paragraph> graveyard: <paragraph></paragraph>
  1584. //
  1585. // Split side client:
  1586. //
  1587. // After split:
  1588. // <heading>Foo</heading>{}<paragraph>B</paragraph><paragraph>ar</paragraph>
  1589. //
  1590. // After merge:
  1591. // <heading>FooB</heading><paragraph>ar</paragraph> graveyard: <paragraph></paragraph>
  1592. //
  1593. // This special case scenario only applies if the original split operation clones the split element.
  1594. // If the original split operation has `graveyardPosition` set, it all doesn't have sense because split operation
  1595. // knows exactly which element it should use. So there would be no original problem with different contents.
  1596. //
  1597. // Additionally, the special case applies only if the merge wasn't already undone.
  1598. //
  1599. if ( !a.graveyardPosition && !context.bWasUndone && a.splitPosition.hasSameParentAs( b.sourcePosition ) ) {
  1600. const splitPath = b.graveyardPosition.path.slice();
  1601. splitPath.push( 0 );
  1602. const splitPosition = new Position( b.graveyardPosition.root, splitPath );
  1603. const insertionPosition = SplitOperation.getInsertionPosition( new Position( b.graveyardPosition.root, splitPath ) );
  1604. const additionalSplit = new SplitOperation( splitPosition, 0, insertionPosition, null, 0 );
  1605. a.splitPosition = a.splitPosition._getTransformedByMergeOperation( b );
  1606. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1607. a.graveyardPosition = Position.createFromPosition( additionalSplit.insertionPosition );
  1608. a.graveyardPosition.stickiness = 'toNext';
  1609. return [ additionalSplit, a ];
  1610. }
  1611. // The default case.
  1612. //
  1613. if ( a.splitPosition.hasSameParentAs( b.deletionPosition ) && !a.splitPosition.isAfter( b.deletionPosition ) ) {
  1614. a.howMany--;
  1615. }
  1616. if ( a.splitPosition.hasSameParentAs( b.targetPosition ) ) {
  1617. a.howMany += b.howMany;
  1618. }
  1619. a.splitPosition = a.splitPosition._getTransformedByMergeOperation( b );
  1620. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1621. if ( a.graveyardPosition ) {
  1622. a.graveyardPosition = a.graveyardPosition._getTransformedByMergeOperation( b );
  1623. }
  1624. return [ a ];
  1625. } );
  1626. setTransformation( SplitOperation, MoveOperation, ( a, b, context ) => {
  1627. if ( a.graveyardPosition ) {
  1628. a.graveyardPosition = a.graveyardPosition._getTransformedByMoveOperation( b );
  1629. }
  1630. // Case 1:
  1631. //
  1632. // If the split position is inside the moved range, we need to shift the split position to a proper place.
  1633. // The position cannot be moved together with moved range because that would result in splitting of an incorrect element.
  1634. //
  1635. // Characters `bc` should be moved to the second paragraph while split position is between them:
  1636. // <paragraph>A[b|c]d</paragraph><paragraph>Xyz</paragraph>
  1637. //
  1638. // After move, new split position is incorrect:
  1639. // <paragraph>Ad</paragraph><paragraph>Xb|cyz</paragraph>
  1640. //
  1641. // Correct split position:
  1642. // <paragraph>A|d</paragraph><paragraph>Xbcyz</paragraph>
  1643. //
  1644. // After split:
  1645. // <paragraph>A</paragraph><paragraph>d</paragraph><paragraph>Xbcyz</paragraph>
  1646. //
  1647. const rangeToMove = Range.createFromPositionAndShift( b.sourcePosition, b.howMany );
  1648. if ( a.splitPosition.hasSameParentAs( b.sourcePosition ) && rangeToMove.containsPosition( a.splitPosition ) ) {
  1649. const howManyRemoved = b.howMany - ( a.splitPosition.offset - b.sourcePosition.offset );
  1650. a.howMany -= howManyRemoved;
  1651. if ( a.splitPosition.hasSameParentAs( b.targetPosition ) && a.splitPosition.offset < b.targetPosition.offset ) {
  1652. a.howMany += b.howMany;
  1653. }
  1654. a.splitPosition = Position.createFromPosition( b.sourcePosition );
  1655. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1656. return [ a ];
  1657. }
  1658. // Case 2:
  1659. //
  1660. // Split is at a position where nodes were moved.
  1661. //
  1662. // This is a scenario described in `MoveOperation` x `SplitOperation` transformation but from the
  1663. // "split operation point of view".
  1664. //
  1665. const splitAtTarget = a.splitPosition.isEqual( b.targetPosition );
  1666. if ( splitAtTarget && ( context.baRelation == 'insertAtSource' || context.abRelation == 'splitBefore' ) ) {
  1667. a.howMany += b.howMany;
  1668. a.splitPosition = a.splitPosition._getTransformedByDeletion( b.sourcePosition, b.howMany );
  1669. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1670. return [ a ];
  1671. }
  1672. // The default case.
  1673. //
  1674. if ( a.splitPosition.hasSameParentAs( b.sourcePosition ) && a.splitPosition.offset <= b.sourcePosition.offset ) {
  1675. a.howMany -= b.howMany;
  1676. }
  1677. if ( a.splitPosition.hasSameParentAs( b.targetPosition ) && a.splitPosition.offset < b.targetPosition.offset ) {
  1678. a.howMany += b.howMany;
  1679. }
  1680. // Change position stickiness to force a correct transformation.
  1681. a.splitPosition.stickiness = 'toNone';
  1682. a.splitPosition = a.splitPosition._getTransformedByMoveOperation( b );
  1683. a.splitPosition.stickiness = 'toNext';
  1684. if ( a.graveyardPosition ) {
  1685. a.insertionPosition = a.insertionPosition._getTransformedByMoveOperation( b );
  1686. } else {
  1687. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1688. }
  1689. return [ a ];
  1690. } );
  1691. setTransformation( SplitOperation, SplitOperation, ( a, b, context ) => {
  1692. // Case 1:
  1693. //
  1694. // Split at the same position.
  1695. //
  1696. // If there already was a split at the same position as in `a` operation, it means that the intention
  1697. // conveyed by `a` operation has already been fulfilled and `a` should not do anything (to avoid double split).
  1698. //
  1699. // However, there is a difference if these are new splits or splits created by undo. These have different
  1700. // intentions. Also splits moving back different elements from graveyard have different intentions. They
  1701. // are just different operations.
  1702. //
  1703. // So we cancel split operation only if it was really identical.
  1704. //
  1705. if ( a.splitPosition.isEqual( b.splitPosition ) ) {
  1706. if ( !a.graveyardPosition && !b.graveyardPosition ) {
  1707. return [ new NoOperation( 0 ) ];
  1708. }
  1709. if ( a.graveyardPosition && b.graveyardPosition && a.graveyardPosition.isEqual( b.graveyardPosition ) ) {
  1710. return [ new NoOperation( 0 ) ];
  1711. }
  1712. }
  1713. // Case 2:
  1714. //
  1715. // Same node is using to split different elements. This happens in undo when previously same element was merged to
  1716. // two different elements. This is described in `MergeOperation` x `MergeOperation` transformation.
  1717. //
  1718. // In this case we will follow the same logic. We will assume that `insertionPosition` is same for both
  1719. // split operations. This might not always be true but in the real cases that were experienced it was. After all,
  1720. // if these splits are reverses of merge operations that were merging the same element, then the `insertionPosition`
  1721. // should be same for both of those splits.
  1722. //
  1723. // Again, we will decide which operation is stronger by checking if split happens in graveyard or in non-graveyard root.
  1724. //
  1725. if ( a.graveyardPosition && b.graveyardPosition && a.graveyardPosition.isEqual( b.graveyardPosition ) ) {
  1726. const aInGraveyard = a.splitPosition.root.rootName == '$graveyard';
  1727. const bInGraveyard = b.splitPosition.root.rootName == '$graveyard';
  1728. // If `aIsWeak` it means that `a` points to graveyard while `b` doesn't. Don't move nodes then.
  1729. const aIsWeak = aInGraveyard && !bInGraveyard;
  1730. // If `bIsWeak` it means that `b` points to graveyard while `a` doesn't. Force moving nodes then.
  1731. const bIsWeak = bInGraveyard && !aInGraveyard;
  1732. // Force move if `b` is weak or neither operation is weak but `a` is stronger through `context.aIsStrong`.
  1733. const forceMove = bIsWeak || ( !aIsWeak && context.aIsStrong );
  1734. if ( forceMove ) {
  1735. const result = [];
  1736. // First we need to move any nodes split by `b` back to where they were.
  1737. // Do it only if `b` actually moved something.
  1738. if ( b.howMany ) {
  1739. result.push( new MoveOperation( b.moveTargetPosition, b.howMany, b.splitPosition, 0 ) );
  1740. }
  1741. // Then we need to move nodes from `a` split position to their new element.
  1742. // Do it only if `a` actually should move something.
  1743. if ( a.howMany ) {
  1744. result.push( new MoveOperation( a.splitPosition, a.howMany, a.moveTargetPosition, 0 ) );
  1745. }
  1746. return result;
  1747. } else {
  1748. return [ new NoOperation( 0 ) ];
  1749. }
  1750. }
  1751. if ( a.graveyardPosition ) {
  1752. a.graveyardPosition = a.graveyardPosition._getTransformedBySplitOperation( b );
  1753. }
  1754. // Case 3:
  1755. //
  1756. // Position where operation `b` inserted a new node after split is the same as the operation `a` split position.
  1757. // As in similar cases, there is ambiguity if the split should be before the new node (created by `b`) or after.
  1758. //
  1759. if ( a.splitPosition.isEqual( b.insertionPosition ) && context.abRelation == 'splitBefore' ) {
  1760. a.howMany++;
  1761. return [ a ];
  1762. }
  1763. // Case 4:
  1764. //
  1765. // This is a mirror to the case 2. above.
  1766. //
  1767. if ( b.splitPosition.isEqual( a.insertionPosition ) && context.baRelation == 'splitBefore' ) {
  1768. const newPositionPath = b.insertionPosition.path.slice();
  1769. newPositionPath.push( 0 );
  1770. const newPosition = new Position( b.insertionPosition.root, newPositionPath );
  1771. const moveOp = new MoveOperation( a.insertionPosition, 1, newPosition, 0 );
  1772. return [ a, moveOp ];
  1773. }
  1774. // The default case.
  1775. //
  1776. if ( a.splitPosition.hasSameParentAs( b.splitPosition ) && a.splitPosition.offset < b.splitPosition.offset ) {
  1777. a.howMany -= b.howMany;
  1778. }
  1779. a.splitPosition = a.splitPosition._getTransformedBySplitOperation( b );
  1780. a.insertionPosition = SplitOperation.getInsertionPosition( a.splitPosition );
  1781. return [ a ];
  1782. } );
  1783. // Checks whether `MoveOperation` `targetPosition` is inside a node from the moved range of the other `MoveOperation`.
  1784. //
  1785. // @private
  1786. // @param {module:engine/model/operation/moveoperation~MoveOperation} a
  1787. // @param {module:engine/model/operation/moveoperation~MoveOperation} b
  1788. // @returns {Boolean}
  1789. function _moveTargetIntoMovedRange( a, b ) {
  1790. return a.targetPosition._getTransformedByDeletion( b.sourcePosition, b.howMany ) === null;
  1791. }
  1792. // Helper function for `MoveOperation` x `MoveOperation` transformation. Converts given ranges and target position to
  1793. // move operations and returns them.
  1794. //
  1795. // Ranges and target position will be transformed on-the-fly when generating operations.
  1796. //
  1797. // Given `ranges` should be in the order of how they were in the original transformed operation.
  1798. //
  1799. // Given `targetPosition` is the target position of the first range from `ranges`.
  1800. //
  1801. // @private
  1802. // @param {Array.<module:engine/model/range~Range>} ranges
  1803. // @param {module:engine/model/position~Position} targetPosition
  1804. // @returns {Array.<module:engine/model/operation/moveoperation~MoveOperation>}
  1805. function _makeMoveOperationsFromRanges( ranges, targetPosition ) {
  1806. // At this moment we have some ranges and a target position, to which those ranges should be moved.
  1807. // Order in `ranges` array is the go-to order of after transformation.
  1808. //
  1809. // We are almost done. We have `ranges` and `targetPosition` to make operations from.
  1810. // Unfortunately, those operations may affect each other. Precisely, first operation after move
  1811. // may affect source range and target position of second and third operation. Same with second
  1812. // operation affecting third.
  1813. //
  1814. // We need to fix those source ranges and target positions once again, before converting `ranges` to operations.
  1815. const operations = [];
  1816. // Keep in mind that nothing will be transformed if there is just one range in `ranges`.
  1817. for ( let i = 0; i < ranges.length; i++ ) {
  1818. // Create new operation out of a range and target position.
  1819. const range = ranges[ i ];
  1820. const op = new MoveOperation( range.start, range.end.offset - range.start.offset, targetPosition, 0 );
  1821. operations.push( op );
  1822. // Transform other ranges by the generated operation.
  1823. for ( let j = i + 1; j < ranges.length; j++ ) {
  1824. // All ranges in `ranges` array should be:
  1825. //
  1826. // * non-intersecting (these are part of original operation source range), and
  1827. // * `targetPosition` does not target into them (opposite would mean that transformed operation targets "inside itself").
  1828. //
  1829. // This means that the transformation will be "clean" and always return one result.
  1830. ranges[ j ] = ranges[ j ]._getTransformedByMove( op.sourcePosition, op.targetPosition, op.howMany )[ 0 ];
  1831. }
  1832. targetPosition = targetPosition._getTransformedByMove( op.sourcePosition, op.targetPosition, op.howMany );
  1833. }
  1834. return operations;
  1835. }