We should unify various forms of tree traversal in DOM

We should unify various forms of tree traversal in DOM

Unifies tree-traversal methods in newer WTF::TreeNode class to reduce code
copying and ensure that traversals are as fast as possible.  This is hopefully
a first step towards unifying the data structures and traversal algorithms for
Node/ContainerNode and RenderObject/RenderObjectChildList.

The plan is to eventually merge NodeTraversal.h into TreeNode.h and replace all
usage of the former with the latter.  This first step is more modest in scope,
replacing only those methods that are templated and/or are copy pasted copies
between the current user of TreeNode.h -- HTMLImport -- and NodeTraversal.h.

BUG=331880
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=164625

[atreat, 2014-01-06 22:46:03]

What do you think?

[Hajime Morrita, 2014-01-07 03:27:29]

Oh, basically we're just moving traversal fucntions to TreeNode.h?
This looks reasonable for me.

[Inactive, 2014-01-07 14:37:02]

Reducing code duplication makes sense.

Looks like you have valid compilation errors in treenodetest.cpp. Make sure you
build blink_tests target.

https://codereview.chromium.org/125503002/diff/1/Source/core/dom/Node.h
File Source/core/dom/Node.h (right):

https://codereview.chromium.org/125503002/diff/1/Source/core/dom/Node.h#newco...
Source/core/dom/Node.h:174: ContainerNode* parent() const { return parentNode();
}
Longer term, we probably want to get rid of parentNode() and use
ImplementedAs=parent in Node.idl. parentNode() is used quite a lot of native
side also so this would be a big but mechanical change.

Maybe add a FIXME if others agree?

https://codereview.chromium.org/125503002/diff/1/Source/core/dom/NodeTraversal.h
File Source/core/dom/NodeTraversal.h (right):

https://codereview.chromium.org/125503002/diff/1/Source/core/dom/NodeTraversa...
Source/core/dom/NodeTraversal.h:71: inline Node* next(const Node& current) {
return WTF::traverseNext(current); }
We should not need the WTF:: prefixes.

https://codereview.chromium.org/125503002/diff/1/Source/wtf/TreeNode.h
File Source/wtf/TreeNode.h (right):

https://codereview.chromium.org/125503002/diff/1/Source/wtf/TreeNode.h#newcod...
Source/wtf/TreeNode.h:279: using WTF::traverseNextPostOrder;
You added a few methods so you are probably missing a couple of using statements
now.

[atreat, 2014-01-07 17:15:23]

On 2014/01/07 14:37:02, Chris Dumez wrote:
> Reducing code duplication makes sense.

Updated patch taking into account all your suggestions.  Everything looks to be
passing.

[Inactive, 2014-01-07 19:07:07]

Thanks for updating the patch.

lgtm for core/ but please make sure Googlers are also happy with this.

[eseidel, 2014-01-07 19:14:00]

lgtm

https://codereview.chromium.org/125503002/diff/100001/Source/core/dom/Node.h
File Source/core/dom/Node.h (right):

https://codereview.chromium.org/125503002/diff/100001/Source/core/dom/Node.h#...
Source/core/dom/Node.h:174: // FIXME: We should get rid of parentNode() usage
and replace with parent()
parentNode is part of the DOM API.  But we can prefer parent() internally if we
like.

[esprehn, 2014-01-07 19:16:36]

I'm not sure how I feel about this. Node::parentNode() checks for the ShadowRoot
encapsulation so we can't just use the TreeNode::parent() anyway. What's your
plan for this?

https://codereview.chromium.org/125503002/diff/100001/Source/core/dom/Node.h
File Source/core/dom/Node.h (right):

https://codereview.chromium.org/125503002/diff/100001/Source/core/dom/Node.h#...
Source/core/dom/Node.h:176: ContainerNode* parent() const { return parentNode();
}
Not really a fan of this, I don't think we should start using parent instead of
parentNode, diverging from the JS API just makes things confusing.

https://codereview.chromium.org/125503002/diff/100001/Source/wtf/TreeNode.h
File Source/wtf/TreeNode.h (right):

https://codereview.chromium.org/125503002/diff/100001/Source/wtf/TreeNode.h#n...
Source/wtf/TreeNode.h:146: /* fast pre-order traversal */
Why is it "fast"?

https://codereview.chromium.org/125503002/diff/100001/Source/wtf/TreeNode.h#n...
Source/wtf/TreeNode.h:236: /* fast traversal skipping children */
Same thing, what's fast about it?

[commit-bot: I haz the power, 2014-01-07 19:16:54]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/adam.treat@samsung.com/125503002/100001

[atreat, 2014-01-07 19:25:46]

On 2014/01/07 19:16:36, esprehn wrote:
> I'm not sure how I feel about this. Node::parentNode() checks for the
ShadowRoot
> encapsulation so we can't just use the TreeNode::parent() anyway. What's your
> plan for this?

Ok, stopped the commit check.  Too quick on the draw ;)

> https://codereview.chromium.org/125503002/diff/100001/Source/core/dom/Node.h
> File Source/core/dom/Node.h (right):
> 
>
https://codereview.chromium.org/125503002/diff/100001/Source/core/dom/Node.h#...
> Source/core/dom/Node.h:176: ContainerNode* parent() const { return
parentNode();
> }
> Not really a fan of this, I don't think we should start using parent instead
of
> parentNode, diverging from the JS API just makes things confusing.

Ok, well the options seem to be:

1) Change TreeNode.h to use 'parentNode()' instead.
2) Keep the parent() convenience method on Node.h and remove the FIXME
3) Replace parentNode() in c++ with parent(), but keep parentNode in JS (I have
a patch that does exactly this btw...)

Looking for consensus.

>
https://codereview.chromium.org/125503002/diff/100001/Source/wtf/TreeNode.h#n...
> Source/wtf/TreeNode.h:146: /* fast pre-order traversal */
> Why is it "fast"?

I have a small program I've written trying various different traversal
algorithms (both non-recursive and recursive) against various tree types:

1) large balanced tree with 21523359 nodes and 15 layers deep
2) large depth tree with 10000 layers deep
3) large breadth tree with 10000 siblings in one layer

In all cases the algorithm in NodeTraversal.h that I'm moving to TreeNode.h was
the fastest.  Much faster than recursion.
 
>
https://codereview.chromium.org/125503002/diff/100001/Source/wtf/TreeNode.h#n...
> Source/wtf/TreeNode.h:236: /* fast traversal skipping children */
> Same thing, what's fast about it?

See above.

I can share my small program if you want.

[esprehn, 2014-01-07 19:38:58]

On 2014/01/07 19:25:46, atreat wrote:
> On 2014/01/07 19:16:36, esprehn wrote:
> > I'm not sure how I feel about this. Node::parentNode() checks for the
> ShadowRoot
> > encapsulation so we can't just use the TreeNode::parent() anyway. What's
your
> > plan for this?
> 
> Ok, stopped the commit check.  Too quick on the draw ;)
> 
> > https://codereview.chromium.org/125503002/diff/100001/Source/core/dom/Node.h
> > File Source/core/dom/Node.h (right):
> > 
> >
>
https://codereview.chromium.org/125503002/diff/100001/Source/core/dom/Node.h#...
> > Source/core/dom/Node.h:176: ContainerNode* parent() const { return
> parentNode();
> > }
> > Not really a fan of this, I don't think we should start using parent instead
> of
> > parentNode, diverging from the JS API just makes things confusing.
> 
> Ok, well the options seem to be:
> 
> 1) Change TreeNode.h to use 'parentNode()' instead.
> 2) Keep the parent() convenience method on Node.h and remove the FIXME
> 3) Replace parentNode() in c++ with parent(), but keep parentNode in JS (I
have
> a patch that does exactly this btw...)
> 
> Looking for consensus.

I suppose lets go forward with what you have right now.

> 
> >
>
https://codereview.chromium.org/125503002/diff/100001/Source/wtf/TreeNode.h#n...
> > Source/wtf/TreeNode.h:146: /* fast pre-order traversal */
> > Why is it "fast"?
> 
> I have a small program I've written trying various different traversal
> algorithms (both non-recursive and recursive) against various tree types:
> 
> 1) large balanced tree with 21523359 nodes and 15 layers deep
> 2) large depth tree with 10000 layers deep
> 3) large breadth tree with 10000 siblings in one layer
> 
> In all cases the algorithm in NodeTraversal.h that I'm moving to TreeNode.h
was
> the fastest.  Much faster than recursion.
>  

Add this to a comment and remove the two comments you have. Adding comments that
something is "fast" without any explaination means someone is likely to come
undo your code later and make it slower without realizing it, especially this
which doesn't explain what makes it fast (ex. no recursion).

> >
>
https://codereview.chromium.org/125503002/diff/100001/Source/wtf/TreeNode.h#n...
> > Source/wtf/TreeNode.h:236: /* fast traversal skipping children */
> > Same thing, what's fast about it?
> 
> See above.
> 
> I can share my small program if you want.

Sure!

[atreat, 2014-01-07 19:40:51]

On 2014/01/07 19:16:36, esprehn wrote:
> I'm not sure how I feel about this. Node::parentNode() checks for the
ShadowRoot
> encapsulation so we can't just use the TreeNode::parent() anyway. What's your
> plan for this?

Hmm, I thought we could deal with Node/ContainerNode's peculiarities with
template specialization:

class SpecialNode : public TreeNode<SpecialNode> {
public:
    bool isSpecial() const { return true; }
};

template<> SpecialNode* TreeNode<SpecialNode>::parent()
{
    return static_cast<SpecialNode*>(this)->isSpecial() ? 0 : m_parent;
}

I don't have this all roughed out yet, but I think we can get somewhere with
this.

[esprehn, 2014-01-07 19:44:34]

On 2014/01/07 19:40:51, atreat wrote:
> On 2014/01/07 19:16:36, esprehn wrote:
> > I'm not sure how I feel about this. Node::parentNode() checks for the
> ShadowRoot
> > encapsulation so we can't just use the TreeNode::parent() anyway. What's
your
> > plan for this?
> 
> Hmm, I thought we could deal with Node/ContainerNode's peculiarities with
> template specialization:
> 
> class SpecialNode : public TreeNode<SpecialNode> {
> public:
>     bool isSpecial() const { return true; }
> };
> 
> template<> SpecialNode* TreeNode<SpecialNode>::parent()
> {
>     return static_cast<SpecialNode*>(this)->isSpecial() ? 0 : m_parent;
> }
> 
> I don't have this all roughed out yet, but I think we can get somewhere with
> this.

That seems fine if we're sure the generated code and optimizations will be the
same.

[esprehn, 2014-01-07 19:48:54]

lgtm

[commit-bot: I haz the power, 2014-01-07 19:58:59]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/adam.treat@samsung.com/125503002/260001

[commit-bot: I haz the power, 2014-01-07 22:47:29]

Change committed as 164625

[esprehn, 2014-01-08 02:34:56]

On 2014/01/07 22:47:29, I haz the power (commit-bot) wrote:
> Change committed as 164625

This patch is not correct, you disabled the ContainerNode template
specialization that avoided the isContainerNode() checks in NodeTraversal.
Specifically:

 inline Node* nextSkippingChildren(const ContainerNode& current) { return
traverseNextSkippingChildren<Node>(current); }

It's not correct to force it down the Node template specialization there, since
we lost all the optimization from having the ContainerNode version of the
function that skips the isContainerNode() checks in Node::firstChild() and
friends.

[Inactive, 2014-01-08 02:51:07]

On 2014/01/08 02:34:56, esprehn wrote:
> On 2014/01/07 22:47:29, I haz the power (commit-bot) wrote:
> > Change committed as 164625
> 
> This patch is not correct, you disabled the ContainerNode template
> specialization that avoided the isContainerNode() checks in NodeTraversal.
> Specifically:
> 
>  inline Node* nextSkippingChildren(const ContainerNode& current) { return
> traverseNextSkippingChildren<Node>(current); }
> 
> It's not correct to force it down the Node template specialization there,
since
> we lost all the optimization from having the ContainerNode version of the
> function that skips the isContainerNode() checks in Node::firstChild() and
> friends.

In the call to traverseNextSkippingChildren<Node>(current), the "Node" template
argument is for the expected returned type. traverseNextSkippingChildren() has 2
template arguments (the return type and the argument type). Here the argument
type is not specified explicitly as the compiler can deduce it. Since current is
a ContainerNode, ContainerNode::firstChild() should be called.

Or am I missing something?

[Inactive, 2014-01-08 03:08:00]

https://codereview.chromium.org/125503002/diff/260001/Source/wtf/TreeNode.h
File Source/wtf/TreeNode.h (right):

https://codereview.chromium.org/125503002/diff/260001/Source/wtf/TreeNode.h#n...
Source/wtf/TreeNode.h:147: template<class NodeType, class ContainerType>
BTW, I am not a big fan of the NodeType / ContainerType naming. They are both
Node types, but they may be different.

ContainerType may be a Node here (as opposed to a ContainerNode) so I think the
naming is a bit confusing. I would have preferred more generic names (e.g.
NodeType1 / NodeType2), what do others think?

[esprehn, 2014-01-08 03:39:40]

On 2014/01/08 03:08:00, Chris Dumez wrote:
> https://codereview.chromium.org/125503002/diff/260001/Source/wtf/TreeNode.h
> File Source/wtf/TreeNode.h (right):
> 
>
https://codereview.chromium.org/125503002/diff/260001/Source/wtf/TreeNode.h#n...
> Source/wtf/TreeNode.h:147: template<class NodeType, class ContainerType>
> BTW, I am not a big fan of the NodeType / ContainerType naming. They are both
> Node types, but they may be different.

Yeah it does appear to be that.

> 
> ContainerType may be a Node here (as opposed to a ContainerNode) so I think
the
> naming is a bit confusing. I would have preferred more generic names (e.g.
> NodeType1 / NodeType2), what do others think?

I think the current naming makes sense, one is the type for things with children
and one is the type for things where you're not sure.