How do I upgrade a reference to a mutable reference?

Question

I have a program that revolves around one shared data structure, proposing changes to the data, and then applying these changes at a later stage. These proposed changes hold references to the core object.

In C++ or another language, I would simply make the reference non-const, then mutate it when I need to. But Rust doesn't play well with this approach. (I asked about this in IRC earlier today, but sadly I'm still stuck.)

To help, I made a distilled example for booking tickets in a theatre, where theatre is the data structure, the Bookings are proposed changes, and the run method would be applying them if I could figure out how to get it to work!

Firstly, defining some data structures. A theatre has many rows, which have many seats each:

use std::sync::{Arc, RwLock};
use std::thread;

struct Theatre { rows: Vec<Row> }
struct Row { seats: Vec<Seat> }

struct Seat {
    number: i32,
    booked: bool,
}

impl Seat {
    fn new(number: i32) -> Seat {
        Seat { number: number, booked: false }
    }

    fn book(&mut self) {
        self.booked = true;
    }
}

Here, the get_booking method searches for a seat, returning a Booking with a reference to the seat it finds.

impl Theatre {
    fn get_booking<'t>(&'t self, number: i32) -> Option<Booking<'t>> {
        for row in self.rows.iter() {
            for seat in row.seats.iter() {
                if seat.number == number && seat.booked == false {
                    return Some(Booking { seats: vec![ seat ] })
                }
            }
        }

        None
    }
}

But this is where I get stuck. The run method has mutable access to the overall theatre (from its parameter), and it knows which seat to mutate (self). But since self isn't mutable, even though the theatre that contains it is, it can't be mutated.

struct Booking<'t> {
    seats: Vec<&'t Seat>
}

impl<'t> Booking<'t> {
    fn describe(&self) {
        let seats: Vec<_> = self.seats.iter().map(|s| s.number).collect();
        println!("You want to book seats: {:?}", seats);
    }

    fn run(&self, _theatre: &mut Theatre) {
        let mut seat = ??????;
        seat.book();
    }
}

Finally, a main method that would use it if it worked.

fn main() {
    // Build a theatre (with only one seat... small theatre)
    let theatre = Theatre { rows: vec![ Row { seats: vec![ Seat::new(7) ] } ] };
    let wrapper = Arc::new(RwLock::new(theatre));

    // Try to book a seat in another thread
    let thread = thread::spawn(move || {
        let desired_seat_number = 7;

        let t = wrapper.read().unwrap();
        let booking = t.get_booking(desired_seat_number).expect("No such seat!");

        booking.describe();

        let mut tt = wrapper.write().unwrap();
        booking.run(&mut tt);  // this is never actually reached because we still have the read lock
    });

    thread.join().unwrap();
}

What's annoying is that I know exactly why my current code doesn't work - I just can't figure out how Rust wants my program formatted instead. There are some things I don't want to do:

• The simplest solution is to have Booking hold an index to its seat, instead of a reference: in this case, with row and seat usize fields. However, although my theatre uses O(1) vectors, I'd also like to reference a value in the middle of a large tree, where having to iterate to find the value would be much more expensive. This would also mean that you couldn't, say, get the seat number (in the describe function) without having to pass in the entire Theatre.
• It would also be solved by having a Booking hold a mutable reference to the seat, which I could just then mutate as normal. However, this would mean I could only have one proposed change at a time: I couldn't, for example, have a list of bookings and apply them all at once, or have two bookings and only apply one.

I feel like I'm very close to having something that Rust will accept, but don't quite know how to structure my program to accommodate it. So, any pointers? (pun intended)

Answer 1

First, here's the code:

use std::sync::{Arc, RwLock};
use std::thread;
use std::sync::atomic::{AtomicBool, Ordering};

struct Theatre { rows: Vec<Row> }
struct Row { seats: Vec<Seat> }

struct Seat {
    number: i32,
    booked: AtomicBool,
}

impl Seat {
    fn new(number: i32) -> Seat {
        Seat { number: number, booked: AtomicBool::new(false) }
    }

    fn book(&self) {
        self.booked.store(true, Ordering::Release);
        println!("Booked seat: {:?}", self.number);
    }
}

impl Theatre {
    fn get_booking<'t>(&'t self, number: i32) -> Option<Booking<'t>> {
        for row in self.rows.iter() {
            for seat in row.seats.iter() {
                if seat.number == number && seat.booked.load(Ordering::Acquire) == false {
                    return Some(Booking { seats: vec![ seat ] })
                }
            }
        }

        None
    }
}

struct Booking<'t> {
    seats: Vec<&'t Seat>
}

impl<'t> Booking<'t> {
    fn describe(&self) {
        let seats: Vec<_> = self.seats.iter().map(|s| s.number).collect();
        println!("You want to book seats: {:?}", seats);
    }

    fn run(&self) {
        for seat in self.seats.iter() {
            seat.book();
        }
    }
}

fn main() {
    // Build a theatre (with only one seat... small theatre)
    let theatre = Theatre { rows: vec![ Row { seats: vec![ Seat::new(7) ] } ] };
    let wrapper = Arc::new(RwLock::new(theatre));

    // Try to book a seat in another thread
    let thread = thread::spawn(move || {
        let desired_seat_number = 7;

        let t = wrapper.read().unwrap();
        let booking = t.get_booking(desired_seat_number).expect("No such seat!");

        booking.describe();

        booking.run();
    });

    thread.join().unwrap();
}

View on playpen

There are two important changes:

1. The booked field was changed from bool to AtomicBool. The atomic types provide a store method that is available on immutable references. Therefore, we can make Seat::book() take self by immutable reference. If you have a more complex type that is not covered by the atomic types, you should instead use a Mutex or a RwLock.
2. I removed the &mut Theatre parameter on Booking::run(). If this is not acceptable, please leave a comment to explain why you need that reference.

As you found, you cannot have both a read lock and a write lock active at the same time on a RwLock. However, a Booking cannot live longer than the read lock on the Theatre, because it contains references inside the Theatre. Once you release the read lock, you cannot guarantee that the references you obtained will remain valid when you acquired another lock later on. If that's a problem, consider using Arc instead of simple borrowed pointers (&).