22.5 KB651 lines
Blame
1/**
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8// @lint-ignore-every SPELL
9
10import type {CommitInfo, CommitPhaseType, Hash, SuccessorInfo} from '../../types';
11import type {SetLike} from '../set';
12
13import {BaseDag} from '../base_dag';
14import {Dag, DagCommitInfo, REBASE_SUCC_PREFIX} from '../dag';
15import {HashSet} from '../set';
16
17const toInfo = (info: Partial<CommitInfo>): DagCommitInfo => DagCommitInfo.fromCommitInfo(info);
18const DRAFT: CommitPhaseType = 'draft';
19const PUBLIC: CommitPhaseType = 'public';
20
21describe('Dag', () => {
22 // Dummy info.
23 const date = new Date(42);
24 const info: CommitInfo = {
25 title: '',
26 hash: '',
27 parents: [],
28 grandparents: [],
29 phase: DRAFT,
30 isDot: false,
31 author: '',
32 date,
33 description: '',
34 bookmarks: [],
35 remoteBookmarks: [],
36 totalFileCount: 0,
37 filePathsSample: [],
38 maxCommonPathPrefix: '',
39 };
40
41 describe('basic queries', () => {
42 const dagAbc = new BaseDag().add([
43 {hash: 'a', parents: ['z'], grandparents: []},
44 {hash: 'b', parents: ['a'], grandparents: []},
45 {hash: 'c', parents: ['b', 'a'], grandparents: []},
46 ]);
47
48 it('maintains parent<->child mappings', () => {
49 const dag = dagAbc;
50 expect(dag.parentHashes('a')).toEqual([]);
51 expect(dag.parentHashes('b')).toEqual(['a']);
52 expect(dag.parentHashes('c')).toEqual(['b', 'a']);
53 expect(dag.parentHashes('d')).toEqual([]);
54 expect(dag.parentHashes('z')).toEqual([]);
55 expect(dag.childHashes('a').toArray()).toEqual(['b', 'c']);
56 expect(dag.childHashes('b').toArray()).toEqual(['c']);
57 expect(dag.childHashes('c').toArray()).toEqual([]);
58 expect(dag.childHashes('d').toArray()).toEqual([]);
59 expect(dag.childHashes('z').toArray()).toEqual([]);
60 });
61
62 it('maintains parent<->child mappings after remove()', () => {
63 const dag = dagAbc.remove(['b']);
64 expect(dag.parentHashes('c')).toEqual(['a']);
65 expect(dag.childHashes('a').toArray()).toEqual(['c']);
66 expect(dag.parentHashes('b')).toEqual([]);
67 expect(dag.childHashes('b').toArray()).toEqual([]);
68 });
69
70 it('removes conflicted commits', () => {
71 const dag = dagAbc.add([{hash: 'c', parents: [], grandparents: []}]);
72 expect(dag.parentHashes('c')).toEqual([]);
73 expect(dag.childHashes('b').toArray()).toEqual([]);
74 });
75
76 it('supports replaceWith()', () => {
77 const dag = new Dag()
78 .add(
79 [
80 {...info, hash: 'a', parents: ['z']},
81 {...info, hash: 'b', parents: ['a']},
82 {...info, hash: 'c', parents: ['b', 'a']},
83 ].map(toInfo),
84 )
85 .replaceWith(['c', 'd'], (h, _c) =>
86 toInfo({
87 ...info,
88 hash: h,
89 parents: ['b'],
90 }),
91 ).commitDag;
92 expect(dag.parentHashes('c')).toEqual(['b']);
93 expect(dag.parentHashes('d')).toEqual(['b']);
94 expect(dag.childHashes('a').toArray()).toEqual(['b']);
95 expect(dag.childHashes('b').toArray()).toEqual(['c', 'd']);
96 });
97 });
98
99 describe('high-level queries', () => {
100 /**
101 * A--B--C--F
102 * \ /
103 * D-E--G
104 */
105 const dag = new Dag().add(
106 [
107 {...info, hash: 'a', parents: []},
108 {...info, hash: 'b', parents: ['a']},
109 {...info, hash: 'c', parents: ['b']},
110 {...info, hash: 'd', parents: ['b']},
111 {...info, hash: 'e', parents: ['d']},
112 {...info, hash: 'f', parents: ['c', 'e']},
113 {...info, hash: 'g', parents: ['e']},
114 ].map(toInfo),
115 );
116
117 it('parents()', () => {
118 expect(dag.parents('f').toSortedArray()).toEqual(['c', 'e']);
119 expect(dag.parents(['b', 'c', 'f']).toSortedArray()).toEqual(['a', 'b', 'c', 'e']);
120 });
121
122 it('children()', () => {
123 expect(dag.children('b').toSortedArray()).toEqual(['c', 'd']);
124 expect(dag.children(['a', 'b', 'd']).toSortedArray()).toEqual(['b', 'c', 'd', 'e']);
125 });
126
127 it('ancestors()', () => {
128 expect(dag.ancestors('c').toSortedArray()).toEqual(['a', 'b', 'c']);
129 expect(dag.ancestors('f').toSortedArray()).toEqual(['a', 'b', 'c', 'd', 'e', 'f']);
130 expect(dag.ancestors('g').toSortedArray()).toEqual(['a', 'b', 'd', 'e', 'g']);
131 expect(dag.ancestors('f', {within: ['a', 'c', 'd', 'e']}).toSortedArray()).toEqual([
132 'c',
133 'd',
134 'e',
135 'f',
136 ]);
137 });
138
139 it('descendants()', () => {
140 expect(dag.descendants('a').toSortedArray()).toEqual(['a', 'b', 'c', 'd', 'e', 'f', 'g']);
141 expect(dag.descendants('c').toSortedArray()).toEqual(['c', 'f']);
142 expect(dag.descendants('d').toSortedArray()).toEqual(['d', 'e', 'f', 'g']);
143 expect(dag.descendants('b', {within: ['c', 'd', 'g']}).toSortedArray()).toEqual([
144 'b',
145 'c',
146 'd',
147 ]);
148 });
149
150 it('heads()', () => {
151 expect(dag.heads(['a', 'b', 'c']).toSortedArray()).toEqual(['c']);
152 expect(dag.heads(['d', 'e', 'g']).toSortedArray()).toEqual(['g']);
153 expect(dag.heads(['e', 'f', 'g']).toSortedArray()).toEqual(['f', 'g']);
154 expect(dag.heads(['c', 'e', 'f']).toSortedArray()).toEqual(['f']);
155 });
156
157 it('roots()', () => {
158 expect(dag.roots(['a', 'b', 'c']).toSortedArray()).toEqual(['a']);
159 expect(dag.roots(['d', 'e', 'g']).toSortedArray()).toEqual(['d']);
160 expect(dag.roots(['e', 'f', 'g']).toSortedArray()).toEqual(['e']);
161 expect(dag.roots(['c', 'e', 'f']).toSortedArray()).toEqual(['c', 'e']);
162 });
163
164 it('range()', () => {
165 expect(dag.range('a', 'c').toSortedArray()).toEqual(['a', 'b', 'c']);
166 expect(dag.range('a', 'f').toSortedArray()).toEqual(['a', 'b', 'c', 'd', 'e', 'f']);
167 expect(dag.range('b', 'g').toSortedArray()).toEqual(['b', 'd', 'e', 'g']);
168 expect(dag.range(['a', 'b'], ['a', 'b']).toSortedArray()).toEqual(['a', 'b']);
169 });
170
171 it('gca()', () => {
172 expect(dag.gca('f', 'g').toSortedArray()).toEqual(['e']);
173 expect(dag.gca('f', 'e').toSortedArray()).toEqual(['e']);
174 expect(dag.gca('c', 'e').toSortedArray()).toEqual(['b']);
175 });
176
177 it('isAncestor()', () => {
178 expect(dag.isAncestor('a', 'a')).toBe(true);
179 expect(dag.isAncestor('b', 'g')).toBe(true);
180 expect(dag.isAncestor('d', 'f')).toBe(true);
181 expect(dag.isAncestor('c', 'g')).toBe(false);
182 expect(dag.isAncestor('g', 'a')).toBe(false);
183 });
184
185 it('supports present()', () => {
186 expect(dag.present(['a', 'x']).toSortedArray()).toEqual(['a']);
187 });
188
189 it('does not infinite loop on cyclic graphs', () => {
190 const dag = new BaseDag().add([
191 {hash: 'a', parents: ['b'], grandparents: []},
192 {hash: 'b', parents: ['c'], grandparents: []},
193 {hash: 'c', parents: ['a'], grandparents: []},
194 ]);
195 expect(dag.ancestors('b').toSortedArray()).toEqual(['a', 'b', 'c']);
196 expect(dag.descendants('b').toSortedArray()).toEqual(['a', 'b', 'c']);
197 expect(dag.isAncestor('a', 'c')).toBe(true);
198 expect(dag.isAncestor('c', 'a')).toBe(true);
199 });
200
201 it('preserves order for ancestors() or descendants()', () => {
202 // a--b--c
203 const dag = new BaseDag().add([
204 {...info, hash: 'a', parents: []},
205 {...info, hash: 'b', parents: ['a']},
206 {...info, hash: 'c', parents: ['b']},
207 ]);
208 expect(dag.ancestors('c').toArray()).toEqual(['c', 'b', 'a']);
209 expect(dag.ancestors('c').reverse().toArray()).toEqual(['a', 'b', 'c']);
210 expect(dag.descendants('a').toArray()).toEqual(['a', 'b', 'c']);
211 });
212 });
213
214 describe('sort', () => {
215 // a--b--c--d---e--f
216 // \ /
217 // y--x--w--v--u
218 const dag = new BaseDag().add(
219 Object.entries({
220 a: '',
221 b: 'a',
222 c: 'b',
223 d: 'c',
224 e: 'd v',
225 f: 'e',
226 y: '',
227 x: 'y b',
228 w: 'x',
229 v: 'w',
230 u: 'v',
231 }).map(([hash, v]) => {
232 return {hash, parents: v.split(' '), grandparents: []};
233 }),
234 );
235
236 it('asc', () => {
237 const sort = (s: SetLike) => dag.sortAsc(s).join(' ');
238 // sort all
239 expect(sort(dag)).toBe('a b c d y x w v e f u');
240 // sort subset
241 expect(sort(['a', 'f', 'b', 'c', 'e', 'd'])).toBe('a b c d e f');
242 expect(sort(['y', 'u', 'w', 'v', 'x'])).toBe('y x w v u');
243 expect(sort(['a', 'f', 'd'])).toBe('a d f');
244 expect(sort(['u', 'y', 'w'])).toBe('y w u');
245 expect(sort(['w', 'f', 'y'])).toBe('y w f');
246 expect(sort(['x', 'y', 'f', 'e'])).toBe('y x e f');
247 // custom sort function
248 expect(dag.sortAsc(['d', 'v'], {compare: a => (a.hash === 'v' ? -1 : 1)})).toEqual([
249 'v',
250 'd',
251 ]);
252 });
253
254 it('desc', () => {
255 const sort = (s: SetLike) => [...dag.sortDesc(s)].join(' ');
256 // sort all
257 expect(sort(dag)).toBe('u f e v w x y d c b a');
258 // sort subset
259 expect(sort(['a', 'f', 'b', 'c', 'e', 'd'])).toBe('f e d c b a');
260 expect(sort(['y', 'u', 'w', 'v', 'x'])).toBe('u v w x y');
261 expect(sort(['w', 'f', 'y'])).toBe('f w y');
262 expect(sort(['x', 'y', 'f', 'e'])).toBe('f e x y');
263 // custom sort function
264 expect(dag.sortDesc(['c', 'x'], {compare: a => (a.hash === 'x' ? -1 : 1)})).toEqual([
265 'x',
266 'c',
267 ]);
268 });
269 });
270
271 describe('resolve', () => {
272 const dag = new Dag().add(
273 [
274 {...info, hash: 'abc'},
275 {...info, hash: 'abd', bookmarks: ['foo', 'bar']},
276 {...info, hash: 'acc', remoteBookmarks: ['remote/foo', 'remote/main']},
277 {...info, hash: 'add', isDot: true},
278 {...info, hash: 'aee', remoteBookmarks: ['remote/bar'], bookmarks: ['baz']},
279 {...info, hash: 'aff'},
280 ].map(toInfo),
281 );
282
283 it('supports "."', () => {
284 expect(dag.resolve('.')?.hash).toBe('add');
285 });
286
287 it('supports hashes', () => {
288 for (const h of ['abc', 'abd', 'aff']) {
289 expect(dag.resolve(h)?.hash).toBe(h);
290 }
291 });
292
293 it('supports bookmarks', () => {
294 expect(dag.resolve('foo')?.hash).toBe('abd');
295 expect(dag.resolve('bar')?.hash).toBe('abd');
296 expect(dag.resolve('baz')?.hash).toBe('aee');
297 });
298
299 it('supports remotenames', () => {
300 expect(dag.resolve('remote/foo')?.hash).toBe('acc');
301 expect(dag.resolve('remote/main')?.hash).toBe('acc');
302 expect(dag.resolve('remote/bar')?.hash).toBe('aee');
303 });
304
305 it('supports hoisted remotenames', () => {
306 expect(dag.resolve('main')?.hash).toBe('acc');
307 });
308
309 it('supports hash prefix', () => {
310 expect(dag.resolve('af')?.hash).toBe('aff');
311 expect(dag.resolve('ac')?.hash).toBe('acc');
312 expect(dag.resolve('ab')?.hash).toBe(undefined); // ambiguous
313 });
314
315 it('considers priorities between bookmarks and hashes', () => {
316 const dag = new Dag().add(
317 [
318 {...info, hash: 'foo'},
319 {...info, hash: 'bar', bookmarks: ['foo']},
320 {...info, hash: 'baz', bookmarks: ['fo']},
321 ].map(toInfo),
322 );
323 // full hash > bookmark
324 expect(dag.resolve('foo')?.hash).toBe('foo');
325 // bookmark > prefix
326 expect(dag.resolve('fo')?.hash).toBe('baz');
327 });
328
329 it('moves "." with edits', () => {
330 const dag1 = dag.replaceWith(['add', 'abc'], (h, c) => {
331 return c?.set('isDot', h === 'abc');
332 });
333 expect(dag1.remove('abc').resolve('.')?.hash).toBe(undefined);
334 });
335
336 it('resolves hoisted name when conflicted bookmark is removed', () => {
337 // foo: abd (bookmark); acc (hoisted remote bookmark)
338 // removing 'abc' will make foo resolve to acc.
339 expect(dag.remove('abd').resolve('foo')?.hash).toBe('acc');
340 });
341
342 it('hash prefix works when ambiguous hashes are removed', () => {
343 // 'ab' prefix: abc abd
344 // removing 'abc' will make 'ab' resolve to 'abd'.
345 expect(dag.remove('abc').resolve('ab')?.hash).toBe('abd');
346 });
347 });
348
349 describe('mutation', () => {
350 // mutation: a-->a1-->a2-->a3
351 // dag: a1 a2 b.
352 const dag = new Dag()
353 .add(
354 [
355 {...info, hash: 'a', successorInfo: {hash: 'a1', type: ''}},
356 {...info, hash: 'a1'},
357 {...info, hash: 'a2', closestPredecessors: ['a1']},
358 {...info, hash: 'a3', closestPredecessors: ['a2']},
359 {...info, hash: 'b', closestPredecessors: ['b0']},
360 ].map(toInfo),
361 )
362 .remove(['a', 'a3']);
363
364 it('followSuccessors()', () => {
365 expect(dag.followSuccessors(['a', 'b']).toSortedArray()).toEqual(['a2', 'b']);
366 expect(dag.followSuccessors(['a3']).toSortedArray()).toEqual(['a3']);
367 expect(dag.followSuccessors(['a1', 'a2']).toSortedArray()).toEqual(['a2']);
368 });
369
370 it('successors()', () => {
371 expect(dag.successors(['a', 'b']).toSortedArray()).toEqual(['a', 'a1', 'a2', 'b']);
372 expect(dag.successors(['a1', 'a2']).toSortedArray()).toEqual(['a1', 'a2']);
373 });
374
375 it('predecessors()', () => {
376 expect(dag.predecessors(['a', 'b']).toSortedArray()).toEqual(['b']);
377 expect(dag.predecessors(['a2']).toSortedArray()).toEqual(['a1', 'a2']);
378 expect(dag.predecessors(['a3']).toSortedArray()).toEqual(['a1', 'a2']);
379 });
380
381 it('picks stack top when following a split', () => {
382 // mutation: a->b a->c a->d
383 // dag: a b--d--c.
384 const dag = new Dag()
385 .add(
386 [
387 {...info, hash: 'a'},
388 {...info, hash: 'b', closestPredecessors: ['a']},
389 {...info, hash: 'c', closestPredecessors: ['a'], parents: ['d']},
390 {...info, hash: 'd', closestPredecessors: ['a'], parents: ['b']},
391 ].map(toInfo),
392 )
393 .remove(['a']);
394 // not ['d'] or ['b', 'c', 'd']
395 expect(dag.followSuccessors('a').toSortedArray()).toEqual(['c']);
396 });
397 });
398
399 describe('rebase', () => {
400 const succ = (h: Hash): Hash => `${REBASE_SUCC_PREFIX}${h}`;
401
402 it('can break linear stack', () => {
403 // a--b--c rebase -r c -d a
404 let dag = new Dag().add(
405 [
406 {...info, hash: 'a', parents: []},
407 {...info, hash: 'b', parents: ['a']},
408 {...info, hash: 'c', parents: ['b']},
409 ].map(toInfo),
410 );
411 dag = dag.rebase(['c'], 'a');
412 expect(dag.parentHashes('c')).toEqual(['a']);
413 });
414
415 it('skips already rebased branches', () => {
416 // a--------b rebase -r c+d+e+f -d b
417 // \ \ e f should not be touched.
418 // c--d e--f
419 let dag = new Dag().add(
420 [
421 {...info, hash: 'a', parents: [], phase: PUBLIC},
422 {...info, hash: 'b', parents: ['a'], phase: PUBLIC},
423 {...info, hash: 'c', parents: ['a'], phase: DRAFT},
424 {...info, hash: 'd', parents: ['c'], phase: DRAFT},
425 {...info, hash: 'e', parents: ['b'], phase: DRAFT},
426 {...info, hash: 'f', parents: ['e'], phase: DRAFT},
427 ].map(toInfo),
428 );
429 dag = dag.rebase(['c', 'd', 'e', 'f'], 'b');
430
431 // e and f should not be touched
432 expect(dag.get('e')?.date).toEqual(date);
433 expect(dag.get('f')?.date).toEqual(date);
434
435 // c and d are touched
436 expect(dag.get('c')?.date).not.toEqual(date);
437 expect(dag.get('d')?.date).not.toEqual(date);
438
439 // check b--e--f and b--c--d
440 expect(dag.parentHashes('f')).toEqual(['e']);
441 expect(dag.parentHashes('e')).toEqual(['b']);
442 expect(dag.parentHashes('d')).toEqual(['c']);
443 expect(dag.parentHashes('c')).toEqual(['b']);
444 });
445
446 it('handles orphaned commits', () => {
447 // a--b z; rebase -r a -d z; result:
448 // a(pred)--b z--a(succ).
449 let dag = new Dag().add(
450 [
451 {...info, hash: 'z', parents: [], phase: PUBLIC},
452 {...info, hash: 'a', parents: [], phase: DRAFT},
453 {...info, hash: 'b', parents: ['a'], phase: DRAFT},
454 ].map(toInfo),
455 );
456 dag = dag.rebase(['a'], 'z');
457
458 // check z--a(succ)
459 expect(dag.parentHashes(succ('a'))).toEqual(['z']);
460 expect(dag.get(succ('a'))?.date).not.toEqual(date);
461
462 // check a(pred)--b
463 expect(dag.parentHashes('b')).toEqual(['a']);
464 expect(dag.parentHashes('a')).toEqual([]);
465 expect(dag.get('a')?.date).toEqual(date);
466 expect(dag.get('b')?.date).toEqual(date);
467 });
468
469 it('handles non-continuous selection', () => {
470 // a--b--c--d--e--f z; rebase b+c+e+f to z; result:
471 // a--b(pred)--c(pred)--d; z--b(succ)--c(succ)--e--f
472 let dag = new Dag().add(
473 [
474 {...info, hash: 'a', parents: []},
475 {...info, hash: 'b', parents: ['a']},
476 {...info, hash: 'c', parents: ['b']},
477 {...info, hash: 'd', parents: ['c']}, // not rebasing
478 {...info, hash: 'e', parents: ['d']},
479 {...info, hash: 'f', parents: ['e']},
480 {...info, hash: 'z', parents: []},
481 ].map(toInfo),
482 );
483 dag = dag.rebase(['b', 'c', 'e', 'f'], 'z');
484
485 // check z--b(succ)--c(succ)--e--f
486 expect(dag.parentHashes('f')).toEqual(['e']);
487 expect(dag.parentHashes('e')).toEqual([succ('c')]);
488 expect(dag.parentHashes(succ('c'))).toEqual([succ('b')]);
489 expect(dag.parentHashes(succ('b'))).toEqual(['z']);
490
491 // check a--b(pred)--c(pred)--c--d
492 expect(dag.parentHashes('c')).toEqual(['b']);
493 expect(dag.parentHashes('b')).toEqual(['a']);
494 expect(dag.childHashes('d').toArray()).toEqual([]);
495
496 // succ and pred info
497 expect(dag.get('b')?.successorInfo?.hash).toEqual(succ('b'));
498 expect(dag.get('c')?.successorInfo?.hash).toEqual(succ('c'));
499 expect(dag.get(succ('b'))?.closestPredecessors).toEqual(['b']);
500 expect(dag.get(succ('c'))?.closestPredecessors).toEqual(['c']);
501
502 // orphaned and obsoleted b--c--d are not touched
503 expect(dag.get('b')?.date).toEqual(date);
504 expect(dag.get('c')?.date).toEqual(date);
505 expect(dag.get('d')?.date).toEqual(date);
506 });
507
508 it('cleans up obsoleted commits', () => {
509 // a--b--c--f rebase -r f -d z
510 // \ / b, c, d, e are obsoleted
511 // -d--e- b is head
512 // z check: c, d, e are removed
513 const successorInfo: SuccessorInfo = {hash: 'z', type: 'rewrite'};
514 let dag = new Dag().add(
515 [
516 {...info, hash: 'z', parents: [], phase: PUBLIC},
517 {...info, hash: 'a', parents: [], phase: DRAFT},
518 {...info, hash: 'b', parents: ['a'], phase: DRAFT, date, successorInfo, isDot: true},
519 {...info, hash: 'c', parents: ['b'], phase: DRAFT, date, successorInfo},
520 {...info, hash: 'd', parents: ['a'], phase: DRAFT, date, successorInfo},
521 {...info, hash: 'e', parents: ['d'], phase: DRAFT, date, successorInfo},
522 {...info, hash: 'f', parents: ['c', 'e'], phase: DRAFT, date},
523 ].map(toInfo),
524 );
525 dag = dag.rebase(['f'], 'z');
526 expect(['b', 'c', 'd', 'e'].filter(h => dag.has(h))).toEqual(['b']);
527 });
528 });
529
530 describe('connect public commits', () => {
531 it('connect with grandparents info', () => {
532 // z-w x y => z-x-y
533 // \
534 // w
535 const dag = new Dag().add(
536 [
537 {...info, hash: 'z', phase: PUBLIC},
538 {...info, hash: 'x', phase: PUBLIC, parents: ['a'], grandparents: ['z']},
539 {...info, hash: 'y', phase: PUBLIC, parents: ['b'], grandparents: ['x']},
540 {...info, hash: 'w', phase: PUBLIC, parents: ['z']},
541 ].map(toInfo),
542 );
543 expect(dag.children('z').toSortedArray()).toEqual(['w', 'x']);
544 expect(dag.children('x').toSortedArray()).toEqual(['y']);
545 expect(dag.children('y').toSortedArray()).toEqual([]);
546 expect(dag.children('w').toSortedArray()).toEqual([]);
547 });
548
549 it('forceConnectPublic() without grandparents info', () => {
550 // z-w x y => z-x-y
551 // \
552 // w
553 const dag = new Dag()
554 .add(
555 [
556 {...info, hash: 'z', phase: PUBLIC, date: new Date(1)},
557 {...info, hash: 'x', phase: PUBLIC, date: new Date(2)},
558 {...info, hash: 'y', phase: PUBLIC, date: new Date(3)},
559 {...info, hash: 'w', phase: PUBLIC, date: new Date(3), parents: ['z']},
560 ].map(toInfo),
561 )
562 .maybeForceConnectPublic();
563 // Without grandparents info, fallback to chronological connections.
564 expect(dag.children('z').toSortedArray()).toEqual(['w', 'x']);
565 expect(dag.children('x').toSortedArray()).toEqual(['y']);
566 expect(dag.children('y').toSortedArray()).toEqual([]);
567 // w is not a root so it does not need fix.
568 expect(dag.children('w').toSortedArray()).toEqual([]);
569 });
570 });
571
572 it('renders to ASCII text', () => {
573 // a--b--c
574 // / \
575 // z d
576 const dag = new Dag().add(
577 [
578 {...info, phase: PUBLIC, hash: 'a', parents: []},
579 {...info, phase: PUBLIC, hash: 'z', parents: []},
580 {...info, phase: PUBLIC, hash: 'b', parents: ['a', 'z']},
581 {...info, phase: PUBLIC, hash: 'c', parents: ['b']},
582 {...info, phase: DRAFT, hash: 'd', parents: ['c']},
583 ].map(toInfo),
584 );
585
586 expect(dag.renderAscii()).toMatchInlineSnapshot(`
587 "
588 o d
589 │
590 ╭─╯
591 o c
592 │
593 o b
594 │
595 ├─╮
596 o │ a
597 │
598 o z"
599 `);
600
601 // Render a subset.
602 // [a, c] subset: edge is dashed.
603 expect(dag.renderAscii(['a', 'c'])).toMatchInlineSnapshot(`
604 "
605 o c
606 │
607 :
608 o a"
609 `);
610 // [b, d] subset: indents "d" (draft), and "b" has an "~".
611 expect(dag.renderAscii(['b', 'd'])).toMatchInlineSnapshot(`
612 "
613 o d
614 │
615 ╭─╯
616 :
617 o b
618 │
619 │
620 ~"
621 `);
622 });
623});
624
625describe('HashSet', () => {
626 it('preserves order on intersect', () => {
627 const a = HashSet.fromHashes(['c', 'b', 'e', 'd', 'a', 'f']);
628 expect(a.intersect(['d', 'b']).toArray()).toEqual(['b', 'd']);
629 expect(a.intersect(['b', 'd']).toArray()).toEqual(['b', 'd']);
630 });
631
632 it('preserves order on substract', () => {
633 const a = HashSet.fromHashes(['c', 'b', 'e', 'd', 'a', 'f']);
634 expect(a.subtract(['d', 'b']).toArray()).toEqual(['c', 'e', 'a', 'f']);
635 expect(a.subtract(['b', 'd']).toArray()).toEqual(['c', 'e', 'a', 'f']);
636 expect(a.subtract(['f', 'c', 'e']).toArray()).toEqual(['b', 'd', 'a']);
637 });
638
639 it('preserves order on union', () => {
640 const a = HashSet.fromHashes(['d', 'a', 'c']);
641 expect(a.union(['x', 'z', 'y']).toArray()).toEqual(['d', 'a', 'c', 'x', 'z', 'y']);
642 expect(a.union(['y', 'z', 'x']).toArray()).toEqual(['d', 'a', 'c', 'y', 'z', 'x']);
643
644 expect(a.union(['a', 'd']).toArray()).toEqual(['d', 'a', 'c']);
645 expect(a.union(['d', 'a']).toArray()).toEqual(['d', 'a', 'c']);
646
647 expect(a.union(['a', 'b']).toArray()).toEqual(['d', 'a', 'c', 'b']);
648 expect(a.union(['f', 'c', 'a', 'd', 'e']).toArray()).toEqual(['d', 'a', 'c', 'f', 'e']);
649 });
650});
651