Stack overflow with recursive mapped types

[falsandtru]

From https://github.com/DefinitelyTyped/DefinitelyTyped/tree/master/types/lodash

cc @sandersn @ahejlsberg

TypeScript Version: master

Code

type PartialDeep<T> = {
    [P in keyof T]?: PartialDeep<T[P]>;
};
interface Struct {
    a: number;
    b: string;
    c: boolean;
}

declare function f<T>(): PartialDeep<T>;
var result: Partial<Struct> = f();

Expected behavior:

pass

Actual behavior:

$ node built/local/tsc.js index.ts
...\TypeScript\built\local\tsc.js:73240
                throw e;
                ^

RangeError: Maximum call stack size exceeded
    at ...\TypeScript\built\local\tsc.js:31397:29
    at Object.map (...\TypeScript\built\local\tsc.js:1703:29)
    at getAnonymousTypeInstantiation (...\TypeScript\built\local\tsc.js:31498:40)
    at instantiateType (...\TypeScript\built\local\tsc.js:31584:32)
    at getTemplateTypeFromMappedType (...\TypeScript\built\local\tsc.js:29217:21)
    at inferTypeForHomomorphicMappedType (...\TypeScript\built\local\tsc.js:33779:32)
    at inferFromObjectTypes (...\TypeScript\built\local\tsc.js:34031:48)
    at inferFromTypes (...\TypeScript\built\local\tsc.js:33985:29)
    at inferTypes (...\TypeScript\built\local\tsc.js:33824:13)
    at inferTargetType (...\TypeScript\built\local\tsc.js:33803:17)

[sandersn]

Some notes on this:

Two weeks ago when I was testing DefinitelyTyped frequently, lodash crashed the compiler. Last week it stopped doing so.

I just compiled lodash just now and couldn't repro the problem. I copied the repro above into a buffer and couldn't repro the problem in the compiler or the language service (although my language service is from last week). Here is my test tsconfig.

{
    "compilerOptions": {
        "strict": true,
        "target": "es6",
        "lib": ["es5", "dom"],
        "allowJs": true,
        "checkJs": true,
        "outDir": "out",
        "jsx": "preserve",
        "module": "commonjs"
    },
    "include": [
        "welove.ts",
        "first.ts",
        "test.js"
    ]
}

[falsandtru]

repro: https://travis-ci.org/falsandtru/TypeScript/builds/301501435#L513

[falsandtru]

@sandersn Can you see the repro?

[sandersn]

Thanks for the additional detail. Can you repro this outside Travis?

[falsandtru]

I can repro on my local machine.

[sandersn]

What does your file structure look like? What version of tsc.js are you using?

[falsandtru]

Same as https://travis-ci.org/falsandtru/TypeScript/builds/301501435. Can't you repro using that my commit???

[sandersn]

You edited travis.yml, and I have no idea how to use that to repro on a local machine. Here is the information I expected:

I ended up getting the crash from the typescript repo.

1. Put the original text in ~/TypeScript/index.ts.
2. Run ~/TypeScript/built/local/tsc.js index.ts

This crash must be from interaction with the contents of node_modules because if you drop index.ts into a new directory, the crash doesn't happen. If you copy Typescript's node_modules, the crash does happen.

The similar code

var result: Partial<Struct>
var result = f()

does not crash, so the crash is very likely an infinite loop caused by the interaction between contextual typing and type inference.

[falsandtru]

Here is a repro for local machines:

1. Put the original text in ~/TypeScript/index.ts.
2. Run jake local.
3. Run node built/local/tsc.js index.ts.

if you drop index.ts into a new directory, the crash doesn't happen.

It seems not true.

$ node built/local/tsc.js temp/index.ts
...\TypeScript\built\local\tsc.js:73313
                throw e;
                ^

RangeError: Maximum call stack size exceeded

the crash is very likely an infinite loop caused by the interaction between contextual typing and type inference.

I think so.

[sandersn]

~/TypeScript/temp/index.ts or ~/temp/index.ts? Anywhere that node resolution will find TypeScript's node_modules should cause the crash.

[falsandtru]

Ah, so can you repro and confirm this bug?

[sandersn]

Another Microsoft team encountered a very similar crash resulting from lodash. Here's the simplified repro:

interface A { a: A }
declare let a: A
type Deep<T> = { [K in keyof T]: Deep<T[K]> }
declare function f<T>(deep: Deep<T>): void
f(a)

This works with HTMLElement too, so I think you could easily produce a crash like this:

import _ = require('lodash')
class C {
  elements: HTMLElement[]
  doWork(e: HTMLElement) {
    this.elements = _.remove(this.elements, e)
  }
}

Which is similar to code that people write every day.

[sandersn]

Fix is up at #20370.