Compiler runs out of memory in classes with lots of static, generic functions

[sandersn]

This repro is based on ListWrapper from Angular 2, a class that contains nothing but static functions. Most of them are generic.

When I test the upcoming strictThis flag, ListWrapper causes the compiler to run out of memory. The code below is equivalent to making all the this arguments explicit as dit: typeof ListWrapper. Nobody would write code like this today, but with strictThis, static functions all get an extra argument like this: typeof ListWrapper by default.

The reason for the failure is that when inferring type arguments for a call, such as ListWrapper.clone, its signature is first retrieved:

let clone = ListWrapper.clone(ListWrapper, [1,2,3,4]);

Which gives <T>(dit: typeof ListWrapper, array: T[]): T[]. Then the signature is instantiated with the inferred type parameters: (dit: typeof ListWrapper, array: number[]): number[].

Unfortunately, this instantiation causes typeof ListWrapper to be instantiated as well since it's an anonymous type. This creates a new type whose target is the original but is otherwise identical. Now, checking that the arguments (ListWrapper, [1,2,3,4]) are applicable to this instantiated signature will check that the argument typeof ListWrapper (un-instantiated) is applicable to the parameter typeof ListWrapper (instantiated). This checks spirals out of control because the types are not identical, so all properties need to be checked. But when any generic method is checked, the same instantiated-type mismatch happens again and the process recurs until the compiler runs out of memory.

class ListWrapper {
  // JS has no way to express a statically fixed size list, but dart does so we
  // keep both methods.
  static createFixedSize(dit: typeof ListWrapper, size: number): any[] { return new Array(size); }
  static createGrowableSize(dit: typeof ListWrapper, size: number): any[] { return new Array(size); }
  static clone<T>(dit: typeof ListWrapper, array: T[]): T[] { return array.slice(0); }
  static forEachWithIndex<T>(dit: typeof ListWrapper, array: T[], fn: (t: T, n: number) => void) {
    for (var i = 0; i < array.length; i++) {
      fn(array[i], i);
    }
  }
  static first<T>(dit: typeof ListWrapper, array: T[]): T {
    if (!array) return null;
    return array[0];
  }
  static last<T>(dit: typeof ListWrapper, array: T[]): T {
    if (!array || array.length == 0) return null;
    return array[array.length - 1];
  }
  static indexOf<T>(dit: typeof ListWrapper, array: T[], value: T, startIndex: number = 0): number {
    return array.indexOf(value, startIndex);
  }
  static contains<T>(dit: typeof ListWrapper, list: T[], el: T): boolean { return list.indexOf(el) !== -1; }
  static reversed<T>(dit: typeof ListWrapper, array: T[]): T[] {
    var a = ListWrapper.clone(dit, array);
    return a.reverse();
  }
  static concat(dit: typeof ListWrapper, a: any[], b: any[]): any[] { return a.concat(b); }
  static insert<T>(dit: typeof ListWrapper, list: T[], index: number, value: T) { list.splice(index, 0, value); }
  static removeAt<T>(dit: typeof ListWrapper, list: T[], index: number): T {
    var res = list[index];
    list.splice(index, 1);
    return res;
  }
  static removeAll<T>(dit: typeof ListWrapper, list: T[], items: T[]) {
    for (var i = 0; i < items.length; ++i) {
      var index = list.indexOf(items[i]);
      list.splice(index, 1);
    }
  }
  static remove<T>(dit: typeof ListWrapper, list: T[], el: T): boolean {
    var index = list.indexOf(el);
    if (index > -1) {
      list.splice(index, 1);
      return true;
    }
    return false;
  }
  static clear(dit: typeof ListWrapper, list: any[]) { list.length = 0; }
  static isEmpty(dit: typeof ListWrapper, list: any[]): boolean { return list.length == 0; }
  static fill(dit: typeof ListWrapper, list: any[], value: any, start: number = 0, end: number = null) {
    list.fill(value, start, end === null ? list.length : end);
  }
  static equals(dit: typeof ListWrapper, a: any[], b: any[]): boolean {
    if (a.length != b.length) return false;
    for (var i = 0; i < a.length; ++i) {
      if (a[i] !== b[i]) return false;
    }
    return true;
  }
  static slice<T>(dit: typeof ListWrapper, l: T[], from: number = 0, to: number = null): T[] {
    return l.slice(from, to === null ? undefined : to);
  }
  static splice<T>(dit: typeof ListWrapper, l: T[], from: number, length: number): T[] { return l.splice(from, length); }
  static sort<T>(dit: typeof ListWrapper, l: T[], compareFn?: (a: T, b: T) => number) {
    if (isPresent(compareFn)) {
      l.sort(compareFn);
    } else {
      l.sort();
    }
  }
  static toString<T>(dit: typeof ListWrapper, l: T[]): string { return l.toString(); }
  static toJSON<T>(dit: typeof ListWrapper, l: T[]): string { return JSON.stringify(l); }

  static maximum<T>(dit: typeof ListWrapper, list: T[], predicate: (t: T) => number): T {
    if (list.length == 0) {
      return null;
    }
    var solution: T = null;
    var maxValue = -Infinity;
    for (var index = 0; index < list.length; index++) {
      var candidate = list[index];
      if (isBlank(candidate)) {
        continue;
      }
      var candidateValue = predicate(candidate);
      if (candidateValue > maxValue) {
        solution = candidate;
        maxValue = candidateValue;
      }
    }
    return solution;
  }
}
let clone = ListWrapper.clone([1,2,3,4,5]);
declare function isBlank(x: any): boolean;
declare function isPresent<T>(compareFn?: (a: T, b: T) => number): boolean;
interface Array<T> {
    fill(value: any, start: number, end: number): void;
}

[sandersn]

Probably related to #5695 (relating identical types that come from two places). Might be related to #7081 (relating lots of complex types).

[sandersn]

@ahejlsberg do you have an idea of how to fix this? I don't know whether the fix is to make typeof X not anonymous vs some other solution -- like an ad-hoc fix to the type argument inference code or something.

[ahejlsberg]

@sandersn We instantiate the (anonymous) static side of a class because it might reference one of the type parameters being mapped. For example:

function foo<T>(x: T) {
    class C {
        static y: T = x;
    }
    return C;
}
let y = foo(5).y;  // Type of y is number

Now, as the example above illustrates, we really only need to instantiate anonymous types if they are nested within the class or function that introduced the type parameters being mapped (because only then could members of the anonymous types possibly reference those type parameters). We don't currently do that check and I think that's the problem you're running into. In your example there really is no need to instantiate typeof ListWrapper because the type parameter being mapped isn't in scope in the class (it's actually introduced by a member in the class).

Unfortunately, there is currently no easy way to check which type parameters are being mapped by a particular type mapper (which is why we don't currently do the check), but I guess we need to figure something out.

[sandersn]

I have a strawman PR at #7138. It's probably wrong (and currently the mapper extension is ugly too), but I think a bad solution is good for contrasting with a better solution.