treewalker.js 15 KB

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