Bug 215755 – Remove almost all the remaining uses of live ranges

• Status: RESOLVED
• Resolution: FIXED
• Component: HTML Editing

[Darin Adler]

Remove almost all the remaining uses of live ranges

[Darin Adler]

Created attachment 407078 [details]
Patch

[Darin Adler]

Created attachment 407262 [details]
Patch

[Darin Adler]

Created attachment 407339 [details]
Patch

[EWS Watchlist]

Thanks for the patch. If this patch contains new public API please make sure it follows the guidelines for new WebKit2 GTK+ API. See http://trac.webkit.org/wiki/WebKitGTK/AddingNewWebKit2API

[Darin Adler]

Created attachment 407347 [details]
Patch

[Darin Adler]

Created attachment 407348 [details]
Patch

[Darin Adler]

Comment on attachment 407348 [details]
Patch

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

Tests are passing. Review time.

> Source/WebKitLegacy/mac/DOM/DOMUIKitExtensions.mm:127
> +// FIXME: Could use SimpleRange::intersectingNodes instead, if we did not want to preserve the historical behavior of returning a node with no children when the range starts inside it.

Since I wrote this comment, I added intersectingNodesWithDeprecatedZeroOffsetStartQuirk, which I could use here, especially if I added a IntersectingNodeRangeWithQuirk::first() function, like ElementChildRange::first.

> Tools/ChangeLog:9
> +        * TestWebKitAPI/Tests/WebCore/DocumentOrder.cpp:
> +        (TestWebKitAPI::TEST): Added a test case for a non-user-agent shadow tree.

Oops, I did more than that! I’ll write a more complete change log entry.

> Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/xcshareddata/xcschemes/TestWebKitAPI.xcscheme:58
> +      <CommandLineArguments>
> +         <CommandLineArgument
> +            argument = "--gtest_filter=*DocumentOrder*"
> +            isEnabled = "YES">
> +         </CommandLineArgument>
> +      </CommandLineArguments>

Probably should not land this?

[Darin Adler]

Oops, looks like we still have an assertion failure in the test: editing/pasteboard/copy-across-shadow-boundaries-crash.html

[Darin Adler]

Created attachment 407443 [details]
Patch

[Darin Adler]

Created attachment 407478 [details]
Patch

[Sam Weinig]

Comment on attachment 407478 [details]
Patch

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

This is such a fantastic change for improving the readability and understandability of this code.

> Source/WebCore/dom/SimpleRange.cpp:249
> +// FIXME: Name this "unionRange" instead? The word "union" is a noun more than a verb. Would like to call it just union if it wasn't for the conflict with the C keyword.

This would also make it consistent with the FloatRect/IntRect naming, unionRect(a, b).

> Source/WebCore/testing/Internals.cpp:2172
> +// FIXME: Find a good place for this general purpose algorithm.
> +static String join(Vector<String>&& strings)

Not for this change, but it should probably go in StringConcatenate.h, as it is the moral equivalent to makeString(). Wish I could think of a good way to make a generic join() operator for StringBuilder/makeString, but my efforts so far have been kind of bad.

[Darin Adler]

Created attachment 407495 [details]
Patch

[Darin Adler]

Comment on attachment 407478 [details]
Patch

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

>> Source/WebCore/dom/SimpleRange.cpp:249
>> +// FIXME: Name this "unionRange" instead? The word "union" is a noun more than a verb. Would like to call it just union if it wasn't for the conflict with the C keyword.
> 
> This would also make it consistent with the FloatRect/IntRect naming, unionRect(a, b).

OK, renaming to unionRange.

>> Source/WebCore/testing/Internals.cpp:2172
>> +static String join(Vector<String>&& strings)
> 
> Not for this change, but it should probably go in StringConcatenate.h, as it is the moral equivalent to makeString(). Wish I could think of a good way to make a generic join() operator for StringBuilder/makeString, but my efforts so far have been kind of bad.

Should we just add this feature to makeString? Then the call site could just call makeString instead of join. Seems like we could flatten any vector.

[EWS]

Committed r266295: <https://trac.webkit.org/changeset/266295>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 407495 [details].

[Radar WebKit Bug Importer]

<rdar://problem/67962384>

[Ryosuke Niwa]

Comment on attachment 407495 [details]
Patch

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

> Source/WebCore/dom/Node.cpp:2634
> -    while ((ancestor = ancestor->parentOrShadowHostNode()))
> +    while ((ancestor = ancestor->parentInComposedTree()))

Hm... I'm not certain that this is right. Unless we're doing tree traversal in the composed tree order,
which is only really used for rendering operations, we should be using parentOrShadowHostNode().

In general, the DOM spec only defines the ordering for nodes in the same tree
https://dom.spec.whatwg.org/#concept-tree-order
https://dom.spec.whatwg.org/#concept-tree-preceding

So if this is used in some DOM API implementations, we need to figure out which tree traversal strategy should be used.

[Ryosuke Niwa]

(In reply to Ryosuke Niwa from comment #16)
> Comment on attachment 407495 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=407495&action=review
> 
> > Source/WebCore/dom/Node.cpp:2634
> > -    while ((ancestor = ancestor->parentOrShadowHostNode()))
> > +    while ((ancestor = ancestor->parentInComposedTree()))
> 
> Hm... I'm not certain that this is right. Unless we're doing tree traversal
> in the composed tree order,
> which is only really used for rendering operations, we should be using
> parentOrShadowHostNode().
> 
> In general, the DOM spec only defines the ordering for nodes in the same tree
> https://dom.spec.whatwg.org/#concept-tree-order
> https://dom.spec.whatwg.org/#concept-tree-preceding
> 
> So if this is used in some DOM API implementations, we need to figure out
> which tree traversal strategy should be used.

Actually, I think this change regressed Range API so that now we can set start & end of Range to different trees. That's wrong.

We need to implement step 4.1 where we check the root node:
https://dom.spec.whatwg.org/#concept-range-bp-set

[Darin Adler]

I did this intentionally.

We could have multiple documentOrder functions, some that worked across trees and some the worked within trees, some that used the composed tree and some that don't. If we need them.

But I am not sure we need them.

I know that editing code does need to know answers for the composed tree order.

I think in some cases the algorithm is specified and callers can’t have pointers inside shadow trees, so the restriction isn’t in the Range class itself, it’s in the rules about what node pointers callers could have.

But could definitely be wrong and happy to fix.

Could you please give me examples of how to write failing tests, to go beyond your critique of the code? If you do, then I can explain why I thought this approach would work, and do the right kind of fix.

> Actually, I think this change regressed Range API so that now we can set start & end of Range to different trees.

If it did that, where’s the failing test?

I am happy to fix this once this is cleared up.

[Ryosuke Niwa]

(In reply to Darin Adler from comment #18)
> I did this intentionally.
> 
> We could have multiple documentOrder functions, some that worked across
> trees and some the worked within trees, some that used the composed tree and
> some that don't. If we need them.

Well, the trouble here is that this document order will only be correct for what the spec calls "flat tree". For most DOM APIs, we should not be using the flat tree (or composed tree in our codebase's terminology) for ordering purposes.

> I know that editing code does need to know answers for the composed tree
> order.

I think this is more subtle point than that. There are some editing code that would have to use the composed tree when asked to work with the composed tree. But in other cases, we need to be ignoring the shadow trees.

> I think in some cases the algorithm is specified and callers can’t have
> pointers inside shadow trees, so the restriction isn’t in the Range class
> itself, it’s in the rules about what node pointers callers could have.

That's not true. Range restricts that the root node of start & end must be same:
https://dom.spec.whatwg.org/#concept-range-bp-set

> But could definitely be wrong and happy to fix.

There is definitely a regression here. I've tested it manually myself.

> Could you please give me examples of how to write failing tests, to go
> beyond your critique of the code? If you do, then I can explain why I
> thought this approach would work, and do the right kind of fix.

<!DOCTYPE html>
<html>
<body>
<script>

const shadowHost = document.body.appendChild(document.createElement('div'));
const shadowRoot = shadowHost.attachShadow({mode: 'closed'});
shadowRoot.innerHTML = 'hello';

const range = document.createRange();
range.setStart(document.body, 0);
range.setEnd(shadowRoot, 1);

document.write(range.startContainer.getRootNode() == range.endContainer.getRootNode() ? 'PASS' : 'FAIL');

</script>
</body>
</html>

[Ryosuke Niwa]

Filed https://bugs.webkit.org/show_bug.cgi?id=217895 to track the regression.

[Ryosuke Niwa]

Comment on attachment 407495 [details]
Patch

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

> Source/WebCore/accessibility/AccessibilityObject.cpp:304
> -            if (createLiveRange(*misspellingRange)->compareBoundaryPoints(Range::END_TO_END, createLiveRange(start)).releaseReturnValue() > 0)
> +            if (misspellingRange && is_gt(documentOrder(misspellingRange->end, start.end)))

For example, this code probably shouldn't be crossing shadow boundaries because content-editable doesn't carry across shadow boundaries.

> Source/WebCore/accessibility/AccessibilityObject.cpp:310
> +            if (misspellingRange && is_lt(documentOrder(misspellingRange->start, start.start)))

Ditto.

> Source/WebCore/accessibility/AccessibilityObject.cpp:588
> +                    ? is_gt(documentOrder(foundStringRange->end, closestStringRange->end))
> +                    : is_lt(documentOrder(foundStringRange->start, closestStringRange->start));

Whereas here, using the composed tree is correct because rangeOfString uses TextIteratorTraversesFlatTree.

> Source/WebCore/dom/Node.cpp:2646
> +// FIXME: This function's name is not explicit about the fact that it's the common inclusive ancestor in the composed tree.
>  static AncestorAndChildren commonInclusiveAncestorAndChildren(const Node& a, const Node& b)

It's very dubious that this function considers slots. No HTML or DOM spec would use this algorithm.
DOM spec has the concept of shadow-including ancestors but it does not consider slots:
https://dom.spec.whatwg.org/#concept-shadow-including-inclusive-ancestor

I suspect this will cause a bunch of weird bugs or crashes in editing code
because now we end up finding a common ancestor that don't belong in the same tree.

> Source/WebCore/dom/Node.cpp:2677
> +// FIXME: This function's name is not explicit about the fact that it's the common inclusive ancestor in the composed tree.
>  RefPtr<Node> commonInclusiveAncestor(Node& a, Node& b)

Ditto.

> Source/WebCore/dom/Range.cpp:144
> -ExceptionOr<bool> Range::isPointInRange(Node& refNode, unsigned offset)
> +ExceptionOr<bool> Range::isPointInRange(Node& container, unsigned offset)

Same issue.

> Source/WebCore/dom/Range.cpp:165
> +    auto ordering = documentOrder({ container, offset }, makeSimpleRange(*this));

This is wrong. We're missing step 1 to check the root: https://dom.spec.whatwg.org/#dom-range-comparepoint

> Source/WebCore/dom/Range.cpp:175
> +ExceptionOr<Range::CompareResults> Range::compareNode(Node& node) const

Ditto. Although this is a WebKit only API, I don't think we want to be changing our behavior.

> Source/WebCore/dom/Range.cpp:209
> -ExceptionOr<short> Range::compareBoundaryPointsForBindings(unsigned short how, const Range& sourceRange) const
> +ExceptionOr<short> Range::compareBoundaryPoints(unsigned short how, const Range& sourceRange) const

Same issue here.

> Source/WebCore/dom/Range.cpp:251
> -ExceptionOr<bool> Range::intersectsNode(Node& refNode) const
> +bool Range::intersectsNode(Node& node) const

Same issue as other functions.

> Source/WebCore/dom/Range.cpp:673
> +    for (auto& node : intersectingNodes(range)) {

It's a bit confusing that intersects checks the composed / flat tree but intersectingNodes only considers the same tree.
The behavior is correct here but mixing those two completely different modes of traversal will be confusing if we don't give different names.

> Source/WebCore/editing/Editor.cpp:3712
> +            // Only consider ranges with a detected telephone number if they overlap with the selection.
> +            if (intersects(range, selectedRange))

Given scanForTelephoneNumbers doesn't use the flat / composed tree,
it's a bit dubious that we check the intersection using flat / composed tree.

> Source/WebCore/editing/FrameSelection.cpp:557
> +        if (auto range = m_selection.firstRange(); range && intersects(*range, node)) {

Oh neat. You fixed a bug here. I had been wondering why we have this selection repaint bug.

> Source/WebCore/editing/mac/DictionaryLookupLegacy.mm:72
> +    auto selectedRange = selection.firstRange();
> +    return selectedRange && isPointInRange(*selectedRange, makeBoundaryPoint(position));

This is likely correct although I doubt that the rest of dictionary lookup code handles the shadow boundaries correctly.

> Source/WebCore/page/DOMSelection.cpp:326
> +        if (!selectedRange->start.container->containingShadowRoot() && intersects(*selectedRange, range))
> +            selection.setSelection(unionRange(*selectedRange, range));

I don't think we want to do this. This will make the presence of shadow DOM observable.

> Source/WebCore/page/DOMSelection.cpp:364
> +    return allowPartial ? intersects(*selectedRange, node) : contains(*selectedRange, node);

I don't think this is correct. Because we're working with Range object in the selection API, this API should not be considering shadow boundaries.

[Darin Adler]

I’m worried that we need multiple versions of every function based on document structure and ordering. Maybe three of each. I think that’s going to be pretty bad.