www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - More pathological range subtleties

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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
Feb 12 2013
next sibling parent reply Benjamin Thaut <code benjamin-thaut.de> writes:
Am 12.02.2013 21:22, schrieb H. S. Teoh:
 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).

But fun never calls front, fun calls popFront and popFront does indeed change the internal slice? Kind Regards Benjamin Thaut
Feb 12 2013
parent Benjamin Thaut <code benjamin-thaut.de> writes:
Am 12.02.2013 21:43, schrieb H. S. Teoh:

 There are two levels of ranges going on here. The outer range's .front
 is what gets assigned to ref e, and when you call e.popFront, it indeed
 changes the slice returned by the outer range's .front. However, the
 problem is that the outer range's .front *always* creates a new slice of
 the underlying array, and it never keeps track of older slices. So no
 matter what you do with the slice returned by .front, it doesn't change
 the outer range at all, and .front will continue to return a slice over
 the same elements -- the e.popFront has no effect on it.


 T

Yeah your right, didn't see that. Kind Regards Benjamin Thaut
Feb 12 2013
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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" ® .
Feb 12 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/12/13 4:09 PM, H. S. Teoh wrote:
 But at least, this code should refuse to compile when you try to assign
 ror.front = e (because .front is non-ref). I guess this is better than
 nothing.

Yah, that's a major one. Has this been filed yet? Andrei
Feb 12 2013