www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Is this a bug? RandomSample claims it needs input range but actually

reply "finalpatch" <fengli gmail.com> writes:
in the declaration of RandomSample it only checks for 
isInputRange, but in the implementation it calls the .save() 
method which is only available in forward ranges.

as a result this code does not compile:

void main()
{
	auto a = File("test.d", "r").byLine();
	auto s = randomSample(a,1,5);
	writeln(s);
}

Is this a bug or I missed something?
Jun 18 2013
next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, June 19, 2013 03:56:43 finalpatch wrote:
 in the declaration of RandomSample it only checks for
 isInputRange, but in the implementation it calls the .save()
 method which is only available in forward ranges.
 
 as a result this code does not compile:
 
 void main()
 {
 auto a = File("test.d", "r").byLine();
 auto s = randomSample(a,1,5);
 writeln(s);
 }
 
 Is this a bug or I missed something?

Any function which uses save requires at least a forward range, and if its template constraint requires only an input range, then its template constraint is wrong. _Any_ function whose template constraint does not actually guarantee that anything that passes the constraint will compile with that function is buggy. - Jonathan M Davis
Jun 18 2013
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 06/19/2013 02:56 AM, finalpatch wrote:
 in the declaration of RandomSample it only checks for isInputRange, but in the
 implementation it calls the .save() method which is only available in forward
 ranges.

What compiler and version are you using? This was reported here: http://d.puremagic.com/issues/show_bug.cgi?id=10265 ... and fixed in this pull request: https://github.com/D-Programming-Language/phobos/pull/1332
Jun 18 2013
prev sibling next sibling parent "finalpatch" <fengli gmail.com> writes:
On Wednesday, 19 June 2013 at 02:32:46 UTC, Jonathan M Davis 
wrote:
 On Wednesday, June 19, 2013 03:56:43 finalpatch wrote:
 in the declaration of RandomSample it only checks for
 isInputRange, but in the implementation it calls the .save()
 method which is only available in forward ranges.
 
 as a result this code does not compile:
 
 void main()
 {
 auto a = File("test.d", "r").byLine();
 auto s = randomSample(a,1,5);
 writeln(s);
 }
 
 Is this a bug or I missed something?

Any function which uses save requires at least a forward range, and if its template constraint requires only an input range, then its template constraint is wrong. _Any_ function whose template constraint does not actually guarantee that anything that passes the constraint will compile with that function is buggy. - Jonathan M Davis

So you are saying this is a bug in std.random?
Jun 18 2013
prev sibling next sibling parent "finalpatch" <fengli gmail.com> writes:
On Wednesday, 19 June 2013 at 03:46:11 UTC, Joseph Rushton 
Wakeling wrote:
 On 06/19/2013 02:56 AM, finalpatch wrote:
 in the declaration of RandomSample it only checks for 
 isInputRange, but in the
 implementation it calls the .save() method which is only 
 available in forward
 ranges.

What compiler and version are you using? This was reported here: http://d.puremagic.com/issues/show_bug.cgi?id=10265 ... and fixed in this pull request: https://github.com/D-Programming-Language/phobos/pull/1332

I was testing with DMD 2.063
Jun 18 2013
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 06/19/2013 04:49 AM, finalpatch wrote:
 I was testing with DMD 2.063

Try the very latest, 2.063.2 ... ? 2.063 was released on 28 May, my fix got committed on 7 June.
Jun 18 2013
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 06/19/2013 03:32 AM, Jonathan M Davis wrote:
 Any function which uses save requires at least a forward range, and if its 
 template constraint requires only an input range, then its template constraint 
 is wrong. _Any_ function whose template constraint does not actually guarantee 
 that anything that passes the constraint will compile with that function is 
 buggy.

It was a failure of testing. Doing a bit of git archaeology, it looks like the save function was introduced first, then the isInputRange template constraints, but as the unittests all involved arrays as sample input, the clash with .save was never spotted. Since most of the practical use cases for randomSample involve sampling either from an array or from a forward range like iota, it obviously didn't get spotted "in the wild" either. The annoying thing is that when I first started using randomSample over a year ago, I _must_ have encountered this bug, because I wrote code trying to sample from file.byLine -- the trouble is, at the time, I didn't understand the range concept very well and so didn't realize the compilation error was the sign of a bug, I just rewrote my code to read the file into an array of strings and sample that. (Kids, let this be a lesson -- always ask when your code won't compile and you don't understand the error message.) It was just coincidence that last month I was discussing randomSample on D.learn and wanted to present an example of its flexibility, so revisited the idea of sampling from file.byLine and (this time) realized it shouldn't fail to compile. Incidentally, sampling from .byLine carries a certain cost. The algorithm used in RandomSample is designed to sample n items from N in O(n) time and generating O(n) random variates (i.e. scaling with sample size). However, that relies on the fact that one can .popFrontN(s) or .popFrontExactly(s) the input range in O(1) time. With .byLine it's O(s) and so the overall complexity of the algorithm becomes O(N), that is, scaling with input size.
Jun 18 2013
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, June 19, 2013 05:48:13 finalpatch wrote:
 So you are saying this is a bug in std.random?

Yes. - Jonathan M Davis
Jun 18 2013
prev sibling parent finalpatch <fengli gmail.com> writes:
Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:

 On 06/19/2013 04:49 AM, finalpatch wrote:
 I was testing with DMD 2.063

Try the very latest, 2.063.2 ... ? 2.063 was released on 28 May, my fix got committed on 7 June.

2.063.2 has the same bug. But good to know it's fixed in git master. -- finalpatch
Jun 19 2013