84187 - rdfliner unhappy on cyclic graphs

Status: RESOLVED WORKSFORME

(Core :: XUL, defect, P2)

Description

[Eric Murphy]

From Bugzilla Helper:
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9+) Gecko/20010605
BuildID:    2001060504

I created a rock-paper-scissors scenario in RDF. The outliner should expand
"infinitely".

rock > paper > scissors > CRASH

Reproducible: Always
Steps to Reproduce:
Open the rps.xul and start expanding the tree.

Comment 1

[Eric Murphy]

Attachment: rps.rdf

Comment 2

[Eric Murphy]

Attachment: template-outliner.xul

Comment 3

[Chris Waterson]

This is happening because I'm using an RDF datasource to store the ``open'' and
``closed'' state of each row. This is indexed by the URI of the row, so, once we
get back around to ``Rock'', it attempts to recursively open rows until it runs
out of stack space!

Comment 4

[Chris Waterson]

Attachment: suck less when presented with a cyclic graph

Comment 5

[Chris Waterson]

Okay, this patch makes us suck a bit less when presented with a cyclic graph.
We'll still crash eventually (probably because the XUL outliner builder assumes
that every row in the graph corresponds uniquely to an RDF resource). jan,
bryner: what do you think?

Comment 6

[Chris Waterson]

bryner, jan: could you r=? thanks...

Comment 7

[Jan Varga [:janv]]

I've found crasher.
You should check for aIndex == -1 in OpenSubreeOf()

anyway, sorry for delay

Comment 8

[Chris Waterson]

Attachment: what jan said.

Comment 9

[Jan Varga [:janv]]

r=[e-mail]

Comment 10

[kinmoz]

rs=[e-mail]

Comment 11

[Chris Waterson]

Okay, I've changed my mind. This is wallpaper: I'll try to figure out the real
fix instead.

Comment 12

[John Morrison]

May God have mercy on us all. The 212 bug spam-o-rama is Now!

Comment 13

[Asa Dotzler [:asa]]

Bugs targeted at mozilla1.0 without the mozilla1.0 keyword moved to mozilla1.0.1 
(you can query for this string to delete spam or retrieve the list of bugs I've 
moved)

Comment 14

[Wesley W. Terpstra]

Ok, I have been looking at this for a while now and I have two patches.
Neither of them is acceptable; I will outline below.

Comment 15

[Wesley W. Terpstra]

Attachment: Enforce the only one path to a resource rule (bad idea)

This patch will enforce that given a particular starting root, all nodes are
visible from only one path. This breaks cycles.

This is a terrible idea. For the practical situations where this happens we
have very poor behaviour.

Example:
  root 1 -> * (a personal fact) 1 -> * (person who knows it)

In this case, it would only appear that Fred knew one fact about me even if he
knew two! This is clearly not the intent of the graph represented in this tree.


Also, this case is also a bug in mozilla at present since closing the container
will remove elements from the conflictset on container close. eg: if (person
who knows it) has properties, you can cause a crash without cycles.

Comment 16

[Wesley W. Terpstra]

Attachment: Deep tree traversal works, but will die because of the conflict set

This patch will allow the user to descend infinitely.
Ideally, this would be a toggle in the XUL like flags="dont-save-state"

However, when a container is closed, the conflictset has stuff removed.
This will free the nsTemplateMatch* mMatch; in nsTreeRows::Row leading to an
eventual crash.

As to the semantics of this patch, I am uncertain that infinite descent is
desireable since niavely programmed JS users of a tree could hang.

On the other hand, this method does not require checking the parents which
satisfies Jan's stated requirement that it be fast.

Back to the first hand, since the tree is marked by a flag "dont-save-state",
the JS programmer should be tipped off. Maybe "infinite-recursion" would be
better. ,-)

Comment 17

[Wesley W. Terpstra]

As the first step to properly fixing this bug, I think that the conflict set
needs to behave more intelligently. It should not free resources if they are in
use by another row.

This would hopefully solve the a->b, a->c, b->d, c->d graph crash.
Then, applying a patch to turn off remembering the state a->a will work as well.

However, I cannot grok the code for that little AI algorithm dropped in the
middle of mozilla. :-) I do not think I will be able to fix the conflict set
memory problem.

So... Help please! This bug is a show stopper for me and my coworkers.

Comment 18

[Wesley W. Terpstra]

Comment on attachment 106086 [details] [diff] [review]
Enforce the only one path to a resource rule (bad idea)

--- nsXULTreeBuilder.cpp	Wed Nov 13 16:39:55 2002
+++ nsXULTreeBuilder.cpp.only_once	Wed Nov 13 14:23:18 2002
@@ -202,6 +202,12 @@
     IsContainerOpen(nsIRDFResource* aContainer, PRBool* aResult);

     /**
+     * A helper method that determines if the specified container is cyclic.
+     */
+    nsresult
+    IsContainerCyclic(nsIRDFResource* aRoot, nsIRDFResource* aParent,
nsIRDFResource* aChild, PRBool* aResult);
+
+    /**
      * A sorting callback for NS_QuickSort().
      */
     static int PR_CALLBACK
@@ -1637,6 +1643,17 @@
		("xultemplate[%p] %smatch=%p", this, space.get(), match));
 #endif

+	 Value val;
+	 match->GetAssignmentFor(mConflictSet,
+				 match->mRule->GetMemberVariable(),
+				 &val);
+	 
+	 // If this would introduce a cycle, drop it
+	 PRBool isCyclic = PR_FALSE;
+	 IsContainerCyclic(mRows.GetRootResource(), aContainer,
VALUE_TO_IRDFRESOURCE(val), &isCyclic);
+	 if (isCyclic)
+	     continue;
+	 
	 // Remember that this match applied to this row
	 mRows.InsertRowAt(match, aSubtree, count);

@@ -1645,10 +1662,6 @@

	 // If this is open, then remember it so we can recursively add
	 // *its* rows to the tree.
-	 Value val;
-	 match->GetAssignmentFor(mConflictSet,
-				 match->mRule->GetMemberVariable(),
-				 &val);

	 PRBool isOpen = PR_FALSE;
	 IsContainerOpen(VALUE_TO_IRDFRESOURCE(val), &isOpen);
@@ -1819,6 +1832,51 @@
     else
	 *aResult = PR_FALSE;

+    return NS_OK;
+}
+
+nsresult
+nsXULTreeBuilder::IsContainerCyclic(nsIRDFResource* aRoot,
+				     nsIRDFResource* aParent, 
+				     nsIRDFResource* aChild,
+				     PRBool*	     aResult)
+{
+    if (mPersistStateStore)
+    {
+	 nsresult rv;
+	 nsCOMPtr<nsIRDFNode> properParent;
+	 
+	 rv = mPersistStateStore->GetTarget(aChild,
+					    aRoot,
+					    PR_TRUE,
+					    getter_AddRefs(properParent));
+	 if (NS_FAILED(rv) && rv != NS_RDF_NO_VALUE) return rv;
+	 
+	 if (rv == NS_RDF_NO_VALUE || !properParent)
+	 {
+	      rv = mPersistStateStore->Assert(aChild,
+					      aRoot,
+					      aParent,
+					      PR_TRUE);
+	      if (NS_FAILED(rv)) return rv;
+	      *aResult = PR_FALSE;
+	 }
+	 else
+	 {
+	     rv = properParent->EqualsNode(aParent, aResult);
+	     *aResult = !*aResult;
+	     if (NS_FAILED(rv)) return rv;
+	     
+	     if (*aResult == PR_TRUE)
+	     {	 // Give them one more chance to see this node, if it is not
+		 // displayed anywhere else, we can move it.
+		 
+		 // NOT DONE!!!
+	     }
+	 }
+    }
+    else
+	 *aResult = PR_FALSE;
     return NS_OK;
 }

Comment 19

[Chris Waterson]

IIRC, the big problem here is that the rdfliner can't handle two rows with the
same resource. The nsConflictSet hashes RDF resource to row (e.g.,
aMatch->GetAssignmentFor() in nsXULTreeBuilder::SynchronizeMatch), which is a
one-to-one relationship.  So, if you end up with two of the same resource in the
rdfliner, that map returns the wrong thing when you try to access the 2nd
through nth copy of the resource.

So...the bottom line is, even if you fix the cycles, you'll still end up
crashing eventually due to the above problem.  I'd need to get my head back
around this to actually figure out how to fix it properly.

Comment 20

[timeless]

this is the cause of bug 158428 which is a topcrasher. wallpaper is good.

please select a wallpaper and commit it. correct fixes can be done at someone's leisure.

Comment 21

[Jan Varga [:janv]]

Attachment: up to date patch

Comment 22

[Chris Waterson]

Comment on attachment 110780 [details] [diff] [review]
up to date patch

r=waterson

Comment 23

[jag (Peter Annema)]

Comment on attachment 110780 [details] [diff] [review]
up to date patch

sr=jag

Comment 24

[Jan Varga [:janv]]

checked in

Comment 25

[Brant Gurganus]

By the definitions on <http://bugzilla.mozilla.org/bug_status.html#severity> and
<http://bugzilla.mozilla.org/enter_bug.cgi?format=guided>, crashing and dataloss
bugs are of critical or possibly higher severity.  Only changing open bugs to
minimize unnecessary spam.  Keywords to trigger this would be crash, topcrash,
topcrash+, zt4newcrash, dataloss.

Comment 26

[Mats Palmgren (inactive)]

Please file a new bug if there is still something left to do that is still relevant.