Misleading type mismatch error on failed type inference

Hi,

I have come across something very confusing. Essentially, the following compiles:


pub type Solver<G, const N: usize> = fn(&G, Option<IOMode>) -> Record<N>;

impl Solvable<2> for Session
{
    ...

    fn solvers(&self) -> HashMap<String, Solver<Self, 2>>
    {
        let acyclic: Solver<Self, 2> = <Self as AcyclicSolver<2>>::solve;
        HashMap::from([
            (<Self as AcyclicSolver<2>>::name(), acyclic)
        ])
    }
}

But the following does not:

impl Solvable<2> for Session
{
    ...

    fn solvers(&self) -> HashMap<String, Solver<Self, 2>>
    {
        HashMap::from([
            (<Self as AcyclicSolver<2>>::name(), 
             <Self as AcyclicSolver<2>>::solve)
        ])
    }
}

With the confusing type mismatch error:

error[E0308]: mismatched types
   --> nova/src/games/zero_by/mod.rs:147:9
    |
145 |       fn solvers(&self) -> HashMap<String, Solver<Self, 2>>
    |                            -------------------------------- expected `HashMap<std::string::String, for<'a> fn(&'a Session, Option<IOMode>) -> Record<2>>` because of return type
146 |       {
147 | /         HashMap::from([
148 | |             (Self::name(), <Self as AcyclicSolver<2>>::solve)
149 | |         ])
    | |__________^ expected fn pointer, found fn item
    |
    = note: expected struct `HashMap<_, for<'a> fn(&'a Session, Option<_>) -> Record<_>>`
               found struct `HashMap<_, for<'a> fn(&'a Session, Option<_>) -> Record<_> {<Session as AcyclicSolver<2>>::solve}>`

As you can see in the following snippet,

 expected struct `HashMap<_, for<'a> fn(&'a Session, Option<_>) -> Record<_>>`
    found struct `HashMap<_, for<'a> fn(&'a Session, Option<_>) -> Record<_> {<Session as AcyclicSolver<2>>::solve}>`

The type matches perfectly, with the exception of the appended fully qualified disambiguation {<Session as AcyclicSolver<2>>::solve} to the function type. Does anyone know if this has any meaning, and why the compiler is not able to perform type inference in this particular case?

If anything, to me it looks like this should be a "cannot infer type" kind of error, not a type mismatch (it had me pulling my hair for a good minute). Let me know if I should provide the trait declarations as further context.

Each function item has it's own type in Rust which is not the same as the type of the function pointer which has the advantage that a function item is zero sized.

You can read more about it here: Function item types - The Rust Reference

1 Like

Better than that, the function being called is statically known, so the optimizer can easily inline it if needed and thus better optimize it. Function pointers on the other hand require a devirtualization pass in order to do this.

2 Likes

This is exactly what I was looking for, thank you!

With devirtualization pass, do you mean the cost of following the function pointer to the segment where its instructions are?

At least from my understanding, having a function pointer isn't that bad since the associated cost of it would only be a few instruction cache misses due to not necessarily being able to inline it. Sorry for the extra questions, I was only able to find C++ articles on it and I have never typed a character of C++.

It means that sometimes optimizer can see what is the exact value of the function pointer in this place and, essentially, "const-propagate" it into the call instruction, instead of looking the value at runtime.

When the function is impossible to inline, it's also impossible to optimize it further with the knowledge of surrounding code. A slightly contrived example:

fn outer(arr: [u8; 2]) -> u8 {
    inner(&arr)
}
fn inner(arr: &[u8]) -> u8 {
    arr[0]
}

When compiled in isolation, inner must include the bound check to ensure that arr is not empty (and so that indexing it with 0 is valid). When inlined to outer though, compiler can see the arr is definitely not empty (because of the type), and bound check becomes unnecessary. And you can see this in action (use "Show assembly" in the linked playground) - outer is just a mov, and inner can panic.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.