rust - `cannot infer an appropriate lifetime for autoref due to conflicting requirements` 但由于 trait 定义限制，不能改变任何东西

Question

我通过跟随 too many linked lists 来实现链表.尝试实现时 iter_mut() ，我自己做了，并制作了以下代码:

type Link<T> = Option<Box<Node<T>>>;

pub struct List<T> {
    head: Link<T>,
}

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut::<T>(&mut self.head)
    }
}

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

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

    fn next<'b>(&'b mut self) -> Option<&'a mut T> {
        self.0.as_mut().map(|node| {
            self.0 = &mut (**node).next;
            &mut (**node).elem
        })
    }
}

我要避免强制和省略，因为明确让我了解更多。
错误:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/third.rs:24:16
   |
24 |         self.0.as_mut().map(|node| {
   |                ^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime `'b` as defined on the method body at 23:13...
  --> src/third.rs:23:13
   |
23 |     fn next<'b>(&'b mut self) -> Option<&'a mut T> {
   |             ^^
note: ...so that reference does not outlive borrowed content
  --> src/third.rs:24:9
   |
24 |         self.0.as_mut().map(|node| {
   |         ^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 20:6...
  --> src/third.rs:20:6
   |
20 | impl<'a, T> Iterator for IterMut<'a, T> {
   |      ^^
note: ...so that reference does not outlive borrowed content
  --> src/third.rs:25:22
   |
25 |             self.0 = &mut (**node).next;
   |                      ^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0495`.

我看过 Cannot infer an appropriate lifetime for autoref due to conflicting requirements .
我懂一点，但不多。我在这里面临的问题是，如果我尝试更改任何内容，则会弹出一个错误，指出无法匹配特征定义。
我的想法是基本上我需要以某种方式说明生命周期 'b活下去 'a即 <'b : 'a>但我不知道该怎么做。另外，我有类似的功能来实现 iter()这工作正常。我很困惑为什么 iter_mut()产生这样的错误。
迭代器

type Link<T> = Option<Box<Node<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> {
        self.0.as_ref().map(|node| {
            self.0 = &((**node).next);
            &((**node).elem)
        })
    }
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter::<T>(&self.head)
    }
}

☝️这有效。

Answer 1

关键是您需要能够以某种方式提取 Option<&'a mut T>来自 &'b mut IterMut<'a, T> .

了解原因 IterMut<'a, T> := &'a mut Link<T>不能工作，你需要了解你可以用可变引用做什么。当然，答案几乎就是一切。您可以从中复制数据、更改其值以及许多其他操作。你不能做的一件事就是使它无效。如果要将可变引用下的数据移出，则必须将其替换为相同类型(包括生命周期)的内容。

体内next , self是(本质上)&'b mut &'a mut Link<T> .除非我们知道 T (在这种情况下我们不能)，根本没有办法产生 &'a mut Link<T> 类型的东西。由此。例如，如果这在一般情况下是可能的，我们将能够做到

fn bad<'a, 'b, T>(_x: &'b mut &'a mut T) -> &'a mut T {
    todo!()
}

fn do_stuff<'a>(x: &'a mut i32, y: &'a mut i32) {
    // lots of stuff that only works if x and y don't alias
    *x = 13;
    *y = 42;
}

fn main() {
    let mut x: &mut i32 = &mut 0;
    let y: &mut i32 = {
        let z: &mut &mut i32 = &mut x;
        bad(z)
    };
    // `x` and `y` are aliasing mutable references
    // and we can use both at once!
    do_stuff(x, y);
}

(playground link)

关键是，如果我们能够在短期(通用)生命周期内借用一些东西 'b并返回允许在较长生命周期内修改的内容 'a ，我们将能够使用多个短生命周期(短于 'a 且不重叠)来获得多个具有相同生命周期的可变引用 'a .

这也解释了为什么不可变版本有效。使用不可变引用，从 &'b &'a T 开始是微不足道的至 &'a T : 只是尊重并复制不可变的引用。相比之下，可变引用不实现 Copy .

所以如果我们不能产生 &'a mut Link<T>来自 &'b mut &'a mut Link<T> ，我们当然不能得到 Option<&'a mut T或者(除了 None )。 (请注意，我们可以生成 &'b mut Link<T> ，因此生成 Option<'b mut T> 。这就是您的代码现在所做的。)

那么有什么作用呢？请记住，我们的目标是能够生产 Option<&'a mut T>来自 &'b mut IterMut<'a, T> .

如果我们能够生产 IterMut<'a, T>无条件地，我们可以(暂时)替换 self使用它，因此能够直接访问 IterMut<'a, T>关联到我们的列表。

// This actually type-checks!
fn next<'b>(&'b mut self) -> Option<&'a mut T> {
    let mut temp: IterMut<'a, T> = todo!(); // obviously this won't work
    std::mem::swap(&mut self.0, &mut temp.0);
    temp.0.as_mut().map(|node| {
        self.0 = &mut node.next;
        &mut node.elem
    })
}

(playground link)

进行设置以使这一切正常的最简单方法是转置 IterMut<'a, T>一点点。与其将可变引用置于选项之外，不如将其置于内部!现在您将始终能够生成 IterMut<'a, T>与 None !

struct IterMut<'a, T>(Option<&mut Box<Node<T>>>);

翻译 next ，我们得到

fn next<'b>(&'b mut self) -> Option<&'a mut T> {
    let mut temp: IterMut<'a, T> = IterMut(None);
    std::mem::swap(&mut self.0, &mut temp.0);
    temp.0.map(|node| {
        self.0 = node.next.as_mut();
        &mut node.elem
    })
}

更惯用的是，我们可以使用 Option::take而不是 std::mem::swap (这在前面的太多链接列表中提到过)。

fn next<'b>(&'b mut self) -> Option<&'a mut T> {
    self.0.take().map(|node| {
        self.0 = node.next.as_mut();
        &mut node.elem
    })
}

(playground link)

这实际上最终与 Too Many Linked Lists 中的实现略有不同。该实现删除了 &mut Box<Node<T>> 的双重间接寻址并简单地将其替换为 &mut Node<T> .但是，我不确定您获得了多少，因为该实现在 List::iter_mut 中仍然有双重解引用。和 Iterator::next .