8
0

differ.js 39 KB

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