Bug 209773 – Hit test with clipPath referencing parent element causes infinite recursion

• Component: SVG
• Status: RESOLVED FIXED

[Doug Kelly]

This is a continuation of bug #208279; when referencing an element via a use tag, you can still land in a situation where the result is infinite recursion due to the hit test.

<rdar://problem/60002347>

[Doug Kelly]

Created attachment 394968 [details]
Patch

[Said Abou-Hallawa]

Comment on attachment 394968 [details]
Patch

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

> Source/WebCore/svg/SVGDocumentExtensions.cpp:52
> +    ASSERT(m_visitedElements.isEmpty());

This is a weird and very late assertion. Visiting nodes for hit testing should happen only during that operation.

> Source/WebCore/svg/SVGDocumentExtensions.cpp:379
> +void SVGDocumentExtensions::startVisiting(const RenderElement& element)
> +{
> +    // We should never be visiting an element more than once.
> +    ASSERT(!m_visitedElements.contains(&element));
> +    m_visitedElements.add(&element);
> +}
> +
> +void SVGDocumentExtensions::stopVisiting(const RenderElement& element)
> +{
> +    ASSERT(m_visitedElements.contains(&element));
> +    m_visitedElements.remove(&element);
> +}
> +
> +bool SVGDocumentExtensions::isVisiting(const RenderElement& element)
> +{
> +    return m_visitedElements.contains(&element);
> +}

I do not think tracking the visited renderers in the SVGDocumentExtensions is a good design. I would suggest moving this m_visitedElements to RenderSVGRoot. At the beginning and at the end of RenderSVGRoot::nodeAtPoint(), this m_visitedElements should be empty.

To visit a renderer you can write the following code:

    auto* root = SVGRenderSupport::findTreeRootObject(element);
    root->startVisiting(element);

And RenderSVGRoot::nodeAtPoint() can look like this:

RenderSVGRoot::nodeAtPoint()
{
    {
        CurrentVisitedElementsMaintainer maintainer(*this);
        for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
            ...
        }
    }
    ASSERT(m_visitedElements.isEmpty());

    ...
}

> LayoutTests/svg/hittest/svg-clip-path-child-element-with-use.html:20
> +    <use href="#group"/>

Please add another test case where the cycle goes to the root.
    <use href="#svg"/>

[Doug Kelly]

Created attachment 395225 [details]
Patch

[Said Abou-Hallawa]

Comment on attachment 395225 [details]
Patch

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

> Source/WebCore/ChangeLog:3
> +        Hit test with clipPath referencing parent element causes infinite recursion (when referenced by use element)

I think the cyclic referencing can happen without the use element. So maybe you need to change the title to something like: SVG cyclic referencing causes hit-testing a clipPath to recurse infinitely.

> Source/WebCore/ChangeLog:12
> +        visiting the same element twice, and thus breaking any cycles which might occur in the SVG document.  By
> +        storing the data at the top of the SVG document, this keeps a finite scope for the set of renderers, and

The visited elements are stored now in the RenderSVGRoot.

> Source/WebCore/ChangeLog:19
> +
> +

One extra line.

> Source/WebCore/rendering/svg/RenderSVGRoot.cpp:405
> +    ASSERT(m_visitedElements.isEmpty());

Since you made m_visitedElements accessible from the methods of this class expect in this place, can't we add a new function and name isVisitingAny() or something similar and replace this assertion by 

ASSERT(!isVisitingAny());

> Source/WebCore/rendering/svg/RenderSVGRoot.cpp:458
> +    // We should never be visiting an element more than once.

This comment adds no value. The assertion below says the same thing.

> Source/WebCore/rendering/svg/RenderSVGRoot.cpp:460
> +    ASSERT(!m_visitedElements.contains(&element));
> +    m_visitedElements.add(&element);

Another way to write this and save one HashSet traversal is:

auto result = m_visitedElements.add(&element);
ASSERT_UNUSED(result, result.isNewEntry);

> Source/WebCore/rendering/svg/RenderSVGRoot.cpp:466
> +    ASSERT(m_visitedElements.contains(&element));
> +    m_visitedElements.remove(&element);

Another way to write this is:

bool result = m_visitedElements.remove(&element);
ASSERT_UNUSED(result, result);

> Source/WebCore/rendering/svg/SVGRenderSupport.h:105
> +    WeakPtr<RenderElement> m_element;

I am puzzled by this WeakPtr. m_visitedElements is supposed to keep renderers while they are alive in the calling stack. So there is no possibility at any point that any of them will be freed before it is removed from m_visitedElements. So I think we do not need m_element and it is fine to have m_visitedElements be HashSet of raw pointers.

[Doug Kelly]

Comment on attachment 395225 [details]
Patch

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

>> Source/WebCore/ChangeLog:3
>> +        Hit test with clipPath referencing parent element causes infinite recursion (when referenced by use element)
> 
> I think the cyclic referencing can happen without the use element. So maybe you need to change the title to something like: SVG cyclic referencing causes hit-testing a clipPath to recurse infinitely.

Fair, I was distinguishing this from the past change. :)

>> Source/WebCore/ChangeLog:12
>> +        storing the data at the top of the SVG document, this keeps a finite scope for the set of renderers, and
> 
> The visited elements are stored now in the RenderSVGRoot.

Good catch.

>> Source/WebCore/rendering/svg/RenderSVGRoot.cpp:405
>> +    ASSERT(m_visitedElements.isEmpty());
> 
> Since you made m_visitedElements accessible from the methods of this class expect in this place, can't we add a new function and name isVisitingAny() or something similar and replace this assertion by 
> 
> ASSERT(!isVisitingAny());

I'm not sure I understand your point here -- it's not that I made m_visitedElements accessible from the methods of the class; it *is* a member of the class.  In any case, this check isn't performed anywhere else besides this function... I don't think an additional function for this test makes much sense.

>> Source/WebCore/rendering/svg/SVGRenderSupport.h:105
>> +    WeakPtr<RenderElement> m_element;
> 
> I am puzzled by this WeakPtr. m_visitedElements is supposed to keep renderers while they are alive in the calling stack. So there is no possibility at any point that any of them will be freed before it is removed from m_visitedElements. So I think we do not need m_element and it is fine to have m_visitedElements be HashSet of raw pointers.

This may not need to be a WeakPtr, but the purpose of this class is to manage scope of visited elements -- when this object is destroyed, it will correctly remove the element from m_visitedElements.

[Doug Kelly]

Created attachment 395293 [details]
Patch

[Geoffrey Garen]

Comment on attachment 395293 [details]
Patch

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

> Source/WebCore/rendering/svg/RenderSVGRoot.h:120
> +    HashSet<const RenderElement*> m_visitedElements;

If the visited elements set should only exist within the scope of a given CurrentVisitedElementsMaintainer, then perhaps it would be clearer (and smaller) for this data member to be a pointer to a CurrentVisitedElementsMaintainer, and the CurrentVisitedElementsMaintainer can hold the set of visited elements, and implement the functionality of startVisiting / stopVisiting / isVisiting.

(In the ideal world, we would explicitly pass the CurrentVisitedElementsMaintainer object to every function that needed to participate; but if that's not practical, storing a pointer to the CurrentVisitedElementsMaintainer inside the RenderSVGRoot seems OK to me. I don't really love the design where m_visitedElements lives on the RenderSVGRoot because it's a paradox for a heap-allocated object to maintain stack-scoped state.)

> Source/WebCore/rendering/svg/SVGRenderSupport.h:98
> +class CurrentVisitedElementsMaintainer {

Let's call this VisitedElementsScope.

[Ryosuke Niwa]

Comment on attachment 395293 [details]
Patch

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

> Source/WebCore/rendering/svg/RenderSVGRoot.h:67
> +    void startVisiting(RenderElement&);
> +    void stopVisiting(RenderElement&);
> +    bool isVisiting(const RenderElement&) const;

There are very generic names. We should probably rename them to something like:
addElementToCycleDetector, removeElementFromCycleDetector, & isElementInCycle or something.

> Source/WebCore/rendering/svg/RenderSVGRoot.h:120
> +    HashSet<const RenderElement*> m_visitedElements;

Please use WeakHashSet.

> Source/WebCore/rendering/svg/RenderSVGShape.cpp:369
> +    CurrentVisitedElementsMaintainer maintainer(*this);

We usually call these objects *Scope. I think we should call this one SVGCycleDetectionScope or something.

> Source/WebCore/rendering/svg/SVGRenderSupport.h:98
> +class CurrentVisitedElementsMaintainer {

This is a very generic name. We should probably call it SVGRenderCycleDetectionScope.

[Doug Kelly]

Created attachment 395768 [details]
Patch

[Geoffrey Garen]

Comment on attachment 395768 [details]
Patch

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

r=me

> Source/WebCore/rendering/svg/SVGRenderSupport.h:107
> +    static WeakHashSet<RenderElement>& getVisitedElements();

WebKit style is to name a C++ accessor by the accessed value's name. In this case, "visitedElements()". (We usually reserve the "get" prefix for something that returns an out parameter.)

> Source/WebCore/rendering/svg/SVGRenderSupport.h:108
> +    static WeakHashSet<RenderElement>& getVisitedElements();
> +    WeakPtr<RenderElement> m_element;

Upon reflection, I think it would be slightly clearer to make these pointers RefPtr. We don't actually intend for them to become null or disappear -- we just want a safe pointer idiom.

[Doug Kelly]

Comment on attachment 395768 [details]
Patch

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

>> Source/WebCore/rendering/svg/SVGRenderSupport.h:107
>> +    static WeakHashSet<RenderElement>& getVisitedElements();
> 
> WebKit style is to name a C++ accessor by the accessed value's name. In this case, "visitedElements()". (We usually reserve the "get" prefix for something that returns an out parameter.)

Seems reasonable (and easy enough to do).

>> Source/WebCore/rendering/svg/SVGRenderSupport.h:108
>> +    WeakPtr<RenderElement> m_element;
> 
> Upon reflection, I think it would be slightly clearer to make these pointers RefPtr. We don't actually intend for them to become null or disappear -- we just want a safe pointer idiom.

RenderObject doesn't seem to inherit from RefCounted, so I *think* the best I can do is a WeakPtr?  At least, trying to use a RefPtr encounters a compiler error because deref() doesn't exist.  (Also, I don't assume you're implying that WeakHashSet should be changed, because I don't see an analog here.)

[Doug Kelly]

Created attachment 395777 [details]
Patch

[zalan]

> Upon reflection, I think it would be slightly clearer to make these pointers
> RefPtr. We don't actually intend for them to become null or disappear -- we
> just want a safe pointer idiom.
Renderers should not be refcounted as they have a very clear ownership (and it is never a shared one). We've been using the weakptr to indicate weak reference across the rendering codebase.

[Geoffrey Garen]

Comment on attachment 395777 [details]
Patch

r=me

Okeedokee

[EWS]

Committed r259722: <https://trac.webkit.org/changeset/259722>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 395777 [details].

[Darin Adler]

Comment on attachment 395777 [details]
Patch

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

> Source/WebCore/rendering/svg/SVGRenderSupport.cpp:521
> +    bool result = visitedElements().remove(*m_element.get());

Normally we don’t need both "*" and ".get()".

> Source/WebCore/rendering/svg/SVGRenderSupport.h:101
> +    SVGHitTestCycleDetectionScope(const RenderElement&);

We should add "explicit".

[Doug Kelly]

(In reply to Darin Adler from comment #16)
> Comment on attachment 395777 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=395777&action=review
> 
> > Source/WebCore/rendering/svg/SVGRenderSupport.cpp:521
> > +    bool result = visitedElements().remove(*m_element.get());
> 
> Normally we don’t need both "*" and ".get()".
> 
> > Source/WebCore/rendering/svg/SVGRenderSupport.h:101
> > +    SVGHitTestCycleDetectionScope(const RenderElement&);
> 
> We should add "explicit".

Thanks, addressed in bug #210203.