RFC: Fragmentation/pagination/multicol/inline layout models

[pcwalton]

As a follow-up to the inline layout discussion in Orlando, I wanted to float ideas for how to implement fragmentation in Servo layout 2.0. Fragmentation encompasses pagination, multi-column, and inline layout, as well as possible future CSS features such as overflow: fragments. As I see it, there are basically three models we can choose from, each with advantages and disadvantages. Because it's not immediately obvious which to choose, I'd like to lay them all out on the table so that we can get a clear picture of the advantages and disadvantages of each.

One-tree model

In this model, we have one layout tree. During frame construction, we build the tree without any fragmentation. We then mutate it as we determine where line and page breaks are in the process of layout to create the post-fragmentation tree (via continuation frames). For dynamic layout, we need logic to undo these changes and then redo them as appropriate as styles change. This corresponds to what Gecko does today; I think Blink and WebKit may still do this as well. The latter two engines are both moving away from this model in their rewrites, as I understand it.

Advantages: Having just one tree saves memory, and the data model is simple.
Disadvantages: Having to undo changes adds a large amount of complexity. Cutting up trees is both complex and bad for cache locality. Tree mutation during layout makes layout harder to understand and potentially negatively impacts parallelism.
Verdict: I'm basically assuming that this model is a non-starter, for the reasons above.

Two-tree model

For this model, we have two layout trees: a pre-fragmentation tree and a post-fragmentation tree. Frame construction generates the pre-fragmentation tree, and layout is (at a high level) a pure function that takes a pre-fragmentation tree as input and produces a post-fragmentation tree as output. Portions of the post-fragmentation tree must be invalidated whenever the frame constructor is reinvoked due to style changes.

In an ECS model, we could conceivably share entity IDs between the boxes in the pre-fragmentation tree and the first fragment of each box in the post-fragmentation tree. However, if we do so we will need to be careful about which layout data belongs to which tree, lest we inherit some of the problems of the one-tree model. For instance, if we store resolved border sizes somewhere (which we probably wouldn't do in practice, but just as an example) then we would need to be clear about whether those resolved border sizes refer to the borders of a box before fragmentation or after fragmentation. This is a potential footgun. On the other hand, sharing entity IDs in this way makes the common (99%+) case of no pagination potentially a lot faster, because we don't have to generate so many boxes.

This model corresponds to the model that Blink and WebKit are moving to, per my understanding.

Advantages: Layout becomes more functional, which reduces complexity. There is no need to undo changes during dynamic situations in frame construction; we can simply invalidate the post-fragmentation data as appropriate. Because we have two trees that can be arbitrarily similar or different, we can handle anything the CSS working groups might throw at us.
Disadvantages: Cutting up trees for line and page breaks is complex. Having two trees reduces cache efficiency and increases memory usage.
Verdict: This is an attractive approach because of its conceptual cleanliness. But for inline layout this could have negative complexity and performance implications similar to those that we see in Gecko with continuation frames, which is vexing because inline layout is the 99% case. Making what is overwhelmingly the most common (and expensive!) layout scenario slower to unify the logic with rare features doesn't sit well with me (though I'm of course open to it if it's ultimately the right thing to do).

Range model

This model represents fragment containers as ranges. Like the Range API in the DOM, a range is simply a (start entity ID, start offset, end entity ID, end offset) tuple. Such a range represents all boxes that would be visited in between the start and end entities during an in-order traversal of the frame tree. Dynamic layout is accomplished by simply invalidating the ranges as necessary and rebuilding them.

Previously, I was referring to this model as the "flat list" model, and in fact a further optimization of this model for inline layout is to flatten inline frames that are part of the same inline formatting context into a single linked list or array. However, it doesn't seem feasible to flatten frames where pagination and multicol are concerned. So instead I call this the range model, because ranges are the fundamental concept that can potentially apply to not only inline but also paginated and multi-column layout.

As mentioned before, the DOM has the Range concept, which is very similar to this model except that it operates over the DOM instead of the frame tree. OS line layout systems such as Apple's Core Text frequently use this model (in Core Text's case via "attributed strings").

Fragments need to store data unique to them--for example, if an inline element gets split, each fragment needs a position of its own--and so this model must choose a strategy to handle this. The two strategies that I can see correspond to the one-tree model and the two-tree model above: either we mutate the frame tree to split frames during layout and undo that mutation as necessary for dynamic layout, or we build up fragments into a separate list that then gets invalidated and rebuilt as necessary. The former approach is what Servo does today, but I think the latter is probably preferable for Servo Layout 2.0.

The big issue with this model is that it requires that the specs are written in such a way as to guarantee that ranges are actually sufficient to determine page and multi-column boundaries, and I'm not sure that this is the case. Note, however, that we could extend this model to treat fragmentainers as a set of ranges, much like the DOM Selection API treats selections as a set of ranges.

Advantages: The model maximizes cache efficiency and therefore performance. There's no need to store two trees, which is both simpler and better for memory consumption.
Disadvantages: It's not clear that this model will be flexible enough to handle everything that CSS requires right now or that CSS working groups might throw at us in the future.
Verdict: I'm leaning toward this model, if it works.

Discussion

I think that either the two-tree or the range model are likely the way to go, but I'm somewhat torn between them. I'm very curious to know what others think.

[bzbarsky]

How would these various models handle table header/footer replication? What about fixed-pos replication during pagination?

That's assuming we want to actually support those. Gecko does, last I checked, but I don't know whether anyone else does. Also, both are pagination-specific, I think, so don't apply to overflow: fragments or multicol...

[SimonSapin]

two layout trees: a pre-fragmentation tree and a post-fragmentation tree. Frame construction generates the pre-fragmentation tree, and layout is (at a high level) a pure function that takes a pre-fragmentation tree as input and produces a post-fragmentation tree as output.

I think these map closely to what specs call boxes (the box tree) and fragments (the fragment tree). Contrary to what their name suggest, boxes don’t have geometry. The box tree is still similar to the DOM tree, only transformed based on the display property and pseudo-elements.

If we want to stick with spec terminology we can call "fragments" the things in the output of layout, even when a given box only generates one fragment (and so "fragmentation" didn’t really happen to it).

By the way, except for a few special cases (for example table rows), in the internal representation of boxes we should separate the "outside" behavior of a box (for example flex-level, inline-level, …) from the inside (establishes a new block formatting context, is a table, …). This is the separation that https://drafts.csswg.org/css-display-3/#the-display-properties makes between outer display type and inner display type. Even if we don’t support the syntax introduced in that spec, this separation allows for example inline-block to be just another combination rather than a special case.

In a tree based on ownership rather than ECS, this could look something like:

type BoxTreeRoot = BlockFormattingContext;

struct BlockFormattingContext(BlockContainer);

enum BlockContainer {
    BlockLevels(Vec<BlockLevel>),
    InlineFormattingContext(Vec<InlineLevel>),
}

enum BlockLevel {
    SameFormattingContextBlock {
        style: Arc<ComputedValues>,
        contents: BlockContainer,
    },
    Other(FormattingContext),
}

enum InlineLevel {
    Text {
        style: Arc<ComputedValues>,
        content: DOMString,
    }
    Inline {
        style: Arc<ComputedValues>,
        children: Vec<InlineLevel>,
        // May be fragmented by an in-flow block-level descendant element
        first_fragment: bool,
        last_fragment: bool,
    },
    Atomic(FormattingContext),
}

struct FormattingContext {
    style: Arc<ComputedValues>,
    kind: FormattingContextKind,
}

enum FormattingContextKind {
    // Not included: inline formatting context, which is always part of a block container

    Flow(BlockFormattingContext), // a.k.a. blocks-and-inlines
    Replaced(…), // Not called FC in specs, but behaves close enough
    Table(…),
    Flexbox(Vec<FlexItem>),
    Grid(…),
    Multicol(…),
    // New layout modes (usually) go here.
}

struct FlexItem(FormattingContext);

for inline layout this could have negative complexity and performance implications similar to those that we see in Gecko with continuation frames, which is vexing because inline layout is the 99% case.

Could we have an hybrid model where inline layout (and fragmentation) is based on ranges, but everything else is a second tree?

Every single layout mode needs to deal with fragmentation, so having that as systematic as possible would make correctness easier to achieve.

Disadvantages: It's not clear that this model will be flexible enough to handle everything that CSS requires right now or that CSS working groups might throw at us in the future.

Parallel flows come to mind: https://drafts.csswg.org/css-break-3/#parallel-flows

The easiest example to visualize is a table with multiple columns and many words in each cell (tall rows). A (page/column/region) break could occur in the middle of a row. In that case, each cell of that row has its own break point, where the next page (or column or region) resumes.

In terms of ranges, this means that either or both of the start and end for a page might be not a single point in the box tree, but multiple points.

WeasyPrint currently does not support page breaks in parallel flows. This is perhaps its biggest limitation. In tables, page breaks can only occur between rows. If a row doesn’t fit, it is moved entirely to the next page. If it still doesn’t fit there, WeasyPrint lets it overflow the page. Similarly with floats, WeasyPrint does not at all support fragmenting them.

[pcwalton]

So I was thinking about @SimonSapin's comment:

Could we have an hybrid model where inline layout (and fragmentation) is based on ranges, but everything else is a second tree?

I realized that the range model is equivalent to turning the frame tree into a directed acyclic graph. For example, suppose we have the following document and we wish to paginate it:

With the range model, we might create two page ranges like so:

But remember that, in an entity-component system, we represent pointers in the tree as IDs. Every entity ID can be viewed as a pointer into the tree. So we can equivalently view the above structure as a DAG that looks like this:

Compare to the corresponding explicit fragment tree in the one-tree or two-tree model:

Viewed in this way, the fundamental difference between the range model and the two-tree model is that the former model produces a fragment DAG from the frame tree, while the latter produces a fragment tree from the frame tree by generating continuation frames as necessary.

Now the critical question is how a fragment DAG should store per-fragment information, such as the resolved positions of both fragments of block 1 in this example. I can't really think of another way other than to generate continuation frames of some sort. Since the DAG model doesn't have continuation frames for parents, the two-tree model seems to be the only realistic solution that I can see for pagination and multi-column layout. (I certainly could be missing something, though.)

Assuming we settle on the two-tree model for pagination and multicol, then, the remaining question then is which model we should use for inline layout. Let's consider a simple paragraph in the range model:

As before, the range model can be equivalently viewed as a DAG:

Observe that there is not a great difference between this and the corresponding paragraph in the two-tree model:

So for inline layout I don't think it matters which model we pick: they're actually equivalent. In an entity-component system, where all pointers are indices into a giant flat list of nodes, a line box can be viewed as both a range and as a node in the fragment tree. As far as inline layout is concerned, the two-tree model and the range model have the same in-memory representation.

[emilio]

I was going to just ask how would ranges represent stuff that doesn't have a clear position in the box / layout tree but does have a clear position in the fragment tree, like out of flows...

Seems you have settled out on two trees instead, which makes sense to me :)

[SimonSapin]

So we can equivalently view the above structure as a DAG that looks like this:

[…]

So for inline layout I don't think it matters which model we pick: they're actually equivalent.

Sorry, I’m really confused.

I understand this discussion’s premise being: assuming a given output of layout (as observable by users or scripts), what data structures should we use to represent that data in memory. By a certain definition of equivalent, all possible accurate memory representations of this data are equivalent since they all achieve accuracy. (This is pretty much a tautology, not very insightful by itself.) But it does matter which one we pick, or we wouldn’t be having this discussion.

Do you mean something else by "equivalent" or "doesn’t matter"?

[pcwalton]

I understand this discussion’s premise being: assuming a given output of layout (as observable by users or scripts), what data structures should we use to represent that data in memory.

What I mean is that the pervasive use of entity IDs instead of pointers in the ECS means that the two-tree system and ranges have the exact same in-memory representation in the case of inline layout. Thus there really isn't any distinction to begin with. The implication is that we might as well just go with the two-tree model everywhere, since it isn't any less efficient than the ranges model for inline layout.

(Note: I realized after making that post that the ranges model and the two-tree model are only equivalent when you don't have any nested <span>s—a.k.a. there is no "inline fragment context" in Servo terminology. If there are nested spans, we don't have a flat list of inlines anymore, and we're back to the tree vs. DAG distinction. I need to give more thought to how the list-of-ranges approach for nested <span>s compares to the two-tree model.)

[SimonSapin]

So the two-trees with IDs model and ranges model have the same memory representation when the tree depth happens to be 1? Ok, I see what you mean now, but I’m not sure how that conclusion is helpful. We do need to support display: inline.

[pcwalton]

So I think this actually comes down to whether we need to generate continuation frames all the way up the tree when we perform a line break. In the two-tree model, we have to generate these continuation frames, which effectively amounts to cutting up trees. In the ranges model (by which I mean the "hybrid model" of ranges for inlines and two trees for pagination/multicol that @SimonSapin mentioned earlier), we don't generate those continuation frames and instead turn our tree into a DAG whenever we perform a line break.

To give an example, suppose we have this:

Lorem ipsum <span>dolor sit</span> amet

Let's say we break after "dolor". It's clear we will have to effectively split the "dolor sit" text frame into two frames: "dolor" and the continuation frame "sit". But do we need to generate a continuation frame for the span as well (i.e. do we need to divide the span into the part before the break and the part after the break, as well as dividing the text)? Or can we get away with only splitting the text?

If we generate a continuation frame for the span and the text, then we have a fragment tree. If we generate a continuation frame for the text only, then we have a fragment DAG.

[bzbarsky]

For this specific situation, what is the approach for painting borders on the span in both cases?

(And what is the approach for ::first-line?)

[pcwalton]

For this specific situation, what is the approach for painting borders on the span in both cases?

The display list builder would do a traversal of each line and would visit the span twice, one for each line, in order to paint its borders.

(And what is the approach for ::first-line?)

Not sure exactly which ::first-line situation you might be referring to. Could you give a specific example?

[bzbarsky]

body { font-size: 10px; }
body::first-line { font-size: 20px; }
span { font-size: 2em; }

Where is the 40px font-size for the pre-break part of the span stored?

[SimonSapin]

The display list builder would do a traversal of each line and would visit the span twice, one for each line, in order to paint its borders.

But those two fragments have different geometry. Don’t we need to store in "the output of layout" sizes and positions for each of them, in order to paint those borders?

[pcwalton]

I think that restyling has to hang both the "computed values if this span is not on the first line" and "computed values if this span is on the first line" objects off the box for the span. (I believe this is what Servo does today: it has separate "computed values" and "computed values for first line" fields.)

Whether we use continuations or not doesn't seem relevant to me in this case, because at the time CSS selector matching and cascading happens, the restyler doesn't know which boxes will end up on the first line. So it has to be conservative, compute the "computed values for the first line", and store it in a special field anyway, just in case any node it styles happens to go on the first line.

During layout, the inline layout system can keep track of whether it's laying out the first line or not and consult the appropriate computed values slot (non-first-line styles or first-line styles) as appropriate. Display list building can do the same: it can keep a flag indicating whether it's building the display list for the first line and consult the appropriate styles.

[pcwalton]

But those two fragments have different geometry. Don’t we need to store in "the output of layout" sizes and positions for each of them, in order to paint those borders?

Well, remember that we are generating continuation frames for the text no matter what, so I was assuming we could figure out where the borders are supposed to go from the geometry of the text fragments, coupled with the styles of the spans. (And likewise with other replaced content.) Servo does that today with its "inline fragment context", which only stores styles, not positions.

[SimonSapin]

This doesn’t seem easy to do correctly. For example:

<span style="border: solid; font-size: 5em">
  <span style="font-size: .2em; padding-right: 2em">
    foo

In Firefox:

Servo correctly accounts for the padding for the width the outer inline (I’m not sure how, if as you say only text runs are preserved), but not for the larger font size for its height.

And then there’s vertical-align, position: relative, z-index, …

Oh, and of course an inline element could be empty, but still have padding and background.

[pcwalton]

Well, wait. I'm not saying that we just ignore outer spans—we still lay them out by traversing the tree—we just don't generate continuation frames for them if they're line broken. In other words, the only difference between the two-tree model and the range model is that the former splits all frames in between the inline context and the text node when line breaking, while the latter only splits the text node (where "splits" means "allocates a new node for").

[SimonSapin]

Yes, and I’m saying that there are various cases where we need to track the separate size and position of each fragment of inline boxes, not just one per box/element.

[pcwalton]

Could you help me understand what those cases are, with an example? I'm certainly willing to go in for the two-tree model if that's what needs to be done, but I'd like to understand why first.

Blink seems to be using a flat list in LayoutNG, for example. If Blink's approach is doomed to fail, then it would be interesting to understand why.

[pcwalton]

Actually, I think I was wrong there: Blink is not using a flat list. I guess the strict two-tree model is what everyone has converged on. Let's do that then :)

[pcwalton]

In a tree based on ownership rather than ECS, this could look something like:

In this model, are you representing {ib} splits as blocks that are children of inlines, or are you assuming that the frame constructor will already have resolved {ib} splits by explicitly generating anonymous blocks as necessary? I'm guessing the latter, because I don't see how you would distinguish between inline-block and an {ib} split otherwise.

Assuming that the frame constructor generates explicit anonymous blocks as needed, is there ever a case where the outer display type of a box is different from the formatting context its parent is located in? For example, is there ever a case in which a block child of an inline is ever not an inline-block? If there is no such case, do we need to make the distinction between inner and outer display explicit in the box tree (which might complicate our component definitions)? Or can we centralize that logic in frame construction and have inline layout just assume that all non-text, non-inline kids of inline boxes are atomic formatting contexts of their own?

(Mostly I'm trying to figure out what our components should look like.)

[SimonSapin]

This data structure is intended to be the output of frame/box construction, including anonymous box construction. I’m not sure what you mean by {ib}, so:

display: inline-block is represented as InlineLevel::Atomic(FormattingContext { kind: FormattingContextKind::Flow(..), .. }).

When a block container has any block-level child (the BlockContainer::Blocks case), an anonymous (with no specified style and inheriting from the block container) BlockLevel::SameFormattingContextBlock is created to wrap consecutive inline-level children if any.

When a non-replaced inline element contains a block-level element, the box for the latter is "moved up" to become a child of the nearest block container. The intermediate display: inline ancestors are split up, and anonymous BlockContainer::InlineFormattingContexts are generated.

This is what I came up with based on reading https://drafts.csswg.org/css2/visuren.html#box-gen. I haven’t drawn the rest of the owl written the rest of the layout code based on this data structure, so maybe doing things differently would make more sense.

is there ever a case where the outer display type of a box is different from the formatting context its parent is located in?

In spirit, there is not. For example, these types enforce that children of a flex box are all flex item boxes. (But this is not exactly the definition of https://drafts.csswg.org/css-display-3/#outer-display-type, there is no syntax like display: flex-item.)

is there ever a case in which a block child of an inline is ever not an inline-block?

What do you mean by “block child”? That it’s useful to separate block-level and block container is precisely my point.

A block-level child element in an inline element would cause splits and "moving up" as described above, so their generated boxes would not be child/parent. Conversely, children of a InlineLevel::Inline box are all InlineLevel.

As to a block container that also happens to be inline-level, that can occur with display: inline-block. (Or if a display: block is inlinified https://drafts.csswg.org/css-display-3/#transformations by a ruby container, which means do as if it were display: inline-block.)

Or can we centralize that logic in frame construction and have inline layout just assume that all non-text, non-inline kids of inline boxes are atomic formatting contexts of their own?

I think this is exactly what I mean by making this separation. On the outside, all atomic inline-level boxes can be treated the same: as inline-level. Inline layout doesn’t care about what’s inside. Only when inline layout needs to know for example the min-content width do we look at the inside, at which point there’s dispatch based on the kind of formatting context. Each formatting context known how to compute its own min-content width, and doesn’t care how that result used.

The point is that none of e.g. display: inline-block, display: inline-grid, or flex item with display: table are special cases. They’re all combinations of various outside behaviors (inline-level, flex item, etc.) and inside behaviors (formatting context kind).

In terms of ECS, I’m not sure. Maybe a "formatting context" component with an enum type?

[SimonSapin]

children of a InlineLevel::Inline box are all InlineLevel

By the way, in the code above this is enforced by the type system.

This is somewhat off-topic for this issue, but this is a concern I have with ECS. We can write box generation code that only generates inline-level children boxes for an inline box, and we can write layout code that assumes that this is the case. But with ECS the compiler doesn’t really help us ensure that an entity with a given ID has the components we expect it has. A game engine might have a system that operates on all entities that have a given component (say, velocity) and not care about other entities if they have some other components (say, collision). But in layout it seems that the relationships between entities/nodes/boxes/fragments are "more specific".

Similarly, when we remove an entity the compiler doesn’t help us find out if its ID is still stored somewhere. A generation number can help us catch them at runtime and make them sound, but dangling references can still happen.

In other words, ECS is dynamic typing and manual memory management. Are those really the right fit for layout? I have multiple times when working on Stylo made large-scale refactors that (I felt) would have been much harder to pull off without compile-time type checking.

[pcwalton]

Good points, and I'll address them in reverse order:

Similarly, when we remove an entity the compiler doesn’t help us find out if its ID is still stored somewhere. A generation number can help us catch them at runtime and make them sound, but dangling references can still happen.

Well, the compiler can only help with memory management if the data structure is a tree (or something else based on single ownership). I think we need "weak references" either up or down the tree, though, no? Take absolute containing blocks: either we place them at their DOM level and have a pointer to the containing block (WebKit style) or we move them up to the containing block and have a pointer down to their hypothetical box (Gecko style). Either way breaks the strict tree structure, because now we have extra pointers to ancestors or descendants.

Another simple example is that each DOM object needs to be able to find its associated box for layout queries. Right now Servo traverses the layout tree searching for the right box on each query, but I'm not at all sure that that is shippable from a performance point of view, because it's O(depth of tree), and traversing all those links is bad on cache. All other engines have a pointer from the DOM node directly to the associated layout frame and can do those queries in O(1).

Once you break out of single ownership like this, then you have to use Arcs and RwLocks and so forth, which seems unattractive for layout. Arc is for when you truly don't statically know when an object is to be destroyed, but we do destroy layout objects in one place: the frame constructor kills them when the DOM changes. We could use weak pointers to Arcs to handle pointers up and down the tree structure, but I think ultimately those have worse ergonomics than just using IDs (as well as more overhead at runtime due to reference count manipulation).

It is true that we need to use some sort of reader-writer lock for synchronization in many cases, no matter what. My hope is that the component architecture can end up reducing the amount of synchronization, by dividing up layout data into the pieces that need synchronization and the parts that don't. For instance, style is immutable after styling, so we can potentially avoid all synchronization on the style component during layout. But this is a bit up in the air.

This is somewhat off-topic for this issue, but this is a concern I have with ECS. We can write box generation code that only generates inline-level children boxes for an inline box, and we can write layout code that assumes that this is the case. But with ECS the compiler doesn’t really help us ensure that an entity with a given ID has the components we expect it has. A game engine might have a system that operates on all entities that have a given component (say, velocity) and not care about other entities if they have some other components (say, collision). But in layout it seems that the relationships between entities/nodes/boxes/fragments are "more specific".

Yeah, this is also a concern I had when going to sketch out layout code after reading your reply. Given the memory management concerns outlined above, though, I don't see how we really get away from IDs in some form or another.

There's a simple solution to the problem you described: have multiple kinds of entity IDs and just only have one component for each such kind. Ensure that you can't construct an entity ID of a given kind without inserting a component into the appropriate component map. This gives you the same data structure you would have with a tree of Arcs, but effectively with indices into lists instead of the Arc pointers.

(One could imagine extending this scheme to multiple components, by having some types like EntityID<(HasComponentA, HasComponentB)>, but let's not overcomplicate this for now.)

[bzbarsky]

the box for the latter is "moved up" to become a child of the nearest block container.

How does that handle relative positioning of the now-no-longer-parent inline? Per spec, that should affect the block no-longer-child.

Fwiw, in Gecko we generate anonymous blocks wrapping the block being hosted and apply the relative positioning to them...

[pcwalton]

Fwiw, in Gecko we generate anonymous blocks wrapping the block being hosted and apply the relative positioning to them...

Could you elaborate as to when and how {ib} splits are handled in Gecko (during frame construction? during layout? both?) This is an important topic and it'd be great to have all of this on the table.

[SimonSapin]

How does that handle relative positioning of the now-no-longer-parent inline? Per spec, that should affect the block no-longer-child.

Good point! I hadn’t thought of that case, and I suspect that WeasyPrint gets this wrong. Does the same happen with transform and opacity? (Should it?) Anything else?

[bzbarsky]

Answering the simple question first: Gecko makes the following properties from the original inline apply to the anonymous blocks (via inheriting them): position, outline, outline-offset, clip-path, filter, mask, opacity, text-decoration, overflow-clip-box, text-overflow, top, left, bottom, right, z-index.

The spec support for most of that is somewhere between "slim" and "based on the fact that the spec applies a bunch of these properties to elements and their descendants, not boxes and their descendants".

As far as how this is handled in Gecko, the frame-tree aspect is all handled during frame construction. The output of frame construction is a frame tree in which a non-replaced inline never contains a block-level box. Contiguous runs of such boxes are wrapped in an anonymous block box of the :-moz-block-inside-inline-wrapper type, which has various styles applied to it in ua.css. If there are multiple ancestor inlines, you get multiple anonymous block boxes.

I think we create inlines for whitespace between the blocks when that whitespace is not suppressed.

During layout and painting, inlines in the middle of this construct don't get their start/end borders/padding/margins as needed, just like for any other linebreak, even though on the frametree level they don't look like they're at a normal linebreak.

There's also some related complication about column spanners inside inlines, by the way. I think those lead to somewhat similar behavior....

[emilio]

Could you elaborate as to when and how {ib} splits are handled in Gecko (during frame construction? during layout? both?) This is an important topic and it'd be great to have all of this on the table.

It's mostly during frame construction, see nsCSSFrameConstructor::CreateIBSiblings:

https://searchfox.org/mozilla-central/rev/3160ddc1f0ab55d230c595366662c62950e5c785/layout/base/nsCSSFrameConstructor.cpp#10974

AFAIK Blink also does something like this. But at least there's:

https://groups.google.com/a/chromium.org/d/msg/layout-dev/WgaYctOJQs4/xw_-OhfpAwAJ

Which hints that Blink may try to get rid of this and WebKit may have done it already? Though I'm confused, since I still see the code to create the block wrappers:

http://webkit.crisal.io/webkit/rev/7309ce8ca95860db764259de9e326fb301e58258/Source/WebCore/rendering/updating/RenderTreeBuilderInline.cpp#167

[nox]

With the assumption that we can get away with having only one owning reference to any tree in the layout tree and all others be "weak" references, I made the crate arbalest, which provides types that can do the same kind of stuff as Arc<AtomicRefCell<T>> except that the main type (Strong<T>) doesn't need to perform any atomic operation to access the T and weak (Frail<T>) references can be created from any Strong<T> or even the RefMut<T>.