Unexpected behaviors of trait bounds

I have difficulty reason about how trait bounds work in this following examples. Would appreciate any hints on what's going on, why is that, or if some of these are just bugs.

Let's say we have this taxonomy:

pub trait Partial: Copy {
    fn foo() -> Option<Self>;
}

pub trait Complete where Self: Partial + Default {
    fn foo() -> Self;
}

impl<T> Partial for T where T: Complete {
    fn foo() -> Option<Self> {
        Some(<Self as Complete>::foo())
    }
}

pub trait Orthogonal: Partial {}

Now, here's one usage of the taxonomy, defining a Partial type:

#[derive(Clone, Copy)]
enum TypeA {
    A,
}

impl Partial for TypeA {
    fn foo() -> Option<Self> {
        None
    }
}

And there's another one, defining a Complete type:

enum TypeB {
    B,
}

impl Default for TypeB {
    fn default() -> Self {
        TypeB::B
    }
}

impl Complete for TypeB {
    fn foo() -> Self {
        TypeB::B
    }
}

These compile without error.

Question 1

Why TypeB works here even though it has not implemented Copy, which is required by Partial? Not having Copy implemented for TypeA results in a compile error.

Question 2

Now let's try to define another with Orthogonal implementation:

enum TypeC {}

impl Orthogonal for TypeC {}

I would get this error:

error[E0277]: the trait bound `traits::TypeC: traits::Complete` is not satisfied
  --> src/traits.rs:61:6
   |
61 | impl Orthogonal for TypeC {}
   |      ^^^^^^^^^^ the trait `traits::Complete` is not implemented for `traits::TypeC`
   |
   = note: required because of the requirements on the impl of `traits::Partial` for `traits::TypeC`
   = note: required by `traits::Orthogonal`

Which is not accurate, because implementing Partial is just enough here and Complete is not required.

What do you think?

1 Like

Answer to question 1

TypeB::B works in Default and Foo because the value is not copied when it is returned, it is moved. As the method ends after returning as the implementations does not store the returned value the compiler does not need to copy the object it just moves it to its new location.

For TypeA::A it doesn't work because you implement Partial for TypeA and Partial requires Copy to be implemented for all types implementing it (due to the bound trait Partial: Copy ...). It does not mean that moving couldn't be done in this situation, but you explicitly forbade it with the bound.

A bound on a trait ala trait Partial: Copy ... states what must be implemented by a type if it implements Partial.

1 Like

Well question 1 is a compiler bug.


fn main() {
    crash(TypeB::B);
}

fn crash<P: Partial>(p: P) {
    p.clone();
}
error: internal compiler error: /checkout/src/librustc/traits/trans/mod.rs:76: Encountered error `Unimplemented` selecting `Binder(<TypeB as std::clone::Clone>)` during trans

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>', /checkout/src/librustc_errors/lib.rs:428
note: Run with `RUST_BACKTRACE=1` for a backtrace.
4 Likes

Answer to question 2

Orthogonal requires Partial to be implemented for TypeC. As you didn't provide such an implementation, the compiler looks for a generic implementation and finds one: impl<T> Partial for T where T: Complete
This states that Partial can be implemented for any type T. So the compiler tries to do that---and fails. Why? Because the where clause requires of T (which is subsituted with TypeC in our case) that it implements Complete. TypeC does not implement Complete and the compilation fails due to unsatisfied requirements.

You would either need to implement Complete for TypeC or provide a specialized implementation of Partial for TypeC.

3 Likes

As mentioned by @dtolnay, the answer for question 1 is that it's a bug. It's probably getting confused because the implementation of Complete depends on the blanket implementation of Partial, which depends on the implementation of Complete. The compiler is probably neglecting to check the supertraits of Partial when it resolves this cycle.

For question 2, the reason it complains about Complete instead of Partial is that, when it fails to find an implementation of Partial, it then tries to use the blanket impl

impl<T> Partial for T where T: Complete

and then discovers that TypeC doesn't implement Complete. It's maybe being a bit too helpful, since you might want to implement Partial directly. There's already an issue for this (#28894).

1 Like

I think it's a bug. Whether something is moved or not shouldn't have an effect on type checking trait constraints. The function can change later to make use of Copy and that shouldn't change compilation outcome, at least in terms of type checking.

1 Like

Awesome! Thanks @dtolnay and @mindsbackyard @stevenblenkinsop for the responses.

So, Question 1 is a compiler type checking bug, apparently. Just as a reminder, I used Copy as an example trait that I'm interested in for my model. It can, indeed, be any other trait and resulting the same behavior. I'll report the bug with a minimal repro.

For Question 2, now I see what's happening internally. So, I would argue that the bug is in the error reporting: it's claiming something is required (Complete being implemented) when it's actually only one of the options (another option being implementing Partial). I'll file a bug for this, as well.

2 Likes

Seems very likely. If you just paste the given code it compiles fine, though I haven't tried to actually use the implementation. Though I guess the function should move the value (if there wasn't a bug) in this case as Copy is not implemented. And in the other case Copy is explicitly requested, so can't be omitted.

For question one, you might want to mention that it might be a variant of #29859, which is closed. For question 2, I'm pretty sure it is #28894.

2 Likes

Right but only cause it's a bug :smile:

It shouldn't compile if there was no bug.

Copy vs move is a semantic thing - a move copies data too, just like copy (technically, neither needs to happen once the optimizer gets its hands on it). Only difference is compiler tracks moved-from values and doesn't allow using them again, whereas Copy is left intact. In this case the distinction really doesn't matter because there's no lvalue to move from.

Filed this for the first issue: https://github.com/rust-lang/rust/issues/43777

For the second, commented on the related existing open issue: https://github.com/rust-lang/rust/issues/28894#issuecomment-321402485

Thanks all!

3 Likes

There is a fix on the way for question 1 in rust-lang/rust#43786.

3 Likes