Proposal for layout / child widget sizing in Xilem

[nicoburns]

The proposals here came from me looking into what it would take to integrate Taffy layout into Xilem. But nothing proposed here is really specific to the CSS style layout modes (Flexbox and CSS Grid) that Taffy implements. Nor would they commit Xilem to CSS style layout. Rather, I believe they would enable Taffy layout modes to implemented in Xilem as widgets (which could live in an external crate), in much the same way that the existing Flex widget is implemented in Druid.

I suspect that we could make a much more streamlined system if support for associating arbitrary data (e.g. "styles") with elements such that a parent widget could access them on a child widget the chidl widget having to add support for them was implemented (ala https://github.com/linebender/druid/issues/2207). But that's a much more significant change, which I think can wait.

I have also written a prototype integration of Taffy with Iced (Iced also uses a similar layout mechanism to Druid and Xilem). And despite having to work around some limitation of Iced's system (like no measure method, and layout taking &self rather than &mut self), the integration actually ended up being relatively straightforward (you can see the implementation of Iced's layout method here (calling into Taffy from Iced), and the implementation of Taffy's perform_child_layout method here (calling back into Iced from Taffy)).

Review of Existing Systems

Here I lay out the state of things as they are in Xilem, Druid, and Taffy.

Prerequisite Type Defintions

A Size<T> in Taffy is defined as:

struct Size<T> {
    width: T,
    height: T,
}

A Size in Druid/Xilem (kurbo) is a Size<f64> using the above definition. For the remainder of this post I will translate this to Size<f64> in the function signatures below for clarity.

A BoxConstraints in Druid is defined as:

struct BoxConstraints {
    min: Size<f64>,
    max: Size<f64>,
}

An AvailableSpace in Taffy is defined as:

enum AvailableSpace {
	MinContent,
	MaxContent,
	Definite(Size<f32>),
}

A SizingMode in Taffy is defined as:

enum SizingMode {
	ContentSize,  // Size ignoring explicit styles
	InherentSize, // Size including explicit styles
}

Xilem's Existing Layout System

/// Compute intrinsic sizes.
/// The returned sizes are (min_size, max_size)
fn measure(&mut self, cx: &mut LayoutCx) -> (Size<f64>, Size<f64>);

/// Compute size given proposed size.
fn layout(&mut self, cx: &mut LayoutCx, proposed_size: Size<f64>) -> Size<f64>;

Druid's Layout System

/// Max intrinsic/preferred dimension is the dimension the widget could take, provided infinite constraint on that axis.
/// Intrinsic is a *could-be* value. It's the value a widget *could* have given infinite constraints. This does not mean the value returned by layout() would be the same.
/// This method **must** return a finite value.
fn compute_max_intrinsic(
	&mut self,
	ctx: &mut LayoutCtx,
	axis: Axis,
	bc: &BoxConstraints,
	data: &T,
	env: &Env,
) -> f64

/// For efficiency, a container should only invoke layout of a child widget
/// once, though there is nothing enforcing this.
fn layout(
	&mut self,
	ctx: &mut LayoutCtx,
	bc: &BoxConstraints,
	data: &T,
	env: &Env
) -> Size;

Taffy's Layout System

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

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

Analysis

Trivial Differences

There are a few difference which look like they might be important, but I suspect that they are actually not:

• Druid/Xilem use f64 and Taffy uses f32. Perhaps @raphlinus can comment on if/why he thinks f64 is needed, but in any case we can trivially convert between the two types (accepting the loss of precision), or if it came to it, it would be simple enough (if verbose) to extend Taffy to work with f64. I'm going to use f32 everywhere for the remainder of this post, but it could just as easily be f64.
• Taffy functions use Option<f32> where Druid/Xilem just use f32. However, where Taffy uses Option::None to represent an infinite/unset size (never using f32::INFINITY) Druid/Xilem use f32::INFINITY to represent this case. Again, this is a trivial conversion that could easily be handled as part of a widget or similar.

Extra data parameters

• Druid has data and env parameters which provide extra data. I don't quite understand env, but I think it's some kind of context. We will need something like that in Taffy at some point for allowing styles (particularly things like writing mode / direction) to inherit down the tree. But for now, I think we can ignore this.
• Taffy has the tree parameter which provides access to style information, the ability to request that children size themselves, and the ability to store the final computed size and position of nodes. I think this can all be handled by the widget implementation, so again we can ignore this (although this is one place where we might later get nicer DX with tigher integration with Xilem).

Comparison of functions

• Layout function: All three frameworks have a layout function that implements a full layout of that node and all children and returns a Size<f32> (modulo the aforementioned f32/f64 difference). Druid suggests that this should only be called once (but that this isn't actually enforced). Taffy only does call this method once in the usual case, but may need to call it multiple times to support baseline alignment (only if baseline alignment is actually used in the layout).
• Measure function: All three frameworks also have a measure function (this is compute_max_intrinsic in Druid) which allow child nodes to compute their intrinsic (content) size(s) under the provided constraints and hints and return it to parent nodes. However, they all work slightly differently:
  • Xilem's measure function returns:
    • Returns the sizes in BOTH the horizontal and vertical dimensions at once (as a Size)
    • Returns BOTH the min and max sizes (as a tuple)
  • Taffy's measure function:
    • Returns the sizes in BOTH the horizontal and vertical dimensions at once (as a Size)
    • Returns EITHER the min or max size depending on the available_space parameter
  • Druid's compute_max_intrinsic function
    • Returns the size in EITHER the horizontal and vertical dimension depending on the axis parameter
    • Returns ONLY the max size. Druid has no concept of a min content size.

I would suggest that the concept of a "min content size" is important and should definitely be included. I would also suggest that the function should not compute both the min and max sizes at once as Xilem currently does, as this could be expensive (e.g. for a text node) and at least for CSS layout it's relatively common that only one of the sizes is required.

~Whether both axis are computed together or seperately I don't have too strong an opinion about. Taffy layout modes would probably compute both either way and cache the other one the other one for future queries.~ Update: I now believe that the single-axis-at-a-time model is superior.

Comparision of function parameters

Constraint paramters

Constaint parameters have a direct relationship with the returned size and must be respected by nodes' measurement/layout functions (and/or the sizes returned will be ignored/clamped if they are not).

• [Taffy] known_dimensions (Size<Option<f32>>) - it is often the case that a parent node wants to ask a child node to size itself in one dimension while treating the other dimension as fixed, effectively asking the child a question like "suppose your width is 100px, what would your height be?" (perhaps the width has already been determined in an earlier part of the algorithm). This parameter provides a way to specify those fixed dimensions.
• [Druid] box_constraints (BoxConstraints). Druid's box constraints offer a strict superset of this functionality (setting min=max=some finite number in a given dimension is equivalent to setting the known dimension in that dimension; setting min=0, max=Infinity is equivalent to not setting the known dimension in that dimension). The max contraint also seems useful in it's own right. It makes sense to ask a node to size itself within a certain bounding box. Taffy has it's own version of this in the available_space parameter

Hint parameters

Hint parameters provide extra information that nodes may use to help choose their size. These are merely hints and may be ignored in some cases. But will likely be very helpful to allow the parent and child node to cooperatively choose a good size.

• [Taffy] sizing_mode: This makes a distinction between the intrinsic (content) size of a child (ignoring styles like min-width and max-width that might override this) and the inherent size which does respect those styles. This is important for a 100% spec compliant flexbox implementation, but I think it can ignored here (at least for the time being).
• [Xilem] proposed_size (Size<f32>): Xilem uses a proposed_size: Size<f32> parameter, which seems to be used primarily by the v_stack component which sizes children in order and uses proposed_size to pass "remaining available space" which is equal to it's own proposed_size minus "the size of any already sized children" minus "spacing between children". I would suggest that this is replaced by a more general available_space parameter (see below).
• [Taffy] parent_size The purpose of this parameter is a size for the child to resolve percentage sizes against. The parent container can choose exactly how this is defined (for example in flexbox this is the size of the overall flexbox container, whereas in CSS Grid it is the size of the grid cell that the child being sized in placed in). I think is useful (because percentage sizing is useful) and should be kept.
• [Taffy] available_space: In Taffy this is always set to the same value as parent_size if parent_size is a finite definite pixel size. But if the parent size is unknown then this enum carries an additional hint: whether the content based size should be a "min content" or a "max content" size. Taffy doesn't have an hstack/vstack-like layout, but I think this parameter would be a good place to pass the "remaining available space" that Xilem's current v_stack widget calls proposed_size (in this case available_space would differ from parent_size). I think this is useful and should be kept, however I think it is potentially confusing to couple the min/max content sizing hint with this size, so I suggest that we split this into a seperate enum parameter.

Proposal for Xilem

The following type definitions are used in the propsoal below:

struct Size<T> {
    width: T,
    height: T,
}

struct BoxConstraints {
    min: Size<f32>,
    max: Size<f32>,
}

enum RequestedSize {
    MinContent,
    MaxContent,
    FitAvailableSpace,
}

I propose that the Xilem widget trait has the following two methods for layout, replacing the existing layout and measure methods:

fn measure(
    &mut self,
    box_constraints: BoxConstraints,
    parent_size: Size<f32>,
    available_space: Size<f32>,
    requested_size: Size<RequestedSize>,
    axis: Axis,
) -> Size<f32>;

fn layout(
    &mut self,
    box_constraints: BoxConstraints,
    parent_size: Size<f32>,
    available_space: Size<f32>,
    requested_size: Size<RequestedSize>,
) -> Size<f32>;

I believe this would provide a strong framework within which lots of powerful layout paradigms could be implemented. But I'm sure I haven't thought of everything and feedback and discussion is of course enouraged!

[raphlinus]

I haven't had a chance to review in detail, but I can answer the f64 question. For a very large scrolling area, the scroll offset would lose precision (ie not even be able to represent an integer scroll offset) around 2^24. On CPU, the speed of doing f64 arithmetic is generally the same as f32.

I should also point out that what's referred to as "Xilem" above is an experimental prototype based on SwiftUI, and doesn't represent the current proposal, which is the same as Druid.

[alice-i-cecile]

Taffy maintainer here: I'm happy to make upstream changes that you need. Adding f64 support is feasible, if that's what you end up needing.

[Speykious]

For a very large scrolling area, the scroll offset would lose precision (ie not even be able to represent an integer scroll offset) around 2^24.

Isn't there a way to alleviate this issue regardless of the precision of float numbers? As in, making the widgets move into the view of the scrolling area, rather than the view moving inside the scrolling area, which would eliminate any problems for widgets displayed on screen and have any float precision issue invisible outside.

Edit: hmmm maybe that fixes the view position precision but not the widget position precision?

[alice-i-cecile]

In game dev, that strategy is called a "floating origin". I think there's a good chance it would work well here.

[raphlinus]

Yes, and we may well end up wanting to do that, partly because transforms are going to be f32 on the GPU. I'm explaining the reasoning why it was f64 in Druid, and it's still open to discussion.

[jaredoconnell]

I'm working implementing Taffy in Xilem, so the layout and measure functions are relevant to that.

Since Xilem has switched to a Masonry, which was based on Druid, it's currently just using BoxConstraints. It's getting the job done, but it doesn't interface very well with all of the requirements of Taffy.

Given that Masonry currently only uses BoxConstraints, do you think available_space: Size<f32> contributes anything? If so, what would it be used for when used alongside BoxConstraints?

How would requested_size: Size<RequestedSize> interact with BoxConstaints? Your proposal retains support for BoxConstraints. In the prior implementation, infinite bounds were passed into BoxConstraints. It feels partially redundant or conflicting.