Gecko:Reflow Refactoring

From MozillaWiki
Jump to: navigation, search

Landed 2006-12-07, see bug 300030

Background and Terminology

The CSS specification has a concept of a rendering object, which it calls a box. There is a tree of rendering objects parallel to and close-to-isomorphic to the content (or DOM) tree. In Mozilla, these rendering objects are implemented by objects that implement the nsIFrame interface (and, for XUL, also the nsIBox interface), known as frames.

There are three main operations performed on these objects:

  • frame construction (building the tree of objects)
  • reflow (determining their positions; should perhaps have been called Layout instead), and
  • painting (drawing them on the screen) (the code to determine targets for events is closely connected to the painting code, so it can be considered part of this area).

The algorithms used to determine the positions of some types of rendering objects are described in the CSS specifications. The most important version of the specification is CSS2.1, and the chapter with the most interesting material is 10 (visudet.html), although 9 (visuren.html), 11 (visufx.html), and 8 (box.html) are also quite relevant. However, many of the rendering objects are described poorly (tables) or not at all (form controls, many other things) by the CSS2.1 specification.

The algorithms used to determine the positions of XUL rendering objects are architecturally rather different. See dbaron's XTech 2006 paper for some further discussion of this difference.

Summary

Reflow refactoring is the name for two related changes currently being worked on mainly by dbaron:

  • Change intrinsic width computation so that it happens in separate methods on nsIFrame. (Currently preferred width calculation using the nsIFrame API can happen in two different ways as well: having only one codepath reduces incremental layout ("{inc}") bugs.)
  • Change the way we handle incremental layout to use dirty bits on the frames rather than the reflow tree (which is essentially out-of-line dirty bits) and a complicated system of reflow reasons that often leads to weird incremental layout ("{inc}") bugs.

The goals of these changes are:

  • simplification of code
  • fixing incremental reflow ("{inc}") bugs
  • fixing intrinsic sizing bugs
  • allowing better integration of nsIBox and nsIFrame layout
  • allowing easier implementation of new features like 'inline-block'

Quick Links

Build Instructions

The reflow branch landed on the trunk on December 7, 2006, so the normal trunk build instructions now apply.

Rationale

The goal of the branch is to change the design in two areas of layout that have given us the most problems due to their complexity. It will also help make the nsIFrame and nsIBox layout methods a little more similar.

nsIFrame and nsIBox layout

Understanding the current situation with Mozilla's rendering objects requires understanding a bit of history, since it's currently in a state that nobody really intended.

CSS sort of has a notion of a rendering tree: a tree structure that's similar to the content tree but also contains pseudo-elements and does not contain objects that are display:none. In the original Gecko codebase, the objects in the rendering tree were intended to be implementations of nsIFrame. Different implementations would be used for different types of rendering objects: for example, objects with CSS display:block (nsBlockFrame), objects with CSS display:inline (nsInlineFrame), HTML <input type="text"> or <textarea> (nsTextControlFrame), or images resulting from <img> or <object> (nsImageFrame).

When the XUL layout model was implemented, nsIFrame was found not to be suitable for the flexible box model needed for XUL. So, for better or for worse, a second interface for rendering objects came into existence: nsIBox. XUL layout objects also delegate to singleton nsIBoxLayout objects for a number of the things that differentiate different types of rendering objects.

In an effort to reduce the size of box rendering objects (which had to implement nsIFrame and nsIBox), the two rendering object interfaces have been merged into nsIFrame and the merged list of methods is on track to be gradually consolidated. Base implementations of the separate methods are still split between nsBox and nsFrame, although the latter inherits from the former. The method nsIFrame::IsBoxFrame is the way the two types of objects can currently be distinguished.

The handling of the boundary between box and non-box rendering objects is currently handled in two places: the code in nsBoxFrame and nsLeafBoxFrame handles a box inside a non-box. The box methods on nsFrame handle a non-box being inside a box (although these used to be on a separate class called nsBoxToBlockAdaptor).

Intrinsic sizing changes

One of the messy areas in the current code is the way we do intrinsic width calculation. A number of aspects of CSS and HTML layout (such as table layout and floats or absolutely positioned elements with width:auto) depend on two different concepts of intrinsic width. One of those we generally call the preferred width: this is roughly the widest width that the element can usefully occupy. For example, the preferred width of a line of text is the width of that line when laid out without any breaks. The second we generally call the minimum width: this is roughly the narrowest width that the element can occupy without overflow. For example, the minimum width of a line of text is the width of the widest word in the line. dbaron has started to write a specification for intrinsic widths.

The basic problem with what's messy about intrinsic sizing in nsIFrame layout in Gecko is that a single method, nsIFrame::Reflow, is used to do final layout and to calculate both types of intrinsic widths. The minimum width is calculated by asking for the "max-element-width", and the preferred width is calculated in one of two ways: reflowing with NS_UNCONSTRAINEDSIZE as the available width and computed width or setting the NS_REFLOW_CALC_MAX_WIDTH flag. Inconsistencies between implementations of these two methods mean that callers that use both at different times face incremental reflow bugs. (Various callers call them in different ways, though.) There are also block flags that tell blocks to compute their final size in special ways that depend on the intrinsic widths in various ways.

The other problem is that box layout uses a completely different intrinsic sizing mechanism: it uses three intrinsic widths and intrinsic heights: GetMinSize, GetPrefSize, and GetMaxSize (which isn't generally all that interesting or useful). These are separate methods from the box method to do final layout, which is called Layout. Note that the size (width x height) vs. width difference between the two layout models will remain after this work.

Incremental layout Changes

Purpose of incremental layout

(This section is taken from a post dbaron wrote.)

There are certain situations where it's important that we not recompute the layout of everything in the page. (These are in general based on the idea that layout time is roughly linear in the amount of content being laid out.)

  1. Ensuring that the time to respond to small changes is proportionately small, which is important for:
    1. incremental loading of pages (which should be O(N) rather than O(N^2))
    2. specified style changes to very small parts of pages
    3. editing operations
  2. resizing of the window
  3. changes to the CSS properties 'top', 'left', 'right', and 'bottom' that move positioned elements

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 is much simpler to do in a world where min/max width computation were separate from reflow. (This is one of the connections between these two changes that makes them easier to do at the same time.)

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 (1.1), should maintain the invariants that:

  1. The page always ends up displayed the same way, no matter what the units of incremental layout were during its load
  2. 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...

The current incremental layout system

The current incremental layout system used by non-box layout is quite complex and has been the source of hard-to-fix bugs (although we've worked around most of the serious ones). The basic idea is that there are a bunch of different types of reflows that can be done, and different types cause different things to be recomputed. We have two different enums for these: reflow types (stored on reflow commands) and reflow reasons (passed as input to nsIFrame::Reflow within the nsHTMLReflowState). When a frame is dirty for some reason, we create a reflow command object (nsHTMLReflowCommand) which is put in a reflow tree (of nsReflowPath), which is used to track which frames have dirty children and coalesce the processing of multiple reflow commands into a single reflow.

One of the reflow reasons is eReflowReason_Incremental, which means that there is at least one reflow command on a descendant but otherwise nothing needs to be handled. Another is eReflowReason_Resize, which means that only the final width needs to be recalculated (intrinsic widths do not). Another is eReflowReason_StyleChange, which means that everything, including intrinsic widths, needs to be recalculated. The other reflow reasons and the reflow types not corresponding to these reasons (other than incremental, which has no corresponding reflow type) are poorly defined and hopefully unnecessary.

There are also methods on the pres shell to cause a style change or resize reflow over the entire frame tree: these don't rely on a reflow command at some point in the reflow tree to convert the incremental reflow reason to a style change or resize; instead, they start with a style change or resize reflow reason from the top of the tree.

In addition to the information in the reflow commands (which are in the reflow tree), there are two bits, NS_FRAME_IS_DIRTY and NS_FRAME_HAS_DIRTY_CHILDREN. They are used very differently for non-box and box layout. (Maybe it's worth explaining, but I don't remember the whole business, nor do I much care. - Dbaron)

Design

Parts of this section are taken from a post dbaron wrote.

Intrinsic Sizing

The ability to determine intrinsic widths using the Reflow method has been removed.

Four new methods are being added to nsIFrame for intrinsic width calculation. GetMinWidth and GetPrefWidth simply return the minimum/preferred width of the frame. AddInlineMinWidth and AddInlinePrefWidth are used to build up intrinsic width information for inline layout, where we need to accumulate information for whatever could be on the same line. These special methods for inline layout are needed since multiple frames can be on one line, and one frame could be split into multiple frames across multiple lines. The state of that line breaking at any given time should not influence what the frames return for their intrinsic widths.

Since frames will receive a MarkIntrinsicWidthsDirty call when intrinsic widths may have changed (a part of the new incremental layout design), they may cache intrinsic width results. Which frames should cache is a performance/memory tradeoff, but my current plan is that at least blocks and some table frames should cache their intrinsic sizes. Probably caching should be added to some box frames as well.

It is important to note that the GetMinWidth and GetPrefWidth functions return content-box widths. This is helpful because intrinsic widths are often compared to the results of the 'width', 'min-width', and 'max-width' properties and may in the future also be used for proposed of these properties such as intrinsic and min-intrinsic and shrink-wrap. It is also important that the results of GetMinWidth and GetPrefWidth are not influenced by the width, min-width, and max-width properties. This is important so that the results can be used as special values for these properties. However, what the containing frame is generally interested in when computing its own values for these functions is the intrinsic width as influenced by these properties (since the properties override any intrinsic size), and with the padding, border, and margin added on. The function nsLayoutUtils::IntrinsicForContainer does this. (Note that neither of these caveats apply to AddInlineMinWidth and AddInlinePrefWidth.)

Incremental Layout

Reflow commands, reflow types, and reflow reasons are being removed. So are box layout reasons and box's style change flag.

The meaning of the NS_FRAME_IS_DIRTY and NS_FRAME_HAS_DIRTY_CHILDREN bits is being defined more consistently. NS_FRAME_IS_DIRTY means that a frame is inconsistent in some way and Reflow must be called on that frame. NS_FRAME_HAS_DIRTY_CHILDREN means the frame has a descendant with NS_FRAME_IS_DIRTY set or has had a descendant removed.

When Reflow is called on a frame that has NS_FRAME_IS_DIRTY set, it should recompute pretty much everything. (Intrinsic width calculation is now independent, though, so its recomputation is as well; see below.) When Reflow is called on a frame that has NS_FRAME_HAS_DIRTY_CHILDREN set, it is responsible for calling Reflow on at least the children that have one of the two bits set. When Reflow is called on a frame that does not have NS_FRAME_IS_DIRTY set but the computed width in the reflow state is different from the frame's current width, then it should also reflow its children so they can resize. (This is actually a relatively recent change, but it allows restoring the resize reflow optimizations that I was initially planning to remove. - Dbaron 21:33, 5 Oct 2005 (PDT)) The method nsHTMLReflowState::ShouldReflowAllKids checks both the NS_FRAME_IS_DIRTY bit and the resize case, for convenience.

New methods are being added (see above) to indicate that intrinsic width information is dirty. These methods should only be called by nsPresShell::FrameNeedsReflow since that will mark intrinsic widths dirty on descendants (if appropriate) and ancestors.

One of the messy issues with incremental layout is in the layout protocol. Non-box layout uses Reflow, which expects the frame's rect to be set after Reflow, and often uses the old rect for optimization. Box layout uses Layout, which expects the frame's rect to be set before Layout. This makes some resize optimizations harder. Perhaps box should switch to setting the rect after Layout, although this does require more state to be passed in to Layout.

Status

Currently a lot of the design is done but subject to change. CSS block/inline layout code and XUL box layout code have been converted to the new design and work well enough that the Firefox UI basically works (although with some glitches). MathML has not yet been converted to the new intrinsic width calculation design, although it does compile.

Future Development Tasks

  • investigate whether special height reflow quirks were introduced into standards mode for non-tables in the case where a table cell has both a table and a non-table child with percentage heights
  • add quirks related to line breaking around replaced elements
  • fix incremental reflow regression on acid2 from first round of vertical resizing changes - Done David Baron 17:02, 21 June 2006 (PDT)
  • figure out why vertical resizing changes affected acid2 at all
  • fix display of acid2 test as -chrome (one line is wrong) - Done David Baron 17:07, 21 June 2006 (PDT)
  • Make sure NS_FRAME_CONTAINS_RELATIVE_HEIGHT works right for quirks percentage heights
  • fix marquee
  • consolidate move-but-don't-reflow code into nsIFrame::SlideTo and nsIFrame::SlideBy (with the code to handle the not-same-position case shared)
  • try to remove the aInit parameter from the nsHTMLReflowState constructor
  • assertions print-previewing mozilla.com - Done David Baron 18:19, 1 July 2006 (PDT)
  • fix asserts and maybe bugs on testcase
  • make sure the propagation of NS_FRAME_IS_DIRTY to children works on boxes, and through block->box->block
  • fix intrinsic sizing bug in default browser prompt, which has something to do with either insufficient invalidation on image load or a timing change related to the image load Done, David Baron 17:10, 6 Oct 2005 (PDT)
  • figure out why the text in the caps privilege dialog doesn't wrap anymore Done, David Baron 01:01, 8 Oct 2005 (PDT)
  • make sure that resize codepaths are correct, i.e., that frames reflow all of their children when nsHTMLReflowState.mFlags.mIsResize is true. Done David Baron 01:29, 7 Oct 2005 (PDT)
  • convert table code (David Baron priority #1) - Table reflow optimization
  • Sort out the behavior of nsHTMLReflowState::InitConstraints when parentReflowState is null. This happens for reflow roots and for frames being reflowed as a child of a box (via nsFrame::BoxReflow). The current behavior seems wrong.
  • fix bugs
    • create better communication between nsHTMLReflowState and nsTableFrame about computed widths on tables so that we can do both intrinsic sizing and specified widths correctly, for both values of border-collapse, Done David Baron 01:58, 13 April 2006 (PDT)
    • rename nsHTMLReflowState::mIsResize to mHResize, and add an mVResize so that ShouldReflowAllKids doesn't optimize away vertical resizes - Done David Baron 23:42, 22 June 2006 (PDT)
    • test vertical resizes more carefully
    • HR elements don't resize
    • hit CachedIsEmpty and other assertions loading acid2, although it displays fine
    • empty cells' borders (e.g., on tinderbox) pop in when resizing Done, David Baron 14:22, 2 June 2006 (PDT)
    • fix side captions in nsTableOuterFrame or nsHTMLReflowState
    • consider going back to old top/bottom caption behavior in nsTableOuterFrame or nsHTMLReflowState
    • incremental reflow bug (images blank) on Firefox start page - Done David Baron 23:39, 22 June 2006 (PDT)
    • incremental reflow bug (small gaps) on Firefox start page - Done David Baron 16:11, 23 June 2006 (PDT)
    • make width on tables not override intrinsic minimum width [Is this done at this point?]
    • Firefox and Seamonkey print preview doesn't make the print preview tall enough.
    • fix layout problems on network error pages - Done David Baron 18:19, 1 July 2006 (PDT)
      • figure out who (frame class?) should compute intrinsic width when about to reflow an inline-box or inline-block within inline layout
    • Fix https://bugzilla.mozilla.org/attachment.cgi?id=200664 -- minimal testcase is http://wargers.org/mozilla/margin_100_percent.html
    • Fix assert on the following markup: <select multiple size=1><option>o </select> (note space after the "o") - Fixed David Baron 5 June 2006
  • convert form control code
    • figure out whether to refactor nsLeafFrame::GetDesiredSize and implement nsLeafFrame::GetMinWidth and nsLeafFrame::GetPrefWidth in terms of it or whether to implement GetMinWidth and GetPrefWidth separately for all the subclasses of nsLeafFrame that use GetDesiredSize - done, bzbarsky, 1 May 2006
    • go back to caching ascent again and optimizing more
      • or should ascent just be a member of nsIFrame?
      • or should ascent computation just be separate from reflow?
  • convert MathML code
    • similar refactoring decisions as for nsLeafFrame, but the inline intrinsic width API may be more involved here
  • Figure out whether the inline min/pref width interfaces currently on the branch (nsIFrame::GetInlineMinWidth and GetInlinePrefWidth) are sufficient or whether we need to make additional architectural changes related to continuations (particularly making various special things use the existing next-in-flow model)
  • figure out why nsDocShellTreeOwner::SizeShellTo calls ResizeReflow directly and fix it
  • go through "XXX" comments added on branch and address them
  • should table special height reflows mark dirty or ensure nsHTMLReflowState::mFlags.mVResize is set and depend on vertical resize optimizations?
  • We can end up in a state where mDirtyRoots is empty after a FrameNeedsReflow() call -- when nsGfxScrollFrameInner::LayoutScrollbars sets attributes on the slider we end up in nsSliderFrame::AttributeChanged which calls FrameNeedsReflow(). Should we be checking that boolean that the scrollframe uses to tell itself that it's not a real curpos change?
  • debug assertions related to special height reflows in gmail *compose*

Future Testing Tasks

  • Make sure dbaron's existing testcases work
  • develop more table testcases
    • test boundary and overflow conditions for percentage widths in tables
    • test table-layout:fixed better
    • test table captions
    • test min-width and max-width on table cells, columns, and tables, with both lengths and percentages, and for both auto and fixed table-layout
  • Develop testcases that test box-block boundaries better
  • Extend intrinsic sizing testcases to check that padding, border, and margin are counted correctly, especially around box-block boundaries
  • Test XUL user interfaces
  • Test Web pages
  • performance testing
    • performance metrics that run on tinderbox
    • profiling
    • test resizes and incremental changes under reflow logging to make sure things are as expected
    • test potential performance improvements
      • combine AddInlinePrefWidth and AddInlineMinWidth into one function to avoid two passes of text measurement (this could hurt the non-table cases, though, which often call GetPrefWith but not GetMinWidth)
      • make MarkIntrinsicWidthsDirty take a child that was dirty to allow blocks to optimize per-line
  • test percentage height quirks

Discussion and Feedback

Discussion and feedback about technical issues related to these changes takes place on the dev-tech-layout mailing list / mozilla.dev.tech.layout newsgroup:

Please only email the list / post to the newsgroup about these changes if your message will contribute to the success of these changes or help you contribute to it.

Retrieved from "https://wiki.mozilla.org/index.php?title=Gecko:Reflow_Refactoring&oldid=57487"