circular reference to samefile.svg

[Bug Importer]

version: 0.43 (and probably also svn10765)

A hand-edited or externally sourced svg may contain a
self-referential xlink:href to itself. Inkscape should
consider this to be an invalid circular reference as per:

  http://www.w3.org/TR/SVG11/struct.html#Head

  "URI references that directly or indirectly reference
themselves are treated as invalid circular references."

Example:

  (within file "image_recursive.svg")

  <image
       ...
       xlink:href="image_recursive.svg" />

Current behavior appears to be infinite recursion
(attached file causes inkscape to run up to 1GB+ ram
usage very quickly.)

Note that this is (apparently) not reproducible through
the non-xml inkscape interface, though recent
discussions of providing more control over link/embed
behavior may change this.

[Ericwilhelm (ericwilhelm)]

This bug submitted by me (sorry, thought I was logged-in --
doesn't look like I can change that now though.)

[Ericwilhelm (ericwilhelm)]

Ack! Attachment got dropped too. Last try:

  http://scratchcomputing.com/tmp/image_recursive.svg

[Fluffy-lobster (fluffy-lobster)]

Originator: NO

I suspect there is a wider flaw in the handling of circular recursion
which needs addressing to resolve this bug. There are a number of ways to
crash Inkscape by trying to drag elements in the XML tree into elements
they reference. For example, try to drag an object into its mask, or a
<use> into the element it uses.

[Florent Becker (florent-becker-ens-lyon)]

this can be triggered without using the xml editor.

Create a group, clone it, cut the clone, right-click the group, enter group #g1337, paste.

THEN inkscape goes into an infinite loop after a while (but does not seem to try to render the pasted clone)

[Stephen Eisenhauer (bhspitmonkey)]

I stopped by to report the exact issue Florent described. It's not hard to do this by mistake while copying/pasting clones, and Inkscape seems to have no built-in protection against these infinite recursive cases currently.

[Guiu Rocafort (neandertalspeople)]

I've been playing a little bit with the SVG 1.1 test suite circled a little bit the problem.

Just circular references doesn't cause problem, but when there is an element with a reference to a group which has a child element which causes a circular dependency to the first element then inkscape enters an infinite loop.

The attached svg reproduces the problem.

[su_v (suv-lp)]

Related page of the SVG 1.1 test suite (2nd edition):
<http://www.w3.org/Graphics/SVG/Test/20110816/harness/htmlObjectApproved/struct-use-12-f.html>
(AFAIU the crash is triggered by the 'useMultipleIndirectNestedGroup' scenario)

Raising bug importance:
- Inkscape 0.48.4 and current trunk crash when trying to load the sample file or the original file from the testsuite.
<http://wiki.inkscape.org/wiki/index.php/Bug_management#Bug_importance>

[Guiu Rocafort (neandertalspeople)]

I managed to get a backtrace of the crash while opening the file circular.svg posted above. There is an infinite loop with the following functions:

SPUse::href_changed
SPObject::invoke_build
SPObject::build
SPObject::readAttr
SPObject::setKeyValue
SPUse::set
Inkscape::URIReference::attach
Inkscape::URIReference::_setObject

and then the SPUSe::href_changed is called again and it starts again the same succession.

[Guiu Rocafort (neandertalspeople)]

A fragment of the detailed backtrace:

#0 0xb6f154b8 in sigc::internal::signal_impl::notify(void*) () from /usr/lib/i386-linux-gnu/libsigc-2.0.so.0
#1 0xb6f15f22 in sigc::internal::slot_rep::disconnect() () from /usr/lib/i386-linux-gnu/libsigc-2.0.so.0
#2 0xb6f16151 in sigc::slot_base::disconnect() () from /usr/lib/i386-linux-gnu/libsigc-2.0.so.0
#3 0xb6f15e11 in sigc::connection::disconnect() () from /usr/lib/i386-linux-gnu/libsigc-2.0.so.0
#4 0x08207d6e in sp_style_clear (style=0xd2c7f08) at style.cpp:3044
#5 0x0820ba5f in sp_style_read (style=0xd2c7f08, object=0xd2c7da8, repr=0xa3037f0) at style.cpp:647
#6 0x081ddf4f in SPObject::set (this=0xd2c7da8, key=9, value=0x0) at sp-object.cpp:902
#7 0x081b3601 in SPItem::set (this=0xd2c7da8, key=9, value=0x0) at sp-item.cpp:509
#8 0x081ff0e8 in SPUse::set (this=0xd2c7da8, key=9, value=0x0) at sp-use.cpp:155
#9 0x081dbaef in setKeyValue (value=<optimized out>, key=9, this=0xd2c7da8) at sp-object.cpp:915
#10 SPObject::readAttr (this=0xd2c7da8, key=0x892e2ac "style") at sp-object.cpp:932
#11 0x081b17eb in SPItem::build (this=0xd2c7da8, document=0x8f01e40, repr=0xa3037f0) at sp-item.cpp:389
#12 0x081ff3a0 in SPUse::build (this=0xd2c7da8, document=0x8f01e40, repr=0xa3037f0) at sp-use.cpp:76
#13 0x081db753 in SPObject::invoke_build (this=0xd2c7da8, document=0x8f01e40, repr=0xa3037f0, cloned=1) at sp-object.cpp:722
#14 0x081ffd38 in SPUse::href_changed (this=0xd2c7720) at sp-use.cpp:436
#15 0x0821d931 in emit (_A_a2=<optimized out>, _A_a1=<optimized out>, impl=<optimized out>)
    at /usr/include/sigc++-2.0/sigc++/signal.h:1252
#16 emit (_A_a2=<optimized out>, _A_a1=<optimized out>, this=<optimized out>)
    at /usr/include/sigc++-2.0/sigc++/signal.h:2891
#17 Inkscape::URIReference::_setObject (this=0xd2c7b58, obj=0xd2c7c18) at uri-references.cpp:124
#18 0x0821dd41 in Inkscape::URIReference::attach (this=0xd2c7b58, uri=...) at uri-references.cpp:94
#19 0x081ff208 in SPUse::set (this=0xd2c7720, key=13, value=0xa2bd450 "#b") at sp-use.cpp:142
#20 0x081dbaef in setKeyValue (value=<optimized out>, key=13, this=0xd2c7720) at sp-object.cpp:915
#21 SPObject::readAttr (this=0xd2c7720, key=0x882f82b "xlink:href") at sp-object.cpp:932
#22 0x081db753 in SPObject::invoke_build (this=this@entry=0xd2c7720, document=document@entry=0x8f01e40,
    repr=repr@entry=0xa303670, cloned=1) at sp-object.cpp:722
#23 0x081de121 in SPObject::build (this=0xd2c71a0, document=0x8f01e40, repr=0xa3036f0) at sp-object.cpp:655
#24 0x081db753 in SPObject::invoke_build (this=0xd2c71a0, document=0x8f01e40, repr=0xa3036f0, cloned=1) at sp-object.cpp:722
#25 0x081ffd38 in SPUse::href_changed (this=0xd2c6aa8) at sp-use.cpp:436
#26 0x0821d931 in emit (_A_a2=<optimized out>, _A_a1=<optimized out>, impl=<optimized out>)
    at /usr/include/sigc++-2.0/sigc++/signal.h:1252
#27 emit (_A_a2=<optimized out>, _A_a1=<optimized out>, this=<optimized out>)
    at /usr/include/sigc++-2.0/sigc++/signal.h:2891
#28 Inkscape::URIReference::_setObject (this=0xd2a68a0, obj=0xd2c7028) at uri-references.cpp:124
#29 0x0821dd41 in Inkscape::URIReference::attach (this=0xd2a68a0, uri=...) at uri-references.cpp:94
#30 0x081ff208 in SPUse::set (this=0xd2c6aa8...

[Guiu Rocafort (neandertalspeople)]

Hi, ive been trying a little bit and I noticed that the bug is solved commenting the line:

uri-references.cpp:111
_connection = document->connectIdChanged(id, sigc::mem_fun(*this, &URIReference::_setObject));

Of course this is not a definitive fix, but the problem is getting circled in a narrower of the code.

[Krzysztof Kosinski (tweenk)]

The problem seems to be that when a new reference is made, Inkscape is detecting cycles by checking whether the target is an ancestor of the reference owner, while in reality it should check whether the set of all objects referenced by target contains any of the owner's ancestors. A new virtual function in the SP tree that would compute all referenced items might be required to solve this.

[Mc (mc...)]

I tried to see what could be done about this old bug, and came up with the attached patch. It does not crash on the struct-use-12-f w3c test.
Its main contents is URIReference::_acceptObject which is called by all subclasses of URIReference to check the absence of a loop.

I'm far from believing this is a perfect fix, but i'd like to get feedback about it before committing, there is great potential from error

[su_v (suv-lp)]

Fix committed to trunk in rev 14245:
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/revision/14245

Commit message:
> Fix for circular references detection in almost all cases, fixing
> https://bugs.launchpad.net/inkscape/+bug/167247 and a few of its
> duplicates. This fix is aimed at preventing any sort of circular
> references with the URIReference::_acceptObject method, checking the
> absence of loops in the reference+child tree.
>
> There can be some performance improvements done if we add a pointer
> from cloned sub-objects to their origin sub-object.
>
> The remaining cases that are not fixed can involve non-trivial loops
> using one or more "url()" stylesheet references. Being able to take
> them into account would require a non-obvious style.cpp refactoring
> making use of URIReference for this kind of reference (and not
> handling manually the signals in the styling code, which would
> probably be a good thing to do anyway)

Any remaining issues with circular references or regressions should be tracked in separate reports.