Inconsistent incompatible types error for a sparse array type declaration

[upsuper]

Bug Report

🔎 Search Terms

incompatible types inconsistent

🕗 Version & Regression Information

The behavior changes between 4.4.4 and 4.5.5, but the previous state wasn't the expected result either.

⏯ Playground Link

Playground link with relevant code

💻 Code

export interface ReadonlySparseArray<T> {
  readonly length: number;
  slice(start?: number, end?: number): SparseArray<T>;
  every<S extends T>(
      predicate: (value: T, index: number) => value is S,
  ): this is ReadonlySparseArray<S>;

  readonly [n: number]: T | undefined;
  flatMap<U>(callback: (value: T, index: number) => U | readonly U[] | ReadonlySparseArray<U>): U[];
}

export interface SparseArray<T> extends ReadonlySparseArray<T> {
  [n: number]: T | undefined;
}

// const _a: SparseArray<string> = ['a'];

export function foo<T>(): ReadonlySparseArray<T> {
    let a: T[] = [];
    return a;
}

🙁 Actual behavior

The code above reports:

    Type 'T[]' is not assignable to type 'ReadonlySparseArray<T>'.
      The types returned by 'slice(...).flatMap(...)' are incompatible between these types.
        Type '(U | ReadonlySparseArray<U>)[]' is not assignable to type 'U[]'.
          Type 'U | ReadonlySparseArray<U>' is not assignable to type 'U'.
            'U' could be instantiated with an arbitrary type which could be unrelated to 'U | ReadonlySparseArray<U>'.

on return a;.

However, if the const _a line is uncommented, the error goes away. If you move that line to after the generic function, both places report this error.

(Weirdly, if you remove the every method from the ReadonlySparseArray, both places would be reporting the error regardless of the place of the const _a line.)

🙂 Expected behavior

It should not report error, since SparseArray and ReadonlySparseArray here should be compatible with array type. It's just a declaration of some of its methods.

[upsuper]

Rethought about it, I now believe that the correct behavior is that TypeScript should consistently reject it. Because for flatMap,

• U | readonly U[] is a subtype of U | readonly U[] | ReadonlySparseArray<T> (and not the reverse, since sparse array is not supposed to be assignable to dense array), so
• (...) => U | readonly U[] is a subtype of (...) => U | readonly U[] | ReadonlySparseArray<T>, thus
• (callback: (...) => U | readonly U[] | ReadonlySparseArray<T>) => U[] is a subtype of (callback: (...) => U | readonly U[]) => U[], which means
• ReadonlyArray.flatMap should not be assignable to ReadonlySparseArray.flatMap here.

[andrewbranch]

This is caused by a false positive of isDeeplyNestedType. @upsuper is correct that flatMap should consistently cause an assignability error. However, because of the interconnected return types in the methods of ReadonlySparseArray and SparseArray and the order they’re written, we end up bailing out of comparing flatMap just barely too early. The comparison stack at the point of bailing looks like:

	Source	Target
0	(literal) Array<string>	SparseArray<string>
1	(literal) Array<string>["slice"]	SparseArray<string>["slice"]
2	Array<string>	SparseArray<string>
3	Array<string>["every"]	SparseArray<string>["every"]
4	Array<any>	ReadonlySparseArray<any>
5	Array<any>["slice"]	ReadonlySparseArray<any>["slice"]
6	Array<any>	SparseArray["any"]
7	Array<any>["flatMap"]	SparseArray<any>["flatMap"]
8	U | ReadonlyArray<U | ReadonlySparseArray<U>> | ReadonlySparseArray<U>	U | ReadonlyArray<U> | ReadonlySparseArray<U>
9	ReadonlyArray<U | ReadonlySparseArray<U>>	ReadonlySparseArray<U>
10	ReadonlyArray<U | ReadonlySparseArray<U>>["slice"]	ReadonlySparseArray<U>["slice"]
11	Array<U | ReadonlySparseArray<U>>	SparseArray<U>

While this looks pretty chaotic, it does finish with the correct results if you bump the maxDepth parameter of isDeeplyNestedType from 3 to 4, with the following error elaboration:

    const _a: SparseArray<string> = ['a'];
          ~~
!!! error TS2322: Type 'string[]' is not assignable to type 'SparseArray<string>'.
!!! error TS2322:   The types of 'slice(...).every' are incompatible between these types.
!!! error TS2322:     Type '{ <S extends string>(predicate: (value: string, index: number, array: string[]) => value is S, thisArg?: any): this is S[]; (predicate: (value: string, index: number, array: string[]) => unknown, thisArg?: any): boolean; }' is not assignable to type '<S extends string>(predicate: (value: string, index: number) => value is S) => this is ReadonlySparseArray<S>'.
!!! error TS2322:       Type predicate 'this is any[]' is not assignable to 'this is ReadonlySparseArray<any>'.
!!! error TS2322:         Type 'any[]' is not assignable to type 'ReadonlySparseArray<any>'.
!!! error TS2322:           The types returned by 'slice(...).flatMap(...)' are incompatible between these types.
!!! error TS2322:             Type '(U | ReadonlySparseArray<U>)[]' is not assignable to type 'U[]'.
!!! error TS2322:               Type 'U | ReadonlySparseArray<U>' is not assignable to type 'U'.
!!! error TS2322:                 'U' could be instantiated with an arbitrary type which could be unrelated to 'U | ReadonlySparseArray<U>'.

Note that the comparison at index 8 is the result of contextual signature instantiation after a potentially questionable inference explained here. That’s a separate bug, but fixing it would probably prevent this particular example from triggering the depth limiter.

[andrewbranch]

#58321 fixes this by changing the weird inference mentioned above, but I feel like it’s probably wrong