treewalker.js 16 KB

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