8
0

treewalker.js 13 KB

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