Bug 6000 - <use> does not handle recursion safely
Summary: <use> does not handle recursion safely
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: SVG (show other bugs)
Version: 420+
Hardware: Mac OS X 10.4
: P2 Normal
Assignee: Nikolas Zimmermann
URL:
Keywords: NeedsReduction, SVGHitList
Depends on:
Blocks:
 
Reported: 2005-12-08 01:25 PST by Eric Seidel (no email)
Modified: 2007-01-30 11:54 PST (History)
2 users (show)

See Also:


Attachments
Patch rewriting use - not ready yet! (54.26 KB, patch)
2007-01-17 06:46 PST, Nikolas Zimmermann
no flags Details | Formatted Diff | Diff
Initial patch (260.91 KB, patch)
2007-01-28 13:45 PST, Nikolas Zimmermann
no flags Details | Formatted Diff | Diff
Updated patch (316.70 KB, patch)
2007-01-29 04:32 PST, Nikolas Zimmermann
sam: review-
Details | Formatted Diff | Diff
Final patch (316.70 KB, patch)
2007-01-30 04:34 PST, Nikolas Zimmermann
mrowe: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Eric Seidel (no email) 2005-12-08 01:25:39 PST
<use> does not handle recursion correctly

If nothing else, <use> needs to check for recursive loops, otherwise Safari might just blow up on bad 
content.  The FireFox devs have some testcase for these sorts of things which I will attach.
Comment 1 Eric Seidel (no email) 2006-01-26 15:23:15 PST
Because these could all be Safari crashers, we would not want to ship an SVG implementation without these fixed.  Adding SVGHitList keyword and bumping to P2.

I began a patch at one time to fix <pattern> and <gradient>.  The way that I envision solving this is:

1.  Create a on-the-stack simplified "pattern attributes" or "gradient attributes" structure.
2.  Loop backwards through the xlink:href parent chain until either one of the following:
- All attributes in the structure are filled
- The chain terminates (no more, or you reach a node you've seen before).

I would suggest using a HashSet to keep track of all the nodes that you've seen when walking backwards.  In all three cases one of the required "attributes" to track in this structure is a pointer to whichever pattern/gradient/use element actually had children that you're going to render.  In all three cases, if an element does not itself have children, it uses the children of the first element in its xlink:href inheritance chain when rendering.
Comment 2 Eric Seidel (no email) 2006-04-09 13:03:15 PDT
I'm adding the NeedsReduction keyword as this bug really could use probably 10+ test cases to catch all the recursion cases coverd by these elements.
Comment 3 Eric Seidel (no email) 2006-12-31 19:53:54 PST
At least gradients and patterns are likely to be addressed in Wildfox's next patch.
Comment 4 Nikolas Zimmermann 2007-01-02 04:26:12 PST
Fixed by bug 12013 patch for gradients & patterns. <use> still TODO. Landed in r18521.
Comment 5 Nikolas Zimmermann 2007-01-17 06:46:34 PST
Created attachment 12503 [details]
Patch rewriting use - not ready yet!

Patch for early-birds - not ready yet.
Comment 6 Nikolas Zimmermann 2007-01-28 13:45:40 PST
Created attachment 12731 [details]
Initial patch

Hopefully the last big <use> rewrite - this time using a proper shadow tree!
Fixes all issues & uglyness we had before.
Comment 7 Oliver Hunt 2007-01-28 14:09:59 PST
Comment on attachment 12731 [details]
Initial patch

SVGUseElement:
-    Copyright (C) 2004, 2005, 2006, 2007 Nikolas Zimmermann <zimmermann@kde.org>
-                  2004, 2005, 2006 Rob Buis <buis@kde.org>
+    Copyright (C) 2007 Nikolas Zimmermann <zimmermann@kde.org>

You're removing Rob's copyright???

SVGUseElement.cpp: replace NOTE: with FIXME:

Looks fine to me, but i'd be happier if eric did a once over as well
Comment 8 Nikolas Zimmermann 2007-01-28 14:16:00 PST
(In reply to comment #7)
> (From update of attachment 12731 [details] [edit])
> SVGUseElement:
> -    Copyright (C) 2004, 2005, 2006, 2007 Nikolas Zimmermann
> <zimmermann@kde.org>
> -                  2004, 2005, 2006 Rob Buis <buis@kde.org>
> +    Copyright (C) 2007 Nikolas Zimmermann <zimmermann@kde.org>
> 
> You're removing Rob's copyright???
Whoops, copy'n'paste! Will fix. My copyright year is also wrong...

> SVGUseElement.cpp: replace NOTE: with FIXME:
Okay.
 
> Looks fine to me, but i'd be happier if eric did a once over as well
Thanks for the review! :-)

Niko
Comment 9 Eric Seidel (no email) 2007-01-28 14:48:17 PST
Comment on attachment 12731 [details]
Initial patch

The patch seems fine.  It does not seem to address the bug however.  Nor does it seem to have tests for the bug.

The bug was about <use> recursion, and how recursive <use>'s could send Safari off spinning forever.  Maybe that's handled here and I just don't see it.

Also, this seems strange:
*to->attributes() = *from->attributes();
Comment 10 Nikolas Zimmermann 2007-01-29 04:29:42 PST
(In reply to comment #9)
> (From update of attachment 12731 [details] [edit])
> The patch seems fine.  It does not seem to address the bug however.  Nor does
> it seem to have tests for the bug.
> 
> The bug was about <use> recursion, and how recursive <use>'s could send Safari
> off spinning forever.  Maybe that's handled here and I just don't see it.
Hehe funny, I mixed up things, I thought this bug was about "expansion" of <use> elements.
Uploading new patch which contains 4 recursion tests, and actually handles recursion.

Good catch :-)

> Also, this seems strange:
> *to->attributes() = *from->attributes();
This is common WebCore code: (see Element::cloneNode)
...
    // clone attributes
    if (namedAttrMap)
        *clone->attributes() = *namedAttrMap;
...
 
Niko
Comment 11 Nikolas Zimmermann 2007-01-29 04:32:48 PST
Created attachment 12736 [details]
Updated patch

This time it actually also fixes this bug - handle recursion properly.
As SVG spec doesn't say a word about recursion, I'm doing the only logical thing: just ignore cycles.
Comment 12 Mark Rowe (bdash) 2007-01-29 05:10:23 PST
Comment on attachment 12736 [details]
Updated patch

Discussed a slightly updated version of this on IRC.  r=me
Comment 13 Sam Weinig 2007-01-29 17:14:54 PST
Comment on attachment 12736 [details]
Updated patch

Marking r- until the leaks are dealt with.
Comment 14 Nikolas Zimmermann 2007-01-30 04:34:06 PST
Created attachment 12788 [details]
Final patch

Finally it does not leak anymore! The problematic area was SVGElementInstance, it always ref()'ed the correspondingUseElement so these never got deleted, once expandUseElementsInShadowTree() was executed. No new regressions - <use> feels much more stable today (ie. carto.net/window.svg works _perfectly_ now - no bugs!), no new leaks. All fine :-)
Comment 15 Mark Rowe (bdash) 2007-01-30 04:47:29 PST
Comment on attachment 12788 [details]
Final patch

r=me.  Glad to see you finally tracked those leaks down!
Comment 16 Sam Weinig 2007-01-30 11:54:07 PST
Landed in r19254.