# Segment-trie 路由器：不靠正則的匹配

> gortex 的 segment-trie 路由器不靠正則，每次請求只做字串切割加 map 查詢，比對成本 O(segments)，Static、Param、Wildcard 依序比對並支援回溯。

原文：https://sheng.page/posts/gortex-segment-trie-router/ · 發布：2026-03-08 · 作者：Sheng

路由比對可以用正則，但正則有回溯的不確定性。gortex 選了 segment-trie，每次請求只做字串切割加 map 查詢。這篇講 Static、Param、Wildcard 的優先順序。

> 前置閱讀：〈[Struct tag 宣告式路由：reflect 實戰](/posts/gortex-struct-tag-routing/)〉

## 為什麼是 trie 不是正則

路由就是把一條 path 對到一個 handler。一種做法是把每條路由編成正則逐一試，但正則的回溯在最壞情況下是不確定的（ReDoS 那類風險），路由一多就難推理效能。

gortex 選 segment-trie：把 path 用 `/` 切成 segment，沿一棵樹往下走，每一步不是 map 查詢就是固定分支，確定且可預期。每個 HTTP method 各自一棵樹（`trees map[string]*routeNode`），節點分三種：

```go
type routeNode struct {
    handler    HandlerFunc
    children   map[string]*routeNode // static：精確段
    paramChild *routeNode            // :id
    wildChild  *routeNode            // *
    paramName  string
}
```

## Static > Param > Wildcard

比對有明確優先序，而且會回溯。`searchTree` 取出當前 segment 後，依序試：

1. **static**：`children[segment]` 命中就先走。
2. **param**：`:id`，先記下參數往下走；子樹找不到 handler 就回溯（`params.truncate`）退回。
3. **wildcard**：`*`，吃掉剩下整段 path。

```go
// 1. static 先試
if child, ok := node.children[segment]; ok {
    if h, mw := r.searchTree(child, rest, params); h != nil {
        return h, mw
    }
}
// 2. 再試 param；失敗就 truncate 回溯，換 wildcard
if node.paramChild != nil {
    saved := params.count
    params.set(node.paramChild.paramName, segment)
    if h, mw := r.searchTree(node.paramChild, rest, params); h != nil {
        return h, mw
    }
    params.truncate(saved)
}
// 3. 最後才 wildcard
```

回溯是關鍵：`/users/new` 會比中 static 的 `/users/new`，而不是被 `/users/:id` 攔走，即使 `:id` 也配得到 "new"。wildcard 的捕捉名「先註冊先贏」，所以同一位置註冊 `*x` 再 `*y`，結果固定走 `x`。

## O(segments) 比對

hot path 刻意零配置：

- `searchTree` 直接走字串，用 `strings.IndexByte` 找下一個 `/`，**不呼叫 `strings.Split`**，省掉每次請求的 slice 配置。註冊期的 `addToTree` 才用 split，那不在 hot path。
- 參數寫進 `*smartParams`，**不配 map**（細節留〈[零分配的秘密：Context pool 與 smartParams](/posts/gortex-zero-allocation-context/)〉）。
- 比對成本是 O(path segment 數)，跟總路由數無關，樹深等於 path 深。

並行方面，整棵樹由一把**共享的 `*sync.RWMutex`** 保護，`findRoute` 用 `RLock`（讀並行），註冊用 `Lock`：

```go
func (r *gortexRouter) findRoute(method, path string, params *smartParams) HandlerFunc {
    r.mu.RLock()
    defer r.mu.RUnlock()
    root := r.trees[method]
    if root == nil {
        return nil
    }
    params.reset()
    h, _ := r.searchTree(root, path, params)
    return h
}
```

這把鎖是 pointer 不是 value：`Group()` 出來的子 router 共用同一個 `trees` map，若用 value mutex，每個 group 會各自一把鎖去鎖同一份資料，sibling 併發註冊就是 data race。`ServeHTTP` 進來還先從 pool 拿 Context（`AcquireContext` / `defer ReleaseContext`），直接接到零分配那篇。


## 補充筆記

- 路由用 trie 不用正則：每段一次 map 查詢或固定分支，O(segments)、沒有回溯不確定性。
- 每個 HTTP method 一棵樹；節點分 static / param / wildcard。
- 比對優先序 Static > Param > Wildcard，靠 `params.truncate` 回溯，`/users/new` 贏過 `/users/:id`。
- hot path 零配置：比對直接走字串免 `strings.Split`、參數免 map（接零分配那篇）。
- 樹用共享的 `*sync.RWMutex`（pointer 不是 value，否則 sibling group 併發註冊會 data race）。

原始碼：[yshengliao/gortex](https://github.com/yshengliao/gortex)。

---

> 想法與技術判斷出自 Sheng，和 Claude 一起起草 · 環境 Go 1.24（gortex go.mod）· 本系列為事後回填整理 · 列入 20260613 blog 翻新計劃，新漆未乾。