Rule for `!Trait` without `impl Trait` being a breaking change

The Problem

As far as I understand, one of the main reasons why !Trait is disallowed, is because it implies that implementing a trait would be a breaking change. For example, let's say I'm using a trait Foo from an extern crate:

use foo::Foo;
impl<T: !Foo> Bar for T {
 \\ ...
}
let bar: &dyn Bar  = &"hello" // doesn't impl foo

If later, the owner of foo implemented Foo for &'static str, then my code would break. That is because &'static str would no longer be Bar. This means that implementing traits would be a breaking change. So to avoid this, we don't allow negative implementations.

A Possible Solution

The way I would solve this issue, is not to forbid !Trait, but to forbid negative implementations without their complementary counterparts. So the previous example would not compile, unless I implemented impl<T: Foo> Bar for T. Thus, T has to be Bar regardless of whether it implements Foo.

Also, if you think about it, impl<T: !Foo> Bar for T has no real expressivity by itself. It is only useful once you also implement impl<T: Foo> Bar for T, so Rust can distinguish between two different implementations. I think this would be a reasonable restriction, since writing impl<T: !Foo> Bar for T without its complement is no more useful than impl<T> Bar for T. This should also work with trait arithmetic. So you should be able to do something like:

impl<T: A + !B> Foo for T {
    // ...
}
// required by the previous impl block
impl<T: A + B> Foo for T {
    // ...
}

Drawbacks

As you increase the number of negative traits, the number of implementations required to satisfy this rule increases exponentially. Specifically, the number of separate implementations is 2^n, where n is the number of negative traits. Also, it seems to be that some details about how to implement !Traits haven't really been fully worked out yet.

5 Likes

It would also be able to help with doing impl<T: !Default> Default for [T; 0] but maybe that is what specialization is for.

3 Likes

Isn't it what specialization literally is?

1 Like

Oh, I haven't read about specialization. Is it equivalent to what I just said?

EDIT:

It seems specialization does address the same problems that I wanted to solve. So this proposal wouldn't be that useful. Although I guess it could help with auto traits.

Unfortunately, this does share the same soundness issue as specialization, because it would allow two types that differ only in lifetimes to have different impls for the same trait. (In your example, suppose Foo was implemented for &'static str, but not for any other &'a str.)

The soundness issue may be fixable (someday), but it would likely require additional annotations on trait bounds of specialized impls, which breaks the 'just an extension of existing features' aspect of your proposal.

Isn't the fix the same as for full HKTs - require picking the impl explicitly?

Oh, I see the issue. Well, I hope they figure a way around it.

Ok this may just be a terrible solution, but what if under any conflict the type checker chooses the negative implementation. So if we have something like:

trait Foo {}

trait Bar {
    fn bar();
}

impl Foo for &'static str {}

impl<T: !Foo> Bar for Foo {
    fn bar() {
        println!("not Foo")
    }
}

impl<T: Foo> Bar for Foo {
    fn bar() {
        println!("Foo")
    }
}

let x: &'static = "asd";
x.foo() // prints "not Foo"

Since negative implementations always have less bounds than positive ones, it is always safe to downcast the 'static to just 'a, (or I believe it to be so). It may not be very satisfying but it should be sound right?