Mozilla's Layout Engine

Layout

• where things go on the screen / paper
• between content and view+gfx
• also interacts with images, plugins, etc.

Layout (and neighbors)

• single threaded
• most operations run to completion off main event loop
  • some things triggered synchronously by scripts even though typically asynchronous

Layout (and neighbors): Key Data Structures

Content

parse tree of markup

Frames

Rectangular formatting primitive

Style contexts

Computed style data

Views

Going away (z-order, compositing)

Widgets

Native windows (we want only one)

Input (concepts)

• content tree
• images, plugins, etc.

Input: Content tree

<doc>
  <title>A few quotes</title>
  <para class="emph">
    Franklin said that <quote>"A penny
    saved is a penny earned."</quote>
  </para>
  <para>
    FDR said <quote>"We have nothing to
    fear but <span class="emph">fear
    itself.</span>"</quote>
  </para>
</doc>

Input: Content tree

Input: Content Tree APIs

• nsIContent, nsINode, etc. (internal; preferred)
• nsIDOM* (frozen)

Output (concepts)

• Calls to 2-D graphics API
  • translate, save, restore, fill rect, draw text, draw image, etc.
  • See vlad's talk
• Mapping from coordinates back to content nodes (e.g., for event handling)
• APIs for computed style and element positions

Parts of Layout

• Style data computation
• Frame construction
• Reflow
• Painting (and event handling)
• Glue to hold things together
• Other things on frame classes: selection, accessibility, etc.

Sources of style data

• nsIStyleSheet; nsIStyleRuleProcessor
• nsIStyleRule
• examples of implementations (CSS, mapped attributes)
• selector matching done up-front

Style context

• The internal API for computed style data
• style structs
• lazily computed data
• immutable
• shared among siblings

Rule tree

/* rule 1 */ doc { display: block; text-indent: 1em; }
/* rule 2 */ title { display: block; font-size: 3em; }
/* rule 3 */ para { display: block; }
/* rule 4 */ [class="emph"] { font-style: italic; }

Frames

• Bad name: CSS "box", "rendering object"
• nsIFrame interface
• internal
• XUL: nsIBox, nsIBoxLayout
• tree structure, using linked lists of children

Examples of frame classes

• nsBlockFrame
• nsInlineFrame
• nsTableRowFrame
• nsViewportFrame
• nsGfxScrollFrame
• nsBoxFrame, nsLeafBoxFrame
• nsSVGOuterSVGFrame
• many more

Frame construction

• nsCSSFrameConstructor.cpp
  • Also has some frame initialization code that could be refactored
• Based on element name or style data
• Recursive, but need not start at top
• Most often done in response to nsIDocumentObserver notifications
• frame→content pointers, content→frame hashtable

Continuations

• line breaking
• page breaking
• bidirectional text

Continuations

<p>text <span>with
line</span> breaks</p>

<Block>text <Inline(1)>with</Inline(1)>
<Inline(2)>line</Inline(2)> breaks</Block>

Continuations

(diagram from continuation model)

    Root                      Root
     |                       / |  \ 
     A                     A1  A2  A3
    / \                   / |  |    |
   B   C                 B  C1 C2   C3
   |  /|\                |  |  | \   |
   D E F G               D  E  F G1  G2

Generated content

(Differences between frame and content trees, #1.)

<p>World</p>

p:before { display: inline; content: url(icon.png) "Hello"; }

XBL

(Differences between frame and content trees, #2.)

• XBL interleaves "anonymous" content with content tree
• Frame tree matches the "flattened" (interleaved) content tree
• XTF similar

Floats and absolute positioning

(Differences between frame and content trees, #3.)

• floats and absolutely positioned elements (and some others) are "out of flow"
• placed at a different place in the frame tree than they are in the content tree
• a placeholder frame is placed where they would have been with a pointer
• The frame manager has a hashtable for the reverse (out of flow -> placeholder) mapping
• multiple child lists
• float ends up in additional child list of its containing block

Floats and absolute positioning

(Differences between frame and content trees, #3.)

<p>This is a document with <span>some
markup and a floating <img align="left"
src="icon.png"> image</span> in it.</p>

Extra frames

(Differences between frame and content trees, #4.)

• table
• table cell
• scroll frame
• viewport

Extra frames

(Differences between frame and content trees, #4.)

Reflow

• Computing coordinates (top, left, width, height) for frames
• top and left relative to parent
• Recursive, starting from top of tree or reflow roots
• frames that are also boxes use Layout instead
  • box→block glue in in nsFrame::DoLayout, GetPrefSize, etc.
  • block→box glue in nsBoxFrame::Reflow, nsLeafBoxFrame::Reflow
• usually off the main event loop

Intrinsic sizes

Intrinsic sizes

Intrinsic sizes

• non-boxes have GetMinWidth, GetPrefWidth
  • Separate methods for inline layout
• boxes have GetMinSize, GetPrefSize, GetMaxSize

Reflow

• nsHTMLReflowState is input
• nsHTMLReflowMetrics is output
• caller of Reflow responsible for setting the rect to the size in the reflow metrics
• Designed for traditional-style layout (widths input, heights output)

Breaking

• lines, columns, pages
• Breaking done by propagating break-before or break-after status out of reflow
• Caller responsible for creating next-in-flow and propagating status

Incremental layout

• bits: is dirty, has dirty children
• intrinsic widths can be marked as dirty too (and are, up & down)

Box Layout

• Parent sizes box first (based on intrinsic sizes, flex, etc.), then calls Layout
• much of the work done by an nsIBoxLayout object (sprocket, stack/deck)
• grid, tree more complicated

Painting

• Painting initiated from paint event in widget code
• View manager tells pres shell to paint root frame for each of the layers requiring compositing or other special handling

Painting (in Layout)

• BuildDisplayList method builds a display list for the frames in a clip rect or at a point
• we then paint the needed items in the list from bottom-most to top
• views mostly vestigial
• usually off the main event loop

Painting: BuildDisplayList

• Recursive, starting from root
  • will soon cross parent/child presentations, if it doesn't already
• Only adds items that are in the clip rect / at the event's point
• Single recursive call to build lists for a multi-pass algorithm
• Various display items added to display list, for painting things like
  • background
  • border
  • text
• Read CSS2.1 Appendix E for requirements

Invalidation

• Reflow invalidates regions that need to be repainted
• We don't have a good sense of what the rules are, and they'll hopefully change soon
• maximum containing rectangle or each rectangle separately?

Painting

• Display list optimized to avoid painting things underneath fully opaque things, etc.
• Paint bottom-to-top, using 2-D graphics API
• Usually from system paint events

Mouse event handling

• point ← frame mapping must use paint order
• so we use the same display list

Reasons to optimize dynamic changes

• Incremental page loading
• Small changes should take smaller amounts of time (DOM manipulation, editing)
• resizing

Dynamic changes: content changes

• document observer notifications trigger frame destruction/construction
• incremental reflow
• repaint invalidated region

Dynamic changes: attribute and event state changes

• document .getElementById("ok-button") .removeAttribute("disabled");
• Changes to :hover, :checked, :link (vs. :visited)
• Style system makes a somewhat (not very) conservative approximation for whether something might have changed
• Worth doing as much work as selector matching since it's not the whole subtree
• If a change, processed as a style change

Dynamic changes: style changes

• document .getElementById("foo") .style .color = "green";
• style changes caused by attribute or event state changes

• rerun rule matching on subtree
• recursively compare data in old and new style contexts
• hints (applying to subtree): frame reconstruction, reflow, repaint, etc.