Bug 14478 – isInputRange should allow ranges of non-copyable elements

assume we have this code: import std.range; import std.stdio; struct S { int n; @disable this (this); } void main () { S[2] s0, s1; foreach (ref el; chain(s0[], s1[])) writeln(el.n); } if we try to compile it, we got error: (12): Error: template std.range.chain cannot deduce function from argument types yet if we will remove `@disable this (this);`, everything is working fine. the bug is in `isInputRange` template: template isInputRange(R) { enum bool isInputRange = is(typeof( (inout int = 0) { R r = R.init; // can define a range object if (r.empty) {} // can test for empty r.popFront(); // can invoke popFront() auto h = r.front; // can get the front of the range (HERE!) })); } line `auto h = r.front;` causes the bug. althru `front` returning ref here, we can't declare ref variables, so `h` looses `ref` and thus requires copying. yet we explicitly disabled copying for our struct, so `isInputRange` is failing. here is the proposed fix: template isInputRange(R) { enum bool isInputRange = is(typeof( (inout int = 0) { R r = R.init; // can define a range object if (r.empty) {} // can test for empty r.popFront(); // can invoke popFront() static void testfront(T) (auto ref T n) {} testfront(r.front); })); } here we using nested function with `auto ref` to not loose `ref` from `front`. it would be good to check if some other templates requires such fix too. p.s. with the proposed fix sample code works like a charm.

seems that `isBidirectionalRange` can be affected too.

*** Issue 14479 has been marked as a duplicate of this issue. ***

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.

yet at least some std.algorithm algorithms are able to work with such ranges. chain works ok, filter works too. others will do too, i think, with `(ref a)` predicates. yet current implementation forbids such usage.

Sure, some may work, but many won't, and a lot of user code out there won't. Grepping for such usage in Phobos quickly finds some, and a function like std.array.array _can't_ work with non-copyable elements (and that's a pretty major range-based function in Phobos). auto h = r.front; has been part of the definition of input ranges from the beginning, and so, everyone has been free to assume that a range's elements are copyable, because the definition of an input range guarantees it. We can't expect that it won't break code to change that now - especially when having non-copyable elements is so rare. This is the first time that I've ever heard anyone complain about this issue, so it clearly isn't affecting very many people, and the C++ folks thought that it was okay to require that elements in STL containers be copyable, so we're not the first to require that sort of thing with a major component of the standard library. I can see why you'd want to able to have ranges work with non-copyable elements, but simply changing the definition of an input range would break too much code, and I think that it's naive to expect that most range-based code would work with the change. I've seen plenty of cases in code where something like auto value = range.front; is done, and if this change were made, then that code's template constraints would be claiming that it worked with non-copyable elements when it didn't, and as it is now, such template constraints actually guarantee that non-copyable elements aren't used with such algorithms. If we were going to support anything like this, then we'd need a new set of traits for it rather than simply changing isInputRange, and given how rare this use case is, I don't think that it's worth it. I'd suggest that you just wrap a would-be range with non-copyable elements in another range which makes it so that they _are_ copyable (e.g. via pointer) and get around the problem that way.

(In reply to Jonathan M Davis from comment #3) > <snip> 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. Most containers in C++ only require movability, otherwise you couldn't have containers of std::unique_ptr<T>.

> Most containers in C++ only require movability, otherwise you couldn't have containers of std::unique_ptr<T> Then that's a change with C++11. Regardless, while it might be nice to support non-copyable elements with ranges, I really don't think that it's worth it - particularly when isInputRange has always required copyability. We'd be forced to either create a separate set of basic range traits - e.g. isInputRangeWithNonCopyableElements - or add something like hasCopyableElements and change isInputRange to no longer require copyable elements, which would then mean that a large portion of the range-based code out there would be wrong, since a lot of it is going to be copying elements, and unless folks regularly test their range-based code with ranges with non-copyable elements, they're not likely to catch the bugs where they accidentally require it, and they could be in for some rude surprises later when someone tries to use non-copyable elements. We already have enough problems with code assuming forward ranges or assuming that ranges aren't full reference types, which cause all kinds of fun bugs - including in Phobos.

(In reply to Jonathan M Davis from comment #7) > > Most containers in C++ only require movability, otherwise you couldn't have containers of std::unique_ptr<T> > > Then that's a change with C++11. Correct. Move semantics didn't really exist before C++11. > Regardless, while it might be nice to support non-copyable elements with > ranges, I really don't think that it's worth it - particularly when > isInputRange has always required copyability. We'd be forced to either > create a separate set of basic range traits - e.g. > isInputRangeWithNonCopyableElements - or add something like > hasCopyableElements and change isInputRange to no longer require copyable > elements, which would then mean that a large portion of the range-based code > out there would be wrong, since a lot of it is going to be copying elements, > and unless folks regularly test their range-based code with ranges with > non-copyable elements, they're not likely to catch the bugs where they > accidentally require it, and they could be in for some rude surprises later > when someone tries to use non-copyable elements. We already have enough > problems with code assuming forward ranges or assuming that ranges aren't > full reference types, which cause all kinds of fun bugs - including in > Phobos. I'd propose your second options: we already have hasMobileElements, hasAssignableElements etc., so I see no harm adding hasCopyableElements, and relax the isInputRange restrictions. Worst case scenario: someone has a range algorithm that expects copyable elements, but doesn't test for it, and tries to use it with move-only elements. In this case, they'll get an error on the line that tries to do the copy. Other than that, I don't believe any existing code will break.

Also, I just want to say that I think this is important. The only reason we aren't seeing its importance right now is because we have few non-copyable, but moveable types. Barely anyone uses Unique. Once Unique becomes more popular, I don't think we can justify a world where it's not possible to have an input range over a container of Unique objects.

Well, having something like Unique in the standard library not work with input ranges does sound worse, though I've rarely had a need for that sort of thing, and I'm quite certain that a lot of range-based code copies elements right now without considering the possibility of elements that aren't copyable. Even if we _do_ want to make it so that input ranges work with non-copyable types though, does it make any sense to do so with forward ranges - particularly when you consider having movable elements? Though that raises the question as to how well we do with movable elements and forward ranges right now. I don't think that most ranges have movable elements, but what happens when a range has been saved and then an element from that range is moved? Does the saved range still have a copy of it? Since it's supposed to be a copy of the range, ideally, it would, but realistically - particularly from the standpoint of a range being a view into a container - I don't see how it could. So, I suspect that we're really not dealing with the movability of elements cleanly right now either. Regardless, I really think that this is the sort of decision that Andrei needs to be involved in, and I have no idea what his take on it will be. Allowing non-copyable elements definitely makes things more complicated - particularly when it involves adding yet another range trait (and we arguably have too many already) - but I could also see it looking bad if Unique can't work in ranges, particularly if the STL now works with movable elements and not just copyable ones. This is just ugly all around.

> I've seen plenty of cases in code where something like > > auto value = range.front; Algorithms shouldn't needlessly copy values because it might be expensive, e.g. with big values. We should probably add an isCopyable!(ElementType!R) to the algorithms that do require this.

(In reply to Martin Nowak from comment #11) > Algorithms shouldn't needlessly copy values because it might be expensive, > e.g. with big values. > We should probably add an isCopyable!(ElementType!R) to the algorithms that do require this. Calling front multiple times can be just as expensive (or even more so) depending on what it does - e.g. if it calculates front, that could be more expensive than copying it, or in the case of map, it actually could be allocating a new value for every call to front. So, it's not at all cut and dry as to whether copying front is cheaper or not - especially if the value of front needs to be used multiple times before popFront gets called again. And while I agree that we should avoid unnecessary copying, when the cost of copying has come up in the past, it's pretty much been stated that copying has to be cheap (e.g. IIRC, Andrei always insists that copying should be O(1) - even with postblits - which seems unreasonable to me). So, whether it's a good idea or not, we've generally assumed that copying elements is cheap. The real problem though is that whether it's cheaper to call front once and copy the result or to call it multiple times without copying the result depends on what the range actually does, and there's no way to know. However, given map's behavior in particular, I'd tend to argue that we'd normally want to copy front rather than call it multiple times, which becomes problematic if we then have to worry about whether front is copyable. Some algorithms avoid the problem by only needing to access front once per element, but many of them need to access it multiple times.

I use a lot of noncopyable types, and I also think it is really important that they work with ranges. The comparison with C++ containers is somewhat tenuous, as containers generally manage their own elements and therefore need to be able to move them around. Ranges, on the other hand, typically do *not* own their elements, they are just views on someone else's. Consider this: struct S { @disable this(this); } S[9] array; auto slice = array[1 .. 5]; You would be very surprised if that last line didn't work, right? Ranges are just a higher-order abstraction of slices. Element copyability should most definitely be an orthogonal requirement to range-ness. As Peter pointed out, this will strictly be a loosening of a constraint, and as such will not break any existing code. To me it seems like a no-brainer.

@RazvanN7 created dlang/phobos pull request #7188 "Fix Issue 14478 - isInputRange should allow ranges of non-copyable elements" fixing this issue: - Fix Issue 14478 - isInputRange should allow ranges of non-copyable elements https://github.com/dlang/phobos/pull/7188

This issue has some similarities to issue #15413, but 15413 deals with ranges which are non-copyable, whereas this deals with ranges with elements which are non-copyable (though a range with non-copyable elements would also be non-copyable if the elements were contained directly in the range as occurs with some range types - e.g. std.range's only).

The linked PR changes have been merged as https://github.com/dlang/phobos/pull/8573 The issue title works now / has been fixed. `chain` still doesn't make use of this though.

@WebFreak001 created dlang/phobos pull request #8721 "fix 14478: support non-copyable elements in many range algorithms" fixing this issue: - fix 14478: support non-copyable elements in many range algorithms https://github.com/dlang/phobos/pull/8721

dlang/phobos pull request #8721 "fix 14478: support non-copyable elements in many range algorithms" was merged into master: - 1e161a0e0ecc5fd9dba2996ec883e371adb66aae by WebFreak001: fix 14478: support non-copyable elements in many range algorithms https://github.com/dlang/phobos/pull/8721