8
0

nodelist.js 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453
  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 CharacterProxy from './characterproxy.js';
  7. import Text from './text.js';
  8. import utils from '../utils.js';
  9. import clone from '../lib/lodash/clone.js';
  10. import CKEditorError from '../ckeditorerror.js';
  11. /**
  12. * This is a private helper-class for {@link core.treeModel.NodeList} text compression utility.
  13. *
  14. * @protected
  15. * @memberOf core.treeModel
  16. */
  17. class NodeListText extends Text {
  18. /**
  19. * @see {@link core.treeModel.Text#constructor}
  20. * @protected
  21. * @constructor
  22. */
  23. constructor( text, attrs ) {
  24. super( text, attrs );
  25. this.parent = null;
  26. }
  27. /**
  28. * Gets a character at given index and creates a {@link core.treeModel.CharacterProxy} out of it.
  29. *
  30. * @param {Number} index Character index.
  31. * @returns {core.treeModel.CharacterProxy}
  32. */
  33. getCharAt( index ) {
  34. index = index && index >= 0 ? index : 0;
  35. return new CharacterProxy( this, index );
  36. }
  37. /**
  38. * Custom toJSON method to solve child-parent circular dependencies.
  39. *
  40. * @returns {Object} Clone of this object with the parent property replaced with its name.
  41. */
  42. toJSON() {
  43. const json = clone( this );
  44. json.parent = json.parent ? this.parent.name : null;
  45. return json;
  46. }
  47. }
  48. /**
  49. * List of nodes. It is used to represent multiple nodes with a given order, for example children of
  50. * {@link core.treeModel.Element} object or nodes inserted using {@link core.treeModel.operation.InsertOperation}.
  51. *
  52. * Thanks to the constructor, which accepts various arguments, this class lets you easily create desired list of nodes.
  53. *
  54. * Parameters passed to constructor are converted and internally kept as an array of {@link core.treeModel.Node}
  55. * and {@link core.treeModel.Text} instances.
  56. *
  57. * @memberOf core.treeModel
  58. */
  59. export default class NodeList {
  60. /**
  61. * Constructor lets you create a list of nodes in many ways. See examples:
  62. *
  63. * let nodeList = new NodeList( [ new Element( p1 ), new Element( p1 ) ] );
  64. * nodeList.length; // 2
  65. *
  66. * let nodeList = new NodeList( new Element( p ) );
  67. * nodeList.length; // 1
  68. *
  69. * let nodeList = new NodeList( [ 'foo', new Element( p ), 'bar' ] );
  70. * nodeList.length; // 7
  71. *
  72. * let nodeList = new NodeList( 'foo' );
  73. * nodeList.length; // 3
  74. *
  75. * let nodeList = new NodeList( new Text( 'foo', { bar: 'bom' } ) );
  76. * nodeList.length; // 3
  77. * nodeList.get( 0 ).getAttribute( 'bar' ); // 'bom'
  78. * nodeList.get( 1 ).getAttribute( 'bar' ); // 'bom'
  79. * nodeList.get( 2 ).getAttribute( 'bar' ); // 'bom'
  80. *
  81. * let nodeListA = new NodeList( 'foo' );
  82. * let nodeListB = new NodeList( nodeListA );
  83. * nodeListA === nodeListB // true
  84. * nodeListB.length // 3
  85. *
  86. * @see {@link core.treeModel.NodeSet} for more explanation.
  87. *
  88. * @param {core.treeModel.NodeSet} nodes List of nodes.
  89. * @constructor
  90. */
  91. constructor( nodes ) {
  92. if ( nodes instanceof NodeList ) {
  93. // We do not clone anything.
  94. return nodes;
  95. }
  96. /**
  97. * Internal array to store nodes.
  98. *
  99. * @protected
  100. * @type {Array}
  101. */
  102. this._nodes = [];
  103. /**
  104. * Internal array where each index is mapped to correct node from `_nodes` array. This is introduced
  105. * to easily refer `_nodes` by index, since some of elements in `_nodes` may contain multiple characters,
  106. * which occupy multiple slots in `_indexMap`.
  107. *
  108. * @private
  109. * @type {Array}
  110. */
  111. this._indexMap = [];
  112. if ( nodes ) {
  113. if ( typeof nodes == 'string' || !utils.isIterable( nodes ) ) {
  114. nodes = [ nodes ];
  115. }
  116. for ( let node of nodes ) {
  117. let indexInNodes = this._nodes.length;
  118. let mergedWithPrev = false;
  119. let length = 1;
  120. if ( node instanceof CharacterProxy ) {
  121. node = new NodeListText( node.character, node._attrs );
  122. } else if ( node instanceof Text ) {
  123. node = new NodeListText( node.text, node._attrs );
  124. } else if ( typeof node == 'string' ) {
  125. node = new NodeListText( node, [] );
  126. }
  127. if ( node instanceof NodeListText ) {
  128. length = node.text.length;
  129. let prev = this._nodes[ this._nodes.length - 1 ];
  130. if ( prev instanceof NodeListText && utils.mapsEqual( prev._attrs, node._attrs ) ) {
  131. // If previously added text has same attributes, merge this text with it.
  132. prev.text += node.text;
  133. mergedWithPrev = true;
  134. indexInNodes--;
  135. } else if ( node.text.length === 0 ) {
  136. // If this is an empty text just omit it.
  137. continue;
  138. }
  139. }
  140. if ( !mergedWithPrev ) {
  141. this._nodes.push( node );
  142. }
  143. for ( let i = 0; i < length; i++ ) {
  144. this._indexMap.push( indexInNodes );
  145. }
  146. }
  147. }
  148. }
  149. /**
  150. * Number of nodes in the node list.
  151. *
  152. * @readonly
  153. * @type {Number}
  154. */
  155. get length() {
  156. return this._indexMap.length;
  157. }
  158. /**
  159. * Node list iterator.
  160. */
  161. [ Symbol.iterator ]() {
  162. let i = 0;
  163. return {
  164. next: () => ( {
  165. done: i == this.length,
  166. value: this.get( i++ )
  167. } )
  168. };
  169. }
  170. /**
  171. * Returns node at the given index.
  172. *
  173. * @param {Number} index Node index.
  174. * @returns {core.treeModel.Node} Node at given index.
  175. */
  176. get( index ) {
  177. let realIndex = this._indexMap[ index ];
  178. let node = this._nodes[ realIndex ];
  179. if ( node instanceof NodeListText ) {
  180. return node.getCharAt( this._getCharIndex( index ) );
  181. } else {
  182. return node;
  183. }
  184. }
  185. /**
  186. * Search for the element in the node list.
  187. *
  188. * @param {core.treeModel.Node} node Node to find.
  189. * @returns {Number} Position of the element in the list or -1 if not found.
  190. */
  191. indexOf( node ) {
  192. if ( node instanceof CharacterProxy ) {
  193. let baseIndex = this.indexOf( node._nodeListText );
  194. return baseIndex == -1 ? -1 : baseIndex + node._index;
  195. }
  196. let realIndex = this._nodes.indexOf( node );
  197. return this._indexMap.indexOf( realIndex );
  198. }
  199. /**
  200. * Inserts nodes from the given node list into this node list at the given index.
  201. *
  202. * @param {Number} index Position where nodes should be inserted.
  203. * @param {core.treeModel.NodeList} nodeList List of nodes to insert.
  204. */
  205. insert( index, nodeList ) {
  206. if ( this._nodes.length === 0 ) {
  207. this._nodes = nodeList._nodes.slice();
  208. this._indexMap = nodeList._indexMap.slice();
  209. return;
  210. }
  211. // If we are inserting into a text, splitting may be needed.
  212. this._splitNodeAt( index );
  213. // If `index` is too high to be found in `_indexMap` it means that we insert at the end of node list.
  214. let realIndex = index >= this._indexMap.length ? this._nodes.length : this._indexMap[ index ];
  215. // Splice arrays from inserted nodeList into this nodeList.
  216. this._indexMap.splice.apply( this._indexMap, [ index, 0 ].concat( nodeList._indexMap ) );
  217. this._nodes.splice.apply( this._nodes, [ realIndex, 0 ].concat( nodeList._nodes ) );
  218. // Fix indexes in index map.
  219. // From the beginning of spliced-in array to the end of spliced-in array.
  220. for ( let i = index; i < index + nodeList._indexMap.length; i++ ) {
  221. this._indexMap[ i ] += realIndex;
  222. }
  223. // From the end of spliced-in array to the end of original array.
  224. for ( let i = index + nodeList._indexMap.length; i < this._indexMap.length; i++ ) {
  225. this._indexMap[ i ] += nodeList._nodes.length;
  226. }
  227. this._mergeNodeAt( index );
  228. this._mergeNodeAt( index + nodeList.length );
  229. }
  230. /**
  231. * Removes number of nodes starting at the given index.
  232. *
  233. * @param {Number} index Position of the first node to remove.
  234. * @param {Number} number Number of nodes to remove.
  235. * @returns {core.treeModel.NodeList} List of removed nodes.
  236. */
  237. remove( index, number ) {
  238. if ( this._nodes.length === 0 ) {
  239. return new NodeList();
  240. }
  241. // Removed "range" may start in NodeListText or end in NodeListText. Some splitting may be needed.
  242. this._splitNodeAt( index );
  243. this._splitNodeAt( index + number );
  244. // If given index is too high to be found in `_indexMap` it means that we remove to the end of node list.
  245. let realIndexEnd = ( index + number ) >= this._indexMap.length ? this._nodes.length : this._indexMap[ index + number ];
  246. let realIndexStart = this._indexMap[ index ];
  247. let removed = this._nodes.splice( realIndexStart, realIndexEnd - realIndexStart );
  248. this._indexMap.splice( index, number );
  249. for ( let i = index; i < this._indexMap.length ; i++ ) {
  250. this._indexMap[ i ] -= removed.length;
  251. }
  252. this._mergeNodeAt( index );
  253. return new NodeList( removed );
  254. }
  255. /**
  256. * Sets or removes given attribute on a range of nodes in the node list.
  257. *
  258. * @param {Number} index Position of the first node to change.
  259. * @param {Number} number Number of nodes to change.
  260. * @param {String} key Attribute key to change.
  261. * @param {*} [attribute] Attribute value or null if attribute with given key should be removed.
  262. */
  263. setAttribute( index, number, key, value ) {
  264. if ( index < 0 || index + number > this.length ) {
  265. /**
  266. * Trying to set attribute on non-existing node list items.
  267. *
  268. * @error nodelist-setattribute-out-of-bounds
  269. * @param root
  270. */
  271. throw new CKEditorError( 'nodelist-setattribute-out-of-bounds: Trying to set attribute on non-existing node list items.' );
  272. }
  273. // "Range" of nodes to remove attributes may start in NodeListText or end in NodeListText. Some splitting may be needed.
  274. this._splitNodeAt( index );
  275. this._splitNodeAt( index + number );
  276. let i = index;
  277. while ( i < index + number ) {
  278. let node = this._nodes[ this._indexMap[ i ] ];
  279. if ( node instanceof NodeListText ) {
  280. if ( value !== null ) {
  281. node._attrs.set( key, value );
  282. } else {
  283. node._attrs.delete( key );
  284. }
  285. this._mergeNodeAt( i );
  286. i += node.text.length;
  287. } else {
  288. if ( value !== null ) {
  289. node.setAttribute( key, value );
  290. } else {
  291. node.removeAttribute( key );
  292. }
  293. i++;
  294. }
  295. }
  296. this._mergeNodeAt( index + number );
  297. }
  298. /**
  299. * Checks whether given index is inside a text and if so, splits that text node. This method should be used
  300. * to split text objects whenever there are some changes made on a part of text object (i.e. removing part of text,
  301. * inserting between text object, changing attributes of part of a text object).
  302. *
  303. * @param {Number} index Index in the node list at which node should be broken.
  304. * @protected
  305. */
  306. _splitNodeAt( index ) {
  307. if ( this._indexMap[ index ] != this._indexMap[ index - 1 ] || this._indexMap.length === 0 ) {
  308. // Node before and node after splitting point are already different.
  309. // Or the node list is empty.
  310. // No splitting is needed.
  311. return;
  312. }
  313. let realIndex = this._indexMap[ index ];
  314. let node = this._nodes[ realIndex ];
  315. // Get position in the text node where the text should be split.
  316. let charIndex = this._getCharIndex( index );
  317. // Get text part before and after split point.
  318. let textBefore = node.text.substr( 0, charIndex );
  319. let textAfter = node.text.substr( charIndex );
  320. // "Remove" part after split point from current text node.
  321. node.text = textBefore;
  322. // Create a new text node with the "removed" part and splice it after original node.
  323. let newText = new NodeListText( textAfter, node._attrs );
  324. newText.parent = node.parent;
  325. this._nodes.splice.call( this._nodes, realIndex + 1, 0, newText );
  326. // We added new element in the middle of _nodes what invalidated _indexMap. We have to fix it.
  327. for ( let i = index; i < this._indexMap.length; i++ ) {
  328. this._indexMap[ i ]++;
  329. }
  330. }
  331. /**
  332. * Checks whether given index is between two text nodes that have same attributes and if so, merges them
  333. * together into one node. Used to compress characters into large text objects and use less memory. This method
  334. * should be used whenever there are some changed done to the node list to check whether it is possible to merge
  335. * text objects.
  336. *
  337. * @param {Number} index Index in the node list at which node should be merged.
  338. * @protected
  339. */
  340. _mergeNodeAt( index ) {
  341. if ( this._indexMap[ index ] == this._indexMap[ index - 1 ] || this._indexMap.length === 0 ) {
  342. // Node before and node after splitting point are already same.
  343. // Or the node list is empty.
  344. // No splitting is needed.
  345. return;
  346. }
  347. // Get the node before and after given index.
  348. let realIndexBefore = this._indexMap[ index - 1 ];
  349. let realIndexAfter = this._indexMap[ index ];
  350. let nodeBefore = this._nodes[ realIndexBefore ];
  351. let nodeAfter = this._nodes[ realIndexAfter ];
  352. // Check if both of those nodes are text objects with same attributes.
  353. if ( nodeBefore instanceof NodeListText && nodeAfter instanceof NodeListText && utils.mapsEqual( nodeBefore._attrs, nodeAfter._attrs ) ) {
  354. // Append text of text node after index to the before one.
  355. nodeBefore.text += nodeAfter.text;
  356. // Remove text node after index.
  357. this._nodes.splice( realIndexAfter, 1 );
  358. for ( let i = index; i < this._indexMap.length ; i++ ) {
  359. this._indexMap[ i ]--;
  360. }
  361. }
  362. }
  363. /**
  364. * Helper function that takes an index in a node list that is inside a text node and returns the offset of that
  365. * index from the beginning of that text node. If index
  366. *
  367. * @param index
  368. * @returns {Number} Offset of given index from the beginning of the text node.
  369. * @private
  370. */
  371. _getCharIndex( index ) {
  372. return index - this._indexMap.indexOf( this._indexMap[ index ] );
  373. }
  374. }
  375. /**
  376. * Value that is convertible to an item kept in {@link core.treeModel.NodeList} or an iterable collection of such items.
  377. * In other words, this is anything that {@link core.treeModel.NodeList#constructor} is able to take and convert to node:
  378. * * {@link core.treeModel.Element} will be left as is
  379. * * {@link core.treeModel.CharacterProxy} will be left as is
  380. * * {@link core.treeModel.Text} and {String} will be converted to a set of {@link core.treeModel.CharacterProxy}
  381. * * {@link core.treeModel.NodeList} will clone a node list (but not the nodes inside, so the new and passed list will
  382. * point to the same nodes.
  383. * * Iterable collection of above items will be iterated over and all items will be added to the node list.
  384. *
  385. * @typedef {treeModel.Element|treeModel.CharacterProxy|treeModel.Text|String|treeModel.NodeList|Iterable} core.treeModel.NodeSet
  386. */