Directly-invoked closure inference weirdness

Here's a function that seems like it should compile to me, but doesn't:

fn foo(s: i32) -> String {
    (|s| s.to_string())(s)
}
error[E0282]: type annotations needed
  --> src/lib.rs:10:7
   |
10 |     (|s| s.to_string())(s)
   |       ^  - type must be known at this point
   |
help: consider giving this closure parameter an explicit type
   |
10 |     (|s: /* Type */| s.to_string())(s)
   |        ++++++++++++

In addition to directly specifying the type, I can also fix the build by indirecting through a "call" function:

fn foo(s: i32) -> String {
    call(|s| s.to_string(), s)
}

fn call<T, R>(f: impl FnOnce(T) -> R, t: T) -> R {
    f(t)
}

Does anyone understand why the first snippet fails to compile, but the second one does? It seems like they should be equivalent (i.e. the compiler should be able to understand that the argument type of the close is the type of the value passed to its invocation).

EDIT:

This also works, which makes me think the issue is specific to the closure call sugar somehow?

#![feature(fn_traits)]

fn foo(s: i32) -> String {
    FnOnce::call_once(|s| s.to_string(), (s,))
}

I presume you meant (|s| s.to_string())(x)?

Oops, yeah fixed.

That doesn't surprise me all that much, because this also fails to compile:

let mut x = None;
if let Some(x) = x {
    x.to_string();
}
x = Some(4_i32);

for roughly the same reason: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=6f9460abd0c2a413a9ab18c1708898b4

error[E0282]: type annotations needed for `Option<T>`
 --> src/main.rs:2:9
  |
2 |     let mut x = None;
  |         ^^^^^
3 |     if let Some(x) = x {
4 |         x.to_string();
  |         - type must be known at this point

Basically, as soon as you hit a method call inference gives up.

And it's specifically about method calls too, since this works:

fn foo_ufcs(s: i32) -> String {
    (|s| ToString::to_string(&s))(s)
}

AFAIK it's a consequence of how we do method dispatch (maybe something about inherent method lookup or autoref?), but I couldn't say whether it's fundamental or incidental.

2 Likes

Ah yeah that sounds right - this desugared version fails to compile:

#![feature(fn_traits)]

fn foo(s: i32) -> String {
    (|s| s.to_string()).call_once((s,))
}
error[E0282]: type annotations needed
 --> src/lib.rs:4:7
  |
4 |     (|s| s.to_string()).call_once((s,))
  |       ^  - type must be known at this point
  |
help: consider giving this closure parameter an explicit type
  |
4 |     (|s: /* Type */| s.to_string()).call_once((s,))
  |        ++++++++++++

For more information about this error, try `rustc --explain E0282`.

I haven't studied the type inference algorithm in detail, but I believe it mostly just goes top-to-bottom through all statements in evaluation order, and tries to infer the types. For non-generic functions, it's mostly easy: check that the arguments conform to the desired parameter types, infer that the result has the type specified in the signature. Generics make it more complicated, since their type can be inferred "backwards" in a limited sense. It works introducing obligation equations, which track all unresolved generic parameters (including associated types), their trait bounds and possible equalities between them. On each step, the type checker tries to reduce the obligations, either finding the unique types satisfying them (for some parameters), or finding ambiguity or contradiction, either of which is a type error.

Method resolution is a wrench in this process: the deref coercion and method resolution algorithm in general make it very difficult to track all possible obligations without knowing the specifics of the receiver type (I think it's possible in principle, but it can easily cause an exponential blowup in type inference, since all possible deref possibilities need to be considered separately). Add in that the type inference for traits is a Turing-complete algorithm, and all of that means that inferring the method receiver type via obligations is generally infeasible, and quite brittle/slow even in the cases where we could do it.

For this reason, method resolution doesn't introduce obligations w.r.t. the receiver and possible traits defining the method. We require that the method can be uniquely resolved given the information that we already know about the receiver. Of course, the receiver may itself be generic, but that just means that we must find a properly generic unique trait impl which fits.

This means that we can't delay the resolution of to_string until the moment where we know more about s, even if at a later point s becomes uniquely defined. So the type checker errors out.

The trick with generic functions works because it changes the inference order. Instead of going left-to-right through the body of the closure, we find the generic parameters of your call function. This allows to look at the type of the second argument before the body of the closure, which breaks the typechecking block. It wouldn't help if the relation between parameter types were more complex, e.g. if call had a signature

fn call<T, R>(f: impl FnOnce(R) -> T, t: T) -> R;

In principle, your specific example with the closure is simple enough that it could be special-cased in the typechecker, but it's not clear that the win is worth the extra complexity, and changing the type inference algorithm is always a bit scary (what if we infer something differently, add support for something too brittle, or make a change we regret?).

It's not only method resolution.

struct S { s: i32 }
fn foo(s: S) {
    (|s| s.s)(s)
}
error[E0282]: type annotations needed
 --> src/lib.rs:3:7
  |
3 |     (|s| s.s)(s)
  |       ^  - type must be known at this point
  |
help: consider giving this closure parameter an explicit type
  |
3 |     (|s: /* Type */| s.s)(s)
  |        ++++++++++++

For more information about this error, try `rustc --explain E0282`.
1 Like

Isn't resolving fields basically just “method resolution”, too?

1 Like

I don't know how it's implemented. It needs to query Deref implementations, which is perhaps your point. (It also needs to query field names and privacy of types, but doesn't need to query method names and receivers of traits.)

1 Like

I wonder whether it's strictly necessary to do method resolution as soon as the compiler gets to the expression with the method call.

In principle is it possible to run type inference on the expressions which aren't method calls first, then go back and deal with those?

It absolutely is. The following two cases don't compile:

call((|s| s.to_string()).0, s)
call({|s| s.to_string()}, s)

There's a giant hack an elegant maneuver in the compiler with an appologetic comment:

3 Likes

Haha, I guess I feel less bad about special-casing specifically closure expressions on my end as well then :smiley: Fix closure conversion expressions by sfackler · Pull Request #19 · sfackler/staged-builder · GitHub

1 Like