LayoutNG / LFC

Some interesting links

• LayoutNG original design document. Beware of it being somewhat outdated to some extent.

• layout/ng/README.md. Slightly more up-to-date, but lots of TODOs.

• layout/ng/inline/README.md. Inline layout description, pretty up-to-date.

• LFC original notes. Was called LayoutReloaded at the time.

• LFC source

Current status

LayoutNG

• Has block and inline layout working, as far as I can tell.
  • That includes floats, margin collapsing, line breaking, and all the other hard stuff.
• You can dogfood it via chrome://flags on canary, if you happen to have an OS which has Canaries (not my case).
• Falls back to legacy layout for unsupported stuff, can switch back and forth at BFC boundaries.
• Still some slightly hard bugs bugs need fixing for them to ship the first part, but pretty close.
• Prototypes of flex and multicol not fully working yet AFAIK.
• Block fragmentation that looks working with the rest of the stuff.
  • Though they still fall back to legacy for printing, at least for what they plan to ship.

LFC

• Pretty much at the prototyping stage.
• Now you can enable it at runtime on WebKit with a runtime flag.
• LFC-passing-tests.txt has a list of tests that are known-passing.

Bits in common

Layout tree split

A bit in common between both is that they split what currently is the layout / render / frame tree:

LayoutNG

• LayoutObject tree: "legacy" layout tree. LayoutNG creates its own legacy layout objects that allows to hook into LayoutNG (LayoutNGBlockFlow).
• NGInputNode tree: Not a fully separate tree, but a very thin wrapper over some nodes of the LayoutObject tree. Acts as a proxy to avoid contaminating new code with access to the whole legacy layout tree structure.
• Fragment tree: Output of layout (more on it below).

LayoutNG seems to heavily rely on legacy layout objects for a variety of stuff. I'm not sure if there's a plan to eventually nix the LayoutObject tree entirely as of right now, though they do try to minimize dependencies on it.

LFC

• Render tree: Good ole RenderObject tree. LFC doesn't touch anything from it, it just builds its own layout tree off it.
• Layout tree: The tree LFC primarily operates on. Built entirely at once from the render tree.
  • LayoutTreeBuilder.cpp
  • Still no incremental integration integration / plans as far as I can tell.
  • From what Simon Fraser told me the render tree will go completely away in the future, and they'll just use the layout tree.
• Display tree: A very simple box tree.
  • Not sure how it interacts with inline layout / how is inline layout represented.

Unknowns:

• I don't know whether they plan to fragment the layout tree or the display tree. The main API for the display tree is LayoutState::displayBoxForLayoutBox, which maps layout tree to fragment tree one-to-one.

• I don't know the incremental setup they have, they do have some stub invalidation code, but as far as I can tell it's not yet called, and invalidates everything all the time looks like:

  • BlockInvalidation.cpp
  • InlineInvalidation.cpp

Motivations

• Current layout implementations are really hard to reason about / improve.
• Mostly a maintainability effort, not a performance effort.
  • Though LayoutNG has seen huge inline layout performance wins too, from what I heard from Kojii.
• Custom layout API? This one maybe not so much in common, but surely a LayoutNG motivation.

Block layout in LayoutNG: Key data-structures.

NGLayoutInputNode

• As of right now, either NGInlineNode (for blocks that contain only inlines) or NGBlockNode (for other blocks).

Fragment Tree

• Fragments are the result of layout.

• Kinds of fragments:

  • Boxes
    • Normal
    • Inline
    • Column
    • Atomic inline
    • Floating
    • Out of flow positioned (abspos / fixed pos)
    • BlockFlowRoot (?)
  • Text
  • Line boxes
  • Rendered legend

• Fragments don't contain their positioning information.

  • Positioning relative to parent fragment is stored as part of NGLink.
  • This allows caching and reusing fragments regardless of position.

• Members:

  • LayoutObject* const layout_object_;: Legacy layout object that owns this fragment. Pretty sporadic use, and somewhat fishy since fragments are refcounted but LayoutObjects aren't. But according to cbiesinger@ it works :).

  • const NGPhysicalSize size_;

  • scoped_refptr<NGBreakToken> break_token_;.

  • Type, subtype, other type-specific flags so they get packed.

  • Container fragments have a Vec<NGLink> effectively.

NGLayoutAlgorithm

• On the stack, base class that performs the layout computation.

• Inputs:

  • NGInputNode: The layout tree node (NGInlineNode / NGBlockNode) you're laying out (which has a style as well).
  • NGConstraintSpace: All the information that represents the input to the current layout.
  • NGBreakToken: Inout parameter to handle fragmentation.

• Output: NGLayoutResult.

A bit of complexity around this to handle margin collapsing (bfc block offset and such).

NGConstraintSpace

• Input to layout.

• Main member is available size, but a bunch of other stuff related to float positioning, fragmentation, etc.

NGLayoutResult

• Returns a physical, positioned fragment subtree.

• NGLink root_fragment_;

• Other information: breaking, positioned OOFs / floats / etc.

NGExclusionSpace

• Represents the float positioning information inside a BFC.

• Shelves algorithm exploiting floats' properties to take some shorcuts.

• Coordinates of the shelves and of the floats are relative to the BFC block offset.

Floats and margin collapsing.

• Margin collapsing can move the BFC, and thus change the floats position.

• Some of the most complex bits are handling this interaction.

• They do margin collapsing without re-laying out in most cases.

  • When you reach a new BFC you need to do potentially 2 layouts to determine what is positioned.

• Floats are not positioned until their BFC block offset is known, which depends on margin collapsing.

  • Floats and NGExclusionSpace are always positioned relative to their block formatting context (NGBfcRect, NGBfcOffset are the relevant types here).

Test case

<!DOCTYPE html>
<div style="width: 100px;">
  <!-- This margin collapses with the one after it if the float doesn't push the div below down -->
  <div style="margin-top: 90px">
    <span style="float: left; width: 50px; height: 50px; background-color: hotpink;"></span>
  </div>
  <div style="display: flow-root; overflow: hidden; width: 60px; border: 3px solid green; margin-top: 90px"></div>
</div>

NGMarginStrut

• Struct that keeps the margin collapsing state.

• Conceptually, a pair of biggest_positive_margin and smallest_negative_margin.

Inline layout in LayoutNG

(Disclaimer: less knowledgeable about this bits)

• Three phases to do inline layout:

  • Pre-layout: Goes from LayoutObject tree to a concatenated string of all the text, and a Vector of NGInlineItems.

  • Line breaking.

  • Line box construction, which constructs a fragment tree.

• README.md

Incremental

• Still rely on the legacy LayoutObject tree mark stuff dirty.

• If you have an LayoutNG object you keep around the last layout result and constraint space.

  • Fragment caching: Reuse the last fragment if the constraint space matches.

    • They don't cache intermediate layouts yet, but they want to.

• Intrinsic sizes are still cached on the legacy layout object.

• Fragments are refcounted, keep references to non-refcounted LayoutObjects. Though in practice the references to the fragment are always dropped before the LayoutObject.