• H. S. Teoh (53/53) Oct 16 2012 In the course of digging deeper into why the new Cartesian product

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

In the course of digging deeper into why the new Cartesian product
implementation is triggering buggy behaviour, I found this:

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

	auto cprod(R1,R2)(R1 A, R2 B) {
		// This part is exactly the same as in main(), below. So
		// in theory, it should work exactly the same way.
		auto r = 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]))
			))
			.joiner;

		// But something goes wrong here: is it because the
		// above composed ranges are stack-allocated temporaries
		// that go out of scope upon return?
		return r;
	}

	void main() {
		// Two ranges to test with
		auto A = sequence!"100+2*n"(cast(size_t)0);
		auto B = sequence!"200+2*n+1"(cast(size_t)0);

		// This code is exactly the same as the code in cprod().
		auto r = 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]))
			))
			.joiner;

		// This works correctly
		writeln(r.map!"[a[0],a[1]]".take(20));

		writeln("====");

		// But this is garbled. Why?
		writeln(cprod(A,B).map!"[a[0],a[1]]".take(20));
	}

FWIW, here is the output from my machine:

[[100, 201], [102, 201], [100, 203], [102, 203], [104, 201], [104, 203], [100,
205], [102, 205], [104, 205], [106, 201], [106, 203], [106, 205], [100, 207],
[102, 207], [104, 207], [106, 207], [108, 201], [108, 203], [108, 205], [108,
207]]
====
[[100, 201], [102, 201], [20, 203], [104, 203], [104, 201], [104, 205], [20,
205], [104, 205], [106, 205], [106, 201], [106, 205], [106, 207], [20, 207],
[104, 207], [106, 207], [108, 207], [108, 201], [108, 205], [108, 207], [108,
209]]


Notice in the second output range, that the third element is [20, 203]
instead of [100, 203], and thereafter a bunch of elements are skipped,
and things just start going haywire after that.

The only difference between the two is that the first is computed within
main(), and the second is returned from a function call. Does this mean
that it's unsafe to return composed ranges from functions? I'm trying to
think what might be going wrong. Could it be that the composed ranges
are stack-allocated temporaries that go out of scope upon returning from
the function, so the returned range is actually accessing invalid
memory? (That is a really scary thought.)


T

-- 
Bare foot: (n.) A device for locating thumb tacks on the floor.