Купа способів переиспользовать код у Rust

Я знайшов цю статті авторства 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() {
нехай x = try!(File::open("Привіт"));
}

<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 як щось, що потрібно збирати і запускати кожен раз при збірці пакету. Очевидно, що їм дозволено копошитися в проекті як заманеться. Очікувано, що найкраще використовувати для недоступною макросів генерації коду.

Я б ще міг додати пару-трійку прикладів, але особливо не в темі цих можливостей, і абсолютно до них байдужий. Ну генерація коду, і добре. І взагалі, я цю статтю вже не перший день пишу і грунтовно подзадолбался (авторський капс прибраний — прим. пер.).

Перерахування

У точності описані раніше угруповання з тегами.
Найчастіше зустрічаються в особі Alt та 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 або C#, але іноді доводиться переступати межу. Трейты задумані архітектурно більш гнучкими. В С# і 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> :<T> {
fn new(data: T) -> :<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> :<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> :<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() {
// Статичне мономорфизированное використання
нехай 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 in val &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 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 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 in val &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> :<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> :<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);
нехай b = (2, 3);

нехай 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 Output type = &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() {
нехай 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>);
/// &'* T mut
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 для чого завгодно. Технічно це звучить як for where<T> Ref: RcLike<T>. Це дозволить нам заховати необов'язкові до поширення деталі використання Ref.

На жаль. Як вже було сказано, обмеження трейтов вищого порядку не працюють ні з чим, крім часів життя. Може їх коли-небудь докрутити повноцінно, або хоча б для типів, тоді можна сміливо вирішити проблему створення типів вищих порядків! Але не сьогодні.

Взагалі, я сподіваюся, ви вже розумієте, що розмови про конструкторів типів, навіть у тому обмеженому вигляді, який потрібен нам зараз, в середовищі розробників Rust викликають напади гострого головного болю. Хоча в ідеалі, типи вищих порядків повинні підтримуватися мовою на рівні синтаксису.

Обобщаемость

Ось ви замислювалися коли-небудь, що два примірники одного і того ж типу фактично взаємозамінні? Якщо у нас було два Віджета, і ми їх поміняли місцями, ніхто і вусом не повів. В більшості випадків це дуже вітається. А що якщо заборонити екземплярів одного типу взаємозамінюватися?

Масиви, наприклад. Коли ми перебираємо масив, це зазвичай робиться для отримання його елементів. Ну так, дана задача вимагає від нас надати відповідні ітератори для різних потреб доступу до елементів: Iter, IterMut та IntoIter. Не було б зручніше, якби ітератор говорив нам, куди дивитися, а ми вже самі вирішували, там господарювати?

Теоретично це можливо, якщо у вашого масиву є власний ітератор за індексами. 0, 1, 2, ..., len — 1. Бігай собі за індексами, делов-то, всі задоволені. Тільки в цьому випадку надійність ітератора страждає. Зазвичай же від ітераторів чекають як раз впевненості, що кожен елемент буде пройдено хоча б один раз, а ще вони гарантовано не падають.

Доступ же за індексами ламає все вищеописане. Індекси можна підмінити, можна поміняти сам масив, роблячи індекси невалидными, можна, нарешті, ненавмисно натягнути індекси одного масиву на інший. Але все це можна вирішити, з різним ступенем докладених зусиль. Проти підміни індексів — тип-обгортка над ними, щоб користувачу були недоступні реальні їх значення. Проти инвалидации індексів відмінно допоможе прив'язка їх до часу життя їх масиву.

А з підміною самого масиву як? У мене два масиву, їх типи індексів ідентичні і де-факто взаємозамінні, а ми цього не хочемо. Спосіб одержати нами (не)бажане носить назву обобщаемость (generativity). В основі обобщаемости лежить ідея володіння різних примірників одного й того ж типу різними асоційованими типами. Значення асоційованого типу залежить від примірника типу, тобто.

Я втомився, страшенно втомився. Ми тут все одно майже біля фінішу, так що я просто вам скопирую сюди демонстрацію вищеописаного, яку написав якийсь час назад. Все одно все є в коментарях, читайте їх.

// Ця програма демонструє нібито небезпечну індексацію,
// коли слайсы генерують валідні індекси і "підписують" 
// незмінним часом життя. Дані індекси можна використовувати з інших слайсом,
// ні зберігати їх довше, ніж живе створив їх масив.
// (можете спробувати прикрутити цей підхід до Vec, а потім посмикати ці індекси після заповнення вектора).
//
// Дизайн тут можна назвати "ітератор без одного кроку", що надає
// більше можливостей користувачеві. Замість посилань на елементи масиву
// ми отримуємо індекси, з яких ми можемо отримати ті ж посилання,
// або використовувати індекси без посилань (послайсить масив?). Зазвичай такі операції
// перевіряються в рантайме, щоб не вийти за межі масиву, але так як
// сам масив відповідальний за народжені їм індекси, їм можна довіряти і так.
// Гіпотетично це дозволяє поліпшити композиционность. З цією технікою
// можна перевірити індексацію всього один раз (let idx = arr.validate(idx)).
//
// Головний недолік цього підходу - необхідно для замикання
// створення оточення, куди прив'язані всі підписи, серйозно ускладнюючи
// будь-яку логіку спілкування з зовнішнім світом (зразок moving values in/out і try!).
// У принципі, компілятор можна навчити уникати необхідності в замиканні
// в подібних випадках, ЕМНІП, хоча як це зробити, питання окреме.
// Також очікувана поява обгортки навколо потрібної структури для надання 
// необхідного API (знову ж таки, щодо застосування до Vec -- не допускати прямих викликів `push` і `pop`.
// Той самий принцип використовується в итераторах.
//
// Ще ця штука спантеличує компілятор, змушуючи його плюватися рандомными помилками обробки часів життя,
// тому що ми використовуємо злегка незвичне семантику, яка викидає борроучекер за борт здорового глузду
//
// Вперше ця техніка була реалізована gereeter для безпечної складання
// шляхів пошуку для BTreeMap. Дивись ST Монада з 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));

// має бути невалидно для індексу чужого джерела
// 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 // повинно бути невалидно, щоб повернути індекс
});

// виймаємо і посилання на елементи, що не тільки індекси
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 Indices for<'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 Indices for<'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 з маловідомих закутків існуючого синтаксису.

І взагалі, з мене вистачить. Більше немає сил щось писати. Все і так затягнулося далі нікуди. Прошу мене пробачити. Дуже прошу.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.