-
-
Notifications
You must be signed in to change notification settings - Fork 2.9k
Layout Overview
🚩 Note: This is a historical document. Information here might not reflect the current status of the Servo project. For a more recent document about Servo Layout see the following page: Servo Layout Engines Report.
This is a high-level overview of Servo’s style and layout algorithm. This should be up to date as of Summer of 2016. It is targeted at people who are interested in contributing to these parts of Servo, and are already somewhat familiar with the CSS specifications. It includes some comparisons to other implementations, like Gecko, which may be useful if you have experience with those implementations.
Styling and layout are the steps that transform a DOM tree (the in-memory representation of a parsed HTML document) into a display list (a sequence of graphics commands that can be used to render the page to the screen or other output device), using the rules specified in the various CSS standards.
The styling and layout process starts with the DOM tree, and produces an intermediate representation called the flow tree (which we will describe later). Each step of the process walks through the DOM tree or the flow tree, processing each node as it goes.
Some steps operate top-down (or pre-order), starting at the root of the tree and processing each node before its children. The others operate bottom-up (or post-order), starting at the leaves of the tree and processing each node after all its children. One full traversal of the tree can perform a pre-order step (on its way “down” the tree) and then a post-order step (on its way back “up”).
A tree traversal can be parallelized: To process a node, run the pre-order step on it, then spawn tasks to recursively process each of its children. Then run the post-order step on the node after all its child tasks have finished.
Servo uses rayon
to execute tasks in parallel.
The code that uses this queue is in the style::parallel and layout::parallel modules.
(There are also sequential alternatives to these parallel modules,
which may be useful for testing and comparison,
or for cases where the overhead of a parallel traversal is not justified.)
Servo’s styling and layout algorithm is divided into the following traversals, which will be described in detail below:
- Top-down: Style calculation
- Bottom-up: Flow construction + Bubble inline size
- Top-down: Assign inline size
- Bottom-up: Assign block size
- Top-down: Display list construction
One neat property of Servo’s work queue is that while one thread is still working its way down some sub-tree running the pre-order step, another thread may have reached the bottom of another sub-tree and started working its way back up running the post-order step. So, for example, flow construction of one part of the document may happen in parallel with style calculation on another part.
Style calculation takes a DOM tree and its associated CSS styles, and determines the computed values for each node in the tree. CSS is (intentionally) specified such that this can be done in a single top-down traversal of the DOM tree.
In contrast, computing the used values requires the full set of layout passes. This is a key difference between what we call “styling” and what we call “layout”: Computed values only require the style system; used values need the layout system. (The poorly-named DOM Window.getComputedStyle() method sometimes returns used values and sometimes computed values, but that is unrelated to the terminology used here.)
Servo’s style system is implemented by the style crate and its dependencies.
The cssparser crate parses CSS style sheets into rules, selectors, declarations, values, etc.
You should only need to edit this crate if you are adding support for a new piece of CSS syntax or if there is some CSS-specific interpetation of data to perform here. For example, this crate is where color values specified in hex are clamped to the correct value range. It has an extensive set of macros to handle parsing, fallback, etc.
The style::properties module contains types and functions for specific CSS properties. This is where to start if you want to add a new property.
There is a lot of generated code here, because we want to do things like loop over all properties at compile time. Rust macros aren’t powerful enough, and Rust compiler plugins weren’t available when this code was written. So instead there is a Python script that uses Mako templates to generate Rust code. (Using code generation also works better with stable Rust, compared to compiler plugins.)
Properties are grouped into style structs, as in Gecko, to enable partial sharing of values between nodes.
The properties module has two submodules: longhands and shorthands.
(“Longhand” just means any property that is not a shorthand property.)
Inside longhands there is one file per style struct,
containing a block for each property in that struct.
Each property’s block expands to one Rust module.
This module exports a Rust type called SpecifiedValue
and another called computed_value::T.
(If multiple properties share the same set of values,
they might just export aliases to some shared type.)
These types implement the ToCss trait which defines how they are serialized,
and the ToComputedValue trait
that defines how to resolve specified values to computed values during the cascade.
Each property module also has a get_initial_value function,
which defines how to initialize the style struct.
There are Mako helper functions to auto-generate the types and impls for simple cases.
For example, for a property whose only values are single keywords,
helper.single_keyword will generate the entire module using from just one line of code.
These are defined in helpers.mako.rs.
Each property module also exports a parse function.
This function gets passed a cssparser::Parser
that represents the next input to be parsed.
There is a Parser::next method that returns the next Token
(or Err if it is at the end of the input).
The cssparser crate takes care of things like escaping and nesting.
cssparser is centered around Rust’s standard Result<T, E> type,
which is either Ok(T) or Err(E).
Typically, you will write functions or closures that return Result,
and pass them to the parser’s try method.
If the function returns an Err, then input.try(...) will fail
and reset the parser to its state before the call.
try can restore the position even if many items were parsed before the failure.
To add a new property, add a new block of code to the appropriate Mako file
and write parsing code based on the corresponding spec.
For example, the background-image property supports values of type <bg-image>
which is either none or an <image>.
So background_image::parse calls try, giving it a closure that tries to parse "none".
If that fails, then the parser is reset and it tries to parse an <image> instead.
The background-image parse function uses expect_ident_matching.
You can always just call next and check the value using a match expression,
but the expect_* helper methods are useful for checking common cases.
The Token enum includes blocks, e.g., ParenthesisBlock.
These “Block” tokens are nullary (contain no fields).
If you get one, you can then call a special method, parse_nested_block,
to parse the body of the block.
For example if Image::parse finds linear-gradient followed by a function body,
it calls parse_nested_block with another function to parse the body.
parse_nested_block will verify that you parse the entire block, and that it
is closed and nested correctly, throwing an error otherwise.
The cssparser crate does similar verification for things that are not nested
blocks, e.g., that normal property declarations do not have extra gunk at the end.
This is done by the function parse_entirely,
which is called by the code that parses blocks of property declarations.
The same Mako templates are used by both Servo and Gecko (via the Stylo project).
The global product variable is set at compile time to either "servo" or "gecko",
depending on the build target.
By default, a property block is used for both Servo and Gecko builds.
You can pass products="servo" or products="gecko" to the helpers:longhand tag to define a property for just one engine.
There are properties that are used by both Servo and Gecko, but with different sets of values.
That is where in the definition there is python code that does if product == "gecko".
There are also arguments like gecko_ffi_name, which are needed when the gecko style structs have a different field name than the Servo ones.
The geckolib crate contains the code for the Stylo library.
This crate has some Mako templates of its own.
These import the Mako and Python modules from the style crate
and generate additional Stylo-specific FFI code.
Selector matching is implemented in the selectors crate. This crate uses the output of the CSS parser library (the component values and declarations) to perform matching. It includes optimizations like a Bloom filter for descendant selectors (as seen in other engines like Gecko and WebKit).
Servo’s style::matching module uses this library to take a DOM element and a list of parsed style sheets, and compute the element’s applicable declarations (a list of all the property declarations from all the CSS rules that match that element).
After selector matching we call cascade.
This function takes the applicable declarations for the current node and the computed values for its parent, and generates the computed values for the current node. It also has access to a Context that contains global information like the viewport size.
If the computed value of property B depends on the computed value of property A,
then we need to make sure that A is computed first.
So we divide properties into two phases, early and other.
The “early” properties are the ones you need first because other ones may depend on them.
For example, font-size is early because it must be computed before em values are resolved.
For each element, we first loop through all the early properties, then all the other properties.
(In Gecko, there is a thing that resolves the dependencies at compile-time and generates code that handles these dependencies. Servo’s design is more similar to WebKit’s.)
Each CSS property has two associated Rust types: one for the specified value (after parsing) and one for the computed value (after the cascade for a given element). Initial values (the "defaults") are represented with computed value types to make inheritance consistent. But in some cases the computed value calculation can affect initial values. For example, the initial value of border-left-width is medium (which computes to 3px) but its computed value is set to zero if border-left-style is none (the initial value) or hidden. To deal with cases like this, we have a fixup step at the end of the cascade() function.
The IS_DIRTY flag is set on any DOM node that needs its style to be (re-)calculated, and HAS_DIRTY_DESCENDANTS is set on all of its ancestors. Style recalc can check these flags, and skip any nodes that are not dirty, or whole subtrees with no dirty descendants. These flags can be set explicitly by the script thread calling the Node::dirty method, or by the restyle hint system.
Restyle hints are an optimization to avoid unnecessary style calculation. When certain types of element state change, like the “mouse hover” flag, instead of dirtying the node immediately, the script thread takes “before” and “after” snapshots of the state and adds them to a list of “modified elements.” (If the same element is modified again before layout runs, the new modification will be coalesced with the previous one.) When layout runs, it examines each modified element, and computes a "hint" based on what state changed and what selectors the node matches, then uses that hint to decide which nodes to dirty (if any).
The layout::construct module performs a bottom-up parallel traversal of the styled DOM tree, and produces a flow tree. The flow tree includes flows and fragments.
(Servo’s flow tree plays a similar role to Gecko’s frame tree or WebKit’s render tree.)
This traversal happens on the way “back up” from the style calculation traversal.
Fragments are the leaves of the flow tree. A fragment roughly corresponds to a CSS “box” or “fragment,” and has a single rectangular boundary. A single DOM node may be split into multiple fragments, for example if a text node is broken across two or more lines. (Multiple nodes may also be merged into a one fragment; see Text Scanning, below.)
A fragment knows how to draw (i.e., generate a display list for) its content. There are several fragment types, including text, image, canvas, and “generic” fragments (which correspond to elements like <div> that just draw backgrounds and borders).
Flows come in two major-types: block-like flows and inline flows. A flow roughly corresponds to a CSS “formatting context.”
Elements with display: block generate block-like flows. Tables, table rows, table cells, flex-box, and inline-box elements also generate block-like flows. A block-like flow has a single fragment that draws its borders and background, and zero or more child flows.
An inline flow does not contain any child flows. Instead it contains a list of fragments. The later layout traversals will arrange these fragments into lines, breaking and merging them as necessary. (This is different from Gecko, which keeps inline content in the frame tree and uses continuations to split frames across lines.)
Because the fragments are a flat list rather than a tree, we need an alternate way to handle layout of nested elements. Each inline fragment has an array of pointers to any inline DOM element(s) it is nested in, so that it can draw the borders and padding for each of those elements. These pointers are stored in the Fragment::inline_context field.
(TODO: Discuss ConstructionResults, {ib}-splits?)
An element with position: absolute and position: fixed has the is_absolute_position flag set, and a pointer to its containing block. Since accessing the containing block during parallel layout could cause race conditions, there is a special wrapper type that limits the properties you can access. They sit in the tree at their static position.
It becomes a real mess when you get to absolutely positioned inline flows. Because, the hypothetical box is inline even though the display is absolute. In that case, we have a special “inline hypothetical block” type to gather the information during layout.
When blocks iterate over their children, they basically ignore absolute-/fixed-position children. There are likely still some bugs around InlineAbsoluteHypothethical.
During flow construction, each text node initially generates an unscanned text fragment. This fragment just contains the raw text content of the node. When a sequence of unscanned text fragments are ready to be added to an inline flow, they are first converted into scanned text fragments by TextRunScanner.
The text scanner takes a sequence of unscanned text fragments and generates a sequence of text runs. A text run is a contiguous string of characters that will all be rendered with the same shaping options (font, script, direction, color...). Several fragments might be combined into one text run if their styles are the same, or a single fragment might be split into multiple text runs if it has substrings with different Unicode scripts or directions.
Each text run then generates one or more scanned text fragments. The scanned fragments replace the unscanned fragments in the parent flow. Later, changes to line breaking or text selection might cause these scanned fragments to be split further, or merged with adjacent fragments. Each scanned text fragment has a reference-counted pointer to its text run, and a range of byte offsets within that text run.
TextRunScanner also does a bunch of other work, including: find and record line breaking opportunities, collapse whitespace, and apply text-transform styles, and shape the text (use HarfBuzz to map characters to glyphs).
After flows and fragments are constructed, the layout crate performs the following traversals of the flow tree.
(Terminology note: The inline direction is the direction that words flow within a line of text, while the block direction is the direction in which paragraphs are laid out on the page. For horizontal scripts like Latin, the inline direction is horizontal and the block direction is vertical. For vertical scripts it is the opposite. See the CSS Writing Modes spec for details.)
This computes the minimum and preferred intrinsic inline size (width, for horizonal scripts) of each element, as used in CSS 2.1 by floats, tables, and inline-block elements. This is a parallel, bottom-up traversal, and we do some other things here as well such as set up flags for use when positioning floats in later traversals.
WebKit computes intrinsic widths on-demand during reflow. This is different — we compute it up-front. That’s because when we actually need it we may have some other flow that needs it. So we can’t be racing on computing those sizes against parallelism. That does mean we may do more work computing those sizes, but due to parallelism and the short time for this pass is not an issue. If we needed a certain size early we could always have a goal and get it first.
This traversal is combined with the flow construction traversal, to avoid traversing the DOM a second time.
This parallel traversal is responsible for determining the used inline size (width) of every element in the flow tree. Since the inline size of a flow generally depends on its parent’s width, this operation is top-down.
Finally, block-size (height) is back up the tree, since a flow’s height generally depends on its children’s heights.
This is where line breaking occurs. It accounts for the majority of layout time (though style calculation still dominates layout in general).
We also handle floats here. If you have paragraphs and their text wraps around floats, then paragraphs that come later cannot be laid out until all earlier paragraphs are finished. You don’t know whether a float will stick out into a subsequent paragraph, which would reduce the space for that paragraph. To handle that, we sequentialize parts of the tree. During bubble_inline_sizes, we mark flows whose text might wrap around floats. For those flows, you can’t do block-size for those in parallel. So we defer block size until we get to the parent node, which then lays out these children sequentially.
The thing that saves us is that most floats are cleared, as we can reset at that point and still get parallelism on any content after the clearing element. Also, many pages that use floats put the complicated stuff inside the floats. The content inside the float can still be done in parallel. The limitation is only that stuff around floats cannot be laid out in parallel. We also have special things for when floats flow into a margin that re-enables parallelism. Most Servo layout bugs are in this area: interactions between block sizes, line breaking, floats, and margin collapsing.
After layout is completed, we use a sequential top-down traversal to compute the final position (or “stacking-relative position”) for everything, and produce the display lists. These are low-level lists of the CSS items. It constructs a tree of stacking contexts. The traversal is sequential because it’s so fast there’s no reason to paralellize it.
Servo currently builds a display list for the whole page, but we’re looking into reducing that to the “display port.” The display port is 16 times the size of the viewport and outside of that we wouldn’t construct items. Basically, it helps for pages like the HTML spec. It’s larger than the viewport so that you don’t have to go back to layout immediately when you scroll. Display list construction is one file, taking styles and turning them into items. There are only about 6 display items.
We handle stacking contexts by just putting everything into the display lists as we encounter them. We then fix up the display list per the CSS spec.
Flows and fragments have “damage” flags.
The layout passes skip nodes that don’t have the corresponding damage bit set.
For each CSS property, we have a map of what kinds of damage it causes if its value changes.
For example, if color changes, we only need to re-run display list construction.
You can see this in restyle_damage.rs.
Right now Servo only looks at which properties changed, not at their values (or the values of other properties). It could be easily be made smarter. (For example, changes to border-width don’t matter if border-style is none.)
The flow constructor will skip all nodes under an ancestor with display: none. We have an internal CSS property -servo-under-display-none that is used to implement this.
This could be changed to short-circuit even sooner, during style calculation. We could probably do it at the traversal level, but then we'd have to add lazy style calculation for the case where script queries the style.