transform.js 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307
  1. /**
  2. * @license Copyright (c) 2003-2017, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. /**
  6. * @module engine/model/delta/transform
  7. */
  8. import Delta from './delta';
  9. import operationTransform from '../operation/transform';
  10. import NoOperation from '../operation/nooperation';
  11. import arrayUtils from '@ckeditor/ckeditor5-utils/src/lib/lodash/array';
  12. const specialCases = new Map();
  13. const deltaTransform = {
  14. transform,
  15. defaultTransform,
  16. addTransformationCase,
  17. getTransformationCase,
  18. transformDeltaSets
  19. };
  20. export default deltaTransform;
  21. /**
  22. * Transforms given {@link module:engine/model/delta/delta~Delta delta} by another {@link module:engine/model/delta/delta~Delta delta} and
  23. * 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, {@link module:engine/model/delta/transform~defaultTransform default transformation algorithm}
  36. * 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 {Boolean} isAMoreImportantThanB Flag indicating whether the delta which will be transformed (`a`) should be treated
  41. * as more important when resolving conflicts. Note that this flag is used only if provided deltas have same
  42. * {@link module:engine/model/delta/delta~Delta._priority priority}. If deltas have different priorities, their importance is resolved
  43. * automatically and overwrites this flag.
  44. * @returns {Array.<module:engine/model/delta/delta~Delta>} Result of the transformation.
  45. */
  46. function transform( a, b, isAMoreImportantThanB ) {
  47. const transformAlgorithm = getTransformationCase( a, b ) || defaultTransform;
  48. const transformed = transformAlgorithm( a, b, isAMoreImportantThanB );
  49. const baseVersion = arrayUtils.last( b.operations ).baseVersion;
  50. return updateBaseVersion( baseVersion, transformed );
  51. }
  52. // Updates base versions of operations inside deltas (which are the results of delta transformation).
  53. function updateBaseVersion( baseVersion, deltas ) {
  54. for ( let delta of deltas ) {
  55. for ( let op of delta.operations ) {
  56. op.baseVersion = ++baseVersion;
  57. }
  58. }
  59. return deltas;
  60. }
  61. /**
  62. * The default delta transformation function. It is used for those deltas that are not in special case conflict.
  63. *
  64. * This algorithm is similar to a popular `dOPT` algorithm used in operational transformation, as we are in fact
  65. * transforming two sets of operations by each other.
  66. *
  67. * @param {module:engine/model/delta/delta~Delta} a Delta that will be transformed.
  68. * @param {module:engine/model/delta/delta~Delta} b Delta to transform by.
  69. * @param {Boolean} isAMoreImportantThanB Flag indicating whether the delta which will be transformed (`a`) should be treated
  70. * as more important when resolving conflicts. Note that this flag is used only if provided deltas have same
  71. * {@link module:engine/model/delta/delta~Delta._priority priority}. If deltas have different priorities, their importance is resolved
  72. * automatically and overwrites this flag.
  73. * @returns {Array.<module:engine/model/delta/delta~Delta>} Result of the transformation, that is an array with single delta instance.
  74. */
  75. function defaultTransform( a, b, isAMoreImportantThanB ) {
  76. // First, resolve the flag real value.
  77. isAMoreImportantThanB = getPriority( a.constructor, b.constructor, isAMoreImportantThanB );
  78. // Create a new delta instance. Make sure that the new delta is of same type as transformed delta.
  79. // We will transform operations in that delta but it doesn't mean the delta's "meaning" which is connected to
  80. // the delta's type. Since the delta's type is heavily used in transformations and probably other parts
  81. // of system it is important to keep proper delta type through all transformation process.
  82. const transformed = new a.constructor();
  83. // Array containing operations that we will transform by. At the beginning these are just operations from
  84. let byOps = b.operations;
  85. // This array is storing operations from `byOps` which got transformed by operation from delta `a`.
  86. let newByOps = [];
  87. // We take each operation from original set of operations to transform.
  88. for ( let opA of a.operations ) {
  89. // We wrap the operation in the array. This is important, because operation transformation algorithm returns
  90. // an array of operations so we need to make sure that our algorithm is ready to handle arrays.
  91. const ops = [ opA ];
  92. // Now the real algorithm takes place.
  93. for ( let opB of byOps ) {
  94. // For each operation that we need transform by...
  95. for ( let i = 0; i < ops.length; i++ ) {
  96. // We take each operation to transform...
  97. const op = ops[ i ];
  98. // And transform both of them by themselves.
  99. // The result of transforming operation from delta B by operation from delta A is saved in
  100. // `newByOps` array. We will use that array for transformations in next loops. We need delta B
  101. // operations after transformed by delta A operations to get correct results of transformations
  102. // of next operations from delta A.
  103. //
  104. // It's like this because 2nd operation from delta A assumes that 1st operation from delta A
  105. // is "already applied". When we transform 2nd operation from delta A by operations from delta B
  106. // we have to be sure that operations from delta B are in a state that acknowledges 1st operation
  107. // from delta A.
  108. //
  109. // This can be easier understood when operations sets to transform are represented by diamond diagrams:
  110. // http://www.codecommit.com/blog/java/understanding-and-applying-operational-transformation
  111. // Using push.apply because operationTransform function is returning an array with one or multiple results.
  112. Array.prototype.push.apply( newByOps, operationTransform( opB, op, !isAMoreImportantThanB ) );
  113. // Then, we transform operation from delta A by operation from delta B.
  114. const results = operationTransform( op, opB, isAMoreImportantThanB );
  115. // We replace currently processed operation from `ops` array by the results of transformation.
  116. // Note, that we process single operation but the operationTransform result might be an array, so we
  117. // might splice-in more operations. We will process them further in next iterations. Right now we
  118. // just save them in `ops` array and move `i` pointer by proper offset.
  119. Array.prototype.splice.apply( ops, [ i, 1 ].concat( results ) );
  120. i += results.length - 1;
  121. }
  122. // At this point a single operation from delta A got transformed by a single operation from delta B.
  123. // The transformation result is in `ops` array and it may be one or more operations. This was just the first step.
  124. // Operation from delta A has to be further transformed by the other operations from delta B.
  125. // So in next iterator loop we will take another operation from delta B and use transformed delta A (`ops`)
  126. // to transform it further.
  127. }
  128. // We got through all delta B operations and have a final transformed state of an operation from delta A.
  129. // As previously mentioned, we substitute operations from delta B by their transformed equivalents.
  130. byOps = newByOps;
  131. newByOps = [];
  132. // We add transformed operation from delta A to newly created delta.
  133. // Remember that transformed operation from delta A may consist of multiple operations.
  134. for ( let op of ops ) {
  135. transformed.addOperation( op );
  136. }
  137. // In next loop, we will take another operation from delta A and transform it through (transformed) operations
  138. // from delta B...
  139. }
  140. return [ transformed ];
  141. }
  142. /**
  143. * Adds a special case callback for given delta classes.
  144. *
  145. * @external module:engine/model/delta/transform~transform
  146. * @function module:engine/model/delta/transform~transform.addTransformationCase
  147. * @param {Function} A Delta constructor which instance will get transformed.
  148. * @param {Function} B Delta constructor which instance will be transformed by.
  149. * @param {Function} resolver A callback that will handle custom special case transformation for instances of given delta classes.
  150. */
  151. function addTransformationCase( A, B, resolver ) {
  152. let casesA = specialCases.get( A );
  153. if ( !casesA ) {
  154. casesA = new Map();
  155. specialCases.set( A, casesA );
  156. }
  157. casesA.set( B, resolver );
  158. }
  159. /**
  160. * Gets a special case callback which was previously {@link module:engine/model/delta/transform~transform.addTransformationCase added}.
  161. *
  162. * @param {module:engine/model/delta/delta~Delta} a Delta to transform.
  163. * @param {module:engine/model/delta/delta~Delta} b Delta to be transformed by.
  164. */
  165. function getTransformationCase( a, b ) {
  166. let casesA = specialCases.get( a.constructor );
  167. // If there are no special cases registered for class which `a` is instance of, we will
  168. // check if there are special cases registered for any parent class.
  169. if ( !casesA || !casesA.get( b.constructor ) ) {
  170. const cases = specialCases.keys();
  171. for ( let caseClass of cases ) {
  172. if ( a instanceof caseClass && specialCases.get( caseClass ).get( b.constructor ) ) {
  173. casesA = specialCases.get( caseClass );
  174. break;
  175. }
  176. }
  177. }
  178. if ( casesA ) {
  179. return casesA.get( b.constructor );
  180. }
  181. return undefined;
  182. }
  183. // Checks priorities of passed constructors and decides which one is more important.
  184. // If both priorities are same, value passed in `isAMoreImportantThanB` parameter is used.
  185. function getPriority( A, B, isAMoreImportantThanB ) {
  186. if ( A._priority > B._priority ) {
  187. return true;
  188. } else if ( A._priority < B._priority ) {
  189. return false;
  190. } else {
  191. return isAMoreImportantThanB;
  192. }
  193. }
  194. /**
  195. * Transforms two sets of deltas by themselves. Returns both transformed sets. Does not modify passed parameters.
  196. *
  197. * @param {Array.<module:engine/model/delta/delta~Delta>} deltasA Array with first set of deltas to transform.
  198. * @param {Array.<module:engine/model/delta/delta~Delta>} deltasB Array with second set of deltas to transform.
  199. * @param {Boolean} isAMoreImportantThanB Flag indicating whether the deltas from `deltasA` set should be treated as more
  200. * important when resolving conflicts.
  201. * @returns {Object}
  202. * @returns {Array.<module:engine/model/delta/delta~Delta>} return.deltasA The first set of deltas transformed by the second set of deltas.
  203. * @returns {Array.<module:engine/model/delta/delta~Delta>} return.deltasB The second set of deltas transformed by the first set of deltas.
  204. */
  205. function transformDeltaSets( deltasA, deltasB, isAMoreImportantThanB ) {
  206. let transformedDeltasA = Array.from( deltasA );
  207. let transformedDeltasB = Array.from( deltasB );
  208. for ( let i = 0; i < transformedDeltasA.length; i++ ) {
  209. let deltaA = [ transformedDeltasA[ i ] ];
  210. for ( let j = 0; j < transformedDeltasB.length; j++ ) {
  211. let deltaB = [ transformedDeltasB[ j ] ];
  212. for ( let k = 0; k < deltaA.length; k++ ) {
  213. for ( let l = 0; l < deltaB.length; l++ ) {
  214. let resultAB = transform( deltaA[ k ], deltaB[ l ], isAMoreImportantThanB );
  215. let resultBA = transform( deltaB[ l ], deltaA[ k ], !isAMoreImportantThanB );
  216. deltaA.splice( k, 1, ...resultAB );
  217. k += resultAB.length - 1;
  218. deltaB.splice( l, 1, ...resultBA );
  219. l += resultBA.length - 1;
  220. }
  221. }
  222. transformedDeltasB.splice( j, 1, ...deltaB );
  223. j += deltaB.length - 1;
  224. }
  225. transformedDeltasA.splice( i, 1, ...deltaA );
  226. i += deltaA.length - 1;
  227. }
  228. const opsDiffA = getOpsCount( transformedDeltasA ) - getOpsCount( deltasA );
  229. const opsDiffB = getOpsCount( transformedDeltasB ) - getOpsCount( deltasB );
  230. if ( opsDiffB < opsDiffA ) {
  231. padWithNoOps( transformedDeltasB, opsDiffA - opsDiffB );
  232. } else if ( opsDiffA < opsDiffB ) {
  233. padWithNoOps( transformedDeltasA, opsDiffB - opsDiffA );
  234. }
  235. return { deltasA: transformedDeltasA, deltasB: transformedDeltasB };
  236. }
  237. // Returns number of operations in given array of deltas.
  238. function getOpsCount( deltas ) {
  239. return deltas.reduce( ( current, delta ) => {
  240. return current + delta.operations.length;
  241. }, 0 );
  242. }
  243. // Adds a delta containing `howMany` `NoOperation` instances to given array with deltas.
  244. // Used to "synchronize" the number of operations in two delta sets.
  245. function padWithNoOps( deltas, howMany ) {
  246. const lastDelta = deltas[ deltas.length - 1 ];
  247. let baseVersion = lastDelta.operations.length + lastDelta.baseVersion;
  248. let noDelta = new Delta();
  249. for ( let i = 0; i < howMany; i++ ) {
  250. noDelta.addOperation( new NoOperation( baseVersion++ ) );
  251. }
  252. deltas.push( noDelta );
  253. }