Flow: Reduce of inferred arrays causes stack overflow

[0rvar]

This code causes runaway memory consumption until flow crashes.
This is a bug in flow >= 0.39, and still exists in 0.48.0. It can also be reproduced in flow.org/try.

flow.org/try link. If you check the browser console, there is a stack overflow on the server.

// @flow

export function wrapAndFlatten(arr: Array<*>) {
    return arr.map(n => {
        return [n];
    }).reduce((x, y) => [...x, ...y]);
};

[0rvar]

Possibly causes: #4070, #4046

[0rvar]

Further information; this does not terminate:

export function wrapAndFlatten<T>(arr: Array<T>) {
    const mapped = arr.map((n: T) => {
        return [n];
    });
    return mapped.reduce((x, y) => [...x, ...y]);
};

... but these terminate (with "Found 0 errors"):

export function wrapAndFlatten<T>(arr: Array<T>): Array<T> {
    // explicit type signature of mapped
    const mapped: Array<Array<T>> = arr.map((n: T) => {
        return [n];
    });
    return mapped.reduce((x, y) => [...x, ...y]);
};

export function wrapAndFlatten<T>(arr: Array<T>): Array<T> {
    const mapped = arr.map((n: T) => {
        return [n];
    });
    // concat instead of array comprehensions
    return mapped.reduce((x, y) => x.concat(y));
};

export function wrapAndFlatten<T>(arr: Array<T>) {
    const mapped = arr.map((n: T) => {
        return [n];
    });
    // explicit type signature of reduce arguments
    return mapped.reduce((x: Array<T>, y: Array<T>) => [...x, ...y]);
};

[joevbruno]

Any progress on this?

[avikchaudhuri]

Minimal array lib def that repros this:

declare class Array<T> {
  map<U>(callbackfn: (value: T, index: number, array: Array<T>) => U, thisArg?: any): Array<U>;
  reduce(
    callbackfn: (previousValue: T, currentValue: T, currentIndex: number, array: Array<T>) => T, initialValue: void
  ): T;
}

Then with:

export function wrapAndFlatten<T>(arr: Array<T>) {
  const mapped = arr.map((n: T) => {
    return [n];
  });
  return mapped.reduce((x, y) => [...x, ...y]);
};

Running flow check --no-flowlib --verbose, I clearly see a loop involving ArrT ~> ResolveSpreadT, with new tvars being generated every time (probably for the type parameter U in map).

[gabelevi]

I have a fix

[0rvar]

Thank you all! Happy to see this fixed

[joevbruno]

Any idea when this will be released on NPM?