Bug 37060

Created attachment 52495 [details] patch This patch addresses the problem. I've added a function to LayoutTestController that returns the marker number for a list item, according to Darin's idea in https://bugs.webkit.org/show_bug.cgi?id=36724 and an JS function that output a readable representation of a list, so that the tests don't need to dump the whole render tree.

Attachment 52495 [details] did not build on win: Build output: http://webkit-commit-queue.appspot.com/results/1583216

Created attachment 52512 [details] patch Added stubs for the new LayoutTestController function in Mac and Win ports and skipped the new tests on these platforms. This will most likely fix the Windows build failure.

Comment on attachment 52512 [details] patch > static Node* enclosingList(const RenderObject* renderer) > { > - Node* node = renderer->node(); > - if (node) > - return enclosingList(node); > - > - renderer = renderer->parent(); > while (renderer && !renderer->node()) > renderer = renderer->parent(); > > - node = renderer->node(); > + if (!renderer) > + return 0; > + > + Node* node = renderer->node(); > if (isList(node)) > return node; This change means the code now walks up the render tree before walking up the DOM tree. How did you determine that there was no case where that changed the function result? > +void updateListMarkerNumbers(RenderObject* listItem) > +{ > + ASSERT(listItem->isListItem()); Since this function is designed to only be called on a RenderListItem, its argument type should be RenderListItem*, not RenderObject*. The callers should call toRenderListItem, which will do the type cast and assertion. In fact, you should make it a member function, since it's in the RenderListItem.cpp file and is a basic part of what a RenderListItem does. I suggest also changing the argument type of the enclosingList function to RenderListItem*. > + RenderObject* child = listItem->nextInPreOrder(list); Is this the right thing to do when list is 0? It means you'll walk the entire document looking for other list items. Is that really what we want to do for items outside the document. > + while (child) { This should probably be written as a for loop instead of a while loop, although the line will end up being long. But it would make the loop logic easier to understand. > + // We've found a nested, independent list - nothing to do here. Instead of a hyphen separating these phrases, I'd suggest a colon. > // renumber ordered lists > if (oldChild->isListItem()) > - updateListMarkerNumbers(oldChild->nextSibling()); > + updateListMarkerNumbers(oldChild); > + // renumber ordered lists > + if (newChild->isListItem()) > + updateListMarkerNumbers(newChild); > + // renumber ordered lists > + if (child->isListItem()) > + updateListMarkerNumbers(child); If we really need this same comment every time we call the updateListMarkerNumbers function, then I think we need to rename the function instead. Please omit the comment. > +gchar* webkit_web_frame_marker_text_for_list_item(WebKitWebFrame* frame, JSObjectRef nodeObject) > +{ > + JSC::JSObject* object = toJS(nodeObject); > + if (!object || !object->inherits(&JSHTMLElement::s_info)) > + return 0; > + > + HTMLElement* element = static_cast<JSHTMLElement*>(object)->impl(); > + if (!element || !element->renderer()) > + return 0; > + > + RenderObject* renderer = element->renderer(); > + if (!renderer->isListItem()) > + return 0; > + > + String markerText = toRenderListItem(renderer)->markerText(); > + return g_strdup(markerText.utf8().data()); > +} There's no reason to limit this to HTML elements. Non-HTML elements can be styled and end up as list items. You should check for JSElement rather than JSHTMLElement. This function as written isn't safe. You can't grab an element's renderer without first calling Document::updateLayout. You should move the part of this function that goes from an element to marker text out of Qt-specific and GTK-specific code into RenderTreeAsText.cpp, alongside the similar counterValueForElement function and using similar implementation techniques. > +static JSValueRef markerTextForListItemCallback(JSContextRef context, JSObjectRef, JSObjectRef thisObject, size_t argumentCount, const JSValueRef arguments[], JSValueRef* exception) > +{ > + if (argumentCount < 1) > + return JSValueMakeUndefined(context); > + > + LayoutTestController* controller = static_cast<LayoutTestController*>(JSObjectGetPrivate(thisObject)); > + JSObjectRef nodeObject = JSValueToObject(context, arguments[0], exception); > + ASSERT(!*exception); > + > + return JSValueMakeString(context, controller->markerTextForListItem(nodeObject).get()); > +} I find the division of responsibilities here a little strange. This function handles converting the JSValue to a JSObject, but not checking the type of JSObject. I think it would be cleaner to pass the JSValue in to the controller since it already has to deal with JavaScript type checking to check that this is a node object. review- because I think at least some of these things should be fixed before landing

Created attachment 52526 [details] patch (In reply to comment #4) > (From update of attachment 52512 [details]) > > static Node* enclosingList(const RenderObject* renderer) > > { > > - Node* node = renderer->node(); > > - if (node) > > - return enclosingList(node); > > - > > - renderer = renderer->parent(); > > while (renderer && !renderer->node()) > > renderer = renderer->parent(); > > > > - node = renderer->node(); > > + if (!renderer) > > + return 0; > > + > > + Node* node = renderer->node(); > > if (isList(node)) > > return node; > > This change means the code now walks up the render tree before walking up the > DOM tree. How did you determine that there was no case where that changed the > function result? Actually it was doing this before too, I just wanted to formulate it simpler. But you're right, there is one possible behavior change: for a list that also acts as a list item, it would return the list itself. Anyway, I'll just revert this hunk as it's not even necessary for this patch. > > +void updateListMarkerNumbers(RenderObject* listItem) > > +{ > > + ASSERT(listItem->isListItem()); > > Since this function is designed to only be called on a RenderListItem, its > argument type should be RenderListItem*, not RenderObject*. The callers should > call toRenderListItem, which will do the type cast and assertion. > > In fact, you should make it a member function, since it's in the > RenderListItem.cpp file and is a basic part of what a RenderListItem does. > > I suggest also changing the argument type of the enclosingList function to > RenderListItem*. Done. > > + RenderObject* child = listItem->nextInPreOrder(list); > > Is this the right thing to do when list is 0? It means you'll walk the entire > document looking for other list items. Is that really what we want to do for > items outside the document. 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. > > + while (child) { > > This should probably be written as a for loop instead of a while loop, although > the line will end up being long. But it would make the loop logic easier to > understand. I changed it to be a for loop but personally I don't find it easier to read as we're ending up with something like: if (child->node() && isList(child->node())) { // We've found a nested, independent list: nothing to do here. child = child->nextInPreOrderAfterChildren(list)->previousInPreOrder(); continue; } > > + // We've found a nested, independent list - nothing to do here. > > Instead of a hyphen separating these phrases, I'd suggest a colon. Fixed. > > // renumber ordered lists > > if (oldChild->isListItem()) > > - updateListMarkerNumbers(oldChild->nextSibling()); > > + updateListMarkerNumbers(oldChild); > > > + // renumber ordered lists > > + if (newChild->isListItem()) > > + updateListMarkerNumbers(newChild); > > > + // renumber ordered lists > > + if (child->isListItem()) > > + updateListMarkerNumbers(child); > > If we really need this same comment every time we call the > updateListMarkerNumbers function, then I think we need to rename the function > instead. Please omit the comment. Yeah, that original comment wasn't really valuable. > > +gchar* webkit_web_frame_marker_text_for_list_item(WebKitWebFrame* frame, JSObjectRef nodeObject) > > +{ > > + JSC::JSObject* object = toJS(nodeObject); > > + if (!object || !object->inherits(&JSHTMLElement::s_info)) > > + return 0; > > + > > + HTMLElement* element = static_cast<JSHTMLElement*>(object)->impl(); > > + if (!element || !element->renderer()) > > + return 0; > > + > > + RenderObject* renderer = element->renderer(); > > + if (!renderer->isListItem()) > > + return 0; > > + > > + String markerText = toRenderListItem(renderer)->markerText(); > > + return g_strdup(markerText.utf8().data()); > > +} > > There's no reason to limit this to HTML elements. Non-HTML elements can be > styled and end up as list items. You should check for JSElement rather than > JSHTMLElement. Fixed. > This function as written isn't safe. You can't grab an element's renderer > without first calling Document::updateLayout. Indeed, that's why I needed to explicitly trigger a layout in the tests. Doing this in the function makes more sense. > You should move the part of this function that goes from an element to marker > text out of Qt-specific and GTK-specific code into RenderTreeAsText.cpp, > alongside the similar counterValueForElement function and using similar > implementation techniques. Done. > > +static JSValueRef markerTextForListItemCallback(JSContextRef context, JSObjectRef, JSObjectRef thisObject, size_t argumentCount, const JSValueRef arguments[], JSValueRef* exception) > > +{ > > + if (argumentCount < 1) > > + return JSValueMakeUndefined(context); > > + > > + LayoutTestController* controller = static_cast<LayoutTestController*>(JSObjectGetPrivate(thisObject)); > > + JSObjectRef nodeObject = JSValueToObject(context, arguments[0], exception); > > + ASSERT(!*exception); > > + > > + return JSValueMakeString(context, controller->markerTextForListItem(nodeObject).get()); > > +} > > I find the division of responsibilities here a little strange. This function > handles converting the JSValue to a JSObject, but not checking the type of > JSObject. I think it would be cleaner to pass the JSValue in to the controller > since it already has to deal with JavaScript type checking to check that this > is a node object. Done. > review- because I think at least some of these things should be fixed before > landing Thanks, can you take another look?

Attachment 52526 [details] did not build on gtk: Build output: http://webkit-commit-queue.appspot.com/results/1652163

(In reply to comment #5) > Created an attachment (id=52526) [details] > patch > > (In reply to comment #4) > > (From update of attachment 52512 [details] [details]) > > > static Node* enclosingList(const RenderObject* renderer) > > > { > > > - Node* node = renderer->node(); > > > - if (node) > > > - return enclosingList(node); > > > - > > > - renderer = renderer->parent(); > > > while (renderer && !renderer->node()) > > > renderer = renderer->parent(); > > > > > > - node = renderer->node(); > > > + if (!renderer) > > > + return 0; > > > + > > > + Node* node = renderer->node(); > > > if (isList(node)) > > > return node; > > > > This change means the code now walks up the render tree before walking up the > > DOM tree. How did you determine that there was no case where that changed the > > function result? > > Actually it was doing this before too Huh? The old code says if there is a node, then call enclosingList, walking up the DOM tree, and don't go up the render tree at all. The new code does not do that. We can debate that later if needed when we try to land this change, I guess. > Anyway, I'll just revert > this hunk as it's not even necessary for this patch. All we need to land this is a test case demonstrating what the code change fixes. > I changed it to be a for loop but personally I don't find it easier to read as > we're ending up with something like: > > if (child->node() && isList(child->node())) { > // We've found a nested, independent list: nothing to do here. > child = child->nextInPreOrderAfterChildren(list)->previousInPreOrder(); > continue; > } Yes, that's not good. You should not let it be like that! Lets go back to the way you have it.

Attachment 52526 [details] did not build on win: Build output: http://webkit-commit-queue.appspot.com/results/1581254

Comment on attachment 52526 [details] patch 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. 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? > + 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. 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. 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

(In reply to comment #7) > Huh? The old code says if there is a node, then call enclosingList, walking up > the DOM tree, and don't go up the render tree at all. The new code does not do > that. We can debate that later if needed when we try to land this change, I > guess. I'm not sure I am following. This loop: while (renderer && !renderer->node()) renderer = renderer->parent(); will execute 0 times when the renderer has a node attached to it, which will bring us to: Node* node = renderer->node(); if (isList(node)) return node; return enclosingList(node); so basically it's the same code, just formulated in a different way. > > Anyway, I'll just revert > > this hunk as it's not even necessary for this patch. > > All we need to land this is a test case demonstrating what the code change > fixes. The thing is it was not supposed to fix anything. It was just an unnecessary cleanup. I should have been more clear about it before. > > I changed it to be a for loop but personally I don't find it easier to read as > > we're ending up with something like: > > > > if (child->node() && isList(child->node())) { > > // We've found a nested, independent list: nothing to do here. > > child = child->nextInPreOrderAfterChildren(list)->previousInPreOrder(); > > continue; > > } > > Yes, that's not good. You should not let it be like that! Lets go back to the > way you have it.

(In reply to comment #10) > so basically it's the same code, just formulated in a different way. I see. > The thing is it was not supposed to fix anything. It was just an unnecessary > cleanup. I should have been more clear about it before. Oh, OK. We can still land it later.

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

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

(In reply to comment #13) > > 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". OK, I'll give it a go. > 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. Are you sure this is the case? What the patch does (and so does the old code) is calling updateValue() on the RenderListItems, which is: void RenderListItem::updateValue() { if (!m_hasExplicitValue) { m_isValueUpToDate = false; if (m_marker) m_marker->setNeedsLayoutAndPrefWidthsRecalc(); } } And then, on the next layout, RenderListMarker pulls the value, which is lazily calculated in updateValueNow(). But still, what we're doing too many times is marking items as outdated. > > 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. Yes. For a reversed list, however, an opposite assumption would be true (adding/removing an item requires all the previous ones to be updated or the whole list for other changes, as above). > 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're adding a new last item for an existing list, we need to find out if it's the last one. But anyway, we only go through the nodes after the new item within the list subtree. So this case should already be fast. > 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. I understand that. I hope we can simply add the optimization I mentioned as it's quite straightforward. This would make the code even faster than it was before (assuming I got it right).

(In reply to comment #14) > But still, what we're doing too many times is marking items as outdated. Got it. Your plan sounds good.

Created attachment 52553 [details] patch A revised patch addressing your comments and the build failures.

Attachment 52553 [details] did not pass style-queue: Failed to run "WebKitTools/Scripts/check-webkit-style" exit_code: 1 WARNING: File exempt from style guide. Skipping: "WebKit/qt/Api/qwebframe_p.h" WARNING: File exempt from style guide. Skipping: "WebKit/qt/Api/qwebframe.cpp" WebKitTools/DumpRenderTree/win/LayoutTestControllerWin.cpp:42: Alphabetical sorting problem. [build/include_order] [4] WARNING: File exempt from style guide. Skipping: "WebKit/qt/Api/qwebelement.h" Total errors found: 1 in 38 files If any of these errors are false positives, please file a bug against check-webkit-style.

Comment on attachment 52553 [details] patch > +JSRetainPtr<JSStringRef> LayoutTestController::markerTextForListItem(JSValueRef nodeObject) const > +{ > + gchar* markerTextGChar = webkit_web_frame_marker_text_for_list_item(mainFrame, nodeObject); > + if (!markerTextGChar) > + return 0; > + > + JSRetainPtr<JSStringRef> markerText(Adopt, JSStringCreateWithUTF8CString(markerTextGChar)); > + return markerText; > +} There's a storage leak here. You need to g_free markerTextGChar. > #include <JavaScriptCore/JSRetainPtr.h> > #include <JavaScriptCore/JSStringRefBSTR.h> > #include <JavaScriptCore/JavaScriptCore.h> > +#include <JavaScriptCore/JSValueRef.h> > #include <WebCore/COMPtr.h> > #include <WebKit/WebKit.h> > #include <WebKit/WebKitCOMAPI.h> Alphabetical order, case sensitive, like the sort tool. That means JSValueRef.h should be moved up one line. But I really don't get why you need to add an include here at all. JavaScriptCore.h includes JavaScript.h which in turn includes JSValueRef.h.

Thanks! (In reply to comment #18) > (From update of attachment 52553 [details]) > > +JSRetainPtr<JSStringRef> LayoutTestController::markerTextForListItem(JSValueRef nodeObject) const > > +{ > > + gchar* markerTextGChar = webkit_web_frame_marker_text_for_list_item(mainFrame, nodeObject); > > + if (!markerTextGChar) > > + return 0; > > + > > + JSRetainPtr<JSStringRef> markerText(Adopt, JSStringCreateWithUTF8CString(markerTextGChar)); > > + return markerText; > > +} > > There's a storage leak here. You need to g_free markerTextGChar. Will fix. > > #include <JavaScriptCore/JSRetainPtr.h> > > #include <JavaScriptCore/JSStringRefBSTR.h> > > #include <JavaScriptCore/JavaScriptCore.h> > > +#include <JavaScriptCore/JSValueRef.h> > > #include <WebCore/COMPtr.h> > > #include <WebKit/WebKit.h> > > #include <WebKit/WebKitCOMAPI.h> > > Alphabetical order, case sensitive, like the sort tool. That means JSValueRef.h > should be moved up one line. Will fix. > But I really don't get why you need to add an include here at all. > JavaScriptCore.h includes JavaScript.h which in turn includes JSValueRef.h. Yeah, I must say it was a blind guess at the build failure. The win EWS does not seem to provide build logs. :(

Created attachment 52559 [details] patch Let me post the patch once again to let the EWS test it on all platforms. Darin, please don't r+ it yet as the EWS does not process reviewed patches.

Attachment 52559 [details] did not build on gtk: Build output: http://webkit-commit-queue.appspot.com/results/1608243

Created attachment 52561 [details] patch (In reply to comment #21) > Attachment 52559 [details] did not build on gtk: > Build output: http://webkit-commit-queue.appspot.com/results/1608243 Oh, that would explain the Windows failure as well. I wonder how it compiled on Mac.

Attachment 52561 [details] did not build on gtk: Build output: http://webkit-commit-queue.appspot.com/results/1600261

> gchar* webkit_web_frame_marker_text_for_list_item(WebKitWebFrame* frame, JSObjectRef nodeObject); You changed the actual function to take a JSValueRef, but this extra definition still has the old signature. I don't know why this definition has to be here, but this is why the GTK build is failing.

Attachment 52559 [details] did not build on win: Build output: http://webkit-commit-queue.appspot.com/results/1605310

Created attachment 52569 [details] patch (In reply to comment #24) > > gchar* webkit_web_frame_marker_text_for_list_item(WebKitWebFrame* frame, JSObjectRef nodeObject); > > You changed the actual function to take a JSValueRef, but this extra definition > still has the old signature. I don't know why this definition has to be here, > but this is why the GTK build is failing. Yeah, it's not in the public headers. Thanks! I just finished a local build to make sure it builds fine on GTK+. I looked at a diff between the patch that built on win and the last one, and I suspect this is what breaks it: + 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 one should fix it. Thanks for your patience. :) And yay for the EWS!

(In reply to comment #26) > I looked at a diff between the patch that built on win and the last one, and I > suspect this is what breaks it: > > + 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; Ah. The shadowing I mentioned in my review.

OK, looks like it builds on all platforms. Darin, if you don't have further comments, could you r+ this patch so I can land it?

Comment on attachment 52569 [details] patch The downside of waiting for all the EWS compiles is that I forgot the review I did earlier, and had to reread the patch. > + var child = element.firstChild; > + while (child) { > + if (child.nodeType == Node.ELEMENT_NODE) { > + var marker = layoutTestController.markerTextForListItem(child); > + if (marker) > + ret += indent(depth) + ' ' + marker + ' ' + child.innerText.trim() + '<br />'; > + ret += dumpListHelper(child, depth + 1); > + } > + > + child = child.nextSibling; > + } This could be a for loop. Loop could use firstElementChild and nextElementSibling and so avoid the nodeType check. No need for that "/" in "<br />". This is not XHTML; the slash is just ignored. > + return ret; I much prefer words for variable names over fragments of words. > + // Don't show the actual list as it is useless in the text-only mode. > + document.getElementById("list").style.display = "none"; Instead of styling it, you can just remove it from the DOM tree after grabbing a dump of it. r=me

Thanks Darin but I'm afraid the patch will need at least one more iteration. :( I was just going to land it but decided to give it a go with a debug build and it turns out we're actually hitting the assertion we decided to add (it's great that you suggested it, otherwise it would remain unspotted): void RenderListItem::updateListMarkerNumbers() { Node* listNode = enclosingList(this); ASSERT(listNode && listNode->renderer()); This happens because of the difference in when ContainerNode detaches a node from the DOM tree: - when removing all children (ContainerNode::removeChildren), it does that _before_ detaching it from the rendering tree - whereas when removing a single child (ContainerNode::removeChild), it does that _afterwards_. We're being hit by the former - in enclosingList() we can't walk up the DOM tree, because there is nowhere we can go. That looks strange to me, but it looks like it's not only me because even the comments next to the code says: // Remove the node from the tree before calling detach or removedFromDocument (4427024, 4129744). // removeChild() does this after calling detach(). There is no explanation for // this discrepancy between removeChild() and its optimized version removeChildren(). (I wonder what these numbers are). Do you think it should be OK to change the enclosingList() function to walk up the rendering tree only? If so, I'm going to upload one more patch tomorrow with a test case for this situation.

(In reply to comment #30) > Thanks Darin but I'm afraid the patch will need at least one more iteration. :( Sad, but I think our direction is good. > This happens because of the difference in when ContainerNode detaches a node > from the DOM tree: > - when removing all children (ContainerNode::removeChildren), it does that > _before_ detaching it from the rendering tree > - whereas when removing a single child (ContainerNode::removeChild), it does > that _afterwards_. > > We're being hit by the former - in enclosingList() we can't walk up the DOM > tree, because there is nowhere we can go. Irritating that these two are different. > That looks strange to me, but it looks like it's not only me because even the > comments next to the code says: > // Remove the node from the tree before calling detach or removedFromDocument > (4427024, 4129744). > // removeChild() does this after calling detach(). There is no explanation for > // this discrepancy between removeChild() and its optimized version > removeChildren(). Alexey and I wrote this comment recently. Or maybe it was Mitz and me, but we wrote it together. > (I wonder what these numbers are). Those numbers are Apple Radar bug numbers. Bug 4427024 was reported in 2006 and was about this crash: http://www.formassembly.com/form-builder.php? Safari consistently crashes when using this AJAX demo. Follow the instructions.. click on the link "unnamed form" on the left) type in a name for the form as instructed, hit" return" after that - Safari crashes. Bug 4129744 was <http://trac.webkit.org/changeset/14045>. There is a test case included. > Do you think it should be OK to change the enclosingList() function to walk up > the rendering tree only? Maybe, but we'll have to quite a bit more testing to make that change. In fact, I suggest you make that change separately before changing how list item markers are updated.

Comment on attachment 52553 [details] patch Cleared Darin Adler's review+ from obsolete attachment 52553 [details] so that this bug does not appear in http://webkit.org/pending-commit.

(In reply to comment #31) > Alexey and I wrote this comment recently. Or maybe it was Mitz and me, but we > wrote it together. > > > (I wonder what these numbers are). > > Those numbers are Apple Radar bug numbers. > > Bug 4427024 was reported in 2006 and was about this crash: > > http://www.formassembly.com/form-builder.php? > Safari consistently crashes when using this AJAX demo. > Follow the instructions.. click on the link "unnamed form" on the left) > type in a name for the form as instructed, hit" return" after that - Safari > crashes. > > Bug 4129744 was <http://trac.webkit.org/changeset/14045>. There is a test case > included. Thanks for this data. > > Do you think it should be OK to change the enclosingList() function to walk up > > the rendering tree only? > > Maybe, but we'll have to quite a bit more testing to make that change. In fact, > I suggest you make that change separately before changing how list item markers > are updated. That sounds good but I wonder if I need a test case for this? If so, it might be hard to come up with one as this does not really affect the current code. If not, I can definitely do that as a separate change.

(In reply to comment #33) > > > Do you think it should be OK to change the enclosingList() function to walk up > > > the rendering tree only? > > > > Maybe, but we'll have to quite a bit more testing to make that change. In fact, > > I suggest you make that change separately before changing how list item markers > > are updated. > > That sounds good but I wonder if I need a test case for this? If so, it might > be hard to come up with one as this does not really affect the current code. If > not, I can definitely do that as a separate change. You should definitely do the change separately whether or not it changes behavior. If it's just a refactoring that helps with your later change, that's good too. You say it "does really affect the current code". I find that surprising since the DOM tree and render tree don't always have identical hierarchies, but maybe I'm wrong about that. You can make the change and just add a test case that helps demonstrate the change didn't break anything, or even no test case at all if you find specific tests that you think cover it well enough.

Created attachment 52910 [details] 2nd changeset > You say it "does really affect the current code". I find that surprising since > the DOM tree and render tree don't always have identical hierarchies, but maybe > I'm wrong about that. You're right here. This could be a dangerous change to make. I'm not sure if it would work correctly with e.g. the list object living in a different layer than an item. That's only a guess as I haven't tested that. I think we can make a safer and a simpler change that will address the issue. Posting the proposed change here in a separate patch as you suggested. I should have filed another bug for it probably but I'm not sure if it's not better to incorporate it to the first one if it's an one-liner (with no tests and a comment that is not true until the main patch gets in). I'm planning on doing the proper testing tomorrow to see if it's the right to do.

(In reply to comment #35) > > You say it "does really affect the current code". I find that surprising since > > the DOM tree and render tree don't always have identical hierarchies, but maybe > > I'm wrong about that. > > You're right here. This could be a dangerous change to make. I'm not sure if it > would work correctly with e.g. the list object living in a different layer than > an item. That's only a guess as I haven't tested that. I think we can make a > safer and a simpler change that will address the issue. My take on this is that I think it will be safe, and in fact is an improvement in making things logical, but we should think about the likely edge cases and make tests.

Created attachment 52999 [details] Use render tree to find the enclosing list (In reply to comment #36) > My take on this is that I think it will be safe, and in fact is an improvement > in making things logical, but we should think about the likely edge cases and > make tests. OK, sounds good to me. I am posting the patch now but I'm going to see if we can include some tests with this change. The existing test coverage seems to be pretty good but there might be some edge cases that I could have missed and that the existing tests also don't cover. However, it seems that we will need to get the DRT support from the 1st patch first landed if we want to include any plain text tests. We could also make this single change without adding new tests and let them come with the other patch. I'm fine with either of the options.

Darin, could you take a look at this?

Comment on attachment 52999 [details] Use render tree to find the enclosing list This change seems OK. I think we should consider using the renderer itself to represent the list rather than the renderer's node. Thus the return value would have a type of RenderObject* rather than Node*. I also think that the argument should be RenderListItem* rather than const RenderListeItem*. I don't know why we made it const!

(In reply to comment #39) > I think we should consider using the renderer itself to represent the list > rather than the renderer's node. Thus the return value would have a type of > RenderObject* rather than Node*. If you don't mind, I'll be happy to do this in a follow-up patch. > I also think that the argument should be RenderListItem* rather than const > RenderListeItem*. I don't know why we made it const! I know that it is not a common practice in WebKit but in this case we're calling it in const contexts, so yes, it's necessary.

(In reply to comment #40) > (In reply to comment #39) > > I think we should consider using the renderer itself to represent the list > > rather than the renderer's node. Thus the return value would have a type of > > RenderObject* rather than Node*. > > If you don't mind, I'll be happy to do this in a follow-up patch. Yes. I meant to leave that decision in your hands, otherwise I would have used review- and asked for it more forcefully. > > I also think that the argument should be RenderListItem* rather than const > > RenderListeItem*. I don't know why we made it const! > > I know that it is not a common practice in WebKit but in this case we're > calling it in const contexts, so yes, it's necessary. I think that those const contexts are probably unwise -- const member functions where the const provides little or no benefit -- but changing that has little to do with your patch and this was a sort of "side comment" rather than some action I wanted you to take.

Comment on attachment 52999 [details] Use render tree to find the enclosing list Committed in http://trac.webkit.org/changeset/57893.

Created attachment 53896 [details] patch Getting back to the first patch. It does no longer apply against ToT (partially due to a recent Qt DRT refactoring), let me post a slightly rebased version (moved the Qt private API from QWebFramePrivate to the new DumpRenderTreeSupportQt). (In reply to comment #29) > (From update of attachment 52569 [details]) > The downside of waiting for all the EWS compiles is that I forgot the review I > did earlier, and had to reread the patch. > > > + var child = element.firstChild; > > + while (child) { > > + if (child.nodeType == Node.ELEMENT_NODE) { > > + var marker = layoutTestController.markerTextForListItem(child); > > + if (marker) > > + ret += indent(depth) + ' ' + marker + ' ' + child.innerText.trim() + '<br />'; > > + ret += dumpListHelper(child, depth + 1); > > + } > > + > > + child = child.nextSibling; > > + } > > This could be a for loop. Loop could use firstElementChild and > nextElementSibling and so avoid the nodeType check. > > No need for that "/" in "<br />". This is not XHTML; the slash is just ignored. > > > + return ret; > > I much prefer words for variable names over fragments of words. > > > + // Don't show the actual list as it is useless in the text-only mode. > > + document.getElementById("list").style.display = "none"; > > Instead of styling it, you can just remove it from the DOM tree after grabbing > a dump of it. Fixed all of them. I'm afraid the LayoutTestController patch will need to be changed to pass the JS context to the private functions in each port, just like the new computedStyleIncludingVisitedInfo API does. I had no idea that there was an assertion about the context not being 0 in the JSC C API, even though it is not actually used. I'm not a big fan of this but that's what computedStyleIncludingVisitedInfo does. Following this idea seems like the best choice. Darin, these are the only changes I've made compared to the old version, hopefully it doesn't involve much effort from you. Thanks in advance.

Comment on attachment 53896 [details] patch > + RenderObject* child = this->nextInPreOrder(list); No need for "this->" here. > + if (newChild->isListItem()) > + toRenderListItem(newChild)->updateListMarkerNumbers(); After looking at this over and over again, I realized that we should probably just put a virtual updateListMarkerNumbers function into RenderObject. Because the code is just making a virtual function call to get the answer for whether something is a list item, which is just a slower less elegant way of calling virtual function in the first place. > + String markerText = markerTextForListItem(element); > + return g_strdup(markerText.utf8().data()); Seems to me we don't really need the local variable here. > friend class QWebFrame; > + friend class DumpRenderTreeSupportQt; > friend class QWebElementCollection; > friend class QWebHitTestResult; > friend class QWebHitTestResultPrivate; Normally we keep these in alphabetical order. > + Element* element = listItem.m_element; > + return WebCore::markerTextForListItem(element); Seems to me we don't really need the local variable here.

Thanks, will fix all of these except for: > After looking at this over and over again, I realized that we should probably > just put a virtual updateListMarkerNumbers function into RenderObject. Because > the code is just making a virtual function call to get the answer for whether > something is a list item, which is just a slower less elegant way of calling > virtual function in the first place. Because I don't think having a virtual function in RenderObject would make that code more elegant. It doesn't seem to belong there and in fact, it would be somewhat confusing as updateListMarkerNumbers() would always do nothing for renderers other than RenderListItem and that wouldn't be that obvious from just reading the code that calls the function as it is now.

Committed in http://trac.webkit.org/changeset/57986.

http://trac.webkit.org/changeset/57986 might have broken SnowLeopard Intel Release (Tests)

(In reply to comment #47) > http://trac.webkit.org/changeset/57986 might have broken SnowLeopard Intel > Release (Tests) Fixed in http://trac.webkit.org/changeset/57989. For some reason the Skipped list changes disappeared in between the review iterations.