[ 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/ >
