Iterating backwards over HTMLCollection is O(n^2)

https://bugs.webkit.org/show_bug.cgi?id=91306

Reviewed by Anders Carlsson.

Source/WebCore:

Fixed the bug by introducing itemBefore that iterates nodes backwards to complement itemAfter.
Unfortunately, some HTML collections such as HTMLFormCollection and HTMLTableRowsCollection have
its own itemAfter function and writing an equivalent itemBefore is somewhat tricky. For now,
added a new boolean flag indicating whether a given HTML collection supports itemBefore or not,
and left those HTML collections that override itemAfter alone.

This also paves our way to share more code between DynamicNodeList and HTMLCollection.

Test: perf/htmlcollection-backwards-iteration.html

* dom/DynamicNodeList.h:
(WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): Takes ItemBeforeSupportType.
(WebCore::DynamicNodeListCacheBase::supportsItemBefore): Added.
(DynamicNodeListCacheBase):
(WebCore::DynamicNodeListCacheBase::setItemCache): Replaced a FIXME by an assertion now that
we can.
* html/HTMLAllCollection.cpp:
(WebCore::HTMLAllCollection::HTMLAllCollection): Supports itemBefore since it doesn't override
itemAfter.
* html/HTMLCollection.cpp:
(WebCore::HTMLCollection::HTMLCollection):
(WebCore::HTMLCollection::create):
(WebCore::isAcceptableElement): Made it a static local function instead of a static member.
(WebCore::nextNode): Templatized.
(WebCore::itemBeforeOrAfter): Extracted from itemAfter and templatized.
(WebCore::HTMLCollection::itemBefore): Added.
(WebCore::HTMLCollection::itemAfter):
(WebCore::HTMLCollection::shouldSearchFromFirstItem): Added. Determines whether we should reset
the item cache to the first item. We obviously do if the cache is invalid. If the target offset
is after the cached offset, then we shouldn't go back regardless of availability of itemBefore.
Otherwise, we go back to the first item iff itemBefore is not available or the distance from
the cached offset to the target offset is greater than the target offset itself.
(WebCore::HTMLCollection::length):
(WebCore::HTMLCollection::item): Use the term "offset" to match the terminology elsewhere.
(WebCore::HTMLCollection::itemBeforeOrAfterCachedItem): Ditto. Also added the logic to iterate
nodes backwards using itemBefore. Once we're in this branch, we should always find a matching
item since the target offset was less than the cached offset, and offsets are non-negative.
If we had ever reached the end of the loop without finding an item, it indicates that the cache
has been invalid and we have some serious bug elsewhere.
* html/HTMLCollection.h:
(WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase):
(HTMLCollection):
* html/HTMLOptionsCollection.cpp:
(WebCore::HTMLOptionsCollection::HTMLOptionsCollection): Supports itemBefore since it doesn't
override itemAfter.
* html/HTMLFormCollection.cpp:
(WebCore::HTMLFormCollection::HTMLFormCollection): Doesn't support itemBefore as it overrides
itemAfter.
* html/HTMLNameCollection.cpp:
(WebCore::HTMLNameCollection::HTMLNameCollection): Ditto.
* html/HTMLPropertiesCollection.cpp:
(WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
* html/HTMLTableRowsCollection.cpp:
(WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection):

LayoutTests:

Add an asymptotic time complexity test.

* perf/htmlcollection-backwards-iteration-expected.txt: Added.
* perf/htmlcollection-backwards-iteration.html: Added.

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

diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog
index 5cb98d4..e06acc1 100644 (file)
--- a/LayoutTests/ChangeLog
+++ b/LayoutTests/ChangeLog
@@ -1,3 +1,15 @@
+2012-07-13  Ryosuke Niwa  <rniwa@webkit.org>
+
+        Iterating backwards over HTMLCollection is O(n^2)
+        https://bugs.webkit.org/show_bug.cgi?id=91306
+
+        Reviewed by Anders Carlsson.
+
+        Add an asymptotic time complexity test.
+
+        * perf/htmlcollection-backwards-iteration-expected.txt: Added.
+        * perf/htmlcollection-backwards-iteration.html: Added.
+
 2012-07-13  Kent Tamura  <tkent@chromium.org>
 
         Internals: Clean up the mock PagePopupDriver correctly.

diff --git a/LayoutTests/perf/htmlcollection-backwards-iteration-expected.txt b/LayoutTests/perf/htmlcollection-backwards-iteration-expected.txt
new file mode 100644 (file)
index 0000000..1a24936
--- /dev/null
+++ b/LayoutTests/perf/htmlcollection-backwards-iteration-expected.txt
@@ -0,0 +1,3 @@
+Tests that iterating over HTMLCollection backwards is linear.
+PASS
+

diff --git a/LayoutTests/perf/htmlcollection-backwards-iteration.html b/LayoutTests/perf/htmlcollection-backwards-iteration.html
new file mode 100644 (file)
index 0000000..032c5a7
--- /dev/null
+++ b/LayoutTests/perf/htmlcollection-backwards-iteration.html
@@ -0,0 +1,28 @@
+<!DOCTYPE html>
+<body>
+<div id="container" style="display: none;"></div>
+<script src="../resources/magnitude-perf.js"></script>
+<script>
+
+var container = document.getElementById('container');
+
+function setupFunction(magnitude)
+{
+    container.innerHTML = '';
+    for (var i = 0; i < magnitude; i++)
+        container.appendChild(document.createElement('div'));
+}
+
+function test(magnitude)
+{
+    var children = container.children;
+    for (var i = children.length; i > 0;i--)
+        children[i - 1].class = 'hi';
+}
+
+Magnitude.description("Tests that iterating over HTMLCollection backwards is linear.");
+Magnitude.run(setupFunction, test, Magnitude.LINEAR);
+
+</script>
+</body>
+</html>

diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
index 4111092..1dbb66d 100644 (file)
--- a/Source/WebCore/ChangeLog
+++ b/Source/WebCore/ChangeLog
@@ -1,3 +1,65 @@
+2012-07-13  Ryosuke Niwa  <rniwa@webkit.org>
+
+        Iterating backwards over HTMLCollection is O(n^2)
+        https://bugs.webkit.org/show_bug.cgi?id=91306
+
+        Reviewed by Anders Carlsson.
+
+        Fixed the bug by introducing itemBefore that iterates nodes backwards to complement itemAfter.
+        Unfortunately, some HTML collections such as HTMLFormCollection and HTMLTableRowsCollection have
+        its own itemAfter function and writing an equivalent itemBefore is somewhat tricky. For now,
+        added a new boolean flag indicating whether a given HTML collection supports itemBefore or not,
+        and left those HTML collections that override itemAfter alone.
+
+        This also paves our way to share more code between DynamicNodeList and HTMLCollection.
+
+        Test: perf/htmlcollection-backwards-iteration.html
+
+        * dom/DynamicNodeList.h:
+        (WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): Takes ItemBeforeSupportType.
+        (WebCore::DynamicNodeListCacheBase::supportsItemBefore): Added.
+        (DynamicNodeListCacheBase):
+        (WebCore::DynamicNodeListCacheBase::setItemCache): Replaced a FIXME by an assertion now that
+        we can.
+        * html/HTMLAllCollection.cpp:
+        (WebCore::HTMLAllCollection::HTMLAllCollection): Supports itemBefore since it doesn't override
+        itemAfter.
+        * html/HTMLCollection.cpp:
+        (WebCore::HTMLCollection::HTMLCollection):
+        (WebCore::HTMLCollection::create):
+        (WebCore::isAcceptableElement): Made it a static local function instead of a static member.
+        (WebCore::nextNode): Templatized.
+        (WebCore::itemBeforeOrAfter): Extracted from itemAfter and templatized.
+        (WebCore::HTMLCollection::itemBefore): Added.
+        (WebCore::HTMLCollection::itemAfter):
+        (WebCore::HTMLCollection::shouldSearchFromFirstItem): Added. Determines whether we should reset
+        the item cache to the first item. We obviously do if the cache is invalid. If the target offset
+        is after the cached offset, then we shouldn't go back regardless of availability of itemBefore.
+        Otherwise, we go back to the first item iff itemBefore is not available or the distance from
+        the cached offset to the target offset is greater than the target offset itself.
+        (WebCore::HTMLCollection::length):
+        (WebCore::HTMLCollection::item): Use the term "offset" to match the terminology elsewhere.
+        (WebCore::HTMLCollection::itemBeforeOrAfterCachedItem): Ditto. Also added the logic to iterate
+        nodes backwards using itemBefore. Once we're in this branch, we should always find a matching
+        item since the target offset was less than the cached offset, and offsets are non-negative.
+        If we had ever reached the end of the loop without finding an item, it indicates that the cache
+        has been invalid and we have some serious bug elsewhere.
+        * html/HTMLCollection.h:
+        (WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase):
+        (HTMLCollection):
+        * html/HTMLOptionsCollection.cpp:
+        (WebCore::HTMLOptionsCollection::HTMLOptionsCollection): Supports itemBefore since it doesn't
+        override itemAfter.
+        * html/HTMLFormCollection.cpp:
+        (WebCore::HTMLFormCollection::HTMLFormCollection): Doesn't support itemBefore as it overrides
+        itemAfter.
+        * html/HTMLNameCollection.cpp:
+        (WebCore::HTMLNameCollection::HTMLNameCollection): Ditto.
+        * html/HTMLPropertiesCollection.cpp:
+        (WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
+        * html/HTMLTableRowsCollection.cpp:
+        (WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection):
+
 2012-07-13  Eric Penner  <epenner@google.com>
 
         [chromium] Add 'self-managed' option to CCPrioritizedTexture to enable render-surface and canvas use cases.

diff --git a/Source/WebCore/dom/DynamicNodeList.h b/Source/WebCore/dom/DynamicNodeList.h
index 56ab865..a3c12c2 100644 (file)
--- a/Source/WebCore/dom/DynamicNodeList.h
+++ b/Source/WebCore/dom/DynamicNodeList.h
@@ -43,7 +43,13 @@ enum NodeListRootType {
 
 class DynamicNodeListCacheBase {
 public:
-    DynamicNodeListCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType = InvalidCollectionType)
+    enum ItemBeforeSupportType {
+        DoNotSupportItemBefore,
+        SupportItemBefore,
+    };
+
+    DynamicNodeListCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType,
+        CollectionType collectionType = InvalidCollectionType, ItemBeforeSupportType itemBeforeSupportType = DoNotSupportItemBefore)
         : m_cachedItem(0)
         , m_isLengthCacheValid(false)
         , m_isItemCacheValid(false)
@@ -51,6 +57,7 @@ public:
         , m_invalidationType(invalidationType)
         , m_isNameCacheValid(false)
         , m_collectionType(collectionType)
+        , m_supportsItemBefore(itemBeforeSupportType == SupportItemBefore)
     {
         ASSERT(m_invalidationType == static_cast<unsigned>(invalidationType));
         ASSERT(m_collectionType == static_cast<unsigned>(collectionType));
@@ -66,6 +73,8 @@ public:
     static bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType, const QualifiedName&);
 
 protected:
+    bool supportsItemBefore() const { return m_supportsItemBefore; }
+
     ALWAYS_INLINE bool isItemCacheValid() const { return m_isItemCacheValid; }
     ALWAYS_INLINE Node* cachedItem() const { return m_cachedItem; }
     ALWAYS_INLINE unsigned cachedItemOffset() const { return m_cachedItemOffset; }
@@ -79,7 +88,7 @@ protected:
     }
     ALWAYS_INLINE void setItemCache(Node* item, unsigned offset) const
     {
-        // FIXME: Assert that item is not null once we've updated DynamicNodeList.
+        ASSERT(item);
         m_cachedItem = item;
         m_cachedItemOffset = offset;
         m_isItemCacheValid = true;
@@ -100,6 +109,7 @@ private:
     // From HTMLCollection
     mutable unsigned m_isNameCacheValid : 1;
     const unsigned m_collectionType : 5;
+    const unsigned m_supportsItemBefore : 1;
 };
 
 ALWAYS_INLINE bool DynamicNodeListCacheBase::shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType type, const QualifiedName& attrName)

diff --git a/Source/WebCore/html/HTMLAllCollection.cpp b/Source/WebCore/html/HTMLAllCollection.cpp
index a008ff0..e769b26 100644 (file)
--- a/Source/WebCore/html/HTMLAllCollection.cpp
+++ b/Source/WebCore/html/HTMLAllCollection.cpp
@@ -36,7 +36,7 @@ PassRefPtr<HTMLAllCollection> HTMLAllCollection::create(Document* document)
 }
 
 HTMLAllCollection::HTMLAllCollection(Document* document)
-    : HTMLCollection(document, DocAll)
+    : HTMLCollection(document, DocAll, SupportItemBefore)
 {
 }
 

diff --git a/Source/WebCore/html/HTMLCollection.cpp b/Source/WebCore/html/HTMLCollection.cpp
index 9dcfc0b..f1bc473 100644 (file)
--- a/Source/WebCore/html/HTMLCollection.cpp
+++ b/Source/WebCore/html/HTMLCollection.cpp
@@ -152,8 +152,8 @@ static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(Col
 }
     
 
-HTMLCollection::HTMLCollection(Node* base, CollectionType type)
-    : HTMLCollectionCacheBase(rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type)
+HTMLCollection::HTMLCollection(Node* base, CollectionType type, ItemBeforeSupportType itemBeforeSupportType)
+    : HTMLCollectionCacheBase(rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type, itemBeforeSupportType)
     , m_base(base)
 {
     ASSERT(m_base);
@@ -162,7 +162,7 @@ HTMLCollection::HTMLCollection(Node* base, CollectionType type)
 
 PassRefPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
 {
-    return adoptRef(new HTMLCollection(base, type));
+    return adoptRef(new HTMLCollection(base, type, SupportItemBefore));
 }
 
 HTMLCollection::~HTMLCollection()
@@ -179,12 +179,12 @@ HTMLCollection::~HTMLCollection()
     m_base->document()->unregisterNodeListCache(this);
 }
 
-inline bool HTMLCollection::isAcceptableElement(Element* element) const
+static inline bool isAcceptableElement(CollectionType type, Element* element)
 {
-    if (!element->isHTMLElement() && !(type() == DocAll || type() == NodeChildren))
+    if (!element->isHTMLElement() && !(type == DocAll || type == NodeChildren))
         return false;
 
-    switch (type()) {
+    switch (type) {
     case DocImages:
         return element->hasLocalName(imgTag);
     case DocScripts:
@@ -237,26 +237,54 @@ inline bool HTMLCollection::isAcceptableElement(Element* element) const
     return false;
 }
 
-static ALWAYS_INLINE Node* nextNode(Node* base, Node* previous, bool onlyIncludeDirectChildren)
+template<bool forward>
+static Node* nextNode(Node* base, Node* previous, bool onlyIncludeDirectChildren)
 {
-    return onlyIncludeDirectChildren ? previous->traverseNextSibling(base) : previous->traverseNextNode(base);
+    if (forward)
+        return onlyIncludeDirectChildren ? previous->nextSibling() : previous->traverseNextNode(base);
+    else
+        return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traversePreviousNode(base);
 }
 
-Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
+template<bool forward>
+static Element* itemBeforeOrAfter(CollectionType type, Node* base, unsigned& offsetInArray, Node* previous)
 {
     ASSERT_UNUSED(offsetInArray, !offsetInArray);
-    bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren(type());
-    Node* rootNode = base();
-    Node* current = previous ? nextNode(rootNode, previous, onlyIncludeDirectChildren) : m_base->firstChild();
+    bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren(type);
+    Node* rootNode = base;
+    Node* current = previous ? nextNode<forward>(rootNode, previous, onlyIncludeDirectChildren) : (forward ? base->firstChild() : base->lastChild());
 
-    for (; current; current = nextNode(rootNode, current, onlyIncludeDirectChildren)) {
-        if (current->isElementNode() && isAcceptableElement(toElement(current)))
+    for (; current; current = nextNode<forward>(rootNode, current, onlyIncludeDirectChildren)) {
+        if (current->isElementNode() && isAcceptableElement(type, toElement(current)))
             return toElement(current);
     }
 
     return 0;
 }
 
+Element* HTMLCollection::itemBefore(unsigned& offsetInArray, Element* previous) const
+{
+    return itemBeforeOrAfter<false>(type(), base(), offsetInArray, previous);
+}
+
+Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
+{
+    return itemBeforeOrAfter<true>(type(), base(), offsetInArray, previous);
+}
+    
+bool ALWAYS_INLINE HTMLCollection::shouldSearchFromFirstItem(unsigned offset) const
+{
+    if (!isItemCacheValid())
+        return true;
+
+    ASSERT(offset != cachedItemOffset());
+    if (offset > cachedItemOffset())
+        return false;
+
+    unsigned distanceFromCachedItem = cachedItemOffset() - offset;
+    return !supportsItemBefore() || offset < distanceFromCachedItem;
+}
+
 unsigned HTMLCollection::length() const
 {
     if (isLengthCacheValid())
@@ -272,18 +300,18 @@ unsigned HTMLCollection::length() const
     unsigned offset = cachedItemOffset();
     do {
         offset++;
-    } while (itemAfterCachedItem(offset));
+    } while (itemBeforeOrAfterCachedItem(offset));
 
     setLengthCache(offset);
     return offset;
 }
 
-Node* HTMLCollection::item(unsigned index) const
+Node* HTMLCollection::item(unsigned offset) const
 {
-    if (isItemCacheValid() && cachedItemOffset() == index)
+    if (isItemCacheValid() && cachedItemOffset() == offset)
         return cachedItem();
 
-    if (isLengthCacheValid() && cachedLength() <= index)
+    if (isLengthCacheValid() && cachedLength() <= offset)
         return 0;
 
 #if ENABLE(MICRODATA)
@@ -291,7 +319,7 @@ Node* HTMLCollection::item(unsigned index) const
         static_cast<const HTMLPropertiesCollection*>(this)->updateRefElements();
 #endif
 
-    if (!isItemCacheValid() || cachedItemOffset() > index) {
+    if (shouldSearchFromFirstItem(offset)) {
         unsigned offsetInArray = 0;
         Node* firstItem = itemAfter(offsetInArray, 0);
         if (!firstItem) {
@@ -300,30 +328,45 @@ Node* HTMLCollection::item(unsigned index) const
         }
         setItemCache(firstItem, 0, offsetInArray);
         ASSERT(!cachedItemOffset());
-        if (!index)
+        if (!offset)
             return cachedItem();
     }
 
-    return itemAfterCachedItem(index);
+    return itemBeforeOrAfterCachedItem(offset);
 }
 
-Element* HTMLCollection::itemAfterCachedItem(unsigned index) const
+Element* HTMLCollection::itemBeforeOrAfterCachedItem(unsigned offset) const
 {
-    unsigned currentIndex = cachedItemOffset();
+    unsigned currentOffset = cachedItemOffset();
     ASSERT(cachedItem()->isElementNode());
     Element* currentItem = toElement(cachedItem());
-    ASSERT(currentIndex < index);
+    ASSERT(currentOffset != offset);
 
     unsigned offsetInArray = cachedElementsArrayOffset();
+
+    if (offset < cachedItemOffset()) {
+        ASSERT(supportsItemBefore());
+        while ((currentItem = itemBefore(offsetInArray, currentItem))) {
+            ASSERT(currentOffset);
+            currentOffset--;
+            if (currentOffset == offset) {
+                setItemCache(currentItem, currentOffset, offsetInArray);
+                return currentItem;
+            }
+        }
+        ASSERT_NOT_REACHED();
+        return 0;
+    }
+
     while ((currentItem = itemAfter(offsetInArray, currentItem))) {
-        currentIndex++;
-        if (currentIndex == index) {
-            setItemCache(currentItem, currentIndex, offsetInArray);
+        currentOffset++;
+        if (currentOffset == offset) {
+            setItemCache(currentItem, currentOffset, offsetInArray);
             return currentItem;
         }
     }
 
-    setLengthCache(currentIndex);
+    setLengthCache(currentOffset);
 
     return 0;
 }

diff --git a/Source/WebCore/html/HTMLCollection.h b/Source/WebCore/html/HTMLCollection.h
index 1330a1b..66ad21f 100644 (file)
--- a/Source/WebCore/html/HTMLCollection.h
+++ b/Source/WebCore/html/HTMLCollection.h
@@ -39,8 +39,8 @@ class NodeList;
 
 class HTMLCollectionCacheBase : public DynamicNodeListCacheBase {
 public:
-    HTMLCollectionCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType)
-        : DynamicNodeListCacheBase(rootType, invalidationType, collectionType)
+    HTMLCollectionCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType, ItemBeforeSupportType itemBeforeSupportType)
+        : DynamicNodeListCacheBase(rootType, invalidationType, collectionType, itemBeforeSupportType)
         , m_cachedElementsArrayOffset(0)
     {
     }
@@ -106,7 +106,7 @@ public:
     Node* base() const { return m_base.get(); }
 
 protected:
-    HTMLCollection(Node* base, CollectionType);
+    HTMLCollection(Node* base, CollectionType, ItemBeforeSupportType);
 
     virtual void updateNameCache() const;
     virtual Element* itemAfter(unsigned& offsetInArray, Element*) const;
@@ -114,8 +114,9 @@ protected:
 private:
     bool checkForNameMatch(Element*, bool checkName, const AtomicString& name) const;
 
-    Element* itemAfterCachedItem(unsigned) const;
-    bool isAcceptableElement(Element*) const;
+    Element* itemBefore(unsigned& offsetInArray, Element*) const;
+    bool shouldSearchFromFirstItem(unsigned offset) const;
+    Element* itemBeforeOrAfterCachedItem(unsigned offset) const;
 
     RefPtr<Node> m_base;
 };

diff --git a/Source/WebCore/html/HTMLFormCollection.cpp b/Source/WebCore/html/HTMLFormCollection.cpp
index 7be1d1f..b845f0c 100644 (file)
--- a/Source/WebCore/html/HTMLFormCollection.cpp
+++ b/Source/WebCore/html/HTMLFormCollection.cpp
@@ -37,7 +37,7 @@ using namespace HTMLNames;
 // calculation every time if anything has changed.
 
 HTMLFormCollection::HTMLFormCollection(Element* base)
-    : HTMLCollection(base, FormControls)
+    : HTMLCollection(base, FormControls, DoNotSupportItemBefore)
 {
     ASSERT(base->hasTagName(formTag) || base->hasTagName(fieldsetTag));
 }

diff --git a/Source/WebCore/html/HTMLNameCollection.cpp b/Source/WebCore/html/HTMLNameCollection.cpp
index 631eee8..246235d 100644 (file)
--- a/Source/WebCore/html/HTMLNameCollection.cpp
+++ b/Source/WebCore/html/HTMLNameCollection.cpp
@@ -33,7 +33,7 @@ namespace WebCore {
 using namespace HTMLNames;
 
 HTMLNameCollection::HTMLNameCollection(Document* document, CollectionType type, const AtomicString& name)
-    : HTMLCollection(document, type)
+    : HTMLCollection(document, type, DoNotSupportItemBefore)
     , m_name(name)
 {
 }

diff --git a/Source/WebCore/html/HTMLOptionsCollection.cpp b/Source/WebCore/html/HTMLOptionsCollection.cpp
index 7000f28..960fc89 100644 (file)
--- a/Source/WebCore/html/HTMLOptionsCollection.cpp
+++ b/Source/WebCore/html/HTMLOptionsCollection.cpp
@@ -28,7 +28,7 @@
 namespace WebCore {
 
 HTMLOptionsCollection::HTMLOptionsCollection(Element* select)
-    : HTMLCollection(select, SelectOptions)
+    : HTMLCollection(select, SelectOptions, SupportItemBefore)
 {
     ASSERT(select->hasTagName(HTMLNames::selectTag));
 }

diff --git a/Source/WebCore/html/HTMLPropertiesCollection.cpp b/Source/WebCore/html/HTMLPropertiesCollection.cpp
index 597b265..c17e7c6 100644 (file)
--- a/Source/WebCore/html/HTMLPropertiesCollection.cpp
+++ b/Source/WebCore/html/HTMLPropertiesCollection.cpp
@@ -51,7 +51,7 @@ PassRefPtr<HTMLPropertiesCollection> HTMLPropertiesCollection::create(Node* item
 }
 
 HTMLPropertiesCollection::HTMLPropertiesCollection(Node* itemNode)
-    : HTMLCollection(itemNode, ItemProperties)
+    : HTMLCollection(itemNode, ItemProperties, DoNotSupportItemBefore)
     , m_hasPropertyNameCache(false)
     , m_hasItemRefElements(false)
 {

diff --git a/Source/WebCore/html/HTMLTableRowsCollection.cpp b/Source/WebCore/html/HTMLTableRowsCollection.cpp
index 81f4a79..206864e 100644 (file)
--- a/Source/WebCore/html/HTMLTableRowsCollection.cpp
+++ b/Source/WebCore/html/HTMLTableRowsCollection.cpp
@@ -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)
+    : HTMLCollection(table, TableRows, DoNotSupportItemBefore)
 {
     ASSERT(table->hasTagName(tableTag));
 }