8
0

range.js 39 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047
  1. /**
  2. * @license Copyright (c) 2003-2020, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md or https://ckeditor.com/legal/ckeditor-oss-license
  4. */
  5. /**
  6. * @module engine/model/range
  7. */
  8. import Position from './position';
  9. import TreeWalker from './treewalker';
  10. import CKEditorError from '@ckeditor/ckeditor5-utils/src/ckeditorerror';
  11. import compareArrays from '@ckeditor/ckeditor5-utils/src/comparearrays';
  12. /**
  13. * Represents a range in the model tree.
  14. *
  15. * A range is defined by its {@link module:engine/model/range~Range#start} and {@link module:engine/model/range~Range#end}
  16. * positions.
  17. *
  18. * You can create range instances via its constructor or the `createRange*()` factory methods of
  19. * {@link module:engine/model/model~Model} and {@link module:engine/model/writer~Writer}.
  20. */
  21. export default class Range {
  22. /**
  23. * Creates a range spanning from `start` position to `end` position.
  24. *
  25. * @param {module:engine/model/position~Position} start Start position.
  26. * @param {module:engine/model/position~Position} [end] End position. If not set, range will be collapsed at `start` position.
  27. */
  28. constructor( start, end = null ) {
  29. /**
  30. * Start position.
  31. *
  32. * @readonly
  33. * @member {module:engine/model/position~Position}
  34. */
  35. this.start = Position._createAt( start );
  36. /**
  37. * End position.
  38. *
  39. * @readonly
  40. * @member {module:engine/model/position~Position}
  41. */
  42. this.end = end ? Position._createAt( end ) : Position._createAt( start );
  43. // If the range is collapsed, treat in a similar way as a position and set its boundaries stickiness to 'toNone'.
  44. // In other case, make the boundaries stick to the "inside" of the range.
  45. this.start.stickiness = this.isCollapsed ? 'toNone' : 'toNext';
  46. this.end.stickiness = this.isCollapsed ? 'toNone' : 'toPrevious';
  47. }
  48. /**
  49. * Iterable interface.
  50. *
  51. * Iterates over all {@link module:engine/model/item~Item items} that are in this range and returns
  52. * them together with additional information like length or {@link module:engine/model/position~Position positions},
  53. * grouped as {@link module:engine/model/treewalker~TreeWalkerValue}.
  54. * It iterates over all {@link module:engine/model/textproxy~TextProxy text contents} that are inside the range
  55. * and all the {@link module:engine/model/element~Element}s that are entered into when iterating over this range.
  56. *
  57. * This iterator uses {@link module:engine/model/treewalker~TreeWalker} with `boundaries` set to this range
  58. * and `ignoreElementEnd` option set to `true`.
  59. *
  60. * @returns {Iterable.<module:engine/model/treewalker~TreeWalkerValue>}
  61. */
  62. * [ Symbol.iterator ]() {
  63. yield* new TreeWalker( { boundaries: this, ignoreElementEnd: true } );
  64. }
  65. /**
  66. * Returns whether the range is collapsed, that is if {@link #start} and
  67. * {@link #end} positions are equal.
  68. *
  69. * @type {Boolean}
  70. */
  71. get isCollapsed() {
  72. return this.start.isEqual( this.end );
  73. }
  74. /**
  75. * Returns whether this range is flat, that is if {@link #start} position and
  76. * {@link #end} position are in the same {@link module:engine/model/position~Position#parent}.
  77. *
  78. * @type {Boolean}
  79. */
  80. get isFlat() {
  81. const startParentPath = this.start.getParentPath();
  82. const endParentPath = this.end.getParentPath();
  83. return compareArrays( startParentPath, endParentPath ) == 'same';
  84. }
  85. /**
  86. * Range root element.
  87. *
  88. * @type {module:engine/model/element~Element|module:engine/model/documentfragment~DocumentFragment}
  89. */
  90. get root() {
  91. return this.start.root;
  92. }
  93. /**
  94. * Checks whether this range contains given {@link module:engine/model/position~Position position}.
  95. *
  96. * @param {module:engine/model/position~Position} position Position to check.
  97. * @returns {Boolean} `true` if given {@link module:engine/model/position~Position position} is contained
  98. * in this range,`false` otherwise.
  99. */
  100. containsPosition( position ) {
  101. return position.isAfter( this.start ) && position.isBefore( this.end );
  102. }
  103. /**
  104. * Checks whether this range contains given {@link ~Range range}.
  105. *
  106. * @param {module:engine/model/range~Range} otherRange Range to check.
  107. * @param {Boolean} [loose=false] Whether the check is loose or strict. If the check is strict (`false`), compared range cannot
  108. * start or end at the same position as this range boundaries. If the check is loose (`true`), compared range can start, end or
  109. * even be equal to this range. Note that collapsed ranges are always compared in strict mode.
  110. * @returns {Boolean} `true` if given {@link ~Range range} boundaries are contained by this range, `false` otherwise.
  111. */
  112. containsRange( otherRange, loose = false ) {
  113. if ( otherRange.isCollapsed ) {
  114. loose = false;
  115. }
  116. const containsStart = this.containsPosition( otherRange.start ) || ( loose && this.start.isEqual( otherRange.start ) );
  117. const containsEnd = this.containsPosition( otherRange.end ) || ( loose && this.end.isEqual( otherRange.end ) );
  118. return containsStart && containsEnd;
  119. }
  120. /**
  121. * Checks whether given {@link module:engine/model/item~Item} is inside this range.
  122. *
  123. * @param {module:engine/model/item~Item} item Model item to check.
  124. */
  125. containsItem( item ) {
  126. const pos = Position._createBefore( item );
  127. return this.containsPosition( pos ) || this.start.isEqual( pos );
  128. }
  129. /**
  130. * Checks whether this object is of the given.
  131. *
  132. * range.is( 'range' ); // -> true
  133. * range.is( 'model:range' ); // -> true
  134. *
  135. * range.is( 'view:range' ); // -> false
  136. * range.is( 'documentSelection' ); // -> false
  137. *
  138. * {@link module:engine/model/node~Node#is Check the entire list of model objects} which implement the `is()` method.
  139. *
  140. * @param {String} type
  141. * @returns {Boolean}
  142. */
  143. is( type ) {
  144. return type === 'range' || type === 'model:range';
  145. }
  146. /**
  147. * Two ranges are equal if their {@link #start} and {@link #end} positions are equal.
  148. *
  149. * @param {module:engine/model/range~Range} otherRange Range to compare with.
  150. * @returns {Boolean} `true` if ranges are equal, `false` otherwise.
  151. */
  152. isEqual( otherRange ) {
  153. return this.start.isEqual( otherRange.start ) && this.end.isEqual( otherRange.end );
  154. }
  155. /**
  156. * Checks and returns whether this range intersects with given range.
  157. *
  158. * @param {module:engine/model/range~Range} otherRange Range to compare with.
  159. * @returns {Boolean} `true` if ranges intersect, `false` otherwise.
  160. */
  161. isIntersecting( otherRange ) {
  162. return this.start.isBefore( otherRange.end ) && this.end.isAfter( otherRange.start );
  163. }
  164. /**
  165. * Computes which part(s) of this {@link ~Range range} is not a part of given {@link ~Range range}.
  166. * Returned array contains zero, one or two {@link ~Range ranges}.
  167. *
  168. * Examples:
  169. *
  170. * let range = model.createRange(
  171. * model.createPositionFromPath( root, [ 2, 7 ] ),
  172. * model.createPositionFromPath( root, [ 4, 0, 1 ] )
  173. * );
  174. * let otherRange = model.createRange( model.createPositionFromPath( root, [ 1 ] ), model.createPositionFromPath( root, [ 5 ] ) );
  175. * let transformed = range.getDifference( otherRange );
  176. * // transformed array has no ranges because `otherRange` contains `range`
  177. *
  178. * otherRange = model.createRange( model.createPositionFromPath( root, [ 1 ] ), model.createPositionFromPath( root, [ 3 ] ) );
  179. * transformed = range.getDifference( otherRange );
  180. * // transformed array has one range: from [ 3 ] to [ 4, 0, 1 ]
  181. *
  182. * otherRange = model.createRange( model.createPositionFromPath( root, [ 3 ] ), model.createPositionFromPath( root, [ 4 ] ) );
  183. * transformed = range.getDifference( otherRange );
  184. * // transformed array has two ranges: from [ 2, 7 ] to [ 3 ] and from [ 4 ] to [ 4, 0, 1 ]
  185. *
  186. * @param {module:engine/model/range~Range} otherRange Range to differentiate against.
  187. * @returns {Array.<module:engine/model/range~Range>} The difference between ranges.
  188. */
  189. getDifference( otherRange ) {
  190. const ranges = [];
  191. if ( this.isIntersecting( otherRange ) ) {
  192. // Ranges intersect.
  193. if ( this.containsPosition( otherRange.start ) ) {
  194. // Given range start is inside this range. This means that we have to
  195. // add shrunken range - from the start to the middle of this range.
  196. ranges.push( new Range( this.start, otherRange.start ) );
  197. }
  198. if ( this.containsPosition( otherRange.end ) ) {
  199. // Given range end is inside this range. This means that we have to
  200. // add shrunken range - from the middle of this range to the end.
  201. ranges.push( new Range( otherRange.end, this.end ) );
  202. }
  203. } else {
  204. // Ranges do not intersect, return the original range.
  205. ranges.push( new Range( this.start, this.end ) );
  206. }
  207. return ranges;
  208. }
  209. /**
  210. * Returns an intersection of this {@link ~Range range} and given {@link ~Range range}.
  211. * Intersection is a common part of both of those ranges. If ranges has no common part, returns `null`.
  212. *
  213. * Examples:
  214. *
  215. * let range = model.createRange(
  216. * model.createPositionFromPath( root, [ 2, 7 ] ),
  217. * model.createPositionFromPath( root, [ 4, 0, 1 ] )
  218. * );
  219. * let otherRange = model.createRange( model.createPositionFromPath( root, [ 1 ] ), model.createPositionFromPath( root, [ 2 ] ) );
  220. * let transformed = range.getIntersection( otherRange ); // null - ranges have no common part
  221. *
  222. * otherRange = model.createRange( model.createPositionFromPath( root, [ 3 ] ), model.createPositionFromPath( root, [ 5 ] ) );
  223. * transformed = range.getIntersection( otherRange ); // range from [ 3 ] to [ 4, 0, 1 ]
  224. *
  225. * @param {module:engine/model/range~Range} otherRange Range to check for intersection.
  226. * @returns {module:engine/model/range~Range|null} A common part of given ranges or `null` if ranges have no common part.
  227. */
  228. getIntersection( otherRange ) {
  229. if ( this.isIntersecting( otherRange ) ) {
  230. // Ranges intersect, so a common range will be returned.
  231. // At most, it will be same as this range.
  232. let commonRangeStart = this.start;
  233. let commonRangeEnd = this.end;
  234. if ( this.containsPosition( otherRange.start ) ) {
  235. // Given range start is inside this range. This means thaNt we have to
  236. // shrink common range to the given range start.
  237. commonRangeStart = otherRange.start;
  238. }
  239. if ( this.containsPosition( otherRange.end ) ) {
  240. // Given range end is inside this range. This means that we have to
  241. // shrink common range to the given range end.
  242. commonRangeEnd = otherRange.end;
  243. }
  244. return new Range( commonRangeStart, commonRangeEnd );
  245. }
  246. // Ranges do not intersect, so they do not have common part.
  247. return null;
  248. }
  249. /**
  250. * Returns a range created by joining this {@link ~Range range} with the given {@link ~Range range}.
  251. * If ranges have no common part, returns `null`.
  252. *
  253. * Examples:
  254. *
  255. * let range = model.createRange(
  256. * model.createPositionFromPath( root, [ 2, 7 ] ),
  257. * model.createPositionFromPath( root, [ 4, 0, 1 ] )
  258. * );
  259. * let otherRange = model.createRange(
  260. * model.createPositionFromPath( root, [ 1 ] ),
  261. * model.createPositionFromPath( root, [ 2 ] )
  262. * );
  263. * let transformed = range.getJoined( otherRange ); // null - ranges have no common part
  264. *
  265. * otherRange = model.createRange(
  266. * model.createPositionFromPath( root, [ 3 ] ),
  267. * model.createPositionFromPath( root, [ 5 ] )
  268. * );
  269. * transformed = range.getJoined( otherRange ); // range from [ 2, 7 ] to [ 5 ]
  270. *
  271. * @param {module:engine/model/range~Range} otherRange Range to be joined.
  272. * @param {Boolean} [loose=false] Whether the intersection check is loose or strict. If the check is strict (`false`),
  273. * ranges are tested for intersection or whether start/end positions are equal. If the check is loose (`true`),
  274. * compared range is also checked if it's {@link module:engine/model/position~Position#isTouching touching} current range.
  275. * @returns {module:engine/model/range~Range|null} A sum of given ranges or `null` if ranges have no common part.
  276. */
  277. getJoined( otherRange, loose = false ) {
  278. let shouldJoin = this.isIntersecting( otherRange );
  279. if ( !shouldJoin ) {
  280. if ( this.start.isBefore( otherRange.start ) ) {
  281. shouldJoin = loose ? this.end.isTouching( otherRange.start ) : this.end.isEqual( otherRange.start );
  282. } else {
  283. shouldJoin = loose ? otherRange.end.isTouching( this.start ) : otherRange.end.isEqual( this.start );
  284. }
  285. }
  286. if ( !shouldJoin ) {
  287. return null;
  288. }
  289. let startPosition = this.start;
  290. let endPosition = this.end;
  291. if ( otherRange.start.isBefore( startPosition ) ) {
  292. startPosition = otherRange.start;
  293. }
  294. if ( otherRange.end.isAfter( endPosition ) ) {
  295. endPosition = otherRange.end;
  296. }
  297. return new Range( startPosition, endPosition );
  298. }
  299. /**
  300. * Computes and returns the smallest set of {@link #isFlat flat} ranges, that covers this range in whole.
  301. *
  302. * See an example of a model structure (`[` and `]` are range boundaries):
  303. *
  304. * root root
  305. * |- element DIV DIV P2 P3 DIV
  306. * | |- element H H P1 f o o b a r H P4
  307. * | | |- "fir[st" fir[st lorem se]cond ipsum
  308. * | |- element P1
  309. * | | |- "lorem" ||
  310. * |- element P2 ||
  311. * | |- "foo" VV
  312. * |- element P3
  313. * | |- "bar" root
  314. * |- element DIV DIV [P2 P3] DIV
  315. * | |- element H H [P1] f o o b a r H P4
  316. * | | |- "se]cond" fir[st] lorem [se]cond ipsum
  317. * | |- element P4
  318. * | | |- "ipsum"
  319. *
  320. * As it can be seen, letters contained in the range are: `stloremfoobarse`, spread across different parents.
  321. * We are looking for minimal set of flat ranges that contains the same nodes.
  322. *
  323. * Minimal flat ranges for above range `( [ 0, 0, 3 ], [ 3, 0, 2 ] )` will be:
  324. *
  325. * ( [ 0, 0, 3 ], [ 0, 0, 5 ] ) = "st"
  326. * ( [ 0, 1 ], [ 0, 2 ] ) = element P1 ("lorem")
  327. * ( [ 1 ], [ 3 ] ) = element P2, element P3 ("foobar")
  328. * ( [ 3, 0, 0 ], [ 3, 0, 2 ] ) = "se"
  329. *
  330. * **Note:** if an {@link module:engine/model/element~Element element} is not wholly contained in this range, it won't be returned
  331. * in any of the returned flat ranges. See in the example how `H` elements at the beginning and at the end of the range
  332. * were omitted. Only their parts that were wholly in the range were returned.
  333. *
  334. * **Note:** this method is not returning flat ranges that contain no nodes.
  335. *
  336. * @returns {Array.<module:engine/model/range~Range>} Array of flat ranges covering this range.
  337. */
  338. getMinimalFlatRanges() {
  339. const ranges = [];
  340. const diffAt = this.start.getCommonPath( this.end ).length;
  341. const pos = Position._createAt( this.start );
  342. let posParent = pos.parent;
  343. // Go up.
  344. while ( pos.path.length > diffAt + 1 ) {
  345. const howMany = posParent.maxOffset - pos.offset;
  346. if ( howMany !== 0 ) {
  347. ranges.push( new Range( pos, pos.getShiftedBy( howMany ) ) );
  348. }
  349. pos.path = pos.path.slice( 0, -1 );
  350. pos.offset++;
  351. posParent = posParent.parent;
  352. }
  353. // Go down.
  354. while ( pos.path.length <= this.end.path.length ) {
  355. const offset = this.end.path[ pos.path.length - 1 ];
  356. const howMany = offset - pos.offset;
  357. if ( howMany !== 0 ) {
  358. ranges.push( new Range( pos, pos.getShiftedBy( howMany ) ) );
  359. }
  360. pos.offset = offset;
  361. pos.path.push( 0 );
  362. }
  363. return ranges;
  364. }
  365. /**
  366. * Creates a {@link module:engine/model/treewalker~TreeWalker TreeWalker} instance with this range as a boundary.
  367. *
  368. * For example, to iterate over all items in the entire document root:
  369. *
  370. * // Create a range spanning over the entire root content:
  371. * const range = editor.model.createRangeIn( editor.model.document.getRoot() );
  372. *
  373. * // Iterate over all items in this range:
  374. * for ( const value of range.getWalker() ) {
  375. * console.log( value.item );
  376. * }
  377. *
  378. * @param {Object} options Object with configuration options. See {@link module:engine/model/treewalker~TreeWalker}.
  379. * @param {module:engine/model/position~Position} [options.startPosition]
  380. * @param {Boolean} [options.singleCharacters=false]
  381. * @param {Boolean} [options.shallow=false]
  382. * @param {Boolean} [options.ignoreElementEnd=false]
  383. */
  384. getWalker( options = {} ) {
  385. options.boundaries = this;
  386. return new TreeWalker( options );
  387. }
  388. /**
  389. * Returns an iterator that iterates over all {@link module:engine/model/item~Item items} that are in this range and returns
  390. * them.
  391. *
  392. * This method uses {@link module:engine/model/treewalker~TreeWalker} with `boundaries` set to this range and `ignoreElementEnd` option
  393. * set to `true`. However it returns only {@link module:engine/model/item~Item model items},
  394. * not {@link module:engine/model/treewalker~TreeWalkerValue}.
  395. *
  396. * You may specify additional options for the tree walker. See {@link module:engine/model/treewalker~TreeWalker} for
  397. * a full list of available options.
  398. *
  399. * @param {Object} options Object with configuration options. See {@link module:engine/model/treewalker~TreeWalker}.
  400. * @returns {Iterable.<module:engine/model/item~Item>}
  401. */
  402. * getItems( options = {} ) {
  403. options.boundaries = this;
  404. options.ignoreElementEnd = true;
  405. const treeWalker = new TreeWalker( options );
  406. for ( const value of treeWalker ) {
  407. yield value.item;
  408. }
  409. }
  410. /**
  411. * Returns an iterator that iterates over all {@link module:engine/model/position~Position positions} that are boundaries or
  412. * contained in this range.
  413. *
  414. * This method uses {@link module:engine/model/treewalker~TreeWalker} with `boundaries` set to this range. However it returns only
  415. * {@link module:engine/model/position~Position positions}, not {@link module:engine/model/treewalker~TreeWalkerValue}.
  416. *
  417. * You may specify additional options for the tree walker. See {@link module:engine/model/treewalker~TreeWalker} for
  418. * a full list of available options.
  419. *
  420. * @param {Object} options Object with configuration options. See {@link module:engine/model/treewalker~TreeWalker}.
  421. * @returns {Iterable.<module:engine/model/position~Position>}
  422. */
  423. * getPositions( options = {} ) {
  424. options.boundaries = this;
  425. const treeWalker = new TreeWalker( options );
  426. yield treeWalker.position;
  427. for ( const value of treeWalker ) {
  428. yield value.nextPosition;
  429. }
  430. }
  431. /**
  432. * Returns a range that is a result of transforming this range by given `operation`.
  433. *
  434. * **Note:** transformation may break one range into multiple ranges (for example, when a part of the range is
  435. * moved to a different part of document tree). For this reason, an array is returned by this method and it
  436. * may contain one or more `Range` instances.
  437. *
  438. * @param {module:engine/model/operation/operation~Operation} operation Operation to transform range by.
  439. * @returns {Array.<module:engine/model/range~Range>} Range which is the result of transformation.
  440. */
  441. getTransformedByOperation( operation ) {
  442. switch ( operation.type ) {
  443. case 'insert':
  444. return this._getTransformedByInsertOperation( operation );
  445. case 'move':
  446. case 'remove':
  447. case 'reinsert':
  448. return this._getTransformedByMoveOperation( operation );
  449. case 'split':
  450. return [ this._getTransformedBySplitOperation( operation ) ];
  451. case 'merge':
  452. return [ this._getTransformedByMergeOperation( operation ) ];
  453. }
  454. return [ new Range( this.start, this.end ) ];
  455. }
  456. /**
  457. * Returns a range that is a result of transforming this range by multiple `operations`.
  458. *
  459. * @see ~Range#getTransformedByOperation
  460. * @param {Iterable.<module:engine/model/operation/operation~Operation>} operations Operations to transform the range by.
  461. * @returns {Array.<module:engine/model/range~Range>} Range which is the result of transformation.
  462. */
  463. getTransformedByOperations( operations ) {
  464. const ranges = [ new Range( this.start, this.end ) ];
  465. for ( const operation of operations ) {
  466. for ( let i = 0; i < ranges.length; i++ ) {
  467. const result = ranges[ i ].getTransformedByOperation( operation );
  468. ranges.splice( i, 1, ...result );
  469. i += result.length - 1;
  470. }
  471. }
  472. // It may happen that a range is split into two, and then the part of second "piece" is moved into first
  473. // "piece". In this case we will have incorrect third range, which should not be included in the result --
  474. // because it is already included in the first "piece". In this loop we are looking for all such ranges that
  475. // are inside other ranges and we simply remove them.
  476. for ( let i = 0; i < ranges.length; i++ ) {
  477. const range = ranges[ i ];
  478. for ( let j = i + 1; j < ranges.length; j++ ) {
  479. const next = ranges[ j ];
  480. if ( range.containsRange( next ) || next.containsRange( range ) || range.isEqual( next ) ) {
  481. ranges.splice( j, 1 );
  482. }
  483. }
  484. }
  485. return ranges;
  486. }
  487. /**
  488. * Returns an {@link module:engine/model/element~Element} or {@link module:engine/model/documentfragment~DocumentFragment}
  489. * which is a common ancestor of the range's both ends (in which the entire range is contained).
  490. *
  491. * @returns {module:engine/model/element~Element|module:engine/model/documentfragment~DocumentFragment|null}
  492. */
  493. getCommonAncestor() {
  494. return this.start.getCommonAncestor( this.end );
  495. }
  496. /**
  497. * Returns an {@link module:engine/model/element~Element Element} contained by the range.
  498. * The element will be returned when it is the **only** node within the range and **fully–contained**
  499. * at the same time.
  500. *
  501. * @returns {module:engine/model/element~Element|null}
  502. */
  503. getContainedElement() {
  504. if ( this.isCollapsed ) {
  505. return null;
  506. }
  507. const nodeAfterStart = this.start.nodeAfter;
  508. const nodeBeforeEnd = this.end.nodeBefore;
  509. if ( nodeAfterStart && nodeAfterStart.is( 'element' ) && nodeAfterStart === nodeBeforeEnd ) {
  510. return nodeAfterStart;
  511. }
  512. return null;
  513. }
  514. /**
  515. * Converts `Range` to plain object and returns it.
  516. *
  517. * @returns {Object} `Node` converted to plain object.
  518. */
  519. toJSON() {
  520. return {
  521. start: this.start.toJSON(),
  522. end: this.end.toJSON()
  523. };
  524. }
  525. /**
  526. * Returns a new range that is equal to current range.
  527. *
  528. * @returns {module:engine/model/range~Range}
  529. */
  530. clone() {
  531. return new this.constructor( this.start, this.end );
  532. }
  533. /**
  534. * Returns a result of transforming a copy of this range by insert operation.
  535. *
  536. * One or more ranges may be returned as a result of this transformation.
  537. *
  538. * @protected
  539. * @param {module:engine/model/operation/insertoperation~InsertOperation} operation
  540. * @returns {Array.<module:engine/model/range~Range>}
  541. */
  542. _getTransformedByInsertOperation( operation, spread = false ) {
  543. return this._getTransformedByInsertion( operation.position, operation.howMany, spread );
  544. }
  545. /**
  546. * Returns a result of transforming a copy of this range by move operation.
  547. *
  548. * One or more ranges may be returned as a result of this transformation.
  549. *
  550. * @protected
  551. * @param {module:engine/model/operation/moveoperation~MoveOperation} operation
  552. * @returns {Array.<module:engine/model/range~Range>}
  553. */
  554. _getTransformedByMoveOperation( operation, spread = false ) {
  555. const sourcePosition = operation.sourcePosition;
  556. const howMany = operation.howMany;
  557. const targetPosition = operation.targetPosition;
  558. return this._getTransformedByMove( sourcePosition, targetPosition, howMany, spread );
  559. }
  560. /**
  561. * Returns a result of transforming a copy of this range by split operation.
  562. *
  563. * Always one range is returned. The transformation is done in a way to not break the range.
  564. *
  565. * @protected
  566. * @param {module:engine/model/operation/splitoperation~SplitOperation} operation
  567. * @returns {module:engine/model/range~Range}
  568. */
  569. _getTransformedBySplitOperation( operation ) {
  570. const start = this.start._getTransformedBySplitOperation( operation );
  571. let end = this.end._getTransformedBySplitOperation( operation );
  572. if ( this.end.isEqual( operation.insertionPosition ) ) {
  573. end = this.end.getShiftedBy( 1 );
  574. }
  575. // Below may happen when range contains graveyard element used by split operation.
  576. if ( start.root != end.root ) {
  577. // End position was next to the moved graveyard element and was moved with it.
  578. // Fix it by using old `end` which has proper `root`.
  579. end = this.end.getShiftedBy( -1 );
  580. }
  581. return new Range( start, end );
  582. }
  583. /**
  584. * Returns a result of transforming a copy of this range by merge operation.
  585. *
  586. * Always one range is returned. The transformation is done in a way to not break the range.
  587. *
  588. * @protected
  589. * @param {module:engine/model/operation/mergeoperation~MergeOperation} operation
  590. * @returns {module:engine/model/range~Range}
  591. */
  592. _getTransformedByMergeOperation( operation ) {
  593. // Special case when the marker is set on "the closing tag" of an element. Marker can be set like that during
  594. // transformations, especially when a content of a few block elements were removed. For example:
  595. //
  596. // {} is the transformed range, [] is the removed range.
  597. // <p>F[o{o</p><p>B}ar</p><p>Xy]z</p>
  598. //
  599. // <p>Fo{o</p><p>B}ar</p><p>z</p>
  600. // <p>F{</p><p>B}ar</p><p>z</p>
  601. // <p>F{</p>}<p>z</p>
  602. // <p>F{}z</p>
  603. //
  604. if ( this.start.isEqual( operation.targetPosition ) && this.end.isEqual( operation.deletionPosition ) ) {
  605. return new Range( this.start );
  606. }
  607. let start = this.start._getTransformedByMergeOperation( operation );
  608. let end = this.end._getTransformedByMergeOperation( operation );
  609. if ( start.root != end.root ) {
  610. // This happens when the end position was next to the merged (deleted) element.
  611. // Then, the end position was moved to the graveyard root. In this case we need to fix
  612. // the range cause its boundaries would be in different roots.
  613. end = this.end.getShiftedBy( -1 );
  614. }
  615. if ( start.isAfter( end ) ) {
  616. // This happens in three following cases:
  617. //
  618. // Case 1: Merge operation source position is before the target position (due to some transformations, OT, etc.)
  619. // This means that start can be moved before the end of the range.
  620. //
  621. // Before: <p>a{a</p><p>b}b</p><p>cc</p>
  622. // Merge: <p>b}b</p><p>cca{a</p>
  623. // Fix: <p>{b}b</p><p>ccaa</p>
  624. //
  625. // Case 2: Range start is before merged node but not directly.
  626. // Result should include all nodes that were in the original range.
  627. //
  628. // Before: <p>aa</p>{<p>cc</p><p>b}b</p>
  629. // Merge: <p>aab}b</p>{<p>cc</p>
  630. // Fix: <p>aa{bb</p><p>cc</p>}
  631. //
  632. // The range is expanded by an additional `b` letter but it is better than dropping the whole `cc` paragraph.
  633. //
  634. // Case 3: Range start is directly before merged node.
  635. // Resulting range should include only nodes from the merged element:
  636. //
  637. // Before: <p>aa</p>{<p>b}b</p><p>cc</p>
  638. // Merge: <p>aab}b</p>{<p>cc</p>
  639. // Fix: <p>aa{b}b</p><p>cc</p>
  640. //
  641. if ( operation.sourcePosition.isBefore( operation.targetPosition ) ) {
  642. // Case 1.
  643. start = Position._createAt( end );
  644. start.offset = 0;
  645. } else {
  646. if ( !operation.deletionPosition.isEqual( start ) ) {
  647. // Case 2.
  648. end = operation.deletionPosition;
  649. }
  650. // In both case 2 and 3 start is at the end of the merge-to element.
  651. start = operation.targetPosition;
  652. }
  653. return new Range( start, end );
  654. }
  655. return new Range( start, end );
  656. }
  657. /**
  658. * Returns an array containing one or two {@link ~Range ranges} that are a result of transforming this
  659. * {@link ~Range range} by inserting `howMany` nodes at `insertPosition`. Two {@link ~Range ranges} are
  660. * returned if the insertion was inside this {@link ~Range range} and `spread` is set to `true`.
  661. *
  662. * Examples:
  663. *
  664. * let range = model.createRange(
  665. * model.createPositionFromPath( root, [ 2, 7 ] ),
  666. * model.createPositionFromPath( root, [ 4, 0, 1 ] )
  667. * );
  668. * let transformed = range._getTransformedByInsertion( model.createPositionFromPath( root, [ 1 ] ), 2 );
  669. * // transformed array has one range from [ 4, 7 ] to [ 6, 0, 1 ]
  670. *
  671. * transformed = range._getTransformedByInsertion( model.createPositionFromPath( root, [ 4, 0, 0 ] ), 4 );
  672. * // transformed array has one range from [ 2, 7 ] to [ 4, 0, 5 ]
  673. *
  674. * transformed = range._getTransformedByInsertion( model.createPositionFromPath( root, [ 3, 2 ] ), 4 );
  675. * // transformed array has one range, which is equal to original range
  676. *
  677. * transformed = range._getTransformedByInsertion( model.createPositionFromPath( root, [ 3, 2 ] ), 4, true );
  678. * // transformed array has two ranges: from [ 2, 7 ] to [ 3, 2 ] and from [ 3, 6 ] to [ 4, 0, 1 ]
  679. *
  680. * @protected
  681. * @param {module:engine/model/position~Position} insertPosition Position where nodes are inserted.
  682. * @param {Number} howMany How many nodes are inserted.
  683. * @param {Boolean} [spread] Flag indicating whether this {~Range range} should be spread if insertion
  684. * was inside the range. Defaults to `false`.
  685. * @returns {Array.<module:engine/model/range~Range>} Result of the transformation.
  686. */
  687. _getTransformedByInsertion( insertPosition, howMany, spread = false ) {
  688. if ( spread && this.containsPosition( insertPosition ) ) {
  689. // Range has to be spread. The first part is from original start to the spread point.
  690. // The other part is from spread point to the original end, but transformed by
  691. // insertion to reflect insertion changes.
  692. return [
  693. new Range( this.start, insertPosition ),
  694. new Range(
  695. insertPosition.getShiftedBy( howMany ),
  696. this.end._getTransformedByInsertion( insertPosition, howMany )
  697. )
  698. ];
  699. } else {
  700. const range = new Range( this.start, this.end );
  701. range.start = range.start._getTransformedByInsertion( insertPosition, howMany );
  702. range.end = range.end._getTransformedByInsertion( insertPosition, howMany );
  703. return [ range ];
  704. }
  705. }
  706. /**
  707. * Returns an array containing {@link ~Range ranges} that are a result of transforming this
  708. * {@link ~Range range} by moving `howMany` nodes from `sourcePosition` to `targetPosition`.
  709. *
  710. * @protected
  711. * @param {module:engine/model/position~Position} sourcePosition Position from which nodes are moved.
  712. * @param {module:engine/model/position~Position} targetPosition Position to where nodes are moved.
  713. * @param {Number} howMany How many nodes are moved.
  714. * @param {Boolean} [spread=false] Whether the range should be spread if the move points inside the range.
  715. * @returns {Array.<module:engine/model/range~Range>} Result of the transformation.
  716. */
  717. _getTransformedByMove( sourcePosition, targetPosition, howMany, spread = false ) {
  718. // Special case for transforming a collapsed range. Just transform it like a position.
  719. if ( this.isCollapsed ) {
  720. const newPos = this.start._getTransformedByMove( sourcePosition, targetPosition, howMany );
  721. return [ new Range( newPos ) ];
  722. }
  723. // Special case for transformation when a part of the range is moved towards the range.
  724. //
  725. // Examples:
  726. //
  727. // <div><p>ab</p><p>c[d</p></div><p>e]f</p> --> <div><p>ab</p></div><p>c[d</p><p>e]f</p>
  728. // <p>e[f</p><div><p>a]b</p><p>cd</p></div> --> <p>e[f</p><p>a]b</p><div><p>cd</p></div>
  729. //
  730. // Without this special condition, the default algorithm leaves an "artifact" range from one of `differenceSet` parts:
  731. //
  732. // <div><p>ab</p><p>c[d</p></div><p>e]f</p> --> <div><p>ab</p>{</div>}<p>c[d</p><p>e]f</p>
  733. //
  734. // This special case is applied only if the range is to be kept together (not spread).
  735. const moveRange = Range._createFromPositionAndShift( sourcePosition, howMany );
  736. const insertPosition = targetPosition._getTransformedByDeletion( sourcePosition, howMany );
  737. if ( this.containsPosition( targetPosition ) && !spread ) {
  738. if ( moveRange.containsPosition( this.start ) || moveRange.containsPosition( this.end ) ) {
  739. const start = this.start._getTransformedByMove( sourcePosition, targetPosition, howMany );
  740. const end = this.end._getTransformedByMove( sourcePosition, targetPosition, howMany );
  741. return [ new Range( start, end ) ];
  742. }
  743. }
  744. // Default algorithm.
  745. let result;
  746. const differenceSet = this.getDifference( moveRange );
  747. let difference = null;
  748. const common = this.getIntersection( moveRange );
  749. if ( differenceSet.length == 1 ) {
  750. // `moveRange` and this range may intersect but may be separate.
  751. difference = new Range(
  752. differenceSet[ 0 ].start._getTransformedByDeletion( sourcePosition, howMany ),
  753. differenceSet[ 0 ].end._getTransformedByDeletion( sourcePosition, howMany )
  754. );
  755. } else if ( differenceSet.length == 2 ) {
  756. // `moveRange` is inside this range.
  757. difference = new Range(
  758. this.start,
  759. this.end._getTransformedByDeletion( sourcePosition, howMany )
  760. );
  761. } // else, `moveRange` contains this range.
  762. if ( difference ) {
  763. result = difference._getTransformedByInsertion( insertPosition, howMany, common !== null || spread );
  764. } else {
  765. result = [];
  766. }
  767. if ( common ) {
  768. const transformedCommon = new Range(
  769. common.start._getCombined( moveRange.start, insertPosition ),
  770. common.end._getCombined( moveRange.start, insertPosition )
  771. );
  772. if ( result.length == 2 ) {
  773. result.splice( 1, 0, transformedCommon );
  774. } else {
  775. result.push( transformedCommon );
  776. }
  777. }
  778. return result;
  779. }
  780. /**
  781. * Returns a copy of this range that is transformed by deletion of `howMany` nodes from `deletePosition`.
  782. *
  783. * If the deleted range is intersecting with the transformed range, the transformed range will be shrank.
  784. *
  785. * If the deleted range contains transformed range, `null` will be returned.
  786. *
  787. * @protected
  788. * @param {module:engine/model/position~Position} deletionPosition Position from which nodes are removed.
  789. * @param {Number} howMany How many nodes are removed.
  790. * @returns {module:engine/model/range~Range|null} Result of the transformation.
  791. */
  792. _getTransformedByDeletion( deletePosition, howMany ) {
  793. let newStart = this.start._getTransformedByDeletion( deletePosition, howMany );
  794. let newEnd = this.end._getTransformedByDeletion( deletePosition, howMany );
  795. if ( newStart == null && newEnd == null ) {
  796. return null;
  797. }
  798. if ( newStart == null ) {
  799. newStart = deletePosition;
  800. }
  801. if ( newEnd == null ) {
  802. newEnd = deletePosition;
  803. }
  804. return new Range( newStart, newEnd );
  805. }
  806. /**
  807. * Creates a new range, spreading from specified {@link module:engine/model/position~Position position} to a position moved by
  808. * given `shift`. If `shift` is a negative value, shifted position is treated as the beginning of the range.
  809. *
  810. * @protected
  811. * @param {module:engine/model/position~Position} position Beginning of the range.
  812. * @param {Number} shift How long the range should be.
  813. * @returns {module:engine/model/range~Range}
  814. */
  815. static _createFromPositionAndShift( position, shift ) {
  816. const start = position;
  817. const end = position.getShiftedBy( shift );
  818. return shift > 0 ? new this( start, end ) : new this( end, start );
  819. }
  820. /**
  821. * Creates a range inside an {@link module:engine/model/element~Element element} which starts before the first child of
  822. * that element and ends after the last child of that element.
  823. *
  824. * @protected
  825. * @param {module:engine/model/element~Element} element Element which is a parent for the range.
  826. * @returns {module:engine/model/range~Range}
  827. */
  828. static _createIn( element ) {
  829. return new this( Position._createAt( element, 0 ), Position._createAt( element, element.maxOffset ) );
  830. }
  831. /**
  832. * Creates a range that starts before given {@link module:engine/model/item~Item model item} and ends after it.
  833. *
  834. * @protected
  835. * @param {module:engine/model/item~Item} item
  836. * @returns {module:engine/model/range~Range}
  837. */
  838. static _createOn( item ) {
  839. return this._createFromPositionAndShift( Position._createBefore( item ), item.offsetSize );
  840. }
  841. /**
  842. * Combines all ranges from the passed array into a one range. At least one range has to be passed.
  843. * Passed ranges must not have common parts.
  844. *
  845. * The first range from the array is a reference range. If other ranges start or end on the exactly same position where
  846. * the reference range, they get combined into one range.
  847. *
  848. * [ ][] [ ][ ][ ][ ][] [ ] // Passed ranges, shown sorted
  849. * [ ] // The result of the function if the first range was a reference range.
  850. * [ ] // The result of the function if the third-to-seventh range was a reference range.
  851. * [ ] // The result of the function if the last range was a reference range.
  852. *
  853. * @param {Array.<module:engine/model/range~Range>} ranges Ranges to combine.
  854. * @returns {module:engine/model/range~Range} Combined range.
  855. */
  856. static _createFromRanges( ranges ) {
  857. if ( ranges.length === 0 ) {
  858. /**
  859. * At least one range has to be passed to
  860. * {@link module:engine/model/range~Range._createFromRanges `Range._createFromRanges()`}.
  861. *
  862. * @error range-create-from-ranges-empty-array
  863. */
  864. throw new CKEditorError(
  865. 'range-create-from-ranges-empty-array: At least one range has to be passed.',
  866. null
  867. );
  868. } else if ( ranges.length == 1 ) {
  869. return ranges[ 0 ].clone();
  870. }
  871. // 1. Set the first range in `ranges` array as a reference range.
  872. // If we are going to return just a one range, one of the ranges need to be the reference one.
  873. // Other ranges will be stuck to that range, if possible.
  874. const ref = ranges[ 0 ];
  875. // 2. Sort all the ranges so it's easier to process them.
  876. ranges.sort( ( a, b ) => {
  877. return a.start.isAfter( b.start ) ? 1 : -1;
  878. } );
  879. // 3. Check at which index the reference range is now.
  880. const refIndex = ranges.indexOf( ref );
  881. // 4. At this moment we don't need the original range.
  882. // We are going to modify the result and we need to return a new instance of Range.
  883. // We have to create a copy of the reference range.
  884. const result = new this( ref.start, ref.end );
  885. // 5. Ranges should be checked and glued starting from the range that is closest to the reference range.
  886. // Since ranges are sorted, start with the range with index that is closest to reference range index.
  887. if ( refIndex > 0 ) {
  888. for ( let i = refIndex - 1; true; i++ ) {
  889. if ( ranges[ i ].end.isEqual( result.start ) ) {
  890. result.start = Position._createAt( ranges[ i ].start );
  891. } else {
  892. // If ranges are not starting/ending at the same position there is no point in looking further.
  893. break;
  894. }
  895. }
  896. }
  897. // 6. Ranges should be checked and glued starting from the range that is closest to the reference range.
  898. // Since ranges are sorted, start with the range with index that is closest to reference range index.
  899. for ( let i = refIndex + 1; i < ranges.length; i++ ) {
  900. if ( ranges[ i ].start.isEqual( result.end ) ) {
  901. result.end = Position._createAt( ranges[ i ].end );
  902. } else {
  903. // If ranges are not starting/ending at the same position there is no point in looking further.
  904. break;
  905. }
  906. }
  907. return result;
  908. }
  909. /**
  910. * Creates a `Range` instance from given plain object (i.e. parsed JSON string).
  911. *
  912. * @param {Object} json Plain object to be converted to `Range`.
  913. * @param {module:engine/model/document~Document} doc Document object that will be range owner.
  914. * @returns {module:engine/model/element~Element} `Range` instance created using given plain object.
  915. */
  916. static fromJSON( json, doc ) {
  917. return new this( Position.fromJSON( json.start, doc ), Position.fromJSON( json.end, doc ) );
  918. }
  919. // @if CK_DEBUG_ENGINE // toString() {
  920. // @if CK_DEBUG_ENGINE // return `${ this.root } [ ${ this.start.path.join( ', ' ) } ] - [ ${ this.end.path.join( ', ' ) } ]`;
  921. // @if CK_DEBUG_ENGINE // }
  922. // @if CK_DEBUG_ENGINE // log() {
  923. // @if CK_DEBUG_ENGINE // console.log( 'ModelPosition: ' + this );
  924. // @if CK_DEBUG_ENGINE // }
  925. }