Bug 215755 - Remove almost all the remaining uses of live ranges
Summary: Remove almost all the remaining uses of live ranges
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: HTML Editing (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Darin Adler
URL:
Keywords: InRadar
Depends on:
Blocks: 217895 218007
  Show dependency treegraph
 
Reported: 2020-08-22 15:20 PDT by Darin Adler
Modified: 2020-10-20 21:37 PDT (History)
25 users (show)

See Also:


Attachments
Patch (119.12 KB, patch)
2020-08-23 12:16 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (150.53 KB, patch)
2020-08-25 19:29 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (157.31 KB, patch)
2020-08-26 14:44 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (157.66 KB, patch)
2020-08-26 15:51 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (158.99 KB, patch)
2020-08-26 16:10 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (158.27 KB, patch)
2020-08-27 19:04 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (164.37 KB, patch)
2020-08-28 10:16 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (164.27 KB, patch)
2020-08-28 12:23 PDT, Darin Adler
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Darin Adler 2020-08-22 15:20:10 PDT
Remove almost all the remaining uses of live ranges
Comment 1 Darin Adler 2020-08-23 12:16:42 PDT Comment hidden (obsolete)
Comment 2 Darin Adler 2020-08-25 19:29:24 PDT Comment hidden (obsolete)
Comment 3 Darin Adler 2020-08-26 14:44:55 PDT Comment hidden (obsolete)
Comment 4 EWS Watchlist 2020-08-26 14:45:36 PDT
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
Comment 5 Darin Adler 2020-08-26 15:51:42 PDT Comment hidden (obsolete)
Comment 6 Darin Adler 2020-08-26 16:10:13 PDT Comment hidden (obsolete)
Comment 7 Darin Adler 2020-08-26 17:04:29 PDT Comment hidden (obsolete)
Comment 8 Darin Adler 2020-08-27 11:53:08 PDT Comment hidden (obsolete)
Comment 9 Darin Adler 2020-08-27 19:04:15 PDT Comment hidden (obsolete)
Comment 10 Darin Adler 2020-08-28 10:16:29 PDT Comment hidden (obsolete)
Comment 11 Sam Weinig 2020-08-28 11:21:46 PDT
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.
Comment 12 Darin Adler 2020-08-28 12:23:19 PDT
Created attachment 407495 [details]
Patch
Comment 13 Darin Adler 2020-08-28 14:04:55 PDT
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.
Comment 14 EWS 2020-08-28 14:37:12 PDT
Committed r266295: <https://trac.webkit.org/changeset/266295>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 407495 [details].
Comment 15 Radar WebKit Bug Importer 2020-08-28 14:38:19 PDT
<rdar://problem/67962384>
Comment 16 Ryosuke Niwa 2020-10-17 23:28:12 PDT
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.
Comment 17 Ryosuke Niwa 2020-10-17 23:38:00 PDT
(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
Comment 18 Darin Adler 2020-10-18 09:38:53 PDT
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.
Comment 19 Ryosuke Niwa 2020-10-18 15:40:53 PDT
(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>
Comment 20 Ryosuke Niwa 2020-10-18 15:42:55 PDT
Filed https://bugs.webkit.org/show_bug.cgi?id=217895 to track the regression.
Comment 21 Ryosuke Niwa 2020-10-18 16:20:02 PDT
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.
Comment 22 Darin Adler 2020-10-18 16:35:20 PDT
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.