Why type annotations needed?

[filtsin]

I have this code

enum Foo<T> {
    V1(T),
    V2(Bar<T>),
}

impl<T> From<T> for Foo<T> {
    fn from(v: T) -> Self {
        Self::V1(v)
    }
}

struct Bar<T> {
    marker: std::marker::PhantomData<T>,
}

impl<T> From<Bar<T>> for Foo<T> {
    fn from(v: Bar<T>) -> Self {
        Self::V2(v)
    }
}

fn create_bar<T>(_: T) -> Bar<T> {
    Bar { marker: std::marker::PhantomData }
}

fn accept_foo<T, U>(foo: T)
where
    T: Into<Foo<U>>,
    U: AsRef<str> + 'static {}
    
fn main() {
    accept_foo("2"); // compiles: T = &str, U = &str
    let bar: Bar<String> = create_bar("Hello".to_owned());
    accept_foo(bar); // not compiles, but T = Bar<String>, U = String, why?
}

Why rust can not infer U type on last line in main function.

[H2CO3]

There may be several different U s for which T: Into<Foo<U>>. There's nothing in the signature that would imply that U must be String above.

[filtsin]

Why? I can not understand it. Compiler knows that Bar<String> has Into<Foo<String>>, why he can not infer that U = String. If I remove From<T> for Foo<T> in the code above, the last line is compiling.

[Cerber-Ursi]

@filtsin

Compiler knows that Bar<String> has Into<Foo<String>>

But it doesn't know that there's no other U such that Bar<String>: Into<Foo<U>>.

[ekuber]

And if it did, then adding an impl would break existing working code.

[ExpHP]

@Cerber-Ursi

But it doesn't know that there's no other U such that Bar<String>: Into<Foo<U>> .

@ekuber

And if it did , then adding an impl would break existing working code.

These are not the issue. The compiler does use uniqueness of type arguments in type inference (as exploited by type-level programming libraries like frunk), and yes, rust today does have the issue that adding an impl can break existing working code for this reason.

The true crux of the problem here is that Bar<String> already has two impls of Into<Foo<_>>:

1. Into<Foo<Bar<String>>>, from the impl<T> From<T> for Foo<T>
2. Into<Foo<String>>, from the impl<T> From<Bar<T>> for Foo<T>

If you delete the impl<T> From<T> for Foo<T>, then the line of code compiles.

[Cerber-Ursi]

@ExpHP

The true crux of the problem here is that Bar<String> already has two impls of Into<Foo<_>>

...and that it can't know whether the second bound will be satisfied, i.e. whether Bar<String> will be AsRef<str>, if I understand correctly?

[ExpHP]

Ah, yes, I should mention the second where bound.

Perhaps counter-intuitively, the U: AsRef<str> bound here plays no role in the type inference here, even though the other bound does. The general intuition to have here is that type inference via trait impls does not work by filtering possible types, it only works by solving for them.^[1] i.e. the set of trait impls that exist needs to provide it with some equation like Foo<U> = Foo<String> which can be solved for U.

In my modified form of the example, the following happens:

• We have String: Into<Foo<U>>, which matches a single impl, impl Into<T: From<U>> for U, and gives us a new trait bound, Foo<U>: From<String>.
• That matches a single impl, impl<T> From<Bar<T>> for Foo<T>, which gives us U = String.
• The type String is now specific enough for the compiler to find a unique impl for String: AsRef<str>.

---

From a more practical viewpoint, I'd like to say: The rules of type inference via trait solving are not well-documented and are difficult to internalize, and they're mostly something that a rust coder gains intuition for after a lot of programming in rust. The perhaps-disappointing tl;dr though is: in rust it is difficult to achieve a generic function which can have one behavior for a certain type, and a different behavior for "all other types". This is something people often try to do, perhaps based on past experience with e.g. template specialization in C++, but it's not so simple in rust where type inference relies significantly on parametricity.

The easiest way to solve this in most cases is to introduce a wrapper type for the broad case; so, for instance, instead of impl<T> From<T> for Foo<T>, you instead have impl<T> From<Wrapper<T>> for Foo<T>, and the caller calls the method with Wrapper("Hello".to_owned()). Or, you have two separate methods.

---

1. On the rustc dev guide, you'll see a mention of a "winnowing pass" where where bounds are sometimes used to cull candidates. However, this isn't used to cut candidates from the list of types, rather it cuts candidates from the list of impls of a trait! (basically, when looking for a unique impl of a trait, the compiler can ignore impls that contain a where bound that is unsatisfiable). ↩︎