How to use fine-grained methods in a struct?

Question

I have created a small program where I add users to a register. When I take an object oriented approach in Java, it is quite common to decompose functionality into smaller methods, so I have created addUser and findUser methods for Register. When I compile this program I get the following compilation errors. I have read about borrowing, but could not find a way to fix this.

struct User {
    userId: u8,
    age: u8,
}
struct Register {
    users: Vec<User>,
}

impl Register {
    // Initialize
    fn init() -> Register {
        Register {
            users: Vec::new()
        }
    }

    // Add user to register, if user does not exist in register
    fn addUser(&mut self, user: User) {
        match self.findUser(user.userId) {
            Some(u) => println!("User exists!"),
            None => self.users.push(user),
        };
    }

    // If user exists, return user, else return None
    fn findUser(&self, userId: u8) -> Option<&User> {
        for user in &self.users {
            if user.userId == userId {
                return Some(&user);
            }
        }
        None
    }
}

(playground)

Compilation error message:

error[E0502]: cannot borrow `self.users` as mutable because `*self` is also borrowed as immutable
  --> src/main.rs:18:21
   |
16 |         match self.findUser(user.userId) {
   |               ---- immutable borrow occurs here
17 |             Some(u) => println!("User exists!"),
18 |             None => self.users.push(user),
   |                     ^^^^^^^^^^ mutable borrow occurs here
19 |         };
   |         - immutable borrow ends here

Answer 1

This is an old problem, which is someday solved by non-lexical lifetimes. Your program is safe, the compiler just is not able to see that (yet!).

There are many ways to work around this problem; here is one possibility (playground):

fn add_user(&mut self, user: User) {
    let user_pos = self.users.iter().position(|u| u.user_id == user.user_id);
    match user_pos {
        Some(pos) => {
            let u = &self.users[pos];  // get the user like that
            println!("User exists!");
        }
        None => self.users.push(user),
    }
}

The key insight: we find the position in the vector first and use that position later to index the vector. This delays referencing something inside the vector.

---

A few additional notes:

• I got rid of the findUser method: it's a super common algorithm, so there are shortcuts already. I recommend you getting familiar with the Iterator API to write very brief and easy to read algorithms.
• I changed the names to match the idiomatic naming in Rust: snake_case.
• Searching through the vector every time is in O(n); it takes linear time. Inserting n users into your register has a time complexity of O(n²). This is probably not what you want. Why not use a set data structure, like HashSet or BTreeSet?

Answer 2

Why the rustc complains

The first thing to do in this case is of course understand why rustc thinks what you're doing is not allowed. So let's look at what you're trying to do:

A Register contains a vector of Users. findUser returns a reference into that vector. addUser pushes a new User into that vector. So far so good. addUser uses findUser to find an Option<&User>. That (optional) reference to a User refers to a User inside the users vector. If a matching User is found, the reference in u points to a valid User, but you ignore it. If no matching User is found, no reference exists, but you mutate the vector. Pushing onto the vector, of course, potentially requires a reallocation, which would invalidate references into the vector. However, this is not a problem, as no reference into the vector exists at that point.

But this is where rustc (or more concretely: the borrowchecker) falls short: when the borrowchecker sees

    match self.findUser(user.userId){
        // ...
    };

it concludes that the Option<&User> must be live for the entire match body, and concludes from that that the &User must be live for the entire match body. Hence, when you try to push onto self.users inside the match body, it complains.

Solutions

One solution is to wait for the borrowchecker to become smarter and figure out that matching an Option<T> can ignore T's lifetime in the None branch.

A better short-term solution is to painstakingly explain to the borrowchecker that it's fine, by splitting up the checking and the pushing, e.g. as follows:

    let is_found = match self.findUser(user.userId){
        Some(u) => { println!("User exists!"); true},
        None => false
    };
    if !is_found {
        self.users.push(user)
    }

Another solution uses the fact that you really don't use the &User at all here, so that you can just write the following:

    if self.findUser(user.userId) // At this point there is still a `&User`
           .is_some() { // Here, it's lifetime is over and there's a `bool` instead
        println!("User exists!")
    } else {
        // No live references into `self.user` exist, mutation is trivially allowed
        self.users.push(user)
    }

Yet another solution would be to change the API of Register to reflect that you don't want to do anything with that matching user: just make a fn contains_user(&self, userId: u8) -> bool.

Footnote

By the way, as @starblue already mentioned in comments, the Rust naming convention is to use snake_case for method names. Also, init should probably just be called new.