Дженерики на максималках

В уроке про дженерики и границы ты научился писать fn max<T: Ord>(...) и понял, что компилятор разворачивает обобщённый код в конкретный под каждый тип, без цены в рантайме. Этим уроком мы закрываем блок «Глубокий core», и закрываем его на самом интересном: на том краю системы типов, где типы перестают быть просто ярлыками на данных и начинают считать, доказывать и запрещать.

Что разберём. Ассоциированные типы против дженерик-параметров (две похожие записи под разные задачи). GAT, дженерик прямо на ассоциированном типе. Const generics, где параметром служит число, а не тип. HRTB и for<'a>, граница, истинная для любого времени жизни сразу. И наконец проблема выражения и typestate, где состояние программы переезжает в тип, а невалидный вызов просто не компилируется. Всё это работает до запуска и не стоит ни байта.

Ассоциированный тип против дженерик-параметра

Начнём с развилки, на которой спотыкаются почти все. У трейта есть два способа притащить с собой ещё один тип, и выглядят они обманчиво похоже.

Первый способ это ассоциированный тип: трейт объявляет внутри себя type Item, а реализация его задаёт. Так устроен Iterator:

pub trait Iterator {
    type Item;                       // ассоциированный тип
    fn next(&mut self) -> Option<Self::Item>;
}

impl Iterator for Counter {
    type Item = u32;                 // для Counter ответ один: u32
    fn next(&mut self) -> Option<u32> { /* ... */ }
}

Второй способ это дженерик-параметр самого трейта: trait Convert<Target>. Тут тип выбирает не реализация, а тот, кто пишет границу.

pub trait From<T> {                  // T это параметр трейта
    fn from(value: T) -> Self;
}

impl From<i32> for Wrapper { /* ... */ }
impl From<&str> for Wrapper { /* ... */ }   // тот же Self, разные T: можно

Разница ровно в одном вопросе: сколько реализаций для одного Self ты хочешь разрешить. Ассоциированный тип говорит «для данного типа ответ единственный»: у Counter элемент всегда u32, второй реализации Iterator для Counter быть не может. Дженерик-параметр говорит «для одного типа реализаций сколько угодно, по одной на каждый параметр»: Wrapper умеет рождаться и из i32, и из &str, это два разных impl From<...>.

Отсюда практическое правило выбора. Если выходной тип однозначно определяется тем, кто реализует трейт (у итератора по строкам элемент это всегда символ или байт, выбора нет), бери ассоциированный тип: меньше параметров в сигнатурах, компилятор сам выводит Self::Item. Если же ты хочешь несколько реализаций для одного типа, по штуке на каждый вариант входа, нужен дженерик-параметр. From обязан быть дженериком именно потому, что один тип должен конструироваться из многих разных.

// ассоциированный тип: компилятор выводит Item, его не надо называть в границе
fn sum_all<I: Iterator<Item = u32>>(it: I) -> u32 { it.sum() }

// если бы Item был параметром трейта (Iterator<u32>), его пришлось бы
// таскать в каждой сигнатуре, и Vec<i32> мог бы случайно реализовать
// Iterator дважды с разным элементом: каша вместо вывода типов

GAT: дженерик прямо на ассоциированном типе

Ассоциированный тип фиксирован: type Item = u32, и точка. Но иногда он сам должен быть обобщён, чаще всего по времени жизни. Это и есть GAT, обобщённые ассоциированные типы, ставшие стабильными в Rust 1.65.

Классическая мотивация это «одалживающий итератор» (lending iterator): итератор, который на каждом шаге отдаёт ссылку в свой же буфер, а не владеемое значение. Обычный Iterator так не умеет: его Item не может заимствовать из &mut self, потому что в сигнатуре next нет общего времени жизни между элементом и заимствованием. GAT добавляет это время жизни прямо в ассоциированный тип:

trait LendingIterator {
    type Item<'a> where Self: 'a;    // элемент параметризован временем жизни заимствования
    fn next(&mut self) -> Option<Self::Item<'_>>;
}

struct Windows {
    buf: Vec<u8>,
    pos: usize,
}

impl LendingIterator for Windows {
    type Item<'a> = &'a [u8];        // отдаём срез внутрь buf, ничего не копируя
    fn next(&mut self) -> Option<&[u8]> {
        let win = self.buf.get(self.pos..self.pos + 4)?;
        self.pos += 1;
        Some(win)
    }
}

Каждый возвращённый срез живёт ровно столько, сколько длится заимствование &mut self, поэтому два соседних окна нельзя держать одновременно (как и должно быть: между шагами буфер мог сдвинуться). До GAT такой API в безопасном Rust выразить было нельзя, приходилось копировать в Vec. Это узкая, но важная фича: она открывает класс API с нулевым копированием там, где раньше платили аллокацией.

Const generics: параметр это число, а не тип

До сих пор параметром был тип (T) или время жизни ('a). Const generics добавляют третий вид: параметр-значение, известное на этапе компиляции.

struct Matrix<const ROWS: usize, const COLS: usize> {
    data: [[f64; COLS]; ROWS],       // размеры зашиты в тип
}

impl<const ROWS: usize, const COLS: usize> Matrix<ROWS, COLS> {
    fn zeros() -> Self {
        Matrix { data: [[0.0; COLS]; ROWS] }
    }
}

fn main() {
    let m = Matrix::<2, 3>::zeros();  // тип знает: это матрица 2 на 3
    // Matrix<2, 3> и Matrix<3, 2> это РАЗНЫЕ типы, перепутать нельзя
}

Главная боль, которую это сняло, это массивы фиксированной длины. Раньше [T; N] нельзя было обобщить по N, и стандартная библиотека реализовывала трейты для массивов через макрос, вручную перечисляя длины от 0 до 32 (почему [T; 33] исторически и не печатался через Debug). Теперь impl<T, const N: usize> Trait for [T; N] пишется один раз и работает для любой длины. Значение N участвует в типе так же полноправно, как T: компилятор инстанцирует отдельную версию кода под каждое использованное число, и неверный размер ловится до запуска.

HRTB: граница для любого времени жизни сразу

Теперь самая загадочная запись во всём Rust, та, что внезапно вылезает в сообщениях об ошибках вокруг замыканий: for<'a>. Это HRTB, граница высшего ранга, и читается она буквально: «для любого времени жизни 'a».

Зачем такое вообще нужно. Сравни две функции, принимающие замыкание:

// 'a фиксировано снаружи: замыкание обязано работать с одним конкретным временем жизни
fn apply_fixed<'a, F: Fn(&'a str) -> &'a str>(f: F, s: &'a str) -> &'a str { f(s) }

// for<'a>: замыкание обязано работать с ЛЮБЫМ временем жизни, которое мы дадим
fn apply_any<F: for<'a> Fn(&'a str) -> &'a str>(f: F) {
    let long = String::from("длинная");
    let short = String::from("к");
    println!("{}", f(&long));        // одно время жизни
    println!("{}", f(&short));       // другое, более короткое
}

В apply_fixed время жизни 'a выбирается один раз на весь вызов, и обе ссылки обязаны жить одинаково долго. В apply_any замыкание должно уметь принять ссылку с любым временем жизни, потому что внутри мы зовём его дважды с разными по длине заимствованиями. Вот это «с любым» и есть for<'a>: граница утверждается не для одного конкретного 'a, а сразу для всех. Без неё компилятор не пустил бы второй вызов: он не смог бы найти единое время жизни, подходящее обоим.

Хорошая новость: в 95% случаев for<'a> подставляется автоматически, и писать её руками не приходится (это называется late-bound lifetime elision). Видишь ты её обычно тогда, когда что-то пошло не так и компилятор печатает expected ... found ... с непонятным for<'a> внутри. Теперь ты знаешь, что это не магия, а «граница, истинная для любого времени жизни», и читать такое сообщение надо именно так.

Проблема выражения: enum против трейтов

Поднимемся на уровень проектирования. Есть классическая дилемма, у которой даже имя есть: проблема выражения. Суть в том, что данные растут в двух независимых направлениях: добавляются новые виды данных и добавляются новые операции над ними. Хочется расширять и то и другое, не переписывая старое. Полностью бесплатно так не бывает, и Rust честно даёт тебе два инструмента с зеркальными компромиссами.

enum + match это закрытый набор типов. Все варианты перечислены в одном месте.

enum Shape { Circle(f64), Square(f64) }

fn area(s: &Shape) -> f64 {
    match s {
        Shape::Circle(r) => 3.14 * r * r,
        Shape::Square(a) => a * a,
    }
}
fn perimeter(s: &Shape) -> f64 { /* ещё один match */ 0.0 }

Добавить новую операцию (perimeter, to_svg) тут легко: пишешь новую функцию с новым match, старый код не трогаешь, и компилятор даже проверит, что ты учёл все варианты. А вот добавить новый вид (Triangle) дорого: надо влезть в само определение enum и поправить каждый match во всём коде, иначе не скомпилируется.

Трейт + impl это открытый набор типов. Каждый тип сам по себе.

trait Shape { fn area(&self) -> f64; }

struct Circle(f64);
struct Square(f64);
impl Shape for Circle { fn area(&self) -> f64 { 3.14 * self.0 * self.0 } }
impl Shape for Square { fn area(&self) -> f64 { self.0 * self.0 } }

Тут зеркально. Добавить новый вид (Triangle) легко: новая структура, новый impl Shape, старое не трогаешь, можно даже в чужом крейте. А добавить новую операцию дорого: метод perimeter придётся дописать в трейт и в каждый существующий impl.

Вывод не в том, что один способ лучше. Вывод в том, что ось, которую ты ждёшь чаще, должна быть дешёвой. Набор операций стабилен, а типы будут прилетать извне (плагины, форматы файлов)? Бери трейт. Набор типов закрыт и известен (токены лексера, состояния протокола), а операции над ними будут множиться? Бери enum. Это не вкусовщина, а прямой инженерный расчёт, и теперь у тебя есть таблица, чтобы его сделать.

Typestate: состояние программы переезжает в тип

И последний приём, ради которого всё затевалось. Typestate кодирует состояние объекта не значением поля, а его типом. Каждое состояние это отдельный тип, и методы, неуместные в этом состоянии, в нём попросту отсутствуют. Вызвать их нельзя не потому, что в рантайме выскочит ошибка, а потому что код с таким вызовом не скомпилируется.

Соберём билдер HTTP-запроса. Состояние «есть ли URL» и «готов ли к отправке» поедет в дженерик-маркер:

use std::marker::PhantomData;

struct Draft;   // маркеры состояний, каждый это ZST (ноль байт)
struct HasUrl;
struct Ready;

struct RequestBuilder<S> {
    url: Option<String>,
    body: Option<String>,
    _state: PhantomData<S>,          // состояние живёт только в типе
}

impl RequestBuilder<Draft> {
    fn new() -> Self {
        RequestBuilder { url: None, body: None, _state: PhantomData }
    }
    fn url(self, u: &str) -> RequestBuilder<HasUrl> {   // переход Draft -> HasUrl
        RequestBuilder { url: Some(u.into()), body: self.body, _state: PhantomData }
    }
}

impl RequestBuilder<HasUrl> {
    fn body(self, b: &str) -> RequestBuilder<Ready> {   // переход HasUrl -> Ready
        RequestBuilder { url: self.url, body: Some(b.into()), _state: PhantomData }
    }
}

impl RequestBuilder<Ready> {
    fn send(self) -> String {        // send существует ТОЛЬКО у Ready
        format!("POST {} body={}", self.url.unwrap(), self.body.unwrap())
    }
}

Теперь главное. Метод send объявлен только в impl RequestBuilder<Ready>. Значит, RequestBuilder::new().send() не компилируется: у типа RequestBuilder<Draft> метода send физически нет, и компилятор скажет no method named 'send' found for RequestBuilder<Draft>. Чтобы добраться до send, ты обязан пройти url(...), потом body(...), и каждый шаг меняет тип. Невозможное состояние «отправить запрос без URL» исчезло не из логики проверок, а из системы типов. И платить за это нечем: PhantomData<S> занимает ноль байт, размер билдера не меняется.

Покрути стенд: начни с Draft, попробуй вызвать send() раньше времени и прочитай ошибку, потом пройди цепочку правильно. Следи, как с каждым шагом меняется тип слева.

Так строят защищённые API в большом коде: File в режиме чтения и записи, состояния TCP-соединения, шаги OAuth, конфигурация устройства во встраиваемом Rust. Везде одна идея: сделать невалидный переход не ошибкой времени выполнения, а ошибкой компиляции, и пусть проверяющий труд возьмёт на себя система типов.

Правило урока

Свернём весь край системы типов в одну мысль.

Когда выходной тип однозначно задан реализацией, бери ассоциированный тип (type Item), когда нужно много реализаций на один тип, бери дженерик-параметр трейта (From<T>). GAT добавляет параметр самому ассоциированному типу (type Item<'a>) и открывает API с заимствованием из Self. Const generics делают параметром число, а не тип, и снимают боль массивов фиксированной длины. for<'a> это граница «для любого времени жизни сразу», нужная замыканиям, работающим с любым заимствованием. Набор типов и набор операций тянут в разные стороны (проблема выражения): enum дешёв на новые операции и дорог на новые типы, трейт наоборот, выбирай по той оси, что будет расти. А typestate переносит состояние в тип, и невалидный вызов перестаёт компилироваться, всё это без цены в рантайме.

Типичная ошибка, которую снимает урок: упереться в загадочное for<'a> или the trait Trait is not implemented вокруг ассоциированных типов и начать наугад добавлять параметры и 'static. На деле почти всегда вопрос один: ты перепутал ось. Либо запихиваешь в дженерик-параметр то, что должно быть ассоциированным типом (и получаешь неоднозначность вывода), либо ждёшь от ассоциированного типа второй реализации, которой он по определению не допускает. Сначала ответь «сколько реализаций на один тип я хочу», и запись выберется сама.

ДЗ

Дальше

Ты прошёл весь край системы типов: ассоциированные типы и GAT, const generics, for<'a> и typestate. Общая нить простая: чем больше работы ты перекладываешь на типы, тем больше ошибок ловится до запуска и тем меньше остаётся проверок в рантайме. Это и есть «нулевая стоимость абстракции» в её сильной форме. Но у системы типов есть потолок: она не умеет порождать код. Когда дублирование начинается не на уровне значений, а на уровне самих объявлений (десять почти одинаковых impl, таблица вариантов, обёртка над каждым полем), дженерик уже не помогает, потому что обобщать нужно не значение, а синтаксис. Тут начинается метапрограммирование. В следующем уроке мы откроем macro_rules!: кодогенерацию по образцу, которая работает на этапе компиляции и пишет код за тебя, и разберём, во что на самом деле разворачивается знакомый println!.