transform.js 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509
  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 operationTransform from '../operation/transform';
  12. import NoOperation from '../operation/nooperation';
  13. import MoveOperation from '../operation/moveoperation';
  14. import arrayUtils from '@ckeditor/ckeditor5-utils/src/lib/lodash/array';
  15. import compareArrays from '@ckeditor/ckeditor5-utils/src/comparearrays';
  16. const specialCases = new Map();
  17. /**
  18. * @namespace
  19. */
  20. const transform = {
  21. /**
  22. * Transforms given {@link module:engine/model/delta/delta~Delta delta} by another {@link module:engine/model/delta/delta~Delta delta}
  23. * and returns the result of that transformation as an array containing one or more {@link module:engine/model/delta/delta~Delta delta}
  24. * instances.
  25. *
  26. * Delta transformations heavily base on {@link module:engine/model/operation/transform~transform operational transformations}. Since
  27. * delta is a list of operations most situations can be handled thanks to operational transformation. Unfortunately,
  28. * deltas are more complicated than operations and have they semantic meaning, as they represent user's editing intentions.
  29. *
  30. * Sometimes, simple operational transformation on deltas' operations might result in some unexpected results. Those
  31. * results would be fine from OT point of view, but would not reflect user's intentions. Because of such conflicts
  32. * we need to handle transformations in special cases in a custom way.
  33. *
  34. * The function itself looks whether two given delta types have a special case function registered. If so, the deltas are
  35. * transformed using that function. If not,
  36. * {@link module:engine/model/delta/transform~transform.defaultTransform default transformation algorithm} is used.
  37. *
  38. * @param {module:engine/model/delta/delta~Delta} a Delta that will be transformed.
  39. * @param {module:engine/model/delta/delta~Delta} b Delta to transform by.
  40. * @param {module:engine/model/delta/transform~transformationContext} context Transformation context object.
  41. * @returns {Array.<module:engine/model/delta/delta~Delta>} Result of the transformation.
  42. */
  43. transform( a, b, context ) {
  44. if ( context.useAdditionalContext ) {
  45. _setContext( a, b, context );
  46. }
  47. const transformAlgorithm = transform.getTransformationCase( a, b ) || transform.defaultTransform;
  48. // Make new instance of context object, so all changes done during transformation are not saved in original object.
  49. const transformed = transformAlgorithm( a, b, Object.assign( {}, context ) );
  50. const baseVersion = arrayUtils.last( b.operations ).baseVersion;
  51. if ( context.useAdditionalContext ) {
  52. _updateContext( a, transformed, context );
  53. }
  54. return updateBaseVersion( baseVersion, transformed );
  55. },
  56. /**
  57. * The default delta transformation function. It is used for those deltas that are not in special case conflict.
  58. *
  59. * This algorithm is similar to a popular `dOPT` algorithm used in operational transformation, as we are in fact
  60. * transforming two sets of operations by each other.
  61. *
  62. * @param {module:engine/model/delta/delta~Delta} a Delta that will be transformed.
  63. * @param {module:engine/model/delta/delta~Delta} b Delta to transform by.
  64. * @param {module:engine/model/delta/transform~transformationContext} context Transformation context object.
  65. * @returns {Array.<module:engine/model/delta/delta~Delta>} Result of the transformation, that is an array with single delta instance.
  66. */
  67. defaultTransform( a, b, context ) {
  68. // Create a new delta instance. Make sure that the new delta is of same type as transformed delta.
  69. // We will transform operations in that delta but it doesn't mean the delta's "meaning" which is connected to
  70. // the delta's type. Since the delta's type is heavily used in transformations and probably other parts
  71. // of system it is important to keep proper delta type through all transformation process.
  72. const transformed = new a.constructor();
  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.addOperation( 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. // If `MoveDelta` or `RemoveDelta` operation got split, instead of returning one delta with multiple operations,
  138. // return multiple deltas with single operation each.
  139. if ( transformed instanceof MoveDelta && transformed.operations.length > 1 ) {
  140. const result = [];
  141. for ( const operation of transformed.operations ) {
  142. const delta = new a.constructor();
  143. delta.addOperation( operation );
  144. result.push( delta );
  145. }
  146. return result;
  147. } else {
  148. return [ transformed ];
  149. }
  150. },
  151. /**
  152. * Adds a special case callback for given delta classes.
  153. *
  154. * @param {Function} A Delta constructor which instance will get transformed.
  155. * @param {Function} B Delta constructor which instance will be transformed by.
  156. * @param {Function} resolver A callback that will handle custom special case transformation for instances of given delta classes.
  157. */
  158. addTransformationCase( A, B, resolver ) {
  159. let casesA = specialCases.get( A );
  160. if ( !casesA ) {
  161. casesA = new Map();
  162. specialCases.set( A, casesA );
  163. }
  164. casesA.set( B, resolver );
  165. },
  166. /**
  167. * Gets a special case callback which was previously {@link module:engine/model/delta/transform~transform.addTransformationCase added}.
  168. *
  169. * @param {module:engine/model/delta/delta~Delta} a Delta to transform.
  170. * @param {module:engine/model/delta/delta~Delta} b Delta to be transformed by.
  171. */
  172. getTransformationCase( a, b ) {
  173. let casesA = specialCases.get( a.constructor );
  174. // If there are no special cases registered for class which `a` is instance of, we will
  175. // check if there are special cases registered for any parent class.
  176. if ( !casesA || !casesA.get( b.constructor ) ) {
  177. const cases = specialCases.keys();
  178. for ( const caseClass of cases ) {
  179. if ( a instanceof caseClass && specialCases.get( caseClass ).get( b.constructor ) ) {
  180. casesA = specialCases.get( caseClass );
  181. break;
  182. }
  183. }
  184. }
  185. if ( casesA ) {
  186. return casesA.get( b.constructor );
  187. }
  188. return undefined;
  189. },
  190. /**
  191. * Transforms two sets of deltas by themselves. Returns both transformed sets.
  192. *
  193. * @param {Array.<module:engine/model/delta/delta~Delta>} deltasA Array with the first set of deltas to transform. These
  194. * deltas are considered more important (than `deltasB`) when resolving conflicts.
  195. * @param {Array.<module:engine/model/delta/delta~Delta>} deltasB Array with the second set of deltas to transform. These
  196. * deltas are considered less important (than `deltasA`) when resolving conflicts.
  197. * @param {module:engine/model/document~Document} [document=null] If set, deltas will be transformed in "context mode"
  198. * and given `document` will be used to determine relations between deltas. If not set (default), deltas will be
  199. * transforming without additional context information.
  200. * @returns {Object}
  201. * @returns {Array.<module:engine/model/delta/delta~Delta>} return.deltasA The first set of deltas transformed
  202. * by the second set of deltas.
  203. * @returns {Array.<module:engine/model/delta/delta~Delta>} return.deltasB The second set of deltas transformed
  204. * by the first set of deltas.
  205. */
  206. transformDeltaSets( deltasA, deltasB, document = null ) {
  207. const transformedDeltasA = Array.from( deltasA );
  208. const transformedDeltasB = Array.from( deltasB );
  209. const useAdditionalContext = document !== null;
  210. const contextAB = {
  211. isStrong: true,
  212. useAdditionalContext
  213. };
  214. const contextBA = {
  215. isStrong: false,
  216. useAdditionalContext
  217. };
  218. if ( useAdditionalContext ) {
  219. const additionalContext = {
  220. forceWeakRemove: true,
  221. document
  222. };
  223. // We need two different instances for `wasAffected` property.
  224. Object.assign( contextAB, { wasAffected: new Map() }, additionalContext );
  225. Object.assign( contextBA, { wasAffected: new Map() }, additionalContext );
  226. }
  227. for ( let i = 0; i < transformedDeltasA.length; i++ ) {
  228. const deltaA = [ transformedDeltasA[ i ] ];
  229. for ( let j = 0; j < transformedDeltasB.length; j++ ) {
  230. const deltaB = [ transformedDeltasB[ j ] ];
  231. for ( let k = 0; k < deltaA.length; k++ ) {
  232. for ( let l = 0; l < deltaB.length; l++ ) {
  233. const resultAB = transform.transform( deltaA[ k ], deltaB[ l ], contextAB );
  234. const resultBA = transform.transform( deltaB[ l ], deltaA[ k ], contextBA );
  235. deltaA.splice( k, 1, ...resultAB );
  236. k += resultAB.length - 1;
  237. deltaB.splice( l, 1, ...resultBA );
  238. l += resultBA.length - 1;
  239. }
  240. }
  241. transformedDeltasB.splice( j, 1, ...deltaB );
  242. j += deltaB.length - 1;
  243. }
  244. transformedDeltasA.splice( i, 1, ...deltaA );
  245. i += deltaA.length - 1;
  246. }
  247. const opsDiffA = getOpsCount( transformedDeltasA ) - getOpsCount( deltasA );
  248. const opsDiffB = getOpsCount( transformedDeltasB ) - getOpsCount( deltasB );
  249. if ( opsDiffB < opsDiffA ) {
  250. padWithNoOps( transformedDeltasB, opsDiffA - opsDiffB );
  251. } else if ( opsDiffA < opsDiffB ) {
  252. padWithNoOps( transformedDeltasA, opsDiffB - opsDiffA );
  253. }
  254. return { deltasA: transformedDeltasA, deltasB: transformedDeltasB };
  255. }
  256. };
  257. export default transform;
  258. // Updates base versions of operations inside deltas (which are the results of delta transformation).
  259. function updateBaseVersion( baseVersion, deltas ) {
  260. for ( const delta of deltas ) {
  261. for ( const op of delta.operations ) {
  262. op.baseVersion = ++baseVersion;
  263. }
  264. }
  265. return deltas;
  266. }
  267. // Returns number of operations in given array of deltas.
  268. function getOpsCount( deltas ) {
  269. return deltas.reduce( ( current, delta ) => {
  270. return current + delta.operations.length;
  271. }, 0 );
  272. }
  273. // Adds a delta containing `howMany` `NoOperation` instances to given array with deltas.
  274. // Used to "synchronize" the number of operations in two delta sets.
  275. function padWithNoOps( deltas, howMany ) {
  276. const lastDelta = deltas[ deltas.length - 1 ];
  277. let baseVersion = lastDelta.operations.length + lastDelta.baseVersion;
  278. const noDelta = new Delta();
  279. for ( let i = 0; i < howMany; i++ ) {
  280. noDelta.addOperation( new NoOperation( baseVersion++ ) );
  281. }
  282. deltas.push( noDelta );
  283. }
  284. // Sets context data before delta `a` by delta `b` transformation.
  285. // Using data given in `context` object, sets `context.insertBefore` and `context.forceNotSticky` flags.
  286. // Also updates `context.wasAffected`.
  287. function _setContext( a, b, context ) {
  288. _setWasAffected( a, b, context );
  289. _setInsertBeforeContext( a, b, context );
  290. _setForceNotSticky( b, context );
  291. }
  292. // Sets `context.insertBefore` basing on `context.document` history for `a` by `b` transformation.
  293. //
  294. // Simply saying, if `b` is "undoing delta" it means that `a` might already be transformed by the delta
  295. // which was undone by `b` (let's call it `oldB`). If this is true, `a` by `b` transformation has to consider
  296. // how `a` was transformed by `oldB` to get an expected result.
  297. //
  298. // This is used to resolve conflict when two operations want to insert nodes at the same position. If the operations
  299. // are not related, it doesn't matter in what order operations insert those nodes. However if the operations are
  300. // related (for example, in undo) we need to keep the same order.
  301. //
  302. // For example, assume that editor has two letters: 'ab'. Then, both letters are removed, creating two operations:
  303. // (op. 1) REM [ 1 ] - [ 2 ] => (graveyard) [ 0 ]
  304. // (op. 2) REM [ 0 ] - [ 1 ] => (graveyard) [ 1 ]
  305. // Then, we undo operation 2:
  306. // REM [ 0 ] - [ 1 ] => (graveyard) [ 1 ] is reversed to REI (graveyard) [ 1 ] => [ 0 ] - [ 1 ] and is applied.
  307. // History stack is:
  308. // (op. 1) REM [ 1 ] - [ 2 ] => (graveyard) [ 0 ]
  309. // (op. 2) REM [ 0 ] - [ 1 ] => (graveyard) [ 1 ]
  310. // (op. 3) REI (graveyard) [ 1 ] => [ 0 ] - [ 1 ]
  311. // Then, we undo operation 1:
  312. // REM [ 1 ] - [ 2 ] => (graveyard) [ 0 ] is reversed to REI (graveyard) [ 0 ] => [ 1 ] - [ 2 ] then,
  313. // is transformed by (op. 2) REM [ 0 ] - [ 1 ] => (graveyard) [ 1 ] and becomes REI (graveyard) [ 0 ] => [ 0 ] - [ 1 ] then,
  314. // is transformed by (op. 3) REI (graveyard) [ 1 ] => [ 0 ] - [ 1 ] and we have a conflict because both operations
  315. // insert at the same position, but thanks to keeping the context, we know that in this case, the transformed operation should
  316. // insert the node after operation 3.
  317. //
  318. // Keep in mind, that `context.insertBefore` may be either `Boolean` or `undefined`. If it is `Boolean` then the order is
  319. // known (deltas are related and `a` should insert nodes before or after `b`). However, if deltas were not related,
  320. // `context.isBefore` is `undefined` and other factors will be taken into consideration when resolving the order
  321. // (this, however, happens in operational transformation algorithms).
  322. //
  323. // Keep in mind that this problem only affects `MoveOperation` (and operations that derive from it).
  324. function _setInsertBeforeContext( a, b, context ) {
  325. // If `b` is a delta that undoes other delta...
  326. if ( context.document.history.isUndoingDelta( b ) ) {
  327. // Get the undone delta...
  328. const undoneDelta = context.document.history.getUndoneDelta( b );
  329. // Get a map with deltas related to `a` delta...
  330. const aWasAffectedBy = context.wasAffected.get( a );
  331. // And check if the undone delta is related with delta `a`.
  332. const affected = aWasAffectedBy.get( undoneDelta );
  333. if ( affected !== undefined ) {
  334. // If deltas are related, set `context.insertBefore` basing on whether `a` was affected by the undone delta.
  335. context.insertBefore = affected;
  336. }
  337. }
  338. }
  339. // Sets `context.forceNotSticky` basing on `context.document` history for transformation by `b` delta.
  340. //
  341. // `MoveOperation` may be "sticky" which means, that anything that was inserted at the boundary of moved range, should
  342. // also be moved. This is particularly helpful for actions like splitting or merging a node. However, this behavior
  343. // sometimes leads to an error, for example in undo.
  344. //
  345. // Simply saying, if delta is going to be transformed by delta `b`, stickiness should not be taken into consideration
  346. // if delta `b` was already undone or if delta `b` is an undoing delta.
  347. //
  348. // Keep in mind that this problem only affects `MoveOperation` (and operations that derive from it).
  349. function _setForceNotSticky( b, context ) {
  350. // If `b` delta is undoing or undone delta, stickiness should not be taken into consideration.
  351. if ( context.document.history.isUndoingDelta( b ) || context.document.history.isUndoneDelta( b ) ) {
  352. context.forceNotSticky = true;
  353. }
  354. }
  355. // Sets `context.wasAffected` which holds context information about how transformed deltas are related. `context.wasAffected`
  356. // is used by `_setInsertBeforeContext` helper function.
  357. function _setWasAffected( a, b, context ) {
  358. if ( !context.wasAffected.get( a ) ) {
  359. // Create a new map with relations for `a` delta.
  360. context.wasAffected.set( a, new Map() );
  361. }
  362. let wasAffected = false;
  363. // Cross-check all operations from both deltas...
  364. for ( const opA of a.operations ) {
  365. for ( const opB of b.operations ) {
  366. if ( opA instanceof MoveOperation && opB instanceof MoveOperation ) {
  367. if ( _isOperationAffected( opA, opB ) ) {
  368. // If any of them are move operations that affect each other, set the relation accordingly.
  369. wasAffected = true;
  370. break;
  371. }
  372. }
  373. }
  374. // Break both loops if affecting pair has been found.
  375. if ( wasAffected ) {
  376. break;
  377. }
  378. }
  379. context.wasAffected.get( a ).set( b, wasAffected );
  380. }
  381. // Checks whether `opA` is affected by `opB`. It is assumed that both operations are `MoveOperation`.
  382. // Operation is affected only if the other operation's source range is before that operation's source range.
  383. function _isOperationAffected( opA, opB ) {
  384. const target = opA.targetPosition;
  385. const source = opB.sourcePosition;
  386. const cmpResult = compareArrays( source.getParentPath(), target.getParentPath() );
  387. if ( target.root != source.root ) {
  388. return false;
  389. }
  390. return cmpResult == 'same' && source.offset < target.offset;
  391. }
  392. // Updates `context` object after delta by delta transformation is done.
  393. //
  394. // This means two things:
  395. // 1. Some information are removed from context (those that apply only to the transformation that just happened).
  396. // 2. `context.wasAffected` is updated because `oldDelta` has been transformed to one or many `newDeltas` and we
  397. // need to update entries in `context.wasAffected`. Basically, anything that was in `context.wasAffected` under
  398. // `oldDelta` key should be rewritten to `newDeltas`. This way in next transformation steps, `newDeltas` "remember"
  399. // the context of `oldDelta`.
  400. function _updateContext( oldDelta, newDeltas, context ) {
  401. delete context.insertBefore;
  402. delete context.forceNotSticky;
  403. const wasAffected = context.wasAffected.get( oldDelta );
  404. context.wasAffected.delete( oldDelta );
  405. for ( const delta of newDeltas ) {
  406. context.wasAffected.set( delta, new Map( wasAffected ) );
  407. }
  408. }
  409. /**
  410. * Object containing values and flags describing context of a transformation.
  411. *
  412. * @typedef {Object} module:engine/model/delta/transform~transformationContext
  413. * @property {Boolean} useAdditionalContext Whether additional context should be evaluated and used during transformations.
  414. * @property {Boolean} isStrong Whether transformed deltas are more (`true`) or less (`false`) important than deltas to transform by.
  415. * @property {module:engine/model/document~Document} [document] Model document which is a context for transformations.
  416. * Available only if `useAdditionalContext` is `true`.
  417. * @property {Boolean|undefined} forceWeakRemove Whether {@link module:engine/model/operation/removeoperation~RemoveOperation}
  418. * should be always more important than other operations. Available only if `useAdditionalContext` is `true`.
  419. * @property {Boolean|undefined} insertBefore Used when transforming {@link module:engine/model/operation/moveoperation~MoveOperation}s
  420. * If two `MoveOperation`s target to the same position, `insertBefore` is used to resolve such conflict. This flag
  421. * is set and used internally by transformation algorithms. Available only if `useAdditionalContext` is `true`.
  422. * @property {Boolean|undefined} forceNotSticky Used when transforming
  423. * {@link module:engine/model/operation/moveoperation~MoveOperation#isSticky sticky MoveOperation}. If set to `true`,
  424. * `isSticky` flag is discarded during transformations. This flag is set and used internally by transformation algorithms.
  425. * Available only if `useAdditionalContext` is `true`.
  426. * @property {Map|undefined} wasAffected Used to evaluate `insertBefore` flag. This map is set and used internally by
  427. * transformation algorithms. Available only if `useAdditionalContext` is `true`.
  428. */