Simple incremental display list building using global Z-indices

[pcwalton]

Here's a proposal for simple incremental display list building:

1. Assign a global Z-index to each display item. This is an idea that we discussed in the past. The idea is that you can globally sort the entire display list once at the end instead of sorting as-you-go. The Z-index can basically be thought of as an arbitrarily long string to handle nested stacking contexts. These will need to be stable across DOM mutations (e.g. don't just use the index of a node's child in its sibling list because that could change as DOM elements are added and removed).

2. Keep track of which Fragments are clean (don't have REPAINT flags set) at all times. This could be a hash set that layout maintains, or it could be merged with the next step during restyle damage propagation.

3. Save display lists from layout to layout. Every time layout is done, instead of rebuilding from scratch, sweep through the display list and remove display items that are no longer relevant (because the fragment needed to be repainted or because the fragment disappeared). Make sure every display item is tagged with the ID of the Fragment it came from so we can do this.

4. Instead of rebuilding the DL from scratch every layout, only append items to the DL for elements that needed to be repainted.

5. Use Timsort to sort the display list before sending to WR. Timsort is designed to handle arrays that are mostly sorted very efficiently, which will be the case for most of our incremental display list construction.

Thoughts? I think the tricky part will be coming up with these global keys. Though the fact that Timsort is a stable sort may help us…

cc @jrmuizel @mrobinson @glennw

[mrobinson]

I think this could be a really great idea and would move Servo closer to fully incremental display list construction. Apart from the complication you mention with global key generation, another tricky bit is how to properly sort when only some siblings of a stacking context are invalidated. For instance:

StackingContext
   - element A
   - element B (invalid)
   - element C

We need some way of encoding that B goes after the preserved elements of A and the preserved elements of C. A potential fix here (which may have, in fact, been implicit in your description) is to regenerate elements at stacking context granularity.

That said, even the ability to generate global z-indices opens up a lot of interesting avenues for parallelism.

[jrmuizel]

This seems relatively sane. It's quite different in the details from what Chrome does but if you squint enough it's the same basic idea.

The squinty version is that you have a DAG of display items with edges representing the 'must draw after/z-order' relationship. You want to be able to replace parts of that DAG without having to regenerate it frame scratch. The ordering relationship (whether a global index as above, or local structural information as Chrome seems to use) lets you do this.

Also, instead of just appending to the existing list of display items, you can just sort the new list and then do a single pass to merge it into the new one. No point in throwing away the fact that the old list was sorted.

[jdm]

It's not clear that E-less easy is an appropriate tag for this issue given the ongoing discussion around it.