Never types should implement everything

[mqudsi]

I haven't thought this through fully, but I feel like it should be possible (by definition) for the compiler to act as if ! implemented every trait, or rather, to ignore errors about it not implementing a particular trait.

e.g. given this definition of an enum:

enum Style<T>
where 
    T: SomeTrait,
{
    Variant1,
    Variant2(T),
}

I propose that it should be valid to use Style<!> directly, so long as one is not instantiating an instance of type Style::Variant2, which would in turn make this legal:

enum Style<T=!>
where 
    T: SomeTrait,
{
    Variant1,
    Variant2(T),
}

Since ! cannot exist, all of Style::Variant2 cannot exist, in which case it doesn't matter if the generic constraint !: SomeTrait is not met; thus allowing the use of Style::Variant1 directly without needing to specify a type for T which will never be used.

With regards to the calculation of the size of the enum: it is provable that Style<!>::Variant2 cannot exist, therefore it should be precluded from the calculation of the size of the type, and treated as a phantom variant with no bearing on the object size. In fact, in the case of such a binary enum with only two types, one of which is purely phantom, the entire enum should be optimized away and it should be treated as a zero-size type altogether (or else the size of Variant1 should Variant1 have any associated values).

[Diggsey]

@mqudsi you should be aware that it's possible to use many trait implementations without ever needing an instance of the type. For example:

trait Foo {
    fn do_something();
}

<! as Foo>::do_something();

Any rule about ! implementing traits must constrain the traits it implements appropriately. (Probably something along the lines of the existing object safety rules for traits).

[mqudsi]

@Diggsey thanks, indeed I hadn't considered that. I think that actually plays nicely with my proposal, since the proposal is to allow its use for any impls that don't require an instance of that type to function.

[H2CO3]

I haven't thought this through fully

Unfortunately, it doesn't really work. Basically, needing to instantiate a value of the type is not the only issue. I've run into this once before, but unfortunately I can't find the discussion anymore. The bottom line is that simply making ! implement every trait automatically is not technically possible, it leads to unsoundness.

[mqudsi]

I think rust needs to have an answer for "I don't want to implement traits I explicitly promise not to use" in order to supply a generic type, and this seems like a good starting place.

The bottom line is that simply making ! implement every trait automatically is not technically possible, it leads to unsoundness.

Well, the nice thing is that it doesn't need to implement/pretend to implemnet everything. We just need a story that would allow for a safe, well-defined subset of cases where it is OK to ignore errors about missing implementations when T = !. As with many other RFCs and language components, it can start off very small and conservative, for explicitly correct cases, and grow from there.

Also since ! is not just a recognized ZST but rather now a core language construct, it can be special cased with impunity (I exaggerate) to improve the ergonomics here.

I'm not positive, but I think the example in the original post is a decent starting place in terms of showing an example of what should be straight-forward behavior with a feature like this, for which there is no great workaround in its absence. (Premise: a library-defined type not intended to be extended by outside users (so supporting foreign impls is not a requirement), with n cases, an optional one of which requires a constrained, generic trait.)

The only alternative I'm seeing here would be to a poor man's enum implemented as a maker trait and sandboxed into its own module to create a fake enum namespace with ZST structs (representing the enum variants) implementing the marker trait, one of which is generic over T. But that basically requires dyn to support mutable cases, lacks pattern matching, can't be defined as an exhaustive collection, etc, etc.

(One possible alternative here is to explicitly impl the trait for !, presuming it is allowed to do so (i.e. when you are the provider of the trait specified in the constraint in question), but there is a very good chance that isn't the case.)

[H2CO3]

it can be special cased with impunity (I exaggerate) to improve the ergonomics here

I think that would be really sad. I think the right direction is making the type system more powerful so that basically any empty enum can be treated as a proper never type. In this case, generalization seems clearly more principled and more ergonomic than special-casing !.

One possible alternative here is to explicitly impl the trait for !, presuming it is allowed to do so (i.e. when you are the provider of the trait specified in the constraint in question), but there is a very good chance that isn't the case.

In this case, I don't see why it should be allowed. Trait coherence rules are there for a reason; as I mentioned previously, exempting a type from it leads to unsoundness.

The only alternative I'm seeing here would be to a poor man's enum implemented as a maker trait and sandboxed into its own module to create a fake enum namespace with ZST structs (representing the enum variants) implementing the marker trait, one of which is generic over T. But that basically requires dyn to support mutable cases, lacks pattern matching, can't be defined as an exhaustive collection, etc, etc.

I'm not sure I fully understand the construct and the concerns here. Can you please provide a specific example?

[mqudsi]

In this case, I don't see why it should be allowed. Trait coherence rules are there for a reason; as I mentioned previously, exempting a type from it leads to unsoundness.

It shouldn't be required to exempt anything, my proposal was to push for (sound) extensions to the type system that would allow for the compiler to not complain when a trait does not implement a type if the dependencies on that trait can only be serviced by an instance of that type, ergo, cannot be used for a never type. You mentioned this leads to unsoundness without providing a specific example, and I countered with "perhaps we can special case this behavior and restrict it to cases that don't lead to unsoundness" which is the best I can counter with given your very abstract rejection of the original proposal.

I'm not sure I fully understand the construct and the concerns here. Can you please provide a specific example?

It's besides the point and not worth going into, it's a way to (partially) work around the absence of such a feature and not actually relevant to this feature request.

[H2CO3]

You mentioned this leads to unsoundness without providing a specific example

As I mentioned, I couldn't find the relevant discussion thread off the top of my head; there was a very good explanation as to why this doesn't work, I'll try to find it.

[mqudsi]

Thanks. Sorry if I was a bit rude.

[H2CO3]

@mqudsi I've found it, it was on IRLO, not GitHub. See KennyTM's, comex's, Centril's, ExHP's, and CAD97's comments for the most important highlights.

[ExpHP]

The tl;dr of that conversation is:

Associated types can be used for type-level programming. As a result, allowing conflicting impls of traits with associated types can lead to badness, even if we try something clever like saying that the associated type is a fresh type inference variable.

---

If we rule out all traits with associated types (in addition of course to those with static methods or consts), then I'm not sure what issues remain. I guess the next issue is Copy + Drop? (we should probably assume it impls Copy, but not Drop.)

(aside: I really wish it was not possible to use Drop as a trait bound...)

[mqudsi]

@H2CO3 Thank you for digging that up, it was quite the interesting read. I see that you kicked off with the discussion with the same suggestion I'm making here!

That said, I think we're fortunate that the direction RFCs take consists of extremely conservative first steps, and I don't think that the objections raised in the thread rise to the level of ruling this feature out altogether.

As @ExpHP says, there is still room for ignoring trait restrictions when it comes to never types (and I'm not talking about the reinterpretation of associated types), except I'm saying there are very easy cases of low-hanging-fruit here that are entirely unaffected by that altogether, an example of which is the enum variant situation illustrated in my original post.

If you forget for a second the original proposal to allow never types to implement everything and you simply focus on the following enum:

enum Style<T=!>
where 
    T: SomeTrait,
{
    Variant1,
    Variant2(T),
}

It is provable that all of Variant2 may be elided without consequence in the event that T is a never type, since it explicitly requires an instance of type T for its instantiation (the type T cannot be accessed from without and functions as a constraint that precludes the possibility of Style::Variant2 ever existing if T is a never type like !).

Now if, at the stage where generics were being resolved into actual types, Style<!> is encountered, it may be optimized to the following,

enum Style<T=!>
where 
    T: SomeTrait,
{
    Variant1,
}

... if and only if the only usage of T was the existence of a variant Variant2 which explicitly requires the existence of an actual object of type T. Normally, that fragment of code would result in a compiler error about an unused generic type, which can safely be omitted/bypassed since it wasn't unused until the compiler optimized Variant2(T) away entirely.

So if we were to say "it's not possible to always pretend ! implements all traits" and therefore change this RFC from "pretend ! implements all traits" to "take small steps one-at-a-time to allow (partial?) elision of type constraints where it is provable that all code dependent on the type in question cannot be reached if the supplied type is a never type," and this specific example being the first step towards fulfilling the ultimate goal of that RFC, would that be acceptable? (Then as a next step it should be possible to also to take @ExpHP's approach and extend this to cases where the code may be accessed with a never type but the trait in question ultimately resolves to an empty trait if all of its features cannot be reached without an explicit instance of the type in question, i.e. the trait does not have any associated types/constants, non-Self functions, etc.)

(I would also like to get this in before someone comes up with an RFC that ultimately enables some clever way of accessing T without first instantiating an instance of Style::Variant2.... unless that's already been done!)

[H2CO3]

I think definitely; properties of never like this can be extremely convenient and elegant at times, we just have to be very careful about soundness. I'd be fine with something like the elision of the impossible-to-construct variant type (as an example).

[ExpHP]

So if we were to say "it's not possible to always pretend ! implements all traits" and therefore change this RFC from "pretend ! implements all traits" to "take small steps one-at-a-time to allow (partial?) elision of type constraints where it is provable that all code dependent on the type in question cannot be reached if the supplied type is a never type," and this specific example being the first step towards fulfilling the ultimate goal of that RFC, would that be acceptable?

You're saying this should be allowed even if the trait is something that ! could not implement? I'm not sure how well such an idea would play with implied bounds.

trait SomeTrait {
    fn method() -> u32;
}

enum Style<T>
where 
    T: SomeTrait,
{
    Variant1,
    Variant2(T),
}

fn lol<T>(_: Style<T>) -> u32 {
    // RFC 2089 says we can assume T impls SomeTrait because
    // one of our arguments is a Style<T>
    <T as SomeTrait>::method()
}

fn main() {
    // meaning that the only place a compiler error could occur
    // must be here somehow
    lol(Style::Variant1::<!>)
}

[scottmcm]

I think that would be really sad. I think the right direction is making the type system more powerful so that basically any empty enum can be treated as a proper never type.

I'm not sure this necessarily follows. One can also make custom unit-like ZST structs, but those aren't completely as privileged as the built-in () is, so there's precedent for the built-in one being special.

[briansmith]

We currently have a pattern pub(crate) mod sealed { pub trait Sealed {} } where a T: sealed::Sealed constraint guarantees that T is implemented within the current crate. ! : sealed::Sealed seems incompatible with this pattern.