Шаблон индексирования для нового типа

Аналогично предыдущему посту, мы попробуем добавить типы к коду 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.

Поддержите на Patreon