Skip to content
  • rniwa@webkit.org's avatar
    Iterating backwards over HTMLCollection is O(n^2) · 25d91a55
    rniwa@webkit.org authored
    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: http://svn.webkit.org/repository/webkit/trunk@122660 268f45cc-cd09-0410-ab3c-d52691b4dbfc
    25d91a55