Время жизни в рекурсивной структуре с изменяемой ссылкой

Я пытаюсь определить рекурсивную структуру, похожую на связанный список для обхода дерева. Узел имеет некоторые данные и доступ к своему родителю. Дочерний узел должен взаимно заимствовать своего родителя, чтобы обеспечить монопольный доступ, и освободить его после удаления. Я могу определить эту структуру, используя неизменяемые ссылки, но не тогда, когда я делаю родительскую ссылку изменяемой. Когда я делаю родительскую ссылку изменяемой, меня сбивает с толку ошибка компилятора, и я ее не понимаю.

Как я могу определить время жизни такой рекурсивной структуры с изменяемой родительской ссылкой?

Вот минимальный пример. Это компилируется, но использует ссылку только для чтения:

struct Node<'a> {
    // Parent reference. `None` indicates a root node.
    // I want this to be a mutable reference.
    pub parent: Option<&'a Node<'a>>,
    // This field just represents some data attached to this node.
    pub value: u32,
}

// Creates a root node
// I use a static lifetime since there's no parent for the root so there are no constraints there
fn root_node(value: u32) -> Node<'static> {
    Node {
        parent: None,
        value,
    }
}

// Creates a child node
// The lifetimes indicates that the parent must outlive its child
fn child_node<'inner, 'outer: 'inner>(
    parent: &'inner mut Node<'outer>,
    value: u32,
) -> Node<'inner> {
    Node {
        parent: Some(parent),
        value,
    }
}

// An example function using the struct
fn main() {
    let mut root = root_node(0);
    let mut c1 = child_node(&mut root, 1);
    let mut c2 = child_node(&mut c1, 2);
    {
        let mut c3 = child_node(&mut c2, 3);
        let c4 = child_node(&mut c3, 4);
        let mut cur = Some(&c4);
        while let Some(n) = cur {
            println!("{}", n.value);
            cur = n.parent;
        }
    }
    {
        let c5 = child_node(&mut c2, 5);
        let mut cur = Some(&c5);
        while let Some(n) = cur {
            println!("{}", n.value);
            cur = n.parent;
        }
    }
    println!("{}", c2.value);
}

Площадка для ржавчины: неизменный справочник

Мне нужна изменяемая ссылка, поэтому я попытался заменить структуру Node, чтобы использовать изменяемую ссылку:

struct Node<'a> {
    // Parent reference. `None` indicates a root node.
    // I want this to be a mutable reference.
    pub parent: Option<&'a mut Node<'a>>,
    // This field just represents some data attached to this node.
    pub value: u32,
}

Но тогда я получаю следующую ошибку:

error[E0623]: lifetime mismatch
  --> src/main.rs:25:22
   |
21 |     parent: &'inner mut Node<'outer>,
   |             ------------------------
   |             |
   |             these two types are declared with different lifetimes...
...
25 |         parent: Some(parent),
   |                      ^^^^^^ ...but data from `parent` flows into `parent` here

Площадка для ржавчины: изменяемая ссылка

Я не понимаю взаимосвязи между изменчивостью и потоком данных в поле. В неизменяемом случае я уже требовал, чтобы функции передавали изменяемые / исключительные ссылки. Я пробовал различные комбинации жизней (используя одну жизнь, меняя их отношения вспять и т. Д.), Но безуспешно.


person Demurgos    schedule 11.02.2020    source источник
comment
Уверен, что вся ваша концепция ошибочна. Эта структура допускает изменяемые псевдонимы (head.next.next и (head.next).next).   -  person Shepmaster    schedule 12.02.2020
comment
@Shepmaster Моя цель состоит в том, чтобы только самый нижний (активный) узел мог управлять данными в цепочке. Я не совсем понимаю ваше обозначение изменяемого псевдонима. В моем примере после создания c3 он заимствует c2 (а вместе с ним c1 и root), поэтому вы не можете получить к ним доступ, пока c2 не будет удален, и поэтому вы не должны иметь возможность использовать их псевдонимы (по крайней мере, это цель).   -  person Demurgos    schedule 12.02.2020
comment
Это сильно напоминает мне Как мне реализовать шаблон "Цепочка ответственности" с использованием цепочки черт-объектов?, но я не уверен, что это достаточно близко, чтобы отметить дубликат. Могут ли ответы на этот вопрос (как мой, так и вопрос Лукаса) пролить свет на вашу проблему?   -  person trentcl    schedule 12.02.2020
comment
@trentcl Спасибо, я разберусь. Чтобы дать больше контекста, я хочу использовать эту структуру для передачи данных между вызовами рекурсивных функций. Каждый узел представляет уровень вызова функции. Это гарантирует, что родительский элемент создается первым, я передаю его как изменяемую ссылку на следующий вызов, он создает дочерний узел с монопольным доступом к этому родительскому элементу, и когда внутренний вызов завершается, дочерний элемент удаляется, и я получаю обратно доступ к нему. родительский узел.   -  person Demurgos    schedule 12.02.2020
comment
@trentcl Вопрос, который вы разместили, действительно похож. На самом деле это более общий вопрос с использованием трейтов и того, где следующий узел устанавливается с помощью метода, а не при построении. Ваш ответ на этот вопрос действительно соответствует моему неизменному случаю. Проблема в том, что мне нужна изменчивость. Тем не менее, я считаю, что это помогло мне продвинуться в решении проблемы. Я чувствую, что это связано с вариацией на протяжении всей жизни. Я думаю, что помню, что неизменяемые ссылки в структурах ковариантны, а изменяемые - инвариантны, но я не уверен, означает ли это, что мой вопрос разрешим или нет.   -  person Demurgos    schedule 12.02.2020


Ответы (1)


Реализовать такую ​​рекурсивную структуру с изменяемыми ссылками невозможно из-за дисперсии.

В Rustonomicon есть раздел о дисперсии со следующей таблицей:

|           | 'a        | T         |
|-----------|-----------|-----------|
| &'a T     | covariant | covariant |
| &'a mut T | covariant | invariant |

В частности, &'a mut T инвариантен по отношению к T.

Основная проблема здесь в том, что Node знает только время жизни своего родителя, а не время жизни всех своих предков. Даже если в моем случае меня просто интересует изменение поля value предка, &mut Node также дает доступ для изменения поля parent любого предка в цепочке, где у нас нет доступа к точному времени жизни.

Вот пример, когда моя структура может вызывать несостоятельность с изменяемой родительской ссылкой. Следующий код будет принят, если T был ковариантным в &'a mut T:

fn main() {
    let mut root: Node<'static> = root_node(0);

    // where 'a corresponds to `root`
    let mut c1: Node<'a> = child_node(&mut root, 1);
    {
        let mut evil_root: Node<'static> = root_node(666);
        {
            // where 'b corresponds to `c1`
            let mut c2: Node<'b>  = child_node(&mut c1, 2);
            // where 'c corresponds to `c2`
            let mut c3: Node<'c>  = child_node(&mut c2, 3);

            // Here is the issue: `c3` knows that its ancestors live at least as long
            // as `c2`. But it does not know how long exactly.
            // With covariance, the lifetime of `evil_root` would be compatible since
            // it outlives `c2`. And because `&mut T` enables to mutate any field
            // we could do the following:
            let c2_ref: &mut Node<'c> = c3.parent.unwrap();
            let c1_ref: &mut Node<'c> = c2_ref.parent.unwrap();
            *c1_ref.parent = Some(&mut evil_root);
        }
    }
    // Trying to access the parent of `c1` now causes a read-after-free
    println!("{}", c1.parent.unwrap().value);
}

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

Поскольку &mut позволяет изменять любые поля, включая поля со ссылками, и поскольку этот вид рекурсии не отслеживает все родительские времена жизни, это было бы неверно. Для безопасной реализации такой рекурсивной структуры Rust потребуется ссылка, позволяющая изменять value (поскольку у него статическое время жизни, проблем нет), но не parent. В минимальном примере, который я опубликовал выше, этого можно достичь, используя неизменяемые ссылки для родителей и помещая данные узла за Cell или RefCell. Другое возможное решение (но я не особо в него разбирался) - разместить изменяемые родительские ссылки за Pin, но разыменование будет unsafe: мне придется вручную гарантировать, что я никогда не изменяю ссылку parent.

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

person Demurgos    schedule 12.02.2020