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

renderdag/
box_drawing.rs
