The Segment-Trie Router: Matching Without Regex

You can match routes with regex, but regex brings backtracking uncertainty. Gortex picks a segment-trie: each request is just string splitting plus map lookups. This post covers static, param, and wildcard precedence.

Prerequisite: B2 struct-tag routing.

Why a trie, not regex

Routing maps a path to a handler. One approach compiles each route to a regex and tries them in turn — but regex backtracking is nondeterministic in the worst case (the ReDoS family of problems), and it gets hard to reason about as routes pile up.

Gortex picks a segment-trie: split the path on / into segments and walk a tree, where each step is either a map lookup or a fixed branch — deterministic and predictable. Each HTTP method gets its own tree (trees map[string]*routeNode), and a node is one of three kinds:

type routeNode struct {
    handler    HandlerFunc
    children   map[string]*routeNode // static: an exact segment
    paramChild *routeNode            // :id
    wildChild  *routeNode            // *
    paramName  string
}

Static > Param > Wildcard

Matching has a definite precedence, and it backtracks. After searchTree pulls the current segment, it tries, in order:

1. static: take children[segment] if it’s there.
2. param: :id, record the parameter and descend; if the subtree finds no handler, backtrack (params.truncate).
3. wildcard: *, swallow the rest of the path.

// 1. static first
if child, ok := node.children[segment]; ok {
    if h, mw := r.searchTree(child, rest, params); h != nil {
        return h, mw
    }
}
// 2. then param; on failure truncate and fall through to 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 last

Backtracking is the point: /users/new matches the static /users/new rather than being intercepted by /users/:id — even though :id would happily match “new”. A wildcard’s capture name is “first registration wins”, so registering *x then *y at the same spot deterministically resolves under x.

O(segments) matching

The hot path is deliberately allocation-free:

• searchTree walks the string directly, using strings.IndexByte to find the next /, and never calls strings.Split, saving a per-request slice allocation. Registration’s addToTree uses split — but that’s not the hot path.
• Parameters are written into a *smartParams, with no map allocation (details in B4).
• Match cost is O(number of path segments), independent of route count — tree depth equals path depth.

For concurrency, the whole tree is guarded by one shared *sync.RWMutex: findRoute takes RLock (concurrent reads), registration takes 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
}

The lock is a pointer, not a value: a child router from Group() shares the same trees map, so a value mutex would give each group its own lock over the same data — a data race when sibling groups register concurrently. ServeHTTP also takes the Context from a pool on the way in (AcquireContext / defer ReleaseContext), which leads straight into B4’s zero-allocation story.

Takeaways

• A trie, not regex: each segment is one map lookup or a fixed branch — O(segments), no backtracking uncertainty.
• One tree per HTTP method; nodes are static / param / wildcard.
• Precedence is Static > Param > Wildcard, with params.truncate to backtrack — /users/new beats /users/:id.
• The hot path is allocation-free: matching walks the string without strings.Split, and params avoid a map (continued in B4, “The Zero-Allocation Secret”, gortex-zero-allocation-context).
• The tree is guarded by a shared *sync.RWMutex — a pointer, not a value, or sibling-group concurrent registration races.

Source: yshengliao/gortex.

---

Outline by Sheng, drafted with Claude · Go 1.24 (gortex go.mod) · compiled retroactively · part of the 2026-06-13 blog renovation, paint still drying.