Bug 217886 – Optimize Range and StaticRange by having AbstractRange derive from SimpleRange

• Status: ASSIGNED
• Component: DOM

[Darin Adler]

Optimize Range and StaticRange by having AbstractRange derive from SimpleRange

[Darin Adler]

Created attachment 411690 [details]
Patch

[Darin Adler]

Created attachment 411691 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 411691 [details]
Patch

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

> Source/WebCore/dom/AbstractRange.h:34
> +class AbstractRange : public RefCounted<AbstractRange>, protected SimpleRange {

This is a random tangential point but it occurs to me that SimpleRange having two BoundaryPoint isn't great for packing.
It might be better to instead store Ref<Node>, Ref<Node>, then two offsets in that order, and create BoundaryPoint object on fly when they're needed.
That would reduce the size of SimpleRange by 8 bytes in 64-bit architecture although I'm not certain if it's all that important.

> Source/WebCore/dom/AbstractRange.h:52
> +WEBCORE_EXPORT const SimpleRange& makeSimpleRange(const AbstractRange&);

I think MSVC doesn't like the fact this has WEBCORE_EXPORT but the above friend declaration doesn't.

> Source/WebCore/dom/Range.cpp:126
> +    boundary.container = WTFMove(container);
> +    boundary.offset = offset;

Why not just boundary = BoundaryPoint { WTFMove(container), offset } ?

> Source/WebCore/dom/Range.cpp:128
> +    if (!is_lteq(documentOrder(start, end)))

I commented in https://bugs.webkit.org/show_bug.cgi?id=215755 but this check is currently wrong.
We need to add step 4.1 in https://dom.spec.whatwg.org/#concept-range-bp-set and also check that the root nodes are equal.

> Source/WebCore/dom/Range.cpp:129
> +        otherBoundary(boundary) = boundary;

I think it's more readable for this to be passed in as an argument.
Also, don't we need to update childBefore(otherBoundary(boundary)) here?

> Source/WebCore/dom/Range.cpp:869
> +    if (boundary.container.ptr() == &container)
> +        boundary.offset = computeNodeIndexAfter(childBefore(boundary).get());

Don't we also need to invalidate m_childBeforeStart/m_childBeforeEnd?
Maybe we should make some kind of wrapper objects for start & end,
and have most of Range code work with that phantom object.
Otherwise, it's easy to forget those side data exists.

> Source/WebCore/dom/Range.cpp:939
>  void Range::textInserted(Node& text, unsigned offset, unsigned length)

It's silly that this takes Node& instead of CharacterData&.

[Darin Adler]

Comment on attachment 411691 [details]
Patch

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

>> Source/WebCore/dom/Range.cpp:128
>> +    if (!is_lteq(documentOrder(start, end)))
> 
> I commented in https://bugs.webkit.org/show_bug.cgi?id=215755 but this check is currently wrong.
> We need to add step 4.1 in https://dom.spec.whatwg.org/#concept-range-bp-set and also check that the root nodes are equal.

Are you sure? When the root nodes are not equal the order is “unordered” and that will return false from “is_lteq”. Just to double check, is there a test failing because this is wrong or are you just saying it’s wrong because of code inspection?

[Darin Adler]

Comment on attachment 411691 [details]
Patch

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

Thanks so much for looking this over! I have to find the mistake I made that’s causing all the tests to fail, but I will also take all your suggestions.

>> Source/WebCore/dom/AbstractRange.h:34
>> +class AbstractRange : public RefCounted<AbstractRange>, protected SimpleRange {
> 
> This is a random tangential point but it occurs to me that SimpleRange having two BoundaryPoint isn't great for packing.
> It might be better to instead store Ref<Node>, Ref<Node>, then two offsets in that order, and create BoundaryPoint object on fly when they're needed.
> That would reduce the size of SimpleRange by 8 bytes in 64-bit architecture although I'm not certain if it's all that important.

This would have a colossal effect on use of SimpleRange. “Create BoundaryPoint on the fly when needed” would change this from a struct to a class and change all uses. You could no longer take references to the boundary points or use assignment to change them.

I understand that we could make them smaller this way but it’s a big deal and deeply changes how the thing works.

>> Source/WebCore/dom/Range.cpp:126
>> +    boundary.offset = offset;
> 
> Why not just boundary = BoundaryPoint { WTFMove(container), offset } ?

Good idea, will do.

>> Source/WebCore/dom/Range.cpp:869
>> +        boundary.offset = computeNodeIndexAfter(childBefore(boundary).get());
> 
> Don't we also need to invalidate m_childBeforeStart/m_childBeforeEnd?
> Maybe we should make some kind of wrapper objects for start & end,
> and have most of Range code work with that phantom object.
> Otherwise, it's easy to forget those side data exists.

No, we don’t. This is the case where *other* children changed and we re-derive the offset *from* childBefore, which does not change. That was the same before; invalidateOffsef did the same thing.

>> Source/WebCore/dom/Range.cpp:939
>>  void Range::textInserted(Node& text, unsigned offset, unsigned length)
> 
> It's silly that this takes Node& instead of CharacterData&.

Yes I will change that.

[Darin Adler]

Comment on attachment 411691 [details]
Patch

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

>> Source/WebCore/dom/Range.cpp:129
>> +        otherBoundary(boundary) = boundary;
> 
> I think it's more readable for this to be passed in as an argument.
> Also, don't we need to update childBefore(otherBoundary(boundary)) here?

Yes, we do need to update childBefore here.

When you say "more readable" to have this passed in, should we pass in all four of boundary, other, childBefore, and other childBefore? I didn’t want to do that because I thought it would be easier to know we had it correct if we didn’t pass things separately, but I could definitely do so. Here and in the other places too.

[Darin Adler]

Created attachment 411708 [details]
Patch

[Darin Adler]

OK, this is passing tests now, so ready to land once I have a review+. I considered all of Ryosuke’s comments, so those should be mostly resolved now.

[Darin Adler]

Comment on attachment 411708 [details]
Patch

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

> Source/WebCore/ChangeLog:8
> +        * Headers.cmake: Removed BoundaryPoint.h.

Oops, this should say RangeBoundaryPoint.h. Code change fine, change log comment wrong.

[Darin Adler]

Comment on attachment 411708 [details]
Patch

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

> Source/WebCore/dom/Range.cpp:947
> +        childBeforeBoundary = nullptr;

I can remove this line of code, because it’s guaranteed that the boundary contains was a text node in this case, which means it’s already null. This is the same reason that we can use the boundary.offset, knowing it’s a character offset. So I should remove this line of code.

[Darin Adler]

Comment on attachment 411708 [details]
Patch

Setting commit-queue- to make sure I don’t forget to at least fix the small change log mistake and remove the one unnecessary line of code before landing. The two things I just mentioned in comments.

[Darin Adler]

Comment on attachment 411708 [details]
Patch

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

>> Source/WebCore/dom/Range.cpp:947
>> +        childBeforeBoundary = nullptr;
> 
> I can remove this line of code, because it’s guaranteed that the boundary contains was a text node in this case, which means it’s already null. This is the same reason that we can use the boundary.offset, knowing it’s a character offset. So I should remove this line of code.

the boundary *container* was a text node

[Darin Adler]

Comment on attachment 411708 [details]
Patch

The mac-debug-wk1 failures look real. Will fix.

[Ryosuke Niwa]

https://ews-build.s3-us-west-2.amazonaws.com/macOS-Mojave-Debug-WK1-Tests-EWS/r411708-20704/results.html

fast/dom/non-numeric-values-numeric-parameters.html:
ASSERTION FAILED: is<Text>(oldNode.nextSibling())
./dom/Range.cpp(966) : void WebCore::Range::textNodeSplit(WebCore::BoundaryPoint &, RefPtr<WebCore::Node> &, WebCore::Text &)
1   0x10564ac89 WTFCrash
2   0x121aac56b WTFCrashWithInfo(int, char const*, char const*, int)
3   0x12515d0aa WebCore::Range::textNodeSplit(WebCore::BoundaryPoint&, WTF::RefPtr<WebCore::Node, WTF::DumbPtrTraits<WebCore::Node>, WTF::DefaultRefDerefTraits<WebCore::Node> >&, WebCore::Text&)
4   0x12515cff6 WebCore::Range::textNodeSplit(WebCore::Text&)
5   0x124f65478 WebCore::Document::textNodeSplit(WebCore::Text&)
6   0x1251cfa82 WebCore::Text::splitText(unsigned int)
7   0x1237fd243 WebCore::jsTextPrototypeFunction_splitTextBody(JSC::JSGlobalObject*, JSC::CallFrame*, WebCore::JSText*)
8   0x12376df79 long long WebCore::IDLOperation<WebCore::JSText>::call<&(WebCore::jsTextPrototypeFunction_splitTextBody(JSC::JSGlobalObject*, JSC::CallFrame*, WebCore::JSText*)), (WebCore::CastedThisErrorBehavior)0>(JSC::JSGlobalObject&, JSC::CallFrame&, char const*)
9   0x12376dc54 WebCore::jsTextPrototypeFunction_splitText(JSC::JSGlobalObject*, JSC::CallFrame*)
10  0x22b0f6601178
11  0x105c2e05c llint_entry

[Ryosuke Niwa]

Comment on attachment 411708 [details]
Patch

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

> Source/WebCore/dom/Range.cpp:108
> -ExceptionOr<void> Range::setStart(Ref<Node>&& container, unsigned offset)
> +ExceptionOr<void> Range::setBoundary(BoundaryPoint& boundary, RefPtr<Node>& childBeforeBoundary, BoundaryPoint& otherBoundary, RefPtr<Node>& childBeforeOtherBoundary, Ref<Node>&& container, unsigned offset)

Hm... it sucks that we have to pass in 4 variables.

> Source/WebCore/dom/Range.cpp:114
> +    boundary = { WTFMove(container), offset };
> +    childBeforeBoundary = childNode.releaseReturnValue();

What if we added a helper struct like this:
struct BoundaryPointWithChildBeforeBoundary {
    BoundaryPoint& boundary;
    RefPtr<Node>& childBeforeBoundary;
};

> Source/WebCore/dom/Range.cpp:117
> +        otherBoundary = boundary;
> +        childBeforeOtherBoundary = childBeforeBoundary;

Then this could be one liner.

But maybe it's not really worth the extra complexity / code.

> Source/WebCore/dom/Range.cpp:214
> +    const BoundaryPoint* thisPoint;
> +    const BoundaryPoint* otherPoint;

Instead of computing this & other point, why don't we just call documentOrder in each case below?

> Source/WebCore/dom/Range.cpp:216
>      switch (how) {
>      case START_TO_START:

In fact, we could wrap this into a helper function so that we can just do:
switch (how) {
case START_TO_START:
    return documentOrder(start, sourceRange.start);
...
}

> Source/WebCore/dom/Range.cpp:258
> -static inline Node* highestAncestorUnderCommonRoot(Node* node, Node* commonRoot)
> +static inline RefPtr<Node> highestAncestorUnderCommonRoot(Node& node, Node& commonRoot)

Per rule we've come up with, we don't need to return a RefPtr here.
It's okay to return a raw pointer. It's the caller which has to store it in a Ref/RefPtr.
But it's okay to make this return Ref/RefPtr if we want to avoid repeating makeRefPtr in every call site.

>>> Source/WebCore/dom/Range.cpp:947
>>> +        childBeforeBoundary = nullptr;
>> 
>> I can remove this line of code, because it’s guaranteed that the boundary contains was a text node in this case, which means it’s already null. This is the same reason that we can use the boundary.offset, knowing it’s a character offset. So I should remove this line of code.
> 
> the boundary *container* was a text node

Maybe we should assert it instead?

> Source/WebCore/dom/Range.cpp:966
> +    ASSERT(is<Text>(oldNode.nextSibling()));

I think it's possible that oldNode doesn't have a parent here as evidenced by the assert in line 986 below.
In fact, all these assertions seem kind of bogus as it's always possible for mutation events to have re-arranged these nodes.

Document::textNodeSplit is called too late. We need to make the adjustment before we start firing mutation events.
Thats probably too big of a patch to do it as a part of this patch though.

> Source/WebCore/dom/Range.cpp:969
>          unsigned splitOffset = oldNode.length();

Can we assert here that childBeforeBoundary is null?

[Radar WebKit Bug Importer]

<rdar://problem/70654513>

[Darin Adler]

Comment on attachment 411708 [details]
Patch

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

>> Source/WebCore/dom/Range.cpp:108
>> +ExceptionOr<void> Range::setBoundary(BoundaryPoint& boundary, RefPtr<Node>& childBeforeBoundary, BoundaryPoint& otherBoundary, RefPtr<Node>& childBeforeOtherBoundary, Ref<Node>&& container, unsigned offset)
> 
> Hm... it sucks that we have to pass in 4 variables.

I did that to get rid of the the childBefore and otherBoundary helper functions. There are only two callers; I don’t think it’s so bad.

>> Source/WebCore/dom/Range.cpp:114
>> +    childBeforeBoundary = childNode.releaseReturnValue();
> 
> What if we added a helper struct like this:
> struct BoundaryPointWithChildBeforeBoundary {
>     BoundaryPoint& boundary;
>     RefPtr<Node>& childBeforeBoundary;
> };

I wouldn’t mind adding that.

>> Source/WebCore/dom/Range.cpp:117
>> +        childBeforeOtherBoundary = childBeforeBoundary;
> 
> Then this could be one liner.
> 
> But maybe it's not really worth the extra complexity / code.

No, it wouldn’t be a one-liner; can’t assign to a struct like that which contains references.

>> Source/WebCore/dom/Range.cpp:214
>> +    const BoundaryPoint* otherPoint;
> 
> Instead of computing this & other point, why don't we just call documentOrder in each case below?

Not sure it’s better, but happy to do that.

>> Source/WebCore/dom/Range.cpp:258
>> +static inline RefPtr<Node> highestAncestorUnderCommonRoot(Node& node, Node& commonRoot)
> 
> Per rule we've come up with, we don't need to return a RefPtr here.
> It's okay to return a raw pointer. It's the caller which has to store it in a Ref/RefPtr.
> But it's okay to make this return Ref/RefPtr if we want to avoid repeating makeRefPtr in every call site.

Thanks for clarifying. I will leave RefPtr here because the two places that use it would have to add a makeRefPtr otherwise.

> Source/WebCore/dom/Range.cpp:269
> +static inline RefPtr<Node> childOfCommonRootBeforeOffset(const BoundaryPoint& boundary, Node& commonRoot)

Same logic here.

>>>> Source/WebCore/dom/Range.cpp:947
>>>> +        childBeforeBoundary = nullptr;
>>> 
>>> I can remove this line of code, because it’s guaranteed that the boundary contains was a text node in this case, which means it’s already null. This is the same reason that we can use the boundary.offset, knowing it’s a character offset. So I should remove this line of code.
>> 
>> the boundary *container* was a text node
> 
> Maybe we should assert it instead?

OK.

>> Source/WebCore/dom/Range.cpp:966
>> +    ASSERT(is<Text>(oldNode.nextSibling()));
> 
> I think it's possible that oldNode doesn't have a parent here as evidenced by the assert in line 986 below.
> In fact, all these assertions seem kind of bogus as it's always possible for mutation events to have re-arranged these nodes.
> 
> Document::textNodeSplit is called too late. We need to make the adjustment before we start firing mutation events.
> Thats probably too big of a patch to do it as a part of this patch though.

Yes, this assertion is failing in the case where the old node doesn't have a parent.

As far as Document::textNodeSplit is concerned, it is *not* called too late; I researched this. It might look like it when reading the Text::splitText function, but the EventQueueScope object in that function prevents mutation events from being fired until the function is about to return, which is after textNodeSplit is called.

>> Source/WebCore/dom/Range.cpp:969
>>          unsigned splitOffset = oldNode.length();
> 
> Can we assert here that childBeforeBoundary is null?

Done.

[Darin Adler]

Created attachment 415915 [details]
Patch

[Darin Adler]

I made most of the changes Ryosuke asked for, and EWS bubbles are all green, so I think this is ready to go.

[Ryosuke Niwa]

Comment on attachment 415915 [details]
Patch

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

> Source/WebCore/dom/AbstractRange.cpp:32
> +AbstractRange::AbstractRange(SimpleRange&& range)
> +    : SimpleRange(WTFMove(range))

It seems like we can just inline this now?

> Source/WebCore/dom/AbstractRange.cpp:38
> +    return range;

Ditto.

> Source/WebCore/dom/AbstractRange.cpp:41
> -SimpleRange makeSimpleRange(const Ref<AbstractRange>& range)
> +const SimpleRange& makeSimpleRange(const Ref<AbstractRange>& range)

Ditto.

> Source/WebCore/dom/Range.cpp:131
> +    return setBoundary(start, m_childBeforeStart, end, m_childBeforeEnd, WTFMove(container), offset);

Hm... the fact SimpleRange doesn't use m_start & m_end makes this code a bit harder to parse/read.
I wonder if we should make SimpleRange a member of AbstractRange instead so that we can access these as m_range.start & m_range.end?

> Source/WebCore/dom/Range.cpp:204
> -    auto startOrdering = treeOrder(nodeRange->start, makeBoundaryPoint(m_start));
> -    auto endOrdering = treeOrder(nodeRange->end, makeBoundaryPoint(m_end));
> +    auto startOrdering = treeOrder(nodeRange->start, start);
> +    auto endOrdering = treeOrder(nodeRange->end, end);

Nice!

> Source/WebCore/dom/Range.cpp:230
> -        thisPoint = &m_start;
> -        otherPoint = &sourceRange.m_start;
> -        break;
> +        return compareBoundaryPoints(start, sourceRange.start);

This is a much cleaner code too.

> Source/WebCore/dom/Range.cpp:930
> +    if (offset + length >= boundary.offset)
> +        boundary.offset = offset;
>      else
> -        boundary.setOffset(boundaryOffset - length);
> +        boundary.offset -= length;

Hm... I wish there was some kind of validation of these boundary offsets.
Maybe we can add makeBoundaryPoint and have that function validate the offset?

> Source/WebCore/dom/Range.cpp:944
> +        boundary = { *oldNode.node().previousSibling(), boundary.offset + offset };

Here again, I wish we can assert the the offset is valid.

> Source/WebCore/dom/Range.cpp:946
> +        boundary = { *oldNode.node().previousSibling(), offset };

Ditto.

> Source/WebCore/dom/Range.cpp:969
> -                boundary.set(*oldNode.nextSibling(), boundaryOffset - splitOffset, 0);
> +                boundary = { *oldNode.nextSibling(), boundary.offset - splitOffset };

Ditto.

> Source/WebCore/dom/Range.cpp:971
> -                boundary.setOffset(splitOffset);
> +                boundary.offset = splitOffset;

Ditto.

> Source/WebCore/dom/Range.cpp:1052
> +const SimpleRange& makeSimpleRange(const Ref<Range>& range)

It seems like we can inline this now?

> Source/WebCore/dom/Range.cpp:1057
>  Optional<SimpleRange> makeSimpleRange(const RefPtr<Range>& range)

Ditto.

> Source/WebCore/dom/StaticRange.cpp:78
> +const SimpleRange& makeSimpleRange(const Ref<StaticRange>& range)

Same comment about making these inline.

> Source/WebCore/dom/StaticRange.h:-49
> -    Node& startContainer() const final { return SimpleRange::startContainer(); }

Very nice!

[Darin Adler]

Comment on attachment 415915 [details]
Patch

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

>> Source/WebCore/dom/AbstractRange.cpp:32
>> +    : SimpleRange(WTFMove(range))
> 
> It seems like we can just inline this now?

Maybe. I’d prefer to do more inlining in a separate pass, just add the inline keyword and move functions to headers. Need to be sure it’s worth it; don’t want to do it if I’m not sure it’s better.

>> Source/WebCore/dom/Range.cpp:131
>> +    return setBoundary(start, m_childBeforeStart, end, m_childBeforeEnd, WTFMove(container), offset);
> 
> Hm... the fact SimpleRange doesn't use m_start & m_end makes this code a bit harder to parse/read.
> I wonder if we should make SimpleRange a member of AbstractRange instead so that we can access these as m_range.start & m_range.end?

Yes, could do that.

>> Source/WebCore/dom/Range.cpp:930
>> +        boundary.offset -= length;
> 
> Hm... I wish there was some kind of validation of these boundary offsets.
> Maybe we can add makeBoundaryPoint and have that function validate the offset?

Could add a function that checks BoundaryPoint invariants and call it any time we modify one in code that’s supposed to only create "canonical" ones like this.

Many BoundaryPoints aren’t guaranteed to stay valid—they can contain any offset—but range endpoints are special, so maybe it should be a Range member function to check the invariants. We can call it at the ends of functions like these.

[Darin Adler]

Created attachment 416267 [details]
Patch

[Darin Adler]

Created attachment 416279 [details]
Patch

[Darin Adler]

Created attachment 416306 [details]
Patch

[Darin Adler]

Created attachment 416345 [details]
Patch

[Darin Adler]

Adding an invariant check has proven difficult. When a single composite operation like splitText happens, there are times during the processing when the invariants are not true, and they only become valid at the end. The callers don’t communicate this down through the levels to Range. I am tempted to not add it now and come back to this later.

[Ryosuke Niwa]

(In reply to Darin Adler from comment #26)
> Adding an invariant check has proven difficult. When a single composite
> operation like splitText happens, there are times during the processing when
> the invariants are not true, and they only become valid at the end. The
> callers don’t communicate this down through the levels to Range. I am
> tempted to not add it now and come back to this later.

I see. That's unfortunate but sounds too.

[Darin Adler]

Created attachment 416446 [details]
Patch

[Brent Fulgham]

It's a shame this seems to have gotten dropped!

[Darin Adler]

Not really sure this optimization will be super-successful. I dropped it because it was getting hard and I’m not sure it will pay off.