Trying to flatten an array with unknown depth causes a type error

[GuiltyDolphin]

Bug Report

Trying to flatten an array with unknown depth causes a type error.

🔎 Search Terms

• flat
• Infinity

🕗 Version & Regression Information

• Errors in version 4.2.4
• This changed between versions 3.6.2 and 3.7.5 (but probably just because the type definitions aren't supported prior)

The PR #32131 provides a definition for FlatArray that has this issue.

⏯ Playground Link

Playground link with relevant code

💻 Code

// first define a nested list with arbitrary depth
type Nested<T> = (T | Nested<T>)[];

const arr: Nested<number> = [1,[2,[3]]];

// locally, this bit fails for me (version 4.2.4)
//
// with an error '"recur"' is referenced directly or indirectly in its own type annotation.
const res: number[] = arr.flat(Infinity);

// you can do a quick workaround as follows:
const res2: number[] = (arr as any[]).flat(Infinity);

// but for some reason on the TypeScript playground this doesn't fail, but you can emulate it
// by using the following definition that is equivalent to the one provided in the standard library:
// https://github.com/microsoft/TypeScript/blob/d8e9f6951919a347bb155b938a5006f9efabb778/lib/lib.es2019.array.d.ts#L21
type FlatArray2<Arr, Depth extends number> = {
    "done": Arr,
    "recur": Arr extends ReadonlyArray<infer InnerArr>
        ? FlatArray2<InnerArr, [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20][Depth]>
        : Arr
}[Depth extends -1 ? "done" : "recur"];

// causes a type error: '"recur"' is referenced directly or indirectly in its own type annotation.
type TestFlat<T> = FlatArray2<Nested<T>, typeof Infinity>

🙁 Actual behavior

The code errors with '"recur"' is referenced directly or indirectly in its own type annotation.

🙂 Expected behavior

The code to pass typechecking.

[jcalz]

Now that we have genuine recursive conditional types, I wonder if this shouldn't be refactored to use them. Either way, recursion limits exist and problems will happen; I guess someone could hand-tune the definition to try to avoid them:

type FlatArrayʹ<A, D extends number> =
    D extends -1 ? A :
    A extends ReadonlyArray<infer I> ? FlatArrayʹ<
        I, [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...20[]][D]
    > : A;

interface Array<T> {
    flatʹ<A, D extends number = 1>(
        this: A,
        depth?: D
    ): FlatArrayʹ<A, D>[];
}

const arr: Nested<number> = [1, [2, [3]]];
// I'm not sure what type we expect to see coming out of `arr.flat(Infinity)
// Infinity is just some unknown number as far as the compiler is concerned
// we just don't want a crash 
const res = arr.flatʹ(Infinity); // const res: (number | Nested<number>)[] 🤷‍♂️

But I feel like recursion in the standard lib always is going to be prone to this no matter what.

Playground link

[GuiltyDolphin]

Yeah, it's hard without dependent types. We might be able to get away with certain type operations on numbers (e.g., see work over at https://github.com/granule-project/granule), so that we could capture more information on how we are flattening without restricting the number of levels. With support for natural numbers, we might be able to make use of (semi-dependent?) elimination to get some nice recursion without hitting any limits.

I think for arr.flat(Infinity) we would just expect a flattened array type out (for any nested array Nested<T>, we'd expect flat(Infinity) to try and flatten the array completely, and yield an array T[]). If T is itself an array, this could lead to issues, but this can be guarded against (e.g., see https://github.com/GuiltyDolphin/functionality/blob/19f4b0be86b71da42bcaed6933ef69e4d9b64a56/src/array.ts#L146).

[jcalz]

There's no Infinity at the type level, though (#32277), so for now this must be the same as just number.