transform.js 9.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221
  1. /**
  2. * @license Copyright (c) 2003-2016, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. 'use strict';
  6. import operationTransform from '../operation/transform.js';
  7. import arrayUtils from '../../lib/lodash/array.js';
  8. const specialCases = new Map();
  9. /**
  10. * Transforms given {@link core.treeModel.delta.Delta delta} by another {@link core.treeModel.delta.Delta delta} and
  11. * returns the result of that transformation as an array containing one or more {@link core.treeModel.delta.Delta delta}
  12. * instances.
  13. *
  14. * Delta transformations heavily base on {@link core.treeModel.operation.transform operational transformations}. Since
  15. * delta is a list of operations most situations can be handled thanks to operational transformation. Unfortunately,
  16. * deltas are more complicated than operations and have they semantic meaning, as they represent user's editing intentions.
  17. *
  18. * Sometimes, simple operational transformation on deltas' operations might result in some unexpected results. Those
  19. * results would be fine from OT point of view, but would not reflect user's intentions. Because of such conflicts
  20. * we need to handle transformations in special cases in a custom way.
  21. *
  22. * The function itself looks whether two given delta types have a special case function registered. If so, the deltas are
  23. * transformed using that function. If not, {@link core.treeModel.delta.defaultTransform default transformation algorithm}
  24. * is used.
  25. *
  26. * @see core.treeModel.operation.transform
  27. *
  28. * @external core.treeModel.delta.transform
  29. * @function core.treeModel.delta.transform.transform
  30. * @param {core.treeModel.delta.Delta} a Delta that will be transformed.
  31. * @param {core.treeModel.delta.Delta} b Delta to transform by.
  32. * @param {Boolean} isAMoreImportantThanB Flag indicating whether the delta which will be transformed (`a`) should be treated
  33. * as more important when resolving conflicts. Note that this flag is used only if provided deltas have same
  34. * {@link core.treeModel.delta.priorities priority}. If deltas have different priorities, their importance is resolved
  35. * automatically and overwrites this flag.
  36. * @returns {Array.<core.treeModel.delta.Delta>} Result of the transformation.
  37. */
  38. export default function transform( a, b, isAMoreImportantThanB ) {
  39. const transformAlgorithm = getTransformationCase( a, b ) || defaultTransform;
  40. const transformed = transformAlgorithm( a, b, isAMoreImportantThanB );
  41. const baseVersion = arrayUtils.last( b.operations ).baseVersion;
  42. return updateBaseVersion( baseVersion, transformed );
  43. }
  44. // Updates base versions of operations inside deltas (which are the results of delta transformation).
  45. function updateBaseVersion( baseVersion, deltas ) {
  46. for ( let delta of deltas ) {
  47. for ( let op of delta.operations ) {
  48. op.baseVersion = ++baseVersion;
  49. }
  50. }
  51. return deltas;
  52. }
  53. /**
  54. * The default delta transformation function. It is used for those deltas that are not in special case conflict.
  55. *
  56. * This algorithm is similar to popular `dOPT` algorithm used in operational transformation, as we are in fact
  57. * transforming two sets of operations by each other.
  58. *
  59. * @param {core.treeModel.delta.Delta} a Delta that will be transformed.
  60. * @param {core.treeModel.delta.Delta} b Delta to transform by.
  61. * @param {Boolean} isAMoreImportantThanB Flag indicating whether the delta which will be transformed (`a`) should be treated
  62. * as more important when resolving conflicts. Note that this flag is used only if provided deltas have same
  63. * {@link core.treeModel.delta.priorities priority}. If deltas have different priorities, their importance is resolved
  64. * automatically and overwrites this flag.
  65. * @returns {Array.<core.treeModel.delta.Delta>} Result of the transformation, that is an array with single delta instance.
  66. */
  67. export function defaultTransform( a, b, isAMoreImportantThanB ) {
  68. // First, resolve the flag real value.
  69. isAMoreImportantThanB = getPriority( a.constructor, b.constructor, isAMoreImportantThanB );
  70. // Create a new delta instance. Make sure that the new delta is of same type as transformed delta.
  71. // We will transform operations in that delta but it doesn't mean the delta's "meaning" which is connected to
  72. // the delta's type. Since the delta's type is heavily used in transformations and probably other parts
  73. // of system it is important to keep proper delta type through all transformation process.
  74. const transformed = new a.constructor();
  75. // Array containing operations that we will transform by. At the beginning these are just operations from
  76. let byOps = b.operations;
  77. // This array is storing operations from `byOps` which got transformed by operation from delta `a`.
  78. let newByOps = [];
  79. // We take each operation from original set of operations to transform.
  80. for ( let opA of a.operations ) {
  81. // We wrap the operation in the array. This is important, because operation transformation algorithm returns
  82. // an array of operations so we need to make sure that our algorithm is ready to handle arrays.
  83. const ops = [ opA ];
  84. // Now the real algorithm takes place.
  85. for ( let opB of byOps ) {
  86. // For each operation that we need transform by...
  87. for ( let i = 0; i < ops.length; i++ ) {
  88. // We take each operation to transform...
  89. const op = ops[ i ];
  90. // And transform both of them by themselves.
  91. // The result of transforming operation from delta B by operation from delta A is saved in
  92. // `newByOps` array. We will use that array for transformations in next loops. We need delta B
  93. // operations after transformed by delta A operations to get correct results of transformations
  94. // of next operations from delta A.
  95. //
  96. // It's like this because 2nd operation from delta A assumes that 1st operation from delta A
  97. // is "already applied". When we transform 2nd operation from delta A by operations from delta B
  98. // we have to be sure that operations from delta B are in a state that acknowledges 1st operation
  99. // from delta A.
  100. //
  101. // This can be easier understood when operations sets to transform are represented by diamond diagrams:
  102. // http://www.codecommit.com/blog/java/understanding-and-applying-operational-transformation
  103. // Using push.apply because operationTransform function is returning an array with one or multiple results.
  104. Array.prototype.push.apply( newByOps, operationTransform( opB, op, !isAMoreImportantThanB ) );
  105. // Then, we transform operation from delta A by operation from delta B.
  106. const results = operationTransform( op, opB, isAMoreImportantThanB );
  107. // We replace currently processed operation from `ops` array by the results of transformation.
  108. // Note, that we process single operation but the operationTransform result might be an array, so we
  109. // might splice-in more operations. We will process them further in next iterations. Right now we
  110. // just save them in `ops` array and move `i` pointer by proper offset.
  111. Array.prototype.splice.apply( ops, [ i, 1 ].concat( results ) );
  112. i += results.length - 1;
  113. }
  114. // At this point a single operation from delta A got transformed by a single operation from delta B.
  115. // The transformation result is in `ops` array and it may be one or more operations. This was just the first step.
  116. // Operation from delta A has to be further transformed by the other operations from delta B.
  117. // So in next iterator loop we will take another operation from delta B and use transformed delta A (`ops`)
  118. // to transform it further.
  119. }
  120. // We got through all delta B operations and have a final transformed state of an operation from delta A.
  121. // As previously mentioned, we substitute operations from delta B by their transformed equivalents.
  122. byOps = newByOps;
  123. newByOps = [];
  124. // We add transformed operation from delta A to newly created delta.
  125. // Remember that transformed operation from delta A may consist of multiple operations.
  126. for ( let op of ops ) {
  127. transformed.addOperation( op );
  128. }
  129. // In next loop, we will take another operation from delta A and transform it through (transformed) operations
  130. // from delta B...
  131. }
  132. return [ transformed ];
  133. }
  134. /**
  135. * Adds a special case callback for given delta classes.
  136. *
  137. * @param {Function} A Delta constructor which instance will get transformed.
  138. * @param {Function} B Delta constructor which instance will be transformed by.
  139. * @param {Function} resolver A callback that will handle custom special case transformation for instances of given delta classes.
  140. * @external core.treeModel.delta.transform
  141. * @function core.treeModel.delta.transform.addTransformationCase
  142. */
  143. export function addTransformationCase( A, B, resolver ) {
  144. let casesA = specialCases.get( A );
  145. if ( !casesA ) {
  146. casesA = new Map();
  147. specialCases.set( A, casesA );
  148. }
  149. casesA.set( B, resolver );
  150. }
  151. /**
  152. * Gets a special case callback which was previously {@link core.treeModel.delta.transform.addTransformationCase added}.
  153. *
  154. * @param {core.treeModel.delta.Delta} a Delta to transform.
  155. * @param {core.treeModel.delta.Delta} b Delta to be transformed by.
  156. * @external core.treeModel.delta.transform
  157. * @function core.treeModel.delta.transform.getTransformationCase
  158. */
  159. export function getTransformationCase( a, b ) {
  160. let casesA = specialCases.get( a.constructor );
  161. // If there are no special cases registered for class which `a` is instance of, we will
  162. // check if there are special cases registered for any parent class.
  163. if ( !casesA || !casesA.get( b.constructor ) ) {
  164. const cases = specialCases.keys();
  165. for ( let caseClass of cases ) {
  166. if ( a instanceof caseClass ) {
  167. casesA = specialCases.get( caseClass );
  168. }
  169. }
  170. }
  171. if ( casesA ) {
  172. return casesA.get( b.constructor );
  173. }
  174. return undefined;
  175. }
  176. // Checks priorities of passed constructors and decides which one is more important.
  177. // If both priorities are same, value passed in `isAMoreImportantThanB` parameter is used.
  178. function getPriority( A, B, isAMoreImportantThanB ) {
  179. if ( A._priority > B._priority ) {
  180. return true;
  181. } else if ( A._priority < B._priority ) {
  182. return false;
  183. } else {
  184. return isAMoreImportantThanB;
  185. }
  186. }