www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Iterating over 0..T.max

reply Magnus Lie Hetland <magnus hetland.org> writes:
In a (template) data structure I'm working on, I had the following thinko:

    auto a = new T[n];
    foreach (T i, ref e; a) {
        e = i;
    }

Then I instantiated it with T=bool, and n=256. Infinite loop, of course 
-- the problem being that i wraps around to 0 after the last iteration. 
Easily fixed, and not that much of a problem (given that I caught it) 
-- I'll just use e = cast(T) i. (Of course, even with that solution, 
I'd get wrap problems if n=257, but I just want to make sure I allow 
T.max as a size.)

But I'm wondering: given D's excellent valua range propagations and 
overflow checking, would it be possible to catch this special case 
(i.e., detect when the array can be too long for the index type)? Or 
are any other safeguards possible to prevent this sort of thing?

-- 
Magnus Lie Hetland
http://hetland.org
Mar 09 2011
parent reply Kai Meyer <kai unixlords.com> writes:
On 03/09/2011 09:09 AM, Magnus Lie Hetland wrote:
 In a (template) data structure I'm working on, I had the following thinko:

 auto a = new T[n];
 foreach (T i, ref e; a) {
 e = i;
 }

 Then I instantiated it with T=bool, and n=256. Infinite loop, of course
 -- the problem being that i wraps around to 0 after the last iteration.
 Easily fixed, and not that much of a problem (given that I caught it) --
 I'll just use e = cast(T) i. (Of course, even with that solution, I'd
 get wrap problems if n=257, but I just want to make sure I allow T.max
 as a size.)

 But I'm wondering: given D's excellent valua range propagations and
 overflow checking, would it be possible to catch this special case
 (i.e., detect when the array can be too long for the index type)? Or are
 any other safeguards possible to prevent this sort of thing?
I don't see how that works in dmd2, and I don't have much experience with dmd1, so I'll admit that this may be different on dmd1. I get compilation errors with your code: import std.stdio; void main() { make_new!(bool)(256); } void make_new(T)(size_t n) { auto a = new T[n]; foreach (T i, ref e; a) { e = i; } } This gives me: tmax.d(12): Error: operation not allowed on bool 'i' tmax.d(5): Error: template instance tmax.make_new!(bool) error instantiating As far as I understand, a foreach over an array makes the first value (i) a uint for the index, and the second value (e) a copy of the value in the array (in our case a bool). import std.stdio; void main() { make_new!(bool)(1); } void make_new(T)(size_t n) { auto a = new T[n]; writef("%s\n", typeof(a).stringof); foreach (i,e; a) { writef("%s\n", typeof(i).stringof); writef("%s\n", typeof(e).stringof); } } /* Output: bool[] uint bool */ But to the question about boundaries, 'i' is a uint (size_t), and on a 4GB machine, I can't call "auto a = new bool[size_t.max];". The program segfaults. size_t.max / 2 for a size gives me "Memory allocation failed". size_t.max / 4 works fine. I'm not sure how to get a program to do what you describe.
Mar 09 2011
parent reply Magnus Lie Hetland <magnus hetland.org> writes:
On 2011-03-09 21:24:57 +0100, Kai Meyer said:

 I don't see how that works in dmd2, and I don't have much experience 
 with dmd1, so I'll admit that this may be different on dmd1.
Derp. I didn't mean bool -- I was talking about byte. (Which should make quite a bit more sense, given that I'm talking about a limit of 256... :D) And, for the record, I'm using DMD 2.052 (OS X). Just replace bool with byte in your program, and it should compile. Sorry for the brain fart ;) -- Magnus Lie Hetland http://hetland.org
Mar 10 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Magnus Lie Hetland:

 Derp. I didn't mean bool -- I was talking about byte. (Which should 
 make quite a bit more sense, given that I'm talking about a limit of 
 256... :D)
Please show a complete minimal program that gives you problem. (I have failed to reproduce your problem on Windows). Bye, bearophile
Mar 10 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 10 Mar 2011 07:50:21 -0500, bearophile <bearophileHUGS lycos.com>  
wrote:

 Magnus Lie Hetland:

 Derp. I didn't mean bool -- I was talking about byte. (Which should
 make quite a bit more sense, given that I'm talking about a limit of
 256... :D)
Please show a complete minimal program that gives you problem. (I have failed to reproduce your problem on Windows).
void main() { auto a = new ubyte[256]; foreach(ubyte i, ref e; a) e = i; } I think you should file this as a bug Magnus, I see no reason why this should result in an infinite loop. Probably the reason is because the compiler rewrites this as: for(ubyte i = 0; i < a.length; i++) where what it should do is: for(size_t _i = 0; _i < a.length; _i++) { auto i = cast(ubyte) _i; ... } or just fail to compile if you use anything that can't hold a size_t as an index type. -Steve
Mar 10 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Steven Schveighoffer:

 void main()
 {
      auto a = new ubyte[256];
      foreach(ubyte i, ref e; a) e = i;
 }
http://d.puremagic.com/issues/show_bug.cgi?id=5725 Bye, bearophile
Mar 10 2011