Как TypeScript проверяет равенство для бесконечных рекурсивных типов?
Пример:
// LL is the same as L unfolded once
type L = [] | {item: number, next: L}
type LL = [] | {item: number, next: ({item: number, next: LL} | [])}
// An L is assignable to an LL
declare const L1: L
const LL1: LL = L1
// An LL is assignable to an L
declare const LL2: LL
const L2: L = LL2
type Interassignable<T, U> = T extends U ? U extends T ? true : never : never
declare const check: Interassignable<L, LL>
const x: true = check // OK
Это сводится как минимум к двум вопросам:
Как TS проверяет, что L можно присвоить LL (и наоборот).
Как TS проверяет, что L расширяет LL (и наоборот)
Я думаю, что ответ может быть таким же, и что это как-то связано с кэшированием рекурсивных типов, чтобы избежать проверки навсегда, но я не уверен в деталях.
Я ищу какой-нибудь псевдокод или текстовое описание алгоритма, который можно применить к примеру.
Алгоритм, о котором вы говорите, описан в документах здесь
Основное правило для системы структурных типов TypeScript состоит в том, что x совместим с y, если y имеет по крайней мере те же элементы, что и x.
Чтобы проверить, может ли y быть присвоено x, компилятор проверяет каждое свойство x, чтобы найти соответствующее совместимое свойство в y.
Вернемся к вашему примеру.
// LL is the same as L unfolded once
type L = [] | { item: number, next: L }
/**
* It s because here you went one level deeper, but type is practicaly the same
*/
type LL = [] | { item: number, next: ({ item: number, next: LL } | []) }
L
и LL
оба могут быть пустым массивом или объектом с двумя свойствами.Вот небольшой пример:
type A = [] | {}
type B = [] | {}
let a: A = []
let b: B = {}
a = b // a can be an empty object as well
b = a // b can be an empty array as well
L
и LL
также могут быть объектами со свойством item
и свойством next
.Итак, компилятор TS идет к L
и спрашивает:
ТС: Хей L
, могу я относиться к тебе как к объекту с двумя свойствами?
Л: Конечно, можете, потому что я был введен как объект с двумя свойствами (item
и next
).
ТС: Хей, LL
, могу я относиться к тебе как к объекту со свойствами item
и next
?
LL: Конечно, это мой тип. Вы даже можете обращаться со мной как с пустым массивом.
ТС: Хорошо, L
и LL
, может быть, я могу относиться к вам как к пустому массиву?
Л,ЛЛ: Никаких проблем )
Поскольку TS имеет систему структурных типов, оба типа обрабатываются одинаково.
Я так понимаю этот алгоритм.
ОБНОВЛЕНИЕ для рекурсии Я не могу объяснить это лучше, чем документы
Но обходной путь введения интерфейса не был интуитивно понятным для пользователей. И в принципе не было ничего плохого в исходной версии ValueOrArray, которая напрямую использовала Array. Если бы компилятор был немного «ленивее» и вычислял аргументы типа для массива только при необходимости, то TypeScript мог бы правильно выразить их.
Это именно то, что представляет TypeScript 3.7. На «верхнем уровне» псевдонима типа TypeScript будет откладывать разрешение аргументов типа, чтобы разрешить эти шаблоны.
До TS 3.7 была линитация:
Раньше вы не могли ссылаться на определяемый вами тип внутри самого типа.
Начиная с TS 3.7 вы можете это сделать. Раньше, чтобы сделать рекурсивный тип, вы должны были использовать интерфейс вместе с типом.
Пример:
type ValueOrArray2<T> = T | ArrayOfValueOrArray<T>;
interface ArrayOfValueOrArray<T> extends Array<ValueOrArray2<T>> {}
Насколько я понимаю, ТС делает псевдоним, если вы ссылаетесь на сам тип (косвенная ссылка)
Чтобы лучше понять, как работают рекурсивные типы, вы можете проверить эти тесты
Я не знаю настолько хорошего репозитория TS, чтобы сделать пошаговый анализ этого алгоритма.
Спасибо, но я спросил о проверках присваиваемости для бесконечно рекурсивных типов и привел пример использования type Interassignable<T, U> = T extends U ? U extends T ? true : never : never
, применяемого к LL и L. Я не понимаю, как алгоритм, который вы набросали, завершится. В исходном посте я предположил, что есть какое-то кэширование, чтобы остановить бесконечный регресс.
@MaxHeiber, ты прав, я сделал обновление. Может быть, это поможет вам
Ваша интуиция о том, как происходит завершение, верна. Typescript действительно имеет способ ограничить рекурсию. Рабочая лошадка проверки совместимости — isRelatedTo
в checker.ts
. Эта функция возвращает один из False
, Unknown
, Maybe
или True
. True
и False
довольно явные, они используются, когда отношение может быть определено однозначно. Maybe
это то, что нас интересует. Maybe
используется, когда во время сравнения встречаются два типа, которые в настоящее время сравниваются. Чтобы отслеживать это, компилятор будет хранить массив отношений, которые он рассматривает в данный момент.
Имея это в виду, давайте рассмотрим более простой рекурсивный пример:
type L = { next: L}
type LL = { next: ({ next: LL})}
declare const L1: L
const LL1: LL = L1
Как компилятор определит, что L1
можно присвоить LL1
:
В-1. Можно ли L1
присвоить LL1
?
В-2. Только если L.next
и LL.next
присваиваемы, так они и есть?
В-3. Можно ли присвоить L { next: LL}
?
В-4. Только если L.next
и { next: LL}.next
присваиваемы
В-5. Можно ли присвоить L1
LL1
?
А-5. Поскольку это то, что мы рассматриваем в 1. Предположим, что они есть, поэтому вернитесь Maybe
А-4. Их типы могут быть совместимы, так что они могут быть, так что вернитесь Maybe
А-3. Так как ни одно из их свойств точно не совместимо, а одно свойство было Maybe
, может они и есть, поэтому возвращаем Maybe
А-2. Их типы могут быть совместимы, так что они могут быть, так что вернитесь Maybe
А-1. Поскольку мы не обнаружили определенной несовместимости, их можно назначить.
(Чрезмерно) упрощенная версия кода на псевдокоде будет выглядеть так:
interface Type { id: string, properties: Map<string, { type: Type}> }
enum Ternary {
True = -1,
False = 0,
Maybe = 3
}
function checkTypeRelatedTo(source: Type, target: Type){
let maybeRelated: string[]
return isRelatedTo(source, target) != Ternary.False;
function isRelatedTo(source: Type, target: Type): Ternary {
const relationId = source.id + "," + target.id;
if (maybeRelated.indexOf(relationId) != -1) {
return Ternary.Maybe
}
maybeRelated.push(relationId);
const result = structureRelatedTo(source, target);
maybeRelated.pop();
return result;
}
function structureRelatedTo(source: Type, target: Type): Ternary{
let result = Ternary.True;
for(const prop of target.properties.keys()) {
result &= isRelatedTo(source.properties.get(prop)!.type, target.properties.get(prop)!.type)
if (!result){
return Ternary.False
}
}
return result;
}
}
Добавление дополнительных членов и объединения принципиально не меняет этот алгоритм, а просто добавляет дополнительные слои сверху. Союз считается совместимым, если любая составляющая одного союза совместима с любой составляющей другого союза. И совместимость участников тоже не сильно на это влияет. Если один элемент Maybe
совместим, то весь тип Maybe
совместим, даже если все остальные реквизиты определенно совместимы.
Спасибо! Часть, которую я упускал, отсутствовала раньше, это то, что происходит, когда «Может быть» идет до конца — довольно круто.
нашел этот PR github.com/microsoft/TypeScript/pull/33050, я его не читал, поэтому не уверен, что он объясняет некоторые технические детали.