The following example is adapted from the definition of Iterator::find in the standard library. This doesn't compile because predicate is immutable:
fn check<T>(predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> bool {
move |x| predicate(&x)
}
// error[E0596]: cannot borrow `predicate` as mutable, as it is not declared as mutable
The error is resolved by declaring predicate as mutable, as the standard library does:
FnMut has signature fn call(&mut self, ...args) so by definition calling it borrows it. It's called FnMut for a reason. You can change it to Fn to see the difference.
With FnMut, any variables captured by the closure can be mutated by the closure. So the closure itself must be mutable.
Internally, a struct is created for a closure to contain the captured variables. In the generated code, a hidden self parameter is used to refer to the captured variables in this struct. For FnMut, &mut self is used. For Fn, &self is used. And for FnOnce, self is used; this means self is consumed which is why it can only be called once.