differ.js 33 KB

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