Bug 105324 – Use ElementTraversal in LiveNodeListBase

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Antti Koivisto]

We should use ElementTraversal when traversing elements.

[Antti Koivisto]

Created attachment 179980 [details]
patch

[WebKit Review Bot]

Attachment 179980 [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:316:  The parameter name "nodeList" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/WebCore/html/HTMLCollection.cpp:316:  The parameter name "element" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/WebCore/dom/TagNodeList.h:39:  Missing space after ,  [whitespace/comma] [3]
Source/WebCore/dom/TagNodeList.h:51:  The parameter name "type" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/WebCore/html/HTMLCollection.h:67:  Extra space before last semicolon. If this should be an empty statement, use { } instead.  [whitespace/semicolon] [5]
Total errors found: 5 in 11 files


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

[Antti Koivisto]

Created attachment 179981 [details]
with less style errors

[Ryosuke Niwa]

Comment on attachment 179980 [details]
patch

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

> Source/WebCore/ChangeLog:9
> +        

Leading whitespace.

> Source/WebCore/ChangeLog:11
> +        

Ditto.

> Source/WebCore/ChangeLog:13
> +        

Ditto.

> Source/WebCore/ChangeLog:21
> +        

Ditto for the rest of the change log entry.

> Source/WebCore/ChangeLog:27
> +            Root is always ContainerNode if the list has anything in it. Traversal functions are slightly more

Root is always ContainerNode. period. We only instantiate LiveNodeListBase on Document or Element.

> Source/WebCore/dom/LiveNodeList.cpp:59
> +    if (!rootNode->isContainerNode())
> +        return 0;

I don't think this can ever occur. m_ownerNode is always element or document, and root node can only be m_ownerNode or its ancestor.

> Source/WebCore/dom/TagNodeList.h:45
> -            return adoptRef(new TagNodeList(rootNode, starAtom, localName));
> +            return adoptRef(new TagNodeList(rootNode, TagNodeListType, starAtom, localName));

You can just pass in type here.

> Source/WebCore/html/HTMLCollection.cpp:382
> +    if (type() == HTMLTagNodeListType)
> +        return firstMatchingElement(static_cast<const HTMLTagNodeList*>(this), root);
> +    if (type() == ClassNodeListType)
> +        return firstMatchingElement(static_cast<const ClassNodeList*>(this), root);

So the reason you're cherry-picking these is because they're most frequently used?
Why don't we just special-case ChildNodeListType and then handle the rest in isAcceptableElement instead? There isn't really a point in differentiating NodeList and HTMLCollection here.

> Source/WebCore/html/HTMLCollection.cpp:470
> +    ContainerNode* root = rootContainerNode();
> +    if (!root) {
> +        setLengthCache(0);
> +        return 0;
> +    }

It's really strange that rootContainerNode could ever return 0. Do you recall when that happened?
We probably need to fix that bug first.

> Source/WebCore/html/HTMLCollection.cpp:522
> +        currentItem = traverseForwardToOffset(offset, currentItem, currentOffset, root);
> +    else
> +        currentItem = static_cast<const HTMLCollection*>(this)->traverseForwardToOffset(offset, toElement(currentItem), currentOffset, offsetInArray, root);

Note that we know currentOffset != offset at this point.

> Source/WebCore/html/HTMLCollection.cpp:584
> +        offsetInArray = m_cachedElementsArrayOffset;
> +        while (currentOffset != offset && (currentElement = virtualItemAfter(offsetInArray, currentElement)))
> +            ++currentOffset;

This doesn't seem right virtualItemAfter needs to update m_cachedElementsArrayOffset. You probably need to enable microdata in order to test this change.

[Ryosuke Niwa]

(In reply to comment #4)
> (From update of attachment 179980 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=179980&action=review
>
> > Source/WebCore/html/HTMLCollection.cpp:584
> > +        offsetInArray = m_cachedElementsArrayOffset;
> > +        while (currentOffset != offset && (currentElement = virtualItemAfter(offsetInArray, currentElement)))
> > +            ++currentOffset;
> 
> This doesn't seem right virtualItemAfter needs to update m_cachedElementsArrayOffset. You probably need to enable microdata in order to test this change.

Forget about this comment. I misread your code.

[WebKit Review Bot]

Comment on attachment 179981 [details]
with less style errors

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

New failing tests:
fast/forms/form-collection-radio-node-list.html
fast/forms/fieldset/fieldset-elements.html
inspector-protocol/debugger-terminate-dedicated-worker-while-paused.html
fast/forms/fieldset/fieldset-form-collection-radionode-list.html
inspector/console/console-format-collections.html
dom/html/level2/html/HTMLFormElement01.html
fast/forms/formmove.html
fast/forms/elements-invalidate-on-form-attribute-invalidation.html
fast/forms/update-form-attribute-element.html
fast/dom/HTMLFormElement/elements-not-in-document.html
fast/forms/form-collection-elements-order.html
fast/forms/button-in-forms-collection.html
fast/forms/element-order.html
dom/xhtml/level2/html/HTMLFormElement01.xhtml
fast/forms/form-collection-elements.html
fast/dom/html-collections-named-getter.html
fast/forms/form-attribute-elements.html
fast/forms/formmove2.html
jquery/traversing.html

[Antti Koivisto]

(In reply to comment #4)
> Root is always ContainerNode. period. We only instantiate LiveNodeListBase on Document or Element.

This is not true. At least Text.childNodes will have Text as root. It would be better handled elsewhere but that is out of scope of this patch.

[Ryosuke Niwa]

(In reply to comment #7)
> (In reply to comment #4)
> > Root is always ContainerNode. period. We only instantiate LiveNodeListBase on Document or Element.
> 
> This is not true. At least Text.childNodes will have Text as root. It would be better handled elsewhere but that is out of scope of this patch.

Right, we discussed this on IRC. We definitely need to make this saner at some point though.

[Antti Koivisto]

Created attachment 180186 [details]
patch3

Some changes as discussed with Ryosuke

- removed isAcceptableElement(), always use isMatchingElement templates instead
- separated ChildNodeList iteration function. It is the only one that operates on Nodes instead of Elements.
- bring back the accidentally removed ALWAYS_INLINEs for the backwards case

Also made it less buggy.

[Ryosuke Niwa]

Comment on attachment 180186 [details]
patch3

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

> Source/WebCore/dom/LiveNodeList.cpp:57
> +    Node* rootNode = this->rootNode();

Do we need "this->"?

> Source/WebCore/html/HTMLCollection.cpp:204
> +template <> inline bool isMatchingElement(const HTMLCollection* htmlCollection, Element* element)

Nice! It might make sense to specialize this function further for common html collections like element.children & document.all (of course in a follow up patch).

> Source/WebCore/html/HTMLCollection.cpp:277
> +template <> inline bool isMatchingElement(const HTMLTagNodeList* nodeList, Element* element)
> +{
> +    return nodeList->nodeMatchesInlined(element);
> +}

Would it make sense to define this specialization in TagNodeList.h instead? (No need to do this in this patch).

> Source/WebCore/html/HTMLCollection.cpp:327
>      if (isNodeList(type()) && shouldOnlyIncludeDirectChildren()) // ChildNodeList

Can we change this to type() == ChildNodeList? If not, I'll do that.

> Source/WebCore/html/HTMLCollection.cpp:371
> +    while (currentOffset != offset && (currentElement = nextMatchingElement(nodeList, currentElement, root)))

Can we assert that ASSERT(currentOffset < offset); at the beginning?

> Source/WebCore/html/HTMLCollection.cpp:380
> +    ASSERT(!overridesItemAfter());

I don't think this assertion is useful given that we're already asserting type() is ChildNodeListType since only HTMLCollection overrides itemAfter.

> Source/WebCore/html/HTMLCollection.cpp:381
> +    while (currentOffset != offset && (currentNode = currentNode->nextSibling()))

Ditto about asserting currentOffset < offset.

> Source/WebCore/html/HTMLCollection.cpp:528
> +    if (type() == ChildNodeListType) {
> +        currentItem = traverseChildNodeListForwardToOffset(offset, currentItem, currentOffset);
> +    } else if (isNodeList(type()))

Nit: We don't need curly brackets here.

> Source/WebCore/html/HTMLCollection.cpp:579
> +    if (overridesItemAfter())

We can add UNLIKELY here as well although I don't think it'll matter.

> Source/WebCore/html/HTMLCollection.cpp:583
> +    if (shouldOnlyIncludeDirectChildren())
> +        return firstMatchingChildElement(static_cast<const HTMLCollection*>(this), root);

It'll be nice if we could merge this code with childNodes somehow.

> Source/WebCore/html/HTMLCollection.cpp:601
> +    if (overridesItemAfter()) {

UNLIKELY?

[Antti Koivisto]

http://trac.webkit.org/changeset/138195

[Antti Koivisto]

(In reply to comment #10)
> Do we need "this->"?

Yeah, the local variable hides the function.

> Can we change this to type() == ChildNodeList? If not, I'll do that.

Done. 

> Can we assert that ASSERT(currentOffset < offset); at the beginning?

Did these.

> > +    ASSERT(!overridesItemAfter());
> 
> I don't think this assertion is useful given that we're already asserting type() is ChildNodeListType since only HTMLCollection overrides itemAfter.

Removed.

> We can add UNLIKELY here as well although I don't think it'll matter.

Removed the remaining UNLIKELY. Since the branches are now outside of loops, they are unlikely to make a difference.

[Antti Koivisto]

Looks like this was ~15% progression in DOM/GridSort and ~3% progression in DOM/DOMDivWalk:

http://webkit-perf.appspot.com/graph.html#tests=[[9106,2001,32196],[6104,2001,32196]]&sel=none&displayrange=7&datatype=running

[Antoine Quint]

This changed caused https://bugs.webkit.org/show_bug.cgi?id=117836.

[Antoine Quint]

(In reply to comment #14)
> This changed caused https://bugs.webkit.org/show_bug.cgi?id=117836.

Except it didn't, it was actually the change for http://webkit.org/b/115584. Sorry for the noise.