treewalker.js 9.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272
  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 CharacterProxy from './characterproxy.js';
  7. import TextFragment from './textfragment.js';
  8. import Element from './element.js';
  9. import Position from './position.js';
  10. import CKEditorError from '../ckeditorerror.js';
  11. /**
  12. * Position iterator class. It allows to iterate forward and backward over the tree document.
  13. *
  14. * @memberOf core.treeModel
  15. */
  16. export default class TreeWalker {
  17. /**
  18. * Creates a range iterator. All parameters are optional, but you have to specify either `boundaries` or `position`.
  19. *
  20. * @param {Object} options Object with configuration.
  21. * @param {core.treeModel.Range} [options.boundaries] Range to define boundaries of the iterator.
  22. * @param {core.treeModel.Position} [options.position] Starting position.
  23. * @param {Boolean} [options.singleCharacters=false] Flag indicating whether all consecutive characters with the same attributes
  24. * should be returned one by one as multiple {@link core.treeModel.CharacterProxy} (`true`) objects or as one
  25. * {@link core.treeModel.TextFragment} (`false`).
  26. * @constructor
  27. */
  28. constructor( options ) {
  29. if ( !options || ( !options.boundaries && !options.position ) ) {
  30. /**
  31. * Neither boundaries nor starting position have been defined.
  32. *
  33. * @error tree-walker-no-start-position
  34. */
  35. throw new CKEditorError( 'tree-walker-no-start-position: Neither boundaries nor starting position have been defined.' );
  36. }
  37. /**
  38. * Iterator boundaries.
  39. *
  40. * When the {@link #next} method is called on the end boundary or the {@link #previous} method
  41. * on the start boundary, then `{ done: true }` is returned.
  42. *
  43. * If boundaries are not defined they are set before first and after last child of the root node.
  44. *
  45. * @type {core.treeModel.Range}
  46. */
  47. this.boundaries = options.boundaries || null;
  48. /**
  49. * Start boundary cached for optimization purposes.
  50. *
  51. * @private
  52. * @type {core.treeModel.Element}
  53. */
  54. this._boundaryStartParent = this.boundaries ? this.boundaries.start.parent : null;
  55. /**
  56. * End boundary cached for optimization purposes.
  57. *
  58. * @private
  59. * @type {core.treeModel.Element}
  60. */
  61. this._boundaryEndParent = this.boundaries ? this.boundaries.end.parent : null;
  62. /**
  63. * Iterator position. This is alway static position, even if the initial position was a
  64. * {@link core.treeModel.LivePosition live position}.
  65. *
  66. * @type {core.treeModel.Position}
  67. */
  68. this.position = options.position ?
  69. Position.createFromPosition( options.position ) :
  70. Position.createFromPosition( options.boundaries.start );
  71. /**
  72. * Flag indicating whether all consecutive characters with the same attributes should be
  73. * returned as one {@link core.treeModel.CharacterProxy} (`true`) or one by one (`false`).
  74. *
  75. * @type {Boolean}
  76. */
  77. this.singleCharacters = !!options.singleCharacters;
  78. /**
  79. * Parent of the most recently visited node. Cached for optimization purposes.
  80. *
  81. * @private
  82. * @type {core.treeModel.Element}
  83. */
  84. this._visitedParent = this.position.parent;
  85. }
  86. /**
  87. * Iterator interface.
  88. */
  89. [ Symbol.iterator ]() {
  90. return this;
  91. }
  92. /**
  93. * Makes a step forward in tree model. Moves the {@link #position} to the next position and returns the encountered value.
  94. *
  95. * @returns {Object} Object implementing iterator interface, returning information about taken step.
  96. * @returns {Boolean} return.done True if iterator is done.
  97. * @returns {core.treeModel.TreeWalkerValue} return.value Information about taken step.
  98. */
  99. next() {
  100. const previousPosition = this.position;
  101. const position = Position.createFromPosition( this.position );
  102. const parent = this._visitedParent;
  103. // We are at the end of the root.
  104. if ( parent.parent === null && position.offset === parent.getChildCount() ) {
  105. return { done: true };
  106. }
  107. // Parent can't be null so by comparing with boundaryParent we check if boundaryParent is set at all.
  108. if ( parent == this._boundaryEndParent && position.offset == this.boundaries.end.offset ) {
  109. return { done: true };
  110. }
  111. const node = parent.getChild( position.offset );
  112. if ( node instanceof Element ) {
  113. // Manual operations on path internals for optimization purposes. Here and in the rest of the method.
  114. position.path.push( 0 );
  115. this.position = position;
  116. this._visitedParent = node;
  117. return formatReturnValue( 'ELEMENT_START', node, previousPosition, position, 1 );
  118. } else if ( node instanceof CharacterProxy ) {
  119. if ( this.singleCharacters ) {
  120. position.offset++;
  121. this.position = position;
  122. return formatReturnValue( 'CHARACTER', node, previousPosition, position, 1 );
  123. } else {
  124. let charactersCount = node._nodeListText.text.length - node._index;
  125. let offset = position.offset + charactersCount;
  126. if ( this._boundaryEndParent == parent && this.boundaries.end.offset < offset ) {
  127. offset = this.boundaries.end.offset;
  128. charactersCount = offset - position.offset;
  129. }
  130. let textFragment = new TextFragment( node, charactersCount );
  131. position.offset = offset;
  132. this.position = position;
  133. return formatReturnValue( 'TEXT', textFragment, previousPosition, position, charactersCount );
  134. }
  135. } else {
  136. position.path.pop();
  137. position.offset++;
  138. this.position = position;
  139. this._visitedParent = parent.parent;
  140. return formatReturnValue( 'ELEMENT_END', parent, previousPosition, position );
  141. }
  142. }
  143. /**
  144. * Makes a step backward in tree model. Moves the {@link #position} to the previous position and returns the encountered value.
  145. *
  146. * @returns {Object} Object implementing iterator interface, returning information about taken step.
  147. * @returns {Boolean} return.done True if iterator is done.
  148. * @returns {core.treeModel.TreeWalkerValue} return.value Information about taken step.
  149. */
  150. previous() {
  151. const previousPosition = this.position;
  152. const position = Position.createFromPosition( this.position );
  153. const parent = this._visitedParent;
  154. // We are at the end of the root.
  155. if ( parent.parent === null && position.offset === 0 ) {
  156. return { done: true };
  157. }
  158. // Parent can't be null so by comparing with boundaryParent we check if boundaryParent is set at all.
  159. if ( parent == this._boundaryStartParent && position.offset == this.boundaries.start.offset ) {
  160. return { done: true };
  161. }
  162. const node = parent.getChild( position.offset - 1 );
  163. if ( node instanceof Element ) {
  164. // Manual operations on path internals for optimization purposes. Here and in the rest of the method.
  165. position.offset--;
  166. position.path.push( node.getChildCount() );
  167. this.position = position;
  168. this._visitedParent = node;
  169. return formatReturnValue( 'ELEMENT_END', node, position, previousPosition );
  170. } else if ( node instanceof CharacterProxy ) {
  171. if ( this.singleCharacters ) {
  172. position.offset--;
  173. this.position = position;
  174. return formatReturnValue( 'CHARACTER', node, position, previousPosition, 1 );
  175. } else {
  176. let charactersCount = node._index + 1;
  177. let offset = position.offset - charactersCount;
  178. if ( this._boundaryStartParent == parent && this.boundaries.start.offset > offset ) {
  179. offset = this.boundaries.start.offset;
  180. charactersCount = position.offset - offset;
  181. }
  182. let textFragment = new TextFragment( parent.getChild( offset ), charactersCount );
  183. position.offset = offset;
  184. this.position = position;
  185. return formatReturnValue( 'TEXT', textFragment, position, previousPosition, charactersCount );
  186. }
  187. } else {
  188. position.path.pop();
  189. this.position = position;
  190. this._visitedParent = parent.parent;
  191. return formatReturnValue( 'ELEMENT_START', parent, position, previousPosition, 1 );
  192. }
  193. }
  194. }
  195. function formatReturnValue( type, item, previousPosition, nextPosition, length ) {
  196. return {
  197. done: false,
  198. value: {
  199. type: type,
  200. item: item,
  201. previousPosition: previousPosition,
  202. nextPosition: nextPosition,
  203. length: length
  204. }
  205. };
  206. }
  207. /**
  208. * Type of the step made by {@link core.treeModel.TreeWalker}.
  209. * Possible values: `'ELEMENT_START'` if walker is at the beginning of a node, `'ELEMENT_END'` if walker is at the end of node,
  210. * `'CHARACTER'` if walker traversed over a character, or `'TEXT'` if walker traversed over multiple characters (available in
  211. * character merging mode, see {@link core.treeModel.TreeWalker#constructor}).
  212. *
  213. * @typedef {String} core.treeModel.TreeWalkerValueType
  214. */
  215. /**
  216. * Object returned by {@link core.treeModel.TreeWalker} when traversing tree model.
  217. *
  218. * @typedef {Object} core.treeModel.TreeWalkerValue
  219. * @property {core.treeModel.TreeWalkerValueType} type
  220. * @property {core.treeModel.Item} item Item between old and new positions of {@link core.treeModel.TreeWalker}.
  221. * @property {core.treeModel.Position} previousPosition Previous position of the iterator. For `'ELEMENT_END'` it is the last
  222. * position inside the element. For all other types it is the position before the item. Note that it is more
  223. * efficient to use this position then calculate the position before the node using
  224. * {@link core.treeModel.Position.createBefore}. It is also more efficient to get the position after node by shifting
  225. * `previousPosition` by `length`, using {@link core.treeModel.Position#getShiftedBy}, then calculate the position using
  226. * {@link core.treeModel.Position.createAfter}.
  227. * @property {core.treeModel.Position} nextPosition Next position of the iterator. For `'ELEMENT_START'` it is the first
  228. * position inside the element. For all other types it is the position after the item.
  229. * @property {Number} [length] Length of the item. For `'ELEMENT_START'` and `'CHARACTER'` it is 1. For `'TEXT'` it is
  230. * the length of the text. For `'ELEMENT_END'` it is undefined.
  231. */