Route Matching Algorithms

Every client-side router answers one question on every navigation: given a URL pathname, which registered route owns it, and what parameter values does it carry? The data structure and traversal strategy you choose to answer that question — a list of compiled regular expressions, a prefix trie, or a compressed radix tree — decides whether resolution costs microseconds or stalls a frame. This page walks through the algorithms behind frontend route matching and gives you correct, framework-agnostic TypeScript you can drop into a custom router or use to reason about what your framework does internally.

← Back to Routing Architecture & Fundamentals

The Problem

A router that resolves routes incorrectly or slowly degrades the whole application in ways that are hard to attribute. The naive approach — iterate a flat array of patterns and return the first that matches — works for a dozen routes and quietly rots as the table grows. Three concrete failure surfaces appear.

First, ordering ambiguity. If /users/new and /users/:id both live in a flat list, the order they were registered in silently decides whether visiting /users/new renders the create form or treats new as a user identifier. A correct matcher ranks specificity (static beats dynamic beats wildcard) instead of trusting registration order.

Second, latency under scale. Linear scanning is O(n) in the number of routes, and each step may run a regular expression. With several hundred routes, resolution can creep past a single frame’s budget, and because matching often runs synchronously inside a popstate event handler during back/forward navigation, the cost lands directly on interaction responsiveness.

Third, catastrophic backtracking. Hand-written or generated regular expressions with nested quantifiers can take exponential time on adversarial input — a ReDoS that freezes the main thread. Path matching is the wrong place to discover this in production.

Underlying all three is a subtler design tension: flexibility versus determinism. Regular expressions buy you arbitrary pattern power — optional groups, alternations, lookahead — at the cost of unpredictable runtime behaviour and the need to compile them. Tree structures trade that expressiveness for predictable, prefix-driven traversal that is trivial to reason about and easy to validate at build time. Most production routers land somewhere in between, which is why understanding both ends of the spectrum lets you read what your framework actually does and intervene when its defaults stop fitting.

The matter is closely tied to how you model variable URL parts; the conventions on the Dynamic Route Segments page govern what your matcher must extract, and the broader SPA vs MPA tradeoffs decision determines whether this matching happens in the browser at all.

Core API & Primitives

Three building blocks recur across every matching strategy, regardless of the data structure underneath.

A compiled pattern turns a route definition string into something cheap to evaluate repeatedly. For the regex approach, that is a RegExp plus an ordered list of parameter names:

// TypeScript 5.x — framework-agnostic, no runtime dependencies
interface CompiledRoute {
  source: string;             // original definition, e.g. '/users/:id'
  regex: RegExp;              // anchored matcher
  keys: string[];            // ordered parameter names
  score: number;             // specificity rank for tie-breaking
}

interface MatchResult {
  routeId: string;
  params: Record<string, string>;
}

A segment classifier decides, per path fragment, whether it is a literal, a required parameter, an optional parameter, or a catch-all wildcard. This single function keeps the regex compiler and the trie builder in agreement:

// TypeScript 5.x — framework-agnostic
type SegmentKind =
  | { kind: 'literal'; value: string }
  | { kind: 'param'; name: string; optional: boolean }
  | { kind: 'wildcard'; name: string };

function classifySegment(segment: string): SegmentKind {
  if (segment === '*' || segment.startsWith('*')) {
    return { kind: 'wildcard', name: segment.slice(1) || 'rest' };
  }
  if (segment.startsWith(':')) {
    const optional = segment.endsWith('?');
    const name = segment.slice(1, optional ? -1 : undefined);
    return { kind: 'param', name, optional };
  }
  return { kind: 'literal', value: segment };
}

A specificity score breaks ties deterministically so registration order never decides a match. The convention below ranks a static segment above a dynamic one above a wildcard, weighting earlier segments more heavily so /users/new always outranks /users/:id:

// TypeScript 5.x — framework-agnostic
function scoreSegments(segments: SegmentKind[]): number {
  return segments.reduce((total, seg, index) => {
    const weight = 1 << Math.max(0, 16 - index); // earlier segments dominate
    const rank = seg.kind === 'literal' ? 3 : seg.kind === 'param' ? 2 : 1;
    return total + rank * weight;
  }, 0);
}

Step-by-Step Implementation

Prerequisite: an environment supporting ES2018 named capture groups (Chrome 64+, Safari 11.1+, Firefox 78+, Node 18+). The steps below build a regex-backed matcher first, then layer a trie for scale.

Step 1: Compile a route definition into a regex

Escape regex metacharacters in literal text, then replace parameter and wildcard tokens with named capture groups. Compile once at startup — never per navigation.

// TypeScript 5.x — framework-agnostic
function compileRoute(source: string, routeId: string): CompiledRoute & { routeId: string } {
  const keys: string[] = [];
  const segments = source.split('/').filter(Boolean).map(classifySegment);

  const body = segments.map(seg => {
    if (seg.kind === 'literal') {
      return '/' + seg.value.replace(/[.+^${}()|[\]\\?*]/g, '\\$&');
    }
    if (seg.kind === 'param') {
      keys.push(seg.name);
      return seg.optional ? `(?:/(?<${seg.name}>[^/]+))?` : `/(?<${seg.name}>[^/]+)`;
    }
    keys.push(seg.name);
    return `(?<${seg.name}>/.*)?`; // wildcard captures the remainder
  }).join('');

  return {
    routeId,
    source,
    keys,
    score: scoreSegments(segments),
    regex: new RegExp(`^${body || '/'}/?$`, 'i'), // tolerate trailing slash
  };
}

Step 2: Build a ranked table and match against it

Sort compiled routes by descending score once, then return the first match. Because the table is pre-ranked, the first match is guaranteed to be the most specific one.

// TypeScript 5.x — framework-agnostic
class RegexRouter {
  private routes: ReturnType<typeof compileRoute>[] = [];

  add(source: string, routeId: string): void {
    this.routes.push(compileRoute(source, routeId));
    this.routes.sort((a, b) => b.score - a.score); // most specific first
  }

  match(pathname: string): MatchResult | null {
    for (const route of this.routes) {
      const m = route.regex.exec(pathname);
      if (!m) continue;
      const params: Record<string, string> = {};
      for (const key of route.keys) {
        const raw = m.groups?.[key];
        if (raw !== undefined) params[key] = decodeURIComponent(raw.replace(/^\//, ''));
      }
      return { routeId: route.routeId, params };
    }
    return null;
  }
}

This is the pragmatic baseline; the dedicated walkthrough on regex route matching in vanilla JS covers the edge cases — duplicate parameter names, trailing-slash normalisation, and encoded segments — in finer detail.

Step 3: Swap the linear scan for a trie at scale

A flat regex table stays O(n). A trie keyed on path segments turns lookup into O(k), where k is the URL’s segment depth, by sharing common prefixes. Dynamic segments are stored under a single sentinel key so they never collide with literal names.

// TypeScript 5.x — framework-agnostic
interface TrieNode {
  children: Map<string, TrieNode>;
  param?: TrieNode;       // single dynamic branch
  paramName?: string;
  wildcard?: { node: TrieNode; name: string };
  routeId?: string;
}

class TrieRouter {
  private root: TrieNode = { children: new Map() };

  add(source: string, routeId: string): void {
    let node = this.root;
    for (const seg of source.split('/').filter(Boolean).map(classifySegment)) {
      if (seg.kind === 'literal') {
        node = getOrCreate(node.children, seg.value);
      } else if (seg.kind === 'param') {
        node.param ??= { children: new Map() };
        node.param.paramName = seg.name;
        node = node.param;
      } else {
        node.wildcard ??= { node: { children: new Map() }, name: seg.name };
        node = node.wildcard.node;
      }
    }
    node.routeId = routeId;
  }
}

function getOrCreate(map: Map<string, TrieNode>, key: string): TrieNode {
  let next = map.get(key);
  if (!next) { next = { children: new Map() }; map.set(key, next); }
  return next;
}

Step 4: Traverse the trie with static-first precedence

At each segment, try the literal child before the parameter branch before the wildcard. This bakes specificity into the traversal itself, so no separate scoring pass is needed at match time.

// TypeScript 5.x — framework-agnostic
function trieMatch(root: TrieNode, pathname: string): MatchResult | null {
  const segments = pathname.split('/').filter(Boolean);
  const params: Record<string, string> = {};

  function walk(node: TrieNode, i: number): TrieNode | null {
    if (i === segments.length) return node.routeId ? node : null;
    const seg = segments[i];

    const literal = node.children.get(seg);
    if (literal) { const r = walk(literal, i + 1); if (r) return r; }

    if (node.param) {
      const r = walk(node.param, i + 1);
      if (r) { params[node.param.paramName!] = decodeURIComponent(seg); return r; }
    }

    if (node.wildcard) {
      params[node.wildcard.name] = segments.slice(i).map(decodeURIComponent).join('/');
      return node.wildcard.node.routeId ? node.wildcard.node : null;
    }
    return null;
  }

  const hit = walk(root, 0);
  return hit?.routeId ? { routeId: hit.routeId, params } : null;
}

Backtracking into the param branch only happens when the literal child fails to lead to a terminal route, which keeps the common case — a clean literal path — linear in depth.

Verification & Testing

Match correctness is best pinned down with a table of expected resolutions, then exercised through real navigation so you also catch integration bugs with the History API. The Playwright snippet below drives back/forward navigation and asserts the resolved route and params your router exposes on window.

// Playwright 1.4x — end-to-end navigation assertions
import { test, expect } from '@playwright/test';

const cases: [string, string, Record<string, string>][] = [
  ['/users/new', 'users.create', {}],
  ['/users/42', 'users.detail', { id: '42' }],
  ['/files/a/b/c', 'files.catchAll', { rest: 'a/b/c' }],
];

test('matcher resolves the most specific route', async ({ page }) => {
  await page.goto('/');
  for (const [path, routeId, params] of cases) {
    const result = await page.evaluate(p => window.__router.match(p), path);
    expect(result?.routeId).toBe(routeId);
    expect(result?.params).toEqual(params);
  }
});

test('back navigation re-resolves via popstate', async ({ page }) => {
  await page.goto('/users/42');
  await page.goto('/users/new');
  await page.goBack();
  await expect(page).toHaveURL(/\/users\/42$/);
});

For ad-hoc inspection without a full harness, paste the matcher into a DevTools console and run console.table(['/users/new', '/users/42'].map(p => router.match(p))) to see resolutions side by side.

Performance Tuning

Treat matcher latency as a measurable budget, not a feeling. Wrap resolution in the User Timing API so a single frame’s worth of work shows up in the Performance panel:

// TypeScript 5.x — User Timing API (Chrome 88+, Firefox 88+, Safari 15.4+)
function timedMatch(router: { match(p: string): MatchResult | null }, path: string) {
  performance.mark('match:start');
  const result = router.match(path);
  performance.measure('route-match', 'match:start');
  const { duration } = performance.getEntriesByName('route-match').at(-1)!;
  if (duration > 0.5) console.warn(`Slow match for ${path}: ${duration.toFixed(2)}ms`);
  return result;
}

Concrete optimisations, in rough order of impact:

  • Compile once. Build every RegExp or trie node at startup, never inside a navigation handler. Re-compilation per navigation is the single most common cause of inflated INP in hand-rolled routers.
  • Switch structures by size. Below roughly 100 routes a ranked regex table is fine and simplest. Past that, a trie’s O(k) traversal pulls measurably ahead because it stops touching routes that share no prefix with the request.
  • Cache resolved paths with a bounded LRU. Memoising pathname → MatchResult removes repeat work on revisited URLs, but an unbounded cache leaks heap in long-lived applications; cap it and evict.
  • Defer rarely hit branches. Pair the matcher with route-level code splitting so the modules behind seldom-visited routes never enter the initial bundle, keeping first-load parse cost down.

Gotchas & Failure Modes

  • Registration order masquerading as precedence. Without a specificity score, /users/:id registered before /users/new swallows the literal route. Always rank, or traverse literal-first.
  • Catastrophic regex backtracking. Nested quantifiers like (.+)+ on a non-matching input take exponential time and freeze the thread. Constrain parameter captures to [^/]+ and avoid nesting greedy groups.
  • Trailing-slash inconsistency. /about and /about/ resolving differently produces phantom duplicate URLs. Normalise the pathname before matching, or anchor the regex with /?$ as shown above.
  • Dynamic-segment key collisions in tries. Storing a parameter under its literal name (:id) lets a route literally named :id clash with every dynamic branch. Use one sentinel branch per node for all parameters.
  • Forgetting to decode. Raw capture groups contain percent-encoded bytes; a param of caf%C3%A9 must be decodeURIComponent-ed before it reaches components, or downstream lookups silently miss.
  • Unbounded match cache. An LRU without a size cap turns a performance optimisation into a slow memory leak in a session that never reloads.

Go Deeper