Feature request: Dependent contextual inference

首先审查依赖上下文推断提案以及 PR #64092 中现有的实现。将其行为与动机示例进行比较，包括有限遍历和无限循环的情况；当所请求的推断能够在不改变 JavaScript 输出的情况下工作，并处理所述的终止行为时，工作即告完成。

🔍 Search Terms

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

✅ 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

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<T> perform n checks each with contextual type T extends F<Tn-1> 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...

declare const f:
  <T extends { a: unknown, b: (a: T["a"]) => unknown }>
    (t: T) =>
      ReturnType<T["b"]>
    
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...

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()(...))...

declare const runMachine:
  <TMachine extends { state: string, context: object }>() =>
    <TDefinition extends {
      initial: TMachine,
      transitions: {
        [S in TMachine["state"]]:
          (parameter: { context: Extract<TMachine, { state: S }>["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...

declare const runMachine:
  <TState extends string, TContext extends object>
    (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...

declare const runMachine:
  <TDefinition extends {
    initial: {
      state: keyof TDefinition["transitions"],
      context: object
    },
    transitions: {
      [TState in keyof TDefinition["transitions"]]:
        (current: { context: Context<TDefinition, TState> }) =>
          | void
          | { state: keyof TDefinition["transitions"], context: object }
    }
  }>
    (definition: TDefinition) =>
      { [S in keyof TDefinition["transitions"]]: { state: S, context: Context<TDefinition, S> } }[keyof TDefinition["transitions"]]

// iterative over all transitions and collect the context for the given state
type Context<TDefinition extends Definition, TState> =
  | { [S in keyof TDefinition["transitions"]]:
        ReturnType<TDefinition["transitions"][S]> 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<keyof any, (...a: never) => 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<T> 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...

declare const update:
  <T>(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<T>...

declare const update:
  <T extends (previous: ReturnType<T>) => unknown>(f: T) => ReturnType<T>

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...

declare const update:
  <T extends (previous: ReturnType<T>) => unknown>(f: T) => ReturnType<T>

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...

declare const update:
  <T extends (previous: ReturnType<T>) => unknown>(f: T) => ReturnType<T>

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...

declare const create:
  <T extends
    ( set: Store<ReturnType<T>>["set"]
    , get: Store<ReturnType<T>>["get"]
    ) => unknown
  >
    (t: T) =>
      Store<ReturnType<T>>
  
interface Store<T>
  { get: () => T
  , set: (value: Partial<T>) => void
  }

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

Today store is inferred as Store<unknown> hence zustand requires it's users to explicitly type the generic with create<T>()(...), 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...

declare const useQuery:
  <K, T, U>
    (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<T> form and it'd work with dependent contextual types...

declare const useQueries:
  <T extends { [I in keyof T]: { key: unknown, fetch: (key: T[I]["key"]) => unknown, select: (data: ReturnType<T[I]["fetch"]>) => unknown } }>
    (queries: T) =>
      { [I in keyof T]: ReturnType<T[I]["select"]> }}

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. 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<T> types which are useful when typing any self referencing generics which occur in eDSLs example...

declare const createMachine:
  <T extends StateNode<T>>(definition: T) => "STUB"

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

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...

declare const createMachine:
  <T extends StateNode<T, T["context"]> & { context: object }>(definition: T) => "STUB"

type StateNode<T, C> = {
  initial?: keyof T["states" & keyof T],
  states?: {
    [K in keyof T["states" & keyof T]]: StateNode<T["states" & keyof T][K], C>
  },
  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. 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<T> 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