range.js 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563
  1. /**
  2. * @license Copyright (c) 2003-2016, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. import Position from './position.js';
  6. import TreeWalker from './treewalker.js';
  7. import compareArrays from '../../utils/comparearrays.js';
  8. /**
  9. * Range class. Range is iterable.
  10. *
  11. * @memberOf engine.model
  12. */
  13. export default class Range {
  14. /**
  15. * Creates a range spanning from `start` position to `end` position.
  16. *
  17. * **Note:** Constructor creates it's own {@link engine.model.Position Position} instances basing on passed values.
  18. *
  19. * @param {engine.model.Position} start Start position.
  20. * @param {engine.model.Position} end End position.
  21. */
  22. constructor( start, end ) {
  23. /**
  24. * Start position.
  25. *
  26. * @readonly
  27. * @member {engine.model.Position} engine.model.Range#start
  28. */
  29. this.start = Position.createFromPosition( start );
  30. /**
  31. * End position.
  32. *
  33. * @readonly
  34. * @member {engine.model.Position} engine.model.Range#end
  35. */
  36. this.end = Position.createFromPosition( end );
  37. }
  38. /**
  39. * Returns an iterator that iterates over all {@link engine.model.Item items} that are in this range and returns
  40. * them together with additional information like length or {@link engine.model.Position positions},
  41. * grouped as {@link engine.model.TreeWalkerValue}. It iterates over all {@link engine.model.TextProxy text contents}
  42. * that are inside the range and all the {@link engine.model.Element}s that are entered into when iterating over this range.
  43. *
  44. * This iterator uses {@link engine.model.TreeWalker} with `boundaries` set to this range and `ignoreElementEnd` option
  45. * set to `true`.
  46. *
  47. * @returns {Iterable.<engine.model.TreeWalkerValue>}
  48. */
  49. *[ Symbol.iterator ]() {
  50. yield* new TreeWalker( { boundaries: this, ignoreElementEnd: true } );
  51. }
  52. /**
  53. * Returns whether the range is collapsed, that is if {@link engine.model.Range#start start} and
  54. * {@link engine.model.Range#end end} positions are equal.
  55. *
  56. * @type {Boolean}
  57. */
  58. get isCollapsed() {
  59. return this.start.isEqual( this.end );
  60. }
  61. /**
  62. * Returns whether this range is flat, that is if {@link engine.model.Range#start start} position and
  63. * {@link engine.model.Range#end end} position are in the same {@link engine.model.Position#parent parent}.
  64. *
  65. * @type {Boolean}
  66. */
  67. get isFlat() {
  68. return this.start.parent === this.end.parent;
  69. }
  70. /**
  71. * Returns whether this range has no nodes in it, that is if {@link engine.model.Range#start start} position and
  72. * {@link engine.model.Range#end end} position are {@link engine.model.Position#isTouching touching}.
  73. *
  74. * **Note:** A range may be empty, but not {@link engine.model.Range#isCollapsed collapsed}.
  75. *
  76. * @type {Boolean}
  77. */
  78. get isEmpty() {
  79. return this.start.isTouching( this.end );
  80. }
  81. /**
  82. * Range root element.
  83. *
  84. * @type {engine.model.Element|engine.model.DocumentFragment}
  85. */
  86. get root() {
  87. return this.start.root;
  88. }
  89. /**
  90. * Checks whether this range contains given {@link engine.model.Position position}.
  91. *
  92. * @param {engine.model.Position} position Position to check.
  93. * @returns {Boolean} `true` if given {@link engine.model.Position position} is contained in this range, `false` otherwise.
  94. */
  95. containsPosition( position ) {
  96. return position.isAfter( this.start ) && position.isBefore( this.end );
  97. }
  98. /**
  99. * Checks whether this range contains given {@link engine.model.Range range}.
  100. *
  101. * @param {engine.model.Range} otherRange Range to check.
  102. * @returns {Boolean} `true` if given {@link engine.model.Range range} boundaries are contained by this range, `false` otherwise.
  103. */
  104. containsRange( otherRange ) {
  105. return this.containsPosition( otherRange.start ) && this.containsPosition( otherRange.end );
  106. }
  107. /**
  108. * Two ranges are equal if their {@link engine.model.Range#start start} and
  109. * {@link engine.model.Range#end end} positions are equal.
  110. *
  111. * @param {engine.model.Range} otherRange Range to compare with.
  112. * @returns {Boolean} `true` if ranges are equal, `false` otherwise.
  113. */
  114. isEqual( otherRange ) {
  115. return this.start.isEqual( otherRange.start ) && this.end.isEqual( otherRange.end );
  116. }
  117. /**
  118. * Checks and returns whether this range intersects with given range.
  119. *
  120. * @param {engine.model.Range} otherRange Range to compare with.
  121. * @returns {Boolean} `true` if ranges intersect, `false` otherwise.
  122. */
  123. isIntersecting( otherRange ) {
  124. return this.start.isBefore( otherRange.end ) && this.end.isAfter( otherRange.start );
  125. }
  126. /**
  127. * Computes which part(s) of this {@link engine.model.Range range} is not a part of given {@link engine.model.Range range}.
  128. * Returned array contains zero, one or two {@link engine.model.Range ranges}.
  129. *
  130. * Examples:
  131. *
  132. * let range = new Range( new Position( root, [ 2, 7 ] ), new Position( root, [ 4, 0, 1 ] ) );
  133. * let otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 5 ] ) );
  134. * let transformed = range.getDifference( otherRange );
  135. * // transformed array has no ranges because `otherRange` contains `range`
  136. *
  137. * otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 3 ] ) );
  138. * transformed = range.getDifference( otherRange );
  139. * // transformed array has one range: from [ 3 ] to [ 4, 0, 1 ]
  140. *
  141. * otherRange = new Range( new Position( root, [ 3 ] ), new Position( root, [ 4 ] ) );
  142. * transformed = range.getDifference( otherRange );
  143. * // transformed array has two ranges: from [ 2, 7 ] to [ 3 ] and from [ 4 ] to [ 4, 0, 1 ]
  144. *
  145. * @param {engine.model.Range} otherRange Range to differentiate against.
  146. * @returns {Array.<engine.model.Range>} The difference between ranges.
  147. */
  148. getDifference( otherRange ) {
  149. const ranges = [];
  150. if ( this.isIntersecting( otherRange ) ) {
  151. // Ranges intersect.
  152. if ( this.containsPosition( otherRange.start ) ) {
  153. // Given range start is inside this range. This means that we have to
  154. // add shrunken range - from the start to the middle of this range.
  155. ranges.push( new Range( this.start, otherRange.start ) );
  156. }
  157. if ( this.containsPosition( otherRange.end ) ) {
  158. // Given range end is inside this range. This means that we have to
  159. // add shrunken range - from the middle of this range to the end.
  160. ranges.push( new Range( otherRange.end, this.end ) );
  161. }
  162. } else {
  163. // Ranges do not intersect, return the original range.
  164. ranges.push( Range.createFromRange( this ) );
  165. }
  166. return ranges;
  167. }
  168. /**
  169. * Returns an intersection of this {@link engine.model.Range range} and given {@link engine.model.Range range}.
  170. * Intersection is a common part of both of those ranges. If ranges has no common part, returns `null`.
  171. *
  172. * Examples:
  173. *
  174. * let range = new Range( new Position( root, [ 2, 7 ] ), new Position( root, [ 4, 0, 1 ] ) );
  175. * let otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 2 ] ) );
  176. * let transformed = range.getIntersection( otherRange ); // null - ranges have no common part
  177. *
  178. * otherRange = new Range( new Position( root, [ 3 ] ), new Position( root, [ 5 ] ) );
  179. * transformed = range.getIntersection( otherRange ); // range from [ 3 ] to [ 4, 0, 1 ]
  180. *
  181. * @param {engine.model.Range} otherRange Range to check for intersection.
  182. * @returns {engine.model.Range|null} A common part of given ranges or `null` if ranges have no common part.
  183. */
  184. getIntersection( otherRange ) {
  185. if ( this.isIntersecting( otherRange ) ) {
  186. // Ranges intersect, so a common range will be returned.
  187. // At most, it will be same as this range.
  188. let commonRangeStart = this.start;
  189. let commonRangeEnd = this.end;
  190. if ( this.containsPosition( otherRange.start ) ) {
  191. // Given range start is inside this range. This means thaNt we have to
  192. // shrink common range to the given range start.
  193. commonRangeStart = otherRange.start;
  194. }
  195. if ( this.containsPosition( otherRange.end ) ) {
  196. // Given range end is inside this range. This means that we have to
  197. // shrink common range to the given range end.
  198. commonRangeEnd = otherRange.end;
  199. }
  200. return new Range( commonRangeStart, commonRangeEnd );
  201. }
  202. // Ranges do not intersect, so they do not have common part.
  203. return null;
  204. }
  205. /**
  206. * Computes and returns the smallest set of {@link engine.model.Range#isFlat flat} ranges, that covers this range in whole.
  207. *
  208. * See an example of model structure (`[` and `]` are range boundaries):
  209. *
  210. * root root
  211. * |- element DIV DIV P2 P3 DIV
  212. * | |- element H H P1 f o o b a r H P4
  213. * | | |- "fir[st" fir[st lorem se]cond ipsum
  214. * | |- element P1
  215. * | | |- "lorem" ||
  216. * |- element P2 ||
  217. * | |- "foo" VV
  218. * |- element P3
  219. * | |- "bar" root
  220. * |- element DIV DIV [P2 P3] DIV
  221. * | |- element H H [P1] f o o b a r H P4
  222. * | | |- "se]cond" fir[st] lorem [se]cond ipsum
  223. * | |- element P4
  224. * | | |- "ipsum"
  225. *
  226. * As it can be seen, letters contained in the range are: `stloremfoobarse`, spread across different parents.
  227. * We are looking for minimal set of flat ranges that contains the same nodes.
  228. *
  229. * Minimal flat ranges for above range `( [ 0, 0, 3 ], [ 3, 0, 2 ] )` will be:
  230. *
  231. * ( [ 0, 0, 3 ], [ 0, 0, 5 ] ) = "st"
  232. * ( [ 0, 1 ], [ 0, 2 ] ) = element P1 ("lorem")
  233. * ( [ 1 ], [ 3 ] ) = element P2, element P3 ("foobar")
  234. * ( [ 3, 0, 0 ], [ 3, 0, 2 ] ) = "se"
  235. *
  236. * **Note:** if an {@link engine.model.Element element} is not contained wholly in this range, it won't be returned
  237. * in any of returned flat ranges. See in an example, how `H` elements at the beginning and at the end of the range
  238. * were omitted. Only it's parts that were wholly in the range were returned.
  239. *
  240. * **Note:** this method is not returning flat ranges that contain no nodes.
  241. *
  242. * @returns {Array.<engine.model.Range>} Array of flat ranges covering this range.
  243. */
  244. getMinimalFlatRanges() {
  245. let ranges = [];
  246. // We find on which tree-level start and end have the lowest common ancestor
  247. let cmp = compareArrays( this.start.path, this.end.path );
  248. // If comparison returned string it means that arrays are same.
  249. let diffAt = ( typeof cmp == 'string' ) ? Math.min( this.start.path.length, this.end.path.length ) : cmp;
  250. let pos = Position.createFromPosition( this.start );
  251. let posParent = pos.parent;
  252. // Go up.
  253. while ( pos.path.length > diffAt + 1 ) {
  254. let howMany = posParent.maxOffset - pos.offset;
  255. if ( howMany !== 0 ) {
  256. ranges.push( new Range( pos, pos.getShiftedBy( howMany ) ) );
  257. }
  258. pos.path = pos.path.slice( 0, -1 );
  259. pos.offset++;
  260. posParent = posParent.parent;
  261. }
  262. // Go down.
  263. while ( pos.path.length <= this.end.path.length ) {
  264. let offset = this.end.path[ pos.path.length - 1 ];
  265. let howMany = offset - pos.offset;
  266. if ( howMany !== 0 ) {
  267. ranges.push( new Range( pos, pos.getShiftedBy( howMany ) ) );
  268. }
  269. pos.offset = offset;
  270. pos.path.push( 0 );
  271. }
  272. return ranges;
  273. }
  274. /**
  275. * Creates a {@link engine.model.TreeWalker TreeWalker} instance with this range as a boundary.
  276. *
  277. * @param {Object} options Object with configuration options. See {@link engine.model.TreeWalker}.
  278. * @param {engine.model.Position} [options.startPosition]
  279. * @param {Boolean} [options.singleCharacters=false]
  280. * @param {Boolean} [options.shallow=false]
  281. * @param {Boolean} [options.ignoreElementEnd=false]
  282. */
  283. getWalker( options = {} ) {
  284. options.boundaries = this;
  285. return new TreeWalker( options );
  286. }
  287. /**
  288. * Returns an iterator that iterates over all {@link engine.model.Item items} that are in this range and returns
  289. * them.
  290. *
  291. * This method uses {@link engine.model.TreeWalker} with `boundaries` set to this range and `ignoreElementEnd` option
  292. * set to `true`. However it returns only {@link engine.model.Item model items}, not {@link engine.model.TreeWalkerValue}.
  293. *
  294. * You may specify additional options for the tree walker. See {@link engine.model.TreeWalker} for
  295. * a full list of available options.
  296. *
  297. * @param {Object} options Object with configuration options. See {@link engine.model.TreeWalker}.
  298. * @returns {Iterable.<engine.model.Item>}
  299. */
  300. *getItems( options = {} ) {
  301. options.boundaries = this;
  302. options.ignoreElementEnd = true;
  303. const treeWalker = new TreeWalker( options );
  304. for ( let value of treeWalker ) {
  305. yield value.item;
  306. }
  307. }
  308. /**
  309. * Returns an iterator that iterates over all {@link engine.model.Position positions} that are boundaries or
  310. * contained in this range.
  311. *
  312. * This method uses {@link engine.model.TreeWalker} with `boundaries` set to this range. However it returns only
  313. * {@link engine.model.Position positions}, not {@link engine.model.TreeWalkerValue}.
  314. *
  315. * You may specify additional options for the tree walker. See {@link engine.model.TreeWalker} for
  316. * a full list of available options.
  317. *
  318. * @param {Object} options Object with configuration options. See {@link engine.model.TreeWalker}.
  319. * @returns {Iterable.<engine.model.Position>}
  320. */
  321. *getPositions( options = {} ) {
  322. options.boundaries = this;
  323. const treeWalker = new TreeWalker( options );
  324. yield treeWalker.position;
  325. for ( let value of treeWalker ) {
  326. yield value.nextPosition;
  327. }
  328. }
  329. /**
  330. * Returns an array containing one or two {@link engine.model.Range ranges} that are a result of transforming this
  331. * {@link engine.model.Range range} by inserting `howMany` nodes at `insertPosition`. Two {@link engine.model.Range ranges} are
  332. * returned if the insertion was inside this {@link engine.model.Range range} and `spread` is set to `true`.
  333. *
  334. * Examples:
  335. *
  336. * let range = new Range( new Position( root, [ 2, 7 ] ), new Position( root, [ 4, 0, 1 ] ) );
  337. * let transformed = range._getTransformedByInsertion( new Position( root, [ 1 ] ), 2 );
  338. * // transformed array has one range from [ 4, 7 ] to [ 6, 0, 1 ]
  339. *
  340. * transformed = range._getTransformedByInsertion( new Position( root, [ 4, 0, 0 ] ), 4 );
  341. * // transformed array has one range from [ 2, 7 ] to [ 4, 0, 5 ]
  342. *
  343. * transformed = range._getTransformedByInsertion( new Position( root, [ 3, 2 ] ), 4 );
  344. * // transformed array has one range, which is equal to original range
  345. *
  346. * transformed = range._getTransformedByInsertion( new Position( root, [ 3, 2 ] ), 4, true );
  347. * // transformed array has two ranges: from [ 2, 7 ] to [ 3, 2 ] and from [ 3, 6 ] to [ 4, 0, 1 ]
  348. *
  349. * transformed = range._getTransformedByInsertion( new Position( root, [ 4, 0, 1 ] ), 4, false, false );
  350. * // transformed array has one range which is equal to original range because insertion is after the range boundary
  351. *
  352. * transformed = range._getTransformedByInsertion( new Position( root, [ 4, 0, 1 ] ), 4, false, true );
  353. * // transformed array has one range: from [ 2, 7 ] to [ 4, 0, 5 ] because range was expanded
  354. *
  355. * @protected
  356. * @param {engine.model.Position} insertPosition Position where nodes are inserted.
  357. * @param {Number} howMany How many nodes are inserted.
  358. * @param {Boolean} [spread] Flag indicating whether this {engine.model.Range range} should be spread if insertion
  359. * was inside the range. Defaults to `false`.
  360. * @param {Boolean} [isSticky] Flag indicating whether insertion should expand a range if it is in a place of
  361. * range boundary. Defaults to `false`.
  362. * @returns {Array.<engine.model.Range>} Result of the transformation.
  363. */
  364. _getTransformedByInsertion( insertPosition, howMany, spread = false, isSticky = false ) {
  365. if ( spread && this.containsPosition( insertPosition ) ) {
  366. // Range has to be spread. The first part is from original start to the spread point.
  367. // The other part is from spread point to the original end, but transformed by
  368. // insertion to reflect insertion changes.
  369. return [
  370. new Range( this.start, insertPosition ),
  371. new Range(
  372. insertPosition._getTransformedByInsertion( insertPosition, howMany, true ),
  373. this.end._getTransformedByInsertion( insertPosition, howMany, this.isCollapsed )
  374. )
  375. ];
  376. } else {
  377. const range = Range.createFromRange( this );
  378. let insertBeforeStart = range.isCollapsed ? isSticky : !isSticky;
  379. let insertBeforeEnd = isSticky;
  380. range.start = range.start._getTransformedByInsertion( insertPosition, howMany, insertBeforeStart );
  381. range.end = range.end._getTransformedByInsertion( insertPosition, howMany, insertBeforeEnd );
  382. return [ range ];
  383. }
  384. }
  385. /**
  386. * Returns an array containing {@link engine.model.Range ranges} that are a result of transforming this
  387. * {@link engine.model.Range range} by moving `howMany` nodes from `sourcePosition` to `targetPosition`.
  388. *
  389. * @protected
  390. * @param {engine.model.Position} sourcePosition Position from which nodes are moved.
  391. * @param {engine.model.Position} targetPosition Position to where nodes are moved.
  392. * @param {Number} howMany How many nodes are moved.
  393. * @param {Boolean} [spread] Flag indicating whether this {engine.model.Range range} should be spread if insertion
  394. * was inside the range. Defaults to `false`.
  395. * @returns {Array.<engine.model.Range>} Result of the transformation.
  396. */
  397. _getTransformedByMove( sourcePosition, targetPosition, howMany, spread, isSticky = false ) {
  398. let result;
  399. const moveRange = new Range( sourcePosition, sourcePosition.getShiftedBy( howMany ) );
  400. const differenceSet = this.getDifference( moveRange );
  401. let difference;
  402. if ( differenceSet.length == 1 ) {
  403. difference = new Range(
  404. differenceSet[ 0 ].start._getTransformedByDeletion( sourcePosition, howMany ),
  405. differenceSet[ 0 ].end._getTransformedByDeletion( sourcePosition, howMany )
  406. );
  407. } else if ( differenceSet.length == 2 ) {
  408. // This means that ranges were moved from the inside of this range.
  409. // So we can operate on this range positions and we don't have to transform starting position.
  410. difference = new Range(
  411. this.start,
  412. this.end._getTransformedByDeletion( sourcePosition, howMany )
  413. );
  414. } else {
  415. // 0.
  416. difference = null;
  417. }
  418. const insertPosition = targetPosition._getTransformedByDeletion( sourcePosition, howMany );
  419. if ( difference ) {
  420. result = difference._getTransformedByInsertion( insertPosition, howMany, spread, isSticky );
  421. } else {
  422. result = [];
  423. }
  424. const common = this.getIntersection( moveRange );
  425. // Add common part of the range only if there is any and only if it is not
  426. // already included in `difference` part.
  427. if ( common && ( spread || difference === null || !difference.containsPosition( insertPosition ) ) ) {
  428. result.push( new Range(
  429. common.start._getCombined( moveRange.start, insertPosition ),
  430. common.end._getCombined( moveRange.start, insertPosition )
  431. ) );
  432. }
  433. return result;
  434. }
  435. /**
  436. * Creates a range inside an {@link engine.model.Element element} which starts before the first child of
  437. * that element and ends after the last child of that element.
  438. *
  439. * @param {engine.model.Element} element Element which is a parent for the range.
  440. * @returns {engine.model.Range}
  441. */
  442. static createFromElement( element ) {
  443. return this.createFromParentsAndOffsets( element, 0, element, element.maxOffset );
  444. }
  445. /**
  446. * Creates a range on given {@link engine.model.Element element} only. The range starts directly before that element
  447. * and ends before the first child of that element.
  448. *
  449. * @param {engine.model.Element} element Element on which range should be created.
  450. * @returns {engine.model.Range}
  451. */
  452. static createOnElement( element ) {
  453. return this.createFromParentsAndOffsets( element.parent, element.startOffset, element, 0 );
  454. }
  455. /**
  456. * Creates a new range, spreading from specified {@link engine.model.Position position} to a position moved by
  457. * given `shift`. If `shift` is a negative value, shifted position is treated as the beginning of the range.
  458. *
  459. * @param {engine.model.Position} position Beginning of the range.
  460. * @param {Number} shift How long the range should be.
  461. * @returns {engine.model.Range}
  462. */
  463. static createFromPositionAndShift( position, shift ) {
  464. const start = position;
  465. const end = position.getShiftedBy( shift );
  466. return shift > 0 ? new this( start, end ) : new this( end, start );
  467. }
  468. /**
  469. * Creates a range from given parents and offsets.
  470. *
  471. * @param {engine.model.Element} startElement Start position parent element.
  472. * @param {Number} startOffset Start position offset.
  473. * @param {engine.model.Element} endElement End position parent element.
  474. * @param {Number} endOffset End position offset.
  475. * @returns {engine.model.Range}
  476. */
  477. static createFromParentsAndOffsets( startElement, startOffset, endElement, endOffset ) {
  478. return new this(
  479. Position.createFromParentAndOffset( startElement, startOffset ),
  480. Position.createFromParentAndOffset( endElement, endOffset )
  481. );
  482. }
  483. /**
  484. * Creates a new instance of `Range` which is equal to passed range.
  485. *
  486. * @param {engine.model.Range} range Range to clone.
  487. * @returns {engine.model.Range}
  488. */
  489. static createFromRange( range ) {
  490. return new this( range.start, range.end );
  491. }
  492. /**
  493. * Creates a `Range` instance from given plain object (i.e. parsed JSON string).
  494. *
  495. * @param {Object} json Plain object to be converted to `Range`.
  496. * @returns {engine.model.Element} `Range` instance created using given plain object.
  497. */
  498. static fromJSON( json, doc ) {
  499. return new this( Position.fromJSON( json.start, doc ), Position.fromJSON( json.end, doc ) );
  500. }
  501. }