Pattern 10/22 · Structural
Composite Cây thành phần
Cho lá và nhánh cùng chia sẻ một interface, trong đó mỗi phép toán được định nghĩa đệ quy: lá trả lời trực tiếp, nhánh trả lời bằng cách hỏi con. Code gọi vì thế xử lý một phần tử và cả một cây bằng đúng một đoạn code.
01 — Mở đầu bằng code đang hỏng
Vấn đề
Bạn làm giỏ hàng. Ban đầu chỉ có Product { name, price } và Cart { items }, tính tổng là một vòng lặp. Rồi marketing bán combo: "Gói du lịch = vé máy bay + khách sạn + bảo hiểm", giá bằng tổng cộng lại, và combo có thể chứa combo. Bạn thêm Bundle { items }.
Vòng lặp tính tổng lập tức vỡ: sum += item.price không còn đúng với Bundle, vì bundle không có price. Bạn viết if (item instanceof Bundle) sum += totalOf(item.items) else sum += item.price. Thế là xong — cho tới khi totalOf() cũng gặp bundle lồng nhau và bạn thêm đệ quy vào đó. Rồi tới renderLine(), rồi discountFor(), rồi validateStock(). Mỗi hàm đều phải nhớ cái cây này lồng nhau, và một hàm quên là giá trị sai.
Chỗ nào có cây, chỗ đó có cùng cơn đau. Menu và submenu trong app ẩm thực; comment có reply, reply của reply; file system; breadcrumb; AST mà ESLint đi qua; cây component của Vue. Pattern lặp lại: một hàm traverse(node) với if (node.children) thò ra ở đầu, và vài nhánh instanceof phía sau. Mỗi if (node.children) là một Composite chưa được khai sinh.
Hậu quả khi dự án lớn lên có tính cơ học: thêm một loại node mới (ví dụ GiftCard — là lá, giá 0, nhưng không được tính vào tổng) buộc bạn phải mở mọi chỗ gọi đang có instanceof, và compiler không chỉ được chỗ nào thiếu vì else cuối cùng thường chỉ là sum += 0 im lặng. Bug loại này không crash — nó ra con số sai trên hoá đơn.
Nguyên nhân sâu hơn nằm ở kiểu dữ liệu: Product và Bundle cùng trả lời được các câu hỏi "giá bao nhiêu", "vẽ ra sao", "còn hàng không", nhưng hệ thống type không biết điều đó, nên mỗi chỗ gọi phải tự tái dựng vòng đệ quy và tự nhớ case nào còn thiếu.
02 — Ý tưởng, chưa động vào code
Giải pháp
Composite: đưa lá và nhánh về cùng một interface, và định nghĩa mỗi phép toán theo kiểu đệ quy ngay trong interface đó. size() của lá là một con số; size() của nhánh là tổng size() của con. Không có chỗ nào ngoài hai class này biết sự khác biệt giữa lá và nhánh.
Client vì thế chỉ giữ FsNode, và một hàm chạy cho cả hai: in một file hay in cả thư mục là cùng một lời gọi. Vòng đệ quy sống đúng một nơi, được test một nơi, và khi thêm loại node mới, không một chỗ gọi nào phải sửa.
Cái giá, nói thẳng trước: nếu interface có add(child), lá buộc phải fake nó (ném error hoặc im lặng làm rỗng) — đó là dấu hiệu vi phạm Liskov. Có hai cách sống chung, và bạn phải chọn có ý thức: interface "transparent" (mọi node đều có add, leaf fake) hoặc interface "safe" (tách CompositeNode extends FsNode có add, client muốn thêm con thì phải biết mình đang cầm composite). Không có phương án thứ ba miễn phí.
03 — Làm thật, mỗi bước một fragment code
Từng bước một
Liệt kê loại node và các phép toán chạy trên cả lá lẫn nhánh
Composite chỉ đáng làm khi có phép toán chung cho hai loại. Liệt kê node ra một bên (File, Folder, MenuItem, MenuCategory), phép toán ra một bên (tổng dung lượng, render, đếm số lượng, validate, serialize).
Với mỗi ô giao nhau, hỏi: phép toán này có định nghĩa được cho cả lá lẫn nhánh không? delete() thì vô nghĩa với File — đừng nhét nó vào interface chung. Interface chỉ lấy phần cả hai phía cùng trả lời được.
size() render() count() add() delete()
File (leaf) co co co khong co
Folder (composite) co co co co co
MenuItem (leaf) co co co khong co
=> interface chung: size, render, count
=> add/delete: chỉ phía composite (hoặc chấp nhận leaf fake)Định nghĩa interface bằng đúng các phép toán đệ quy
Interface không mô tả "hình dạng của một file", nó mô tả cách hỏi một node. Chú ý render(depth): tham số depth chỉ tồn tại vì có cây — mọi node đều phải biết mình đang ở tầng nào để tự vẽ, kể cả lá.
Đây là lúc chọn: add() nằm trong interface chung (transparent) hay nằm trong interface riêng của composite (safe). Đoạn dưới chọn transparent để bạn thấy tận mắt cái giá của nó ở Bước 6.
export interface FsNode {
readonly name: string
/** Lá: trả về số byte. Nhánh: tổng của con. */
size(): number
/** Trả về nhiều dòng để caller khỏi cần biết độ sâu. */
render(depth: number): string[]
add(child: FsNode): void
}Leaf: trả lời trực tiếp, không có children
Lá là nơi đệ quy dừng. size() của file là dữ liệu, không phải vòng lặp; render() của nó trả về đúng một dòng. Nếu bạn thấy leaf của mình giữ một mảng children rỗng chỉ để gọi .reduce() cho giống, bạn đang để logic của composite rò xuống lá.
import type { FsNode } from './component'
export class FileEntry implements FsNode {
constructor(readonly name: string, private bytes: number) {}
size(): number { return this.bytes }
render(depth: number): string[] {
return [' '.repeat(depth) + this.name + ' (' + this.bytes + ')']
}
// cái giá của interface transparent:
add(_child: FsNode): void { throw new Error('File không chứa được gì: ' + this.name) }
}Composite: cộng tác bằng cách hỏi con, đúng một tầng
Nhánh không đi khắp cây. size() của nó là reduce qua con trực tiếp, mỗi con tự lo phần của mình; con là folder thì folder đó lại reduce tiếp. Không một dòng nào trong FolderEntry nhắc tới độ sâu hay tới "con của con".
Đó là toàn bộ sức mạnh của Composite: bạn viết một bước cộng, và nó đúng cho cây 2 tầng lẫn cây 2000 tầng, vì phần còn lại do các node khác chịu trách nhiệm.
import type { FsNode } from './component'
export class FolderEntry implements FsNode {
private children: FsNode[] = []
constructor(readonly name: string) {}
add(child: FsNode): void { this.children.push(child) }
size(): number {
return this.children.reduce((sum, c) => sum + c.size(), 0)
}
render(depth: number): string[] {
const lines = [' '.repeat(depth) + this.name + '/ (' + this.size() + ')']
for (const c of this.children) lines.push(...c.render(depth + 1))
return lines
}
}Chỗ gọi chỉ còn interface: một hàm chạy cho cả lá lẫn cây
Bây giờ nhìn từ phía client. Nó không instanceof, không switch (node.kind), không biết FolderEntry là gì. printSize(readme) và printSize(app) là cùng một dòng code với hai đối số khác nhau — đó là lý do pattern này có tên trong sách.
import type { FsNode } from './component'
import { FileEntry } from './leaf'
import { FolderEntry } from './composite'
const printSize = (node: FsNode): void => console.log(node.name + ': ' + node.size() + ' bytes')
const readme: FsNode = new FileEntry('README.md', 120)
const app = new FolderEntry('app')
app.add(new FileEntry('main.ts', 80))
app.add(readme)
printSize(readme) // một lá, đơn độc
printSize(app) // cả cây, cùng một hàm, không một nhánh nàoREADME.md: 120 bytes app: 200 bytes
Trả giá: leaf fake add(), và lựa chọn transparent/safe
readme.add(x) là code hợp lệ về type nhưng sai về ngữ nghĩa. Bạn xử lý bằng một throw — nghĩa là compiler không còn chặn được bạn, mà phải tới lúc chạy mới biết. Đây chính là vi phạm Liskov: một subtype không thay thế được supertype về hành vi.
Phương án "safe" tách interface: FsNode chỉ có size/render, còn CompositeNode extends FsNode thêm add(). Bù lại, client muốn thêm con phải biết mình đang cầm composite — và các instanceof bạn vừa đuổi đi sẽ quay về, ít nhất ở chỗ ghi dữ liệu. Trong TypeScript còn một lối nửa vời dễ chịu: giữ transparent nhưng khai báo add?(child: FsNode) và gọi node.add?.(child) — leaf không phải fake, đổi lại mọi caller phải xử lý nhánh "không có".
export interface FsNode { readonly name: string, size(): number }
export interface CompositeNode extends FsNode {
add(child: FsNode): void // chỉ composite mới hứa cái này
isComposite(): true
}
// caller muốn thêm con thì phải xin quyền:
function addTo(node: FsNode, child: FsNode) {
if (isComposite(node)) node.add(child)
else throw new Error(node.name + ' không chứa được gì')
}
const isComposite = (n: FsNode): n is CompositeNode => 'isComposite' in nThêm chiều thật của cây: depth, cycle, cache
Cây trong demo này sâu 3 tầng nên đệ quy miễn phí. Cây comment của app thật sâu không lường trước (reply-of-reply 200 tầng là đủ chạm trần call stack), và nếu user chọn "trả lời" vào một comment là tổ tiên của chính nó, bạn có một chu trình — đệ quy không bao giờ về.
Hai defence rẻ: giới hạn độ sâu (kèm thông báo lỗi nói rõ độ sâu), và chặn chu trình ngay lúc add() bằng cách đi lên chuỗi cha hoặc dùng Set đã-ghé. Nếu tổng hợp (size, count) được gọi nhiều lần trên cây lớn, cache tại node và vô hiệu cache trong add/remove — đừng tính lại cả nghìn node cho một lần hiển thị.
const MAX_DEPTH = 64
class FolderEntry {
private children: FsNode[] = []
private cachedSize = -1
add(child: FsNode): void {
if ((child as unknown as { hasAncestor?: (n: object) => boolean }).hasAncestor?.(this)) {
throw new Error('không nhét node vào chính con cháu của nó')
}
this.children.push(child)
this.cachedSize = -1 // vô hiệu cache khi cây đổi
}
size(depth = 0): number {
if (depth > MAX_DEPTH) throw new Error('cây sâu bất thường, nghi có cycle')
if (this.cachedSize < 0) {
this.cachedSize = this.children.reduce((s, c) => s + c.size(depth + 1), 0)
}
return this.cachedSize
}
}Đo xem có đáng: số file sửa được khi thêm node mới
Bài test cuối, cũng là bài test duy nhất đáng tin: thêm một loại lá mới (Symlink) rồi đếm số file phải sửa. Đúng ra là 1. Nếu bạn phải sửa client.ts, renderer.ts, validator.ts, thì còn instanceof rơi rớt ở đâu đó — tìm và giết.
Nếu việc bạn thêm thường xuyên là phép toán mới (search, diff, export) chứ không phải node mới, thì Composite cộng dồn đệ quy sẽ bắt bạn sửa mọi class một lần cho mỗi phép toán. Đó là lúc Visitor xuất hiện — xem visitor. Còn nếu cây của bạn chỉ có 2 tầng cố định và 4 loại node, khả năng cao là bạn không cần pattern này: một mảng phẳng và một field parentId rẻ hơn nhiều.
// File MỚI, duy nhất. Không sửa FolderEntry, không sửa client.
export class Symlink implements FsNode {
constructor(readonly name: string, private target: FsNode) {}
size(): number { return this.target.size() }
render(depth: number): string[] { return [' '.repeat(depth) + this.name + ' -> ' + this.target.name] }
add(child: FsNode): void { this.target.add(child) }
}04 — Ai nói chuyện với ai
Cấu trúc
- ComponentInterface chung: `size()`, `render(depth)`. Mọi câu hỏi mà cả lá lẫn nhánh đều trả lời được.
- LeafPhần tử không có con. Mỗi method là một phép tính trực tiếp; đây là đáy của đệ quy.
- CompositePhần tử có `children: Component[]`. Mỗi method = hỏi từng con rồi cộng kết quả lại.
- ClientChỉ giữ `Component`. Gọi một phần tử và gọi cả cây bằng đúng một dòng code.
- Client-Writer (tuỳ chọn)Chỗ thật sự cần thêm/bớt con — nơi bạn phân biệt Composite với Leaf (bản "safe") hoặc nơi hứng `throw` (bản "transparent").
┌───────────────────────────────┐
│ Component (interface) │
│ + name: string │
│ + size(): number │
│ + render(depth): string[] │
│ + add(child) ← leaf fake! │
└──────────────┬────────────────┘
┌────────┴────────┐
▼ ▼
┌───────────────────┐ ┌───────────────────────┐
│ Leaf (FileEntry) │ │ Composite (Folder) │
│ size() = bytes │ │ children: FsNode[] │
│ add() -> throw │ │ size() = Σ con.size()│
└───────────────────┘ └───────────┬───────────┘
│ đệ quy: chỉ hỏi con trực tiếp
┌───────────────────┼───────────────────┐
▼ ▼ ▼
FolderEntry FileEntry FolderEntry
(nhánh con) (lá) (nhánh)
Client chỉ giữ FsNode → không biết (và không cần biết) đang cầm cái nào.05 — Sửa tuỳ ý, chạy ngay tại đây
Chạy thử: cùng một hàm `size()`/`render()` cho file và cho cả cây
interface FsNode {
readonly name: string
size(): number
render(depth: number): string[]
add(child: FsNode): void
}
class FileEntry implements FsNode {
constructor(readonly name: string, private bytes: number) {}
size(): number { return this.bytes }
add(_child: FsNode): void { throw new Error('File không chứa được gì: ' + this.name) }
render(depth: number): string[] { return [' '.repeat(depth) + this.name + ' (' + this.bytes + ')'] }
}
class FolderEntry implements FsNode {
private children: FsNode[] = []
constructor(readonly name: string) {}
add(child: FsNode): void { this.children.push(child) }
size(): number { return this.children.reduce((sum, c) => sum + c.size(), 0) }
render(depth: number): string[] {
const lines = [' '.repeat(depth) + this.name + '/ (' + this.size() + ')']
for (const c of this.children) lines.push(...c.render(depth + 1))
return lines
}
}
const src = new FolderEntry('src')
src.add(new FileEntry('App.vue', 240))
const utils = new FolderEntry('utils')
utils.add(new FileEntry('format.ts', 150))
utils.add(new FileEntry('parse.ts', 250))
src.add(utils)
const root = new FolderEntry('app')
root.add(src)
const readme = new FileEntry('README.md', 120)
root.add(readme)
console.log(root.render(0).join('\n'))
console.log('total: ' + root.size())
try { readme.add(new FileEntry('x.ts', 10)) }
catch (e) { console.log('leaf cũng phải fake add(): ' + (e as Error).message) }app/ (760)
src/ (640)
App.vue (240)
utils/ (400)
format.ts (150)
parse.ts (250)
README.md (120)
total: 760
leaf cũng phải fake add(): File không chứa được gì: README.mdCùng code này chạy được bằng Bun: bun run demo.ts. Output in ra được kiểm tự động trong quá trình build site.
06 — Thành thật về cái giá
Khi nào dùng, khi nào đừng
Dùng khi
- Domain thật sự là cây: menu/category, file system, comment có reply, org chart, breadcrumb, AST, DOM, cây component.
- Client muốn coi một phần tử và cả một nhóm là một: cùng tính tổng, cùng render, cùng gửi đi (nguyên lý "composite unit").
- Bạn đếm được ≥ 2 loại node và ≥ 2 phép toán chung chạy được trên cả lá lẫn nhánh.
- Loại node mới xuất hiện thường xuyên hơn là phép toán mới (ngược lại thì Visitor phù hợp hơn).
- Bạn muốn một chỗ duy nhất chứa vòng đệ quy, để kiểm soát độ sâu, cache và lỗi ở đó.
- Đừng dùng nếu cấu trúc phẳng và cố định (order → items, post → tags): cha con giả tạo chỉ thêm một tầng indirection.
Đừng dùng khi
- Thuế LSP.
add()trên interface chung buộc leaf phải fake —throw, no-op, hay trảfalseđều là chữ ký của một thiết kế đã thoả hiệp. Chọn transparent/safe có ý thức, đừng để nó tự xảy ra. - Over-generalise kiểu JS. Nửa đường, ai cũng viết
interface Node { type: string, children: Node[], meta: Record<string, any> }. cây thì tổng quát thật, nhưng đổi lạinode.meta.pricelàanyvà không còn ai biết node là cái gì. Composite đáng giá khi interface mạnh (size(): number), không phải khi mọi thứ bị hoà thành một shape chung. - Đệ quy không miễn phí: trần call stack (vài nghìn tầng là crash), chu trình do user tạo (reply vào tổ tiên của mình) biến render thành vòng lặp vô hạn. Trần độ sâu + chặn cycle là bắt buộc, không phải optional.
- Đo lường:
Σ size()mỗi lần render là O(N) cho mỗi frame. Với cây lớn, cache tại composite và vô hiệu cache trong add/remove; nếu không, UI sẽ chậm mà profiler chỉ ra đúng một hàm đệ quy. - Composite + nhiều phép toán = mỗi phép toán mới phải sửa mọi class. Nếu đó là chiều thay đổi chính của bạn, đừng cố: chuyển sang Visitor, hoặc tách hành vi ra function thuần nhận
Component.
07 — Bạn đã gặp nó rồi, chỉ là không gọi tên
Trong code thật
DOM: Node là composite, Text là leaf
Element (composite) và Text/Comment (leaf) cùng cài Node, và element.textContent là một phép cộng đệ quy trên toàn bộ subtree — bạn không cần biết giữa đường có bao nhiêu tầng. Ngược lại, gọi appendChild trên một Text node thất bại: đúng cái thuế "leaf phải fake add()" mà browser cũng không tránh được.
Cây VNode của Vue
Template compiled thành VNode tree: Fragment (nhiều node gốc, v-for) là composite, text/comment vnodes là leaf, và patch() trong runtime-core là một hàm đệ quy xử lý mọi loại mà không cần biết component lồng bao nhiêu tầng. Nested <RouterView>/<NuxtPage> với layout lồng nhau chính là cây này.
@babel/traverse, ESLint, PostCSS
Mỗi node AST có type và các field con; visitorKeys nói cho traverser biết field nào là con, để plugin của bạn viết enter(node) đúng một lần và chạy đúng trên mọi node type. Cấu trúc lồng nhau là Composite, traverser là client không biết gì về loại node cụ thể.
JSON: composite thuần tuý
JSON.stringify chỉ cần một thuật toán đệ quy: object/array là composite, string/number/boolean/null là leaf. Không có một dòng if (typeof value === "object" && depth === 2) nào, vì leaf và composite cùng trả lời một câu hỏi: "serialize ra gì".
08 — Tự tay làm
Bài tập
Menu của app ăn uống có `MenuItem { name, price }` và `MenuCategory { name, items }`, và chỗ gọi hiện viết `if (item instanceof MenuCategory)`. Hãy chuyển sang Composite với `total()` và `render(depth)`, rồi thêm `Combo` (một nhóm giảm 10% giá tổng) mà **không sửa chỗ gọi**.
Gợi ý, mở từng cái một:
- Interface chung cần gì? Gợi ý:
name,total(): number,render(depth): string[]— vàadd()thì để đâu? - Composite không được cộng giá của cháu: nó chỉ hỏi con trực tiếp.
Σ con.total()là đủ. CombokhácMenuCategoryđúng một chỗ — hãy kế thừa từ composite thay vì viết lại vòng lặp.
Khai báo interface MenuNode { name, total(), render(depth) }. MenuItem cài trực tiếp (leaf). MenuCategory giữ nodes: MenuNode[], total() là reduce, render() cộng thêm indent và đệ quy con. Combo extends MenuCategory chỉ override total() bằng super.total() * 0.9. Chỗ gọi vẫn là console.log(menu.total()).
interface MenuNode {
readonly name: string
total(): number
render(depth: number): string[]
}
class MenuItem implements MenuNode {
constructor(readonly name: string, private price: number) {}
total() { return this.price }
render(d: number) { return [' '.repeat(d) + this.name + ': ' + this.total()] }
}
class MenuCategory implements MenuNode {
protected nodes: MenuNode[] = []
constructor(readonly name: string) {}
add(n: MenuNode) { this.nodes.push(n) }
total() { return this.nodes.reduce((s, n) => s + n.total(), 0) }
render(d: number): string[] {
const out = [' '.repeat(d) + this.name + ' = ' + this.total()]
for (const n of this.nodes) out.push(...n.render(d + 1))
return out
}
}
class Combo extends MenuCategory { // node MỚI, không sửa chỗ gọi
total() { return Math.round(super.total() * 0.9) }
}
const tour = new Combo('Gói du lịch')
tour.add(new MenuItem('Vé máy bay', 1_500_000))
const khachSan = new MenuCategory('Khách sạn')
khachSan.add(new MenuItem('2 đêm', 900_000))
khachSan.add(new MenuItem('Ăn sáng', 200_000))
tour.add(khachSan)
console.log(tour.render(0).join('\n'))
console.log('khach le: ' + new MenuItem('Cà phê', 45_000).total())09 — Đọc cặp để hiểu bản chất
Pattern liên quan
- IteratorKhi client cần **đi qua** cây thay vì gọi một phép toán gộp, Iterator là cách đưa vòng đệ quy ra khỏi client. Composite + Iterator là cặp bài trùng (duyệt cây theo thứ tự preorder/postorder).
- VisitorCùng giải quyết cây, ngược trục: Composite nhét hành vi vào node (thêm node rẻ, thêm phép toán đắt); Visitor đẩy hành vi ra ngoài (thêm phép toán rẻ, thêm node đắt).
- DecoratorCùng "đứng cùng interface với thứ mà nó chứa", nhưng Decorator bọc **đúng một** object để thêm trách nhiệm, Composite chứa **nhiều** object để gộp kết quả. Stack decorator cũng là một cây — chỉ là cây một nhánh.
- FlyweightKhi lá lặp lại hàng nghìn lần (glyph trong text, quân cờ, icon), Flyweight cho các leaf dùng chung một object, Composite giữ cây tham chiếu tới chúng.