range.js 21 KB

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