Bug 59812 - Refactor DOM tree traversal methods
Summary: Refactor DOM tree traversal methods
Status: RESOLVED INVALID
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks: 54441 59802
  Show dependency treegraph
 
Reported: 2011-04-29 11:16 PDT by Roland Steiner
Modified: 2011-06-08 14:25 PDT (History)
5 users (show)

See Also:


Attachments
WIP - add universalTraverseNextNode (6.11 KB, patch)
2011-05-19 23:38 PDT, Hayato Ito
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Roland Steiner 2011-04-29 11:16:51 PDT
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()
Comment 1 Roland Steiner 2011-05-18 21:40:19 PDT
ShadowRoot
    parentTreeScope()

is also needed.
Comment 2 Dimitri Glazkov (Google) 2011-05-18 21:42:33 PDT
htmlediting is a great place to fish for those.
Comment 3 Dominic Cooney 2011-05-19 22:46:10 PDT
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.
Comment 4 Roland Steiner 2011-05-19 23:35:29 PDT
(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).
Comment 5 Hayato Ito 2011-05-19 23:38:23 PDT
Created attachment 94179 [details]
WIP - add universalTraverseNextNode
Comment 6 Hayato Ito 2011-05-19 23:43:07 PDT
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
Comment 7 Roland Steiner 2011-05-20 02:46:52 PDT
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?
Comment 8 Hayato Ito 2011-05-20 03:24:02 PDT
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.
Comment 9 Dimitri Glazkov (Google) 2011-05-20 08:37:05 PDT
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?
Comment 10 Ryosuke Niwa 2011-05-20 11:19:52 PDT
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.
Comment 11 Hayato Ito 2011-05-22 19:21:56 PDT
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.
Comment 12 Dimitri Glazkov (Google) 2011-06-08 14:25:51 PDT
Closing per last comment.