nodelist.js 15 KB

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