Why is the type not inferred?

I have the following code snippet:

fn A(a: &str) -> Vec<Card> {
    let mut v = "abc".chars().map(|x| x.into()).collect();
    v.sort_unstable();
    v
}

Based on return type, I expected the compiler to figure out v's type to be Vec<Card>. Instead, I get the error:

error[E0282]: type annotations needed
 --> infer.rs:3:5
  |
2 |     let mut v = "abc".chars().map(|x| x.into()).collect();
  |         ----- consider giving `v` a type
3 |     v.sort_unstable();
  |     ^ cannot infer type
  |
  = note: type must be known at this point

Is there any way v could have a type other than Vec<Card> at line 3?

yes v has to be a &mut [Card] or something what implements DerefMut<Target = [Card]> since sort_ubstable is only implemented for slices not for Vec

Not formally derived from the inference algorithm, but:

I've found that informally, calling a method on a binding basically requires all information required by that method to be specified at that point.

Type information does flow reverse, but in a limited fashion.

I think of it as each line assigning constraints onto the type. If the new constraint can't be unified with the old one into one single coherent type constraint, then you get a "must be specified" error.

You'll see this mostly around generic return types such as .into() and .collect(), as the compiler is working from almost nothing, do if you do basically anything but put it into a typed place, you'll run into issues.

1 Like

To expand briefly on what @CAD97 said, my understanding is that type checking is always done "in order," leading to errors like this.

During type checking, type inference is performed, which carries information backwards (allowing the type checker to know what the most general possible type of a variable is given how far it has gone through the function body). This often gives the illusion that the compiler can work backwards from the return type, and it works fine for things like trait bounds; but the illusion easily breaks in the face of features like type-directed method resolution.

.collect::<Vec<_>>() should be enough to make the snippet compile. You only need to specify the type far enough for the method to be found, and can leave placeholders for the rest.

1 Like

Yes, if literally any other type in the universe had defined that method and FromIterator.

Looking at methods on everything ever is a recipe for bad perf and surprising results, so Rust doesn't do that.

Well... it's not like a statement of the form

value.method();

can change the type of anything. It can only make the type of value more specific through unification. This particular example, when judged in a vacuum, can be solved by making this statement introduce a lazily-verified requirement:

  • after the assignment, v has type ?T0 where ?T0: FromIterator<Card>.
  • no methods can be found on v, so checking the method call is deferred.
  • unifying the output type reveals that ?T0 = Vec<Card>
  • now that the end of the function body has been reached, we return to deferred jobs
  • v.sort_unstable() is successfully resolved

The key to why such an algorithm cannot be used must lie in other, more complicated examples.


Addendum: Perhaps the key lies in coercions. Strictly speaking, the only thing that can be told from the output expression is that ?T0 is a type that can be coerced into Vec<char>. It just so happens that the only type that can be coerced into Vec<char> is, in fact, Vec<char>.

Or the OP could specify the type in line 2 like so let mut v: Vec<Card> = ...