treewalker.js 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375
  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 TextProxy from './textproxy.js';
  8. import Element from './element.js';
  9. import Position from './position.js';
  10. import CKEditorError from '../../utils/ckeditorerror.js';
  11. /**
  12. * Position iterator class. It allows to iterate forward and backward over the document.
  13. *
  14. * @memberOf engine.model
  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. * @constructor
  21. * @param {Object} options Object with configuration.
  22. * @param {engine.model.Range} [options.boundaries=null] Range to define boundaries of the iterator.
  23. * @param {engine.model.Position} [options.startPosition] Starting position.
  24. * @param {'FORWARD'|'BACKWARD'} [options.direction='FORWARD'] Walking direction.
  25. * @param {Boolean} [options.singleCharacters=false] Flag indicating whether all consecutive characters with the same attributes
  26. * should be returned one by one as multiple {@link engine.model.CharacterProxy} (`true`) objects or as one
  27. * {@link engine.model.TextProxy} (`false`).
  28. * @param {Boolean} [options.shallow=false] Flag indicating whether iterator should enter elements or not. If the
  29. * iterator is shallow child nodes of any iterated node will not be returned along with `ELEMENT_END` tag.
  30. * @param {Boolean} [options.ignoreElementEnd=false] Flag indicating whether iterator should ignore `ELEMENT_END`
  31. * tags. If the option is true walker will not return a parent node of start position. If this option is `true`
  32. * each {@link engine.model.Element} will be returned once, while if the option is `false` they might be returned
  33. * twice: for `'ELEMENT_START'` and `'ELEMENT_END'`.
  34. */
  35. constructor(
  36. {
  37. boundaries = null,
  38. startPosition,
  39. direction = 'FORWARD',
  40. singleCharacters = false,
  41. shallow = false,
  42. ignoreElementEnd = false,
  43. } = {}
  44. ) {
  45. if ( !boundaries && !startPosition ) {
  46. /**
  47. * Neither boundaries nor starting position have been defined.
  48. *
  49. * @error tree-walker-no-start-position
  50. */
  51. throw new CKEditorError( 'tree-walker-no-start-position: Neither boundaries nor starting position have been defined.' );
  52. }
  53. if ( direction != 'FORWARD' && direction != 'BACKWARD' ) {
  54. throw new CKEditorError(
  55. 'tree-walker-unknown-direction: Only `BACKWARD` and `FORWARD` direction allowed.',
  56. { direction }
  57. );
  58. }
  59. /**
  60. * Iterator boundaries.
  61. *
  62. * When the iterator is walking `FORWARD` on the end of boundary or is walking `BACKWARD`
  63. * on the start of boundary, then `{ done: true }` is returned.
  64. *
  65. * If boundaries are not defined they are set before first and after last child of the root node.
  66. *
  67. * @readonly
  68. * @member {engine.model.Range} engine.model.TreeWalker#boundaries
  69. */
  70. this.boundaries = boundaries;
  71. /**
  72. * Iterator position. This is always static position, even if the initial position was a
  73. * {@link engine.model.LivePosition live position}. If start position is not defined then position depends
  74. * on {@link #direction}. If direction is `FORWARD` position starts form the beginning, when direction
  75. * is `BACKWARD` position starts from the end.
  76. *
  77. * @readonly
  78. * @member {engine.model.Position} engine.model.TreeWalker#position
  79. */
  80. if ( startPosition ) {
  81. this.position = Position.createFromPosition( startPosition );
  82. } else {
  83. this.position = Position.createFromPosition( boundaries[ direction == 'BACKWARD' ? 'end' : 'start' ] );
  84. }
  85. /**
  86. * Walking direction. Defaults `FORWARD`.
  87. *
  88. * @readonly
  89. * @member {'BACKWARD'|'FORWARD'} engine.model.TreeWalker#direction
  90. */
  91. this.direction = direction;
  92. /**
  93. * Flag indicating whether all consecutive characters with the same attributes should be
  94. * returned as one {@link engine.model.CharacterProxy} (`true`) or one by one (`false`).
  95. *
  96. * @readonly
  97. * @member {Boolean} engine.model.TreeWalker#singleCharacters
  98. */
  99. this.singleCharacters = !!singleCharacters;
  100. /**
  101. * Flag indicating whether iterator should enter elements or not. If the iterator is shallow child nodes of any
  102. * iterated node will not be returned along with `ELEMENT_END` tag.
  103. *
  104. * @readonly
  105. * @member {Boolean} engine.model.TreeWalker#shallow
  106. */
  107. this.shallow = !!shallow;
  108. /**
  109. * Flag indicating whether iterator should ignore `ELEMENT_END` tags. If the option is true walker will not
  110. * return a parent node of the start position. If this option is `true` each {@link engine.model.Element} will
  111. * be returned once, while if the option is `false` they might be returned twice:
  112. * for `'ELEMENT_START'` and `'ELEMENT_END'`.
  113. *
  114. * @readonly
  115. * @member {Boolean} engine.model.TreeWalker#ignoreElementEnd
  116. */
  117. this.ignoreElementEnd = !!ignoreElementEnd;
  118. /**
  119. * Start boundary cached for optimization purposes.
  120. *
  121. * @private
  122. * @member {engine.model.Element} engine.model.TreeWalker#_boundaryStartParent
  123. */
  124. this._boundaryStartParent = this.boundaries ? this.boundaries.start.parent : null;
  125. /**
  126. * End boundary cached for optimization purposes.
  127. *
  128. * @private
  129. * @member {engine.model.Element} engine.model.TreeWalker#_boundaryEndParent
  130. */
  131. this._boundaryEndParent = this.boundaries ? this.boundaries.end.parent : null;
  132. /**
  133. * Parent of the most recently visited node. Cached for optimization purposes.
  134. *
  135. * @private
  136. * @member {engine.model.Element|engine.model.DocumentFragment} engine.model.TreeWalker#_visitedParent
  137. */
  138. this._visitedParent = this.position.parent;
  139. }
  140. /**
  141. * Iterator interface.
  142. */
  143. [ Symbol.iterator ]() {
  144. return this;
  145. }
  146. /**
  147. * Iterator interface method.
  148. * Detects walking direction and makes step forward or backward.
  149. *
  150. * @returns {Object} Object implementing iterator interface, returning information about taken step.
  151. */
  152. next() {
  153. if ( this.direction == 'FORWARD' ) {
  154. return this._next();
  155. } else {
  156. return this._previous();
  157. }
  158. }
  159. /**
  160. * Makes a step forward in model. Moves the {@link #position} to the next position and returns the encountered value.
  161. *
  162. * @private
  163. * @returns {Object}
  164. * @returns {Boolean} return.done True if iterator is done.
  165. * @returns {engine.model.TreeWalkerValue} return.value Information about taken step.
  166. */
  167. _next() {
  168. const previousPosition = this.position;
  169. const position = Position.createFromPosition( this.position );
  170. const parent = this._visitedParent;
  171. // We are at the end of the root.
  172. if ( parent.parent === null && position.offset === parent.getChildCount() ) {
  173. return { done: true };
  174. }
  175. // We reached the walker boundary.
  176. if ( parent === this._boundaryEndParent && position.offset == this.boundaries.end.offset ) {
  177. return { done: true };
  178. }
  179. const node = parent.getChild( position.offset );
  180. if ( node instanceof Element ) {
  181. if ( !this.shallow ) {
  182. // Manual operations on path internals for optimization purposes. Here and in the rest of the method.
  183. position.path.push( 0 );
  184. this._visitedParent = node;
  185. } else {
  186. position.offset++;
  187. }
  188. this.position = position;
  189. return formatReturnValue( 'ELEMENT_START', node, previousPosition, position, 1 );
  190. } else if ( node instanceof CharacterProxy ) {
  191. if ( this.singleCharacters ) {
  192. position.offset++;
  193. this.position = position;
  194. return formatReturnValue( 'CHARACTER', node, previousPosition, position, 1 );
  195. } else {
  196. let charactersCount = node._nodeListText.text.length - node._index;
  197. let offset = position.offset + charactersCount;
  198. if ( this._boundaryEndParent == parent && this.boundaries.end.offset < offset ) {
  199. offset = this.boundaries.end.offset;
  200. charactersCount = offset - position.offset;
  201. }
  202. let textProxy = new TextProxy( node, charactersCount );
  203. position.offset = offset;
  204. this.position = position;
  205. return formatReturnValue( 'TEXT', textProxy, previousPosition, position, charactersCount );
  206. }
  207. } else {
  208. // `node` is not set, we reached the end of current `parent`.
  209. position.path.pop();
  210. position.offset++;
  211. this.position = position;
  212. this._visitedParent = parent.parent;
  213. if ( this.ignoreElementEnd ) {
  214. return this._next();
  215. } else {
  216. return formatReturnValue( 'ELEMENT_END', parent, previousPosition, position );
  217. }
  218. }
  219. }
  220. /**
  221. * Makes a step backward in model. Moves the {@link #position} to the previous position and returns the encountered value.
  222. *
  223. * @private
  224. * @returns {Object}
  225. * @returns {Boolean} return.done True if iterator is done.
  226. * @returns {engine.model.TreeWalkerValue} return.value Information about taken step.
  227. */
  228. _previous() {
  229. const previousPosition = this.position;
  230. const position = Position.createFromPosition( this.position );
  231. const parent = this._visitedParent;
  232. // We are at the beginning of the root.
  233. if ( parent.parent === null && position.offset === 0 ) {
  234. return { done: true };
  235. }
  236. // We reached the walker boundary.
  237. if ( parent == this._boundaryStartParent && position.offset == this.boundaries.start.offset ) {
  238. return { done: true };
  239. }
  240. // Get node just before current position
  241. const node = parent.getChild( position.offset - 1 );
  242. if ( node instanceof Element ) {
  243. position.offset--;
  244. if ( !this.shallow ) {
  245. position.path.push( node.getChildCount() );
  246. this.position = position;
  247. this._visitedParent = node;
  248. if ( this.ignoreElementEnd ) {
  249. return this._previous();
  250. } else {
  251. return formatReturnValue( 'ELEMENT_END', node, previousPosition, position );
  252. }
  253. } else {
  254. this.position = position;
  255. return formatReturnValue( 'ELEMENT_START', node, previousPosition, position, 1 );
  256. }
  257. } else if ( node instanceof CharacterProxy ) {
  258. if ( this.singleCharacters ) {
  259. position.offset--;
  260. this.position = position;
  261. return formatReturnValue( 'CHARACTER', node, previousPosition, position, 1 );
  262. } else {
  263. let charactersCount = node._index + 1;
  264. let offset = position.offset - charactersCount;
  265. if ( this._boundaryStartParent == parent && this.boundaries.start.offset > offset ) {
  266. offset = this.boundaries.start.offset;
  267. charactersCount = position.offset - offset;
  268. }
  269. let textFragment = new TextProxy( parent.getChild( offset ), charactersCount );
  270. position.offset = offset;
  271. this.position = position;
  272. return formatReturnValue( 'TEXT', textFragment, previousPosition, position, charactersCount );
  273. }
  274. } else {
  275. // `node` is not set, we reached the beginning of current `parent`.
  276. position.path.pop();
  277. this.position = position;
  278. this._visitedParent = parent.parent;
  279. return formatReturnValue( 'ELEMENT_START', parent, previousPosition, position, 1 );
  280. }
  281. }
  282. }
  283. function formatReturnValue( type, item, previousPosition, nextPosition, length ) {
  284. return {
  285. done: false,
  286. value: {
  287. type: type,
  288. item: item,
  289. previousPosition: previousPosition,
  290. nextPosition: nextPosition,
  291. length: length
  292. }
  293. };
  294. }
  295. /**
  296. * Type of the step made by {@link engine.model.TreeWalker}.
  297. * Possible values: `'ELEMENT_START'` if walker is at the beginning of a node, `'ELEMENT_END'` if walker is at the end of node,
  298. * `'CHARACTER'` if walker traversed over a character, or `'TEXT'` if walker traversed over multiple characters (available in
  299. * character merging mode, see {@link engine.model.TreeWalker#constructor}).
  300. *
  301. * @typedef {String} engine.model.TreeWalkerValueType
  302. */
  303. /**
  304. * Object returned by {@link engine.model.TreeWalker} when traversing tree model.
  305. *
  306. * @typedef {Object} engine.model.TreeWalkerValue
  307. * @property {engine.model.TreeWalkerValueType} type
  308. * @property {engine.model.Item} item Item between old and new positions of {@link engine.model.TreeWalker}.
  309. * @property {engine.model.Position} previousPosition Previous position of the iterator.
  310. * * Forward iteration: For `'ELEMENT_END'` it is the last position inside the element. For all other types it is the
  311. * position before the item. Note that it is more efficient to use this position then calculate the position before
  312. * the node using {@link engine.model.Position.createBefore}. It is also more efficient to get the
  313. * position after node by shifting `previousPosition` by `length`, using {@link engine.model.Position#getShiftedBy},
  314. * then calculate the position using {@link engine.model.Position.createAfter}.
  315. * * Backward iteration: For `'ELEMENT_START'` it is the first position inside the element. For all other types it is
  316. * the position after item.
  317. * @property {engine.model.Position} nextPosition Next position of the iterator.
  318. * * Forward iteration: For `'ELEMENT_START'` it is the first position inside the element. For all other types it is
  319. * the position after the item.
  320. * * Backward iteration: For `'ELEMENT_END'` it is last position inside element. For all other types it is the position
  321. * before the item.
  322. * @property {Number} [length] Length of the item. For `'ELEMENT_START'` and `'CHARACTER'` it is 1. For `'TEXT'` it is
  323. * the length of the text. For `'ELEMENT_END'` it is undefined.
  324. */
  325. /**
  326. * Tree walking directions.
  327. *
  328. * @typedef {'FORWARD'|'BACKWARD'} engine.view.TreeWalkerDirection
  329. */