• H. S. Teoh (55/55) Oct 15 2012 Thanks to an idea by Andrei, I now have an implementation of the
• Andrei Alexandrescu (6/12) Oct 17 2012 [snip]

"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:

Thanks to an idea by Andrei, I now have an implementation of the
Cartesian product of two infinite ranges that requires only forward
ranges.

However, I'm running into an array-out-of-bounds problem with
std.algorithm.joiner, and I don't know how to reduce the code to track
down the problem. Here's the code:

	import std.algorithm;
	import std.range;
	import std.stdio;

	// Cartesian product of two infinite ranges (this is a testing
	// version, so I left out the template constraints; it's
	// supposed to ensure R1 and R2 are infinite forward ranges)
	auto cprod(R1,R2)(R1 A, R2 B) {
	    // Behold the awesomeness of D functional programming!
	    return zip(sequence!"n"(cast(size_t)0), A.save, B.save)
		.map!((a) => chain(
		    zip(repeat(a[1]), B.save.take(a[0])),
		    zip(A.save.take(a[0]+1), repeat(a[2]))
		))

		// Or not... the following line causes problems
		.joiner;
	}

	void main() {
	    auto A = sequence!"n+100"(0);
	    auto B = sequence!"n+200"(0);

	    // This *should* produce 25 elements of the Cartesian
	    // product... but the .joiner bug introduces foreign
	    // elements into the result.
	    writeln(cprod(A,B)
		.map!"[a[0],a[1]]"
		.take(25)
	    );
	}

The output is:

	[[100, 200], [101, 200], [25, 201], [102, 201], [102, 200], [102, 202], [25,
202], [102, 202], [103, 202], [103, 200], [103, 202], [103, 203], [25, 203],
[102, 203], [103, 203], [104, 203], [104, 200], [104, 202], [104, 203], [104,
204], [25, 204], [102, 204], [103, 204], [104, 204], [105, 204]]

Now take note: neither A nor B have an element "25", yet it shows up
repeatedly in the output. In fact, if you change the line that reads
".take(25)" to something else, say ".take(15)", all occurrences of "25"
in the output will turn into 15. This means that joiner() is returning
slices that overrun the original range(s). :-(

Commenting out the ".joiner" line fixes the problem, except that the
resulting Cartesian product is nested one level inside an array. The
.joiner call was supposed to flatten the segments of the product into a
flat range, but due to the array overrun bug, the wrong result is
produced.

This being an array overrun bug, YMMV. In my other test suite (which
contains a bunch of other code), a runtime exception is thrown, so you
may or may not see the "25" shown above.

Any help in locating the bug in .joiner would be greatly appreciated.
I've tried to simplify the above code in various ways but the buggy
behaviour is sporadic and seems to change depending on minute code
details, so it's kinda annoying to track down.


T

-- 
One disk to rule them all, One disk to find them. One disk to bring them all
and in the darkness grind them. In the Land of Redmond where the shadows lie.
-- The Silicon Valley Tarot

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 10/15/12 8:46 PM, H. S. Teoh wrote:
 Thanks to an idea by Andrei, I now have an implementation of the
 Cartesian product of two infinite ranges that requires only forward
 ranges.

 However, I'm running into an array-out-of-bounds problem with
 std.algorithm.joiner, and I don't know how to reduce the code to track
 down the problem. Here's the code:

[snip]

I'm traveling with little time to spare, but one visible thing is that 
the limit of the iteration (25) spills into the result. May be easiest 
to track things starting from that observation.

Andrei