Algorithm for ordering routes

algorithm-for-orderiner g-routes.md

An algorithm for ordering routes

Definition of a "route"

For the purposes of this algorithm, a route is a string containing:

• An optional HTTP verb (or ALL) prefix, followed by a space, followed by:
• 1 or more path components, where each path component is:
  • A forward slash /, followed by:
  • A colon : followed by any combination of letters and numbers (a "param"), OR
  • A star * OR (a "wildcard")
  • Any combination of letters and numbers (a "static path component")

In other words, any Express-compatible route path.

Algorithm

Given an unordered list of routes:

1. Find the maximum number of parts (maxParts) in any route, by ignoring the optional prefix and splitting each route on /

2. For each route, construct a string (rank) by examining each part in the route from left to right and:

   • Adding a 1 to the string for each static path component
   • Adding a 2 to the string for each param component
   • Adding a 3 to the string for each wildcard component
   • If the route being examined has fewer than maxParts parts, pad the string with 0s if no wildcards were encountered, or 4s if wildcards were encountered.
   • Add a 0 to the end of the string if the route has a specific verb prefix (i.e. not ALL), and a 1 if it has a ALL prefix or no prefix.
   • Finally, prefix a 5 at the beginning of the string if the path has no static components¹.

3. Sort the routes by their rank, with lesser ranks coming before greater ones.

Example

RANK  ROUTE
----  -----
1000  GET /foo
1001  /foo
1101  /foo/bar
1111  /foo/bar/baz
1120  GET /foo/bar/:baz
1121  /foo/bar/:baz
1130  GET /foo/bar/*
1131  /foo/bar/*
1201  /foo/:bar
1211  /foo/:bar/baz
1221  /foo/:bar/:baz
1311  /foo/*/baz
1341  /foo/*
2101  /:foo/bar
2111  /:foo/bar/baz
2121  /:foo/bar/:baz
2211  /:foo/:bar/baz
3111  /*/bar/baz
3131  /*/baz/*
3141  /*/baz
52001 /:foo
52201 /:foo/:bar
52221 /:foo/:bar/:baz
52231 /:foo/:bar/*
52341 /:foo/*
53440 GET /*
53441 /*

---

¹: This ensures that routes like /*/baz/* are ranked above ones like /:foo/:bar/:baz -- the static baz component implies that the author intends for */baz/* to handle request URLs of at least three components, one of which is baz; if /:foo/:bar/:baz/ were ranked higher in the list, it would swallow the subset of those URLs with exactly three components.