TS Type Challenges · Part 10 — Parsers & State Machines

type KebabCase<S extends string> = S extends `${infer C}${infer Tail}`
  ? Tail extends Uncapitalize<Tail>
    ? `${Uncapitalize<C>}${KebabCase<Tail>}`
    : `${Uncapitalize<C>}-${KebabCase<Tail>}`
  : S;

Cơ chế

Bốn ý ghép thành một máy trạng thái nhỏ:

1. Tiến con trỏ — `${infer C}${infer Tail}` bóc một ký tự ở đầu; C tham lam (một ký tự), Tail là phần còn lại.
2. Lookahead — Tail extends Uncapitalize<Tail> hỏi “ký tự kế có bắt đầu từ mới không?” mà không tiêu thụ nó.
3. Phát — luôn xuất Uncapitalize<C>; có điều kiện nối - trước khi đệ quy.
4. Base case — chuỗi rỗng (không còn C để bóc) trả S nguyên (tức '').

Trạng thái ngầm là “tôi có đang ở ranh giới từ không?” — trả lời bằng cách nhìn chữ hoa/thường của ký tự đầu Tail.

Từng dòng

type KebabCase<S extends string> = S extends `${infer C}${infer Tail}`
// If S has at least one character, bind C = first char, Tail = rest.
// If S is '', this branch fails → fall through to : S (base case).

  ? Tail extends Uncapitalize<Tail>
  // LOOKAHEAD: Uncapitalize<Tail> lowercases only the FIRST char of Tail.
  // If Tail already starts lowercase, Uncapitalize<Tail> === Tail → true branch.
  // If Tail starts uppercase, they differ → false branch → insert '-'.

    ? `${Uncapitalize<C>}${KebabCase<Tail>}`
    // No boundary after C: emit lowercased C, recurse on Tail (cursor moves 1).

    : `${Uncapitalize<C>}-${KebabCase<Tail>}`
    // Boundary after C: emit lowercased C + '-', recurse on Tail.

  : S;
// Base case: S is empty string → done.

Đánh giá type từng bước

Theo dõi KebabCase<'doNothing'> — chỗ khó nhất là chữ N trong Nothing:

// step 0: S = 'doNothing', cursor at start, output accumulator = ''

// step 1: peel C='d', Tail='oNothing'
//   Tail extends Uncapitalize<Tail>?
//   Uncapitalize<'oNothing'> = 'oNothing' → YES (next char is lowercase)
//   emit 'd', no dash → partial output 'd', recurse on 'oNothing'

// step 2: peel C='o', Tail='Nothing'
//   Uncapitalize<'Nothing'> = 'nothing' ≠ 'Nothing' → NO (next char is uppercase 'N')
//   emit 'o' + '-' → partial output 'do-', recurse on 'Nothing'

// step 3: peel C='N', Tail='othing'
//   Uncapitalize<'othing'> = 'othing' → YES
//   emit 'n', no dash → partial output 'do-n', recurse on 'othing'

// step 4: peel C='o', Tail='thing'
//   YES → emit 'o' → 'do-no', recurse on 'thing'

// step 5: peel C='t', Tail='hing'
//   YES → emit 't' → 'do-not', recurse on 'hing'

// step 6: peel C='h', Tail='ing'
//   YES → emit 'h' → 'do-noth', recurse on 'ing'

// step 7: peel C='i', Tail='ng'
//   YES → emit 'i' → 'do-nothi', recurse on 'ng'

// step 8: peel C='n', Tail='g'
//   YES → emit 'n' → 'do-nothin', recurse on 'g'

// step 9: peel C='g', Tail=''
//   Tail='' extends Uncapitalize<''>? → '' extends '' → YES
//   emit 'g' → 'do-nothing', recurse on ''

// step 10: S='' → base case → ''

type Result = KebabCase<'doNothing'>; // 'do-nothing'

Trace ngắn cho KebabCase<'FooBar'>:

// step 1: C='F', Tail='ooBar' → Tail starts lowercase 'o' → emit 'f' (no dash)
// step 2: C='o', Tail='oBar'   → Tail starts lowercase 'o' → emit 'o'
// step 3: C='o', Tail='Bar'    → Tail starts uppercase 'B' → emit 'o-'
// step 4: C='B', Tail='ar'     → Tail starts lowercase    → emit 'b'
// step 5: C='a', Tail='r'      → emit 'a'
// step 6: C='r', Tail=''       → emit 'r'
// step 7: '' → done

type Result = KebabCase<'FooBar'>; // 'foo-bar'

Cạm bẫy

• Uncapitalize chỉ đụng ký tự đầu — đúng ý lookahead trên Tail, nhưng đừng dùng nó để hạ chữ cả phần còn lại.
• Chữ hoa liên tiếp (XMLHttpRequest, IO) — thuật toán này chèn gạch trước mọi chữ hoa sau chữ thường; không tách XML thành x-m-l. Cần ngữ pháp phức tạp hơn.
• Độ sâu đệ quy — một lần gọi đệ quy mỗi ký tự; string literal type rất dài có thể chạm giới hạn độ sâu compiler.
• Chuỗi rỗng — KebabCase<''> → ''; nhánh `${infer C}${infer Tail}` không khớp, rơi vào base case gọn.

Tóm lại: bóc một ký tự, nhìn chữ hoa/thường ký tự kế để quyết định -, hạ chữ ký tự hiện tại, đệ quy — parser lookahead một ký tự.

type TupleToNestedObject<T extends readonly PropertyKey[], U> = T extends [
  infer Head extends PropertyKey,
  ...infer Tail,
]
  ? { [K in Head]: TupleToNestedObject<Tail extends PropertyKey[] ? Tail : [], U> }
  : U;

Cơ chế

Đây là fold lồng phải với accumulator bắt đầu là giá trị lá U và được bọc ra ngoài mỗi bước:

1. Dequeue — mẫu tuple [infer Head, ...infer Tail] bóc key đầu ở phía trước (như shift() trên mảng).
2. Đệ quy — tính cấu trúc trong từ các key còn lại.
3. Bọc — { [K in Head]: inner } thêm một tầng lồng quanh kết quả đệ quy.
4. Base case — tuple rỗng [] không khớp mẫu [Head, ...Tail] → trả U.

Trạng thái ở đây là đường key còn lại (Tail) và độ lồng tích luỹ dựng khi đệ quy trở về.

Từng dòng

type TupleToNestedObject<T extends readonly PropertyKey[], U> = T extends [
  infer Head extends PropertyKey,
  // Head must be a valid object key (string | number | symbol).
  ...infer Tail,
  // Tail is "whatever is left" — might not be a tuple yet; we guard below.
]
  ? { [K in Head]: TupleToNestedObject<Tail extends PropertyKey[] ? Tail : [], U> }
  // Mapped type with exactly ONE key (Head). Value is the recursive call on Tail.
  // Tail extends PropertyKey[] ? Tail : [] — if Tail isn't a key tuple, treat as [].

  : U;
// T is [] (or not a non-empty tuple) → we've consumed all keys → return leaf U.

Đánh giá type từng bước

Theo dõi TupleToNestedObject<['a', 'b', 'c'], number>:

// step 0: T = ['a', 'b', 'c'], U = number
//   keys remaining: ['a', 'b', 'c'], accumulator not built yet

// step 1: match [Head, ...Tail] → Head='a', Tail=['b', 'c']
//   must compute inner = TupleToNestedObject<['b', 'c'], number>
//   state: wrap 'a' around whatever inner becomes

// step 2: T = ['b', 'c']
//   Head='b', Tail=['c']
//   must compute inner = TupleToNestedObject<['c'], number>

// step 3: T = ['c']
//   Head='c', Tail=[]
//   must compute inner = TupleToNestedObject<[], number>

// step 4: T = [] → base case → inner = number
//   (leaf reached; accumulator = number)

// step 5: unwind step 3 → { c: number }

// step 6: unwind step 2 → { b: { c: number } }

// step 7: unwind step 1 → { a: { b: { c: number } } }

type Result = TupleToNestedObject<['a', 'b', 'c'], number>;
// { a: { b: { c: number } } }

Base case tuple rỗng:

// step 0: T = [], U = boolean
// step 1: [] extends [infer Head, ...infer Tail]? → NO
// step 2: base case → boolean

type Result = TupleToNestedObject<[], boolean>; // boolean

Cạm bẫy

• PropertyKey, không chỉ string — key có thể là number hoặc symbol; ràng buộc Head extends PropertyKey giữ mapped type hợp lệ.
• Tail extends PropertyKey[] ? Tail : [] — sau ...infer Tail, TypeScript suy luận Tail lỏng; guard ngăn rest type lỗi làm hỏng đệ quy.
• Thứ tự key quan trọng — ['a', 'b'] và ['b', 'a'] cho hình dạng khác; fold này không giao hoán.
• Độ sâu = độ dài tuple — tuple 20 phần tử nghĩa là 20 tầng lồng; cùng giới hạn độ sâu đệ quy như parser chuỗi.

Tóm lại: lấy key đầu, đệ quy dựng object trong, bọc một lớp — fold làm lồng sâu dần khi tuple co lại.

type ControlsMap = {
  c: string;
  s: string;
  d: number;
  o: number;
  x: number;
  X: number;
  f: number;
  e: number;
  g: number;
  a: number;
  A: number;
  p: string;
};

type ParsePrintFormat<S extends string> =
  S extends `${string}%${infer Rest}`
    ? Rest extends `${infer Control}${infer Tail}`
      ? Control extends keyof ControlsMap
        ? [ControlsMap[Control], ...ParsePrintFormat<Tail>]
        : ParsePrintFormat<Rest>
      : []
    : [];

Cơ chế

Đệ quy là vòng lặp; Rest / Tail là con trỏ.

Từng dòng

type ParsePrintFormat<S extends string> =
  S extends `${string}%${infer Rest}`
  // SCAN state: `${string}%` greedily skips any literal prefix up to the first '%'.
  // Rest = everything AFTER that '%' (the '%' itself is consumed).

    ? Rest extends `${infer Control}${infer Tail}`
    // CONSUME state: peel one char as Control, rest as Tail.
    // If Rest is '' (format ends with bare '%'), this fails → return [].

      ? Control extends keyof ControlsMap
      // ACT state — known specifier?

        ? [ControlsMap[Control], ...ParsePrintFormat<Tail>]
        // Emit mapped type, prepend to tuple, advance cursor to Tail.

        : ParsePrintFormat<Rest>
        // Unknown Control (e.g. '%q'): do NOT recurse on Tail alone.
        // Re-enter SCAN from Rest so the next '%' is found uniformly.

      : []
    // Rest is empty after '%' → malformed trailing '%' → no args

    : [];
// No '%' in S → scanning done → empty arg list

Đánh giá type từng bước

Theo dõi ParsePrintFormat<'%s is %d years old.'>:

// step 0: S = '%s is %d years old.', output tuple = (building), cursor at start

// ── first placeholder ──
// step 1 (SCAN): '%s is %d years old.' matches `${string}%${infer Rest}`
//   literal prefix = '' (empty), Rest = 's is %d years old.'
// step 2 (CONSUME): Rest → Control='s', Tail=' is %d years old.'
// step 3 (ACT): 's' extends keyof ControlsMap? → YES → ControlsMap['s'] = string
//   emit string, recurse on Tail=' is %d years old.'
//   partial tuple: [string]

// ── second placeholder ──
// step 4 (SCAN): ' is %d years old.' → skip ' is ', Rest = 'd years old.'
// step 5 (CONSUME): Control='d', Tail=' years old.'
// step 6 (ACT): 'd' known → ControlsMap['d'] = number
//   emit number, recurse on Tail=' years old.'
//   partial tuple: [string, number]

// ── no more placeholders ──
// step 7 (SCAN): ' years old.' has no '%' → branch fails → []
// step 8: unwind → [string, number] ++ [] = [string, number]

type Result = ParsePrintFormat<'%s is %d years old.'>; // [string, number]

Trace phục hồi specifier không biết: ParsePrintFormat<'%q%d'>:

// step 1 (SCAN): Rest = 'q%d'
// step 2 (CONSUME): Control='q', Tail='%d'
// step 3 (ACT): 'q' NOT in ControlsMap → ParsePrintFormat<Rest>
//   i.e. ParsePrintFormat<'q%d'>  (NOT ParsePrintFormat<'%d'> via Tail!)
// step 4 (SCAN): 'q%d' → skip 'q', Rest = 'd'  (wait — no second '%' yet!)
//   Actually: 'q%d' matches `${string}%${infer Rest}` with prefix 'q', Rest='d'
// step 5 (CONSUME): Control='d', Tail=''
// step 6 (ACT): 'd' known → [number]
// step 7: SCAN on '' → []

type Result = ParsePrintFormat<'%q%d'>; // [number]  — '%q' skipped, '%d' found

Cạm bẫy

• Vì sao Rest ở nhánh unknown, không phải Tail? — Cả hai đều dừng, nhưng Rest vào lại trạng thái quét (“tìm % kế”), giữ một đường code. Tail đã bỏ ký tự lạ và vẫn chạy ở đây, nhưng lệch tinh thần “luôn quét trước”.
• % đơn ở cuối — '%' → Rest='' → consume thất bại → [], không phải error type.
• % trong text literal — mẫu quét chỉ kích hoạt trên %; % literal trong output ổn, nhưng %% (percent thoát) không được ngữ pháp này xử lý.
• Thứ tự tuple = thứ tự quét trái sang phải — ghép đầu [ControlsMap[Control], ...] giữ thứ tự placeholder xuất hiện trong chuỗi.
• Độ sâu đệ quy — hai lần gọi đệ quy mỗi placeholder (quét + tiếp tục); chuỗi format dài cộng dồn.

Tóm lại: quét %, tiêu thụ một ký tự điều khiển, ánh xạ qua ControlsMap hoặc bỏ qua — parser ba trạng thái mà vòng lặp là đệ quy và con trỏ là Rest/Tail.

type Split<
  S extends string,
  Sep extends string,
> = S extends `${infer Head}${Sep}${infer Tail}`
  ? [Head, ...Split<Tail, Sep>]
  : [S];

Đánh giá type từng bước

Theo dõi Split<'a.b.c', '.'>:

// step 0: S = 'a.b.c', Sep = '.', segments = (building)

// step 1: match Head='a', Sep='.', Tail='b.c'
//   emit 'a', recurse on 'b.c' → partial ['a', ...]

// step 2: Head='b', Tail='c'
//   emit 'b', recurse on 'c' → partial ['a', 'b', ...]

// step 3: 'c' has no '.' → base case → ['c']
//   unwind: ['a', 'b', 'c']

type Result = Split<'a.b.c', '.'>; // ['a', 'b', 'c']

Cạm bẫy

• Chỉ separator đầu mỗi lần gọi — `${infer Head}${Sep}${infer Tail}` tách ở Sep sớm nhất (xem Phần 7 về infer tham lam/không tham lam).
• Hết separator — cả chuỗi thành đoạn cuối một phần tử [S].
• Đoạn rỗng — Split<'a..b', '.'> → ['a', '', 'b']; ngữ pháp cho phép Head độ dài 0.

Tóm lại: tách ở separator đầu, phát Head, đệ quy Tail; khi hết separator, trả [S].

Không cái nào lặp vô tận — cả Rest và Tail đều ngắn hơn chuỗi gốc, nên đệ quy luôn dừng. Khác biệt là trạng thái parser nào bạn vào lại:

// Unknown '%q' in '%q%d':
// Rest = 'q%d'   Tail = '%d'

// Recurse on Rest → ParsePrintFormat<'q%d'>
//   SCAN skips 'q', finds '%', parses '%d' → [number] ✓

// Recurse on Tail → ParsePrintFormat<'%d'>
//   SCAN finds '%' immediately, parses '%d' → [number] ✓
//   (same result for THIS input)

Với '%q' đơn (không có % sau), đệ quy trên Tail khi Tail='' trả [] ngay — bạn không bao giờ “thử lại” q lạ từ trạng thái quét, nhưng cũng không còn gì để tìm. Dùng Rest giữ mọi nhánh tiếp tục đồng nhất: luôn quét lại % kế thay vì đôi khi nhảy thẳng sang consume. Tính đồng nhất quan trọng khi mở rộng ngữ pháp (width, precision, %%) — một điểm vào cho “tiếp tục parse”.

Tóm lại: Tail thường vẫn chạy với input đơn giản, nhưng Rest giữ hình dạng máy trạng thái quét-trước.