Created
December 5, 2018 15:24
-
-
Save emilio/cfb3e778955f17fca614cc3a45dafff3 to your computer and use it in GitHub Desktop.
Revisions
-
emilio created this gist
Dec 5, 2018 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,255 @@ # LayoutNG / LFC ## Some interesting links * [LayoutNG original design document](https://docs.google.com/document/d/1uxbDh4uONFQOiGuiumlJBLGgO4KDWB8ZEkp7Rd47fw4/preview#heading=h.guvbepjyp0oj). Beware of it being somewhat outdated to some extent. * [`layout/ng/README.md`](https://chromium.googlesource.com/chromium/src/+/master/third_party/blink/renderer/core/layout/ng/README.md). Slightly more up-to-date, but lots of TODOs. * [`layout/ng/inline/README.md`](https://chromium.googlesource.com/chromium/src/+/master/third_party/blink/renderer/core/layout/ng/inline/README.md). Inline layout description, pretty up-to-date. * [LFC original notes](http://webkit.crisal.io/webkit/source/Tools/LayoutReloaded/README.md). Was called `LayoutReloaded` at the time. * [LFC source](http://webkit.crisal.io/webkit/source/Source/WebCore/layout) ## 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](http://webkit.crisal.io/webkit/source/Tools/LayoutReloaded/misc/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](http://webkit.crisal.io/webkit/source/Source/WebCore/layout/layouttree/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](http://webkit.crisal.io/webkit/source/Source/WebCore/layout/blockformatting/BlockInvalidation.cpp) * [InlineInvalidation.cpp](http://webkit.crisal.io/webkit/source/Source/WebCore/layout/inlineformatting/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 ```html <!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 `NGInlineItem`s. * Line breaking. * Line box construction, which constructs a fragment tree. * [README.md](https://chromium.googlesource.com/chromium/src/+/master/third_party/blink/renderer/core/layout/ng/inline/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.