www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - oversight with input ranges

reply ketmar <ketmar ketmar.no-ip.org> writes:
here's the interesting oversight for isInputRange:
https://issues.dlang.org/show_bug.cgi?id=3D14478

so be careful: ranges with non-copyable elements aren't input ranges for=20
now. ;-)=
Apr 21 2015
next sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tuesday, April 21, 2015 19:53:47 ketmar via Digitalmars-d wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=14478

 so be careful: ranges with non-copyable elements aren't input ranges for
 now. ;-)
If auto h = r.front; doesn't work, then I don't think that it can be a range. And if that means that elements have to be copyable to be in a range, then I think that they're going to have to be copyable. There is going to be _way_ too much code out there that does auto h = r.front; for it to work to try and claim that something is an input range when that line doesn't work. And IIRC, C++ STL containers require that their elements be copyable in order to work, so it's not like we'd be the first to require this sort of thing. - Jonathan M Davis
Apr 21 2015
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Tue, 21 Apr 2015 15:48:25 -0700, Jonathan M Davis via Digitalmars-d
wrote:

 On Tuesday, April 21, 2015 19:53:47 ketmar via Digitalmars-d wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=3D14478

 so be careful: ranges with non-copyable elements aren't input ranges
 for now. ;-)
=20 If =20 auto h =3D r.front; =20 doesn't work, then I don't think that it can be a range. And if that means that elements have to be copyable to be in a range, then I think that they're going to have to be copyable. There is going to be _way_ too much code out there that does =20 auto h =3D r.front; =20 for it to work to try and claim that something is an input range when that line doesn't work. And IIRC, C++ STL containers require that their elements be copyable in order to work, so it's not like we'd be the first to require this sort of thing.
the thing is that chain, or filter, or other algorithms are perfectly=20 able to work with such ranges, yet it is forbidden now. it looks like=20 arbitrary limitation to me.=
Apr 21 2015
next sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tuesday, April 21, 2015 23:33:38 ketmar via Digitalmars-d wrote:
 On Tue, 21 Apr 2015 15:48:25 -0700, Jonathan M Davis via Digitalmars-d
 wrote:

 On Tuesday, April 21, 2015 19:53:47 ketmar via Digitalmars-d wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=14478

 so be careful: ranges with non-copyable elements aren't input ranges
 for now. ;-)
If auto h = r.front; doesn't work, then I don't think that it can be a range. And if that means that elements have to be copyable to be in a range, then I think that they're going to have to be copyable. There is going to be _way_ too much code out there that does auto h = r.front; for it to work to try and claim that something is an input range when that line doesn't work. And IIRC, C++ STL containers require that their elements be copyable in order to work, so it's not like we'd be the first to require this sort of thing.
the thing is that chain, or filter, or other algorithms are perfectly able to work with such ranges, yet it is forbidden now. it looks like arbitrary limitation to me.
Just because a few algorithms happen to work with non-copyable elements doesn't meant that it works in general. I can understand why you'd want to be able to do it, but not being able to do auto h = r.front; is such a huge limitation that I don't think that it's even vaguely acceptable. I can guarantee that there is a lot of code out there that does it. Just grepping Phobos quickly finds a few cases, let alone digging into all of the code that exists in the wild. If anything, the problem that we've run into is folks who keep front around after popFront has been called (which doesn't always work with input ranges - e.g. byLine), and to do that, you have to be able to copy front, so clearly, folks have been doing that. The definition of input ranges has quite clearly included auto h = r.front; from the very beginning. This isn't new. And given that the C++ STL gets away with its containers not working with non-copyable elements, I think that that proves that you can have a major component in the standard library - containers no less - not support copyable elements and have it work and be acceptable. Also, AFAIK, this is the first time anyone has ever brought up this complaint for D ranges. So, while I'm sure that it's a limitation that might be irritating in some cases, I also think that it's pretty clear that it affects a very small percentage of the users out there. If we were starting over, then maybe we could have something like hasCopyableElements and indicate that range elements aren't guaranteed to be copyable without that, but that would break too much code at this point, and honestly, we have too many traits like that already. Writing fully correct range code that takes into all of the stray cases is ridiculously hard - especially if you try and wrap a range without losing any of its capabilities while wrapped. We really need the common case to be easy, and disallowing copying range elements without testing for that capability first is not user-friendly at all. Even if it were considered more correct from a technical standpoint, folks just wouldn't do it. And since isInputRange has guaranteed that elements have been copyable, I think that it's perfectly reasonable that it's been assumed that they would be, and changing that at this point just isn't worth it. - Jonathan M Davis
Apr 21 2015
next sibling parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Tue, 21 Apr 2015 18:30:44 -0700, Jonathan M Davis via Digitalmars-d
wrote:

 And since isInputRange has guaranteed that elements have been copyable,
 I think that it's perfectly reasonable that it's been assumed that they
 would be, and changing that at this point just isn't worth it.
yet disallowing some algorithms on ranges that are (algos) working ok is=20 limiting too. fixing `isInputRange` was the easiest way i found to allow=20 usage of such algorithms. another possibility is to check all algo implementations and see if they=20 can be used with ranges that have non-copyable elements, and then mark=20 them as such, replacing `isInputRange` to newly created trait. this can=20 be automated, i believe -- at least checking. i understand that this will add another trait to the pile, but i believe=20 that this will make std.algorithm better, as it will accept more range=20 types. from the user POV i don't care about "range definition purity",=20 the only thing i see is that std.algorithm is rejecting a perfectly valid=20 range, and i'm doing no copies at all -- so i must forget about all=20 std.algo niceties and fall back to stupid loops. i.e. allowing such ranges in std.algo (where appropriate) will be a win=20 for end-user. i understand that it will add some support burden, though.=20 but it shouldn't be that big, considering that implementations are more=20 or less stable now.=
Apr 21 2015
parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wednesday, April 22, 2015 02:05:38 ketmar via Digitalmars-d wrote:
 On Tue, 21 Apr 2015 18:30:44 -0700, Jonathan M Davis via Digitalmars-d
 wrote:

 And since isInputRange has guaranteed that elements have been copyable,
 I think that it's perfectly reasonable that it's been assumed that they
 would be, and changing that at this point just isn't worth it.
yet disallowing some algorithms on ranges that are (algos) working ok is limiting too. fixing `isInputRange` was the easiest way i found to allow usage of such algorithms. another possibility is to check all algo implementations and see if they can be used with ranges that have non-copyable elements, and then mark them as such, replacing `isInputRange` to newly created trait. this can be automated, i believe -- at least checking. i understand that this will add another trait to the pile, but i believe that this will make std.algorithm better, as it will accept more range types. from the user POV i don't care about "range definition purity", the only thing i see is that std.algorithm is rejecting a perfectly valid range, and i'm doing no copies at all -- so i must forget about all std.algo niceties and fall back to stupid loops. i.e. allowing such ranges in std.algo (where appropriate) will be a win for end-user. i understand that it will add some support burden, though. but it shouldn't be that big, considering that implementations are more or less stable now.
An alternative would be to create a range of pointers to the non-copyable objects and operate on those instead. That may not be quite what you want, but it should work, and it avoids having to complicate ranges any further for what amounts to a very uncommon use case. - Jonathan M Davis
Apr 21 2015
prev sibling parent "Atila Neves" <atila.neves gmail.com> writes:
<snip>
 from the very beginning. This isn't new. And given that the C++ 
 STL gets
 away with its containers not working with non-copyable 
 elements, I think
 that that proves that you can have a major component in the 
 standard library
 - containers no less - not support copyable elements and have 
 it work and be
 acceptable.
Semi-acceptable, and even then, no longer the case in C++. Before move semantics, yes, C++ containers were limited to copyable elements, which meant using raw pointers since auto_ptr couldn't be copied. It was a royal pain. But for 4 years now I've been able to do this: std::vector<std::unique_ptr<MyClass>> stuff; stuff.emplace_back(new MyClass); auto ptr = std::unique_ptr<MyClass>(new MyClass); stuff.push_back(std::move(ptr)); Which won't compile with the `std::move` because unique_ptr isn't copyable. D has move semantics. C++98/03 did not. The comparison with C++ is no longer justified. Ketmar has a point though. So do you. The worst part of D move semantics is not being able to copy a const variable, since copying is move + postblit and you can't move from a const object. Atila
Apr 22 2015
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
I should also point out that std.array.array can't work with non-copyable
elements, and that's a pretty major function in Phobos. So, if we _were_
going to support non-copyable elements, we couldn't do it simply by making
isInputRange accept them, but regardless, I don't think that it's worth the
extra complication to support non-copyable elements.

- Jonathan M Davis
Apr 21 2015
prev sibling parent reply "Dominikus Dittes Scherkl" writes:
On Tuesday, 21 April 2015 at 23:33:38 UTC, ketmar wrote:
 On Tue, 21 Apr 2015 15:48:25 -0700, Jonathan M Davis via 
 Digitalmars-d wrote:
 auto h = r.front;
the thing is that chain, or filter, or other algorithms are perfectly able to work with such ranges, yet it is forbidden now. it looks like arbitrary limitation to me.
why not introducing a new trait "isNonCopyingInputRange" with the old definition and define "isInputRange = isNonCopyingInputRange and compiles( auto h = r.front)" and then make filters and chain and all algorithms that don't need copying requiring only the new trait?
Apr 22 2015
parent ketmar <ketmar ketmar.no-ip.org> writes:
On Wed, 22 Apr 2015 08:41:38 +0000, Dominikus Dittes Scherkl wrote:

 On Tuesday, 21 April 2015 at 23:33:38 UTC, ketmar wrote:
 On Tue, 21 Apr 2015 15:48:25 -0700, Jonathan M Davis via Digitalmars-d
 wrote:
 auto h =3D r.front;
the thing is that chain, or filter, or other algorithms are perfectly able to work with such ranges, yet it is forbidden now. it looks like arbitrary limitation to me.
=20 why not introducing a new trait "isNonCopyingInputRange" with the old definition and define "isInputRange =3D isNonCopyingInputRange and compiles( auto h =3D r.front)" and then make filters and chain and all algorithms that don't need copying requiring only the new trait?
i already suggested that. but the thing is that: 1. someone has to code that. 2. it has to convince at least W&A to accept the code. that won't be me, especially considering "2".=
Apr 22 2015
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/21/15 3:53 PM, ketmar wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=14478

 so be careful: ranges with non-copyable elements aren't input ranges for
 now. ;-)
This does seem like an incorrect limitation, and I'm not sure if it was intentional. However, there is a lot of code out there that expects this to work when isInputRange is true. I don't know if we should change it, as the range definition is pretty clear in the documentation that auto h = r.front is a required feature for ranges. What is the use case for this? -Steve
Apr 21 2015
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Tue, 21 Apr 2015 18:57:50 -0400, Steven Schveighoffer wrote:

 On 4/21/15 3:53 PM, ketmar wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=3D14478

 so be careful: ranges with non-copyable elements aren't input ranges
 for now. ;-)
=20 This does seem like an incorrect limitation, and I'm not sure if it was intentional. However, there is a lot of code out there that expects this to work when isInputRange is true. I don't know if we should change it, as the range definition is pretty clear in the documentation that auto h =3D r.front is a required feature for ranges. What is the use case for this?
one possible use case was shown in bugreport. array of non-copyable=20 struct, yet i still want chain 'em, for example. or filter. or... struct S { int n; disable this (this); } void main () { S[2] arr; arr[0].n =3D 1; arr[1].n =3D 2; foreach (ref el; arr[].filter!((ref a) =3D> a.n > 1)) { writeln(el.n); } } this code is perfectly valid, it doesn't require copying at all, yet it=20 is invalid now.=
Apr 21 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/21/15 7:31 PM, ketmar wrote:
 On Tue, 21 Apr 2015 18:57:50 -0400, Steven Schveighoffer wrote:

 On 4/21/15 3:53 PM, ketmar wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=14478

 so be careful: ranges with non-copyable elements aren't input ranges
 for now. ;-)
This does seem like an incorrect limitation, and I'm not sure if it was intentional. However, there is a lot of code out there that expects this to work when isInputRange is true. I don't know if we should change it, as the range definition is pretty clear in the documentation that auto h = r.front is a required feature for ranges. What is the use case for this?
one possible use case was shown in bugreport. array of non-copyable struct, yet i still want chain 'em, for example. or filter. or... struct S { int n; disable this (this); } void main () { S[2] arr; arr[0].n = 1; arr[1].n = 2; foreach (ref el; arr[].filter!((ref a) => a.n > 1)) { writeln(el.n); } } this code is perfectly valid, it doesn't require copying at all, yet it is invalid now.
Yes, I agree this is a valid use case. I don't think we can change isInputRange, because other code may depend on that requirement of copyability, but it is probably possible to alter algorithms so they can accept these "not-quite" input ranges. Definitely proxy or decorator type adapters that provide a proxy for front shouldn't be restricted to using only copyable range elements. 1st step is we need a trait to define what we are looking for, then the next step is to simply alter all the appropriate algorithms to use it. It shouldn't hinder any code that exists if we do that. So what should be the name of this beast? -Steve
Apr 22 2015
next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 22 April 2015 at 16:02:51 UTC, Steven Schveighoffer 
wrote:
 On 4/21/15 7:31 PM, ketmar wrote:
 On Tue, 21 Apr 2015 18:57:50 -0400, Steven Schveighoffer wrote:

 On 4/21/15 3:53 PM, ketmar wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=14478

 so be careful: ranges with non-copyable elements aren't 
 input ranges
 for now. ;-)
This does seem like an incorrect limitation, and I'm not sure if it was intentional. However, there is a lot of code out there that expects this to work when isInputRange is true. I don't know if we should change it, as the range definition is pretty clear in the documentation that auto h = r.front is a required feature for ranges. What is the use case for this?
one possible use case was shown in bugreport. array of non-copyable struct, yet i still want chain 'em, for example. or filter. or... struct S { int n; disable this (this); } void main () { S[2] arr; arr[0].n = 1; arr[1].n = 2; foreach (ref el; arr[].filter!((ref a) => a.n > 1)) { writeln(el.n); } } this code is perfectly valid, it doesn't require copying at all, yet it is invalid now.
Yes, I agree this is a valid use case. I don't think we can change isInputRange, because other code may depend on that requirement of copyability, but it is probably possible to alter algorithms so they can accept these "not-quite" input ranges. Definitely proxy or decorator type adapters that provide a proxy for front shouldn't be restricted to using only copyable range elements. 1st step is we need a trait to define what we are looking for, then the next step is to simply alter all the appropriate algorithms to use it. It shouldn't hinder any code that exists if we do that. So what should be the name of this beast? -Steve
We could just add a flag as a second argument to isInputRange.
Apr 22 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/22/15 12:10 PM, John Colvin wrote:
 On Wednesday, 22 April 2015 at 16:02:51 UTC, Steven Schveighoffer wrote:
 Yes, I agree this is a valid use case. I don't think we can change
 isInputRange, because other code may depend on that requirement of
 copyability, but it is probably possible to alter algorithms so they
 can accept these "not-quite" input ranges. Definitely proxy or
 decorator type adapters that provide a proxy for front shouldn't be
 restricted to using only copyable range elements.

 1st step is we need a trait to define what we are looking for, then
 the next step is to simply alter all the appropriate algorithms to use
 it. It shouldn't hinder any code that exists if we do that.

 So what should be the name of this beast?
We could just add a flag as a second argument to isInputRange.
Yeah, I like this. But now we have to name the flag :) I don't think it should be a bool, because: isInputRange!(R, true) Is pretty obtuse. I'd rather see something like: isInputRange!(R, RangeOption.NonCopyable) Or whatever name we come up with. The nice thing about this solution is that the range options could be passed down the trait chain, so isForwardRange easily gets this ability as well. -Steve
Apr 22 2015
parent reply "Dominikus Dittes Scherkl" writes:
On Wednesday, 22 April 2015 at 19:37:21 UTC, Steven Schveighoffer 
wrote:
 Yeah, I like this. But now we have to name the flag :)

 I don't think it should be a bool, because:

 isInputRange!(R, true)

 Is pretty obtuse. I'd rather see something like:

 isInputRange!(R, RangeOption.NonCopyable)

 Or whatever name we come up with.

 The nice thing about this solution is that the range options 
 could be passed down the trait chain, so isForwardRange easily 
 gets this ability as well.

 -Steve
I don't like that, because this is NOT an input range, it is something inferior but it is enough that some algorithms happen to work also on this crippled input range. And option would indicate that it has some extra features over and above what a general input range provides, which is not the case. This would require to change the code of every algorithm taking input ranges to check if the range is copyable - exactly what we don't wanted! I would name it clumsy "isNonCopyableInputRange", and change only those algorithms that can cope with such a thing.
Apr 23 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 4/23/15 5:03 AM, Dominikus Dittes Scherkl wrote:
 On Wednesday, 22 April 2015 at 19:37:21 UTC, Steven Schveighoffer wrote:
 Yeah, I like this. But now we have to name the flag :)

 I don't think it should be a bool, because:

 isInputRange!(R, true)

 Is pretty obtuse. I'd rather see something like:

 isInputRange!(R, RangeOption.NonCopyable)

 Or whatever name we come up with.

 The nice thing about this solution is that the range options could be
 passed down the trait chain, so isForwardRange easily gets this
 ability as well.

 -Steve
I don't like that, because this is NOT an input range, it is something inferior but it is enough that some algorithms happen to work also on this crippled input range. And option would indicate that it has some extra features over and above what a general input range provides, which is not the case. This would require to change the code of every algorithm taking input ranges to check if the range is copyable - exactly what we don't wanted! I would name it clumsy "isNonCopyableInputRange", and change only those algorithms that can cope with such a thing.
I've given some more thought to how this is playing out. If you look around std.algorithm, etc., you will see many different "additive" traits for input ranges, i.e. hasAssignableElements, hasSlicing, all these things that work on top of the basic building blocks of ranges to further tune what an algorithm can do. This is kind of a new thing that wasn't considered, and something where we can't say "is input range but doesn't have x", because isInputRange doesn't provide a less specific version. It's like we thought we had discovered the atom, only to find we actually just discovered a molecule. Note, that the only *language* requirements for ranges is that foreach works with them, and foreach works with these. But the library adds this requirement that the elements be copyable. I'm actually not convinced this was intentional, as when ranges came about, I don't believe we had the ability to disable copying. I begrudgingly agree with you that the flag idea isn't going to cut it. The alternatives here are, we fix isInputRange so it allows non-copyable elements (I don't think we can do this immediately, it's an API change to a fundamental building block), or we have a fleet of isNonCopyableXRange. That lacks appeal as well, especially in the DRY department. I wonder if a possible fix is to define hasRangeTroika or whatever, and then hasCopyableElements, and define isInputRange to mean both. Then later we can deprecate the meaning of isInputRange to mean both, and just have it mean the first. I don't know of a good way to do this so people are warned that their code won't work. The nice thing about isInputRange is that it's just a template constraint. If the code expects the copyable nature, it would simply mean a compile error in compiling the function vs. a compile error in finding a suitable template. It might be a distinction without a difference. I'd really like to hear from Andrei on this. -Steve
Apr 23 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/23/15 5:52 AM, Steven Schveighoffer wrote:
 I'd really like to hear from Andrei on this.
Such an abstraction (a range without the ability to copy its front) is a bit of a rarity so only a small subset of algorithms would work with it. So probably it deserves its name e.g. SingleReadRange. -- Andrei
Apr 25 2015
prev sibling parent ketmar <ketmar ketmar.no-ip.org> writes:
On Wed, 22 Apr 2015 12:02:51 -0400, Steven Schveighoffer wrote:

 So what should be the name of this beast?
isRestrictedInputRange? ;-) no, really, it's not a fully valid input range, so let's name the trait=20 with a long word to indicate that something is very unusual with it.=
Apr 22 2015
prev sibling parent reply "Jesse Phillips" <Jesse.K.Phillips+D gmail.com> writes:
On Tuesday, 21 April 2015 at 19:53:47 UTC, ketmar wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=14478

 so be careful: ranges with non-copyable elements aren't input 
 ranges for
 now. ;-)
The problem with allowing the inability to copy elements to be an input range is that you must then preven an algorithm from copying the range elements, how do you do that without preventing input ranges from having copyable elements?
Apr 21 2015
parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Wed, 22 Apr 2015 03:00:18 +0000, Jesse Phillips wrote:

 On Tuesday, 21 April 2015 at 19:53:47 UTC, ketmar wrote:
 here's the interesting oversight for isInputRange:
 https://issues.dlang.org/show_bug.cgi?id=3D14478

 so be careful: ranges with non-copyable elements aren't input ranges
 for now. ;-)
=20 =20 The problem with allowing the inability to copy elements to be an input range is that you must then preven an algorithm from copying the range elements, how do you do that without preventing input ranges from having copyable elements?
many algorithms in std.algo doesn't copy if you'll use `(ref a)` labmdas.=
Apr 21 2015
parent reply "Jesse Phillips" <Jessekphillips+D gmail.com> writes:
On Wednesday, 22 April 2015 at 05:31:03 UTC, ketmar wrote:
 many algorithms in std.algo doesn't copy if you'll use `(ref 
 a)` labmdas.
I understand that, but the compiler won't complain "hey that isn't valid for all input ranges!" when it sees that someone copied front.
Apr 22 2015
parent ketmar <ketmar ketmar.no-ip.org> writes:
On Wed, 22 Apr 2015 18:32:55 +0000, Jesse Phillips wrote:

 On Wednesday, 22 April 2015 at 05:31:03 UTC, ketmar wrote:
 many algorithms in std.algo doesn't copy if you'll use `(ref a)`
 labmdas.
=20 I understand that, but the compiler won't complain "hey that isn't valid for all input ranges!" when it sees that someone copied front.
yes, that's why introducing new trait is better. i was trying to minify=20 support burden with changes to `isInputRange`, yet it seems to bring more=20 problems that it is intended to solve, and i was wrong. but i still believe that allowing "proxying algos" work on such=20 "restriced" ranges is a viable addition. think about `Unique`, for=20 example, as Peter noted in bugzilla.=
Apr 22 2015