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: ...
}

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 * of OPTIONS * and the authority form of CONNECT match nothing, so the program answers them before it routes.
  • A path is split on / into segments; /a/ has two, a and an empty one. A trailing slash is significant, and matching is on raw bytes, so %2F never 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[]required

the buffer the range points into, usually the request head

starti32required

where the raw parameter starts in target

endi32required

where the raw parameter ends in target

outu8[]required

where the decoded bytes go, from index 0; the caller's buffer

returnsi32

how 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.