Bug 136719 - Avoid redundant isElementNode() checks in Traversal<HTML*Element> / Traversal<SVG*Element>
Summary: Avoid redundant isElementNode() checks in Traversal<HTML*Element> / Traversal...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Chris Dumez
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-09-10 15:31 PDT by Chris Dumez
Modified: 2014-09-15 08:59 PDT (History)
5 users (show)

See Also:


Attachments
Patch (25.76 KB, patch)
2014-09-11 10:07 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (27.24 KB, patch)
2014-09-11 12:01 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (27.24 KB, patch)
2014-09-11 12:24 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (26.83 KB, patch)
2014-09-14 18:32 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (26.62 KB, patch)
2014-09-15 07:54 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (26.75 KB, patch)
2014-09-15 08:14 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Chris Dumez 2014-09-10 15:31:50 PDT
Avoid redundant isElementNode() checks in Traversal<HTML*Element> / Traversal<SVG*Element>.  We used to iterate through Elements, and then call isElementOfType<HTML*Element>()  on each Element. This made sense because hasTagName() used to be defined on Element. However, after http://trac.webkit.org/changeset/165699, hasTagName() is now defined on Node for HTMLQualifiedName / SVGQualifiedName.

Node::hasTagName(HTMLQualifiedName) basically does the following check "isHTMLElement() &&  toHTMLElement(*this).hasTagName(tagName)". As a consequence, doing an isElementNode() check is now redundant as isHTMLElement() is defined on Node.

This patch adds isElementOfType<ElementType>(Node) helper functions and updates Traversal<ElementType> so that the methods use NodeTraversal internally instead of Traversal<ElementType>. As a result, we now iterate over Nodes (not Elements) and call the new isElementOfType<ElementType>(Node) helpers (which are efficient after r165699).

Before the patch, the code ended up doing the following checks for Traversal<HTML*element>:
node.isElementNode() && toElement(node).isHTMLElement() && toHTMLElement(node).hasTagName(HTMLNames::fooTag)

After the patch, the code only does:
node.isHTMLElement() && toHTMLElement(node).hasTagName(HTMLNames::fooTag)

As an example, here is the assembly diff on HTMLFiedSetElement::updateFromControlElementsAncestorDisabledStateUnder(), which uses Traversal<HTMLFormControlElement> API:
http://pastebin.com/zyJ3kymP

For the HTMLFieldSetElement.o object file, the overall number of asm lines goes down by 90 (out of 842).
Comment 1 Chris Dumez 2014-09-11 10:07:14 PDT
Created attachment 237959 [details]
Patch
Comment 2 Chris Dumez 2014-09-11 12:01:10 PDT
Created attachment 237972 [details]
Patch
Comment 3 Chris Dumez 2014-09-11 12:24:51 PDT
Created attachment 237977 [details]
Patch
Comment 4 Darin Adler 2014-09-11 18:38:51 PDT
I suspect there is a better way to do this with a far smaller patch. Let me think about it.
Comment 5 Darin Adler 2014-09-14 12:53:23 PDT
Comment on attachment 237977 [details]
Patch

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

I think we don’t need multiple function templates when the isXXX function is already overloaded for all the types we care about. It would be nice to keep the explicit mention of Node to a minimum.

> Source/WebCore/ChangeLog:41
> +        Add new isElementOfType() helper taking a Node in argument.

I don’t understand why we need this. It seems like a step in the wrong direction. One of the main reasons we have these helpers is to create a future where we code in terms of Element and not Node.

Is there a way to accomplish everything else without adding all these Node overloads in all the files?

I understand that somehow we want to express generically that checking isHTMLElement also implicitly checks isElement and avoid a second check. Is there some other way to do this?

> Source/WebCore/html/HTMLFormControlElement.h:197
>  inline bool isHTMLFormControlElement(const Element& element) { return element.isFormControlElement(); }
>  inline bool isHTMLFormControlElement(const Node& node) { return node.isElementNode() && toElement(node).isFormControlElement(); }
> +template <> inline bool isElementOfType<const HTMLFormControlElement>(const Node& node) { return isHTMLFormControlElement(node); }
>  template <> inline bool isElementOfType<const HTMLFormControlElement>(const Element& element) { return isHTMLFormControlElement(element); }

Node should come after Element to match the code above, which goes from more specific to more general.

Can this be a single template rather than two functions? The argument type would need to be a template argument, but we wouldn’t have to specify Element and Node.

> Source/WebCore/html/HTMLFrameElementBase.h:81
> +inline bool isHTMLFrameElementBase(const HTMLElement& element) { return isHTMLFrameElement(element) || isHTMLIFrameElement(element); }
> +inline bool isHTMLFrameElementBase(const Node& node) { return isHTMLFrameElement(node) || isHTMLIFrameElement(node); }

Can this be a single template rather than two functions? The argument type would need to be a template argument, but we wouldn’t have to specify HTMLElement and Node.

> Source/WebCore/html/HTMLMediaElement.h:920
>  void isHTMLMediaElement(const HTMLMediaElement&); // Catch unnecessary runtime check of type known at compile time.
>  inline bool isHTMLMediaElement(const Element& element) { return element.isMediaElement(); }
>  inline bool isHTMLMediaElement(const Node& node) { return node.isElementNode() && toElement(node).isMediaElement(); }
> -template <> inline bool isElementOfType<const HTMLMediaElement>(const Element& element) { return element.isMediaElement(); }
> +template <> inline bool isElementOfType<const HTMLMediaElement>(const Node& node) { return isHTMLMediaElement(node); }
> +template <> inline bool isElementOfType<const HTMLMediaElement>(const Element& element) { return isHTMLMediaElement(element); }

Node should come after Element to match the code above, which goes from more specific to more general.

But can this be a single template rather than two functions? The argument type would need to be a template argument, but we wouldn’t have to specify Element and Node.

> Source/WebCore/html/LabelableElement.h:57
> -template <> inline bool isElementOfType<const LabelableElement>(const Element& element) { return isLabelableElement(element); }
> +template <> inline bool isElementOfType<const LabelableElement>(const HTMLElement& element) { return isLabelableElement(element); }
> +template <> inline bool isElementOfType<const LabelableElement>(const Node& node) { return isLabelableElement(node); }

Can this be a single template rather than two functions? The argument type would need to be a template argument, but we wouldn’t have to specify HTMLElement and Node.

> Source/WebCore/mathml/MathMLElement.h:82
>  inline bool isMathMLElement(const Node& node) { return node.isMathMLElement(); }
>  NODE_TYPE_CASTS(MathMLElement)
>  
> +template <typename T> bool isElementOfType(const MathMLElement&);
> +template <> inline bool isElementOfType<const MathMLElement>(const Node& node) { return node.isMathMLElement(); }
> +template <> inline bool isElementOfType<const MathMLElement>(const MathMLElement&) { return true; }

Node should come after MathMLElement to match the code above, which goes from specific to general. This should also come before the NODE_TYPE_CASTS macro to match the other files.

> Source/WebCore/svg/SVGElement.h:230
> -template <> inline bool isElementOfType<const SVGElement>(const Element& element) { return element.isSVGElement(); }
> +template <typename T> bool isElementOfType(const SVGElement&);
> +template <> inline bool isElementOfType<const SVGElement>(const Node& node) { return node.isSVGElement(); }
> +template <> inline bool isElementOfType<const SVGElement>(const SVGElement&) { return true; }

Node should come after SVGElement to match the code above, which goes from more specific to more general.

> Source/WebCore/svg/SVGFilterPrimitiveStandardAttributes.h:89
> +template <> inline bool isElementOfType<const SVGFilterPrimitiveStandardAttributes>(const SVGElement& element) { return isSVGFilterPrimitiveStandardAttributes(element); }
> +template <> inline bool isElementOfType<const SVGFilterPrimitiveStandardAttributes>(const Node& node) { return isSVGFilterPrimitiveStandardAttributes(node); }

Can this be a single template rather than two functions? The argument type would need to be a template argument, but we wouldn’t have to specify SVGElement and Node.

> Source/WebCore/svg/animation/SVGSMILElement.h:244
> +template <> inline bool isElementOfType<const SVGSMILElement>(const SVGElement& element) { return isSVGSMILElement(element); }
> +template <> inline bool isElementOfType<const SVGSMILElement>(const Node& node) { return isSVGSMILElement(node); }

Can this be a single template rather than two specializations? The argument type would need to be a template argument, but we wouldn’t have to specify HTMLElement and Node.
Comment 6 Chris Dumez 2014-09-14 14:54:51 PDT
Comment on attachment 237977 [details]
Patch

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

>> Source/WebCore/ChangeLog:41
>> +        Add new isElementOfType() helper taking a Node in argument.
> 
> I don’t understand why we need this. It seems like a step in the wrong direction. One of the main reasons we have these helpers is to create a future where we code in terms of Element and not Node.
> 
> Is there a way to accomplish everything else without adding all these Node overloads in all the files?
> 
> I understand that somehow we want to express generically that checking isHTMLElement also implicitly checks isElement and avoid a second check. Is there some other way to do this?

Yes, there is now an overload of isElementOfType() taking a Node in argument. The thing is that isElementOfType() is never called explicitly by developers, it is only called internally in our fancy traversal APIs (i.e. Traversal<*Element>, childrenOfType(), ...). So developers still very much code in terms of Elements and not Nodes. The only thing is that the Traversal API now uses NodeTraversal *internally* instead of ElementTraversal to bypass the isElementNode() check and call Node::hasTagName(HTMLQualifiedName) directly.

>> Source/WebCore/html/HTMLFormControlElement.h:197
>>  template <> inline bool isElementOfType<const HTMLFormControlElement>(const Element& element) { return isHTMLFormControlElement(element); }
> 
> Node should come after Element to match the code above, which goes from more specific to more general.
> 
> Can this be a single template rather than two functions? The argument type would need to be a template argument, but we wouldn’t have to specify Element and Node.

Yes, it sounds like your proposal would work and would avoid having 2 functions. I'll give it a try and verify the impact on binary size to be sure.
Comment 7 Chris Dumez 2014-09-14 18:32:09 PDT
Created attachment 238098 [details]
Patch
Comment 8 Chris Dumez 2014-09-14 18:34:44 PDT
Comment on attachment 237977 [details]
Patch

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

Please take another look as the change was not trivial.

>>> Source/WebCore/html/HTMLFormControlElement.h:197
>>>  template <> inline bool isElementOfType<const HTMLFormControlElement>(const Element& element) { return isHTMLFormControlElement(element); }
>> 
>> Node should come after Element to match the code above, which goes from more specific to more general.
>> 
>> Can this be a single template rather than two functions? The argument type would need to be a template argument, but we wouldn’t have to specify Element and Node.
> 
> Yes, it sounds like your proposal would work and would avoid having 2 functions. I'll give it a try and verify the impact on binary size to be sure.

Done. However, since C++ does not support function template partial specialization, I had to introduce an IsElementOfType functor (isElementOfType() calls that functor so there is no need to update the call sites).
Comment 9 Darin Adler 2014-09-14 22:12:16 PDT
Comment on attachment 238098 [details]
Patch

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

> Source/WebCore/dom/Element.h:675
> +    bool operator()(ArgType&);

I’m not sure we should use operator() rather than a named function for this. I would think I would name the struct ElementTypeCastTraits and name the function “is”.

> Source/WebCore/dom/Element.h:680
> +inline bool isElementOfType(const ArgType& node) { return IsElementOfType<ExpectedType, const ArgType>()(node); }

Seems like we could omit both “const” here.

> Source/WebCore/html/HTMLElement.h:155
> +template <typename ArgType>
> +struct IsElementOfType<const HTMLElement, ArgType> {
> +    bool operator()(ArgType& node) { return isHTMLElement(node); }
> +};

Since the entire template now is the same for every class except for the class name, maybe we can make the NODE_TYPE_CASTS macro generate this instead of having to repeat it in every source file, or have a variant on NODE_TYPE_CASTS that does it.
Comment 10 WebKit Commit Bot 2014-09-14 22:13:45 PDT
Comment on attachment 238098 [details]
Patch

Rejecting attachment 238098 [details] from commit-queue.

Failed to run "['/Volumes/Data/EWS/WebKit/Tools/Scripts/webkit-patch', '--status-host=webkit-queues.appspot.com', '--bot-id=webkit-cq-02', 'apply-attachment', '--no-update', '--non-interactive', 238098, '--port=mac']" exit_code: 2 cwd: /Volumes/Data/EWS/WebKit

Last 500 characters of output:
/WebCore/html/HTMLMediaElement.h
patching file Source/WebCore/html/HTMLPlugInImageElement.h
patching file Source/WebCore/html/LabelableElement.h
patching file Source/WebCore/mathml/MathMLElement.h
patching file Source/WebCore/svg/SVGElement.h
patching file Source/WebCore/svg/SVGFilterPrimitiveStandardAttributes.h
patching file Source/WebCore/svg/animation/SVGSMILElement.h

Failed to run "[u'/Volumes/Data/EWS/WebKit/Tools/Scripts/svn-apply', '--force']" exit_code: 1 cwd: /Volumes/Data/EWS/WebKit

Full output: http://webkit-queues.appspot.com/results/6358717847044096
Comment 11 Antti Koivisto 2014-09-14 23:22:47 PDT
Comment on attachment 238098 [details]
Patch

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

> Source/WebCore/ChangeLog:3
> +        Avoid redundant isElementNode() checks in Traversal<HTML*Element> / Traversal<SVG*Element>

Note that Traversal<> template is obsolete and all clients should use element iterators instead. The iterators are still implemented in terms of Traversal<> so improving it is useful. However it should really be considered an implementation detail of the iterators and should probably be made more so (via naming or actually moving the code to the iterators).
Comment 12 Chris Dumez 2014-09-15 07:48:45 PDT
Comment on attachment 238098 [details]
Patch

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

>> Source/WebCore/ChangeLog:3
>> +        Avoid redundant isElementNode() checks in Traversal<HTML*Element> / Traversal<SVG*Element>
> 
> Note that Traversal<> template is obsolete and all clients should use element iterators instead. The iterators are still implemented in terms of Traversal<> so improving it is useful. However it should really be considered an implementation detail of the iterators and should probably be made more so (via naming or actually moving the code to the iterators).

Understood, thanks for the information Antti.

>> Source/WebCore/dom/Element.h:680
>> +inline bool isElementOfType(const ArgType& node) { return IsElementOfType<ExpectedType, const ArgType>()(node); }
> 
> Seems like we could omit both “const” here.

Actually, it did not build otherwise. isElementOfType() is sometimes called with a non-const argument and thus, the compiler complains about IsElementOfType<ExpectedType, NonConstType> not being defined.

>> Source/WebCore/html/HTMLElement.h:155
>> +};
> 
> Since the entire template now is the same for every class except for the class name, maybe we can make the NODE_TYPE_CASTS macro generate this instead of having to repeat it in every source file, or have a variant on NODE_TYPE_CASTS that does it.

Yes, I'll look into this in a follow-up patch.
Comment 13 Chris Dumez 2014-09-15 07:54:15 PDT
Created attachment 238128 [details]
Patch
Comment 14 Chris Dumez 2014-09-15 08:06:14 PDT
Comment on attachment 238128 [details]
Patch

Will stop using a Functor as suggested by Darin and reupload.
Comment 15 Chris Dumez 2014-09-15 08:14:52 PDT
Created attachment 238129 [details]
Patch
Comment 16 Chris Dumez 2014-09-15 08:16:25 PDT
Comment on attachment 238098 [details]
Patch

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

>> Source/WebCore/dom/Element.h:675
>> +    bool operator()(ArgType&);
> 
> I’m not sure we should use operator() rather than a named function for this. I would think I would name the struct ElementTypeCastTraits and name the function “is”.

Done.
Comment 17 WebKit Commit Bot 2014-09-15 08:59:52 PDT
Comment on attachment 238129 [details]
Patch

Clearing flags on attachment: 238129

Committed r173622: <http://trac.webkit.org/changeset/173622>
Comment 18 WebKit Commit Bot 2014-09-15 08:59:57 PDT
All reviewed patches have been landed.  Closing bug.