Problem with type inference

[SvetlinZarev]

I tried this code:

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!()
}

I expected to see this happen:
The code should have compiled without errors

Instead, this happened:

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

Meta

I've checked with 1.45 stable, 1.56 stable, 1.57 beta , 1.58 nightly

rustc --version --verbose:

`--> rustc --version --verbose
rustc 1.56.0 (09c42c458 2021-10-18)
binary: rustc
commit-hash: 09c42c45858d5f3aedfa670698275303a3d19afa
commit-date: 2021-10-18
host: x86_64-apple-darwin
release: 1.56.0
LLVM version: 13.0.0

Additional information

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![(0, 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 comming from .enumerate():

pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut widths = vec![(0, 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![(0, 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
            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: https://stackoverflow.com/questions/69696784/cannot-infer-type-type-annotations-needed-but-the-type-is-already-known

[TieWay59]

I got another discovery : if you initialize the stack with items, this code won't fail to infer types.

fn some_fn() {
    let mut widths = vec![(0usize, 0usize); 100];
    let mut stack = vec![0usize];  // <---- 

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

    stack.push(idx);
}

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

    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!()
}

I guess this is because type infer is somewhat order based. If you reorder while let Some(&pos) = stack.last() and stack.push(idx); in your origin code, it will also compile 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() {
        stack.push(idx); // <---- 
        while let Some(&pos) = stack.last() {
            if x >= heights[pos] {
                break;
            }

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

    todo!()
}

The logic behind it is: you need stack to infer your pos type, and the type must be known in the line you invoke while let Some(&pos) = stack.last(), it can't be inferred from the lines behind.

I can't tell whether this is a bug, but hoping my discovery helps.

[SvetlinZarev]

@TieWay59 Yes, explicitly specifying the type for stack works, as shown in my third code snippet.

The question is why it fails to infer the type for widths[pos].1 = idx but succeeds for widths[pos] = (0, idx) and let at_pos: &mut (usize, usize) = &mut widths[pos]; ?

If I elide the type annotation for let at_pos: &mut (usize, usize) = &mut widths[pos]; it still fails. So why is this type annotation needed, when the vector is explicitly initialized as vec![(some_usize; some_usize); len] ?

[TieWay59]

@SvetlinZarev I got your point now. It might be related to tuple indexing. But I don't know any further about it, try post your issue link in other im platform for more attention.

[TieWay59]

[dingxiangfei2009]

I am going to make my best effort to explain why type inference does not work for this case. I am still fresh to rustc internals, so correct me if I am wrong. 😄

I am working with the commit 47aeac648ed56095688c1c20972c9b72bd0da7ce so it should be fairly recent at the time of this writing.

I am also working with an adapted MCVE.

struct A {
    a: u8,
}

fn some_fn() {
    let mut widths = vec![A {a: 0}];
    let mut stack = vec![];

    let a = stack.pop().unwrap();
    let idx = 0usize;
    let b = &widths[a].a; // <-- (1)

    stack.push(idx); 
}

Type checking arrives at (1). We need to assign a type to b.
Below two layers of check_expr_with_expectation calls, check_field is called to determine the type of widths[a].a.
Since the variable a is still assigned to a type placeholder _, the type of the value widths[a] resulting from indexing operation on the slice widths[..] is also assigned to a type placeholder _.
After this, we see trouble.
We may theoretically assign a type placeholder to the type of the sub-expression widths[a].a, on the condition that we should record an "obligation" that it is possible to access a field a from widths[a]. This condition must be checked against later type assignments. Unfortunately, such condition is not yet expressible. This fact can be confirmed by examining the PredicateKind.

Otherwise, if the type of the variable a is known to be usize at (1), the type of widths[a] is known by evaluating the associate type <std::vec::Vec<A> as std::ops::Index<usize>>::Output.

To make that condition expressible, we may need to see how hard it is to get row polymorphism in Rust. 🤔

[oerdn]

Otherwise, if the type of the variable a is known to be usize at (1), the type of widths[a] is known by evaluating the associate type <[A] as std::ops::Index<usize>>::Output.

let b:String = widths[a]; // <-- (1)

If you define b like this, it throws:

   |
12 |     let b:String = widths[a]; // <-- (1)
   |                    ^^^^^^^^^ expected struct `A`, found struct `String`

It is a bit unusual to me, compiler knows the a's type during error reporting but not while inferring?

Also another example which might prove that the compiler knows the type of a on step (1)
Try adding &'static str to the stack :

//...
let b = widths[a]; // <-- (1)
b.a;
stack.push("idx"); 
//...

(Playground)

It will throw one more error with the "type annotations needed" error, to me it should throw a single error like below :

error[E0277]: the type `[A]` cannot be indexed by `&str`
  --> src/lib.rs:12:13
   |
12 |     let b = widths[a]; // <-- (1)
   |             ^^^^^^^^^ slice indices are of type `usize` or ranges of `usize`
   |
   = help: the trait `SliceIndex<[A]>` is not implemented for `&str`
   = note: required because of the requirements on the impl of `Index<&str>` for `Vec<A>`

It looks like it knows the type of index on step (1), because index access has evaluated before field access.

[dingxiangfei2009]

It is a bit unusual to me, compiler knows the a's type during error reporting but not while inferring?

TL;DR: Yes. That error reporting happens not at (1) but at a later point.

I have tried the new code. For completeness, I am posting what I used for debugging.

What I am using for debugging

struct A {
    a: u8,
}

fn some_fn() {
    let mut widths = vec![A {a: 0}];
    let mut stack = vec![];

    let a = stack.pop().unwrap();
    let idx = 0usize;
    let b: String = widths[a]; // <-- (1)

    stack.push(idx); // <-- (2)
}

fn main() {}

rustc gives this.

error[E0271]: type mismatch resolving `<usize as SliceIndex<[A]>>::Output == String`
  --> test2.rs:11:21
   |
11 |     let b: String = widths[a];
   |                     ^^^^^^^^^ expected struct `A`, found struct `String`

I observe that the type checking actually passes at (1) initially, though. The error that you see above this line is in fact emitted at (2).

What happens is, at (1), the type checking passes except with some conditions attached. If we enable logging in the rustc_trait_selection, we can see that the following conditions are recorded because <Vec<A> as std::ops::Index<_>> is selected to type-check (1). This list is not ordered.

• <_ as std::slice::SliceIndex<[A]>> because of the where clause here.
• WellFormed(fn(&std::vec::Vec<A>, _) -> &_) implied by the indexing operation so that we can actually index on Vec<A>.
• OutlivesPredicate(std::vec::Vec<A>, '_#2r) implied by the above obligation, I think.
• A bunch of WellFormed(_) but I am honestly losing track of which values those placeholders correspond to. 😢
• Most important of all, <_ as SliceIndex<[A]>>::Output == String, because by stating let b: String = <..> we are expecting the indexing operation to return with a String.

At this point, rustc needs more information to check this list of conditions. Therefore, it proceeds to the rest of the function body for hints on those type placeholders.

Now, it appears that rustc knows the type of widths[a] and points its finger at (1), but it is only able to when it is checking the types at (2) by assigning the placeholder in <_ as SliceIndex<[A]>>::Output == String to usize and realizing that the predicate is unsatisfiable.