Implement `z-index`

[pcwalton]

Needed for the Acid2 introduction message.

[larsbergstrom]

Needed for #1366.

[metajack]

mentor @metajack

[SimonSapin]

More than just the z-index property, this is about implementing the painting order described in CSS 2.1 Appendix E

[larsbergstrom]

#1538 will be required once we implement stacking context identification from the CSS appendix listed above.

[pradeep90]

Proposal for z-index / stacking contexts implementation:

• Stacking Context = List of normal display items + List of child stacking contexts
• The aim is to sort all items in a Stacking Context by (z-index, layer index, tree order)
• Display items in a Stacking context will be painted together atomically (other display items cannot come in between)
• Display items are annotated with their layer number (Root layer, in-flow block layer, float layer, etc.) - this is defined in http://www.w3.org/TR/CSS21/zindex.html
• Stacking contexts are annotated with their z-index
• Elements with specified z-index will create a new Stacking Context
• Floats and elements with z-index: auto will create a "pseudo" Stacking Context - they encapsulate their display items and paint them together atomically, but they pass any nested Stacking Contexts to their actual parent. This can be done simply by passing in the parent's nested_stacking_context list in the traversal.

The interface we expect from a DisplayList currently:

• iter() - an iteration over all the display items in reverse order (item painted farthest from the user first) - this is used in all kinds of ways in layout_task - hit testing, mouse over query, context box finding, etc. Right now, this does not recurse into display items like ClipDisplayItem. We have to do that manually. I plan to change this.
• draw_lists_into_context - Draw all items into the context. This needs to clip items that come under ClipDisplayItem, if necessary.

Algorithm:

• For now, we will do this using a sequential post-order traversal
• Inside a Stacking Context, we collect kids' display items in tree order. The display items are annotated with their layer number as per their element type.
• We collect direct Stacking Context descendants in a separate list.
• For pseudo Stacking Contexts, we bubble nested Stacking Context descendants to our parents.
• At the root of a Stacking Context, we sort the nested Stacking Context list by z-index. (This can also be 3 different lists - positive_z_index, zero_z_index, negative_z_index. That is what Weasyprint seems to do)
• Implementation of iter() - we need to get display items in ascending order of (z-index, layer index, tree order). One way is to sort all the normal display items too at the root of each Stacking Context. Then, for iteration, do a pre-order traversal of the Stacking Context tree. The problem with this is that we would have to propagate the Clipping information to all display items that are being clipped (because display items would now not be nested under their ClipDisplayItem)
• Another way is to traverse the normal display items list 4 times - once each for
  • background and borders
  • in-flow block-level
  • float
  • inline elements
• This way we can preserve the nested nature of the ClipDisplayItem and keep track of the clipping information when we implement draw_into_context. Plus, I believe we will have other nested display items like Opacity and stuff in the future.

@pcwalton @SimonSapin please let me know your feedback on this idea. Especially about the iteration part and the clipping part: should we have display items nested under ClipDisplayItem or should we flatten them?

@pcwalton What are the other requirements from the Display List data structure? The above algo will preserve all current behaviour, but you had mentioned something about animations and wanting to deal with z-index elements in a separate layer.

[larsbergstrom]

Requirements

• DisplayLists need tagging as active vs. inactive (this can also change over time)

These tags are a hint for later stages in a pipeline for which DisplayLists (the active ones) we should avoid rendering into the same underlying layer as other content because the active content would cause us to unnecessarily repaint inactive content. You do not need to compute these now, but we anticipate that we would set active at least when there is a CSS transition or animation property defined on an element in that DisplayList.

• Should have separate DisplayLists for each stacking context

Note that stacking contexts can come from at least one other place than just a new z-index and positioned elements: opacity.

• We need to be able to do some post-processing of the layers, possibly device-specific, later in the pipeline

One idea we’d like to follow up on is culling of occluded parts of the page, which is a technique that has worked well on low-power devices. We also need to be able to tell when we want to merge multiple layers based on available HW resources.

Implementation feedback

When I was talking at the workweek with @pcwalton and @nick29581, and we were hoping that instead of a tree of stacking contexts (which is admittedly easier to build!) we could instead produce a flattened list of DisplayLists that is in proper painting order and does not expose the stacking context or z-index information to the rest of the pipeline, so that all of the decisions that had to be made (i.e., ordering of the DisplayLists in terms of the zindex spec and ordering of the items within the DisplayList in tree order) are implicit in the data structure passed on and do not need to be recomputed by later stages.

Note that you may still want to build up the nested stacking contexts per your implementation design and just deliver the flattened DisplayLists to the rest of the pipeline.

@pcwalton, @SimonSapin, does this accurately capture some of our prior discussions on this front?

[SimonSapin]

@nical How does this look to you?

[nical]

Hi, I am not a display list expert (Matt Woodrow would be the go-to person for this), so on this topic I can just advise you guys to make the layerization heuristics (deciding what's active and what is not) as flexible as possible because tuning these heuristics will affect performance a lot. I can relate to how this has been affecting b2g and still does. I suspect marking an item active depends on more than what is presented in this thread (if you want to have very efficient layerization).

[pcwalton]

Fixed.