cleaning up layout
L. David Baron
[ I'd like to prefix this by saying that I'd like to use
mozilla-layout more for its original purpose -- discussion between
layout engine developers. It's much better to have discussion in the
open because it makes it much easier for new people to get involved --
people who I wouldn't have cc:ed if I were sending this by private
email. However, using mozilla-layout can only work if the
signal-to-noise ratio is low enough. That means I won't necessarily
respond to all responses to this in public -- I may respond to some in
private email, or some not at all. ]
Here are a bunch of related things that I'd like to fix in Layout. I've
been thinking about which of these are more important and in which order
these things should be done (since they're quite related). Some of the
sections below are more coherent than others. More on that below.
Line breaking
=============
I'd like to implement the UAX #14 algorithm for line breaking. See
http://www.unicode.org/reports/tr14/ . The algorithm is relatively
simple since it's pair-based. This would be vastly more advanced than
what we now have, which breaks only on spaces for western text. We'd
probably also want to make nsTextTransformer transform away a few more
characters than it does now, and also handle ­. (Well,
there was an attempt to implement correctly, but it was really
broken -- see bug 187899 comment 7.)
Our current JIS X 4051 linebreaker is documented in a way that makes it
hard to understand without a copy of the JIS X 4051 standard, so it's
somewhat hard for me to tell whether such a change would improve or
worsen our linebreaking for CJK languages. However, having tested the
way we handle breaking around '-' in CJK languages, I certainly wouldn't
be surprised if it would help.
Storing the results of line breaking and text measurement
=========================================================
I think in an ideal world, each text frame ought to store an array of
the possible break points in it, and the measurement to reach each one.
(How to handle trimming of final spaces?)
This looks easy on Windows, where we currently have complicated text
measurement optimizations, and this would allow us to just call
GetTextExtentExPoint instead of GetTextExtent32. (Any idea why we
didn't do that before?)
On the mac we could use MeasureText (or MeasureJustified?) instead of
TextWidth.
For nsXFontNormal and nsFontMetricsXft, it looks like we have to
measure by pieces, ourselves, and that's likely true for the other
Unix APIs we have to deal with. We could always write some shared
code to do the measurement-by-pieces.
Storing this stuff would avoid the need for functions to compute line
breaks in either direction (a good bit of code in nsTextTransformer and
nsJISx4051LineBreaker) just for shift-rightarrow.
Line breaking needs to be word-by-word (where a "word" is an unbreakable
unit, not a word, but I'll call it a word because it's easier to type),
not box-by-box (e.g., nsLineLayout::CanPlaceFrame). (An nsIFrame "is a"
box, in CSS terms.) I think we currently have a bunch of line breaking
bugs where things that are in different boxes don't stick together when
they should, and I suspect it's probably related to this design,
although I haven't investigated in detail. I'm not sure what this
should mean for whether we try to call the line breaking code one word
at a time or one box at a time -- I think it could still work with the
latter, assuming the actual "where do we wrap" question isn't handled by
trying to place one box or piece of a box at a time, as it partly is
now.
Requirements for handling dynamic changes
=========================================
There are only a few cases for which we need to optimize:
1. Ensuring that the time to respond to small changes is
proportionately small, which is important for:
a. incremental loading of pages
b. specified style changes to very small parts of pages
c. editing operations
2. resizing of the window
3. changes to 'top', 'left', 'right', and 'bottom'
Pretty much everything else doesn't matter. In particular, any changes
to the specified style for an element should mean *everything* inside
that element gets recomputed (and a good bit outside, but that falls
under the optimizations for (1)).
The optimization to make in (2) is not to recalculate intrinsic widths
(min/max widths), which would be simpler to do in a world where min/max
width computation were separate from reflow. (See bugs marked with
[reflow-refactor] in the status whiteboard for other things that such a
refactoring would fix. Probably the worst of these bugs relate to the
fact that minimum width is computed in the same pass as either preferred
width or a layout, and thus subject to different containing block
dimensions depending on when it is calculated.)
It would be nice if the optimization we'd need to make for (3) meant we
could just move things and recompute overflow areas. I think this was
the original intent of those properties. I also thought this when I
commented in bug 157681. However, I'm afraid that's not actually the
case, and the rules in the current CSS2.1 draft are correct as far as
WinIE compatibility goes. However, caching of preferred and minimum
widths should mean that we don't need to re-layout in the vast majority
of cases.
The optimizations necessary for (1), particularly (1a), should maintain
the invariants that:
A. The page always ends up displayed the same way, no matter what the
units of incremental layout were during its load
B. The result after any incremental load of part of a page should be
the same as if that part were the whole page (excluding unloaded
images, etc.) Otherwise we confuse authors and encourage hacks to
prevent incremental reflow.
Incremental loading of content requires recomputation of preferred
widths and of sizes for almost any content that has descendants
modified. More on this later, perhaps...
Refactoring reflow
==================
I want to split Reflow() into GetMinWidth(), GetPrefWidth(), and
Layout(). This seems relatively straightforward to me once the issue of
how to integrate it with line breaking is handled, although it's a huge
amount of work. However, I think it may be possible to make the changes
for blocks but keep the inline code working roughly as it does now.
This may be the best approach to doing this first.
I think the complexity of Reflow()'s semantics are the source of a lot
of bugs (many of which are marked [reflow-refactor], although some of
those are things that could be fixed with difficulty in the current
design). I think separating GetMinWidth() and GetPrefWidth() will make
the code much easier to maintain and make it much easier to implement
the correct layout rules for things like inline-block and inline-table
(never mind fixing bugs with floats or absolutely positioned elements).
Splitting reflow is very closely tied in to the system we use for noting
which layout computations need to be recomputed for dynamic changes to
documents.
Dirty bits
==========
Our current system for meeting the above requirements is quite
complicated. We have the reflow tree, which is essentially out of line
dirty bits, we have two frame state bits (NS_FRAME_IS_DIRTY and
NS_FRAME_HAS_DIRTY_CHILDREN, which have different meanings in block code
and XUL nsIBox implementations, and the block meaning of the latter
should be mostly obsolete thanks to the reflow tree). Then we have
reflow types and reflow reasons, which roughly correspond to each other.
But we have too many types and reasons -- we should really only have
ones for things that we need to optimize, and everything else should
just do "full reflow" of some subtree.
That leaves figuring out a simpler solution that meets the requirements
in the previous section. My current thoughts are:
Block-ish frames should have two additional member variables for their
minimum and preferred width, with special (largest possible?) values for
"descendant is dirty" and "completely dirty" states.
We should have frame state bits for "descendant is dirty" and
"completely dirty" states as well. (Or do we need two types of
"completely dirty" for the resize optimizations? Is this sufficient to
get rid of reflow reasons?)
But I haven't thought this through too carefully yet.
Frame construction
==================
Something along the lines of CSS3's 'display-role' and 'display-model'.
We need to figure out the right set of objects to do this. I think this
is probably well in the distance at this point.
The plan
========
Which pieces of the above should happen first? One possibility is to do
UAX #14, then line breaking, then reflow refactoring and dirty bits
(which I suspect are effectively inseparable), then the frame
construction changes. This is a somewhat logical order.
However, I think the parts from which we'd get the most real,
user-visible, gain, and the most ability to implement new features
easily, are the reflow refactoring of blocks and the UAX #14
linebreaking.
So an alternative, which I suspect is probably better, is to do the
reflow refactoring for blocks but not inlines (which would solve most of
the bugs). In other words, we'll continue moving inlines around to
determine preferred width and minimum width. That would allow work to
continue on incrementality optimizations and line breaking / text
measurement in parallel, and the full reflow refactoring (or movement to
whatever method we want to use for inline layout -- it's really a bit
different anyway) would still wait until the end. I'm probably going to
look into exactly what it would take to do this bit next, and probably
write up some more detailed design ideas.
Thoughts?
-David
--
L. David Baron <URL: http://dbaron.org/ >
Robert O'Callahan
L. David Baron wrote:
> I think in an ideal world, each text frame ought to store an array of
> the possible break points in it, and the measurement to reach each one.
> (How to handle trimming of final spaces?)
This sounds like it could be a significant space increase. Still could
be a good idea though.
> The plan
> ========
>
> Which pieces of the above should happen first? One possibility is to do
> UAX #14, then line breaking, then reflow refactoring and dirty bits
> (which I suspect are effectively inseparable), then the frame
> construction changes. This is a somewhat logical order.
>
> However, I think the parts from which we'd get the most real,
> user-visible, gain, and the most ability to implement new features
> easily, are the reflow refactoring of blocks and the UAX #14
> linebreaking.
>
> So an alternative, which I suspect is probably better, is to do the
> reflow refactoring for blocks but not inlines (which would solve most of
> the bugs). In other words, we'll continue moving inlines around to
> determine preferred width and minimum width. That would allow work to
> continue on incrementality optimizations and line breaking / text
> measurement in parallel, and the full reflow refactoring (or movement to
> whatever method we want to use for inline layout -- it's really a bit
> different anyway) would still wait until the end. I'm probably going to
> look into exactly what it would take to do this bit next, and probably
> write up some more detailed design ideas.
Sounds like a very good plan.
Rob
fantasai
> Line breaking
> =============
>
> I'd like to implement the UAX #14 algorithm for line breaking. See
> http://www.unicode.org/reports/tr14/ . The algorithm is relatively
> simple since it's pair-based. This would be vastly more advanced than
> what we now have, which breaks only on spaces for western text. We'd
> probably also want to make nsTextTransformer transform away a few more
> characters than it does now, and also handle ­. (Well,
> there was an attempt to implement correctly, but it was really
> broken -- see bug 187899 comment 7.)
Two points:
1. In discussions on line breaking on www-style, Jukka Korpela brought
up some criticism [1] on the UAX 14 algorithm. For example, breaks
are disallowed before slashes '/' even with intervening spaces,
resulting in some weird line breaks [2].
So the UAX 14 algorithm should be taken with some reservation.
2. If we're breaking in places that aren't spaces, we need to
prioritize break points. It doesn't need to be complex, but it
needs to be there, or we'll be breaking things like "s/he" and
the "-a" Jukka mentions in [2].
A simple prioritizing algorithm like the one outlined in [3]
would suffice. (Though in the context of Mozilla, it may not be
quite so simple. ;)
[1] http://www.cs.tut.fi/~jkorpela/unicode/linebr.html
[2] http://lists.w3.org/Archives/Public/www-style/2003May/0014.html
(Fifth reply section, with /usr/spool example.)
[3] http://lists.w3.org/Archives/Public/www-style/2003May/0010.html
("As a simplistic example...")
~fantasai