How to correctly write struct that owns bunch of items and list of references for those items


#1

Let’s assume that at each moment item would be changed via mutable reference or via object in struct. Is my implementation prefect?

struct Object {
    item1: Box<Item>,
    item2: Box<Item>,
    list: Vec<&'static mut Item>,
}

impl Object {
    fn new() -> Object {
        let mut item1 = Box::new(Item::new);
        let mut item2 = Box::new(Item::new);
        let mut list = Vec::new();
        list.push(&mut item1);
        list.push(&mut item2);
        Object {
            item1: item1,
            item2: item2,
            list: list
        }
    }
}

This code is not compiles.


#2

You cannot do that in Rust. This has been answered in different ways on stackoverflow: http://stackoverflow.com/questions/28608823/how-to-model-complex-recursive-data-structures-graphs http://stackoverflow.com/questions/23135409/rust-borrowed-pointers-and-lifetimes

The easiest solution is to use Rc


#3

Currently I use Rc<RefCell<Item>>, but I brings runtime costs.


#4

Could item1 and item2 be indexes into list? That way you don’t need to have the references around, and accessing “item1” would be self.list[self.item1]. There would be additional overhead of accessing the array, but it should be minor.


#5

Do you suggest to save indices of items? Items may be removed from list, reordered and etc. Index is bad idea. I thought about it.


#6

How about this

use std::borrow::BorrowMut;

struct Item {
    id: i32,
}

impl Item {
    fn new(id: i32) -> Self {
        Item { id: id }
    }
}

struct Object<'a> {
    item1: Box<Item>,
    item2: Box<Item>,
    list: Vec<&'a mut Item>,
}

fn add_item_to_vec<'a>(item: &mut Box<Item>, vec: &mut Vec<&'a mut Item>) {
    let item: &mut Item = item.borrow_mut();
    let item = unsafe { &mut *(item as *mut Item) };
    vec.push(item);
}

impl<'a> Object<'a> {
    fn new() -> Self {
        let mut item1 = Box::new(Item::new(0));
        let mut item2 = Box::new(Item::new(1));
        let mut list: Vec<&'a mut Item> = Vec::new();
        add_item_to_vec(&mut item1, &mut list);
        add_item_to_vec(&mut item2, &mut list);
        Object {
            item1: item1,
            item2: item2,
            list: list,
        }
    }
}

fn main() {
    let mut object = Object::new();
    println!("{}", object.item1.id);
    object.item1.id = 25;
    println!("{}", object.list[0].id);
}

#7

The same problem is true for references, though. Even if you only append items to the list, the Vec will eventually need to resize, all of its items would be copied to a new place in memory, and then all of those references stored in the struct would become invalid.


#8

You can make something like this work. Since it’s nothing the borrowck understands, you need ‘unsafe’ and utmost care. To soundly modify items you need Box<UnsafeCell<Item>> instead, and internally &UnsafeCell<Item> in the vec.


#9

I made it
lib.rs

#![feature(raw)]

use std::borrow::{Borrow, BorrowMut};
use std::cell::UnsafeCell;
use std::marker::PhantomData;
use std::mem;
use std::raw::TraitObject;
use std::rc::Rc;

pub trait NodeChild {
    fn name(&self) -> &str;
}

pub struct NodeChildIndex<T: NodeChild> {
    index: Rc<UnsafeCell<usize>>,
    marker: PhantomData<T>,
}

impl<T: NodeChild> NodeChildIndex<T> {
    fn new(index: Rc<UnsafeCell<usize>>) -> Self {
        NodeChildIndex {
            index: index,
            marker: PhantomData::default(),
        }
    }

    fn index(&self) -> usize {
        unsafe { *self.index.get() }
    }
}

struct NodeChildData<'a> {
    index: Rc<UnsafeCell<usize>>,
    child: Box<NodeChild + 'a>,
}

impl<'a> NodeChildData<'a> {
    fn set_index(&mut self, new_index: usize) {
        let index = unsafe { &mut *self.index.get() };
        *index = new_index;
    }
}

pub struct Node<'a> {
    children: Vec<NodeChildData<'a>>,
}

impl<'a> Node<'a> {
    pub fn new() -> Self {
        Node { children: Vec::new() }
    }

    pub fn add_child<T: NodeChild + 'a>(&mut self, child: Box<T>) -> NodeChildIndex<T> {
        let index = Rc::new(UnsafeCell::new(self.children.len()));
        self.children.push(NodeChildData {
            index: index.clone(),
            child: child,
        });
        NodeChildIndex::new(index)
    }

    pub fn remove_child<T: NodeChild + 'a>(&mut self, index: NodeChildIndex<T>) -> Box<T> {
        let child = self.children.remove(index.index());
        for (index, child) in self.children.iter_mut().enumerate().skip(index.index()) {
            child.set_index(index);
        }
        unsafe {
            let raw_data = Box::into_raw(child.child);
            let raw_representation: TraitObject = mem::transmute(raw_data);
            let raw_data = raw_representation.data as *mut T;
            Box::from_raw(raw_data)
        }
    }

    pub fn child_at_index<T: NodeChild + 'a>(&self, index: &NodeChildIndex<T>) -> &T {
        let child: &(NodeChild + 'a) = self.children[index.index()].child.borrow();
        unsafe {
            let raw_representation: TraitObject = mem::transmute(child);
            let data = raw_representation.data as *const T;
            &*data
        }
    }

    pub fn child_at_index_mut<T: NodeChild + 'a>(&mut self, index: &NodeChildIndex<T>) -> &mut T {
        let child: &mut (NodeChild + 'a) = self.children[index.index()].child.borrow_mut();
        unsafe {
            let raw_representation: TraitObject = mem::transmute(child);
            let data = raw_representation.data as *mut T;
            &mut *data
        }
    }
}

main.rs

extern crate playground;
use playground::{NodeChild, Node};

struct A {
    index: i32,
}

impl A {
    fn say_hi(&self) {
        println!("Hi");
    }
}

impl NodeChild for A {
    fn name(&self) -> &'static str {
        "A"
    }
}

fn main() {
    let mut node = Node::new();
    let node_child_index = node.add_child(Box::new(A { index: 123123 }));
    {
        let child = node.child_at_index_mut(&node_child_index);
        println!("{}", child.name());
        child.say_hi();
    }
    let a = node.remove_child(node_child_index);
    println!("{}", a.index);
}

#10

I can’t vouch for the soundness of that implementation, but if the payload is that simple (usize) you can use Cell instead, which is both simple to use and is always itself sound. (Then it depends on what the rest of the code is doing). Cell<T> is only implemented for T: Copy.

Edit: I didn’t catch that Item was a simple copyable (possible to make Copy at least) type, I thought it was generic. If I had caught that, I’d have recommended Cell immediately.