differ.js 34 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015
  1. /**
  2. * @license Copyright (c) 2003-2018, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. /**
  6. * @module engine/model/differ
  7. */
  8. import Position from './position';
  9. import Range from './range';
  10. /**
  11. * Calculates the difference between two model states.
  12. *
  13. * Receives operations that are to be applied on the model document. Marks parts of the model document tree which
  14. * are changed and saves the state of these elements before the change. Then, it compares saved elements with the
  15. * changed elements, after all changes are applied on the model document. Calculates the diff between saved
  16. * elements and new ones and returns a change set.
  17. */
  18. export default class Differ {
  19. /**
  20. * Creates a `Differ` instance.
  21. *
  22. * @param {module:engine/model/markercollection~MarkerCollection} markerCollection Model's marker collection.
  23. */
  24. constructor( markerCollection ) {
  25. /**
  26. * Reference to the model's marker collection.
  27. *
  28. * @private
  29. * @type {module:engine/model/markercollection~MarkerCollection}
  30. */
  31. this._markerCollection = markerCollection;
  32. /**
  33. * A map that stores changes that happened in a given element.
  34. *
  35. * The keys of the map are references to the model elements.
  36. * The values of the map are arrays with changes that were done on this element.
  37. *
  38. * @private
  39. * @type {Map}
  40. */
  41. this._changesInElement = new Map();
  42. /**
  43. * A map that stores "element's children snapshots". A snapshot is representing children of a given element before
  44. * the first change was applied on that element. Snapshot items are objects with two properties: `name`,
  45. * containing the element name (or `'$text'` for a text node) and `attributes` which is a map of the node's attributes.
  46. *
  47. * @private
  48. * @type {Map}
  49. */
  50. this._elementSnapshots = new Map();
  51. /**
  52. * A map that stores all changed markers.
  53. *
  54. * The keys of the map are marker names.
  55. * The values of the map are objects with the `oldRange` and `newRange` properties. They store the marker range
  56. * state before and after the change.
  57. *
  58. * @private
  59. * @type {Map}
  60. */
  61. this._changedMarkers = new Map();
  62. /**
  63. * Stores the number of changes that were processed. Used to order the changes chronologically. It is important
  64. * when changes are sorted.
  65. *
  66. * @private
  67. * @type {Number}
  68. */
  69. this._changeCount = 0;
  70. /**
  71. * For efficiency purposes, `Differ` stores the change set returned by the differ after {@link #getChanges} call.
  72. * Cache is reset each time a new operation is buffered. If the cache has not been reset, {@link #getChanges} will
  73. * return the cached value instead of calculating it again.
  74. *
  75. * This property stores those changes that did not take place in graveyard root.
  76. *
  77. * @private
  78. * @type {Array.<Object>|null}
  79. */
  80. this._cachedChanges = null;
  81. /**
  82. * For efficiency purposes, `Differ` stores the change set returned by the differ after the {@link #getChanges} call.
  83. * The cache is reset each time a new operation is buffered. If the cache has not been reset, {@link #getChanges} will
  84. * return the cached value instead of calculating it again.
  85. *
  86. * This property stores all changes evaluated by `Differ`, including those that took place in the graveyard.
  87. *
  88. * @private
  89. * @type {Array.<Object>|null}
  90. */
  91. this._cachedChangesWithGraveyard = null;
  92. }
  93. /**
  94. * Informs whether there are any changes buffered in `Differ`.
  95. *
  96. * @readonly
  97. * @type {Boolean}
  98. */
  99. get isEmpty() {
  100. return this._changesInElement.size == 0 && this._changedMarkers.size == 0;
  101. }
  102. /**
  103. * Buffers a given operation. An operation has to be buffered before it is executed.
  104. *
  105. * Operation type is checked and it is checked which nodes it will affect. These nodes are then stored in `Differ`
  106. * in the state before the operation is executed.
  107. *
  108. * @param {module:engine/model/operation/operation~Operation} operation An operation to buffer.
  109. */
  110. bufferOperation( operation ) {
  111. switch ( operation.type ) {
  112. case 'insert': {
  113. if ( this._isInInsertedElement( operation.position.parent ) ) {
  114. return;
  115. }
  116. this._markInsert( operation.position.parent, operation.position.offset, operation.nodes.maxOffset );
  117. break;
  118. }
  119. case 'addAttribute':
  120. case 'removeAttribute':
  121. case 'changeAttribute': {
  122. for ( const item of operation.range.getItems() ) {
  123. if ( this._isInInsertedElement( item.parent ) ) {
  124. continue;
  125. }
  126. this._markAttribute( item );
  127. }
  128. break;
  129. }
  130. case 'remove':
  131. case 'move':
  132. case 'reinsert': {
  133. const sourceParentInserted = this._isInInsertedElement( operation.sourcePosition.parent );
  134. const targetParentInserted = this._isInInsertedElement( operation.targetPosition.parent );
  135. if ( !sourceParentInserted ) {
  136. this._markRemove( operation.sourcePosition.parent, operation.sourcePosition.offset, operation.howMany );
  137. }
  138. if ( !targetParentInserted ) {
  139. this._markInsert( operation.targetPosition.parent, operation.getMovedRangeStart().offset, operation.howMany );
  140. }
  141. break;
  142. }
  143. case 'rename': {
  144. if ( this._isInInsertedElement( operation.position.parent ) ) {
  145. return;
  146. }
  147. this._markRemove( operation.position.parent, operation.position.offset, 1 );
  148. this._markInsert( operation.position.parent, operation.position.offset, 1 );
  149. const range = Range.createFromPositionAndShift( operation.position, 1 );
  150. for ( const marker of this._markerCollection.getMarkersIntersectingRange( range ) ) {
  151. const markerRange = marker.getRange();
  152. this.bufferMarkerChange( marker.name, markerRange, markerRange );
  153. }
  154. break;
  155. }
  156. }
  157. // Clear cache after each buffered operation as it is no longer valid.
  158. this._cachedChanges = null;
  159. }
  160. /**
  161. * Buffers marker change.
  162. *
  163. * @param {String} markerName The name of the marker that changed.
  164. * @param {module:engine/model/range~Range|null} oldRange Marker range before the change or `null` if the marker has just
  165. * been created.
  166. * @param {module:engine/model/range~Range|null} newRange Marker range after the change or `null` if the marker was removed.
  167. */
  168. bufferMarkerChange( markerName, oldRange, newRange ) {
  169. const buffered = this._changedMarkers.get( markerName );
  170. if ( !buffered ) {
  171. this._changedMarkers.set( markerName, {
  172. oldRange,
  173. newRange
  174. } );
  175. } else {
  176. buffered.newRange = newRange;
  177. if ( buffered.oldRange == null && buffered.newRange == null ) {
  178. // The marker is going to be removed (`newRange == null`) but it did not exist before the first buffered change
  179. // (`buffered.oldRange == null`). In this case, do not keep the marker in buffer at all.
  180. this._changedMarkers.delete( markerName );
  181. }
  182. }
  183. }
  184. /**
  185. * Returns all markers that should be removed as a result of buffered changes.
  186. *
  187. * @returns {Array.<Object>} Markers to remove. Each array item is an object containing the `name` and `range` properties.
  188. */
  189. getMarkersToRemove() {
  190. const result = [];
  191. for ( const [ name, change ] of this._changedMarkers ) {
  192. if ( change.oldRange != null ) {
  193. result.push( { name, range: change.oldRange } );
  194. }
  195. }
  196. return result;
  197. }
  198. /**
  199. * Returns all markers which should be added as a result of buffered changes.
  200. *
  201. * @returns {Array.<Object>} Markers to add. Each array item is an object containing the `name` and `range` properties.
  202. */
  203. getMarkersToAdd() {
  204. const result = [];
  205. for ( const [ name, change ] of this._changedMarkers ) {
  206. if ( change.newRange != null ) {
  207. result.push( { name, range: change.newRange } );
  208. }
  209. }
  210. return result;
  211. }
  212. /**
  213. * Calculates the diff between the old model tree state (the state before the first buffered operations since the last {@link #reset}
  214. * call) and the new model tree state (actual one). It should be called after all buffered operations are executed.
  215. *
  216. * The diff set is returned as an array of diff items, each describing a change done on the model. The items are sorted by
  217. * the position on which the change happened. If a position {@link module:engine/model/position~Position#isBefore is before}
  218. * another one, it will be on an earlier index in the diff set.
  219. *
  220. * Because calculating the diff is a costly operation, the result is cached. If no new operation was buffered since the
  221. * previous {@link #getChanges} call, the next call will return the cached value.
  222. *
  223. * @param {Object} options Additional options.
  224. * @param {Boolean} [options.includeChangesInGraveyard=false] If set to `true`, also changes that happened
  225. * in the graveyard root will be returned. By default, changes in the graveyard root are not returned.
  226. * @returns {Array.<Object>} Diff between the old and the new model tree state.
  227. */
  228. getChanges( options = { includeChangesInGraveyard: false } ) {
  229. // If there are cached changes, just return them instead of calculating changes again.
  230. if ( this._cachedChanges ) {
  231. if ( options.includeChangesInGraveyard ) {
  232. return this._cachedChangesWithGraveyard.slice();
  233. } else {
  234. return this._cachedChanges.slice();
  235. }
  236. }
  237. // Will contain returned results.
  238. const diffSet = [];
  239. // Check all changed elements.
  240. for ( const element of this._changesInElement.keys() ) {
  241. // Get changes for this element and sort them.
  242. const changes = this._changesInElement.get( element ).sort( ( a, b ) => {
  243. if ( a.offset === b.offset ) {
  244. if ( a.type != b.type ) {
  245. // If there are multiple changes at the same position, "remove" change should be first.
  246. // If the order is different, for example, we would first add some nodes and then removed them
  247. // (instead of the nodes that we should remove).
  248. return a.type == 'remove' ? -1 : 1;
  249. }
  250. return 0;
  251. }
  252. return a.offset < b.offset ? -1 : 1;
  253. } );
  254. // Get children of this element before any change was applied on it.
  255. const snapshotChildren = this._elementSnapshots.get( element );
  256. // Get snapshot of current element's children.
  257. const elementChildren = _getChildrenSnapshot( element.getChildren() );
  258. // Generate actions basing on changes done on element.
  259. const actions = _generateActionsFromChanges( snapshotChildren.length, changes );
  260. let i = 0; // Iterator in `elementChildren` array -- iterates through current children of element.
  261. let j = 0; // Iterator in `snapshotChildren` array -- iterates through old children of element.
  262. // Process every action.
  263. for ( const action of actions ) {
  264. if ( action === 'i' ) {
  265. // Generate diff item for this element and insert it into the diff set.
  266. diffSet.push( this._getInsertDiff( element, i, elementChildren[ i ].name ) );
  267. i++;
  268. } else if ( action === 'r' ) {
  269. // Generate diff item for this element and insert it into the diff set.
  270. diffSet.push( this._getRemoveDiff( element, i, snapshotChildren[ j ].name ) );
  271. j++;
  272. } else if ( action === 'a' ) {
  273. // Take attributes from saved and current children.
  274. const elementAttributes = elementChildren[ i ].attributes;
  275. const snapshotAttributes = snapshotChildren[ j ].attributes;
  276. let range;
  277. if ( elementChildren[ i ].name == '$text' ) {
  278. range = Range.createFromParentsAndOffsets( element, i, element, i + 1 );
  279. } else {
  280. const index = element.offsetToIndex( i );
  281. range = Range.createFromParentsAndOffsets( element, i, element.getChild( index ), 0 );
  282. }
  283. // Generate diff items for this change (there might be multiple attributes changed and
  284. // there is a single diff for each of them) and insert them into the diff set.
  285. diffSet.push( ...this._getAttributesDiff( range, snapshotAttributes, elementAttributes ) );
  286. i++;
  287. j++;
  288. } else {
  289. // `action` is 'equal'. Child not changed.
  290. i++;
  291. j++;
  292. }
  293. }
  294. }
  295. // Then, sort the changes by the position (change at position before other changes is first).
  296. diffSet.sort( ( a, b ) => {
  297. // If the change is in different root, we don't care much, but we'd like to have all changes in given
  298. // root "together" in the array. So let's just sort them by the root name. It does not matter which root
  299. // will be processed first.
  300. if ( a.position.root != b.position.root ) {
  301. return a.position.root.rootName < b.position.root.rootName ? -1 : 1;
  302. }
  303. // If change happens at the same position...
  304. if ( a.position.isEqual( b.position ) ) {
  305. // Keep chronological order of operations.
  306. return a.changeCount < b.changeCount ? -1 : 1;
  307. }
  308. // If positions differ, position "on the left" should be earlier in the result.
  309. return a.position.isBefore( b.position ) ? -1 : 1;
  310. } );
  311. // Glue together multiple changes (mostly on text nodes).
  312. for ( let i = 1; i < diffSet.length; i++ ) {
  313. const prevDiff = diffSet[ i - 1 ];
  314. const thisDiff = diffSet[ i ];
  315. // Glue remove changes if they happen on text on same position.
  316. const isConsecutiveTextRemove =
  317. prevDiff.type == 'remove' && thisDiff.type == 'remove' &&
  318. prevDiff.name == '$text' && thisDiff.name == '$text' &&
  319. prevDiff.position.isEqual( thisDiff.position );
  320. // Glue insert changes if they happen on text on consecutive fragments.
  321. const isConsecutiveTextAdd =
  322. prevDiff.type == 'insert' && thisDiff.type == 'insert' &&
  323. prevDiff.name == '$text' && thisDiff.name == '$text' &&
  324. prevDiff.position.parent == thisDiff.position.parent &&
  325. prevDiff.position.offset + prevDiff.length == thisDiff.position.offset;
  326. // Glue attribute changes if they happen on consecutive fragments and have same key, old value and new value.
  327. const isConsecutiveAttributeChange =
  328. prevDiff.type == 'attribute' && thisDiff.type == 'attribute' &&
  329. prevDiff.position.parent == thisDiff.position.parent &&
  330. prevDiff.range.isFlat && thisDiff.range.isFlat &&
  331. prevDiff.position.offset + prevDiff.length == thisDiff.position.offset &&
  332. prevDiff.attributeKey == thisDiff.attributeKey &&
  333. prevDiff.attributeOldValue == thisDiff.attributeOldValue &&
  334. prevDiff.attributeNewValue == thisDiff.attributeNewValue;
  335. if ( isConsecutiveTextRemove || isConsecutiveTextAdd || isConsecutiveAttributeChange ) {
  336. diffSet[ i - 1 ].length++;
  337. if ( isConsecutiveAttributeChange ) {
  338. diffSet[ i - 1 ].range.end = diffSet[ i - 1 ].range.end.getShiftedBy( 1 );
  339. }
  340. diffSet.splice( i, 1 );
  341. i--;
  342. }
  343. }
  344. // Remove `changeCount` property from diff items. It is used only for sorting and is internal thing.
  345. for ( const item of diffSet ) {
  346. delete item.changeCount;
  347. if ( item.type == 'attribute' ) {
  348. delete item.position;
  349. delete item.length;
  350. }
  351. }
  352. this._changeCount = 0;
  353. // Cache changes.
  354. this._cachedChangesWithGraveyard = diffSet.slice();
  355. this._cachedChanges = diffSet.slice().filter( _changesInGraveyardFilter );
  356. if ( options.includeChangesInGraveyard ) {
  357. return this._cachedChangesWithGraveyard;
  358. } else {
  359. return this._cachedChanges;
  360. }
  361. }
  362. /**
  363. * Resets `Differ`. Removes all buffered changes.
  364. */
  365. reset() {
  366. this._changesInElement.clear();
  367. this._elementSnapshots.clear();
  368. this._changedMarkers.clear();
  369. this._cachedChanges = null;
  370. }
  371. /**
  372. * Saves and handles an insert change.
  373. *
  374. * @private
  375. * @param {module:engine/model/element~Element} parent
  376. * @param {Number} offset
  377. * @param {Number} howMany
  378. */
  379. _markInsert( parent, offset, howMany ) {
  380. const changeItem = { type: 'insert', offset, howMany, count: this._changeCount++ };
  381. this._markChange( parent, changeItem );
  382. }
  383. /**
  384. * Saves and handles a remove change.
  385. *
  386. * @private
  387. * @param {module:engine/model/element~Element} parent
  388. * @param {Number} offset
  389. * @param {Number} howMany
  390. */
  391. _markRemove( parent, offset, howMany ) {
  392. const changeItem = { type: 'remove', offset, howMany, count: this._changeCount++ };
  393. this._markChange( parent, changeItem );
  394. this._removeAllNestedChanges( parent, offset, howMany );
  395. }
  396. /**
  397. * Saves and handles an attribute change.
  398. *
  399. * @private
  400. * @param {module:engine/model/item~Item} item
  401. */
  402. _markAttribute( item ) {
  403. const changeItem = { type: 'attribute', offset: item.startOffset, howMany: item.offsetSize, count: this._changeCount++ };
  404. this._markChange( item.parent, changeItem );
  405. }
  406. /**
  407. * Saves and handles a model change.
  408. *
  409. * @private
  410. * @param {module:engine/model/element~Element} parent
  411. * @param {Object} changeItem
  412. */
  413. _markChange( parent, changeItem ) {
  414. // First, make a snapshot of this parent's children (it will be made only if it was not made before).
  415. this._makeSnapshot( parent );
  416. // Then, get all changes that already were done on the element (empty array if this is the first change).
  417. const changes = this._getChangesForElement( parent );
  418. // Then, look through all the changes, and transform them or the new change.
  419. this._handleChange( changeItem, changes );
  420. // Add the new change.
  421. changes.push( changeItem );
  422. // Remove incorrect changes. During transformation some change might be, for example, included in another.
  423. // In that case, the change will have `howMany` property set to `0` or less. We need to remove those changes.
  424. for ( let i = 0; i < changes.length; i++ ) {
  425. if ( changes[ i ].howMany < 1 ) {
  426. changes.splice( i, 1 );
  427. i--;
  428. }
  429. }
  430. }
  431. /**
  432. * Gets an array of changes that have already been saved for a given element.
  433. *
  434. * @private
  435. * @param {module:engine/model/element~Element} element
  436. * @returns {Array.<Object>}
  437. */
  438. _getChangesForElement( element ) {
  439. let changes;
  440. if ( this._changesInElement.has( element ) ) {
  441. changes = this._changesInElement.get( element );
  442. } else {
  443. changes = [];
  444. this._changesInElement.set( element, changes );
  445. }
  446. return changes;
  447. }
  448. /**
  449. * Saves a children snapshot for a given element.
  450. *
  451. * @private
  452. * @param {module:engine/model/element~Element} element
  453. */
  454. _makeSnapshot( element ) {
  455. if ( !this._elementSnapshots.has( element ) ) {
  456. this._elementSnapshots.set( element, _getChildrenSnapshot( element.getChildren() ) );
  457. }
  458. }
  459. /**
  460. * For a given newly saved change, compares it with a change already done on the element and modifies the incoming
  461. * change and/or the old change.
  462. *
  463. * @private
  464. * @param {Object} inc Incoming (new) change.
  465. * @param {Array.<Object>} changes An array containing all the changes done on that element.
  466. */
  467. _handleChange( inc, changes ) {
  468. // We need a helper variable that will store how many nodes are to be still handled for this change item.
  469. // `nodesToHandle` (how many nodes still need to be handled) and `howMany` (how many nodes were affected)
  470. // needs to be differentiated.
  471. //
  472. // This comes up when there are multiple changes that are affected by `inc` change item.
  473. //
  474. // For example: assume two insert changes: `{ offset: 2, howMany: 1 }` and `{ offset: 5, howMany: 1 }`.
  475. // Assume that `inc` change is remove `{ offset: 2, howMany: 2, nodesToHandle: 2 }`.
  476. //
  477. // Then, we:
  478. // - "forget" about first insert change (it is "eaten" by remove),
  479. // - because of that, at the end we will want to remove only one node (`nodesToHandle = 1`),
  480. // - but still we have to change offset of the second insert change from `5` to `3`!
  481. //
  482. // So, `howMany` does not change throughout items transformation and keeps information about how many nodes were affected,
  483. // while `nodesToHandle` means how many nodes need to be handled after the change item is transformed by other changes.
  484. inc.nodesToHandle = inc.howMany;
  485. for ( const old of changes ) {
  486. const incEnd = inc.offset + inc.howMany;
  487. const oldEnd = old.offset + old.howMany;
  488. if ( inc.type == 'insert' ) {
  489. if ( old.type == 'insert' ) {
  490. if ( inc.offset <= old.offset ) {
  491. old.offset += inc.howMany;
  492. } else if ( inc.offset < oldEnd ) {
  493. old.howMany += inc.nodesToHandle;
  494. inc.nodesToHandle = 0;
  495. }
  496. }
  497. if ( old.type == 'remove' ) {
  498. if ( inc.offset < old.offset ) {
  499. old.offset += inc.howMany;
  500. }
  501. }
  502. if ( old.type == 'attribute' ) {
  503. if ( inc.offset <= old.offset ) {
  504. old.offset += inc.howMany;
  505. } else if ( inc.offset < oldEnd ) {
  506. // This case is more complicated, because attribute change has to be split into two.
  507. // Example (assume that uppercase and lowercase letters mean different attributes):
  508. //
  509. // initial state: abcxyz
  510. // attribute change: aBCXYz
  511. // incoming insert: aBCfooXYz
  512. //
  513. // Change ranges cannot intersect because each item has to be described exactly (it was either
  514. // not changed, inserted, removed, or its attribute was changed). That's why old attribute
  515. // change has to be split and both parts has to be handled separately from now on.
  516. const howMany = old.howMany;
  517. old.howMany = inc.offset - old.offset;
  518. // Add the second part of attribute change to the beginning of processed array so it won't
  519. // be processed again in this loop.
  520. changes.unshift( {
  521. type: 'attribute',
  522. offset: incEnd,
  523. howMany: howMany - old.howMany,
  524. count: this._changeCount++
  525. } );
  526. }
  527. }
  528. }
  529. if ( inc.type == 'remove' ) {
  530. if ( old.type == 'insert' ) {
  531. if ( incEnd <= old.offset ) {
  532. old.offset -= inc.howMany;
  533. } else if ( incEnd <= oldEnd ) {
  534. if ( inc.offset < old.offset ) {
  535. const intersectionLength = incEnd - old.offset;
  536. old.offset = inc.offset;
  537. old.howMany -= intersectionLength;
  538. inc.nodesToHandle -= intersectionLength;
  539. } else {
  540. old.howMany -= inc.nodesToHandle;
  541. inc.nodesToHandle = 0;
  542. }
  543. } else {
  544. if ( inc.offset <= old.offset ) {
  545. inc.nodesToHandle -= old.howMany;
  546. old.howMany = 0;
  547. } else if ( inc.offset < oldEnd ) {
  548. const intersectionLength = oldEnd - inc.offset;
  549. old.howMany -= intersectionLength;
  550. inc.nodesToHandle -= intersectionLength;
  551. }
  552. }
  553. }
  554. if ( old.type == 'remove' ) {
  555. if ( incEnd <= old.offset ) {
  556. old.offset -= inc.howMany;
  557. } else if ( inc.offset < old.offset ) {
  558. inc.nodesToHandle += old.howMany;
  559. old.howMany = 0;
  560. }
  561. }
  562. if ( old.type == 'attribute' ) {
  563. if ( incEnd <= old.offset ) {
  564. old.offset -= inc.howMany;
  565. } else if ( inc.offset < old.offset ) {
  566. const intersectionLength = incEnd - old.offset;
  567. old.offset = inc.offset;
  568. old.howMany -= intersectionLength;
  569. } else if ( inc.offset < oldEnd ) {
  570. if ( incEnd <= oldEnd ) {
  571. // On first sight in this case we don't need to split attribute operation into two.
  572. // However the changes set is later converted to actions (see `_generateActionsFromChanges`).
  573. // For that reason, no two changes may intersect.
  574. // So we cannot have an attribute change that "contains" remove change.
  575. // Attribute change needs to be split.
  576. const howMany = old.howMany;
  577. old.howMany = inc.offset - old.offset;
  578. const howManyAfter = howMany - old.howMany - inc.nodesToHandle;
  579. // Add the second part of attribute change to the beginning of processed array so it won't
  580. // be processed again in this loop.
  581. changes.unshift( {
  582. type: 'attribute',
  583. offset: inc.offset,
  584. howMany: howManyAfter,
  585. count: this._changeCount++
  586. } );
  587. } else {
  588. old.howMany -= oldEnd - inc.offset;
  589. }
  590. }
  591. }
  592. }
  593. if ( inc.type == 'attribute' ) {
  594. // In case of attribute change, `howMany` should be kept same as `nodesToHandle`. It's not an error.
  595. if ( old.type == 'insert' ) {
  596. if ( inc.offset < old.offset && incEnd > old.offset ) {
  597. if ( incEnd > oldEnd ) {
  598. // This case is similar to a case described when incoming change was insert and old change was attribute.
  599. // See comment above.
  600. //
  601. // This time incoming change is attribute. We need to split incoming change in this case too.
  602. // However this time, the second part of the attribute change needs to be processed further
  603. // because there might be other changes that it collides with.
  604. const attributePart = {
  605. type: 'attribute',
  606. offset: oldEnd,
  607. howMany: incEnd - oldEnd,
  608. count: this._changeCount++
  609. };
  610. this._handleChange( attributePart, changes );
  611. changes.push( attributePart );
  612. }
  613. inc.nodesToHandle = old.offset - inc.offset;
  614. inc.howMany = inc.nodesToHandle;
  615. } else if ( inc.offset >= old.offset && inc.offset < oldEnd ) {
  616. if ( incEnd > oldEnd ) {
  617. inc.nodesToHandle = incEnd - oldEnd;
  618. inc.offset = oldEnd;
  619. } else {
  620. inc.nodesToHandle = 0;
  621. }
  622. }
  623. }
  624. if ( old.type == 'attribute' ) {
  625. // There are only two conflicting scenarios possible here:
  626. if ( inc.offset >= old.offset && incEnd <= oldEnd ) {
  627. // `old` change includes `inc` change, or they are the same.
  628. inc.nodesToHandle = 0;
  629. inc.howMany = 0;
  630. inc.offset = 0;
  631. } else if ( inc.offset <= old.offset && incEnd >= oldEnd ) {
  632. // `inc` change includes `old` change.
  633. old.howMany = 0;
  634. }
  635. }
  636. }
  637. }
  638. inc.howMany = inc.nodesToHandle;
  639. delete inc.nodesToHandle;
  640. }
  641. /**
  642. * Returns an object with a single insert change description.
  643. *
  644. * @private
  645. * @param {module:engine/model/element~Element} parent The element in which the change happened.
  646. * @param {Number} offset The offset at which change happened.
  647. * @param {String} name The name of the removed element or `'$text'` for a character.
  648. * @returns {Object} The diff item.
  649. */
  650. _getInsertDiff( parent, offset, name ) {
  651. return {
  652. type: 'insert',
  653. position: Position.createFromParentAndOffset( parent, offset ),
  654. name,
  655. length: 1,
  656. changeCount: this._changeCount++
  657. };
  658. }
  659. /**
  660. * Returns an object with a single remove change description.
  661. *
  662. * @private
  663. * @param {module:engine/model/element~Element} parent The element in which change happened.
  664. * @param {Number} offset The offset at which change happened.
  665. * @param {String} name The name of the removed element or `'$text'` for a character.
  666. * @returns {Object} The diff item.
  667. */
  668. _getRemoveDiff( parent, offset, name ) {
  669. return {
  670. type: 'remove',
  671. position: Position.createFromParentAndOffset( parent, offset ),
  672. name,
  673. length: 1,
  674. changeCount: this._changeCount++
  675. };
  676. }
  677. /**
  678. * Returns an array of objects where each one is a single attribute change description.
  679. *
  680. * @private
  681. * @param {module:engine/model/range~Range} range The range where the change happened.
  682. * @param {Map} oldAttributes A map, map iterator or compatible object that contains attributes before the change.
  683. * @param {Map} newAttributes A map, map iterator or compatible object that contains attributes after the change.
  684. * @returns {Array.<Object>} An array containing one or more diff items.
  685. */
  686. _getAttributesDiff( range, oldAttributes, newAttributes ) {
  687. // Results holder.
  688. const diffs = [];
  689. // Clone new attributes as we will be performing changes on this object.
  690. newAttributes = new Map( newAttributes );
  691. // Look through old attributes.
  692. for ( const [ key, oldValue ] of oldAttributes ) {
  693. // Check what is the new value of the attribute (or if it was removed).
  694. const newValue = newAttributes.has( key ) ? newAttributes.get( key ) : null;
  695. // If values are different (or attribute was removed)...
  696. if ( newValue !== oldValue ) {
  697. // Add diff item.
  698. diffs.push( {
  699. type: 'attribute',
  700. position: range.start,
  701. range: Range.createFromRange( range ),
  702. length: 1,
  703. attributeKey: key,
  704. attributeOldValue: oldValue,
  705. attributeNewValue: newValue,
  706. changeCount: this._changeCount++
  707. } );
  708. }
  709. // Prevent returning two diff items for the same change.
  710. newAttributes.delete( key );
  711. }
  712. // Look through new attributes that weren't handled above.
  713. for ( const [ key, newValue ] of newAttributes ) {
  714. // Each of them is a new attribute. Add diff item.
  715. diffs.push( {
  716. type: 'attribute',
  717. position: range.start,
  718. range: Range.createFromRange( range ),
  719. length: 1,
  720. attributeKey: key,
  721. attributeOldValue: null,
  722. attributeNewValue: newValue,
  723. changeCount: this._changeCount++
  724. } );
  725. }
  726. return diffs;
  727. }
  728. /**
  729. * Checks whether given element or any of its parents is an element that is buffered as an inserted element.
  730. *
  731. * @private
  732. * @param {module:engine/model/element~Element} element Element to check.
  733. * @returns {Boolean}
  734. */
  735. _isInInsertedElement( element ) {
  736. const parent = element.parent;
  737. if ( !parent ) {
  738. return false;
  739. }
  740. const changes = this._changesInElement.get( parent );
  741. const offset = element.startOffset;
  742. if ( changes ) {
  743. for ( const change of changes ) {
  744. if ( change.type == 'insert' && offset >= change.offset && offset < change.offset + change.howMany ) {
  745. return true;
  746. }
  747. }
  748. }
  749. return this._isInInsertedElement( parent );
  750. }
  751. /**
  752. * Removes deeply all buffered changes that are registered in elements from range specified by `parent`, `offset`
  753. * and `howMany`.
  754. *
  755. * @private
  756. * @param {module:engine/model/element~Element} parent
  757. * @param {Number} offset
  758. * @param {Number} howMany
  759. */
  760. _removeAllNestedChanges( parent, offset, howMany ) {
  761. const range = Range.createFromParentsAndOffsets( parent, offset, parent, offset + howMany );
  762. for ( const item of range.getItems( { shallow: true } ) ) {
  763. if ( item.is( 'element' ) ) {
  764. this._elementSnapshots.delete( item );
  765. this._changesInElement.delete( item );
  766. this._removeAllNestedChanges( item, 0, item.maxOffset );
  767. }
  768. }
  769. }
  770. }
  771. // Returns an array that is a copy of passed child list with the exception that text nodes are split to one or more
  772. // objects, each representing one character and attributes set on that character.
  773. function _getChildrenSnapshot( children ) {
  774. const snapshot = [];
  775. for ( const child of children ) {
  776. if ( child.is( 'text' ) ) {
  777. for ( let i = 0; i < child.data.length; i++ ) {
  778. snapshot.push( {
  779. name: '$text',
  780. attributes: new Map( child.getAttributes() )
  781. } );
  782. }
  783. } else {
  784. snapshot.push( {
  785. name: child.name,
  786. attributes: new Map( child.getAttributes() )
  787. } );
  788. }
  789. }
  790. return snapshot;
  791. }
  792. // Generates array of actions for given changes set.
  793. // It simulates what `diff` function does.
  794. // Generated actions are:
  795. // - 'e' for 'equal' - when item at that position did not change,
  796. // - 'i' for 'insert' - when item at that position was inserted,
  797. // - 'r' for 'remove' - when item at that position was removed,
  798. // - 'a' for 'attribute' - when item at that position has it attributes changed.
  799. //
  800. // Example (assume that uppercase letters have bold attribute, compare with function code):
  801. //
  802. // children before: fooBAR
  803. // children after: foxybAR
  804. //
  805. // changes: type: remove, offset: 1, howMany: 1
  806. // type: insert, offset: 2, howMany: 2
  807. // type: attribute, offset: 4, howMany: 1
  808. //
  809. // expected actions: equal (f), remove (o), equal (o), insert (x), insert (y), attribute (b), equal (A), equal (R)
  810. //
  811. // steps taken by th script:
  812. //
  813. // 1. change = "type: remove, offset: 1, howMany: 1"; offset = 0; oldChildrenHandled = 0
  814. // 1.1 between this change and the beginning is one not-changed node, fill with one equal action, one old child has been handled
  815. // 1.2 this change removes one node, add one remove action
  816. // 1.3 change last visited `offset` to 1
  817. // 1.4 since an old child has been removed, one more old child has been handled
  818. // 1.5 actions at this point are: equal, remove
  819. //
  820. // 2. change = "type: insert, offset: 2, howMany: 2"; offset = 1; oldChildrenHandled = 2
  821. // 2.1 between this change and previous change is one not-changed node, add equal action, another one old children has been handled
  822. // 2.2 this change inserts two nodes, add two insert actions
  823. // 2.3 change last visited offset to the end of the inserted range, that is 4
  824. // 2.4 actions at this point are: equal, remove, equal, insert, insert
  825. //
  826. // 3. change = "type: attribute, offset: 4, howMany: 1"; offset = 4, oldChildrenHandled = 3
  827. // 3.1 between this change and previous change are no not-changed nodes
  828. // 3.2 this change changes one node, add one attribute action
  829. // 3.3 change last visited `offset` to the end of change range, that is 5
  830. // 3.4 since an old child has been changed, one more old child has been handled
  831. // 3.5 actions at this point are: equal, remove, equal, insert, insert, attribute
  832. //
  833. // 4. after loop oldChildrenHandled = 4, oldChildrenLength = 6 (fooBAR is 6 characters)
  834. // 4.1 fill up with two equal actions
  835. //
  836. // The result actions are: equal, remove, equal, insert, insert, attribute, equal, equal.
  837. function _generateActionsFromChanges( oldChildrenLength, changes ) {
  838. const actions = [];
  839. let offset = 0;
  840. let oldChildrenHandled = 0;
  841. // Go through all buffered changes.
  842. for ( const change of changes ) {
  843. // First, fill "holes" between changes with "equal" actions.
  844. if ( change.offset > offset ) {
  845. actions.push( ...'e'.repeat( change.offset - offset ).split( '' ) );
  846. oldChildrenHandled += change.offset - offset;
  847. }
  848. // Then, fill up actions accordingly to change type.
  849. if ( change.type == 'insert' ) {
  850. actions.push( ...'i'.repeat( change.howMany ).split( '' ) );
  851. // The last handled offset is after inserted range.
  852. offset = change.offset + change.howMany;
  853. } else if ( change.type == 'remove' ) {
  854. actions.push( ...'r'.repeat( change.howMany ).split( '' ) );
  855. // The last handled offset is at the position where the nodes were removed.
  856. offset = change.offset;
  857. // We removed `howMany` old nodes, update `oldChildrenHandled`.
  858. oldChildrenHandled += change.howMany;
  859. } else {
  860. actions.push( ...'a'.repeat( change.howMany ).split( '' ) );
  861. // The last handled offset isa at the position after the changed range.
  862. offset = change.offset + change.howMany;
  863. // We changed `howMany` old nodes, update `oldChildrenHandled`.
  864. oldChildrenHandled += change.howMany;
  865. }
  866. }
  867. // Fill "equal" actions at the end of actions set. Use `oldChildrenHandled` to see how many children
  868. // has not been changed / removed at the end of their parent.
  869. if ( oldChildrenHandled < oldChildrenLength ) {
  870. actions.push( ...'e'.repeat( oldChildrenLength - oldChildrenHandled ).split( '' ) );
  871. }
  872. return actions;
  873. }
  874. // Filter callback for Array.filter that filters out change entries that are in graveyard.
  875. function _changesInGraveyardFilter( entry ) {
  876. const posInGy = entry.position && entry.position.root.rootName == '$graveyard';
  877. const rangeInGy = entry.range && entry.range.root.rootName == '$graveyard';
  878. return !posInGy && !rangeInGy;
  879. }