Optimize and rationalize type-checking for appropriate cases of generic functions with overloads.

[craigphicks]

Suggestion

Optimize and rationalize type-checking for appropriate cases of generic functions with overloads.

🔍 Search Terms

is:issue generic function with overloads optimize type-check
is:issue generic function overloads narrowed type-check
#27808 "extends oneof" generic constraint; allows for narrowing type parameters

List of keywords you searched for before creating this issue. Write them down here so that others can find this suggestion more easily and help provide feedback.

✅ Viability Checklist

My suggestion meets these guidelines:

• This wouldn't be a breaking change in existing TypeScript/JavaScript code
• This wouldn't change the runtime behavior of existing JavaScript code
• This could be implemented without emitting different JS based on the types of the expressions
• This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, new syntax sugar for JS, etc.)
• This feature would agree with the rest of TypeScript's Design Goals.

⭐ Suggestion

Description

A description of the proposed processing in words:
Given a module top level generic function with overloads, the proposed checking result is grossly equivalent to type checking the body of the implementation attached to the declaration of the overload, for each overload, and taking the union of the errors.

A more formal description is given below in More formal description. An illustrative example is given below in Motivating Example.

Targeted Problem:

The driving motivation for this proposal is to allow code in generics function which rely heavily on operator overloading to be written without incurring (seemingly) nuisance type checking errors. (See the code in Use Cases).

Feasability

Two concerns:

1. Correct results

• Because the type-checking result is the union of errors of indiviual type-checking runs over each overload,
  the correctness is preserved. There could be fewer errors then in the current type checking behavior,
  because the current type-checking behavior includes errros about combinations of types which do not exist
  in any of the overloads - but those are false errors.

2. Processing time

• To prevent unwanted combinatorial explosion of processing paths, the target functions will be limited to module top level functions only. Any generic functions with overloads at lower levels will processed with existing type-checking behavior.

More formal description

Suppose the overloads have signature types F_1, ...F_n, ...F_N where

type F_n = (...args:Parameters_n):ReturnType_n

Then the overloads an implementation can be written as

...
function func(...args:Parameters_n):ReturnType_n;
...
function func<F extends F1,...,F_n,...,F_N>(...args:Parameters<F>):ReturnType<F>{
  // implementation body
}

Then the virtual n_th type-checking pass processes the virtual function

function func(...args:Parameters_n):ReturnType_n{
  // body of implementation
}

which is the declaration of the n_th overload with the body of the implementation.
The union of warning/errors over all overload passes is the result, with the line numbers
in the implementation body.

📃 Motivating Example

As a toy example, consider an add function that overloads number, bigint and string,
but is restricted to adding like types only.

Create defined types to ensure uniform parameter names.

type Add<T> = (a:T,b:T)=>T
type AddN = Add<number>;
type AddB = Add<bigint>;
type AddS = Add<string>;

Define overloads.

function add(...args:Parameters<AddN>):ReturnType<AddN>;
function add(...args:Parameters<AddB>):ReturnType<AddB>;
function add(...args:Parameters<AddS>):ReturnType<AddS>;

Define implementation.

function add<F extends AddN|AddB|AddS>(...args:Parameters<F>):ReturnType<F>{
  const [a,b]=args;
  // @ts-ignore - to prevent error that number and bigint can't be added together 
  const r = a+b;
  return r;  
}

• Note : The above shows an error in the current type checking behavior, and one goal of this
  proposal is to remove that error.

Thanks to the overloads the call interface type checking is already working correctly.
(This is both the current and desired behavior).

add(1,2); // ok 
add('1','2'); // ok 
add(1n,2n) // ok 
add(1,2n) // error
add(1,'2') // error

Now we define the proposed type checker behavior in simple terms.
We want each pass (one per overload) to behave as though it were type checking
a function with the signature of the overload and the body of the implementation,
just like the following -

function add_virtual_N(...args:Parameters<AddN>):ReturnType<AddN>{
  return a+b;
}
function add_virtual_B(...args:Parameters<AddS>):ReturnType<AddN>{
  return a+b;
}
function add_virtual_S(...args:Parameters<AddN>):ReturnType<AddN>{
  return a+b;
}

and take the total of all error (in this case, none).
Just to emphasize, this is defining a result - not the mechanics for achieving the result.

A case analysis for a body with if (typeof ....) ... conditional branches, is discussed in more detail below.*

Would more passes necessarily mean more type-checking time?
Suppose that a single type check pass over a generic function takes time porportional to the number of candidate parameter combinations the type-checker must juggle. Then by filtering out the impossible combinations via individual passes,
the total time could be less, even with more passes.

Use Cases

@emilioplatzer shared the following production code in a comment on another issue, and on playground.

function checkdigit<Num extends bigint|number>(number:any, cast:(numbreString:string|number)=>Num, multipliers:Num[], divider:Num, shift?:Num, turn?:boolean):Num|null{
    var digitos=number.toString().split('');
    var i=0;
    var sumador:Num = cast(0);
    while(digitos.length){
        var digito = cast(digitos.pop()||0);
        var multiplicador = multipliers[i];
        // @ts-expect-error until I have https://github.com/microsoft/TypeScript/issues/39569
        var producto:Num = digito * multiplicador;
        // @ts-expect-error until I have https://github.com/microsoft/TypeScript/issues/39569
        sumador = sumador + producto;
        i++;
    }
    if(shift){
        // @ts-expect-error until I have https://github.com/microsoft/TypeScript/issues/39569
        sumador = sumador + shift;
    }
    // @ts-expect-error until I have https://github.com/microsoft/TypeScript/issues/39569
    var remainder:Num = sumador % divider;
    if(!remainder) return cast(0);
    if(divider-remainder>9) return null;
    // @ts-expect-error until I have https://github.com/microsoft/TypeScript/issues/39569
    return turn ? divider-remainder : remainder;
}

var isbnBook1 = "007140638" // 7
var isbnBook2 = "046505065" // 4

console.log(checkdigit(isbnBook1, Number, [9,8,7,6,5,4,3,2,1], 11), "= 7?");
console.log(checkdigit(isbnBook2, BigInt, [9n,8n,7n,6n,5n,4n,3n,2n,1n], 11n), "= 4?");

There are several places where type-check errors must be ignored.

If this proposal were enabled, the above code could be rewritten as

type Checkdigit<Num extends bigint|number> = (
    number:any, 
    cast:(numbreString:string|number)=>Num, 
    multipliers:Num[], 
    divider:Num, 
    shift?:Num, 
    turn?:boolean
)=>Num|null
type CheckdigitNumber = Checkdigit<number>
type CheckdigitBigint = Checkdigit<bigint>
function checkdigit(...args:Parameters<CheckdigitNumber>):ReturnType<CheckdigitNumber>;
function checkdigit(...args:Parameters<CheckdigitBigint>):ReturnType<CheckdigitBigint>;
function checkdigit<F extends CheckdigitBigint|CheckdigitNumber>(...args:Parameters<F>):ReturnType<F>{
    const [number, cast, multipliers, divider, shift, turn] = args as Parameters<F>;
    var digitos=number.toString().split('');
    var i=0;
    var sumador = cast(0);
    while(digitos.length){
        var digito = cast(digitos.pop()||0);
        var multiplicador = multipliers[i];
        var producto = digito * multiplicador;
        sumador = sumador + producto;
        i++;
    }
    if(shift){
        sumador = sumador + shift;
    }
    var remainder = sumador % divider;
    if(!remainder) return cast(0);
    if(divider-remainder>9) return null;
    return (turn ? divider-remainder : remainder);
}

and it would pass the type checker without errors.

There is a little more work than the original code to define the types and overloads
at the top, but that also has the advantage of forcing the correct type checking on the calls
to checkdigit, which the original code did not have.

Other

Relationship to issue #27808

Issue #27808 is titled '"extends oneof" generic constraint; allows for narrowing type parameters'.

My reading of what #27808 intends to achieve is to autogenerate the overloads, possibly virtual overloads,
to enable interface type checking. As such, it is not a requirement for this proposal,
which can use manually written call overloads. Neither is this proposal required for #27808,
because the stated goal there is only to automate interface type checking.
However, both proposals could be mutually beneficial to each other.

Type-checking behavior with conditional blocks

In the implementation body shown above

   // @ts-ignore
   const r = a+b
   return r 

we would have to use @ts-ignore or @ts-expect-error in order to pass type checking.
Suppose instead we prioritize type checking over operator-overloading the +, and
write out all the cases, as follows:

function add1<F extends AddN|AddB|AddS>(...args:Parameters<F>):ReturnType<F>{
  const [a,b]=args;
  if (typeof a === 'number' && typeof b === 'number'){
    const r = a+b;
    return r as ReturnType<F>; // compiler insists - is it related to #22617, #40111 ?
  } 
  else if (typeof a === 'bigint' && typeof b === 'bigint'){
    const r = a+b;
    return r as ReturnType<F>; // 
  } else if (typeof a === 'string' && typeof b === 'string'){
    const r = a+b;
    return r as ReturnType<F>; // 
  }
  throw "never" // 
}

Even then there is a still stubborn error on the returns requiring
as ReturnType<F> to suppress an error.

Additionally, the flow control
doesn't recognise the reduced number of possible cases implied by the overloads,
so it calculates a possible undefined return value.
Here we solve that by adding throw never.

How does the implementation fare under the proposed type-checking per-overload?

function add_virtual_n(...args: Parameters<AddN>): ReturnType<AddN> {
  const [a,b]=args;
  if (typeof a === 'number' && typeof b === 'number'){
    const r = a+b;
    return r;
  } 
  else if (typeof a === 'bigint' && typeof b === 'bigint'){
    const r = a+b;
    return r; 
  } else if (typeof a === 'string' && typeof b === 'string'){
    const r = a+b;
    return r; 
  }
  //throw "never"; // to prevent error on return type 
}

• The individual return r statement no longer error, so coercion there is not required.
• However, the final throw "never" is still there. Analysis:
  • the flow control analysis available when looking at only a single type-checking result (among those for all overloads) is not sufficient to calculate that the final 'throw "never" is not necessary
  • By keeping track of the flow across all per-overload type-checkings, the problem could be solved - however, that is beyond the scope of this proposal. This comment has mentioned the possibility of combinatorial complexity, which would be impractical in practice. Although combinatorial might not be an issue with the proposal limited only to module top level functions.
  • It would be much harder or impossible to solve it without per-overload type-checkings.
  • Since the problem already exists in the current behavior, this is not a regress in design.

[MartinJohns]

My reading of what #27808 intends to achieve is to autogenerate the overloads, possibly virtual overloads,
to enable interface type checking.

The intent is to have a generic type parameter extend one of the specified types, but have the type parameter not be a union type itself. So for example extends oneof string | number would allow the type string, and the type number, but not the type string | number. No auto-generation happening.

[RyanCavanaugh]

It would be much harder or impossible to solve it without per-overload type-checkings.

Definitely

By keeping track of the flow across all per-overload type-checkings, the problem can be solved.

This is really a death knell and why we've rejected other sorts of proposals: It's combinatorially explosive to do this, and the explosion occurs in non-pathological code. If you wrote something like

function fn1<T extends "A" | "B" | "C">(uno: T) {
    function fn2<T extends "A" | "B" | "C">(dos: T) {
        function fn3<T extends "A" | "B" | "C">(tres: T) {
            return [uno, dos, tres] as const;
        }
    }
}

then the correctly-computed result here involves typechecking the return line all 27 times (3 * 3 * 3). People can and do write large blocks of code inside nested generic functions and shouldn't encounter extreme performance degradations as a result.

[craigphicks]

My reading of what #27808 intends to achieve is to autogenerate the overloads, possibly virtual overloads,
to enable interface type checking.

The intent is to have a generic type parameter extend one of the specified types, but have the type parameter not be a union type itself. So for example extends oneof string | number would allow the type string, and the type number, but not the type string | number. No auto-generation happening.

@MartinJohns

Thank you for your reply.

I think the onus is on me to explain where I see the equivalence. Observe the following code and it's compilation result:

/---------------------------------------------------
// As a functionally equivalent substiture for #27808 line 
// function smallest<T extends oneof(string, number)>(x: T[]): T {
// we can write 
function smallest<T extends number>(x:T[]):T 
function smallest<T extends string>(x:T[]):T 
function smallest<T extends string|number>(x:T[]):T{ return x[0]; } 
/---------------------------------------------------

// these are the type-checker cases = same result for out substitute.
smallest<number>([1, 2, 3]);        // legal
smallest<string>(["a", "b", "c"]); // legal  
smallest([1, 2, 3]);               // legal
smallest(["a", "b", "c"]);         // legal 
smallest<string | number>(["a", "b", "c"]); // illegal
smallest<string | number>([1, 2, 3]);       // illegal
smallest([1, "a", 3]);                      // illegal

playground

That shows functional equivalence between extends oneof and overloads.

Just like extends oneof, overloads lock-out the use of smallest<string|number>(/anything/) because it is not in the overloads list. (Let me just say that fact is not immediately obvious, so it understandable that it would be questioned.)

Next consider implementation. I strongly suspect the most efficient way to implement extends oneof would be to make use of the existing internal overloads framework. Of course it wouldn't generate a textual interface, but it could conveniently create the same internal structures as would be created by reading the two overload lines in the above code as a way to represent the desired behavior of extends oneof.

So you are right, but I am not exactly wrong to make the functional and implementation analogy.

[craigphicks]

It would be much harder or impossible to solve it without per-overload type-checkings.

Definitely

By keeping track of the flow across all per-overload type-checkings, the problem can be solved.

This is really a death knell and why we've rejected other sorts of proposals: It's combinatorially explosive to do this, and the explosion occurs in non-pathological code. If you wrote something like

function fn1<T extends "A" | "B" | "C">(uno: T) {
    function fn2<T extends "A" | "B" | "C">(dos: T) {
        function fn3<T extends "A" | "B" | "C">(tres: T) {
            return [uno, dos, tres] as const;
        }
    }
}

then the correctly-computed result here involves typechecking the return line all 27 times (3 * 3 * 3). People can and do write large blocks of code inside nested generic functions and shouldn't encounter extreme performance degradations as a result.

I have added to the requirements for being a targeted function

The function must be a module top-level function.

That get's rid of embedded definitions and narrows the range of potential candidates further. Yet it is still sufficient to solve many pernicious problems, e.g., @emilioplatzer 's example code shown in the proposal.

Also, I have to point out that your example does not contain generic functions with overloads. The processing does not change in cases of generic functions WITHOUT overloads. Or to put it another way - in the case of the case of a generic functions WITHOUT overloads the default overload is itself - and the proposed processing of that would be identical to the current processing.

[craigphicks]

To prevent combinatorial complexity, the following control is imposed -

1. Does the generic function have overloads?

• if not, then skip.

2. Is the generic function embedded in another generic function with overloads?

• if so, then skip.

3. For each overload fn[i], type check a virtual function which has

• the input parameters of the specific overload fn[i]
• the return type equal to the union of all overload return types
• the body of the implementation
• let tcr[i] be the type check result of that virtual function

4. The union of tcr[i] over all those virtual functions is the total result which
   will be reported for the implementation body.

(Note: The proposal currently has different version of "2." - requiring the generic function be a module top level function, but that is unnecessarily strict.)

For an example of how complexity is avoided, consider the following code -

function fn1<T extends number>(uno: T): T;
function fn1<T extends bigint>(uno: T): T;
function fn1<T extends string>(uno: T): T;
function fn1<T extends number | bigint | string>(uno: T) {
  function fn2<T extends number>(dos: T): T;
  function fn2<T extends bigint>(dos: T): T;
  function fn2<T extends string>(dos: T): T;
  function fn2<T extends number | bigint | string>(dos: T) {
    function fn3<T extends number>(tres: T): T;
    function fn3<T extends bigint>(tres: T): T;
    function fn3<T extends string>(tres: T): T;
    function fn3<T extends number | bigint | string>(tres: T) {
      if (typeof uno === typeof dos && typeof uno === typeof tres)
        // @ts-ignore
        return uno + dos + tres; // Operator '+' cannot be applied to types 'T' and 'T'.
      throw "never";
    }
    if (typeof dos === "number") return fn3(3);
    if (typeof dos === "bigint") return fn3(3n);
    if (typeof dos === "string") return fn3("3");
  }
  if (typeof uno === "number") return fn2(2);
  if (typeof uno === "bigint") return fn2(2n);
  if (typeof uno === "string") return fn2("2");
}

By the above rule number 2, the inner generic functions are not processed per overload.
Therefore the type-checked virtual functions would only be those for outermost functions overloads - e.g.

function fn1_virtual_number<T extends number>(uno: T):number|bigint|string {
  function fn2<T extends number>(dos: T): T;
  function fn2<T extends bigint>(dos: T): T;
  function fn2<T extends string>(dos: T): T;
  function fn2<T extends number | bigint | string>(dos: T) {
    function fn3<T extends number>(tres: T): T;
    function fn3<T extends bigint>(tres: T): T;
    function fn3<T extends string>(tres: T): T;
    function fn3<T extends number | bigint | string>(tres: T) {
      //if (typeof uno === typeof dos && typeof uno === typeof tres)
        // @ts-ignore
        return uno + dos + tres; // Operator '+' cannot be applied to types 'T' and 'T'.
      throw "never";
    }
    if (typeof dos === "number") return fn3(3) ;
    if (typeof dos === "bigint") return fn3(3n) ;
    if (typeof dos === "string") return fn3("3") ;
    throw "never";
  }
  if (typeof uno === "number") return fn2(2) ;
  if (typeof uno === "bigint") return fn2(2n) ;
  if (typeof uno === "string") return fn2("2") ;
  throw "never";
}
//function fn1_virtual_bigint<T extends number>(uno: T):number|bigint|string {...}
//function fn1_virtual_string<T extends number>(uno: T):number|bigint|string {...}

That wouldn't be much help to the coder in terms of reducing errors, but it also wouldn't
result in processing time of combinatorial complexity. The coder could, however, write the
following to take advantage of the proposal -

type FN<T> = (uno: T, dos: T, tres: T)=> T
function helper(uno:number,dos:number,tres:number): number;
function helper(uno:bigint,dos:bigint,tres:bigint): bigint;
function helper(uno:string,dos:string,tres:string): string;
function helper<T extends number | bigint | string>(uno: T, dos: T, tres: T):T  {
  // @ts-expect-error  <- proposal would obviate the need for this
  return (uno + dos + tres);
}

which would type-check the following virtual functions:

function helper_virtual_number(uno: number, dos: number, tres: number): number {
  return (uno + dos + tres);
}
function helper_virtual_bigint(uno: bigint, dos: bigint, tres: bigint): bigint {
  return (uno + dos + tres);
}
function helper_virtual_string(uno: string, dos: string, tres: string): string {
  return (uno + dos + tres);
}

The coder could then incorporate the helper function into their code, e.g.:

function fn1v2<T extends number | bigint | string>(uno: T) {
  if (typeof uno==='number') return helper(uno,2,3);
  if (typeof uno==='bigint') return helper(uno,2n,3n);
  if (typeof uno==='string') return helper(uno,'2','3');
}

or even

function fn1v2(uno: number): number;
function fn1v2(uno: bigint): bigint;
function fn1v2(uno: string): string;
function fn1v2<T extends number | bigint | string>(uno: T) {
  // ... other code which leverages the proposed overload type-checking algorithm
  //     which is fine because (the definition of) this function fn1v2 is not embedded 
  //     in (the definition of) helper,  and (the definition of) helper is not embedded 
  //     in (the definition of) this function fn1v2.
  if (typeof uno==='number') return helper(uno,2,3);
  if (typeof uno==='bigint') return helper(uno,2n,3n);
  if (typeof uno==='string') return helper(uno,'2','3');
}

[craigphicks]

I'm going to close this because there is sufficient overlap with #27808, but it is more simple.