Calling a function which takes a closure twice with different closures

Question

As a project for learning rust, I am writing a program which can parse sgf files (a format for storing go games, and technically also other games). Currently the program is supposed to parse strings of the type (this is just an exampel) ";B[ab]B[cd]W[ef]B[gh]" into [Black((0,1)),Black((2,3,)),White((4,5)),Black((6,7))]

For this I am using the parser-combinators library.

I have run into the following error:

main.rs:44:15: 44:39 error: can't infer the "kind" of the closure; explicitly annotate it; e.g. `|&:| {}` [E0187]
main.rs:44      pmove().map(|m| {Property::White(m)})
                            ^~~~~~~~~~~~~~~~~~~~~~~~
main.rs:44:15: 44:39 error: mismatched types:
 expected `closure[main.rs:39:15: 39:39]`,
    found `closure[main.rs:44:15: 44:39]`
(expected closure,
    found a different closure) [E0308]
main.rs:44      pmove().map(|m| {Property::White(m)})
                            ^~~~~~~~~~~~~~~~~~~~~~~~
error: aborting due to 2 previous errors
Could not compile `go`.

The function in question is below. I am completely new to rust, so I can't really isolate the problem further or recreate it in a context without the parser-combinators library (might even have something to do with that library?).

fn parse_go_sgf(input: &str) -> Vec<Property> {
    let alphabetic = |&:| {parser::satisfy(|c| {c.is_alphabetic()})};
    let prop_value = |&: ident, value_type| {
        parser::spaces().with(ident).with(parser::spaces()).with(
            parser::between(
                parser::satisfy(|c| c == '['),
                parser::satisfy(|c| c == ']'),
                value_type
            )
        )
    };

    let pmove = |&:| {
        alphabetic().and(alphabetic())
        .map(|a| {to_coord(a.0, a.1)})
    };

    let pblack = prop_value(
        parser::string("B"),
        pmove().map(|m| {Property::Black(m)}) //This is where I am first calling the map function.
    );

    let pwhite = prop_value(
        parser::string("W"),
        pmove().map(|m| {Property::White(m)}) //This is where the compiler complains
    );

    let pproperty = parser::try(pblack).or(pwhite);

    let mut pnode = parser::spaces()
        .with(parser::string(";"))
        .with(parser::many(pproperty));

    match pnode.parse(input) {
        Ok((value, _)) => value,
        Err(err) => {
            println!("{}",err);
            vec!(Property::Unkown)
        }
    }
}

So I am guessing this has something to do with closures all having different types. But in other cases it seems possible to call the same function with different closures. For example

let greater_than_forty_two = range(0, 100)
                         .find(|x| *x > 42);
let greater_than_forty_three = range(0, 100)
                         .find(|x| *x > 43);

Seems to work just fine.

So what is going on in my case that is different.

Also, as I am just learning, any general comments on the code are also welcome.

Answer 1

As the author of parser-combinators I will just chime in on another way of solving this, without needing to use the compiler to generate the return type.

As each parser is basically just a function together with 2 associated types there are implementations for the Parser trait for all function types.

impl <I, O> Parser for fn (State<I>) -> ParseResult<O, I>
    where I: Stream { ... }
pub struct FnParser<I, O, F>(F);
impl <I, O, F> Parser for FnParser<I, O, F>
    where I: Stream, F: FnMut(State<I>) -> ParseResult<O, I> { ... }

These should all be replaced by a single trait and the FnParser type removed, once the orphan checking allows it. In the meantime we can use the FnParser type to create a parser from a closure.

Using these traits we can essentially hide the big parser type returned from in Vladimir Matveev's example.

fn prop_value<'r, I, P, L, R>(ident: I, value_type: P, l: L, r: R, input: State<&'r str>) -> ParseResult<Property, &'r str>
    where I: Parser<Input=&'r str, Output=&'r str>,
      P: Parser<Input=&'r str, Output=Property>,
      L: Fn(char) -> bool,
      R: Fn(char) -> bool {
    parser::spaces().with(ident).with(parser::spaces()).with(
        parser::between(
            parser::satisfy(l),
            parser::satisfy(r),
            value_type
        )
    ).parse_state(input)
}

And we can now construct the parser with this

let parser = FnParser(move |input| prop_value(ident, value_type, l, r, input));

And this is basically the best we can do at the moment using rust. Unboxed anonymous return types would make all of this significantly easier since complex return types would not be needed (nor created since the library itself could be written to utilize this, avoiding the complex types entirely).

Answer 2

Unfortunately, you stumbled upon one of the rough edges in the Rust type system (which is, given the closure-heavy nature of parser-combinators, not really unexpected).

Here is a simplified example of your problem:

fn main() {
    fn call_closure_fun<F: Fn(usize)>(f: F) { f(12) }  // 1
    fn print_int(prefix: &str, i: usize) { println!("{}: {}", prefix, i) }

    let call_closure = |&: closure| call_closure_fun(closure);  // 2

    call_closure(|&: i| print_int("first", i));  // 3.1
    call_closure(|&: i| print_int("second", i)); // 3.2
}

It gives exactly the same error as your code:

test.rs:8:18: 8:47 error: mismatched types:
 expected `closure[test.rs:7:18: 7:46]`,
    found `closure[test.rs:8:18: 8:47]`
(expected closure,
    found a different closure) [E0308]
test.rs:8     call_closure(|&: i| print_int("second", i));
                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

We have (referenced in the comments in the code):

1. a function which accepts a closure of some concrete form;
2. a closure which calls a function (1) with its own argument;
3. two invocations of closure (1), passing different closures each time.

Rust closures are unboxed. It means that for each closure the compiler generates a fresh type which implements one of closure traits (Fn, FnMut, FnOnce). These types are anonymous - they don't have a name you can write out. All you know is that these types implement a certain trait.

Rust is a strongly- and statically-typed language: the compiler must know exact type of each variable and each parameter at the compile time. Consequently it has to assign types for every parameter of every closure you write. But what type should closure argument of (2) have? Ideally, it should be some generic type, just like in (1): the closure should accept any type as long as it implements a trait. However, Rust closures can't be generic, and so there is no syntax to specify that. So Rust compiler does the most natural thing it can - it infers the type of closure argument based on the first use of call_closure, i.e. from 3.1 invocation - that is, it assigns the anonymous type of the closure in 3.1!

But this anonymous type is different from the anonymous type of the closure in 3.2: the only thing they have in common is that they both implement Fn(usize). And this is exactly what error is about.

The best solution would be to use functions instead of closures because functions can be generic. Unfortunately, you won't be able to do that either: your closures return structures which contain closures inside themselves, something like

pub struct Satisfy<I, Pred> { ... }

where Pred is later constrained to be Pred: FnMut(char) -> bool. Again, because closures have anonymous types, you can't specify them in type signatures, so you won't be able to write out the signature of such generic function.

In fact, the following does work (because I've extracted closures for parser::satisfy() calls to parameters):

fn prop_value<'r, I, P, L, R>(ident: I, value_type: P, l: L, r: R) -> pp::With<pp::With<pp::With<pp::Spaces<&'r str>, I>, pp::Spaces<&'r str>>, pp::Between<pp::Satisfy<&'r str, L>, pp::Satisfy<&'r str, R>, P>>
    where I: Parser<Input=&'r str, Output=&'r str>,
          P: Parser<Input=&'r str, Output=Property>,
          L: Fn(char) -> bool,
          R: Fn(char) -> bool {
    parser::spaces().with(ident).with(parser::spaces()).with(
        parser::between(
            parser::satisfy(l),
            parser::satisfy(r),
            value_type
        )
    )
}

And you'd use it like this:

let pblack = prop_value(
    parser::string("B"),
    pmove().map(|&: m| Property::Black(m)),
    |c| c == '[', |c| c == ']'
);

let pwhite = prop_value(
    parser::string("W"),
    pmove().map(|&: m| Property::White(m)),
    |c| c == '[', |c| c == ']'
);

pp is introduced with use parser::parser as pp.

This does work, but it is really ugly - I had to use the compiler error output to actually determine the required return type. With the slightest change in the function it will have to be adjusted again. Ideally this is solved with unboxed abstract return types - there is a postponed RFC on them - but we're still not there yet.

Answer 3

The existing answer(s) are good, but I wanted to share an even smaller example of the problem:

fn thing<F: FnOnce(T), T>(f: F) {}

fn main() {
    let caller = |&: f| {thing(f)};
    caller(|&: _| {});
    caller(|&: _| {});
}

When we define caller, its signature is not fully fixed yet. When we call it the first time, type inference sets the input and output types. In this example, after the first call, caller will be required to take a closure with a specific type, the type of the first closure. This is because each and every closure has its own unique, anonymous type. When we call caller a second time, the second closure's (unique, anonymous) type doesn't fit!

As @wingedsubmariner points out, there's no way to create closures with generic types. If we had hypothetical syntax like for<F: Fn()> |f: F| { ... }, then perhaps we could work around this. The suggestion to make a generic function is a good one.

Answer 4

Two facets of Rust's closures are causing your problem, one, closures cannot be generic, and two, each closure is its own type. Because closure's cannot be generic,prop_value's parameter value_type must be a specific type. Because each closure is a specific type, the closure you pass to prop_value in pwhite is a different type from the one in pblack. What the compiler does is conclude that the value_type must have the type of the closure in pblack, and when it gets to pwhite it finds a different closure, and gives an error.

Judging from your code sample, the simplest solution would probably be to make prop_value a generic fn - it doesn't look like it needs to be a closure. Alternatively, you could declare its parameter value_type to be a closure trait object, e.g. &Fn(...) -> .... Here is a simplifed example demonstrating these approaches:

fn higher_fn<F: Fn() -> bool>(f: &F) -> bool {
    f()
}
let higher_closure = |&: f: &Fn() -> bool | { f() };

let closure1 = |&:| { true };
let closure2 = |&:| { false };
higher_fn(&closure1);
higher_fn(&closure2);
higher_closure(&closure1);
higher_closure(&closure2);