Diagnostic forgets about transitive trait bounds when there are multiple candidate impls.

[BGR360]

EDIT this was originally reported as a problem specific to auto-traits, but I don't think it actually is. See the comment below.

EDIT 2: It's actually not specific to specialization either. See this comment

This is spun off from #90601.

Given the following code (playground):

#![feature(min_specialization)]
#![feature(rustc_attrs)]

#[rustc_specialization_trait]
trait Special {}

trait Foo {
    fn foo();
}

impl<T: Send> Foo for T {
    default fn foo() {
        println!("foo");
    }
}

fn main() {
    <std::rc::Rc<()> as Foo>::foo();
}

The current (good) output is:

error[E0277]: `Rc<()>` cannot be sent between threads safely
  --> src/main.rs:18:5
   |
18 |     <std::rc::Rc<()> as Foo>::foo();
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `Rc<()>` cannot be sent between threads safely
   |
   = help: the trait `Send` is not implemented for `Rc<()>`
note: required because of the requirements on the impl of `Foo` for `Rc<()>`
  --> src/main.rs:11:15
   |
11 | impl<T: Send> Foo for T {
   |               ^^^     ^
note: required by `Foo::foo`
  --> src/main.rs:8:5
   |
8  |     fn foo();
   |     ^^^^^^^^^

But if you add a specialized impl of Foo (playground):

#![feature(min_specialization)]
#![feature(rustc_attrs)]

#[rustc_specialization_trait]
trait Special {}

trait Foo {
    fn foo();
}

impl<T: Send> Foo for T {
    default fn foo() {
        println!("foo");
    }
}

impl<T: Send + Special> Foo for T {
    fn foo() {
        println!("special foo");
    }
}

fn main() {
    <std::rc::Rc<()> as Foo>::foo();
}

Then the error message loses all of the information regarding the unimplemented auto trait:

error[E0277]: the trait bound `Rc<()>: Foo` is not satisfied
  --> src/main.rs:24:5
   |
24 |     <std::rc::Rc<()> as Foo>::foo();
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Foo` is not implemented for `Rc<()>`
   |
note: required by `Foo::foo`
  --> src/main.rs:8:5
   |
8  |     fn foo();
   |     ^^^^^^^^^

So there is something about the presence of a specialized impl that causes trait selection to not know that there's an unimplemented auto trait obligation. I have confirmed this by exploring the debug logging of rustc a little bit:

Without specialized impl:
rustc_trait_selection::traits::error_reporting::report_fulfillment_error error=FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<std::rc::Rc<()> as std::marker::Send>, polarity:Positive), []), depth=1),Unimplemented), body_id=Some(BodyId { hir_id: HirId { owner: DefId(0:9 ~ issue_xxxxx_specialization[8170]::main), local_id: 12 } }), fallback_has_occurred=false

With specialized impl:
rustc_trait_selection::traits::error_reporting::report_fulfillment_error error=FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<std::rc::Rc<()> as Foo>, polarity:Positive), []), depth=0),Unimplemented), body_id=Some(BodyId { hir_id: HirId { owner: DefId(0:12 ~ issue_xxxxx_specialization[8170]::main), local_id: 12 } }), fallback_has_occurred=false

If you take a look at Example 4 in #90601, you can see that this can result in detrimentally unhelpful error messages in more complex cases.

cc #13231 #31844 #68970

@rustbot label +A-specialization +A-traits +D-confusing +D-terse +F-auto_traits +F-specialization

[BGR360]

Okay actually I think this has nothing to do with auto traits and is entirely the fault of min_specialization.

If we transform the original example to use a trait bound on a non-auto trait like Display instead of Send, we can see the same regression in the diagnostic.

Before adding a specializing impl (playground):

#![feature(min_specialization)]
#![feature(rustc_attrs)]

use std::fmt::Display;

#[rustc_specialization_trait]
trait Special {}

trait Foo {
    fn foo(&self);
}

impl<T: Display> Foo for T {
    default fn foo(&self) {
        println!("foo: {self}");
    }
}

fn main() {
    let vec = vec![1, 2, 3];
    Foo::foo(&vec);
}

error[E0277]: `Vec<{integer}>` doesn't implement `std::fmt::Display`
  --> src/main.rs:21:14
   |
21 |     Foo::foo(&vec);
   |     -------- ^^^^ `Vec<{integer}>` cannot be formatted with the default formatter
   |     |
   |     required by a bound introduced by this call
   |
   = help: the trait `std::fmt::Display` is not implemented for `Vec<{integer}>`
   = note: in format strings you may be able to use `{:?}` (or {:#?} for pretty-print) instead
note: required for `Vec<{integer}>` to implement `Foo`
  --> src/main.rs:13:18
   |
13 | impl<T: Display> Foo for T {
   |                  ^^^     ^

After adding a specializing impl (playground):

#![feature(min_specialization)]
#![feature(rustc_attrs)]

use std::fmt::Display;

#[rustc_specialization_trait]
trait Special {}

trait Foo {
    fn foo(&self);
}

impl<T: Display> Foo for T {
    default fn foo(&self) {
        println!("foo: {self}");
    }
}

impl<T: Display + Special> Foo for T {
    fn foo(&self) {
        println!("special foo: {self}");
    }
}

fn main() {
    let vec = vec![1, 2, 3];
    Foo::foo(&vec);
}

error[E0277]: the trait bound `Vec<{integer}>: Foo` is not satisfied
  --> src/main.rs:27:14
   |
27 |     Foo::foo(&vec);
   |     -------- ^^^^ the trait `Foo` is not implemented for `Vec<{integer}>`
   |     |
   |     required by a bound introduced by this call

@rustbot label -F-auto_traits

[BGR360]

I think I've narrowed down the cause to this part of rustc_trait_selection:

rust/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs

Lines 140 to 156 in 88a1922

	// If there is more than one candidate, first winnow them down
	// by considering extra conditions (nested obligations and so
	// forth). We don't winnow if there is exactly one
	// candidate. This is a relatively minor distinction but it
	// can lead to better inference and error-reporting. An
	// example would be if there was an impl:
	//
	// impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
	//
	// and we were to see some code `foo.push_clone()` where `boo`
	// is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
	// we were to winnow, we'd wind up with zero candidates.
	// Instead, we select the right impl now but report "`Bar` does
	// not implement `Clone`".
	if candidates.len() == 1 {
	return self.filter_reservation_impls(candidates.pop().unwrap(), stack.obligation);
	}

This is inside of candidate_from_obligation_no_cache. What it's saying is that if there is exactly one candidate impl for the obligation, then return it rather than attempting to filter it out if it doesn't apply. This early return seems to be exactly what allows the more helpful error message to arise later (and the comment even admits this).

So the problem isn't inherent to specialization. Rather, any time there is more than one candidate impl for an obligation, we will fail to give the more helpful error message.

We can reproduce this without specialization by using a trait with a generic parameter.

With only one candidate impl, the error message is helpful (playground):

trait Foo<T> {
    fn foo();
}

trait Bound {}

impl<T: Bound> Foo<u32> for T {
    fn foo() {
        println!("u32 foo");
    }
}

fn main() {
    <() as Foo<_>>::foo();
}

error[E0277]: the trait bound `(): Bound` is not satisfied
  --> src/main.rs:14:5
   |
14 |     <() as Foo<_>>::foo();
   |     ^^^^^^^^^^^^^^^^^^^ the trait `Bound` is not implemented for `()`
   |
note: required because of the requirements on the impl of `Foo<u32>` for `()`
  --> src/main.rs:7:16
   |
7  | impl<T: Bound> Foo<u32> for T {
   |                ^^^^^^^^     ^

But with two candidate impls, the error message is not as helpful (playground):

trait Foo<T> {
    fn foo();
}

trait Bound {}

impl<T: Bound> Foo<u32> for T {
    fn foo() {
        println!("u32 foo");
    }
}

impl<T: Bound> Foo<u64> for T {
    fn foo() {
        println!("u64 foo");
    }
}

fn main() {
    <() as Foo<_>>::foo();
}

error[E0277]: the trait bound `(): Foo<_>` is not satisfied
  --> src/main.rs:20:5
   |
20 |     <() as Foo<_>>::foo();
   |     ^^^^^^^^^^^^^^^^^^^ the trait `Foo<_>` is not implemented for `()`

[BGR360]

I would love some help coming up with a plan for how to improve this. I'm thinking I could do one of two things:

1. Do some really involved logic after the fact in rustc_trait_selection::traits::error_reporting (I already saw one example where the error reporting code just re-calls select_from_obligation).
2. Add a special case to candidate_from_obligation_no_cache: if "winnowing" down the candidates leads to zero candidates, then check if they're all "similar" to each other. If they are, then just return the first one and let the subsequent error reporting reveal the missing nested obligation.

Or perhaps a secret third option where the trait selection cache is able to cache a set of candidates for an obligation.

[BGR360]

Some discussion here: https://rust-lang.zulipchat.com/#narrow/stream/131828-t-compiler/topic/trait_sel.3A.20Advice.20for.20.2390665

[devillove084]

@BGR360 Hey there, I'd like to come and help with this task, but I'm not quite sure how to start, is there some documentation about this module, or rfc of related functions that I can quickly understand.

[BGR360]

Hi @devillove084. Have you read that Zulip thread? The consensus seemed to be that we maybe shouldn't poke at it too much quite yet:

lcnr: i don't have any actionable advice for you here though :/ changing fulfillment errors in this way is probably quite difficult and something i don't have the time for rn

Jack Huey: we should chat sometime, because I have similar thoughts and want to hack on this a bit

See also #103911

[devillove084]

@BGR360 Yes, I did read what you said, and I decided to try to modify it according to what was said.

[BGR360]

Okedoke, well unfortunately I don't have enough experience with this code to give any pointers. You could ask @lcnr or @jackh726