Bug 91335 – Unify HTMLCollection and DynamicNodeList

• Component: DOM
• Status: RESOLVED FIXED

[Ryosuke Niwa]

The grand unification of HTMLCollection and DynamicNodeList. In this bug, I'm going to merge item(unsigned) and length() of HTMLCollection and DynamicNodeList.

[Ryosuke Niwa]

Created attachment 152450 [details]
Patch

[Ryosuke Niwa]

This contains my patch for the bug 91334 as well. The patch becomes smaller once that's in.

[WebKit Review Bot]

Comment on attachment 152450 [details]
Patch

Attachment 152450 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/13242627

New failing tests:
jquery/manipulation.html

[WebKit Review Bot]

Created attachment 152453 [details]
Archive of layout-test-results from gce-cr-linux-01

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: gce-cr-linux-01  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.39-gcg-201203291735-x86_64-with-Ubuntu-10.04-lucid

[WebKit Review Bot]

Comment on attachment 152450 [details]
Patch

Attachment 152450 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/13243627

New failing tests:
jquery/manipulation.html

[WebKit Review Bot]

Created attachment 152455 [details]
Archive of layout-test-results from gce-cr-linux-08

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: gce-cr-linux-08  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.39-gcg-201203291735-x86_64-with-Ubuntu-10.04-lucid

[Ojan Vafai]

Comment on attachment 152450 [details]
Patch

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

> Source/WebCore/html/HTMLCollection.cpp:302
> +    if (overridesItemAfter())
> +        return static_cast<const HTMLCollection*>(this)->virtualItemAfter(offsetInArray, toElement(previous));
> +    ASSERT(!offsetInArray);
> +    return itemBeforeOrAfter<true>(previous);

Have you seen this actually matter in benchmarks or profiles? It's a lot of complexity to add if we're not sure this matters (instead of making itemAfter always be virtual).

[Ryosuke Niwa]

Comment on attachment 152450 [details]
Patch

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

>> Source/WebCore/html/HTMLCollection.cpp:302
>> +    return itemBeforeOrAfter<true>(previous);
> 
> Have you seen this actually matter in benchmarks or profiles? It's a lot of complexity to add if we're not sure this matters (instead of making itemAfter always be virtual).

Making itemAfter always virtual will actually add more complexity and make the code more fragile because:

1. itemAfter needs to take & return Node* now since childNodes can contain non-element nodes; however, some of subclasses that overrides itemAfter uses itemAfter themselves so we'll need to add a lot of toElement calls.

2. Before this patch, itemAfter was always virtual. However, subclasses had to tell HTMLCollection whether it supports itemBefore (only HTMLCollection itself provides one) or not. And subclasses passed in a wrong value, it still worked when HTMLCollection was traversed forwards but hit assertions when traversed backwards. After this patch, neither forwards nor backwards traversal works if it didn't give HTMLCollection the right value.

[Ojan Vafai]

Comment on attachment 152450 [details]
Patch

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

>>> Source/WebCore/html/HTMLCollection.cpp:302
>>> +    return itemBeforeOrAfter<true>(previous);
>> 
>> Have you seen this actually matter in benchmarks or profiles? It's a lot of complexity to add if we're not sure this matters (instead of making itemAfter always be virtual).
> 
> Making itemAfter always virtual will actually add more complexity and make the code more fragile because:
> 
> 1. itemAfter needs to take & return Node* now since childNodes can contain non-element nodes; however, some of subclasses that overrides itemAfter uses itemAfter themselves so we'll need to add a lot of toElement calls.
> 
> 2. Before this patch, itemAfter was always virtual. However, subclasses had to tell HTMLCollection whether it supports itemBefore (only HTMLCollection itself provides one) or not. And subclasses passed in a wrong value, it still worked when HTMLCollection was traversed forwards but hit assertions when traversed backwards. After this patch, neither forwards nor backwards traversal works if it didn't give HTMLCollection the right value.

I see. Your ChangeLog description says that this is for performance. I think the name is confusing though. How about the following changes?
1. s/virtualItemAfter/elementAfter/
2. s/overridesItemAfter/isListOfElements/

I think that would make most of the code make more sense to me. It makes HTMLCollection::item a tad bit more confusing, but I think it's worth the clarity elsewhere in the code.

Or are there HTMLCollections that are lists of Elements and don't override itemAfter?

[Ryosuke Niwa]

Unfortunately there are HTMLCollections that contain only elements and don't use elements array but still override itemAfter.

Maybe itemElementAfter and ProvideItemElementAfter?

[Ryosuke Niwa]

Created attachment 152474 [details]
Patch

[Ryosuke Niwa]

I can't reproduce jquery/manipulation.html failure on mac port or chromium mac port.

[WebKit Review Bot]

Comment on attachment 152474 [details]
Patch

Attachment 152474 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/13233869

New failing tests:
jquery/manipulation.html

[WebKit Review Bot]

Created attachment 152483 [details]
Archive of layout-test-results from gce-cr-linux-07

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: gce-cr-linux-07  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.39-gcg-201203291735-x86_64-with-Ubuntu-10.04-lucid

[Ojan Vafai]

Comment on attachment 152474 [details]
Patch

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

> Source/WebCore/html/HTMLCollection.cpp:370
> +    if (isLengthCacheValid() && !overridesItemAfter() && isLastItemCloserThanLastOrCachedItem(offset)) {

Is the plan for the rest of the collections to implement itemBefore? If so, I think that would make this code make a lot more sense to me. As it is, overridesItemAfter is serving multiple purposes and it makes the code very convoluted.

[Ojan Vafai]

(In reply to comment #10)
> Unfortunately there are HTMLCollections that contain only elements and don't use elements array but still override itemAfter.
> 
> Maybe itemElementAfter and ProvideItemElementAfter?

I'd prefer elementAfter and ProvidesElementAfter.

Can you put elementAfter as a virtual on DynamicNodeListCacheBase and have DynamicNodeListCacheBase::itemAfter be something like:
if (Element* element = elementAfter(...))
    return element;
ASSERT(!offsetInArray);
return itemBeforeOrAfter<true>(previous);

Then you don't need ProvidesElementAfter. I understand it's adding a virtual function call, but I think we should try it and see if the performance is a problem.

I think this patch as is makes the code very confusing.

[Ryosuke Niwa]

(In reply to comment #16)
> (In reply to comment #10)
> > Unfortunately there are HTMLCollections that contain only elements and don't use elements array but still override itemAfter.
> > 
> > Maybe itemElementAfter and ProvideItemElementAfter?
> 
> I'd prefer elementAfter and ProvidesElementAfter.

That's very cumbersome because HTMLPropertiesCollection can contain multiple items inside each element in the elementsArray.

> Can you put elementAfter as a virtual on DynamicNodeListCacheBase and have DynamicNodeListCacheBase::itemAfter be something like:
> if (Element* element = elementAfter(...))
>     return element;
> ASSERT(!offsetInArray);
> return itemBeforeOrAfter<true>(previous);
> 
> Then you don't need ProvidesElementAfter. I understand it's adding a virtual function call, but I think we should try it and see if the performance is a problem.

No, we can't afford to do that. Furthermore, that'll add one more vtable pointer because DynamicNodeList inherits from both NodeList and DynamicNodeListCacheBase. And no, DynamicNodeListCacheBase can't inherit from NodeList because HTMLCollection is not a NodeList.

[Ryosuke Niwa]

(In reply to comment #16)
>
> Can you put elementAfter as a virtual on DynamicNodeListCacheBase and have DynamicNodeListCacheBase::itemAfter be something like:
> if (Element* element = elementAfter(...))
>     return element;
> ASSERT(!offsetInArray);
> return itemBeforeOrAfter<true>(previous);

Also, this is semantically wrong. This change would force HTMLCollections that provide elementAfter to call both elementAfter and itemBeforeOrAfter<true>(previous) when there are items left. We'll then have to either iterate DOM twice or add a special branching at the beginning of itemBeforeOrAfter, which is added complexity and unnecessary runtime cost.

[Ryosuke Niwa]

I have the exact same patch on https://bugs.webkit.org/show_bug.cgi?id=91413 with a slight modification to jquery/manipulation.html to diagnose the issue. The cr-linux EWS passed. I have no idea what the heck is going on there. I'm just going to ignore cr-linux EWS for now.

Adam & Eric, it seems like EWS cr-linux has been very unreliable on this particular patch.

[Ryosuke Niwa]

Created attachment 152838 [details]
Patch

[Ryosuke Niwa]

Created attachment 153071 [details]
Fixed perf. regression

[Ryosuke Niwa]

Created attachment 153072 [details]
childNodes perf test

Fixed the perf. regression I saw on this test. In old versions of this patch, the performance regressed as much as 100%.

[WebKit Review Bot]

Attachment 153071 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1
Source/WebCore/html/HTMLCollection.cpp:258:  An else statement can be removed when the prior "if" concludes with a return, break, continue or goto statement.  [readability/control_flow] [4]
Total errors found: 1 in 24 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Ryosuke Niwa]

Committed r123281: <http://trac.webkit.org/changeset/123281>

[Csaba Osztrogonác]

(In reply to comment #24)
> Committed r123281: <http://trac.webkit.org/changeset/123281>

It made 2 tests timeout on the perf bots. I filed a new bug report to
fix this regression: https://bugs.webkit.org/show_bug.cgi?id=91980

Could you check what happened?

[Vsevolod Vlasov]

(In reply to comment #24)
> Committed r123281: <http://trac.webkit.org/changeset/123281>

This caused a regression: https://bugs.webkit.org/show_bug.cgi?id=92104

TL;DR 
table.childNodes[table.childNodes.length - 1] returns incorrect value.