Stack overflow with recursive mapped types

Nathan Shively-Sanders (@sandersn)

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

cc Nathan Shively-Sanders (@sandersn) Anders Hejlsberg (@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)

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"
    ]
}

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

Nathan Shively-Sanders (@sandersn)

Nathan Shively-Sanders (@sandersn) Can you see the repro?

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

I can repro on my local machine.

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

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

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.

Put the original text in ~/TypeScript/index.ts.
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.

Here is a repro for local machines:

Put the original text in ~/TypeScript/index.ts.
Run jake local.
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.

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

Ah, so can you repro and confirm this bug?

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.

Fix is up at #20370.

Navigation Menu

Repository navigation

Stack overflow with recursive mapped types #19951

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Stack overflow with recursive mapped types #19951

Description

Activity

sandersn commented on Nov 13, 2017

falsandtru commented on Nov 13, 2017

falsandtru commented on Nov 14, 2017

sandersn commented on Nov 14, 2017

falsandtru commented on Nov 14, 2017

sandersn commented on Nov 14, 2017

falsandtru commented on Nov 14, 2017

sandersn commented on Nov 14, 2017

falsandtru commented on Nov 14, 2017

sandersn commented on Nov 14, 2017

falsandtru commented on Nov 15, 2017

sandersn commented on Nov 30, 2017

sandersn commented on Nov 30, 2017

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions