mozilla/servo — pull request #2235 by pcwalton (2014-04-26 08:30:56+00:00)
Title: Rewrite display list building and opportunistically lay out floats in parallel

layout: Rewrite display list building to be parallel and to handle
overflow correctly, and opportunistically lay out blocks in parallel
even if floats are present.

This series of commits fixes the `inline-height-test` in Acid2 by
implementing proper overflow as well as the inline "strut". (See CSS 2.1
§ 10.8.1.) It was accidentally working before because tables' descendant
flows were not being laid out properly.

Display list building is now parallel and is done by bubbling up display
items and layers from parent to child. Speedups of around 60%-70% are
observed on Wikipedia with a 4-core HyperThreaded Core i7. More
optimizations are possible; this is just a start.

To minimize the amount of data that needs to be bubbled up, as well as
to make proper handling of `overflow: hidden` clipping easier, the
`StackingContext` abstraction is now purely internal to the display
list. Instead of placing items into a stacking context directly, display
items are placed into display lists with an explicit `StackingLevel`
provided. The stacking level determines a display item's position within
the stacking context. When a stacking context is finished, it is
flattened with the the `flatten` method, which shuffles the display
items that make up the context into their proper order while handling
clipping properly.

r? @SimonSapin and/or @larsbergstrom