transform.js 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406
  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 InsertOperation from './insertoperation.js';
  7. import AttributeOperation from './attributeoperation.js';
  8. import RootAttributeOperation from './rootattributeoperation.js';
  9. import MoveOperation from './moveoperation.js';
  10. import RemoveOperation from './removeoperation.js';
  11. import NoOperation from './nooperation.js';
  12. import Range from '../range.js';
  13. import isEqual from '../../../utils/lib/lodash/isEqual.js';
  14. import utils from '../../../utils/utils.js';
  15. /**
  16. * Transforms given {@link core.treeModel.operation.Operation operation} by another {@link core.treeModel.operation.Operation operation} and
  17. * returns the result of that transformation as an array containing one or more {@link core.treeModel.operation.Operation operation}
  18. * elements.
  19. *
  20. * Operations work on specified positions, passed to them when they are created. Whenever {@link core.treeModel.Document document}
  21. * changes, we have to reflect those modifications by updating or "transforming" operations which are not yet applied.
  22. * When an operation is transformed, its parameters may change based on the operation by which it is transformed.
  23. * If the transform-by operation applied any modifications to the Tree Data Model which affect positions or nodes
  24. * connected with transformed operation, those changes will be reflected in the parameters of the returned operation(s).
  25. *
  26. * Whenever the {@link core.treeModel.Document document} has different {@link core.treeModel.Document#baseVersion}
  27. * than the operation you want to {@link core.treeModel.Document#applyOperation apply}, you need to transform that
  28. * operation by all operations which were already applied to the {@link core.treeModel.Document document} and have greater
  29. * {@link core.treeModel.Document#baseVersion} than the operation being applied. Transform them in the same order as those
  30. * operations which were applied. This way all modifications done to the Tree Data Model will be reflected
  31. * in the operation parameters and the operation will "operate" on "up-to-date" version of the Tree Data Model.
  32. * This is mostly the case with Operational Transformations but it might be needed in particular features as well.
  33. *
  34. * In some cases, when given operation apply changes to the same nodes as this operation, two or more operations need
  35. * to be created as one would not be able to reflect the combination of these operations.
  36. * This is why an array is returned instead of a single object. All returned operations have to be applied
  37. * (or further transformed) to get an effect which was intended in pre-transformed operation.
  38. *
  39. * Sometimes two operations are in conflict. This happens when they modify the same node in a different way, i.e.
  40. * set different value for the same attribute or move the node into different positions. When this happens,
  41. * we need to decide which operation is more important. We can't assume that operation `a` or operation `b` is always
  42. * more important. In Operational Transformations algorithms we often need to get a result of transforming
  43. * `a` by `b` and also `b` by `a`. In both transformations the same operation has to be the important one. If we assume
  44. * that first or the second passed operation is always more important we won't be able to solve this case.
  45. *
  46. * @external core.treeModel.operation
  47. * @function core.treeModel.operation.transform
  48. * @param {core.treeModel.operation.Operation} a Operation that will be transformed.
  49. * @param {core.treeModel.operation.Operation} b Operation to transform by.
  50. * @param {Boolean} isAMoreImportantThanB Flag indicating whether the operation which will be transformed (`a`) should be treated
  51. * as more important when resolving conflicts.
  52. * @returns {Array.<core.treeModel.operation.Operation>} Result of the transformation.
  53. */
  54. export default transform;
  55. const ot = {
  56. InsertOperation: {
  57. // Transforms InsertOperation `a` by InsertOperation `b`. Accepts a flag stating whether `a` is more important
  58. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  59. InsertOperation( a, b, isStrong ) {
  60. // Transformed operations are always new instances, not references to the original operations.
  61. const transformed = a.clone();
  62. // Transform insert position by the other operation position.
  63. transformed.position = transformed.position.getTransformedByInsertion( b.position, b.nodeList.length, !isStrong );
  64. return [ transformed ];
  65. },
  66. AttributeOperation: doNotUpdate,
  67. RootAttributeOperation: doNotUpdate,
  68. // Transforms InsertOperation `a` by MoveOperation `b`. Accepts a flag stating whether `a` is more important
  69. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  70. MoveOperation( a, b, isStrong ) {
  71. const transformed = a.clone();
  72. const moveTargetPosition = b.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany );
  73. // Transform insert position by the other operation parameters.
  74. transformed.position = a.position.getTransformedByMove( b.sourcePosition, moveTargetPosition, b.howMany, !isStrong, b.isSticky );
  75. return [ transformed ];
  76. }
  77. },
  78. AttributeOperation: {
  79. // Transforms AttributeOperation `a` by InsertOperation `b`. Returns results as an array of operations.
  80. InsertOperation( a, b ) {
  81. // Transform this operation's range.
  82. const ranges = a.range.getTransformedByInsertion( b.position, b.nodeList.length, true, false );
  83. // Map transformed range(s) to operations and return them.
  84. return ranges.reverse().map( ( range ) => {
  85. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
  86. } );
  87. },
  88. // Transforms AttributeOperation `a` by AttributeOperation `b`. Accepts a flag stating whether `a` is more important
  89. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  90. AttributeOperation( a, b, isStrong ) {
  91. if ( a.key === b.key ) {
  92. // If operations attributes are in conflict, check if their ranges intersect and manage them properly.
  93. // First, we want to apply change to the part of a range that has not been changed by the other operation.
  94. let operations = a.range.getDifference( b.range ).map( ( range ) => {
  95. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
  96. } );
  97. // Then we take care of the common part of ranges, but only if operations has different `newValue`.
  98. if ( isStrong && !isEqual( a.newValue, b.newValue ) ) {
  99. // If this operation is more important, we also want to apply change to the part of the
  100. // original range that has already been changed by the other operation. Since that range
  101. // got changed we also have to update `oldValue`.
  102. const common = a.range.getIntersection( b.range );
  103. if ( common !== null ) {
  104. operations.push( new AttributeOperation( common, b.key, b.oldValue, a.newValue, a.baseVersion ) );
  105. }
  106. }
  107. // If no operations has been added nothing should get updated, but since we need to return
  108. // an instance of Operation we add NoOperation to the array.
  109. if ( operations.length === 0 ) {
  110. operations.push( new NoOperation( a.baseVersion ) );
  111. }
  112. return operations;
  113. } else {
  114. // If operations don't conflict, simply return an array containing just a clone of this operation.
  115. return [ a.clone() ];
  116. }
  117. },
  118. RootAttributeOperation: doNotUpdate,
  119. // Transforms AttributeOperation `a` by MoveOperation `b`. Returns results as an array of operations.
  120. MoveOperation( a, b ) {
  121. // Convert MoveOperation properties into a range.
  122. const rangeB = Range.createFromPositionAndShift( b.sourcePosition, b.howMany );
  123. // Get target position from the state "after" nodes specified by MoveOperation are "detached".
  124. const newTargetPosition = b.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany );
  125. // This will aggregate transformed ranges.
  126. let ranges = [];
  127. // Difference is a part of changed range that is modified by AttributeOperation but is not affected
  128. // by MoveOperation. This can be zero, one or two ranges (if moved range is inside changed range).
  129. // Right now we will make a simplification and join difference ranges and transform them as one. We will cover rangeB later.
  130. const difference = joinRanges( a.range.getDifference( rangeB ) );
  131. // Common is a range of nodes that is affected by MoveOperation. So it got moved to other place.
  132. const common = a.range.getIntersection( rangeB );
  133. if ( difference !== null ) {
  134. // MoveOperation removes nodes from their original position. We acknowledge this by proper transformation.
  135. // Take the start and the end of the range and transform them by deletion of moved nodes.
  136. // Note that if rangeB was inside AttributeOperation range, only difference.end will be transformed.
  137. // This nicely covers the joining simplification we did in the previous step.
  138. difference.start = difference.start.getTransformedByDeletion( b.sourcePosition, b.howMany );
  139. difference.end = difference.end.getTransformedByDeletion( b.sourcePosition, b.howMany );
  140. // MoveOperation pastes nodes into target position. We acknowledge this by proper transformation.
  141. // Note that since we operate on transformed difference range, we should transform by
  142. // previously transformed target position.
  143. // Note that we do not use Position.getTransformedByMove on range boundaries because we need to
  144. // transform by insertion a range as a whole, since newTargetPosition might be inside that range.
  145. ranges = difference.getTransformedByInsertion( newTargetPosition, b.howMany, true, false ).reverse();
  146. }
  147. if ( common !== null ) {
  148. // Here we do not need to worry that newTargetPosition is inside moved range, because that
  149. // would mean that the MoveOperation targets into itself, and that is incorrect operation.
  150. // Instead, we calculate the new position of that part of original range.
  151. common.start = common.start._getCombined( b.sourcePosition, newTargetPosition );
  152. common.end = common.end._getCombined( b.sourcePosition, newTargetPosition );
  153. ranges.push( common );
  154. }
  155. // Map transformed range(s) to operations and return them.
  156. return ranges.map( ( range ) => {
  157. return new AttributeOperation( range, a.key, a.oldValue, a.newValue, a.baseVersion );
  158. } );
  159. }
  160. },
  161. RootAttributeOperation: {
  162. InsertOperation: doNotUpdate,
  163. AttributeOperation: doNotUpdate,
  164. // Transforms RootAttributeOperation `a` by RootAttributeOperation `b`. Accepts a flag stating whether `a` is more important
  165. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  166. RootAttributeOperation( a, b, isStrong ) {
  167. if ( a.root === b.root && a.key === b.key ) {
  168. if ( ( a.newValue !== b.newValue && !isStrong ) || a.newValue === b.newValue ) {
  169. return [ new NoOperation( a.baseVersion ) ];
  170. }
  171. }
  172. return [ a.clone() ];
  173. },
  174. MoveOperation: doNotUpdate
  175. },
  176. MoveOperation: {
  177. // Transforms MoveOperation `a` by InsertOperation `b`. Accepts a flag stating whether `a` is more important
  178. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  179. InsertOperation( a, b, isStrong ) {
  180. // Create range from MoveOperation properties and transform it by insertion.
  181. let range = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  182. range = range.getTransformedByInsertion( b.position, b.nodeList.length, false, a.isSticky )[ 0 ];
  183. return [
  184. new a.constructor(
  185. range.start,
  186. range.end.offset - range.start.offset,
  187. a instanceof RemoveOperation ? a.baseVersion : a.targetPosition.getTransformedByInsertion( b.position, b.nodeList.length, !isStrong ),
  188. a instanceof RemoveOperation ? undefined : a.baseVersion
  189. )
  190. ];
  191. },
  192. AttributeOperation: doNotUpdate,
  193. RootAttributeOperation: doNotUpdate,
  194. // Transforms MoveOperation `a` by MoveOperation `b`. Accepts a flag stating whether `a` is more important
  195. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  196. MoveOperation( a, b, isStrong ) {
  197. // Special case when both move operations' target positions are inside nodes that are
  198. // being moved by the other move operation. So in other words, we move ranges into inside of each other.
  199. // This case can't be solved reasonably (on the other hand, it should not happen often).
  200. if ( moveTargetIntoMovedRange( a, b ) && moveTargetIntoMovedRange( b, a ) ) {
  201. // Instead of transforming operation, we return a reverse of the operation that we transform by.
  202. // So when the results of this "transformation" will be applied, `b` MoveOperation will get reversed.
  203. return [ b.getReversed() ];
  204. }
  205. // If one of operations is actually a remove operation, we force remove operation to be the "stronger" one
  206. // to provide more expected results.
  207. if ( a instanceof RemoveOperation && !( b instanceof RemoveOperation ) ) {
  208. isStrong = true;
  209. } else if ( !( a instanceof RemoveOperation ) && b instanceof RemoveOperation ) {
  210. isStrong = false;
  211. }
  212. // Create ranges from MoveOperations properties.
  213. const rangeA = Range.createFromPositionAndShift( a.sourcePosition, a.howMany );
  214. const rangeB = Range.createFromPositionAndShift( b.sourcePosition, b.howMany );
  215. // Get target position from the state "after" nodes specified by other MoveOperation are "detached".
  216. const moveTargetPosition = b.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany );
  217. // This will aggregate transformed ranges.
  218. let ranges = [];
  219. // All the other non-special cases are treated by generic algorithm below.
  220. let difference = joinRanges( rangeA.getDifference( rangeB ) );
  221. if ( difference ) {
  222. difference.start = difference.start.getTransformedByMove( b.sourcePosition, moveTargetPosition, b.howMany, !a.isSticky, false );
  223. difference.end = difference.end.getTransformedByMove( b.sourcePosition, moveTargetPosition, b.howMany, a.isSticky, false );
  224. ranges.push( difference );
  225. }
  226. // Then, we have to manage the common part of both move ranges.
  227. const common = rangeA.getIntersection( rangeB );
  228. // If MoveOperations has common range it can be one of two:
  229. // * on the same tree level - it means that we move the same nodes into different places
  230. // * on deeper tree level - it means that we move nodes that are inside moved nodes
  231. // The operations are conflicting only if they try to move exactly same nodes, so only in the first case.
  232. // That means that we transform common part in two cases:
  233. // * `rangeA` is "deeper" than `rangeB` so it does not collide
  234. // * `rangeA` is at the same level but is stronger than `rangeB`.
  235. let aCompB = utils.compareArrays( a.sourcePosition.getParentPath(), b.sourcePosition.getParentPath() );
  236. // If the `b` MoveOperation points inside the `a` MoveOperation range, the common part will be included in
  237. // range(s) that (is) are results of processing `difference`. If that's the case, we cannot include it again.
  238. let bTargetsToA = rangeA.containsPosition( b.targetPosition ) ||
  239. ( rangeA.start.isEqual( b.targetPosition ) && a.isSticky ) ||
  240. ( rangeA.end.isEqual( b.targetPosition ) && a.isSticky );
  241. // If the `b` MoveOperation range contains both whole `a` range and target position we do an exception and
  242. // transform `a` operation. Normally, when same nodes are moved, we stick with stronger operation's target.
  243. // Here it is a move inside larger range so there is no conflict because after all, all nodes from
  244. // smaller range will be moved to larger range target. The effect of this transformation feels natural.
  245. let aIsInside = rangeB.containsRange( rangeA ) && rangeB.containsPosition( a.targetPosition );
  246. if ( common !== null && ( aCompB === 'EXTENSION' || ( aCompB === 'SAME' && isStrong ) || aIsInside ) && !bTargetsToA ) {
  247. // Here we do not need to worry that newTargetPosition is inside moved range, because that
  248. // would mean that the MoveOperation targets into itself, and that is incorrect operation.
  249. // Instead, we calculate the new position of that part of original range.
  250. common.start = common.start._getCombined( b.sourcePosition, moveTargetPosition );
  251. common.end = common.end._getCombined( b.sourcePosition, moveTargetPosition );
  252. // We have to take care of proper range order.
  253. if ( difference && difference.start.isBefore( common.start ) ) {
  254. ranges.push( common );
  255. } else {
  256. ranges.unshift( common );
  257. }
  258. }
  259. // At this point we transformed this operation's source ranges it means that nothing should be changed.
  260. // But since we need to return an instance of Operation we return an array with NoOperation.
  261. if ( ranges.length === 0 ) {
  262. return [ new NoOperation( a.baseVersion ) ];
  263. }
  264. // Target position also could be affected by the other MoveOperation. We will transform it.
  265. let newTargetPosition = a.targetPosition.getTransformedByMove( b.sourcePosition, moveTargetPosition, b.howMany, !isStrong, b.isSticky );
  266. // Map transformed range(s) to operations and return them.
  267. return ranges.reverse().map( ( range ) => {
  268. // We want to keep correct operation class.
  269. return new a.constructor(
  270. range.start,
  271. range.end.offset - range.start.offset,
  272. a instanceof RemoveOperation ? a.baseVersion : newTargetPosition,
  273. a instanceof RemoveOperation ? undefined : a.baseVersion
  274. );
  275. } );
  276. }
  277. }
  278. };
  279. function transform( a, b, isStrong ) {
  280. let group;
  281. let algorithm;
  282. if ( a instanceof InsertOperation ) {
  283. group = ot.InsertOperation;
  284. } else if ( a instanceof AttributeOperation ) {
  285. group = ot.AttributeOperation;
  286. } else if ( a instanceof RootAttributeOperation ) {
  287. group = ot.RootAttributeOperation;
  288. } else if ( a instanceof MoveOperation ) {
  289. group = ot.MoveOperation;
  290. } else {
  291. algorithm = doNotUpdate;
  292. }
  293. if ( group ) {
  294. if ( b instanceof InsertOperation ) {
  295. algorithm = group.InsertOperation;
  296. } else if ( b instanceof AttributeOperation ) {
  297. algorithm = group.AttributeOperation;
  298. } else if ( b instanceof RootAttributeOperation ) {
  299. algorithm = group.RootAttributeOperation;
  300. } else if ( b instanceof MoveOperation ) {
  301. algorithm = group.MoveOperation;
  302. } else {
  303. algorithm = doNotUpdate;
  304. }
  305. }
  306. let transformed = algorithm( a, b, isStrong );
  307. return updateBaseVersions( a.baseVersion, transformed );
  308. }
  309. // When we don't want to update an operation, we create and return a clone of it.
  310. // Returns the operation in "unified format" - wrapped in an Array.
  311. function doNotUpdate( operation ) {
  312. return [ operation.clone() ];
  313. }
  314. // Takes an Array of operations and sets consecutive base versions for them, starting from given base version.
  315. // Returns the passed array.
  316. function updateBaseVersions( baseVersion, operations ) {
  317. for ( let i = 0; i < operations.length; i++ ) {
  318. operations[ i ].baseVersion = baseVersion + i + 1;
  319. }
  320. return operations;
  321. }
  322. // Checks whether MoveOperation targetPosition is inside a node from the moved range of the other MoveOperation.
  323. function moveTargetIntoMovedRange( a, b ) {
  324. return a.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany ) === null;
  325. }
  326. // Gets an array of Ranges and produces one Range out of it. The root of a new range will be same as
  327. // the root of the first range in the array. If any of given ranges has different root than the first range,
  328. // it will be discarded.
  329. function joinRanges( ranges ) {
  330. if ( ranges.length === 0 ) {
  331. return null;
  332. } else if ( ranges.length == 1 ) {
  333. return ranges[ 0 ];
  334. } else {
  335. ranges[ 0 ].end = ranges[ ranges.length - 1 ].end;
  336. return ranges[ 0 ];
  337. }
  338. }