Range Redesign: Copy Semantics

[Quirin Schroll]

On Monday, 22 January 2024 at 05:22:44 UTC, Paul Backus wrote:
> You have N data structures and M algorithms, and by using this 
> common interface you can implement all N*M combinations in 
> O(N+M) code. Each data structure implements the range API once, 
> and each algorithm is implemented once using the range API.
>
> If you split the API in two, by making input streams (basic 
> input ranges) and forward ranges completely disjoint, you 
> undermine this goal. Now, each data structure has to implement 
> *two* APIs, and each algorithm has to be implemented *twice*, 
> once for input streams and once for forward ranges.

Not necessarily. First, any algorithm requiring a forward range 
wouldn’t be implemented twice. And, most importantly, a data 
structure would not offer input range iteration if it can offer 
forward range. Why would it?

> In practice, what's going to happen is library authors will 
> simply not bother to implement both, and we will end up with 
> gaps where many (data structure, algorithm) pairs are not 
> covered.

The only realistic concern I see with the proposal is algorithms 
being implemented requiring forward ranges when they could (also) 
work with basic input ranges. Overconstraining input is not 
specific to ranges, though.

What Jonathan never mentioned in his proposal, but something 
that, as far as I see, is true: One can wrap any forward range to 
be an input range. Heck, the pointer to any forward range is an 
input range, assuming there is a global `next(ForwardRange*)` 
function utilizing the forward range primitives. If you pass 
`&forwardRange` to an input range algorithm, it may copy it 
around as it pleases, it will change the underlying range just 
like an input range should; and you’d have the `&` for an 
indication that it does.

A problem I see with this is composition. Requiring the lifting 
to a pointer requires lvalues, and composition lives on not 
having those. The issue will generally be negligible, as most 
range algorithms returning a range will for the most part want to 
preserve as many of the abilities of the original range as 
possible. The difference in the algorithm would be that, instead 
of:
```d
// implement input range
static if (/* base range is forward range */)
     // implement forward range
static if (/* base range is bidi range */
     // implement bidi range
// etc.
```
You would have:
```d
static if (/* base range is input range */)
     // implement input range
else:
static if (/* base range is forward range */)
     // implement forward range
static if (/* base range is bidi range */)
     // implement bidi range
// etc.
```