Solving mutable and immutable borrow issue

#1

I am trying to build a System that contains Types, which contain Fields, which in turn refer to (other) Types. In other words, trying to implement something similar to a possible in-memory representation of parsing Rust structs.

I have the following code (playground), which gives an error: cannot borrow system as mutable because it is also borrowed as immutable. I have started to use enough Rust to understand why that is an error: Adding to system (a mutable borrow), which in turn adds to a vector, may move memory upon exhausting its capacity. This will make any dolled-out references (immutable borrows) dangled.

But I can't figure out how to do what I want/need to do. I think a Box or RefCell may be a part of a solution (to keep Type objects in heap and thus keep them valid even when the vector (of such wrapper) reallocates). However, not sure if this is the correct way to think about and how to put them to a good use.

pub struct System<'system> {
    types: Vec<Type<'system>>,
}

pub struct Type<'a> {
    pub name: String,
    pub fields: Vec<Field<'a>>,
}

pub struct Field<'a> {
    pub name: String,
    pub tpe: &'a Type<'a>,
}

impl<'system> System<'system> {
    fn new() -> Self {
        let primitive_types: Vec<Type> = ["Int", "String"].iter().map(|tname| Type {
            name: tname.to_string(),
            fields: vec![],
        }).collect();

        System {
            types: primitive_types,
        }
    }

    fn find_type(&self, name: String) -> Option<&Type<'system>> {
        self.types.iter().find(|tpe| tpe.name == name)
    }

    fn add_type(&mut self, tpe: Type<'system>) {
        self.types.push(tpe);
    }
}

pub fn test() {
    let mut system = System::new();

    let person_type = Type {
        name: "Person".to_string(),
        fields: vec![
            Field {
                name: "first_name".to_string(),
                tpe: system.find_type("String".to_string()).unwrap(),
            }
        ]
    };
    system.add_type(person_type);
}

Any hints on fixing this?

#2

You’re trying to build a self-referential type, where each Type stored in System::types might refer to other Types in the same vector. This isn’t possible with safe Rust. Instead, you need to use Rc or Arc in place of regular references. They provide shared ownership of the contained value— It is only dropped when the last copy of the reference goes away.

They don’t allow mutable access to the value inside, so they’re often paired with RefCell or Mutex. This is only necessary for you if a Type may need to be modified after it’s been added to the System. I’ve adapted your code to use Arc:

use std::sync::Arc;

pub struct System {
    types: Vec<Arc<Type>>,
}

pub struct Type {
    pub name: String,
    pub fields: Vec<Field>,
}

pub struct Field {
    pub name: String,
    pub tpe: Arc<Type>,
}

impl System {
    fn new() -> Self {
        let primitive_types: Vec<Arc<Type>> = ["Int", "String"].iter().map(|tname| Type {
            name: tname.to_string(),
            fields: vec![],
        }).map(Arc::new).collect();

        System {
            types: primitive_types,
        }
    }

    fn find_type(&self, name: String) -> Option<Arc<Type>> {
        self.types.iter().find(|tpe| tpe.name == name).cloned()
    }

    fn add_type(&mut self, tpe: Arc<Type>) {
        self.types.push(tpe);
    }
}

pub fn test() {
    let mut system = System::new();

    let person_type = Type {
        name: "Person".to_string(),
        fields: vec![
            Field {
                name: "first_name".to_string(),
                tpe: system.find_type("String".to_string()).unwrap(),
            }
        ]
    };
    system.add_type(Arc::new(person_type));
}
6 Likes
#3

Thank you!