关于生命周期的问题

O.O 发表于 2023-08-12 11:58

Tags：生命周期,裸指针

我的链表及不可变迭代器，可变迭代器实现如下：

#[derive(Default)]
pub enum LinkList<T> {
    Ele(T, Box<LinkList<T>>),
    #[default]
    Empty,
}
pub struct LinkListIter<'a, T>(&'a LinkList<T>);
pub struct LinkListIterMut<'a, T>(&'a mut LinkList<T>);

对于不可变迭代器使用如下实现没有任何问题：

impl<'a, T> Iterator for LinkListIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.0 {
            Ele(data, next) => {
                self.0 = next;
                Some(data)
            }
            Empty => None,
        }
    }
}

但是对于可变迭代器的如下安全实现：

impl<'a, T> Iterator for LinkListIterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.0 {
            Ele(e, next) => {
                self.0 = next;
                Some(e)
            }
            Empty => None,
        }
    }
}

在Some(e)那里会有报错：lifetime may not live long enough method was supposed to return data with lifetime 'a but it is returning data with lifetime '1。（我无法修改方法签名，为&mut self添加生命周期标注来解决此问题）

当我使用如下不安全的代码就可以编译成功，且运行正常：

impl<'a, T> Iterator for LinkListIterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.0 {
            Ele(e, next) => unsafe {
                self.0 = &mut *(next as *mut Box<LinkList<T>>);
                Some(&mut *(e as *mut T))
            },
            Empty => None,
        }
    }
}

我有以下疑问：

为什么LinkListIter的Iterator实现没有报错，但是LinkListIterMut却有生命周期问题呢？
采用裸指针解引用再引用的方式可以跳过编译器生命周期检查吗？

评论区

写评论

作者 O.O 2023-08-13 08:20

谢谢大佬赐教。

--
👇
Pikachu: 最后回到原问题上来：

为什么IterMut不行？

因为mutable reference不是Copy的，所以需要reborrow，引入了额外的约束。

裸指针unsafe行不行？

就目前的实现来看，应该没有破坏aliasing rule。miri跑了一些简单的测试也没有发现问题。但建议还是照着楼上的例子，用Option绕开reborrow。

Pikachu 2023-08-13 07:00

最后回到原问题上来：

为什么IterMut不行？

因为mutable reference不是Copy的，所以需要reborrow，引入了额外的约束。

裸指针unsafe行不行？

就目前的实现来看，应该没有破坏aliasing rule。miri跑了一些简单的测试也没有发现问题。但建议还是照着楼上的例子，用Option绕开reborrow。

Pikachu 2023-08-13 04:01

记录一下解决问题的过程：

首先，给出一个最小的可以复现问题的代码。

pub fn get_mut<'a, 'b>(x: &'b mut &'a mut i32) -> &'a mut i32
where
    'b: 'a,
{
    *x
}

pub fn get<'a, 'b>(x: &'b mut &'a i32) -> &'a i32 {
    *x
}

这里的get_mut必须要有'b:'a的约束，否则会报和你问题里一样的错误，而get则不需要这个约束。

第二步，检查可以成功编译的代码的MIR。（变量重命名了一下保证可读性。）

fn get_mut(x: &mut &mut i32) -> &mut i32 {
    let mut ret: &mut i32;
    bb0: {
        ret = deref_copy (*x);
        return;
    }
}

fn get(x: &mut &i32) -> &i32 {
    let mut ret: &i32;
    bb0: {
        ret = (*x);
        return;
    }
}

注意到get_mut的MIR中有一个deref_copy。出现这种区别的原因是shared reference是Copy的，但mutable reference不是。MIR里面对应这个的是CopyForDeref.

第三步，尝试把get_mut的实现替换成todo!()，并去掉'b:'a的约束。这一步是为了确定是函数签名本身需要这个约束，还是函数的实现导致必须满足这个约束。验证的结果是空实现的函数不需要'b:'a的约束。

第四步，读NLL...分割线以下是我最终的理解。

get_mut里应该发生了reborrow。我猜测，ret = deref_copy (*x);这一行等价于ret = &**x;（暂时没找到具体的文档，所以这里只能猜一下）。**x的supporting prefixes包括了*x和x，所以这产生了x outlive ret的约束。这也就是你看到的报错和必须加'b:'a约束的原因。

对于get里的情况，我这里有两种理解。两种理解导致了同样的生命周期约束，但前一种应该更接近编译器做的事情。

第一种，shared reference本身就是Copy的，所以ret = (*x);只需要考虑subtype的约束，根本没有reborrow发生。

第二种，即使我们假设reborrow确实发生了，**x的supporting prefixes只包含*x，而不包含x，所以同样只有一个subtype的约束。

最后，官方文档里有一个完美的例子说明为什么你的next函数是无法通过编译的。具体情况请参考reborrow constraints里面的example 3。

aj3n 2023-08-13 01:10

pub struct ListNode<T> {
    value: T,
    next: Option<Box<Self>>,
}

pub struct IterMut<'a, T>(Option<&'a mut ListNode<T>>);

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
	//XXX: try remove .take()
        match self.0.take() {
            Some(ListNode { value, next }) => {
                self.0 = next.as_mut().map(AsMut::as_mut);
                Some(value)
            }
            None => None,
        }
    }
}

这是我之前的iter_mut的实现，去掉了self.0.take()以后也会出现同样的报错，你可以参考这个修复思路;

我还没有找到具体的原因，观察你的代码里ret_val和next的生命周期应该是推导成了依赖&mut self（也就是'1)而不‘a，直觉和match &mut T的语义有关;

night-cruise 2023-08-12 21:51

对呀，为什么呢。我之前一直用的裸指针实现数据结构，还真没见过这种问题。

1 共 5 条评论, 1 页