Out of memory checking recursive mapped type with two constraint type references

[mquandalle]

edit: better description of the issue in #21048 (comment)

---

Hello,

I have the following Node error in one of my project using Typescript:

<--- Last few GCs --->

[6455:0x3fcc3c0]    44547 ms: Mark-sweep 1410.5 (1465.1) -> 1410.4 (1449.1) MB, 1625.7 / 0.0 ms  (+ 0.0 ms in 0 steps since start of marking, biggest step 0.0 ms, walltime since start of marking1626 ms) last resort GC in old space requested
[6455:0x3fcc3c0]    46098 ms: Mark-sweep 1410.4 (1449.1) -> 1410.5 (1449.1) MB, 1551.3 / 0.0 ms  last resort GC in old space requested


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x2198fd4a5ee1 <JSObject>
    2: getTypeListId(aka getTypeListId) [/home/project/node_modules/typescript/lib/typescript.js:~30911] [pc=0x3ee74d14a111](this=0x28fe3da82311 <undefined>,types=0x29df387ac9c9 <JSArray[4]>)
    3: /* anonymous */(aka /* anonymous */) [/home/project/node_modules/typescript/lib/typescript.js:~31668] [pc=0x3ee74d35e07d](this=0x28fe3da82311 <undefined>,t...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: node::Abort() [node]
 2: 0x121a2cc [node]
 3: v8::Utils::ReportOOMFailure(char const*, bool) [node]
 4: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [node]
 5: v8::internal::Factory::NewRawOneByteString(int, v8::internal::PretenureFlag) [node]
 6: v8::internal::Factory::NewStringFromOneByte(v8::internal::Vector<unsigned char const>, v8::internal::PretenureFlag) [node]
 7: v8::internal::Factory::NumberToString(v8::internal::Handle<v8::internal::Object>, bool) [node]
 8: v8::internal::Runtime_NumberToString(int, v8::internal::Object**, v8::internal::Isolate*) [node]
 9: 0x3ee74d00463d

I've spend a lot of time trying to fix it by using various versions of Node, Typescript (including latest dev version), and Webpack. Is there any method I can use to understand this issue?

[electricessence]

Would be helpful to have a bit more context. What, when, where?
Do you have any tsconfig.json settings?
Can you point to what you are trying to compile/run?

[mquandalle]

Yes sorry I wasn't able to provide a more detailed bug report in the first place, I was more looking at techniques to deal with this kind of Node error related to the Typescript compilation.

I have now identified the file and the typing dependency (@types/ramda) causing the issue in my project. I made a minimal clonable repository demonstrating the issue: https://github.com/mquandalle/typescript-issue-21048

[sandersn]

Here is a smaller repro that doesn't depend on ramda and is easier for me to read:

interface A {
  x: PartialDeep<A>;
  calls: number | { };
}
type PartialDeep<T> = { [P in keyof T]?: T[P] & PartialDeep<T[P]> };

declare var deep: PartialDeep<A>;
declare var xdeep: { x: PartialDeep<A> };
deep = xdeep;

[sandersn]

I haven't spent much time in the debugger yet, but notably

1. calls needs to have a type that's a union with an object type.
2. The template type of PartialDeep needs to be T[P] & PartialDeep<T[P]>.
3. [Updated] There must be some assignment of type { x: PartialDeep<A> } to PartialDeep<A>.

[sandersn]

The basic type of problem is checking assignability of an infinitely expanding type, in this case "is <T2>(b: T2) => { x: Deep } & T2 assignable to F?". We try to make this work in two ways:

1. Recognising when further expansion of a recursive type will fail to inform the result of assignability.
2. Giving up after a certain recursion depth.

In both approaches, assignability checking continues to the next property, having failed to obtain a positive or negative result from checking the infinitely expanding one. However, (1) only works in specific situations; in general it's hard to say that a comparison will not produce additional information. One example is below. (2) only works when there is one (or a few) infinite expansion. (1) definitely isn't applying here, and (2) looks to be defeated because of the first two points in my previous comment: a reasonably complex type A and a mapped type that expands infinitely for every property.

It might be possible to come up with a rule that falls under category (1), something like "when comparing PartialDeep<A> ==> PartialDeep<PartialDeep<A>>, continue to the next property because you won't learn anything from this comparison."

[sandersn]

In the meantime, a workaround is to change the partial-deep type:

type PartialDescriptor<T> = { [P in keyof T]?: T[P] & PartialDescriptor<T[P]> };
// remove T[P]
type PartialDescriptor<T> = { [P in keyof T]?: PartialDescriptor<T[P]> };

The first definition is wrong anyway, and is the source of the infinite expansion.

PartialDescriptor<{ x: { y: number } }> is equivalent to { x?: { y: number } & { y?: number } }, but this type requires y. I assume this definition is written to work around the deep-mapped type skipping signatures:

{ x: { f(): void } would become { x?: { f?: {} } with the simple definition vs { x?: { f(): void } & { f?: {} } } with the complex one.

But there is no way to make only non-methods become optional in the current version of typescript. I think it is possible with conditional types, which might be in 2.8.

By the way, if the current, incorrect definition was good enough to not notice the incorrectness, a non-deep mapped type is even better: you can just use Partial.

[electricessence]

So I've installed typescript@2.8.0-dev.20180127 and (still) when my build runs it takes forever and then displays the fatal error. I'm guessing this is because (as you may be suggesting) there is some recursion in the type checking. What can I do to avoid this?

I'm pretty confident I know where this is happening in my code, but it would require changing the code in a way that is undesirable.

In order to maintain modularity and not have to load the Linq library but still provide the convenience of having a .linq property on all collections. I had to mirror the interfaces used by the library. Maybe I'm doing this all wrong. If anyone would be willing to critique, it might be helpful:

Here are the interfaces:
https://github.com/electricessence/TypeScript.NET/blob/master/source/System.Linq/Enumerable.d.ts

Here is the actual classes:
https://github.com/electricessence/TypeScript.NET/blob/master/source/System.Linq/Linq.ts

Here is where the interfaces are consumed:
https://github.com/electricessence/TypeScript.NET/blob/master/source/System/Collections/CollectionBase.ts#L17

I'm pretty confident if there wasn't a need for the interfaces themselves then this issue would go away for me. The way to make this all work the way I'm intending is that the .linq property should still expose the types inside Linq.ts, but not end up loading the classes unless used.

See the .linq and .linqAsync methods here:
https://github.com/electricessence/TypeScript.NET/blob/master/source/System/Collections/CollectionBase.ts#L429-L494

It ends up being quite painful keeping the classes in sync with the interfaces.

[mquandalle]

My particular issue is now solved, the T[P] & PartialDeep<T[P]> wasn't needed in my case.