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. Reading a header can change it.
   Our logging layer collects a request's Set-Cookie values and appends a redaction
   marker to the list it got back. Downstream, the request carries that marker as a
   real cookie value.
   Reading a header should not hand out a reference the caller can mutate.

2. 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)
    .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;
    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);
});

tests/headers-alias.test.ts: 
import { test } from 'node:test';
import assert from 'node:assert';
import { Headers } from '../src/index.ts';

test('mutating the result does not change the header', () => {
  const h = new Headers({ 'Set-Cookie': 'a=1' });
  h.all('set-cookie').push('REDACTED');
  assert.deepStrictEqual(h.all('set-cookie'), ['a=1']);
});

test('mutation does not leak across reads', () => {
  const h = new Headers({ 'X-A': '1' });
  const first = h.all('x-a');
  first.push('2');
  assert.deepStrictEqual(h.all('x-a'), ['1']);
});

test('get is unaffected by a mutated all()', () => {
  const h = new Headers({ 'X-A': '1' });
  h.all('x-a').length = 0;
  assert.strictEqual(h.get('x-a'), '1');
});

test('multiple values are still returned', () => {
  const h = new Headers();
  h.append('a', '1'); h.append('a', '2');
  assert.deepStrictEqual(h.all('a'), ['1', '2']);
});

test('absent header returns an empty list', () => {
  assert.deepStrictEqual(new Headers().all('nope'), []);
});

test('append still accumulates', () => {
  const h = new Headers();
  h.append('a', '1'); h.append('a', '2'); h.append('a', '3');
  assert.strictEqual(h.all('a').length, 3);
});

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);
});

tests/query.test.ts: 
import { test } from 'node:test';
import assert from 'node:assert';
import { parseQuery, first } from '../src/index.ts';

test('repeated keys collect every value', () => {
  assert.deepStrictEqual(parseQuery('?tag=red&tag=blue&tag=green').tag,
                         ['red', 'blue', 'green']);
});

test('order is preserved', () => {
  assert.deepStrictEqual(parseQuery('a=1&a=2&a=3').a, ['1', '2', '3']);
});

test('repeats mixed with singles', () => {
  const q = parseQuery('tag=a&page=2&tag=b');
  assert.deepStrictEqual(q.tag, ['a', 'b']);
  assert.deepStrictEqual(q.page, ['2']);
});

test('duplicate identical values are all kept', () => {
  assert.deepStrictEqual(parseQuery('x=1&x=1').x, ['1', '1']);
});

test('single values still work', () => {
  assert.deepStrictEqual(parseQuery('?page=2'), { page: ['2'] });
});

test('valueless keys are present and empty', () => {
  assert.deepStrictEqual(parseQuery('?verbose').verbose, ['']);
});

test('percent and plus decoding still work', () => {
  assert.deepStrictEqual(parseQuery('q=a%20b').q, ['a b']);
  assert.deepStrictEqual(parseQuery('q=a+b').q, ['a b']);
});

test('empty query is an empty object', () => {
  assert.deepStrictEqual(parseQuery(''), {});
  assert.deepStrictEqual(parseQuery('?'), {});
});

test('first() returns the leading value', () => {
  assert.strictEqual(first(parseQuery('tag=a&tag=b'), 'tag'), 'a');
  assert.strictEqual(first(parseQuery(''), 'tag'), undefined);
});


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