8
0

treewalker.js 17 KB

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