Next Generation Layout and Rendering

by Simon Fraser

• 2-3 years!
• Current layout and rendering:
  • Render tree exists, FrameView owns it
  • Hasn’t changed since KHTML
  • Layout is recursive across the render tree, then painting is recursive across the render tree, then hit testing is also recursive across the render tree
  • There is only one render tree! Used for many things
  • RenderLayers are used as entry points for painting and hit testing (and also handle things like opacity & clipping, scrolling, etc.)
  • Internally, the trees might have (effectively) different structures depending on their use. For example, the z-order tree is only used for some purpose
  • Bad things
    • Mutating the tree at a bad time causes lots of bugs
    • Current render tree is not read-only in any sense
    • The code for grid, flexbox, block, etc. all live in the same set of objects. This leads to dependency hell.
    • The render tree has inline trees as its leaves. The data in the inline tree is sometimes duplicated in the inline tree. This makes it difficult to think about
    • Repaint is difficult to reason about (because it involves mutability, but there are no immutability constraints)
    • No parallelism
    • Painting involves full paint phases that may do nothing, and involves running through the entire render tree (with some culling)
    • Current code often has structure of “if is block do block thing, else do inline thing”
• Goals of this project
  • We want more guarantees about what can change when. This probably involves sprinkling “const” in many places
  • Hackability - naming should match specs, and classes should be smaller and better scoped
  • Parallelism: With more strict mutability comes more likelihood of asynch work
    • Painting may be asynchronous (e.g. with display lists)
• One tree is used for layout, layerization, and painting!
• Instead, we want:
  • “Layout” tree, created the tree builder
  • Layout creates a “box tree” where all nodes are boxes. There is no distinction between block boxes and inline boxes
  • We probably still need a layerization step that works the same as it does today
    • Or not, maybe layerization would produce a “presentation tree”
  • Then, we will produce a display list thing which is used for painting
• Tree building! (Step 1)
  • RenderTreeBuilder currently does it.
    • This should do any mutation that currently occurs during (later) layout. We’ve been working on this
    • RenderTreeBuilder will also do things like anonymous box generation
    • The logic for this will move out of the data objects and into controller objects (like RenderTreeBuilder)
  • Layout! (Step 2)
    • Produces box tree, which includes geometry
    • Inline tree would be invisible, because the logic would move into iterators.
    • “Formatting contexts” will be the controllers for sub pieces of this.
      • e.g. BlockFormattingContext, InlineFormattingContext, GridFormattingContext etc.
      • These match what the spec language describes
      • Interruptible, resumable
        • These handle layout, so they don’t have to operate recursively. They can use whichever they use
          • Nested formatting contexts still need to be recursive
        • Each one can be processed in parallel
    • Box tree: Output form Layout
      • Mostly geometry. Doesn’t care about formatting contexts.
      • Used for painting and hit testing
      • Immutable
    • Immutability is great because you can do “throwaway” layouts (not real layouts) for things like JS sync layouts
      • This lets you do animations where the destination is “auto”. Your throwaway layout computes the value of “auto”
      • Or do it off the main thread
        • And paint while layout
  • Doing these phases asynchronously decreases latency (and uses more cores)
  • Presentation Tree (Step 3)
    • These are like RenderLayers that reference into the box tree
    • This will implement opacity, transforms, filters, and stacking contexts / z-order tree
    • Clipping will be easier to implement because you will have a new tree just for it!
    • Don’t have to traverse the render tree for each painting phase
    • All this crap is currently implemented by RenderLayer. So we want to get rid of a lot of the functionality of RenderLayer and move it elsewhere
      • Remove a bunch of things: scrolling, Marquee, fragmentation, compositing?
  • Painting (Step 4)
    • Currently, we paint in this order:
      • Layers -> Box tree -> GraphicsContext -> Platform drawing API
    • But, if we had display lists, we do this:
      • Layers -> Box tree -> GraphicsContext -> Display List
        • Then, later, Display List -> GraphicsContext -> platform drawing API
    • We could do the same thing, but we get rid of GraphicsContext!
      • Layers -> Box tree -> Display List
        • Then, later, Display List -> Graphics Context -> platform drawing API
        • OR! Display List -> platform drawing API
  • Display Lists (Step 5)
    • Just a list of serialized drawing commands
    • Retained between paints! So you don’t have to rebuild it every frame
    • The combination of retained-mode display lists, and extent information, lets you optimize repainting by culling a bunch of crap that was painted last time
    • Display lists can be cached!
    • You can optimize the list! Eliminate redundant state changes, etc.
    • Downsides
      • They take memory, but probably less memory than compositing layer bitmaps
      • There is an extra phase for display lists: recording & repainting, so latency is increased
      • Recording and replaying can’t happen in parallel
• So how do we do this?
  • Incrementally!
    • Remove mutability from the render tree during layout
    • Hide the difference between simple line layout and real layout behind iterators
    • We can make formatting context objects and move code into them (this is just code moving)
    • Display lists (because we have an implementation)
    • Breaking up RenderLayer into its constituent pieces
  • Non-incrementally
    • Generational layout and box trees. So we have multiple render trees in memory at once (which is okay)
    • Using a box tree
    • Flip how repaint works to using display lists
      • Repaint just updates a few bytes in the display list and then plays the display list again