← Глава 21. Шаблонные литеральные типы Содержание Глава 23. Утилитные типы изнутри →

Глава 22. Рекурсия и пределы

Глава 22. Рекурсия и пределы

Как глубоко это заходит — и как глубоко стоит лезть

К этой главе в руках уже есть весь набор: условные типы и infer (Глава 19), сопоставленные типы (Глава 20), шаблонные литералы (Глава 21). Каждый из них работает на одном уровне. Readonly<T> помечает поля верхнего уровня readonly — и останавливается, не заглядывая внутрь:

type Order = {
  id: string;
  total: number;
  shipping: { address: string; city: string };
};

type RO = Readonly<Order>;
// { readonly id: string; readonly total: number;
//   readonly shipping: { address: string; city: string } }
//                      ^ внутренний объект остался изменяемым

shipping стал readonly, но то, на что он указывает, — нет. ro.shipping.city = "..." пройдёт проверку. Сопоставленный тип прошёл по ключам один раз и не нырнул глубже, потому что не умеет: [K in keyof T] — это один проход, плоский цикл по верхнему слою.

Та же стена встаёт, когда нужно разобрать строку до конца. Шаблонный литерал вытащит первый сегмент пути /users/:id/posts/:postId, но путь — это произвольное число сегментов, а одно сопоставление с образцом ловит фиксированное их количество. Чтобы достать все параметры, нужно повторять разбор, пока строка не кончится, — а сколько раз повторять, заранее неизвестно.

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

type DeepReadonly<T> = {
  readonly [K in keyof T]: DeepReadonly<T[K]>;
};

type DRO = DeepReadonly<Order>;
// total и id остаются number/string, а shipping становится
// { readonly address: string; readonly city: string } — насквозь

Тип DeepReadonly упомянул сам себя внутри собственного определения, и проверяющий пошёл по структуре вглубь, применяя одно и то же преобразование на каждом уровне, пока не упёрся в примитивы. Один и тот же приём — самоссылка — даёт не только глубокие преобразования. Им считают арифметику. Им парсят строки. Им пишут мини-интерпретаторы целых языков, работающие во время проверки типов. Система типов, которую вы знали как способ описывать формы, оказывается способом вычислять.

Это первая половина главы — что так можно. Вторая, не менее важная, — докуда это доходит, где язык встаёт, и где раньше языка должен встать ты.

Рекурсия: тип, ссылающийся на себя

Разберём DeepReadonly по шагам, потому что в нём собрана вся механика. Проверяющий, разворачивая DeepReadonly<Order>, делает следующее. Берёт каждый ключ T. Берёт тип значения под этим ключом — T[K]. И вместо того чтобы оставить его как есть, оборачивает в DeepReadonly<T[K]> — тот же тип, что разворачивается прямо сейчас. Для id значение — string; DeepReadonly<string> проходит по keyof string (методы строки) и по сути возвращает string. Для shipping значение — объект, и DeepReadonly спускается в него ровно так же. Рекурсия останавливается сама, когда T[K] — примитив: у него нет интересной структуры, разворачивать дальше нечего.

Это рекурсия по структуре — она следует за вложенностью данных. Есть и второй вид, более похожий на привычный цикл: рекурсия по кортежу. Она опирается на то, что кортеж можно разобрать на голову и хвост через infer со спред-элементом.

type Head<T extends unknown[]> =
  T extends [infer H, ...unknown[]] ? H : never;

type H = Head<[1, 2, 3]>; // 1

[infer H, ...unknown[]] читается как «первый элемент назови H, остальные — что угодно». Симметрично достаётся хвост:

type Tail<T extends unknown[]> =
  T extends [unknown, ...infer Rest] ? Rest : [];

type R = Tail<[1, 2, 3]>; // [2, 3]

Имея голову и хвост, можно крутить цикл: обработай голову, рекурсивно обработай хвост, останавливайся на пустом кортеже. Развернём кортеж задом наперёд:

type Reverse<T extends unknown[]> =
  T extends [infer Head, ...infer Rest]
    ? [...Reverse<Rest>, Head] // хвост развёрнут, голову — в конец
    : [];                      // база: пустой кортеж развёрнут сам в себя

type Rev = Reverse<[1, 2, 3]>; // [3, 2, 1]

Здесь видна вся анатомия типовой итерации. Условный тип T extends [...] — это if: есть ли ещё элемент. Деструктуризация [infer Head, ...infer Rest] — это шаг: отделить текущий элемент от остатка. Самоссылка Reverse<Rest> — это переход к следующей итерации на уменьшенном входе. Ветка : [] — база рекурсии, условие выхода. Каждый виток работает на кортеже на один элемент короче, рано или поздно приходит к [], и развёртка сходится.

Часто удобнее не строить результат на возврате, а накапливать его в дополнительном параметре — паттерн аккумулятора, знакомый по функциональному программированию. Тот же Reverse, но с аккумулятором:

type Reverse<T extends unknown[], Acc extends unknown[] = []> =
  T extends [infer Head, ...infer Rest]
    ? Reverse<Rest, [Head, ...Acc]> // голову — в начало аккумулятора
    : Acc;                          // вход кончился — отдаём накопленное

type Rev = Reverse<[1, 2, 3]>; // [3, 2, 1]

Acc стартует пустым, на каждом шаге в его начало дописывается текущая голова, и когда вход иссяк, аккумулятор и есть ответ. Разница не косметическая. В первой версии рекурсивный вызов завёрнут в [...Reverse<Rest>, Head] — проверяющему нужно держать незавершённый контекст на каждом уровне вложенности, дожидаясь, пока вернётся внутренний вызов, чтобы достроить кортеж вокруг него. Во второй вся работа сделана до рекурсивного вызова, и Reverse<Rest, ...> стоит на последней позиции — ничего не ждёт. Это хвостовая позиция, и компилятор умеет на ней разворачивать рекурсию плоско, не накапливая контекст. К тому, почему это решает судьбу глубоких рекурсий, вернёмся ниже; пока достаточно запомнить, что форма аккумулятора — не стилистический выбор.

Соберём из этого что-то осмысленнее перестановки. Разбор пути в типе параметров — ровно та задача, на которой споткнулся шаблонный литерал в начале главы. Теперь шаблон даёт шаг, рекурсия — повторение:

type Params<Path extends string> =
  Path extends `${string}:${infer Param}/${infer Rest}`
    ? Param | Params<`/${Rest}`>      // нашли :param — собираем дальше
    : Path extends `${string}:${infer Param}`
      ? Param                          // последний :param в конце строки
      : never;                         // параметров больше нет

type P = Params<"/users/:id/posts/:postId">; // "id" | "postId"

Шаблонный литерал отрывает один сегмент :Param, рекурсия применяет тот же разбор к остатку, объединение | копит найденное. Параметров может быть сколько угодно — тип это переживёт, потому что не привязан к их числу. Это и есть обещанное в начале: один приём, самоссылка, поднимает одноуровневые инструменты до работы на произвольной глубине.

Что вычислимо — и что это значит

Стоит увидеть, как далеко это заходит, потому что граница проходит не там, где ожидаешь. В системе типов нет чисел в обычном смысле — точнее, есть числовые литералы, но над ними нет арифметики: написать A + B в типе нельзя. И всё же сложение строится — через длину кортежа. Число N представляют кортежем длины N, сложение — конкатенацией.

// кортеж из N элементов
type Tuple<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : Tuple<N, [unknown, ...Acc]>;

type Add<A extends number, B extends number> =
  [...Tuple<A>, ...Tuple<B>]["length"];

type Seven = Add<3, 4>; // 7

Tuple<3> рекурсивно набирает [unknown, unknown, unknown], проверяя на каждом шаге Acc["length"] extends N. Сложение склеивает два таких кортежа и спрашивает длину готового — ["length"] возвращает числовой литерал. Из сложения тем же манером выводят вычитание, умножение, сравнение. Получается арифметика — медленная, ограниченная небольшими числами, но настоящая, целиком внутри проверяющего.

Если в типах считается арифметика, разбираются строки и обходятся произвольные структуры, напрашивается вывод, и он верен: система типов TypeScript, с оговорками, тьюринг-полна. На ней писали парсеры JSON, выдающие типизированный результат из строкового литерала. Писали интерпретаторы маленьких языков. Писали игру, ходы которой — это типы. Всё это исполняется не в рантайме — в рантайме типов нет, как помним из Главы 3, — а внутри tsc, во время проверки, и не оставляет в выходном .js ни байта.

Важно, что здесь сказано и что нет. Сказано: это можно. Не сказано: это нужно. Разница между двумя утверждениями — нерв всей главы. То, что язык вычислений у тебя в руках, не делает каждую задачу задачей для него. С этого момента восхищение и дисциплина идут вместе, и вторая важнее первой.

Где останавливается язык

У вычислителя есть жёсткие пределы, и наткнуться на них легко. Самый известный — глубина рекурсии. Проверяющий не разворачивает самоссылку бесконечно; на некотором уровне вложенности он сдаётся и сообщает об этом:

type Tuple<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : Tuple<N, [unknown, ...Acc]>;

type Big = Tuple<1000>;
// Error: Type instantiation is excessively deep and possibly infinite. ts(2589)

Tuple<1000> потребовал бы около тысячи витков рекурсии, и проверяющий упёрся в свой лимит — исторически порядка нескольких десятков уровней для общего случая. Сообщение «Type instantiation is excessively deep and possibly infinite» — это не утверждение, что тип неверен. Это признание: «глубже я не пойду, и я не могу отличить твою честную рекурсию от той, что не закончится никогда». Лимит существует именно потому, что отличить в общем случае невозможно: остановка рекурсивного типа — задача неразрешимая, и компилятор обязан где-то поставить искусственную стену, чтобы не зависнуть навсегда.

Стену отчасти отодвигает хвостовая форма. Та самая хвостовая позиция из аккумуляторного Reverse — это не только про стиль: для условных типов в хвостовой позиции компилятор применяет устранение хвостовой рекурсии (tail-recursion elimination), разворачивая её плоско, без накопления контекста на каждом уровне. Это поднимает практический потолок с десятков витков до тысяч.

// хвостовая форма: рекурсивный вызов — последнее, что делает ветка
type Tuple<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : Tuple<N, [unknown, ...Acc]>;
//                                ^ Tuple<...> в хвостовой позиции

type Big = Tuple<999>; // проходит — благодаря плоской развёртке

Но это смягчение, а не снятие предела. Во-первых, потолок всё равно есть, просто выше. Во-вторых — и это важнее — хвостовая оптимизация хрупка. Она срабатывает, только когда рекурсивный вызов стоит ровно последним в ветке. Стоит обернуть его хоть во что-то — [...Self<Rest>, X], объединение, лишнее условие, — и оптимизация молча отключается, потолок обрушивается обратно к десяткам, а тип, который вчера компилировался, сегодня выдаёт ts(2589). Никакого предупреждения «вы потеряли хвостовую форму» не будет; будет внезапная ошибка глубины на входе, который раньше проходил.

Глубина — предел резкий, с понятным сообщением. Есть второй, коварнее, потому что не выдаёт ошибки вовсе, — производительность. Рекурсивный тип, который компилируется, может компилироваться долго. На N=10 всё мгновенно; на N=50 тот же тип заставляет tsc думать секунды, IDE — подвисать на каждое нажатие, а память — расти. Граница тут не бинарная «работает / не работает», а плавная деградация: сначала редактор чуть медленнее предлагает автодополнение, потом подсветка ошибок отстаёт, потом наведение на тип крутит спиннер. Язык не останавливается — останавливается комфортная работа с ним, и это происходит без единого сообщения об ошибке. Зелёная сборка, которая собирается минуту, — тоже сигнал, что ты у предела, просто предел этот тихий.

Где должен остановиться ты

Жёсткие пределы языка — ts(2589), лаги, память — это граница, дальше которой нельзя. Но есть граница ближе, дальше которой не стоит, и проходит она задолго до технической стены. Чтобы её увидеть, надо честно назвать, что такое сложный типовой код как артефакт.

Типовая программа — это код. Но код без всего, что делает код сопровождаемым. У него нет тестов: нельзя написать модульный тест на DeepReadonly, можно лишь насоздавать проверочных типов и глазами смотреть, те ли. Нет отладчика: нельзя поставить точку останова внутри разворачивающейся рекурсии и посмотреть, чему равен Acc на сороковом витке. Нет читаемых ошибок: когда сложный тип не сходится, сообщение — это страница вложенных условных типов, в которой настоящая причина похоронена под механикой развёртки. Нет нормального способа прочесть результат: всплывающая подсказка над переменной показывает не аккуратный Order, а развёрнутую кашу из DeepReadonly<...>, которую невозможно охватить взглядом.

Из этого следует трезвое правило: когда типовое решение стало уродливым — длинным, многоэтажным, медленным, нечитаемым, — это не повод его дошлифовывать, а сигнал, что выбран не тот инструмент. Почти всегда есть выход дешевле:

Есть и разделение по ролям, которое снимает половину споров. Автор библиотеки и автор приложения находятся в разном положении. Когда условный тип внутри популярной библиотеки даёт её тысячам потребителей точный вывод без единой аннотации с их стороны, сложность этого типа написана один раз, а окупается многократно — издержки амортизированы по всей экосистеме. Тот же по сложности тип внутри прикладного кода, который увидят три человека в команде, — почти наверняка переусложнение: цена платится здесь и сейчас, выигрыш мелкий, а сопровождать это придётся тем же троим. Виртуозная рекурсия уместна там, где её один раз пишут и постоянно переиспользуют; в коде приложения она чаще симптом, что автор увлёкся.

Старшее умение в этой части книги — не написать самый хитрый тип, а вовремя не написать его. Сдержанность, а не виртуозность.

Глазами джависта

Соблазнительно поискать в Java аналог и обнаружить, что искать нечего — и это честнее всего сказать прямо, без злорадства в обе стороны.

Система типов Java не является практическим вычислителем. Дженерики с extends, wildcards, рекурсивные границы вроде <T extends Comparable<T>> — всё это параметрический полиморфизм, способ ограничивать и связывать типы, а не считать ими. На дженериках Java не построить DeepReadonly, прошивающий структуру насквозь, не разобрать строковый литерал на параметры пути, не сложить два числа во время компиляции. Не потому, что джависты до этого не додумались, а потому, что в языке нет conditional-типов, нет infer, нет сопоставленных и шаблонных типов — нет ветвления и деструктуризации на уровне типов, без которых рекурсия типу ничего не даёт. Когда джависту нужно то, что в TS делает рекурсивный тип, он берёт другой инструмент: кодогенерацию (аннотации и annotation processor, порождающие классы) или рефлексию (разбор структуры в рантайме). Оба обходят систему типов, а не работают внутри неё.

Отсюда симметричный вывод, и обе его половины верны. TypeScript даёт силу, которой у Java нет: тип может вычислять, и из этого вырастают точные API, выводящие форму результата из формы аргументов без единой ручной аннотации. И TypeScript даёт грабли, которых у Java быть не может: на типах можно написать нечитаемый тормозящий несопровождаемый вычислитель — и соблазн это сделать реален. Джавист никогда не вырабатывал в себе правило «не перепрограммируй систему типов», потому что язык не давал такой возможности — соблазна не существовало. Здесь это правило приходится осваивать с нуля, и осваивать рано. Тьюринг-полные типы — благо смешанное: чаще предмет восхищения, чем глубокого повседневного применения, и взрослое отношение к ним ближе к осторожности, чем к энтузиазму.

Где рекурсия кусается

Соберём ловушки в одном месте, потому что каждая из них однажды испортит кому-то день, и лучше узнать их заранее.

ts(2589) приходит не в тесте, а в бою. Глубина срабатывает, когда размер входа переходит порог. Пока в тестах гоняют Tuple<5> и путь из двух сегментов, всё зелено. На боевой форме — кортеж из сотни элементов, путь из десятка параметров, глубоко вложенный объект конфигурации — рекурсия пробивает потолок, и тип, написанный и проверенный месяц назад, впервые падает на реальных данных. Порог входа, а не порог разработки, решает, когда вылезет ошибка.

Хвостовая оптимизация рассыпается от рефакторинга. Она держится на том, что рекурсивный вызов стоит ровно последним. Безобидное на вид изменение — обернуть результат в кортеж, добавить ветку, объединить с чем-то — молча её отключает, и глубина, которая вчера была тысячи, сегодня десятки. Ошибка вылезает не в строке, которую трогали, а на старом входе, который перестал проходить. Связь между правкой и поломкой неочевидна.

Производительность обрывается нелинейно. Норма на N=10 ничего не говорит о N=50: стоимость многих типовых вычислений растёт быстрее линейного, и переход от мгновенного к невыносимому случается на узком участке. Хуже, если внутри рекурсии работает распределение по объединению (distributive conditional types, Глава 19): каждый член входного union’а запускает собственную ветку рекурсии, и стоимости перемножаются. Union из десяти членов под рекурсивным типом — это не в десять раз дороже, это потенциально в разы хуже, чем кажется.

Отладки практически нет. Когда рекурсивный тип даёт не тот результат, нет ни точки останова, ни пошагового исполнения, ни лога промежуточных значений. Остаётся вручную инстанцировать тип на маленьких входах и сравнивать ожидаемое с полученным во всплывашке — то есть отлаживать вычисление через присматривание за ним глазами.

Нечитаемый результат бьёт по потребителю. Даже корректный сложный тип наказывает того, кто им пользуется: наведение на переменную показывает не имя, а развёрнутую простыню DeepReadonly<{ ... }> или цепочку условных типов на пол-экрана. Сообщения об ошибках в коде потребителя начинают ссылаться на внутренности твоей рекурсии. Сложность, спрятанная в тип, не исчезает — она протекает наружу в каждую подсказку IDE.

Ничего из этого не значит «не пользуйся рекурсией». Это значит — пользуйся, зная цену, и держи её в поле зрения с самого начала, а не открывай для себя в день, когда боевая форма впервые превысила порог.

Почти язык — но без тестов, отладчика и читаемых ошибок; знай, где встать

Переключатель этой главы — двойной, и обе его половины нужно повернуть разом.

Первая половина: рекурсия достраивает систему типов до почти полноценного языка вычислений. Самоссылающийся тип в связке с ветвлением (Глава 19) и деструктуризацией кортежей превращает одноуровневые инструменты в инструменты произвольной глубины — и этим можно считать, парсить, преобразовывать формы насквозь. Это не фокус и не злоупотребление; это законная и иногда незаменимая сила языка.

Вторая половина: это язык без страховочной сетки. Без тестов, без отладчика, без читаемых ошибок, дорогой в сопровождении и склонный к тихой деградации производительности. Из чего следует рабочая дисциплина, а не запрет:

Знать, где встаёт язык, и где раньше языка должен встать ты, — то самое умение, к которому вела вся четвёртая часть. Оно же — мост к шестой, где речь пойдёт о вкусе: о том, когда доверять выводу, а когда писать явно, и где проходит граница между мощью и её злоупотреблением (Часть VI). Тот, кто умеет не только вычислять типами, но и вовремя убирать руки от клавиатуры, владеет этим языком, а не одержим им.

Итог

Рекурсия превращает систему типов в почти полноценный язык — но язык без тестов, отладчика и читаемых ошибок, с тихими обрывами на глубине и на производительности. Зрелое мастерство здесь не в том, чтобы вычислить типами всё, что вычислимо, а в том, чтобы вовремя остановиться: владеет частью IV тот, кто знает, где встаёт компилятор и где раньше него должен встать он сам.

← Глава 21. Шаблонные литеральные типы Содержание Глава 23. Утилитные типы изнутри →