treewalker.js 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448
  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 Element from './element.js';
  7. import Text from './text.js';
  8. import TextProxy from './textproxy.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.view
  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.view.Range} [options.boundaries=null] Range to define boundaries of the iterator.
  23. * @param {engine.view.Position} [options.startPosition] Starting position.
  24. * @param {'FORWARD'|'BACKWARD'} [options.direction='FORWARD'] Walking direction.
  25. * @param {Boolean} [options.singleCharacters=false] Flag indicating whether all characters from
  26. * {@link engine.view.Text} should be returned as one {@link engine.view.Text} (`false`) ore one by one as
  27. * {@link engine.view.TextProxy} (`true`).
  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.view.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( options = {} ) {
  36. if ( !options.boundaries && !options.startPosition ) {
  37. /**
  38. * Neither boundaries nor starting position have been defined.
  39. *
  40. * @error tree-walker-no-start-position
  41. */
  42. throw new CKEditorError( 'tree-walker-no-start-position: Neither boundaries nor starting position have been defined.' );
  43. }
  44. if ( options.direction && options.direction != 'FORWARD' && options.direction != 'BACKWARD' ) {
  45. throw new CKEditorError(
  46. 'tree-walker-unknown-direction: Only `BACKWARD` and `FORWARD` direction allowed.',
  47. { direction: options.direction }
  48. );
  49. }
  50. /**
  51. * Iterator boundaries.
  52. *
  53. * When the iterator is walking `FORWARD` on the end of boundary or is walking `BACKWARD`
  54. * on the start of boundary, then `{ done: true }` is returned.
  55. *
  56. * If boundaries are not defined they are set before first and after last child of the root node.
  57. *
  58. * @readonly
  59. * @member {engine.view.Range} engine.view.TreeWalker#boundaries
  60. */
  61. this.boundaries = options.boundaries || null;
  62. /**
  63. * Iterator position. If start position is not defined then position depends on {@link #direction}. If direction is
  64. * `FORWARD` position starts form the beginning, when direction is `BACKWARD` position starts from the end.
  65. *
  66. * @readonly
  67. * @member {engine.view.Position} engine.view.TreeWalker#position
  68. */
  69. if ( options.startPosition ) {
  70. this.position = Position.createFromPosition( options.startPosition );
  71. } else {
  72. this.position = Position.createFromPosition( options.boundaries[ options.direction == 'BACKWARD' ? 'end' : 'start' ] );
  73. }
  74. /**
  75. * Walking direction. Defaults `FORWARD`.
  76. *
  77. * @readonly
  78. * @member {'BACKWARD'|'FORWARD'} engine.view.TreeWalker#direction
  79. */
  80. this.direction = options.direction || 'FORWARD';
  81. /**
  82. * Flag indicating whether all characters from {@link engine.view.Text} should be returned as one
  83. * {@link engine.view.Text} or one by one as {@link.engine.TextProxy}.
  84. *
  85. * @readonly
  86. * @member {Boolean} engine.view.TreeWalker#singleCharacters
  87. */
  88. this.singleCharacters = !!options.singleCharacters;
  89. /**
  90. * Flag indicating whether iterator should enter elements or not. If the iterator is shallow child nodes of any
  91. * iterated node will not be returned along with `ELEMENT_END` tag.
  92. *
  93. * @readonly
  94. * @member {Boolean} engine.view.TreeWalker#shallow
  95. */
  96. this.shallow = !!options.shallow;
  97. /**
  98. * Flag indicating whether iterator should ignore `ELEMENT_END` tags. If the option is true walker will not
  99. * return a parent node of the start position. If this option is `true` each {@link engine.view.Element} will
  100. * be returned once, while if the option is `false` they might be returned twice:
  101. * for `'ELEMENT_START'` and `'ELEMENT_END'`.
  102. *
  103. * @readonly
  104. * @member {Boolean} engine.view.TreeWalker#ignoreElementEnd
  105. */
  106. this.ignoreElementEnd = !!options.ignoreElementEnd;
  107. /**
  108. * Start boundary cached for optimization purposes.
  109. *
  110. * @private
  111. * @member {engine.view.Element} engine.view.TreeWalker#_boundaryStartParent
  112. */
  113. this._boundaryStartParent = this.boundaries ? this.boundaries.start.parent : null;
  114. /**
  115. * End boundary cached for optimization purposes.
  116. *
  117. * @private
  118. * @member {engine.view.Element} engine.view.TreeWalker#_boundaryEndParent
  119. */
  120. this._boundaryEndParent = this.boundaries ? this.boundaries.end.parent : null;
  121. }
  122. /**
  123. * Iterator interface.
  124. */
  125. [ Symbol.iterator ]() {
  126. return this;
  127. }
  128. /**
  129. * Iterator interface method.
  130. * Detects walking direction and makes step forward or backward.
  131. *
  132. * @returns {Object} Object implementing iterator interface, returning information about taken step.
  133. */
  134. next() {
  135. if ( this.direction == 'FORWARD' ) {
  136. return this._next();
  137. } else {
  138. return this._previous();
  139. }
  140. }
  141. /**
  142. * Makes a step forward in view. Moves the {@link #position} to the next position and returns the encountered value.
  143. *
  144. * @private
  145. * @returns {Object}
  146. * @returns {Boolean} return.done True if iterator is done.
  147. * @returns {engine.view.TreeWalkerValue} return.value Information about taken step.
  148. */
  149. _next() {
  150. let position = Position.createFromPosition( this.position );
  151. const previousPosition = this.position;
  152. const parent = position.parent;
  153. // We are at the end of the root.
  154. if ( parent.parent === null && position.offset === parent.getChildCount() ) {
  155. return { done: true };
  156. }
  157. // We reached the walker boundary.
  158. if ( parent === this._boundaryEndParent && position.offset == this.boundaries.end.offset ) {
  159. return { done: true };
  160. }
  161. // Get node just after current position.
  162. let node;
  163. // Text is a specific parent because it contains string instead of child nodes.
  164. if ( parent instanceof Text ) {
  165. node = parent.data[ position.offset ];
  166. } else {
  167. node = parent.getChild( position.offset );
  168. }
  169. if ( node instanceof Element ) {
  170. if ( !this.shallow ) {
  171. position = new Position( node, 0 );
  172. } else {
  173. position.offset++;
  174. }
  175. this.position = position;
  176. return this._formatReturnValue( 'ELEMENT_START', node, previousPosition, position, 1 );
  177. } else if ( node instanceof Text ) {
  178. if ( this.singleCharacters ) {
  179. position = new Position( node, 0 );
  180. this.position = position;
  181. return this._next();
  182. } else {
  183. let charactersCount = node.data.length;
  184. let item = node;
  185. // If text stick out of walker range, we need to cut it and wrap by TextProxy.
  186. if ( node == this._boundaryEndParent ) {
  187. charactersCount = this.boundaries.end.offset;
  188. item = new TextProxy( node, 0, charactersCount );
  189. position = Position.createAfter( item );
  190. } else {
  191. // If not just keep moving forward.
  192. position.offset++;
  193. }
  194. this.position = position;
  195. return this._formatReturnValue( 'TEXT', item, previousPosition, position, charactersCount );
  196. }
  197. } else if ( typeof node == 'string' ) {
  198. let textLength;
  199. if ( this.singleCharacters ) {
  200. textLength = 1;
  201. } else {
  202. // Check if text stick out of walker range.
  203. const endOffset = parent === this._boundaryEndParent ? this.boundaries.end.offset : parent.data.length;
  204. textLength = endOffset - position.offset;
  205. }
  206. const textProxy = new TextProxy( parent, position.offset, textLength );
  207. position.offset += textLength;
  208. this.position = position;
  209. return this._formatReturnValue( 'TEXT', textProxy, previousPosition, position, textLength );
  210. } else {
  211. // `node` is not set, we reached the end of current `parent`.
  212. position = Position.createAfter( parent );
  213. this.position = position;
  214. if ( this.ignoreElementEnd ) {
  215. return this._next();
  216. } else {
  217. return this._formatReturnValue( 'ELEMENT_END', parent, previousPosition, position );
  218. }
  219. }
  220. }
  221. /**
  222. * Makes a step backward in view. Moves the {@link #position} to the previous position and returns the encountered value.
  223. *
  224. * @private
  225. * @returns {Object}
  226. * @returns {Boolean} return.done True if iterator is done.
  227. * @returns {engine.view.TreeWalkerValue} return.value Information about taken step.
  228. */
  229. _previous() {
  230. let position = Position.createFromPosition( this.position );
  231. const previousPosition = this.position;
  232. const parent = position.parent;
  233. // We are at the beginning of the root.
  234. if ( parent.parent === null && position.offset === 0 ) {
  235. return { done: true };
  236. }
  237. // We reached the walker boundary.
  238. if ( parent == this._boundaryStartParent && position.offset == this.boundaries.start.offset ) {
  239. return { done: true };
  240. }
  241. // Get node just before current position.
  242. let node;
  243. // Text {@link engine.view.Text} element is a specific parent because contains string instead of child nodes.
  244. if ( parent instanceof Text ) {
  245. node = parent._data[ position.offset - 1 ];
  246. } else {
  247. node = parent.getChild( position.offset - 1 );
  248. }
  249. if ( node instanceof Element ) {
  250. if ( !this.shallow ) {
  251. position = new Position( node, node.getChildCount() );
  252. this.position = position;
  253. if ( this.ignoreElementEnd ) {
  254. return this._previous();
  255. } else {
  256. return this._formatReturnValue( 'ELEMENT_END', node, previousPosition, position );
  257. }
  258. } else {
  259. position.offset--;
  260. this.position = position;
  261. return this._formatReturnValue( 'ELEMENT_START', node, previousPosition, position, 1 );
  262. }
  263. } else if ( node instanceof Text ) {
  264. if ( this.singleCharacters ) {
  265. position = new Position( node, node.data.length );
  266. this.position = position;
  267. return this._previous();
  268. } else {
  269. let charactersCount = node.data.length;
  270. let item = node;
  271. // If text stick out of walker range, we need to cut it and wrap by TextProxy.
  272. if ( node == this._boundaryStartParent ) {
  273. const offset = this.boundaries.start.offset;
  274. item = new TextProxy( node, offset );
  275. charactersCount = item.data.length;
  276. position = Position.createBefore( item );
  277. } else {
  278. // If not just keep moving backward.
  279. position.offset--;
  280. }
  281. this.position = position;
  282. return this._formatReturnValue( 'TEXT', item, previousPosition, position, charactersCount );
  283. }
  284. } else if ( typeof node == 'string' ) {
  285. let textLength;
  286. if ( !this.singleCharacters ) {
  287. // Check if text stick out of walker range.
  288. const startOffset = parent === this._boundaryStartParent ? this.boundaries.start.offset : 0;
  289. textLength = position.offset - startOffset;
  290. } else {
  291. textLength = 1;
  292. }
  293. position.offset -= textLength;
  294. const textProxy = new TextProxy( parent, position.offset, textLength );
  295. this.position = position;
  296. return this._formatReturnValue( 'TEXT', textProxy, previousPosition, position, textLength );
  297. } else {
  298. // `node` is not set, we reached the beginning of current `parent`.
  299. position = Position.createBefore( parent );
  300. this.position = position;
  301. return this._formatReturnValue( 'ELEMENT_START', parent, previousPosition, position, 1 );
  302. }
  303. }
  304. /**
  305. * Format returned data and adjust `previousPosition` and `nextPosition` if reach the bound of the {@link engine.view.Text}.
  306. *
  307. * @private
  308. * @param {engine.view.TreeWalkerValueType} type Type of step.
  309. * @param {engine.view.Item} item Item between old and new position.
  310. * @param {engine.view.Position} previousPosition Previous position of iterator.
  311. * @param {engine.view.Position} nextPosition Next position of iterator.
  312. * @param {Number} [length] Length of the item.
  313. * @returns {engine.view.TreeWalkerValue}
  314. */
  315. _formatReturnValue( type, item, previousPosition, nextPosition, length ) {
  316. // Text is a specific parent, because contains string instead of childs.
  317. // Walker doesn't enter to the Text except situations when walker is iterating over every single character,
  318. // or the bound starts/ends inside the Text. So when the position is at the beginning or at the end of the Text
  319. // we move it just before or just after Text.
  320. if ( item instanceof TextProxy ) {
  321. // Position is at the end of Text.
  322. if ( item.index + item.data.length == item.textNode.data.length ) {
  323. if ( this.direction == 'FORWARD' ) {
  324. nextPosition = Position.createAfter( item.textNode );
  325. // When we change nextPosition of returned value we need also update walker current position.
  326. this.position = nextPosition;
  327. } else {
  328. previousPosition = Position.createAfter( item.textNode );
  329. }
  330. }
  331. // Position is at the begining ot the text.
  332. if ( item.index === 0 ) {
  333. if ( this.direction == 'FORWARD' ) {
  334. previousPosition = Position.createBefore( item.textNode );
  335. } else {
  336. nextPosition = Position.createBefore( item.textNode );
  337. // When we change nextPosition of returned value we need also update walker current position.
  338. this.position = nextPosition;
  339. }
  340. }
  341. }
  342. return {
  343. done: false,
  344. value: {
  345. type: type,
  346. item: item,
  347. previousPosition: previousPosition,
  348. nextPosition: nextPosition,
  349. length: length
  350. }
  351. };
  352. }
  353. }
  354. /**
  355. * Type of the step made by {@link engine.view.TreeWalker}.
  356. * Possible values: `'ELEMENT_START'` if walker is at the beginning of a node, `'ELEMENT_END'` if walker is at the end
  357. * of node, or `'TEXT'` if walker traversed over single and multiple characters.
  358. * For {@link engine.view.Text} `ELEMENT_START` and `ELEMENT_END` is not returned.
  359. *
  360. * @typedef {String} engine.view.TreeWalkerValueType
  361. */
  362. /**
  363. * Object returned by {@link engine.view.TreeWalker} when traversing tree view.
  364. *
  365. * @typedef {Object} engine.view.TreeWalkerValue
  366. * @property {engine.view.TreeWalkerValueType} type
  367. * @property {engine.view.Item} item Item between old and new positions of {@link engine.view.TreeWalker}.
  368. * @property {engine.view.Position} previousPosition Previous position of the iterator.
  369. * * Forward iteration: For `'ELEMENT_END'` it is the last position inside the element. For all other types it is the
  370. * position before the item. Note that it is more efficient to use this position then calculate the position before
  371. * the node using {@link engine.view.Position.createBefore}.
  372. * * Backward iteration: For `'ELEMENT_START'` it is the first position inside the element. For all other types it is
  373. * the position after item.
  374. * * If the position is at the beginning or at the end of the {@link engine.view.Text} it is always moved from the
  375. * inside of the Text to its parent just before or just after Text.
  376. * @property {engine.view.Position} nextPosition Next position of the iterator.
  377. * * Forward iteration: For `'ELEMENT_START'` it is the first position inside the element. For all other types it is
  378. * the position after the item.
  379. * * Backward iteration: For `'ELEMENT_END'` it is last position inside element. For all other types it is the position
  380. * before the item.
  381. * * If the position is at the beginning or at the end of the {@link engine.view.Text} it is always moved from the
  382. * inside of the Text to its parent just before or just after Text.
  383. * @property {Number} [length] Length of the item. For `'ELEMENT_START'` it is 1. For `'TEXT'` it is
  384. * the length of the text. For `'ELEMENT_END'` it is undefined.
  385. */
  386. /**
  387. * Tree walking directions.
  388. *
  389. * @typedef {'FORWARD'|'BACKWARD'} engine.view.TreeWalkerDirection
  390. */