Range.init does not imply Range.empty==true

[Jonathan M Davis]

On Thursday, December 20, 2012 14:35:15 H. S. Teoh wrote:
> On Thu, Dec 20, 2012 at 11:04:05PM +0100, Jonathan M Davis wrote:
> > But regardless, my point is that Range.init.empty must be true _for
> > structs_. A struct range should be written such that its init value
> > is empty. That's not true for classes, because they'll be null.
> > 
> > Your assertion should pass as long as the type of _current is a
> > struct.
> 
> The problem with generic code is that you can't assume this. The type
> could be literally _anything_ (as long as it conforms to the range API).
> Unless you protect it with static ifs or something similar, of course.

Yes. That's why you use takeNone instead of the range's init property. And if 
you have to reassign the empty range to the original, then you'll need a 
template constraint which only accepts ranges which return the same type for 
takeNone.

> > If you want to get an empty range from an existing range, then use
> > takeNone. If it returns the same type (which it tries to do but can't
> > always do - e.g. with non-sliceable ranges which are classes or
> > non-sliceable Voldemort types), then you can reassign it to the
> > original. If it doesn't, then there's no generic way to get an empty
> > range of the same type from that range other than calling popFront
> > until it's empty (which is obviously ineffecient in the finite case
> > and impossible in the infinite case).
> 
> [...]
> 
> Which is why I'm leaning towards rewriting algorithms so that they don't
> rely on ranges being emptiable. (Like you said, it's easy to have a
> range class that's infinite, in which case there is no empty state for
> ranges of that type at all -- .empty is an enum set to false.) I find
> that the code often becomes cleaner when written in a way that minimizes
> extraneous assumptions. It's harder to write, for sure, but I think it's
> more rewarding in the end.

It should be fairly rare that algorithms have to make a range empty. I've run 
into cases where it was outright required, but I don't think that 
std.algorithm has many such cases (if any), though it may have some places 
where it can take advantage of takeNone for optimizations where possible (e.g. 
find does that in one of its overloads).

> Anyway, coming back to takeNone: in many cases takeNone won't return the
> exact same type as the original range, so code like this won't work
> anymore:
> 
> auto myRangeFunc(R)(R range) {
> struct Wrapper {
> R _src;
> R _helper;
> 
> this(R src) {
> _src = src;
> ...
> 
> // Works:
> _helper = _src;
> ...
> 
> // Won't work: R != typeof(takeNone!R)
> // in general.
> _helper = takeNone(src);
> }
> }
> }
> 
> To allow both _helper=_src and _helper=takeNone(src) to work, one would
> have to make _helper a wrapper type that can be assigned both R and
> typeof(takeNone!R). Is this possible with the current implementation of
> takeNone? I glanced at the code briefly but couldn't tell for sure.

That would depend on the type of _helper. If takeNone can't return the same 
type, it'll return takeExactly(range, 0). So, if the type of _helper is 
assignable from takeExactly, then sure. Or, if UFCS is used, then _helper 
could have a takeNone function on it which was able to return an empty range 
of the same type.

In general though, code can't assume that takeNone returns the same type. It 
will have to test for it if it needs that. But there's no way around that 
unfortunately.

- Jonathan M Davis