8
0

treewalker.js 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646
  1. /**
  2. * @license Copyright (c) 2003-2016, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. /* bender-tags: model */
  6. 'use strict';
  7. import Document from '/ckeditor5/engine/model/document.js';
  8. import Element from '/ckeditor5/engine/model/element.js';
  9. import Text from '/ckeditor5/engine/model/text.js';
  10. import TreeWalker from '/ckeditor5/engine/model/treewalker.js';
  11. import Position from '/ckeditor5/engine/model/position.js';
  12. import Range from '/ckeditor5/engine/model/range.js';
  13. import CKEditorError from '/ckeditor5/utils/ckeditorerror.js';
  14. describe( 'TreeWalker', () => {
  15. let doc, root, img1, paragraph, b, a, r, img2, x;
  16. let rootBeginning, rootEnding;
  17. before( () => {
  18. doc = new Document();
  19. root = doc.createRoot( 'root' );
  20. // root
  21. // |- img1
  22. // |- p
  23. // |- B -bold
  24. // |- A -bold
  25. // |- R
  26. // |
  27. // |- img2
  28. // |
  29. // |- X
  30. b = new Text( 'b', { bold: true } );
  31. a = new Text( 'a', { bold: true } );
  32. r = new Text( 'r' );
  33. img2 = new Element( 'img2' );
  34. x = new Text( 'x' );
  35. paragraph = new Element( 'p', [], [ b, a, r, img2, x ] );
  36. img1 = new Element( 'img1' );
  37. root.insertChildren( 0, [ img1, paragraph ] );
  38. rootBeginning = new Position( root, [ 0 ] );
  39. rootEnding = new Position( root, [ 2 ] );
  40. } );
  41. describe( 'constructor', () => {
  42. it( 'should throw if neither boundaries nor starting position is set', () => {
  43. expect( () => {
  44. new TreeWalker();
  45. } ).to.throw( CKEditorError, /^tree-walker-no-start-position/ );
  46. expect( () => {
  47. new TreeWalker( {} );
  48. } ).to.throw( CKEditorError, /^tree-walker-no-start-position/ );
  49. expect( () => {
  50. new TreeWalker( { singleCharacters: true } );
  51. } ).to.throw( CKEditorError, /^tree-walker-no-start-position/ );
  52. } );
  53. it( 'should throw if walking direction is unknown', () => {
  54. expect( () => {
  55. new TreeWalker( { startPosition: rootBeginning, direction: 'UNKNOWN' } );
  56. } ).to.throw( CKEditorError, /^tree-walker-unknown-direction/ );
  57. } );
  58. } );
  59. describe( 'iterate from start position `startPosition`', () => {
  60. let expected;
  61. beforeEach( () => {
  62. expected = [
  63. { type: 'ELEMENT_START', item: img1 },
  64. { type: 'ELEMENT_END', item: img1 },
  65. { type: 'ELEMENT_START', item: paragraph },
  66. { type: 'TEXT', text: 'ba', attrs: [ [ 'bold', true ] ] },
  67. { type: 'TEXT', text: 'r', attrs: [] },
  68. { type: 'ELEMENT_START', item: img2 },
  69. { type: 'ELEMENT_END', item: img2 },
  70. { type: 'TEXT', text: 'x', attrs: [] },
  71. { type: 'ELEMENT_END', item: paragraph }
  72. ];
  73. } );
  74. it( 'should provide iterator interface with default FORWARD direction', () => {
  75. let iterator = new TreeWalker( { startPosition: rootBeginning } );
  76. let i = 0;
  77. for ( let value of iterator ) {
  78. expectValue( value, expected[ i ] );
  79. i++;
  80. }
  81. expect( i ).to.equal( expected.length );
  82. } );
  83. it( 'should provide iterator interface with FORWARD direction', () => {
  84. let iterator = new TreeWalker( { startPosition: rootBeginning, direction: 'FORWARD' } );
  85. let i = 0;
  86. for ( let value of iterator ) {
  87. expectValue( value, expected[ i ] );
  88. i++;
  89. }
  90. expect( i ).to.equal( expected.length );
  91. } );
  92. it( 'should provide iterator interface which BACKWARD direction', () => {
  93. let iterator = new TreeWalker( { startPosition: rootEnding, direction: 'BACKWARD' } );
  94. let i = expected.length;
  95. for ( let value of iterator ) {
  96. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  97. }
  98. expect( i ).to.equal( 0 );
  99. } );
  100. it( 'should throw if walking direction is unknown', () => {
  101. let iterator = new TreeWalker( { startPosition: rootEnding } );
  102. iterator.direction = 'UNKNOWN';
  103. expect( () => {
  104. iterator.next();
  105. } ).to.throw( CKEditorError, /^tree-walker-unknown-direction/ );
  106. } );
  107. it( 'should start iterating at the startPosition witch is not a root bound', () => {
  108. let iterator = new TreeWalker( { startPosition: new Position( root, [ 1 ] ) } );
  109. let i = 2;
  110. for ( let value of iterator ) {
  111. expectValue( value, expected[ i ] );
  112. i++;
  113. }
  114. expect( i ).to.equal( expected.length );
  115. } );
  116. it( 'should start iterating at the startPosition witch is not a root bound, going backward', () => {
  117. let expected = [
  118. { type: 'ELEMENT_START', item: img1 },
  119. { type: 'ELEMENT_END', item: img1 }
  120. ];
  121. let iterator = new TreeWalker( { startPosition: new Position( root, [ 1 ] ), direction: 'BACKWARD' } );
  122. let i = expected.length;
  123. for ( let value of iterator ) {
  124. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  125. }
  126. expect( i ).to.equal( 0 );
  127. } );
  128. } );
  129. describe( 'iterate trough the range `boundary`', () => {
  130. describe( 'range starts between elements', () => {
  131. let expected, range;
  132. before( () => {
  133. expected = [
  134. { type: 'ELEMENT_START', item: paragraph },
  135. { type: 'TEXT', text: 'ba', attrs: [ [ 'bold', true ] ] },
  136. { type: 'TEXT', text: 'r', attrs: [] },
  137. { type: 'ELEMENT_START', item: img2 },
  138. { type: 'ELEMENT_END', item: img2 }
  139. ];
  140. range = new Range( new Position( root, [ 1 ] ), new Position( root, [ 1, 4 ] ) );
  141. } );
  142. it( 'should iterating over the range', () => {
  143. let iterator = new TreeWalker( { boundaries: range } );
  144. let i = 0;
  145. for ( let value of iterator ) {
  146. expectValue( value, expected[ i ] );
  147. i++;
  148. }
  149. expect( i ).to.equal( expected.length );
  150. } );
  151. it( 'should iterating over the range going backward', () => {
  152. let iterator = new TreeWalker( { boundaries: range, direction: 'BACKWARD' } );
  153. let i = expected.length;
  154. for ( let value of iterator ) {
  155. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  156. }
  157. expect( i ).to.equal( 0 );
  158. } );
  159. } );
  160. describe( 'range starts inside the text', () => {
  161. let expected, range;
  162. before( () => {
  163. expected = [
  164. { type: 'TEXT', text: 'a', attrs: [ [ 'bold', true ] ] },
  165. { type: 'TEXT', text: 'r', attrs: [] },
  166. { type: 'ELEMENT_START', item: img2 },
  167. { type: 'ELEMENT_END', item: img2 }
  168. ];
  169. range = new Range( new Position( root, [ 1, 1 ] ), new Position( root, [ 1, 4 ] ) );
  170. } );
  171. it( 'should return part of the text', () => {
  172. let iterator = new TreeWalker( { boundaries: range } );
  173. let i = 0;
  174. for ( let value of iterator ) {
  175. expectValue( value, expected[ i ] );
  176. i++;
  177. }
  178. expect( i ).to.equal( expected.length );
  179. } );
  180. it( 'should return part of the text going backward', () => {
  181. let iterator = new TreeWalker( {
  182. boundaries: range,
  183. direction: 'BACKWARD' }
  184. );
  185. let i = expected.length;
  186. for ( let value of iterator ) {
  187. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  188. }
  189. expect( i ).to.equal( 0 );
  190. } );
  191. } );
  192. describe( 'range ends inside the text', () => {
  193. let expected, range;
  194. before( () => {
  195. expected = [
  196. { type: 'ELEMENT_START', item: img1 },
  197. { type: 'ELEMENT_END', item: img1 },
  198. { type: 'ELEMENT_START', item: paragraph },
  199. { type: 'TEXT', text: 'b', attrs: [ [ 'bold', true ] ] }
  200. ];
  201. range = new Range( rootBeginning, new Position( root, [ 1, 1 ] ) );
  202. } );
  203. it( 'should return part of the text', () => {
  204. let iterator = new TreeWalker( { boundaries: range } );
  205. let i = 0;
  206. for ( let value of iterator ) {
  207. expectValue( value, expected[ i ] );
  208. i++;
  209. }
  210. expect( i ).to.equal( expected.length );
  211. } );
  212. it( 'should return part of the text going backward', () => {
  213. let iterator = new TreeWalker( {
  214. boundaries: range,
  215. startPosition: range.end,
  216. direction: 'BACKWARD'
  217. } );
  218. let i = expected.length;
  219. for ( let value of iterator ) {
  220. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  221. }
  222. expect( i ).to.equal( 0 );
  223. } );
  224. } );
  225. describe( 'custom start position', () => {
  226. it( 'should iterating from the start position', () => {
  227. let expected = [
  228. { type: 'TEXT', text: 'r', attrs: [] },
  229. { type: 'ELEMENT_START', item: img2 },
  230. { type: 'ELEMENT_END', item: img2 }
  231. ];
  232. let range = new Range( new Position( root, [ 1 ] ), new Position( root, [ 1, 4 ] ) );
  233. let iterator = new TreeWalker( {
  234. boundaries: range,
  235. startPosition: new Position( root, [ 1, 2 ] )
  236. } );
  237. let i = 0;
  238. for ( let value of iterator ) {
  239. expectValue( value, expected[ i ] );
  240. i++;
  241. }
  242. expect( i ).to.equal( expected.length );
  243. } );
  244. it( 'should iterating from the start position going backward', () => {
  245. let expected = [
  246. { type: 'TEXT', text: 'r', attrs: [] },
  247. { type: 'ELEMENT_START', item: img2 },
  248. { type: 'ELEMENT_END', item: img2 }
  249. ];
  250. let range = new Range( new Position( root, [ 1, 2 ] ), new Position( root, [ 1, 6 ] ) );
  251. let iterator = new TreeWalker( {
  252. boundaries: range,
  253. startPosition: new Position( root, [ 1, 4 ] ),
  254. direction: 'BACKWARD'
  255. } );
  256. let i = expected.length;
  257. for ( let value of iterator ) {
  258. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  259. }
  260. expect( i ).to.equal( 0 );
  261. } );
  262. } );
  263. } );
  264. describe( 'iterate by every single characters `singleCharacter`', () => {
  265. describe( 'whole root', () => {
  266. let expected;
  267. before( () => {
  268. expected = [
  269. { type: 'ELEMENT_START', item: img1 },
  270. { type: 'ELEMENT_END', item: img1 },
  271. { type: 'ELEMENT_START', item: paragraph },
  272. { type: 'CHARACTER', text: 'b', attrs: [ [ 'bold', true ] ] },
  273. { type: 'CHARACTER', text: 'a', attrs: [ [ 'bold', true ] ] },
  274. { type: 'CHARACTER', text: 'r', attrs: [] },
  275. { type: 'ELEMENT_START', item: img2 },
  276. { type: 'ELEMENT_END', item: img2 },
  277. { type: 'CHARACTER', text: 'x', attrs: [] },
  278. { type: 'ELEMENT_END', item: paragraph }
  279. ];
  280. } );
  281. it( 'should return single characters', () => {
  282. let iterator = new TreeWalker( { startPosition: rootBeginning, singleCharacters: true } );
  283. let i = 0;
  284. for ( let value of iterator ) {
  285. expectValue( value, expected[ i ] );
  286. i++;
  287. }
  288. expect( i ).to.equal( expected.length );
  289. } );
  290. it( 'should return single characters going backward', () => {
  291. let iterator = new TreeWalker( {
  292. startPosition: rootEnding,
  293. singleCharacters: true,
  294. direction: 'BACKWARD' }
  295. );
  296. let i = expected.length;
  297. for ( let value of iterator ) {
  298. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  299. }
  300. expect( i ).to.equal( 0 );
  301. } );
  302. } );
  303. describe( 'range', () => {
  304. let start, end, range, expected;
  305. before( () => {
  306. expected = [
  307. { type: 'CHARACTER', text: 'b', attrs: [ [ 'bold', true ] ] },
  308. { type: 'CHARACTER', text: 'a', attrs: [ [ 'bold', true ] ] },
  309. { type: 'CHARACTER', text: 'r', attrs: [] },
  310. { type: 'ELEMENT_START', item: img2 }
  311. ];
  312. start = new Position( root, [ 1, 0 ] ); // p, 0
  313. end = new Position( root, [ 1, 3, 0 ] ); // img2, 0
  314. range = new Range( start, end );
  315. } );
  316. it( 'should respect boundaries', () => {
  317. let iterator = new TreeWalker( { boundaries: range, singleCharacters: true } );
  318. let i = 0;
  319. for ( let value of iterator ) {
  320. expectValue( value, expected[ i ] );
  321. i++;
  322. }
  323. expect( i ).to.equal( expected.length );
  324. } );
  325. it( 'should respect boundaries going backward', () => {
  326. let iterator = new TreeWalker( {
  327. boundaries: range,
  328. singleCharacters: true,
  329. startPosition: range.end,
  330. direction: 'BACKWARD'
  331. } );
  332. let i = expected.length;
  333. for ( let value of iterator ) {
  334. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  335. }
  336. expect( i ).to.equal( 0 );
  337. } );
  338. } );
  339. } );
  340. describe( 'iterate omitting child nodes and ELEMENT_END `shallow`', () => {
  341. let expected;
  342. before( () => {
  343. expected = [
  344. { type: 'ELEMENT_START', item: img1 },
  345. { type: 'ELEMENT_START', item: paragraph }
  346. ];
  347. } );
  348. it( 'should not enter elements', () => {
  349. let iterator = new TreeWalker( { startPosition: rootBeginning, shallow: true } );
  350. let i = 0;
  351. for ( let value of iterator ) {
  352. expectValue( value, expected[ i ], { shallow: true } );
  353. i++;
  354. }
  355. expect( i ).to.equal( expected.length );
  356. } );
  357. it( 'should not enter elements going backward', () => {
  358. let iterator = new TreeWalker( { startPosition: rootEnding, shallow: true, direction: 'BACKWARD' } );
  359. let i = expected.length;
  360. for ( let value of iterator ) {
  361. expectValue( value, expected[ --i ], { shallow: true, direction: 'BACKWARD' } );
  362. }
  363. expect( i ).to.equal( 0 );
  364. } );
  365. } );
  366. describe( 'iterate omitting ELEMENT_END `ignoreElementEnd`', () => {
  367. describe( 'merged text', () => {
  368. let expected;
  369. before( () => {
  370. expected = [
  371. { type: 'ELEMENT_START', item: img1 },
  372. { type: 'ELEMENT_START', item: paragraph },
  373. { type: 'TEXT', text: 'ba', attrs: [ [ 'bold', true ] ] },
  374. { type: 'TEXT', text: 'r', attrs: [] },
  375. { type: 'ELEMENT_START', item: img2 },
  376. { type: 'TEXT', text: 'x', attrs: [] }
  377. ];
  378. } );
  379. it( 'should iterate ignoring ELEMENT_END', () => {
  380. let iterator = new TreeWalker( { startPosition: rootBeginning, ignoreElementEnd: true } );
  381. let i = 0;
  382. for ( let value of iterator ) {
  383. expectValue( value, expected[ i ] );
  384. i++;
  385. }
  386. expect( i ).to.equal( expected.length );
  387. } );
  388. it( 'should iterate ignoring ELEMENT_END going backward', () => {
  389. let iterator = new TreeWalker( {
  390. startPosition: rootEnding,
  391. ignoreElementEnd: true,
  392. direction: 'BACKWARD'
  393. } );
  394. let i = expected.length;
  395. for ( let value of iterator ) {
  396. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  397. }
  398. expect( i ).to.equal( 0 );
  399. } );
  400. } );
  401. describe( 'single character', () => {
  402. let expected;
  403. before( () => {
  404. expected = [
  405. { type: 'ELEMENT_START', item: img1 },
  406. { type: 'ELEMENT_START', item: paragraph },
  407. { type: 'CHARACTER', text: 'b', attrs: [ [ 'bold', true ] ] },
  408. { type: 'CHARACTER', text: 'a', attrs: [ [ 'bold', true ] ] },
  409. { type: 'CHARACTER', text: 'r', attrs: [] },
  410. { type: 'ELEMENT_START', item: img2 },
  411. { type: 'CHARACTER', text: 'x', attrs: [] }
  412. ];
  413. } );
  414. it( 'should return single characters ignoring ELEMENT_END', () => {
  415. let iterator = new TreeWalker( {
  416. startPosition: rootBeginning,
  417. singleCharacters: true,
  418. ignoreElementEnd: true
  419. } );
  420. let i = 0;
  421. for ( let value of iterator ) {
  422. expectValue( value, expected[ i ] );
  423. i++;
  424. }
  425. expect( i ).to.equal( expected.length );
  426. } );
  427. it( 'should return single characters ignoring ELEMENT_END going backward', () => {
  428. let iterator = new TreeWalker( {
  429. startPosition: rootEnding,
  430. singleCharacters: true,
  431. ignoreElementEnd: true,
  432. direction: 'BACKWARD'
  433. } );
  434. let i = expected.length;
  435. for ( let value of iterator ) {
  436. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  437. }
  438. expect( i ).to.equal( 0 );
  439. } );
  440. } );
  441. } );
  442. } );
  443. function expectValue( value, expected, options ) {
  444. expect( value.type ).to.equal( expected.type );
  445. if ( value.type == 'TEXT' ) {
  446. expectText( value, expected, options );
  447. } else if ( value.type == 'CHARACTER' ) {
  448. expectCharacter( value, expected, options );
  449. } else if ( value.type == 'ELEMENT_START' ) {
  450. expectStart( value, expected, options );
  451. } else if ( value.type == 'ELEMENT_END' ) {
  452. expectEnd( value, expected, options );
  453. }
  454. }
  455. function expectText( value, expected, options = {} ) {
  456. let previousPosition, nextPosition;
  457. expect( value.item.text ).to.equal( expected.text );
  458. expect( Array.from( value.item.first._attrs ) ).to.deep.equal( expected.attrs );
  459. expect( value.length ).to.equal( value.item.text.length );
  460. if ( options.direction == 'BACKWARD' ) {
  461. previousPosition = Position.createAfter( value.item.last );
  462. nextPosition = Position.createBefore( value.item.first );
  463. } else {
  464. previousPosition = Position.createBefore( value.item.first );
  465. nextPosition = Position.createAfter( value.item.last );
  466. }
  467. expect( value.previousPosition ).to.deep.equal( previousPosition );
  468. expect( value.nextPosition ).to.deep.equal( nextPosition );
  469. }
  470. function expectCharacter( value, expected, options = {} ) {
  471. let previousPosition, nextPosition;
  472. expect( value.item.character ).to.equal( expected.text );
  473. expect( Array.from( value.item._attrs ) ).to.deep.equal( expected.attrs );
  474. expect( value.length ).to.equal( value.item.character.length );
  475. if ( options.direction == 'BACKWARD' ) {
  476. previousPosition = Position.createAfter( value.item );
  477. nextPosition = Position.createBefore( value.item );
  478. } else {
  479. previousPosition = Position.createBefore( value.item );
  480. nextPosition = Position.createAfter( value.item );
  481. }
  482. expect( value.previousPosition ).to.deep.equal( previousPosition );
  483. expect( value.nextPosition ).to.deep.equal( nextPosition );
  484. }
  485. function expectStart( value, expected, options = {} ) {
  486. let previousPosition, nextPosition;
  487. expect( value.item ).to.equal( expected.item );
  488. expect( value.length ).to.equal( 1 );
  489. if ( options.direction == 'BACKWARD' ) {
  490. previousPosition = Position.createAfter( value.item );
  491. nextPosition = Position.createBefore( value.item );
  492. } else {
  493. previousPosition = Position.createBefore( value.item );
  494. nextPosition = Position.createFromParentAndOffset( value.item, 0 );
  495. }
  496. if ( options.shallow ) {
  497. expect( value.previousPosition ).to.deep.equal( previousPosition );
  498. } else {
  499. expect( value.nextPosition ).to.deep.equal( nextPosition );
  500. }
  501. }
  502. function expectEnd( value, expected, options = {} ) {
  503. let previousPosition, nextPosition;
  504. expect( value.item ).to.equal( expected.item );
  505. expect( value.length ).to.be.undefined;
  506. if ( options.direction == 'BACKWARD' ) {
  507. previousPosition = Position.createAfter( value.item );
  508. nextPosition = Position.createFromParentAndOffset( value.item, value.item.getChildCount() );
  509. } else {
  510. previousPosition = Position.createFromParentAndOffset( value.item, value.item.getChildCount() );
  511. nextPosition = Position.createAfter( value.item );
  512. }
  513. expect( value.previousPosition ).to.deep.equal( previousPosition );
  514. expect( value.nextPosition ).to.deep.equal( nextPosition );
  515. }