Re: [css3-box] Issue with the current shrink to fit algorithm

On Thu, Oct 28, 2010 at 6:32 PM, Boris Zbarsky <bzbarsky@mit.edu> wrote:
> On 10/28/10 12:22 PM, Giuseppe Bilotta wrote:
>>
>> (1) find the minimum preferred width [this is like the second step of
>> the current shrink-wrap algorithm]
>> (2) find the maximum available width [this is like the third step of
>> the current shrink-wrap algorithm]
>> (3) layout the box content assuming a containing width of
>> max(minpref,available).
>> (4) set the box width to the largest contained box width (plus
>> margins, paddings, etc)
>
> After step 4 you have to redo the layout, due to percentage widths.
>
> So you have to do two full layout passes for each shrink-wrap width
> computation.  So a shrink-wrap box with N shrink-wrap ancestors needs 2^N
> such passes (modulo maybe caching some layout results somewhere, but you'd
> still hit the worst case in some cases, and the caching sounds pretty
> error-prone, in addition to using additional memory).  It might be doable;
> it's all a matter of programming, obviously... ;)
>
> Note that on real-world websites nesting 10-deep of shrink-wrap boxes is not
> uncommon.  We've seen nesting up to 30-deep on some sites that didn't do
> well with exponential growth in nesting depth... ;)

Eh, I can imagine ;-) and by the way, I'm glad you're still sticking
with me and pointing out the errors in my plan.

For example, I hadn't considered the percentage width case. Let me
think about it, though, because at first thought I cannot easily find
a case when the layout would need to be recomputed. Relayouting would
be needed when the final width of the shrink-wrap turns out to be
different (and specifically, smaller) than the maximum allowed width M
= max(minprefwidth, available-space) in a context in which it cannot
be precomputed some other way. When can this happen?

In what follows, let me call lines the block-level content one would
get when only splitting the content at obligatory breaks (i.e. the
blocks whose width is roughly estimated by the first step of the
current shrink-wrap spec). Due to the way M is computed, it will not
be smaller than the intrinsic width of any unbreakable line. Also, for
any line that also involves pct-width elements, the fitting width can
be computed as F = W/(1-p) where W is the intrinsic width of the
non-pct-width part, and p is the total pct width. By convention, let F
be 0 for lines that W = 0 (only pct-width components). If for all
lines we have F <= M, then we can set the shrink-wrap width at the
maximum of these F, or M if F = 0 for all lines. Note that for these
situations we do not need to do any actual layout (even if nested
shrink-wraps are involved, as long as they are also in the same
situation).

The problem would arise if there is at least one line where F > M. In
this case the content of the line needs to be reflown, and the actual
breakpoints depend on the actual width of the pct-width. But in this
case you can reflow the non-pct part assuming a max-width of (1-p)M,
and then work with these lines as mentioned above. Something like this
should work rather straightforwardly even with nested shrink-wraps,
where the available space of each nested shrink-wrap is (1-p)M.

So the idea is to do a _partial_ layout on the first pass, considering
the pct-width components only for their contribution to the width of
lines they influence, and then doing a second pass that does the
actual layout for the parts that were not laid out during the first
pass, that only involves taking widths and splitting. This way, there
should be no double-laying out and not much additional structure.

Would something like this make sense?


-- 
Giuseppe "Oblomov" Bilotta

Received on Thursday, 28 October 2010 20:50:26 UTC