Bug 11031 - Another crazy counters bug
Summary: Another crazy counters bug
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 420+
Hardware: Macintosh OS X 10.4
: P2 Normal
Assignee: Carol Szabo
URL: http://dbaron.org/css2.1/tests/import...
Keywords:
: 23262 30505 (view as bug list)
Depends on: 4980 31723 31814 32884 33600 33625
Blocks:
  Show dependency treegraph
 
Reported: 2006-09-25 14:36 PDT by Beth Dakin
Modified: 2010-01-19 16:09 PST (History)
6 users (show)

See Also:


Attachments
Test case (3.76 KB, text/html)
2006-09-25 14:37 PDT, Beth Dakin
no flags Details
Proposed Patch (49.55 KB, patch)
2009-11-05 15:28 PST, Carol Szabo
no flags Details | Formatted Diff | Diff
Proposed Patch - fixed a few style issues. (50.63 KB, patch)
2009-11-05 18:46 PST, Carol Szabo
no flags Details | Formatted Diff | Diff
Proposed Patch - Fixes error in RenderObject::isEmpty as suggested by Mitz (50.63 KB, patch)
2009-11-06 09:17 PST, Carol Szabo
darin: review-
Details | Formatted Diff | Diff
FYI patch (10.85 KB, patch)
2009-11-17 00:30 PST, Shinichiro Hamaji
no flags Details | Formatted Diff | Diff
Proposed Patch (40.26 KB, patch)
2009-11-18 22:08 PST, Carol Szabo
darin: review-
Details | Formatted Diff | Diff
Proposed Patch (16.03 KB, patch)
2010-01-18 13:34 PST, Carol Szabo
no flags Details | Formatted Diff | Diff
Proposed patch; (16.89 KB, patch)
2010-01-18 16:45 PST, Carol Szabo
no flags Details | Formatted Diff | Diff
New Proposed patch. Fixed style issue that I missed in my original submission. (16.97 KB, patch)
2010-01-18 17:07 PST, Carol Szabo
darin: review+
darin: commit-queue-
Details | Formatted Diff | Diff
Proposed patch; Fixes style and ChangeLog error mentioned by Darin. (16.41 KB, patch)
2010-01-19 08:41 PST, Carol Szabo
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Beth Dakin 2006-09-25 14:36:15 PDT
The attached test case does not render properly. To see the bug, counters need
to be implemented (http://bugzilla.opendarwin.org/show_bug.cgi?id=4980), but I
have not yet committed that patch, so this bug is not yet present in the
nightlies. I am filing it anyway in anticipation.
Comment 1 Beth Dakin 2006-09-25 14:37:27 PDT
Created attachment 10768 [details]
Test case
Comment 2 Beth Dakin 2006-09-25 14:38:01 PDT
http://dbaron.org/css2.1/tests/imported-20050702/t1204-increment-01-c-o.xht might be the same problem?
Comment 4 Carol Szabo 2009-11-03 18:38:47 PST
I have a patch that fixes both this bug and 11030. Suggest marking these as duplicate of each other.
Comment 5 Carol Szabo 2009-11-05 15:28:42 PST
Created attachment 42605 [details]
Proposed Patch

This patch introduces support for counter update during dynamic DOM changes which is required by CSS2.1 it also fixes a few other obscure bugs in the previous CSS2.1 counter support.
Comment 6 Carol Szabo 2009-11-05 18:46:16 PST
Created attachment 42617 [details]
Proposed Patch - fixed a few style issues.

Fixed a few style issues that I detected in my previous patch.
Comment 7 mitz 2009-11-06 07:42:27 PST
Comment on attachment 42617 [details]
Proposed Patch - fixed a few style issues.

> -    virtual bool isEmpty() const { return firstChild() == 0; }
> +    virtual bool isEmpty() const { return firstChild(); }

This doesn’t seem right.
Comment 8 Carol Szabo 2009-11-06 07:46:49 PST
(In reply to comment #7)
> (From update of attachment 42617 [details])
> > -    virtual bool isEmpty() const { return firstChild() == 0; }
> > +    virtual bool isEmpty() const { return firstChild(); }
> 
> This doesn’t seem right.

If the reviewer thinks that this is wrong (which I agree with), I'll change it, but WebKit Style Guidelines require that there are no explicit comparisons to 0.
Comment 9 mitz 2009-11-06 08:27:23 PST
(In reply to comment #8)
> (In reply to comment #7)
> > (From update of attachment 42617 [details] [details])
> > > -    virtual bool isEmpty() const { return firstChild() == 0; }
> > > +    virtual bool isEmpty() const { return firstChild(); }
> > 
> > This doesn’t seem right.
> 
> If the reviewer thinks that this is wrong (which I agree with), I'll change it,
> but WebKit Style Guidelines require that there are no explicit comparisons to
> 0.

The above change reverses the logic.
Comment 10 Carol Szabo 2009-11-06 08:30:30 PST
(In reply to comment #9)
> (In reply to comment #8)
> > (In reply to comment #7)
> > > (From update of attachment 42617 [details] [details] [details])
> > > > -    virtual bool isEmpty() const { return firstChild() == 0; }
> > > > +    virtual bool isEmpty() const { return firstChild(); }
> > > 
> > > This doesn’t seem right.
> > 
> > If the reviewer thinks that this is wrong (which I agree with), I'll change it,
> > but WebKit Style Guidelines require that there are no explicit comparisons to
> > 0.
> 
> The above change reverses the logic.

Ooops. Sorry, my mistake, I'll fix it and submit a new patch.
Comment 11 Carol Szabo 2009-11-06 09:17:38 PST
Created attachment 42655 [details]
Proposed Patch - Fixes error in RenderObject::isEmpty as suggested by Mitz

Fixed error discovered by Mitz in the previous patch.
Comment 12 Darin Adler 2009-11-06 10:17:18 PST
Comment on attachment 42655 [details]
Proposed Patch - Fixes error in RenderObject::isEmpty as suggested by Mitz

This patch is huge! I'm not sure I can review the whole thing. Is there any way to do this work in smaller pieces instead of all at once? It seems to me there are definitely many independent changes here, such as the showTreeAndMark change, which are separable from the rest.

> +        Tests: css2.1/counter-increment-002.html
> +               css2.1/counter-reset-000.html
> +               css2.1/counter-reset-002.html

New counter tests should go into "fast/css/counters". The directory named "css2.1" is for the CSS 2.1 test suite. Not something invented by the WebKit project, but something imported. Your new test should go in there.

Patches should not include svn:mergeinfo. You should remove those with the svn pd command before generating the patch if they have crept in.

Many of these tests say "No newline at end of file". Please put a newline at the end of the file.

Please make the new tests use dumpAsText if possible.

> +void CounterNode::resetRenderer(AtomicStringImpl* identifier)
> +{
> +    if(m_renderer && !m_renderer->documentBeingDestroyed())
> +        if (RenderObjectChildList* children = m_renderer->virtualChildren())
> +            children->invalidateCounters(m_renderer, identifier);
> +}

Coding style mistakes here. There is a missing space after "if" and missing braces. Please read the style guide and/or use the check-webkit-style command to find these issues.

In general it is not good to have recursive algorithms that take stack space proportional to the depth of the render tree. And so many of these functions work that way. We need a test case with an extremely deeply nested render tree to see what effect that has.

> +void CounterNode::resetRenderers(AtomicStringImpl *identifier)

The * here is in the wrong place. Needs to be before the space, not after.

> +    for(CounterNode* c = m_firstChild; c ; c = c->m_nextSibling)

Need a space space here after the "for".

Should not have a space after the "c" before the ";".

We prefer words rather than letters for local variable names. The word "child" would probably be good. I see other older code in this file that is using the letter "c" and "o" -- sorry, that was older style.

> +        //Relayout all counters that may be affected by this change

Comments should have a space after the "//" and a period at the end of the sentence.

> -void CounterNode::insertAfter(CounterNode* newChild, CounterNode* refChild)
> +void CounterNode::insertAfter(CounterNode* newChild,
> +    CounterNode* refChild, AtomicStringImpl *identifier)

There's no need to break this into multiple lines. It goes against our usual style. Also, the "*" is in the wrong place.

> +        RefPtr<AtomicStringImpl> identifierPtr(identifier);
> +        while (m_lastChild != refChild) {
> +            RenderCounter::destroyCounterNode(m_lastChild->renderer(),
> +                identifierPtr);
> +        }

I don't understand the use of RefPtr here. And breaking up the call to destroyCounterNode into two lines seems unhelpful.

> -void CounterNode::removeChild(CounterNode* oldChild)
> +void CounterNode::removeChild(CounterNode* oldChild,
> +    AtomicStringImpl* identifier)

Same comment about multiple lines.

> +        fprintf(stderr, "0x%08X %s: %d %d P:0x08%X PS:0x%08X NS:0x08%X\n",
> +            (int)c, c->isReset() ? "reset" : "increment", c->value(),
> +            c->countInParent(), c->parent(), c->previousSibling(),
> +            c->nextSibling());

Normally we would use static_cast, not a C-style cast.

> -    bool isReset() const { return m_isReset; }
> -    int value() const { return m_value; }
> -    int countInParent() const { return m_countInParent; }
> -    RenderObject* renderer() const { return m_renderer; }
> -
> -    CounterNode* parent() const { return m_parent; }
> -    CounterNode* previousSibling() const { return m_previousSibling; }
> -    CounterNode* nextSibling() const { return m_nextSibling; }
> -    CounterNode* firstChild() const { return m_firstChild; }
> -    CounterNode* lastChild() const { return m_lastChild; }
> -
> -    void insertAfter(CounterNode* newChild, CounterNode* beforeChild);
> -    void removeChild(CounterNode*);
> +    ALWAYS_INLINE bool isReset() const { return m_isReset || !m_parent; }
> +    ALWAYS_INLINE bool isTypeReset() const { return m_isReset; }
> +    ALWAYS_INLINE int value() const { return m_value; }
> +    ALWAYS_INLINE int countInParent() const { return m_countInParent; }
> +    ALWAYS_INLINE RenderObject* renderer() const { return m_renderer; }
> +
> +    ALWAYS_INLINE CounterNode* parent() const { return m_parent; }
> +    ALWAYS_INLINE CounterNode* previousSibling() const { return m_previousSibling; }
> +    ALWAYS_INLINE CounterNode* nextSibling() const { return m_nextSibling; }
> +    ALWAYS_INLINE CounterNode* firstChild() const { return m_firstChild; }
> +    ALWAYS_INLINE CounterNode* lastChild() const { return m_lastChild; }

Our general rule is to use ALWAYS_INLINE only when we see an actual performance effect and have to use it to get that effect. There are tons of simple accessors like this and we do not plan to mark all the others with ALWAYS_INLINE, so please don't start with these.

> +    /* identifier must match the identifier of this counter or
> +     * the renderers affected by this insertion shall not be
> +     * invalidated.
> +     */

We use "//" for comments, and sentences with capital letters and periods.

> +    void insertAfter(CounterNode* newChild, CounterNode* beforeChild,
> +        AtomicStringImpl* identifier);

I think we should consider using const AtomicString& instead of AtomicStringImpl* for all these new functions.

> +/* Finds the insertion point for the counter described by counterOwner, isReset and 
> + * counterName in the CounterNode tree for counterName and sets parent and
> + * previousSibling accordingly.
> + * The function returns true if the counter whose insertion point is searched is NOT
> + * the root of the tree.
> + * The root of the tree is a counter reference that is not in the scope of any other
> + * counter with the same identifier.
> + * All the counter references with the same identifier as this one that are in
> + * children or subsequent siblings of the renderer that owns the root of the tree
> + * form the rest of of the nodes of the tree.
> + * The root of the tree is always a reset type reference.
> + * A subtree rooted at any reset node in the tree is equivalent to all counter 
> + * references that are in the scope of the counter or nested counter defined by that
> + * reset node.
> + * Non-reset CounterNodes cannot have descendants.
> + */

We use // for comments, not /*.

It's nice that this comment is complete, but the long comment is hard to read. Maybe you could say less or paragraph it in some way that makes it easier to digest.

> +static bool findPlaceForCounter(RenderObject* counterOwner,
> +                                const AtomicString& counterName,
> +                                bool isReset, CounterNode*& parent, 
> +                                CounterNode*& previousSibling)

We do not line up declarations like this when they span multiple lines. It would be better not to reformat unless we're trying to move the code in that direction.

> +                            && (currentRenderer->parent() == counterOwner->parent())) {

I find that including parentheses in common cases like this (&& or || expressions combined with == involved in if statements) makes things less clear rather than more. The idiom comes up so often it is not a source of doubt in any real case. I suggest omitting the parentheses.

The tactical comments inside the function were all removed and replaced with a large one at the top. Partly because of that I find the new function harder to follow than the old, even though the total amount of comments is now greater.

> +    for (CounterMaps::iterator it = counterMaps().begin();it != end;
> +        ++it)

This formatting is unnecessarily ugly. PUtting it all in one line would make it easier to read. Also, please include a space after the ";". Also, need braces around something that's more than one line.

> +        if (it->first != object) {
> +            nodeMap = it->second;
> +            if (CounterNode* node = nodeMap->get(counterName.impl())) {
> +                if (!node->parent()
> +                    && findPlaceForCounter(
> +                        const_cast<RenderObject*>(it->first),
> +                        counterName, true, newParent,
> +                        newPreviousSibling)) {

Need to find a way to do this so things aren't broken into so many lines. We don't do it this way in WebKit code.

One way to do this since this just keeps eliminating cases is to use the "early continue" idiom, so the main logic of the loop just continues at the outer level instead of getting more and more deeply nested.

    if (it->first == object)
        continue;
    CounterNode* node = it->second->get(counterName.impl());
    if (!node)
        continue;
    // etc.

> -void RenderCounter::invalidate()
> +void RenderCounter::invalidate(AtomicStringImpl *identifier)
>  {
> -    m_counterNode = 0;
> -    setNeedsLayoutAndPrefWidthsRecalc();
> +    if (!identifier
> +        || (m_counter.identifier() == (const char*)identifier->characters())) {
> +        m_counterNode = 0;
> +        setNeedsLayoutAndPrefWidthsRecalc();
> +    }
>  }

Early return would be easier to read than the nested code here.

It is not correct to cast identifier->characters() to const char *, and even if it was correct, you would need to do it with static_cast.

To compare two AtomicString instances you just use "==", no casting needed.

Patch is too big for me to review the rest at this time.

Looking forward to seeing some future iterations, hopefully in some smaller pieces.

review- for now
Comment 13 Carol Szabo 2009-11-06 12:38:09 PST
(In reply to comment #12)
> > +        Tests: css2.1/counter-increment-002.html
> > +               css2.1/counter-reset-000.html
> > +               css2.1/counter-reset-002.html

These tests are actually copied from the css2.1 test battery and I maintained the naming convention from there.
The only modification to the tests have to do with whitespace and indentation and with making sure that DumpRenderTree waits for the timer to fire before it dumps.
Do you still think that these tests need to be moved to fast/css/counters?

> Please make the new tests use dumpAsText if possible.

Unfortunately dumpAsText does not dumpCounterValues. So I was unable to have the tests work that way. If anybody has an idea how to retrieve Counter values from JS, I would try it that way, as I prefer dumpAsText myself since it is less platform specific.

> Coding style mistakes here. There is a missing space after "if" and missing

I am sorry for the many style mistakes in this patch. I tried to hunt them down to the best of my abilities and fixed what I found including what check-webkit-style reported. Some of these files have many style errors and I did not want to make the patch more confusing than it already is.
I'll do my best to fix the issues.
> > +    /* identifier must match the identifier of this counter or
> > +     * the renderers affected by this insertion shall not be
> > +     * invalidated.
> > +     */
> 
> We use "//" for comments, and sentences with capital letters and periods.

In a previous submission a reviewer (I believe that it was Tor Arne Vestb?) made me change // to /* for function usage comments, I am not sure what is the right way anymore.

> Looking forward to seeing some future iterations, hopefully in some smaller
> pieces.

It is hard to break this up since most changes depend on each other for proper results, also Eric Seidel wants one patch per bug. I will do the following, though:
1. I shall create a new bug and I shall submit the improvements to the debug function as a separate patch for that bug.
2. I shall remove all code changes that are not affecting functionality, and try to resubmit. Hopefully the patch will not look that big, because except for the tests it should not have more than 100 lines or so.

1. I shall submit
Comment 14 Alexey Proskuryakov 2009-11-06 20:13:09 PST
> Do you still think that these tests need to be moved to fast/css/counters?

The idea behind keeping the css2.1/ directory intact is that we could delete everything in it, and import a new version of the test suite one day.

> In a previous submission a reviewer (I believe that it was Tor Arne Vestb?)
> made me change // to /* for function usage comments

Were these headers used in both C++ and plain C files? That's an exception, because some C compilers reject "//".
Comment 15 Carol Szabo 2009-11-09 08:04:39 PST
(In reply to comment #14)

> > In a previous submission a reviewer (I believe that it was Tor Arne Vestb?)
> > made me change // to /* for function usage comments
> 
> Were these headers used in both C++ and plain C files? That's an exception,
> because some C compilers reject "//".
The header contained a class declaration so it would have not compiled in C anyway.
Comment 16 Shinichiro Hamaji 2009-11-16 01:24:13 PST
Hmm Carol, it seems you and I are working for the same issue in different bugs, unfortunately :( Let me introduce my current status. I started commenting on Bug 23262, I fixed all css2.1 test suite bugs locally, splitted my patch into several chunks, and posted two patches. One was already landed (see fast/css/counters/t1204-increment-0[01]-c-o), and another was r+ed but blocked by unrelated issue. The patch r+ed is in Bug 30505. When I'm trying to land the second patch, it conflicted and I found another person is working for the same issue.

If you want to continue your work on this, I'll leave this work to you and help improving your patch. Of course, if you want to delegate this bug to me, I'm happy to continue working.

Three major issues I found:

- It seems addChild always traverse subsequent elements and call updateCounter() for them. I think it will make most website, which don't use counters, slow. In Bug 30505, I needed to update counters only when the new child is a counter and not anonymous.
- fast/css/counters/invalidate-cached-counter-node is failing after this patch?
- Please use layoutTestController.counterValueForElementById(). With this, I think you can tests them with dumpAsText().
Comment 17 Shinichiro Hamaji 2009-11-16 06:00:52 PST
It seems that Carol's patch would still need some more work. For example, Darin suggested me to invalidate subsequent counters instead of creating counter when a render object with counter directives is added, but this patch seems to do the latter way. So, even if we decide to ask Carol to fix this bug, I guess it would make sense to land Bug 30505 first so that reviewers don't need to say the same comments on Carol's patch. What do you think?

By the way, I'd like two more issues/requests in the patch:

> +    if (temp = node->parent())

I cannot compile your patch on my Mac due to this line. This line produces a GCC warning and WebKit is using -Werror on Mac.

I think it would be better to have more smaller tests so that we can easily distinguish the cause of failures in future. Specifically, I think this bug can be divided into 4 smaller issues which are related each other:

1. dynamic addition of increment node
2. dynamic deletion of increment node
3. dynamic addition of reset node
4. dynamic deletion of reset node

Once these four issues are fixed, I think it's very easy to fix style change case. So, I would like to have four tests. I was planning to fix this bug with 4 steps, and Bug 30505 was the first step.
Comment 18 Carol Szabo 2009-11-16 08:31:03 PST
(In reply to comment #17)
> It seems that Carol's patch would still need some more work. For example, Darin
> suggested me to invalidate subsequent counters instead of creating counter when
> a render object with counter directives is added, but this patch seems to do
> the latter way. So, even if we decide to ask Carol to fix this bug, I guess it
> would make sense to land Bug 30505 first so that reviewers don't need to say
> the same comments on Carol's patch. What do you think?
> 
> By the way, I'd like two more issues/requests in the patch:
> 
> > +    if (temp = node->parent())
> 
> I cannot compile your patch on my Mac due to this line. This line produces a
> GCC warning and WebKit is using -Werror on Mac.
> 
> I think it would be better to have more smaller tests so that we can easily
> distinguish the cause of failures in future. Specifically, I think this bug can
> be divided into 4 smaller issues which are related each other:
> 
> 1. dynamic addition of increment node
> 2. dynamic deletion of increment node
> 3. dynamic addition of reset node
> 4. dynamic deletion of reset node
> 
> Once these four issues are fixed, I think it's very easy to fix style change
> case. So, I would like to have four tests. I was planning to fix this bug with
> 4 steps, and Bug 30505 was the first step.

I will probably submit my final version of the patch by the end of tomorrow.
I in the solution that I am proposing, which handles all cases, the issues are broken down differently on two different axis:
A. Cause of change:
1. Changing the DOM tree via adding/removing nodes or subtrees
->This is addressed by changes to RenderObject addChild/removeChild
2. Altering the style of an existing node
->This is addressed by changes to setStyle()

B. The effect of change on some counterNodes of the same hierarchy with the counterNodes added/removed by either cause but different than the nodes added/removed:
1. Change in values only
2. Change in location in the hierarchy.

While the first case is easily addressable without destroying and recreating the affected counters, the second situation is not.

I have briefly looked at Shinichiro Hamaji's patch and I saw that he addresses a very limited number of cases.
I will try to sync my patch with the latest entries. I would like to continue working on this issue as I feel that I found a good and fast solution that covers all cases.
I am glad to defend any decisions that I made and seem worthwhile.
I did not defend my position on recursive traversal of the counter tree not the rendering tree as Darin thought, because I did not find it worthwhile to argue that the counter tree is expected to be shallow ( cannot think of a 9 levels counter hierarchy that would be readable).
I am open for suggestions for optimizations as long as the optimized code still covers all cases.
I do not yet understand the concern about updateCounters.
I am usually available for discussions on #webkit IRC channel on freenonde.
Comment 19 Shinichiro Hamaji 2009-11-17 00:30:08 PST
Created attachment 43347 [details]
FYI patch

FYI, this is the code change I was planning to submit. I'm sorry, but
this patch isn't for TOT but for r50717, which is before Carol's
change r50960 (btw I think this fix was great, thanks for doing
this). I don't want to resolve conflict Carol want to fix this issue
and my patch won't be landed.

> I have briefly looked at Shinichiro Hamaji's patch and I saw that he
> addresses a very limited number of cases.

Yes, my patch submitted in Bug 30505 focused the limited cases because
I thought submitting a big patch would confuse reviewers. Also, I
wanted to create smaller test cases in each steps. That's why I'm
splitting my patch.

> B. The effect of change on some counterNodes of the same hierarchy with the
> counterNodes added/removed by either cause but different than the nodes
> added/removed:
> 1. Change in values only
> 2. Change in location in the hierarchy.
>
> While the first case is easily addressable without destroying and recreating
> the affected counters, the second situation is not.

I'm not sure if the B2 can be an issue. I thought changing location
requires DOM nodes detach/attach and render objects will be
destructed/constructed. Please correct me if my understanding is
wrong. It's very nice if you post an HTML where B2 is an issue.

Anyway, even if B2 is really an issue, I don't think calling
updateCounters() for all add-child is good deal as counter is rarely
used. This would make all website, which insert DOM nodes, slower even
if they don't use counter at all.
Comment 20 Carol Szabo 2009-11-17 08:41:04 PST
> I'm not sure if the B2 can be an issue. I thought changing location
> requires DOM nodes detach/attach and render objects will be
> destructed/constructed. Please correct me if my understanding is
> wrong. It's very nice if you post an HTML where B2 is an issue.
1. I am not talking about counters attached to the node being attached or detached but about the other nodes that may be affected.
2. You do not need to attach a node or detach it to cause restructuring of the tree, you just need to change the style of an existing node.
See this example on how a counter hierarchy can be change without adding or removing nodes from the dom:
http://www.w3.org/Style/CSS/Test/CSS2.1/current/html4/counter-increment-002.htm

Note: the setTimeout part is critical. If you directly call run from onLoad, everything works without any changes not even your landed patch is necessary, because the changes to the dom are done before any counters or renderers are created and that case is covered (with some errors) by the previous code.

> Anyway, even if B2 is really an issue, I don't think calling
> updateCounters() for all add-child is good deal as counter is rarely
> used. This would make all website, which insert DOM nodes, slower even
> if they don't use counter at all.
The real question is how much slower?
If there is only one node inserted all updateCounters does is check the node's style for counter directives and verify that the node does not have children and it returns. To me this isn't much overhead.
If a hierarchy of nodes is inserted at one time (as it is sometimes the case in the examples from w3.org) updateCounters checks all those nodes for counterDirectives and if none is found it does nothing more.
Only if counter directives are found, the algorithm becomes more complex.
If anyone has a better idea please state it I am more than happy to use it as long as it works.
Right now I have a working solution. The only problem is with the test cases, because despite QtLauncher displaying the proper counter values and DumpRenderTree dumping the proper tree, counterValueForElementById sometimes crashes and some other times returns an empty string instead of the proper counter value.
I believe that for the moment I shall submit a patch with the accompanying tests in normal dump mode, and then I shall fix DumpRenderTree in a separate patch.
Comment 21 Shinichiro Hamaji 2009-11-17 22:08:48 PST
> 1. I am not talking about counters attached to the node being attached or
> detached but about the other nodes that may be affected.

Ah, I see.

> 2. You do not need to attach a node or detach it to cause restructuring of the
> tree, you just need to change the style of an existing node.
> See this example on how a counter hierarchy can be change without adding or
> removing nodes from the dom:
> http://www.w3.org/Style/CSS/Test/CSS2.1/current/html4/counter-increment-002.htm

So, I think my "FYI patch" is working. I confirmed my patch is working
for all CSS counter tests.

> Note: the setTimeout part is critical. If you directly call run from onLoad,
> everything works without any changes not even your landed patch is necessary,
> because the changes to the dom are done before any counters or renderers are
> created and that case is covered (with some errors) by the previous code.

Yeah, I know this. I confirmed the test was failing without my patch
when I landed the patch. Note that counterValueForElementById calls
updateLayout so I didn't need setTimeout.

> The real question is how much slower?

I think my "FYI patch" is working without traversal. I guess you can
add

if (!renderer->style()->counterDirectives() || renderer->isAnonymous())
    return;

into the top of updateCounters so that your patch won't make
non-counter-sites slower.
Comment 22 Carol Szabo 2009-11-18 16:03:21 PST
> > The real question is how much slower?
> 
> I think my "FYI patch" is working without traversal. I guess you can
> add

I looked at your patch and I did not see how it could possibly handle a case like this
<el1>
  ...
  <el2 style="counter-reset: c;">
     ...
  </el2>
  ...
</el1>

Now let's say that el1's style is changed to "counter-increment: c;"
This will cause this counter to be a root counter in a totally new counter tree.
Without traversing all children of el1 to verify whether they have counters for c, I do not know how to figure that these counters are now children of the counter on el1.

> 
> if (!renderer->style()->counterDirectives() || renderer->isAnonymous())
>     return;
> 
> into the top of updateCounters so that your patch won't make
> non-counter-sites slower.

This will not work, because I came across a case where a whole tree is attached at once to the document, and the root of the tree has no counters, but one of the children has (I believe the case is <el class="use" /> where use:before is "content-counter: c", so el is inserted in the tree with its child renderers for before. el itself has no counter directives but the before child has and requires update. One can argue that this is done automatically when originalText() is called, but that does not work, because the counter may be created before, when the style was set on the child which appeared attached to the tree, and now it only needs an update. originalText() can not do that.

I finally figured out the counterValueFromElementById function and why it crashed on me at some point, so I can submit now proper tests.
Comment 23 Shinichiro Hamaji 2009-11-18 21:43:52 PST
> I looked at your patch and I did not see how it could possibly handle a case
> like this
> <el1>
>   ...
>   <el2 style="counter-reset: c;">
>      ...
>   </el2>
>   ...
> </el1>

Ah, yes. I forgot about this case. Maybe we could create a global hashmap keyed by counter-identifier and its value is root counter node, but I'm not sure. Thanks for the description.

> This will not work, because I came across a case where a whole tree is attached
> at once to the document, and the root of the tree has no counters, but one of
> the children has (I believe the case is <el class="use" /> where use:before is
> "content-counter: c", so el is inserted in the tree with its child renderers
> for before. el itself has no counter directives but the before child has and
> requires update.

I cannot imagine this case, but you may be right. It would be nice if you add a test case to exercise this situation so that we won't introduce regressions in future.

> I finally figured out the counterValueFromElementById function and why it
> crashed on me at some point, so I can submit now proper tests.

Good news! I'm looking forward your next patch.
Comment 24 Shinichiro Hamaji 2009-11-18 21:45:24 PST
*** Bug 23262 has been marked as a duplicate of this bug. ***
Comment 25 Carol Szabo 2009-11-18 22:08:00 PST
Created attachment 43487 [details]
Proposed Patch

This patch addresses Darin's concerns regarding my previous submission.
The patch was broken up in 3 installments of which this is the last.
-Changed Comment styles
-Changed Code layout and fixed coding style errors (all that I could find).
-Explained in detail the findPlaceForCounter algorithm as well as its design.
The code is somewhat lengthier than the previous implementation, but it handles a lot more complex cases and it is faster as it shortcuts a good portion of the render tree once it found a predecessor to the counter. If anyone can find a meaningful reduction please let me know.

Continuing concerns:
- I do not understand why the Renderer to CounterNodes map uses RefPtr<AtomicStringImpl> as the key, instead of AtomicString. Since Darin wanted me to use AtomicString in most code for counter identifiers, there is a lot of conversion going on to and from these map lookups which need RefPtr<AtomicStringImpl>.

Regarding the alternative solution that Shinchiro Hamaji proposed, after a brief analysis I found that it fails to address a few concerns that my solution addresses:
-  When a new counter reference counter is created which comes in preorder before any other reference to a counter with the same id, it may be that some counter node trees must be merged, and previous nodes that were reset nodes become increment nodes, because they were forced to reset by the virtue of not having a reset node come before them.
- Sometimes a subtree of renderers is attached to the main tree as a whole and the root of the attached tree does not have a counter but the branches have such a counter. These counters may not be correctly updated by Shichiro's patch, as he does not take any action if the root node does not have a counter with it.
- Shinchiro does not address the problems with the findPlaceForCounter algorithm.
Also Shinchiro's algorithm raises some performance issues:
- Shinchiro's algorithm invalidates counters with all ids when the style of a node changes even if some of the counter directives stay the same.
- When a node with a counter is inserted all renders that follow that renderer in the render tree are searched for counters and if the counters are found, they are invalidated. This appears to be much slower than my approach of searching the counters with the same id and find out whether they are affected and doing this only for root counters.
Comment 26 Darin Adler 2009-11-19 09:52:28 PST
(In reply to comment #25)
> - I do not understand why the Renderer to CounterNodes map uses
> RefPtr<AtomicStringImpl> as the key, instead of AtomicString. Since Darin
> wanted me to use AtomicString in most code for counter identifiers, there is a
> lot of conversion going on to and from these map lookups which need
> RefPtr<AtomicStringImpl>.

I think it's simply an issue of whether maps with AtomicString keys work efficiently or not. It's cleaner to work at the AtomicString level if we can prove there is no loss of efficiency. It's even possible that at the time the original code was written we couldn't even compile a HasMap with AtomicString keys.
Comment 27 Darin Adler 2009-11-19 10:24:16 PST
Comment on attachment 43487 [details]
Proposed Patch

Patch looks good. Quite a few stylistic issues.

I don't know that all of this needs to go in one patch. I'd prefer to see one fix at a time even though it would take a bit longer. There may be some pieces that are interdependent, but many seem not to be. To pick just one example, the change to isReset seems separate from the rest. Similarly, adding comments can be done separate from behavior changes. And some of the refactoring can be done in an initial patch before reusing the refactored code in new ways. For example, destroyCounterNodes could be refactored in a separate patch that does not change behavior at all.

> +        while (m_lastChild != refChild) {
> +            RenderCounter::destroyCounterNode(m_lastChild->renderer(), identifier);
> +        }

In WebKit coding style this does not have braces.

> -    bool isReset() const { return m_isReset; }
> +    bool isReset() const { return m_isReset || !m_parent; }
> +    bool isTypeReset() const { return m_isReset; }

I don't think these names are clear enough.

The one you call isReset could be have a name like shouldTriggerReset.

It is not good to have an m_isReset and an isReset function that do not match. At the very least if you think these function names are great and want to keep them you'd have to rename the data member to m_isTypeReset. But also when naming function members remember that we want them to work as a sentence like this:

    "<object> <functionName>"

And "counter is type reset" is not clear. Thus you might end up with a name like hasResetType since "counter has reset type" is not bad.

> +    // identifier must match the identifier of this counter or
> +    // the renderers affected by this removal shall not be invalidated.
>      void removeChild(CounterNode*, const AtomicString& identifier);

This comment seems kind of sideways. I think the comment should say what the function does, rather than what the function does not do. If renderers are not invalidated, why is that correct/OK? I think I know the answer but that's what the comment should be talking about, not just the mechanics of the logic in the function.

We sometimes use "identifier" and other times "counterName". It would be good to make the terminology as consistent as possible.

> +// Finds the insertion point for the counter described by counterOwner, isReset and 
> +// counterName in the CounterNode tree for counterName and sets parent and
> +// previousSibling accordingly.
> +// The function returns true if the counter whose insertion point is searched is NOT
> +// the root of the tree.
> +// The root of the tree is a counter reference that is not in the scope of any other
> +// counter with the same identifier.
> +// All the counter references with the same identifier as this one that are in
> +// children or subsequent siblings of the renderer that owns the root of the tree
> +// form the rest of of the nodes of the tree.
> +// The root of the tree is always a reset type reference.
> +// A subtree rooted at any reset node in the tree is equivalent to all counter 
> +// references that are in the scope of the counter or nested counter defined by that
> +// reset node.
> +// Non-reset CounterNodes cannot have descendants.

Typically we don't put line breaks after sentences in a comment like this.

> -static bool findPlaceForCounter(RenderObject* object, const AtomicString& counterName,
> -    bool isReset, CounterNode*& parent, CounterNode*& previousSibling)
> +static bool findPlaceForCounter(RenderObject* counterOwner,
> +                                const AtomicString& counterName,
> +                                bool isReset, CounterNode*& parent, 
> +                                CounterNode*& previousSibling)

This kind of formatting, where the subsequent lines are lined up with the "(", is typically frowned upon in WebKit. Sadly the editors push you to do it this way. One of the problems with this is that it complicates later efforts to rename. You have to realign the function. The old version used our formatting style.

> +            // We may be at the end of our search

Comments use sentence style, so typically have a period as well as a capital letter.

> +            if (currentCounter) {
> +                // We have a suitable counter on the EndSearchRenderer
> +                if (previousSibling) { //But we already found another counter that we come after

We put spaces after the "//".

> +                    if (currentCounter->isReset()) {
> +                        // We found a reset counter that is on a renderer that is a sibling of ours or a parent
> +                        if (isReset
> +                            && (currentRenderer->parent() == counterOwner->parent())) {

We typically don't use parentheses when && and == are involved in a boolean expression. Since this idiom is so common in if statements the order of precedence is clear by convention if nothing else.

> +                        // We are not a reset node or the previous reset must be on an ancestor of our renderer
> +                        // hence we must be a child of that reset counter

Another of many examples that lack a period.

> +                        parent = currentCounter;
> +                        ASSERT(previousSibling->parent() == currentCounter);
> +                        return true;
> +                    } // currentCounter is not reset

This kind of comment on the ending brace does not seem to make the code clearer. In fact, I find it confusing that it describes the condition on the code above it. These are not giant if statements, so I think the code is clearer without these back-reference comments. Maybe you meant this to be a comment on the code after the brace, in which case it's critical to move it to the next line.

> +                    if (!isReset
> +                        || (currentRenderer->parent() != counterOwner->parent())) {
> +                    // If the node we are placing is not reset or we have found a counter that is attached
> +                    // to an ancestor of the placed counter's renderer we know we are a sibling of that node
> +                        ASSERT(currentCounter->parent() == previousSibling->parent());
> +                        parent = currentCounter->parent();
> +                        return true;
> +                    }

In the other cases like this just above and below you indented the comment to match the body of the if. Should do that here too.

> +                        if (isReset
> +                            && (currentRenderer->parent() == counterOwner->parent())) {

Really seems this expression would read better on one line. And similar ones above and below. The line break makes it harder to read.

> +            } // We come here if the previous sibling or parent of our renderer had no 
> +            // good counter, or we are a reset node and the counter on the previous sibling
> +            // of our renderer was not a reset counter.
> +            // Set a new goal for the end of the search.

The comment not be on the same line with the brace.

> +                // We found a suitable counter ...

We definitely do not use "..." like this. People can see the structure from the C++ code, and trying to mirror that with sentence fragments doesn't seem to make the code clearer.

> +                    if ( currentCounter->isReset()) {
> +                        // but this one is reset.

The above is a perfect example of a comment that says exactly the same thing as the C++ code. It's important to have comments say the things that the C++ code does not say, rather than repeating what it does say. Comments are good for why the code does something but should rarely be used for what the code does. There are other ways to make clear what the code does, including making well-named local variables and helper functions, that are far more effective.

> +    for (CounterMaps::iterator it = counterMaps().begin();it != end;
> +        ++it)

Need a space after the semicolon. This should be on one line.

> +        if (it->first != object) {

We often find that early continue makes these things better, rather than nesting the entire loop.

> +            nodeMap = it->second;
> +            if (CounterNode* node = nodeMap->get(counterName.impl())) {

Same here.

> +                if (!node->parent()
> +                    && findPlaceForCounter(
> +                        const_cast<RenderObject*>(it->first),
> +                        counterName, true, newParent,
> +                        newPreviousSibling)) {

And here too. It's especially poor to write a function call vertically like this. Makes it hard to read. It would be better to have a named variable for it->first casted to the right type and put this on one line.

The worst argument here is the "true". That's why we no longer used booleans for this type of thing. Instead we would have an enum with two named values.

> +                    newParent->insertAfter(node,
> +                        newPreviousSibling, counterName.impl());

This should be on one line, not two. Do we still need the impl() call here?

> -    CounterMap* map = maps.get(object);
> +    CounterMap* map = maps.get(renderer);
>      if (!map)
>          return;
> -    maps.remove(object);
> -
>      CounterMap::const_iterator end = map->end();
>      for (CounterMap::const_iterator it = map->begin(); it != end; ++it) {
> -        CounterNode* node = it->second;
>          AtomicString identifier(it->first.get());
> -        destroyCounterNodeChildren(identifier, node);
> -        if (CounterNode* parent = node->parent())
> -            parent->removeChild(node, identifier);
> -        delete node;
> +        destroyCounterNodeWithoutMapRemoval(identifier, it->second);
>      }

Braces go now that the body has one line.

> +    maps.remove(renderer);

Now that the get and remove function calls are in the same function, it's not good to do double hash table lookup. Instead you should use a find call and check against end to do the "get" part, and call the version of remove that takes an iterator so we can reuse the single hash table lookup.

> +    CounterMaps& maps = counterMaps();
> +    CounterMap* map = maps.get(renderer);

Seems unnecessary to put counterMaps() into a local variable in a function that uses it only one.

> +    if (!map)
> +        return;
> +    CounterNode* node = map->get(identifier.impl());
> +    if (node) {
> +        destroyCounterNodeWithoutMapRemoval(identifier, node);
> +        map->remove(RefPtr<AtomicStringImpl>(identifier.impl()));

I do not thing that typecast to RefPtr<AtomicStringImpl> is need. If it is, I am quite surprised! 

> +// Do not delete map even if empty as the expectation is that soon nodes will be added
> +// to the map, or otherwise destroyCounterNodes would have been called instead.
> +    }

This comment is at the wrong nesting level. Also, I think "expectation" is not right here. This comment needs to treat this as guarantee the caller makes, not an expectation, using words like "must". It would be even better if later we can modify the code to ensure this always happens.

> +void RenderCounter::createCounterIfNeeded(RenderObject* renderer,
> +        const AtomicString& identifier)
> +{
> +    makeCounterNode(renderer, identifier, false);
> +}

The line before the opening brace is indented wrong, should be only one level. But also, This should just all go on one line.

> +void RenderCounter::updateCounters(RenderObject* renderer)
> +{
> +    updateCounter(renderer);
> +    for (RenderObject* child = renderer->nextInPreOrder(renderer); child; child = child->nextInPreOrder(renderer))
> +        updateCounter(child);
> +}

The variable child is actually any descendant, so child is not the optimal name. And this can be written like this:

    for (RenderObject* descendant = renderer; descendant; descendant = descendant->nextInPreOrder(renderer))
        updateCounter(descendant);

No separate function call outside the loop needed.

> +    const CounterDirectiveMap* pCounterDirectiveMap = object->style()->counterDirectives();

We don't use "pXXX" names like this in WebKit code. I also think that you can just call this directiveMap since the context of the function means "counter" can often be omitted. It's always a readability/judgement call.

> +        if ((newParent == node->parent()) && (newPreviousSibling == node->previousSibling()))
> +            continue;
> +        if (node->parent())
> +            node->parent()->removeChild(node, it->first.get());

Since node->parent() is always used, and used three times, you could consider a local variable for it.

I suggest omitting the parentheses in the "==" and "&&" expression. We normally do and I find it slightly harder to read the expression with the additional punctuation.

> +    static void destroyCounterNodes(RenderObject* renderer);
> +    static void destroyCounterNode(RenderObject* renderer, const AtomicString& identifier);
> +    static void updateCounters(RenderObject* renderer);
> +    static void updateCounter(RenderObject* renderer);
> +    static void createCounterIfNeeded(RenderObject* renderer, const AtomicString& identifier);

The argument name "renderer" adds nothing for a type that is RenderObject*, so I suggest omitting it. If there was some way to make clearer the role of the RenderObject you could include an argument name that did it, but I don't think there is.

> +    RenderCounter::updateCounters(newChild);

Is this extra work that is bad for performance?

> -    updateFillImages(oldStyle ? oldStyle->backgroundLayers() : 0, m_style ? m_style->backgroundLayers() : 0);
> -    updateFillImages(oldStyle ? oldStyle->maskLayers() : 0, m_style ? m_style->maskLayers() : 0);
> -
> -    updateImage(oldStyle ? oldStyle->borderImage().image() : 0, m_style ? m_style->borderImage().image() : 0);
> -    updateImage(oldStyle ? oldStyle->maskBoxImage().image() : 0, m_style ? m_style->maskBoxImage().image() : 0);
> +    if (oldStyle) {
> +        if (m_style) {
> +            if (const CounterDirectiveMap* pCounterDirectiveMap = m_style->counterDirectives()) {
> +                if (const CounterDirectiveMap* pOldCounterDirectiveMap = oldStyle->counterDirectives()) {
> +                    CounterDirectiveMap::const_iterator end = pCounterDirectiveMap->end();
> +                    for (CounterDirectiveMap::const_iterator it = pCounterDirectiveMap->begin(); it != end; ++it) {
> +                        if (pOldCounterDirectiveMap->contains(it->first)) {
> +                            if (pOldCounterDirectiveMap->get(it->first) != it->second)
> +                                RenderCounter::destroyCounterNode(this, AtomicString(it->first.get()));
> +                        } else {
> +                            RenderCounter::destroyCounterNode(this, AtomicString(it->first.get()));
> +                            RenderCounter::createCounterIfNeeded(this, AtomicString(it->first.get()));
> +                        }
> +                    }
> +                    end = pOldCounterDirectiveMap->end();
> +                    for (CounterDirectiveMap::const_iterator it = pOldCounterDirectiveMap->begin(); it != end; ++it)
> +                        if (!pCounterDirectiveMap->contains(it->first))
> +                            RenderCounter::destroyCounterNode(this, AtomicString(it->first.get()));
> +                } else {
> +                    RenderCounter::destroyCounterNodes(this);
> +                    RenderCounter::updateCounters(this);
> +                }
> +            } else if (m_hasCounterNodeMap)
> +                RenderCounter::destroyCounterNodes(this);
>  
> -    // We need to ensure that view->maximalOutlineSize() is valid for any repaints that happen
> -    // during styleDidChange (it's used by clippedOverflowRectForRepaint()).
> -    if (m_style->outlineWidth() > 0 && m_style->outlineSize() > maximalOutlineSize(PaintPhaseOutline))
> -        toRenderView(document()->renderer())->setMaximalOutlineSize(m_style->outlineSize());
> +            updateFillImages(oldStyle->backgroundLayers(),
> +                m_style->backgroundLayers());
> +            updateFillImages(oldStyle->maskLayers(), m_style->maskLayers());
> +
> +            updateImage(oldStyle->borderImage().image(),
> +                m_style->borderImage().image());
> +            updateImage(oldStyle->maskBoxImage().image(),
> +                m_style->maskBoxImage().image());
> +            // We need to ensure that view->maximalOutlineSize() is valid for 
> +            // any repaints that happen during styleDidChange (it's used by
> +            // clippedOverflowRectForRepaint()).
> +            if (m_style->outlineWidth() > 0 && m_style->outlineSize() >
> +                maximalOutlineSize(PaintPhaseOutline)) {
> +                toRenderView(document()->renderer())->setMaximalOutlineSize(
> +                    m_style->outlineSize());
> +            }
> +        } else {
> +            if (m_hasCounterNodeMap)
> +                RenderCounter::destroyCounterNodes(this);
> +            updateFillImages(oldStyle->backgroundLayers(), 0);
> +            updateFillImages(oldStyle->maskLayers(), 0);
> +
> +            updateImage(oldStyle->borderImage().image(), 0);
> +            updateImage(oldStyle->maskBoxImage().image(), 0);
> +        }
> +    } else if (m_style) {
> +        RenderCounter::updateCounter(this);
> +        updateFillImages(0, m_style->backgroundLayers());
> +        updateFillImages(0, m_style->maskLayers());
> +
> +        updateImage(0, m_style->borderImage().image());
> +        updateImage(0, m_style->maskBoxImage().image());
> +        // We need to ensure that view->maximalOutlineSize() is valid for any repaints that happen
> +        // during styleDidChange (it's used by clippedOverflowRectForRepaint()).
> +        if (m_style->outlineWidth() > 0 && m_style->outlineSize() > maximalOutlineSize(PaintPhaseOutline))
> +            toRenderView(document()->renderer())->setMaximalOutlineSize(m_style->outlineSize());
> +    }

This new code is long and hard to read and understand. What's the benefit of putting all the cases in different branches like this? Is there a way we can factor this so it's not so gigantic? Replacing 4 lines of code with 50 needs a really good justification. There's also a lot of code broken into two lines prematurely. We'd prefer to have a moderately long line rather than breaking everything so it fits in an 80-column character.

> -    virtual bool isEmpty() const { return firstChild() == 0; }
> +    virtual bool isEmpty() const { return !firstChild(); }

> -    SelectionState selectionState() const { return static_cast<SelectionState>(m_selectionState);; }
> +    SelectionState selectionState() const { return static_cast<SelectionState>(m_selectionState); }

These changes, unrelated to the rest of the patch, should go in a separate patch.

Given the amount of change, I'm surprised at the small number of new test cases.

review- because I want at least some of the style issues fixed. Please consider all my comments.
Comment 28 Carol Szabo 2009-11-20 10:23:22 PST
(In reply to comment #27)
> (From update of attachment 43487 [details])
> Patch looks good. Quite a few stylistic issues.
> 
> I don't know that all of this needs to go in one patch. I'd prefer to see one
> fix at a time even though it would take a bit longer.

> In WebKit coding style this does not have braces.
> 
> > -    bool isReset() const { return m_isReset; }
> > +    bool isReset() const { return m_isReset || !m_parent; }
> > +    bool isTypeReset() const { return m_isReset; }
> 
> I don't think these names are clear enough.

> > +    // identifier must match the identifier of this counter or
> > +    // the renderers affected by this removal shall not be invalidated.
> >      void removeChild(CounterNode*, const AtomicString& identifier);
> 
> This comment seems kind of sideways.

> We sometimes use "identifier" and other times "counterName". It would be good
> to make the terminology as consistent as possible.
> 

Eric Seidel and the commit bot wants one landed patch per bug hence I created bug 31723 (https://bugs.webkit.org/show_bug.cgi?id=31723) which highlights the problems in the findPlaceForCounter algorithm and I created a small fix just around that.
I hate pedantic fixes that require bug filings and going through a whole review process just to add comments to code and change variable names which add no benefit to the user, and are beneficial to a developer only in the context of looking at a real user issue, so I put the comments and related fixes in this patch together with this algorithm fix hopefully the reviewer (likely Darin) will not mind that.


> > +// Finds the insertion point for the counter described by counterOwner, isReset and 
> > +// counterName in the CounterNode tree for counterName and sets parent and
> > +// previousSibling accordingly.
> > +// The function returns true if the counter whose insertion point is searched is NOT
> > +// the root of the tree.
> > +// The root of the tree is a counter reference that is not in the scope of any other
> > +// counter with the same identifier.
> 
> Typically we don't put line breaks after sentences in a comment like this.

I found myself struggling to understand the design of CounterNode trees so for the benefit of whoever looks at this code after me I took the opportunity to clarify a few things here that are critical for the implementation of this function beside the boilerplate description of what the function does and what the return values are. Since I had a lot of explaining to do, I used line breaks to separate main ideas, try to make the comment more readable while keeping it pretty condensed. I am sorry if I failed, I tried a new (hopefully better) version in the patch to 31723 (see above).


> >      CounterMap::const_iterator end = map->end();
> >      for (CounterMap::const_iterator it = map->begin(); it != end; ++it) {
> > -        CounterNode* node = it->second;
> >          AtomicString identifier(it->first.get());
> > -        destroyCounterNodeChildren(identifier, node);
> > -        if (CounterNode* parent = node->parent())
> > -            parent->removeChild(node, identifier);
> > -        delete node;
> > +        destroyCounterNodeWithoutMapRemoval(identifier, it->second);
> >      }
> 
> Braces go now that the body has one line.

The body is actually 2 lines: AtomicString identifier(it->first.get()); stays.


> > +void RenderCounter::updateCounters(RenderObject* renderer)
> > +{
> > +    updateCounter(renderer);
> > +    for (RenderObject* child = renderer->nextInPreOrder(renderer); child; child = child->nextInPreOrder(renderer))
> > +        updateCounter(child);
> > +}
> 
> The variable child is actually any descendant, so child is not the optimal
> name. And this can be written like this:
> 
>     for (RenderObject* descendant = renderer; descendant; descendant =
> descendant->nextInPreOrder(renderer))
>         updateCounter(descendant);
> 
> No separate function call outside the loop needed.

I have refactored the code per your comment. You are right about child/descendant, as far as including the initial updateCounter in the loop, I was trying to save an unnecessary comparison, since this function is called for every DOM node insertion I was trying to make it as quick as possible if the node being inserted and its descendants have no counter directives. (See the next item bellow about updateCounters being called unnecessarily).

> > +    RenderCounter::updateCounters(newChild);
> 
> Is this extra work that is bad for performance?

As I explained in my response to Shinchiro Hamaji, this work is usually not that much and is critical for being able to respond to DOM node changes.
In the current implementation updateCounters, for most DOM nodes, boils down to: 2 function calls with one pointer arg, plus checking the style of the node for counter directives and the node for the existence of children. I believe this is the bare minimum needed to detect changes to the counter hierarchy that result from addition of DOM nodes.
The reason why Shinchiro's "check before the call" solution (which only saves the time to call 2 non virtual functions - pretty much one CPU cycle on processors with long enough instruction pipelines) does not work is that sometimes a whole Renderer subtree is inserted at once in the main tree and sometimes the root node of this renderer tree does not have any counter directive such as in this case:
<span style=":before reset-counter c 4;"/>
The Renderer for span and for its virtual before child are inserted together in the main tree, but the renderer for span has no counter directives.
I found this case in one of the css2.1 tests.


> > -    updateFillImages(oldStyle ? oldStyle->backgroundLayers() : 0, m_style ? m_style->backgroundLayers() : 0);
> > -    updateFillImages(oldStyle ? oldStyle->maskLayers() : 0, m_style ? m_style->maskLayers() : 0);
> > -
> > -    updateImage(oldStyle ? oldStyle->borderImage().image() : 0, m_style ? m_style->borderImage().image() : 0);
> > -    updateImage(oldStyle ? oldStyle->maskBoxImage().image() : 0, m_style ? m_style->maskBoxImage().image() : 0);
> > +    if (oldStyle) {
> > +        if (m_style) {
> > +            if (const CounterDirectiveMap* pCounterDirectiveMap = m_style->counterDirectives()) {
> > +                if (const CounterDirectiveMap* pOldCounterDirectiveMap = oldStyle->counterDirectives()) {
> > +                    CounterDirectiveMap::const_iterator end = pCounterDirectiveMap->end();
> > +                    for (CounterDirectiveMap::const_iterator it = pCounterDirectiveMap->begin(); it != end; ++it) {
> > +                        if (pOldCounterDirectiveMap->contains(it->first)) {
> > +                            if (pOldCounterDirectiveMap->get(it->first) != it->second)
> > +                                RenderCounter::destroyCounterNode(this, AtomicString(it->first.get()));
> > +                        } else {
> > +                            RenderCounter::destroyCounterNode(this, AtomicString(it->first.get()));
> > +                            RenderCounter::createCounterIfNeeded(this, AtomicString(it->first.get()));
> > +                        }
> > +                    }
> > +                    end = pOldCounterDirectiveMap->end();
> > +                    for (CounterDirectiveMap::const_iterator it = pOldCounterDirectiveMap->begin(); it != end; ++it)
> > +                        if (!pCounterDirectiveMap->contains(it->first))
> > +                            RenderCounter::destroyCounterNode(this, AtomicString(it->first.get()));
> > +                } else {
> > +                    RenderCounter::destroyCounterNodes(this);
> > +                    RenderCounter::updateCounters(this);
> > +                }
> > +            } else if (m_hasCounterNodeMap)
> > +                RenderCounter::destroyCounterNodes(this);
> >  
> > -    // We need to ensure that view->maximalOutlineSize() is valid for any repaints that happen
> > -    // during styleDidChange (it's used by clippedOverflowRectForRepaint()).
> > -    if (m_style->outlineWidth() > 0 && m_style->outlineSize() > maximalOutlineSize(PaintPhaseOutline))
> > -        toRenderView(document()->renderer())->setMaximalOutlineSize(m_style->outlineSize());
> > +            updateFillImages(oldStyle->backgroundLayers(),
> > +                m_style->backgroundLayers());
> > +            updateFillImages(oldStyle->maskLayers(), m_style->maskLayers());
> > +
> > +            updateImage(oldStyle->borderImage().image(),
> > +                m_style->borderImage().image());
> > +            updateImage(oldStyle->maskBoxImage().image(),
> > +                m_style->maskBoxImage().image());
> > +            // We need to ensure that view->maximalOutlineSize() is valid for 
> > +            // any repaints that happen during styleDidChange (it's used by
> > +            // clippedOverflowRectForRepaint()).
> > +            if (m_style->outlineWidth() > 0 && m_style->outlineSize() >
> > +                maximalOutlineSize(PaintPhaseOutline)) {
> > +                toRenderView(document()->renderer())->setMaximalOutlineSize(
> > +                    m_style->outlineSize());
> > +            }
> > +        } else {
> > +            if (m_hasCounterNodeMap)
> > +                RenderCounter::destroyCounterNodes(this);
> > +            updateFillImages(oldStyle->backgroundLayers(), 0);
> > +            updateFillImages(oldStyle->maskLayers(), 0);
> > +
> > +            updateImage(oldStyle->borderImage().image(), 0);
> > +            updateImage(oldStyle->maskBoxImage().image(), 0);
> > +        }
> > +    } else if (m_style) {
> > +        RenderCounter::updateCounter(this);
> > +        updateFillImages(0, m_style->backgroundLayers());
> > +        updateFillImages(0, m_style->maskLayers());
> > +
> > +        updateImage(0, m_style->borderImage().image());
> > +        updateImage(0, m_style->maskBoxImage().image());
> > +        // We need to ensure that view->maximalOutlineSize() is valid for any repaints that happen
> > +        // during styleDidChange (it's used by clippedOverflowRectForRepaint()).
> > +        if (m_style->outlineWidth() > 0 && m_style->outlineSize() > maximalOutlineSize(PaintPhaseOutline))
> > +            toRenderView(document()->renderer())->setMaximalOutlineSize(m_style->outlineSize());
> > +    }
> 
> This new code is long and hard to read and understand. What's the benefit of
> putting all the cases in different branches like this? Is there a way we can
> factor this so it's not so gigantic? Replacing 4 lines of code with 50 needs a
> really good justification.

The code above appears to replace 4 lines, but in reality it adds totally new functionality while optimizing those 4 lines to run faster.
The design goal behind the code above which I admit has some readability issues (mainly due to broken lines, which I fixed) is to make the code as fast as possible since it is run for every style change.
I read an article in a respected Software Development journal where a guy published a breadth first graph travesal algorithm optimized for the Cell processor. The algorithm had 5000 lines versus the usual about 50. But was running an order of magnitude faster on the same hardware as the vanilla algorithm.
My goal in the design of the code above was to minimize unnecessary work.
In the original code the 4 or so functions were called whether or not it made sense (i.e. whether or not there was a non-null oldStyle or newStyle).
I know from testing that sometimes oldStyle can be null and probably newStyle may be null too.
So I separated  the code in these 4 cases and I minimized work in each of them.
For counters the problem is complicated by the fact that for each style there may or may not be counter directives associated with the style, and the counters may or may not be the same for each directive.
Of course there is an easy way out: delete all old counters if any in all cases and create the new ones if any, but this is way less than optimal as creating a counter involves inspecting many renderers.
I took your comment to heart though and I shall try to create some helper functions to increase readability and I shall definitely stop breaking those lines. I personally hate breaking the lines but I read somewhere in the style guidelines that long lines are bad and I was trying to comply with that.

Darin,
Please review my patch for 31723 so that I can come back and submit a smaller better patch for this.
Thanks.
Comment 29 Darin Adler 2009-11-20 12:40:13 PST
Sounds like you're heading in the right direction. I do have a few thoughts.

(In reply to comment #28)
> I hate pedantic fixes that require bug filings and going through a whole review
> process just to add comments to code and change variable names which add no
> benefit to the user, and are beneficial to a developer only in the context of
> looking at a real user issue, so I put the comments and related fixes in this
> patch together with this algorithm fix hopefully the reviewer (likely Darin)
> will not mind that.

It's extremely helpful to have bug fixes that have only the bug fix. Separate refactoring patches help achieve that and make the process of fixing bugs much safer and more deliberate.

I'm sorry you hate those patches.

> Since I had a lot of explaining to do, I used line
> breaks to separate main ideas, try to make the comment more readable while
> keeping it pretty condensed.

I found the formatting of the comment distracting. Starting the new sentences on new lines didn't make it easier for me to understand it.

> as far as including the initial updateCounter in the loop, I
> was trying to save an unnecessary comparison, since this function is called for
> every DOM node insertion I was trying to make it as quick as possible if the
> node being inserted and its descendants have no counter directives.

If the extra branch at the start of loop is a concern, other possible idioms are a do/while loop or an infinite loop with an explicit break.

> As I explained in my response to Shinchiro Hamaji, this work is usually not
> that much

In a hot function like this, to turn the guess of "usually not that much" into something we can make decisions based on, we'd typically do measurement to see what effect the code change has on performance. Trying with something we think is likely to be the worst case of additional overhead.

> The code above appears to replace 4 lines, but in reality it adds totally new
> functionality while optimizing those 4 lines to run faster.

If you're saying this new structure should be judged as a performance optimization, then it should come by itself in a separate patch, with measurement of the speedup.

> I read an article in a respected Software Development journal where a guy
> published a breadth first graph travesal algorithm optimized for the Cell
> processor. The algorithm had 5000 lines versus the usual about 50. But was
> running an order of magnitude faster on the same hardware as the vanilla
> algorithm.

If you're going to cite this article as evidence that your approach is good, then you'll need to measure actual speedup. The guy in that article did.

I did notice the way your patch cut down on work in various cases by reusing the results of if statements. Consider that readability of the code is critical although minimizing the number of lines is not. If we have to make things significantly less readable, then we need a *measurable* speedup to counterbalance that cost.

> I read somewhere in the style
> guidelines that long lines are bad and I was trying to comply with that.

We should fix that guideline; it's not really our WebKit style. Could you cite the specific text? I'd like to correct it.
Comment 30 Shinichiro Hamaji 2009-12-09 18:32:05 PST
*** Bug 30505 has been marked as a duplicate of this bug. ***
Comment 31 Carol Szabo 2010-01-18 13:34:00 PST
Created attachment 46841 [details]
Proposed Patch

Still testing this patch, but I am almost done.
Comment 32 Carol Szabo 2010-01-18 16:45:03 PST
Created attachment 46863 [details]
Proposed patch;

This the final patch to be submitted in the long series that lead to fixing (see blocker bug list) this bug and a dozen similar ones reported in various repositories.
Comment 33 Darin Adler 2010-01-18 16:52:49 PST
Are all those explicit AtomicString conversions needed? I’d expect a conversion from AtomicStringImpl* to AtomicString to work without an explicit conversion.
Comment 34 Carol Szabo 2010-01-18 17:07:17 PST
Created attachment 46866 [details]
New Proposed patch. Fixed style issue that I missed in my original submission.

Removed explicit conversions from AtomicStringImpl* to AtomicString as they are not needed at least not for g++.
Comment 35 Carol Szabo 2010-01-18 17:10:45 PST
(In reply to comment #33)
> Are all those explicit AtomicString conversions needed? I’d expect a conversion
> from AtomicStringImpl* to AtomicString to work without an explicit conversion.

The conversions are not needed, but I had a prior problem with converting from RefPtr<AtomicStringImpl*> and once I solved that I left the AtomicString in place, I thought that it does not hurt. If anything it makes the code more portable.
Thanks for the quick review.
Comment 36 Darin Adler 2010-01-18 17:16:01 PST
Comment on attachment 46866 [details]
New Proposed patch. Fixed style issue that I missed in my original submission.

> -void RenderObject::styleDidChange(StyleDifference diff, const RenderStyle*)
> +void RenderObject::styleDidChange(StyleDifference diff, const RenderStyle*oldStyle)

Missing space here.

> Index: LayoutTests/ChangeLog
> ===================================================================
> --- LayoutTests/ChangeLog	(revision 53399)
> +++ LayoutTests/ChangeLog	(working copy)
> @@ -1,3 +1,32 @@
> +2010-01-18  Carol Szabo  <carol.szabo@nokia.com>
> +
> +        Reviewed by NOBODY (OOPS!).
> +
> +        Another crazy counters bug
> +        https://bugs.webkit.org/show_bug.cgi?id=11031
> +
> +        * fast/css/counters/counter-increment-002-expected.txt: Added.
> +        * fast/css/counters/counter-increment-002.html: Added.
> +        * fast/css/counters/counter-reset-000-expected.txt: Added.
> +        * fast/css/counters/counter-reset-000.html: Added.
> +        * fast/css/counters/counter-reset-002-expected.txt: Added.
> +        * fast/css/counters/counter-reset-002.html: Added.
> +
> +2010-01-18  Carol Szabo  <carol.szabo@nokia.com>
> +
> +        Reviewed by NOBODY (OOPS!).
> +
> +        Another crazy counters bug
> +        https://bugs.webkit.org/show_bug.cgi?id=11031
> +        Added tests for dynamic DOM changes affecting counters.
> +
> +        * fast/css/counters/counter-increment-002.html: Added.
> +        * fast/css/counters/counter-reset-000.html: Added.
> +        * fast/css/counters/counter-reset-002.html: Added.
> +        * fast/css/counters/counter-increment-002-expected.txt: Added.
> +        * fast/css/counters/counter-reset-000-expected.txt: Added.
> +        * fast/css/counters/counter-reset-002-expected.txt: Added.
> +

Double change log here.

You should post another patch without the double change log.
Comment 37 Carol Szabo 2010-01-19 08:41:43 PST
Created attachment 46916 [details]
Proposed patch; Fixes style and ChangeLog error mentioned by Darin.
Comment 38 WebKit Commit Bot 2010-01-19 16:09:26 PST
Comment on attachment 46916 [details]
Proposed patch; Fixes style and ChangeLog error mentioned by Darin.

Clearing flags on attachment: 46916

Committed r53506: <http://trac.webkit.org/changeset/53506>
Comment 39 WebKit Commit Bot 2010-01-19 16:09:37 PST
All reviewed patches have been landed.  Closing bug.