[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 #13 from Darin Adler <darin at apple.com>  2010-04-05 10:00:53 PST ---
(In reply to comment #12)
> (In reply to comment #9)
> > (From update of attachment 52526 [details] [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.

I'd like to see some actual test data. It should be easy to make something so
huge that you can easily see these effects with a "stopwatch test".

One thing that's different from our list marker code and our other similar code
is that it's not coalesced. The values of markers are updated immediately, even
if they are about to be invalidated a moment later by another DOM modification.
Whereas other sorts of updates use an invalidation scheme and then get updated
later, for example when layout occurs.

> 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.

There's another patch adding support for the "reversed" attribute for <ol>,
which will probably change these assumptions and thus change this code.

An improvement that helps improve the case where you're constantly adding a new
last item for an existing list is probably worthwhile. If we can prove this
patch doesn't make any case significantly worse, then we can definitely leave
optimization for a later patch. But we do need to double check that we haven't
added any new bad performance behavior. I don't want any nasty surprises later
from people testing live websites.

> > > +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.

What about enclosingList->renderer()? If it's really true that neither should
ever be 0 then I think we should add assertions to that effect. And I also
suggest an early return after the assertions.

It's OK to have code to handle the 0 case without crashing, but I would suggest
an early return rather than "iterate the entire document" behavior for that
case.

> using IDs instead of node objects would make the tests more complicated.

It would.

> We could, however, automate the assignment within the dumpList() JS function.

Yes.

> > 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.

There are no other existing layout test controller functions that do this;
things like include files and type casting will be covering new territory. But
I'm encouraged by your optimism.

If this really is easy, I'd be tempted to change the counter test function to
work this way instead of depending on IDs.

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