transform.js 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678
  1. /**
  2. * @license Copyright (c) 2003-2017, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. /**
  6. * @protected
  7. * @module engine/model/delta/transform
  8. */
  9. import Delta from './delta';
  10. import MoveDelta from './movedelta';
  11. import RemoveDelta from './removedelta';
  12. import MergeDelta from './mergedelta';
  13. import SplitDelta from './splitdelta';
  14. import WrapDelta from './wrapdelta';
  15. import UnwrapDelta from './unwrapdelta';
  16. import RenameDelta from './renamedelta';
  17. import AttributeDelta from './attributedelta';
  18. import operationTransform from '../operation/transform';
  19. import NoOperation from '../operation/nooperation';
  20. import MoveOperation from '../operation/moveoperation';
  21. import RemoveOperation from '../operation/removeoperation';
  22. import arrayUtils from '@ckeditor/ckeditor5-utils/src/lib/lodash/array';
  23. import compareArrays from '@ckeditor/ckeditor5-utils/src/comparearrays';
  24. const specialCases = new Map();
  25. /**
  26. * @namespace
  27. */
  28. const transform = {
  29. /**
  30. * Transforms given {@link module:engine/model/delta/delta~Delta delta} by another {@link module:engine/model/delta/delta~Delta delta}
  31. * and returns the result of that transformation as an array containing one or more {@link module:engine/model/delta/delta~Delta delta}
  32. * instances.
  33. *
  34. * Delta transformations heavily base on {@link module:engine/model/operation/transform~transform operational transformations}. Since
  35. * delta is a list of operations most situations can be handled thanks to operational transformation. Unfortunately,
  36. * deltas are more complicated than operations and have they semantic meaning, as they represent user's editing intentions.
  37. *
  38. * Sometimes, simple operational transformation on deltas' operations might result in some unexpected results. Those
  39. * results would be fine from OT point of view, but would not reflect user's intentions. Because of such conflicts
  40. * we need to handle transformations in special cases in a custom way.
  41. *
  42. * The function itself looks whether two given delta types have a special case function registered. If so, the deltas are
  43. * transformed using that function. If not,
  44. * {@link module:engine/model/delta/transform~transform.defaultTransform default transformation algorithm} is used.
  45. *
  46. * @param {module:engine/model/delta/delta~Delta} a Delta that will be transformed.
  47. * @param {module:engine/model/delta/delta~Delta} b Delta to transform by.
  48. * @param {module:engine/model/delta/transform~transformationContext} context Transformation context object.
  49. * @returns {Array.<module:engine/model/delta/delta~Delta>} Result of the transformation.
  50. */
  51. transform( a, b, context ) {
  52. const transformAlgorithm = transform.getTransformationCase( a, b ) || transform.defaultTransform;
  53. // Make new instance of context object, so all changes done during transformation are not saved in original object.
  54. const transformed = transformAlgorithm( a, b, Object.assign( {}, context ) );
  55. const baseVersion = arrayUtils.last( b.operations ).baseVersion;
  56. return updateBaseVersion( baseVersion, transformed );
  57. },
  58. /**
  59. * The default delta transformation function. It is used for those deltas that are not in special case conflict.
  60. *
  61. * This algorithm is similar to a popular `dOPT` algorithm used in operational transformation, as we are in fact
  62. * transforming two sets of operations by each other.
  63. *
  64. * @param {module:engine/model/delta/delta~Delta} a Delta that will be transformed.
  65. * @param {module:engine/model/delta/delta~Delta} b Delta to transform by.
  66. * @param {module:engine/model/delta/transform~transformationContext} context Transformation context object.
  67. * @returns {Array.<module:engine/model/delta/delta~Delta>} Result of the transformation.
  68. */
  69. defaultTransform( a, b, context ) {
  70. // This will hold operations from delta `a` that will be transformed by operations from delta `b`.
  71. // Eventually, those operations will be used to create result delta(s).
  72. const transformed = [];
  73. // Array containing operations that we will transform by. At the beginning these are just operations from
  74. let byOps = b.operations;
  75. // This array is storing operations from `byOps` which got transformed by operation from delta `a`.
  76. let newByOps = [];
  77. // We take each operation from original set of operations to transform.
  78. for ( const opA of a.operations ) {
  79. // We wrap the operation in the array. This is important, because operation transformation algorithm returns
  80. // an array of operations so we need to make sure that our algorithm is ready to handle arrays.
  81. const ops = [ opA ];
  82. // Now the real algorithm takes place.
  83. for ( const opB of byOps ) {
  84. // For each operation that we need transform by...
  85. for ( let i = 0; i < ops.length; i++ ) {
  86. // We take each operation to transform...
  87. const op = ops[ i ];
  88. // And transform both of them by themselves.
  89. // The result of transforming operation from delta B by operation from delta A is saved in
  90. // `newByOps` array. We will use that array for transformations in next loops. We need delta B
  91. // operations after transformed by delta A operations to get correct results of transformations
  92. // of next operations from delta A.
  93. //
  94. // It's like this because 2nd operation from delta A assumes that 1st operation from delta A
  95. // is "already applied". When we transform 2nd operation from delta A by operations from delta B
  96. // we have to be sure that operations from delta B are in a state that acknowledges 1st operation
  97. // from delta A.
  98. //
  99. // This can be easier understood when operations sets to transform are represented by diamond diagrams:
  100. // http://www.codecommit.com/blog/java/understanding-and-applying-operational-transformation
  101. // Transform operation from delta A by operation from delta B.
  102. const results = operationTransform( op, opB, context );
  103. // We replace currently processed operation from `ops` array by the results of transformation.
  104. // Note, that we process single operation but `operationTransform` result is an array, so we
  105. // might have to splice-in more than one operation. Save them in `ops` array and move `i` pointer by a proper offset.
  106. Array.prototype.splice.apply( ops, [ i, 1 ].concat( results ) );
  107. i += results.length - 1;
  108. // Then, transform operation from delta B by operation from delta A.
  109. // Since this is a "mirror" transformation, first, we "mirror" some of context values.
  110. const reverseContext = Object.assign( {}, context );
  111. reverseContext.isStrong = !context.isStrong;
  112. reverseContext.insertBefore = context.insertBefore !== undefined ? !context.insertBefore : undefined;
  113. // Transform operations.
  114. const updatedOpB = operationTransform( opB, op, reverseContext );
  115. // Update `newByOps` by transformed, updated `opB`.
  116. // Using push.apply because `operationTransform` returns an array with one or multiple results.
  117. Array.prototype.push.apply( newByOps, updatedOpB );
  118. }
  119. // At this point a single operation from delta A got transformed by a single operation from delta B.
  120. // The transformation result is in `ops` array and it may be one or more operations. This was just the first step.
  121. // Operation from delta A has to be further transformed by the other operations from delta B.
  122. // So in next iterator loop we will take another operation from delta B and use transformed delta A (`ops`)
  123. // to transform it further.
  124. }
  125. // We got through all delta B operations and have a final transformed state of an operation from delta A.
  126. // As previously mentioned, we substitute operations from delta B by their transformed equivalents.
  127. byOps = newByOps;
  128. newByOps = [];
  129. // We add transformed operation from delta A to newly created delta.
  130. // Remember that transformed operation from delta A may consist of multiple operations.
  131. for ( const op of ops ) {
  132. transformed.push( op );
  133. }
  134. // In next loop, we will take another operation from delta A and transform it through (transformed) operations
  135. // from delta B...
  136. }
  137. return getNormalizedDeltas( a.constructor, transformed );
  138. },
  139. /**
  140. * Adds a special case callback for given delta classes.
  141. *
  142. * @param {Function} A Delta constructor which instance will get transformed.
  143. * @param {Function} B Delta constructor which instance will be transformed by.
  144. * @param {Function} resolver A callback that will handle custom special case transformation for instances of given delta classes.
  145. */
  146. addTransformationCase( A, B, resolver ) {
  147. let casesA = specialCases.get( A );
  148. if ( !casesA ) {
  149. casesA = new Map();
  150. specialCases.set( A, casesA );
  151. }
  152. casesA.set( B, resolver );
  153. },
  154. /**
  155. * Gets a special case callback which was previously {@link module:engine/model/delta/transform~transform.addTransformationCase added}.
  156. *
  157. * @param {module:engine/model/delta/delta~Delta} a Delta to transform.
  158. * @param {module:engine/model/delta/delta~Delta} b Delta to be transformed by.
  159. */
  160. getTransformationCase( a, b ) {
  161. let casesA = specialCases.get( a.constructor );
  162. // If there are no special cases registered for class which `a` is instance of, we will
  163. // check if there are special cases registered for any parent class.
  164. if ( !casesA || !casesA.get( b.constructor ) ) {
  165. const cases = specialCases.keys();
  166. for ( const caseClass of cases ) {
  167. if ( a instanceof caseClass && specialCases.get( caseClass ).get( b.constructor ) ) {
  168. casesA = specialCases.get( caseClass );
  169. break;
  170. }
  171. }
  172. }
  173. if ( casesA ) {
  174. return casesA.get( b.constructor );
  175. }
  176. return undefined;
  177. },
  178. /**
  179. * Transforms two sets of deltas by themselves. Returns both transformed sets.
  180. *
  181. * @param {Array.<module:engine/model/delta/delta~Delta>} deltasA Array with the first set of deltas to transform. These
  182. * deltas are considered more important (than `deltasB`) when resolving conflicts.
  183. * @param {Array.<module:engine/model/delta/delta~Delta>} deltasB Array with the second set of deltas to transform. These
  184. * deltas are considered less important (than `deltasA`) when resolving conflicts.
  185. * @param {module:engine/model/document~Document} [document=null] If set, deltas will be transformed in "context mode"
  186. * and given `document` will be used to determine relations between deltas. If not set (default), deltas will be
  187. * transforming without additional context information.
  188. * @returns {Object}
  189. * @returns {Array.<module:engine/model/delta/delta~Delta>} return.deltasA The first set of deltas transformed
  190. * by the second set of deltas.
  191. * @returns {Array.<module:engine/model/delta/delta~Delta>} return.deltasB The second set of deltas transformed
  192. * by the first set of deltas.
  193. */
  194. transformDeltaSets( deltasA, deltasB, document = null ) {
  195. const transformedDeltasA = Array.from( deltasA );
  196. const transformedDeltasB = Array.from( deltasB );
  197. const useAdditionalContext = document !== null;
  198. const contextAB = {
  199. isStrong: true
  200. };
  201. if ( useAdditionalContext ) {
  202. contextAB.wasAffected = new Map();
  203. contextAB.originalDelta = new Map();
  204. contextAB.document = document;
  205. for ( const delta of transformedDeltasB ) {
  206. contextAB.originalDelta.set( delta, delta );
  207. }
  208. }
  209. for ( let i = 0; i < transformedDeltasA.length; i++ ) {
  210. const deltaA = [ transformedDeltasA[ i ] ];
  211. for ( let j = 0; j < transformedDeltasB.length; j++ ) {
  212. const deltaB = [ transformedDeltasB[ j ] ];
  213. for ( let k = 0; k < deltaA.length; k++ ) {
  214. for ( let l = 0; l < deltaB.length; l++ ) {
  215. if ( useAdditionalContext ) {
  216. _setContext( deltaA[ k ], deltaB[ l ], contextAB );
  217. }
  218. const resultAB = transform.transform( deltaA[ k ], deltaB[ l ], {
  219. insertBefore: contextAB.insertBefore,
  220. forceNotSticky: contextAB.forceNotSticky,
  221. isStrong: contextAB.isStrong,
  222. forceWeakRemove: contextAB.forceWeakRemove,
  223. aWasUndone: false,
  224. bWasUndone: contextAB.bWasUndone
  225. } );
  226. const resultBA = transform.transform( deltaB[ l ], deltaA[ k ], {
  227. insertBefore: !contextAB.insertBefore,
  228. forceNotSticky: contextAB.forceNotSticky,
  229. isStrong: !contextAB.isStrong,
  230. forceWeakRemove: contextAB.forceWeakRemove,
  231. aWasUndone: contextAB.bWasUndone,
  232. bWasUndone: false
  233. } );
  234. if ( useAdditionalContext ) {
  235. _updateContext( deltaA[ k ], resultAB, contextAB );
  236. const originalDelta = contextAB.originalDelta.get( deltaB[ l ] );
  237. for ( const deltaBA of resultBA ) {
  238. contextAB.originalDelta.set( deltaBA, originalDelta );
  239. }
  240. }
  241. deltaA.splice( k, 1, ...resultAB );
  242. k += resultAB.length - 1;
  243. deltaB.splice( l, 1, ...resultBA );
  244. l += resultBA.length - 1;
  245. }
  246. }
  247. transformedDeltasB.splice( j, 1, ...deltaB );
  248. j += deltaB.length - 1;
  249. }
  250. transformedDeltasA.splice( i, 1, ...deltaA );
  251. i += deltaA.length - 1;
  252. }
  253. const opsDiffA = getOpsCount( transformedDeltasA ) - getOpsCount( deltasA );
  254. const opsDiffB = getOpsCount( transformedDeltasB ) - getOpsCount( deltasB );
  255. if ( opsDiffB < opsDiffA ) {
  256. padWithNoOps( transformedDeltasB, opsDiffA - opsDiffB );
  257. } else if ( opsDiffA < opsDiffB ) {
  258. padWithNoOps( transformedDeltasA, opsDiffB - opsDiffA );
  259. }
  260. return { deltasA: transformedDeltasA, deltasB: transformedDeltasB };
  261. }
  262. };
  263. export default transform;
  264. // Updates base versions of operations inside deltas (which are the results of delta transformation).
  265. function updateBaseVersion( baseVersion, deltas ) {
  266. for ( const delta of deltas ) {
  267. for ( const op of delta.operations ) {
  268. op.baseVersion = ++baseVersion;
  269. }
  270. }
  271. return deltas;
  272. }
  273. // Returns number of operations in given array of deltas.
  274. function getOpsCount( deltas ) {
  275. return deltas.reduce( ( current, delta ) => {
  276. return current + delta.operations.length;
  277. }, 0 );
  278. }
  279. // Adds a delta containing `howMany` `NoOperation` instances to given array with deltas.
  280. // Used to "synchronize" the number of operations in two delta sets.
  281. function padWithNoOps( deltas, howMany ) {
  282. const lastDelta = deltas[ deltas.length - 1 ];
  283. let baseVersion = lastDelta.operations.length + lastDelta.baseVersion;
  284. const noDelta = new Delta();
  285. for ( let i = 0; i < howMany; i++ ) {
  286. noDelta.addOperation( new NoOperation( baseVersion++ ) );
  287. }
  288. deltas.push( noDelta );
  289. }
  290. // Sets context data before delta `a` by delta `b` transformation.
  291. // Using data given in `context` object, sets `context.insertBefore` and `context.forceNotSticky` flags.
  292. // Also updates `context.wasAffected`.
  293. function _setContext( a, b, context ) {
  294. _setBWasUndone( b, context );
  295. _setWasAffected( a, b, context );
  296. _setInsertBeforeContext( a, b, context );
  297. _setForceWeakRemove( b, context );
  298. _setForceNotSticky( context );
  299. }
  300. // Sets `context.bWasUndone` basing on `context.document` history for `b` delta.
  301. //
  302. // `context.bWasUndone` is set to `true` if the (originally transformed) `b` delta was undone or was undoing delta.
  303. function _setBWasUndone( b, context ) {
  304. const originalDelta = context.originalDelta.get( b );
  305. const history = context.document.history;
  306. context.bWasUndone = history.isUndoneDelta( originalDelta ) || history.isUndoingDelta( originalDelta );
  307. }
  308. // Sets `context.insertBefore` basing on `context.document` history for `a` by `b` transformation.
  309. //
  310. // Simply saying, if `b` is "undoing delta" it means that `a` might already be transformed by the delta
  311. // which was undone by `b` (let's call it `oldB`). If this is true, `a` by `b` transformation has to consider
  312. // how `a` was transformed by `oldB` to get an expected result.
  313. //
  314. // This is used to resolve conflict when two operations want to insert nodes at the same position. If the operations
  315. // are not related, it doesn't matter in what order operations insert those nodes. However if the operations are
  316. // related (for example, in undo) we need to keep the same order.
  317. //
  318. // For example, assume that editor has two letters: 'ab'. Then, both letters are removed, creating two operations:
  319. // (op. 1) REM [ 1 ] - [ 2 ] => (graveyard) [ 0 ]
  320. // (op. 2) REM [ 0 ] - [ 1 ] => (graveyard) [ 1 ]
  321. // Then, we undo operation 2:
  322. // REM [ 0 ] - [ 1 ] => (graveyard) [ 1 ] is reversed to REI (graveyard) [ 1 ] => [ 0 ] - [ 1 ] and is applied.
  323. // History stack is:
  324. // (op. 1) REM [ 1 ] - [ 2 ] => (graveyard) [ 0 ]
  325. // (op. 2) REM [ 0 ] - [ 1 ] => (graveyard) [ 1 ]
  326. // (op. 3) REI (graveyard) [ 1 ] => [ 0 ] - [ 1 ]
  327. // Then, we undo operation 1:
  328. // REM [ 1 ] - [ 2 ] => (graveyard) [ 0 ] is reversed to REI (graveyard) [ 0 ] => [ 1 ] - [ 2 ] then,
  329. // is transformed by (op. 2) REM [ 0 ] - [ 1 ] => (graveyard) [ 1 ] and becomes REI (graveyard) [ 0 ] => [ 0 ] - [ 1 ] then,
  330. // is transformed by (op. 3) REI (graveyard) [ 1 ] => [ 0 ] - [ 1 ] and we have a conflict because both operations
  331. // insert at the same position, but thanks to keeping the context, we know that in this case, the transformed operation should
  332. // insert the node after operation 3.
  333. //
  334. // Keep in mind, that `context.insertBefore` may be either `Boolean` or `undefined`. If it is `Boolean` then the order is
  335. // known (deltas are related and `a` should insert nodes before or after `b`). However, if deltas were not related,
  336. // `context.isBefore` is `undefined` and other factors will be taken into consideration when resolving the order
  337. // (this, however, happens in operational transformation algorithms).
  338. //
  339. // This affects both `MoveOperation` (and its derivatives) and `InsertOperation`.
  340. function _setInsertBeforeContext( a, b, context ) {
  341. // If `b` is a delta that undoes other delta...
  342. const originalDelta = context.originalDelta.get( b );
  343. if ( context.document.history.isUndoingDelta( originalDelta ) ) {
  344. // Get the undone delta...
  345. const undoneDelta = context.document.history.getUndoneDelta( originalDelta );
  346. // Get a map with deltas related to `a` delta...
  347. const aWasAffectedBy = context.wasAffected.get( a );
  348. // And check if the undone delta is related with delta `a`.
  349. const affected = aWasAffectedBy.get( undoneDelta );
  350. if ( affected !== undefined ) {
  351. // If deltas are related, set `context.insertBefore` basing on whether `a` was affected by the undone delta.
  352. context.insertBefore = affected;
  353. }
  354. }
  355. }
  356. // Sets `context.forceNotSticky` basing on `context.document` history for transformation by `b` delta.
  357. //
  358. // `MoveOperation` may be "sticky" which means, that anything that was inserted at the boundary of moved range, should
  359. // also be moved. This is particularly helpful for actions like splitting or merging a node. However, this behavior
  360. // sometimes leads to an error, for example in undo.
  361. //
  362. // Simply saying, if delta is going to be transformed by delta `b`, stickiness should not be taken into consideration
  363. // if delta `b` was already undone or if delta `b` is an undoing delta.
  364. //
  365. // This affects `MoveOperation` (and its derivatives).
  366. function _setForceNotSticky( context ) {
  367. if ( context.bWasUndone ) {
  368. context.forceNotSticky = true;
  369. }
  370. }
  371. // Sets `context.forceWeakRemove` basing on `context.document` history for transformation by `b` delta.
  372. //
  373. // When additional context is not used, default `MoveOperation` x `RemoveOperation` transformation
  374. // always treats `RemoveOperation` as a stronger one, no matter how `context.isStrong` is set. It is like this
  375. // to provide better results when transformations happen.
  376. //
  377. // This, however, works fine only when additional context is not used.
  378. //
  379. // When additional context is used, we need a better way to decide whether `RemoveOperation` is "dominating" (or in other
  380. // words, whether nodes removed by given operation should stay in graveyard if other operation wants to move them).
  381. //
  382. // The answer to this is easy: if `RemoveOperation` has been already undone, we are not forcing given nodes to stay
  383. // in graveyard. In such scenario, we set `context.forceWeakRemove` to `true`. However, if the `RemoveOperation` has
  384. // not been undone, we set `context.forceWeakRemove` to `false` because we want the operation to be "dominating".
  385. function _setForceWeakRemove( b, context ) {
  386. const history = context.document.history;
  387. const originalB = context.originalDelta.get( b );
  388. // If `b` delta has not been undone yet, forceWeakRemove should be `false`.
  389. // It should be `true`, in any other case, if additional context is used.
  390. context.forceWeakRemove = history.isUndoneDelta( originalB );
  391. }
  392. // Sets `context.wasAffected` which holds context information about how transformed deltas are related. `context.wasAffected`
  393. // is used by `_setInsertBeforeContext` helper function.
  394. function _setWasAffected( a, b, context ) {
  395. if ( !context.wasAffected.get( a ) ) {
  396. // Create a new map with relations for `a` delta.
  397. context.wasAffected.set( a, new Map() );
  398. }
  399. const originalDelta = context.originalDelta.get( b );
  400. let wasAffected = !!context.wasAffected.get( a ).get( originalDelta );
  401. // Cross-check all operations from both deltas...
  402. for ( const opA of a.operations ) {
  403. for ( const opB of b.operations ) {
  404. if ( opA instanceof MoveOperation && opB instanceof MoveOperation ) {
  405. if ( _isOperationAffected( opA, opB ) ) {
  406. // If any of them are move operations that affect each other, set the relation accordingly.
  407. wasAffected = true;
  408. break;
  409. }
  410. }
  411. }
  412. // Break both loops if affecting pair has been found.
  413. if ( wasAffected ) {
  414. break;
  415. }
  416. }
  417. context.wasAffected.get( a ).set( originalDelta, wasAffected );
  418. }
  419. // Checks whether `opA` is affected by `opB`. It is assumed that both operations are `MoveOperation`.
  420. // Operation is affected only if the other operation's source range is before that operation's source range.
  421. function _isOperationAffected( opA, opB ) {
  422. const target = opA.targetPosition;
  423. const source = opB.sourcePosition;
  424. const cmpResult = compareArrays( source.getParentPath(), target.getParentPath() );
  425. if ( target.root != source.root ) {
  426. return false;
  427. }
  428. return cmpResult == 'same' && source.offset < target.offset;
  429. }
  430. // Updates `context` object after delta by delta transformation is done.
  431. //
  432. // This means two things:
  433. // 1. Some information are removed from context (those that apply only to the transformation that just happened).
  434. // 2. `context.wasAffected` is updated because `oldDelta` has been transformed to one or many `newDeltas` and we
  435. // need to update entries in `context.wasAffected`. Basically, anything that was in `context.wasAffected` under
  436. // `oldDelta` key should be rewritten to `newDeltas`. This way in next transformation steps, `newDeltas` "remember"
  437. // the context of `oldDelta`.
  438. function _updateContext( oldDelta, newDeltas, context ) {
  439. delete context.insertBefore;
  440. delete context.forceNotSticky;
  441. delete context.forceWeakRemove;
  442. const wasAffected = context.wasAffected.get( oldDelta );
  443. context.wasAffected.delete( oldDelta );
  444. for ( const delta of newDeltas ) {
  445. context.wasAffected.set( delta, new Map( wasAffected ) );
  446. }
  447. }
  448. // Takes base delta class (`DeltaClass`) and a set of `operations` that are transformation results and creates
  449. // one or more deltas, acknowledging that the result is a transformation of a delta that is of `DeltaClass`.
  450. //
  451. // The normalization ensures that each delta has it's "normal" state, that is, for example, `MoveDelta` has
  452. // just one `MoveOperation`, `SplitDelta` has just two operations of which first is `InsertOperation` and second
  453. // is `MoveOperation` or `NoOperation`, etc.
  454. function getNormalizedDeltas( DeltaClass, operations ) {
  455. let deltas = [];
  456. let delta = null;
  457. let attributeOperationIndex;
  458. switch ( DeltaClass ) {
  459. case MoveDelta:
  460. case RemoveDelta:
  461. // Normal MoveDelta has just one MoveOperation.
  462. // Take all operations and create MoveDelta for each of them.
  463. for ( const o of operations ) {
  464. if ( o instanceof NoOperation ) {
  465. // An operation may be instance of NoOperation and this may be correct.
  466. // If that's the case, do not create a MoveDelta with singular NoOperation.
  467. // Create "no delta" instead, that is Delta instance with NoOperation.
  468. delta = new Delta();
  469. } else {
  470. if ( o instanceof RemoveOperation ) {
  471. delta = new RemoveDelta();
  472. } else {
  473. delta = new MoveDelta();
  474. }
  475. // Unsticky the operation. Only operations in "special" deltas can be sticky.
  476. o.isSticky = false;
  477. }
  478. delta.addOperation( o );
  479. deltas.push( delta );
  480. }
  481. // Return all created MoveDeltas.
  482. return deltas;
  483. case SplitDelta:
  484. case WrapDelta:
  485. // Normal SplitDelta and WrapDelta have two operations: first is InsertOperation and second is MoveOperation.
  486. // The MoveOperation may be split into multiple MoveOperations.
  487. // If that's the case, convert additional MoveOperations into MoveDeltas.
  488. // First, create normal SplitDelta or WrapDelta, using first two operations.
  489. delta = new DeltaClass();
  490. delta.addOperation( operations[ 0 ] );
  491. delta.addOperation( operations[ 1 ] );
  492. // Then, take all but last two operations and use them to create normalized MoveDeltas.
  493. deltas = getNormalizedDeltas( MoveDelta, operations.slice( 2 ) );
  494. // Return all deltas as one array, in proper order.
  495. return [ delta ].concat( deltas );
  496. case MergeDelta:
  497. case UnwrapDelta:
  498. // Normal MergeDelta and UnwrapDelta have two operations: first is MoveOperation and second is RemoveOperation.
  499. // The MoveOperation may be split into multiple MoveOperations.
  500. // If that's the case, convert additional MoveOperations into MoveDeltas.
  501. // Take all but last two operations and use them to create normalized MoveDeltas.
  502. deltas = getNormalizedDeltas( MoveDelta, operations.slice( 0, -2 ) );
  503. // Then, create normal MergeDelta or UnwrapDelta, using last two operations.
  504. delta = new DeltaClass();
  505. delta.addOperation( operations[ operations.length - 2 ] );
  506. delta.addOperation( operations[ operations.length - 1 ] );
  507. // Return all deltas as one array, in proper order.
  508. return deltas.concat( delta );
  509. case RenameDelta:
  510. // RenameDelta may become a "no delta" if it's only operation is transformed to NoOperation.
  511. // This may happen when RenameOperation is transformed by RenameOperation.
  512. // Keep in mind that RenameDelta always have just one operation.
  513. if ( operations[ 0 ] instanceof NoOperation ) {
  514. delta = new Delta();
  515. } else {
  516. delta = new RenameDelta();
  517. }
  518. delta.addOperation( operations[ 0 ] );
  519. return [ delta ];
  520. case AttributeDelta:
  521. // AttributeDelta is allowed to have multiple AttributeOperations and also NoOperations but
  522. // the first operation has to be an AttributeOperation as it is used as a reference for deltas properties.
  523. // Keep in mind that we cannot simply remove NoOperations cause that would mess up base versions.
  524. // Find an index of first operation that is not a NoOperation.
  525. for ( attributeOperationIndex = 0; attributeOperationIndex < operations.length; attributeOperationIndex++ ) {
  526. if ( !( operations[ attributeOperationIndex ] instanceof NoOperation ) ) {
  527. break;
  528. }
  529. }
  530. // No AttributeOperations has been found. Convert AttributeDelta to "no delta".
  531. if ( attributeOperationIndex == operations.length ) {
  532. delta = new Delta();
  533. }
  534. // AttributeOperation found.
  535. else {
  536. delta = new AttributeDelta();
  537. // AttributeOperation wasn't the first operation.
  538. if ( attributeOperationIndex != 0 ) {
  539. // Move AttributeOperation to the beginning.
  540. operations.unshift( operations.splice( attributeOperationIndex, 1 )[ 0 ] );
  541. // No need to update base versions - they are updated at the end of transformation algorithm anyway.
  542. }
  543. }
  544. // Add all operations to the delta (even if it is just a couple of NoOperations we have to keep them all).
  545. for ( const o of operations ) {
  546. delta.addOperation( o );
  547. }
  548. return [ delta ];
  549. default:
  550. // For all other deltas no normalization is needed.
  551. delta = new DeltaClass();
  552. for ( const o of operations ) {
  553. delta.addOperation( o );
  554. }
  555. return [ delta ];
  556. }
  557. }
  558. /**
  559. * Object containing values and flags describing context of a transformation.
  560. *
  561. * @typedef {Object} module:engine/model/delta/transform~transformationContext
  562. * @property {Boolean} useAdditionalContext Whether additional context should be evaluated and used during transformations.
  563. * @property {Boolean} isStrong Whether transformed deltas are more (`true`) or less (`false`) important than deltas to transform by.
  564. * @property {module:engine/model/document~Document} [document] Model document which is a context for transformations.
  565. * Available only if `useAdditionalContext` is `true`.
  566. * @property {Boolean|undefined} forceWeakRemove Whether {@link module:engine/model/operation/removeoperation~RemoveOperation}
  567. * should be always more important than other operations. Available only if `useAdditionalContext` is `true`.
  568. * @property {Boolean|undefined} insertBefore Used when transforming {@link module:engine/model/operation/moveoperation~MoveOperation}s
  569. * If two `MoveOperation`s target to the same position, `insertBefore` is used to resolve such conflict. This flag
  570. * is set and used internally by transformation algorithms. Available only if `useAdditionalContext` is `true`.
  571. * @property {Boolean|undefined} forceNotSticky Used when transforming
  572. * {@link module:engine/model/operation/moveoperation~MoveOperation#isSticky sticky MoveOperation}. If set to `true`,
  573. * `isSticky` flag is discarded during transformations. This flag is set and used internally by transformation algorithms.
  574. * Available only if `useAdditionalContext` is `true`.
  575. * @property {Map|undefined} wasAffected Used to evaluate `insertBefore` flag. This map is set and used internally by
  576. * transformation algorithms. Available only if `useAdditionalContext` is `true`.
  577. */