Bug 43783 – Make CSS Style Selector non-recursive

• Component: CSS
• Status: RESOLVED WONTFIX

[Hayato Ito]

Please see the master bug for details.
https://bugs.webkit.org/show_bug.cgi?id=42806

We have to make CSSStyleSelector's code non-recursive one in order to avoid stack overflow when a long CSS selector is used.

[Hayato Ito]

Created attachment 64003 [details]
make-it-iterative

[Hayato Ito]

I'd like to paste my comment from master bug:

---
I've made CSSStyleSelector::SelectorChecker::checkSelector() iterative to avoid stack overflow.
To achieve it, I have to maintain CallStack manually.

Hi reviewers,

I am afraid the code became unintuitive. But I guess it is inevitable. If you have any ideas to make it clean and intuitive, please let me know.

I also have a concern about performance. Is there any standard way to make sure a performance degradation won't happen by this change?

[WebKit Review Bot]

Attachment 64003 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/css/CSSStyleSelector.cpp:1999:  Non-label code inside switch statements should be indented.  [whitespace/indent] [4]
WebCore/css/CSSStyleSelector.cpp:2092:  Non-label code inside switch statements should be indented.  [whitespace/indent] [4]
Total errors found: 2 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Hayato Ito]

The style issues are expected ones. Maybe it should be filed as false positives.

(In reply to comment #3)
> Attachment 64003 [details] did not pass style-queue:
> 
> Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
> WebCore/css/CSSStyleSelector.cpp:1999:  Non-label code inside switch statements should be indented.  [whitespace/indent] [4]
> WebCore/css/CSSStyleSelector.cpp:2092:  Non-label code inside switch statements should be indented.  [whitespace/indent] [4]
> Total errors found: 2 in 3 files
> 
> 
> If any of these errors are false positives, please file a bug against check-webkit-style.

[Shinichiro Hamaji]

(In reply to comment #4)
> The style issues are expected ones. Maybe it should be filed as false positives.

I think it's a good chance to change the style of this code. It seems majority WebKit code is putting '{' just after ':' for case

% grep 'case.*: {' */*.cpp | wc
    340    1365   21891
% grep -B 1 '^ \+{' */*.cpp | grep case | wc
    113     343    6935

Also, our style guideline says "Other braces: place the open brace on the line preceding the code block; place the close brace on its own line.".

[Hayato Ito]

Thank you for the comment.
I'll change the style of this code as you suggested.

I'll also fix styles in other parts of the same file to avoid inconsistency.
I am not sure it is encouraged to include style fixes which are not related to this change. But I'll do it.
If it should be avoided to include style fixes in other parts of same file, please let me know it.


(In reply to comment #5)
> (In reply to comment #4)
> > The style issues are expected ones. Maybe it should be filed as false positives.
> 
> I think it's a good chance to change the style of this code. It seems majority WebKit code is putting '{' just after ':' for case
> 
> % grep 'case.*: {' */*.cpp | wc
>     340    1365   21891
> % grep -B 1 '^ \+{' */*.cpp | grep case | wc
>     113     343    6935
> 
> Also, our style guideline says "Other braces: place the open brace on the line preceding the code block; place the close brace on its own line.".

[Hayato Ito]

Created attachment 64069 [details]
make-it-iterative

[Hayato Ito]

I've fixed the style issues in the previous patch, putting '{' just after ':' for case.

I've not fixed style issues in other parts of the same file because there are a lot of style issues. It might be better to fix the these styles in another patch.

(In reply to comment #7)
> Created an attachment (id=64069) [details]
> make-it-iterative

[Darin Adler]

Comment on attachment 64069 [details]
make-it-iterative

This looks like a good idea. We need to measure if it makes things faster or slower. Also, can we construct a test case demonstrating that the old algorithm runs out of stack space if nested too deeply, or is that not practical?

> +class CSSStyleSelector::SelectorChecker::CallState {

If this is going to have public data members, lets have it be a struct and not use the "m_" prefix. Or make the data members private.

> +    State m_state;
> +    CSSSelector* m_sel;

Lets spell it out: selector, not sel.

> +    Element* m_e;

Lets spell it out: element, not e.

> +    CallState(State state, CSSSelector* sel, Element* e, bool isSubSelector, bool encounteredLink, RenderStyle* elementStyle, RenderStyle* elementParentStyle)
> +            : m_state(state)

Not sure why this is indented 8 spaces.

> +    void push(CallState state)
> +    {
> +        m_stack.append(state);
> +    }

Cuts down on copying if this takes a const CallState&.

> +private:
> +    Vector<CallState> m_stack;

It may improve performance to use Vector<CallState, 20> here or some other number that's usually larger than the typical depth of the stack.

Is there a way to make this patch have a smaller diff, by doing enough of this to change the indentation level separately? All those lines of code marked different that are not different make the patch too hard to read.

Normally, we do not use "const bool".

I'm going to say review- for this patch, but it looks like a step in the right direction.

[Hayato Ito]

Created attachment 66201 [details]
test-included

[Hayato Ito]

Thank you for the review!

(In reply to comment #9)
> (From update of attachment 64069 [details])
> This looks like a good idea. We need to measure if it makes things faster or slower. Also, can we construct a test case demonstrating that the old algorithm runs out of stack space if nested too deeply, or is that not practical?

I am glad to hear that this is a step in the right direction.

I've tried i-Bench and run the performance tests against with-this-patch and without-this-patch.
But my impression about this benchmark is that the score of the performance test is unstable. So it looks difficult to me to judge this patch is good for the performance. Hmm. My understanding and/or usage of i-Bench might be wrong.

I'll attach the result of performance tests for reference.

As for a test case, I've added a testcase in this patch. That test contains deeply nested HTML and long CSS selector. That should not happen in practical, I guess. If we increate a nest level in the test case, WebKit without this patch will crash.
The bad thing about this test case is that it takes too much time, over 1 minute (!), until the test runs out of stack space. So I am afraid that it is inappropriate to add this test to LayoutTest directory as is.


> 
> > +class CSSStyleSelector::SelectorChecker::CallState {
> 
> If this is going to have public data members, lets have it be a struct and not use the "m_" prefix. Or make the data members private.

Thank you. I've changed it to a struct and removed 'm_' prefix from the member variables.
Note that I've appended an underscore, '_', to each formal parameter of the constructor to avoid naming conflicts with member variables. I am nor sure that that there is any established naming convention for formal parameters of such a constructor.


> 
> > +    State m_state;
> > +    CSSSelector* m_sel;
> 
> Lets spell it out: selector, not sel.

Done.

> 
> > +    Element* m_e;
> 
> Lets spell it out: element, not e.


Done.

> 
> > +    CallState(State state, CSSSelector* sel, Element* e, bool isSubSelector, bool encounteredLink, RenderStyle* elementStyle, RenderStyle* elementParentStyle)
> > +            : m_state(state)
> 
> Not sure why this is indented 8 spaces.

Done. Thank you!

> 
> > +    void push(CallState state)
> > +    {
> > +        m_stack.append(state);
> > +    }
> 
> Cuts down on copying if this takes a const CallState&.

Done.

> 
> > +private:
> > +    Vector<CallState> m_stack;
> 
> It may improve performance to use Vector<CallState, 20> here or some other number that's usually larger than the typical depth of the stack.

Done. I think so.

> 
> Is there a way to make this patch have a smaller diff, by doing enough of this to change the indentation level separately? All those lines of code marked different that are not different make the patch too hard to read.

I agree that this patch is hard to read. I am sorry for that. Though I am not sure that I understand your suggestion correctly, I don't have any good ideas to make this patch have a smaller diff. You mean that it might be okay to change indent level of lines, breaking code styles temporarily, for easy reviewing?
I'd like to make this patch easy to read as possible as I can. Any comments are welcome.


> 
> Normally, we do not use "const bool".

Done.

> 
> I'm going to say review- for this patch, but it looks like a step in the right direction.

[Hayato Ito]

Created attachment 66202 [details]
Result of i-Bench performance test for reference

[Darin Adler]

Comment on attachment 66201 [details]
test-included

View in context: https://bugs.webkit.org/attachment.cgi?id=66201&action=review

> WebCore/css/CSSStyleSelector.cpp:1922
> +    CallState(State state_, CSSSelector* selector_, Element* element_, bool isSubSelector_, bool encounteredLink_, RenderStyle* elementStyle_, RenderStyle* elementParentStyle_)
> +        : state(state_)
> +        , selector(selector_)
> +        , element(element_)
> +        , isSubSelector(isSubSelector_)
> +        , encounteredLink(encounteredLink_)
> +        , elementStyle(elementStyle_)
> +        , elementParentStyle(elementParentStyle_)
> +    {
> +    }

There is no reason for all those trailing underscores. The C++ language works fine with initializer arguments named the same as the data members, so there’s no reason to have this strangeness.

> WebCore/css/CSSStyleSelector.cpp:1953
> +    // Therefore we have to maintain a call stack by ourselves so that we can check selector iteratively.

This should say "check selectors iteratively", with an "s".

> WebCore/css/CSSStyleSelector.cpp:2064
> +            default:
> +                return false;

It’s unfortunate we have a default case, because including it turns off gcc’s warning that is given when we forget to handle an enum value.

> WebCore/css/CSSStyleSelector.cpp:2070
> +            while (true) {
> +                if (callStack.isEmpty())
> +                    return false;

A more traditional way to write this is:

    while (!callStack.isEmpty()) {
        // loop body
    }
    return false;

That seems better than using an infinite loop.

> WebCore/css/CSSStyleSelector.cpp:2107
> +                default:
> +                    ASSERT_NOT_REACHED();

It’s unfortunate we have a default case, because including it turns off gcc’s warning that is given when we forget to handle an enum value.

> WebCore/css/CSSStyleSelector.h:234
> +            struct CallState;
> +            class CallStack;

I’m not sure these two need to be CSSStyleSelector members. I think it would be better if they were private to the implementation file and not mentioned in the header at all. We could give them slightly more specific names and do that. I guess either way is OK.

[Eric Seidel (no email)]

Hayato is not a committer.  This will need an updated patch unless darin is comfortable cq+ing this as is.

[Hayato Ito]

Hi Eric,
thank you for your attention.

I became a WebKit committer recently. I am preparing an updated patch and will send that for the review soon after I confirm all tests passes.

(In reply to comment #14)
> Hayato is not a committer.  This will need an updated patch unless darin is comfortable cq+ing this as is.

[Hayato Ito]

Manually committed r70040: https://trac.webkit.org/changeset/70040

[Hayato Ito]

I manually committed after merging HEAD and addressing Darin's comments.
Thank you for reviewing and r+!

(In reply to comment #16)
> Manually committed r70040: https://trac.webkit.org/changeset/70040

[Darin Adler]

So now we should reopen this?

[Hayato Ito]

Yes. I've reopened this.

https://trac.webkit.org/changeset/70040 was reverted in http://trac.webkit.org/changeset/70209.

r70040 caused a performance regression.
See http://code.google.com/p/chromium/issues/detail?id=59985 for more info.

We need a better implementation which does not cause a performance regression.


(In reply to comment #18)
> So now we should reopen this?

[Eric Seidel (no email)]

Attachment 66201 [details] was posted by a committer and has review+, assigning to Hayato Ito for commit.

[Eric Seidel (no email)]

Comment on attachment 66201 [details]
test-included

Marking r- since this was reverted.