Bug 35688 – expandUseElementsInShadowTree infinite recursion stack exhaustion.

• Status: RESOLVED
• Resolution: FIXED
• Component: SVG

[Berend-Jan Wever]

Repro:
  <svg xmlns="http://www.w3.org/2000/svg">
  <g id="foo">
  <svg xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xl="http://www.w3.org/1999/xlink">
  <use xl:href="#foo"/>
  <g id="bar" />
  <use xlink:href="#bar" />

This causes infinite recursion in expandUseElementsInShadowTree, which leads to stack exhaustion. Below is the code, as you can see, it calls itself in two locations. The 
bottom one seems to be the culprit in this case:

http://svn.webkit.org/repository/webkit/trunk/WebCore/svg/SVGUseElement.cpp?r=55462
void SVGUseElement::expandUseElementsInShadowTree(SVGShadowTreeRootElement* shadowRoot, Node* element)
{
    // Why expand the <use> elements in the shadow tree here, and not just
    // do this directly in buildShadowTree, if we encounter a <use> element?
    //
    // Short answer: Because we may miss to expand some elements. Ie. if a <symbol>
    // contains <use> tags, we'd miss them. So once we're done with settin' up the
    // actual shadow tree (after the special case modification for svg/symbol) we have
    // to walk it completely and expand all <use> elements.
    if (element->hasTagName(SVGNames::useTag)) {
        SVGUseElement* use = static_cast<SVGUseElement*>(element);

        String id = SVGURIReference::getTarget(use->href());
        Element* targetElement = document()->getElementById(id); 
        SVGElement* target = 0;
        if (targetElement && targetElement->isSVGElement())
            target = static_cast<SVGElement*>(targetElement);

        // Don't ASSERT(target) here, it may be "pending", too.
        if (target) {
            // Setup sub-shadow tree root node
            RefPtr<SVGShadowTreeContainerElement> cloneParent = new SVGShadowTreeContainerElement(document());

            // Spec: In the generated content, the 'use' will be replaced by 'g', where all attributes from the
            // 'use' element except for x, y, width, height and xlink:href are transferred to the generated 'g' element.
            transferUseAttributesToReplacedElement(use, cloneParent.get());

            ExceptionCode ec = 0;

            // For instance <use> on <foreignObject> (direct case).
            if (isDisallowedElement(target)) {
                // We still have to setup the <use> replacment (<g>). Otherwhise
                // associateInstancesWithShadowTreeElements() makes wrong assumptions.
                // Replace <use> with referenced content.
                ASSERT(use->parentNode()); 
                use->parentNode()->replaceChild(cloneParent.release(), use, ec);
                ASSERT(!ec);
                return;
            }

            RefPtr<Element> newChild = target->cloneElementWithChildren();

            // We don't walk the target tree element-by-element, and clone each element,
            // but instead use cloneElementWithChildren(). This is an optimization for the common
            // case where <use> doesn't contain disallowed elements (ie. <foreignObject>).
            // Though if there are disallowed elements in the subtree, we have to remove them.
            // For instance: <use> on <g> containing <foreignObject> (indirect case).
            if (subtreeContainsDisallowedElement(newChild.get()))
                removeDisallowedElementsFromSubtree(newChild.get());

            SVGElement* newChildPtr = 0;
            if (newChild->isSVGElement())
                newChildPtr = static_cast<SVGElement*>(newChild.get());
            ASSERT(newChildPtr);

            cloneParent->appendChild(newChild.release(), ec);
            ASSERT(!ec);

            // Replace <use> with referenced content.
            ASSERT(use->parentNode()); 
            use->parentNode()->replaceChild(cloneParent.release(), use, ec);
            ASSERT(!ec);

            // Immediately stop here, and restart expanding.
            expandUseElementsInShadowTree(shadowRoot, shadowRoot);
            return;
        }
    }

    for (RefPtr<Node> child = element->firstChild(); child; child = child->nextSibling())
        expandUseElementsInShadowTree(shadowRoot, child.get());
}

[Tim Horton]

Are you still able to reproduce this? I cannot.

[Tim Horton]

Appears fixed in Safari/Chrome/QtWebKit. Please reopen if you can reproduce.

[Tim Horton]

Created attachment 99485 [details]
unreduced repro

[Tim Horton]

Attached a different reproduction which works on recent WebKit.

[Tim Horton]

Created attachment 99538 [details]
significantly reduced repro

[Nikolas Zimmermann]

Since bug 77764 landed, this can't happen anymore, we now white-list allowed use shadow tree elements, everything else is removed from the DOM.

Does anyone know another way to trigger this? Shall we still add the reduced testcase? I guess it crashed before in trunk reliable?

[Berend-Jan Wever]

I'm not aware of any other cases and I haven't found any during fuzzing in a long time. (But it may be my fuzzers aren't very effective at finding this kind of bug).

[Berend-Jan Wever]

Coincidentally, my fuzzers found two cases after I wrote that. However, they were testing a version of WebKit that didn't have the patch. After the patch, these cases no longer reproduce. So it seems my fuzzer should be able to catch any regressions or variations. I think we can close this one out.

[Stephen Chenney]

Verified this no longer crashes.