Unify HTMLCollection and DynamicNodeList
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 21 Jul 2012 01:03:17 +0000 (01:03 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 21 Jul 2012 01:03:17 +0000 (01:03 +0000)
https://bugs.webkit.org/show_bug.cgi?id=91335

Reviewed by Anders Carlsson.

This is the grand unification of HTMLCollection and DynamicNodeList.

It merges implementations of item() and length() in ChildNodeList, DynamicNodeList,
and HTMLCollection. The unified implementation is based on the one used for HTMLCollection,
that has been improved over the last few days; see r122660 and r122672 for examples.

There are five key changes:
1. Made itemBeforeOrAfter aware of DynamicNodeList.
2. itemBeforeOrAfter and related functions take and return Node* to support ChildNodeList.
3. Renamed InvalidCollectionType to NodeListCollectionType since DynamicNodeLists need to be
identified itemBeforeOrAfter.
4. Renamed itemAfter to virtualItemAfter in subclasses of HTMLCollection, and devirtualized
itemAfter used in common cases to avoid performance regressions. To make this intent clear,
SupportItemBefore and DoNotSupportItemBefore have been renamed to DoesNotOverrideItemAfter
and OverridesItemAfter. This change also help us detect a subclass of HTMLCollection that
passes in a wrong value to ItemBeforeSupportType by making forward iterations fail (hit an
assertion or doesn't iterate at all) as well as backward iterations.
5. Restricted the use of elementsArrayOffset to subclasses that provide virtualItemAfter.

This patch completes my effort to share code between HTMLCollection and DynamicNodeList.

* dom/ChildNodeList.cpp:
(WebCore::ChildNodeList::ChildNodeList):
(WebCore): Removed length() and item().
(WebCore::ChildNodeList::nodeMatches):
* dom/ChildNodeList.h:
(ChildNodeList):
* dom/ClassNodeList.cpp:
(WebCore::ClassNodeList::ClassNodeList):
* dom/Document.cpp:
(WebCore::Document::registerNodeListCache):
(WebCore::Document::unregisterNodeListCache):
* dom/DynamicNodeList.cpp:
(WebCore::DynamicNodeListCacheBase::invalidateCache):
(WebCore::DynamicNodeList::length):
(WebCore::DynamicNodeList::item):
* dom/DynamicNodeList.h:
(WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): Takes new boolean argument
shouldOnlyIncludeDirectChildren indicating whether the non-child descendents should be
included or not. This is necessary to identify ChildNodeList in itemBeforeOrAfter.
(WebCore::DynamicNodeListCacheBase::ownerNode): Moved from DynamicNodeListCacheBase and
HTMLCollectionCacheBase.
(WebCore::DynamicNodeListCacheBase::document): Moved from DynamicNodeListCacheBase.
(WebCore::DynamicNodeListCacheBase::rootNode): Ditto.
(WebCore::DynamicNodeListCacheBase::overridesItemAfter): Renamed from supportsItemBefore
and the return value has been negated.
(WebCore::DynamicNodeListCacheBase::shouldOnlyIncludeDirectChildren): Added.
(WebCore::DynamicNodeListCacheBase):
(WebCore::DynamicNodeList::DynamicNodeList): Takes NodeListType to determine the value of
shouldOnlyIncludeDirectChildren.
(DynamicNodeList):
(WebCore::DynamicSubtreeNodeList::~DynamicSubtreeNodeList):
(WebCore::DynamicSubtreeNodeList::DynamicSubtreeNodeList):
* dom/MicroDataItemList.cpp:
(WebCore::MicroDataItemList::MicroDataItemList):
* dom/NameNodeList.cpp:
(WebCore::NameNodeList::NameNodeList):
* dom/TagNodeList.cpp:
(WebCore::TagNodeList::TagNodeList):
* html/CollectionType.h:
* html/HTMLAllCollection.cpp:
(WebCore::HTMLAllCollection::HTMLAllCollection):
* html/HTMLCollection.cpp:
(WebCore::shouldOnlyIncludeDirectChildren):
(WebCore::rootTypeFromCollectionType):
(WebCore::invalidationTypeExcludingIdAndNameAttributes):
(WebCore::HTMLCollection::HTMLCollection):
(WebCore::HTMLCollection::create):
(WebCore::HTMLCollection::~HTMLCollection):
(WebCore::isAcceptableElement):
(WebCore::firstNode): Extracted from itemBeforeOrAfter.
(WebCore::DynamicNodeListCacheBase::iterateForNextNode): Ditto.
(WebCore::DynamicNodeListCacheBase::itemBeforeOrAfter): Takes and returns Node*.
Special case ChildNodeList since there is no need to skip any node. When "this" is a
node list, call nodeMatches instead of isAcceptableElement.
(WebCore::DynamicNodeListCacheBase::itemBefore): No longer takes offsetInArray since
the use of elementsArrayOffset has been restricted to HTMLCollections that provides
virtualItemAfter.
(WebCore::DynamicNodeListCacheBase::itemAfter): Calls virtualItemAfter if necessary.
Otherwise assert offsetInArray is zero since we should never be using this variable
when virtualItemAfter is not provided.
(WebCore::DynamicNodeListCacheBase::isLastItemCloserThanLastOrCachedItem):
(WebCore::DynamicNodeListCacheBase::isFirstItemCloserThanCachedItem):
(WebCore::DynamicNodeListCacheBase::setItemCache): Updates m_cachedElementsArrayOffset
in HTMLCollection if and only if virtualItemAfter is provided. This is safe because
node lists never provide virtualItemAfter.
(WebCore::DynamicNodeListCacheBase::cachedElementsArrayOffset): Similarly, returns
m_cachedElementsArrayOffset if virtualItemAfter is provided.
(WebCore::DynamicNodeListCacheBase::lengthCommon):
(WebCore::DynamicNodeListCacheBase::itemCommon): Note that supportsItemBefore() is
equivalent to !overridesItemAfter() here.
(WebCore::DynamicNodeListCacheBase::itemBeforeOrAfterCachedItem): Uses Node* through
out the function. Since itemBefore never uses offsetInArray, always sets 0 for that.
Note that we never call itemBefore and virtualItemAfter on the same object.
(WebCore::HTMLCollection::virtualItemAfter): Added only to make the class "concrete".
(WebCore::HTMLCollection::namedItem):
(WebCore::HTMLCollection::updateNameCache):
(WebCore::HTMLCollection::tags):
* html/HTMLCollection.h:
(WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase):
(HTMLCollectionCacheBase):
(WebCore::HTMLCollection::length):
(WebCore::HTMLCollection::item):
(WebCore::HTMLCollection::base):
(HTMLCollection):
* html/HTMLFormCollection.cpp:
(WebCore::HTMLFormCollection::HTMLFormCollection):
(WebCore::HTMLFormCollection::virtualItemAfter):
* html/HTMLFormCollection.h:
(HTMLFormCollection):
* html/HTMLNameCollection.cpp:
(WebCore::HTMLNameCollection::HTMLNameCollection):
(WebCore::HTMLNameCollection::virtualItemAfter):
* html/HTMLNameCollection.h:
(HTMLNameCollection):
* html/HTMLOptionsCollection.cpp:
(WebCore::HTMLOptionsCollection::HTMLOptionsCollection):
* html/HTMLPropertiesCollection.cpp:
(WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
(WebCore::HTMLPropertiesCollection::virtualItemAfter):
(WebCore::HTMLPropertiesCollection::updateNameCache):
* html/HTMLPropertiesCollection.h:
(HTMLPropertiesCollection):
* html/HTMLTableRowsCollection.cpp:
(WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection):
(WebCore::HTMLTableRowsCollection::virtualItemAfter):
* html/HTMLTableRowsCollection.h:
(HTMLTableRowsCollection):
* html/LabelsNodeList.cpp:
(WebCore::LabelsNodeList::LabelsNodeList):
* html/RadioNodeList.cpp:
(WebCore::RadioNodeList::RadioNodeList):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@123281 268f45cc-cd09-0410-ab3c-d52691b4dbfc

25 files changed:
Source/WebCore/ChangeLog
Source/WebCore/dom/ChildNodeList.cpp
Source/WebCore/dom/ChildNodeList.h
Source/WebCore/dom/ClassNodeList.cpp
Source/WebCore/dom/Document.cpp
Source/WebCore/dom/DynamicNodeList.cpp
Source/WebCore/dom/DynamicNodeList.h
Source/WebCore/dom/MicroDataItemList.cpp
Source/WebCore/dom/NameNodeList.cpp
Source/WebCore/dom/TagNodeList.cpp
Source/WebCore/html/CollectionType.h
Source/WebCore/html/HTMLAllCollection.cpp
Source/WebCore/html/HTMLCollection.cpp
Source/WebCore/html/HTMLCollection.h
Source/WebCore/html/HTMLFormCollection.cpp
Source/WebCore/html/HTMLFormCollection.h
Source/WebCore/html/HTMLNameCollection.cpp
Source/WebCore/html/HTMLNameCollection.h
Source/WebCore/html/HTMLOptionsCollection.cpp
Source/WebCore/html/HTMLPropertiesCollection.cpp
Source/WebCore/html/HTMLPropertiesCollection.h
Source/WebCore/html/HTMLTableRowsCollection.cpp
Source/WebCore/html/HTMLTableRowsCollection.h
Source/WebCore/html/LabelsNodeList.cpp
Source/WebCore/html/RadioNodeList.cpp

index bb48fc2..03bda28 100644 (file)
@@ -1,3 +1,143 @@
+2012-07-18  Ryosuke Niwa  <rniwa@webkit.org>
+
+        Unify HTMLCollection and DynamicNodeList
+        https://bugs.webkit.org/show_bug.cgi?id=91335
+
+        Reviewed by Anders Carlsson.
+
+        This is the grand unification of HTMLCollection and DynamicNodeList.
+
+        It merges implementations of item() and length() in ChildNodeList, DynamicNodeList,
+        and HTMLCollection. The unified implementation is based on the one used for HTMLCollection,
+        that has been improved over the last few days; see r122660 and r122672 for examples.
+
+        There are five key changes:
+        1. Made itemBeforeOrAfter aware of DynamicNodeList.
+        2. itemBeforeOrAfter and related functions take and return Node* to support ChildNodeList.
+        3. Renamed InvalidCollectionType to NodeListCollectionType since DynamicNodeLists need to be
+        identified itemBeforeOrAfter.
+        4. Renamed itemAfter to virtualItemAfter in subclasses of HTMLCollection, and devirtualized
+        itemAfter used in common cases to avoid performance regressions. To make this intent clear,
+        SupportItemBefore and DoNotSupportItemBefore have been renamed to DoesNotOverrideItemAfter
+        and OverridesItemAfter. This change also help us detect a subclass of HTMLCollection that
+        passes in a wrong value to ItemBeforeSupportType by making forward iterations fail (hit an
+        assertion or doesn't iterate at all) as well as backward iterations.
+        5. Restricted the use of elementsArrayOffset to subclasses that provide virtualItemAfter.
+
+        This patch completes my effort to share code between HTMLCollection and DynamicNodeList.
+
+        * dom/ChildNodeList.cpp:
+        (WebCore::ChildNodeList::ChildNodeList):
+        (WebCore): Removed length() and item().
+        (WebCore::ChildNodeList::nodeMatches):
+        * dom/ChildNodeList.h:
+        (ChildNodeList):
+        * dom/ClassNodeList.cpp:
+        (WebCore::ClassNodeList::ClassNodeList):
+        * dom/Document.cpp:
+        (WebCore::Document::registerNodeListCache):
+        (WebCore::Document::unregisterNodeListCache):
+        * dom/DynamicNodeList.cpp:
+        (WebCore::DynamicNodeListCacheBase::invalidateCache):
+        (WebCore::DynamicNodeList::length):
+        (WebCore::DynamicNodeList::item):
+        * dom/DynamicNodeList.h:
+        (WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): Takes new boolean argument
+        shouldOnlyIncludeDirectChildren indicating whether the non-child descendents should be
+        included or not. This is necessary to identify ChildNodeList in itemBeforeOrAfter.
+        (WebCore::DynamicNodeListCacheBase::ownerNode): Moved from DynamicNodeListCacheBase and
+        HTMLCollectionCacheBase.
+        (WebCore::DynamicNodeListCacheBase::document): Moved from DynamicNodeListCacheBase.
+        (WebCore::DynamicNodeListCacheBase::rootNode): Ditto.
+        (WebCore::DynamicNodeListCacheBase::overridesItemAfter): Renamed from supportsItemBefore
+        and the return value has been negated.
+        (WebCore::DynamicNodeListCacheBase::shouldOnlyIncludeDirectChildren): Added.
+        (WebCore::DynamicNodeListCacheBase):
+        (WebCore::DynamicNodeList::DynamicNodeList): Takes NodeListType to determine the value of
+        shouldOnlyIncludeDirectChildren.
+        (DynamicNodeList):
+        (WebCore::DynamicSubtreeNodeList::~DynamicSubtreeNodeList):
+        (WebCore::DynamicSubtreeNodeList::DynamicSubtreeNodeList):
+        * dom/MicroDataItemList.cpp:
+        (WebCore::MicroDataItemList::MicroDataItemList):
+        * dom/NameNodeList.cpp:
+        (WebCore::NameNodeList::NameNodeList):
+        * dom/TagNodeList.cpp:
+        (WebCore::TagNodeList::TagNodeList):
+        * html/CollectionType.h:
+        * html/HTMLAllCollection.cpp:
+        (WebCore::HTMLAllCollection::HTMLAllCollection):
+        * html/HTMLCollection.cpp:
+        (WebCore::shouldOnlyIncludeDirectChildren):
+        (WebCore::rootTypeFromCollectionType):
+        (WebCore::invalidationTypeExcludingIdAndNameAttributes):
+        (WebCore::HTMLCollection::HTMLCollection):
+        (WebCore::HTMLCollection::create):
+        (WebCore::HTMLCollection::~HTMLCollection):
+        (WebCore::isAcceptableElement):
+        (WebCore::firstNode): Extracted from itemBeforeOrAfter.
+        (WebCore::DynamicNodeListCacheBase::iterateForNextNode): Ditto.
+        (WebCore::DynamicNodeListCacheBase::itemBeforeOrAfter): Takes and returns Node*.
+        Special case ChildNodeList since there is no need to skip any node. When "this" is a
+        node list, call nodeMatches instead of isAcceptableElement.
+        (WebCore::DynamicNodeListCacheBase::itemBefore): No longer takes offsetInArray since
+        the use of elementsArrayOffset has been restricted to HTMLCollections that provides
+        virtualItemAfter.
+        (WebCore::DynamicNodeListCacheBase::itemAfter): Calls virtualItemAfter if necessary.
+        Otherwise assert offsetInArray is zero since we should never be using this variable
+        when virtualItemAfter is not provided.
+        (WebCore::DynamicNodeListCacheBase::isLastItemCloserThanLastOrCachedItem):
+        (WebCore::DynamicNodeListCacheBase::isFirstItemCloserThanCachedItem):
+        (WebCore::DynamicNodeListCacheBase::setItemCache): Updates m_cachedElementsArrayOffset
+        in HTMLCollection if and only if virtualItemAfter is provided. This is safe because
+        node lists never provide virtualItemAfter.
+        (WebCore::DynamicNodeListCacheBase::cachedElementsArrayOffset): Similarly, returns
+        m_cachedElementsArrayOffset if virtualItemAfter is provided.
+        (WebCore::DynamicNodeListCacheBase::lengthCommon):
+        (WebCore::DynamicNodeListCacheBase::itemCommon): Note that supportsItemBefore() is
+        equivalent to !overridesItemAfter() here.
+        (WebCore::DynamicNodeListCacheBase::itemBeforeOrAfterCachedItem): Uses Node* through
+        out the function. Since itemBefore never uses offsetInArray, always sets 0 for that.
+        Note that we never call itemBefore and virtualItemAfter on the same object.
+        (WebCore::HTMLCollection::virtualItemAfter): Added only to make the class "concrete".
+        (WebCore::HTMLCollection::namedItem):
+        (WebCore::HTMLCollection::updateNameCache):
+        (WebCore::HTMLCollection::tags):
+        * html/HTMLCollection.h:
+        (WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase):
+        (HTMLCollectionCacheBase):
+        (WebCore::HTMLCollection::length):
+        (WebCore::HTMLCollection::item):
+        (WebCore::HTMLCollection::base):
+        (HTMLCollection):
+        * html/HTMLFormCollection.cpp:
+        (WebCore::HTMLFormCollection::HTMLFormCollection):
+        (WebCore::HTMLFormCollection::virtualItemAfter):
+        * html/HTMLFormCollection.h:
+        (HTMLFormCollection):
+        * html/HTMLNameCollection.cpp:
+        (WebCore::HTMLNameCollection::HTMLNameCollection):
+        (WebCore::HTMLNameCollection::virtualItemAfter):
+        * html/HTMLNameCollection.h:
+        (HTMLNameCollection):
+        * html/HTMLOptionsCollection.cpp:
+        (WebCore::HTMLOptionsCollection::HTMLOptionsCollection):
+        * html/HTMLPropertiesCollection.cpp:
+        (WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
+        (WebCore::HTMLPropertiesCollection::virtualItemAfter):
+        (WebCore::HTMLPropertiesCollection::updateNameCache):
+        * html/HTMLPropertiesCollection.h:
+        (HTMLPropertiesCollection):
+        * html/HTMLTableRowsCollection.cpp:
+        (WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection):
+        (WebCore::HTMLTableRowsCollection::virtualItemAfter):
+        * html/HTMLTableRowsCollection.h:
+        (HTMLTableRowsCollection):
+        * html/LabelsNodeList.cpp:
+        (WebCore::LabelsNodeList::LabelsNodeList):
+        * html/RadioNodeList.cpp:
+        (WebCore::RadioNodeList::RadioNodeList):
+
 2012-07-20  Joshua Bell  <jsbell@chromium.org>
 
         IndexedDB: Simplify backend interface classes
index 86fab6f..fe55892 100644 (file)
@@ -28,7 +28,7 @@
 namespace WebCore {
 
 ChildNodeList::ChildNodeList(PassRefPtr<Node> node)
-    : DynamicNodeList(node, NodeListIsRootedAtNode, DoNotInvalidateOnAttributeChanges)
+    : DynamicNodeList(node, ChildNodeListType, NodeListIsRootedAtNode, DoNotInvalidateOnAttributeChanges)
 {
 }
 
@@ -37,73 +37,9 @@ ChildNodeList::~ChildNodeList()
     ownerNode()->removeCachedChildNodeList();
 }
 
-unsigned ChildNodeList::length() const
-{
-    if (isLengthCacheValid())
-        return cachedLength();
-
-    unsigned len = 0;
-    for (Node* n = rootNode()->firstChild(); n; n = n->nextSibling())
-        len++;
-
-    setLengthCache(len);
-
-    return len;
-}
-
-Node* ChildNodeList::item(unsigned index) const
-{
-    unsigned int pos = 0;
-    Node* n = rootNode()->firstChild();
-
-    if (isItemCacheValid()) {
-        if (index == cachedItemOffset())
-            return cachedItem();
-
-        int diff = index - cachedItemOffset();
-        unsigned dist = abs(diff);
-        if (dist < index) {
-            n = cachedItem();
-            pos = cachedItemOffset();
-        }
-    }
-
-    if (isLengthCacheValid()) {
-        if (index >= cachedLength())
-            return 0;
-
-        int diff = index - pos;
-        unsigned dist = abs(diff);
-        if (dist > cachedLength() - 1 - index) {
-            n = rootNode()->lastChild();
-            pos = cachedLength() - 1;
-        }
-    }
-
-    if (pos <= index) {
-        while (n && pos < index) {
-            n = n->nextSibling();
-            ++pos;
-        }
-    } else {
-        while (n && pos > index) {
-            n = n->previousSibling();
-            --pos;
-        }
-    }
-
-    if (n) {
-        setItemCache(n, pos);
-        return n;
-    }
-
-    return 0;
-}
-
 bool ChildNodeList::nodeMatches(Element* testNode) const
 {
-    // Note: Due to the overrides of the length and item functions above,
-    // this function will be called only by DynamicNodeList::itemWithName,
+    // This function will be called only by DynamicNodeList::itemWithName,
     // for an element that was located with getElementById.
     return testNode->parentNode() == rootNode();
 }
index df3d67b..243e897 100644 (file)
@@ -38,9 +38,6 @@ namespace WebCore {
 
         virtual ~ChildNodeList();
 
-        virtual unsigned length() const;
-        virtual Node* item(unsigned index) const;
-
     protected:
         ChildNodeList(PassRefPtr<Node> rootNode);
 
index 14db324..c0ce6d2 100644 (file)
@@ -37,7 +37,7 @@
 namespace WebCore {
 
 ClassNodeList::ClassNodeList(PassRefPtr<Node> rootNode, const String& classNames)
-    : DynamicSubtreeNodeList(rootNode, InvalidateOnClassAttrChange)
+    : DynamicSubtreeNodeList(rootNode, ClassNodeListType, InvalidateOnClassAttrChange)
     , m_classNames(classNames, document()->inQuirksMode())
     , m_originalClassNames(classNames)
 {
index 74d48e8..3449ff0 100644 (file)
@@ -3882,7 +3882,7 @@ void Document::setCSSTarget(Element* n)
 
 void Document::registerNodeListCache(DynamicNodeListCacheBase* list)
 {
-    if (list->type() != InvalidCollectionType)
+    if (list->type() != NodeListCollectionType)
         m_nodeListCounts[InvalidateOnIdNameAttrChange]++;
     m_nodeListCounts[list->invalidationType()]++;
     if (list->isRootedAtDocument())
@@ -3891,7 +3891,7 @@ void Document::registerNodeListCache(DynamicNodeListCacheBase* list)
 
 void Document::unregisterNodeListCache(DynamicNodeListCacheBase* list)
 {
-    if (list->type() != InvalidCollectionType)
+    if (list->type() != NodeListCollectionType)
         m_nodeListCounts[InvalidateOnIdNameAttrChange]--;
     m_nodeListCounts[list->invalidationType()]--;
     if (list->isRootedAtDocument()) {
index 25a4504..96e0082 100644 (file)
@@ -36,7 +36,7 @@ void DynamicNodeListCacheBase::invalidateCache() const
     m_isLengthCacheValid = false;
     m_isItemCacheValid = false;
     m_isNameCacheValid = false;
-    if (type() == InvalidCollectionType)
+    if (type() == NodeListCollectionType)
         return;
 
     const HTMLCollectionCacheBase* cacheBase = static_cast<const HTMLCollectionCacheBase*>(this);
@@ -51,72 +51,14 @@ void DynamicNodeListCacheBase::invalidateCache() const
 #endif
 }
 
-unsigned DynamicSubtreeNodeList::length() const
+unsigned DynamicNodeList::length() const
 {
-    if (isLengthCacheValid())
-        return cachedLength();
-
-    unsigned length = 0;
-    Node* rootNode = this->rootNode();
-
-    for (Node* n = rootNode->firstChild(); n; n = n->traverseNextNode(rootNode))
-        length += n->isElementNode() && nodeMatches(static_cast<Element*>(n));
-
-    setLengthCache(length);
-
-    return length;
+    return lengthCommon();
 }
 
-Node* DynamicSubtreeNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
+Node* DynamicNodeList::item(unsigned offset) const
 {
-    ASSERT(remainingOffset >= 0);
-    Node* rootNode = this->rootNode();
-    for (Node* n = start; n; n = n->traverseNextNode(rootNode)) {
-        if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
-            if (!remainingOffset) {
-                setItemCache(n, offset);
-                return n;
-            }
-            --remainingOffset;
-        }
-    }
-
-    return 0; // no matching node in this subtree
-}
-
-Node* DynamicSubtreeNodeList::itemBackwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
-{
-    ASSERT(remainingOffset < 0);
-    Node* rootNode = this->rootNode();
-    for (Node* n = start; n; n = n->traversePreviousNode(rootNode)) {
-        if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
-            if (!remainingOffset) {
-                setItemCache(n, offset);
-                return n;
-            }
-            ++remainingOffset;
-        }
-    }
-
-    return 0; // no matching node in this subtree
-}
-
-Node* DynamicSubtreeNodeList::item(unsigned offset) const
-{
-    int remainingOffset = offset;
-    Node* start = rootNode()->firstChild();
-    if (isItemCacheValid()) {
-        if (offset == cachedItemOffset())
-            return cachedItem();
-        if (offset > cachedItemOffset() || cachedItemOffset() - offset < offset) {
-            start = cachedItem();
-            remainingOffset -= cachedItemOffset();
-        }
-    }
-
-    if (remainingOffset < 0)
-        return itemBackwardsFromCurrent(start, offset, remainingOffset);
-    return itemForwardsFromCurrent(start, offset, remainingOffset);
+    return itemCommon(offset);
 }
 
 Node* DynamicNodeList::itemWithName(const AtomicString& elementId) const
index c1c05f4..a5cd269 100644 (file)
@@ -43,31 +43,34 @@ enum NodeListRootType {
 
 class DynamicNodeListCacheBase {
 public:
-    enum ItemBeforeSupportType {
-        DoNotSupportItemBefore,
-        SupportItemBefore,
+    enum ItemAfterOverrideType {
+        OverridesItemAfter,
+        DoesNotOverrideItemAfter,
     };
 
-    DynamicNodeListCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType,
-        CollectionType collectionType = InvalidCollectionType, ItemBeforeSupportType itemBeforeSupportType = DoNotSupportItemBefore)
-        : m_cachedItem(0)
+    DynamicNodeListCacheBase(Node* ownerNode, NodeListRootType rootType, NodeListInvalidationType invalidationType,
+        bool shouldOnlyIncludeDirectChildren, CollectionType collectionType, ItemAfterOverrideType itemAfterOverrideType)
+        : m_ownerNode(ownerNode)
+        , m_cachedItem(0)
         , m_isLengthCacheValid(false)
         , m_isItemCacheValid(false)
         , m_rootedAtDocument(rootType == NodeListIsRootedAtDocument)
         , m_invalidationType(invalidationType)
+        , m_shouldOnlyIncludeDirectChildren(shouldOnlyIncludeDirectChildren)
         , m_isNameCacheValid(false)
         , m_collectionType(collectionType)
-        , m_supportsItemBefore(itemBeforeSupportType == SupportItemBefore)
+        , m_overridesItemAfter(itemAfterOverrideType == OverridesItemAfter)
     {
         ASSERT(m_invalidationType == static_cast<unsigned>(invalidationType));
         ASSERT(m_collectionType == static_cast<unsigned>(collectionType));
+        ASSERT(!m_overridesItemAfter || m_collectionType != NodeListCollectionType);
     }
 
 public:
     ALWAYS_INLINE bool isRootedAtDocument() const { return m_rootedAtDocument; }
     ALWAYS_INLINE NodeListInvalidationType invalidationType() const { return static_cast<NodeListInvalidationType>(m_invalidationType); }
     ALWAYS_INLINE CollectionType type() const { return static_cast<CollectionType>(m_collectionType); }
-
+    Node* ownerNode() const { return m_ownerNode.get(); }
     ALWAYS_INLINE void invalidateCache(const QualifiedName* attrName) const
     {
         if (!attrName || shouldInvalidateTypeOnAttributeChange(invalidationType(), *attrName))
@@ -78,11 +81,19 @@ public:
     static bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType, const QualifiedName&);
 
 protected:
-    bool supportsItemBefore() const { return m_supportsItemBefore; }
+    Document* document() const { return m_ownerNode->document(); }
+    Node* rootNode() const
+    {
+        if (isRootedAtDocument() && m_ownerNode->inDocument())
+            return m_ownerNode->document();
+        return m_ownerNode.get();
+    }
+    bool overridesItemAfter() const { return m_overridesItemAfter; }
 
     ALWAYS_INLINE bool isItemCacheValid() const { return m_isItemCacheValid; }
     ALWAYS_INLINE Node* cachedItem() const { return m_cachedItem; }
     ALWAYS_INLINE unsigned cachedItemOffset() const { return m_cachedItemOffset; }
+    unsigned cachedElementsArrayOffset() const;
 
     ALWAYS_INLINE bool isLengthCacheValid() const { return m_isLengthCacheValid; }
     ALWAYS_INLINE unsigned cachedLength() const { return m_cachedLength; }
@@ -98,11 +109,25 @@ protected:
         m_cachedItemOffset = offset;
         m_isItemCacheValid = true;
     }
+    void setItemCache(Node* item, unsigned offset, unsigned elementsArrayOffset) const;
 
     bool hasNameCache() const { return m_isNameCacheValid; }
     void setHasNameCache() const { m_isNameCacheValid = true; }
 
+    unsigned lengthCommon() const;
+    Node* itemCommon(unsigned offset) const;
+    Node* itemBeforeOrAfterCachedItem(unsigned offset) const;
+    Node* itemAfter(unsigned&, Node* previousItem) const;
+
 private:
+    bool shouldOnlyIncludeDirectChildren() const { return m_shouldOnlyIncludeDirectChildren; }
+    bool isLastItemCloserThanLastOrCachedItem(unsigned offset) const;
+    bool isFirstItemCloserThanCachedItem(unsigned offset) const;
+    template <bool forward> Node* iterateForNextNode(Node* current) const;
+    template<bool forward> Node* itemBeforeOrAfter(Node* previousItem) const;    
+    Node* itemBefore(Node* previousItem) const;
+
+    RefPtr<Node> m_ownerNode;
     mutable Node* m_cachedItem;
     mutable unsigned m_cachedLength;
     mutable unsigned m_cachedItemOffset;
@@ -110,11 +135,12 @@ private:
     mutable unsigned m_isItemCacheValid : 1;
     const unsigned m_rootedAtDocument : 1;
     const unsigned m_invalidationType : 4;
+    const unsigned m_shouldOnlyIncludeDirectChildren : 1;
 
     // From HTMLCollection
     mutable unsigned m_isNameCacheValid : 1;
     const unsigned m_collectionType : 5;
-    const unsigned m_supportsItemBefore : 1;
+    const unsigned m_overridesItemAfter : 1;
 };
 
 ALWAYS_INLINE bool DynamicNodeListCacheBase::shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType type, const QualifiedName& attrName)
@@ -156,33 +182,21 @@ public:
         LabelsNodeListType,
         MicroDataItemListType,
     };
-    DynamicNodeList(PassRefPtr<Node> ownerNode, NodeListRootType rootType, NodeListInvalidationType invalidationType)
-        : DynamicNodeListCacheBase(rootType, invalidationType)
-        , m_ownerNode(ownerNode)
+    DynamicNodeList(PassRefPtr<Node> ownerNode, NodeListType type, NodeListRootType rootType, NodeListInvalidationType invalidationType)
+        : DynamicNodeListCacheBase(ownerNode.get(), rootType, invalidationType, type == ChildNodeListType, NodeListCollectionType, DoesNotOverrideItemAfter)
     { }
     virtual ~DynamicNodeList() { }
 
     // DOM methods & attributes for NodeList
-    virtual unsigned length() const = 0;
-    virtual Node* item(unsigned index) const = 0;
+    virtual unsigned length() const OVERRIDE;
+    virtual Node* item(unsigned offset) const OVERRIDE;
     virtual Node* itemWithName(const AtomicString&) const;
 
     // Other methods (not part of DOM)
-    Node* ownerNode() const { return m_ownerNode.get(); }
-
-protected:
-    Node* rootNode() const
-    {
-        if (isRootedAtDocument() && m_ownerNode->inDocument())
-            return m_ownerNode->document();
-        return m_ownerNode.get();
-    }
-    Document* document() const { return m_ownerNode->document(); }
     virtual bool nodeMatches(Element*) const = 0;
 
 private:
     virtual bool isDynamicNodeList() const OVERRIDE { return true; }
-    RefPtr<Node> m_ownerNode;
 };
 
 class DynamicSubtreeNodeList : public DynamicNodeList {
@@ -191,12 +205,10 @@ public:
     {
         document()->unregisterNodeListCache(this);
     }
-    virtual unsigned length() const OVERRIDE;
-    virtual Node* item(unsigned index) const OVERRIDE;
 
 protected:
-    DynamicSubtreeNodeList(PassRefPtr<Node> node, NodeListInvalidationType invalidationType, NodeListRootType rootType = NodeListIsRootedAtNode)
-        : DynamicNodeList(node, rootType, invalidationType)
+    DynamicSubtreeNodeList(PassRefPtr<Node> node, NodeListType type, NodeListInvalidationType invalidationType, NodeListRootType rootType = NodeListIsRootedAtNode)
+        : DynamicNodeList(node, type, rootType, invalidationType)
     {
         document()->registerNodeListCache(this);
     }
index 7b48635..6fc5393 100644 (file)
@@ -45,7 +45,7 @@ const String& MicroDataItemList::undefinedItemType()
 }
 
 MicroDataItemList::MicroDataItemList(PassRefPtr<Node> rootNode, const String& typeNames)
-    : DynamicSubtreeNodeList(rootNode, InvalidateOnItemAttrChange)
+    : DynamicSubtreeNodeList(rootNode, MicroDataItemListType, InvalidateOnItemAttrChange)
     , m_typeNames(typeNames, document()->inQuirksMode())
     , m_originalTypeNames(typeNames)
 {
index 34d5a53..0c9e089 100644 (file)
@@ -33,7 +33,7 @@ namespace WebCore {
 using namespace HTMLNames;
 
 NameNodeList::NameNodeList(PassRefPtr<Node> rootNode, const AtomicString& name)
-    : DynamicSubtreeNodeList(rootNode, InvalidateOnNameAttrChange)
+    : DynamicSubtreeNodeList(rootNode, NameNodeListType, InvalidateOnNameAttrChange)
     , m_name(name)
 {
 }
index 295a8d9..a832a6c 100644 (file)
@@ -31,7 +31,7 @@
 namespace WebCore {
 
 TagNodeList::TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName)
-    : DynamicSubtreeNodeList(rootNode, DoNotInvalidateOnAttributeChanges)
+    : DynamicSubtreeNodeList(rootNode, TagNodeListType, DoNotInvalidateOnAttributeChanges)
     , m_namespaceURI(namespaceURI)
     , m_localName(localName)
 {
index 9cd70ce..ab03ce6 100644 (file)
@@ -61,7 +61,7 @@ enum CollectionType {
 #endif
 
     FormControls,
-    InvalidCollectionType
+    NodeListCollectionType
 };
 
 static const CollectionType FirstUnnamedDocumentCachedType = DocImages;
index e769b26..1dd5c15 100644 (file)
@@ -36,7 +36,7 @@ PassRefPtr<HTMLAllCollection> HTMLAllCollection::create(Document* document)
 }
 
 HTMLAllCollection::HTMLAllCollection(Document* document)
-    : HTMLCollection(document, DocAll, SupportItemBefore)
+    : HTMLCollection(document, DocAll, DoesNotOverrideItemAfter)
 {
 }
 
index 2b53edd..57953ac 100644 (file)
@@ -69,7 +69,7 @@ static bool shouldOnlyIncludeDirectChildren(CollectionType type)
     case TSectionRows:
     case TableTBodies:
         return true;
-    case InvalidCollectionType:
+    case NodeListCollectionType:
         break;
     }
     ASSERT_NOT_REACHED();
@@ -104,7 +104,7 @@ static NodeListRootType rootTypeFromCollectionType(CollectionType type)
     case SelectedOptions:
     case DataListOptions:
     case MapAreas:
-    case InvalidCollectionType:
+    case NodeListCollectionType:
         return NodeListIsRootedAtNode;
     }
     ASSERT_NOT_REACHED();
@@ -144,7 +144,7 @@ static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(Col
 #endif
     case FormControls:
         return InvalidateForFormControls;
-    case InvalidCollectionType:
+    case NodeListCollectionType:
         break;
     }
     ASSERT_NOT_REACHED();
@@ -152,17 +152,16 @@ static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(Col
 }
     
 
-HTMLCollection::HTMLCollection(Node* base, CollectionType type, ItemBeforeSupportType itemBeforeSupportType)
-    : HTMLCollectionCacheBase(rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type, itemBeforeSupportType)
-    , m_base(base)
+HTMLCollection::HTMLCollection(Node* ownerNode, CollectionType type, ItemAfterOverrideType itemAfterOverrideType)
+    : HTMLCollectionCacheBase(ownerNode, rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type),
+        WebCore::shouldOnlyIncludeDirectChildren(type), type, itemAfterOverrideType)
 {
-    ASSERT(m_base);
-    m_base->document()->registerNodeListCache(this);
+    document()->registerNodeListCache(this);
 }
 
 PassRefPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
 {
-    return adoptRef(new HTMLCollection(base, type, SupportItemBefore));
+    return adoptRef(new HTMLCollection(base, type, DoesNotOverrideItemAfter));
 }
 
 HTMLCollection::~HTMLCollection()
@@ -176,7 +175,7 @@ HTMLCollection::~HTMLCollection()
     } else // HTMLNameCollection removes cache by itself.
         ASSERT(type() == WindowNamedItems || type() == DocumentNamedItems);
 
-    m_base->document()->unregisterNodeListCache(this);
+    document()->unregisterNodeListCache(this);
 }
 
 static inline bool isAcceptableElement(CollectionType type, Element* element)
@@ -231,7 +230,7 @@ static inline bool isAcceptableElement(CollectionType type, Element* element)
     case DocumentNamedItems:
     case TableRows:
     case WindowNamedItems:
-    case InvalidCollectionType:
+    case NodeListCollectionType:
         ASSERT_NOT_REACHED();
     }
     return false;
@@ -254,41 +253,65 @@ static inline Node* lastDescendent(Node* node)
     return node;
 }
 
-template<bool forward>
-static Element* itemBeforeOrAfter(CollectionType type, Node* base, unsigned& offsetInArray, Node* previous)
+static Node* firstNode(bool forward, Node* rootNode, bool onlyIncludeDirectChildren)
 {
-    ASSERT_UNUSED(offsetInArray, !offsetInArray);
-    bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren(type);
-    Node* rootNode = base;
-    Node* current;
-    if (previous)
-        current = nextNode<forward>(rootNode, previous, onlyIncludeDirectChildren);
-    else {
-        if (forward)
-            current = rootNode->firstChild();
-        else
-            current = onlyIncludeDirectChildren ? rootNode->lastChild() : lastDescendent(rootNode);
-    }
+    if (forward)
+        return rootNode->firstChild();
+    else
+        return onlyIncludeDirectChildren ? rootNode->lastChild() : lastDescendent(rootNode);
+}
 
+template <bool forward>
+Node* DynamicNodeListCacheBase::iterateForNextNode(Node* current) const
+{
+    bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren();
+    CollectionType collectionType = type();
+    Node* rootNode = this->rootNode();
     for (; current; current = nextNode<forward>(rootNode, current, onlyIncludeDirectChildren)) {
-        if (current->isElementNode() && isAcceptableElement(type, toElement(current)))
-            return toElement(current);
+        if (collectionType == NodeListCollectionType) {
+            if (current->isElementNode() && static_cast<const DynamicNodeList*>(this)->nodeMatches(toElement(current)))
+                return toElement(current);
+        } else {
+            if (current->isElementNode() && isAcceptableElement(collectionType, toElement(current)))
+                return toElement(current);
+        }
     }
 
     return 0;
 }
 
-Element* HTMLCollection::itemBefore(unsigned& offsetInArray, Element* previous) const
+// Without this ALWAYS_INLINE, length() and item() can be 100% slower.
+template<bool forward> ALWAYS_INLINE
+Node* DynamicNodeListCacheBase::itemBeforeOrAfter(Node* previous) const
+{
+    Node* current;
+    if (LIKELY(!!previous)) // Without this LIKELY, length() and item() can be 10% slower.
+        current = nextNode<forward>(rootNode(), previous, shouldOnlyIncludeDirectChildren());
+    else
+        current = firstNode(forward, rootNode(), previous);
+
+    if (type() == NodeListCollectionType && shouldOnlyIncludeDirectChildren()) // ChildNodeList
+        return current;
+
+    return iterateForNextNode<forward>(current);
+}
+
+// Without this ALWAYS_INLINE, length() and item() can be 100% slower.
+ALWAYS_INLINE Node* DynamicNodeListCacheBase::itemBefore(Node* previous) const
 {
-    return itemBeforeOrAfter<false>(type(), base(), offsetInArray, previous);
+    return itemBeforeOrAfter<false>(previous);
 }
 
-Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
+// Without this ALWAYS_INLINE, length() and item() can be 100% slower.
+ALWAYS_INLINE Node* DynamicNodeListCacheBase::itemAfter(unsigned& offsetInArray, Node* previous) const
 {
-    return itemBeforeOrAfter<true>(type(), base(), offsetInArray, previous);
+    if (UNLIKELY(overridesItemAfter())) // Without this UNLIKELY, length() can be 100% slower.
+        return static_cast<const HTMLCollection*>(this)->virtualItemAfter(offsetInArray, toElement(previous));
+    ASSERT(!offsetInArray);
+    return itemBeforeOrAfter<true>(previous);
 }
 
-bool ALWAYS_INLINE HTMLCollection::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
+bool ALWAYS_INLINE DynamicNodeListCacheBase::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
 {
     ASSERT(isLengthCacheValid());
     unsigned distanceFromLastItem = cachedLength() - offset;
@@ -298,7 +321,7 @@ bool ALWAYS_INLINE HTMLCollection::isLastItemCloserThanLastOrCachedItem(unsigned
     return cachedItemOffset() < offset && distanceFromLastItem < offset - cachedItemOffset();
 }
     
-bool ALWAYS_INLINE HTMLCollection::isFirstItemCloserThanCachedItem(unsigned offset) const
+bool ALWAYS_INLINE DynamicNodeListCacheBase::isFirstItemCloserThanCachedItem(unsigned offset) const
 {
     ASSERT(isItemCacheValid());
     if (cachedItemOffset() < offset)
@@ -308,28 +331,33 @@ bool ALWAYS_INLINE HTMLCollection::isFirstItemCloserThanCachedItem(unsigned offs
     return offset < distanceFromCachedItem;
 }
 
-unsigned HTMLCollection::length() const
+ALWAYS_INLINE void DynamicNodeListCacheBase::setItemCache(Node* item, unsigned offset, unsigned elementsArrayOffset) const
+{
+    setItemCache(item, offset);
+    if (overridesItemAfter()) {
+        ASSERT(item->isElementNode());
+        static_cast<const HTMLCollectionCacheBase*>(this)->m_cachedElementsArrayOffset = elementsArrayOffset;
+    } else
+        ASSERT(!elementsArrayOffset);
+}
+
+ALWAYS_INLINE unsigned DynamicNodeListCacheBase::cachedElementsArrayOffset() const
+{
+    return overridesItemAfter() ? static_cast<const HTMLCollectionCacheBase*>(this)->m_cachedElementsArrayOffset : 0;
+}
+
+unsigned DynamicNodeListCacheBase::lengthCommon() const
 {
     if (isLengthCacheValid())
         return cachedLength();
 
-    if (!isItemCacheValid() && !item(0)) {
-        ASSERT(isLengthCacheValid());
-        return 0;
-    }
-
-    ASSERT(isItemCacheValid());
-    ASSERT(cachedItem());
-    unsigned offset = cachedItemOffset();
-    do {
-        offset++;
-    } while (itemBeforeOrAfterCachedItem(offset));
+    itemCommon(UINT_MAX);
     ASSERT(isLengthCacheValid());
-
-    return offset;
+    
+    return cachedLength();
 }
 
-Node* HTMLCollection::item(unsigned offset) const
+Node* DynamicNodeListCacheBase::itemCommon(unsigned offset) const
 {
     if (isItemCacheValid() && cachedItemOffset() == offset)
         return cachedItem();
@@ -342,14 +370,11 @@ Node* HTMLCollection::item(unsigned offset) const
         static_cast<const HTMLPropertiesCollection*>(this)->updateRefElements();
 #endif
 
-    if (isLengthCacheValid() && supportsItemBefore() && isLastItemCloserThanLastOrCachedItem(offset)) {
-        // FIXME: Need to figure out the last offset in array for HTMLFormCollection and HTMLPropertiesCollection
-        unsigned unusedOffsetInArray = 0;
-        Node* lastItem = itemBefore(unusedOffsetInArray, 0);
-        ASSERT(!unusedOffsetInArray);
+    if (isLengthCacheValid() && !overridesItemAfter() && isLastItemCloserThanLastOrCachedItem(offset)) {
+        Node* lastItem = itemBefore(0);
         ASSERT(lastItem);
         setItemCache(lastItem, cachedLength() - 1, 0);
-    } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) {
+    } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (overridesItemAfter() && offset < cachedItemOffset())) {
         unsigned offsetInArray = 0;
         Node* firstItem = itemAfter(offsetInArray, 0);
         if (!firstItem) {
@@ -366,22 +391,19 @@ Node* HTMLCollection::item(unsigned offset) const
     return itemBeforeOrAfterCachedItem(offset);
 }
 
-Element* HTMLCollection::itemBeforeOrAfterCachedItem(unsigned offset) const
+Node* DynamicNodeListCacheBase::itemBeforeOrAfterCachedItem(unsigned offset) const
 {
     unsigned currentOffset = cachedItemOffset();
-    ASSERT(cachedItem()->isElementNode());
-    Element* currentItem = toElement(cachedItem());
+    Node* currentItem = cachedItem();
     ASSERT(currentOffset != offset);
 
-    unsigned offsetInArray = cachedElementsArrayOffset();
-
     if (offset < cachedItemOffset()) {
-        ASSERT(supportsItemBefore());
-        while ((currentItem = itemBefore(offsetInArray, currentItem))) {
+        ASSERT(!overridesItemAfter());
+        while ((currentItem = itemBefore(currentItem))) {
             ASSERT(currentOffset);
             currentOffset--;
             if (currentOffset == offset) {
-                setItemCache(currentItem, currentOffset, offsetInArray);
+                setItemCache(currentItem, currentOffset, 0);
                 return currentItem;
             }
         }
@@ -389,6 +411,7 @@ Element* HTMLCollection::itemBeforeOrAfterCachedItem(unsigned offset) const
         return 0;
     }
 
+    unsigned offsetInArray = cachedElementsArrayOffset();
     while ((currentItem = itemAfter(offsetInArray, currentItem))) {
         currentOffset++;
         if (currentOffset == offset) {
@@ -403,6 +426,12 @@ Element* HTMLCollection::itemBeforeOrAfterCachedItem(unsigned offset) const
     return 0;
 }
 
+Element* HTMLCollection::virtualItemAfter(unsigned&, Element*) const
+{
+    ASSERT_NOT_REACHED();
+    return 0;
+}
+
 static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element)
 {
     // The document.all collection returns only certain types of elements by name,
@@ -441,8 +470,8 @@ Node* HTMLCollection::namedItem(const AtomicString& name) const
 
     unsigned arrayOffset = 0;
     unsigned i = 0;
-    for (Element* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
-        if (checkForNameMatch(e, /* checkName */ false, name)) {
+    for (Node* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
+        if (checkForNameMatch(toElement(e), /* checkName */ false, name)) {
             setItemCache(e, i, arrayOffset);
             return e;
         }
@@ -450,10 +479,10 @@ Node* HTMLCollection::namedItem(const AtomicString& name) const
     }
 
     i = 0;
-    for (Element* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
-        if (checkForNameMatch(e, /* checkName */ true, name)) {
+    for (Node* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
+        if (checkForNameMatch(toElement(e), /* checkName */ true, name)) {
             setItemCache(e, i, arrayOffset);
-            return e;
+            return toElement(e);
         }
         i++;
     }
@@ -467,10 +496,10 @@ void HTMLCollection::updateNameCache() const
         return;
 
     unsigned arrayOffset = 0;
-    for (Element* element = itemAfter(arrayOffset, 0); element; element = itemAfter(arrayOffset, element)) {
-        if (!element->isHTMLElement())
+    for (Node* node = itemAfter(arrayOffset, 0); node; node = itemAfter(arrayOffset, node)) {
+        if (!node->isHTMLElement())
             continue;
-        HTMLElement* e = toHTMLElement(element);
+        HTMLElement* e = toHTMLElement(node);
         const AtomicString& idAttrVal = e->getIdAttribute();
         const AtomicString& nameAttrVal = e->getNameAttribute();
         if (!idAttrVal.isEmpty())
@@ -522,7 +551,7 @@ void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Node> >&
 
 PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
 {
-    return m_base->getElementsByTagName(name);
+    return ownerNode()->getElementsByTagName(name);
 }
 
 void HTMLCollectionCacheBase::append(NodeCacheMap& map, const AtomicString& key, Element* element)
index 6343e8e..8336183 100644 (file)
@@ -39,20 +39,13 @@ class NodeList;
 
 class HTMLCollectionCacheBase : public DynamicNodeListCacheBase {
 public:
-    HTMLCollectionCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType, ItemBeforeSupportType itemBeforeSupportType)
-        : DynamicNodeListCacheBase(rootType, invalidationType, collectionType, itemBeforeSupportType)
-        , m_cachedElementsArrayOffset(0)
+    HTMLCollectionCacheBase(Node* ownerNode, NodeListRootType rootType, NodeListInvalidationType invalidationType,
+        bool shouldOnlyIncludeDirectChildren, CollectionType collectionType, ItemAfterOverrideType itemAfterOverrideType)
+        : DynamicNodeListCacheBase(ownerNode, rootType, invalidationType, shouldOnlyIncludeDirectChildren, collectionType, itemAfterOverrideType)
     {
     }
 
 protected:
-    void setItemCache(Node* item, unsigned offset, unsigned elementsArrayOffset) const
-    {
-        setItemCache(item, offset);
-        m_cachedElementsArrayOffset = elementsArrayOffset;
-    }
-    unsigned cachedElementsArrayOffset() const { return m_cachedElementsArrayOffset; }
-
     typedef HashMap<AtomicStringImpl*, OwnPtr<Vector<Element*> > > NodeCacheMap;
     Vector<Element*>* idCache(const AtomicString& name) const { return m_idCache.get(name.impl()); }
     Vector<Element*>* nameCache(const AtomicString& name) const { return m_nameCache.get(name.impl()); }
@@ -63,13 +56,12 @@ protected:
 
 private:
     using DynamicNodeListCacheBase::isRootedAtDocument;
-    using DynamicNodeListCacheBase::setItemCache;
 
     mutable NodeCacheMap m_idCache;
     mutable NodeCacheMap m_nameCache;
     mutable unsigned m_cachedElementsArrayOffset;
 
-    friend void DynamicNodeListCacheBase::invalidateCache() const;
+    friend class DynamicNodeListCacheBase;
 };
 
 class HTMLCollection : public RefCounted<HTMLCollection>, public HTMLCollectionCacheBase {
@@ -78,8 +70,8 @@ public:
     virtual ~HTMLCollection();
 
     // DOM API
-    unsigned length() const;
-    Node* item(unsigned index) const;
+    unsigned length() const { return lengthCommon(); }
+    Node* item(unsigned offset) const { return itemCommon(offset); }
     virtual Node* namedItem(const AtomicString& name) const;
     PassRefPtr<NodeList> tags(const String&);
 
@@ -103,23 +95,16 @@ public:
         return item(0) && !item(1);
     }
 
-    Node* base() const { return m_base.get(); }
+    Node* base() const { return ownerNode(); }
+    virtual Element* virtualItemAfter(unsigned& offsetInArray, Element*) const;
 
 protected:
-    HTMLCollection(Node* base, CollectionType, ItemBeforeSupportType);
+    HTMLCollection(Node* base, CollectionType, ItemAfterOverrideType);
 
     virtual void updateNameCache() const;
-    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const;
 
 private:
     bool checkForNameMatch(Element*, bool checkName, const AtomicString& name) const;
-
-    Element* itemBefore(unsigned& offsetInArray, Element*) const;
-    bool isLastItemCloserThanLastOrCachedItem(unsigned offset) const;
-    bool isFirstItemCloserThanCachedItem(unsigned offset) const;
-    Element* itemBeforeOrAfterCachedItem(unsigned offset) const;
-
-    RefPtr<Node> m_base;
 };
 
 } // namespace
index b845f0c..a5cc6ac 100644 (file)
@@ -37,7 +37,7 @@ using namespace HTMLNames;
 // calculation every time if anything has changed.
 
 HTMLFormCollection::HTMLFormCollection(Element* base)
-    : HTMLCollection(base, FormControls, DoNotSupportItemBefore)
+    : HTMLCollection(base, FormControls, OverridesItemAfter)
 {
     ASSERT(base->hasTagName(formTag) || base->hasTagName(fieldsetTag));
 }
@@ -67,7 +67,7 @@ const Vector<HTMLImageElement*>& HTMLFormCollection::formImageElements() const
     return static_cast<HTMLFormElement*>(base())->imageElements();
 }
 
-Element* HTMLFormCollection::itemAfter(unsigned& offset, Element* previousItem) const
+Element* HTMLFormCollection::virtualItemAfter(unsigned& offset, Element* previousItem) const
 {
     const Vector<FormAssociatedElement*>& elementsArray = formControlElements();
     if (previousItem)
index 82cbfed..978a26f 100644 (file)
@@ -49,7 +49,7 @@ private:
 
     const Vector<FormAssociatedElement*>& formControlElements() const;
     const Vector<HTMLImageElement*>& formImageElements() const;
-    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
+    virtual Element* virtualItemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
 };
 
 } //namespace
index 246235d..36c7350 100644 (file)
@@ -33,7 +33,7 @@ namespace WebCore {
 using namespace HTMLNames;
 
 HTMLNameCollection::HTMLNameCollection(Document* document, CollectionType type, const AtomicString& name)
-    : HTMLCollection(document, type, DoNotSupportItemBefore)
+    : HTMLCollection(document, type, OverridesItemAfter)
     , m_name(name)
 {
 }
@@ -49,7 +49,7 @@ HTMLNameCollection::~HTMLNameCollection()
         static_cast<Document*>(base())->removeDocumentNamedItemCache(this, m_name);
 }
 
-Element* HTMLNameCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
+Element* HTMLNameCollection::virtualItemAfter(unsigned& offsetInArray, Element* previous) const
 {
     ASSERT_UNUSED(offsetInArray, !offsetInArray);
     ASSERT(previous != base());
index dd9d45d..4a7afeb 100644 (file)
@@ -43,7 +43,7 @@ public:
 private:
     HTMLNameCollection(Document*, CollectionType, const AtomicString& name);
 
-    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
+    virtual Element* virtualItemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
 
     AtomicString m_name;
 };
index 960fc89..8d2aff9 100644 (file)
@@ -28,7 +28,7 @@
 namespace WebCore {
 
 HTMLOptionsCollection::HTMLOptionsCollection(Element* select)
-    : HTMLCollection(select, SelectOptions, SupportItemBefore)
+    : HTMLCollection(select, SelectOptions, DoesNotOverrideItemAfter)
 {
     ASSERT(select->hasTagName(HTMLNames::selectTag));
 }
index c17e7c6..d86bf6c 100644 (file)
@@ -51,7 +51,7 @@ PassRefPtr<HTMLPropertiesCollection> HTMLPropertiesCollection::create(Node* item
 }
 
 HTMLPropertiesCollection::HTMLPropertiesCollection(Node* itemNode)
-    : HTMLCollection(itemNode, ItemProperties, DoNotSupportItemBefore)
+    : HTMLCollection(itemNode, ItemProperties, OverridesItemAfter)
     , m_hasPropertyNameCache(false)
     , m_hasItemRefElements(false)
 {
@@ -112,10 +112,10 @@ static Node* nextNodeWithProperty(Node* base, Node* node)
             ? node->traverseNextNode(base) : node->traverseNextSibling(base);
 }
 
-Element* HTMLPropertiesCollection::itemAfter(unsigned& offsetInArray, Element* previousItem) const
+Element* HTMLPropertiesCollection::virtualItemAfter(unsigned& offsetInArray, Element* previousItem) const
 {
     while (offsetInArray < m_itemRefElements.size()) {
-        if (Element* next = itemAfter(m_itemRefElements[offsetInArray], previousItem))
+        if (Element* next = virtualItemAfter(m_itemRefElements[offsetInArray], previousItem))
             return next;
         offsetInArray++;
         previousItem = 0;
@@ -123,7 +123,7 @@ Element* HTMLPropertiesCollection::itemAfter(unsigned& offsetInArray, Element* p
     return 0;
 }
 
-HTMLElement* HTMLPropertiesCollection::itemAfter(HTMLElement* base, Element* previous) const
+HTMLElement* HTMLPropertiesCollection::virtualItemAfter(HTMLElement* base, Element* previous) const
 {
     Node* current;
     current = previous ? nextNodeWithProperty(base, previous) : base;
@@ -149,7 +149,7 @@ void HTMLPropertiesCollection::updateNameCache() const
 
     for (unsigned i = 0; i < m_itemRefElements.size(); ++i) {
         HTMLElement* refElement = m_itemRefElements[i];
-        for (HTMLElement* element = itemAfter(refElement, 0); element; element = itemAfter(refElement, element)) {
+        for (HTMLElement* element = virtualItemAfter(refElement, 0); element; element = virtualItemAfter(refElement, element)) {
             DOMSettableTokenList* itemProperty = element->itemProp();
             for (unsigned propertyIndex = 0; propertyIndex < itemProperty->length(); ++propertyIndex)
                 updatePropertyCache(element, itemProperty->item(propertyIndex));
index dba91ca..29a84ed 100644 (file)
@@ -65,8 +65,8 @@ private:
 
     Node* findRefElements(Node* previous) const;
 
-    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
-    HTMLElement* itemAfter(HTMLElement* base, Element* previous) const;
+    virtual Element* virtualItemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
+    HTMLElement* virtualItemAfter(HTMLElement* base, Element* previous) const;
 
     void updateNameCache() const;
 
index 206864e..2619f94 100644 (file)
@@ -152,7 +152,7 @@ HTMLTableRowElement* HTMLTableRowsCollection::lastRow(HTMLTableElement* table)
 // table to get at the collection cache. Order of argument evaluation is undefined and can
 // differ between compilers.
 HTMLTableRowsCollection::HTMLTableRowsCollection(Element* table)
-    : HTMLCollection(table, TableRows, DoNotSupportItemBefore)
+    : HTMLCollection(table, TableRows, OverridesItemAfter)
 {
     ASSERT(table->hasTagName(tableTag));
 }
@@ -162,7 +162,7 @@ PassRefPtr<HTMLTableRowsCollection> HTMLTableRowsCollection::create(Element* tab
     return adoptRef(new HTMLTableRowsCollection(table));
 }
 
-Element* HTMLTableRowsCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
+Element* HTMLTableRowsCollection::virtualItemAfter(unsigned& offsetInArray, Element* previous) const
 {
     ASSERT_UNUSED(offsetInArray, !offsetInArray);
     ASSERT(!previous || (previous->isHTMLElement() && toHTMLElement(previous)->hasLocalName(trTag)));
index 817b143..c5068db 100644 (file)
@@ -46,7 +46,7 @@ public:
 private:
     HTMLTableRowsCollection(Element*);
 
-    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
+    virtual Element* virtualItemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
 };
 
 } // namespace
index d3a4ba1..3b2b8d3 100644 (file)
@@ -34,7 +34,7 @@ namespace WebCore {
 using namespace HTMLNames;
 
 LabelsNodeList::LabelsNodeList(Node* forNode)
-    : DynamicSubtreeNodeList(forNode, InvalidateOnForAttrChange, NodeListIsRootedAtDocument)
+    : DynamicSubtreeNodeList(forNode, LabelsNodeListType, InvalidateOnForAttrChange, NodeListIsRootedAtDocument)
 {
 }
 
index bd3cc87..944f7b4 100644 (file)
@@ -38,7 +38,7 @@ namespace WebCore {
 using namespace HTMLNames;
 
 RadioNodeList::RadioNodeList(Node* rootNode, const AtomicString& name)
-    : DynamicSubtreeNodeList(rootNode, InvalidateForFormControls, rootNode->hasTagName(formTag) ? NodeListIsRootedAtDocument : NodeListIsRootedAtNode)
+    : DynamicSubtreeNodeList(rootNode, RadioNodeListType, InvalidateForFormControls, rootNode->hasTagName(formTag) ? NodeListIsRootedAtDocument : NodeListIsRootedAtNode)
     , m_name(name)
 {
 }