Implement CSS floats

[SimonSapin]

Used on https://servo.org for two-column layout.

We already have logic for disabling parallelism in a block formatting context that contains any float. Drawing the rest of the owl actual layout implementation is missing as of this writing.

• https://drafts.csswg.org/css2/visuren.html#floats
• https://drafts.csswg.org/css2/visudet.html

[pcwalton]

So I'm starting to look into this. I'll add questions as I get to them (cc @nox):

• Should there be a new Float(FloatFragment) enum variant in Fragment? In the case of AbsoluteOrFixedPositionedFragment, I'm guessing that the hoisted_fragment is the link from the hypothetical box up to its real ancestor fragment? If so, it would seem that at least inline float fragments would probably want a similar link. But why does the hypothetical box of absolute positioned elements need to be in the fragment tree at all?

[SimonSapin]

Could AbsoluteOrFixedPositionedFragment be renamed HoistedFragment and used for floats as well? (With an appropriate doc-comment.)

Maybe @mrobinson can say more: my understanding of why we have hoisting with this indirection at all, effectively turning a tree into a DAG, is the tension between:

• For the purpose of positioning, the "main layout phase" wants to create a fragment tree where the coordinates of each node are relative to that of their parent, which represents their containing block.

  Layout has a lot of data dependencies that require things to be computed in a certain order. In some cases we need to determine the size of a block container for a given fragment, then lay out its subtree, then the compute its size based on the laid out content, then position the whole subtree based on some alignment property.

  Therefore coordinates in the fragment tree can’t be absolute without a translate method that involves a subtree traversal to patch things up, which I presume would be expensive. And fragments need to be "near" their containing block for the next phase to be able to compute absolute coordinates.

• For the purpose of determining the painting order, we build the stacking context tree as an intermediate between the fragment tree and the display list. This is what gets sorted by z-index. Elements that generate a stacking context form a sort of isolation boundary such that a subtree is treated as a unit for this sorting.

  But "subtree" here is meaningful is at the level of the DOM or box tree, not the fragment tree. What containing block a fragment has is unrelated to what stacking context it directly participates in. In all out-of-flow cases (position: fixed, position: absolute, and float), when a fragment is hoisted from its DOM/box tree position to be near its containing block, it can go past/through an intermediate ancestor that generates a stacking context. But the original DOM/box tree position is still meaningful for painting order.

This is why we need some fragments to "be in two places" in the fragment DAG pseudo-tree.

We may also want to rethink the terminology: which of these two do we call hoisted, and which do we call "real"? Should we call the latter something else? The current name of the AbsoluteOrFixedPositionedFragment::hoisted_fragment field may be backward if I understand correctly: I feel that a field that contains Arc should be named after the target of the link, but here I does the link goes from the hoisted fragment?

[mrobinson]

I think the description that @SimonSapin gave is great. For the case of absolutely positioned items we need to move them close to their parents for computing their position, but for building the display list we need them in tree order.

I do have one question about floating content though. Do they need information from ancestors for size or position computation? If it's only about painting order, then we can probably use the "pseudo stacking context" approach which is more-or-less perfect for this case and already implemented.

[pcwalton]

Ah, I see, it's a painting order thing. Makes sense.

I don't believe that floats need information from ancestors for size/position calculation, but my memory is a bit fuzzy.

[SimonSapin]

Right, I believe floats do not have a "backward" data dependency like abspos does with the bottom property. They can (and likely must) be laid out at the time of encountering them in a "normal" sequential depth-first tree traversal of boxes in the block formatting context they participate in.

If it's only about painting order, then we can probably use the "pseudo stacking context" approach which is more-or-less perfect for this case and already implemented.

That sounds appropriate since https://drafts.csswg.org/css2/zindex.html does say to handle a float “as if it created a new stacking context” anyway. @mrobinson Could you say more about what this approach does in our code? Especially in terms of how the data structures end up being shaped.

[mrobinson]

That sounds appropriate since https://drafts.csswg.org/css2/zindex.html does say to handle a float “as if it created a new stacking context” anyway. @mrobinson Could you say more about what this approach does in our code? Especially in terms of how the data structures end up being shaped.

Sure, there's currently a list of types of stacking contexts:

pub(crate) enum StackingContextType {
    Real,
    PseudoPositioned,
    PseudoFloat,
    PseudoAtomicInline,
}

Looking over the code, it looks like this is halfway implemented. I think all that's required is to:

1. When doing the traversal that creates stacking context tree, create a new stacking context for floating blocks and make sure its fragments are added to it. This might already be happening...
2. Make sure that the stacking context is added to the float_stacking_context Vector on the parent StackingContext instead of stacking_contexts.
3. When children are stolen from pseudo-stacking contexts (look for stolen_children) make sure that floating stacking contexts are also properly re-parented to a real stacking context.

[pcwalton]

Another question:

• For incremental layout, should we make the list of floats a persistent list so that we can resume layout at any point in the containing block? I'm inclined to say yes, but at least WebKit does not do this.

[SimonSapin]

Like all granularity levels of incremental, I think we can start without and still have the option to add this later.

[pcwalton]

Spec questions/potential bugs/ambiguities discovered so far, from https://www.w3.org/TR/CSS2/visuren.html#float-position:

1. Rule 7 states "a left-floating box that has another left-floating box to its left may not have its right outer edge to the right of its containing block's right edge. (Loosely: a left float may not stick out at the right edge, unless it is already as far to the left as possible.)" These statements may not be equivalent in the case of zero-width floats, depending on what the meaning of "to its left" and "to its right" mean. Consider:

   <div id=container style="position: absolute; width: 3px">
       <div id=a style="float: left; width: 0; height: 32px"></div>
       <div id=b style="float: left; width: 32px; height: 32px"></div>
   </div>
   

Is b "a left-floating box that has another left-floating box to its left"? If so (what I assumed), then b's top would be 32px. However, Gecko renders it at the top of its containing block, which suggests to me that Gecko is choosing the "loose" interpretation. Even though b has the left-floating box a to its left, b is still as far left as possible, so Gecko allows b to stick out to the right.

2. Consider:

   <div id=container style="position: absolute; width: 3px">
       <div id=a style="float: right; width: 0; height: 61px"></div>
       <div id=b style="float: left; width: 6px; height: 33px"></div>
   </div>
   

Rule 3 states that "the right outer edge of a left-floating box may not be to the right of the left outer edge of any right-floating box that is next to it. Analogous rules hold for right-floating elements." This seems to indicate that b must be below a, making the top of b at 61px. However, Gecko and Blink place b at the top of the containing block.

I'm unsure what to do here, but for now I'll follow what I understand the spec to be rather than reverse engineering Gecko and Blink.

[pcwalton]

@mrobinson I'm still a bit confused. Why can we not keep track of the position of the absolute/fixed containing block in addition to the position of the parent when traversing the tree for display list construction? Wouldn't we not need to hoist absolutely positioned objects at all then?

[SimonSapin]

Layout also needs hoisting. For example position: absolute; top: 10px; bottom: 20px; height: auto results in a used height based on that of the containing block, even if that containing block has height: auto.

[mrobinson]

@pcwalton Currently, I think we track the containing block like you suggest during StackingContextTree construction. Later, during StackingContextTree conversion to WebRender display list we only reorder StackingContextFragments according to Appendix E without worrying about the containing block.

[pcwalton]

@SimonSapin Oh, OK, that makes sense. I guess the other option would be to store a link from every absolutely-positioned element to its containing block (WebKit has a containingBlock() method for this). But this probably would end up very similar to the hoisting solution, just with an edge directly to the containing block instead of an edge to an immediate child of the containing block, so isn't worth doing I guess.

[SimonSapin]

Even with that link, we’d still need to delay laying out the abspos box until the height of its containing block is known which make require having finished laying out all of the in-flow content of that containing block. How does WebKit handle that?