www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - DMD Bug or not? foreach over struct range

reply "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
This code:

------------------------------------------
import std.stdio;

struct Foo
{
    int val;

     property bool empty() {
        return val >= 5;
    }

     property int front() {
        return val;
    }

    void popFront() {
        val++;
    }
}

void main()
{
    Foo foo;
    foreach(val; foo)
        writeln(foo.val, " ", val);
}

------------------------------------------

Expected output:
0 0
1 1
2 2
3 3
4 4

Actual output:
0 0
0 1
0 2
0 3
0 4

It seems that foreach is iterating over an implicit copy of 'foo' instead of 
'foo' itself. Is this correct behavior, or a DMD bug?
May 15 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, May 16, 2012 02:43:19 Nick Sabalausky wrote:
 This code:
 
 ------------------------------------------
 import std.stdio;
 
 struct Foo
 {
     int val;
 
      property bool empty() {
         return val >= 5;
     }
 
      property int front() {
         return val;
     }
 
     void popFront() {
         val++;
     }
 }
 
 void main()
 {
     Foo foo;
     foreach(val; foo)
         writeln(foo.val, " ", val);
 }
 
 ------------------------------------------
 
 Expected output:
 0 0
 1 1
 2 2
 3 3
 4 4
 
 Actual output:
 0 0
 0 1
 0 2
 0 3
 0 4
 
 It seems that foreach is iterating over an implicit copy of 'foo' instead of
 'foo' itself. Is this correct behavior, or a DMD bug?

No. That's expected. Your range is a value type, so it got copied when you used it with foreach. Otherwise, if you did Foo foo foreach(val; foo) {} assert(foo.empty); that assertion would pass, but it doesn't, and it shouldn't. If your range was a reference type (e.g. if it were a class or it was like the ranges in std.stdio which deal with I/O), then using it with foreach would consume it, but that won't happen with a value type range. - Jonathan M Davis
May 16 2012
parent "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
"Jonathan M Davis" <jmdavisProg gmx.com> wrote in message 
news:mailman.826.1337151940.24740.digitalmars-d-learn puremagic.com...
 No. That's expected. Your range is a value type, so it got copied when you
 used it with foreach.

But foreach isn't a function, it's a flow-control statement.
May 16 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Nick Sabalausky:

 It seems that foreach is iterating over an implicit copy of 
 'foo' instead of
 'foo' itself. Is this correct behavior, or a DMD bug?

This program prints "[11, 21, 31]" so for fixed-size arrays (that are values as much as structs) it doesn't perform a copy: import std.stdio; void main() { int[3] a = [10, 20, 30]; foreach (ref x; a) x++; writeln(a); } Bye, bearophile
May 16 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, May 16, 2012 09:15:06 bearophile wrote:
 Nick Sabalausky:
 It seems that foreach is iterating over an implicit copy of
 'foo' instead of
 'foo' itself. Is this correct behavior, or a DMD bug?

This program prints "[11, 21, 31]" so for fixed-size arrays (that are values as much as structs) it doesn't perform a copy: import std.stdio; void main() { int[3] a = [10, 20, 30]; foreach (ref x; a) x++; writeln(a); }

It probably slices the array, which would mean that it was operating on a dynamic array rather than a static one. But it could just generate different code for static arrays. - Jonathan M Davis
May 16 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Wednesday, 16 May 2012 at 07:04:09 UTC, Jonathan M Davis wrote:
 that assertion would pass, but it doesn't, and it shouldn't. If 
 your range was a reference type (e.g. if it were a class or it 
 was like the ranges in std.stdio which deal with I/O), then 
 using it with foreach would consume it, but that won't happen 
 with a value type range.

Then perhaps I'm missing something. Some time ago (6 months?) I submitted a similar example of this to walter; a little prime walking range-like struct that acts like a range. It may contain an AA, but otherwise basic structure isn't far from his... Could you explain why mine works and his doesn't? (Extras taken out proving ever number is a prime) --- import std.stdio; struct prime_walk { int map[int]; int position = 2; int cap = int.max; int front() { return position; } void popFront() { //where the real work is done. if ((position & 1) == 0) { position++; } else if (position >= cap) { throw new Exception("Out of bounds!"); } else { int div = position; int p2 = position * 3; //current spot IS a prime. So... if (p2 < cap) map[p2] = div; position += 2; //identify marked spot, if so we loop again. while (position in map) { div = map[position]; map.remove(position); p2 = position; do p2 += div * 2; while (p2 in map); position += 2; if (p2 <= cap) //skip out, no need to save larger than needed values. map[p2] = div; } } } bool empty() { return position >= cap; } } void main() { prime_walk pw; pw.cap = 100; foreach(i; pw) writeln(i); }
May 16 2012
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, May 16, 2012 03:29:23 Nick Sabalausky wrote:
 "Jonathan M Davis" <jmdavisProg gmx.com> wrote in message
 news:mailman.826.1337151940.24740.digitalmars-d-learn puremagic.com...
 
 No. That's expected. Your range is a value type, so it got copied when you
 used it with foreach.

But foreach isn't a function, it's a flow-control statement.

If it _wasn't_ copied, using foreach would consume your range. It doesn't, and it would really suck if it did. But foreach(e; range) {} pretty has to be translated to something similar to for(auto r = range; !r.empty(); r.popFront()) { auto e = r.front; } And actually, looking at TDPL (p. 381), that's pretty much _exactly_ what it gets translated to (save for the exact variable names used). - Jonathan M Davis
May 16 2012
parent reply "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
"Jonathan M Davis" <jmdavisProg gmx.com> wrote in message 
news:mailman.828.1337154007.24740.digitalmars-d-learn puremagic.com...
 On Wednesday, May 16, 2012 03:29:23 Nick Sabalausky wrote:
 "Jonathan M Davis" <jmdavisProg gmx.com> wrote in message
 news:mailman.826.1337151940.24740.digitalmars-d-learn puremagic.com...

 No. That's expected. Your range is a value type, so it got copied when 
 you
 used it with foreach.

But foreach isn't a function, it's a flow-control statement.

If it _wasn't_ copied, using foreach would consume your range.

Iterating a range normally *does* consume it. And that's expected, as it should be: Imagine, for example, an input range that read from stdin. Leaving that range unconsumed would make no sense at all. Actually any input range can be expected to *not* leave an uniterated copy: if it *could* have an uniterated copy left behind, it would be a forward range, not an input range.
 It doesn't, and it would really suck if it did.

Like I said above, it would suck if you use the current foreach over an input range: Sometimes it might work by pure luck (as in the original example), but you can expect that for some input ranges it would fail miserably, because an input range is *not* a forward range and by definition cannot reliably save a previous state. Additionally, if you wanted to still have an un-iterated version (of an actual foreard range, or an input range that you knew to be safe), then that's trivial: Foo a; b = a.save(); // Or "b = a;" if you really know what you're doing. foreach(elem; a) {} assert(a.empty); assert(!b.empty); Note, however, that there is no such simple way to go the other way around: to have the current "foreach over a copy" behavior and have access to the actual iterated range. Maybe if we had "foreach(e; ref range)", but AFAIK we don't. Maybe it's just me, but I'd intuitively expect foreach over a range to work like this: Range range; foreach(e; range) {...} --> Range range; for(; !range.empty(); range.popFront()) { auto e = range.front; ... } I was initially open to the idea I may have just misunderstood something, but I'm becoming more and more convinced that the current "foreach over an implicit copy" behavior is indeed a bad idea. I'd love to see Andrei weigh in on this. I'm curious if the example you pointed out in TDPL made the copy deliberately, or if the effects of that copy were just an oversight.
May 16 2012
parent "Nick Sabalausky" <SeeWebsiteToContactMe semitwist.com> writes:
Actually, I think I'm going to move this over to "digitalmars.D". Seems a 
more appropriate place at this point. 
May 16 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, May 16, 2012 09:24:23 Era Scarecrow wrote:
 On Wednesday, 16 May 2012 at 07:04:09 UTC, Jonathan M Davis wrote:
 that assertion would pass, but it doesn't, and it shouldn't. If
 your range was a reference type (e.g. if it were a class or it
 was like the ranges in std.stdio which deal with I/O), then
 using it with foreach would consume it, but that won't happen
 with a value type range.

Then perhaps I'm missing something. Some time ago (6 months?) I submitted a similar example of this to walter; a little prime walking range-like struct that acts like a range. It may contain an AA, but otherwise basic structure isn't far from his... Could you explain why mine works and his doesn't? (Extras taken out proving ever number is a prime) --- import std.stdio; struct prime_walk { int map[int]; int position = 2; int cap = int.max; int front() { return position; } void popFront() { //where the real work is done. if ((position & 1) == 0) { position++; } else if (position >= cap) { throw new Exception("Out of bounds!"); } else { int div = position; int p2 = position * 3; //current spot IS a prime. So... if (p2 < cap) map[p2] = div; position += 2; //identify marked spot, if so we loop again. while (position in map) { div = map[position]; map.remove(position); p2 = position; do p2 += div * 2; while (p2 in map); position += 2; if (p2 <= cap) //skip out, no need to save larger than needed values. map[p2] = div; } } } bool empty() { return position >= cap; } } void main() { prime_walk pw; pw.cap = 100; foreach(i; pw) writeln(i); }

I'm not quite sure what yours is doing, but yours isn't empty after the call to foreach any more than Nick's is. The issue with Nick's is that he's using the original range _inside_ the loop and not seeing the changes. Your loop isn't referencing the original range. It just uses its copy. If you did void main() { prime_walk pw; pw.cap = 100; foreach(i; pw) writefln("%s %s", i, pw.position); } You'd see that pw.postion is always printed as 2, just like Nick's foo.val always prints as 0. - Jonathan M Davis
May 16 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Wednesday, 16 May 2012 at 07:41:14 UTC, Jonathan M Davis wrote:
 void main()
 {
     prime_walk pw;
     pw.cap = 100;
     foreach(i; pw)
         writefln("%s %s", i, pw.position);
 }

 You'd see that pw.postion is always printed as 2, just like 
 Nick's foo.val
 always prints as 0.

Hmmm... [quote] void main() { Foo foo; foreach(val; foo) writeln(foo.val, " ", val); } [/quote] Indeed... he is using foo.val isn't he? Instead he should just use 'val' by itself. Quick overview, my little prime walker is dropping the requirement of checking for if a number is prime by only going up and being on valid prime numbers. Each time the old prime is used it's stepped up in the array (and can't step on another used element), this removes your 'is this a prime' down to basically O(1). You can't ask randomly is x a prime, but if you needed a range of primes you can get quite a large list very quickly. Half of it is there for optimization purposes.
May 16 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, May 16, 2012 09:48:20 Era Scarecrow wrote:
   Hmmm...
 [quote]
 void main()
 {
     Foo foo;
     foreach(val; foo)
         writeln(foo.val, " ", val);
 }
 [/quote]
 
   Indeed...  he is using foo.val isn't he? Instead he should just
 use 'val' by itself.

Well, there's nothing wrong with it as long as you know what it's doing and that behavior is what you want. The problem is when you expect it to be doing something else than what it is, and I suspect that what he provided was just an example and that whatever he was doing in actual code when he ran into the problem wasn't quite as obvious as that. - Jonathan M Davis
May 16 2012
prev sibling next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Wednesday, 16 May 2012 at 20:50:55 UTC, Nick Sabalausky wrote:

 I was initially open to the idea I may have just misunderstood 
 something, but I'm becoming more and more convinced that the 
 current "foreach over an implicit copy" behavior is indeed a 
 bad idea.

 I'd love to see Andrei weigh in on this. I'm curious if the 
 example you pointed out in TDPL made the copy deliberately, or 
 if the effects of that copy were just an oversight.

I remember going over hard and long over that section. I think it's deliberate. Range can refer to many things, and I'm assuming array is one of them. So... If the array is consumed when using foreach, that seems dump right? (An array in the end is just a small struct afterall...) --- int[] x = [1,2,3]; foreach(i; x) { //stuff } assert(x.length == 0, "Should have been consumed!"); --- Structs being value types are by value and so are copied, not referenced. Although referencing a copy does seem a bit silly... int[] x = [1,2,3]; foreach(ref i; x) { i = 10; } assert(x == [10,10,10], "But i changed them to 10!!"); -- That means that foreach(ref; ref) if it's considered (And I think it makes sense to) would work for structs in these few cases. (Course you'd still consume dynamic arrays that way) Something stream based as I've seen in std.stream are classes, so they are consumed. I'm probably just rambling...
May 16 2012
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 16 May 2012 03:20:39 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Wednesday, May 16, 2012 09:15:06 bearophile wrote:
 Nick Sabalausky:
 It seems that foreach is iterating over an implicit copy of
 'foo' instead of
 'foo' itself. Is this correct behavior, or a DMD bug?

This program prints "[11, 21, 31]" so for fixed-size arrays (that are values as much as structs) it doesn't perform a copy: import std.stdio; void main() { int[3] a = [10, 20, 30]; foreach (ref x; a) x++; writeln(a); }

It probably slices the array, which would mean that it was operating on a dynamic array rather than a static one. But it could just generate different code for static arrays.

foreach does *not* use range primitives for arrays, they are special. -Steve
May 17 2012