Bug 91320

Summary: Accessing the last item in children should be a constant time operation
Product: WebKit Reporter: Ryosuke Niwa <rniwa>
Component: DOMAssignee: Ryosuke Niwa <rniwa>
Status: RESOLVED FIXED    
Severity: Normal CC: andersca, darin, haraken, kling, koivisto, ojan, sam
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 91306    
Bug Blocks: 89919    
Attachments:
Description Flags
Fixes the bug ojan: review+

Description Ryosuke Niwa 2012-07-14 03:38:57 PDT
element.children[element.children.length - 1] should be a constant time operation with respect to the number of child nodes element has.
Comment 1 Ryosuke Niwa 2012-07-14 03:47:56 PDT
Created attachment 152418 [details]
Fixes the bug
Comment 2 Ryosuke Niwa 2012-07-14 03:48:55 PDT
(provided that the length cache is available).
Comment 3 Ryosuke Niwa 2012-07-14 04:13:44 PDT
Once this patch is landed, I'll post the final unification patch that merges DynamicNodeList::item and HTMLCollection::item.
Comment 4 Ojan Vafai 2012-07-14 09:41:50 PDT
Comment on attachment 152418 [details]
Fixes the bug

View in context: https://bugs.webkit.org/attachment.cgi?id=152418&action=review

> Source/WebCore/html/HTMLCollection.cpp:336
> +    if (isLengthCacheValid() && supportsItemBefore() && isLastItemCloserThanLastOrCachedItem(offset)) {
> +        // FIXME: Need to figure out the last offset in array for HTMLFormCollection and HTMLPropertiesCollection
> +        unsigned unusedOffsetInArray = 0;
> +        Node* lastItem = itemBefore(unusedOffsetInArray, 0);
> +        ASSERT(!unusedOffsetInArray);
> +        ASSERT(lastItem);
> +        setItemCache(lastItem, cachedLength() - 1, 0);
> +    } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) {

This would probably be more readable if you had shouldSearchFromFirstItem and shouldSearchFromLastItem helper functions.
Comment 5 Ryosuke Niwa 2012-07-14 11:18:29 PDT
Comment on attachment 152418 [details]
Fixes the bug

View in context: https://bugs.webkit.org/attachment.cgi?id=152418&action=review

>> Source/WebCore/html/HTMLCollection.cpp:336
>> +    } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) {
> 
> This would probably be more readable if you had shouldSearchFromFirstItem and shouldSearchFromLastItem helper functions.

I did that initially but then realized that the fact such as length is cached, and itemBefore is supported, etc... isn't obvious in the first if statement.
Also, if I did add those two functions then I have to assume that either shouldSearchFromFirstItem or shouldSearchFromLastItem is called first
since conditions in the function becomes way too complicated otherwise and making such call order assumption seemed error prone.
Comment 6 Ryosuke Niwa 2012-07-14 14:38:44 PDT
Committed r122672: <http://trac.webkit.org/changeset/122672>