history.js 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
  1. /**
  2. * @license Copyright (c) 2003-2016, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. 'use strict';
  6. import CKEditorError from '../../utils/ckeditorerror.js';
  7. /**
  8. * `History` keeps the track of all the deltas applied to the {@link engine.model.Document document}. Deltas stored in
  9. * `History` might get updated, split into more deltas or even removed. This is used mostly to compress history, instead
  10. * of keeping all deltas in a state in which they were applied.
  11. *
  12. * **Note:** deltas kept in `History` should be used only to transform deltas. It's not advised to use `History` to get
  13. * original delta basing on it's {@link engine.model.delta.Delta#baseVersion baseVersion}. Also, after transforming a
  14. * delta by deltas from `History`, fix it's base version accordingly (set to {@link engine.model.Document#version}.
  15. *
  16. * @memberOf engine.model
  17. */
  18. export default class History {
  19. /**
  20. * Creates an empty History instance.
  21. */
  22. constructor() {
  23. /**
  24. * Deltas added to the history.
  25. *
  26. * @protected
  27. * @member {Array.<engine.model.delta.Delta>} engine.model.History#_deltas
  28. */
  29. this._deltas = [];
  30. /**
  31. * Helper structure that maps added delta's base version to the index in {@link engine.model.History#_deltas}
  32. * at which the delta was added.
  33. *
  34. * @protected
  35. * @member {Map} engine.model.History#_historyPoints
  36. */
  37. this._historyPoints = new Map();
  38. }
  39. /**
  40. * Adds delta to the history.
  41. *
  42. * @param {engine.model.delta.Delta} delta Delta to add.
  43. */
  44. addDelta( delta ) {
  45. if ( delta.operations.length > 0 && !this._historyPoints.has( delta.baseVersion ) ) {
  46. const index = this._deltas.length;
  47. this._deltas[ index ] = delta;
  48. this._historyPoints.set( delta.baseVersion, index );
  49. }
  50. }
  51. /**
  52. * Returns deltas added to the history.
  53. *
  54. * @param {Number} [from=0] Base version from which deltas should be returned (inclusive). Defaults to `0` which means
  55. * that deltas from the first one will be returned.
  56. * @param {Number} [to=Number.POSITIVE_INFINITY] Base version up to which deltas should be returned (exclusive).
  57. * Defaults to `Number.POSITIVE_INFINITY` which means that deltas up to the last one will be returned.
  58. * @returns {Iterator.<engine.model.delta.Delta>} Deltas added to the history.
  59. */
  60. *getDeltas( from = 0, to = Number.POSITIVE_INFINITY ) {
  61. // No deltas added, nothing to yield.
  62. if ( this._deltas.length === 0 ) {
  63. return;
  64. }
  65. // Will throw if base version is incorrect.
  66. let fromIndex = this._getIndex( from );
  67. // Base version is too low or too high and is not found in history.
  68. if ( fromIndex == -1 ) {
  69. return;
  70. }
  71. // We have correct `fromIndex` so let's iterate starting from it.
  72. while ( fromIndex < this._deltas.length ) {
  73. const delta = this._deltas[ fromIndex++ ];
  74. if ( delta.baseVersion >= to ) {
  75. break;
  76. }
  77. yield delta;
  78. }
  79. }
  80. /**
  81. * Returns one or more deltas from history that bases on given `baseVersion`. Most often it will be just
  82. * one delta, but if that delta got updated by multiple deltas, all of those updated deltas will be returned.
  83. *
  84. * @see engine.model.History#updateDelta
  85. * @param {Number} baseVersion Base version of the delta to retrieve.
  86. * @returns {Array.<engine.model.delta.Delta>|null} Delta with given base version or null if no such delta is in history.
  87. */
  88. getDelta( baseVersion ) {
  89. let index = this._historyPoints.get( baseVersion );
  90. if ( index === undefined ) {
  91. return null;
  92. }
  93. const deltas = [];
  94. for ( index; index < this._deltas.length; index++ ) {
  95. const delta = this._deltas[ index ];
  96. if ( delta.baseVersion != baseVersion ) {
  97. break;
  98. }
  99. deltas.push( delta );
  100. }
  101. return deltas.length === 0 ? null : deltas;
  102. }
  103. /**
  104. * Removes delta from the history. This happens i.e., when a delta is undone by another delta. Both undone delta and
  105. * undoing delta should be removed so they won't have an impact on transforming other deltas.
  106. *
  107. * **Note:** using this method does not change the state of {@link engine.model.Document model}. It just affects
  108. * the state of `History`.
  109. *
  110. * **Note:** when some deltas are removed, deltas between them should probably get updated. See
  111. * {@link engine.model.History#updateDelta}.
  112. *
  113. * **Note:** if delta with `baseVersion` got {@link engine.model.History#updateDelta updated} by multiple
  114. * deltas, all updated deltas will be removed.
  115. *
  116. * @param {Number} baseVersion Base version of a delta to be removed.
  117. */
  118. removeDelta( baseVersion ) {
  119. this.updateDelta( baseVersion, [] );
  120. }
  121. /**
  122. * Substitutes delta in history by one or more given deltas.
  123. *
  124. * **Note:** if delta with `baseVersion` was already updated by multiple deltas, all updated deltas will be removed
  125. * and new deltas will be inserted at their position.
  126. *
  127. * **Note:** delta marked as reversed won't get updated.
  128. *
  129. * @param {Number} baseVersion Base version of a delta to update.
  130. * @param {Iterable.<engine.model.delta.Delta>} updatedDeltas Deltas to be inserted in place of updated delta.
  131. */
  132. updateDelta( baseVersion, updatedDeltas ) {
  133. const deltas = this.getDelta( baseVersion );
  134. // If there are no deltas, stop executing function as there is nothing to update.
  135. if ( deltas === null ) {
  136. return;
  137. }
  138. // Make sure that every updated delta has correct `baseVersion`.
  139. // This is crucial for algorithms in `History` and algorithms using `History`.
  140. for ( let delta of updatedDeltas ) {
  141. delta.baseVersion = baseVersion;
  142. }
  143. // Put updated deltas in place of old deltas.
  144. this._deltas.splice( this._getIndex( baseVersion ), deltas.length, ...updatedDeltas );
  145. // Update history points.
  146. const changeBy = updatedDeltas.length - deltas.length;
  147. for ( let key of this._historyPoints.keys() ) {
  148. if ( key > baseVersion ) {
  149. this._historyPoints.set( key, this._historyPoints.get( key ) + changeBy );
  150. }
  151. }
  152. }
  153. /**
  154. * Gets an index in {@link engine.model.History#_deltas} where delta with given `baseVersion` is added.
  155. *
  156. * @private
  157. * @param {Number} baseVersion Base version of delta.
  158. */
  159. _getIndex( baseVersion ) {
  160. let index = this._historyPoints.get( baseVersion );
  161. // Base version not found - it is either too high or too low, or is in the middle of delta.
  162. if ( index === undefined ) {
  163. const lastDelta = this._deltas[ this._deltas.length - 1 ];
  164. const nextBaseVersion = lastDelta.baseVersion + lastDelta.operations.length;
  165. if ( baseVersion < 0 || baseVersion >= nextBaseVersion ) {
  166. // Base version is too high or too low - it's acceptable situation.
  167. // Return -1 because `baseVersion` was correct.
  168. return -1;
  169. }
  170. /**
  171. * Given base version points to the middle of a delta.
  172. *
  173. * @error history-wrong-version
  174. */
  175. throw new CKEditorError( 'history-wrong-version: Given base version points to the middle of a delta.' );
  176. }
  177. return index;
  178. }
  179. }