treewalker.js 17 KB

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