Overly strict matching of function overloads to function intersections, and an algorithm that could help

[craigphicks]

🔍 Search Terms

function intersections
matching function intersections to function overloads

✅ Viability Checklist

• 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 isn't a request to add a new utility type: https://github.com/microsoft/TypeScript/wiki/No-New-Utility-Types
• This feature would agree with the rest of our Design Goals: https://github.com/Microsoft/TypeScript/wiki/TypeScript-Design-Goals

⭐ Suggestion

Intersections of functions occur naturally when the superposition of two or more functions which take function as arguments.
Example: naturally occuring intersection of functions as parameters

interface FMap<T,R> {
    f:(x:T)=>R
    g(f:(x:T)=>R):R;
}
declare const x1: FMap<1|2,1|2>;
x1.g(x1.f); // no error
declare const x2: FMap<2|3,"2"|"3">;
x2.g(x2.f); // no error
const x: Math.random() < 0.5 ? x1 : x2;
x.g; // (method) FMap<T, R>.g(f: ((x: 1 | 2) => 1 | 2) & ((x: 2 | 3) => "2" | "3")): 1 | 2 | "2" | "3"

In this example it is the function x.g that has an intersection of functions as a parameter.

In the general case a argument function passed to such an intersection of function parameters may need to be an overload, and TypeScript has an algorithm to type check that argument (the function overload) against the parameter (the intersection of functions). However, the algorithm is too strict in some cases, and rejects some valid overloads. Examples of valid overloads that are rejected are shown, and an algorithm that would pass those valid overloads is proposed.

📃 Motivating Example

The value of x.g is a function that takes a function as an argument. When x is the superpostion (union) of two FMap objects, the intersection of the argument types of the two functions is the type of the argument of the intersection function. Because g takes a function argument, the parameter type of g is the intersection of two functions.

What exactly does intersection of two functions mean?

When we say union of two functions it is just stating a fact about the flow analysis. The function itself is not a new function, the user need to provide no new coding. Instead, the compiler recognizes that only the interscetion of the argument types of the two functions is valid for the union function:

x.f(1); // error
x.f(2); // no error
x.f(3); // error

In contrast, in the general case, the "intersection" function that is passed to x.g may need to be a new function with an input domain that encompasses the input domains of the two functions. In this case neither x1.f nor x2.f alone satisfies that condition:

x.g(x1.f); // error because input domain of x1.f is too narrow
x.g(x2.f); // error because input domain of x2.f is too narrow

The user must provide a new function that has the union of the input domains of x1.f and x2.f:

function ft1(x:1|2|3):1|2|"2"|"3" {
    if (x!==3) return x1.f(x);
    else return x2.f(x);
}

Try it

x.g(ft1); // correctly error
//  ~~~
// Argument of type '(x: 1 | 2 | 3) => 1 | 2 | "2" | "3"' is not assignable to parameter of type '((x: 1 | 2) => 1 | 2) & ((x: 2 | 3) => "2" | "3")'.
//   Type '(x: 1 | 2 | 3) => 1 | 2 | "2" | "3"' is not assignable to type '(x: 1 | 2) => 1 | 2'.
//     Type '1 | 2 | "2" | "3"' is not assignable to type '1 | 2'.
//       Type '"2"' is not assignable to type '1 | 2'.ts(2345)

x.g(ft1) is an error because single function ft1 signature has a wider input-output map than the intersection of the input-output maps of x1.f and x2.f.

Actually the implementation is fine - it does deliver the required narrowness of the required input-output map. We just need to write a narrower overload signature to match the parameter for x.g:

Example 1

function ft2(x:1|2):1|2;
function ft2(x:3):"2"|"3";
function ft2(x:1|2|3):1|2|"2"|"3" {
    if (x!==3) return x1.f(x);
    else return x2.f(x);
}
x.g(ft2); // error
//  ~~~
// Argument of type '{ (x: 1 | 2): 1 | 2; (x: 3): "2" | "3"; }' is not assignable
// to parameter of type '((x: 1 | 2) => 1 | 2) & ((x: 2 | 3) => "2" | "3")'.
//   Type '{ (x: 1 | 2): 1 | 2; (x: 3): "2" | "3"; }' is not assignable to type '(x: 2 | 3) => "2" | "3"'.
//     Types of parameters 'x' and 'x' are incompatible.
//       Type '2 | 3' is not assignable to type '1 | 2'.ts(2345)

Unfortunately - it's still an error, but the error message is different. However, it doesn't need to be an error; the specified overload is sound. No error here would be preferable.

If we make the overload declaration match intersection shape exactly (note: intersection member order is a free parameter), then it works:

function ft2(x:1|2):1|2;
function ft2(x:2|3):"2"|"3";  // added 2 to domain
function ft2(x:1|2|3):1|2|"2"|"3" {
    if (x!==3) return x1.f(x);
    else return x2.f(x);
}
x.g(ft2); // no error

which is good, but we shouldn't have to do that.

Example 2

function ft3(x:1):1|2;
function ft3(x:3):"2"|"3";
function ft3(x:2):1|2|"2"|"3";
function ft3(x:1|2|3):1|2|"2"|"3"{
    if (x===1) return x1.f(x);
    if (x===3) return x2.f(x);
    return Math.random() < 0.5 ? x1.f(x) : x2.f(x);
}
x.g(ft3); // error

Again, this doesn't need to be an error; the specified overload is sound. No error here would be preferable.

Example 3

interface A9<T> {
    t: T;
    f():T;
    g(f: ()=>T):T[];
};

declare const a9: A9<string> | A9<number>;
declare const f9: A9<string>["f"] & A9<number>["f"];
a9.g(f9); // NO ERROR when argument is defined as an intersection of functions type


const f91 = ()=>Math.random() < 0.5 ? Math.random().toString() : Math.random();
a9.g(f91); // INCORRECT ERROR;  argument is as an actual valid implementation, should not be error.
//   ~~~
// Argument of type '() => "hello" | 42' is not assignable to parameter of type '(() => string) & (() => number)'.
//   Type '() => "hello" | 42' is not assignable to type '() => string'.
//     Type 'string | number' is not assignable to type 'string'.
//       Type 'number' is not assignable to type 'string'.ts(2345)

An algorithm that would pass all the above examples:

• Algorithm to check that an overload f = { f[0];f[1]; ...} is a valid argument to a function g = g[0] && g[1] && ...
  • Check that the domain of f at least includes the whole domain of g
    • if Union[i in 0,1,..] Parameters<g[i]> extends Union[i in 0,1,..] Parameters<f[i]> then
      • OK
    • else
      • signature error
  • For each f[i]
    • hadMatch = false
    • gReturn = never;
    • For each g[j] // j'th intersection member
      • For each g[j][k] // k'th overload member of g[j]
        • If Parameters<f[i]> extends Parameters<g[j][k]> then
          • hadMatch = true
          • gReturn = Union[gReturn, ReturnType<g[j][k]>]
    • If !hadMatch or !(ReturnType<f[i]> extends gReturn) then
      • signature error

In words, the algorithm passes if the overload f is both large enough to support the domain of g, and small enough to be a subset of the input-output mappings of g.

💻 Use Cases

Parameters which are function intersections generally require arguments which are described by function overloads.
This proposal showed a class of valid overloads that are currently rejected by the compiler, and offers a proposed algorithm that would accept them.

• What workarounds are you using in the meantime?
  An any cast.

Additional Information

This proposal doesn't include information about the current algorithm, and the reasons why it was chosen.
It is not clear whether the current algorithm is or is not the best choice due to other factors not considered here, but it is clear that it is not the only choice.