Feature request: Dependent contextual inference

### 🔍 Search Terms

Dependent contextual inference, self type checking types, can't infer type parameters from context-sensitive expressions, self referencing types

### ✅ Viability Checklist

- [x] This wouldn't be a breaking change in existing TypeScript/JavaScript code
- [x] This wouldn't change the runtime behavior of existing JavaScript code
- [x] This could be implemented without emitting different JS based on the types of the expressions
- [x] This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, new syntax sugar for JS, etc.)
- [x] This isn't a request to add a new utility type: https://github.com/microsoft/TypeScript/wiki/No-New-Utility-Types
- [x] This feature would agree with the rest of our Design Goals: https://github.com/Microsoft/TypeScript/wiki/TypeScript-Design-Goals

### ⭐ Suggestion

To keep it really terse the feature request (which I'm calling "dependent contextual inference") is when a contextual type of an expression is in the form `T extends F` perform `n` checks each with contextual type `T extends F` where `Tn-1` is the type of the expression after check `n-1` for `n > 1` and `T` for `n = 1` until the `Tn` is identitcal to `Tn-1` or `n >= 5`

Let's take an example...

```ts
declare const f:
unknown }>
(t: T) =>
ReturnType

const r = f({
a: "hello",
b: a => a.toUpperCase()
// ~
// 'a' is of type 'unknown'. (18046)
})
```

Today `a` is inferred as `unknown` that's because there's just two passes of check that happen, in the first pass the object literal is inferred as `{ a: string, b: anyFunctionType }` and because it's effectively a non-inferrable type as it contains an `anyFunctionType`, `T` has no inference candidates leading `T` to be inferred with it's constraint... and the second pass just happens with `T` being fixed to what was inferred in the first pass ie as if the user has written `f<{ a: unknown, b: (a: unknown) => unknown }>(...)`.

With dependent contextual inference the first pass remains the same and the object literal's type is inferred as `{ a: string, b: anyFunctionType }` but the second pass happens with the contextual type as `T extends { a: unknown: b: (a: { a: string, b: anyFunctionType }["a"]) => unknown }` and now object literal's type becomes `{ a: string, b: (a: string) => string }`, and checker does one more pass with contextual type `T extends { a: unknown, b: (a: { a: string, b: (a: string) => string }["a"]) }` resulting the object literal's type being the same as before and the checker stops as the last two checks produced identical types. And finally `T` is inferred as `{ a: string, b: (a: string) => string }`. And the checker does one final check with `T` being fixed to that as if the user had written `f<{ a: string, b: (a: string) => string }>(...)`.

I've implemented a shabby version in PR #64092 but maybe there's a better way to implement it.

### 📃 Motivating Example

Imagine you have a state machine like library written in javascript...

```js
const runMachine = (definition) => {
let { state, context } = definition.initial
while (true) {
if (state === undefined) break;
const next = definition.transitions[state]({ context })
state = next?.state
context = next?.context
}
return { state, context }
}

const result = runMachine({
initial: {
state: "loggedOut",
context: {}
},
transitions: {
loggedOut: ({ context }) => {
return { state: "loggingIn", context: { username: "devanshj", password: "1234" } }
},
loggingIn: ({ context }) => {
if (context.username === "devanshj" && context.password === "1234") {
return { state: "loggedIn", context: { ...context, accessToken: "whatever" } }
} else {
return { state: "loggedOut", context: { failedOnce: true } }
}
},
loggedIn: ({ context }) => {
console.log(context.accessToken)
}
}
})
```

And now you want to write types for it... Today the best typings look like this (with a little change in api ie the double invocation `runMachine()(...)`)...

```ts
declare const runMachine:
() =>
["context"] }) => void | TMachine
}
}>
(definition: TDefinition) =>
TMachine

const result = runMachine<
| { state: "loggedOut", context: {} | { failedOnce: boolean } }
| { state: "loggingIn", context: { username: string, password: string } }
| { state: "loggedIn", context: { username: string, password: string, accessToken: string, failedOnce?: boolean } }
>()({
initial: {
state: "loggedOut",
context: {}
},
transitions: {
loggedOut: ({ context }) => {
return { state: "loggingIn", context: { username: "devanshj", password: "1234" } }
},
loggingIn: ({ context }) => {
if (context.username === "devanshj" && context.password === "1234") {
return { state: "loggedIn", context: { ...context, accessToken: "whatever" } }
} else {
return { state: "loggedOut", context: { failedOnce: true } }
}
},
loggedIn: ({ context }) => {
console.log(context.accessToken)
}
}
})
```

This is the best because the expectation is that the final result is a discriminated union so that when you do `if (result.state === "loggedIn")` it narrows the result and the context in a way you can read `accessToken` from the context which is gauranteed by the logic. Another expectation is that each transition receives the `context` in the shape that is again gauranteed by the definition logic eg `loggingIn` must receive a context where `username` and `password` are defined because each `loggedOut` sends it.

So any other easy solution (eg the following) won't work...

```ts
declare const runMachine:

(definition: {
initial: { state: TState, context: TContext },
transitions:
Record<
TState,
(current: { context: TContext }) => void | { state: TState, context: TContext }
>
}) =>
{ state: TState, context: TContext }
```

Now in theory we can type it like this...

```ts
declare const runMachine:
}) =>
| void
| { state: keyof TDefinition["transitions"], context: object }
}
}>
(definition: TDefinition) =>
{ [S in keyof TDefinition["transitions"]]: { state: S, context: Context } }[keyof TDefinition["transitions"]]

// iterative over all transitions and collect the context for the given state
type Context =
| { [S in keyof TDefinition["transitions"]]:
ReturnType extends infer R
? R extends unknown
? R extends { state: TState, context: infer C }
? C
: never
: never
: never
}[keyof TDefinition["transitions"]]
| (TDefinition["initial"]["state"] extends TState
? TDefinition["initial"]["context"]
: never)

// just to satisfy the type checker
type Definition =
{ initial: { state: keyof any, context: object }, transitions: Record unknown> }
```

The result? It works exactly like the manually annotated one (ie each transition gets the context it would expect and the final result is a discriminated union) and the user has to write zero type annotations...

The only caveat is that it relies on dependent contextual inference and doesn't actually work today.

### 💻 Use Cases

Because any generic signature can be rewritten in form of `T extends F` and leverage dependent contextual inference, a lot of problems can be solved, here are few...

1. Inferring invariant generics

Let's take a simple example...

```ts
declare const update:
(f: (previous: T) => T) => T

update(previous => ({ count: typeof previous.count === "number" ? previous.count + 1 : 0 }))
```

Here `previous` in inferred as `unknown` so this doesn't compile. But it can be refactored to `T extends F`...

```ts
declare const update:
) => unknown>(f: T) => ReturnType

update(previous => ({ count: typeof previous.count === "number" ? previous.count + 1 : 0 }))
```

Here `previous` is inferred as `{ count: number }` and it compiles. It also gracefully handles infinite loops...

```ts
declare const update:
) => unknown>(f: T) => ReturnType

udpate(lol => ({ lol }))
// ~~~~~~~~~~~~~~~~~
// Dependent contextual inference requires too many passes and possibly infinite
```

However the user can use getters if they meant to a circular shape which would infer a recursive type...

```ts
declare const update:
) => unknown>(f: T) => ReturnType

const x = udpate(lol => ({ get lol() { return lol } }))
x.lol.lol.lol.lol.lol.lol // compiles
```

A popular user of invaraint generic would be [zustand](https://github.com/pmndrs/zustand)...

```ts
declare const create:
>["set"]
, get: Store>["get"]
) => unknown
>
(t: T) =>
Store>

interface Store
{ get: () => T
, set: (value: Partial) => void
}

const store = create((set, get) => ({
count: 0,
increment: () => set({ count: get().count + 1 })
}))
```

Today `store` is inferred as `Store` hence zustand requires it's users to explicitly type the generic with `create()(...)`, but with dependent contextual inference `store` can be inferred as `Store<{ count: number, increment: () => void }>`

2. Inferring m times n generics

Today we already do a good job of inferring a chain of n-generics...

```ts
declare const useQuery:

(query: { key: K, fetch: (key: K) => T, select: (data: T) => U }) => U

const result = useQuery({
key: "0",
fetch: key => +key,
select: data => [data]
})
```

But because we don't have existential types it's hard to support m times n generics... Except in theory we can rewrite them in `T extends F` form and it'd work with dependent contextual types...

```ts
declare const useQueries:
unknown, select: (data: ReturnType) => unknown } }>
(queries: T) =>
{ [I in keyof T]: ReturnType }}

const results = useQueries([
{
key: "0",
fetch: key => +key,
select: data => [data]
},
{
key: 1,
fetch: key => key.toString(),
select: data => ({ data })
}
])
```

A popular user of this m times n generics use case is [tanstack query](https://github.com/TanStack/query). Their `useQueries` looks like the `useQueries` above and is completely untyped.

3. Inferring self referencing generics

Today we again already do a good job of inferring `T extends F` types which are useful when typing any self referencing generics which occur in eDSLs example...

```ts
declare const createMachine:
>(definition: T) => "STUB"

type StateNode = {
initial?: keyof T["states" & keyof T],
states?: {
[K in keyof T["states" & keyof T]]: StateNode
}
}

createMachine({
initial: "a", // can only be "a" or "b"
states: {
a: {
initial: "a1", // can only be "a1" or "a2" or "a3"
states: {
a1: {},
a2: {},
a3: {}
}
},
b: {}
}
})
```

But you can't have functions in them as their parameters don't get inferred...

```ts
declare const createMachine:
& { context: object }>(definition: T) => "STUB"

type StateNode = {
initial?: keyof T["states" & keyof T],
states?: {
[K in keyof T["states" & keyof T]]: StateNode
},
entry?: (context: C) => void
}

createMachine({
initial: "a",
context: { hello: "world" },
states: {
a: {
initial: "a1",
states: {
a1: {},
a2: {},
a3: {}
},
entry: (context) => { // context is `object` instead of `{ hello: string }`
console.log("entered node a")
}
},
b: {}
}
})
```

This again is fixed by dependent contextual inference.

A popular user that will get benefitted by this is [xstate](https://github.com/statelyai/xstate). In fact xstate is the main motivation for this feature request, even in a langauge as powerful as typescript there is no smart type-safe state machine abstraction out there.

4. Many more use cases

Because `T extends F` are what I call "self-type-checking types" they are already very powerful and any inference problem can be refactored to it. So I think there are many many open issues that can be fixed by this... The only missing piece is that they don't work as expected when the expression is context-sensitive ie if it has functions in it... And hopefully we can fill that gap.

Thanks for reading!

PS: Linking some issues this will indirectly fix...
- #49618
- #51377
- #40439
- #51612
- #52047
- perhaps many more I'll update as I find them

Start by reviewing the dependent contextual inference proposal and the existing implementation in PR #64092. Compare its behavior with the motivating examples, including the bounded-pass and infinite-loop cases; the work is done when the requested inference works without changing JavaScript output and handles the stated termination behavior.

Written by the indexing model from the issue text.