LINUX.ORG.RU

Rust, borrow rules и нерекурсивный обход рекурсивной структуры

 


0

4

Допустим, у нас есть некая рекурсивная структура. Например, n-арное дерево:

enum Tree<'a> {
  Leaf(i32),
  Node(Vec<&'a Tree<'a>>)
}

Допустим, мы хотим метод для получения самого левого потомка и хотим реализовать его нерекурсивно:

impl<'a> Tree<'a> {
  fn leftmost(&self) -> &'a Tree {
    let mut leftmost = self;
    while let Tree::Node(ref children) = *leftmost {
      leftmost = children[0]
    }
    leftmost
  }
}

Проверяем:

fn main() {
  let bottom = Tree::Leaf(42);
  let middle = Tree::Node(vec![&bottom]);
  let top = Tree::Node(vec![&middle]);
  
  if let Tree::Leaf(val) = *top.leftmost() {
    println!("val: {}", val)
  }
}

Печатает val: 42, как и ожидается.

Теперь мы хотим сделать так, чтобы на одного потомка произвольной вершины могли ссылаться несколько слотов родительской вершины, т. е. чтобы потомок был достижим разными путями. Поскольку нам нужно много ссылок на одно значение, нам нужен Rc<Tree>. Поскольку Rc неизменяем, нам нужен Rc<RefCell<Tree>>:

enum RCTree {
  Leaf(i32),
  Node(Vec<Rc<RefCell<RCTree>>>)
}
Пробуем реализовать leftmost:
impl RCTree {
  fn leftmost(&self) -> &RCTree {
    let mut leftmost = self;
    while let RCTree::Node(ref children) = *leftmost {
      // &Ref<RCTree> coerces to &RCTree
      leftmost = &children[0].borrow()
    }
    leftmost
  }
}
И тут нам лупит лопатой по морде borrow checker:
rustc 1.12.1 (d4f39402a 2016-10-19)
error: borrowed value does not live long enough
  --> <anon>:29:19
   |
29 |       leftmost = &children[0].borrow()
   |                   ^^^^^^^^^^^^^^^^^^^^
   |
note: reference must be valid for the anonymous lifetime #1 defined on the block at 25:32...
  --> <anon>:25:33
   |
25 |   fn leftmost(&self) -> &RCTree {
   |                                 ^
note: ...but borrowed value is only valid for the expression at 27:53
  --> <anon>:27:54
   |
27 |     while let RCTree::Node(ref children) = *leftmost {
   |                                                      ^

error: aborting due to previous error
Вопрос: можно ли реализовать таким образом leftmost для RCTree и если можно, то как?

★★★

Код не запускал, но как-то так:

use std::cell::Ref;

fn leftmost(&self) -> Ref<RCTree> {
    let mut leftmost = self;
    while let RCTree::Node(ref children) = *leftmost {
      // &Ref<RCTree> coerces to &RCTree
      leftmost = Ref::map(children[0].borrow(), |n| &n);
    }
    leftmost
}

PS: компилятор в этом случае прав, ибо ссылка живёт в области видимости borrow(). Закончилась область - закончилась и ссылка. А вы ее куда-то еще отдаёте. Всё. Нет ёё уже.

RazrFalcon ★★★★★ ()
Последнее исправление: RazrFalcon (всего исправлений: 1)
Ответ на: комментарий от RazrFalcon
leftmost = Ref::map(children[0].borrow(), |n| &n);

Так не сработает. Тут тип результата Ref<RCTree>, а в &RCTree преобразуется только &Ref<RCTree>. Если же взять ссылку от этого выражения, то опять же, оно живёт только внутри цикла, а отдать мы её пытаемся наружу.

PS: компилятор в этом случае прав, ибо ссылка живёт в области видимости borrow(). Закончилась область - закончилась и ссылка. А вы ее куда-то еще отдаёте. Всё. Нет ёё уже.

Конечно прав. Я с компилятором не спорю, просто не могу найти способа выразить предлагаемую семантику в случае Rc<Ref<T>>

Zenom ★★★ ()
Последнее исправление: Zenom (всего исправлений: 1)
Ответ на: комментарий от Zenom

Там в начале ссылка на статью, которая объясняет несколько подходов, в том числе Rc<RefCell<T>>

tailgunner ★★★★★ ()

Зачем возвращаешь &? Возвращай Rc (это же ref counter, да? - ну вот и создай копию и отдай кому надо), по идее проблем не должно быть.

anonymous ()
Ответ на: комментарий от anonymous

У нас ссылка leftmost имеет тип &RCTree, а Rc ссылается на RefCell. Типы не совпадут.

Zenom ★★★ ()
Ответ на: комментарий от Zenom

Ясен пень. Начать с того, что у тебя структура данных не оч. Вообще ноды у тебя спрятаны за Rc<RefCell<>>, а вызывать ты хочешь через по &. Как по-твоему Rc будет определять когда выкидывать свой контейнер, если ты заимствуешь &?

По сути ты пытаешься смешать динамическую (runtime) проверку времени жизни со статической (compile-time, тот самы borrow checker).

Вообще советую вот это почитать http://cglab.ca/~abeinges/blah/too-many-lists/book/

anonymous ()
Ответ на: комментарий от Zenom

Не понял. Вам нужно возвращать Ref<T>, а не &T. Вот и всё.

RazrFalcon ★★★★★ ()

... думал я написать ММО на расте, но понял, что оно того не стоит. Не хватает динамики типов и много гемороя с древовидными структурами. Короче, остаюсь на С++11, ибо ничего лучшего человечество пока не осилило придумать.

q0tw4 ★★★★ ()
Ответ на: комментарий от q0tw4

Когда надоест решать проблемы с памятью - приходите.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от RazrFalcon

Быстрее надоест объяснять компилятору, что то, что я делаю безопасно и, когда окажется, что подобное невозможно, искать разрезы, где можно подпереть ансейфом так, чтоб над ним всегда было реально safe. Быстрее просто культурно кодить и всегда помнить что кому принадлежит. Ну это когда один человек на проекте. Когда много, то наверно да, лучше перестраховаться, чем недостраховаться.

q0tw4 ★★★★ ()
Последнее исправление: q0tw4 (всего исправлений: 1)
Ответ на: комментарий от q0tw4

всегда помнить что кому принадлежит

Это когда некуда тратить ресурсы мозга.

tailgunner ★★★★★ ()
Ответ на: комментарий от tailgunner

некуда тратить ресурсы мозга.

Да, лучше их тратить на борьбу с компилятором. Причем без каких либо гарантий безкостыльной победы над ним.

q0tw4 ★★★★ ()
Ответ на: комментарий от q0tw4

Не хватает динамики типов

Что такое «динамика типов» в данном контексте?

DarkEld3r ★★★★★ ()
Ответ на: комментарий от q0tw4

некуда тратить ресурсы мозга.

Да, лучше их тратить на борьбу с компилятором

Компилятор нужно понять один раз и дальше жить долго и счастливо. А запоминать что кому принадлежит нужно постоянно.

tailgunner ★★★★★ ()
Ответ на: комментарий от DarkEld3r

Это хранение vtable в самом объекте, ну тоесть dynamic_cast.

q0tw4 ★★★★ ()
Ответ на: комментарий от q0tw4

У меня под 20k строк без единого unsafe. Ваши фантазии не обоснованы.

что я делаю безопасно

Типичный сишник. А потом поддержка превращается в бесконечное исправление утечек и сегфолтов.

всегда помнить что кому принадлежит

Вы или гений или быдлокодер. Если у меня в проге 100500 объектов, я физически не могу помнить всех их взаимосвязи.

RazrFalcon ★★★★★ ()

man visitor composite design patterns

anonymous ()
Ответ на: комментарий от q0tw4

dynamic_cast

Этот костыль даже в самих плюсах не рекомендуют использовать.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от q0tw4

Это хранение vtable в самом объекте, ну тоесть dynamic_cast.

Есть в Rust.

Zenom ★★★ ()
Ответ на: комментарий от tailgunner

Компилятор нужно понять один раз

Ок, как на расте написать ациклический ориентированный граф без выноса ребер в отдельный массив (массивы rc clidren и weak_rc parents). По нему нужна итерация с параллельной модификацией.

q0tw4 ★★★★ ()
Ответ на: комментарий от RazrFalcon

Тем не менее при использовании плагинов и прочих полезных техниках организации кода dynamic_cast неизбежен. В джавке кстати реально все на нем держится, хоть и завешено почти везде дженериками.

q0tw4 ★★★★ ()
Ответ на: комментарий от q0tw4

Без понятия. Но, если ты точно знаешь, что язык не позволяет сделать то, что тебе абсолютно необходимо, так и говори - «язык меня не устраивает».

А ссылка на методы реализации графов - выше.

tailgunner ★★★★★ ()
Ответ на: комментарий от Zenom

Есть в Rust.

Разве в расте можно перейти от трейта T1 к T2, если второй наследуется от первого?

DarkEld3r ★★★★★ ()
Ответ на: комментарий от DarkEld3r

Ну технически то всегда можно. Просто храните в мапе отображение указателей одного интерфейса на второй. Вот только связываться с таким...

q0tw4 ★★★★ ()
Ответ на: комментарий от q0tw4

Просто храните в мапе отображение указателей одного интерфейса на второй.

Ну так не интересно, но вдруг я чего-то не знаю. Так-то есть Any, но его возможности несколько ограничены.

DarkEld3r ★★★★★ ()
Ответ на: комментарий от DarkEld3r

В текущей реализации без костылей нельзя. Но этого и не было в постановке задачи.

Zenom ★★★ ()
Ответ на: комментарий от q0tw4

В джавке кстати реально все на нем держится, хоть и завешено почти везде дженериками.

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

Zenom ★★★ ()
Ответ на: комментарий от Zenom

Но этого и не было в постановке задачи.

Значит мы «постановку задачи» поняли по разному.

DarkEld3r ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.