Changeset 122660 in webkit


Ignore:
Timestamp:
Jul 14, 2012 12:08:55 AM (12 years ago)
Author:
rniwa@webkit.org
Message:

Iterating backwards over HTMLCollection is O(n2)
​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.
Location:
trunk
Files:
2 added
11 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r122656 r122660  
     12012-07-13  Ryosuke Niwa  <rniwa@webkit.org>
     2
     3        Iterating backwards over HTMLCollection is O(n^2)
     4        https://bugs.webkit.org/show_bug.cgi?id=91306
     5
     6        Reviewed by Anders Carlsson.
     7
     8        Add an asymptotic time complexity test.
     9
     10        * perf/htmlcollection-backwards-iteration-expected.txt: Added.
     11        * perf/htmlcollection-backwards-iteration.html: Added.
     12
    1132012-07-13  Kent Tamura  <tkent@chromium.org>
    214

  • trunk/Source/WebCore/ChangeLog

    r122658 r122660  
     12012-07-13  Ryosuke Niwa  <rniwa@webkit.org>
     2
     3        Iterating backwards over HTMLCollection is O(n^2)
     4        https://bugs.webkit.org/show_bug.cgi?id=91306
     5
     6        Reviewed by Anders Carlsson.
     7
     8        Fixed the bug by introducing itemBefore that iterates nodes backwards to complement itemAfter.
     9        Unfortunately, some HTML collections such as HTMLFormCollection and HTMLTableRowsCollection have
     10        its own itemAfter function and writing an equivalent itemBefore is somewhat tricky. For now,
     11        added a new boolean flag indicating whether a given HTML collection supports itemBefore or not,
     12        and left those HTML collections that override itemAfter alone.
     13
     14        This also paves our way to share more code between DynamicNodeList and HTMLCollection.
     15
     16        Test: perf/htmlcollection-backwards-iteration.html
     17
     18        * dom/DynamicNodeList.h:
     19        (WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): Takes ItemBeforeSupportType.
     20        (WebCore::DynamicNodeListCacheBase::supportsItemBefore): Added.
     21        (DynamicNodeListCacheBase):
     22        (WebCore::DynamicNodeListCacheBase::setItemCache): Replaced a FIXME by an assertion now that
     23        we can.
     24        * html/HTMLAllCollection.cpp:
     25        (WebCore::HTMLAllCollection::HTMLAllCollection): Supports itemBefore since it doesn't override
     26        itemAfter.
     27        * html/HTMLCollection.cpp:
     28        (WebCore::HTMLCollection::HTMLCollection):
     29        (WebCore::HTMLCollection::create):
     30        (WebCore::isAcceptableElement): Made it a static local function instead of a static member.
     31        (WebCore::nextNode): Templatized.
     32        (WebCore::itemBeforeOrAfter): Extracted from itemAfter and templatized.
     33        (WebCore::HTMLCollection::itemBefore): Added.
     34        (WebCore::HTMLCollection::itemAfter):
     35        (WebCore::HTMLCollection::shouldSearchFromFirstItem): Added. Determines whether we should reset
     36        the item cache to the first item. We obviously do if the cache is invalid. If the target offset
     37        is after the cached offset, then we shouldn't go back regardless of availability of itemBefore.
     38        Otherwise, we go back to the first item iff itemBefore is not available or the distance from
     39        the cached offset to the target offset is greater than the target offset itself.
     40        (WebCore::HTMLCollection::length):
     41        (WebCore::HTMLCollection::item): Use the term "offset" to match the terminology elsewhere.
     42        (WebCore::HTMLCollection::itemBeforeOrAfterCachedItem): Ditto. Also added the logic to iterate
     43        nodes backwards using itemBefore. Once we're in this branch, we should always find a matching
     44        item since the target offset was less than the cached offset, and offsets are non-negative.
     45        If we had ever reached the end of the loop without finding an item, it indicates that the cache
     46        has been invalid and we have some serious bug elsewhere.
     47        * html/HTMLCollection.h:
     48        (WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase):
     49        (HTMLCollection):
     50        * html/HTMLOptionsCollection.cpp:
     51        (WebCore::HTMLOptionsCollection::HTMLOptionsCollection): Supports itemBefore since it doesn't
     52        override itemAfter.
     53        * html/HTMLFormCollection.cpp:
     54        (WebCore::HTMLFormCollection::HTMLFormCollection): Doesn't support itemBefore as it overrides
     55        itemAfter.
     56        * html/HTMLNameCollection.cpp:
     57        (WebCore::HTMLNameCollection::HTMLNameCollection): Ditto.
     58        * html/HTMLPropertiesCollection.cpp:
     59        (WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
     60        * html/HTMLTableRowsCollection.cpp:
     61        (WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection):
     62
    1632012-07-13  Eric Penner  <epenner@google.com>
    264

  • trunk/Source/WebCore/dom/DynamicNodeList.h

    r122649 r122660  
    4444class DynamicNodeListCacheBase {
    4545public:
    46     DynamicNodeListCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType = InvalidCollectionType)
     46    enum ItemBeforeSupportType {
     47        DoNotSupportItemBefore,
     48        SupportItemBefore,
     49    };
     50
     51    DynamicNodeListCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType,
     52        CollectionType collectionType = InvalidCollectionType, ItemBeforeSupportType itemBeforeSupportType = DoNotSupportItemBefore)
    4753        : m_cachedItem(0)
    4854        , m_isLengthCacheValid(false)
    … …  
    5258        , m_isNameCacheValid(false)
    5359        , m_collectionType(collectionType)
     60        , m_supportsItemBefore(itemBeforeSupportType == SupportItemBefore)
    5461    {
    5562        ASSERT(m_invalidationType == static_cast<unsigned>(invalidationType));
    … …  
    6774
    6875protected:
     76    bool supportsItemBefore() const { return m_supportsItemBefore; }
     77
    6978    ALWAYS_INLINE bool isItemCacheValid() const { return m_isItemCacheValid; }
    7079    ALWAYS_INLINE Node* cachedItem() const { return m_cachedItem; }
    … …  
    8089    ALWAYS_INLINE void setItemCache(Node* item, unsigned offset) const
    8190    {
    82         // FIXME: Assert that item is not null once we've updated DynamicNodeList.
     91        ASSERT(item);
    8392        m_cachedItem = item;
    8493        m_cachedItemOffset = offset;
    … …  
    101110    mutable unsigned m_isNameCacheValid : 1;
    102111    const unsigned m_collectionType : 5;
     112    const unsigned m_supportsItemBefore : 1;
    103113};
    104114

  • trunk/Source/WebCore/html/HTMLAllCollection.cpp

    r122621 r122660  
    3737
    3838HTMLAllCollection::HTMLAllCollection(Document* document)
    39     : HTMLCollection(document, DocAll)
     39    : HTMLCollection(document, DocAll, SupportItemBefore)
    4040{
    4141}

  • trunk/Source/WebCore/html/HTMLCollection.cpp

    r122621 r122660  
    153153   
    154154
    155 HTMLCollection::HTMLCollection(Node* base, CollectionType type)
    156     : HTMLCollectionCacheBase(rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type)
     155HTMLCollection::HTMLCollection(Node* base, CollectionType type, ItemBeforeSupportType itemBeforeSupportType)
     156    : HTMLCollectionCacheBase(rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type, itemBeforeSupportType)
    157157    , m_base(base)
    158158{
    … …  
    163163PassRefPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
    164164{
    165     return adoptRef(new HTMLCollection(base, type));
     165    return adoptRef(new HTMLCollection(base, type, SupportItemBefore));
    166166}
    167167
    … …  
    180180}
    181181
    182 inline bool HTMLCollection::isAcceptableElement(Element* element) const
    183 {
    184     if (!element->isHTMLElement() && !(type() == DocAll || type() == NodeChildren))
    185         return false;
    186 
    187     switch (type()) {
     182static inline bool isAcceptableElement(CollectionType type, Element* element)
     183{
     184    if (!element->isHTMLElement() && !(type == DocAll || type == NodeChildren))
     185        return false;
     186
     187    switch (type) {
    188188    case DocImages:
    189189        return element->hasLocalName(imgTag);
    … …  
    238238}
    239239
    240 static ALWAYS_INLINE Node* nextNode(Node* base, Node* previous, bool onlyIncludeDirectChildren)
    241 {
    242     return onlyIncludeDirectChildren ? previous->traverseNextSibling(base) : previous->traverseNextNode(base);
     240template<bool forward>
     241static Node* nextNode(Node* base, Node* previous, bool onlyIncludeDirectChildren)
     242{
     243    if (forward)
     244        return onlyIncludeDirectChildren ? previous->nextSibling() : previous->traverseNextNode(base);
     245    else
     246        return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traversePreviousNode(base);
     247}
     248
     249template<bool forward>
     250static Element* itemBeforeOrAfter(CollectionType type, Node* base, unsigned& offsetInArray, Node* previous)
     251{
     252    ASSERT_UNUSED(offsetInArray, !offsetInArray);
     253    bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren(type);
     254    Node* rootNode = base;
     255    Node* current = previous ? nextNode<forward>(rootNode, previous, onlyIncludeDirectChildren) : (forward ? base->firstChild() : base->lastChild());
     256
     257    for (; current; current = nextNode<forward>(rootNode, current, onlyIncludeDirectChildren)) {
     258        if (current->isElementNode() && isAcceptableElement(type, toElement(current)))
     259            return toElement(current);
     260    }
     261
     262    return 0;
     263}
     264
     265Element* HTMLCollection::itemBefore(unsigned& offsetInArray, Element* previous) const
     266{
     267    return itemBeforeOrAfter<false>(type(), base(), offsetInArray, previous);
    243268}
    244269
    245270Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
    246271{
    247     ASSERT_UNUSED(offsetInArray, !offsetInArray);
    248     bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren(type());
    249     Node* rootNode = base();
    250     Node* current = previous ? nextNode(rootNode, previous, onlyIncludeDirectChildren) : m_base->firstChild();
    251 
    252     for (; current; current = nextNode(rootNode, current, onlyIncludeDirectChildren)) {
    253         if (current->isElementNode() && isAcceptableElement(toElement(current)))
    254             return toElement(current);
    255     }
    256 
    257     return 0;
     272    return itemBeforeOrAfter<true>(type(), base(), offsetInArray, previous);
     273}
     274   
     275bool ALWAYS_INLINE HTMLCollection::shouldSearchFromFirstItem(unsigned offset) const
     276{
     277    if (!isItemCacheValid())
     278        return true;
     279
     280    ASSERT(offset != cachedItemOffset());
     281    if (offset > cachedItemOffset())
     282        return false;
     283
     284    unsigned distanceFromCachedItem = cachedItemOffset() - offset;
     285    return !supportsItemBefore() || offset < distanceFromCachedItem;
    258286}
    259287
    … …  
    273301    do {
    274302        offset++;
    275     } while (itemAfterCachedItem(offset));
     303    } while (itemBeforeOrAfterCachedItem(offset));
    276304
    277305    setLengthCache(offset);
    … …  
    279307}
    280308
    281 Node* HTMLCollection::item(unsigned index) const
    282 {
    283     if (isItemCacheValid() && cachedItemOffset() == index)
     309Node* HTMLCollection::item(unsigned offset) const
     310{
     311    if (isItemCacheValid() && cachedItemOffset() == offset)
    284312        return cachedItem();
    285313
    286     if (isLengthCacheValid() && cachedLength() <= index)
     314    if (isLengthCacheValid() && cachedLength() <= offset)
    287315        return 0;
    288316
    … …  
    292320#endif
    293321
    294     if (!isItemCacheValid() || cachedItemOffset() > index) {
     322    if (shouldSearchFromFirstItem(offset)) {
    295323        unsigned offsetInArray = 0;
    296324        Node* firstItem = itemAfter(offsetInArray, 0);
    … …  
    301329        setItemCache(firstItem, 0, offsetInArray);
    302330        ASSERT(!cachedItemOffset());
    303         if (!index)
     331        if (!offset)
    304332            return cachedItem();
    305333    }
    306334
    307     return itemAfterCachedItem(index);
    308 }
    309 
    310 Element* HTMLCollection::itemAfterCachedItem(unsigned index) const
    311 {
    312     unsigned currentIndex = cachedItemOffset();
     335    return itemBeforeOrAfterCachedItem(offset);
     336}
     337
     338Element* HTMLCollection::itemBeforeOrAfterCachedItem(unsigned offset) const
     339{
     340    unsigned currentOffset = cachedItemOffset();
    313341    ASSERT(cachedItem()->isElementNode());
    314342    Element* currentItem = toElement(cachedItem());
    315     ASSERT(currentIndex < index);
     343    ASSERT(currentOffset != offset);
    316344
    317345    unsigned offsetInArray = cachedElementsArrayOffset();
     346
     347    if (offset < cachedItemOffset()) {
     348        ASSERT(supportsItemBefore());
     349        while ((currentItem = itemBefore(offsetInArray, currentItem))) {
     350            ASSERT(currentOffset);
     351            currentOffset--;
     352            if (currentOffset == offset) {
     353                setItemCache(currentItem, currentOffset, offsetInArray);
     354                return currentItem;
     355            }
     356        }
     357        ASSERT_NOT_REACHED();
     358        return 0;
     359    }
     360
    318361    while ((currentItem = itemAfter(offsetInArray, currentItem))) {
    319         currentIndex++;
    320         if (currentIndex == index) {
    321             setItemCache(currentItem, currentIndex, offsetInArray);
     362        currentOffset++;
     363        if (currentOffset == offset) {
     364            setItemCache(currentItem, currentOffset, offsetInArray);
    322365            return currentItem;
    323366        }
    324367    }
    325368
    326     setLengthCache(currentIndex);
     369    setLengthCache(currentOffset);
    327370
    328371    return 0;

  • trunk/Source/WebCore/html/HTMLCollection.h

    r122637 r122660  
    4040class HTMLCollectionCacheBase : public DynamicNodeListCacheBase {
    4141public:
    42     HTMLCollectionCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType)
    43         : DynamicNodeListCacheBase(rootType, invalidationType, collectionType)
     42    HTMLCollectionCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType, ItemBeforeSupportType itemBeforeSupportType)
     43        : DynamicNodeListCacheBase(rootType, invalidationType, collectionType, itemBeforeSupportType)
    4444        , m_cachedElementsArrayOffset(0)
    4545    {
    … …  
    107107
    108108protected:
    109     HTMLCollection(Node* base, CollectionType);
     109    HTMLCollection(Node* base, CollectionType, ItemBeforeSupportType);
    110110
    111111    virtual void updateNameCache() const;
    … …  
    115115    bool checkForNameMatch(Element*, bool checkName, const AtomicString& name) const;
    116116
    117     Element* itemAfterCachedItem(unsigned) const;
    118     bool isAcceptableElement(Element*) const;
     117    Element* itemBefore(unsigned& offsetInArray, Element*) const;
     118    bool shouldSearchFromFirstItem(unsigned offset) const;
     119    Element* itemBeforeOrAfterCachedItem(unsigned offset) const;
    119120
    120121    RefPtr<Node> m_base;

  • trunk/Source/WebCore/html/HTMLFormCollection.cpp

    r122621 r122660  
    3838
    3939HTMLFormCollection::HTMLFormCollection(Element* base)
    40     : HTMLCollection(base, FormControls)
     40    : HTMLCollection(base, FormControls, DoNotSupportItemBefore)
    4141{
    4242    ASSERT(base->hasTagName(formTag) || base->hasTagName(fieldsetTag));

  • trunk/Source/WebCore/html/HTMLNameCollection.cpp

    r122518 r122660  
    3434
    3535HTMLNameCollection::HTMLNameCollection(Document* document, CollectionType type, const AtomicString& name)
    36     : HTMLCollection(document, type)
     36    : HTMLCollection(document, type, DoNotSupportItemBefore)
    3737    , m_name(name)
    3838{

  • trunk/Source/WebCore/html/HTMLOptionsCollection.cpp

    r122115 r122660  
    2929
    3030HTMLOptionsCollection::HTMLOptionsCollection(Element* select)
    31     : HTMLCollection(select, SelectOptions)
     31    : HTMLCollection(select, SelectOptions, SupportItemBefore)
    3232{
    3333    ASSERT(select->hasTagName(HTMLNames::selectTag));

  • trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp

    r122621 r122660  
    5252
    5353HTMLPropertiesCollection::HTMLPropertiesCollection(Node* itemNode)
    54     : HTMLCollection(itemNode, ItemProperties)
     54    : HTMLCollection(itemNode, ItemProperties, DoNotSupportItemBefore)
    5555    , m_hasPropertyNameCache(false)
    5656    , m_hasItemRefElements(false)

  • trunk/Source/WebCore/html/HTMLTableRowsCollection.cpp

    r122518 r122660  
    153153// differ between compilers.
    154154HTMLTableRowsCollection::HTMLTableRowsCollection(Element* table)
    155     : HTMLCollection(table, TableRows)
     155    : HTMLCollection(table, TableRows, DoNotSupportItemBefore)
    156156{
    157157    ASSERT(table->hasTagName(tableTag));
Note: See TracChangeset for help on using the changeset viewer.