Шаблон индексирования для нового типа
• оригинал: Aleksey Kladov • перевод: Александр Андреев • руководства • поддержите на Patreon
Аналогично предыдущему посту, мы попробуем добавить типы к коду Rust, который без них прекрасно работает. В этот раз мы попробуем улучшить распространённый подход использования индексов для управления циклическими структурами данных.
Проблема
Часто приходится работать со структурой данных, которая содержит циклические ссылки
вида: объект foo
ссылается на bar
, который ссылается baz
,
который в свою очередь ссылается на foo
.
Учебный пример здесь представляет собой граф вершин и рёбер.
Однако на практике истинные графы встречаются редко.
Вместо этого, вы скорее всего увидите дерево с указателями на родителей,
которое содержит много тривиальных циклов,
и иногда неявные циклические графы: Сотрудник (Employee)
может быть руководителем Отдела (Department)
,
и в Отделе (Department)
есть сотрудники Vec<Employee>
.
Это что-то вроде замаскированного графа: в обычных графах все вершины одного типа,
а вот Сотрудник (Employee)
и Отдел (Department)
— это разные типы.
Работать с такими структурами данных сложно на любом языке. Прибывать
в ситуации, когда A
указывает на B
, который указывает на A
, некоторая
форма изменчивости обязательна. Действительно, любой из объектов A
или B
может быть
создан первым, и поэтому он может не сразу после
создания указывать на другой объект.
Вы можете спрятать изменяемость с помощью let rec
, как в
OCaml
, или ленивости как в Haskell
, но она ни куда девается.
Rust старается обнаруживать проблемы такого вида во время компиляции, поэтому реализация таких графов в Rust является сложной задачей. Три обычно применяемых подхода:
- Подсчёт ссылок, более подробно смотрите у nrc,
- Арена и реальные циклические ссылки, объяснение от simonsapin (это очень хороший пост!),
- Арена целочисленные индексы, объяснение от nikomatsakis.
(по-видимому, переписывание учебника по монадам в Haskell для Rust приводит к записям в блоге про графы).
Лично мне больше всего нравится подход с индексами, но с ним
возникает другая проблема. С ссылками, вы имеете
foo
типа &Foo
, и сразу понятно что это такое
и что вы можете с этим сделать. С индексами, однако, у вас есть foo: usize
,
и не очевидно, что вы каким-то образом можете получить Foo
.
Даже хуже, если индексы используются для двух типов объектов, таких как Foo
и
Bar
, вы можете в конечном итоге получить thing: usize
. При написании кода с
использованием usize
на самом деле работает довольно хорошо
(хотя я не думаю, что когда-либо использовал неправильный тип индекса),
чтение его сложнее, потому что usize
гораздо менее информативно о том,
что вы могли бы сделать с полученным значением.
Трюк с новым типом (Newtype)
Один из способов обойти эту проблему — это сделать обёртку над usize
:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | struct Foo; #[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)] struct FooIdx(usize); struct Arena { foos: Vec<Foo>, } impl Arena { fn foo(&self, foo: FooIdx) -> &Foo { &self.foos[foo.0] } } |
Здесь, «надо использовать FooIdx
в Vec<Foo>
», это только соглашение.
Одно из достоинств Rust заключается в том, что мы можем превратить это
соглашение в свойство, проверенное во время проверки типа. Путём добавления
соответствующей реализации, мы сможем индексировать Vec<Foo>
с
помощью FooIdx
напрямую:
1 2 3 4 | #[test] fn direct_indexing(foos: Vec<Foo>, idx: FooIdx) { let _foo: &Foo = &foos[idx]; } |
Реализация выглядит так:
1 2 3 4 5 6 7 8 9 | use std::ops; impl ops::Index<FooIdx> for Vec<Foo> { type Output = Foo; fn index(&self, index: FooIdx) -> &Foo { &self[index.0] } } |
Последовательность
Интересно разобраться, почему эта реализация вообще разрешена языком.
В Rust типы, типажи и реализации разделены.
Это создаёт проблемы: что если есть два блока impl
для данной пары (типаж, тип)?
Очевидный выбор — запретить иметь два impls
, и это именно, то что делает Rust.
На самом деле сложно соблюдать это ограничение! Самое простое правило
«ошибка, если набор пакетов содержит повторяющиеся impls
»
имеет серьёзные недостатки. Прежде всего, это глобальная проверка, которая
требуется знание всех скомпилированных пакетов. Эта проверка откладывается
до более поздних стадий компиляции. Эта проблема также создаёт проблемы с зависимостями,
потому что два совершенно несвязанных пакета могут не
компилироваться, если одновременно присутствует impl
для пары (типаж, тип).
Более того, компилятор сам не решит проблему, т. к. у него нет всей информации обо всех пакетах.
Например, можно загрузить дополнительный код во время выполнения через динамические библиотеки
и могут произойти всякие плохие штуки, если ваша программа и динамическая библиотека содержат дублирующиеся реализации.
Для того чтобы свободно комбинировать пакеты, мы хотим гораздо более сильное свойство:
не только текущее множество скомпилированных пакетов, но и все существующие и
даже будущие пакеты не должны нарушать ограничение на одну реализацию типажа.
Как это в дальнейшем проверить?
При публикации пакета на crates.io
через cargo publish
должно выдаваться предупреждение
о конфликте реализации impl
для пары (типаж, тип) с уже опубликованными пакетами?
К счастью, и это потрясающе красиво, можно нивелировать это всеобъемлющее свойство до локального.
В самом простом виде, мы может поместить ограничение, что impl Foo for Bar
может появиться либо в пакете, который определяет Foo
, или в том, который определяет
Bar
. Важно то, какой из них определяет impl
, должен использовать другой,
что даёт возможность обнаружить конфликт.
Это все действительно изящно, но мы только что определили Index
для
Vec
, и оба — и Index
и Vec
из стандартной библиотеки! Как
это возможно? Хитрость в том, что Index
имеет параметр типа:
trait Index<Idx: ?Sized>
. Это шаблон для типажа, и мы получаем
«реальный» типаж, когда мы подставляем параметр типа. Поскольку
FooIdx
является локальным типом, итоговый Index<FromIdx>
тоже
считается локальным. Точные правила здесь довольно сложны, RFC
объясняет их довольно хорошо.
Больше impls
Поскольку Index<FooIdx>
и Index<BarIdx>
разные типажи, один
тип может реализовать их оба. Это удобно для контейнеров
которые содержат различные типы:
1 2 3 4 5 6 7 8 | struct Arena { foos: Vec<Foo>, bars: Vec<Bar>, } impl ops::Index<FooIdx> for Arena { ... } impl ops::Index<BarIdx> for Arena { ... } |
Также полезно определить арифметические операции и преобразования для
новых типизированных индексов.
Я собрал typed_index_derive
, чтобы автоматизировать этот шаблон через
процедурный макрос, конечный результат выглядит следующим образом:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #[macro_use] extern crate typed_index_derive; struct Spam(String); #[derive( // Обычно выводит типичные типажи для структур Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, TypedIndex )] #[typed_index(Spam)] // индексирует `&[Spam]` struct SpamIdx(usize); // может быть `u32` вместо `usize` fn main() { let spams = vec![Spam("foo".into()), Spam("bar".into()), Spam("baz".into())]; // Преобразования между `usize` и `SpamIdx` let idx: SpamIdx = 1.into(); assert_eq!(usize::from(idx), 1); // Индексирование `Vec<Spam>` с помощью `SpamIdx`, `IndexMut` тоже работает assert_eq!(&spams[idx].0, "bar"); // Индексировать `Vec<usize>` нельзя, как и задумывалось // vec![1, 2, 3][idx] // error: slice indices are of type `usize` or ranges of `usize` // Можно прибавлять `usize` или вычитать его из индекса assert_eq!(&spams[idx - 1].0, "foo"); // Разность между двумя индексами выраженная через `usize` assert_eq!(idx - idx, 0usize); } |
Обсуждение /r/rust.