Impls for GAT-parameterized objects with bounds on specific instantation of GAT type result in incorrect mismatched type errors

Let me first say thank you for implementing GATs, and also apologize for the heinous haskell-brained madness you see before you. With that out of the way:

I tried to compile this code (https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=674f6412128946f9ef6abf6ddd15dcf7):

pub trait Functor {
    type Layer<X>;
}

pub trait FunctorExt: Functor {
    fn expand_and_collapse<In, Out>(
        seed: In,
        expand: impl Fn(In) -> <Self as Functor>::Layer<In>,
        collapse: impl Fn(<Self as Functor>::Layer<Out>) -> Out,
    ) -> Out;
}

impl<X> FunctorExt for X
where
    X: Functor,
{
    fn expand_and_collapse<In, Out>(
        seed: In,
        expand: impl Fn(In) -> <X as Functor>::Layer<In>,
        collapse: impl Fn(<X as Functor>::Layer<Out>) -> Out,
    ) -> Out {
        todo!()
    }
}

struct Repro<F>(std::marker::PhantomData<F>);

impl<F: Functor> Repro<F>
where
    // The following 'u8' ties the use of F::Layer in the repro fn to 'u8'
    // if this line is commented out, it compiles successfully
    F::Layer<u8>: Clone,
{
    fn repro(x: ()) {
        // there is no reason to expect 'F::Layer<u8>' here
        <F as FunctorExt>::expand_and_collapse(x, |x| todo!(), |_x| ());
    }

    // it works if you provide type annotation, although I do have a much more complex case
    // that I wasn't able to minimize where even type annotations don't fix the problem
    fn works(x: ()) {
        <F as FunctorExt>::expand_and_collapse(
            x,
            |x: ()| -> F::Layer<()> { todo!() },
            |_x: F::Layer<()>| -> () { () },
        );
    }
}

I expected it to compile.

Instead, it failed with

error[[E0308]](https://doc.rust-lang.org/stable/error-index.html#E0308): mismatched types
  --> src/lib.rs:37:69
   |
37 |         <F as FunctorExt>::expand_and_collapse(x, |x| todo!(), |_x| ());
   |                                                                     ^^ expected `u8`, found `()`

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` due to previous error

Note: the F::Layer<u8>: Clone bound is not used anywhere in this code, and if that line is commented out, this code compiles.

Meta

The bug occurs in stable and nightly on play.rust-lang.org: 1.66.1 1.68.0-nightly

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=674f6412128946f9ef6abf6ddd15dcf7

Here's a minimized version of this:

pub trait Trait {
    type Assoc<A>;
}

fn test<T: Trait>()
where
    T::Assoc<u8>: Sized,
{
    constrain::<T, _>(1i32);
    // Registers `T::Assoc<_>: Sized`, which is eagerly satisfied by `T::Assoc<u8>: Sized`.
    // That means we infer the argument type to be u8.
}

fn constrain<T: Trait, A>(_: A)
where
    T::Assoc<A>: Sized,
{}

Specifically, when we're required to prove T::Assoc<_>: Sized and we have some where-clause bound T::Assoc<u8>: Sized, we over-eagerly infer the type variable _ to be equal to u8.

In the example provided, the Clone bound implies a Sized bound here which is the "real culprit", and the place where we're required to prove that Sized bound is in the closure args.

although I do have a much more complex case that I wasn't able to minimize where even type annotations don't fix the problem

@inanna-malick I'd be curious to see the example you said you couldn't fix/minimize, if you're able to share it.

@compiler-errors I can share it, it's just, well - it's not proprietary, it's just ideas translated directly to code without much thought of readability:

I was able to get it working using the Shim workaround here https://github.com/inanna-malick/dag-cache/blob/47706a801bee459bffeab5cf495bc2bf2e4a3a16/dag-store/src/client.rs#L82, but even though I added types to all the closures I still got a compile error.

if the F::Layer<domain::Header>: Clone, line at https://github.com/inanna-malick/dag-cache/blob/47706a801bee459bffeab5cf495bc2bf2e4a3a16/dag-store/src/client.rs#L124 is commented out this compiles - as in the above example, this trait bound is not used anywhere in the impl block

error (at https://github.com/inanna-malick/dag-cache/blob/47706a801bee459bffeab5cf495bc2bf2e4a3a16/dag-store/src/client.rs#L202)


error[E0308]: mismatched types
   --> dag-store/src/client.rs:202:17
    |
202 | /                 <Compose<MerkleLayer<PartiallyApplied>, F> as FunctorExt>::expand_and_collapse(
203 | |                         header,
204 | |                         |header: Header| -> <Compose<MerkleLayer<PartiallyApplied>, F> as Functor>::Layer<
205 | |                             Header,
...   |
217 | |                         },
218 | |                     )
    | |_____________________^ expected enum `MerkleLayer`, found struct `Header`
    |
    = note: expected enum `MerkleLayer<Fix<Compose<F, MerkleLayer<PartiallyApplied>>>>`
             found struct `dag_store_types::types::domain::Header`
help: try wrapping the expression in `client::MerkleLayer::Remote`
    |
202 ~                 client::MerkleLayer::Remote(<Compose<MerkleLayer<PartiallyApplied>, F> as FunctorExt>::expand_and_collapse(
203 |                         header,
  ...
217 |                         },
218 ~                     ))
    |

error[E0631]: type mismatch in closure arguments
   --> dag-store/src/client.rs:202:17
    |
202 |                 <Compose<MerkleLayer<PartiallyApplied>, F> as FunctorExt>::expand_and_collapse(
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected due to this
...
213 |                         |layer: MerkleLayer<<F as Functor>::Layer<MerkleLayer<Fix<Compose<F, MerkleLayer<PartiallyApplied>>>>>>| -> MerkleLayer<Fix<Compose<F, MerkleLayer<PartiallyApplied>>>>   {
    |                         ----------------------------------------------------------------------------------------------------------------------------------------------------------------------- found signature defined here
    |
    = note: expected closure signature `fn(MerkleLayer<<F as Functor>::Layer<dag_store_types::types::domain::Header>>) -> _`
               found closure signature `fn(MerkleLayer<<F as Functor>::Layer<MerkleLayer<Fix<Compose<F, MerkleLayer<PartiallyApplied>>>>>>) -> _`
note: required by a bound in `recursion_schemes::functor::FunctorExt::expand_and_collapse`
   --> /home/inanna/.cargo/registry/src/github.com-1ecc6299db9ec823/recursion-schemes-0.1.2/src/functor.rs:60:30
    |
60  |         collapse_layer: impl FnMut(<Self as Functor>::Layer<Out>) -> Out,
    |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `FunctorExt::expand_and_collapse`

wa

here's my rustc version output:

➜  dag-store git:(adding_client) ✗ rustc --version --verbose
rustc 1.68.0-nightly (61a415be5 2023-01-12)
binary: rustc
commit-hash: 61a415be590113b4935464ef0aaf3b4e7713a077
commit-date: 2023-01-12
host: x86_64-unknown-linux-gnu
release: 1.68.0-nightly
LLVM version: 15.0.6

Someone on URLO encountered what I believe is this issue in lifetime form.

In the following code, the compiler thinks you're trying to call get with a lifetime of 'b within test_fun, but that's not actually necessary.

trait Get {
    type T<'a> where Self: 'a;
    fn get(&self) -> Self::T<'_>;
}

// Note that we don't actually *need* to generate a `T` in the function body
fn test_fun<'b, T>(get_to: T) where T: Get<T<'b> = T> + 'b {
    get_to.get(); // So this could be called with something besides &'b get_to
}

Current error:

error[[E0597]](https://doc.rust-lang.org/stable/error-index.html#E0597): `get_to` does not live long enough
 --> src/lib.rs:8:5
  |
7 | fn test_fun<'b, T>(get_to: T) where T: Get<T<'b> = T> + 'b {
  |             -- lifetime `'b` defined here
8 |     get_to.get(); // So this could be called with something besides &'b get_to
  |     ^^^^^^^^^^^^
  |     |
  |     borrowed value does not live long enough
  |     argument requires that `get_to` is borrowed for `'b`
9 | }
  | - `get_to` dropped here while still borrowed

This attempt to accept a bound on one specific lifetime also fails.

fn test_fun<'b, T, U>(get_to: U, other: &'b T) -> T
where
    U: Get,
    T: Get<T<'b> = T>,
    T: Get<T<'b> = U>,
{
    get_to.get();
    other.get()
}

Current error:

error[[E0284]](https://doc.rust-lang.org/stable/error-index.html#E0284): type annotations needed: cannot satisfy `<T as Get>::T<'_> == T`
  --> src/lib.rs:13:11
   |
13 |     other.get()
   |           ^^^ cannot satisfy `<T as Get>::T<'_> == T`

And being more explicit doesn't really change things in this case.

    <T as Get>::get::<'b>(other)

error[[E0284]](https://doc.rust-lang.org/stable/error-index.html#E0284): type annotations needed: cannot satisfy `<T as Get>::T<'b> == T`
  --> src/lib.rs:13:5
   |
13 |     <T as Get>::get::<'b>(other)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot satisfy `<T as Get>::T<'b> == T`

rust-lang / rust

Impls for GAT-parameterized objects with bounds on specific instantation of GAT type result in incorrect mismatched type errors #106832

Meta