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

Question

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

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

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

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);
}

Rust Playground: неизменяемая ссылка

Я хочу изменяемую ссылку, поэтому я попытался заменить структуру 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

Rust Playground: изменяемая ссылка

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

Answer 1

Невозможно реализовать этот вид рекурсивной структуры с изменяемыми ссылками из-за дисперсии .

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

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

В частности, &'a mut T является инвариантным относительно T.

Основная проблема здесь заключается в том, что узел знает только время жизни своего родителя, а не время жизни всех его предков. Даже если в моем случае меня просто интересует изменение поля 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 (так как он имеет время жизни c, проблем нет), но не parent. В приведенном выше минимальном примере это может быть достигнуто с помощью неизменных ссылок для родителей и размещения данных узла за Cell или RefCell. Другое возможное решение (но я не особо разбираюсь в этом) было бы поместить изменяемые родительские ссылки за Pin, но разыменование это было бы unsafe: я должен был бы вручную убедиться, что я никогда не изменяю parent reference.

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