Как TypeScript проверяет равенство для бесконечных рекурсивных типов?

Как 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

ссылка на детскую площадку

Это сводится как минимум к двум вопросам:

  1. Как TS проверяет, что L можно присвоить LL (и наоборот).

  2. Как TS проверяет, что L расширяет LL (и наоборот)

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

Я ищу какой-нибудь псевдокод или текстовое описание алгоритма, который можно применить к примеру.

нашел этот PR github.com/microsoft/TypeScript/pull/33050, я его не читал, поэтому не уверен, что он объясняет некоторые технические детали.

ABOS 20.12.2020 15:27
Зод: сила проверки и преобразования данных
Зод: сила проверки и преобразования данных
Сегодня я хочу познакомить вас с библиотекой Zod и раскрыть некоторые ее особенности, например, возможности валидации и трансформации данных, а также...
Как заставить Remix работать с Mantine и Cloudflare Pages/Workers
Как заставить Remix работать с Mantine и Cloudflare Pages/Workers
Мне нравится библиотека Mantine Component , но заставить ее работать без проблем с Remix бывает непросто.
Угловой продивер
Угловой продивер
Оригинал этой статьи на турецком языке. ChatGPT используется только для перевода на английский язык.
TypeScript против JavaScript
TypeScript против JavaScript
TypeScript vs JavaScript - в чем различия и какой из них выбрать?
Синхронизация localStorage в масштабах всего приложения с помощью пользовательского реактивного хука useLocalStorage
Синхронизация localStorage в масштабах всего приложения с помощью пользовательского реактивного хука useLocalStorage
Не все нужно хранить на стороне сервера. Иногда все, что вам нужно, это постоянное хранилище на стороне клиента для хранения уникальных для клиента...
Что такое ленивая загрузка в Angular и как ее применять
Что такое ленивая загрузка в Angular и как ее применять
Ленивая загрузка - это техника, используемая в Angular для повышения производительности приложения путем загрузки модулей только тогда, когда они...
3
1
324
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Алгоритм, о котором вы говорите, описан в документах здесь

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

Max Heiber 20.12.2020 16:50

@MaxHeiber, ты прав, я сделал обновление. Может быть, это поможет вам

captain-yossarian from Ukraine 20.12.2020 17:12
Ответ принят как подходящий

Ваша интуиция о том, как происходит завершение, верна. 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. Можно ли присвоить L1LL1?
А-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 совместим, даже если все остальные реквизиты определенно совместимы.

Спасибо! Часть, которую я упускал, отсутствовала раньше, это то, что происходит, когда «Может быть» идет до конца — довольно круто.

Max Heiber 21.12.2020 10:00

Другие вопросы по теме