Jump to page: 1 2
Thread overview
DMD Bug or not? foreach over struct range
May 16, 2012
Nick Sabalausky
May 16, 2012
Jonathan M Davis
May 16, 2012
Era Scarecrow
May 16, 2012
Jonathan M Davis
May 16, 2012
Era Scarecrow
May 16, 2012
Jonathan M Davis
May 16, 2012
Nick Sabalausky
May 16, 2012
Jonathan M Davis
May 16, 2012
Nick Sabalausky
May 16, 2012
Nick Sabalausky
May 16, 2012
Era Scarecrow
May 16, 2012
bearophile
May 16, 2012
Jonathan M Davis
May 16, 2012
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 16, 2012
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
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
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
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
"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
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
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
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
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
« First   ‹ Prev
1 2