Stack overflow on certain platforms

[DanielRosenwasser]

From @h-joo at #45571

type SomeType = number | string | SomeType[];

declare var obj: { key: SomeType; };

declare namespace jasmine {
    interface Matchers<T> {
        toEqual(expected: Expected<T>): void;
    }

    type Expected<T> = T | {
        [K in keyof T]: ExpectedRecursive<T[K]>;
    }

    type ExpectedRecursive<T> = T | {
        [K in keyof T]: ExpectedRecursive<T[K]>;
    };
}

declare function expect<T>(actual: T): jasmine.Matchers<T>;

expect(obj).toEqual({ key: 'value1' });

With tsc or in the editor

> tsc -p src
src/index.ts:19:21 - error TS2589: Type instantiation is excessively deep and possibly infinite.

expect(obj).toEqual({key: 'value1'});
                    ~~~~~~~~~~~~~~~

Or in the playground for me:

simpleWorker.ts:125 Uncaught (in promise) RangeError: Maximum call stack size exceeded
    at isTypeAssignableTo (tsWorker.js:60285)
    at isApplicableIndexType (tsWorker.js:56207)
    at findApplicableIndexInfo (tsWorker.js:56187)
    at getApplicableIndexInfo (tsWorker.js:56236)
    at getPropertyTypeForIndexType (tsWorker.js:58675)
    at getIndexedAccessTypeOrUndefined (tsWorker.js:59018)
    at getIndexedAccessType (tsWorker.js:58940)
    at instantiateTypeWorker (tsWorker.js:60141)
    at instantiateTypeWithAlias (tsWorker.js:60092)
    at instantiateType (tsWorker.js:60075)

---

This seems to have been caused by the newly introduced recursive definition of
the IDBValidKey, and this causes an infinite type instantiation.

[DanielRosenwasser]

I managed to get a simpler repro by replacing IDBKey with

type SomeType = number | string | SomeType[];

[ahejlsberg]

Is the issue here the stack overflow in the playground? Best I can tell, the excessive depth error is expected behavior and also happens with versions prior to 4.4.

[ahejlsberg]

BTW, I'm not seeing the stack overflow in the playground.

[DanielRosenwasser]

Hm - there's a few things to note I think.

1. The "deep or possibly infinite" error is probably not desirable, but maybe the best we can do here, so I guess that's expected.
2. The fact that IDBValidKey changed was part of what triggered the investigation. The definition of IDBValidKey seems correct, so the fact that this type doesn't play well with Jasmine might be a pill we have to swallow for 4.4.
3. The stack overflow does seems like a problem. I see it in Edge, but not in Firefox or Node.

[ahejlsberg]

The stack overflow does seems like a problem. I see it in Edge, but not in Firefox or Node.

On nightly or 4.4.1-rc? We've increased the maximum instantiation depth from 50 to 500 in nightly, so that may have something to do with it.

[DanielRosenwasser]

I guess playing with the depth limiter is still an open area of investigation

[andrewbranch]

The definition of IDBValidKey changed from

interface IDBArrayKey extends Array<IDBValidKey> {}
type IDBValidKey = number | string | Date | BufferSource | IDBArrayKey;

which does not trigger the infinite instantiation, to

type IDBValidKey = number | string | Date | BufferSource | IDBValidKey[];

which does trigger the infinite instantiation, which prompts a question and a hypothesis:

• Question: Should (normatively speaking) those two definitions of IDBValidKey behave identically? I know the interface trick was a long-standing workaround for recursive type aliases being totally prohibited, but when recursive type aliases became supported, I assumed these would work pretty much the same. It seems like using the intermediate interface is still necessary sometimes.
• Hypothesis: The difference in behavior seen between these two assignments, combined with the substitution made in getNormalizedType starting in Relate non-augmenting subtypes without resorting to structural comparison #43624, is a major contributor to the increased errors in instantiation depth limits, stack overflows, and OOMs (listed in order of decreasing confidence).

[charlescapps]

I'm running into a similar issue. When I run tsc on our node project, I get RangeError: Maximum call stack size exceeded.

Everything was working fine - this just happens when I attempt to upgrade to typescript 4.5.3. It works fine in typescript 4.2.3.

FWIW, recursive types should definitely be allowed. They're a standard part of any programming language (more generally, Context Free Grammars) and it's very common to do this (e.g. with datastructures like trees, or compilers, etc.).

e.g. it's 100% valid to have:

type Tree<T> = { data: T; children: Tree<T>[] } 

Unfortunately the stacktrace I get doesn't give me any indication of which type is causing the issue:

/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:94444
                throw e;
                ^

RangeError: Maximum call stack size exceeded
    at getRelationKey (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:54317:32)
    at recursiveTypeRelatedTo (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:52985:26)
    at isRelatedTo (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:52645:30)
    at typeRelatedToSomeType (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:52869:35)
    at structuredTypeRelatedToWorker (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:53099:32)
    at structuredTypeRelatedTo (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:53084:30)
    at isRelatedTo (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:52642:30)
    at checkTypeRelatedTo (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:52314:26)
    at isTypeRelatedTo (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:52276:24)
    at isTypeAssignableTo (/Users/cbattycapps/{REDACTED}/node_modules/typescript/lib/tsc.js:51558:20)

[charlescapps]

I just verified I don't get this Maximum call stack size exceeded error on version 4.5.2 of typescript, so this is likely a regression in the current latest release - 4.5.3 at time of writing.