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)

(bzr r14245)

17 files changed, 74 insertions, 48 deletions

diff --git a/src/live_effects/lpeobject-reference.cpp b/src/live_effects/lpeobject-reference.cpp
index 573c8a2fd..d9de6e77f 100644
--- a/src/live_effects/lpeobject-reference.cpp
+++ b/src/live_effects/lpeobject-reference.cpp
@@ -43,14 +43,7 @@ LPEObjectReference::~LPEObjectReference(void)
 bool LPEObjectReference::_acceptObject(SPObject * const obj) const
 {
     if (IS_LIVEPATHEFFECT(obj)) {
-        SPObject * const owner = getOwner();
-        /* Refuse references to us or to an ancestor. */
-        for ( SPObject *iter = owner ; iter ; iter = iter->parent ) {
-            if ( iter == obj ) {
-                return false;
-            }
-        }
-        return true;
+        return URIReference::_acceptObject(obj);
     } else {
         return false;
     }
diff --git a/src/live_effects/parameter/path-reference.cpp b/src/live_effects/parameter/path-reference.cpp
index a76fb1b32..42589b050 100644
--- a/src/live_effects/parameter/path-reference.cpp
+++ b/src/live_effects/parameter/path-reference.cpp
@@ -22,7 +22,7 @@ bool PathReference::_acceptObject(SPObject * const obj) const
             return false;
         }
         // TODO: check whether the referred path has this LPE applied, if so: deny deny deny!
-        return true;
+        return URIReference::_acceptObject(obj);
     } else {
         return false;
     }
diff --git a/src/persp3d-reference.cpp b/src/persp3d-reference.cpp
index 895eac6f2..4526a8d8f 100644
--- a/src/persp3d-reference.cpp
+++ b/src/persp3d-reference.cpp
@@ -35,7 +35,8 @@ Persp3DReference::~Persp3DReference(void)
 bool
 Persp3DReference::_acceptObject(SPObject *obj) const
 {
-    return SP_IS_PERSP3D(obj);
+    return SP_IS_PERSP3D(obj) && URIReference::_acceptObject(obj);
+;
     /* effic: Don't bother making this an inline function: _acceptObject is a virtual function,
        typically called from a context where the runtime type is not known at compile time. */
 }
diff --git a/src/sp-clippath.h b/src/sp-clippath.h
index 91dcfd625..c9a8c68df 100644
--- a/src/sp-clippath.h
+++ b/src/sp-clippath.h
@@ -88,7 +88,7 @@ protected:
             return false;
         }
         SPObject * const owner = this->getOwner();
-        if (obj->isAncestorOf(owner)) {
+        if (!URIReference::_acceptObject(obj)) {
             //XML Tree being used directly here while it shouldn't be...
             Inkscape::XML::Node * const owner_repr = owner->getRepr();
             //XML Tree being used directly here while it shouldn't be...
diff --git a/src/sp-filter-reference.cpp b/src/sp-filter-reference.cpp
index 57600ad39..afb014820 100644
--- a/src/sp-filter-reference.cpp
+++ b/src/sp-filter-reference.cpp
@@ -4,7 +4,7 @@
 bool
 SPFilterReference::_acceptObject(SPObject *obj) const
 {
-    return SP_IS_FILTER(obj);
+    return SP_IS_FILTER(obj) && URIReference::_acceptObject(obj);
     /* effic: Don't bother making this an inline function: _acceptObject is a virtual function,
        typically called from a context where the runtime type is not known at compile time. */
 }
diff --git a/src/sp-gradient-reference.cpp b/src/sp-gradient-reference.cpp
index d2b8128fb..216ac73de 100644
--- a/src/sp-gradient-reference.cpp
+++ b/src/sp-gradient-reference.cpp
@@ -4,7 +4,7 @@
 bool
 SPGradientReference::_acceptObject(SPObject *obj) const
 {
-    return SP_IS_GRADIENT(obj);
+    return SP_IS_GRADIENT(obj) && URIReference::_acceptObject(obj);
     /* effic: Don't bother making this an inline function: _acceptObject is a virtual function,
        typically called from a context where the runtime type is not known at compile time. */
 }
diff --git a/src/sp-hatch.h b/src/sp-hatch.h
index 5004a611f..546f06a1e 100644
--- a/src/sp-hatch.h
+++ b/src/sp-hatch.h
@@ -168,7 +168,7 @@ public:
 
 protected:
     virtual bool _acceptObject(SPObject *obj) const {
-        return dynamic_cast<SPHatch *>(obj) != NULL;
+        return dynamic_cast<SPHatch *>(obj) != NULL && URIReference::_acceptObject(obj);
     }
 };
 
diff --git a/src/sp-marker.h b/src/sp-marker.h
index 56cbaf94f..bae13243b 100644
--- a/src/sp-marker.h
+++ b/src/sp-marker.h
@@ -92,7 +92,7 @@ class SPMarkerReference : public Inkscape::URIReference {
 	}
 protected:
 	virtual bool _acceptObject(SPObject *obj) const {
-		return SP_IS_MARKER(obj);
+		return SP_IS_MARKER(obj) && URIReference::_acceptObject(obj);
 	}
 };
 
diff --git a/src/sp-mask.h b/src/sp-mask.h
index 3559483bb..74bd4d66e 100644
--- a/src/sp-mask.h
+++ b/src/sp-mask.h
@@ -81,7 +81,7 @@ protected:
 		    return false;
 	    }
 	    SPObject * const owner = this->getOwner();
-        if (obj->isAncestorOf(owner)) {
+        if (!URIReference::_acceptObject(obj)) {
 	  //XML Tree being used directly here while it shouldn't be...
 	  Inkscape::XML::Node * const owner_repr = owner->getRepr();
 	  //XML Tree being used directly here while it shouldn't be...
diff --git a/src/sp-object.cpp b/src/sp-object.cpp
index 0bb8c240f..db66eb3e6 100644
--- a/src/sp-object.cpp
+++ b/src/sp-object.cpp
@@ -721,6 +721,9 @@ void SPObject::invoke_build(SPDocument *document, Inkscape::XML::Node *repr, uns
     }
     this->cloned = cloned;
 
+    /* Invoke derived methods, if any */
+    this->build(document, repr);
+
     if ( !cloned ) {
         this->document->bindObjectToRepr(this->repr, this);
 
@@ -754,8 +757,6 @@ void SPObject::invoke_build(SPDocument *document, Inkscape::XML::Node *repr, uns
         g_assert(this->getId() == NULL);
     }
 
-    /* Invoke derived methods, if any */
-    this->build(document, repr);
 
     /* Signalling (should be connected AFTER processing derived methods */
     sp_repr_add_listener(repr, &object_event_vector, this);
diff --git a/src/sp-paint-server.cpp b/src/sp-paint-server.cpp
index ae40ad1aa..c3416c6c8 100644
--- a/src/sp-paint-server.cpp
+++ b/src/sp-paint-server.cpp
@@ -27,7 +27,7 @@ SPPaintServer *SPPaintServerReference::getObject() const
 
 bool SPPaintServerReference::_acceptObject(SPObject *obj) const
 {
-    return SP_IS_PAINT_SERVER(obj);
+    return SP_IS_PAINT_SERVER(obj) && URIReference::_acceptObject(obj);
 }
 
 SPPaintServer::SPPaintServer() : SPObject() {
diff --git a/src/sp-pattern.h b/src/sp-pattern.h
index 145bb934e..a5e7be1d4 100644
--- a/src/sp-pattern.h
+++ b/src/sp-pattern.h
@@ -129,9 +129,8 @@ public:
     }
 
 protected:
-    virtual bool _acceptObject(SPObject *obj) const
-    {
-        return SP_IS_PATTERN(obj);
+    virtual bool _acceptObject(SPObject *obj) const {
+        return SP_IS_PATTERN (obj)&& URIReference::_acceptObject(obj);
     }
 };
 
diff --git a/src/sp-tag-use-reference.cpp b/src/sp-tag-use-reference.cpp
index 220cd16d1..9fcb31fd1 100644
--- a/src/sp-tag-use-reference.cpp
+++ b/src/sp-tag-use-reference.cpp
@@ -24,14 +24,7 @@
 bool SPTagUseReference::_acceptObject(SPObject * const obj) const
 {
     if (SP_IS_ITEM(obj)) {
-        SPObject * const owner = getOwner();
-        // Refuse references to us or to an ancestor.
-        for ( SPObject *iter = owner ; iter ; iter = iter->parent ) {
-            if ( iter == obj ) {
-                return false;
-            }
-        }
-        return true;
+        return URIReference::_acceptObject(obj);
     } else {
         return false;
     }
diff --git a/src/sp-tref-reference.cpp b/src/sp-tref-reference.cpp
index e82f575e0..7c6ff00e7 100644
--- a/src/sp-tref-reference.cpp
+++ b/src/sp-tref-reference.cpp
@@ -21,7 +21,7 @@ bool SPTRefReference::_acceptObject(SPObject * const obj) const
 {
     SPObject *owner = getOwner();
     if (SP_IS_TREF(owner))
-        return sp_tref_reference_allowed(SP_TREF(getOwner()), obj);
+        return URIReference::_acceptObject(obj);
     else
         return false;
 }
diff --git a/src/sp-use-reference.cpp b/src/sp-use-reference.cpp
index 642cfede8..f0b2985d2 100644
--- a/src/sp-use-reference.cpp
+++ b/src/sp-use-reference.cpp
@@ -25,18 +25,7 @@
 
 bool SPUseReference::_acceptObject(SPObject * const obj) const
 {
-    if (SP_IS_ITEM(obj)) {
-        SPObject * const owner = getOwner();
-        // Refuse references to us or to an ancestor.
-        for ( SPObject *iter = owner ; iter ; iter = iter->parent ) {
-            if ( iter == obj ) {
-                return false;
-            }
-        }
-        return true;
-    } else {
-        return false;
-    }
+	return URIReference::_acceptObject(obj);
 }
 
 
diff --git a/src/uri-references.cpp b/src/uri-references.cpp
index 2518c173e..04f904d39 100644
--- a/src/uri-references.cpp
+++ b/src/uri-references.cpp
@@ -43,6 +43,56 @@ URIReference::~URIReference()
     detach();
 }
 
+/*
+ * The main ideas here are:
+ * (1) "If we are inside a clone, then we can accept if and only if our "original thing" can accept the reference"
+ * (this caused problems when there are clones because a change in ids triggers signals for the object hrefing this id, but also its cloned reprs
+ * (descendants of <use> referencing an ancestor of the href'ing object)). The way it is done here is *atrocious*, but i could not find a better way.
+ * FIXME: find a better and safer way to find the "original object" of anyone with the flag ->cloned
+ *
+ * (2) Once we have an (potential owner) object, it can accept a href to obj, iff the graph of objects where directed edges are
+ * either parent->child relations , *** or href'ing to href'ed *** relations, stays acyclic.
+ * We can go either from owner and up in the tree, or from obj and down, in either case this will be in the worst case linear in the number of objects.
+ * There are no easy objects allowing to do the second proposition, while "hrefList" is a "list of objects href'ing us", so we'll take this.
+ * Then we keep a set of already visited elements, and do a DFS on this graph. if we find obj, then BOOM.
+ */
+
+bool URIReference::_acceptObject(SPObject *obj) const {
+	//we go back following hrefList and parent to find if the object already references ourselves indirectly
+	std::set<SPObject*> done;
+	SPObject * owner = getOwner();
+	if(!owner)return true;
+	while(owner->cloned){
+		std::vector<int> positions;
+        while(owner->cloned){
+        	int position=0;
+        	SPObject* c = owner->parent->firstChild();
+        	while(c != owner && dynamic_cast<SPObject*>(c) ){position++;c=c->next;}
+	    	positions.push_back(position);
+    		owner=owner->parent;
+    	}
+		    owner = ((SPUse*)owner)->get_original();
+		    for(int i=positions.size()-2;i>=0;i--)owner=owner->childList(false)[positions[i]];
+	}
+	//once we have the "original" object (hopefully) we look at who is referencing it
+	std::list<SPObject*> todo(owner->hrefList);
+	todo.push_front(owner->parent);
+	while(!todo.empty()){
+	    SPObject* e = todo.front();
+	    todo.pop_front();
+	    if(!dynamic_cast<SPObject*>(e))continue;
+	    if(done.insert(e).second){
+	    	if(e==obj){return false;}
+	    	todo.push_front(e->parent);
+	    	todo.insert(todo.begin(),e->hrefList.begin(),e->hrefList.end());
+	    }
+	}
+    return true;
+}
+
+
+
+
 void URIReference::attach(const URI &uri) throw(BadURIException)
 {
     SPDocument *document = NULL;
diff --git a/src/uri-references.h b/src/uri-references.h
index 0c51481cc..e56ea0612 100644
--- a/src/uri-references.h
+++ b/src/uri-references.h
@@ -15,11 +15,15 @@
  */
 
 #include <cstddef>
+#include <vector>
+#include <set>
 #include <sigc++/connection.h>
 #include <sigc++/trackable.h>
 
 #include "bad-uri-exception.h"
 #include "sp-object.h"
+#include "sp-item.h"
+#include "sp-use.h"
 
 namespace Inkscape {
 
@@ -122,11 +126,7 @@ public:
     SPObject   *getOwnerObject()   { return _owner; }
 
 protected:
-    virtual bool _acceptObject(SPObject *obj) const {
-        (void)obj;
-        return true;
-    }
-
+    virtual bool _acceptObject(SPObject *obj) const;
 private:
     SPObject *_owner;
     SPDocument *_owner_document;