transformoperation.js 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416
  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 operate 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 operation is transformed, its parameters may change basing on the operation by which it is transformed.
  13. * If the transform-by operation applied any modifications to the Tree Model that affects 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 an operation you want to {@link document.Document#applyOperation apply}, you need to transform that
  18. * operation by all the operations that were applied to the {@link document.Document document} since it has
  19. * {@link document.Document#baseVersion} same as the operation. Transform them in the same order as those
  20. * operations were applied. This way all modifications done to the Tree Model will be reflected
  21. * in the operation parameters and the operation will "operate" on "up-to-date" version of the Tree Model.
  22. * This is mostly the case with Operational Transformation but it might be needed in particular features.
  23. *
  24. * In some cases, when given operation apply changes to the same nodes as this operation, there is a need
  25. * to create two operations as a result. It would be impossible to create just one operation that handles
  26. * modifications needed to be applied to the tree. This is why Array is returned instead of single object.
  27. * All returned operations has to be applied (or further transformed) to get an effect that was intended in
  28. * pre-transformed operation.
  29. *
  30. * Sometimes two operations are in conflict. This happens when they modify the same node in a different way, i.e.
  31. * set different value for the same attribute or move the node into different positions. When this happens,
  32. * we need to decide which operation is more important. We can't assume that operation `a` or operation `b` is always
  33. * important. In Operational Transformations algorithms we often need to get a result of transforming
  34. * `a` by `b` and also `b` by `a`. In both transformations the same operation has to be the important one. If we assume
  35. * that first or second passed operation is always more important we won't be able to solve this case.
  36. *
  37. * @function transformOperation
  38. * @param {document.operation.Operation} a Operation that will be transformed.
  39. * @param {document.operation.Operation} b Operation to transform by.
  40. * @param {Boolean} isStrong Flag indicating whether this operation should be treated as more important
  41. * when resolving conflicts.
  42. * @returns {Array.<document.operation.Operation>} Result of the transformation.
  43. */
  44. CKEDITOR.define( [
  45. 'document/operation/insertoperation',
  46. 'document/operation/changeoperation',
  47. 'document/operation/moveoperation',
  48. 'document/operation/nooperation',
  49. 'document/range',
  50. 'utils'
  51. ], ( InsertOperation, ChangeOperation, MoveOperation, NoOperation, Range, utils ) => {
  52. // When we don't want to update an operation, we create and return a clone of it.
  53. // Returns the operation in "unified format" - wrapped in an Array.
  54. function doNotUpdate( operation ) {
  55. return [ operation.clone() ];
  56. }
  57. // Takes an Array of operations and sets consecutive base versions for them, starting from given base version.
  58. // Returns the passed array.
  59. function updateBaseVersions( baseVersion, operations ) {
  60. for ( let i = 0; i < operations.length; i++ ) {
  61. operations[ i ].baseVersion = baseVersion + i + 1;
  62. }
  63. return operations;
  64. }
  65. // Checks whether MoveOperation targetPosition is inside a node from the moved range of the other MoveOperation.
  66. function moveTargetIntoMovedRange( a, b ) {
  67. return a.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany ) === null;
  68. }
  69. // Takes two ChangeOperations and checks whether their attributes are in conflict.
  70. // This happens when both operations changes an attribute with the same key and they either set different
  71. // values for this attribute or one of them removes it while the other one sets it.
  72. // Returns true if attributes are in conflict.
  73. function haveConflictingAttributes( a, b ) {
  74. // Keeping in mind that newAttr or oldAttr might be null.
  75. // We will retrieve the key from whichever parameter is set.
  76. const keyA = ( a.newAttr || a.oldAttr ).key;
  77. const keyB = ( b.newAttr || b.oldAttr ).key;
  78. if ( keyA != keyB ) {
  79. // Different keys - not conflicting.
  80. return false;
  81. }
  82. // Check if they set different value or one of them removes the attribute.
  83. return ( a.newAttr === null && b.newAttr !== null ) ||
  84. ( a.newAttr !== null && b.newAttr === null ) ||
  85. ( !a.newAttr.isEqual( b.newAttr ) );
  86. }
  87. const ot = {
  88. InsertOperation: {
  89. // Transforms InsertOperation `a` by InsertOperation `b`. Accepts a flag stating whether `a` is more important
  90. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  91. InsertOperation( a, b, isStrong ) {
  92. // Transformed operations are always new instances, not references to the original operations.
  93. const transformed = a.clone();
  94. // Transform operation position by the other operation position.
  95. transformed.position = transformed.position.getTransformedByInsertion( b.position, b.nodeList.length, !isStrong );
  96. return [ transformed ];
  97. },
  98. ChangeOperation: doNotUpdate,
  99. // Transforms InsertOperation `a` by MoveOperation `b`. Accepts a flag stating whether `a` is more important
  100. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  101. MoveOperation( a, b, isStrong ) {
  102. const transformed = a.clone();
  103. // MoveOperation removes nodes from their original position. We acknowledge this by proper transformation.
  104. const newPosition = a.position.getTransformedByDeletion( b.sourcePosition, b.howMany );
  105. if ( newPosition === null ) {
  106. // This operation's position was inside a node moved by MoveOperation. We substitute that position by
  107. // the combination of move target position and insert position. This reflects changes done by MoveOperation.
  108. transformed.position = transformed.position.getCombined( b.sourcePosition, b.targetPosition );
  109. } else {
  110. // Here we have the insert position after some nodes has been removed by MoveOperation.
  111. // Next step is to reflect pasting nodes by MoveOperation, which might further affect the position.
  112. transformed.position = newPosition.getTransformedByInsertion( b.targetPosition, b.howMany, !isStrong );
  113. }
  114. return [ transformed ];
  115. }
  116. },
  117. ChangeOperation: {
  118. // Transforms ChangeOperation `a` by InsertOperation `b`. Returns results as an array of operations.
  119. InsertOperation( a, b ) {
  120. // Transform this operation's range.
  121. const ranges = a.range.getTransformedByInsertion( b.position, b.nodeList.length );
  122. // Map transformed range(s) to operations and return them.
  123. return ranges.map( ( range ) => {
  124. return new ChangeOperation(
  125. range,
  126. a.oldAttr,
  127. a.newAttr,
  128. a.baseVersion
  129. );
  130. } );
  131. },
  132. // Transforms ChangeOperation `a` by ChangeOperation `b`. Accepts a flag stating whether `a` is more important
  133. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  134. ChangeOperation( a, b, isStrong ) {
  135. if ( haveConflictingAttributes( a, b ) ) {
  136. // If operations attributes are in conflict, check if their ranges intersect and manage them properly.
  137. let operations = [];
  138. // First, we want to apply change to the part of a range that has not been changed by the other operation.
  139. operations = operations.concat(
  140. a.range.getDifference( b.range ).map( ( range ) => {
  141. return new ChangeOperation( range, a.oldAttr, a.newAttr, a.baseVersion );
  142. } )
  143. );
  144. if ( isStrong ) {
  145. // If this operation is more important, we want also want to apply change to the part of the
  146. // original range that has already been changed by the other operation. Since that range
  147. // got changed we have to update oldAttr.
  148. const common = a.range.getIntersection( b.range );
  149. if ( common !== null ) {
  150. operations.push( new ChangeOperation( common, b.oldAttr, a.newAttr, a.baseVersion ) );
  151. }
  152. }
  153. // If no operations has been added nothing should get updated, but since we need to return
  154. // an instance of Operation we add NoOperation to the array.
  155. if ( operations.length === 0 ) {
  156. operations.push( new NoOperation( a.baseVersion ) );
  157. }
  158. return operations;
  159. } else {
  160. // If operations don't conflict simply, return an array containing just a clone of this operation.
  161. return [ a.clone() ];
  162. }
  163. },
  164. // Transforms ChangeOperation `a` by MoveOperation `b`. Returns results as an array of operations.
  165. MoveOperation( a, b ) {
  166. // Convert MoveOperation properties into a range.
  167. const rangeB = Range.createFromPositionAndOffset( b.sourcePosition, b.howMany );
  168. // Get target position from the state "after" nodes specified by MoveOperation are "detached".
  169. const newTargetPosition = b.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany );
  170. // This will aggregate transformed ranges.
  171. let ranges = [];
  172. const differenceSet = a.range.getDifference( rangeB );
  173. const common = a.range.getIntersection( rangeB );
  174. // Difference is a part of changed range that is modified by ChangeOperation but are not affected
  175. // by MoveOperation. This can be zero, one or two ranges (if moved range is inside changed range).
  176. if ( differenceSet.length > 0 ) {
  177. const difference = differenceSet[ 0 ];
  178. // If two ranges were returned it means that rangeB was inside rangeA. We will cover rangeB later.
  179. // Right now we will make a simplification and join difference ranges and transform them as one.
  180. if ( differenceSet.length == 2 ) {
  181. difference.end = differenceSet[ 1 ].end.clone();
  182. }
  183. // MoveOperation removes nodes from their original position. We acknowledge this by proper transformation.
  184. // Take the start and the end of the range and transform them by deletion of moved nodes.
  185. // Note that if rangeB was inside ChangeOperation range, only difference.end will be transformed.
  186. // This nicely covers the joining simplification we did in the previous step.
  187. difference.start = difference.start.getTransformedByDeletion( b.sourcePosition, b.howMany );
  188. difference.end = difference.end.getTransformedByDeletion( b.sourcePosition, b.howMany );
  189. // MoveOperation pastes nodes into target position. We acknowledge this by proper transformation.
  190. // Note that since we operate on transformed difference range, we should transform by
  191. // previously transformed target position.
  192. ranges = difference.getTransformedByInsertion( newTargetPosition, b.howMany, false );
  193. }
  194. // Common is a range of nodes that is affected by MoveOperation. So it got moved to other place.
  195. if ( common !== null ) {
  196. // We substitute original position by the combination of target position and original position.
  197. // This reflects that those nodes were moved to another place by MoveOperation.
  198. common.start = common.start.getCombined( b.sourcePosition, newTargetPosition );
  199. common.end = common.end.getCombined( b.sourcePosition, newTargetPosition );
  200. ranges.push( common );
  201. }
  202. // Map transformed range(s) to operations and return them.
  203. return ranges.map( ( range ) => {
  204. return new ChangeOperation(
  205. range,
  206. a.oldAttr,
  207. a.newAttr,
  208. a.baseVersion
  209. );
  210. } );
  211. }
  212. },
  213. MoveOperation: {
  214. // Transforms MoveOperation `a` by InsertOperation `b`. Accepts a flag stating whether `a` is more important
  215. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  216. InsertOperation( a, b, isStrong ) {
  217. // Get target position from the state "after" nodes are inserted by InsertOperation.
  218. const newTargetPosition = a.targetPosition.getTransformedByInsertion( b.position, b.nodeList.length, !isStrong );
  219. // Create range from MoveOperation properties and transform it by insertion as well.
  220. const rangeB = Range.createFromPositionAndOffset( a.sourcePosition, a.howMany );
  221. const ranges = rangeB.getTransformedByInsertion( b.position, b.nodeList.length, true );
  222. // Map transformed range(s) to operations and return them.
  223. return ranges.map( ( range ) => {
  224. return new MoveOperation(
  225. range.start,
  226. newTargetPosition.clone(),
  227. range.end.offset - range.start.offset,
  228. a.baseVersion
  229. );
  230. } );
  231. },
  232. ChangeOperation: doNotUpdate,
  233. // Transforms MoveOperation `a` by MoveOperation `b`. Accepts a flag stating whether `a` is more important
  234. // than `b` when it comes to resolving conflicts. Returns results as an array of operations.
  235. MoveOperation( a, b, isStrong ) {
  236. // There is a special case when both move operations' target positions are inside nodes that are
  237. // being moved by the other move operation. So in other words, we move ranges into inside of each other.
  238. // This case can't be solved reasonably (on the other hand, it should not happen often).
  239. if ( moveTargetIntoMovedRange( a, b ) && moveTargetIntoMovedRange( b, a ) ) {
  240. // Instead of transforming operation, we return a reverse of the operation that we transform by.
  241. // So when the results of this "transformation" will be applied, `b` MoveOperation will get reversed.
  242. return [ b.getReversed() ];
  243. }
  244. // Get target position from the state "after" nodes specified by other MoveOperation are "detached".
  245. const moveTargetPosition = b.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany );
  246. // This will aggregate transformed ranges.
  247. let ranges = [];
  248. // Create ranges from MoveOperations properties.
  249. const rangeA = Range.createFromPositionAndOffset( a.sourcePosition, a.howMany );
  250. const rangeB = Range.createFromPositionAndOffset( b.sourcePosition, b.howMany );
  251. const differenceSet = rangeA.getDifference( rangeB );
  252. // MoveOperations ranges may intersect.
  253. // First, we take care of that part of the range that is only modified by transformed operation.
  254. if ( differenceSet.length > 0 ) {
  255. const difference = differenceSet[ 0 ];
  256. // If two ranges were returned it means that rangeB was inside rangeA. We will cover rangeB later.
  257. // Right now we will make a simplification and join difference ranges and transform them as one.
  258. if ( differenceSet.length == 2 ) {
  259. difference.end = differenceSet[ 1 ].end.clone();
  260. }
  261. // MoveOperation removes nodes from their original position. We acknowledge this by proper transformation.
  262. // Take the start and the end of the range and transform them by deletion of moved nodes.
  263. // Note that if rangeB was inside rangeA, only difference.end will be transformed.
  264. // This nicely covers the joining simplification we did in the previous step.
  265. difference.start = difference.start.getTransformedByDeletion( b.sourcePosition, b.howMany );
  266. difference.end = difference.end.getTransformedByDeletion( b.sourcePosition, b.howMany );
  267. // MoveOperation pastes nodes into target position. We acknowledge this by proper transformation.
  268. // Note that since we operate on transformed difference range, we should transform by
  269. // previously transformed target position.
  270. ranges = difference.getTransformedByInsertion( moveTargetPosition, b.howMany, true );
  271. }
  272. // Then, we have to manage the common part of both move ranges.
  273. // If MoveOperations has common range it can be one of two:
  274. // * on the same tree level - it means that we move the same nodes into different places
  275. // * on deeper tree level - it means that we move nodes that are inside moved nodes
  276. // The operations are conflicting only if they try to move exactly same nodes, so only in the first case.
  277. // So, we will handle common range if it is "deeper" or if transformed operation is more important.
  278. let isDeeper = utils.compareArrays( b.sourcePosition.getParentPath(), a.sourcePosition.getParentPath() ) == utils.compareArrays.PREFIX;
  279. if ( isDeeper || isStrong ) {
  280. const common = rangeA.getIntersection( rangeB );
  281. if ( common !== null ) {
  282. // We substitute original position by the combination of target position and original position.
  283. // This reflects that those nodes were moved to another place by MoveOperation.
  284. common.start = common.start.getCombined( b.sourcePosition, moveTargetPosition );
  285. common.end = common.end.getCombined( b.sourcePosition, moveTargetPosition );
  286. ranges.push( common );
  287. }
  288. }
  289. // At this point we transformed this operation's source range. Now, we need to transform target position.
  290. // First, transform target position by deletion of the other operation's range.
  291. let newTargetPosition = a.targetPosition.getTransformedByDeletion( b.sourcePosition, b.howMany );
  292. if ( newTargetPosition === null ) {
  293. // Transformed operation target position was inside a node moved by the other MoveOperation.
  294. // We substitute that position by the combination of the other move target position and
  295. // transformed operation target position. This reflects changes done by the other MoveOperation.
  296. newTargetPosition = a.targetPosition.getCombined( b.sourcePosition, moveTargetPosition );
  297. } else {
  298. // Here we have transformed operation target position after some nodes has been removed by MoveOperation.
  299. // Next step is to reflect pasting nodes by MoveOperation, which might further affect the position.
  300. newTargetPosition = newTargetPosition.getTransformedByInsertion( moveTargetPosition, b.howMany, true );
  301. }
  302. // If we haven't got any ranges this far it means that both operations tried to move the same nodes and
  303. // transformed operation is less important. We return NoOperation in this case.
  304. if ( ranges.length === 0 ) {
  305. return [ new NoOperation( a.baseVersion ) ];
  306. }
  307. // At this point we might have multiple ranges. All ranges will be moved to the same, newTargetPosition.
  308. // To keep them in the right order, we need to move them starting from the last one.
  309. // [|ABC||DEF||GHI|] ==> [^], [|ABC||DEF|] ==> [^GHI], [|ABC|] ==> [^DEFGHI], [] ==> [ABCDEFGHI]
  310. // To achieve this, we sort ranges by their starting position in descending order.
  311. ranges.sort( ( a, b ) => a.start.isBefore( b.start ) ? 1 : -1 );
  312. // Map transformed range(s) to operations and return them.
  313. return ranges.map( ( range ) => {
  314. return new MoveOperation(
  315. range.start,
  316. newTargetPosition,
  317. range.end.offset - range.start.offset,
  318. a.baseVersion
  319. );
  320. } );
  321. }
  322. }
  323. };
  324. return ( a, b, isStrong ) => {
  325. let group;
  326. let algorithm;
  327. if ( a instanceof InsertOperation ) {
  328. group = ot.InsertOperation;
  329. } else if ( a instanceof ChangeOperation ) {
  330. group = ot.ChangeOperation;
  331. } else if ( a instanceof MoveOperation ) {
  332. group = ot.MoveOperation;
  333. } else {
  334. algorithm = doNotUpdate;
  335. }
  336. if ( group ) {
  337. if ( b instanceof InsertOperation ) {
  338. algorithm = group.InsertOperation;
  339. } else if ( b instanceof ChangeOperation ) {
  340. algorithm = group.ChangeOperation;
  341. } else if ( b instanceof MoveOperation ) {
  342. algorithm = group.MoveOperation;
  343. } else {
  344. algorithm = doNotUpdate;
  345. }
  346. }
  347. let transformed = algorithm( a, b, isStrong );
  348. return updateBaseVersions( a.baseVersion, transformed );
  349. };
  350. } );