routing.rst

Improve routing

Goals:

• Improve performace by not testing routes unnecessarily
• Provide an ordering of routes based on specificity of a route pattern.

Routing in other systems

Nginx

http://wiki.nginx.org/HttpCoreModule#location

1. Directives with the "=" prefix that match the query exactly (literal string). If found, searching stops.

• Simple route pattern, /foo.html

2. All remaining directives with conventional strings. If this match used the "^~" prefix, searching stops.

• Could be considered as a Pyramid route with path segments, e.g. /foo/*fizzle

3. Regular expressions, in the order they are defined in the configuration file.
4. If #3 yielded a match, that result is used. Otherwise, the match from #2 is used.

Apache

http://serverfault.com/questions/391457/how-does-apache-merge-multiple-matching-location-sections

All matching locations are merged, where their directives conflict the last one by configuration file order usually wins.

A very draft proposal

Given the following route definitions, how should they be ordered?:

/foo/{name}.html
/foo/foo-{name}.html
/foo/foo-page.html
/foo/{name}
/foo/*path

For me, the natural ordering by specificity seems to be:

/foo/foo-page.html
/foo/foo-{name}.html
/foo/{name}.html
/foo/{name}
/foo/*path

How could this be achieved? Order each path segment based on its string and pattern components. For example: foo-{name}.html becomes:

<str:foo-> <pat:{name}> <str:.html>

Compare path segments by:

1. A sole <str> component sorts first. Order between sole <str> components does not matter.
2. Where a path segment includes a pattern component, path segments beginning with a <str> component sort before path segments s beginning with a <pat> component.
3. Then path segments with the most string components sort first. foo-{bar}.html sorts before foo-{bar}
4. <*path> components sort last.

I guess first of all path segments should be normalized so that adjacent patterns are merged, e.g: foo-{bar}{baz}.html => foo-{name}.html.

Execution

We now have an ordered tree with the configured route patterns at the leaf nodes. Each internal node is a match against a partial pattern sorted as above. The tree is traversed in order matching against each pattern. When lead match is found execution stops.

Fallback ordering of declarative routes

What happens when two routes have the same specificity? We should fallback to the configured order. Declaratively configured routes are not currently allowed as there is no implied ordering from config.scan / iter_modules. Venusian could sort modules by name before scanning to provide a consistent configuration ordering.