[Webkit-unassigned] [Bug 41129] CSSSelector: Avoid chaining tagHistory of CSSSelector, which causes stack overflow.

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=41129


Darin Adler <darin at apple.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #59764|review?                     |review-
               Flag|                            |




--- Comment #18 from Darin Adler <darin at apple.com>  2010-07-14 09:55:18 PST ---
(From update of attachment 59764)
I think this patch takes the right basic approach.

> +    Deque<CSSSelector*> selectorsToBeDeleted;

1) Since the order of deletion does not matter, I would use a single local variable for the next selector to delete and only use the general purpose data structure in the unusual case where we have both m_tagHistory and m_simpleSelector.

2) We can keep the Deque a lot smaller by doing the null checking at append time instead of when the selector is taken out of the Deque.

1) Because the length of the chain is usually short, I think our WTF::Deque is not the right data structure. Our Deque implementation is not particularly efficient when the vector is short, as it almost always should be in these cases. Instead, I would use a Vector with a fixed capacity on the stack. This would use more memory in the case where there is a long chain, but would be considerably faster in the normal case, avoiding allocation altogether.

If you did all of these, then I think we'd end up with code like this, but consierably more efficient. One of the best ways to do this would be to make your own class:

    class SelectorDeque {
    public:
        bool isEmpty() const;
        PassOwnPtr<CSSSelector> takeFirst();
        void append(PassOwnPtr<CSSSelector>);
    };

We could then leave the code as is, except you could remove the null check on the result of takeFirst.

Please give it a try; I think this is the way to go!

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