Iterating backwards over HTMLCollection is O(n^2)
[WebKit-https.git] / Source / WebCore / ChangeLog
index 4111092..1dbb66d 100644 (file)
@@ -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.
 2012-07-13  Eric Penner  <epenner@google.com>
 
         [chromium] Add 'self-managed' option to CCPrioritizedTexture to enable render-surface and canvas use cases.