Bug report (typescript repo "router"):
Our hottest routes keep falling out of the route cache.

The cache holds 128 entries and we serve far more distinct paths than that, but
a handful of endpoints take almost all the traffic. Those popular endpoints miss
constantly, while paths hit once at start-up survive for ages. Cache hit rate
sits far below what the traffic mix should give.

The cache is meant to evict whatever has gone longest without being *used*.
Please make it do that.

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;
    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('/'));
}


Hidden tests:
tests/cache.test.ts: 
import { test } from 'node:test';
import assert from 'node:assert';
import { LruCache } from '../src/index.ts';

test('reading an entry protects it from eviction', () => {
  const c = new LruCache<string, number>(2);
  c.set('a', 1);
  c.set('b', 2);
  c.get('a');
  c.set('c', 3);
  assert.deepStrictEqual(c.keys().sort(), ['a', 'c']);
});

test('the least recently used key is evicted', () => {
  const c = new LruCache<string, number>(3);
  c.set('a', 1); c.set('b', 2); c.set('c', 3);
  c.get('a'); c.get('c');
  c.set('d', 4);
  assert.deepStrictEqual(c.keys().sort(), ['a', 'c', 'd']);
});

test('a repeatedly read key survives many insertions', () => {
  const c = new LruCache<string, number>(3);
  c.set('hot', 0);
  for (let i = 0; i < 10; i++) {
    c.get('hot');
    c.set('cold' + i, i);
  }
  assert.ok(c.has('hot'));
});

test('reading does not change the size', () => {
  const c = new LruCache<string, number>(2);
  c.set('a', 1); c.set('b', 2);
  c.get('a');
  assert.strictEqual(c.size, 2);
});

test('values are still returned correctly', () => {
  const c = new LruCache<string, number>(2);
  c.set('a', 41);
  assert.strictEqual(c.get('a'), 41);
  assert.strictEqual(c.get('missing'), undefined);
});

test('hit and miss counters still work', () => {
  const c = new LruCache<string, number>(2);
  c.set('a', 1);
  c.get('a'); c.get('nope');
  assert.strictEqual(c.hits, 1);
  assert.strictEqual(c.misses, 1);
});

test('capacity is enforced', () => {
  const c = new LruCache<string, number>(2);
  c.set('a', 1); c.set('b', 2); c.set('c', 3);
  assert.strictEqual(c.size, 2);
});

test('overwriting a key keeps one entry', () => {
  const c = new LruCache<string, number>(2);
  c.set('a', 1); c.set('a', 2);
  assert.strictEqual(c.size, 1);
  assert.strictEqual(c.get('a'), 2);
});


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('/'));
}