Compiler crashes with 'Allocation failed' error after using mapped type

[dsehnal]

TypeScript Version: 2.1.5 and nightly (2.2.0-dev.20170125)
Node Version: 6.9.4 64-bit (probably not relevant)

Code

I have changed type annotation in my code from

export function create<Props extends { }>(info: TypeInfoBase, traits?: TypeTraits): Type<Props & CommonProps>

to

export function create<T extends Any>(info: TypeInfoBase, traits?: TypeTraits): Type<T['props']>

Here is the change in the full context.

I did the change because using the original approach

const X = create<{ prop: number }>(...)
type X = typeof X._Entity

resulted in loosing typename in typedoc documentation.

Instead, I decided to use

interface X extends Entity<{ props: number }> {}
const X = create<X>(...)

Expected behavior:

The code compiles and does not crash.

Actual behavior:

Code takes extremely long to compile or crashes.

If I modify the code to

export function create<T extends Any>(info: TypeInfoBase, traits?: TypeTraits): Type<T & any>

the problem goes away. (I am using T & any because I am using the noUnusedLocals flag and would have to change more code).

Steps to reproduce:

Compiles without problems:

git clone https://github.com/dsehnal/LiteMol.git
cd LiteMol
npm install
git checkout 04314ab
gulp

Crashes on "Viewer and Examples" task and takes too long on "Bootstrap" task:

git stash
git checkout c075025
gulp

The error I am getting is:

<--- Last few GCs --->

   55484 ms: Mark-sweep 1345.9 (1433.7) -> 1342.6 (1434.2) MB, 1105.7 / 0.0 ms [
allocation failure] [GC in old space requested].
   56710 ms: Mark-sweep 1342.6 (1434.2) -> 1342.4 (1434.2) MB, 1225.5 / 0.0 ms [
allocation failure] [GC in old space requested].
   57887 ms: Mark-sweep 1342.4 (1434.2) -> 1344.5 (1403.2) MB, 1177.3 / 0.0 ms [
last resort gc].
   59057 ms: Mark-sweep 1344.5 (1403.2) -> 1346.5 (1403.2) MB, 1169.3 / 0.0 ms [
last resort gc].


<--- JS stacktrace --->

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

Security context: 000001B4D2ACFB61 <JS Object>
    1: getNodeLinks [g:\Test\LiteMol\node_modules\typescript\lib\typescript.js:~
24871] [pc=000003923497B90A] (this=000001B4D2AE6659 <JS Global Object>,node=0000
03159B6D0029 <a NodeObject with map 0000004590944209>)
    2: isSymbolOfDeclarationWithCollidingName [g:\Test\LiteMol\node_modules\type
script\lib\typescript.js:~42858] [pc=0000039234857861] (this=000001B4D2AE6659 <J
S Global Object>,sym...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memo
ry

[mhegazy]

@rbuckton can you take a look.

[sandersn]

I couldn't repro this with the latest build of typescript, but I may have missed something along the way. There were tons of build errors reported, so maybe the crash is avoided because of earlier errors.

[sandersn]

@dsehnal does the crash still happen with typescript@next? Several stack overflow errors have been fixed in the last few days, and this bug may be a duplicate of one of those.

[dsehnal]

@sandersn Yes it does happen on 2.3.0-dev.20170406. Oddly enough, in 2.2.2 it works but takes unreasonably long (13s for the "Bootstrap" component vs ~2.5-5s for the other ones while having comparable amount of code).

To reproduce it in git checkout c075025, go to src/Visualization/Utils/Palette.ts and move the line

private static previous = Palette.randomMix({ r: 0.75, g: 0, b: 0.25 }, { r: 1, g: 0.5, b: 0 }, { r: 0, g: 0.35, b: 1 }, 0.5);

under the randomMix function. The older versions of tsc didn't catch this "use before declaration" error. Afterwards, rest of the project compiles.

[sandersn]

Moving the line definitely got rid of the errors, but Viewer and Examples still completes for me (in 34 seconds). Bootstrap takes 26 seconds though. Let me try on a Windows machine...and also with 2.1.7.

[dsehnal]

Well, I think that I must have hit some degenerate path with the way I used the mapped type. Or maybe it's something that when fixed speeds up the compilation in general.

I am on Windows 10. Originally, I got the error in Node 6.9 and when I tested it yesterday, it was present in 7.6 as well.

[sandersn]

Well, I got a consistent repro. In Viewer/PDBe/SequenceAnnotation.ts, a line like e.type !== Annotation cause the crash because it tries to compare the types Entity.Any and Tree.Node.Type. Entity.Any is a subclass of Tree.Node.Type, but the two have subtly different type arguments.

I'm still looking for the point where the compiler gets trapped in the comparison of the two types.

[sandersn]

Here's a standalone repro.

interface N<Props> {
    type: BaseType<N<Props>>,
    props: Props,
}

interface Transform<B> {
    // Note: Seems to require `transformer` to be an array
    // or else the `transform` parameter of `create` to be an array
    transformer: BaseType<B>[],
}

interface BaseType<T> {
    create(transform: Transform<T>): T
}
interface Type<P> extends BaseType<N<P>> {
    create(transform: Transform<N<P>>): N<P>
}

// Note: must be interface; `type Annotation = ...` doesn't fail
interface Annotation extends N<{ n: number }> { }

//// actual repro ////
// Note: `BaseType<N<Annotation['props']>>` doesn't fail even though it looks substitutable
declare const Annotation: Type<Annotation['props']>
// declare const Annotation: Type<{ n: number }>
function update(e: N<{}>) {
    return e.type !== Annotation
}

[sandersn]

Here's a bit more progress. It turns out the code should actually fail with an error: Type 'N<{}>' is not comparable to type 'N<{ n: number }>'; Property 'n' is missing in type '{}'. (N<{}> corresponds to Entity.Any in the original, and N<{ n: number }> to Entity<{ query: Query.Source, color: Visualization.Color }>)

In other words, Entity.Any should not be comparable to more specialised entity types.

However, the code path in isRelatedTo that finds this error is directly comparing {} to { n: number } because both were type arguments to N. It doesn't actually report the error. Instead it tries structural comparison to see whether that will succeed. That means it instantiates all the properties of N with the respect type argument types (for example, N<{}>.props : {} and N<{n:number}>.props : { n: number}. But the type of N.type is recursive, so it never finishes.

[dsehnal]

@sandersn But I am comparing the "types" of the entities (where the "type" is a factory of sorts for the given entity), not the entities themselves, therefore the error message does not make much sense to me. Or am I missing something?

[sandersn]

Well, e.type: BaseType<N<{}>> and Annotation: Type<Annotation['props']>, which simplifies as follows:

Type<Annotation['props']>
Type<N<{ n: number }>['props']>
BaseType<N<N<{ n: number }>>['props']>
BaseType<N<{ n: number }>>

Then when the checker compares BaseType<N<{}>> with BaseType<N<{ n: number }>>, it ends up checking {} and { n: number }. I think the type parameter check is stricter than structural comparison, though, because of course {} === { n: 12 } is legal.

Notably, when I lower the recursion overflow limit in isRelatedTo from 100 to 20, the repro code hits the limit and fails. So structural comparison might eventually fail too.

[dsehnal]

I might be totally off here, but could this be related to the variance of the type parameters?

I've run into an issue in the next iteration of the "transform tree" data structure I am using in LiteMol.

Basically I wanted to achieve what in C# would look like

interface Transform<in A, out B, P> { .... }

My first attempt was to try

export interface Transform<A extends Entity.Any, B extends Entity.Any, P> {
  '@sourceType'?: A,
  '@targetType'?: B
}

But I was getting "X is not assignable to Y" type of errors which sounds kind of similar to "X and Y are not comparable". I assume this is because the compiler assumed A and B are bi-variant when trying to compare different instances of the Transform interface.

(Tho a bit unrelated, eventually, I figured out I need to use

export interface Transform<A extends Entity.Any, B extends Entity.Any, P> {
  '@typeAnnotation'?: (src: A['kind'], params: P) => B['kind'],
}

and the whole interface then behaves as the C# version.)

Where I am going with this:

The compiler tries to compare types A and B, which are both recursive as you pointed out. There is probably some "symmetric equivalence property" which is tested recursively and includes isAssignableTo(A, B) which in turns calls isAssignableTo(B, A) later down the line and it gets stuck in infinite recursion.

So maybe a solution would be to memoize which type pairs have already been compared?

[sandersn]

Well, yes, basically. When isRelatedTo checks type parameters of something like Array<P> <=> Array<Q>, it first checks that both are instantiations of Array<T>. Then it checks that P is comparable to Q. If that fails, it tries structural comparison. Structural comparison has to instantiate and then check every property of Array<P> and Array<Q> so it can be very expensive (as it is in this bug). But by checking every property individually it implements bivariance by default (and perhaps some other type-system oddities, I can't remember).

isRelatedTo has a couple of caches: relation caches pairs that are definitely comparable or not. This doesn't apply since none of the pairs that matter ever find an answer. maybeStack caches pairs that are in the process of being calculated. If a pair shows up in the maybe stack, then it means the compiler hit a loop and it returns "Maybe", which means "check other properties and if nothing else fails, then the comparison is allowed". maybeStack gets hit a lot during compilation of the repro, but not enough to keep ahead of the new instantiations from the ever-expanding Transform<T> ~ BaseType<B>[] cycle.

[sandersn]

Can you try typescript@next? #15519 improved comparison of Array instantiations a lot a couple of days ago. My standalone repro now takes less than 2 seconds instead of over 30 seconds.

[dsehnal]

Yes, this seems to fix it for checkout c075025 (after using "any" type for the newly introduced type errors because 2.4's typechecker seems to be stricter/more correct) and the compile time takes ~2.6s on my machine.

On the latest version of my project, there is no significant time difference between 2.4 (@next) and 2.3.2.