Infer type of simple recursion

[rotu]

🔍 Search Terms

recursive, never, implicitly has return type 'any' because it does not have a return type annotation and is referenced directly or indirectly in one of its return expressions.

✅ 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 feature would agree with the rest of our Design Goals: https://github.com/Microsoft/TypeScript/wiki/TypeScript-Design-Goals

⭐ Suggestion

With recursive functions, it is often possible to infer the return type without function annotations.

• If all return statements have inferrable type, it would be nice to use their union as the return type of a function (even if that function is recursive)

• Similar to Ignore self tail calls when collecting the return type of a function #53995, you can assume in the body of a recursive function that any recursive call with unchanged argument types returns type never.

📃 Motivating Example

// @target: ES2020
function factorial(x:bigint){
  if (x<=0n)
    return 1n
  return x*(factorial(x-1n))
}

function factorial2(x:bigint){
  if (x<=0n)
    return 1n
  return x*(factorial2(x-1n) as bigint)
}

Workbench Repro

💻 Use Cases

TBD

[fatcerberus]

Duplicate #3336

[MartinJohns]

Relevant part from the linked issue:

Unless some use cases become super compelling in terms of complexity vs gain, we don't foresee changing this for the sake of eliding one type annotation.

I think any implementation with special rules as outlined by OP is way too complex for the small benefit. Just add a type annotation.

[rotu]

I think any implementation with special rules as outlined by OP is way too complex for the small benefit. Just add a type annotation.

According to that issue:

The current rule is that any function that sees itself during the resolution of its return type is any.

I think the resolution is as simple as changing any to never in that case, no? It seems like this is even simpler than making tail-calls a narrow special case.

[RyanCavanaugh]

I think the resolution is as simple as changing any to never in that case, no?

This wouldn't work, and would be dangerously unsound. It'd imply you could write code like

function self() {
  const arr: string[] = [];
  arr.push(self()); // OK, self() returns never here, and never subtypes string
  return 3 * (Math.random() > 0.5 ? self() : 2);
}

[MartinJohns]

It'd imply you could write code like

You actually can write code like that with noImplicitAny turned off. But no one should have that turned off.

[rotu]

This wouldn't work, and would be dangerously unsound. It'd imply you could write code like

function self() {
  const arr: string[] = [];
  arr.push(self()); // OK, self() returns never here, and never subtypes string
  return 3 * (Math.random() > 0.5 ? self() : 2);
}

I presume you mean something like this.

function f() {
  const arr: string[] = [];
  if (Math.random() < 0.5){
    arr.push(f())
  }
  return 3 * (Math.random() > 0.5 ? f() : 2);
}

When performing inference, yes, you'd allow the above code, and you'd infer that f returns type number | never i.e. number. Then when checking types, you'd complain about the bad conversion from number to string.

It similar in spirit to this, which has no trouble inferring the type of f2() and does provide a useful error:

function f2() {
  const rec = Math.random()<0.5 ? "": f2()
  const z:string[] = [rec] // Typescript correctly flags the type issue even though it's before the return statement
  return (Math.random()>0.5) ? z.length : null
}

[RyanCavanaugh]

Then when checking types, you'd complain about the bad conversion from number to string.

Checking and resolving types are done in the same pass.

See the conversation in #45213 where this was discussed at length with another contributor.

[rotu]

@RyanCavanaugh Thank you! #45213 sheds a lot of light. I had assumed the overall checking algorithm was some sort of iterative constraint solver, that is:

1. Gather all expressions and assume they are type unknown. Gather a database of type relations based on the program.
2. Iteratively narrow type bounds with those relations. Repeat until convergence or until some maximum recursion depth for generics.
3. Report any problems (like incompatible assignments or bad function calls or operators)

It hadn't even occurred to me that the checker is doing structural recursion instead of iterative constraint solving!

@MartinJohns, @fatcerberus I guess you could call this a duplicate of #3336, but it's hard to say. The discussion has scant detail, and the motivating example was fixed by #53995.