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

Пару дней назад 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), состоящие из любых элементов, которые мы можем сравнивать на равенство. Явный полиморфизм почти всегда лучше неявного и почти всегда лучше его отсутствия, не так ли?

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

fn refl<El: PartialEq + Copy>(el: El) -> Option<usize> {
    foo(&[el], el) // should always return Some(0), right?
}
#[test]
fn dont_find_nan() {
    assert_eq!(refl(std::f64::NAN), None);
}

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

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

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

Лирическое отступление: we want to go MORE generic!

Этот вариант не имеет отношения к исходной задаче, зато является, на мой взгляд, хорошей иллюстрацией к принципу: "be liberal in what you accept, be conservative in what you do". Иначе говоря: если есть возможность без ущерба для эргономики и производительности сделать тип принимаемых значений более общим — есть смысл именно так и поступить.

Рассмотрим вот такой вариант:

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

Что мы теперь знаем об этой функции? Всё то же самое, только теперь она принимает на вход не список и не срез, а какой-то произвольный объект, который можно заставить выдавать поочерёдно ссылки на объекты типа El и сравнивать их с искомым: аналогом в Java, если я правильно помню, была бы функция, принимающая Iterable<Comparable>.

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

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

Короче говоря, нам нужен 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, гарантированно возвращающий такое число).

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

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

Заключение

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

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