8
0

range.js 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468
  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.js';
  9. /**
  10. * Range class. Range is iterable.
  11. *
  12. * @class treeModel.Range
  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 treeModel.Position} instances basing on passed values.
  18. *
  19. * @param {treeModel.Position} start Start position.
  20. * @param {treeModel.Position} end End position.
  21. * @constructor
  22. */
  23. constructor( start, end ) {
  24. /**
  25. * Start position.
  26. *
  27. * @property {treeModel.Position}
  28. */
  29. this.start = Position.createFromPosition( start );
  30. /**
  31. * End position.
  32. *
  33. * @property {treeModel.Position}
  34. */
  35. this.end = Position.createFromPosition( end );
  36. }
  37. /**
  38. * Returns whether the range is collapsed, that is it start and end positions are equal.
  39. *
  40. * @property {Boolean}
  41. */
  42. get isCollapsed() {
  43. return this.start.isEqual( this.end );
  44. }
  45. /**
  46. * Returns whether this range is flat, that is if start position and end position are in the same parent.
  47. *
  48. * @returns {Boolean}
  49. */
  50. get isFlat() {
  51. return this.start.parent === this.end.parent;
  52. }
  53. /**
  54. * Range root element. Equals to the root of start position (which should be same as root of end position).
  55. *
  56. * @property {treeModel.RootElement}
  57. */
  58. get root() {
  59. return this.start.root;
  60. }
  61. /**
  62. * Range iterator.
  63. *
  64. * @see treeModel.TreeWalker
  65. */
  66. [ Symbol.iterator ]() {
  67. return new TreeWalker( { boundaries: this } );
  68. }
  69. /**
  70. * Checks whether this contains given {@link treeModel.Position position}.
  71. *
  72. * @param {treeModel.Position} position Position to check.
  73. * @returns {Boolean} True if given {@link treeModel.Position position} is contained.
  74. */
  75. containsPosition( position ) {
  76. return position.isAfter( this.start ) && position.isBefore( this.end );
  77. }
  78. /**
  79. * Checks whether this range contains given {@link treeModel.Range range}.
  80. *
  81. * @param {treeModel.Range} otherRange Range to check.
  82. * @returns {Boolean} True if given {@link treeModel.Range range} boundaries are contained by this range.
  83. */
  84. containsRange( otherRange ) {
  85. return this.containsPosition( otherRange.start ) && this.containsPosition( otherRange.end );
  86. }
  87. /**
  88. * Gets a part of this {@link treeModel.Range range} which is not a part of given {@link treeModel.Range range}. Returned
  89. * array contains zero, one or two {@link treeModel.Range ranges}.
  90. *
  91. * Examples:
  92. *
  93. * let range = new Range( new Position( root, [ 2, 7 ] ), new Position( root, [ 4, 0, 1 ] ) );
  94. * let otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 5 ] ) );
  95. * let transformed = range.getDifference( otherRange );
  96. * // transformed array has no ranges because `otherRange` contains `range`
  97. *
  98. * otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 3 ] ) );
  99. * transformed = range.getDifference( otherRange );
  100. * // transformed array has one range: from [ 3 ] to [ 4, 0, 1 ]
  101. *
  102. * otherRange = new Range( new Position( root, [ 3 ] ), new Position( root, [ 4 ] ) );
  103. * transformed = range.getDifference( otherRange );
  104. * // transformed array has two ranges: from [ 2, 7 ] to [ 3 ] and from [ 4 ] to [ 4, 0, 1 ]
  105. *
  106. * @param {treeModel.Range} otherRange Range to differentiate against.
  107. * @returns {Array.<treeModel.Range>} The difference between ranges.
  108. */
  109. getDifference( otherRange ) {
  110. const ranges = [];
  111. if ( this.isIntersecting( otherRange ) ) {
  112. // Ranges intersect.
  113. if ( this.containsPosition( otherRange.start ) ) {
  114. // Given range start is inside this range. This means that we have to
  115. // add shrunken range - from the start to the middle of this range.
  116. ranges.push( new Range( this.start, otherRange.start ) );
  117. }
  118. if ( this.containsPosition( otherRange.end ) ) {
  119. // Given range end is inside this range. This means that we have to
  120. // add shrunken range - from the middle of this range to the end.
  121. ranges.push( new Range( otherRange.end, this.end ) );
  122. }
  123. } else {
  124. // Ranges do not intersect, return the original range.
  125. ranges.push( Range.createFromRange( this ) );
  126. }
  127. return ranges;
  128. }
  129. /**
  130. * Returns an intersection of this {@link treeModel.Range range} and given {@link treeModel.Range range}. Intersection
  131. * is a common part of both of those ranges. If ranges has no common part, returns `null`.
  132. *
  133. * Examples:
  134. *
  135. * let range = new Range( new Position( root, [ 2, 7 ] ), new Position( root, [ 4, 0, 1 ] ) );
  136. * let otherRange = new Range( new Position( root, [ 1 ] ), new Position( root, [ 2 ] ) );
  137. * let transformed = range.getIntersection( otherRange ); // null - ranges have no common part
  138. *
  139. * otherRange = new Range( new Position( root, [ 3 ] ), new Position( root, [ 5 ] ) );
  140. * transformed = range.getIntersection( otherRange ); // range from [ 3 ] to [ 4, 0, 1 ]
  141. *
  142. * @param {treeModel.Range} otherRange Range to check for intersection.
  143. * @returns {treeModel.Range|null} A common part of given ranges or null if ranges have no common part.
  144. */
  145. getIntersection( otherRange ) {
  146. if ( this.isIntersecting( otherRange ) ) {
  147. // Ranges intersect, so a common range will be returned.
  148. // At most, it will be same as this range.
  149. let commonRangeStart = this.start;
  150. let commonRangeEnd = this.end;
  151. if ( this.containsPosition( otherRange.start ) ) {
  152. // Given range start is inside this range. This means thaNt we have to
  153. // shrink common range to the given range start.
  154. commonRangeStart = otherRange.start;
  155. }
  156. if ( this.containsPosition( otherRange.end ) ) {
  157. // Given range end is inside this range. This means that we have to
  158. // shrink common range to the given range end.
  159. commonRangeEnd = otherRange.end;
  160. }
  161. return new Range( commonRangeStart, commonRangeEnd );
  162. }
  163. // Ranges do not intersect, so they do not have common part.
  164. return null;
  165. }
  166. /**
  167. * Computes and returns the smallest set of {@link #isFlat flat} ranges, that covers this range in whole.
  168. * Assuming that tree model model structure is ("[" and "]" are range boundaries):
  169. *
  170. * root root
  171. * |- element DIV DIV P2 P3 DIV
  172. * | |- element H H P1 f o o b a r H P4
  173. * | | |- "fir[st" fir[st lorem se]cond ipsum
  174. * | |- element P1
  175. * | | |- "lorem" ||
  176. * |- element P2 ||
  177. * | |- "foo" VV
  178. * |- element P3
  179. * | |- "bar" root
  180. * |- element DIV DIV [P2 P3] DIV
  181. * | |- element H H [P1] f o o b a r H P4
  182. * | | |- "se]cond" fir[st] lorem [se]cond ipsum
  183. * | |- element P4
  184. * | | |- "ipsum"
  185. *
  186. * As it can be seen, letters contained in the range are stloremfoobarse, spread across different parents.
  187. * We are looking for minimal set of {@link #isFlat flat} ranges that contains the same nodes.
  188. *
  189. * Minimal flat ranges for above range `( [ 0, 0, 3 ], [ 3, 0, 2 ] )` will be:
  190. *
  191. * ( [ 0, 0, 3 ], [ 0, 0, 5 ] ) = "st"
  192. * ( [ 0, 1 ], [ 0, 2 ] ) = element P1 ("lorem")
  193. * ( [ 1 ], [ 3 ] ) = element P2, element P3 ("foobar")
  194. * ( [ 3, 0, 0 ], [ 3, 0, 2 ] ) = "se"
  195. *
  196. * **Note:** this method is not returning flat ranges that contain no nodes. It may also happen that not-collapsed
  197. * range will return an empty array of flat ranges.
  198. *
  199. * @returns {Array.<treeModel.Range>} Array of flat ranges.
  200. */
  201. getMinimalFlatRanges() {
  202. let ranges = [];
  203. // We find on which tree-level start and end have the lowest common ancestor
  204. let cmp = utils.compareArrays( this.start.path, this.end.path );
  205. // If comparison returned string it means that arrays are same.
  206. let diffAt = ( typeof cmp == 'string' ) ? Math.min( this.start.path.length, this.end.path.length ) : cmp;
  207. let pos = Position.createFromPosition( this.start );
  208. let posParent = pos.parent;
  209. // Go up.
  210. while ( pos.path.length > diffAt + 1 ) {
  211. let howMany = posParent.getChildCount() - pos.offset;
  212. if ( howMany !== 0 ) {
  213. ranges.push( new Range( pos, pos.getShiftedBy( howMany ) ) );
  214. }
  215. pos.path = pos.path.slice( 0, -1 );
  216. pos.offset++;
  217. posParent = posParent.parent;
  218. }
  219. // Go down.
  220. while ( pos.path.length <= this.end.path.length ) {
  221. let offset = this.end.path[ pos.path.length - 1 ];
  222. let howMany = offset - pos.offset;
  223. if ( howMany !== 0 ) {
  224. ranges.push( new Range( pos, pos.getShiftedBy( howMany ) ) );
  225. }
  226. pos.offset = offset;
  227. pos.path.push( 0 );
  228. }
  229. return ranges;
  230. }
  231. /**
  232. * Returns an iterator that iterates over all {@link treeModel.Node nodes} that are in this range and returns them.
  233. * A node is in the range when it is after a {@link treeModel.Position position} contained in this range.
  234. * In other words, this iterates over all text characters that are inside the range and all the {@link treeModel.Element}s
  235. * we enter into when iterating over this range.
  236. *
  237. * **Note:** this method will not return a parent node of start position. This is in contrary to {@link treeModel.TreeWalker}
  238. * which will return that node with `'ELEMENT_END'` type. This method also returns each {@link treeModel.Element} once,
  239. * while simply used {@link treeModel.TreeWalker} might return it twice: for `'ELEMENT_START'` and `'ELEMENT_END'`.
  240. *
  241. * @see {treeModel.TreeWalker}
  242. * @param {Boolean} [mergeCharacters] Flag indicating whether all consecutive characters with the same attributes
  243. * should be returned as one {@link treeModel.TextFragment} (`true`) or one by one as multiple {@link treeModel.CharacterProxy}
  244. * (`false`) objects. Defaults to `false`.
  245. * @returns {Iterable.<treeModel.Node|treeModel.TextFragment>}
  246. */
  247. *getAllNodes( mergeCharacters ) {
  248. let it = new TreeWalker( { boundaries: this, mergeCharacters: mergeCharacters } );
  249. let step;
  250. do {
  251. step = it.next();
  252. if ( step.value && step.value.type != 'ELEMENT_END' ) {
  253. yield step.value.item;
  254. }
  255. } while ( !step.done );
  256. }
  257. /**
  258. * Returns an iterator that iterates over all {@link treeModel.Position positions} that are boundaries or
  259. * contained in this range.
  260. *
  261. * @param {Boolean} [mergeCharacters] Flag indicating whether all consecutive characters with the same attributes
  262. * should be returned as one {@link treeModel.TextFragment} (`true`) or one by one as multiple {@link treeModel.CharacterProxy}
  263. * (`false`) objects. Defaults to `false`.
  264. * @returns {Iterable.<treeModel.Position>}
  265. */
  266. *getPositions( mergeCharacters ) {
  267. let it = new TreeWalker( { boundaries: this, mergeCharacters: mergeCharacters } );
  268. do {
  269. yield it.position;
  270. } while ( !it.next().done );
  271. }
  272. /**
  273. * Returns an iterator that iterates over all {@link treeModel.Node nodes} that are top-level nodes in this range
  274. * and returns them. A node is a top-level node when it is in the range but it's parent is not. In other words,
  275. * this function splits the range into separate sub-trees and iterates over their roots.
  276. *
  277. * @param {Boolean} [mergeCharacters] Flag indicating whether all consecutive characters with the same attributes
  278. * should be returned as one {@link treeModel.TextFragment} (`true`) or one by one as multiple {@link treeModel.CharacterProxy}
  279. * (`false`) objects. Defaults to `false`.
  280. * @returns {Iterable.<treeModel.Node|treeModel.TextFragment>}
  281. */
  282. *getTopLevelNodes( mergeCharacters ) {
  283. let flatRanges = this.getMinimalFlatRanges();
  284. for ( let range of flatRanges ) {
  285. // This loop could be much simpler as we could just iterate over siblings of node after the first
  286. // position of each range. But then we would have to re-implement character merging strategy here.
  287. let it = new TreeWalker( { boundaries: range, mergeCharacters: mergeCharacters } );
  288. let step;
  289. // We will only return nodes that are on same level as node after the range start. To do this,
  290. // we keep "depth" counter.
  291. let depth = 0;
  292. do {
  293. step = it.next();
  294. if ( step.value ) {
  295. if ( step.value.type == 'ELEMENT_START' ) {
  296. depth++;
  297. } else if ( step.value.type == 'ELEMENT_END' ) {
  298. depth--;
  299. }
  300. if ( depth === 0 ) {
  301. yield step.value.item;
  302. }
  303. }
  304. } while ( !step.done );
  305. }
  306. }
  307. /**
  308. * Returns an array containing one or two {treeModel.Range ranges} that are a result of transforming this
  309. * {@link treeModel.Range range} by inserting `howMany` nodes at `insertPosition`. Two {@link treeModel.Range ranges} are
  310. * returned if the insertion was inside this {@link treeModel.Range range}.
  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, [ 3, 2 ] ), 4 );
  319. * // transformed array has two ranges: from [ 2, 7 ] to [ 3, 2 ] and from [ 3, 6 ] to [ 4, 0, 1 ]
  320. *
  321. * transformed = range.getTransformedByInsertion( new Position( root, [ 3, 2 ] ), 4, true );
  322. * // transformed array has one range which is equal to `range`. This is because of spreadOnlyOnSameLevel flag.
  323. *
  324. * @param {treeModel.Position} insertPosition Position where nodes are inserted.
  325. * @param {Number} howMany How many nodes are inserted.
  326. * @param {Boolean} spreadOnlyOnSameLevel Flag indicating whether this {treeModel.Range range} should be spread
  327. * if insertion was inside a node from this {treeModel.Range range} but not in the range itself.
  328. * @returns {Array.<treeModel.Range>} Result of the transformation.
  329. */
  330. getTransformedByInsertion( insertPosition, howMany, spreadOnlyOnSameLevel ) {
  331. // Flag indicating whether this whole range and given insertPosition is on the same tree level.
  332. const areOnSameLevel = utils.compareArrays( this.start.getParentPath(), this.end.getParentPath() ) == 'SAME' &&
  333. utils.compareArrays( this.start.getParentPath(), insertPosition.getParentPath() ) == 'SAME';
  334. if ( this.containsPosition( insertPosition ) && ( !spreadOnlyOnSameLevel || areOnSameLevel ) ) {
  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, true )
  343. )
  344. ];
  345. } else {
  346. // If insertion is not inside the range, simply transform range boundaries (positions) by the insertion.
  347. // Both, one or none of them might be affected by the insertion.
  348. const range = Range.createFromRange( this );
  349. range.start = range.start.getTransformedByInsertion( insertPosition, howMany, true );
  350. range.end = range.end.getTransformedByInsertion( insertPosition, howMany, false );
  351. return [ range ];
  352. }
  353. }
  354. /**
  355. * Two ranges equal if their start and end positions equal.
  356. *
  357. * @param {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 {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 {treeModel.Element} element Element which is a parent for the range.
  376. * @returns {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 {treeModel.Position} position Beginning of the range.
  385. * @param {Number} shift How long the range should be.
  386. * @returns {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 {treeModel.Element} startElement Start position parent element.
  395. * @param {Number} startOffset Start position offset.
  396. * @param {treeModel.Element} endElement End position parent element.
  397. * @param {Number} endOffset End position offset.
  398. * @returns {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 {treeModel.Range} range Range to clone.
  410. * @returns {treeModel.Range}
  411. */
  412. static createFromRange( range ) {
  413. return new this( range.start, range.end );
  414. }
  415. }