8
0

range.js 18 KB

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