8
0

range.js 18 KB

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