# The Segment-Trie Router: Matching Without Regex

> Gortex routes with a segment trie, not regex: string splitting plus map lookups in O(segments), static > param > wildcard precedence, no allocations.

Source: https://sheng.page/en/posts/gortex-segment-trie-router/ · Published: 2026-03-08 · Author: Sheng

Regex can match routes, although its backtracking makes the work less predictable. Gortex uses a segment trie, so each request needs string splitting and map lookups. Static, param, and wildcard branches each have an explicit precedence.

> Prerequisite: [Struct-Tag Routing: reflect in Practice](/en/posts/gortex-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:

```go
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.

```go
// 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](/en/posts/gortex-zero-allocation-context/)).
- 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`:

```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
}
```

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), 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 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](https://github.com/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.