Вариантность и PhantomData

Будет неправильно откладывать эту часть на потом, так что мы прямо сейчас займёмся Хардкорным Представлением.

Есть пять ужасных всадников создания небезопасных коллекций в Rust:

  1. Вариантность
  2. Дроп-чек
  3. Оптимизации NonNull
  4. Правило выделения isize::MAX
  5. Типы нулевой длины

Слава небесам, последние два не являются для нас проблемой.

Третий всадник мог бы стать проблемой, но овчинка не стоит выделки — если вы выбрали связный список, вы уже стократно проиграли битву за эффективное использование памяти.

Второго всадника я когда-то считала очень важным, поскольку стандартная библиотека применяет для дроп-чека разные трюки, но настройки по умолчанию безопасны, а способы их «подкрутить» — нестабильны. Вам надо очень постараться, чтобы заметить ограничения этих настроек, так что просто забудьте об этом.

Остаётся Вариантность. Честно говоря, на ней, наверное, тоже можно было не настаивать, но я всё ещё горжусь своей работой в качестве человека, разработавшего std::collections, так что мы всё-таки займёмся Этой Штукой.

Так вот, сюрприз: в Rust есть подтипы. В частности, &'big T — это подтип &'small T. (Прим. перевод.: время жизни big больше, чем время жизни small). Почему? Ну, потому что если какому-то коду нужна ссылка, живущая в течение определённого времени, вполне допустимо дать ему ссылку, которая живёт дольше. Интуитивно это же понятно, так?

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

fn take_two<T>(_val1: T, _val2: T) { }

Это поистине скучный код, поэтому мы ожидаем, что он будет работать при T=&u32, так?

#![allow(unused)]
fn main() {
fn two_refs<'big: 'small, 'small>(
    big: &'big u32, 
    small: &'small u32,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }
}

Да, без проблем компилируется!

А теперь давайте немного повеселимся и завернём его, ну, я не знаю, в std::cell::Cell:

#![allow(unused)]
fn main() {
use std::cell::Cell;

fn two_refs<'big: 'small, 'small>(
    // ОБРАТИТЕ ВНИМАНИЕ: эти две строки изменились
    big: Cell<&'big u32>, 
    small: Cell<&'small u32>,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }
}
error[E0623]: lifetime mismatch
 --> src/main.rs:7:19
  |
4 |     big: Cell<&'big u32>, 
  |               ---------
5 |     small: Cell<&'small u32>,
  |                 ----------- these two types are declared with different lifetimes...
6 | ) {
7 |     take_two(big, small);
  |                   ^^^^^ ...but data from `small` flows into `big` here

Что??? Мы не трогали время жизни, почему компилятор стал ругаться?

Хорошо, штука со временем жизни «подтипов» должна быть очень простой, поэтому она даёт сбой, если завернуть ссылки во что-то ещё. Смотрите, она ломается и с Vec:

#![allow(unused)]
fn main() {
fn two_refs<'big: 'small, 'small>(
    big: Vec<&'big u32>, 
    small: Vec<&'small u32>,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }
}
    Finished dev [unoptimized + debuginfo] target(s) in 1.07s
     Running `target/debug/playground`

Видите, этот код тоже не компилиру... — подождите, что??? Vec что, магический???

Ну, да. Но, и в то же время — нет. Эта магия всегда была с нами и имя ей — ✨Вариантность✨.

Прочитайте главу про подтипы в Растономиконе, если вам нужны кровавые подробности, но, вкратце: подтипы не всегда безопасны. В частности, небезопасно когда смешиваются изменяемые ссылки, потому что вы можете вызывать что-то вроде mem::swap и получить висячие указатели!

Штуки, которые выглядят как «изменяемые ссылки» являются инвариантными. Это значит, что они не разрешают использовать подтипы вместо типов. Так что, в целях безопасности, &mut T — инвариантен относительно T, и Cell<T> — инвариантен относительно T, потому что &Cell<T> по сути является обычным &mut T (из-за внутренней изменчивости).

Почти всё, что не является инвариантным, ковариантно. Это значит, что подтипы можно использовать везде, где можно использовать типы, и всё будет работать. (Есть также контравариантные типы, где типы можно использовать вместо подтипов, но они встречаются редко и никому не нравятся, так что я не буду про них говорить).

Обычно коллекции содержат изменяемый указатель на свои данные, так что они должны быть инвариантными, но на самом деле, это не так! Из-за системы владения Rust, Vec<T> семантически эквивалентен T и это значит, что его можно сделать ковариантным и это будет безопасно!

К сожалению, такое определение инвариантно:

#![allow(unused)]
fn main() {
pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
}

type Link<T> = *mut Node<T>;

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}
}

Но как на самом деле Rust принимает решение о вариантности типов? В старые добрые времена (до версии 1.0) мы разрешали людям просто указывать нужную им вариантность... и это был полный провал! Подтипы и вариантность — действительно сложные понятия. Разработчики ядра вполне искренне не могли договориться даже о базовой терминологии! В конце концов мы остановились на «вариантности на примере»: компилятор смотрит на ваши поля и копирует их вариантность. Если возникают противоречия, побеждает инвариантность, потому что это безопасно.

Так что же такого есть в наших определениях, что так не нравится Rust? *mut!

Сырые указатели в Rust и в самом деле позволяют вам делать всё, что угодно, но и они имеют одну безопасную черту: из-за того, что большинство людей не имеют представления о вариантности и подтипах, и из-за того, что некорректная ковариантность может привести к ужасным последствиям, *mut T инвариантен, поскольку обычно его используют «как» &mut T.

Это крайне раздражает меня, человека, потратившего много времени на реализую коллекций в Rust. Именно поэтому, когда я писала std::ptr::NonNull, я добавила этот кусочек магии:

В отличие от *mut T, NonNull<T> ковариантен относительно T. Благодаря этому можно использовать NonNull<T> для построения ковариантных типов. Это может привести к ошибкам, если тип не должен быть ковариантным.

Однако интерфейс NonNull<T> построен на базе *mut T, почему всё работает? Опять магия? Давайте посмотрим:

#![allow(unused)]
fn main() {
pub struct NonNull<T> {
    pointer: *const T,
}

impl<T> NonNull<T> {
    pub unsafe fn new_unchecked(ptr: *mut T) -> Self {
        // БЕЗОПАСНОСТЬ: вызывающая сторона должна гарантировать, что `ptr` не равен null.
        unsafe { NonNull { pointer: ptr as *const T } }
    }
}
}

НЕТ. НИКАКОЙ МАГИИ! NonNull полагается на то, что *const T ковариантен и хранит его вместо *mut T, преобразовывая значения туда и обратно, чтобы создать впечатление, будто он хранит *mut T. Весь трюк в этом! Вот почему коллекции в Rust ковариантны. Было бы довольно грустно всё время писать так. Поэтому я заставила Правильный Тип Указателя делать всю грязную работу! Пожалуйста! Наслаждайтесь своими подтипами!

Решение в том, чтобы использовать NonNull<T>, а если вам потребуются нулевые указатели, использовать Option<NonNull<T>>. Мы действительно станем так делать?

Ага! Мы пишем связные списки продуктового уровня, поэтому будем героически разбираться в деталях и писать сложный код. (Можно было бы просто использовать *const T и приводить типы, но я искренне хочу узнать, насколько это больно... в Интересах Науки).

Так что принимайте окончательное определение нашего типа:

#![allow(unused)]
fn main() {
use std::ptr::NonNull;

// !!!Изменилось!!!
pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
}

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

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}
}

...хотя, подождите, ещё одна деталь. Всякий раз, используя сырые указатели, добавляйте поле PhantomData для их защиты:

use std::marker::PhantomData;

pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
    /// Логически мы владеем объектами типа T и храним их по значению.
    _boo: PhantomData<T>,
}

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

PhantomData — это способ предоставить компилятору «пример» поля, которое концептуально присутствует в вашем типе, но физически — нет. (Прим. перевод.: физически LinkedList содержит два сырых указателя на значения типа T. Компилятор не знает, владеет ли LinkedList этими значениями и будет ли их освобождать при вызове drop. С помощью PhantomData мы даём подсказку: LinkedList владеет значениями типа T — не &T и не &mut T.) В данном случае мы используем NonNull, поэтому можем утверждать, что наш тип ведёт себя так, как будто хранит значения T, и мы добавляем PhantomData, чтобы явно это выразить.

Раньше в стандартной библиотеке PhantomData часто использовался из-за сложных и опасных трюков с деструкторами, но эти правила менялись столько раз, что я уже не уверена в необходимости фантомного поля. Впрочем, успела выработать привычку, так что буду следовать карго-культу и ставить PhantomData, даже если он не обязателен!

(Кстати, узел действительно хранит значение типа T, так что маркер для LinkedList не обязателен!)

...ладно, с представлением мы закончили! Переходим к основным функциям!