【TypeScript】再帰的な型（Recursive Types）の使い方｜JSON・ツリー構造にネストした型を付ける

interface LinkedList {
  value: number;
  next: LinkedList | null;   // ← 自分自身を参照している
}

const list: LinkedList = {
  value: 1,
  next: { value: 2, next: { value: 3, next: null } },
};

type A1 = A1[];                  // OK（配列の要素）
type A2 = { next: A2 };          // OK（オブジェクトのプロパティ）
type A3 = [string, A3];          // OK（タプルの要素）
type A4 = () => A4;              // OK（関数の戻り値）
type A7 = string | A7[];         // OK（配列に包まれていれば OK）

// error TS2456: Type alias 'A5' circularly references itself.
type A5 = A5 | string;

// error TS2456: Type alias 'A6' circularly references itself.
type A6 = A6 & { a: string };

type JsonPrimitive = string | number | boolean | null;

type JsonValue =
  | JsonPrimitive
  | JsonValue[]                      // 配列に包まれているので OK
  | { [key: string]: JsonValue };    // プロパティなので OK

const data: JsonValue = {
  name: 'webool',
  tags: ['typescript', 'react'],
  meta: { published: true, views: 1200, author: null },
};

// JSON の中に文字列がいくつ含まれているかを数える
function countStrings(value: JsonValue): number {
  if (typeof value === 'string') return 1;

  if (Array.isArray(value)) {
    // ここでは value: JsonValue[]
    let count = 0;
    for (const item of value) count += countStrings(item);
    return count;
  }

  if (value !== null && typeof value === 'object') {
    // ここでは value: { [key: string]: JsonValue }
    let count = 0;
    for (const item of Object.values(value)) count += countStrings(item);
    return count;
  }

  // 残るのは number | boolean | null
  return 0;
}

console.log(countStrings(data));   // 3（'webool' / 'typescript' / 'react'）

interface TreeNode {
  id: string;
  label: string;
  children?: TreeNode[];
}

const tree: TreeNode = {
  id: 'root',
  label: 'ルート',
  children: [
    { id: 'a', label: 'A', children: [{ id: 'a-1', label: 'A-1' }] },
    { id: 'b', label: 'B' },   // children を省略＝葉ノード
  ],
};

// id を指定してノードを探す
function findNode(node: TreeNode, id: string): TreeNode | undefined {
  if (node.id === id) return node;

  // children が undefined なら空配列として扱う
  for (const child of node.children ?? []) {
    const found = findNode(child, id);
    if (found) return found;
  }
  return undefined;
}

// ツリーを1次元の配列に平坦化する
function flatten(node: TreeNode): TreeNode[] {
  return [node, ...(node.children ?? []).flatMap(flatten)];
}

// もっとも深い階層の数を返す
function maxDepth(node: TreeNode): number {
  const children = node.children ?? [];
  if (children.length === 0) return 1;   // 葉ノードで止まる
  return 1 + Math.max(...children.map(maxDepth));
}

console.log(findNode(tree, 'a-1')?.label);   // 'A-1'
console.log(flatten(tree).length);           // 4
console.log(maxDepth(tree));                 // 3

interface GenericTree<T> {
  value: T;
  children: GenericTree<T>[];
}

const numbers: GenericTree<number> = {
  value: 1,
  children: [{ value: 2, children: [] }],
};

// 値だけを取り出す（型引数はそのまま引き継がれる）
function values<T>(node: GenericTree<T>): T[] {
  return [node.value, ...node.children.flatMap(values)];
}

console.log(values(numbers));   // [ 1, 2 ]

type MenuItem = {
  label: string;
  href?: string;
  children?: MenuItem[];
};

const menu: MenuItem[] = [
  { label: 'ホーム', href: '/' },
  {
    label: 'ブログ',
    children: [
      { label: 'TypeScript', href: '/blog/typescript' },
      {
        label: 'CSS',
        href: '/blog/css',
        children: [{ label: 'Grid', href: '/blog/css/grid' }],
      },
    ],
  },
];

// 入れ子の ul を組み立てる
function renderMenu(items: MenuItem[]): string {
  const li = items.map((item) => {
    const link = item.href
      ? `<a href="${item.href}">${item.label}</a>`
      : `<span>${item.label}</span>`;
    const child = item.children ? renderMenu(item.children) : '';
    return `<li>${link}${child}</li>`;
  });
  return `<ul>${li.join('')}</ul>`;
}

// href に一致する項目までの経路（パンくず）を返す
function findPath(
  items: MenuItem[],
  href: string,
  trail: MenuItem[] = [],
): MenuItem[] | undefined {
  for (const item of items) {
    const next = [...trail, item];
    if (item.href === href) return next;

    const found = item.children && findPath(item.children, href, next);
    if (found) return found;
  }
  return undefined;
}

const path = findPath(menu, '/blog/css/grid');
console.log(path?.map((item) => item.label).join(' > '));
// ブログ > CSS > Grid

type NaiveDeepPartial<T> = { [K in keyof T]?: NaiveDeepPartial<T[K]> };

type Settings = {
  plugins: { name: string }[];
  onSave: (value: string) => void;
};

type P = NaiveDeepPartial<Settings>;
declare const p: P;

// 配列は残るが、要素まで「あるかもしれない」ものになる
const first = p.plugins![0];
// error TS2322: Type 'NaiveDeepPartial<{ name: string; }> | undefined' is not
// assignable to type '{ name?: string | undefined; }'.
const n: { name?: string } = first;

// 関数は呼び出しシグネチャを失って呼べなくなる
// error TS2349: This expression is not callable.
//   Type 'NaiveDeepPartial<(value: string) => void>' has no call signatures.
p.onSave?.('x');

type Primitive = string | number | boolean | bigint | symbol | null | undefined;

type DeepPartial<T> =
  T extends Primitive ? T :                                   // 1. そのまま返す
  T extends (...args: any[]) => any ? T :                     // 2. 関数もそのまま
  T extends readonly (infer U)[] ? DeepPartial<U>[] :         // 3. 要素型だけ再帰
  T extends object ? { [K in keyof T]?: DeepPartial<T[K]> } : // 4. ここで ? を付ける
  T;

type Settings = {
  theme: { color: string; fontSize: number };
  plugins: { name: string; options: { enabled: boolean } }[];
  onSave: (value: string) => void;
};

// 何階層目でも自由に省略できる
const patch: DeepPartial<Settings> = {
  theme: { fontSize: 14 },        // color を省略できる
  plugins: [{ options: {} }],     // name も enabled も省略できる
};

type DeepReadonly<T> =
  T extends Primitive ? T :
  T extends (...args: any[]) => any ? T :
  T extends readonly (infer U)[] ? readonly DeepReadonly<U>[] :
  T extends object ? { readonly [K in keyof T]: DeepReadonly<T[K]> } :
  T;

const frozen: DeepReadonly<Settings> = {
  theme: { color: '#fff', fontSize: 14 },
  plugins: [{ name: 'a', options: { enabled: true } }],
  onSave: () => {},
};

// error TS2540: Cannot assign to 'color' because it is a read-only property.
frozen.theme.color = '#000';

// error TS2339: Property 'push' does not exist on type 'readonly { readonly name:
// string; readonly options: { readonly enabled: boolean; }; }[]'.
frozen.plugins.push({ name: 'b', options: { enabled: false } });

// error TS2456: Type alias 'Expr' circularly references itself.
type Expr = Expr | number;

// OK: 再帰がプロパティの中に入っている
type Expr2 =
  | { kind: 'num'; value: number }
  | { kind: 'add'; left: Expr2; right: Expr2 };

const e: Expr2 = {
  kind: 'add',
  left: { kind: 'num', value: 1 },
  right: { kind: 'num', value: 2 },
};

// 判別可能なユニオンなので、再帰関数も安全に書ける
function evaluate(expr: Expr2): number {
  switch (expr.kind) {
    case 'num':
      return expr.value;
    case 'add':
      return evaluate(expr.left) + evaluate(expr.right);
  }
}

console.log(evaluate(e));   // 3

// error TS2310: Type 'Loop' recursively references itself as a base type.
interface Loop extends Loop {
  a: string;
}

// これは問題ない（プロパティとしての自己参照）
interface Node2 {
  a: string;
  parent: Node2 | null;
}

// 長さ N のタプルを作る（再帰で1要素ずつ足していく）
type BuildTuple<N extends number, R extends unknown[] = []> =
  R['length'] extends N ? R : BuildTuple<N, [...R, unknown]>;

type T500 = BuildTuple<500>;    // OK

// error TS2589: Type instantiation is excessively deep and possibly infinite.
type T2000 = BuildTuple<2000>;

type Primitive = string | number | boolean | bigint | symbol | null | undefined;

// Prev[3] は 2、Prev[1] は 0、Prev[0] は never（＝打ち切り）
type Prev = [never, 0, 1, 2, 3, 4, 5];

type DeepPartial<T, D extends number = 5> =
  [D] extends [never] ? T :                                        // 深さ切れ
  T extends Primitive ? T :
  T extends (...args: any[]) => any ? T :
  T extends readonly (infer U)[] ? DeepPartial<U, Prev[D]>[] :
  T extends object ? { [K in keyof T]?: DeepPartial<T[K], Prev[D]> } :
  T;

type Node2 = { value: string; child: Node2 };

// 5階層までは省略可能、その先は元の型のまま
const patch: DeepPartial<Node2> = { value: 'a', child: { child: { child: {} } } };

type Split<S extends string, D extends string> =
  S extends `${infer Head}${D}${infer Tail}`
    ? [Head, ...Split<Tail, D>]   // 区切り文字が見つかったら残りを再帰
    : [S];                        // 見つからなければ終わり

// ['theme', 'color', 'primary']
type Parts = Split<'theme.color.primary', '.'>;

const parts: Parts = ['theme', 'color', 'primary'];

type Get<T, P extends string> =
  P extends `${infer Key}.${infer Rest}`
    ? Key extends keyof T ? Get<T[Key], Rest> : never   // 途中を掘り進む
    : P extends keyof T ? T[P] : never;                 // 最後のキー

type Config = {
  theme: { color: { primary: string; secondary: string }; fontSize: number };
  debug: boolean;
};

type C1 = Get<Config, 'theme.color.primary'>;   // string
type C2 = Get<Config, 'theme.fontSize'>;        // number
type C3 = Get<Config, 'debug'>;                 // boolean
type C4 = Get<Config, 'theme.nope'>;            // never（存在しないパス）