Skip to main content
Module

x/router/mod.ts

A high-performance basic router works anywhere.
Latest
File
export class Node<T = Function> { children = new Map<string, Node<T>>(); path = ""; handler: T | undefined;
constructor(node?: Partial<Node<T>>) { if (node) { Object.assign(this, node); } }
add(path: string, handler: T): void { let n: Node<T> = this;
let i = 0; for (; i < path.length && !isWildcard(path[i]); ++i); n = n.#merge(path.slice(0, i));
let j = i; for (; i < path.length; ++i) { if (isWildcard(path[i])) { if (j !== i) { // insert static route n = n.#insert(path.slice(j, i)); j = i; }
++i;
for (; i < path.length && path[i] !== "/"; ++i) { if (isWildcard(path[i])) { throw new Error( `only one wildcard per path segment is allowed, has: "${ path.slice( j, i, ) }" in path "${path}"`, ); } } if (path[j] === ":" && i - j === 1) { throw new Error( `param must be named with a non-empty name in path "${path}"`, ); } // insert wildcard route n = n.#insert(path.slice(j, i)); j = i; } }
if (j === path.length) { n.#merge("", handler); } else { n.#insert(path.slice(j), handler); } }
find( path: string, ): [handler: T | undefined, params: Map<string, string>] { let handler: T | undefined; let params = new Map<string, string>();
const stack: [node: Node<T>, path: string, vis: boolean][] = [ [this, path, false], ];
for (let i = 0; i >= 0;) { const [n, p, v] = stack[i];
let np: string | undefined; // next path
if (v) { --i; // assert not "*" if (n.path[0] === ":") { params.delete(n.path.slice(1)); } continue; } else { // vis = true stack[i][2] = true; }
if (n.path[0] === "*") { if (n.path.length > 1) { params.set(n.path.slice(1), p); } np = undefined; } else if (n.path[0] === ":") { const [_cp, _np] = splitFromFirstSlash(p); params.set(n.path.slice(1), _cp); np = _np === "" ? undefined : _np; } else if (n.path === p) { if (n.handler === undefined) { if (n.children.has("*")) { np = ""; } else { --i; continue; } } else { np = undefined; } } else { const lcp = longestCommonPrefix(n.path, p); if (lcp !== n.path.length) { --i; continue; } else { np = p.slice(lcp); } }
if (np === undefined) { handler = n.handler; break; }
let c = n.children.get("*"); if (c) { stack[++i] = [c, np, false]; }
if (np === "") { continue; }
c = n.children.get(":"); if (c) { stack[++i] = [c, np, false]; }
c = n.children.get(np[0]); if (c) { stack[++i] = [c, np, false]; } }
return [handler, params]; }
#merge = (path: string, handler?: T): Node<T> => { let n: Node<T> = this;
if (n.path === "" && n.children.size === 0) { n.path = path; n.handler = handler;
return n; }
if (path === "") { if (n.handler) { throw new Error( `a handler is already registered for path "${n.path}"`, ); } n.handler = handler;
return n; }
for (;;) { const i = longestCommonPrefix(path, n.path);
if (i < n.path.length) { const c = new Node({ path: n.path.slice(i), children: n.children, handler: n.handler, });
n.children = new Map([[c.path[0], c]]); n.path = path.slice(0, i); n.handler = undefined; }
if (i < path.length) { path = path.slice(i); let c = n.children.get(path[0]);
if (c) { n = c; continue; }
c = new Node({ path, handler }); n.children.set(path[0], c); n = c; } else if (handler) { if (n.handler) { throw new Error( `a handler is already registered for path "${path}"`, ); } n.handler = handler; }
break; }
return n; };
#insert = (path: string, handler?: T): Node<T> => { let n: Node<T> = this;
let c = n.children.get(path[0]);
if (c) { n = c.#merge(path, handler); } else { c = new Node({ path, handler }); n.children.set(path[0], c); n = c; }
return n; };}
function longestCommonPrefix(a: string, b: string): number { let i = 0; let len = Math.min(a.length, b.length); for (; i < len && a[i] === b[i]; ++i);
return i;}
function splitFromFirstSlash( path: string,): [cp: string, np: string] { let i = 0; for (; i < path.length && path[i] !== "/"; ++i); return [path.slice(0, i), path.slice(i)];}
function isWildcard(c: string): boolean { assert(c.length === 1);
return c === ":" || c === "*";}
function assert(expr: unknown, msg = ""): asserts expr { if (!expr) { throw new AssertionError(msg); }}
class AssertionError extends Error { constructor(message: string) { super(message); this.name = "AssertionError"; }}