1pub mod graph;
2
3pub use graph::{
4 ColumnComputation, ConnectionKind, GraphLayout, GraphNode, GraphRenderer, LaneId, MaskRoute, Node, NodeId,
5 NodeKind, RenderConfig, Renderable, RouteReason, RowPlan, StepDetails, TrackCell,
6};
7
8#[cfg(test)]
9mod tests {
10 use std::sync::Once;
11
12 use super::*;
13
14 static COLOR_EYRE_INIT: Once = Once::new();
15
16 #[must_use]
17 pub fn parse_nodes(input: &str) -> color_eyre::eyre::Result<Vec<Node>> {
18 fn parse_parent_list(part: &str) -> Vec<NodeId> {
19 part.split(',').map(str::trim).filter(|s| !s.is_empty()).map(str::to_string).collect()
20 }
21
22 let mut nodes = Vec::new();
23
24 for (idx, raw) in input.lines().enumerate() {
25 let line_no = idx + 1;
26 let line = raw.trim();
27
28 if line.is_empty() {
29 continue;
30 }
31
32 let (id_part, parents_part) = match line.split_once(':') {
33 Some((left, right)) => (left.trim(), Some(right)),
34 None => (line, None),
35 };
36
37 if id_part.is_empty() {
38 color_eyre::eyre::bail!("Line {}: Missing node ID", line_no);
39 }
40
41 let parents = parents_part.map(parse_parent_list).unwrap_or_default();
42 nodes.push(Node::new(id_part, parents));
43 }
44
45 Ok(nodes)
46 }
47
48 fn diff_blocks(expected: &str, actual: &str) -> String {
49 let mut msg = String::new();
50 msg.push_str("\n\n--- expected ---\n\n");
51 msg.push_str(expected);
52 msg.push_str("\n\n--- actual ---\n\n");
53 msg.push_str(actual);
54 msg.push_str("\n");
55 msg
56 }
57
58 pub fn test_output(data: &str, expected: &str) -> color_eyre::Result<()> {
59 use color_eyre::eyre::eyre;
60
61 COLOR_EYRE_INIT.call_once(|| {
62 let _ = color_eyre::install();
63 });
64
65 let nodes = parse_nodes(data).map_err(|e| eyre!("parse_nodes failed: {:?}", e))?;
66
67 let mut r = GraphRenderer::new(RenderConfig::default());
68 let actual_glyphs = r.render_to_string(&nodes);
69
70 let expected_n = expected.trim().to_string();
71
72 let expected_has_suffix = expected_n.chars().any(|c| c.is_ascii_alphanumeric() || c == '(' || c == ')');
74
75 let actual_pretty =
76 if expected_has_suffix { render_with_suffix(&actual_glyphs, &nodes) } else { actual_glyphs };
77
78 let actual_n = actual_pretty.trim().to_string();
79
80 if expected_n != actual_n {
81 println!("\n{}", diff_blocks(&expected_n, &actual_n));
82 }
83 pretty_assertions::assert_eq!(
84 expected_n,
85 actual_n,
86 "Expected (left; `<`) output did not match Actual (right; `>`) output"
87 );
88
89 Ok(())
90 }
91
92 fn render_with_suffix(rendered: &str, nodes: &[Node]) -> String {
93 let mut out = String::with_capacity(rendered.len() + nodes.len() * 16);
94
95 for (i, (line, node)) in rendered.lines().zip(nodes.iter()).enumerate() {
96 if i != 0 {
97 out.push('\n');
98 }
99
100 out.push_str(line);
101
102 out.push(' ');
104 out.push_str(&node.id);
105
106 if !node.parents.is_empty() {
108 out.push(' ');
109 out.push('(');
110 for (pi, p) in node.parents.iter().enumerate() {
111 if pi != 0 {
112 out.push(' ');
113 }
114 out.push_str(p);
115 }
116 out.push(')');
117 }
118 }
119
120 out
121 }
122
123 #[test]
124 fn test_linear_chain() -> color_eyre::Result<()> {
125 test_output(
126 r#"
1271-d: 1-c
1281-c: 1-b
1291-b: 1-a
1301-a
131"#,
132 r#"
133⦿ 1-d (1-c)
134● 1-c (1-b)
135● 1-b (1-a)
136⊝ 1-a
137"#,
138 )?;
139
140 Ok(())
141 }
142
143 #[test]
144 fn test_merge_with_single_side_commit() -> color_eyre::Result<()> {
145 test_output(
146 r#"
1471-d: 1-c
1481-c: 1-b, 2-a
1492-a: 1-b
1501-b: 1-a
1511-a
152"#,
153 r#"
154⦿ 1-d (1-c)
155⊗─╮ 1-c (1-b 2-a)
156│ ● 2-a (1-b)
157●─╯ 1-b (1-a)
158⊝ 1-a
159"#,
160 )?;
161
162 Ok(())
163 }
164
165 #[test]
166 fn test_merge_with_extra_mainline_commit() -> color_eyre::Result<()> {
167 test_output(
168 r#"
1691-e: 1-d
1701-d: 1-c, 2-a
1712-a: 1-b
1721-c: 1-b
1731-b: 1-a
1741-a
175"#,
176 r#"
177⦿ 1-e (1-d)
178⊗─╮ 1-d (1-c 2-a)
179│ ● 2-a (1-b)
180● │ 1-c (1-b)
181●─╯ 1-b (1-a)
182⊝ 1-a
183"#,
184 )?;
185
186 Ok(())
187 }
188
189 #[test]
190 fn test_merge_with_extra_commits_on_both_branches() -> color_eyre::Result<()> {
191 test_output(
192 r#"
1931-e: 1-d
1941-d: 1-c, 2-b
1952-b: 2-a
1962-a: 1-b
1971-c: 1-b
1981-b: 1-a
1991-a
200"#,
201 r#"
202⦿ 1-e (1-d)
203⊗─╮ 1-d (1-c 2-b)
204│ ● 2-b (2-a)
205│ ● 2-a (1-b)
206● │ 1-c (1-b)
207●─╯ 1-b (1-a)
208⊝ 1-a
209"#,
210 )?;
211
212 Ok(())
213 }
214
215 #[test]
216 fn test_merge_with_crossover_left_variant() -> color_eyre::Result<()> {
217 test_output(
218 r#"
219f: e, c
220e: b, d
221d: a
222c: a
223b: a
224a
225"#,
226 r#"
227⍟─╮ f (e c)
228⊗─┊─╮ e (b d)
229│ │ ● d (a)
230│ ● │ c (a)
231● │ │ b (a)
232⊝─┴─╯ a
233"#,
234 )?;
235
236 Ok(())
237 }
238
239 #[test]
240 fn test_merge_with_crossover_right_variant() -> color_eyre::Result<()> {
241 test_output(
242 r#"
243f: e, d
244e: b, c
245d: a
246c: a
247b: a
248a
249"#,
250 r#"
251⍟─╮ f (e d)
252⊗─┊─╮ e (b c)
253│ ● │ d (a)
254│ │ ● c (a)
255● │ │ b (a)
256⊝─┴─╯ a
257"#,
258 )?;
259
260 Ok(())
261 }
262
263 #[test]
264 fn test_merge_whose_parent_is_itself_a_merge() -> color_eyre::Result<()> {
265 test_output(
266 r#"
267A: B, C
268C: B, D
269B: D
270D
271"#,
272 r#"
273⍟─╮ A (B C)
274│ ⊗─╮ C (B D)
275●─╯ │ B (D)
276⊝───╯ D
277"#,
278 )?;
279
280 Ok(())
281 }
282
283 #[test]
284 fn test_merge_with_shared_ancestor_parent() -> color_eyre::Result<()> {
285 test_output(
286 r#"
287A: B, D
288B: D, C
289C: D
290D
291"#,
292 r#"
293⍟─╮ A (B D)
294⊗─┊─╮ B (D C)
295│ │ ● C (D)
296⊝─┴─╯ D
297"#,
298 )?;
299
300 Ok(())
301 }
302
303 #[test]
304 fn test_octopus_merge_with_many_parents() -> color_eyre::Result<()> {
305 test_output(
306 r#"
307A: B, C, D, E, F, G, H, I, J, K
308B: K
309C: K
310D: K
311E: K
312F: K
313G: K
314H: K
315I: K
316J: K
317K
318"#,
319 r#"
320⍟─┬─┬─┬─┬─┬─┬─┬─┬─╮ A (B C D E F G H I J K)
321● │ │ │ │ │ │ │ │ │ B (K)
322│ ● │ │ │ │ │ │ │ │ C (K)
323│ │ ● │ │ │ │ │ │ │ D (K)
324│ │ │ ● │ │ │ │ │ │ E (K)
325│ │ │ │ ● │ │ │ │ │ F (K)
326│ │ │ │ │ ● │ │ │ │ G (K)
327│ │ │ │ │ │ ● │ │ │ H (K)
328│ │ │ │ │ │ │ ● │ │ I (K)
329│ │ │ │ │ │ │ │ ● │ J (K)
330⊝─┴─┴─┴─┴─┴─┴─┴─┴─╯ K
331"#,
332 )?;
333
334 Ok(())
335 }
336
337 #[test]
338 fn test_octopus_merge_with_nested_merge_parent() -> color_eyre::Result<()> {
339 test_output(
340 r#"
341A: B, C, D, E
342C: E
343E: D, B
344B: D
345D
346"#,
347 r#"
348⍟─┬─┬─╮ A (B C D E)
349│ ● │ │ C (E)
350│ ⊗─┊─┴─╮ E (D B)
351●─┊─┊───╯ B (D)
352⊝─┴─╯ D
353"#,
354 )?;
355
356 Ok(())
357 }
358
359 #[test]
360 fn test_three_merges_with_nested_branch_merge() -> color_eyre::Result<()> {
361 test_output(
362 r#"
363A: B, C
364B: D, E
365C: F
366F: G, D
367D: G
368G: E
369E
370"#,
371 r#"
372⍟─╮ A (B C)
373⊗─┊─╮ B (D E)
374│ ● │ C (F)
375│ ⊗─┊─╮ F (G D)
376●─┊─┊─╯ D (G)
377●─╯ │ G (E)
378⊝───╯ E
379"#,
380 )?;
381
382 Ok(())
383 }
384
385 #[test]
386 fn test_disconnected_histories_without_common_root() -> color_eyre::Result<()> {
387 test_output(
388 r#"
389A: B, C
390C: D
391B: E, D
392D: F
393E
394F
395"#,
396 r#"
397⍟─╮ A (B C)
398│ ● C (D)
399⊗─┊─╮ B (E D)
400│ ●─╯ D (F)
401⊝ │ E
402 ⊝ F
403"#,
404 )?;
405
406 Ok(())
407 }
408
409 #[test]
410 fn test_disconnected_history_with_missing_parents() -> color_eyre::Result<()> {
411 test_output(
412 r#"
413A: B, C
414C: B
415D: B
416E: F
417F: G
418G: H
419"#,
420 r#"
421⍟─╮ A (B C)
422│ ◌ C (B)
423│ │ ◌ D (B)
424│ │ │ ⦿ E (F)
425│ │ │ ● F (G)
426│ │ │ ◌ G (H)
427"#,
428 )?;
429 Ok(())
430 }
431
432 #[test]
433 fn collapses_lanes_in_linearized_multi_parent_chain() -> color_eyre::Result<()> {
434 test_output(
435 r#"
436A: B, C, D, E, F, G
437B: C
438C: D
439D: E
440E: F
441F: G
442G
443"#,
444 r#"
445⍟─┬─┬─┬─┬─╮ A (B C D E F G)
446● │ │ │ │ │ B (C)
447●─╯ │ │ │ │ C (D)
448●───╯ │ │ │ D (E)
449●─────╯ │ │ E (F)
450●───────╯ │ F (G)
451⊝─────────╯ G
452"#,
453 )?;
454
455 Ok(())
456 }
457
458 #[test]
459 fn collapses_single_lane_after_merge_resolution() -> color_eyre::Result<()> {
460 test_output(
461 r#"
462A: B, C, D, E, F
463C: B
464B: H
465F: E
466H: D
467D: E
468E
469"#,
470 r#"
471⍟─┬─┬─┬─╮ A (B C D E F)
472│ ● │ │ │ C (B)
473●─╯ │ │ │ B (H)
474│ ╭─╯ │ ● F (E)
475● │ ╭─╯ │ H (D)
476●─╯ │ ╭─╯ D (E)
477⊝───┴─╯ E
478"#,
479 )?;
480
481 Ok(())
482 }
483
484 #[test]
485 fn collapses_multiple_lanes_in_one_pass() -> color_eyre::Result<()> {
486 test_output(
487 r#"
488A: B, C, D, E, F
489C: B
490B: H
491F: G
492H: D
493D: E
494E: G
495G
496"#,
497 r#"
498⍟─┬─┬─┬─╮ A (B C D E F)
499│ ● │ │ │ C (B)
500●─╯ │ │ │ B (H)
501│ ╭─╯ │ ● F (G)
502● │ ╭─╯ │ H (D)
503●─╯ │ ╭─╯ D (E)
504●───╯ │ E (G)
505⊝─────╯ G
506"#,
507 )?;
508
509 Ok(())
510 }
511
512 #[test]
513 fn collapses_multiple_lanes_across_several_rows() -> color_eyre::Result<()> {
514 test_output(
515 r#"
516A: B, C, K, D, E, F
517C: B
518B: K
519K: H
520F: G
521H: D
522D: E
523E: G
524G
525"#,
526 r#"
527⍟─┬─┬─┬─┬─╮ A (B C K D E F)
528│ ● │ │ │ │ C (B)
529●─╯ │ │ │ │ B (K)
530●───╯ │ │ │ K (H)
531│ ╭───╯ │ ● F (G)
532● │ ╭───╯ │ H (D)
533●─╯ │ ╭───╯ D (E)
534●───╯ │ E (G)
535⊝─────╯ G
536"#,
537 )?;
538
539 Ok(())
540 }
541
542 #[test]
543 fn collapses_all_possible_lanes_in_dense_graph() -> color_eyre::Result<()> {
544 test_output(
545 r#"
546A: Z, B, C, D, E, F
547C: B
548B: H
549F: G
550H: D
551D: E
552E: G
553G: Z
554Z
555"#,
556 r#"
557⍟─┬─┬─┬─┬─╮ A (Z B C D E F)
558│ │ ● │ │ │ C (B)
559│ ●─╯ │ │ │ B (H)
560│ │ ╭─╯ │ ● F (G)
561│ ● │ ╭─╯ │ H (D)
562│ ●─╯ │ ╭─╯ D (E)
563│ ●───╯ │ E (G)
564│ ●─────╯ G (Z)
565⊝─╯ Z
566"#,
567 )?;
568
569 Ok(())
570 }
571
572 #[test]
573 fn test_large_disconnected_history_with_many_missing_parents() -> color_eyre::Result<()> {
574 test_output(
575 r#"
576A: B, C
577C: B
578D: B
579E: F
580F: G
581G: H
582H: I
583I: J
584J: K
585K: L
586L: M
587M: N
588N: O
589O: P
590B: Q, R
591R: Q
592Q: S, T
593T: S
594P: U
595U: V
596V: W
597S: X, Y
598Z: 1
599Y: X
600X: 2, 3
6013: 2
6024: 5
6035: 6
604W: 7
6056: 8
6067: 9
6072: 0, a
608a: b
609b: c
610c: d, 0
6118: e
612e: f
613f: g
6140: h, i
615g: j
616j: k
617k: l
618l: m
619m: n
620n: o
621o: p
622p: 1
6239: q
6241: r
625i: h
626d: h
627r: s
628h: t, u
629s: v
630u: t
631w: x
632x: y
633"#,
634 r#"
635⍟─╮ A (B C)
636│ ● C (B)
637│ │ ⦿ D (B)
638│ │ │ ⦿ E (F)
639│ │ │ ● F (G)
640│ │ │ ● G (H)
641│ │ │ ● H (I)
642│ │ │ ● I (J)
643│ │ │ ● J (K)
644│ │ │ ● K (L)
645│ │ │ ● L (M)
646│ │ │ ● M (N)
647│ │ │ ● N (O)
648│ │ │ ● O (P)
649⊗─┴─┴─┊─╮ B (Q R)
650│ ╭───╯ ● R (Q)
651⊗─┊─┬───╯ Q (S T)
652│ │ ● T (S)
653│ ● │ P (U)
654│ ● │ U (V)
655│ ● │ V (W)
656⊗─┊─┴─╮ S (X Y)
657│ │ ⦿ │ Z (1)
658│ │ │ ● Y (X)
659⊗─┊─┊─┴─╮ X (2 3)
660│ │ │ ●─╯ 3 (2)
661│ │ │ │ ⦿ 4 (5)
662│ │ │ │ ● 5 (6)
663│ ● │ │ │ W (7)
664│ │ │ │ ● 6 (8)
665│ ● │ │ │ 7 (9)
666⊗─┊─┊─┴─┊─╮ 2 (0 a)
667│ │ │ ╭─╯ ● a (b)
668│ │ │ │ ●─╯ b (c)
669│ │ │ │ ⊗─╮ c (d 0)
670│ │ │ ● │ │ 8 (e)
671│ │ │ ● │ │ e (f)
672│ │ │ ● │ │ f (g)
673⊗─┊─┊─┊─┊─┴─╮ 0 (h i)
674│ │ │ ● │ ╭─╯ g (j)
675│ │ │ ● │ │ j (k)
676│ │ │ ● │ │ k (l)
677│ │ │ ● │ │ l (m)
678│ │ │ ● │ │ m (n)
679│ │ │ ● │ │ n (o)
680│ │ │ ● │ │ o (p)
681│ │ │ ● │ │ p (1)
682│ ◌ │ │ │ │ 9 (q)
683│ │ ●─╯ │ │ 1 (r)
684│ │ │ ╭─╯ ● i (h)
685│ │ │ ● ╭─╯ d (h)
686│ │ ● │ │ r (s)
687⊗─┊─┊─┴─┴─╮ h (t u)
688│ │ ◌ ╭───╯ s (v)
689│ │ │ ◌ u (t)
690│ │ │ │ ⦿ w (x)
691│ │ │ │ ◌ x (y)
692"#,
693 )?;
694 Ok(())
695 }
696
697 #[test]
698 fn test_parallel_sibling_merges() -> color_eyre::Result<()> {
699 test_output(
700 r#"
701A: Z, B, C
702B: D, C
703D: E, C
704E: Z
705Z: Y
706Y: X
707X: W
708W: C
709C
710"#,
711 r#"
712⍟─┬─╮ A (Z B C)
713│ ⊗─┊─╮ B (D C)
714│ ⊗─┊─┊─╮ D (E C)
715│ ● │ │ │ E (Z)
716●─╯ │ │ │ Z (Y)
717● ╭─╯ │ │ Y (X)
718● │ ╭─╯ │ X (W)
719● │ │ ╭─╯ W (C)
720⊝─┴─┴─╯ C
721"#,
722 )?;
723
724 Ok(())
725 }
726
727 #[test]
728 fn test_merge_path_shorter_than_parallel_branch() -> color_eyre::Result<()> {
729 test_output(
730 r#"
731A: H, B, C, D, J, E
732B: K
733C: H
734J: I
735D: K
736E: F
737K: F
738F: G, H
739G: I
740H: I
741I
742"#,
743 r#"
744⍟─┬─┬─┬─┬─╮ A (H B C D J E)
745│ ● │ │ │ │ B (K)
746│ │ ● │ │ │ C (H)
747│ │ │ │ ● │ J (I)
748│ │ │ ● │ │ D (K)
749│ │ │ │ │ ● E (F)
750│ ●─┊─╯ │ │ K (F)
751│ ⊗─┊─┬─┊─╯ F (G H)
752│ ● │ │ │ G (I)
753●─┊─┴─╯ │ H (I)
754⊝─┴─────╯ I
755"#,
756 )?;
757
758 Ok(())
759 }
760
761 #[test]
762 fn test_branch_and_merge_with_middle_divergence() -> color_eyre::Result<()> {
763 test_output(
764 r#"
765A: B, C, E
766B: F
767C: F
768E: Z
769F: G, I
770G: H, I
771H: I
772I: Z
773Z
774"#,
775 r#"
776⍟─┬─╮ A (B C E)
777● │ │ B (F)
778│ ● │ C (F)
779│ │ ● E (Z)
780⊗─┴─┊─╮ F (G I)
781⊗─╮ │ │ G (H I)
782● │ │ │ H (I)
783●─┴─┊─╯ I (Z)
784⊝───╯ Z
785"#,
786 )?;
787
788 Ok(())
789 }
790
791 #[test]
792 fn test_crossover_then_lane_collapse() -> color_eyre::Result<()> {
793 test_output(
794 r#"
795A: B, D, E
796B: F
797D: F
798E: Z
799F: G
800G: H, I
801H: I
802I: Z
803Z
804"#,
805 r#"
806⍟─┬─╮ A (B D E)
807● │ │ B (F)
808│ ● │ D (F)
809│ │ ● E (Z)
810●─╯ │ F (G)
811⊗─╮ │ G (H I)
812● │ │ H (I)
813●─╯ │ I (Z)
814⊝───╯ Z
815"#,
816 )?;
817
818 Ok(())
819 }
820
821 #[test]
822 fn collapses_parallel_branches_with_distinct_middle_paths() -> color_eyre::Result<()> {
823 test_output(
824 r#"
825A: B, C, D, E, F
826D: I
827E: J
828F: I
829B: C
830C: G
831G: H
832H: I
833I: J
834J
835"#,
836 r#"
837⍟─┬─┬─┬─╮ A (B C D E F)
838│ │ ● │ │ D (I)
839│ │ │ ● │ E (J)
840│ │ │ │ ● F (I)
841● │ │ │ │ B (C)
842●─╯ │ │ │ C (G)
843● ╭─╯ │ │ G (H)
844● │ ╭─╯ │ H (I)
845●─┴─┊───╯ I (J)
846⊝───╯ J
847"#,
848 )?;
849
850 Ok(())
851 }
852
853 #[test]
854 fn collapses_long_multi_stage_lane_chain() -> color_eyre::Result<()> {
855 test_output(
856 r#"
857A: B, C, D, E, F, G
858C: B
859D: B
860E: B
861F: B
862B: H
863H: I, G
864I: J
865G: J
866J: K
867K: L, M, N, O, P, Q
868M: L
869N: L
870O: L
871P: L
872L: R
873R: S, T
874S: Q
875T: Q
876Q
877"#,
878 r#"
879⍟─┬─┬─┬─┬─╮ A (B C D E F G)
880│ ● │ │ │ │ C (B)
881│ │ ● │ │ │ D (B)
882│ │ │ ● │ │ E (B)
883│ │ │ │ ● │ F (B)
884●─┴─┴─┴─╯ │ B (H)
885⊗─╮ ╭─────╯ H (I G)
886● │ │ I (J)
887│ ●─╯ G (J)
888●─╯ J (K)
889⊗─┬─┬─┬─┬─╮ K (L M N O P Q)
890│ ● │ │ │ │ M (L)
891│ │ ● │ │ │ N (L)
892│ │ │ ● │ │ O (L)
893│ │ │ │ ● │ P (L)
894●─┴─┴─┴─╯ │ L (R)
895⊗─╮ ╭─────╯ R (S T)
896● │ │ S (Q)
897│ ● │ T (Q)
898⊝─┴─╯ Q
899"#,
900 )?;
901
902 Ok(())
903 }
904
905 #[test]
906 fn test_deep_history_with_many_merges() -> color_eyre::Result<()> {
907 test_output(
908 r#"
909P: N, O
910O: M
911N: L, M
912M: K
913L: J, K
914K: E, J
915J: I, F
916I: C, H
917H: G
918F: C
919E: D
920C: A, B
921D: Q
922B: R
923R: A
924Q: X
925A: S, T
926T: U
927U: V
928V: W
929"#,
930 r#"
931⍟─╮ P (N O)
932│ ● O (M)
933⊗─┊─╮ N (L M)
934│ ●─╯ M (K)
935⊗─┊─╮ L (J K)
936│ ⊗─┴─╮ K (E J)
937⊗─┊─┬─╯ J (I F)
938⊗─┊─┊─╮ I (C H)
939│ │ │ ◌ H (G)
940│ │ ● │ F (C)
941│ ● │ │ E (D)
942⊗─┊─┴─┊─╮ C (A B)
943│ ● ╭─╯ │ D (Q)
944│ │ │ ●─╯ B (R)
945│ │ │ ● R (A)
946│ ◌ │ │ Q (X)
947⊗─┊─┊─┴─╮ A (S T)
948│ │ │ ●─╯ T (U)
949│ │ │ ● U (V)
950│ │ │ ◌ V (W)
951"#,
952 )?;
953
954 Ok(())
955 }
956
957 #[test]
958 fn test_highly_tangled_merge_graph() -> color_eyre::Result<()> {
959 test_output(
960 r#"
9611-l: 1-k, 2-d
9621-k: 1-j, 3-b, 4-a
9632-d: 1-i
9641-j: 1-i
9653-b: 1-i
9664-a: 1-i
9671-i: 1-h, 2-c
9681-h: 1-g, 5-a
9692-c: 2-b, 3-a
9701-g: 1-f
9715-a: 3-a
9722-b: 2-a, 1-e
9731-f: 1-e
9743-a: 1-c
9752-a: 1-b
9761-e: 1-d
9771-d: 1-c
9781-c: 1-b
9791-b: 1-a
9801-a
981"#,
982 r#"
983⍟─╮ 1-l (1-k 2-d)
984⊗─┊─┬─╮ 1-k (1-j 3-b 4-a)
985│ ● │ │ 2-d (1-i)
986● │ │ │ 1-j (1-i)
987│ │ ● │ 3-b (1-i)
988│ │ │ ● 4-a (1-i)
989⊗─┴─┴─┴─╮ 1-i (1-h 2-c)
990⊗─╮ ╭───╯ 1-h (1-g 5-a)
991│ │ ⊗─╮ 2-c (2-b 3-a)
992● │ │ │ 1-g (1-f)
993│ ● │ │ 5-a (3-a)
994│ │ ⊗─┊─╮ 2-b (2-a 1-e)
995● │ │ │ │ 1-f (1-e)
996│ ●─┊─╯ │ 3-a (1-c)
997│ │ ● ╭─╯ 2-a (1-b)
998●─┊─┊─╯ 1-e (1-d)
999● │ │ 1-d (1-c)
1000●─╯ │ 1-c (1-b)
1001●───╯ 1-b (1-a)
1002⊝ 1-a
1003"#,
1004 )?;
1005 Ok(())
1006 }
1007
1008 #[test]
1009 fn test_four_parent_octopus_merge() -> color_eyre::Result<()> {
1010 test_output(
1011 r#"
10121-c: 1-b, 2-a, 3-a, 4-a
10134-a: 1-a
10143-a: 1-a
10152-a: 1-a
10161-b: 1-a
10171-a
1018"#,
1019 r#"
1020⍟─┬─┬─╮ 1-c (1-b 2-a 3-a 4-a)
1021│ │ │ ● 4-a (1-a)
1022│ │ ● │ 3-a (1-a)
1023│ ● │ │ 2-a (1-a)
1024● │ │ │ 1-b (1-a)
1025⊝─┴─┴─╯ 1-a
1026"#,
1027 )?;
1028
1029 Ok(())
1030 }
1031
1032 #[test]
1033 fn test_branch_end_with_multi_parent_rejoin() -> color_eyre::Result<()> {
1034 test_output(
1035 r#"
1036 1-e: 1-c, 2-b, 3-b, 4-b
1037 4-b: 4-a
1038 3-b: 3-a
1039 2-b: 2-a
1040 2-a: 1-c, 3-a, 4-a
1041 4-a: 1-a
1042 3-a: 1-a
1043 1-c: 1-b
1044 1-b: 1-a
1045 1-a
1046"#,
1047 r#"
1048⍟─┬─┬─╮ 1-e (1-c 2-b 3-b 4-b)
1049│ │ │ ● 4-b (4-a)
1050│ │ ● │ 3-b (3-a)
1051│ ● │ │ 2-b (2-a)
1052│ ⊗─┊─┊─┬─╮ 2-a (1-c 3-a 4-a)
1053│ │ │ ●─┊─╯ 4-a (1-a)
1054│ │ ●─┊─╯ 3-a (1-a)
1055●─╯ │ │ 1-c (1-b)
1056● ╭─╯ │ 1-b (1-a)
1057⊝─┴───╯ 1-a
1058"#,
1059 )?;
1060
1061 Ok(())
1062 }
1063
1064 #[test]
1065 fn test_three_node_linear_history() -> color_eyre::Result<()> {
1066 test_output(
1067 r#"
1068a: b
1069b: c
1070c
1071"#,
1072 r#"
1073⦿ a (b)
1074● b (c)
1075⊝ c
1076"#,
1077 )?;
1078
1079 Ok(())
1080 }
1081
1082 #[test]
1083 fn test_basic_branch_and_merge() -> color_eyre::Result<()> {
1084 test_output(
1085 r#"
1086d: b, c
1087c: a
1088b: a
1089a
1090"#,
1091 r#"
1092⍟─╮ d (b c)
1093│ ● c (a)
1094● │ b (a)
1095⊝─╯ a
1096"#,
1097 )?;
1098
1099 Ok(())
1100 }
1101
1102 #[test]
1103 fn test_large_multi_merge() -> color_eyre::Result<()> {
1104 test_output(
1105 r#"
1106A: B, C, D, E
1107D: B
1108C: F
1109E: H
1110B: H, F
1111F: G
1112G: H
1113H: I
1114I: J, K, L, M, P, O
1115K: J
1116J: N
1117N: O
1118O: Q
1119Q: R, S
1120R: T, U
1121T: V, W
1122V: X, W
1123X: Y, Z
1124W
1125QQ: M
1126M: Y, A1, A2
1127P: Y
1128Z: Y
1129Y: A1
1130A1: A2
1131A2: S
1132S: U
1133U: A3
1134A3: A4, A5, A8
1135A4: A6, A5
1136A5: A7, A9
1137A6: AA, A9
1138AA
1139L
1140A7
1141A8
1142A9
1143"#,
1144 r#"
1145⍟─┬─┬─╮ A (B C D E)
1146│ │ ● │ D (B)
1147│ ● │ │ C (F)
1148│ │ │ ● E (H)
1149⊗─┊─┴─┊─╮ B (H F)
1150│ ●───┊─╯ F (G)
1151│ ● ╭─╯ G (H)
1152●─┴─╯ H (I)
1153⊗─┬─┬─┬─┬─╮ I (J K L M P O)
1154│ ● │ │ │ │ K (J)
1155●─╯ │ │ │ │ J (N)
1156● ╭─╯ │ │ │ N (O)
1157●─┊───┊─┊─╯ O (Q)
1158⊗─┊─╮ │ │ Q (R S)
1159⊗─┊─┊─┊─┊─╮ R (T U)
1160⊗─┊─┊─┊─┊─┊─╮ T (V W)
1161⊗─┊─┊─┊─┊─┊─┊─╮ V (X W)
1162⊗─┊─┊─┊─┊─┊─┊─┊─╮ X (Y Z)
1163│ │ │ │ │ │ ⊝─╯ │ W
1164│ │ │ │ │ │ ⦿ ╭─╯ QQ (M)
1165│ │ │ ⊗─┊─┊─┴─┊─┬─╮ M (Y A1 A2)
1166│ │ │ │ ● │ ╭─╯ │ │ P (Y)
1167│ │ │ │ │ │ ● ╭─╯ │ Z (Y)
1168●─┊─┊─┴─┴─┊─╯ │ ╭─╯ Y (A1)
1169●─┊─┊─────┊───╯ │ A1 (A2)
1170●─┊─┊─────┊─────╯ A2 (S)
1171●─┊─╯ ╭───╯ S (U)
1172●─┊───╯ U (A3)
1173⊗─┊─┬─╮ A3 (A4 A5 A8)
1174⊗─┊─┊─┊─╮ A4 (A6 A5)
1175│ │ ⊗─┊─┴─╮ A5 (A7 A9)
1176⊗─┊─┊─┊─╮ │ A6 (AA A9)
1177⊝ │ │ │ │ │ AA
1178 ⊝ │ │ │ │ L
1179 ⊝ │ │ │ A7
1180 ⊝ │ │ A8
1181 ⊝─╯ A9
1182"#,
1183 )?;
1184
1185 Ok(())
1186 }
1187
1188 #[test]
1189 fn test_orphan_isolated_node() -> color_eyre::Result<()> {
1190 test_output(
1191 r#"
1192i: h
1193h: g, d
1194g: f, e
1195f: c
1196e: c
1197d: c
1198c: b
1199b: a
1200"#,
1201 r#"
1202⦿ i (h)
1203⊗─╮ h (g d)
1204⊗─┊─╮ g (f e)
1205● │ │ f (c)
1206│ │ ● e (c)
1207│ ● │ d (c)
1208●─┴─╯ c (b)
1209◌ b (a)
1210"#,
1211 )?;
1212
1213 Ok(())
1214 }
1215
1216 #[test]
1217 fn test_cross_merge() -> color_eyre::Result<()> {
1218 test_output(
1219 r#"
12201-e: 1-d, 2-c, 3-b
12213-b: 3-a
12222-c: 2-b
12232-b: 2-a, 1-c, 3-a
12243-a: 1-a
12252-a: 1-b
12261-d: 1-c
12271-c: 1-b
12281-b: 1-a
12291-a
1230"#,
1231 r#"
1232⍟─┬─╮ 1-e (1-d 2-c 3-b)
1233│ │ ● 3-b (3-a)
1234│ ● │ 2-c (2-b)
1235│ ⊗─┊─┬─╮ 2-b (2-a 1-c 3-a)
1236│ │ ●─┊─╯ 3-a (1-a)
1237│ ● │ │ 2-a (1-b)
1238● │ │ │ 1-d (1-c)
1239●─┊─┊─╯ 1-c (1-b)
1240●─╯ │ 1-b (1-a)
1241⊝───╯ 1-a
1242"#,
1243 )?;
1244
1245 Ok(())
1246 }
1247
1248 #[test]
1249 fn test_cross_merge_fan_out() -> color_eyre::Result<()> {
1250 test_output(
1251 r#"
12521-e: 1-d, 2-c, 3-b
12531-d: 1-c
12542-c: 2-b
12553-b: 3-a
12562-b: 2-a, 1-c, 3-a
12571-c: 1-b
12582-a: 1-b
12593-a: 1-a
12601-b: 1-a
12611-a
1262"#,
1263 r#"
1264⍟─┬─╮ 1-e (1-d 2-c 3-b)
1265● │ │ 1-d (1-c)
1266│ ● │ 2-c (2-b)
1267│ │ ● 3-b (3-a)
1268│ ⊗─┊─┬─╮ 2-b (2-a 1-c 3-a)
1269●─┊─┊─╯ │ 1-c (1-b)
1270│ ● │ ╭─╯ 2-a (1-b)
1271│ │ ●─╯ 3-a (1-a)
1272●─╯ │ 1-b (1-a)
1273⊝───╯ 1-a
1274"#,
1275 )?;
1276
1277 Ok(())
1278 }
1279
1280 #[test]
1281 fn test_cross_merge_with_extra_crossover() -> color_eyre::Result<()> {
1282 test_output(
1283 r#"
12841-e: 1-d, 2-c, 3-b
12853-b: 3-a, 2-b
12862-c: 2-b
12872-b: 2-a, 1-c, 3-a
12883-a: 1-a
12892-a: 1-b
12901-d: 1-c
12911-c: 1-b
12921-b: 1-a
12931-a
1294"#,
1295 r#"
1296⍟─┬─╮ 1-e (1-d 2-c 3-b)
1297│ │ ⊗─╮ 3-b (3-a 2-b)
1298│ ● │ │ 2-c (2-b)
1299│ ⊗─┊─┴─┬─╮ 2-b (2-a 1-c 3-a)
1300│ │ ●───┊─╯ 3-a (1-a)
1301│ ● │ ╭─╯ 2-a (1-b)
1302● │ │ │ 1-d (1-c)
1303●─┊─┊─╯ 1-c (1-b)
1304●─╯ │ 1-b (1-a)
1305⊝───╯ 1-a
1306"#,
1307 )?;
1308
1309 Ok(())
1310 }
1311
1312 #[test]
1313 fn test_complex_cross_merge_with_multiple_crossovers() -> color_eyre::Result<()> {
1314 test_output(
1315 r#"
13161-e: 1-d, 2-c, 3-b, 1-b
13171-d: 1-c
13183-b: 3-a, 2-b, 1-b, 2-c
13192-c: 2-b
13202-b: 2-a, 1-c, 3-a, 1-b
13211-c: 1-b
13222-a: 1-b
13233-a: 1-a
13241-b
13251-a
1326"#,
1327 r#"
1328⍟─┬─┬─╮ 1-e (1-d 2-c 3-b 1-b)
1329● │ │ │ 1-d (1-c)
1330│ │ ⊗─┊─┬─┬─╮ 3-b (3-a 2-b 1-b 2-c)
1331│ ●─┊─┊─┊─┊─╯ 2-c (2-b)
1332│ ⊗─┊─┊─┴─┊─┬─┬─╮ 2-b (2-a 1-c 3-a 1-b)
1333●─┊─┊─┊───┊─╯ │ │ 1-c (1-b)
1334│ ● │ │ ╭─╯ ╭─╯ │ 2-a (1-b)
1335│ │ ●─┊─┊───╯ ╭─╯ 3-a (1-a)
1336⊝─┴─┊─┴─┴─────╯ 1-b
1337 ⊝ 1-a
1338"#,
1339 )?;
1340
1341 Ok(())
1342 }
1343
1344 #[test]
1345 fn test_dense_interwoven_merge_fixture_with_hook_avoiding_base_vertical() -> color_eyre::Result<()> {
1346 test_output(
1347 r#"
1348G: A, D, B, E, F
1349F: C, A, D, E, B
1350E: D, A
1351D: B, C
1352C: B, A
1353B: A
1354A
1355"#,
1356 r#"
1357⍟─┬─┬─┬─╮ G (A D B E F)
1358│ │ │ │ ⊗─┬─┬─┬─╮ F (C A D E B)
1359│ │ │ ⊗─┊─┊─┊─┴─┊─╮ E (D A)
1360│ ⊗─┊─┴─┊─┊─┴─╮ │ │ D (B C)
1361│ │ │ ⊗─┴─┊─┬─╯ │ │ C (B A)
1362│ ●─┴─┴───┊─┊───╯ │ B (A)
1363⊝─┴───────┴─┴─────╯ A
1364"#,
1365 )?;
1366 Ok(())
1367 }
1368
1369 #[test]
1370 fn test_dense_interwoven_merge_fixture_with_early_collapse_hook() -> color_eyre::Result<()> {
1371 test_output(
1372 r#"
1373 G: B, D, E, C, F, A
1374 F: B, E, C, A, D
1375 E: B, A, D
1376 D: C
1377 C: B, A
1378 B: A
1379 A
1380"#,
1381 r#"
1382⍟─┬─┬─┬─┬─╮ G (B D E C F A)
1383│ │ │ │ ⊗─┊─┬─┬─┬─╮ F (B E C A D)
1384│ │ ⊗─┊─┊─┊─┴─┊─┊─┊─┬─╮ E (B A D)
1385│ ●─┊─┊─┊─┊───┊─┊─┴─┊─╯ D (C)
1386│ ⊗─┊─┴─┊─┊─┬─╯ │ ╭─╯ C (B A)
1387●─┴─┴───╯ │ │ ╭─╯ │ B (A)
1388⊝─────────┴─┴─┴───╯ A
1389"#,
1390 )?;
1391 Ok(())
1392 }
1393
1394 #[test]
1395 fn test_multiple_disconnected_families() -> color_eyre::Result<()> {
1396 test_output(
1397 r#"
1398 H: F
1399 G: D
1400 F: E
1401 E: B
1402 D: C
1403 C
1404 B: A
1405 A
1406"#,
1407 r#"
1408⦿ H (F)
1409│ ⦿ G (D)
1410● │ F (E)
1411● │ E (B)
1412│ ● D (C)
1413│ ⊝ C
1414● B (A)
1415⊝ A
1416"#,
1417 )?;
1418 Ok(())
1419 }
1420
1421 #[test]
1422 fn test_stacked_merges_fixture_with_early_collapse() -> color_eyre::Result<()> {
1423 test_output(
1424 r#"
14251-d: 1-c
14262-a: 1-c
14273-a: 1-a
14281-c: 1-b, 1-a
14291-b: 1-a
14301-a
1431"#,
1432 r#"
1433⦿ 1-d (1-c)
1434│ ⦿ 2-a (1-c)
1435│ │ ⦿ 3-a (1-a)
1436⊗─┴─┊─╮ 1-c (1-b 1-a)
1437● ╭─╯ │ 1-b (1-a)
1438⊝─┴───╯ 1-a
1439"#,
1440 )?;
1441 Ok(())
1442 }
1443
1444 #[test]
1445 fn test_stacked_merges_fixture_cascade_out_with_all_crossover() -> color_eyre::Result<()> {
1446 test_output(
1447 r#"
14481-d: 1-c, 2-a
14492-a: 1-c
14503-a: 1-b, 4-a
14514-a: 1-b, 5-a
14525-a: 1-b, 1-a
14531-c: 1-b, 1-a
14541-b: 1-a
14551-a
1456"#,
1457 r#"
1458⍟─╮ 1-d (1-c 2-a)
1459│ ● 2-a (1-c)
1460│ │ ⍟─╮ 3-a (1-b 4-a)
1461│ │ │ ⊗─╮ 4-a (1-b 5-a)
1462│ │ │ │ ⊗─╮ 5-a (1-b 1-a)
1463⊗─┴─┊─┊─┊─┊─╮ 1-c (1-b 1-a)
1464●───┴─┴─╯ │ │ 1-b (1-a)
1465⊝─────────┴─╯ 1-a
1466"#,
1467 )?;
1468 Ok(())
1469 }
1470
1471 #[test]
1472 fn test_stacked_merges_fixture_cascade_out_with_one_crossover() -> color_eyre::Result<()> {
1473 test_output(
1474 r#"
14751-d: 1-c, 2-a
14762-a: 1-c
14771-c: 1-b, 1-a
14783-a: 1-b, 4-a
14794-a: 1-b, 5-a
14805-a: 1-b, 1-a
14811-b: 1-a
14821-a
1483"#,
1484 r#"
1485⍟─╮ 1-d (1-c 2-a)
1486│ ● 2-a (1-c)
1487⊗─┴─╮ 1-c (1-b 1-a)
1488│ ⍟─┊─╮ 3-a (1-b 4-a)
1489│ │ │ ⊗─╮ 4-a (1-b 5-a)
1490│ │ │ │ ⊗─╮ 5-a (1-b 1-a)
1491●─┴─┊─┴─╯ │ 1-b (1-a)
1492⊝───┴─────╯ 1-a
1493"#,
1494 )?;
1495 Ok(())
1496 }
1497
1498 #[test]
1499 fn test_high_fan_in_merge_fixture() -> color_eyre::Result<()> {
1500 test_output(
1501 r#"
15021-c: 1-b, 2-a, 3-b, 4-a, 1-a, 3-a
15032-a: 4-a, 3-a, 1-b, 1-a
15044-a: 1-a, 3-a, 1-b
15053-b: 1-a, 3-a
15063-a: 1-b
15071-b: 1-a
15081-a
1509"#,
1510 r#"
1511⍟─┬─┬─┬─┬─╮ 1-c (1-b 2-a 3-b 4-a 1-a 3-a)
1512│ ⊗─┊─┊─┊─┊─┬─┬─╮ 2-a (4-a 3-a 1-b 1-a)
1513│ ⊗─┊─┴─┊─┊─┊─┊─┊─┬─╮ 4-a (1-a 3-a 1-b)
1514│ │ ⊗─╮ │ │ │ │ │ │ │ 3-b (1-a 3-a)
1515│ │ │ ●─┊─┴─┴─┊─┊─╯ │ 3-a (1-b)
1516●─┊─┊─┴─┊─────┴─┊───╯ 1-b (1-a)
1517⊝─┴─┴───┴───────╯ 1-a
1518"#,
1519 )?;
1520 Ok(())
1521 }
1522
1523 #[test]
1524 fn test_merge_with_reintroduced_mainline_parent_collapse_root() -> color_eyre::Result<()> {
1525 test_output(
1526 r#"
1527 1-e: 1-d, 1-a, 2-a, 3-a, 1-c
1528 2-a: 3-a, 1-d, 1-a
1529 1-d: 1-c
1530 3-a: 1-a, 1-c
1531 1-c: 1-b
1532 1-b: 1-a
1533 1-a
1534"#,
1535 r#"
1536⍟─┬─┬─┬─╮ 1-e (1-d 1-a 2-a 3-a 1-c)
1537│ │ ⊗─┊─┊─┬─╮ 2-a (3-a 1-d 1-a)
1538●─┊─┊─┊─┊─╯ │ 1-d (1-c)
1539│ │ ⊗─┴─┊─╮ │ 3-a (1-a 1-c)
1540●─┊─┊───┴─╯ │ 1-c (1-b)
1541● │ │ ╭─────╯ 1-b (1-a)
1542⊝─┴─┴─╯ 1-a
1543"#,
1544 )?;
1545 Ok(())
1546 }
1547
1548 #[test]
1549 fn test_descending_merge_stack_cascade_collapse() -> color_eyre::Result<()> {
1550 test_output(
1551 r#"
1552 1b: 1a, 2a, 3b, 3a, 4a, 5a
1553 4a: 3a, 5a, 3b, 2a
1554 5a: 1a, 3b, 2a
1555 3b: 1a
1556 3a: 2c
1557 2c: 2b
1558 2b: 2a
1559 2a: 1a
1560 1a
1561"#,
1562 r#"
1563⍟─┬─┬─┬─┬─╮ 1b (1a 2a 3b 3a 4a 5a)
1564│ │ │ │ ⊗─┊─┬─┬─╮ 4a (3a 5a 3b 2a)
1565│ │ │ │ │ ⊗─┴─┊─┊─┬─╮ 5a (1a 3b 2a)
1566│ │ ●─┊─┊─┊───┴─┊─╯ │ 3b (1a)
1567│ │ │ ●─╯ │ ╭───╯ ╭─╯ 3a (2c)
1568│ │ │ ● ╭─╯ │ ╭───╯ 2c (2b)
1569│ │ │ ● │ ╭─╯ │ 2b (2a)
1570│ ●─┊─┴─┊─┴───╯ 2a (1a)
1571⊝─┴─┴───╯ 1a
1572"#,
1573 )?;
1574
1575 Ok(())
1576 }
1577
1578 #[test]
1579 fn test_multi_branch_rejoin_with_nested_side_branches() -> color_eyre::Result<()> {
1580 test_output(
1581 r#"
1582 1-d: 1-c, 2-a, 3-a, 4-b, 5-b
1583 5-b: 5-a
1584 5-a: 4-a
1585 4-b: 4-a
1586 4-a: 1-a, 1-c
1587 1-c: 1-b
1588 3-a: 1-b
1589 1-b: 1-a
1590 2-a: 1-a
1591 1-a
1592"#,
1593 r#"
1594⍟─┬─┬─┬─╮ 1-d (1-c 2-a 3-a 4-b 5-b)
1595│ │ │ │ ● 5-b (5-a)
1596│ │ │ │ ● 5-a (4-a)
1597│ │ │ ● │ 4-b (4-a)
1598│ │ │ ⊗─┴─╮ 4-a (1-a 1-c)
1599●─┊─┊─┊───╯ 1-c (1-b)
1600│ │ ● │ 3-a (1-b)
1601●─┊─╯ │ 1-b (1-a)
1602│ ● ╭─╯ 2-a (1-a)
1603⊝─┴─╯ 1-a
1604"#,
1605 )?;
1606
1607 Ok(())
1608 }
1609
1610 #[test]
1611 fn test_three_way_merge_with_vertical_crossover() -> color_eyre::Result<()> {
1612 test_output(
1613 r#"
1614 1-d: 1-c, 2-b, 3-b
1615 3-b: 3-a
1616 2-b: 2-a
1617 1-c: 1-b, 2-a, 3-a
1618 2-a: 1-b
1619 3-a: 1-a
1620 1-b: 1-a
1621 1-a
1622"#,
1623 r#"
1624⍟─┬─╮ 1-d (1-c 2-b 3-b)
1625│ │ ● 3-b (3-a)
1626│ ● │ 2-b (2-a)
1627⊗─┊─┊─┬─╮ 1-c (1-b 2-a 3-a)
1628│ ●─┊─╯ │ 2-a (1-b)
1629│ │ ●───╯ 3-a (1-a)
1630●─╯ │ 1-b (1-a)
1631⊝───╯ 1-a
1632"#,
1633 )?;
1634
1635 Ok(())
1636 }
1637
1638 #[test]
1639 fn test_left_leaning_octopus_merge() -> color_eyre::Result<()> {
1640 test_output(
1641 r#"
1642 1-c: 1-b
1643 2-b: 1-b, 4-a, 5-a, 2-a
1644 2-a: 1-a
1645 5-a: 1-a
1646 4-a: 1-a
1647 1-b: 1-a
1648 1-a
1649"#,
1650 r#"
1651⦿ 1-c (1-b)
1652│ ⍟─┬─┬─╮ 2-b (1-b 4-a 5-a 2-a)
1653│ │ │ │ ● 2-a (1-a)
1654│ │ │ ● │ 5-a (1-a)
1655│ │ ● │ │ 4-a (1-a)
1656●─╯ │ │ │ 1-b (1-a)
1657⊝───┴─┴─╯ 1-a
1658"#,
1659 )?;
1660
1661 Ok(())
1662 }
1663
1664 #[test]
1665 fn test_octopus_merge_with_crossover() -> color_eyre::Result<()> {
1666 test_output(
1667 r#"
1668 1-b: 1-a
1669 2-b: 2-a, 3-a, 4-a, 5-a
1670 5-a: 1-a
1671 4-a: 1-a
1672 3-a: 1-a
1673 2-a: 1-a
1674 1-a
1675"#,
1676 r#"
1677⦿ 1-b (1-a)
1678│ ⍟─┬─┬─╮ 2-b (2-a 3-a 4-a 5-a)
1679│ │ │ │ ● 5-a (1-a)
1680│ │ │ ● │ 4-a (1-a)
1681│ │ ● │ │ 3-a (1-a)
1682│ ● │ │ │ 2-a (1-a)
1683⊝─┴─┴─┴─╯ 1-a
1684"#,
1685 )?;
1686
1687 Ok(())
1688 }
1689
1690 #[test]
1691 fn test_left_leaning_octopus_merge_with_crossover() -> color_eyre::Result<()> {
1692 test_output(
1693 r#"
1694 1-c: 1-b
1695 2-b: 2-a, 3-a, 4-a, 1-b
1696 1-b: 1-a
1697 4-a: 1-a
1698 3-a: 1-a
1699 2-a: 1-a
1700 1-a
1701"#,
1702 r#"
1703⦿ 1-c (1-b)
1704│ ⍟─┬─┬─╮ 2-b (2-a 3-a 4-a 1-b)
1705●─┊─┊─┊─╯ 1-b (1-a)
1706│ │ │ ● 4-a (1-a)
1707│ │ ● │ 3-a (1-a)
1708│ ● │ │ 2-a (1-a)
1709⊝─┴─┴─╯ 1-a
1710"#,
1711 )?;
1712
1713 Ok(())
1714 }
1715
1716 #[test]
1717 fn test_long_history_with_repeated_branch_merge_cycles() -> color_eyre::Result<()> {
1718 test_output(
1719 r#"
1720 1-M: 1-L
1721 1-L: 1-K, 2-bb
1722 2-bb: 2-aa, 3-aa
1723 3-aa
1724 2-aa
1725 1-K: 1-J
1726 1-J: 1-I, 2-E
1727 2-E: 2-D, 3-B
1728 3-B: 3-A
1729 3-A: 2-B
1730 2-D: 2-C
1731 2-C: 1-F
1732 1-I: 1-H
1733 1-H: 1-G
1734 1-G: 1-F
1735 1-F: 1-E
1736 1-E: 1-D, 2-B
1737 2-B: 2-A
1738 2-A: 1-B
1739 1-D: 1-C
1740 1-C: 1-B
1741 1-B: 1-A
1742 1-A
1743"#,
1744 r#"
1745⦿ 1-M (1-L)
1746⊗─╮ 1-L (1-K 2-bb)
1747│ ⊗─╮ 2-bb (2-aa 3-aa)
1748│ │ ⊝ 3-aa
1749│ ⊝ 2-aa
1750● 1-K (1-J)
1751⊗─╮ 1-J (1-I 2-E)
1752│ ⊗─╮ 2-E (2-D 3-B)
1753│ │ ● 3-B (3-A)
1754│ │ ● 3-A (2-B)
1755│ ● │ 2-D (2-C)
1756│ ● │ 2-C (1-F)
1757● │ │ 1-I (1-H)
1758● │ │ 1-H (1-G)
1759● │ │ 1-G (1-F)
1760●─╯ │ 1-F (1-E)
1761⊗─╮ │ 1-E (1-D 2-B)
1762│ ●─╯ 2-B (2-A)
1763│ ● 2-A (1-B)
1764● │ 1-D (1-C)
1765● │ 1-C (1-B)
1766●─╯ 1-B (1-A)
1767⊝ 1-A
1768"#,
1769 )?;
1770
1771 Ok(())
1772 }
1773
1774 #[test]
1775 fn test_octopus_branches_followed_by_merge_with_hook_collapse() -> color_eyre::Result<()> {
1776 test_output(
1777 r#"
1778 1-d: 1-c, 2-b, 3-b
1779 3-b: 1-c, 2-a, 3-a, 4-a, 5-a
1780 2-b: 1-c, 2-a, 3-a, 4-a, 5-a
1781 5-a: 1-b
1782 4-a: 1-b
1783 3-a: 1-a, 1-b
1784 2-a: 1-a, 1-b
1785 1-c: 1-b
1786 1-b: 1-aa
1787 1-aa: 1-a
1788 1-a
1789"#,
1790 r#"
1791⍟─┬─╮ 1-d (1-c 2-b 3-b)
1792│ │ ⊗─┬─┬─┬─╮ 3-b (1-c 2-a 3-a 4-a 5-a)
1793│ ⊗─┊─┊─┊─┊─┊─┬─┬─┬─╮ 2-b (1-c 2-a 3-a 4-a 5-a)
1794│ │ │ │ │ │ ●─┊─┊─┊─╯ 5-a (1-b)
1795│ │ │ │ │ ●─┊─┊─┊─╯ 4-a (1-b)
1796│ │ │ │ ⊗─┊─┊─┊─┴─╮ 3-a (1-a 1-b)
1797│ │ │ ⊗─┊─┊─┊─┴─╮ │ 2-a (1-a 1-b)
1798●─┴─╯ │ │ │ │ ╭─╯ │ 1-c (1-b)
1799●─────┊─┊─┴─┴─┴───╯ 1-b (1-aa)
1800● ╭───╯ │ 1-aa (1-a)
1801⊝─┴─────╯ 1-a
1802"#,
1803 )?;
1804
1805 Ok(())
1806 }
1807
1808 #[test]
1809 fn test_branch_and_merge_near_root() -> color_eyre::Result<()> {
1810 test_output(
1811 r#"
1812 1-c: 1-b
1813 2-c: 1-b
1814 2-b: 2-a
1815 2-a: 1-a, 3-a
1816 3-a: 1-a
1817 1-b: 1-a
1818 1-a
1819"#,
1820 r#"
1821⦿ 1-c (1-b)
1822│ ⦿ 2-c (1-b)
1823│ │ ⦿ 2-b (2-a)
1824│ │ ⊗─╮ 2-a (1-a 3-a)
1825│ │ │ ● 3-a (1-a)
1826●─╯ │ │ 1-b (1-a)
1827⊝───┴─╯ 1-a
1828"#,
1829 )?;
1830
1831 Ok(())
1832 }
1833
1834 #[test]
1835 fn test_immediate_merge_after_parallel_branches() -> color_eyre::Result<()> {
1836 test_output(
1837 r#"
1838 F: C
1839 E: B
1840 D: A
1841 C: A, B
1842 B: A
1843 A
1844"#,
1845 r#"
1846⦿ F (C)
1847│ ⦿ E (B)
1848│ │ ⦿ D (A)
1849⊗─┊─┊─╮ C (A B)
1850│ ●─┊─╯ B (A)
1851⊝─┴─╯ A
1852"#,
1853 )?;
1854
1855 Ok(())
1856 }
1857
1858 #[test]
1859 fn test_branching_out_from_single_base() -> color_eyre::Result<()> {
1860 test_output(
1861 r#"
1862 E: A, B
1863 D: B
1864 C: B
1865 B: A
1866 A
1867"#,
1868 r#"
1869⍟─╮ E (A B)
1870│ │ ⦿ D (B)
1871│ │ │ ⦿ C (B)
1872│ ●─┴─╯ B (A)
1873⊝─╯ A
1874"#,
1875 )?;
1876
1877 Ok(())
1878 }
1879
1880 #[test]
1881 fn test_multiple_branches_merge_in_to_single_node() -> color_eyre::Result<()> {
1882 test_output(
1883 r#"
1884 F: B
1885 E: B, C, D
1886 D: A
1887 C: A
1888 B: A
1889 A
1890"#,
1891 r#"
1892⦿ F (B)
1893│ ⍟─┬─╮ E (B C D)
1894│ │ │ ● D (A)
1895│ │ ● │ C (A)
1896●─╯ │ │ B (A)
1897⊝───┴─╯ A
1898"#,
1899 )?;
1900
1901 Ok(())
1902 }
1903
1904 #[test]
1905 fn test_multiple_source_nodes_branching_in() -> color_eyre::Result<()> {
1906 test_output(
1907 r#"
1908 H: E
1909 G: E
1910 F: E, D, C
1911 E: B
1912 D: A
1913 C: A
1914 B: A
1915 A
1916"#,
1917 r#"
1918⦿ H (E)
1919│ ⦿ G (E)
1920│ │ ⍟─┬─╮ F (E D C)
1921●─┴─╯ │ │ E (B)
1922│ ●───╯ │ D (A)
1923│ │ ●───╯ C (A)
1924● │ │ B (A)
1925⊝─┴─╯ A
1926"#,
1927 )?;
1928
1929 Ok(())
1930 }
1931
1932 #[test]
1933 fn lane_collapse_shifts_lanes_left_when_possible_but_orphan_nodes_dont() -> color_eyre::Result<()> {
1934 test_output(
1935 r#"
1936X: A, B, C
1937A
1938B
1939C: D
1940D
1941"#,
1942 r#"
1943⍟─┬─╮ X (A B C)
1944⊝ │ │ A
1945 ⊝ │ B
1946●───╯ C (D)
1947⊝ D
1948"#,
1949 )?;
1950
1951 Ok(())
1952 }
1953
1954 #[test]
1955 fn orphan_nodes_are_marked_as_such_and_force_extra_lanes() -> color_eyre::Result<()> {
1956 test_output(
1957 r#"
1958X: Z
1959T
1960"#,
1961 r#"
1962◌ X (Z)
1963│ ⊝ T
1964"#,
1965 )?;
1966
1967 Ok(())
1968 }
1969}