Я нашел эту статью авторства Alexis Beingessner как наиболее понятное описание системы типов в Rust, и что с ними можно делать. Надеюсь, кому-нибудь этот перевод будет полезен. Не смотрите на то, что вначале описываются очевидные вещи — под конец можно утонуть. Статья огромная и скорее всего будет разобрана на главы. Переведено достаточно вольно. Авторский стиль сохранен. — прим.пер.
(статья написана о Rust 1.7 stable)
В системе типов Rust есть много всякого. Насколько я знаю, практически вся сложность этого всякого заключается в том, чтобы выразить программу в максимально обобщённом виде. Притом народ еще и требует большего! У меня всегда были проблемы с простым пониманием наиболее сложных вещей, потому этот пост скорее напоминалка самому себе. Но тем не менее, мне также нравится делать что-то, полезное другим, поэтому в данной статье также есть вещи, которые я вряд ли забуду, но о которых некоторые могут не знать.
В этой статье не будет исчерпывающего описания синтаксиса или общих деталей описываемых возможностей. Здесь рассказывается, почему происходит так или иначе, так как подобные вещи я всегда забываю. Если вы нашли эту статью в попытках выучить Rust полноценно, вам определенно стоит для начала ознакомиться с Книгой (оригинал вот — прим.пер.). В то же время я здесь буду уточнять некоторые произвольные теоретические аспекты того, что происходит.
Скорее всего, в этой статье полно ошибок, и она не должна претендовать на звание официального руководства. Это просто сборник того, что я накопал за неделю, пока искал новую работу.
Краткое описание принципов переиспользования кода
(здесь и далее под «переиспользованием» я подразумеваю «повторное использование» — звучит не так неуклюже, понимается быстрей — прим.пер.)
Желание использовать части кода более одного раза существует с тех самых ранних времен, когда самые первые вычислительные машины получили свой первый полезный результирующий бит. Определенно, я не имею ни малейшего представления о том, как в то прекрасное время выглядело переиспользование кода. Может, листики-шпаргалки? Или стопки перфокарт? Понятия не имею. Мне интересней, как это делается сейчас.
Наиболее известная форма повторного использования кода — это, безусловно, функция. Ну как бы да, функции привычны всем. Однако, в зависимости от того, на каком языке вы пишете и что вам необходимо сделать, возможностей функций как приема переиспользования кода может быть недостаточно. Возможно, вам требуется применить что-то, существующее под современными терминами «метапрограммирование» (когда код создает сам себя) или «полиморфизм» (когда код можно применить для различных типов данных).
Технически эти принципы совершенно разные, тем не менее их часто приходится использовать вместе. В современных языках реализации этих принципов представлены достаточно широко: макросы, шаблоны, дженерики, наследование, указатели на функции, интерфейсы, перегрузка, группировка (union) и так далее. Однако, все это лишь семантическое разнообразие реализации трех основных принципов — мономорфизм, виртуализация, перечисление.
Мономорфизм
Мономорфизм — по сути практика копипасты куска кода, с незначительными изменениями в каждой новой копии. Главная выгода мономорфизма — возможность «идеально кастомизировать» реализацию, не пугая компилятор сложными конструкциями. Это же и главный недостаток принципа — в худшем случае мы получим изрядно растолстевший код, из-за множества практически идентичных частей, которые физически скопированы во все места, где используются. К толстому бинарнику и увеличенному времени компиляции здесь добавляется и чудовищная нагрузка на кэш инструкций в процессоре. По сути, никаким переиспользованием кода здесь и не пахнет!
Семантическое ограничение мономорфизма в том, что его нельзя использовать (напрямую) в обработке нескольких различных типов данных одновременно. К примеру, я хочу построить очередь исполнения (job queue), принимающую различные задачи, и с ее помощью выполнить эти задачи в порядке поступления. При условии, что все задачи идентичны, все решается мономорфизмом довольно просто. Проблемы появляются, когда задачи различны — становится неясно, как это реализовать только мономорфизмом. Поэтому и название у него — мономорфизм. Абстракция над кодом, который делает только что-нибудь одно.
Распространенные примеры мономорфизма: шаблоны С++, макросы С, Go Generate, дженерики C#. Большинство из них работает при компиляции, кроме дженериков С#, которые мономорфируют во время выполнения кода. Все, что создается во время компиляции — шаблон. Мономорфизм жутко популярен как средство оптимизации при обычной (inline) и JIT-компиляции.
Виртуализация
Прямая противоположность мономорфизма, к которой приходит каждый разработчик, наигравшись в копипаст: прикрутить вариативность применения. И данные, и исполняемый код могут быть виртуализированы, после чего все, что видит пользователь виртуального интерфейса — тот на что-то указывает.
Виртуализация позволяет коду работать с типами различного размера и структуры совершенно одинаково. Виртуализация функции позволяет ей иметь альтернативное поведение без необходимости копипаста. Пример с очередью исполнения, на котором мономорфизм ломает зубы, прекрасно решается виртуализацией — любая задача, которую необходимо выполнить, являет собой указатель на функцию, которую можно найти и запустить. Нужны данные отдельно для каждой задачи — без вопросов, добавляем еще указатель на данные, они подгрузятся вместе с функцией.
Главный недостаток виртуализации — она обычно влияет на производительность, вариативность кода выливается в частое выделение памяти в куче, прыжки по указателям (кэш негодует) и определение, с чем же именно мы в данный момент имеем дело.
Однако виртуализация может быть производительней мономорфирования! Каждый раз, когда функция дергается статически, компилятор способен заинлайнить ее, но делает это не всегда, так как, как уже было сказано, это перегружает и замусоривает бинарь. По тем же причинам выгодной бывает насильная виртуализация редко использующихся функций. К примеру, хендлерам исключений вовсе нежелательно постоянно запускаться, и лучше их виртуализировать, расчистив таким образом кэш инструкций для «безошибочной» ветки выполнения.
Распространенные примеры виртуализации: указатели на функцию и пустые (void) указатели в С, обратные вызовы, наследование, дженерики Java, прототипы Javascript. Заметьте, что во многих из этих примеров нет различия между виртуализацией данных и исполняемого кода. Например, если у меня указатель на Животное, за ним может стоять и Кот, и Пёс, и когда я прошу это Животное подать голос() — он же откуда-то знает, сказать ему «Гав» или «Мяу»?
Обычный способ реализации виртуализации для каждого объекта каждого типа — иерархия наследований для скрытого хранения указателей на разные куски имплементаций, которые могут понадобиться в процессе работы программы, называемая «vtable». Обычно в vtable хранят пачку указателей на функции (в том числе и на голос() из примера выше), но могут также и размер, выравнивание в памяти, конкретный тип объекта.
Перечисления
Перечисления (enums) это компромисс между виртуализацией и мономорфизмом. Во время выполнения мономорфированный код может быть только один, без вариантов, виртуализированный может быть каким угодно. Код из перечисления может быть любым из ограниченного списка вариантов. Обычно использование перечислений заключается в работе с неким целочисленным «тегом», определяющим вариант из списка, который нужно использовать.
Например, наша очередь исполнения, реализованная перечислением, может определять три типа возможных задач, «Создать», «Изменить», «Удалить». Для использования, к примеру, «Создания», нужно всего лишь отправить очереди данные для Создания, помеченные тегом, соответствующим функции «Создать». Очередь видит тег, понимает из него, что от нее хотят и что лежит в данных, и запускает соответствующий код.
Как и в виртуализации, перечисление может понимать разные типы данных с помощью одного и того же кода, который теперь нет необходимости копировать. Как и в мономорфизме, здесь нет нужды в вариативности — меняется только тег. Кроме того, оптимизировать перечисления существенно проще.
Нужно, однако, отметить, что если вариативность не использовать совсем, перечислимый тип серьезно разрастется, так как каждому объекту типа придется хранить информацию для наибольшего типа, который присутствует в перечислении. Для того, чтобы «Удалить», хватит и только имени, а вот «Создать» попросит имя, тип, автора, содержимое, и так далее, и даже если так случилось, что очередь используется в основном для «удаления», памяти она будет просить как для постоянного «создания».
Ну и разумеется, вам нужно знать наперед весь ассортимент возможностей, это главное ограничение перечислений. И мономорфизм, и виртуализацию можно расширить при необходимости в любой момент, чего не скажешь о перечислении — шаблон можно наложить на новый тип, класс можно унаследовать, а перечисление уже выжжено в коде намертво. Лучше не ковырять его с попытками обмануть и расширить — вы с большой долей вероятности сломаете код тех, кто уже его использует!
Поэтому данная стратегия отчасти невразумительна. Много у каких языков она встречается в виде enum, тем не менее ее использование серьезно ограничено, из-за невозможности ассоциировать данные отдельно для каждого варианта в перечислении. С позволяет определить вариант как группу из двух типов, но решение вопроса, что из этих типов данные, а что код, взваливается на пользователя перечисления. Во многих функциональных языках есть группы с тегами (tagged unions), которые являются объединением перечислений и группой в С, позволяющим приклеить произвольные данные к разным вариантам перечисления.
А как в Rust?
Вот да, мы перечислили возможности других языков, а с нашим что делать можно? А в нашем все держится на трех столпах:
- Макросы (простой мономорфизм)
- Перечисления (полноценные, с данными!)
- Трейты (тут будет весело)
Макросы
Тут все просто. Чистое переиспользование кода. В Rust они работают поверх основного синтаксического дерева (AST, abstract syntax tree) — кормишь макрос синтаксическим деревом, результатом получаешь другое дерево. Информации о типах вроде «хм, эта строка похожа на чьё-то имя» в макросах нет (на самом деле немного есть — прим. пер.).
Обычно макросы используют по двум причинам: расширить сам язык или сделать копию существующего кода. Первый местами открыто используется в стандартной библиотеке Rust (println!, thread_local!, vec!, try!, и всё такое):
/// Создать вектор `Vec`, содержащий аргументы.
///
/// `vec!` позволяет создать `Vec`s по синтаксису создания массивов.
/// У данного макроса две формы:
///
/// - Создать `Vec` с данным списком элементов:
///
/// ```
/// let v = vec![1, 2, 3];
/// assert_eq!(v[0], 1);
/// assert_eq!(v[1], 2);
/// assert_eq!(v[2], 3);
/// ```
///
/// - Создать `Vec` данного размера из копий данного элемента:
///
/// ```
/// let v = vec![1; 3];
/// assert_eq!(v, [1, 1, 1]);
/// ```
///
/// Обратите внимание - в отличие от массивов данный макрос работает только с типами,
/// которые реализуют трейт `Clone`, а размер может быть и выражением, а не только константой.
///
/// Здесь используется `clone()` для копирования элемента, поэтому поосторожней с
/// типами с нестандартной реализацией `Clone`. Например,
/// `vec![Rc::new(1); 5]` создаст пять указателей на один и тот же integer из кучи,
/// а не пять разных значений.
#[cfg(not(test))]
#[macro_export]
#[stable(feature = "rust1", since = "1.0.0")]
macro_rules! vec {
($elem:expr; $n:expr) => (
$crate::vec::from_elem($elem, $n)
);
($($x:expr),*) => (
<[_]>::into_vec($crate::boxed::Box::new([$($x),*]))
);
($($x:expr,)*) => (vec![$($x),*])
}
а последний используется внутри для реализации многих повторяющихся интерфейсов:
// Трейт для преобразований целочисленных и дробных примитивов
// Преобразования T -> T покрыты пустой имплементацией и потому исключены.
// Некоторые преобразования между знаковыми и беззнаковыми типами не реализованы
// ввиду плохой переносимости между архитектурами
macro_rules! impl_from {
($Small: ty, $Large: ty) => {
impl From<$Small> for $Large {
fn from(small: $Small) -> $Large {
small as $Large
}
}
}
}
// Беззнаковый -> Беззнаковый
impl_from! { u8, u16 }
impl_from! { u8, u32 }
impl_from! { u8, u64 }
// и далее больше сорока раз в том же духе...
Насколько мне представляется, макросы это наихудший из предоставленных способов переиспользования кода. Они какбе должны помогать (имена переменных не используются внутри и не утекают из макроса), но много где ими чересчур увлекаются (использование unsafe в макросах дает странные побочные эффекты (интересно, какие? — прим. пер.)). В основе обработчика макросов лежит регулярное выражение (если закрыть глаза на то, что expr и tt парсить совсем не тривиально), и вообще, регулярки никто читать не любит!
Более важно, ИМХО, что макросы тут по сути метапрограммирование с динамической типизацией. Компилятор не проверяет, что тело макроса соответствует его сигнатуре, он генерирует согласно макросу код, получает что-то на выходе, и только тогда производит проверку, что приводит к типичной проблеме динамического программирования — поздняя привязка ошибок. Так мы можем получить аналог нетленного «undefined is not a function» для Rust:
macro_rules! make_struct {
(name: ident) => {
struct name {
field: u32,
}
}
}
make_struct! { Foo }
<anon>:10:16: 10:19 error: no rules expected the token `Foo`
<anon>:10 make_struct! { Foo }
^~~
playpen: application terminated with error code 101
Вот что тут за ошибка? Конечно, я забыл про $, потому макрос понимает name не как переменную, а как литерал и всегда отдает
struct name { field: u32 }
(если честно, так себе повод относиться к макросам прохладно — прим. пер.)
Далее, если в сгенерированном по макросу коде вылезет обычная ошибка, в логах будет неперевариваемая каша:
use std::fs::File;
fn main() {
let x = try!(File::open("Hello"));
}
<std macros>:5:8: 6:42 error: mismatched types:
expected `()`,
found `core::result::Result<_, _>`
(expected (),
found enum `core::result::Result`) [E0308]
<std macros>:5 return $ crate:: result:: Result:: Err (
<std macros>:6 $ crate:: convert:: From:: from ( err ) ) } } )
<anon>:4:13: 4:38 note: in this expansion of try! (defined in <std macros>)
<std macros>:5:8: 6:42 help: see the detailed explanation for E0308
Ну… зато у нас в плюсах, как и у других динамически типизированных языков, существенно больше гибкости в выражениях. Короче, макросы прекрасны в тех областях, где их применение оправдано, они просто… хрупкие, что ли.
Стоит упомянуть: расширение синтаксиса и генерация кода
Конечно, у макросов есть пределы. Они не выполняют произвольный код во время компиляции. Это хорошо для безопасности и частой сборки, но иногда мешает. В Rust это исправляемо двумя способами: расширения синтаксиса (известные как процедурные макросы) и генерация кода (build.rs) (с 10й версии языка еще и плагины к компилятору — прим. пер.). Все они дают вам зеленый свет для выполнения чего угодно для генерации чего угодно.
Расширения синтаксиса выглядят как макросы или аннотации, но у них есть способность просить компилятор выполнить произвольные действия для (в идеале) изменения дерева синтаксиса. Файлы build.rs понимаются пакетным менеджером Cargo как что-то, что нужно собирать и запускать каждый раз при сборке пакета. Очевидно, что им позволено копошиться в проекте как заблагорассудится. Ожидаемо, что лучше это использовать для недоступной макросам генерации кода.
Я бы еще мог добавить пару-тройку примеров, но особо не в теме этих возможностей, и совершенно к ним равнодушен. Ну генерация кода, и ладно. И вообще, я эту статью уже не первый день пишу и основательно подзадолбался (авторский капс убран — прим. пер.).
Перечисления
В точности описанные ранее группировки с тегами.
Чаще всего встречаются в лице Option и Result, выражающие успешный/неудачный результат чего-либо. То есть, это буквально перечисления с вариантами «Успех» и «Поломка».
Можно и свои перечисления написать. Вот, к примеру, вам надо код работы с сетью, который работает с ipv4 и ipv6. Вам совершенно точно не нужна возможная поддержка гипотетического ipv8, да и будь он даже необходим, все равно пес его знает, что с ним в коде делать. Пишем перечисление для того, что точно есть:
enum IpAddress {
V4(IPv4Address),
V6(Ipv6Address),
}
fn connect(addr: IpAddress) {
// смотрим, что пришло, запускаем соответствующий обработчик
match addr {
V4(ip) => connect_v4(ip),
V6(ip) => connect_v6(ip),
}
}
Всё. Дальше можно работать с общим типом IpAddress, а если кому необходимо узнать точный тип внутри, его можно способом, описанным выше, выудить с помощью match.
Трейты
До этого момента все было просто, сейчас пойдет посложней и поинтересней.
Если коротко, трейты в Rust предназначены для описания всего остального. Мономорфирование, виртуализация, рефлексия, перегрузка операторов, преобразование типов, семантика копирования, потокобезопасность, функции высших порядков, итераторы для циклов — весь этот цветастый паноптикум работает через трейты. Далее, все новые пользовательские возможности языка наиболее вероятно реализуются через трейты.
А вообще трейты это интерфейсы. Нет, серьезно.
struct MyType {
data: u32,
}
// Смотрите, интерфейс же
trait MyTrait {
fn foo(&self) -> u32;
}
// Вот мы его реализуем
impl MyTrait for MyType {
fn foo(&self) -> u32 {
self.data
}
}
fn main() {
let mine = MyType { data: 0 };
println!("{}", mine.foo());
}
Очень часто общение с трейтами не отличается от общения с интерфейсами в Java или С#, но иногда приходится переступать черту. Трейты задуманы архитектурно более гибкими. В С# и Java реализовывать MyTrait для MyType может только владелец MyType. В Rust такое разрешено и для владельца MyTrait. Это позволяет авторам библиотек с трейтами писать их реализации также для, скажем, типов из стандартной библиотеки.
Безусловно, пускание такой фичи на самотек весьма чревато — мало ли что кому куда взбредет реализовывать. Потому это счастье ограничено видимостью имплементаций только для того кода, у которого есть в области видимости соответствующий трейт. Отсюда, кстати, все проблемы с работой с вводом-выводом, если не импортировать Read и Write явно.
В тему: согласованность
Знакомые с Haskell могут увидеть в трейтах много общего с классами типов (type classes). Они же вправе задать совершенно очевидный и обоснованный вопрос: а что, собственно, будет, если реализовать один и тот же трейт для одного и того же типа несколько раз в разных местах? Вопрос согласованности, то есть. В согласованном мире есть только одна пара реализации трейт-тип. А в Rust для достижения согласованности существует большее количество ограничений, чем есть таковые в Haskell. Ограничения же сводятся к следующему — вы должны быть владельцем либо трейта, либо типа, что его реализует, а также у вас не должно быть круговых зависимостей.
impl Trait for Type
Это красиво, просто и понятно, но немного неправда, так как вы можете нарисовать что-то вроде:
impl Trait for Box<MyType>
даже если вы понятия не имеете, где физически находятся Trait и MyType. Корректная обработка подобных манипуляций и является основной сложностью согласованности. Она регулируется т.н. «правилами уникальности» (orphan rules), которые требуют условия, что для всей паутины зависимостей лишь один крейт содержит реализацию трейта для определенной комбинации типов (о комбинациях будет ниже — прим.пер.). В результате две различные библиотеки, содержащие конфликтные реализации, будучи импортированными одновременно, просто не скомпилируются. Это иногда раздражает до такой степени, что Нико Матсакиса хочется натурально проклять (Niko Matsakis, один из главных коммиттеров Rust — прим.пер.).
Забавно, что нарушения согласованности в стандартной библиотеке Rust (которая внутри склеена из нескольких непересекающихся частей) теоретически встречаются сплошь и рядом, поэтому некоторые трейты, имплементации и типы всплывают довольно в неожиданных местах. Еще более забавно, что тасовать так типы помогало не очень, в результате чего родился костыль #[fundamental], приказывающий компилятору закрывать на несогласованность глаза.
Дженерики
(я понимаю, что правильно их назвать «обобщенные типы», но это во-первых, долго, во вторых, менее понятно, так как все всё равно пользуются термином «дженерики» — прим.пер.)
Так как же использовать трейты для повторного использования кода? Тут Rust нам дает выбор! Мы можем мономорфировать, можем виртуализировать. Мономорфизм в подавляющем большинстве случаев является выбором в стандартной библиотеке, а также в большей части кода, что я видел. Вероятно, это потому что мономорфизм в целом более эффективен, а также явно более обобщен. Тем не менее мономорфный интерфейс можно виртуализировать, что я чуть позже покажу.
Мономорфный интерфейс реализуется в Rust дженериками:
// Простая структура, для нужд сравнения.
struct Concrete {
data: u32,
}
// Обобщенная структура. `<..>` указывает на обобщенный аргумент типа.
// Можно создать версию `Generic` для чего угодно, кроме
// `Concrete`, потому что он не дженерик и умеет только `u32`.
struct Generic<T> {
data: T,
}
// Обычная реализация
impl Concrete {
fn new(data: u32) -> Concrete {
Concrete { data: data }
}
fn is_big(&self) -> bool {
self.data > 120
}
}
// Реализация для конкретного класса Foo.
// Смотрите, это не специализация, в том смысле,
// что определенные здесь имена типов не конфликтуют
// с другими реализациями.
// (Говоря проще, тип аргумента дженерика это часть типа самого дженерика - прим.пер.)
impl Generic<u32> {
fn is_big(&self) -> bool {
self.data > 120
}
}
// Реализуем для всех возможных T.
// "impl" здесь также Generic.
// Надеюсь, этот пример плюс предыдущий вместе
// убедительно показывают, зачем здесь еще один <T>.
impl<T> Generic<T> {
fn new(data: T) -> Generic<T> {
Generic { data: data }
}
fn get(&self) -> &T {
&self.data
}
}
// Обычный трейт.
trait Clone {
fn clone(&self) -> Self;
}
// Обобщенный трейт.
// Определяет отношение к другому типу. В данном случае мы хотим
// сравнивать экземпляр нашего типа с экземпляром другого, который определен как Т.
// Дальше будет понятней.
trait Equal<T> {
fn equal(&self, other: &T) -> bool;
}
// Реализация обычного трейта
impl Clone for Concrete {
fn clone(&self) -> Self {
Concrete { data: self.data }
}
}
// Конкретная реализация обобщенного трейта для конкретного типа
impl Equal<Concrete> for Concrete {
fn equal(&self, other: &Concrete) -> bool {
self.data == other.data
}
}
// А, для чужих типов это тоже работает, мы ж владеем трейтом!
impl Clone for u32 {
fn clone(&self) -> Self {
*self
}
}
impl Equal<u32> for u32 {
fn equal(&self, other: &u32) -> Self {
*self == *other
}
}
// То же, с обобщенным типом!
impl Equal<i32> for u32 {
fn equal(&self, other: &i32) -> Self {
if *other < 0 {
false
} else {
*self == *other as u32
}
}
}
// Обобщенная реализация обобщенного трейта для конкретного типа
impl<T: Equal<u32>> Equal<T> for Concrete {
fn equal(&self, other: &T) -> bool {
other.equal(&self.data)
}
}
// Обобщенная реализация конкретного трейта для обобщенного типа
// Смотрите, нам надо, чтобы `T` реализовывал
// трейт `Clone`! Это *ограничение трейта* (trait bound).
// (некрасиво и малопонятно, да. варианты перевода приветствуются - прим.пер.)
impl<T: Clone> Clone for Generic<T> {
fn clone(&self) -> Self {
Generic { data: self.data.clone() }
}
}
// Обобщенная реализация обобщенного трейта для обобщенного типа.
// У нас появляется второй тип-аргумент U.
impl<T: Equal<U>, U> Equal<Generic<U>> for Generic<T> {
fn equal(&self, other: &Generic<U>) -> bool {
self.equal(&other.data)
}
}
// Ну да, отдельные функции тоже можно обобщить.
impl Concrete {
fn my_equal<T: Equal<u32>>(&self, other: &T) -> bool {
other.equal(&self.data)
}
}
impl<T> Generic<T> {
// Смотрите, куда мы пришли: инвертировали вызов `equal` относительно того,
// кто вызывает, а кто аргумент.
// (`x == y` здесь все еще равен `y == x`). А вот как нам развернуть аргументы типов,
// чтоб получить `T: Equal<U>` чтобы это починить? Мы не можем это сделать одновременно
// с определением `T`, потому что `U` еще не существует!
// Об этом позже.
fn my_equal<U: Equal<T>>(&self, other: &Generic<U>) -> bool {
other.data.equal(&self.data)
}
}
Фух.
Как мы видим, как только встанет необходимость определять интерфейсы и их реализации, выбор у нас богат для разных вариаций обобщенности. А под капотом компилятора, как я уже говорил, все это мономорфизируется. Как минимум до первой оптимизации мы получим вот такой промежуточный код:
// До
struct Generic<T> { data: T }
impl<T> Generic<T> {
fn new(data: T) {
Generic { data: data }
}
}
fn main() {
let thing1 = Generic::new(0u32);
let thing2 = Generic::new(0i32);
}
// После
struct Generic_u32 { data: u32 }
impl Generic_u32 {
fn new(data: u32) {
Generic { data: data }
}
}
struct Generic_i32 { data: i32 }
impl Generic_i32 {
fn new(data: i32) {
Generic { data: data }
}
}
fn main() {
let thing1 = Generic_u32::new(0u32);
let thing2 = Generic_i32::new(0i32);
}
Возможно вы удивитесь (или не удивитесь), но некоторые важные функции заинлайнены очень много где. К примеру, brson нашел в коде Servo более 1700 копий Option::map. В общем верно, виртуализация всех этих вызовов убьет производительность рантайма напрочь.
Тоже важно: определение типа и оператор «турбо-рыба»
(я не могу перевести «turbofish» лучше. варианты приветствуются — прим.пер.)
Дженерики в Rust определяют тип автоматически. Если тип где-то указан, все работает как часы. А если не указан, начинается фейерверк:
// Vec::new() функция обобщенная, определяет тип элементов вектора
// из типа переменной, куда присваивается вывод. Если он указан. Вот сейчас у нас
// точно `Vec`, но тип-аргумент нам неизвестен.
let mut x = Vec::new();
// Раз мы вставляем `u8` в `x`, значит тип вектора `Vec<T>`
x.push(0u8);
x.push(10);
x.push(20);
// `collect` тоже функция обобщенная. Она производит все, что реализует
// `FromIterator`, обычно это коллекция Vec или VecDeque.
// Без четкого определения типа-аргумента непонятно, что же именно
// `collect` производит, в отличие от `Vec::new()`, из этой функции может
// вылезти совершенно что угодно
// Потому тип-аргумент для дженерика лучше определить явно.
let y: Vec<u8> = x.clone().into_iter().collect();
// Или сказать функции напрямую, каким типом следует ограничиться в выводе
// с помощью "турбо-рыбы" `::<>`!
let y = x.clone().into_iter().collect::<Vec<u8>>();
Трейт-объекты
Так как же у нас происходит виртуализация? Как мы удаляем информацию про конкретный тип, чтобы стать просто безликим «чем-то»? У Rust это происходит с помощью трейт-объектов. Вы просто говорите, что данный экземпляр типа это экземпляр трейта, а компилятор делает все остальное. Разумеется, вам также нужно абстрагироваться от размера экземпляра, потому мы также прячемся за указатель, вроде &, &mut, Box, Rc, Arc:
trait Print {
fn print(&self);
}
impl Print for i32 {
fn print(&self) { println!("{}", self); }
}
impl Print for i64 {
fn print(&self) { println!("{}", self); }
}
fn main() {
// Статическое мономорфизированное использование
let x = 0i32;
let y = 10i64;
x.print(); // 0
y.print(); // 10
// Box<Print> - трейт-объект, и может хранить экземпляр
// типа, реализующего Print. Для создания Box<Print> мы просто создадим
// `Box<T: Print>`, и воткнем его куда-то, где ожидают `Box<Print>`.
// Вот мы определили `data` с `Box<Print>`ами,
// и массив-литерал нам радостно выполнил согласование типов!
// Видите, мы вставляем и i32 и i64 в тот же самый список,
// чего не удалось бы сделать с массивом конкретного типа.
let data: [Box<Print>; 2] = [Box::new(20i32), Box::new(30i64)];
// Ну и печать работает соответственно.
for val in &data {
val.print(); // 20, 30
}
}
Обратите внимание, требование прятать конкретный тип за указателем имеет больше последствий, чем может показаться на первый взгляд. Вот, например, наш старый знакомый трейт:
trait Clone {
fn clone(&self) -> Self;
}
Трейт определяет функцию, которая возвращает экземпляр собственного типа по значению.
fn main() {
let x: &Clone = ...; // Трейт-объект за указателем, хорошо
let y = x.clone(); // Щас как склонируем, ииии...?
}
А вот сколько места надо зарезервировать на стеке для y? Какого он вообще типа?
Ответ в том, что мы не знаем этого на этапе компиляции. Это говорит о том, что трейт-объект Clone по факту бессмысленен. Точнее, трейт не может быть превращен в трейт-объект, если в нем есть упоминание собственного типа как значения (а не указателя — прим.пер.).
Трейт-объекты реализованы в Rust довольно неожиданным образом. Давайте вспомним — обычно для таких целей применяются виртуализируемые таблицы функций. Есть минимум две причины, которые в данном способе раздражают.
Первая — все хранится за указателем, независимо от того, есть ли в этом необходимость. То есть если тип определен как виртуализируемый, то хранить этот указатель нужно всем экземплярам типа.
Вторая — получить нужные вам функции из виртуальной таблицы задача не такая и тривиальная. Это все из-за того, что интерфейсы это в общем-то частный случай множественного наследования (у С++ множественное наследование полноценное). В качестве примера вот вам такой набор:
trait Animal { } // Животное
trait Feline { } // Кошачьи
trait Pet { } // Питомец
// Животное, Кошачьи, Питомец
struct Cat { }
// Животное, Питомец
struct Dog { }
// Животное, Кошачьи
struct Tiger { }
Как организовать хранение указателей на функции в случае смешанных типов, таких как Животное + Питомец, или Животное + Кошачьи? Животное + Питомец состоит из Cat и Dog. Мы их подравняем по указателям:
Cat vtable Dog vtable Tiger vtable +-----------------+ +-----------------+ +-----------------+ | type stuff | | type stuff | | type stuff | +-----------------+ +-----------------+ +-----------------+ | Animal stuff | | Animal stuff | | Animal stuff | +-----------------+ +-----------------+ +-----------------+ | Pet stuff | | Pet stuff | | Feline stuff | +-----------------+ +-----------------+ +-----------------+ | Feline stuff | +-----------------+
А теперь Cat и Tiger непохожи. Ок, поменяем местами Питомца и Кошачьи у Cat:
Cat vtable Dog vtable Tiger vtable +-----------------+ +-----------------+ +-----------------+ | type stuff | | type stuff | | type stuff | +-----------------+ +-----------------+ +-----------------+ | Animal stuff | | Animal stuff | | Animal stuff | +-----------------+ +-----------------+ +-----------------+ | Feline stuff | | Pet stuff | | Feline stuff | +-----------------+ +-----------------+ +-----------------+ | Pet stuff | +-----------------+
Ээ, теперь Cat и Dog различаются. Переклеим разметку под функции еще раз, вот так.
Cat vtable Dog vtable Tiger vtable +-----------------+ +-----------------+ +-----------------+ | type stuff | | type stuff | | type stuff | +-----------------+ +-----------------+ +-----------------+ | Animal stuff | | Animal stuff | | Animal stuff | +-----------------+ +-----------------+ +-----------------+ | Feline stuff | | | | Feline stuff | +-----------------+ +-----------------+ +-----------------+ | Pet stuff | | Pet stuff | +-----------------+ +-----------------+
Хорошо. Только это не масштабируется. Получается, у каждого интерфейса должно быть свое уникальное смещение, чтобы каждая виртуальная таблица функций могла теоретически вместить любой необходимый интерфейс, но это также значит, что каждая таблица должна хранить информацию о всех без исключения интерфейсах. Да, неиспользуемое место в конце таблицы можно и обрезать, но это слабое утешение, памяти расходуется слишком много. К тому же мы не можем знать смещения интерфейсов, которые импортированы из динамических библиотек. Поэтому в большинстве языков таблицы функций определяются только во время выполнения программы.
Однако к Rust это все не имеет отношения. Rust не хранит виртуальные таблицы в типах. Трейт-объекты в Rust — это так называемые толстые указатели. &Pet это не один указатель, а два, на данные и на виртуальную таблицу. Виртуальная таблица трейт-объекта, в свою очередь, не привязана к определенному типу. Она уникальна для каждой комбинации типов.
Cat's Pet vtable Dog's Pet vtable +-----------------+ +-----------------+ | type stuff | | type stuff | +-----------------+ +-----------------+ | Pet stuff | | Pet stuff | +-----------------+ +-----------------+
Аналогично, у наборов Животное + Питомец и Животное + Кошачьи разные таблицы. То есть, таблицы функций мономорфизированы для каждого уникального набора типов.
Данный подход полностью устраняет проблему строения виртуальной таблицы функций. Значения, не принимающие участие в виртуализации, не хранят дополнительных данных, и можно статически определить, где в любом типе, реализующем Питомца находится та или иная функция Питомца.
Недостатки у этого способа тоже есть. Толстый указатель занимает вдвое больше места, что можеть обернуться проблемами, если указателей много. Мы также мономорфизируем таблицу функций для каждой запрошенной комбинации типов. Это возможно благодаря тому, что мы можем узнать статически тип каждого объекта в некоторый определенный момент времени, и все приведения к трейт-объектам в том числе. Заменить здесь мономорфирование виртуализацией чревато серьезным падением производительности. (а еще поэтому в языке очень ограниченная возможность приведения типов — прим.пер.).
Внимание: возможность придраться!
Толстые указатели можно в принципе обобщить дальше, до тучных указателей. Как «толстый указатель», тип Животное + Кошачьи указывает на одну общую виртуальную таблицу, тем не менее нет причин не разделить эту таблицу на две, отдельно для каждого трейта, наградив тип двумя на них указателями, соответственно. В теории, этим можно ограничить мономорфизм таблицы, за счет еще сильнее растолстевших указателей. Данная идея регулярно всплывает, но серьезно за нее никто не берется.
Наконец, вспомним недавнее утверждение — мономорфный интерфейс пользователь может сделать виртуализированным. Это возможно благодаря такой штуке, как «реализовать трейт для трейта» (impl Trait for Trait), а точнее — трейт-объект реализует собственный трейт (имхо самая крутая фича системы типов — прим.пер.). В итоге вот такой код валиден:
// Это уже было...
trait Print {
fn print(&self);
}
impl Print for i32 {
fn print(&self) { println!("{}", self); }
}
impl Print for i64 {
fn print(&self) { println!("{}", self); }
}
// ?Sized указывает, что T может быть виртуальный (&, Box, Rc, вот это всё).
// Sized (без знака вопроса) - наоборот, только конкретный тип.
// Тем не менее вещи вроде Traits и [T] размера "не имеют".
// Говоря `T: ?Sized`, мы приказываем компилятору выдать ошибку
// при попытке использовать T по значению, а не через указатель,
// потому как Sized может не быть реализован.
fn print_it_twice<T: ?Sized + Print>(to_print: &T) {
to_print.print();
to_print.print();
}
fn main() {
// Мономорфированная версия функции для каждого типа: статический подход.
print_it_twice(&0i32); // 0, 0
print_it_twice(&10i64); // 10, 10
// Тут собираются виртуальные таблицы для i32::Print и i64::Print.
let data: [Box<Print>; 2] = [Box::new(20i32), Box::new(30i64)];
for val in &data {
// Динамический подход: мономорфирована единственная виртуальная версия.
// Гадкий каст &Box<Print> к &Print вручную, потому что
// дженерики и авто-разыменование указателей архитектурно дружат так себе...
print_it_twice(&**val); // 20, 20, 30, 30
}
}
Прикольно. Не то чтоб идеально, но прикольно. К сожалению, здесь нету impl Trait for Box<Trait> — мне кажется, оно тут будет плохо взаимодействовать с impl<T: Trait> Trait for Box<T>, но я его еще серьезно не копал. Может, хватит и того, что Т у нас Sized?
Ассоциированные типы
Какие последствия того, что мы определяем нечто как обобщенное по некоторому типу? И что мы вообще хотим этим выразить? Собственно, и выражение, и последствие здесь одно, мы хотим определить, как работать с типом, который нам подсунут. По факту — у нас тип это входящий параметр. struct Foo<T> говорит, что мы можем собрать полноценный тип только из Foo и Т вместе, Foo сам по себе незавершенный. Если у вас страсть к специальным терминам, вы можете сказать, что Foo — конструктор типов — функция, принимающая тип как аргумент, и возвращающая тип как результат. То есть тип высшего порядка.
Далее. trait Eat<T>, или обобщенный трейт Eat — что он нам о себе скажет? Как минимум то, что его можно реализовать более одного раза. А еще, что для каждой его реализации надо иметь в виду некий сторонний тип Т, без него Eat неполноценен. Отсюда же вывод, что нельзя говорить о том, что Eat где-то реализован, реализованным может быть только Eat<T>, где Т, в свою очередь, определяется пользователем.
Ну ок, а мы тут при чем? Это можно показать на примере итераторов:
trait Iterator<T> {
fn next(&mut self) -> Option<T>;
}
/// Итератор, получающий элементы из вектора, по принципу стека
struct StackIter<T> {
data: Vec<T>,
}
// Итератор диапазона [min, max)
struct RangeIter {
min: u32,
max: u32,
}
impl<T> Iterator<T> for StackIter<T> {
fn next(&mut self) -> Option<T> {
self.data.pop()
}
}
impl Iterator<u32> for RangeIter {
fn next(&mut self) -> Option<u32> {
if self.min >= self.max {
None
} else {
let res = Some(self.min);
self.min += 1;
res
}
}
}
Пока нормально. Мы можем написать и общую, и частную реализации интерфейса. А дальше пошли чудеса — каждый реальный тип может реализовать Iterator только один раз. StackIter<Cat> реализует только Iterator<Cat>, ему незачем реализовывать Iterator<Dog>. По факту ему и разрешать реализовывать что-либо еще нельзя, иначе пользователь будет озадачен, объект какого из реализованных типов ему вернет Iterator::next()!
Получается, мы совершенно не в восторге, что Т как входящий тип для Iterator — это тот же входящий тип Т для StackIter. Тем не менее от этого никуда не деться, ведь мы как пользователь не можем хардкодить выдаваемые Iterator::next() типы. Эту информацию нам обязан выдавать тип, реализующий итератор!
В этот не слишком радостный момент пора познакомиться с ассоциированными типами.
Ассоциированные типы позволят нам указать, что реализация трейта должна указать дополнительные типы, ассоциированные с определенной реализацией. То есть сказать, что трейту требуются конкретные типы точно так же, как и конкретные функции. Вот вам соответствующим образом переделанный Iterator:
trait Iterator {
// У каждого итератора есть дополнительный внутренний тип,
// который должен быть определен пользователем
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
/// Итератор, получающий элементы из вектора, по принципу стека
struct StackIter<T> {
data: Vec<T>,
}
// Итератор диапазона [min, max)
struct RangeIter {
min: u32,
max: u32,
}
impl<T> Iterator for StackIter<T> {
// Ассоциированные типы не запрещено
// получить из типа-аргумента
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.data.pop()
}
}
impl Iterator for RangeIter {
// Или указать конкретно
type Item = u32;
fn next(&mut self) -> Option<Self::Item> {
if self.min >= self.max {
None
} else {
let res = Some(self.min);
self.min += 1;
res
}
}
}
И вот теперь нам нельзя имплементить Iterator несколько раз. Хотя ассоциированные типы могут быть обобщенными, их нельзя определить отдельно от других типов, как, например, вот тут:
impl<T> Iterator for RangeIter {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
unimplemented!()
}
}
<anon>:3:6: 3:7 error: the type parameter `T` is not constrained by the impl trait, self type, or predicates [E0207]
<anon>:3 impl<T> Iterator for RangeIter {
^
Поэтому ассоциированныым типам можно вправе дать название "исходящие типы".
Так, мы ограничили реализацию трейта ассоциированными типами, что это нам дает еще? Теперь нам можно выразить что-нибудь эдакое, недоступное ранее?
А то!
Вот машина состояний (наш слегка подправленный итератор):
trait StateMachine {
type NextState: StateMachine;
fn step(self) -> Option<Self::NextState>;
}
Итак, это тип, экземпляр которого мы можем попросить совершить step(), результатом которого будет превращение его в другой экземпляр этого же типа. Выразим его дженериком...:
trait StateMachine<NextStep: StateMachine<АААА_БЛИН_ЧТО_ТУТ_ЗА_ТИП>> {
fn step(self) -> Option<NextState>;
}
… и радостно получаем бесконечною рекурсию типов. Так как обобщенный тип дженерика — входящий, его должен определить пользователь трейта. В данном случае этот тип — сам трейт. Тем не менее, можно обойтись и без ассоциированных типов — у нас же есть виртуализация!
trait StateMachine {
// Box чудесен! self у нас будет Box<Self>.
// С Rc<Self> это уже не работает, потому что *Box чудесен*.
// (да нет тут никаких чудес, это принципиально разные инструменты - прим.пер.)
fn step(self: Box<Self>) -> Option<Box<StateMachine>>;
}
Здесь мы нарисовали нашу старую машину состояний, только без ассоциированных типов. Оригинальный экземпляр мы поглощаем (self у нас не заимствованный, то есть после завершения step() его использовать уже нельзя — прим.пер.), на выходе получаем что-то, реализующее машину состояний. Но чтобы это работало, нам нужно ограничить возможности использования всех машин состояний только их реализациями в куче, а еще мы теряем сведения о конкретном типе машины после первого же вызова step(). С ассоциативными типами ни первого, ни второго не происходит.
А, вот еще: трейт-объекты не работают с ассоциированными типами. По той же причине, почему они не работают с Self по значению — неизвестен конкретный реализующий тип. Способ заставить их подружиться — указать все конкретные типы. Box<Iterator> выругается, а Box<Iterator<Item=u32>> вполне себе заведется.
Условия «Where»
Наш старый пример:
impl<T> Generic<T> {
// Смотрите, куда мы пришли: инвертировали вызов `equal` относительно того,
// кто вызывает, а кто аргумент.
// (`x == y` здесь все еще равен `y == x`). А вот как нам развернуть аргументы типов,
// чтоб получить `T: Equal<U>` чтобы это починить? Мы не можем это сделать одновременно
// с определением `T`, потому что `U` еще не существует!
// Об этом позже.
fn my_equal<U: Equal<T>>(&self, other: &Generic<U>) -> bool {
other.data.equal(&self.data)
}
}
Теперь же мы умеем в ассоциированные типы — чем нам это поможет?
// Новой задачкой: ассоциированные типы вроде как позволяют
// избежать определения "исходящих типов", но нам же их все равно
// определять в сигнатуре, если мы прикрепляем Item!
fn min<I: Iterator<Item = T>, T: Ord>(mut iter: I) -> Option<I::Item> {
if let Some(first) = iter.next() {
let mut min = first;
for x in iter {
if x < min {
min = x;
}
}
Some(min)
} else {
None
}
}
И тут решение есть — условие «Where».
impl<T> Generic<T> {
fn my_equal<U>(&self, other: &Generic<U>) -> bool
where T: Equal<U>
{
self.data.equal(&other.data)
}
}
fn min<I>(mut iter: I) -> Option<I::Item>
where I: Iterator,
I::Item: Ord,
{
if let Some(first) = iter.next() {
let mut min = first;
for x in iter {
if x < min {
min = x;
}
}
Some(min)
} else {
None
}
}
Where позволяет ограничивать трейты произвольными типами. Ни больше, ни меньше. Это более гибко, чем инлайнить тип в сигнатуре. Where можно совать в реализацию трейта, определения трейта, функции, структуры, перечисления — грубо говоря, везде, где есть обобщенные типы.
Кроме того, что некоторые развеселые определения могут с ходу вынести (прочтите кто-нибудь impl Send for MyReference<T> where &T: Send с первого раза), у Where взаимодействие с трейт-объектами также сопровождается некоторыми спецэффектами. Помните, я говорил, что трейт, подразумевающий обращение к самому себе по значению, использовать в трейт-объекте нельзя? Короче, спецэффектами можно это поправить:
trait Print {
fn print(&self);
// `where Self: Sized` значит, что
// функция для трейт-объектов недоступна. Значит,
// можно использовать Print как трейт-объект!
fn copy(&self) -> Self where Self: Sized;
}
impl Print for u32 {
fn print(&self) { println!("{}", self); }
fn copy(&self) -> Self { *self }
}
fn main() {
let x: Box<Print> = Box::new(0u32);
x.print();
}
Ограничения трейтов высшего порядка
Если к этому моменту крыша у вас еще не поехала — вам просто повезло, так как следующий раздел шансов ей не оставляет. Тут будет происходить и описываться откровенно мутное болото, удовольствие от ковыряния в котором могут получить только отъявленные фанатики накрученных систем типов.
Сейчас мы будем писать функции высших порядков, что, в свою очередь, есть «функции, работающие с функциями». Прекрасный и всем известный пример — map():
let x: Option<u32> = Some(0);
let y: Option<bool> = x.map(|v| v > 5);
Пятью чашками кофе назад вы могли наткнуться на ненавязчивый комментарий, что Rust это делает через трейты. «Ааа, ооо, чудесные трейты, было дело, да», скажете вы, и немедля добавите «но это же просто трейты!». Вот они: Fn, FnMut и FnOnce. Сейчас для нас их отличия несущественны, и мы просто будем брать из них тот, который красивее ложится на то, что мы хотим объяснить.
Fn вообще-то не трейт, а семейство трейтов. Fn(A, B) -> C, в свою очередь, уже таки трейт. Чем-то похож на дженерик. Хотя даже так: это дженерик и есть. Fn(A, B) -> C — синтаксический сахар поверх обобщенного трейта, который вам напрямую недоступен (для версии 1.7 как минимум). Компилятор его разворачивает в Fn<(A, B), Output=C>. Отчетливо видны входящие типы, исходящие типы, все прям как мы рассказываем!
Исходя их этого, замыкание из примера map() реализует FnOnce(u32) -> bool. Пока совсем не страшно. Пока что.
fn get_first(input: &(u32, i32)) -> &u32 { &input.0 }
fn main() {
let a = (0, 1);
let b = (2, 3);
let x = Some(&a);
let y = Some(&b);
println!("{}", x.map(get_first).unwrap());
println!("{}", y.map(get_first).unwrap());
}
Какой, собственно, трейт get_first здесь реализует? Похоже на Fn(&(u32, i32)) -> &u32? Черта с два.
trait MyFn<Input> {
type Output;
}
// Тип-заглушка; нам пока наплевать
// на то, что у него может быть внутри.
struct Thunk;
impl MyFn<&(u32, i32)> for Thunk {
type Output = &u32;
}
<anon>:9:11: 9:22 error: missing lifetime specifier [E0106]
<anon>:9 impl MyFn<&(u32, i32)> for Thunk {
^~~~~~~~~~~
<anon>:9:11: 9:22 help: see the detailed explanation for E0106
<anon>:10:19: 10:23 error: missing lifetime specifier [E0106]
<anon>:10 type Output = &u32;
^~~~
<anon>:10:19: 10:23 help: see the detailed explanation for E0106
error: aborting due to 2 previous errors
Заимствования без времен жизни — ребус в чистом виде. Железное правило: если заимствование это часть типа — приложи время жизни! Другое дело, что Rust достаточно мудр, чтобы не напрягать нас этом правилом в 99% случаев, просто подставляя дефолтное время жизни (еще один термин, который нет особого смысла переводить дословно, им и так все пользуются — прим.пер.).
Получается, get_first у нас на самом деле вот такой монстр:
fn get_first<'a>(input: &'a (u32, i32)) -> &'a u32 { &input.0 }
Еще одно правило: заимствования в сигнатуре функции значит, что функция обобщена относительно них. Соответственно, реализовывать надо обобщенный трейт:
trait MyFn<Input> {
type Output;
}
struct Thunk;
impl<'a> MyFn<&'a (u32, i32)> for Thunk {
type Output = &'a u32;
}
Компилируется. А я вам теперь говорю обратное: нужный нам трейт — Fn(&(u32, i32)) -> &u32. Там, выше, я вам приврал. Как и почему, сейчас покажу на примере фильтра для итератора:
/// Фильтр для итератора
struct Filter<I, F> {
iter: I,
pred: F,
}
/// Клеим фильтр
fn filter<I, F>(iter: I, pred: F) -> Filter<I, F> {
Filter { iter: iter, pred: pred }
}
impl<I, F> Iterator for Filter<I, F>
where I: Iterator,
F: Fn(&I::Item) -> bool, // Ой! Заимствование есть - времени жизни нет! Сколько живет аргумент?
{
type Item = I::Item;
fn next(&mut self) -> Option<I::Item> {
while let Some(val) = self.iter.next() {
if (self.pred)(&val) {
return Some(val);
}
}
None
}
}
fn main() {
let x = vec![1, 2, 3, 4, 5];
for v in filter(x.into_iter(), |v: &i32| *v % 2 == 0) {
println!("{}", v); // 2, 4
}
}
Все страньше и страньше. Нам надо, чтоб pred() работал с временем жизни &val. Увы, явно назвать это время жизни мы не способны, даже если мы повесим условие Where на next() (вообще нам Iterator так не позволит). Данное время жизни просто появляется и исчезает внутри функции, мы не можем его ни выделить, ни назвать. И нам еще и надо, чтоб pred() работал с тем-чье-имя-нельзя-назвать! Полезем в лоб — потребуем от pred() работы со всеми временами жизни. Внезапно:
F: Fn(&I::Item) -> bool
это сахар для
for<'a> F: Fn(&I::Item) -> bool
То есть for<'a> читается почти дословно: для всех 'a (for all 'a)!
Назовем это ограничением трейта высшего порядка (higher rank trait bound (HRTB)). Вам с ними работать не надо, разве что вас уже всосало в какое-нибудь болото со сложными структурами типов. Обычно HTRB показываются при работе с функциональными трейтами, да и там накрыты синтаксическим сахаром, то есть часто прозрачны для пользователя. Еще на данный момент ограничения трейтов высших порядков работают только с временами жизни.
Типы высших порядков
Уже было упомянуто ранее, что дженерики по своей сути способ выражения типов высших порядков. Можно представить Vec как конструктор типа вида (T) -> Vec<T>. Мы можем подразумевать этот конструктор типа при написании обобщенного кода, вроде impl<T> Trait for Vec<T> или fn make_vec<T>() -> Vec<T>. И мы также помним про ограничение — говоря о конструкторе типа, мы обязаны этот исходящий тип указать. То есть, обобщать поверх самих конструкторов мы не можем.
Например, нам нужна структура данных, которая использует считающие ссылки указатели (reference-counted pointers). Rust предлагает два варианта, Rc и Arc. Rc производительный, Arc потокобезопасный. Допустим, с точки зрения имплементации в нашей структуре эти типы полностью взаимозаменяемы. А вот для пользователей структуры очень важно, какой именно указатель-счетчик используется.
Конечно же мы хотим, чтоб наша структура была обобщена относительно Rc и Arc. В идеале мы бы написали эдакое:
// Это не код, а полная ботва. Он не взлетит!
/// Связный список со счетчиком ссылок.
/// RefCount может быть Rc или Arc, как вам того захочется.
struct Node<RefCount: RcLike, T> {
elem: T,
next: Option<RefCount<Node<RefCount, T>>>,
}
Блин, нам так нельзя! Пользователь не может отправить сюда Rc или Arc так, чтобы мы этого не знали. Типы-то обобщенные, их надо завершить, подсунув тип-аргумент, вроде Rc<SomeType>. Можно было бы придумать трейт для множества Rc<Node<T>>, но это менее удобоваримо, чем работа напрямую с Rc и Arc. Еще это можно использовать в дженериках, возвращающих заимствование, вроде такого:
/// Итератор, не позволяющий вызывать `next` снова,
/// пока последний используемый элемент не отпущен.
trait RefIterator {
type Item;
fn next(&mut self) -> &mut T
}
что, как мы уже знаем, просто сахар для
trait RefIterator {
type Item;
fn next<'a>(&'a mut self) -> &'a mut Self::Item;
}
Раздражающим здесь пунктом является факт, что мы вхардкодили заимствование как крайний объект, торчащий из типа наружу, то есть нам Self::Item надо где-то хранить. С удовольствием решили бы данный вопрос, выбросив это заимствование:
trait RefIterator {
type Item;
fn next<'a>(&'a mut self) -> Self::Item<'a>;
}
Вроде еще красивей и обобщенней, ведь можно написать Self::Item = &mut T, и теоретически мы довольны. Пока не замечаем, что Item тихонько превратился в конструктор типов, а их обобщать нельзя!
Хотя если хорошенько попросить компилятор, то можно. Но я вам этого не говорил. Не палите, пожалуйста, контору.
Ключевое знание тут — понимание того, что у трейта есть входящие и исходящие типы, то есть трейт это функция поверх типов. Вот смотрите:
trait TypeToType<Input> {
type Output;
}
Конструктор типов же! Пошли имплементить обобщенный итератор счетчиков ссылок RefIter:
use std::marker::PhantomData;
use std::mem;
use std::cmp;
// Тип, который RefIter нам будет отдавать
struct MyType<'a> {
slice: &'a mut [u8],
index: usize,
}
// Преобразование времени жизни в тип:
trait LifetimeToType<'a> {
type Output;
}
// Заглушки-конструкторы типов,
// с которыми мы будем работать
/// &'* T
struct Ref_<T>(PhantomData<T>);
/// &'* mut T
struct RefMut_<T>(PhantomData<T>);
/// MyType<*>
struct MyType_;
// Опишем маппинг типов, который происходит в наших конструкторах
impl<'a, T: 'a> LifetimeToType<'a> for Ref_<T> {
type Output = &'a T;
}
impl<'a, T: 'a> LifetimeToType<'a> for RefMut_<T> {
type Output = &'a mut T;
}
impl<'a> LifetimeToType<'a> for MyType_ {
type Output = MyType<'a>;
}
// А это трейт, который надо реализовать!
// `Self::TypeCtor as LifetimeToType<'a>>::Output`
// - результат применения 'a к TypeCtor.
//
// Вот, кстати: <X as Trait>::AssociatedItem это "развернутая турбо-рыба",
// чтобы четко ссылаться на ассоциированные части.
//
// Примечание: Не думаю, что тут можно использовать HRTB,
// этому мешает требование `T: 'a`.
// `for<'a> Self::TypeCtor: LifetimeToType<'a>` требуют соблюдение
// `&'a T` для всех возможных `'a`,
// но это работает только в случае `T: 'static`!
// Лучше используем условие "where" для `next`.
trait RefIterator {
type TypeCtor;
fn next<'a>(&'a mut self)
-> Option<<Self::TypeCtor as LifetimeToType<'a>>::Output>
where Self::TypeCtor: LifetimeToType<'a>;
}
// Итераторы!
struct Iter<'a, T: 'a> {
slice: &'a [T],
}
struct IterMut<'a, T: 'a> {
slice: &'a mut [T],
}
struct MyIter<'a> {
slice: &'a mut [u8],
}
// FIXME: https://github.com/rust-lang/rust/issues/31580
// Компилятор падает на сборке сложных типов, где падать не должен.
// Его можно привести в чувство вот такими костылями
// (которые все равно ничего не делают, только расшифровывают типы)
fn _hack_project_ref<'a, T>(v: &'a T) -> <Ref_<T> as LifetimeToType<'a>>::Output { v }
fn _hack_project_ref_mut<'a, T>(v: &'a mut T) -> <RefMut_<T> as LifetimeToType<'a>>::Output { v }
fn _hack_project_my_type<'a>(v: MyType<'a>) -> <MyType_ as LifetimeToType<'a>>::Output { v }
// Реализации (тоже особо нечего комментировать)
impl<'x, T> RefIterator for Iter<'x, T> {
type TypeCtor = Ref_<T>;
fn next<'a>(&'a mut self)
-> Option<<Self::TypeCtor as LifetimeToType<'a>>::Output>
where Self::TypeCtor: LifetimeToType<'a>
{
if self.slice.is_empty() {
None
} else {
let (l, r) = self.slice.split_at(1);
self.slice = r;
Some(_hack_project_ref(&l[0]))
}
}
}
impl<'x, T> RefIterator for IterMut<'x, T> {
type TypeCtor = RefMut_<T>;
fn next<'a>(&'a mut self)
-> Option<<Self::TypeCtor as LifetimeToType<'a>>::Output>
where Self::TypeCtor: LifetimeToType<'a>
{
if self.slice.is_empty() {
None
} else {
let (l, r) = mem::replace(&mut self.slice, &mut []).split_at_mut(1);
self.slice = r;
Some(_hack_project_ref_mut(&mut l[0]))
}
}
}
impl<'x> RefIterator for MyIter<'x> {
type TypeCtor = MyType_;
fn next<'a>(&'a mut self)
-> Option<<Self::TypeCtor as LifetimeToType<'a>>::Output>
where Self::TypeCtor: LifetimeToType<'a>
{
if self.slice.is_empty() {
None
} else {
let split = cmp::min(self.slice.len(), 5);
let (l, r) = mem::replace(&mut self.slice, &mut []).split_at_mut(split);
self.slice = r;
let my_type = MyType { slice: l, index: split / 2 };
Some(_hack_project_my_type(my_type))
}
}
}
// Пользуемся!
fn main() {
let mut data: [u8; 12] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
{
let mut iter = Iter { slice: &data };
while let Some(v) = iter.next() {
println!("{:?}", v);
}
}
{
let mut iter = IterMut { slice: &mut data };
while let Some(v) = iter.next() {
println!("{:?}", v);
}
}
{
let mut iter = MyIter { slice: &mut data };
while let Some(v) = iter.next() {
println!("{:?} {}", v.slice, v.index);
}
}
}
Не уверен, что у меня получится расшифровать происходящее выше, да и не уверен, что это необходимо — обычная последовательность действий, описанных здесь ранее. И вообще, оно нам поможет разобраться с Rc / Arc?
А вот и да!
use std::rc::Rc;
use std::sync::Arc;
use std::ops::Deref;
// Kind: Type -> Type
trait RcLike<T> {
type Output;
fn new(data: T) -> Self::Output;
}
// Заглушки
struct Rc_;
struct Arc_;
impl<T> RcLike<T> for Rc_ {
type Output = Rc<T>;
fn new(data: T) -> Self::Output {
Rc::new(data)
}
}
impl<T> RcLike<T> for Arc_ {
type Output = Arc<T>;
fn new(data: T) -> Self::Output {
Arc::new(data)
}
}
struct Node<Ref, T>
// Условие `where` нам еще вылезет боком (детальней - ниже)
where Ref: RcLike<Node<Ref, T>>,
{
elem: T,
// basically: Option<Rc<Node<Rc_, T>>
next: Option<<Ref as RcLike<Node<Ref, T>>>::Output>
}
struct List<Ref, T>
where Ref: RcLike<Node<Ref, T>>,
{
head: Option<<Ref as RcLike<Node<Ref, T>>>::Output>
}
impl<Ref, T, RefNode> List<Ref, T>
where Ref: RcLike<Node<Ref, T>, Output=RefNode>,
RefNode: Deref<Target=Node<Ref, T>>,
RefNode: Clone,
{
fn new() -> Self {
List {
head: None
}
}
fn push(&self, elem: T) -> Self {
List {
head: Some(Ref::new(Node {
elem: elem,
next: self.head.clone(),
}))
}
}
fn tail(&self) -> Self {
List {
head: self.head.as_ref().and_then(|head| head.next.clone())
}
}
}
fn main() {
// Использование (мы притворяемся, что правильно реализовали итераторы и геттеры)
let list: List<Rc_, u32> = List::new().push(0).push(1).push(2).tail();
println!("{}", list.head.unwrap().elem); // 1
let list: List<Arc_, u32> = List::new().push(10).push(11).push(12).tail();
println!("{}", list.head.unwrap().elem); // 11
}
У нас почти получилось, но мешает вышеупомянутое условие where Ref: RcLike<Node<Ref, T>>. Это дыра в нашей абстракции. С одной стороны пользователям нашей структуры совершенно не нужно знать про Node, с другой стороны мы вынуждены их там упомянуть. А хотелось бы получить возможность заявить, что Ref это RcLike для чего угодно. Технически это звучит как where for<T> Ref: RcLike<T>. Это позволит нам спрятать необязательные к распространению детали использования Ref.
Увы. Как уже было сказано, ограничения трейтов высшего порядка не работают ни с чем, кроме времен жизни. Может их когда-нибудь докрутят полноценно, или хотя бы для типов, тогда можно смело решить проблему создания типов высших порядков! Но не сегодня.
Вообще, я надеюсь, вы уже понимаете, что разговоры о конструкторах типов, даже в том ограниченном виде, который нужен нам сейчас, в среде разработчиков Rust вызывают приступы острой головной боли. Хотя в идеале, типы высших порядков должны поддерживаться языком на уровне синтаксиса.
Обобщаемость
Вот вы задумывались когда-нибудь, что два экземпляра одного и того же типа фактически взаимозаменяемы? Чтобы если у нас было два Виджета, и мы их поменяли местами, никто и усом не повел. В большинстве случаев это весьма приветствуется. А что если запретить экземплярам одного типа взаимозаменяться?
Массивы, например. Когда мы перебираем массив, это обычно делается для получения его элементов. Ну да, данная задача требует от нас предоставить соответствующие итераторы для различных потребностей доступа к элементам: Iter, IterMut и IntoIter. Не было бы удобней, если бы итератор говорил нам, куда смотреть, а мы уже сами решали, как там хозяйничать?
Теоретически это возможно, если у вашего массива есть собственный итератор по индексам. 0, 1, 2, ..., len — 1. Бегай себе по индексам, делов-то, все довольны. Только в этом случае надежность итератора страдает. Обычно же от итераторов ждут как раз уверенности, что каждый элемент будет пройден хотя бы единожды, а еще они гарантированно не падают.
Доступ же по индексам ломает всё вышеописанное. Индексы можно подменить, можно поменять сам массив, делая индексы невалидными, можно, наконец, нечаянно натянуть индексы одного массива на другой. Но все это решаемо, с разной степенью приложенных усилий. Против подмены индексов — тип-обертка над ними, чтоб пользователю были недоступны реальные их значения. Против инвалидации индексов отлично поможет привязка их к времени жизни их массива.
А с подменой самого массива как? У меня два массива, типы их индексов идентичны и де-факто взаимозаменяемы, а мы этого не хотим. Способ получить нами (не)желаемое носит название обобщаемость. В основе обобщаемости лежит идея обладания разных экземпляров одного и того же типа разными ассоциированными типами. Значение ассоциированного типа зависит от экземпляра типа, то есть.
Я устал, ужасно устал. Мы тут все равно почти у финиша, так что я просто вам скопирую сюда демонстрацию вышеописанного, которую написал какое-то время назад. Все равно все есть в комментариях, читайте их.
// Эта программа демонстрирует якобы небезопасную индексацию,
// когда слайсы генерируют валидные индексы и "подписывают" их
// неизменным временем жизни. Данные индексы нельзя ни использовать с других слайсом,
// ни хранить их дольше, чем живет создавший их массив.
// (можете попробовать прикрутить этот подход к Vec, а потом подергать эти индексы после заполнения вектора).
//
// Дизайн здесь можно назвать "итератор без одного шага", предоставляющий
// больше возможностей пользователю. Вместо ссылок на элементы массива
// мы получаем индексы, из которых мы можем либо получить те же ссылки,
// либо использовать индексы без ссылок (послайсить массив?). Обычно такие операции
// проверяются в рантайме, чтоб не выйти за границы массива, но так как
// сам массив ответственен за рожденные им индексы, им можно доверять и так.
// Гипотетически это позволяет улучшить композиционность. С этой техникой
// можно проверить индексацию всего один раз (let idx = arr.validate(idx)).
//
// Главный недостаток этого подхода - необходимо замыкание для
// создания окружения, куда привязаны все подписи, серьезно усложняя
// любую логику общения с внешним миром (вроде moving values in/out и try!).
// В принципе, компилятор можно обучить избегать необходимости в замыкании
// в подобных случаях, ЕМНИП, хотя как это сделать, вопрос отдельный.
// Также ожидаемо появление обертки вокруг нужной структуры для предоставления
// требуемого API (опять же, касательно применения к Vec -- не допускать прямых вызовов `push` и `pop`.
// Тот же самый принцип используется в итераторах.
//
// Еще эта штука озадачивает компилятор, заставляя его плеваться рандомными ошибками обработки времен жизни,
// потому что мы используем слегка непривычную семантику, которая выбрасывает борроучекер за борт здравого смысла
//
// Впервые эта техника была реализована gereeter для безопасной сборки
// путей поиска для BTreeMap. Смотри ST Monad из Haskell для понимания дизайна.
//
// Этот пример не блещет образцовой обобщенностью, потому что я замотался
// воевать с ограничениями поддержки &[T] и &mut [T].
fn main() {
use indexing::indices;
let arr1: &[u32] = &[1, 2, 3, 4, 5];
let arr2: &[u32] = &[10, 20, 30];
// одновременная итерация (самое жесткое, что можно сделать с итератором)
indices(arr1, |arr1, it1| {
indices(arr2, move |arr2, it2| {
for (i, j) in it1.zip(it2) {
println!("{} {}", arr1.get(i), arr2.get(j));
// should be invalid to idx wrong source
// println!("{} ", arr2.get(i));
// println!("{} ", arr1.get(j));
}
});
});
// можно верить индексам, пока они остаются внутри замыкания
let _a = indices(arr1, |arr, mut it| {
let a = it.next().unwrap();
let b = it.next_back().unwrap();
println!("{} {}", arr.get(a), arr.get(b));
// a // should be invalid to return an index
});
// вынимаем и ссылки на элементы, не только индексы
let (x, y) = indices(arr1, |arr, mut it| {
let a = it.next().unwrap();
let b = it.next_back().unwrap();
(arr.get(a), arr.get(b))
});
println!("{} {}", x, y);
// Упражнение читателю: воспроизвести мультииндексную изменяемую индексацию!?
// (подсказка: с текущим дизайном ничего у вас не выйдет)
}
mod indexing {
use std::marker::PhantomData;
use std::ops::Deref;
use std::iter::DoubleEndedIterator;
// Cell<T> неизменна для T; потому Cell<&'id _> делает `id` неизменным.
// Это означает, что движку вывода не разрешено кромсать или увеличивать
// 'id для "починки" заимствований.
type Id<'id> = PhantomData<::std::cell::Cell<&'id mut ()>>;
pub struct Indexer<'id, Array> {
_id: Id<'id>,
arr: Array,
}
pub struct Indices<'id> {
_id: Id<'id>,
min: usize,
max: usize,
}
#[derive(Copy, Clone)]
pub struct Index<'id> {
_id: Id<'id>,
idx: usize,
}
impl<'id, 'a> Indexer<'id, &'a [u32]> {
pub fn get(&self, idx: Index<'id>) -> &'a u32 {
unsafe {
self.arr.get_unchecked(idx.idx)
}
}
}
impl<'id> Iterator for Indices<'id> {
type Item = Index<'id>;
fn next(&mut self) -> Option<Self::Item> {
if self.min != self.max {
self.min += 1;
Some(Index { _id: PhantomData, idx: self.min - 1 })
} else {
None
}
}
}
impl<'id> DoubleEndedIterator for Indices<'id> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.min != self.max {
self.max -= 1;
Some(Index { _id: PhantomData, idx: self.max })
} else {
None
}
}
}
pub fn indices<Array, F, Out>(arr: Array, f: F) -> Out
where F: for<'id> FnOnce(Indexer<'id, Array>, Indices<'id>) -> Out,
Array: Deref<Target = [u32]>,
{
// Тут все самое вкусное. Мы приклеиваем индексатор и индексы
// к одному и тому же неизменному времени жизни (условие, установленное
// определением F). Из этого получаем, что каждый вызов `indices` производит
// уникальную подпись, которая видна одновременно только этим двум вещам.
//
// Внутри этой функции обработчик заимствований может выбрать буквально любое
// время жизни, в том числе и `'static`, но нам нет дела до того, что он делает внутри
// функции *this*. Нам его надо надуть только для области видимости вызывающего его кода.
// Так как в обработчике нет межпроцедурного анализа, ему видно лишь то, что
// каждый вызов данной функции производит значения с неким мутным временем
// жизни, и обработчик бессилен их систематизировать.
//
// В принципе если обучить его межпроцедурному анализу,
// этот дизайн прикажет долго жить, но его можно быстро оживить, привязав время жизни к кишкам функции.
// Я совершенно уверен, что такого варианта бояться не стоит,
// ибо никто никогда это в борроучекер не воткнет.
let len = arr.len();
let indexer = Indexer { _id: PhantomData, arr: arr };
let indices = Indices { _id: PhantomData, min: 0, max: len };
f(indexer, indices)
}
}
Мухаха, не правда ли, все просто? Да нет, чистейший ад. И это все умопомрачительно небезопасно и хрупко. По сравнению с этим претензия Rust против использования Unsafe звучит как вежливая просьба не ругаться матом в падающем здании — вся стабильность системы зависит от филигранной подгонки всех типов друг к другу в любых, даже самых критичных условиях, при этом строка, помеченная unsafe — единственная на все полотно.
Зависимость программы от обобщаемости — это безопасно не более чем курение в пороховом складе, потому я очень ожидаю увидеть ее непосредственную поддержку в Rust, вместо собирания ее по крупицам HTRB из малоизвестных закоулков существующего синтаксиса.
И вообще, с меня хватит. Больше нет сил что либо писать. Все и так затянулось дальше некуда. Прошу меня простить. Очень прошу.
Автор: snuk182
