8
0

range.js 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489
  1. /**
  2. * @license Copyright (c) 2003-2016, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. 'use strict';
  6. import Position from './position.js';
  7. import TreeWalker from './treewalker.js';
  8. import utils from '../utils.js';
  9. /**
  10. * Range class. Range is iterable.
  11. *
  12. * @memberOf core.treeModel
  13. */
  14. export default class Range {
  15. /**
  16. * Creates a range spanning from `start` position to `end` position.
  17. * **Note:** Constructor creates it's own {@link core.treeModel.Position} instances basing on passed values.
  18. *
  19. * @param {core.treeModel.Position} start Start position.
  20. * @param {core.treeModel.Position} end End position.
  21. */
  22. constructor( start, end ) {
  23. /**
  24. * Start position.
  25. *
  26. * @private
  27. * @member {core.treeModel.Position} core.treeModel.Range#start
  28. */
  29. this.start = Position.createFromPosition( start );
  30. /**
  31. * End position.
  32. *
  33. * @private
  34. * @member {core.treeModel.Position} core.treeModel.Range#end
  35. */
  36. this.end = Position.createFromPosition( end );
  37. }
  38. /**
  39. * Returns whether the range is collapsed, that is it start and end positions are equal.
  40. *
  41. * @type {Boolean}
  42. */
  43. get isCollapsed() {
  44. return this.start.isEqual( this.end );
  45. }
  46. /**
  47. * Returns whether this range is flat, that is if start position and end position are in the same parent.
  48. *
  49. * @returns {Boolean}
  50. */
  51. get isFlat() {
  52. return this.start.parent === this.end.parent;
  53. }
  54. /**
  55. * Range root element. Equals to the root of start position (which should be same as root of end position).
  56. *
  57. * @type {core.treeModel.RootElement}
  58. */
  59. get root() {
  60. return this.start.root;
  61. }
  62. /**
  63. * Checks whether this contains given {@link core.treeModel.Position position}.
  64. *
  65. * @param {core.treeModel.Position} position Position to check.
  66. * @returns {Boolean} True if given {@link core.treeModel.Position position} is contained.
  67. */
  68. containsPosition( position ) {
  69. return position.isAfter( this.start ) && position.isBefore( this.end );
  70. }
  71. /**
  72. * Checks whether this range contains given {@link core.treeModel.Range range}.
  73. *
  74. * @param {core.treeModel.Range} otherRange Range to check.
  75. * @returns {Boolean} True if given {@link core.treeModel.Range range} boundaries are contained by this range.
  76. */
  77. containsRange( otherRange ) {
  78. return this.containsPosition( otherRange.start ) && this.containsPosition( otherRange.end );
  79. }
  80. /**
  81. * Gets a part of this {@link core.treeModel.Range range} which is not a part of given {@link core.treeModel.Range range}. Returned
  82. * array contains zero, one or two {@link core.treeModel.Range ranges}.
  83. *
  84. * Examples:
  85. *
  86. * let range = new Range( new Position( root, [ 2, 7 ] ), new Position( root, [ 4, 0, 1 ] ) );
  87. * let otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 5 ] ) );
  88. * let transformed = range.getDifference( otherRange );
  89. * // transformed array has no ranges because `otherRange` contains `range`
  90. *
  91. * otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 3 ] ) );
  92. * transformed = range.getDifference( otherRange );
  93. * // transformed array has one range: from [ 3 ] to [ 4, 0, 1 ]
  94. *
  95. * otherRange = new Range( new Position( root, [ 3 ] ), new Position( root, [ 4 ] ) );
  96. * transformed = range.getDifference( otherRange );
  97. * // transformed array has two ranges: from [ 2, 7 ] to [ 3 ] and from [ 4 ] to [ 4, 0, 1 ]
  98. *
  99. * @param {core.treeModel.Range} otherRange Range to differentiate against.
  100. * @returns {Array.<core.treeModel.Range>} The difference between ranges.
  101. */
  102. getDifference( otherRange ) {
  103. const ranges = [];
  104. if ( this.isIntersecting( otherRange ) ) {
  105. // Ranges intersect.
  106. if ( this.containsPosition( otherRange.start ) ) {
  107. // Given range start is inside this range. This means that we have to
  108. // add shrunken range - from the start to the middle of this range.
  109. ranges.push( new Range( this.start, otherRange.start ) );
  110. }
  111. if ( this.containsPosition( otherRange.end ) ) {
  112. // Given range end is inside this range. This means that we have to
  113. // add shrunken range - from the middle of this range to the end.
  114. ranges.push( new Range( otherRange.end, this.end ) );
  115. }
  116. } else {
  117. // Ranges do not intersect, return the original range.
  118. ranges.push( Range.createFromRange( this ) );
  119. }
  120. return ranges;
  121. }
  122. /**
  123. * Returns an intersection of this {@link core.treeModel.Range range} and given {@link core.treeModel.Range range}. Intersection
  124. * is a common part of both of those ranges. If ranges has no common part, returns `null`.
  125. *
  126. * Examples:
  127. *
  128. * let range = new Range( new Position( root, [ 2, 7 ] ), new Position( root, [ 4, 0, 1 ] ) );
  129. * let otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 2 ] ) );
  130. * let transformed = range.getIntersection( otherRange ); // null - ranges have no common part
  131. *
  132. * otherRange = new Range( new Position( root, [ 3 ] ), new Position( root, [ 5 ] ) );
  133. * transformed = range.getIntersection( otherRange ); // range from [ 3 ] to [ 4, 0, 1 ]
  134. *
  135. * @param {core.treeModel.Range} otherRange Range to check for intersection.
  136. * @returns {core.treeModel.Range|null} A common part of given ranges or null if ranges have no common part.
  137. */
  138. getIntersection( otherRange ) {
  139. if ( this.isIntersecting( otherRange ) ) {
  140. // Ranges intersect, so a common range will be returned.
  141. // At most, it will be same as this range.
  142. let commonRangeStart = this.start;
  143. let commonRangeEnd = this.end;
  144. if ( this.containsPosition( otherRange.start ) ) {
  145. // Given range start is inside this range. This means thaNt we have to
  146. // shrink common range to the given range start.
  147. commonRangeStart = otherRange.start;
  148. }
  149. if ( this.containsPosition( otherRange.end ) ) {
  150. // Given range end is inside this range. This means that we have to
  151. // shrink common range to the given range end.
  152. commonRangeEnd = otherRange.end;
  153. }
  154. return new Range( commonRangeStart, commonRangeEnd );
  155. }
  156. // Ranges do not intersect, so they do not have common part.
  157. return null;
  158. }
  159. /**
  160. * Computes and returns the smallest set of {@link #isFlat flat} ranges, that covers this range in whole.
  161. * Assuming that tree model model structure is ("[" and "]" are range boundaries):
  162. *
  163. * root root
  164. * |- element DIV DIV P2 P3 DIV
  165. * | |- element H H P1 f o o b a r H P4
  166. * | | |- "fir[st" fir[st lorem se]cond ipsum
  167. * | |- element P1
  168. * | | |- "lorem" ||
  169. * |- element P2 ||
  170. * | |- "foo" VV
  171. * |- element P3
  172. * | |- "bar" root
  173. * |- element DIV DIV [P2 P3] DIV
  174. * | |- element H H [P1] f o o b a r H P4
  175. * | | |- "se]cond" fir[st] lorem [se]cond ipsum
  176. * | |- element P4
  177. * | | |- "ipsum"
  178. *
  179. * As it can be seen, letters contained in the range are stloremfoobarse, spread across different parents.
  180. * We are looking for minimal set of {@link #isFlat flat} ranges that contains the same nodes.
  181. *
  182. * Minimal flat ranges for above range `( [ 0, 0, 3 ], [ 3, 0, 2 ] )` will be:
  183. *
  184. * ( [ 0, 0, 3 ], [ 0, 0, 5 ] ) = "st"
  185. * ( [ 0, 1 ], [ 0, 2 ] ) = element P1 ("lorem")
  186. * ( [ 1 ], [ 3 ] ) = element P2, element P3 ("foobar")
  187. * ( [ 3, 0, 0 ], [ 3, 0, 2 ] ) = "se"
  188. *
  189. * **Note:** this method is not returning flat ranges that contain no nodes. It may also happen that not-collapsed
  190. * range will return an empty array of flat ranges.
  191. *
  192. * @returns {Array.<core.treeModel.Range>} Array of flat ranges.
  193. */
  194. getMinimalFlatRanges() {
  195. let ranges = [];
  196. // We find on which tree-level start and end have the lowest common ancestor
  197. let cmp = utils.compareArrays( this.start.path, this.end.path );
  198. // If comparison returned string it means that arrays are same.
  199. let diffAt = ( typeof cmp == 'string' ) ? Math.min( this.start.path.length, this.end.path.length ) : cmp;
  200. let pos = Position.createFromPosition( this.start );
  201. let posParent = pos.parent;
  202. // Go up.
  203. while ( pos.path.length > diffAt + 1 ) {
  204. let howMany = posParent.getChildCount() - pos.offset;
  205. if ( howMany !== 0 ) {
  206. ranges.push( new Range( pos, pos.getShiftedBy( howMany ) ) );
  207. }
  208. pos.path = pos.path.slice( 0, -1 );
  209. pos.offset++;
  210. posParent = posParent.parent;
  211. }
  212. // Go down.
  213. while ( pos.path.length <= this.end.path.length ) {
  214. let offset = this.end.path[ pos.path.length - 1 ];
  215. let howMany = offset - pos.offset;
  216. if ( howMany !== 0 ) {
  217. ranges.push( new Range( pos, pos.getShiftedBy( howMany ) ) );
  218. }
  219. pos.offset = offset;
  220. pos.path.push( 0 );
  221. }
  222. return ranges;
  223. }
  224. /**
  225. * Returns an iterator that iterates over all {@link core.treeModel.Item items} that are in this range and returns
  226. * them together with additional information like length or {@link core.treeModel.Position positions},
  227. * grouped as {@link core.treeModel.TreeWalkerValue}. It iterates over all {@link core.treeModel.TextFragment texts}
  228. * that are inside the range and all the {@link core.treeModel.Element}s we enter into when iterating over this
  229. * range.
  230. *
  231. * **Note:** iterator will not return a parent node of start position. This is in contrary to
  232. * {@link core.treeModel.TreeWalker} which will return that node with `'ELEMENT_END'` type. Iterator also
  233. * returns each {@link core.treeModel.Element} once, while simply used {@link core.treeModel.TreeWalker} might
  234. * return it twice: for `'ELEMENT_START'` and `'ELEMENT_END'`.
  235. *
  236. * **Note:** because iterator does not return {@link core.treeModel.TreeWalkerValue values} with the type of
  237. * `'ELEMENT_END'`, you can use {@link core.treeModel.TreeWalkerValue.previousPosition} as a position before the
  238. * item.
  239. *
  240. * @see {@link core.treeModel.TreeWalker}
  241. * @returns {Iterable.<core.treeModel.TreeWalkerValue>}
  242. */
  243. *[ Symbol.iterator ]() {
  244. const treeWalker = new TreeWalker( { boundaries: this } );
  245. for ( let value of treeWalker ) {
  246. if ( value.type != 'ELEMENT_END' ) {
  247. yield value;
  248. }
  249. }
  250. }
  251. /**
  252. * Returns an iterator that iterates over all {@link core.treeModel.Item items} that are in this range and returns
  253. * them. It iterates over all {@link core.treeModel.CharacterProxy characters} or
  254. * {@link core.treeModel.TextFragment texts} that are inside the range and all the {@link core.treeModel.Element}s
  255. * we enter into when iterating over this range.
  256. *
  257. * **Note:** this method will not return a parent node of start position. This is in contrary to
  258. * {@link core.treeModel.TreeWalker} which will return that node with `'ELEMENT_END'` type. This method also
  259. * returns each {@link core.treeModel.Element} once, while simply used {@link core.treeModel.TreeWalker} might
  260. * return it twice: for `'ELEMENT_START'` and `'ELEMENT_END'`.
  261. *
  262. * @see {@link core.treeModel.TreeWalker}
  263. * @param {Boolean} [singleCharacters] Flag indicating whether all consecutive characters with the same attributes
  264. * should be returned one by one as multiple {@link core.treeModel.CharacterProxy} (`true`) objects or as one
  265. * {@link core.treeModel.TextFragment} (`false`). Defaults to `false`.
  266. * @returns {Iterable.<core.treeModel.Item>}
  267. */
  268. *getItems( singleCharacters ) {
  269. const treeWalker = new TreeWalker( { boundaries: this, singleCharacters: singleCharacters } );
  270. for ( let value of treeWalker ) {
  271. if ( value.type != 'ELEMENT_END' ) {
  272. yield value.item;
  273. }
  274. }
  275. }
  276. /**
  277. * Returns an iterator that iterates over all {@link core.treeModel.Position positions} that are boundaries or
  278. * contained in this range.
  279. *
  280. * @param {Boolean} [singleCharacters] Flag indicating whether all consecutive characters with the same attributes
  281. * should be returned one by one as multiple {@link core.treeModel.CharacterProxy} (`true`) objects or as one
  282. * {@link core.treeModel.TextFragment} (`false`). Defaults to `false`.
  283. * @returns {Iterable.<core.treeModel.Position>}
  284. */
  285. *getPositions( singleCharacters ) {
  286. const treeWalker = new TreeWalker( { boundaries: this, singleCharacters: singleCharacters } );
  287. yield treeWalker.position;
  288. for ( let value of treeWalker ) {
  289. yield value.nextPosition;
  290. }
  291. }
  292. /**
  293. * Returns an iterator that iterates over all {@link core.treeModel.Node nodes} that are top-level nodes in this range
  294. * and returns them. A node is a top-level node when it is in the range but it's parent is not. In other words,
  295. * this function splits the range into separate sub-trees and iterates over their roots.
  296. *
  297. * @param {Boolean} [singleCharacters] Flag indicating whether all consecutive characters with the same attributes
  298. * should be returned one by one as multiple {@link core.treeModel.CharacterProxy} (`true`) objects or as one
  299. * {@link core.treeModel.TextFragment} (`false`). Defaults to `false`.
  300. * @returns {Iterable.<core.treeModel.Node|treeModel.TextFragment>}
  301. */
  302. *getTopLevelNodes( singleCharacters ) {
  303. let flatRanges = this.getMinimalFlatRanges();
  304. for ( let range of flatRanges ) {
  305. // This loop could be much simpler as we could just iterate over siblings of node after the first
  306. // position of each range. But then we would have to re-implement character merging strategy here.
  307. let it = new TreeWalker( { boundaries: range, singleCharacters: singleCharacters } );
  308. let step;
  309. // We will only return nodes that are on same level as node after the range start. To do this,
  310. // we keep "depth" counter.
  311. let depth = 0;
  312. do {
  313. step = it.next();
  314. if ( step.value ) {
  315. if ( step.value.type == 'ELEMENT_START' ) {
  316. depth++;
  317. } else if ( step.value.type == 'ELEMENT_END' ) {
  318. depth--;
  319. }
  320. if ( depth === 0 ) {
  321. yield step.value.item;
  322. }
  323. }
  324. } while ( !step.done );
  325. }
  326. }
  327. /**
  328. * Returns an array containing one or two {core.treeModel.Range ranges} that are a result of transforming this
  329. * {@link core.treeModel.Range range} by inserting `howMany` nodes at `insertPosition`. Two {@link core.treeModel.Range ranges} are
  330. * returned if the insertion was inside this {@link core.treeModel.Range range}.
  331. *
  332. * Examples:
  333. *
  334. * let range = new Range( new Position( root, [ 2, 7 ] ), new Position( root, [ 4, 0, 1 ] ) );
  335. * let transformed = range.getTransformedByInsertion( new Position( root, [ 1 ] ), 2 );
  336. * // transformed array has one range from [ 4, 7 ] to [ 6, 0, 1 ]
  337. *
  338. * transformed = range.getTransformedByInsertion( new Position( root, [ 3, 2 ] ), 4 );
  339. * // transformed array has two ranges: from [ 2, 7 ] to [ 3, 2 ] and from [ 3, 6 ] to [ 4, 0, 1 ]
  340. *
  341. * transformed = range.getTransformedByInsertion( new Position( root, [ 3, 2 ] ), 4, true );
  342. * // transformed array has one range which is equal to `range`. This is because of spreadOnlyOnSameLevel flag.
  343. *
  344. * @param {core.treeModel.Position} insertPosition Position where nodes are inserted.
  345. * @param {Number} howMany How many nodes are inserted.
  346. * @param {Boolean} spreadOnlyOnSameLevel Flag indicating whether this {core.treeModel.Range range} should be spread
  347. * if insertion was inside a node from this {core.treeModel.Range range} but not in the range itself.
  348. * @returns {Array.<core.treeModel.Range>} Result of the transformation.
  349. */
  350. getTransformedByInsertion( insertPosition, howMany, spreadOnlyOnSameLevel ) {
  351. // Flag indicating whether this whole range and given insertPosition is on the same tree level.
  352. const areOnSameLevel = utils.compareArrays( this.start.getParentPath(), this.end.getParentPath() ) == 'SAME' &&
  353. utils.compareArrays( this.start.getParentPath(), insertPosition.getParentPath() ) == 'SAME';
  354. if ( this.containsPosition( insertPosition ) && ( !spreadOnlyOnSameLevel || areOnSameLevel ) ) {
  355. // Range has to be spread. The first part is from original start to the spread point.
  356. // The other part is from spread point to the original end, but transformed by
  357. // insertion to reflect insertion changes.
  358. return [
  359. new Range( this.start, insertPosition ),
  360. new Range(
  361. insertPosition.getTransformedByInsertion( insertPosition, howMany, true ),
  362. this.end.getTransformedByInsertion( insertPosition, howMany, true )
  363. )
  364. ];
  365. } else {
  366. // If insertion is not inside the range, simply transform range boundaries (positions) by the insertion.
  367. // Both, one or none of them might be affected by the insertion.
  368. const range = Range.createFromRange( this );
  369. range.start = range.start.getTransformedByInsertion( insertPosition, howMany, true );
  370. range.end = range.end.getTransformedByInsertion( insertPosition, howMany, false );
  371. return [ range ];
  372. }
  373. }
  374. /**
  375. * Two ranges equal if their start and end positions equal.
  376. *
  377. * @param {core.treeModel.Range} otherRange Range to compare with.
  378. * @returns {Boolean} True if ranges equal.
  379. */
  380. isEqual( otherRange ) {
  381. return this.start.isEqual( otherRange.start ) && this.end.isEqual( otherRange.end );
  382. }
  383. /**
  384. * Checks and returns whether this range intersects with given range.
  385. *
  386. * @param {core.treeModel.Range} otherRange Range to compare with.
  387. * @returns {Boolean} True if ranges intersect.
  388. */
  389. isIntersecting( otherRange ) {
  390. return this.start.isBefore( otherRange.end ) && this.end.isAfter( otherRange.start );
  391. }
  392. /**
  393. * Creates a range inside an element which starts before the first child and ends after the last child.
  394. *
  395. * @param {core.treeModel.Element} element Element which is a parent for the range.
  396. * @returns {core.treeModel.Range} Created range.
  397. */
  398. static createFromElement( element ) {
  399. return this.createFromParentsAndOffsets( element, 0, element, element.getChildCount() );
  400. }
  401. /**
  402. * Creates a new range spreading from specified position to the same position moved by given shift.
  403. *
  404. * @param {core.treeModel.Position} position Beginning of the range.
  405. * @param {Number} shift How long the range should be.
  406. * @returns {core.treeModel.Range}
  407. */
  408. static createFromPositionAndShift( position, shift ) {
  409. return new this( position, position.getShiftedBy( shift ) );
  410. }
  411. /**
  412. * Creates a range from given parents and offsets.
  413. *
  414. * @param {core.treeModel.Element} startElement Start position parent element.
  415. * @param {Number} startOffset Start position offset.
  416. * @param {core.treeModel.Element} endElement End position parent element.
  417. * @param {Number} endOffset End position offset.
  418. * @returns {core.treeModel.Range} Created range.
  419. */
  420. static createFromParentsAndOffsets( startElement, startOffset, endElement, endOffset ) {
  421. return new this(
  422. Position.createFromParentAndOffset( startElement, startOffset ),
  423. Position.createFromParentAndOffset( endElement, endOffset )
  424. );
  425. }
  426. /**
  427. * Creates and returns a new instance of Range which is equal to passed range.
  428. *
  429. * @param {core.treeModel.Range} range Range to clone.
  430. * @returns {core.treeModel.Range}
  431. */
  432. static createFromRange( range ) {
  433. return new this( range.start, range.end );
  434. }
  435. }