genericsrust

Blanket implement a trait over collections using the family trait pattern


Problem statement

I have a variety of generic "collection" types defined across my codebase consisting of many crates, each generated with the same declarative macro from a single crate e.g. collections. An example collection might be

struct BlahCollection<T> {
    a: T,
    b: T,
}

Separately, I then have a custom trait Distribute from a crate e.g. distribute that I would like to implement for every collection, so long as the type the collection contains (T above) also implements Distribute.

To do this, I could make collections depend on distribute, and then add an impl<T: Distribute> Distribute for $collection<T> block to the macro that generates each collection. However, I want to instead reverse the dependency, since the collections are used very broadly, but distribute is more niche and doesn't need to be depended on throughout the codebase. So basically I want distribute to depend on collections, and all the particular collections to depend only on collections. How can I accomplish this?

My attempt

My thinking was to provide some generic trait machinery for collections that distribute can tap into to blanket implement Distribute. I was looking at the "family traits" pattern. So I tried adding a Collection<T> trait and a CollectionFamily trait to collections, added the trait methods I needed to implement Distribute to Collection<T> (being able to map a collection from one underlying type to another) and implemented it automatically for every generated collection, something like:

// In `collections` crate:
pub trait Collection<T> {
    type Family: CollectionFamily;

    fn map<U>(self, f: impl FnMut(T) -> U) -> <Self::Family as CollectionFamily>::Collection<U>;
}
pub trait CollectionFamily {
    type Collection<T>: Collection<T, Family = Self>;
}

// In `distribute` crate, which depends on `collections`:
impl<T: Distribute, C: collections::Collection<T>> Distribute for C {
    ...
}

However, the last impl block produces the classic unconstrained type parameter error. I think the usual solution is to move a generic parameter into an associated type or similar, but I haven't been able to figure out how to do something similar here.

Playground link. See also this related question I asked awhile back -- the above is sort of the second iteration of the original problem I was having (which was solved).


Solution

  • This can't work because a type could implement Collection<T> and Collection<U>, and then the Distribute blanket implementation would be ambiguous in terms of which Collection implementation to use. This potential ambiguity is why the implementation is disallowed.

    A straightforward solution is to simply disallow multiple Collection implementations, which can be done by changing the generic type parameter T to an associated type:

    pub trait Collection {
        type Item;
        type Family: CollectionFamily;
    
        fn map<U>(
            self,
            f: impl FnMut(Self::Item) -> U,
        ) -> <Self::Family as CollectionFamily>::Collection<U>;
    }
    
    pub trait CollectionFamily {
        type Collection<T>: Collection<Item = T, Family = Self>;
    }
    
    pub trait Distribute {}
    
    impl<C> Distribute for C
    where
        C: Collection,
        C::Item: Distribute,
    {
    }