Element upgrade ordering

[justinfagnani]

The scoped custom elements proposal needs to define the upgrade order of custom elements within shadow roots that have a scoped registry.

We've discussed the question of scoped registry upgrade ordering in other issues, but it deserves its own issue so we can more easily track the discussion and consensus.

The discussion on ordering starts here: #716 (comment) and is also brought up here: #865 (comment) with the second link having some more detailed discussion.

To reiterate, the two main options seem to be:

1. Keep document order upgrading.
2. Order upgrades by the order that shadow roots were associated with the registry, then tree order within those roots.

It seemed from the discussion in the last face-to-face and in #865 that if disconnected trees are not upgraded and registries are restricted to one document that keeping a list of shadow roots associated with a registry - in the order they were created, and upgrading only those roots was preferable. I did want open this to double check with @rniwa @annevk and @emilio especially.

[annevk]

Yeah, the argument in favor of 2 is performance. I don't think I explained the argument of 1 during the call, but it's consistency with the global registry.

Breaking consistency for the sake of performance is acceptable, but it also comes with additional bookkeeping as you note. (I'm wondering if #907 (comment) applies here as well, but I'm not familiar enough with the specifics.)

[rniwa]

Note that if we went with (2), we still can't allow upgrading of elements in a disconnected subtree for the same reasons as I had stated in #419

[justinfagnani]

@rniwa agreed. I think we mentioned this in the f2f as well as not wanting to diverge from global registry behavior.

[trusktr]

Element upgrade order with a document registry already changes depending on various factors (f.e. whether elements come before a script tag that runs all customElements.define calls, etc), so authors already must design their elements such that upgrade order does not matter if they wish for their elements to be robust and to work properly regardless in which order some end user may load things.

Threfore, specifying a specific order for ShadowRoot registries that does not match document registries is totally acceptable, and an author's robust elements will probably already just work regardless. (It is a huge headache to figure how to write that robustness though).

[keithamus]

WCCG had their spring F2F in which this was discussed. I'd like to point out that you can read the full notes of the discussion (#978 (comment)) in which this was discussed, heading entitled "Scoped Custom Element Registries".

[rniwa]

2023 TPAC F2F resolution: We would use the ordered set of weak references to documents to which a shadow root was created with a given custom element registry. When a shadow root is adopted from one document to another, that document is inserted into this ordered set. We would ignore any documents without browsing context or any disconnected trees at the time of upgrade call. In each document, all shadow trees are visited in the document order.

[xiaochengh]

I'm implementing scoped upgrade in Chromium, and found that the upgrade order can be made even simpler:

• Elements in different documents are upgraded in frame tree order, namely, elements in a frame attached earlier will be upgraded earlier
• Everything else remains the same: upgrade in tree order in the same document, don't upgrade disconnected elements, and don't upgrade elements without a frame

And that doesn't require complicated index structure or expensive full document traversals. We only need to maintain the set of candidate elements for each scoped registry, and when upgrading, perform a bottom-up traversal from those candidates to the root to build a minimal subtree containing every one of them, so that we can sort them.

In fact, the current (non-scoped) registry in Chromium is already doing that, and it's straightforward to extend that to work for multiple tree scopes and multiple documents.

Since there's no implementation issues, I think we should simplify the resolution into using frame tree order when there are multiple documents.

[annevk]

The concern we discussed at the meeting was that going through all documents belonging to the same agent would be slow. I'm not even sure we have a well-defined order for all documents belonging to the same agent. (You can have multiple frame trees after all.)

[smaug----]

What is "frame tree order"? Is that iframes and such? There is no order between iframes especially if they are in different documents.

[rniwa]

Yeah, there could be multiple frame trees (i.e. multiple top-level documents) for a give agent so I don't see how it would be possible to totally order documents based on the frame free ordering.

[xiaochengh]

The "frame tree" I'm thinking about is: since each CustomElementRegistry is created in a global object Window, we can (conceptually) traverse from this Window through the parent and array index getters and get a tree of windows. And the tree order of this tree is well-defined as the insertion order.

I assume there's no way to use a registry in an active document outside this tree, is that correct? If so then we can use this tree.

[smaug----]

But the point is that you can use the CustomElementRegistry in another top level window, or in any iframe there.

[xiaochengh]

Maybe I missed something obvious, but could you give an example?

Also, if that's possible, I assume these top level windows must be in a bigger tree (since that's how it's implemented in Chromium), whose tree order can still be used here.

[annevk]

If you use window.open() or <a target>. There is some kind of order there too, for sure, but we don't have any existing infrastructure around looping through it all. It's also not immediately clear to me we want to make that order observable.

[xiaochengh]

Thanks! I'll add that to the test cases.

Agreed that we probably don't want to expose the tree order implied by window.opener.

How about using document creation time order? This is still easy to implement without performance issues, easy to explain to developers and does not require any additional index structure.

[annevk]

Document creation-time is also not something we expose today or use as a primitive as far as I know. What's wrong with the set approach we discussed at the meeting?

[xiaochengh]

1. I found it harder to implement in Chromium. It requires adding new index structures, while what I proposed can fully make use of existing structures in Chromium.
   And document creation time order shouldn't be hard to implement in other engines (if I read the code correctly):

   • WebKit currently doesn't maintain any data structure for upgrades but traverses the full document, so it's free to add any index structure
   • Gecko's current implementation seems similar to Chromium, so it doesn't require any additional index structure for document creation time order, either.

2. I think an ordering is simpler for spec and developers if it depends less on the past states

Since what we want is just a fixed ordering without implementation or performance issues, if there are multiple orderings to choose, we should choose the simplest one.

Document creation-time is also not something we expose today or use as a primitive as far as I know

I was inspired by this, which uses child frame insertion time but doesn't quite expose it as a primitive:

Sort children in ascending order, with navigableA being less than navigableB if navigableA's container was inserted into W's associated Document earlier than navigableB's container was.

Since we can use frame insertion time, maybe we can also use document creation time in a similar manner?

[annevk]

I was inspired by this

I see, I consider that extremely fragile and not well tested. A lot of the words there are not defined in terms of well-understood primitives.

[rniwa]

FWIW, traversing documents in their creation order isn't a thing so we'd need a way to sort documents in that order, which could be quite expensive. Furthermore, each scoped registry needs to remember the set of documents that contain a shadow tree which uses the registry anyway since otherwise UA would have to traverse through all documents in the creation order and filter those that do (e.g. by having a set of all scoped registries per document).

My preference is to still use the ordering we agreed to during TPAC since it's a lot simpler to spec and implement.

[smaug----]

I agree. The approach we discussed during TPAC is indeed simple, to spec and implement and to understand.

[xiaochengh]

All right, I've implemented it in Chromium following the TPAC resolution's upgrade ordering.

It does need some new structures, but much less than I thought. So everything is fine, and I suppose we just need some explainer/spec edits before closing this issue?