with additional work it can be expanded to all type references.

To be clear, do you intend to resolve nested Promise types? Another, do you also intend to improve Array#{flat,flatMap}?

OK, so I expanded enough on this locally to try the

type HypertextNode = string | [string, { [key: string]: any }, ...HypertextNode[]];

const hypertextNode: HypertextNode =
    ["div", { id: "parent" },
        ["div", { id: "first-child" }, "I'm the first child"],
        ["div", { id: "second-child" }, "I'm the second child"]
    ];

example out (which is a motivator here), and the approach quickly hits its limits - namely, when we compare tuples, eventually we compare the array methods on the tuple, which have this types - this this type for the recursive alias then expands forever in instantiation, because getAnonymousTypeInstantiation eagerly applies type arguments to the object's captured type parameters (which un-defers them, which isn't an immediate issue, since their containing types now exist, but their structure is then problematic as instantiation doesn't keep any kind of "visited" stack, so will happily spin forever on the type (not knowing it needs to introduce a deferral anywhere). The un-deferal occurs because the getIndexTypeOfType call required for a rest parameter forces the type argument to the array to resolve before it's passed forward (while when the reference within the type argument is what is deferred, as in the other PR, this is no problem). I've opened this with the diff of what I've added

type ValueOrArray<T> = T | ValueOrArray<T>[];

So is this an alternative to #33018?

@weswigham Latest commit changes deferred type reference instantiation to use the same logic as anonymous types. This ensures that deferred type references continue to be deferred when instantiated, and it fixes the issues you were seeing with infinite instantiations. The motivating example

type HypertextNode = string | [string, Record<string, unknown>, ...HypertextNode[]];

const hypertextNode: HypertextNode =
  ["div", {id: "parent"},
    ["div", {id: "first-child"}, "I'm the first child"],
    ["div", {id: "second-child"}, "I'm the second child"]
  ];

now works as expected.

I still need to look at pulling in the other changes in your diff. The depth stuff was just a quick fix I put in place, I agree it isn't the correct solution.

@weswigham Printback now fixed by cherry picking some of your changes.

A bit more context on the latest commits... The instantiation logic for array and tuple type references is now similar to that of anonymous types and mapped types: We track which outer type parameters are in scope at the location of the reference and cache instantiations based on the type arguments of those outer type parameters. This means self-referential array and tuple types are no more expensive than self-referential object types.

is this an alternative to #33018?

I think this PR is the right way to solve the issue in #32967.

@typescript-bot perf test this

Heya @ahejlsberg, I've started to run the perf test suite on this PR at b18c70f. You can monitor the build here. It should now contribute to this PR's status checks.

Update: The results are in!

@ahejlsberg
The results of the perf run you requested are in!

Performance tests above show a worst case 5% check time increase and 10% memory consumption increase. That's a bit too expensive. With the latest commit we only defer type argument resolution for aliased array and tuple types. That should improve the numbers.

@typescript-bot perf test this

Heya @ahejlsberg, I've started to run the perf test suite on this PR at 8f3a917. You can monitor the build here. It should now contribute to this PR's status checks.

Update: The results are in!

@ahejlsberg
The results of the perf run you requested are in!

Rather than creating a(nother) location with an observable inline vs not inlined checking change (which we usually attempt to remove), would it really be so bad to only make the deferred type in cases where we find the type to be circular (ie, when we spot it on the circularity stack)? It's not the first place where we'd be doing something other than returning an errorType upon discovering a circularity - getTypeOfVariableOrParameterOrPropertyWorker has fallbacks on initial circularity in some circumstances already, and operating in that way would guarantee the perf and memory costs are near zero unless the feature is actually used.

Performance numbers now look great. Basically zero cost to cover the known scenarios!

would it really be so bad to only make the deferred type in cases where we find the type to be circular (ie, when we spot it on the circularity stack)?

That might be fine too, though we're already at zero cost for the feature. I like the current syntactic solution because it is easy to reason about when it kicks in. I wasn't aware that we do something other than return errorType upon discovering circularities. I'm not convinced that works in all cases because we potentially invalidate multiple circularity stack entries upon detecting a circularity, but we only do the non-errorType logic for some of them.

Yeah, I've wondered about that, too, but it has yet to come up. In any case, that's why I cautiously wrote the peek method instead in the other PR, to avoid invalidating the whole stack. But yeah, I know this roughly covers the important bits via syntax, and in that way, means there's always a way to make a thing work by transforming it into some kind of extracted alias, but we repeatedly got issues about how conditionals, when inlined, don't act the same (because if changes to distributivity, which is intentional), and any time an inlined type doesn't behave correctly because of an issue in variance, it's invariably reported. While this is easier to reason about implementation-wise, the behavior on usage is actually harder to justify, imo.

I believe 5% performance is very acceptable trade for this feature (is it outside of the margin of error at all?). The recursive type references should just be enabled for all cases.

@RWalkling hey, sorry to be a bother, but I have a question in regards to your unwarp construct. I have successfully converted a tree-like structure into a recursive nesting of Plain<Plain<...> | MyType<'a', 'b'>> values. Unfortunately, using released TS 3.7, your recursive inference

type Recursive<T> = 
    | T 
    | Plain<Recursive<T>> 

export type Flatten<T> = T extends Recursive<infer R> ? R : never;

did not work for me, instead producing the same type I passed into the flatten. Could you advise as to how can I unwrap the nested Plain objects? I need a union of all MyType instances in the tree.
Thanks a lot!

@icehaunter Try recursively extracting in Flatten<T> instead. That's what I would've normally done before this PR, and it's also simpler.

export type Flatten<T> = T extends Plain<infer U> ? Flatten<U> : T;

@isiahmeadows that doesn't work, because of error "Type alias 'Flatten' circularly references itself". Because the recursive type usage is not inside an interface.

@icehaunter 🤦‍♀️ Try this. (That was untested, obviously, and so is this.)

type Flatten<T> = {
	0: T,
	1: T extends Plain<infer U> ? Flatten<U> : never,
}[T extends Plain<any> ? 1 : 0]

If it weren't so difficult and time-consuming (as basically every type system more complicated than C or Hindley-Milner is), I'd reimplement TS myself using proper deductive types with infer being proper mathematical induction.

I still get Type alias ... circularly references itself. when type created with Intersection. For example:

type TreeNode = {
//   ^--------^ Type alias 'TreeNode' circularly references itself 
  [key: string]: TreeNode | [string, string],
} & {path: string};

playground

Doesn't seem to work:

type UnknownProps = Record<string, UnknownValues>
type UnknownValues = unknown | Record<string, UnknownProps>

Type alias 'UnknownProps' circularly references itself. ts(2456)
Type alias 'UnknownValues' circularly references itself. ts(2456)

playground link

Maybe I misunderstood it.

@trusktr

In the opening comment by Anders the definition of the new kinds of types that can be circularly referenced are defined as:

Instantiations of generic class and interface types (for example Array).
Array types (for example Foo[]).
Tuple types (for example [string, Foo?]).

The type Record is a reference to a mapped type from an alias, rather than an interface or class. For example, this works:

interface R<T> {
    [keys: string]: T;
}
type UnknownProps = R<UnknownValues>;
type UnknownValues = unknown | R<UnknownProps>;

It is still the case that TypeScript is not going to resolve arbitrary symbols because there needs to be some indication that the recursion in guarded by something.

Interesting. Also here's another way to write it:

type UnknownProps2 = {[K in string]: UnknownValues2};
type UnknownValues2 = unknown | Record<string, UnknownProps2>
type StartValues2 = {[K in string]: number | Array<number> | StartValues2};

const test2: UnknownProps = {a: 1, b: {c: 2}}

playground

I heard 4.1 will have better support for recursive types?