The compiler fails to infer the type, although it is either known or explicitly specified

[zarev]

I have the following function:

pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut widths = vec![(0usize, heights.len()); heights.len()];
    let mut stack = vec![];

    for (idx, &x) in heights.iter().enumerate() {
        while let Some(&pos) = stack.last() {
            if x >= heights[pos] {
                break;
            }

            widths[pos].1 = idx;
            stack.pop();
        }

        stack.push(idx);
    }

    todo!()
}

Which fails to compile:

error[E0282]: type annotations needed
  --> src/lib.rs:11:13
   |
11 |             widths[pos].1 = idx;
   |             ^^^^^^^^^^^ cannot infer type
   |
   = note: type must be known at this point

But if I change widths[pos].1 = idx to widths[pos] = (0, idx) the code compiles fine:

pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut widths = vec![(0usize, heights.len()); heights.len()];
    let mut stack = vec![];

    for (idx, &x) in heights.iter().enumerate() {
        while let Some(&pos) = stack.last() {
            if x >= heights[pos] {
                break;
            }

            widths[pos] = (0, idx); // now it compiles fine
            stack.pop();
        }

        stack.push(idx);
    }
  
    todo!()
}

It also compiles fine if I add type annotations for the stack variable, which should be Vec<usize> as its content is coming from .enumerate():

pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut widths = vec![(0usize, heights.len()); heights.len()];
    let mut stack: Vec<usize> = vec![];

    for (idx, &x) in heights.iter().enumerate() {
        while let Some(&pos) = stack.last() {
            if x >= heights[pos] {
                break;
            }

            widths[pos].1 = idx; // now it compiles fine
            stack.pop();
        }

        stack.push(idx);
    }
  
    todo!()
}

It also compiles fine if I add type annotations for widths like that, but fails with the same error without that type annotation.

pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut widths = vec![(0usize, heights.len()); heights.len()];
    let mut stack = vec![];

    for (idx, &x) in heights.iter().enumerate() {
        while let Some(&pos) = stack.last() {
            if x >= heights[pos] {
                break;
            }

            let at_pos: &mut (usize, usize) = &mut widths[pos]; // type annotations added here, although the vec is explicitly initialized with `(usize, usize)`
            at_pos.1 = idx;
            stack.pop(); 
         }

        stack.push(idx);
    }
  
    todo!()
}

So at the end I'm not sure If it fails to infer the type of pos or the type of widths

A user at StackOverflow managed to create the following smaller reproducible example:

fn some_fn() {
    let mut widths = vec![(0usize, 0usize); 100];
    let mut stack = vec![]; 
    //let mut stack:Vec<usize> = vec![]; //why explicit type definition is needed

    let a = stack.pop().unwrap();
    let idx = 0usize;
    widths[a].1 = idx;

    stack.push(idx);
}

Here is the SO question for reference: rust - "Cannot infer type - type annotations needed", but the type is already known - Stack Overflow

Do you have any idea what the issue might be ? Is this a known limitation or a bug in the compiler (I've also opened Problem with type inference · Issue #90252 · rust-lang/rust · GitHub)?

[alice]

It can't figure out if the vector has item type usize or something else e.g. a range of indexes. There are, after all, quite a few types that can be used to index a vector.

[zarev]

Yea, it fails when I do widths[pos].1 = idx, but succeeds when widths[pos] = (0, idx); without any other changes. So I cannot explain why.

In the other example it fails to recognize the type of the vector which is (usize, usize) because that's how it is declared. So I cannot understand why it fails in that case, because the type is know and it does not need to be inferred.

[kornel]

It seems that it's not about the type of widths, but about the type of stack. Adding this type hint solves it:

let mut stack: Vec<usize> = vec![];

but it could just be a quirk/bug of type inference that depends on the order in which it evaluates things. To index widths it needs to see stack.push(idx) to know it's a vec of usize from idx's type.

[zarev]

@kornel Try the other example:

pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut widths = vec![(0usize, heights.len()); heights.len()];
    let mut stack = vec![];

    for (idx, &x) in heights.iter().enumerate() {
        while let Some(&pos) = stack.last() {
            if x >= heights[pos] {
                break;
            }

            let at_pos: &mut (usize, usize) = &mut widths[pos]; // type annotations added here, although the vec is explicitly initialized with `(usize, usize)`
            at_pos.1 = idx;
            stack.pop(); 
         }

        stack.push(idx);
    }
  
    todo!()
}

Now remove the type hint:

   Compiling playground v0.0.1 (/playground)
error[E0282]: type annotations needed for `&mut _`
  --> src/lib.rs:12:13
   |
11 |             let at_pos = &mut  widths[pos];
   |                 ------ consider giving `at_pos` the explicit type `&mut _`, with the type parameters specified
12 |             at_pos.1 = idx;
   |             ^^^^^^^^ cannot infer type
   |
   = note: type must be known at this point

error[E0609]: no field `1` on type `&mut _`
  --> src/lib.rs:12:20
   |
12 |             at_pos.1 = idx;
   |                    ^

So yes - adding explicit Vec<usize> solves the issue, just as adding an explicit &mut (usize, usize) or just by doing widths[pos] = (0, idx)

Why ?

To index widths it needs to see stack.push(idx) to know it's a vec of usize from idx 's type.

That's exactly what's happening at the last line of the loop

[alice]

Basically, the reason widths[pos] = (0, idx) works is that tells the compiler that the Index::Output type is (usize, usize). Using this, it can tell that the only possible choice for Index is usize. However, when you instead write widths[pos].1 = idx, you are not telling it what the Index::Output type is — all you're saying is that it has a field called 1, and it isn't clever enough to deduce what the actual type is from that information.

As for adding a type annotation for stack, well obviously that tells it the item type of stack, so that also works.

Then there's the let at_pos: &mut (usize, usize) = &mut widths[pos] option. This also works because it's just another way to tell it what the type of Index::Output is.

As for the stack.push(idx) call, well, the compiler will prefer to infer based on the first use of stack.