Make HTMLCollection / NodeList backward traversal consistent with forward one

Make HTMLCollection / NodeList backward traversal consistent with forward one

This makes the code clearer and more consistent. There is no reason to handle
backward traversal differently from forward traversal.

This CL also updates to make ElementTraversal::lastWithin() actually return
the last descendant of Element type, and not the last child Element. This is
not equivalent. ElementTraversal::lastChild() should be used instead to get
the last child Element. This results in the removal of
LiveNodeListBase::lastDescendant() method.

R=esprehn@chromium.org, adamk@chromium.org

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

[adamk, 2014-04-09 22:38:16]

Sorry for the slow response, but I've read over this change a few times now and
I'm unclear on its advantages. Is it just to make it easier for future
generations to make sense of the traversal code?

It doesn't seem like there are any callers that are interested in the new return
value of ElementTraversal::lastWithin, so this patch has no interesting effect
on the public API as far as I can tell.

[Inactive, 2014-04-09 22:58:35]

On 2014/04/09 22:38:16, adamk wrote:
> It doesn't seem like there are any callers that are interested in the new
return
> value of ElementTraversal::lastWithin, so this patch has no interesting effect
> on the public API as far as I can tell.

To be fair, the current version of ElementTraversal::lastWithin() is wrong (last
descendant != last child) and is used incorrectly instead of lastChild(). I do
think there is value in fixing it, and also using it in HTMLCollection to avoid
duplication with LiveNodeListBase::lastDescendant(). I could even do this change
separately.

Regarding the other changes, this make the code clearer and more consistent as
backward traversal and forward traversal would work the same way. The reason
they behaved differently is likely because forward traversal was optimized a lot
more than backward traversal (which is less common). So there is a performance
impact of this change for backward traversal but I will explain this better
separately.

[Inactive, 2014-04-09 23:08:57]

Here are some details about the performance benefits of doing this change.
Currently, traversing forward is faster than traverse backward. It is true that
traversing backward is less common but I don't think this change decreases code
readability. On the contrary, I believe it is clearer because it is consistent
with the code for forward traversal.

https://codereview.chromium.org/229213002/diff/1/Source/core/dom/LiveNodeList...
File Source/core/dom/LiveNodeListBase.h (left):

https://codereview.chromium.org/229213002/diff/1/Source/core/dom/LiveNodeList...
Source/core/dom/LiveNodeListBase.h:168: if (LIKELY(!!previous)) // Without this
LIKELY, length() and item() can be 10% slower.
This if check is now avoided as the current caller (CollectionIndexCache)
already knows if it want the last item or a previous item. This is why we now
have separate methods for traverseBackwardToOffset() and traverseToLastItem().

https://codereview.chromium.org/229213002/diff/1/Source/core/html/CollectionI...
File Source/core/html/CollectionIndexCache.h (left):

https://codereview.chromium.org/229213002/diff/1/Source/core/html/CollectionI...
Source/core/html/CollectionIndexCache.h:188: NodeType* lastItem =
collection.itemBefore(0);
We now call traverseToLastElement() here instead of the generic itemBefore()
which means the implementation no longer need to do a null check on the argument
to know what to do.

https://codereview.chromium.org/229213002/diff/1/Source/core/html/CollectionI...
File Source/core/html/CollectionIndexCache.h (right):

https://codereview.chromium.org/229213002/diff/1/Source/core/html/CollectionI...
Source/core/html/CollectionIndexCache.h:165: NodeType* currentNode =
collection.traverseBackwardToOffset(index, *cachedNode(), currentIndex);
We now pass a reference instead of a pointer to the implementation since there
is now a separate traverseToLastElement() method.

https://codereview.chromium.org/229213002/diff/1/Source/core/html/HTMLCollect...
File Source/core/html/HTMLCollection.cpp (right):

https://codereview.chromium.org/229213002/diff/1/Source/core/html/HTMLCollect...
Source/core/html/HTMLCollection.cpp:404: if (shouldOnlyIncludeDirectChildren())
{
Now we do this check once and then traverse to the right offset.
Previously, since there was no method to traverse backward to an offset (only
itemBefore()), we were doing this check for *every* item on the path to the
offset. The check was in LiveNodeListBase::itemBefore() and CollectionIndexCache
was calling it in a for loop until it reached the right offset.

[Inactive, 2014-04-09 23:14:29]

https://codereview.chromium.org/229213002/diff/1/Source/core/dom/ElementTrave...
File Source/core/dom/ElementTraversal.h (right):

https://codereview.chromium.org/229213002/diff/1/Source/core/dom/ElementTrave...
Source/core/dom/ElementTraversal.h:48: // First or last ElementType descendant
of the node.
BTW, the comment here clearly says we are supposed to return the last
*descendant* of the node. This is currently true for non-pure Elements. However,
for pure Elements, it was returning the last child of the node.

Also note that there is already an ElementTraversal::lastChild() to return the
last child Element of a Node.

I made this mistake when I refactored the ElementTraversal class because
ElementTraversal::firstWithin() *is* identical to
ElementTraversal::firstChild(). I (wrongly) did the same thing for
ElementTraversal::lastWithin() / ElementTraversal::lastChild().

[Inactive, 2014-04-09 23:19:07]

https://codereview.chromium.org/229213002/diff/1/Source/core/dom/ElementTrave...
File Source/core/dom/ElementTraversal.h (right):

https://codereview.chromium.org/229213002/diff/1/Source/core/dom/ElementTrave...
Source/core/dom/ElementTraversal.h:122: Node* node =
NodeTraversal::lastWithin(current);
Also see that WebKit is doing the same thing that I propose there:
http://trac.webkit.org/browser/trunk/Source/WebCore/dom/ElementTraversal.h#L107

[adamk, 2014-04-09 23:23:43]

lgtm

Thank you for the comments, very helpful in understanding the change, and sorry
if I was being dense. After a couple of weeks with this stuff swapped out of my
head I wasn't doing a good job of swapping it back in.

[Inactive, 2014-04-09 23:34:17]

The CQ bit was checked by ch.dumez@samsung.com

[commit-bot: I haz the power, 2014-04-09 23:34:19]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ch.dumez@samsung.com/229213002/1

[commit-bot: I haz the power, 2014-04-09 23:43:56]

Change committed as 171202