How to have a value (a collection of values) and separate mutable pointers to the values

I have a recursive collection (list of lists of lists type of thing, with all the lists being values and what they store being values, i.e., no references).

To populate the collection I need to keep track of the current list so that I can add values to it. I am trying to do this by having the overall list value stored in data and a list of pointers to the lists as they are encountered in a stack so I can add new values to the right list.

If this were C/C++ I'd just have a std::vec<*Value> (or maybe use a smart pointer), but I can't get this working in rust.

Below is a very cut down (so may not be syntactically incorrect) version of what I'm trying to do. The problem appears to be at line XXX: here I want to add a pointer to the current list, but the lifetime isn't long enough.

pub enum Value {
    Int(i64),
    List(List),
    Str(String),
}

pub struct List {
    values: Vec<Value>,
}

struct A {
    data: Value
    had_root: bool
    stack: Vec<Rc<RefCell<&'a mut Value>>>, // DOESN'T WORK
}

impl A {
    fn new() -> Self {
	A { data: Value::List(List::default()), stack: vec![],
	    had_root: false }
    }

    fn populate(&mut self) {
	// ...
        {
            if !self.stack.is_empty() {
                let mut last = self.stack.last_mut().unwrap().borrow_mut();
                if last.is_list() {
                    last.as_list_mut().unwrap().push(value);
                }
            }
            self.stack.push(Rc::new(RefCell::new(&mut value))); // XXX
        }
        if !self.had_root { // only called once
            self.data = value;
            self.had_root = true;
        }
    }
}

There's no safe way to create a self-referencial struct using actual references in Rust [1]. There are a couple crates to support the pattern to some extent.

Alternatively, sometimes you can keep the borrows in a separate struct (though in not sure that matches your use case).


  1. without also exclusively borrowing yourself forever, which is an extremely niche application ↩︎

So what is the pattern in rust? Is it something like this:

pub enum Value {
    Int(i64),
    List(Box<List>),
    Str(String),
}

pub struct List {
    values: Vec<Box<Value>>,
}

There’s two strategies I commonly use in situations like this:

  1. Store integer indices instead on the stack, and only turn them into mutable references temporarily when you want to make a modification.
  2. Store the lists-in-progress as owned values on the stack, and only move them into the main datastructure once they are complete.
1 Like

I've switched to using Rc<RefCell<>>s for the lists.
Almost all of it compiles, but when I want to add a Rc<RefCell> to the list thats the last (top) item of the stack, I can't get it to compile:

pub enum Value {
    Int(i64),
    List(Rc<RefCell<List>>),
    Str(String),
}

struct A {
    data: Value,
    stack: Vec<Rc<RefCell<Value>>>, // Only ever stores Lists
}

pub struct List {
    values: Vec<Value>,
}

impl A {
    fn populate(&mut self) {
        ...
        if !self.stack.is_empty() {
            let mut last = self.stack.last_mut().unwrap();
            let last = last.borrow_mut();
            if last.borrow().is_list() {
                last.borrow_mut().push(value);
                // ERROR          ^^^^ method not found in `&mut Rc<RefCell<Value>>`
            }
        }
        self.stack.push(Rc::new(RefCell::new(value)));
    }
}

If you want to see the real code in context, it is all in this repo: uxf. To try it cd to the rs subdir and run cargo test or cargo build or cargo run -- -cl ../testdata/t0.uxf -.

Your stack contains Value, not List, and push is only on List.values, not the general purpose Value. The is_list check is meaningless to the compiler, and doesn't change the fact that Value is Value and has no push method.

Change is_list to get_list that returns Option<Rc<RefCell<List>>> or Option<&RefCell<List>> if it is a list, an then you'll be able to borrow it and push.

1 Like

The is_list() is a Value method.
This actually works (but looks horrible):

            let mut last = self.stack.last_mut().unwrap();
           (*(*(*last.borrow_mut())).borrow_mut().as_list().unwrap()).borrow_mut().push(value);

However, it doesn't really help since although I do want to put the actual value into the collection that the last item in the stack points to, I also want to put an Rc<RefCell<>> of that value into the stack, and of course I can't because then I get a "value used here after move" error.

I'm now wondering if I'd be better off trying to use C++. My main motivation for using Rust isn't the language per se, but the ecosystem (cargo etc.).

Rust has a lot of syntax and helpers to avoid ever using unwrap(), e.g.:

if let Some(list) = self.stack.last().and_then(|v| v.as_list()) {
   list.borrow_mut().push(value);
}
1 Like

Given your problem description, and glancing at the repository, this seems like the wrong approach. Would a strategy like this work for you, which builds a complete list first, and then adds it to the parent after it's completely built?

pub enum Value {
    Int(i64),
    List(List),
    Str(String),
}

struct ListBuilder {
    stack: Vec<List>, // Only ever stores Lists
}

#[derive(Default)]
pub struct List {
    values: Vec<Value>,
}

impl ListBuilder {
    fn new()->Self {
        ListBuilder { stack: vec![List::default()] }
    }
    
    fn leaf(&mut self)->&mut List {
        self.stack.last_mut().expect("Stack underflow!")
    }
    
    fn push_val(&mut self, x:Value) {
        self.leaf().values.push(x)
    }
    
    fn push_int(&mut self, x:i64) {
        self.push_val(Value::Int(x))
    }

    fn push_str(&mut self, x:String) {
        self.push_val(Value::Str(x))
    }
    
    fn open_sublist(&mut self) {
        self.stack.push(List::default());
    }
    
    fn close_sublist(&mut self) {
        let list = self.stack.pop().unwrap();
        self.push_val(Value::List(list));
    }
    
    fn finalize(mut self)->List {
        assert_eq!(self.stack.len(), 1, "Unbalanced open/close");
        self.stack.pop().unwrap()
    }
}

Rust Playground (rust-lang.org)

Unlike my ugly code, that doesn't compile at as_list() with "method not found in &Rc<RefCell<Value>>".

Your builder solution looks reasonable, but I've spent enough time fighting with rust for the time being. I hope that someone who's a far better rust programmer than I am will implement a Rust uxf library, because right now it seems beyond me.

I appreciate your help though; thank you.

PS I've now had one more go at this by creating two tiny examples, one in Python and one in Rust. The Python one works and the Rust one won't compile, but is at least self-contained and small enough that there's some hope. I've put it in a separate post: Works in Python; (im)?possible in Rust? How to populate a nested struct with a stack?

If you step away for now, there's a good chance that you'll come back in a couple weeks time after writing more Rust and immediately see what the problem was.

This sort of library is possible to write and doesn't necessarily need to use complicated tools like RefCell, it might just require a change of perspective. Something I've found useful is to think about the "ownership story" of my library and try to make sure values have an obvious parent-child relationship rather than creating a web of objects.

1 Like