std.v2020.algorithm etc[ WAS: Is run.d going to be expand for runtime and the phobos library?]

[Jonathan M Davis]

On Monday, June 22, 2020 9:12:02 PM MDT H. S. Teoh via Digitalmars-d wrote:
> On Mon, Jun 22, 2020 at 10:54:08PM +0000, Jon Degenhardt via Digitalmars-d 
wrote:
> > On Monday, 22 June 2020 at 02:52:57 UTC, Andrei Alexandrescu wrote:
> > > On 6/21/20 10:47 AM, Andrei Alexandrescu wrote:
> > > One more thing before I forget - we should drop classes that are
> > > ranges.  They add too much complication. The functionality would
> > > still be present by wrapping a polymorphic implementation in a
> > > struct.
> >
> > I have used class-based ranges quite a bit to implement ranges with
> > reference semantics. Classes are very convenient for this because the
> > implementation is structurally very similar to a struct based
> > implementation. Typically, replace 'struct' with 'final class' and
> > modify a helper function constructing the range to use 'new'. It's
> > amazingly easy.
>
> [...]
>
> Yeah, I rely on class ranges on occasion too, when runtime polymorphism
> is required. They *are* cumbersome to use, though, I'll give you that.
> If we're going to remove class-based ranges, then whatever replaces them
> better have good support for runtime polymorphism, otherwise it's not
> gonna fly.
>
> This may be more common than people think. For example, sometimes I have
> a range helper:
>
>   auto myFunc(R)(R r, bool cond)
>   {
>       if (cond)
>           return r.map!someFunc;
>       else
>           return r.filter!someFilter.map!someFunc;
>   }
>
> There is no way to make this compile (cond is only known at runtime),
> because the return statements return diverse types, except to wrap it in
> an InputRangeObject.
>
> Though I only rarely need this, it's nonetheless critical functionality
> because sometimes, you cannot know the exact range type until runtime,
> and runtime polymorphism is unavoidable.  So this part of the current
> range API cannot be just thrown out without a viable replacement.

As far as forward ranges go, all that should be required is that the class
be wrapped by a struct where the copy constructor does the equivalent of
save. The class itself can then do the polymorphism like it would now. It's
just that the class won't be passed around directly. But because it's
wrapped in a struct, it then becomes possible to require that all forward
ranges have the same copying semantics (thus allowing us to ditch save) as
well as stuff like requiring that the init value be a valid, empty range
(which not only is not the case right now but cannot be the case so long as
we allow ranges which are classes).

That being said, it is almost always a mistake to make a range a class if it
can be avoided, because the allocations for save (or the copy constructor if
it replaces save) incur a huge performance hit relative to what it costs to
copy a range that's just a struct (e.g. the tests for dxml which use classes
for the range are _very_ slow in comparison to those that use dynamic arrays
or structs). So, even wrapped in a struct, it's not a great idea to use a
class for a forward range, but with problems like you describe here, AFAIK,
we really don't have a better solution. It's best to avoid the need for
runtime polymorphism with ranges, but it's not always possible. That being
said, it should work wrapped in a struct rather than having the class
exposed directly.

Now, as far as basic input ranges go, having them be classes isn't
necessarily a problem, since basic input ranges are essentially reference
types by their very nature (or at least, they can't be value types). If they
could have value semantics, they could be forward ranges. In fact, in some
ways, it would be nice to require that basic input ranges be classes, since
then it would be easy to introspect a basic input range vs a forward range,
and it would ensure that basic input ranges have full-on reference
semantics, but it also would result in heap allocations that are not
currently necessary - particularly in cases where it would currently work to
use a pseudo-reference type rather than full-on reference type. So, while it
would be very nice to be able to require that basic input ranges be classes,
I doubt that it's actually reasonable to do so. Either way, it shouldn't be
a problem to allow basic input ranges to be classes. It's just with forward
ranges that it's a problem, but struct wrappers should solve that problem.

- Jonathan M Davis