Subtyping и variance в Rust: о чём обычно молчат / Хабр

Привет, Хабр!

Есть вещи в Rust, которые работают незаметно, пока не ломаются, да ломаются они странно... Компилятор указывает на место, где вы ничего плохого не делали, и говорит про «lifetime mismatch» или «mismatched types» без внятного объяснения почему. Или наоборот: вы ожидаете ошибку, потому что передаёте ссылку с явно другим временем жизни, а компилятор молчит и пропускает.

Оба случая объясняются одним механизмом: variance.

Большинство останавливаются на трёх определениях и паре примеров. Пойдём глубже — до алгебры композиции, до того, как компилятор выводит variance через итерацию фиксированной точки, до #[may_dangle] и до того, почему NonNull<T> ковариантен, а *mut T нет.

Подтипирование без наследования

В языках с наследованием подтипирование работает очевидно:Cat extends Animal, и там, где ожидается Animal, можно передать Cat. В Rust нет наследования, зато есть подтипирование по временам жизни, оно работает по той же логике, просто объект другой.

Если 'long: 'short — то есть 'long живёт не короче 'short — то 'long является подтипом 'short. Это конечно все контринтуитивно, но логика такая: подтип более специфичная версия. &'static str удовлетворяет любым требованиям к времени жизни, она «умеет больше», чем &'a str с произвольным 'a. Поэтому 'static это подтип любого 'a.

Компилятор использует это постоянно, когда вы передаёте &'static str туда, где ожидается &'a str, он просто укорачивает время жизни до нужного. Никакого копирования, просто трактует ту же ссылку как менее гарантированную. Это вот и есть подтипирование.

Алгебра variance: как она композируется

Variance — это не тупо какое-то свойство типа, это свойство конкретной позиции параметра внутри типа. И когда типы вкладываются друг в друга, variance композируется по конкретным правилам.

Если у вас есть F<G<T>>, итоговая variance по T определяется умножением variance позиций:

F по G	G по T	Итог F по T
ковариантен	ковариантен	ковариантен
ковариантен	контрвариантен	контрвариантен
ковариантен	инвариантен	инвариантен
контрвариантен	ковариантен	контрвариантен
контрвариантен	контрвариантен	ковариантен
контрвариантен	инвариантен	инвариантен
инвариантен	что угодно	инвариантен

Минус на минус даёт плюс. Контрвариантность внутри контрвариантности — это ковариантность.

Посмотрим на пример:

// fn(T) — контрвариантен по T
// fn(fn(T)) — контрвариантен по fn(T), а fn(T) контрвариантен по T
// итог: контрвариантен * контрвариантен = ковариантен по T

type F<T> = fn(fn(T));
// F<T> ковариантен по T — двойное переворачивание возвращает исходное направление

На практике это проявляется в коде, который обрабатывает обратные вызовы:

struct Dispatcher<T> {
    // Хранит функцию, которая принимает функции, принимающие T
    handler: fn(fn(T) -> bool) -> bool,
    // fn(T) контрвариантен по T
    // fn(fn(T) -> bool) контрвариантен по fn(T)
    // итог: ковариантность по T (контрвариантен * контрвариантен)
}

Если хотя бы в одной позиции инвариантность — вся цепочка инвариантна. Инвариантность поглощает всё, как умножение на нолик.

Как компилятор выводит variance: итерация фиксированной точки

Компилятор не смотрит на каждый тип по одному разу, он запускает итерационный алгоритм.

Сначала каждому параметру присваивается пессимистичное начальное значение: «бивариантен», то есть неизвестно, никаких ограничений. Потом компилятор обходит определения типов, применяет правила позиций и обновляет варианс. И так по кругу, пока значения не перестанут меняться, это и есть фиксированная точка.

Рекурсивные типы требуют нескольких итераций именно поэтому:

// Связный список
enum List<T> {
    Nil,
    Cons(T, Box<List<T>>),
}

Итерация 1: T встречается как поле T (ковариантная позиция) и внутри Box<List<T>>. Box<X> ковариантен по X, List<T> пока бивариантен по T (начальное значение). Результат пока неопределён.

Итерация 2: List<T> теперь предварительно ковариантен. Box<List<T>> ковариантен по List<T>, List<T> ковариантен по T, значит ковариантен. Оба поля ковариантны — List<T> ковариантен.

Итерация 3: ничего не изменилось. Фиксированная точка достигнута.

Если бы где-то в цепочке появился &mut T или Cell<T> — инвариантность распространилась бы через все итерации и «заразила» весь тип.

Почему &mut T обязан быть инвариантным

Предположим, что &mut T ковариантен по T. Тогда из &mut &'long str можно получить &mut &'short str (потому что &'long str это подтип &'short str, а ковариантность сохраняет направление).

Теперь вот эта функция:

fn shorten<'long, 'short>(r: &mut &'long str, s: &'short str)
where
    'short: 'long, // 'short живёт не дольше 'long — это НАОБОРОТ от обычного
{
    // Если &mut T ковариантен по T:
    // &mut &'long str -> &mut &'short str (потому что 'long: 'short, значит 'long — подтип 'short)
    // После сужения типа r до &mut &'short str:
    *r = s; // записываем &'short str туда, где ожидается &'long str
}

Что происходит при вызове:

fn main() {
    let mut s: &'static str = "hello"; // 'static — самое длинное время жизни
    
    {
        let local = String::from("world");
        let local_ref: &str = &local; // время жизни равно блоку
        
        // Если бы компилятор разрешил — мы бы записали &local в s,
        // который объявлен как &'static str
        // shorten(&mut s, local_ref);
    }
    // local освобождён, но s теперь указывает туда
    
    println!("{}", s); // use-after-free
}

s объявлена как &'static str. Любой код после блока вправе использовать s, считая что она живёт вечно. Это разумное ожидание, вы объявили 'static. Если бы мы могли записать туда &local, это ожидание нарушалось бы без каких-либо предупреждений.

const T против mut T: не только про мутабельность

Многие удивляются: const T ковариантен, а mut T инвариантен, хотя оба raw-pointer и оба без borrow checker. В чём разница?

Дело не в том, что компилятор физически запрещает запись через *const T — через unsafe вы можете делать всё что угодно с обоими. Дело в таком вот семантическом обещании.

const T — это указатель «только для чтения» по соглашению. Если вы объявляете поле как const T, вы заявляете: «я не буду изменять данные через этот указатель». Компилятор доверяет этому заявлению и делает тип ковариантным.

*mut T — это указатель «для чтения и записи». Компилятор не может знать, что вы через него делаете (это же unsafe-код), поэтому применяет консервативное правило: если возможна запись — инвариантность.

Отсюда следствие: если у вас структура с mut T и вы хотите ковариантности (потому что семантически ведёте себя как «только читаем»), нужно либо использовать const T, либо добавить PhantomData<T> и взять на себя ответственность за это обещание.

// Вариант 1: честный *const T — ковариантность автоматически
struct ReadOnly<T> {
    ptr: *const T,
    // ковариантен по T — компилятор видит *const T
}

// Вариант 2: *mut T + PhantomData<T> — явное обещание
struct ActuallyReadOnly<T> {
    ptr: *mut T, // технически mut, но мы обещаем не писать через внешний интерфейс
    _reads: PhantomData<T>, // ковариантен — *mut T инвариантен, но PhantomData<T> ковариантен
    // итог: есть инвариантная позиция (*mut T) — всё инвариантно!
    // ЭТО НЕ РАБОТАЕТ — *mut T перевешивает
}

Второй вариант работать не будет. Если в структуре есть и *mut T (инвариантная позиция) и PhantomData<T> (ковариантная позиция), то инвариантность перевешивает.

Правильно сделать так:

struct ActuallyReadOnly<T> {
    ptr: NonNull<T>, // NonNull<T> ковариантен по T
    _phantom: PhantomData<T>, // тоже ковариантен — усиливает сигнал
}

NonNull

NonNull<T> из std::ptr часто воспринимают как «*mut T, который не может быть нулевым», и используют именно за это свойство. Но у него есть второе отличие: NonNull<T> ковариантен по T, тогда как *mut T инвариантен.

NonNull разработан для использования в структурах данных, которые владеют данными.

Vec<T>, Box<T>, Rc<T> — все они используют NonNull<T> внутри. Владеющий контейнер должен быть ковариантным (иначе Vec<&'static str> нельзя было бы использовать там, где нужен Vec<&str>). Если бы NonNull<T> был инвариантным, все эти типы требовали бы явного PhantomData<T> для ковариантности, что и так есть в их исходниках, но именно для drop check, а не для variance.

use std::ptr::NonNull;

struct MyBox<T> {
    ptr: NonNull<T>,
    _owns: PhantomData<T>, // нужен для drop check, не для variance
    // без PhantomData<T>: ковариантен по T (через NonNull), но без drop check
    // с PhantomData<T>: ковариантен + drop check
}

Для сравнения посмотрим что происходит с *mut T:

struct BrokenBox<T> {
    ptr: *mut T, // инвариантен по T
    // даже если добавить PhantomData<T>:
    _phantom: PhantomData<T>, // ковариантен по T
    // итог: инвариантен (инвариантная позиция побеждает)
}
// BrokenBox<T> инвариантен по T — нехорошо для владеющего контейнера

Поэтому для низкоуровневых структур данных, которые владеют данными, используйте NonNull<T> вместо *mut T. Это даёт правильную ковариантность автоматически, плюс гарантию ненулевого указателя, плюс оптимизацию Option<NonNull<T>>, всё по цене одного типа.

Drop check

Про PhantomData<T> и drop check обычно говорят коротко: «добавь — и компилятор будет знать, что ты дропаешь T». Но за этим стоит более тонкая механика.

Базовое правило drop check: если тип реализует Drop, компилятор требует, чтобы все типы-параметры строго пережили сам тип. «Строго пережили» означает не «жили одновременно», а «жили дольше». Компилятор не анализирует тело деструктора, он просто предполагает, что деструктор может обратиться к любому T.

Вот где это становится проблемой:

struct Inspector<'a> {
    name: &'a str,
}

impl<'a> Drop for Inspector<'a> {
    fn drop(&mut self) {
        println!("Инспектор {} завершил работу", self.name);
    }
}

fn main() {
    let name = String::from("Иванов");
    let inspector = Inspector { name: &name };
    // Всё хорошо — name живёт дольше inspector
    
    drop(name); // Явно дропаем name раньше inspector
    // drop(inspector) вызовется тут и попытается обратиться к name — use-after-free
    // Компилятор это запрещает
}

Это разумно, но представьте, что деструктор не обращается к self.name, только логирует факт уничтожения без обращения к данным. Компилятор всё равно запретит. Он не смотрит внутрь деструктора.

Здесь уже появляется наш герой #[may_dangle].

#[may_dangle]

#[may_dangle] — нестабильный атрибут (#![feature(dropck_eyepatch)]), но он используется в самой стандартной библиотеке. Vec<T> реализует Drop с этим атрибутом.

Атрибут говорит компилятору: «в этом impl Drop я обещаю, что не буду разыменовывать T в деструкторе,только освобожу память». T больше не обязан строго пережить контейнер.

Зачем это Vec<T>? Без #[may_dangle] вот этот код не компилировался бы:

let v: Vec<&str>;
{
    let s = String::from("hello");
    v = vec![s.as_str()]; // ссылка на s внутри Vec
} // s дропается здесь
// v дропается здесь — без may_dangle компилятор требовал бы,
// чтобы &str пережил Vec строго

Без #[may_dangle] компилятор говорит: «Vec<T> реализует Drop и может обращаться к T в деструкторе, значит T должен пережить Vec». С #[may_dangle] — «Vec обещает не разыменовывать T в деструкторе, значит T может дропнуться одновременно с Vec».

unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> {
    fn drop(&mut self) {
        unsafe {
            // ptr::drop_in_place дропает элементы (это обращение к T)
            // но компилятор разрешает — мы сами отвечаем за безопасность
            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(
                self.as_mut_ptr(),
                self.len,
            ))
        }
        // память освобождается через allocator
    }
}

Хотя тут есть обращение к T через drop_in_place, это безопасно, элементы Vec существуют внутри самого Vec, и если Vec ещё жив, элементы тоже живы.

PhantomData<T> при этом всё равно нужен, для drop check он говорит «мы владеем T и должны дропнуть T», что вместе с #[may_dangle] создаёт правильную картинку: «мы дропаем T, но не через висячие ссылки, а через собственные данные».

Variance в трейт-объектах: dyn Trait + 'a

Трейт-объекты имеют свои правила variance, и они работают не так, как можно ожидать.

dyn Trait + 'a ковариантен по 'a — это время жизни самого трейт-объекта, и его можно укоротить. Если у вас dyn Trait + 'static, вы можете использовать его там, где нужен dyn Trait + 'a. Это логично.

Но dyn Trait<T> инвариантен по T. Почему? Потому что трейт-объект — это указатель на таблицу виртуальных методов, и эти методы могут как принимать T, так и возвращать T. Компилятор не знает, какие именно методы используются, поэтому применяет консервативное правило.

trait Processor<T> {
    fn process(&self, item: T);
    fn produce(&self) -> T;
}

// dyn Processor<T> — инвариантен по T
// Потому что process принимает T (контрвариантная позиция)
// а produce возвращает T (ковариантная позиция)
// контрвариантен + ковариантен = инвариантен

Если вы пытаетесь сохранить Box<dyn Trait<Cat>> туда, где ожидается Box<dyn Trait<Animal>> — не получится. Трейт-объект инвариантен.

Отдельный интересный случай — dyn Fn и его вариации:

// dyn Fn(T) — контрвариантен по T (как fn(T))
// dyn Fn() -> T — ковариантен по T
// dyn Fn(T) -> T — инвариантен по T

Замыкания, хранящие &mut T, делают тип инвариантным по T, потому что &mut T появляется как поле замыкания.

Variance замыканий: неочевидное следствие захвата

Замыкания в Rust — это анонимные структуры, и их variance определяется так же, как для обычных структур: через типы захваченных переменных.

Если замыкание захватывает &T — оно ковариантно по T. Если захватывает &mut T — инвариантно по T. Если захватывает T по значению — ковариантно (как Box<T>).

fn make_closure<T>(val: T) -> impl Fn() -> &'static T 
where T: 'static 
{
    // Замыкание захватывает T по значению — ковариантно по T
    // Если T = &'static str, замыкание ковариантно по времени жизни строки
    move || Box::leak(Box::new(val)) // упрощённо
}

Менее же очевидный случай — замыкания, возвращающие ссылки на захваченные данные:

fn captures_ref<'a, T>(val: &'a T) -> impl Fn() -> &'a T + 'a {
    // Замыкание захватывает &'a T — ковариантно по 'a и T
    // Тип замыкания привязан к 'a
    move || val
}

Здесь тип замыкания ковариантен по 'a, что значит: замыкание с 'long можно использовать там, где нужно замыкание с 'short.

Variance и where-clauses: как ограничения влияют на вывод

Интересный момент: where-clauses не влияют на variance. Variance определяется только структурой типа, тем, где и как используются параметры.

struct OnlyEq<T: Eq> {
    val: T,
}
// OnlyEq<T> ковариантен по T — ограничение T: Eq не меняет variance
// Поле val: T — ковариантная позиция

Это значит, что ограничение T: Copy или T: 'static никак не влияет на то, ковариантен ли тип по T. Ограничение — это требование к конкретному T, а variance — это отношение между разными T.

PhantomData: полная карта вариантов

Дадим полную картину PhantomData:

use std::marker::PhantomData;
use std::cell::Cell;

// Ковариантен по T, T в drop check (владение)
struct Owns<T>        { _p: PhantomData<T> }

// Ковариантен по T, без drop check (только ссылается)  
struct Refs<T>        { _p: PhantomData<*const T> }

// Инвариантен по T, T в drop check
struct OwnsMut<T>     { _p: PhantomData<Cell<T>> }

// Инвариантен по T, без drop check
struct InvariantRef<T>{ _p: PhantomData<*mut T> }

// Контрвариантен по T, без drop check (потребляет T)
struct Sink<T>        { _p: PhantomData<fn(T)> }

// Ковариантен по T в возвращаемом, контрвариантен по T в аргументах
struct BiDi<T>        { _p: PhantomData<fn(T) -> T> }
// fn(T) -> T — инвариантен по T
// контрвариантен (аргумент) + ковариантен (возврат) = инвариантен

Арена: пример со всеми механизмами

Соберём всё вместе на примере. Арена — аллокатор, выдающий ссылки на объекты с временем жизни самой арены:

use std::marker::PhantomData;
use std::cell::Cell;

pub struct Arena<'arena> {
    data: bumpalo::Bump,
    // Почему Cell<&'arena ()>, а не просто &'arena ()?
    //
    // &'arena () — ковариантная позиция по 'arena
    // Arena<'long> стала бы подтипом Arena<'short>
    // Можно было бы передать арену с длинным временем жизни
    // туда, где ожидается короткая — и создать объект,
    // который думает что проживёт долго, а не доживёт
    //
    // Cell<T> инвариантен по T, значит Cell<&'arena ()>
    // инвариантен по 'arena — Arena<'long> != Arena<'short>
    _lifetime: PhantomData<Cell<&'arena ()>>,
}

impl<'arena> Arena<'arena> {
    pub fn alloc<T>(&'arena self, val: T) -> &'arena T {
        self.data.alloc(val)
        // Возвращаемая ссылка ковариантна по 'arena:
        // &'arena T ковариантен по 'arena
        // Если 'arena длинный — ссылку можно укоротить
    }
}

Объект Arena<'arena> инвариантен по 'arena,нельзя взять арену с длинным временем жизни и передать как арену с коротким. Зато ссылки, которые арена выдаёт, ковариантны по 'arena, их можно укоротить при необходимости. Оба свойства нужны одновременно, и они достигаются разными механизмами в одном типе.

Как применять это знание

Когда компилятор говорит «lifetime may not live long enough» в месте, где вы ничего плохого не делали — первый вопрос: какой тип здесь инвариантен, хотя не должен быть?

Алгоритм:

Найти тип, с которым работаете. Посмотреть на его поля — есть ли там *mut T, Cell<T>, UnsafeCell<T>? Если да — там инвариантность, и укоротить или удлинить время жизни не получится.
Если пишете собственный тип с raw-pointer и получаете неожиданную ошибку — посмотреть, что именно нужно: ковариантность (нужен NonNull<T> или PhantomData<T>), контрвариантность (нужен PhantomData<fn(T)>), инвариантность (и так будет, если есть *mut T).
Если ошибка в трейт-объекте — помнить, что dyn Trait<T> инвариантен по T. Попытка подставить dyn Trait<Cat> вместо dyn Trait<Animal> не пройдёт.
Если ошибка в замыкании — посмотреть, что оно захватывает. &mut T внутри замыкания делает его инвариантным по T.

Вот вам еще табличка:

Тип	Variance по T	Drop check	Когда использовать
`&'a T`	ковариантен	—	только читаем
`&'a mut T`	инвариантен	—	читаем и пишем
`*const T`	ковариантен	нет	raw-указатель только для чтения
`*mut T`	инвариантен	нет	raw-указатель для чтения и записи
`NonNull<T>`	ковариантен	нет	ненулевой raw-указатель владельца
`Box<T>`	ковариантен	да	владение с автодропом
`Vec<T>`	ковариантен	да (с `#[may_dangle]`)	коллекция с владением
`Cell<T>`	инвариантен	—	внутренняя мутабельность
`UnsafeCell<T>`	инвариантен	—	основа внутренней мутабельности
`fn(T)`	контрвариантен	—	функциональный тип
`fn() -> T`	ковариантен	—	функциональный тип
`PhantomData<T>`	ковариантен	да	«владею T, не пишу через внешний интерфейс»
`PhantomData<*const T>`	ковариантен	нет	«ссылаюсь на T, не владею»
`PhantomData<*mut T>`	инвариантен	нет	явная инвариантность
`PhantomData<fn(T)>`	контрвариантен	нет	«потребляю T, не произвожу»
`PhantomData<Cell<T>>`	инвариантен	нет	явная инвариантность с семантикой изменения
`dyn Trait + 'a`	ковариантен по `'a`	—	трейт-объект
`dyn Trait<T>`	инвариантен по T	—	трейт-объект с параметром

Самое полезное, что лично я вынес из этого: variance — это по сути просто вопрос, который нужно задавать себе про каждый тип: этот тип только читает T, только пишет, или и то и другое? Ответ на этот вопрос почти всегда сразу говорит, какая variance нужна. Всё остальное — PhantomData, NonNull, #[may_dangle], это уже просто инструменты, которые позволяют выразить ответ в коде точнее.

Размещайте облачную инфраструктуру и масштабируйте сервисы с надежным облачным провайдером Beget.
Эксклюзивно для читателей Хабра мы даем бонус 10% при первом пополнении.

Subtyping и variance в Rust: о чём обычно молчат