More pathological range subtleties

H. S. Teoh hsteoh at quickfur.ath.cx
Tue Feb 12 12:22:05 PST 2013


If you thought transience was bad, you ain't seen nuthin' yet. Check
this one out.

So, what do you think? What is the effect of this function?

	auto fun(RoR)(RoR ror)
		if (isForwardRange!RoR && isInputRange!(ElementType!RoR))
	{
		foreach (ref e; ror)
		{
			if (!e.empty)
				e.popFront();
		}
		return ror;
	}

Which of the following will happen?

1) The result is a range that consists of subranges with one element
less than the original range.

2) The result is an empty range.

3) The result is identical to the original range.

Go on, pick one, before you read on.

I'll wait.

.

.

.

Have you picked one yet?

Alright. Now let's discuss each possibility.

(1) is what happens if RoR == array of arrays. This should be obvious.

How can (2) possibly happen?  Easy:

	class RoR {
		int[][] _src;
		auto front() { return _src.front; }
		bool empty() { return _src.empty; }
		void popFront() { _src = _src[1..$]; }
	}

Remember that classes have reference semantics. Once you iterate over
ror, it's consumed, so it would return an empty range. (But you knew
that. Right ... ?)

Well, given that RoR is a forward range, this problem is relatively easy
to fix: just write "ror.save" in the foreach instead of just "ror".

But there's more. What if RoR is this:

	struct RoR {
		int[] _src;
		auto front() { return _src[0 .. min(5, $)]; }
		bool empty() { return _src.empty; }
		void popFront() { _src = _src[0 .. min(5, $)]; }
	}

Note that .front returns a slice of _src. But this slice is constructed
*each time* you call .front. Which means the slice that fun called
.popFront on has no effect on the range at all. So fun will return the
original range in this case -- this is case (3).

Isn't fun wonderfully generic? It's so generic, that (1), (2), and (3)
are all possible outcomes, and you've no way to tell beforehand! Isn't
that fun? (Pun fully intended.)

This is the root cause of:
	http://d.puremagic.com/issues/show_bug.cgi?id=8764

Exercise for the reader: how would you modify fun so that the intended
result, (1), will actually happen in all cases? (2) is easy to eliminate
with .save, but I see no way of preventing (3).


T

-- 
You have to expect the unexpected. -- RL


More information about the Digitalmars-d mailing list