[webkit-changes] [158774] trunk/Source/WebCore

Wed, 06 Nov 2013 12:37:35 -0800

Title: [158774] trunk/Source/WebCore
Revision
158774
Author
[email protected]
Date
2013-11-06 12:38:37 -0800 (Wed, 06 Nov 2013)

Log Message

HTMLCollection should use CollectionIndexCache
https://bugs.webkit.org/show_bug.cgi?id=123906

Reviewed by Ryosuke Niwa.
        
More code sharing.

* bindings/js/JSDOMWindowCustom.cpp:
(WebCore::namedItemGetter):
* bindings/js/JSHTMLDocumentCustom.cpp:
(WebCore::JSHTMLDocument::nameGetter):
* dom/ChildNodeList.h:
* dom/CollectionIndexCache.h:
(WebCore::::nodeBeforeCached):
(WebCore::::nodeAfterCached):
(WebCore::::nodeAt):
            
    Add a mechanism for disabling use of backward traversal.

* dom/LiveNodeList.h:
(WebCore::LiveNodeList::collectionCanTraverseBackward):
* html/HTMLCollection.cpp:
(WebCore::HTMLCollection::HTMLCollection):
(WebCore::isMatchingElement):
(WebCore::HTMLCollection::iterateForPreviousElement):
(WebCore::firstMatchingElement):
(WebCore::nextMatchingElement):
(WebCore::HTMLCollection::length):
(WebCore::HTMLCollection::item):
(WebCore::nameShouldBeVisibleInDocumentAll):
(WebCore::firstMatchingChildElement):
(WebCore::nextMatchingSiblingElement):
(WebCore::HTMLCollection::firstElement):
(WebCore::HTMLCollection::traverseForward):
(WebCore::HTMLCollection::collectionFirst):
(WebCore::HTMLCollection::collectionLast):
(WebCore::HTMLCollection::collectionTraverseForward):
(WebCore::HTMLCollection::collectionTraverseBackward):
(WebCore::HTMLCollection::invalidateCache):
(WebCore::HTMLCollection::namedItem):
(WebCore::HTMLCollection::updateNameCache):
* html/HTMLCollection.h:
(WebCore::HTMLCollection::collectionCanTraverseBackward):
        
    Disable use of backward traversal for collections that use custom traversal.

Modified Paths

Diff

Modified: trunk/Source/WebCore/ChangeLog (158773 => 158774)


--- trunk/Source/WebCore/ChangeLog	2013-11-06 20:32:19 UTC (rev 158773)
+++ trunk/Source/WebCore/ChangeLog	2013-11-06 20:38:37 UTC (rev 158774)
@@ -1,3 +1,51 @@
+2013-11-06  Antti Koivisto  <[email protected]>
+
+        HTMLCollection should use CollectionIndexCache
+        https://bugs.webkit.org/show_bug.cgi?id=123906
+
+        Reviewed by Ryosuke Niwa.
+        
+        More code sharing.
+
+        * bindings/js/JSDOMWindowCustom.cpp:
+        (WebCore::namedItemGetter):
+        * bindings/js/JSHTMLDocumentCustom.cpp:
+        (WebCore::JSHTMLDocument::nameGetter):
+        * dom/ChildNodeList.h:
+        * dom/CollectionIndexCache.h:
+        (WebCore::::nodeBeforeCached):
+        (WebCore::::nodeAfterCached):
+        (WebCore::::nodeAt):
+            
+            Add a mechanism for disabling use of backward traversal.
+
+        * dom/LiveNodeList.h:
+        (WebCore::LiveNodeList::collectionCanTraverseBackward):
+        * html/HTMLCollection.cpp:
+        (WebCore::HTMLCollection::HTMLCollection):
+        (WebCore::isMatchingElement):
+        (WebCore::HTMLCollection::iterateForPreviousElement):
+        (WebCore::firstMatchingElement):
+        (WebCore::nextMatchingElement):
+        (WebCore::HTMLCollection::length):
+        (WebCore::HTMLCollection::item):
+        (WebCore::nameShouldBeVisibleInDocumentAll):
+        (WebCore::firstMatchingChildElement):
+        (WebCore::nextMatchingSiblingElement):
+        (WebCore::HTMLCollection::firstElement):
+        (WebCore::HTMLCollection::traverseForward):
+        (WebCore::HTMLCollection::collectionFirst):
+        (WebCore::HTMLCollection::collectionLast):
+        (WebCore::HTMLCollection::collectionTraverseForward):
+        (WebCore::HTMLCollection::collectionTraverseBackward):
+        (WebCore::HTMLCollection::invalidateCache):
+        (WebCore::HTMLCollection::namedItem):
+        (WebCore::HTMLCollection::updateNameCache):
+        * html/HTMLCollection.h:
+        (WebCore::HTMLCollection::collectionCanTraverseBackward):
+        
+            Disable use of backward traversal for collections that use custom traversal.
+
 2013-11-06  Brendan Long  <[email protected]>
 
         Add "id" attribute to TextTrack

Modified: trunk/Source/WebCore/bindings/js/JSDOMWindowCustom.cpp (158773 => 158774)


--- trunk/Source/WebCore/bindings/js/JSDOMWindowCustom.cpp	2013-11-06 20:32:19 UTC (rev 158773)
+++ trunk/Source/WebCore/bindings/js/JSDOMWindowCustom.cpp	2013-11-06 20:38:37 UTC (rev 158774)
@@ -101,8 +101,7 @@
 
     if (UNLIKELY(toHTMLDocument(document)->windowNamedItemContainsMultipleElements(*atomicPropertyName))) {
         RefPtr<HTMLCollection> collection = document->windowNamedItems(atomicPropertyName);
-        ASSERT(!collection->isEmpty());
-        ASSERT(!collection->hasExactlyOneItem());
+        ASSERT(collection->length() > 1);
         return toJS(exec, thisObj->globalObject(), WTF::getPtr(collection));
     }

Modified: trunk/Source/WebCore/bindings/js/JSHTMLDocumentCustom.cpp (158773 => 158774)


--- trunk/Source/WebCore/bindings/js/JSHTMLDocumentCustom.cpp	2013-11-06 20:32:19 UTC (rev 158773)
+++ trunk/Source/WebCore/bindings/js/JSHTMLDocumentCustom.cpp	2013-11-06 20:38:37 UTC (rev 158774)
@@ -68,8 +68,7 @@
 
     if (UNLIKELY(document.documentNamedItemContainsMultipleElements(*atomicPropertyName))) {
         RefPtr<HTMLCollection> collection = document.documentNamedItems(atomicPropertyName);
-        ASSERT(!collection->isEmpty());
-        ASSERT(!collection->hasExactlyOneItem());
+        ASSERT(collection->length() > 1);
         return toJS(exec, thisObj->globalObject(), WTF::getPtr(collection));
     }

Modified: trunk/Source/WebCore/dom/ChildNodeList.h (158773 => 158774)


--- trunk/Source/WebCore/dom/ChildNodeList.h	2013-11-06 20:32:19 UTC (rev 158773)
+++ trunk/Source/WebCore/dom/ChildNodeList.h	2013-11-06 20:38:37 UTC (rev 158774)
@@ -73,6 +73,7 @@
     Node* collectionLast() const;
     Node* collectionTraverseForward(Node&, unsigned count, unsigned& traversedCount) const;
     Node* collectionTraverseBackward(Node&, unsigned count) const;
+    bool collectionCanTraverseBackward() const { return true; }
 
 private:
     explicit ChildNodeList(ContainerNode& parent);

Modified: trunk/Source/WebCore/dom/CollectionIndexCache.h (158773 => 158774)


--- trunk/Source/WebCore/dom/CollectionIndexCache.h	2013-11-06 20:32:19 UTC (rev 158773)
+++ trunk/Source/WebCore/dom/CollectionIndexCache.h	2013-11-06 20:38:37 UTC (rev 158774)
@@ -80,7 +80,7 @@
     ASSERT(index < m_currentIndex);
 
     bool firstIsCloser = index < m_currentIndex - index;
-    if (firstIsCloser) {
+    if (firstIsCloser || !collection.collectionCanTraverseBackward()) {
         m_currentNode = collection.collectionFirst();
         m_currentIndex = 0;
         if (index)
@@ -104,7 +104,7 @@
     ASSERT(!m_nodeCountValid || index < m_nodeCount);
 
     bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index - m_currentIndex;
-    if (lastIsCloser) {
+    if (lastIsCloser && collection.collectionCanTraverseBackward()) {
         m_currentNode = collection.collectionLast();
         if (index < m_nodeCount - 1)
             m_currentNode = collection.collectionTraverseBackward(*m_currentNode, m_nodeCount - index - 1);
@@ -142,7 +142,7 @@
     }
 
     bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index;
-    if (lastIsCloser) {
+    if (lastIsCloser && collection.collectionCanTraverseBackward()) {
         m_currentNode = collection.collectionLast();
         if (index < m_nodeCount - 1)
             m_currentNode = collection.collectionTraverseBackward(*m_currentNode, m_nodeCount - index - 1);

Modified: trunk/Source/WebCore/dom/LiveNodeList.h (158773 => 158774)


--- trunk/Source/WebCore/dom/LiveNodeList.h	2013-11-06 20:32:19 UTC (rev 158773)
+++ trunk/Source/WebCore/dom/LiveNodeList.h	2013-11-06 20:38:37 UTC (rev 158774)
@@ -66,7 +66,7 @@
 
         document().registerNodeList(*this);
     }
-    virtual Node* namedItem(const AtomicString&) const OVERRIDE;
+    virtual Node* namedItem(const AtomicString&) const OVERRIDE FINAL;
     virtual bool nodeMatches(Element*) const = 0;
 
     virtual ~LiveNodeList()
@@ -75,8 +75,8 @@
     }
 
     // DOM API
-    virtual unsigned length() const OVERRIDE;
-    virtual Node* item(unsigned offset) const OVERRIDE;
+    virtual unsigned length() const OVERRIDE FINAL;
+    virtual Node* item(unsigned offset) const OVERRIDE FINAL;
 
     ALWAYS_INLINE bool isRootedAtDocument() const { return m_rootType == NodeListIsRootedAtDocument; }
     ALWAYS_INLINE NodeListInvalidationType invalidationType() const { return static_cast<NodeListInvalidationType>(m_invalidationType); }
@@ -94,6 +94,7 @@
     Element* collectionLast() const;
     Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
     Element* collectionTraverseBackward(Element&, unsigned count) const;
+    bool collectionCanTraverseBackward() const { return true; }
 
 protected:
     Document& document() const { return m_ownerNode->document(); }

Modified: trunk/Source/WebCore/html/HTMLCollection.cpp (158773 => 158774)


--- trunk/Source/WebCore/html/HTMLCollection.cpp	2013-11-06 20:32:19 UTC (rev 158773)
+++ trunk/Source/WebCore/html/HTMLCollection.cpp	2013-11-06 20:38:37 UTC (rev 158774)
@@ -133,9 +133,6 @@
 
 HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ElementTraversalType traversalType)
     : m_ownerNode(ownerNode)
-    , m_cachedElement(nullptr)
-    , m_isLengthCacheValid(false)
-    , m_isElementCacheValid(false)
     , m_rootType(rootTypeFromCollectionType(type))
     , m_invalidationType(invalidationTypeExcludingIdAndNameAttributes(type))
     , m_shouldOnlyIncludeDirectChildren(shouldOnlyIncludeDirectChildren(type))
@@ -172,53 +169,53 @@
     return ownerNode();
 }
 
-inline bool isMatchingElement(const HTMLCollection* htmlCollection, Element* element)
+inline bool isMatchingElement(const HTMLCollection& htmlCollection, Element& element)
 {
-    CollectionType type = htmlCollection->type();
-    if (!element->isHTMLElement() && !(type == DocAll || type == NodeChildren || type == WindowNamedItems))
+    CollectionType type = htmlCollection.type();
+    if (!element.isHTMLElement() && !(type == DocAll || type == NodeChildren || type == WindowNamedItems))
         return false;
 
     switch (type) {
     case DocImages:
-        return element->hasLocalName(imgTag);
+        return element.hasLocalName(imgTag);
     case DocScripts:
-        return element->hasLocalName(scriptTag);
+        return element.hasLocalName(scriptTag);
     case DocForms:
-        return element->hasLocalName(formTag);
+        return element.hasLocalName(formTag);
     case TableTBodies:
-        return element->hasLocalName(tbodyTag);
+        return element.hasLocalName(tbodyTag);
     case TRCells:
-        return element->hasLocalName(tdTag) || element->hasLocalName(thTag);
+        return element.hasLocalName(tdTag) || element.hasLocalName(thTag);
     case TSectionRows:
-        return element->hasLocalName(trTag);
+        return element.hasLocalName(trTag);
     case SelectOptions:
-        return element->hasLocalName(optionTag);
+        return element.hasLocalName(optionTag);
     case SelectedOptions:
-        return element->hasLocalName(optionTag) && toHTMLOptionElement(element)->selected();
+        return element.hasLocalName(optionTag) && toHTMLOptionElement(element).selected();
     case DataListOptions:
-        if (element->hasLocalName(optionTag)) {
-            HTMLOptionElement* option = toHTMLOptionElement(element);
-            if (!option->isDisabledFormControl() && !option->value().isEmpty())
+        if (element.hasLocalName(optionTag)) {
+            HTMLOptionElement& option = toHTMLOptionElement(element);
+            if (!option.isDisabledFormControl() && !option.value().isEmpty())
                 return true;
         }
         return false;
     case MapAreas:
-        return element->hasLocalName(areaTag);
+        return element.hasLocalName(areaTag);
     case DocApplets:
-        return element->hasLocalName(appletTag) || (element->hasLocalName(objectTag) && static_cast<HTMLObjectElement*>(element)->containsJavaApplet());
+        return element.hasLocalName(appletTag) || (element.hasLocalName(objectTag) && toHTMLObjectElement(element).containsJavaApplet());
     case DocEmbeds:
-        return element->hasLocalName(embedTag);
+        return element.hasLocalName(embedTag);
     case DocLinks:
-        return (element->hasLocalName(aTag) || element->hasLocalName(areaTag)) && element->fastHasAttribute(hrefAttr);
+        return (element.hasLocalName(aTag) || element.hasLocalName(areaTag)) && element.fastHasAttribute(hrefAttr);
     case DocAnchors:
-        return element->hasLocalName(aTag) && element->fastHasAttribute(nameAttr);
+        return element.hasLocalName(aTag) && element.fastHasAttribute(nameAttr);
     case DocAll:
     case NodeChildren:
         return true;
     case DocumentNamedItems:
-        return static_cast<const DocumentNameCollection*>(htmlCollection)->nodeMatches(element);
+        return static_cast<const DocumentNameCollection&>(htmlCollection).nodeMatches(&element);
     case WindowNamedItems:
-        return static_cast<const WindowNameCollection*>(htmlCollection)->nodeMatches(element);
+        return static_cast<const WindowNameCollection&>(htmlCollection).nodeMatches(&element);
     case FormControls:
     case TableRows:
         break;
@@ -232,216 +229,139 @@
     return onlyIncludeDirectChildren ? ElementTraversal::previousSibling(previous) : ElementTraversal::previous(previous, &base);
 }
 
-static Element* lastElement(ContainerNode& rootNode, bool onlyIncludeDirectChildren)
-{
-    return onlyIncludeDirectChildren ? ElementTraversal::lastChild(&rootNode) : ElementTraversal::lastWithin(&rootNode);
-}
-
 ALWAYS_INLINE Element* HTMLCollection::iterateForPreviousElement(Element* current) const
 {
     bool _onlyIncludeDirectChildren_ = m_shouldOnlyIncludeDirectChildren;
     ContainerNode& rootNode = this->rootNode();
     for (; current; current = previousElement(rootNode, current, onlyIncludeDirectChildren)) {
-        if (isMatchingElement(this, current))
+        if (isMatchingElement(*this, *current))
             return current;
     }
-    return 0;
+    return nullptr;
 }
 
-ALWAYS_INLINE Element* HTMLCollection::itemBefore(Element* previous) const
+inline Element* firstMatchingElement(const HTMLCollection& collection, ContainerNode& root)
 {
-    Element* current;
-    if (LIKELY(!!previous)) // Without this LIKELY, length() and item() can be 10% slower.
-        current = previousElement(rootNode(), previous, m_shouldOnlyIncludeDirectChildren);
-    else
-        current = lastElement(rootNode(), m_shouldOnlyIncludeDirectChildren);
-
-    return iterateForPreviousElement(current);
-}
-
-inline Element* firstMatchingElement(const HTMLCollection* collection, ContainerNode* root)
-{
-    Element* element = ElementTraversal::firstWithin(root);
-    while (element && !isMatchingElement(collection, element))
-        element = ElementTraversal::next(element, root);
+    Element* element = ElementTraversal::firstWithin(&root);
+    while (element && !isMatchingElement(collection, *element))
+        element = ElementTraversal::next(element, &root);
     return element;
 }
 
-inline Element* nextMatchingElement(const HTMLCollection* collection, Element* current, ContainerNode* root)
+inline Element* nextMatchingElement(const HTMLCollection& collection, Element* current, ContainerNode& root)
 {
     do {
-        current = ElementTraversal::next(current, root);
-    } while (current && !isMatchingElement(collection, current));
+        current = ElementTraversal::next(current, &root);
+    } while (current && !isMatchingElement(collection, *current));
     return current;
 }
 
-inline Element* traverseMatchingElementsForwardToOffset(const HTMLCollection* collection, unsigned offset, Element* currentElement, unsigned& currentOffset, ContainerNode* root)
-{
-    ASSERT_WITH_SECURITY_IMPLICATION(currentOffset < offset);
-    while ((currentElement = nextMatchingElement(collection, currentElement, root))) {
-        if (++currentOffset == offset)
-            return currentElement;
-    }
-    return 0;
-}
-
-bool ALWAYS_INLINE HTMLCollection::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
-{
-    ASSERT(isLengthCacheValid());
-    unsigned distanceFromLastItem = cachedLength() - offset;
-    if (!isElementCacheValid())
-        return distanceFromLastItem < offset;
-
-    return cachedElementOffset() < offset && distanceFromLastItem < offset - cachedElementOffset();
-}
-    
-bool ALWAYS_INLINE HTMLCollection::isFirstItemCloserThanCachedItem(unsigned offset) const
-{
-    ASSERT(isElementCacheValid());
-    if (cachedElementOffset() < offset)
-        return false;
-
-    unsigned distanceFromCachedItem = cachedElementOffset() - offset;
-    return offset < distanceFromCachedItem;
-}
-
 unsigned HTMLCollection::length() const
 {
-    if (isLengthCacheValid())
-        return cachedLength();
-
-    item(UINT_MAX);
-    ASSERT(isLengthCacheValid());
-    
-    return cachedLength();
+    return m_indexCache.nodeCount(*this);
 }
 
 Node* HTMLCollection::item(unsigned offset) const
 {
-    if (isElementCacheValid() && cachedElementOffset() == offset)
-        return cachedElement();
-
-    if (isLengthCacheValid() && cachedLength() <= offset)
-        return 0;
-
-    ContainerNode& root = rootNode();
-
-    if (isLengthCacheValid() && !usesCustomForwardOnlyTraversal() && isLastItemCloserThanLastOrCachedItem(offset)) {
-        Element* lastItem = itemBefore(0);
-        ASSERT(lastItem);
-        setCachedElement(*lastItem, cachedLength() - 1);
-    } else if (!isElementCacheValid() || isFirstItemCloserThanCachedItem(offset) || (usesCustomForwardOnlyTraversal() && offset < cachedElementOffset())) {
-        Element* firstItem = firstElement(&root);
-
-        if (!firstItem) {
-            setLengthCache(0);
-            return 0;
-        }
-        setCachedElement(*firstItem, 0);
-        ASSERT(!cachedElementOffset());
-    }
-
-    if (cachedElementOffset() == offset)
-        return cachedElement();
-
-    return elementBeforeOrAfterCachedElement(offset, &root);
+    return m_indexCache.nodeAt(*this, offset);
 }
 
-inline Element* HTMLCollection::elementBeforeOrAfterCachedElement(unsigned offset, ContainerNode* root) const
+static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement& element)
 {
-    unsigned currentOffset = cachedElementOffset();
-    Element* currentItem = cachedElement();
-    ASSERT(currentItem);
-    ASSERT(currentOffset != offset);
-
-    if (offset < cachedElementOffset()) {
-        ASSERT(!usesCustomForwardOnlyTraversal());
-        while ((currentItem = itemBefore(currentItem))) {
-            ASSERT(currentOffset);
-            currentOffset--;
-            if (currentOffset == offset) {
-                setCachedElement(*currentItem, currentOffset);
-                return currentItem;
-            }
-        }
-        ASSERT_NOT_REACHED();
-        return 0;
-    }
-
-    currentItem = traverseForwardToOffset(offset, currentItem, currentOffset, root);
-
-    if (!currentItem) {
-        // Did not find the item. On plus side, we now know the length.
-        setLengthCache(currentOffset + 1);
-        return 0;
-    }
-    setCachedElement(*currentItem, currentOffset);
-    return currentItem;
-}
-
-static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element)
-{
     // The document.all collection returns only certain types of elements by name,
     // although it returns any type of element by id.
-    return element->hasLocalName(appletTag)
-        || element->hasLocalName(embedTag)
-        || element->hasLocalName(formTag)
-        || element->hasLocalName(imgTag)
-        || element->hasLocalName(inputTag)
-        || element->hasLocalName(objectTag)
-        || element->hasLocalName(selectTag);
+    return element.hasLocalName(appletTag)
+        || element.hasLocalName(embedTag)
+        || element.hasLocalName(formTag)
+        || element.hasLocalName(imgTag)
+        || element.hasLocalName(inputTag)
+        || element.hasLocalName(objectTag)
+        || element.hasLocalName(selectTag);
 }
 
-inline Element* firstMatchingChildElement(const HTMLCollection* nodeList, ContainerNode* root)
+inline Element* firstMatchingChildElement(const HTMLCollection& nodeList, ContainerNode& root)
 {
-    Element* element = ElementTraversal::firstWithin(root);
-    while (element && !isMatchingElement(nodeList, element))
+    Element* element = ElementTraversal::firstWithin(&root);
+    while (element && !isMatchingElement(nodeList, *element))
         element = ElementTraversal::nextSibling(element);
     return element;
 }
 
-inline Element* nextMatchingSiblingElement(const HTMLCollection* nodeList, Element* current)
+inline Element* nextMatchingSiblingElement(const HTMLCollection& nodeList, Element* current)
 {
     do {
         current = ElementTraversal::nextSibling(current);
-    } while (current && !isMatchingElement(nodeList, current));
+    } while (current && !isMatchingElement(nodeList, *current));
     return current;
 }
 
-inline Element* HTMLCollection::firstElement(ContainerNode* root) const
+inline Element* HTMLCollection::firstElement(ContainerNode& root) const
 {
     if (usesCustomForwardOnlyTraversal())
         return customElementAfter(nullptr);
     if (m_shouldOnlyIncludeDirectChildren)
-        return firstMatchingChildElement(this, root);
-    return firstMatchingElement(this, root);
+        return firstMatchingChildElement(*this, root);
+    return firstMatchingElement(*this, root);
 }
 
-inline Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Element* currentElement, unsigned& currentOffset, ContainerNode* root) const
+inline Element* HTMLCollection::traverseForward(Element& current, unsigned count, unsigned& traversedCount, ContainerNode& root) const
 {
-    ASSERT_WITH_SECURITY_IMPLICATION(currentOffset < offset);
+    Element* element = &current;
     if (usesCustomForwardOnlyTraversal()) {
-        while ((currentElement = customElementAfter(currentElement))) {
-            if (++currentOffset == offset)
-                return currentElement;
+        for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+            element = customElementAfter(element);
+            if (!element)
+                return nullptr;
         }
-        return 0;
+        return element;
     }
     if (m_shouldOnlyIncludeDirectChildren) {
-        while ((currentElement = nextMatchingSiblingElement(this, currentElement))) {
-            if (++currentOffset == offset)
-                return currentElement;
+        for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+            element = nextMatchingSiblingElement(*this, element);
+            if (!element)
+                return nullptr;
         }
-        return 0;
+        return element;
     }
-    return traverseMatchingElementsForwardToOffset(this, offset, currentElement, currentOffset, root);
+    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+        element = nextMatchingElement(*this, element, root);
+        if (!element)
+            return nullptr;
+    }
+    return element;
 }
 
+Element* HTMLCollection::collectionFirst() const
+{
+    return firstElement(rootNode());
+}
+
+Element* HTMLCollection::collectionLast() const
+{
+    // FIXME: This should be optimized similarly to the forward case.
+    auto& root = rootNode();
+    Element* last = m_shouldOnlyIncludeDirectChildren ? ElementTraversal::lastChild(&root) : ElementTraversal::lastWithin(&root);
+    return iterateForPreviousElement(last);
+}
+
+Element* HTMLCollection::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
+{
+    return traverseForward(current, count, traversedCount, rootNode());
+}
+
+Element* HTMLCollection::collectionTraverseBackward(Element& current, unsigned count) const
+{
+    // FIXME: This should be optimized similarly to the forward case.
+    auto& root = rootNode();
+    Element* element = &current;
+    for (; count && element ; --count)
+        element = iterateForPreviousElement(ElementTraversal::previous(element, &root));
+    return element;
+}
+
 void HTMLCollection::invalidateCache() const
 {
-    m_cachedElement = nullptr;
-    m_isLengthCacheValid = false;
-    m_isElementCacheValid = false;
+    m_indexCache.invalidate();
     m_isNameCacheValid = false;
     m_isItemRefElementsCacheValid = false;
     m_idCache.clear();
@@ -475,14 +395,13 @@
         } else if (treeScope.hasElementWithName(*name.impl())) {
             if (!treeScope.containsMultipleElementsWithName(name)) {
                 candidate = treeScope.getElementByName(name);
-                if (candidate && type() == DocAll && (!candidate->isHTMLElement() || !nameShouldBeVisibleInDocumentAll(toHTMLElement(candidate))))
+                if (candidate && type() == DocAll && (!candidate->isHTMLElement() || !nameShouldBeVisibleInDocumentAll(toHTMLElement(*candidate))))
                     candidate = 0;
             }
         } else
             return 0;
 
-        if (candidate
-            && isMatchingElement(this, candidate)
+        if (candidate && isMatchingElement(*this, *candidate)
             && (m_shouldOnlyIncludeDirectChildren ? candidate->parentNode() == &root : candidate->isDescendantOf(&root)))
             return candidate;
     }
@@ -510,15 +429,15 @@
 
     ContainerNode& root = rootNode();
 
-    unsigned offset = 0;
-    for (Element* element = firstElement(&root); element; element = traverseForwardToOffset(offset + 1, element, offset, &root)) {
+    unsigned count;
+    for (Element* element = firstElement(root); element; element = traverseForward(*element, 1, count, root)) {
         const AtomicString& idAttrVal = element->getIdAttribute();
         if (!idAttrVal.isEmpty())
             appendIdCache(idAttrVal, element);
         if (!element->isHTMLElement())
             continue;
         const AtomicString& nameAttrVal = element->getNameAttribute();
-        if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(element))))
+        if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element))))
             appendNameCache(nameAttrVal, element);
     }

Modified: trunk/Source/WebCore/html/HTMLCollection.h (158773 => 158774)


--- trunk/Source/WebCore/html/HTMLCollection.h	2013-11-06 20:32:19 UTC (rev 158773)
+++ trunk/Source/WebCore/html/HTMLCollection.h	2013-11-06 20:38:37 UTC (rev 158774)
@@ -23,6 +23,7 @@
 #ifndef HTMLCollection_h
 #define HTMLCollection_h
 
+#include "CollectionIndexCache.h"
 #include "CollectionType.h"
 #include "ContainerNode.h"
 #include "Document.h"
@@ -51,26 +52,7 @@
     // Non-DOM API
     bool hasNamedItem(const AtomicString& name) const;
     void namedItems(const AtomicString& name, Vector<Ref<Element>>&) const;
-    bool isEmpty() const
-    {
-        if (isLengthCacheValid())
-            return !cachedLength();
-        if (isElementCacheValid())
-            return !cachedElement();
-        return !item(0);
-    }
-    bool hasExactlyOneItem() const
-    {
-        if (isLengthCacheValid())
-            return cachedLength() == 1;
-        if (isElementCacheValid())
-            return cachedElement() && !cachedElementOffset() && !item(1);
-        return item(0) && !item(1);
-    }
 
-    Element* firstElement(ContainerNode* root) const;
-    Element* traverseForwardToOffset(unsigned offset, Element* currentElement, unsigned& currentOffset, ContainerNode* root) const;
-
     bool isRootedAtDocument() const { return m_rootType == NodeListIsRootedAtDocument; }
     NodeListInvalidationType invalidationType() const { return static_cast<NodeListInvalidationType>(m_invalidationType); }
     CollectionType type() const { return static_cast<CollectionType>(m_collectionType); }
@@ -85,6 +67,13 @@
     virtual void invalidateCache() const;
     void invalidateIdNameCacheMaps() const;
 
+    // For CollectionIndexCache
+    Element* collectionFirst() const;
+    Element* collectionLast() const;
+    Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
+    Element* collectionTraverseBackward(Element&, unsigned count) const;
+    bool collectionCanTraverseBackward() const { return !m_usesCustomForwardOnlyTraversal; }
+
 protected:
     enum ElementTraversalType { NormalTraversal, CustomForwardOnlyTraversal };
     HTMLCollection(ContainerNode& base, CollectionType, ElementTraversalType = NormalTraversal);
@@ -101,24 +90,6 @@
     ContainerNode& rootNode() const;
     bool usesCustomForwardOnlyTraversal() const { return m_usesCustomForwardOnlyTraversal; }
 
-    bool isElementCacheValid() const { return m_isElementCacheValid; }
-    Element* cachedElement() const { return m_cachedElement; }
-    unsigned cachedElementOffset() const { return m_cachedElementOffset; }
-
-    bool isLengthCacheValid() const { return m_isLengthCacheValid; }
-    unsigned cachedLength() const { return m_cachedLength; }
-    void setLengthCache(unsigned length) const
-    {
-        m_cachedLength = length;
-        m_isLengthCacheValid = true;
-    }
-    void setCachedElement(Element& element, unsigned offset) const
-    {
-        m_cachedElement = &element;
-        m_cachedElementOffset = offset;
-        m_isElementCacheValid = true;
-    }
-
     bool isItemRefElementsCacheValid() const { return m_isItemRefElementsCacheValid; }
     void setItemRefElementsCacheValid() const { m_isItemRefElementsCacheValid = true; }
 
@@ -130,20 +101,16 @@
 private:
     static void append(NodeCacheMap&, const AtomicString&, Element*);
 
-    Element* elementBeforeOrAfterCachedElement(unsigned offset, ContainerNode* root) const;
-    bool isLastItemCloserThanLastOrCachedItem(unsigned offset) const;
-    bool isFirstItemCloserThanCachedItem(unsigned offset) const;
     Element* iterateForPreviousElement(Element* current) const;
-    Element* itemBefore(Element* previousItem) const;
+    Element* firstElement(ContainerNode& root) const;
+    Element* traverseForward(Element& current, unsigned count, unsigned& traversedCount, ContainerNode& root) const;
 
     virtual Element* customElementAfter(Element*) const { ASSERT_NOT_REACHED(); return nullptr; }
 
     Ref<ContainerNode> m_ownerNode;
-    mutable Element* m_cachedElement;
-    mutable unsigned m_cachedLength;
-    mutable unsigned m_cachedElementOffset;
-    mutable unsigned m_isLengthCacheValid : 1;
-    mutable unsigned m_isElementCacheValid : 1;
+
+    mutable CollectionIndexCache<HTMLCollection, Element> m_indexCache;
+
     const unsigned m_rootType : 2;
     const unsigned m_invalidationType : 4;
     const unsigned m_shouldOnlyIncludeDirectChildren : 1;

_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to