treewalker.js 18 KB

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