LayoutNG

This directory contains the implementation of Blink's new layout engine “LayoutNG”.

This README can be viewed in formatted form here.

The original design document can be seen here.

High level overview

CSS has many different types of layout modes, controlled by the display property. (In addition to this specific HTML elements have custom layout modes as well). For each different type of layout, we have a NGLayoutAlgorithm.

The input to an NGLayoutAlgorithm is the same tuple for every kind of layout:

  • The NGBlockNode which we are currently performing layout for. The following information is accessed:

    • The ComputedStyle for the node which we are currently performing laying for.

    • The list of children NGBlockNodees to perform layout upon, and their respective style objects.

  • The NGConstraintSpace which represents the “space” in which the current layout should produce a NGPhysicalFragment.

  • TODO(layout-dev): BreakTokens should go here once implemented.

The current layout should not access any information outside this set, this will break invariants in the system. (As a concrete example we intend to cache NGPhysicalFragments based on this set, accessing additional information outside this set will break caching behaviour).

Box Tree

TODO(layout-dev): Document with lots of pretty pictures.

Inline Layout

Please refer to the inline layout README.

Fragment Tree

TODO(layout-dev): Document with lots of pretty pictures.

All coordinates and sizes associated with an NGPhysicalFragment are physical, i.e. pure left/top offsets from the parent fragment, and sizes are expressed with widths and heights (not inline-size / block-size). No logical offsets or sizes. Writing mode and direction are resolved during layout.

Constraint Spaces

TODO(layout-dev): Document with lots of pretty pictures.

Block Flow Algorithm

Please refer to the block flow layout docs.

Collapsing Margins

TODO(layout-dev): Document with lots of pretty pictures.

Float Positioning

TODO(layout-dev): Document with lots of pretty pictures.

Fragment Caching

After layout, we cache the resulting fragment to avoid redoing all of layout the next time. You can read the full design document.

Here's how it works:

  • We store the input constraint space and the resulting fragment on the LayoutNGBlockFlow. However, we only do that if we have no break token to simplify the initial implementation. We call LayoutNGBlockFlow::SetCachedLayoutResult from NGBlockNode::Layout.
  • Once cached, NGBlockNode::Layout checks at the beginning if we already have a cached result by calling LayoutNGBlockFlow::CachedLayoutResult. If that returns a layout result, we return it and are done.
  • CachedLayoutResult will always clone the fragment (but without the offset) so that the parent algorithm can position this fragment.
  • We only reuse a layout result if the constraint space is identical (using operator==), if there was no break token (a current limitation, we may lift this eventually), and if the node is not marked for layout. We need the NeedsLayout() check because we currently have no other way to ensure that relayout happens when style or children change. Eventually we need to rethink this part as we transition away from legacy layout.

Block fragmentation

Design doc here.

Tutorial here.

Code coverage

The latest code coverage (from Feb 14 2017) can be found here. Here is the instruction how to generate a new result.

Environment setup

  1. Set up Chromium development environment for Windows
  2. Download DynamoRIO from www.dynamorio.org
  3. Extract downloaded DynamoRIO package into your chromium/src folder.
  4. Get dynamorio.git and extract it into your chromium/src folder git clone https://github.com/DynamoRIO/dynamorio.git
  5. Install Node js from https://nodejs.org/en/download/
  6. Install lcov-merger dependencies: npm install vinyl, npm install vinyl-fs
  7. Install Perl from https://www.perl.org/get.html#win32
  8. Get lcov-result-merger and extract into your chromium/src folder git clone https://github.com/mweibel/lcov-result-merger

Generating code coverage

  • Build the unit tets target with debug information chromium\src> ninja -C out\Debug blink_unittests
  • Run DynamoRIO with drcov tool chromium\src>DynamoRIO\bin64\drrun.exe -t drcov -- .\out\Debug\blink_unittests.exe --gtest_filter=NG*
  • Convert the output information to lcov format chromium\src>for %file in (*.log) do DynamoRIO\tools\bin64\drcov2lcov.exe -input %file -output %file.info -src_filter layout/ng -src_skip_filter _test
  • Merge all lcov files into one file chromium\src>node lcov-result-merger\bin\lcov-result-merger.js *.info output.info
  • Generate the coverage html from the lcov file chromium\src>C:\Perl64\bin\perl.exe dynamorio.git\third_party\lcov\genhtml output.info -o output

Debugging, logging and testing

Both layout input node subtrees and layout output physical fragment subtrees may be dumped, for debugging, logging and testing purposes.

For layout input node subtree

Call NGLayoutInputNode::ShowNodeTree() to dump the tree to stderr.

For physical fragment subtree

Call NGPhysicalFragment::ShowFragmentTree() to dump the tree to stderr. Fragments in the subtree are not required to be marked as placed (i.e. know their offset).

A fragment tree may also be dumped to a String, by calling NGPhysicalFragment::DumpFragmentTree(). It takes a flag parameter, so that the output can be customized to only contain what's relevant for a given purpose.