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 reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 12, 2013 at 09:29:57PM +0100, Benjamin Thaut wrote:

 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?


[...]

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

-- 
He who sacrifices functionality for ease of use, loses both and deserves
neither. -- Slashdotter
Feb 12 2013
next sibling 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 Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Tue, 12 Feb 2013 12:43:54 -0800
"H. S. Teoh" <hsteoh quickfur.ath.cx> wrote:


 He who sacrifices functionality for ease of use, loses both and
 deserves neither. -- Slashdotter


I can't sufficiently describe how much I love that quote.
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 reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 12, 2013 at 09:52:48PM +0100, monarch_dodra wrote:
[...]

 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:


Yes, a frightening amount of Phobos code suffers from this problem.



 //----
 	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.


I've always felt uneasy about the way D handles ref's in foreach loops.
It feels like it was a good idea that was carried over from D1, but
didn't get implemented thoroughly enough to handle the new stuff in D2.
Forcing opApply to *always* take a delegate with ref arguments is one
indication of the deeper problem. This makes it so that the container
can't customize its behaviour for the ref case and for the non-ref case,
and this conflation leads to problems down the road (like people just
passing a ref to a temporary variable when they want foreach loops to
not change the contained elements, which leads to bugs 'cos the person
writing the foreach loop thought things were being updated but they
actually aren't).

But anyway. That's a different issue from the one at hand.



 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" ® .


This code still doesn't work with the second RoR candidate I gave,
because .front always returns a fresh slice of the underlying array. The
thing is, the original range simply does not keep track of its
subranges, because they are conceptual, there's no actual storage where
they are kept.

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.


T

-- 
Mediocrity has been pushed to extremes.
Feb 12 2013
next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Tue, 12 Feb 2013 13:09:33 -0800
schrieb "H. S. Teoh" <hsteoh quickfur.ath.cx>:


 I've always felt uneasy about the way D handles ref's in foreach loops.
 It feels like it was a good idea that was carried over from D1, but
 didn't get implemented thoroughly enough to handle the new stuff in D2.
 Forcing opApply to *always* take a delegate with ref arguments is one
 indication of the deeper problem. This makes it so that the container
 can't customize its behaviour for the ref case and for the non-ref case,
 and this conflation leads to problems down the road (like people just
 passing a ref to a temporary variable when they want foreach loops to
 not change the contained elements, which leads to bugs 'cos the person
 writing the foreach loop thought things were being updated but they
 actually aren't).


Oh man, I just wrote such code today...

-- 
Marco
Feb 12 2013
prev sibling parent reply 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
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 12, 2013 at 05:45:45PM -0500, Andrei Alexandrescu wrote:

 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?


[...]

It has been, for a while. Though it's non-obvious from the bug
description:

	http://d.puremagic.com/issues/show_bug.cgi?id=8764

I'm thinking that the fix should simply make it illegal to pass Chunks
to transposed, so it will force the user to call array() which avoids
the bug.


T

-- 
Talk is cheap. Whining is actually free. -- Lars Wirzenius
Feb 12 2013
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 12, 2013 at 05:45:45PM -0500, Andrei Alexandrescu wrote:

 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?


[...]

P.S.: https://github.com/D-Programming-Language/phobos/pull/1138


T

-- 
Debian GNU/Linux: Cray on your desktop.
Feb 12 2013