Eyes Above The Waves

Robert O'Callahan. Christian. Repatriate Kiwi. Hacker.

Saturday 29 December 2007

Our Rectangles Overfloweth

When we're laying out content in Gecko, we create an nsIFrame object for each CSS box for each element, as I've described previously. CSS actually defines several kinds of boxes: margin boxes, border boxes, padding boxes and content boxes, depending on exactly what part of each element is included. In nsIFrames we store border-boxes always, and can reconstruct margin, padding and content boxes on demand.

CSS boxes for an element do not necessarily contain the boxes for that element's children. However, there are some situations where we want to aggregate geometry information for an entire subtree of elements:

  • For "overflow:scroll/auto" elements we need to figure out how far we should permit scrolling in each direction. A reasonable thing to do here would be to compute, and possibly store, the smallest rectangle containing the border-boxes for all elements which have the scrollable element as a containing block ancestor. Note that for overflow:auto elements, we need to know this during layout because we need to decide whether scrollbars should be shown.
  • To optimize repainting, we want to be able to quickly test whether a subtree of content is responsible for painting anything visible in a given rectangle that needs repainting. An obvious solution is to store on some or all elements a rectangle which contains all pixels drawn by the subtree rooted at the element.

In Gecko we mash together both of these concepts into the single concept of an "overflow rect". Every nsIFrame has an "overflow rect" which is the smallest rect containing both every pixel drawn by the frame and its descendants, and also the border-boxes of the frame and its descendants. We do the obvious optimization of not storing the rect when it's equal to the frame's border-box --- usually true since overflow is still the uncommon case. Combining the two concepts simplifies code and reduces memory usage. It usually doesn't produce any noticeable effects, but there are some unfortunate and relatively rare situations where it does. For example, adding a CSS "outline" to the child of an overflow:auto element can result in a scrollbar being displayed just so you can scroll the edge of the outline into view.

One unfortunate thing is that right now every container frame's Reflow method is responsible for computing the overflow area for the frame by unioning together the overflow areas of all child frames. It's only a few lines per Reflow method but like all code duplication it's unnecessary bloat and it's fragile too.

Another unfortunate thing is that the "bounding box of drawn pixels" area can be expensive to compute, in particular because it means you have to retrieve the ink extents for every glyph.

In a perfect world, I think we'd separate these two concepts, and store 0, 1 or 2 additional rectangles for each nsIFrame. We'd compute "scrollable overflow areas" by walking the frame tree directly from scrollframes instead of spraying code through Reflow() implementations. We'd compute the "drawing overflow area" lazily, possibly even while painting; this would get the expensive glyph extents operations off the layout path, which would speed up layout flushes, e.g. when script requests geometry data via getBoundingClientRect() or offsetTop.

I've thought pretty hard about ways to avoid computing the "drawing overflow area" at all. It's certainly possible for content that remains hidden, such as a hidden IFRAME or background tab. Unfortunately for the common case of page loading you almost always load the page, render it, and then something changes on the page --- a caret blink, an animated GIF, incremental content load --- and that usually forces you to compute the "drawing overflow area" of most elements in the page, in case they overlap the area you need to repaint. For example we should get the extents of each glyph on the page, to see if there's an insanely large glyph that might overlap the repaint area. (As I've explained in other posts, currently, even on trunk, for performance reasons we fudge and assume that at small font sizes glyphs stay within their regular font boxes. Webkit does something similar.)


Alfred Kayser
Some comments:
1. Don't forget about 'outline', which adds another box that can contain drawable pixels.
2. For animated images, if we apply the rule that the size of the first frame is the total size of the animated image, the actual size of the box of drawable doesn't change. (but for some frame only a part of it needs to be redrawn).