Proposed Changes to the Range API for Phobos v3

[Jonathan M Davis]

On Saturday, May 18, 2024 2:21:01 PM MDT Steven Schveighoffer via Digitalmars-d 
wrote:
> The `hasSlicing` test is very hard to understand. But it looks
> like it either it's infinite, or the slice must be the same type
> as the range itself.
>
> So I think we already are dealing with this, and I wouldn't
> expect it to change.
>
> Clearly, `.init` is going to be the same type, and we can exploit
> that for emptying a range.
>
> I wouldn't expect the rules for hasSlicing to change.

The rules will have to change somewhat, but the way that they will change is
to bring them in line with how most folks would likely expect slicing to
work. At least with finite ranges, slicing a range should behave like you'd
expect with dynamic arrays so that you really don't have to think about it,
and code that was written to work with dynamic arrays would then just work
with ranges (at least as far as slicing goes).

Right now, what hasSlicing essentially requires is

1. If the range is finite, slicing the range must result in the same type,
that type must have length, and length must be size_t (which therefore
indirectly requires that a finite range with slicing have length).

2. If the range is infinite, slicing the range with indices must result in a
finite range with length, and length must be size_t (though it seems to fail
to require that the element type be the same or that the resulting type have
slicing).

3. Slicing with indices has to result in a forward range, so that indirectly
requires that finite ranges with slicing be forward ranges, but it puts
infinite ranges in the bizarre position that they can have slicing as only
basic input ranges so long as slicing them with indices somehow is then able
to result in a forward range.

4. If slicing the range with an index and $ (e.g. range[0 .. $]) compiles,
it must result in a range with the same type, but slicing the range with an
index and $ does not actually need to compile.

5. If range[0 .. $ - 1] compiles (whether the range is finite or infinite),
then the result must be the same type. There is no requirement that
range[0 .. $ - 1] compiles if range[0 .. $] compiles or that range[0 .. $]
compiles if range[0 .. $ - 1] compiles.

And actually figuring out that that's what hasSlicing does is annoyingly
difficult. It's definitely a mess. As it stands, it wouldn't surprise me if
I screwed up something in what I just listed, though I _think_ that I have
it right.

Either way, since hasSlicing does not actually require that $ work, we can't
actually use it in generic code right now, so the current checks for it are
pretty pointless.

What we need is for finite ranges to be sliceable with basically the same
semantics as dynamic arrays, and for that to work, not only does $ need to
work with slicing, but at least some of the basic arithmetic operations need
to work (ideally, no one would really need to think about what they can do
with $ and ranges; they'd just do what they do with arrays).

And for infinite ranges, we need $ to work, but it really only makes sense
for it to work without arithmetic, since doing arithmetic on infinity is
pointless. For infinite ranges, $ is really just a marker for the end of the
range and not an index. And just like now, slicing an infinite range should
result in a finite range if $ isn't used, and it should result in the same
range type if $ is used.

So, the rules become something like

1. Ranges with slicing should be forward ranges (or copyable ranges as
they'll likely be renamed to).

2. Finite ranges should have length, and length should evaluate to size_t.

3. For finite ranges, range[0 .. 0] and range[0 .. $] need to compile and
result in the same type. In addition to that, we need the set of arithmetic
operations that folks would typically expect to work with dynamic arrays to
work, which I think includes subtraction, division, and comparison - e.g.
range[0 .. $ - 1], range[0 .. $ / 2], range[0 .. $ == 1 ? 0 : $], and
range[0 .. $ < 10 ? $ : 10].

4. For infinite ranges, range[0 .. 0] must compile and result in a finite
range with the same element type, and that finite range must also have
slicing.

5. For infinite ranges, range[0 .. $] must compile and result in the same
range type. No arithmetic or comparison operations will be checked for with
$ and infinite ranges.

All in all, I think that that's straightforward and as expected with the
main complication being the exact operations that $ supports with finite
ranges (which I unfortunately had not thought about in great detail until
monkyyy brought it up in this thread). And there are two ways that I see to
handle that

1. We figure out the set of arithmetic operations that we want to guarantee
work (and I _think_ that that list is subtraction, division, and the
comparison operators).

2. We just require that opDollar evaluate to size_t, which would effectively
require that it be an alias to length even if it technically wouldn't have
to be.

I was thinking that we would need to do #1 to support some edge cases, but
since length already has to be size_t, I'm increasingly tempted to just
require that $ be size_t as well, since then we don't have to do _any_ work
to make sure that $ works with the same operations that $ works with for
arrays. And realistically, in the vast majority of cases, opDollar is just
going to be an alias of length anyway. It would also have the benefit of
making the trait that much shorter and cleaner, so understanding the
requirements would be much easier. The only real question is whether there
are any reasonable ranges that we would then be disallowing (and I don't
think that there would be, but I'm not entirely sure).

Either way, opDollar for infinite ranges would not require any arithmetic
and could not be size_t, since that would mean using actual indices for both
ends of the range, which would result in a finite range.

And regardless of the exact set of requirements, the updated trait needs to
written much more clearly than what we currently have.

Actually, a related issue is whether random-access ranges should require
slicing. Slicing can work with forward ranges (presumably because of edge
cases where you can reasonably slice a forward range but can't reasonably
provide the elements in the middle without iterating through the preceding
elements first) even though you'd usually associate slicing with
random-access ranges. However, while slicing is typically associated with
random-access ranges, isRandomAccessRange does not actually require it. I'm
very tempted to add that requirement in order to simplify things, though
that would likely result in hasSlicing being used almost not at all (since
slicing anything other than a random-access range is definitely an edge
case), but I'm not 100% sure that there isn't some weird edge case where
it's reasonable to be able to randomly access a range's elements, but it's
not reasonable to be able to slice the range.

- Jonathan M Davis