Метод drop

Мы можем создать стек, вставить в него элемент, извлечь его обратно. Мы даже протестировали, что всё это правильно работает!

Надо ли нам беспокоиться об освобождении памяти? Технически — нет, вообще не надо! Как и C++, Rust использует деструкторы, чтобы автоматически освобождать ресурсы, после их использования. Тип имеет деструктор, если он реализует типаж, который называется Drop. Типажи — это научное название интерфейсов в языке Rust. Типаж Drop имеет следующий вид:

pub trait Drop {
    fn drop(&mut self);
}

Что-то вроде: «когда вы выйдете из области видимости, я дам вам секунду, чтобы прибрать за собой».

Вы не должны реализовывать Drop, если у вас есть типы, реализующие Drop и всё, что вы хотите — это вызвать их деструкторы. В случае List, всё что ему нужно — это освободить голову, что, по идее приведёт к освобождению Box<Node>. Всё это будет сделано автоматически... с одним «но».

Автоматическая уборка может пойти не по плану.

Посмотрим на простой список:

list -> A -> B -> C

Когда удаляется list, он попытается удалить A, который попытается удалить B, который попытается удалить C. Возможно, кое-кто из вас занервничал. Это рекурсивный код, а рекурсивный код может привести к переполнению стека!

Некоторые из вас, возможно, подумали: «здесь точно хвостовая рекурсия, а любой приличный язык программирования гарантирует, что при хвостовой рекурсии переполнения не будет». На самом деле это неверно! Чтобы понять, почему, давайте вручную реализуем Drop так, как это сделал бы компилятор:

impl Drop for List {
    fn drop(&mut self) {
        // ПРИМЕЧАНИЕ: в реальном коде нельзя вызвать `drop` явно;
        // так что мы притворимся компилятором!
        self.head.drop(); // хвостовая рекурсия - хорошо!
    }
}

impl Drop for Link {
    fn drop(&mut self) {
        match *self {
            Link::Empty => {} // Готово!
            Link::More(ref mut boxed_node) => {
                boxed_node.drop(); // хвостовая рекурсия - хорошо!
            }
        }
    }
}

impl Drop for Box<Node> {
    fn drop(&mut self) {
        self.ptr.drop(); // ой, подождите, не хвостовая рекурсия!
        deallocate(self.ptr);
    }
}

impl Drop for Node {
    fn drop(&mut self) {
        self.next.drop();
    }
}

Мы не можем освободить содержимое Box после вызова deallocate, так что здесь у нас хвостовая рекурсия отменяется! Вместо этого, напишем итеративное освобождение List, которое выведет узлы из их боксов.

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);
        // `while let` == "повторяй, пока образец совпадает"
        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
            // здесь boxed_node выходит из области видимости и уничтожается;
            // но поле `next` заменяется на `Link::Empty`,
            // поэтому бесконечная рекурсия не возникает
        }
    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 1 test
test first::test::basics ... ok

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

Великолепно!

Бонусный раздел для преждевременной оптимизации!

Наша реализация освобождения очень напоминает код while let Some(_) = self.pop() { }, который, безусловно, проще. Чем они отличаются, и какие проблемы с производительностью могут возникнуть, если мы обобщим наш список для хранения объектов любого типа, а не только целых чисел?