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

[inanna-malick]

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

[compiler-errors]

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.

[compiler-errors]

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.

[inanna-malick]

@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

[QuineDot]

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`

[zakrad]

@rustbot claim