`не может определить подходящее время жизни для autoref из-за противоречивых требований`, но не может ничего изменить из-за ограничений определения признаков

avatar
Mihir Luthra
17 мая 2020 в 04:58
657
2
4

Я внедрял связанные списки, используя слишком много связанных списков. При попытке реализовать 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`.

Я просмотрел Не могу определить подходящее время жизни для авторефа из-за противоречивых требований.

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

Я думал, что в основном мне нужно как-то заявить, что время жизни '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)
    }
}

☝️Это работает.

Источник
SCappella
17 мая 2020 в 06:41
0

Ответов пока нет, но этот вопрос почти идентичен этому.

Mihir Luthra
17 мая 2020 в 08:22
0

@SCappella, да, это почти та же проблема. Проблема не в компиляции кода. Меня в основном интересует понимание ошибки. @ Ответ Вивека устраняет некоторые сомнения, и комментарии к связанному вопросу также полезны, но все еще не могут полностью понять сообщение об ошибке и почему то же самое работает с iter()

Ответы (2)

avatar
SCappella
17 мая 2020 в 08:31
4

Ключевым моментом является то, что вам нужно как-то извлечь 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);
}

(ссылка на игровую площадку)

Дело в том, что если бы мы могли заимствовать что-то на короткое (общее) время жизни '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
    })
}

(ссылка на игровую площадку)

Самый простой способ настроить все так, чтобы все это работало, это немного транспонировать 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
    })
}

(ссылка на игровую площадку)


На самом деле это немного отличается от реализации в Слишком много связанных списков. Эта реализация удаляет двойную косвенность &mut Box<Node<T>> и заменяет ее простым &mut Node<T>. Однако я не уверен, сколько вы выиграете, так как эта реализация все еще имеет двойное отключение в List::iter_mut и Iterator::next.

.
Mihir Luthra
17 мая 2020 в 09:15
0

Это потребовало много времени, чтобы понять. Супер полезно. Спасибо, вы вылечили мою двухдневную головную боль.

Mihir Luthra
17 мая 2020 в 10:23
0

Что ж, теперь я понимаю, что идея указать 'b : 'a ('b переживет a) была неплохой, если черта приняла ее. если мы изменим fn bad<'a, 'b, T>(_x: &'b mut &'a mut T) -> &'a mut T на fn bad<'a, 'b : 'a, T>(_x: &'b mut &'a mut T) -> &'a mut T, то компилятор это примет. Пример, который вы привели, действительно полезен, и я бы посоветовал всем, кто столкнется с этой проблемой, поиграть с ней (изменить ссылки mut на ссылки immut и т. д.).

avatar
apatniv
17 мая 2020 в 06:11
1

Rust пытается сказать, что у вас есть оборванная ссылка.

self.0.as_mut() // value borrowed
self.0 = <> // underlying value changed here. 

Проблема заключается в следующем определении:

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

Это не может означать, что у вас будет "пустой" узел, что означает достижение конца узла.

Используйте структуру, указанную в книге, например:

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

Это гарантирует, что вы можете оставить None на своем месте, когда запускаете конец списка и используете take для изменения содержимого IterMut за кулисами.

Mihir Luthra
17 мая 2020 в 08:13
0

Это имеет смысл для меня. Но как же тогда работает iter()? Это почти похоже. Там я заимствую значение как as_ref(), а затем присваиваю self.0 внутри замыкания, которое работает без ошибок. Не могли бы вы помочь мне понять это?