Гайд на полиморфизм. Rust
В прошлых статьях мы разобрали теорию: что такое полиморфизм и какие существуют способы его реализации. Настало время посмотреть, как это реализуется на практике. В качестве примера был выбран Rust — язык с богатой функциональностью, с одной стороны, и простой, прозрачной реализацией — с другой.
Закрытый полиморфизм
Первый факт — в Rust есть несколько типов для строк.
Основные из них — это &str и String.&str — это ссылка на строковый срез, которая может указывать на символы, находящиеся в различных частях памяти — например, в куче или статической памяти. Это неизменяемый тип.String — это коллекция UTF-8 байт, выделяемая в куче. Это изменяемый тип.
Второй факт — в Rust нет наследования.
Третий факт — данный код работает:
fn print_name(name: &str) {
println!("Name is {name}");
}
fn main() {
let name = String::from("Alex");
print_name(&name));
}Ну ладно в Java, ладно в C#, где есть наследование типов и можно было бы представить что String наследуется от str. Но в Rust нет такого и данные виды друг от друга напрямую никак не зависят. Как же так получается что в качестве &str может выступать любой String?
Ответ кроется в неявном приведении типов:
impl ops::Deref for String {
type Target = str;
#[inline]
fn deref(&self) -> &str {
self.as_str()
}
}Тип String реализует оператор разыменования и неявно превращает ссылку на String в строковый срез, когда это требуется:
pub const fn as_str(&self) -> &str {
unsafe { str::from_utf8_unchecked(self.vec.as_slice()) }
}
pub const unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
// после получения ссылки на сред байт
// мы форсировано приводит его к типу строкового среза
unsafe { mem::transmute(v) }
}
Таким образом, оба вызова равнозначны:
print_name(&name);
print_name(&name.as_str());Кстати, о перегрузке. В Rust доступна только перегрузка операторов. Сделано это довольно элегантно: просто как реализация контракта (trait) для типа:
impl ops::Add<Point> for Point {
type Output = Point;
fn add(self, rhs: Point) -> Self::Output {
Self {
x: self.x + rhs.x,
y: self.y + rhs.y,
}
}
}Что позволяет выполнять удобные операции с пользовательскими типами:
fn main() {
let point_a = Point { x: 3.4, y: 5.6 };
let point_b = Point { x: 1.4, y: 8.8 };
let point_c = point_a + point_b;
// Point { x: 4.8, y: 14.4 }
println!("{point_c:?}")
}Открытый полиморфизм
В контексте открытого вида полиморфизма Rust оперирует одной из двух категорий типов:
Универсальный тип — это тип, который может быть заменен любым удовлетворяющим критирии типом. Такие типы используются в параметрическом полиморфизме и часто называются дженериками.
Player -> T:User -> PlayerЭкзистенциальный тип — это тип, скрывающий истинную природу оригинального типа но гарантирующий что тот удовлетворяет определенным критериям. Такие типы, например, используются в полиморфизме подтипов, реализуемом во многих языках через наследование типов.
Player -> ?:User -> ?:UserПредположим, у нас есть контракт User и типы Player и Admin, его реализующие:
trait User {
fn id(&self) -> u32;
}
#[derive(Debug)]
struct Player {
id: u32,
games: Vec<String>,
}
#[derive(Debug)]
struct Admin {
id: u32,
permissions: Vec<u8>,
}Использование универсального типа будет выглядеть так:
fn universal<T>(user: &T) -> &T where T: User {
// тип сохранен
let u: &T = user;
// monomor::core::Player
println!("{}", type_name_of_val(u));
println!("{}", u.id());
u
}
let original_player: &Player = universal(&player);Здесь всё просто: шаблон T фактически заменяется реальным типом, при этом тип должен реализовывать контракт User. Нетрудно заметить, что тип, переданный в T, сохраняется на всём протяжении выполнения функции, и вернув T, мы получим тот же самый Player, что и передали. В данном примере T ограничен только одним контрактом User, но никто не мешает добавить другие.
Пример использования экзистенциального типа:
fn existional(user: &impl User) -> &impl User {
// тип утерян, его нельзя указать явно
let u = user;
// monomor::core::Player
println!("{}", type_name_of_val(u));
println!("{}", u.id());
u
}
let unknown_user = existional(&player);Здесь уже всё по-другому: при передаче типа в функцию она забивает забывает его и оперирует только контрактом User. Мы не можем явно указать экзистенциальный тип — только использовать автоматическое выведение. Функция была применена к Player, а вернула нечто, тип которого нам неизвестен, но при этом гарантированно реализующее контракт User.
Возникает резонный вопрос: зачем вообще нужны экзистенциальные типы, если через них нельзя задать более одного ограничения и при этом теряется конкретный тип?
Во-первых, это может быть удобно, если нам не нужно сохранять тип: написать impl куда компактнее, чем объявлять параметр типа и задавать для него ограничения.
Во-вторых, бывают ситуации, когда мы не можем предоставить конкретный тип, и использование универсальных типов становится невозможным.
Ахиллесова пята универсальных типов — их зависимость от входных параметров. Мы можем определить тип извне, но не изнутри самой функции. Поэтому универсальные типы, при всех их плюсах, ломаются на банальном примере:
fn create_default_user<T>(id: u32) -> T where T: User {
Player { id, games: vec![] }
}На первый взгляд всё выглядит хорошо. Но на деле между типом, который мы позволяем передать в функцию, и тем, что получим в результате, нет никакой жёсткой связи. Закономерный итог:
fn create_default_user<T>(id: u32) -> T where T: User {
- -
| |
| expected `T` because of return type
| help: consider using an impl return type: `impl User`
expected this type parameter
Player { id, games: vec![] }
^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `T`, found `Player`Компилятор заботливо подсказывает: в данном случае следует использовать экзистенциальный тип.
fn create_default_user(id: u32) -> impl User {
Player { id, games: vec![] }
}Но почему это сработает? Ответ: потому что, в отличие от универсального типа, экзистенциальный не нужно задавать извне, ему вообще не важен конкретный тип — важно лишь соблюдение контракта.
А вот что действительно критично для обоих подходов — это соблюдение требований к размеру типов в памяти. Но об этом чуть позже.
Сначала давайте разберёмся, как на низком уровне реализуются описанные выше механизмы. Определим типы:
trait Printer {
fn print(&self);
}
impl Printer for bool {
fn print(&self) {
println!("Is's bool:{self}")
}
}
impl Printer for i32 {
fn print(&self) {
println!("Is's i32:self")
}
}
struct Point {
x: f64,
y: f64,
}
impl Printer for Point {
fn print(&self) {
println!("Is's Point:({}.{})", self.x, self.y)
}
}У нас будет контракт Printer, который должен гарантировать наличие функции print для определённого типа. Мы реализуем Printer для двух скалярных типов и одного пользовательского. Теперь перейдём к самой полиморфной функции. Определим и вызовем функцию с универсальным типом:
fn universal_print<T>(val: T) where T: Printer {
val.print();
}
pub fn main() {
universal_print(true);
universal_print(99);
universal_print(Point { x: 1.0, y: 4.5 });
}Напомню: universal_print применяется к любому типу, который реализует контракт Printer, и сохраняет данный тип на всём протяжении своей работы. Мы сделали три вызова с тремя разными типами данных. Давайте посмотрим на ASM через Godbolt:
example::main::hdc436770f0aefb4c:
push rax
mov edi, 1
call example::universal_print::h711e55ed310c15bb
mov edi, 99
call example::universal_print::h9f7d5cef34f9e24e
movsd xmm0, qword ptr [rip + .LCPI12_0]
movsd xmm1, qword ptr [rip + .LCPI12_1]
call example::universal_print::hdb8d1cfe18105ad7
pop rax
retЗдесь мы чётко видим три вызова universal_print, но при внимательном рассмотрении становится заметно: на самом деле это три разные функции — часть имени, содержащая хеш, различается. Взглянем на содержимое самих функций:
example::universal_print::h711e55ed310c15bb:
push rax
mov al, dil
and al, 1
mov byte ptr [rsp + 7], al
lea rdi, [rsp + 7]
call qword ptr [rip + <bool as example::Printer>::print::ha90281dba6484e75@GOTPCREL]
pop rax
ret
example::universal_print::h9f7d5cef34f9e24e:
push rax
mov dword ptr [rsp + 4], edi
lea rdi, [rsp + 4]
call qword ptr [rip + <i32 as example::Printer>::print::h4ed00bd6afa69296@GOTPCREL]
pop rax
ret
example::universal_print::hdb8d1cfe18105ad7:
sub rsp, 24
movsd qword ptr [rsp + 8], xmm0
movsd qword ptr [rsp + 16], xmm1
lea rdi, [rsp + 8]
call qword ptr [rip + <example::Point as example::Printer>::print::h278cd73f496c36f1@GOTPCREL]
add rsp, 24
retМожно заметить, что сгенерированные функции действительно различаются. Это указывает на то, что компилятор применил мономорфизацию — преобразуя одну универсальную (полиморфную) функцию в набор специализированных реализаций для каждого конкретного типа.
Примечание
Важно отметить, что для наглядности примеры компилируются с использованием следующих флагов:
-C panic=abort -C opt-level=0
На более высоком уровне, будут применяться различные оптимизации, включая встраивание (inlining). Поэтому в продакшене многие полиморфные функции не будут мономорфизироваться — вместо этого они будут встраиваться напрямую в вызывающий код, что позволит избежать генерации отдельных реализаций для каждого типа.
Хорошо, мы рассмотрели, как работают универсальные типы, теперь пора перейти к экзистенциальным:
fn existential_print(val: impl Printer) {
val.print();
}
pub fn main() {
existential_print(true);
existential_print(99);
existential_print(Point { x: 1.0, y: 4.5 })
}Как мы помним, эта функция забывает оригинальный тип. Заглянем под капот:
example::main::hdc436770f0aefb4c:
push rax
mov edi, 1
call example::existential_print::h27a720521bb10817
mov edi, 99
call example::existential_print::h127a4c4152bc7a41
movsd xmm0, qword ptr [rip + .LCPI12_0]
movsd xmm1, qword ptr [rip + .LCPI12_1]
call example::existential_print::hc85fc40cdb877da9
pop rax
retРеализация функций
example::existential_print::h127a4c4152bc7a41:
push rax
mov dword ptr [rsp + 4], edi
lea rdi, [rsp + 4]
call qword ptr [rip + <i32 as example::Printer>::print::h4ed00bd6afa69296@GOTPCREL]
pop rax
ret
example::existential_print::h27a720521bb10817:
push rax
mov al, dil
and al, 1
mov byte ptr [rsp + 7], al
lea rdi, [rsp + 7]
call qword ptr [rip + <bool as example::Printer>::print::ha90281dba6484e75@GOTPCREL]
pop rax
ret
example::existential_print::hc85fc40cdb877da9:
sub rsp, 24
movsd qword ptr [rsp + 8], xmm0
movsd qword ptr [rsp + 16], xmm1
lea rdi, [rsp + 8]
call qword ptr [rip + <example::Point as example::Printer>::print::h278cd73f496c36f1@GOTPCREL]
add rsp, 24
retА под капотом ровно то же самое. Это говорит о том, что разница между такими типами только в их возможностях и только на этапе компиляции, а реализация у них одинаковая:
fn universal_print<T>(val: T) where T: Printer {
val.print();
}
fn existential_print(val: impl Printer) {
val.print();
}Универсальный тип T: Printer позволяет сохранять оригинальный тип, а также ограничивать его множественными контрактами, однако синтаксически он более громоздкий и не может быть выведен внутри самой функции.
Экзистенциальный тип impl Printer, напротив, более компактный и удобный для ситуаций, когда не нужно сохранять оригинальный тип. Он также даёт возможность использовать тип без его явного определения извне.
Давайте рассмотрим другой пример:
fn create_user_by_type(id: u32, user_type: UserType) -> impl User {
match user_type {
UserType::Player => Player { id, games: vec![] },
UserType::Admin => Admin {
id,
permissions: vec![1],
},
}
}Осознав что параметры типа T нам не помогут используем экзистенциальный тип:
|
32 | match user_type {
| --------------- `match` arms have incompatible types
33 | UserType::Player => Player { id, games: vec![] },
| ---------------------------- this is found to be of type `Player`
34 | UserType::Admin => Admin {
| ____________________________________^
35 | | id,
36 | | permissions: vec![1],
37 | | },
| |_________________^ expected `Player`, found `Admin`
|
help: you could change the return type to be a boxed trait object
|
31 - fn create_user_by_type(id: u32, user_type: UserType) -> impl User {
31 + fn create_user_by_type(id: u32, user_type: UserType) -> Box<dyn User> {
|
help: if you change the return type to expect trait objects, box the returned expressions
|
33 ~ UserType::Player => Box::new(Player { id, games: vec![] }),
34 ~ UserType::Admin => Box::new(Admin {
35 | id,
36 | permissions: vec![1],
37 ~ }),Ошибка. Всё дело в том, что размер параметров и возвращаемого значения функции должен быть фиксированным в стеке. До этого так и происходило. Было три используемых параметра для функции, каждый определённого размера. Компилятор генерировал по функции на каждую комбинацию используемых типов и размеров.
Но в последнем примере мы столкнулись с динамикой — ситуацией, когда возвращаемый тип и его размер будут известны только в момент вызова функции во время исполнения. Мономорфизация здесь бесполезна. Придеться обратиться к оставшимся способам реализации полиморфизма — резервированию или упаковке.
Резервирование
enum UserUnion {
Admin(Admin),
Player(Player),
}
fn create_user_by_type3(id: u32, user_type: UserType) -> UserUnion {
match user_type {
UserType::Player => UserUnion::Player(Player {
id,
games: vec![]
}),
UserType::Admin => UserUnion::Admin(Admin {
id,
permissions: vec![1],
}),
}
}
let user = create_user_by_type(10, UserType::Player);
match user {
UserUnion::Admin(admin) => todo!(),
UserUnion::Player(player) => todo!(),
}Мы создали специальный тип, размер которого равен размеру самого крупного из используемых типов, а это значит, размер возвращаемого значения зафиксирован и такой код может быть успешно скомпилирован.
Упаковка
Последнее из решений — спрятать типы за ссылку, размер которой всегда фиксирован. Для реализации этого способа в Rust существует специальная динамическая разновидность экзистенциальных типов.
impl User — это экзистенциальный тип со статической природой. В качестве такого типа может использоваться любая реализация указанного контракта. При этом исходный тип становится неважен.
dyn User — его динамический «кузен». Отличие в том, что реализация скрывается за указателем, а поведение определяется динамически с помощью таблицы виртуальных методов.
fn create_user_by_type(id: u32, user_type: UserType) -> Box<dyn User> {
match user_type {
UserType::Player => Box::new(Player {
id,
games: vec![]
}),
UserType::Admin => Box::new(Admin {
id,
permissions: vec![1],
}),
}
}
let user: Box<dyn User> = create_user_by_type(10, UserType::Player);Первое — мы возвращаем не сам объект User, а указатель на память в куче.
Второе — тип возвращаемого значения не известен, мы знаем только, что он удовлетворяет контракту User.
Третье — для User указано ключевое слово dyn, что означает, что поскольку конкретный тип неизвестен, будет использоваться динамическая диспетчеризация, и адрес метода будет определён в момент вызова.
Почему мы вынуждены выделять память в куче?
Мы не можем вернуть реализацию User, поскольку это тип неизвестного размера, а нам необходимо зарезервировать память известного размера.
Также мы не можем вернуть ссылку на структуру, созданную внутри функции, так как после завершения функции эта память будет освобождена.
Поэтому приходится выделять память на стороне — в куче.
Для наглядности воспользуемся предыдущим примером с print:
fn dynamic_existential_print(val: &dyn Printer) {
val.print();
}
pub fn main() {
let a = true;
let b = 99;
let c = Point { x: 1.0, y: 4.5 };
dynamic_existential_print(&a);
dynamic_existential_print(&b);
dynamic_existential_print(&c)
}В данном примере мы не будем упаковывать данные в кучу, а просто возьмём указатели на них — этого вполне достаточно. Посмотрим на вызовы в main:
example::main::hdc436770f0aefb4c:
sub rsp, 24
mov byte ptr [rsp + 3], 1
mov dword ptr [rsp + 4], 99
movsd xmm0, qword ptr [rip + .LCPI13_1]
movsd qword ptr [rsp + 8], xmm0
movsd xmm0, qword ptr [rip + .LCPI13_0]
movsd qword ptr [rsp + 16], xmm0
lea rdi, [rsp + 3]
lea rsi, [rip + .Lanon.ca4ea46b1734d957c09d7b07bf131053.10]
call example::dynamic_existential_print::hd5f8b3b52234a935
lea rdi, [rsp + 4]
lea rsi, [rip + .Lanon.ca4ea46b1734d957c09d7b07bf131053.11]
call example::dynamic_existential_print::hd5f8b3b52234a935
lea rdi, [rsp + 8]
lea rsi, [rip + .Lanon.ca4ea46b1734d957c09d7b07bf131053.12]
call example::dynamic_existential_print::hd5f8b3b52234a935
add rsp, 24
retПервое, что мы видим — в отличие от прошлых примеров вызывается одна и та же функция. Посмотрим внимательно:
lea rdi, [rsp + 3]
lea rsi, [rip + .Lanon.ca4ea46b1734d957c09d7b07bf131053.10]
call example::dynamic_existential_print::hd5f8b3b52234a935Сначала в регистр rdi помещается указатель на аргумент (bool, i32, Point).
В регистр rsi — указатель на таблицу виртуальных методов (vtable).
В конце происходит вызов функции dynamic_existential_print.
Взглянем на таинственную запись.Lanon.ca4ea46b1734d957c09d7b07bf131053.10:
.Lanon.ca4ea46b1734d957c09d7b07bf131053.10:
.asciz "\000\000\000\000\000\000\000\000\001\000\000\000\000\000\000\000\001\000\000\000\000\000\000"
.quad <bool as example::Printer>::print::ha90281dba6484e75
.Lanon.ca4ea46b1734d957c09d7b07bf131053.11:
.asciz "\000\000\000\000\000\000\000\000\004\000\000\000\000\000\000\000\004\000\000\000\000\000\000"
.quad <i32 as example::Printer>::print::h4ed00bd6afa69296
.Lanon.ca4ea46b1734d957c09d7b07bf131053.12:
.asciz "\000\000\000\000\000\000\000\000\020\000\000\000\000\000\000\000\b\000\000\000\000\000\000"
.quad <example::Point as example::Printer>::print::h278cd73f496c36f1Можно заметить, что для каждого используемого типа была создана отдельная таблица виртуальных методов. Она содержит соответствие между индексом метода и его реальным адресом. Выглядит не очень читабельно. Попробуем привести к человеческому виду на примере типа bool:
Offset | Bytes | Описание
-------+----------------------------+---------------------------------
+0 | 00 00 00 00 00 00 00 00 | Адрес функции очистки памяти
+8 | 01 00 00 00 00 00 00 00 | size
+16 | 01 00 00 00 00 00 00 00 | align
+24 | <адрес функции> | Адрес <bool as example::Printer>::print::...Первая позиция таблицы зарезервирована под адрес функции очистки памяти.
Далее располагаются размер типа и его выравнивание.
Со смещением в 24 байта начинаются адреса методов-реализаций: адрес первого метода находится со смещением в 24 байта, а второго в 32 байта и так далее.
Заглянем в функцию dynamic_existential_print:
example::dynamic_existential_print::hd5f8b3b52234a935:
sub rsp, 24
mov qword ptr [rsp + 8], rdi
mov qword ptr [rsp + 16], rsi
call qword ptr [rsi + 24]
add rsp, 24
retЗдесь все предельно просто:
mov qword ptr [rsp + 8], rdi
mov qword ptr [rsp + 16], rsiСохраняем аргументы — указатель на данные и указатель на таблицу виртуальных методов — в стек.
call qword ptr [rsi + 24]Вызываем функцию, адрес которой вычисляется как адрес vtable + смещение. Напоминаю, что смещение указывает на реальный адрес функции-реализации:
Offset | Value | Описание
-------+----------------------------+---------------------------------
+0 | 0 | Адрес функции очистки памяти
+8 | 1 | size
+16 | 1 | align
+24 | 93824992263216 | Адрес <bool as example::Printer>::print::...Таким образом, в зависимости от типа данных во-первых передается указатель на сами данные разных типов, во-вторых — связанная с этим типом таблица виртуальных методов, и, соответственно, вычисляются разные адреса для различных реализаций методов.
Подводя итог: в самой функции вместо адреса метода хранится величина смещения в vtable. Используя переданный в функцию указатель на vtable и фиксированное смещение, извлекается реальный адрес функции, после чего происходит вызов.
Таблицу виртуальных методов можно посмотреть в отладчике — она спрятана в указателе на объект:
fn dynamic_existential_print(val: &dyn Printer) {
val.print();
}
Полиморфизм на уровне типов
Интересной особенностью Rust, в отличие от многих мейнстримных языков, является возможность объявлять контракты не только для объектов, но и для типов. Например, мы хотим, чтобы у типа был метод создания варианта по умолчанию — к счастью, в языке уже предусмотрен такой контракт:
pub trait Default: Sized {
fn default() -> Self;
}Теперь реализуем этот контракт для пользовательского типа:
impl Default for Point {
fn default() -> Self {
Self { x: 0., y: 0. }
}
}
fn main() {
let default_point = Point::default();
// Point { x: 0.0, y: 0.0 }
println!("{default_point:?}");
}Но это далеко не самое интересное. Вот пример, который гораздо более увлекателен:
fn print_type_info<T>()
where
T: Default,
T: Debug,
{
println!(
"Type name: {}\nSize: {}\nDefault: {:?}",
type_name::<T>(),
size_of::<T>(),
T::default()
);
}
fn main() {
// Type name: monomor::Point
// Size: 16
// Default: Point { x: 0.0, y: 0.0 }
print_type_info::<Point>();
}Заключение
В данной статье мы подробно рассмотрели основные виды полиморфизма в языке Rust. Особое впечатление производит сочетание простоты и высокой эффективности реализованных механизмов, что прекрасно отражает философию языка — абстракции нулевой стоимости. Рассмотренные решения удобны не только для практического применения и обучения, но и для глубокого понимания более сложных концепций программирования на примере Rust.
Благодарю за внимание!
