Use a tree for routing

[ysbaddaden]

The idea is to generate a tree of routes, using the different segments for each node, which may either be a static string (eg: posts) or a variable (eg: :id) with or without a regexp match (eg: /^\d+$/) or always matching (eg: *path).

Resolving a route should then be (almost) constant time, and not tied to wherever the route is defined first or last. Currently, hitting the first matching route is fast (we run a single regular expression) but matching the last route is slow (we run N regular expressions, where N can grow quickly). We can define the most important routes first, and the less used ones last, but what about when the route doesn't exist? A potential DDoS is to hit long URI, so each regexp is slow, and that doesn't match.

I don't know what will happen to the before and after blocks. Maybe they can just become attributes to the tree node, and run whenever the node matches.