Overflow evaluating the requirement with a where clause on associated type

[bugaevc]

I tried this code (playground):

#![feature(generic_associated_types)]

use std::fmt::Debug;

trait Foo {
    type Ass where Self::Ass: Debug;
}

#[derive(Debug)]
struct Bar;

impl Foo for Bar {
    type Ass = Bar;
}

Note that while it doesn't use GATs, it requires feature(generic_associated_types) for the where clause on the associated type to be allowed.

I expected to see this happen: this should build without errors.

Instead, this happened:

error[E0275]: overflow evaluating the requirement `<Bar as Foo>::Ass == _`
  --> src/lib.rs:12:5
   |
12 |     type Ass = Bar;
   |     ^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0275`.

Error E0275 explanation uses this example:

trait Foo {}

struct Bar<T>(T);

impl<T> Foo for T where Bar<T>: Foo {}

where indeed there's a recursive requirement that can't be checked in a small number of steps. Not so in my example: there's no recursion; Bar clearly implements Debug (and Foo).

@rustbot modify labels: +A-associated-items +F-generic_associated_types

[jackh726]

Effectively a duplicate of #80807, but obviously a bit different since the where clause here is on the associated type

(note, I'm going to leave some notes here from me playing with this, some directly related, some indirectly)

This is difficult. The general idea of why this is a problem is:

To prove that <Bar as Foo>::Ass: Sized
We try to project <Bar as Foo>::Ass
We first select the impl impl Foo for Bar
To confirm, we require that ::Ass: Debug
So, we try to project <Bar as Foo>::Ass, which is a cycle
So, we register the obligation <Bar as Foo>::Ass -> _#0t
Later, we can't overwrite <Bar as Foo>::Ass, because of here

Effectively reverting #80246 does fix this, but then impl-wf-cycle-1.rs regresses (and only that) because

We try to project <(_#0t,) as Grault>::A
So, we have to select an impl for <(_#0t,) as Grault>
We find DefId(0:12 ~ impl_wf_cycle_1[2856]::{impl#3})
To confirm, we try to prove <<(_#1t,) as Grault>::A as Baz>
We try to project <<(_#1t,) as Grault>::A, completing the cycle

I'm not convinced that #80246 is the right fix. It solves impl-wf-cycle-1.rs by failing a bit earlier than the above cycle, but so far I haven't had any luck with alternative fixes.

I do have a branch (https://github.com/jackh726/rust/tree/projection-recursion) that first tries to normalize a canonicalized projection type, but this isn't really correct as-is because we rely on being able to recover from a cycle. Also, it would be nice to be able to return "canonical obligations", instead of having to fully solve a canonical normalization. But something along this line detecting when we end up with a cycle where we effectively can't make any progress is probably the right answer.

Another alternative I've thought about is in match_impl. The is the bit of code that is responsible for picking the substitution for an impl that matches.

match_impl details

Let's start by imagining
impl<T, U> Foo for Vec<T> where T: Iterator<Item = U> {}
And there is an impl

impl Iterator for Bar {
    type Item = ()
}

If we then had the predicate <Vec<Bar> as Foo>
We try to match against the impl <Vec<T> as Foo>

First, we create fresh substs [?0, ?1]
Then, we subst and create <Vec<?0> as Foo>
When we equate, we get ?0 = Bar

Later, we try to confirm the impl with substs [?0, ?1]
We see the predicate <T as Iterator>::Item == U
We substitute: <?0 as Iterator>::Item == ?1
We register that obligation

Later, when we try to solve that obligation:
We resolve ?0 to Bar
We normalize <Bar as Iterator>::Item to ()
We equate ?1 to ()
No problems, so obligation is proven

The idea is to either 1) not create fresh inference vars for parts of the impl_trait_ref that we have specified or 2) detect when an impl matches, but when we've made no "progress" and report a cycle error, i.e. all inference vars only resolve to other inference vars (though, I wonder if we need an exception here for when those vars appear in where clauses)

Another solution would be to have the impl_or_trait_obligations code let us assume that Self::Assoc normalizes to the associated type defined on the current impl (but this is "coinductive" and may have some interaction with specialization). This also requires us to "stop" after we see a matching predicate in the param_env (which we already do for object candidates)

Finally, we could potentially delay normalization in impl_or_trait_obligations, but this is potentially difficult and wouldn't necessarily fix the problem.

[jackh726]

GATs issue triage: not blocking. Not strictly a GATs issue; you can run into similar problems with a where clause on the trait itself. Unfortunate, but a larger class of issues.