Bug 35688 - expandUseElementsInShadowTree infinite recursion stack exhaustion.
Summary: expandUseElementsInShadowTree infinite recursion stack exhaustion.
Alias: None
Product: WebKit
Classification: Unclassified
Component: SVG (show other bugs)
Version: 528+ (Nightly build)
Hardware: PC Windows Vista
: P3 Normal
Assignee: Nobody
URL: http://code.google.com/p/chromium/iss...
Depends on:
Reported: 2010-03-03 07:54 PST by Berend-Jan Wever
Modified: 2012-05-21 14:03 PDT (History)
5 users (show)

See Also:

unreduced repro (10.53 KB, text/html)
2011-07-01 10:35 PDT, Tim Horton
no flags Details
significantly reduced repro (293 bytes, text/html)
2011-07-01 16:45 PDT, Tim Horton
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description Berend-Jan Wever 2010-03-03 07:54:38 PST
  <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:

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.
                use->parentNode()->replaceChild(cloneParent.release(), use, ec);

            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()))

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

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

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

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

    for (RefPtr<Node> child = element->firstChild(); child; child = child->nextSibling())
        expandUseElementsInShadowTree(shadowRoot, child.get());
Comment 1 Tim Horton 2011-06-29 12:39:12 PDT
Are you still able to reproduce this? I cannot.
Comment 2 Tim Horton 2011-06-29 13:29:17 PDT
Appears fixed in Safari/Chrome/QtWebKit. Please reopen if you can reproduce.
Comment 3 Tim Horton 2011-07-01 10:35:59 PDT
Created attachment 99485 [details]
unreduced repro
Comment 4 Tim Horton 2011-07-01 10:42:48 PDT
Attached a different reproduction which works on recent WebKit.
Comment 5 Tim Horton 2011-07-01 16:45:18 PDT
Created attachment 99538 [details]
significantly reduced repro
Comment 6 Nikolas Zimmermann 2012-03-01 06:44:46 PST
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?
Comment 7 Berend-Jan Wever 2012-03-01 09:57:44 PST
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).
Comment 8 Berend-Jan Wever 2012-03-06 04:39:22 PST
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.
Comment 9 Stephen Chenney 2012-05-21 14:03:42 PDT
Verified this no longer crashes.