8
0

differ.js 42 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272
  1. /**
  2. * @license Copyright (c) 2003-2020, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md or https://ckeditor.com/legal/ckeditor-oss-license
  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. * Marks given `item` in differ to be "refreshed". It means that the item will be marked as removed and inserted in the differ changes
  104. * set, so it will be effectively re-converted when differ changes will be handled by a dispatcher.
  105. *
  106. * @param {module:engine/model/item~Item} item Item to refresh.
  107. */
  108. refreshItem( item ) {
  109. if ( this._isInInsertedElement( item.parent ) ) {
  110. return;
  111. }
  112. this._markRemove( item.parent, item.startOffset, item.offsetSize );
  113. this._markInsert( item.parent, item.startOffset, item.offsetSize );
  114. const range = Range._createOn( item );
  115. for ( const marker of this._markerCollection.getMarkersIntersectingRange( range ) ) {
  116. const markerRange = marker.getRange();
  117. this.bufferMarkerChange( marker.name, markerRange, markerRange, marker.affectsData );
  118. }
  119. // Clear cache after each buffered operation as it is no longer valid.
  120. this._cachedChanges = null;
  121. }
  122. _pocRefreshItem( item ) {
  123. if ( this._isInInsertedElement( item.parent ) ) {
  124. return;
  125. }
  126. this._markRefresh( item.parent, item.startOffset, item.offsetSize );
  127. // @todo: Probably makes sense - check later.
  128. const range = Range._createOn( item );
  129. for ( const marker of this._markerCollection.getMarkersIntersectingRange( range ) ) {
  130. const markerRange = marker.getRange();
  131. this.bufferMarkerChange( marker.name, markerRange, markerRange, marker.affectsData );
  132. }
  133. // Clear cache after each buffered operation as it is no longer valid.
  134. this._cachedChanges = null;
  135. }
  136. /**
  137. * Buffers the given operation. An operation has to be buffered before it is executed.
  138. *
  139. * Operation type is checked and it is checked which nodes it will affect. These nodes are then stored in `Differ`
  140. * in the state before the operation is executed.
  141. *
  142. * @param {module:engine/model/operation/operation~Operation} operation An operation to buffer.
  143. */
  144. bufferOperation( operation ) {
  145. // Below we take an operation, check its type, then use its parameters in marking (private) methods.
  146. // The general rule is to not mark elements inside inserted element. All inserted elements are re-rendered.
  147. // Marking changes in them would cause a "double" changing then.
  148. //
  149. switch ( operation.type ) {
  150. case 'insert': {
  151. if ( this._isInInsertedElement( operation.position.parent ) || this._isInRefreshedElement( operation.position.parent ) ) {
  152. return;
  153. }
  154. this._markInsert( operation.position.parent, operation.position.offset, operation.nodes.maxOffset );
  155. break;
  156. }
  157. case 'addAttribute':
  158. case 'removeAttribute':
  159. case 'changeAttribute': {
  160. for ( const item of operation.range.getItems( { shallow: true } ) ) {
  161. // Attribute change on refreshed element is ignored
  162. // TODO: this is wrong if attribute would be handled elsewhere: || this._isInRefreshedElement( item )
  163. if ( this._isInInsertedElement( item.parent ) || this._isInRefreshedElement( item ) ) {
  164. continue;
  165. }
  166. this._markAttribute( item );
  167. }
  168. break;
  169. }
  170. case 'remove':
  171. case 'move':
  172. case 'reinsert': {
  173. // When range is moved to the same position then not mark it as a change.
  174. // See: https://github.com/ckeditor/ckeditor5-engine/issues/1664.
  175. if (
  176. operation.sourcePosition.isEqual( operation.targetPosition ) ||
  177. operation.sourcePosition.getShiftedBy( operation.howMany ).isEqual( operation.targetPosition )
  178. ) {
  179. return;
  180. }
  181. const sourceParentInserted = this._isInInsertedElement( operation.sourcePosition.parent );
  182. const targetParentInserted = this._isInInsertedElement( operation.targetPosition.parent );
  183. const sourceParentRefreshed = this._isInRefreshedElement( operation.sourcePosition.parent );
  184. const targetParentRefreshed = this._isInRefreshedElement( operation.sourcePosition.parent );
  185. if ( !sourceParentInserted && !sourceParentRefreshed ) {
  186. this._markRemove( operation.sourcePosition.parent, operation.sourcePosition.offset, operation.howMany );
  187. }
  188. if ( !targetParentInserted && !targetParentRefreshed ) {
  189. this._markInsert( operation.targetPosition.parent, operation.getMovedRangeStart().offset, operation.howMany );
  190. }
  191. break;
  192. }
  193. case 'rename': {
  194. if ( this._isInInsertedElement( operation.position.parent ) ) {
  195. return;
  196. }
  197. this._markRemove( operation.position.parent, operation.position.offset, 1 );
  198. this._markInsert( operation.position.parent, operation.position.offset, 1 );
  199. const range = Range._createFromPositionAndShift( operation.position, 1 );
  200. for ( const marker of this._markerCollection.getMarkersIntersectingRange( range ) ) {
  201. const markerRange = marker.getRange();
  202. this.bufferMarkerChange( marker.name, markerRange, markerRange, marker.affectsData );
  203. }
  204. break;
  205. }
  206. case 'split': {
  207. const splitElement = operation.splitPosition.parent;
  208. // Mark that children of the split element were removed.
  209. if ( !this._isInInsertedElement( splitElement ) ) {
  210. this._markRemove( splitElement, operation.splitPosition.offset, operation.howMany );
  211. }
  212. // Mark that the new element (split copy) was inserted.
  213. if ( !this._isInInsertedElement( operation.insertionPosition.parent ) ) {
  214. this._markInsert( operation.insertionPosition.parent, operation.insertionPosition.offset, 1 );
  215. }
  216. // If the split took the element from the graveyard, mark that the element from the graveyard was removed.
  217. if ( operation.graveyardPosition ) {
  218. this._markRemove( operation.graveyardPosition.parent, operation.graveyardPosition.offset, 1 );
  219. }
  220. break;
  221. }
  222. case 'merge': {
  223. // Mark that the merged element was removed.
  224. const mergedElement = operation.sourcePosition.parent;
  225. if ( !this._isInInsertedElement( mergedElement.parent ) ) {
  226. this._markRemove( mergedElement.parent, mergedElement.startOffset, 1 );
  227. }
  228. // Mark that the merged element was inserted into graveyard.
  229. const graveyardParent = operation.graveyardPosition.parent;
  230. this._markInsert( graveyardParent, operation.graveyardPosition.offset, 1 );
  231. // Mark that children of merged element were inserted at new parent.
  232. const mergedIntoElement = operation.targetPosition.parent;
  233. if ( !this._isInInsertedElement( mergedIntoElement ) ) {
  234. this._markInsert( mergedIntoElement, operation.targetPosition.offset, mergedElement.maxOffset );
  235. }
  236. break;
  237. }
  238. }
  239. // Clear cache after each buffered operation as it is no longer valid.
  240. this._cachedChanges = null;
  241. }
  242. /**
  243. * Buffers a marker change.
  244. *
  245. * @param {String} markerName The name of the marker that changed.
  246. * @param {module:engine/model/range~Range|null} oldRange Marker range before the change or `null` if the marker has just
  247. * been created.
  248. * @param {module:engine/model/range~Range|null} newRange Marker range after the change or `null` if the marker was removed.
  249. * @param {Boolean} affectsData Flag indicating whether marker affects the editor data.
  250. */
  251. bufferMarkerChange( markerName, oldRange, newRange, affectsData ) {
  252. const buffered = this._changedMarkers.get( markerName );
  253. if ( !buffered ) {
  254. this._changedMarkers.set( markerName, {
  255. oldRange,
  256. newRange,
  257. affectsData
  258. } );
  259. } else {
  260. buffered.newRange = newRange;
  261. buffered.affectsData = affectsData;
  262. if ( buffered.oldRange == null && buffered.newRange == null ) {
  263. // The marker is going to be removed (`newRange == null`) but it did not exist before the first buffered change
  264. // (`buffered.oldRange == null`). In this case, do not keep the marker in buffer at all.
  265. this._changedMarkers.delete( markerName );
  266. }
  267. }
  268. }
  269. /**
  270. * Returns all markers that should be removed as a result of buffered changes.
  271. *
  272. * @returns {Array.<Object>} Markers to remove. Each array item is an object containing the `name` and `range` properties.
  273. */
  274. getMarkersToRemove() {
  275. const result = [];
  276. for ( const [ name, change ] of this._changedMarkers ) {
  277. if ( change.oldRange != null ) {
  278. result.push( { name, range: change.oldRange } );
  279. }
  280. }
  281. return result;
  282. }
  283. /**
  284. * Returns all markers which should be added as a result of buffered changes.
  285. *
  286. * @returns {Array.<Object>} Markers to add. Each array item is an object containing the `name` and `range` properties.
  287. */
  288. getMarkersToAdd() {
  289. const result = [];
  290. for ( const [ name, change ] of this._changedMarkers ) {
  291. if ( change.newRange != null ) {
  292. result.push( { name, range: change.newRange } );
  293. }
  294. }
  295. return result;
  296. }
  297. /**
  298. * Returns all markers which changed.
  299. *
  300. * @returns {Array.<Object>}
  301. */
  302. getChangedMarkers() {
  303. return Array.from( this._changedMarkers ).map( item => (
  304. {
  305. name: item[ 0 ],
  306. data: {
  307. oldRange: item[ 1 ].oldRange,
  308. newRange: item[ 1 ].newRange
  309. }
  310. }
  311. ) );
  312. }
  313. /**
  314. * Checks whether some of the buffered changes affect the editor data.
  315. *
  316. * Types of changes which affect the editor data:
  317. *
  318. * * model structure changes,
  319. * * attribute changes,
  320. * * changes of markers which were defined as `affectingData`.
  321. *
  322. * @returns {Boolean}
  323. */
  324. hasDataChanges() {
  325. for ( const [ , change ] of this._changedMarkers ) {
  326. if ( change.affectsData ) {
  327. return true;
  328. }
  329. }
  330. // If markers do not affect the data, check whether there are some changes in elements.
  331. return this._changesInElement.size > 0;
  332. }
  333. /**
  334. * Calculates the diff between the old model tree state (the state before the first buffered operations since the last {@link #reset}
  335. * call) and the new model tree state (actual one). It should be called after all buffered operations are executed.
  336. *
  337. * The diff set is returned as an array of diff items, each describing a change done on the model. The items are sorted by
  338. * the position on which the change happened. If a position {@link module:engine/model/position~Position#isBefore is before}
  339. * another one, it will be on an earlier index in the diff set.
  340. *
  341. * Because calculating the diff is a costly operation, the result is cached. If no new operation was buffered since the
  342. * previous {@link #getChanges} call, the next call will return the cached value.
  343. *
  344. * @param {Object} options Additional options.
  345. * @param {Boolean} [options.includeChangesInGraveyard=false] If set to `true`, also changes that happened
  346. * in the graveyard root will be returned. By default, changes in the graveyard root are not returned.
  347. * @returns {Array.<Object>} Diff between the old and the new model tree state.
  348. */
  349. getChanges( options = { includeChangesInGraveyard: false } ) {
  350. // If there are cached changes, just return them instead of calculating changes again.
  351. if ( this._cachedChanges ) {
  352. if ( options.includeChangesInGraveyard ) {
  353. return this._cachedChangesWithGraveyard.slice();
  354. } else {
  355. return this._cachedChanges.slice();
  356. }
  357. }
  358. // Will contain returned results.
  359. const diffSet = [];
  360. // Check all changed elements.
  361. for ( const element of this._changesInElement.keys() ) {
  362. // Get changes for this element and sort them.
  363. const changes = this._changesInElement.get( element ).sort( ( a, b ) => {
  364. if ( a.offset === b.offset ) {
  365. if ( a.type != b.type ) {
  366. // If there are multiple changes at the same position, "remove" change should be first.
  367. // If the order is different, for example, we would first add some nodes and then removed them
  368. // (instead of the nodes that we should remove).
  369. return a.type == 'remove' ? -1 : 1;
  370. }
  371. return 0;
  372. }
  373. return a.offset < b.offset ? -1 : 1;
  374. } );
  375. // Get children of this element before any change was applied on it.
  376. const snapshotChildren = this._elementSnapshots.get( element );
  377. // Get snapshot of current element's children.
  378. const elementChildren = _getChildrenSnapshot( element.getChildren() );
  379. // Generate actions basing on changes done on element.
  380. const actions = _generateActionsFromChanges( snapshotChildren.length, changes );
  381. let i = 0; // Iterator in `elementChildren` array -- iterates through current children of element.
  382. let j = 0; // Iterator in `snapshotChildren` array -- iterates through old children of element.
  383. // console.log( changes.map( change => change.type ) );
  384. // console.log( 'actions', actions, elementChildren.length );
  385. // Process every action.
  386. for ( const action of actions ) {
  387. if ( action === 'i' ) {
  388. // Generate diff item for this element and insert it into the diff set.
  389. diffSet.push( this._getInsertDiff( element, i, elementChildren[ i ].name ) );
  390. i++;
  391. } else if ( action === 'r' ) {
  392. // Generate diff item for this element and insert it into the diff set.
  393. diffSet.push( this._getRemoveDiff( element, i, snapshotChildren[ j ].name ) );
  394. j++;
  395. } else if ( action === 'a' ) {
  396. // Take attributes from saved and current children.
  397. const elementAttributes = elementChildren[ i ].attributes;
  398. const snapshotAttributes = snapshotChildren[ j ].attributes;
  399. let range;
  400. if ( elementChildren[ i ].name == '$text' ) {
  401. range = new Range( Position._createAt( element, i ), Position._createAt( element, i + 1 ) );
  402. } else {
  403. const index = element.offsetToIndex( i );
  404. range = new Range( Position._createAt( element, i ), Position._createAt( element.getChild( index ), 0 ) );
  405. }
  406. // Generate diff items for this change (there might be multiple attributes changed and
  407. // there is a single diff for each of them) and insert them into the diff set.
  408. diffSet.push( ...this._getAttributesDiff( range, snapshotAttributes, elementAttributes ) );
  409. i++;
  410. j++;
  411. } else if ( action === 'x' ) {
  412. // Swap action - similar to 'equal'.
  413. diffSet.push( this._getRefreshDiff( element, i, elementChildren[ i ].name ) );
  414. i++;
  415. j++;
  416. } else {
  417. // `action` is 'equal'. Child not changed.
  418. i++;
  419. j++;
  420. }
  421. }
  422. }
  423. // Then, sort the changes by the position (change at position before other changes is first).
  424. diffSet.sort( ( a, b ) => {
  425. // If the change is in different root, we don't care much, but we'd like to have all changes in given
  426. // root "together" in the array. So let's just sort them by the root name. It does not matter which root
  427. // will be processed first.
  428. if ( a.position.root != b.position.root ) {
  429. return a.position.root.rootName < b.position.root.rootName ? -1 : 1;
  430. }
  431. // If change happens at the same position...
  432. if ( a.position.isEqual( b.position ) ) {
  433. // Keep chronological order of operations.
  434. return a.changeCount - b.changeCount;
  435. }
  436. // If positions differ, position "on the left" should be earlier in the result.
  437. return a.position.isBefore( b.position ) ? -1 : 1;
  438. } );
  439. // Glue together multiple changes (mostly on text nodes).
  440. for ( let i = 1; i < diffSet.length; i++ ) {
  441. const prevDiff = diffSet[ i - 1 ];
  442. const thisDiff = diffSet[ i ];
  443. // Glue remove changes if they happen on text on same position.
  444. const isConsecutiveTextRemove =
  445. prevDiff.type == 'remove' && thisDiff.type == 'remove' &&
  446. prevDiff.name == '$text' && thisDiff.name == '$text' &&
  447. prevDiff.position.isEqual( thisDiff.position );
  448. // Glue insert changes if they happen on text on consecutive fragments.
  449. const isConsecutiveTextAdd =
  450. prevDiff.type == 'insert' && thisDiff.type == 'insert' &&
  451. prevDiff.name == '$text' && thisDiff.name == '$text' &&
  452. prevDiff.position.parent == thisDiff.position.parent &&
  453. prevDiff.position.offset + prevDiff.length == thisDiff.position.offset;
  454. // Glue attribute changes if they happen on consecutive fragments and have same key, old value and new value.
  455. const isConsecutiveAttributeChange =
  456. prevDiff.type == 'attribute' && thisDiff.type == 'attribute' &&
  457. prevDiff.position.parent == thisDiff.position.parent &&
  458. prevDiff.range.isFlat && thisDiff.range.isFlat &&
  459. prevDiff.position.offset + prevDiff.length == thisDiff.position.offset &&
  460. prevDiff.attributeKey == thisDiff.attributeKey &&
  461. prevDiff.attributeOldValue == thisDiff.attributeOldValue &&
  462. prevDiff.attributeNewValue == thisDiff.attributeNewValue;
  463. if ( isConsecutiveTextRemove || isConsecutiveTextAdd || isConsecutiveAttributeChange ) {
  464. diffSet[ i - 1 ].length++;
  465. if ( isConsecutiveAttributeChange ) {
  466. diffSet[ i - 1 ].range.end = diffSet[ i - 1 ].range.end.getShiftedBy( 1 );
  467. }
  468. diffSet.splice( i, 1 );
  469. i--;
  470. }
  471. }
  472. // Remove `changeCount` property from diff items. It is used only for sorting and is internal thing.
  473. for ( const item of diffSet ) {
  474. delete item.changeCount;
  475. if ( item.type == 'attribute' ) {
  476. delete item.position;
  477. delete item.length;
  478. }
  479. }
  480. this._changeCount = 0;
  481. // Cache changes.
  482. this._cachedChangesWithGraveyard = diffSet;
  483. this._cachedChanges = diffSet.filter( _changesInGraveyardFilter );
  484. if ( options.includeChangesInGraveyard ) {
  485. return this._cachedChangesWithGraveyard.slice();
  486. } else {
  487. return this._cachedChanges.slice();
  488. }
  489. }
  490. /**
  491. * Resets `Differ`. Removes all buffered changes.
  492. */
  493. reset() {
  494. this._changesInElement.clear();
  495. this._elementSnapshots.clear();
  496. this._changedMarkers.clear();
  497. this._cachedChanges = null;
  498. }
  499. /**
  500. * Saves and handles an insert change.
  501. *
  502. * @private
  503. * @param {module:engine/model/element~Element} parent
  504. * @param {Number} offset
  505. * @param {Number} howMany
  506. */
  507. _markInsert( parent, offset, howMany ) {
  508. const changeItem = { type: 'insert', offset, howMany, count: this._changeCount++ };
  509. this._markChange( parent, changeItem );
  510. }
  511. /**
  512. * Saves and handles a remove change.
  513. *
  514. * @private
  515. * @param {module:engine/model/element~Element} parent
  516. * @param {Number} offset
  517. * @param {Number} howMany
  518. */
  519. _markRemove( parent, offset, howMany ) {
  520. const changeItem = { type: 'remove', offset, howMany, count: this._changeCount++ };
  521. this._markChange( parent, changeItem );
  522. this._removeAllNestedChanges( parent, offset, howMany );
  523. }
  524. _markRefresh( parent, offset, howMany ) {
  525. const changeItem = { type: 'refresh', offset, howMany, count: this._changeCount++ };
  526. this._markChange( parent, changeItem );
  527. // Needed to remove "attribute" change or other.
  528. // @todo: might need to retain "slot" changes.
  529. this._removeAllNestedAttributeChanges( parent, offset, howMany );
  530. }
  531. /**
  532. * Saves and handles an attribute change.
  533. *
  534. * @private
  535. * @param {module:engine/model/item~Item} item
  536. */
  537. _markAttribute( item ) {
  538. const changeItem = { type: 'attribute', offset: item.startOffset, howMany: item.offsetSize, count: this._changeCount++ };
  539. this._markChange( item.parent, changeItem );
  540. }
  541. /**
  542. * Saves and handles a model change.
  543. *
  544. * @private
  545. * @param {module:engine/model/element~Element} parent
  546. * @param {Object} changeItem
  547. */
  548. _markChange( parent, changeItem ) {
  549. // First, make a snapshot of this parent's children (it will be made only if it was not made before).
  550. this._makeSnapshot( parent );
  551. // Then, get all changes that already were done on the element (empty array if this is the first change).
  552. const changes = this._getChangesForElement( parent );
  553. // Then, look through all the changes, and transform them or the new change.
  554. this._handleChange( changeItem, changes );
  555. // Add the new change.
  556. changes.push( changeItem );
  557. // Remove incorrect changes. During transformation some change might be, for example, included in another.
  558. // In that case, the change will have `howMany` property set to `0` or less. We need to remove those changes.
  559. for ( let i = 0; i < changes.length; i++ ) {
  560. if ( changes[ i ].howMany < 1 ) {
  561. changes.splice( i, 1 );
  562. i--;
  563. }
  564. }
  565. }
  566. /**
  567. * Gets an array of changes that have already been saved for a given element.
  568. *
  569. * @private
  570. * @param {module:engine/model/element~Element} element
  571. * @returns {Array.<Object>}
  572. */
  573. _getChangesForElement( element ) {
  574. let changes;
  575. if ( this._changesInElement.has( element ) ) {
  576. changes = this._changesInElement.get( element );
  577. } else {
  578. changes = [];
  579. this._changesInElement.set( element, changes );
  580. }
  581. return changes;
  582. }
  583. /**
  584. * Saves a children snapshot for a given element.
  585. *
  586. * @private
  587. * @param {module:engine/model/element~Element} element
  588. */
  589. _makeSnapshot( element ) {
  590. if ( !this._elementSnapshots.has( element ) ) {
  591. this._elementSnapshots.set( element, _getChildrenSnapshot( element.getChildren() ) );
  592. }
  593. }
  594. /**
  595. * For a given newly saved change, compares it with a change already done on the element and modifies the incoming
  596. * change and/or the old change.
  597. *
  598. * @private
  599. * @param {Object} inc Incoming (new) change.
  600. * @param {Array.<Object>} changes An array containing all the changes done on that element.
  601. */
  602. _handleChange( inc, changes ) {
  603. // We need a helper variable that will store how many nodes are to be still handled for this change item.
  604. // `nodesToHandle` (how many nodes still need to be handled) and `howMany` (how many nodes were affected)
  605. // needs to be differentiated.
  606. //
  607. // This comes up when there are multiple changes that are affected by `inc` change item.
  608. //
  609. // For example: assume two insert changes: `{ offset: 2, howMany: 1 }` and `{ offset: 5, howMany: 1 }`.
  610. // Assume that `inc` change is remove `{ offset: 2, howMany: 2, nodesToHandle: 2 }`.
  611. //
  612. // Then, we:
  613. // - "forget" about first insert change (it is "eaten" by remove),
  614. // - because of that, at the end we will want to remove only one node (`nodesToHandle = 1`),
  615. // - but still we have to change offset of the second insert change from `5` to `3`!
  616. //
  617. // So, `howMany` does not change throughout items transformation and keeps information about how many nodes were affected,
  618. // while `nodesToHandle` means how many nodes need to be handled after the change item is transformed by other changes.
  619. inc.nodesToHandle = inc.howMany;
  620. for ( const old of changes ) {
  621. const incEnd = inc.offset + inc.howMany;
  622. const oldEnd = old.offset + old.howMany;
  623. if ( inc.type == 'insert' ) {
  624. if ( old.type == 'insert' ) {
  625. if ( inc.offset <= old.offset ) {
  626. old.offset += inc.howMany;
  627. } else if ( inc.offset < oldEnd ) {
  628. old.howMany += inc.nodesToHandle;
  629. inc.nodesToHandle = 0;
  630. }
  631. }
  632. if ( old.type == 'remove' ) {
  633. if ( inc.offset < old.offset ) {
  634. old.offset += inc.howMany;
  635. }
  636. }
  637. if ( old.type == 'attribute' ) {
  638. if ( inc.offset <= old.offset ) {
  639. old.offset += inc.howMany;
  640. } else if ( inc.offset < oldEnd ) {
  641. // This case is more complicated, because attribute change has to be split into two.
  642. // Example (assume that uppercase and lowercase letters mean different attributes):
  643. //
  644. // initial state: abcxyz
  645. // attribute change: aBCXYz
  646. // incoming insert: aBCfooXYz
  647. //
  648. // Change ranges cannot intersect because each item has to be described exactly (it was either
  649. // not changed, inserted, removed, or its attribute was changed). That's why old attribute
  650. // change has to be split and both parts has to be handled separately from now on.
  651. const howMany = old.howMany;
  652. old.howMany = inc.offset - old.offset;
  653. // Add the second part of attribute change to the beginning of processed array so it won't
  654. // be processed again in this loop.
  655. changes.unshift( {
  656. type: 'attribute',
  657. offset: incEnd,
  658. howMany: howMany - old.howMany,
  659. count: this._changeCount++
  660. } );
  661. }
  662. }
  663. }
  664. if ( inc.type == 'remove' ) {
  665. if ( old.type == 'insert' ) {
  666. if ( incEnd <= old.offset ) {
  667. old.offset -= inc.howMany;
  668. } else if ( incEnd <= oldEnd ) {
  669. if ( inc.offset < old.offset ) {
  670. const intersectionLength = incEnd - old.offset;
  671. old.offset = inc.offset;
  672. old.howMany -= intersectionLength;
  673. inc.nodesToHandle -= intersectionLength;
  674. } else {
  675. old.howMany -= inc.nodesToHandle;
  676. inc.nodesToHandle = 0;
  677. }
  678. } else {
  679. if ( inc.offset <= old.offset ) {
  680. inc.nodesToHandle -= old.howMany;
  681. old.howMany = 0;
  682. } else if ( inc.offset < oldEnd ) {
  683. const intersectionLength = oldEnd - inc.offset;
  684. old.howMany -= intersectionLength;
  685. inc.nodesToHandle -= intersectionLength;
  686. }
  687. }
  688. }
  689. if ( old.type == 'remove' ) {
  690. if ( incEnd <= old.offset ) {
  691. old.offset -= inc.howMany;
  692. } else if ( inc.offset < old.offset ) {
  693. inc.nodesToHandle += old.howMany;
  694. old.howMany = 0;
  695. }
  696. }
  697. if ( old.type == 'attribute' ) {
  698. if ( incEnd <= old.offset ) {
  699. old.offset -= inc.howMany;
  700. } else if ( inc.offset < old.offset ) {
  701. const intersectionLength = incEnd - old.offset;
  702. old.offset = inc.offset;
  703. old.howMany -= intersectionLength;
  704. } else if ( inc.offset < oldEnd ) {
  705. if ( incEnd <= oldEnd ) {
  706. // On first sight in this case we don't need to split attribute operation into two.
  707. // However the changes set is later converted to actions (see `_generateActionsFromChanges`).
  708. // For that reason, no two changes may intersect.
  709. // So we cannot have an attribute change that "contains" remove change.
  710. // Attribute change needs to be split.
  711. const howMany = old.howMany;
  712. old.howMany = inc.offset - old.offset;
  713. const howManyAfter = howMany - old.howMany - inc.nodesToHandle;
  714. if ( howManyAfter > 0 ) {
  715. // Add the second part of attribute change to the beginning of processed array so it won't
  716. // be processed again in this loop.
  717. changes.unshift( {
  718. type: 'attribute',
  719. offset: inc.offset,
  720. howMany: howManyAfter,
  721. count: this._changeCount++
  722. } );
  723. }
  724. } else {
  725. old.howMany -= oldEnd - inc.offset;
  726. }
  727. }
  728. }
  729. }
  730. if ( inc.type == 'attribute' ) {
  731. // In case of attribute change, `howMany` should be kept same as `nodesToHandle`. It's not an error.
  732. if ( old.type == 'insert' ) {
  733. if ( inc.offset < old.offset && incEnd > old.offset ) {
  734. if ( incEnd > oldEnd ) {
  735. // This case is similar to a case described when incoming change was insert and old change was attribute.
  736. // See comment above.
  737. //
  738. // This time incoming change is attribute. We need to split incoming change in this case too.
  739. // However this time, the second part of the attribute change needs to be processed further
  740. // because there might be other changes that it collides with.
  741. const attributePart = {
  742. type: 'attribute',
  743. offset: oldEnd,
  744. howMany: incEnd - oldEnd,
  745. count: this._changeCount++
  746. };
  747. this._handleChange( attributePart, changes );
  748. changes.push( attributePart );
  749. }
  750. inc.nodesToHandle = old.offset - inc.offset;
  751. inc.howMany = inc.nodesToHandle;
  752. } else if ( inc.offset >= old.offset && inc.offset < oldEnd ) {
  753. if ( incEnd > oldEnd ) {
  754. inc.nodesToHandle = incEnd - oldEnd;
  755. inc.offset = oldEnd;
  756. } else {
  757. inc.nodesToHandle = 0;
  758. }
  759. }
  760. }
  761. if ( old.type == 'remove' ) {
  762. // This is a case when attribute change "contains" remove change.
  763. // The attribute change needs to be split into two because changes cannot intersect.
  764. if ( inc.offset < old.offset && incEnd > old.offset ) {
  765. const attributePart = {
  766. type: 'attribute',
  767. offset: old.offset,
  768. howMany: incEnd - old.offset,
  769. count: this._changeCount++
  770. };
  771. this._handleChange( attributePart, changes );
  772. changes.push( attributePart );
  773. inc.nodesToHandle = old.offset - inc.offset;
  774. inc.howMany = inc.nodesToHandle;
  775. }
  776. }
  777. if ( old.type == 'attribute' ) {
  778. // There are only two conflicting scenarios possible here:
  779. if ( inc.offset >= old.offset && incEnd <= oldEnd ) {
  780. // `old` change includes `inc` change, or they are the same.
  781. inc.nodesToHandle = 0;
  782. inc.howMany = 0;
  783. inc.offset = 0;
  784. } else if ( inc.offset <= old.offset && incEnd >= oldEnd ) {
  785. // `inc` change includes `old` change.
  786. old.howMany = 0;
  787. }
  788. }
  789. }
  790. if ( inc.type == 'refresh' ) {
  791. if ( old.type == 'insert' ) {
  792. if ( inc.offset === old.offset && inc.howMany === old.howMany ) {
  793. old.howMany = 0;
  794. }
  795. }
  796. if ( old.type == 'remove' ) {
  797. if ( inc.offset === old.offset && inc.howMany === old.howMany ) {
  798. inc.nodesToHandle = 0;
  799. }
  800. }
  801. }
  802. }
  803. inc.howMany = inc.nodesToHandle;
  804. delete inc.nodesToHandle;
  805. }
  806. /**
  807. * Returns an object with a single insert change description.
  808. *
  809. * @private
  810. * @param {module:engine/model/element~Element} parent The element in which the change happened.
  811. * @param {Number} offset The offset at which change happened.
  812. * @param {String} name The name of the removed element or `'$text'` for a character.
  813. * @returns {Object} The diff item.
  814. */
  815. _getInsertDiff( parent, offset, name ) {
  816. return {
  817. type: 'insert',
  818. position: Position._createAt( parent, offset ),
  819. name,
  820. length: 1,
  821. changeCount: this._changeCount++
  822. };
  823. }
  824. /**
  825. * Returns an object with a single remove change description.
  826. *
  827. * @private
  828. * @param {module:engine/model/element~Element} parent The element in which change happened.
  829. * @param {Number} offset The offset at which change happened.
  830. * @param {String} name The name of the removed element or `'$text'` for a character.
  831. * @returns {Object} The diff item.
  832. */
  833. _getRemoveDiff( parent, offset, name ) {
  834. return {
  835. type: 'remove',
  836. position: Position._createAt( parent, offset ),
  837. name,
  838. length: 1,
  839. changeCount: this._changeCount++
  840. };
  841. }
  842. /**
  843. * Returns an array of objects where each one is a single attribute change description.
  844. *
  845. * @private
  846. * @param {module:engine/model/range~Range} range The range where the change happened.
  847. * @param {Map} oldAttributes A map, map iterator or compatible object that contains attributes before the change.
  848. * @param {Map} newAttributes A map, map iterator or compatible object that contains attributes after the change.
  849. * @returns {Array.<Object>} An array containing one or more diff items.
  850. */
  851. _getAttributesDiff( range, oldAttributes, newAttributes ) {
  852. // Results holder.
  853. const diffs = [];
  854. // Clone new attributes as we will be performing changes on this object.
  855. newAttributes = new Map( newAttributes );
  856. // Look through old attributes.
  857. for ( const [ key, oldValue ] of oldAttributes ) {
  858. // Check what is the new value of the attribute (or if it was removed).
  859. const newValue = newAttributes.has( key ) ? newAttributes.get( key ) : null;
  860. // If values are different (or attribute was removed)...
  861. if ( newValue !== oldValue ) {
  862. // Add diff item.
  863. diffs.push( {
  864. type: 'attribute',
  865. position: range.start,
  866. range: range.clone(),
  867. length: 1,
  868. attributeKey: key,
  869. attributeOldValue: oldValue,
  870. attributeNewValue: newValue,
  871. changeCount: this._changeCount++
  872. } );
  873. }
  874. // Prevent returning two diff items for the same change.
  875. newAttributes.delete( key );
  876. }
  877. // Look through new attributes that weren't handled above.
  878. for ( const [ key, newValue ] of newAttributes ) {
  879. // Each of them is a new attribute. Add diff item.
  880. diffs.push( {
  881. type: 'attribute',
  882. position: range.start,
  883. range: range.clone(),
  884. length: 1,
  885. attributeKey: key,
  886. attributeOldValue: null,
  887. attributeNewValue: newValue,
  888. changeCount: this._changeCount++
  889. } );
  890. }
  891. return diffs;
  892. }
  893. _getRefreshDiff( parent, offset, name ) {
  894. return {
  895. type: 'refresh',
  896. position: Position._createAt( parent, offset ),
  897. name,
  898. length: 1,
  899. changeCount: this._changeCount++
  900. };
  901. }
  902. /**
  903. * Checks whether given element or any of its parents is an element that is buffered as an inserted element.
  904. *
  905. * @private
  906. * @param {module:engine/model/element~Element} element Element to check.
  907. * @returns {Boolean}
  908. */
  909. _isInInsertedElement( element ) {
  910. const parent = element.parent;
  911. if ( !parent ) {
  912. return false;
  913. }
  914. const changes = this._changesInElement.get( parent );
  915. const offset = element.startOffset;
  916. if ( changes ) {
  917. for ( const change of changes ) {
  918. if ( change.type == 'insert' && offset >= change.offset && offset < change.offset + change.howMany ) {
  919. return true;
  920. }
  921. }
  922. }
  923. return this._isInInsertedElement( parent );
  924. }
  925. // TODO: copy-paste of above _isInInsertedElement.
  926. _isInRefreshedElement( element ) {
  927. const parent = element.parent;
  928. if ( !parent ) {
  929. return false;
  930. }
  931. const changes = this._changesInElement.get( parent );
  932. const offset = element.startOffset;
  933. if ( changes ) {
  934. for ( const change of changes ) {
  935. if ( change.type == 'refresh' && offset >= change.offset && offset < change.offset + change.howMany ) {
  936. return true;
  937. }
  938. }
  939. }
  940. return this._isInRefreshedElement( parent );
  941. }
  942. /**
  943. * Removes deeply all buffered changes that are registered in elements from range specified by `parent`, `offset`
  944. * and `howMany`.
  945. *
  946. * @private
  947. * @param {module:engine/model/element~Element} parent
  948. * @param {Number} offset
  949. * @param {Number} howMany
  950. */
  951. _removeAllNestedChanges( parent, offset, howMany ) {
  952. const range = new Range( Position._createAt( parent, offset ), Position._createAt( parent, offset + howMany ) );
  953. for ( const item of range.getItems( { shallow: true } ) ) {
  954. if ( item.is( 'element' ) ) {
  955. this._elementSnapshots.delete( item );
  956. this._changesInElement.delete( item );
  957. this._removeAllNestedChanges( item, 0, item.maxOffset );
  958. }
  959. }
  960. }
  961. _removeAllNestedAttributeChanges( parent, offset, howMany ) {
  962. const parentChanges = this._changesInElement.get( parent );
  963. const notAttributeChange = change => change.type !== 'attribute' || change.offset !== offset || change.howMany !== howMany;
  964. if ( parentChanges ) {
  965. this._changesInElement.set( parent, parentChanges.filter( notAttributeChange ) );
  966. }
  967. }
  968. }
  969. // Returns an array that is a copy of passed child list with the exception that text nodes are split to one or more
  970. // objects, each representing one character and attributes set on that character.
  971. function _getChildrenSnapshot( children ) {
  972. const snapshot = [];
  973. for ( const child of children ) {
  974. if ( child.is( '$text' ) ) {
  975. for ( let i = 0; i < child.data.length; i++ ) {
  976. snapshot.push( {
  977. name: '$text',
  978. attributes: new Map( child.getAttributes() )
  979. } );
  980. }
  981. } else {
  982. snapshot.push( {
  983. name: child.name,
  984. attributes: new Map( child.getAttributes() )
  985. } );
  986. }
  987. }
  988. return snapshot;
  989. }
  990. // Generates array of actions for given changes set.
  991. // It simulates what `diff` function does.
  992. // Generated actions are:
  993. // - 'e' for 'equal' - when item at that position did not change,
  994. // - 'i' for 'insert' - when item at that position was inserted,
  995. // - 'r' for 'remove' - when item at that position was removed,
  996. // - 'a' for 'attribute' - when item at that position has it attributes changed.
  997. //
  998. // Example (assume that uppercase letters have bold attribute, compare with function code):
  999. //
  1000. // children before: fooBAR
  1001. // children after: foxybAR
  1002. //
  1003. // changes: type: remove, offset: 1, howMany: 1
  1004. // type: insert, offset: 2, howMany: 2
  1005. // type: attribute, offset: 4, howMany: 1
  1006. //
  1007. // expected actions: equal (f), remove (o), equal (o), insert (x), insert (y), attribute (b), equal (A), equal (R)
  1008. //
  1009. // steps taken by th script:
  1010. //
  1011. // 1. change = "type: remove, offset: 1, howMany: 1"; offset = 0; oldChildrenHandled = 0
  1012. // 1.1 between this change and the beginning is one not-changed node, fill with one equal action, one old child has been handled
  1013. // 1.2 this change removes one node, add one remove action
  1014. // 1.3 change last visited `offset` to 1
  1015. // 1.4 since an old child has been removed, one more old child has been handled
  1016. // 1.5 actions at this point are: equal, remove
  1017. //
  1018. // 2. change = "type: insert, offset: 2, howMany: 2"; offset = 1; oldChildrenHandled = 2
  1019. // 2.1 between this change and previous change is one not-changed node, add equal action, another one old children has been handled
  1020. // 2.2 this change inserts two nodes, add two insert actions
  1021. // 2.3 change last visited offset to the end of the inserted range, that is 4
  1022. // 2.4 actions at this point are: equal, remove, equal, insert, insert
  1023. //
  1024. // 3. change = "type: attribute, offset: 4, howMany: 1"; offset = 4, oldChildrenHandled = 3
  1025. // 3.1 between this change and previous change are no not-changed nodes
  1026. // 3.2 this change changes one node, add one attribute action
  1027. // 3.3 change last visited `offset` to the end of change range, that is 5
  1028. // 3.4 since an old child has been changed, one more old child has been handled
  1029. // 3.5 actions at this point are: equal, remove, equal, insert, insert, attribute
  1030. //
  1031. // 4. after loop oldChildrenHandled = 4, oldChildrenLength = 6 (fooBAR is 6 characters)
  1032. // 4.1 fill up with two equal actions
  1033. //
  1034. // The result actions are: equal, remove, equal, insert, insert, attribute, equal, equal.
  1035. function _generateActionsFromChanges( oldChildrenLength, changes ) {
  1036. const actions = [];
  1037. let offset = 0;
  1038. let oldChildrenHandled = 0;
  1039. // Go through all buffered changes.
  1040. for ( const change of changes ) {
  1041. // First, fill "holes" between changes with "equal" actions.
  1042. if ( change.offset > offset ) {
  1043. for ( let i = 0; i < change.offset - offset; i++ ) {
  1044. actions.push( 'e' );
  1045. }
  1046. oldChildrenHandled += change.offset - offset;
  1047. }
  1048. // Then, fill up actions accordingly to change type.
  1049. if ( change.type == 'insert' ) {
  1050. for ( let i = 0; i < change.howMany; i++ ) {
  1051. actions.push( 'i' );
  1052. }
  1053. // The last handled offset is after inserted range.
  1054. offset = change.offset + change.howMany;
  1055. } else if ( change.type == 'remove' ) {
  1056. for ( let i = 0; i < change.howMany; i++ ) {
  1057. actions.push( 'r' );
  1058. }
  1059. // The last handled offset is at the position where the nodes were removed.
  1060. offset = change.offset;
  1061. // We removed `howMany` old nodes, update `oldChildrenHandled`.
  1062. oldChildrenHandled += change.howMany;
  1063. } else if ( change.type == 'attribute' ) {
  1064. actions.push( ...'a'.repeat( change.howMany ).split( '' ) );
  1065. // The last handled offset is at the position after the changed range.
  1066. offset = change.offset + change.howMany;
  1067. // We changed `howMany` old nodes, update `oldChildrenHandled`.
  1068. oldChildrenHandled += change.howMany;
  1069. } else {
  1070. actions.push( 'x' );
  1071. // The last handled offset is after inserted range.
  1072. offset = change.offset + change.howMany;
  1073. }
  1074. }
  1075. // Fill "equal" actions at the end of actions set. Use `oldChildrenHandled` to see how many children
  1076. // has not been changed / removed at the end of their parent.
  1077. if ( oldChildrenHandled < oldChildrenLength ) {
  1078. for ( let i = 0; i < oldChildrenLength - oldChildrenHandled - offset; i++ ) {
  1079. actions.push( 'e' );
  1080. }
  1081. }
  1082. return actions;
  1083. }
  1084. // Filter callback for Array.filter that filters out change entries that are in graveyard.
  1085. function _changesInGraveyardFilter( entry ) {
  1086. const posInGy = entry.position && entry.position.root.rootName == '$graveyard';
  1087. const rangeInGy = entry.range && entry.range.root.rootName == '$graveyard';
  1088. return !posInGy && !rangeInGy;
  1089. }