Roadmap for a first zest of incrementality in layout 2020

[nox]

We already have a damage system which tracks whether a node have dirty descendants or not, HAS_DIRTY_DESCENDANTS. In DOM, this is set on all ancestors of all nodes with a pending restyle or whose children were mutated. In layout 2013, this flag is unset in the postorder traversal step through construct_flows_at. In layout 2020, we don't use style's traversal machinery at all to do the layout itself, so we need to plug the unsetting in the layout box tree construction. My ideal roadmap for this stuff is:

1. make those dirty bits use an atomic integer type (in Servo only, Gecko can't afford the penalty hit I assume), I don't want to need to call unsafe methods in the middle of nowhere in layout 2020, and both @asajeffrey and I have ideas on how to change those traversals, in both layout and script, to be able to use proper mutation without the need for multi-thread synchronization;

2. move the unset_dirty_descendants call from the restyling pass to the box tree construction system;

3. make the box tree construction system reuse a box if it isn't dirty and it doesn't have dirty descendants;

4. introduce a "dirty roots" concept, piggybacking the "nodes with pending restyles" concept, to do incremental box construction without going through the document tree every time, like Firefox.

Cc @SimonSapin @emilio

[nox]

@emilio says that step 2 should be done with a different layout-specific damage system.

[nox]

An interesting discussion about all that stuff.

https://matrix.to/#/!crXxRMedJXFPxKffWI:mozilla.org/$TMH7akLhjHuJiEcfHkvrK2Wsis0tOnTlGBklqVbV1ok?via=mozilla.org&via=matrix.org&via=igalia.com

[asajeffrey]

One thing we should think about is using a library for dirty bit management rather than making every dirty bit an ad hoc case. Self-adjusting computation (which is the name used for dirty bit managing APIs 🤷‍♂️) has been around for a while. We could either use adapton or write our own.

[nox]

@asajeffrey I disagree quite a bit on this. That's basically "let's rewrite everything again". Literally every framework or tool I've looked at to do "self-adjusting computations" were extremely invasive and too general-purpose for our needs.

[asajeffrey]

Well, it's a trade off between an API which is, like you said, quite invasive, and having to do ad hoc reasoning for every dirty bit. Essentially this is cache invalidation, so it's unsurprisingly tricky.

[nox]

I'm wary of adapton and its heavy API full of macros, and how we can integrate that in layout 2020 in any reasonable amount of time.

[asajeffrey]

Adapton is probably more than we need, but we could shoot for a simpler API, with something like RW<T> for get/send and RO<T> for just get, with dirty bit propagation so that the RO<T> gets its value updated if any of its dependencies were.

The problem with these APIs is that they're quite visible, in that the imperative code:

    if (dirty_y) {
       y = foo(x);
       dirty_y = false;
    }

turns into:

    y = x.map(foo);

which like you said is a big rewrite :/

[nox]

which like you said is a big rewrite :/

So we shouldn't shoot for that, that's what I'm saying. Also, there is no such thing as a mere dirty_y = false statement anywhere.

---

As for progress: I have added a concept of "dirty root" to the Document struct, but now I need to properly update that on node removal.

[nox]

So I made this which implements the same dirty root concept as the one in Gecko. There are a lot of things to double check (what happens on deletion, making sure that the dirty root is not pointing to a removed node, etc etc), but the intent is to be able to restyle from that root, then maybe go a few layers up again in the tree to relayout only a portion of it. The first valid point to relayout will probably block elements that introduce their own stacking context.