Bug report (typescript repo "router"):
2 findings from this week's triage. They have separate causes and are not related to one another; all 2 need fixing.

1. A bug in one of our middlewares corrupted a whole batch of requests before we
   noticed, and the router gave us no signal at all.
   The middleware in question awaited next(), then on a certain branch called
   next() a second time. Everything below it in the stack ran twice against the
   same request -- including a layer that charges a payment. We only found it from
   the duplicate charges.
   Running the remainder of the stack twice for one request is never correct.
   The composed handler should refuse it rather than quietly do it.

2. Content negotiation ignores what the client asked for first.
   A client sending `Accept: text/html, application/json` -- no explicit
   qualities, so both are equally acceptable -- gets JSON back. Per the spec, when
   two acceptable types carry the same quality, the client's own ordering is the
   tie-break, so that request should be served HTML.
   Requests that state explicit differing q-values are handled correctly; it is
   only ties that come out wrong. Please fix.

Repository files (containing the defects):
README.md: # router

A small HTTP router: pattern matching, middleware composition, and the bits of
header/query handling a router needs.

```ts
import { Router } from './src/index.ts';

const router = new Router();
router.add('GET', '/users/:id', async (req) => ({ status: 200, body: String(req.params.id) }));
router.add('GET', '/users/me', async () => ({ status: 200, body: 'self' }));

router.resolve('GET', '/users/me')?.pattern;   // '/users/me' -- static beats param
router.resolve('GET', '/users/42')?.params;    // { id: '42' }
```

## Layout

| module | role |
|---|---|
| `router.ts` | method-aware routing, with a cache of resolved paths |
| `trie.ts` | the route table: collects matches, orders them by specificity |
| `matcher.ts` | pattern parsing and the specificity ranking |
| `middleware.ts` | composition of a middleware stack |
| `params.ts` | coercion of raw path parameters |
| `query.ts` | query-string parsing, including repeated keys |
| `headers.ts` | case-insensitive header storage |
| `negotiate.ts` | Accept-header content negotiation |
| `cache.ts` | LRU used for compiled routes |
| `url.ts` | path splitting and normalisation |
| `errors.ts` | error types |
| `types.ts` | shared request/response shapes |

## Design notes

**Specificity, not registration order.** Every route that matches is collected
and the most specific wins, compared segment by segment from the left: static
beats parameter beats wildcard. Two routers given the same routes in different
orders resolve identically.

**Recency means use.** The route cache is LRU by *access*, so reading an entry
makes it the newest. A hot route is never the eviction candidate.

**Client preference breaks ties.** In content negotiation, equal quality values
are resolved in the order the client listed them.

**Case-insensitive fields.** Header names are stored and looked up lower-cased,
as HTTP requires; values keep their case.

src/cache.ts: /**
 * A least-recently-used cache for compiled routes.
 *
 * Recency is defined by *use*, not by insertion: reading an entry makes it the
 * most recently used one, so a hot entry is never the eviction candidate no
 * matter how long ago it was first stored.
 */
export class LruCache<K, V> {
  private readonly store = new Map<K, V>();
  readonly capacity: number;
  hits = 0;
  misses = 0;

  constructor(capacity: number) {
    if (capacity <= 0) throw new RangeError('cache capacity must be positive');
    this.capacity = capacity;
  }

  get(key: K): V | undefined {
    if (!this.store.has(key)) {
      this.misses++;
      return undefined;
    }
    const value = this.store.get(key) as V;
    // reinsert so this key becomes the newest in iteration order
    this.store.delete(key);
    this.store.set(key, value);
    this.hits++;
    return value;
  }

  set(key: K, value: V): void {
    if (this.store.has(key)) this.store.delete(key);
    this.store.set(key, value);
    while (this.store.size > this.capacity) {
      const oldest = this.store.keys().next();
      if (oldest.done) break;
      this.store.delete(oldest.value);
    }
  }

  has(key: K): boolean {
    return this.store.has(key);
  }

  get size(): number {
    return this.store.size;
  }

  keys(): K[] {
    return [...this.store.keys()];
  }

  clear(): void {
    this.store.clear();
    this.hits = 0;
    this.misses = 0;
  }
}

src/errors.ts: export class RouterError extends Error {
  constructor(message: string) {
    super(message);
    this.name = new.target.name;
  }
}

export class InvalidPattern extends RouterError {
  readonly pattern: string;
  constructor(pattern: string, reason: string) {
    super(`invalid route pattern ${JSON.stringify(pattern)}: ${reason}`);
    this.pattern = pattern;
  }
}

export class DuplicateRoute extends RouterError {
  readonly pattern: string;
  constructor(pattern: string) {
    super(`route already registered: ${pattern}`);
    this.pattern = pattern;
  }
}

export class CoercionError extends RouterError {
  readonly name_: string;
  readonly raw: string;
  constructor(name: string, raw: string, kind: string) {
    super(`parameter ${name} = ${JSON.stringify(raw)} is not a valid ${kind}`);
    this.name_ = name;
    this.raw = raw;
  }
}

src/headers.ts: /**
 * Header handling.
 *
 * HTTP field names are case-insensitive, so everything is stored lower-cased
 * and looked up the same way. Values keep their original case.
 */
export class Headers {
  private readonly store = new Map<string, string[]>();

  constructor(initial?: Record<string, string | string[]>) {
    if (initial) {
      for (const [name, value] of Object.entries(initial)) this.set(name, value);
    }
  }

  private static key(name: string): string {
    return name.toLowerCase();
  }

  set(name: string, value: string | string[]): void {
    this.store.set(Headers.key(name), Array.isArray(value) ? [...value] : [value]);
  }

  append(name: string, value: string): void {
    const key = Headers.key(name);
    const existing = this.store.get(key);
    if (existing) existing.push(value);
    else this.store.set(key, [value]);
  }

  get(name: string): string | undefined {
    return this.store.get(Headers.key(name))?.[0];
  }

  all(name: string): string[] {
    return [...(this.store.get(Headers.key(name)) ?? [])];
  }

  has(name: string): boolean {
    return this.store.has(Headers.key(name));
  }

  delete(name: string): boolean {
    return this.store.delete(Headers.key(name));
  }

  names(): string[] {
    return [...this.store.keys()].sort();
  }
}

src/index.ts: export { Router } from './router.ts';
export type { Resolved } from './router.ts';
export { RouteTable } from './trie.ts';
export type { Route, Match } from './trie.ts';
export { compose } from './middleware.ts';
export type { Middleware, Next } from './middleware.ts';
export { Headers } from './headers.ts';
export { LruCache } from './cache.ts';
export { parseQuery, first } from './query.ts';
export { parseAccept, selectType } from './negotiate.ts';
export type { Candidate } from './negotiate.ts';
export { coerce, coerceInt, coerceAll } from './params.ts';
export type { ParamValue } from './params.ts';
export { parsePattern, specificity, compareSpecificity } from './matcher.ts';
export type { PatternSegment, SegmentKind } from './matcher.ts';
export { segments, decodeSegment, normalise, joinPath } from './url.ts';
export { RouterError, InvalidPattern, DuplicateRoute, CoercionError } from './errors.ts';
export type { Request, Response, Handler } from './types.ts';

src/matcher.ts: import { InvalidPattern } from './errors.ts';
import { segments } from './url.ts';

export type SegmentKind = 'static' | 'param' | 'wildcard';

export interface PatternSegment {
  readonly kind: SegmentKind;
  /** literal text for static segments, parameter name otherwise */
  readonly value: string;
}

/**
 * Parse a route pattern into segments.
 *
 *   /users/:id      -> static 'users', param 'id'
 *   /files/*rest    -> static 'files', wildcard 'rest'
 *
 * A wildcard consumes the remainder of the path and may therefore only appear
 * as the final segment.
 */
export function parsePattern(pattern: string): PatternSegment[] {
  const parts = segments(pattern);
  const out: PatternSegment[] = [];

  parts.forEach((part, index) => {
    if (part.startsWith(':')) {
      const name = part.slice(1);
      if (name.length === 0) throw new InvalidPattern(pattern, 'empty parameter name');
      out.push({ kind: 'param', value: name });
      return;
    }
    if (part.startsWith('*')) {
      const name = part.slice(1) || 'wildcard';
      if (index !== parts.length - 1) {
        throw new InvalidPattern(pattern, 'wildcard must be the last segment');
      }
      out.push({ kind: 'wildcard', value: name });
      return;
    }
    out.push({ kind: 'static', value: part });
  });

  return out;
}

/**
 * Specificity of a pattern, used to order competing routes.
 *
 * A static segment is more specific than a parameter, which is more specific
 * than a wildcard. Comparing segment by segment from the left means
 * /users/me wins over /users/:id, which in turn wins over /users/*rest.
 */
export function specificity(pattern: PatternSegment[]): number[] {
  const rank: Record<SegmentKind, number> = { static: 2, param: 1, wildcard: 0 };
  return pattern.map((segment) => rank[segment.kind]);
}

/** Compare two specificity vectors. Positive means `a` is more specific. */
export function compareSpecificity(a: number[], b: number[]): number {
  const length = Math.max(a.length, b.length);
  for (let i = 0; i < length; i++) {
    const left = a[i] ?? -1;
    const right = b[i] ?? -1;
    if (left !== right) return left - right;
  }
  return 0;
}

src/middleware.ts: import type { Request, Response } from './types.ts';

export type Next = () => Promise<Response>;
export type Middleware = (request: Request, next: Next) => Promise<Response>;

/**
 * Compose middleware into a single handler.
 *
 * The first entry is outermost: it sees the request first and the response
 * last. Each layer must call `next` at most once; calling it twice would run
 * the rest of the stack again against the same request.
 */
export function compose(layers: Middleware[]): Middleware {
  return function composed(request: Request, final: Next): Promise<Response> {
    function dispatch(index: number): Promise<Response> {
      if (index === layers.length) return final();
      const layer = layers[index];
      return layer(request, () => dispatch(index + 1));
    }

    return dispatch(0);
  };
}

src/negotiate.ts: /**
 * Content negotiation over an Accept header.
 *
 * Each candidate carries an optional quality between 0 and 1, defaulting to 1.
 * A q of 0 means "not acceptable" and is never selected. Where qualities tie,
 * the order the client listed them in wins, because that is the client's own
 * statement of preference.
 */
export interface Candidate {
  readonly type: string;
  readonly quality: number;
  readonly order: number;
}

export function parseAccept(header: string): Candidate[] {
  const out: Candidate[] = [];
  header.split(',').forEach((part, order) => {
    const pieces = part.trim().split(';');
    const type = pieces[0].trim();
    if (type.length === 0) return;
    let quality = 1;
    for (const piece of pieces.slice(1)) {
      const [name, value] = piece.split('=').map((s) => s.trim());
      if (name === 'q') {
        const parsed = Number(value);
        quality = Number.isFinite(parsed) ? parsed : 1;
      }
    }
    out.push({ type, quality, order });
  });
  return out;
}

/** Pick the best offered type, or undefined when nothing is acceptable. */
export function selectType(header: string, offered: string[]): string | undefined {
  const candidates = parseAccept(header)
    .filter((c) => c.quality > 0)
    .sort((a, b) => b.quality - a.quality || a.type.localeCompare(b.type));
  let best: Candidate | undefined;

  for (const candidate of candidates) {
    if (!matchesAny(candidate.type, offered)) continue;
    if (best === undefined) best = candidate;
  }

  if (best === undefined) return undefined;
  return offered.find((type) => matches(best.type, type));
}

function matches(pattern: string, type: string): boolean {
  if (pattern === '*/*') return true;
  if (pattern === type) return true;
  const [group] = pattern.split('/');
  return pattern.endsWith('/*') && type.startsWith(group + '/');
}

function matchesAny(pattern: string, offered: string[]): boolean {
  return offered.some((type) => matches(pattern, type));
}

src/params.ts: import { CoercionError } from './errors.ts';

export type ParamValue = string | number | boolean;

/**
 * Coerce a raw path parameter.
 *
 * Only the exact strings 'true' and 'false' are booleans; anything else that
 * looks numeric becomes a number, and everything else stays a string. The
 * string '0' is therefore the number 0, not false -- a route parameter of
 * /items/0 must address item zero.
 */
export function coerce(name: string, raw: string): ParamValue {
  if (raw === 'true') return true;
  if (raw === 'false') return false;
  if (raw.length > 0 && Number.isFinite(Number(raw))) return Number(raw);
  return raw;
}

export function coerceInt(name: string, raw: string): number {
  const value = Number(raw);
  if (!Number.isInteger(value)) throw new CoercionError(name, raw, 'integer');
  return value;
}

export function coerceAll(raw: Record<string, string>): Record<string, ParamValue> {
  const out: Record<string, ParamValue> = {};
  for (const [name, value] of Object.entries(raw)) out[name] = coerce(name, value);
  return out;
}

src/query.ts: /**
 * Query-string parsing.
 *
 * A key that appears more than once collects every value in order, so
 * `?tag=a&tag=b` yields both. A key with no `=` is present with an empty
 * value, which is how flags like `?verbose` are expressed.
 */
export function parseQuery(raw: string): Record<string, string[]> {
  const out: Record<string, string[]> = {};
  const text = raw.startsWith('?') ? raw.slice(1) : raw;
  if (text.length === 0) return out;

  for (const pair of text.split('&')) {
    if (pair.length === 0) continue;
    const index = pair.indexOf('=');
    const rawKey = index === -1 ? pair : pair.slice(0, index);
    const rawValue = index === -1 ? '' : pair.slice(index + 1);
    const key = safeDecode(rawKey);
    const value = safeDecode(rawValue.replace(/\+/g, ' '));
    if (key.length === 0) continue;
    if (out[key]) out[key].push(value);
    else out[key] = [value];
  }
  return out;
}

function safeDecode(raw: string): string {
  try {
    return decodeURIComponent(raw);
  } catch {
    return raw;
  }
}

/** The first value for a key, or undefined when the key is absent. */
export function first(query: Record<string, string[]>, key: string): string | undefined {
  return query[key]?.[0];
}

src/router.ts: import { LruCache } from './cache.ts';
import { DuplicateRoute } from './errors.ts';
import { coerceAll } from './params.ts';
import { RouteTable } from './trie.ts';
import type { Match } from './trie.ts';
import { normalise } from './url.ts';
import type { Handler } from './types.ts';

export interface Resolved {
  readonly handler: Handler;
  readonly params: Record<string, string>;
  readonly pattern: string;
}

/** Method-aware router with a small cache of resolved paths. */
export class Router {
  private readonly tables = new Map<string, RouteTable<Handler>>();
  private readonly cache: LruCache<string, Resolved | null>;

  constructor(cacheSize = 128) {
    this.cache = new LruCache<string, Resolved | null>(cacheSize);
  }

  private tableFor(method: string): RouteTable<Handler> {
    const key = method.toUpperCase();
    let table = this.tables.get(key);
    if (!table) {
      table = new RouteTable<Handler>();
      this.tables.set(key, table);
    }
    return table;
  }

  add(method: string, pattern: string, handler: Handler): void {
    const table = this.tableFor(method);
    const canonical = normalise(pattern);
    if (table.patterns().some((existing) => normalise(existing) === canonical)) {
      throw new DuplicateRoute(pattern);
    }
    table.add(pattern, handler);
    this.cache.clear();
  }

  resolve(method: string, path: string): Resolved | undefined {
    const key = `${method.toUpperCase()} ${normalise(path)}`;
    const cached = this.cache.get(key);
    if (cached !== undefined) return cached ?? undefined;

    const table = this.tables.get(method.toUpperCase());
    const match: Match<Handler> | undefined = table?.match(path);
    const resolved: Resolved | null = match
      ? { handler: match.route.value, params: match.params, pattern: match.route.pattern }
      : null;
    this.cache.set(key, resolved);
    return resolved ?? undefined;
  }

  params(method: string, path: string): Record<string, unknown> {
    const resolved = this.resolve(method, path);
    return resolved ? coerceAll(resolved.params) : {};
  }

  methods(): string[] {
    return [...this.tables.keys()].sort();
  }
}

src/trie.ts: import { compareSpecificity, parsePattern, specificity } from './matcher.ts';
import type { PatternSegment } from './matcher.ts';
import { decodeSegment, segments } from './url.ts';

export interface Route<T> {
  readonly pattern: string;
  readonly parsed: PatternSegment[];
  readonly rank: number[];
  readonly value: T;
}

export interface Match<T> {
  readonly route: Route<T>;
  readonly params: Record<string, string>;
}

/**
 * Route table.
 *
 * Every registered route that matches a path is collected, then the most
 * specific one wins. Registration order never decides a match -- two routers
 * given the same routes in different orders must resolve identically.
 */
export class RouteTable<T> {
  private readonly routes: Route<T>[] = [];

  add(pattern: string, value: T): Route<T> {
    const parsed = parsePattern(pattern);
    const route: Route<T> = { pattern, parsed, rank: specificity(parsed), value };
    this.routes.push(route);
    return route;
  }

  get size(): number {
    return this.routes.length;
  }

  patterns(): string[] {
    return this.routes.map((route) => route.pattern);
  }

  /** Every route matching `path`, most specific first. */
  matchAll(path: string): Match<T>[] {
    const parts = segments(path).map(decodeSegment);
    const found: Match<T>[] = [];

    for (const route of this.routes) {
      const params = tryMatch(route.parsed, parts);
      if (params !== undefined) found.push({ route, params });
    }

    found.sort((a, b) => {
      const bySpecificity = compareSpecificity(b.route.rank, a.route.rank);
      if (bySpecificity !== 0) return bySpecificity;
      return a.route.pattern.localeCompare(b.route.pattern);
    });
    return found;
  }

  match(path: string): Match<T> | undefined {
    return this.matchAll(path)[0];
  }
}

function tryMatch(
  pattern: PatternSegment[],
  parts: string[],
): Record<string, string> | undefined {
  const params: Record<string, string> = {};

  for (let i = 0; i < pattern.length; i++) {
    const segment = pattern[i];
    if (segment.kind === 'wildcard') {
      params[segment.value] = parts.slice(i).join('/');
      return params;
    }
    if (i >= parts.length) return undefined;
    if (segment.kind === 'static') {
      if (segment.value !== parts[i]) return undefined;
      continue;
    }
    params[segment.value] = parts[i];
  }

  return pattern.length === parts.length ? params : undefined;
}

src/types.ts: import type { Headers } from './headers.ts';
import type { ParamValue } from './params.ts';

export interface Request {
  readonly method: string;
  readonly path: string;
  readonly query: Record<string, string[]>;
  readonly headers: Headers;
  readonly params: Record<string, ParamValue>;
}

export interface Response {
  readonly status: number;
  readonly body: string;
}

export type Handler = (request: Request) => Promise<Response>;

src/url.ts: /** Path helpers. Paths are compared as a list of decoded segments. */

/** Split a path into segments, ignoring leading, trailing and repeated slashes. */
export function segments(path: string): string[] {
  return path.split('/').filter((part) => part.length > 0);
}

/** Percent-decode a single segment, leaving it untouched if it is malformed. */
export function decodeSegment(raw: string): string {
  try {
    return decodeURIComponent(raw);
  } catch {
    return raw;
  }
}

/** Normalise a path to a canonical leading-slash, no-trailing-slash form. */
export function normalise(path: string): string {
  const parts = segments(path);
  return parts.length === 0 ? '/' : '/' + parts.join('/');
}

export function joinPath(...parts: string[]): string {
  return normalise(parts.join('/'));
}


Hidden tests:
tests/middleware.test.ts: 
import { test } from 'node:test';
import assert from 'node:assert';
import { compose } from '../src/index.ts';
import type { Middleware } from '../src/index.ts';

const REQ = {} as any;
const OK = async () => ({ status: 200, body: 'ok' });

test('calling next twice is rejected', async () => {
  const twice: Middleware = async (_r, next) => {
    await next();
    return next();
  };
  await assert.rejects(() => compose([twice])(REQ, OK));
});

test('downstream runs only once per request', async () => {
  let runs = 0;
  const counter: Middleware = async (_r, next) => { runs++; return next(); };
  const twice: Middleware = async (_r, next) => {
    await next();
    try { await next(); } catch { /* expected */ }
    return { status: 200, body: '' };
  };
  await compose([twice, counter])(REQ, OK);
  assert.strictEqual(runs, 1);
});

test('final handler runs only once', async () => {
  let finals = 0;
  const twice: Middleware = async (_r, next) => {
    await next();
    try { await next(); } catch { /* expected */ }
    return { status: 200, body: '' };
  };
  await compose([twice])(REQ, async () => { finals++; return { status: 200, body: '' }; });
  assert.strictEqual(finals, 1);
});

test('ordinary stacks still work end to end', async () => {
  const seen: string[] = [];
  const mk = (name: string): Middleware => async (_r, next) => {
    seen.push(name + '-in');
    const res = await next();
    seen.push(name + '-out');
    return res;
  };
  const res = await compose([mk('a'), mk('b'), mk('c')])(REQ, OK);
  assert.strictEqual(res.body, 'ok');
  assert.deepStrictEqual(seen, ['a-in','b-in','c-in','c-out','b-out','a-out']);
});

test('empty stack calls the final handler', async () => {
  assert.strictEqual((await compose([])(REQ, OK)).body, 'ok');
});

test('a layer may short-circuit without calling next', async () => {
  const stop: Middleware = async () => ({ status: 403, body: 'no' });
  let reached = false;
  const after: Middleware = async (_r, next) => { reached = true; return next(); };
  const res = await compose([stop, after])(REQ, OK);
  assert.strictEqual(res.status, 403);
  assert.strictEqual(reached, false);
});

test('errors propagate', async () => {
  const boom: Middleware = async () => { throw new Error('boom'); };
  await assert.rejects(() => compose([boom])(REQ, OK), /boom/);
});

tests/negotiate.test.ts: 
import { test } from 'node:test';
import assert from 'node:assert';
import { selectType, parseAccept } from '../src/index.ts';

const OFFER = ['text/html', 'application/json'];

test('equal quality is broken by client order', () => {
  assert.strictEqual(selectType('text/html, application/json', OFFER), 'text/html');
  assert.strictEqual(selectType('application/json, text/html', OFFER), 'application/json');
});

test('explicit equal q values also use client order', () => {
  assert.strictEqual(selectType('application/json;q=0.8, text/html;q=0.8', OFFER),
                     'application/json');
});

test('client order beats alphabetical order', () => {
  assert.strictEqual(selectType('text/html, application/json', OFFER), 'text/html');
});

test('three-way tie takes the first listed', () => {
  const offer = ['text/plain', 'text/html', 'application/json'];
  assert.strictEqual(selectType('text/plain, text/html, application/json', offer),
                     'text/plain');
});

test('higher quality still wins over order', () => {
  assert.strictEqual(selectType('text/html;q=0.2, application/json;q=0.9', OFFER),
                     'application/json');
  assert.strictEqual(selectType('application/json;q=0.1, text/html;q=0.7', OFFER),
                     'text/html');
});

test('zero quality is never selected', () => {
  assert.strictEqual(selectType('text/html;q=0', ['text/html']), undefined);
});

test('wildcards still match', () => {
  assert.strictEqual(selectType('*/*', ['text/html']), 'text/html');
  assert.strictEqual(selectType('text/*', ['text/html']), 'text/html');
});

test('nothing acceptable yields undefined', () => {
  assert.strictEqual(selectType('image/png', OFFER), undefined);
});

test('parseAccept still records order and quality', () => {
  const parsed = parseAccept('a/b;q=0.5, c/d');
  assert.strictEqual(parsed[0].quality, 0.5);
  assert.strictEqual(parsed[1].order, 1);
});


Reference fix:
README.md: # router

A small HTTP router: pattern matching, middleware composition, and the bits of
header/query handling a router needs.

```ts
import { Router } from './src/index.ts';

const router = new Router();
router.add('GET', '/users/:id', async (req) => ({ status: 200, body: String(req.params.id) }));
router.add('GET', '/users/me', async () => ({ status: 200, body: 'self' }));

router.resolve('GET', '/users/me')?.pattern;   // '/users/me' -- static beats param
router.resolve('GET', '/users/42')?.params;    // { id: '42' }
```

## Layout

| module | role |
|---|---|
| `router.ts` | method-aware routing, with a cache of resolved paths |
| `trie.ts` | the route table: collects matches, orders them by specificity |
| `matcher.ts` | pattern parsing and the specificity ranking |
| `middleware.ts` | composition of a middleware stack |
| `params.ts` | coercion of raw path parameters |
| `query.ts` | query-string parsing, including repeated keys |
| `headers.ts` | case-insensitive header storage |
| `negotiate.ts` | Accept-header content negotiation |
| `cache.ts` | LRU used for compiled routes |
| `url.ts` | path splitting and normalisation |
| `errors.ts` | error types |
| `types.ts` | shared request/response shapes |

## Design notes

**Specificity, not registration order.** Every route that matches is collected
and the most specific wins, compared segment by segment from the left: static
beats parameter beats wildcard. Two routers given the same routes in different
orders resolve identically.

**Recency means use.** The route cache is LRU by *access*, so reading an entry
makes it the newest. A hot route is never the eviction candidate.

**Client preference breaks ties.** In content negotiation, equal quality values
are resolved in the order the client listed them.

**Case-insensitive fields.** Header names are stored and looked up lower-cased,
as HTTP requires; values keep their case.

src/cache.ts: /**
 * A least-recently-used cache for compiled routes.
 *
 * Recency is defined by *use*, not by insertion: reading an entry makes it the
 * most recently used one, so a hot entry is never the eviction candidate no
 * matter how long ago it was first stored.
 */
export class LruCache<K, V> {
  private readonly store = new Map<K, V>();
  readonly capacity: number;
  hits = 0;
  misses = 0;

  constructor(capacity: number) {
    if (capacity <= 0) throw new RangeError('cache capacity must be positive');
    this.capacity = capacity;
  }

  get(key: K): V | undefined {
    if (!this.store.has(key)) {
      this.misses++;
      return undefined;
    }
    const value = this.store.get(key) as V;
    // reinsert so this key becomes the newest in iteration order
    this.store.delete(key);
    this.store.set(key, value);
    this.hits++;
    return value;
  }

  set(key: K, value: V): void {
    if (this.store.has(key)) this.store.delete(key);
    this.store.set(key, value);
    while (this.store.size > this.capacity) {
      const oldest = this.store.keys().next();
      if (oldest.done) break;
      this.store.delete(oldest.value);
    }
  }

  has(key: K): boolean {
    return this.store.has(key);
  }

  get size(): number {
    return this.store.size;
  }

  keys(): K[] {
    return [...this.store.keys()];
  }

  clear(): void {
    this.store.clear();
    this.hits = 0;
    this.misses = 0;
  }
}

src/errors.ts: export class RouterError extends Error {
  constructor(message: string) {
    super(message);
    this.name = new.target.name;
  }
}

export class InvalidPattern extends RouterError {
  readonly pattern: string;
  constructor(pattern: string, reason: string) {
    super(`invalid route pattern ${JSON.stringify(pattern)}: ${reason}`);
    this.pattern = pattern;
  }
}

export class DuplicateRoute extends RouterError {
  readonly pattern: string;
  constructor(pattern: string) {
    super(`route already registered: ${pattern}`);
    this.pattern = pattern;
  }
}

export class CoercionError extends RouterError {
  readonly name_: string;
  readonly raw: string;
  constructor(name: string, raw: string, kind: string) {
    super(`parameter ${name} = ${JSON.stringify(raw)} is not a valid ${kind}`);
    this.name_ = name;
    this.raw = raw;
  }
}

src/headers.ts: /**
 * Header handling.
 *
 * HTTP field names are case-insensitive, so everything is stored lower-cased
 * and looked up the same way. Values keep their original case.
 */
export class Headers {
  private readonly store = new Map<string, string[]>();

  constructor(initial?: Record<string, string | string[]>) {
    if (initial) {
      for (const [name, value] of Object.entries(initial)) this.set(name, value);
    }
  }

  private static key(name: string): string {
    return name.toLowerCase();
  }

  set(name: string, value: string | string[]): void {
    this.store.set(Headers.key(name), Array.isArray(value) ? [...value] : [value]);
  }

  append(name: string, value: string): void {
    const key = Headers.key(name);
    const existing = this.store.get(key);
    if (existing) existing.push(value);
    else this.store.set(key, [value]);
  }

  get(name: string): string | undefined {
    return this.store.get(Headers.key(name))?.[0];
  }

  all(name: string): string[] {
    return [...(this.store.get(Headers.key(name)) ?? [])];
  }

  has(name: string): boolean {
    return this.store.has(Headers.key(name));
  }

  delete(name: string): boolean {
    return this.store.delete(Headers.key(name));
  }

  names(): string[] {
    return [...this.store.keys()].sort();
  }
}

src/index.ts: export { Router } from './router.ts';
export type { Resolved } from './router.ts';
export { RouteTable } from './trie.ts';
export type { Route, Match } from './trie.ts';
export { compose } from './middleware.ts';
export type { Middleware, Next } from './middleware.ts';
export { Headers } from './headers.ts';
export { LruCache } from './cache.ts';
export { parseQuery, first } from './query.ts';
export { parseAccept, selectType } from './negotiate.ts';
export type { Candidate } from './negotiate.ts';
export { coerce, coerceInt, coerceAll } from './params.ts';
export type { ParamValue } from './params.ts';
export { parsePattern, specificity, compareSpecificity } from './matcher.ts';
export type { PatternSegment, SegmentKind } from './matcher.ts';
export { segments, decodeSegment, normalise, joinPath } from './url.ts';
export { RouterError, InvalidPattern, DuplicateRoute, CoercionError } from './errors.ts';
export type { Request, Response, Handler } from './types.ts';

src/matcher.ts: import { InvalidPattern } from './errors.ts';
import { segments } from './url.ts';

export type SegmentKind = 'static' | 'param' | 'wildcard';

export interface PatternSegment {
  readonly kind: SegmentKind;
  /** literal text for static segments, parameter name otherwise */
  readonly value: string;
}

/**
 * Parse a route pattern into segments.
 *
 *   /users/:id      -> static 'users', param 'id'
 *   /files/*rest    -> static 'files', wildcard 'rest'
 *
 * A wildcard consumes the remainder of the path and may therefore only appear
 * as the final segment.
 */
export function parsePattern(pattern: string): PatternSegment[] {
  const parts = segments(pattern);
  const out: PatternSegment[] = [];

  parts.forEach((part, index) => {
    if (part.startsWith(':')) {
      const name = part.slice(1);
      if (name.length === 0) throw new InvalidPattern(pattern, 'empty parameter name');
      out.push({ kind: 'param', value: name });
      return;
    }
    if (part.startsWith('*')) {
      const name = part.slice(1) || 'wildcard';
      if (index !== parts.length - 1) {
        throw new InvalidPattern(pattern, 'wildcard must be the last segment');
      }
      out.push({ kind: 'wildcard', value: name });
      return;
    }
    out.push({ kind: 'static', value: part });
  });

  return out;
}

/**
 * Specificity of a pattern, used to order competing routes.
 *
 * A static segment is more specific than a parameter, which is more specific
 * than a wildcard. Comparing segment by segment from the left means
 * /users/me wins over /users/:id, which in turn wins over /users/*rest.
 */
export function specificity(pattern: PatternSegment[]): number[] {
  const rank: Record<SegmentKind, number> = { static: 2, param: 1, wildcard: 0 };
  return pattern.map((segment) => rank[segment.kind]);
}

/** Compare two specificity vectors. Positive means `a` is more specific. */
export function compareSpecificity(a: number[], b: number[]): number {
  const length = Math.max(a.length, b.length);
  for (let i = 0; i < length; i++) {
    const left = a[i] ?? -1;
    const right = b[i] ?? -1;
    if (left !== right) return left - right;
  }
  return 0;
}

src/middleware.ts: import type { Request, Response } from './types.ts';

export type Next = () => Promise<Response>;
export type Middleware = (request: Request, next: Next) => Promise<Response>;

/**
 * Compose middleware into a single handler.
 *
 * The first entry is outermost: it sees the request first and the response
 * last. Each layer must call `next` at most once; calling it twice would run
 * the rest of the stack again against the same request.
 */
export function compose(layers: Middleware[]): Middleware {
  return function composed(request: Request, final: Next): Promise<Response> {
    let lastCalled = -1;

    function dispatch(index: number): Promise<Response> {
      if (index <= lastCalled) {
        return Promise.reject(new Error('next() called more than once'));
      }
      lastCalled = index;
      if (index === layers.length) return final();
      const layer = layers[index];
      return layer(request, () => dispatch(index + 1));
    }

    return dispatch(0);
  };
}

src/negotiate.ts: /**
 * Content negotiation over an Accept header.
 *
 * Each candidate carries an optional quality between 0 and 1, defaulting to 1.
 * A q of 0 means "not acceptable" and is never selected. Where qualities tie,
 * the order the client listed them in wins, because that is the client's own
 * statement of preference.
 */
export interface Candidate {
  readonly type: string;
  readonly quality: number;
  readonly order: number;
}

export function parseAccept(header: string): Candidate[] {
  const out: Candidate[] = [];
  header.split(',').forEach((part, order) => {
    const pieces = part.trim().split(';');
    const type = pieces[0].trim();
    if (type.length === 0) return;
    let quality = 1;
    for (const piece of pieces.slice(1)) {
      const [name, value] = piece.split('=').map((s) => s.trim());
      if (name === 'q') {
        const parsed = Number(value);
        quality = Number.isFinite(parsed) ? parsed : 1;
      }
    }
    out.push({ type, quality, order });
  });
  return out;
}

/** Pick the best offered type, or undefined when nothing is acceptable. */
export function selectType(header: string, offered: string[]): string | undefined {
  const candidates = parseAccept(header).filter((c) => c.quality > 0);
  let best: Candidate | undefined;

  for (const candidate of candidates) {
    if (!matchesAny(candidate.type, offered)) continue;
    if (best === undefined) {
      best = candidate;
      continue;
    }
    if (candidate.quality > best.quality) best = candidate;
  }

  if (best === undefined) return undefined;
  return offered.find((type) => matches(best.type, type));
}

function matches(pattern: string, type: string): boolean {
  if (pattern === '*/*') return true;
  if (pattern === type) return true;
  const [group] = pattern.split('/');
  return pattern.endsWith('/*') && type.startsWith(group + '/');
}

function matchesAny(pattern: string, offered: string[]): boolean {
  return offered.some((type) => matches(pattern, type));
}

src/params.ts: import { CoercionError } from './errors.ts';

export type ParamValue = string | number | boolean;

/**
 * Coerce a raw path parameter.
 *
 * Only the exact strings 'true' and 'false' are booleans; anything else that
 * looks numeric becomes a number, and everything else stays a string. The
 * string '0' is therefore the number 0, not false -- a route parameter of
 * /items/0 must address item zero.
 */
export function coerce(name: string, raw: string): ParamValue {
  if (raw === 'true') return true;
  if (raw === 'false') return false;
  if (raw.length > 0 && Number.isFinite(Number(raw))) return Number(raw);
  return raw;
}

export function coerceInt(name: string, raw: string): number {
  const value = Number(raw);
  if (!Number.isInteger(value)) throw new CoercionError(name, raw, 'integer');
  return value;
}

export function coerceAll(raw: Record<string, string>): Record<string, ParamValue> {
  const out: Record<string, ParamValue> = {};
  for (const [name, value] of Object.entries(raw)) out[name] = coerce(name, value);
  return out;
}

src/query.ts: /**
 * Query-string parsing.
 *
 * A key that appears more than once collects every value in order, so
 * `?tag=a&tag=b` yields both. A key with no `=` is present with an empty
 * value, which is how flags like `?verbose` are expressed.
 */
export function parseQuery(raw: string): Record<string, string[]> {
  const out: Record<string, string[]> = {};
  const text = raw.startsWith('?') ? raw.slice(1) : raw;
  if (text.length === 0) return out;

  for (const pair of text.split('&')) {
    if (pair.length === 0) continue;
    const index = pair.indexOf('=');
    const rawKey = index === -1 ? pair : pair.slice(0, index);
    const rawValue = index === -1 ? '' : pair.slice(index + 1);
    const key = safeDecode(rawKey);
    const value = safeDecode(rawValue.replace(/\+/g, ' '));
    if (key.length === 0) continue;
    if (out[key]) out[key].push(value);
    else out[key] = [value];
  }
  return out;
}

function safeDecode(raw: string): string {
  try {
    return decodeURIComponent(raw);
  } catch {
    return raw;
  }
}

/** The first value for a key, or undefined when the key is absent. */
export function first(query: Record<string, string[]>, key: string): string | undefined {
  return query[key]?.[0];
}

src/router.ts: import { LruCache } from './cache.ts';
import { DuplicateRoute } from './errors.ts';
import { coerceAll } from './params.ts';
import { RouteTable } from './trie.ts';
import type { Match } from './trie.ts';
import { normalise } from './url.ts';
import type { Handler } from './types.ts';

export interface Resolved {
  readonly handler: Handler;
  readonly params: Record<string, string>;
  readonly pattern: string;
}

/** Method-aware router with a small cache of resolved paths. */
export class Router {
  private readonly tables = new Map<string, RouteTable<Handler>>();
  private readonly cache: LruCache<string, Resolved | null>;

  constructor(cacheSize = 128) {
    this.cache = new LruCache<string, Resolved | null>(cacheSize);
  }

  private tableFor(method: string): RouteTable<Handler> {
    const key = method.toUpperCase();
    let table = this.tables.get(key);
    if (!table) {
      table = new RouteTable<Handler>();
      this.tables.set(key, table);
    }
    return table;
  }

  add(method: string, pattern: string, handler: Handler): void {
    const table = this.tableFor(method);
    const canonical = normalise(pattern);
    if (table.patterns().some((existing) => normalise(existing) === canonical)) {
      throw new DuplicateRoute(pattern);
    }
    table.add(pattern, handler);
    this.cache.clear();
  }

  resolve(method: string, path: string): Resolved | undefined {
    const key = `${method.toUpperCase()} ${normalise(path)}`;
    const cached = this.cache.get(key);
    if (cached !== undefined) return cached ?? undefined;

    const table = this.tables.get(method.toUpperCase());
    const match: Match<Handler> | undefined = table?.match(path);
    const resolved: Resolved | null = match
      ? { handler: match.route.value, params: match.params, pattern: match.route.pattern }
      : null;
    this.cache.set(key, resolved);
    return resolved ?? undefined;
  }

  params(method: string, path: string): Record<string, unknown> {
    const resolved = this.resolve(method, path);
    return resolved ? coerceAll(resolved.params) : {};
  }

  methods(): string[] {
    return [...this.tables.keys()].sort();
  }
}

src/trie.ts: import { compareSpecificity, parsePattern, specificity } from './matcher.ts';
import type { PatternSegment } from './matcher.ts';
import { decodeSegment, segments } from './url.ts';

export interface Route<T> {
  readonly pattern: string;
  readonly parsed: PatternSegment[];
  readonly rank: number[];
  readonly value: T;
}

export interface Match<T> {
  readonly route: Route<T>;
  readonly params: Record<string, string>;
}

/**
 * Route table.
 *
 * Every registered route that matches a path is collected, then the most
 * specific one wins. Registration order never decides a match -- two routers
 * given the same routes in different orders must resolve identically.
 */
export class RouteTable<T> {
  private readonly routes: Route<T>[] = [];

  add(pattern: string, value: T): Route<T> {
    const parsed = parsePattern(pattern);
    const route: Route<T> = { pattern, parsed, rank: specificity(parsed), value };
    this.routes.push(route);
    return route;
  }

  get size(): number {
    return this.routes.length;
  }

  patterns(): string[] {
    return this.routes.map((route) => route.pattern);
  }

  /** Every route matching `path`, most specific first. */
  matchAll(path: string): Match<T>[] {
    const parts = segments(path).map(decodeSegment);
    const found: Match<T>[] = [];

    for (const route of this.routes) {
      const params = tryMatch(route.parsed, parts);
      if (params !== undefined) found.push({ route, params });
    }

    found.sort((a, b) => {
      const bySpecificity = compareSpecificity(b.route.rank, a.route.rank);
      if (bySpecificity !== 0) return bySpecificity;
      return a.route.pattern.localeCompare(b.route.pattern);
    });
    return found;
  }

  match(path: string): Match<T> | undefined {
    return this.matchAll(path)[0];
  }
}

function tryMatch(
  pattern: PatternSegment[],
  parts: string[],
): Record<string, string> | undefined {
  const params: Record<string, string> = {};

  for (let i = 0; i < pattern.length; i++) {
    const segment = pattern[i];
    if (segment.kind === 'wildcard') {
      params[segment.value] = parts.slice(i).join('/');
      return params;
    }
    if (i >= parts.length) return undefined;
    if (segment.kind === 'static') {
      if (segment.value !== parts[i]) return undefined;
      continue;
    }
    params[segment.value] = parts[i];
  }

  return pattern.length === parts.length ? params : undefined;
}

src/types.ts: import type { Headers } from './headers.ts';
import type { ParamValue } from './params.ts';

export interface Request {
  readonly method: string;
  readonly path: string;
  readonly query: Record<string, string[]>;
  readonly headers: Headers;
  readonly params: Record<string, ParamValue>;
}

export interface Response {
  readonly status: number;
  readonly body: string;
}

export type Handler = (request: Request) => Promise<Response>;

src/url.ts: /** Path helpers. Paths are compared as a list of decoded segments. */

/** Split a path into segments, ignoring leading, trailing and repeated slashes. */
export function segments(path: string): string[] {
  return path.split('/').filter((part) => part.length > 0);
}

/** Percent-decode a single segment, leaving it untouched if it is malformed. */
export function decodeSegment(raw: string): string {
  try {
    return decodeURIComponent(raw);
  } catch {
    return raw;
  }
}

/** Normalise a path to a canonical leading-slash, no-trailing-slash form. */
export function normalise(path: string): string {
  const parts = segments(path);
  return parts.length === 0 ? '/' : '/' + parts.join('/');
}

export function joinPath(...parts: string[]): string {
  return normalise(parts.join('/'));
}