Как реализовать превращение вектора объектов в дерево?

Question

[0ralo]

Вопрос такой, что я делаю не так, мой алгоритм не работает, не понимаю.
У меня есть вектор объектов

#[derive(Default, Clone, Debug)]
struct Node {
    name: String,
    source: String,

    path: String,
    leaf: bool,
    children: Vec<RcNode>
}

Заполнены только name и source. name содержит имя, source - путь в дереве(A.B.C).
После исполнения функции должна остаться 1 нода, которая содержит в children ее детей, которые содержут своих детей и тд.
Я серьёзно застрял на 1 моменте - мне нужно создать ноду, запушить ее в вектор а потом использовать, чего раст мне конечно не даёт. В интернете нашел примеры использования Rc>, но не сумел получить необходимого эффекта. Если есть готовые решения, подсказки, ошибки или лучшие практики - буду рад узнать

Моя попытка (не рабочий вариант)

use std::cell::RefCell;
use std::rc::Rc;


#[derive(Default, Clone, Debug)]
struct Node {
    name: String,
    source: String,

    path: String,
    leaf: bool,
    children: Vec<RcNode>
}

type RcNode = Rc<RefCell<&'static Node>>;

impl Node {
    fn fast(name: &str, source: &str) -> Node{
        Node{
            name: name.to_string(),
            source: source.to_string(),

            path: String::from(""),
            leaf: true,
            children: Vec::new()
        }
    }

    fn insert(&'static self, node: Node){
        let mut current = Rc::new(RefCell::new(self));
        let mut temp;
        for part in node.source.split(".") {
            temp = node.children.iter().find(|&v| v.borrow().path == part);

            match temp {
                None => {
                    let tmp: RcNode = Rc::new(
                        RefCell::new(
                            &Node {
                                name: String::new(),
                                source: String::new(),

                                path: part.to_string(),
                                leaf: true,
                                children: Vec::new()
                            }
                        )
                    );
                    current.borrow_mut().children.push(
                        tmp
                    );
                    current = tmp;
                }
                Some(val) => {
                    current = val.clone()
                }
            }
        }
    }
}

fn main() {
    let mut root = Node::default();
    root.insert(Node::fast("First", "e"));
    root.insert(Node::fast("First", "e.sources"));
    root.insert(Node::fast("First", "e.sources.two"));
    root.insert(Node::fast("First", "e.secret"));
    root.insert(Node::fast("First", "e.secret.left"));
    root.insert(Node::fast("First", "e.secret.right"));
    print!("{:#?}", root);
}

Кстати объект имеет атрибут leaf, но как его реализовать я даже еще не дошел.

Answer 1

[Дмитрий Беляев]

Главная проблема тут - лайфтаймы. В частности у переменной на стеке никогда не будет лайфтайма 'static.
Ну и отдавать в куда либо долгоживущее ссылку на временное значение - UB. Благо лайфтаймы и тут спасают.
Собственно для этого Rc и нужен - он владеющая ссылка. Соответственно в нём должно быть значение, а не ссылка (ссылка на ссылку редко когда нужна).

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Default, Clone, Debug)]
struct NodeInner {
    name: String,
    source: String,

    path: String,
    leaf: bool,
    children: Vec<Node>,
}

#[derive(Default, Clone, Debug)]
struct Node(Rc<RefCell<NodeInner>>);

impl Node {
    fn fast(name: impl Into<String>, source: impl Into<String>) -> Self {
        Self(Rc::new(RefCell::new(NodeInner {
            name: name.into(),
            source: source.into(),

            path: String::new(),
            leaf: true,
            children: Vec::new(),
        })))
    }

    fn insert(&self, node: Node) {
        let mut current = self.clone();
        for part in node.0.borrow().source.split(".") {
            let inner = node.0.borrow();
            let found = inner.children.iter().find(|&v| v.0.borrow().path == part);

            match found {
                None => {
                    let tmp = Node::fast(String::new(), String::new());
                    current.0.borrow_mut().children.push(tmp.clone());
                    current = tmp;
                }
                Some(val) => current = val.clone(),
            }
        }
    }
}

fn main() {
    let mut root = Node::default();
    root.insert(Node::fast("First", "e"));
    root.insert(Node::fast("First", "e.sources"));
    root.insert(Node::fast("First", "e.sources.two"));
    root.insert(Node::fast("First", "e.secret"));
    root.insert(Node::fast("First", "e.secret.left"));
    root.insert(Node::fast("First", "e.secret.right"));
    print!("{:#?}", root);
}

Как заполнять поля уже сами разбирайтесь, думаю тут не сложно

Comments

[0ralo]

Окей, а вопрос ещё. Зачем нужна прослойка в виде
struct Node(Rc<RefCell<NodeInner>>);
если я сделаю .clone() на экземпляр объекта Node, то 0 элемент нового объекта будет вести на ту же память что и оригинал?

[0ralo]

А еще у меня проблема, я добавил поля, но каждая ветка дерева растет из корня.

Оригинал

fn insert(&self, node: Node) {
        let mut current = self.clone();
        for part in node.0.borrow().source.split(".") {
            let inner = node.0.borrow(); -- вот тут по идее нужно идти по current.children, а не по node.children
            let found = inner.children.iter().find(|&v| v.0.borrow().path == part);

            match found {
                None => {
                    let tmp = Node::fast(String::new(), String::new());
                    current.0.borrow_mut().children.push(tmp.clone());
                    current = tmp;
                }
                Some(val) => current = val.clone(),
            }
        }
    }

Мой код

fn insert(&self, node: Node) {
        let mut current = self.clone();
        for part in node.0.borrow().source.split(".") {
            let found = current.0.borrow().children.iter().find(|&v| v.0.borrow().path == part.to_string());


            match found {
                None => {
                    let tmp = Node::fast(String::new(), String::new(), part);
                    current.0.borrow_mut().children.push(tmp.clone());
                    current = tmp;
                }
                Some(val) => current = val.clone(),
            }
        }
        current.0.borrow_mut().name = node.0.borrow().name.clone();
        current.0.borrow_mut().source = node.0.borrow().source.clone();
    }

Но на меня нападает опять borow checker.
Раст очень сложный после питона(

[Дмитрий Беляев]

0ralo, Rc - это умный указатель со счётчиком ссылок, который при клонировании просто увеличивает счётчик, а не копирует данные.
derive(Clone) просто реализует трейт Clone за нас таким образом, что просто делает клон через клонирование всех полей.
Так что по сути да, в Node указатель на одни и те же данные во всех копиях.

Ну а насчёт лайфтаймов, есть такая штука как временные объекты, это когда мы получили что-то, вызвали на нём метод, а после это что-то сразу дропается.
Но вот метод iter() создаёт итератор, который связан лайфтаймом с тем, от чего был вызван, а там у нас подобъект того, что вернул метод borrow() - то есть если вызывать в одну строчку, то borrow() вернёт как раз таки временный объект, который сразу после этой строки будет дропнут, а значит нам нельзя иметь итератор, ссылающийся на этот объект и вытаскивать что-то из этого итератора методом find()
Но если положить объект возвращаемый borrow() в отдельную переменную, он уже будет не временный, а вполне себе жить до конца области видимости этой переменной, что позволит нам ссылаться на его внутренности.