[Webkit-unassigned] [Bug 37060] List item markers are not always updated after changes in the DOM

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=37060





--- Comment #12 from Jakub Wieczorek <jwieczorek at webkit.org>  2010-04-05 09:22:03 PST ---
(In reply to comment #9)
> (From update of attachment 52526 [details])
> My biggest worry here is that this algorithm seems to iterate the entire
> document every time you add a list item. And if you add multiple list items, it
> seems to iterate the document once per list item. That can't be good for
> performance. Sorry I didn't mention that last time. Is there some way to
> quantify this? I don't think other browsers have this sort of O(n^2) behavior
> when adding list items, but I could be wrong.

We're not making the complexity worse as such (it was already pretty much n^2)
but yes, we're possibly making the code slower for some cases. To fix the bugs
we're fixing here we need to be traversing more than before.

We can benefit from the assumption, that whenever a list item is marked as
needing an update to the marker, then all the subsequent ones will be too (this
was not true before but with this patch is). I can't think of any situation
where that would not be the case:
1) changing the start value for a list revaluates the whole list
2) changing the value of an item revaluates all the subsequent ones
3) adding/removing items revaluates all the subsequent ones

If this is true, then I could improve this, either as part of this patch, or a
separate one.

> Some good performance tests would be to make a extremely large list and test
> performance of adding items, an extremely document without lists and test
> performance of adding list items, a small list of extremely large lists and
> test the performance of adding an item at the top level.
> 
> It would be good to know if this patch has significantly changed performance or
> not for those cases. It may be that the only cases that are slower with this
> patch are unlikely or unimportant cases, but we should find that out with some
> testing.
> 
> > +        RenderListItem* item = toRenderListItem(renderer);
> > +        Node* otherList = enclosingList(item);
> >          // This item is part of our current list, so it's what we're looking for.
> >          if (list == otherList)
> > -            return toRenderListItem(renderer);
> > +            return item;
> 
> This variable named item shadows the function argument. Might be OK. It's also
> OK to repeat the toRenderListItem call twice, because it's just an inlined
> typecast.
> 
> > +void RenderListItem::updateListMarkerNumbers()
> > +{
> > +    Node* listNode = enclosingList(this);
> > +    RenderObject* list = listNode ? listNode->renderer() : 0;
> > +
> > +    for (RenderObject* child = this->nextInPreOrder(list); child; child = child->nextInPreOrder(list)) {
> > +        if (child->node() && isList(child->node())) {
> > +            // We've found a nested, independent list: nothing to do here.
> > +            child = child->nextInPreOrderAfterChildren(list)->previousInPreOrder();
> > +            continue;
> > +        }
> > +
> > +        if (child->isListItem())
> > +            toRenderListItem(child)->updateValue();
> > +    }
> > +}
> 
> I asked in the previous patch whether it was OK, when the local variable list
> is 0, to iterate the entire document looking for other list items. Because that
> is what nextInPreOrder will do when passed a 0. I did not see an answer to my
> question, and the question remains. It seems potentially bad for performance.
> Is this tested in a test case?

I responded:
> Well, I made a mistake to let enclosingList be 0 in the first place. For some
> reason I came to that conclusion when I saw fast/lists/anonymous-items.html
> crashing with my patch but it turned out to be a different issue which I fixed
> even before the first version of the patch.

Again, should have been more precise: enclosingList would never be 0 now.

> > +    if (!element->renderer())
> > +        return String();
> > +
> > +    RenderObject* renderer = element->renderer();
> > +    if (!renderer->isListItem())
> > +        return String();
> 
> It would be a little more elegant to use the local variable, renderer, for the
> null check as well as the list item check.
> 
> > +    WEBKIT_API gchar*
> > +    webkit_web_frame_marker_text_for_list_item(WebKitWebFrame* frame, JSValueRef nodeObject);
> 
> Normally it would be the responsibility of the layout test controller file in
> DumpRenderTree, which binds test controller JavaScript calls to WebKit calls,
> to convert from a JSValueRef all the way to the platform's API representation
> for an Element.
> 
> Last time I advised you to make sure you didn't do JSValueRef to JSObjectRef in
> one place, and then JSObjectRef to Element* in another. But I think that using
> actual JSValueRef in the API on GTK is not great. I don't think functions at
> the WebKit API level should be responsible for converting a JavaScript value
> into an element pointer. I see now that for ports that don't have a public DOM
> API, it's difficult to figure out what type to use to pass around a pointer to
> a element. That's the reason that we ended up using an ID instead of an element
> pointer in counterValueForElementById. 

Right, but using IDs instead of node objects would make the tests more
complicated. We could, however, automate the assignment within the dumpList()
JS function.

> While you found a way to make this work
> for GTK and Qt, I'm concerned that it will be tricky to get this working on the
> other platforms.

What exactly would be tricky with implementing this on other platforms? By
grepping the sources, it looks like the JSC C API is being used in the API
layer both of the Mac and Win ports.

> This seems almost ready to go in, but review- because of my performance
> question and the "is this the right thing to do when the list is 0" question

I'll post one more patch to fix the GTK+ and Windows builds and address some of
your comments. Thanks.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.