treewalker.js 8.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232
  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 `startPosition`.
  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.startPosition] 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. * @param {Boolean} [options.shallow=false] Flag indicating whether iterator should enter elements or not. If the
  27. * iterator is shallow child nodes of any iterated node will not be returned along with `ELEMENT_END` tag.
  28. * @param {Boolean} [options.ignoreElementEnd=false] Flag indicating whether iterator should ignore `ELEMENT_END`
  29. * tags. If the option is true walker will not return a parent node of start position. If this option is `true`
  30. * each {@link core.treeModel.Element} will be returned once, while if the option is `false` they might be returned
  31. * twice: for `'ELEMENT_START'` and `'ELEMENT_END'`.
  32. * @constructor
  33. */
  34. constructor( options ) {
  35. if ( !options || ( !options.boundaries && !options.startPosition ) ) {
  36. /**
  37. * Neither boundaries nor starting position have been defined.
  38. *
  39. * @error tree-walker-no-start-position
  40. */
  41. throw new CKEditorError( 'tree-walker-no-start-position: Neither boundaries nor starting position have been defined.' );
  42. }
  43. /**
  44. * Iterator boundaries.
  45. *
  46. * When the {@link #next} method is called on the end boundary or the {@link #previous} method
  47. * on the start boundary, then `{ done: true }` is returned.
  48. *
  49. * If boundaries are not defined they are set before first and after last child of the root node.
  50. *
  51. * @member {core.treeModel.Range} core.treeModel.TreeWalker#boundaries
  52. */
  53. this.boundaries = options.boundaries || null;
  54. /**
  55. * End boundary cached for optimization purposes.
  56. *
  57. * @private
  58. * @member {core.treeModel.Element} core.treeModel.TreeWalker#_boundaryEndParent
  59. */
  60. this._boundaryEndParent = this.boundaries ? this.boundaries.end.parent : null;
  61. /**
  62. * Iterator position. This is always static position, even if the initial position was a
  63. * {@link core.treeModel.LivePosition live position}.
  64. *
  65. * @member {core.treeModel.Position} core.treeModel.TreeWalker#position
  66. */
  67. this.position = options.startPosition ?
  68. Position.createFromPosition( options.startPosition ) :
  69. Position.createFromPosition( options.boundaries.start );
  70. /**
  71. * Flag indicating whether all consecutive characters with the same attributes should be
  72. * returned as one {@link core.treeModel.CharacterProxy} (`true`) or one by one (`false`).
  73. *
  74. * @member {Boolean} core.treeModel.TreeWalker#singleCharacters
  75. */
  76. this.singleCharacters = !!options.singleCharacters;
  77. /**
  78. * Flag indicating whether iterator should enter elements or not. If the iterator is shallow child nodes of any
  79. * iterated node will not be returned along with `ELEMENT_END` tag.
  80. *
  81. * @member {Boolean} core.treeModel.TreeWalker#shallow
  82. */
  83. this.shallow = !!options.shallow;
  84. /**
  85. * Flag indicating whether iterator should ignore `ELEMENT_END` tags. If the option is true walker will not
  86. * return a parent node of the start position. If this option is `true` each {@link core.treeModel.Element} will
  87. * be returned once, while if the option is `false` they might be returned twice:
  88. * for `'ELEMENT_START'` and `'ELEMENT_END'`.
  89. *
  90. * @member {Boolean} core.treeModel.TreeWalker#ignoreElementEnd
  91. */
  92. this.ignoreElementEnd = !!options.ignoreElementEnd;
  93. /**
  94. * Parent of the most recently visited node. Cached for optimization purposes.
  95. *
  96. * @private
  97. * @member {core.treeModel.Element} core.treeModel.TreeWalker#_visitedParent
  98. */
  99. this._visitedParent = this.position.parent;
  100. }
  101. /**
  102. * Iterator interface.
  103. */
  104. [ Symbol.iterator ]() {
  105. return this;
  106. }
  107. /**
  108. * Makes a step forward in tree model. Moves the {@link #position} to the next position and returns the encountered value.
  109. *
  110. * @returns {Object} Object implementing iterator interface, returning information about taken step.
  111. * @returns {Boolean} return.done True if iterator is done.
  112. * @returns {core.treeModel.TreeWalkerValue} return.value Information about taken step.
  113. */
  114. next() {
  115. const previousPosition = this.position;
  116. const position = Position.createFromPosition( this.position );
  117. const parent = this._visitedParent;
  118. // We are at the end of the root.
  119. if ( parent.parent === null && position.offset === parent.getChildCount() ) {
  120. return { done: true };
  121. }
  122. // We reached the walker boundary.
  123. if ( parent === this._boundaryEndParent && position.offset == this.boundaries.end.offset ) {
  124. return { done: true };
  125. }
  126. const node = parent.getChild( position.offset );
  127. if ( node instanceof Element ) {
  128. if ( !this.shallow ) {
  129. // Manual operations on path internals for optimization purposes. Here and in the rest of the method.
  130. position.path.push( 0 );
  131. this._visitedParent = node;
  132. } else {
  133. position.offset++;
  134. }
  135. this.position = position;
  136. return formatReturnValue( 'ELEMENT_START', node, previousPosition, position, 1 );
  137. } else if ( node instanceof CharacterProxy ) {
  138. if ( this.singleCharacters ) {
  139. position.offset++;
  140. this.position = position;
  141. return formatReturnValue( 'CHARACTER', node, previousPosition, position, 1 );
  142. } else {
  143. let charactersCount = node._nodeListText.text.length - node._index;
  144. let offset = position.offset + charactersCount;
  145. if ( this._boundaryEndParent == parent && this.boundaries.end.offset < offset ) {
  146. offset = this.boundaries.end.offset;
  147. charactersCount = offset - position.offset;
  148. }
  149. let textFragment = new TextFragment( node, charactersCount );
  150. position.offset = offset;
  151. this.position = position;
  152. return formatReturnValue( 'TEXT', textFragment, previousPosition, position, charactersCount );
  153. }
  154. } else {
  155. // `node` is not set, we reached the end of current `parent`.
  156. position.path.pop();
  157. position.offset++;
  158. this.position = position;
  159. this._visitedParent = parent.parent;
  160. if ( this.ignoreElementEnd ) {
  161. return this.next();
  162. } else {
  163. return formatReturnValue( 'ELEMENT_END', parent, previousPosition, position );
  164. }
  165. }
  166. }
  167. }
  168. function formatReturnValue( type, item, previousPosition, nextPosition, length ) {
  169. return {
  170. done: false,
  171. value: {
  172. type: type,
  173. item: item,
  174. previousPosition: previousPosition,
  175. nextPosition: nextPosition,
  176. length: length
  177. }
  178. };
  179. }
  180. /**
  181. * Type of the step made by {@link core.treeModel.TreeWalker}.
  182. * Possible values: `'ELEMENT_START'` if walker is at the beginning of a node, `'ELEMENT_END'` if walker is at the end of node,
  183. * `'CHARACTER'` if walker traversed over a character, or `'TEXT'` if walker traversed over multiple characters (available in
  184. * character merging mode, see {@link core.treeModel.TreeWalker#constructor}).
  185. *
  186. * @typedef {String} core.treeModel.TreeWalkerValueType
  187. */
  188. /**
  189. * Object returned by {@link core.treeModel.TreeWalker} when traversing tree model.
  190. *
  191. * @typedef {Object} core.treeModel.TreeWalkerValue
  192. * @property {core.treeModel.TreeWalkerValueType} type
  193. * @property {core.treeModel.Item} item Item between old and new positions of {@link core.treeModel.TreeWalker}.
  194. * @property {core.treeModel.Position} previousPosition Previous position of the iterator. For `'ELEMENT_END'` it is the last
  195. * position inside the element. For all other types it is the position before the item. Note that it is more
  196. * efficient to use this position then calculate the position before the node using
  197. * {@link core.treeModel.Position.createBefore}. It is also more efficient to get the position after node by shifting
  198. * `previousPosition` by `length`, using {@link core.treeModel.Position#getShiftedBy}, then calculate the position using
  199. * {@link core.treeModel.Position.createAfter}.
  200. * @property {core.treeModel.Position} nextPosition Next position of the iterator. For `'ELEMENT_START'` it is the first
  201. * position inside the element. For all other types it is the position after the item.
  202. * @property {Number} [length] Length of the item. For `'ELEMENT_START'` and `'CHARACTER'` it is 1. For `'TEXT'` it is
  203. * the length of the text. For `'ELEMENT_END'` it is undefined.
  204. */