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

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

前置：B2 struct-tag routing。

為什麼是 trie 不是正則

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

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

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

Static > Param > Wildcard

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

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

// 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（細節留 B4）。
比對成本是 O(path segment 數)，跟總路由數無關，樹深等於 path 深。

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

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），直接接到 B4 的零分配。

重點整理

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

原始碼：yshengliao/gortex。

大綱 Sheng，內文 Claude 協助 · 環境 Go 1.24（gortex go.mod）· 本系列為事後回填整理 · 列入 20260613 blog 翻新計劃，新漆未乾。