Recursive conditional types

A recursive conditional type is a conditional type whose alias refers to itself, letting you compute over a nested type by peeling one layer and recursing on the rest. CruftScript admits it only when every self-reference re-enters on a structurally smaller infer-captured operand, so it can prove the loop stops before accepting the definition.

A recursive conditional type is a conditional type whose alias refers to itself. It lets you compute over a nested type by peeling one layer and recursing on the rest.

type Flatten<T> = T extends Array<infer E> ? Flatten<E> : T
type A = Flatten<Array<Array<number>>>   // number

This is type-level computation that loops: each self-reference is another turn of the loop, running at compile time. CruftScript admits such an alias only when it can prove the loop stops. TypeScript allows recursion too, but it relies on an incidental depth limiter to eventually give up. CruftScript instead requires a real termination proof before it accepts the definition.

The decrease rule

An alias is admitted only when every self-reference re-enters on an infer-captured operand that is structurally smaller than the type it started with. The checker runs this decrease proof once, when it reads the alias definition. If any self-reference does not shrink, the alias is rejected.

type Flatten<T> = T extends Array<infer E> ? Flatten<E> : T   // admitted: E is captured from inside T, so it is smaller
type Bad<T> = T extends number ? Bad<T> : T                   // error: Bad<T> re-passes T unchanged, no decrease

Flatten shrinks because E is captured from inside T with infer, so each turn operates on something strictly contained in the last. Bad recurses on the same T it received, so the loop could run forever, and the definition is refused.

Two things that always fail

Because an infer name is only in scope in the true branch, two recursive shapes are always rejected:

  • A recursive call in the false branch. The false branch has no captured operand in scope, so it cannot pass anything smaller, and a self-reference there is rejected.
  • Re-passing the original parameter. Handing the recursion the same parameter you received is not a decrease, so it is rejected even in the true branch.
type Wrong<T> = T extends Array<infer E> ? T : Wrong<T>   // error: recursion in the false branch, nothing captured

The depth backstop

The decrease proof is the real guarantee. Behind it sits a depth backstop of 100 turns. Reaching it is a hard error, not a silent truncation: the checker stops the build and tells you, rather than quietly returning a partial result as if the computation had finished. In practice a proven-terminating alias never approaches 100; the backstop exists to catch anything the proof did not.

Why it works this way

Recursion that might not stop is a compiler that might not stop, so CruftScript makes termination a property it proves rather than a limit it happens to hit. The decrease rule is a plain, checkable condition: shrink on every self-reference. That gives you a definite answer at definition time instead of a computation that runs until some depth counter runs out. The backstop stays as a hard failure so that even an unforeseen case surfaces as an error you can see, never as a truncated type you cannot.

Limitations

  • Decrease detection is deliberately narrow. It recognizes only a bare captured name as the smaller operand. Some aliases that do terminate, but express their decreasing argument in a form other than a bare infer capture, are rejected conservatively. The rule prefers a false rejection to an unproven acceptance.
  • No recursion in the false branch, and no re-passing the parameter. Both lack a captured smaller operand, so both are always rejected.
  • The depth backstop is a hard error. Hitting 100 turns stops the build; it does not return a truncated result.