Provide declaration of sparse array

[upsuper]

lib Update Request

While majority of arrays in JavaScript / TypeScript are dense arrays, occasionally there are use cases for sparse array. (We are using it in Canva for some core data structures.)

Sparse array has some interesting behavior different from a dense array, for example, all the methods iterating it (like forEach, map, every, etc.) only visits occupied slots, while @@iterator and index access (for index < length) can visit empty slots with undefined.

I've done some spike to declare sparse array as an interface with a subset of array, and so far I have:

export interface ReadonlySparseArray<T> {
  //
  // From lib.es5.d.ts
  //

  readonly length: number;
  join(separator?: string): string;
  slice(start?: number, end?: number): SparseArray<T>;
  indexOf(searchElement: T, fromIndex?: number): number;
  lastIndexOf(searchElement: T, fromIndex?: number): number;
  every<S extends T>(
      predicate: (value: T, index: number) => value is S,
  ): this is ReadonlySparseArray<S>;
  every(predicate: (value: T, index: number) => unknown): boolean;
  some(predicate: (value: T, index: number) => unknown): boolean;
  forEach(callbackFn: (value: T, index: number) => void): void;
  map<U>(callbackFn: (value: T, index: number) => U): SparseArray<U>;
  filter<S extends T>(predicate: (value: T, index: number) => value is S): S[];
  filter(predicate: (value: T, index: number) => unknown): T[];
  reduce(
      callbackFn: (previousValue: T, currentValue: T, currentIndex: number) => T,
      initialValue?: T,
  ): T;
  reduce<U>(
      callbackFn: (previousValue: U, currentValue: T, currentIndex: number) => U,
      initialValue: U,
  ): U;
  reduceRight(
      callbackFn: (previousValue: T, currentValue: T, currentIndex: number) => T,
      initialValue?: T,
  ): T;
  reduceRight<U>(
      callbackFn: (previousValue: U, currentValue: T, currentIndex: number) => U,
      initialValue: U,
  ): U;
  readonly [n: number]: T | undefined;

  //
  // From lib.es2015.core.d.ts
  //

  find<S extends T>(predicate: (value: T, index: number) => value is S): S | undefined;
  find(predicate: (value: T, index: number) => unknown): T | undefined;

  //
  // From lib.es2019.array.d.ts
  //

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

export interface SparseArray<T> extends ReadonlySparseArray<T> {
  //
  // From lib.es5.d.ts
  //

  length: number;
  pop(): T | undefined;
  push(...items: T[]): number;
  shift(): T | undefined;
  splice(start: number, deleteCount?: number): SparseArray<T>;
  splice(start: number, deleteCount: number, ...items: T[]): SparseArray<T>;
  unshift(...items: T[]): number;
  [n: number]: T | undefined;
}

It seemingly works fine to some extent, with two issues (apart from all the things lacked currently) I see:

First, it has problem with assigning dense array to the type. Ideally, a dense array can be assigned to a variable with sparse array type, but not the reverse. When T is simple, it works as expected, however, when T gets more complicated, the assignment sometimes gets mysteriously rejected with something like:

Type 'SomeComplicatedType[]' is not assignable to type 'ReadonlySparseArray'.
The types returned by 'slice(...).map(...)' are incompatible between these types.
Type 'U[]' is not assignable to type 'SparseArray'.

However, if I add a simple assignment to the start of a file with this kind of errors, e.g. const _a: SparseArray<string> = ['a'];, then all the errors go away in that file. This is likely a bug in TypeScript's type checker that I haven't been able to construct a minimal reproducible example for (will create a separate issue if I can construct it).

Second, the type for index definition is actually wrong. It should really have a getter returning T | undefined, but a setter only accepting T, because undefined should only be accepted for a sparse array of T | undefined, not a sparse array of T, since it would turn an empty slot into an occupied slot with undefined, affecting behavior of the iterating methods. But as far as I know, there is no way to declare different type for setter and getter on interface in TypeScript.

Given all these challenges and that it's an existing thing in JavaScript, I think it would be good to have the type declarations provided by TypeScript directly.

[fatcerberus]

Second, the type for index definition is actually wrong. It should really have a getter returning T | undefined, but a setter only accepting T

This is what noUncheckedIndexedAccess is for.

[upsuper]

This is what noUncheckedIndexedAccess is for.

Majority of arrays are still dense arrays, for which getter wouldn't return undefined when the index is within [0, length). We shouldn't change the experience of dense arrays for sparse arrays, so a global option like this is improper here I believe.

[fatcerberus]

Even for dense arrays, the type system doesn't prevent you from indexing out of range:

const arr = [ 1, 2, 3 ];
const x = arr[3];  // x: number
console.log(x);  // ...but x is actually undefined at runtime!

Sparse arrays have the additional caveat that you might have gaps inside [0, length) but from the point of view of the type system it's the same problem: which slots are occupied is not encoded in the type of the array.

[fatcerberus]

At any rate, if you don't want to use the global noUncheckedIndexedAccess option, then this feature request can't be implemented with only a lib update, since index signatures don't get the automatic | undefined getter typing without it (for backward compatibility reasons, that won't change). There would need to be direct compiler support, e.g. special syntax like sparse number[]

[upsuper]

Sparse arrays have the additional caveat that you might have gaps inside [0, length) but from the point of view of the type system it's the same problem: which slots are occupied is not encoded in the type of the array.

That's right. It is less a problem when accessing out-of-boundary returns an undefined which is not caught by the type system, because it's to some extent easier to figure out in the context and easier to diagnose. The gaps within the length is a bigger problem that developers would more likely fail to notice, especially when it only happens occasionally.

There would need to be direct compiler support, e.g. special syntax like sparse number[]

Yeah, it can't be a pure lib update, but it may not need a special syntax like that. An alternative is to allow declaring getter and setter with different types in interface.

[luckydonald]

The idea of specifically marking a list as sparse makes sense to me, so a developer will know that it behaves more like a dictionary with numbers as keys, just that it also has those iteration methods.

[RyanCavanaugh]

This is likely a bug in TypeScript's type checker that I haven't been able to construct a minimal reproducible example for (will create a separate issue if I can construct it).

This definitely sounds like a bug.

[upsuper]

A trimmed down version of the type checker issue has been reported in #50351.

It would still be good if TypeScript can provide a sparse array type, though.