Typescript: Type alias circularly references itself

[pelotom]

Why does this work:

type Foo = { x: Foo }

but this doesn't:

type Bar<A> = { x: A }
type Foo = Bar<Foo>
//   ^^^ Type alias 'Foo' circularly references itself

Shouldn't they be equivalent?

[tycho01]

See the explanation here for more info.

[RyanCavanaugh]

type Foo = Bar<Foo>

Illegal because we don't know that the definition of Bar isn't

type Bar<T> = T;

[pelotom]

Don't you have access to the definition of Bar so you could check that?

[RyanCavanaugh]

Bar might be

type Bar<T> = Foo<T>;

and now we're going infinitely deep.

Type aliases and interfaces are subtly different and there are rules about self-recursion for aliases that don't apply to interfaces. Because an alias is supposed to always be "immediately expandable" (it's as if it were an in-place expansion of its referand), there are things you can do interfaces you can't do with type aliases.

[pelotom]

Cycles can be detected and you can give up at that point, but as long as you can topologically order the type aliases by their references to one another it's fine. Haskell, PureScript, Scala etc have no problem with this.

[RyanCavanaugh]

I mean, we could, it's just that writing interface Bar<T> extends Foo<T> { } accomplishes the same thing without requiring us to rearchitect how type aliases work

[pelotom]

Sure, you can do that to emulate

type Foo = Bar<Foo>

But what about

type Foo = Bar<Foo> | Baz<Foo>

In this situation afaict the only solution is to expand the definitions of Bar and Baz into the union, substituting Foo for their type variable. Bar and Baz (and however many other alternatives) could be large complex interfaces, and must now each be maintained as 2 separate copies that must be kept in sync with one another.

[skreborn]

I'm trying to create a type that circularly references itself, but in a way that it makes sense - or at least it does to me. This is basically the same problem as @pelotom is having.

type Data = number | string | Data[] | Record<string, Data>;

If I modify it to the following, it works as intended, but this really is just more work for the user. This gets even worse when the data types are more complicated than a simple key-value pair.

type Data = number | string | { [key: number]: Data } | { [key: string]: Data };

This type allows me to create values like the following and handle them in a type safe way even when they are deeply nested.

const data: Data = {
    foo: [ 1, 'one', { two: 2 } ],
    bar: 'foobar'
};

@RyanCavanaugh Is there any other (sane) way to create type-safe nested objects?

[mhegazy]

Automatically closing this issue for housekeeping purposes. The issue labels indicate that it is unactionable at the moment or has already been addressed.

[pelotom]

I think this is a reasonable feature request for reasons that are made clear in the comments, can we reopen please?

[brandonbloom]

I think aleksey-bykov nailed the primary goal use case in this comment:
https://github.com/Microsoft/TypeScript/issues/6230#issuecomment-167023181

type Json = null | string | number | boolean | Json[] | { [name: string]: Json }

[zpdDG4gta8XKpMCd]

please stop bringing this silly "going infinitely deep" excuse, will you? we are all mature developers to know how to deal with it, aren't we?

[zpdDG4gta8XKpMCd]

@brandonbloom the json problem was solved without recursive types, was posted somewhere in the issues

[RyanCavanaugh]

please stop bringing this silly "going infinitely deep" excuse, will you? we are all mature developers to know how to deal with it, aren't we?

Definitely 😆

[zpdDG4gta8XKpMCd]

come on, if you know you going deep you can prevent it, if you dont then you will see those overflows and thrn you know, it is not a stopper by any means or not an excuse

moreover if a problem is so bad maybe it makse sense to add some static checks to see where tge problem is likely to arise?

and why are so few new features to typescript been made lately, are you guys on a cut budget?

[RyanCavanaugh]

Lots of summer vacations, some parental leave, slightly more staff turnover than usual, and mapped types had a substantial bug tail that's taken a lot of time.

[pelotom]

I appreciate the TypeScript team's hard work. Mapped types have been a great addition and well worth the added complexity and corner cases!

[thorn0]

Is it the same issue? playground

// Error: Type alias 'DeepPartial' circularly references itself
type DeepPartial<T> = T extends Array<infer U>
  ? Array<DeepPartial<U>>
  : T extends ReadonlyArray<infer U>
    ? ReadonlyArray<DeepPartial<U>>
    : T extends Date
      ? T
      : { [P in keyof T]?: DeepPartial<T[P]> };

upd: found working DeepPartial here

[donaldpipowitch]

I also wonder if I hit this bug or if it is different (modified example from this Tweet):

type FormValue<T> = { value: T }; // potentially many more fields

type FormModel<T> =
    //T extends Array<infer U> ? { value: FormModel<U>[] } : // THIS WORKS
    T extends Array<infer U> ? FormValue<FormModel<U>[]> :   // THIS ERRORS
    T extends object ? FormValue<FormModelObject<T>> :
    FormValue<T>;

type FormModelObject<T> = {
    [key in keyof T]: FormModel<T[key]>;
};

const model: FormModel<{
    bar: string,
    baz: {
        foo: string
    },
    items: string[]
}> = {} as any;

model.value.bar.value.toLowerCase();
model.value.baz.value.foo.value.toLowerCase();
model.value.items.value.map(item => item.value.toLowerCase());

(Playground)

I wonder if there is a solution were I can re-use FormValue for the array-case instead of re-writing it...?

---

Update: Looks like I found a solution in the DeepPartial comment from above. See this new example. Works, but was hard to figure out.

[kgtkr]

The maximum value of recursion is solved like Rust-recursion_limit

#![recursion_limit = "1024"]

[tycho01]

for visibility to others finding this thread in an attempt to pull off recursion, see @fightingcat's trick to get the compiler to overlook the recursion.

[zpdDG4gta8XKpMCd]

@tycho01 can you share a minimal example of how recursion in types can be done?

[zpdDG4gta8XKpMCd]

might be relevant: #8517

[tycho01]

@aleksey-bykov the trick was pretty old, not unlike the recursion I'd been using.
His code on the actual recursive type there:

type Concat_<RA extends any[], B extends any[]> = {
    1: Reverse<RA>,
    0: Concat_<Unshift<RA, Head<B>>, Tail<B>>,
}[B extends [] ? 1 : 0];

The idea is basically to ensure the recursive call is wrapped such that it cannot immediately evaluate the whole thing and complain about the recursion.

This is done by wrapping the call into an object type (traditionally in the form { 0: ..., 1: ... }), which you then navigate using a condition it is unable to simplify out right away (here using conditional types: B extends [] ? 1 : 0).

What this solves is the issue you run into when trying this the easy way, e.g. type Rec<T> = T extends ... ? ... : Rec<...>;.
This has the recursive call at the top level, which it'll try to evaluate right away, and therefore trigger an error.

[hailbopp]

Thanks @fightingcat and @tycho01!

Did... did the type system just become Turing-complete? I was thinking that recursive dependent types were the last thing really holding it back.

For the record, I just wrote this little bit of code up that doesn't actually do anything meaningful or interesting, but it _does_ show arbitrary recursion, dependent types that successfully use infer, and a bit of the basis for Peano arithmetic.

// Below this line is silliness
type Nil = { sym: "Nil" };
const Nil: Nil = { sym: "Nil" };

type Zero = { sym: "Zero" };
const Zero: Zero = { sym: "Zero" };


type Succ<TNat> = { sym: "Succ", param: TNat }

type One = Succ<Zero>;
type Two = Succ<One>;
type Three = Succ<Two>;

type Nat<TPredecessor> =
    | Zero
    | Succ<Zero>
    | Succ<TPredecessor>;

type Double_<TNat, TTotal> =
    TNat extends Zero ? TTotal :
    TNat extends Succ<infer TPredecessor> ? {
        1: Double_<TPredecessor, Succ<Succ<TTotal>>>;
        0: never;
    }[TNat extends Succ<TPredecessor> ? 1 : 0] : never;

type Double<TNat, TTotal> = Double_<TNat, TTotal>;

// Alright, time for some magic
let dbl: Double<Succ<Three>, Zero>;      // The type signature of `dbl` is Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Zero>>>>>>>>

[RyanCavanaugh]

Re: Turing completeness, see #14833, or some of the issues lately where people have written compilations which never stop (that we are unable to detect) 😆

[babakness]

@tycho01 The code quoted by @aleksey-bykov is brilliant and it works; but only the first time. If I change the value of one of the tuples being concatenated, TypeScript hangs.

Also adding this function to the bottom of the concat example will hang Typescript

declare function foo<A, B>(a: A[], b: B[]): Concat<A,B>

Example link:

http://www.typescriptlang.org/play/#src=%0D%0Atype%20ToTuple%3CT%3E%20%3D%20T%20extends%20any%5B%5D%20%3F%20T%20%3A%20any%5B%5D%3B%0D%0A%0D%0Atype%20Head%3CTuple%20extends%20any%5B%5D%3E%20%3D%20Tuple%20extends%20%5Binfer%20H%2C%20...any%5B%5D%5D%20%3F%20H%20%3A%20never%3B%0D%0Atype%20Tail%3CTuple%20extends%20any%5B%5D%3E%20%3D%20((...t%3A%20Tuple)%20%3D%3E%20void)%20extends%20((h%3A%20any%2C%20...rest%3A%20infer%20R)%20%3D%3E%20void)%20%3F%20R%20%3A%20never%3B%0D%0Atype%20Unshift%3CTuple%20extends%20any%5B%5D%2C%20Element%3E%20%3D%20((h%3A%20Element%2C%20...t%3A%20Tuple)%20%3D%3E%20void)%20extends%20(...t%3A%20infer%20R)%20%3D%3E%20void%20%3F%20R%20%3A%20never%3B%0D%0Atype%20Push%3CTuple%20extends%20any%5B%5D%2C%20Element%2C%20R%20%3D%20Reverse%3CTuple%3E%2C%20T%20extends%20any%5B%5D%3D%20ToTuple%3CR%3E%3E%20%3D%20Reverse%3CUnshift%3CT%2C%20Element%3E%3E%3B%0D%0A%0D%0Atype%20Reverse%3CTuple%20extends%20any%5B%5D%3E%20%3D%20Reverse_%3CTuple%2C%20%5B%5D%3E%3B%0D%0Atype%20Reverse_%3CTuple%20extends%20any%5B%5D%2C%20Result%20extends%20any%5B%5D%3E%20%3D%20%7B%0D%0A%20%20%20%201%3A%20Result%2C%0D%0A%20%20%20%200%3A%20Reverse_%3CTail%3CTuple%3E%2C%20Unshift%3CResult%2C%20Head%3CTuple%3E%3E%3E%0D%0A%7D%5BTuple%20extends%20%5B%5D%20%3F%201%20%3A%200%5D%3B%0D%0A%0D%0Atype%20Concat%3CTuple1%20extends%20any%5B%5D%2C%20Tuple2%20extends%20any%5B%5D%2C%20R%20%3D%20Reverse%3CTuple1%3E%2C%20T%20extends%20any%5B%5D%3D%20ToTuple%3CR%3E%3E%20%3D%20Concat_%3CT%2C%20Tuple2%3E%3B%0D%0Atype%20Concat_%3CTuple1%20extends%20any%5B%5D%2C%20Tuple2%20extends%20any%5B%5D%3E%20%3D%20%7B%0D%0A%20%20%20%201%3A%20Reverse%3CTuple1%3E%2C%0D%0A%20%20%20%200%3A%20Concat_%3CUnshift%3CTuple1%2C%20Head%3CTuple2%3E%3E%2C%20Tail%3CTuple2%3E%3E%2C%0D%0A%7D%5BTuple2%20extends%20%5B%5D%20%3F%201%20%3A%200%5D%3B%0D%0A%0D%0Atype%20x%20%3D%20Concat%3C%5B1%2C%202%2C%203%5D%2C%20%5B4%2C%205%2C%206%5D%3E%3B%20%2F%2F%20%5B1%2C%202%2C%203%2C%204%2C%205%2C%206%5D%0D%0Atype%20y%20%3D%20Concat%3C%5B1%2C%202%2C%203%2C%204%5D%2C%20%5B5%2C%206%2C%207%5D%3E%3B%20%2F%2F%20%5B1%2C%202%2C%203%2C%204%2C%205%2C%206%5D%0D%0A%0D%0Adeclare%20function%20foo%3CA%2C%20B%3E(a%3A%20A%5B%5D%2C%20b%3A%20B%5B%5D)%3A%20Concat%3CA%2CB%3E

[bobvanderlinden]

Hmm, I think I also ran into this issue when trying to implement a type that deeply removes | null and optionalField?s from GraphQL-like structures:

type GraphQLObject = { '__typename': string }
type DeepRequired<T> = NonNullable<
  T extends Array<infer TItem>
    ? Array<DeepRequired<TItem>>
    : T extends GraphQLObject
      ? Required<{ [TKey in keyof T]: DeepRequired<T[TKey]> }>
      : T
>

The hack mentioned earlier will not work for me (or I haven't figured it out yet), because I need to infer TItem.

[skreborn]

@bobvanderlinden Would the following satisfy your requirements?

type GraphQLObject = { '__typename': string }

type DeepRequired<T> = T extends GraphQLObject ?
    Required<{ [TKey in keyof T]: DeepRequiredObject<T[TKey]> }> :
    (T extends Array<infer TItem> ? DeepRequiredArray<TItem> : DeepRequiredObject<T>);

interface DeepRequiredArray<T> extends Array<DeepRequired<T>> {}

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

It seems to be producing the correct result in a simple case, but I'm unsure if it works in all required scenarios as I haven't yet used GraphQL myself.

interface Result {
    data: {
        search: [
            {
                __typename: string,
                name: string | null
            }
        ]
    }
}

const result: DeepRequired<Result> = {
    data: {
        search: [
            {
                __typename: "Human",
                name: "Han Solo"
            },
            {
                __typename: "Human",
                name: "Leia Organa"
            },
            {
                __typename: "Starship",
                name: "TIE Advanced x1"
            }
        ]
    }
};

result.data.search[0].name; // string

The implementation is largely based on @nieltg's DeepImmutable.

[bobvanderlinden]

@skreborn Wow, thanks for that one 😁👍. It's still a bit confusing why this variant does work, but directly inlining DeepRequiredObject and DeepRequiredArray doesn't. Is such a solution considered a workaround for this issue? Or am I just doing something fundamentally wrong in my type definition?

[skreborn]

@bobvanderlinden This is, as far as I know, the only workaround for now. Inlining them doesn't work because circular referencing is not allowed. So why is it allowed if you put an extra step between the two? It's black magic that might have something to do with lazy evaluation, but it's definitely beyond my knowledge on the internal workings of the type system.

[babakness]

You can sort of induce lazy evaluation by using the following pattern

type DeepUnnest<P extends any[]> = {
  'more': P extends Array<infer U>
    ?  U extends any[]
       ? DeepUnnest<U>
       : never
    : never
  'end': P extends Array<infer U>
    ? U
    : never,
}[
  P extends Array<infer U>
   ? U extends any[]
     ? 'more'
     : 'end'
   : 'end'
]

Its ugly but it works avoiding circular reference problems.

[pronebird]

I found that cyclic references work very well with nested objects

class Node<T> {}

type ExtractType<T> =
    T extends SchemaNode<infer S>
        ? S extends { [name: string]: SchemaNode<infer _> } 
            ? { [K in keyof S]: ExtractType<S[K]> }
            : S extends Array<infer E> 
                ? any[]
                : S           
    : T;

But as soon as I add an Array into the mix and attempt to type it, the whole thing breaks, i.e:

class Node<T> {}

type ExtractType<T> =
    T extends SchemaNode<infer S>
        ? S extends { [name: string]: SchemaNode<infer _> } 
            ? { [K in keyof S]: ExtractType<S[K]> }
            : S extends Array<infer E> 
                ? Array<ExtractType<E>> 
                : S           
    : T;

Full source:

class SchemaNode<T> {
    constructor(private value: T) { }
    validate(): ExtractType<SchemaNode<T>> {
        return this.value as any; // [redacted]
    }
}

type ExtractType<T> =
    T extends SchemaNode<infer S>
        ? S extends { [name: string]: SchemaNode<infer _> } 
            ? { [K in keyof S]: ExtractType<S[K]> }
            : S extends Array<infer E> 
                ? Array<ExtractType<E>>
                : S           
    : T;

type AccountType = "retail" | "company";

const mySchema = new SchemaNode({
    account: new SchemaNode({
        token: new SchemaNode("john doe"),
        type: new SchemaNode<AccountType>("retail"),
        options: new SchemaNode({
            autoLogin: new SchemaNode(true)
        }),
        isActive: new SchemaNode(true),
    }),
    history: new SchemaNode([
        new SchemaNode("went to barber shop")
    ]),
    credits: new SchemaNode(1000)
});

const res = mySchema.validate();

(res.account.token as string);
(res.account.isActive as boolean);
(res.account.type as AccountType);
(res.account.options.autoLogin as boolean);
(res.history as string[]);
(res.credits as number);

[flux627]

I think aleksey-bykov nailed the primary goal use case in this comment:
#6230 (comment)

type Json = null | string | number | boolean | Json[] | { [name: string]: Json }

Here's my work-around:

type JsonPrimitive = string | number | boolean | null
interface JsonMap { [member: string]: JsonPrimitive | JsonArray | JsonMap }
interface JsonArray extends Array<JsonPrimitive | JsonArray | JsonMap> {}
type Json = JsonPrimitive | JsonMap | JsonArray

[kevinbeal]

I wanted to do this:

type lineOfCode = [string, lineOfCode[], [string, void | number]];

But I had to do this workaround:

type _lineOfCode = [string, unknown, [string, void | number]];
interface ILineOfCode extends _lineOfCode {
    1: ILineOfCode[];
}

Maybe this will help someone else.

[ahejlsberg]

With #33050 the original example can now be written as:

interface Bar<A> { x: A }
type Foo = Bar<Foo>