W3C home > Mailing lists > Public > www-style@w3.org > October 2010

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

From: Giuseppe Bilotta <giuseppe.bilotta@gmail.com>
Date: Thu, 28 Oct 2010 18:22:13 +0200
Message-ID: <AANLkTik_x2ZU2MiU8VC7O3cnXxhBc3+5x0mE8NkbWrDi@mail.gmail.com>
To: Boris Zbarsky <bzbarsky@mit.edu>
Cc: WWW Style <www-style@w3.org>
On Thu, Oct 28, 2010 at 5:04 PM, Boris Zbarsky <bzbarsky@mit.edu> wrote:
> On 10/28/10 10:52 AM, Giuseppe Bilotta wrote:
>>
>> And how is that different from the first step of the current
>> algorithm? Don't you need to do a full layout of all the descendants
>
> No, you just need to apply some basic heuristics (look at the computed
> styles, plus the simple shrink-wrap algorithm) for them.
>
>> The only difference I see is that in the algorithm currently used, the
>> layout is done assuming max-width: none, whereas in my case it would
>> be done assuming max-width: available-width. Or am I missing
>> something?
>
> I think you are missing something.
>
> To make this concrete, for a block box in Gecko the width determination when
> shrink-wrapping (which is what needs to be done on all descendants in a
> shrink-wrap situation is
> http://hg.mozilla.org/mozilla-central/file/882525a98119/layout/generic/nsBlockFrame.cpp#l762
> going through line 837.  It does call some other code; total estimated
> amount of code involved including all the functions this calls is < 1000
> lines.
>
> The code for doing an actual layout is
> http://hg.mozilla.org/mozilla-central/file/882525a98119/layout/generic/nsBlockFrame.cpp#l1770
> going through line 2370.  Total estimated amount of code involves is tens of
> thousands of lines.

I see. I somehow expected the preferred width to be computed in a
stricter way, which is why I couldn't figure why my proposed approach
would be so costly instead. Now it's clearer, even though by reading
through some of the code it would seem like they could use some kind
of max-width specification, although it still probably wouldn't help
due to the quick way the computations are done.

>> There's an additional bonus here, too, since most of the results of
>> the layout during the "preferred width not greater than the available
>> width" can actually be directly used, whereas with the current
>> specification, after laying out the inner boxes assuming no max-width
>> you'd have to re-layout them assuming the shrinked width.
>
> You're making the assumption that actual layout happens during the
> shrink-wrap pass.  The point is, it doesn't.  Some heuristics are used to
> approximate what layout would look like and avoid all the complexity of
> actual layout.

Right. So my question is: since sooner or later the layout has to be
done anyway, would it be possible to do it _during_ the shrink-wrap
pass?

IOW, would an algorithm such as the following be possible?

(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)

Would this be more expensive than the current approach, given that the
total amount of work (for finding the width plus doing the layout)
would be basically the same? (We wouldn't have to find the maximum
preferred width, but we might have to do some positional adjustment to
the inner box after the shrink-wrapping container is set). As
expensive as the layout might be, it's being done in both cases,
modulo some shifts.

>>> and _still_ gives "incorrect" results in many cases.  The set of cases
>>> where
>>> this behavior helps is very small...
>>
>> I would like to know of some of the cases where my proposed algorithm
>> would give "incorrect" result
>
> For Gecko's old implementation, which basically used your proposal, that
> would be most of the crossed-out items in the "Bug 300030 blocks" section of
> https://bugzilla.mozilla.org/showdependencytree.cgi?id=300030&hide_resolved=0

Thanks. I haven't had time to go through all of them, but the ones I
sampled seemed more like (1) either bugs in the way the preferred
width was computed (something which, I dare say, can also happen with
the current implemention of the current shrink-wrap algorithm, if some
important factor is not taken into consideration during the rough
estimate, and (2) bugs that are actually caused by some page layout
relying on the existing not-really-shrink-wrapping shrink-wap
specification.

In either case, an option such s width: fit-content to trigger a
"true" shrink-to-fit wouldn't go against either, especially if you can
confirm my remark above, that the total layout cost doesn't change
much. What I _do_ see as a problem to the acceptance of this
alternative in the spec is that CSS tends to have more of a 'top down'
approach, laying out the outer box first and then filling them,
whereas my proposed approach goes a little against that by suggesting
the preparation of the filling first.



-- 
Giuseppe "Oblomov" Bilotta
Received on Thursday, 28 October 2010 16:23:17 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 17:20:33 GMT