Google Git
Sign in
chromium / chromium / src / b6b13c9cfe64d52a4168d9d8d1ad9bb8f0b46a2a / . / third_party / WebKit / Source / core / layout / ng
tree: 14e07861aeac186d47146a16ab8a5592fa16c2f3 [path history] [tgz]
  1. geometry/
  2. inline/
  3. layout_ng_block_flow.cc
  4. layout_ng_block_flow.h
  5. ng_absolute_utils.cc
  6. ng_absolute_utils.h
  7. ng_absolute_utils_test.cc
  8. ng_base_layout_algorithm_test.cc
  9. ng_base_layout_algorithm_test.h
  10. ng_block_break_token.cc
  11. ng_block_break_token.h
  12. ng_block_child_iterator.cc
  13. ng_block_child_iterator.h
  14. ng_block_child_iterator_test.cc
  15. ng_block_layout_algorithm.cc
  16. ng_block_layout_algorithm.h
  17. ng_block_layout_algorithm_test.cc
  18. ng_block_node.cc
  19. ng_block_node.h
  20. ng_block_node_test.cc
  21. ng_box_fragment.cc
  22. ng_box_fragment.h
  23. ng_break_token.h
  24. ng_column_layout_algorithm.cc
  25. ng_column_layout_algorithm.h
  26. ng_constraint_space.cc
  27. ng_constraint_space.h
  28. ng_constraint_space_builder.cc
  29. ng_constraint_space_builder.h
  30. ng_constraint_space_builder_test.cc
  31. ng_constraint_space_test.cc
  32. ng_exclusion.cc
  33. ng_exclusion.h
  34. ng_floats_utils.cc
  35. ng_floats_utils.h
  36. ng_fragment.cc
  37. ng_fragment.h
  38. ng_fragment_builder.cc
  39. ng_fragment_builder.h
  40. ng_layout_algorithm.h
  41. ng_layout_input_node.cc
  42. ng_layout_input_node.h
  43. ng_layout_opportunity_iterator.cc
  44. ng_layout_opportunity_iterator.h
  45. ng_layout_opportunity_tree_node.cc
  46. ng_layout_opportunity_tree_node.h
  47. ng_layout_result.cc
  48. ng_layout_result.h
  49. ng_length_utils.cc
  50. ng_length_utils.h
  51. ng_length_utils_test.cc
  52. ng_macros.h
  53. ng_min_max_content_size.cc
  54. ng_min_max_content_size.h
  55. ng_min_max_content_size_test.cc
  56. ng_out_of_flow_layout_part.cc
  57. ng_out_of_flow_layout_part.h
  58. ng_out_of_flow_layout_part_test.cc
  59. ng_physical_box_fragment.cc
  60. ng_physical_box_fragment.h
  61. ng_physical_fragment.cc
  62. ng_physical_fragment.h
  63. ng_positioned_float.h
  64. ng_relative_utils.cc
  65. ng_relative_utils.h
  66. ng_relative_utils_test.cc
  67. ng_space_utils.cc
  68. ng_space_utils.h
  69. ng_space_utils_test.cc
  70. ng_unpositioned_float.cc
  71. ng_unpositioned_float.h
  72. ng_writing_mode.cc
  73. ng_writing_mode.h
  74. OWNERS
  75. README.md
third_party/WebKit/Source/core/layout/ng/README.md

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

Inline layout is performed in the following phases:

  1. Pre-layout.
  2. Line breaking.
  3. Line box construction.

This is similar to CSS Text Processing Order of Operations, but not exactly the same, because the spec prioritizes the simple description than being accurate.

Pre-layout

For inline layout there is a pre-layout pass that prepares the internal data structures needed to perform line layout.

The pre-layout pass, triggered by calling NGInlineNode::PrepareLayout(), has three separate steps or stages that are executed in order:

  • CollectInlines: Performs a depth-first scan of the container collecting all non-atomic inlines and TextNodess. Atomic inlines are represented as a unicode object replacement character but are otherwise skipped. Each non-atomic inline and TextNodes is fed to a NGInlineItemsBuilder instance which collects the text content for all non-atomic inlines in the container.

    During this process white-space is collapsed and normalized according to CSS white-space processing rules.

    The CSS text-transform is already applied in LayoutObject tree. The plan is to implement in this phase when LayoutNG builds the tree from DOM.

  • SegmentText: Performs BiDi segmentation and resolution. See Bidirectional text below.

  • ShapeText: Shapes the resolved BiDi runs using HarfBuzz. TODO(eae): Fill out

Line Breaking

NGLineBreaker takes a list of NGInlineItem, measure them, break into lines, and produces a list of NGInlineItemResult for each line.

NGInlineItemResult keeps several information needed during the line box construction, such as inline size and ShapeResult, though the inline position is recomputed later because Bidirectional text may change it.

This phase:

  1. Measures each item.
  2. Breaks text NGInlineItem into multiple NGInlineItemResult. The core logic of this part is implemented in ShapingLineBreaker.
  3. Computes inline size of borders/margins/paddings. The block size of borders/margins/paddings are ignored for inline non-replaced elements, but the inline size affects layout, and hence line breaking. See CSS Calculating widths and margins for more details.
  4. Determines which item can fit in the line.
  5. Determines the break opportunities between items. If an item overflows, and there were no break opportunity before it, the item before must also overflow.

ShapingLineBreaker is... TODO(kojii): fill out.

Line Box Construction

NGInlineLayoutAlgorithm::CreateLine() takes a list of NGInlineItemResult and produces NGPhysicalLineBoxFragment for each line.

Lines are then wrapped in an anonymous NGPhysicalBoxFragment so that one NGInlineNode has one corresponding fragment.

This phase consists of following sub-phases:

  1. Bidirectional reordering: Reorder the list of NGInlineItemResult according to UAX#9 Reordering Resolved Levels. See Bidirectional text below.

    After this point forward, the list of NGInlineItemResult is in visual order; which is from line-left to line-right. The block direction is still logical, but the inline direction is physical.

  2. Create a NGPhysicalFragment for each NGInlineItemResult in visual (line-left to line-right) order, and place them into NGPhysicalLineBoxFragment.

    1. A text item produces a NGPhysicalTextFragment.
    2. An open-tag item pushes a new stack entry of NGInlineBoxState, and a close-tag item pops a stack entry. Performs operations that require the size of the inline box, or ancestor boxes. See Inline Box Tree below.

    The inline size of each item was already determined by NGLineBreaker, but the inline position is recomputed because BiDi reordering may have changed it.

    In block direction, NGPhysicalFragment is placed as if the baseline is at 0. This is adjusted later, possibly multiple times. See Inline Box Tree and the post-process below.

  3. Post-process the constructed line box. This includes:

    1. Process all pending operations in Inline Box Tree.
    2. Moves the baseline to the correct position based on the height of the line box.
    3. Applies the CSS text-align property.

Inline Box Tree

A flat list structure is suitable for many inline operations, but some operations require an inline box tree structure. A stack of NGInlineBoxState is constructed from a list of NGInlineItemResult to represent the box tree structure.

This stack:

  1. Caches common values for an inline box. For instance, the primary font metrics do not change within an inline box.
  2. Computes the height of an inline box. The height of inline, non-replaced elements depends on the content area, but CSS doesn't define how to compute the content area.
  3. Creates NGPhysicalBoxFragments when needed. CSS doesn't define when an inline box should have a box, but existing implementations are interoperable that there should be a box when it has borders. Also, background should have a box if it is not empty. Other cases are where paint or scroller will need a box.
  4. Applies vertical-align to shift baselines. Some values are applicable immediately. Some values need the size of the box, or the parent box. Some values need the size of the root inline box. Depends on the value, the operation is queued to the appropriate stack entry.

Because of index-based operations to the list of NGInlineItemResult, the list is append-only during the process. When all operations are done, OnEndPlaceItems() turns the list into the final fragment tree structure.

Bidirectional Text

UAX#9 Unicode Bidirectional Algorithm defines processing algorithm for bidirectional text.

The core logic is implemented in NGBidiParagraph, which is a thin wrapper for ICU BiDi.

In a bird's‐eye view, it consists of two parts:

  1. Before line breaking: Segmenting text and resolve embedding levels as defined in UAX#9 Resolving Embedding Levels.

    The core logic uses ICU BiDi ubidi_getLogicalRun() function.

    This is part of the Pre-layout phase above.

  2. After line breaking: Reorder text as defined in UAX#9 Reordering Resolved Levels.

    The core logic uses ICU BiDi ubidi_reorderVisual() function.

    This is part of the Line Box Construction phase above.

Fragment Tree

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

Constraint Spaces

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

Block Flow Algorithm

This section contains details specific to the NGBlockLayoutAlgorithm.

Collapsing Margins

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

Float Positioning

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

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 webkit_unit_tests
  • Run DynamoRIO with drcov tool chromium\src>DynamoRIO\bin64\drrun.exe -t drcov -- .\out\Debug\webkit_unit_tests.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 master lcov file chromium\src>C:\Perl64\bin\perl.exe dynamorio.git\third_party\lcov\genhtml output.info -o output