Variadic inference fails to infer type parameter at all

[Jamesernator]

Bug Report

🔎 Search Terms

variadic inference

🕗 Version & Regression Information

• This is the behavior in every version I tried, and I reviewed the FAQ for entries about variadic inference

⏯ Playground Link

Playground link with relevant code

💻 Code

type WasmOp<StackHead extends any[], NewStackHead extends any[]> = { 
    stackHead: StackHead, 
    newStackHead: NewStackHead, 
};

declare class i64 { #i64: true; }
declare class i32 { #i32: true; }
declare class externref { #externref: true; }

declare function compose<A extends any[], B extends any[], C extends any[], D extends any[]>(
    op1: WasmOp<A, [...B, ...C]>,
    op2: WasmOp<C, D>,
):  WasmOp<A, [...B, ...D]>;


declare const tee: WasmOp<[i32], [i32, i32]>;
declare const add: WasmOp<[i32, i32], [i32]>;
declare const testOperator: WasmOp<[i64, i64], [externref, i32, i32]>;

// This should be inferred as Op<[i64, i64], [externref, i32]> not Op<[i64, i64], [...any[], i32]>
// This happens because B is not inferred to B=[externref] as it should be
const op = compose(testOperator, add);

🙁 Actual behavior

The inferred type is incorrect, we get out Op<[i64, i64], [...any[], i32]> because B is inferred to any[].

My assumption is this is probably a design limitation, so an alternative way to write this type signature so that TypeScript can handle it would be helpful as well.

🙂 Expected behavior

It should infer that B = [externref] and hence produce the correct return type Op<[i64, i64], [externref, i32]>.

[fatcerberus]

[...B, ...C] seems ambiguous as an inference site.

Given [ ...T[], ...U[] ] and an input of [ 42, 3, "foo", "bar" ] these are all valid inferences:

• T = number, U = string
• T = string | number, U = string
• T = number, U = string | number
• T = any, U = string | number (i.e. T[] is an empty list)
• T = string | number, U = any (i.e. U[] is an empty list)

Intuitively, the first one is probably what most people want in most situations, but from the compiler's point of view, in the general case, it's ambiguous. Least-effort solution would be to pick one of the last two, and it looks like that's what the compiler is doing here.

[RyanCavanaugh]

My assumption is this is probably a design limitation

I'm glad you started there 😅. We'd need to figure out that C needs to be resolved first, because only at that point is it safe to collect candidates for B, but that sort of logic just isn't present.

This definition works for inference but doesn't catch the same error cases as the original should. With a little more elbow grease you can make Head refuse to carve off non-matching end elements.

type Head<List, Acc> = Acc extends [] ? List : Head<SliceAllButLast<List>, SliceAllButLast<Acc>>;
type SliceAllButLast<T> = T extends [...(infer R), unknown] ? R : never;
declare function compose<A extends any[], Op1Out extends any[], C extends any[], D extends any[]>(
    op1: WasmOp<A, Op1Out>,
    op2: WasmOp<C, D>,
):  WasmOp<A, [...Head<Op1Out, C>, ...D]>;


declare const tee: WasmOp<[i32], [i32, i32]>;
declare const add: WasmOp<[i32, i32], [i32]>;
declare const testOperator: WasmOp<[i64, i64], [externref, i32, i32]>;

// This should be inferred as Op<[i64, i64], [externref, i32]> not Op<[i64, i64], [...any[], i32]>
const op = compose(testOperator, add);

A better definition than this might be possible; I won't claim this is the best.

[Jamesernator]

[...B, ...C] seems ambiguous as an inference site.

At this inference site it is, there are multiple intepretations yes as you point out, however only one such interpretation is consistent with op2: WasmOp<C, D>, in particular because op2 has known type WasmOp<[i32, i32], [i32]>, so it should be possible to infer C = [i32, i32] and hence [...B, ...[i32, i32]] can be used to infer B trivially. This is the main reason this is surprising, because C is entirely known already.

Least-effort solution would be to pick one of the last two, and it looks like that's what the compiler is doing here.

And yeah it would require branching (potentially a lot in general cases of spreading [...A, ...B, ...C, ...Etc]), however the correctness would still be desirable.

---

We'd need to figure out that C needs to be resolved first, because only at that point is it safe to collect candidates for B, but that sort of logic just isn't present.

I don't know enough about TypeScript implements this stuff internally, but couldn't it just infer B = [] | [externref] | [externref, i32] | [externref, i32, i32] which are the only possibilities given WasmOp<A, [...B, ...C]> is already known to be WasmOpt<[i64, i64], [externref, i32, i32]>? Only one of these inferences would be compatible with the following op2: WasmOp<C, D> (as op2 = add has known type WasmOp<[i32, i32], [i32]>).

Again I have no idea how this is implemented internally, but I'd imagine gathering all possible candidates for B and C at the first usage WasmOp<A, [...B, ...C]>, into say:

// In all cases A = [i64, i64], so this is omitted
// D is still unknown at this point so it's also omitted
B = [], C = [externref, i32, i32]
B = [externref], C = [i32, i32]
B = [externref, i32], C = [i32]
B = [externref, i32, i32], C = []

and then narrowing it further when it hits the second WasmOp<C, D>. By noticing that only the second candidate collection of type variables is compatible with WasmOp<C = [i32, i32], D>.

[Jamesernator]

This might be a huge can of worms, but it would be helpful if TypeScript actually produced warnings where TypeScript can't infer something fully, or takes shortcuts, or cuts branches, or otherwise. Like it would be nice if compose(testOperator, add) produced a warning that B failed to infer to a narrower type.

This does go well beyond this issue though, I've actually hit a decent number of the design limitations particularly with inference where a warning would be more helpful than doing the wrong thing. A lot of them feel like they should at least be detectable for warnings, especially given that based on answers for a lot of the design limitations, the actual places where TypeScript takes shortcuts or is limited do seem to be well known by implementers.

[fatcerberus]

only one such interpretation is consistent with op2: WasmOp<C, D>, in particular because op2 has known type WasmOp<[i32, i32], [i32]>, so it should be possible to infer C = [i32, i32] and hence [...B, ...[i32, i32]] can be used to infer B trivially.

Indeed, this is true in theory, but this would require op2's type to be inferred first and IIRC inference is always done left-to-right and in a single pass. So the ambiguity still comes into play for op1. Unlike Hindley-Milner systems (e.g. Haskell), TS doesn't do full type unification; it won't go back and tighten up overwide inferences using "later" information. See #30134.

edit: Interestingly though, swapping the order of op1 and op2 doesn't fix the inference, so it does seem like TS is genuinely taking a shortcut on [...B, ...C]

[RyanCavanaugh]

The only "shortcut" that's being taken here is falling back to the constraint in the presence of zero candidates, which is sound and useful. From TypeScript's perspective, nothing wrong at all has happened -- the same mechanisms that come into play here also happen during "expected" inference situations (and indeed work has been done to make them do so per request)

[fatcerberus]

@RyanCavanaugh There are candidates for B when C is fixed first (by swapping the parameters for compose) though, right?

[RyanCavanaugh]

I don't recall how the inference rules work when there are consecutive spreads - I believe that we don't pick them up at all, even if a prior type argument has been fixed

declare function fn<T extends any[], U extends any[]>(arg: readonly [...T, ...U]): { a: T, b: U }
// a: any / any
const a = fn([1, 2, 3] as const);

declare function fn<T extends readonly any[], U extends readonly any[]>(a1: T, arg: readonly [...T, ...U]): { a: T, b: U }
const a = fn([1, 2] as const, [1, 2, 3] as const);

[Jamesernator]

Out of curiosity is it possible with the more recent TypeScript features to represent the type of what compose takes?

This is more general, and in the simplified version for just plain old unary functions, if we had a function:

function compose<A, C>(
    f: (a: A) => B,
    g: (b: B) => C,
): (a: A) => C {
    
}

Like is it possible to define the type?:

type ComposablePair<A, C> = [/* Some dark magic here */];

Such that for example the following happens:

declare const p1: [(a: A) => B, (b: B) => C];
const p2: ComposablePair<A, C> = p1; // Allowed

// Can't compose B and C so this won't be assignable
declare const p3: [(a: A) => B, (c: C) => D];
const p4: ComposablePair<A, D> = p3; // Not allowed

I believe this is roughly equivalent to a dependent union (roughly dependent sum, except not requiring the disjoint union "tag"). I'm not sure just how much power TypeScript has, but I have seen a lot of fairly powerful types done with mapped types so it might be possible.