How does this impl have stricter requirements than the trait?

help
1

(This is a part of a bigger problem I have, but I made a reproduction of the error)

use core::ops::Index;

struct Wrapper<Ix>(Ix);
struct Container<Ix> {
    _ghost: core::marker::PhantomData<Ix>,
}
impl<Ix> Index<Wrapper<Ix>> for Container<Ix> {
    type Output = ();
    fn index(&self, _: Wrapper<Ix>) -> &() { unimplemented!() }
}
trait Trait {
    type Assoc;
    fn foo()
    where
        Container<Self::Assoc>: Index<Self>,
        <Container<Self::Assoc> as Index<Self>>::Output: Sized;
}
impl<T> Trait for Wrapper<T> {
    type Assoc = T;
    fn foo()
    where
        Container<T>: Index<Self>,
        <Container<T> as Index<Self>>::Output: Sized {}
}

Playground

But this code fails to compile (try clicking “Build” on the playground)

error[E0276]: impl has stricter requirements than trait
  --> src/lib.rs:29:48
   |
17 | /     fn foo()
18 | |     where
19 | |         Container<Self::Assoc>: Index<Self>,
20 | |         <Container<Self::Assoc> as Index<Self>>::Output: Sized;
   | |_______________________________________________________________- definition of `foo` from trait
...
29 |           <Container<T> as Index<Self>>::Output: Sized,
   |                                                  ^^^^^ impl has extra requirement `<Container<T> as Index<Wrapper<T>>>::Output: Sized`

rustc says that the impl has the stricter requirement <Container<T> as Index<Wrapper<T>>>::Output: Sized, even though the trait has that exact bound (changing the T to Self::Assoc makes no difference).
Is this error intentional, and if so, what is it keeping me from doing? Either way, how can I go about fixing it and getting my code to work?

2

It does make a difference I see: there's an additional error.

error[E0277]: the size for values of type `<Container<T> as Index<Wrapper<T>>>::Output` cannot be known at compilation time
  --> src/lib.rs:29:58
   |
29 |         <Container<Self::Assoc> as Index<Self>>::Output: Sized,
   |                                                          ^^^^^ doesn't have a size known at compile-time
   |
   = help: the trait `Sized` is not implemented for `<Container<T> as Index<Wrapper<T>>>::Output`

This suggests to me that the compiler is having some kind of trait-solving problem. I don’t know what the problem is or what further implications it might have, but I can get the code to compile by removing the bound:

impl<T> Trait for Wrapper<T> {
    type Assoc = T;
    fn foo() {}
}

Now the compiler is satisfied merely by proving that the concrete requirement (): Sized holds when you try to call Wrapper::<T>::foo(). We’ve gotten rid of your “stricter requirement” problem with a “weaker requirement” solution.

3

A more remarkable example of such weakening:

trait Foo {}
trait Bar {
    fn bar<T>() where T: Foo;
}

impl Foo for () {}

struct Xyz;
impl Bar for Xyz {
    fn bar<T>() {}
}

fn main() {
    Xyz::bar::<()>();
}

As written, Xyz::bar() is more flexible than declared in the trait — it accepts Ts which don't implement Foo. You cannot actually call Xyz::bar::<DoesNotImplementFoo>() currently, but if and when RFC 3245 “refined trait implementations” are implemented, that will be possible (if Xyz::bar() is marked as refined). Today, it’s merely the case that this code compiles without complaint.

4

Thank you for explaining how you can remove the bounds in the example (this is really interesting), but my code is more complicated. Container<Ix> is actually petgraph::Graph<N, E, Ty, Ix>, and Wrapper<Ix> is NodeIndex<Ix>. Trait is petgraph::GraphIndex, and foo must return &mut <Graph as Index<NodeIndex>>.
More details: I’m trying to solve the issue I created, petgraph#669, but it’s actually a duplicate of the older #582. To do this, I must return a &mut <Graph<N,E,Ty,Ix> as Index<T>>, where T is either NodeIndex<Ix> or EdgeIndex<Ix>. (without creating a &mut Graph, which would reassert total unique access) The hard part comes from getting the compiler to recognize that either/or type information in a useful manner.
I flipped it “inside out” and got the implementation of GraphIndex to return an unsafely created reference, and that’s what I’m trying to express the signature for. The code in the OP is analogous to my attempt

unsafe trait GraphIndex {
    // `impl<Ix> GraphIndex for NodeIndex<Ix> { type IndexType = Ix; ... }`
    type IndexType;
    unsafe fn index_into_mut<'a, N, E, Ty: EdgeType>(
        &self,
        graph: *mut Graph<N, E, Ty, Self::IndexType>,
    ) -> &'a mut <Graph<N, E, Ty, Self::IndexType> as Index<Self>>::Output
    where
        Graph<N, E, Ty, Self::IndexType>: Index<Self>,
        <Graph<N, E, Ty, Self::IndexType> as Index<Self>>::Output: Sized;
}

(other GraphIndex functions removed for clarity)
The Sized bound is needed because the implementation has to create a &mut <Graph as Index<NodeIndex>>::Output from a &mut N. N and Graph::Output are the same type, but the compiler won’t acknowledge that. I tried brute-forcing it by casting the pointer from N to Graph::Output, but that needs Graph::Output: Sized, hence the Sized bound.