transform.js 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422
  1. /**
  2. * @license Copyright (c) 2003-2015, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. 'use strict';
  6. /**
  7. * Transforms given {document.operation.Operation} by another {document.operation.Operation} and returns the result of
  8. * that transformation as an array containing one or more {document.operation.Operation} elements.
  9. *
  10. * Operations work on specified positions, passed to them when they are created. Whenever {@link document.Document document}
  11. * changes, we have to reflect those modifications by updating or "transforming" operations which are not yet applied.
  12. * When an operation is transformed, its parameters may change based on the operation by which it is transformed.
  13. * If the transform-by operation applied any modifications to the Tree Data Model which affect positions or nodes
  14. * connected with transformed operation, those changes will be reflected in the parameters of the returned operation(s).
  15. *
  16. * Whenever the {@link document.Document document} has different {@link document.Document#baseVersion}
  17. * than the operation you want to {@link document.Document#applyOperation apply}, you need to transform that
  18. * operation by all operations which were already applied to the {@link document.Document document} and have greater
  19. * {@link document.Document#baseVersion} than the operation being applied. Transform them in the same order as those
  20. * operations which were applied. This way all modifications done to the Tree Data Model will be reflected
  21. * in the operation parameters and the operation will "operate" on "up-to-date" version of the Tree Data Model.
  22. * This is mostly the case with Operational Transformations but it might be needed in particular features as well.
  23. *
  24. * In some cases, when given operation apply changes to the same nodes as this operation, two or more operations need
  25. * to be created as one would not be able to reflect the combination of these operations.
  26. * This is why an array is returned instead of a single object. All returned operations have to be applied
  27. * (or further transformed) to get an effect which was intended in pre-transformed operation.
  28. *
  29. * Sometimes two operations are in conflict. This happens when they modify the same node in a different way, i.e.
  30. * set different value for the same attribute or move the node into different positions. When this happens,
  31. * we need to decide which operation is more important. We can't assume that operation `a` or operation `b` is always
  32. * more important. In Operational Transformations algorithms we often need to get a result of transforming
  33. * `a` by `b` and also `b` by `a`. In both transformations the same operation has to be the important one. If we assume
  34. * that first or the second passed operation is always more important we won't be able to solve this case.
  35. *
  36. * @function document.operation.transform
  37. * @param {document.operation.Operation} a Operation that will be transformed.
  38. * @param {document.operation.Operation} b Operation to transform by.
  39. * @param {Boolean} isAMoreImportantThanB Flag indicating whether the operation which will be transformed (`a`) should be treated
  40. * as more important when resolving conflicts.
  41. * @returns {Array.<document.operation.Operation>} Result of the transformation.
  42. */
  43. CKEDITOR.define( [
  44. 'document/operation/insertoperation',
  45. 'document/operation/changeoperation',
  46. 'document/operation/moveoperation',
  47. 'document/operation/nooperation',
  48. 'document/range',
  49. 'utils'
  50. ], ( InsertOperation, ChangeOperation, MoveOperation, NoOperation, Range, utils ) => {
  51. const ot = {
  52. InsertOperation: {
  53. // Transforms InsertOperation `a` by InsertOperation `b`. Accepts a flag stating whether `a` is more important
  54. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  55. InsertOperation( a, b, isStrong ) {
  56. // Transformed operations are always new instances, not references to the original operations.
  57. const transformed = a.clone();
  58. // Transform insert position by the other operation position.
  59. transformed.position = transformed.position.getTransformedByInsertion( b.position, b.nodeList.length, !isStrong );
  60. return [ transformed ];
  61. },
  62. ChangeOperation: doNotUpdate,
  63. // Transforms InsertOperation `a` by MoveOperation `b`. Accepts a flag stating whether `a` is more important
  64. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  65. MoveOperation( a, b, isStrong ) {
  66. const transformed = a.clone();
  67. // Transform insert position by the other operation parameters.
  68. transformed.position = a.position.getTransformedByMove( b.sourcePosition, b.targetPosition, b.howMany, !isStrong );
  69. return [ transformed ];
  70. }
  71. },
  72. ChangeOperation: {
  73. // Transforms ChangeOperation `a` by InsertOperation `b`. Returns results as an array of operations.
  74. InsertOperation( a, b ) {
  75. // Transform this operation's range.
  76. const ranges = a.range.getTransformedByInsertion( b.position, b.nodeList.length );
  77. // Map transformed range(s) to operations and return them.
  78. return ranges.reverse().map( ( range ) => {
  79. return new ChangeOperation(
  80. range,
  81. a.oldAttr,
  82. a.newAttr,
  83. a.baseVersion
  84. );
  85. } );
  86. },
  87. // Transforms ChangeOperation `a` by ChangeOperation `b`. Accepts a flag stating whether `a` is more important
  88. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  89. ChangeOperation( a, b, isStrong ) {
  90. if ( haveConflictingAttributes( a, b ) ) {
  91. // If operations attributes are in conflict, check if their ranges intersect and manage them properly.
  92. let operations = [];
  93. // First, we want to apply change to the part of a range that has not been changed by the other operation.
  94. operations = operations.concat(
  95. a.range.getDifference( b.range ).map( ( range ) => {
  96. return new ChangeOperation( range, a.oldAttr, a.newAttr, a.baseVersion );
  97. } )
  98. );
  99. if ( isStrong ) {
  100. // If this operation is more important, we want also want to apply change to the part of the
  101. // original range that has already been changed by the other operation. Since that range
  102. // got changed we have to update oldAttr.
  103. const common = a.range.getIntersection( b.range );
  104. if ( common !== null ) {
  105. operations.push( new ChangeOperation( common, b.oldAttr, a.newAttr, a.baseVersion ) );
  106. }
  107. }
  108. // If no operations has been added nothing should get updated, but since we need to return
  109. // an instance of Operation we add NoOperation to the array.
  110. if ( operations.length === 0 ) {
  111. operations.push( new NoOperation( a.baseVersion ) );
  112. }
  113. return operations;
  114. } else {
  115. // If operations don't conflict simply, return an array containing just a clone of this operation.
  116. return [ a.clone() ];
  117. }
  118. },
  119. // Transforms ChangeOperation `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.createFromPositionAndOffset( 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 ChangeOperation but are not affected
  128. // by MoveOperation. This can be zero, one or two ranges (if moved range is inside changed range).
  129. // If two ranges were returned it means that rangeB was inside rangeA. We will cover rangeB later.
  130. // Right now we will make a simplification and join difference ranges and transform them as one.
  131. const difference = joinRanges( a.range.getDifference( rangeB ) );
  132. // Common is a range of nodes that is affected by MoveOperation. So it got moved to other place.
  133. const common = a.range.getIntersection( rangeB );
  134. if ( difference !== null ) {
  135. // MoveOperation removes nodes from their original position. We acknowledge this by proper transformation.
  136. // Take the start and the end of the range and transform them by deletion of moved nodes.
  137. // Note that if rangeB was inside ChangeOperation range, only difference.end will be transformed.
  138. // This nicely covers the joining simplification we did in the previous step.
  139. difference.start = difference.start.getTransformedByDeletion( b.sourcePosition, b.howMany );
  140. difference.end = difference.end.getTransformedByDeletion( b.sourcePosition, b.howMany );
  141. // MoveOperation pastes nodes into target position. We acknowledge this by proper transformation.
  142. // Note that since we operate on transformed difference range, we should transform by
  143. // previously transformed target position.
  144. // Note that we do not use Position.getTransformedByMove on range boundaries because we need to
  145. // transform by insertion a range as a whole, since newTargetPosition might be inside that range.
  146. ranges = difference.getTransformedByInsertion( newTargetPosition, b.howMany, false ).reverse();
  147. }
  148. if ( common !== null ) {
  149. // Here we do not need to worry that newTargetPosition is inside moved range, because that
  150. // would mean that the MoveOperation targets into itself, and that is incorrect operation.
  151. // Instead, we calculate the new position of that part of original range.
  152. common.start = common.start._getCombined( b.sourcePosition, newTargetPosition );
  153. common.end = common.end._getCombined( b.sourcePosition, newTargetPosition );
  154. ranges.push( common );
  155. }
  156. // Map transformed range(s) to operations and return them.
  157. return ranges.map( ( range ) => {
  158. return new ChangeOperation(
  159. range,
  160. a.oldAttr,
  161. a.newAttr,
  162. a.baseVersion
  163. );
  164. } );
  165. }
  166. },
  167. MoveOperation: {
  168. // Transforms MoveOperation `a` by InsertOperation `b`. Accepts a flag stating whether `a` is more important
  169. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  170. InsertOperation( a, b, isStrong ) {
  171. // Get target position from the state "after" nodes are inserted by InsertOperation.
  172. const newTargetPosition = a.targetPosition.getTransformedByInsertion( b.position, b.nodeList.length, !isStrong );
  173. // Create range from MoveOperation properties and transform it by insertion as well.
  174. const rangeB = Range.createFromPositionAndOffset( a.sourcePosition, a.howMany );
  175. const ranges = rangeB.getTransformedByInsertion( b.position, b.nodeList.length, true );
  176. // Map transformed range(s) to operations and return them.
  177. return ranges.reverse().map( ( range ) => {
  178. return new MoveOperation(
  179. range.start,
  180. newTargetPosition.clone(),
  181. range.end.offset - range.start.offset,
  182. a.baseVersion
  183. );
  184. } );
  185. },
  186. ChangeOperation: doNotUpdate,
  187. // Transforms MoveOperation `a` by MoveOperation `b`. Accepts a flag stating whether `a` is more important
  188. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  189. MoveOperation( a, b, isStrong ) {
  190. // Special case when both move operations' target positions are inside nodes that are
  191. // being moved by the other move operation. So in other words, we move ranges into inside of each other.
  192. // This case can't be solved reasonably (on the other hand, it should not happen often).
  193. if ( moveTargetIntoMovedRange( a, b ) && moveTargetIntoMovedRange( b, a ) ) {
  194. // Instead of transforming operation, we return a reverse of the operation that we transform by.
  195. // So when the results of this "transformation" will be applied, `b` MoveOperation will get reversed.
  196. return [ b.getReversed() ];
  197. }
  198. // Create ranges from MoveOperations properties.
  199. const rangeA = Range.createFromPositionAndOffset( a.sourcePosition, a.howMany );
  200. const rangeB = Range.createFromPositionAndOffset( b.sourcePosition, b.howMany );
  201. // Special case when transformed range contains both the other operation's whole range and target.
  202. // In such case, operations are not really conflicting and we should leave transformed operation as it is.
  203. // Without this we would have 3 or 4 operations and the transformation result would probably be not intuitive.
  204. if ( rangeA.containsRange( rangeB ) && rangeA.containsPosition( b.targetPosition ) ) {
  205. return [ a.clone() ];
  206. }
  207. // Mirror situation for the case above - now transformed range is wholly contained in the other
  208. // operation's range and also targets to that range. Without this special treatment we would
  209. // transform this operation into NoOperation, but this would not be compatible with the result
  210. // generated by the special case above.
  211. else if ( rangeB.containsRange( rangeA ) && rangeB.containsPosition( a.targetPosition ) ) {
  212. return [
  213. new MoveOperation(
  214. a.sourcePosition._getCombined( b.sourcePosition, b.targetPosition ),
  215. a.targetPosition._getCombined( b.sourcePosition, b.targetPosition ),
  216. a.howMany,
  217. a.baseVersion
  218. )
  219. ];
  220. }
  221. // All the other non-special cases are treated by generic algorithm below.
  222. const differenceSet = rangeA.getDifference( rangeB );
  223. const common = rangeA.getIntersection( rangeB );
  224. // This will aggregate transformed ranges.
  225. let ranges = [];
  226. // Get target position from the state "after" nodes specified by other MoveOperation are "detached".
  227. const moveTargetPosition = b.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany );
  228. // First, we take care of that part of the range that is only modified by transformed operation.
  229. for ( let i = 0; i < differenceSet.length; i++ ) {
  230. // MoveOperation removes nodes from their original position. We acknowledge this by proper transformation.
  231. // Take the start and the end of the range and transform them by deletion of moved nodes.
  232. differenceSet[ i ].start = differenceSet[ i ].start.getTransformedByDeletion( b.sourcePosition, b.howMany );
  233. differenceSet[ i ].end = differenceSet[ i ].end.getTransformedByDeletion( b.sourcePosition, b.howMany );
  234. // MoveOperation pastes nodes into target position. We acknowledge this by proper transformation.
  235. // Note that since we operate on transformed difference range, we should transform by
  236. // previously transformed target position.
  237. // Note that we do not use Position.getTransformedByMove on range boundaries because we need to
  238. // transform by insertion a range as a whole, since newTargetPosition might be inside that range.
  239. ranges = ranges.concat( differenceSet[ i ].getTransformedByInsertion( moveTargetPosition, b.howMany, true ) );
  240. }
  241. // Then, we have to manage the common part of both move ranges.
  242. // If MoveOperations has common range it can be one of two:
  243. // * on the same tree level - it means that we move the same nodes into different places
  244. // * on deeper tree level - it means that we move nodes that are inside moved nodes
  245. // The operations are conflicting only if they try to move exactly same nodes, so only in the first case.
  246. // So, we will handle common range if it is "deeper" or if transformed operation is more important.
  247. let isDeeper = utils.compareArrays( b.sourcePosition.getParentPath(), a.sourcePosition.getParentPath() ) == utils.compareArrays.PREFIX;
  248. if ( common !== null && ( isDeeper || isStrong ) ) {
  249. // Here we do not need to worry that newTargetPosition is inside moved range, because that
  250. // would mean that the MoveOperation targets into itself, and that is incorrect operation.
  251. // Instead, we calculate the new position of that part of original range.
  252. common.start = common.start._getCombined( b.sourcePosition, moveTargetPosition );
  253. common.end = common.end._getCombined( b.sourcePosition, moveTargetPosition );
  254. // We have to take care of proper range order.
  255. // Note that both push, splice and unshift do the same if there are no ranges in the array.
  256. if ( rangeB.end.isAfter( rangeA.end ) ) {
  257. ranges.push( common );
  258. } else if ( rangeB.start.isBefore( rangeA.start ) ) {
  259. ranges.unshift( common );
  260. } else {
  261. ranges.splice( 1, 0, common );
  262. }
  263. }
  264. // At this point we transformed this operation's source ranges it means that nothing should be changed.
  265. // But since we need to return an instance of Operation we return an array with NoOperation.
  266. if ( ranges.length === 0 ) {
  267. return [ new NoOperation( a.baseVersion ) ];
  268. }
  269. // Target position also could be affected by the other MoveOperation. We will transform it.
  270. let newTargetPosition = a.targetPosition.getTransformedByMove( b.sourcePosition, moveTargetPosition, b.howMany, !isStrong );
  271. // Map transformed range(s) to operations and return them.
  272. return ranges.reverse().map( ( range ) => {
  273. return new MoveOperation(
  274. range.start,
  275. newTargetPosition,
  276. range.end.offset - range.start.offset,
  277. a.baseVersion
  278. );
  279. } );
  280. }
  281. }
  282. };
  283. return ( a, b, isStrong ) => {
  284. let group;
  285. let algorithm;
  286. if ( a instanceof InsertOperation ) {
  287. group = ot.InsertOperation;
  288. } else if ( a instanceof ChangeOperation ) {
  289. group = ot.ChangeOperation;
  290. } else if ( a instanceof MoveOperation ) {
  291. group = ot.MoveOperation;
  292. } else {
  293. algorithm = doNotUpdate;
  294. }
  295. if ( group ) {
  296. if ( b instanceof InsertOperation ) {
  297. algorithm = group.InsertOperation;
  298. } else if ( b instanceof ChangeOperation ) {
  299. algorithm = group.ChangeOperation;
  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. // Takes two ChangeOperations and checks whether their attributes are in conflict.
  327. // This happens when both operations changes an attribute with the same key and they either set different
  328. // values for this attribute or one of them removes it while the other one sets it.
  329. // Returns true if attributes are in conflict.
  330. function haveConflictingAttributes( a, b ) {
  331. // Keeping in mind that newAttr or oldAttr might be null.
  332. // We will retrieve the key from whichever parameter is set.
  333. const keyA = ( a.newAttr || a.oldAttr ).key;
  334. const keyB = ( b.newAttr || b.oldAttr ).key;
  335. if ( keyA != keyB ) {
  336. // Different keys - not conflicting.
  337. return false;
  338. }
  339. if ( a.newAttr === null && b.newAttr === null ) {
  340. // Both remove the attribute - not conflicting.
  341. return false;
  342. }
  343. // Check if they set different value or one of them removes the attribute.
  344. return ( a.newAttr === null && b.newAttr !== null ) ||
  345. ( a.newAttr !== null && b.newAttr === null ) ||
  346. ( !a.newAttr.isEqual( b.newAttr ) );
  347. }
  348. // Gets an array of Ranges and produces one Range out of it. The root of a new range will be same as
  349. // the root of the first range in the array. If any of given ranges has different root than the first range,
  350. // it will be discarded.
  351. function joinRanges( ranges ) {
  352. if ( ranges.length === 0 ) {
  353. return null;
  354. } else if ( ranges.length == 1 ) {
  355. return ranges[ 0 ];
  356. } else {
  357. ranges[ 0 ].end = ranges[ ranges.length - 1 ].end;
  358. return ranges[ 0 ];
  359. }
  360. }
  361. } );