8
0

treewalker.js 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636
  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();
  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: 'elementStart', item: img1 },
  64. { type: 'elementEnd', item: img1 },
  65. { type: 'elementStart', item: paragraph },
  66. { type: 'text', text: 'ba', attrs: [ [ 'bold', true ] ] },
  67. { type: 'text', text: 'r', attrs: [] },
  68. { type: 'elementStart', item: img2 },
  69. { type: 'elementEnd', item: img2 },
  70. { type: 'text', text: 'x', attrs: [] },
  71. { type: 'elementEnd', 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 start iterating at the startPosition witch is not a root bound', () => {
  101. let iterator = new TreeWalker( { startPosition: new Position( root, [ 1 ] ) } );
  102. let i = 2;
  103. for ( let value of iterator ) {
  104. expectValue( value, expected[ i ] );
  105. i++;
  106. }
  107. expect( i ).to.equal( expected.length );
  108. } );
  109. it( 'should start iterating at the startPosition witch is not a root bound, going backward', () => {
  110. let expected = [
  111. { type: 'elementStart', item: img1 },
  112. { type: 'elementEnd', item: img1 }
  113. ];
  114. let iterator = new TreeWalker( { startPosition: new Position( root, [ 1 ] ), direction: 'BACKWARD' } );
  115. let i = expected.length;
  116. for ( let value of iterator ) {
  117. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  118. }
  119. expect( i ).to.equal( 0 );
  120. } );
  121. } );
  122. describe( 'iterate trough the range `boundary`', () => {
  123. describe( 'range starts between elements', () => {
  124. let expected, range;
  125. before( () => {
  126. expected = [
  127. { type: 'elementStart', item: paragraph },
  128. { type: 'text', text: 'ba', attrs: [ [ 'bold', true ] ] },
  129. { type: 'text', text: 'r', attrs: [] },
  130. { type: 'elementStart', item: img2 },
  131. { type: 'elementEnd', item: img2 }
  132. ];
  133. range = new Range( new Position( root, [ 1 ] ), new Position( root, [ 1, 4 ] ) );
  134. } );
  135. it( 'should iterating over the range', () => {
  136. let iterator = new TreeWalker( { boundaries: range } );
  137. let i = 0;
  138. for ( let value of iterator ) {
  139. expectValue( value, expected[ i ] );
  140. i++;
  141. }
  142. expect( i ).to.equal( expected.length );
  143. } );
  144. it( 'should iterating over the range going backward', () => {
  145. let iterator = new TreeWalker( { boundaries: range, direction: 'BACKWARD' } );
  146. let i = expected.length;
  147. for ( let value of iterator ) {
  148. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  149. }
  150. expect( i ).to.equal( 0 );
  151. } );
  152. } );
  153. describe( 'range starts inside the text', () => {
  154. let expected, range;
  155. before( () => {
  156. expected = [
  157. { type: 'text', text: 'a', attrs: [ [ 'bold', true ] ] },
  158. { type: 'text', text: 'r', attrs: [] },
  159. { type: 'elementStart', item: img2 },
  160. { type: 'elementEnd', item: img2 }
  161. ];
  162. range = new Range( new Position( root, [ 1, 1 ] ), new Position( root, [ 1, 4 ] ) );
  163. } );
  164. it( 'should return part of the text', () => {
  165. let iterator = new TreeWalker( { boundaries: range } );
  166. let i = 0;
  167. for ( let value of iterator ) {
  168. expectValue( value, expected[ i ] );
  169. i++;
  170. }
  171. expect( i ).to.equal( expected.length );
  172. } );
  173. it( 'should return part of the text going backward', () => {
  174. let iterator = new TreeWalker( {
  175. boundaries: range,
  176. direction: 'BACKWARD' }
  177. );
  178. let i = expected.length;
  179. for ( let value of iterator ) {
  180. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  181. }
  182. expect( i ).to.equal( 0 );
  183. } );
  184. } );
  185. describe( 'range ends inside the text', () => {
  186. let expected, range;
  187. before( () => {
  188. expected = [
  189. { type: 'elementStart', item: img1 },
  190. { type: 'elementEnd', item: img1 },
  191. { type: 'elementStart', item: paragraph },
  192. { type: 'text', text: 'b', attrs: [ [ 'bold', true ] ] }
  193. ];
  194. range = new Range( rootBeginning, new Position( root, [ 1, 1 ] ) );
  195. } );
  196. it( 'should return part of the text', () => {
  197. let iterator = new TreeWalker( { boundaries: range } );
  198. let i = 0;
  199. for ( let value of iterator ) {
  200. expectValue( value, expected[ i ] );
  201. i++;
  202. }
  203. expect( i ).to.equal( expected.length );
  204. } );
  205. it( 'should return part of the text going backward', () => {
  206. let iterator = new TreeWalker( {
  207. boundaries: range,
  208. startPosition: range.end,
  209. direction: 'BACKWARD'
  210. } );
  211. let i = expected.length;
  212. for ( let value of iterator ) {
  213. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  214. }
  215. expect( i ).to.equal( 0 );
  216. } );
  217. } );
  218. describe( 'custom start position', () => {
  219. it( 'should iterating from the start position', () => {
  220. let expected = [
  221. { type: 'text', text: 'r', attrs: [] },
  222. { type: 'elementStart', item: img2 },
  223. { type: 'elementEnd', item: img2 }
  224. ];
  225. let range = new Range( new Position( root, [ 1 ] ), new Position( root, [ 1, 4 ] ) );
  226. let iterator = new TreeWalker( {
  227. boundaries: range,
  228. startPosition: new Position( root, [ 1, 2 ] )
  229. } );
  230. let i = 0;
  231. for ( let value of iterator ) {
  232. expectValue( value, expected[ i ] );
  233. i++;
  234. }
  235. expect( i ).to.equal( expected.length );
  236. } );
  237. it( 'should iterating from the start position going backward', () => {
  238. let expected = [
  239. { type: 'text', text: 'r', attrs: [] },
  240. { type: 'elementStart', item: img2 },
  241. { type: 'elementEnd', item: img2 }
  242. ];
  243. let range = new Range( new Position( root, [ 1, 2 ] ), new Position( root, [ 1, 6 ] ) );
  244. let iterator = new TreeWalker( {
  245. boundaries: range,
  246. startPosition: new Position( root, [ 1, 4 ] ),
  247. direction: 'BACKWARD'
  248. } );
  249. let i = expected.length;
  250. for ( let value of iterator ) {
  251. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  252. }
  253. expect( i ).to.equal( 0 );
  254. } );
  255. } );
  256. } );
  257. describe( 'iterate by every single characters `singleCharacter`', () => {
  258. describe( 'whole root', () => {
  259. let expected;
  260. before( () => {
  261. expected = [
  262. { type: 'elementStart', item: img1 },
  263. { type: 'elementEnd', item: img1 },
  264. { type: 'elementStart', item: paragraph },
  265. { type: 'CHARACTER', text: 'b', attrs: [ [ 'bold', true ] ] },
  266. { type: 'CHARACTER', text: 'a', attrs: [ [ 'bold', true ] ] },
  267. { type: 'CHARACTER', text: 'r', attrs: [] },
  268. { type: 'elementStart', item: img2 },
  269. { type: 'elementEnd', item: img2 },
  270. { type: 'CHARACTER', text: 'x', attrs: [] },
  271. { type: 'elementEnd', item: paragraph }
  272. ];
  273. } );
  274. it( 'should return single characters', () => {
  275. let iterator = new TreeWalker( { startPosition: rootBeginning, singleCharacters: true } );
  276. let i = 0;
  277. for ( let value of iterator ) {
  278. expectValue( value, expected[ i ] );
  279. i++;
  280. }
  281. expect( i ).to.equal( expected.length );
  282. } );
  283. it( 'should return single characters going backward', () => {
  284. let iterator = new TreeWalker( {
  285. startPosition: rootEnding,
  286. singleCharacters: true,
  287. direction: 'BACKWARD' }
  288. );
  289. let i = expected.length;
  290. for ( let value of iterator ) {
  291. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  292. }
  293. expect( i ).to.equal( 0 );
  294. } );
  295. } );
  296. describe( 'range', () => {
  297. let start, end, range, expected;
  298. before( () => {
  299. expected = [
  300. { type: 'CHARACTER', text: 'b', attrs: [ [ 'bold', true ] ] },
  301. { type: 'CHARACTER', text: 'a', attrs: [ [ 'bold', true ] ] },
  302. { type: 'CHARACTER', text: 'r', attrs: [] },
  303. { type: 'elementStart', item: img2 }
  304. ];
  305. start = new Position( root, [ 1, 0 ] ); // p, 0
  306. end = new Position( root, [ 1, 3, 0 ] ); // img2, 0
  307. range = new Range( start, end );
  308. } );
  309. it( 'should respect boundaries', () => {
  310. let iterator = new TreeWalker( { boundaries: range, singleCharacters: true } );
  311. let i = 0;
  312. for ( let value of iterator ) {
  313. expectValue( value, expected[ i ] );
  314. i++;
  315. }
  316. expect( i ).to.equal( expected.length );
  317. } );
  318. it( 'should respect boundaries going backward', () => {
  319. let iterator = new TreeWalker( {
  320. boundaries: range,
  321. singleCharacters: true,
  322. startPosition: range.end,
  323. direction: 'BACKWARD'
  324. } );
  325. let i = expected.length;
  326. for ( let value of iterator ) {
  327. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  328. }
  329. expect( i ).to.equal( 0 );
  330. } );
  331. } );
  332. } );
  333. describe( 'iterate omitting child nodes and elementEnd `shallow`', () => {
  334. let expected;
  335. before( () => {
  336. expected = [
  337. { type: 'elementStart', item: img1 },
  338. { type: 'elementStart', item: paragraph }
  339. ];
  340. } );
  341. it( 'should not enter elements', () => {
  342. let iterator = new TreeWalker( { startPosition: rootBeginning, shallow: true } );
  343. let i = 0;
  344. for ( let value of iterator ) {
  345. expectValue( value, expected[ i ], { shallow: true } );
  346. i++;
  347. }
  348. expect( i ).to.equal( expected.length );
  349. } );
  350. it( 'should not enter elements going backward', () => {
  351. let iterator = new TreeWalker( { startPosition: rootEnding, shallow: true, direction: 'BACKWARD' } );
  352. let i = expected.length;
  353. for ( let value of iterator ) {
  354. expectValue( value, expected[ --i ], { shallow: true, direction: 'BACKWARD' } );
  355. }
  356. expect( i ).to.equal( 0 );
  357. } );
  358. } );
  359. describe( 'iterate omitting elementEnd `ignoreElementEnd`', () => {
  360. describe( 'merged text', () => {
  361. let expected;
  362. before( () => {
  363. expected = [
  364. { type: 'elementStart', item: img1 },
  365. { type: 'elementStart', item: paragraph },
  366. { type: 'text', text: 'ba', attrs: [ [ 'bold', true ] ] },
  367. { type: 'text', text: 'r', attrs: [] },
  368. { type: 'elementStart', item: img2 },
  369. { type: 'text', text: 'x', attrs: [] }
  370. ];
  371. } );
  372. it( 'should iterate ignoring elementEnd', () => {
  373. let iterator = new TreeWalker( { startPosition: rootBeginning, ignoreElementEnd: true } );
  374. let i = 0;
  375. for ( let value of iterator ) {
  376. expectValue( value, expected[ i ] );
  377. i++;
  378. }
  379. expect( i ).to.equal( expected.length );
  380. } );
  381. it( 'should iterate ignoring elementEnd going backward', () => {
  382. let iterator = new TreeWalker( {
  383. startPosition: rootEnding,
  384. ignoreElementEnd: true,
  385. direction: 'BACKWARD'
  386. } );
  387. let i = expected.length;
  388. for ( let value of iterator ) {
  389. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  390. }
  391. expect( i ).to.equal( 0 );
  392. } );
  393. } );
  394. describe( 'single character', () => {
  395. let expected;
  396. before( () => {
  397. expected = [
  398. { type: 'elementStart', item: img1 },
  399. { type: 'elementStart', item: paragraph },
  400. { type: 'CHARACTER', text: 'b', attrs: [ [ 'bold', true ] ] },
  401. { type: 'CHARACTER', text: 'a', attrs: [ [ 'bold', true ] ] },
  402. { type: 'CHARACTER', text: 'r', attrs: [] },
  403. { type: 'elementStart', item: img2 },
  404. { type: 'CHARACTER', text: 'x', attrs: [] }
  405. ];
  406. } );
  407. it( 'should return single characters ignoring elementEnd', () => {
  408. let iterator = new TreeWalker( {
  409. startPosition: rootBeginning,
  410. singleCharacters: true,
  411. ignoreElementEnd: true
  412. } );
  413. let i = 0;
  414. for ( let value of iterator ) {
  415. expectValue( value, expected[ i ] );
  416. i++;
  417. }
  418. expect( i ).to.equal( expected.length );
  419. } );
  420. it( 'should return single characters ignoring elementEnd going backward', () => {
  421. let iterator = new TreeWalker( {
  422. startPosition: rootEnding,
  423. singleCharacters: true,
  424. ignoreElementEnd: true,
  425. direction: 'BACKWARD'
  426. } );
  427. let i = expected.length;
  428. for ( let value of iterator ) {
  429. expectValue( value, expected[ --i ], { direction: 'BACKWARD' } );
  430. }
  431. expect( i ).to.equal( 0 );
  432. } );
  433. } );
  434. } );
  435. } );
  436. function expectValue( value, expected, options ) {
  437. expect( value.type ).to.equal( expected.type );
  438. if ( value.type == 'text' ) {
  439. expectText( value, expected, options );
  440. } else if ( value.type == 'CHARACTER' ) {
  441. expectCharacter( value, expected, options );
  442. } else if ( value.type == 'elementStart' ) {
  443. expectStart( value, expected, options );
  444. } else if ( value.type == 'elementEnd' ) {
  445. expectEnd( value, expected, options );
  446. }
  447. }
  448. function expectText( value, expected, options = {} ) {
  449. let previousPosition, nextPosition;
  450. expect( value.item.text ).to.equal( expected.text );
  451. expect( Array.from( value.item.first._attrs ) ).to.deep.equal( expected.attrs );
  452. expect( value.length ).to.equal( value.item.text.length );
  453. if ( options.direction == 'BACKWARD' ) {
  454. previousPosition = Position.createAfter( value.item.last );
  455. nextPosition = Position.createBefore( value.item.first );
  456. } else {
  457. previousPosition = Position.createBefore( value.item.first );
  458. nextPosition = Position.createAfter( value.item.last );
  459. }
  460. expect( value.previousPosition ).to.deep.equal( previousPosition );
  461. expect( value.nextPosition ).to.deep.equal( nextPosition );
  462. }
  463. function expectCharacter( value, expected, options = {} ) {
  464. let previousPosition, nextPosition;
  465. expect( value.item.character ).to.equal( expected.text );
  466. expect( Array.from( value.item._attrs ) ).to.deep.equal( expected.attrs );
  467. expect( value.length ).to.equal( value.item.character.length );
  468. if ( options.direction == 'BACKWARD' ) {
  469. previousPosition = Position.createAfter( value.item );
  470. nextPosition = Position.createBefore( value.item );
  471. } else {
  472. previousPosition = Position.createBefore( value.item );
  473. nextPosition = Position.createAfter( value.item );
  474. }
  475. expect( value.previousPosition ).to.deep.equal( previousPosition );
  476. expect( value.nextPosition ).to.deep.equal( nextPosition );
  477. }
  478. function expectStart( value, expected, options = {} ) {
  479. let previousPosition, nextPosition;
  480. expect( value.item ).to.equal( expected.item );
  481. expect( value.length ).to.equal( 1 );
  482. if ( options.direction == 'BACKWARD' ) {
  483. previousPosition = Position.createAfter( value.item );
  484. nextPosition = Position.createBefore( value.item );
  485. } else {
  486. previousPosition = Position.createBefore( value.item );
  487. nextPosition = Position.createFromParentAndOffset( value.item, 0 );
  488. }
  489. if ( options.shallow ) {
  490. expect( value.previousPosition ).to.deep.equal( previousPosition );
  491. } else {
  492. expect( value.nextPosition ).to.deep.equal( nextPosition );
  493. }
  494. }
  495. function expectEnd( value, expected, options = {} ) {
  496. let previousPosition, nextPosition;
  497. expect( value.item ).to.equal( expected.item );
  498. expect( value.length ).to.be.undefined;
  499. if ( options.direction == 'BACKWARD' ) {
  500. previousPosition = Position.createAfter( value.item );
  501. nextPosition = Position.createFromParentAndOffset( value.item, value.item.getChildCount() );
  502. } else {
  503. previousPosition = Position.createFromParentAndOffset( value.item, value.item.getChildCount() );
  504. nextPosition = Position.createAfter( value.item );
  505. }
  506. expect( value.previousPosition ).to.deep.equal( previousPosition );
  507. expect( value.nextPosition ).to.deep.equal( nextPosition );
  508. }