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
next sibling parent reply "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
parent reply 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
parent reply "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
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 parent reply "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
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
next sibling 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 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 reply "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
parent reply 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
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