renderdag/
box_drawing.rs

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
8use std::marker::PhantomData;
9
10use itertools::Itertools;
11
12use super::output::OutputRendererOptions;
13use super::render::Ancestor;
14use super::render::GraphRow;
15use super::render::LinkLine;
16use super::render::NodeLine;
17use super::render::PadLine;
18use super::render::Renderer;
19
20mod glyph {
21    pub(super) const SPACE: usize = 0;
22    pub(super) const HORIZONTAL: usize = 1;
23    pub(super) const PARENT: usize = 2;
24    pub(super) const ANCESTOR: usize = 3;
25    pub(super) const MERGE_LEFT: usize = 4;
26    pub(super) const MERGE_RIGHT: usize = 5;
27    pub(super) const MERGE_BOTH: usize = 6;
28    pub(super) const FORK_LEFT: usize = 7;
29    pub(super) const FORK_RIGHT: usize = 8;
30    pub(super) const FORK_BOTH: usize = 9;
31    pub(super) const JOIN_LEFT: usize = 10;
32    pub(super) const JOIN_RIGHT: usize = 11;
33    pub(super) const JOIN_BOTH: usize = 12;
34    pub(super) const TERMINATION: usize = 13;
35    pub(super) const COUNT: usize = 14;
36}
37
38const SQUARE_GLYPHS: [&str; glyph::COUNT] = [
39    "  ", "──", "│ ", "· ", "┘ ", "└─", "┴─", "┐ ", "┌─", "┬─", "┤ ", "├─", "┼─", "~ ",
40];
41
42const CURVED_GLYPHS: [&str; glyph::COUNT] = [
43    "  ", "──", "│ ", "╷ ", "╯ ", "╰─", "┴─", "╮ ", "╭─", "┬─", "┤ ", "├─", "┼─", "~ ",
44];
45
46const DEC_GLYPHS: [&str; glyph::COUNT] = [
47    "  ",
48    "\x1B(0qq\x1B(B",
49    "\x1B(0x \x1B(B",
50    "\x1B(0~ \x1B(B",
51    "\x1B(0j \x1B(B",
52    "\x1B(0mq\x1B(B",
53    "\x1B(0vq\x1B(B",
54    "\x1B(0k \x1B(B",
55    "\x1B(0lq\x1B(B",
56    "\x1B(0wq\x1B(B",
57    "\x1B(0u \x1B(B",
58    "\x1B(0tq\x1B(B",
59    "\x1B(0nq\x1B(B",
60    "~ ",
61];
62
63impl PadLine {
64    fn to_glyph(&self) -> usize {
65        match *self {
66            PadLine::Parent => glyph::PARENT,
67            PadLine::Ancestor => glyph::ANCESTOR,
68            PadLine::Blank => glyph::SPACE,
69        }
70    }
71}
72
73pub struct BoxDrawingRenderer<N, R>
74where
75    R: Renderer<N, Output = GraphRow<N>> + Sized,
76{
77    inner: R,
78    options: OutputRendererOptions,
79    extra_pad_line: Option<String>,
80    glyphs: &'static [&'static str; glyph::COUNT],
81    _phantom: PhantomData<N>,
82}
83
84impl<N, R> BoxDrawingRenderer<N, R>
85where
86    R: Renderer<N, Output = GraphRow<N>> + Sized,
87{
88    pub(crate) fn new(inner: R, options: OutputRendererOptions) -> Self {
89        BoxDrawingRenderer {
90            inner,
91            options,
92            extra_pad_line: None,
93            glyphs: &CURVED_GLYPHS,
94            _phantom: PhantomData,
95        }
96    }
97
98    pub fn with_square_glyphs(mut self) -> Self {
99        self.glyphs = &SQUARE_GLYPHS;
100        self
101    }
102
103    pub fn with_dec_graphics_glyphs(mut self) -> Self {
104        self.glyphs = &DEC_GLYPHS;
105        self
106    }
107}
108
109impl<N, R> Renderer<N> for BoxDrawingRenderer<N, R>
110where
111    N: Clone + Eq,
112    R: Renderer<N, Output = GraphRow<N>> + Sized,
113{
114    type Output = String;
115
116    fn width(&self, node: Option<&N>, parents: Option<&Vec<Ancestor<N>>>) -> u64 {
117        self.inner
118            .width(node, parents)
119            .saturating_mul(2)
120            .saturating_add(1)
121    }
122
123    fn reserve(&mut self, node: N) {
124        self.inner.reserve(node);
125    }
126
127    fn next_row(
128        &mut self,
129        node: N,
130        parents: Vec<Ancestor<N>>,
131        glyph: String,
132        message: String,
133    ) -> String {
134        let glyphs = self.glyphs;
135        let line = self.inner.next_row(node, parents, glyph, message);
136        let mut out = String::new();
137        let mut message_lines = line
138            .message
139            .lines()
140            .pad_using(self.options.min_row_height, |_| "");
141        let mut need_extra_pad_line = false;
142
143        // Render the previous extra pad line
144        if let Some(extra_pad_line) = self.extra_pad_line.take() {
145            out.push_str(extra_pad_line.trim_end());
146            out.push('\n');
147        }
148
149        // Render the nodeline
150        let mut node_line = String::new();
151        for entry in line.node_line.iter() {
152            match entry {
153                NodeLine::Node => {
154                    node_line.push_str(&line.glyph);
155                    node_line.push(' ');
156                }
157                NodeLine::Parent => node_line.push_str(glyphs[glyph::PARENT]),
158                NodeLine::Ancestor => node_line.push_str(glyphs[glyph::ANCESTOR]),
159                NodeLine::Blank => node_line.push_str(glyphs[glyph::SPACE]),
160            }
161        }
162        if let Some(msg) = message_lines.next() {
163            node_line.push(' ');
164            node_line.push_str(msg);
165        }
166        out.push_str(node_line.trim_end());
167        out.push('\n');
168
169        // Render the link line
170        #[allow(clippy::if_same_then_else)]
171        if let Some(link_row) = line.link_line {
172            let mut link_line = String::new();
173            for cur in link_row.iter() {
174                if cur.intersects(LinkLine::HORIZONTAL) {
175                    if cur.intersects(LinkLine::CHILD) {
176                        link_line.push_str(glyphs[glyph::JOIN_BOTH]);
177                    } else if cur.intersects(LinkLine::ANY_FORK)
178                        && cur.intersects(LinkLine::ANY_MERGE)
179                    {
180                        link_line.push_str(glyphs[glyph::JOIN_BOTH]);
181                    } else if cur.intersects(LinkLine::ANY_FORK)
182                        && cur.intersects(LinkLine::VERT_PARENT)
183                        && !line.merge
184                    {
185                        link_line.push_str(glyphs[glyph::JOIN_BOTH]);
186                    } else if cur.intersects(LinkLine::ANY_FORK) {
187                        link_line.push_str(glyphs[glyph::FORK_BOTH]);
188                    } else if cur.intersects(LinkLine::ANY_MERGE) {
189                        link_line.push_str(glyphs[glyph::MERGE_BOTH]);
190                    } else {
191                        link_line.push_str(glyphs[glyph::HORIZONTAL]);
192                    }
193                } else if cur.intersects(LinkLine::VERT_PARENT) && !line.merge {
194                    let left = cur.intersects(LinkLine::LEFT_MERGE | LinkLine::LEFT_FORK);
195                    let right = cur.intersects(LinkLine::RIGHT_MERGE | LinkLine::RIGHT_FORK);
196                    match (left, right) {
197                        (true, true) => link_line.push_str(glyphs[glyph::JOIN_BOTH]),
198                        (true, false) => link_line.push_str(glyphs[glyph::JOIN_LEFT]),
199                        (false, true) => link_line.push_str(glyphs[glyph::JOIN_RIGHT]),
200                        (false, false) => link_line.push_str(glyphs[glyph::PARENT]),
201                    }
202                } else if cur.intersects(LinkLine::VERT_PARENT | LinkLine::VERT_ANCESTOR)
203                    && !cur.intersects(LinkLine::LEFT_FORK | LinkLine::RIGHT_FORK)
204                {
205                    let left = cur.intersects(LinkLine::LEFT_MERGE);
206                    let right = cur.intersects(LinkLine::RIGHT_MERGE);
207                    match (left, right) {
208                        (true, true) => link_line.push_str(glyphs[glyph::JOIN_BOTH]),
209                        (true, false) => link_line.push_str(glyphs[glyph::JOIN_LEFT]),
210                        (false, true) => link_line.push_str(glyphs[glyph::JOIN_RIGHT]),
211                        (false, false) => {
212                            if cur.intersects(LinkLine::VERT_ANCESTOR) {
213                                link_line.push_str(glyphs[glyph::ANCESTOR]);
214                            } else {
215                                link_line.push_str(glyphs[glyph::PARENT]);
216                            }
217                        }
218                    }
219                } else if cur.intersects(LinkLine::LEFT_FORK)
220                    && cur.intersects(LinkLine::LEFT_MERGE | LinkLine::CHILD)
221                {
222                    link_line.push_str(glyphs[glyph::JOIN_LEFT]);
223                } else if cur.intersects(LinkLine::RIGHT_FORK)
224                    && cur.intersects(LinkLine::RIGHT_MERGE | LinkLine::CHILD)
225                {
226                    link_line.push_str(glyphs[glyph::JOIN_RIGHT]);
227                } else if cur.intersects(LinkLine::LEFT_MERGE)
228                    && cur.intersects(LinkLine::RIGHT_MERGE)
229                {
230                    link_line.push_str(glyphs[glyph::MERGE_BOTH]);
231                } else if cur.intersects(LinkLine::LEFT_FORK)
232                    && cur.intersects(LinkLine::RIGHT_FORK)
233                {
234                    link_line.push_str(glyphs[glyph::FORK_BOTH]);
235                } else if cur.intersects(LinkLine::LEFT_FORK) {
236                    link_line.push_str(glyphs[glyph::FORK_LEFT]);
237                } else if cur.intersects(LinkLine::LEFT_MERGE) {
238                    link_line.push_str(glyphs[glyph::MERGE_LEFT]);
239                } else if cur.intersects(LinkLine::RIGHT_FORK) {
240                    link_line.push_str(glyphs[glyph::FORK_RIGHT]);
241                } else if cur.intersects(LinkLine::RIGHT_MERGE) {
242                    link_line.push_str(glyphs[glyph::MERGE_RIGHT]);
243                } else {
244                    link_line.push_str(glyphs[glyph::SPACE]);
245                }
246            }
247            if let Some(msg) = message_lines.next() {
248                link_line.push(' ');
249                link_line.push_str(msg);
250            }
251            out.push_str(link_line.trim_end());
252            out.push('\n');
253        }
254
255        // Render the term line
256        if let Some(term_row) = line.term_line {
257            let term_strs = [glyphs[glyph::PARENT], glyphs[glyph::TERMINATION]];
258            for term_str in term_strs.iter() {
259                let mut term_line = String::new();
260                for (i, term) in term_row.iter().enumerate() {
261                    if *term {
262                        term_line.push_str(term_str);
263                    } else {
264                        term_line.push_str(glyphs[line.pad_lines[i].to_glyph()]);
265                    }
266                }
267                if let Some(msg) = message_lines.next() {
268                    term_line.push(' ');
269                    term_line.push_str(msg);
270                }
271                out.push_str(term_line.trim_end());
272                out.push('\n');
273            }
274            need_extra_pad_line = true;
275        }
276
277        let mut base_pad_line = String::new();
278        for entry in line.pad_lines.iter() {
279            base_pad_line.push_str(glyphs[entry.to_glyph()]);
280        }
281
282        // Render any pad lines
283        for msg in message_lines {
284            let mut pad_line = base_pad_line.clone();
285            pad_line.push(' ');
286            pad_line.push_str(msg);
287            out.push_str(pad_line.trim_end());
288            out.push('\n');
289            need_extra_pad_line = false;
290        }
291
292        if need_extra_pad_line {
293            self.extra_pad_line = Some(base_pad_line);
294        }
295
296        out
297    }
298}
299
300#[cfg(test)]
301mod tests {
302    use super::super::test_fixtures;
303    use super::super::test_fixtures::TestFixture;
304    use super::super::test_utils::render_string;
305    use super::super::test_utils::render_string_with_order;
306    use crate::GraphRowRenderer;
307
308    fn render(fixture: &TestFixture) -> String {
309        let mut renderer = GraphRowRenderer::new().output().build_box_drawing();
310        render_string(fixture, &mut renderer)
311    }
312
313    #[test]
314    fn basic() {
315        assert_eq!(
316            render(&test_fixtures::BASIC),
317            r#"
318            o  C
319            │
320            o  B
321            │
322            o  A"#
323        );
324    }
325
326    #[test]
327    fn branches_and_merges() {
328        assert_eq!(
329            render(&test_fixtures::BRANCHES_AND_MERGES),
330            r#"
331            o  W
332            │
333            o    V
334            ├─╮
335            │ o    U
336            │ ├─╮
337            │ │ o  T
338            │ │ │
339            │ o │  S
340            │   │
341            o   │  R
342            │   │
343            o   │  Q
344            ├─╮ │
345            │ o │    P
346            │ ├───╮
347            │ │ │ o  O
348            │ │ │ │
349            │ │ │ o    N
350            │ │ │ ├─╮
351            │ o │ │ │  M
352            │ │ │ │ │
353            │ o │ │ │  L
354            │ │ │ │ │
355            o │ │ │ │  K
356            ├───────╯
357            o │ │ │  J
358            │ │ │ │
359            o │ │ │  I
360            ├─╯ │ │
361            o   │ │  H
362            │   │ │
363            o   │ │  G
364            ├─────╮
365            │   │ o  F
366            │   ├─╯
367            │   o  E
368            │   │
369            o   │  D
370            │   │
371            o   │  C
372            ├───╯
373            o  B
374            │
375            o  A"#
376        );
377    }
378
379    #[test]
380    fn octopus_branch_and_merge() {
381        assert_eq!(
382            render(&test_fixtures::OCTOPUS_BRANCH_AND_MERGE),
383            r#"
384            o      J
385            ├─┬─╮
386            │ │ o  I
387            │ │ │
388            │ o │      H
389            ╭─┼─┬─┬─╮
390            │ │ │ │ o  G
391            │ │ │ │ │
392            │ │ │ o │  E
393            │ │ │ ├─╯
394            │ │ o │  D
395            │ │ ├─╮
396            │ o │ │  C
397            │ ├───╯
398            o │ │  F
399            ├─╯ │
400            o   │  B
401            ├───╯
402            o  A"#
403        );
404    }
405
406    #[test]
407    fn reserved_column() {
408        assert_eq!(
409            render(&test_fixtures::RESERVED_COLUMN),
410            r#"
411              o  Z
412              │
413              o  Y
414              │
415              o  X
416            ╭─╯
417            │ o  W
418            ├─╯
419            o  G
420            │
421            o    F
422            ├─╮
423            │ o  E
424            │ │
425            │ o  D
426            │
427            o  C
428            │
429            o  B
430            │
431            o  A"#
432        );
433    }
434
435    #[test]
436    fn ancestors() {
437        assert_eq!(
438            render(&test_fixtures::ANCESTORS),
439            r#"
440              o  Z
441              │
442              o  Y
443            ╭─╯
444            o  F
445            ╷
446            ╷ o  X
447            ╭─╯
448            │ o  W
449            ├─╯
450            o  E
451            ╷
452            o    D
453            ├─╮
454            │ o  C
455            │ ╷
456            o ╷  B
457            ├─╯
458            o  A"#
459        );
460    }
461
462    #[test]
463    fn split_parents() {
464        assert_eq!(
465            render(&test_fixtures::SPLIT_PARENTS),
466            r#"
467                  o  E
468            ╭─┬─┬─┤
469            ╷ o │ ╷  D
470            ╭─┴─╮ ╷
471            │   o ╷  C
472            │   ├─╯
473            o   │  B
474            ├───╯
475            o  A"#
476        );
477    }
478
479    #[test]
480    fn terminations() {
481        assert_eq!(
482            render(&test_fixtures::TERMINATIONS),
483            r#"
484              o  K
485              │
486              │ o  J
487              ├─╯
488              o    I
489            ╭─┼─╮
490            │ │ │
491            │ ~ │
492            │   │
493            o   │  E
494            │   │
495            │   o  H
496            ├───╯
497            o  D
498            │
499            ~
500            
501            o  C
502            │
503            o  B
504            │
505            ~"#
506        );
507    }
508
509    #[test]
510    fn long_messages() {
511        assert_eq!(
512            render(&test_fixtures::LONG_MESSAGES),
513            r#"
514            o      F
515            ├─┬─╮  very long message 1
516            │ │ │  very long message 2
517            │ │ ~  very long message 3
518            │ │
519            │ │    very long message 4
520            │ │    very long message 5
521            │ │    very long message 6
522            │ │
523            │ o  E
524            │ │
525            │ o  D
526            │ │
527            o │  C
528            ├─╯  long message 1
529            │    long message 2
530            │    long message 3
531            │
532            o  B
533            │
534            o  A
535            │  long message 1
536            ~  long message 2
537               long message 3"#
538        );
539    }
540
541    #[test]
542    fn different_orders() {
543        let order = |order: &str| {
544            let order = order.matches(|_: char| true).collect::<Vec<_>>();
545            let mut renderer = GraphRowRenderer::new().output().build_box_drawing();
546            render_string_with_order(&test_fixtures::ORDERS1, &mut renderer, Some(&order))
547        };
548
549        assert_eq!(
550            order("KJIHGFEDCBZA"),
551            r#"
552            o    K
553            ├─╮
554            │ o    J
555            │ ├─╮
556            │ │ o    I
557            │ │ ├─╮
558            │ │ │ o    H
559            │ │ │ ├─╮
560            │ │ │ │ o    G
561            │ │ │ │ ├─╮
562            o │ │ │ │ │  F
563            │ │ │ │ │ │
564            │ o │ │ │ │  E
565            ├─╯ │ │ │ │
566            │   o │ │ │  D
567            ├───╯ │ │ │
568            │     o │ │  C
569            ├─────╯ │ │
570            │       o │  B
571            ├───────╯ │
572            │         o  Z
573            │
574            o  A"#
575        );
576
577        assert_eq!(
578            order("KJIHGZBCDEFA"),
579            r#"
580            o    K
581            ├─╮
582            │ o    J
583            │ ├─╮
584            │ │ o    I
585            │ │ ├─╮
586            │ │ │ o    H
587            │ │ │ ├─╮
588            │ │ │ │ o    G
589            │ │ │ │ ├─╮
590            │ │ │ │ │ o  Z
591            │ │ │ │ │
592            │ │ │ │ o  B
593            │ │ │ │ │
594            │ │ │ o │  C
595            │ │ │ ├─╯
596            │ │ o │  D
597            │ │ ├─╯
598            │ o │  E
599            │ ├─╯
600            o │  F
601            ├─╯
602            o  A"#
603        );
604
605        // Keeping the p1 branch the longest path (KFEDCBA) is a reasonable
606        // optimization for a cleaner graph (less columns, more text space).
607        assert_eq!(
608            render(&test_fixtures::ORDERS2),
609            r#"
610            o    K
611            ├─╮
612            │ o  J
613            │ │
614            o │    F
615            ├───╮
616            │ │ o  I
617            │ ├─╯
618            o │    E
619            ├───╮
620            │ │ o  H
621            │ ├─╯
622            o │    D
623            ├───╮
624            │ │ o  G
625            │ ├─╯
626            o │    C
627            ├───╮
628            │ │ o  Z
629            │ │
630            o │  B
631            ├─╯
632            o  A"#
633        );
634
635        // Try to use the ORDERS2 order. However, the parent ordering in the
636        // graph is different, which makes the rendering different.
637        //
638        // Note: it's KJFIEHDGCZBA in the ORDERS2 graph. To map it to ORDERS1,
639        // follow:
640        //
641        // ORDERS1: KFJEIDHCGBZA
642        // ORDERS2: KJFIEHDGCBZA
643        //
644        // And we get KFJEIDHCGZBA.
645        assert_eq!(
646            order("KFJEIDHCGZBA"),
647            r#"
648            o    K
649            ├─╮
650            o │  F
651            │ │
652            │ o    J
653            │ ├─╮
654            │ o │  E
655            ├─╯ │
656            │   o  I
657            │ ╭─┤
658            │ │ o  D
659            ├───╯
660            │ o    H
661            │ ├─╮
662            │ o │  C
663            ├─╯ │
664            │   o  G
665            │ ╭─┤
666            │ o │  Z
667            │   │
668            │   o  B
669            ├───╯
670            o  A"#
671        );
672    }
673}
renderdag/box_drawing.rs

renderdag/
box_drawing.rs
