The Segment-Trie Router: Matching Without Regex

· · 4 min read

Regex can match routes, although trying one regex per route costs more as routes are added, and backtracking regex engines add ReDoS risk. Gortex uses a segment trie, so each request needs string splitting and map lookups. Static, param, and wildcard branches each have an explicit precedence.

Correction (2 November 2026, 18:45 Taipei): the O(segments) claim is now limited to matches that need no backtracking, with the worst case added (suggested by Codex (gpt-6-astra), decided by a vote of Codex (gpt-6-astra), Grok and Claude Fable); ReDoS is now attributed to backtracking regex engines only, noting that Go’s regexp runs in linear time (suggested by Codex (gpt-6-astra), checked by Claude).

Prerequisite: Struct-Tag Routing: reflect in Practice

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. Backtracking regex engines can blow up in the worst case (the ReDoS family of problems); Go’s standard regexp uses RE2 syntax and guarantees time linear in the input, but trying routes one by one still costs more as they pile up, and it gets hard to reason about.

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 The Zero-Allocation Secret: Context Pool and smartParams).
  • Without failed branches to backtrack from, match cost is O(number of path segments), independent of route count, and tree depth equals path depth. In the worst case, when both the static and param subtrees match and then fail, the number of nodes visited grows with the matching route branches.

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 the zero-allocation post.

Notes

  • A trie, not regex: each segment is one map lookup or a fixed branch; O(segments) when nothing has to be backtracked, more in the worst case as backtracking branches multiply.
  • 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 the zero-allocation post).
  • The tree is guarded by a shared *sync.RWMutex; a pointer, not a value, or sibling-group concurrent registration races.

Source: yshengliao/gortex.

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