More pathological range subtleties

monarch_dodra monarchdodra at gmail.com
Tue Feb 12 12:52:48 PST 2013


On Tuesday, 12 February 2013 at 20:24:08 UTC, H. S. Teoh wrote:
> 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

First: when foreach failed to call "save", it started down the 
wrong path. If you plan to re-use your range, you *must* call 
save. Let's try again with this:

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

At this point, I'll argue that the only *legal* outcome is (1). 
Why? Because you asked for a "ref e", yet in your examples, your 
ranges did not yield references. This is a bug with the language, 
and the reason you are getting a strange behavior. From there, 
bad things are bound to happen.

The foreach should *not* have legally compiled. That's why we 
usually avoid it in std.algorithm.

So if we try to avoid the foreach bug, and switch it back to a 
for loop.

//----
	auto fun(RoR)(RoR ror)
		if (isForwardRange!RoR && isInputRange!(ElementType!RoR))
	{
		auto bck = ror.save;
		for ( ; !ror.empty ; ror.popFront())
		{
			e = ror.front;
			if (!e.empty)
			{
				e.popFront();
				ror.front = e;
			}
		}
		return bck;
	}
//----

Now, once you have written this code, the only way it could break 
is if RoR is an assignable forward transient range, that sends to 
the trash what is assigned to it. Which would be a violation of 
its own interface, so "not out problem" ® .


More information about the Digitalmars-d mailing list