Regression in 1.56.0 - Trait bound not satisfied error even though the impl exists

[AzureMarker]

Code

I tried this code (minimized from this test in my library):

trait HasProvider<T: ?Sized> {}
trait Provider<M> {
    type Interface: ?Sized;
}

trait Repository {}
trait Service {}

struct DbConnection;
impl<M> Provider<M> for DbConnection {
    type Interface = DbConnection;
}

struct RepositoryImpl;
impl<M: HasProvider<DbConnection>> Provider<M> for RepositoryImpl {
    type Interface = dyn Repository;
}

struct ServiceImpl;
impl<M: HasProvider<dyn Repository>> Provider<M> for ServiceImpl {
    type Interface = dyn Service;
}

struct TestModule;
impl HasProvider<<DbConnection as Provider<Self>>::Interface> for TestModule {}
impl HasProvider<<RepositoryImpl as Provider<Self>>::Interface> for TestModule {}
impl HasProvider<<ServiceImpl as Provider<Self>>::Interface> for TestModule {}

fn main() {}

I expected to see this happen: Compile without errors.

Instead, this happened: Compiled with errors:

error[E0277]: the trait bound `TestModule: HasProvider<(dyn Repository + 'static)>` is not satisfied
  --> shaku/tests/debug_rust_1_56.rs:26:6
   |
26 | impl HasProvider<<RepositoryImpl as Provider<Self>>::Interface> for TestModule {}
   |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `HasProvider<(dyn Repository + 'static)>` is not implemented for `TestModule`
   |
   = help: the following implementations were found:
             <TestModule as HasProvider<(dyn Repository + 'static)>>
             <TestModule as HasProvider<<ServiceImpl as Provider<TestModule>>::Interface>>
             <TestModule as HasProvider<DbConnection>>
note: required by a bound in `HasProvider`
  --> shaku/tests/debug_rust_1_56.rs:1:1
   |
1  | trait HasProvider<T: ?Sized> {}
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `HasProvider`

error[E0277]: the trait bound `TestModule: HasProvider<(dyn Repository + 'static)>` is not satisfied
  --> shaku/tests/debug_rust_1_56.rs:27:6
   |
27 | impl HasProvider<<ServiceImpl as Provider<Self>>::Interface> for TestModule {}
   |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `HasProvider<(dyn Repository + 'static)>` is not implemented for `TestModule`
   |
   = help: the following implementations were found:
             <TestModule as HasProvider<(dyn Repository + 'static)>>
             <TestModule as HasProvider<<ServiceImpl as Provider<TestModule>>::Interface>>
             <TestModule as HasProvider<DbConnection>>
note: required because of the requirements on the impl of `Provider<TestModule>` for `ServiceImpl`
  --> shaku/tests/debug_rust_1_56.rs:20:38
   |
20 | impl<M: HasProvider<dyn Repository>> Provider<M> for ServiceImpl {
   |                                      ^^^^^^^^^^^     ^^^^^^^^^^^

error: aborting due to 2 previous errors

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

Note that it says HasProvider<(dyn Repository + 'static)> is not implemented for TestModule, but then lists it as an existing implementation.

Version it worked on

It most recently worked on: 1.55.0

Version with regression

rustc --version --verbose:

rustc 1.56.0 (09c42c458 2021-10-18)
binary: rustc
commit-hash: 09c42c45858d5f3aedfa670698275303a3d19afa
commit-date: 2021-10-18
host: x86_64-unknown-linux-gnu
release: 1.56.0
LLVM version: 13.0.0

[AzureMarker]

@rustbot modify labels: +regression-from-stable-to-stable

[camelid]

Bisects to #85868. cc @Aaron1011 @jackh726

---

searched nightlies: from nightly-2021-07-01 to nightly-2021-10-01
regressed nightly: nightly-2021-09-03
searched commits: from 50171c3 to 371f3cd
regressed commit: 371f3cd

bisected with cargo-bisect-rustc v0.6.0

Host triple: x86_64-apple-darwin
Reproduce with:

cargo bisect-rustc --preserve --regress=error --start=2021-07-01 --end=2021-10-01 -- check 

[apiraino]

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-high

[elertan]

Any advancements on this issue? I currently can't upgrade to Rust 1.56 due to this exact problem