Day 28: Who controls whom

Option 1: You call the tree

What seemed like the simplest option was to have a Tree struct that you call into with various methods, representing the tree structure over time. In the past I’ve referred to this as “church encoding”. I’m not sure if that is really the right term, but I don’t know of a better one. This is the option that I made the most progress with, and is fairly straightforward. Here’s the beginning of its definition:

pub(crate) struct Tree {
    depth: u8
}

impl Tree {
    fn new(area) -> Tree {
        Tree { depth: 0 }
    }

    fn ascend(&mut self) {
        self.depth -= 1;
    }

    fn descend(&mut self) {
        self.depth += 1;
    }

    fn render_node(widget: impl Widget) {
        todo!()
    }
}

You would use this structure by calling ascend, descend, and render_node in patterns that reflect the tree structure. So the above example would look something like this:

let t = Tree::new();
for channel in channels {
    t.render_node(channel.title);

    t.descend();
    for item in channel.items {
        t.render_node(item.title);
        t.descend();
        t.render_node(item.progress);
        t.ascend();
    }
    t.ascend();
}

This approach works, but has a few shortcomings. For one, we have to keep track of these descend() and ascend() calls carefully. Leaving one out would cause the entire rest of the tree to render incorrectly. We can work around this by instead providing a single branch function which does both a descend() and ascend() for us:

let t = Tree::new();
for channel in channels {
    t.render_node(channel.title);

    t.branch(|| {
        for item in channel.items {
            t.render_node(item.title);
            t.branch(|| {
                t.render_node(item.progress);
            });
        }
    });
}

The second problem is that this is not a particularly natural way to use Ratatui, which conceptually wants you to have a series of widgets that form a render hierarchy. From this point of view, the calls to render for each child widget would be nested within the tree’s own render() call. This is conceptually elegant, but can also easily lead to a lot of short-lived allocations, as we discussed in a previous entry. There is a way around this, though, as we will explore next.

Option 2: The tree calls you

If we want our new tree abstraction to be able to render each of its children in turn, but not to have any knowledge of the rest of our application, then we need to create a seam between them. We could try to do this as follows:

trait TreeWidget: Widget {
    type Child: TreeWidget;

    fn children<V>(&self, visitor: V) -> impl Iterator<Item=Self::Child>;
}

As an aside, I was surprised that Rust’s type system allows for this. Both the use of impl Iterator in the return type of a trait method and the type bounds on the associated type (Child: TreeWidget). It does seem to type check though, which is neat!

One shortcoming with this approach is that it requires the children of each widget to have the same type. This isn’t a limitation of the previous approach, where every render_node call could generate specialized code for a generic type. I don’t think this would be a problem in practice, though, since the actual hierarchy is constant: Channels > Items > Status.

You would use this trait by first wrapping some type in a Tree widget, then rendering it as you would any other with Ratatui:

frame.render(Tree(&self));

I plan to explore this option further in tomorrow’s session.