Cannot borrow as mutable more than once at a time in one code - but can in another very similar

I've this snippet that doesn't pass the borrow checker:

use std::collections::HashMap;

enum Error {
    FunctionNotFound,
}

#[derive(Copy, Clone)]
struct Function<'a> {
    name: &'a str,
    code: &'a [u32],
}

struct Context<'a> {
    program: HashMap<&'a str, Function<'a>>,
    call_stack: Vec<Function<'a>>,
}

impl<'a> Context<'a> {
    fn get_function(&'a mut self, fun_name: &'a str) -> Result<Function<'a>, Error> {
        self.program
            .get(fun_name)
            .map(|f| *f)
            .ok_or(Error::FunctionNotFound)
    }

    fn call(&'a mut self, fun_name: &'a str) -> Result<(), Error> {
        let fun = try!(self.get_function(fun_name));

        self.call_stack.push(fun);

        Ok(())
    }
}

fn main() {}

error[E0499]: cannot borrow `self.call_stack` as mutable more than once at a time
  --> src/main.rs:29:9
   |
27 |         let fun = try!(self.get_function(fun_name));
   |                        ---- first mutable borrow occurs here
28 | 
29 |         self.call_stack.push(fun);
   |         ^^^^^^^^^^^^^^^ second mutable borrow occurs here
...
32 |     }
   |     - first borrow ends here

My gut feeling is that the problem is tied to the fact that HashMap returns either None or a reference of the value inside the data structure. But I don't want that: my intention is that self.get_function should return either a byte copy of the stored value or an error (that's why I put .map(|f| *f), and Function is Copy).

Changing &'a mut self to something else doesn't help.

However, the following snippet, somewhat similar in spirit, is accepted:

#[derive(Debug)]
enum Error {
    StackUnderflow,
}

struct Context {
    stack: Vec<u32>,
}

impl Context {
    fn pop(&mut self) -> Result<u32, Error> {
        self.stack.pop().ok_or(Error::StackUnderflow)
    }

    fn add(&mut self) -> Result<(), Error> {
        let a = try!(self.pop());
        let b = try!(self.pop());

        self.stack.push(a + b);
        Ok(())
    }
}

fn main() {
    let mut a = Context { stack: vec![1, 2] };
    a.add().unwrap();
    println!("{:?}", a.stack);
}

Now I'm confused. What is the problem with the first snippet? Why doesn't it happen in the second?

The snippets are part of a larger piece of code. In order to provide more context, this on the Rust Playground shows a more complete example with the faulty code, and this shows an earlier version without HashMap, which passes the borrow checker and runs normally.

You have fallen into the lifetime-trap. Adding the same lifetime to more references will constrain your program more. Adding more lifetimes and giving each reference the minimal possible lifetime will permit more programs. As @o11c notes, removing the constraints to the 'a lifetime will solve your issue.

impl<'a> Context<'a> {
    fn get_function(&mut self, fun_name: &str) -> Result<Function<'a>, Error> {
        self.program
            .get(fun_name)
            .map(|f| *f)
            .ok_or(Error::FunctionNotFound)
    }

    fn call(&mut self, fun_name: &str) -> Result<(), Error> {
        let fun = try!(self.get_function(fun_name));

        self.call_stack.push(fun);

        Ok(())
    }
}

The reason this works is that Rust inserts new lifetimes, so in the compiler your function's signatures will look like this:

fn get_function<'b>(&'b mut self, fun_name: &'b str) -> Result<Function<'a>, Error>
fn call<'b>(&'b mut self, fun_name: &'b str) -> Result<(), Error>

Always try to not use any lifetimes and let the compiler be smart. If that fails, don't spray lifetimes everywhere, think about where you want to pass ownership, and where you want to limit the lifetime of a reference.

You only need to remove unnecessary lifetime qualifiers in order for your code to compile:

fn get_function(&mut self, fun_name: &str) -> Result<Function<'a>, Error> { ... }

fn call(&mut self, fun_name: &str) -> Result<(), Error> { ... }

Your problem was that you tied the lifetime of &mut self and the lifetime of the value stored in it (Function<'a>), which is in most cases unnecessary. With this dependency which was present in get_function() definition, the compiler had to assume that the result of the call self.get_function(...) borrows self, and hence it prohibits you from borrowing it again.

Lifetime on &str argument is also unnecessary - it just limits the possible set of argument values for no reason. Your key can be a string with arbitrary lifetime, not just 'a.