Making type inference work both ways


#1

Here is a Thing.

struct IndexVec<I, T>(PhantomData<fn(I)>, Vec<T>);

struct Thing<I = usize>(IndexVec<I, i32>);

I want to construct many Things. But Thing did not always have this newfangled index type parameter; it used to hold a Vec, and exposed methods that returned slices and etc. I want to gradually introduce support for indices into my codebase, so I’ve chosen to give Thing an interface that works with both Vec and IndexVec seemlessly. For most methods, I’ve managed to find a signature that works nicely… except when it comes to the constructor.

You see, new used to actually take a Vec<i32>. Which is useful because it is frequently constructed from iterators, and so collect() just works. Here’s a way you can write new which allows that to work:

// A trait whose sole purpose here is to NOT be implemented by usize
trait IsNewtypeIndex { }

trait IndexFamily<I, T> {
    type Owned;

    fn index_vec_from_owned(vec: Self::Owned) -> IndexVec<I, T>;
}

impl<T> IndexFamily<usize, T> for () {
    type Owned = Vec<T>;
    
    fn index_vec_from_owned(vec: Vec<T>) -> IndexVec<usize, T> { ... }
}

impl<I: IsNewtypeIndex, T> IndexFamily<I, T> for () {
    type Owned = IndexVec<I, T>;
    
    fn index_vec_from_owned(vec: IndexVec<I, T>) -> IndexVec<I, T> { vec }
}

impl<I> Thing<I> {
    fn new_one(vec: <() as IndexFamily<I, i32>>::Owned) -> Self
    where (): IndexFamily<I, i32>,
    { Thing(<()>::index_vec_from_owned(vec)) }
}

Written like this, new_one can infer the input type from how the output is used. However, not everything is wonderful: you must use the Thing in a way that constrains I, or no dice, since the compiler chooses not to deduce I from knowledge of <() as Trait<I>>::Assoc. (understandably, for coherence reasons)

println!("{:?}", Thing::new_one(vec![2])); // error: type annotations needed

This can be fixed by trying another signature:

trait IntoIndexVec {
    type Index;
    type Elem;

    fn into_index_vec(self) -> IndexVec<Self::Index, Self::Elem>;
}

impl<T> IntoIndexVec for Vec<T> {
    type Index = usize;
    type Elem = T;
    
    fn into_index_vec(self) -> IndexVec<usize, T> { ... }
}

impl<I, T> IntoIndexVec for IndexVec<I, T> {
    type Index = I;
    type Elem = T;
    
    fn into_index_vec(self) -> IndexVec<I, T> { self }
}

impl<I> Thing<I> {
    fn new_two(vec: impl IntoIndexVec<Index=I, Elem=i32>) -> Self
    { Thing(vec.into_index_vec()) }
}

Now the first example can infer that I=usize. However, collect()-ing into an argument no longer works without type annotations:

Thing::new_two((0..3).collect()) // error: type annotations needed

…because the compiler no longer has any concrete information about the type of the argument beyond a set of bounds it must simultaneously satisfy (impl (FromIterator<i32> + IntoIndexVec<Index=I, Elem=i32>)), and it chooses (very understandibly) not to deduce Vec<i32> from that.


So between these two signatures, I am forced to choose between allowing the input to sometimes determine the output, or allowing the output to sometimes determine the input.

Can I have my cake and eat it too?

playground


#2

Maybe add FromIterator for Thing. Even then no guarantee collect won’t need turbofish.


#3

In my actual code, Thing cannot implement FromIterator because it has another field which must because given to new which is not sequence-like. Also, I’d like for ::new(collect()) to work as well for Thing<Foo> where Foo is a specific, known type that implements IsNewtypeIndex. (and this does work for new_one, as rust will infer the collected value to be an IndexVec).

Edit: I posted too hastily. Obviously the second requirement would be met by impl<I> FromIterator<i32> for Thing<I>, and technically speaking I could do something similar to this to slip in that other argument… but AFAICT, I’d lose type safety in the case where the input has the wrong index type (I wouldn’t be able to make it not compile).