8
0

range.js 21 KB

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