On Monday, January 22, 2024 8:41:35 AM MST Atila Neves via Digitalmars-d wrote:
> On Sunday, 21 January 2024 at 05:00:31 UTC, Jonathan M Davis
>
> wrote:
> > I've been thinking about this for a while now, but with the next version of Phobos which is in the early planning stages, we really should do some redesigning of ranges. Most of their API is just fine how it is, but there are some aspects of it which really should be changed if we want them to be better (the most obvious one being the removal of auto-decoding). But what I'd like to discuss specifically in this thread is fixing - and defining - the semantics of copying and assigning to ranges. Specifically, the semantics of stuff like
> >
> > [...]
>
> I don't think I've ever encountered a situation where reference ranges would have been desirable - I've never used one.
>
> I think that `.save` was a historical mistake, and that ranges that can be copied are forward ranges. Something like a range reading from stdin or a socket would/should disable the copy/postblit constructors.

Once you disable the copy/postblit constructor, you can't generally pass the range around or wrap it in another range - at least not without explicit calls to move. ref parameters and return values would solve some of that, but it wouldn't solve all of it (wrapping in particular, which ranges do heavily, won't work with ref). I would expect a range that can't be copied to be too annoying to even bother with. And in fact, they can't even work with foreach, because foreach copies the range that it iterates over (and has to in order to have the semantics match what hapens with dynamic arrays, though if we separate basic input ranges from forward ranges, then we can change what happens with basic input ranges). IMHO, if we want to go the route of trying to make them uncopyable, we pretty much might as well just get rid of the concept of basic input ranges and require that they use opApply (which isn't an entirely bad idea given how limited basic input ranges are in practice anyway).

Basic input ranges are inherently either reference types or pseudo-reference types, and they can be made to work cleanly if we just require that they be reference types. Those are very different semantics from forward ranges, which are value types with regards to their iteration state (assuming that we require that copying them results in copies which can be independently iterated rather than having save). And that's why I'm arguing that we should split the two concepts rather than trying to treat forward ranges like an extension of basic input ranges - especially since basic input ranges are extremely hamstrung anyway, because you can't actually get an independent copy of them, and in practice, most stuff needs that. And if we did go with a solution for basic input ranges which made them non-copyable, then they couldn't be used with the same code that uses forward ranges anyway, so we might as well just give them a different API and stop treating them like the same thing when they really aren't.

> Has anyone here used the class-based ranges?

Yes. Symmetry uses them. In general, it's best not to use them for forward ranges, but when you're dealing with code where you can't determine the type at compile time (like with an interpreter), then you need some some kind of runtime polymorphism, and you really don't have much choice. That being said, we can support that by wrapping such classes in structs and ensuring that the structs have the correct copy semantics rather than allowing forward ranges that are classes. So, it should be quite possible to get rid of save without losing any functionality, and we'd get much cleaner copy semantics in the process, making it so that forward ranges in general behave more like dynamic arrays.

For basic input ranges, it should be perfectly fine for them to be classes - desirable even - simply because you can't actually get independent copies of them, and using a struct with pseudo-reference copy semantics is just begging for bugs, because it means that mutating the copy puts the original in an invalid state, whereas if we can require that all basic input ranges be full-on reference types (which could include structs and pointers to structs so long as they have the correct semantics), then we can actually rely on sane, consistent copy semantics for basic input ranges. It's just that they would be different from the copy semantics of forward ranges - which would also be true if we were somehow able to make it work to make basic input ranges noncopyable instead, though I really don't think that that will work.

- Jonathan M Davis

On Monday, January 22, 2024 2:17:08 AM MST Alexandru Ermicioi via Digitalmars- d wrote:
> On Monday, 22 January 2024 at 03:52:02 UTC, Jonathan M Davis
>
> wrote:
> > I'd have to think about it more to see whether having hasNext instead of returning a nullable type from next would be an improvement, make it worse, or be more or less equal. A lot of that depends on how it would affect the typical implementation of a basic input range.
>
> Well one advantage of `hasNext` is that you can check in advance whether range is empty or not, without the need to pop front element.

true

> > Part of the point here is to _not_ do that, because they fundamentally have different semantics.
>
> That would mean that you need to overload a method to accept both input, and forward ranges when foreach is not used, right?

Yes, though in practice, most functions tend to require forward ranges anyway. So, while the separation will be annoying in some cases, in general, I wouldn't expect it to be a big problem, and if anything, it will help make the distinction between basic input ranges and forward ranges clearer, which will probably make it easier to reason about the code. Obviously, we'll have to actually do it to see what the impact is, but realistically, about all you can do with basic input ranges is iterate through them once and possibly do transformations on their elements as you do it. The fact that they can be iterated separately from a foreach loop is beneficial, and some range-based functions are useful with them (e.g. map), but most range-based algorithms need forward ranges.

> > If this is coming across as complicated, then it's probably because of all of the explanatory text I had to give as to why these changes should be made. But the changes themselves simplify things for forward ranges.
>
> Could be the case :). Perhaps it would be nice to see it as a code example.

Well for forward ranges, you'd basically be writing what you write now except that you wouldn't have to worry about calling save anywhere, which would signifcantly reduce the number of bugs that crop into range-based code. So, about all I could really show you would be normal range-based code that just doesn't call save, because it doesn't need to.

It would also allow you to assign one range to another (assuming that they're the same type), which you can't do right now without relying on the specific copy semantics of a range. But for forward ranges, the main change here would simply be that you could assume that copying a range was equivalent to save, which is purely a simplification. If there's a complication, it's only that ranges which are currently reference types would have to do something smarter than saving in their copy constructor if they wanted to be efficient. So, they'd work with something like

struct Range(T)
{
    T front() { return _range.front; }
    void popFront() { _range.popFront(); }
    bool empty() { return _range.empty; }

    // or copy constructor
    this(this)
    {
        _range = _range.save;
    }

    private static class RefRange { ... }

    private RefRange _range;
}

but if you wanted them to be more efficient, you'd need something like

struct Range(T)
{
    T front() { return _range.front; }

    void popFront()
    {
        if(_range._refCount != 1)
            _range = _range.save; // ref count now 1

        _range.popFront();
    }

    bool empty() { return _range.empty; }

    // or copy constructor
    this(this)
    {
        _range.incRef();
    }

    ~this()
    {
        _range.decRef();
    }

    private static class RefRange { ... }

    private RefRange _range;
}

So, there would be some extra complication for reference type forward ranges, but most forward ranges already do the equivalent of calling save when they're copied, which is a large part of why you frequently end up with bugs when you try to use a range that needs you to call save explicitly.

- Jonathan M Davis

On Sunday, January 21, 2024 10:22:44 PM MST Paul Backus via Digitalmars-d wrote:
> On Monday, 22 January 2024 at 03:52:02 UTC, Jonathan M Davis
>
> wrote:
> > On Sunday, January 21, 2024 6:50:26 AM MST Alexandru Ermicioi
> >
> > via Digitalmars- d wrote:
> >> Then new input range api can also be propagated to other types of range such as forward range and further.
> >
> > Part of the point here is to _not_ do that, because they fundamentally have different semantics.

> 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.
>
> 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.

In practice, basic input ranges don't work with the vast majority of algorithms anyway. Some do (e.g. map), but pretty much anything that needs to do more than a simple transformation on the elements ends up needing a forward range. I really don't think that we're going to lose much by forcing basic input ranges to be separate.

> > Restricting copying would make ranges borderline unusable. They have to be able to be passed around and be wrappable, which means either copying them or moving them, and moving them would be very un-user-friendly, since it would require explicit calls to move calls all over the place.
>
> Worth noting that generic range algorithms already have to account for the existence of non-copyable types, since even if a range itself is copyable, its elements may not be.

Do they? Non-copyable types do not work with ranges right now. They don't work with foreach right now. Non-copyable types have their uses to be sure, but they're also fairly niche. Realistically, very little range-based code is going to work with them because of how restricted they are to deal with, and unless you're explicitly testing code with them, you're not going to end up writing code that works with them. We could bend over backwards to try to make them work in Phobos, but no one else is going to do that unless they're using non-copyable types in ranges themselves (which almost no one will be doing even if we support it), and trying to support non-copyable types will actively make range-base code worse in many cases, because it will require calling front multiple times, and many range-based algorithms do real work in front rather than simply returning a value (e.g. map works that way).

Granted, range-based code in general doesn't tend to be very disciplined about whether it calls front once or several times, but forcing it to be several times in order to support non-copyable types will have a real cost for code that is _way_ more common than non-copyable types.

Personally, I think that we should make it very explicit that non-copyable types are not supported by ranges. They don't work with them now, and I don't think that it's even vaguely worth it to try to make ranges work with them. The cost is too high for too little benefit.

> In light of the points above, my proposed copying semantics for input streams are:
>
> 1. Input streams MAY be non-copyable, but are not required to be. 2. If you copy an input stream and then call next() on the original, the behavior of both the original and the copy is unspecified.
>
> That is, I think we should give up on having 100% consistent copying semantics in this one case, in order to keep the overall API unified (by supporting UFCS next()) and avoid unnecessary pessimization of range algorithms.
>
> The good news is that with these semantics, if you write you generic code conservatively and treat all input streams as non-copyable, you'll get the right behavior in all cases. And if you don't, you'll get a compile-time error as soon as you actually try to pass in a non-copyable input stream, and you'll know exactly how to fix it. So this design is still an improvement on the status quo.

I really think that trying to support non-copyable types is not worth it - either for the ranges themselves or for their elements. It's not something that very many people are even going to think about, let alone do. So, if it were supported, realistically, it would just be with the algorithms in Phobos and with the code that the few people using such types wrote for themselves. And even in Phobos, even if we wanted to support it, realistically, it wouldn't work a lot of the time until the few people that cared complained about it, because very few programmers would even think about testisg with non-copyable types. It would be _far_ worse than the situation we have now with code needing to call save to work correctly and yet failing to call save all over the place, because most ranges don't need it. Even with Phobos, we have had many bugs over the years due to stuff like forgetting to call save or reusing a range, because you have to test with way too many range types to catch all of the edge cases. IMHO, we need to be trying to reduce the number of edge cases, not increasing them.

And it's not like non-copyable types have ever worked properly with ranges - so not supporting them is not removing capabiltiies. It's just not adding capabilities that a select few would like to have. And while I feel for them, I really think that it's far too niche to support given how costly it is to support.

- Jonathan M Davis

On Monday, 22 January 2024 at 23:07:28 UTC, Jonathan M Davis wrote:
> In practice, basic input ranges don't work with the vast majority of algorithms anyway. Some do (e.g. map), but pretty much anything that needs to do more than a simple transformation on the elements ends up needing a forward range. I really don't think that we're going to lose much by forcing basic input ranges to be separate.

Here's a very rough approximation of the number of algorithms in Phobos that work with basic input ranges:

    $ grep 'isInputRange' std/algorithm/*.d | wc -l
    153

For comparison, here are the other range types:

    $ grep 'isForwardRange' std/algorithm/*.d | wc -l
    141
    $ grep 'isBidirectionalRange' std/algorithm/*.d | wc -l
    42
    $ grep 'isRandomAccessRange' std/algorithm/*.d | wc -l
    62

So, I would say that your hypothesis is not supported by the data, in this case.

> Do they? Non-copyable types do not work with ranges right now. They don't work with foreach right now. Non-copyable types have their uses to be sure, but they're also fairly niche.

Work is being done to make ranges work with non-copyable types (e.g. [1]).

Foreach works if the elements are rvalues, or the elements are lvalues and you use ref for the loop variable. This is the correct, expected behavior.

I think a big part of the reason non-copyable types are not widely used is that a lot of existing library code was written without support for them in mind. Since we have an opportunity to start from scratch with Phobos v3, there is no reason to repeat this mistake.

[1] https://github.com/dlang/phobos/pull/8721

> trying to support non-copyable types will actively make range-base code worse in many cases, because it will require calling front multiple times, and many range-based algorithms do real work in front rather than simply returning a value (e.g. map works that way).

Have you ever actually written generic code that works with non-copyable types? I have, and it mostly involves (a) passing things by ref, (b) using 'auto ref' and core.lifetime.forward a lot, and (c) checking isCopyable!T before trying to copy things.

I have no idea why you think this would require calling front multiple times, or doing extra work. Perhaps you could try writing out some example code to clarify?

> Personally, I think that we should make it very explicit that non-copyable types are not supported by ranges. They don't work with them now, and I don't think that it's even vaguely worth it to try to make ranges work with them. The cost is too high for too little benefit.

First, as a general rule, I don't think that we, as standard-library authors, should be in the business of telling our users that their use-cases are illegitimate just because it makes our jobs more difficult.

Second...how do you know the benefit is too little? You thought earlier that "the vast majority of algorithms" didn't work with basic input ranges, even though the actual data shows that isn't true. Unless you have concrete evidence, I think it is better to avoid making assumptions about which use-cases are important and which aren't.

On Monday, January 22, 2024 5:57:49 PM MST Paul Backus via Digitalmars-d wrote:
> On Monday, 22 January 2024 at 23:07:28 UTC, Jonathan M Davis
>
> wrote:
> > In practice, basic input ranges don't work with the vast majority of algorithms anyway. Some do (e.g. map), but pretty much anything that needs to do more than a simple transformation on the elements ends up needing a forward range. I really don't think that we're going to lose much by forcing basic input ranges to be separate.
>
> Here's a very rough approximation of the number of algorithms in Phobos that work with basic input ranges:
>
>      $ grep 'isInputRange' std/algorithm/*.d | wc -l
>      153
>
> For comparison, here are the other range types:
>
>      $ grep 'isForwardRange' std/algorithm/*.d | wc -l
>      141
>      $ grep 'isBidirectionalRange' std/algorithm/*.d | wc -l
>      42
>      $ grep 'isRandomAccessRange' std/algorithm/*.d | wc -l
>      62
>
> So, I would say that your hypothesis is not supported by the data, in this case.

I will admit that the number is higher than I would have expected, but most of those algorithms are on the simple side where the algorithm itself doesn't care whether the range is consumed, whereas the caller very much cares. They were written to accept basic input ranges, because the algorithm itself will work with a basic input range, but that doesn't mean that it can actually be used with basic input ranges to do anything useful. For instance, you can use startsWith on a basic input range, but you pretty much never would, because then you've consumed it - and actually, it's not even safe to use the rest of the range in generic code after passing it to startsWith, because it was copied, and the original could be in an invalid state. The same goes with any function that takes an argument and gives you a result that doesn't wrap the input range and return it or return a partially iterated range.

In my experience, it's very rare that it's possible to make anything that isn't incredibly simple work with a basic input range due to the fact that looking at it consumes it and makes it impossible to then do anything useful with it. And it's easy to write simple algorithms which will technically work with a basic input range but which aren't actually useful with a basic input range.

So, sure, a surprising number of the algorithms in std.algorithm work with isInputRange, but a number of them really shouldn't be used with basic input ranges. Now, a few of them might be more useful if you could rely on a basic input range having reference semantics, but their composibility in general is pretty poor.

Either way, I think that the gain from being able to require specific copy semantics for both forward ranges and basic input ranges is worth it. And since such a requirement couldn't actually be enforced at compile time unless we made it impossible to have basic input ranges that were structs (which would then make reference counting impossible), then a specific algorithm could choose to add a function to forward ranges via UFCS and support them if it didn't care about the copy semantics, but like with @trusted code, I think that it should then be up to the programmer to make sure that it does the right thing so that basic input ranges can be required to have reference semantics.

> Foreach works if the elements are rvalues, or the elements are lvalues and you use ref for the loop variable. This is the correct, expected behavior.

Well, I couldn't get it to work when I tried, but either way, it means that you can't use foreach on a range of non-copyable types in generic code, because the way that you use foreach would have to be the same regardless of the elment type. Of course, you could use static if and branch the code based on whether the types are copyable or not, but that's yet another complication to range implementations which are already often far too complicated with too many static if branches.

> > trying to support non-copyable types will actively make range-base code worse in many cases, because it will require calling front multiple times, and many range-based algorithms do real work in front rather than simply returning a value (e.g. map works that way).
>
> Have you ever actually written generic code that works with
> non-copyable types? I have, and it mostly involves (a) passing
> things by ref, (b) using 'auto ref' and core.lifetime.forward a
> lot, and (c) checking isCopyable!T before trying to copy things.
>
> I have no idea why you think this would require calling front multiple times, or doing extra work. Perhaps you could try writing out some example code to clarify?

If you can't rely on front returning something that you can copy, then you're going to have to call front multiple times any time that you need to access front multiple times - either that or call move on it, which you can't necessarily do safely, because that would alter the range. Algorithms that don't have to look at front more than once don't have that problem, but plenty of algorithms need to do multiple things with front. And often, it's much better to just store the result of front rather than call front multiple times, because it's often the case that front does actual work that you'd rather not do over and over again (and it's particularly bad when you have stuff like the result of map where the transformation function it was given allocates on the heap).

So the result of having to worry about non-copyable types is that algorithms that need to access front multiple times are either going to end up calling front multiple times, harming performance in many cases, or they're going to have static if branches to change what they're doing based on the return type of front, which is going to make them that much more complex to implement.

> > Personally, I think that we should make it very explicit that non-copyable types are not supported by ranges. They don't work with them now, and I don't think that it's even vaguely worth it to try to make ranges work with them. The cost is too high for too little benefit.
>
> First, as a general rule, I don't think that we, as standard-library authors, should be in the business of telling our users that their use-cases are illegitimate just because it makes our jobs more difficult.
>
> Second...how do you know the benefit is too little? You thought earlier that "the vast majority of algorithms" didn't work with basic input ranges, even though the actual data shows that isn't true. Unless you have concrete evidence, I think it is better to avoid making assumptions about which use-cases are important and which aren't.

IMHO, it's already way too complicated to write correct range-based code, and adding non-copyable types into the mix is very much a step too far. Obviously, there can be disagreement on that, but it's already very difficult to write range-based code that actually works properly with all types of ranges. You have to test it with a ridiculous number of types, and most people just don't do that. Phobos often doesn't do that. And every capability that we add to ranges means even more static if blocks and even more variations that need to be tested. The only way to fix that is to simplify things by putting greater restrictions and requirements on how ranges work, whereas making them work with a wider variety of things is going in the opposite direction of that.

Realistically, the best that even might happen here for folks who want ranges to work with non-copyable types is that a subset of the algorithms in Phobos will be made to work with them, but third-party libraries are not going to go to that level of effort (and I don't think that it's all reasonable to tell them that they should). And Phobos' range-based code will become even more complicated and that much harder to maintain and make sure that it works correctly. And we already have too much trouble making sure that Phobos' range-based code works correctly.

So, my take on it is that supporting non-copyable types is simply not worth the effort given that it's going to complicate the code and the tests that much more, and they're already too complex.

And so, if it's my choice, then we simply won't support non-copyable types with ranges. Obviously, I'm not the sole voice in this, and ultimately, the choice is going to be up to Walter and Atila (probably Atila given that he's supposed to be the one in charge of Phobos), so I could definitely be overruled on this, but I very much want to see it become easier to write correct range-based code, not have it become harder.

- Jonathan M Davis

On Sunday, January 21, 2024 7:51:33 AM MST Paul Backus via Digitalmars-d wrote:
> On Sunday, 21 January 2024 at 05:00:31 UTC, Jonathan M Davis
>
> wrote:
> > From what I can see, the main negative is simply that you can't then write code that works on both a basic input range and a forward range (though you can obviously still create function overloads so that the caller can use either)
>
> With the proposed design, it would be possible to implement next() for forward ranges as a UFCS function:
>
>      auto next(FR)(FR fr)
>          if (std.v2.range.isForwardRange!FR)
>      {
>          if (fr.empty)
>          {
>              return Nullable!(ElementType!FR).init;
>          }
>          else
>          {
>              scope(success) fr.popFront;
>              return nullable(fr.front);
>          }
>      }
>
> So, a function written to operate on basic input ranges would be able to accept any kind of range, same as today.

Actually. What occurs to me is that if we made this function take the range by pointer, then it would be possible to give a forward range the correct copy semantics. You'd then have to take its address (or put it on the heap) to make it work, but then you'd get reference semantics even though it's a forward range.

Obviously, that's less than ideal if you want a function to accept both basic input ranges and forward ranges, but if it's a function that really only needs basic input ranges and doesn't benefit from operating on a forward range, then it would be simple enough to create an overload which takes the address - and if you really want to be returning the range from the function, then you wouldn't want it to be operating on both basic input ranges and forward ranges anyway, since you'd usually be looking to wrap the result, in which case, you'd need to do all of the annoying static ifs to determine which functions from the range API you could slap on the wrapper range based on the capabilities of the one being passed in.

- Jonathan M Davis

On Monday, 22 January 2024 at 17:07:05 UTC, H. S. Teoh wrote:
> On Mon, Jan 22, 2024 at 03:41:35PM +0000, Atila Neves via Digitalmars-d wrote:
>> On Sunday, 21 January 2024 at 05:00:31 UTC, Jonathan M Davis wrote:
>> > [...]
>> 
>> I don't think I've ever encountered a situation where reference ranges would have been desirable - I've never used one.
>
> It's useful in recursive-descent parsers where you expect the range to have advanced past whatever a recursive call has consumed.

Why can't this be done with value ranges?

>> I think that `.save` was a historical mistake, and that ranges that can be copied are forward ranges. Something like a range reading from stdin or a socket would/should disable the copy/postblit constructors.
>
> Meaning they can only be passed by reference?

Or moved.

On Tue, Jan 23, 2024 at 09:19:24AM +0000, Atila Neves via Digitalmars-d wrote:
> On Monday, 22 January 2024 at 17:07:05 UTC, H. S. Teoh wrote:
> > On Mon, Jan 22, 2024 at 03:41:35PM +0000, Atila Neves via Digitalmars-d wrote:
> > > On Sunday, 21 January 2024 at 05:00:31 UTC, Jonathan M Davis wrote:
> > > > [...]
> > > 
> > > I don't think I've ever encountered a situation where reference ranges would have been desirable - I've never used one.
> > 
> > It's useful in recursive-descent parsers where you expect the range to have advanced past whatever a recursive call has consumed.
> 
> Why can't this be done with value ranges?
[...]

Because the recursive call advances a value copy of the passed range, and when it returns, the range in the caller is still in the old position.


T

-- 
"Hi." "'Lo."