transformoperation.js 20 KB

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