Невозможно получить изменяемую ссылку при повторении рекурсивной структуры: не может заимствовать как изменчивый более одного раза за раз

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

type Link = Option<Box<Node>>;

struct Node {
    next: Link
}

struct Recursive {
    root: Link
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(ref mut node) = *anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

(Ссылка на площадку Rust)

Однако это не удается:

error[E0499]: cannot borrow 'anchor.0' as mutable more than once at a time
  --> src/main.rs:14:24
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ^^^^^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first mutable borrow occurs here
...
18 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to 'anchor' because it is borrowed
  --> src/main.rs:15:13
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ borrow of 'anchor' occurs here
15 |             anchor = &mut node.next;
   |             ^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed 'anchor' occurs here

error[E0499]: cannot borrow '*anchor' as mutable more than once at a time
  --> src/main.rs:17:9
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ first mutable borrow occurs here
...
17 |         anchor
   |         ^^^^^^ second mutable borrow occurs here
18 |     }
   |     - first borrow ends here

Это имеет смысл, поскольку и anchor и node ссылаются на одну и ту же структуру, но я действительно не забочусь о anchor больше после его разрушения.

Как можно корректно выполнить back() корректную работу с использованием надежной ржавчины?

Ответы

Ответ 1

Это возможно... но мне жаль, что у меня не было более элегантного решения.

Трюк НЕ заимствовать у anchor и, следовательно, жонглировать между двумя аккумуляторами:

один из которых содержит ссылку на текущий узел
другому назначается ссылка на следующий узел

Это приводит меня к:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            let tmp = anchor;
            if let Some(ref mut node) = *tmp {
                anchor = &mut node.next;
            } else {
                anchor = tmp;
                break;
            }
        }

        anchor
    }
}

Не совсем красиво, но это что-то, что может проверить заемщик ¯\_ (ツ) _/¯.

@ker улучшил это, создав неназванное временное:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            match {anchor} {
                &mut Some(ref mut node) => anchor = &mut node.next,
                other => return other,
            }
        }
    }
}

Трюк здесь заключается в том, что использование {anchor} перемещает содержимое anchor в неназванное временное, на котором выполняется совпадение. Поэтому в match блоке мы не заимствуем из anchor а из временного, оставляя нас свободными изменять anchor. См. Связанное сообщение в блоге. Функция идентификатора (в ржавчине).

Ответ 2

Вы можете использовать рекурсию для выполнения проверки чека. Это имеет недостаток в создании фрейма стека для каждого элемента в вашем списке. Если ваш список длинный, это, безусловно, приведет к переполнению стека. LLVM оптимизирует метод Node::back в цикле (см. LLVM IR, сгенерированный на игровой площадке)

impl Node {
    fn back(&mut self) -> &mut Link {
        match self.next {
            Some(ref mut node) => node.back(),
            None => &mut self.next,
        }
    }
}

impl Recursive {
    fn back(&mut self) -> Option<&mut Link> {
        self.root.as_mut().map(|node| node.back())
    }
}

Ответ 3

Исходный код работает как-то, когда включены нелегические времена жизни:

#![feature(nll)]

type Link = Option<Box<Node>>;

struct Node {
    next: Link
}

struct Recursive {
    root: Link
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(node) = anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

fn main() {}

Нелексические времена жизни повышают точность проверки счетчика компилятора, позволяя ему видеть, что изменчивый заимствование anchor больше не используется. Мы также можем упростить ключевые слова в if let из-за недавних изменений языка.

Ответ 4

Оно работает:

fn back(&mut self) -> &mut Link {
    let mut anchor = &mut self.root;
    while anchor.is_some(){
        anchor = &mut {anchor}.as_mut().unwrap().next;
    }
    anchor
}