| |
 | Posted by monarch_dodra
in reply to H. S. Teoh |  Permalink Reply |
|
monarch_dodra 
Posted in reply to H. S. Teoh
| 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" ® .
|
