Better title needed: Issue with Generics and Recursion?

[SephReed]

TypeScript Version: 3.7.5

Search Terms:
Generic recursion
Subtype
Also, already asked elsewhere

Code

export type TestProxy<TARGET> = (
  TARGET extends Array<any> ? TestArray<TARGET> : 
  TARGET
)

type TestArray<TYPE extends Array<any>> = {
  [key in (keyof TYPE & number)]: TYPE[key];
}
& Omit<TYPE, keyof Array<any>> // Special case for Array extensions
& {
  length: any, push: any, concat: any,
  join: any, reverse: any, shift: any, slice: any,
  sort: any, splice: any, unshift: any, indexOf: any,
  lastIndexOf: any, every: any, some: any, forEach: any,
  filter: any, reduce: any, reduceRight: any, find: any,
  findIndex: any, fill: any, copyWithin: any, [Symbol.iterator]: any,
  entries: any, keys: any, values: any, [Symbol.unscopables]: any,
  includes: any, flatMap: any, flat: any,

  // pop: any,  // CASE A everything works
  pop(): TestProxy<TYPE[number]>;  // CASE B 
  map<OUT>(cb: (it: TYPE[number], index: number, array: TestArray<TYPE>) => OUT): TestProxy<Array<OUT>>;
}

type TYPE = Array<string> & { extraField: string };
const thing: TYPE = null as any as TestProxy<TYPE>;  // Works in CASE A
const hat: string = "hat" as TestProxy<"hat">; // Always works

function proxyMe<TYPE>(target: TYPE): TestProxy<TYPE> {
  return target as any; // imagine proxy
}

const obj: { arr: number[][] } = { arr: [] };
const testArr = proxyMe([[1], [2], [3]]);
obj.arr = testArr;  // CASE A: works -- CASE B: Type 'TestArray<U[]>' is not assignable to type 'U[]

Expected behavior:
In Case A, it is valid to say TYPE === TestProxy<TYPE> for all types. Therefore, having pop() return TestProxy<TYPE> in Case B should be valid.

Actual behavior:
In Case A, everything works.

In Case B, this error arises (see playground link)

Type 'TestArray<number[][]>' is not assignable to type 'number[][]'.
The types returned by 'pop()' are incompatible between these types.
Type 'TestArray<number[]> | undefined' is not assignable to type 'number[] | undefined'.
Type 'TestArray<number[]>' is not assignable to type 'number[] | undefined'.
Type 'TestArray<number[]>' is not assignable to type 'number[]'.
The types returned by 'map(...)' are incompatible between these types.
Type 'TestArray<U[]>' is not assignable to type 'U[]'

Playground Link:
Playground Link

Related Issues:
I've heard there are limitations to Generics that have been found elsewhere

[RyanCavanaugh]

Please ping me if you can supply a simpler repro; we generally cannot handle intricate and long examples like this in a timely manner

[SephReed]

I've got a simpler repro here:

type ARR<TYPE> = {
  pop(): TYPE;
  map<OUT>(cb: () => OUT): ARR<OUT>
  [key: number]: TYPE;
};

type Proxied<TARGET> = (
  TARGET extends ARR<any> ? ProxiedArray<TARGET> : 
  TARGET
)

type ProxiedArray<TYPE extends ARR<any>> =
  Omit<TYPE, "pop" | "map"> // don't want overloads
& {
  // pop(): any; // CASE A : works
  pop(): Proxied<TYPE[number]> // CASE B : fails
  map<OUT>(cb: () => OUT): Proxied<ARR<OUT>>;
}

const hat: string = "hat" as Proxied<string>; // Always works

type TYPE = ARR<string> & { extraField: string };
const thing: TYPE = null as any as Proxied<TYPE>;  // Works in CASE A


const testArr = {} as Proxied<ARR<ARR<string>>>;
testArr.pop(); // ProxiedArray

const obj = {} as { prox: ARR<ARR<string>> } ;
obj.prox = testArr;  // CASE A: works -- CASE B: Type 'ProxiedArray<ARR<OUT>>' is not assignable to type 'ARR<OUT>'

Playground Link

[tadhgmister]

A possibly clearer demo with playground

type TestProxy<TARGET> = TARGET extends Array<any> ? MockArray<TARGET> : TARGET;

/** wrapper for array with a few custom overrides, intent is to be fully compatible with normal array */
type MockArray<Orig extends Array<any>> = 
    & Overrides<Orig[number]> // overrides provided
    & Omit<Orig, keyof Overrides<any>> // all original fields except overrides
    & {[Symbol.iterator]: any; [Symbol.unscopables]: any; } // since Omit also gets rid of symbol keys we need this to remain compatible.

interface Overrides<T> {
    pop(): TestProxy<T> | undefined;
    map<OUT>(cb: (elem: T, index: number, arr: this) => OUT): MockArray<OUT[]>;
}
function showErrWithArrGeneric<A extends any[]>(testArr: MockArray<A>){
    // only when pop is commented out the error shows extra line about 'MockArray<A>' is assignable to the constraint of type 'A'
    const normalArr: A = testArr;
} /*
Type 'MockArray<A>' is not assignable to type 'A'.
*/

function showErrWithObj<T>(testObj: TestProxy<T>){
    const normalObj: T = testObj;
} /*
Type 'TestProxy<T>' is not assignable to type 'T'.
  'TestProxy<T>' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.
    Type 'T | MockArray<T>' is not assignable to type 'T'.
      'T | MockArray<T>' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.
--->    Type 'MockArray<T>' is not assignable to type 'T'.
          'MockArray<T>' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.ts(2322)
*/
function showErrWithArr<T>(testArr: MockArray<T[]>){
    // this passes if Overrides.pop() is commented out
    const normalArr: T[] = testArr;
} /*
Type 'MockArray<T[]>' is not assignable to type 'T[]'.
  The types returned by 'pop()' are incompatible between these types.
    Type 'TestProxy<T> | undefined' is not assignable to type 'T | undefined'.
      Type 'TestProxy<T>' is not assignable to type 'T | undefined'.
        Type 'T | MockArray<T>' is not assignable to type 'T | undefined'.
          Type 'MockArray<T>' is not assignable to type 'T | undefined'.
-------->   Type 'MockArray<T>' is not assignable to type 'T'.
              'MockArray<T>' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.
                Type 'TestProxy<T>' is not assignable to type 'T'.
                  'TestProxy<T>' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.
                    Type 'T | MockArray<T>' is not assignable to type 'T'.
                      'T | MockArray<T>' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.
------------------>     Type 'MockArray<T>' is not assignable to type 'T'.
                          'MockArray<T>' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.ts(2322)
*/

When the map override is commented out concrete arrays work fine since there is no wildcard generics anywhere and typescript can figure out that all is fine:

interface Overrides<T> {
    pop(): TestProxy<T> | undefined;
    // map<OUT>(cb: (elem: T, index: number, arr: this) => OUT): MockArray<OUT[]>;
}
declare function proxyMe<TYPE>(target: TYPE): TestProxy<TYPE>
const a: number[] = proxyMe([1,2,3]) // works fine

When pop override is commented out then MockArray<T[]> is assignable to T[] since typescript knows there aren't any weird extensions on an array so the third case passes.

interface Overrides<T> {
    //pop(): TestProxy<T> | undefined;
    map<OUT>(cb: (elem: T, index: number, arr: this) => OUT): MockArray<OUT[]>;
}
function WORKS_NOW<T>(testArr: MockArray<T[]>){
    const normalArr: T[] = testArr;
} 

So I know the root error is that MockArray<A> is not assignable to A for wildcard generics because A as a total wildcard generic could defines extra overloads for pop or map then we'd omit them in our mock so it's not unconditionally assignable. It is still strange we get the error message with repeating lines though.

Hope this helps :)

[SephReed]

That makes sense, and it feels good to finally understand why it's not 100% valid typing.

If I understand correctly, an exact type (#12936) would be able to solve this by defining the variable as non-extendable, correct?

Then users wouldn't be allowed to override things that I'm expecting them not to.

[SephReed]

Can you think of a way to write:

type TestProxy<TARGET> = TARGET extends Array<any> ? MockArray<TARGET> : TARGET;

such that TARGET will only become a MockArray if it is exactly an array and not an extension?

[tadhgmister]

Can you think of a way to write:

type TestProxy<TARGET> = TARGET extends Array<any> ? MockArray<TARGET> : TARGET;

such that TARGET will only become a MockArray if it is exactly an array and not an extension?

you can by somehow using Array<any> extends TARGET but I'm pretty sure when typescript puts a deferred generic through one of these conditional types it can only statically know that the result is a union of all possible branches, so no matter how you setup the conditional type a wildcard generic will still be seen as T | TestArray<T> and therefore only pass if TestArray<T> is unconditionally assignable to T, so I'm afraid to satisfy typescript you need to use an intersection with the underlying type. I think my suggestion here is as good as you'll get, the only improvement might be to have the overrides extend Array<E> so it will catch you if your overrides are blatantly incompatible with a standard array

type TestProxy<T> = T extends Array<any> ? TestArray<T> : T;
type TestArray<Arr extends any[]> = ArrOverrides<Arr[number]> & Arr;
interface ArrOverrides<E> extends Array<E>{
/* Interface 'ArrOverrides<E>' incorrectly extends interface 'E[]'.
     The types returned by 'find(...)' are incompatible between these types.
       Type 'string' is not assignable to type 'E | undefined'.ts(2430) */
    find(): string;
}

If you really wanted to put some extra checks to not allow weird extra fields then you could use any[] extends Arr inside the TestArray definition like this:

type TestArrayValidating<Arr extends any[]> = any[] extends Arr ? ArrOverrides<Arr[number]> & Arr : never;
type Valid = TestArrayValidating<number[]>
type Invalid = TestArrayValidating<number[] & {extraField: string}>;
type MaybeShouldBeValidButIsnt = TestArrayValidating<Valid> // passing a TestArray ends up never

When typescript puts a generic through this, it doesn't know if any[] is assignable to it so it takes the union of both branches, but since one of the branches is never the union is the same as just the first branch so this is just as compatible with wildcard (deferred) generics as the first definition, and if you expect people to add weird extra fields and want to end up breaking their types then this might be useful? I feel like wanting TestArray<TestArray<number[]>> to still be valid would be better than wanting extra fields to cause it all to end up never.

Anyway, good luck with your really dope shit 😃

[SephReed]

Thank you for all your patience.

One last thing: if an Exact<TYPE> ever comes into existence, it should -- theoretically -- make it so the equivalence I'm trying to achieve is possible, right?

[tadhgmister]

One last thing: if an Exact<TYPE> ever comes into existence, it should -- theoretically -- make it so the equivalence I'm trying to achieve is possible, right?

Yes probably, I have something close implemented below. But I'm going to make an argument for why what you are trying to achieve isn't actually what you want. (And why this is true for pretty much everyone looking for an Exact<TYPE>which is why it is never going to get added to typescript)

I brought up any[] & {extraField: any} as a counter example when you were saying things like "provably an error in the compiler", and once you realize that that is the kind of case that typescript is complaining about it is natural to want to specify a type contract that makes that illegal to use in your code.

What you don't realize that you are more likely to run into reasonable cases of "array extensions" than unreasonable ones. Like if you pass an array with an extra field to a function called proxyMe which is designed for normal arrays, you shouldn't get your hopes up that it preserves your unusual behaviour. However the following 2 lines of code is very reasonable to expect to work for any (valid array) type of MyArr:

declare const testArr: TestArray<MyArr>;
const x: MyArr[0] = testArr[0]; // first element of MyArr assigned to first element of wrapper

Normal arrays have an index number not a specific index for 0, but array literals do:

type MyArr = ["a", "b", "c"];
type ExplicitEquivelent = Array<"a"|"b"|"c"> & {0: "a", 1:"b", 2:"c", length: 3}

This is a valid extension of the basic array type that you almost certainly already support, and the definition of TestArray that always uses an intersection with the original type will always preserve this. If we just want to ensure that the type is a plain array then we end up losing information and this ends up failing:

type EnsureRegularArray<T> = T extends Array<infer E> ? Array<E> : T;

declare const testArr2: EnsureRegularArray<MyArr>;
const y: MyArr[0] = testArr2[0];  // Error: Type '"a" | "b" | "c"' is not assignable to type '"a"'.

If your case primarily revolves around the pop method I doubt array literals are an expected use case, but I doubt you want to deny them just because they are "more specific".

Now lets talk about how typing relates to runtime, lets say we did have syntax of this form:

type DreamProxy<T> = T isMutuallyAssignableWith Array<infer E> ? OverrideArr<E> : T

In this case the type checker would know that the first branch is only visited if Array<E> is assignable to T so we just need to validate that OverrideArr<E> is assignable to Array<E> (which it is because we extended Array) so this would play nice with wildcard generics. Yay!

Here's the catch, if we implement proxyMe to check obj instanceof Array to actually check if we are using an array, then it means that an array extension will be proxied at runtime even though the type will claim to return the same object. I'm pretty sure this is the primary argument against the Exact<TYPE>, because most of the time you can't actually enforce at runtime that only an exact type signature will be converted. If you still have any doubts try running this playground since it should convince you that this notion of Exact<TYPE> is almost certainly not what you want.

// closest thing to isMutuallyAssignableWith that we can get.
// only gives ArrOverrides <E> if Array <E> is mutually assignable to T and returns T in any other case.
// note that the `&T` shouldn't affect anything, it's just a way of getting around
// typescripts limitation that it thinks that that branch wouldn't be assignable to T
type DreamProxy<T> = T extends Array<infer E> ? (Array<E> extends T ? ArrOverrides<E> & T : T) : T;
// note that the point of this demo is to show that this DreamProxy type is in fact A NIGHTMARE
// because we have no way to enforce at runtime that only run of the mill arrays would be proxied

function proxyMe<T>(obj: T): DreamProxy<T> {
    if (obj instanceof Array) {
        // ANY ARRAY OBJECT WILL BE PROXIED, SO WHY ARE WE CLAIMING OTHERWISE IN DreamProxy?
        return new ArrOverrides(...obj) as DreamProxy<T>;
    } else {
        return obj as DreamProxy<T>;
    }
}
class ArrOverrides<E> extends Array<E>{

    pop() {
        return proxyMe(super.pop());
    }
    map<OUT>(cb: (it: E, index: number, array: E[]) => OUT) {
        return proxyMe(super.map(cb))
    }
    rock_out() {
        console.log(this, "IS ROCKING OUT!!");
    }
}

const VALID_AND_WORKS = proxyMe([1, 2, 3]);
VALID_AND_WORKS.rock_out(); // yay!

const ARR = [1, 2, 3] as const;
const TOTALLY_VALID_USE_CASE_FOR_PROXY = proxyMe(ARR);
TOTALLY_VALID_USE_CASE_FOR_PROXY.rock_out(); // works at runtime, typescript isn't convinced.


const LESS_VALID_USE_CASE = ["a", "b", "c"] as string[] & { extraField: string };
LESS_VALID_USE_CASE.extraField = "Some data here"

const WRONG = proxyMe(LESS_VALID_USE_CASE); 
// typescript claims this is valid but the proxy didn't keep it
console.log("extra field on proxy, which we aren't supporting is: ", WRONG.extraField);
// again, rock_out() works at runtime but we've told typescript otherwise
WRONG.rock_out()

So yeah, DreamProxy is valid, the &T part in it is to get around a limitation in typescript and should not affect the effective types at all. There is absolutely no way to enforce it at runtime.

[SephReed]

I see why DreamProxy doesn't exist. And, for my use case, it's totally okay if extended and const arrays are blocked, but the typing on DreamProxy seems nightmarishly confusing for any user who'd get an error there.

---

At this point, I feel content to have seen what seems to be every possible option. Your first suggestion is the best.

---

It still seems like there should be a way to do this. This type exists, I've created it. I just don't know how to explain it.

[RyanCavanaugh]

@SephReed is there a TL;DR version of something actionable we can look at, or can I mark this as Question ?

[SephReed]

tl;dr It is impossible to describe this type such that it is equivalent to the object it is proxying:

type Impossible<TYPE> = ???;

let numberOfTimesPopHasBeenUsed = 0;

function proxyAnything<TYPE>(target: TYPE): Impossible<TYPE> {
  if (Array.isArray(target) === false) { return target;  }

  return new Proxy(target, {
    get: (_, propName) => {
      if (propName === "pop") { 
        numberOfTimesPopHasBeenUsed++;
        return () => proxyAnything(target.pop()); 
      }
      if (propName === "map") { 
        return (...args: any[]) => proxyAnything(target.map(...args)); 
      }
      if (propName === "target") {
        return target;
      }
      return target[propName];
    }
  });
}