Bug 217895 – REGRESSION(r266295): Range allows start and end containers to belong to different trees

• Component: DOM
• Status: RESOLVED FIXED

[Ryosuke Niwa]

After https://trac.webkit.org/changeset/266295, we allow start & end of a range to point to different trees.
This is wrong. We need to implement step 4.1 of https://dom.spec.whatwg.org/#concept-range-bp-set

[Ryosuke Niwa]

Created attachment 411720 [details]
test

[Darin Adler]

I will fix this. I am really surprised that there is no coverage of this in WPT.

[Ryosuke Niwa]

It looks like Range::comparePoint has also regressed.

[Ryosuke Niwa]

Range::compareNode and Range::compareBoundaryPoints have the same issue too.

[Ryosuke Niwa]

Also Range::intersectsNode & Range::isPointInRange.

[Ryosuke Niwa]

(In reply to Darin Adler from comment #2)
> I will fix this. I am really surprised that there is no coverage of this in
> WPT.

I'm starting to think that WPT is missing a whole bunch of test cases for Shadow DOM with regards to Range. Clearly, none of these functions have adequate WPT tests with regards to Shadow DOM.

[Ryosuke Niwa]

Looks like DOMSelection::addRange and DOMSelection::containsNode have similar bugs as well.

[Darin Adler]

One problem is that there is a lot of editing code that needs the current behavior. We can fix documentOrder to work properly, and all of this will start working, and all the editing code will break, proving, I suppose, that we need multiple sets of documentOrder functions.

[Darin Adler]

Needs the current behavior of checking order of nodes, not the current behavior of Range.

[Darin Adler]

So WPT didn’t have tests for this, and WebKit didn’t either.

Can you see how I misunderstood our intended behavior?

[Ryosuke Niwa]

(In reply to Darin Adler from comment #8)
> One problem is that there is a lot of editing code that needs the current
> behavior. We can fix documentOrder to work properly, and all of this will
> start working, and all the editing code will break, proving, I suppose, that
> we need multiple sets of documentOrder functions.

I think we need that. Maybe what we need is composedTreeOrder and treeOrder and we just need to replace existing usage of documentOrder with either one of the two.

I commented in https://bugs.webkit.org/show_bug.cgi?id=215755 as I was going through your patch there but I think "commonInclusiveAncestorAndChildren" is a very confusing function because it doesn't match any of the DOM concepts in the spec.

[Ryosuke Niwa]

(In reply to Darin Adler from comment #10)
> So WPT didn’t have tests for this, and WebKit didn’t either.
> 
> Can you see how I misunderstood our intended behavior?

Yeah, there is no doubt that we need more tests. The annoying thing is that we even not every part of HTML / DOM spec work correctly with the Shadow DOM, and we've been slowly finding more cases and fixing them as we go.

[Darin Adler]

Yes, but let's not slippery slide into talking about everything.

All of these functions have no tests whatsoever about this topic, apparently!

[Darin Adler]

(In reply to Ryosuke Niwa from comment #11)
> I think we need that. Maybe what we need is composedTreeOrder and treeOrder
> and we just need to replace existing usage of documentOrder with either one
> of the two.

Yes, and they will share code; either templates or function arguments so they can be the same code.

> I commented in https://bugs.webkit.org/show_bug.cgi?id=215755 as I was going
> through your patch there but I think "commonInclusiveAncestorAndChildren" is
> a very confusing function because it doesn't match any of the DOM concepts
> in the spec.

Sure, same thing, we can have multiple functions for the different trees.

I’m just worried about having *so* many different ones, and so many different functions. For example, Position has <,>,== operators, and I think it’s ambiguous which of the trees they would be based on.

Other functions which we might need multiple versions of:

isPointInRange
contains
intersects
unionRange
intersection
intersectingNodes
intersectingNodesWithDeprecatedZeroOffsetStartQuirk

It bothers me that we might need 2 of each, and I am concerned about what to name things. Also, aside from the "which tree" issue, now that I read the DOM specification text about Range a bit more carefully, I think the names and semantics of these might need a bit of work. There are contained nodes, partially contained nodes, and the special case of CharacterData endpoint nodes which are partially intersecting (but not "partially contained") and I want to figure out how to cleanly include them all. Not sure that "intersecting" has a precise definition.

[Darin Adler]

Started working on this by making a test that covers all of these cases.

[Darin Adler]

I’m fixing this by adding new functions name treeOrder. Not yet sure how many other new functions I will need to fix Range.

The existing documentOrder functions can later be renamed composedTreeOrder and maybe eventually deleted if no one needs that.

The fate of the many other functions like isPointInRange is unclear: not sure how many different variants of those I will need to make to fix this bug or to resolve other issues.

[Darin Adler]

Created attachment 411949 [details]
Patch

[Darin Adler]

Created attachment 411951 [details]
Patch

[Darin Adler]

Created attachment 411953 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 411953 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=411953&action=review

Should I file a new bug for DOMSelection?

> Source/WebCore/ChangeLog:26
> +        also be objects of another type. Maybe an enumeration named TreeType instead?

Maybe enum class would be more appropriate.

> Source/WebCore/dom/Node.h:759
> +struct ShadowIncludingTree { };

So it never makes sense to use this type thing for ordering nodes.
It's only ever used when we're walking up the ancestor nodes so maybe TreeIncludingShadowAncestors might be appropriate.
We probably don't want to support it in treeOrder though.

> Source/WebCore/dom/SimpleRange.cpp:215
> +template<typename TreeType> bool isPointInRange(const SimpleRange& range, const BoundaryPoint& point)

This is somewhat tangential but this seems backwards.
I'd have expected point to come before range given this is asking: is *point* in *range*.

[Darin Adler]

Comment on attachment 411953 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=411953&action=review

>> Source/WebCore/ChangeLog:26
>> +        also be objects of another type. Maybe an enumeration named TreeType instead?
> 
> Maybe enum class would be more appropriate.

It would be irritating to have it be long like treeOrder<TreeType::Composed>. What do you think?

>> Source/WebCore/dom/Node.h:759
>> +struct ShadowIncludingTree { };
> 
> So it never makes sense to use this type thing for ordering nodes.
> It's only ever used when we're walking up the ancestor nodes so maybe TreeIncludingShadowAncestors might be appropriate.
> We probably don't want to support it in treeOrder though.

I took this name right out of the DOM specification. I understand we’d never want to use it for treeOrder, but I don’t think we need to enforce that.

>> Source/WebCore/dom/SimpleRange.cpp:215
>> +template<typename TreeType> bool isPointInRange(const SimpleRange& range, const BoundaryPoint& point)
> 
> This is somewhat tangential but this seems backwards.
> I'd have expected point to come before range given this is asking: is *point* in *range*.

I think I will rename this to contains in a future patch.

[Darin Adler]

(In reply to Ryosuke Niwa from comment #20)
> Should I file a new bug for DOMSelection?

Probably. Which method do you think is wrong? I think they are already all correct.

[Ryosuke Niwa]

(In reply to Darin Adler from comment #21)
> Comment on attachment 411953 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=411953&action=review
> 
> >> Source/WebCore/ChangeLog:26
> >> +        also be objects of another type. Maybe an enumeration named TreeType instead?
> > 
> > Maybe enum class would be more appropriate.
> 
> It would be irritating to have it be long like
> treeOrder<TreeType::Composed>. What do you think?

Oh I see what you're saying. Maybe what you have is better then. We can always change it later if others feel strongly.

> >> Source/WebCore/dom/Node.h:759
> >> +struct ShadowIncludingTree { };
> > 
> > So it never makes sense to use this type thing for ordering nodes.
> > It's only ever used when we're walking up the ancestor nodes so maybe TreeIncludingShadowAncestors might be appropriate.
> > We probably don't want to support it in treeOrder though.
> 
> I took this name right out of the DOM specification. I understand we’d never
> want to use it for treeOrder, but I don’t think we need to enforce that.

Oh I see. You're referring to:
https://dom.spec.whatwg.org/#concept-shadow-including-tree-order

I guess we can use that then.

> >> Source/WebCore/dom/SimpleRange.cpp:215
> >> +template<typename TreeType> bool isPointInRange(const SimpleRange& range, const BoundaryPoint& point)
> > 
> > This is somewhat tangential but this seems backwards.
> > I'd have expected point to come before range given this is asking: is *point* in *range*.
> 
> I think I will rename this to contains in a future patch.

Ok.

(In reply to Darin Adler from comment #22)
> (In reply to Ryosuke Niwa from comment #20)
> > Should I file a new bug for DOMSelection?
> 
> Probably. Which method do you think is wrong? I think they are already all
> correct.

Filed https://webkit.org/b/218007

[Ryosuke Niwa]

By the way, I mentioned in the slack but I don't think the current implementation of documentOrder is correct with respect to slots. You can't use "offset" to compare position in the case a node is assigned to a slot because slotting could re-order nodes. e.g. <slot name="a"></slot><slot slot="b"> in the shadow then <span slot="b"></span><span slot="a"></span> would put span[slot=a] before span[slot=b]. So I suspect what really want is simply shadow-including tree order in some code, and not composed/flat tree. But you mentioned that the composed tree was needed somewhere? Where was that?

[Darin Adler]

(In reply to Ryosuke Niwa from comment #24)
> But you mentioned that the composed tree was needed somewhere? Where was
> that?

It was in some editing use cases that were covered by regression tests. We can switch the call sites that use ComposedTree off of it one by one and that should "smoke it out".

[Darin Adler]

Comment on attachment 411953 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=411953&action=review

>>>> Source/WebCore/ChangeLog:26
>>>> +        also be objects of another type. Maybe an enumeration named TreeType instead?
>>> 
>>> Maybe enum class would be more appropriate.
>> 
>> It would be irritating to have it be long like treeOrder<TreeType::Composed>. What do you think?
> 
> Oh I see what you're saying. Maybe what you have is better then. We can always change it later if others feel strongly.

I can change from classes to an enumeration without changing how it’s used. I’d change from "typename TreeType" to "TreeType treeType" and then uses from "TreeType" to "treeType". Going further to an enum class would require that I change the call sites of the functions, the way I showed above.

[Darin Adler]

Committed r268800: <https://trac.webkit.org/changeset/268800>

[Radar WebKit Bug Importer]

<rdar://problem/70532742>