A Type Inference Failure Edge Case?

1

I know that Rust can't always infer type information, especially if there is not enough information to resolve generic types, which makes complete sense. However, I was working on a project, and I came across this scenario where Rust couldn't resolve the generic types of a HashMap. This seemed surprising, because there are multiple places where the compiler could infer it, but just wasn't strong enough.

Code example below:

use std::collections::HashMap;

fn main() {
    // Dummy code to compile
    handle_selection(vec![])
}

fn handle_selection(
    query: Vec<(u8, u8)>,
) {
    // HashMap<_, _>
    let mut board_map: HashMap<u8, Vec<u8>> = HashMap::new();
    
    for (selection_id, slot_id) in query.iter() {
        if let Some(selections) = board_map.get_mut(slot_id) {
            selections.push(*selection_id);
        } else {
            board_map.insert(*slot_id, vec![*selection_id]);
        }
    }

    eprintln!("{:?}", GameBoard::removals(board_map))
}

pub struct GameBoard;
impl GameBoard {
    pub fn removals(board: HashMap<u8, Vec<u8>>) -> Vec<(u8, u8)> {
        todo!("This is not relevant right now!")
    }
}

The error specifically is:

error[E0282]: type annotations needed for `HashMap<_, _>`
  --> src/main.rs:12:9
   |
12 |     let mut board_map = HashMap::new();
   |         ^^^^^^^^^^^^^
...
16 |             selections.push(*selection_id);
   |                        ---- type must be known at this point
   |
help: consider giving `board_map` an explicit type, where the type for type parameter `V` is specified
   |
12 |     let mut board_map: HashMap<K, V> = HashMap::new();
   |                      +++++++++++++++

I guess it makes sense how the type inference would struggle with this example. However, with a stronger type inference, after failing to resolve the type from line 16, couldn't Rust look at line 18 to figure out the type of selections through the .insert(...), or infer the HashMap's type on line 22 with the GameBoard::removals function call?

In other words, is this a case where the type inference isn't "strong enough", or is it just fundamentally wrong for the compiler to try to infer the type in this scenario.

Personally, my intuition leads me to believe it just isn't strong enough, but I could just be missing some underlying issues...

2

It is a limitation of the compiler. When performing a field access or method call, the type has to be known based on the (~current or) preceding code.

So this works with inferred HashMap generics:

        match board_map.get_mut(slot_id) {
            None => {
                board_map.insert(*slot_id, vec![*selection_id]);
            }
            Some(selections) => selections.push(*selection_id),
        }

But swapping the None and Some arm order does not.

Incidentally, you can avoid a double lookup using the entry API.

    let mut board_map = HashMap::<_, Vec<_>>::new();
    for (selection_id, slot_id) in query.iter() {
        board_map.entry(*slot_id).or_default().push(*selection_id);
    }

(But it also doesn't play nice with inference.[1])

  1. and in this case there's no longer something unambiguous later ↩︎

1 Like
3

How is the type inferred when get_mut is called? Seems like it is looking ahead.

Oh, I'm guessing it infers the HashMap key and value types separately, and only when they're used. Is that right?

4

Good point. I believe it's along the lines of, unresolved generic parameters are fine, but the top level type needs to be known. It knows board_map is a HashMap<_, _> before the match. Then after get_mut it knows it's a HashMap<u8, _>. But not until the insert does it know it's a HashMap<u8, Vec<u8>>.

Similarly, HashMap::<_, Vec<_>> is enough annotation to compile a call .len instead of .push in the OP, even though .len() doesn't resolve the generic of Vec<_> like push does.

...but as a disclaimer, my feedback is based on experience and not-very-technical comments,[1] not a knowledge of how the compiler is actually implemented. There are probably exceptions, like when a field is defined based on the associated type of a generic parameter.

  1. e.g. ↩︎

1 Like
5

Does it? get_mut is generic over the key type used for the lookup, so the real key might not be u8 but instead just any type implementing Borrow<u8>

6

Maybe it works because the only in-scope implementation of Borrow<u8> is for u8 (the blanket impl)?