Curiously recurring generic trait pattern: overflow evaluating the requirement

Question

I am trying to implement a generic structure with a bunch of fields, where each of the field types should know about the exact type of the whole structure. It's a sort of strategy pattern.

pub struct Example<S: Strategy<Example<S, D>>, D> {
    pub s: S,
    pub a: S::Associated,
    pub data: D,
}
pub trait Strategy<T> {
    type Associated;
    fn run(&self, &T);
}
pub trait HasData {
    type Data;
    fn data(&self) -> &Self::Data;
}

impl<S: Strategy<Self>, D> Example<S, D> {
//               ^^^^
// the complex code in this impl is the actual meat of the library:
    pub fn do_it(&self) {
        self.s.run(self); // using the Strategy trait
    }
}
impl<S: Strategy<Self>, D> HasData for Example<S, D> {
    type Data = D;
    fn data(&self) -> &D {
        &self.data
    }
}

I was planning to then instantiate the generics from the above "library":

pub struct ExampleStrat;
pub struct ExampleData;

impl<E: HasData<Data = ExampleData>> Strategy<E> for ExampleStrat {
    type Associated = ();
    fn run(&self, e: &E) {
        let _ = e.data();
        // uses ExampleData here
    }
}
let example = Example {
    s: ExampleStrat,
    a: (),
    data: ExampleData,
};
example.do_it();

In my actual code I've got quite a few different "strategies" and also multiple data fields, so the Example type has an impressive list of generics, and I'm happy if the library user doesn't need to be explicit about them (or not often at least) and instead can just use the HasData trait (with its associated types, not generic type parameters).

If there was no type bound in struct Example<S, D>, this would actually work (surprisingly) fine, much better than I has initially expected (after fighting with Self in the struct bounds). However it is recommended to duplicate the impl trait bounds on the struct when the struct is only supposed to be used with the constrained types, and in my case I actually need them to be able to use the Associated type for the a field.

Now the compiler is complaining

error[E0275]: overflow evaluating the requirement `main::ExampleStrat: Strategy<Example<main::ExampleStrat, main::ExampleData>>`
  --> src/main.rs:42:9
   |
42 |         a: (),
   |         ^^^^^
   |
   = note: required because of the requirements on the impl of `HasData` for `Example<main::ExampleStrat, main::ExampleData>`
   = note: required because of the requirements on the impl of `Strategy<Example<main::ExampleStrat, main::ExampleData>>` for `main::ExampleStrat`

How can I solve this? Am I trying to do something that is not possible, am I doing it wrong, or is it supposed to be possible but I am falling prey to a compiler bug? Is my complete design flawed?

Answer 1

First of all, everything becomes a lot clearer if you avoid putting trait bounds on definitions of structs and traits. When things get complicated, the constraints are at least solved from the same direction.

pub struct Example<S, D, A> {
    pub s: S,
    pub a: A,
    pub data: D,
}

pub trait Strategy<T> {
    type Associated;
    fn run(&self, &T);
}

pub trait HasData {
    type Data;
    fn data(&self) -> &Self::Data;
}

impl<S, D, A> Example<S, D, A>
where
    S: Strategy<Self, Associated = A>,
{
    pub fn do_it(&self) {
        self.s.run(self);
    }
}

impl<S, D, A> HasData for Example<S, D, A>
where
    S: Strategy<Self, Associated = A>,
{
    type Data = D;
    fn data(&self) -> &D {
        &self.data
    }
}

Your implementation of Strategy for ExampleStrat looks like this:

impl<E: HasData<Data = ExampleData>> Strategy<E> for ExampleStrat {
    type Associated = ();
     // ...
}

What this means is that you are defining it for all possible qualifying types E. The type-checker can now only look at the trait bounds, which are again generic and only expressed in terms of other traits, which use each other as bounds, so the type-checker gets into a cycle. Put a block in the cycle by giving it a concrete type, which you know.

pub struct ExampleStrat;
pub struct ExampleData;

impl Strategy<Example<ExampleStrat, ExampleData, ()>> for ExampleStrat {
    type Associated = ();
    fn run(&self, e: &Example<ExampleStrat, ExampleData, ()>) {
        let _ = e.data();
        // uses ExampleData here
    }
}

fn main() {
    let example = Example {
        s: ExampleStrat,
        a: (),
        data: ExampleData,
    };
    example.do_it();
}

Answer 2

If the following impl is characteristic for Strategy, then it might be parameterized on the wrong thing. (I'm going to ignore the associated type for this answer, because the example doesn't use it.)

impl<E: HasData<Data = ExampleData>> Strategy<E> for ExampleStrat {
    fn run(&self, e: &E) {
        let _ = e.data();
        // uses ExampleData here
    }
}

You could instead parameterize Strategy over D -- breaking the impl dependency cycle -- and parameterize only the run method over E.

pub trait Strategy<D> {
    fn run(&self, &impl HasData<Data = D>);
}

impl Strategy<ExampleData> for ExampleStrat {
    fn run(&self, e: &impl HasData<Data = ExampleData>) {
        let _ = e.data();
        // uses ExampleData here
    }
}

fn run<E: HasData<Data = ExampleData>>(&self, e: &E) is another way to define run that is the same for this purpose. Here is a full example.

A potential drawback of this approach is that run can't be called through a Strategy trait object, because it has to be monomorphized for any type that implements HasData. But the HasData trait doesn't seem to do much in this impl: the only thing it can do is return an internal reference, and once you have it, there's no point in using it again. Maybe run could just take a &D reference?

pub trait Strategy<D> {
    fn run(&self, &D);
}

impl Strategy<ExampleData> for ExampleStrat {
    fn run(&self, _: &ExampleData) {
        // uses ExampleData here
    }
}

To be sure, now you have to call self.s.run(self.data()) in do_it, but this doesn't cost you in flexibility over the original version, in which, had it worked¹, you could only call Strategy<E>::run with an argument of type &E.

In fact, the whole HasData trait seems unnecessary to me: it's always implemented by the same type whose implementation calls it, so aside from the minor convenience of passing self instead of self.data, it doesn't elevate the level of abstraction inside the do_it method. So it seems to me effectively the same thing to delete HasData entirely and let Example know how to call Strategy::run with the right reference; it has to, anyway. (However, it's possible I merely lack imagination.)

Any of these solutions ought to handle adding an associated type to Strategy, but without knowing how it will be used, it's hard to say for sure.

¹It could be made to work in some future version of the compiler, with sufficiently smart type checking.