期待する挙動

  type X = { 
    x: { 
      a: 1
      b: 'hi'
    }
    y: 'hey'
  }

  type Expected = { 
    readonly x: { 
      readonly a: 1
      readonly b: 'hi'
    }
    readonly y: 'hey' 
  }

tl;dr（要約）

Homomorphic Mapped Typesは型引数にプリミティブを渡すとそのままプリミティブ型となるので、再帰処理のエスケープとして使うと以下のように記述を短くできます。

type Builtin = Function | Date | Error | RegExp;

type DeepReadonly<T> =  T extends Builtin 
 ? T
 : { readonly [key in keyof T]: DeepReadonly<T[key]>}

正攻法

順当にいくなら、プリミティブ型をあらかじめ定義しておき、プリミティブかそうでないかで再帰呼び出しを行う型を定義すればいけそうですね。

type Primitive = number | string | boolean | bigint | symbol | undefined | null;
type Builtin = Primitive | Function | Date | Error | RegExp;

type DeepReadonly<T> =   T extends Builtin
  ? T
  : { readonly [ key in keyof T]: DeepReadonly<T[key]>}

別解

しかし、別回答を覗いていると、こんな回答がありました。

type Builtin = Function | Date | Error | RegExp;

type DeepReadonly<T> =  T extends Builtin 
 ? T
 : { readonly [key in keyof T]: DeepReadonly<T[key]>}

もはやプリミティブの定義すらされていません。
私はここで頭を長い時間捻ることになりました。

Homomorphic Mapped Typesの特徴

実は、 Homomorphic Mapped Types¹はkeyof TのTの型引数にプリミティブが突っ込まれたらプリミティブが返ってくるという仕様になっているようです。
私はこれを知らず悩む羽目になりました。

type Mapped<T> = { [key in keyof T]: any}
type Foo = Mapped<string> // これはstring型になる
type Bar = Mapped<number> // これはnumber型になる

つまり、上記の例の

type DeepReadonly<T> = { readonly [key in keyof T]: DeepReadonly<T[key]>}

の部分は、プリミティブ型がTに渡されれば右辺はイコールそのプリミティブ型になり再帰処理が走らず、プリミティブ型以外がTに渡された場合は再帰処理を含む右辺が走るようになるというわけです。

ちなみにConditional Typeとして書かれていた条件分岐は、プリミティブではないがそのまま出力して欲しい型が別途定義されています。

感想

そんな使い方もあるのか〜と感心した反面、わかりやすさという面では微妙な気がするので、自身で使うことはないかなと思いました。
ですがまた出てきた際に理解できるようになったはずなので、良い勉強になりました。

{[key in keyof T]:K} といった形で表されるmapped typeのことを指す ↩