trait selection arbitrarily resolves projection ambiguities

[benjaminp]

trait Print<T> {
    fn print(self);
}

impl Print<char> for () {
    fn print(self) {
        println!("char");
    }
}

impl Print<usize> for () {
    fn print(self) {
        println!("usize")
    }
}

fn make1() -> impl Print<char> + Print<usize> {}

fn make2() -> impl Print<usize> + Print<char> {}

fn main() { 
    make1().print();
    make2().print();
}

The above program (https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2e211dacba7209200273bf1bc6a2b77f) prints

usize
char

Not only does rustc pick without guidance between Print<char>::print and Print<usize>::print, but it depends on the ordering of the predicates in the impl traits!

This problem happens because trait selection wants to prove that make1() implements Print. To do that, it arbitrarily selects Print<usize> even though the Print<char> bound would also suffice at the time of inference. It makes the opposite eager selection for make2().

The same problem underlies #66057, where eager selection of projection bounds prevents further inference from removing the ambiguity.

Analogous problems exist for associated traits with multiple predicates as they go through the same trait selection code path.

[jonas-schievink]

Seems like this code maybe shouldn't compile without using fully-qualified function syntax <_ as Print<char>>::print(make1()), so marking for prioritization

[apiraino]

Assigning P-medium as discussed as part of the Prioritization Working Group procedure and removing I-prioritize.

[Aaron1011]

The issue occurs here:

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

Lines 1343 to 1353 in c0b15cc

	let matching_bound = predicates.iter().find_map(|bound| {
	if let ty::PredicateAtom::Trait(pred, _) = bound.skip_binders() {
	let bound = ty::Binder::bind(pred.trait_ref);
	if self.infcx.probe(|_| {
	self.match_projection(obligation, bound, placeholder_trait_predicate.trait_ref)
	}) {
	return Some(bound);
	}
	}
	None
	});

We pick the first matching predicate from the projection predicates of the opaque type, without checking if multiple match.

[benjaminp]

#73905 turned this into a compiler error.