Hi everyone,
Pradeep's excellent pull request [1] for absolute positioning raised
some thorny issues relating to solving geometry constraints for
absolutely positioned blocks in a parallel setting. The fundamental
issue is that absolute positioning can depend not only on width and
height of the containing block, but also the top/left/right position of
the hypothetical box created by its static position. This is in conflict
with our two-direction approach for computing widths and heights: widths
are computed *top-down*, so that kids' widths depend on parents' widths,
but heights are computed *bottom-up*, so that parents' heights depend on
kids' heights.
There are two basic approaches to dealing with absolutely-positioned
frames: (1) parent the absolutely-positioned frame to its containing
block, and keep track of a separate "hypothetical frame" (which is what
Gecko seems to do, with `nsHTMLReflowState::CalculateHypotheticalBox()`
and `nsFrameManager::GetPlaceholderFrameFor()`), or (2) keep track of
the containing block separately from the parent and use the
"hypothetical frame" as the real frame, which is WebKit's approach (see
the comments in `RenderObject::container()` and
`RenderBox::computePositionedLogicalWidth()`).
The pull request #1681 takes approach #2. It deals with the parallel
hazard by deferring height computation of absolutely positioned blocks
until display list construction time (which is top-down). However, this
has a problem in that the overflow for the containing block cannot be
correctly calculated, because the height is not yet known. This will
make it impossible for us to construct the display list only for frames
in the visible region, since that depends on having correct overflow
information.
After some thought I've begun to think that approach #2 (WebKit's
approach) is a dead-end in a parallel setting. The fundamental problem
is that the height of an absolutely-positioned block cannot be
determined without knowing the height of its containing block (if `top`
and `bottom` are specified). Yet knowing the overflow region of *at
least* the containing block depends on knowing the height of the
absolutely-positioned blocks for which it is the containing block. I say
"at least" because if we were to adopt WebKit's approach (putting the
absolutely-positioned frame at its hypothetical static location) then
potentially many more intervening blocks would have their overflow
regions depend on their absolutely positioned descendants:
^ height +------------------+ overflow
| +-------+ containing block |<--------+
| | +--------+---------+ |
| | | overflow |
| | v |
| | +-------+ |
| | | block | |
direction| | +---+---+ |
of| | | overflow |
traversal| | v |
| | +-------+ |
| | | block | |
| | +---+---+ |
| | | overflow |
| | v |
| | +----------------------------+ |
| +->+ absolutely positioned flow +----+
| +----------------------------+
That's a potentially unbounded amount of extra information that needs to
travel in the opposite direction to the traversal.
By contrast, approach #1 (Gecko's approach) avoids the unbounded amount
of information flow in the opposite direction to the traversal. The
height and overflow region only need to travel one step: from containing
block to its immediate absolutely positioned flow child and back. This
can be implemented by simply moving the computation of height and
overflow of absolutely-positioned frames to the parent. This loses a
small amount of parallelism during the assign-heights phase, but it
should be small with fixed overhead.
Width assignment becomes potentially trickier with absolute positioning.
Recall that in Servo actual width computation is a top-down traversal.
But because the width of an absolutely-positioned frame can depend on
its hypothetical frame's static position, it is possible that an
absolutely-positioned frame will not have its width ready by the time
the traversal wants to compute it, because its hypothetical frame has
not yet been reached. This can be remedied by simply (a) having
containing blocks *not* enqueue their absolutely-positioned kids in the
usual manner during the parallel top-down traversal and (b) having the
*hypothetical* frame be the frame responsible for computing its
associated absolutely positioned frame's width, and enqueuing its kids.
Unfortunately, I don't know off the top of my head the best way to
enforce that this logic is correct in the Rust type system. Races during
layout can cause memory safety problems, so we need to make sure the
parallel traversal logic is correct. We may be able to do something like
(a) add on-in-production asserts that hypothetical frames encode only
absolutely-positioned flows; (b) add on-in-production asserts that
absolutely-positioned flows are never enqueued for parallel layout
directly by their containing blocks; (c) lock down the "is this
absolutely positioned?" flag to only be able to be touched by flow
construction, never by layout itself. This may be sufficient for making
the system foolproof, although I haven't thought too hard about it.
There is one minor issue of reference counting flows: there will need to
be a reference from the absolutely-positioned flow to its hypothetical
flow (so that the flow can find its static position if need be) and vice
versa (so that width can be assigned as above). At least one of these
references must be a strong reference. This is not too big of an issue
because we need to reference count flows for incremental reflow at some
point anyway.
As an added bonus, adopting approach #2 (Gecko's approach) will
eliminate the need to push down "containing block" information and to
have the idea of a "container" separate from the "parent", giving us a
small algorithmic performance improvement over approach #1. Perhaps not
having to store this information is part of the reason we're so fast at
layout today, even sequentially.
Anyway, for now I'm inclined to just not handle hypothetical boxes and
just make up some values (e.g. zero) where the spec says to calculate
their positions. This will almost certainly break the Web, so I'm not
suggesting that we do this for the long run, but I think landing
complicated work like this is best done piecemeal.
Thoughts?
Patrick
[1]: https://github.com/mozilla/servo/pull/1681
_______________________________________________
dev-servo mailing list
dev-servo@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-servo
