【问题】单链表 IterMut 的一种生存期错误怎么解决

viruscamp 发表于 2021-05-18 21:33

做 too many list 的单链表。Iter 和 IterMut 用了不同与文章的写法。
结果 Iter 可以，IterMut 败给了生存期检查。
我感觉生存期这方面 Iter 和 IterMut 是一样的啊，他要是报cannot borrow x as mutable more than once at a time 倒还好理解一些。
IterMut 这种错误怎么解决？

struct Node<T> {
    elem: T,
    next: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
pub struct LinkedStack<T> {
    head: Link<T>,
}

pub struct Iter<'a, T>(&'a Link<T>);
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        match self.0 {
            None => None,
            Some(node) => {
                self.0 = &node.next;
                Some(&node.elem)
            }
        }
    }
}

pub struct IterMut<'a, T>(&'a mut Link<T>);
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        match self.0 {
            None => None,
            Some(node) => {
                self.0 = &mut node.next;
                Some(&mut node.elem)
            }
        }
    }
}
// too many list 的写法 从 map 改回 match 了
pub struct IterMutBook<'a, T>(Option<&'a mut Node<T>>);
impl<'a, T> Iterator for IterMutBook<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        match self.0.take() {
            None => None,
            Some(node) => {
                self.0 = node.next.as_deref_mut();
                Some(&mut node.elem)
            }
        }
    }
}

附编译错误

error[E0495]: cannot infer an appropriate lifetime for pattern due to conflicting requirements
  --> too-many-linked-list\src\linked_stack\iter_x.rs:30:18
   |
30 |             Some(node) => {
   |                  ^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 27:13...
  --> too-many-linked-list\src\linked_stack\iter_x.rs:27:13
   |
27 |     fn next(&mut self) -> Option<Self::Item> {
   |             ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> too-many-linked-list\src\linked_stack\iter_x.rs:30:18
   |
30 |             Some(node) => {
   |                  ^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 25:6...
  --> too-many-linked-list\src\linked_stack\iter_x.rs:25:6
   |
25 | impl<'a, T> Iterator for IterMut<'a, T> {
   |      ^^
note: ...so that reference does not outlive borrowed content
  --> too-many-linked-list\src\linked_stack\iter_x.rs:31:26
   |
31 |                 self.0 = &mut node.next;
   |                          ^^^^^^^^^^^^^^

评论区

写评论

Grobycn 2021-05-19 11:15

~~我是指 IterMut 本身可能会改变链表长度。&mut Link 不仅能改变 node.elem，还能改变 node.next。~~

写着写着发现 IterMutBook 也可能发生这种情况，是我想多了。

--
👇
viruscamp: 有启发。
因为 &T 是 Copy 的, 所以 match 表达式和 match arm 的变量可以共存。
而 &mut T 是 !Copy 的, 所以 match 表达式在 match arm 内无效。

至于你说，这种实现有问题，具体是什么问题呢？能有伪代码描述吗？
我觉得没有问题，是因为持有 IterMut 时，是不可能调用 list.push list.pop 等函数改变长度的。
而且我们可以在 IterMut 内实现各种修改链表结构的操作

// 对 struct IterMutBook<'a, T>(Option<&'a mut Node<T>>);
fn insert_after(&mut self, elem: T) -> Option<()>; // 可能失败
// 对 struct IterMut<'a, T>(&'a mut Link<T>);
fn insert_at(&mut self, elem: T); //永远成功

--
👇
Grobycn: 参考 https://users.rust-lang.org/t/cannot-infer-appropriate-lifetime-for-mutable-reference/17485/3

The gist is when you hold a &'a mut T reference, you cannot give it out from a mutable of borrow of self for longer than you hold the mutable borrow of self.

This doesn't work either for the same reason - mutable references are not Copy, but move-only. This is different from immutable references, where you’re free to copy them around as much as you want.

另外说一句， pub struct IterMut<'a, T>(&'a mut Link<T>); 这种实现是有问题的，第三方使用者并不能确定 IterMut 使用之后链表长度是否发生变化。

作者 viruscamp 2021-05-19 10:49

有启发。
因为 &T 是 Copy 的, 所以 match 表达式和 match arm 的变量可以共存。
而 &mut T 是 !Copy 的, 所以 match 表达式在 match arm 内无效。

// 对 struct IterMutBook<'a, T>(Option<&'a mut Node<T>>);
fn insert_after(&mut self, elem: T) -> Option<()>; // 可能失败
// 对 struct IterMut<'a, T>(&'a mut Link<T>);
fn insert_at(&mut self, elem: T); //永远成功

--
👇
Grobycn: 参考 https://users.rust-lang.org/t/cannot-infer-appropriate-lifetime-for-mutable-reference/17485/3

The gist is when you hold a &'a mut T reference, you cannot give it out from a mutable of borrow of self for longer than you hold the mutable borrow of self.

This doesn't work either for the same reason - mutable references are not Copy, but move-only. This is different from immutable references, where you’re free to copy them around as much as you want.

另外说一句， pub struct IterMut<'a, T>(&'a mut Link<T>); 这种实现是有问题的，第三方使用者并不能确定 IterMut 使用之后链表长度是否发生变化。

作者 viruscamp 2021-05-19 10:32

用 unsafe 勉强实现了。测试没有问题。

pub struct IterMut<'a, T>(&'a mut Link<T>);
// 可以实现 insert_at 空串可插入 next() == None 也可插入
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node| unsafe {
            let node_ptr: *mut Node<T> = Box::into_raw(node);
            *self.0 = Some(Box::from_raw(node_ptr));
            self.0 = &mut (*node_ptr).next;
            &mut (*node_ptr).elem
        })
    }
}

Grobycn 2021-05-19 10:09

参考 https://users.rust-lang.org/t/cannot-infer-appropriate-lifetime-for-mutable-reference/17485/3

The gist is when you hold a &'a mut T reference, you cannot give it out from a mutable of borrow of self for longer than you hold the mutable borrow of self.

This doesn't work either for the same reason - mutable references are not Copy, but move-only. This is different from immutable references, where you’re free to copy them around as much as you want.

另外说一句， pub struct IterMut<'a, T>(&'a mut Link<T>); 这种实现是有问题的，第三方使用者并不能确定 IterMut 使用之后链表长度是否发生变化。

1 共 4 条评论, 1 页