When does a closure implement Fn, FnMut and FnOnce?

What are the specific conditions for a closure to implement the Fn, FnMut and FnOnce traits?

That is:

When does a closure not implement the FnOnce trait?
When does a closure not implement the FnMut trait?
When does a closure not implement the Fn trait?

For instance, mutating the state of the closure on it's body makes the compiler not implement Fn on it.

Solution

The traits each represent more and more restrictive properties about closures/functions, indicated by the signatures of their call_... method, and particularly the type of self:

FnOnce (self) are functions that can be called once
FnMut (&mut self) are functions that can be called if they have &mut access to their environment
Fn (&self) are functions that can be called if they only have & access to their environment

A closure |...| ... will automatically implement as many of those as it can.

All closures implement FnOnce: a closure that can't be called once doesn't deserve the name. Note that if a closure only implements FnOnce, it can be called only once.
Closures that don't move out of their captures implement FnMut, allowing them to be called more than once (if there is unaliased access to the function object).
Closures that don't need unique/mutable access to their captures implement Fn, allowing them to be called essentially everywhere.

These restrictions follow directly from the type of self and the "desugaring" of closures into structs; described in my blog post Finding Closure in Rust.

For information on closures, see Closures: Anonymous Functions that Can Capture Their Environment in The Rust Programming Language.