How does Rust compile this example with cyclic trait bounds?

user_15255830 0
Viewed 64

I'm having trouble understanding how the following example, distilled from this code, compiles:

trait A: B {}
trait B {}
impl<T> B for T where T: A {}

struct Foo;
impl A for Foo {}

fn main() {}

My current understanding is that

Supertraits are traits that are required to be implemented for a type to implement a specific trait.

  • impl<T> B for T where T:A implements B for any type with the trait A .

I expect impl A for Foo to fail because before A is implemented for Foo, the blanket implementation can't implement B for Foo, which is required.

My most plausible model for what rustc does while compiling the snippet is as follows:

  • implement A for Foo, deferring the check that Foo implements B to a later stage
  • implement B for Foo with the blanket implementation, since Foo now implements A
  • check that Foo implements B as required by the trait bound A: B

Is this in some way close to the truth? Is there any documentation I missed explaining the order in which implementations are processed?

rust
1 Answers

rustc doesn't work "in order". Rather, we first register all impls and then type-check each impl with no particular order. The idea is that we collect a list of obligations (of various kinds - one of them is a trait bound), and then we match them against impls (not just; this is only one way to resolve an obligation, but this is what relevant here). Each obligation can create another, recursive obligations and we elaborate them until there are no more.

The way it currently works is that when we check an impl Trait for Type, we add an obligation Type: Trait. This might seem silly, but we later elaborate it further until all required bounds are met.

So let's say we're currently checking impl<T> B for T where T: A. We add one obligation, T: B, and match it against impl B for T. There is nothing to elaborate further, so we finish successfully.

We then check impl A for Foo, and add an obligation Foo: A. Since the trait A requires Self: B, we add another obligation Foo: B. Then we start matching obligations: the first obligation, Foo: A, is matched by the currently processed impl with no additional obligations. The second obligation, Foo: B, is matched against impl<T> B for T where T: A. This has a new obligate - T: A or Foo: A - so we try to match that. We successfully match that against impl A for Foo, with no additional obligations.

An interesting implication of the above is that if we change the second impl to the following:

impl A for Foo where Foo: B {}

Then this no longer compiles with an "overflow evaluating the requirement Foo: A" error (playground), even though it is essentially the same, because now to prove that Foo: A rustc needs to prove that Foo: B and again that Foo: A, while previously it just registered an obligation for Foo: B and not proved it immediately.

Note: The above is an over-simplification: for example, there is also a cache, and well-formed obligations, and much more. But the general principle is the same.

user_78843050
Related