[Из песочницы] Куча способов переиспользовать код в Rust11.08.2016 18:33

(статья написана о Rust 1.7 stable)

В системе типов Rust есть много всякого. Насколько я знаю, практически вся сложность этого всякого заключается в том, чтобы выразить программу в максимально обобщённом виде. Притом народ еще и требует большего! У меня всегда были проблемы с простым пониманием наиболее сложных вещей, потому этот пост скорее напоминалка самому себе. Но тем не менее, мне также нравится делать что-то, полезное другим, поэтому в данной статье также есть вещи, которые я вряд ли забуду, но о которых некоторые могут не знать.

В этой статье не будет исчерпывающего описания синтаксиса или общих деталей описываемых возможностей. Здесь рассказывается, почему происходит так или иначе, так как подобные вещи я всегда забываю. Если вы нашли эту статью в попытках выучить Rust полноценно, вам определенно стоит для начала ознакомиться с Книгой (оригинал вот — прим.пер.). В то же время я здесь буду уточнять некоторые произвольные теоретические аспекты того, что происходит.
Скорее всего, в этой статье полно ошибок, и она не должна претендовать на звание официального руководства. Это просто сборник того, что я накопал за неделю, пока искал новую работу.

Краткое описание принципов переиспользования кода

Желание использовать части кода более одного раза существует с тех самых ранних времен, когда самые первые вычислительные машины получили свой первый полезный результирующий бит. Определенно, я не имею ни малейшего представления о том, как в то прекрасное время выглядело переиспользование кода. Может, листики-шпаргалки? Или стопки перфокарт? Понятия не имею. Мне интересней, как это делается сейчас.

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

Технически эти принципы совершенно разные, тем не менее их часто приходится использовать вместе. В современных языках реализации этих принципов представлены достаточно широко: макросы, шаблоны, дженерики, наследование, указатели на функции, интерфейсы, перегрузка, группировка (union) и так далее. Однако, все это лишь семантическое разнообразие реализации трех основных принципов — мономорфизм, виртуализация, перечисление.

Мономорфизм

Семантическое ограничение мономорфизма в том, что его нельзя использовать (напрямую) в обработке нескольких различных типов данных одновременно. К примеру, я хочу построить очередь исполнения (job queue), принимающую различные задачи, и с ее помощью выполнить эти задачи в порядке поступления. При условии, что все задачи идентичны, все решается мономорфизмом довольно просто. Проблемы появляются, когда задачи различны — становится неясно, как это реализовать только мономорфизмом. Поэтому и название у него — мономорфизм. Абстракция над кодом, который делает только что-нибудь одно.

Распространенные примеры мономорфизма: шаблоны С++, макросы С, Go Generate, дженерики C#. Большинство из них работает при компиляции, кроме дженериков С#, которые мономорфируют во время выполнения кода. Все, что создается во время компиляции — шаблон. Мономорфизм жутко популярен как средство оптимизации при обычной (inline) и JIT-компиляции.

Виртуализация

Виртуализация позволяет коду работать с типами различного размера и структуры совершенно одинаково. Виртуализация функции позволяет ей иметь альтернативное поведение без необходимости копипаста. Пример с очередью исполнения, на котором мономорфизм ломает зубы, прекрасно решается виртуализацией — любая задача, которую необходимо выполнить, являет собой указатель на функцию, которую можно найти и запустить. Нужны данные отдельно для каждой задачи — без вопросов, добавляем еще указатель на данные, они подгрузятся вместе с функцией.

Главный недостаток виртуализации — она обычно влияет на производительность, вариативность кода выливается в частое выделение памяти в куче, прыжки по указателям (кэш негодует) и определение, с чем же именно мы в данный момент имеем дело.
Однако виртуализация может быть производительней мономорфирования! Каждый раз, когда функция дергается статически, компилятор способен заинлайнить ее, но делает это не всегда, так как, как уже было сказано, это перегружает и замусоривает бинарь. По тем же причинам выгодной бывает насильная виртуализация редко использующихся функций. К примеру, хендлерам исключений вовсе нежелательно постоянно запускаться, и лучше их виртуализировать, расчистив таким образом кэш инструкций для «безошибочной» ветки выполнения.

Распространенные примеры виртуализации: указатели на функцию и пустые (void) указатели в С, обратные вызовы, наследование, дженерики Java, прототипы Javascript. Заметьте, что во многих из этих примеров нет различия между виртуализацией данных и исполняемого кода. Например, если у меня указатель на Животное, за ним может стоять и Кот, и Пёс, и когда я прошу это Животное подать голос () — он же откуда-то знает, сказать ему «Гав» или «Мяу»?

Обычный способ реализации виртуализации для каждого объекта каждого типа — иерархия наследований для скрытого хранения указателей на разные куски имплементаций, которые могут понадобиться в процессе работы программы, называемая «vtable». Обычно в vtable хранят пачку указателей на функции (в том числе и на голос () из примера выше), но могут также и размер, выравнивание в памяти, конкретный тип объекта.

Перечисления

Например, наша очередь исполнения, реализованная перечислением, может определять три типа возможных задач, «Создать», «Изменить», «Удалить». Для использования, к примеру, «Создания», нужно всего лишь отправить очереди данные для Создания, помеченные тегом, соответствующим функции «Создать». Очередь видит тег, понимает из него, что от нее хотят и что лежит в данных, и запускает соответствующий код.

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

Нужно, однако, отметить, что если вариативность не использовать совсем, перечислимый тип серьезно разрастется, так как каждому объекту типа придется хранить информацию для наибольшего типа, который присутствует в перечислении. Для того, чтобы «Удалить», хватит и только имени, а вот «Создать» попросит имя, тип, автора, содержимое, и так далее, и даже если так случилось, что очередь используется в основном для «удаления», памяти она будет просить как для постоянного «создания».

Ну и разумеется, вам нужно знать наперед весь ассортимент возможностей, это главное ограничение перечислений. И мономорфизм, и виртуализацию можно расширить при необходимости в любой момент, чего не скажешь о перечислении — шаблон можно наложить на новый тип, класс можно унаследовать, а перечисление уже выжжено в коде намертво. Лучше не ковырять его с попытками обмануть и расширить — вы с большой долей вероятности сломаете код тех, кто уже его использует!

Поэтому данная стратегия отчасти невразумительна. Много у каких языков она встречается в виде enum, тем не менее ее использование серьезно ограничено, из-за невозможности ассоциировать данные отдельно для каждого варианта в перечислении. С позволяет определить вариант как группу из двух типов, но решение вопроса, что из этих типов данные, а что код, взваливается на пользователя перечисления. Во многих функциональных языках есть группы с тегами (tagged unions), которые являются объединением перечислений и группой в С, позволяющим приклеить произвольные данные к разным вариантам перечисления.

А как в Rust?

• Макросы (простой мономорфизм)
• Перечисления (полноценные, с данными!)
• Трейты (тут будет весело)

Макросы

Обычно макросы используют по двум причинам: расширить сам язык или сделать копию существующего кода. Первый местами открыто используется в стандартной библиотеке 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 }

// и далее больше сорока раз в том же духе...

Более важно, ИМХО, что макросы тут по сути метапрограммирование с динамической типизацией. Компилятор не проверяет, что тело макроса соответствует его сигнатуре, он генерирует согласно макросу код, получает что-то на выходе, и только тогда производит проверку, что приводит к типичной проблеме динамического программирования — поздняя привязка ошибок. Так мы можем получить аналог нетленного «undefined is not a function» для Rust:

macro_rules! make_struct {
    (name: ident) => {
        struct name {
            field: u32,
        }
    }
}

make_struct! { Foo }

:10:16: 10:19 error: no rules expected the token `Foo`
:10 make_struct! { Foo }
                         ^~~
playpen: application terminated with error code 101

struct name { field: u32 }

use std::fs::File;

fn main() {
    let x = try!(File::open("Hello"));
}

:5:8: 6:42 error: mismatched types:
 expected `()`,
    found `core::result::Result<_, _>`
(expected (),
    found enum `core::result::Result`) [E0308]
:5 return $ crate:: result:: Result:: Err (
:6 $ crate:: convert:: From:: from ( err ) ) } } )
:4:13: 4:38 note: in this expansion of try! (defined in )
:5:8: 6:42 help: see the detailed explanation for E0308

Стоит упомянуть: расширение синтаксиса и генерация кода

Расширения синтаксиса выглядят как макросы или аннотации, но у них есть способность просить компилятор выполнить произвольные действия для (в идеале) изменения дерева синтаксиса. Файлы build.rs понимаются пакетным менеджером Cargo как что-то, что нужно собирать и запускать каждый раз при сборке пакета. Очевидно, что им позволено копошиться в проекте как заблагорассудится. Ожидаемо, что лучше это использовать для недоступной макросам генерации кода.

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

Перечисления

Можно и свои перечисления написать. Вот, к примеру, вам надо код работы с сетью, который работает с 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),
    }
}

Трейты

А вообще трейты это интерфейсы. Нет, серьезно.

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());
}

В тему: согласованность

impl Trait for Type

impl Trait for Box

Забавно, что нарушения согласованности в стандартной библиотеке Rust (которая внутри склеена из нескольких непересекающихся частей) теоретически встречаются сплошь и рядом, поэтому некоторые трейты, имплементации и типы всплывают довольно в неожиданных местах. Еще более забавно, что тасовать так типы помогало не очень, в результате чего родился костыль #[fundamental], приказывающий компилятору закрывать на несогласованность глаза.

Дженерики

Так как же использовать трейты для повторного использования кода? Тут Rust нам дает выбор! Мы можем мономорфировать, можем виртуализировать. Мономорфизм в подавляющем большинстве случаев является выбором в стандартной библиотеке, а также в большей части кода, что я видел. Вероятно, это потому что мономорфизм в целом более эффективен, а также явно более обобщен. Тем не менее мономорфный интерфейс можно виртуализировать, что я чуть позже покажу.

Мономорфный интерфейс реализуется в Rust дженериками:

// Простая структура, для нужд сравнения.
struct Concrete {
    data: u32,
}

// Обобщенная структура. `<..>` указывает на обобщенный аргумент типа.
// Можно создать версию `Generic` для чего угодно, кроме
// `Concrete`, потому что он не дженерик и умеет только `u32`.
struct Generic {
    data: T,
}

// Обычная реализация
impl Concrete {
    fn new(data: u32) -> Concrete {
        Concrete { data: data }
    }

    fn is_big(&self) -> bool {
        self.data > 120
    }
}

// Реализация для конкретного класса Foo.
// Смотрите, это не специализация, в том смысле,
// что определенные здесь имена типов не конфликтуют
// с другими реализациями.
// (Говоря проще, тип аргумента дженерика это часть типа самого дженерика - прим.пер.)
impl Generic {
    fn is_big(&self) -> bool {
        self.data > 120
    }
}

// Реализуем для всех возможных T.
// "impl" здесь также Generic.
// Надеюсь, этот пример плюс предыдущий вместе
// убедительно показывают, зачем здесь еще один .
impl Generic {
    fn new(data: T) -> Generic {
        Generic { data: data }
    }

    fn get(&self) -> &T {
        &self.data
    }
}

// Обычный трейт.
trait Clone {
    fn clone(&self) -> Self;
}

// Обобщенный трейт.
// Определяет отношение к другому типу. В данном случае мы хотим
// сравнивать экземпляр нашего типа с экземпляром другого, который определен как Т.
// Дальше будет понятней.
trait Equal {
    fn equal(&self, other: &T) -> bool;
}

// Реализация обычного трейта
impl Clone for Concrete {
    fn clone(&self) -> Self {
        Concrete { data: self.data }
    }
}

// Конкретная реализация обобщенного трейта для конкретного типа
impl Equal for Concrete {
    fn equal(&self, other: &Concrete) -> bool {
        self.data == other.data
    }
}

// А, для чужих типов это тоже работает, мы ж владеем трейтом!
impl Clone for u32 {
    fn clone(&self) -> Self {
        *self
    }
}

impl Equal for u32 {
    fn equal(&self, other: &u32) -> Self {
        *self == *other
    }
}

// То же, с обобщенным типом!
impl Equal for u32 {
    fn equal(&self, other: &i32) -> Self {
        if *other < 0 {
            false
        } else {
            *self == *other as u32
        }
    }
}


// Обобщенная реализация обобщенного трейта для конкретного типа
impl> Equal for Concrete {
    fn equal(&self, other: &T) -> bool {
        other.equal(&self.data)
    }
}

// Обобщенная реализация конкретного трейта для обобщенного типа  
// Смотрите, нам надо, чтобы `T` реализовывал
// трейт `Clone`! Это *ограничение трейта* (trait bound).
// (некрасиво и малопонятно, да. варианты перевода приветствуются - прим.пер.)
impl Clone for Generic {
    fn clone(&self) -> Self {
        Generic { data: self.data.clone() }
    }
}

// Обобщенная реализация обобщенного трейта для обобщенного типа.
// У нас появляется второй тип-аргумент U.
impl, U> Equal> for Generic {
    fn equal(&self, other: &Generic) -> bool {
       self.equal(&other.data)
    }
}

// Ну да, отдельные функции тоже можно обобщить.
impl Concrete {
    fn my_equal>(&self, other: &T) -> bool {
        other.equal(&self.data)
    }
}

impl Generic {
    // Смотрите, куда мы пришли: инвертировали вызов `equal` относительно того,
    // кто вызывает, а кто аргумент.
    // (`x == y` здесь все еще равен `y == x`). А вот как нам развернуть аргументы типов,
    // чтоб получить `T: Equal` чтобы это починить? Мы не можем это сделать одновременно
    // с определением `T`, потому что `U` еще не существует!
    // Об этом позже.
    fn my_equal>(&self, other: &Generic) -> bool {
       other.data.equal(&self.data)
    }
}

// До
struct Generic { data: T }
impl Generic {
    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);
}

// Vec::new() функция обобщенная, определяет тип элементов вектора
// из типа переменной, куда присваивается вывод. Если он указан. Вот сейчас у нас
// точно `Vec`, но тип-аргумент нам неизвестен.
let mut x = Vec::new();

// Раз мы вставляем `u8` в `x`, значит тип вектора `Vec`
x.push(0u8);
x.push(10);
x.push(20);

// `collect` тоже функция обобщенная. Она производит все, что реализует
// `FromIterator`, обычно это коллекция Vec или VecDeque.
// Без четкого определения типа-аргумента непонятно, что же именно
// `collect` производит, в отличие от `Vec::new()`, из этой функции может
// вылезти совершенно что угодно

// Потому тип-аргумент для дженерика лучше определить явно.
let y: Vec = x.clone().into_iter().collect();

// Или сказать функции напрямую, каким типом следует ограничиться в выводе
// с помощью "турбо-рыбы" `::<>`!
let y = x.clone().into_iter().collect::>();

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. Для создания Box мы просто создадим
    // `Box`, и воткнем его куда-то, где ожидают `Box`.
    // Вот мы определили `data` с `Box`ами,
    // и массив-литерал нам радостно выполнил согласование типов!
    // Видите, мы вставляем и i32 и i64 в тот же самый список,
    // чего не удалось бы сделать с массивом конкретного типа.
    let data: [Box; 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();   // Щас как склонируем, ииии...?
}

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 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       |
+-----------------+     +-----------------+

Cat's Pet vtable        Dog's Pet vtable
+-----------------+     +-----------------+
| type stuff      |     | type stuff      |
+-----------------+     +-----------------+
| Pet stuff       |     | Pet stuff       |
+-----------------+     +-----------------+

// Это уже было...
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(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; 2] = [Box::new(20i32), Box::new(30i64)];

    for val in &data {
        // Динамический подход: мономорфирована единственная виртуальная версия.
        // Гадкий каст &Box к &Print вручную, потому что
        // дженерики и авто-разыменование указателей архитектурно дружат так себе...
        print_it_twice(&**val);    // 20, 20, 30, 30
    }
}