8
0

history.js 6.8 KB

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