Generics and Type Inference in TypeScript

Conceptually, all you'd need to do is make on optional everywhere it's currently required, and use the NonNullable<T> utility type everywhere you are programmatically using the type of on, and things would just work:

type States<T extends Record<keyof T, { on?: any }>> = { [K in keyof T]: {
  on?: Record<keyof (NonNullable<T[K]['on']>), keyof T>,
  effect?(send: (action: keyof NonNullable<T[K]['on']>) => void): void;
} }

function createStateMachine<
  T extends States<T>>(states: {
    initial: keyof T,
    states: T
  }) {
  return function send(arg: KeysOfTransition<NonNullable<T[keyof T]['on']>>) {
  };
}

function stateNode<T extends Record<keyof T, PropertyKey>>({ on, effect }: {
  on?: T, effect?: (send: (action: keyof T) => void) => void
}) {
  return { ...on && { on }, ...effect && { effect } }
}

Unfortunately that doesn't quite work out:

const a = createStateMachine({
  initial: 'inactive',
  states: {
    inactive: stateNode({
      on: {
        ACTIVATE: 'active'
      }
    }),
    frozen: stateNode({ effect() { console.log("Entered Frozen") } }), // error!
//  ~~~~~~
// Type 'Record<string | number | symbol, string | number | symbol>' is not assignable to 
// type 'Record<string | number | symbol, "inactive" | "active" | "frozen">'.
    active: stateNode({
      on: {
        DEACTIVATE: 'inactive',
      },
      effect: send => {
        send('DEACTIVATE')
      },
    })
  },
});
// const a: (arg: string | number | symbol) => void

The compiler correctly infers T when you call stateNode with something that has an on property, but when you leave it out, the compiler infers Record<PropertyKey, PropertyKey>, and that's not what you want at all. Even if I could make that compile, PropertyKey would make the compiler forget all the names of your states, and you'd end up with something useless like (arg: PropertyKey) => void coming out of createStateMachine(). You'd like T to be undefined or {} or Record<never, any> or something. Well, I tried playing around with a single call signature for stateNode, but contextual typing kept causing T to be inferred with this unfortunately wide type.

Instead, I'd suggest making stateNode() an overloaded function so that we have more control over what happens when you leave out the on property:

function stateNode<T extends Record<keyof T, PropertyKey>>(param: {
  on: T;
  effect?: ((send: (action: keyof T) => void) => void) | undefined;
}): typeof param;
function stateNode(param: { effect?: () => void, on?: undefined }): typeof param;
function stateNode<T extends Record<keyof T, PropertyKey>>({ on, effect }: {
  on?: T, effect?: (send: (action: keyof T) => void) => void
}) {
  return { ...on && { on }, ...effect && { effect } }
}

If you specify on when you call stateNode(), the first call signature is used and the behavior is the same as before. If you leave on out, the second call signature is used. Here there is no T type to infer at all; instead, the compiler sees effect as an optional no-arg function (because, as you said in your comments, this is what you want). In both cases the output is the same type as the input. Let's see if this improves things:

const a = createStateMachine({
  initial: 'inactive',
  states: {
    inactive: stateNode({
      on: {
        ACTIVATE: 'active'
      }
    }),
    frozen: stateNode({ effect() { console.log("Entered Frozen") } }),
    active: stateNode({
      on: {
        DEACTIVATE: 'inactive',
      },
      effect: send => {
        send('DEACTIVATE')
      },
    })
  },
});
// const a: (arg: "ACTIVATE" | "DEACTIVATE") => void

Looks good!

Playground link to code