'Incomplete' generic type

Suppose we have the following implementation:

trait S<T> {
    type Item;
}

impl<T> S<T> for Mutex<T> {
    type Item = T;
}

struct MyStruct<T1: S<u8>, T2: S<i32>, T3: S<f64>> {
    feild1: T1,
    feild2: T2,
    feild3: T3,
}

let a: MyStruct<Mutex<u8>, Mutex<i32>, Mutex<f64>> = MyStruct {
    feild1: Mutex::new(1),
    feild2: Mutex::new(5),
    feild3: Mutex::new(9.),
};

Each field in MyStruct implements S, but we need to use a separate generic parameter for each of them. This can lead to an explosion of generic parameters in your project. If we can simplify this writing to the following:

struct MyStruct<T: S<_>> {
    feild1: T<u8>,
    feild2: T<i32>,
    feild3: T<f64>,
}

We can just use S<_> in the generic declaration, and let the struct itself decide which generic type to use inside S.

I'm not sure if this language feature has anything to do with GAT or HKT (higner-kinded type), but since it has alternative implementations (i.e. the generic explosion case above), I think it can be implemented.

The motivation of this is parallel rustc. I've done quite a bit of work and research on parallel rustc. Yesterday I tried refactoring the Lock data structure to try to make the nightly compiler parallelize (PR here), but the performance hit is still huge.

If we had the language features mentioned above, we could do this by implementing the S trait for both RefCell and Mutex, and then specifying whether T was a RefCell or Mutex in the struct declaration, so that It is possible to have both shared and non-shared instances of MyStruct. Based on this we can ship parallel compilation without degrading performance.

This seems to me just a weirder implementation of HKT. You're pretty much asking for a family of types (for example the family of all Mutex<T> types), and then you want to instantiate it with a concrete generic type. With GATs with would be something like:

trait S {
    type Item<T>;
}

struct MyStruct<T: S> {
    feild1: T::Item<u8>,
    feild2: T::Item<i32>,
    feild3: T::Item<f64>,
}

enum MutexFamily {}
impl S for MutexFamily {
    type Item<T> = Mutex<T>;
}

let a: MyStruct<MutexFamily> = MyStruct {
    feild1: Mutex::new(1),
    feild2: Mutex::new(5),
    feild3: Mutex::new(9.),
};

I say weird because if I see struct MyStruct<T: /* ... */> I would expect T to be a type, not a HKT like in your example. That is, I would expect to see the <_> part on the type, not the trait bound.

Moreover the two snippets aren't exactly equivalent, are they? The first example with T1, T2 and T3 allows to mix different types together, for example MyStruct<RefCell<u8>, Mutex<i32>, Mutex<f64>>.

1 Like

Yes, what I'm trying to express here is that feild1, feild2 and feild3 are either all Mutex or all RefCell, which is exactly what the parallel rustc needs.

Of course It would be great if GAT could solve this problem.

See this blog post and perhaps the rest in the series.