Recursive type strangely resolved to never

[yukimotochern]

🔎 Search Terms

recursive never

🕗 Version & Regression Information

• This is the behavior in every version I tried, and I reviewed the FAQ for entries about recursive type.
• Every 5.x versions in playground have this behavior.

⏯ Playground Link

https://www.typescriptlang.org/play/?target=99&ts=5.4.5#code/C4TwDgpgBAKgrmANtAvFAThAhgEwPYB2iIUWBIA2gLoDcAUHaJFAIJiQE4A8AMlBAA9gETgGdYCZABpW-ISJziyIAHxQ0FAHTaeMlrQZNoASU6Dec4WIlIIatAAMAJAG8eFAOTICAc2AALDyoAXwcoAB8ody8RP0CDRnBoAHEIYC4AeUsFcTwAIwArCABjYBkABWzrUWB0AEtfCKgCOABbPIh0eygAUSF0LFKuOigocqkR5raO9Do1QStFKABrCBA8ADMoDMmAfm2KPtrB9PGp9s6VKkmALl7+k64zmvrfeflrVfWtndH9jMODyGz1qDR8V1uzQgADdOvREsx4LYMhthqMsgsclB8kVShNRgBpdT3Y5DL6bbYyFoXdBNZwuakzUIqfGwKpLTC4QjEUjkajEzn4IgkahzYkuSYABjuSOQKMyMj6xUQcBwEC4BJkpjVAi4MBULNY7AUepkqXSGS1Zl1+oNKnoowAjDL6MEKETMdYCDDOlB9o6oHdzQqoNrzLb2eJvbDaf7A1BJQk6AB6ZNySClKDAPBQHxpKCeSWSoKkcQBaCILA1LNJKAOUQAJjAYQaWf8dXEGzqyCgeTgwFz+Yc0c6DgR0FEkuJsog8olow8xbui+LrvtDFTUEd1YaYH74+xhXFk0XHmXRY8rvoRhWAbQp+vteAd4LCU324HMKwKqwwDqhAPUQX3nBMZUkWdURxRUBGVVV1WWR0rR1LhnwNPRjU4FDEKgYMoNDa0sLtdcnTuZ9XQoBDIyhGM-S3eNcMKJDzFQ95FijH1Yzou5E3hTcG04KBd33G9lgbYklRVNUuAQpjdRYx9mGAMS0DYDhuGfM00i4PCwzkx07V4tN+JwfhoW-OBf3-AhAOUmw5UgxiVgbGQlPXG9GzAY9RmlOyIO0xyJLg6TnPw5DXMNVSTSUzT0h0gjwoNB0t1IhtyNEqiR04gMgy0uKwobA0Mo42jsoTKggA

💻 Code

type Tuple = readonly any[];

type Append<L extends Tuple, A extends any> = [...L, A];

type Index<L extends Tuple> = `${L['length']}` | L['length'];

type Get<O extends object, P extends string | number> = Extract<
  P,
  number
> extends keyof O
  ? O[Extract<P, number>]
  : Extract<P, string> extends keyof O
  ? O[Extract<P, string>]
  : never;

type TupleOf<
  O extends object,
  K = Extract<keyof O, number | `${number}`>,
  T extends readonly any[] = readonly []
> = {
  0: TupleOf<O, Exclude<K, Index<T>>, Append<T, Get<O, Index<T>>>>;
  1: T;
}[K extends never ? 1 : Get<O, Index<T>> extends never ? 1 : 0];


// expect to get ['00'] as the last type `s2p` in this file but get `never`
type s0 = TupleOf<{
  '0': '00';
}>;

// 1st input
type obj = {
  '0': '00';
};
type k1 = '0';
type t1 = [];

// 1st evaluation
type s1 = {
  0: TupleOf<obj, Exclude<k1, Index<t1>>, Append<t1, Get<obj, Index<t1>>>>;
  1: t1;
}[k1 extends never ? 1 : Get<obj, Index<t1>> extends never ? 1 : 0];

// 2nd input
type k2 = Exclude<k1, Index<t1>>;
type t2 = Append<t1, Get<obj, Index<t1>>>;

// 2nd evaluation
type s2 = TupleOf<obj, k2, t2>;
type s2p = {
  0: TupleOf<obj, Exclude<k2, Index<t2>>, Append<t2, Get<obj, Index<t2>>>>;
  1: t2;
}[k2 extends never ? 1 : Get<obj, Index<t2>> extends never ? 1 : 0]

🙁 Actual behavior

typeof s0, typeof s2 are never but typeof s2p is ["00"]

🙂 Expected behavior

• typeof s2 should equal to typeof s2p
• typeof s0, typeof s2, and typeof s2p should all be ["00"]

Additional information about the issue

No response

[jcalz]

I'm wondering... what makes you think this is a bug in TypeScript and not a mistake in your complex recursive conditional types? It's not obvious to me from inspection of that code what it's supposed to do, and the fact that it apparently has this behavior for every version of TS you've tried makes it unlikely that something broke. Why would this be a problem with the language and not the code you're writing?

EDIT: If this were Stack Overflow I'd suggest this:

type TupleOf<O extends object, T extends any[] = []> =
  keyof O extends never ? T :
  TupleOf<
    Omit<O, T["length"] | `${T["length"]}`>,
    [...T, O extends Record<T["length"], infer V> | Record<`${T["length"]}`, infer V> ? V : undefined]
  >

type Z = TupleOf<{ 0: "a", 1: "b", "2": "c", 4: "d" }>
// type Z = ["a", "b", "c", undefined, "d"]

but it's not, so I'm not suggesting that 🙃 and instead I'm still wondering why this is a bug report.

[yukimotochern]

Sorry for causing confusion. I mean the last part.

type s2 = TupleOf<obj, k2, t2>;
type s2p = {
  0: TupleOf<obj, Exclude<k2, Index<t2>>, Append<t2, Get<obj, Index<t2>>>>;
  1: t2;
}[k2 extends never ? 1 : Get<obj, Index<t2>> extends never ? 1 : 0]

The s2p is the insertion of obj, k2, t2 into the definition of TupleOf, but the resulting types are different. This part is confusing to me. My understanding of generics is that they are functions that map types to types. Therefore, it is very strange that plugging the input types into definition will result in different outcome.

[jcalz]

I honestly have not tried to step through that thing.

But do keep in mind that distributive conditional types only happen when the checked type is a generic type parameter. The type type X<T> = T extends U ? A : B; type Y = X<V> behaves differently from type Y= V extends U ? A : B when V is not a generic type. That could easily cause a "I plugged this into the definition and it changed" behavior. But if that's the case then this is definitely not a bug in TypeScript.

I'd say that you should try condensing your example into something minimal; the least complex thing that demonstrates the same issue you're having. Then, if you don't understand it, assume first that it's a problem with your understanding and not with TypeScript, and ask on Stack Overflow or the TS Discord about it. At some point you might isolate a behavior that is genuinely confusing or inexplicable or incorrect to you and others... and then it would be a good time to consider opening a bug report here. Right now I'd recommend closing this and doing that.

But: I'm not a TS team member, just an annoying interested third party. So you could always just wait for official word.

[yukimotochern]

I honestly have not tried to step through that thing.

But do keep in mind that distributive conditional types only happen when the checked type is a generic type parameter. The type type X<T> = T extends U ? A : B; type Y = X<V> behaves differently from type Y= V extends U ? A : B when V is not a generic type. That could easily cause a "I plugged this into the definition and it changed" behavior. But if that's the case then this is definitely not a bug in TypeScript.

I'd say that you should try condensing your example into something minimal; the least complex thing that demonstrates the same issue you're having. Then, if you don't understand it, assume first that it's a problem with your understanding and not with TypeScript, and ask on Stack Overflow or the TS Discord about it. At some point you might isolate a behavior that is genuinely confusing or inexplicable or incorrect to you and others... and then it would be a good time to consider opening a bug report here. Right now I'd recommend closing this and doing that.

But: I'm not a TS team member, just an annoying interested third party. So you could always just wait for official word.
@jcalz You are correct. Thank you very much.
The issue is in the distributive conditional types. The below will fix the issue.

type TupleOf<
  O extends object,
  K = Extract<keyof O, number | `${number}`>,
  T extends readonly any[] = readonly []
> = {
  0: TupleOf<O, Exclude<K, Index<T>>, Append<T, Get<O, Index<T>>>>;
  1: T;
}[[K] extends [never] ? 1 : [Get<O, Index<T>>] extends [never] ? 1 : 0];