Bug 5776 – REGRESSION: YAHOO: Generated numbers of ordered lists (OL) are not calculated right

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Soryu Waldfee]

Viewing the given URL you will see all generated numbers for li elements are 1.
reduced exaple:
<ol>
	<font size=-1> 
	<li><a name=1></a><b>How does Google Book Search work?</b><br>
	</li>
	</font> <font size=-1> 
	<li><a name=2></a><b>What types of books are available?</b><br>
	</font>
	</li>
</ol>

Removing the font tags will make it work.
Also there seems to be a testsuite for this problem: http://websvn.kde.org/*checkout*/trunk/tests/
khtmltests/rendering/lists/olstart.html?rev=409208

[Maks Orlovich]

Hi... That testfile linked to in the original report is mine (to reporter: I 
am SadEagle on IRC). This stuff mostly works in the KDE tree, because Allen 
implemented CSS counters (#8 fails, will have to bug him), but I actually had 
a patch beforehand which supposedly fixes everything. It's at  
http://www.cs.cornell.edu/~maksim/patches/calc_num_fancy.diff 
It has been quite a while since I wrote it, and it was before I seriously got 
involved in khtml, so it probably needs some serious review/testing, but I 
hope it'll save you some time.  
 

[Joost de Valk (AlthA)]

Created attachment 4773 [details]
Testcase

Testcase further reduced from code in report.

[Joost de Valk (AlthA)]

Confirmed, works in moz.

[Eric Seidel (no email)]

Nice test case.  Should be a simple fix.

[Andrew Wellington]

Created attachment 5566 [details]
Incomplete patch

This is a patch that fixes the attached test case. This does not yet fix all
the cases from the KDE testcase
(http://websvn.kde.org/*checkout*/trunk/tests/khtmltests/rendering/lists/olstart.html?rev=409208)
or rendering of the Google Books URL as we still need to go up from the current
node to find the top of the list if the current node is nested.

[Andrew Wellington]

Created attachment 5796 [details]
Proposed patch

This patch fixes this issue as demonstrated by the Google Books URL and KDE
test file. The test case included in this patch is the KDE test file.

[Darin Adler]

Comment on attachment 5796 [details]
Proposed patch

This looks really good! A few comments:

To compare if two nodes are same, code should use "==". The isSameNode function is for DOM bindings, not internal use. For most people working on the code, the isSameNode calls will be harder to read.

On this line:

+        } else if (n->firstChild() && (!dontDescend || !n->isSameNode(dontDescend))) {

can just do n != dontDescend, since we're guaranteed n is not 0.

I think it would be best to change getPrevListNode so that it's iterative rather than recursive when following parentNode pointers -- should be a straightforward change.

Some minor style things:

    1) we don't usually put else after return
    2) the while loops in getPrevListNode and prevListNode look well suited to be for loops instead
    3) the "found" variable should be declared right where it's used; there's no need to declare it outside the loop

This:

-        if (listNode && listNode->hasTagName(olTag) && !m_render->previousSibling()) {
-            HTMLOListElementImpl *ol = static_cast<HTMLOListElementImpl *>(listNode);
-            render->setValue(ol->start());
+        if (listNode && listNode->hasTagName(olTag)) {
+            NodeImpl *prevNode = prevListNode();

should just be:

+        if (listNode && listNode->hasTagName(olTag) && prevListNode()) {

No reason to break it into multiple lines and add a local variable.

Also, should that be prevListNode() or listNode->prevListNode()?

In render_list.cpp, these spaces in the parentheses don't match our coding style:

+    while ( o ) {
+        if ( o->isListItem() && o->style()->listStyleType() != LNONE )

In this line of code:

+        NodeImpl *n = ((HTMLLIElementImpl *)node())->prevListNode();

what do we do to be sure that node is an HTMLLIElement? The reason I ask is that these assumptions about the DOM tree by the render tree have caused crashing bugs in the past. Often there are CSS ways to get a particular type of renderer with an unexpectedly different type of DOM node, which is one reason renderers can't alway assume the type of DOM element. But in this case there may be no issue -- it's hard to see locally in the calcListValue function.

We try to use static_cast syntax rather than C-style casts when possible.

[Joost de Valk (AlthA)]

*** Bug 6863 has been marked as a duplicate of this bug. ***

[Joost de Valk (AlthA)]

Amongst other sites, this is affecting Yahoo, needs fixing badly.

[Joost de Valk (AlthA)]

This is also a Regression. Adding keywords, changing subject.

[Andrew Wellington]

Created attachment 6023 [details]
Proposed patch 2

Updated patch to address comments from Darin:
- Remove use of isSameNode
- Clean up use of return to be more clear in if statements
- Use of for loops instead of while in appropriate locations
- Move declaration of found local variable in getPrevListNode
- Remove unneeded local variable in attach -- prevListNode() is correct, we want to know if the new node is the first node in the list here
- Remove extraneous function in render_list.cpp from earlier attempt at patch without use of DOM tree
- Use static_cast not a C-style case
- Check that DOM node is an HTML LI node in render_list.cpp

[Darin Adler]

Comment on attachment 6023 [details]
Proposed patch 2

Looking great. I love this patch!

There are still some slight improvements that could be made. In fact, I thought of one major one.

1) I believe that the entire prevListNode function can be simplified, all recursion removed, the two levels of loop removed, and all this folded back into prevListNode by using the traversePreviousNode() function. Something like this:

    static NodeImpl* parentList(NodeList* node)
    {
        for (NodeImpl* n = node; n; n = n->parentNode()) {
            if (n->hasTagName(ulTag) || n->hasTagName(olTag))
                return n;
        return 0;
    }

    HTMLLIElementImpl* HTMLLIElementImpl::previousListItem()
    {
        NodeImpl* list = parentList(this);
        if (!list)
            return 0;
        for (NodeImpl* n = this; n != list; n = n->traversePreviousNode())
            if (n->hasTagName(liTag)) {
                NodeImpl* otherList = parentList(n);
                if (list == otherList)
                    // This item is part of our current list, so it's what we're looking for.
                    return static_cast<HTMLLIElementImpl *>(n);
                // We found ourself inside another list; lets skip the rest of it.
                if (otherList)
                    n = otherList;
            }
        return 0;
    }

The parentList function could also be changed to be a member of HTMLLIElementImpl instead of a local helper -- should work either way -- and we might want to give it a different name since "parent" doesn't really express the relationship. It's "the" list for a list item.

The logic is a little less nice than I'd like it, because it would be nicer to not descend into nested list subtrees at all. But to do that we'd have to visit parents before children, and to do that we'd use traversePreviousNodePostOrder. But if we did that traversePreviousNodePostOrder would return an outer <li> node *before* an <li> element inside it, which is out of document order. I think that's a real case we need to handle, so I recommend just using traversePreviousNode and using a different technique to avoid nodes in other lists; should still be efficient enough. If I'm wrong about that <li> element nesting issue, we could improve this further. We should make sure the test cases include something like that (they probably do).

I have other comments about the existing patch's code's loop structure, but I'll omit them since if you take my suggestion those loops will be gone.

2) I suggest renaming prevListNode to either previousListItem, previousItemInList, previousLIElement, previousListItemElement, or something like that.

3) If you follow my suggestion (1) above, then HTMLLIElementImpl::attach can also use the parentList function. Then, since HTMLLIElementImpl::attach already has the list pointer, you could factor out the "find previous <li> in a particular list" part of the code I wrote above into a separate function and call that from HTMLLIElementImpl::attach to avoid finding the parentList twice.

4) We've been putting the * next to the type, as in "NodeImpl*", in code recently. Although I believe the coding style guide has not yet been updated, I'd really like this patch to be that way, if it's not too much trouble.

5) Here, there's no need for isHTMLElement:

+        if (node()->isHTMLElement() && node()->hasTagName(liTag))

That's because liTag includes both the tag name and the HTML namespace, so this includes the check that this is an HTML node. Some older code in our tree seems to not now this.

6) There's extra parentheses here:

+            n = (static_cast<HTMLLIElementImpl *>(node()))->prevListNode();

One nice thing about static_cast syntax is that it provides parentheses so you don't need that extra set.

7) We *might* need a null-check of node(). Not sure; there can sometimes be render objects without corresponding DOM nodes, but this probably can't happen for list items. We can probably land the patch without determining this.

8) Given my comments in item (3), we need some test cases where one <li> is nested inside another (both for the same list). If those cases really don't list, we can improve on (1) as described under (3).

9) We might want to consider changing responsibilities so the "start value" code is not shared between both the render and DOM tree code. For example, the DOM tree could always set the value, which could be named "listStartValue" and we could only look at the value in the case where there's no previous list item. Or we could explicitly fetch the value from the DOM tree inside RenderListItem::calcListValue, since we already have to locate the list element as a part of finding the previous list items. If you do the latter, then the previousListItem function can be entirely local to render_list.cpp and need not be added to the DOM tree code publicly at all.

10) This code seems to compute marker values even for the three list style types that are symbols and not integers: DISC, CIRCLE, and SQUARE, although it does have a special case for LNONE. That seems like unnecessary work. I think we need test cases that mix list style types. Is it really true that a list item with no marker resets the count to 0, but a list item with a disc gets an invisible number? That's what the current code seems to do.

Thanks for tackling this!

[David Kilzer (:ddkilzer)]

(In reply to comment #12)
> The parentList function could also be changed to be a member of
> HTMLLIElementImpl instead of a local helper -- should work either way -- and we
> might want to give it a different name since "parent" doesn't really express
> the relationship. It's "the" list for a list item.

How about container or listContainer?

[Andrew Wellington]

Created attachment 6206 [details]
Proposed patch 3

- Use traversePreviousNode to traverse tree in a nicer way
- Move DOM node looking code to the render tree
- Remove calculation of start nodes from html_listimpl.cpp. Only explicitly set values are set from here now.
- Rename functions: previousListItemElement and enclosingList
- Did not change attach() to use a function to find the enclosing list as that function was moved to render_list.cpp
- List items with styles that won't display a number still get assigned an invisible number (remove LNONE check that came from original code). This matches every other browser I tried including IE and Firefox.

[Darin Adler]

Comment on attachment 6206 [details]
Proposed patch 3

This is looking really good. Almost ready to land.

I see one bug, so I'll have to mark this review-.

The bug is here:

+            NodeImpl* list = enclosingList(node());
+            if (list)
+                m_marker->m_value = static_cast<HTMLOListElementImpl*>(list)->start();

This casts the list to HTMLOListElementImpl* without checking if it's an <ol> element or a <ul> element. Need to add a hasTagName(olTag).

--------

I also think we need some more test cases.

    1) Test with list items that use list styles that don't display the number. You said, "List items with styles that won't display a number still get assigned an invisible number." And you tested this in other browsers. Great! But we don't have a test that demonstrates this and regression-tests it.

    2) Test with list items that are in the list but not displayed (using style="display: none") to test whether they are skipped when assigning numbers, get assigned invisible numbers, or have some other behavior. Such items will not have renderers. I believe the proposed code will start over at 1 if there's a list item that is not displayed, which may not be right. And depending on the behavior we may have to find out some way to store values for list items without renderers.

    3) Test with list items that use other "display" modes. There is "none", which is test (2) above, but there are also modes like "display: block" that make a list item no longer look like a list item. Specifically, "display: list-item" will make anything behave like a list item, even if it's not an <li> element and any display mode other than "display: list-item" can make an <li> element behave as if it's not a list item. Do the numbers on these types of items work properly?

Some of these test cases will probably uncover further problems that might be beyond the scope of this patch. For example the assumption that If so, we can land the test cases with the current results even if incorrect, and write further bug reports about the outstanding problems.

To fix problems uncovered by (3) we might have to change previousListItemElement to work based on the render tree instead of the DOM tree. If so, then we might have to write the RenderObject version of the NodeImpl::traversePreviousNode function, and use isListItem() rather than hasTagName(liTag) to identify list items.

But depending on the results of (2) we might have to go in a conflicting direction, because "display: none" elements don't get render objects. If they have to participate in the numbering then we'll have a conundrum on our hands. If we're lucky, the changing to use the render tree instead of the DOM tree will give us correct results for both (2) and (3)!

What's important to me is having the test cases -- eventually it would be nice to handle all the cases well too but that's less urgent.

--------

Here are five much-less-important optional improvements. Let me reiterate, these are all optional:

A)

+    NodeImpl* n;
+    for (n = node; n; n = n->parentNode()) {

Declare NodeImpl* inside the for loop here.

B)

+            // We found ourself inside another list; lets skip the rest of  it.

Remove one of the two spaces between "of" and "it".

C)

+        NodeImpl *n = 0;

Put the * next to the NodeImpl intead of next to the n.

D)

+        RenderObject *o = 0;

...

+        if (n) {
+            o = n->renderer();

Declare o only inside the if statement right where it's initialized rather than declaring it earlier and initializing it to 0.

E)

Since we need to know the list in the case where previousListItemElement return 0, perhaps we could change that function so that it takes the list as a parameter. Then we could restructure the calling code to get the list and pass it in, saving us from finding the list twice in the case where there's no previous list item.

[Andrew Wellington]

Created attachment 6214 [details]
Proposed patch 4

- Check that list that start value is fetched from is an <ol> list
- New test case ol-display-types.html that covers messing with the list using CSS
- Modified behaviours to check against isListElement() instead of tag names. This is workable now that this code is in the render tree.
- Now match Firefox's display (seems to match common sense) for items with display: list-item or <li> tags with a different display type. IE's behaviour doesn't seem to make any sense, and it's unlikely that there's significant reliance on IE's seemingly broken method of numbering when messing with display types in CSS.
- previousListItemElement() now takes an optional parent list if the calling function knows it. calcListValue() uses this.
- change logic in setStyle() to have a marker in all cases except error images. Previous code didn't have one when display: none, this could potentially cause crashes.
- did all of the cleanups because they're a good idea :)

[Darin Adler]

Comment on attachment 6214 [details]
Proposed patch 4

Great! r=me

I noticed a RenderObject * that should be RenderObject*, and I don't think making the list parameter to previousListItemElement is good, since it means you search for the list twice if there is none. But both of those are so minor they are no obstacle to landing this.

Very nice tests.

The fix as landed seems to have broken several layout tests:

css2.1/t0505-c16-descendant-00-e
css2.1/t0803-c5501-mrgn-t-00-b-a
css2.1/t0803-c5502-mrgn-r-01-c-a
... several others in css2.1 and
fast/css/007
fast/css/acid2-pixel
fast/css/acid2

I also noticed that the ChangeLog entry mentions a change to html_listimpl.cpp that wasn't committed.

[Andrew Wellington]

Created attachment 6244 [details]
Followup patch

This patch when applied to what's currently in SVN + the missing html_listimpl.cpp fixes the problem mitzpettel mentioned. Moved the value storage to the RenderListItem, some Items shouldn't have markers, but should still have values.

[Alexey Proskuryakov]

Reopening because of comment 18 (html_listimpl.cpp is now committed, but the followup patch is not).

[Darin Adler]

Comment on attachment 6244 [details]
Followup patch

This followup patch needs review.

[Darin Adler]

Comment on attachment 6214 [details]
Proposed patch 4

Cleared review flag from this since it's landed.

[Darin Adler]

Comment on attachment 6244 [details]
Followup patch

r=me

I'll test and land this one as "penance" for not testing the last one enough.