Iterating backwards over HTMLCollection is O(n^2)
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 14 Jul 2012 07:08:55 +0000 (07:08 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 14 Jul 2012 07:08:55 +0000 (07:08 +0000)
commita4756302195c1369f3c49ab93cb9c6a36264873a
treea511bf4899d710babaa065ad7b8451de66b5a22f
parent504ee628e4740e2bb41b8a0c230d848c200d1f53
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
13 files changed:
LayoutTests/ChangeLog
LayoutTests/perf/htmlcollection-backwards-iteration-expected.txt [new file with mode: 0644]
LayoutTests/perf/htmlcollection-backwards-iteration.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/dom/DynamicNodeList.h
Source/WebCore/html/HTMLAllCollection.cpp
Source/WebCore/html/HTMLCollection.cpp
Source/WebCore/html/HTMLCollection.h
Source/WebCore/html/HTMLFormCollection.cpp
Source/WebCore/html/HTMLNameCollection.cpp
Source/WebCore/html/HTMLOptionsCollection.cpp
Source/WebCore/html/HTMLPropertiesCollection.cpp
Source/WebCore/html/HTMLTableRowsCollection.cpp