Flat Tree or Composed Tree

dizhang168 commented 1 month ago

This surfaced from the conversation at TPAC 2024 about whether we should use a Flat Tree Traversal (Meeting notes) for comparing Selection positions that cross shadow trees.

Composed Tree

With the Composed Tree, we do the normal DOM tree traversal, but consider the owner document to be the common ancestor. Why this is good:

Currently, most Selection API uses the Composed Tree, including setStart/setEnd/setBaseAndExtent/isPointInRange. There might be many compat risks to change these APIs.
Doesn’t require updating Style and Layout. Easier to implement.

Flat Tree

With the Flat Tree, we traverse a flattened tree where the shadow trees are flattened to all be contained within one tree. Why this is good:

This is what the user sees when the selection is painted.
Would take care of re-ordered slotted contents.
Would make IsPointInRange() and toString() more useful to web users, as what the user sees is what’s selected in the flat tree.
It avoids the problem of multiple range objects to manage, but looks visually contiguous to the user

Open questions

Should we change existing Selection APIs to use flat trees? This information can be stored internally and only be accessed by getComposedRanges(), keeping the rest of the behaviors unchanged.
Else, should we have new APIs which definitely do use Flat Tree?
Should we support discontiguous ranges?

Examples:

Selection where start and end are in the same tree, but slotted to be in reverse order. Selection start from the sibling of shadow host, end inside the slotted content. https://github.com/mfreed7/shadow-dom-selection?tab=readme-ov-file#3-slotted-content

Some use cases

Bidi, tables, flex/grid layout maybe.

Related issues

Need spec changes to Range and StaticRange to support nodes in different tree? #169 Serialization of the current selection, when that selection crosses shadow roots #163

dizhang168 commented 1 month ago

Personally, I think the getComposedRanges() API would be much more valuable if it was traversing using a flat tree. I also do agree this is a significant change. I wonder how hard it would be to change to flat tree if we ship getComposedRanges first using only composed tree?

rniwa commented 1 month ago

This is not just getComposedRanges. It will affect the semantics and rendering of selection. I don't think we can change the definition of selection once any API has shipped.

sefeng211 commented 1 month ago

Another option is to make selection to support multiple ranges, but I guess this is more complicated than using flat tree....

sefeng211 commented 1 month ago

@rniwa Ryosuke, do you mind clarify what you meant by the definition of selection? Is it selection should be in composed tree..or what else ?

dizhang168 commented 1 month ago

I did an audit of the existing Selection API that uses DOM tree traversal and where a Flat tree traversal would be more useful and visual:

Selection::setBaseAndExtent
Range::setStart/setStartBefore/setStartAfter
Range::setEnd/setEndAfter/setEndBefore
Range::isPointInRange
Range::comparePoint/compareBoundaryPoints
Range::intersectsNode
Range::commonAncestorContainer

Specifically, for Selection::setBaseAndExtent, I wrote out a proposal of how we can change/add to the existing API to allow a flat tree position comparison to set the base and extent: https://github.com/dizhang168/shadow-dom-selection/blob/main/flat-tree-setBaseAndExtent.md We should reach out to Editor authors to better understand their pain points with slots. If we want to fix all the existing Selection/Range APIs above to use flat tree, then that is a whole new project.

The more immediate question is scoping how getComposedRanges() behave. Blink prefers to use the flattened tree to set the composed range endpoints it exposes. These endpoints will only be accessed by this API and wouldn't change any existing behavior. This way, the output of getComposedRanges() would match the computed visible selection.

dizhang168 commented 1 month ago

@johanneswilm could you Agenda+ this for the upcoming Editing meeting? Thank you!

dizhang168 commented 1 month ago

After talking with the Blink team, we have come to an agreement that changing the Selection API to use flat tree traversal would be a huge project. The proposal of supporting multiple ranges for Selection is something we cannot implement currently. Adding more APIs should also be considered after a thorough new compatibility investigation. Surveying the existing feature requests, most complaints are about selection across trees not returning the same between browsers and less about specific slot edge cases. Since our goal is to unblock the web developers who depend on the Selection API, we agree to move forward with an implementation of getComposedRanges() using Composed DOM tree traversal.

With all the good conversations so far, it is obvious a flat tree traversal can help solve the discrepancy across browsers when it comes to how elements are selected. Some use cases include selection by dragging and converting a selection to string. We should keep this issue open and continue the discussion.

sefeng211 commented 1 month ago

(I'd like to document what I have in mind to support flat tree)

We need to introduce flat-before, flat-equal and flat-after algorithms to allow us comparing boundaries in flat tree

~and these algorithms will be used to the following API~ First, we keep these APIs as is

Selection::setBaseAndExtent
Range::setStart/setStartBefore/setStartAfter
Range::setEnd/setEndAfter/setEndBefore

Instead, we use Di's proposal to introduce a new set of setter APIs to allow web authors to use the flat tree algorithms. So that the true start and true end that match the visual selection will be stored.

And we also shouldn't change the following APIs because they should remain as is to not break the encapsulation of shadow trees.

Range::isPointInRange
Range::comparePoint/compareBoundaryPoints
Range::intersectsNode
Range::commonAncestorContainer

So we probably need a new set of APIs that can expose information across the boundary. Maybe we should introduce a new range call CrossShadowBoundaryRange that can only be returned from getComposedRanges. This range supports APIs to allow web authors to get results that match the what users see on screen.

w3c / selection-api