Default impls cannot reliably expose type inequality

[ebfull]

trait NotSame { }
impl NotSame for .. { }
impl<A> !NotSame for (A, A) { }

If I understand default impls right, it should be possible to express S != T using (S, T): NotSame. In fact this does work in some situations, but not generally.

doesn't work:

#![feature(optin_builtin_traits)]

trait NotSame { }
impl NotSame for .. { }
impl<A> !NotSame for (A, A) { }

fn f<T, U>(_: T, _: U) where (T, U): NotSame {}

struct S;
struct Z;

fn main() {
    f(S, Z); // error: the trait `NotSame` is not implemented for the type `(_, _)`
    f(S, S); // error: the trait `NotSame` is not implemented for the type `(_, _)`
}

but this does:

#![feature(optin_builtin_traits)]

use std::marker::PhantomData;

trait NotSame { }
impl NotSame for .. { }
impl<A> !NotSame for (A, A) { }

struct Choose<S, P>(PhantomData<(S, P)>);
struct Finally<P>(PhantomData<P>);

pub trait Chooser<T> {
    fn num() -> usize;
}

impl<S, Q> Chooser<S> for Choose<S, Q> {
    fn num() -> usize { 0 }
}

impl<S> Chooser<S> for Finally<S> {
    fn num() -> usize { 0 }
}

impl<R, S, Q: Chooser<S>> Chooser<S> for Choose<R, Q>
    where (S, R): NotSame
{
    fn num() -> usize { Q::num().checked_add(1).unwrap() }
}

fn main() { }

Perhaps it only works when trying to ensure there are no conflicting impls? Perhaps it's not meant to work, and the second example is a hole?

[Aatch]

I think that being able to express type inequality at all is just a side-effect. Default impls like that aren't stable and the semantics aren't concrete right now.

@rust-lang/lang might have some input?

[arielb1]

It looks like this just interacts badly with type inference.

[bluss]

If it would compile, type inequality gives you ad-hoc specialization (code example).

The specialization passes trait coherence checks, and both can be called, but indeed it does not infer to the right implementation in a regular method call.

Edit: Oh wow, making the iterator the Self type instead, the “dream specialization” for extend works.

[wthrowe]

I believe that the fact that that impl is accepted is a known bug. (In particular, the first point of #13231.)

[Manishearth]

I agree with Aatch, this is a side effect. I do wish we had a way of expressing type inequality, but this isn't the way to go about it.

[rphmeier]

Additionally, this lead to an ICE when I tried to take it to the next step: tuples where every type is different.

#![feature(optin_builtin_traits)]

trait NotSame {}
impl NotSame for .. {}
impl<A> !NotSame for (A, A) {}

trait OneOfEach {}

impl <A> OneOfEach for (A) { }

impl <A, B> OneOfEach for (A, B) where (B): OneOfEach, (A, B): NotSame { }

impl <A, B, C> OneOfEach for (A, B, C) where (B, C): OneOfEach, (A, B): NotSame,
(A, C): NotSame {}


fn main() {}

robert@laptop:~/projects/one_of_each$ RUST_BACKTRACE=1 rustc one_of_each.rs
one_of_each.rs:11:1: 11:75 error: internal compiler error: coherence failed to report ambiguity: cannot locate the impl of the trait `OneOfEach` for the type `(A, B)`
one_of_each.rs:11 impl <A, B> OneOfEach for (A, B) where (B): OneOfEach, (A, B): NotSame { }
                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: the compiler unexpectedly panicked. this is a bug.
note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports
thread 'rustc' panicked at 'Box<Any>', ../src/libsyntax/diagnostic.rs:176
stack backtrace:
   1:     0x7f8e6d26fd20 - sys::backtrace::tracing::imp::write::h5839347184a363c1Tnt
   2:     0x7f8e6d2765e5 - panicking::log_panic::_<closure>::closure.39955
   3:     0x7f8e6d276055 - panicking::log_panic::hcde6d42710304abbWnx
   4:     0x7f8e6d239683 - sys_common::unwind::begin_unwind_inner::h4039843fef6bffefYgs
   5:     0x7f8e670c63c7 - sys_common::unwind::begin_unwind::begin_unwind::h17811388397816602357
   6:     0x7f8e670c6386 - diagnostic::_<impl>::span_bug::h517cd016f9a1ed4fqGA
   7:     0x7f8e6b04f4a0 - middle::traits::error_reporting::report_fulfillment_errors::h7b40fdbf7b69efa1DqR
   8:     0x7f8e6bdf69b5 - check::_<impl>::select_all_obligations_or_error::h68d2b62f895fda24Nar
   9:     0x7f8e6be4d9a4 - check::wf::_<impl>::check_item_well_formed::h294fa0c9be11cb26O4j
  10:     0x7f8e6be8bfbe - check::check_wf_old::h2896130387effa64m9o
  11:     0x7f8e6bf3b8ab - check_crate::hbd4bd8f4f3340ed1BrD
  12:     0x7f8e6d7438b9 - driver::phase_3_run_analysis_passes::_<closure>::closure.21990
  13:     0x7f8e6d729213 - middle::ty::context::_<impl>::create_and_enter::create_and_enter::h7648551165536465273
  14:     0x7f8e6d72420e - driver::phase_3_run_analysis_passes::h13807885485637783892
  15:     0x7f8e6d704c92 - driver::compile_input::he5c7814d86abe8678ba
  16:     0x7f8e6d85badb - run_compiler::h3e946a4e9bc089bfvqc
  17:     0x7f8e6d858b56 - sys_common::unwind::try::try_fn::try_fn::h18225326314371046170
  18:     0x7f8e6d26da48 - __rust_try
  19:     0x7f8e6d261abb - sys_common::unwind::try::inner_try::h81e998e565f2181dwds
  20:     0x7f8e6d858ea4 - boxed::_<impl>::call_box::call_box::h16507595822000360715
  21:     0x7f8e6d2750b3 - sys::thread::_<impl>::new::thread_start::h0be42f811434f5398Fw
  22:     0x7f8e6691c181 - start_thread
  23:     0x7f8e6ceef47c - __clone
  24:                0x0 - <unknown>

On rustc 1.6.0-nightly (1a2eaff 2015-10-31)

[Manishearth]

File a separate bug?

[ebfull]

Will default impls will be expressive enough if they aren't capable of expressing type inequality in this way? It seemed like a no-brainer when I wrote it. Obviously the language should support it with native syntax as well-- sooner rather than later, to avoid hacks like this from becoming commonplace.

[nikomatsakis]

I don't think that this impl:

impl !NotSame for (A, A) { }

is intended to work. I thought we had some restrictions to this effect, but perhaps we only placed them on positive impls. This is in a sense a kind of coherence violation -- there is a default, builtin impl for tuples that this interacts with.

But in general the expressive power of negative impls is not firmly settled and will be changing. It's something that we need to make firmer decisions on (and there is also clear interaction with ongoing design, such as specialization, rust-lang/rfcs#1148, and catch panic).

[Ms2ger]

impl <A> OneOfEach for (A) { }

Did you mean (A,)?

[arielb1]

@bluss

You don't exactly have specialization, because you can't have a generic method use extend. Anyway, OIBITs were basically intended as "structural impls with negative impls for opt-out".

[rphmeier]

@Ms2ger As I addressed in the separate issue, I am aware that (A) is not correct, strictly speaking. When you compile it with the trailing comma, it works (mostly) as expected. The important point is that the ICE occurs at all.