nish/net/router
A method and path router for HTTP servers, independent of the carrier: the same table answers an HTTP/1 request line and an HTTP/2 or HTTP/3 :path.
import {
ROUTER_AMBIGUOUS,
ROUTER_BAD_ESCAPE,
ROUTER_BAD_METHOD,
ROUTER_BAD_PATTERN,
ROUTER_DUPLICATE,
ROUTER_FULL,
ROUTER_METHOD_NOT_ALLOWED,
ROUTER_NOT_FOUND,
ROUTER_NO_ROOM,
ROUTER_TOO_LONG,
ROUTER_TOO_MANY_PARAMS,
Router,
RouterLimits,
routerDecode,
} from "nish/net/router";
const HOME: i32 = 0 // module constants, in the order the routes are added
const USER: i32 = 1
const router = new Router(new RouterLimits())
if (router.add("GET", "/") !== HOME || router.add("GET", "/users/:id") !== USER) panic(...)
// per request, with `params` made once beside the connection:
switch (router.match(p.head, p.methodStart, p.methodEnd, p.head, p.targetStart, p.targetEnd, params)) {
case HOME: ... case USER: ... case ROUTER_NOT_FOUND: ...
}
routerDecode
Percent-decodes target[start .. end), one range match answered, into out from 0, and answers the decoded length or a negative ROUTER_* code; on a code nothing is written.
Router
A route table: a tree whose edges are path segments, kept in flat arrays.
RouterLimits
What a Router holds and refuses past.
Nish has no function values, so a route is the index add answered, 0 for
the first and one more for each after, and the program dispatches on it
with switch, whose labels are module constants. A parameter is answered as a
[start, end) pair of offsets into the target, never as a copy, and
routerDecode percent-decodes one of them into a buffer the caller owns.
The table is built once; a match allocates nothing
add refuses a
duplicate, an ambiguous or an over-long pattern with a negative code and
adds nothing. match walks flat i32 arrays the table grew and writes into
scratch the constructor sized, so a warmed server moves the arena by
nothing per request. A Router is therefore not reentrant: one match at a
time, which is what a connection loop does.
A route with no parameter and no `*` is answered without the tree
add
also files such a route under a hash of its method and path, in one more
flat array, and match looks there first, for a target no longer than the
longest such route: one pass over the path, at most ROUTER_PROBES slots,
and a byte comparison for a slot whose method and length agree. The
tree stays the definition: a literal is tried first at every segment, so
the route the exact table holds for a method and a path is the one the tree
would have reached, and anything the table does not hold falls through to
the tree unchanged. matchTree is the tree alone, for a test of exactly that.
The rules
The rules (docs/wp43-http-app-layer.md §2):
-
The path is the target up to its first
?(the query is left alone) and must start with/: the*ofOPTIONS *and the authority form ofCONNECTmatch nothing, so the program answers them before it routes. -
A path is split on
/into segments;/a/has two,aand an empty one. A trailing slash is significant, and matching is on raw bytes, so%2Fnever splits a segment. -
A pattern segment is a literal, a parameter
:name(one non-empty segment), or*as the last segment (the rest of the path, possibly empty, as one more pair). Precedence is literal, then parameter, then wildcard, segment by segment from the left; a branch that fails further down falls back to the next one. Every edge consumes one segment, so a lookup visits each node of the table at most once. -
A path that matches only routes of other methods answers
ROUTER_METHOD_NOT_ALLOWED, so a server can tell 405 from 404.
What is unchecked
routerSameBytes reads with nish:unsafe's
uncheckedGet, after one check that both ranges are inside their arrays;
a range that is not compares unequal, as a byte that differs does. It is
the one byte compare a lookup makes: a method of more than seven bytes
against each known one (a shorter one is one packed word, routerMethodKey),
a path against a static route's, a segment against a label.
routerMethodKey reads its at most seven bytes the same way, after the same
one range check; a range outside the array packs to 0, which no method is.
Every other read is checked.
Private helpers share the importing program's flat symbol namespace
(docs/wp26-stdlib.md §3e), which is why each one carries the module's name.
Functions
routerDecode
Percent-decodes target[start .. end), one range match answered, into
out from 0, and answers the decoded length or a negative ROUTER_* code;
on a code nothing is written. %2F becomes / here, inside the one
parameter, because match split the path before anything was decoded. +
stays +: a space spelled + is the query's form encoding, not the path's.
The output may hold any byte, NUL and / included. Panics on a range
outside target.
const routerDecode: (
target: u8[],
start: i32,
end: i32,
out: u8[],
) => i32
targetu8[]requiredthe buffer the range points into, usually the request head
starti32requiredwhere the raw parameter starts in target
endi32requiredwhere the raw parameter ends in target
outu8[]requiredwhere the decoded bytes go, from index 0; the caller's buffer
returnsi32how many decoded bytes were written, or ROUTER_BAD_ESCAPE or ROUTER_NO_ROOM
Classes
Router
A route table: a tree whose edges are path segments, kept in flat arrays.
Node 0 is the root, the point before the first segment; a node at depth d
has consumed d segments.
class Router
| Member | |
|---|---|
new Router(limits: RouterLimits) |
An empty table. Panics, naming the field, on a limit outside the range RouterLimits gives it. |
add(method: string, pattern: string): i32 |
Adds the route method pattern and answers its index, counting from 0, or a negative ROUTER_* code; a refused pattern adds nothing. Whether a pattern is refused never depends on the order routes were added in. |
lastVisited(): i32 |
How many nodes of the tree the last match visited. |
match(method: u8[], mStart: i32, mEnd: i32, target: u8[], tStart: i32, tEnd: i32, params: i32[]): i32 |
The route method[mStart .. mEnd) and target[tStart .. tEnd) reach, or a negative ROUTER_* code. On a route, its parameters are written to params as [start, end) offsets into target, two slots each, in the pattern's order, and a final * as one more pair; on a refusal params is untouched. Panics on a range outside its array. |
matchTree(method: u8[], mStart: i32, mEnd: i32, target: u8[], tStart: i32, tEnd: i32, params: i32[]): i32 |
What match answers, found by the tree alone: the exact-path table is not read. The two agree on every method and target, in the route or code they answer, in params and in where the path ends; this one is the definition and exists so that a test can hold match to it. |
nodeCount(): i32 |
How many nodes the tree has, the root included: the most one match visits. |
paramCount(route: i32): i32 |
How many [start, end) pairs route answers: its parameters, and one more for a final *. |
staticCount(): i32 |
How many routes the exact-path table holds: the routes match answers without the tree. Every route with no parameter and no * is one, but for a route whose slots were all taken, which the tree answers instead. |
RouterLimits
What a Router holds and refuses past. Each field has a default a server
can use as it is; the constructor panics on a value no table could work with.
class RouterLimits
| Member | |
|---|---|
new RouterLimits() |
|
maxMethods: i32 |
The most distinct methods (1 to 64). |
maxParams: i32 |
The most parameters in one pattern, a final * counted (0 to 256). |
maxPatternBytes: i32 |
The longest pattern, in bytes (1 to 65536). |
maxRoutes: i32 |
The most routes in the table (1 to 1048576). |
maxSegments: i32 |
The most segments in one pattern (1 to 256): the deepest a route can be. |
Constants
-4
ROUTER_AMBIGUOUS: i32
add: a * that is not the last segment, where how much it takes would be a guess.
-10
ROUTER_BAD_ESCAPE: i32
routerDecode: a % not followed by two hex digits.
-2
ROUTER_BAD_METHOD: i32
add: the method is not a token of 1 to 32 bytes.
-1
ROUTER_BAD_PATTERN: i32
add: the pattern is empty, does not start with /, or misuses :, *, %, ? or a byte outside ! to ~.
-5
ROUTER_DUPLICATE: i32
add: the method already has a route of this shape, whatever its parameters are called.
-6
ROUTER_FULL: i32
add: the table holds RouterLimits.maxRoutes routes or maxMethods methods already.
-8
ROUTER_METHOD_NOT_ALLOWED: i32
match: the path matches only routes of other methods.
-7
ROUTER_NOT_FOUND: i32
match: no route's pattern matches the path, or the target is not /-rooted.
-11
ROUTER_NO_ROOM: i32
routerDecode: the decoded bytes do not fit out; nothing was written.
-3
ROUTER_TOO_LONG: i32
add: the pattern is over RouterLimits' bytes, segments or parameters.
-9
ROUTER_TOO_MANY_PARAMS: i32
match: the route matched, but its parameters need more than params holds; nothing was written.

