Compiled Router

TypoKit’s router is a compiled radix tree — constructed at build time in Rust, serialized to a plain TypeScript module, and consumed at runtime for O(k) route lookup (where k is the number of path segments). No runtime route compilation, no regex matching, no linear scans.

Note

For a high-level overview of where the router fits in the overall architecture, see the Architecture Overview. For the build pipeline that produces the router, see the Build Pipeline deep dive.

Why a Compiled Router?

Traditional frameworks compile routes at server startup — parsing path patterns, building regex tables, and constructing lookup structures on every cold start. TypoKit moves all of this to build time:

Approach	When routes are compiled	Startup cost	Lookup complexity
Express-style linear scan	Server startup	O(n) registration	O(n) per request
Fastify-style radix tree	Server startup	O(n) construction	O(k) per request
TypoKit compiled radix tree	Build time (Rust)	O(1) — load pre-built tree	O(k) per request

By compiling the radix tree in Rust during the build step, TypoKit achieves:

1. Near-zero startup cost — The tree is already built; runtime just loads the module
2. O(k) lookup — Walk the tree by path segment depth, not route count
3. AI-inspectable output — The compiled tree is a plain TypeScript file that agents can read and understand
4. Deterministic behavior — The same route definitions always produce the same tree; no runtime surprises

Build-Time Construction (Rust)

Route compilation is stage 3 of 8 in the Rust transform pipeline, handled by route_compiler.rs in @typokit/transform-native. The process:

1. Extract route contracts — The type extractor (stage 2) identifies all RouteContract interfaces and their HTTP method + path declarations (e.g., "GET /users/:id").

2. Parse path patterns — Each path is split into segments. Segments are classified as:

   • Static — Exact string match (e.g., users, posts)
   • Parameterized — Starts with : (e.g., :id, :slug)
   • Wildcard — * catch-all (e.g., *path matches all remaining segments)

3. Construct the radix tree — Segments are inserted into a compressed trie (radix tree). Shared prefixes are merged into common nodes, minimizing memory and maximizing lookup speed.

4. Assign handler references — Each leaf node is annotated with a handler reference key (method + path) that maps to the handler registry at runtime.

5. Serialize to TypeScript — The tree structure is serialized as a plain TypeScript module at .typokit/routes/compiled-router.ts.

How the Radix Tree Works

A radix tree (also called a compressed trie or Patricia tree) stores strings by their shared prefixes. For URL routing, each node represents one or more path segments:

Routes defined:
  GET  /users
  GET  /users/:id
  GET  /users/:id/posts
  POST /users
  GET  /posts
  GET  /posts/:slug

Radix tree structure:
  root
  ├── users ──────────── [GET, POST]
  │   └── :id ────────── [GET]
  │       └── posts ──── [GET]
  └── posts ──────────── [GET]
      └── :slug ──────── [GET]

The key insight: looking up /users/abc123/posts requires walking exactly 3 nodes (users → :id → posts), regardless of how many total routes exist. This is the O(k) guarantee — k is path depth, not route count.

Compiled Router Output Format

The Rust transform serializes the radix tree to .typokit/routes/compiled-router.ts. Here’s an example of the generated output for a typical API:

.typokit/routes/compiled-router.ts

// AUTO-GENERATED — do not edit. Regenerated on every build.

import type { CompiledRouteNode, CompiledRouteTree } from "@typokit/types";

export const routeTree: CompiledRouteTree = {
  root: {
    segment: "",
    children: [
      {
        segment: "users",
        methods: {
          GET: { ref: "GET /users", validators: ["PaginatedQuery"] },
          POST: { ref: "POST /users", validators: ["CreateUserInput"] },
        },
        children: [
          {
            segment: ":id",
            paramName: "id",
            methods: {
              GET: { ref: "GET /users/:id", validators: [] },
              PUT: { ref: "PUT /users/:id", validators: ["UpdateUserInput"] },
              DELETE: { ref: "DELETE /users/:id", validators: [] },
            },
            children: [
              {
                segment: "posts",
                methods: {
                  GET: { ref: "GET /users/:id/posts", validators: ["PaginatedQuery"] },
                },
                children: [],
              },
            ],
          },
        ],
      },
      {
        segment: "posts",
        methods: {
          GET: { ref: "GET /posts", validators: ["PaginatedQuery"] },
          POST: { ref: "POST /posts", validators: ["CreatePostInput"] },
        },
        children: [
          {
            segment: ":slug",
            paramName: "slug",
            methods: {
              GET: { ref: "GET /posts/:slug", validators: [] },
            },
            children: [],
          },
        ],
      },
    ],
  },
  metadata: {
    totalRoutes: 8,
    maxDepth: 3,
    staticRoutes: 3,
    parameterizedRoutes: 5,
    generatedAt: "2026-03-02T12:00:00.000Z",
  },
};

Tip

This file is plain TypeScript — AI agents can read it to understand the full route structure. It’s also gitignored and regenerated on every build, so it’s always in sync with the source route contracts.

Route Table Companion

Alongside the compiled router, the build generates .typokit/routes/route-table.ts — a flat registry mapping handler references to their metadata:

.typokit/routes/route-table.ts

// AUTO-GENERATED — do not edit.

import type { RouteTableEntry } from "@typokit/types";

export const routeTable: Record<string, RouteTableEntry> = {
  "GET /users": {
    method: "GET",
    path: "/users",
    params: [],
    querySchema: "PaginatedQuery",
    responseSchema: "PaginatedResponse<PublicUser>",
    middleware: [],
  },
  "GET /users/:id": {
    method: "GET",
    path: "/users/:id",
    params: ["id"],
    querySchema: null,
    responseSchema: "PublicUser",
    middleware: [],
  },
  "POST /users": {
    method: "POST",
    path: "/users",
    params: [],
    bodySchema: "CreateUserInput",
    responseSchema: "PublicUser",
    middleware: [],
  },
  // ... additional routes
};

Server adapters use both files: the compiled router for request matching and the route table for handler metadata (validation schemas, middleware chains, response types).

Runtime Route Matching

At runtime, route matching is a simple tree walk. Here’s the algorithm:

1. Split the request path into segments (e.g., /users/abc123/posts → ["users", "abc123", "posts"]).

2. Walk the tree from the root, matching each segment against child nodes:

   • First, check static children for an exact match
   • If no static match, check for a parameterized child (:param)
   • If no param match, check for a wildcard child (*)

3. Extract parameters as the walk progresses. When a :param node matches, record the segment value under the parameter name.

4. Check the HTTP method on the matched leaf node. If the method exists, return the handler reference. If not, return a 405 Method Not Allowed with the Allow header listing valid methods.

5. Return 404 if no node matches after exhausting the tree.

Static vs. Parameterized Route Lookup

The tree walk prioritizes static segments over parameterized ones. This is critical for correctness:

// Route definitions:
// GET /users/me      — static "me" segment
// GET /users/:id     — parameterized ":id" segment

// Request: GET /users/me
// Match: GET /users/me ✓ (static match takes priority)
// NOT:   GET /users/:id with id = "me"

// Request: GET /users/abc123
// Match: GET /users/:id with id = "abc123" ✓ (no static match, falls to param)

The priority order at each tree level is:

1. Static match — Exact string comparison (fastest)
2. Parameterized match — Any single segment captured as a named parameter
3. Wildcard match — Captures all remaining segments

This priority is enforced at build time — the Rust compiler structures child nodes so that static children are checked before parameterized ones.

Lookup Complexity

Route type	Complexity	How
Static route (e.g., /users)	O(k) where k = segment count	Walk tree, string comparison per segment
Parameterized route (e.g., /users/:id)	O(k) where k = segment count	Walk tree, param node matches any segment
Wildcard route (e.g., /files/*path)	O(k) where k = segments before wildcard	Walk to wildcard node, capture rest
Method resolution	O(1)	Hash map lookup on matched node

The key property: lookup time depends on path depth (typically 2–4 segments), not on route count (could be hundreds). An API with 5 routes and an API with 500 routes have the same lookup speed for a given path depth.

Edge Cases

Parameter vs. Static Priority

When both a static and parameterized route match the same position, the static route always wins:

// Routes:
// GET /files/upload     → static match
// GET /files/:filename  → param match

// GET /files/upload    → matches /files/upload (static)
// GET /files/readme.md → matches /files/:filename with filename = "readme.md"

This is the standard behavior across radix tree routers (find-my-way, @hono/router) and avoids ambiguity.

Wildcard / Catch-All Routes

Wildcard segments (*) match all remaining path segments. They’re always the lowest priority at any tree level:

// Routes:
// GET /files/:id        → matches single segment after /files/
// GET /files/*path      → matches any depth after /files/

// GET /files/123        → matches /files/:id with id = "123"
// GET /files/a/b/c.txt  → matches /files/*path with path = "a/b/c.txt"

Wildcards capture the entire remaining path as a single string parameter. They cannot coexist with parameterized routes at the same depth — the build step will emit an error if this is detected.

Trailing Slash Handling

TypoKit normalizes trailing slashes at build time:

• /users and /users/ are treated as the same route
• The compiled tree stores the canonical form (without trailing slash)
• At runtime, incoming paths are normalized before tree lookup

// Route defined as: GET /users
// All of these match:
// GET /users     ✓
// GET /users/    ✓ (trailing slash stripped before lookup)

Note

Trailing slash normalization happens before the tree walk, not during it. This keeps the tree structure clean and the matching logic simple.

405 Method Not Allowed

When a path matches a node in the tree but the HTTP method isn’t registered on that node, the router returns 405 Method Not Allowed (not 404):

// Routes:
// GET  /users
// POST /users

// DELETE /users → 405 Method Not Allowed
// Response headers: Allow: GET, POST

The Allow header is populated from the matched node’s method registry — no additional lookup needed.

Overlapping Prefixes

The radix tree compression automatically handles overlapping prefixes efficiently:

// Routes:
// GET /api/users
// GET /api/users/:id
// GET /api/user-settings

// Tree structure:
// root
// └── api
//     └── user
//         ├── s ─────── [GET]         ← /api/users
//         │   └── :id ── [GET]       ← /api/users/:id
//         └── -settings ── [GET]     ← /api/user-settings

The shared prefix user is stored once, with branching only where paths diverge. This compression reduces memory usage and keeps the tree shallow.

Performance Targets

Metric	Target	Notes
Static route lookup	< 100ns	Direct tree walk with string comparison
Parameterized route lookup	< 200ns	Tree walk with parameter extraction
Wildcard route lookup	< 200ns	Tree walk to wildcard node + path capture
Route tree load time	< 1ms	Loading the compiled TypeScript module at startup
Method not allowed check	< 50ns	Hash map lookup on matched node
Memory (100 routes)	< 50KB	Compressed radix tree in memory
Memory (1000 routes)	< 200KB	Radix compression keeps growth sub-linear

Tip

These targets are for the runtime route matching only. Build-time route compilation in Rust typically completes in under 50ms for 100 routes — see the Build Pipeline performance targets for build-time metrics.

Benchmark Comparison

Router	Static lookup	Param lookup	Route registration
Express (linear scan)	~1–5μs	~2–10μs	Runtime
Fastify (find-my-way)	~100–200ns	~200–400ns	Runtime (startup)
Hono (RegExpRouter)	~50–150ns	~100–300ns	Runtime (startup)
TypoKit (compiled radix tree)	< 100ns	< 200ns	Build time (zero startup cost)

TypoKit matches or beats the fastest framework routers on lookup speed while eliminating startup registration cost entirely.

How Server Adapters Consume the Router

Each server adapter consumes the compiled router differently:

Native Server

// @typokit/server-native — uses the compiled radix tree directly
import { routeTree } from ".typokit/routes/compiled-router";
import { routeTable } from ".typokit/routes/route-table";

// The native server walks the tree on every request
// No translation layer — direct radix tree lookup
function matchRoute(method: string, path: string) {
  const segments = path.split("/").filter(Boolean);
  let node = routeTree.root;
  const params: Record<string, string> = {};

  for (const segment of segments) {
    // 1. Check static children first
    const staticChild = node.children.find(c => c.segment === segment);
    if (staticChild) { node = staticChild; continue; }

    // 2. Check parameterized children
    const paramChild = node.children.find(c => c.paramName);
    if (paramChild) {
      params[paramChild.paramName] = segment;
      node = paramChild;
      continue;
    }

    // 3. Check wildcard
    const wildcardChild = node.children.find(c => c.wildcard);
    if (wildcardChild) {
      params[wildcardChild.paramName] = segments.slice(segments.indexOf(segment)).join("/");
      return { ref: wildcardChild.methods[method]?.ref, params };
    }

    return null; // 404
  }

  if (!node.methods?.[method]) {
    // 405 — path matched but method didn't
    return { allowed: Object.keys(node.methods) };
  }

  return { ref: node.methods[method].ref, params };
}

Fastify Adapter

// @typokit/server-fastify — translates route table to Fastify registrations
import { routeTable } from ".typokit/routes/route-table";

// Fastify has its own radix tree (find-my-way)
// TypoKit translates the flat route table into Fastify-native routes
for (const [ref, entry] of Object.entries(routeTable)) {
  fastify.route({
    method: entry.method,
    url: entry.path,
    handler: async (request, reply) => {
      const typoReq = normalizeRequest(request);
      const typoRes = await middlewareChain.execute(typoReq, handlerMap[ref]);
      writeResponse(reply, typoRes);
    },
  });
}
// Fastify uses its own router — the compiled tree is not used directly

Hono Adapter

// @typokit/server-hono — translates route table to Hono registrations
import { routeTable } from ".typokit/routes/route-table";

// Hono has its own highly optimized router (RegExpRouter / TrieRouter)
// TypoKit registers routes using Hono's API
for (const [ref, entry] of Object.entries(routeTable)) {
  app.on(entry.method, entry.path, async (c) => {
    const typoReq = normalizeRequest(c.req);
    const typoRes = await middlewareChain.execute(typoReq, handlerMap[ref]);
    return writeResponse(c, typoRes);
  });
}
// Hono uses its own router — the compiled tree is not used directly

Note

Only @typokit/server-native uses the compiled radix tree directly. Other adapters (Fastify, Hono, Express) use the flat route table to register routes in the framework’s native format, relying on the framework’s own router for request matching.

Inspecting the Router

The CLI provides inspection commands for the compiled router:

# List all registered routes with their schemas
typokit inspect routes

# Inspect a single route's full metadata
typokit inspect route "GET /users/:id"

# Output (structured JSON):
# {
#   "method": "GET",
#   "path": "/users/:id",
#   "params": ["id"],
#   "responseSchema": "PublicUser",
#   "middleware": ["logging", "auth"],
#   "validators": [],
#   "treeDepth": 2
# }

The debug sidecar (when enabled) also exposes GET /_debug/routes which returns the full route tree and table as JSON — useful for AI agents diagnosing routing issues at runtime.

Summary

The compiled router is a core architectural decision in TypoKit:

• Build time (Rust): route_compiler.rs constructs a radix tree from route contracts, serializes it to TypeScript
• Runtime (TypeScript): Server adapters consume the tree (native) or flat table (Fastify/Hono/Express) for request matching
• O(k) lookup by path depth, independent of total route count
• Static > param > wildcard priority at each tree level
• Plain TypeScript output — inspectable by humans and AI agents alike