treewalker.js 15 KB

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