Skip to content

Instantly share code, notes, and snippets.

@nelhage

nelhage/README.md

Created April 26, 2018 03:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nelhage/fb214679a271f3a42f210af1f2912791 to your computer and use it in GitHub Desktop.
Save nelhage/fb214679a271f3a42f210af1f2912791 to your computer and use it in GitHub Desktop.
Download ZIP
Experience report: Trying to map an `FnMut` over a binary tree in Rust
Raw
README.md

This story is simplified from an attempt to write an AST walker for a toy compiler, but the essential facts are unchanged.

I am fairly new to Rust (but an experienced C++ programmer) and am trying to write a program to map an FnMut over a binary tree. I start with a simple tree definition, and try to write what seems to me to be the straightforward code:

use std::rc::Rc;

#[derive(Debug)]
enum Tree {
    Leaf(i32),
    Node(Rc<Tree>, Rc<Tree>),
}

fn map_tree<F>(tree: &Rc<Tree>, f: F) -> Rc<Tree>
where
    F: FnMut(Rc<Tree>) -> Rc<Tree>,
{
    match &**tree {
        &Tree::Leaf(_) => f(Rc::clone(tree)),
        &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, f), map_tree(&r, f))),
    }
}

pub fn main() {
    let tree = Rc::new(
    Tree::Node(Rc::new(Tree::Leaf(0)), Rc::new(Tree::Leaf(1))),
    );
    let mut sum = 0;
    map_tree(&tree, |node| {
        match *node {
            Tree::Leaf(i) => sum = sum + i,
            _ => unreachable!()
        }
        node
    });
    print!("sum={}", sum);
}

(playground link)

I've got a vague premonition that the borrow-checker will yell at me for using f twice in that latter clause, but hey, let's see what it says. It says:

error[E0596]: cannot borrow immutable argument `f` as mutable
  --> src/main.rs:14:27
   |
9  | fn map_tree<F>(tree: &Rc<Tree>, f: F) -> Rc<Tree>
   |                                 - consider changing this to `mut f`
...
14 |         &Tree::Leaf(_) => f(Rc::clone(tree)),
   |                           ^ cannot borrow mutably

error[E0382]: use of moved value: `f`
  --> src/main.rs:15:87
   |
15 |         &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, f), map_tree(&r, f))),
   |                                                                      -                ^ value used here after move
   |                                                                      |
   |                                                                      value moved here
   |
   = note: move occurs because `f` has type `F`, which does not implement the `Copy` trait

Well, I was right. Let's start by following the first piece of advice, from the E0596:

fn map_tree<F>(tree: &Rc<Tree>, mut f: mut F) -> Rc<Tree>
where
    F: FnMut(Rc<Tree>) -> Rc<Tree>,
{
    match &**tree {
        &Tree::Leaf(_) => f(Rc::clone(tree)),
        &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, f), map_tree(&r, f))),
    }
}

(playground link)

First error is resolved, but the second remains unchanged:

error[E0382]: use of moved value: `f`
  --> src/main.rs:15:87
   |
15 |         &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, f), map_tree(&r, f))),
   |                                                                      -                ^ value used here after move
   |                                                                      |
   |                                                                      value moved here
   |
   = note: move occurs because `f` has type `F`, which does not implement the `Copy` trait

Well, I've started to pick up Rust; I know what to do when I'm using a value temporarily and then want to use it again: I probably need more borrows. Because I'm new to this, I forget to borrow mutably:

fn map_tree<F>(tree: &Rc<Tree>, mut f: F) -> Rc<Tree>
where
    F: FnMut(Rc<Tree>) -> Rc<Tree>,
{
    match &**tree {
        &Tree::Leaf(_) => f(Rc::clone(tree)),
        &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, &f), map_tree(&r, &f))),
    }
}

(playground link)

This makes that error go away, but replaces it with a different -- very confusing -- spew:

error[E0277]: the trait bound `F: std::ops::Fn<(std::rc::Rc<Tree>,)>` is not satisfied
  --> src/main.rs:15:57
   |
15 |         &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, &f), map_tree(&r, &f))),
   |                                                         ^^^^^^^^ the trait `std::ops::Fn<(std::rc::Rc<Tree>,)>` is not implemented for `F`
   |
   = help: consider adding a `where F: std::ops::Fn<(std::rc::Rc<Tree>,)>` bound
   = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&F`
note: required by `map_tree`
  --> src/main.rs:9:1
   |
9  | / fn map_tree<F>(tree: &Rc<Tree>, mut f: F) -> Rc<Tree>
10 | | where
11 | |     F: FnMut(Rc<Tree>) -> Rc<Tree>,
12 | | {
...  |
16 | |     }
17 | | }
   | |_^

Why is std::ops::Fn suddenly appearing? I said FnMut. What is going on?

I eventually google around and realize I need more muts:

fn map_tree<F>(tree: &Rc<Tree>, mut f: F) -> Rc<Tree>
where
    F: FnMut(Rc<Tree>) -> Rc<Tree>,
{
    match &**tree {
        &Tree::Leaf(_) => f(Rc::clone(tree)),
        &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, &mut f), map_tree(&r, &mut f))),
    }
}

(playground link)

This now compiles the implementation, but blows up with a recursion limit at the call site!

error[E0275]: overflow evaluating the requirement `[closure@src/main.rs:22:21: 28:6 sum:&mut i32]: std::ops::FnMut<(std::rc::Rc<Tree>,)>`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
  = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut [closure@src/main.rs:22:21: 28:6 sum:&mut i32]`
...

At this point I'm pretty stuck and pretty frustrated.

But I need to break the recursion somehow, so maybe I need to also make map_vars take a reference so the inner and outer calls have the same type? I've not yet mastered Rust syntax, but I know &mut is a thing, and I've already got a mut in the signature, so let's stick an & on it:

fn map_tree<F>(tree: &Rc<Tree>, &mut f: F) -> Rc<Tree>
where
    F: FnMut(Rc<Tree>) -> Rc<Tree>,
{
    match &**tree {
        &Tree::Leaf(_) => f(Rc::clone(tree)),
        &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, &mut f), map_tree(&r, &mut f))),
    }
}

(playground link)

New error!

error[E0308]: mismatched types
 --> src/main.rs:9:33
  |
9 | fn map_tree<F>(tree: &Rc<Tree>, &mut f: F) -> Rc<Tree>
  |                                 ^^^^^^ expected type parameter, found &mut _
  |
  = note: expected type `F`
             found type `&mut _`
  = help: did you mean `mut f: &F`?

Well, there's a helpful "did you mean"; let's try that:

fn map_tree<F>(tree: &Rc<Tree>, mut f: &F) -> Rc<Tree>
where
    F: FnMut(Rc<Tree>) -> Rc<Tree>,
{
    match &**tree {
        &Tree::Leaf(_) => f(Rc::clone(tree)),
        &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, &mut f), map_tree(&r, &mut f))),
    }
}

(playground link)

No luck, and we're back to complaining about Fn, which I still haven't mentioned anywhere:

error[E0277]: the trait bound `F: std::ops::Fn<(std::rc::Rc<Tree>,)>` is not satisfied
  --> src/main.rs:15:57
   |
15 |         &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, &mut f), map_tree(&r, &mut f))),
   |                                                         ^^^^^^^^ the trait `std::ops::Fn<(std::rc::Rc<Tree>,)>` is not implemented for `F`
   |
   = help: consider adding a `where F: std::ops::Fn<(std::rc::Rc<Tree>,)>` bound
   = note: required because of the requirements on the impl of `std::ops::FnMut<(std::rc::Rc<Tree>,)>` for `&F`
note: required by `map_tree`
  --> src/main.rs:9:1
   |
9  | / fn map_tree<F>(tree: &Rc<Tree>, mut f: &F) -> Rc<Tree>
10 | | where
11 | |     F: FnMut(Rc<Tree>) -> Rc<Tree>,
12 | | {
...  |
16 | |     }
17 | | }
   | |_^

At this point I gave up and asked a Rustacean I knew on IRC, who pointed out that I was so close, and yet so far:

fn map_tree<F>(tree: &Rc<Tree>, f: &mut F) -> Rc<Tree>
where
    F: FnMut(Rc<Tree>) -> Rc<Tree>,
{
    match &**tree {
        &Tree::Leaf(_) => f(Rc::clone(tree)),
        &Tree::Node(ref l, ref r) => Rc::new(Tree::Node(map_tree(&l, f), map_tree(&r, f))),
    }
}

(playground link)

I can, with the benefit of hindsight, more-or-less understand what happened and the error messages at every step of the way. However, the experience of getting there was really frustrating, notably because at no point did the "did you mean" suggestions actually lead me particularly closer to my goal, and because I had to go by way of a compiler recursion overflow(!) before I could reach a working program.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment