[gecode-users] Bug in TupleSet?

[Christian Schulte]

Dear Michal,

Thanks so far for your input, I'll have a closer look at all of this as I
find time (I am travelling today).

Cheers
Christian

--
Christian Schulte, www.it.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Michal D.
Sent: Tuesday, December 16, 2008 6:17 AM
To: users at gecode.org
Subject: Re: [gecode-users] Bug in TupleSet?

> 
> There seems to be a bug in TupleSet. If you add a particular tuple  
> more than twice, the next call to extensional will segfault. Eg:
> 
> 	TupleSet tuples;
> 
> 	int n = 3;		// works if n <= 2
> 
> 	for (int i = 0; i < n; i++) {
> 		IntArgs pair(2);
> 		pair[0] = 0;
> 		pair[1] = 1;
> 
> 		tuples.add(pair);
> 	}
> 
> 	TestSpace* space = new TestSpace();
> 
> 	IntVarArray x(space, 2, 0, 1);
> 	space->add(x);
> 
> 	extensional(space, x, tuples);	// segfault if n >= 3
> 
> (where TestSpace is a simple Space implementation)
> 
> GDB shows:
> 
> Program received signal EXC_BAD_ACCESS, Could not access memory.
> Reason: KERN_PROTECTION_FAILURE at address: 0x00000000
> 0x0057f857 in (anonymous namespace)::FullTupleCompare::operator() ()  
> at gecode/int/extensional/tuple-set.cc:55
> 55              if (a[i] < b[i]) {
> 
> Malcolm
> 

I just noticed this message, and it's the exact same problem I was having
(see http://article.gmane.org/gmane.comp.lib.gecode.user/2053). Just for
reference: extensional() calls tupleSet::finalize() which calls quicksort()
on the tuples and eventually produces this seg fault. I confirmed that with
duplicates removed quicksort() terminates using the "<=" comparison and a
stack depth of 32 for my data. However, this does not clear the use of "<="
comparisons in quicksort (see the other thread).

Sorry for spamming everyone with all these posts but hopefully we're making
progress. I do have two actual questions:

1) Is a tupleSet shared if it is used as part of multiple extensional()
constraints?

2) Do the unneeded tuples in a given extensional() constraint get discarded
at
some point? Ie. is it ok to have extra values that will be dropped on the
first
propagation or will they stay on as runtime overhead forever?

Thanks,

Michal



_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users