Модуль 2.4 — Трейты и обобщения

Слайды

Упражнение 2.4.1: Векторная математика

В этом упражнении мы реализуем базовые операции векторной математики для нашего двумерного типа вектора Vec2D.

2.4.1.A Сложение векторов

Начнём с реализации сложения для Vec2D через трейт std::ops::Add. Замените todo!() так, чтобы возвращался новый Vec2D, у которого компонента x равна сумме компонент x двух входных векторов, и аналогично для y. Если всё реализовано правильно, тест integer_addition должен пройти!

2.4.1.B Скалярное произведение

Теперь реализуем скалярное произведение для нашего типа вектора. Скалярное произведение двух векторов — это одно число, равное сумме произведений их компонент. Например, [1, 2] * [3, 4] = 1 * 3 + 2 * 4 = 11. Реализуйте его, добавив новый блок impl, который реализует трейт std::ops::Mul для Vec2D. Раскомментируйте тест integer_dot_product, чтобы проверить код!

2.4.1.C Делаем Vec2D обобщённым

Сейчас компоненты x и y нашего Vec2D могут быть только 32-битными целыми. А что, если нужны другие числовые типы, например числа с плавающей точкой? Сделаем Vec2D обобщённым по типу T, изменив определение Vec2D так, чтобы x и y имели обобщённый тип.

Также нужно обновить реализации сложения и скалярного произведения, чтобы они работали с обобщённым типом T. Вместо того чтобы реализовывать add и mul отдельно для каждого числового типа, можно сделать реализации обобщёнными: реализовать их для любого типа T, который можно складывать и/или умножать (то есть для любого T, реализующего трейты Add и/или Mul). Тогда достаточно поменять только начало блока impl, без изменения самих функций!

Раскомментируйте тесты float_addition и float_dot_product, чтобы проверить, что Vec2D теперь работает и с числами с плавающей точкой!

Упражнение 2.4.2: Вектор с локальным хранилищем (LocalStorageVec)

Это бонусное упражнение! Мы создадим тип LocalStorageVec, обобщённый список элементов, который хранится либо на стеке, либо в куче, в зависимости от размера. Если элементы достаточно малы, чтобы поместиться на стеке, буфер LocalStorageVec реализован массивом. LocalStorageVec обобщён не только по типу (T) элементов списка, но и по размеру (N) массива на стеке, используя относительно новую возможность языка, константные обобщения (const generics). Как только в LocalStorageVec оказывается больше элементов, чем помещается в массив, выделяется Vec в куче, где и будут храниться элементы.

В этом упражнении цели помечены звёздочками (⭐), которые показывают сложность. Скорее всего, вы не успеете выполнить все упражнения во время занятия.

Вопросы

1. Когда такая структура данных эффективнее обычного Vec?
2. Каковы её недостатки по сравнению с обычным Vec?

Откройте крейт exercises/2-foundations-of-rust/4-traits-and-generics/1-local-storage-vec. В нём есть файл src/lib.rs, то есть этот крейт — библиотека. В lib.rs есть набор тестов, которые запускаются командой cargo test. Не беспокойтесь, если они пока не проходят или даже не компилируются: в этом упражнении ваша задача — это исправить. Большинство тестов сейчас закомментированы, чтобы можно было идти шаг за шагом. Прежде чем начать, посмотрите код и комментарии в нём: там много полезных подсказок.

2.4.2.A Определяем тип ⭐

Сейчас перечисление LocalStorageVec (enum) не завершено. Добавьте в него два варианта: Stack и Heap. Stack содержит два именованных поля: buf и len. buf — массив, вмещающий N элементов типа T; len — поле типа usize, которое хранит количество реально сохранённых элементов. Вариант Heap содержит безымянное поле с Vec<T>. Если варианты определены правильно, запуск cargo test должен вывести примерно следующее:

running 1 test
test test::it_compiles ... ignored, This test is just to validate the definition of `LocalStorageVec`. If it compiles, all is OK

test result: ok. 0 passed; 0 failed; 1 ignored; 0 measured; 0 filtered out; finished in 0.00s

Этот тест не запускается (и не должен), он нужен только для проверки определения вариантов.

#![allow(unused)]
fn main() {
// Определяем перечисление `LocalStorageVec`, обобщённое
// по типу `T` и константе `N` типа `usize`
pub enum LocalStorageVec<T, const N: usize> {
    // Вариант в стиле структуры с именем `Stack`, содержащий два именованных поля:
    // - `buf` — массив элементов типа `T` размером `N`
    // - `len` — поле типа `usize`
    Stack { buf: [T; N], len: usize },
    // Вариант в стиле кортежа с именем `Heap`, содержащий одно поле
    // типа `Vec<T>` — растущий непрерывный список `T` в куче
    Heap(Vec<T>),
}
}

2.4.2.B Реализуем From<Vec<T>> ⭐

Раскомментируйте тест it_from_vecs и добавьте реализацию From<Vec<T>> для LocalStorageVec<T>. Для этого скопируйте следующий код в файл lib.rs и замените вызов макроса todo! на ваш код, который создаёт LocalStorageVec в куче с переданным Vec<T>.

#![allow(unused)]
fn main() {
impl<T, const N: usize> From<Vec<T>> for LocalStorageVec<T, N> {
    fn from(v: Vec<T>) -> Self {
        todo!("Implement me");
    }
}
}

Вопрос

1. Как бы вы по-английски прочитали первую строку кода, которую только что скопировали?*

Запустите cargo test, чтобы проверить реализацию.

2.4.2.C AsRef и AsMut ⭐⭐

AsRef и AsMut используются для реализации дешёвого преобразования ссылки в ссылку. Например, наш LocalStorageVec<T, N> похож на срез &[T]: оба представляют непрерывную последовательность значений T. Это верно и тогда, когда буфер LocalStorageVec находится на стеке, и тогда, когда он в куче.

Раскомментируйте тестовый случай it_as_refs и реализуйте AsRef<[T]> и AsMut<[T]>.

2.4.2.D impl LocalStorageVec ⭐⭐

Чтобы LocalStorageVec был полезнее, добавим в него больше методов. Создайте блок impl для LocalStorageVec. Не забудьте объявить обобщённые параметры и передать их. Чтобы упростить реализацию, пока добавим ограничение на T: он должен реализовывать Copy и Default. Сначала раскомментируйте тест it_constructs. Сделайте его компилируемым и проходящим, создав ассоциированную функцию new для LocalStorageVec, которая создаёт новый пустой экземпляр LocalStorageVec без выделения памяти в куче.

Далее реализуем методы len, push, pop, insert, remove и clear:

• len возвращает длину LocalStorageVec;
• push добавляет элемент в конец LocalStorageVec и увеличивает длину. Если содержимое больше не помещается на стеке, оно может быть перенесено в кучу;
• pop удаляет элемент с конца LocalStorageVec, возвращает его (опционально) и уменьшает длину. Если длина равна 0, pop возвращает None;
• insert вставляет элемент по заданному индексу и увеличивает длину LocalStorageVec;
• remove удаляет элемент по заданному индексу и возвращает его;
• clear сбрасывает длину LocalStorageVec в 0.

Раскомментируйте соответствующие тестовые случаи и добейтесь, чтобы они компилировались и проходили. Обязательно изучите методы, которые предоставляют срезы [T] и Vec<T>. В частности, могут пригодиться [T]::copy_within и Vec::extend_from_slice.

2.4.2.E Iterator и IntoIterator ⭐⭐

Теперь LocalStorageVec можно использовать на практике, но останавливаться рано. В стандартной библиотеке есть трейты, которые можно реализовать для LocalStorageVec, и пользователи вашего крейта будут им рады.

Для начала реализуем трейты IntoIterator и Iterator. Раскомментируйте тестовый случай it_iters. Определим новый тип:

#![allow(unused)]
fn main() {
pub struct LocalStorageVecIter<T, const N: usize> {
    vec: LocalStorageVec<T, N>,
    counter: usize,
}
}

Именно для этого типа мы реализуем трейт Iterator. Вам нужно указать тип элемента, который выдаёт реализация Iterator, а также реализовать Iterator::next, который возвращает следующий элемент. Задача упростится, если при реализации Iterator ограничить T трейтом Default: тогда можно использовать функцию std::mem::take, чтобы забрать элемент из LocalStorageVec и заменить его значением по умолчанию для T.

Посмотрите список методов в разделе «provided methods». Там много полезных методов, которые доступны бесплатно после реализации Iterator и выражаются через метод next. Если держать их в голове, писать код на Rust будет заметно эффективнее. Какие из этих методов можно переопределить, чтобы реализация LocalStorageVecIter стала эффективнее, учитывая, что мы имеем доступ к полям и методам LocalStorageVec?

Чтобы создать LocalStorageVecIter, реализуйте для него трейт IntoIter так, чтобы вызов into_iter возвращал LocalStorageVecIter.

2.4.2.F Index ⭐⭐

Чтобы пользователи LocalStorageVec могли читать элементы и срезы из его буфера, можно реализовать трейт Index. Этот трейт обобщён по типу индекса. Чтобы сделать LocalStorageVec универсальным, реализуйте:

• Index<usize> — позволяет получить один элемент через vec[1];
• Index<RangeTo<usize>> — позволяет получить первые n элементов (не включая элемент n) через vec[..n];
• Index<RangeFrom<usize>> — позволяет получить элементы с позиции n до конца через vec[n..];
• Index<Range<usize>> — позволяет получить элементы между n и m (не включая элемент m) через vec[n..m].

Каждую из этих реализаций можно выразить через реализацию as_ref, поскольку срезы [T] поддерживают индексирование всеми перечисленными типами. То есть [T] тоже реализует Index для этих типов. Раскомментируйте тестовый случай it_indexes и запустите cargo test, чтобы проверить реализацию.

2.4.2.G Снимаем ограничения ⭐⭐

Когда мы реализовывали итератор, заимствующий данные, мы видели, что методы можно определять в разных блоках impl с разными ограничениями на типы. Часть написанного нами функционала опиралась на допущение, что T одновременно реализует Copy и Default. Но из-за этого каждый такой метод определён только для LocalStorageVec, содержащих элементы типа T, которые действительно реализуют Copy и Default, а это неидеально. Сколько методов можно переписать, убрав одно или оба из этих ограничений?

2.4.2.H Заимствующий Iterator ⭐⭐⭐

У LocalStorageVec уже есть итератор, но у него есть ограничение: чтобы его создать, LocalStorageVec нужно поглотить (consume). А что, если мы хотим только перебирать элементы, не забирая их? Понадобится другой тип итератора, который содержит неизменяемую ссылку на LocalStorageVec и, значит, потребует аннотацию времени жизни. Добавьте в LocalStorageVec метод iter, который принимает разделяемую ссылку &self и создаёт заимствующий итератор. Реализуйте трейт Iterator с подходящим типом ссылки Item для вашего заимствующего итератора. Чтобы проверить код, раскомментируйте и запустите тестовый случай it_borrowing_iters.

Обратите внимание: на этот раз тест не скомпилируется, если потребовать, чтобы элементы LocalStorageVec были Copy! Значит, метод LocalStorageVec::iter нужно определить в новом блоке impl, который не накладывает это ограничение на T:

#![allow(unused)]
fn main() {
impl<T: Default + Copy, const N: usize> LocalStorageVec<T, N> {
    // Методы, которые вы реализовали до сих пор
}

impl<T, const N: usize> LocalStorageVec<T, N> {
    pub fn iter(&self) -> /* TODO */
}
}

Определение методов в разных блоках impl означает, что часть методов недоступна для некоторых экземпляров обобщённого типа. В нашем случае метод new доступен только для LocalStorageVec, содержащих элементы типа T, которые реализуют и Copy, и Default, а iter доступен для всех LocalStorageVec.

2.4.2.I Обобщённый Index ⭐⭐⭐⭐

Скорее всего, в упражнении 2.4.2.F вы продублировали много кода. Его можно сократить, определив пустой трейт:

#![allow(unused)]
fn main() {
trait LocalStorageVecIndex {}
}

Сначала реализуйте этот трейт для usize, RangeTo<usize>, RangeFrom<usize> и Range<usize>.

Затем замените несколько реализаций Index одной. Словами это звучит так:

«Для каждого типа T, типа I и константы N типа usize реализовать Index<I> для LocalStorageVec<T, N>, где I реализует LocalStorageVecIndex и [T] реализует Index<I>»

Если вы всё сделали правильно, it_indexes снова должен компилироваться и проходить.

2.4.2.J Deref и DerefMut ⭐⭐⭐⭐

Следующие трейты, которые сделают LocalStorageVec гибче, — это Deref и DerefMut. Они используют возможность Rust «deref coercion», которая позволяет обращаться с типом так, будто это тот тип, на который он похож. Благодаря этому мы сможем вызывать на LocalStorageVec любой метод, определённый для [T]. Прежде чем продолжить, прочитайте раздел «Treating a Type Like a Reference by Implementing the Deref Trait» из The Rust Programming Language (TRPL) — раздел о том, как относиться к типу как к ссылке, реализуя трейт Deref. Не путайте deref coercion с наследованием! Использовать Deref и DerefMut для имитации наследования в Rust не принято.

Ниже приведена реализация Deref и DerefMut через реализации AsRef и AsMut. Обратите внимание на то, как именно вызываются as_ref и as_mut.

#![allow(unused)]
fn main() {
impl<T, const N: usize> Deref for LocalStorageVec<T, N> {
    type Target = [T];

    fn deref(&self) -> &Self::Target {
        <Self as AsRef<[T]>>::as_ref(self)
    }
}

impl<T, const N: usize> DerefMut for LocalStorageVec<T, N> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        <Self as AsMut<[T]>>::as_mut(self)
    }
}
}

Вопрос

• Если заменить реализацию deref на self.as_ref(), то при запуске неоптимизированной сборки возникает переполнение стека. Почему? (Подсказка: deref coercion)