Make HTMLCollection / NodeList backward traversal consistent with forward one

Source/core/html/HTMLCollection.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2014 Samsung Electronics. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
@@ skipping 258 matching lines @@
 template <> inline bool isMatchingElement(const ClassCollection& collection, const Element& element)
 {
     return collection.elementMatches(element);
 }
 
 template <> inline bool isMatchingElement(const HTMLTagCollection& collection, const Element& element)
 {
     return collection.elementMatches(element);
 }
 
-Element* HTMLCollection::itemBefore(const Element* previous) const
-{
-    return LiveNodeListBase::itemBefore(*this, previous);
-}
-
 Element* HTMLCollection::virtualItemAfter(Element*) const
 {
     ASSERT_NOT_REACHED();
     return 0;
 }
 
 static inline bool nameShouldBeVisibleInDocumentAll(const HTMLElement& element)
 {
     // http://www.whatwg.org/specs/web-apps/current-work/multipage/common-dom-interfaces.html#dom-htmlallcollection-nameditem:
     // The document.all collection returns only certain types of elements by name,
@@ skipping 13 matching lines @@
 }
 
 inline Element* firstMatchingChildElement(const HTMLCollection& nodeList)
 {
     Element* element = ElementTraversal::firstChild(nodeList.rootNode());
     while (element && !isMatchingElement(nodeList, *element))
         element = ElementTraversal::nextSibling(*element);
     return element;
 }
 
+inline Element* lastMatchingChildElement(const HTMLCollection& nodeList)
+{
+    Element* element = ElementTraversal::lastChild(nodeList.rootNode());
+    while (element && !isMatchingElement(nodeList, *element))
+        element = ElementTraversal::previousSibling(*element);
+    return element;
+}
+
 inline Element* nextMatchingChildElement(const HTMLCollection& nodeList, Element& current)
 {
     Element* next = &current;
     do {
         next = ElementTraversal::nextSibling(*next);
     } while (next && !isMatchingElement(nodeList, *next));
     return next;
 }
 
+inline Element* previousMatchingChildElement(const HTMLCollection& nodeList, Element& current)
+{
+    Element* previous = &current;
+    do {
+        previous = ElementTraversal::previousSibling(*previous);
+    } while (previous && !isMatchingElement(nodeList, *previous));
+    return previous;
+}
+
 Element* HTMLCollection::traverseToFirstElement() const
 {
     switch (type()) {
     case HTMLTagCollectionType:
         return firstMatchingElement(static_cast<const HTMLTagCollection&>(*this));
     case ClassCollectionType:
         return firstMatchingElement(static_cast<const ClassCollection&>(*this));
     default:
         if (overridesItemAfter())
             return virtualItemAfter(0);
         if (shouldOnlyIncludeDirectChildren())
             return firstMatchingChildElement(*this);
         return firstMatchingElement(*this);
     }
 }
 
+Element* HTMLCollection::traverseToLastElement() const
+{
+    ASSERT(canTraverseBackward());
+    if (shouldOnlyIncludeDirectChildren())
+        return lastMatchingChildElement(*this);
+    return lastMatchingElement(*this);
+}
+
 inline Element* HTMLCollection::traverseNextElement(Element& previous) const
 {
     if (overridesItemAfter())
         return virtualItemAfter(&previous);
     if (shouldOnlyIncludeDirectChildren())
         return nextMatchingChildElement(*this, previous);
     return nextMatchingElement(*this, previous);
 }
 
 Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset) const
@@ skipping 18 matching lines @@
             while ((next = nextMatchingChildElement(*this, *next))) {
                 if (++currentOffset == offset)
                     return next;
             }
             return 0;
         }
         return traverseMatchingElementsForwardToOffset(*this, offset, currentElement, currentOffset);
     }
 }
 
+Element* HTMLCollection::traverseBackwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset) const
+{
+    ASSERT(currentOffset > offset);
+    ASSERT(canTraverseBackward());
+    if (shouldOnlyIncludeDirectChildren()) {

[Inactive, 2014/04/09 23:08:58]

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.

+        Element* previous = &currentElement;
+        while ((previous = previousMatchingChildElement(*this, *previous))) {
+            if (--currentOffset == offset)
+                return previous;
+        }
+        return 0;
+    }
+    return traverseMatchingElementsBackwardToOffset(*this, offset, currentElement, currentOffset);
+}
+
 Element* HTMLCollection::namedItem(const AtomicString& name) const
 {
     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
     // This method first searches for an object with a matching id
     // attribute. If a match is not found, the method then searches for an
     // object with a matching name attribute, but only on those elements
     // that are allowed a name attribute.
     updateIdNameCache();
 
     const NamedItemCache& cache = namedItemCache();
@@ skipping 84 matching lines @@
 
     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
         result.append(nameResults->at(i));
 }
 
 HTMLCollection::NamedItemCache::NamedItemCache()
 {
 }
 
 } // namespace WebCore