Тесты или типы? — Rust version

Пару дней назад 0xd34df00d опубликовал здесь перевод статьи, описывающей, что можно узнать о функции в разных языках, если рассматривать её как "чёрный ящик", не используя информацию о её реализации (но, разумеется, не мешая ей пользоваться компилятору). Разумеется, получаемая информация очень сильно зависит от языка — в исходной статье рассматривались четыре примера:

• Python — динамически типизированный, информации минимум, какие-то подсказки дают только тесты;
• C — слабо статически типизированный, информации ненамного больше;
• Haskell — сильно статически типизированный, с чистыми функциями, информации существенно больше;
• Idris — язык с зависимыми типами, информации достаточно, чтобы во время компиляции доказать корректность функции.

"Есть C, есть Haskell, а где же Rust?!" — немедленно прозвучал вопрос. Ответ — под катом.

Напомним условие задачи:

Пусть дан список и некоторое значение. Необходимо вернуть индекс этого значения в списке или указать, что этого значения в списке нет.

Для нетерпеливых — все рассмотренные ниже варианты можно увидеть в Rust playground.
Погнали!

Простой поиск

Мы начнём с почти наивной сигнатуры, которая, по сути, от кода на C отличается только некоторыми идиоматичными элементами:

fn foo(x: &[i32], y: i32) -> Option<usize> {
    // 10000 строк нечитаемого кода
}

Что мы знаем об этой функции? Ну… не так и много, на самом деле. Конечно, иметь в возвращаемых значениях Option<usize> — это гораздо лучше, чем то, что предоставлял нам C, но никакой информации о семантике функции у нас всё равно нет. В частности, нет никакой гарантии отсутствия побочных эффектов, как нет и возможности как-либо проверить ожидаемое поведение.

Может ли ситуацию исправить грамотно написанный тест? Смотрим:

#[test]
fn test() {
    assert_eq!(foo(&[1, 2, 3], 2), Some(1));
    assert_eq!(foo(&[1, 2, 3], 4), None);
}

В общем-то, ничего нового мы не получили — все те же самые проверки мы спокойно могли проделывать и с Python (и, забегая вперёд, тесты практически ничего не дадут и в дальнейшем).

Use the generics, Luke!

Но разве ж это хорошо, что мы вынуждены использовать только знаковые 32-битные числа? Непорядок. Исправляем:

fn foo<El>(x: &[El], y: El) -> Option<usize>
where
    El: PartialEq,
{
    // 10000 строк нечитаемого кода
}

Ага! Это уже кое-что. Теперь мы можем принимать срезы (slice), состоящие из любых элементов, которые мы можем сравнивать на равенство. Явный полиморфизм почти всегда лучше неявного и почти всегда лучше его отсутствия, не так ли?

Однако такая функция может неожиданно для нас пройти вот такой тест:

#[test]
fn dont_find_nan() {
    assert_eq!(foo(&[std::f64::NAN], std::f64::NAN), None);
}

Это сразу указывает на некоторый недочёт с нашей стороны, потому как по изначальной спецификации такой вызов должен был бы вернуть Some(0). Разумеется, проблема здесь из-за специфики типов с частично определённым сравнением вообще и float-ов в частности.
Допустим, теперь мы хотим избавиться от такой проблемы, — для этого всего лишь ужесточим требования на тип El:

fn foo<El>(x: &[El], y: El) -> Option<usize>
where
    El: Eq,
{
    // 10000 строк нечитаемого кода
}

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

fn foo<'a, El: 'a>(x: impl IntoIterator<Item = &'a El>, y: El) -> Option<usize>
where
    El: Eq,
{
    // 10000 строк нечитаемого кода
}

Как раньше, только строже

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

Короче говоря, нам нужен generic array — и в Rust уже есть пакет, предоставляющий дословно это.

Теперь в нашем распоряжении уже такой код:

use generic_array::{GenericArray, ArrayLength};

fn foo<El, Size>(x: GenericArray<El, Size>, y: El) -> Option<usize>
where
    El: Eq,
    Size: ArrayLength<El>,
{
    // 10000 строк нечитаемого кода
}

Что мы знаем из этого кода? Что функция принимает массив некоторого фиксированного размера, отражённого в её типе (и для каждого такого размера скомпилируется независимо). Пока что это почти ничего не меняет — в конце концов, точно такие же гарантии, только не на этапе мономорфизации, а в рантайме, обеспечивал и предыдущий вариант со срезом.

Но мы можем пойти ещё дальше.

Арифметика уровня типов

В исходной статье упоминались несколько гарантий, которую мы получили от Idris и не смогли получить ни от кого более. Одна из них — и, пожалуй, сама простая, потому что для неё даже не нужно писать полноценное доказательство или полноценный тест, а только чуть конкретизировать тип, — гласит, что возвращаемое значение, если оно есть (т.е. если оно не Nothing), гарантированно не будет превосходить длины входного списка.

Казалось бы, необходимое условие для такой гарантии — наличие зависимых типов, ну, или хотя бы какого-то их подобия, и странно было бы ожидать подобного от Rust, верно?

Встречайте — typenum. С его помощью наша функция может быть изображена вот так:

use generic_array::{ArrayLength, GenericArray};
use typenum::{IsLess, Unsigned, B1};
trait UnsignedLessThan<T> {
    fn as_usize(&self) -> usize;
}

impl<Less, More> UnsignedLessThan<More> for Less
where
    Less: IsLess<More, Output = B1>,
    Less: Unsigned,
{
    fn as_usize(&self) -> usize {
        <Self as Unsigned>::USIZE
    }
}

fn foo<El, Size>(x: GenericArray<El, Size>, y: El) -> Option<Box<dyn UnsignedLessThan<Size>>>
where
    El: Eq,
    Size: ArrayLength<El>,
{
    // 10000 строк нечитаемого кода
}

"Что это за чёртова чёрная магия?!" — спросите вы. И будете, безусловно, правы: typenum — это та ещё чёрная магия, а попытки его хоть как-то вменяемо использовать — вдвойне.

И тем не менее, сигнатура этой функции достаточно однозначна.

• Функция принимает массив элементов El длины Size и один элемент типа El.
• Функция возвращает значение Option, которое, если оно является Some,
  
  • представляет собой trait object, основанный на типаже UnsignedLessThan<T>, который принимает в качестве параметра тип Size;
  • в свою очередь, типаж UnsignedLessThan<T> реализован для всех типов, реализующих Unsigned и IsLess<T>, для которых IsLess<T> возвращает B1, т.е. true.

Иначе говоря, таким образом мы написали функцию, которая гарантированно возвращает неотрицательное (беззнаковое) число, меньшее, чем исходный размер массива (вернее, конечно, она возвращает этот самый trait object, у которого мы позже должны вызвать метод as_usize, гарантированно возвращающий такое число).

Подвохов у данного подхода ровно два:

1. Мы можем ощутимо потерять в производительности. Если вдруг по какой-то причине такая наша функция окажется на "горячем" участке программы, постоянная необходимость в динамических вызовах может оказаться одной из самых медленных операций. Впрочем, этот недостаток вполне может быть не так значителен, как кажется, но есть и второй:
2. Чтобы эта функция корректно скомпилировалась, нам потребуется либо фактически написать внутри неё самой доказательство корректности её работы, либо "обмануть" систему типов через unsafe. Первое слишком сложно для пятничной статьи, ну а второе — попросту жульничество.

Заключение

Разумеется, на практике в подобных случаях будет использоваться либо вторая реализация (принимающая срез произвольного типа), либо реализация под спойлером (принимающая итерируемый объект). Все последующие рассуждения почти наверняка не несут практического интереса и служат исключительно упражнением по работе с системой типов.

Тем не менее, сам факт, что на системе типов Rust можно суметь эмулировать одну из особенностей заведомо более сильной системы типов Idris, на мой взгляд, достаточно показателен.