Mutable borrow errors disappear when refining the type of a function pointer variable

In my function I need to rotate a VecDeque a certain amount of times, always in the same direction that depends on the input, with a value that never changes. So I started envisioning a solution like the following, where I can just assign the right rotation function to a function pointer and call it inside the loop to avoid repeating a useless branching.

(Playground)

use std::collections::VecDeque;

fn example(k: isize) -> Vec<usize> {
    let mut queue: VecDeque<usize> = VecDeque::from(vec![1, 2, 3, 4, 5]);
    let mut order = Vec::new();
    let rotation = 1 - k;
    let (amount, rotate) = match rotation >= 0 {
        true => (
            rotation as usize,
            VecDeque::rotate_right as fn(_, _),
        ),
        _ => (
            rotation.unsigned_abs(),
            VecDeque::rotate_left as fn(_, _),
        ),
    };

    while !queue.is_empty() {
        rotate(&mut queue, amount % queue.len());
        order.push(queue.pop_front().unwrap());
    }

    order
}

This would have worked, but as soon as I wrote the loop I got all manners of errors related to mutable and immutable borrows of queue. After some fiddling and the help of other people, it seems the most reasonable way is to write the code like this, with the differences highlighted by comments.

(Playground)

use std::collections::VecDeque;

fn example(k: isize) -> Vec<usize> {
    let mut queue: VecDeque<usize> = VecDeque::from(vec![1, 2, 3, 4, 5]);
    let mut order = Vec::new();
    let rotation = 1 - k;
    let (amount, rotate) = match rotation >= 0 {
        true => (
            rotation as usize,         
            VecDeque::rotate_right as fn(&mut _, _),
        ),                         // HERE ^
        _ => (
            rotation.unsigned_abs(), 
            VecDeque::rotate_left as fn(&mut _, _),
        ),                        // HERE ^
    };

    while !queue.is_empty() {
        let len = queue.len();

        rotate(&mut queue, amount % len);
                             // HERE ^
        order.push(queue.pop_front().unwrap());
    }

    order
}

Now, why exactly is the &mut required as if it provided a better suggestion for allowing the compiler to correctly infer the type of the function pointer? And inside the loop I also need to assign the current length of the queue to a separate variable first, due to the old known limitation of the borrow checker.

I'm not an expert on the compiler internals, but I think the difference is with the inferred lifetime. when you coerce to a function pointer type, the fn(&mut _) makes the inferred type having a universal qualified lifetime, but fn(_) makes the inferred the type with an single lifetime. e.g.

fn(&mut _, _); // ---> for <'a> fn(&'a mut VecDeque, usize)
fn(_, _); // ---> fn(&'some_lifetime mut VecDeque, usize)

the rule of two phase borrow doesn't apply here because you are calling the methods through a function pointer, but two phase borrow only allows the receiver of a method (i.e. &mut self) to have a temporary "reservation" phase.

an alternative is to turn the control flow inside out, i.e. nest the loop inside the branch, something like:

	// `impl Fn()` cannot be used for closure parameters,
	// for simplicity, this example use `&dyn Fn()` as a workaround
	let mut process = |rotate: &dyn Fn(&mut VecDeque<usize>)| {
		while !queue.is_empty() {
			rotate(&mut queue);
			order.push(queue.pop_front().unwrap());
		}
	};
	if rotation >= 0 {
		let amount = rotation as usize;
		process(&|queue| queue.rotate_right(amount % queue.len()));
	} else {
		let amount = rotation.unsigned_abs();
		process(&|queue| queue.rotate_left(amount % queue.len()));
	}
3 Likes

Incidentally, most people run into this inference failure when dealing with closures.

2 Likes