Bug 59812 – Refactor DOM tree traversal methods

• Status: RESOLVED
• Resolution: INVALID
• Component: DOM

[Roland Steiner]

Currently we have a slew of methods to climb the DOM tree in conjunction with shadow trees that should be pruned down: parent(), parentNode(), parentOrHostNode(), parentNodeGuaranteedHostFree(), shadowAncestorNode(), shadowTreeRootNode()...

Conceptually we only need:

Node
    parent()
    treeScope()

Element
    shadowRoot()

ShadowRoot
    shadowHost()

[Roland Steiner]

ShadowRoot
    parentTreeScope()

is also needed.

[Dimitri Glazkov (Google)]

htmlediting is a great place to fish for those.

[Dominic Cooney]

Per the discussion in bug 54441 we should consider broadening the scope of this bug to not just simplify the number of accessors but provide traversals to simplify the actual uses of these.

[Roland Steiner]

(In reply to comment #3)
> Per the discussion in bug 54441 we should consider broadening the scope of this bug to not just simplify the number of accessors but provide traversals to simplify the actual uses of these.

IMHO refactoring more complex traversal methods (such as the Node::traverse...() functions) as discussed in bug 54441 is IMHO a separate and orthogonal issue from paring down the accessors as described here (and therefore should be different bug entries).

[Hayato Ito]

Created attachment 94179 [details]
WIP - add universalTraverseNextNode

[Hayato Ito]

Let me share my patch (work in progress). I am trying to add a new traverseNode family, which traverses also into a shadow dom and a document in a frame element.

That function will be used in implementing a tab traversal.
The function name is a tentative name.  I'll try to implement a tab traversal using this function.

Maybe I should file a new bug entry for this patch.

(In reply to comment #5)
> Created an attachment (id=94179) [details]
> WIP - add universalTraverseNextNode

[Roland Steiner]

Comment on attachment 94179 [details]
WIP - add universalTraverseNextNode

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

Refering to the discussion in bug 54441, given that the functionality is getting rather complex and specific I'd also vote to move this into a separate class - or perhaps template that takes a traversal strategy trait (?).

> Source/WebCore/dom/Node.cpp:1143
> +    if (renderer() && renderer()->isTextControl()) {

Once the conversion to new-style shadow DOM is finished, this shouldn't be necessary anymore :)

> Source/WebCore/dom/Node.cpp:1149
> +        return firstChild();

The code traverses first the shadow DOM, then the "light" DOM children. For tab traversal it may be necessary to consider the order of <content> elements in the shadow DOM instead - i.e., jump to the appropriate light DOM child(ren) from the shadow DOM <content> node(s).

> Source/WebCore/dom/Node.cpp:2563
> +void Node::showTreeAndMarkDeeply(const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char* markedLabel2) const

Isn't the declaration for this function missing in the header file?

[Hayato Ito]

Thank you for the review.

(In reply to comment #7)
> (From update of attachment 94179 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=94179&action=review
> 
> Refering to the discussion in bug 54441, given that the functionality is getting rather complex and specific I'd also vote to move this into a separate class - or perhaps template that takes a traversal strategy trait (?).

Yeah, I am not sure whether this functionality should belong to a Node class or not. Maybe I'll move that to FocusController class or other suitable locations. But I haven't decided yet where we should have it.

A traversal strategy trait sounds nice, but we should be careful to implement a such a trait, which should not cause any performance impacts to existing traverseXXX functions. I don't have a clear idea about it as of now.

> 
> > Source/WebCore/dom/Node.cpp:1143
> > +    if (renderer() && renderer()->isTextControl()) {
> 
> Once the conversion to new-style shadow DOM is finished, this shouldn't be necessary anymore :)

Thank you for the info. I am assuming that we should have it as of now :)

> 
> > Source/WebCore/dom/Node.cpp:1149
> > +        return firstChild();
> 
> The code traverses first the shadow DOM, then the "light" DOM children. For tab traversal it may be necessary to consider the order of <content> elements in the shadow DOM instead - i.e., jump to the appropriate light DOM child(ren) from the shadow DOM <content> node(s).

Nice point. Let me implement that in a next patch.

> 
> > Source/WebCore/dom/Node.cpp:2563
> > +void Node::showTreeAndMarkDeeply(const Node* markedNode1, const char* markedLabel1, const Node* markedNode2, const char* markedLabel2) const
> 
> Isn't the declaration for this function missing in the header file?

True. I'll address it.

[Dimitri Glazkov (Google)]

Comment on attachment 94179 [details]
WIP - add universalTraverseNextNode

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

> Source/WebCore/dom/Node.cpp:2541
> +void Node::showTreeForThisDeeply() const

Deeply sounds like a wrong word. What are you trying to communicate here?

[Ryosuke Niwa]

Comment on attachment 94179 [details]
WIP - add universalTraverseNextNode

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

> Source/WebCore/dom/Node.cpp:1137
> +Node* Node::traverseNextNodeConsideringFrameAndShadow() const

Considering frame and shadow sound misleading because we certainly consider the existence of frame and shadow whenever we traverse nodes.

Maybe traverseNextNodeAcrossFrameAndShadow?

> Source/WebCore/dom/Node.cpp:1142
> +    if (shadowRoot(this))
> +        return shadowRoot(this)->traverseNextNodeConsideringFrameAndShadow();

I would have saved the shadowRoot as a pointer here to avoid accessing rare data twice.

>>> Source/WebCore/dom/Node.cpp:1143
>>> +    if (renderer() && renderer()->isTextControl()) {
>> 
>> Once the conversion to new-style shadow DOM is finished, this shouldn't be necessary anymore :)
> 
> Thank you for the info. I am assuming that we should have it as of now :)

The patch has been r+ed so it'll probably be landed before this patch gets r+.

> Source/WebCore/dom/Node.cpp:1157
> +    if (nextSibling())
> +        return nextSibling();
> +    const Node* n = this;
> +    while (n && !n->nextSibling())
> +        n = n->parentOrHostOrFrameNode();
> +    if (n)
> +        return n->nextSibling();
> +    return 0;

Why don't we just call traverseNextNode here instead?  I would not like to see code duplication like this.

[Hayato Ito]

Thank you for the review. As Roland said, this patch should be discussed in an another bug.
It turned out that this patch is not so useful for tab traversing for focus (bug 54441), I don't have a strong reason to submit this anymore.

I'll address your comments if I need this patch again. But that should be in an another bug.

Thank you.

(In reply to comment #10)
> (From update of attachment 94179 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=94179&action=review
> 
> > Source/WebCore/dom/Node.cpp:1137
> > +Node* Node::traverseNextNodeConsideringFrameAndShadow() const
> 
> Considering frame and shadow sound misleading because we certainly consider the existence of frame and shadow whenever we traverse nodes.
> 
> Maybe traverseNextNodeAcrossFrameAndShadow?
> 
> > Source/WebCore/dom/Node.cpp:1142
> > +    if (shadowRoot(this))
> > +        return shadowRoot(this)->traverseNextNodeConsideringFrameAndShadow();
> 
> I would have saved the shadowRoot as a pointer here to avoid accessing rare data twice.
> 
> >>> Source/WebCore/dom/Node.cpp:1143
> >>> +    if (renderer() && renderer()->isTextControl()) {
> >> 
> >> Once the conversion to new-style shadow DOM is finished, this shouldn't be necessary anymore :)
> > 
> > Thank you for the info. I am assuming that we should have it as of now :)
> 
> The patch has been r+ed so it'll probably be landed before this patch gets r+.
> 
> > Source/WebCore/dom/Node.cpp:1157
> > +    if (nextSibling())
> > +        return nextSibling();
> > +    const Node* n = this;
> > +    while (n && !n->nextSibling())
> > +        n = n->parentOrHostOrFrameNode();
> > +    if (n)
> > +        return n->nextSibling();
> > +    return 0;
> 
> Why don't we just call traverseNextNode here instead?  I would not like to see code duplication like this.

[Dimitri Glazkov (Google)]

Closing per last comment.