loc. logo

Recursive Types

Recursive Types

Bạn cần định nghĩa kiểu cho một cấu trúc dữ liệu cây -- JSON, DOM node, folder/file system, comment có reply lồng nhau. Không có cách nào diễn đạt "kiểu này chứa chính nó" bằng interface phẳng. Bạn cần recursive type.

Nhưng recursion trong type system có giới hạn. Đi quá sâu, compiler sẽ báo lỗi. Bài học này sẽ cho bạn biết khi nào dùng recursive type, cách viết chúng, và khi nào nên dừng.

#Type Alias Đệ Quy -- Cơ bản

Một type alias có thể tham chiếu đến chính nó:

// ❌ Không có recursion: phải lặp thủ công, không cover mọi trường hợp
interface Comment {
  text: string;
  replies: Array<{
    text: string;
    replies: Array<{
      text: string;
      replies: Array<{ text: string; replies: never[] }>;
    }>;
  }>;
}
// Chỉ 3 tầng. Reply tầng 4 trở đi? Không có cách nào biểu đạt.
 
// ✅ Recursive type: không giới hạn độ sâu
type NestedComment = {
  text: string;
  replies: NestedComment[];
};
 
// Hoạt động ở bất kỳ độ sâu
const thread: NestedComment = {
  text: "Top level",
  replies: [
    {
      text: "Reply 1",
      replies: [
        {
          text: "Nested reply",
          replies: [
            { text: "Very deep", replies: [] },
          ],
        },
      ],
    },
  ],
};

Compiler sẽ tự "unroll" recursive type khi cần kiểm tra assignment. Bạn không cần khai báo bao nhiêu tầng.

#JSON Type -- Recursive Type Kinh điển

Đây là ví dụ phổ biến nhất của recursive type: định nghĩa kiểu cho bất kỳ giá trị JSON hợp lệ.

// ❌ Không dùng recursion: phải liệt kê thủ công, bỏ sót nested objects
type BadJson =
  | string
  | number
  | boolean
  | null
  | BadJson[]    // Mảng lồng -- đã đệ quy!
  | { [key: string]: BadJson };  // Object lồng -- cũng đệ quy!
 
// Nhưng viết như trên có vấn đề: TypeScript không cho type alias
// tự tham chiếu trực tiếp. Cần dùng interface:
 
// ✅ Đúng cách: kết hợp type alias + interface
type Json =
  | string
  | number
  | boolean
  | null
  | Json[]
  | JsonObject;
 
interface JsonObject {
  [key: string]: Json;
}
 
// Sử dụng
const data: Json = {
  name: "Alice",
  age: 30,
  active: true,
  address: {
    city: "Hanoi",
    coordinates: [21.0285, 105.8542],
  },
  tags: ["dev", "ts"],
  metadata: null,
};

Tại sao cần kết hợp type + interface?

TypeScript giới hạn: type alias không thể tự tham chiếu trực tiếp trong một số trường hợp. Dùng interface JsonObject phá vỡ vòng đệ quy thành hai phần, mỗi phần hợp lệ.

// ❌ Cách viết lỗi -- infinite recursion trực tiếp
type Json =
  | string
  | number
  | boolean
  | null
  | Json[]
  | { [key: string]: Json };
// Một số phiên bản TS sẽ chấp nhận, nhưng có thể gây ra
// "Type instantiation is excessively deep" ở nơi sử dụng
 
// ✅ Cách an toàn: dùng interface để "tách" vòng đệ quy
type JsonValue =
  | string
  | number
  | boolean
  | null
  | JsonValue[]
  | JsonObject;
 
interface JsonObject {
  [key: string]: JsonValue;
}

#DeepReadonly -- Utility Type Đệ Quy

TypeScript có sẵn Readonly<T> nhưng nó chỉ shallow -- chỉ readonly tầng đầu tiên:

// ❌ Shallow Readonly: nested objects vẫn mutable
interface Config {
  database: {
    host: string;
    port: number;
    credentials: {
      user: string;
      password: string;
    };
  };
}
 
type ReadonlyConfig = Readonly<Config>;
 
const config: ReadonlyConfig = {
  database: {
    host: "localhost",
    port: 5432,
    credentials: { user: "admin", password: "secret" },
  },
};
 
config.database = { host: "other", port: 3306, credentials: { user: "x", password: "y" } };
// ❌ Readonly chặn được -- "Cannot assign to 'database'"
 
config.database.host = "other";
// ✅ Không lỗi! Vì Readonly chỉ sâu 1 tầng, database.host vẫn mutable

Giải pháp: DeepReadonly đệ quy:

// ✅ DeepReadonly đệ quy -- mọi tầng đều readonly
type DeepReadonly<T> = T extends (infer U)[]
  ? ReadonlyArray<DeepReadonly<U>>
  : T extends object
    ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
    : T;
 
type ReadonlyConfig = DeepReadonly<Config>;
 
const config: ReadonlyConfig = {
  database: {
    host: "localhost",
    port: 5432,
    credentials: { user: "admin", password: "secret" },
  },
};
 
config.database = { /* ... */ }; // ❌ Cannot assign
config.database.host = "other"; // ❌ Cannot assign
config.database.credentials.password = "new"; // ❌ Cannot assign
// Mọi tầng đều được bảo vệ

Giải thích từng phần:

  1. T extends (infer U)[] -- kiểm tra T có phải mảng không. Nếu có, chuyển mỗi phần tử U thành DeepReadonly<U>, bọc trong ReadonlyArray.
  2. T extends object -- nếu là object, biến mọi property thành readonly, và đệ quy vào giá trị property.
  3. Nếu không phải mảng hay object (tức là primitive), trả về T nguyên bản.

#DeepPartial -- Recursive Partial Tương tự

Cùng pattern, nhưng thay vì readonly thì biến mọi property thành optional:

type DeepPartial<T> = T extends (infer U)[]
  ? DeepPartial<U>[]
  : T extends object
    ? { [K in keyof T]?: DeepPartial<T[K]> }
    : T;
 
// Hữu ích khi update nested config
function updateConfig(current: Config, patch: DeepPartial<Config>): Config {
  // Merge sâu -- chỉ ghi đè những field được cung cấp
  return deepMerge(current, patch);
}
 
// Có thể update bất kỳ tầng nào
updateConfig(currentConfig, {
  database: {
    credentials: {
      password: "new-secret",
      // host, port, user -- không cần, giữ nguyên
    },
  },
});

#Giới Hạn Recursion Depth

TypeScript có giới hạn cho recursive type. Khi recursion quá sâu, compiler sẽ báo lỗi:

// ❌ Quá sâu -- compiler sẽ dừng lại
type TooDeep<T> = T extends object
  ? { [K in keyof T]: TooDeep<T[K]> }
  : T;
 
// Dùng với cấu trúc 50+ tầng lồng nhau
// -> Error: "Type instantiation is excessively deep and possibly infinite"
 
// TypeScript giới hạn ở khoảng 50 lần "unroll" đệ quy
// Đây là hard limit, không thể cấu hình

Cách xử lý khi gặp giới hạn:

// Giải pháp 1: Giới hạn độ sâu bằng counter type
type DeepReadonlyLimited<T, Depth extends number[] = []> =
  Depth["length"] extends 5  // Giới hạn 5 tầng
    ? T
    : T extends (infer U)[]
      ? ReadonlyArray<DeepReadonlyLimited<U, [...Depth, 0]>>
      : T extends object
        ? { readonly [K in keyof T]: DeepReadonlyLimited<T[K], [...Depth, 0]> }
        : T;
 
// Giải pháp 2: Dùng tail-call optimization (TypeScript 4.5+)
// TypeScript tối ưu một số đệ quy "tail-recursive" để không stack overflow

#Tail-Call Optimization cho Types

Từ TypeScript 4.5, compiler tối ưu một số đệ quy kiểu tail-call -- đệ quy mà kết quả cuối cùng chính là kết quả của lời gọi đệ quy, không cần thêm phép tính nào:

// ❌ Không tail-recursive: phải map kết quả sau khi đệ quy
type DeepReadonly<T> = T extends (infer U)[]
  ? ReadonlyArray<DeepReadonly<U>>  // Phải wrap lại -> không tail-call
  : T extends object
    ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
    : T;
 
// ✅ Tail-recursive: dùng tuple để "tích lũy" kết quả
type BuildTuple<N extends number, T extends any[] = []> =
  T["length"] extends N
    ? T
    : BuildTuple<N, [...T, any]>;
 
// Ví dụ: tạo tuple dài N
type Five = BuildTuple<5>["length"]; // 5
type Ten = BuildTuple<10>["length"]; // 10
 
// Tail-recursive với accumulator pattern
type FlattenTuple<T extends any[], Acc extends any[] = []> =
  T extends [infer First, ...infer Rest]
    ? First extends any[]
      ? FlattenTuple<Rest, [...Acc, ...First]>  // Tail call: đệ quy là bước cuối
      : FlattenTuple<Rest, [...Acc, First]>
    : Acc;
 
type Result = FlattenTuple<[[1, 2], [3], [4, 5]]>; // [1, 2, 3, 4, 5]

Quy tắc: Để TypeScript tối ưu tail-call, đệ quy phải ở vị trí "tail" -- tức là kết quả của hàm chính là kết quả của lời gọi đệ quy, không bọc thêm wrapper nào.

#Recursive Type cho Tree Structures

Cây là ứng dụng tự nhiên nhất của recursive type:

// File system
type FileSystemNode = {
  name: string;
} & (
  | { kind: "file"; size: number; content: string }
  | { kind: "directory"; children: FileSystemNode[] }
);
 
const project: FileSystemNode = {
  name: "my-project",
  kind: "directory",
  children: [
    {
      name: "src",
      kind: "directory",
      children: [
        { name: "index.ts", kind: "file", size: 1024, content: "..." },
        { name: "utils.ts", kind: "file", size: 512, content: "..." },
      ],
    },
    { name: "package.json", kind: "file", size: 256, content: "..." },
  ],
};
 
// Recursive function để traverse
function getTotalSize(node: FileSystemNode): number {
  if (node.kind === "file") {
    return node.size;
  }
  return node.children.reduce((sum, child) => sum + getTotalSize(child), 0);
}
// Comment tree với generic depth limit
type Comment<TDepth extends number = 10> =
  TDepth extends 0
    ? { text: string; replies: [] }
    : {
        text: string;
        author: string;
        replies: Comment<Subtract<TDepth, 1>>[];
      };
 
// Utility: Subtract cho type-level arithmetic (giới hạn trong tuple length)
type Subtract<A extends number, B extends number> =
  BuildTuple<A> extends [...BuildTuple<B>, ...infer Rest]
    ? Rest["length"]
    : never;

#Anti-pattern: Infinite Recursion trong Types

Sai lầm phổ biến nhất là tạo type đệ quy vô hạn:

// ❌ INFINITE RECURSION -- compiler sẽ báo lỗi hoặc treo
type Bad<T> = {
  value: T;
  next: Bad<T>;  // Không có base case -> đệ quy vô hạn
};
 
// ❌ Circular reference
type A = { b: B };
type B = { a: A }; // Vòng lặp vô hạn
 
// ✅ Sửa: thêm base case rõ ràng
type LinkedList<T> =
  | { value: T; next: LinkedList<T> }
  | null;  // Base case: null kết thúc chuỗi
 
const list: LinkedList<number> = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: null,  // Base case
    },
  },
};
 
// ✅ Sửa circular reference: dùng interface (lazy evaluation)
interface NodeA {
  b: NodeB;
}
interface NodeB {
  a: NodeA;
}
// Interface được resolve "lazy" -- TypeScript không cố gắng expand ngay lập tức

Quy tắc: Mọi recursive type PHẢI có base case. Nếu không, compiler sẽ:

  • Báo "Type instantiation is excessively deep" (tốt -- bạn biết để sửa)
  • Hoặc treo/hết memory (xấu -- phải restart IDE)

Khi nào nên dừng recursion:

  • Khi bạn thấy lỗi "excessively deep"
  • Khi IDE trở nên chậm bất thường khi hover type
  • Khi type quá phức tạp, không ai đọc được -- dùng // @ts-ignore hoặc simplify

#Tổng kết

  • Recursive type cho phép type tham chiếu đến chính nó -- cần thiết cho JSON, cây, đồ thị, và mọi cấu trúc dữ liệu có độ sâu không xác định.
  • JSON type là ví dụ kinh điển: kết hợp type alias (cho union) và interface (cho object) để phá vòng đệ quy.
  • DeepReadonly / DeepPartial dùng conditional type đệ quy để apply readonly/optional tới mọi tầng. TypeScript sẵn có Readonly<T> chỉ là shallow.
  • Giới hạn depth: Compiler giới hạn khoảng 50 lần unroll đệ quy. Dùng accumulator pattern hoặc tail-call optimization để tận dụng tối đa.
  • Tail-call optimization (TS 4.5+): đệ quy ở vị trí tail được tối ưu, cho phép depth lớn hơn. Quy tắc: kết quả hàm = kết quả đệ quy, không wrap thêm.
  • Anti-pattern: Infinite recursion -- mọi recursive type phải có base case. Dùng interface cho lazy evaluation khi có circular reference.
  • Khi nào nên dừng: Nếu type quá sâu hoặc quá khó đọc, cân nhắc simplify. Type phức tạp không ai hiểu thì worse hơn type đơn giản thiếu một edge case.

Bài tiếp theo chúng ta sẽ khám phá Template Literal Types -- cách dùng string literal type kết hợp recursion để parse và biến đổi chuỗi ở type level.