Support multiple layout algorithms

[alice-i-cecile]

Tracking Issues:

• Add feature flag for Flexbox: Move flexbox code behind a default feature #298
• CSS Grid: Support CSS Grid #204
• Morphorm: Support Morphorm/Subform layout #308

This library will be dramatically more useful if it can be used to support multiple layout strategies. This is useful because:

• it centralizes community effort
• it enables fair benchmarks
• it lets users easily swap out approaches
• it creates the potential for blended layouts in the same app

Must have:

• each layout algorithm lives behind its own feature flag
• this crate provides a relatively unified interface to them
  • a trait seems like the natural fit here

Nice to have:

• low or zero abstraction overhead
• the ability to nest multiple distinct layout strategies, ala flutter
• competitive benchmarks between the different strategies
• rosetta-stone comparisons of practical examples, demonstrating how to create the same / comparable layouts in different paradigms
• users can create their own layout algorithms using our primitives in an interoperable way

Possible layout algorithms we may want to support:

• hstack / vstack
• Swift-UI style
• Flutter style
• CSS grid
• Morphorm
• Cassowary

[CobaltCause]

I have some ideas for this, encoded in my now-dead attempt at a layouting engine. (The name might sound familiar; I never made this public till just now because it was never able to do much of anything.) The way it supported multiple layouts was by making a distinction between container nodes and item (aka leaf) nodes.

Nodes have a method that can convert itself into a container, and that method decides which layouting algorithm its items will be subject to. So for example, you'd have a flex method, a grid method, and so on. Actual code example here. Items are added to a &mut container type returned by the flex/grid/whatever method that are defined like this, for example, which keeps the interface pretty uniform for all layout algorithms.

Here's what creating an item looks like using this API, and here's creating a container. There are some other examples in files in the view folder in that repo as well. This API was mainly designed with the Elm architecture in mind (since iced uses that to great success and I was trying to copy the developer ergonomics it provides).

Nested layouts: Since the layouting method is decided at layout-time, you can easily (from the user's perspective, anyway) support nested distinct layouts.

Feature flags: It should be possible to put these methods and their configuration types behind feature flags.

Unified interface: The interface would be unified via the return type from the methods like Node::flex, we could theoretically consume the original crate's configuration through arguments to those methods and return a custom type that can receive that container's children.

Custom algorithms: I haven't considered this at all but as a quick guess I'm imagining one could implement a method like Node::custom_layout<T, U>(&mut self, layout: U, solver: /* some sort of callback capable of processing T with U options*/) -> &mut T where T would be like flex::Children from the code linked above, which would then be used to add children, and U which is the configuration of the container itself.

Performance: I have absolutely no idea since I never actually got any of this working to a point where it's worth benchmarking 😅 .

[alice-i-cecile]

That's very promising: I think the Container vs. Leaf distinction is quite natural, and should transfer well across algorithms.

The Hierarchy and [Node]) traits by @geom3trik from Morphorm looks like interesting prior art too.

[geom3trik]

The Hierarchy and [Node]) traits by @geom3trik from Morphorm looks like interesting prior art too.

I realised recently that a better approach is to just have the Node trait but with some associated types for Store, which represents the case where node properties are not owned by the node, and for Tree, which represents the case where the hierarchy is stored externally.

Then there's just a method on the node trait for returning an iterator on the children, and any layout algorithm can be described recursively.

The Hierarchy trait before required that the tree be described separately. This new approach allows for both the case where nodes own their properties and children, and also the case where they are stored externally.

[CobaltCause]

The Hierarchy and [Node]) traits by @geom3trik from Morphorm looks like interesting prior art too.

Ah; at first I was confused what purpose a trait for nodes would serve, that example helped me understand. That seems to be using an ECS architecture, and a trait makes sense for that, since all the objects are stored "flatly".

My project organized things hierarchically with enums, so naturally I also used an enum for that: see the definition, the use in Node, and the use in the actual solver. For custom algorithm support, a Custom variant with some generics would probably do the trick.

I guess it depends on whether this project wants to do ECS, something like what I've come up with, or something else entirely. (I don't have any real preference for any particular approach since I haven't really explored the alternatives.)

[geom3trik]

Ah; at first I was confused what purpose a trait for nodes would serve, that example helped me understand. That seems to be using an ECS architecture, and a trait makes sense for that, since all the objects are stored "flatly".

That is definitely true for the Hierarchy trait. However, as I mentioned above, my new approach that I'm working on just has a trait for nodes which works for both an ECS approach and for where nodes own their children. I think a trait-based approach like this could be used to abstract an interface for different algorithms.

Using enums to express the tree isn't something I had thought of, but I guess that only really makes sense if you want to force a distinction between containers and non-containers. In morphorm, any node can contain children and then it's up to the user to design an API where it's possible or not to add those children to a node.

[Andrewp2]

Possible layout algorithms we may want to support:

hstack / vstack
Swift-style
CSS grid
Morphorm
Cassowary

Any specific ordering or prioritization for these? I might tackle one if I have some time.

[alice-i-cecile]

CSS grid is probably the highest priority due to its popularity. After that, my personal favorite is Morphorm, then Cassowary.

Once those three are in we can see what sort of gaps are still left; I don't think there's a lot of need to support very similar APIs.

EDIT: the other dead simple "layout algorithm" I want is the identity layout algorithm. Users just pass in absolute positionings and we return them. This is both a useful escape hatch and serves as a great test ground for the broader architecture.

[tigregalis]

Could it support a Flutter-style (one pass) layout algorithm? Or is that covered by one of the others? I refer to: https://medium.com/snapp-mobile/flutter-anatomy-layout-internals-part-1-de99b772ab99

[TimJentzsch]

CSS grid also works in combination with Flexbox, I use the gap properly quite often with Flexbox during web development.
I wonder how we can make some algorithms work in combination and some not, where it makes sense.

[alice-i-cecile]

Mhmm. I think we'll want a few diverse layout algorithms in place first, then start experimenting with patterns there.

If we need to define pairwise compatibility rules, we can use a generic trait that takes the other layout algorithm, ala From.

[nicoburns]

Regarding leaf nodes, would it make sense for them to be "just another layout type"? So you end up with:

enum Display {
     Flexbox,
     CSSGrid,
     Leaf,
     // More layout algorithms here...
}

where the Leaf layout type works similarly to MeasureFunc in the current codebase which takes a bunch of context (we may want to include more than are currently passed in - such as min/max constraints) as parameters (which may used or ignored as the consumer of the library sees fit) and returns a width/height (the mechanism behind the calculation being out of the scope of this library).

Leaf could also potentially be called Custom, as I believe it would also serve as an escape hatch for integrating additional layout algorithms with Taffy.

[alice-i-cecile]

Oh that's a cool idea. The idea of "Leaf" as a layout algorithm is pretty appealing 🤔 I'm a bit nervous to use an enum rather than a trait here: like you say, I want an escape hatch for custom layouts if we can get away with it.

[Weibye]

More relevant conversation #205 (comment)

[nicoburns]

I've done quite a bit of research into and thinking about this, and I think I've now gotten to a settled viewpoint on this topic which I will write out below.

Two types of "layout algorithm"

Considering the "layout algorithms" listed in the top-level description of this (and a couple of others that I'm adding in), I believe they fall into two categories:

True algorithms

These are well-defined algorithms that specify a specific way to size and position boxes in 2D space. Included in this category is:

• Flexbox
• CSS Grid (Support CSS Grid #204)
• Any other CSS layout algorithms we may wish to implement such as table layout or flow (block and inline) layout
• Morphorm/Subform (Support Morphorm/Subform layout #308)
• hstack/vstack/zstack (although these are very simple and may or may not be worth including in Taffy)
• Apple AutoLayout/Cassowary (which is very complex and probably won't be implemented anytime soon).

Side note: "Cassowary" is the name of the underlying constaint solving algorithm (which is what the cassowary crate implements), but we would want an implementation of 2D layout on top of that (that would most likely work similarly to Apple's AutoLayout). There is not currently an implementation of this in Rust.

I believe it would make sense to implement these algorithms as part of Taffy itself (to the extent that we have the engineering resources to do so and the specific algorithm is considered priority). And indeed we are already making good progress on this with a CSS Grid implementation nearly complete, and work on Morphorm scoped out.

Layout Frameworks

On the other hand we have broader "layout frameworks". These do not prescribe a specific way of doing layout, but rather provide a framwork within which individual widgets can implement their own layout algorithm. These include:

• SwiftUI
• Flutter
• Xilem's (and Druid's) layout system
• Iced's layout system

These frameworks vary in exactly how they implement layout. On one end of the spectrum you have Flutter which has a pretty complete Flexbox implementation as a widget. On the other end of the spectrum you have Swift UI which uses simplistic hstack/vstack layout, but combines that with lot of "widget combinators" like padding/border to achieve complex layouts (so in SwiftUI there is a seperate widget specifically for applying padding, another one for borders, etc). What they have in common is that they are extensible. And specifically, they are extensible in end-user code. While end-users will commonly use the built-in "vocabulary widgets" (hstack, padding, etc) to define their layouts, they are also free to write their own widgets which implement custom algorithms (and indeed there are libraries like SwiftYogaKit that implement Flexbox as a SwiftUI widget)

I believe that the way to support these frameworks in Taffy would not be to attempt to implement the specific vocabulary types (there are too many of them, and most of them are so trivial to implement that potential consumers of Taffy are unlikely to consider gaining implementations of them worth the pain of integrating with a 3rd party library). Rather, supporting these frameworks would consist in having excellent support for custom layout algorithms (and would probably also constitute a solution to #57).

Supporting custom layout modes/algorithms

Rethinking our approach

The crux of this issue then becomes how best to support custom layout algorithms. And I think I have had a bit of a revelation in my thinking around this issue. So far, most of our discussion (or at least most of my thinking) has been about how to cram support for custom layout modes into Taffy. Which is awkward because it's hard to know what the requirements for the custom layout modes will be so you end trying to design a super-generic solution which quickly becomes very complex, cumbersome, or simply not actually possible to implement. My revelation (inspired by how Flutter and Druid integrate flexbox-like layout) is that we should flip our approach on it's head: rather than trying to make it possible to embed support for custom layout modes into Taffy, we should instead make it straightforward for consumers of Taffy to embed Taffy (and specifically Taffy's layout algorithms) into their own layout systems which may implement Taffy layout modes as well as their own custom modes (e.g. text layout, image layout, and/or any SwiftUI style combinators)

Extending the LayoutTree trait

As of #246, Taffy trampolines all calls to measure child node size or perform layout on a child node through the taffy::compute::compute_node_layout function. This allows us to easily support multiple layout alogrithms like CSS Grid by having a match statement in the compute_node_layout function that switches on the Display property and delegates layout to the relevant algorithm.

I believe the key change we need to make to enable Taffy to be more easily embedded is to add the compute_node_layout function to the LayoutTree trait, which will mean that (for consumers of Taffy using a custom implementation of LayoutTree) we effectively yield control flow back to the consumer of Taffy after running the Taffy algorithm for a single node, and allow them to intercept calls to measure/layout child nodes. Those consumers can then implement their own custom logic to determine how to layout that node. This will likely involve calling straight back into Taffy in the case that the child node also uses a layout algorithm that Taffy implements, but gives them a straightforward way to call into arbitrary code with full access to their own storage/state in cases where the child node is something like a text node or some other layout mode that Taffy doesn't support.

More specifically (and again inspired by Druid/Xilem), I think we ought to split the compute_node_layout method into separate measure_size and perform_layout methods, which will correspond to calling the existing compute_node_layout function with the run_mode parameters RunMode::ComputeSize and RunMode::PerformLayout respectively (the run_mode parameter would then be removed). Additionally (motivated by the need to support baseline alignment in CSS Grid and custom layout algorithms), I think we should add a 3rd method compute_baseline which will be used to expose text baselines for baseline alignment (we can probably provide a default impl for this as CSS provides a simple algorthm for computing the baseline of an element which doesn't really have one).

Putting all that together, my proposal is to add the following methods to LayoutTree (exact details subject to change):

fn measure_size(
    &mut self,
    node: Node,
    known_dimensions: Size<Option<f32>>,
    parent_size: Size<Option<f32>>,
    available_space: Size<AvailableSpace>,
    sizing_mode: SizingMode,
) -> Size<f32>

fn perform_layout(
    &mut self,
    node: Node,
    known_dimensions: Size<f32>,
    parent_size: Size<f32>,
    available_space: Size<AvailableSpace>,
    sizing_mode: SizingMode,
) -> Size<f32>

fn compute_baseline(
    &mut self,
    node: Node,
    known_dimensions: Size<f32>,
    parent_size: Size<f32>,
    first_or_last: BaselineType,
    axis: AbsoluteAxis,
) -> Option<BaselineSet>

Further Improvements

I think that there are a number of further improvements that we could make that would make embedding Taffy easier still. Such as:

• Changing the LayoutTree trait to be a LayoutNode trait that corresponds to a specific node similar to Morphorm's WIP Node trait (https://github.com/vizia/morphorm/blob/new-layout-no-wrap/src/node2.rs)
• Improving the story around caching (either take it out of the LayoutTree trait and implement it internally or provide better support for implementing it).
• Better support for calling Taffy layout modes individually rather than from the top-level compute_node_layout function.
• Improving the way Taffy accepts styles, perhaps along the lines of Refactor Style component into many smaller pieces bevyengine/bevy#5513
• Better documentation, potentially including a full worked example of integrating the LayoutTree trait with text layout and rendering. Potentially even a couple of examples with different storage strategies.

However, I think that just including the measurement/layout methods above in the LayoutTree trait will make a huge difference in how easy it is to embed Taffy, and in my mind effectively takes Taffy from "custom layout modes are not really supported but you might be able to hack them with measure_funcs" to "custom layout modes are supported".

---

What do people think?

[TimJentzsch]

From a first look this sounds good!

Would it be possible / how would it look like to nest different types of layout algorithms or to combine them?
E.g. having flexbox layout, but also using the grid padding. Or having a table inside regular flex layout.

[alice-i-cecile]

1. I agree that we should only support true algorithms: this split is very nice.
2. I'm interested in supporting the embedding strategy you laid out above by extending traits. We'll want to demonstrate how to do that for consumers, as it's not immediately obvious.
3. Agreed on all of your Future Work suggestions.
4. Once this is done, I think we can close this issue out and move to more targeted improvements.

[nicoburns]

@TimJentzsch

Would it be possible / how would it look like to nest different types of layout algorithms or to combine them?
E.g. having flexbox layout, but also using the grid padding. Or having a table inside regular flex layout.

It would absolutely be possible to combine them (as is already the case with Flexbox and CSS Grid). Each node would:

• Have a single layout mode that is uses to lay out it's children
• Have access to styles for itself and it's direct children (storing those styles and making them available to Taffy would be the responsibility of the consumer of Taffy if they are not using our default storage implementation - if they don't support a given style then they can just return a default value).
• Be able to query it's children for size/baseline alignment information, and ask them to perform a full layout using the methods defined above.
• Be able to communicate it's own size and baseline alignment information to it's parent by returning them when queried.

Children of a node can use any layout algorithm they like to lay out their own content.

[nicoburns]

@alice-i-cecile Excellent - it sounds like we're in agreement on everything! I'll probably get to this soon, because I think doing something like this is going to be necessary for baseline alignment support in CSS Grid (technically I wouldn't need to expose it on the trait, but I might as well if I'm touching that code anyway :))

Once this is done, I think we can close this issue out and move to more targeted improvements.

Yes, definitely keen to get mega-issue closed!