IterMut

Я хочу быть честной: IterMut это БЕЗУМИЕ. Что само по себе звучит безумно: он ведь должен быть похож на Iter!

Семантически да, но природа разделяемых и изменяемых ссылок такова, что Iter можно считать «тривиальным», в то время как IterMut — это Настоящее Колдовство.

Возьмём ключевую идею из нашей реализации Iterator для Iter:

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

    fn next(&mut self) -> Option<Self::Item> { /* что-то */ }
}

Которую можно преобразовать в:

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

    fn next<'b>(&'b mut self) -> Option<&'a T> { /* что-то */ }
}

Сигнатура next не устанавливает ограничений между временем жизни входной и выходной переменных! Почему для нас это важно? Потому, что мы можем вызывать next снова и снова без всяких условий!

let mut list = List::new();
list.push(1); list.push(2); list.push(3);

let mut iter = list.iter();
let x = iter.next().unwrap();
let y = iter.next().unwrap();
let z = iter.next().unwrap();

Круто!

Это совершенно нормально для разделяемых ссылок, потому что их смысл в том, что их одновременно может быть очень много. А вот изменяемые ссылки сосуществовать не могут. Их смысл в том, что они эксклюзивные.

В результате, написать безопасный код для IterMut гораздо сложнее (и мы, кстати, пока не выяснили, что это значит...). Удивительно, но IterMut можно совершенно безопасно реализовать для многих структур данных!

Начнём с того, что просто возьмём код Iter и перепишем всё так, чтобы ссылки стали изменяемыми:

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
    pub fn iter_mut(&self) -> IterMut<'_, T> {
        IterMut { next: self.head.as_deref_mut() }
    }
}

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

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_deref_mut();
            &mut node.elem
        })
    }
}
> cargo build
error[E0596]: cannot borrow `self.head` as mutable, as it is behind a `&` reference
  --> src/second.rs:95:25
   |
94 |     pub fn iter_mut(&self) -> IterMut<'_, T> {
   |                     ----- help: consider changing this to be a mutable reference: `&mut self`
95 |         IterMut { next: self.head.as_deref_mut() }
   |                         ^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be borrowed as mutable

error[E0507]: cannot move out of borrowed content
   --> src/second.rs:103:9
    |
103 |         self.next.map(|node| {
    |         ^^^^^^^^^ cannot move out of borrowed content

Хорошо, выглядит так, словно у нас тут две разные ошибки. Первая очень понятная и в сообщении даже написано, как её исправить! Нельзя преобразовать разделяемую ссылку в изменяемую, так что iter_mut должен принимать &mut self. Обычная глупая ошибка копи-пасты.

pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut { next: self.head.as_deref_mut() }
}

А что насчёт второй?

Ой! На самом дела я случайно ошиблась при написании iter в прошлом разделе, и нам просто повезло, что всё заработало!

Мы только что столкнулись с типажом Copy. Когда мы вводили понятие владения, то сказали, что передав владение, вы больше не можете использовать переменную. Для многих типов это правда. Наш добрый друг Box управляет размещением памяти в куче и мы конечно же не хотим, чтобы два куска кода думали, что они должны освободить эту память.

В то же время для других типов всё это мусор. Целые числа не обладают семантикой владения, они всего лишь бессмысленные числа! Именно по этой причине, целые числа реализуют типаж Copy. Известно, что типы, помеченные как Copy, идеально копируется побитовым копированием. Поэтому они обладают сверхспособностью: при перемещении старое значение всё ещё можно использовать. Как следствие, вы можете даже забрать копируемый тип из ссылки без замены!

Копируемыми являются все численные примитивы Rust (i32, u64, bool, f32, char и т. д.). Вы также можете объявить свой тип копируемым, если все его компоненты — также копируемые.

Ключевым моментом, объясняющим, почему этот код работал, является то, что разделяемые ссылки также копируемые! А, поскольку & можно копировать, Option<&> также можно копировать. Так что когда мы вызывали self.next.map, это работало потому что что Option просто копировался. Но теперь мы не можем так сделать, потому что &mut не копируется (если вы скопируете &mut, у вас будет две изменяемые ссылки на одно и то же место в памяти, что запрещено). Вместо копирования, мы должны забрать владение, вызвав метод take.

fn next(&mut self) -> Option<Self::Item> {
    self.next.take().map(|node| {
        self.next = node.next.as_deref_mut();
        &mut node.elem
    })
}
cargo build

Так... подождите. Охренеть! IterMut просто работает!

Давайте протестируем:

#[test]
fn iter_mut() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);

    let mut iter = list.iter_mut();
    assert_eq!(iter.next(), Some(&mut 3));
    assert_eq!(iter.next(), Some(&mut 2));
    assert_eq!(iter.next(), Some(&mut 1));
}
> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 6 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::peek ... ok

test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured

Да. Он работает.

Охренеть.

Хотя.

Конечно, IterMut должен работать, но обычно этому мешает какая-нибудь глупость! Проясню:

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

Как по мне, это большое достижение. Есть пара причин, поэтому всё работает.

  • Мы вызываем take у Option<&mut>, так что получаем эксклюзивный доступ к изменяемой ссылке. Не надо беспокоиться, что кто-то ещё сможет получить к ней доступ.
  • Rust понимает, что это нормально — разбить изменяемую ссылку на отдельные поля указываемой структуры, потому что нет способа «собрать её обратно» и поля определённо не пересекаются.

Та же самая базовая логика применима при реализации безопасного IterMut для массива или дерева! Можно даже сделать итератор DoubleEnded, чтобы перебирать элементы одновременно от начала к концу, и от конца к началу! Вот как!