isForwardRange doesn't work with alias range this or inheritance

[dlangBugzillaToGithub]

ali.akhtarzada reported this on 2019-06-27T21:24:42Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=20009

CC List

• shove

Description

struct FR {
  bool empty = true;
  void popFront() {}
  auto front() { return 0; }
  FR save() { return this; }
}

struct S {
  FR range;
  alias range this;
}

pragma(msg, isInputRange!S); // true
pragma(msg, isForwardRange!S); // false

It's because isForwardRange is defined as:

isInputRange!R && is(ReturnType!((R r) => r.save) == R);

But it should be:

isInputRange!R && is(R : ReturnType!((R r) => r.save));

The same thing will happen if you try an inherit from an interface that is a forward range, and if the save function returns the base class it will fail.

[dlangBugzillaToGithub]

dlang-bot commented on 2019-06-28T07:19:10Z

@shove70 created dlang/phobos pull request #7095 "Fix issue 20009 - isForwardRange doesn't work with alias range this o…" fixing this issue:

- Fix issue 20009 - isForwardRange doesn't work with alias range this or inheritance

https://github.com/dlang/phobos/pull/7095

[dlangBugzillaToGithub]

shove commented on 2019-06-29T05:01:15Z

(In reply to Ali Ak from comment #0)
> struct FR {
>   bool empty = true;
>   void popFront() {}
>   auto front() { return 0; }
>   FR save() { return this; }
> }
> 
> struct S {
>   FR range;
>   alias range this;
> }
> 
> pragma(msg, isInputRange!S); // true
> pragma(msg, isForwardRange!S); // false
> 
> It's because isForwardRange is defined as:
> 
> isInputRange!R && is(ReturnType!((R r) => r.save) == R);
> 
> But it should be:
> 
> isInputRange!R && is(R : ReturnType!((R r) => r.save));
> 
> The same thing will happen if you try an inherit from an interface that is a
> forward range, and if the save function returns the base class it will fail.


Since struct S inherits from struct FR, I think it should have the characteristics of ForwardRange too.
But unfortunately, after I do it according to your idea, although struct S passed the isForwardRange test, it caused a lot of compilation errors in the entire Phobos, including function code and assertions in unit tests. The reasons for this include at least the following:

1. is(T1 : T2) is somewhat different than what I have understood before:
    is(R!(int) : int[]) will pass the test, obviously this is not what is expected here.
2. Too many templates and APIs assume that the return type of save() is exactly equal to itself, and cannot be equal to the base class. It is equal to the base class that will overturn these assumptions and cause the program to fail or assert the failure. Such as:

    std.std.algorithm.searching.d line 3359:
    Range least = range.save;

    Obviously, the base type cannot be assigned to a derived type, and this assumption has limited the expectations of this issue.

Therefore, if you want isForwardRange to support derived types, then Phobos has too many places to change, and the workload is a bit large.

It might be a good idea to add a new template to the existing one that is specifically designed to test derived types with ForwardRange attributes:

template isDerivedForwardRange(R)
{
    static if (isInputRange!R && is(typeof((R r) => r.save) RT))
        enum bool isForwardRange = !is(R == ReturnType!RT) && is(R : ReturnType!RT);
    else
        enum bool isForwardRange = false;
}

But I don't know if it has practical use.

[dlangBugzillaToGithub]

ali.akhtarzada commented on 2019-07-08T08:39:26Z

Why mark this invalid? Are interfaces and alias this'd ranges not supposed to work?

[dlangBugzillaToGithub]

shove commented on 2019-07-08T09:21:32Z

(In reply to Ali Ak from comment #3)
> Why mark this invalid? Are interfaces and alias this'd ranges not supposed
> to work?

Misread the title and misoperate it. I'm sorry.

[jmdavis]

In general, testing for implicit conversions with template constraints is fraught with bugs. In particular, if a type passes a template constraint due to an implicit conversion, but the templated function does not then force the conversion, there can be compilation errors at best (due to the type not actually working with the code even if it would have if it had been converted), or worse it can result in silently incorrect behavior due to the fact that the implicit conversion happens implicitly in some parts of the code but not others (e.g. it could happen when front or popFront is used, because that requires the aliased type, but it's still the original object being passed around, not the actual range, which could result in things like front returning the same value every time if the range is copying the object's state when returned from the alias this rather than referencing it).

And to make matters worse, in some cases, even if the conversion is forced within the function, it's an @safety bug to do the implicit conversion within the function instead of at the call site. A prime example of this would be with static arrays (but it certainly isn't restricted to them). When implicitly slicing the static array at the call site (as happens when passing a static array to a function that takes a dynamic array), the result is a slice of the static array at the call site, whereas if the slicing happens within the function (as would occur with a templated function if the conversion is done inside it), then you're slicing a copy of the static array rather than the static array at the call site, and if it's returned, you're returning a slice of invalid memory. So, in the general case, templated code really needs to have any implicit conversions happen at the call site, not within the function. And since there is no way to tell the language to do the conversion at the call site, those conversions need to be explicit rather than having template constraints allow a type through because a type that it could implicitly convert to would work with the code.

So, as a general rule, it's a huge footgun to have template constraints allow implicit conversions, and just like range-based functions do not normally implicitly accept static arrays (rather, you have to slice them to get a range), types which are not themselves ranges should require that they be explicitly converted to a range at the call site. To do otherwise is to open the door to subtle bugs. So, IMHO, it would be a huge mistake to change isForwardRange to allow implicit conversions. We already have to fight bugs due to some of the traits in Phobos allowing implicit conversions when they really shouldn't (e.g. a number of the traits in std.traits treat enums as their base type even though they don't act exactly the same as their base type, which tends to cause issues for code which doesn't then check that a type isn't an enum), and isConvertibleToString in particular has caused @safety bugs precisely because it's testing for an implicit conversion and allowing such types in without the conversion having been done at the call site. And that particular mistake was introduced by Walter, showing that even experts make mistakes with implicit conversions and templates. It's the sort of thing that at first glance seem like it's really nice for usability but which in practice becomes a bug factory.

So, Phobos 3 will most definitely not be allowing implicit conversions for traits like isForwardRange, and even if we thought that it was a good idea and wanted to do it with Phobos 3, the Phobos 2 range traits aren't going to be changed to support it, because the risk of breaking existing code would be too great.

So, if a type is a range on its own, it's a range, whereas if it can be implicitly converted to be a range but isn't itself a range, code that wants to use it as a range is going to need to force the conversion. And that's not going to change, because it would risk far too many bugs in general even if it happens to work in some cases.