Transience of .front in input vs. forward ranges

[Jonathan M Davis]

On Sunday, November 04, 2012 21:49:58 Dmitry Olshansky wrote:
> I was mostly going by:
>  > The simpler way would be to simply state that input ranges can't
> 
> guarantee the persistence of .front after calling .popFront.
> 
> and
> 
>  >The algorithms that need to worry about .front's transience are only
> 
> the ones that work with input ranges (as opposed to forward ranges or
> stronger).
> 
> And conclude that applying this simple rule to std.array.array* means it
> has to assume non-transient elements and somehow copy/dup'em. Problem is
> we don't have generic function to make 100% guaranteed unaliased copy
> (it could omit doing any work on non-aliased objects).
> 
> Also that it misses forward ranges that have aliased .front, assuming
> they are non-transient.

The reality is that in the general case, you can't know for certain whether 
the result of front is transient or not. In some cases, you know, because the 
type is clearly immutable or a value type. In others (e.g. char[]), you can't 
know. A particularly annoying one though is classes, because they're almost 
never going to be immutable, so in almost all cases, if input ranges can have 
transient fronts and the range's element types is a class, then you have to 
assume that its front is transient. And I'm not sure whether it's possible to 
determine whether a struct is a value type or a reference type or not. The 
mutable indirections bit probably makes it so that you can determine for sure 
that some structs are value types, but you can't be certain for some of them 
whether they're a reference type or value type without examining the postblit 
constructor.

So, what it ends up coming down to if we accept that input ranges can have 
transient fronts is that algorithms then either have to require forward ranges 
in the case where they need to keep the result of front around, or we need a 
template of some kind which can determine in at least some cases that front in 
not transient (but it's going to have to say that front is transient in many 
cases where it isn't), and such algorithms will have to use that trait when 
dealing with input ranges.

The big problem though is std.array.array. Based on the functions that an 
input range has, all it needs is an input range, but it'll never work with a 
transient front. So, what is likely one of the most heavily used range-based 
functions can't work with input ranges. This is a big problem, and fixing it 
_will_ break code. Because either, we need to create a hasTransientFront 
template or make std.array.array require at least a forward range, which will 
make dealing with input ranges that much worse.

Still, as much as I hate the idea of permitting transient fronts, I'd rather 
have it be part of input ranges and be able to assume that other range types 
have non-transient fronts than create isTransient. Ranges are already overly 
complicated as it is. Regardless, if we decide that input ranges can have 
transient fronts, then we need to make that very clear, which clearly hasn't 
been the case, because only Andrei thought that the transience of front had 
anything to do with the definition of an input range.

- Jonathan M Davis